Mercurial > hg > CbC > CbC_gcc
annotate gcc/domwalk.c @ 89:3356a4c26abc
modify comment out :c-parser.c
author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 20 Dec 2011 19:03:56 +0900 |
parents | f6334be47118 |
children | 04ced10e8804 |
rev | line source |
---|---|
0 | 1 /* Generic dominator tree walker |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2 Copyright (C) 2003, 2004, 2005, 2007, 2008, 2010 Free Software Foundation, |
0 | 3 Inc. |
4 Contributed by Diego Novillo <dnovillo@redhat.com> | |
5 | |
6 This file is part of GCC. | |
7 | |
8 GCC is free software; you can redistribute it and/or modify | |
9 it under the terms of the GNU General Public License as published by | |
10 the Free Software Foundation; either version 3, or (at your option) | |
11 any later version. | |
12 | |
13 GCC is distributed in the hope that it will be useful, | |
14 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 GNU General Public License for more details. | |
17 | |
18 You should have received a copy of the GNU General Public License | |
19 along with GCC; see the file COPYING3. If not see | |
20 <http://www.gnu.org/licenses/>. */ | |
21 | |
22 #include "config.h" | |
23 #include "system.h" | |
24 #include "coretypes.h" | |
25 #include "tm.h" | |
26 #include "basic-block.h" | |
27 #include "domwalk.h" | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
28 #include "sbitmap.h" |
0 | 29 |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
30 /* This file implements a generic walker for dominator trees. |
0 | 31 |
32 To understand the dominator walker one must first have a grasp of dominators, | |
33 immediate dominators and the dominator tree. | |
34 | |
35 Dominators | |
36 A block B1 is said to dominate B2 if every path from the entry to B2 must | |
37 pass through B1. Given the dominance relationship, we can proceed to | |
38 compute immediate dominators. Note it is not important whether or not | |
39 our definition allows a block to dominate itself. | |
40 | |
41 Immediate Dominators: | |
42 Every block in the CFG has no more than one immediate dominator. The | |
43 immediate dominator of block BB must dominate BB and must not dominate | |
44 any other dominator of BB and must not be BB itself. | |
45 | |
46 Dominator tree: | |
47 If we then construct a tree where each node is a basic block and there | |
48 is an edge from each block's immediate dominator to the block itself, then | |
49 we have a dominator tree. | |
50 | |
51 | |
52 [ Note this walker can also walk the post-dominator tree, which is | |
53 defined in a similar manner. i.e., block B1 is said to post-dominate | |
54 block B2 if all paths from B2 to the exit block must pass through | |
55 B1. ] | |
56 | |
57 For example, given the CFG | |
58 | |
59 1 | |
60 | | |
61 2 | |
62 / \ | |
63 3 4 | |
64 / \ | |
65 +---------->5 6 | |
66 | / \ / | |
67 | +--->8 7 | |
68 | | / | | |
69 | +--9 11 | |
70 | / | | |
71 +--- 10 ---> 12 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
72 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
73 |
0 | 74 We have a dominator tree which looks like |
75 | |
76 1 | |
77 | | |
78 2 | |
79 / \ | |
80 / \ | |
81 3 4 | |
82 / / \ \ | |
83 | | | | | |
84 5 6 7 12 | |
85 | | | |
86 8 11 | |
87 | | |
88 9 | |
89 | | |
90 10 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
91 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
92 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
93 |
0 | 94 The dominator tree is the basis for a number of analysis, transformation |
95 and optimization algorithms that operate on a semi-global basis. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
96 |
0 | 97 The dominator walker is a generic routine which visits blocks in the CFG |
98 via a depth first search of the dominator tree. In the example above | |
99 the dominator walker might visit blocks in the following order | |
100 1, 2, 3, 4, 5, 8, 9, 10, 6, 7, 11, 12. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
101 |
0 | 102 The dominator walker has a number of callbacks to perform actions |
103 during the walk of the dominator tree. There are two callbacks | |
104 which walk statements, one before visiting the dominator children, | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
105 one after visiting the dominator children. There is a callback |
0 | 106 before and after each statement walk callback. In addition, the |
107 dominator walker manages allocation/deallocation of data structures | |
108 which are local to each block visited. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
109 |
0 | 110 The dominator walker is meant to provide a generic means to build a pass |
111 which can analyze or transform/optimize a function based on walking | |
112 the dominator tree. One simply fills in the dominator walker data | |
113 structure with the appropriate callbacks and calls the walker. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
114 |
0 | 115 We currently use the dominator walker to prune the set of variables |
116 which might need PHI nodes (which can greatly improve compile-time | |
117 performance in some cases). | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
118 |
0 | 119 We also use the dominator walker to rewrite the function into SSA form |
120 which reduces code duplication since the rewriting phase is inherently | |
121 a walk of the dominator tree. | |
122 | |
123 And (of course), we use the dominator walker to drive our dominator | |
124 optimizer, which is a semi-global optimizer. | |
125 | |
126 TODO: | |
127 | |
128 Walking statements is based on the block statement iterator abstraction, | |
129 which is currently an abstraction over walking tree statements. Thus | |
130 the dominator walker is currently only useful for trees. */ | |
131 | |
132 /* Recursively walk the dominator tree. | |
133 | |
134 WALK_DATA contains a set of callbacks to perform pass-specific | |
135 actions during the dominator walk as well as a stack of block local | |
136 data maintained during the dominator walk. | |
137 | |
138 BB is the basic block we are currently visiting. */ | |
139 | |
140 void | |
141 walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb) | |
142 { | |
143 void *bd = NULL; | |
144 basic_block dest; | |
145 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2); | |
146 int sp = 0; | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
147 sbitmap visited = sbitmap_alloc (last_basic_block + 1); |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
148 sbitmap_zero (visited); |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
149 SET_BIT (visited, ENTRY_BLOCK_PTR->index); |
0 | 150 |
151 while (true) | |
152 { | |
153 /* Don't worry about unreachable blocks. */ | |
154 if (EDGE_COUNT (bb->preds) > 0 | |
155 || bb == ENTRY_BLOCK_PTR | |
156 || bb == EXIT_BLOCK_PTR) | |
157 { | |
158 /* Callback to initialize the local data structure. */ | |
159 if (walk_data->initialize_block_local_data) | |
160 { | |
161 bool recycled; | |
162 | |
163 /* First get some local data, reusing any local data | |
164 pointer we may have saved. */ | |
165 if (VEC_length (void_p, walk_data->free_block_data) > 0) | |
166 { | |
167 bd = VEC_pop (void_p, walk_data->free_block_data); | |
168 recycled = 1; | |
169 } | |
170 else | |
171 { | |
172 bd = xcalloc (1, walk_data->block_local_data_size); | |
173 recycled = 0; | |
174 } | |
175 | |
176 /* Push the local data into the local data stack. */ | |
177 VEC_safe_push (void_p, heap, walk_data->block_data_stack, bd); | |
178 | |
179 /* Call the initializer. */ | |
180 walk_data->initialize_block_local_data (walk_data, bb, | |
181 recycled); | |
182 | |
183 } | |
184 | |
185 /* Callback for operations to execute before we have walked the | |
186 dominator children, but before we walk statements. */ | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
187 if (walk_data->before_dom_children) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
188 (*walk_data->before_dom_children) (walk_data, bb); |
0 | 189 |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
190 SET_BIT (visited, bb->index); |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
191 |
0 | 192 /* Mark the current BB to be popped out of the recursion stack |
193 once children are processed. */ | |
194 worklist[sp++] = bb; | |
195 worklist[sp++] = NULL; | |
196 | |
197 for (dest = first_dom_son (walk_data->dom_direction, bb); | |
198 dest; dest = next_dom_son (walk_data->dom_direction, dest)) | |
199 worklist[sp++] = dest; | |
200 } | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
201 /* NULL is used to mark pop operations in the recursion stack. */ |
0 | 202 while (sp > 0 && !worklist[sp - 1]) |
203 { | |
204 --sp; | |
205 bb = worklist[--sp]; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
206 |
0 | 207 /* Callback for operations to execute after we have walked the |
208 dominator children, but before we walk statements. */ | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
209 if (walk_data->after_dom_children) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
210 (*walk_data->after_dom_children) (walk_data, bb); |
0 | 211 |
212 if (walk_data->initialize_block_local_data) | |
213 { | |
214 /* And finally pop the record off the block local data stack. */ | |
215 bd = VEC_pop (void_p, walk_data->block_data_stack); | |
216 /* And save the block data so that we can re-use it. */ | |
217 VEC_safe_push (void_p, heap, walk_data->free_block_data, bd); | |
218 } | |
219 } | |
220 if (sp) | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
221 { |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
222 int spp; |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
223 spp = sp - 1; |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
224 if (walk_data->dom_direction == CDI_DOMINATORS) |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
225 /* Find the dominator son that has all its predecessors |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
226 visited and continue with that. */ |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
227 while (1) |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
228 { |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
229 edge_iterator ei; |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
230 edge e; |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
231 bool found = true; |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
232 bb = worklist[spp]; |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
233 FOR_EACH_EDGE (e, ei, bb->preds) |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
234 { |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
235 if (!dominated_by_p (CDI_DOMINATORS, e->src, e->dest) |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
236 && !TEST_BIT (visited, e->src->index)) |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
237 { |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
238 found = false; |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
239 break; |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
240 } |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
241 } |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
242 if (found) |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
243 break; |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
244 /* If we didn't find a dom child with all visited |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
245 predecessors just use the candidate we were checking. |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
246 This happens for candidates in irreducible loops. */ |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
247 if (!worklist[spp - 1]) |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
248 break; |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
249 --spp; |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
250 } |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
251 bb = worklist[spp]; |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
252 worklist[spp] = worklist[--sp]; |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
253 } |
0 | 254 else |
255 break; | |
256 } | |
257 free (worklist); | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
258 sbitmap_free (visited); |
0 | 259 } |
260 | |
261 void | |
262 init_walk_dominator_tree (struct dom_walk_data *walk_data) | |
263 { | |
264 walk_data->free_block_data = NULL; | |
265 walk_data->block_data_stack = NULL; | |
266 } | |
267 | |
268 void | |
269 fini_walk_dominator_tree (struct dom_walk_data *walk_data) | |
270 { | |
271 if (walk_data->initialize_block_local_data) | |
272 { | |
273 while (VEC_length (void_p, walk_data->free_block_data) > 0) | |
274 free (VEC_pop (void_p, walk_data->free_block_data)); | |
275 } | |
276 | |
277 VEC_free (void_p, heap, walk_data->free_block_data); | |
278 VEC_free (void_p, heap, walk_data->block_data_stack); | |
279 } |