123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224 |
- // SPDX-License-Identifier: MIT
- //
- // Various utilities for flowgraphs.
- //
- // Copyright (c) 2017 Luc Van Oostenryck.
- //
- #include "flowgraph.h"
- #include "linearize.h"
- #include "flow.h" // for bb_generation
- #include <assert.h>
- #include <stdio.h>
- #include <stdlib.h>
- struct cfg_info {
- struct basic_block_list *list;
- unsigned long gen;
- unsigned int nr;
- };
- static void label_postorder(struct basic_block *bb, struct cfg_info *info)
- {
- struct basic_block *child;
- if (bb->generation == info->gen)
- return;
- bb->generation = info->gen;
- FOR_EACH_PTR_REVERSE(bb->children, child) {
- label_postorder(child, info);
- } END_FOR_EACH_PTR_REVERSE(child);
- bb->postorder_nr = info->nr++;
- add_bb(&info->list, bb);
- }
- static void reverse_bbs(struct basic_block_list **dst, struct basic_block_list *src)
- {
- struct basic_block *bb;
- FOR_EACH_PTR_REVERSE(src, bb) {
- add_bb(dst, bb);
- } END_FOR_EACH_PTR_REVERSE(bb);
- }
- static void debug_postorder(struct entrypoint *ep)
- {
- struct basic_block *bb;
- printf("%s's reverse postorder:\n", show_ident(ep->name->ident));
- FOR_EACH_PTR(ep->bbs, bb) {
- printf("\t.L%u: %u\n", bb->nr, bb->postorder_nr);
- } END_FOR_EACH_PTR(bb);
- }
- //
- // cfg_postorder - Set the BB's reverse postorder links
- //
- // Do a postorder DFS walk and set the links
- // (which will do the reverse part).
- //
- int cfg_postorder(struct entrypoint *ep)
- {
- struct cfg_info info = {
- .gen = ++bb_generation,
- };
- label_postorder(ep->entry->bb, &info);
- // OK, now info.list contains the node in postorder
- // Reuse ep->bbs for the reverse postorder.
- free_ptr_list(&ep->bbs);
- ep->bbs = NULL;
- reverse_bbs(&ep->bbs, info.list);
- free_ptr_list(&info.list);
- if (dbg_postorder)
- debug_postorder(ep);
- return info.nr;
- }
- //
- // Calculate the dominance tree following:
- // "A simple, fast dominance algorithm"
- // by K. D. Cooper, T. J. Harvey, and K. Kennedy.
- // cfr. http://www.cs.rice.edu/∼keith/EMBED/dom.pdf
- //
- static struct basic_block *intersect_dom(struct basic_block *doms[],
- struct basic_block *b1, struct basic_block *b2)
- {
- int f1 = b1->postorder_nr, f2 = b2->postorder_nr;
- while (f1 != f2) {
- while (f1 < f2) {
- b1 = doms[f1];
- f1 = b1->postorder_nr;
- }
- while (f2 < f1) {
- b2 = doms[f2];
- f2 = b2->postorder_nr;
- }
- }
- return b1;
- }
- static void debug_domtree(struct entrypoint *ep)
- {
- struct basic_block *bb = ep->entry->bb;
- printf("%s's idoms:\n", show_ident(ep->name->ident));
- FOR_EACH_PTR(ep->bbs, bb) {
- if (bb == ep->entry->bb)
- continue; // entry node has no idom
- printf("\t%s <- %s\n", show_label(bb), show_label(bb->idom));
- } END_FOR_EACH_PTR(bb);
- }
- void domtree_build(struct entrypoint *ep)
- {
- struct basic_block *entry = ep->entry->bb;
- struct basic_block **doms;
- struct basic_block *bb;
- unsigned int size;
- int max_level = 0;
- int changed;
- // First calculate the (reverse) postorder.
- // This will give use us:
- // - the links to do a reverse postorder traversal
- // - the order number for each block
- size = cfg_postorder(ep);
- // initialize the dominators array
- doms = calloc(size, sizeof(*doms));
- assert(entry->postorder_nr == size-1);
- doms[size-1] = entry;
- do {
- struct basic_block *b;
- changed = 0;
- FOR_EACH_PTR(ep->bbs, b) {
- struct basic_block *p;
- int bnr = b->postorder_nr;
- struct basic_block *new_idom = NULL;
- if (b == entry)
- continue; // ignore entry node
- FOR_EACH_PTR(b->parents, p) {
- unsigned int pnr = p->postorder_nr;
- if (!doms[pnr])
- continue;
- if (!new_idom) {
- new_idom = p;
- continue;
- }
- new_idom = intersect_dom(doms, p, new_idom);
- } END_FOR_EACH_PTR(p);
- assert(new_idom);
- if (doms[bnr] != new_idom) {
- doms[bnr] = new_idom;
- changed = 1;
- }
- } END_FOR_EACH_PTR(b);
- } while (changed);
- FOR_EACH_PTR(ep->bbs, bb) {
- free_ptr_list(&bb->doms);
- } END_FOR_EACH_PTR(bb);
- // set the idom links
- FOR_EACH_PTR(ep->bbs, bb) {
- struct basic_block *idom = doms[bb->postorder_nr];
- if (bb == entry)
- continue; // ignore entry node
- bb->idom = idom;
- add_bb(&idom->doms, bb);
- } END_FOR_EACH_PTR(bb);
- entry->idom = NULL;
- // set the dominance levels
- FOR_EACH_PTR(ep->bbs, bb) {
- struct basic_block *idom = bb->idom;
- int level = idom ? idom->dom_level + 1 : 0;
- bb->dom_level = level;
- if (max_level < level)
- max_level = level;
- } END_FOR_EACH_PTR(bb);
- ep->dom_levels = max_level + 1;
- free(doms);
- if (dbg_domtree)
- debug_domtree(ep);
- }
- // dt_dominates - does BB a dominates BB b?
- bool domtree_dominates(struct basic_block *a, struct basic_block *b)
- {
- if (a == b) // dominance is reflexive
- return true;
- if (a == b->idom)
- return true;
- if (b == a->idom)
- return false;
- // can't dominate if deeper in the DT
- if (a->dom_level >= b->dom_level)
- return false;
- // FIXME: can be faster if we have the DFS in-out numbers
- // walk up the dominator tree
- for (b = b->idom; b; b = b->idom) {
- if (b == a)
- return true;
- }
- return false;
- }
|