graph.h 3.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
  1. /*
  2. ****************************************************************************
  3. * CFG, BB and interval related definitions
  4. * ( C ) Cristina Cifuentes
  5. ****************************************************************************
  6. */
  7. #pragma once
  8. #include <stdint.h>
  9. #include <list>
  10. struct Function;
  11. /* Types of basic block nodes */
  12. /* Real basic blocks: type defined according to their out-edges */
  13. enum eBBKind
  14. {
  15. ONE_BRANCH = 0, /* unconditional branch */
  16. TWO_BRANCH = 1, /* conditional branch */
  17. MULTI_BRANCH=2, /* case branch */
  18. FALL_NODE=3, /* fall through */
  19. RETURN_NODE=4, /* procedure/program return */
  20. CALL_NODE=5, /* procedure call */
  21. LOOP_NODE=6, /* loop instruction */
  22. REP_NODE=7, /* repeat instruction */
  23. INTERVAL_NODE=8, /* contains interval list */
  24. TERMINATE_NODE=11, /* Exit to DOS */
  25. NOWHERE_NODE=12 /* No outedges going anywhere */
  26. };
  27. /* Depth-first traversal constants */
  28. enum eDFS
  29. {
  30. DFS_NONE,
  31. DFS_DISP=1, /* Display graph pass */
  32. DFS_MERGE=2, /* Merge nodes pass */
  33. DFS_NUM=3, /* DFS numbering pass */
  34. DFS_CASE=4, /* Case pass */
  35. DFS_ALPHA=5, /* Alpha code generation*/
  36. DFS_JMP=9 /* rmJMP pass - must be largest flag */
  37. };
  38. /* Control flow analysis constants */
  39. enum eNodeHeaderType
  40. {
  41. NO_TYPE=0, /* node is not a loop header*/
  42. WHILE_TYPE=1, /* node is a while header */
  43. REPEAT_TYPE=2, /* node is a repeat header */
  44. ENDLESS_TYPE=3 /* endless loop header */
  45. };
  46. /* Uninitialized values for certain fields */
  47. #define NO_NODE MAX /* node has no associated node */
  48. #define NO_DOM MAX /* node has no dominator */
  49. #define UN_INIT MAX /* uninitialized variable */
  50. #define THEN 0 /* then edge */
  51. #define ELSE 1 /* else edge */
  52. /* Basic Block (BB) flags */
  53. #define INVALID_BB 0x0001 /* BB is not valid any more */
  54. #define IS_LATCH_NODE 0x0002 /* BB is the latching node of a loop */
  55. struct BB;
  56. /* Interval structure */
  57. typedef std::list<BB *> queue;
  58. struct interval
  59. {
  60. uint8_t numInt; /* # of the interval */
  61. uint8_t numOutEdges; /* Number of out edges */
  62. queue nodes; /* Nodes of the interval*/
  63. queue::iterator currNode; /* Current node */
  64. interval *next; /* Next interval */
  65. BB *firstOfInt();
  66. interval()
  67. {
  68. numInt=numOutEdges=0;
  69. currNode=nodes.end();
  70. next=0;
  71. }
  72. void appendNodeInt(queue &pqH, BB *node);
  73. };
  74. /* Derived Sequence structure */
  75. struct derSeq_Entry
  76. {
  77. BB * Gi; /* Graph pointer */
  78. std::list<interval *> m_intervals;
  79. interval * Ii; /* Interval list of Gi */
  80. derSeq_Entry() : Gi(0),Ii(0)
  81. {
  82. }
  83. ~derSeq_Entry();
  84. public:
  85. void findIntervals(Function *c);
  86. };
  87. class derSeq : public std::list<derSeq_Entry>
  88. {
  89. public:
  90. void display();
  91. };
  92. void freeDerivedSeq(derSeq &derivedG); /* reducible.c */