1 /* Define control and data flow tables, and regsets.
2 Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 #ifndef GCC_BASIC_BLOCK_H
23 #define GCC_BASIC_BLOCK_H
28 #include "partition.h"
29 #include "hard-reg-set.h"
34 /* Head of register set linked list. */
35 typedef bitmap_head regset_head;
37 /* A pointer to a regset_head. */
38 typedef bitmap regset;
40 /* Allocate a register set with oballoc. */
41 #define ALLOC_REG_SET(OBSTACK) BITMAP_ALLOC (OBSTACK)
43 /* Do any cleanup needed on a regset when it is no longer used. */
44 #define FREE_REG_SET(REGSET) BITMAP_FREE (REGSET)
46 /* Initialize a new regset. */
47 #define INIT_REG_SET(HEAD) bitmap_initialize (HEAD, ®_obstack)
49 /* Clear a register set by freeing up the linked list. */
50 #define CLEAR_REG_SET(HEAD) bitmap_clear (HEAD)
52 /* Copy a register set to another register set. */
53 #define COPY_REG_SET(TO, FROM) bitmap_copy (TO, FROM)
55 /* Compare two register sets. */
56 #define REG_SET_EQUAL_P(A, B) bitmap_equal_p (A, B)
58 /* `and' a register set with a second register set. */
59 #define AND_REG_SET(TO, FROM) bitmap_and_into (TO, FROM)
61 /* `and' the complement of a register set with a register set. */
62 #define AND_COMPL_REG_SET(TO, FROM) bitmap_and_compl_into (TO, FROM)
64 /* Inclusive or a register set with a second register set. */
65 #define IOR_REG_SET(TO, FROM) bitmap_ior_into (TO, FROM)
67 /* Exclusive or a register set with a second register set. */
68 #define XOR_REG_SET(TO, FROM) bitmap_xor_into (TO, FROM)
70 /* Or into TO the register set FROM1 `and'ed with the complement of FROM2. */
71 #define IOR_AND_COMPL_REG_SET(TO, FROM1, FROM2) \
72 bitmap_ior_and_compl_into (TO, FROM1, FROM2)
74 /* Clear a single register in a register set. */
75 #define CLEAR_REGNO_REG_SET(HEAD, REG) bitmap_clear_bit (HEAD, REG)
77 /* Set a single register in a register set. */
78 #define SET_REGNO_REG_SET(HEAD, REG) bitmap_set_bit (HEAD, REG)
80 /* Return true if a register is set in a register set. */
81 #define REGNO_REG_SET_P(TO, REG) bitmap_bit_p (TO, REG)
83 /* Copy the hard registers in a register set to the hard register set. */
84 extern void reg_set_to_hard_reg_set (HARD_REG_SET *, bitmap);
85 #define REG_SET_TO_HARD_REG_SET(TO, FROM) \
87 CLEAR_HARD_REG_SET (TO); \
88 reg_set_to_hard_reg_set (&TO, FROM); \
91 typedef bitmap_iterator reg_set_iterator;
93 /* Loop over all registers in REGSET, starting with MIN, setting REGNUM to the
94 register number and executing CODE for all registers that are set. */
95 #define EXECUTE_IF_SET_IN_REG_SET(REGSET, MIN, REGNUM, RSI) \
96 EXECUTE_IF_SET_IN_BITMAP (REGSET, MIN, REGNUM, RSI)
98 /* Loop over all registers in REGSET1 and REGSET2, starting with MIN, setting
99 REGNUM to the register number and executing CODE for all registers that are
100 set in the first regset and not set in the second. */
101 #define EXECUTE_IF_AND_COMPL_IN_REG_SET(REGSET1, REGSET2, MIN, REGNUM, RSI) \
102 EXECUTE_IF_AND_COMPL_IN_BITMAP (REGSET1, REGSET2, MIN, REGNUM, RSI)
104 /* Loop over all registers in REGSET1 and REGSET2, starting with MIN, setting
105 REGNUM to the register number and executing CODE for all registers that are
106 set in both regsets. */
107 #define EXECUTE_IF_AND_IN_REG_SET(REGSET1, REGSET2, MIN, REGNUM, RSI) \
108 EXECUTE_IF_AND_IN_BITMAP (REGSET1, REGSET2, MIN, REGNUM, RSI) \
110 /* Type we use to hold basic block counters. Should be at least
111 64bit. Although a counter cannot be negative, we use a signed
112 type, because erroneous negative counts can be generated when the
113 flow graph is manipulated by various optimizations. A signed type
114 makes those easy to detect. */
115 typedef HOST_WIDEST_INT gcov_type;
117 /* Control flow edge information. */
118 struct edge_def GTY(())
120 /* The two blocks at the ends of the edge. */
121 struct basic_block_def *src;
122 struct basic_block_def *dest;
124 /* Instructions queued on the edge. */
125 union edge_def_insns {
126 tree GTY ((tag ("true"))) t;
127 rtx GTY ((tag ("false"))) r;
128 } GTY ((desc ("current_ir_type () == IR_GIMPLE"))) insns;
130 /* Auxiliary info specific to a pass. */
131 PTR GTY ((skip (""))) aux;
133 /* Location of any goto implicit in the edge, during tree-ssa. */
134 source_locus goto_locus;
136 int flags; /* see EDGE_* below */
137 int probability; /* biased by REG_BR_PROB_BASE */
138 gcov_type count; /* Expected number of executions calculated
141 /* The index number corresponding to this edge in the edge vector
143 unsigned int dest_idx;
146 typedef struct edge_def *edge;
148 DEF_VEC_ALLOC_P(edge,gc);
149 DEF_VEC_ALLOC_P(edge,heap);
151 #define EDGE_FALLTHRU 1 /* 'Straight line' flow */
152 #define EDGE_ABNORMAL 2 /* Strange flow, like computed
154 #define EDGE_ABNORMAL_CALL 4 /* Call with abnormal exit
155 like an exception, or sibcall */
156 #define EDGE_EH 8 /* Exception throw */
157 #define EDGE_FAKE 16 /* Not a real edge (profile.c) */
158 #define EDGE_DFS_BACK 32 /* A backwards edge */
159 #define EDGE_CAN_FALLTHRU 64 /* Candidate for straight line
161 #define EDGE_IRREDUCIBLE_LOOP 128 /* Part of irreducible loop. */
162 #define EDGE_SIBCALL 256 /* Edge from sibcall to exit. */
163 #define EDGE_LOOP_EXIT 512 /* Exit of a loop. */
164 #define EDGE_TRUE_VALUE 1024 /* Edge taken when controlling
165 predicate is nonzero. */
166 #define EDGE_FALSE_VALUE 2048 /* Edge taken when controlling
167 predicate is zero. */
168 #define EDGE_EXECUTABLE 4096 /* Edge is executable. Only
169 valid during SSA-CCP. */
170 #define EDGE_CROSSING 8192 /* Edge crosses between hot
171 and cold sections, when we
173 #define EDGE_ALL_FLAGS 16383
175 #define EDGE_COMPLEX (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH)
177 /* Counter summary from the last set of coverage counts read by
179 extern const struct gcov_ctr_summary *profile_info;
181 /* Declared in cfgloop.h. */
184 /* Declared in tree-flow.h. */
185 struct edge_prediction;
188 /* A basic block is a sequence of instructions with only entry and
189 only one exit. If any one of the instructions are executed, they
190 will all be executed, and in sequence from first to last.
192 There may be COND_EXEC instructions in the basic block. The
193 COND_EXEC *instructions* will be executed -- but if the condition
194 is false the conditionally executed *expressions* will of course
195 not be executed. We don't consider the conditionally executed
196 expression (which might have side-effects) to be in a separate
197 basic block because the program counter will always be at the same
198 location after the COND_EXEC instruction, regardless of whether the
199 condition is true or not.
201 Basic blocks need not start with a label nor end with a jump insn.
202 For example, a previous basic block may just "conditionally fall"
203 into the succeeding basic block, and the last basic block need not
204 end with a jump insn. Block 0 is a descendant of the entry block.
206 A basic block beginning with two labels cannot have notes between
209 Data for jump tables are stored in jump_insns that occur in no
210 basic block even though these insns can follow or precede insns in
213 /* Basic block information indexed by block number. */
214 struct basic_block_def GTY((chain_next ("%h.next_bb"), chain_prev ("%h.prev_bb")))
216 /* Pointers to the first and last trees of the block. */
219 /* The edges into and out of the block. */
223 /* Auxiliary info specific to a pass. */
224 PTR GTY ((skip (""))) aux;
226 /* Innermost loop containing the block. */
227 struct loop * GTY ((skip (""))) loop_father;
229 /* The dominance and postdominance information node. */
230 struct et_node * GTY ((skip (""))) dom[2];
232 /* Previous and next blocks in the chain. */
233 struct basic_block_def *prev_bb;
234 struct basic_block_def *next_bb;
236 union basic_block_il_dependent {
237 struct rtl_bb_info * GTY ((tag ("1"))) rtl;
238 } GTY ((desc ("((%1.flags & BB_RTL) != 0)"))) il;
240 /* Chain of PHI nodes for this block. */
243 /* Expected number of executions: calculated in profile.c. */
246 /* The index of this block. */
249 /* The loop depth of this block. */
252 /* Expected frequency. Normalized to be in range 0 to BB_FREQ_MAX. */
255 /* Various flags. See BB_* below. */
259 struct rtl_bb_info GTY(())
261 /* The first and last insns of the block. */
265 /* The registers that are live on entry to this block. */
266 bitmap GTY ((skip (""))) global_live_at_start;
268 /* The registers that are live on exit from this block. */
269 bitmap GTY ((skip (""))) global_live_at_end;
271 /* In CFGlayout mode points to insn notes/jumptables to be placed just before
272 and after the block. */
276 /* This field is used by the bb-reorder and tracer passes. */
280 typedef struct basic_block_def *basic_block;
282 DEF_VEC_P(basic_block);
283 DEF_VEC_ALLOC_P(basic_block,gc);
284 DEF_VEC_ALLOC_P(basic_block,heap);
286 #define BB_FREQ_MAX 10000
288 /* Masks for basic_block.flags.
290 BB_HOT_PARTITION and BB_COLD_PARTITION should be preserved throughout
291 the compilation, so they are never cleared.
293 All other flags may be cleared by clear_bb_flags(). It is generally
294 a bad idea to rely on any flags being up-to-date. */
299 /* Set if insns in BB have are modified. Used for updating liveness info. */
302 /* Only set on blocks that have just been created by create_bb. */
305 /* Set by find_unreachable_blocks. Do not rely on this being set in any
309 /* Set for blocks in an irreducible loop by loop analysis. */
310 BB_IRREDUCIBLE_LOOP = 8,
312 /* Set on blocks that may actually not be single-entry single-exit block. */
315 /* Set on basic blocks that the scheduler should not touch. This is used
316 by SMS to prevent other schedulers from messing with the loop schedule. */
317 BB_DISABLE_SCHEDULE = 32,
319 /* Set on blocks that should be put in a hot section. */
320 BB_HOT_PARTITION = 64,
322 /* Set on blocks that should be put in a cold section. */
323 BB_COLD_PARTITION = 128,
325 /* Set on block that was duplicated. */
328 /* Set on blocks that are in RTL format. */
331 /* Set on blocks that are forwarder blocks.
332 Only used in cfgcleanup.c. */
333 BB_FORWARDER_BLOCK = 2048,
335 /* Set on blocks that cannot be threaded through.
336 Only used in cfgcleanup.c. */
337 BB_NONTHREADABLE_BLOCK = 4096
340 /* Dummy flag for convenience in the hot/cold partitioning code. */
341 #define BB_UNPARTITIONED 0
343 /* Partitions, to be used when partitioning hot and cold basic blocks into
344 separate sections. */
345 #define BB_PARTITION(bb) ((bb)->flags & (BB_HOT_PARTITION|BB_COLD_PARTITION))
346 #define BB_SET_PARTITION(bb, part) do { \
347 basic_block bb_ = (bb); \
348 bb_->flags = ((bb_->flags & ~(BB_HOT_PARTITION|BB_COLD_PARTITION)) \
352 #define BB_COPY_PARTITION(dstbb, srcbb) \
353 BB_SET_PARTITION (dstbb, BB_PARTITION (srcbb))
355 /* A structure to group all the per-function control flow graph data.
356 The x_* prefixing is necessary because otherwise references to the
357 fields of this struct are interpreted as the defines for backward
358 source compatibility following the definition of this struct. */
359 struct control_flow_graph GTY(())
361 /* Block pointers for the exit and entry of a function.
362 These are always the head and tail of the basic block list. */
363 basic_block x_entry_block_ptr;
364 basic_block x_exit_block_ptr;
366 /* Index by basic block number, get basic block struct info. */
367 VEC(basic_block,gc) *x_basic_block_info;
369 /* Number of basic blocks in this flow graph. */
370 int x_n_basic_blocks;
372 /* Number of edges in this flow graph. */
375 /* The first free basic block number. */
376 int x_last_basic_block;
378 /* Mapping of labels to their associated blocks. At present
379 only used for the tree CFG. */
380 VEC(basic_block,gc) *x_label_to_block_map;
382 enum profile_status {
389 /* Defines for accessing the fields of the CFG structure for function FN. */
390 #define ENTRY_BLOCK_PTR_FOR_FUNCTION(FN) ((FN)->cfg->x_entry_block_ptr)
391 #define EXIT_BLOCK_PTR_FOR_FUNCTION(FN) ((FN)->cfg->x_exit_block_ptr)
392 #define basic_block_info_for_function(FN) ((FN)->cfg->x_basic_block_info)
393 #define n_basic_blocks_for_function(FN) ((FN)->cfg->x_n_basic_blocks)
394 #define n_edges_for_function(FN) ((FN)->cfg->x_n_edges)
395 #define last_basic_block_for_function(FN) ((FN)->cfg->x_last_basic_block)
396 #define label_to_block_map_for_function(FN) ((FN)->cfg->x_label_to_block_map)
398 #define BASIC_BLOCK_FOR_FUNCTION(FN,N) \
399 (VEC_index (basic_block, basic_block_info_for_function(FN), (N)))
401 /* Defines for textual backward source compatibility. */
402 #define ENTRY_BLOCK_PTR (cfun->cfg->x_entry_block_ptr)
403 #define EXIT_BLOCK_PTR (cfun->cfg->x_exit_block_ptr)
404 #define basic_block_info (cfun->cfg->x_basic_block_info)
405 #define n_basic_blocks (cfun->cfg->x_n_basic_blocks)
406 #define n_edges (cfun->cfg->x_n_edges)
407 #define last_basic_block (cfun->cfg->x_last_basic_block)
408 #define label_to_block_map (cfun->cfg->x_label_to_block_map)
409 #define profile_status (cfun->cfg->x_profile_status)
411 #define BASIC_BLOCK(N) (VEC_index (basic_block, basic_block_info, (N)))
412 #define SET_BASIC_BLOCK(N,BB) (VEC_replace (basic_block, basic_block_info, (N), (BB)))
414 /* For iterating over basic blocks. */
415 #define FOR_BB_BETWEEN(BB, FROM, TO, DIR) \
416 for (BB = FROM; BB != TO; BB = BB->DIR)
418 #define FOR_EACH_BB_FN(BB, FN) \
419 FOR_BB_BETWEEN (BB, (FN)->cfg->x_entry_block_ptr->next_bb, (FN)->cfg->x_exit_block_ptr, next_bb)
421 #define FOR_EACH_BB(BB) FOR_EACH_BB_FN (BB, cfun)
423 #define FOR_EACH_BB_REVERSE_FN(BB, FN) \
424 FOR_BB_BETWEEN (BB, (FN)->cfg->x_exit_block_ptr->prev_bb, (FN)->cfg->x_entry_block_ptr, prev_bb)
426 #define FOR_EACH_BB_REVERSE(BB) FOR_EACH_BB_REVERSE_FN(BB, cfun)
428 /* For iterating over insns in basic block. */
429 #define FOR_BB_INSNS(BB, INSN) \
430 for ((INSN) = BB_HEAD (BB); \
431 (INSN) && (INSN) != NEXT_INSN (BB_END (BB)); \
432 (INSN) = NEXT_INSN (INSN))
434 #define FOR_BB_INSNS_REVERSE(BB, INSN) \
435 for ((INSN) = BB_END (BB); \
436 (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB)); \
437 (INSN) = PREV_INSN (INSN))
439 /* Cycles through _all_ basic blocks, even the fake ones (entry and
442 #define FOR_ALL_BB(BB) \
443 for (BB = ENTRY_BLOCK_PTR; BB; BB = BB->next_bb)
445 #define FOR_ALL_BB_FN(BB, FN) \
446 for (BB = ENTRY_BLOCK_PTR_FOR_FUNCTION (FN); BB; BB = BB->next_bb)
448 extern bitmap_obstack reg_obstack;
450 /* Indexed by n, gives number of basic block that (REG n) is used in.
451 If the value is REG_BLOCK_GLOBAL (-2),
452 it means (REG n) is used in more than one basic block.
453 REG_BLOCK_UNKNOWN (-1) means it hasn't been seen yet so we don't know.
454 This information remains valid for the rest of the compilation
455 of the current function; it is used to control register allocation. */
457 #define REG_BLOCK_UNKNOWN -1
458 #define REG_BLOCK_GLOBAL -2
460 #define REG_BASIC_BLOCK(N) \
461 (VEC_index (reg_info_p, reg_n_info, N)->basic_block)
463 /* Stuff for recording basic block info. */
465 #define BB_HEAD(B) (B)->il.rtl->head_
466 #define BB_END(B) (B)->il.rtl->end_
468 /* Special block numbers [markers] for entry and exit. */
469 #define ENTRY_BLOCK (0)
470 #define EXIT_BLOCK (1)
472 /* The two blocks that are always in the cfg. */
473 #define NUM_FIXED_BLOCKS (2)
476 #define BLOCK_NUM(INSN) (BLOCK_FOR_INSN (INSN)->index + 0)
477 #define set_block_for_insn(INSN, BB) (BLOCK_FOR_INSN (INSN) = BB)
479 extern void compute_bb_for_insn (void);
480 extern unsigned int free_bb_for_insn (void);
481 extern void update_bb_for_insn (basic_block);
483 extern void free_basic_block_vars (void);
485 extern void insert_insn_on_edge (rtx, edge);
486 basic_block split_edge_and_insert (edge, rtx);
488 extern void commit_edge_insertions (void);
490 extern void remove_fake_edges (void);
491 extern void remove_fake_exit_edges (void);
492 extern void add_noreturn_fake_exit_edges (void);
493 extern void connect_infinite_loops_to_exit (void);
494 extern edge unchecked_make_edge (basic_block, basic_block, int);
495 extern edge cached_make_edge (sbitmap, basic_block, basic_block, int);
496 extern edge make_edge (basic_block, basic_block, int);
497 extern edge make_single_succ_edge (basic_block, basic_block, int);
498 extern void remove_edge (edge);
499 extern void redirect_edge_succ (edge, basic_block);
500 extern edge redirect_edge_succ_nodup (edge, basic_block);
501 extern void redirect_edge_pred (edge, basic_block);
502 extern basic_block create_basic_block_structure (rtx, rtx, rtx, basic_block);
503 extern void clear_bb_flags (void);
504 extern int post_order_compute (int *, bool);
505 extern int pre_and_rev_post_order_compute (int *, int *, bool);
506 extern int dfs_enumerate_from (basic_block, int,
507 bool (*)(basic_block, void *),
508 basic_block *, int, void *);
509 extern void compute_dominance_frontiers (bitmap *);
510 extern void dump_bb_info (basic_block, bool, bool, int, const char *, FILE *);
511 extern void dump_edge_info (FILE *, edge, int);
512 extern void brief_dump_cfg (FILE *);
513 extern void clear_edges (void);
514 extern rtx first_insn_after_basic_block_note (basic_block);
515 extern void scale_bbs_frequencies_int (basic_block *, int, int, int);
516 extern void scale_bbs_frequencies_gcov_type (basic_block *, int, gcov_type,
519 /* Structure to group all of the information to process IF-THEN and
520 IF-THEN-ELSE blocks for the conditional execution support. This
521 needs to be in a public file in case the IFCVT macros call
522 functions passing the ce_if_block data structure. */
524 typedef struct ce_if_block
526 basic_block test_bb; /* First test block. */
527 basic_block then_bb; /* THEN block. */
528 basic_block else_bb; /* ELSE block or NULL. */
529 basic_block join_bb; /* Join THEN/ELSE blocks. */
530 basic_block last_test_bb; /* Last bb to hold && or || tests. */
531 int num_multiple_test_blocks; /* # of && and || basic blocks. */
532 int num_and_and_blocks; /* # of && blocks. */
533 int num_or_or_blocks; /* # of || blocks. */
534 int num_multiple_test_insns; /* # of insns in && and || blocks. */
535 int and_and_p; /* Complex test is &&. */
536 int num_then_insns; /* # of insns in THEN block. */
537 int num_else_insns; /* # of insns in ELSE block. */
538 int pass; /* Pass number. */
540 #ifdef IFCVT_EXTRA_FIELDS
541 IFCVT_EXTRA_FIELDS /* Any machine dependent fields. */
546 /* This structure maintains an edge list vector. */
554 /* The base value for branch probability notes and edge probabilities. */
555 #define REG_BR_PROB_BASE 10000
557 /* This is the value which indicates no edge is present. */
558 #define EDGE_INDEX_NO_EDGE -1
560 /* EDGE_INDEX returns an integer index for an edge, or EDGE_INDEX_NO_EDGE
561 if there is no edge between the 2 basic blocks. */
562 #define EDGE_INDEX(el, pred, succ) (find_edge_index ((el), (pred), (succ)))
564 /* INDEX_EDGE_PRED_BB and INDEX_EDGE_SUCC_BB return a pointer to the basic
565 block which is either the pred or succ end of the indexed edge. */
566 #define INDEX_EDGE_PRED_BB(el, index) ((el)->index_to_edge[(index)]->src)
567 #define INDEX_EDGE_SUCC_BB(el, index) ((el)->index_to_edge[(index)]->dest)
569 /* INDEX_EDGE returns a pointer to the edge. */
570 #define INDEX_EDGE(el, index) ((el)->index_to_edge[(index)])
572 /* Number of edges in the compressed edge list. */
573 #define NUM_EDGES(el) ((el)->num_edges)
575 /* BB is assumed to contain conditional jump. Return the fallthru edge. */
576 #define FALLTHRU_EDGE(bb) (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \
577 ? EDGE_SUCC ((bb), 0) : EDGE_SUCC ((bb), 1))
579 /* BB is assumed to contain conditional jump. Return the branch edge. */
580 #define BRANCH_EDGE(bb) (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \
581 ? EDGE_SUCC ((bb), 1) : EDGE_SUCC ((bb), 0))
583 /* Return expected execution frequency of the edge E. */
584 #define EDGE_FREQUENCY(e) (((e)->src->frequency \
586 + REG_BR_PROB_BASE / 2) \
589 /* Return nonzero if edge is critical. */
590 #define EDGE_CRITICAL_P(e) (EDGE_COUNT ((e)->src->succs) >= 2 \
591 && EDGE_COUNT ((e)->dest->preds) >= 2)
593 #define EDGE_COUNT(ev) VEC_length (edge, (ev))
594 #define EDGE_I(ev,i) VEC_index (edge, (ev), (i))
595 #define EDGE_PRED(bb,i) VEC_index (edge, (bb)->preds, (i))
596 #define EDGE_SUCC(bb,i) VEC_index (edge, (bb)->succs, (i))
598 /* Returns true if BB has precisely one successor. */
601 single_succ_p (basic_block bb)
603 return EDGE_COUNT (bb->succs) == 1;
606 /* Returns true if BB has precisely one predecessor. */
609 single_pred_p (basic_block bb)
611 return EDGE_COUNT (bb->preds) == 1;
614 /* Returns the single successor edge of basic block BB. Aborts if
615 BB does not have exactly one successor. */
618 single_succ_edge (basic_block bb)
620 gcc_assert (single_succ_p (bb));
621 return EDGE_SUCC (bb, 0);
624 /* Returns the single predecessor edge of basic block BB. Aborts
625 if BB does not have exactly one predecessor. */
628 single_pred_edge (basic_block bb)
630 gcc_assert (single_pred_p (bb));
631 return EDGE_PRED (bb, 0);
634 /* Returns the single successor block of basic block BB. Aborts
635 if BB does not have exactly one successor. */
637 static inline basic_block
638 single_succ (basic_block bb)
640 return single_succ_edge (bb)->dest;
643 /* Returns the single predecessor block of basic block BB. Aborts
644 if BB does not have exactly one predecessor.*/
646 static inline basic_block
647 single_pred (basic_block bb)
649 return single_pred_edge (bb)->src;
652 /* Iterator object for edges. */
656 VEC(edge,gc) **container;
659 static inline VEC(edge,gc) *
660 ei_container (edge_iterator i)
662 gcc_assert (i.container);
666 #define ei_start(iter) ei_start_1 (&(iter))
667 #define ei_last(iter) ei_last_1 (&(iter))
669 /* Return an iterator pointing to the start of an edge vector. */
670 static inline edge_iterator
671 ei_start_1 (VEC(edge,gc) **ev)
681 /* Return an iterator pointing to the last element of an edge
683 static inline edge_iterator
684 ei_last_1 (VEC(edge,gc) **ev)
688 i.index = EDGE_COUNT (*ev) - 1;
694 /* Is the iterator `i' at the end of the sequence? */
696 ei_end_p (edge_iterator i)
698 return (i.index == EDGE_COUNT (ei_container (i)));
701 /* Is the iterator `i' at one position before the end of the
704 ei_one_before_end_p (edge_iterator i)
706 return (i.index + 1 == EDGE_COUNT (ei_container (i)));
709 /* Advance the iterator to the next element. */
711 ei_next (edge_iterator *i)
713 gcc_assert (i->index < EDGE_COUNT (ei_container (*i)));
717 /* Move the iterator to the previous element. */
719 ei_prev (edge_iterator *i)
721 gcc_assert (i->index > 0);
725 /* Return the edge pointed to by the iterator `i'. */
727 ei_edge (edge_iterator i)
729 return EDGE_I (ei_container (i), i.index);
732 /* Return an edge pointed to by the iterator. Do it safely so that
733 NULL is returned when the iterator is pointing at the end of the
736 ei_safe_edge (edge_iterator i)
738 return !ei_end_p (i) ? ei_edge (i) : NULL;
741 /* Return 1 if we should continue to iterate. Return 0 otherwise.
742 *Edge P is set to the next edge if we are to continue to iterate
743 and NULL otherwise. */
746 ei_cond (edge_iterator ei, edge *p)
760 /* This macro serves as a convenient way to iterate each edge in a
761 vector of predecessor or successor edges. It must not be used when
762 an element might be removed during the traversal, otherwise
763 elements will be missed. Instead, use a for-loop like that shown
764 in the following pseudo-code:
766 FOR (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
775 #define FOR_EACH_EDGE(EDGE,ITER,EDGE_VEC) \
776 for ((ITER) = ei_start ((EDGE_VEC)); \
777 ei_cond ((ITER), &(EDGE)); \
780 struct edge_list * create_edge_list (void);
781 void free_edge_list (struct edge_list *);
782 void print_edge_list (FILE *, struct edge_list *);
783 void verify_edge_list (FILE *, struct edge_list *);
784 int find_edge_index (struct edge_list *, basic_block, basic_block);
785 edge find_edge (basic_block, basic_block);
788 enum update_life_extent
790 UPDATE_LIFE_LOCAL = 0,
791 UPDATE_LIFE_GLOBAL = 1,
792 UPDATE_LIFE_GLOBAL_RM_NOTES = 2
795 /* Flags for life_analysis and update_life_info. */
797 #define PROP_DEATH_NOTES 1 /* Create DEAD and UNUSED notes. */
798 #define PROP_LOG_LINKS 2 /* Create LOG_LINKS. */
799 #define PROP_REG_INFO 4 /* Update regs_ever_live et al. */
800 #define PROP_KILL_DEAD_CODE 8 /* Remove dead code. */
801 #define PROP_SCAN_DEAD_CODE 16 /* Scan for dead code. */
802 #define PROP_ALLOW_CFG_CHANGES 32 /* Allow the CFG to be changed
803 by dead code removal. */
804 #define PROP_AUTOINC 64 /* Create autoinc mem references. */
805 #define PROP_SCAN_DEAD_STORES 128 /* Scan for dead code. */
806 #define PROP_ASM_SCAN 256 /* Internal flag used within flow.c
807 to flag analysis of asms. */
808 #define PROP_DEAD_INSN 1024 /* Internal flag used within flow.c
809 to flag analysis of dead insn. */
810 #define PROP_POST_REGSTACK 2048 /* We run after reg-stack and need
811 to preserve REG_DEAD notes for
813 #define PROP_FINAL (PROP_DEATH_NOTES | PROP_LOG_LINKS \
814 | PROP_REG_INFO | PROP_KILL_DEAD_CODE \
815 | PROP_SCAN_DEAD_CODE | PROP_AUTOINC \
816 | PROP_ALLOW_CFG_CHANGES \
817 | PROP_SCAN_DEAD_STORES)
818 #define PROP_POSTRELOAD (PROP_DEATH_NOTES \
819 | PROP_KILL_DEAD_CODE \
820 | PROP_SCAN_DEAD_CODE \
821 | PROP_SCAN_DEAD_STORES)
823 #define CLEANUP_EXPENSIVE 1 /* Do relatively expensive optimizations
824 except for edge forwarding */
825 #define CLEANUP_CROSSJUMP 2 /* Do crossjumping. */
826 #define CLEANUP_POST_REGSTACK 4 /* We run after reg-stack and need
827 to care REG_DEAD notes. */
828 #define CLEANUP_UPDATE_LIFE 8 /* Keep life information up to date. */
829 #define CLEANUP_THREADING 16 /* Do jump threading. */
830 #define CLEANUP_NO_INSN_DEL 32 /* Do not try to delete trivially dead
832 #define CLEANUP_CFGLAYOUT 64 /* Do cleanup in cfglayout mode. */
833 #define CLEANUP_LOG_LINKS 128 /* Update log links. */
835 /* The following are ORed in on top of the CLEANUP* flags in calls to
836 struct_equiv_block_eq. */
837 #define STRUCT_EQUIV_START 256 /* Initializes the search range. */
838 #define STRUCT_EQUIV_RERUN 512 /* Rerun to find register use in
839 found equivalence. */
840 #define STRUCT_EQUIV_FINAL 1024 /* Make any changes necessary to get
841 actual equivalence. */
842 #define STRUCT_EQUIV_NEED_FULL_BLOCK 2048 /* struct_equiv_block_eq is required
843 to match only full blocks */
844 #define STRUCT_EQUIV_MATCH_JUMPS 4096 /* Also include the jumps at the end of the block in the comparison. */
846 extern void life_analysis (int);
847 extern int update_life_info (sbitmap, enum update_life_extent, int);
848 extern int update_life_info_in_dirty_blocks (enum update_life_extent, int);
849 extern int count_or_remove_death_notes (sbitmap, int);
850 extern int propagate_block (basic_block, regset, regset, regset, int);
852 struct propagate_block_info;
853 extern rtx propagate_one_insn (struct propagate_block_info *, rtx);
854 extern struct propagate_block_info *init_propagate_block_info
855 (basic_block, regset, regset, regset, int);
856 extern void free_propagate_block_info (struct propagate_block_info *);
859 extern struct edge_list *pre_edge_lcm (int, sbitmap *, sbitmap *,
860 sbitmap *, sbitmap *, sbitmap **,
862 extern struct edge_list *pre_edge_rev_lcm (int, sbitmap *,
863 sbitmap *, sbitmap *,
864 sbitmap *, sbitmap **,
866 extern void compute_available (sbitmap *, sbitmap *, sbitmap *, sbitmap *);
869 extern bool maybe_hot_bb_p (basic_block);
870 extern bool probably_cold_bb_p (basic_block);
871 extern bool probably_never_executed_bb_p (basic_block);
872 extern bool tree_predicted_by_p (basic_block, enum br_predictor);
873 extern bool rtl_predicted_by_p (basic_block, enum br_predictor);
874 extern void tree_predict_edge (edge, enum br_predictor, int);
875 extern void rtl_predict_edge (edge, enum br_predictor, int);
876 extern void predict_edge_def (edge, enum br_predictor, enum prediction);
877 extern void guess_outgoing_edge_probabilities (basic_block);
878 extern void remove_predictions_associated_with_edge (edge);
879 extern bool edge_probability_reliable_p (edge);
880 extern bool br_prob_note_reliable_p (rtx);
883 extern void init_flow (void);
884 extern void debug_bb (basic_block);
885 extern basic_block debug_bb_n (int);
886 extern void dump_regset (regset, FILE *);
887 extern void debug_regset (regset);
888 extern void allocate_reg_life_data (void);
889 extern void expunge_block (basic_block);
890 extern void link_block (basic_block, basic_block);
891 extern void unlink_block (basic_block);
892 extern void compact_blocks (void);
893 extern basic_block alloc_block (void);
894 extern void find_unreachable_blocks (void);
895 extern int delete_noop_moves (void);
896 extern basic_block force_nonfallthru (edge);
897 extern rtx block_label (basic_block);
898 extern bool forwarder_block_p (basic_block);
899 extern bool purge_all_dead_edges (void);
900 extern bool purge_dead_edges (basic_block);
901 extern void find_many_sub_basic_blocks (sbitmap);
902 extern void rtl_make_eh_edge (sbitmap, basic_block, rtx);
903 extern bool can_fallthru (basic_block, basic_block);
904 extern bool could_fall_through (basic_block, basic_block);
905 extern void flow_nodes_print (const char *, const sbitmap, FILE *);
906 extern void flow_edge_list_print (const char *, const edge *, int, FILE *);
907 extern void alloc_aux_for_block (basic_block, int);
908 extern void alloc_aux_for_blocks (int);
909 extern void clear_aux_for_blocks (void);
910 extern void free_aux_for_blocks (void);
911 extern void alloc_aux_for_edge (edge, int);
912 extern void alloc_aux_for_edges (int);
913 extern void clear_aux_for_edges (void);
914 extern void free_aux_for_edges (void);
915 extern void find_basic_blocks (rtx);
916 extern bool cleanup_cfg (int);
917 extern bool delete_unreachable_blocks (void);
918 extern bool merge_seq_blocks (void);
920 extern bool mark_dfs_back_edges (void);
921 extern void set_edge_can_fallthru_flag (void);
922 extern void update_br_prob_note (basic_block);
923 extern void fixup_abnormal_edges (void);
924 extern bool inside_basic_block_p (rtx);
925 extern bool control_flow_insn_p (rtx);
926 extern rtx get_last_bb_insn (basic_block);
928 /* In bb-reorder.c */
929 extern void reorder_basic_blocks (void);
941 DOM_NONE, /* Not computed at all. */
942 DOM_NO_FAST_QUERY, /* The data is OK, but the fast query data are not usable. */
943 DOM_OK /* Everything is ok. */
946 extern enum dom_state dom_computed[2];
948 extern bool dom_info_available_p (enum cdi_direction);
949 extern void calculate_dominance_info (enum cdi_direction);
950 extern void free_dominance_info (enum cdi_direction);
951 extern basic_block nearest_common_dominator (enum cdi_direction,
952 basic_block, basic_block);
953 extern basic_block nearest_common_dominator_for_set (enum cdi_direction,
955 extern void set_immediate_dominator (enum cdi_direction, basic_block,
957 extern basic_block get_immediate_dominator (enum cdi_direction, basic_block);
958 extern bool dominated_by_p (enum cdi_direction, basic_block, basic_block);
959 extern int get_dominated_by (enum cdi_direction, basic_block, basic_block **);
960 extern unsigned get_dominated_by_region (enum cdi_direction, basic_block *,
961 unsigned, basic_block *);
962 extern void add_to_dominance_info (enum cdi_direction, basic_block);
963 extern void delete_from_dominance_info (enum cdi_direction, basic_block);
964 basic_block recount_dominator (enum cdi_direction, basic_block);
965 extern void redirect_immediate_dominators (enum cdi_direction, basic_block,
967 extern void iterate_fix_dominators (enum cdi_direction, basic_block *, int);
968 extern void verify_dominators (enum cdi_direction);
969 extern basic_block first_dom_son (enum cdi_direction, basic_block);
970 extern basic_block next_dom_son (enum cdi_direction, basic_block);
971 unsigned bb_dom_dfs_in (enum cdi_direction, basic_block);
972 unsigned bb_dom_dfs_out (enum cdi_direction, basic_block);
974 extern edge try_redirect_by_replacing_jump (edge, basic_block, bool);
975 extern void break_superblocks (void);
976 extern void relink_block_chain (bool);
977 extern void check_bb_profile (basic_block, FILE *);
978 extern void update_bb_profile_for_threading (basic_block, int, gcov_type, edge);
979 extern void init_rtl_bb_info (basic_block);
981 extern void initialize_original_copy_tables (void);
982 extern void free_original_copy_tables (void);
983 extern void set_bb_original (basic_block, basic_block);
984 extern basic_block get_bb_original (basic_block);
985 extern void set_bb_copy (basic_block, basic_block);
986 extern basic_block get_bb_copy (basic_block);
988 extern rtx insert_insn_end_bb_new (rtx, basic_block);
990 #include "cfghooks.h"
992 /* In struct-equiv.c */
994 /* Constants used to size arrays in struct equiv_info (currently only one).
995 When these limits are exceeded, struct_equiv returns zero.
996 The maximum number of pseudo registers that are different in the two blocks,
997 but appear in equivalent places and are dead at the end (or where one of
998 a pair is dead at the end). */
999 #define STRUCT_EQUIV_MAX_LOCAL 16
1000 /* The maximum number of references to an input register that struct_equiv
1003 /* Structure used to track state during struct_equiv that can be rolled
1004 back when we find we can't match an insn, or if we want to match part
1005 of it in a different way.
1006 This information pertains to the pair of partial blocks that has been
1007 matched so far. Since this pair is structurally equivalent, this is
1008 conceptually just one partial block expressed in two potentially
1010 struct struct_equiv_checkpoint
1012 int ninsns; /* Insns are matched so far. */
1013 int local_count; /* Number of block-local registers. */
1014 int input_count; /* Number of inputs to the block. */
1016 /* X_START and Y_START are the first insns (in insn stream order)
1017 of the partial blocks that have been considered for matching so far.
1018 Since we are scanning backwards, they are also the instructions that
1019 are currently considered - or the last ones that have been considered -
1020 for matching (Unless we tracked back to these because a preceding
1021 instruction failed to match). */
1022 rtx x_start, y_start;
1024 /* INPUT_VALID indicates if we have actually set up X_INPUT / Y_INPUT
1025 during the current pass; we keep X_INPUT / Y_INPUT around between passes
1026 so that we can match REG_EQUAL / REG_EQUIV notes referring to these. */
1029 /* Some information would be expensive to exactly checkpoint, so we
1030 merely increment VERSION any time information about local
1031 registers, inputs and/or register liveness changes. When backtracking,
1032 it is decremented for changes that can be undone, and if a discrepancy
1033 remains, NEED_RERUN in the relevant struct equiv_info is set to indicate
1034 that a new pass should be made over the entire block match to get
1035 accurate register information. */
1039 /* A struct equiv_info is used to pass information to struct_equiv and
1040 to gather state while two basic blocks are checked for structural
1045 /* Fields set up by the caller to struct_equiv_block_eq */
1047 basic_block x_block, y_block; /* The two blocks being matched. */
1049 /* MODE carries the mode bits from cleanup_cfg if we are called from
1050 try_crossjump_to_edge, and additionally it carries the
1051 STRUCT_EQUIV_* bits described above. */
1054 /* INPUT_COST is the cost that adding an extra input to the matched blocks
1055 is supposed to have, and is taken into account when considering if the
1056 matched sequence should be extended backwards. input_cost < 0 means
1057 don't accept any inputs at all. */
1061 /* Fields to track state inside of struct_equiv_block_eq. Some of these
1062 are also outputs. */
1064 /* X_INPUT and Y_INPUT are used by struct_equiv to record a register that
1065 is used as an input parameter, i.e. where different registers are used
1066 as sources. This is only used for a register that is live at the end
1067 of the blocks, or in some identical code at the end of the blocks;
1068 Inputs that are dead at the end go into X_LOCAL / Y_LOCAL. */
1069 rtx x_input, y_input;
1070 /* When a previous pass has identified a valid input, INPUT_REG is set
1071 by struct_equiv_block_eq, and it is henceforth replaced in X_BLOCK
1075 /* COMMON_LIVE keeps track of the registers which are currently live
1076 (as we scan backwards from the end) and have the same numbers in both
1077 blocks. N.B. a register that is in common_live is unsuitable to become
1080 /* Likewise, X_LOCAL_LIVE / Y_LOCAL_LIVE keep track of registers that are
1081 local to one of the blocks; these registers must not be accepted as
1082 identical when encountered in both blocks. */
1083 regset x_local_live, y_local_live;
1085 /* EQUIV_USED indicates for which insns a REG_EQUAL or REG_EQUIV note is
1086 being used, to avoid having to backtrack in the next pass, so that we
1087 get accurate life info for this insn then. For each such insn,
1088 the bit with the number corresponding to the CUR.NINSNS value at the
1089 time of scanning is set. */
1092 /* Current state that can be saved & restored easily. */
1093 struct struct_equiv_checkpoint cur;
1094 /* BEST_MATCH is used to store the best match so far, weighing the
1095 cost of matched insns COSTS_N_INSNS (CUR.NINSNS) against the cost
1096 CUR.INPUT_COUNT * INPUT_COST of setting up the inputs. */
1097 struct struct_equiv_checkpoint best_match;
1098 /* If a checkpoint restore failed, or an input conflict newly arises,
1099 NEED_RERUN is set. This has to be tested by the caller to re-run
1100 the comparison if the match appears otherwise sound. The state kept in
1101 x_start, y_start, equiv_used and check_input_conflict ensures that
1102 we won't loop indefinitely. */
1104 /* If there is indication of an input conflict at the end,
1105 CHECK_INPUT_CONFLICT is set so that we'll check for input conflicts
1106 for each insn in the next pass. This is needed so that we won't discard
1107 a partial match if there is a longer match that has to be abandoned due
1108 to an input conflict. */
1109 bool check_input_conflict;
1110 /* HAD_INPUT_CONFLICT is set if CHECK_INPUT_CONFLICT was already set and we
1111 have passed a point where there were multiple dying inputs. This helps
1112 us decide if we should set check_input_conflict for the next pass. */
1113 bool had_input_conflict;
1115 /* LIVE_UPDATE controls if we want to change any life info at all. We
1116 set it to false during REG_EQUAL / REG_EUQIV note comparison of the final
1117 pass so that we don't introduce new registers just for the note; if we
1118 can't match the notes without the current register information, we drop
1122 /* X_LOCAL and Y_LOCAL are used to gather register numbers of register pairs
1123 that are local to X_BLOCK and Y_BLOCK, with CUR.LOCAL_COUNT being the index
1124 to the next free entry. */
1125 rtx x_local[STRUCT_EQUIV_MAX_LOCAL], y_local[STRUCT_EQUIV_MAX_LOCAL];
1126 /* LOCAL_RVALUE is nonzero if the corresponding X_LOCAL / Y_LOCAL entry
1127 was a source operand (including STRICT_LOW_PART) for the last invocation
1128 of struct_equiv mentioning it, zero if it was a destination-only operand.
1129 Since we are scanning backwards, this means the register is input/local
1130 for the (partial) block scanned so far. */
1131 bool local_rvalue[STRUCT_EQUIV_MAX_LOCAL];
1134 /* Additional fields that are computed for the convenience of the caller. */
1136 /* DYING_INPUTS is set to the number of local registers that turn out
1137 to be inputs to the (possibly partial) block. */
1139 /* X_END and Y_END are the last insns in X_BLOCK and Y_BLOCK, respectively,
1140 that are being compared. A final jump insn will not be included. */
1143 /* If we are matching tablejumps, X_LABEL in X_BLOCK corresponds to
1144 Y_LABEL in Y_BLOCK. */
1145 rtx x_label, y_label;
1149 extern bool insns_match_p (rtx, rtx, struct equiv_info *);
1150 extern int struct_equiv_block_eq (int, struct equiv_info *);
1151 extern bool struct_equiv_init (int, struct equiv_info *);
1152 extern bool rtx_equiv_p (rtx *, rtx, int, struct equiv_info *);
1155 extern bool condjump_equiv_p (struct equiv_info *, bool);
1157 /* Return true when one of the predecessor edges of BB is marked with EDGE_EH. */
1158 static inline bool bb_has_eh_pred (basic_block bb)
1163 FOR_EACH_EDGE (e, ei, bb->preds)
1165 if (e->flags & EDGE_EH)
1171 #endif /* GCC_BASIC_BLOCK_H */