ra_interv.c 4.4 KB

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