cf_idom.c 2.9 KB

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