1/* Natural loop functions 2 Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, USA. */ 21 22#ifndef GCC_CFGLOOP_H 23#define GCC_CFGLOOP_H 24 25#include "basic-block.h" 26/* For rtx_code. */ 27#include "rtl.h" 28 29/* Structure to hold decision about unrolling/peeling. */ 30enum lpt_dec 31{ 32 LPT_NONE, 33 LPT_PEEL_COMPLETELY, 34 LPT_PEEL_SIMPLE, 35 LPT_UNROLL_CONSTANT, 36 LPT_UNROLL_RUNTIME, 37 LPT_UNROLL_STUPID 38}; 39 40struct lpt_decision 41{ 42 enum lpt_dec decision; 43 unsigned times; 44}; 45 46/* The structure describing a bound on number of iterations of a loop. */ 47 48struct nb_iter_bound 49{ 50 tree bound; /* The constant expression whose value is an upper 51 bound on the number of executions of ... */ 52 tree at_stmt; /* ... this statement during one execution of 53 a loop. */ 54 struct nb_iter_bound *next; 55 /* The next bound in a list. */ 56}; 57 58/* Structure to hold information for each natural loop. */ 59struct loop 60{ 61 /* Index into loops array. */ 62 int num; 63 64 /* Basic block of loop header. */ 65 basic_block header; 66 67 /* Basic block of loop latch. */ 68 basic_block latch; 69 70 /* For loop unrolling/peeling decision. */ 71 struct lpt_decision lpt_decision; 72 73 /* Number of loop insns. */ 74 unsigned ninsns; 75 76 /* Average number of executed insns per iteration. */ 77 unsigned av_ninsns; 78 79 /* Number of blocks contained within the loop. */ 80 unsigned num_nodes; 81 82 /* The loop nesting depth. */ 83 int depth; 84 85 /* Superloops of the loop. */ 86 struct loop **pred; 87 88 /* The height of the loop (enclosed loop levels) within the loop 89 hierarchy tree. */ 90 int level; 91 92 /* The outer (parent) loop or NULL if outermost loop. */ 93 struct loop *outer; 94 95 /* The first inner (child) loop or NULL if innermost loop. */ 96 struct loop *inner; 97 98 /* Link to the next (sibling) loop. */ 99 struct loop *next; 100 101 /* Loop that is copy of this loop. */ 102 struct loop *copy; 103 104 /* Auxiliary info specific to a pass. */ 105 void *aux; 106 107 /* The probable number of times the loop is executed at runtime. 108 This is an INTEGER_CST or an expression containing symbolic 109 names. Don't access this field directly: 110 number_of_iterations_in_loop computes and caches the computed 111 information in this field. */ 112 tree nb_iterations; 113 114 /* An INTEGER_CST estimation of the number of iterations. NULL_TREE 115 if there is no estimation. */ 116 tree estimated_nb_iterations; 117 118 /* Upper bound on number of iterations of a loop. */ 119 struct nb_iter_bound *bounds; 120 121 /* If not NULL, loop has just single exit edge stored here (edges to the 122 EXIT_BLOCK_PTR do not count. */ 123 edge single_exit; 124 125 /* True when the loop does not carry data dependences, and 126 consequently the iterations can be executed in any order. False 127 when the loop carries data dependences, or when the property is 128 not decidable. */ 129 bool parallel_p; 130}; 131 132/* Flags for state of loop structure. */ 133enum 134{ 135 LOOPS_HAVE_PREHEADERS = 1, 136 LOOPS_HAVE_SIMPLE_LATCHES = 2, 137 LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4, 138 LOOPS_HAVE_MARKED_SINGLE_EXITS = 8 139}; 140 141#define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \ 142 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) 143 144/* Structure to hold CFG information about natural loops within a function. */ 145struct loops 146{ 147 /* Number of natural loops in the function. */ 148 unsigned num; 149 150 /* State of loops. */ 151 int state; 152 153 /* We store just pointers to loops here. 154 Note that a loop in this array may actually be NULL, if the loop 155 has been removed and the entire loops structure has not been 156 recomputed since that time. */ 157 struct loop **parray; 158 159 /* Pointer to root of loop hierarchy tree. */ 160 struct loop *tree_root; 161 162 /* Information derived from the CFG. */ 163 struct cfg 164 { 165 /* The ordering of the basic blocks in a depth first search. */ 166 int *dfs_order; 167 168 /* The reverse completion ordering of the basic blocks found in a 169 depth first search. */ 170 int *rc_order; 171 } cfg; 172 173 /* Headers shared by multiple loops that should be merged. */ 174 sbitmap shared_headers; 175}; 176 177/* The loop tree currently optimized. */ 178 179extern struct loops *current_loops; 180 181/* Loop recognition. */ 182extern int flow_loops_find (struct loops *); 183extern void flow_loops_free (struct loops *); 184extern void flow_loops_dump (const struct loops *, FILE *, 185 void (*)(const struct loop *, FILE *, int), int); 186extern void flow_loop_dump (const struct loop *, FILE *, 187 void (*)(const struct loop *, FILE *, int), int); 188extern void flow_loop_free (struct loop *); 189int flow_loop_nodes_find (basic_block, struct loop *); 190void fix_loop_structure (struct loops *, bitmap changed_bbs); 191void mark_irreducible_loops (struct loops *); 192void mark_single_exit_loops (struct loops *); 193 194/* Loop data structure manipulation/querying. */ 195extern void flow_loop_tree_node_add (struct loop *, struct loop *); 196extern void flow_loop_tree_node_remove (struct loop *); 197extern bool flow_loop_nested_p (const struct loop *, const struct loop *); 198extern bool flow_bb_inside_loop_p (const struct loop *, const basic_block); 199extern struct loop * find_common_loop (struct loop *, struct loop *); 200struct loop *superloop_at_depth (struct loop *, unsigned); 201extern unsigned tree_num_loop_insns (struct loop *); 202extern int num_loop_insns (struct loop *); 203extern int average_num_loop_insns (struct loop *); 204extern unsigned get_loop_level (const struct loop *); 205extern bool loop_exit_edge_p (const struct loop *, edge); 206extern void mark_loop_exit_edges (struct loops *); 207 208/* Loops & cfg manipulation. */ 209extern basic_block *get_loop_body (const struct loop *); 210extern basic_block *get_loop_body_in_dom_order (const struct loop *); 211extern basic_block *get_loop_body_in_bfs_order (const struct loop *); 212extern edge *get_loop_exit_edges (const struct loop *, unsigned *); 213extern unsigned num_loop_branches (const struct loop *); 214 215extern edge loop_preheader_edge (const struct loop *); 216extern edge loop_latch_edge (const struct loop *); 217 218extern void add_bb_to_loop (basic_block, struct loop *); 219extern void remove_bb_from_loops (basic_block); 220 221extern void cancel_loop_tree (struct loops *, struct loop *); 222 223extern basic_block loop_split_edge_with (edge, rtx); 224extern int fix_loop_placement (struct loop *); 225 226enum 227{ 228 CP_SIMPLE_PREHEADERS = 1 229}; 230 231extern void create_preheaders (struct loops *, int); 232extern void force_single_succ_latches (struct loops *); 233 234extern void verify_loop_structure (struct loops *); 235 236/* Loop analysis. */ 237extern bool just_once_each_iteration_p (const struct loop *, basic_block); 238extern unsigned expected_loop_iterations (const struct loop *); 239extern rtx doloop_condition_get (rtx); 240 241/* Loop manipulation. */ 242extern bool can_duplicate_loop_p (struct loop *loop); 243 244#define DLTHE_FLAG_UPDATE_FREQ 1 /* Update frequencies in 245 duplicate_loop_to_header_edge. */ 246#define DLTHE_RECORD_COPY_NUMBER 2 /* Record copy number in the aux 247 field of newly create BB. */ 248#define DLTHE_FLAG_COMPLETTE_PEEL 4 /* Update frequencies expecting 249 a complete peeling. */ 250 251extern struct loop * duplicate_loop (struct loops *, struct loop *, 252 struct loop *); 253extern bool duplicate_loop_to_header_edge (struct loop *, edge, struct loops *, 254 unsigned, sbitmap, edge, edge *, 255 unsigned *, int); 256extern struct loop *loopify (struct loops *, edge, edge, 257 basic_block, edge, edge, bool); 258struct loop * loop_version (struct loops *, struct loop *, void *, 259 basic_block *, bool); 260extern bool remove_path (struct loops *, edge); 261 262/* Induction variable analysis. */ 263 264/* The description of induction variable. The things are a bit complicated 265 due to need to handle subregs and extends. The value of the object described 266 by it can be obtained as follows (all computations are done in extend_mode): 267 268 Value in i-th iteration is 269 delta + mult * extend_{extend_mode} (subreg_{mode} (base + i * step)). 270 271 If first_special is true, the value in the first iteration is 272 delta + mult * base 273 274 If extend = UNKNOWN, first_special must be false, delta 0, mult 1 and value is 275 subreg_{mode} (base + i * step) 276 277 The get_iv_value function can be used to obtain these expressions. 278 279 ??? Add a third mode field that would specify the mode in that inner 280 computation is done, which would enable it to be different from the 281 outer one? */ 282 283struct rtx_iv 284{ 285 /* Its base and step (mode of base and step is supposed to be extend_mode, 286 see the description above). */ 287 rtx base, step; 288 289 /* The type of extend applied to it (SIGN_EXTEND, ZERO_EXTEND or UNKNOWN). */ 290 enum rtx_code extend; 291 292 /* Operations applied in the extended mode. */ 293 rtx delta, mult; 294 295 /* The mode it is extended to. */ 296 enum machine_mode extend_mode; 297 298 /* The mode the variable iterates in. */ 299 enum machine_mode mode; 300 301 /* Whether the first iteration needs to be handled specially. */ 302 unsigned first_special : 1; 303}; 304 305/* The description of an exit from the loop and of the number of iterations 306 till we take the exit. */ 307 308struct niter_desc 309{ 310 /* The edge out of the loop. */ 311 edge out_edge; 312 313 /* The other edge leading from the condition. */ 314 edge in_edge; 315 316 /* True if we are able to say anything about number of iterations of the 317 loop. */ 318 bool simple_p; 319 320 /* True if the loop iterates the constant number of times. */ 321 bool const_iter; 322 323 /* Number of iterations if constant. */ 324 unsigned HOST_WIDEST_INT niter; 325 326 /* Upper bound on the number of iterations. */ 327 unsigned HOST_WIDEST_INT niter_max; 328 329 /* Assumptions under that the rest of the information is valid. */ 330 rtx assumptions; 331 332 /* Assumptions under that the loop ends before reaching the latch, 333 even if value of niter_expr says otherwise. */ 334 rtx noloop_assumptions; 335 336 /* Condition under that the loop is infinite. */ 337 rtx infinite; 338 339 /* Whether the comparison is signed. */ 340 bool signed_p; 341 342 /* The mode in that niter_expr should be computed. */ 343 enum machine_mode mode; 344 345 /* The number of iterations of the loop. */ 346 rtx niter_expr; 347}; 348 349extern void iv_analysis_loop_init (struct loop *); 350extern bool iv_analyze (rtx, rtx, struct rtx_iv *); 351extern bool iv_analyze_result (rtx, rtx, struct rtx_iv *); 352extern bool iv_analyze_expr (rtx, rtx, enum machine_mode, struct rtx_iv *); 353extern rtx get_iv_value (struct rtx_iv *, rtx); 354extern bool biv_p (rtx, rtx); 355extern void find_simple_exit (struct loop *, struct niter_desc *); 356extern void iv_analysis_done (void); 357extern struct df *iv_current_loop_df (void); 358 359extern struct niter_desc *get_simple_loop_desc (struct loop *loop); 360extern void free_simple_loop_desc (struct loop *loop); 361 362static inline struct niter_desc * 363simple_loop_desc (struct loop *loop) 364{ 365 return (struct niter_desc *) loop->aux; 366} 367 368/* The properties of the target. */ 369 370extern unsigned target_avail_regs; /* Number of available registers. */ 371extern unsigned target_res_regs; /* Number of reserved registers. */ 372extern unsigned target_small_cost; /* The cost for register when there 373 is a free one. */ 374extern unsigned target_pres_cost; /* The cost for register when there are 375 not too many free ones. */ 376extern unsigned target_spill_cost; /* The cost for register when we need 377 to spill. */ 378 379/* Register pressure estimation for induction variable optimizations & loop 380 invariant motion. */ 381extern unsigned global_cost_for_size (unsigned, unsigned, unsigned); 382extern void init_set_costs (void); 383 384/* Loop optimizer initialization. */ 385extern struct loops *loop_optimizer_init (unsigned); 386extern void loop_optimizer_finalize (struct loops *); 387 388/* Optimization passes. */ 389extern void unswitch_loops (struct loops *); 390 391enum 392{ 393 UAP_PEEL = 1, /* Enables loop peeling. */ 394 UAP_UNROLL = 2, /* Enables peeling of loops if it seems profitable. */ 395 UAP_UNROLL_ALL = 4 /* Enables peeling of all loops. */ 396}; 397 398extern void unroll_and_peel_loops (struct loops *, int); 399extern void doloop_optimize_loops (struct loops *); 400extern void move_loop_invariants (struct loops *); 401extern void record_estimate (struct loop *, tree, tree, tree); 402 403#endif /* GCC_CFGLOOP_H */ 404