]>
Commit | Line | Data |
---|---|---|
3245eea0 | 1 | /* Define control and data flow tables, and regsets. |
d9221e01 | 2 | Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004 |
8aab0f2b | 3 | Free Software Foundation, Inc. |
3245eea0 | 4 | |
1322177d | 5 | This file is part of GCC. |
3245eea0 | 6 | |
1322177d LB |
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 | |
10 | version. | |
3245eea0 | 11 | |
1322177d LB |
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 | |
15 | for more details. | |
3245eea0 CH |
16 | |
17 | You should have received a copy of the GNU General Public License | |
1322177d LB |
18 | along with GCC; see the file COPYING. If not, write to the Free |
19 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
20 | 02111-1307, USA. */ | |
3245eea0 | 21 | |
88657302 | 22 | #ifndef GCC_BASIC_BLOCK_H |
7f8a2125 | 23 | #define GCC_BASIC_BLOCK_H |
3245eea0 | 24 | |
19d18142 | 25 | #include "bitmap.h" |
5f6c11d6 | 26 | #include "sbitmap.h" |
e881bb1b | 27 | #include "varray.h" |
4e872036 | 28 | #include "partition.h" |
56f15830 | 29 | #include "hard-reg-set.h" |
6de9cd9a | 30 | #include "predict.h" |
19d18142 | 31 | |
b1dbfa1d BS |
32 | /* Head of register set linked list. */ |
33 | typedef bitmap_head regset_head; | |
6de9cd9a | 34 | |
b1dbfa1d BS |
35 | /* A pointer to a regset_head. */ |
36 | typedef bitmap regset; | |
37 | ||
38 | /* Initialize a new regset. */ | |
e2500fed | 39 | #define INIT_REG_SET(HEAD) bitmap_initialize (HEAD, 1) |
19d18142 RK |
40 | |
41 | /* Clear a register set by freeing up the linked list. */ | |
42 | #define CLEAR_REG_SET(HEAD) bitmap_clear (HEAD) | |
43 | ||
44 | /* Copy a register set to another register set. */ | |
45 | #define COPY_REG_SET(TO, FROM) bitmap_copy (TO, FROM) | |
46 | ||
d3a923ee RH |
47 | /* Compare two register sets. */ |
48 | #define REG_SET_EQUAL_P(A, B) bitmap_equal_p (A, B) | |
49 | ||
19d18142 RK |
50 | /* `and' a register set with a second register set. */ |
51 | #define AND_REG_SET(TO, FROM) bitmap_operation (TO, TO, FROM, BITMAP_AND) | |
52 | ||
53 | /* `and' the complement of a register set with a register set. */ | |
54 | #define AND_COMPL_REG_SET(TO, FROM) \ | |
55 | bitmap_operation (TO, TO, FROM, BITMAP_AND_COMPL) | |
56 | ||
57 | /* Inclusive or a register set with a second register set. */ | |
58 | #define IOR_REG_SET(TO, FROM) bitmap_operation (TO, TO, FROM, BITMAP_IOR) | |
59 | ||
d3a923ee RH |
60 | /* Exclusive or a register set with a second register set. */ |
61 | #define XOR_REG_SET(TO, FROM) bitmap_operation (TO, TO, FROM, BITMAP_XOR) | |
62 | ||
19d18142 RK |
63 | /* Or into TO the register set FROM1 `and'ed with the complement of FROM2. */ |
64 | #define IOR_AND_COMPL_REG_SET(TO, FROM1, FROM2) \ | |
65 | bitmap_ior_and_compl (TO, FROM1, FROM2) | |
916b1701 MM |
66 | |
67 | /* Clear a single register in a register set. */ | |
19d18142 | 68 | #define CLEAR_REGNO_REG_SET(HEAD, REG) bitmap_clear_bit (HEAD, REG) |
916b1701 MM |
69 | |
70 | /* Set a single register in a register set. */ | |
19d18142 | 71 | #define SET_REGNO_REG_SET(HEAD, REG) bitmap_set_bit (HEAD, REG) |
916b1701 MM |
72 | |
73 | /* Return true if a register is set in a register set. */ | |
19d18142 | 74 | #define REGNO_REG_SET_P(TO, REG) bitmap_bit_p (TO, REG) |
916b1701 MM |
75 | |
76 | /* Copy the hard registers in a register set to the hard register set. */ | |
f55ade6e | 77 | extern void reg_set_to_hard_reg_set (HARD_REG_SET *, bitmap); |
916b1701 MM |
78 | #define REG_SET_TO_HARD_REG_SET(TO, FROM) \ |
79 | do { \ | |
916b1701 | 80 | CLEAR_HARD_REG_SET (TO); \ |
efc9bd41 | 81 | reg_set_to_hard_reg_set (&TO, FROM); \ |
916b1701 MM |
82 | } while (0) |
83 | ||
84 | /* Loop over all registers in REGSET, starting with MIN, setting REGNUM to the | |
eebedaa5 | 85 | register number and executing CODE for all registers that are set. */ |
916b1701 | 86 | #define EXECUTE_IF_SET_IN_REG_SET(REGSET, MIN, REGNUM, CODE) \ |
19d18142 | 87 | EXECUTE_IF_SET_IN_BITMAP (REGSET, MIN, REGNUM, CODE) |
916b1701 MM |
88 | |
89 | /* Loop over all registers in REGSET1 and REGSET2, starting with MIN, setting | |
90 | REGNUM to the register number and executing CODE for all registers that are | |
eebedaa5 | 91 | set in the first regset and not set in the second. */ |
916b1701 | 92 | #define EXECUTE_IF_AND_COMPL_IN_REG_SET(REGSET1, REGSET2, MIN, REGNUM, CODE) \ |
19d18142 | 93 | EXECUTE_IF_AND_COMPL_IN_BITMAP (REGSET1, REGSET2, MIN, REGNUM, CODE) |
916b1701 | 94 | |
22fa5b8a MM |
95 | /* Loop over all registers in REGSET1 and REGSET2, starting with MIN, setting |
96 | REGNUM to the register number and executing CODE for all registers that are | |
eebedaa5 | 97 | set in both regsets. */ |
22fa5b8a MM |
98 | #define EXECUTE_IF_AND_IN_REG_SET(REGSET1, REGSET2, MIN, REGNUM, CODE) \ |
99 | EXECUTE_IF_AND_IN_BITMAP (REGSET1, REGSET2, MIN, REGNUM, CODE) | |
100 | ||
916b1701 | 101 | /* Allocate a register set with oballoc. */ |
19d18142 | 102 | #define OBSTACK_ALLOC_REG_SET(OBSTACK) BITMAP_OBSTACK_ALLOC (OBSTACK) |
916b1701 | 103 | |
ee25a7a5 | 104 | /* Initialize a register set. Returns the new register set. */ |
e2500fed | 105 | #define INITIALIZE_REG_SET(HEAD) bitmap_initialize (&HEAD, 1) |
19d18142 RK |
106 | |
107 | /* Do any cleanup needed on a regset when it is no longer used. */ | |
108 | #define FREE_REG_SET(REGSET) BITMAP_FREE(REGSET) | |
109 | ||
110 | /* Do any one-time initializations needed for regsets. */ | |
111 | #define INIT_ONCE_REG_SET() BITMAP_INIT_ONCE () | |
112 | ||
113 | /* Grow any tables needed when the number of registers is calculated | |
114 | or extended. For the linked list allocation, nothing needs to | |
115 | be done, other than zero the statistics on the first allocation. */ | |
7f8a2125 | 116 | #define MAX_REGNO_REG_SET(NUM_REGS, NEW_P, RENUMBER_P) |
916b1701 | 117 | |
4977bab6 ZW |
118 | /* Type we use to hold basic block counters. Should be at least |
119 | 64bit. Although a counter cannot be negative, we use a signed | |
120 | type, because erroneous negative counts can be generated when the | |
121 | flow graph is manipulated by various optimizations. A signed type | |
32dd366d | 122 | makes those easy to detect. */ |
b2aec5c0 JH |
123 | typedef HOST_WIDEST_INT gcov_type; |
124 | ||
e881bb1b | 125 | /* Control flow edge information. */ |
6de9cd9a DN |
126 | struct edge_def GTY((chain_next ("%h.pred_next"))) |
127 | { | |
e881bb1b | 128 | /* Links through the predecessor and successor lists. */ |
6de9cd9a DN |
129 | struct edge_def *pred_next; |
130 | struct edge_def *succ_next; | |
3245eea0 | 131 | |
e881bb1b | 132 | /* The two blocks at the ends of the edge. */ |
6de9cd9a DN |
133 | struct basic_block_def *src; |
134 | struct basic_block_def *dest; | |
e881bb1b RH |
135 | |
136 | /* Instructions queued on the edge. */ | |
6de9cd9a DN |
137 | union edge_def_insns { |
138 | rtx GTY ((tag ("0"))) r; | |
139 | tree GTY ((tag ("1"))) t; | |
140 | } GTY ((desc ("ir_type ()"))) insns; | |
e881bb1b RH |
141 | |
142 | /* Auxiliary info specific to a pass. */ | |
6de9cd9a | 143 | PTR GTY ((skip (""))) aux; |
3245eea0 | 144 | |
e881bb1b RH |
145 | int flags; /* see EDGE_* below */ |
146 | int probability; /* biased by REG_BR_PROB_BASE */ | |
b2aec5c0 | 147 | gcov_type count; /* Expected number of executions calculated |
51891abe | 148 | in profile.c */ |
750054a2 CT |
149 | bool crossing_edge; /* Crosses between hot and cold sections, when |
150 | we do partitioning. */ | |
6de9cd9a DN |
151 | }; |
152 | ||
153 | typedef struct edge_def *edge; | |
3245eea0 | 154 | |
6c208acd NS |
155 | #define EDGE_FALLTHRU 1 /* 'Straight line' flow */ |
156 | #define EDGE_ABNORMAL 2 /* Strange flow, like computed | |
157 | label, or eh */ | |
158 | #define EDGE_ABNORMAL_CALL 4 /* Call with abnormal exit | |
159 | like an exception, or sibcall */ | |
160 | #define EDGE_EH 8 /* Exception throw */ | |
161 | #define EDGE_FAKE 16 /* Not a real edge (profile.c) */ | |
162 | #define EDGE_DFS_BACK 32 /* A backwards edge */ | |
163 | #define EDGE_CAN_FALLTHRU 64 /* Candidate for straight line | |
4b7e68e7 | 164 | flow. */ |
35b07080 | 165 | #define EDGE_IRREDUCIBLE_LOOP 128 /* Part of irreducible loop. */ |
1722c2c8 | 166 | #define EDGE_SIBCALL 256 /* Edge from sibcall to exit. */ |
65f43cdf | 167 | #define EDGE_LOOP_EXIT 512 /* Exit of a loop. */ |
6de9cd9a DN |
168 | #define EDGE_TRUE_VALUE 1024 /* Edge taken when controlling |
169 | predicate is non zero. */ | |
170 | #define EDGE_FALSE_VALUE 2048 /* Edge taken when controlling | |
171 | predicate is zero. */ | |
172 | #define EDGE_EXECUTABLE 4096 /* Edge is executable. Only | |
173 | valid during SSA-CCP. */ | |
174 | #define EDGE_ALL_FLAGS 8191 | |
3245eea0 | 175 | |
65b98a02 JW |
176 | #define EDGE_COMPLEX (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH) |
177 | ||
cdb23767 | 178 | /* Counter summary from the last set of coverage counts read by |
71c0e7fc | 179 | profile.c. */ |
cdb23767 NS |
180 | extern const struct gcov_ctr_summary *profile_info; |
181 | ||
3d436d2a ZD |
182 | /* Declared in cfgloop.h. */ |
183 | struct loop; | |
184 | struct loops; | |
3245eea0 | 185 | |
6de9cd9a DN |
186 | /* Declared in tree-flow.h. */ |
187 | struct bb_ann_d; | |
188 | ||
e68e3108 MM |
189 | /* A basic block is a sequence of instructions with only entry and |
190 | only one exit. If any one of the instructions are executed, they | |
191 | will all be executed, and in sequence from first to last. | |
192 | ||
193 | There may be COND_EXEC instructions in the basic block. The | |
194 | COND_EXEC *instructions* will be executed -- but if the condition | |
195 | is false the conditionally executed *expressions* will of course | |
196 | not be executed. We don't consider the conditionally executed | |
197 | expression (which might have side-effects) to be in a separate | |
198 | basic block because the program counter will always be at the same | |
199 | location after the COND_EXEC instruction, regardless of whether the | |
200 | condition is true or not. | |
201 | ||
202 | Basic blocks need not start with a label nor end with a jump insn. | |
b53978a3 JO |
203 | For example, a previous basic block may just "conditionally fall" |
204 | into the succeeding basic block, and the last basic block need not | |
205 | end with a jump insn. Block 0 is a descendant of the entry block. | |
206 | ||
207 | A basic block beginning with two labels cannot have notes between | |
208 | the labels. | |
209 | ||
210 | Data for jump tables are stored in jump_insns that occur in no | |
211 | basic block even though these insns can follow or precede insns in | |
212 | basic blocks. */ | |
213 | ||
e881bb1b | 214 | /* Basic block information indexed by block number. */ |
6de9cd9a DN |
215 | struct basic_block_def GTY((chain_next ("%h.next_bb"), chain_prev ("%h.prev_bb"))) |
216 | { | |
e881bb1b | 217 | /* The first and last insns of the block. */ |
6de9cd9a DN |
218 | rtx head_; |
219 | rtx end_; | |
3245eea0 | 220 | |
6de9cd9a DN |
221 | /* Pointers to the first and last trees of the block. */ |
222 | tree stmt_list; | |
2b1d9dc0 | 223 | |
e881bb1b | 224 | /* The edges into and out of the block. */ |
6de9cd9a DN |
225 | edge pred; |
226 | edge succ; | |
4d1d8045 | 227 | |
e68e3108 MM |
228 | /* Liveness info. */ |
229 | ||
230 | /* The registers that are modified within this in block. */ | |
6de9cd9a | 231 | bitmap GTY ((skip (""))) local_set; |
e68e3108 MM |
232 | /* The registers that are conditionally modified within this block. |
233 | In other words, registers that are set only as part of a | |
234 | COND_EXEC. */ | |
6de9cd9a | 235 | bitmap GTY ((skip (""))) cond_local_set; |
e68e3108 MM |
236 | /* The registers that are live on entry to this block. |
237 | ||
238 | Note that in SSA form, global_live_at_start does not reflect the | |
239 | use of regs in phi functions, since the liveness of these regs | |
240 | may depend on which edge was taken into the block. */ | |
6de9cd9a | 241 | bitmap GTY ((skip (""))) global_live_at_start; |
e68e3108 | 242 | /* The registers that are live on exit from this block. */ |
6de9cd9a | 243 | bitmap GTY ((skip (""))) global_live_at_end; |
4d1d8045 | 244 | |
e881bb1b | 245 | /* Auxiliary info specific to a pass. */ |
6de9cd9a | 246 | PTR GTY ((skip (""))) aux; |
3245eea0 | 247 | |
0b17ab2f RH |
248 | /* The index of this block. */ |
249 | int index; | |
336a6399 | 250 | |
918ed612 | 251 | /* Previous and next blocks in the chain. */ |
6de9cd9a DN |
252 | struct basic_block_def *prev_bb; |
253 | struct basic_block_def *next_bb; | |
918ed612 | 254 | |
52a11cbf RH |
255 | /* The loop depth of this block. */ |
256 | int loop_depth; | |
51891abe | 257 | |
6de9cd9a DN |
258 | /* Innermost loop containing the block. */ |
259 | struct loop * GTY ((skip (""))) loop_father; | |
2ecfd709 | 260 | |
d47cc544 | 261 | /* The dominance and postdominance information node. */ |
6de9cd9a | 262 | struct et_node * GTY ((skip (""))) dom[2]; |
d47cc544 | 263 | |
52a11cbf | 264 | /* Expected number of executions: calculated in profile.c. */ |
b2aec5c0 | 265 | gcov_type count; |
7f8a2125 | 266 | |
861f9cd0 JH |
267 | /* Expected frequency. Normalized to be in range 0 to BB_FREQ_MAX. */ |
268 | int frequency; | |
006844a3 DN |
269 | |
270 | /* Various flags. See BB_* below. */ | |
271 | int flags; | |
bc35512f | 272 | |
750054a2 CT |
273 | /* Which section block belongs in, when partitioning basic blocks. */ |
274 | int partition; | |
275 | ||
6de9cd9a DN |
276 | /* The data used by basic block copying and reordering functions. */ |
277 | struct reorder_block_def * GTY ((skip (""))) rbi; | |
278 | ||
279 | /* Annotations used at the tree level. */ | |
280 | struct bb_ann_d *tree_annotations; | |
281 | }; | |
282 | ||
283 | typedef struct basic_block_def *basic_block; | |
284 | ||
285 | /* Structure to hold information about the blocks during reordering and | |
286 | copying. */ | |
287 | ||
288 | typedef struct reorder_block_def | |
289 | { | |
290 | rtx header; | |
291 | rtx footer; | |
292 | basic_block next; | |
293 | basic_block original; | |
294 | /* Used by loop copying. */ | |
295 | basic_block copy; | |
296 | int duplicated; | |
297 | ||
298 | /* These fields are used by bb-reorder pass. */ | |
299 | int visited; | |
300 | } *reorder_block_def; | |
7f8a2125 | 301 | |
861f9cd0 | 302 | #define BB_FREQ_MAX 10000 |
e881bb1b | 303 | |
006844a3 | 304 | /* Masks for basic_block.flags. */ |
38c1593d JH |
305 | #define BB_DIRTY 1 |
306 | #define BB_NEW 2 | |
307 | #define BB_REACHABLE 4 | |
2ecfd709 | 308 | #define BB_VISITED 8 |
3d436d2a ZD |
309 | #define BB_IRREDUCIBLE_LOOP 16 |
310 | #define BB_SUPERBLOCK 32 | |
006844a3 | 311 | |
750054a2 CT |
312 | /* Partitions, to be used when partitioning hot and cold basic blocks into |
313 | separate sections. */ | |
314 | #define UNPARTITIONED 0 | |
315 | #define HOT_PARTITION 1 | |
316 | #define COLD_PARTITION 2 | |
317 | ||
e881bb1b RH |
318 | /* Number of basic blocks in the current function. */ |
319 | ||
0b17ab2f | 320 | extern int n_basic_blocks; |
e881bb1b | 321 | |
d55bc081 ZD |
322 | /* First free basic block number. */ |
323 | ||
bf77398c | 324 | extern int last_basic_block; |
d55bc081 | 325 | |
d3a923ee RH |
326 | /* Number of edges in the current function. */ |
327 | ||
328 | extern int n_edges; | |
329 | ||
e881bb1b RH |
330 | /* Index by basic block number, get basic block struct info. */ |
331 | ||
6de9cd9a | 332 | extern GTY(()) varray_type basic_block_info; |
e881bb1b RH |
333 | |
334 | #define BASIC_BLOCK(N) (VARRAY_BB (basic_block_info, (N))) | |
3245eea0 | 335 | |
918ed612 ZD |
336 | /* For iterating over basic blocks. */ |
337 | #define FOR_BB_BETWEEN(BB, FROM, TO, DIR) \ | |
338 | for (BB = FROM; BB != TO; BB = BB->DIR) | |
339 | ||
340 | #define FOR_EACH_BB(BB) \ | |
341 | FOR_BB_BETWEEN (BB, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR, next_bb) | |
342 | ||
343 | #define FOR_EACH_BB_REVERSE(BB) \ | |
344 | FOR_BB_BETWEEN (BB, EXIT_BLOCK_PTR->prev_bb, ENTRY_BLOCK_PTR, prev_bb) | |
345 | ||
50654f6c ZD |
346 | /* For iterating over insns in basic block. */ |
347 | #define FOR_BB_INSNS(BB, INSN) \ | |
348 | for ((INSN) = BB_HEAD (BB); \ | |
349 | (INSN) != NEXT_INSN (BB_END (BB)); \ | |
350 | (INSN) = NEXT_INSN (INSN)) | |
351 | ||
352 | #define FOR_BB_INSNS_REVERSE(BB, INSN) \ | |
353 | for ((INSN) = BB_END (BB); \ | |
354 | (INSN) != PREV_INSN (BB_HEAD (BB)); \ | |
355 | (INSN) = PREV_INSN (INSN)) | |
356 | ||
ed8d2920 MM |
357 | /* Cycles through _all_ basic blocks, even the fake ones (entry and |
358 | exit block). */ | |
359 | ||
360 | #define FOR_ALL_BB(BB) \ | |
361 | for (BB = ENTRY_BLOCK_PTR; BB; BB = BB->next_bb) | |
362 | ||
19d18142 RK |
363 | /* What registers are live at the setjmp call. */ |
364 | ||
365 | extern regset regs_live_at_setjmp; | |
366 | ||
402209ff JH |
367 | /* Special labels found during CFG build. */ |
368 | ||
a8106207 DM |
369 | extern GTY(()) rtx label_value_list; |
370 | extern GTY(()) rtx tail_recursion_label_list; | |
402209ff JH |
371 | |
372 | extern struct obstack flow_obstack; | |
373 | ||
3245eea0 CH |
374 | /* Indexed by n, gives number of basic block that (REG n) is used in. |
375 | If the value is REG_BLOCK_GLOBAL (-2), | |
376 | it means (REG n) is used in more than one basic block. | |
377 | REG_BLOCK_UNKNOWN (-1) means it hasn't been seen yet so we don't know. | |
378 | This information remains valid for the rest of the compilation | |
379 | of the current function; it is used to control register allocation. */ | |
380 | ||
381 | #define REG_BLOCK_UNKNOWN -1 | |
382 | #define REG_BLOCK_GLOBAL -2 | |
b1f21e0a | 383 | |
6feacd09 | 384 | #define REG_BASIC_BLOCK(N) (VARRAY_REG (reg_n_info, N)->basic_block) |
5ece9746 JL |
385 | \f |
386 | /* Stuff for recording basic block info. */ | |
387 | ||
a813c111 SB |
388 | #define BB_HEAD(B) (B)->head_ |
389 | #define BB_END(B) (B)->end_ | |
2b1d9dc0 | 390 | |
5ece9746 JL |
391 | /* Special block numbers [markers] for entry and exit. */ |
392 | #define ENTRY_BLOCK (-1) | |
393 | #define EXIT_BLOCK (-2) | |
394 | ||
eebedaa5 | 395 | /* Special block number not valid for any block. */ |
b53978a3 JO |
396 | #define INVALID_BLOCK (-3) |
397 | ||
e881bb1b | 398 | /* Similarly, block pointers for the edge list. */ |
6de9cd9a DN |
399 | extern GTY(()) basic_block ENTRY_BLOCK_PTR; |
400 | extern GTY(()) basic_block EXIT_BLOCK_PTR; | |
e881bb1b | 401 | |
0b17ab2f | 402 | #define BLOCK_NUM(INSN) (BLOCK_FOR_INSN (INSN)->index + 0) |
ba4f7968 | 403 | #define set_block_for_insn(INSN, BB) (BLOCK_FOR_INSN (INSN) = BB) |
e881bb1b | 404 | |
f55ade6e AJ |
405 | extern void compute_bb_for_insn (void); |
406 | extern void free_bb_for_insn (void); | |
407 | extern void update_bb_for_insn (basic_block); | |
e881bb1b | 408 | |
bb8a619e | 409 | extern void free_basic_block_vars (void); |
52becdc0 | 410 | |
f55ade6e | 411 | extern void insert_insn_on_edge (rtx, edge); |
ff25ef99 | 412 | bool safe_insert_insn_on_edge (rtx, edge); |
3dec4024 | 413 | |
f55ade6e AJ |
414 | extern void commit_edge_insertions (void); |
415 | extern void commit_edge_insertions_watch_calls (void); | |
416 | ||
417 | extern void remove_fake_edges (void); | |
418 | extern void add_noreturn_fake_exit_edges (void); | |
419 | extern void connect_infinite_loops_to_exit (void); | |
f55ade6e AJ |
420 | extern edge unchecked_make_edge (basic_block, basic_block, int); |
421 | extern edge cached_make_edge (sbitmap *, basic_block, basic_block, int); | |
422 | extern edge make_edge (basic_block, basic_block, int); | |
423 | extern edge make_single_succ_edge (basic_block, basic_block, int); | |
424 | extern void remove_edge (edge); | |
425 | extern void redirect_edge_succ (edge, basic_block); | |
426 | extern edge redirect_edge_succ_nodup (edge, basic_block); | |
427 | extern void redirect_edge_pred (edge, basic_block); | |
428 | extern basic_block create_basic_block_structure (rtx, rtx, rtx, basic_block); | |
429 | extern void clear_bb_flags (void); | |
f55ade6e AJ |
430 | extern void flow_reverse_top_sort_order_compute (int *); |
431 | extern int flow_depth_first_order_compute (int *, int *); | |
432 | extern void flow_preorder_transversal_compute (int *); | |
433 | extern int dfs_enumerate_from (basic_block, int, | |
434 | bool (*)(basic_block, void *), | |
435 | basic_block *, int, void *); | |
436 | extern void dump_edge_info (FILE *, edge, int); | |
6de9cd9a | 437 | extern void brief_dump_cfg (FILE *); |
f55ade6e AJ |
438 | extern void clear_edges (void); |
439 | extern void mark_critical_edges (void); | |
440 | extern rtx first_insn_after_basic_block_note (basic_block); | |
10c4b247 | 441 | |
c05ffc49 BS |
442 | /* Structure to group all of the information to process IF-THEN and |
443 | IF-THEN-ELSE blocks for the conditional execution support. This | |
444 | needs to be in a public file in case the IFCVT macros call | |
445 | functions passing the ce_if_block data structure. */ | |
446 | ||
447 | typedef struct ce_if_block | |
448 | { | |
449 | basic_block test_bb; /* First test block. */ | |
450 | basic_block then_bb; /* THEN block. */ | |
451 | basic_block else_bb; /* ELSE block or NULL. */ | |
452 | basic_block join_bb; /* Join THEN/ELSE blocks. */ | |
453 | basic_block last_test_bb; /* Last bb to hold && or || tests. */ | |
454 | int num_multiple_test_blocks; /* # of && and || basic blocks. */ | |
455 | int num_and_and_blocks; /* # of && blocks. */ | |
456 | int num_or_or_blocks; /* # of || blocks. */ | |
457 | int num_multiple_test_insns; /* # of insns in && and || blocks. */ | |
458 | int and_and_p; /* Complex test is &&. */ | |
459 | int num_then_insns; /* # of insns in THEN block. */ | |
460 | int num_else_insns; /* # of insns in ELSE block. */ | |
461 | int pass; /* Pass number. */ | |
462 | ||
463 | #ifdef IFCVT_EXTRA_FIELDS | |
464 | IFCVT_EXTRA_FIELDS /* Any machine dependent fields. */ | |
465 | #endif | |
466 | ||
467 | } ce_if_block_t; | |
468 | ||
410538ea | 469 | /* This structure maintains an edge list vector. */ |
7f8a2125 | 470 | struct edge_list |
410538ea AM |
471 | { |
472 | int num_blocks; | |
473 | int num_edges; | |
474 | edge *index_to_edge; | |
475 | }; | |
476 | ||
477 | /* This is the value which indicates no edge is present. */ | |
478 | #define EDGE_INDEX_NO_EDGE -1 | |
479 | ||
480 | /* EDGE_INDEX returns an integer index for an edge, or EDGE_INDEX_NO_EDGE | |
481 | if there is no edge between the 2 basic blocks. */ | |
482 | #define EDGE_INDEX(el, pred, succ) (find_edge_index ((el), (pred), (succ))) | |
483 | ||
484 | /* INDEX_EDGE_PRED_BB and INDEX_EDGE_SUCC_BB return a pointer to the basic | |
485 | block which is either the pred or succ end of the indexed edge. */ | |
486 | #define INDEX_EDGE_PRED_BB(el, index) ((el)->index_to_edge[(index)]->src) | |
487 | #define INDEX_EDGE_SUCC_BB(el, index) ((el)->index_to_edge[(index)]->dest) | |
488 | ||
489 | /* INDEX_EDGE returns a pointer to the edge. */ | |
490 | #define INDEX_EDGE(el, index) ((el)->index_to_edge[(index)]) | |
491 | ||
492 | /* Number of edges in the compressed edge list. */ | |
493 | #define NUM_EDGES(el) ((el)->num_edges) | |
494 | ||
7a442791 JH |
495 | /* BB is assumed to contain conditional jump. Return the fallthru edge. */ |
496 | #define FALLTHRU_EDGE(bb) ((bb)->succ->flags & EDGE_FALLTHRU \ | |
497 | ? (bb)->succ : (bb)->succ->succ_next) | |
498 | ||
499 | /* BB is assumed to contain conditional jump. Return the branch edge. */ | |
500 | #define BRANCH_EDGE(bb) ((bb)->succ->flags & EDGE_FALLTHRU \ | |
501 | ? (bb)->succ->succ_next : (bb)->succ) | |
502 | ||
134d3a2e JH |
503 | /* Return expected execution frequency of the edge E. */ |
504 | #define EDGE_FREQUENCY(e) (((e)->src->frequency \ | |
505 | * (e)->probability \ | |
506 | + REG_BR_PROB_BASE / 2) \ | |
507 | / REG_BR_PROB_BASE) | |
508 | ||
4262e623 JH |
509 | /* Return nonzero if edge is critical. */ |
510 | #define EDGE_CRITICAL_P(e) ((e)->src->succ->succ_next \ | |
511 | && (e)->dest->pred->pred_next) | |
512 | ||
f55ade6e AJ |
513 | struct edge_list * create_edge_list (void); |
514 | void free_edge_list (struct edge_list *); | |
515 | void print_edge_list (FILE *, struct edge_list *); | |
516 | void verify_edge_list (FILE *, struct edge_list *); | |
517 | int find_edge_index (struct edge_list *, basic_block, basic_block); | |
6de9cd9a | 518 | edge find_edge (basic_block, basic_block); |
410538ea | 519 | |
49c3bb12 | 520 | |
d3a923ee RH |
521 | enum update_life_extent |
522 | { | |
715e7fbc RH |
523 | UPDATE_LIFE_LOCAL = 0, |
524 | UPDATE_LIFE_GLOBAL = 1, | |
5a425893 | 525 | UPDATE_LIFE_GLOBAL_RM_NOTES = 2 |
d3a923ee RH |
526 | }; |
527 | ||
49c3bb12 RH |
528 | /* Flags for life_analysis and update_life_info. */ |
529 | ||
530 | #define PROP_DEATH_NOTES 1 /* Create DEAD and UNUSED notes. */ | |
531 | #define PROP_LOG_LINKS 2 /* Create LOG_LINKS. */ | |
532 | #define PROP_REG_INFO 4 /* Update regs_ever_live et al. */ | |
533 | #define PROP_KILL_DEAD_CODE 8 /* Remove dead code. */ | |
534 | #define PROP_SCAN_DEAD_CODE 16 /* Scan for dead code. */ | |
11f68165 JW |
535 | #define PROP_ALLOW_CFG_CHANGES 32 /* Allow the CFG to be changed |
536 | by dead code removal. */ | |
537 | #define PROP_AUTOINC 64 /* Create autoinc mem references. */ | |
5a133afd | 538 | #define PROP_EQUAL_NOTES 128 /* Take into account REG_EQUAL notes. */ |
5149f070 | 539 | #define PROP_SCAN_DEAD_STORES 256 /* Scan for dead code. */ |
df2ef49b AM |
540 | #define PROP_ASM_SCAN 512 /* Internal flag used within flow.c |
541 | to flag analysis of asms. */ | |
5149f070 JH |
542 | #define PROP_FINAL (PROP_DEATH_NOTES | PROP_LOG_LINKS \ |
543 | | PROP_REG_INFO | PROP_KILL_DEAD_CODE \ | |
544 | | PROP_SCAN_DEAD_CODE | PROP_AUTOINC \ | |
545 | | PROP_ALLOW_CFG_CHANGES \ | |
546 | | PROP_SCAN_DEAD_STORES) | |
23bd7a93 JH |
547 | #define PROP_POSTRELOAD (PROP_DEATH_NOTES \ |
548 | | PROP_KILL_DEAD_CODE \ | |
549 | | PROP_SCAN_DEAD_CODE | PROP_AUTOINC \ | |
550 | | PROP_SCAN_DEAD_STORES) | |
5d6a16e2 | 551 | |
e0bb17a8 | 552 | #define CLEANUP_EXPENSIVE 1 /* Do relatively expensive optimizations |
46fac664 JH |
553 | except for edge forwarding */ |
554 | #define CLEANUP_CROSSJUMP 2 /* Do crossjumping. */ | |
555 | #define CLEANUP_POST_REGSTACK 4 /* We run after reg-stack and need | |
556 | to care REG_DEAD notes. */ | |
4793dca1 JH |
557 | #define CLEANUP_PRE_SIBCALL 8 /* Do not get confused by code hidden |
558 | inside call_placeholders.. */ | |
0068fd96 JH |
559 | #define CLEANUP_PRE_LOOP 16 /* Take care to preserve syntactic loop |
560 | notes. */ | |
635559ab | 561 | #define CLEANUP_UPDATE_LIFE 32 /* Keep life information up to date. */ |
8ecba28a | 562 | #define CLEANUP_THREADING 64 /* Do jump threading. */ |
95479831 DM |
563 | #define CLEANUP_NO_INSN_DEL 128 /* Do not try to delete trivially dead |
564 | insns. */ | |
bc35512f | 565 | #define CLEANUP_CFGLAYOUT 256 /* Do cleanup in cfglayout mode. */ |
23bd7a93 | 566 | #define CLEANUP_LOG_LINKS 512 /* Update log links. */ |
f55ade6e AJ |
567 | extern void life_analysis (rtx, FILE *, int); |
568 | extern int update_life_info (sbitmap, enum update_life_extent, int); | |
569 | extern int update_life_info_in_dirty_blocks (enum update_life_extent, int); | |
570 | extern int count_or_remove_death_notes (sbitmap, int); | |
571 | extern int propagate_block (basic_block, regset, regset, regset, int); | |
292f3869 RH |
572 | |
573 | struct propagate_block_info; | |
f55ade6e | 574 | extern rtx propagate_one_insn (struct propagate_block_info *, rtx); |
292f3869 | 575 | extern struct propagate_block_info *init_propagate_block_info |
f55ade6e AJ |
576 | (basic_block, regset, regset, regset, int); |
577 | extern void free_propagate_block_info (struct propagate_block_info *); | |
d3a923ee | 578 | |
077692c6 | 579 | /* In lcm.c */ |
f55ade6e AJ |
580 | extern struct edge_list *pre_edge_lcm (FILE *, int, sbitmap *, sbitmap *, |
581 | sbitmap *, sbitmap *, sbitmap **, | |
582 | sbitmap **); | |
583 | extern struct edge_list *pre_edge_rev_lcm (FILE *, int, sbitmap *, | |
584 | sbitmap *, sbitmap *, | |
585 | sbitmap *, sbitmap **, | |
586 | sbitmap **); | |
587 | extern void compute_available (sbitmap *, sbitmap *, sbitmap *, sbitmap *); | |
588 | extern int optimize_mode_switching (FILE *); | |
a05924f9 JH |
589 | |
590 | /* In emit-rtl.c. */ | |
f55ade6e AJ |
591 | extern rtx emit_block_insn_after (rtx, rtx, basic_block); |
592 | extern rtx emit_block_insn_before (rtx, rtx, basic_block); | |
4dc9341c | 593 | |
f1ebdfc5 | 594 | /* In predict.c */ |
f55ade6e AJ |
595 | extern void estimate_probability (struct loops *); |
596 | extern void note_prediction_to_br_prob (void); | |
597 | extern void expected_value_to_br_prob (void); | |
598 | extern bool maybe_hot_bb_p (basic_block); | |
599 | extern bool probably_cold_bb_p (basic_block); | |
600 | extern bool probably_never_executed_bb_p (basic_block); | |
6de9cd9a DN |
601 | extern bool tree_predicted_by_p (basic_block, enum br_predictor); |
602 | extern bool rtl_predicted_by_p (basic_block, enum br_predictor); | |
603 | extern void tree_predict_edge (edge, enum br_predictor, int); | |
604 | extern void rtl_predict_edge (edge, enum br_predictor, int); | |
605 | extern void predict_edge_def (edge, enum br_predictor, enum prediction); | |
f1ebdfc5 | 606 | |
11bdd2ae | 607 | /* In flow.c */ |
f55ade6e | 608 | extern void init_flow (void); |
f55ade6e AJ |
609 | extern void debug_bb (basic_block); |
610 | extern basic_block debug_bb_n (int); | |
611 | extern void dump_regset (regset, FILE *); | |
612 | extern void debug_regset (regset); | |
613 | extern void allocate_reg_life_data (void); | |
614 | extern void allocate_bb_life_data (void); | |
615 | extern void expunge_block (basic_block); | |
616 | extern void link_block (basic_block, basic_block); | |
617 | extern void unlink_block (basic_block); | |
618 | extern void compact_blocks (void); | |
619 | extern basic_block alloc_block (void); | |
620 | extern void find_unreachable_blocks (void); | |
621 | extern int delete_noop_moves (rtx); | |
622 | extern basic_block force_nonfallthru (edge); | |
623 | extern rtx block_label (basic_block); | |
624 | extern bool forwarder_block_p (basic_block); | |
625 | extern bool purge_all_dead_edges (int); | |
626 | extern bool purge_dead_edges (basic_block); | |
627 | extern void find_sub_basic_blocks (basic_block); | |
628 | extern void find_many_sub_basic_blocks (sbitmap); | |
6de9cd9a | 629 | extern void rtl_make_eh_edge (sbitmap *, basic_block, rtx); |
f55ade6e AJ |
630 | extern bool can_fallthru (basic_block, basic_block); |
631 | extern void flow_nodes_print (const char *, const sbitmap, FILE *); | |
632 | extern void flow_edge_list_print (const char *, const edge *, int, FILE *); | |
633 | extern void alloc_aux_for_block (basic_block, int); | |
634 | extern void alloc_aux_for_blocks (int); | |
635 | extern void clear_aux_for_blocks (void); | |
636 | extern void free_aux_for_blocks (void); | |
637 | extern void alloc_aux_for_edge (edge, int); | |
638 | extern void alloc_aux_for_edges (int); | |
639 | extern void clear_aux_for_edges (void); | |
640 | extern void free_aux_for_edges (void); | |
6de9cd9a DN |
641 | extern void find_basic_blocks (rtx, int, FILE *); |
642 | extern bool cleanup_cfg (int); | |
643 | extern bool delete_unreachable_blocks (void); | |
644 | extern bool merge_seq_blocks (void); | |
11bdd2ae | 645 | |
4e872036 AS |
646 | typedef struct conflict_graph_def *conflict_graph; |
647 | ||
648 | /* Callback function when enumerating conflicts. The arguments are | |
649 | the smaller and larger regno in the conflict. Returns zero if | |
da7d8304 | 650 | enumeration is to continue, nonzero to halt enumeration. */ |
f55ade6e | 651 | typedef int (*conflict_graph_enum_fn) (int, int, void *); |
4e872036 AS |
652 | |
653 | ||
654 | /* Prototypes of operations on conflict graphs. */ | |
655 | ||
7f8a2125 | 656 | extern conflict_graph conflict_graph_new |
f55ade6e AJ |
657 | (int); |
658 | extern void conflict_graph_delete (conflict_graph); | |
659 | extern int conflict_graph_add (conflict_graph, int, int); | |
660 | extern int conflict_graph_conflict_p (conflict_graph, int, int); | |
661 | extern void conflict_graph_enum (conflict_graph, int, conflict_graph_enum_fn, | |
662 | void *); | |
663 | extern void conflict_graph_merge_regs (conflict_graph, int, int); | |
664 | extern void conflict_graph_print (conflict_graph, FILE*); | |
665 | extern conflict_graph conflict_graph_compute (regset, partition); | |
666 | extern bool mark_dfs_back_edges (void); | |
667 | extern void set_edge_can_fallthru_flag (void); | |
668 | extern void update_br_prob_note (basic_block); | |
669 | extern void fixup_abnormal_edges (void); | |
670 | extern bool can_hoist_insn_p (rtx, rtx, regset); | |
671 | extern rtx hoist_insn_after (rtx, rtx, rtx, rtx); | |
672 | extern rtx hoist_insn_to_edge (rtx, edge, rtx, rtx); | |
673 | extern bool inside_basic_block_p (rtx); | |
674 | extern bool control_flow_insn_p (rtx); | |
11bdd2ae | 675 | |
4682ae04 AJ |
676 | /* In bb-reorder.c */ |
677 | extern void reorder_basic_blocks (void); | |
750054a2 | 678 | extern void partition_hot_cold_basic_blocks (void); |
4682ae04 | 679 | |
6de9cd9a DN |
680 | /* In cfg.c */ |
681 | extern void alloc_rbi_pool (void); | |
682 | extern void initialize_bb_rbi (basic_block bb); | |
683 | extern void free_rbi_pool (void); | |
684 | ||
f8032688 MM |
685 | /* In dominance.c */ |
686 | ||
687 | enum cdi_direction | |
688 | { | |
689 | CDI_DOMINATORS, | |
690 | CDI_POST_DOMINATORS | |
691 | }; | |
692 | ||
d47cc544 SB |
693 | enum dom_state |
694 | { | |
695 | DOM_NONE, /* Not computed at all. */ | |
696 | DOM_CONS_OK, /* The data is conservatively OK, i.e. if it says you that A dominates B, | |
697 | it indeed does. */ | |
698 | DOM_NO_FAST_QUERY, /* The data is OK, but the fast query data are not usable. */ | |
699 | DOM_OK /* Everything is ok. */ | |
700 | }; | |
701 | ||
702 | extern enum dom_state dom_computed[2]; | |
703 | ||
704 | extern void calculate_dominance_info (enum cdi_direction); | |
705 | extern void free_dominance_info (enum cdi_direction); | |
706 | extern basic_block nearest_common_dominator (enum cdi_direction, | |
f55ade6e | 707 | basic_block, basic_block); |
d47cc544 | 708 | extern void set_immediate_dominator (enum cdi_direction, basic_block, |
f55ade6e | 709 | basic_block); |
d47cc544 SB |
710 | extern basic_block get_immediate_dominator (enum cdi_direction, basic_block); |
711 | extern bool dominated_by_p (enum cdi_direction, basic_block, basic_block); | |
712 | extern int get_dominated_by (enum cdi_direction, basic_block, basic_block **); | |
713 | extern void add_to_dominance_info (enum cdi_direction, basic_block); | |
714 | extern void delete_from_dominance_info (enum cdi_direction, basic_block); | |
715 | basic_block recount_dominator (enum cdi_direction, basic_block); | |
716 | extern void redirect_immediate_dominators (enum cdi_direction, basic_block, | |
f55ade6e | 717 | basic_block); |
d47cc544 SB |
718 | extern void iterate_fix_dominators (enum cdi_direction, basic_block *, int); |
719 | extern void verify_dominators (enum cdi_direction); | |
720 | extern basic_block first_dom_son (enum cdi_direction, basic_block); | |
721 | extern basic_block next_dom_son (enum cdi_direction, basic_block); | |
6de9cd9a | 722 | extern edge try_redirect_by_replacing_jump (edge, basic_block, bool); |
12c3874e | 723 | extern void break_superblocks (void); |
9ee634e3 JH |
724 | |
725 | #include "cfghooks.h" | |
726 | ||
88657302 | 727 | #endif /* GCC_BASIC_BLOCK_H */ |