0
|
1 /* Control flow graph manipulation 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 low level functions to manipulate the CFG and analyze it
|
|
23 that are aware of the RTL intermediate language.
|
|
24
|
|
25 Available functionality:
|
|
26 - Basic CFG/RTL manipulation API documented in cfghooks.h
|
|
27 - CFG-aware instruction chain manipulation
|
|
28 delete_insn, delete_insn_chain
|
|
29 - Edge splitting and committing to edges
|
|
30 insert_insn_on_edge, commit_edge_insertions
|
|
31 - CFG updating after insn simplification
|
|
32 purge_dead_edges, purge_all_dead_edges
|
|
33
|
|
34 Functions not supposed for generic use:
|
|
35 - Infrastructure to determine quickly basic block for insn
|
|
36 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
|
|
37 - Edge redirection with updating and optimizing of insn chain
|
|
38 block_label, tidy_fallthru_edge, force_nonfallthru */
|
|
39
|
|
40 #include "config.h"
|
|
41 #include "system.h"
|
|
42 #include "coretypes.h"
|
|
43 #include "tm.h"
|
|
44 #include "tree.h"
|
|
45 #include "rtl.h"
|
|
46 #include "hard-reg-set.h"
|
|
47 #include "basic-block.h"
|
|
48 #include "regs.h"
|
|
49 #include "flags.h"
|
|
50 #include "output.h"
|
|
51 #include "function.h"
|
|
52 #include "except.h"
|
|
53 #include "toplev.h"
|
|
54 #include "tm_p.h"
|
|
55 #include "obstack.h"
|
|
56 #include "insn-config.h"
|
|
57 #include "cfglayout.h"
|
|
58 #include "expr.h"
|
|
59 #include "target.h"
|
|
60 #include "cfgloop.h"
|
|
61 #include "ggc.h"
|
|
62 #include "tree-pass.h"
|
|
63 #include "df.h"
|
|
64
|
|
65 static int can_delete_note_p (const_rtx);
|
|
66 static int can_delete_label_p (const_rtx);
|
|
67 static void commit_one_edge_insertion (edge);
|
|
68 static basic_block rtl_split_edge (edge);
|
|
69 static bool rtl_move_block_after (basic_block, basic_block);
|
|
70 static int rtl_verify_flow_info (void);
|
|
71 static basic_block cfg_layout_split_block (basic_block, void *);
|
|
72 static edge cfg_layout_redirect_edge_and_branch (edge, basic_block);
|
|
73 static basic_block cfg_layout_redirect_edge_and_branch_force (edge, basic_block);
|
|
74 static void cfg_layout_delete_block (basic_block);
|
|
75 static void rtl_delete_block (basic_block);
|
|
76 static basic_block rtl_redirect_edge_and_branch_force (edge, basic_block);
|
|
77 static edge rtl_redirect_edge_and_branch (edge, basic_block);
|
|
78 static basic_block rtl_split_block (basic_block, void *);
|
|
79 static void rtl_dump_bb (basic_block, FILE *, int, int);
|
|
80 static int rtl_verify_flow_info_1 (void);
|
|
81 static void rtl_make_forwarder_block (edge);
|
|
82
|
|
83 /* Return true if NOTE is not one of the ones that must be kept paired,
|
|
84 so that we may simply delete it. */
|
|
85
|
|
86 static int
|
|
87 can_delete_note_p (const_rtx note)
|
|
88 {
|
|
89 return (NOTE_KIND (note) == NOTE_INSN_DELETED
|
|
90 || NOTE_KIND (note) == NOTE_INSN_BASIC_BLOCK);
|
|
91 }
|
|
92
|
|
93 /* True if a given label can be deleted. */
|
|
94
|
|
95 static int
|
|
96 can_delete_label_p (const_rtx label)
|
|
97 {
|
|
98 return (!LABEL_PRESERVE_P (label)
|
|
99 /* User declared labels must be preserved. */
|
|
100 && LABEL_NAME (label) == 0
|
|
101 && !in_expr_list_p (forced_labels, label));
|
|
102 }
|
|
103
|
|
104 /* Delete INSN by patching it out. Return the next insn. */
|
|
105
|
|
106 rtx
|
|
107 delete_insn (rtx insn)
|
|
108 {
|
|
109 rtx next = NEXT_INSN (insn);
|
|
110 rtx note;
|
|
111 bool really_delete = true;
|
|
112
|
|
113 if (LABEL_P (insn))
|
|
114 {
|
|
115 /* Some labels can't be directly removed from the INSN chain, as they
|
|
116 might be references via variables, constant pool etc.
|
|
117 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
|
|
118 if (! can_delete_label_p (insn))
|
|
119 {
|
|
120 const char *name = LABEL_NAME (insn);
|
|
121
|
|
122 really_delete = false;
|
|
123 PUT_CODE (insn, NOTE);
|
|
124 NOTE_KIND (insn) = NOTE_INSN_DELETED_LABEL;
|
|
125 NOTE_DELETED_LABEL_NAME (insn) = name;
|
|
126 }
|
|
127
|
|
128 remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
|
|
129 }
|
|
130
|
|
131 if (really_delete)
|
|
132 {
|
|
133 /* If this insn has already been deleted, something is very wrong. */
|
|
134 gcc_assert (!INSN_DELETED_P (insn));
|
|
135 remove_insn (insn);
|
|
136 INSN_DELETED_P (insn) = 1;
|
|
137 }
|
|
138
|
|
139 /* If deleting a jump, decrement the use count of the label. Deleting
|
|
140 the label itself should happen in the normal course of block merging. */
|
|
141 if (JUMP_P (insn))
|
|
142 {
|
|
143 if (JUMP_LABEL (insn)
|
|
144 && LABEL_P (JUMP_LABEL (insn)))
|
|
145 LABEL_NUSES (JUMP_LABEL (insn))--;
|
|
146
|
|
147 /* If there are more targets, remove them too. */
|
|
148 while ((note
|
|
149 = find_reg_note (insn, REG_LABEL_TARGET, NULL_RTX)) != NULL_RTX
|
|
150 && LABEL_P (XEXP (note, 0)))
|
|
151 {
|
|
152 LABEL_NUSES (XEXP (note, 0))--;
|
|
153 remove_note (insn, note);
|
|
154 }
|
|
155 }
|
|
156
|
|
157 /* Also if deleting any insn that references a label as an operand. */
|
|
158 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX)) != NULL_RTX
|
|
159 && LABEL_P (XEXP (note, 0)))
|
|
160 {
|
|
161 LABEL_NUSES (XEXP (note, 0))--;
|
|
162 remove_note (insn, note);
|
|
163 }
|
|
164
|
|
165 if (JUMP_P (insn)
|
|
166 && (GET_CODE (PATTERN (insn)) == ADDR_VEC
|
|
167 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
|
|
168 {
|
|
169 rtx pat = PATTERN (insn);
|
|
170 int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC;
|
|
171 int len = XVECLEN (pat, diff_vec_p);
|
|
172 int i;
|
|
173
|
|
174 for (i = 0; i < len; i++)
|
|
175 {
|
|
176 rtx label = XEXP (XVECEXP (pat, diff_vec_p, i), 0);
|
|
177
|
|
178 /* When deleting code in bulk (e.g. removing many unreachable
|
|
179 blocks) we can delete a label that's a target of the vector
|
|
180 before deleting the vector itself. */
|
|
181 if (!NOTE_P (label))
|
|
182 LABEL_NUSES (label)--;
|
|
183 }
|
|
184 }
|
|
185
|
|
186 return next;
|
|
187 }
|
|
188
|
|
189 /* Like delete_insn but also purge dead edges from BB. */
|
|
190
|
|
191 rtx
|
|
192 delete_insn_and_edges (rtx insn)
|
|
193 {
|
|
194 rtx x;
|
|
195 bool purge = false;
|
|
196
|
|
197 if (INSN_P (insn)
|
|
198 && BLOCK_FOR_INSN (insn)
|
|
199 && BB_END (BLOCK_FOR_INSN (insn)) == insn)
|
|
200 purge = true;
|
|
201 x = delete_insn (insn);
|
|
202 if (purge)
|
|
203 purge_dead_edges (BLOCK_FOR_INSN (insn));
|
|
204 return x;
|
|
205 }
|
|
206
|
|
207 /* Unlink a chain of insns between START and FINISH, leaving notes
|
|
208 that must be paired. If CLEAR_BB is true, we set bb field for
|
|
209 insns that cannot be removed to NULL. */
|
|
210
|
|
211 void
|
|
212 delete_insn_chain (rtx start, rtx finish, bool clear_bb)
|
|
213 {
|
|
214 rtx next;
|
|
215
|
|
216 /* Unchain the insns one by one. It would be quicker to delete all of these
|
|
217 with a single unchaining, rather than one at a time, but we need to keep
|
|
218 the NOTE's. */
|
|
219 while (1)
|
|
220 {
|
|
221 next = NEXT_INSN (start);
|
|
222 if (NOTE_P (start) && !can_delete_note_p (start))
|
|
223 ;
|
|
224 else
|
|
225 next = delete_insn (start);
|
|
226
|
|
227 if (clear_bb && !INSN_DELETED_P (start))
|
|
228 set_block_for_insn (start, NULL);
|
|
229
|
|
230 if (start == finish)
|
|
231 break;
|
|
232 start = next;
|
|
233 }
|
|
234 }
|
|
235
|
|
236 /* Like delete_insn_chain but also purge dead edges from BB. */
|
|
237
|
|
238 void
|
|
239 delete_insn_chain_and_edges (rtx first, rtx last)
|
|
240 {
|
|
241 bool purge = false;
|
|
242
|
|
243 if (INSN_P (last)
|
|
244 && BLOCK_FOR_INSN (last)
|
|
245 && BB_END (BLOCK_FOR_INSN (last)) == last)
|
|
246 purge = true;
|
|
247 delete_insn_chain (first, last, false);
|
|
248 if (purge)
|
|
249 purge_dead_edges (BLOCK_FOR_INSN (last));
|
|
250 }
|
|
251
|
|
252 /* Create a new basic block consisting of the instructions between HEAD and END
|
|
253 inclusive. This function is designed to allow fast BB construction - reuses
|
|
254 the note and basic block struct in BB_NOTE, if any and do not grow
|
|
255 BASIC_BLOCK chain and should be used directly only by CFG construction code.
|
|
256 END can be NULL in to create new empty basic block before HEAD. Both END
|
|
257 and HEAD can be NULL to create basic block at the end of INSN chain.
|
|
258 AFTER is the basic block we should be put after. */
|
|
259
|
|
260 basic_block
|
|
261 create_basic_block_structure (rtx head, rtx end, rtx bb_note, basic_block after)
|
|
262 {
|
|
263 basic_block bb;
|
|
264
|
|
265 if (bb_note
|
|
266 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
|
|
267 && bb->aux == NULL)
|
|
268 {
|
|
269 /* If we found an existing note, thread it back onto the chain. */
|
|
270
|
|
271 rtx after;
|
|
272
|
|
273 if (LABEL_P (head))
|
|
274 after = head;
|
|
275 else
|
|
276 {
|
|
277 after = PREV_INSN (head);
|
|
278 head = bb_note;
|
|
279 }
|
|
280
|
|
281 if (after != bb_note && NEXT_INSN (after) != bb_note)
|
|
282 reorder_insns_nobb (bb_note, bb_note, after);
|
|
283 }
|
|
284 else
|
|
285 {
|
|
286 /* Otherwise we must create a note and a basic block structure. */
|
|
287
|
|
288 bb = alloc_block ();
|
|
289
|
|
290 init_rtl_bb_info (bb);
|
|
291 if (!head && !end)
|
|
292 head = end = bb_note
|
|
293 = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
|
|
294 else if (LABEL_P (head) && end)
|
|
295 {
|
|
296 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
|
|
297 if (head == end)
|
|
298 end = bb_note;
|
|
299 }
|
|
300 else
|
|
301 {
|
|
302 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
|
|
303 head = bb_note;
|
|
304 if (!end)
|
|
305 end = head;
|
|
306 }
|
|
307
|
|
308 NOTE_BASIC_BLOCK (bb_note) = bb;
|
|
309 }
|
|
310
|
|
311 /* Always include the bb note in the block. */
|
|
312 if (NEXT_INSN (end) == bb_note)
|
|
313 end = bb_note;
|
|
314
|
|
315 BB_HEAD (bb) = head;
|
|
316 BB_END (bb) = end;
|
|
317 bb->index = last_basic_block++;
|
|
318 bb->flags = BB_NEW | BB_RTL;
|
|
319 link_block (bb, after);
|
|
320 SET_BASIC_BLOCK (bb->index, bb);
|
|
321 df_bb_refs_record (bb->index, false);
|
|
322 update_bb_for_insn (bb);
|
|
323 BB_SET_PARTITION (bb, BB_UNPARTITIONED);
|
|
324
|
|
325 /* Tag the block so that we know it has been used when considering
|
|
326 other basic block notes. */
|
|
327 bb->aux = bb;
|
|
328
|
|
329 return bb;
|
|
330 }
|
|
331
|
|
332 /* Create new basic block consisting of instructions in between HEAD and END
|
|
333 and place it to the BB chain after block AFTER. END can be NULL in to
|
|
334 create new empty basic block before HEAD. Both END and HEAD can be NULL to
|
|
335 create basic block at the end of INSN chain. */
|
|
336
|
|
337 static basic_block
|
|
338 rtl_create_basic_block (void *headp, void *endp, basic_block after)
|
|
339 {
|
|
340 rtx head = (rtx) headp, end = (rtx) endp;
|
|
341 basic_block bb;
|
|
342
|
|
343 /* Grow the basic block array if needed. */
|
|
344 if ((size_t) last_basic_block >= VEC_length (basic_block, basic_block_info))
|
|
345 {
|
|
346 size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
|
|
347 VEC_safe_grow_cleared (basic_block, gc, basic_block_info, new_size);
|
|
348 }
|
|
349
|
|
350 n_basic_blocks++;
|
|
351
|
|
352 bb = create_basic_block_structure (head, end, NULL, after);
|
|
353 bb->aux = NULL;
|
|
354 return bb;
|
|
355 }
|
|
356
|
|
357 static basic_block
|
|
358 cfg_layout_create_basic_block (void *head, void *end, basic_block after)
|
|
359 {
|
|
360 basic_block newbb = rtl_create_basic_block (head, end, after);
|
|
361
|
|
362 return newbb;
|
|
363 }
|
|
364
|
|
365 /* Delete the insns in a (non-live) block. We physically delete every
|
|
366 non-deleted-note insn, and update the flow graph appropriately.
|
|
367
|
|
368 Return nonzero if we deleted an exception handler. */
|
|
369
|
|
370 /* ??? Preserving all such notes strikes me as wrong. It would be nice
|
|
371 to post-process the stream to remove empty blocks, loops, ranges, etc. */
|
|
372
|
|
373 static void
|
|
374 rtl_delete_block (basic_block b)
|
|
375 {
|
|
376 rtx insn, end;
|
|
377
|
|
378 /* If the head of this block is a CODE_LABEL, then it might be the
|
|
379 label for an exception handler which can't be reached. We need
|
|
380 to remove the label from the exception_handler_label list. */
|
|
381 insn = BB_HEAD (b);
|
|
382 if (LABEL_P (insn))
|
|
383 maybe_remove_eh_handler (insn);
|
|
384
|
|
385 end = get_last_bb_insn (b);
|
|
386
|
|
387 /* Selectively delete the entire chain. */
|
|
388 BB_HEAD (b) = NULL;
|
|
389 delete_insn_chain (insn, end, true);
|
|
390
|
|
391
|
|
392 if (dump_file)
|
|
393 fprintf (dump_file, "deleting block %d\n", b->index);
|
|
394 df_bb_delete (b->index);
|
|
395 }
|
|
396
|
|
397 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
|
|
398
|
|
399 void
|
|
400 compute_bb_for_insn (void)
|
|
401 {
|
|
402 basic_block bb;
|
|
403
|
|
404 FOR_EACH_BB (bb)
|
|
405 {
|
|
406 rtx end = BB_END (bb);
|
|
407 rtx insn;
|
|
408
|
|
409 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
|
|
410 {
|
|
411 BLOCK_FOR_INSN (insn) = bb;
|
|
412 if (insn == end)
|
|
413 break;
|
|
414 }
|
|
415 }
|
|
416 }
|
|
417
|
|
418 /* Release the basic_block_for_insn array. */
|
|
419
|
|
420 unsigned int
|
|
421 free_bb_for_insn (void)
|
|
422 {
|
|
423 rtx insn;
|
|
424 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
|
|
425 if (!BARRIER_P (insn))
|
|
426 BLOCK_FOR_INSN (insn) = NULL;
|
|
427 return 0;
|
|
428 }
|
|
429
|
|
430 struct rtl_opt_pass pass_free_cfg =
|
|
431 {
|
|
432 {
|
|
433 RTL_PASS,
|
|
434 NULL, /* name */
|
|
435 NULL, /* gate */
|
|
436 free_bb_for_insn, /* execute */
|
|
437 NULL, /* sub */
|
|
438 NULL, /* next */
|
|
439 0, /* static_pass_number */
|
|
440 0, /* tv_id */
|
|
441 0, /* properties_required */
|
|
442 0, /* properties_provided */
|
|
443 PROP_cfg, /* properties_destroyed */
|
|
444 0, /* todo_flags_start */
|
|
445 0, /* todo_flags_finish */
|
|
446 }
|
|
447 };
|
|
448
|
|
449 /* Return RTX to emit after when we want to emit code on the entry of function. */
|
|
450 rtx
|
|
451 entry_of_function (void)
|
|
452 {
|
|
453 return (n_basic_blocks > NUM_FIXED_BLOCKS ?
|
|
454 BB_HEAD (ENTRY_BLOCK_PTR->next_bb) : get_insns ());
|
|
455 }
|
|
456
|
|
457 /* Emit INSN at the entry point of the function, ensuring that it is only
|
|
458 executed once per function. */
|
|
459 void
|
|
460 emit_insn_at_entry (rtx insn)
|
|
461 {
|
|
462 edge_iterator ei = ei_start (ENTRY_BLOCK_PTR->succs);
|
|
463 edge e = ei_safe_edge (ei);
|
|
464 gcc_assert (e->flags & EDGE_FALLTHRU);
|
|
465
|
|
466 insert_insn_on_edge (insn, e);
|
|
467 commit_edge_insertions ();
|
|
468 }
|
|
469
|
|
470 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
|
|
471 (or BARRIER if found) and notify df of the bb change.
|
|
472 The insn chain range is inclusive
|
|
473 (i.e. both BEGIN and END will be updated. */
|
|
474
|
|
475 static void
|
|
476 update_bb_for_insn_chain (rtx begin, rtx end, basic_block bb)
|
|
477 {
|
|
478 rtx insn;
|
|
479
|
|
480 end = NEXT_INSN (end);
|
|
481 for (insn = begin; insn != end; insn = NEXT_INSN (insn))
|
|
482 if (!BARRIER_P (insn))
|
|
483 df_insn_change_bb (insn, bb);
|
|
484 }
|
|
485
|
|
486 /* Update BLOCK_FOR_INSN of insns in BB to BB,
|
|
487 and notify df of the change. */
|
|
488
|
|
489 void
|
|
490 update_bb_for_insn (basic_block bb)
|
|
491 {
|
|
492 update_bb_for_insn_chain (BB_HEAD (bb), BB_END (bb), bb);
|
|
493 }
|
|
494
|
|
495
|
|
496 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
|
|
497 note associated with the BLOCK. */
|
|
498
|
|
499 static rtx
|
|
500 first_insn_after_basic_block_note (basic_block block)
|
|
501 {
|
|
502 rtx insn;
|
|
503
|
|
504 /* Get the first instruction in the block. */
|
|
505 insn = BB_HEAD (block);
|
|
506
|
|
507 if (insn == NULL_RTX)
|
|
508 return NULL_RTX;
|
|
509 if (LABEL_P (insn))
|
|
510 insn = NEXT_INSN (insn);
|
|
511 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
|
|
512
|
|
513 return NEXT_INSN (insn);
|
|
514 }
|
|
515
|
|
516 /* Creates a new basic block just after basic block B by splitting
|
|
517 everything after specified instruction I. */
|
|
518
|
|
519 static basic_block
|
|
520 rtl_split_block (basic_block bb, void *insnp)
|
|
521 {
|
|
522 basic_block new_bb;
|
|
523 rtx insn = (rtx) insnp;
|
|
524 edge e;
|
|
525 edge_iterator ei;
|
|
526
|
|
527 if (!insn)
|
|
528 {
|
|
529 insn = first_insn_after_basic_block_note (bb);
|
|
530
|
|
531 if (insn)
|
|
532 insn = PREV_INSN (insn);
|
|
533 else
|
|
534 insn = get_last_insn ();
|
|
535 }
|
|
536
|
|
537 /* We probably should check type of the insn so that we do not create
|
|
538 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
|
|
539 bother. */
|
|
540 if (insn == BB_END (bb))
|
|
541 emit_note_after (NOTE_INSN_DELETED, insn);
|
|
542
|
|
543 /* Create the new basic block. */
|
|
544 new_bb = create_basic_block (NEXT_INSN (insn), BB_END (bb), bb);
|
|
545 BB_COPY_PARTITION (new_bb, bb);
|
|
546 BB_END (bb) = insn;
|
|
547
|
|
548 /* Redirect the outgoing edges. */
|
|
549 new_bb->succs = bb->succs;
|
|
550 bb->succs = NULL;
|
|
551 FOR_EACH_EDGE (e, ei, new_bb->succs)
|
|
552 e->src = new_bb;
|
|
553
|
|
554 /* The new block starts off being dirty. */
|
|
555 df_set_bb_dirty (bb);
|
|
556 return new_bb;
|
|
557 }
|
|
558
|
|
559 /* Blocks A and B are to be merged into a single block A. The insns
|
|
560 are already contiguous. */
|
|
561
|
|
562 static void
|
|
563 rtl_merge_blocks (basic_block a, basic_block b)
|
|
564 {
|
|
565 rtx b_head = BB_HEAD (b), b_end = BB_END (b), a_end = BB_END (a);
|
|
566 rtx del_first = NULL_RTX, del_last = NULL_RTX;
|
|
567 int b_empty = 0;
|
|
568
|
|
569 if (dump_file)
|
|
570 fprintf (dump_file, "merging block %d into block %d\n", b->index, a->index);
|
|
571
|
|
572 /* If there was a CODE_LABEL beginning B, delete it. */
|
|
573 if (LABEL_P (b_head))
|
|
574 {
|
|
575 /* This might have been an EH label that no longer has incoming
|
|
576 EH edges. Update data structures to match. */
|
|
577 maybe_remove_eh_handler (b_head);
|
|
578
|
|
579 /* Detect basic blocks with nothing but a label. This can happen
|
|
580 in particular at the end of a function. */
|
|
581 if (b_head == b_end)
|
|
582 b_empty = 1;
|
|
583
|
|
584 del_first = del_last = b_head;
|
|
585 b_head = NEXT_INSN (b_head);
|
|
586 }
|
|
587
|
|
588 /* Delete the basic block note and handle blocks containing just that
|
|
589 note. */
|
|
590 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
|
|
591 {
|
|
592 if (b_head == b_end)
|
|
593 b_empty = 1;
|
|
594 if (! del_last)
|
|
595 del_first = b_head;
|
|
596
|
|
597 del_last = b_head;
|
|
598 b_head = NEXT_INSN (b_head);
|
|
599 }
|
|
600
|
|
601 /* If there was a jump out of A, delete it. */
|
|
602 if (JUMP_P (a_end))
|
|
603 {
|
|
604 rtx prev;
|
|
605
|
|
606 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
|
|
607 if (!NOTE_P (prev)
|
|
608 || NOTE_INSN_BASIC_BLOCK_P (prev)
|
|
609 || prev == BB_HEAD (a))
|
|
610 break;
|
|
611
|
|
612 del_first = a_end;
|
|
613
|
|
614 #ifdef HAVE_cc0
|
|
615 /* If this was a conditional jump, we need to also delete
|
|
616 the insn that set cc0. */
|
|
617 if (only_sets_cc0_p (prev))
|
|
618 {
|
|
619 rtx tmp = prev;
|
|
620
|
|
621 prev = prev_nonnote_insn (prev);
|
|
622 if (!prev)
|
|
623 prev = BB_HEAD (a);
|
|
624 del_first = tmp;
|
|
625 }
|
|
626 #endif
|
|
627
|
|
628 a_end = PREV_INSN (del_first);
|
|
629 }
|
|
630 else if (BARRIER_P (NEXT_INSN (a_end)))
|
|
631 del_first = NEXT_INSN (a_end);
|
|
632
|
|
633 /* Delete everything marked above as well as crap that might be
|
|
634 hanging out between the two blocks. */
|
|
635 BB_HEAD (b) = NULL;
|
|
636 delete_insn_chain (del_first, del_last, true);
|
|
637
|
|
638 /* Reassociate the insns of B with A. */
|
|
639 if (!b_empty)
|
|
640 {
|
|
641 update_bb_for_insn_chain (a_end, b_end, a);
|
|
642
|
|
643 a_end = b_end;
|
|
644 }
|
|
645
|
|
646 df_bb_delete (b->index);
|
|
647 BB_END (a) = a_end;
|
|
648 }
|
|
649
|
|
650
|
|
651 /* Return true when block A and B can be merged. */
|
|
652
|
|
653 static bool
|
|
654 rtl_can_merge_blocks (basic_block a, basic_block b)
|
|
655 {
|
|
656 /* If we are partitioning hot/cold basic blocks, we don't want to
|
|
657 mess up unconditional or indirect jumps that cross between hot
|
|
658 and cold sections.
|
|
659
|
|
660 Basic block partitioning may result in some jumps that appear to
|
|
661 be optimizable (or blocks that appear to be mergeable), but which really
|
|
662 must be left untouched (they are required to make it safely across
|
|
663 partition boundaries). See the comments at the top of
|
|
664 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
|
|
665
|
|
666 if (BB_PARTITION (a) != BB_PARTITION (b))
|
|
667 return false;
|
|
668
|
|
669 /* There must be exactly one edge in between the blocks. */
|
|
670 return (single_succ_p (a)
|
|
671 && single_succ (a) == b
|
|
672 && single_pred_p (b)
|
|
673 && a != b
|
|
674 /* Must be simple edge. */
|
|
675 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
|
|
676 && a->next_bb == b
|
|
677 && a != ENTRY_BLOCK_PTR && b != EXIT_BLOCK_PTR
|
|
678 /* If the jump insn has side effects,
|
|
679 we can't kill the edge. */
|
|
680 && (!JUMP_P (BB_END (a))
|
|
681 || (reload_completed
|
|
682 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
|
|
683 }
|
|
684
|
|
685 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
|
|
686 exist. */
|
|
687
|
|
688 rtx
|
|
689 block_label (basic_block block)
|
|
690 {
|
|
691 if (block == EXIT_BLOCK_PTR)
|
|
692 return NULL_RTX;
|
|
693
|
|
694 if (!LABEL_P (BB_HEAD (block)))
|
|
695 {
|
|
696 BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block));
|
|
697 }
|
|
698
|
|
699 return BB_HEAD (block);
|
|
700 }
|
|
701
|
|
702 /* Attempt to perform edge redirection by replacing possibly complex jump
|
|
703 instruction by unconditional jump or removing jump completely. This can
|
|
704 apply only if all edges now point to the same block. The parameters and
|
|
705 return values are equivalent to redirect_edge_and_branch. */
|
|
706
|
|
707 edge
|
|
708 try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout)
|
|
709 {
|
|
710 basic_block src = e->src;
|
|
711 rtx insn = BB_END (src), kill_from;
|
|
712 rtx set;
|
|
713 int fallthru = 0;
|
|
714
|
|
715 /* If we are partitioning hot/cold basic blocks, we don't want to
|
|
716 mess up unconditional or indirect jumps that cross between hot
|
|
717 and cold sections.
|
|
718
|
|
719 Basic block partitioning may result in some jumps that appear to
|
|
720 be optimizable (or blocks that appear to be mergeable), but which really
|
|
721 must be left untouched (they are required to make it safely across
|
|
722 partition boundaries). See the comments at the top of
|
|
723 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
|
|
724
|
|
725 if (find_reg_note (insn, REG_CROSSING_JUMP, NULL_RTX)
|
|
726 || BB_PARTITION (src) != BB_PARTITION (target))
|
|
727 return NULL;
|
|
728
|
|
729 /* We can replace or remove a complex jump only when we have exactly
|
|
730 two edges. Also, if we have exactly one outgoing edge, we can
|
|
731 redirect that. */
|
|
732 if (EDGE_COUNT (src->succs) >= 3
|
|
733 /* Verify that all targets will be TARGET. Specifically, the
|
|
734 edge that is not E must also go to TARGET. */
|
|
735 || (EDGE_COUNT (src->succs) == 2
|
|
736 && EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target))
|
|
737 return NULL;
|
|
738
|
|
739 if (!onlyjump_p (insn))
|
|
740 return NULL;
|
|
741 if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL))
|
|
742 return NULL;
|
|
743
|
|
744 /* Avoid removing branch with side effects. */
|
|
745 set = single_set (insn);
|
|
746 if (!set || side_effects_p (set))
|
|
747 return NULL;
|
|
748
|
|
749 /* In case we zap a conditional jump, we'll need to kill
|
|
750 the cc0 setter too. */
|
|
751 kill_from = insn;
|
|
752 #ifdef HAVE_cc0
|
|
753 if (reg_mentioned_p (cc0_rtx, PATTERN (insn))
|
|
754 && only_sets_cc0_p (PREV_INSN (insn)))
|
|
755 kill_from = PREV_INSN (insn);
|
|
756 #endif
|
|
757
|
|
758 /* See if we can create the fallthru edge. */
|
|
759 if (in_cfglayout || can_fallthru (src, target))
|
|
760 {
|
|
761 if (dump_file)
|
|
762 fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn));
|
|
763 fallthru = 1;
|
|
764
|
|
765 /* Selectively unlink whole insn chain. */
|
|
766 if (in_cfglayout)
|
|
767 {
|
|
768 rtx insn = src->il.rtl->footer;
|
|
769
|
|
770 delete_insn_chain (kill_from, BB_END (src), false);
|
|
771
|
|
772 /* Remove barriers but keep jumptables. */
|
|
773 while (insn)
|
|
774 {
|
|
775 if (BARRIER_P (insn))
|
|
776 {
|
|
777 if (PREV_INSN (insn))
|
|
778 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
|
|
779 else
|
|
780 src->il.rtl->footer = NEXT_INSN (insn);
|
|
781 if (NEXT_INSN (insn))
|
|
782 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
|
|
783 }
|
|
784 if (LABEL_P (insn))
|
|
785 break;
|
|
786 insn = NEXT_INSN (insn);
|
|
787 }
|
|
788 }
|
|
789 else
|
|
790 delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target)),
|
|
791 false);
|
|
792 }
|
|
793
|
|
794 /* If this already is simplejump, redirect it. */
|
|
795 else if (simplejump_p (insn))
|
|
796 {
|
|
797 if (e->dest == target)
|
|
798 return NULL;
|
|
799 if (dump_file)
|
|
800 fprintf (dump_file, "Redirecting jump %i from %i to %i.\n",
|
|
801 INSN_UID (insn), e->dest->index, target->index);
|
|
802 if (!redirect_jump (insn, block_label (target), 0))
|
|
803 {
|
|
804 gcc_assert (target == EXIT_BLOCK_PTR);
|
|
805 return NULL;
|
|
806 }
|
|
807 }
|
|
808
|
|
809 /* Cannot do anything for target exit block. */
|
|
810 else if (target == EXIT_BLOCK_PTR)
|
|
811 return NULL;
|
|
812
|
|
813 /* Or replace possibly complicated jump insn by simple jump insn. */
|
|
814 else
|
|
815 {
|
|
816 rtx target_label = block_label (target);
|
|
817 rtx barrier, label, table;
|
|
818
|
|
819 emit_jump_insn_after_noloc (gen_jump (target_label), insn);
|
|
820 JUMP_LABEL (BB_END (src)) = target_label;
|
|
821 LABEL_NUSES (target_label)++;
|
|
822 if (dump_file)
|
|
823 fprintf (dump_file, "Replacing insn %i by jump %i\n",
|
|
824 INSN_UID (insn), INSN_UID (BB_END (src)));
|
|
825
|
|
826
|
|
827 delete_insn_chain (kill_from, insn, false);
|
|
828
|
|
829 /* Recognize a tablejump that we are converting to a
|
|
830 simple jump and remove its associated CODE_LABEL
|
|
831 and ADDR_VEC or ADDR_DIFF_VEC. */
|
|
832 if (tablejump_p (insn, &label, &table))
|
|
833 delete_insn_chain (label, table, false);
|
|
834
|
|
835 barrier = next_nonnote_insn (BB_END (src));
|
|
836 if (!barrier || !BARRIER_P (barrier))
|
|
837 emit_barrier_after (BB_END (src));
|
|
838 else
|
|
839 {
|
|
840 if (barrier != NEXT_INSN (BB_END (src)))
|
|
841 {
|
|
842 /* Move the jump before barrier so that the notes
|
|
843 which originally were or were created before jump table are
|
|
844 inside the basic block. */
|
|
845 rtx new_insn = BB_END (src);
|
|
846
|
|
847 update_bb_for_insn_chain (NEXT_INSN (BB_END (src)),
|
|
848 PREV_INSN (barrier), src);
|
|
849
|
|
850 NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn);
|
|
851 PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn);
|
|
852
|
|
853 NEXT_INSN (new_insn) = barrier;
|
|
854 NEXT_INSN (PREV_INSN (barrier)) = new_insn;
|
|
855
|
|
856 PREV_INSN (new_insn) = PREV_INSN (barrier);
|
|
857 PREV_INSN (barrier) = new_insn;
|
|
858 }
|
|
859 }
|
|
860 }
|
|
861
|
|
862 /* Keep only one edge out and set proper flags. */
|
|
863 if (!single_succ_p (src))
|
|
864 remove_edge (e);
|
|
865 gcc_assert (single_succ_p (src));
|
|
866
|
|
867 e = single_succ_edge (src);
|
|
868 if (fallthru)
|
|
869 e->flags = EDGE_FALLTHRU;
|
|
870 else
|
|
871 e->flags = 0;
|
|
872
|
|
873 e->probability = REG_BR_PROB_BASE;
|
|
874 e->count = src->count;
|
|
875
|
|
876 if (e->dest != target)
|
|
877 redirect_edge_succ (e, target);
|
|
878 return e;
|
|
879 }
|
|
880
|
|
881 /* Redirect edge representing branch of (un)conditional jump or tablejump,
|
|
882 NULL on failure */
|
|
883 static edge
|
|
884 redirect_branch_edge (edge e, basic_block target)
|
|
885 {
|
|
886 rtx tmp;
|
|
887 rtx old_label = BB_HEAD (e->dest);
|
|
888 basic_block src = e->src;
|
|
889 rtx insn = BB_END (src);
|
|
890
|
|
891 /* We can only redirect non-fallthru edges of jump insn. */
|
|
892 if (e->flags & EDGE_FALLTHRU)
|
|
893 return NULL;
|
|
894 else if (!JUMP_P (insn))
|
|
895 return NULL;
|
|
896
|
|
897 /* Recognize a tablejump and adjust all matching cases. */
|
|
898 if (tablejump_p (insn, NULL, &tmp))
|
|
899 {
|
|
900 rtvec vec;
|
|
901 int j;
|
|
902 rtx new_label = block_label (target);
|
|
903
|
|
904 if (target == EXIT_BLOCK_PTR)
|
|
905 return NULL;
|
|
906 if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
|
|
907 vec = XVEC (PATTERN (tmp), 0);
|
|
908 else
|
|
909 vec = XVEC (PATTERN (tmp), 1);
|
|
910
|
|
911 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
|
|
912 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
|
|
913 {
|
|
914 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
|
|
915 --LABEL_NUSES (old_label);
|
|
916 ++LABEL_NUSES (new_label);
|
|
917 }
|
|
918
|
|
919 /* Handle casesi dispatch insns. */
|
|
920 if ((tmp = single_set (insn)) != NULL
|
|
921 && SET_DEST (tmp) == pc_rtx
|
|
922 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
|
|
923 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
|
|
924 && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
|
|
925 {
|
|
926 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (Pmode,
|
|
927 new_label);
|
|
928 --LABEL_NUSES (old_label);
|
|
929 ++LABEL_NUSES (new_label);
|
|
930 }
|
|
931 }
|
|
932 else
|
|
933 {
|
|
934 /* ?? We may play the games with moving the named labels from
|
|
935 one basic block to the other in case only one computed_jump is
|
|
936 available. */
|
|
937 if (computed_jump_p (insn)
|
|
938 /* A return instruction can't be redirected. */
|
|
939 || returnjump_p (insn))
|
|
940 return NULL;
|
|
941
|
|
942 /* If the insn doesn't go where we think, we're confused. */
|
|
943 gcc_assert (JUMP_LABEL (insn) == old_label);
|
|
944
|
|
945 /* If the substitution doesn't succeed, die. This can happen
|
|
946 if the back end emitted unrecognizable instructions or if
|
|
947 target is exit block on some arches. */
|
|
948 if (!redirect_jump (insn, block_label (target), 0))
|
|
949 {
|
|
950 gcc_assert (target == EXIT_BLOCK_PTR);
|
|
951 return NULL;
|
|
952 }
|
|
953 }
|
|
954
|
|
955 if (dump_file)
|
|
956 fprintf (dump_file, "Edge %i->%i redirected to %i\n",
|
|
957 e->src->index, e->dest->index, target->index);
|
|
958
|
|
959 if (e->dest != target)
|
|
960 e = redirect_edge_succ_nodup (e, target);
|
|
961
|
|
962 return e;
|
|
963 }
|
|
964
|
|
965 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
|
|
966 expense of adding new instructions or reordering basic blocks.
|
|
967
|
|
968 Function can be also called with edge destination equivalent to the TARGET.
|
|
969 Then it should try the simplifications and do nothing if none is possible.
|
|
970
|
|
971 Return edge representing the branch if transformation succeeded. Return NULL
|
|
972 on failure.
|
|
973 We still return NULL in case E already destinated TARGET and we didn't
|
|
974 managed to simplify instruction stream. */
|
|
975
|
|
976 static edge
|
|
977 rtl_redirect_edge_and_branch (edge e, basic_block target)
|
|
978 {
|
|
979 edge ret;
|
|
980 basic_block src = e->src;
|
|
981
|
|
982 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
|
|
983 return NULL;
|
|
984
|
|
985 if (e->dest == target)
|
|
986 return e;
|
|
987
|
|
988 if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL)
|
|
989 {
|
|
990 df_set_bb_dirty (src);
|
|
991 return ret;
|
|
992 }
|
|
993
|
|
994 ret = redirect_branch_edge (e, target);
|
|
995 if (!ret)
|
|
996 return NULL;
|
|
997
|
|
998 df_set_bb_dirty (src);
|
|
999 return ret;
|
|
1000 }
|
|
1001
|
|
1002 /* Like force_nonfallthru below, but additionally performs redirection
|
|
1003 Used by redirect_edge_and_branch_force. */
|
|
1004
|
|
1005 static basic_block
|
|
1006 force_nonfallthru_and_redirect (edge e, basic_block target)
|
|
1007 {
|
|
1008 basic_block jump_block, new_bb = NULL, src = e->src;
|
|
1009 rtx note;
|
|
1010 edge new_edge;
|
|
1011 int abnormal_edge_flags = 0;
|
|
1012 int loc;
|
|
1013
|
|
1014 /* In the case the last instruction is conditional jump to the next
|
|
1015 instruction, first redirect the jump itself and then continue
|
|
1016 by creating a basic block afterwards to redirect fallthru edge. */
|
|
1017 if (e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR
|
|
1018 && any_condjump_p (BB_END (e->src))
|
|
1019 && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest))
|
|
1020 {
|
|
1021 rtx note;
|
|
1022 edge b = unchecked_make_edge (e->src, target, 0);
|
|
1023 bool redirected;
|
|
1024
|
|
1025 redirected = redirect_jump (BB_END (e->src), block_label (target), 0);
|
|
1026 gcc_assert (redirected);
|
|
1027
|
|
1028 note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX);
|
|
1029 if (note)
|
|
1030 {
|
|
1031 int prob = INTVAL (XEXP (note, 0));
|
|
1032
|
|
1033 b->probability = prob;
|
|
1034 b->count = e->count * prob / REG_BR_PROB_BASE;
|
|
1035 e->probability -= e->probability;
|
|
1036 e->count -= b->count;
|
|
1037 if (e->probability < 0)
|
|
1038 e->probability = 0;
|
|
1039 if (e->count < 0)
|
|
1040 e->count = 0;
|
|
1041 }
|
|
1042 }
|
|
1043
|
|
1044 if (e->flags & EDGE_ABNORMAL)
|
|
1045 {
|
|
1046 /* Irritating special case - fallthru edge to the same block as abnormal
|
|
1047 edge.
|
|
1048 We can't redirect abnormal edge, but we still can split the fallthru
|
|
1049 one and create separate abnormal edge to original destination.
|
|
1050 This allows bb-reorder to make such edge non-fallthru. */
|
|
1051 gcc_assert (e->dest == target);
|
|
1052 abnormal_edge_flags = e->flags & ~(EDGE_FALLTHRU | EDGE_CAN_FALLTHRU);
|
|
1053 e->flags &= EDGE_FALLTHRU | EDGE_CAN_FALLTHRU;
|
|
1054 }
|
|
1055 else
|
|
1056 {
|
|
1057 gcc_assert (e->flags & EDGE_FALLTHRU);
|
|
1058 if (e->src == ENTRY_BLOCK_PTR)
|
|
1059 {
|
|
1060 /* We can't redirect the entry block. Create an empty block
|
|
1061 at the start of the function which we use to add the new
|
|
1062 jump. */
|
|
1063 edge tmp;
|
|
1064 edge_iterator ei;
|
|
1065 bool found = false;
|
|
1066
|
|
1067 basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL, ENTRY_BLOCK_PTR);
|
|
1068
|
|
1069 /* Change the existing edge's source to be the new block, and add
|
|
1070 a new edge from the entry block to the new block. */
|
|
1071 e->src = bb;
|
|
1072 for (ei = ei_start (ENTRY_BLOCK_PTR->succs); (tmp = ei_safe_edge (ei)); )
|
|
1073 {
|
|
1074 if (tmp == e)
|
|
1075 {
|
|
1076 VEC_unordered_remove (edge, ENTRY_BLOCK_PTR->succs, ei.index);
|
|
1077 found = true;
|
|
1078 break;
|
|
1079 }
|
|
1080 else
|
|
1081 ei_next (&ei);
|
|
1082 }
|
|
1083
|
|
1084 gcc_assert (found);
|
|
1085
|
|
1086 VEC_safe_push (edge, gc, bb->succs, e);
|
|
1087 make_single_succ_edge (ENTRY_BLOCK_PTR, bb, EDGE_FALLTHRU);
|
|
1088 }
|
|
1089 }
|
|
1090
|
|
1091 if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags)
|
|
1092 {
|
|
1093 /* Create the new structures. */
|
|
1094
|
|
1095 /* If the old block ended with a tablejump, skip its table
|
|
1096 by searching forward from there. Otherwise start searching
|
|
1097 forward from the last instruction of the old block. */
|
|
1098 if (!tablejump_p (BB_END (e->src), NULL, ¬e))
|
|
1099 note = BB_END (e->src);
|
|
1100 note = NEXT_INSN (note);
|
|
1101
|
|
1102 jump_block = create_basic_block (note, NULL, e->src);
|
|
1103 jump_block->count = e->count;
|
|
1104 jump_block->frequency = EDGE_FREQUENCY (e);
|
|
1105 jump_block->loop_depth = target->loop_depth;
|
|
1106
|
|
1107 /* Make sure new block ends up in correct hot/cold section. */
|
|
1108
|
|
1109 BB_COPY_PARTITION (jump_block, e->src);
|
|
1110 if (flag_reorder_blocks_and_partition
|
|
1111 && targetm.have_named_sections
|
|
1112 && JUMP_P (BB_END (jump_block))
|
|
1113 && !any_condjump_p (BB_END (jump_block))
|
|
1114 && (EDGE_SUCC (jump_block, 0)->flags & EDGE_CROSSING))
|
|
1115 add_reg_note (BB_END (jump_block), REG_CROSSING_JUMP, NULL_RTX);
|
|
1116
|
|
1117 /* Wire edge in. */
|
|
1118 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
|
|
1119 new_edge->probability = e->probability;
|
|
1120 new_edge->count = e->count;
|
|
1121
|
|
1122 /* Redirect old edge. */
|
|
1123 redirect_edge_pred (e, jump_block);
|
|
1124 e->probability = REG_BR_PROB_BASE;
|
|
1125
|
|
1126 new_bb = jump_block;
|
|
1127 }
|
|
1128 else
|
|
1129 jump_block = e->src;
|
|
1130
|
|
1131 if (e->goto_locus && e->goto_block == NULL)
|
|
1132 loc = e->goto_locus;
|
|
1133 else
|
|
1134 loc = 0;
|
|
1135 e->flags &= ~EDGE_FALLTHRU;
|
|
1136 if (target == EXIT_BLOCK_PTR)
|
|
1137 {
|
|
1138 #ifdef HAVE_return
|
|
1139 emit_jump_insn_after_setloc (gen_return (), BB_END (jump_block), loc);
|
|
1140 #else
|
|
1141 gcc_unreachable ();
|
|
1142 #endif
|
|
1143 }
|
|
1144 else
|
|
1145 {
|
|
1146 rtx label = block_label (target);
|
|
1147 emit_jump_insn_after_setloc (gen_jump (label), BB_END (jump_block), loc);
|
|
1148 JUMP_LABEL (BB_END (jump_block)) = label;
|
|
1149 LABEL_NUSES (label)++;
|
|
1150 }
|
|
1151
|
|
1152 emit_barrier_after (BB_END (jump_block));
|
|
1153 redirect_edge_succ_nodup (e, target);
|
|
1154
|
|
1155 if (abnormal_edge_flags)
|
|
1156 make_edge (src, target, abnormal_edge_flags);
|
|
1157
|
|
1158 df_mark_solutions_dirty ();
|
|
1159 return new_bb;
|
|
1160 }
|
|
1161
|
|
1162 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
|
|
1163 (and possibly create new basic block) to make edge non-fallthru.
|
|
1164 Return newly created BB or NULL if none. */
|
|
1165
|
|
1166 basic_block
|
|
1167 force_nonfallthru (edge e)
|
|
1168 {
|
|
1169 return force_nonfallthru_and_redirect (e, e->dest);
|
|
1170 }
|
|
1171
|
|
1172 /* Redirect edge even at the expense of creating new jump insn or
|
|
1173 basic block. Return new basic block if created, NULL otherwise.
|
|
1174 Conversion must be possible. */
|
|
1175
|
|
1176 static basic_block
|
|
1177 rtl_redirect_edge_and_branch_force (edge e, basic_block target)
|
|
1178 {
|
|
1179 if (redirect_edge_and_branch (e, target)
|
|
1180 || e->dest == target)
|
|
1181 return NULL;
|
|
1182
|
|
1183 /* In case the edge redirection failed, try to force it to be non-fallthru
|
|
1184 and redirect newly created simplejump. */
|
|
1185 df_set_bb_dirty (e->src);
|
|
1186 return force_nonfallthru_and_redirect (e, target);
|
|
1187 }
|
|
1188
|
|
1189 /* The given edge should potentially be a fallthru edge. If that is in
|
|
1190 fact true, delete the jump and barriers that are in the way. */
|
|
1191
|
|
1192 static void
|
|
1193 rtl_tidy_fallthru_edge (edge e)
|
|
1194 {
|
|
1195 rtx q;
|
|
1196 basic_block b = e->src, c = b->next_bb;
|
|
1197
|
|
1198 /* ??? In a late-running flow pass, other folks may have deleted basic
|
|
1199 blocks by nopping out blocks, leaving multiple BARRIERs between here
|
|
1200 and the target label. They ought to be chastised and fixed.
|
|
1201
|
|
1202 We can also wind up with a sequence of undeletable labels between
|
|
1203 one block and the next.
|
|
1204
|
|
1205 So search through a sequence of barriers, labels, and notes for
|
|
1206 the head of block C and assert that we really do fall through. */
|
|
1207
|
|
1208 for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q))
|
|
1209 if (INSN_P (q))
|
|
1210 return;
|
|
1211
|
|
1212 /* Remove what will soon cease being the jump insn from the source block.
|
|
1213 If block B consisted only of this single jump, turn it into a deleted
|
|
1214 note. */
|
|
1215 q = BB_END (b);
|
|
1216 if (JUMP_P (q)
|
|
1217 && onlyjump_p (q)
|
|
1218 && (any_uncondjump_p (q)
|
|
1219 || single_succ_p (b)))
|
|
1220 {
|
|
1221 #ifdef HAVE_cc0
|
|
1222 /* If this was a conditional jump, we need to also delete
|
|
1223 the insn that set cc0. */
|
|
1224 if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
|
|
1225 q = PREV_INSN (q);
|
|
1226 #endif
|
|
1227
|
|
1228 q = PREV_INSN (q);
|
|
1229 }
|
|
1230
|
|
1231 /* Selectively unlink the sequence. */
|
|
1232 if (q != PREV_INSN (BB_HEAD (c)))
|
|
1233 delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)), false);
|
|
1234
|
|
1235 e->flags |= EDGE_FALLTHRU;
|
|
1236 }
|
|
1237
|
|
1238 /* Should move basic block BB after basic block AFTER. NIY. */
|
|
1239
|
|
1240 static bool
|
|
1241 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED,
|
|
1242 basic_block after ATTRIBUTE_UNUSED)
|
|
1243 {
|
|
1244 return false;
|
|
1245 }
|
|
1246
|
|
1247 /* Split a (typically critical) edge. Return the new block.
|
|
1248 The edge must not be abnormal.
|
|
1249
|
|
1250 ??? The code generally expects to be called on critical edges.
|
|
1251 The case of a block ending in an unconditional jump to a
|
|
1252 block with multiple predecessors is not handled optimally. */
|
|
1253
|
|
1254 static basic_block
|
|
1255 rtl_split_edge (edge edge_in)
|
|
1256 {
|
|
1257 basic_block bb;
|
|
1258 rtx before;
|
|
1259
|
|
1260 /* Abnormal edges cannot be split. */
|
|
1261 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
|
|
1262
|
|
1263 /* We are going to place the new block in front of edge destination.
|
|
1264 Avoid existence of fallthru predecessors. */
|
|
1265 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
|
|
1266 {
|
|
1267 edge e;
|
|
1268 edge_iterator ei;
|
|
1269
|
|
1270 FOR_EACH_EDGE (e, ei, edge_in->dest->preds)
|
|
1271 if (e->flags & EDGE_FALLTHRU)
|
|
1272 break;
|
|
1273
|
|
1274 if (e)
|
|
1275 force_nonfallthru (e);
|
|
1276 }
|
|
1277
|
|
1278 /* Create the basic block note. */
|
|
1279 if (edge_in->dest != EXIT_BLOCK_PTR)
|
|
1280 before = BB_HEAD (edge_in->dest);
|
|
1281 else
|
|
1282 before = NULL_RTX;
|
|
1283
|
|
1284 /* If this is a fall through edge to the exit block, the blocks might be
|
|
1285 not adjacent, and the right place is the after the source. */
|
|
1286 if (edge_in->flags & EDGE_FALLTHRU && edge_in->dest == EXIT_BLOCK_PTR)
|
|
1287 {
|
|
1288 before = NEXT_INSN (BB_END (edge_in->src));
|
|
1289 bb = create_basic_block (before, NULL, edge_in->src);
|
|
1290 BB_COPY_PARTITION (bb, edge_in->src);
|
|
1291 }
|
|
1292 else
|
|
1293 {
|
|
1294 bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
|
|
1295 /* ??? Why not edge_in->dest->prev_bb here? */
|
|
1296 BB_COPY_PARTITION (bb, edge_in->dest);
|
|
1297 }
|
|
1298
|
|
1299 make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
|
|
1300
|
|
1301 /* For non-fallthru edges, we must adjust the predecessor's
|
|
1302 jump instruction to target our new block. */
|
|
1303 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
|
|
1304 {
|
|
1305 edge redirected = redirect_edge_and_branch (edge_in, bb);
|
|
1306 gcc_assert (redirected);
|
|
1307 }
|
|
1308 else
|
|
1309 redirect_edge_succ (edge_in, bb);
|
|
1310
|
|
1311 return bb;
|
|
1312 }
|
|
1313
|
|
1314 /* Queue instructions for insertion on an edge between two basic blocks.
|
|
1315 The new instructions and basic blocks (if any) will not appear in the
|
|
1316 CFG until commit_edge_insertions is called. */
|
|
1317
|
|
1318 void
|
|
1319 insert_insn_on_edge (rtx pattern, edge e)
|
|
1320 {
|
|
1321 /* We cannot insert instructions on an abnormal critical edge.
|
|
1322 It will be easier to find the culprit if we die now. */
|
|
1323 gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)));
|
|
1324
|
|
1325 if (e->insns.r == NULL_RTX)
|
|
1326 start_sequence ();
|
|
1327 else
|
|
1328 push_to_sequence (e->insns.r);
|
|
1329
|
|
1330 emit_insn (pattern);
|
|
1331
|
|
1332 e->insns.r = get_insns ();
|
|
1333 end_sequence ();
|
|
1334 }
|
|
1335
|
|
1336 /* Update the CFG for the instructions queued on edge E. */
|
|
1337
|
|
1338 static void
|
|
1339 commit_one_edge_insertion (edge e)
|
|
1340 {
|
|
1341 rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
|
|
1342 basic_block bb = NULL;
|
|
1343
|
|
1344 /* Pull the insns off the edge now since the edge might go away. */
|
|
1345 insns = e->insns.r;
|
|
1346 e->insns.r = NULL_RTX;
|
|
1347
|
|
1348 if (!before && !after)
|
|
1349 {
|
|
1350 /* Figure out where to put these things. If the destination has
|
|
1351 one predecessor, insert there. Except for the exit block. */
|
|
1352 if (single_pred_p (e->dest) && e->dest != EXIT_BLOCK_PTR)
|
|
1353 {
|
|
1354 bb = e->dest;
|
|
1355
|
|
1356 /* Get the location correct wrt a code label, and "nice" wrt
|
|
1357 a basic block note, and before everything else. */
|
|
1358 tmp = BB_HEAD (bb);
|
|
1359 if (LABEL_P (tmp))
|
|
1360 tmp = NEXT_INSN (tmp);
|
|
1361 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
|
|
1362 tmp = NEXT_INSN (tmp);
|
|
1363 if (tmp == BB_HEAD (bb))
|
|
1364 before = tmp;
|
|
1365 else if (tmp)
|
|
1366 after = PREV_INSN (tmp);
|
|
1367 else
|
|
1368 after = get_last_insn ();
|
|
1369 }
|
|
1370
|
|
1371 /* If the source has one successor and the edge is not abnormal,
|
|
1372 insert there. Except for the entry block. */
|
|
1373 else if ((e->flags & EDGE_ABNORMAL) == 0
|
|
1374 && single_succ_p (e->src)
|
|
1375 && e->src != ENTRY_BLOCK_PTR)
|
|
1376 {
|
|
1377 bb = e->src;
|
|
1378
|
|
1379 /* It is possible to have a non-simple jump here. Consider a target
|
|
1380 where some forms of unconditional jumps clobber a register. This
|
|
1381 happens on the fr30 for example.
|
|
1382
|
|
1383 We know this block has a single successor, so we can just emit
|
|
1384 the queued insns before the jump. */
|
|
1385 if (JUMP_P (BB_END (bb)))
|
|
1386 before = BB_END (bb);
|
|
1387 else
|
|
1388 {
|
|
1389 /* We'd better be fallthru, or we've lost track of
|
|
1390 what's what. */
|
|
1391 gcc_assert (e->flags & EDGE_FALLTHRU);
|
|
1392
|
|
1393 after = BB_END (bb);
|
|
1394 }
|
|
1395 }
|
|
1396 /* Otherwise we must split the edge. */
|
|
1397 else
|
|
1398 {
|
|
1399 bb = split_edge (e);
|
|
1400 after = BB_END (bb);
|
|
1401
|
|
1402 if (flag_reorder_blocks_and_partition
|
|
1403 && targetm.have_named_sections
|
|
1404 && e->src != ENTRY_BLOCK_PTR
|
|
1405 && BB_PARTITION (e->src) == BB_COLD_PARTITION
|
|
1406 && !(e->flags & EDGE_CROSSING))
|
|
1407 {
|
|
1408 rtx bb_note, cur_insn;
|
|
1409
|
|
1410 bb_note = NULL_RTX;
|
|
1411 for (cur_insn = BB_HEAD (bb); cur_insn != NEXT_INSN (BB_END (bb));
|
|
1412 cur_insn = NEXT_INSN (cur_insn))
|
|
1413 if (NOTE_INSN_BASIC_BLOCK_P (cur_insn))
|
|
1414 {
|
|
1415 bb_note = cur_insn;
|
|
1416 break;
|
|
1417 }
|
|
1418
|
|
1419 if (JUMP_P (BB_END (bb))
|
|
1420 && !any_condjump_p (BB_END (bb))
|
|
1421 && (single_succ_edge (bb)->flags & EDGE_CROSSING))
|
|
1422 add_reg_note (BB_END (bb), REG_CROSSING_JUMP, NULL_RTX);
|
|
1423 }
|
|
1424 }
|
|
1425 }
|
|
1426
|
|
1427 /* Now that we've found the spot, do the insertion. */
|
|
1428
|
|
1429 if (before)
|
|
1430 {
|
|
1431 emit_insn_before_noloc (insns, before, bb);
|
|
1432 last = prev_nonnote_insn (before);
|
|
1433 }
|
|
1434 else
|
|
1435 last = emit_insn_after_noloc (insns, after, bb);
|
|
1436
|
|
1437 if (returnjump_p (last))
|
|
1438 {
|
|
1439 /* ??? Remove all outgoing edges from BB and add one for EXIT.
|
|
1440 This is not currently a problem because this only happens
|
|
1441 for the (single) epilogue, which already has a fallthru edge
|
|
1442 to EXIT. */
|
|
1443
|
|
1444 e = single_succ_edge (bb);
|
|
1445 gcc_assert (e->dest == EXIT_BLOCK_PTR
|
|
1446 && single_succ_p (bb) && (e->flags & EDGE_FALLTHRU));
|
|
1447
|
|
1448 e->flags &= ~EDGE_FALLTHRU;
|
|
1449 emit_barrier_after (last);
|
|
1450
|
|
1451 if (before)
|
|
1452 delete_insn (before);
|
|
1453 }
|
|
1454 else
|
|
1455 gcc_assert (!JUMP_P (last));
|
|
1456
|
|
1457 /* Mark the basic block for find_many_sub_basic_blocks. */
|
|
1458 if (current_ir_type () != IR_RTL_CFGLAYOUT)
|
|
1459 bb->aux = &bb->aux;
|
|
1460 }
|
|
1461
|
|
1462 /* Update the CFG for all queued instructions. */
|
|
1463
|
|
1464 void
|
|
1465 commit_edge_insertions (void)
|
|
1466 {
|
|
1467 basic_block bb;
|
|
1468 sbitmap blocks;
|
|
1469 bool changed = false;
|
|
1470
|
|
1471 #ifdef ENABLE_CHECKING
|
|
1472 verify_flow_info ();
|
|
1473 #endif
|
|
1474
|
|
1475 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
|
|
1476 {
|
|
1477 edge e;
|
|
1478 edge_iterator ei;
|
|
1479
|
|
1480 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
1481 if (e->insns.r)
|
|
1482 {
|
|
1483 changed = true;
|
|
1484 commit_one_edge_insertion (e);
|
|
1485 }
|
|
1486 }
|
|
1487
|
|
1488 if (!changed)
|
|
1489 return;
|
|
1490
|
|
1491 /* In the old rtl CFG API, it was OK to insert control flow on an
|
|
1492 edge, apparently? In cfglayout mode, this will *not* work, and
|
|
1493 the caller is responsible for making sure that control flow is
|
|
1494 valid at all times. */
|
|
1495 if (current_ir_type () == IR_RTL_CFGLAYOUT)
|
|
1496 return;
|
|
1497
|
|
1498 blocks = sbitmap_alloc (last_basic_block);
|
|
1499 sbitmap_zero (blocks);
|
|
1500 FOR_EACH_BB (bb)
|
|
1501 if (bb->aux)
|
|
1502 {
|
|
1503 SET_BIT (blocks, bb->index);
|
|
1504 /* Check for forgotten bb->aux values before commit_edge_insertions
|
|
1505 call. */
|
|
1506 gcc_assert (bb->aux == &bb->aux);
|
|
1507 bb->aux = NULL;
|
|
1508 }
|
|
1509 find_many_sub_basic_blocks (blocks);
|
|
1510 sbitmap_free (blocks);
|
|
1511 }
|
|
1512
|
|
1513
|
|
1514 /* Print out RTL-specific basic block information (live information
|
|
1515 at start and end). */
|
|
1516
|
|
1517 static void
|
|
1518 rtl_dump_bb (basic_block bb, FILE *outf, int indent, int flags ATTRIBUTE_UNUSED)
|
|
1519 {
|
|
1520 rtx insn;
|
|
1521 rtx last;
|
|
1522 char *s_indent;
|
|
1523
|
|
1524 s_indent = (char *) alloca ((size_t) indent + 1);
|
|
1525 memset (s_indent, ' ', (size_t) indent);
|
|
1526 s_indent[indent] = '\0';
|
|
1527
|
|
1528 if (df)
|
|
1529 {
|
|
1530 df_dump_top (bb, outf);
|
|
1531 putc ('\n', outf);
|
|
1532 }
|
|
1533
|
|
1534 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); insn != last;
|
|
1535 insn = NEXT_INSN (insn))
|
|
1536 print_rtl_single (outf, insn);
|
|
1537
|
|
1538 if (df)
|
|
1539 {
|
|
1540 df_dump_bottom (bb, outf);
|
|
1541 putc ('\n', outf);
|
|
1542 }
|
|
1543
|
|
1544 }
|
|
1545
|
|
1546 /* Like print_rtl, but also print out live information for the start of each
|
|
1547 basic block. */
|
|
1548
|
|
1549 void
|
|
1550 print_rtl_with_bb (FILE *outf, const_rtx rtx_first)
|
|
1551 {
|
|
1552 const_rtx tmp_rtx;
|
|
1553 if (rtx_first == 0)
|
|
1554 fprintf (outf, "(nil)\n");
|
|
1555 else
|
|
1556 {
|
|
1557 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
|
|
1558 int max_uid = get_max_uid ();
|
|
1559 basic_block *start = XCNEWVEC (basic_block, max_uid);
|
|
1560 basic_block *end = XCNEWVEC (basic_block, max_uid);
|
|
1561 enum bb_state *in_bb_p = XCNEWVEC (enum bb_state, max_uid);
|
|
1562
|
|
1563 basic_block bb;
|
|
1564
|
|
1565 if (df)
|
|
1566 df_dump_start (outf);
|
|
1567
|
|
1568 FOR_EACH_BB_REVERSE (bb)
|
|
1569 {
|
|
1570 rtx x;
|
|
1571
|
|
1572 start[INSN_UID (BB_HEAD (bb))] = bb;
|
|
1573 end[INSN_UID (BB_END (bb))] = bb;
|
|
1574 for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x))
|
|
1575 {
|
|
1576 enum bb_state state = IN_MULTIPLE_BB;
|
|
1577
|
|
1578 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
|
|
1579 state = IN_ONE_BB;
|
|
1580 in_bb_p[INSN_UID (x)] = state;
|
|
1581
|
|
1582 if (x == BB_END (bb))
|
|
1583 break;
|
|
1584 }
|
|
1585 }
|
|
1586
|
|
1587 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
|
|
1588 {
|
|
1589 int did_output;
|
|
1590 if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
|
|
1591 {
|
|
1592 edge e;
|
|
1593 edge_iterator ei;
|
|
1594
|
|
1595 fprintf (outf, ";; Start of basic block (");
|
|
1596 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
1597 fprintf (outf, " %d", e->src->index);
|
|
1598 fprintf (outf, ") -> %d\n", bb->index);
|
|
1599
|
|
1600 if (df)
|
|
1601 {
|
|
1602 df_dump_top (bb, outf);
|
|
1603 putc ('\n', outf);
|
|
1604 }
|
|
1605 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
1606 {
|
|
1607 fputs (";; Pred edge ", outf);
|
|
1608 dump_edge_info (outf, e, 0);
|
|
1609 fputc ('\n', outf);
|
|
1610 }
|
|
1611 }
|
|
1612
|
|
1613 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
|
|
1614 && !NOTE_P (tmp_rtx)
|
|
1615 && !BARRIER_P (tmp_rtx))
|
|
1616 fprintf (outf, ";; Insn is not within a basic block\n");
|
|
1617 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
|
|
1618 fprintf (outf, ";; Insn is in multiple basic blocks\n");
|
|
1619
|
|
1620 did_output = print_rtl_single (outf, tmp_rtx);
|
|
1621
|
|
1622 if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
|
|
1623 {
|
|
1624 edge e;
|
|
1625 edge_iterator ei;
|
|
1626
|
|
1627 fprintf (outf, ";; End of basic block %d -> (", bb->index);
|
|
1628 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
1629 fprintf (outf, " %d", e->dest->index);
|
|
1630 fprintf (outf, ")\n");
|
|
1631
|
|
1632 if (df)
|
|
1633 {
|
|
1634 df_dump_bottom (bb, outf);
|
|
1635 putc ('\n', outf);
|
|
1636 }
|
|
1637 putc ('\n', outf);
|
|
1638 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
1639 {
|
|
1640 fputs (";; Succ edge ", outf);
|
|
1641 dump_edge_info (outf, e, 1);
|
|
1642 fputc ('\n', outf);
|
|
1643 }
|
|
1644 }
|
|
1645 if (did_output)
|
|
1646 putc ('\n', outf);
|
|
1647 }
|
|
1648
|
|
1649 free (start);
|
|
1650 free (end);
|
|
1651 free (in_bb_p);
|
|
1652 }
|
|
1653
|
|
1654 if (crtl->epilogue_delay_list != 0)
|
|
1655 {
|
|
1656 fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
|
|
1657 for (tmp_rtx = crtl->epilogue_delay_list; tmp_rtx != 0;
|
|
1658 tmp_rtx = XEXP (tmp_rtx, 1))
|
|
1659 print_rtl_single (outf, XEXP (tmp_rtx, 0));
|
|
1660 }
|
|
1661 }
|
|
1662
|
|
1663 void
|
|
1664 update_br_prob_note (basic_block bb)
|
|
1665 {
|
|
1666 rtx note;
|
|
1667 if (!JUMP_P (BB_END (bb)))
|
|
1668 return;
|
|
1669 note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
|
|
1670 if (!note || INTVAL (XEXP (note, 0)) == BRANCH_EDGE (bb)->probability)
|
|
1671 return;
|
|
1672 XEXP (note, 0) = GEN_INT (BRANCH_EDGE (bb)->probability);
|
|
1673 }
|
|
1674
|
|
1675 /* Get the last insn associated with block BB (that includes barriers and
|
|
1676 tablejumps after BB). */
|
|
1677 rtx
|
|
1678 get_last_bb_insn (basic_block bb)
|
|
1679 {
|
|
1680 rtx tmp;
|
|
1681 rtx end = BB_END (bb);
|
|
1682
|
|
1683 /* Include any jump table following the basic block. */
|
|
1684 if (tablejump_p (end, NULL, &tmp))
|
|
1685 end = tmp;
|
|
1686
|
|
1687 /* Include any barriers that may follow the basic block. */
|
|
1688 tmp = next_nonnote_insn (end);
|
|
1689 while (tmp && BARRIER_P (tmp))
|
|
1690 {
|
|
1691 end = tmp;
|
|
1692 tmp = next_nonnote_insn (end);
|
|
1693 }
|
|
1694
|
|
1695 return end;
|
|
1696 }
|
|
1697
|
|
1698 /* Verify the CFG and RTL consistency common for both underlying RTL and
|
|
1699 cfglayout RTL.
|
|
1700
|
|
1701 Currently it does following checks:
|
|
1702
|
|
1703 - overlapping of basic blocks
|
|
1704 - insns with wrong BLOCK_FOR_INSN pointers
|
|
1705 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
|
|
1706 - tails of basic blocks (ensure that boundary is necessary)
|
|
1707 - scans body of the basic block for JUMP_INSN, CODE_LABEL
|
|
1708 and NOTE_INSN_BASIC_BLOCK
|
|
1709 - verify that no fall_thru edge crosses hot/cold partition boundaries
|
|
1710 - verify that there are no pending RTL branch predictions
|
|
1711
|
|
1712 In future it can be extended check a lot of other stuff as well
|
|
1713 (reachability of basic blocks, life information, etc. etc.). */
|
|
1714
|
|
1715 static int
|
|
1716 rtl_verify_flow_info_1 (void)
|
|
1717 {
|
|
1718 rtx x;
|
|
1719 int err = 0;
|
|
1720 basic_block bb;
|
|
1721
|
|
1722 /* Check the general integrity of the basic blocks. */
|
|
1723 FOR_EACH_BB_REVERSE (bb)
|
|
1724 {
|
|
1725 rtx insn;
|
|
1726
|
|
1727 if (!(bb->flags & BB_RTL))
|
|
1728 {
|
|
1729 error ("BB_RTL flag not set for block %d", bb->index);
|
|
1730 err = 1;
|
|
1731 }
|
|
1732
|
|
1733 FOR_BB_INSNS (bb, insn)
|
|
1734 if (BLOCK_FOR_INSN (insn) != bb)
|
|
1735 {
|
|
1736 error ("insn %d basic block pointer is %d, should be %d",
|
|
1737 INSN_UID (insn),
|
|
1738 BLOCK_FOR_INSN (insn) ? BLOCK_FOR_INSN (insn)->index : 0,
|
|
1739 bb->index);
|
|
1740 err = 1;
|
|
1741 }
|
|
1742
|
|
1743 for (insn = bb->il.rtl->header; insn; insn = NEXT_INSN (insn))
|
|
1744 if (!BARRIER_P (insn)
|
|
1745 && BLOCK_FOR_INSN (insn) != NULL)
|
|
1746 {
|
|
1747 error ("insn %d in header of bb %d has non-NULL basic block",
|
|
1748 INSN_UID (insn), bb->index);
|
|
1749 err = 1;
|
|
1750 }
|
|
1751 for (insn = bb->il.rtl->footer; insn; insn = NEXT_INSN (insn))
|
|
1752 if (!BARRIER_P (insn)
|
|
1753 && BLOCK_FOR_INSN (insn) != NULL)
|
|
1754 {
|
|
1755 error ("insn %d in footer of bb %d has non-NULL basic block",
|
|
1756 INSN_UID (insn), bb->index);
|
|
1757 err = 1;
|
|
1758 }
|
|
1759 }
|
|
1760
|
|
1761 /* Now check the basic blocks (boundaries etc.) */
|
|
1762 FOR_EACH_BB_REVERSE (bb)
|
|
1763 {
|
|
1764 int n_fallthru = 0, n_eh = 0, n_call = 0, n_abnormal = 0, n_branch = 0;
|
|
1765 edge e, fallthru = NULL;
|
|
1766 rtx note;
|
|
1767 edge_iterator ei;
|
|
1768
|
|
1769 if (JUMP_P (BB_END (bb))
|
|
1770 && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX))
|
|
1771 && EDGE_COUNT (bb->succs) >= 2
|
|
1772 && any_condjump_p (BB_END (bb)))
|
|
1773 {
|
|
1774 if (INTVAL (XEXP (note, 0)) != BRANCH_EDGE (bb)->probability
|
|
1775 && profile_status != PROFILE_ABSENT)
|
|
1776 {
|
|
1777 error ("verify_flow_info: REG_BR_PROB does not match cfg %wi %i",
|
|
1778 INTVAL (XEXP (note, 0)), BRANCH_EDGE (bb)->probability);
|
|
1779 err = 1;
|
|
1780 }
|
|
1781 }
|
|
1782 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
1783 {
|
|
1784 if (e->flags & EDGE_FALLTHRU)
|
|
1785 {
|
|
1786 n_fallthru++, fallthru = e;
|
|
1787 if ((e->flags & EDGE_CROSSING)
|
|
1788 || (BB_PARTITION (e->src) != BB_PARTITION (e->dest)
|
|
1789 && e->src != ENTRY_BLOCK_PTR
|
|
1790 && e->dest != EXIT_BLOCK_PTR))
|
|
1791 {
|
|
1792 error ("fallthru edge crosses section boundary (bb %i)",
|
|
1793 e->src->index);
|
|
1794 err = 1;
|
|
1795 }
|
|
1796 }
|
|
1797
|
|
1798 if ((e->flags & ~(EDGE_DFS_BACK
|
|
1799 | EDGE_CAN_FALLTHRU
|
|
1800 | EDGE_IRREDUCIBLE_LOOP
|
|
1801 | EDGE_LOOP_EXIT
|
|
1802 | EDGE_CROSSING)) == 0)
|
|
1803 n_branch++;
|
|
1804
|
|
1805 if (e->flags & EDGE_ABNORMAL_CALL)
|
|
1806 n_call++;
|
|
1807
|
|
1808 if (e->flags & EDGE_EH)
|
|
1809 n_eh++;
|
|
1810 else if (e->flags & EDGE_ABNORMAL)
|
|
1811 n_abnormal++;
|
|
1812 }
|
|
1813
|
|
1814 if (n_eh && GET_CODE (PATTERN (BB_END (bb))) != RESX
|
|
1815 && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX))
|
|
1816 {
|
|
1817 error ("missing REG_EH_REGION note in the end of bb %i", bb->index);
|
|
1818 err = 1;
|
|
1819 }
|
|
1820 if (n_branch
|
|
1821 && (!JUMP_P (BB_END (bb))
|
|
1822 || (n_branch > 1 && (any_uncondjump_p (BB_END (bb))
|
|
1823 || any_condjump_p (BB_END (bb))))))
|
|
1824 {
|
|
1825 error ("too many outgoing branch edges from bb %i", bb->index);
|
|
1826 err = 1;
|
|
1827 }
|
|
1828 if (n_fallthru && any_uncondjump_p (BB_END (bb)))
|
|
1829 {
|
|
1830 error ("fallthru edge after unconditional jump %i", bb->index);
|
|
1831 err = 1;
|
|
1832 }
|
|
1833 if (n_branch != 1 && any_uncondjump_p (BB_END (bb)))
|
|
1834 {
|
|
1835 error ("wrong amount of branch edges after unconditional jump %i", bb->index);
|
|
1836 err = 1;
|
|
1837 }
|
|
1838 if (n_branch != 1 && any_condjump_p (BB_END (bb))
|
|
1839 && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest))
|
|
1840 {
|
|
1841 error ("wrong amount of branch edges after conditional jump %i",
|
|
1842 bb->index);
|
|
1843 err = 1;
|
|
1844 }
|
|
1845 if (n_call && !CALL_P (BB_END (bb)))
|
|
1846 {
|
|
1847 error ("call edges for non-call insn in bb %i", bb->index);
|
|
1848 err = 1;
|
|
1849 }
|
|
1850 if (n_abnormal
|
|
1851 && (!CALL_P (BB_END (bb)) && n_call != n_abnormal)
|
|
1852 && (!JUMP_P (BB_END (bb))
|
|
1853 || any_condjump_p (BB_END (bb))
|
|
1854 || any_uncondjump_p (BB_END (bb))))
|
|
1855 {
|
|
1856 error ("abnormal edges for no purpose in bb %i", bb->index);
|
|
1857 err = 1;
|
|
1858 }
|
|
1859
|
|
1860 for (x = BB_HEAD (bb); x != NEXT_INSN (BB_END (bb)); x = NEXT_INSN (x))
|
|
1861 /* We may have a barrier inside a basic block before dead code
|
|
1862 elimination. There is no BLOCK_FOR_INSN field in a barrier. */
|
|
1863 if (!BARRIER_P (x) && BLOCK_FOR_INSN (x) != bb)
|
|
1864 {
|
|
1865 debug_rtx (x);
|
|
1866 if (! BLOCK_FOR_INSN (x))
|
|
1867 error
|
|
1868 ("insn %d inside basic block %d but block_for_insn is NULL",
|
|
1869 INSN_UID (x), bb->index);
|
|
1870 else
|
|
1871 error
|
|
1872 ("insn %d inside basic block %d but block_for_insn is %i",
|
|
1873 INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index);
|
|
1874
|
|
1875 err = 1;
|
|
1876 }
|
|
1877
|
|
1878 /* OK pointers are correct. Now check the header of basic
|
|
1879 block. It ought to contain optional CODE_LABEL followed
|
|
1880 by NOTE_BASIC_BLOCK. */
|
|
1881 x = BB_HEAD (bb);
|
|
1882 if (LABEL_P (x))
|
|
1883 {
|
|
1884 if (BB_END (bb) == x)
|
|
1885 {
|
|
1886 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
|
|
1887 bb->index);
|
|
1888 err = 1;
|
|
1889 }
|
|
1890
|
|
1891 x = NEXT_INSN (x);
|
|
1892 }
|
|
1893
|
|
1894 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
|
|
1895 {
|
|
1896 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
|
|
1897 bb->index);
|
|
1898 err = 1;
|
|
1899 }
|
|
1900
|
|
1901 if (BB_END (bb) == x)
|
|
1902 /* Do checks for empty blocks here. */
|
|
1903 ;
|
|
1904 else
|
|
1905 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
|
|
1906 {
|
|
1907 if (NOTE_INSN_BASIC_BLOCK_P (x))
|
|
1908 {
|
|
1909 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
|
|
1910 INSN_UID (x), bb->index);
|
|
1911 err = 1;
|
|
1912 }
|
|
1913
|
|
1914 if (x == BB_END (bb))
|
|
1915 break;
|
|
1916
|
|
1917 if (control_flow_insn_p (x))
|
|
1918 {
|
|
1919 error ("in basic block %d:", bb->index);
|
|
1920 fatal_insn ("flow control insn inside a basic block", x);
|
|
1921 }
|
|
1922 }
|
|
1923 }
|
|
1924
|
|
1925 /* Clean up. */
|
|
1926 return err;
|
|
1927 }
|
|
1928
|
|
1929 /* Verify the CFG and RTL consistency common for both underlying RTL and
|
|
1930 cfglayout RTL.
|
|
1931
|
|
1932 Currently it does following checks:
|
|
1933 - all checks of rtl_verify_flow_info_1
|
|
1934 - test head/end pointers
|
|
1935 - check that all insns are in the basic blocks
|
|
1936 (except the switch handling code, barriers and notes)
|
|
1937 - check that all returns are followed by barriers
|
|
1938 - check that all fallthru edge points to the adjacent blocks. */
|
|
1939
|
|
1940 static int
|
|
1941 rtl_verify_flow_info (void)
|
|
1942 {
|
|
1943 basic_block bb;
|
|
1944 int err = rtl_verify_flow_info_1 ();
|
|
1945 rtx x;
|
|
1946 rtx last_head = get_last_insn ();
|
|
1947 basic_block *bb_info;
|
|
1948 int num_bb_notes;
|
|
1949 const rtx rtx_first = get_insns ();
|
|
1950 basic_block last_bb_seen = ENTRY_BLOCK_PTR, curr_bb = NULL;
|
|
1951 const int max_uid = get_max_uid ();
|
|
1952
|
|
1953 bb_info = XCNEWVEC (basic_block, max_uid);
|
|
1954
|
|
1955 FOR_EACH_BB_REVERSE (bb)
|
|
1956 {
|
|
1957 edge e;
|
|
1958 edge_iterator ei;
|
|
1959 rtx head = BB_HEAD (bb);
|
|
1960 rtx end = BB_END (bb);
|
|
1961
|
|
1962 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
|
|
1963 {
|
|
1964 /* Verify the end of the basic block is in the INSN chain. */
|
|
1965 if (x == end)
|
|
1966 break;
|
|
1967
|
|
1968 /* And that the code outside of basic blocks has NULL bb field. */
|
|
1969 if (!BARRIER_P (x)
|
|
1970 && BLOCK_FOR_INSN (x) != NULL)
|
|
1971 {
|
|
1972 error ("insn %d outside of basic blocks has non-NULL bb field",
|
|
1973 INSN_UID (x));
|
|
1974 err = 1;
|
|
1975 }
|
|
1976 }
|
|
1977
|
|
1978 if (!x)
|
|
1979 {
|
|
1980 error ("end insn %d for block %d not found in the insn stream",
|
|
1981 INSN_UID (end), bb->index);
|
|
1982 err = 1;
|
|
1983 }
|
|
1984
|
|
1985 /* Work backwards from the end to the head of the basic block
|
|
1986 to verify the head is in the RTL chain. */
|
|
1987 for (; x != NULL_RTX; x = PREV_INSN (x))
|
|
1988 {
|
|
1989 /* While walking over the insn chain, verify insns appear
|
|
1990 in only one basic block. */
|
|
1991 if (bb_info[INSN_UID (x)] != NULL)
|
|
1992 {
|
|
1993 error ("insn %d is in multiple basic blocks (%d and %d)",
|
|
1994 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
|
|
1995 err = 1;
|
|
1996 }
|
|
1997
|
|
1998 bb_info[INSN_UID (x)] = bb;
|
|
1999
|
|
2000 if (x == head)
|
|
2001 break;
|
|
2002 }
|
|
2003 if (!x)
|
|
2004 {
|
|
2005 error ("head insn %d for block %d not found in the insn stream",
|
|
2006 INSN_UID (head), bb->index);
|
|
2007 err = 1;
|
|
2008 }
|
|
2009
|
|
2010 last_head = PREV_INSN (x);
|
|
2011
|
|
2012 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
2013 if (e->flags & EDGE_FALLTHRU)
|
|
2014 break;
|
|
2015 if (!e)
|
|
2016 {
|
|
2017 rtx insn;
|
|
2018
|
|
2019 /* Ensure existence of barrier in BB with no fallthru edges. */
|
|
2020 for (insn = BB_END (bb); !insn || !BARRIER_P (insn);
|
|
2021 insn = NEXT_INSN (insn))
|
|
2022 if (!insn
|
|
2023 || NOTE_INSN_BASIC_BLOCK_P (insn))
|
|
2024 {
|
|
2025 error ("missing barrier after block %i", bb->index);
|
|
2026 err = 1;
|
|
2027 break;
|
|
2028 }
|
|
2029 }
|
|
2030 else if (e->src != ENTRY_BLOCK_PTR
|
|
2031 && e->dest != EXIT_BLOCK_PTR)
|
|
2032 {
|
|
2033 rtx insn;
|
|
2034
|
|
2035 if (e->src->next_bb != e->dest)
|
|
2036 {
|
|
2037 error
|
|
2038 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
|
|
2039 e->src->index, e->dest->index);
|
|
2040 err = 1;
|
|
2041 }
|
|
2042 else
|
|
2043 for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest);
|
|
2044 insn = NEXT_INSN (insn))
|
|
2045 if (BARRIER_P (insn) || INSN_P (insn))
|
|
2046 {
|
|
2047 error ("verify_flow_info: Incorrect fallthru %i->%i",
|
|
2048 e->src->index, e->dest->index);
|
|
2049 fatal_insn ("wrong insn in the fallthru edge", insn);
|
|
2050 err = 1;
|
|
2051 }
|
|
2052 }
|
|
2053 }
|
|
2054
|
|
2055 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
|
|
2056 {
|
|
2057 /* Check that the code before the first basic block has NULL
|
|
2058 bb field. */
|
|
2059 if (!BARRIER_P (x)
|
|
2060 && BLOCK_FOR_INSN (x) != NULL)
|
|
2061 {
|
|
2062 error ("insn %d outside of basic blocks has non-NULL bb field",
|
|
2063 INSN_UID (x));
|
|
2064 err = 1;
|
|
2065 }
|
|
2066 }
|
|
2067 free (bb_info);
|
|
2068
|
|
2069 num_bb_notes = 0;
|
|
2070 last_bb_seen = ENTRY_BLOCK_PTR;
|
|
2071
|
|
2072 for (x = rtx_first; x; x = NEXT_INSN (x))
|
|
2073 {
|
|
2074 if (NOTE_INSN_BASIC_BLOCK_P (x))
|
|
2075 {
|
|
2076 bb = NOTE_BASIC_BLOCK (x);
|
|
2077
|
|
2078 num_bb_notes++;
|
|
2079 if (bb != last_bb_seen->next_bb)
|
|
2080 internal_error ("basic blocks not laid down consecutively");
|
|
2081
|
|
2082 curr_bb = last_bb_seen = bb;
|
|
2083 }
|
|
2084
|
|
2085 if (!curr_bb)
|
|
2086 {
|
|
2087 switch (GET_CODE (x))
|
|
2088 {
|
|
2089 case BARRIER:
|
|
2090 case NOTE:
|
|
2091 break;
|
|
2092
|
|
2093 case CODE_LABEL:
|
|
2094 /* An addr_vec is placed outside any basic block. */
|
|
2095 if (NEXT_INSN (x)
|
|
2096 && JUMP_P (NEXT_INSN (x))
|
|
2097 && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
|
|
2098 || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
|
|
2099 x = NEXT_INSN (x);
|
|
2100
|
|
2101 /* But in any case, non-deletable labels can appear anywhere. */
|
|
2102 break;
|
|
2103
|
|
2104 default:
|
|
2105 fatal_insn ("insn outside basic block", x);
|
|
2106 }
|
|
2107 }
|
|
2108
|
|
2109 if (JUMP_P (x)
|
|
2110 && returnjump_p (x) && ! condjump_p (x)
|
|
2111 && ! (next_nonnote_insn (x) && BARRIER_P (next_nonnote_insn (x))))
|
|
2112 fatal_insn ("return not followed by barrier", x);
|
|
2113 if (curr_bb && x == BB_END (curr_bb))
|
|
2114 curr_bb = NULL;
|
|
2115 }
|
|
2116
|
|
2117 if (num_bb_notes != n_basic_blocks - NUM_FIXED_BLOCKS)
|
|
2118 internal_error
|
|
2119 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
|
|
2120 num_bb_notes, n_basic_blocks);
|
|
2121
|
|
2122 return err;
|
|
2123 }
|
|
2124
|
|
2125 /* Assume that the preceding pass has possibly eliminated jump instructions
|
|
2126 or converted the unconditional jumps. Eliminate the edges from CFG.
|
|
2127 Return true if any edges are eliminated. */
|
|
2128
|
|
2129 bool
|
|
2130 purge_dead_edges (basic_block bb)
|
|
2131 {
|
|
2132 edge e;
|
|
2133 rtx insn = BB_END (bb), note;
|
|
2134 bool purged = false;
|
|
2135 bool found;
|
|
2136 edge_iterator ei;
|
|
2137
|
|
2138 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
|
|
2139 if (NONJUMP_INSN_P (insn)
|
|
2140 && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
|
|
2141 {
|
|
2142 rtx eqnote;
|
|
2143
|
|
2144 if (! may_trap_p (PATTERN (insn))
|
|
2145 || ((eqnote = find_reg_equal_equiv_note (insn))
|
|
2146 && ! may_trap_p (XEXP (eqnote, 0))))
|
|
2147 remove_note (insn, note);
|
|
2148 }
|
|
2149
|
|
2150 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
|
|
2151 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
|
|
2152 {
|
|
2153 /* There are three types of edges we need to handle correctly here: EH
|
|
2154 edges, abnormal call EH edges, and abnormal call non-EH edges. The
|
|
2155 latter can appear when nonlocal gotos are used. */
|
|
2156 if (e->flags & EDGE_EH)
|
|
2157 {
|
|
2158 if (can_throw_internal (BB_END (bb))
|
|
2159 /* If this is a call edge, verify that this is a call insn. */
|
|
2160 && (! (e->flags & EDGE_ABNORMAL_CALL)
|
|
2161 || CALL_P (BB_END (bb))))
|
|
2162 {
|
|
2163 ei_next (&ei);
|
|
2164 continue;
|
|
2165 }
|
|
2166 }
|
|
2167 else if (e->flags & EDGE_ABNORMAL_CALL)
|
|
2168 {
|
|
2169 if (CALL_P (BB_END (bb))
|
|
2170 && (! (note = find_reg_note (insn, REG_EH_REGION, NULL))
|
|
2171 || INTVAL (XEXP (note, 0)) >= 0))
|
|
2172 {
|
|
2173 ei_next (&ei);
|
|
2174 continue;
|
|
2175 }
|
|
2176 }
|
|
2177 else
|
|
2178 {
|
|
2179 ei_next (&ei);
|
|
2180 continue;
|
|
2181 }
|
|
2182
|
|
2183 remove_edge (e);
|
|
2184 df_set_bb_dirty (bb);
|
|
2185 purged = true;
|
|
2186 }
|
|
2187
|
|
2188 if (JUMP_P (insn))
|
|
2189 {
|
|
2190 rtx note;
|
|
2191 edge b,f;
|
|
2192 edge_iterator ei;
|
|
2193
|
|
2194 /* We do care only about conditional jumps and simplejumps. */
|
|
2195 if (!any_condjump_p (insn)
|
|
2196 && !returnjump_p (insn)
|
|
2197 && !simplejump_p (insn))
|
|
2198 return purged;
|
|
2199
|
|
2200 /* Branch probability/prediction notes are defined only for
|
|
2201 condjumps. We've possibly turned condjump into simplejump. */
|
|
2202 if (simplejump_p (insn))
|
|
2203 {
|
|
2204 note = find_reg_note (insn, REG_BR_PROB, NULL);
|
|
2205 if (note)
|
|
2206 remove_note (insn, note);
|
|
2207 while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
|
|
2208 remove_note (insn, note);
|
|
2209 }
|
|
2210
|
|
2211 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
|
|
2212 {
|
|
2213 /* Avoid abnormal flags to leak from computed jumps turned
|
|
2214 into simplejumps. */
|
|
2215
|
|
2216 e->flags &= ~EDGE_ABNORMAL;
|
|
2217
|
|
2218 /* See if this edge is one we should keep. */
|
|
2219 if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
|
|
2220 /* A conditional jump can fall through into the next
|
|
2221 block, so we should keep the edge. */
|
|
2222 {
|
|
2223 ei_next (&ei);
|
|
2224 continue;
|
|
2225 }
|
|
2226 else if (e->dest != EXIT_BLOCK_PTR
|
|
2227 && BB_HEAD (e->dest) == JUMP_LABEL (insn))
|
|
2228 /* If the destination block is the target of the jump,
|
|
2229 keep the edge. */
|
|
2230 {
|
|
2231 ei_next (&ei);
|
|
2232 continue;
|
|
2233 }
|
|
2234 else if (e->dest == EXIT_BLOCK_PTR && returnjump_p (insn))
|
|
2235 /* If the destination block is the exit block, and this
|
|
2236 instruction is a return, then keep the edge. */
|
|
2237 {
|
|
2238 ei_next (&ei);
|
|
2239 continue;
|
|
2240 }
|
|
2241 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
|
|
2242 /* Keep the edges that correspond to exceptions thrown by
|
|
2243 this instruction and rematerialize the EDGE_ABNORMAL
|
|
2244 flag we just cleared above. */
|
|
2245 {
|
|
2246 e->flags |= EDGE_ABNORMAL;
|
|
2247 ei_next (&ei);
|
|
2248 continue;
|
|
2249 }
|
|
2250
|
|
2251 /* We do not need this edge. */
|
|
2252 df_set_bb_dirty (bb);
|
|
2253 purged = true;
|
|
2254 remove_edge (e);
|
|
2255 }
|
|
2256
|
|
2257 if (EDGE_COUNT (bb->succs) == 0 || !purged)
|
|
2258 return purged;
|
|
2259
|
|
2260 if (dump_file)
|
|
2261 fprintf (dump_file, "Purged edges from bb %i\n", bb->index);
|
|
2262
|
|
2263 if (!optimize)
|
|
2264 return purged;
|
|
2265
|
|
2266 /* Redistribute probabilities. */
|
|
2267 if (single_succ_p (bb))
|
|
2268 {
|
|
2269 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
|
|
2270 single_succ_edge (bb)->count = bb->count;
|
|
2271 }
|
|
2272 else
|
|
2273 {
|
|
2274 note = find_reg_note (insn, REG_BR_PROB, NULL);
|
|
2275 if (!note)
|
|
2276 return purged;
|
|
2277
|
|
2278 b = BRANCH_EDGE (bb);
|
|
2279 f = FALLTHRU_EDGE (bb);
|
|
2280 b->probability = INTVAL (XEXP (note, 0));
|
|
2281 f->probability = REG_BR_PROB_BASE - b->probability;
|
|
2282 b->count = bb->count * b->probability / REG_BR_PROB_BASE;
|
|
2283 f->count = bb->count * f->probability / REG_BR_PROB_BASE;
|
|
2284 }
|
|
2285
|
|
2286 return purged;
|
|
2287 }
|
|
2288 else if (CALL_P (insn) && SIBLING_CALL_P (insn))
|
|
2289 {
|
|
2290 /* First, there should not be any EH or ABCALL edges resulting
|
|
2291 from non-local gotos and the like. If there were, we shouldn't
|
|
2292 have created the sibcall in the first place. Second, there
|
|
2293 should of course never have been a fallthru edge. */
|
|
2294 gcc_assert (single_succ_p (bb));
|
|
2295 gcc_assert (single_succ_edge (bb)->flags
|
|
2296 == (EDGE_SIBCALL | EDGE_ABNORMAL));
|
|
2297
|
|
2298 return 0;
|
|
2299 }
|
|
2300
|
|
2301 /* If we don't see a jump insn, we don't know exactly why the block would
|
|
2302 have been broken at this point. Look for a simple, non-fallthru edge,
|
|
2303 as these are only created by conditional branches. If we find such an
|
|
2304 edge we know that there used to be a jump here and can then safely
|
|
2305 remove all non-fallthru edges. */
|
|
2306 found = false;
|
|
2307 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
2308 if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)))
|
|
2309 {
|
|
2310 found = true;
|
|
2311 break;
|
|
2312 }
|
|
2313
|
|
2314 if (!found)
|
|
2315 return purged;
|
|
2316
|
|
2317 /* Remove all but the fake and fallthru edges. The fake edge may be
|
|
2318 the only successor for this block in the case of noreturn
|
|
2319 calls. */
|
|
2320 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
|
|
2321 {
|
|
2322 if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE)))
|
|
2323 {
|
|
2324 df_set_bb_dirty (bb);
|
|
2325 remove_edge (e);
|
|
2326 purged = true;
|
|
2327 }
|
|
2328 else
|
|
2329 ei_next (&ei);
|
|
2330 }
|
|
2331
|
|
2332 gcc_assert (single_succ_p (bb));
|
|
2333
|
|
2334 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
|
|
2335 single_succ_edge (bb)->count = bb->count;
|
|
2336
|
|
2337 if (dump_file)
|
|
2338 fprintf (dump_file, "Purged non-fallthru edges from bb %i\n",
|
|
2339 bb->index);
|
|
2340 return purged;
|
|
2341 }
|
|
2342
|
|
2343 /* Search all basic blocks for potentially dead edges and purge them. Return
|
|
2344 true if some edge has been eliminated. */
|
|
2345
|
|
2346 bool
|
|
2347 purge_all_dead_edges (void)
|
|
2348 {
|
|
2349 int purged = false;
|
|
2350 basic_block bb;
|
|
2351
|
|
2352 FOR_EACH_BB (bb)
|
|
2353 {
|
|
2354 bool purged_here = purge_dead_edges (bb);
|
|
2355
|
|
2356 purged |= purged_here;
|
|
2357 }
|
|
2358
|
|
2359 return purged;
|
|
2360 }
|
|
2361
|
|
2362 /* Same as split_block but update cfg_layout structures. */
|
|
2363
|
|
2364 static basic_block
|
|
2365 cfg_layout_split_block (basic_block bb, void *insnp)
|
|
2366 {
|
|
2367 rtx insn = (rtx) insnp;
|
|
2368 basic_block new_bb = rtl_split_block (bb, insn);
|
|
2369
|
|
2370 new_bb->il.rtl->footer = bb->il.rtl->footer;
|
|
2371 bb->il.rtl->footer = NULL;
|
|
2372
|
|
2373 return new_bb;
|
|
2374 }
|
|
2375
|
|
2376 /* Redirect Edge to DEST. */
|
|
2377 static edge
|
|
2378 cfg_layout_redirect_edge_and_branch (edge e, basic_block dest)
|
|
2379 {
|
|
2380 basic_block src = e->src;
|
|
2381 edge ret;
|
|
2382
|
|
2383 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
|
|
2384 return NULL;
|
|
2385
|
|
2386 if (e->dest == dest)
|
|
2387 return e;
|
|
2388
|
|
2389 if (e->src != ENTRY_BLOCK_PTR
|
|
2390 && (ret = try_redirect_by_replacing_jump (e, dest, true)))
|
|
2391 {
|
|
2392 df_set_bb_dirty (src);
|
|
2393 return ret;
|
|
2394 }
|
|
2395
|
|
2396 if (e->src == ENTRY_BLOCK_PTR
|
|
2397 && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX))
|
|
2398 {
|
|
2399 if (dump_file)
|
|
2400 fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n",
|
|
2401 e->src->index, dest->index);
|
|
2402
|
|
2403 df_set_bb_dirty (e->src);
|
|
2404 redirect_edge_succ (e, dest);
|
|
2405 return e;
|
|
2406 }
|
|
2407
|
|
2408 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
|
|
2409 in the case the basic block appears to be in sequence. Avoid this
|
|
2410 transformation. */
|
|
2411
|
|
2412 if (e->flags & EDGE_FALLTHRU)
|
|
2413 {
|
|
2414 /* Redirect any branch edges unified with the fallthru one. */
|
|
2415 if (JUMP_P (BB_END (src))
|
|
2416 && label_is_jump_target_p (BB_HEAD (e->dest),
|
|
2417 BB_END (src)))
|
|
2418 {
|
|
2419 edge redirected;
|
|
2420
|
|
2421 if (dump_file)
|
|
2422 fprintf (dump_file, "Fallthru edge unified with branch "
|
|
2423 "%i->%i redirected to %i\n",
|
|
2424 e->src->index, e->dest->index, dest->index);
|
|
2425 e->flags &= ~EDGE_FALLTHRU;
|
|
2426 redirected = redirect_branch_edge (e, dest);
|
|
2427 gcc_assert (redirected);
|
|
2428 e->flags |= EDGE_FALLTHRU;
|
|
2429 df_set_bb_dirty (e->src);
|
|
2430 return e;
|
|
2431 }
|
|
2432 /* In case we are redirecting fallthru edge to the branch edge
|
|
2433 of conditional jump, remove it. */
|
|
2434 if (EDGE_COUNT (src->succs) == 2)
|
|
2435 {
|
|
2436 /* Find the edge that is different from E. */
|
|
2437 edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
|
|
2438
|
|
2439 if (s->dest == dest
|
|
2440 && any_condjump_p (BB_END (src))
|
|
2441 && onlyjump_p (BB_END (src)))
|
|
2442 delete_insn (BB_END (src));
|
|
2443 }
|
|
2444 ret = redirect_edge_succ_nodup (e, dest);
|
|
2445 if (dump_file)
|
|
2446 fprintf (dump_file, "Fallthru edge %i->%i redirected to %i\n",
|
|
2447 e->src->index, e->dest->index, dest->index);
|
|
2448 }
|
|
2449 else
|
|
2450 ret = redirect_branch_edge (e, dest);
|
|
2451
|
|
2452 /* We don't want simplejumps in the insn stream during cfglayout. */
|
|
2453 gcc_assert (!simplejump_p (BB_END (src)));
|
|
2454
|
|
2455 df_set_bb_dirty (src);
|
|
2456 return ret;
|
|
2457 }
|
|
2458
|
|
2459 /* Simple wrapper as we always can redirect fallthru edges. */
|
|
2460 static basic_block
|
|
2461 cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest)
|
|
2462 {
|
|
2463 edge redirected = cfg_layout_redirect_edge_and_branch (e, dest);
|
|
2464
|
|
2465 gcc_assert (redirected);
|
|
2466 return NULL;
|
|
2467 }
|
|
2468
|
|
2469 /* Same as delete_basic_block but update cfg_layout structures. */
|
|
2470
|
|
2471 static void
|
|
2472 cfg_layout_delete_block (basic_block bb)
|
|
2473 {
|
|
2474 rtx insn, next, prev = PREV_INSN (BB_HEAD (bb)), *to, remaints;
|
|
2475
|
|
2476 if (bb->il.rtl->header)
|
|
2477 {
|
|
2478 next = BB_HEAD (bb);
|
|
2479 if (prev)
|
|
2480 NEXT_INSN (prev) = bb->il.rtl->header;
|
|
2481 else
|
|
2482 set_first_insn (bb->il.rtl->header);
|
|
2483 PREV_INSN (bb->il.rtl->header) = prev;
|
|
2484 insn = bb->il.rtl->header;
|
|
2485 while (NEXT_INSN (insn))
|
|
2486 insn = NEXT_INSN (insn);
|
|
2487 NEXT_INSN (insn) = next;
|
|
2488 PREV_INSN (next) = insn;
|
|
2489 }
|
|
2490 next = NEXT_INSN (BB_END (bb));
|
|
2491 if (bb->il.rtl->footer)
|
|
2492 {
|
|
2493 insn = bb->il.rtl->footer;
|
|
2494 while (insn)
|
|
2495 {
|
|
2496 if (BARRIER_P (insn))
|
|
2497 {
|
|
2498 if (PREV_INSN (insn))
|
|
2499 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
|
|
2500 else
|
|
2501 bb->il.rtl->footer = NEXT_INSN (insn);
|
|
2502 if (NEXT_INSN (insn))
|
|
2503 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
|
|
2504 }
|
|
2505 if (LABEL_P (insn))
|
|
2506 break;
|
|
2507 insn = NEXT_INSN (insn);
|
|
2508 }
|
|
2509 if (bb->il.rtl->footer)
|
|
2510 {
|
|
2511 insn = BB_END (bb);
|
|
2512 NEXT_INSN (insn) = bb->il.rtl->footer;
|
|
2513 PREV_INSN (bb->il.rtl->footer) = insn;
|
|
2514 while (NEXT_INSN (insn))
|
|
2515 insn = NEXT_INSN (insn);
|
|
2516 NEXT_INSN (insn) = next;
|
|
2517 if (next)
|
|
2518 PREV_INSN (next) = insn;
|
|
2519 else
|
|
2520 set_last_insn (insn);
|
|
2521 }
|
|
2522 }
|
|
2523 if (bb->next_bb != EXIT_BLOCK_PTR)
|
|
2524 to = &bb->next_bb->il.rtl->header;
|
|
2525 else
|
|
2526 to = &cfg_layout_function_footer;
|
|
2527
|
|
2528 rtl_delete_block (bb);
|
|
2529
|
|
2530 if (prev)
|
|
2531 prev = NEXT_INSN (prev);
|
|
2532 else
|
|
2533 prev = get_insns ();
|
|
2534 if (next)
|
|
2535 next = PREV_INSN (next);
|
|
2536 else
|
|
2537 next = get_last_insn ();
|
|
2538
|
|
2539 if (next && NEXT_INSN (next) != prev)
|
|
2540 {
|
|
2541 remaints = unlink_insn_chain (prev, next);
|
|
2542 insn = remaints;
|
|
2543 while (NEXT_INSN (insn))
|
|
2544 insn = NEXT_INSN (insn);
|
|
2545 NEXT_INSN (insn) = *to;
|
|
2546 if (*to)
|
|
2547 PREV_INSN (*to) = insn;
|
|
2548 *to = remaints;
|
|
2549 }
|
|
2550 }
|
|
2551
|
|
2552 /* Return true when blocks A and B can be safely merged. */
|
|
2553
|
|
2554 static bool
|
|
2555 cfg_layout_can_merge_blocks_p (basic_block a, basic_block b)
|
|
2556 {
|
|
2557 /* If we are partitioning hot/cold basic blocks, we don't want to
|
|
2558 mess up unconditional or indirect jumps that cross between hot
|
|
2559 and cold sections.
|
|
2560
|
|
2561 Basic block partitioning may result in some jumps that appear to
|
|
2562 be optimizable (or blocks that appear to be mergeable), but which really
|
|
2563 must be left untouched (they are required to make it safely across
|
|
2564 partition boundaries). See the comments at the top of
|
|
2565 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
|
|
2566
|
|
2567 if (BB_PARTITION (a) != BB_PARTITION (b))
|
|
2568 return false;
|
|
2569
|
|
2570 /* There must be exactly one edge in between the blocks. */
|
|
2571 return (single_succ_p (a)
|
|
2572 && single_succ (a) == b
|
|
2573 && single_pred_p (b) == 1
|
|
2574 && a != b
|
|
2575 /* Must be simple edge. */
|
|
2576 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
|
|
2577 && a != ENTRY_BLOCK_PTR && b != EXIT_BLOCK_PTR
|
|
2578 /* If the jump insn has side effects, we can't kill the edge.
|
|
2579 When not optimizing, try_redirect_by_replacing_jump will
|
|
2580 not allow us to redirect an edge by replacing a table jump. */
|
|
2581 && (!JUMP_P (BB_END (a))
|
|
2582 || ((!optimize || reload_completed)
|
|
2583 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
|
|
2584 }
|
|
2585
|
|
2586 /* Merge block A and B. The blocks must be mergeable. */
|
|
2587
|
|
2588 static void
|
|
2589 cfg_layout_merge_blocks (basic_block a, basic_block b)
|
|
2590 {
|
|
2591 #ifdef ENABLE_CHECKING
|
|
2592 gcc_assert (cfg_layout_can_merge_blocks_p (a, b));
|
|
2593 #endif
|
|
2594
|
|
2595 if (dump_file)
|
|
2596 fprintf (dump_file, "merging block %d into block %d\n", b->index, a->index);
|
|
2597
|
|
2598 /* If there was a CODE_LABEL beginning B, delete it. */
|
|
2599 if (LABEL_P (BB_HEAD (b)))
|
|
2600 {
|
|
2601 /* This might have been an EH label that no longer has incoming
|
|
2602 EH edges. Update data structures to match. */
|
|
2603 maybe_remove_eh_handler (BB_HEAD (b));
|
|
2604
|
|
2605 delete_insn (BB_HEAD (b));
|
|
2606 }
|
|
2607
|
|
2608 /* We should have fallthru edge in a, or we can do dummy redirection to get
|
|
2609 it cleaned up. */
|
|
2610 if (JUMP_P (BB_END (a)))
|
|
2611 try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true);
|
|
2612 gcc_assert (!JUMP_P (BB_END (a)));
|
|
2613
|
|
2614 /* When not optimizing and the edge is the only place in RTL which holds
|
|
2615 some unique locus, emit a nop with that locus in between. */
|
|
2616 if (!optimize && EDGE_SUCC (a, 0)->goto_locus)
|
|
2617 {
|
|
2618 rtx insn = BB_END (a), end = PREV_INSN (BB_HEAD (a));
|
|
2619 int goto_locus = EDGE_SUCC (a, 0)->goto_locus;
|
|
2620
|
|
2621 while (insn != end && (!INSN_P (insn) || INSN_LOCATOR (insn) == 0))
|
|
2622 insn = PREV_INSN (insn);
|
|
2623 if (insn != end && locator_eq (INSN_LOCATOR (insn), goto_locus))
|
|
2624 goto_locus = 0;
|
|
2625 else
|
|
2626 {
|
|
2627 insn = BB_HEAD (b);
|
|
2628 end = NEXT_INSN (BB_END (b));
|
|
2629 while (insn != end && !INSN_P (insn))
|
|
2630 insn = NEXT_INSN (insn);
|
|
2631 if (insn != end && INSN_LOCATOR (insn) != 0
|
|
2632 && locator_eq (INSN_LOCATOR (insn), goto_locus))
|
|
2633 goto_locus = 0;
|
|
2634 }
|
|
2635 if (goto_locus)
|
|
2636 {
|
|
2637 BB_END (a) = emit_insn_after_noloc (gen_nop (), BB_END (a), a);
|
|
2638 INSN_LOCATOR (BB_END (a)) = goto_locus;
|
|
2639 }
|
|
2640 }
|
|
2641
|
|
2642 /* Possible line number notes should appear in between. */
|
|
2643 if (b->il.rtl->header)
|
|
2644 {
|
|
2645 rtx first = BB_END (a), last;
|
|
2646
|
|
2647 last = emit_insn_after_noloc (b->il.rtl->header, BB_END (a), a);
|
|
2648 delete_insn_chain (NEXT_INSN (first), last, false);
|
|
2649 b->il.rtl->header = NULL;
|
|
2650 }
|
|
2651
|
|
2652 /* In the case basic blocks are not adjacent, move them around. */
|
|
2653 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
|
|
2654 {
|
|
2655 rtx first = unlink_insn_chain (BB_HEAD (b), BB_END (b));
|
|
2656
|
|
2657 emit_insn_after_noloc (first, BB_END (a), a);
|
|
2658 /* Skip possible DELETED_LABEL insn. */
|
|
2659 if (!NOTE_INSN_BASIC_BLOCK_P (first))
|
|
2660 first = NEXT_INSN (first);
|
|
2661 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (first));
|
|
2662 BB_HEAD (b) = NULL;
|
|
2663
|
|
2664 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
|
|
2665 We need to explicitly call. */
|
|
2666 update_bb_for_insn_chain (NEXT_INSN (first),
|
|
2667 BB_END (b),
|
|
2668 a);
|
|
2669
|
|
2670 delete_insn (first);
|
|
2671 }
|
|
2672 /* Otherwise just re-associate the instructions. */
|
|
2673 else
|
|
2674 {
|
|
2675 rtx insn;
|
|
2676
|
|
2677 update_bb_for_insn_chain (BB_HEAD (b), BB_END (b), a);
|
|
2678
|
|
2679 insn = BB_HEAD (b);
|
|
2680 /* Skip possible DELETED_LABEL insn. */
|
|
2681 if (!NOTE_INSN_BASIC_BLOCK_P (insn))
|
|
2682 insn = NEXT_INSN (insn);
|
|
2683 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
|
|
2684 BB_HEAD (b) = NULL;
|
|
2685 BB_END (a) = BB_END (b);
|
|
2686 delete_insn (insn);
|
|
2687 }
|
|
2688
|
|
2689 df_bb_delete (b->index);
|
|
2690
|
|
2691 /* Possible tablejumps and barriers should appear after the block. */
|
|
2692 if (b->il.rtl->footer)
|
|
2693 {
|
|
2694 if (!a->il.rtl->footer)
|
|
2695 a->il.rtl->footer = b->il.rtl->footer;
|
|
2696 else
|
|
2697 {
|
|
2698 rtx last = a->il.rtl->footer;
|
|
2699
|
|
2700 while (NEXT_INSN (last))
|
|
2701 last = NEXT_INSN (last);
|
|
2702 NEXT_INSN (last) = b->il.rtl->footer;
|
|
2703 PREV_INSN (b->il.rtl->footer) = last;
|
|
2704 }
|
|
2705 b->il.rtl->footer = NULL;
|
|
2706 }
|
|
2707
|
|
2708 if (dump_file)
|
|
2709 fprintf (dump_file, "Merged blocks %d and %d.\n",
|
|
2710 a->index, b->index);
|
|
2711 }
|
|
2712
|
|
2713 /* Split edge E. */
|
|
2714
|
|
2715 static basic_block
|
|
2716 cfg_layout_split_edge (edge e)
|
|
2717 {
|
|
2718 basic_block new_bb =
|
|
2719 create_basic_block (e->src != ENTRY_BLOCK_PTR
|
|
2720 ? NEXT_INSN (BB_END (e->src)) : get_insns (),
|
|
2721 NULL_RTX, e->src);
|
|
2722
|
|
2723 if (e->dest == EXIT_BLOCK_PTR)
|
|
2724 BB_COPY_PARTITION (new_bb, e->src);
|
|
2725 else
|
|
2726 BB_COPY_PARTITION (new_bb, e->dest);
|
|
2727 make_edge (new_bb, e->dest, EDGE_FALLTHRU);
|
|
2728 redirect_edge_and_branch_force (e, new_bb);
|
|
2729
|
|
2730 return new_bb;
|
|
2731 }
|
|
2732
|
|
2733 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
|
|
2734
|
|
2735 static void
|
|
2736 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED)
|
|
2737 {
|
|
2738 }
|
|
2739
|
|
2740 /* Return 1 if BB ends with a call, possibly followed by some
|
|
2741 instructions that must stay with the call, 0 otherwise. */
|
|
2742
|
|
2743 static bool
|
|
2744 rtl_block_ends_with_call_p (basic_block bb)
|
|
2745 {
|
|
2746 rtx insn = BB_END (bb);
|
|
2747
|
|
2748 while (!CALL_P (insn)
|
|
2749 && insn != BB_HEAD (bb)
|
|
2750 && (keep_with_call_p (insn)
|
|
2751 || NOTE_P (insn)))
|
|
2752 insn = PREV_INSN (insn);
|
|
2753 return (CALL_P (insn));
|
|
2754 }
|
|
2755
|
|
2756 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
|
|
2757
|
|
2758 static bool
|
|
2759 rtl_block_ends_with_condjump_p (const_basic_block bb)
|
|
2760 {
|
|
2761 return any_condjump_p (BB_END (bb));
|
|
2762 }
|
|
2763
|
|
2764 /* Return true if we need to add fake edge to exit.
|
|
2765 Helper function for rtl_flow_call_edges_add. */
|
|
2766
|
|
2767 static bool
|
|
2768 need_fake_edge_p (const_rtx insn)
|
|
2769 {
|
|
2770 if (!INSN_P (insn))
|
|
2771 return false;
|
|
2772
|
|
2773 if ((CALL_P (insn)
|
|
2774 && !SIBLING_CALL_P (insn)
|
|
2775 && !find_reg_note (insn, REG_NORETURN, NULL)
|
|
2776 && !(RTL_CONST_OR_PURE_CALL_P (insn))))
|
|
2777 return true;
|
|
2778
|
|
2779 return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
|
|
2780 && MEM_VOLATILE_P (PATTERN (insn)))
|
|
2781 || (GET_CODE (PATTERN (insn)) == PARALLEL
|
|
2782 && asm_noperands (insn) != -1
|
|
2783 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
|
|
2784 || GET_CODE (PATTERN (insn)) == ASM_INPUT);
|
|
2785 }
|
|
2786
|
|
2787 /* Add fake edges to the function exit for any non constant and non noreturn
|
|
2788 calls, volatile inline assembly in the bitmap of blocks specified by
|
|
2789 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
|
|
2790 that were split.
|
|
2791
|
|
2792 The goal is to expose cases in which entering a basic block does not imply
|
|
2793 that all subsequent instructions must be executed. */
|
|
2794
|
|
2795 static int
|
|
2796 rtl_flow_call_edges_add (sbitmap blocks)
|
|
2797 {
|
|
2798 int i;
|
|
2799 int blocks_split = 0;
|
|
2800 int last_bb = last_basic_block;
|
|
2801 bool check_last_block = false;
|
|
2802
|
|
2803 if (n_basic_blocks == NUM_FIXED_BLOCKS)
|
|
2804 return 0;
|
|
2805
|
|
2806 if (! blocks)
|
|
2807 check_last_block = true;
|
|
2808 else
|
|
2809 check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
|
|
2810
|
|
2811 /* In the last basic block, before epilogue generation, there will be
|
|
2812 a fallthru edge to EXIT. Special care is required if the last insn
|
|
2813 of the last basic block is a call because make_edge folds duplicate
|
|
2814 edges, which would result in the fallthru edge also being marked
|
|
2815 fake, which would result in the fallthru edge being removed by
|
|
2816 remove_fake_edges, which would result in an invalid CFG.
|
|
2817
|
|
2818 Moreover, we can't elide the outgoing fake edge, since the block
|
|
2819 profiler needs to take this into account in order to solve the minimal
|
|
2820 spanning tree in the case that the call doesn't return.
|
|
2821
|
|
2822 Handle this by adding a dummy instruction in a new last basic block. */
|
|
2823 if (check_last_block)
|
|
2824 {
|
|
2825 basic_block bb = EXIT_BLOCK_PTR->prev_bb;
|
|
2826 rtx insn = BB_END (bb);
|
|
2827
|
|
2828 /* Back up past insns that must be kept in the same block as a call. */
|
|
2829 while (insn != BB_HEAD (bb)
|
|
2830 && keep_with_call_p (insn))
|
|
2831 insn = PREV_INSN (insn);
|
|
2832
|
|
2833 if (need_fake_edge_p (insn))
|
|
2834 {
|
|
2835 edge e;
|
|
2836
|
|
2837 e = find_edge (bb, EXIT_BLOCK_PTR);
|
|
2838 if (e)
|
|
2839 {
|
|
2840 insert_insn_on_edge (gen_use (const0_rtx), e);
|
|
2841 commit_edge_insertions ();
|
|
2842 }
|
|
2843 }
|
|
2844 }
|
|
2845
|
|
2846 /* Now add fake edges to the function exit for any non constant
|
|
2847 calls since there is no way that we can determine if they will
|
|
2848 return or not... */
|
|
2849
|
|
2850 for (i = NUM_FIXED_BLOCKS; i < last_bb; i++)
|
|
2851 {
|
|
2852 basic_block bb = BASIC_BLOCK (i);
|
|
2853 rtx insn;
|
|
2854 rtx prev_insn;
|
|
2855
|
|
2856 if (!bb)
|
|
2857 continue;
|
|
2858
|
|
2859 if (blocks && !TEST_BIT (blocks, i))
|
|
2860 continue;
|
|
2861
|
|
2862 for (insn = BB_END (bb); ; insn = prev_insn)
|
|
2863 {
|
|
2864 prev_insn = PREV_INSN (insn);
|
|
2865 if (need_fake_edge_p (insn))
|
|
2866 {
|
|
2867 edge e;
|
|
2868 rtx split_at_insn = insn;
|
|
2869
|
|
2870 /* Don't split the block between a call and an insn that should
|
|
2871 remain in the same block as the call. */
|
|
2872 if (CALL_P (insn))
|
|
2873 while (split_at_insn != BB_END (bb)
|
|
2874 && keep_with_call_p (NEXT_INSN (split_at_insn)))
|
|
2875 split_at_insn = NEXT_INSN (split_at_insn);
|
|
2876
|
|
2877 /* The handling above of the final block before the epilogue
|
|
2878 should be enough to verify that there is no edge to the exit
|
|
2879 block in CFG already. Calling make_edge in such case would
|
|
2880 cause us to mark that edge as fake and remove it later. */
|
|
2881
|
|
2882 #ifdef ENABLE_CHECKING
|
|
2883 if (split_at_insn == BB_END (bb))
|
|
2884 {
|
|
2885 e = find_edge (bb, EXIT_BLOCK_PTR);
|
|
2886 gcc_assert (e == NULL);
|
|
2887 }
|
|
2888 #endif
|
|
2889
|
|
2890 /* Note that the following may create a new basic block
|
|
2891 and renumber the existing basic blocks. */
|
|
2892 if (split_at_insn != BB_END (bb))
|
|
2893 {
|
|
2894 e = split_block (bb, split_at_insn);
|
|
2895 if (e)
|
|
2896 blocks_split++;
|
|
2897 }
|
|
2898
|
|
2899 make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
|
|
2900 }
|
|
2901
|
|
2902 if (insn == BB_HEAD (bb))
|
|
2903 break;
|
|
2904 }
|
|
2905 }
|
|
2906
|
|
2907 if (blocks_split)
|
|
2908 verify_flow_info ();
|
|
2909
|
|
2910 return blocks_split;
|
|
2911 }
|
|
2912
|
|
2913 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
|
|
2914 the conditional branch target, SECOND_HEAD should be the fall-thru
|
|
2915 there is no need to handle this here the loop versioning code handles
|
|
2916 this. the reason for SECON_HEAD is that it is needed for condition
|
|
2917 in trees, and this should be of the same type since it is a hook. */
|
|
2918 static void
|
|
2919 rtl_lv_add_condition_to_bb (basic_block first_head ,
|
|
2920 basic_block second_head ATTRIBUTE_UNUSED,
|
|
2921 basic_block cond_bb, void *comp_rtx)
|
|
2922 {
|
|
2923 rtx label, seq, jump;
|
|
2924 rtx op0 = XEXP ((rtx)comp_rtx, 0);
|
|
2925 rtx op1 = XEXP ((rtx)comp_rtx, 1);
|
|
2926 enum rtx_code comp = GET_CODE ((rtx)comp_rtx);
|
|
2927 enum machine_mode mode;
|
|
2928
|
|
2929
|
|
2930 label = block_label (first_head);
|
|
2931 mode = GET_MODE (op0);
|
|
2932 if (mode == VOIDmode)
|
|
2933 mode = GET_MODE (op1);
|
|
2934
|
|
2935 start_sequence ();
|
|
2936 op0 = force_operand (op0, NULL_RTX);
|
|
2937 op1 = force_operand (op1, NULL_RTX);
|
|
2938 do_compare_rtx_and_jump (op0, op1, comp, 0,
|
|
2939 mode, NULL_RTX, NULL_RTX, label);
|
|
2940 jump = get_last_insn ();
|
|
2941 JUMP_LABEL (jump) = label;
|
|
2942 LABEL_NUSES (label)++;
|
|
2943 seq = get_insns ();
|
|
2944 end_sequence ();
|
|
2945
|
|
2946 /* Add the new cond , in the new head. */
|
|
2947 emit_insn_after(seq, BB_END(cond_bb));
|
|
2948 }
|
|
2949
|
|
2950
|
|
2951 /* Given a block B with unconditional branch at its end, get the
|
|
2952 store the return the branch edge and the fall-thru edge in
|
|
2953 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
|
|
2954 static void
|
|
2955 rtl_extract_cond_bb_edges (basic_block b, edge *branch_edge,
|
|
2956 edge *fallthru_edge)
|
|
2957 {
|
|
2958 edge e = EDGE_SUCC (b, 0);
|
|
2959
|
|
2960 if (e->flags & EDGE_FALLTHRU)
|
|
2961 {
|
|
2962 *fallthru_edge = e;
|
|
2963 *branch_edge = EDGE_SUCC (b, 1);
|
|
2964 }
|
|
2965 else
|
|
2966 {
|
|
2967 *branch_edge = e;
|
|
2968 *fallthru_edge = EDGE_SUCC (b, 1);
|
|
2969 }
|
|
2970 }
|
|
2971
|
|
2972 void
|
|
2973 init_rtl_bb_info (basic_block bb)
|
|
2974 {
|
|
2975 gcc_assert (!bb->il.rtl);
|
|
2976 bb->il.rtl = GGC_CNEW (struct rtl_bb_info);
|
|
2977 }
|
|
2978
|
|
2979
|
|
2980 /* Add EXPR to the end of basic block BB. */
|
|
2981
|
|
2982 rtx
|
|
2983 insert_insn_end_bb_new (rtx pat, basic_block bb)
|
|
2984 {
|
|
2985 rtx insn = BB_END (bb);
|
|
2986 rtx new_insn;
|
|
2987 rtx pat_end = pat;
|
|
2988
|
|
2989 while (NEXT_INSN (pat_end) != NULL_RTX)
|
|
2990 pat_end = NEXT_INSN (pat_end);
|
|
2991
|
|
2992 /* If the last insn is a jump, insert EXPR in front [taking care to
|
|
2993 handle cc0, etc. properly]. Similarly we need to care trapping
|
|
2994 instructions in presence of non-call exceptions. */
|
|
2995
|
|
2996 if (JUMP_P (insn)
|
|
2997 || (NONJUMP_INSN_P (insn)
|
|
2998 && (!single_succ_p (bb)
|
|
2999 || single_succ_edge (bb)->flags & EDGE_ABNORMAL)))
|
|
3000 {
|
|
3001 #ifdef HAVE_cc0
|
|
3002 rtx note;
|
|
3003 #endif
|
|
3004 /* If this is a jump table, then we can't insert stuff here. Since
|
|
3005 we know the previous real insn must be the tablejump, we insert
|
|
3006 the new instruction just before the tablejump. */
|
|
3007 if (GET_CODE (PATTERN (insn)) == ADDR_VEC
|
|
3008 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
|
|
3009 insn = prev_real_insn (insn);
|
|
3010
|
|
3011 #ifdef HAVE_cc0
|
|
3012 /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts
|
|
3013 if cc0 isn't set. */
|
|
3014 note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
|
|
3015 if (note)
|
|
3016 insn = XEXP (note, 0);
|
|
3017 else
|
|
3018 {
|
|
3019 rtx maybe_cc0_setter = prev_nonnote_insn (insn);
|
|
3020 if (maybe_cc0_setter
|
|
3021 && INSN_P (maybe_cc0_setter)
|
|
3022 && sets_cc0_p (PATTERN (maybe_cc0_setter)))
|
|
3023 insn = maybe_cc0_setter;
|
|
3024 }
|
|
3025 #endif
|
|
3026 /* FIXME: What if something in cc0/jump uses value set in new
|
|
3027 insn? */
|
|
3028 new_insn = emit_insn_before_noloc (pat, insn, bb);
|
|
3029 }
|
|
3030
|
|
3031 /* Likewise if the last insn is a call, as will happen in the presence
|
|
3032 of exception handling. */
|
|
3033 else if (CALL_P (insn)
|
|
3034 && (!single_succ_p (bb)
|
|
3035 || single_succ_edge (bb)->flags & EDGE_ABNORMAL))
|
|
3036 {
|
|
3037 /* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers,
|
|
3038 we search backward and place the instructions before the first
|
|
3039 parameter is loaded. Do this for everyone for consistency and a
|
|
3040 presumption that we'll get better code elsewhere as well. */
|
|
3041
|
|
3042 /* Since different machines initialize their parameter registers
|
|
3043 in different orders, assume nothing. Collect the set of all
|
|
3044 parameter registers. */
|
|
3045 insn = find_first_parameter_load (insn, BB_HEAD (bb));
|
|
3046
|
|
3047 /* If we found all the parameter loads, then we want to insert
|
|
3048 before the first parameter load.
|
|
3049
|
|
3050 If we did not find all the parameter loads, then we might have
|
|
3051 stopped on the head of the block, which could be a CODE_LABEL.
|
|
3052 If we inserted before the CODE_LABEL, then we would be putting
|
|
3053 the insn in the wrong basic block. In that case, put the insn
|
|
3054 after the CODE_LABEL. Also, respect NOTE_INSN_BASIC_BLOCK. */
|
|
3055 while (LABEL_P (insn)
|
|
3056 || NOTE_INSN_BASIC_BLOCK_P (insn))
|
|
3057 insn = NEXT_INSN (insn);
|
|
3058
|
|
3059 new_insn = emit_insn_before_noloc (pat, insn, bb);
|
|
3060 }
|
|
3061 else
|
|
3062 new_insn = emit_insn_after_noloc (pat, insn, bb);
|
|
3063
|
|
3064 return new_insn;
|
|
3065 }
|
|
3066
|
|
3067 /* Returns true if it is possible to remove edge E by redirecting
|
|
3068 it to the destination of the other edge from E->src. */
|
|
3069
|
|
3070 static bool
|
|
3071 rtl_can_remove_branch_p (const_edge e)
|
|
3072 {
|
|
3073 const_basic_block src = e->src;
|
|
3074 const_basic_block target = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest;
|
|
3075 const_rtx insn = BB_END (src), set;
|
|
3076
|
|
3077 /* The conditions are taken from try_redirect_by_replacing_jump. */
|
|
3078 if (target == EXIT_BLOCK_PTR)
|
|
3079 return false;
|
|
3080
|
|
3081 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
|
|
3082 return false;
|
|
3083
|
|
3084 if (find_reg_note (insn, REG_CROSSING_JUMP, NULL_RTX)
|
|
3085 || BB_PARTITION (src) != BB_PARTITION (target))
|
|
3086 return false;
|
|
3087
|
|
3088 if (!onlyjump_p (insn)
|
|
3089 || tablejump_p (insn, NULL, NULL))
|
|
3090 return false;
|
|
3091
|
|
3092 set = single_set (insn);
|
|
3093 if (!set || side_effects_p (set))
|
|
3094 return false;
|
|
3095
|
|
3096 return true;
|
|
3097 }
|
|
3098
|
|
3099 /* Implementation of CFG manipulation for linearized RTL. */
|
|
3100 struct cfg_hooks rtl_cfg_hooks = {
|
|
3101 "rtl",
|
|
3102 rtl_verify_flow_info,
|
|
3103 rtl_dump_bb,
|
|
3104 rtl_create_basic_block,
|
|
3105 rtl_redirect_edge_and_branch,
|
|
3106 rtl_redirect_edge_and_branch_force,
|
|
3107 rtl_can_remove_branch_p,
|
|
3108 rtl_delete_block,
|
|
3109 rtl_split_block,
|
|
3110 rtl_move_block_after,
|
|
3111 rtl_can_merge_blocks, /* can_merge_blocks_p */
|
|
3112 rtl_merge_blocks,
|
|
3113 rtl_predict_edge,
|
|
3114 rtl_predicted_by_p,
|
|
3115 NULL, /* can_duplicate_block_p */
|
|
3116 NULL, /* duplicate_block */
|
|
3117 rtl_split_edge,
|
|
3118 rtl_make_forwarder_block,
|
|
3119 rtl_tidy_fallthru_edge,
|
|
3120 rtl_block_ends_with_call_p,
|
|
3121 rtl_block_ends_with_condjump_p,
|
|
3122 rtl_flow_call_edges_add,
|
|
3123 NULL, /* execute_on_growing_pred */
|
|
3124 NULL, /* execute_on_shrinking_pred */
|
|
3125 NULL, /* duplicate loop for trees */
|
|
3126 NULL, /* lv_add_condition_to_bb */
|
|
3127 NULL, /* lv_adjust_loop_header_phi*/
|
|
3128 NULL, /* extract_cond_bb_edges */
|
|
3129 NULL /* flush_pending_stmts */
|
|
3130 };
|
|
3131
|
|
3132 /* Implementation of CFG manipulation for cfg layout RTL, where
|
|
3133 basic block connected via fallthru edges does not have to be adjacent.
|
|
3134 This representation will hopefully become the default one in future
|
|
3135 version of the compiler. */
|
|
3136
|
|
3137 /* We do not want to declare these functions in a header file, since they
|
|
3138 should only be used through the cfghooks interface, and we do not want to
|
|
3139 move them here since it would require also moving quite a lot of related
|
|
3140 code. They are in cfglayout.c. */
|
|
3141 extern bool cfg_layout_can_duplicate_bb_p (const_basic_block);
|
|
3142 extern basic_block cfg_layout_duplicate_bb (basic_block);
|
|
3143
|
|
3144 struct cfg_hooks cfg_layout_rtl_cfg_hooks = {
|
|
3145 "cfglayout mode",
|
|
3146 rtl_verify_flow_info_1,
|
|
3147 rtl_dump_bb,
|
|
3148 cfg_layout_create_basic_block,
|
|
3149 cfg_layout_redirect_edge_and_branch,
|
|
3150 cfg_layout_redirect_edge_and_branch_force,
|
|
3151 rtl_can_remove_branch_p,
|
|
3152 cfg_layout_delete_block,
|
|
3153 cfg_layout_split_block,
|
|
3154 rtl_move_block_after,
|
|
3155 cfg_layout_can_merge_blocks_p,
|
|
3156 cfg_layout_merge_blocks,
|
|
3157 rtl_predict_edge,
|
|
3158 rtl_predicted_by_p,
|
|
3159 cfg_layout_can_duplicate_bb_p,
|
|
3160 cfg_layout_duplicate_bb,
|
|
3161 cfg_layout_split_edge,
|
|
3162 rtl_make_forwarder_block,
|
|
3163 NULL,
|
|
3164 rtl_block_ends_with_call_p,
|
|
3165 rtl_block_ends_with_condjump_p,
|
|
3166 rtl_flow_call_edges_add,
|
|
3167 NULL, /* execute_on_growing_pred */
|
|
3168 NULL, /* execute_on_shrinking_pred */
|
|
3169 duplicate_loop_to_header_edge, /* duplicate loop for trees */
|
|
3170 rtl_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
|
|
3171 NULL, /* lv_adjust_loop_header_phi*/
|
|
3172 rtl_extract_cond_bb_edges, /* extract_cond_bb_edges */
|
|
3173 NULL /* flush_pending_stmts */
|
|
3174 };
|