src/ozulis/visitors/simplify.cc

   1 #include <sstream>
   2 #include <boost/foreach.hpp>
   3
   4 #include <ozulis/core/assert.hh>
   5 #include <ozulis/ast/cast-tables.hh>
   6 #include <ozulis/ast/ast-cast.hh>
   7 #include <ozulis/ast/node-factory.hh>
   8 #include <ozulis/ast/scope.hh>
   9 #include <ozulis/visitors/type-checker.hh>
  10 #include <ozulis/visitors/simplify.hh>
  11 #include <ozulis/visitors/browser.hh>
  12
  13 namespace ozulis
  14 {
  15   namespace visitors
  16   {
  17     /// @defgroup s
  18     /**
  19      * @class Simplify
  20      * @ingroup Visitors
  21      *
  22      * <b>Algorithm</b><br>
  23      * - on Block
  24      *  - for every instruction
  25      *   - split the instruction in 3 address instruction
  26      */
  27
  28     Simplify::Simplify()
  29       : Visitor<Simplify>(),
  30         simplifications(0),
  31         replacement(0),
  32         scope(0),
  33         nextId_(0)
  34     {
  35     }
  36
  37     Simplify::~Simplify()
  38     {
  39     }
  40
  41     void
  42     Simplify::simplify(ast::Exp *& node)
  43     {
  44       assert(node);
  45       assert(node->type);
  46
  47       visit(*node, *this);
  48       node = replacement;
  49     }
  50
  51     std::string
  52     Simplify::nextId()
  53     {
  54       std::stringstream ss;
  55       ss << "$" << ++nextId_;
  56       return ss.str();
  57     }
  58
  59     std::string
  60     Simplify::currentId() const
  61     {
  62       std::stringstream ss;
  63       ss << "r" << nextId_;
  64       return ss.str();
  65     }
  66
  67     void
  68     Simplify::makeTmpResult(ast::Exp & node)
  69     {
  70       if (node.type->nodeType == ast::VoidType::nodeTypeId())
  71       {
  72         replacement = 0;
  73         simplifications.push_back(&node);
  74         return;
  75       }
  76
  77       ast::SymbolExp * sexp = new ast::SymbolExp();
  78       sexp->symbol = new ast::Symbol;
  79       sexp->symbol->name = nextId();
  80       sexp->symbol->type = node.type;
  81       sexp->type = node.type;
  82       ast::RegisterAddress * addr = new ast::RegisterAddress;
  83       addr->address = scope->prefix + sexp->symbol->name;
  84       sexp->symbol->address = addr;
  85
  86       ast::AssignExp * assign = new ast::AssignExp();
  87       assign->value = &node;
  88       assign->dest = sexp;
  89       assign->type = node.type;
  90       simplifications.push_back(assign);
  91
  92       replacement = sexp;
  93     }
  94
  95     static void visitBlock(ast::Node & node_, Simplify & ctx)
  96     {
  97       ast::Block & block = reinterpret_cast<ast::Block &> (node_);
  98       ctx.scope = block.scope;
  99       std::vector<ast::Node *> backup = ctx.simplifications;
 100       ctx.simplifications.clear();
 101
 102       BOOST_FOREACH (ast::Node * node, (*block.statements))
 103       {
 104         assert(node);
 105         Simplify::visit(*node, ctx);
 106       }
 107
 108       *block.statements = ctx.simplifications;
 109       ctx.simplifications = backup;
 110     }
 111
 112     static void visitVoidExp(ast::Node & node_, Simplify & ctx)
 113     {
 114       ast::VoidExp & node = reinterpret_cast<ast::VoidExp &> (node_);
 115       ctx.replacement = &node;
 116     }
 117
 118 #define SIMPLIFY_UNARY_EXP(Type)                                        \
 119     /**                                                                 \
 120      * @internal                                                        \
 121      * - Simplify childs                                                \
 122      * - Create a new id.                                               \
 123      * - Create a new assign exp to id.                                 \
 124      * - Create a IdExp and tell replace the parent's child with it.    \
 125      */                                                                 \
 126     static void visit##Type(ast::Node & node_, Simplify & ctx)          \
 127     {                                                                   \
 128       ast::Type & node = reinterpret_cast<ast::Type &> (node_);         \
 129       assert(node.exp);                                                 \
 130       ctx.simplify(node.exp);                                           \
 131                                                                         \
 132       ctx.makeTmpResult(node);                                          \
 133     }
 134
 135     SIMPLIFY_UNARY_EXP(NotExp)
 136     SIMPLIFY_UNARY_EXP(BangExp)
 137     SIMPLIFY_UNARY_EXP(NegExp)
 138
 139 #define SIMPLIFY_BINARY_EXP(Type)                                       \
 140     /**                                                                 \
 141      * @internal                                                        \
 142      * - Simplify childs                                                \
 143      * - Create a new id.                                               \
 144      * - Create a new assign exp to id.                                 \
 145      * - Create a IdExp and tell replace the parent's child with it.    \
 146      */                                                                 \
 147     static void visit##Type(ast::Node & node_, Simplify & ctx)          \
 148     {                                                                   \
 149       ast::Type & node = reinterpret_cast<ast::Type &> (node_);         \
 150       ctx.simplify(node.left);                                          \
 151       ctx.simplify(node.right);                                         \
 152                                                                         \
 153       ctx.makeTmpResult(node);                                          \
 154     }
 155
 156     SIMPLIFY_BINARY_EXP(EqExp)
 157     SIMPLIFY_BINARY_EXP(NeqExp)
 158     SIMPLIFY_BINARY_EXP(LtExp)
 159     SIMPLIFY_BINARY_EXP(LtEqExp)
 160     SIMPLIFY_BINARY_EXP(GtExp)
 161     SIMPLIFY_BINARY_EXP(GtEqExp)
 162
 163     SIMPLIFY_BINARY_EXP(AddExp)
 164     SIMPLIFY_BINARY_EXP(SubExp)
 165     SIMPLIFY_BINARY_EXP(MulExp)
 166     SIMPLIFY_BINARY_EXP(DivExp)
 167     SIMPLIFY_BINARY_EXP(ModExp)
 168
 169     SIMPLIFY_BINARY_EXP(AndExp)
 170     SIMPLIFY_BINARY_EXP(OrExp)
 171     SIMPLIFY_BINARY_EXP(XorExp)
 172
 173     SIMPLIFY_BINARY_EXP(AndAndExp)
 174     SIMPLIFY_BINARY_EXP(OrOrExp)
 175
 176     SIMPLIFY_BINARY_EXP(ShlExp)
 177     SIMPLIFY_BINARY_EXP(AShrExp)
 178     SIMPLIFY_BINARY_EXP(LShrExp)
 179
 180     /// @todo redo it :)
 181     static void visitAssignExp(ast::Node & node_, Simplify & ctx)
 182     {
 183       ast::AssignExp & node = reinterpret_cast<ast::AssignExp &> (node_);
 184       assert(node.value);
 185       assert(node.type);
 186       assert(node.dest);
 187
 188       ctx.simplifyLValue(node.dest);
 189       ctx.simplify(node.value);
 190
 191       ast::SymbolExp * dest = ast::ast_cast<ast::SymbolExp *> (node.dest);
 192       ast::StoreVar * sv = new ast::StoreVar();
 193       sv->name = dest->symbol->name;
 194       sv->value = ctx.replacement; // node.value
 195       ctx.simplifications.push_back(sv);
 196       return;
 197     }
 198
 199     static void visitNumberExp(ast::Node & node_, Simplify & ctx)
 200     {
 201       ast::NumberExp & node = reinterpret_cast<ast::NumberExp &> (node_);
 202       ctx.replacement = &node;
 203     }
 204
 205 #define BAD_NODE(Type)                                  \
 206     static void visit##Type(ast::Node & /*node_*/,      \
 207                             Simplify & /*ctx*/)         \
 208     {                                                   \
 209       assert_msg(false, "should never get here.");      \
 210     }
 211
 212     BAD_NODE(Exp)
 213     BAD_NODE(StringExp)
 214     BAD_NODE(IdExp)
 215
 216     /** @internal load a symbol if it's in memory */
 217     static void visitSymbolExp(ast::Node & node_, Simplify & ctx)
 218     {
 219       ast::SymbolExp & node = reinterpret_cast<ast::SymbolExp &> (node_);
 220       if (node.symbol->address->nodeType == ast::MemoryAddress::nodeTypeId())
 221       {
 222         ast::SymbolExp * sexp = new ast::SymbolExp;
 223         sexp->symbol          = new ast::Symbol;
 224         sexp->symbol->name    = node.symbol->name + "_" + ctx.nextId();;
 225         sexp->symbol->type    = unreferencedType(node.type);
 226         sexp->symbol->address = new ast::RegisterAddress;
 227         sexp->type            = sexp->symbol->type;
 228         ctx.replacement       = sexp;
 229
 230         ast::LoadVar * lv = new ast::LoadVar;
 231         lv->to            = sexp->symbol->name;
 232         lv->from          = &node;
 233         ctx.simplifications.push_back(lv);
 234       }
 235       else
 236         ctx.replacement = &node;
 237     }
 238
 239     static void visitAtExp(ast::Node & node_, Simplify & ctx)
 240     {
 241       ast::AtExp & node = reinterpret_cast<ast::AtExp &> (node_);
 242       ctx.replacement = &node;
 243       ctx.simplifyLValue(ctx.replacement);
 244     }
 245
 246     static void visitDereferenceExp(ast::Node & node_, Simplify & ctx)
 247     {
 248       ast::DereferenceExp & node = reinterpret_cast<ast::DereferenceExp &> (node_);
 249       ctx.simplify(node.exp);
 250
 251       ast::LoadVar * lv = new ast::LoadVar;
 252       lv->to            = ctx.nextId();
 253       lv->from          = node.exp;
 254       ctx.simplifications.push_back(lv);
 255
 256       ast::SymbolExp * id     = new ast::SymbolExp;
 257       id->symbol          = new ast::Symbol;
 258       id->symbol->name    = lv->to;
 259       id->symbol->type    = node.type;
 260       id->symbol->address = new ast::RegisterAddress;
 261       id->type            = node.type;
 262       ctx.replacement     = id;
 263     }
 264
 265     /** @internal just do (node.exp + node.index)* */
 266     static void visitDereferenceByIndexExp(ast::Node & node_, Simplify & ctx)
 267     {
 268       ast::DereferenceByIndexExp & node =
 269           reinterpret_cast<ast::DereferenceByIndexExp &> (node_);
 270       ast::PointerArithExp * add = new ast::PointerArithExp;
 271       add->pointer               = node.exp;
 272       add->offset                = node.index;
 273
 274       ast::DereferenceExp * deref = new ast::DereferenceExp;
 275       deref->exp                  = add;
 276       ast::Exp * tmp              = deref;
 277
 278       TypeChecker v;
 279       v.scope = ctx.scope;
 280       v.check(tmp);
 281       ctx.simplify(tmp);
 282       ctx.replacement = tmp;
 283     }
 284
 285     static void visitCallExp(ast::Node & node_, Simplify & ctx)
 286     {
 287       ast::CallExp & node = reinterpret_cast<ast::CallExp &> (node_);
 288       BOOST_FOREACH (ast::Exp *& exp, (*node.args))
 289         ctx.simplify(exp);
 290
 291       ctx.makeTmpResult(node);
 292     }
 293
 294     /** @internal develop the cast, and simplify it */
 295     static void visitCastExp(ast::Node & node_, Simplify & ctx)
 296     {
 297       ast::CastExp & node = reinterpret_cast<ast::CastExp &> (node_);
 298       ctx.simplify(node.exp);
 299
 300       assert(node.exp);
 301       // The cast exp is dummy, remove it
 302       if (!castToBestType(node.type, node.exp->type))
 303         return;
 304
 305       ctx.makeTmpResult(node);
 306     }
 307
 308     static void visitLabel(ast::Node & node_, Simplify & ctx)
 309     {
 310       ast::Label & node = reinterpret_cast<ast::Label &> (node_);
 311       ctx.simplifications.push_back(&node);
 312     }
 313
 314     static void visitGoto(ast::Node & node_, Simplify & ctx)
 315     {
 316       ast::Goto & node = reinterpret_cast<ast::Goto &> (node_);
 317       ctx.simplifications.push_back(&node);
 318     }
 319
 320     static void visitReturn(ast::Node & node_, Simplify & ctx)
 321     {
 322       ast::Return & node = reinterpret_cast<ast::Return &> (node_);
 323       ctx.simplify(node.exp);
 324       ctx.simplifications.push_back(&node);
 325     }
 326
 327     /** @internal
 328      * @code
 329      *   if (cond)
 330      * trueLabel:
 331      *   { ... }
 332      *   goto endLabel;
 333      * falseLabel:
 334      *   { ... }
 335      * endLabel:
 336      * @code
 337      */
 338     static void visitIf(ast::Node & node_, Simplify & ctx)
 339     {
 340       ast::If & node = reinterpret_cast<ast::If &> (node_);
 341       ctx.simplify(node.branch->cond);
 342       ctx.simplifications.push_back(node.branch);
 343
 344       node.branch->trueLabel = new ast::Label;
 345       node.branch->trueLabel->name = std::string("if_true_") + ctx.nextId();
 346       node.branch->falseLabel = new ast::Label;
 347       node.branch->falseLabel->name = std::string("if_false_") + ctx.nextId();
 348       node.endLabel = new ast::Label;
 349       node.endLabel->name = std::string("if_end_") + ctx.nextId();
 350
 351       ctx.simplifications.push_back(node.branch->trueLabel);
 352       Simplify::visit(*node.trueBlock, ctx);
 353       ast::Goto * gotoNode = new ast::Goto;
 354       gotoNode->label = node.endLabel->name;
 355
 356       ctx.simplifications.push_back(node.branch->falseLabel);
 357       Simplify::visit(*node.falseBlock, ctx);
 358       ctx.simplifications.push_back(node.endLabel);
 359     }
 360
 361     /** @internal
 362      * @code
 363      * beginLabel:
 364      *   while (cond)
 365      * trueLabel:
 366      *   { ... }
 367      *   goto beginLabel;
 368      * falseLabel:
 369      * @code
 370      */
 371     static void visitWhile(ast::Node & node_, Simplify & ctx)
 372     {
 373       ast::While & node = reinterpret_cast<ast::While &> (node_);
 374       assert(node.block);
 375       assert(node.branch->cond);
 376
 377       node.beginLabel = new ast::Label;
 378       node.beginLabel->name = std::string("do_while_1_") + ctx.nextId();
 379       node.branch->trueLabel = new ast::Label;
 380       node.branch->trueLabel->name = std::string("do_while_2_") + ctx.nextId();
 381       node.branch->falseLabel = new ast::Label;
 382       node.branch->falseLabel->name = std::string("do_while_3_") + ctx.nextId();
 383
 384       ctx.simplifications.push_back(node.beginLabel);
 385       ctx.simplify(node.branch->cond);
 386       ctx.simplifications.push_back(node.branch);
 387       ctx.simplifications.push_back(node.branch->trueLabel);
 388       Simplify::visit(*node.block, ctx);
 389       node.block = 0;
 390
 391       ast::Goto * gt = new ast::Goto;
 392       gt->label = node.beginLabel->name;
 393       ctx.simplifications.push_back(gt);
 394       ctx.simplifications.push_back(node.branch->falseLabel);
 395     }
 396
 397     /** @internal
 398      * @code
 399      * trueLabel:
 400      *   { ... }
 401      *   while (cond)
 402      * falseLabel:
 403      * @code
 404      */
 405     static void visitDoWhile(ast::Node & node_, Simplify & ctx)
 406     {
 407       ast::DoWhile & node = reinterpret_cast<ast::DoWhile &> (node_);
 408       assert(node.block);
 409       assert(node.branch->cond);
 410
 411       node.branch->trueLabel = new ast::Label;
 412       node.branch->trueLabel->name = std::string("do_while_1_") + ctx.nextId();
 413       node.branch->falseLabel = new ast::Label;
 414       node.branch->falseLabel->name = std::string("do_while_2_") + ctx.nextId();
 415       ctx.simplifications.push_back(node.branch->trueLabel);
 416
 417       Simplify::visit(*node.block, ctx);
 418       node.block = 0;
 419       ctx.simplify(node.branch->cond);
 420
 421       ctx.replacement = 0;
 422       ctx.simplifications.push_back(node.branch);
 423       ctx.simplifications.push_back(node.branch->falseLabel);
 424     }
 425
 426     void
 427     Simplify::simplifyLValue(ast::Exp *& node)
 428     {
 429       if (node->nodeType == ast::SymbolExp::nodeTypeId())
 430         return;
 431       if (node->nodeType == ast::DereferenceExp::nodeTypeId())
 432       {
 433         ast::DereferenceExp * deref = ast::ast_cast<ast::DereferenceExp *>(node);
 434         simplify(deref->exp);
 435
 436         assert(deref->exp->nodeType == ast::SymbolExp::nodeTypeId());
 437         node = deref->exp;
 438         return;
 439       }
 440     }
 441
 442     void
 443     Simplify::initBase()
 444     {
 445 #define REGISTER_METHOD(Class)                                  \
 446       registerMethod(ast::Class::nodeTypeId(), visit##Class)
 447
 448       REGISTER_METHOD(Exp);
 449       REGISTER_METHOD(VoidExp);
 450       REGISTER_METHOD(AssignExp);
 451
 452       REGISTER_METHOD(EqExp);
 453       REGISTER_METHOD(NeqExp);
 454       REGISTER_METHOD(LtExp);
 455       REGISTER_METHOD(LtEqExp);
 456       REGISTER_METHOD(GtExp);
 457       REGISTER_METHOD(GtEqExp);
 458       REGISTER_METHOD(AddExp);
 459       REGISTER_METHOD(SubExp);
 460       REGISTER_METHOD(MulExp);
 461       REGISTER_METHOD(DivExp);
 462       REGISTER_METHOD(ModExp);
 463
 464       REGISTER_METHOD(AndExp);
 465       REGISTER_METHOD(OrExp);
 466       REGISTER_METHOD(XorExp);
 467
 468       REGISTER_METHOD(AndAndExp);
 469       REGISTER_METHOD(OrOrExp);
 470
 471       REGISTER_METHOD(ShlExp);
 472       REGISTER_METHOD(AShrExp);
 473       REGISTER_METHOD(LShrExp);
 474
 475       REGISTER_METHOD(NotExp);
 476       REGISTER_METHOD(NegExp);
 477       REGISTER_METHOD(BangExp);
 478
 479       REGISTER_METHOD(NumberExp);
 480       REGISTER_METHOD(StringExp);
 481       REGISTER_METHOD(IdExp);
 482       REGISTER_METHOD(SymbolExp);
 483       REGISTER_METHOD(AtExp);
 484       REGISTER_METHOD(DereferenceExp);
 485       REGISTER_METHOD(DereferenceByIndexExp);
 486       REGISTER_METHOD(CallExp);
 487       REGISTER_METHOD(Block);
 488
 489       REGISTER_METHOD(CastExp);
 490
 491       REGISTER_METHOD(Label);
 492       REGISTER_METHOD(Goto);
 493       REGISTER_METHOD(Return);
 494       REGISTER_METHOD(If);
 495       REGISTER_METHOD(While);
 496       REGISTER_METHOD(DoWhile);
 497
 498       completeWith<Browser<Simplify> >();
 499     }
 500   }
 501 }