]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Generic dominator tree walker |
23a5b65a | 2 | Copyright (C) 2003-2014 Free Software Foundation, Inc. |
6de9cd9a DN |
3 | Contributed by Diego Novillo <dnovillo@redhat.com> |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify | |
8 | it under the terms of the GNU General Public License as published by | |
9dcd6f09 | 9 | the Free Software Foundation; either version 3, or (at your option) |
6de9cd9a DN |
10 | any later version. |
11 | ||
12 | GCC is distributed in the hope that it will be useful, | |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | GNU General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
6de9cd9a DN |
20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
6de9cd9a | 25 | #include "basic-block.h" |
6de9cd9a | 26 | #include "domwalk.h" |
7a8cba34 | 27 | #include "sbitmap.h" |
6de9cd9a | 28 | |
b8698a0f | 29 | /* This file implements a generic walker for dominator trees. |
6de9cd9a DN |
30 | |
31 | To understand the dominator walker one must first have a grasp of dominators, | |
32 | immediate dominators and the dominator tree. | |
33 | ||
34 | Dominators | |
35 | A block B1 is said to dominate B2 if every path from the entry to B2 must | |
36 | pass through B1. Given the dominance relationship, we can proceed to | |
37 | compute immediate dominators. Note it is not important whether or not | |
38 | our definition allows a block to dominate itself. | |
39 | ||
40 | Immediate Dominators: | |
41 | Every block in the CFG has no more than one immediate dominator. The | |
42 | immediate dominator of block BB must dominate BB and must not dominate | |
43 | any other dominator of BB and must not be BB itself. | |
44 | ||
45 | Dominator tree: | |
46 | If we then construct a tree where each node is a basic block and there | |
47 | is an edge from each block's immediate dominator to the block itself, then | |
48 | we have a dominator tree. | |
49 | ||
50 | ||
51 | [ Note this walker can also walk the post-dominator tree, which is | |
454ff5cb | 52 | defined in a similar manner. i.e., block B1 is said to post-dominate |
6de9cd9a DN |
53 | block B2 if all paths from B2 to the exit block must pass through |
54 | B1. ] | |
55 | ||
56 | For example, given the CFG | |
57 | ||
58 | 1 | |
59 | | | |
60 | 2 | |
61 | / \ | |
62 | 3 4 | |
63 | / \ | |
64 | +---------->5 6 | |
65 | | / \ / | |
66 | | +--->8 7 | |
67 | | | / | | |
68 | | +--9 11 | |
69 | | / | | |
70 | +--- 10 ---> 12 | |
b8698a0f L |
71 | |
72 | ||
6de9cd9a DN |
73 | We have a dominator tree which looks like |
74 | ||
75 | 1 | |
76 | | | |
77 | 2 | |
78 | / \ | |
79 | / \ | |
80 | 3 4 | |
81 | / / \ \ | |
82 | | | | | | |
83 | 5 6 7 12 | |
84 | | | | |
85 | 8 11 | |
86 | | | |
87 | 9 | |
88 | | | |
89 | 10 | |
b8698a0f L |
90 | |
91 | ||
92 | ||
6de9cd9a DN |
93 | The dominator tree is the basis for a number of analysis, transformation |
94 | and optimization algorithms that operate on a semi-global basis. | |
b8698a0f | 95 | |
6de9cd9a DN |
96 | The dominator walker is a generic routine which visits blocks in the CFG |
97 | via a depth first search of the dominator tree. In the example above | |
98 | the dominator walker might visit blocks in the following order | |
99 | 1, 2, 3, 4, 5, 8, 9, 10, 6, 7, 11, 12. | |
b8698a0f | 100 | |
6de9cd9a DN |
101 | The dominator walker has a number of callbacks to perform actions |
102 | during the walk of the dominator tree. There are two callbacks | |
103 | which walk statements, one before visiting the dominator children, | |
b8698a0f | 104 | one after visiting the dominator children. There is a callback |
6de9cd9a DN |
105 | before and after each statement walk callback. In addition, the |
106 | dominator walker manages allocation/deallocation of data structures | |
107 | which are local to each block visited. | |
b8698a0f | 108 | |
6de9cd9a DN |
109 | The dominator walker is meant to provide a generic means to build a pass |
110 | which can analyze or transform/optimize a function based on walking | |
111 | the dominator tree. One simply fills in the dominator walker data | |
112 | structure with the appropriate callbacks and calls the walker. | |
b8698a0f | 113 | |
6de9cd9a DN |
114 | We currently use the dominator walker to prune the set of variables |
115 | which might need PHI nodes (which can greatly improve compile-time | |
116 | performance in some cases). | |
b8698a0f | 117 | |
6de9cd9a DN |
118 | We also use the dominator walker to rewrite the function into SSA form |
119 | which reduces code duplication since the rewriting phase is inherently | |
120 | a walk of the dominator tree. | |
121 | ||
110abdbc | 122 | And (of course), we use the dominator walker to drive our dominator |
6de9cd9a DN |
123 | optimizer, which is a semi-global optimizer. |
124 | ||
125 | TODO: | |
126 | ||
127 | Walking statements is based on the block statement iterator abstraction, | |
128 | which is currently an abstraction over walking tree statements. Thus | |
129 | the dominator walker is currently only useful for trees. */ | |
130 | ||
076b4605 RB |
131 | static int *bb_postorder; |
132 | ||
133 | static int | |
134 | cmp_bb_postorder (const void *a, const void *b) | |
135 | { | |
136 | basic_block bb1 = *(basic_block *)const_cast<void *>(a); | |
137 | basic_block bb2 = *(basic_block *)const_cast<void *>(b); | |
138 | if (bb1->index == bb2->index) | |
139 | return 0; | |
140 | /* Place higher completion number first (pop off lower number first). */ | |
141 | if (bb_postorder[bb1->index] > bb_postorder[bb2->index]) | |
142 | return -1; | |
143 | return 1; | |
144 | } | |
145 | ||
6de9cd9a | 146 | /* Recursively walk the dominator tree. |
6de9cd9a DN |
147 | BB is the basic block we are currently visiting. */ |
148 | ||
149 | void | |
4d9192b5 | 150 | dom_walker::walk (basic_block bb) |
6de9cd9a | 151 | { |
6de9cd9a | 152 | basic_block dest; |
0cae8d31 DM |
153 | basic_block *worklist = XNEWVEC (basic_block, |
154 | n_basic_blocks_for_fn (cfun) * 2); | |
df648b94 | 155 | int sp = 0; |
076b4605 RB |
156 | int *postorder, postorder_num; |
157 | ||
65d3284b | 158 | if (m_dom_direction == CDI_DOMINATORS) |
076b4605 | 159 | { |
0cae8d31 | 160 | postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); |
076b4605 | 161 | postorder_num = inverted_post_order_compute (postorder); |
8b1c6fd7 | 162 | bb_postorder = XNEWVEC (int, last_basic_block_for_fn (cfun)); |
076b4605 RB |
163 | for (int i = 0; i < postorder_num; ++i) |
164 | bb_postorder[postorder[i]] = i; | |
165 | free (postorder); | |
166 | } | |
0bca51f0 | 167 | |
df648b94 | 168 | while (true) |
6de9cd9a | 169 | { |
df648b94 | 170 | /* Don't worry about unreachable blocks. */ |
515f36eb | 171 | if (EDGE_COUNT (bb->preds) > 0 |
fefa31b5 DM |
172 | || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) |
173 | || bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) | |
6de9cd9a | 174 | { |
4d9192b5 TS |
175 | /* Callback for subclasses to do custom things before we have walked |
176 | the dominator children, but before we walk statements. */ | |
177 | before_dom_children (bb); | |
df648b94 JH |
178 | |
179 | /* Mark the current BB to be popped out of the recursion stack | |
fa10beec | 180 | once children are processed. */ |
df648b94 JH |
181 | worklist[sp++] = bb; |
182 | worklist[sp++] = NULL; | |
183 | ||
076b4605 | 184 | int saved_sp = sp; |
65d3284b RS |
185 | for (dest = first_dom_son (m_dom_direction, bb); |
186 | dest; dest = next_dom_son (m_dom_direction, dest)) | |
df648b94 | 187 | worklist[sp++] = dest; |
65d3284b | 188 | if (m_dom_direction == CDI_DOMINATORS) |
076b4605 RB |
189 | switch (sp - saved_sp) |
190 | { | |
191 | case 0: | |
192 | case 1: | |
193 | break; | |
194 | default: | |
195 | qsort (&worklist[saved_sp], sp - saved_sp, | |
196 | sizeof (basic_block), cmp_bb_postorder); | |
197 | } | |
6de9cd9a | 198 | } |
ccf5c864 | 199 | /* NULL is used to mark pop operations in the recursion stack. */ |
df648b94 | 200 | while (sp > 0 && !worklist[sp - 1]) |
6de9cd9a | 201 | { |
df648b94 JH |
202 | --sp; |
203 | bb = worklist[--sp]; | |
df648b94 | 204 | |
4d9192b5 TS |
205 | /* Callback allowing subclasses to do custom things after we have |
206 | walked dominator children, but before we walk statements. */ | |
207 | after_dom_children (bb); | |
6de9cd9a | 208 | } |
df648b94 | 209 | if (sp) |
076b4605 | 210 | bb = worklist[--sp]; |
6de9cd9a | 211 | else |
df648b94 | 212 | break; |
6de9cd9a | 213 | } |
65d3284b | 214 | if (m_dom_direction == CDI_DOMINATORS) |
076b4605 RB |
215 | { |
216 | free (bb_postorder); | |
217 | bb_postorder = NULL; | |
218 | } | |
df648b94 | 219 | free (worklist); |
6de9cd9a | 220 | } |