blob: bf2ae63a9e3930a7c1ebb116b46832fc70a0d660 [file] [log] [blame]
 // SPDX-License-Identifier: MIT // // dominate.c - compute the (iterated) dominance frontier of (a set of) nodes. // // Copyright (C) 2017 - Luc Van Oostenryck // // The algorithm used is the one described in: // "A Linear Time Algorithm for Placing phi-nodes" // by Vugranam C. Sreedhar and Guang R. Gao // #include "dominate.h" #include "flowgraph.h" #include "linearize.h" #include "flow.h" #include #include #include struct piggy { unsigned int max; struct basic_block_list *lists; }; static struct piggy *bank_init(unsigned levels) { struct piggy *bank; bank = calloc(1, sizeof(*bank) + levels * sizeof(bank->lists)); bank->max = levels - 1; return bank; } static void bank_free(struct piggy *bank, unsigned int levels) { for (; levels-- ;) free_ptr_list(&bank->lists[levels]); free(bank); } static void bank_put(struct piggy *bank, struct basic_block *bb) { unsigned int level = bb->dom_level; assert(level <= bank->max); add_bb(&bank->lists[level], bb); } static inline struct basic_block *pop_bb(struct basic_block_list **list) { return delete_ptr_list_last((struct ptr_list **)list); } static struct basic_block *bank_get(struct piggy *bank) { int level = bank->max; do { struct basic_block *bb = pop_bb(&bank->lists[level]); if (bb) return bb; if (!level) return NULL; bank->max = --level; } while (1); } #define VISITED 0x1 #define INPHI 0x2 #define ALPHA 0x4 #define FLAGS 0x7 static void visit(struct piggy *bank, struct basic_block_list **idf, struct basic_block *x, int curr_level) { struct basic_block *y; x->generation |= 1; FOR_EACH_PTR(x->children, y) { unsigned flags = y->generation & FLAGS; if (y->idom == x) // J-edges will be processed later continue; if (y->dom_level > curr_level) continue; if (flags & INPHI) continue; y->generation |= INPHI; add_bb(idf, y); if (flags & ALPHA) continue; bank_put(bank, y); } END_FOR_EACH_PTR(y); FOR_EACH_PTR(x->doms, y) { if (y->generation & VISITED) continue; visit(bank, idf, y, curr_level); } END_FOR_EACH_PTR(y); } void idf_compute(struct entrypoint *ep, struct basic_block_list **idf, struct basic_block_list *alpha) { int levels = ep->dom_levels; struct piggy *bank = bank_init(levels); struct basic_block *bb; unsigned long generation = bb_generation; generation = bb_generation; generation += -generation & FLAGS; bb_generation = generation + (FLAGS + 1); // init all the nodes FOR_EACH_PTR(ep->bbs, bb) { // FIXME: this should be removed and the tests for // visited/in_phi/alpha should use a sparse set bb->generation = generation; } END_FOR_EACH_PTR(bb); FOR_EACH_PTR(alpha, bb) { bb->generation = generation | ALPHA; bank_put(bank, bb); } END_FOR_EACH_PTR(bb); while ((bb = bank_get(bank))) { visit(bank, idf, bb, bb->dom_level); } bank_free(bank, levels); } void idf_dump(struct entrypoint *ep) { struct basic_block *bb; domtree_build(ep); printf("%s's IDF:\n", show_ident(ep->name->ident)); FOR_EACH_PTR(ep->bbs, bb) { struct basic_block_list *alpha = NULL; struct basic_block_list *idf = NULL; struct basic_block *df; add_bb(&alpha, bb); idf_compute(ep, &idf, alpha); printf("\t%s\t<-", show_label(bb)); FOR_EACH_PTR(idf, df) { printf(" %s", show_label(df)); } END_FOR_EACH_PTR(df); printf("\n"); free_ptr_list(&idf); free_ptr_list(&alpha); } END_FOR_EACH_PTR(bb); }