1 /* Define control flow data structures for the CFG.
2 Copyright (C) 1987-2023 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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.
10
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.
15
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/>. */
19
20 #ifndef GCC_BASIC_BLOCK_H
21 #define GCC_BASIC_BLOCK_H
22
23 #include <profile-count.h>
24
25 /* Control flow edge information. */
26 class GTY((user)) edge_def {
27 public:
28 /* The two blocks at the ends of the edge. */
29 basic_block src;
30 basic_block dest;
31
32 /* Instructions queued on the edge. */
33 union edge_def_insns {
34 gimple_seq g;
35 rtx_insn *r;
36 } insns;
37
38 /* Auxiliary info specific to a pass. */
39 void *aux;
40
41 /* Location of any goto implicit in the edge. */
42 location_t goto_locus;
43
44 /* The index number corresponding to this edge in the edge vector
45 dest->preds. */
46 unsigned int dest_idx;
47
48 int flags; /* see cfg-flags.def */
49 profile_probability probability;
50
51 /* Return count of edge E. */
52 inline profile_count count () const;
53 };
54
55 /* Masks for edge.flags. */
56 #define DEF_EDGE_FLAG(NAME,IDX) EDGE_##NAME = 1 << IDX ,
57 enum cfg_edge_flags {
58 #include "cfg-flags.def"
59 LAST_CFG_EDGE_FLAG /* this is only used for EDGE_ALL_FLAGS */
60 };
61 #undef DEF_EDGE_FLAG
62
63 /* Bit mask for all edge flags. */
64 #define EDGE_ALL_FLAGS ((LAST_CFG_EDGE_FLAG - 1) * 2 - 1)
65
66 /* The following four flags all indicate something special about an edge.
67 Test the edge flags on EDGE_COMPLEX to detect all forms of "strange"
68 control flow transfers. */
69 #define EDGE_COMPLEX \
70 (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_PRESERVE)
71
72 struct GTY(()) rtl_bb_info {
73 /* The first insn of the block is embedded into bb->il.x. */
74 /* The last insn of the block. */
75 rtx_insn *end_;
76
77 /* In CFGlayout mode points to insn notes/jumptables to be placed just before
78 and after the block. */
79 rtx_insn *header_;
80 rtx_insn *footer_;
81 };
82
83 struct GTY(()) gimple_bb_info {
84 /* Sequence of statements in this block. */
85 gimple_seq seq;
86
87 /* PHI nodes for this block. */
88 gimple_seq phi_nodes;
89 };
90
91 /* A basic block is a sequence of instructions with only one entry and
92 only one exit. If any one of the instructions are executed, they
93 will all be executed, and in sequence from first to last.
94
95 There may be COND_EXEC instructions in the basic block. The
96 COND_EXEC *instructions* will be executed -- but if the condition
97 is false the conditionally executed *expressions* will of course
98 not be executed. We don't consider the conditionally executed
99 expression (which might have side-effects) to be in a separate
100 basic block because the program counter will always be at the same
101 location after the COND_EXEC instruction, regardless of whether the
102 condition is true or not.
103
104 Basic blocks need not start with a label nor end with a jump insn.
105 For example, a previous basic block may just "conditionally fall"
106 into the succeeding basic block, and the last basic block need not
107 end with a jump insn. Block 0 is a descendant of the entry block.
108
109 A basic block beginning with two labels cannot have notes between
110 the labels.
111
112 Data for jump tables are stored in jump_insns that occur in no
113 basic block even though these insns can follow or precede insns in
114 basic blocks. */
115
116 /* Basic block information indexed by block number. */
117 struct GTY((chain_next ("%h.next_bb"), chain_prev ("%h.prev_bb"))) basic_block_def {
118 /* The edges into and out of the block. */
119 vec<edge, va_gc> *preds;
120 vec<edge, va_gc> *succs;
121
122 /* Auxiliary info specific to a pass. */
123 void *GTY ((skip (""))) aux;
124
125 /* Innermost loop containing the block. */
126 class loop *loop_father;
127
128 /* The dominance and postdominance information node. */
129 struct et_node * GTY ((skip (""))) dom[2];
130
131 /* Previous and next blocks in the chain. */
132 basic_block prev_bb;
133 basic_block next_bb;
134
135 union basic_block_il_dependent {
136 struct gimple_bb_info GTY ((tag ("0"))) gimple;
137 struct {
138 rtx_insn *head_;
139 struct rtl_bb_info * rtl;
140 } GTY ((tag ("1"))) x;
141 } GTY ((desc ("((%1.flags & BB_RTL) != 0)"))) il;
142
143 /* Various flags. See cfg-flags.def. */
144 int flags;
145
146 /* The index of this block. */
147 int index;
148
149 /* Expected number of executions: calculated in profile.cc. */
150 profile_count count;
151 };
152
153 /* This ensures that struct gimple_bb_info is smaller than
154 struct rtl_bb_info, so that inlining the former into basic_block_def
155 is the better choice. */
156 STATIC_ASSERT (sizeof (rtl_bb_info) >= sizeof (gimple_bb_info));
157
158 #define BB_FREQ_MAX 10000
159
160 /* Masks for basic_block.flags. */
161 #define DEF_BASIC_BLOCK_FLAG(NAME,IDX) BB_##NAME = 1 << IDX ,
162 enum cfg_bb_flags
163 {
164 #include "cfg-flags.def"
165 LAST_CFG_BB_FLAG /* this is only used for BB_ALL_FLAGS */
166 };
167 #undef DEF_BASIC_BLOCK_FLAG
168
169 /* Bit mask for all basic block flags. */
170 #define BB_ALL_FLAGS ((LAST_CFG_BB_FLAG - 1) * 2 - 1)
171
172 /* Bit mask for all basic block flags that must be preserved. These are
173 the bit masks that are *not* cleared by clear_bb_flags. */
174 #define BB_FLAGS_TO_PRESERVE \
175 (BB_DISABLE_SCHEDULE | BB_RTL | BB_NON_LOCAL_GOTO_TARGET \
176 | BB_HOT_PARTITION | BB_COLD_PARTITION)
177
178 /* Dummy bitmask for convenience in the hot/cold partitioning code. */
179 #define BB_UNPARTITIONED 0
180
181 /* Partitions, to be used when partitioning hot and cold basic blocks into
182 separate sections. */
183 #define BB_PARTITION(bb) ((bb)->flags & (BB_HOT_PARTITION|BB_COLD_PARTITION))
184 #define BB_SET_PARTITION(bb, part) do { \
185 basic_block bb_ = (bb); \
186 bb_->flags = ((bb_->flags & ~(BB_HOT_PARTITION|BB_COLD_PARTITION)) \
187 | (part)); \
188 } while (0)
189
190 #define BB_COPY_PARTITION(dstbb, srcbb) \
191 BB_SET_PARTITION (dstbb, BB_PARTITION (srcbb))
192
193 /* Defines for accessing the fields of the CFG structure for function FN. */
194 #define ENTRY_BLOCK_PTR_FOR_FN(FN) ((FN)->cfg->x_entry_block_ptr)
195 #define EXIT_BLOCK_PTR_FOR_FN(FN) ((FN)->cfg->x_exit_block_ptr)
196 #define basic_block_info_for_fn(FN) ((FN)->cfg->x_basic_block_info)
197 #define n_basic_blocks_for_fn(FN) ((FN)->cfg->x_n_basic_blocks)
198 #define n_edges_for_fn(FN) ((FN)->cfg->x_n_edges)
199 #define last_basic_block_for_fn(FN) ((FN)->cfg->x_last_basic_block)
200 #define label_to_block_map_for_fn(FN) ((FN)->cfg->x_label_to_block_map)
201 #define profile_status_for_fn(FN) ((FN)->cfg->x_profile_status)
202
203 #define BASIC_BLOCK_FOR_FN(FN,N) \
204 ((*basic_block_info_for_fn (FN))[(N)])
205 #define SET_BASIC_BLOCK_FOR_FN(FN,N,BB) \
206 ((*basic_block_info_for_fn (FN))[(N)] = (BB))
207
208 /* For iterating over basic blocks. */
209 #define FOR_BB_BETWEEN(BB, FROM, TO, DIR) \
210 for (BB = FROM; BB != TO; BB = BB->DIR)
211
212 #define FOR_EACH_BB_FN(BB, FN) \
213 FOR_BB_BETWEEN (BB, (FN)->cfg->x_entry_block_ptr->next_bb, (FN)->cfg->x_exit_block_ptr, next_bb)
214
215 #define FOR_EACH_BB_REVERSE_FN(BB, FN) \
216 FOR_BB_BETWEEN (BB, (FN)->cfg->x_exit_block_ptr->prev_bb, (FN)->cfg->x_entry_block_ptr, prev_bb)
217
218 /* For iterating over insns in basic block. */
219 #define FOR_BB_INSNS(BB, INSN) \
220 for ((INSN) = BB_HEAD (BB); \
221 (INSN) && (INSN) != NEXT_INSN (BB_END (BB)); \
222 (INSN) = NEXT_INSN (INSN))
223
224 /* For iterating over insns in basic block when we might remove the
225 current insn. */
226 #define FOR_BB_INSNS_SAFE(BB, INSN, CURR) \
227 for ((INSN) = BB_HEAD (BB), (CURR) = (INSN) ? NEXT_INSN ((INSN)): NULL; \
228 (INSN) && (INSN) != NEXT_INSN (BB_END (BB)); \
229 (INSN) = (CURR), (CURR) = (INSN) ? NEXT_INSN ((INSN)) : NULL)
230
231 #define FOR_BB_INSNS_REVERSE(BB, INSN) \
232 for ((INSN) = BB_END (BB); \
233 (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB)); \
234 (INSN) = PREV_INSN (INSN))
235
236 #define FOR_BB_INSNS_REVERSE_SAFE(BB, INSN, CURR) \
237 for ((INSN) = BB_END (BB),(CURR) = (INSN) ? PREV_INSN ((INSN)) : NULL; \
238 (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB)); \
239 (INSN) = (CURR), (CURR) = (INSN) ? PREV_INSN ((INSN)) : NULL)
240
241 /* Cycles through _all_ basic blocks, even the fake ones (entry and
242 exit block). */
243
244 #define FOR_ALL_BB_FN(BB, FN) \
245 for (BB = ENTRY_BLOCK_PTR_FOR_FN (FN); BB; BB = BB->next_bb)
246
247
248 /* Stuff for recording basic block info. */
249
250 /* For now, these will be functions (so that they can include checked casts
251 to rtx_insn. Once the underlying fields are converted from rtx
252 to rtx_insn, these can be converted back to macros. */
253
254 #define BB_HEAD(B) (B)->il.x.head_
255 #define BB_END(B) (B)->il.x.rtl->end_
256 #define BB_HEADER(B) (B)->il.x.rtl->header_
257 #define BB_FOOTER(B) (B)->il.x.rtl->footer_
258
259 /* Special block numbers [markers] for entry and exit.
260 Neither of them is supposed to hold actual statements. */
261 #define ENTRY_BLOCK (0)
262 #define EXIT_BLOCK (1)
263
264 /* The two blocks that are always in the cfg. */
265 #define NUM_FIXED_BLOCKS (2)
266
267 /* This is the value which indicates no edge is present. */
268 #define EDGE_INDEX_NO_EDGE -1
269
270 /* EDGE_INDEX returns an integer index for an edge, or EDGE_INDEX_NO_EDGE
271 if there is no edge between the 2 basic blocks. */
272 #define EDGE_INDEX(el, pred, succ) (find_edge_index ((el), (pred), (succ)))
273
274 /* INDEX_EDGE_PRED_BB and INDEX_EDGE_SUCC_BB return a pointer to the basic
275 block which is either the pred or succ end of the indexed edge. */
276 #define INDEX_EDGE_PRED_BB(el, index) ((el)->index_to_edge[(index)]->src)
277 #define INDEX_EDGE_SUCC_BB(el, index) ((el)->index_to_edge[(index)]->dest)
278
279 /* INDEX_EDGE returns a pointer to the edge. */
280 #define INDEX_EDGE(el, index) ((el)->index_to_edge[(index)])
281
282 /* Number of edges in the compressed edge list. */
283 #define NUM_EDGES(el) ((el)->num_edges)
284
285 /* BB is assumed to contain conditional jump. Return the fallthru edge. */
286 #define FALLTHRU_EDGE(bb) (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \
287 ? EDGE_SUCC ((bb), 0) : EDGE_SUCC ((bb), 1))
288
289 /* BB is assumed to contain conditional jump. Return the branch edge. */
290 #define BRANCH_EDGE(bb) (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \
291 ? EDGE_SUCC ((bb), 1) : EDGE_SUCC ((bb), 0))
292
293 /* Return expected execution frequency of the edge E. */
294 #define EDGE_FREQUENCY(e) e->count ().to_frequency (cfun)
295
296 /* Compute a scale factor (or probability) suitable for scaling of
297 gcov_type values via apply_probability() and apply_scale(). */
298 #define GCOV_COMPUTE_SCALE(num,den) \
299 ((den) ? RDIV ((num) * REG_BR_PROB_BASE, (den)) : REG_BR_PROB_BASE)
300
301 /* Return nonzero if edge is critical. */
302 #define EDGE_CRITICAL_P(e) (EDGE_COUNT ((e)->src->succs) >= 2 \
303 && EDGE_COUNT ((e)->dest->preds) >= 2)
304
305 #define EDGE_COUNT(ev) vec_safe_length (ev)
306 #define EDGE_I(ev,i) (*ev)[(i)]
307 #define EDGE_PRED(bb,i) (*(bb)->preds)[(i)]
308 #define EDGE_SUCC(bb,i) (*(bb)->succs)[(i)]
309
310 /* Returns true if BB has precisely one successor. */
311
312 inline bool
313 single_succ_p (const_basic_block bb)
314 {
315 return EDGE_COUNT (bb->succs) == 1;
316 }
317
318 /* Returns true if BB has precisely one predecessor. */
319
320 inline bool
321 single_pred_p (const_basic_block bb)
322 {
323 return EDGE_COUNT (bb->preds) == 1;
324 }
325
326 /* Returns the single successor edge of basic block BB. Aborts if
327 BB does not have exactly one successor. */
328
329 inline edge
330 single_succ_edge (const_basic_block bb)
331 {
332 gcc_checking_assert (single_succ_p (bb));
333 return EDGE_SUCC (bb, 0);
334 }
335
336 /* Returns the single predecessor edge of basic block BB. Aborts
337 if BB does not have exactly one predecessor. */
338
339 inline edge
340 single_pred_edge (const_basic_block bb)
341 {
342 gcc_checking_assert (single_pred_p (bb));
343 return EDGE_PRED (bb, 0);
344 }
345
346 /* Returns the single successor block of basic block BB. Aborts
347 if BB does not have exactly one successor. */
348
349 inline basic_block
350 single_succ (const_basic_block bb)
351 {
352 return single_succ_edge (bb)->dest;
353 }
354
355 /* Returns the single predecessor block of basic block BB. Aborts
356 if BB does not have exactly one predecessor.*/
357
358 inline basic_block
359 single_pred (const_basic_block bb)
360 {
361 return single_pred_edge (bb)->src;
362 }
363
364 /* Iterator object for edges. */
365
366 struct edge_iterator {
367 unsigned index;
368 vec<edge, va_gc> **container;
369 };
370
371 inline vec<edge, va_gc> *
372 ei_container (edge_iterator i)
373 {
374 gcc_checking_assert (i.container);
375 return *i.container;
376 }
377
378 #define ei_start(iter) ei_start_1 (&(iter))
379 #define ei_last(iter) ei_last_1 (&(iter))
380
381 /* Return an iterator pointing to the start of an edge vector. */
382 inline edge_iterator
383 ei_start_1 (vec<edge, va_gc> **ev)
384 {
385 edge_iterator i;
386
387 i.index = 0;
388 i.container = ev;
389
390 return i;
391 }
392
393 /* Return an iterator pointing to the last element of an edge
394 vector. */
395 inline edge_iterator
396 ei_last_1 (vec<edge, va_gc> **ev)
397 {
398 edge_iterator i;
399
400 i.index = EDGE_COUNT (*ev) - 1;
401 i.container = ev;
402
403 return i;
404 }
405
406 /* Is the iterator `i' at the end of the sequence? */
407 inline bool
408 ei_end_p (edge_iterator i)
409 {
410 return (i.index == EDGE_COUNT (ei_container (i)));
411 }
412
413 /* Is the iterator `i' at one position before the end of the
414 sequence? */
415 inline bool
416 ei_one_before_end_p (edge_iterator i)
417 {
418 return (i.index + 1 == EDGE_COUNT (ei_container (i)));
419 }
420
421 /* Advance the iterator to the next element. */
422 inline void
423 ei_next (edge_iterator *i)
424 {
425 gcc_checking_assert (i->index < EDGE_COUNT (ei_container (*i)));
426 i->index++;
427 }
428
429 /* Move the iterator to the previous element. */
430 inline void
431 ei_prev (edge_iterator *i)
432 {
433 gcc_checking_assert (i->index > 0);
434 i->index--;
435 }
436
437 /* Return the edge pointed to by the iterator `i'. */
438 inline edge
439 ei_edge (edge_iterator i)
440 {
441 return EDGE_I (ei_container (i), i.index);
442 }
443
444 /* Return an edge pointed to by the iterator. Do it safely so that
445 NULL is returned when the iterator is pointing at the end of the
446 sequence. */
447 inline edge
448 ei_safe_edge (edge_iterator i)
449 {
450 return !ei_end_p (i) ? ei_edge (i) : NULL;
451 }
452
453 /* Return 1 if we should continue to iterate. Return 0 otherwise.
454 *Edge P is set to the next edge if we are to continue to iterate
455 and NULL otherwise. */
456
457 inline bool
458 ei_cond (edge_iterator ei, edge *p)
459 {
460 if (!ei_end_p (ei))
461 {
462 *p = ei_edge (ei);
463 return 1;
464 }
465 else
466 {
467 *p = NULL;
468 return 0;
469 }
470 }
471
472 /* This macro serves as a convenient way to iterate each edge in a
473 vector of predecessor or successor edges. It must not be used when
474 an element might be removed during the traversal, otherwise
475 elements will be missed. Instead, use a for-loop like that shown
476 in the following pseudo-code:
477
478 FOR (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
479 {
480 IF (e != taken_edge)
481 remove_edge (e);
482 ELSE
483 ei_next (&ei);
484 }
485 */
486
487 #define FOR_EACH_EDGE(EDGE,ITER,EDGE_VEC) \
488 for ((ITER) = ei_start ((EDGE_VEC)); \
489 ei_cond ((ITER), &(EDGE)); \
490 ei_next (&(ITER)))
491
492 #define CLEANUP_EXPENSIVE 1 /* Do relatively expensive optimizations
493 except for edge forwarding */
494 #define CLEANUP_CROSSJUMP 2 /* Do crossjumping. */
495 #define CLEANUP_POST_REGSTACK 4 /* We run after reg-stack and need
496 to care REG_DEAD notes. */
497 #define CLEANUP_THREADING 8 /* Do jump threading. */
498 #define CLEANUP_NO_INSN_DEL 16 /* Do not try to delete trivially dead
499 insns. */
500 #define CLEANUP_CFGLAYOUT 32 /* Do cleanup in cfglayout mode. */
501 #define CLEANUP_CFG_CHANGED 64 /* The caller changed the CFG. */
502 #define CLEANUP_NO_PARTITIONING 128 /* Do not try to fix partitions. */
503 #define CLEANUP_FORCE_FAST_DCE 0x100 /* Force run_fast_dce to be called
504 at least once. */
505
506 /* Return true if BB is in a transaction. */
507
508 inline bool
509 bb_in_transaction (basic_block bb)
510 {
511 return bb->flags & BB_IN_TRANSACTION;
512 }
513
514 /* Return true when one of the predecessor edges of BB is marked with EDGE_EH. */
515 inline bool
516 bb_has_eh_pred (basic_block bb)
517 {
518 edge e;
519 edge_iterator ei;
520
521 FOR_EACH_EDGE (e, ei, bb->preds)
522 {
523 if (e->flags & EDGE_EH)
524 return true;
525 }
526 return false;
527 }
528
529 /* Return true when one of the predecessor edges of BB is marked with EDGE_ABNORMAL. */
530 inline bool
531 bb_has_abnormal_pred (basic_block bb)
532 {
533 edge e;
534 edge_iterator ei;
535
536 FOR_EACH_EDGE (e, ei, bb->preds)
537 {
538 if (e->flags & EDGE_ABNORMAL)
539 return true;
540 }
541 return false;
542 }
543
544 /* Return the fallthru edge in EDGES if it exists, NULL otherwise. */
545 inline edge
546 find_fallthru_edge (vec<edge, va_gc> *edges)
547 {
548 edge e;
549 edge_iterator ei;
550
551 FOR_EACH_EDGE (e, ei, edges)
552 if (e->flags & EDGE_FALLTHRU)
553 break;
554
555 return e;
556 }
557
558 /* Check tha probability is sane. */
559
560 inline void
561 check_probability (int prob)
562 {
563 gcc_checking_assert (prob >= 0 && prob <= REG_BR_PROB_BASE);
564 }
565
566 /* Given PROB1 and PROB2, return PROB1*PROB2/REG_BR_PROB_BASE.
567 Used to combine BB probabilities. */
568
569 inline int
570 combine_probabilities (int prob1, int prob2)
571 {
572 check_probability (prob1);
573 check_probability (prob2);
574 return RDIV (prob1 * prob2, REG_BR_PROB_BASE);
575 }
576
577 /* Apply scale factor SCALE on frequency or count FREQ. Use this
578 interface when potentially scaling up, so that SCALE is not
579 constrained to be < REG_BR_PROB_BASE. */
580
581 inline gcov_type
582 apply_scale (gcov_type freq, gcov_type scale)
583 {
584 return RDIV (freq * scale, REG_BR_PROB_BASE);
585 }
586
587 /* Apply probability PROB on frequency or count FREQ. */
588
589 inline gcov_type
590 apply_probability (gcov_type freq, int prob)
591 {
592 check_probability (prob);
593 return apply_scale (freq, prob);
594 }
595
596 /* Return inverse probability for PROB. */
597
598 inline int
599 inverse_probability (int prob1)
600 {
601 check_probability (prob1);
602 return REG_BR_PROB_BASE - prob1;
603 }
604
605 /* Return true if BB has at least one abnormal outgoing edge. */
606
607 inline bool
608 has_abnormal_or_eh_outgoing_edge_p (basic_block bb)
609 {
610 edge e;
611 edge_iterator ei;
612
613 FOR_EACH_EDGE (e, ei, bb->succs)
614 if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
615 return true;
616
617 return false;
618 }
619
620 /* Return true when one of the predecessor edges of BB is marked with
621 EDGE_ABNORMAL_CALL or EDGE_EH. */
622
623 inline bool
624 has_abnormal_call_or_eh_pred_edge_p (basic_block bb)
625 {
626 edge e;
627 edge_iterator ei;
628
629 FOR_EACH_EDGE (e, ei, bb->preds)
630 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
631 return true;
632
633 return false;
634 }
635
636 /* Return count of edge E. */
637 inline profile_count edge_def::count () const
638 {
639 return src->count.apply_probability (probability);
640 }
641
642 #endif /* GCC_BASIC_BLOCK_H */