Mercurial > hg > CbC > CbC_gcc
annotate gcc/domwalk.c @ 131:84e7813d76e9
gcc-8.2
author | mir3636 |
---|---|
date | Thu, 25 Oct 2018 07:37:49 +0900 |
parents | 04ced10e8804 |
children | 1830386684a0 |
rev | line source |
---|---|
0 | 1 /* Generic dominator tree walker |
131 | 2 Copyright (C) 2003-2018 Free Software Foundation, Inc. |
0 | 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 3, 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 COPYING3. If not see | |
19 <http://www.gnu.org/licenses/>. */ | |
20 | |
21 #include "config.h" | |
22 #include "system.h" | |
23 #include "coretypes.h" | |
111 | 24 #include "backend.h" |
25 #include "cfganal.h" | |
0 | 26 #include "domwalk.h" |
111 | 27 #include "dumpfile.h" |
0 | 28 |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
29 /* This file implements a generic walker for dominator trees. |
0 | 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 | |
52 defined in a similar manner. i.e., block B1 is said to post-dominate | |
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 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
71 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
72 |
0 | 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 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
90 |
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 |
0 | 93 The dominator tree is the basis for a number of analysis, transformation |
94 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
|
95 |
0 | 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. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
100 |
0 | 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, | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
104 one after visiting the dominator children. There is a callback |
0 | 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. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
108 |
0 | 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. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
113 |
0 | 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). | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
117 |
0 | 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 | |
122 And (of course), we use the dominator walker to drive our dominator | |
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 | |
111 | 131 /* Reverse postorder index of each basic block. */ |
132 static int *bb_postorder; | |
133 | |
134 static int | |
135 cmp_bb_postorder (const void *a, const void *b) | |
136 { | |
137 basic_block bb1 = *(const basic_block *)(a); | |
138 basic_block bb2 = *(const basic_block *)(b); | |
139 /* Place higher completion number first (pop off lower number first). */ | |
140 return bb_postorder[bb2->index] - bb_postorder[bb1->index]; | |
141 } | |
142 | |
143 /* Permute array BBS of N basic blocks in postorder, | |
144 i.e. by descending number in BB_POSTORDER array. */ | |
145 | |
146 static void | |
147 sort_bbs_postorder (basic_block *bbs, int n) | |
148 { | |
149 if (__builtin_expect (n == 2, true)) | |
150 { | |
151 basic_block bb0 = bbs[0], bb1 = bbs[1]; | |
152 if (bb_postorder[bb0->index] < bb_postorder[bb1->index]) | |
153 bbs[0] = bb1, bbs[1] = bb0; | |
154 } | |
155 else if (__builtin_expect (n == 3, true)) | |
156 { | |
157 basic_block bb0 = bbs[0], bb1 = bbs[1], bb2 = bbs[2]; | |
158 if (bb_postorder[bb0->index] < bb_postorder[bb1->index]) | |
159 std::swap (bb0, bb1); | |
160 if (bb_postorder[bb1->index] < bb_postorder[bb2->index]) | |
161 { | |
162 std::swap (bb1, bb2); | |
163 if (bb_postorder[bb0->index] < bb_postorder[bb1->index]) | |
164 std::swap (bb0, bb1); | |
165 } | |
166 bbs[0] = bb0, bbs[1] = bb1, bbs[2] = bb2; | |
167 } | |
168 else | |
169 qsort (bbs, n, sizeof *bbs, cmp_bb_postorder); | |
170 } | |
171 | |
131 | 172 /* Set EDGE_EXECUTABLE on every edge within FN's CFG. */ |
111 | 173 |
131 | 174 void |
175 set_all_edges_as_executable (function *fn) | |
176 { | |
177 basic_block bb; | |
178 FOR_ALL_BB_FN (bb, fn) | |
179 { | |
180 edge_iterator ei; | |
181 edge e; | |
182 FOR_EACH_EDGE (e, ei, bb->succs) | |
183 e->flags |= EDGE_EXECUTABLE; | |
184 } | |
185 } | |
186 | |
187 /* Constructor for a dom walker. */ | |
188 | |
111 | 189 dom_walker::dom_walker (cdi_direction direction, |
131 | 190 enum reachability reachability, |
111 | 191 int *bb_index_to_rpo) |
192 : m_dom_direction (direction), | |
131 | 193 m_skip_unreachable_blocks (reachability != ALL_BLOCKS), |
194 m_user_bb_to_rpo (true), | |
111 | 195 m_unreachable_dom (NULL), |
196 m_bb_to_rpo (bb_index_to_rpo) | |
197 { | |
131 | 198 /* Set up edge flags if need be. */ |
199 switch (reachability) | |
200 { | |
201 default: | |
202 gcc_unreachable (); | |
203 case ALL_BLOCKS: | |
204 /* No need to touch edge flags. */ | |
205 break; | |
206 | |
207 case REACHABLE_BLOCKS: | |
208 set_all_edges_as_executable (cfun); | |
209 break; | |
210 | |
211 case REACHABLE_BLOCKS_PRESERVING_FLAGS: | |
212 /* Preserve the edge flags. */ | |
213 break; | |
214 } | |
215 } | |
216 | |
217 /* Constructor for a dom walker. */ | |
218 | |
219 dom_walker::dom_walker (cdi_direction direction, | |
220 enum reachability reachability) | |
221 : m_dom_direction (direction), | |
222 m_skip_unreachable_blocks (reachability != ALL_BLOCKS), | |
223 m_user_bb_to_rpo (false), | |
224 m_unreachable_dom (NULL), | |
225 m_bb_to_rpo (NULL) | |
226 { | |
227 /* Compute the basic-block index to RPO mapping. */ | |
228 if (direction == CDI_DOMINATORS) | |
111 | 229 { |
230 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); | |
231 int postorder_num = pre_and_rev_post_order_compute (NULL, postorder, | |
232 true); | |
233 m_bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun)); | |
234 for (int i = 0; i < postorder_num; ++i) | |
235 m_bb_to_rpo[postorder[i]] = i; | |
236 free (postorder); | |
237 } | |
238 | |
131 | 239 /* Set up edge flags if need be. */ |
240 switch (reachability) | |
241 { | |
242 default: | |
243 gcc_unreachable (); | |
244 case ALL_BLOCKS: | |
245 /* No need to touch edge flags. */ | |
246 break; | |
0 | 247 |
131 | 248 case REACHABLE_BLOCKS: |
249 set_all_edges_as_executable (cfun); | |
250 break; | |
251 | |
252 case REACHABLE_BLOCKS_PRESERVING_FLAGS: | |
253 /* Preserve the edge flags. */ | |
254 break; | |
111 | 255 } |
256 } | |
257 | |
258 /* Destructor. */ | |
259 | |
260 dom_walker::~dom_walker () | |
261 { | |
262 if (! m_user_bb_to_rpo) | |
263 free (m_bb_to_rpo); | |
264 } | |
265 | |
266 /* Return TRUE if BB is reachable, false otherwise. */ | |
267 | |
268 bool | |
269 dom_walker::bb_reachable (struct function *fun, basic_block bb) | |
270 { | |
271 /* If we're not skipping unreachable blocks, then assume everything | |
272 is reachable. */ | |
273 if (!m_skip_unreachable_blocks) | |
274 return true; | |
0 | 275 |
111 | 276 /* If any of the predecessor edges that do not come from blocks dominated |
277 by us are still marked as possibly executable consider this block | |
278 reachable. */ | |
279 bool reachable = false; | |
280 if (!m_unreachable_dom) | |
281 { | |
282 reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (fun); | |
283 edge_iterator ei; | |
284 edge e; | |
285 FOR_EACH_EDGE (e, ei, bb->preds) | |
286 if (!dominated_by_p (CDI_DOMINATORS, e->src, bb)) | |
287 reachable |= (e->flags & EDGE_EXECUTABLE); | |
288 } | |
289 | |
290 return reachable; | |
291 } | |
292 | |
293 /* BB has been determined to be unreachable. Propagate that property | |
294 to incoming and outgoing edges of BB as appropriate. */ | |
295 | |
296 void | |
297 dom_walker::propagate_unreachable_to_edges (basic_block bb, | |
298 FILE *dump_file, | |
299 dump_flags_t dump_flags) | |
300 { | |
301 if (dump_file && (dump_flags & TDF_DETAILS)) | |
302 fprintf (dump_file, "Marking all outgoing edges of unreachable " | |
303 "BB %d as not executable\n", bb->index); | |
304 | |
305 edge_iterator ei; | |
306 edge e; | |
307 FOR_EACH_EDGE (e, ei, bb->succs) | |
308 e->flags &= ~EDGE_EXECUTABLE; | |
309 | |
310 FOR_EACH_EDGE (e, ei, bb->preds) | |
311 { | |
312 if (dominated_by_p (CDI_DOMINATORS, e->src, bb)) | |
313 { | |
314 if (dump_file && (dump_flags & TDF_DETAILS)) | |
315 fprintf (dump_file, "Marking backedge from BB %d into " | |
316 "unreachable BB %d as not executable\n", | |
317 e->src->index, bb->index); | |
318 e->flags &= ~EDGE_EXECUTABLE; | |
319 } | |
320 } | |
321 | |
322 if (!m_unreachable_dom) | |
323 m_unreachable_dom = bb; | |
324 } | |
325 | |
326 const edge dom_walker::STOP = (edge)-1; | |
327 | |
328 /* Recursively walk the dominator tree. | |
0 | 329 BB is the basic block we are currently visiting. */ |
330 | |
331 void | |
111 | 332 dom_walker::walk (basic_block bb) |
0 | 333 { |
334 basic_block dest; | |
111 | 335 basic_block *worklist = XNEWVEC (basic_block, |
336 n_basic_blocks_for_fn (cfun) * 2); | |
0 | 337 int sp = 0; |
111 | 338 bb_postorder = m_bb_to_rpo; |
0 | 339 |
340 while (true) | |
341 { | |
342 /* Don't worry about unreachable blocks. */ | |
343 if (EDGE_COUNT (bb->preds) > 0 | |
111 | 344 || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) |
345 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) | |
0 | 346 { |
111 | 347 edge taken_edge = NULL; |
0 | 348 |
111 | 349 /* Callback for subclasses to do custom things before we have walked |
350 the dominator children, but before we walk statements. */ | |
351 if (this->bb_reachable (cfun, bb)) | |
352 { | |
353 taken_edge = before_dom_children (bb); | |
354 if (taken_edge && taken_edge != STOP) | |
0 | 355 { |
111 | 356 edge_iterator ei; |
357 edge e; | |
358 FOR_EACH_EDGE (e, ei, bb->succs) | |
359 if (e != taken_edge) | |
360 e->flags &= ~EDGE_EXECUTABLE; | |
0 | 361 } |
362 } | |
111 | 363 else |
364 propagate_unreachable_to_edges (bb, dump_file, dump_flags); | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
365 |
0 | 366 /* Mark the current BB to be popped out of the recursion stack |
367 once children are processed. */ | |
368 worklist[sp++] = bb; | |
369 worklist[sp++] = NULL; | |
370 | |
111 | 371 /* If the callback returned NONE then we are supposed to |
372 stop and not even propagate EDGE_EXECUTABLE further. */ | |
373 if (taken_edge != STOP) | |
374 { | |
375 int saved_sp = sp; | |
376 for (dest = first_dom_son (m_dom_direction, bb); | |
377 dest; dest = next_dom_son (m_dom_direction, dest)) | |
378 worklist[sp++] = dest; | |
131 | 379 /* Sort worklist after RPO order if requested. */ |
380 if (sp - saved_sp > 1 | |
381 && m_dom_direction == CDI_DOMINATORS | |
382 && m_bb_to_rpo) | |
111 | 383 sort_bbs_postorder (&worklist[saved_sp], sp - saved_sp); |
384 } | |
0 | 385 } |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
386 /* NULL is used to mark pop operations in the recursion stack. */ |
0 | 387 while (sp > 0 && !worklist[sp - 1]) |
388 { | |
389 --sp; | |
390 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
|
391 |
111 | 392 /* Callback allowing subclasses to do custom things after we have |
393 walked dominator children, but before we walk statements. */ | |
394 if (bb_reachable (cfun, bb)) | |
395 after_dom_children (bb); | |
396 else if (m_unreachable_dom == bb) | |
397 m_unreachable_dom = NULL; | |
0 | 398 } |
399 if (sp) | |
111 | 400 bb = worklist[--sp]; |
0 | 401 else |
402 break; | |
403 } | |
111 | 404 bb_postorder = NULL; |
0 | 405 free (worklist); |
406 } |