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 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. */
62 /* Structure to hold information for each natural loop. */
65 /* Index into loops array. */
68 /* Basic block of loop header. */
71 /* Basic block of loop latch. */
74 /* Basic block of loop preheader or NULL if it does not exist. */
75 basic_block pre_header
;
77 /* For loop unrolling/peeling decision. */
78 struct lpt_decision lpt_decision
;
80 /* Simple loop description. */
82 struct loop_desc desc
;
85 /* Number of loop insns. */
88 /* Average number of executed insns per iteration. */
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
;
96 /* Number of edges along the pre_header extended basic block trace. */
97 int num_pre_header_edges
;
99 /* The first block in the loop. This is not necessarily the same as
103 /* The last block in the loop. This is not necessarily the same as
107 /* Bitmap of blocks contained within the loop. */
110 /* Number of blocks contained within the loop. */
113 /* Array of edges that enter the loop. */
116 /* Number of edges that enter the loop. */
119 /* Array of edges that exit the loop. */
122 /* Number of edges that exit the loop. */
125 /* Bitmap of blocks that dominate all exits of the loop. */
128 /* The loop nesting depth. */
131 /* Superloops of the loop. */
134 /* The height of the loop (enclosed loop levels) within the loop
138 /* The outer (parent) loop or NULL if outermost loop. */
141 /* The first inner (child) loop or NULL if innermost loop. */
144 /* Link to the next (sibling) loop. */
147 /* Loop that is copy of this loop. */
150 /* Nonzero if the loop is invalid (e.g., contains setjmp.). */
153 /* Auxiliary info specific to a pass. */
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. */
159 /* Nonzero if the loop has a NOTE_INSN_LOOP_VTOP. */
162 /* Nonzero if the loop has a NOTE_INSN_LOOP_CONT.
163 A continue statement will generate a branch to NEXT_INSN (cont). */
166 /* The dominator of cont. */
169 /* The NOTE_INSN_LOOP_BEG. */
172 /* The NOTE_INSN_LOOP_END. */
175 /* For a rotated loop that is entered near the bottom,
176 this is the label at the top. Otherwise it is zero. */
179 /* Place in the loop where control enters. */
182 /* The position where to sink insns out of the loop. */
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.
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. */
196 /* The number of LABEL_REFs on exit_labels for this loop and all
197 loops nested inside it. */
201 /* Flags for state of loop structure. */
204 LOOPS_HAVE_PREHEADERS
= 1,
205 LOOPS_HAVE_SIMPLE_LATCHES
= 2,
206 LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
= 4
209 /* Structure to hold CFG information about natural loops within a function. */
212 /* Number of natural loops in the function. */
215 /* Maximum nested loop level in the function. */
218 /* Array of natural loop descriptors (scanning this array in reverse order
219 will find the inner loops before their enclosing outer loops). */
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
225 struct loop
**parray
;
227 /* Pointer to root of loop hierarchy tree. */
228 struct loop
*tree_root
;
230 /* Information derived from the CFG. */
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 (struct loops
*, int flags
);
259 extern int flow_loops_update (struct loops
*, int flags
);
260 extern void flow_loops_free (struct loops
*);
261 extern void flow_loops_dump (const struct loops
*, FILE *,
262 void (*)(const struct loop
*, FILE *, int), int);
263 extern void flow_loop_dump (const struct loop
*, FILE *,
264 void (*)(const struct loop
*, FILE *, int), int);
265 extern int flow_loop_scan (struct loop
*, int);
266 extern void flow_loop_free (struct loop
*);
267 void mark_irreducible_loops (struct loops
*);
269 /* Loop data structure manipulation/querying. */
270 extern void flow_loop_tree_node_add (struct loop
*, struct loop
*);
271 extern void flow_loop_tree_node_remove (struct loop
*);
272 extern bool flow_loop_outside_edge_p (const struct loop
*, edge
);
273 extern bool flow_loop_nested_p (const struct loop
*, const struct loop
*);
274 extern bool flow_bb_inside_loop_p (const struct loop
*, const basic_block
);
275 extern struct loop
* find_common_loop (struct loop
*, struct loop
*);
276 extern int num_loop_insns (struct loop
*);
277 extern int average_num_loop_insns (struct loop
*);
279 /* Loops & cfg manipulation. */
280 extern basic_block
*get_loop_body (const struct loop
*);
281 extern edge
*get_loop_exit_edges (const struct loop
*, unsigned *);
283 extern edge
loop_preheader_edge (const struct loop
*);
284 extern edge
loop_latch_edge (const struct loop
*);
286 extern void add_bb_to_loop (basic_block
, struct loop
*);
287 extern void remove_bb_from_loops (basic_block
);
289 extern void cancel_loop (struct loops
*, struct loop
*);
290 extern void cancel_loop_tree (struct loops
*, struct loop
*);
292 extern basic_block
loop_split_edge_with (edge
, rtx
);
293 extern int fix_loop_placement (struct loop
*);
297 CP_SIMPLE_PREHEADERS
= 1
300 extern void create_preheaders (struct loops
*, int);
301 extern void force_single_succ_latches (struct loops
*);
303 extern void verify_loop_structure (struct loops
*);
306 extern bool simple_loop_p (struct loop
*, struct loop_desc
*);
307 extern rtx
count_loop_iterations (struct loop_desc
*, rtx
, rtx
);
308 extern bool just_once_each_iteration_p (struct loop
*, basic_block
);
309 extern unsigned expected_loop_iterations (const struct loop
*);
311 /* Loop manipulation. */
312 extern bool can_duplicate_loop_p (struct loop
*loop
);
314 #define DLTHE_FLAG_UPDATE_FREQ 1 /* Update frequencies in
315 duplicate_loop_to_header_edge. */
317 extern int duplicate_loop_to_header_edge (struct loop
*, edge
, struct loops
*,
318 unsigned, sbitmap
, edge
, edge
*,
320 extern struct loop
*loopify (struct loops
*, edge
, edge
, basic_block
);
321 extern void unloop (struct loops
*, struct loop
*);
322 extern bool remove_path (struct loops
*, edge
);
323 extern edge
split_loop_bb (basic_block
, rtx
);
325 /* Loop optimizer initialization. */
326 extern struct loops
*loop_optimizer_init (FILE *);
327 extern void loop_optimizer_finalize (struct loops
*, FILE *);
329 /* Optimization passes. */
330 extern void unswitch_loops (struct loops
*);
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. */
339 extern void unroll_and_peel_loops (struct loops
*, int);