ra_interv.c 4.4 KB

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