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