|
0
|
1 /* Control flow optimization code for GNU compiler.
|
|
|
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
|
|
|
3 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
|
|
|
4 Free Software Foundation, Inc.
|
|
|
5
|
|
|
6 This file is part of GCC.
|
|
|
7
|
|
|
8 GCC is free software; you can redistribute it and/or modify it under
|
|
|
9 the terms of the GNU General Public License as published by the Free
|
|
|
10 Software Foundation; either version 3, or (at your option) any later
|
|
|
11 version.
|
|
|
12
|
|
|
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
|
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
16 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 /* This file contains optimizer of the control flow. The main entry point is
|
|
|
23 cleanup_cfg. Following optimizations are performed:
|
|
|
24
|
|
|
25 - Unreachable blocks removal
|
|
|
26 - Edge forwarding (edge to the forwarder block is forwarded to its
|
|
|
27 successor. Simplification of the branch instruction is performed by
|
|
|
28 underlying infrastructure so branch can be converted to simplejump or
|
|
|
29 eliminated).
|
|
|
30 - Cross jumping (tail merging)
|
|
|
31 - Conditional jump-around-simplejump simplification
|
|
|
32 - Basic block merging. */
|
|
|
33
|
|
|
34 #include "config.h"
|
|
|
35 #include "system.h"
|
|
|
36 #include "coretypes.h"
|
|
|
37 #include "tm.h"
|
|
|
38 #include "rtl.h"
|
|
|
39 #include "hard-reg-set.h"
|
|
|
40 #include "regs.h"
|
|
|
41 #include "timevar.h"
|
|
|
42 #include "output.h"
|
|
|
43 #include "insn-config.h"
|
|
|
44 #include "flags.h"
|
|
|
45 #include "recog.h"
|
|
|
46 #include "toplev.h"
|
|
|
47 #include "cselib.h"
|
|
|
48 #include "params.h"
|
|
|
49 #include "tm_p.h"
|
|
|
50 #include "target.h"
|
|
|
51 #include "cfglayout.h"
|
|
|
52 #include "emit-rtl.h"
|
|
|
53 #include "tree-pass.h"
|
|
|
54 #include "cfgloop.h"
|
|
|
55 #include "expr.h"
|
|
|
56 #include "df.h"
|
|
|
57 #include "dce.h"
|
|
|
58 #include "dbgcnt.h"
|
|
|
59
|
|
|
60 #define FORWARDER_BLOCK_P(BB) ((BB)->flags & BB_FORWARDER_BLOCK)
|
|
|
61
|
|
|
62 /* Set to true when we are running first pass of try_optimize_cfg loop. */
|
|
|
63 static bool first_pass;
|
|
|
64
|
|
|
65 /* Set to true if crossjumps occured in the latest run of try_optimize_cfg. */
|
|
|
66 static bool crossjumps_occured;
|
|
|
67
|
|
|
68 static bool try_crossjump_to_edge (int, edge, edge);
|
|
|
69 static bool try_crossjump_bb (int, basic_block);
|
|
|
70 static bool outgoing_edges_match (int, basic_block, basic_block);
|
|
|
71 static int flow_find_cross_jump (int, basic_block, basic_block, rtx *, rtx *);
|
|
|
72 static bool old_insns_match_p (int, rtx, rtx);
|
|
|
73
|
|
|
74 static void merge_blocks_move_predecessor_nojumps (basic_block, basic_block);
|
|
|
75 static void merge_blocks_move_successor_nojumps (basic_block, basic_block);
|
|
|
76 static bool try_optimize_cfg (int);
|
|
|
77 static bool try_simplify_condjump (basic_block);
|
|
|
78 static bool try_forward_edges (int, basic_block);
|
|
|
79 static edge thread_jump (edge, basic_block);
|
|
|
80 static bool mark_effect (rtx, bitmap);
|
|
|
81 static void notice_new_block (basic_block);
|
|
|
82 static void update_forwarder_flag (basic_block);
|
|
|
83 static int mentions_nonequal_regs (rtx *, void *);
|
|
|
84 static void merge_memattrs (rtx, rtx);
|
|
|
85
|
|
|
86 /* Set flags for newly created block. */
|
|
|
87
|
|
|
88 static void
|
|
|
89 notice_new_block (basic_block bb)
|
|
|
90 {
|
|
|
91 if (!bb)
|
|
|
92 return;
|
|
|
93
|
|
|
94 if (forwarder_block_p (bb))
|
|
|
95 bb->flags |= BB_FORWARDER_BLOCK;
|
|
|
96 }
|
|
|
97
|
|
|
98 /* Recompute forwarder flag after block has been modified. */
|
|
|
99
|
|
|
100 static void
|
|
|
101 update_forwarder_flag (basic_block bb)
|
|
|
102 {
|
|
|
103 if (forwarder_block_p (bb))
|
|
|
104 bb->flags |= BB_FORWARDER_BLOCK;
|
|
|
105 else
|
|
|
106 bb->flags &= ~BB_FORWARDER_BLOCK;
|
|
|
107 }
|
|
|
108
|
|
|
109 /* Simplify a conditional jump around an unconditional jump.
|
|
|
110 Return true if something changed. */
|
|
|
111
|
|
|
112 static bool
|
|
|
113 try_simplify_condjump (basic_block cbranch_block)
|
|
|
114 {
|
|
|
115 basic_block jump_block, jump_dest_block, cbranch_dest_block;
|
|
|
116 edge cbranch_jump_edge, cbranch_fallthru_edge;
|
|
|
117 rtx cbranch_insn;
|
|
|
118
|
|
|
119 /* Verify that there are exactly two successors. */
|
|
|
120 if (EDGE_COUNT (cbranch_block->succs) != 2)
|
|
|
121 return false;
|
|
|
122
|
|
|
123 /* Verify that we've got a normal conditional branch at the end
|
|
|
124 of the block. */
|
|
|
125 cbranch_insn = BB_END (cbranch_block);
|
|
|
126 if (!any_condjump_p (cbranch_insn))
|
|
|
127 return false;
|
|
|
128
|
|
|
129 cbranch_fallthru_edge = FALLTHRU_EDGE (cbranch_block);
|
|
|
130 cbranch_jump_edge = BRANCH_EDGE (cbranch_block);
|
|
|
131
|
|
|
132 /* The next block must not have multiple predecessors, must not
|
|
|
133 be the last block in the function, and must contain just the
|
|
|
134 unconditional jump. */
|
|
|
135 jump_block = cbranch_fallthru_edge->dest;
|
|
|
136 if (!single_pred_p (jump_block)
|
|
|
137 || jump_block->next_bb == EXIT_BLOCK_PTR
|
|
|
138 || !FORWARDER_BLOCK_P (jump_block))
|
|
|
139 return false;
|
|
|
140 jump_dest_block = single_succ (jump_block);
|
|
|
141
|
|
|
142 /* If we are partitioning hot/cold basic blocks, we don't want to
|
|
|
143 mess up unconditional or indirect jumps that cross between hot
|
|
|
144 and cold sections.
|
|
|
145
|
|
|
146 Basic block partitioning may result in some jumps that appear to
|
|
|
147 be optimizable (or blocks that appear to be mergeable), but which really
|
|
|
148 must be left untouched (they are required to make it safely across
|
|
|
149 partition boundaries). See the comments at the top of
|
|
|
150 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
|
|
|
151
|
|
|
152 if (BB_PARTITION (jump_block) != BB_PARTITION (jump_dest_block)
|
|
|
153 || (cbranch_jump_edge->flags & EDGE_CROSSING))
|
|
|
154 return false;
|
|
|
155
|
|
|
156 /* The conditional branch must target the block after the
|
|
|
157 unconditional branch. */
|
|
|
158 cbranch_dest_block = cbranch_jump_edge->dest;
|
|
|
159
|
|
|
160 if (cbranch_dest_block == EXIT_BLOCK_PTR
|
|
|
161 || !can_fallthru (jump_block, cbranch_dest_block))
|
|
|
162 return false;
|
|
|
163
|
|
|
164 /* Invert the conditional branch. */
|
|
|
165 if (!invert_jump (cbranch_insn, block_label (jump_dest_block), 0))
|
|
|
166 return false;
|
|
|
167
|
|
|
168 if (dump_file)
|
|
|
169 fprintf (dump_file, "Simplifying condjump %i around jump %i\n",
|
|
|
170 INSN_UID (cbranch_insn), INSN_UID (BB_END (jump_block)));
|
|
|
171
|
|
|
172 /* Success. Update the CFG to match. Note that after this point
|
|
|
173 the edge variable names appear backwards; the redirection is done
|
|
|
174 this way to preserve edge profile data. */
|
|
|
175 cbranch_jump_edge = redirect_edge_succ_nodup (cbranch_jump_edge,
|
|
|
176 cbranch_dest_block);
|
|
|
177 cbranch_fallthru_edge = redirect_edge_succ_nodup (cbranch_fallthru_edge,
|
|
|
178 jump_dest_block);
|
|
|
179 cbranch_jump_edge->flags |= EDGE_FALLTHRU;
|
|
|
180 cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU;
|
|
|
181 update_br_prob_note (cbranch_block);
|
|
|
182
|
|
|
183 /* Delete the block with the unconditional jump, and clean up the mess. */
|
|
|
184 delete_basic_block (jump_block);
|
|
|
185 tidy_fallthru_edge (cbranch_jump_edge);
|
|
|
186 update_forwarder_flag (cbranch_block);
|
|
|
187
|
|
|
188 return true;
|
|
|
189 }
|
|
|
190
|
|
|
191 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
|
|
|
192 on register. Used by jump threading. */
|
|
|
193
|
|
|
194 static bool
|
|
|
195 mark_effect (rtx exp, regset nonequal)
|
|
|
196 {
|
|
|
197 int regno;
|
|
|
198 rtx dest;
|
|
|
199 switch (GET_CODE (exp))
|
|
|
200 {
|
|
|
201 /* In case we do clobber the register, mark it as equal, as we know the
|
|
|
202 value is dead so it don't have to match. */
|
|
|
203 case CLOBBER:
|
|
|
204 if (REG_P (XEXP (exp, 0)))
|
|
|
205 {
|
|
|
206 dest = XEXP (exp, 0);
|
|
|
207 regno = REGNO (dest);
|
|
|
208 CLEAR_REGNO_REG_SET (nonequal, regno);
|
|
|
209 if (regno < FIRST_PSEUDO_REGISTER)
|
|
|
210 {
|
|
|
211 int n = hard_regno_nregs[regno][GET_MODE (dest)];
|
|
|
212 while (--n > 0)
|
|
|
213 CLEAR_REGNO_REG_SET (nonequal, regno + n);
|
|
|
214 }
|
|
|
215 }
|
|
|
216 return false;
|
|
|
217
|
|
|
218 case SET:
|
|
|
219 if (rtx_equal_for_cselib_p (SET_DEST (exp), SET_SRC (exp)))
|
|
|
220 return false;
|
|
|
221 dest = SET_DEST (exp);
|
|
|
222 if (dest == pc_rtx)
|
|
|
223 return false;
|
|
|
224 if (!REG_P (dest))
|
|
|
225 return true;
|
|
|
226 regno = REGNO (dest);
|
|
|
227 SET_REGNO_REG_SET (nonequal, regno);
|
|
|
228 if (regno < FIRST_PSEUDO_REGISTER)
|
|
|
229 {
|
|
|
230 int n = hard_regno_nregs[regno][GET_MODE (dest)];
|
|
|
231 while (--n > 0)
|
|
|
232 SET_REGNO_REG_SET (nonequal, regno + n);
|
|
|
233 }
|
|
|
234 return false;
|
|
|
235
|
|
|
236 default:
|
|
|
237 return false;
|
|
|
238 }
|
|
|
239 }
|
|
|
240
|
|
|
241 /* Return nonzero if X is a register set in regset DATA.
|
|
|
242 Called via for_each_rtx. */
|
|
|
243 static int
|
|
|
244 mentions_nonequal_regs (rtx *x, void *data)
|
|
|
245 {
|
|
|
246 regset nonequal = (regset) data;
|
|
|
247 if (REG_P (*x))
|
|
|
248 {
|
|
|
249 int regno;
|
|
|
250
|
|
|
251 regno = REGNO (*x);
|
|
|
252 if (REGNO_REG_SET_P (nonequal, regno))
|
|
|
253 return 1;
|
|
|
254 if (regno < FIRST_PSEUDO_REGISTER)
|
|
|
255 {
|
|
|
256 int n = hard_regno_nregs[regno][GET_MODE (*x)];
|
|
|
257 while (--n > 0)
|
|
|
258 if (REGNO_REG_SET_P (nonequal, regno + n))
|
|
|
259 return 1;
|
|
|
260 }
|
|
|
261 }
|
|
|
262 return 0;
|
|
|
263 }
|
|
|
264 /* Attempt to prove that the basic block B will have no side effects and
|
|
|
265 always continues in the same edge if reached via E. Return the edge
|
|
|
266 if exist, NULL otherwise. */
|
|
|
267
|
|
|
268 static edge
|
|
|
269 thread_jump (edge e, basic_block b)
|
|
|
270 {
|
|
|
271 rtx set1, set2, cond1, cond2, insn;
|
|
|
272 enum rtx_code code1, code2, reversed_code2;
|
|
|
273 bool reverse1 = false;
|
|
|
274 unsigned i;
|
|
|
275 regset nonequal;
|
|
|
276 bool failed = false;
|
|
|
277 reg_set_iterator rsi;
|
|
|
278
|
|
|
279 if (b->flags & BB_NONTHREADABLE_BLOCK)
|
|
|
280 return NULL;
|
|
|
281
|
|
|
282 /* At the moment, we do handle only conditional jumps, but later we may
|
|
|
283 want to extend this code to tablejumps and others. */
|
|
|
284 if (EDGE_COUNT (e->src->succs) != 2)
|
|
|
285 return NULL;
|
|
|
286 if (EDGE_COUNT (b->succs) != 2)
|
|
|
287 {
|
|
|
288 b->flags |= BB_NONTHREADABLE_BLOCK;
|
|
|
289 return NULL;
|
|
|
290 }
|
|
|
291
|
|
|
292 /* Second branch must end with onlyjump, as we will eliminate the jump. */
|
|
|
293 if (!any_condjump_p (BB_END (e->src)))
|
|
|
294 return NULL;
|
|
|
295
|
|
|
296 if (!any_condjump_p (BB_END (b)) || !onlyjump_p (BB_END (b)))
|
|
|
297 {
|
|
|
298 b->flags |= BB_NONTHREADABLE_BLOCK;
|
|
|
299 return NULL;
|
|
|
300 }
|
|
|
301
|
|
|
302 set1 = pc_set (BB_END (e->src));
|
|
|
303 set2 = pc_set (BB_END (b));
|
|
|
304 if (((e->flags & EDGE_FALLTHRU) != 0)
|
|
|
305 != (XEXP (SET_SRC (set1), 1) == pc_rtx))
|
|
|
306 reverse1 = true;
|
|
|
307
|
|
|
308 cond1 = XEXP (SET_SRC (set1), 0);
|
|
|
309 cond2 = XEXP (SET_SRC (set2), 0);
|
|
|
310 if (reverse1)
|
|
|
311 code1 = reversed_comparison_code (cond1, BB_END (e->src));
|
|
|
312 else
|
|
|
313 code1 = GET_CODE (cond1);
|
|
|
314
|
|
|
315 code2 = GET_CODE (cond2);
|
|
|
316 reversed_code2 = reversed_comparison_code (cond2, BB_END (b));
|
|
|
317
|
|
|
318 if (!comparison_dominates_p (code1, code2)
|
|
|
319 && !comparison_dominates_p (code1, reversed_code2))
|
|
|
320 return NULL;
|
|
|
321
|
|
|
322 /* Ensure that the comparison operators are equivalent.
|
|
|
323 ??? This is far too pessimistic. We should allow swapped operands,
|
|
|
324 different CCmodes, or for example comparisons for interval, that
|
|
|
325 dominate even when operands are not equivalent. */
|
|
|
326 if (!rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
|
|
|
327 || !rtx_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
|
|
|
328 return NULL;
|
|
|
329
|
|
|
330 /* Short circuit cases where block B contains some side effects, as we can't
|
|
|
331 safely bypass it. */
|
|
|
332 for (insn = NEXT_INSN (BB_HEAD (b)); insn != NEXT_INSN (BB_END (b));
|
|
|
333 insn = NEXT_INSN (insn))
|
|
|
334 if (INSN_P (insn) && side_effects_p (PATTERN (insn)))
|
|
|
335 {
|
|
|
336 b->flags |= BB_NONTHREADABLE_BLOCK;
|
|
|
337 return NULL;
|
|
|
338 }
|
|
|
339
|
|
|
340 cselib_init (false);
|
|
|
341
|
|
|
342 /* First process all values computed in the source basic block. */
|
|
|
343 for (insn = NEXT_INSN (BB_HEAD (e->src));
|
|
|
344 insn != NEXT_INSN (BB_END (e->src));
|
|
|
345 insn = NEXT_INSN (insn))
|
|
|
346 if (INSN_P (insn))
|
|
|
347 cselib_process_insn (insn);
|
|
|
348
|
|
|
349 nonequal = BITMAP_ALLOC (NULL);
|
|
|
350 CLEAR_REG_SET (nonequal);
|
|
|
351
|
|
|
352 /* Now assume that we've continued by the edge E to B and continue
|
|
|
353 processing as if it were same basic block.
|
|
|
354 Our goal is to prove that whole block is an NOOP. */
|
|
|
355
|
|
|
356 for (insn = NEXT_INSN (BB_HEAD (b));
|
|
|
357 insn != NEXT_INSN (BB_END (b)) && !failed;
|
|
|
358 insn = NEXT_INSN (insn))
|
|
|
359 {
|
|
|
360 if (INSN_P (insn))
|
|
|
361 {
|
|
|
362 rtx pat = PATTERN (insn);
|
|
|
363
|
|
|
364 if (GET_CODE (pat) == PARALLEL)
|
|
|
365 {
|
|
|
366 for (i = 0; i < (unsigned)XVECLEN (pat, 0); i++)
|
|
|
367 failed |= mark_effect (XVECEXP (pat, 0, i), nonequal);
|
|
|
368 }
|
|
|
369 else
|
|
|
370 failed |= mark_effect (pat, nonequal);
|
|
|
371 }
|
|
|
372
|
|
|
373 cselib_process_insn (insn);
|
|
|
374 }
|
|
|
375
|
|
|
376 /* Later we should clear nonequal of dead registers. So far we don't
|
|
|
377 have life information in cfg_cleanup. */
|
|
|
378 if (failed)
|
|
|
379 {
|
|
|
380 b->flags |= BB_NONTHREADABLE_BLOCK;
|
|
|
381 goto failed_exit;
|
|
|
382 }
|
|
|
383
|
|
|
384 /* cond2 must not mention any register that is not equal to the
|
|
|
385 former block. */
|
|
|
386 if (for_each_rtx (&cond2, mentions_nonequal_regs, nonequal))
|
|
|
387 goto failed_exit;
|
|
|
388
|
|
|
389 EXECUTE_IF_SET_IN_REG_SET (nonequal, 0, i, rsi)
|
|
|
390 goto failed_exit;
|
|
|
391
|
|
|
392 BITMAP_FREE (nonequal);
|
|
|
393 cselib_finish ();
|
|
|
394 if ((comparison_dominates_p (code1, code2) != 0)
|
|
|
395 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
|
|
|
396 return BRANCH_EDGE (b);
|
|
|
397 else
|
|
|
398 return FALLTHRU_EDGE (b);
|
|
|
399
|
|
|
400 failed_exit:
|
|
|
401 BITMAP_FREE (nonequal);
|
|
|
402 cselib_finish ();
|
|
|
403 return NULL;
|
|
|
404 }
|
|
|
405
|
|
|
406 /* Attempt to forward edges leaving basic block B.
|
|
|
407 Return true if successful. */
|
|
|
408
|
|
|
409 static bool
|
|
|
410 try_forward_edges (int mode, basic_block b)
|
|
|
411 {
|
|
|
412 bool changed = false;
|
|
|
413 edge_iterator ei;
|
|
|
414 edge e, *threaded_edges = NULL;
|
|
|
415
|
|
|
416 /* If we are partitioning hot/cold basic blocks, we don't want to
|
|
|
417 mess up unconditional or indirect jumps that cross between hot
|
|
|
418 and cold sections.
|
|
|
419
|
|
|
420 Basic block partitioning may result in some jumps that appear to
|
|
|
421 be optimizable (or blocks that appear to be mergeable), but which really
|
|
|
422 must be left untouched (they are required to make it safely across
|
|
|
423 partition boundaries). See the comments at the top of
|
|
|
424 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
|
|
|
425
|
|
|
426 if (find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX))
|
|
|
427 return false;
|
|
|
428
|
|
|
429 for (ei = ei_start (b->succs); (e = ei_safe_edge (ei)); )
|
|
|
430 {
|
|
|
431 basic_block target, first;
|
|
|
432 int counter, goto_locus;
|
|
|
433 bool threaded = false;
|
|
|
434 int nthreaded_edges = 0;
|
|
|
435 bool may_thread = first_pass | df_get_bb_dirty (b);
|
|
|
436
|
|
|
437 /* Skip complex edges because we don't know how to update them.
|
|
|
438
|
|
|
439 Still handle fallthru edges, as we can succeed to forward fallthru
|
|
|
440 edge to the same place as the branch edge of conditional branch
|
|
|
441 and turn conditional branch to an unconditional branch. */
|
|
|
442 if (e->flags & EDGE_COMPLEX)
|
|
|
443 {
|
|
|
444 ei_next (&ei);
|
|
|
445 continue;
|
|
|
446 }
|
|
|
447
|
|
|
448 target = first = e->dest;
|
|
|
449 counter = NUM_FIXED_BLOCKS;
|
|
|
450 goto_locus = e->goto_locus;
|
|
|
451
|
|
|
452 /* If we are partitioning hot/cold basic_blocks, we don't want to mess
|
|
|
453 up jumps that cross between hot/cold sections.
|
|
|
454
|
|
|
455 Basic block partitioning may result in some jumps that appear
|
|
|
456 to be optimizable (or blocks that appear to be mergeable), but which
|
|
|
457 really must be left untouched (they are required to make it safely
|
|
|
458 across partition boundaries). See the comments at the top of
|
|
|
459 bb-reorder.c:partition_hot_cold_basic_blocks for complete
|
|
|
460 details. */
|
|
|
461
|
|
|
462 if (first != EXIT_BLOCK_PTR
|
|
|
463 && find_reg_note (BB_END (first), REG_CROSSING_JUMP, NULL_RTX))
|
|
|
464 return false;
|
|
|
465
|
|
|
466 while (counter < n_basic_blocks)
|
|
|
467 {
|
|
|
468 basic_block new_target = NULL;
|
|
|
469 bool new_target_threaded = false;
|
|
|
470 may_thread |= df_get_bb_dirty (target);
|
|
|
471
|
|
|
472 if (FORWARDER_BLOCK_P (target)
|
|
|
473 && !(single_succ_edge (target)->flags & EDGE_CROSSING)
|
|
|
474 && single_succ (target) != EXIT_BLOCK_PTR)
|
|
|
475 {
|
|
|
476 /* Bypass trivial infinite loops. */
|
|
|
477 new_target = single_succ (target);
|
|
|
478 if (target == new_target)
|
|
|
479 counter = n_basic_blocks;
|
|
|
480 else if (!optimize)
|
|
|
481 {
|
|
|
482 /* When not optimizing, ensure that edges or forwarder
|
|
|
483 blocks with different locus are not optimized out. */
|
|
|
484 int locus = single_succ_edge (target)->goto_locus;
|
|
|
485
|
|
|
486 if (locus && goto_locus && !locator_eq (locus, goto_locus))
|
|
|
487 counter = n_basic_blocks;
|
|
|
488 else if (locus)
|
|
|
489 goto_locus = locus;
|
|
|
490
|
|
|
491 if (INSN_P (BB_END (target)))
|
|
|
492 {
|
|
|
493 locus = INSN_LOCATOR (BB_END (target));
|
|
|
494
|
|
|
495 if (locus && goto_locus
|
|
|
496 && !locator_eq (locus, goto_locus))
|
|
|
497 counter = n_basic_blocks;
|
|
|
498 else if (locus)
|
|
|
499 goto_locus = locus;
|
|
|
500 }
|
|
|
501 }
|
|
|
502 }
|
|
|
503
|
|
|
504 /* Allow to thread only over one edge at time to simplify updating
|
|
|
505 of probabilities. */
|
|
|
506 else if ((mode & CLEANUP_THREADING) && may_thread)
|
|
|
507 {
|
|
|
508 edge t = thread_jump (e, target);
|
|
|
509 if (t)
|
|
|
510 {
|
|
|
511 if (!threaded_edges)
|
|
|
512 threaded_edges = XNEWVEC (edge, n_basic_blocks);
|
|
|
513 else
|
|
|
514 {
|
|
|
515 int i;
|
|
|
516
|
|
|
517 /* Detect an infinite loop across blocks not
|
|
|
518 including the start block. */
|
|
|
519 for (i = 0; i < nthreaded_edges; ++i)
|
|
|
520 if (threaded_edges[i] == t)
|
|
|
521 break;
|
|
|
522 if (i < nthreaded_edges)
|
|
|
523 {
|
|
|
524 counter = n_basic_blocks;
|
|
|
525 break;
|
|
|
526 }
|
|
|
527 }
|
|
|
528
|
|
|
529 /* Detect an infinite loop across the start block. */
|
|
|
530 if (t->dest == b)
|
|
|
531 break;
|
|
|
532
|
|
|
533 gcc_assert (nthreaded_edges < n_basic_blocks - NUM_FIXED_BLOCKS);
|
|
|
534 threaded_edges[nthreaded_edges++] = t;
|
|
|
535
|
|
|
536 new_target = t->dest;
|
|
|
537 new_target_threaded = true;
|
|
|
538 }
|
|
|
539 }
|
|
|
540
|
|
|
541 if (!new_target)
|
|
|
542 break;
|
|
|
543
|
|
|
544 counter++;
|
|
|
545 target = new_target;
|
|
|
546 threaded |= new_target_threaded;
|
|
|
547 }
|
|
|
548
|
|
|
549 if (counter >= n_basic_blocks)
|
|
|
550 {
|
|
|
551 if (dump_file)
|
|
|
552 fprintf (dump_file, "Infinite loop in BB %i.\n",
|
|
|
553 target->index);
|
|
|
554 }
|
|
|
555 else if (target == first)
|
|
|
556 ; /* We didn't do anything. */
|
|
|
557 else
|
|
|
558 {
|
|
|
559 /* Save the values now, as the edge may get removed. */
|
|
|
560 gcov_type edge_count = e->count;
|
|
|
561 int edge_probability = e->probability;
|
|
|
562 int edge_frequency;
|
|
|
563 int n = 0;
|
|
|
564
|
|
|
565 e->goto_locus = goto_locus;
|
|
|
566
|
|
|
567 /* Don't force if target is exit block. */
|
|
|
568 if (threaded && target != EXIT_BLOCK_PTR)
|
|
|
569 {
|
|
|
570 notice_new_block (redirect_edge_and_branch_force (e, target));
|
|
|
571 if (dump_file)
|
|
|
572 fprintf (dump_file, "Conditionals threaded.\n");
|
|
|
573 }
|
|
|
574 else if (!redirect_edge_and_branch (e, target))
|
|
|
575 {
|
|
|
576 if (dump_file)
|
|
|
577 fprintf (dump_file,
|
|
|
578 "Forwarding edge %i->%i to %i failed.\n",
|
|
|
579 b->index, e->dest->index, target->index);
|
|
|
580 ei_next (&ei);
|
|
|
581 continue;
|
|
|
582 }
|
|
|
583
|
|
|
584 /* We successfully forwarded the edge. Now update profile
|
|
|
585 data: for each edge we traversed in the chain, remove
|
|
|
586 the original edge's execution count. */
|
|
|
587 edge_frequency = ((edge_probability * b->frequency
|
|
|
588 + REG_BR_PROB_BASE / 2)
|
|
|
589 / REG_BR_PROB_BASE);
|
|
|
590
|
|
|
591 if (!FORWARDER_BLOCK_P (b) && forwarder_block_p (b))
|
|
|
592 b->flags |= BB_FORWARDER_BLOCK;
|
|
|
593
|
|
|
594 do
|
|
|
595 {
|
|
|
596 edge t;
|
|
|
597
|
|
|
598 if (!single_succ_p (first))
|
|
|
599 {
|
|
|
600 gcc_assert (n < nthreaded_edges);
|
|
|
601 t = threaded_edges [n++];
|
|
|
602 gcc_assert (t->src == first);
|
|
|
603 update_bb_profile_for_threading (first, edge_frequency,
|
|
|
604 edge_count, t);
|
|
|
605 update_br_prob_note (first);
|
|
|
606 }
|
|
|
607 else
|
|
|
608 {
|
|
|
609 first->count -= edge_count;
|
|
|
610 if (first->count < 0)
|
|
|
611 first->count = 0;
|
|
|
612 first->frequency -= edge_frequency;
|
|
|
613 if (first->frequency < 0)
|
|
|
614 first->frequency = 0;
|
|
|
615 /* It is possible that as the result of
|
|
|
616 threading we've removed edge as it is
|
|
|
617 threaded to the fallthru edge. Avoid
|
|
|
618 getting out of sync. */
|
|
|
619 if (n < nthreaded_edges
|
|
|
620 && first == threaded_edges [n]->src)
|
|
|
621 n++;
|
|
|
622 t = single_succ_edge (first);
|
|
|
623 }
|
|
|
624
|
|
|
625 t->count -= edge_count;
|
|
|
626 if (t->count < 0)
|
|
|
627 t->count = 0;
|
|
|
628 first = t->dest;
|
|
|
629 }
|
|
|
630 while (first != target);
|
|
|
631
|
|
|
632 changed = true;
|
|
|
633 continue;
|
|
|
634 }
|
|
|
635 ei_next (&ei);
|
|
|
636 }
|
|
|
637
|
|
|
638 if (threaded_edges)
|
|
|
639 free (threaded_edges);
|
|
|
640 return changed;
|
|
|
641 }
|
|
|
642
|
|
|
643
|
|
|
644 /* Blocks A and B are to be merged into a single block. A has no incoming
|
|
|
645 fallthru edge, so it can be moved before B without adding or modifying
|
|
|
646 any jumps (aside from the jump from A to B). */
|
|
|
647
|
|
|
648 static void
|
|
|
649 merge_blocks_move_predecessor_nojumps (basic_block a, basic_block b)
|
|
|
650 {
|
|
|
651 rtx barrier;
|
|
|
652
|
|
|
653 /* If we are partitioning hot/cold basic blocks, we don't want to
|
|
|
654 mess up unconditional or indirect jumps that cross between hot
|
|
|
655 and cold sections.
|
|
|
656
|
|
|
657 Basic block partitioning may result in some jumps that appear to
|
|
|
658 be optimizable (or blocks that appear to be mergeable), but which really
|
|
|
659 must be left untouched (they are required to make it safely across
|
|
|
660 partition boundaries). See the comments at the top of
|
|
|
661 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
|
|
|
662
|
|
|
663 if (BB_PARTITION (a) != BB_PARTITION (b))
|
|
|
664 return;
|
|
|
665
|
|
|
666 barrier = next_nonnote_insn (BB_END (a));
|
|
|
667 gcc_assert (BARRIER_P (barrier));
|
|
|
668 delete_insn (barrier);
|
|
|
669
|
|
|
670 /* Scramble the insn chain. */
|
|
|
671 if (BB_END (a) != PREV_INSN (BB_HEAD (b)))
|
|
|
672 reorder_insns_nobb (BB_HEAD (a), BB_END (a), PREV_INSN (BB_HEAD (b)));
|
|
|
673 df_set_bb_dirty (a);
|
|
|
674
|
|
|
675 if (dump_file)
|
|
|
676 fprintf (dump_file, "Moved block %d before %d and merged.\n",
|
|
|
677 a->index, b->index);
|
|
|
678
|
|
|
679 /* Swap the records for the two blocks around. */
|
|
|
680
|
|
|
681 unlink_block (a);
|
|
|
682 link_block (a, b->prev_bb);
|
|
|
683
|
|
|
684 /* Now blocks A and B are contiguous. Merge them. */
|
|
|
685 merge_blocks (a, b);
|
|
|
686 }
|
|
|
687
|
|
|
688 /* Blocks A and B are to be merged into a single block. B has no outgoing
|
|
|
689 fallthru edge, so it can be moved after A without adding or modifying
|
|
|
690 any jumps (aside from the jump from A to B). */
|
|
|
691
|
|
|
692 static void
|
|
|
693 merge_blocks_move_successor_nojumps (basic_block a, basic_block b)
|
|
|
694 {
|
|
|
695 rtx barrier, real_b_end;
|
|
|
696 rtx label, table;
|
|
|
697
|
|
|
698 /* If we are partitioning hot/cold basic blocks, we don't want to
|
|
|
699 mess up unconditional or indirect jumps that cross between hot
|
|
|
700 and cold sections.
|
|
|
701
|
|
|
702 Basic block partitioning may result in some jumps that appear to
|
|
|
703 be optimizable (or blocks that appear to be mergeable), but which really
|
|
|
704 must be left untouched (they are required to make it safely across
|
|
|
705 partition boundaries). See the comments at the top of
|
|
|
706 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
|
|
|
707
|
|
|
708 if (BB_PARTITION (a) != BB_PARTITION (b))
|
|
|
709 return;
|
|
|
710
|
|
|
711 real_b_end = BB_END (b);
|
|
|
712
|
|
|
713 /* If there is a jump table following block B temporarily add the jump table
|
|
|
714 to block B so that it will also be moved to the correct location. */
|
|
|
715 if (tablejump_p (BB_END (b), &label, &table)
|
|
|
716 && prev_active_insn (label) == BB_END (b))
|
|
|
717 {
|
|
|
718 BB_END (b) = table;
|
|
|
719 }
|
|
|
720
|
|
|
721 /* There had better have been a barrier there. Delete it. */
|
|
|
722 barrier = NEXT_INSN (BB_END (b));
|
|
|
723 if (barrier && BARRIER_P (barrier))
|
|
|
724 delete_insn (barrier);
|
|
|
725
|
|
|
726
|
|
|
727 /* Scramble the insn chain. */
|
|
|
728 reorder_insns_nobb (BB_HEAD (b), BB_END (b), BB_END (a));
|
|
|
729
|
|
|
730 /* Restore the real end of b. */
|
|
|
731 BB_END (b) = real_b_end;
|
|
|
732
|
|
|
733 if (dump_file)
|
|
|
734 fprintf (dump_file, "Moved block %d after %d and merged.\n",
|
|
|
735 b->index, a->index);
|
|
|
736
|
|
|
737 /* Now blocks A and B are contiguous. Merge them. */
|
|
|
738 merge_blocks (a, b);
|
|
|
739 }
|
|
|
740
|
|
|
741 /* Attempt to merge basic blocks that are potentially non-adjacent.
|
|
|
742 Return NULL iff the attempt failed, otherwise return basic block
|
|
|
743 where cleanup_cfg should continue. Because the merging commonly
|
|
|
744 moves basic block away or introduces another optimization
|
|
|
745 possibility, return basic block just before B so cleanup_cfg don't
|
|
|
746 need to iterate.
|
|
|
747
|
|
|
748 It may be good idea to return basic block before C in the case
|
|
|
749 C has been moved after B and originally appeared earlier in the
|
|
|
750 insn sequence, but we have no information available about the
|
|
|
751 relative ordering of these two. Hopefully it is not too common. */
|
|
|
752
|
|
|
753 static basic_block
|
|
|
754 merge_blocks_move (edge e, basic_block b, basic_block c, int mode)
|
|
|
755 {
|
|
|
756 basic_block next;
|
|
|
757
|
|
|
758 /* If we are partitioning hot/cold basic blocks, we don't want to
|
|
|
759 mess up unconditional or indirect jumps that cross between hot
|
|
|
760 and cold sections.
|
|
|
761
|
|
|
762 Basic block partitioning may result in some jumps that appear to
|
|
|
763 be optimizable (or blocks that appear to be mergeable), but which really
|
|
|
764 must be left untouched (they are required to make it safely across
|
|
|
765 partition boundaries). See the comments at the top of
|
|
|
766 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
|
|
|
767
|
|
|
768 if (BB_PARTITION (b) != BB_PARTITION (c))
|
|
|
769 return NULL;
|
|
|
770
|
|
|
771 /* If B has a fallthru edge to C, no need to move anything. */
|
|
|
772 if (e->flags & EDGE_FALLTHRU)
|
|
|
773 {
|
|
|
774 int b_index = b->index, c_index = c->index;
|
|
|
775 merge_blocks (b, c);
|
|
|
776 update_forwarder_flag (b);
|
|
|
777
|
|
|
778 if (dump_file)
|
|
|
779 fprintf (dump_file, "Merged %d and %d without moving.\n",
|
|
|
780 b_index, c_index);
|
|
|
781
|
|
|
782 return b->prev_bb == ENTRY_BLOCK_PTR ? b : b->prev_bb;
|
|
|
783 }
|
|
|
784
|
|
|
785 /* Otherwise we will need to move code around. Do that only if expensive
|
|
|
786 transformations are allowed. */
|
|
|
787 else if (mode & CLEANUP_EXPENSIVE)
|
|
|
788 {
|
|
|
789 edge tmp_edge, b_fallthru_edge;
|
|
|
790 bool c_has_outgoing_fallthru;
|
|
|
791 bool b_has_incoming_fallthru;
|
|
|
792 edge_iterator ei;
|
|
|
793
|
|
|
794 /* Avoid overactive code motion, as the forwarder blocks should be
|
|
|
795 eliminated by edge redirection instead. One exception might have
|
|
|
796 been if B is a forwarder block and C has no fallthru edge, but
|
|
|
797 that should be cleaned up by bb-reorder instead. */
|
|
|
798 if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c))
|
|
|
799 return NULL;
|
|
|
800
|
|
|
801 /* We must make sure to not munge nesting of lexical blocks,
|
|
|
802 and loop notes. This is done by squeezing out all the notes
|
|
|
803 and leaving them there to lie. Not ideal, but functional. */
|
|
|
804
|
|
|
805 FOR_EACH_EDGE (tmp_edge, ei, c->succs)
|
|
|
806 if (tmp_edge->flags & EDGE_FALLTHRU)
|
|
|
807 break;
|
|
|
808
|
|
|
809 c_has_outgoing_fallthru = (tmp_edge != NULL);
|
|
|
810
|
|
|
811 FOR_EACH_EDGE (tmp_edge, ei, b->preds)
|
|
|
812 if (tmp_edge->flags & EDGE_FALLTHRU)
|
|
|
813 break;
|
|
|
814
|
|
|
815 b_has_incoming_fallthru = (tmp_edge != NULL);
|
|
|
816 b_fallthru_edge = tmp_edge;
|
|
|
817 next = b->prev_bb;
|
|
|
818 if (next == c)
|
|
|
819 next = next->prev_bb;
|
|
|
820
|
|
|
821 /* Otherwise, we're going to try to move C after B. If C does
|
|
|
822 not have an outgoing fallthru, then it can be moved
|
|
|
823 immediately after B without introducing or modifying jumps. */
|
|
|
824 if (! c_has_outgoing_fallthru)
|
|
|
825 {
|
|
|
826 merge_blocks_move_successor_nojumps (b, c);
|
|
|
827 return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
|
|
|
828 }
|
|
|
829
|
|
|
830 /* If B does not have an incoming fallthru, then it can be moved
|
|
|
831 immediately before C without introducing or modifying jumps.
|
|
|
832 C cannot be the first block, so we do not have to worry about
|
|
|
833 accessing a non-existent block. */
|
|
|
834
|
|
|
835 if (b_has_incoming_fallthru)
|
|
|
836 {
|
|
|
837 basic_block bb;
|
|
|
838
|
|
|
839 if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
|
|
|
840 return NULL;
|
|
|
841 bb = force_nonfallthru (b_fallthru_edge);
|
|
|
842 if (bb)
|
|
|
843 notice_new_block (bb);
|
|
|
844 }
|
|
|
845
|
|
|
846 merge_blocks_move_predecessor_nojumps (b, c);
|
|
|
847 return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
|
|
|
848 }
|
|
|
849
|
|
|
850 return NULL;
|
|
|
851 }
|
|
|
852
|
|
|
853
|
|
|
854 /* Removes the memory attributes of MEM expression
|
|
|
855 if they are not equal. */
|
|
|
856
|
|
|
857 void
|
|
|
858 merge_memattrs (rtx x, rtx y)
|
|
|
859 {
|
|
|
860 int i;
|
|
|
861 int j;
|
|
|
862 enum rtx_code code;
|
|
|
863 const char *fmt;
|
|
|
864
|
|
|
865 if (x == y)
|
|
|
866 return;
|
|
|
867 if (x == 0 || y == 0)
|
|
|
868 return;
|
|
|
869
|
|
|
870 code = GET_CODE (x);
|
|
|
871
|
|
|
872 if (code != GET_CODE (y))
|
|
|
873 return;
|
|
|
874
|
|
|
875 if (GET_MODE (x) != GET_MODE (y))
|
|
|
876 return;
|
|
|
877
|
|
|
878 if (code == MEM && MEM_ATTRS (x) != MEM_ATTRS (y))
|
|
|
879 {
|
|
|
880 if (! MEM_ATTRS (x))
|
|
|
881 MEM_ATTRS (y) = 0;
|
|
|
882 else if (! MEM_ATTRS (y))
|
|
|
883 MEM_ATTRS (x) = 0;
|
|
|
884 else
|
|
|
885 {
|
|
|
886 rtx mem_size;
|
|
|
887
|
|
|
888 if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
|
|
|
889 {
|
|
|
890 set_mem_alias_set (x, 0);
|
|
|
891 set_mem_alias_set (y, 0);
|
|
|
892 }
|
|
|
893
|
|
|
894 if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y)))
|
|
|
895 {
|
|
|
896 set_mem_expr (x, 0);
|
|
|
897 set_mem_expr (y, 0);
|
|
|
898 set_mem_offset (x, 0);
|
|
|
899 set_mem_offset (y, 0);
|
|
|
900 }
|
|
|
901 else if (MEM_OFFSET (x) != MEM_OFFSET (y))
|
|
|
902 {
|
|
|
903 set_mem_offset (x, 0);
|
|
|
904 set_mem_offset (y, 0);
|
|
|
905 }
|
|
|
906
|
|
|
907 if (!MEM_SIZE (x))
|
|
|
908 mem_size = NULL_RTX;
|
|
|
909 else if (!MEM_SIZE (y))
|
|
|
910 mem_size = NULL_RTX;
|
|
|
911 else
|
|
|
912 mem_size = GEN_INT (MAX (INTVAL (MEM_SIZE (x)),
|
|
|
913 INTVAL (MEM_SIZE (y))));
|
|
|
914 set_mem_size (x, mem_size);
|
|
|
915 set_mem_size (y, mem_size);
|
|
|
916
|
|
|
917 set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y)));
|
|
|
918 set_mem_align (y, MEM_ALIGN (x));
|
|
|
919 }
|
|
|
920 }
|
|
|
921
|
|
|
922 fmt = GET_RTX_FORMAT (code);
|
|
|
923 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
|
|
|
924 {
|
|
|
925 switch (fmt[i])
|
|
|
926 {
|
|
|
927 case 'E':
|
|
|
928 /* Two vectors must have the same length. */
|
|
|
929 if (XVECLEN (x, i) != XVECLEN (y, i))
|
|
|
930 return;
|
|
|
931
|
|
|
932 for (j = 0; j < XVECLEN (x, i); j++)
|
|
|
933 merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j));
|
|
|
934
|
|
|
935 break;
|
|
|
936
|
|
|
937 case 'e':
|
|
|
938 merge_memattrs (XEXP (x, i), XEXP (y, i));
|
|
|
939 }
|
|
|
940 }
|
|
|
941 return;
|
|
|
942 }
|
|
|
943
|
|
|
944
|
|
|
945 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
|
|
|
946
|
|
|
947 static bool
|
|
|
948 old_insns_match_p (int mode ATTRIBUTE_UNUSED, rtx i1, rtx i2)
|
|
|
949 {
|
|
|
950 rtx p1, p2;
|
|
|
951
|
|
|
952 /* Verify that I1 and I2 are equivalent. */
|
|
|
953 if (GET_CODE (i1) != GET_CODE (i2))
|
|
|
954 return false;
|
|
|
955
|
|
|
956 p1 = PATTERN (i1);
|
|
|
957 p2 = PATTERN (i2);
|
|
|
958
|
|
|
959 if (GET_CODE (p1) != GET_CODE (p2))
|
|
|
960 return false;
|
|
|
961
|
|
|
962 /* If this is a CALL_INSN, compare register usage information.
|
|
|
963 If we don't check this on stack register machines, the two
|
|
|
964 CALL_INSNs might be merged leaving reg-stack.c with mismatching
|
|
|
965 numbers of stack registers in the same basic block.
|
|
|
966 If we don't check this on machines with delay slots, a delay slot may
|
|
|
967 be filled that clobbers a parameter expected by the subroutine.
|
|
|
968
|
|
|
969 ??? We take the simple route for now and assume that if they're
|
|
|
970 equal, they were constructed identically. */
|
|
|
971
|
|
|
972 if (CALL_P (i1)
|
|
|
973 && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
|
|
|
974 CALL_INSN_FUNCTION_USAGE (i2))
|
|
|
975 || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)))
|
|
|
976 return false;
|
|
|
977
|
|
|
978 #ifdef STACK_REGS
|
|
|
979 /* If cross_jump_death_matters is not 0, the insn's mode
|
|
|
980 indicates whether or not the insn contains any stack-like
|
|
|
981 regs. */
|
|
|
982
|
|
|
983 if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
|
|
|
984 {
|
|
|
985 /* If register stack conversion has already been done, then
|
|
|
986 death notes must also be compared before it is certain that
|
|
|
987 the two instruction streams match. */
|
|
|
988
|
|
|
989 rtx note;
|
|
|
990 HARD_REG_SET i1_regset, i2_regset;
|
|
|
991
|
|
|
992 CLEAR_HARD_REG_SET (i1_regset);
|
|
|
993 CLEAR_HARD_REG_SET (i2_regset);
|
|
|
994
|
|
|
995 for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
|
|
|
996 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
|
|
|
997 SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
|
|
|
998
|
|
|
999 for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
|
|
|
1000 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
|
|
|
1001 SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
|
|
|
1002
|
|
|
1003 if (!hard_reg_set_equal_p (i1_regset, i2_regset))
|
|
|
1004 return false;
|
|
|
1005 }
|
|
|
1006 #endif
|
|
|
1007
|
|
|
1008 if (reload_completed
|
|
|
1009 ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2))
|
|
|
1010 return true;
|
|
|
1011
|
|
|
1012 /* Do not do EQUIV substitution after reload. First, we're undoing the
|
|
|
1013 work of reload_cse. Second, we may be undoing the work of the post-
|
|
|
1014 reload splitting pass. */
|
|
|
1015 /* ??? Possibly add a new phase switch variable that can be used by
|
|
|
1016 targets to disallow the troublesome insns after splitting. */
|
|
|
1017 if (!reload_completed)
|
|
|
1018 {
|
|
|
1019 /* The following code helps take care of G++ cleanups. */
|
|
|
1020 rtx equiv1 = find_reg_equal_equiv_note (i1);
|
|
|
1021 rtx equiv2 = find_reg_equal_equiv_note (i2);
|
|
|
1022
|
|
|
1023 if (equiv1 && equiv2
|
|
|
1024 /* If the equivalences are not to a constant, they may
|
|
|
1025 reference pseudos that no longer exist, so we can't
|
|
|
1026 use them. */
|
|
|
1027 && (! reload_completed
|
|
|
1028 || (CONSTANT_P (XEXP (equiv1, 0))
|
|
|
1029 && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
|
|
|
1030 {
|
|
|
1031 rtx s1 = single_set (i1);
|
|
|
1032 rtx s2 = single_set (i2);
|
|
|
1033 if (s1 != 0 && s2 != 0
|
|
|
1034 && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
|
|
|
1035 {
|
|
|
1036 validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
|
|
|
1037 validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
|
|
|
1038 if (! rtx_renumbered_equal_p (p1, p2))
|
|
|
1039 cancel_changes (0);
|
|
|
1040 else if (apply_change_group ())
|
|
|
1041 return true;
|
|
|
1042 }
|
|
|
1043 }
|
|
|
1044 }
|
|
|
1045
|
|
|
1046 return false;
|
|
|
1047 }
|
|
|
1048
|
|
|
1049 /* Look through the insns at the end of BB1 and BB2 and find the longest
|
|
|
1050 sequence that are equivalent. Store the first insns for that sequence
|
|
|
1051 in *F1 and *F2 and return the sequence length.
|
|
|
1052
|
|
|
1053 To simplify callers of this function, if the blocks match exactly,
|
|
|
1054 store the head of the blocks in *F1 and *F2. */
|
|
|
1055
|
|
|
1056 static int
|
|
|
1057 flow_find_cross_jump (int mode ATTRIBUTE_UNUSED, basic_block bb1,
|
|
|
1058 basic_block bb2, rtx *f1, rtx *f2)
|
|
|
1059 {
|
|
|
1060 rtx i1, i2, last1, last2, afterlast1, afterlast2;
|
|
|
1061 int ninsns = 0;
|
|
|
1062
|
|
|
1063 /* Skip simple jumps at the end of the blocks. Complex jumps still
|
|
|
1064 need to be compared for equivalence, which we'll do below. */
|
|
|
1065
|
|
|
1066 i1 = BB_END (bb1);
|
|
|
1067 last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
|
|
|
1068 if (onlyjump_p (i1)
|
|
|
1069 || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
|
|
|
1070 {
|
|
|
1071 last1 = i1;
|
|
|
1072 i1 = PREV_INSN (i1);
|
|
|
1073 }
|
|
|
1074
|
|
|
1075 i2 = BB_END (bb2);
|
|
|
1076 if (onlyjump_p (i2)
|
|
|
1077 || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
|
|
|
1078 {
|
|
|
1079 last2 = i2;
|
|
|
1080 /* Count everything except for unconditional jump as insn. */
|
|
|
1081 if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
|
|
|
1082 ninsns++;
|
|
|
1083 i2 = PREV_INSN (i2);
|
|
|
1084 }
|
|
|
1085
|
|
|
1086 while (true)
|
|
|
1087 {
|
|
|
1088 /* Ignore notes. */
|
|
|
1089 while (!INSN_P (i1) && i1 != BB_HEAD (bb1))
|
|
|
1090 i1 = PREV_INSN (i1);
|
|
|
1091
|
|
|
1092 while (!INSN_P (i2) && i2 != BB_HEAD (bb2))
|
|
|
1093 i2 = PREV_INSN (i2);
|
|
|
1094
|
|
|
1095 if (i1 == BB_HEAD (bb1) || i2 == BB_HEAD (bb2))
|
|
|
1096 break;
|
|
|
1097
|
|
|
1098 if (!old_insns_match_p (mode, i1, i2))
|
|
|
1099 break;
|
|
|
1100
|
|
|
1101 merge_memattrs (i1, i2);
|
|
|
1102
|
|
|
1103 /* Don't begin a cross-jump with a NOTE insn. */
|
|
|
1104 if (INSN_P (i1))
|
|
|
1105 {
|
|
|
1106 /* If the merged insns have different REG_EQUAL notes, then
|
|
|
1107 remove them. */
|
|
|
1108 rtx equiv1 = find_reg_equal_equiv_note (i1);
|
|
|
1109 rtx equiv2 = find_reg_equal_equiv_note (i2);
|
|
|
1110
|
|
|
1111 if (equiv1 && !equiv2)
|
|
|
1112 remove_note (i1, equiv1);
|
|
|
1113 else if (!equiv1 && equiv2)
|
|
|
1114 remove_note (i2, equiv2);
|
|
|
1115 else if (equiv1 && equiv2
|
|
|
1116 && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
|
|
|
1117 {
|
|
|
1118 remove_note (i1, equiv1);
|
|
|
1119 remove_note (i2, equiv2);
|
|
|
1120 }
|
|
|
1121
|
|
|
1122 afterlast1 = last1, afterlast2 = last2;
|
|
|
1123 last1 = i1, last2 = i2;
|
|
|
1124 ninsns++;
|
|
|
1125 }
|
|
|
1126
|
|
|
1127 i1 = PREV_INSN (i1);
|
|
|
1128 i2 = PREV_INSN (i2);
|
|
|
1129 }
|
|
|
1130
|
|
|
1131 #ifdef HAVE_cc0
|
|
|
1132 /* Don't allow the insn after a compare to be shared by
|
|
|
1133 cross-jumping unless the compare is also shared. */
|
|
|
1134 if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
|
|
|
1135 last1 = afterlast1, last2 = afterlast2, ninsns--;
|
|
|
1136 #endif
|
|
|
1137
|
|
|
1138 /* Include preceding notes and labels in the cross-jump. One,
|
|
|
1139 this may bring us to the head of the blocks as requested above.
|
|
|
1140 Two, it keeps line number notes as matched as may be. */
|
|
|
1141 if (ninsns)
|
|
|
1142 {
|
|
|
1143 while (last1 != BB_HEAD (bb1) && !INSN_P (PREV_INSN (last1)))
|
|
|
1144 last1 = PREV_INSN (last1);
|
|
|
1145
|
|
|
1146 if (last1 != BB_HEAD (bb1) && LABEL_P (PREV_INSN (last1)))
|
|
|
1147 last1 = PREV_INSN (last1);
|
|
|
1148
|
|
|
1149 while (last2 != BB_HEAD (bb2) && !INSN_P (PREV_INSN (last2)))
|
|
|
1150 last2 = PREV_INSN (last2);
|
|
|
1151
|
|
|
1152 if (last2 != BB_HEAD (bb2) && LABEL_P (PREV_INSN (last2)))
|
|
|
1153 last2 = PREV_INSN (last2);
|
|
|
1154
|
|
|
1155 *f1 = last1;
|
|
|
1156 *f2 = last2;
|
|
|
1157 }
|
|
|
1158
|
|
|
1159 return ninsns;
|
|
|
1160 }
|
|
|
1161
|
|
|
1162 /* Return true iff outgoing edges of BB1 and BB2 match, together with
|
|
|
1163 the branch instruction. This means that if we commonize the control
|
|
|
1164 flow before end of the basic block, the semantic remains unchanged.
|
|
|
1165
|
|
|
1166 We may assume that there exists one edge with a common destination. */
|
|
|
1167
|
|
|
1168 static bool
|
|
|
1169 outgoing_edges_match (int mode, basic_block bb1, basic_block bb2)
|
|
|
1170 {
|
|
|
1171 int nehedges1 = 0, nehedges2 = 0;
|
|
|
1172 edge fallthru1 = 0, fallthru2 = 0;
|
|
|
1173 edge e1, e2;
|
|
|
1174 edge_iterator ei;
|
|
|
1175
|
|
|
1176 /* If BB1 has only one successor, we may be looking at either an
|
|
|
1177 unconditional jump, or a fake edge to exit. */
|
|
|
1178 if (single_succ_p (bb1)
|
|
|
1179 && (single_succ_edge (bb1)->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
|
|
|
1180 && (!JUMP_P (BB_END (bb1)) || simplejump_p (BB_END (bb1))))
|
|
|
1181 return (single_succ_p (bb2)
|
|
|
1182 && (single_succ_edge (bb2)->flags
|
|
|
1183 & (EDGE_COMPLEX | EDGE_FAKE)) == 0
|
|
|
1184 && (!JUMP_P (BB_END (bb2)) || simplejump_p (BB_END (bb2))));
|
|
|
1185
|
|
|
1186 /* Match conditional jumps - this may get tricky when fallthru and branch
|
|
|
1187 edges are crossed. */
|
|
|
1188 if (EDGE_COUNT (bb1->succs) == 2
|
|
|
1189 && any_condjump_p (BB_END (bb1))
|
|
|
1190 && onlyjump_p (BB_END (bb1)))
|
|
|
1191 {
|
|
|
1192 edge b1, f1, b2, f2;
|
|
|
1193 bool reverse, match;
|
|
|
1194 rtx set1, set2, cond1, cond2;
|
|
|
1195 enum rtx_code code1, code2;
|
|
|
1196
|
|
|
1197 if (EDGE_COUNT (bb2->succs) != 2
|
|
|
1198 || !any_condjump_p (BB_END (bb2))
|
|
|
1199 || !onlyjump_p (BB_END (bb2)))
|
|
|
1200 return false;
|
|
|
1201
|
|
|
1202 b1 = BRANCH_EDGE (bb1);
|
|
|
1203 b2 = BRANCH_EDGE (bb2);
|
|
|
1204 f1 = FALLTHRU_EDGE (bb1);
|
|
|
1205 f2 = FALLTHRU_EDGE (bb2);
|
|
|
1206
|
|
|
1207 /* Get around possible forwarders on fallthru edges. Other cases
|
|
|
1208 should be optimized out already. */
|
|
|
1209 if (FORWARDER_BLOCK_P (f1->dest))
|
|
|
1210 f1 = single_succ_edge (f1->dest);
|
|
|
1211
|
|
|
1212 if (FORWARDER_BLOCK_P (f2->dest))
|
|
|
1213 f2 = single_succ_edge (f2->dest);
|
|
|
1214
|
|
|
1215 /* To simplify use of this function, return false if there are
|
|
|
1216 unneeded forwarder blocks. These will get eliminated later
|
|
|
1217 during cleanup_cfg. */
|
|
|
1218 if (FORWARDER_BLOCK_P (f1->dest)
|
|
|
1219 || FORWARDER_BLOCK_P (f2->dest)
|
|
|
1220 || FORWARDER_BLOCK_P (b1->dest)
|
|
|
1221 || FORWARDER_BLOCK_P (b2->dest))
|
|
|
1222 return false;
|
|
|
1223
|
|
|
1224 if (f1->dest == f2->dest && b1->dest == b2->dest)
|
|
|
1225 reverse = false;
|
|
|
1226 else if (f1->dest == b2->dest && b1->dest == f2->dest)
|
|
|
1227 reverse = true;
|
|
|
1228 else
|
|
|
1229 return false;
|
|
|
1230
|
|
|
1231 set1 = pc_set (BB_END (bb1));
|
|
|
1232 set2 = pc_set (BB_END (bb2));
|
|
|
1233 if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
|
|
|
1234 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
|
|
|
1235 reverse = !reverse;
|
|
|
1236
|
|
|
1237 cond1 = XEXP (SET_SRC (set1), 0);
|
|
|
1238 cond2 = XEXP (SET_SRC (set2), 0);
|
|
|
1239 code1 = GET_CODE (cond1);
|
|
|
1240 if (reverse)
|
|
|
1241 code2 = reversed_comparison_code (cond2, BB_END (bb2));
|
|
|
1242 else
|
|
|
1243 code2 = GET_CODE (cond2);
|
|
|
1244
|
|
|
1245 if (code2 == UNKNOWN)
|
|
|
1246 return false;
|
|
|
1247
|
|
|
1248 /* Verify codes and operands match. */
|
|
|
1249 match = ((code1 == code2
|
|
|
1250 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
|
|
|
1251 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
|
|
|
1252 || (code1 == swap_condition (code2)
|
|
|
1253 && rtx_renumbered_equal_p (XEXP (cond1, 1),
|
|
|
1254 XEXP (cond2, 0))
|
|
|
1255 && rtx_renumbered_equal_p (XEXP (cond1, 0),
|
|
|
1256 XEXP (cond2, 1))));
|
|
|
1257
|
|
|
1258 /* If we return true, we will join the blocks. Which means that
|
|
|
1259 we will only have one branch prediction bit to work with. Thus
|
|
|
1260 we require the existing branches to have probabilities that are
|
|
|
1261 roughly similar. */
|
|
|
1262 if (match
|
|
|
1263 && optimize_bb_for_speed_p (bb1)
|
|
|
1264 && optimize_bb_for_speed_p (bb2))
|
|
|
1265 {
|
|
|
1266 int prob2;
|
|
|
1267
|
|
|
1268 if (b1->dest == b2->dest)
|
|
|
1269 prob2 = b2->probability;
|
|
|
1270 else
|
|
|
1271 /* Do not use f2 probability as f2 may be forwarded. */
|
|
|
1272 prob2 = REG_BR_PROB_BASE - b2->probability;
|
|
|
1273
|
|
|
1274 /* Fail if the difference in probabilities is greater than 50%.
|
|
|
1275 This rules out two well-predicted branches with opposite
|
|
|
1276 outcomes. */
|
|
|
1277 if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
|
|
|
1278 {
|
|
|
1279 if (dump_file)
|
|
|
1280 fprintf (dump_file,
|
|
|
1281 "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
|
|
|
1282 bb1->index, bb2->index, b1->probability, prob2);
|
|
|
1283
|
|
|
1284 return false;
|
|
|
1285 }
|
|
|
1286 }
|
|
|
1287
|
|
|
1288 if (dump_file && match)
|
|
|
1289 fprintf (dump_file, "Conditionals in bb %i and %i match.\n",
|
|
|
1290 bb1->index, bb2->index);
|
|
|
1291
|
|
|
1292 return match;
|
|
|
1293 }
|
|
|
1294
|
|
|
1295 /* Generic case - we are seeing a computed jump, table jump or trapping
|
|
|
1296 instruction. */
|
|
|
1297
|
|
|
1298 /* Check whether there are tablejumps in the end of BB1 and BB2.
|
|
|
1299 Return true if they are identical. */
|
|
|
1300 {
|
|
|
1301 rtx label1, label2;
|
|
|
1302 rtx table1, table2;
|
|
|
1303
|
|
|
1304 if (tablejump_p (BB_END (bb1), &label1, &table1)
|
|
|
1305 && tablejump_p (BB_END (bb2), &label2, &table2)
|
|
|
1306 && GET_CODE (PATTERN (table1)) == GET_CODE (PATTERN (table2)))
|
|
|
1307 {
|
|
|
1308 /* The labels should never be the same rtx. If they really are same
|
|
|
1309 the jump tables are same too. So disable crossjumping of blocks BB1
|
|
|
1310 and BB2 because when deleting the common insns in the end of BB1
|
|
|
1311 by delete_basic_block () the jump table would be deleted too. */
|
|
|
1312 /* If LABEL2 is referenced in BB1->END do not do anything
|
|
|
1313 because we would loose information when replacing
|
|
|
1314 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
|
|
|
1315 if (label1 != label2 && !rtx_referenced_p (label2, BB_END (bb1)))
|
|
|
1316 {
|
|
|
1317 /* Set IDENTICAL to true when the tables are identical. */
|
|
|
1318 bool identical = false;
|
|
|
1319 rtx p1, p2;
|
|
|
1320
|
|
|
1321 p1 = PATTERN (table1);
|
|
|
1322 p2 = PATTERN (table2);
|
|
|
1323 if (GET_CODE (p1) == ADDR_VEC && rtx_equal_p (p1, p2))
|
|
|
1324 {
|
|
|
1325 identical = true;
|
|
|
1326 }
|
|
|
1327 else if (GET_CODE (p1) == ADDR_DIFF_VEC
|
|
|
1328 && (XVECLEN (p1, 1) == XVECLEN (p2, 1))
|
|
|
1329 && rtx_equal_p (XEXP (p1, 2), XEXP (p2, 2))
|
|
|
1330 && rtx_equal_p (XEXP (p1, 3), XEXP (p2, 3)))
|
|
|
1331 {
|
|
|
1332 int i;
|
|
|
1333
|
|
|
1334 identical = true;
|
|
|
1335 for (i = XVECLEN (p1, 1) - 1; i >= 0 && identical; i--)
|
|
|
1336 if (!rtx_equal_p (XVECEXP (p1, 1, i), XVECEXP (p2, 1, i)))
|
|
|
1337 identical = false;
|
|
|
1338 }
|
|
|
1339
|
|
|
1340 if (identical)
|
|
|
1341 {
|
|
|
1342 replace_label_data rr;
|
|
|
1343 bool match;
|
|
|
1344
|
|
|
1345 /* Temporarily replace references to LABEL1 with LABEL2
|
|
|
1346 in BB1->END so that we could compare the instructions. */
|
|
|
1347 rr.r1 = label1;
|
|
|
1348 rr.r2 = label2;
|
|
|
1349 rr.update_label_nuses = false;
|
|
|
1350 for_each_rtx (&BB_END (bb1), replace_label, &rr);
|
|
|
1351
|
|
|
1352 match = old_insns_match_p (mode, BB_END (bb1), BB_END (bb2));
|
|
|
1353 if (dump_file && match)
|
|
|
1354 fprintf (dump_file,
|
|
|
1355 "Tablejumps in bb %i and %i match.\n",
|
|
|
1356 bb1->index, bb2->index);
|
|
|
1357
|
|
|
1358 /* Set the original label in BB1->END because when deleting
|
|
|
1359 a block whose end is a tablejump, the tablejump referenced
|
|
|
1360 from the instruction is deleted too. */
|
|
|
1361 rr.r1 = label2;
|
|
|
1362 rr.r2 = label1;
|
|
|
1363 for_each_rtx (&BB_END (bb1), replace_label, &rr);
|
|
|
1364
|
|
|
1365 return match;
|
|
|
1366 }
|
|
|
1367 }
|
|
|
1368 return false;
|
|
|
1369 }
|
|
|
1370 }
|
|
|
1371
|
|
|
1372 /* First ensure that the instructions match. There may be many outgoing
|
|
|
1373 edges so this test is generally cheaper. */
|
|
|
1374 if (!old_insns_match_p (mode, BB_END (bb1), BB_END (bb2)))
|
|
|
1375 return false;
|
|
|
1376
|
|
|
1377 /* Search the outgoing edges, ensure that the counts do match, find possible
|
|
|
1378 fallthru and exception handling edges since these needs more
|
|
|
1379 validation. */
|
|
|
1380 if (EDGE_COUNT (bb1->succs) != EDGE_COUNT (bb2->succs))
|
|
|
1381 return false;
|
|
|
1382
|
|
|
1383 FOR_EACH_EDGE (e1, ei, bb1->succs)
|
|
|
1384 {
|
|
|
1385 e2 = EDGE_SUCC (bb2, ei.index);
|
|
|
1386
|
|
|
1387 if (e1->flags & EDGE_EH)
|
|
|
1388 nehedges1++;
|
|
|
1389
|
|
|
1390 if (e2->flags & EDGE_EH)
|
|
|
1391 nehedges2++;
|
|
|
1392
|
|
|
1393 if (e1->flags & EDGE_FALLTHRU)
|
|
|
1394 fallthru1 = e1;
|
|
|
1395 if (e2->flags & EDGE_FALLTHRU)
|
|
|
1396 fallthru2 = e2;
|
|
|
1397 }
|
|
|
1398
|
|
|
1399 /* If number of edges of various types does not match, fail. */
|
|
|
1400 if (nehedges1 != nehedges2
|
|
|
1401 || (fallthru1 != 0) != (fallthru2 != 0))
|
|
|
1402 return false;
|
|
|
1403
|
|
|
1404 /* fallthru edges must be forwarded to the same destination. */
|
|
|
1405 if (fallthru1)
|
|
|
1406 {
|
|
|
1407 basic_block d1 = (forwarder_block_p (fallthru1->dest)
|
|
|
1408 ? single_succ (fallthru1->dest): fallthru1->dest);
|
|
|
1409 basic_block d2 = (forwarder_block_p (fallthru2->dest)
|
|
|
1410 ? single_succ (fallthru2->dest): fallthru2->dest);
|
|
|
1411
|
|
|
1412 if (d1 != d2)
|
|
|
1413 return false;
|
|
|
1414 }
|
|
|
1415
|
|
|
1416 /* Ensure the same EH region. */
|
|
|
1417 {
|
|
|
1418 rtx n1 = find_reg_note (BB_END (bb1), REG_EH_REGION, 0);
|
|
|
1419 rtx n2 = find_reg_note (BB_END (bb2), REG_EH_REGION, 0);
|
|
|
1420
|
|
|
1421 if (!n1 && n2)
|
|
|
1422 return false;
|
|
|
1423
|
|
|
1424 if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0)))
|
|
|
1425 return false;
|
|
|
1426 }
|
|
|
1427
|
|
|
1428 /* The same checks as in try_crossjump_to_edge. It is required for RTL
|
|
|
1429 version of sequence abstraction. */
|
|
|
1430 FOR_EACH_EDGE (e1, ei, bb2->succs)
|
|
|
1431 {
|
|
|
1432 edge e2;
|
|
|
1433 edge_iterator ei;
|
|
|
1434 basic_block d1 = e1->dest;
|
|
|
1435
|
|
|
1436 if (FORWARDER_BLOCK_P (d1))
|
|
|
1437 d1 = EDGE_SUCC (d1, 0)->dest;
|
|
|
1438
|
|
|
1439 FOR_EACH_EDGE (e2, ei, bb1->succs)
|
|
|
1440 {
|
|
|
1441 basic_block d2 = e2->dest;
|
|
|
1442 if (FORWARDER_BLOCK_P (d2))
|
|
|
1443 d2 = EDGE_SUCC (d2, 0)->dest;
|
|
|
1444 if (d1 == d2)
|
|
|
1445 break;
|
|
|
1446 }
|
|
|
1447
|
|
|
1448 if (!e2)
|
|
|
1449 return false;
|
|
|
1450 }
|
|
|
1451
|
|
|
1452 return true;
|
|
|
1453 }
|
|
|
1454
|
|
|
1455 /* Returns true if BB basic block has a preserve label. */
|
|
|
1456
|
|
|
1457 static bool
|
|
|
1458 block_has_preserve_label (basic_block bb)
|
|
|
1459 {
|
|
|
1460 return (bb
|
|
|
1461 && block_label (bb)
|
|
|
1462 && LABEL_PRESERVE_P (block_label (bb)));
|
|
|
1463 }
|
|
|
1464
|
|
|
1465 /* E1 and E2 are edges with the same destination block. Search their
|
|
|
1466 predecessors for common code. If found, redirect control flow from
|
|
|
1467 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
|
|
|
1468
|
|
|
1469 static bool
|
|
|
1470 try_crossjump_to_edge (int mode, edge e1, edge e2)
|
|
|
1471 {
|
|
|
1472 int nmatch;
|
|
|
1473 basic_block src1 = e1->src, src2 = e2->src;
|
|
|
1474 basic_block redirect_to, redirect_from, to_remove;
|
|
|
1475 rtx newpos1, newpos2;
|
|
|
1476 edge s;
|
|
|
1477 edge_iterator ei;
|
|
|
1478
|
|
|
1479 newpos1 = newpos2 = NULL_RTX;
|
|
|
1480
|
|
|
1481 /* If we have partitioned hot/cold basic blocks, it is a bad idea
|
|
|
1482 to try this optimization.
|
|
|
1483
|
|
|
1484 Basic block partitioning may result in some jumps that appear to
|
|
|
1485 be optimizable (or blocks that appear to be mergeable), but which really
|
|
|
1486 must be left untouched (they are required to make it safely across
|
|
|
1487 partition boundaries). See the comments at the top of
|
|
|
1488 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
|
|
|
1489
|
|
|
1490 if (flag_reorder_blocks_and_partition && reload_completed)
|
|
|
1491 return false;
|
|
|
1492
|
|
|
1493 /* Search backward through forwarder blocks. We don't need to worry
|
|
|
1494 about multiple entry or chained forwarders, as they will be optimized
|
|
|
1495 away. We do this to look past the unconditional jump following a
|
|
|
1496 conditional jump that is required due to the current CFG shape. */
|
|
|
1497 if (single_pred_p (src1)
|
|
|
1498 && FORWARDER_BLOCK_P (src1))
|
|
|
1499 e1 = single_pred_edge (src1), src1 = e1->src;
|
|
|
1500
|
|
|
1501 if (single_pred_p (src2)
|
|
|
1502 && FORWARDER_BLOCK_P (src2))
|
|
|
1503 e2 = single_pred_edge (src2), src2 = e2->src;
|
|
|
1504
|
|
|
1505 /* Nothing to do if we reach ENTRY, or a common source block. */
|
|
|
1506 if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR)
|
|
|
1507 return false;
|
|
|
1508 if (src1 == src2)
|
|
|
1509 return false;
|
|
|
1510
|
|
|
1511 /* Seeing more than 1 forwarder blocks would confuse us later... */
|
|
|
1512 if (FORWARDER_BLOCK_P (e1->dest)
|
|
|
1513 && FORWARDER_BLOCK_P (single_succ (e1->dest)))
|
|
|
1514 return false;
|
|
|
1515
|
|
|
1516 if (FORWARDER_BLOCK_P (e2->dest)
|
|
|
1517 && FORWARDER_BLOCK_P (single_succ (e2->dest)))
|
|
|
1518 return false;
|
|
|
1519
|
|
|
1520 /* Likewise with dead code (possibly newly created by the other optimizations
|
|
|
1521 of cfg_cleanup). */
|
|
|
1522 if (EDGE_COUNT (src1->preds) == 0 || EDGE_COUNT (src2->preds) == 0)
|
|
|
1523 return false;
|
|
|
1524
|
|
|
1525 /* Look for the common insn sequence, part the first ... */
|
|
|
1526 if (!outgoing_edges_match (mode, src1, src2))
|
|
|
1527 return false;
|
|
|
1528
|
|
|
1529 /* ... and part the second. */
|
|
|
1530 nmatch = flow_find_cross_jump (mode, src1, src2, &newpos1, &newpos2);
|
|
|
1531
|
|
|
1532 /* Don't proceed with the crossjump unless we found a sufficient number
|
|
|
1533 of matching instructions or the 'from' block was totally matched
|
|
|
1534 (such that its predecessors will hopefully be redirected and the
|
|
|
1535 block removed). */
|
|
|
1536 if ((nmatch < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
|
|
|
1537 && (newpos1 != BB_HEAD (src1)))
|
|
|
1538 return false;
|
|
|
1539
|
|
|
1540 /* Avoid deleting preserve label when redirecting ABNORMAL edges. */
|
|
|
1541 if (block_has_preserve_label (e1->dest)
|
|
|
1542 && (e1->flags & EDGE_ABNORMAL))
|
|
|
1543 return false;
|
|
|
1544
|
|
|
1545 /* Here we know that the insns in the end of SRC1 which are common with SRC2
|
|
|
1546 will be deleted.
|
|
|
1547 If we have tablejumps in the end of SRC1 and SRC2
|
|
|
1548 they have been already compared for equivalence in outgoing_edges_match ()
|
|
|
1549 so replace the references to TABLE1 by references to TABLE2. */
|
|
|
1550 {
|
|
|
1551 rtx label1, label2;
|
|
|
1552 rtx table1, table2;
|
|
|
1553
|
|
|
1554 if (tablejump_p (BB_END (src1), &label1, &table1)
|
|
|
1555 && tablejump_p (BB_END (src2), &label2, &table2)
|
|
|
1556 && label1 != label2)
|
|
|
1557 {
|
|
|
1558 replace_label_data rr;
|
|
|
1559 rtx insn;
|
|
|
1560
|
|
|
1561 /* Replace references to LABEL1 with LABEL2. */
|
|
|
1562 rr.r1 = label1;
|
|
|
1563 rr.r2 = label2;
|
|
|
1564 rr.update_label_nuses = true;
|
|
|
1565 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
|
|
|
1566 {
|
|
|
1567 /* Do not replace the label in SRC1->END because when deleting
|
|
|
1568 a block whose end is a tablejump, the tablejump referenced
|
|
|
1569 from the instruction is deleted too. */
|
|
|
1570 if (insn != BB_END (src1))
|
|
|
1571 for_each_rtx (&insn, replace_label, &rr);
|
|
|
1572 }
|
|
|
1573 }
|
|
|
1574 }
|
|
|
1575
|
|
|
1576 /* Avoid splitting if possible. We must always split when SRC2 has
|
|
|
1577 EH predecessor edges, or we may end up with basic blocks with both
|
|
|
1578 normal and EH predecessor edges. */
|
|
|
1579 if (newpos2 == BB_HEAD (src2)
|
|
|
1580 && !(EDGE_PRED (src2, 0)->flags & EDGE_EH))
|
|
|
1581 redirect_to = src2;
|
|
|
1582 else
|
|
|
1583 {
|
|
|
1584 if (newpos2 == BB_HEAD (src2))
|
|
|
1585 {
|
|
|
1586 /* Skip possible basic block header. */
|
|
|
1587 if (LABEL_P (newpos2))
|
|
|
1588 newpos2 = NEXT_INSN (newpos2);
|
|
|
1589 if (NOTE_P (newpos2))
|
|
|
1590 newpos2 = NEXT_INSN (newpos2);
|
|
|
1591 }
|
|
|
1592
|
|
|
1593 if (dump_file)
|
|
|
1594 fprintf (dump_file, "Splitting bb %i before %i insns\n",
|
|
|
1595 src2->index, nmatch);
|
|
|
1596 redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
|
|
|
1597 }
|
|
|
1598
|
|
|
1599 if (dump_file)
|
|
|
1600 fprintf (dump_file,
|
|
|
1601 "Cross jumping from bb %i to bb %i; %i common insns\n",
|
|
|
1602 src1->index, src2->index, nmatch);
|
|
|
1603
|
|
|
1604 /* We may have some registers visible through the block. */
|
|
|
1605 df_set_bb_dirty (redirect_to);
|
|
|
1606
|
|
|
1607 /* Recompute the frequencies and counts of outgoing edges. */
|
|
|
1608 FOR_EACH_EDGE (s, ei, redirect_to->succs)
|
|
|
1609 {
|
|
|
1610 edge s2;
|
|
|
1611 edge_iterator ei;
|
|
|
1612 basic_block d = s->dest;
|
|
|
1613
|
|
|
1614 if (FORWARDER_BLOCK_P (d))
|
|
|
1615 d = single_succ (d);
|
|
|
1616
|
|
|
1617 FOR_EACH_EDGE (s2, ei, src1->succs)
|
|
|
1618 {
|
|
|
1619 basic_block d2 = s2->dest;
|
|
|
1620 if (FORWARDER_BLOCK_P (d2))
|
|
|
1621 d2 = single_succ (d2);
|
|
|
1622 if (d == d2)
|
|
|
1623 break;
|
|
|
1624 }
|
|
|
1625
|
|
|
1626 s->count += s2->count;
|
|
|
1627
|
|
|
1628 /* Take care to update possible forwarder blocks. We verified
|
|
|
1629 that there is no more than one in the chain, so we can't run
|
|
|
1630 into infinite loop. */
|
|
|
1631 if (FORWARDER_BLOCK_P (s->dest))
|
|
|
1632 {
|
|
|
1633 single_succ_edge (s->dest)->count += s2->count;
|
|
|
1634 s->dest->count += s2->count;
|
|
|
1635 s->dest->frequency += EDGE_FREQUENCY (s);
|
|
|
1636 }
|
|
|
1637
|
|
|
1638 if (FORWARDER_BLOCK_P (s2->dest))
|
|
|
1639 {
|
|
|
1640 single_succ_edge (s2->dest)->count -= s2->count;
|
|
|
1641 if (single_succ_edge (s2->dest)->count < 0)
|
|
|
1642 single_succ_edge (s2->dest)->count = 0;
|
|
|
1643 s2->dest->count -= s2->count;
|
|
|
1644 s2->dest->frequency -= EDGE_FREQUENCY (s);
|
|
|
1645 if (s2->dest->frequency < 0)
|
|
|
1646 s2->dest->frequency = 0;
|
|
|
1647 if (s2->dest->count < 0)
|
|
|
1648 s2->dest->count = 0;
|
|
|
1649 }
|
|
|
1650
|
|
|
1651 if (!redirect_to->frequency && !src1->frequency)
|
|
|
1652 s->probability = (s->probability + s2->probability) / 2;
|
|
|
1653 else
|
|
|
1654 s->probability
|
|
|
1655 = ((s->probability * redirect_to->frequency +
|
|
|
1656 s2->probability * src1->frequency)
|
|
|
1657 / (redirect_to->frequency + src1->frequency));
|
|
|
1658 }
|
|
|
1659
|
|
|
1660 /* Adjust count and frequency for the block. An earlier jump
|
|
|
1661 threading pass may have left the profile in an inconsistent
|
|
|
1662 state (see update_bb_profile_for_threading) so we must be
|
|
|
1663 prepared for overflows. */
|
|
|
1664 redirect_to->count += src1->count;
|
|
|
1665 redirect_to->frequency += src1->frequency;
|
|
|
1666 if (redirect_to->frequency > BB_FREQ_MAX)
|
|
|
1667 redirect_to->frequency = BB_FREQ_MAX;
|
|
|
1668 update_br_prob_note (redirect_to);
|
|
|
1669
|
|
|
1670 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
|
|
|
1671
|
|
|
1672 /* Skip possible basic block header. */
|
|
|
1673 if (LABEL_P (newpos1))
|
|
|
1674 newpos1 = NEXT_INSN (newpos1);
|
|
|
1675
|
|
|
1676 if (NOTE_P (newpos1))
|
|
|
1677 newpos1 = NEXT_INSN (newpos1);
|
|
|
1678
|
|
|
1679 redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
|
|
|
1680 to_remove = single_succ (redirect_from);
|
|
|
1681
|
|
|
1682 redirect_edge_and_branch_force (single_succ_edge (redirect_from), redirect_to);
|
|
|
1683 delete_basic_block (to_remove);
|
|
|
1684
|
|
|
1685 update_forwarder_flag (redirect_from);
|
|
|
1686 if (redirect_to != src2)
|
|
|
1687 update_forwarder_flag (src2);
|
|
|
1688
|
|
|
1689 return true;
|
|
|
1690 }
|
|
|
1691
|
|
|
1692 /* Search the predecessors of BB for common insn sequences. When found,
|
|
|
1693 share code between them by redirecting control flow. Return true if
|
|
|
1694 any changes made. */
|
|
|
1695
|
|
|
1696 static bool
|
|
|
1697 try_crossjump_bb (int mode, basic_block bb)
|
|
|
1698 {
|
|
|
1699 edge e, e2, fallthru;
|
|
|
1700 bool changed;
|
|
|
1701 unsigned max, ix, ix2;
|
|
|
1702 basic_block ev, ev2;
|
|
|
1703 edge_iterator ei;
|
|
|
1704
|
|
|
1705 /* Nothing to do if there is not at least two incoming edges. */
|
|
|
1706 if (EDGE_COUNT (bb->preds) < 2)
|
|
|
1707 return false;
|
|
|
1708
|
|
|
1709 /* Don't crossjump if this block ends in a computed jump,
|
|
|
1710 unless we are optimizing for size. */
|
|
|
1711 if (optimize_bb_for_size_p (bb)
|
|
|
1712 && bb != EXIT_BLOCK_PTR
|
|
|
1713 && computed_jump_p (BB_END (bb)))
|
|
|
1714 return false;
|
|
|
1715
|
|
|
1716 /* If we are partitioning hot/cold basic blocks, we don't want to
|
|
|
1717 mess up unconditional or indirect jumps that cross between hot
|
|
|
1718 and cold sections.
|
|
|
1719
|
|
|
1720 Basic block partitioning may result in some jumps that appear to
|
|
|
1721 be optimizable (or blocks that appear to be mergeable), but which really
|
|
|
1722 must be left untouched (they are required to make it safely across
|
|
|
1723 partition boundaries). See the comments at the top of
|
|
|
1724 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
|
|
|
1725
|
|
|
1726 if (BB_PARTITION (EDGE_PRED (bb, 0)->src) !=
|
|
|
1727 BB_PARTITION (EDGE_PRED (bb, 1)->src)
|
|
|
1728 || (EDGE_PRED (bb, 0)->flags & EDGE_CROSSING))
|
|
|
1729 return false;
|
|
|
1730
|
|
|
1731 /* It is always cheapest to redirect a block that ends in a branch to
|
|
|
1732 a block that falls through into BB, as that adds no branches to the
|
|
|
1733 program. We'll try that combination first. */
|
|
|
1734 fallthru = NULL;
|
|
|
1735 max = PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES);
|
|
|
1736
|
|
|
1737 if (EDGE_COUNT (bb->preds) > max)
|
|
|
1738 return false;
|
|
|
1739
|
|
|
1740 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
1741 {
|
|
|
1742 if (e->flags & EDGE_FALLTHRU)
|
|
|
1743 {
|
|
|
1744 fallthru = e;
|
|
|
1745 break;
|
|
|
1746 }
|
|
|
1747 }
|
|
|
1748
|
|
|
1749 changed = false;
|
|
|
1750 for (ix = 0, ev = bb; ix < EDGE_COUNT (ev->preds); )
|
|
|
1751 {
|
|
|
1752 e = EDGE_PRED (ev, ix);
|
|
|
1753 ix++;
|
|
|
1754
|
|
|
1755 /* As noted above, first try with the fallthru predecessor (or, a
|
|
|
1756 fallthru predecessor if we are in cfglayout mode). */
|
|
|
1757 if (fallthru)
|
|
|
1758 {
|
|
|
1759 /* Don't combine the fallthru edge into anything else.
|
|
|
1760 If there is a match, we'll do it the other way around. */
|
|
|
1761 if (e == fallthru)
|
|
|
1762 continue;
|
|
|
1763 /* If nothing changed since the last attempt, there is nothing
|
|
|
1764 we can do. */
|
|
|
1765 if (!first_pass
|
|
|
1766 && (!(df_get_bb_dirty (e->src))
|
|
|
1767 && !(df_get_bb_dirty (fallthru->src))))
|
|
|
1768 continue;
|
|
|
1769
|
|
|
1770 if (try_crossjump_to_edge (mode, e, fallthru))
|
|
|
1771 {
|
|
|
1772 changed = true;
|
|
|
1773 ix = 0;
|
|
|
1774 ev = bb;
|
|
|
1775 continue;
|
|
|
1776 }
|
|
|
1777 }
|
|
|
1778
|
|
|
1779 /* Non-obvious work limiting check: Recognize that we're going
|
|
|
1780 to call try_crossjump_bb on every basic block. So if we have
|
|
|
1781 two blocks with lots of outgoing edges (a switch) and they
|
|
|
1782 share lots of common destinations, then we would do the
|
|
|
1783 cross-jump check once for each common destination.
|
|
|
1784
|
|
|
1785 Now, if the blocks actually are cross-jump candidates, then
|
|
|
1786 all of their destinations will be shared. Which means that
|
|
|
1787 we only need check them for cross-jump candidacy once. We
|
|
|
1788 can eliminate redundant checks of crossjump(A,B) by arbitrarily
|
|
|
1789 choosing to do the check from the block for which the edge
|
|
|
1790 in question is the first successor of A. */
|
|
|
1791 if (EDGE_SUCC (e->src, 0) != e)
|
|
|
1792 continue;
|
|
|
1793
|
|
|
1794 for (ix2 = 0, ev2 = bb; ix2 < EDGE_COUNT (ev2->preds); )
|
|
|
1795 {
|
|
|
1796 e2 = EDGE_PRED (ev2, ix2);
|
|
|
1797 ix2++;
|
|
|
1798
|
|
|
1799 if (e2 == e)
|
|
|
1800 continue;
|
|
|
1801
|
|
|
1802 /* We've already checked the fallthru edge above. */
|
|
|
1803 if (e2 == fallthru)
|
|
|
1804 continue;
|
|
|
1805
|
|
|
1806 /* The "first successor" check above only prevents multiple
|
|
|
1807 checks of crossjump(A,B). In order to prevent redundant
|
|
|
1808 checks of crossjump(B,A), require that A be the block
|
|
|
1809 with the lowest index. */
|
|
|
1810 if (e->src->index > e2->src->index)
|
|
|
1811 continue;
|
|
|
1812
|
|
|
1813 /* If nothing changed since the last attempt, there is nothing
|
|
|
1814 we can do. */
|
|
|
1815 if (!first_pass
|
|
|
1816 && (!(df_get_bb_dirty (e->src))
|
|
|
1817 && !(df_get_bb_dirty (e2->src))))
|
|
|
1818 continue;
|
|
|
1819
|
|
|
1820 if (try_crossjump_to_edge (mode, e, e2))
|
|
|
1821 {
|
|
|
1822 changed = true;
|
|
|
1823 ev2 = bb;
|
|
|
1824 ix = 0;
|
|
|
1825 break;
|
|
|
1826 }
|
|
|
1827 }
|
|
|
1828 }
|
|
|
1829
|
|
|
1830 if (changed)
|
|
|
1831 crossjumps_occured = true;
|
|
|
1832
|
|
|
1833 return changed;
|
|
|
1834 }
|
|
|
1835
|
|
|
1836 /* Do simple CFG optimizations - basic block merging, simplifying of jump
|
|
|
1837 instructions etc. Return nonzero if changes were made. */
|
|
|
1838
|
|
|
1839 static bool
|
|
|
1840 try_optimize_cfg (int mode)
|
|
|
1841 {
|
|
|
1842 bool changed_overall = false;
|
|
|
1843 bool changed;
|
|
|
1844 int iterations = 0;
|
|
|
1845 basic_block bb, b, next;
|
|
|
1846
|
|
|
1847 if (mode & (CLEANUP_CROSSJUMP | CLEANUP_THREADING))
|
|
|
1848 clear_bb_flags ();
|
|
|
1849
|
|
|
1850 crossjumps_occured = false;
|
|
|
1851
|
|
|
1852 FOR_EACH_BB (bb)
|
|
|
1853 update_forwarder_flag (bb);
|
|
|
1854
|
|
|
1855 if (! targetm.cannot_modify_jumps_p ())
|
|
|
1856 {
|
|
|
1857 first_pass = true;
|
|
|
1858 /* Attempt to merge blocks as made possible by edge removal. If
|
|
|
1859 a block has only one successor, and the successor has only
|
|
|
1860 one predecessor, they may be combined. */
|
|
|
1861 do
|
|
|
1862 {
|
|
|
1863 changed = false;
|
|
|
1864 iterations++;
|
|
|
1865
|
|
|
1866 if (dump_file)
|
|
|
1867 fprintf (dump_file,
|
|
|
1868 "\n\ntry_optimize_cfg iteration %i\n\n",
|
|
|
1869 iterations);
|
|
|
1870
|
|
|
1871 for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR;)
|
|
|
1872 {
|
|
|
1873 basic_block c;
|
|
|
1874 edge s;
|
|
|
1875 bool changed_here = false;
|
|
|
1876
|
|
|
1877 /* Delete trivially dead basic blocks. */
|
|
|
1878 if (EDGE_COUNT (b->preds) == 0)
|
|
|
1879 {
|
|
|
1880 c = b->prev_bb;
|
|
|
1881 if (dump_file)
|
|
|
1882 fprintf (dump_file, "Deleting block %i.\n",
|
|
|
1883 b->index);
|
|
|
1884
|
|
|
1885 delete_basic_block (b);
|
|
|
1886 if (!(mode & CLEANUP_CFGLAYOUT))
|
|
|
1887 changed = true;
|
|
|
1888 /* Avoid trying to remove ENTRY_BLOCK_PTR. */
|
|
|
1889 b = (c == ENTRY_BLOCK_PTR ? c->next_bb : c);
|
|
|
1890 continue;
|
|
|
1891 }
|
|
|
1892
|
|
|
1893 /* Remove code labels no longer used. */
|
|
|
1894 if (single_pred_p (b)
|
|
|
1895 && (single_pred_edge (b)->flags & EDGE_FALLTHRU)
|
|
|
1896 && !(single_pred_edge (b)->flags & EDGE_COMPLEX)
|
|
|
1897 && LABEL_P (BB_HEAD (b))
|
|
|
1898 /* If the previous block ends with a branch to this
|
|
|
1899 block, we can't delete the label. Normally this
|
|
|
1900 is a condjump that is yet to be simplified, but
|
|
|
1901 if CASE_DROPS_THRU, this can be a tablejump with
|
|
|
1902 some element going to the same place as the
|
|
|
1903 default (fallthru). */
|
|
|
1904 && (single_pred (b) == ENTRY_BLOCK_PTR
|
|
|
1905 || !JUMP_P (BB_END (single_pred (b)))
|
|
|
1906 || ! label_is_jump_target_p (BB_HEAD (b),
|
|
|
1907 BB_END (single_pred (b)))))
|
|
|
1908 {
|
|
|
1909 rtx label = BB_HEAD (b);
|
|
|
1910
|
|
|
1911 delete_insn_chain (label, label, false);
|
|
|
1912 /* If the case label is undeletable, move it after the
|
|
|
1913 BASIC_BLOCK note. */
|
|
|
1914 if (NOTE_KIND (BB_HEAD (b)) == NOTE_INSN_DELETED_LABEL)
|
|
|
1915 {
|
|
|
1916 rtx bb_note = NEXT_INSN (BB_HEAD (b));
|
|
|
1917
|
|
|
1918 reorder_insns_nobb (label, label, bb_note);
|
|
|
1919 BB_HEAD (b) = bb_note;
|
|
|
1920 if (BB_END (b) == bb_note)
|
|
|
1921 BB_END (b) = label;
|
|
|
1922 }
|
|
|
1923 if (dump_file)
|
|
|
1924 fprintf (dump_file, "Deleted label in block %i.\n",
|
|
|
1925 b->index);
|
|
|
1926 }
|
|
|
1927
|
|
|
1928 /* If we fall through an empty block, we can remove it. */
|
|
|
1929 if (!(mode & CLEANUP_CFGLAYOUT)
|
|
|
1930 && single_pred_p (b)
|
|
|
1931 && (single_pred_edge (b)->flags & EDGE_FALLTHRU)
|
|
|
1932 && !LABEL_P (BB_HEAD (b))
|
|
|
1933 && FORWARDER_BLOCK_P (b)
|
|
|
1934 /* Note that forwarder_block_p true ensures that
|
|
|
1935 there is a successor for this block. */
|
|
|
1936 && (single_succ_edge (b)->flags & EDGE_FALLTHRU)
|
|
|
1937 && n_basic_blocks > NUM_FIXED_BLOCKS + 1)
|
|
|
1938 {
|
|
|
1939 if (dump_file)
|
|
|
1940 fprintf (dump_file,
|
|
|
1941 "Deleting fallthru block %i.\n",
|
|
|
1942 b->index);
|
|
|
1943
|
|
|
1944 c = b->prev_bb == ENTRY_BLOCK_PTR ? b->next_bb : b->prev_bb;
|
|
|
1945 redirect_edge_succ_nodup (single_pred_edge (b),
|
|
|
1946 single_succ (b));
|
|
|
1947 delete_basic_block (b);
|
|
|
1948 changed = true;
|
|
|
1949 b = c;
|
|
|
1950 }
|
|
|
1951
|
|
|
1952 if (single_succ_p (b)
|
|
|
1953 && (s = single_succ_edge (b))
|
|
|
1954 && !(s->flags & EDGE_COMPLEX)
|
|
|
1955 && (c = s->dest) != EXIT_BLOCK_PTR
|
|
|
1956 && single_pred_p (c)
|
|
|
1957 && b != c)
|
|
|
1958 {
|
|
|
1959 /* When not in cfg_layout mode use code aware of reordering
|
|
|
1960 INSN. This code possibly creates new basic blocks so it
|
|
|
1961 does not fit merge_blocks interface and is kept here in
|
|
|
1962 hope that it will become useless once more of compiler
|
|
|
1963 is transformed to use cfg_layout mode. */
|
|
|
1964
|
|
|
1965 if ((mode & CLEANUP_CFGLAYOUT)
|
|
|
1966 && can_merge_blocks_p (b, c))
|
|
|
1967 {
|
|
|
1968 merge_blocks (b, c);
|
|
|
1969 update_forwarder_flag (b);
|
|
|
1970 changed_here = true;
|
|
|
1971 }
|
|
|
1972 else if (!(mode & CLEANUP_CFGLAYOUT)
|
|
|
1973 /* If the jump insn has side effects,
|
|
|
1974 we can't kill the edge. */
|
|
|
1975 && (!JUMP_P (BB_END (b))
|
|
|
1976 || (reload_completed
|
|
|
1977 ? simplejump_p (BB_END (b))
|
|
|
1978 : (onlyjump_p (BB_END (b))
|
|
|
1979 && !tablejump_p (BB_END (b),
|
|
|
1980 NULL, NULL))))
|
|
|
1981 && (next = merge_blocks_move (s, b, c, mode)))
|
|
|
1982 {
|
|
|
1983 b = next;
|
|
|
1984 changed_here = true;
|
|
|
1985 }
|
|
|
1986 }
|
|
|
1987
|
|
|
1988 /* Simplify branch over branch. */
|
|
|
1989 if ((mode & CLEANUP_EXPENSIVE)
|
|
|
1990 && !(mode & CLEANUP_CFGLAYOUT)
|
|
|
1991 && try_simplify_condjump (b))
|
|
|
1992 changed_here = true;
|
|
|
1993
|
|
|
1994 /* If B has a single outgoing edge, but uses a
|
|
|
1995 non-trivial jump instruction without side-effects, we
|
|
|
1996 can either delete the jump entirely, or replace it
|
|
|
1997 with a simple unconditional jump. */
|
|
|
1998 if (single_succ_p (b)
|
|
|
1999 && single_succ (b) != EXIT_BLOCK_PTR
|
|
|
2000 && onlyjump_p (BB_END (b))
|
|
|
2001 && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX)
|
|
|
2002 && try_redirect_by_replacing_jump (single_succ_edge (b),
|
|
|
2003 single_succ (b),
|
|
|
2004 (mode & CLEANUP_CFGLAYOUT) != 0))
|
|
|
2005 {
|
|
|
2006 update_forwarder_flag (b);
|
|
|
2007 changed_here = true;
|
|
|
2008 }
|
|
|
2009
|
|
|
2010 /* Simplify branch to branch. */
|
|
|
2011 if (try_forward_edges (mode, b))
|
|
|
2012 changed_here = true;
|
|
|
2013
|
|
|
2014 /* Look for shared code between blocks. */
|
|
|
2015 if ((mode & CLEANUP_CROSSJUMP)
|
|
|
2016 && try_crossjump_bb (mode, b))
|
|
|
2017 changed_here = true;
|
|
|
2018
|
|
|
2019 /* Don't get confused by the index shift caused by
|
|
|
2020 deleting blocks. */
|
|
|
2021 if (!changed_here)
|
|
|
2022 b = b->next_bb;
|
|
|
2023 else
|
|
|
2024 changed = true;
|
|
|
2025 }
|
|
|
2026
|
|
|
2027 if ((mode & CLEANUP_CROSSJUMP)
|
|
|
2028 && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
|
|
|
2029 changed = true;
|
|
|
2030
|
|
|
2031 #ifdef ENABLE_CHECKING
|
|
|
2032 if (changed)
|
|
|
2033 verify_flow_info ();
|
|
|
2034 #endif
|
|
|
2035
|
|
|
2036 changed_overall |= changed;
|
|
|
2037 first_pass = false;
|
|
|
2038 }
|
|
|
2039 while (changed);
|
|
|
2040 }
|
|
|
2041
|
|
|
2042 FOR_ALL_BB (b)
|
|
|
2043 b->flags &= ~(BB_FORWARDER_BLOCK | BB_NONTHREADABLE_BLOCK);
|
|
|
2044
|
|
|
2045 return changed_overall;
|
|
|
2046 }
|
|
|
2047
|
|
|
2048 /* Delete all unreachable basic blocks. */
|
|
|
2049
|
|
|
2050 bool
|
|
|
2051 delete_unreachable_blocks (void)
|
|
|
2052 {
|
|
|
2053 bool changed = false;
|
|
|
2054 basic_block b, next_bb;
|
|
|
2055
|
|
|
2056 find_unreachable_blocks ();
|
|
|
2057
|
|
|
2058 /* Delete all unreachable basic blocks. */
|
|
|
2059
|
|
|
2060 for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
|
|
|
2061 {
|
|
|
2062 next_bb = b->next_bb;
|
|
|
2063
|
|
|
2064 if (!(b->flags & BB_REACHABLE))
|
|
|
2065 {
|
|
|
2066 delete_basic_block (b);
|
|
|
2067 changed = true;
|
|
|
2068 }
|
|
|
2069 }
|
|
|
2070
|
|
|
2071 if (changed)
|
|
|
2072 tidy_fallthru_edges ();
|
|
|
2073 return changed;
|
|
|
2074 }
|
|
|
2075
|
|
|
2076 /* Delete any jump tables never referenced. We can't delete them at the
|
|
|
2077 time of removing tablejump insn as they are referenced by the preceding
|
|
|
2078 insns computing the destination, so we delay deleting and garbagecollect
|
|
|
2079 them once life information is computed. */
|
|
|
2080 void
|
|
|
2081 delete_dead_jumptables (void)
|
|
|
2082 {
|
|
|
2083 basic_block bb;
|
|
|
2084
|
|
|
2085 /* A dead jump table does not belong to any basic block. Scan insns
|
|
|
2086 between two adjacent basic blocks. */
|
|
|
2087 FOR_EACH_BB (bb)
|
|
|
2088 {
|
|
|
2089 rtx insn, next;
|
|
|
2090
|
|
|
2091 for (insn = NEXT_INSN (BB_END (bb));
|
|
|
2092 insn && !NOTE_INSN_BASIC_BLOCK_P (insn);
|
|
|
2093 insn = next)
|
|
|
2094 {
|
|
|
2095 next = NEXT_INSN (insn);
|
|
|
2096 if (LABEL_P (insn)
|
|
|
2097 && LABEL_NUSES (insn) == LABEL_PRESERVE_P (insn)
|
|
|
2098 && JUMP_P (next)
|
|
|
2099 && (GET_CODE (PATTERN (next)) == ADDR_VEC
|
|
|
2100 || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
|
|
|
2101 {
|
|
|
2102 rtx label = insn, jump = next;
|
|
|
2103
|
|
|
2104 if (dump_file)
|
|
|
2105 fprintf (dump_file, "Dead jumptable %i removed\n",
|
|
|
2106 INSN_UID (insn));
|
|
|
2107
|
|
|
2108 next = NEXT_INSN (next);
|
|
|
2109 delete_insn (jump);
|
|
|
2110 delete_insn (label);
|
|
|
2111 }
|
|
|
2112 }
|
|
|
2113 }
|
|
|
2114 }
|
|
|
2115
|
|
|
2116
|
|
|
2117 /* Tidy the CFG by deleting unreachable code and whatnot. */
|
|
|
2118
|
|
|
2119 bool
|
|
|
2120 cleanup_cfg (int mode)
|
|
|
2121 {
|
|
|
2122 bool changed = false;
|
|
|
2123
|
|
|
2124 /* Set the cfglayout mode flag here. We could update all the callers
|
|
|
2125 but that is just inconvenient, especially given that we eventually
|
|
|
2126 want to have cfglayout mode as the default. */
|
|
|
2127 if (current_ir_type () == IR_RTL_CFGLAYOUT)
|
|
|
2128 mode |= CLEANUP_CFGLAYOUT;
|
|
|
2129
|
|
|
2130 timevar_push (TV_CLEANUP_CFG);
|
|
|
2131 if (delete_unreachable_blocks ())
|
|
|
2132 {
|
|
|
2133 changed = true;
|
|
|
2134 /* We've possibly created trivially dead code. Cleanup it right
|
|
|
2135 now to introduce more opportunities for try_optimize_cfg. */
|
|
|
2136 if (!(mode & (CLEANUP_NO_INSN_DEL))
|
|
|
2137 && !reload_completed)
|
|
|
2138 delete_trivially_dead_insns (get_insns (), max_reg_num ());
|
|
|
2139 }
|
|
|
2140
|
|
|
2141 compact_blocks ();
|
|
|
2142
|
|
|
2143 /* To tail-merge blocks ending in the same noreturn function (e.g.
|
|
|
2144 a call to abort) we have to insert fake edges to exit. Do this
|
|
|
2145 here once. The fake edges do not interfere with any other CFG
|
|
|
2146 cleanups. */
|
|
|
2147 if (mode & CLEANUP_CROSSJUMP)
|
|
|
2148 add_noreturn_fake_exit_edges ();
|
|
|
2149
|
|
|
2150 if (!dbg_cnt (cfg_cleanup))
|
|
|
2151 return changed;
|
|
|
2152
|
|
|
2153 while (try_optimize_cfg (mode))
|
|
|
2154 {
|
|
|
2155 delete_unreachable_blocks (), changed = true;
|
|
|
2156 if (!(mode & CLEANUP_NO_INSN_DEL))
|
|
|
2157 {
|
|
|
2158 /* Try to remove some trivially dead insns when doing an expensive
|
|
|
2159 cleanup. But delete_trivially_dead_insns doesn't work after
|
|
|
2160 reload (it only handles pseudos) and run_fast_dce is too costly
|
|
|
2161 to run in every iteration.
|
|
|
2162
|
|
|
2163 For effective cross jumping, we really want to run a fast DCE to
|
|
|
2164 clean up any dead conditions, or they get in the way of performing
|
|
|
2165 useful tail merges.
|
|
|
2166
|
|
|
2167 Other transformations in cleanup_cfg are not so sensitive to dead
|
|
|
2168 code, so delete_trivially_dead_insns or even doing nothing at all
|
|
|
2169 is good enough. */
|
|
|
2170 if ((mode & CLEANUP_EXPENSIVE) && !reload_completed
|
|
|
2171 && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
|
|
|
2172 break;
|
|
|
2173 else if ((mode & CLEANUP_CROSSJUMP)
|
|
|
2174 && crossjumps_occured)
|
|
|
2175 run_fast_dce ();
|
|
|
2176 }
|
|
|
2177 else
|
|
|
2178 break;
|
|
|
2179 }
|
|
|
2180
|
|
|
2181 if (mode & CLEANUP_CROSSJUMP)
|
|
|
2182 remove_fake_exit_edges ();
|
|
|
2183
|
|
|
2184 /* Don't call delete_dead_jumptables in cfglayout mode, because
|
|
|
2185 that function assumes that jump tables are in the insns stream.
|
|
|
2186 But we also don't _have_ to delete dead jumptables in cfglayout
|
|
|
2187 mode because we shouldn't even be looking at things that are
|
|
|
2188 not in a basic block. Dead jumptables are cleaned up when
|
|
|
2189 going out of cfglayout mode. */
|
|
|
2190 if (!(mode & CLEANUP_CFGLAYOUT))
|
|
|
2191 delete_dead_jumptables ();
|
|
|
2192
|
|
|
2193 timevar_pop (TV_CLEANUP_CFG);
|
|
|
2194
|
|
|
2195 return changed;
|
|
|
2196 }
|
|
|
2197
|
|
|
2198 static unsigned int
|
|
|
2199 rest_of_handle_jump (void)
|
|
|
2200 {
|
|
|
2201 delete_unreachable_blocks ();
|
|
|
2202
|
|
|
2203 if (crtl->tail_call_emit)
|
|
|
2204 fixup_tail_calls ();
|
|
|
2205 return 0;
|
|
|
2206 }
|
|
|
2207
|
|
|
2208 struct rtl_opt_pass pass_jump =
|
|
|
2209 {
|
|
|
2210 {
|
|
|
2211 RTL_PASS,
|
|
|
2212 "sibling", /* name */
|
|
|
2213 NULL, /* gate */
|
|
|
2214 rest_of_handle_jump, /* execute */
|
|
|
2215 NULL, /* sub */
|
|
|
2216 NULL, /* next */
|
|
|
2217 0, /* static_pass_number */
|
|
|
2218 TV_JUMP, /* tv_id */
|
|
|
2219 0, /* properties_required */
|
|
|
2220 0, /* properties_provided */
|
|
|
2221 0, /* properties_destroyed */
|
|
|
2222 TODO_ggc_collect, /* todo_flags_start */
|
|
|
2223 TODO_verify_flow, /* todo_flags_finish */
|
|
|
2224 }
|
|
|
2225 };
|
|
|
2226
|
|
|
2227
|
|
|
2228 static unsigned int
|
|
|
2229 rest_of_handle_jump2 (void)
|
|
|
2230 {
|
|
|
2231 delete_trivially_dead_insns (get_insns (), max_reg_num ());
|
|
|
2232 if (dump_file)
|
|
|
2233 dump_flow_info (dump_file, dump_flags);
|
|
|
2234 cleanup_cfg ((optimize ? CLEANUP_EXPENSIVE : 0)
|
|
|
2235 | (flag_thread_jumps ? CLEANUP_THREADING : 0));
|
|
|
2236 return 0;
|
|
|
2237 }
|
|
|
2238
|
|
|
2239
|
|
|
2240 struct rtl_opt_pass pass_jump2 =
|
|
|
2241 {
|
|
|
2242 {
|
|
|
2243 RTL_PASS,
|
|
|
2244 "jump", /* name */
|
|
|
2245 NULL, /* gate */
|
|
|
2246 rest_of_handle_jump2, /* execute */
|
|
|
2247 NULL, /* sub */
|
|
|
2248 NULL, /* next */
|
|
|
2249 0, /* static_pass_number */
|
|
|
2250 TV_JUMP, /* tv_id */
|
|
|
2251 0, /* properties_required */
|
|
|
2252 0, /* properties_provided */
|
|
|
2253 0, /* properties_destroyed */
|
|
|
2254 TODO_ggc_collect, /* todo_flags_start */
|
|
|
2255 TODO_dump_func | TODO_verify_rtl_sharing,/* todo_flags_finish */
|
|
|
2256 }
|
|
|
2257 };
|
|
|
2258
|
|
|
2259
|
