BasicBlock.h 5.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141
  1. #pragma once
  2. #include <list>
  3. #include <vector>
  4. #include <bitset>
  5. #include <string>
  6. #include <llvm/ADT/ilist.h>
  7. #include <llvm/ADT/ilist_node.h>
  8. #include <boost/range.hpp>
  9. #include "icode.h"
  10. #include "types.h"
  11. #include "graph.h"
  12. //#include "icode.h"
  13. /* Basic block (BB) node definition */
  14. struct Function;
  15. class CIcodeRec;
  16. struct BB;
  17. struct LOCAL_ID;
  18. struct interval;
  19. //TODO: consider default address value -> INVALID
  20. struct TYPEADR_TYPE
  21. {
  22. uint32_t ip; /* Out edge icode address */
  23. BB * BBptr; /* Out edge pointer to next BB */
  24. interval *intPtr; /* Out edge ptr to next interval*/
  25. TYPEADR_TYPE(uint32_t addr=0) : ip(addr),BBptr(nullptr),intPtr(nullptr)
  26. {}
  27. TYPEADR_TYPE(interval *v) : ip(0),BBptr(nullptr),intPtr(v)
  28. {}
  29. };
  30. struct BB : public llvm::ilist_node<BB>
  31. {
  32. private:
  33. BB(const BB&);
  34. BB() : nodeType(0),traversed(DFS_NONE),
  35. numHlIcodes(0),flg(0),
  36. inEdges(0),
  37. edges(0),beenOnH(0),inEdgeCount(0),reachingInt(0),
  38. inInterval(0),correspInt(0),liveUse(0),def(0),liveIn(0),liveOut(0),
  39. dfsFirstNum(0),dfsLastNum(0),immedDom(0),ifFollow(0),loopType(0),latchNode(0),
  40. numBackEdges(0),loopHead(0),loopFollow(0),caseHead(0),caseTail(0),index(0)
  41. {
  42. }
  43. //friend class SymbolTableListTraits<BB, Function>;
  44. typedef boost::iterator_range<iICODE> rCODE;
  45. rCODE instructions;
  46. public:
  47. struct ValidFunctor
  48. {
  49. bool operator()(BB *p) {return p->valid();}
  50. };
  51. iICODE begin();
  52. iICODE end() const;
  53. riICODE rbegin();
  54. riICODE rend();
  55. ICODE &front();
  56. ICODE &back();
  57. size_t size();
  58. uint8_t nodeType; /* Type of node */
  59. eDFS traversed; /* last traversal id is held here traversed yet? */
  60. int numHlIcodes; /* No. of high-level icodes */
  61. uint32_t flg; /* BB flags */
  62. /* In edges and out edges */
  63. std::vector<BB *> inEdges; // does not own held pointers
  64. //int numOutEdges; /* Number of out edges */
  65. std::vector<TYPEADR_TYPE> edges;/* Array of ptrs. to out edges */
  66. /* For interval construction */
  67. int beenOnH; /* #times been on header list H */
  68. int inEdgeCount; /* #inEdges (to find intervals) */
  69. BB * reachingInt; /* Reaching interval header */
  70. interval *inInterval; /* Node's interval */
  71. /* For derived sequence construction */
  72. interval *correspInt; /* Corresponding interval in
  73. * derived graph Gi-1 */
  74. /* For live register analysis
  75. * LiveIn(b) = LiveUse(b) U (LiveOut(b) - Def(b)) */
  76. std::bitset<32> liveUse; /* LiveUse(b) */
  77. std::bitset<32> def; /* Def(b) */
  78. std::bitset<32> liveIn; /* LiveIn(b) */
  79. std::bitset<32> liveOut; /* LiveOut(b) */
  80. /* For structuring analysis */
  81. int dfsFirstNum; /* DFS #: first visit of node */
  82. int dfsLastNum; /* DFS #: last visit of node */
  83. int immedDom; /* Immediate dominator (dfsLast
  84. * index) */
  85. int ifFollow; /* node that ends the if */
  86. int loopType; /* Type of loop (if any) */
  87. int latchNode; /* latching node of the loop */
  88. size_t numBackEdges; /* # of back edges */
  89. int loopHead; /* most nested loop head to which this node belongs (dfsLast) */
  90. int loopFollow; /* node that follows the loop */
  91. int caseHead; /* most nested case to which this
  92. node belongs (dfsLast) */
  93. int caseTail; /* tail node for the case */
  94. int index; /* Index, used in several ways */
  95. static BB * Create(void *ctx=0,const std::string &s="",Function *parent=0,BB *insertBefore=0);
  96. static BB * CreateIntervalBB(Function *parent);
  97. static BB * Create(const rCODE &r, uint8_t _nodeType, Function *parent);
  98. void writeCode(int indLevel, Function *pProc, int *numLoc, int latchNode, int ifFollow);
  99. void mergeFallThrough(CIcodeRec &Icode);
  100. void dfsNumbering(std::vector<BB *> &dfsLast, int *first, int *last);
  101. void displayDfs();
  102. void display();
  103. /// getParent - Return the enclosing method, or null if none
  104. ///
  105. const Function *getParent() const { return Parent; }
  106. Function *getParent() { return Parent; }
  107. void writeBB(std::ostream &ostr, int lev, Function *pProc, int *numLoc);
  108. BB * rmJMP(int marker, BB *pBB);
  109. void genDU1();
  110. void findBBExps(LOCAL_ID &locals, Function *f);
  111. bool valid() {return 0==(flg & INVALID_BB); }
  112. bool wasTraversedAtLevel(int l) const {return traversed==l;}
  113. ICODE * writeLoopHeader(int &indLevel, Function* pProc, int *numLoc, BB *&latch, boolT &repCond);
  114. void addOutEdge(uint32_t ip) // TODO: fix this
  115. {
  116. edges.push_back(TYPEADR_TYPE(ip));
  117. }
  118. void addOutEdgeInterval(interval *i) // TODO: fix this
  119. {
  120. edges.push_back(TYPEADR_TYPE(i));
  121. }
  122. void RemoveUnusedDefs(eReg regi, int defRegIdx, iICODE picode);
  123. private:
  124. bool FindUseBeforeDef(eReg regi, int defRegIdx, iICODE start_at);
  125. void ProcessUseDefForFunc(eReg regi, int defRegIdx, iICODE picode);
  126. bool isEndOfPath(int latch_node_idx) const;
  127. Function *Parent;
  128. };