src/ast/simplify-visitor.cc

   1 #include <sstream>
   2 #include <boost/foreach.hpp>
   3
   4 #include <core/assert.hh>
   5 #include <ast/cast-tables.hh>
   6 #include "simplify-visitor.hh"
   7
   8 namespace ast
   9 {
  10   /// @defgroup Visitors
  11   /**
  12    * @class SimplifyVisitor
  13    * @ingroup Visitors
  14    *
  15    * <b>Algorithm</b><br>
  16    * - on Block
  17    *  - for every instruction
  18    *   - split the instruction in 3 address instruction
  19    */
  20
  21   SimplifyVisitor::SimplifyVisitor()
  22     : BrowseVisitor(),
  23       simplifications_(0),
  24       replacement_(0),
  25       nextId_(0)
  26   {
  27   }
  28
  29   SimplifyVisitor::~SimplifyVisitor()
  30   {
  31   }
  32
  33   std::string
  34   SimplifyVisitor::nextId()
  35   {
  36     std::stringstream ss;
  37     ss << "r" << ++nextId_;
  38     return ss.str();
  39   }
  40
  41   std::string
  42   SimplifyVisitor::currentId() const
  43   {
  44     std::stringstream ss;
  45     ss << "r" << nextId_;
  46     return ss.str();
  47   }
  48
  49   void
  50   SimplifyVisitor::makeTmpResult(Exp & node)
  51   {
  52     if (node.type->nodeType == VoidType::nodeTypeId())
  53     {
  54       replacement_ = 0;
  55       simplifications_.push_back(&node);
  56       return;
  57     }
  58
  59     AssignExp * assign = new AssignExp();
  60     assign->value = &node;
  61     assign->dest = new Symbol();
  62     assign->dest->name = nextId();
  63     assign->dest->type = node.type;
  64     assign->type = node.type;
  65     simplifications_.push_back(assign);
  66
  67     TmpResultExp * tre = new TmpResultExp();
  68     tre->name = assign->dest->name;
  69     tre->type = node.type;
  70     replacement_ = tre;
  71   }
  72
  73   void
  74   SimplifyVisitor::visit(Block & block)
  75   {
  76     std::vector<Node *> backup = simplifications_;
  77     simplifications_.clear();
  78
  79     BOOST_FOREACH (Node * node, (*block.statements))
  80     {
  81       assert(node);
  82       node->accept(*this);
  83     }
  84
  85     *block.statements = simplifications_;
  86     simplifications_ = backup;
  87   }
  88
  89   void
  90   SimplifyVisitor::visit(Exp & /*node*/)
  91   {
  92     assert_msg(false, "unimplemented visit method");
  93   }
  94
  95   void
  96   SimplifyVisitor::visit(VoidExp & node)
  97   {
  98     replacement_ = &node;
  99   }
 100
 101 #define SIMPLIFY_UNARY_EXP(Type)                                        \
 102   /**                                                                   \
 103    * @internal                                                          \
 104    * - Simplify childs                                                  \
 105    * - Create a new id.                                                 \
 106    * - Create a new assign exp to id.                                   \
 107    * - Create a IdExp and tell replace the parent's child with it.      \
 108    */                                                                   \
 109   void                                                                  \
 110   SimplifyVisitor::visit(Type & node)                                   \
 111   {                                                                     \
 112     assert(node.exp);                                                   \
 113     node.exp->accept(*this);                                            \
 114     node.exp = replacement_;                                            \
 115                                                                         \
 116     makeTmpResult(node);                                                \
 117   }
 118
 119   SIMPLIFY_UNARY_EXP(NotExp)
 120   SIMPLIFY_UNARY_EXP(BangExp)
 121   SIMPLIFY_UNARY_EXP(NegExp)
 122
 123 #define SIMPLIFY_BINARY_EXP(Type)                                       \
 124   /**                                                                   \
 125    * @internal                                                          \
 126    * - Simplify childs                                                  \
 127    * - Create a new id.                                                 \
 128    * - Create a new assign exp to id.                                   \
 129    * - Create a IdExp and tell replace the parent's child with it.      \
 130    */                                                                   \
 131   void                                                                  \
 132   SimplifyVisitor::visit(Type & node)                                   \
 133   {                                                                     \
 134     assert(node.left);                                                  \
 135     node.left->accept(*this);                                           \
 136     node.left = replacement_;                                           \
 137     assert(node.right);                                                 \
 138     node.right->accept(*this);                                          \
 139     node.right = replacement_;                                          \
 140                                                                         \
 141     makeTmpResult(node);                                                \
 142   }
 143
 144   SIMPLIFY_BINARY_EXP(EqExp)
 145   SIMPLIFY_BINARY_EXP(NeqExp)
 146   SIMPLIFY_BINARY_EXP(LtExp)
 147   SIMPLIFY_BINARY_EXP(LtEqExp)
 148   SIMPLIFY_BINARY_EXP(GtExp)
 149   SIMPLIFY_BINARY_EXP(GtEqExp)
 150
 151   SIMPLIFY_BINARY_EXP(AddExp)
 152   SIMPLIFY_BINARY_EXP(SubExp)
 153   SIMPLIFY_BINARY_EXP(MulExp)
 154   SIMPLIFY_BINARY_EXP(DivExp)
 155   SIMPLIFY_BINARY_EXP(ModExp)
 156
 157   SIMPLIFY_BINARY_EXP(AndExp)
 158   SIMPLIFY_BINARY_EXP(OrExp)
 159   SIMPLIFY_BINARY_EXP(XorExp)
 160
 161   SIMPLIFY_BINARY_EXP(AndAndExp)
 162   SIMPLIFY_BINARY_EXP(OrOrExp)
 163
 164   SIMPLIFY_BINARY_EXP(ShlExp)
 165   SIMPLIFY_BINARY_EXP(AShrExp)
 166   SIMPLIFY_BINARY_EXP(LShrExp)
 167
 168   void
 169   SimplifyVisitor::visit(AssignExp & node)
 170   {
 171     assert(node.value);
 172     node.value->accept(*this);
 173     node.value = replacement_;
 174
 175     StoreVar * sv = new StoreVar();
 176     sv->name = node.dest->name;
 177     sv->value = replacement_;
 178     simplifications_.push_back(sv);
 179
 180     delete &node;
 181   }
 182
 183   void
 184   SimplifyVisitor::visit(NumberExp & node)
 185   {
 186     replacement_ = &node;
 187   }
 188
 189   void
 190   SimplifyVisitor::visit(IdExp & node)
 191   {
 192     LoadVar * lv = new LoadVar();
 193     lv->name = node.name;
 194     lv->to = nextId();
 195     lv->type = node.type;
 196     simplifications_.push_back(lv);
 197
 198     TmpResultExp * tre = new TmpResultExp();
 199     tre->name = lv->to;
 200     tre->type = node.type;
 201     replacement_ = tre;
 202     delete &node;
 203   }
 204
 205   void
 206   SimplifyVisitor::visit(CallExp & node)
 207   {
 208     BOOST_FOREACH (Exp *& exp, (*node.args))
 209     {
 210       exp->accept(*this);
 211       exp = replacement_;
 212     }
 213
 214     makeTmpResult(node);
 215   }
 216
 217   /**
 218    * @internal
 219    * develop the cast, and simplify it
 220    */
 221   void
 222   SimplifyVisitor::visit(CastExp & node)
 223   {
 224     node.exp->accept(*this);
 225     node.exp = replacement_;
 226
 227     if (!castToBestType(node.type, node.exp->type))
 228       return;
 229
 230     makeTmpResult(node);
 231   }
 232
 233   void
 234   SimplifyVisitor::visit(Label & node)
 235   {
 236     simplifications_.push_back(&node);
 237   }
 238
 239   void
 240   SimplifyVisitor::visit(Goto & node)
 241   {
 242     simplifications_.push_back(&node);
 243   }
 244
 245   void
 246   SimplifyVisitor::visit(Return & node)
 247   {
 248     node.exp->accept(*this);
 249     node.exp = replacement_;
 250     simplifications_.push_back(&node);
 251   }
 252
 253   void
 254   SimplifyVisitor::visit(If & node)
 255   {
 256     node.branch->cond->accept(*this);
 257     assert(replacement_);
 258     node.branch->cond = replacement_;
 259
 260     simplifications_.push_back(node.branch);
 261
 262     node.branch->trueLabel = new Label;
 263     node.branch->trueLabel->name = std::string("if_true_") + nextId();
 264     node.branch->falseLabel = new Label;
 265     node.branch->falseLabel->name = std::string("if_false_") + nextId();
 266     node.endLabel = new Label;
 267     node.endLabel->name = std::string("if_end_") + nextId();
 268
 269     simplifications_.push_back(node.branch->trueLabel);
 270     node.trueBlock->accept(*this);
 271     Goto * gotoNode = new Goto;
 272     gotoNode->label = node.endLabel->name;
 273
 274     simplifications_.push_back(node.branch->falseLabel);
 275     node.falseBlock->accept(*this);
 276     simplifications_.push_back(node.endLabel);
 277   }
 278
 279   void
 280   SimplifyVisitor::visit(While & node)
 281   {
 282     assert(node.block);
 283     assert(node.branch->cond);
 284
 285     node.beginLabel = new Label;
 286     node.beginLabel->name = std::string("do_while_1_") + nextId();
 287     node.branch->trueLabel = new Label;
 288     node.branch->trueLabel->name = std::string("do_while_2_") + nextId();
 289     node.branch->falseLabel = new Label;
 290     node.branch->falseLabel->name = std::string("do_while_3_") + nextId();
 291
 292     simplifications_.push_back(node.beginLabel);
 293     node.branch->cond->accept(*this);
 294     node.branch->cond = replacement_;
 295     simplifications_.push_back(node.branch);
 296     simplifications_.push_back(node.branch->trueLabel);
 297     node.block->accept(*this);
 298     node.block = replacement_;
 299
 300     Goto * gt = new Goto;
 301     gt->label = node.beginLabel->name;
 302     simplifications_.push_back(gt);
 303     simplifications_.push_back(node.branch->falseLabel);
 304   }
 305
 306   void
 307   SimplifyVisitor::visit(DoWhile & node)
 308   {
 309     assert(node.block);
 310     assert(node.branch->cond);
 311
 312     node.branch->trueLabel = new Label;
 313     node.branch->trueLabel->name = std::string("do_while_1_") + nextId();
 314     node.branch->falseLabel = new Label;
 315     node.branch->falseLabel->name = std::string("do_while_2_") + nextId();
 316     simplifications_.push_back(node.branch->trueLabel);
 317
 318     node.block->accept(*this);
 319     node.block = replacement_;
 320     node.branch->cond->accept(*this);
 321     node.branch->cond = replacement_;
 322
 323     replacement_ = 0;
 324     simplifications_.push_back(node.branch);
 325     simplifications_.push_back(node.branch->falseLabel);
 326   }
 327 }