graph.h 5.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132
  1. /*****************************************************************************
  2. * CFG, BB and interval related definitions
  3. * (C) Cristina Cifuentes
  4. ****************************************************************************/
  5. /* Types of basic block nodes */
  6. /* Real basic blocks: type defined according to their out-edges */
  7. #define ONE_BRANCH 0 /* unconditional branch */
  8. #define TWO_BRANCH 1 /* conditional branch */
  9. #define MULTI_BRANCH 2 /* case branch */
  10. #define FALL_NODE 3 /* fall through */
  11. #define RETURN_NODE 4 /* procedure/program return */
  12. #define CALL_NODE 5 /* procedure call */
  13. #define LOOP_NODE 6 /* loop instruction */
  14. #define REP_NODE 7 /* repeat instruction */
  15. #define INTERVAL_NODE 8 /* contains interval list */
  16. #define TERMINATE_NODE 11 /* Exit to DOS */
  17. #define NOWHERE_NODE 12 /* No outedges going anywhere */
  18. /* Depth-first traversal constants */
  19. #define DFS_DISP 1 /* Display graph pass */
  20. #define DFS_MERGE 2 /* Merge nodes pass */
  21. #define DFS_NUM 3 /* DFS numbering pass */
  22. #define DFS_CASE 4 /* Case pass */
  23. #define DFS_ALPHA 5 /* Alpha code generation*/
  24. #define DFS_JMP 9 /* rmJMP pass - must be largest flag */
  25. /* Control flow analysis constants */
  26. #define NO_TYPE 0 /* node is not a loop header*/
  27. #define WHILE_TYPE 1 /* node is a while header */
  28. #define REPEAT_TYPE 2 /* node is a repeat header */
  29. #define ENDLESS_TYPE 3 /* endless loop header */
  30. /* Uninitialized values for certain fields */
  31. #define NO_NODE MAX /* node has no associated node */
  32. #define NO_DOM MAX /* node has no dominator */
  33. #define UN_INIT MAX /* uninitialized variable */
  34. #define THEN 0 /* then edge */
  35. #define ELSE 1 /* else edge */
  36. /* Basic Block (BB) flags */
  37. #define INVALID_BB 0x0001 /* BB is not valid any more */
  38. #define IS_LATCH_NODE 0x0002 /* BB is the latching node of a loop */
  39. /* Interval structure */
  40. typedef struct _queueNode {
  41. struct _BB *node; /* Ptr to basic block */
  42. struct _queueNode *next;
  43. } queue;
  44. typedef struct _intNode {
  45. byte numInt; /* # of the interval */
  46. byte numOutEdges; /* Number of out edges */
  47. queue *nodes; /* Nodes of the interval*/
  48. queue *currNode; /* Current node */
  49. struct _intNode *next; /* Next interval */
  50. } interval;
  51. typedef union
  52. {
  53. dword ip; /* Out edge icode address */
  54. struct _BB *BBptr; /* Out edge pointer to next BB */
  55. interval *intPtr; /* Out edge ptr to next interval*/
  56. } TYPEADR_TYPE;
  57. /* Basic block (BB) node definition */
  58. typedef struct _BB {
  59. byte nodeType; /* Type of node */
  60. Int traversed; /* Boolean: traversed yet? */
  61. Int start; /* First instruction offset */
  62. Int length; /* No. of instructions this BB */
  63. Int numHlIcodes; /* No. of high-level icodes */
  64. flags32 flg; /* BB flags */
  65. /* In edges and out edges */
  66. Int numInEdges; /* Number of in edges */
  67. struct _BB **inEdges; /* Array of ptrs. to in edges */
  68. Int numOutEdges; /* Number of out edges */
  69. TYPEADR_TYPE *edges; /* Array of ptrs. to out edges */
  70. /* For interval construction */
  71. Int beenOnH; /* #times been on header list H */
  72. Int inEdgeCount; /* #inEdges (to find intervals) */
  73. struct _BB *reachingInt; /* Reaching interval header */
  74. interval *inInterval; /* Node's interval */
  75. /* For derived sequence construction */
  76. interval *correspInt; /* Corresponding interval in
  77. * derived graph Gi-1 */
  78. /* For live register analysis
  79. * LiveIn(b) = LiveUse(b) U (LiveOut(b) - Def(b)) */
  80. dword liveUse; /* LiveUse(b) */
  81. dword def; /* Def(b) */
  82. dword liveIn; /* LiveIn(b) */
  83. dword liveOut; /* LiveOut(b) */
  84. /* For structuring analysis */
  85. Int dfsFirstNum; /* DFS #: first visit of node */
  86. Int dfsLastNum; /* DFS #: last visit of node */
  87. Int immedDom; /* Immediate dominator (dfsLast
  88. * index) */
  89. Int ifFollow; /* node that ends the if */
  90. Int loopType; /* Type of loop (if any) */
  91. Int latchNode; /* latching node of the loop */
  92. Int numBackEdges; /* # of back edges */
  93. Int loopHead; /* most nested loop head to which
  94. * this node belongs (dfsLast) */
  95. Int loopFollow; /* node that follows the loop */
  96. Int caseHead; /* most nested case to which this
  97. node belongs (dfsLast) */
  98. Int caseTail; /* tail node for the case */
  99. Int index; /* Index, used in several ways */
  100. struct _BB *next; /* Next (list link) */
  101. } BB;
  102. typedef BB *PBB;
  103. /* Derived Sequence structure */
  104. typedef struct _derivedNode {
  105. BB *Gi; /* Graph pointer */
  106. interval *Ii; /* Interval list of Gi */
  107. struct _derivedNode *next; /* Next derived graph */
  108. } derSeq;