]>
Commit | Line | Data |
---|---|---|
6de9cd9a DN |
1 | /* Generic dominator tree walker |
2 | Copyright (C) 2003, 2004 Free Software Foundation, Inc. | |
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 | |
9 | the Free Software Foundation; either version 2, or (at your option) | |
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 | |
18 | along with GCC; see the file COPYING. If not, write to | |
19 | the Free Software Foundation, 59 Temple Place - Suite 330, | |
20 | Boston, MA 02111-1307, USA. */ | |
21 | ||
22 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
25 | #include "tm.h" | |
26 | #include "tree.h" | |
27 | #include "basic-block.h" | |
28 | #include "tree-flow.h" | |
29 | #include "domwalk.h" | |
30 | #include "ggc.h" | |
31 | ||
32 | /* This file implements a generic walker for dominator trees. | |
33 | ||
34 | To understand the dominator walker one must first have a grasp of dominators, | |
35 | immediate dominators and the dominator tree. | |
36 | ||
37 | Dominators | |
38 | A block B1 is said to dominate B2 if every path from the entry to B2 must | |
39 | pass through B1. Given the dominance relationship, we can proceed to | |
40 | compute immediate dominators. Note it is not important whether or not | |
41 | our definition allows a block to dominate itself. | |
42 | ||
43 | Immediate Dominators: | |
44 | Every block in the CFG has no more than one immediate dominator. The | |
45 | immediate dominator of block BB must dominate BB and must not dominate | |
46 | any other dominator of BB and must not be BB itself. | |
47 | ||
48 | Dominator tree: | |
49 | If we then construct a tree where each node is a basic block and there | |
50 | is an edge from each block's immediate dominator to the block itself, then | |
51 | we have a dominator tree. | |
52 | ||
53 | ||
54 | [ Note this walker can also walk the post-dominator tree, which is | |
55 | defined in a similar manner. ie, block B1 is said to post-dominate | |
56 | block B2 if all paths from B2 to the exit block must pass through | |
57 | B1. ] | |
58 | ||
59 | For example, given the CFG | |
60 | ||
61 | 1 | |
62 | | | |
63 | 2 | |
64 | / \ | |
65 | 3 4 | |
66 | / \ | |
67 | +---------->5 6 | |
68 | | / \ / | |
69 | | +--->8 7 | |
70 | | | / | | |
71 | | +--9 11 | |
72 | | / | | |
73 | +--- 10 ---> 12 | |
74 | ||
75 | ||
76 | We have a dominator tree which looks like | |
77 | ||
78 | 1 | |
79 | | | |
80 | 2 | |
81 | / \ | |
82 | / \ | |
83 | 3 4 | |
84 | / / \ \ | |
85 | | | | | | |
86 | 5 6 7 12 | |
87 | | | | |
88 | 8 11 | |
89 | | | |
90 | 9 | |
91 | | | |
92 | 10 | |
93 | ||
94 | ||
95 | ||
96 | The dominator tree is the basis for a number of analysis, transformation | |
97 | and optimization algorithms that operate on a semi-global basis. | |
98 | ||
99 | The dominator walker is a generic routine which visits blocks in the CFG | |
100 | via a depth first search of the dominator tree. In the example above | |
101 | the dominator walker might visit blocks in the following order | |
102 | 1, 2, 3, 4, 5, 8, 9, 10, 6, 7, 11, 12. | |
103 | ||
104 | The dominator walker has a number of callbacks to perform actions | |
105 | during the walk of the dominator tree. There are two callbacks | |
106 | which walk statements, one before visiting the dominator children, | |
107 | one after visiting the dominator children. There is a callback | |
108 | before and after each statement walk callback. In addition, the | |
109 | dominator walker manages allocation/deallocation of data structures | |
110 | which are local to each block visited. | |
111 | ||
112 | The dominator walker is meant to provide a generic means to build a pass | |
113 | which can analyze or transform/optimize a function based on walking | |
114 | the dominator tree. One simply fills in the dominator walker data | |
115 | structure with the appropriate callbacks and calls the walker. | |
116 | ||
117 | We currently use the dominator walker to prune the set of variables | |
118 | which might need PHI nodes (which can greatly improve compile-time | |
119 | performance in some cases). | |
120 | ||
121 | We also use the dominator walker to rewrite the function into SSA form | |
122 | which reduces code duplication since the rewriting phase is inherently | |
123 | a walk of the dominator tree. | |
124 | ||
125 | And (of course), we use the dominator walker to drive a our dominator | |
126 | optimizer, which is a semi-global optimizer. | |
127 | ||
128 | TODO: | |
129 | ||
130 | Walking statements is based on the block statement iterator abstraction, | |
131 | which is currently an abstraction over walking tree statements. Thus | |
132 | the dominator walker is currently only useful for trees. */ | |
133 | ||
134 | /* Recursively walk the dominator tree. | |
135 | ||
136 | WALK_DATA contains a set of callbacks to perform pass-specific | |
137 | actions during the dominator walk as well as a stack of block local | |
138 | data maintained during the dominator walk. | |
139 | ||
140 | BB is the basic block we are currently visiting. */ | |
141 | ||
142 | void | |
143 | walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb) | |
144 | { | |
145 | void *bd = NULL; | |
146 | basic_block dest; | |
147 | block_stmt_iterator bsi; | |
148 | ||
149 | /* Callback to initialize the local data structure. */ | |
150 | if (walk_data->initialize_block_local_data) | |
151 | { | |
152 | bool recycled; | |
153 | ||
154 | /* First get some local data, reusing any local data pointer we may | |
155 | have saved. */ | |
156 | if (VARRAY_ACTIVE_SIZE (walk_data->free_block_data) > 0) | |
157 | { | |
158 | bd = VARRAY_TOP_GENERIC_PTR (walk_data->free_block_data); | |
159 | VARRAY_POP (walk_data->free_block_data); | |
160 | recycled = 1; | |
161 | } | |
162 | else | |
163 | { | |
164 | bd = xcalloc (1, walk_data->block_local_data_size); | |
165 | recycled = 0; | |
166 | } | |
167 | ||
168 | /* Push the local data into the local data stack. */ | |
169 | VARRAY_PUSH_GENERIC_PTR (walk_data->block_data_stack, bd); | |
170 | ||
171 | /* Call the initializer. */ | |
172 | walk_data->initialize_block_local_data (walk_data, bb, recycled); | |
173 | ||
174 | } | |
175 | ||
176 | /* Callback for operations to execute before we have walked the | |
177 | dominator children, but before we walk statements. */ | |
178 | if (walk_data->before_dom_children_before_stmts) | |
179 | (*walk_data->before_dom_children_before_stmts) (walk_data, bb); | |
180 | ||
181 | /* Statement walk before walking dominator children. */ | |
182 | if (walk_data->before_dom_children_walk_stmts) | |
183 | { | |
184 | if (walk_data->walk_stmts_backward) | |
185 | for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) | |
186 | (*walk_data->before_dom_children_walk_stmts) (walk_data, bb, bsi); | |
187 | else | |
188 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
189 | (*walk_data->before_dom_children_walk_stmts) (walk_data, bb, bsi); | |
190 | } | |
191 | ||
192 | /* Callback for operations to execute before we have walked the | |
193 | dominator children, and after we walk statements. */ | |
194 | if (walk_data->before_dom_children_after_stmts) | |
195 | (*walk_data->before_dom_children_after_stmts) (walk_data, bb); | |
196 | ||
197 | /* Recursively call ourselves on the dominator children of BB. */ | |
198 | for (dest = first_dom_son (walk_data->dom_direction, bb); | |
199 | dest; | |
200 | dest = next_dom_son (walk_data->dom_direction, dest)) | |
201 | { | |
202 | /* The destination block may have become unreachable, in | |
203 | which case there's no point in optimizing it. */ | |
204 | if (dest->pred) | |
205 | walk_dominator_tree (walk_data, dest); | |
206 | } | |
207 | ||
208 | /* Callback for operations to execute after we have walked the | |
209 | dominator children, but before we walk statements. */ | |
210 | if (walk_data->after_dom_children_before_stmts) | |
211 | (*walk_data->after_dom_children_before_stmts) (walk_data, bb); | |
212 | ||
213 | /* Statement walk after walking dominator children. */ | |
214 | if (walk_data->after_dom_children_walk_stmts) | |
215 | { | |
216 | if (walk_data->walk_stmts_backward) | |
217 | for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) | |
218 | (*walk_data->after_dom_children_walk_stmts) (walk_data, bb, bsi); | |
219 | else | |
220 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
221 | (*walk_data->after_dom_children_walk_stmts) (walk_data, bb, bsi); | |
222 | } | |
223 | ||
224 | /* Callback for operations to execute after we have walked the | |
225 | dominator children and after we have walked statements. */ | |
226 | if (walk_data->after_dom_children_after_stmts) | |
227 | (*walk_data->after_dom_children_after_stmts) (walk_data, bb); | |
228 | ||
229 | if (walk_data->initialize_block_local_data) | |
230 | { | |
231 | /* And save the block data so that we can re-use it. */ | |
232 | VARRAY_PUSH_GENERIC_PTR (walk_data->free_block_data, bd); | |
233 | ||
234 | /* And finally pop the record off the block local data stack. */ | |
235 | VARRAY_POP (walk_data->block_data_stack); | |
236 | } | |
237 | } | |
238 | ||
239 | void | |
240 | init_walk_dominator_tree (struct dom_walk_data *walk_data) | |
241 | { | |
242 | if (walk_data->initialize_block_local_data) | |
243 | { | |
244 | VARRAY_GENERIC_PTR_INIT (walk_data->free_block_data, 2, "freelist "); | |
245 | VARRAY_GENERIC_PTR_INIT (walk_data->block_data_stack, 2, "block_data"); | |
246 | } | |
247 | else | |
248 | { | |
249 | walk_data->free_block_data = NULL; | |
250 | walk_data->block_data_stack = NULL; | |
251 | } | |
252 | } | |
253 | ||
254 | void | |
255 | fini_walk_dominator_tree (struct dom_walk_data *walk_data) | |
256 | { | |
257 | if (walk_data->initialize_block_local_data) | |
258 | { | |
259 | while (VARRAY_ACTIVE_SIZE (walk_data->free_block_data) > 0) | |
260 | { | |
261 | free (VARRAY_TOP_GENERIC_PTR (walk_data->free_block_data)); | |
262 | VARRAY_POP (walk_data->free_block_data); | |
263 | } | |
264 | } | |
265 | } |