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