ra_interv.c 4.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222
  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. /* R E G I S T E R A L L O C A T I O N
  7. *
  8. * R A _ I N T E R V A L . C
  9. */
  10. #include <em_reg.h>
  11. #include "../share/types.h"
  12. #include "../share/debug.h"
  13. #include "../share/global.h"
  14. #include "../share/alloc.h"
  15. #include "../share/lset.h"
  16. #include "ra.h"
  17. #include "ra_interv.h"
  18. interv_p cons_interval(short t_start, short t_stop)
  19. {
  20. interv_p x;
  21. x = newinterval();
  22. x->i_start = t_start;
  23. x->i_stop = t_stop;
  24. return x;
  25. }
  26. void add_interval(short t1, short t2, interv_p *list)
  27. {
  28. /* Add interval (t1,t2) to the list of intervals (which is
  29. * an in-out parameter!). The list is sorted in 'chronological'
  30. * order. We attempt to keep the list as small as possible, by
  31. * putting adjacent intervals in one interval.
  32. */
  33. interv_p x1, x2, *q;
  34. int adjacent = 0;
  35. interv_p x;
  36. q = list;
  37. x1 = (interv_p) 0;
  38. for (x2 = *list; x2 != (interv_p) 0; x2 = x2->i_next) {
  39. if (t2 < x2->i_start) break;
  40. x1 = x2;
  41. q = &x2->i_next;
  42. }
  43. /* Now interval (t1,t2) should be inserted somewhere in between
  44. * x1 and x2.
  45. */
  46. if (x1 != (interv_p) 0 && t1 == x1->i_stop + 1) {
  47. /* join x1 and (t1,t2) */
  48. x1->i_stop = t2;
  49. adjacent++;
  50. }
  51. if (x2 != (interv_p) 0 && t2 + 1 == x2->i_start) {
  52. /* join (t1,t2) and x2 */
  53. x2->i_start = t1;
  54. adjacent++;
  55. }
  56. if (adjacent == 0) {
  57. /* no adjacents, allocate a new intervalfor (t1,t2) */
  58. x = cons_interval(t1,t2);
  59. x->i_next = x2;
  60. *q = x;
  61. } else {
  62. if (adjacent == 2) {
  63. /* x1, (t1,t2) and x2 can be put in one interval */
  64. x1->i_stop = x2->i_stop;
  65. x1->i_next = x2->i_next;
  66. oldinterval(x2);
  67. }
  68. }
  69. }
  70. interv_p loop_lifetime(loop_p lp)
  71. {
  72. /* Determine the timespan of the loop, expressed as a list
  73. * of intervals.
  74. */
  75. interv_p lt = 0;
  76. bblock_p b;
  77. Lindex bi;
  78. for (bi = Lfirst(lp->LP_BLOCKS); bi != (Lindex) 0;
  79. bi = Lnext(bi,lp->LP_BLOCKS)) {
  80. b = (bblock_p) Lelem(bi);
  81. add_interval(b->B_BEGIN,b->B_END,&lt);
  82. }
  83. return lt;
  84. }
  85. interv_p proc_lifetime(proc_p p)
  86. {
  87. /* Determine the lifetime of an entire procedure */
  88. bblock_p b;
  89. for (b = p->p_start; b->b_next != (bblock_p) 0; b = b->b_next) ;
  90. return cons_interval(0,b->B_END);
  91. }
  92. static void set_min_max(interv_p *iv1, interv_p *iv2)
  93. {
  94. /* Auxiliary routine of intersect */
  95. interv_p i1 = *iv1, i2 = *iv2;
  96. if (i1->i_start < i2->i_start) {
  97. *iv1 = i1;
  98. *iv2 = i2;
  99. } else {
  100. *iv1 = i2;
  101. *iv2 = i1;
  102. }
  103. }
  104. interv_p intersect(interv_p list1, interv_p list2)
  105. {
  106. /* Intersect two lifetimes, each denoted by a list of intervals.
  107. * We maintain two pointers, pmin and pmax, pointing to the
  108. * next interval of each list. At any time, pmin points to the
  109. * interval of which i_start is lowest; pmax points to the
  110. * other interval (i.e. the next interval of the other list).
  111. */
  112. interv_p lt = 0;
  113. interv_p pmin,pmax;
  114. #define BUMP(p) p = p->i_next
  115. #define EMIT(t1,t2) add_interval(t1,t2,&lt)
  116. pmin = list1;
  117. pmax = list2;
  118. while (pmin != (interv_p) 0 && pmax != (interv_p) 0) {
  119. set_min_max(&pmin,&pmax);
  120. if (pmax->i_start > pmin->i_stop) {
  121. /* e.g. (5,7) and (9,13) */
  122. BUMP(pmin);
  123. } else {
  124. if (pmax->i_stop < pmin->i_stop) {
  125. /* e.g. (5,12) and (7,10) */
  126. EMIT(pmax->i_start,pmax->i_stop);
  127. BUMP(pmax);
  128. } else {
  129. /* e.g. (5,8) and (7,12) */
  130. EMIT(pmax->i_start,pmin->i_stop);
  131. if (pmax->i_stop == pmin->i_stop) {
  132. /* e.g. (5,12) and (7,12) */
  133. BUMP(pmax);
  134. }
  135. BUMP(pmin);
  136. }
  137. }
  138. }
  139. return lt;
  140. }
  141. bool not_disjoint(interv_p list1, interv_p list2)
  142. {
  143. /* See if list1 and list2 do overlap somewhere */
  144. interv_p pmin,pmax;
  145. pmin = list1;
  146. pmax = list2;
  147. while (pmin != (interv_p) 0 && pmax != (interv_p) 0) {
  148. set_min_max(&pmin,&pmax);
  149. if (pmax->i_start > pmin->i_stop) {
  150. /* e.g. (5,7) and (9,13) */
  151. BUMP(pmin);
  152. } else {
  153. return TRUE; /* not disjoint */
  154. }
  155. }
  156. return FALSE; /* disjoint */
  157. }
  158. bool contains(short t, interv_p timespan)
  159. {
  160. interv_p iv;
  161. for (iv = timespan; iv != (interv_p) 0; iv = iv->i_next) {
  162. if (t <= iv->i_stop) return (t >= iv->i_start);
  163. }
  164. return FALSE;
  165. }
  166. interv_p copy_timespan(interv_p list)
  167. {
  168. /* copy the time span */
  169. interv_p x,y,head,*p;
  170. head = (interv_p) 0;
  171. p = &head;
  172. for (x = list; x != (interv_p) 0; x = x->i_next) {
  173. y = cons_interval(x->i_start,x->i_stop);
  174. *p = y;
  175. p = &y->i_next;
  176. }
  177. return head;
  178. }