| // 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); |
| |
| // 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; |
| } |