|
0
|
1 /* CFG cleanup for trees.
|
|
|
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
|
|
|
3 Free Software Foundation, Inc.
|
|
|
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"
|
|
|
24 #include "tm.h"
|
|
|
25 #include "tree.h"
|
|
|
26 #include "rtl.h"
|
|
|
27 #include "tm_p.h"
|
|
|
28 #include "hard-reg-set.h"
|
|
|
29 #include "basic-block.h"
|
|
|
30 #include "output.h"
|
|
|
31 #include "toplev.h"
|
|
|
32 #include "flags.h"
|
|
|
33 #include "function.h"
|
|
|
34 #include "expr.h"
|
|
|
35 #include "ggc.h"
|
|
|
36 #include "langhooks.h"
|
|
|
37 #include "diagnostic.h"
|
|
|
38 #include "tree-flow.h"
|
|
|
39 #include "timevar.h"
|
|
|
40 #include "tree-dump.h"
|
|
|
41 #include "tree-pass.h"
|
|
|
42 #include "toplev.h"
|
|
|
43 #include "except.h"
|
|
|
44 #include "cfgloop.h"
|
|
|
45 #include "cfglayout.h"
|
|
|
46 #include "hashtab.h"
|
|
|
47 #include "tree-ssa-propagate.h"
|
|
|
48 #include "tree-scalar-evolution.h"
|
|
|
49
|
|
|
50 /* The set of blocks in that at least one of the following changes happened:
|
|
|
51 -- the statement at the end of the block was changed
|
|
|
52 -- the block was newly created
|
|
|
53 -- the set of the predecessors of the block changed
|
|
|
54 -- the set of the successors of the block changed
|
|
|
55 ??? Maybe we could track these changes separately, since they determine
|
|
|
56 what cleanups it makes sense to try on the block. */
|
|
|
57 bitmap cfgcleanup_altered_bbs;
|
|
|
58
|
|
|
59 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
|
|
|
60
|
|
|
61 static bool
|
|
|
62 remove_fallthru_edge (VEC(edge,gc) *ev)
|
|
|
63 {
|
|
|
64 edge_iterator ei;
|
|
|
65 edge e;
|
|
|
66
|
|
|
67 FOR_EACH_EDGE (e, ei, ev)
|
|
|
68 if ((e->flags & EDGE_FALLTHRU) != 0)
|
|
|
69 {
|
|
|
70 remove_edge_and_dominated_blocks (e);
|
|
|
71 return true;
|
|
|
72 }
|
|
|
73 return false;
|
|
|
74 }
|
|
|
75
|
|
|
76
|
|
|
77 /* Disconnect an unreachable block in the control expression starting
|
|
|
78 at block BB. */
|
|
|
79
|
|
|
80 static bool
|
|
|
81 cleanup_control_expr_graph (basic_block bb, gimple_stmt_iterator gsi)
|
|
|
82 {
|
|
|
83 edge taken_edge;
|
|
|
84 bool retval = false;
|
|
|
85 gimple stmt = gsi_stmt (gsi);
|
|
|
86 tree val;
|
|
|
87
|
|
|
88 if (!single_succ_p (bb))
|
|
|
89 {
|
|
|
90 edge e;
|
|
|
91 edge_iterator ei;
|
|
|
92 bool warned;
|
|
|
93
|
|
|
94 fold_defer_overflow_warnings ();
|
|
|
95 val = gimple_fold (stmt);
|
|
|
96 taken_edge = find_taken_edge (bb, val);
|
|
|
97 if (!taken_edge)
|
|
|
98 {
|
|
|
99 fold_undefer_and_ignore_overflow_warnings ();
|
|
|
100 return false;
|
|
|
101 }
|
|
|
102
|
|
|
103 /* Remove all the edges except the one that is always executed. */
|
|
|
104 warned = false;
|
|
|
105 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
|
|
|
106 {
|
|
|
107 if (e != taken_edge)
|
|
|
108 {
|
|
|
109 if (!warned)
|
|
|
110 {
|
|
|
111 fold_undefer_overflow_warnings
|
|
|
112 (true, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
|
|
|
113 warned = true;
|
|
|
114 }
|
|
|
115
|
|
|
116 taken_edge->probability += e->probability;
|
|
|
117 taken_edge->count += e->count;
|
|
|
118 remove_edge_and_dominated_blocks (e);
|
|
|
119 retval = true;
|
|
|
120 }
|
|
|
121 else
|
|
|
122 ei_next (&ei);
|
|
|
123 }
|
|
|
124 if (!warned)
|
|
|
125 fold_undefer_and_ignore_overflow_warnings ();
|
|
|
126 if (taken_edge->probability > REG_BR_PROB_BASE)
|
|
|
127 taken_edge->probability = REG_BR_PROB_BASE;
|
|
|
128 }
|
|
|
129 else
|
|
|
130 taken_edge = single_succ_edge (bb);
|
|
|
131
|
|
|
132 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
|
|
|
133 gsi_remove (&gsi, true);
|
|
|
134 taken_edge->flags = EDGE_FALLTHRU;
|
|
|
135
|
|
|
136 return retval;
|
|
|
137 }
|
|
|
138
|
|
|
139 /* Try to remove superfluous control structures in basic block BB. Returns
|
|
|
140 true if anything changes. */
|
|
|
141
|
|
|
142 static bool
|
|
|
143 cleanup_control_flow_bb (basic_block bb)
|
|
|
144 {
|
|
|
145 gimple_stmt_iterator gsi;
|
|
|
146 bool retval = false;
|
|
|
147 gimple stmt;
|
|
|
148
|
|
|
149 /* If the last statement of the block could throw and now cannot,
|
|
|
150 we need to prune cfg. */
|
|
|
151 retval |= gimple_purge_dead_eh_edges (bb);
|
|
|
152
|
|
|
153 gsi = gsi_last_bb (bb);
|
|
|
154 if (gsi_end_p (gsi))
|
|
|
155 return retval;
|
|
|
156
|
|
|
157 stmt = gsi_stmt (gsi);
|
|
|
158
|
|
|
159 if (gimple_code (stmt) == GIMPLE_COND
|
|
|
160 || gimple_code (stmt) == GIMPLE_SWITCH)
|
|
|
161 retval |= cleanup_control_expr_graph (bb, gsi);
|
|
|
162 else if (gimple_code (stmt) == GIMPLE_GOTO
|
|
|
163 && TREE_CODE (gimple_goto_dest (stmt)) == ADDR_EXPR
|
|
|
164 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt), 0))
|
|
|
165 == LABEL_DECL))
|
|
|
166 {
|
|
|
167 /* If we had a computed goto which has a compile-time determinable
|
|
|
168 destination, then we can eliminate the goto. */
|
|
|
169 edge e;
|
|
|
170 tree label;
|
|
|
171 edge_iterator ei;
|
|
|
172 basic_block target_block;
|
|
|
173
|
|
|
174 /* First look at all the outgoing edges. Delete any outgoing
|
|
|
175 edges which do not go to the right block. For the one
|
|
|
176 edge which goes to the right block, fix up its flags. */
|
|
|
177 label = TREE_OPERAND (gimple_goto_dest (stmt), 0);
|
|
|
178 target_block = label_to_block (label);
|
|
|
179 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
|
|
|
180 {
|
|
|
181 if (e->dest != target_block)
|
|
|
182 remove_edge_and_dominated_blocks (e);
|
|
|
183 else
|
|
|
184 {
|
|
|
185 /* Turn off the EDGE_ABNORMAL flag. */
|
|
|
186 e->flags &= ~EDGE_ABNORMAL;
|
|
|
187
|
|
|
188 /* And set EDGE_FALLTHRU. */
|
|
|
189 e->flags |= EDGE_FALLTHRU;
|
|
|
190 ei_next (&ei);
|
|
|
191 }
|
|
|
192 }
|
|
|
193
|
|
|
194 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
|
|
|
195 bitmap_set_bit (cfgcleanup_altered_bbs, target_block->index);
|
|
|
196
|
|
|
197 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
|
|
|
198 relevant information we need. */
|
|
|
199 gsi_remove (&gsi, true);
|
|
|
200 retval = true;
|
|
|
201 }
|
|
|
202
|
|
|
203 /* Check for indirect calls that have been turned into
|
|
|
204 noreturn calls. */
|
|
|
205 else if (is_gimple_call (stmt)
|
|
|
206 && gimple_call_noreturn_p (stmt)
|
|
|
207 && remove_fallthru_edge (bb->succs))
|
|
|
208 retval = true;
|
|
|
209
|
|
|
210 return retval;
|
|
|
211 }
|
|
|
212
|
|
|
213 /* Return true if basic block BB does nothing except pass control
|
|
|
214 flow to another block and that we can safely insert a label at
|
|
|
215 the start of the successor block.
|
|
|
216
|
|
|
217 As a precondition, we require that BB be not equal to
|
|
|
218 ENTRY_BLOCK_PTR. */
|
|
|
219
|
|
|
220 static bool
|
|
|
221 tree_forwarder_block_p (basic_block bb, bool phi_wanted)
|
|
|
222 {
|
|
|
223 gimple_stmt_iterator gsi;
|
|
|
224 edge_iterator ei;
|
|
|
225 edge e, succ;
|
|
|
226 basic_block dest;
|
|
|
227
|
|
|
228 /* BB must have a single outgoing edge. */
|
|
|
229 if (single_succ_p (bb) != 1
|
|
|
230 /* If PHI_WANTED is false, BB must not have any PHI nodes.
|
|
|
231 Otherwise, BB must have PHI nodes. */
|
|
|
232 || gimple_seq_empty_p (phi_nodes (bb)) == phi_wanted
|
|
|
233 /* BB may not be a predecessor of EXIT_BLOCK_PTR. */
|
|
|
234 || single_succ (bb) == EXIT_BLOCK_PTR
|
|
|
235 /* Nor should this be an infinite loop. */
|
|
|
236 || single_succ (bb) == bb
|
|
|
237 /* BB may not have an abnormal outgoing edge. */
|
|
|
238 || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
|
|
|
239 return false;
|
|
|
240
|
|
|
241 #if ENABLE_CHECKING
|
|
|
242 gcc_assert (bb != ENTRY_BLOCK_PTR);
|
|
|
243 #endif
|
|
|
244
|
|
|
245 /* Now walk through the statements backward. We can ignore labels,
|
|
|
246 anything else means this is not a forwarder block. */
|
|
|
247 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
|
|
|
248 {
|
|
|
249 gimple stmt = gsi_stmt (gsi);
|
|
|
250
|
|
|
251 switch (gimple_code (stmt))
|
|
|
252 {
|
|
|
253 case GIMPLE_LABEL:
|
|
|
254 if (DECL_NONLOCAL (gimple_label_label (stmt)))
|
|
|
255 return false;
|
|
|
256 break;
|
|
|
257
|
|
|
258 default:
|
|
|
259 return false;
|
|
|
260 }
|
|
|
261 }
|
|
|
262
|
|
|
263 if (find_edge (ENTRY_BLOCK_PTR, bb))
|
|
|
264 return false;
|
|
|
265
|
|
|
266 if (current_loops)
|
|
|
267 {
|
|
|
268 basic_block dest;
|
|
|
269 /* Protect loop latches, headers and preheaders. */
|
|
|
270 if (bb->loop_father->header == bb)
|
|
|
271 return false;
|
|
|
272 dest = EDGE_SUCC (bb, 0)->dest;
|
|
|
273
|
|
|
274 if (dest->loop_father->header == dest)
|
|
|
275 return false;
|
|
|
276 }
|
|
|
277
|
|
|
278 /* If we have an EH edge leaving this block, make sure that the
|
|
|
279 destination of this block has only one predecessor. This ensures
|
|
|
280 that we don't get into the situation where we try to remove two
|
|
|
281 forwarders that go to the same basic block but are handlers for
|
|
|
282 different EH regions. */
|
|
|
283 succ = single_succ_edge (bb);
|
|
|
284 dest = succ->dest;
|
|
|
285 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
286 {
|
|
|
287 if (e->flags & EDGE_EH)
|
|
|
288 {
|
|
|
289 if (!single_pred_p (dest))
|
|
|
290 return false;
|
|
|
291 }
|
|
|
292 }
|
|
|
293
|
|
|
294 return true;
|
|
|
295 }
|
|
|
296
|
|
|
297 /* Return true if BB has at least one abnormal incoming edge. */
|
|
|
298
|
|
|
299 static inline bool
|
|
|
300 has_abnormal_incoming_edge_p (basic_block bb)
|
|
|
301 {
|
|
|
302 edge e;
|
|
|
303 edge_iterator ei;
|
|
|
304
|
|
|
305 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
306 if (e->flags & EDGE_ABNORMAL)
|
|
|
307 return true;
|
|
|
308
|
|
|
309 return false;
|
|
|
310 }
|
|
|
311
|
|
|
312 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
|
|
|
313 those alternatives are equal in each of the PHI nodes, then return
|
|
|
314 true, else return false. */
|
|
|
315
|
|
|
316 static bool
|
|
|
317 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
|
|
|
318 {
|
|
|
319 int n1 = e1->dest_idx;
|
|
|
320 int n2 = e2->dest_idx;
|
|
|
321 gimple_stmt_iterator gsi;
|
|
|
322
|
|
|
323 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
324 {
|
|
|
325 gimple phi = gsi_stmt (gsi);
|
|
|
326 tree val1 = gimple_phi_arg_def (phi, n1);
|
|
|
327 tree val2 = gimple_phi_arg_def (phi, n2);
|
|
|
328
|
|
|
329 gcc_assert (val1 != NULL_TREE);
|
|
|
330 gcc_assert (val2 != NULL_TREE);
|
|
|
331
|
|
|
332 if (!operand_equal_for_phi_arg_p (val1, val2))
|
|
|
333 return false;
|
|
|
334 }
|
|
|
335
|
|
|
336 return true;
|
|
|
337 }
|
|
|
338
|
|
|
339 /* Removes forwarder block BB. Returns false if this failed. */
|
|
|
340
|
|
|
341 static bool
|
|
|
342 remove_forwarder_block (basic_block bb)
|
|
|
343 {
|
|
|
344 edge succ = single_succ_edge (bb), e, s;
|
|
|
345 basic_block dest = succ->dest;
|
|
|
346 gimple label;
|
|
|
347 edge_iterator ei;
|
|
|
348 gimple_stmt_iterator gsi, gsi_to;
|
|
|
349 bool seen_abnormal_edge = false;
|
|
|
350
|
|
|
351 /* We check for infinite loops already in tree_forwarder_block_p.
|
|
|
352 However it may happen that the infinite loop is created
|
|
|
353 afterwards due to removal of forwarders. */
|
|
|
354 if (dest == bb)
|
|
|
355 return false;
|
|
|
356
|
|
|
357 /* If the destination block consists of a nonlocal label, do not merge
|
|
|
358 it. */
|
|
|
359 label = first_stmt (dest);
|
|
|
360 if (label
|
|
|
361 && gimple_code (label) == GIMPLE_LABEL
|
|
|
362 && DECL_NONLOCAL (gimple_label_label (label)))
|
|
|
363 return false;
|
|
|
364
|
|
|
365 /* If there is an abnormal edge to basic block BB, but not into
|
|
|
366 dest, problems might occur during removal of the phi node at out
|
|
|
367 of ssa due to overlapping live ranges of registers.
|
|
|
368
|
|
|
369 If there is an abnormal edge in DEST, the problems would occur
|
|
|
370 anyway since cleanup_dead_labels would then merge the labels for
|
|
|
371 two different eh regions, and rest of exception handling code
|
|
|
372 does not like it.
|
|
|
373
|
|
|
374 So if there is an abnormal edge to BB, proceed only if there is
|
|
|
375 no abnormal edge to DEST and there are no phi nodes in DEST. */
|
|
|
376 if (has_abnormal_incoming_edge_p (bb))
|
|
|
377 {
|
|
|
378 seen_abnormal_edge = true;
|
|
|
379
|
|
|
380 if (has_abnormal_incoming_edge_p (dest)
|
|
|
381 || !gimple_seq_empty_p (phi_nodes (dest)))
|
|
|
382 return false;
|
|
|
383 }
|
|
|
384
|
|
|
385 /* If there are phi nodes in DEST, and some of the blocks that are
|
|
|
386 predecessors of BB are also predecessors of DEST, check that the
|
|
|
387 phi node arguments match. */
|
|
|
388 if (!gimple_seq_empty_p (phi_nodes (dest)))
|
|
|
389 {
|
|
|
390 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
391 {
|
|
|
392 s = find_edge (e->src, dest);
|
|
|
393 if (!s)
|
|
|
394 continue;
|
|
|
395
|
|
|
396 if (!phi_alternatives_equal (dest, succ, s))
|
|
|
397 return false;
|
|
|
398 }
|
|
|
399 }
|
|
|
400
|
|
|
401 /* Redirect the edges. */
|
|
|
402 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
|
|
|
403 {
|
|
|
404 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
|
|
|
405
|
|
|
406 if (e->flags & EDGE_ABNORMAL)
|
|
|
407 {
|
|
|
408 /* If there is an abnormal edge, redirect it anyway, and
|
|
|
409 move the labels to the new block to make it legal. */
|
|
|
410 s = redirect_edge_succ_nodup (e, dest);
|
|
|
411 }
|
|
|
412 else
|
|
|
413 s = redirect_edge_and_branch (e, dest);
|
|
|
414
|
|
|
415 if (s == e)
|
|
|
416 {
|
|
|
417 /* Create arguments for the phi nodes, since the edge was not
|
|
|
418 here before. */
|
|
|
419 for (gsi = gsi_start_phis (dest);
|
|
|
420 !gsi_end_p (gsi);
|
|
|
421 gsi_next (&gsi))
|
|
|
422 {
|
|
|
423 gimple phi = gsi_stmt (gsi);
|
|
|
424 add_phi_arg (phi, gimple_phi_arg_def (phi, succ->dest_idx), s);
|
|
|
425 }
|
|
|
426 }
|
|
|
427 }
|
|
|
428
|
|
|
429 if (seen_abnormal_edge)
|
|
|
430 {
|
|
|
431 /* Move the labels to the new block, so that the redirection of
|
|
|
432 the abnormal edges works. */
|
|
|
433 gsi_to = gsi_start_bb (dest);
|
|
|
434 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
|
|
|
435 {
|
|
|
436 label = gsi_stmt (gsi);
|
|
|
437 gcc_assert (gimple_code (label) == GIMPLE_LABEL);
|
|
|
438 gsi_remove (&gsi, false);
|
|
|
439 gsi_insert_before (&gsi_to, label, GSI_CONTINUE_LINKING);
|
|
|
440 }
|
|
|
441 }
|
|
|
442
|
|
|
443 bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
|
|
|
444
|
|
|
445 /* Update the dominators. */
|
|
|
446 if (dom_info_available_p (CDI_DOMINATORS))
|
|
|
447 {
|
|
|
448 basic_block dom, dombb, domdest;
|
|
|
449
|
|
|
450 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
|
|
|
451 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
|
|
|
452 if (domdest == bb)
|
|
|
453 {
|
|
|
454 /* Shortcut to avoid calling (relatively expensive)
|
|
|
455 nearest_common_dominator unless necessary. */
|
|
|
456 dom = dombb;
|
|
|
457 }
|
|
|
458 else
|
|
|
459 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
|
|
|
460
|
|
|
461 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
|
|
|
462 }
|
|
|
463
|
|
|
464 /* And kill the forwarder block. */
|
|
|
465 delete_basic_block (bb);
|
|
|
466
|
|
|
467 return true;
|
|
|
468 }
|
|
|
469
|
|
|
470 /* Split basic blocks on calls in the middle of a basic block that are now
|
|
|
471 known not to return, and remove the unreachable code. */
|
|
|
472
|
|
|
473 static bool
|
|
|
474 split_bbs_on_noreturn_calls (void)
|
|
|
475 {
|
|
|
476 bool changed = false;
|
|
|
477 gimple stmt;
|
|
|
478 basic_block bb;
|
|
|
479
|
|
|
480 /* Detect cases where a mid-block call is now known not to return. */
|
|
|
481 if (cfun->gimple_df)
|
|
|
482 while (VEC_length (gimple, MODIFIED_NORETURN_CALLS (cfun)))
|
|
|
483 {
|
|
|
484 stmt = VEC_pop (gimple, MODIFIED_NORETURN_CALLS (cfun));
|
|
|
485 bb = gimple_bb (stmt);
|
|
|
486 /* BB might be deleted at this point, so verify first
|
|
|
487 BB is present in the cfg. */
|
|
|
488 if (bb == NULL
|
|
|
489 || bb->index < NUM_FIXED_BLOCKS
|
|
|
490 || bb->index >= n_basic_blocks
|
|
|
491 || BASIC_BLOCK (bb->index) != bb
|
|
|
492 || last_stmt (bb) == stmt
|
|
|
493 || !gimple_call_noreturn_p (stmt))
|
|
|
494 continue;
|
|
|
495
|
|
|
496 changed = true;
|
|
|
497 split_block (bb, stmt);
|
|
|
498 remove_fallthru_edge (bb->succs);
|
|
|
499 }
|
|
|
500
|
|
|
501 return changed;
|
|
|
502 }
|
|
|
503
|
|
|
504 /* If GIMPLE_OMP_RETURN in basic block BB is unreachable, remove it. */
|
|
|
505
|
|
|
506 static bool
|
|
|
507 cleanup_omp_return (basic_block bb)
|
|
|
508 {
|
|
|
509 gimple stmt = last_stmt (bb);
|
|
|
510 basic_block control_bb;
|
|
|
511
|
|
|
512 if (stmt == NULL
|
|
|
513 || gimple_code (stmt) != GIMPLE_OMP_RETURN
|
|
|
514 || !single_pred_p (bb))
|
|
|
515 return false;
|
|
|
516
|
|
|
517 control_bb = single_pred (bb);
|
|
|
518 stmt = last_stmt (control_bb);
|
|
|
519
|
|
|
520 if (gimple_code (stmt) != GIMPLE_OMP_SECTIONS_SWITCH)
|
|
|
521 return false;
|
|
|
522
|
|
|
523 /* The block with the control statement normally has two entry edges -- one
|
|
|
524 from entry, one from continue. If continue is removed, return is
|
|
|
525 unreachable, so we remove it here as well. */
|
|
|
526 if (EDGE_COUNT (control_bb->preds) == 2)
|
|
|
527 return false;
|
|
|
528
|
|
|
529 gcc_assert (EDGE_COUNT (control_bb->preds) == 1);
|
|
|
530 remove_edge_and_dominated_blocks (single_pred_edge (bb));
|
|
|
531 return true;
|
|
|
532 }
|
|
|
533
|
|
|
534 /* Tries to cleanup cfg in basic block BB. Returns true if anything
|
|
|
535 changes. */
|
|
|
536
|
|
|
537 static bool
|
|
|
538 cleanup_tree_cfg_bb (basic_block bb)
|
|
|
539 {
|
|
|
540 bool retval = false;
|
|
|
541
|
|
|
542 if (cleanup_omp_return (bb))
|
|
|
543 return true;
|
|
|
544
|
|
|
545 retval = cleanup_control_flow_bb (bb);
|
|
|
546
|
|
|
547 /* Forwarder blocks can carry line number information which is
|
|
|
548 useful when debugging, so we only clean them up when
|
|
|
549 optimizing. */
|
|
|
550 if (optimize > 0
|
|
|
551 && tree_forwarder_block_p (bb, false)
|
|
|
552 && remove_forwarder_block (bb))
|
|
|
553 return true;
|
|
|
554
|
|
|
555 /* Merging the blocks may create new opportunities for folding
|
|
|
556 conditional branches (due to the elimination of single-valued PHI
|
|
|
557 nodes). */
|
|
|
558 if (single_succ_p (bb)
|
|
|
559 && can_merge_blocks_p (bb, single_succ (bb)))
|
|
|
560 {
|
|
|
561 merge_blocks (bb, single_succ (bb));
|
|
|
562 return true;
|
|
|
563 }
|
|
|
564
|
|
|
565 return retval;
|
|
|
566 }
|
|
|
567
|
|
|
568 /* Iterate the cfg cleanups, while anything changes. */
|
|
|
569
|
|
|
570 static bool
|
|
|
571 cleanup_tree_cfg_1 (void)
|
|
|
572 {
|
|
|
573 bool retval = false;
|
|
|
574 basic_block bb;
|
|
|
575 unsigned i, n;
|
|
|
576
|
|
|
577 retval |= split_bbs_on_noreturn_calls ();
|
|
|
578
|
|
|
579 /* Prepare the worklists of altered blocks. */
|
|
|
580 cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
|
|
|
581
|
|
|
582 /* During forwarder block cleanup, we may redirect edges out of
|
|
|
583 SWITCH_EXPRs, which can get expensive. So we want to enable
|
|
|
584 recording of edge to CASE_LABEL_EXPR. */
|
|
|
585 start_recording_case_labels ();
|
|
|
586
|
|
|
587 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB,
|
|
|
588 since the basic blocks may get removed. */
|
|
|
589 n = last_basic_block;
|
|
|
590 for (i = NUM_FIXED_BLOCKS; i < n; i++)
|
|
|
591 {
|
|
|
592 bb = BASIC_BLOCK (i);
|
|
|
593 if (bb)
|
|
|
594 retval |= cleanup_tree_cfg_bb (bb);
|
|
|
595 }
|
|
|
596
|
|
|
597 /* Now process the altered blocks, as long as any are available. */
|
|
|
598 while (!bitmap_empty_p (cfgcleanup_altered_bbs))
|
|
|
599 {
|
|
|
600 i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
|
|
|
601 bitmap_clear_bit (cfgcleanup_altered_bbs, i);
|
|
|
602 if (i < NUM_FIXED_BLOCKS)
|
|
|
603 continue;
|
|
|
604
|
|
|
605 bb = BASIC_BLOCK (i);
|
|
|
606 if (!bb)
|
|
|
607 continue;
|
|
|
608
|
|
|
609 retval |= cleanup_tree_cfg_bb (bb);
|
|
|
610
|
|
|
611 /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
|
|
|
612 calls. */
|
|
|
613 retval |= split_bbs_on_noreturn_calls ();
|
|
|
614 }
|
|
|
615
|
|
|
616 end_recording_case_labels ();
|
|
|
617 BITMAP_FREE (cfgcleanup_altered_bbs);
|
|
|
618 return retval;
|
|
|
619 }
|
|
|
620
|
|
|
621
|
|
|
622 /* Remove unreachable blocks and other miscellaneous clean up work.
|
|
|
623 Return true if the flowgraph was modified, false otherwise. */
|
|
|
624
|
|
|
625 static bool
|
|
|
626 cleanup_tree_cfg_noloop (void)
|
|
|
627 {
|
|
|
628 bool changed;
|
|
|
629
|
|
|
630 timevar_push (TV_TREE_CLEANUP_CFG);
|
|
|
631
|
|
|
632 /* Iterate until there are no more cleanups left to do. If any
|
|
|
633 iteration changed the flowgraph, set CHANGED to true.
|
|
|
634
|
|
|
635 If dominance information is available, there cannot be any unreachable
|
|
|
636 blocks. */
|
|
|
637 if (!dom_info_available_p (CDI_DOMINATORS))
|
|
|
638 {
|
|
|
639 changed = delete_unreachable_blocks ();
|
|
|
640 calculate_dominance_info (CDI_DOMINATORS);
|
|
|
641 }
|
|
|
642 else
|
|
|
643 {
|
|
|
644 #ifdef ENABLE_CHECKING
|
|
|
645 verify_dominators (CDI_DOMINATORS);
|
|
|
646 #endif
|
|
|
647 changed = false;
|
|
|
648 }
|
|
|
649
|
|
|
650 changed |= cleanup_tree_cfg_1 ();
|
|
|
651
|
|
|
652 gcc_assert (dom_info_available_p (CDI_DOMINATORS));
|
|
|
653 compact_blocks ();
|
|
|
654
|
|
|
655 #ifdef ENABLE_CHECKING
|
|
|
656 verify_flow_info ();
|
|
|
657 #endif
|
|
|
658
|
|
|
659 timevar_pop (TV_TREE_CLEANUP_CFG);
|
|
|
660
|
|
|
661 if (changed && current_loops)
|
|
|
662 loops_state_set (LOOPS_NEED_FIXUP);
|
|
|
663
|
|
|
664 return changed;
|
|
|
665 }
|
|
|
666
|
|
|
667 /* Repairs loop structures. */
|
|
|
668
|
|
|
669 static void
|
|
|
670 repair_loop_structures (void)
|
|
|
671 {
|
|
|
672 bitmap changed_bbs = BITMAP_ALLOC (NULL);
|
|
|
673 fix_loop_structure (changed_bbs);
|
|
|
674
|
|
|
675 /* This usually does nothing. But sometimes parts of cfg that originally
|
|
|
676 were inside a loop get out of it due to edge removal (since they
|
|
|
677 become unreachable by back edges from latch). */
|
|
|
678 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
|
|
|
679 rewrite_into_loop_closed_ssa (changed_bbs, TODO_update_ssa);
|
|
|
680
|
|
|
681 BITMAP_FREE (changed_bbs);
|
|
|
682
|
|
|
683 #ifdef ENABLE_CHECKING
|
|
|
684 verify_loop_structure ();
|
|
|
685 #endif
|
|
|
686 scev_reset ();
|
|
|
687
|
|
|
688 loops_state_clear (LOOPS_NEED_FIXUP);
|
|
|
689 }
|
|
|
690
|
|
|
691 /* Cleanup cfg and repair loop structures. */
|
|
|
692
|
|
|
693 bool
|
|
|
694 cleanup_tree_cfg (void)
|
|
|
695 {
|
|
|
696 bool changed = cleanup_tree_cfg_noloop ();
|
|
|
697
|
|
|
698 if (current_loops != NULL
|
|
|
699 && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
|
|
|
700 repair_loop_structures ();
|
|
|
701
|
|
|
702 return changed;
|
|
|
703 }
|
|
|
704
|
|
|
705 /* Merge the PHI nodes at BB into those at BB's sole successor. */
|
|
|
706
|
|
|
707 static void
|
|
|
708 remove_forwarder_block_with_phi (basic_block bb)
|
|
|
709 {
|
|
|
710 edge succ = single_succ_edge (bb);
|
|
|
711 basic_block dest = succ->dest;
|
|
|
712 gimple label;
|
|
|
713 basic_block dombb, domdest, dom;
|
|
|
714
|
|
|
715 /* We check for infinite loops already in tree_forwarder_block_p.
|
|
|
716 However it may happen that the infinite loop is created
|
|
|
717 afterwards due to removal of forwarders. */
|
|
|
718 if (dest == bb)
|
|
|
719 return;
|
|
|
720
|
|
|
721 /* If the destination block consists of a nonlocal label, do not
|
|
|
722 merge it. */
|
|
|
723 label = first_stmt (dest);
|
|
|
724 if (label
|
|
|
725 && gimple_code (label) == GIMPLE_LABEL
|
|
|
726 && DECL_NONLOCAL (gimple_label_label (label)))
|
|
|
727 return;
|
|
|
728
|
|
|
729 /* Redirect each incoming edge to BB to DEST. */
|
|
|
730 while (EDGE_COUNT (bb->preds) > 0)
|
|
|
731 {
|
|
|
732 edge e = EDGE_PRED (bb, 0), s;
|
|
|
733 gimple_stmt_iterator gsi;
|
|
|
734
|
|
|
735 s = find_edge (e->src, dest);
|
|
|
736 if (s)
|
|
|
737 {
|
|
|
738 /* We already have an edge S from E->src to DEST. If S and
|
|
|
739 E->dest's sole successor edge have the same PHI arguments
|
|
|
740 at DEST, redirect S to DEST. */
|
|
|
741 if (phi_alternatives_equal (dest, s, succ))
|
|
|
742 {
|
|
|
743 e = redirect_edge_and_branch (e, dest);
|
|
|
744 redirect_edge_var_map_clear (e);
|
|
|
745 continue;
|
|
|
746 }
|
|
|
747
|
|
|
748 /* PHI arguments are different. Create a forwarder block by
|
|
|
749 splitting E so that we can merge PHI arguments on E to
|
|
|
750 DEST. */
|
|
|
751 e = single_succ_edge (split_edge (e));
|
|
|
752 }
|
|
|
753
|
|
|
754 s = redirect_edge_and_branch (e, dest);
|
|
|
755
|
|
|
756 /* redirect_edge_and_branch must not create a new edge. */
|
|
|
757 gcc_assert (s == e);
|
|
|
758
|
|
|
759 /* Add to the PHI nodes at DEST each PHI argument removed at the
|
|
|
760 destination of E. */
|
|
|
761 for (gsi = gsi_start_phis (dest);
|
|
|
762 !gsi_end_p (gsi);
|
|
|
763 gsi_next (&gsi))
|
|
|
764 {
|
|
|
765 gimple phi = gsi_stmt (gsi);
|
|
|
766 tree def = gimple_phi_arg_def (phi, succ->dest_idx);
|
|
|
767
|
|
|
768 if (TREE_CODE (def) == SSA_NAME)
|
|
|
769 {
|
|
|
770 edge_var_map_vector head;
|
|
|
771 edge_var_map *vm;
|
|
|
772 size_t i;
|
|
|
773
|
|
|
774 /* If DEF is one of the results of PHI nodes removed during
|
|
|
775 redirection, replace it with the PHI argument that used
|
|
|
776 to be on E. */
|
|
|
777 head = redirect_edge_var_map_vector (e);
|
|
|
778 for (i = 0; VEC_iterate (edge_var_map, head, i, vm); ++i)
|
|
|
779 {
|
|
|
780 tree old_arg = redirect_edge_var_map_result (vm);
|
|
|
781 tree new_arg = redirect_edge_var_map_def (vm);
|
|
|
782
|
|
|
783 if (def == old_arg)
|
|
|
784 {
|
|
|
785 def = new_arg;
|
|
|
786 break;
|
|
|
787 }
|
|
|
788 }
|
|
|
789 }
|
|
|
790
|
|
|
791 add_phi_arg (phi, def, s);
|
|
|
792 }
|
|
|
793
|
|
|
794 redirect_edge_var_map_clear (e);
|
|
|
795 }
|
|
|
796
|
|
|
797 /* Update the dominators. */
|
|
|
798 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
|
|
|
799 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
|
|
|
800 if (domdest == bb)
|
|
|
801 {
|
|
|
802 /* Shortcut to avoid calling (relatively expensive)
|
|
|
803 nearest_common_dominator unless necessary. */
|
|
|
804 dom = dombb;
|
|
|
805 }
|
|
|
806 else
|
|
|
807 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
|
|
|
808
|
|
|
809 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
|
|
|
810
|
|
|
811 /* Remove BB since all of BB's incoming edges have been redirected
|
|
|
812 to DEST. */
|
|
|
813 delete_basic_block (bb);
|
|
|
814 }
|
|
|
815
|
|
|
816 /* This pass merges PHI nodes if one feeds into another. For example,
|
|
|
817 suppose we have the following:
|
|
|
818
|
|
|
819 goto <bb 9> (<L9>);
|
|
|
820
|
|
|
821 <L8>:;
|
|
|
822 tem_17 = foo ();
|
|
|
823
|
|
|
824 # tem_6 = PHI <tem_17(8), tem_23(7)>;
|
|
|
825 <L9>:;
|
|
|
826
|
|
|
827 # tem_3 = PHI <tem_6(9), tem_2(5)>;
|
|
|
828 <L10>:;
|
|
|
829
|
|
|
830 Then we merge the first PHI node into the second one like so:
|
|
|
831
|
|
|
832 goto <bb 9> (<L10>);
|
|
|
833
|
|
|
834 <L8>:;
|
|
|
835 tem_17 = foo ();
|
|
|
836
|
|
|
837 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
|
|
|
838 <L10>:;
|
|
|
839 */
|
|
|
840
|
|
|
841 static unsigned int
|
|
|
842 merge_phi_nodes (void)
|
|
|
843 {
|
|
|
844 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks);
|
|
|
845 basic_block *current = worklist;
|
|
|
846 basic_block bb;
|
|
|
847
|
|
|
848 calculate_dominance_info (CDI_DOMINATORS);
|
|
|
849
|
|
|
850 /* Find all PHI nodes that we may be able to merge. */
|
|
|
851 FOR_EACH_BB (bb)
|
|
|
852 {
|
|
|
853 basic_block dest;
|
|
|
854
|
|
|
855 /* Look for a forwarder block with PHI nodes. */
|
|
|
856 if (!tree_forwarder_block_p (bb, true))
|
|
|
857 continue;
|
|
|
858
|
|
|
859 dest = single_succ (bb);
|
|
|
860
|
|
|
861 /* We have to feed into another basic block with PHI
|
|
|
862 nodes. */
|
|
|
863 if (!phi_nodes (dest)
|
|
|
864 /* We don't want to deal with a basic block with
|
|
|
865 abnormal edges. */
|
|
|
866 || has_abnormal_incoming_edge_p (bb))
|
|
|
867 continue;
|
|
|
868
|
|
|
869 if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
|
|
|
870 {
|
|
|
871 /* If BB does not dominate DEST, then the PHI nodes at
|
|
|
872 DEST must be the only users of the results of the PHI
|
|
|
873 nodes at BB. */
|
|
|
874 *current++ = bb;
|
|
|
875 }
|
|
|
876 else
|
|
|
877 {
|
|
|
878 gimple_stmt_iterator gsi;
|
|
|
879 unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
|
|
|
880
|
|
|
881 /* BB dominates DEST. There may be many users of the PHI
|
|
|
882 nodes in BB. However, there is still a trivial case we
|
|
|
883 can handle. If the result of every PHI in BB is used
|
|
|
884 only by a PHI in DEST, then we can trivially merge the
|
|
|
885 PHI nodes from BB into DEST. */
|
|
|
886 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
|
|
|
887 gsi_next (&gsi))
|
|
|
888 {
|
|
|
889 gimple phi = gsi_stmt (gsi);
|
|
|
890 tree result = gimple_phi_result (phi);
|
|
|
891 use_operand_p imm_use;
|
|
|
892 gimple use_stmt;
|
|
|
893
|
|
|
894 /* If the PHI's result is never used, then we can just
|
|
|
895 ignore it. */
|
|
|
896 if (has_zero_uses (result))
|
|
|
897 continue;
|
|
|
898
|
|
|
899 /* Get the single use of the result of this PHI node. */
|
|
|
900 if (!single_imm_use (result, &imm_use, &use_stmt)
|
|
|
901 || gimple_code (use_stmt) != GIMPLE_PHI
|
|
|
902 || gimple_bb (use_stmt) != dest
|
|
|
903 || gimple_phi_arg_def (use_stmt, dest_idx) != result)
|
|
|
904 break;
|
|
|
905 }
|
|
|
906
|
|
|
907 /* If the loop above iterated through all the PHI nodes
|
|
|
908 in BB, then we can merge the PHIs from BB into DEST. */
|
|
|
909 if (gsi_end_p (gsi))
|
|
|
910 *current++ = bb;
|
|
|
911 }
|
|
|
912 }
|
|
|
913
|
|
|
914 /* Now let's drain WORKLIST. */
|
|
|
915 while (current != worklist)
|
|
|
916 {
|
|
|
917 bb = *--current;
|
|
|
918 remove_forwarder_block_with_phi (bb);
|
|
|
919 }
|
|
|
920
|
|
|
921 free (worklist);
|
|
|
922 return 0;
|
|
|
923 }
|
|
|
924
|
|
|
925 static bool
|
|
|
926 gate_merge_phi (void)
|
|
|
927 {
|
|
|
928 return 1;
|
|
|
929 }
|
|
|
930
|
|
|
931 struct gimple_opt_pass pass_merge_phi =
|
|
|
932 {
|
|
|
933 {
|
|
|
934 GIMPLE_PASS,
|
|
|
935 "mergephi", /* name */
|
|
|
936 gate_merge_phi, /* gate */
|
|
|
937 merge_phi_nodes, /* execute */
|
|
|
938 NULL, /* sub */
|
|
|
939 NULL, /* next */
|
|
|
940 0, /* static_pass_number */
|
|
|
941 TV_TREE_MERGE_PHI, /* tv_id */
|
|
|
942 PROP_cfg | PROP_ssa, /* properties_required */
|
|
|
943 0, /* properties_provided */
|
|
|
944 0, /* properties_destroyed */
|
|
|
945 0, /* todo_flags_start */
|
|
|
946 TODO_dump_func | TODO_ggc_collect /* todo_flags_finish */
|
|
|
947 | TODO_verify_ssa
|
|
|
948 }
|
|
|
949 };
|
