1 /* Natural loop functions
2 Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003
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, 59 Temple Place - Suite 330, Boston, MA
22 /* Structure to hold decision about unrolling/peeling. */
35 enum lpt_dec decision;
39 /* Description of loop for simple loop unrolling. */
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 rtx var_alts; /* List of definitions of its initial value. */
46 rtx lim; /* Expression var is compared with. */
47 rtx lim_alts; /* List of definitions of its initial value. */
48 bool const_iter; /* True if it iterates constant number of times. */
49 unsigned HOST_WIDE_INT niter;
50 /* Number of iterations if it is constant. */
51 bool may_be_zero; /* If we cannot determine that the first iteration will pass. */
52 enum rtx_code cond; /* Exit condition. */
53 int neg; /* Set to 1 if loop ends when condition is satisfied. */
54 edge out_edge; /* The exit edge. */
55 edge in_edge; /* And the other one. */
56 int n_branches; /* Number of branches inside the loop. */
59 /* Structure to hold information for each natural loop. */
62 /* Index into loops array. */
65 /* Basic block of loop header. */
68 /* Basic block of loop latch. */
71 /* Basic block of loop preheader or NULL if it does not exist. */
72 basic_block pre_header;
74 /* For loop unrolling/peeling decision. */
75 struct lpt_decision lpt_decision;
77 /* Simple loop description. */
79 struct loop_desc desc;
82 /* Number of loop insns. */
85 /* Average number of executed insns per iteration. */
88 /* Array of edges along the preheader extended basic block trace.
89 The source of the first edge is the root node of preheader
90 extended basic block, if it exists. */
91 edge *pre_header_edges;
93 /* Number of edges along the pre_header extended basic block trace. */
94 int num_pre_header_edges;
96 /* The first block in the loop. This is not necessarily the same as
100 /* The last block in the loop. This is not necessarily the same as
104 /* Bitmap of blocks contained within the loop. */
107 /* Number of blocks contained within the loop. */
110 /* Array of edges that enter the loop. */
113 /* Number of edges that enter the loop. */
116 /* Array of edges that exit the loop. */
119 /* Number of edges that exit the loop. */
122 /* Bitmap of blocks that dominate all exits of the loop. */
125 /* The loop nesting depth. */
128 /* Superloops of the loop. */
131 /* The height of the loop (enclosed loop levels) within the loop
135 /* The outer (parent) loop or NULL if outermost loop. */
138 /* The first inner (child) loop or NULL if innermost loop. */
141 /* Link to the next (sibling) loop. */
144 /* Loop that is copy of this loop. */
147 /* Non-zero if the loop is invalid (e.g., contains setjmp.). */
150 /* Auxiliary info specific to a pass. */
153 /* The following are currently used by loop.c but they are likely to
154 disappear as loop.c is converted to use the CFG. */
156 /* Non-zero if the loop has a NOTE_INSN_LOOP_VTOP. */
159 /* Non-zero if the loop has a NOTE_INSN_LOOP_CONT.
160 A continue statement will generate a branch to NEXT_INSN (cont). */
163 /* The dominator of cont. */
166 /* The NOTE_INSN_LOOP_BEG. */
169 /* The NOTE_INSN_LOOP_END. */
172 /* For a rotated loop that is entered near the bottom,
173 this is the label at the top. Otherwise it is zero. */
176 /* Place in the loop where control enters. */
179 /* The position where to sink insns out of the loop. */
182 /* List of all LABEL_REFs which refer to code labels outside the
183 loop. Used by routines that need to know all loop exits, such as
184 final_biv_value and final_giv_value.
186 This does not include loop exits due to return instructions.
187 This is because all bivs and givs are pseudos, and hence must be
188 dead after a return, so the presence of a return does not affect
189 any of the optimizations that use this info. It is simpler to
190 just not include return instructions on this list. */
193 /* The number of LABEL_REFs on exit_labels for this loop and all
194 loops nested inside it. */
198 /* Flags for state of loop structure. */
201 LOOPS_HAVE_PREHEADERS = 1,
202 LOOPS_HAVE_SIMPLE_LATCHES = 2,
203 LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4
206 /* Structure to hold CFG information about natural loops within a function. */
209 /* Number of natural loops in the function. */
212 /* Maximum nested loop level in the function. */
215 /* Array of natural loop descriptors (scanning this array in reverse order
216 will find the inner loops before their enclosing outer loops). */
219 /* The above array is unused in new loop infrastructure and is kept only for
220 purposes of the old loop optimizer. Instead we store just pointers to
222 struct loop **parray;
224 /* Pointer to root of loop hierarchy tree. */
225 struct loop *tree_root;
227 /* Information derived from the CFG. */
230 /* The bitmap vector of dominators or NULL if not computed. */
233 /* The ordering of the basic blocks in a depth first search. */
236 /* The reverse completion ordering of the basic blocks found in a
237 depth first search. */
241 /* Headers shared by multiple loops that should be merged. */
242 sbitmap shared_headers;
244 /* State of loops. */
248 /* Flags for loop discovery. */
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 */
257 /* Loop recognition. */
258 extern int flow_loops_find PARAMS ((struct loops *, int flags));
259 extern int flow_loops_update PARAMS ((struct loops *, int flags));
260 extern void flow_loops_free PARAMS ((struct loops *));
261 extern void flow_loops_dump PARAMS ((const struct loops *, FILE *,
262 void (*)(const struct loop *,
264 extern void flow_loop_dump PARAMS ((const struct loop *, FILE *,
265 void (*)(const struct loop *,
267 extern int flow_loop_scan PARAMS ((struct loops *,
268 struct loop *, int));
269 void mark_irreducible_loops PARAMS ((struct loops *));
271 /* Loop datastructure manipulation/querying. */
272 extern void flow_loop_tree_node_add PARAMS ((struct loop *, struct loop *));
273 extern void flow_loop_tree_node_remove PARAMS ((struct loop *));
274 extern bool flow_loop_outside_edge_p PARAMS ((const struct loop *, edge));
275 extern bool flow_loop_nested_p PARAMS ((const struct loop *,
276 const struct loop *));
277 extern bool flow_bb_inside_loop_p PARAMS ((const struct loop *,
279 extern struct loop * find_common_loop PARAMS ((struct loop *, struct loop *));
280 extern int num_loop_insns PARAMS ((struct loop *));
281 extern int average_num_loop_insns PARAMS ((struct loop *));
283 /* Loops & cfg manipulation. */
284 extern basic_block *get_loop_body PARAMS ((const struct loop *));
286 extern edge loop_preheader_edge PARAMS ((const struct loop *));
287 extern edge loop_latch_edge PARAMS ((const struct loop *));
289 extern void add_bb_to_loop PARAMS ((basic_block, struct loop *));
290 extern void remove_bb_from_loops PARAMS ((basic_block));
292 extern void cancel_loop PARAMS ((struct loops *, struct loop *));
293 extern void cancel_loop_tree PARAMS ((struct loops *, struct loop *));
295 extern basic_block loop_split_edge_with PARAMS ((edge, rtx, struct loops *));
296 extern int fix_loop_placement PARAMS ((struct loop *));
300 CP_SIMPLE_PREHEADERS = 1,
301 CP_INSIDE_CFGLAYOUT = 2
304 extern void create_preheaders PARAMS ((struct loops *, int));
305 extern void force_single_succ_latches PARAMS ((struct loops *));
307 extern void verify_loop_structure PARAMS ((struct loops *));
310 extern bool simple_loop_p PARAMS ((struct loops *, struct loop *,
311 struct loop_desc *));
312 extern rtx count_loop_iterations PARAMS ((struct loop_desc *, rtx, rtx));
313 extern bool just_once_each_iteration_p PARAMS ((struct loops *,struct loop *,
315 extern unsigned expected_loop_iterations PARAMS ((const struct loop *));
317 /* Loop manipulation. */
318 extern bool can_duplicate_loop_p PARAMS ((struct loop *loop));
320 #define DLTHE_FLAG_UPDATE_FREQ 1 /* Update frequencies in
321 duplicate_loop_to_header_edge. */
323 extern int duplicate_loop_to_header_edge PARAMS ((struct loop *, edge,
324 struct loops *, unsigned,
325 sbitmap, edge, edge *,
327 extern struct loop *loopify PARAMS ((struct loops *, edge,
329 extern bool remove_path PARAMS ((struct loops *, edge));
330 extern edge split_loop_bb PARAMS ((struct loops *, basic_block,
333 /* Loop optimizer initialization. */
334 extern struct loops *loop_optimizer_init PARAMS ((FILE *));
335 extern void loop_optimizer_finalize PARAMS ((struct loops *, FILE *));
337 /* Optimization passes. */
338 extern void unswitch_loops PARAMS ((struct loops *));