1c87b03e5Sespie /* Control flow graph manipulation code for GNU compiler.
2c87b03e5Sespie Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3c87b03e5Sespie 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
4c87b03e5Sespie
5c87b03e5Sespie This file is part of GCC.
6c87b03e5Sespie
7c87b03e5Sespie GCC is free software; you can redistribute it and/or modify it under
8c87b03e5Sespie the terms of the GNU General Public License as published by the Free
9c87b03e5Sespie Software Foundation; either version 2, or (at your option) any later
10c87b03e5Sespie version.
11c87b03e5Sespie
12c87b03e5Sespie GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13c87b03e5Sespie WARRANTY; without even the implied warranty of MERCHANTABILITY or
14c87b03e5Sespie FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15c87b03e5Sespie for more details.
16c87b03e5Sespie
17c87b03e5Sespie You should have received a copy of the GNU General Public License
18c87b03e5Sespie along with GCC; see the file COPYING. If not, write to the Free
19c87b03e5Sespie Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20c87b03e5Sespie 02111-1307, USA. */
21c87b03e5Sespie
22c87b03e5Sespie /* This file contains low level functions to manipulate the CFG and analyze it
23c87b03e5Sespie that are aware of the RTL intermediate language.
24c87b03e5Sespie
25c87b03e5Sespie Available functionality:
26c87b03e5Sespie - CFG-aware instruction chain manipulation
27c87b03e5Sespie delete_insn, delete_insn_chain
28c87b03e5Sespie - Basic block manipulation
29c87b03e5Sespie create_basic_block, flow_delete_block, split_block,
30c87b03e5Sespie merge_blocks_nomove
31c87b03e5Sespie - Infrastructure to determine quickly basic block for insn
32c87b03e5Sespie compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
33c87b03e5Sespie - Edge redirection with updating and optimizing of insn chain
34c87b03e5Sespie block_label, redirect_edge_and_branch,
35c87b03e5Sespie redirect_edge_and_branch_force, tidy_fallthru_edge, force_nonfallthru
36c87b03e5Sespie - Edge splitting and commiting to edges
37c87b03e5Sespie split_edge, insert_insn_on_edge, commit_edge_insertions
38c87b03e5Sespie - Dumping and debugging
39c87b03e5Sespie print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
40c87b03e5Sespie - Consistency checking
41c87b03e5Sespie verify_flow_info
42c87b03e5Sespie - CFG updating after constant propagation
43c87b03e5Sespie purge_dead_edges, purge_all_dead_edges */
44c87b03e5Sespie
45c87b03e5Sespie #include "config.h"
46c87b03e5Sespie #include "system.h"
47c87b03e5Sespie #include "tree.h"
48c87b03e5Sespie #include "rtl.h"
49c87b03e5Sespie #include "hard-reg-set.h"
50c87b03e5Sespie #include "basic-block.h"
51c87b03e5Sespie #include "regs.h"
52c87b03e5Sespie #include "flags.h"
53c87b03e5Sespie #include "output.h"
54c87b03e5Sespie #include "function.h"
55c87b03e5Sespie #include "except.h"
56c87b03e5Sespie #include "toplev.h"
57c87b03e5Sespie #include "tm_p.h"
58c87b03e5Sespie #include "obstack.h"
59c87b03e5Sespie #include "insn-config.h"
60c87b03e5Sespie
61c87b03e5Sespie /* Stubs in case we don't have a return insn. */
62c87b03e5Sespie #ifndef HAVE_return
63c87b03e5Sespie #define HAVE_return 0
64c87b03e5Sespie #define gen_return() NULL_RTX
65c87b03e5Sespie #endif
66c87b03e5Sespie
67c87b03e5Sespie /* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */
68c87b03e5Sespie /* ??? Should probably be using LABEL_NUSES instead. It would take a
69c87b03e5Sespie bit of surgery to be able to use or co-opt the routines in jump. */
70c87b03e5Sespie rtx label_value_list;
71c87b03e5Sespie rtx tail_recursion_label_list;
72c87b03e5Sespie
73c87b03e5Sespie static int can_delete_note_p PARAMS ((rtx));
74c87b03e5Sespie static int can_delete_label_p PARAMS ((rtx));
75c87b03e5Sespie static void commit_one_edge_insertion PARAMS ((edge, int));
76c87b03e5Sespie static bool try_redirect_by_replacing_jump PARAMS ((edge, basic_block));
77c87b03e5Sespie static rtx last_loop_beg_note PARAMS ((rtx));
78c87b03e5Sespie static bool back_edge_of_syntactic_loop_p PARAMS ((basic_block, basic_block));
79c87b03e5Sespie static basic_block force_nonfallthru_and_redirect PARAMS ((edge, basic_block));
80c87b03e5Sespie
81c87b03e5Sespie /* Return true if NOTE is not one of the ones that must be kept paired,
82c87b03e5Sespie so that we may simply delete it. */
83c87b03e5Sespie
84c87b03e5Sespie static int
can_delete_note_p(note)85c87b03e5Sespie can_delete_note_p (note)
86c87b03e5Sespie rtx note;
87c87b03e5Sespie {
88c87b03e5Sespie return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED
89c87b03e5Sespie || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK
90c87b03e5Sespie || NOTE_LINE_NUMBER (note) == NOTE_INSN_PREDICTION);
91c87b03e5Sespie }
92c87b03e5Sespie
93c87b03e5Sespie /* True if a given label can be deleted. */
94c87b03e5Sespie
95c87b03e5Sespie static int
can_delete_label_p(label)96c87b03e5Sespie can_delete_label_p (label)
97c87b03e5Sespie rtx label;
98c87b03e5Sespie {
99c87b03e5Sespie return (!LABEL_PRESERVE_P (label)
100c87b03e5Sespie /* User declared labels must be preserved. */
101c87b03e5Sespie && LABEL_NAME (label) == 0
102c87b03e5Sespie && !in_expr_list_p (forced_labels, label)
103c87b03e5Sespie && !in_expr_list_p (label_value_list, label));
104c87b03e5Sespie }
105c87b03e5Sespie
106c87b03e5Sespie /* Delete INSN by patching it out. Return the next insn. */
107c87b03e5Sespie
108c87b03e5Sespie rtx
delete_insn(insn)109c87b03e5Sespie delete_insn (insn)
110c87b03e5Sespie rtx insn;
111c87b03e5Sespie {
112c87b03e5Sespie rtx next = NEXT_INSN (insn);
113c87b03e5Sespie rtx note;
114c87b03e5Sespie bool really_delete = true;
115c87b03e5Sespie
116c87b03e5Sespie if (GET_CODE (insn) == CODE_LABEL)
117c87b03e5Sespie {
118c87b03e5Sespie /* Some labels can't be directly removed from the INSN chain, as they
119c87b03e5Sespie might be references via variables, constant pool etc.
120c87b03e5Sespie Convert them to the special NOTE_INSN_DELETED_LABEL note. */
121c87b03e5Sespie if (! can_delete_label_p (insn))
122c87b03e5Sespie {
123c87b03e5Sespie const char *name = LABEL_NAME (insn);
124c87b03e5Sespie
125c87b03e5Sespie really_delete = false;
126c87b03e5Sespie PUT_CODE (insn, NOTE);
127c87b03e5Sespie NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL;
128c87b03e5Sespie NOTE_SOURCE_FILE (insn) = name;
129c87b03e5Sespie }
130c87b03e5Sespie
131c87b03e5Sespie remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
132c87b03e5Sespie }
133c87b03e5Sespie
134c87b03e5Sespie if (really_delete)
135c87b03e5Sespie {
136c87b03e5Sespie /* If this insn has already been deleted, something is very wrong. */
137c87b03e5Sespie if (INSN_DELETED_P (insn))
138c87b03e5Sespie abort ();
139c87b03e5Sespie remove_insn (insn);
140c87b03e5Sespie INSN_DELETED_P (insn) = 1;
141c87b03e5Sespie }
142c87b03e5Sespie
143c87b03e5Sespie /* If deleting a jump, decrement the use count of the label. Deleting
144c87b03e5Sespie the label itself should happen in the normal course of block merging. */
145c87b03e5Sespie if (GET_CODE (insn) == JUMP_INSN
146c87b03e5Sespie && JUMP_LABEL (insn)
147c87b03e5Sespie && GET_CODE (JUMP_LABEL (insn)) == CODE_LABEL)
148c87b03e5Sespie LABEL_NUSES (JUMP_LABEL (insn))--;
149c87b03e5Sespie
150c87b03e5Sespie /* Also if deleting an insn that references a label. */
151*4e43c760Sespie else
152*4e43c760Sespie {
153*4e43c760Sespie while ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX
154c87b03e5Sespie && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
155*4e43c760Sespie {
156c87b03e5Sespie LABEL_NUSES (XEXP (note, 0))--;
157*4e43c760Sespie remove_note (insn, note);
158*4e43c760Sespie }
159*4e43c760Sespie }
160c87b03e5Sespie
161c87b03e5Sespie if (GET_CODE (insn) == JUMP_INSN
162c87b03e5Sespie && (GET_CODE (PATTERN (insn)) == ADDR_VEC
163c87b03e5Sespie || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
164c87b03e5Sespie {
165c87b03e5Sespie rtx pat = PATTERN (insn);
166c87b03e5Sespie int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC;
167c87b03e5Sespie int len = XVECLEN (pat, diff_vec_p);
168c87b03e5Sespie int i;
169c87b03e5Sespie
170c87b03e5Sespie for (i = 0; i < len; i++)
171c87b03e5Sespie {
172c87b03e5Sespie rtx label = XEXP (XVECEXP (pat, diff_vec_p, i), 0);
173c87b03e5Sespie
174c87b03e5Sespie /* When deleting code in bulk (e.g. removing many unreachable
175c87b03e5Sespie blocks) we can delete a label that's a target of the vector
176c87b03e5Sespie before deleting the vector itself. */
177c87b03e5Sespie if (GET_CODE (label) != NOTE)
178c87b03e5Sespie LABEL_NUSES (label)--;
179c87b03e5Sespie }
180c87b03e5Sespie }
181c87b03e5Sespie
182c87b03e5Sespie return next;
183c87b03e5Sespie }
184c87b03e5Sespie
185c87b03e5Sespie /* Like delete_insn but also purge dead edges from BB. */
186c87b03e5Sespie rtx
delete_insn_and_edges(insn)187c87b03e5Sespie delete_insn_and_edges (insn)
188c87b03e5Sespie rtx insn;
189c87b03e5Sespie {
190c87b03e5Sespie rtx x;
191c87b03e5Sespie bool purge = false;
192c87b03e5Sespie
193c87b03e5Sespie if (INSN_P (insn)
194c87b03e5Sespie && BLOCK_FOR_INSN (insn)
195c87b03e5Sespie && BLOCK_FOR_INSN (insn)->end == insn)
196c87b03e5Sespie purge = true;
197c87b03e5Sespie x = delete_insn (insn);
198c87b03e5Sespie if (purge)
199c87b03e5Sespie purge_dead_edges (BLOCK_FOR_INSN (insn));
200c87b03e5Sespie return x;
201c87b03e5Sespie }
202c87b03e5Sespie
203c87b03e5Sespie /* Unlink a chain of insns between START and FINISH, leaving notes
204c87b03e5Sespie that must be paired. */
205c87b03e5Sespie
206c87b03e5Sespie void
delete_insn_chain(start,finish)207c87b03e5Sespie delete_insn_chain (start, finish)
208c87b03e5Sespie rtx start, finish;
209c87b03e5Sespie {
210c87b03e5Sespie rtx next;
211c87b03e5Sespie
212c87b03e5Sespie /* Unchain the insns one by one. It would be quicker to delete all of these
213c87b03e5Sespie with a single unchaining, rather than one at a time, but we need to keep
214c87b03e5Sespie the NOTE's. */
215c87b03e5Sespie while (1)
216c87b03e5Sespie {
217c87b03e5Sespie next = NEXT_INSN (start);
218c87b03e5Sespie if (GET_CODE (start) == NOTE && !can_delete_note_p (start))
219c87b03e5Sespie ;
220c87b03e5Sespie else
221c87b03e5Sespie next = delete_insn (start);
222c87b03e5Sespie
223c87b03e5Sespie if (start == finish)
224c87b03e5Sespie break;
225c87b03e5Sespie start = next;
226c87b03e5Sespie }
227c87b03e5Sespie }
228c87b03e5Sespie
229c87b03e5Sespie /* Like delete_insn but also purge dead edges from BB. */
230c87b03e5Sespie void
delete_insn_chain_and_edges(first,last)231c87b03e5Sespie delete_insn_chain_and_edges (first, last)
232c87b03e5Sespie rtx first, last;
233c87b03e5Sespie {
234c87b03e5Sespie bool purge = false;
235c87b03e5Sespie
236c87b03e5Sespie if (INSN_P (last)
237c87b03e5Sespie && BLOCK_FOR_INSN (last)
238c87b03e5Sespie && BLOCK_FOR_INSN (last)->end == last)
239c87b03e5Sespie purge = true;
240c87b03e5Sespie delete_insn_chain (first, last);
241c87b03e5Sespie if (purge)
242c87b03e5Sespie purge_dead_edges (BLOCK_FOR_INSN (last));
243c87b03e5Sespie }
244c87b03e5Sespie
245c87b03e5Sespie /* Create a new basic block consisting of the instructions between HEAD and END
246c87b03e5Sespie inclusive. This function is designed to allow fast BB construction - reuses
247c87b03e5Sespie the note and basic block struct in BB_NOTE, if any and do not grow
248c87b03e5Sespie BASIC_BLOCK chain and should be used directly only by CFG construction code.
249c87b03e5Sespie END can be NULL in to create new empty basic block before HEAD. Both END
250c87b03e5Sespie and HEAD can be NULL to create basic block at the end of INSN chain.
251c87b03e5Sespie AFTER is the basic block we should be put after. */
252c87b03e5Sespie
253c87b03e5Sespie basic_block
create_basic_block_structure(head,end,bb_note,after)254c87b03e5Sespie create_basic_block_structure (head, end, bb_note, after)
255c87b03e5Sespie rtx head, end, bb_note;
256c87b03e5Sespie basic_block after;
257c87b03e5Sespie {
258c87b03e5Sespie basic_block bb;
259c87b03e5Sespie
260c87b03e5Sespie if (bb_note
261c87b03e5Sespie && ! RTX_INTEGRATED_P (bb_note)
262c87b03e5Sespie && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
263c87b03e5Sespie && bb->aux == NULL)
264c87b03e5Sespie {
265c87b03e5Sespie /* If we found an existing note, thread it back onto the chain. */
266c87b03e5Sespie
267c87b03e5Sespie rtx after;
268c87b03e5Sespie
269c87b03e5Sespie if (GET_CODE (head) == CODE_LABEL)
270c87b03e5Sespie after = head;
271c87b03e5Sespie else
272c87b03e5Sespie {
273c87b03e5Sespie after = PREV_INSN (head);
274c87b03e5Sespie head = bb_note;
275c87b03e5Sespie }
276c87b03e5Sespie
277c87b03e5Sespie if (after != bb_note && NEXT_INSN (after) != bb_note)
278c87b03e5Sespie reorder_insns_nobb (bb_note, bb_note, after);
279c87b03e5Sespie }
280c87b03e5Sespie else
281c87b03e5Sespie {
282c87b03e5Sespie /* Otherwise we must create a note and a basic block structure. */
283c87b03e5Sespie
284c87b03e5Sespie bb = alloc_block ();
285c87b03e5Sespie
286c87b03e5Sespie if (!head && !end)
287c87b03e5Sespie head = end = bb_note
288c87b03e5Sespie = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
289c87b03e5Sespie else if (GET_CODE (head) == CODE_LABEL && end)
290c87b03e5Sespie {
291c87b03e5Sespie bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
292c87b03e5Sespie if (head == end)
293c87b03e5Sespie end = bb_note;
294c87b03e5Sespie }
295c87b03e5Sespie else
296c87b03e5Sespie {
297c87b03e5Sespie bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
298c87b03e5Sespie head = bb_note;
299c87b03e5Sespie if (!end)
300c87b03e5Sespie end = head;
301c87b03e5Sespie }
302c87b03e5Sespie
303c87b03e5Sespie NOTE_BASIC_BLOCK (bb_note) = bb;
304c87b03e5Sespie }
305c87b03e5Sespie
306c87b03e5Sespie /* Always include the bb note in the block. */
307c87b03e5Sespie if (NEXT_INSN (end) == bb_note)
308c87b03e5Sespie end = bb_note;
309c87b03e5Sespie
310c87b03e5Sespie bb->head = head;
311c87b03e5Sespie bb->end = end;
312c87b03e5Sespie bb->index = last_basic_block++;
313c87b03e5Sespie bb->flags = BB_NEW;
314c87b03e5Sespie link_block (bb, after);
315c87b03e5Sespie BASIC_BLOCK (bb->index) = bb;
316c87b03e5Sespie update_bb_for_insn (bb);
317c87b03e5Sespie
318c87b03e5Sespie /* Tag the block so that we know it has been used when considering
319c87b03e5Sespie other basic block notes. */
320c87b03e5Sespie bb->aux = bb;
321c87b03e5Sespie
322c87b03e5Sespie return bb;
323c87b03e5Sespie }
324c87b03e5Sespie
325c87b03e5Sespie /* Create new basic block consisting of instructions in between HEAD and END
326c87b03e5Sespie and place it to the BB chain after block AFTER. END can be NULL in to
327c87b03e5Sespie create new empty basic block before HEAD. Both END and HEAD can be NULL to
328c87b03e5Sespie create basic block at the end of INSN chain. */
329c87b03e5Sespie
330c87b03e5Sespie basic_block
create_basic_block(head,end,after)331c87b03e5Sespie create_basic_block (head, end, after)
332c87b03e5Sespie rtx head, end;
333c87b03e5Sespie basic_block after;
334c87b03e5Sespie {
335c87b03e5Sespie basic_block bb;
336c87b03e5Sespie
337c87b03e5Sespie /* Place the new block just after the end. */
338c87b03e5Sespie VARRAY_GROW (basic_block_info, last_basic_block+1);
339c87b03e5Sespie
340c87b03e5Sespie n_basic_blocks++;
341c87b03e5Sespie
342c87b03e5Sespie bb = create_basic_block_structure (head, end, NULL, after);
343c87b03e5Sespie bb->aux = NULL;
344c87b03e5Sespie return bb;
345c87b03e5Sespie }
346c87b03e5Sespie
347c87b03e5Sespie /* Delete the insns in a (non-live) block. We physically delete every
348c87b03e5Sespie non-deleted-note insn, and update the flow graph appropriately.
349c87b03e5Sespie
350c87b03e5Sespie Return nonzero if we deleted an exception handler. */
351c87b03e5Sespie
352c87b03e5Sespie /* ??? Preserving all such notes strikes me as wrong. It would be nice
353c87b03e5Sespie to post-process the stream to remove empty blocks, loops, ranges, etc. */
354c87b03e5Sespie
355c87b03e5Sespie int
flow_delete_block_noexpunge(b)356c87b03e5Sespie flow_delete_block_noexpunge (b)
357c87b03e5Sespie basic_block b;
358c87b03e5Sespie {
359c87b03e5Sespie int deleted_handler = 0;
360c87b03e5Sespie rtx insn, end, tmp;
361c87b03e5Sespie
362c87b03e5Sespie /* If the head of this block is a CODE_LABEL, then it might be the
363c87b03e5Sespie label for an exception handler which can't be reached.
364c87b03e5Sespie
365c87b03e5Sespie We need to remove the label from the exception_handler_label list
366c87b03e5Sespie and remove the associated NOTE_INSN_EH_REGION_BEG and
367c87b03e5Sespie NOTE_INSN_EH_REGION_END notes. */
368c87b03e5Sespie
369c87b03e5Sespie /* Get rid of all NOTE_INSN_PREDICTIONs and NOTE_INSN_LOOP_CONTs
370c87b03e5Sespie hanging before the block. */
371c87b03e5Sespie
372c87b03e5Sespie for (insn = PREV_INSN (b->head); insn; insn = PREV_INSN (insn))
373c87b03e5Sespie {
374c87b03e5Sespie if (GET_CODE (insn) != NOTE)
375c87b03e5Sespie break;
376c87b03e5Sespie if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_PREDICTION
377c87b03e5Sespie || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT)
378c87b03e5Sespie NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
379c87b03e5Sespie }
380c87b03e5Sespie
381c87b03e5Sespie insn = b->head;
382c87b03e5Sespie
383c87b03e5Sespie never_reached_warning (insn, b->end);
384c87b03e5Sespie
385c87b03e5Sespie if (GET_CODE (insn) == CODE_LABEL)
386c87b03e5Sespie maybe_remove_eh_handler (insn);
387c87b03e5Sespie
388c87b03e5Sespie /* Include any jump table following the basic block. */
389c87b03e5Sespie end = b->end;
390c87b03e5Sespie if (GET_CODE (end) == JUMP_INSN
391c87b03e5Sespie && (tmp = JUMP_LABEL (end)) != NULL_RTX
392c87b03e5Sespie && (tmp = NEXT_INSN (tmp)) != NULL_RTX
393c87b03e5Sespie && GET_CODE (tmp) == JUMP_INSN
394c87b03e5Sespie && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
395c87b03e5Sespie || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
396c87b03e5Sespie end = tmp;
397c87b03e5Sespie
398c87b03e5Sespie /* Include any barrier that may follow the basic block. */
399c87b03e5Sespie tmp = next_nonnote_insn (end);
400c87b03e5Sespie if (tmp && GET_CODE (tmp) == BARRIER)
401c87b03e5Sespie end = tmp;
402c87b03e5Sespie
403c87b03e5Sespie /* Selectively delete the entire chain. */
404c87b03e5Sespie b->head = NULL;
405c87b03e5Sespie delete_insn_chain (insn, end);
406c87b03e5Sespie
407c87b03e5Sespie /* Remove the edges into and out of this block. Note that there may
408c87b03e5Sespie indeed be edges in, if we are removing an unreachable loop. */
409c87b03e5Sespie while (b->pred != NULL)
410c87b03e5Sespie remove_edge (b->pred);
411c87b03e5Sespie while (b->succ != NULL)
412c87b03e5Sespie remove_edge (b->succ);
413c87b03e5Sespie
414c87b03e5Sespie b->pred = NULL;
415c87b03e5Sespie b->succ = NULL;
416c87b03e5Sespie
417c87b03e5Sespie return deleted_handler;
418c87b03e5Sespie }
419c87b03e5Sespie
420c87b03e5Sespie int
flow_delete_block(b)421c87b03e5Sespie flow_delete_block (b)
422c87b03e5Sespie basic_block b;
423c87b03e5Sespie {
424c87b03e5Sespie int deleted_handler = flow_delete_block_noexpunge (b);
425c87b03e5Sespie
426c87b03e5Sespie /* Remove the basic block from the array. */
427c87b03e5Sespie expunge_block (b);
428c87b03e5Sespie
429c87b03e5Sespie return deleted_handler;
430c87b03e5Sespie }
431c87b03e5Sespie
432c87b03e5Sespie /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
433c87b03e5Sespie
434c87b03e5Sespie void
compute_bb_for_insn()435c87b03e5Sespie compute_bb_for_insn ()
436c87b03e5Sespie {
437c87b03e5Sespie basic_block bb;
438c87b03e5Sespie
439c87b03e5Sespie FOR_EACH_BB (bb)
440c87b03e5Sespie {
441c87b03e5Sespie rtx end = bb->end;
442c87b03e5Sespie rtx insn;
443c87b03e5Sespie
444c87b03e5Sespie for (insn = bb->head; ; insn = NEXT_INSN (insn))
445c87b03e5Sespie {
446c87b03e5Sespie BLOCK_FOR_INSN (insn) = bb;
447c87b03e5Sespie if (insn == end)
448c87b03e5Sespie break;
449c87b03e5Sespie }
450c87b03e5Sespie }
451c87b03e5Sespie }
452c87b03e5Sespie
453c87b03e5Sespie /* Release the basic_block_for_insn array. */
454c87b03e5Sespie
455c87b03e5Sespie void
free_bb_for_insn()456c87b03e5Sespie free_bb_for_insn ()
457c87b03e5Sespie {
458c87b03e5Sespie rtx insn;
459c87b03e5Sespie for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
460c87b03e5Sespie if (GET_CODE (insn) != BARRIER)
461c87b03e5Sespie BLOCK_FOR_INSN (insn) = NULL;
462c87b03e5Sespie }
463c87b03e5Sespie
464c87b03e5Sespie /* Update insns block within BB. */
465c87b03e5Sespie
466c87b03e5Sespie void
update_bb_for_insn(bb)467c87b03e5Sespie update_bb_for_insn (bb)
468c87b03e5Sespie basic_block bb;
469c87b03e5Sespie {
470c87b03e5Sespie rtx insn;
471c87b03e5Sespie
472c87b03e5Sespie for (insn = bb->head; ; insn = NEXT_INSN (insn))
473c87b03e5Sespie {
474c87b03e5Sespie set_block_for_insn (insn, bb);
475c87b03e5Sespie if (insn == bb->end)
476c87b03e5Sespie break;
477c87b03e5Sespie }
478c87b03e5Sespie }
479c87b03e5Sespie
480c87b03e5Sespie /* Split a block BB after insn INSN creating a new fallthru edge.
481c87b03e5Sespie Return the new edge. Note that to keep other parts of the compiler happy,
482c87b03e5Sespie this function renumbers all the basic blocks so that the new
483c87b03e5Sespie one has a number one greater than the block split. */
484c87b03e5Sespie
485c87b03e5Sespie edge
split_block(bb,insn)486c87b03e5Sespie split_block (bb, insn)
487c87b03e5Sespie basic_block bb;
488c87b03e5Sespie rtx insn;
489c87b03e5Sespie {
490c87b03e5Sespie basic_block new_bb;
491c87b03e5Sespie edge new_edge;
492c87b03e5Sespie edge e;
493c87b03e5Sespie
494c87b03e5Sespie /* There is no point splitting the block after its end. */
495c87b03e5Sespie if (bb->end == insn)
496c87b03e5Sespie return 0;
497c87b03e5Sespie
498c87b03e5Sespie /* Create the new basic block. */
499c87b03e5Sespie new_bb = create_basic_block (NEXT_INSN (insn), bb->end, bb);
500c87b03e5Sespie new_bb->count = bb->count;
501c87b03e5Sespie new_bb->frequency = bb->frequency;
502c87b03e5Sespie new_bb->loop_depth = bb->loop_depth;
503c87b03e5Sespie bb->end = insn;
504c87b03e5Sespie
505c87b03e5Sespie /* Redirect the outgoing edges. */
506c87b03e5Sespie new_bb->succ = bb->succ;
507c87b03e5Sespie bb->succ = NULL;
508c87b03e5Sespie for (e = new_bb->succ; e; e = e->succ_next)
509c87b03e5Sespie e->src = new_bb;
510c87b03e5Sespie
511c87b03e5Sespie new_edge = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
512c87b03e5Sespie
513c87b03e5Sespie if (bb->global_live_at_start)
514c87b03e5Sespie {
515c87b03e5Sespie new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
516c87b03e5Sespie new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
517c87b03e5Sespie COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
518c87b03e5Sespie
519c87b03e5Sespie /* We now have to calculate which registers are live at the end
520c87b03e5Sespie of the split basic block and at the start of the new basic
521c87b03e5Sespie block. Start with those registers that are known to be live
522c87b03e5Sespie at the end of the original basic block and get
523c87b03e5Sespie propagate_block to determine which registers are live. */
524c87b03e5Sespie COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_end);
525c87b03e5Sespie propagate_block (new_bb, new_bb->global_live_at_start, NULL, NULL, 0);
526c87b03e5Sespie COPY_REG_SET (bb->global_live_at_end,
527c87b03e5Sespie new_bb->global_live_at_start);
528c87b03e5Sespie #ifdef HAVE_conditional_execution
529c87b03e5Sespie /* In the presence of conditional execution we are not able to update
530c87b03e5Sespie liveness precisely. */
531c87b03e5Sespie if (reload_completed)
532c87b03e5Sespie {
533c87b03e5Sespie bb->flags |= BB_DIRTY;
534c87b03e5Sespie new_bb->flags |= BB_DIRTY;
535c87b03e5Sespie }
536c87b03e5Sespie #endif
537c87b03e5Sespie }
538c87b03e5Sespie
539c87b03e5Sespie return new_edge;
540c87b03e5Sespie }
541c87b03e5Sespie
542c87b03e5Sespie /* Blocks A and B are to be merged into a single block A. The insns
543c87b03e5Sespie are already contiguous, hence `nomove'. */
544c87b03e5Sespie
545c87b03e5Sespie void
merge_blocks_nomove(a,b)546c87b03e5Sespie merge_blocks_nomove (a, b)
547c87b03e5Sespie basic_block a, b;
548c87b03e5Sespie {
549c87b03e5Sespie rtx b_head = b->head, b_end = b->end, a_end = a->end;
550c87b03e5Sespie rtx del_first = NULL_RTX, del_last = NULL_RTX;
551c87b03e5Sespie int b_empty = 0;
552c87b03e5Sespie edge e;
553c87b03e5Sespie
554c87b03e5Sespie /* If there was a CODE_LABEL beginning B, delete it. */
555c87b03e5Sespie if (GET_CODE (b_head) == CODE_LABEL)
556c87b03e5Sespie {
557c87b03e5Sespie /* Detect basic blocks with nothing but a label. This can happen
558c87b03e5Sespie in particular at the end of a function. */
559c87b03e5Sespie if (b_head == b_end)
560c87b03e5Sespie b_empty = 1;
561c87b03e5Sespie
562c87b03e5Sespie del_first = del_last = b_head;
563c87b03e5Sespie b_head = NEXT_INSN (b_head);
564c87b03e5Sespie }
565c87b03e5Sespie
566c87b03e5Sespie /* Delete the basic block note and handle blocks containing just that
567c87b03e5Sespie note. */
568c87b03e5Sespie if (NOTE_INSN_BASIC_BLOCK_P (b_head))
569c87b03e5Sespie {
570c87b03e5Sespie if (b_head == b_end)
571c87b03e5Sespie b_empty = 1;
572c87b03e5Sespie if (! del_last)
573c87b03e5Sespie del_first = b_head;
574c87b03e5Sespie
575c87b03e5Sespie del_last = b_head;
576c87b03e5Sespie b_head = NEXT_INSN (b_head);
577c87b03e5Sespie }
578c87b03e5Sespie
579c87b03e5Sespie /* If there was a jump out of A, delete it. */
580c87b03e5Sespie if (GET_CODE (a_end) == JUMP_INSN)
581c87b03e5Sespie {
582c87b03e5Sespie rtx prev;
583c87b03e5Sespie
584c87b03e5Sespie for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
585c87b03e5Sespie if (GET_CODE (prev) != NOTE
586c87b03e5Sespie || NOTE_LINE_NUMBER (prev) == NOTE_INSN_BASIC_BLOCK
587c87b03e5Sespie || prev == a->head)
588c87b03e5Sespie break;
589c87b03e5Sespie
590c87b03e5Sespie del_first = a_end;
591c87b03e5Sespie
592c87b03e5Sespie #ifdef HAVE_cc0
593c87b03e5Sespie /* If this was a conditional jump, we need to also delete
594c87b03e5Sespie the insn that set cc0. */
595c87b03e5Sespie if (only_sets_cc0_p (prev))
596c87b03e5Sespie {
597c87b03e5Sespie rtx tmp = prev;
598c87b03e5Sespie
599c87b03e5Sespie prev = prev_nonnote_insn (prev);
600c87b03e5Sespie if (!prev)
601c87b03e5Sespie prev = a->head;
602c87b03e5Sespie del_first = tmp;
603c87b03e5Sespie }
604c87b03e5Sespie #endif
605c87b03e5Sespie
606c87b03e5Sespie a_end = PREV_INSN (del_first);
607c87b03e5Sespie }
608c87b03e5Sespie else if (GET_CODE (NEXT_INSN (a_end)) == BARRIER)
609c87b03e5Sespie del_first = NEXT_INSN (a_end);
610c87b03e5Sespie
611c87b03e5Sespie /* Normally there should only be one successor of A and that is B, but
612c87b03e5Sespie partway though the merge of blocks for conditional_execution we'll
613c87b03e5Sespie be merging a TEST block with THEN and ELSE successors. Free the
614c87b03e5Sespie whole lot of them and hope the caller knows what they're doing. */
615c87b03e5Sespie while (a->succ)
616c87b03e5Sespie remove_edge (a->succ);
617c87b03e5Sespie
618c87b03e5Sespie /* Adjust the edges out of B for the new owner. */
619c87b03e5Sespie for (e = b->succ; e; e = e->succ_next)
620c87b03e5Sespie e->src = a;
621c87b03e5Sespie a->succ = b->succ;
622c87b03e5Sespie a->flags |= b->flags;
623c87b03e5Sespie
624c87b03e5Sespie /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
625c87b03e5Sespie b->pred = b->succ = NULL;
626c87b03e5Sespie a->global_live_at_end = b->global_live_at_end;
627c87b03e5Sespie
628c87b03e5Sespie expunge_block (b);
629c87b03e5Sespie
630c87b03e5Sespie /* Delete everything marked above as well as crap that might be
631c87b03e5Sespie hanging out between the two blocks. */
632c87b03e5Sespie delete_insn_chain (del_first, del_last);
633c87b03e5Sespie
634c87b03e5Sespie /* Reassociate the insns of B with A. */
635c87b03e5Sespie if (!b_empty)
636c87b03e5Sespie {
637c87b03e5Sespie rtx x;
638c87b03e5Sespie
639c87b03e5Sespie for (x = a_end; x != b_end; x = NEXT_INSN (x))
640c87b03e5Sespie set_block_for_insn (x, a);
641c87b03e5Sespie
642c87b03e5Sespie set_block_for_insn (b_end, a);
643c87b03e5Sespie
644c87b03e5Sespie a_end = b_end;
645c87b03e5Sespie }
646c87b03e5Sespie
647c87b03e5Sespie a->end = a_end;
648c87b03e5Sespie }
649c87b03e5Sespie
650c87b03e5Sespie /* Return the label in the head of basic block BLOCK. Create one if it doesn't
651c87b03e5Sespie exist. */
652c87b03e5Sespie
653c87b03e5Sespie rtx
block_label(block)654c87b03e5Sespie block_label (block)
655c87b03e5Sespie basic_block block;
656c87b03e5Sespie {
657c87b03e5Sespie if (block == EXIT_BLOCK_PTR)
658c87b03e5Sespie return NULL_RTX;
659c87b03e5Sespie
660c87b03e5Sespie if (GET_CODE (block->head) != CODE_LABEL)
661c87b03e5Sespie {
662c87b03e5Sespie block->head = emit_label_before (gen_label_rtx (), block->head);
663c87b03e5Sespie }
664c87b03e5Sespie
665c87b03e5Sespie return block->head;
666c87b03e5Sespie }
667c87b03e5Sespie
668c87b03e5Sespie /* Attempt to perform edge redirection by replacing possibly complex jump
669c87b03e5Sespie instruction by unconditional jump or removing jump completely. This can
670c87b03e5Sespie apply only if all edges now point to the same block. The parameters and
671c87b03e5Sespie return values are equivalent to redirect_edge_and_branch. */
672c87b03e5Sespie
673c87b03e5Sespie static bool
try_redirect_by_replacing_jump(e,target)674c87b03e5Sespie try_redirect_by_replacing_jump (e, target)
675c87b03e5Sespie edge e;
676c87b03e5Sespie basic_block target;
677c87b03e5Sespie {
678c87b03e5Sespie basic_block src = e->src;
679c87b03e5Sespie rtx insn = src->end, kill_from;
680c87b03e5Sespie edge tmp;
681c87b03e5Sespie rtx set, table;
682c87b03e5Sespie int fallthru = 0;
683c87b03e5Sespie
684c87b03e5Sespie /* Verify that all targets will be TARGET. */
685c87b03e5Sespie for (tmp = src->succ; tmp; tmp = tmp->succ_next)
686c87b03e5Sespie if (tmp->dest != target && tmp != e)
687c87b03e5Sespie break;
688c87b03e5Sespie
689c87b03e5Sespie if (tmp || !onlyjump_p (insn))
690c87b03e5Sespie return false;
691*4e43c760Sespie if (reload_completed && JUMP_LABEL (insn)
692c87b03e5Sespie && (table = NEXT_INSN (JUMP_LABEL (insn))) != NULL_RTX
693c87b03e5Sespie && GET_CODE (table) == JUMP_INSN
694c87b03e5Sespie && (GET_CODE (PATTERN (table)) == ADDR_VEC
695c87b03e5Sespie || GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC))
696c87b03e5Sespie return false;
697c87b03e5Sespie
698c87b03e5Sespie /* Avoid removing branch with side effects. */
699c87b03e5Sespie set = single_set (insn);
700c87b03e5Sespie if (!set || side_effects_p (set))
701c87b03e5Sespie return false;
702c87b03e5Sespie
703c87b03e5Sespie /* In case we zap a conditional jump, we'll need to kill
704c87b03e5Sespie the cc0 setter too. */
705c87b03e5Sespie kill_from = insn;
706c87b03e5Sespie #ifdef HAVE_cc0
707c87b03e5Sespie if (reg_mentioned_p (cc0_rtx, PATTERN (insn)))
708c87b03e5Sespie kill_from = PREV_INSN (insn);
709c87b03e5Sespie #endif
710c87b03e5Sespie
711c87b03e5Sespie /* See if we can create the fallthru edge. */
712c87b03e5Sespie if (can_fallthru (src, target))
713c87b03e5Sespie {
714c87b03e5Sespie if (rtl_dump_file)
715c87b03e5Sespie fprintf (rtl_dump_file, "Removing jump %i.\n", INSN_UID (insn));
716c87b03e5Sespie fallthru = 1;
717c87b03e5Sespie
718c87b03e5Sespie /* Selectively unlink whole insn chain. */
719c87b03e5Sespie delete_insn_chain (kill_from, PREV_INSN (target->head));
720c87b03e5Sespie }
721c87b03e5Sespie
722c87b03e5Sespie /* If this already is simplejump, redirect it. */
723c87b03e5Sespie else if (simplejump_p (insn))
724c87b03e5Sespie {
725c87b03e5Sespie if (e->dest == target)
726c87b03e5Sespie return false;
727c87b03e5Sespie if (rtl_dump_file)
728c87b03e5Sespie fprintf (rtl_dump_file, "Redirecting jump %i from %i to %i.\n",
729c87b03e5Sespie INSN_UID (insn), e->dest->index, target->index);
730c87b03e5Sespie if (!redirect_jump (insn, block_label (target), 0))
731c87b03e5Sespie {
732c87b03e5Sespie if (target == EXIT_BLOCK_PTR)
733c87b03e5Sespie return false;
734c87b03e5Sespie abort ();
735c87b03e5Sespie }
736c87b03e5Sespie }
737c87b03e5Sespie
738c87b03e5Sespie /* Cannot do anything for target exit block. */
739c87b03e5Sespie else if (target == EXIT_BLOCK_PTR)
740c87b03e5Sespie return false;
741c87b03e5Sespie
742c87b03e5Sespie /* Or replace possibly complicated jump insn by simple jump insn. */
743c87b03e5Sespie else
744c87b03e5Sespie {
745c87b03e5Sespie rtx target_label = block_label (target);
746c87b03e5Sespie rtx barrier, tmp;
747c87b03e5Sespie
748c87b03e5Sespie emit_jump_insn_after (gen_jump (target_label), insn);
749c87b03e5Sespie JUMP_LABEL (src->end) = target_label;
750c87b03e5Sespie LABEL_NUSES (target_label)++;
751c87b03e5Sespie if (rtl_dump_file)
752c87b03e5Sespie fprintf (rtl_dump_file, "Replacing insn %i by jump %i\n",
753c87b03e5Sespie INSN_UID (insn), INSN_UID (src->end));
754c87b03e5Sespie
755c87b03e5Sespie
756c87b03e5Sespie delete_insn_chain (kill_from, insn);
757c87b03e5Sespie
758c87b03e5Sespie /* Recognize a tablejump that we are converting to a
759c87b03e5Sespie simple jump and remove its associated CODE_LABEL
760c87b03e5Sespie and ADDR_VEC or ADDR_DIFF_VEC. */
761c87b03e5Sespie if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
762c87b03e5Sespie && (tmp = NEXT_INSN (tmp)) != NULL_RTX
763c87b03e5Sespie && GET_CODE (tmp) == JUMP_INSN
764c87b03e5Sespie && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
765c87b03e5Sespie || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
766c87b03e5Sespie {
767c87b03e5Sespie delete_insn_chain (JUMP_LABEL (insn), tmp);
768c87b03e5Sespie }
769c87b03e5Sespie
770c87b03e5Sespie barrier = next_nonnote_insn (src->end);
771c87b03e5Sespie if (!barrier || GET_CODE (barrier) != BARRIER)
772c87b03e5Sespie emit_barrier_after (src->end);
773*4e43c760Sespie else
774*4e43c760Sespie {
775*4e43c760Sespie if (barrier != NEXT_INSN (src->end))
776*4e43c760Sespie {
777*4e43c760Sespie /* Move the jump before barrier so that the notes
778*4e43c760Sespie which originally were or were created before jump table are
779*4e43c760Sespie inside the basic block. */
780*4e43c760Sespie rtx new_insn = src->end;
781*4e43c760Sespie rtx tmp;
782*4e43c760Sespie
783*4e43c760Sespie for (tmp = NEXT_INSN (src->end); tmp != barrier;
784*4e43c760Sespie tmp = NEXT_INSN (tmp))
785*4e43c760Sespie set_block_for_insn (tmp, src);
786*4e43c760Sespie
787*4e43c760Sespie NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn);
788*4e43c760Sespie PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn);
789*4e43c760Sespie
790*4e43c760Sespie NEXT_INSN (new_insn) = barrier;
791*4e43c760Sespie NEXT_INSN (PREV_INSN (barrier)) = new_insn;
792*4e43c760Sespie
793*4e43c760Sespie PREV_INSN (new_insn) = PREV_INSN (barrier);
794*4e43c760Sespie PREV_INSN (barrier) = new_insn;
795*4e43c760Sespie }
796*4e43c760Sespie }
797c87b03e5Sespie }
798c87b03e5Sespie
799c87b03e5Sespie /* Keep only one edge out and set proper flags. */
800c87b03e5Sespie while (src->succ->succ_next)
801c87b03e5Sespie remove_edge (src->succ);
802c87b03e5Sespie e = src->succ;
803c87b03e5Sespie if (fallthru)
804c87b03e5Sespie e->flags = EDGE_FALLTHRU;
805c87b03e5Sespie else
806c87b03e5Sespie e->flags = 0;
807c87b03e5Sespie
808c87b03e5Sespie e->probability = REG_BR_PROB_BASE;
809c87b03e5Sespie e->count = src->count;
810c87b03e5Sespie
811c87b03e5Sespie /* We don't want a block to end on a line-number note since that has
812c87b03e5Sespie the potential of changing the code between -g and not -g. */
813c87b03e5Sespie while (GET_CODE (e->src->end) == NOTE
814c87b03e5Sespie && NOTE_LINE_NUMBER (e->src->end) >= 0)
815c87b03e5Sespie delete_insn (e->src->end);
816c87b03e5Sespie
817c87b03e5Sespie if (e->dest != target)
818c87b03e5Sespie redirect_edge_succ (e, target);
819c87b03e5Sespie
820c87b03e5Sespie return true;
821c87b03e5Sespie }
822c87b03e5Sespie
823c87b03e5Sespie /* Return last loop_beg note appearing after INSN, before start of next
824c87b03e5Sespie basic block. Return INSN if there are no such notes.
825c87b03e5Sespie
826c87b03e5Sespie When emitting jump to redirect a fallthru edge, it should always appear
827c87b03e5Sespie after the LOOP_BEG notes, as loop optimizer expect loop to either start by
828c87b03e5Sespie fallthru edge or jump following the LOOP_BEG note jumping to the loop exit
829c87b03e5Sespie test. */
830c87b03e5Sespie
831c87b03e5Sespie static rtx
last_loop_beg_note(insn)832c87b03e5Sespie last_loop_beg_note (insn)
833c87b03e5Sespie rtx insn;
834c87b03e5Sespie {
835c87b03e5Sespie rtx last = insn;
836c87b03e5Sespie
837c87b03e5Sespie for (insn = NEXT_INSN (insn); insn && GET_CODE (insn) == NOTE
838c87b03e5Sespie && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK;
839c87b03e5Sespie insn = NEXT_INSN (insn))
840c87b03e5Sespie if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
841c87b03e5Sespie last = insn;
842c87b03e5Sespie
843c87b03e5Sespie return last;
844c87b03e5Sespie }
845c87b03e5Sespie
846c87b03e5Sespie /* Attempt to change code to redirect edge E to TARGET. Don't do that on
847c87b03e5Sespie expense of adding new instructions or reordering basic blocks.
848c87b03e5Sespie
849c87b03e5Sespie Function can be also called with edge destination equivalent to the TARGET.
850c87b03e5Sespie Then it should try the simplifications and do nothing if none is possible.
851c87b03e5Sespie
852c87b03e5Sespie Return true if transformation succeeded. We still return false in case E
853c87b03e5Sespie already destinated TARGET and we didn't managed to simplify instruction
854c87b03e5Sespie stream. */
855c87b03e5Sespie
856c87b03e5Sespie bool
redirect_edge_and_branch(e,target)857c87b03e5Sespie redirect_edge_and_branch (e, target)
858c87b03e5Sespie edge e;
859c87b03e5Sespie basic_block target;
860c87b03e5Sespie {
861c87b03e5Sespie rtx tmp;
862c87b03e5Sespie rtx old_label = e->dest->head;
863c87b03e5Sespie basic_block src = e->src;
864c87b03e5Sespie rtx insn = src->end;
865c87b03e5Sespie
866c87b03e5Sespie if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
867c87b03e5Sespie return false;
868c87b03e5Sespie
869c87b03e5Sespie if (try_redirect_by_replacing_jump (e, target))
870c87b03e5Sespie return true;
871c87b03e5Sespie
872c87b03e5Sespie /* Do this fast path late, as we want above code to simplify for cases
873c87b03e5Sespie where called on single edge leaving basic block containing nontrivial
874c87b03e5Sespie jump insn. */
875c87b03e5Sespie else if (e->dest == target)
876c87b03e5Sespie return false;
877c87b03e5Sespie
878c87b03e5Sespie /* We can only redirect non-fallthru edges of jump insn. */
879c87b03e5Sespie if (e->flags & EDGE_FALLTHRU)
880c87b03e5Sespie return false;
881c87b03e5Sespie else if (GET_CODE (insn) != JUMP_INSN)
882c87b03e5Sespie return false;
883c87b03e5Sespie
884c87b03e5Sespie /* Recognize a tablejump and adjust all matching cases. */
885c87b03e5Sespie if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
886c87b03e5Sespie && (tmp = NEXT_INSN (tmp)) != NULL_RTX
887c87b03e5Sespie && GET_CODE (tmp) == JUMP_INSN
888c87b03e5Sespie && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
889c87b03e5Sespie || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
890c87b03e5Sespie {
891c87b03e5Sespie rtvec vec;
892c87b03e5Sespie int j;
893c87b03e5Sespie rtx new_label = block_label (target);
894c87b03e5Sespie
895c87b03e5Sespie if (target == EXIT_BLOCK_PTR)
896c87b03e5Sespie return false;
897c87b03e5Sespie if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
898c87b03e5Sespie vec = XVEC (PATTERN (tmp), 0);
899c87b03e5Sespie else
900c87b03e5Sespie vec = XVEC (PATTERN (tmp), 1);
901c87b03e5Sespie
902c87b03e5Sespie for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
903c87b03e5Sespie if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
904c87b03e5Sespie {
905c87b03e5Sespie RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
906c87b03e5Sespie --LABEL_NUSES (old_label);
907c87b03e5Sespie ++LABEL_NUSES (new_label);
908c87b03e5Sespie }
909c87b03e5Sespie
910c87b03e5Sespie /* Handle casesi dispatch insns */
911c87b03e5Sespie if ((tmp = single_set (insn)) != NULL
912c87b03e5Sespie && SET_DEST (tmp) == pc_rtx
913c87b03e5Sespie && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
914c87b03e5Sespie && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
915c87b03e5Sespie && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
916c87b03e5Sespie {
917c87b03e5Sespie XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (VOIDmode,
918c87b03e5Sespie new_label);
919c87b03e5Sespie --LABEL_NUSES (old_label);
920c87b03e5Sespie ++LABEL_NUSES (new_label);
921c87b03e5Sespie }
922c87b03e5Sespie }
923c87b03e5Sespie else
924c87b03e5Sespie {
925c87b03e5Sespie /* ?? We may play the games with moving the named labels from
926c87b03e5Sespie one basic block to the other in case only one computed_jump is
927c87b03e5Sespie available. */
928c87b03e5Sespie if (computed_jump_p (insn)
929c87b03e5Sespie /* A return instruction can't be redirected. */
930c87b03e5Sespie || returnjump_p (insn))
931c87b03e5Sespie return false;
932c87b03e5Sespie
933c87b03e5Sespie /* If the insn doesn't go where we think, we're confused. */
934c87b03e5Sespie if (JUMP_LABEL (insn) != old_label)
935c87b03e5Sespie abort ();
936c87b03e5Sespie
937c87b03e5Sespie /* If the substitution doesn't succeed, die. This can happen
938c87b03e5Sespie if the back end emitted unrecognizable instructions or if
939c87b03e5Sespie target is exit block on some arches. */
940c87b03e5Sespie if (!redirect_jump (insn, block_label (target), 0))
941c87b03e5Sespie {
942c87b03e5Sespie if (target == EXIT_BLOCK_PTR)
943c87b03e5Sespie return false;
944c87b03e5Sespie abort ();
945c87b03e5Sespie }
946c87b03e5Sespie }
947c87b03e5Sespie
948c87b03e5Sespie if (rtl_dump_file)
949c87b03e5Sespie fprintf (rtl_dump_file, "Edge %i->%i redirected to %i\n",
950c87b03e5Sespie e->src->index, e->dest->index, target->index);
951c87b03e5Sespie
952c87b03e5Sespie if (e->dest != target)
953c87b03e5Sespie redirect_edge_succ_nodup (e, target);
954c87b03e5Sespie
955c87b03e5Sespie return true;
956c87b03e5Sespie }
957c87b03e5Sespie
958c87b03e5Sespie /* Like force_nonfallthru below, but additionally performs redirection
959c87b03e5Sespie Used by redirect_edge_and_branch_force. */
960c87b03e5Sespie
961c87b03e5Sespie static basic_block
force_nonfallthru_and_redirect(e,target)962c87b03e5Sespie force_nonfallthru_and_redirect (e, target)
963c87b03e5Sespie edge e;
964c87b03e5Sespie basic_block target;
965c87b03e5Sespie {
966c87b03e5Sespie basic_block jump_block, new_bb = NULL, src = e->src;
967c87b03e5Sespie rtx note;
968c87b03e5Sespie edge new_edge;
969c87b03e5Sespie int abnormal_edge_flags = 0;
970c87b03e5Sespie
971c87b03e5Sespie /* In the case the last instruction is conditional jump to the next
972c87b03e5Sespie instruction, first redirect the jump itself and then continue
973c87b03e5Sespie by creating an basic block afterwards to redirect fallthru edge. */
974c87b03e5Sespie if (e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR
975c87b03e5Sespie && any_condjump_p (e->src->end)
976c87b03e5Sespie /* When called from cfglayout, fallthru edges do not
977c87b03e5Sespie neccessarily go to the next block. */
978c87b03e5Sespie && e->src->next_bb == e->dest
979c87b03e5Sespie && JUMP_LABEL (e->src->end) == e->dest->head)
980c87b03e5Sespie {
981c87b03e5Sespie rtx note;
982c87b03e5Sespie edge b = unchecked_make_edge (e->src, target, 0);
983c87b03e5Sespie
984c87b03e5Sespie if (!redirect_jump (e->src->end, block_label (target), 0))
985c87b03e5Sespie abort ();
986c87b03e5Sespie note = find_reg_note (e->src->end, REG_BR_PROB, NULL_RTX);
987c87b03e5Sespie if (note)
988c87b03e5Sespie {
989c87b03e5Sespie int prob = INTVAL (XEXP (note, 0));
990c87b03e5Sespie
991c87b03e5Sespie b->probability = prob;
992c87b03e5Sespie b->count = e->count * prob / REG_BR_PROB_BASE;
993c87b03e5Sespie e->probability -= e->probability;
994c87b03e5Sespie e->count -= b->count;
995c87b03e5Sespie if (e->probability < 0)
996c87b03e5Sespie e->probability = 0;
997c87b03e5Sespie if (e->count < 0)
998c87b03e5Sespie e->count = 0;
999c87b03e5Sespie }
1000c87b03e5Sespie }
1001c87b03e5Sespie
1002c87b03e5Sespie if (e->flags & EDGE_ABNORMAL)
1003c87b03e5Sespie {
1004c87b03e5Sespie /* Irritating special case - fallthru edge to the same block as abnormal
1005c87b03e5Sespie edge.
1006c87b03e5Sespie We can't redirect abnormal edge, but we still can split the fallthru
1007c87b03e5Sespie one and create separate abnormal edge to original destination.
1008c87b03e5Sespie This allows bb-reorder to make such edge non-fallthru. */
1009c87b03e5Sespie if (e->dest != target)
1010c87b03e5Sespie abort ();
1011c87b03e5Sespie abnormal_edge_flags = e->flags & ~(EDGE_FALLTHRU | EDGE_CAN_FALLTHRU);
1012c87b03e5Sespie e->flags &= EDGE_FALLTHRU | EDGE_CAN_FALLTHRU;
1013c87b03e5Sespie }
1014c87b03e5Sespie else if (!(e->flags & EDGE_FALLTHRU))
1015c87b03e5Sespie abort ();
1016c87b03e5Sespie else if (e->src == ENTRY_BLOCK_PTR)
1017c87b03e5Sespie {
1018c87b03e5Sespie /* We can't redirect the entry block. Create an empty block at the
1019c87b03e5Sespie start of the function which we use to add the new jump. */
1020c87b03e5Sespie edge *pe1;
1021c87b03e5Sespie basic_block bb = create_basic_block (e->dest->head, NULL, ENTRY_BLOCK_PTR);
1022c87b03e5Sespie
1023c87b03e5Sespie /* Change the existing edge's source to be the new block, and add
1024c87b03e5Sespie a new edge from the entry block to the new block. */
1025c87b03e5Sespie e->src = bb;
1026c87b03e5Sespie for (pe1 = &ENTRY_BLOCK_PTR->succ; *pe1; pe1 = &(*pe1)->succ_next)
1027c87b03e5Sespie if (*pe1 == e)
1028c87b03e5Sespie {
1029c87b03e5Sespie *pe1 = e->succ_next;
1030c87b03e5Sespie break;
1031c87b03e5Sespie }
1032c87b03e5Sespie e->succ_next = 0;
1033c87b03e5Sespie bb->succ = e;
1034c87b03e5Sespie make_single_succ_edge (ENTRY_BLOCK_PTR, bb, EDGE_FALLTHRU);
1035c87b03e5Sespie }
1036c87b03e5Sespie
1037c87b03e5Sespie if (e->src->succ->succ_next || abnormal_edge_flags)
1038c87b03e5Sespie {
1039c87b03e5Sespie /* Create the new structures. */
1040c87b03e5Sespie
1041c87b03e5Sespie /* Position the new block correctly relative to loop notes. */
1042c87b03e5Sespie note = last_loop_beg_note (e->src->end);
1043c87b03e5Sespie note = NEXT_INSN (note);
1044c87b03e5Sespie
1045c87b03e5Sespie /* ... and ADDR_VECs. */
1046c87b03e5Sespie if (note != NULL
1047c87b03e5Sespie && GET_CODE (note) == CODE_LABEL
1048c87b03e5Sespie && NEXT_INSN (note)
1049c87b03e5Sespie && GET_CODE (NEXT_INSN (note)) == JUMP_INSN
1050c87b03e5Sespie && (GET_CODE (PATTERN (NEXT_INSN (note))) == ADDR_DIFF_VEC
1051c87b03e5Sespie || GET_CODE (PATTERN (NEXT_INSN (note))) == ADDR_VEC))
1052c87b03e5Sespie note = NEXT_INSN (NEXT_INSN (note));
1053c87b03e5Sespie
1054c87b03e5Sespie jump_block = create_basic_block (note, NULL, e->src);
1055c87b03e5Sespie jump_block->count = e->count;
1056c87b03e5Sespie jump_block->frequency = EDGE_FREQUENCY (e);
1057c87b03e5Sespie jump_block->loop_depth = target->loop_depth;
1058c87b03e5Sespie
1059c87b03e5Sespie if (target->global_live_at_start)
1060c87b03e5Sespie {
1061c87b03e5Sespie jump_block->global_live_at_start
1062c87b03e5Sespie = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1063c87b03e5Sespie jump_block->global_live_at_end
1064c87b03e5Sespie = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1065c87b03e5Sespie COPY_REG_SET (jump_block->global_live_at_start,
1066c87b03e5Sespie target->global_live_at_start);
1067c87b03e5Sespie COPY_REG_SET (jump_block->global_live_at_end,
1068c87b03e5Sespie target->global_live_at_start);
1069c87b03e5Sespie }
1070c87b03e5Sespie
1071c87b03e5Sespie /* Wire edge in. */
1072c87b03e5Sespie new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1073c87b03e5Sespie new_edge->probability = e->probability;
1074c87b03e5Sespie new_edge->count = e->count;
1075c87b03e5Sespie
1076c87b03e5Sespie /* Redirect old edge. */
1077c87b03e5Sespie redirect_edge_pred (e, jump_block);
1078c87b03e5Sespie e->probability = REG_BR_PROB_BASE;
1079c87b03e5Sespie
1080c87b03e5Sespie new_bb = jump_block;
1081c87b03e5Sespie }
1082c87b03e5Sespie else
1083c87b03e5Sespie jump_block = e->src;
1084c87b03e5Sespie
1085c87b03e5Sespie e->flags &= ~EDGE_FALLTHRU;
1086c87b03e5Sespie if (target == EXIT_BLOCK_PTR)
1087c87b03e5Sespie {
1088c87b03e5Sespie if (HAVE_return)
1089c87b03e5Sespie emit_jump_insn_after (gen_return (), jump_block->end);
1090c87b03e5Sespie else
1091c87b03e5Sespie abort ();
1092c87b03e5Sespie }
1093c87b03e5Sespie else
1094c87b03e5Sespie {
1095c87b03e5Sespie rtx label = block_label (target);
1096c87b03e5Sespie emit_jump_insn_after (gen_jump (label), jump_block->end);
1097c87b03e5Sespie JUMP_LABEL (jump_block->end) = label;
1098c87b03e5Sespie LABEL_NUSES (label)++;
1099c87b03e5Sespie }
1100c87b03e5Sespie
1101c87b03e5Sespie emit_barrier_after (jump_block->end);
1102c87b03e5Sespie redirect_edge_succ_nodup (e, target);
1103c87b03e5Sespie
1104c87b03e5Sespie if (abnormal_edge_flags)
1105c87b03e5Sespie make_edge (src, target, abnormal_edge_flags);
1106c87b03e5Sespie
1107c87b03e5Sespie return new_bb;
1108c87b03e5Sespie }
1109c87b03e5Sespie
1110c87b03e5Sespie /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1111c87b03e5Sespie (and possibly create new basic block) to make edge non-fallthru.
1112c87b03e5Sespie Return newly created BB or NULL if none. */
1113c87b03e5Sespie
1114c87b03e5Sespie basic_block
force_nonfallthru(e)1115c87b03e5Sespie force_nonfallthru (e)
1116c87b03e5Sespie edge e;
1117c87b03e5Sespie {
1118c87b03e5Sespie return force_nonfallthru_and_redirect (e, e->dest);
1119c87b03e5Sespie }
1120c87b03e5Sespie
1121c87b03e5Sespie /* Redirect edge even at the expense of creating new jump insn or
1122c87b03e5Sespie basic block. Return new basic block if created, NULL otherwise.
1123c87b03e5Sespie Abort if conversion is impossible. */
1124c87b03e5Sespie
1125c87b03e5Sespie basic_block
redirect_edge_and_branch_force(e,target)1126c87b03e5Sespie redirect_edge_and_branch_force (e, target)
1127c87b03e5Sespie edge e;
1128c87b03e5Sespie basic_block target;
1129c87b03e5Sespie {
1130c87b03e5Sespie if (redirect_edge_and_branch (e, target)
1131c87b03e5Sespie || e->dest == target)
1132c87b03e5Sespie return NULL;
1133c87b03e5Sespie
1134c87b03e5Sespie /* In case the edge redirection failed, try to force it to be non-fallthru
1135c87b03e5Sespie and redirect newly created simplejump. */
1136c87b03e5Sespie return force_nonfallthru_and_redirect (e, target);
1137c87b03e5Sespie }
1138c87b03e5Sespie
1139c87b03e5Sespie /* The given edge should potentially be a fallthru edge. If that is in
1140c87b03e5Sespie fact true, delete the jump and barriers that are in the way. */
1141c87b03e5Sespie
1142c87b03e5Sespie void
tidy_fallthru_edge(e,b,c)1143c87b03e5Sespie tidy_fallthru_edge (e, b, c)
1144c87b03e5Sespie edge e;
1145c87b03e5Sespie basic_block b, c;
1146c87b03e5Sespie {
1147c87b03e5Sespie rtx q;
1148c87b03e5Sespie
1149c87b03e5Sespie /* ??? In a late-running flow pass, other folks may have deleted basic
1150c87b03e5Sespie blocks by nopping out blocks, leaving multiple BARRIERs between here
1151c87b03e5Sespie and the target label. They ought to be chastized and fixed.
1152c87b03e5Sespie
1153c87b03e5Sespie We can also wind up with a sequence of undeletable labels between
1154c87b03e5Sespie one block and the next.
1155c87b03e5Sespie
1156c87b03e5Sespie So search through a sequence of barriers, labels, and notes for
1157c87b03e5Sespie the head of block C and assert that we really do fall through. */
1158c87b03e5Sespie
1159c87b03e5Sespie for (q = NEXT_INSN (b->end); q != c->head; q = NEXT_INSN (q))
1160c87b03e5Sespie if (INSN_P (q))
1161c87b03e5Sespie return;
1162c87b03e5Sespie
1163c87b03e5Sespie /* Remove what will soon cease being the jump insn from the source block.
1164c87b03e5Sespie If block B consisted only of this single jump, turn it into a deleted
1165c87b03e5Sespie note. */
1166c87b03e5Sespie q = b->end;
1167c87b03e5Sespie if (GET_CODE (q) == JUMP_INSN
1168c87b03e5Sespie && onlyjump_p (q)
1169c87b03e5Sespie && (any_uncondjump_p (q)
1170c87b03e5Sespie || (b->succ == e && e->succ_next == NULL)))
1171c87b03e5Sespie {
1172c87b03e5Sespie #ifdef HAVE_cc0
1173c87b03e5Sespie /* If this was a conditional jump, we need to also delete
1174c87b03e5Sespie the insn that set cc0. */
1175c87b03e5Sespie if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1176c87b03e5Sespie q = PREV_INSN (q);
1177c87b03e5Sespie #endif
1178c87b03e5Sespie
1179c87b03e5Sespie q = PREV_INSN (q);
1180c87b03e5Sespie
1181c87b03e5Sespie /* We don't want a block to end on a line-number note since that has
1182c87b03e5Sespie the potential of changing the code between -g and not -g. */
1183c87b03e5Sespie while (GET_CODE (q) == NOTE && NOTE_LINE_NUMBER (q) >= 0)
1184c87b03e5Sespie q = PREV_INSN (q);
1185c87b03e5Sespie }
1186c87b03e5Sespie
1187c87b03e5Sespie /* Selectively unlink the sequence. */
1188c87b03e5Sespie if (q != PREV_INSN (c->head))
1189c87b03e5Sespie delete_insn_chain (NEXT_INSN (q), PREV_INSN (c->head));
1190c87b03e5Sespie
1191c87b03e5Sespie e->flags |= EDGE_FALLTHRU;
1192c87b03e5Sespie }
1193c87b03e5Sespie
1194c87b03e5Sespie /* Fix up edges that now fall through, or rather should now fall through
1195c87b03e5Sespie but previously required a jump around now deleted blocks. Simplify
1196c87b03e5Sespie the search by only examining blocks numerically adjacent, since this
1197c87b03e5Sespie is how find_basic_blocks created them. */
1198c87b03e5Sespie
1199c87b03e5Sespie void
tidy_fallthru_edges()1200c87b03e5Sespie tidy_fallthru_edges ()
1201c87b03e5Sespie {
1202c87b03e5Sespie basic_block b, c;
1203c87b03e5Sespie
1204c87b03e5Sespie if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
1205c87b03e5Sespie return;
1206c87b03e5Sespie
1207c87b03e5Sespie FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb)
1208c87b03e5Sespie {
1209c87b03e5Sespie edge s;
1210c87b03e5Sespie
1211c87b03e5Sespie c = b->next_bb;
1212c87b03e5Sespie
1213c87b03e5Sespie /* We care about simple conditional or unconditional jumps with
1214c87b03e5Sespie a single successor.
1215c87b03e5Sespie
1216c87b03e5Sespie If we had a conditional branch to the next instruction when
1217c87b03e5Sespie find_basic_blocks was called, then there will only be one
1218c87b03e5Sespie out edge for the block which ended with the conditional
1219c87b03e5Sespie branch (since we do not create duplicate edges).
1220c87b03e5Sespie
1221c87b03e5Sespie Furthermore, the edge will be marked as a fallthru because we
1222c87b03e5Sespie merge the flags for the duplicate edges. So we do not want to
1223c87b03e5Sespie check that the edge is not a FALLTHRU edge. */
1224c87b03e5Sespie
1225c87b03e5Sespie if ((s = b->succ) != NULL
1226c87b03e5Sespie && ! (s->flags & EDGE_COMPLEX)
1227c87b03e5Sespie && s->succ_next == NULL
1228c87b03e5Sespie && s->dest == c
1229c87b03e5Sespie /* If the jump insn has side effects, we can't tidy the edge. */
1230c87b03e5Sespie && (GET_CODE (b->end) != JUMP_INSN
1231c87b03e5Sespie || onlyjump_p (b->end)))
1232c87b03e5Sespie tidy_fallthru_edge (s, b, c);
1233c87b03e5Sespie }
1234c87b03e5Sespie }
1235c87b03e5Sespie
1236c87b03e5Sespie /* Helper function for split_edge. Return true in case edge BB2 to BB1
1237c87b03e5Sespie is back edge of syntactic loop. */
1238c87b03e5Sespie
1239c87b03e5Sespie static bool
back_edge_of_syntactic_loop_p(bb1,bb2)1240c87b03e5Sespie back_edge_of_syntactic_loop_p (bb1, bb2)
1241c87b03e5Sespie basic_block bb1, bb2;
1242c87b03e5Sespie {
1243c87b03e5Sespie rtx insn;
1244c87b03e5Sespie int count = 0;
1245c87b03e5Sespie basic_block bb;
1246c87b03e5Sespie
1247c87b03e5Sespie if (bb1 == bb2)
1248c87b03e5Sespie return true;
1249c87b03e5Sespie
1250c87b03e5Sespie /* ??? Could we guarantee that bb indices are monotone, so that we could
1251c87b03e5Sespie just compare them? */
1252c87b03e5Sespie for (bb = bb1; bb && bb != bb2; bb = bb->next_bb)
1253c87b03e5Sespie continue;
1254c87b03e5Sespie
1255c87b03e5Sespie if (!bb)
1256c87b03e5Sespie return false;
1257c87b03e5Sespie
1258c87b03e5Sespie for (insn = bb1->end; insn != bb2->head && count >= 0;
1259c87b03e5Sespie insn = NEXT_INSN (insn))
1260c87b03e5Sespie if (GET_CODE (insn) == NOTE)
1261c87b03e5Sespie {
1262c87b03e5Sespie if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1263c87b03e5Sespie count++;
1264c87b03e5Sespie else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1265c87b03e5Sespie count--;
1266c87b03e5Sespie }
1267c87b03e5Sespie
1268c87b03e5Sespie return count >= 0;
1269c87b03e5Sespie }
1270c87b03e5Sespie
1271c87b03e5Sespie /* Split a (typically critical) edge. Return the new block.
1272c87b03e5Sespie Abort on abnormal edges.
1273c87b03e5Sespie
1274c87b03e5Sespie ??? The code generally expects to be called on critical edges.
1275c87b03e5Sespie The case of a block ending in an unconditional jump to a
1276c87b03e5Sespie block with multiple predecessors is not handled optimally. */
1277c87b03e5Sespie
1278c87b03e5Sespie basic_block
split_edge(edge_in)1279c87b03e5Sespie split_edge (edge_in)
1280c87b03e5Sespie edge edge_in;
1281c87b03e5Sespie {
1282c87b03e5Sespie basic_block bb;
1283c87b03e5Sespie edge edge_out;
1284c87b03e5Sespie rtx before;
1285c87b03e5Sespie
1286c87b03e5Sespie /* Abnormal edges cannot be split. */
1287c87b03e5Sespie if ((edge_in->flags & EDGE_ABNORMAL) != 0)
1288c87b03e5Sespie abort ();
1289c87b03e5Sespie
1290c87b03e5Sespie /* We are going to place the new block in front of edge destination.
1291c87b03e5Sespie Avoid existence of fallthru predecessors. */
1292c87b03e5Sespie if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1293c87b03e5Sespie {
1294c87b03e5Sespie edge e;
1295c87b03e5Sespie
1296c87b03e5Sespie for (e = edge_in->dest->pred; e; e = e->pred_next)
1297c87b03e5Sespie if (e->flags & EDGE_FALLTHRU)
1298c87b03e5Sespie break;
1299c87b03e5Sespie
1300c87b03e5Sespie if (e)
1301c87b03e5Sespie force_nonfallthru (e);
1302c87b03e5Sespie }
1303c87b03e5Sespie
1304c87b03e5Sespie /* Create the basic block note.
1305c87b03e5Sespie
1306c87b03e5Sespie Where we place the note can have a noticeable impact on the generated
1307c87b03e5Sespie code. Consider this cfg:
1308c87b03e5Sespie
1309c87b03e5Sespie E
1310c87b03e5Sespie |
1311c87b03e5Sespie 0
1312c87b03e5Sespie / \
1313c87b03e5Sespie +->1-->2--->E
1314c87b03e5Sespie | |
1315c87b03e5Sespie +--+
1316c87b03e5Sespie
1317c87b03e5Sespie If we need to insert an insn on the edge from block 0 to block 1,
1318c87b03e5Sespie we want to ensure the instructions we insert are outside of any
1319c87b03e5Sespie loop notes that physically sit between block 0 and block 1. Otherwise
1320c87b03e5Sespie we confuse the loop optimizer into thinking the loop is a phony. */
1321c87b03e5Sespie
1322c87b03e5Sespie if (edge_in->dest != EXIT_BLOCK_PTR
1323c87b03e5Sespie && PREV_INSN (edge_in->dest->head)
1324c87b03e5Sespie && GET_CODE (PREV_INSN (edge_in->dest->head)) == NOTE
1325c87b03e5Sespie && (NOTE_LINE_NUMBER (PREV_INSN (edge_in->dest->head))
1326c87b03e5Sespie == NOTE_INSN_LOOP_BEG)
1327c87b03e5Sespie && !back_edge_of_syntactic_loop_p (edge_in->dest, edge_in->src))
1328c87b03e5Sespie before = PREV_INSN (edge_in->dest->head);
1329c87b03e5Sespie else if (edge_in->dest != EXIT_BLOCK_PTR)
1330c87b03e5Sespie before = edge_in->dest->head;
1331c87b03e5Sespie else
1332c87b03e5Sespie before = NULL_RTX;
1333c87b03e5Sespie
1334c87b03e5Sespie bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
1335c87b03e5Sespie bb->count = edge_in->count;
1336c87b03e5Sespie bb->frequency = EDGE_FREQUENCY (edge_in);
1337c87b03e5Sespie
1338c87b03e5Sespie /* ??? This info is likely going to be out of date very soon. */
1339c87b03e5Sespie if (edge_in->dest->global_live_at_start)
1340c87b03e5Sespie {
1341c87b03e5Sespie bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1342c87b03e5Sespie bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1343c87b03e5Sespie COPY_REG_SET (bb->global_live_at_start,
1344c87b03e5Sespie edge_in->dest->global_live_at_start);
1345c87b03e5Sespie COPY_REG_SET (bb->global_live_at_end,
1346c87b03e5Sespie edge_in->dest->global_live_at_start);
1347c87b03e5Sespie }
1348c87b03e5Sespie
1349c87b03e5Sespie edge_out = make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1350c87b03e5Sespie
1351c87b03e5Sespie /* For non-fallthry edges, we must adjust the predecessor's
1352c87b03e5Sespie jump instruction to target our new block. */
1353c87b03e5Sespie if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1354c87b03e5Sespie {
1355c87b03e5Sespie if (!redirect_edge_and_branch (edge_in, bb))
1356c87b03e5Sespie abort ();
1357c87b03e5Sespie }
1358c87b03e5Sespie else
1359c87b03e5Sespie redirect_edge_succ (edge_in, bb);
1360c87b03e5Sespie
1361c87b03e5Sespie return bb;
1362c87b03e5Sespie }
1363c87b03e5Sespie
1364c87b03e5Sespie /* Queue instructions for insertion on an edge between two basic blocks.
1365c87b03e5Sespie The new instructions and basic blocks (if any) will not appear in the
1366c87b03e5Sespie CFG until commit_edge_insertions is called. */
1367c87b03e5Sespie
1368c87b03e5Sespie void
insert_insn_on_edge(pattern,e)1369c87b03e5Sespie insert_insn_on_edge (pattern, e)
1370c87b03e5Sespie rtx pattern;
1371c87b03e5Sespie edge e;
1372c87b03e5Sespie {
1373c87b03e5Sespie /* We cannot insert instructions on an abnormal critical edge.
1374c87b03e5Sespie It will be easier to find the culprit if we die now. */
1375c87b03e5Sespie if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
1376c87b03e5Sespie abort ();
1377c87b03e5Sespie
1378c87b03e5Sespie if (e->insns == NULL_RTX)
1379c87b03e5Sespie start_sequence ();
1380c87b03e5Sespie else
1381c87b03e5Sespie push_to_sequence (e->insns);
1382c87b03e5Sespie
1383c87b03e5Sespie emit_insn (pattern);
1384c87b03e5Sespie
1385c87b03e5Sespie e->insns = get_insns ();
1386c87b03e5Sespie end_sequence ();
1387c87b03e5Sespie }
1388c87b03e5Sespie
1389c87b03e5Sespie /* Update the CFG for the instructions queued on edge E. */
1390c87b03e5Sespie
1391c87b03e5Sespie static void
commit_one_edge_insertion(e,watch_calls)1392c87b03e5Sespie commit_one_edge_insertion (e, watch_calls)
1393c87b03e5Sespie edge e;
1394c87b03e5Sespie int watch_calls;
1395c87b03e5Sespie {
1396c87b03e5Sespie rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
1397c87b03e5Sespie basic_block bb = NULL;
1398c87b03e5Sespie
1399c87b03e5Sespie /* Pull the insns off the edge now since the edge might go away. */
1400c87b03e5Sespie insns = e->insns;
1401c87b03e5Sespie e->insns = NULL_RTX;
1402c87b03e5Sespie
1403c87b03e5Sespie /* Special case -- avoid inserting code between call and storing
1404c87b03e5Sespie its return value. */
1405c87b03e5Sespie if (watch_calls && (e->flags & EDGE_FALLTHRU) && !e->dest->pred->pred_next
1406c87b03e5Sespie && e->src != ENTRY_BLOCK_PTR
1407c87b03e5Sespie && GET_CODE (e->src->end) == CALL_INSN)
1408c87b03e5Sespie {
1409c87b03e5Sespie rtx next = next_nonnote_insn (e->src->end);
1410c87b03e5Sespie
1411c87b03e5Sespie after = e->dest->head;
1412c87b03e5Sespie /* The first insn after the call may be a stack pop, skip it. */
1413c87b03e5Sespie while (next
1414c87b03e5Sespie && keep_with_call_p (next))
1415c87b03e5Sespie {
1416c87b03e5Sespie after = next;
1417c87b03e5Sespie next = next_nonnote_insn (next);
1418c87b03e5Sespie }
1419c87b03e5Sespie bb = e->dest;
1420c87b03e5Sespie }
1421c87b03e5Sespie if (!before && !after)
1422c87b03e5Sespie {
1423c87b03e5Sespie /* Figure out where to put these things. If the destination has
1424c87b03e5Sespie one predecessor, insert there. Except for the exit block. */
1425c87b03e5Sespie if (e->dest->pred->pred_next == NULL && e->dest != EXIT_BLOCK_PTR)
1426c87b03e5Sespie {
1427c87b03e5Sespie bb = e->dest;
1428c87b03e5Sespie
1429c87b03e5Sespie /* Get the location correct wrt a code label, and "nice" wrt
1430c87b03e5Sespie a basic block note, and before everything else. */
1431c87b03e5Sespie tmp = bb->head;
1432c87b03e5Sespie if (GET_CODE (tmp) == CODE_LABEL)
1433c87b03e5Sespie tmp = NEXT_INSN (tmp);
1434c87b03e5Sespie if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1435c87b03e5Sespie tmp = NEXT_INSN (tmp);
1436c87b03e5Sespie if (tmp == bb->head)
1437c87b03e5Sespie before = tmp;
1438c87b03e5Sespie else if (tmp)
1439c87b03e5Sespie after = PREV_INSN (tmp);
1440c87b03e5Sespie else
1441c87b03e5Sespie after = get_last_insn ();
1442c87b03e5Sespie }
1443c87b03e5Sespie
1444c87b03e5Sespie /* If the source has one successor and the edge is not abnormal,
1445c87b03e5Sespie insert there. Except for the entry block. */
1446c87b03e5Sespie else if ((e->flags & EDGE_ABNORMAL) == 0
1447c87b03e5Sespie && e->src->succ->succ_next == NULL
1448c87b03e5Sespie && e->src != ENTRY_BLOCK_PTR)
1449c87b03e5Sespie {
1450c87b03e5Sespie bb = e->src;
1451c87b03e5Sespie
1452c87b03e5Sespie /* It is possible to have a non-simple jump here. Consider a target
1453c87b03e5Sespie where some forms of unconditional jumps clobber a register. This
1454c87b03e5Sespie happens on the fr30 for example.
1455c87b03e5Sespie
1456c87b03e5Sespie We know this block has a single successor, so we can just emit
1457c87b03e5Sespie the queued insns before the jump. */
1458c87b03e5Sespie if (GET_CODE (bb->end) == JUMP_INSN)
1459c87b03e5Sespie for (before = bb->end;
1460c87b03e5Sespie GET_CODE (PREV_INSN (before)) == NOTE
1461c87b03e5Sespie && NOTE_LINE_NUMBER (PREV_INSN (before)) ==
1462c87b03e5Sespie NOTE_INSN_LOOP_BEG; before = PREV_INSN (before))
1463c87b03e5Sespie ;
1464c87b03e5Sespie else
1465c87b03e5Sespie {
1466c87b03e5Sespie /* We'd better be fallthru, or we've lost track of what's what. */
1467c87b03e5Sespie if ((e->flags & EDGE_FALLTHRU) == 0)
1468c87b03e5Sespie abort ();
1469c87b03e5Sespie
1470c87b03e5Sespie after = bb->end;
1471c87b03e5Sespie }
1472c87b03e5Sespie }
1473c87b03e5Sespie /* Otherwise we must split the edge. */
1474c87b03e5Sespie else
1475c87b03e5Sespie {
1476c87b03e5Sespie bb = split_edge (e);
1477c87b03e5Sespie after = bb->end;
1478c87b03e5Sespie }
1479c87b03e5Sespie }
1480c87b03e5Sespie
1481c87b03e5Sespie /* Now that we've found the spot, do the insertion. */
1482c87b03e5Sespie
1483c87b03e5Sespie if (before)
1484c87b03e5Sespie {
1485c87b03e5Sespie emit_insn_before (insns, before);
1486c87b03e5Sespie last = prev_nonnote_insn (before);
1487c87b03e5Sespie }
1488c87b03e5Sespie else
1489c87b03e5Sespie last = emit_insn_after (insns, after);
1490c87b03e5Sespie
1491c87b03e5Sespie if (returnjump_p (last))
1492c87b03e5Sespie {
1493c87b03e5Sespie /* ??? Remove all outgoing edges from BB and add one for EXIT.
1494c87b03e5Sespie This is not currently a problem because this only happens
1495c87b03e5Sespie for the (single) epilogue, which already has a fallthru edge
1496c87b03e5Sespie to EXIT. */
1497c87b03e5Sespie
1498c87b03e5Sespie e = bb->succ;
1499c87b03e5Sespie if (e->dest != EXIT_BLOCK_PTR
1500c87b03e5Sespie || e->succ_next != NULL || (e->flags & EDGE_FALLTHRU) == 0)
1501c87b03e5Sespie abort ();
1502c87b03e5Sespie
1503c87b03e5Sespie e->flags &= ~EDGE_FALLTHRU;
1504c87b03e5Sespie emit_barrier_after (last);
1505c87b03e5Sespie
1506c87b03e5Sespie if (before)
1507c87b03e5Sespie delete_insn (before);
1508c87b03e5Sespie }
1509c87b03e5Sespie else if (GET_CODE (last) == JUMP_INSN)
1510c87b03e5Sespie abort ();
1511c87b03e5Sespie
1512c87b03e5Sespie /* Mark the basic block for find_sub_basic_blocks. */
1513c87b03e5Sespie bb->aux = &bb->aux;
1514c87b03e5Sespie }
1515c87b03e5Sespie
1516c87b03e5Sespie /* Update the CFG for all queued instructions. */
1517c87b03e5Sespie
1518c87b03e5Sespie void
commit_edge_insertions()1519c87b03e5Sespie commit_edge_insertions ()
1520c87b03e5Sespie {
1521c87b03e5Sespie basic_block bb;
1522c87b03e5Sespie sbitmap blocks;
1523c87b03e5Sespie bool changed = false;
1524c87b03e5Sespie
1525c87b03e5Sespie #ifdef ENABLE_CHECKING
1526c87b03e5Sespie verify_flow_info ();
1527c87b03e5Sespie #endif
1528c87b03e5Sespie
1529c87b03e5Sespie FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1530c87b03e5Sespie {
1531c87b03e5Sespie edge e, next;
1532c87b03e5Sespie
1533c87b03e5Sespie for (e = bb->succ; e; e = next)
1534c87b03e5Sespie {
1535c87b03e5Sespie next = e->succ_next;
1536c87b03e5Sespie if (e->insns)
1537c87b03e5Sespie {
1538c87b03e5Sespie changed = true;
1539c87b03e5Sespie commit_one_edge_insertion (e, false);
1540c87b03e5Sespie }
1541c87b03e5Sespie }
1542c87b03e5Sespie }
1543c87b03e5Sespie
1544c87b03e5Sespie if (!changed)
1545c87b03e5Sespie return;
1546c87b03e5Sespie
1547c87b03e5Sespie blocks = sbitmap_alloc (last_basic_block);
1548c87b03e5Sespie sbitmap_zero (blocks);
1549c87b03e5Sespie FOR_EACH_BB (bb)
1550c87b03e5Sespie if (bb->aux)
1551c87b03e5Sespie {
1552c87b03e5Sespie SET_BIT (blocks, bb->index);
1553c87b03e5Sespie bb->aux = NULL;
1554c87b03e5Sespie }
1555c87b03e5Sespie find_many_sub_basic_blocks (blocks);
1556c87b03e5Sespie sbitmap_free (blocks);
1557c87b03e5Sespie }
1558c87b03e5Sespie
1559c87b03e5Sespie /* Update the CFG for all queued instructions, taking special care of inserting
1560c87b03e5Sespie code on edges between call and storing its return value. */
1561c87b03e5Sespie
1562c87b03e5Sespie void
commit_edge_insertions_watch_calls()1563c87b03e5Sespie commit_edge_insertions_watch_calls ()
1564c87b03e5Sespie {
1565c87b03e5Sespie basic_block bb;
1566c87b03e5Sespie sbitmap blocks;
1567c87b03e5Sespie bool changed = false;
1568c87b03e5Sespie
1569c87b03e5Sespie #ifdef ENABLE_CHECKING
1570c87b03e5Sespie verify_flow_info ();
1571c87b03e5Sespie #endif
1572c87b03e5Sespie
1573c87b03e5Sespie FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1574c87b03e5Sespie {
1575c87b03e5Sespie edge e, next;
1576c87b03e5Sespie
1577c87b03e5Sespie for (e = bb->succ; e; e = next)
1578c87b03e5Sespie {
1579c87b03e5Sespie next = e->succ_next;
1580c87b03e5Sespie if (e->insns)
1581c87b03e5Sespie {
1582c87b03e5Sespie changed = true;
1583c87b03e5Sespie commit_one_edge_insertion (e, true);
1584c87b03e5Sespie }
1585c87b03e5Sespie }
1586c87b03e5Sespie }
1587c87b03e5Sespie
1588c87b03e5Sespie if (!changed)
1589c87b03e5Sespie return;
1590c87b03e5Sespie
1591c87b03e5Sespie blocks = sbitmap_alloc (last_basic_block);
1592c87b03e5Sespie sbitmap_zero (blocks);
1593c87b03e5Sespie FOR_EACH_BB (bb)
1594c87b03e5Sespie if (bb->aux)
1595c87b03e5Sespie {
1596c87b03e5Sespie SET_BIT (blocks, bb->index);
1597c87b03e5Sespie bb->aux = NULL;
1598c87b03e5Sespie }
1599c87b03e5Sespie find_many_sub_basic_blocks (blocks);
1600c87b03e5Sespie sbitmap_free (blocks);
1601c87b03e5Sespie }
1602c87b03e5Sespie
1603c87b03e5Sespie /* Print out one basic block with live information at start and end. */
1604c87b03e5Sespie
1605c87b03e5Sespie void
dump_bb(bb,outf)1606c87b03e5Sespie dump_bb (bb, outf)
1607c87b03e5Sespie basic_block bb;
1608c87b03e5Sespie FILE *outf;
1609c87b03e5Sespie {
1610c87b03e5Sespie rtx insn;
1611c87b03e5Sespie rtx last;
1612c87b03e5Sespie edge e;
1613c87b03e5Sespie
1614c87b03e5Sespie fprintf (outf, ";; Basic block %d, loop depth %d, count ",
1615c87b03e5Sespie bb->index, bb->loop_depth);
1616c87b03e5Sespie fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
1617c87b03e5Sespie putc ('\n', outf);
1618c87b03e5Sespie
1619c87b03e5Sespie fputs (";; Predecessors: ", outf);
1620c87b03e5Sespie for (e = bb->pred; e; e = e->pred_next)
1621c87b03e5Sespie dump_edge_info (outf, e, 0);
1622c87b03e5Sespie putc ('\n', outf);
1623c87b03e5Sespie
1624c87b03e5Sespie fputs (";; Registers live at start:", outf);
1625c87b03e5Sespie dump_regset (bb->global_live_at_start, outf);
1626c87b03e5Sespie putc ('\n', outf);
1627c87b03e5Sespie
1628c87b03e5Sespie for (insn = bb->head, last = NEXT_INSN (bb->end); insn != last;
1629c87b03e5Sespie insn = NEXT_INSN (insn))
1630c87b03e5Sespie print_rtl_single (outf, insn);
1631c87b03e5Sespie
1632c87b03e5Sespie fputs (";; Registers live at end:", outf);
1633c87b03e5Sespie dump_regset (bb->global_live_at_end, outf);
1634c87b03e5Sespie putc ('\n', outf);
1635c87b03e5Sespie
1636c87b03e5Sespie fputs (";; Successors: ", outf);
1637c87b03e5Sespie for (e = bb->succ; e; e = e->succ_next)
1638c87b03e5Sespie dump_edge_info (outf, e, 1);
1639c87b03e5Sespie putc ('\n', outf);
1640c87b03e5Sespie }
1641c87b03e5Sespie
1642c87b03e5Sespie void
debug_bb(bb)1643c87b03e5Sespie debug_bb (bb)
1644c87b03e5Sespie basic_block bb;
1645c87b03e5Sespie {
1646c87b03e5Sespie dump_bb (bb, stderr);
1647c87b03e5Sespie }
1648c87b03e5Sespie
1649c87b03e5Sespie void
debug_bb_n(n)1650c87b03e5Sespie debug_bb_n (n)
1651c87b03e5Sespie int n;
1652c87b03e5Sespie {
1653c87b03e5Sespie dump_bb (BASIC_BLOCK (n), stderr);
1654c87b03e5Sespie }
1655c87b03e5Sespie
1656c87b03e5Sespie /* Like print_rtl, but also print out live information for the start of each
1657c87b03e5Sespie basic block. */
1658c87b03e5Sespie
1659c87b03e5Sespie void
print_rtl_with_bb(outf,rtx_first)1660c87b03e5Sespie print_rtl_with_bb (outf, rtx_first)
1661c87b03e5Sespie FILE *outf;
1662c87b03e5Sespie rtx rtx_first;
1663c87b03e5Sespie {
1664c87b03e5Sespie rtx tmp_rtx;
1665c87b03e5Sespie
1666c87b03e5Sespie if (rtx_first == 0)
1667c87b03e5Sespie fprintf (outf, "(nil)\n");
1668c87b03e5Sespie else
1669c87b03e5Sespie {
1670c87b03e5Sespie enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
1671c87b03e5Sespie int max_uid = get_max_uid ();
1672c87b03e5Sespie basic_block *start
1673c87b03e5Sespie = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1674c87b03e5Sespie basic_block *end
1675c87b03e5Sespie = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1676c87b03e5Sespie enum bb_state *in_bb_p
1677c87b03e5Sespie = (enum bb_state *) xcalloc (max_uid, sizeof (enum bb_state));
1678c87b03e5Sespie
1679c87b03e5Sespie basic_block bb;
1680c87b03e5Sespie
1681c87b03e5Sespie FOR_EACH_BB_REVERSE (bb)
1682c87b03e5Sespie {
1683c87b03e5Sespie rtx x;
1684c87b03e5Sespie
1685c87b03e5Sespie start[INSN_UID (bb->head)] = bb;
1686c87b03e5Sespie end[INSN_UID (bb->end)] = bb;
1687c87b03e5Sespie for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x))
1688c87b03e5Sespie {
1689c87b03e5Sespie enum bb_state state = IN_MULTIPLE_BB;
1690c87b03e5Sespie
1691c87b03e5Sespie if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
1692c87b03e5Sespie state = IN_ONE_BB;
1693c87b03e5Sespie in_bb_p[INSN_UID (x)] = state;
1694c87b03e5Sespie
1695c87b03e5Sespie if (x == bb->end)
1696c87b03e5Sespie break;
1697c87b03e5Sespie }
1698c87b03e5Sespie }
1699c87b03e5Sespie
1700c87b03e5Sespie for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
1701c87b03e5Sespie {
1702c87b03e5Sespie int did_output;
1703c87b03e5Sespie
1704c87b03e5Sespie if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
1705c87b03e5Sespie {
1706c87b03e5Sespie fprintf (outf, ";; Start of basic block %d, registers live:",
1707c87b03e5Sespie bb->index);
1708c87b03e5Sespie dump_regset (bb->global_live_at_start, outf);
1709c87b03e5Sespie putc ('\n', outf);
1710c87b03e5Sespie }
1711c87b03e5Sespie
1712c87b03e5Sespie if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
1713c87b03e5Sespie && GET_CODE (tmp_rtx) != NOTE
1714c87b03e5Sespie && GET_CODE (tmp_rtx) != BARRIER)
1715c87b03e5Sespie fprintf (outf, ";; Insn is not within a basic block\n");
1716c87b03e5Sespie else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
1717c87b03e5Sespie fprintf (outf, ";; Insn is in multiple basic blocks\n");
1718c87b03e5Sespie
1719c87b03e5Sespie did_output = print_rtl_single (outf, tmp_rtx);
1720c87b03e5Sespie
1721c87b03e5Sespie if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
1722c87b03e5Sespie {
1723c87b03e5Sespie fprintf (outf, ";; End of basic block %d, registers live:\n",
1724c87b03e5Sespie bb->index);
1725c87b03e5Sespie dump_regset (bb->global_live_at_end, outf);
1726c87b03e5Sespie putc ('\n', outf);
1727c87b03e5Sespie }
1728c87b03e5Sespie
1729c87b03e5Sespie if (did_output)
1730c87b03e5Sespie putc ('\n', outf);
1731c87b03e5Sespie }
1732c87b03e5Sespie
1733c87b03e5Sespie free (start);
1734c87b03e5Sespie free (end);
1735c87b03e5Sespie free (in_bb_p);
1736c87b03e5Sespie }
1737c87b03e5Sespie
1738c87b03e5Sespie if (current_function_epilogue_delay_list != 0)
1739c87b03e5Sespie {
1740c87b03e5Sespie fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
1741c87b03e5Sespie for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0;
1742c87b03e5Sespie tmp_rtx = XEXP (tmp_rtx, 1))
1743c87b03e5Sespie print_rtl_single (outf, XEXP (tmp_rtx, 0));
1744c87b03e5Sespie }
1745c87b03e5Sespie }
1746c87b03e5Sespie
1747c87b03e5Sespie void
update_br_prob_note(bb)1748c87b03e5Sespie update_br_prob_note (bb)
1749c87b03e5Sespie basic_block bb;
1750c87b03e5Sespie {
1751c87b03e5Sespie rtx note;
1752c87b03e5Sespie if (GET_CODE (bb->end) != JUMP_INSN)
1753c87b03e5Sespie return;
1754c87b03e5Sespie note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX);
1755c87b03e5Sespie if (!note || INTVAL (XEXP (note, 0)) == BRANCH_EDGE (bb)->probability)
1756c87b03e5Sespie return;
1757c87b03e5Sespie XEXP (note, 0) = GEN_INT (BRANCH_EDGE (bb)->probability);
1758c87b03e5Sespie }
1759c87b03e5Sespie
1760c87b03e5Sespie /* Verify the CFG consistency. This function check some CFG invariants and
1761c87b03e5Sespie aborts when something is wrong. Hope that this function will help to
1762c87b03e5Sespie convert many optimization passes to preserve CFG consistent.
1763c87b03e5Sespie
1764c87b03e5Sespie Currently it does following checks:
1765c87b03e5Sespie
1766c87b03e5Sespie - test head/end pointers
1767c87b03e5Sespie - overlapping of basic blocks
1768c87b03e5Sespie - edge list correctness
1769c87b03e5Sespie - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1770c87b03e5Sespie - tails of basic blocks (ensure that boundary is necessary)
1771c87b03e5Sespie - scans body of the basic block for JUMP_INSN, CODE_LABEL
1772c87b03e5Sespie and NOTE_INSN_BASIC_BLOCK
1773c87b03e5Sespie - check that all insns are in the basic blocks
1774c87b03e5Sespie (except the switch handling code, barriers and notes)
1775c87b03e5Sespie - check that all returns are followed by barriers
1776c87b03e5Sespie
1777c87b03e5Sespie In future it can be extended check a lot of other stuff as well
1778c87b03e5Sespie (reachability of basic blocks, life information, etc. etc.). */
1779c87b03e5Sespie
1780c87b03e5Sespie void
verify_flow_info()1781c87b03e5Sespie verify_flow_info ()
1782c87b03e5Sespie {
1783c87b03e5Sespie const int max_uid = get_max_uid ();
1784c87b03e5Sespie const rtx rtx_first = get_insns ();
1785c87b03e5Sespie rtx last_head = get_last_insn ();
1786c87b03e5Sespie basic_block *bb_info, *last_visited;
1787c87b03e5Sespie size_t *edge_checksum;
1788c87b03e5Sespie rtx x;
1789c87b03e5Sespie int num_bb_notes, err = 0;
1790c87b03e5Sespie basic_block bb, last_bb_seen;
1791c87b03e5Sespie
1792c87b03e5Sespie bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1793c87b03e5Sespie last_visited = (basic_block *) xcalloc (last_basic_block + 2,
1794c87b03e5Sespie sizeof (basic_block));
1795c87b03e5Sespie edge_checksum = (size_t *) xcalloc (last_basic_block + 2, sizeof (size_t));
1796c87b03e5Sespie
1797c87b03e5Sespie /* Check bb chain & numbers. */
1798c87b03e5Sespie last_bb_seen = ENTRY_BLOCK_PTR;
1799c87b03e5Sespie FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
1800c87b03e5Sespie {
1801c87b03e5Sespie if (bb != EXIT_BLOCK_PTR
1802c87b03e5Sespie && bb != BASIC_BLOCK (bb->index))
1803c87b03e5Sespie {
1804c87b03e5Sespie error ("bb %d on wrong place", bb->index);
1805c87b03e5Sespie err = 1;
1806c87b03e5Sespie }
1807c87b03e5Sespie
1808c87b03e5Sespie if (bb->prev_bb != last_bb_seen)
1809c87b03e5Sespie {
1810c87b03e5Sespie error ("prev_bb of %d should be %d, not %d",
1811c87b03e5Sespie bb->index, last_bb_seen->index, bb->prev_bb->index);
1812c87b03e5Sespie err = 1;
1813c87b03e5Sespie }
1814c87b03e5Sespie
1815c87b03e5Sespie last_bb_seen = bb;
1816c87b03e5Sespie }
1817c87b03e5Sespie
1818c87b03e5Sespie FOR_EACH_BB_REVERSE (bb)
1819c87b03e5Sespie {
1820c87b03e5Sespie rtx head = bb->head;
1821c87b03e5Sespie rtx end = bb->end;
1822c87b03e5Sespie
1823c87b03e5Sespie /* Verify the end of the basic block is in the INSN chain. */
1824c87b03e5Sespie for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
1825c87b03e5Sespie if (x == end)
1826c87b03e5Sespie break;
1827c87b03e5Sespie
1828c87b03e5Sespie if (!x)
1829c87b03e5Sespie {
1830c87b03e5Sespie error ("end insn %d for block %d not found in the insn stream",
1831c87b03e5Sespie INSN_UID (end), bb->index);
1832c87b03e5Sespie err = 1;
1833c87b03e5Sespie }
1834c87b03e5Sespie
1835c87b03e5Sespie /* Work backwards from the end to the head of the basic block
1836c87b03e5Sespie to verify the head is in the RTL chain. */
1837c87b03e5Sespie for (; x != NULL_RTX; x = PREV_INSN (x))
1838c87b03e5Sespie {
1839c87b03e5Sespie /* While walking over the insn chain, verify insns appear
1840c87b03e5Sespie in only one basic block and initialize the BB_INFO array
1841c87b03e5Sespie used by other passes. */
1842c87b03e5Sespie if (bb_info[INSN_UID (x)] != NULL)
1843c87b03e5Sespie {
1844c87b03e5Sespie error ("insn %d is in multiple basic blocks (%d and %d)",
1845c87b03e5Sespie INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
1846c87b03e5Sespie err = 1;
1847c87b03e5Sespie }
1848c87b03e5Sespie
1849c87b03e5Sespie bb_info[INSN_UID (x)] = bb;
1850c87b03e5Sespie
1851c87b03e5Sespie if (x == head)
1852c87b03e5Sespie break;
1853c87b03e5Sespie }
1854c87b03e5Sespie if (!x)
1855c87b03e5Sespie {
1856c87b03e5Sespie error ("head insn %d for block %d not found in the insn stream",
1857c87b03e5Sespie INSN_UID (head), bb->index);
1858c87b03e5Sespie err = 1;
1859c87b03e5Sespie }
1860c87b03e5Sespie
1861c87b03e5Sespie last_head = x;
1862c87b03e5Sespie }
1863c87b03e5Sespie
1864c87b03e5Sespie /* Now check the basic blocks (boundaries etc.) */
1865c87b03e5Sespie FOR_EACH_BB_REVERSE (bb)
1866c87b03e5Sespie {
1867c87b03e5Sespie int n_fallthru = 0, n_eh = 0, n_call = 0, n_abnormal = 0, n_branch = 0;
1868c87b03e5Sespie edge e;
1869c87b03e5Sespie rtx note;
1870c87b03e5Sespie
1871c87b03e5Sespie if (INSN_P (bb->end)
1872c87b03e5Sespie && (note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX))
1873c87b03e5Sespie && bb->succ && bb->succ->succ_next
1874c87b03e5Sespie && any_condjump_p (bb->end))
1875c87b03e5Sespie {
1876c87b03e5Sespie if (INTVAL (XEXP (note, 0)) != BRANCH_EDGE (bb)->probability)
1877c87b03e5Sespie {
1878c87b03e5Sespie error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
1879c87b03e5Sespie INTVAL (XEXP (note, 0)), BRANCH_EDGE (bb)->probability);
1880c87b03e5Sespie err = 1;
1881c87b03e5Sespie }
1882c87b03e5Sespie }
1883c87b03e5Sespie if (bb->count < 0)
1884c87b03e5Sespie {
1885c87b03e5Sespie error ("verify_flow_info: Wrong count of block %i %i",
1886c87b03e5Sespie bb->index, (int)bb->count);
1887c87b03e5Sespie err = 1;
1888c87b03e5Sespie }
1889c87b03e5Sespie if (bb->frequency < 0)
1890c87b03e5Sespie {
1891c87b03e5Sespie error ("verify_flow_info: Wrong frequency of block %i %i",
1892c87b03e5Sespie bb->index, bb->frequency);
1893c87b03e5Sespie err = 1;
1894c87b03e5Sespie }
1895c87b03e5Sespie for (e = bb->succ; e; e = e->succ_next)
1896c87b03e5Sespie {
1897c87b03e5Sespie if (last_visited [e->dest->index + 2] == bb)
1898c87b03e5Sespie {
1899c87b03e5Sespie error ("verify_flow_info: Duplicate edge %i->%i",
1900c87b03e5Sespie e->src->index, e->dest->index);
1901c87b03e5Sespie err = 1;
1902c87b03e5Sespie }
1903c87b03e5Sespie if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
1904c87b03e5Sespie {
1905c87b03e5Sespie error ("verify_flow_info: Wrong probability of edge %i->%i %i",
1906c87b03e5Sespie e->src->index, e->dest->index, e->probability);
1907c87b03e5Sespie err = 1;
1908c87b03e5Sespie }
1909c87b03e5Sespie if (e->count < 0)
1910c87b03e5Sespie {
1911c87b03e5Sespie error ("verify_flow_info: Wrong count of edge %i->%i %i",
1912c87b03e5Sespie e->src->index, e->dest->index, (int)e->count);
1913c87b03e5Sespie err = 1;
1914c87b03e5Sespie }
1915c87b03e5Sespie
1916c87b03e5Sespie last_visited [e->dest->index + 2] = bb;
1917c87b03e5Sespie
1918c87b03e5Sespie if (e->flags & EDGE_FALLTHRU)
1919c87b03e5Sespie n_fallthru++;
1920c87b03e5Sespie
1921c87b03e5Sespie if ((e->flags & ~EDGE_DFS_BACK) == 0)
1922c87b03e5Sespie n_branch++;
1923c87b03e5Sespie
1924c87b03e5Sespie if (e->flags & EDGE_ABNORMAL_CALL)
1925c87b03e5Sespie n_call++;
1926c87b03e5Sespie
1927c87b03e5Sespie if (e->flags & EDGE_EH)
1928c87b03e5Sespie n_eh++;
1929c87b03e5Sespie else if (e->flags & EDGE_ABNORMAL)
1930c87b03e5Sespie n_abnormal++;
1931c87b03e5Sespie
1932c87b03e5Sespie if ((e->flags & EDGE_FALLTHRU)
1933c87b03e5Sespie && e->src != ENTRY_BLOCK_PTR
1934c87b03e5Sespie && e->dest != EXIT_BLOCK_PTR)
1935c87b03e5Sespie {
1936c87b03e5Sespie rtx insn;
1937c87b03e5Sespie
1938c87b03e5Sespie if (e->src->next_bb != e->dest)
1939c87b03e5Sespie {
1940c87b03e5Sespie error
1941c87b03e5Sespie ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
1942c87b03e5Sespie e->src->index, e->dest->index);
1943c87b03e5Sespie err = 1;
1944c87b03e5Sespie }
1945c87b03e5Sespie else
1946c87b03e5Sespie for (insn = NEXT_INSN (e->src->end); insn != e->dest->head;
1947c87b03e5Sespie insn = NEXT_INSN (insn))
1948c87b03e5Sespie if (GET_CODE (insn) == BARRIER
1949c87b03e5Sespie #ifndef CASE_DROPS_THROUGH
1950c87b03e5Sespie || INSN_P (insn)
1951c87b03e5Sespie #else
1952c87b03e5Sespie || (INSN_P (insn) && ! JUMP_TABLE_DATA_P (insn))
1953c87b03e5Sespie #endif
1954c87b03e5Sespie )
1955c87b03e5Sespie {
1956c87b03e5Sespie error ("verify_flow_info: Incorrect fallthru %i->%i",
1957c87b03e5Sespie e->src->index, e->dest->index);
1958c87b03e5Sespie fatal_insn ("wrong insn in the fallthru edge", insn);
1959c87b03e5Sespie err = 1;
1960c87b03e5Sespie }
1961c87b03e5Sespie }
1962c87b03e5Sespie
1963c87b03e5Sespie if (e->src != bb)
1964c87b03e5Sespie {
1965c87b03e5Sespie error ("verify_flow_info: Basic block %d succ edge is corrupted",
1966c87b03e5Sespie bb->index);
1967c87b03e5Sespie fprintf (stderr, "Predecessor: ");
1968c87b03e5Sespie dump_edge_info (stderr, e, 0);
1969c87b03e5Sespie fprintf (stderr, "\nSuccessor: ");
1970c87b03e5Sespie dump_edge_info (stderr, e, 1);
1971c87b03e5Sespie fprintf (stderr, "\n");
1972c87b03e5Sespie err = 1;
1973c87b03e5Sespie }
1974c87b03e5Sespie
1975c87b03e5Sespie edge_checksum[e->dest->index + 2] += (size_t) e;
1976c87b03e5Sespie }
1977c87b03e5Sespie
1978c87b03e5Sespie if (n_eh && GET_CODE (PATTERN (bb->end)) != RESX
1979c87b03e5Sespie && !find_reg_note (bb->end, REG_EH_REGION, NULL_RTX))
1980c87b03e5Sespie {
1981c87b03e5Sespie error ("Missing REG_EH_REGION note in the end of bb %i", bb->index);
1982c87b03e5Sespie err = 1;
1983c87b03e5Sespie }
1984c87b03e5Sespie if (n_branch
1985c87b03e5Sespie && (GET_CODE (bb->end) != JUMP_INSN
1986c87b03e5Sespie || (n_branch > 1 && (any_uncondjump_p (bb->end)
1987c87b03e5Sespie || any_condjump_p (bb->end)))))
1988c87b03e5Sespie {
1989c87b03e5Sespie error ("Too many outgoing branch edges from bb %i", bb->index);
1990c87b03e5Sespie err = 1;
1991c87b03e5Sespie }
1992c87b03e5Sespie if (n_fallthru && any_uncondjump_p (bb->end))
1993c87b03e5Sespie {
1994c87b03e5Sespie error ("Fallthru edge after unconditional jump %i", bb->index);
1995c87b03e5Sespie err = 1;
1996c87b03e5Sespie }
1997c87b03e5Sespie if (n_branch != 1 && any_uncondjump_p (bb->end))
1998c87b03e5Sespie {
1999c87b03e5Sespie error ("Wrong amount of branch edges after unconditional jump %i", bb->index);
2000c87b03e5Sespie err = 1;
2001c87b03e5Sespie }
2002c87b03e5Sespie if (n_branch != 1 && any_condjump_p (bb->end)
2003c87b03e5Sespie && JUMP_LABEL (bb->end) != bb->next_bb->head)
2004c87b03e5Sespie {
2005c87b03e5Sespie error ("Wrong amount of branch edges after conditional jump %i", bb->index);
2006c87b03e5Sespie err = 1;
2007c87b03e5Sespie }
2008c87b03e5Sespie if (n_call && GET_CODE (bb->end) != CALL_INSN)
2009c87b03e5Sespie {
2010c87b03e5Sespie error ("Call edges for non-call insn in bb %i", bb->index);
2011c87b03e5Sespie err = 1;
2012c87b03e5Sespie }
2013c87b03e5Sespie if (n_abnormal
2014c87b03e5Sespie && (GET_CODE (bb->end) != CALL_INSN && n_call != n_abnormal)
2015c87b03e5Sespie && (GET_CODE (bb->end) != JUMP_INSN
2016c87b03e5Sespie || any_condjump_p (bb->end)
2017c87b03e5Sespie || any_uncondjump_p (bb->end)))
2018c87b03e5Sespie {
2019c87b03e5Sespie error ("Abnormal edges for no purpose in bb %i", bb->index);
2020c87b03e5Sespie err = 1;
2021c87b03e5Sespie }
2022c87b03e5Sespie
2023c87b03e5Sespie if (!n_fallthru)
2024c87b03e5Sespie {
2025c87b03e5Sespie rtx insn;
2026c87b03e5Sespie
2027c87b03e5Sespie /* Ensure existence of barrier in BB with no fallthru edges. */
2028c87b03e5Sespie for (insn = bb->end; !insn || GET_CODE (insn) != BARRIER;
2029c87b03e5Sespie insn = NEXT_INSN (insn))
2030c87b03e5Sespie if (!insn
2031c87b03e5Sespie || (GET_CODE (insn) == NOTE
2032c87b03e5Sespie && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK))
2033c87b03e5Sespie {
2034c87b03e5Sespie error ("missing barrier after block %i", bb->index);
2035c87b03e5Sespie err = 1;
2036c87b03e5Sespie break;
2037c87b03e5Sespie }
2038c87b03e5Sespie }
2039c87b03e5Sespie
2040c87b03e5Sespie for (e = bb->pred; e; e = e->pred_next)
2041c87b03e5Sespie {
2042c87b03e5Sespie if (e->dest != bb)
2043c87b03e5Sespie {
2044c87b03e5Sespie error ("basic block %d pred edge is corrupted", bb->index);
2045c87b03e5Sespie fputs ("Predecessor: ", stderr);
2046c87b03e5Sespie dump_edge_info (stderr, e, 0);
2047c87b03e5Sespie fputs ("\nSuccessor: ", stderr);
2048c87b03e5Sespie dump_edge_info (stderr, e, 1);
2049c87b03e5Sespie fputc ('\n', stderr);
2050c87b03e5Sespie err = 1;
2051c87b03e5Sespie }
2052c87b03e5Sespie edge_checksum[e->dest->index + 2] -= (size_t) e;
2053c87b03e5Sespie }
2054c87b03e5Sespie
2055c87b03e5Sespie for (x = bb->head; x != NEXT_INSN (bb->end); x = NEXT_INSN (x))
2056c87b03e5Sespie if (BLOCK_FOR_INSN (x) != bb)
2057c87b03e5Sespie {
2058c87b03e5Sespie debug_rtx (x);
2059c87b03e5Sespie if (! BLOCK_FOR_INSN (x))
2060c87b03e5Sespie error
2061c87b03e5Sespie ("insn %d inside basic block %d but block_for_insn is NULL",
2062c87b03e5Sespie INSN_UID (x), bb->index);
2063c87b03e5Sespie else
2064c87b03e5Sespie error
2065c87b03e5Sespie ("insn %d inside basic block %d but block_for_insn is %i",
2066c87b03e5Sespie INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index);
2067c87b03e5Sespie
2068c87b03e5Sespie err = 1;
2069c87b03e5Sespie }
2070c87b03e5Sespie
2071c87b03e5Sespie /* OK pointers are correct. Now check the header of basic
2072c87b03e5Sespie block. It ought to contain optional CODE_LABEL followed
2073c87b03e5Sespie by NOTE_BASIC_BLOCK. */
2074c87b03e5Sespie x = bb->head;
2075c87b03e5Sespie if (GET_CODE (x) == CODE_LABEL)
2076c87b03e5Sespie {
2077c87b03e5Sespie if (bb->end == x)
2078c87b03e5Sespie {
2079c87b03e5Sespie error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2080c87b03e5Sespie bb->index);
2081c87b03e5Sespie err = 1;
2082c87b03e5Sespie }
2083c87b03e5Sespie
2084c87b03e5Sespie x = NEXT_INSN (x);
2085c87b03e5Sespie }
2086c87b03e5Sespie
2087c87b03e5Sespie if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
2088c87b03e5Sespie {
2089c87b03e5Sespie error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2090c87b03e5Sespie bb->index);
2091c87b03e5Sespie err = 1;
2092c87b03e5Sespie }
2093c87b03e5Sespie
2094c87b03e5Sespie if (bb->end == x)
2095c87b03e5Sespie /* Do checks for empty blocks her. e */
2096c87b03e5Sespie ;
2097c87b03e5Sespie else
2098c87b03e5Sespie for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
2099c87b03e5Sespie {
2100c87b03e5Sespie if (NOTE_INSN_BASIC_BLOCK_P (x))
2101c87b03e5Sespie {
2102c87b03e5Sespie error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2103c87b03e5Sespie INSN_UID (x), bb->index);
2104c87b03e5Sespie err = 1;
2105c87b03e5Sespie }
2106c87b03e5Sespie
2107c87b03e5Sespie if (x == bb->end)
2108c87b03e5Sespie break;
2109c87b03e5Sespie
2110c87b03e5Sespie if (GET_CODE (x) == JUMP_INSN
2111c87b03e5Sespie || GET_CODE (x) == CODE_LABEL
2112c87b03e5Sespie || GET_CODE (x) == BARRIER)
2113c87b03e5Sespie {
2114c87b03e5Sespie error ("in basic block %d:", bb->index);
2115c87b03e5Sespie fatal_insn ("flow control insn inside a basic block", x);
2116c87b03e5Sespie }
2117c87b03e5Sespie }
2118c87b03e5Sespie }
2119c87b03e5Sespie
2120c87b03e5Sespie /* Complete edge checksumming for ENTRY and EXIT. */
2121c87b03e5Sespie {
2122c87b03e5Sespie edge e;
2123c87b03e5Sespie
2124c87b03e5Sespie for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
2125c87b03e5Sespie edge_checksum[e->dest->index + 2] += (size_t) e;
2126c87b03e5Sespie
2127c87b03e5Sespie for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
2128c87b03e5Sespie edge_checksum[e->dest->index + 2] -= (size_t) e;
2129c87b03e5Sespie }
2130c87b03e5Sespie
2131c87b03e5Sespie FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2132c87b03e5Sespie if (edge_checksum[bb->index + 2])
2133c87b03e5Sespie {
2134c87b03e5Sespie error ("basic block %i edge lists are corrupted", bb->index);
2135c87b03e5Sespie err = 1;
2136c87b03e5Sespie }
2137c87b03e5Sespie
2138c87b03e5Sespie num_bb_notes = 0;
2139c87b03e5Sespie last_bb_seen = ENTRY_BLOCK_PTR;
2140c87b03e5Sespie
2141c87b03e5Sespie for (x = rtx_first; x; x = NEXT_INSN (x))
2142c87b03e5Sespie {
2143c87b03e5Sespie if (NOTE_INSN_BASIC_BLOCK_P (x))
2144c87b03e5Sespie {
2145c87b03e5Sespie bb = NOTE_BASIC_BLOCK (x);
2146c87b03e5Sespie
2147c87b03e5Sespie num_bb_notes++;
2148c87b03e5Sespie if (bb != last_bb_seen->next_bb)
2149c87b03e5Sespie internal_error ("basic blocks not numbered consecutively");
2150c87b03e5Sespie
2151c87b03e5Sespie last_bb_seen = bb;
2152c87b03e5Sespie }
2153c87b03e5Sespie
2154c87b03e5Sespie if (!bb_info[INSN_UID (x)])
2155c87b03e5Sespie {
2156c87b03e5Sespie switch (GET_CODE (x))
2157c87b03e5Sespie {
2158c87b03e5Sespie case BARRIER:
2159c87b03e5Sespie case NOTE:
2160c87b03e5Sespie break;
2161c87b03e5Sespie
2162c87b03e5Sespie case CODE_LABEL:
2163c87b03e5Sespie /* An addr_vec is placed outside any block block. */
2164c87b03e5Sespie if (NEXT_INSN (x)
2165c87b03e5Sespie && GET_CODE (NEXT_INSN (x)) == JUMP_INSN
2166c87b03e5Sespie && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
2167c87b03e5Sespie || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
2168c87b03e5Sespie x = NEXT_INSN (x);
2169c87b03e5Sespie
2170c87b03e5Sespie /* But in any case, non-deletable labels can appear anywhere. */
2171c87b03e5Sespie break;
2172c87b03e5Sespie
2173c87b03e5Sespie default:
2174c87b03e5Sespie fatal_insn ("insn outside basic block", x);
2175c87b03e5Sespie }
2176c87b03e5Sespie }
2177c87b03e5Sespie
2178c87b03e5Sespie if (INSN_P (x)
2179c87b03e5Sespie && GET_CODE (x) == JUMP_INSN
2180c87b03e5Sespie && returnjump_p (x) && ! condjump_p (x)
2181c87b03e5Sespie && ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER))
2182c87b03e5Sespie fatal_insn ("return not followed by barrier", x);
2183c87b03e5Sespie }
2184c87b03e5Sespie
2185c87b03e5Sespie if (num_bb_notes != n_basic_blocks)
2186c87b03e5Sespie internal_error
2187c87b03e5Sespie ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2188c87b03e5Sespie num_bb_notes, n_basic_blocks);
2189c87b03e5Sespie
2190c87b03e5Sespie if (err)
2191c87b03e5Sespie internal_error ("verify_flow_info failed");
2192c87b03e5Sespie
2193c87b03e5Sespie /* Clean up. */
2194c87b03e5Sespie free (bb_info);
2195c87b03e5Sespie free (last_visited);
2196c87b03e5Sespie free (edge_checksum);
2197c87b03e5Sespie }
2198c87b03e5Sespie
2199c87b03e5Sespie /* Assume that the preceding pass has possibly eliminated jump instructions
2200c87b03e5Sespie or converted the unconditional jumps. Eliminate the edges from CFG.
2201c87b03e5Sespie Return true if any edges are eliminated. */
2202c87b03e5Sespie
2203c87b03e5Sespie bool
purge_dead_edges(bb)2204c87b03e5Sespie purge_dead_edges (bb)
2205c87b03e5Sespie basic_block bb;
2206c87b03e5Sespie {
2207c87b03e5Sespie edge e, next;
2208c87b03e5Sespie rtx insn = bb->end, note;
2209c87b03e5Sespie bool purged = false;
2210c87b03e5Sespie
2211c87b03e5Sespie /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2212c87b03e5Sespie if (GET_CODE (insn) == INSN
2213c87b03e5Sespie && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
2214c87b03e5Sespie {
2215c87b03e5Sespie rtx eqnote;
2216c87b03e5Sespie
2217c87b03e5Sespie if (! may_trap_p (PATTERN (insn))
2218c87b03e5Sespie || ((eqnote = find_reg_equal_equiv_note (insn))
2219c87b03e5Sespie && ! may_trap_p (XEXP (eqnote, 0))))
2220c87b03e5Sespie remove_note (insn, note);
2221c87b03e5Sespie }
2222c87b03e5Sespie
2223c87b03e5Sespie /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
2224c87b03e5Sespie for (e = bb->succ; e; e = next)
2225c87b03e5Sespie {
2226c87b03e5Sespie next = e->succ_next;
2227c87b03e5Sespie if (e->flags & EDGE_EH)
2228c87b03e5Sespie {
2229c87b03e5Sespie if (can_throw_internal (bb->end))
2230c87b03e5Sespie continue;
2231c87b03e5Sespie }
2232c87b03e5Sespie else if (e->flags & EDGE_ABNORMAL_CALL)
2233c87b03e5Sespie {
2234c87b03e5Sespie if (GET_CODE (bb->end) == CALL_INSN
2235c87b03e5Sespie && (! (note = find_reg_note (insn, REG_EH_REGION, NULL))
2236c87b03e5Sespie || INTVAL (XEXP (note, 0)) >= 0))
2237c87b03e5Sespie continue;
2238c87b03e5Sespie }
2239c87b03e5Sespie else
2240c87b03e5Sespie continue;
2241c87b03e5Sespie
2242c87b03e5Sespie remove_edge (e);
2243c87b03e5Sespie bb->flags |= BB_DIRTY;
2244c87b03e5Sespie purged = true;
2245c87b03e5Sespie }
2246c87b03e5Sespie
2247c87b03e5Sespie if (GET_CODE (insn) == JUMP_INSN)
2248c87b03e5Sespie {
2249c87b03e5Sespie rtx note;
2250c87b03e5Sespie edge b,f;
2251c87b03e5Sespie
2252c87b03e5Sespie /* We do care only about conditional jumps and simplejumps. */
2253c87b03e5Sespie if (!any_condjump_p (insn)
2254c87b03e5Sespie && !returnjump_p (insn)
2255c87b03e5Sespie && !simplejump_p (insn))
2256c87b03e5Sespie return purged;
2257c87b03e5Sespie
2258c87b03e5Sespie /* Branch probability/prediction notes are defined only for
2259c87b03e5Sespie condjumps. We've possibly turned condjump into simplejump. */
2260c87b03e5Sespie if (simplejump_p (insn))
2261c87b03e5Sespie {
2262c87b03e5Sespie note = find_reg_note (insn, REG_BR_PROB, NULL);
2263c87b03e5Sespie if (note)
2264c87b03e5Sespie remove_note (insn, note);
2265c87b03e5Sespie while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
2266c87b03e5Sespie remove_note (insn, note);
2267c87b03e5Sespie }
2268c87b03e5Sespie
2269c87b03e5Sespie for (e = bb->succ; e; e = next)
2270c87b03e5Sespie {
2271c87b03e5Sespie next = e->succ_next;
2272c87b03e5Sespie
2273c87b03e5Sespie /* Avoid abnormal flags to leak from computed jumps turned
2274c87b03e5Sespie into simplejumps. */
2275c87b03e5Sespie
2276c87b03e5Sespie e->flags &= ~EDGE_ABNORMAL;
2277c87b03e5Sespie
2278c87b03e5Sespie /* See if this edge is one we should keep. */
2279c87b03e5Sespie if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
2280c87b03e5Sespie /* A conditional jump can fall through into the next
2281c87b03e5Sespie block, so we should keep the edge. */
2282c87b03e5Sespie continue;
2283c87b03e5Sespie else if (e->dest != EXIT_BLOCK_PTR
2284c87b03e5Sespie && e->dest->head == JUMP_LABEL (insn))
2285c87b03e5Sespie /* If the destination block is the target of the jump,
2286c87b03e5Sespie keep the edge. */
2287c87b03e5Sespie continue;
2288c87b03e5Sespie else if (e->dest == EXIT_BLOCK_PTR && returnjump_p (insn))
2289c87b03e5Sespie /* If the destination block is the exit block, and this
2290c87b03e5Sespie instruction is a return, then keep the edge. */
2291c87b03e5Sespie continue;
2292c87b03e5Sespie else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
2293c87b03e5Sespie /* Keep the edges that correspond to exceptions thrown by
2294c87b03e5Sespie this instruction and rematerialize the EDGE_ABNORMAL flag
2295c87b03e5Sespie we just cleared above. */
2296c87b03e5Sespie {
2297c87b03e5Sespie e->flags |= EDGE_ABNORMAL;
2298c87b03e5Sespie continue;
2299c87b03e5Sespie }
2300c87b03e5Sespie
2301c87b03e5Sespie /* We do not need this edge. */
2302c87b03e5Sespie bb->flags |= BB_DIRTY;
2303c87b03e5Sespie purged = true;
2304c87b03e5Sespie remove_edge (e);
2305c87b03e5Sespie }
2306c87b03e5Sespie
2307c87b03e5Sespie if (!bb->succ || !purged)
2308c87b03e5Sespie return purged;
2309c87b03e5Sespie
2310c87b03e5Sespie if (rtl_dump_file)
2311c87b03e5Sespie fprintf (rtl_dump_file, "Purged edges from bb %i\n", bb->index);
2312c87b03e5Sespie
2313c87b03e5Sespie if (!optimize)
2314c87b03e5Sespie return purged;
2315c87b03e5Sespie
2316c87b03e5Sespie /* Redistribute probabilities. */
2317c87b03e5Sespie if (!bb->succ->succ_next)
2318c87b03e5Sespie {
2319c87b03e5Sespie bb->succ->probability = REG_BR_PROB_BASE;
2320c87b03e5Sespie bb->succ->count = bb->count;
2321c87b03e5Sespie }
2322c87b03e5Sespie else
2323c87b03e5Sespie {
2324c87b03e5Sespie note = find_reg_note (insn, REG_BR_PROB, NULL);
2325c87b03e5Sespie if (!note)
2326c87b03e5Sespie return purged;
2327c87b03e5Sespie
2328c87b03e5Sespie b = BRANCH_EDGE (bb);
2329c87b03e5Sespie f = FALLTHRU_EDGE (bb);
2330c87b03e5Sespie b->probability = INTVAL (XEXP (note, 0));
2331c87b03e5Sespie f->probability = REG_BR_PROB_BASE - b->probability;
2332c87b03e5Sespie b->count = bb->count * b->probability / REG_BR_PROB_BASE;
2333c87b03e5Sespie f->count = bb->count * f->probability / REG_BR_PROB_BASE;
2334c87b03e5Sespie }
2335c87b03e5Sespie
2336c87b03e5Sespie return purged;
2337c87b03e5Sespie }
2338c87b03e5Sespie
2339c87b03e5Sespie /* If we don't see a jump insn, we don't know exactly why the block would
2340c87b03e5Sespie have been broken at this point. Look for a simple, non-fallthru edge,
2341c87b03e5Sespie as these are only created by conditional branches. If we find such an
2342c87b03e5Sespie edge we know that there used to be a jump here and can then safely
2343c87b03e5Sespie remove all non-fallthru edges. */
2344c87b03e5Sespie for (e = bb->succ; e && (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU));
2345c87b03e5Sespie e = e->succ_next)
2346c87b03e5Sespie ;
2347c87b03e5Sespie
2348c87b03e5Sespie if (!e)
2349c87b03e5Sespie return purged;
2350c87b03e5Sespie
2351c87b03e5Sespie for (e = bb->succ; e; e = next)
2352c87b03e5Sespie {
2353c87b03e5Sespie next = e->succ_next;
2354c87b03e5Sespie if (!(e->flags & EDGE_FALLTHRU))
2355c87b03e5Sespie {
2356c87b03e5Sespie bb->flags |= BB_DIRTY;
2357c87b03e5Sespie remove_edge (e);
2358c87b03e5Sespie purged = true;
2359c87b03e5Sespie }
2360c87b03e5Sespie }
2361c87b03e5Sespie
2362c87b03e5Sespie if (!bb->succ || bb->succ->succ_next)
2363c87b03e5Sespie abort ();
2364c87b03e5Sespie
2365c87b03e5Sespie bb->succ->probability = REG_BR_PROB_BASE;
2366c87b03e5Sespie bb->succ->count = bb->count;
2367c87b03e5Sespie
2368c87b03e5Sespie if (rtl_dump_file)
2369c87b03e5Sespie fprintf (rtl_dump_file, "Purged non-fallthru edges from bb %i\n",
2370c87b03e5Sespie bb->index);
2371c87b03e5Sespie return purged;
2372c87b03e5Sespie }
2373c87b03e5Sespie
2374c87b03e5Sespie /* Search all basic blocks for potentially dead edges and purge them. Return
2375c87b03e5Sespie true if some edge has been eliminated. */
2376c87b03e5Sespie
2377c87b03e5Sespie bool
purge_all_dead_edges(update_life_p)2378c87b03e5Sespie purge_all_dead_edges (update_life_p)
2379c87b03e5Sespie int update_life_p;
2380c87b03e5Sespie {
2381c87b03e5Sespie int purged = false;
2382c87b03e5Sespie sbitmap blocks = 0;
2383c87b03e5Sespie basic_block bb;
2384c87b03e5Sespie
2385c87b03e5Sespie if (update_life_p)
2386c87b03e5Sespie {
2387c87b03e5Sespie blocks = sbitmap_alloc (last_basic_block);
2388c87b03e5Sespie sbitmap_zero (blocks);
2389c87b03e5Sespie }
2390c87b03e5Sespie
2391c87b03e5Sespie FOR_EACH_BB (bb)
2392c87b03e5Sespie {
2393c87b03e5Sespie bool purged_here = purge_dead_edges (bb);
2394c87b03e5Sespie
2395c87b03e5Sespie purged |= purged_here;
2396c87b03e5Sespie if (purged_here && update_life_p)
2397c87b03e5Sespie SET_BIT (blocks, bb->index);
2398c87b03e5Sespie }
2399c87b03e5Sespie
2400c87b03e5Sespie if (update_life_p && purged)
2401c87b03e5Sespie update_life_info (blocks, UPDATE_LIFE_GLOBAL,
2402c87b03e5Sespie PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
2403c87b03e5Sespie | PROP_KILL_DEAD_CODE);
2404c87b03e5Sespie
2405c87b03e5Sespie if (update_life_p)
2406c87b03e5Sespie sbitmap_free (blocks);
2407c87b03e5Sespie return purged;
2408c87b03e5Sespie }
2409