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
bank_init(unsigned levels)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
bank_free(struct piggy * bank,unsigned int levels)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
bank_put(struct piggy * bank,struct basic_block * bb)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
pop_bb(struct basic_block_list ** list)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
bank_get(struct piggy * bank)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
visit(struct piggy * bank,struct basic_block_list ** idf,struct basic_block * x,int curr_level)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
idf_compute(struct entrypoint * ep,struct basic_block_list ** idf,struct basic_block_list * alpha)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
idf_dump(struct entrypoint * ep)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 }
154