| // 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 <assert.h> |
| #include <stdlib.h> |
| #include <stdio.h> |
| |
| |
| struct piggy { |
| unsigned int max; |
| struct basic_block_list *lists[0]; |
| }; |
| |
| static struct piggy *bank_init(unsigned levels) |
| { |
| struct piggy *bank; |
| bank = calloc(1, sizeof(*bank) + levels * sizeof(bank->lists[0])); |
| 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); |
| } |