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       IdExp * id       = new IdExp;
 214       id->symbol       = new Symbol;
 215       id->symbol->name = node.symbol->name + "_" + nextId();;
 216       id->symbol->type = unreferencedType(node.type);
 217       id->type         = id->symbol->type;
 218       replacement_     = id;
 219
 220       LoadVar * lv = new LoadVar;
 221       lv->to       = id->symbol->name;
 222       lv->from     = &node;
 223       simplifications_.push_back(lv);
 224     }
 225     else
 226       replacement_ = &node;
 227   }
 228
 229   void
 230   SimplifyVisitor::visit(DereferenceExp & node)
 231   {
 232     node.exp->accept(*this);
 233     node.exp = replacement_;
 234
 235     LoadVar * lv = new LoadVar;
 236     lv->to       = nextId();
 237     lv->from     = node.exp;
 238     simplifications_.push_back(lv);
 239
 240     IdExp * id          = new IdExp;
 241     id->symbol          = new Symbol;
 242     id->symbol->name    = lv->to;
 243     id->symbol->type    = node.type;
 244     id->symbol->address = new RegisterAddress;
 245     id->type            = node.type;
 246     replacement_        = id;
 247   }
 248
 249   void
 250   SimplifyVisitor::visit(CallExp & node)
 251   {
 252     BOOST_FOREACH (Exp *& exp, (*node.args))
 253     {
 254       exp->accept(*this);
 255       exp = replacement_;
 256     }
 257
 258     makeTmpResult(node);
 259   }
 260
 261   /**
 262    * @internal
 263    * develop the cast, and simplify it
 264    */
 265   void
 266   SimplifyVisitor::visit(CastExp & node)
 267   {
 268     node.exp->accept(*this);
 269     node.exp = replacement_;
 270
 271     if (!castToBestType(node.type, node.exp->type))
 272       return;
 273
 274     makeTmpResult(node);
 275   }
 276
 277   void
 278   SimplifyVisitor::visit(Label & node)
 279   {
 280     simplifications_.push_back(&node);
 281   }
 282
 283   void
 284   SimplifyVisitor::visit(Goto & node)
 285   {
 286     simplifications_.push_back(&node);
 287   }
 288
 289   void
 290   SimplifyVisitor::visit(Return & node)
 291   {
 292     node.exp->accept(*this);
 293     node.exp = replacement_;
 294     simplifications_.push_back(&node);
 295   }
 296
 297   void
 298   SimplifyVisitor::visit(If & node)
 299   {
 300     node.branch->cond->accept(*this);
 301     assert(replacement_);
 302     node.branch->cond = replacement_;
 303
 304     simplifications_.push_back(node.branch);
 305
 306     node.branch->trueLabel = new Label;
 307     node.branch->trueLabel->name = std::string("if_true_") + nextId();
 308     node.branch->falseLabel = new Label;
 309     node.branch->falseLabel->name = std::string("if_false_") + nextId();
 310     node.endLabel = new Label;
 311     node.endLabel->name = std::string("if_end_") + nextId();
 312
 313     simplifications_.push_back(node.branch->trueLabel);
 314     node.trueBlock->accept(*this);
 315     Goto * gotoNode = new Goto;
 316     gotoNode->label = node.endLabel->name;
 317
 318     simplifications_.push_back(node.branch->falseLabel);
 319     node.falseBlock->accept(*this);
 320     simplifications_.push_back(node.endLabel);
 321   }
 322
 323   void
 324   SimplifyVisitor::visit(While & node)
 325   {
 326     assert(node.block);
 327     assert(node.branch->cond);
 328
 329     node.beginLabel = new Label;
 330     node.beginLabel->name = std::string("do_while_1_") + nextId();
 331     node.branch->trueLabel = new Label;
 332     node.branch->trueLabel->name = std::string("do_while_2_") + nextId();
 333     node.branch->falseLabel = new Label;
 334     node.branch->falseLabel->name = std::string("do_while_3_") + nextId();
 335
 336     simplifications_.push_back(node.beginLabel);
 337     node.branch->cond->accept(*this);
 338     node.branch->cond = replacement_;
 339     simplifications_.push_back(node.branch);
 340     simplifications_.push_back(node.branch->trueLabel);
 341     node.block->accept(*this);
 342     node.block = replacement_;
 343
 344     Goto * gt = new Goto;
 345     gt->label = node.beginLabel->name;
 346     simplifications_.push_back(gt);
 347     simplifications_.push_back(node.branch->falseLabel);
 348   }
 349
 350   void
 351   SimplifyVisitor::visit(DoWhile & node)
 352   {
 353     assert(node.block);
 354     assert(node.branch->cond);
 355
 356     node.branch->trueLabel = new Label;
 357     node.branch->trueLabel->name = std::string("do_while_1_") + nextId();
 358     node.branch->falseLabel = new Label;
 359     node.branch->falseLabel->name = std::string("do_while_2_") + nextId();
 360     simplifications_.push_back(node.branch->trueLabel);
 361
 362     node.block->accept(*this);
 363     node.block = replacement_;
 364     node.branch->cond->accept(*this);
 365     node.branch->cond = replacement_;
 366
 367     replacement_ = 0;
 368     simplifications_.push_back(node.branch);
 369     simplifications_.push_back(node.branch->falseLabel);
 370   }
 371 }