Merge branch 'master' of ssh://crater.dragonflybsd.org/repository/git/dragonfly
[dragonfly.git] / contrib / gcc-3.4 / gcc / cfgloop.h
CommitLineData
003757ed
MD
1/* Natural loop functions
2 Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
3 Free Software Foundation, Inc.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 2, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING. If not, write to the Free
19Software Foundation, 59 Temple Place - Suite 330, Boston, MA
2002111-1307, USA. */
21
22/* Structure to hold decision about unrolling/peeling. */
23enum lpt_dec
24{
25 LPT_NONE,
26 LPT_PEEL_COMPLETELY,
27 LPT_PEEL_SIMPLE,
28 LPT_UNROLL_CONSTANT,
29 LPT_UNROLL_RUNTIME,
30 LPT_UNROLL_STUPID
31};
32
33struct lpt_decision
34{
35 enum lpt_dec decision;
36 unsigned times;
37};
38
39/* Description of loop for simple loop unrolling. */
40struct loop_desc
41{
42 int postincr; /* 1 if increment/decrement is done after loop exit condition. */
43 rtx stride; /* Value added to VAR in each iteration. */
44 rtx var; /* Loop control variable. */
45 enum machine_mode inner_mode;
46 /* The mode from that it is extended. */
47 enum rtx_code extend; /* With this extend. */
48 rtx var_alts; /* List of definitions of its initial value. */
49 rtx lim; /* Expression var is compared with. */
50 rtx lim_alts; /* List of definitions of its initial value. */
51 bool const_iter; /* True if it iterates constant number of times. */
52 unsigned HOST_WIDE_INT niter;
53 /* Number of iterations if it is constant. */
54 bool may_be_zero; /* If we cannot determine that the first iteration will pass. */
55 enum rtx_code cond; /* Exit condition. */
56 int neg; /* Set to 1 if loop ends when condition is satisfied. */
57 edge out_edge; /* The exit edge. */
58 edge in_edge; /* And the other one. */
59 int n_branches; /* Number of branches inside the loop. */
60};
61
62/* Structure to hold information for each natural loop. */
63struct loop
64{
65 /* Index into loops array. */
66 int num;
67
68 /* Basic block of loop header. */
69 basic_block header;
70
71 /* Basic block of loop latch. */
72 basic_block latch;
73
74 /* Basic block of loop preheader or NULL if it does not exist. */
75 basic_block pre_header;
76
77 /* For loop unrolling/peeling decision. */
78 struct lpt_decision lpt_decision;
79
80 /* Simple loop description. */
81 int simple;
82 struct loop_desc desc;
83 int has_desc;
84
85 /* Number of loop insns. */
86 unsigned ninsns;
87
88 /* Average number of executed insns per iteration. */
89 unsigned av_ninsns;
90
91 /* Array of edges along the preheader extended basic block trace.
92 The source of the first edge is the root node of preheader
93 extended basic block, if it exists. */
94 edge *pre_header_edges;
95
96 /* Number of edges along the pre_header extended basic block trace. */
97 int num_pre_header_edges;
98
99 /* The first block in the loop. This is not necessarily the same as
100 the loop header. */
101 basic_block first;
102
103 /* The last block in the loop. This is not necessarily the same as
104 the loop latch. */
105 basic_block last;
106
107 /* Bitmap of blocks contained within the loop. */
108 sbitmap nodes;
109
110 /* Number of blocks contained within the loop. */
111 unsigned num_nodes;
112
113 /* Array of edges that enter the loop. */
114 edge *entry_edges;
115
116 /* Number of edges that enter the loop. */
117 int num_entries;
118
119 /* Array of edges that exit the loop. */
120 edge *exit_edges;
121
122 /* Number of edges that exit the loop. */
123 int num_exits;
124
125 /* Bitmap of blocks that dominate all exits of the loop. */
126 sbitmap exits_doms;
127
128 /* The loop nesting depth. */
129 int depth;
130
131 /* Superloops of the loop. */
132 struct loop **pred;
133
134 /* The height of the loop (enclosed loop levels) within the loop
135 hierarchy tree. */
136 int level;
137
138 /* The outer (parent) loop or NULL if outermost loop. */
139 struct loop *outer;
140
141 /* The first inner (child) loop or NULL if innermost loop. */
142 struct loop *inner;
143
144 /* Link to the next (sibling) loop. */
145 struct loop *next;
146
147 /* Loop that is copy of this loop. */
148 struct loop *copy;
149
150 /* Nonzero if the loop is invalid (e.g., contains setjmp.). */
151 int invalid;
152
153 /* Auxiliary info specific to a pass. */
154 void *aux;
155
156 /* The following are currently used by loop.c but they are likely to
157 disappear as loop.c is converted to use the CFG. */
158
159 /* Nonzero if the loop has a NOTE_INSN_LOOP_VTOP. */
160 rtx vtop;
161
162 /* Nonzero if the loop has a NOTE_INSN_LOOP_CONT.
163 A continue statement will generate a branch to NEXT_INSN (cont). */
164 rtx cont;
165
166 /* The dominator of cont. */
167 rtx cont_dominator;
168
169 /* The NOTE_INSN_LOOP_BEG. */
170 rtx start;
171
172 /* The NOTE_INSN_LOOP_END. */
173 rtx end;
174
175 /* For a rotated loop that is entered near the bottom,
176 this is the label at the top. Otherwise it is zero. */
177 rtx top;
178
179 /* Place in the loop where control enters. */
180 rtx scan_start;
181
182 /* The position where to sink insns out of the loop. */
183 rtx sink;
184
185 /* List of all LABEL_REFs which refer to code labels outside the
186 loop. Used by routines that need to know all loop exits, such as
187 final_biv_value and final_giv_value.
188
189 This does not include loop exits due to return instructions.
190 This is because all bivs and givs are pseudos, and hence must be
191 dead after a return, so the presence of a return does not affect
192 any of the optimizations that use this info. It is simpler to
193 just not include return instructions on this list. */
194 rtx exit_labels;
195
196 /* The number of LABEL_REFs on exit_labels for this loop and all
197 loops nested inside it. */
198 int exit_count;
199};
200
201/* Flags for state of loop structure. */
202enum
203{
204 LOOPS_HAVE_PREHEADERS = 1,
205 LOOPS_HAVE_SIMPLE_LATCHES = 2,
206 LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4
207};
208
209/* Structure to hold CFG information about natural loops within a function. */
210struct loops
211{
212 /* Number of natural loops in the function. */
213 unsigned num;
214
215 /* Maximum nested loop level in the function. */
216 unsigned levels;
217
218 /* Array of natural loop descriptors (scanning this array in reverse order
219 will find the inner loops before their enclosing outer loops). */
220 struct loop *array;
221
222 /* The above array is unused in new loop infrastructure and is kept only for
223 purposes of the old loop optimizer. Instead we store just pointers to
224 loops here. */
225 struct loop **parray;
226
227 /* Pointer to root of loop hierarchy tree. */
228 struct loop *tree_root;
229
230 /* Information derived from the CFG. */
231 struct cfg
232 {
233 /* The ordering of the basic blocks in a depth first search. */
234 int *dfs_order;
235
236 /* The reverse completion ordering of the basic blocks found in a
237 depth first search. */
238 int *rc_order;
239 } cfg;
240
241 /* Headers shared by multiple loops that should be merged. */
242 sbitmap shared_headers;
243
244 /* State of loops. */
245 int state;
246};
247
248/* Flags for loop discovery. */
249
250#define LOOP_TREE 1 /* Build loop hierarchy tree. */
251#define LOOP_PRE_HEADER 2 /* Analyze loop preheader. */
252#define LOOP_ENTRY_EDGES 4 /* Find entry edges. */
253#define LOOP_EXIT_EDGES 8 /* Find exit edges. */
254#define LOOP_EDGES (LOOP_ENTRY_EDGES | LOOP_EXIT_EDGES)
255#define LOOP_ALL 15 /* All of the above */
256
257/* Loop recognition. */
258extern int flow_loops_find (struct loops *, int flags);
259extern int flow_loops_update (struct loops *, int flags);
260extern void flow_loops_free (struct loops *);
261extern void flow_loops_dump (const struct loops *, FILE *,
262 void (*)(const struct loop *, FILE *, int), int);
263extern void flow_loop_dump (const struct loop *, FILE *,
264 void (*)(const struct loop *, FILE *, int), int);
265extern int flow_loop_scan (struct loop *, int);
266extern void flow_loop_free (struct loop *);
267void mark_irreducible_loops (struct loops *);
268
269/* Loop data structure manipulation/querying. */
270extern void flow_loop_tree_node_add (struct loop *, struct loop *);
271extern void flow_loop_tree_node_remove (struct loop *);
272extern bool flow_loop_outside_edge_p (const struct loop *, edge);
273extern bool flow_loop_nested_p (const struct loop *, const struct loop *);
274extern bool flow_bb_inside_loop_p (const struct loop *, const basic_block);
275extern struct loop * find_common_loop (struct loop *, struct loop *);
276extern int num_loop_insns (struct loop *);
277extern int average_num_loop_insns (struct loop *);
278
279/* Loops & cfg manipulation. */
280extern basic_block *get_loop_body (const struct loop *);
281extern edge *get_loop_exit_edges (const struct loop *, unsigned *);
282
283extern edge loop_preheader_edge (const struct loop *);
284extern edge loop_latch_edge (const struct loop *);
285
286extern void add_bb_to_loop (basic_block, struct loop *);
287extern void remove_bb_from_loops (basic_block);
288
289extern void cancel_loop (struct loops *, struct loop *);
290extern void cancel_loop_tree (struct loops *, struct loop *);
291
292extern basic_block loop_split_edge_with (edge, rtx);
293extern int fix_loop_placement (struct loop *);
294
295enum
296{
297 CP_SIMPLE_PREHEADERS = 1
298};
299
300extern void create_preheaders (struct loops *, int);
301extern void force_single_succ_latches (struct loops *);
302
303extern void verify_loop_structure (struct loops *);
304
305/* Loop analysis. */
306extern bool simple_loop_p (struct loop *, struct loop_desc *);
307extern rtx count_loop_iterations (struct loop_desc *, rtx, rtx);
308extern bool just_once_each_iteration_p (struct loop *, basic_block);
309extern unsigned expected_loop_iterations (const struct loop *);
310
311/* Loop manipulation. */
312extern bool can_duplicate_loop_p (struct loop *loop);
313
314#define DLTHE_FLAG_UPDATE_FREQ 1 /* Update frequencies in
315 duplicate_loop_to_header_edge. */
316
317extern int duplicate_loop_to_header_edge (struct loop *, edge, struct loops *,
318 unsigned, sbitmap, edge, edge *,
319 unsigned *, int);
320extern struct loop *loopify (struct loops *, edge, edge, basic_block);
321extern void unloop (struct loops *, struct loop *);
322extern bool remove_path (struct loops *, edge);
323extern edge split_loop_bb (basic_block, rtx);
324
325/* Loop optimizer initialization. */
326extern struct loops *loop_optimizer_init (FILE *);
327extern void loop_optimizer_finalize (struct loops *, FILE *);
328
329/* Optimization passes. */
330extern void unswitch_loops (struct loops *);
331
332enum
333{
334 UAP_PEEL = 1, /* Enables loop peeling. */
335 UAP_UNROLL = 2, /* Enables peeling of loops if it seems profitable. */
336 UAP_UNROLL_ALL = 4 /* Enables peeling of all loops. */
337};
338
339extern void unroll_and_peel_loops (struct loops *, int);
340extern bool is_bct_cond (rtx);
341extern rtx get_var_set_from_bct (rtx);