cf_idom.c 2.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138
  1. /* C O N T R O L F L O W
  2. *
  3. * C F _ I D O M . C
  4. */
  5. #include "../share/types.h"
  6. #include "../share/debug.h"
  7. #include "../share/lset.h"
  8. #include "../share/alloc.h"
  9. #include "cf.h"
  10. /* The algorithm for finding dominators in a flowgraph
  11. * that is used here, was developed by Thomas Lengauer
  12. * and Robert E. Tarjan of Stanford University.
  13. * The algorithm is described in their article:
  14. * A Fast Algorithm for Finding Dominators
  15. * in a Flowgraph
  16. * which was published in:
  17. * ACM Transactions on Programming Languages and Systems,
  18. * Vol. 1, No. 1, July 1979, Pages 121-141.
  19. */
  20. #define UNREACHABLE(b) (b->B_SEMI == (short) 0)
  21. short dfs_nr;
  22. bblock_p *vertex; /* dynamically allocated array */
  23. STATIC dfs(v)
  24. bblock_p v;
  25. {
  26. /* Depth First Search */
  27. Lindex i;
  28. bblock_p w;
  29. v->B_SEMI = ++dfs_nr;
  30. vertex[dfs_nr] = v->B_LABEL = v;
  31. v->B_ANCESTOR = (bblock_p) 0;
  32. for (i = Lfirst(v->b_succ); i != (Lindex) 0; i = Lnext(i,v->b_succ)) {
  33. w = (bblock_p) Lelem(i);
  34. if (w->B_SEMI == 0) {
  35. w->B_PARENT = v;
  36. dfs(w);
  37. }
  38. }
  39. }
  40. STATIC compress(v)
  41. bblock_p v;
  42. {
  43. if (v->B_ANCESTOR->B_ANCESTOR != (bblock_p) 0) {
  44. compress(v->B_ANCESTOR);
  45. if (v->B_ANCESTOR->B_LABEL->B_SEMI < v->B_LABEL->B_SEMI) {
  46. v->B_LABEL = v->B_ANCESTOR->B_LABEL;
  47. }
  48. v->B_ANCESTOR = v->B_ANCESTOR->B_ANCESTOR;
  49. }
  50. }
  51. STATIC bblock_p eval(v)
  52. bblock_p v;
  53. {
  54. if (v->B_ANCESTOR == (bblock_p) 0) {
  55. return v;
  56. } else {
  57. compress(v);
  58. return v->B_LABEL;
  59. }
  60. }
  61. STATIC linkblocks(v,w)
  62. bblock_p v,w;
  63. {
  64. w->B_ANCESTOR = v;
  65. }
  66. dominators(r,n)
  67. bblock_p r;
  68. short n;
  69. {
  70. /* Compute the immediate dominator of every basic
  71. * block in the control flow graph rooted by r.
  72. */
  73. register short i;
  74. Lindex ind, next;
  75. bblock_p v,w,u;
  76. dfs_nr = 0;
  77. vertex = (bblock_p *) newmap(n);
  78. /* allocate vertex (dynamic array). All remaining
  79. * initializations were done by the routine
  80. * nextblock of get.c.
  81. */
  82. dfs(r);
  83. for (i = dfs_nr; i > 1; i--) {
  84. w = vertex[i];
  85. for (ind = Lfirst(w->b_pred); ind != (Lindex) 0;
  86. ind = Lnext(ind,w->b_pred)) {
  87. v = (bblock_p) Lelem(ind);
  88. if (UNREACHABLE(v)) continue;
  89. u = eval(v);
  90. if (u->B_SEMI < w->B_SEMI) {
  91. w->B_SEMI = u->B_SEMI;
  92. }
  93. }
  94. Ladd(w,&(vertex[w->B_SEMI]->B_BUCKET));
  95. linkblocks(w->B_PARENT,w);
  96. for (ind = Lfirst(w->B_PARENT->B_BUCKET); ind != (Lindex) 0;
  97. ind = next) {
  98. next = Lnext(ind,w->B_PARENT->B_BUCKET);
  99. v = (bblock_p) Lelem(ind);
  100. Lremove(v,&w->B_PARENT->B_BUCKET);
  101. u = eval(v);
  102. v->b_idom = (u->B_SEMI < v->B_SEMI ? u : w->B_PARENT);
  103. }
  104. }
  105. for (i = 2; i <= dfs_nr; i++) {
  106. w = vertex[i];
  107. if (w->b_idom != vertex[w->B_SEMI]) {
  108. w->b_idom = w->b_idom->b_idom;
  109. }
  110. }
  111. r->b_idom = (bblock_p) 0;
  112. oldmap(vertex,n); /* release memory for dynamic array vertex */
  113. }