123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143 |
- /* $Id$ */
- /*
- * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
- * See the copyright notice in the ACK home directory, in the file "Copyright".
- */
- /* C O N T R O L F L O W
- *
- * C F _ I D O M . C
- */
- #include "../share/types.h"
- #include "../share/debug.h"
- #include "../share/lset.h"
- #include "../share/alloc.h"
- #include "cf.h"
- /* The algorithm for finding dominators in a flowgraph
- * that is used here, was developed by Thomas Lengauer
- * and Robert E. Tarjan of Stanford University.
- * The algorithm is described in their article:
- * A Fast Algorithm for Finding Dominators
- * in a Flowgraph
- * which was published in:
- * ACM Transactions on Programming Languages and Systems,
- * Vol. 1, No. 1, July 1979, Pages 121-141.
- */
- #define UNREACHABLE(b) (b->B_SEMI == (short) 0)
- short dfs_nr;
- bblock_p *vertex; /* dynamically allocated array */
- STATIC dfs(v)
- bblock_p v;
- {
- /* Depth First Search */
- Lindex i;
- bblock_p w;
- v->B_SEMI = ++dfs_nr;
- vertex[dfs_nr] = v->B_LABEL = v;
- v->B_ANCESTOR = (bblock_p) 0;
- for (i = Lfirst(v->b_succ); i != (Lindex) 0; i = Lnext(i,v->b_succ)) {
- w = (bblock_p) Lelem(i);
- if (w->B_SEMI == 0) {
- w->B_PARENT = v;
- dfs(w);
- }
- }
- }
- STATIC compress(v)
- bblock_p v;
- {
- if (v->B_ANCESTOR->B_ANCESTOR != (bblock_p) 0) {
- compress(v->B_ANCESTOR);
- if (v->B_ANCESTOR->B_LABEL->B_SEMI < v->B_LABEL->B_SEMI) {
- v->B_LABEL = v->B_ANCESTOR->B_LABEL;
- }
- v->B_ANCESTOR = v->B_ANCESTOR->B_ANCESTOR;
- }
- }
- STATIC bblock_p eval(v)
- bblock_p v;
- {
- if (v->B_ANCESTOR == (bblock_p) 0) {
- return v;
- } else {
- compress(v);
- return v->B_LABEL;
- }
- }
- STATIC linkblocks(v,w)
- bblock_p v,w;
- {
- w->B_ANCESTOR = v;
- }
- dominators(r,n)
- bblock_p r;
- short n;
- {
- /* Compute the immediate dominator of every basic
- * block in the control flow graph rooted by r.
- */
- register short i;
- Lindex ind, next;
- bblock_p v,w,u;
- dfs_nr = 0;
- vertex = (bblock_p *) newmap(n);
- /* allocate vertex (dynamic array). All remaining
- * initializations were done by the routine
- * nextblock of get.c.
- */
- dfs(r);
- for (i = dfs_nr; i > 1; i--) {
- w = vertex[i];
- for (ind = Lfirst(w->b_pred); ind != (Lindex) 0;
- ind = Lnext(ind,w->b_pred)) {
- v = (bblock_p) Lelem(ind);
- if (UNREACHABLE(v)) continue;
- u = eval(v);
- if (u->B_SEMI < w->B_SEMI) {
- w->B_SEMI = u->B_SEMI;
- }
- }
- Ladd(w,&(vertex[w->B_SEMI]->B_BUCKET));
- linkblocks(w->B_PARENT,w);
- for (ind = Lfirst(w->B_PARENT->B_BUCKET); ind != (Lindex) 0;
- ind = next) {
- next = Lnext(ind,w->B_PARENT->B_BUCKET);
- v = (bblock_p) Lelem(ind);
- Lremove(v,&w->B_PARENT->B_BUCKET);
- u = eval(v);
- v->b_idom = (u->B_SEMI < v->B_SEMI ? u : w->B_PARENT);
- }
- }
- for (i = 2; i <= dfs_nr; i++) {
- w = vertex[i];
- if (w->b_idom != vertex[w->B_SEMI]) {
- w->b_idom = w->b_idom->b_idom;
- }
- }
- r->b_idom = (bblock_p) 0;
- oldmap(vertex,n); /* release memory for dynamic array vertex */
- }
|