2014-12-12 Richard Biener <rguenther@suse.de>
[official-gcc.git] / gcc / basic-block.h
blob57324215faf5bf8d087152b01b14394b435c9b81
1 /* Define control flow data structures for the CFG.
2 Copyright (C) 1987-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #ifndef GCC_BASIC_BLOCK_H
21 #define GCC_BASIC_BLOCK_H
24 /* Use gcov_type to hold basic block counters. Should be at least
25 64bit. Although a counter cannot be negative, we use a signed
26 type, because erroneous negative counts can be generated when the
27 flow graph is manipulated by various optimizations. A signed type
28 makes those easy to detect. */
30 /* Control flow edge information. */
31 struct GTY((user)) edge_def {
32 /* The two blocks at the ends of the edge. */
33 basic_block src;
34 basic_block dest;
36 /* Instructions queued on the edge. */
37 union edge_def_insns {
38 gimple_seq g;
39 rtx_insn *r;
40 } insns;
42 /* Auxiliary info specific to a pass. */
43 PTR aux;
45 /* Location of any goto implicit in the edge. */
46 location_t goto_locus;
48 /* The index number corresponding to this edge in the edge vector
49 dest->preds. */
50 unsigned int dest_idx;
52 int flags; /* see cfg-flags.def */
53 int probability; /* biased by REG_BR_PROB_BASE */
54 gcov_type count; /* Expected number of executions calculated
55 in profile.c */
58 /* Masks for edge.flags. */
59 #define DEF_EDGE_FLAG(NAME,IDX) EDGE_##NAME = 1 << IDX ,
60 enum cfg_edge_flags {
61 #include "cfg-flags.def"
62 LAST_CFG_EDGE_FLAG /* this is only used for EDGE_ALL_FLAGS */
64 #undef DEF_EDGE_FLAG
66 /* Bit mask for all edge flags. */
67 #define EDGE_ALL_FLAGS ((LAST_CFG_EDGE_FLAG - 1) * 2 - 1)
69 /* The following four flags all indicate something special about an edge.
70 Test the edge flags on EDGE_COMPLEX to detect all forms of "strange"
71 control flow transfers. */
72 #define EDGE_COMPLEX \
73 (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_PRESERVE)
75 struct GTY(()) rtl_bb_info {
76 /* The first insn of the block is embedded into bb->il.x. */
77 /* The last insn of the block. */
78 rtx_insn *end_;
80 /* In CFGlayout mode points to insn notes/jumptables to be placed just before
81 and after the block. */
82 rtx_insn *header_;
83 rtx_insn *footer_;
86 struct GTY(()) gimple_bb_info {
87 /* Sequence of statements in this block. */
88 gimple_seq seq;
90 /* PHI nodes for this block. */
91 gimple_seq phi_nodes;
94 /* A basic block is a sequence of instructions with only one entry and
95 only one exit. If any one of the instructions are executed, they
96 will all be executed, and in sequence from first to last.
98 There may be COND_EXEC instructions in the basic block. The
99 COND_EXEC *instructions* will be executed -- but if the condition
100 is false the conditionally executed *expressions* will of course
101 not be executed. We don't consider the conditionally executed
102 expression (which might have side-effects) to be in a separate
103 basic block because the program counter will always be at the same
104 location after the COND_EXEC instruction, regardless of whether the
105 condition is true or not.
107 Basic blocks need not start with a label nor end with a jump insn.
108 For example, a previous basic block may just "conditionally fall"
109 into the succeeding basic block, and the last basic block need not
110 end with a jump insn. Block 0 is a descendant of the entry block.
112 A basic block beginning with two labels cannot have notes between
113 the labels.
115 Data for jump tables are stored in jump_insns that occur in no
116 basic block even though these insns can follow or precede insns in
117 basic blocks. */
119 /* Basic block information indexed by block number. */
120 struct GTY((chain_next ("%h.next_bb"), chain_prev ("%h.prev_bb"))) basic_block_def {
121 /* The edges into and out of the block. */
122 vec<edge, va_gc> *preds;
123 vec<edge, va_gc> *succs;
125 /* Auxiliary info specific to a pass. */
126 PTR GTY ((skip (""))) aux;
128 /* Innermost loop containing the block. */
129 struct loop *loop_father;
131 /* The dominance and postdominance information node. */
132 struct et_node * GTY ((skip (""))) dom[2];
134 /* Previous and next blocks in the chain. */
135 basic_block prev_bb;
136 basic_block next_bb;
138 union basic_block_il_dependent {
139 struct gimple_bb_info GTY ((tag ("0"))) gimple;
140 struct {
141 rtx_insn *head_;
142 struct rtl_bb_info * rtl;
143 } GTY ((tag ("1"))) x;
144 } GTY ((desc ("((%1.flags & BB_RTL) != 0)"))) il;
146 /* Various flags. See cfg-flags.def. */
147 int flags;
149 /* The index of this block. */
150 int index;
152 /* Expected number of executions: calculated in profile.c. */
153 gcov_type count;
155 /* Expected frequency. Normalized to be in range 0 to BB_FREQ_MAX. */
156 int frequency;
158 /* The discriminator for this block. The discriminator distinguishes
159 among several basic blocks that share a common locus, allowing for
160 more accurate sample-based profiling. */
161 int discriminator;
164 /* This ensures that struct gimple_bb_info is smaller than
165 struct rtl_bb_info, so that inlining the former into basic_block_def
166 is the better choice. */
167 typedef int __assert_gimple_bb_smaller_rtl_bb
168 [(int) sizeof (struct rtl_bb_info)
169 - (int) sizeof (struct gimple_bb_info)];
172 #define BB_FREQ_MAX 10000
174 /* Masks for basic_block.flags. */
175 #define DEF_BASIC_BLOCK_FLAG(NAME,IDX) BB_##NAME = 1 << IDX ,
176 enum cfg_bb_flags
178 #include "cfg-flags.def"
179 LAST_CFG_BB_FLAG /* this is only used for BB_ALL_FLAGS */
181 #undef DEF_BASIC_BLOCK_FLAG
183 /* Bit mask for all basic block flags. */
184 #define BB_ALL_FLAGS ((LAST_CFG_BB_FLAG - 1) * 2 - 1)
186 /* Bit mask for all basic block flags that must be preserved. These are
187 the bit masks that are *not* cleared by clear_bb_flags. */
188 #define BB_FLAGS_TO_PRESERVE \
189 (BB_DISABLE_SCHEDULE | BB_RTL | BB_NON_LOCAL_GOTO_TARGET \
190 | BB_HOT_PARTITION | BB_COLD_PARTITION)
192 /* Dummy bitmask for convenience in the hot/cold partitioning code. */
193 #define BB_UNPARTITIONED 0
195 /* Partitions, to be used when partitioning hot and cold basic blocks into
196 separate sections. */
197 #define BB_PARTITION(bb) ((bb)->flags & (BB_HOT_PARTITION|BB_COLD_PARTITION))
198 #define BB_SET_PARTITION(bb, part) do { \
199 basic_block bb_ = (bb); \
200 bb_->flags = ((bb_->flags & ~(BB_HOT_PARTITION|BB_COLD_PARTITION)) \
201 | (part)); \
202 } while (0)
204 #define BB_COPY_PARTITION(dstbb, srcbb) \
205 BB_SET_PARTITION (dstbb, BB_PARTITION (srcbb))
207 /* Defines for accessing the fields of the CFG structure for function FN. */
208 #define ENTRY_BLOCK_PTR_FOR_FN(FN) ((FN)->cfg->x_entry_block_ptr)
209 #define EXIT_BLOCK_PTR_FOR_FN(FN) ((FN)->cfg->x_exit_block_ptr)
210 #define basic_block_info_for_fn(FN) ((FN)->cfg->x_basic_block_info)
211 #define n_basic_blocks_for_fn(FN) ((FN)->cfg->x_n_basic_blocks)
212 #define n_edges_for_fn(FN) ((FN)->cfg->x_n_edges)
213 #define last_basic_block_for_fn(FN) ((FN)->cfg->x_last_basic_block)
214 #define label_to_block_map_for_fn(FN) ((FN)->cfg->x_label_to_block_map)
215 #define profile_status_for_fn(FN) ((FN)->cfg->x_profile_status)
217 #define BASIC_BLOCK_FOR_FN(FN,N) \
218 ((*basic_block_info_for_fn (FN))[(N)])
219 #define SET_BASIC_BLOCK_FOR_FN(FN,N,BB) \
220 ((*basic_block_info_for_fn (FN))[(N)] = (BB))
222 /* For iterating over basic blocks. */
223 #define FOR_BB_BETWEEN(BB, FROM, TO, DIR) \
224 for (BB = FROM; BB != TO; BB = BB->DIR)
226 #define FOR_EACH_BB_FN(BB, FN) \
227 FOR_BB_BETWEEN (BB, (FN)->cfg->x_entry_block_ptr->next_bb, (FN)->cfg->x_exit_block_ptr, next_bb)
229 #define FOR_EACH_BB_REVERSE_FN(BB, FN) \
230 FOR_BB_BETWEEN (BB, (FN)->cfg->x_exit_block_ptr->prev_bb, (FN)->cfg->x_entry_block_ptr, prev_bb)
232 /* For iterating over insns in basic block. */
233 #define FOR_BB_INSNS(BB, INSN) \
234 for ((INSN) = BB_HEAD (BB); \
235 (INSN) && (INSN) != NEXT_INSN (BB_END (BB)); \
236 (INSN) = NEXT_INSN (INSN))
238 /* For iterating over insns in basic block when we might remove the
239 current insn. */
240 #define FOR_BB_INSNS_SAFE(BB, INSN, CURR) \
241 for ((INSN) = BB_HEAD (BB), (CURR) = (INSN) ? NEXT_INSN ((INSN)): NULL; \
242 (INSN) && (INSN) != NEXT_INSN (BB_END (BB)); \
243 (INSN) = (CURR), (CURR) = (INSN) ? NEXT_INSN ((INSN)) : NULL)
245 #define FOR_BB_INSNS_REVERSE(BB, INSN) \
246 for ((INSN) = BB_END (BB); \
247 (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB)); \
248 (INSN) = PREV_INSN (INSN))
250 #define FOR_BB_INSNS_REVERSE_SAFE(BB, INSN, CURR) \
251 for ((INSN) = BB_END (BB),(CURR) = (INSN) ? PREV_INSN ((INSN)) : NULL; \
252 (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB)); \
253 (INSN) = (CURR), (CURR) = (INSN) ? PREV_INSN ((INSN)) : NULL)
255 /* Cycles through _all_ basic blocks, even the fake ones (entry and
256 exit block). */
258 #define FOR_ALL_BB_FN(BB, FN) \
259 for (BB = ENTRY_BLOCK_PTR_FOR_FN (FN); BB; BB = BB->next_bb)
262 /* Stuff for recording basic block info. */
264 /* For now, these will be functions (so that they can include checked casts
265 to rtx_insn. Once the underlying fields are converted from rtx
266 to rtx_insn, these can be converted back to macros. */
268 #define BB_HEAD(B) (B)->il.x.head_
269 #define BB_END(B) (B)->il.x.rtl->end_
270 #define BB_HEADER(B) (B)->il.x.rtl->header_
271 #define BB_FOOTER(B) (B)->il.x.rtl->footer_
273 /* Special block numbers [markers] for entry and exit.
274 Neither of them is supposed to hold actual statements. */
275 #define ENTRY_BLOCK (0)
276 #define EXIT_BLOCK (1)
278 /* The two blocks that are always in the cfg. */
279 #define NUM_FIXED_BLOCKS (2)
281 /* The base value for branch probability notes and edge probabilities. */
282 #define REG_BR_PROB_BASE 10000
284 /* This is the value which indicates no edge is present. */
285 #define EDGE_INDEX_NO_EDGE -1
287 /* EDGE_INDEX returns an integer index for an edge, or EDGE_INDEX_NO_EDGE
288 if there is no edge between the 2 basic blocks. */
289 #define EDGE_INDEX(el, pred, succ) (find_edge_index ((el), (pred), (succ)))
291 /* INDEX_EDGE_PRED_BB and INDEX_EDGE_SUCC_BB return a pointer to the basic
292 block which is either the pred or succ end of the indexed edge. */
293 #define INDEX_EDGE_PRED_BB(el, index) ((el)->index_to_edge[(index)]->src)
294 #define INDEX_EDGE_SUCC_BB(el, index) ((el)->index_to_edge[(index)]->dest)
296 /* INDEX_EDGE returns a pointer to the edge. */
297 #define INDEX_EDGE(el, index) ((el)->index_to_edge[(index)])
299 /* Number of edges in the compressed edge list. */
300 #define NUM_EDGES(el) ((el)->num_edges)
302 /* BB is assumed to contain conditional jump. Return the fallthru edge. */
303 #define FALLTHRU_EDGE(bb) (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \
304 ? EDGE_SUCC ((bb), 0) : EDGE_SUCC ((bb), 1))
306 /* BB is assumed to contain conditional jump. Return the branch edge. */
307 #define BRANCH_EDGE(bb) (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \
308 ? EDGE_SUCC ((bb), 1) : EDGE_SUCC ((bb), 0))
310 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
311 /* Return expected execution frequency of the edge E. */
312 #define EDGE_FREQUENCY(e) RDIV ((e)->src->frequency * (e)->probability, \
313 REG_BR_PROB_BASE)
315 /* Compute a scale factor (or probability) suitable for scaling of
316 gcov_type values via apply_probability() and apply_scale(). */
317 #define GCOV_COMPUTE_SCALE(num,den) \
318 ((den) ? RDIV ((num) * REG_BR_PROB_BASE, (den)) : REG_BR_PROB_BASE)
320 /* Return nonzero if edge is critical. */
321 #define EDGE_CRITICAL_P(e) (EDGE_COUNT ((e)->src->succs) >= 2 \
322 && EDGE_COUNT ((e)->dest->preds) >= 2)
324 #define EDGE_COUNT(ev) vec_safe_length (ev)
325 #define EDGE_I(ev,i) (*ev)[(i)]
326 #define EDGE_PRED(bb,i) (*(bb)->preds)[(i)]
327 #define EDGE_SUCC(bb,i) (*(bb)->succs)[(i)]
329 /* Returns true if BB has precisely one successor. */
331 static inline bool
332 single_succ_p (const_basic_block bb)
334 return EDGE_COUNT (bb->succs) == 1;
337 /* Returns true if BB has precisely one predecessor. */
339 static inline bool
340 single_pred_p (const_basic_block bb)
342 return EDGE_COUNT (bb->preds) == 1;
345 /* Returns the single successor edge of basic block BB. Aborts if
346 BB does not have exactly one successor. */
348 static inline edge
349 single_succ_edge (const_basic_block bb)
351 gcc_checking_assert (single_succ_p (bb));
352 return EDGE_SUCC (bb, 0);
355 /* Returns the single predecessor edge of basic block BB. Aborts
356 if BB does not have exactly one predecessor. */
358 static inline edge
359 single_pred_edge (const_basic_block bb)
361 gcc_checking_assert (single_pred_p (bb));
362 return EDGE_PRED (bb, 0);
365 /* Returns the single successor block of basic block BB. Aborts
366 if BB does not have exactly one successor. */
368 static inline basic_block
369 single_succ (const_basic_block bb)
371 return single_succ_edge (bb)->dest;
374 /* Returns the single predecessor block of basic block BB. Aborts
375 if BB does not have exactly one predecessor.*/
377 static inline basic_block
378 single_pred (const_basic_block bb)
380 return single_pred_edge (bb)->src;
383 /* Iterator object for edges. */
385 struct edge_iterator {
386 unsigned index;
387 vec<edge, va_gc> **container;
390 static inline vec<edge, va_gc> *
391 ei_container (edge_iterator i)
393 gcc_checking_assert (i.container);
394 return *i.container;
397 #define ei_start(iter) ei_start_1 (&(iter))
398 #define ei_last(iter) ei_last_1 (&(iter))
400 /* Return an iterator pointing to the start of an edge vector. */
401 static inline edge_iterator
402 ei_start_1 (vec<edge, va_gc> **ev)
404 edge_iterator i;
406 i.index = 0;
407 i.container = ev;
409 return i;
412 /* Return an iterator pointing to the last element of an edge
413 vector. */
414 static inline edge_iterator
415 ei_last_1 (vec<edge, va_gc> **ev)
417 edge_iterator i;
419 i.index = EDGE_COUNT (*ev) - 1;
420 i.container = ev;
422 return i;
425 /* Is the iterator `i' at the end of the sequence? */
426 static inline bool
427 ei_end_p (edge_iterator i)
429 return (i.index == EDGE_COUNT (ei_container (i)));
432 /* Is the iterator `i' at one position before the end of the
433 sequence? */
434 static inline bool
435 ei_one_before_end_p (edge_iterator i)
437 return (i.index + 1 == EDGE_COUNT (ei_container (i)));
440 /* Advance the iterator to the next element. */
441 static inline void
442 ei_next (edge_iterator *i)
444 gcc_checking_assert (i->index < EDGE_COUNT (ei_container (*i)));
445 i->index++;
448 /* Move the iterator to the previous element. */
449 static inline void
450 ei_prev (edge_iterator *i)
452 gcc_checking_assert (i->index > 0);
453 i->index--;
456 /* Return the edge pointed to by the iterator `i'. */
457 static inline edge
458 ei_edge (edge_iterator i)
460 return EDGE_I (ei_container (i), i.index);
463 /* Return an edge pointed to by the iterator. Do it safely so that
464 NULL is returned when the iterator is pointing at the end of the
465 sequence. */
466 static inline edge
467 ei_safe_edge (edge_iterator i)
469 return !ei_end_p (i) ? ei_edge (i) : NULL;
472 /* Return 1 if we should continue to iterate. Return 0 otherwise.
473 *Edge P is set to the next edge if we are to continue to iterate
474 and NULL otherwise. */
476 static inline bool
477 ei_cond (edge_iterator ei, edge *p)
479 if (!ei_end_p (ei))
481 *p = ei_edge (ei);
482 return 1;
484 else
486 *p = NULL;
487 return 0;
491 /* This macro serves as a convenient way to iterate each edge in a
492 vector of predecessor or successor edges. It must not be used when
493 an element might be removed during the traversal, otherwise
494 elements will be missed. Instead, use a for-loop like that shown
495 in the following pseudo-code:
497 FOR (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
499 IF (e != taken_edge)
500 remove_edge (e);
501 ELSE
502 ei_next (&ei);
506 #define FOR_EACH_EDGE(EDGE,ITER,EDGE_VEC) \
507 for ((ITER) = ei_start ((EDGE_VEC)); \
508 ei_cond ((ITER), &(EDGE)); \
509 ei_next (&(ITER)))
511 #define CLEANUP_EXPENSIVE 1 /* Do relatively expensive optimizations
512 except for edge forwarding */
513 #define CLEANUP_CROSSJUMP 2 /* Do crossjumping. */
514 #define CLEANUP_POST_REGSTACK 4 /* We run after reg-stack and need
515 to care REG_DEAD notes. */
516 #define CLEANUP_THREADING 8 /* Do jump threading. */
517 #define CLEANUP_NO_INSN_DEL 16 /* Do not try to delete trivially dead
518 insns. */
519 #define CLEANUP_CFGLAYOUT 32 /* Do cleanup in cfglayout mode. */
520 #define CLEANUP_CFG_CHANGED 64 /* The caller changed the CFG. */
522 #include "cfghooks.h"
524 /* Return true if BB is in a transaction. */
526 static inline bool
527 bb_in_transaction (basic_block bb)
529 return bb->flags & BB_IN_TRANSACTION;
532 /* Return true when one of the predecessor edges of BB is marked with EDGE_EH. */
533 static inline bool
534 bb_has_eh_pred (basic_block bb)
536 edge e;
537 edge_iterator ei;
539 FOR_EACH_EDGE (e, ei, bb->preds)
541 if (e->flags & EDGE_EH)
542 return true;
544 return false;
547 /* Return true when one of the predecessor edges of BB is marked with EDGE_ABNORMAL. */
548 static inline bool
549 bb_has_abnormal_pred (basic_block bb)
551 edge e;
552 edge_iterator ei;
554 FOR_EACH_EDGE (e, ei, bb->preds)
556 if (e->flags & EDGE_ABNORMAL)
557 return true;
559 return false;
562 /* Return the fallthru edge in EDGES if it exists, NULL otherwise. */
563 static inline edge
564 find_fallthru_edge (vec<edge, va_gc> *edges)
566 edge e;
567 edge_iterator ei;
569 FOR_EACH_EDGE (e, ei, edges)
570 if (e->flags & EDGE_FALLTHRU)
571 break;
573 return e;
576 /* Check tha probability is sane. */
578 static inline void
579 check_probability (int prob)
581 gcc_checking_assert (prob >= 0 && prob <= REG_BR_PROB_BASE);
584 /* Given PROB1 and PROB2, return PROB1*PROB2/REG_BR_PROB_BASE.
585 Used to combine BB probabilities. */
587 static inline int
588 combine_probabilities (int prob1, int prob2)
590 check_probability (prob1);
591 check_probability (prob2);
592 return RDIV (prob1 * prob2, REG_BR_PROB_BASE);
595 /* Apply scale factor SCALE on frequency or count FREQ. Use this
596 interface when potentially scaling up, so that SCALE is not
597 constrained to be < REG_BR_PROB_BASE. */
599 static inline gcov_type
600 apply_scale (gcov_type freq, gcov_type scale)
602 return RDIV (freq * scale, REG_BR_PROB_BASE);
605 /* Apply probability PROB on frequency or count FREQ. */
607 static inline gcov_type
608 apply_probability (gcov_type freq, int prob)
610 check_probability (prob);
611 return apply_scale (freq, prob);
614 /* Return inverse probability for PROB. */
616 static inline int
617 inverse_probability (int prob1)
619 check_probability (prob1);
620 return REG_BR_PROB_BASE - prob1;
623 /* Return true if BB has at least one abnormal outgoing edge. */
625 static inline bool
626 has_abnormal_or_eh_outgoing_edge_p (basic_block bb)
628 edge e;
629 edge_iterator ei;
631 FOR_EACH_EDGE (e, ei, bb->succs)
632 if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
633 return true;
635 return false;
637 #endif /* GCC_BASIC_BLOCK_H */