00001 /* 00002 * Copyright (C) 1998-2001, The University of Queensland 00003 * Copyright (C) 2000-2001, Sun Microsystems, Inc 00004 * Copyright (C) 2002-2006, Trent Waddington and Mike Van Emmerik 00005 * 00006 * See the file "LICENSE.TERMS" for information on usage and 00007 * redistribution of this file, and for a DISCLAIMER OF ALL 00008 * WARRANTIES. 00009 * 00010 */ 00011 00012 /*============================================================================== 00013 * FILE: proc.h 00014 * OVERVIEW: Interface for the procedure classes, which are used to store information about variables in the 00015 * procedure such as parameters and locals. 00016 *============================================================================*/ 00017 00018 /* 00019 * $Revision: 1.154 $ // 1.115.2.27 00020 */ 00021 00022 #ifndef _PROC_H_ 00023 #define _PROC_H_ 00024 00025 #include <list> 00026 #include <vector> 00027 #include <map> 00028 #include <set> 00029 #include <string> 00030 #include <assert.h> 00031 #include "exp.h" // For lessExpStar 00032 #include "cfg.h" // For cfg->simplify() 00033 #include "hllcode.h" 00034 #include "memo.h" 00035 #include "dataflow.h" // For class UseCollector 00036 #include "statement.h" // For embedded ReturnStatement pointer, etc 00037 #include "boomerang.h" // For USE_DOMINANCE_NUMS etc 00038 00039 class Prog; 00040 class UserProc; 00041 class Cfg; 00042 class BasicBlock; 00043 typedef BasicBlock* PBB; 00044 class Exp; 00045 class TypedExp; 00046 class lessTI; 00047 class Type; 00048 class RTL; 00049 class HLLCode; 00050 class HLCall; 00051 class Parameter; 00052 class Argument; 00053 class Signature; 00054 class Cluster; 00055 class XMLProgParser; 00056 00057 /*============================================================================== 00058 * Procedure class. 00059 *============================================================================*/ 00060 /// Interface for the procedure classes, which are used to store information about variables in the 00061 /// procedure such as parameters and locals. 00062 class Proc { 00063 public: 00064 00065 /** 00066 * Constructor with name, native address and optional bLib. 00067 */ 00068 Proc(Prog *prog, ADDRESS uNative, Signature *sig); 00069 00070 virtual ~Proc(); 00071 00072 /** 00073 * Gets name of this procedure. 00074 */ 00075 const char* getName(); 00076 00077 /** 00078 * Gets sets the name of this procedure. 00079 */ 00080 void setName(const char *nam); 00081 00082 /** 00083 * Get the native address. 00084 */ 00085 ADDRESS getNativeAddress(); 00086 00087 /** 00088 * Set the native address 00089 */ 00090 void setNativeAddress(ADDRESS a); 00091 00092 /** 00093 * Get the program this procedure belongs to. 00094 */ 00095 Prog *getProg() { return prog; } 00096 void setProg(Prog *p) { prog = p; } 00097 00098 /** 00099 * Get/Set the first procedure that calls this procedure (or null for main/start). 00100 */ 00101 Proc *getFirstCaller(); 00102 void setFirstCaller(Proc *p) { if (m_firstCaller == NULL) m_firstCaller = p; } 00103 00104 /** 00105 * Returns a pointer to the Signature 00106 */ 00107 Signature *getSignature() { return signature; } 00108 void setSignature(Signature *sig) { signature = sig; } 00109 00110 virtual void renameParam(const char *oldName, const char *newName); 00111 00112 /* 00113 * Prints this procedure to an output stream. 00114 */ 00115 //virtual std::ostream& put(std::ostream& os) = 0; 00116 00117 /** 00118 * Modify actuals so that it is now the list of locations that must 00119 * be passed to this procedure. The modification will be to either add 00120 * dummy locations to actuals, delete from actuals, or leave it 00121 * unchanged. 00122 * Add "dummy" params: this will be required when there are 00123 * less live outs at a call site than the number of parameters 00124 * expected by the procedure called. This will be a result of 00125 * one of two things: 00126 * i) a value returned by a preceeding call is used as a 00127 * parameter and as such is not detected as defined by the 00128 * procedure. E.g.: 00129 * 00130 * foo(bar(x)); 00131 * 00132 * Here, the result of bar(x) is used as the first and only 00133 * parameter to foo. On some architectures (such as SPARC), 00134 * the location used as the first parameter (e.g. %o0) is 00135 * also the location in which a value is returned. So, the 00136 * call to bar defines this location implicitly as shown in 00137 * the following SPARC assembly that may be generated by from 00138 * the above code: 00139 * 00140 * mov x, %o0 00141 * call bar 00142 * nop 00143 * call foo 00144 * 00145 * As can be seen, there is no definition of %o0 after the 00146 * call to bar and before the call to foo. Adding the integer 00147 * return location is therefore a good guess for the dummy 00148 * location to add (but may occasionally be wrong). 00149 * 00150 * ii) uninitialised variables are used as parameters to a call 00151 * 00152 * Note that both of these situations can only occur on 00153 * architectures such as SPARC that use registers for parameter 00154 * passing. Stack parameters must always be pushed so that the 00155 * callee doesn't access the caller's non-parameter portion of 00156 * stack. 00157 * 00158 * This used to be a virtual function, implemented differenty for 00159 * LibProcs and for UserProcs. But in fact, both need the exact same 00160 * treatment; the only difference is how the local member "parameters" 00161 * is set (from common.hs in the case of LibProc objects, or from analysis 00162 * in the case of UserProcs). 00163 */ 00164 void matchParams(std::list<Exp*>& actuals, UserProc& caller); 00165 00166 /** 00167 * Get a list of types to cast a given list of actual parameters to 00168 */ 00169 std::list<Type>* getParamTypeList(const std::list<Exp*>& actuals); 00170 00171 /** 00172 * Return true if this is a library proc 00173 */ 00174 virtual bool isLib() {return false;} 00175 00176 /** 00177 * Return true if this procedure doesn't return 00178 */ 00179 virtual bool isNoReturn() = 0; 00180 00181 /** 00182 * OutPut operator for a Proc object. 00183 */ 00184 friend std::ostream& operator<<(std::ostream& os, Proc& proc); 00185 00186 virtual Exp *getProven(Exp *left) = 0; // Get the RHS, if any, that is proven for left 00187 virtual Exp *getPremised(Exp *left) = 0; // Get the RHS, if any, that is premised for left 00188 virtual bool isPreserved(Exp* e) = 0; ///< Return whether e is preserved by this proc 00189 00190 /// Set an equation as proven. Useful for some sorts of testing 00191 void setProvenTrue(Exp* fact); 00192 00193 /** 00194 * Get the callers 00195 * Note: the callers will be in a random order (determined by memory allocation) 00196 */ 00197 std::set<CallStatement*>& getCallers() { return callerSet; } 00198 00199 /** 00200 * Add to the set of callers 00201 */ 00202 void addCaller(CallStatement* caller) { callerSet.insert(caller); } 00203 00204 /** 00205 * Add to a set of caller Procs 00206 */ 00207 void addCallers(std::set<UserProc*>& callers); 00208 00209 void removeParameter(Exp *e); 00210 virtual void removeReturn(Exp *e); 00211 //virtual void addReturn(Exp *e); 00212 // void sortParameters(); 00213 00214 virtual void printCallGraphXML(std::ostream &os, int depth, bool recurse = true); 00215 void printDetailsXML(); 00216 void clearVisited() { visited = false; } 00217 bool isVisited() { return visited; } 00218 00219 Cluster *getCluster() { return cluster; } 00220 void setCluster(Cluster *c) { cluster = c; } 00221 00222 protected: 00223 00224 bool visited; ///< For printCallGraphXML 00225 00226 Prog *prog; ///< Program containing this procedure. 00227 00228 /** 00229 * The formal signature of this procedure. This information is determined 00230 * either by the common.hs file (for a library function) or by analysis. 00231 * 00232 * NOTE: This belongs in the CALL, because the same procedure can have different signatures if it happens to 00233 * have varargs. Temporarily here till it can be permanently moved. 00234 */ 00235 Signature *signature; 00236 00237 /** Persistent state */ 00238 ADDRESS address; ///< Procedure's address. 00239 Proc *m_firstCaller; ///< first procedure to call this procedure. 00240 ADDRESS m_firstCallerAddr; ///< can only be used once. 00241 /// All the expressions that have been proven true. (Could perhaps do with a list of some that are proven false) 00242 // FIXME: shouldn't this be in UserProc, with logic associated with the signature doing the equivalent thing 00243 // for LibProcs? 00244 /// Proof the form r28 = r28 + 4 is stored as map from "r28" to "r28+4" (NOTE: no subscripts) 00245 std::map<Exp*, Exp*, lessExpStar> provenTrue; 00246 // Cache of queries proven false (to save time) 00247 // std::map<Exp*, Exp*, lessExpStar> provenFalse; 00248 // Premises for recursion group analysis. This is a preservation that is assumed true only for definitions by 00249 // calls reached in the proof. It also prevents infinite looping of this proof logic. 00250 std::map<Exp*, Exp*, lessExpStar> recurPremises; 00251 00252 std::set<CallStatement*> callerSet; ///< Set of callers (CallStatements that call this procedure). 00253 Cluster *cluster; ///< Cluster this procedure is contained within. 00254 00255 friend class XMLProgParser; 00256 Proc() : visited(false), prog(NULL), signature(NULL), address(0), m_firstCaller(NULL), m_firstCallerAddr(0), 00257 cluster(NULL) { } 00258 00259 }; // class Proc 00260 00261 /*============================================================================== 00262 * LibProc class. 00263 *============================================================================*/ 00264 class LibProc : public Proc { 00265 public: 00266 00267 LibProc(Prog *prog, std::string& name, ADDRESS address); 00268 virtual ~LibProc(); 00269 00270 /** 00271 * Return true, since is a library proc 00272 */ 00273 bool isLib() {return true;} 00274 00275 virtual bool isNoReturn(); 00276 00277 virtual Exp* getProven(Exp* left); // Get the RHS that is proven for left 00278 virtual Exp* getPremised(Exp* left) {return NULL;} // Get the RHS that is premised for left 00279 virtual bool isPreserved(Exp* e); ///< Return whether e is preserved by this proc 00280 00281 /* 00282 * Prints this procedure to an output stream. 00283 */ 00284 //std::ostream& put(std::ostream& os); 00285 00286 void getInternalStatements(StatementList &internal); 00287 protected: 00288 00289 friend class XMLProgParser; 00290 LibProc() : Proc() { } 00291 }; // class LibProc 00292 00293 enum ProcStatus { 00294 PROC_UNDECODED, ///< Has not even been decoded 00295 PROC_DECODED, ///< Decoded, no attempt at decompiling 00296 PROC_SORTED, ///< Decoded, and CFG has been sorted by address 00297 PROC_VISITED, ///< Has been visited on the way down in decompile() 00298 PROC_INCYCLE, ///< Is involved in cycles, has not completed early decompilation as yet 00299 PROC_PRESERVEDS, ///< Has had preservation analysis done 00300 PROC_EARLYDONE, ///< Has completed everything except the global analyses 00301 PROC_FINAL, ///< Has had final decompilation 00302 // , PROC_RETURNS ///< Has had returns intersected with all caller's defines 00303 PROC_CODE_GENERATED,///< Has had code generated 00304 }; 00305 00306 typedef std::set <UserProc*> ProcSet; 00307 typedef std::list<UserProc*> ProcList; 00308 00309 /*============================================================================== 00310 * UserProc class. 00311 *============================================================================*/ 00312 00313 class UserProc : public Proc { 00314 00315 /** 00316 * The control flow graph. 00317 */ 00318 Cfg* cfg; 00319 00320 /** 00321 * The status of this user procedure. 00322 * Status: undecoded .. final decompiled 00323 */ 00324 ProcStatus status; 00325 00326 /* 00327 * Somewhat DEPRECATED now. Eventually use the localTable. 00328 * This map records the names and types for local variables. It should be a subset of the symbolMap, which also 00329 * stores parameters. 00330 * It is a convenient place to store the types of locals after 00331 * conversion from SSA form, since it is then difficult to access the definitions of locations. 00332 * This map could be combined with symbolMap below, but beware of parameters (in symbols but not locals) 00333 */ 00334 std::map<std::string, Type*> locals; 00335 00336 int nextLocal; // Number of the next local. Can't use locals.size() because some get deleted 00337 int nextParam; // Number for param1, param2, etc 00338 00339 /** 00340 * A map between machine dependent locations and their corresponding symbolic, machine independent 00341 * representations. Example: m[r28{0} - 8] -> local5; this means that *after* transforming out of SSA 00342 * form, any locations not specifically mapped otherwise (e.g. m[r28{0} - 8]{55} -> local6) will get this 00343 * name. 00344 * It is a *multi*map because one location can have several default names differentiated by type. 00345 * E.g. r24 -> eax for int, r24 -> eax_1 for float 00346 */ 00347 public: 00348 typedef std::multimap<Exp*,Exp*,lessExpStar> SymbolMap; 00349 private: 00350 SymbolMap symbolMap; 00351 00352 /** 00353 * The local "symbol table", which is aware of overlaps 00354 */ 00355 DataIntervalMap localTable; 00356 00357 /** 00358 * Set of callees (Procedures that this procedure calls). Used for call graph, among other things 00359 */ 00360 std::list<Proc*> calleeList; 00361 00362 /** 00363 * A collector for initial parameters (locations used before being defined). Note that final parameters don't 00364 * use this; it's only of use during group decompilation analysis (sorting out recursion) 00365 */ 00366 UseCollector col; 00367 00368 /** 00369 * The list of parameters, ordered and filtered. 00370 * Note that a LocationList could be used, but then there would be nowhere to store the types (for DFA based TA) 00371 * The RHS is just ignored; the list is of ImplicitAssigns. 00372 * DESIGN ISSUE: it would be nice for the parameters' implicit assignments to be the sole definitions, i.e. not 00373 * need other implicit assignments for these. But the targets of RefExp's are not expected to change address, 00374 * so they are not suitable at present (since the addresses regularly get changed as the parameters get 00375 * recreated). 00376 */ 00377 StatementList parameters; 00378 00379 /** 00380 * The set of address-escaped locals and parameters. If in this list, they should not be propagated 00381 */ 00382 LocationSet addressEscapedVars; 00383 00384 // The modifieds for the procedure are now stored in the return statement 00385 00386 /** 00387 * DataFlow object. Holds information relevant to transforming to and from SSA form. 00388 */ 00389 DataFlow df; 00390 00391 /** 00392 * Current statement number. Makes it easier to split decompile() into smaller pieces. 00393 */ 00394 int stmtNumber; 00395 00396 /** 00397 * Pointer to a set of procedures involved in a recursion group. 00398 * NOTE: Each procedure in the cycle points to the same set! However, there can be several separate cycles. 00399 * E.g. in test/source/recursion.c, there is a cycle with f and g, while another is being built up (it only 00400 * has c, d, and e at the point where the f-g cycle is found). 00401 */ 00402 ProcSet* cycleGrp; 00403 00404 /** 00405 * A map of stack locations (negative values) to types. This is currently 00406 * PENTIUM specific and is computed from range information. 00407 */ 00408 std::map<int, Type *> stackMap; 00409 00410 /// function to do safe adding. 00411 void addToStackMap(int c, Type *ty); 00412 00413 public: 00414 00415 UserProc(Prog *prog, std::string& name, ADDRESS address); 00416 virtual ~UserProc(); 00417 00418 /** 00419 * Records that this procedure has been decoded. 00420 */ 00421 void setDecoded(); 00422 00423 /** 00424 * Removes the decoded bit and throws away all the current information about this procedure. 00425 */ 00426 void unDecode(); 00427 00428 /** 00429 * Returns a pointer to the CFG object. 00430 */ 00431 Cfg* getCFG() { return cfg; } 00432 00433 /** 00434 * Returns a pointer to the DataFlow object. 00435 */ 00436 DataFlow* getDataFlow() {return &df;} 00437 00438 /** 00439 * Deletes the whole CFG and all the RTLs and Exps associated with it. Also nulls the internal cfg 00440 * pointer (to prevent strange errors) 00441 */ 00442 void deleteCFG(); 00443 00444 virtual bool isNoReturn(); 00445 00446 /** 00447 * Returns an abstract syntax tree for the procedure in the internal representation. This function actually 00448 * _calculates_ * this value and is expected to do so expensively. 00449 */ 00450 SyntaxNode *getAST(); 00451 // print it to a file 00452 void printAST(SyntaxNode *a = NULL); 00453 00454 /** 00455 * Returns whether or not this procedure can be decoded (i.e. has it already been decoded). 00456 */ 00457 bool isDecoded() { return status >= PROC_DECODED; } 00458 bool isDecompiled() { return status >= PROC_FINAL; } 00459 bool isEarlyRecursive() {return cycleGrp != NULL && status <= PROC_INCYCLE;} 00460 bool doesRecurseTo(UserProc* p) {return cycleGrp && cycleGrp->find(p) != cycleGrp->end();} 00461 00462 bool isSorted() { return status >= PROC_SORTED; } 00463 void setSorted() { setStatus(PROC_SORTED); } 00464 00465 ProcStatus getStatus() { return status; } 00466 void setStatus(ProcStatus s); 00467 00468 /// code generation 00469 void generateCode(HLLCode *hll); 00470 00471 /// print this proc, mainly for debugging 00472 void print(std::ostream &out, bool html = false); 00473 void printParams(std::ostream &out, bool html = false); 00474 char *prints(); 00475 void dump(); 00476 void printToLog(); 00477 void printDFG(); 00478 void printSymbolMap(std::ostream& out, bool html = false); ///< Print just the symbol map 00479 void dumpSymbolMap(); ///< For debugging 00480 void dumpSymbolMapx(); ///< For debugging 00481 void testSymbolMap(); ///< For debugging 00482 void dumpLocals(std::ostream& os, bool html = false); 00483 void dumpLocals(); 00484 00485 /// simplify the statements in this proc 00486 void simplify() { cfg->simplify(); } 00487 00488 // simple windows mode decompile 00489 void windowsModeDecompile(); 00490 00491 /// Begin the decompile process at this procedure. path is a list of pointers to procedures, representing the 00492 /// path from the current entry point to the current procedure in the call graph. Pass an empty set at the top 00493 /// level. indent is the indentation level; pass 0 at the top level 00494 ProcSet* decompile(ProcList* path, int& indent); 00495 /// Initialise decompile: sort CFG, number statements, dominator tree, etc. 00496 void initialiseDecompile(); 00497 /// Prepare for preservation analysis only. 00498 void prePresDecompile(); 00499 /// Early decompile: Place phi functions, number statements, first rename, propagation: ready for preserveds. 00500 void earlyDecompile(); 00501 /// Middle decompile: All the decompilation from preservation up to but not including removing unused 00502 /// statements. Returns the cycle set from the recursive call to decompile() 00503 ProcSet* middleDecompile(ProcList* path, int indent); 00504 /// Analyse the whole group of procedures for conditional preserveds, and update till no change. 00505 /// Also finalise the whole group. 00506 void recursionGroupAnalysis(ProcList* path, int indent); 00507 /// Global type analysis (for this procedure). 00508 void typeAnalysis(); 00509 /// Inserting casts as needed (for this procedure) 00510 void insertCasts(); 00511 // Range analysis (for this procedure). 00512 void rangeAnalysis(); 00513 // Detect and log possible buffer overflows 00514 void logSuspectMemoryDefs(); 00515 // Split the set of cycle-associated procs into individual subcycles. 00516 //void findSubCycles(CycleList& path, CycleSet& cs, CycleSetSet& sset); 00517 // The inductive preservation analysis. 00518 bool inductivePreservation(UserProc* topOfCycle); 00519 // Mark calls involved in the recursion cycle as non childless (each child has had middleDecompile called on 00520 // it now). 00521 void markAsNonChildless(ProcSet* cs); 00522 // Update the defines and arguments in calls. 00523 void updateCalls(); 00524 // Look for short circuit branching 00525 void branchAnalysis(); 00526 // Fix any ugly branch statements (from propagating too much) 00527 void fixUglyBranches(); 00528 // Place the phi functions 00529 void placePhiFunctions() {df.placePhiFunctions(this);} 00530 00531 // void propagateAtDepth(int depth); 00532 // Rename block variables, with log if verbose. Return true if a change 00533 bool doRenameBlockVars(int pass, bool clearStacks = false); 00534 //int getMaxDepth() {return maxDepth;} // FIXME: needed? 00535 bool canRename(Exp* e) {return df.canRename(e, this);} 00536 00537 Statement *getStmtAtLex(unsigned int begin, unsigned int end); 00538 00539 /** 00540 * All the decompile stuff except propagation, DFA repair, and null/unused statement removal. 00541 * \todo Check if this function is used, and remove it if it isn't 00542 */ 00543 void complete(); 00544 00545 /// Initialise the statements, e.g. proc, bb pointers 00546 void initStatements(); 00547 void numberStatements(); 00548 bool nameStackLocations(); 00549 void removeRedundantPhis(); 00550 void findPreserveds(); ///< Was trimReturns() 00551 void findSpPreservation(); ///< Preservations only for the stack pointer 00552 void removeSpAssignsIfPossible(); 00553 void removeMatchingAssignsIfPossible(Exp *e); 00554 void updateReturnTypes(); 00555 void fixCallAndPhiRefs(int d); ///< Perform call and phi statement bypassing at depth d 00556 void fixCallAndPhiRefs(); ///< Perform call and phi statement bypassing at all depths 00557 /// Helper function for fixCallAndPhiRefs 00558 void fixRefs(int n, int depth, std::map<Exp*, Exp*, lessExpStar>& pres, StatementList& removes); 00559 void initialParameters(); ///< Get initial parameters based on proc's use collector 00560 void mapLocalsAndParams(); ///< Map expressions to locals and initial parameters 00561 void findFinalParameters(); 00562 int nextParamNum() {return ++nextParam;} 00563 void addParameter(Exp *e, Type* ty); ///< Add parameter to signature 00564 void insertParameter(Exp* e, Type* ty); ///< Insert into parameters list correctly sorted 00565 // void addNewReturns(int depth); 00566 void updateArguments(); ///< Update the arguments in calls 00567 void updateCallDefines(); ///< Update the defines in calls 00568 void reverseStrengthReduction(); 00569 /// Trim parameters. If depth not given or == -1, perform at all depths 00570 void trimParameters(int depth = -1); 00571 void processFloatConstants(); 00572 //void mapExpressionsToParameters(); ///< must be in SSA form 00573 void mapExpressionsToLocals(bool lastPass = false); 00574 void addParameterSymbols(); 00575 bool isLocal(Exp* e); ///< True if e represents a stack local variable 00576 bool isLocalOrParam(Exp* e); ///< True if e represents a stack local or stack param 00577 bool isLocalOrParamPattern(Exp* e); ///< True if e could represent a stack local or stack param 00578 bool existsLocal(char* name); ///< True if a local exists with name \a name 00579 bool isAddressEscapedVar(Exp* e) {return addressEscapedVars.exists(e);} 00580 bool isPropagatable(Exp* e); ///< True if e can be propagated 00581 00582 /// find the procs the calls point to 00583 void assignProcsToCalls(); 00584 00585 /// perform final simplifications 00586 void finalSimplify(); 00587 00588 // eliminate duplicate arguments 00589 void eliminateDuplicateArgs(); 00590 00591 private: 00592 void searchRegularLocals(OPER minusOrPlus, bool lastPass, int sp, StatementList& stmts); 00593 public: 00594 bool removeNullStatements(); 00595 bool removeDeadStatements(); 00596 typedef std::map<Statement*, int> RefCounter; 00597 void countRefs(RefCounter& refCounts); 00598 /// Remove unused statements. 00599 void remUnusedStmtEtc(); 00600 void remUnusedStmtEtc(RefCounter& refCounts /* , int depth*/); 00601 void removeUnusedLocals(); 00602 void mapTempsToLocals(); 00603 void removeCallLiveness(); // Remove all liveness info in UseCollectors in calls 00604 bool propagateAndRemoveStatements(); 00605 /// Propagate statemtents; return true if change; set convert if an indirect call is converted to direct 00606 /// (else clear) 00607 bool propagateStatements(bool& convert, int pass); 00608 void findLiveAtDomPhi(LocationSet& usedByDomPhi); 00609 #if USE_DOMINANCE_NUMS 00610 void setDominanceNumbers(); 00611 #endif 00612 void propagateToCollector(); 00613 void clearUses(); ///< Clear the useCollectors (in this Proc, and all calls). 00614 void clearRanges(); 00615 //int findMaxDepth(); ///< Find max memory nesting depth. 00616 00617 void fromSSAform(); 00618 void findPhiUnites(ConnectionGraph& pu); // Find the locations united by Phi-functions 00619 void insertAssignAfter(Statement* s, Exp* left, Exp* right); 00620 void removeSubscriptsFromSymbols(); 00621 void removeSubscriptsFromParameters(); 00622 //// Insert statement \a a after statement \a s. 00623 void insertStatementAfter(Statement* s, Statement* a); 00624 // Add a mapping for the destinations of phi functions that have one argument that is a parameter 00625 void nameParameterPhis(); 00626 void mapParameters(); 00627 00628 void conTypeAnalysis(); 00629 void dfaTypeAnalysis(); 00630 /// Trim parameters to procedure calls with ellipsis (...). Also add types for ellipsis parameters, if any 00631 /// Returns true if any signature types so added. 00632 bool ellipsisProcessing(); 00633 00634 // For the final pass of removing returns that are never used 00635 //typedef std::map<UserProc*, std::set<Exp*, lessExpStar> > ReturnCounter; 00636 // Used for checking for unused parameters 00637 bool doesParamChainToCall(Exp* param, UserProc* p, ProcSet* visited); 00638 bool isRetNonFakeUsed(CallStatement* c, Exp* loc, UserProc* p, ProcSet* visited); 00639 // Remove redundant parameters. Return true if remove any 00640 bool removeRedundantParameters(); 00641 /// Remove any returns that are not used by any callers 00642 /// return true if any returns are removed 00643 bool removeRedundantReturns(std::set<UserProc*>& removeRetSet); 00644 /// Reurn true if location e is used gainfully in this procedure. visited is a set of UserProcs already 00645 /// visited. 00646 bool checkForGainfulUse(Exp* e, ProcSet& visited); 00647 /// Update parameters and call livenesses to take into account the changes causes by removing a return from this 00648 /// procedure, or a callee's parameter (which affects this procedure's arguments, which are also uses). 00649 void updateForUseChange(std::set<UserProc*>& removeRetSet); 00650 //void countUsedReturns(ReturnCounter& rc); 00651 //void doCountReturns(Statement* def, ReturnCounter& rc, Exp* loc); 00652 00653 /// returns true if the prover is working right now 00654 bool canProveNow(); 00655 /// prove any arbitary property of this procedure. If conditional is true, do not save the result, as it may 00656 /// be conditional on premises stored in other procedures 00657 bool prove(Exp *query, bool conditional = false); 00658 /// helper function, should be private 00659 bool prover(Exp *query, std::set<PhiAssign*> &lastPhis, std::map<PhiAssign*, Exp*> &cache, 00660 Exp* original, PhiAssign *lastPhi = NULL); 00661 00662 /// promote the signature if possible 00663 void promoteSignature(); 00664 00665 /// get all the statements 00666 void getStatements(StatementList &stmts); 00667 00668 virtual void removeReturn(Exp *e); 00669 //virtual void addReturn(Exp *e); 00670 00671 /// remove a statement 00672 void removeStatement(Statement *stmt); 00673 00674 // /// inline constants / decode function pointer constants 00675 //bool processConstants(); 00676 //void processTypes(); 00677 00678 bool searchAll(Exp* search, std::list<Exp*> &result); 00679 00680 void getDefinitions(LocationSet &defs); 00681 void addImplicitAssigns(); 00682 void makeSymbolsImplicit(); 00683 void makeParamsImplicit(); 00684 StatementList& getParameters() { return parameters; } 00685 StatementList& getModifieds() { return theReturnStatement->getModifieds(); } 00686 00687 private: 00688 /** 00689 * Find a pointer to the Exp* representing the given var 00690 * Used by the above 2 00691 */ 00692 Exp** findVarEntry(int idx); 00693 00694 /** 00695 * A special pass to check the sizes of memory that is about to be converted into a var, ensuring that the 00696 * largest size used in the proc is used for all references (and it's declared that size). 00697 */ 00698 void checkMemSizes(); 00699 00700 /** 00701 * Implement the above for one given Exp* 00702 */ 00703 void checkMemSize(Exp* e); 00704 00705 public: 00706 /** 00707 * Return an expression that is equivilent to e in terms of local variables. Creates new locals as needed. 00708 */ 00709 Exp *getSymbolExp(Exp *le, Type *ty = NULL, bool lastPass = false); 00710 00711 00712 /** 00713 * Given a machine dependent location, return a generated symbolic representation for it. 00714 */ 00715 void toSymbolic(TypedExp* loc, TypedExp* result, bool local = true); 00716 00717 /* 00718 * Return a string for a new local suitable for e 00719 */ 00720 char* newLocalName(Exp* e); 00721 00722 /** 00723 * Return the next available local variable; make it the given type. Note: was returning TypedExp*. 00724 * If nam is non null, use that name 00725 */ 00726 Exp* newLocal(Type* ty, Exp* e, char* nam = NULL); 00727 00728 /** 00729 * Add a new local supplying all needed information. 00730 */ 00731 void addLocal(Type *ty, const char *nam, Exp *e); 00732 00733 /// return a local's type 00734 Type *getLocalType(const char *nam); 00735 void setLocalType(const char *nam, Type *ty); 00736 00737 Type *getParamType(const char *nam); 00738 00739 /// return a symbol's exp (note: the original exp, like r24, not local1) 00740 Exp *expFromSymbol(const char *nam); 00741 void setExpSymbol(const char *nam, Exp *e, Type* ty); 00742 void mapSymbolTo(Exp* from, Exp* to); 00743 /// As above but with replacement 00744 void mapSymbolToRepl(Exp* from, Exp* oldTo, Exp* newTo); 00745 void removeSymbolMapping(Exp* from, Exp* to); /// Remove this mapping 00746 /// Lookup the expression in the symbol map. Return NULL or a C string with the symbol. Use the Type* ty to 00747 /// select from several names in the multimap; the name corresponding to the first compatible type is returned 00748 Exp* getSymbolFor(Exp* e, Type* ty); /// Lookup the symbol map considering type 00749 char* lookupSym(Exp* e, Type* ty); 00750 char* lookupSymFromRef(RefExp* r); // Lookup a specific symbol for the given ref 00751 char* lookupSymFromRefAny(RefExp* r); // Lookup a specific symbol if any, else the general one if any 00752 char* lookupParam(Exp* e); // Find the implicit definition for e and lookup a symbol 00753 void checkLocalFor(RefExp* r); // Check if r is already mapped to a local, else add one 00754 Type* getTypeForLocation(Exp* e); // Find the type of the local or parameter e 00755 /// Determine whether e is a local, either as a true opLocal (e.g. generated by fromSSA), or if it is in the 00756 /// symbol map and the name is in the locals map. If it is a local, return its name, else NULL 00757 char* findLocal(Exp* e, Type* ty); 00758 char* findLocalFromRef(RefExp* r); 00759 char* findFirstSymbol(Exp* e); 00760 int getNumLocals() { return (int)locals.size(); } 00761 const char *getLocalName(int n); 00762 char *getSymbolName(Exp* e); ///< As getLocalName, but look for expression e 00763 void renameLocal(const char *oldName, const char *newName); 00764 virtual void renameParam(const char *oldName, const char *newName); 00765 00766 char* getRegName(Exp* r); /// Get a name like eax or o2 from r24 or r8 00767 void setParamType(const char* nam, Type* ty); 00768 void setParamType(int idx, Type* ty); 00769 00770 /** 00771 * Print the locals declaration in C style. 00772 */ 00773 void printLocalsAsC(std::ostream& os); 00774 00775 /** 00776 * Get the BB that is the entry point (not always the first BB) 00777 */ 00778 PBB getEntryBB(); 00779 00780 /* 00781 * Prints this procedure to an output stream. 00782 */ 00783 //std::ostream& put(std::ostream& os); 00784 00785 /** 00786 * Set the entry BB for this procedure (constructor has the entry address) 00787 */ 00788 void setEntryBB(); 00789 00790 /** 00791 * Get the callees. 00792 */ 00793 std::list<Proc*>& getCallees() { return calleeList; } 00794 00795 /** 00796 * Add to the set of callees. 00797 */ 00798 void addCallee(Proc* callee); 00799 00800 /** 00801 * Add to a set of callee Procs. 00802 */ 00803 void addCallees(std::list<UserProc*>& callees); 00804 00805 /** 00806 * return true if this procedure contains the given address. 00807 */ 00808 bool containsAddr(ADDRESS uAddr); 00809 00810 /** 00811 * Change BB containing this statement from a COMPCALL to a CALL. 00812 */ 00813 void undoComputedBB(Statement* stmt) { 00814 cfg->undoComputedBB(stmt); } 00815 00816 /* 00817 * Return true if this proc uses the special aggregate pointer as the 00818 * first parameter 00819 */ 00820 //virtual bool isAggregateUsed() {return aggregateUsed;} 00821 00822 virtual Exp* getProven(Exp* left); 00823 virtual Exp* getPremised(Exp* left); 00824 // Set a location as a new premise, i.e. assume e=e 00825 void setPremise(Exp* e) {e = e->clone(); recurPremises[e] = e;} 00826 void killPremise(Exp* e) {recurPremises.erase(e);} 00827 virtual bool isPreserved(Exp* e); ///< Return whether e is preserved by this proc 00828 00829 virtual void printCallGraphXML(std::ostream &os, int depth, 00830 bool recurse = true); 00831 void printDecodedXML(); 00832 void printAnalysedXML(); 00833 void printSSAXML(); 00834 void printXML(); 00835 void printUseGraph(); 00836 00837 00838 bool searchAndReplace(Exp *search, Exp *replace); 00839 00840 /// Cast the constant whose conscript is num to be type ty 00841 void castConst(int num, Type* ty); 00842 00843 /// Add a location to the UseCollector; this means this location is used before defined, and hence is an 00844 /// *initial* parameter. Note that final parameters don't use this information; it's only for handling recursion. 00845 void useBeforeDefine(Exp* loc) {col.insert(loc);} 00846 00847 /// Copy the decoded indirect control transfer instructions' RTLs to the front end's map, and decode any new 00848 /// targets for this CFG 00849 void processDecodedICTs(); 00850 00851 private: 00852 /// We ensure that there is only one return statement now. See code in frontend/frontend.cpp handling case 00853 /// STMT_RET. If no return statement, this will be NULL. 00854 ReturnStatement* theReturnStatement; 00855 int DFGcount; 00856 public: 00857 ADDRESS getTheReturnAddr() { 00858 return theReturnStatement == NULL ? NO_ADDRESS : theReturnStatement->getRetAddr();} 00859 void setTheReturnAddr(ReturnStatement* s, ADDRESS r) { 00860 assert(theReturnStatement == NULL); 00861 theReturnStatement = s; 00862 theReturnStatement->setRetAddr(r);} 00863 ReturnStatement* getTheReturnStatement() {return theReturnStatement;} 00864 bool filterReturns(Exp* e); ///< Decide whether to filter out e (return true) or keep it 00865 bool filterParams(Exp* e); ///< As above but for parameters and arguments 00866 00867 /// Find and if necessary insert an implicit reference before s whose address expression is a and type is t. 00868 void setImplicitRef(Statement* s, Exp* a, Type* ty); 00869 00870 protected: 00871 friend class XMLProgParser; 00872 UserProc(); 00873 void setCFG(Cfg *c) { cfg = c; } 00874 }; // class UserProc 00875 00876 #endif