util/ego/cf/cf_loop.c

   1 /* $Id: cf_loop.c,v 1.4 1994/06/24 10:20:23 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 /*  C O N T R O L   F L O W
   7  *
   8  *  C F _ L O O P . C
   9  */
  10
  11
  12 #include "../share/types.h"
  13 #include "../share/debug.h"
  14 #include "../share/lset.h"
  15 #include "../share/alloc.h"
  16 #include "../share/aux.h"
  17 #include "cf.h"
  18
  19 #define MARK_STRONG(b)  b->b_flags |= BF_STRONG
  20 #define MARK_FIRM(b)    b->b_flags |= BF_FIRM
  21 #define BF_MARK         04
  22 #define MARK(b)         b->b_flags |= BF_MARK
  23 #define MARKED(b)       (b->b_flags&BF_MARK)
  24 #define INSIDE_LOOP(b,lp)  Lis_elem(b,lp->LP_BLOCKS)
  25
  26
  27
  28 /* The algorithm to detect loops that is used here is taken
  29  * from: Aho & Ullman, Principles of Compiler Design, section 13.1.
  30  * The algorithm uses the dominator relation between nodes
  31  * of the control flow graph:
  32  *  d DOM n => every path from the initial node to n goes through d.
  33  * The dominator relation is recorded via the immediate dominator tree
  34  * (b_idom field of bblock struct) from which the dominator relation
  35  * can be easily computed (see procedure 'dom' below).
  36  * The algorithm first finds 'back edges'. A back edge is an edge
  37  * a->b in the flow graph whose head (b) dominates its tail (a).
  38  * The 'natural loop' of back edge n->d consists of those nodes
  39  * that can reach n without going through d. These nodes, plus d
  40  * form the loop.
  41  * The whole process is rather complex, because different back edges
  42  * may result in the same loop and because loops may partly overlap
  43  * each other (without one being nested inside the other).
  44  */
  45
  46
  47
  48 STATIC bool same_loop(l1,l2)
  49         loop_p l1,l2;
  50 {
  51         /* Two loops are the same if:
  52          * (1)  they have the same number of basic blocks, and
  53          * (2)  the head of the back edge of the first loop
  54          *      also is part of the second loop, and
  55          * (3)  the tail of the back edge of the first loop
  56          *      also is part of the second loop.
  57          */
  58
  59         return (l1->LP_COUNT == l2->LP_COUNT &&
  60                 Lis_elem(l1->lp_entry, l2->LP_BLOCKS) &&
  61                 Lis_elem(l1->lp_end,   l2->LP_BLOCKS));
  62 }
  63
  64
  65
  66 STATIC bool inner_loop(l1,l2)
  67         loop_p l1,l2;
  68 {
  69         /* Loop l1 is an inner loop of l2 if:
  70          * (1)  the first loop has fewer basic blocks than
  71          *      the second one, and
  72          * (2)  the head of the back edge of the first loop
  73          *      also is part of the second loop, and
  74          * (3)  the tail of the back edge of the first loop
  75          *      also is part of the second loop.
  76          */
  77
  78         return (l1->LP_COUNT < l2->LP_COUNT &&
  79                 Lis_elem(l1->lp_entry, l2->LP_BLOCKS) &&
  80                 Lis_elem(l1->lp_end,   l2->LP_BLOCKS));
  81 }
  82
  83
  84
  85 STATIC insrt(b,lpb,s_p)
  86         bblock_p b;
  87         lset *lpb;
  88         lset *s_p;
  89 {
  90         /* Auxiliary routine used by 'natural_loop'.
  91          * Note that we use a set rather than a stack,
  92          * as Aho & Ullman do.
  93          */
  94
  95         if (!Lis_elem(b,*lpb)) {
  96                 Ladd(b,lpb);
  97                 Ladd(b,s_p);
  98         }
  99 }
 100
 101
 102 STATIC loop_p natural_loop(d,n)
 103         bblock_p d,n;
 104 {
 105         /* Find the basic blocks of the natural loop of the
 106          * back edge 'n->d' (i.e. n->d is an edge in the control
 107          * flow graph and d dominates n). The natural loop consists
 108          * of those blocks which can reach n without going through d.
 109          * We find these blocks by finding all predecessors of n,
 110          * up to d.
 111          */
 112
 113         loop_p lp;
 114         bblock_p m;
 115         lset loopblocks;
 116         Lindex pi;
 117         lset s;
 118
 119         lp = newloop();
 120         lp->lp_extend = newcflpx();
 121         lp->lp_entry = d;       /* loop entry block */
 122         lp->lp_end = n;         /* tail of back edge */
 123         s = Lempty_set();
 124         loopblocks = Lempty_set();
 125         Ladd(d,&loopblocks);
 126         insrt(n,&loopblocks,&s);
 127         while ((pi = Lfirst(s)) != (Lindex) 0) {
 128                 m = (bblock_p) Lelem(pi);
 129                 Lremove(m,&s);
 130                 for (pi = Lfirst(m->b_pred); pi != (Lindex) 0;
 131                                         pi = Lnext(pi,m->b_pred)) {
 132                         insrt((bblock_p) Lelem(pi),&loopblocks,&s);
 133                 }
 134         }
 135         lp->LP_BLOCKS = loopblocks;
 136         lp->LP_COUNT = Lnrelems(loopblocks);
 137         return lp;
 138 }
 139
 140
 141 STATIC loop_p org_loop(lp,loops)
 142         loop_p lp;
 143         lset   loops;
 144 {
 145         /* See if the loop lp was already found via another
 146          * back edge; if so return this loop; else return 0.
 147          */
 148
 149         register Lindex li;
 150
 151         for (li = Lfirst(loops); li != (Lindex) 0; li = Lnext(li,loops)) {
 152                 if (same_loop((loop_p) Lelem(li), lp)) {
 153 #ifdef DEBUG
 154                         /* printf("messy loop found\n"); */
 155 #endif
 156                         return (loop_p) Lelem(li);
 157                 }
 158         }
 159         return (loop_p) 0;
 160 }
 161
 162
 163
 164 STATIC collapse_loops(loops_p)
 165         lset *loops_p;
 166 {
 167         register Lindex li1, li2;
 168         register loop_p lp1,lp2;
 169
 170         for (li1 = Lfirst(*loops_p); li1 != (Lindex) 0; li1 = Lnext(li1,*loops_p)) {
 171                 lp1 = (loop_p) Lelem(li1);
 172                 lp1->lp_level = (short) 0;
 173                 for (li2 = Lfirst(*loops_p); li2 != (Lindex) 0;
 174                                         li2 = Lnext(li2,*loops_p)) {
 175                         lp2 = (loop_p) Lelem(li2);
 176                         if (lp1 != lp2 && lp1->lp_entry == lp2->lp_entry) {
 177                             Ljoin(lp2->LP_BLOCKS,&lp1->LP_BLOCKS);
 178                             oldcflpx(lp2->lp_extend);
 179                             Lremove(lp2,loops_p);
 180                         }
 181                 }
 182         }
 183 }
 184
 185
 186 STATIC loop_per_block(lp)
 187         loop_p lp;
 188 {
 189         bblock_p b;
 190
 191         /* Update the b_loops sets */
 192
 193         register Lindex bi;
 194
 195         for (bi = Lfirst(lp->LP_BLOCKS); bi != (Lindex) 0;
 196                 bi = Lnext(bi,lp->LP_BLOCKS)) {
 197                         b = (bblock_p) Lelem(bi);
 198                         Ladd(lp,&(b->b_loops));
 199         }
 200 }
 201
 202
 203
 204 STATIC loop_attrib(loops)
 205         lset loops;
 206 {
 207         /* Compute several attributes */
 208
 209         register Lindex li;
 210         register loop_p lp;
 211         loop_id lastlpid = 0;
 212
 213         for (li = Lfirst(loops); li != (Lindex) 0; li = Lnext(li,loops)) {
 214                 lp = (loop_p) Lelem(li);
 215                 lp->lp_id = ++lastlpid;
 216                 loop_per_block(lp);
 217         }
 218 }
 219
 220
 221
 222 STATIC nest_levels(loops)
 223         lset loops;
 224 {
 225         /* Compute the nesting levels of all loops of
 226          * the current procedure. For every loop we just count
 227          * all loops of which the former is an inner loop.
 228          * The running time is quadratic in the number of loops
 229          * of the current procedure. As this number tends to be
 230          * very small, there is no cause for alarm.
 231          */
 232
 233         register Lindex li1, li2;
 234         register loop_p lp;
 235
 236         for (li1 = Lfirst(loops); li1 != (Lindex) 0; li1 = Lnext(li1,loops)) {
 237                 lp = (loop_p) Lelem(li1);
 238                 lp->lp_level = (short) 0;
 239                 for (li2 = Lfirst(loops); li2 != (Lindex) 0;
 240                                         li2 = Lnext(li2,loops)) {
 241                         if (inner_loop(lp,(loop_p) Lelem(li2))) {
 242                                 lp->lp_level++;
 243                         }
 244                 }
 245         }
 246 }
 247
 248
 249 STATIC cleanup(loops)
 250         lset loops;
 251 {
 252         /* Throw away the LP_BLOCKS sets */
 253
 254         register Lindex i;
 255
 256         for (i = Lfirst(loops); i != (Lindex) 0; i = Lnext(i,loops)) {
 257                 Ldeleteset(((loop_p) Lelem(i))->LP_BLOCKS);
 258         }
 259 }
 260
 261
 262 STATIC bool does_exit(b,lp)
 263         bblock_p b;
 264         loop_p   lp;
 265 {
 266         /* See if b may exit the loop, i.e. if it
 267          * has a successor outside the loop
 268          */
 269
 270         Lindex i;
 271
 272         for (i = Lfirst(b->b_succ); i != (Lindex) 0; i = Lnext(i,b->b_succ)) {
 273                 if (!INSIDE_LOOP(Lelem(i),lp)) return TRUE;
 274         }
 275         return FALSE;
 276 }
 277
 278
 279 STATIC mark_succ(b,lp)
 280         bblock_p b;
 281         loop_p   lp;
 282 {
 283         Lindex i;
 284         bblock_p succ;
 285
 286         for (i = Lfirst(b->b_succ); i != (Lindex) 0; i = Lnext(i,b->b_succ)) {
 287                 succ = (bblock_p) Lelem(i);
 288                 if (succ != b && succ != lp->lp_entry && INSIDE_LOOP(succ,lp) &&
 289                    !MARKED(succ)) {
 290                         MARK(succ);
 291                         mark_succ(succ,lp);
 292                 }
 293         }
 294 }
 295
 296
 297 STATIC mark_blocks(lp)
 298         loop_p lp;
 299 {
 300         /* Mark the strong and firm blocks of a loop.
 301          * The last set of blocks consists of the end-block
 302          * of the loop (i.e. the head of the back edge
 303          * of the natural loop) and its dominators
 304          * (including the loop entry block, i.e. the
 305          * tail of the back edge).
 306          */
 307
 308         register bblock_p b;
 309
 310         /* First mark all blocks that are the successor of a
 311          * block that may exit the loop (i.e. contains a
 312          * -possibly conditional- jump to somewhere outside
 313          * the loop.
 314          */
 315
 316         if (lp->LP_MESSY) return; /* messy loops are hopeless cases */
 317         for (b = lp->lp_entry; b != (bblock_p) 0; b = b->b_next) {
 318                 if (!MARKED(b) && does_exit(b,lp)) {
 319                         mark_succ(b,lp);
 320                 }
 321         }
 322
 323         /* Now find all firm blocks. A block is strong
 324          * if it is firm and not marked.
 325          */
 326
 327         for (b = lp->lp_end; ; b = b->b_idom) {
 328                 MARK_FIRM(b);
 329                 if (!MARKED(b)) {
 330                         MARK_STRONG(b);
 331                 }
 332                 if (b == lp->lp_entry) break;
 333         }
 334 }
 335
 336
 337
 338 STATIC mark_loopblocks(loops)
 339         lset loops;
 340 {
 341         /* Determine for all loops which basic blocks
 342          * of the loop are strong (i.e. are executed
 343          * during every iteration) and which blocks are
 344          * firm (i.e. executed during every iteration with
 345          * the only possible exception of the last one).
 346          */
 347
 348         Lindex i;
 349         loop_p lp;
 350
 351         for (i = Lfirst(loops); i != (Lindex) 0; i = Lnext(i,loops)) {
 352                 lp = (loop_p) Lelem(i);
 353                 mark_blocks(lp);
 354         }
 355 }
 356
 357
 358
 359 loop_detection(p)
 360         proc_p p;
 361 {
 362         /* Find all natural loops of procedure p. Every loop is
 363          * assigned a unique identifying number, a set of basic
 364          * blocks, a loop entry block and a nesting level number.
 365          * Every basic block is assigned a nesting level number
 366          * and a set of loops it is part of.
 367          */
 368
 369         lset loops;  /* the set of all loops */
 370         loop_p lp,org;
 371         register bblock_p b;
 372         bblock_p s;
 373         Lindex si;
 374
 375         loops = Lempty_set();
 376         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 377                 for (si = Lfirst(b->b_succ); si != (Lindex) 0;
 378                                                 si = Lnext(si,b->b_succ)) {
 379                         s = (bblock_p) Lelem(si);
 380                         if (dom(s,b)) {
 381                                 /* 'b->s' is a back edge */
 382                                 lp = natural_loop(s,b);
 383                                 if ((org = org_loop(lp,loops)) == (loop_p) 0) {
 384                                    /* new loop */
 385                                    Ladd(lp,&loops);
 386                                 } else {
 387                                    /* Same loop, generated by several back
 388                                     * edges; such a loop is called a messy
 389                                     * loop.
 390                                     */
 391                                    org->LP_MESSY = TRUE;
 392                                    Ldeleteset(lp->LP_BLOCKS);
 393                                    oldcflpx(lp->lp_extend);
 394                                    oldloop(lp);
 395                                 }
 396                         }
 397                 }
 398         }
 399         collapse_loops(&loops);
 400         loop_attrib(loops);
 401         nest_levels(loops);
 402         mark_loopblocks(loops); /* determine firm and strong blocks */
 403         cleanup(loops);
 404         p->p_loops = loops;
 405 }