graph.h 3.0 KB

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