graph.h 2.9 KB

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