1 /* Natural loop functions 2 Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004 3 Free Software Foundation, Inc. 4 5 This file is part of GCC. 6 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. 11 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. 16 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 20 02111-1307, USA. */ 21 22 /* Structure to hold decision about unrolling/peeling. */ 23 enum 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 33 struct lpt_decision 34 { 35 enum lpt_dec decision; 36 unsigned times; 37 }; 38 39 /* Description of loop for simple loop unrolling. */ 40 struct 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. */ 63 struct 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. */ 202 enum 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. */ 210 struct 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. */ 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 *); 268 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 *); 278 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 *); 282 283 extern edge loop_preheader_edge (const struct loop *); 284 extern edge loop_latch_edge (const struct loop *); 285 286 extern void add_bb_to_loop (basic_block, struct loop *); 287 extern void remove_bb_from_loops (basic_block); 288 289 extern void cancel_loop (struct loops *, struct loop *); 290 extern void cancel_loop_tree (struct loops *, struct loop *); 291 292 extern basic_block loop_split_edge_with (edge, rtx); 293 extern int fix_loop_placement (struct loop *); 294 295 enum 296 { 297 CP_SIMPLE_PREHEADERS = 1 298 }; 299 300 extern void create_preheaders (struct loops *, int); 301 extern void force_single_succ_latches (struct loops *); 302 303 extern void verify_loop_structure (struct loops *); 304 305 /* Loop analysis. */ 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 *); 310 311 /* Loop manipulation. */ 312 extern 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 317 extern int duplicate_loop_to_header_edge (struct loop *, edge, struct loops *, 318 unsigned, sbitmap, edge, edge *, 319 unsigned *, int); 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); 324 325 /* Loop optimizer initialization. */ 326 extern struct loops *loop_optimizer_init (FILE *); 327 extern void loop_optimizer_finalize (struct loops *, FILE *); 328 329 /* Optimization passes. */ 330 extern void unswitch_loops (struct loops *); 331 332 enum 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 339 extern void unroll_and_peel_loops (struct loops *, int); 340 extern bool is_bct_cond (rtx); 341 extern rtx get_var_set_from_bct (rtx); 342