src/ast/simplify-visitor.cc

   1 #include <sstream>
   2 #include <boost/foreach.hpp>
   3
   4 #include <core/assert.hh>
   5 #include "simplify-visitor.hh"
   6 #include "type-checker-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::visit(Block & block)
  51   {
  52     std::vector<Node *> backup = simplifications_;
  53     simplifications_.clear();
  54
  55     BOOST_FOREACH (Node * node, (*block.statements))
  56     {
  57       assert(node);
  58       node->accept(*this);
  59     }
  60
  61     *block.statements = simplifications_;
  62     simplifications_ = backup;
  63   }
  64
  65 #define SIMPLIFY_BINARY_EXP(Type)                                       \
  66   /**                                                                   \
  67    * @internal                                                          \
  68    * - Simplify childs                                                  \
  69    * - Create a new id.                                                 \
  70    * - Create a new assign exp to id.                                   \
  71    * - Create a IdExp and tell replace the parent's child with it.      \
  72    */                                                                   \
  73   void                                                                  \
  74   SimplifyVisitor::visit(Type & node)                                   \
  75   {                                                                     \
  76     assert(node.left);                                                  \
  77     node.left->accept(*this);                                           \
  78     node.left = replacement_;                                           \
  79     assert(node.right);                                                 \
  80     node.right->accept(*this);                                          \
  81     node.right = replacement_;                                          \
  82                                                                         \
  83     std::string name = nextId();                                        \
  84                                                                         \
  85     TmpResultExp * tmpRes = new TmpResultExp();                         \
  86     tmpRes->name = name;                                                \
  87     tmpRes->type = node.type;                                           \
  88     assert(tmpRes->type);                                               \
  89     replacement_ = tmpRes;                                              \
  90                                                                         \
  91     AssignExp * assign = new AssignExp();                               \
  92     assign->dest = new Symbol();                                        \
  93     assign->dest->name = name;                                          \
  94     assign->dest->type = node.type;                                     \
  95     assign->value = &node;                                              \
  96     assign->type = node.type;                                           \
  97     simplifications_.push_back(assign);                                 \
  98   }
  99
 100   SIMPLIFY_BINARY_EXP(EqExp)
 101   SIMPLIFY_BINARY_EXP(NeqExp)
 102   SIMPLIFY_BINARY_EXP(LtExp)
 103   SIMPLIFY_BINARY_EXP(LtEqExp)
 104   SIMPLIFY_BINARY_EXP(GtExp)
 105   SIMPLIFY_BINARY_EXP(GtEqExp)
 106
 107   SIMPLIFY_BINARY_EXP(AddExp)
 108   SIMPLIFY_BINARY_EXP(SubExp)
 109   SIMPLIFY_BINARY_EXP(MulExp)
 110   SIMPLIFY_BINARY_EXP(DivExp)
 111   SIMPLIFY_BINARY_EXP(ModExp)
 112
 113   SIMPLIFY_BINARY_EXP(AndExp)
 114   SIMPLIFY_BINARY_EXP(OrExp)
 115   SIMPLIFY_BINARY_EXP(XorExp)
 116
 117   SIMPLIFY_BINARY_EXP(AndAndExp)
 118   SIMPLIFY_BINARY_EXP(OrOrExp)
 119
 120   SIMPLIFY_BINARY_EXP(ShlExp)
 121   SIMPLIFY_BINARY_EXP(AShrExp)
 122   SIMPLIFY_BINARY_EXP(LShrExp)
 123
 124   void
 125   SimplifyVisitor::visit(AssignExp & node)
 126   {
 127     assert(node.value);
 128     node.value->accept(*this);
 129     node.value = replacement_;
 130
 131     StoreVar * sv = new StoreVar();
 132     sv->name = node.dest->name;
 133     sv->value = replacement_;
 134     simplifications_.push_back(sv);
 135
 136     delete &node;
 137   }
 138
 139   void
 140   SimplifyVisitor::visit(NumberExp & node)
 141   {
 142     replacement_ = &node;
 143   }
 144
 145   void
 146   SimplifyVisitor::visit(IdExp & node)
 147   {
 148     LoadVar * lv = new LoadVar();
 149     lv->name = node.name;
 150     lv->to = nextId();
 151     lv->type = node.type;
 152     simplifications_.push_back(lv);
 153
 154     TmpResultExp * tre = new TmpResultExp();
 155     tre->name = lv->to;
 156     tre->type = node.type;
 157     replacement_ = tre;
 158     delete &node;
 159   }
 160
 161   /**
 162    * @internal
 163    * develop the cast, and simplify it
 164    */
 165   void
 166   SimplifyVisitor::visit(CastExp & node)
 167   {
 168     node.exp->accept(*this);
 169     node.exp = replacement_;
 170
 171     if (!TypeCheckerVisitor::findCast(node.type, node.exp->type))
 172       return;
 173
 174     AssignExp * assign = new AssignExp();
 175     assign->value = &node;
 176     assign->dest = new Symbol();
 177     assign->dest->name = nextId();
 178     assign->dest->type = node.type;
 179     assign->type = node.type;
 180     simplifications_.push_back(assign);
 181
 182     TmpResultExp * tre = new TmpResultExp();
 183     tre->name = assign->dest->name;
 184     tre->type = node.type;
 185     replacement_ = tre;
 186   }
 187
 188   void
 189   SimplifyVisitor::visit(Label & node)
 190   {
 191     simplifications_.push_back(&node);
 192   }
 193
 194   void
 195   SimplifyVisitor::visit(Goto & node)
 196   {
 197     simplifications_.push_back(&node);
 198   }
 199
 200   void
 201   SimplifyVisitor::visit(If & node)
 202   {
 203     assert(node.cond);
 204     assert(node.ifTrue);
 205
 206     node.cond->accept(*this);
 207     assert(replacement_);
 208     node.cond = replacement_;
 209
 210     simplifications_.push_back(&node);
 211
 212 #define EXPAND_BLOCK(True)                                              \
 213     do {                                                                \
 214       Label * True##Label = new Label;                                  \
 215       True##Label->name = std::string(#True "Label_") + nextId();       \
 216       simplifications_.push_back(True##Label);                          \
 217                                                                         \
 218       node.if##True->accept(*this);                                     \
 219       if (node.if##True->nodeType == Block::nodeTypeId()) {             \
 220         BOOST_FOREACH(Node * elt,                                       \
 221                       *reinterpret_cast<Block *>(node.if##True)->statements) \
 222           simplifications_.push_back(elt);                              \
 223       }                                                                 \
 224       node.if##True = True##Label;                                      \
 225     } while (0)
 226
 227     EXPAND_BLOCK(True);
 228
 229     node.endLabel = new Label;
 230     node.endLabel->name = std::string("EndLabel_") + nextId();
 231     Goto * gotoNode = new Goto;
 232     gotoNode->label = node.endLabel->name;
 233     simplifications_.push_back(gotoNode);
 234
 235     EXPAND_BLOCK(False);
 236     simplifications_.push_back(node.endLabel);
 237   }
 238 }