Procedure.h 8.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221
  1. #pragma once
  2. #include <llvm/ADT/ilist.h>
  3. #include <llvm/ADT/ilist_node.h>
  4. #include <bitset>
  5. #include "BasicBlock.h"
  6. #include "locident.h"
  7. #include "state.h"
  8. #include "icode.h"
  9. #include "StackFrame.h"
  10. /* PROCEDURE NODE */
  11. struct CALL_GRAPH;
  12. struct Expr;
  13. struct Disassembler;
  14. struct Function;
  15. struct CALL_GRAPH;
  16. typedef llvm::iplist<Function> FunctionListType;
  17. typedef FunctionListType lFunction;
  18. typedef lFunction::iterator ilFunction;
  19. namespace llvm
  20. {
  21. // Traits for intrusive list of basic blocks...
  22. template<>
  23. struct ilist_traits<BB> : public ilist_default_traits<BB>
  24. {
  25. // createSentinel is used to get hold of the node that marks the end of the
  26. // list... (same trick used here as in ilist_traits<Instruction>)
  27. BB *createSentinel() const {
  28. return static_cast<BB*>(&Sentinel);
  29. }
  30. static void destroySentinel(BB*) {}
  31. BB *provideInitialHead() const { return createSentinel(); }
  32. BB *ensureHead(BB*) const { return createSentinel(); }
  33. static void noteHead(BB*, BB*) {}
  34. //static ValueSymbolTable *getSymTab(Function *ItemParent);
  35. private:
  36. mutable ilist_half_node<BB> Sentinel;
  37. };
  38. }
  39. /* Procedure FLAGS */
  40. enum PROC_FLAGS
  41. {
  42. PROC_BADINST=0x00000100,/* Proc contains invalid or 386 instruction */
  43. PROC_IJMP =0x00000200,/* Proc incomplete due to indirect jmp */
  44. PROC_ICALL =0x00000400, /* Proc incomplete due to indirect call */
  45. PROC_HLL =0x00001000, /* Proc is likely to be from a HLL */
  46. CALL_PASCAL =0x00002000, /* Proc uses Pascal calling convention */
  47. CALL_C =0x00004000, /* Proc uses C calling convention */
  48. CALL_UNKNOWN=0x00008000, /* Proc uses unknown calling convention */
  49. PROC_NEAR =0x00010000, /* Proc exits with near return */
  50. PROC_FAR =0x00020000, /* Proc exits with far return */
  51. GRAPH_IRRED =0x00100000, /* Proc generates an irreducible graph */
  52. SI_REGVAR =0x00200000, /* SI is used as a stack variable */
  53. DI_REGVAR =0x00400000, /* DI is used as a stack variable */
  54. PROC_IS_FUNC=0x00800000, /* Proc is a function */
  55. REG_ARGS =0x01000000, /* Proc has registers as arguments */
  56. PROC_VARARG =0x02000000, /* Proc has variable arguments */
  57. PROC_OUTPUT =0x04000000, /* C for this proc has been output */
  58. PROC_RUNTIME=0x08000000, /* Proc is part of the runtime support */
  59. PROC_ISLIB =0x10000000, /* Proc is a library function */
  60. PROC_ASM =0x20000000, /* Proc is an intrinsic assembler routine */
  61. PROC_IS_HLL =0x40000000 /* Proc has HLL prolog code */
  62. #define CALL_MASK 0xFFFF9FFF /* Masks off CALL_C and CALL_PASCAL */
  63. };
  64. struct FunctionType
  65. {
  66. bool m_vararg;
  67. bool isVarArg() const {return m_vararg;}
  68. };
  69. struct Assignment
  70. {
  71. Expr *lhs;
  72. Expr *rhs;
  73. };
  74. struct JumpTable
  75. {
  76. uint32_t start;
  77. uint32_t finish;
  78. bool valid() {return start<finish;}
  79. size_t size() { return (finish-start)/2;}
  80. size_t entrySize() { return 2;}
  81. void pruneEntries(uint16_t cs);
  82. };
  83. class FunctionCfg
  84. {
  85. std::list<BB*> m_listBB; /* Ptr. to BB list/CFG */
  86. public:
  87. typedef std::list<BB*>::iterator iterator;
  88. iterator begin() {
  89. return m_listBB.begin();
  90. }
  91. iterator end() {
  92. return m_listBB.end();
  93. }
  94. BB * &front() { return m_listBB.front();}
  95. void nodeSplitting()
  96. {
  97. /* Converts the irreducible graph G into an equivalent reducible one, by
  98. * means of node splitting. */
  99. fprintf(stderr,"Attempt to perform node splitting: NOT IMPLEMENTED\n");
  100. }
  101. void push_back(BB *v) { m_listBB.push_back(v);}
  102. };
  103. struct Function : public llvm::ilist_node<Function>
  104. {
  105. typedef llvm::iplist<BB> BasicBlockListType;
  106. // BasicBlock iterators...
  107. typedef BasicBlockListType::iterator iterator;
  108. typedef BasicBlockListType::const_iterator const_iterator;
  109. private:
  110. BasicBlockListType BasicBlocks; ///< The basic blocks
  111. public:
  112. uint32_t procEntry; /* label number */
  113. std::string name; /* Meaningful name for this proc */
  114. STATE state; /* Entry state */
  115. int depth; /* Depth at which we found it - for printing */
  116. uint32_t flg; /* Combination of Icode & Proc flags */
  117. int16_t cbParam; /* Probable no. of bytes of parameters */
  118. STKFRAME args; /* Array of arguments */
  119. LOCAL_ID localId; /* Local identifiers */
  120. ID retVal; /* Return value - identifier */
  121. /* Icodes and control flow graph */
  122. CIcodeRec Icode; /* Object with ICODE records */
  123. FunctionCfg m_actual_cfg;
  124. std::list<BB*> m_cfg; /* Ptr. to BB list/CFG */
  125. std::vector<BB*> m_dfsLast;
  126. std::list<BB*> heldBBs;
  127. //BB * *dfsLast; /* Array of pointers to BBs in dfsLast
  128. // * (reverse postorder) order */
  129. size_t numBBs; /* Number of BBs in the graph cfg */
  130. bool hasCase; /* Procedure has a case node */
  131. /* For interprocedural live analysis */
  132. LivenessSet liveIn; /* Registers used before defined */
  133. LivenessSet liveOut; /* Registers that may be used in successors */
  134. bool liveAnal; /* Procedure has been analysed already */
  135. Function(void */*ty*/=0) : procEntry(0),depth(0),flg(0),cbParam(0),m_cfg(0),m_dfsLast(0),numBBs(0),
  136. hasCase(false),liveIn(0),liveOut(0),liveAnal(0)//,next(0),prev(0)
  137. {
  138. }
  139. public:
  140. static Function *Create(void *ty=0,int /*Linkage*/=0,const std::string &nm="",void */*module*/=0)
  141. {
  142. Function *r=new Function(ty);
  143. r->name = nm;
  144. return r;
  145. }
  146. bool anyFlagsSet(uint32_t t) { return (flg&t)!=0;}
  147. bool hasRegArgs() const { return (flg & REG_ARGS)!=0;}
  148. bool isLibrary() const { return (flg & PROC_ISLIB)!=0;}
  149. void compoundCond();
  150. void writeProcComments();
  151. void lowLevelAnalysis();
  152. void bindIcodeOff();
  153. void dataFlow(LivenessSet &liveOut);
  154. void compressCFG();
  155. void highLevelGen();
  156. void structure(derSeq *derivedG);
  157. derSeq *checkReducibility();
  158. void createCFG();
  159. void markImpure();
  160. void findImmedDom();
  161. void FollowCtrl(CALL_GRAPH *pcallGraph, STATE *pstate);
  162. void process_operands(ICODE &pIcode, STATE *pstate);
  163. bool process_JMP(ICODE &pIcode, STATE *pstate, CALL_GRAPH *pcallGraph);
  164. boolT process_CALL(ICODE &pIcode, CALL_GRAPH *pcallGraph, STATE *pstate);
  165. void freeCFG();
  166. void codeGen(std::ostream &fs);
  167. void mergeFallThrough(BB *pBB);
  168. void structIfs();
  169. void structLoops(derSeq *derivedG);
  170. void buildCFG(Disassembler &ds);
  171. void controlFlowAnalysis();
  172. void newRegArg(iICODE picode, iICODE ticode);
  173. void writeProcComments(std::ostream &ostr);
  174. void displayCFG();
  175. void displayStats();
  176. void processHliCall(Expr *exp, iICODE picode);
  177. void preprocessReturnDU(LivenessSet &_liveOut);
  178. Expr * adjustActArgType(Expr *_exp, hlType forType);
  179. std::string writeCall(Function *tproc, STKFRAME &args, int *numLoc);
  180. protected:
  181. void extractJumpTableRange(ICODE& pIcode, STATE *pstate, JumpTable &table);
  182. bool followAllTableEntries(JumpTable &table, uint32_t cs, ICODE &pIcode, CALL_GRAPH *pcallGraph, STATE *pstate);
  183. bool removeInEdge_Flag_and_ProcessLatch(BB *pbb, BB *a, BB *b);
  184. bool Case_X_and_Y(BB* pbb, BB* thenBB, BB* elseBB);
  185. bool Case_X_or_Y(BB* pbb, BB* thenBB, BB* elseBB);
  186. bool Case_notX_or_Y(BB* pbb, BB* thenBB, BB* elseBB);
  187. bool Case_notX_and_Y(BB* pbb, BB* thenBB, BB* elseBB);
  188. void replaceInEdge(BB* where, BB* which, BB* with);
  189. void processExpPush(int &numHlIcodes, iICODE picode);
  190. // TODO: replace those with friend visitor ?
  191. void propLongReg(int loc_ident_idx, const ID &pLocId);
  192. void propLongStk(int i, const ID &pLocId);
  193. void propLongGlb(int i, const ID &pLocId);
  194. void processTargetIcode(iICODE picode, int &numHlIcodes, iICODE ticode, bool isLong);
  195. int findBackwarLongDefs(int loc_ident_idx, const ID &pLocId, iICODE iter);
  196. int findForwardLongUses(int loc_ident_idx, const ID &pLocId, iICODE beg);
  197. void structCases();
  198. void findExps();
  199. void genDU1();
  200. void elimCondCodes();
  201. void liveRegAnalysis(LivenessSet &in_liveOut);
  202. void findIdioms();
  203. void propLong();
  204. void genLiveKtes();
  205. uint8_t findDerivedSeq (derSeq &derivedGi);
  206. bool nextOrderGraph(derSeq &derivedGi);
  207. };