graph.h 3.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899
  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=0; /* # of the interval */
  61. uint8_t numOutEdges=0; /* Number of out edges */
  62. queue nodes; /* Nodes of the interval*/
  63. queue::iterator currNode; /* Current node */
  64. interval * next=0; /* Next interval */
  65. BB * firstOfInt();
  66. interval() : currNode(nodes.end()){
  67. }
  68. void appendNodeInt(queue &pqH, BB *node);
  69. };
  70. /* Derived Sequence structure */
  71. struct derSeq_Entry
  72. {
  73. BB * Gi=nullptr; /* Graph pointer */
  74. std::list<interval *> m_intervals;
  75. interval * Ii=nullptr; /* Interval list of Gi */
  76. ~derSeq_Entry();
  77. public:
  78. void findIntervals(Function *c);
  79. };
  80. class derSeq : public std::list<derSeq_Entry>
  81. {
  82. public:
  83. void display();
  84. };
  85. void freeDerivedSeq(derSeq &derivedG); /* reducible.c */