visitor.cpp

Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2004-2006, Mike Van Emmerik and Trent Waddington
00003  */
00004 /*==============================================================================
00005  * FILE:       visitor.cpp
00006  * OVERVIEW:   Provides the implementation for the various visitor and modifier classes.
00007  *============================================================================*/
00008 /*
00009  * $Revision: 1.58 $
00010  *
00011  * 18 Aug 06 - Mike: Moved DfaLocalMapper here from type/dfa.cpp
00012  * 14 Jun 04 - Mike: Created, from work started by Trent in 2003
00013  */
00014 
00015 #include "visitor.h"
00016 #include "exp.h"
00017 #include "statement.h"
00018 #include "log.h"
00019 #include "boomerang.h"      // For VERBOSE
00020 #include "proc.h"
00021 #include "signature.h"
00022 #include "prog.h"
00023 #include <sstream>
00024 
00025 
00026 // FixProcVisitor class
00027 
00028 bool FixProcVisitor::visit(Location* l, bool& override) {
00029     l->setProc(proc);       // Set the proc, but only for Locations
00030     override = false;       // Use normal accept logic
00031     return true;
00032 }
00033 
00034 // GetProcVisitor class
00035 
00036 bool GetProcVisitor::visit(Location* l, bool& override) {
00037     proc = l->getProc();
00038     override = false;
00039     return proc == NULL;        // Continue recursion only if failed so far
00040 }
00041 
00042 // SetConscripts class
00043 
00044 bool SetConscripts::visit(Const* c) {
00045     if (!bInLocalGlobal) {
00046         if (bClear)
00047             c->setConscript(0);
00048         else
00049             c->setConscript(++curConscript);
00050     }
00051     bInLocalGlobal = false;
00052     return true;       // Continue recursion
00053 }
00054 
00055 bool SetConscripts::visit(Location* l, bool& override) {
00056     OPER op = l->getOper();
00057     if (op == opLocal || op == opGlobal || op == opRegOf || op == opParam)
00058         bInLocalGlobal = true;
00059     override = false;
00060     return true;       // Continue recursion
00061 }
00062 
00063 bool SetConscripts::visit(Binary* b, bool& override) {
00064     OPER op = b->getOper();
00065     if (op == opSize)
00066         bInLocalGlobal = true;
00067     override = false;
00068     return true;       // Continue recursion
00069 }
00070 
00071 
00072 bool StmtVisitor::visit(RTL* rtl) {
00073     // Mostly, don't do anything at the RTL level
00074     return true;
00075 } 
00076 
00077 bool StmtConscriptSetter::visit(Assign* stmt) {
00078     SetConscripts sc(curConscript, bClear);
00079     stmt->getLeft()->accept(&sc);
00080     stmt->getRight()->accept(&sc);
00081     curConscript = sc.getLast();
00082     return true;
00083 }
00084 bool StmtConscriptSetter::visit(PhiAssign* stmt) {
00085     SetConscripts sc(curConscript, bClear);
00086     stmt->getLeft()->accept(&sc);
00087     curConscript = sc.getLast();
00088     return true;
00089 }
00090 bool StmtConscriptSetter::visit(ImplicitAssign* stmt) {
00091     SetConscripts sc(curConscript, bClear);
00092     stmt->getLeft()->accept(&sc);
00093     curConscript = sc.getLast();
00094     return true;
00095 }
00096 
00097 bool StmtConscriptSetter::visit(CallStatement* stmt) {
00098     SetConscripts sc(curConscript, bClear);
00099     StatementList& args = stmt->getArguments();
00100     StatementList::iterator ss;
00101     for (ss = args.begin(); ss != args.end(); ++ss)
00102         (*ss)->accept(this);
00103     curConscript = sc.getLast();
00104     return true;
00105 }
00106 
00107 bool StmtConscriptSetter::visit(CaseStatement* stmt) {
00108     SetConscripts sc(curConscript, bClear);
00109     SWITCH_INFO* si = stmt->getSwitchInfo();
00110     if (si) {
00111         si->pSwitchVar->accept(&sc);
00112         curConscript = sc.getLast();
00113     }
00114     return true;
00115 }
00116 
00117 bool StmtConscriptSetter::visit(ReturnStatement* stmt) {
00118     SetConscripts sc(curConscript, bClear);
00119     ReturnStatement::iterator rr;
00120     for (rr = stmt->begin(); rr != stmt->end(); ++rr)
00121         (*rr)->accept(this);
00122     curConscript = sc.getLast();
00123     return true;
00124 }
00125 
00126 bool StmtConscriptSetter::visit(BoolAssign* stmt) {
00127     SetConscripts sc(curConscript, bClear);
00128     stmt->getCondExpr()->accept(&sc);
00129     stmt->getLeft()->accept(&sc);
00130     curConscript = sc.getLast();
00131     return true;
00132 }
00133 
00134 bool StmtConscriptSetter::visit(BranchStatement* stmt) {
00135     SetConscripts sc(curConscript, bClear);
00136     stmt->getCondExpr()->accept(&sc);
00137     curConscript = sc.getLast();
00138     return true;
00139 }
00140 
00141 bool StmtConscriptSetter::visit(ImpRefStatement* stmt) {
00142     SetConscripts sc(curConscript, bClear);
00143     stmt->getAddressExp()->accept(&sc);
00144     curConscript = sc.getLast();
00145     return true;
00146 }
00147 
00148 void PhiStripper::visit(PhiAssign* s, bool& recur) {
00149     del = true;
00150     recur = true;
00151 }
00152 
00153 Exp* CallBypasser::postVisit(RefExp* r) {
00154     // If child was modified, simplify now
00155     Exp* ret = r;
00156     if (!(unchanged & mask)) ret = r->simplify();
00157     mask >>= 1;
00158     // Note: r (the pointer) will always == ret (also the pointer) here, so the below is safe and avoids a cast
00159     Statement* def = r->getDef();
00160     CallStatement* call = (CallStatement*)def;
00161     if (call && call->isCall()) {
00162         bool ch;
00163         ret = call->bypassRef((RefExp*)ret, ch);
00164         if (ch) {
00165             unchanged &= ~mask;
00166             mod = true;
00167             // Now have to recurse to do any further bypassing that may be required
00168             // E.g. bypass the two recursive calls in fibo?? FIXME: check!
00169             return ret->accept(new CallBypasser(enclosingStmt));
00170         }
00171     }
00172 
00173     // Else just leave as is (perhaps simplified)   
00174     return ret;
00175 }
00176 
00177 
00178 Exp* CallBypasser::postVisit(Location *e)      {
00179     // Hack to preserve a[m[x]]. Can likely go when ad hoc TA goes.
00180     bool isAddrOfMem = e->isAddrOf() && e->getSubExp1()->isMemOf();
00181     if (isAddrOfMem) return e;
00182     Exp* ret = e;
00183     if (!(unchanged & mask)) ret = e->simplify();
00184     mask >>= 1;
00185     return ret;
00186 }
00187 
00188 
00189 Exp* SimpExpModifier::postVisit(Location *e)       {
00190     Exp* ret = e;
00191     if (!(unchanged & mask)) ret = e->simplify();
00192     mask >>= 1;
00193     return ret;
00194 }
00195 Exp* SimpExpModifier::postVisit(RefExp *e)     {
00196     Exp* ret = e;
00197     if (!(unchanged & mask)) ret = e->simplify();
00198     mask >>= 1;
00199     return ret;
00200 }
00201 Exp* SimpExpModifier::postVisit(Unary *e)      {
00202     Exp* ret = e;
00203     if (!(unchanged & mask)) ret = e->simplify();
00204     mask >>= 1;
00205     return ret;
00206 }
00207 Exp* SimpExpModifier::postVisit(Binary *e)  {
00208     Exp* ret = e;
00209     if (!(unchanged & mask)) ret = e->simplifyArith()->simplify();
00210     mask >>= 1;
00211     return ret;
00212 }
00213 Exp* SimpExpModifier::postVisit(Ternary *e)  {
00214     Exp* ret = e;
00215     if (!(unchanged & mask)) ret = e->simplify();
00216     mask >>= 1;
00217     return ret;
00218 }
00219 Exp* SimpExpModifier::postVisit(TypedExp *e)      {
00220     Exp* ret = e;
00221     if (!(unchanged & mask)) ret = e->simplify();
00222     mask >>= 1;
00223     return ret;
00224 }
00225 Exp* SimpExpModifier::postVisit(FlagDef *e)  {
00226     Exp* ret = e;
00227     if (!(unchanged & mask)) ret = e->simplify();
00228     mask >>= 1;
00229     return ret;
00230 }
00231 Exp* SimpExpModifier::postVisit(Const *e)      {
00232     mask >>= 1;
00233     return e;
00234 }
00235 Exp* SimpExpModifier::postVisit(TypeVal *e)  {
00236     mask >>= 1;
00237     return e;
00238 }
00239 Exp* SimpExpModifier::postVisit(Terminal *e)      {
00240     mask >>= 1;
00241     return e;
00242 }
00243 
00244 // Add used locations finder
00245 bool UsedLocsFinder::visit(Location* e, bool& override) {
00246     if (!memOnly)
00247         used->insert(e);                // All locations visited are used
00248     if (e->isMemOf()) {
00249         // Example: m[r28{10} - 4]  we use r28{10}
00250         Exp* child = e->getSubExp1();
00251         // Care! Need to turn off the memOnly flag for work inside the m[...], otherwise everything will get ignored
00252         bool wasMemOnly = memOnly;
00253         memOnly = false;
00254         child->accept(this);
00255         memOnly = wasMemOnly;
00256         override = true;                    // Already looked inside child
00257     }
00258     else
00259         override = false;
00260     return true;                        // Continue looking for other locations
00261 }
00262 
00263 bool UsedLocsFinder::visit(Terminal* e) {
00264     if (memOnly)
00265         return true;                    // Only interested in m[...]
00266     switch (e->getOper()) {
00267         case opPC:
00268         case opFlags:
00269         case opFflags:
00270         case opDefineAll:
00271         // Fall through
00272         // The carry flag can be used in some SPARC idioms, etc
00273         case opDF: case opCF: case opZF: case opNF: case opOF:  // also these
00274             used->insert(e);
00275         default:
00276             break;
00277     }
00278     return true;        // Always continue recursion
00279 }
00280 
00281 bool UsedLocsFinder::visit(RefExp* e, bool& override) {
00282     if (memOnly) {
00283         override = false;               // Look inside the ref for m[...]
00284         return true;                    // Don't count this reference
00285     }
00286     used->insert(e);         // This location is used
00287     // However, e's subexpression is NOT used ...
00288     override = true;
00289     // ... unless that is a m[x], array[x] or .x, in which case x (not m[x]/array[x]/refd.x) is used
00290     Exp* refd = e->getSubExp1();
00291     if (refd->isMemOf()) {
00292         Exp* x = ((Location*)refd)->getSubExp1();
00293         x->accept(this);
00294     }
00295     else if (refd->isArrayIndex()) {
00296         Exp* x1 = ((Binary*)refd)->getSubExp1();
00297         x1->accept(this);
00298         Exp* x2 = ((Binary*)refd)->getSubExp2();
00299         x2->accept(this);
00300     } else if (refd->isMemberOf()) {
00301         Exp* x = ((Binary*)refd)->getSubExp1();
00302         x->accept(this);
00303     }
00304     return true;
00305 }
00306 
00307 bool UsedLocalFinder::visit(Location* e, bool& override) {
00308     override = false;
00309 #if 0
00310     char* sym = proc->lookupSym(e);
00311     if (sym)
00312         override = true;                // Don't look inside this local or parameter
00313     if (proc->findLocal(e))
00314 #else
00315     if (e->isLocal())
00316 #endif
00317         used->insert(e);                // Found a local
00318     return true;                        // Continue looking for other locations
00319 }
00320 
00321 bool UsedLocalFinder::visit(TypedExp* e, bool& override) {
00322     override = false;
00323     Type* ty = e->getType();
00324     // Assumption: (cast)exp where cast is of pointer type means that exp is the address of a local
00325     if (ty->resolvesToPointer()) {
00326         Exp* sub = e->getSubExp1();
00327         Location* mof = Location::memOf(sub);
00328         if (proc->findLocal(mof, ty)) {
00329             used->insert(mof);
00330             override = true;
00331         }
00332     }
00333     return true;
00334 }
00335 
00336 bool UsedLocalFinder::visit(Terminal* e) {
00337     if (e->getOper() == opDefineAll)
00338         all = true;
00339     char* sym = proc->findFirstSymbol(e);
00340     if (sym)
00341         used->insert(e);
00342     return true;        // Always continue recursion
00343 }
00344 
00345 
00346 bool UsedLocsVisitor::visit(Assign* s, bool& override) {
00347     Exp* lhs = s->getLeft();
00348     Exp* rhs = s->getRight();
00349     if (rhs) rhs->accept(ev);
00350     // Special logic for the LHS. Note: PPC can have r[tmp + 30] on LHS
00351     if (lhs->isMemOf() || lhs->isRegOf()) {
00352         Exp* child = ((Location*)lhs)->getSubExp1();    // m[xxx] uses xxx
00353         // Care! Don't want the memOnly flag when inside a m[...]. Otherwise, nothing will be found
00354         // Also beware that ev may be a UsedLocalFinder now
00355         UsedLocsFinder* ulf = dynamic_cast<UsedLocsFinder*>(ev);
00356         if (ulf) {
00357             bool wasMemOnly = ulf->isMemOnly();
00358             ulf->setMemOnly(false);
00359             child->accept(ev);
00360             ulf->setMemOnly(wasMemOnly);
00361         }
00362     } else if (lhs->getOper() == opArrayIndex || lhs->getOper() == opMemberAccess) {
00363         Exp* subExp1 = ((Binary*)lhs)->getSubExp1();    // array(base, index) and member(base, offset)?? use
00364         subExp1->accept(ev);                            // base and index
00365         Exp* subExp2 = ((Binary*)lhs)->getSubExp2();
00366         subExp2->accept(ev);
00367     } else if (lhs->getOper() == opAt) {                // foo@[first:last] uses foo, first, and last
00368         Exp* subExp1 = ((Ternary*)lhs)->getSubExp1();
00369         subExp1->accept(ev);
00370         Exp* subExp2 = ((Ternary*)lhs)->getSubExp2();
00371         subExp2->accept(ev);
00372         Exp* subExp3 = ((Ternary*)lhs)->getSubExp3();
00373         subExp3->accept(ev);
00374     }
00375     override = true;                // Don't do the usual accept logic
00376     return true;                    // Continue the recursion
00377 }
00378 bool UsedLocsVisitor::visit(PhiAssign* s, bool& override) {
00379     Exp* lhs = s->getLeft();
00380     // Special logic for the LHS
00381     if (lhs->isMemOf()) {
00382         Exp* child = ((Location*)lhs)->getSubExp1();
00383         UsedLocsFinder* ulf = dynamic_cast<UsedLocsFinder*>(ev);
00384         if (ulf) {
00385             bool wasMemOnly = ulf->isMemOnly();
00386             ulf->setMemOnly(false);
00387             child->accept(ev);
00388             ulf->setMemOnly(wasMemOnly);
00389         }
00390     } else if (lhs->getOper() == opArrayIndex || lhs->getOper() == opMemberAccess) {
00391         Exp* subExp1 = ((Binary*)lhs)->getSubExp1();
00392         subExp1->accept(ev);
00393         Exp* subExp2 = ((Binary*)lhs)->getSubExp2();
00394         subExp2->accept(ev);
00395     }
00396     PhiAssign::iterator uu;
00397     for (uu = s->begin(); uu != s->end(); uu++) {
00398         // Note: don't make the RefExp based on lhs, since it is possible that the lhs was renamed in fromSSA()
00399         // Use the actual expression in the PhiAssign
00400         // Also note that it's possible for uu->e to be NULL. Suppose variable a can be assigned to along in-edges
00401         // 0, 1, and 3; inserting the phi parameter at index 3 will cause a null entry at 2
00402         if (uu->e) {
00403             RefExp* temp = new RefExp(uu->e, uu->def);
00404             temp->accept(ev);
00405         }
00406     }
00407 
00408     override = true;                // Don't do the usual accept logic
00409     return true;                    // Continue the recursion
00410 }
00411 bool UsedLocsVisitor::visit(ImplicitAssign* s, bool& override) {
00412     Exp* lhs = s->getLeft();
00413     // Special logic for the LHS
00414     if (lhs->isMemOf()) {
00415         Exp* child = ((Location*)lhs)->getSubExp1();
00416         UsedLocsFinder* ulf = dynamic_cast<UsedLocsFinder*>(ev);
00417         if (ulf) {
00418             bool wasMemOnly = ulf->isMemOnly();
00419             ulf->setMemOnly(false);
00420             child->accept(ev);
00421             ulf->setMemOnly(wasMemOnly);
00422         }
00423     } else if (lhs->getOper() == opArrayIndex || lhs->getOper() == opMemberAccess) {
00424         Exp* subExp1 = ((Binary*)lhs)->getSubExp1();
00425         subExp1->accept(ev);
00426         Exp* subExp2 = ((Binary*)lhs)->getSubExp2();
00427         subExp2->accept(ev);
00428     }
00429     override = true;                // Don't do the usual accept logic
00430     return true;                    // Continue the recursion
00431 }
00432 
00433 bool UsedLocsVisitor::visit(CallStatement* s, bool& override) {
00434     Exp* pDest = s->getDest();
00435     if (pDest)
00436         pDest->accept(ev);
00437     StatementList::iterator it;
00438     StatementList& arguments = s->getArguments();
00439     for (it = arguments.begin(); it != arguments.end(); it++) {
00440         // Don't want to ever collect anything from the lhs
00441         ((Assign*)*it)->getRight()->accept(ev);
00442     }
00443     if (countCol) {
00444         DefCollector::iterator dd;
00445         DefCollector* col = s->getDefCollector();
00446         for (dd = col->begin(); dd != col->end(); ++dd)
00447             (*dd)->accept(this);
00448     }
00449     override = true;            // Don't do the normal accept logic
00450     return true;                // Continue the recursion
00451 }
00452 
00453 bool UsedLocsVisitor::visit(ReturnStatement* s, bool& override) {
00454     // For the final pass, only consider the first return
00455     ReturnStatement::iterator rr;
00456     for (rr = s->begin(); rr != s->end(); ++rr)
00457         (*rr)->accept(this);
00458     // Also consider the reaching definitions to be uses, so when they are the only non-empty component of this
00459     // ReturnStatement, they can get propagated to.
00460     if (countCol) {                     // But we need to ignore these "uses" unless propagating
00461         DefCollector::iterator dd;
00462         DefCollector* col = s->getCollector();
00463         for (dd = col->begin(); dd != col->end(); ++dd)
00464             (*dd)->accept(this);
00465     }
00466 
00467     // Insert a phantom use of "everything" here, so that we can find out if any childless calls define something that
00468     // may end up being returned
00469     // FIXME: Not here! Causes locals to never get removed. Find out where this belongs, if anywhere:
00470     //((UsedLocsFinder*)ev)->getLocSet()->insert(new Terminal(opDefineAll));
00471 
00472     override = true;            // Don't do the normal accept logic
00473     return true;                // Continue the recursion
00474 }
00475 
00476 bool UsedLocsVisitor::visit(BoolAssign* s, bool& override) {
00477     Exp* pCond = s->getCondExpr();
00478     if (pCond)
00479         pCond->accept(ev);              // Condition is used
00480     Exp* lhs = s->getLeft();
00481     if (lhs && lhs->isMemOf()) {    // If dest is of form m[x]...
00482         Exp* x = ((Location*)lhs)->getSubExp1();
00483         UsedLocsFinder* ulf = dynamic_cast<UsedLocsFinder*>(ev);
00484         if (ulf) {
00485             bool wasMemOnly = ulf->isMemOnly();
00486             ulf->setMemOnly(false);
00487             x->accept(ev);
00488             ulf->setMemOnly(wasMemOnly);
00489         }
00490     } else if (lhs->getOper() == opArrayIndex || lhs->getOper() == opMemberAccess) {
00491         Exp* subExp1 = ((Binary*)lhs)->getSubExp1();
00492         subExp1->accept(ev);
00493         Exp* subExp2 = ((Binary*)lhs)->getSubExp2();
00494         subExp2->accept(ev);
00495     }
00496     override = true;            // Don't do the normal accept logic
00497     return true;                // Continue the recursion
00498 }
00499 
00500 //
00501 // Expression subscripter
00502 //
00503 Exp* ExpSubscripter::preVisit(Location* e, bool& recur) {
00504     if (*e == *search) {
00505         recur = e->isMemOf();           // Don't double subscript unless m[...]
00506         return new RefExp(e, def);      // Was replaced by postVisit below
00507     }
00508     recur = true;
00509     return e;
00510 }
00511 
00512 Exp* ExpSubscripter::preVisit(Binary* e, bool& recur) {
00513     // array[index] is like m[addrexp]: requires a subscript
00514     if (e->isArrayIndex() && *e == *search) {
00515         recur = true;                   // Check the index expression
00516         return new RefExp(e, def);      // Was replaced by postVisit below
00517     }
00518     recur = true;
00519     return e;
00520 }
00521 
00522 Exp* ExpSubscripter::preVisit(Terminal* e) {
00523     if (*e == *search)
00524         return new RefExp(e, def);
00525     return e;
00526 }
00527 
00528 Exp* ExpSubscripter::preVisit(RefExp* e, bool& recur) {
00529     recur = false;          // Don't look inside... not sure about this
00530     return e;
00531 }
00532 
00533 // The Statement subscripter class
00534 void StmtSubscripter::visit(Assign* s, bool& recur) {
00535     Exp* rhs = s->getRight();
00536     s->setRight(rhs->accept(mod));
00537     // Don't subscript the LHS of an assign, ever
00538     Exp* lhs = s->getLeft();
00539     if (lhs->isMemOf() || lhs->isRegOf()) {
00540         ((Location*)lhs)->setSubExp1(((Location*)lhs)->getSubExp1()->accept(mod));
00541     }
00542     recur = false;
00543 }
00544 void StmtSubscripter::visit(PhiAssign* s, bool& recur) {
00545     Exp* lhs = s->getLeft();
00546     if (lhs->isMemOf()) {
00547         ((Location*)lhs)->setSubExp1(((Location*)lhs)->getSubExp1()->accept(mod));
00548     }
00549     recur = false;
00550 }
00551 void StmtSubscripter::visit(ImplicitAssign* s, bool& recur) {
00552     Exp* lhs = s->getLeft();
00553     if (lhs->isMemOf()) {
00554         ((Location*)lhs)->setSubExp1(((Location*)lhs)->getSubExp1()->accept(mod));
00555     }
00556     recur = false;
00557 }
00558 void StmtSubscripter::visit(BoolAssign* s, bool& recur) {
00559     Exp* lhs = s->getLeft();
00560     if (lhs->isMemOf()) {
00561         ((Location*)lhs)->setSubExp1(((Location*)lhs)->getSubExp1()->accept(mod));
00562     }
00563     Exp* rhs = s->getCondExpr();
00564     s->setCondExpr(rhs->accept(mod));
00565     recur = false;
00566 }
00567 
00568 void StmtSubscripter::visit(CallStatement* s, bool& recur) {
00569     Exp* pDest = s->getDest();
00570     if (pDest)
00571         s->setDest(pDest->accept(mod));
00572     // Subscript the ordinary arguments
00573     StatementList& arguments = s->getArguments();
00574     StatementList::iterator ss;
00575     for (ss = arguments.begin(); ss != arguments.end(); ++ss)
00576         (*ss)->accept(this);
00577     // Returns are like the LHS of an assignment; don't subscript them directly (only if m[x], and then only subscript
00578     // the x's)
00579     recur = false;          // Don't do the usual accept logic
00580 }
00581 
00582 
00583 // Size stripper
00584 Exp* SizeStripper::preVisit(Binary* b, bool& recur) {
00585     recur = true;           // Visit the binary's children
00586     if (b->isSizeCast())
00587         // Could be a size cast of a size cast
00588         return b->getSubExp2()->stripSizes();
00589     return b;
00590 }
00591 
00592 Exp* ExpConstCaster::preVisit(Const* c) {
00593     if (c->getConscript() == num) {
00594         changed = true;
00595         return new TypedExp(ty, c);
00596     }
00597     return c;
00598 }
00599 
00600 
00601 // This is the code (apart from definitions) to find all constants in a Statement
00602 bool ConstFinder::visit(Const* e) {
00603     lc.push_back(e);
00604     return true;
00605 }
00606 bool ConstFinder::visit(Location* e, bool& override) {
00607     if (e->isMemOf())
00608         override = false;       // We DO want to see constants in memofs
00609     else
00610         override = true;        // Don't consider register numbers, global names, etc
00611     return true;            
00612 }
00613 
00614 // This is in the POST visit function, because it's important to process any child expressions first.
00615 // Otherwise, for m[r28{0} - 12]{0}, you could be adding an implicit assignment with a NULL definition for r28.
00616 Exp* ImplicitConverter::postVisit(RefExp* e) {
00617     if (e->getDef() == NULL)
00618         e->setDef(cfg->findImplicitAssign(e->getSubExp1()));
00619     return e;
00620 }
00621 
00622 
00623 void StmtImplicitConverter::visit(PhiAssign* s, bool& recur) {
00624     // The LHS could be a m[x] where x has a null subscript; must do first
00625     s->setLeft(s->getLeft()->accept(mod));
00626     PhiAssign::iterator uu;
00627     for (uu = s->begin(); uu != s->end(); uu++) {
00628         if (uu->e == NULL) continue;
00629         if (uu->def == NULL)
00630             uu->def = cfg->findImplicitAssign(uu->e);
00631     }
00632     recur = false;      // Already done LHS
00633 }
00634 
00635 
00636 // Localiser. Subscript a location with the definitions that reach the call, or with {-} if none
00637 Exp* Localiser::preVisit(RefExp* e, bool& recur) {
00638     recur = false;              // Don't recurse into already subscripted variables
00639     mask <<= 1;
00640     return e;
00641 }
00642 
00643 Exp* Localiser::preVisit(Location* e, bool& recur) {
00644     recur = true;
00645     mask <<= 1;
00646     return e;
00647 }
00648 
00649 Exp* Localiser::postVisit(Location* e) {
00650     Exp* ret = e;
00651     if (!(unchanged & mask)) ret = e->simplify();
00652     mask >>= 1;
00653     Exp* r = call->findDefFor(ret);
00654     if (r) {
00655         ret = r->clone();
00656         if (0 && EXPERIMENTAL) {        // FIXME: check if sometimes needed
00657             // The trouble with the below is that you can propagate to say a call statement's argument expression and
00658             // not to the assignment of the actual argument. Examples: test/pentium/fromssa2, fbranch
00659             bool ch;
00660             ret = ret->propagateAllRpt(ch);     // Propagate into this repeatedly, in case propagation is limited
00661         }
00662         ret = ret->bypass();
00663         unchanged &= ~mask;
00664         mod = true;
00665     } else
00666         ret = new RefExp(ret, NULL);                // No definition reaches, so subscript with {-}
00667     return ret;
00668 }
00669 
00670 // Want to be able to localise a few terminals, in particular <all>
00671 Exp* Localiser::postVisit(Terminal* e) {
00672     Exp* ret = e;
00673     if (!(unchanged & mask)) ret = e->simplify();
00674     mask >>= 1;
00675     Exp* r = call->findDefFor(ret);
00676     if (r) {
00677         ret = r->clone()->bypass();
00678         unchanged &= ~mask;
00679         mod = true;
00680     } else
00681         ret = new RefExp(ret, NULL);                // No definition reaches, so subscript with {-}
00682     return ret;
00683 }
00684 
00685 bool ComplexityFinder::visit(Location* e, bool& override) {
00686     if (proc && proc->findFirstSymbol(e) != NULL) {
00687         // This is mapped to a local. Count it as zero, not about 3 (m[r28+4] -> memof, regof, plus)
00688         override = true;
00689         return true;
00690     }
00691     if (e->isMemOf() || e->isArrayIndex())
00692         count++;                // Count the more complex unaries
00693     override = false;
00694     return true;
00695 }
00696 bool ComplexityFinder::visit(Unary* e,      bool& override) {count++; override = false; return true;}
00697 bool ComplexityFinder::visit(Binary* e,     bool& override) {count++; override = false; return true;}
00698 bool ComplexityFinder::visit(Ternary* e,    bool& override) {count++; override = false; return true;}
00699 
00700 bool MemDepthFinder::visit(Location* e, bool& override) {
00701     if (e->isMemOf())
00702         ++depth;
00703     override = false;
00704     return true;
00705 }
00706 
00707 // Ugh! This is still a separate propagation mechanism from Statement::propagateTo().
00708 Exp* ExpPropagator::postVisit(RefExp* e) {
00709     // No need to call e->canRename() here, because if e's base expression is not suitable for renaming, it will never
00710     // have been renamed, and we never would get here
00711     if (!Statement::canPropagateToExp(e))       // Check of the definition statement is suitable for propagating
00712         return e;
00713     Statement* def = e->getDef();
00714     Exp* res = e;
00715     if (def && def->isAssign()) {
00716         Exp* lhs = ((Assign*)def)->getLeft();
00717         Exp* rhs = ((Assign*)def)->getRight();
00718         bool ch;
00719         res = e->searchReplaceAll(new RefExp(lhs, def), rhs->clone(), ch);
00720         if (ch) {
00721             change = true;                      // Record this change
00722             unchanged &= ~mask;                 // Been changed now (so simplify parent)
00723             if (res->isSubscript())
00724                 res = postVisit((RefExp*)res);  // Recursively propagate more if possible
00725         }
00726     }
00727     return res;
00728 }
00729 
00730 // Return true if e is a primitive expression; basically, an expression you can propagate to without causing
00731 // memory expression problems. See Mike's thesis for details
00732 // Algorithm: if find any unsubscripted location, not primitive
00733 //   Implicit definitions are primitive (but keep searching for non primitives)
00734 //   References to the results of calls are considered primitive... but only if bypassed?
00735 //   Other references considered non primitive
00736 // Start with result=true, must find primitivity in all components
00737 bool PrimitiveTester::visit(Location* e, bool& override) {
00738     // We reached a bare (unsubscripted) location. This is certainly not primitive
00739     override = true;
00740     result = false;
00741     return false;           // No need to continue searching
00742 }
00743 
00744 bool PrimitiveTester::visit(RefExp* e, bool& override) {
00745     Statement* def = e->getDef();
00746     // If defined by a call, e had better not be a memory location (crude approximation for now)
00747     if (def == NULL || def->getNumber() == 0 || def->isCall() && !e->getSubExp1()->isMemOf()) {
00748         // Implicit definitions are always primitive
00749         // The results of calls are always primitive
00750         override = true;    // Don't recurse into the reference
00751         return true;        // Result remains true
00752     }
00753 
00754     // For now, all references to other definitions will be considered non primitive. I think I'll have to extend this!
00755     result = false;
00756     override = true;        // Regareless of outcome, don't recurse into the reference
00757     return true;
00758 }
00759 
00760 bool ExpHasMemofTester::visit(Location *e, bool& override) {
00761     if (e->isMemOf()) {
00762         override = true;    // Don't recurse children (not needed surely)
00763         result = true;      // Found a memof
00764         return false;       // Don't continue searching the expression
00765     }
00766     override = false;
00767     return true;
00768 }
00769 
00770 bool TempToLocalMapper::visit(Location *e, bool& override) {
00771     if (e->isTemp()) {
00772         // We have a temp subexpression; get its name
00773         char* tempName = ((Const*)e->getSubExp1())->getStr();
00774         Type* ty = Type::getTempType(tempName);     // Types for temps strictly depend on the name
00775         // This call will do the mapping from the temp to a new local:
00776         proc->getSymbolExp(e, ty, true);
00777     }
00778     override = true;        // No need to examine the string
00779     return true;
00780 }
00781 
00782 ExpRegMapper::ExpRegMapper(UserProc* p) : proc(p) {
00783     prog = proc->getProg();
00784 }
00785 
00786 // The idea here is to map the default of a register to a symbol with the type of that first use. If the register is
00787 // not involved in any conflicts, it will use this name by default
00788 bool ExpRegMapper::visit(RefExp *e, bool& override) {
00789     Exp* base = e->getSubExp1();
00790     if (base->isRegOf() || proc->isLocalOrParamPattern(base))   // Don't convert if e.g. a global
00791         proc->checkLocalFor(e);
00792     override = true;        // Don't examine the r[] inside
00793     return true;
00794 }
00795 
00796 bool StmtRegMapper::common(Assignment *stmt, bool& override) {
00797     // In case lhs is a reg or m[reg] such that reg is otherwise unused
00798     Exp* lhs = stmt->getLeft();
00799     RefExp* re = new RefExp(lhs, stmt);
00800     re->accept((ExpRegMapper*)ev);
00801     override = false;
00802     return true;
00803 }
00804 
00805 bool StmtRegMapper::visit(        Assign* stmt, bool& override) {return common(stmt, override);}
00806 bool StmtRegMapper::visit(     PhiAssign* stmt, bool& override) {return common(stmt, override);}
00807 bool StmtRegMapper::visit(ImplicitAssign* stmt, bool& override) {return common(stmt, override);}
00808 bool StmtRegMapper::visit(    BoolAssign* stmt, bool& override) {return common(stmt, override);}
00809 
00810 // Constant global converter. Example: m[m[r24{16} + m[0x8048d60]{-}]{-}]{-} -> m[m[r24{16} + 32]{-}]{-}
00811 // Allows some complex variations to be matched to standard indirect call forms
00812 Exp* ConstGlobalConverter::preVisit(RefExp* e, bool& recur) {
00813     Statement* def = e->getDef();
00814     Exp *base, *addr, *idx, *glo;
00815     if (def == NULL || def->isImplicit()) {
00816         if (    (base = e->getSubExp1(), base->isMemOf()) &&
00817                 (addr = ((Location*)base)->getSubExp1(), addr->isIntConst())) {
00818             // We have a m[K]{-}
00819             int K = ((Const*)addr)->getInt();
00820             int value = prog->readNative4(K);
00821             recur = false;
00822             return new Const(value);
00823         } else if (base->isGlobal()) {
00824             // We have a glo{-}
00825             char* gname = ((Const*)(base->getSubExp1()))->getStr();
00826             ADDRESS gloValue = prog->getGlobalAddr(gname);
00827             int value = prog->readNative4(gloValue);
00828             recur = false;
00829             return new Const(value);
00830         } else if (base->isArrayIndex() &&
00831                     (idx = ((Binary*)base)->getSubExp2(), idx->isIntConst()) &&
00832                     (glo = ((Binary*)base)->getSubExp1(), glo->isGlobal())) {
00833             // We have a glo[K]{-}
00834             int K = ((Const*)idx)->getInt();
00835             char* gname = ((Const*)(glo->getSubExp1()))->getStr();
00836             ADDRESS gloValue = prog->getGlobalAddr(gname);
00837             Type* gloType = prog->getGlobal(gname)->getType();
00838             assert(gloType->isArray());
00839             Type* componentType = gloType->asArray()->getBaseType();
00840             int value = prog->readNative4(gloValue + K * (componentType->getSize() / 8));
00841             recur = false;
00842             return new Const(value);
00843         }
00844     }
00845     recur = true;
00846     return e;
00847 }
00848 
00849 bool ExpDestCounter::visit(RefExp *e, bool& override) {
00850     if (Statement::canPropagateToExp(e))
00851         destCounts[e]++;
00852     override = false;       // Continue searching my children
00853     return true;            // Continue visiting the rest of Exp* e
00854 }
00855 
00856 bool StmtDestCounter::visit(PhiAssign *stmt, bool& override) {
00857     override = false;
00858     return true;
00859 }
00860 
00861 
00862 bool FlagsFinder::visit(Binary *e,  bool& override) {
00863     if (e->isFlagCall()) {
00864         found = true;
00865         return false;       // Don't continue searching
00866     }
00867     override = false;
00868     return true;
00869 }
00870 
00871 // Search for bare memofs (not subscripted) in the expression
00872 bool BadMemofFinder::visit(Location* e, bool& override) {
00873     if (e->isMemOf()) {
00874         found = true;       // A bare memof
00875         return false;
00876     }
00877     override = false;
00878     return true;            // Continue searching
00879 }
00880 
00881 bool BadMemofFinder::visit(RefExp* e, bool& override) {
00882     Exp* base = e->getSubExp1();
00883     if (base->isMemOf()) {
00884         // Beware: it may be possible to have a bad memof inside a subscripted one
00885         Exp* addr = ((Location*)base)->getSubExp1();
00886         addr->accept(this);
00887         if (found)
00888             return false;   // Don't continue searching
00889 #if NEW         // FIXME: not ready for this until have incremental propagation
00890         char* sym = proc->lookupSym(e);
00891         if (sym == NULL) {
00892             found = true;           // Found a memof that is not a symbol
00893             override = true;        // Don't look inside the refexp
00894             return false;
00895         }
00896 #endif
00897     }
00898     override = true;        // Don't look inside the refexp
00899     return true;            // It has a symbol; noting bad foound yet but continue searching
00900 }
00901 
00902 // CastInserters. More cases to be implemented.
00903 
00904 // Check the type of the address expression of memof to make sure it is compatible with the given memofType.
00905 // memof may be changed internally to include a TypedExp, which will emit as a cast
00906 void ExpCastInserter::checkMemofType(Exp* memof, Type* memofType) {
00907     Exp* addr = ((Unary*)memof)->getSubExp1();
00908     if (addr->isSubscript()) {
00909         Exp* addrBase = ((RefExp*)addr)->getSubExp1();
00910         Type* actType = ((RefExp*)addr)->getDef()->getTypeFor(addrBase);
00911         Type* expectedType = new PointerType(memofType);
00912         if (!actType->isCompatibleWith(expectedType)) {
00913             ((Unary*)memof)->setSubExp1(new TypedExp(expectedType, addrBase));
00914         }
00915     }
00916 }
00917 
00918 Exp* ExpCastInserter::postVisit(RefExp* e) {
00919     Exp* base = e->getSubExp1();
00920     if (base->isMemOf()) {
00921         // Check to see if the address expression needs type annotation
00922         Statement* def = e->getDef();
00923         Type* memofType = def->getTypeFor(base);
00924         checkMemofType(base, memofType);
00925     }
00926     return e;
00927 }
00928 
00929 static Exp* checkSignedness(Exp* e, int reqSignedness) {
00930     Type* ty = e->ascendType();
00931     int currSignedness = 0;
00932     bool isInt = ty->resolvesToInteger();
00933     if (isInt) {
00934         currSignedness =  ty->asInteger()->getSignedness();
00935         currSignedness = (currSignedness >= 0) ? 1 : -1;
00936     }
00937     //if (!isInt || currSignedness != reqSignedness) { // }
00938     // Don't want to cast e.g. floats to integer
00939     if (isInt && currSignedness != reqSignedness) {
00940         IntegerType* newtype;
00941         if (!isInt)
00942             newtype = new IntegerType(STD_SIZE, reqSignedness);
00943         else
00944             newtype = new IntegerType(((IntegerType*)ty)->getSize(), reqSignedness);    // Transfer size
00945         newtype->setSigned(reqSignedness);
00946         return new TypedExp(newtype, e);
00947     }
00948     return e;
00949 }
00950 
00951 Exp* ExpCastInserter::postVisit(Binary* e) {
00952     OPER op = e->getOper();
00953     switch (op) {
00954         // This case needed for e.g. test/pentium/switch_gcc:
00955         case opLessUns:
00956         case opGtrUns:
00957         case opLessEqUns:
00958         case opGtrEqUns:
00959         case opShiftR:
00960             e->setSubExp1(checkSignedness(e->getSubExp1(), -1));
00961             if (op != opShiftR)             // The shift amount (second operand) is sign agnostic
00962                 e->setSubExp2(checkSignedness(e->getSubExp2(), -1));
00963             break;
00964         // This case needed for e.g. test/sparc/minmax2, if %g1 is declared as unsigned int
00965         case opLess:
00966         case opGtr:
00967         case opLessEq:
00968         case opGtrEq:
00969         case opShiftRA:
00970             e->setSubExp1(checkSignedness(e->getSubExp1(), +1));
00971             if (op != opShiftRA)
00972                 e->setSubExp2(checkSignedness(e->getSubExp2(), +1));
00973             break;
00974         default:
00975             break;
00976     }
00977     return e;
00978 }
00979 
00980 Exp* ExpCastInserter::postVisit(Const *e) {
00981     if (e->isIntConst()) {
00982         bool naturallySigned = e->getInt() < 0;
00983         Type* ty = e->getType();
00984         if (naturallySigned && ty->isInteger() && !ty->asInteger()->isSigned()) {
00985             return new TypedExp(new IntegerType(ty->asInteger()->getSize(), -1), e);
00986         }
00987     }
00988     return e;
00989 }
00990 
00991 bool StmtCastInserter::visit(         Assign *s) {return common(s);}
00992 bool StmtCastInserter::visit(      PhiAssign *s) {return common(s);}
00993 bool StmtCastInserter::visit(ImplicitAssign *s) {return common(s);}
00994 bool StmtCastInserter::visit(     BoolAssign *s) {return common(s);}
00995 bool StmtCastInserter::common(Assignment* s) {
00996     Exp* lhs = s->getLeft();
00997     if (lhs->isMemOf()) {
00998         Type* memofType = s->getType();
00999         ExpCastInserter::checkMemofType(lhs, memofType);
01000     }
01001     return true;
01002 }
01003 
01004 Exp* ExpSsaXformer::postVisit(RefExp *e) {
01005     char* sym = proc->lookupSymFromRefAny(e);
01006     if (sym != NULL)
01007         return Location::local(sym, proc);
01008     // We should not get here: all locations should be replaced with Locals or Parameters
01009     //LOG << "ERROR! Could not find local or parameter for " << e << " !!\n";
01010     return e->getSubExp1();     // At least strip off the subscript
01011 }
01012 
01013 // Common code for the left hand side of assignments
01014 void StmtSsaXformer::commonLhs(Assignment* as) {
01015     Exp* lhs = as->getLeft();
01016     lhs = lhs->accept((ExpSsaXformer*)mod);     // In case the LHS has say m[r28{0}+8] -> m[esp+8]
01017     RefExp* re = new RefExp(lhs, as);
01018     char* sym = proc->lookupSymFromRefAny(re);
01019     if (sym)
01020         as->setLeft(Location::local(sym, proc));
01021 }
01022 
01023 void StmtSsaXformer::visit(BoolAssign *s, bool& recur) {
01024     commonLhs(s);
01025     Exp* pCond = s->getCondExpr();
01026     pCond = pCond->accept((ExpSsaXformer*)mod);
01027     s->setCondExpr(pCond);
01028 }
01029 
01030 void StmtSsaXformer::visit(Assign *s, bool& recur) {
01031     commonLhs(s);
01032     Exp* rhs = s->getRight();
01033     rhs = rhs->accept((ExpSsaXformer*)mod);
01034     s->setRight(rhs);
01035 }
01036 
01037 void StmtSsaXformer::visit(ImplicitAssign *s, bool& recur) {
01038     commonLhs(s);
01039 }
01040 
01041 void StmtSsaXformer::visit(PhiAssign *s, bool& recur) {
01042     commonLhs(s);
01043     PhiAssign::iterator it;
01044     UserProc* proc = ((ExpSsaXformer*)mod)->getProc();
01045     for (it = s->begin(); it != s->end(); it++) {
01046         if (it->e == NULL) continue;
01047         RefExp* r = new RefExp(it->e, it->def);
01048         char* sym = proc->lookupSymFromRefAny(r);
01049         if (sym != NULL)
01050             it->e = Location::local(sym, proc);     // Some may be parameters, but hopefully it won't matter
01051     }
01052 }
01053 
01054 void StmtSsaXformer::visit(CallStatement* s, bool& recur) {
01055     Exp* pDest = s->getDest();
01056     if (pDest) {
01057         pDest = pDest->accept((ExpSsaXformer*)mod);
01058         s->setDest(pDest);
01059     }
01060     StatementList& arguments = s->getArguments();
01061     StatementList::iterator ss;
01062     for (ss = arguments.begin(); ss != arguments.end(); ++ss)
01063         (*ss)->accept(this);
01064     // Note that defines have statements (assignments) within a statement (this call). The fromSSA logic, which needs
01065     // to subscript definitions on the left with the statement pointer, won't work if we just call the assignment's
01066     // fromSSA() function
01067     StatementList& defines = s->getDefines();
01068     for (ss = defines.begin(); ss != defines.end(); ++ss) {
01069         Assignment* as = ((Assignment*)*ss);
01070         // FIXME: use of fromSSAleft is deprecated
01071         Exp *e = as->getLeft()->fromSSAleft(((ExpSsaXformer*)mod)->getProc(), s);
01072         // FIXME: this looks like a HACK that can go:
01073         Proc* procDest = s->getDestProc();
01074         if (procDest && procDest->isLib() && e->isLocal()) {
01075             UserProc* proc = s->getProc();      // Enclosing proc
01076             Type *lty = proc->getLocalType(((Const*)e->getSubExp1())->getStr());
01077             Type *ty = as->getType();
01078             if (ty && lty && *ty != *lty) {
01079                 LOG << "local " << e << " has type " << lty->getCtype() << " that doesn't agree with type of define " <<
01080                     ty->getCtype() << " of a library, why?\n";
01081                 proc->setLocalType(((Const*)e->getSubExp1())->getStr(), ty);
01082             }
01083         }
01084         as->setLeft(e);
01085     }
01086     // Don't think we'll need this anyway:
01087     // defCol.fromSSAform(ig);
01088 
01089     // However, need modifications of the use collector; needed when say eax is renamed to local5, otherwise
01090     // local5 is removed from the results of the call
01091     s->useColFromSsaForm(s);
01092 }
01093 
01094 // Map expressions to locals, using the (so far DFA based) type analysis information
01095 // Basically, descend types, and when you get to m[...] compare with the local high level pattern;
01096 // when at a sum or difference, check for the address of locals high level pattern that is a pointer
01097 
01098 // Map expressions to locals, some with names like param3
01099 DfaLocalMapper::DfaLocalMapper(UserProc* proc) : proc(proc) {
01100     sig = proc->getSignature();
01101     prog = proc->getProg();
01102     change = false;
01103 }
01104 
01105 // Common processing for the two main cases (visiting a Location or a Binary)
01106 bool DfaLocalMapper::processExp(Exp* e) {
01107     if (proc->isLocalOrParamPattern(e)) {   // Check if this is an appropriate pattern for local variables  
01108         if (sig->isStackLocal(prog, e)) {
01109             change = true;                  // We've made a mapping
01110             // We have probably not even run TA yet, so doing a full descendtype here would be silly
01111             // Note also that void is compatible with all types, so the symbol effectively covers all types
01112             proc->getSymbolExp(e, new VoidType(), true);
01113 #if 0
01114         } else {
01115             std::ostringstream ost;
01116             ost << "tparam" << proc->nextParamNum();
01117             const char* name = strdup(ost.str().c_str());
01118             proc->mapSymbolTo(e, Location::param(const_cast<char*>(name), proc));
01119 #endif
01120         }
01121         return false;           // set recur false: Don't dig inside m[x] to make m[a[m[x]]] !
01122     }
01123     return true;
01124 }
01125 
01126 Exp* DfaLocalMapper::preVisit(Location* e, bool& recur) {
01127 
01128     recur = true;
01129     if (e->isMemOf() && proc->findFirstSymbol(e) == NULL) {     // Need the 2nd test to ensure change set correctly
01130         recur = processExp(e);
01131     }
01132     return e;
01133 }
01134 
01135 Exp* DfaLocalMapper::preVisit(Binary* e, bool& recur) {
01136 #if 1
01137     // Check for sp -/+ K
01138     Exp* memOf_e = Location::memOf(e);
01139     if (proc->findFirstSymbol(memOf_e) != NULL) {
01140         recur = false;                              // Already done; don't recurse
01141         return e;
01142     } else {
01143         recur = processExp(memOf_e);                // Process m[this]
01144         if (!recur)                                 // If made a change this visit,
01145             return new Unary(opAddrOf, memOf_e);    // change to a[m[this]]
01146     }
01147 #endif
01148     return e;
01149 }
01150 
01151 Exp* DfaLocalMapper::preVisit(TypedExp* e, bool& recur) {
01152     // Assume it's already been done correctly, so don't recurse into this
01153     recur = false;
01154     return e;
01155 }
01156 

Generated on Tue Sep 19 21:18:35 2006 for Boomerang by  doxygen 1.4.6