graph.h 3.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
  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_DISP=1, /* Display graph pass */
  29. DFS_MERGE=2, /* Merge nodes pass */
  30. DFS_NUM=3, /* DFS numbering pass */
  31. DFS_CASE=4, /* Case pass */
  32. DFS_ALPHA=5, /* Alpha code generation*/
  33. DFS_JMP=9 /* rmJMP pass - must be largest flag */
  34. };
  35. /* Control flow analysis constants */
  36. enum eNodeHeaderType
  37. {
  38. NO_TYPE=0, /* node is not a loop header*/
  39. WHILE_TYPE=1, /* node is a while header */
  40. REPEAT_TYPE=2, /* node is a repeat header */
  41. ENDLESS_TYPE=3 /* endless loop header */
  42. };
  43. /* Uninitialized values for certain fields */
  44. #define NO_NODE MAX /* node has no associated node */
  45. #define NO_DOM MAX /* node has no dominator */
  46. #define UN_INIT MAX /* uninitialized variable */
  47. #define THEN 0 /* then edge */
  48. #define ELSE 1 /* else edge */
  49. /* Basic Block (BB) flags */
  50. #define INVALID_BB 0x0001 /* BB is not valid any more */
  51. #define IS_LATCH_NODE 0x0002 /* BB is the latching node of a loop */
  52. struct BB;
  53. /* Interval structure */
  54. typedef std::list<BB *> queue;
  55. struct interval
  56. {
  57. byte numInt; /* # of the interval */
  58. byte numOutEdges; /* Number of out edges */
  59. queue nodes; /* Nodes of the interval*/
  60. queue::iterator currNode; /* Current node */
  61. interval *next; /* Next interval */
  62. BB *firstOfInt();
  63. interval()
  64. {
  65. numInt=numOutEdges=0;
  66. currNode=nodes.end();
  67. next=0;
  68. }
  69. };
  70. /* Derived Sequence structure */
  71. struct derSeq_Entry
  72. {
  73. BB * Gi; /* Graph pointer */
  74. interval * Ii; /* Interval list of Gi */
  75. derSeq_Entry() : Gi(0),Ii(0)
  76. {
  77. }
  78. ~derSeq_Entry();
  79. public:
  80. void findIntervals(Function *c);
  81. };
  82. class derSeq : public std::list<derSeq_Entry>
  83. {
  84. public:
  85. void display();
  86. };
  87. void freeDerivedSeq(derSeq &derivedG); /* reducible.c */