narray/loop.c

   1 /* loop.c **********************************************************************
   2
   3         Copyright (c) 1997 A. Krall, R. Grafl, M. Gschwind, M. Probst
   4
   5         See file COPYRIGHT for information on usage and disclaimer of warranties.
   6
   7         Contains the functions which use the control flow graph to do loop detection.
   8                 The loop detection is performed according to Lengauer-Tarjan algorithm
   9                 that uses dominator trees (found eg. in modern compiler implementation
  10                 by a.w. appel)
  11
  12         Authors: Christopher Kruegel      EMAIL: cacao@complang.tuwien.ac.at
  13
  14         Last Change: 1998/17/02
  15
  16 *******************************************************************************/
  17
  18 /*      This function allocates and initializes variables, that are used by the
  19          loop detection algorithm
  20 */
  21 void setup()
  22 {
  23         int i;
  24
  25         c_semi_dom = (int *) malloc(block_count * sizeof(int));
  26         c_idom = (int *) malloc(block_count * sizeof(int));
  27         c_same_dom = (int *) malloc(block_count * sizeof(int));
  28         c_numBucket = (int *) malloc(block_count * sizeof(int));
  29         c_ancestor = (int *) malloc(block_count * sizeof(int));
  30         c_contains = (int *) malloc(block_count * sizeof(int));
  31         c_stack = (int *) malloc(block_count * sizeof(int));
  32
  33         c_bucket = (int **) malloc(block_count * sizeof(int *));
  34
  35         for (i=0; i<block_count; ++i) {
  36                 c_numBucket[i] = 0;
  37                 c_stack[i] = c_ancestor[i] = c_semi_dom[i] = c_same_dom[i] = c_idom[i] = -1;
  38
  39                 c_bucket[i] = (int *) malloc(block_count * sizeof(int));
  40                 }
  41 }
  42
  43 /*      This function is a helper function for dominators and has to find the
  44         ancestor of the node v in the control graph, which semi-dominator has the
  45         lowest def-num.
  46 */
  47 int findLowAnc(int v)
  48 {
  49         int u = v;                      /* u is the node which has the current lowest semi-dom  */
  50
  51         while (c_ancestor[v] != -1) {   /* as long as v has an ancestor, continue       */
  52                 if (c_defnum[c_semi_dom[v]] < c_defnum[c_semi_dom[u]])
  53                                                                         /* if v's semi-dom is smaller                           */
  54                         u = v;                                  /* it gets the new current node u                       */
  55                 v = c_ancestor[v];                      /* climb one step up in the tree                        */
  56                 }
  57         return u;                       /* return node with the lowest semi-dominator def-num   */
  58 }
  59
  60
  61 /*      This function builds the dominator tree out of a given control flow graph and
  62         stores its results in c_idom[]. It first calculates the number of possible
  63         dominators in c_bucket and eventually determines the single dominator in a
  64         final pass.
  65 */
  66 void dominators()
  67 {
  68         int i, j, semi, s, n, v, actual, p, y;
  69
  70         for (n=(c_globalCount-1); n>0; --n) {   /* for all nodes (except last), do      */
  71                 actual = c_reverse[n];
  72                 semi = p = c_parent[actual];
  73
  74                 /* for all predecessors of current node, do                                                             */
  75                 for (i=0; i<c_numPre[actual]; ++i) {
  76                         v = c_pre[actual][i];
  77
  78                         if (c_defnum[v] <= c_defnum[actual])
  79                                 s = v;                  /* if predecessor has lower def-num     than node       */
  80                                                                 /* it becomes candidate for semi dominator              */
  81                         else
  82                                 s = c_semi_dom[findLowAnc(v)];
  83                                                                 /* else the semi-dominator of it's ancestor             */
  84                                                                 /* with lowest def-num becomes candidate                */
  85
  86                         if (c_defnum[s] < c_defnum[semi])
  87                                 semi = s;               /* if the def-num of the new candidate is lower */
  88                                                                 /* than old one, it gets new semi dominator             */
  89                         }
  90
  91                 /* write semi dominator -> according to SEMIDOMINATOR THEOREM                   */
  92                 c_semi_dom[actual] = semi;
  93                 c_ancestor[actual] = p;
  94
  95                 c_bucket[semi][c_numBucket[semi]] = actual;
  96                 c_numBucket[semi]++;    /* defer calculation of dominator to final pass */
  97
  98
  99                 /* first clause of DOMINATOR THEOREM, try to find dominator now                 */
 100                 for (j=0; j<c_numBucket[p]; ++j) {
 101                         v = c_bucket[p][j];
 102                         y = findLowAnc(v);
 103
 104                         if (c_semi_dom[y] == c_semi_dom[v])
 105                                 c_idom[v] = p;                  /* if y's dominator is already known    */
 106                                                                                 /* found it and write to c_idom                 */
 107                         else
 108                                 c_same_dom[v] = y;              /* wait till final pass                                 */
 109                         }
 110
 111                 c_numBucket[p] = 0;
 112                 }
 113
 114         /* final pass to get missing dominators ->second clause of DOMINATOR THEORM     */
 115         for (j=1; j<(c_globalCount-1); ++j) {
 116                 if (c_same_dom[c_reverse[j]] != -1)
 117                         c_idom[c_reverse[j]] = c_idom[c_same_dom[c_reverse[j]]];
 118                 }
 119 }
 120
 121 /*      A helper function needed by detectLoops() that checks, whether a given
 122         connection between two nodes in the control flow graph is possibly part
 123         of a loop (is a backEdge).
 124 */
 125 int isBackEdge(int from, int to)
 126 {
 127         int tmp = c_idom[to];   /* speed optimization: if the to-node is dominated      */
 128         while (tmp != -1) {             /* by the from node as it is most of the time,          */
 129                 if (tmp == from)        /* there is no backEdge                                                         */
 130                         return 0;
 131                 tmp = c_idom[tmp];
 132                 }
 133
 134         tmp = c_idom[from];             /* if from-node doesn't dominate to-node, we have       */
 135         while (tmp != -1) {             /* to climb all the way up from the from-node to        */
 136                 if (tmp == to)          /* the top to check, whether it is dominated by to      */
 137                         return 1;               /* if so, return a backedge                                                     */
 138                 tmp = c_idom[tmp];
 139                 }
 140
 141         return 0;                               /* else, there is no backedge                                           */
 142 }
 143
 144
 145 /*      These stack functions are helper functions for createLoop(int, int)
 146         to manage the set of nodes in the current loop.
 147 */
 148 void push(int i, struct LoopContainer *lc)
 149 {
 150         struct LoopElement *le = lc->nodes, *t;
 151
 152         if (!c_contains[i])
 153         {
 154                 t = DMNEW(struct LoopElement, 1);
 155
 156                 t->node = i;
 157                 t->block = &block[i];
 158
 159                 c_contains[i] = 1;
 160
 161                 if (i < le->node)
 162                 {
 163                         t->next = lc->nodes;
 164                         lc->nodes = t;
 165                 }
 166                 else
 167                 {
 168                         while ((le->next != NULL) && (le->next->node < i))
 169                                 le = le->next;
 170
 171                         t->next = le->next;
 172                         le->next = t;
 173                 }
 174
 175                 c_stack[c_stackPointer++] = i;
 176         }
 177 }
 178 int pop()
 179 {
 180         return (c_stack[--c_stackPointer]);
 181 }
 182 int isFull()
 183 {
 184         return (c_stackPointer);
 185 }
 186
 187
 188 /*      This function is a helper function, that finds all nodes, that belong to
 189         the loop with a known header node and a member node of the loop (and a
 190         back edge between these two nodes).
 191 */
 192 void createLoop(int header, int member)
 193 {
 194         int i, nextMember;
 195
 196         struct LoopContainer *currentLoop = (struct LoopContainer *) malloc(sizeof(struct LoopContainer));
 197         LoopContainerInit(currentLoop, header);         /* set up loop structure                */
 198
 199         for (i=0; i<block_count; ++i)
 200                 c_contains[i] = 0;
 201         c_contains[header] = 1;
 202
 203         c_stackPointer = 0;                             /* init stack with first node of the loop       */
 204         push(member, currentLoop);
 205
 206         while (isFull()) {                              /* while there are still unvisited nodes        */
 207                 nextMember = pop();
 208
 209                 /* push all predecessors, while they are not equal to loop header               */
 210                 for (i=0; i<c_numPre[nextMember]; ++i)
 211                         push(c_pre[nextMember][i], currentLoop);
 212                 }
 213
 214         currentLoop->next = c_allLoops;
 215         c_allLoops = currentLoop;
 216 }
 217
 218
 219 /*      After all dominators have been calculated, the loops can be detected and
 220          added to the global list c_allLoops.
 221 */
 222 void detectLoops()
 223 {
 224         int i;
 225         struct depthElement *h;
 226
 227         /* for all edges in the control flow graph do                                                           */
 228         for (i=0; i<block_count; ++i) {
 229                 h = c_dTable[i];
 230
 231                 while (h != NULL) {
 232                         /* if it's a backedge, than add a new loop to list                                      */
 233                         if (isBackEdge(i, h->value))
 234                                 createLoop(h->value, i);
 235                         h = h->next;
 236                         }
 237                 }
 238 }
 239
 240 /*      This function is called by higher level routines to perform the loop
 241         detection and set up the c_allLoops list.
 242 */
 243 void analyseGraph()
 244 {
 245   setup();
 246   dominators();
 247   detectLoops();
 248 }
 249
 250 /*      Test function -> will be removed in final release
 251 */
 252 void resultPass2()
 253 {
 254   int i, j;
 255   struct LoopContainer *lc = c_allLoops;
 256   struct LoopElement *le;
 257
 258   printf("\n\n****** PASS 2 ******\n\n");
 259
 260   printf("Loops:\n\n");
 261
 262   j=0;
 263   while (lc != NULL) {
 264           printf("Loop [%d]: ", ++j);
 265
 266           le = lc->nodes;
 267           while (le != NULL) {
 268             printf("%d ", le->node);
 269                 printf("\n");
 270                 le = le->next;
 271           }
 272
 273           lc = lc->next;
 274   }
 275
 276   printf("\n");
 277
 278 }
 279 /*
 280  * These are local overrides for various environment variables in Emacs.
 281  * Please do not remove this and leave it at the end of the file, where
 282  * Emacs will automagically detect them.
 283  * ---------------------------------------------------------------------
 284  * Local variables:
 285  * mode: c
 286  * indent-tabs-mode: t
 287  * c-basic-offset: 4
 288  * tab-width: 4
 289  * End:
 290  */
 291
 292
 293