util/ego/ra/ra_interv.c

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