1 // SPDX-License-Identifier: MIT 2 // 3 // dominate.c - compute the (iterated) dominance frontier of (a set of) nodes. 4 // 5 // Copyright (C) 2017 - Luc Van Oostenryck 6 // 7 // The algorithm used is the one described in: 8 // "A Linear Time Algorithm for Placing phi-nodes" 9 // by Vugranam C. Sreedhar and Guang R. Gao 10 // 11 12 #include "dominate.h" 13 #include "flowgraph.h" 14 #include "linearize.h" 15 #include "flow.h" 16 #include <assert.h> 17 #include <stdlib.h> 18 #include <stdio.h> 19 20 21 struct piggy { 22 unsigned int max; 23 struct basic_block_list *lists[0]; 24 }; 25 26 static struct piggy *bank_init(unsigned levels) 27 { 28 struct piggy *bank; 29 bank = calloc(1, sizeof(*bank) + levels * sizeof(bank->lists[0])); 30 bank->max = levels - 1; 31 return bank; 32 } 33 34 static void bank_free(struct piggy *bank, unsigned int levels) 35 { 36 for (; levels-- ;) 37 free_ptr_list(&bank->lists[levels]); 38 free(bank); 39 } 40 41 static void bank_put(struct piggy *bank, struct basic_block *bb) 42 { 43 unsigned int level = bb->dom_level; 44 assert(level <= bank->max); 45 add_bb(&bank->lists[level], bb); 46 } 47 48 static inline struct basic_block *pop_bb(struct basic_block_list **list) 49 { 50 return delete_ptr_list_last((struct ptr_list **)list); 51 } 52 53 static struct basic_block *bank_get(struct piggy *bank) 54 { 55 int level = bank->max; 56 do { 57 struct basic_block *bb = pop_bb(&bank->lists[level]); 58 if (bb) 59 return bb; 60 if (!level) 61 return NULL; 62 bank->max = --level; 63 } while (1); 64 } 65 66 67 #define VISITED 0x1 68 #define INPHI 0x2 69 #define ALPHA 0x4 70 #define FLAGS 0x7 71 72 static void visit(struct piggy *bank, struct basic_block_list **idf, struct basic_block *x, int curr_level) 73 { 74 struct basic_block *y; 75 76 x->generation |= 1; 77 FOR_EACH_PTR(x->children, y) { 78 unsigned flags = y->generation & FLAGS; 79 if (y->idom == x) // J-edges will be processed later 80 continue; 81 if (y->dom_level > curr_level) 82 continue; 83 if (flags & INPHI) 84 continue; 85 y->generation |= INPHI; 86 add_bb(idf, y); 87 if (flags & ALPHA) 88 continue; 89 bank_put(bank, y); 90 } END_FOR_EACH_PTR(y); 91 92 FOR_EACH_PTR(x->doms, y) { 93 if (y->generation & VISITED) 94 continue; 95 visit(bank, idf, y, curr_level); 96 } END_FOR_EACH_PTR(y); 97 } 98 99 void idf_compute(struct entrypoint *ep, struct basic_block_list **idf, struct basic_block_list *alpha) 100 { 101 int levels = ep->dom_levels; 102 struct piggy *bank = bank_init(levels); 103 struct basic_block *bb; 104 unsigned long generation = bb_generation; 105 106 generation = bb_generation; 107 generation += -generation & FLAGS; 108 bb_generation = generation + (FLAGS + 1); 109 110 // init all the nodes 111 FOR_EACH_PTR(ep->bbs, bb) { 112 // FIXME: this should be removed and the tests for 113 // visited/in_phi/alpha should use a sparse set 114 bb->generation = generation; 115 } END_FOR_EACH_PTR(bb); 116 117 FOR_EACH_PTR(alpha, bb) { 118 bb->generation = generation | ALPHA; 119 bank_put(bank, bb); 120 } END_FOR_EACH_PTR(bb); 121 122 while ((bb = bank_get(bank))) { 123 visit(bank, idf, bb, bb->dom_level); 124 } 125 126 bank_free(bank, levels); 127 } 128 129 void idf_dump(struct entrypoint *ep) 130 { 131 struct basic_block *bb; 132 133 domtree_build(ep); 134 135 printf("%s's IDF:\n", show_ident(ep->name->ident)); 136 FOR_EACH_PTR(ep->bbs, bb) { 137 struct basic_block_list *alpha = NULL; 138 struct basic_block_list *idf = NULL; 139 struct basic_block *df; 140 141 add_bb(&alpha, bb); 142 idf_compute(ep, &idf, alpha); 143 144 printf("\t%s\t<-", show_label(bb)); 145 FOR_EACH_PTR(idf, df) { 146 printf(" %s", show_label(df)); 147 } END_FOR_EACH_PTR(df); 148 printf("\n"); 149 150 free_ptr_list(&idf); 151 free_ptr_list(&alpha); 152 } END_FOR_EACH_PTR(bb); 153 }