comparison gcc/domwalk.c @ 16:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents f6334be47118
children 84e7813d76e9
comparison
equal deleted inserted replaced
15:561a7518be6b 16:04ced10e8804
1 /* Generic dominator tree walker 1 /* Generic dominator tree walker
2 Copyright (C) 2003, 2004, 2005, 2007, 2008, 2010 Free Software Foundation, 2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
3 Inc.
4 Contributed by Diego Novillo <dnovillo@redhat.com> 3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 4
6 This file is part of GCC. 5 This file is part of GCC.
7 6
8 GCC is free software; you can redistribute it and/or modify 7 GCC is free software; you can redistribute it and/or modify
20 <http://www.gnu.org/licenses/>. */ 19 <http://www.gnu.org/licenses/>. */
21 20
22 #include "config.h" 21 #include "config.h"
23 #include "system.h" 22 #include "system.h"
24 #include "coretypes.h" 23 #include "coretypes.h"
25 #include "tm.h" 24 #include "backend.h"
26 #include "basic-block.h" 25 #include "cfganal.h"
27 #include "domwalk.h" 26 #include "domwalk.h"
28 #include "sbitmap.h" 27 #include "dumpfile.h"
29 28
30 /* This file implements a generic walker for dominator trees. 29 /* This file implements a generic walker for dominator trees.
31 30
32 To understand the dominator walker one must first have a grasp of dominators, 31 To understand the dominator walker one must first have a grasp of dominators,
33 immediate dominators and the dominator tree. 32 immediate dominators and the dominator tree.
127 126
128 Walking statements is based on the block statement iterator abstraction, 127 Walking statements is based on the block statement iterator abstraction,
129 which is currently an abstraction over walking tree statements. Thus 128 which is currently an abstraction over walking tree statements. Thus
130 the dominator walker is currently only useful for trees. */ 129 the dominator walker is currently only useful for trees. */
131 130
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
172 /* Constructor for a dom walker.
173
174 If SKIP_UNREACHBLE_BLOCKS is true, then we need to set
175 EDGE_EXECUTABLE on every edge in the CFG. */
176 dom_walker::dom_walker (cdi_direction direction,
177 bool skip_unreachable_blocks,
178 int *bb_index_to_rpo)
179 : m_dom_direction (direction),
180 m_skip_unreachable_blocks (skip_unreachable_blocks),
181 m_user_bb_to_rpo (bb_index_to_rpo != NULL),
182 m_unreachable_dom (NULL),
183 m_bb_to_rpo (bb_index_to_rpo)
184 {
185 /* Compute the basic-block index to RPO mapping if not provided by
186 the user. */
187 if (! m_bb_to_rpo && direction == CDI_DOMINATORS)
188 {
189 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
190 int postorder_num = pre_and_rev_post_order_compute (NULL, postorder,
191 true);
192 m_bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
193 for (int i = 0; i < postorder_num; ++i)
194 m_bb_to_rpo[postorder[i]] = i;
195 free (postorder);
196 }
197
198 /* If we are not skipping unreachable blocks, then there is nothing
199 further to do. */
200 if (!m_skip_unreachable_blocks)
201 return;
202
203 basic_block bb;
204 FOR_ALL_BB_FN (bb, cfun)
205 {
206 edge_iterator ei;
207 edge e;
208 FOR_EACH_EDGE (e, ei, bb->succs)
209 e->flags |= EDGE_EXECUTABLE;
210 }
211 }
212
213 /* Destructor. */
214
215 dom_walker::~dom_walker ()
216 {
217 if (! m_user_bb_to_rpo)
218 free (m_bb_to_rpo);
219 }
220
221 /* Return TRUE if BB is reachable, false otherwise. */
222
223 bool
224 dom_walker::bb_reachable (struct function *fun, basic_block bb)
225 {
226 /* If we're not skipping unreachable blocks, then assume everything
227 is reachable. */
228 if (!m_skip_unreachable_blocks)
229 return true;
230
231 /* If any of the predecessor edges that do not come from blocks dominated
232 by us are still marked as possibly executable consider this block
233 reachable. */
234 bool reachable = false;
235 if (!m_unreachable_dom)
236 {
237 reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (fun);
238 edge_iterator ei;
239 edge e;
240 FOR_EACH_EDGE (e, ei, bb->preds)
241 if (!dominated_by_p (CDI_DOMINATORS, e->src, bb))
242 reachable |= (e->flags & EDGE_EXECUTABLE);
243 }
244
245 return reachable;
246 }
247
248 /* BB has been determined to be unreachable. Propagate that property
249 to incoming and outgoing edges of BB as appropriate. */
250
251 void
252 dom_walker::propagate_unreachable_to_edges (basic_block bb,
253 FILE *dump_file,
254 dump_flags_t dump_flags)
255 {
256 if (dump_file && (dump_flags & TDF_DETAILS))
257 fprintf (dump_file, "Marking all outgoing edges of unreachable "
258 "BB %d as not executable\n", bb->index);
259
260 edge_iterator ei;
261 edge e;
262 FOR_EACH_EDGE (e, ei, bb->succs)
263 e->flags &= ~EDGE_EXECUTABLE;
264
265 FOR_EACH_EDGE (e, ei, bb->preds)
266 {
267 if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
268 {
269 if (dump_file && (dump_flags & TDF_DETAILS))
270 fprintf (dump_file, "Marking backedge from BB %d into "
271 "unreachable BB %d as not executable\n",
272 e->src->index, bb->index);
273 e->flags &= ~EDGE_EXECUTABLE;
274 }
275 }
276
277 if (!m_unreachable_dom)
278 m_unreachable_dom = bb;
279 }
280
281 const edge dom_walker::STOP = (edge)-1;
282
132 /* Recursively walk the dominator tree. 283 /* 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. */ 284 BB is the basic block we are currently visiting. */
139 285
140 void 286 void
141 walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb) 287 dom_walker::walk (basic_block bb)
142 { 288 {
143 void *bd = NULL;
144 basic_block dest; 289 basic_block dest;
145 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2); 290 basic_block *worklist = XNEWVEC (basic_block,
291 n_basic_blocks_for_fn (cfun) * 2);
146 int sp = 0; 292 int sp = 0;
147 sbitmap visited = sbitmap_alloc (last_basic_block + 1); 293 bb_postorder = m_bb_to_rpo;
148 sbitmap_zero (visited);
149 SET_BIT (visited, ENTRY_BLOCK_PTR->index);
150 294
151 while (true) 295 while (true)
152 { 296 {
153 /* Don't worry about unreachable blocks. */ 297 /* Don't worry about unreachable blocks. */
154 if (EDGE_COUNT (bb->preds) > 0 298 if (EDGE_COUNT (bb->preds) > 0
155 || bb == ENTRY_BLOCK_PTR 299 || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
156 || bb == EXIT_BLOCK_PTR) 300 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
157 { 301 {
158 /* Callback to initialize the local data structure. */ 302 edge taken_edge = NULL;
159 if (walk_data->initialize_block_local_data) 303
304 /* Callback for subclasses to do custom things before we have walked
305 the dominator children, but before we walk statements. */
306 if (this->bb_reachable (cfun, bb))
160 { 307 {
161 bool recycled; 308 taken_edge = before_dom_children (bb);
162 309 if (taken_edge && taken_edge != STOP)
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 { 310 {
167 bd = VEC_pop (void_p, walk_data->free_block_data); 311 edge_iterator ei;
168 recycled = 1; 312 edge e;
313 FOR_EACH_EDGE (e, ei, bb->succs)
314 if (e != taken_edge)
315 e->flags &= ~EDGE_EXECUTABLE;
169 } 316 }
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 } 317 }
184 318 else
185 /* Callback for operations to execute before we have walked the 319 propagate_unreachable_to_edges (bb, dump_file, dump_flags);
186 dominator children, but before we walk statements. */
187 if (walk_data->before_dom_children)
188 (*walk_data->before_dom_children) (walk_data, bb);
189
190 SET_BIT (visited, bb->index);
191 320
192 /* Mark the current BB to be popped out of the recursion stack 321 /* Mark the current BB to be popped out of the recursion stack
193 once children are processed. */ 322 once children are processed. */
194 worklist[sp++] = bb; 323 worklist[sp++] = bb;
195 worklist[sp++] = NULL; 324 worklist[sp++] = NULL;
196 325
197 for (dest = first_dom_son (walk_data->dom_direction, bb); 326 /* If the callback returned NONE then we are supposed to
198 dest; dest = next_dom_son (walk_data->dom_direction, dest)) 327 stop and not even propagate EDGE_EXECUTABLE further. */
199 worklist[sp++] = dest; 328 if (taken_edge != STOP)
329 {
330 int saved_sp = sp;
331 for (dest = first_dom_son (m_dom_direction, bb);
332 dest; dest = next_dom_son (m_dom_direction, dest))
333 worklist[sp++] = dest;
334 if (sp - saved_sp > 1 && m_dom_direction == CDI_DOMINATORS)
335 sort_bbs_postorder (&worklist[saved_sp], sp - saved_sp);
336 }
200 } 337 }
201 /* NULL is used to mark pop operations in the recursion stack. */ 338 /* NULL is used to mark pop operations in the recursion stack. */
202 while (sp > 0 && !worklist[sp - 1]) 339 while (sp > 0 && !worklist[sp - 1])
203 { 340 {
204 --sp; 341 --sp;
205 bb = worklist[--sp]; 342 bb = worklist[--sp];
206 343
207 /* Callback for operations to execute after we have walked the 344 /* Callback allowing subclasses to do custom things after we have
208 dominator children, but before we walk statements. */ 345 walked dominator children, but before we walk statements. */
209 if (walk_data->after_dom_children) 346 if (bb_reachable (cfun, bb))
210 (*walk_data->after_dom_children) (walk_data, bb); 347 after_dom_children (bb);
211 348 else if (m_unreachable_dom == bb)
212 if (walk_data->initialize_block_local_data) 349 m_unreachable_dom = NULL;
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 } 350 }
220 if (sp) 351 if (sp)
221 { 352 bb = worklist[--sp];
222 int spp;
223 spp = sp - 1;
224 if (walk_data->dom_direction == CDI_DOMINATORS)
225 /* Find the dominator son that has all its predecessors
226 visited and continue with that. */
227 while (1)
228 {
229 edge_iterator ei;
230 edge e;
231 bool found = true;
232 bb = worklist[spp];
233 FOR_EACH_EDGE (e, ei, bb->preds)
234 {
235 if (!dominated_by_p (CDI_DOMINATORS, e->src, e->dest)
236 && !TEST_BIT (visited, e->src->index))
237 {
238 found = false;
239 break;
240 }
241 }
242 if (found)
243 break;
244 /* If we didn't find a dom child with all visited
245 predecessors just use the candidate we were checking.
246 This happens for candidates in irreducible loops. */
247 if (!worklist[spp - 1])
248 break;
249 --spp;
250 }
251 bb = worklist[spp];
252 worklist[spp] = worklist[--sp];
253 }
254 else 353 else
255 break; 354 break;
256 } 355 }
356 bb_postorder = NULL;
257 free (worklist); 357 free (worklist);
258 sbitmap_free (visited); 358 }
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 }