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/clone.hh>
   8 #include <ozulis/ast/node-factory.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         nextId_(0),
  33         scope(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::IdExp * id = new ast::IdExp();
  78       id->symbol = new ast::Symbol;
  79       id->symbol->name = nextId();
  80       id->symbol->type = node.type;
  81       id->symbol->address = new ast::RegisterAddress;
  82       id->type = node.type;
  83
  84       ast::AssignExp * assign = new ast::AssignExp();
  85       assign->value = &node;
  86       assign->dest = id;
  87       assign->type = node.type;
  88       simplifications.push_back(assign);
  89
  90       replacement = id;
  91     }
  92
  93     static void visitBlock(ast::Node & node_, Simplify & ctx)
  94     {
  95       ast::Block & block = reinterpret_cast<ast::Block &> (node_);
  96       ctx.scope = block.scope;
  97       std::vector<ast::Node *> backup = ctx.simplifications;
  98       ctx.simplifications.clear();
  99
 100       BOOST_FOREACH (ast::Node * node, (*block.statements))
 101       {
 102         assert(node);
 103         Simplify::visit(*node, ctx);
 104       }
 105
 106       *block.statements = ctx.simplifications;
 107       ctx.simplifications = backup;
 108     }
 109
 110     static void visitExp(ast::Node & /*node_*/, Simplify & /*ctx*/)
 111     {
 112       assert_msg(false, "unimplemented visit method");
 113     }
 114
 115     static void visitVoidExp(ast::Node & node_, Simplify & ctx)
 116     {
 117       ast::VoidExp & node = reinterpret_cast<ast::VoidExp &> (node_);
 118       ctx.replacement = &node;
 119     }
 120
 121 #define SIMPLIFY_UNARY_EXP(Type)                                        \
 122     /**                                                                 \
 123      * @internal                                                        \
 124      * - Simplify childs                                                \
 125      * - Create a new id.                                               \
 126      * - Create a new assign exp to id.                                 \
 127      * - Create a IdExp and tell replace the parent's child with it.    \
 128      */                                                                 \
 129     static void visit##Type(ast::Node & node_, Simplify & ctx)          \
 130     {                                                                   \
 131       ast::Type & node = reinterpret_cast<ast::Type &> (node_);         \
 132       assert(node.exp);                                                 \
 133       ctx.simplify(node.exp);                                           \
 134                                                                         \
 135       ctx.makeTmpResult(node);                                          \
 136     }
 137
 138     SIMPLIFY_UNARY_EXP(NotExp)
 139     SIMPLIFY_UNARY_EXP(BangExp)
 140     SIMPLIFY_UNARY_EXP(NegExp)
 141
 142 #define SIMPLIFY_BINARY_EXP(Type)                                       \
 143     /**                                                                 \
 144      * @internal                                                        \
 145      * - Simplify childs                                                \
 146      * - Create a new id.                                               \
 147      * - Create a new assign exp to id.                                 \
 148      * - Create a IdExp and tell replace the parent's child with it.    \
 149      */                                                                 \
 150     static void visit##Type(ast::Node & node_, Simplify & ctx)          \
 151     {                                                                   \
 152       ast::Type & node = reinterpret_cast<ast::Type &> (node_);         \
 153       ctx.simplify(node.left);                                          \
 154       ctx.simplify(node.right);                                         \
 155                                                                         \
 156       ctx.makeTmpResult(node);                                          \
 157     }
 158
 159     SIMPLIFY_BINARY_EXP(EqExp)
 160     SIMPLIFY_BINARY_EXP(NeqExp)
 161     SIMPLIFY_BINARY_EXP(LtExp)
 162     SIMPLIFY_BINARY_EXP(LtEqExp)
 163     SIMPLIFY_BINARY_EXP(GtExp)
 164     SIMPLIFY_BINARY_EXP(GtEqExp)
 165
 166     SIMPLIFY_BINARY_EXP(AddExp)
 167     SIMPLIFY_BINARY_EXP(SubExp)
 168     SIMPLIFY_BINARY_EXP(MulExp)
 169     SIMPLIFY_BINARY_EXP(DivExp)
 170     SIMPLIFY_BINARY_EXP(ModExp)
 171
 172     SIMPLIFY_BINARY_EXP(AndExp)
 173     SIMPLIFY_BINARY_EXP(OrExp)
 174     SIMPLIFY_BINARY_EXP(XorExp)
 175
 176     SIMPLIFY_BINARY_EXP(AndAndExp)
 177     SIMPLIFY_BINARY_EXP(OrOrExp)
 178
 179     SIMPLIFY_BINARY_EXP(ShlExp)
 180     SIMPLIFY_BINARY_EXP(AShrExp)
 181     SIMPLIFY_BINARY_EXP(LShrExp)
 182
 183     /// @todo redo it :)
 184     static void visitAssignExp(ast::Node & node_, Simplify & ctx)
 185     {
 186       ast::AssignExp & node = reinterpret_cast<ast::AssignExp &> (node_);
 187       assert(node.value);
 188       assert(node.type);
 189       assert(node.dest);
 190
 191       ctx.simplifyLValue(node.dest);
 192       ctx.simplify(node.value);
 193
 194       ast::IdExp * dest = ast::ast_cast<ast::IdExp *> (node.dest);
 195       ast::StoreVar * sv = new ast::StoreVar();
 196       sv->name = dest->symbol->name;
 197       sv->value = ctx.replacement; // node.value
 198       ctx.simplifications.push_back(sv);
 199       return;
 200     }
 201
 202     static void visitNumberExp(ast::Node & node_, Simplify & ctx)
 203     {
 204       ast::NumberExp & node = reinterpret_cast<ast::NumberExp &> (node_);
 205       ctx.replacement = &node;
 206     }
 207
 208     static void visitIdExp(ast::Node & node_, Simplify & ctx)
 209     {
 210       ast::IdExp & node = reinterpret_cast<ast::IdExp &> (node_);
 211       if (node.symbol->address->nodeType == ast::MemoryAddress::nodeTypeId())
 212       {
 213         ast::IdExp * id     = new ast::IdExp;
 214         id->symbol          = new ast::Symbol;
 215         id->symbol->name    = node.symbol->name + "_" + ctx.nextId();;
 216         id->symbol->type    = unreferencedType(node.type);
 217         id->symbol->address = new ast::RegisterAddress;
 218         id->type            = id->symbol->type;
 219         ctx.replacement     = id;
 220
 221         ast::LoadVar * lv = new ast::LoadVar;
 222         lv->to            = id->symbol->name;
 223         lv->from          = &node;
 224         ctx.simplifications.push_back(lv);
 225       }
 226       else
 227         ctx.replacement = &node;
 228     }
 229
 230     static void visitAtExp(ast::Node & node_, Simplify & ctx)
 231     {
 232       ast::AtExp & node = reinterpret_cast<ast::AtExp &> (node_);
 233       ctx.replacement = &node;
 234       ctx.simplifyLValue(ctx.replacement);
 235     }
 236
 237     static void visitDereferenceExp(ast::Node & node_, Simplify & ctx)
 238     {
 239       ast::DereferenceExp & node = reinterpret_cast<ast::DereferenceExp &> (node_);
 240       ctx.simplify(node.exp);
 241
 242       ast::LoadVar * lv = new ast::LoadVar;
 243       lv->to            = ctx.nextId();
 244       lv->from          = node.exp;
 245       ctx.simplifications.push_back(lv);
 246
 247       ast::IdExp * id     = new ast::IdExp;
 248       id->symbol          = new ast::Symbol;
 249       id->symbol->name    = lv->to;
 250       id->symbol->type    = node.type;
 251       id->symbol->address = new ast::RegisterAddress;
 252       id->type            = node.type;
 253       ctx.replacement     = id;
 254     }
 255
 256     /**
 257      * @internal just do (node.exp + node.index)*
 258      */
 259     static void visitDereferenceByIndexExp(ast::Node & node_, Simplify & ctx)
 260     {
 261       ast::DereferenceByIndexExp & node = reinterpret_cast<ast::DereferenceByIndexExp &> (node_);
 262       ast::AddExp * add = new ast::AddExp;
 263       add->left = node.exp;
 264       add->right = node.index;
 265
 266       ast::DereferenceExp * deref = new ast::DereferenceExp;
 267       deref->exp = add;
 268       ast::Exp * tmp = deref;
 269
 270       TypeChecker v;
 271       v.setScope(ctx.scope);
 272       v.check(tmp);
 273       ctx.simplify(tmp);
 274       ctx.replacement = tmp;
 275     }
 276
 277     static void visitCallExp(ast::Node & node_, Simplify & ctx)
 278     {
 279       ast::CallExp & node = reinterpret_cast<ast::CallExp &> (node_);
 280       BOOST_FOREACH (ast::Exp *& exp, (*node.args))
 281         ctx.simplify(exp);
 282
 283       ctx.makeTmpResult(node);
 284     }
 285
 286     /**
 287      * @internal
 288      * develop the cast, and simplify it
 289      */
 290     static void visitCastExp(ast::Node & node_, Simplify & ctx)
 291     {
 292       ast::CastExp & node = reinterpret_cast<ast::CastExp &> (node_);
 293       ctx.simplify(node.exp);
 294
 295       if (!castToBestType(node.type, node.exp->type))
 296         return;
 297
 298       ctx.makeTmpResult(node);
 299     }
 300
 301     static void visitLabel(ast::Node & node_, Simplify & ctx)
 302     {
 303       ast::Label & node = reinterpret_cast<ast::Label &> (node_);
 304       ctx.simplifications.push_back(&node);
 305     }
 306
 307     static void visitGoto(ast::Node & node_, Simplify & ctx)
 308     {
 309       ast::Goto & node = reinterpret_cast<ast::Goto &> (node_);
 310       ctx.simplifications.push_back(&node);
 311     }
 312
 313     static void visitReturn(ast::Node & node_, Simplify & ctx)
 314     {
 315       ast::Return & node = reinterpret_cast<ast::Return &> (node_);
 316       ctx.simplify(node.exp);
 317       ctx.simplifications.push_back(&node);
 318     }
 319
 320     static void visitIf(ast::Node & node_, Simplify & ctx)
 321     {
 322       ast::If & node = reinterpret_cast<ast::If &> (node_);
 323       ctx.simplify(node.branch->cond);
 324       ctx.simplifications.push_back(node.branch);
 325
 326       node.branch->trueLabel = new ast::Label;
 327       node.branch->trueLabel->name = std::string("if_true_") + ctx.nextId();
 328       node.branch->falseLabel = new ast::Label;
 329       node.branch->falseLabel->name = std::string("if_false_") + ctx.nextId();
 330       node.endLabel = new ast::Label;
 331       node.endLabel->name = std::string("if_end_") + ctx.nextId();
 332
 333       ctx.simplifications.push_back(node.branch->trueLabel);
 334       Simplify::visit(*node.trueBlock, ctx);
 335       ast::Goto * gotoNode = new ast::Goto;
 336       gotoNode->label = node.endLabel->name;
 337
 338       ctx.simplifications.push_back(node.branch->falseLabel);
 339       Simplify::visit(*node.falseBlock, ctx);
 340       ctx.simplifications.push_back(node.endLabel);
 341     }
 342
 343     static void visitWhile(ast::Node & node_, Simplify & ctx)
 344     {
 345       ast::While & node = reinterpret_cast<ast::While &> (node_);
 346       assert(node.block);
 347       assert(node.branch->cond);
 348
 349       node.beginLabel = new ast::Label;
 350       node.beginLabel->name = std::string("do_while_1_") + ctx.nextId();
 351       node.branch->trueLabel = new ast::Label;
 352       node.branch->trueLabel->name = std::string("do_while_2_") + ctx.nextId();
 353       node.branch->falseLabel = new ast::Label;
 354       node.branch->falseLabel->name = std::string("do_while_3_") + ctx.nextId();
 355
 356       ctx.simplifications.push_back(node.beginLabel);
 357       ctx.simplify(node.branch->cond);
 358       ctx.simplifications.push_back(node.branch);
 359       ctx.simplifications.push_back(node.branch->trueLabel);
 360       Simplify::visit(*node.block, ctx);
 361       node.block = 0;
 362
 363       ast::Goto * gt = new ast::Goto;
 364       gt->label = node.beginLabel->name;
 365       ctx.simplifications.push_back(gt);
 366       ctx.simplifications.push_back(node.branch->falseLabel);
 367     }
 368
 369     static void visitDoWhile(ast::Node & node_, Simplify & ctx)
 370     {
 371       ast::DoWhile & node = reinterpret_cast<ast::DoWhile &> (node_);
 372       assert(node.block);
 373       assert(node.branch->cond);
 374
 375       node.branch->trueLabel = new ast::Label;
 376       node.branch->trueLabel->name = std::string("do_while_1_") + ctx.nextId();
 377       node.branch->falseLabel = new ast::Label;
 378       node.branch->falseLabel->name = std::string("do_while_2_") + ctx.nextId();
 379       ctx.simplifications.push_back(node.branch->trueLabel);
 380
 381       Simplify::visit(*node.block, ctx);
 382       node.block = 0;
 383       ctx.simplify(node.branch->cond);
 384
 385       ctx.replacement = 0;
 386       ctx.simplifications.push_back(node.branch);
 387       ctx.simplifications.push_back(node.branch->falseLabel);
 388     }
 389
 390     void
 391     Simplify::simplifyLValue(ast::Exp *& node)
 392     {
 393       if (node->nodeType == ast::IdExp::nodeTypeId())
 394         return;
 395       if (node->nodeType == ast::DereferenceExp::nodeTypeId())
 396       {
 397         ast::DereferenceExp * deref = ast::ast_cast<ast::DereferenceExp *>(node);
 398         simplify(deref->exp);
 399
 400         assert(deref->exp->nodeType == ast::IdExp::nodeTypeId());
 401         node = deref->exp;
 402         return;
 403       }
 404     }
 405
 406     void
 407     Simplify::initBase()
 408     {
 409 #define REGISTER_METHOD(Class)                                  \
 410       registerMethod(ast::Class::nodeTypeId(), visit##Class)
 411
 412       REGISTER_METHOD(Exp);
 413       REGISTER_METHOD(VoidExp);
 414       REGISTER_METHOD(AssignExp);
 415
 416       REGISTER_METHOD(EqExp);
 417       REGISTER_METHOD(NeqExp);
 418       REGISTER_METHOD(LtExp);
 419       REGISTER_METHOD(LtEqExp);
 420       REGISTER_METHOD(GtExp);
 421       REGISTER_METHOD(GtEqExp);
 422       REGISTER_METHOD(AddExp);
 423       REGISTER_METHOD(SubExp);
 424       REGISTER_METHOD(MulExp);
 425       REGISTER_METHOD(DivExp);
 426       REGISTER_METHOD(ModExp);
 427
 428       REGISTER_METHOD(AndExp);
 429       REGISTER_METHOD(OrExp);
 430       REGISTER_METHOD(XorExp);
 431
 432       REGISTER_METHOD(AndAndExp);
 433       REGISTER_METHOD(OrOrExp);
 434
 435       REGISTER_METHOD(ShlExp);
 436       REGISTER_METHOD(AShrExp);
 437       REGISTER_METHOD(LShrExp);
 438
 439       REGISTER_METHOD(NotExp);
 440       REGISTER_METHOD(NegExp);
 441       REGISTER_METHOD(BangExp);
 442
 443       REGISTER_METHOD(NumberExp);
 444       REGISTER_METHOD(IdExp);
 445       REGISTER_METHOD(AtExp);
 446       REGISTER_METHOD(DereferenceExp);
 447       REGISTER_METHOD(DereferenceByIndexExp);
 448       REGISTER_METHOD(CallExp);
 449       REGISTER_METHOD(Block);
 450
 451       REGISTER_METHOD(CastExp);
 452
 453       REGISTER_METHOD(Label);
 454       REGISTER_METHOD(Goto);
 455       REGISTER_METHOD(Return);
 456       REGISTER_METHOD(If);
 457       REGISTER_METHOD(While);
 458       REGISTER_METHOD(DoWhile);
 459
 460       completeWith<Browser<Simplify> >();
 461     }
 462   }
 463 }