proc.h

Go to the documentation of this file.
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

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