1132718Skan/* Natural loop functions 2169689Skan Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 3132718Skan Free Software Foundation, Inc. 4132718Skan 5132718SkanThis file is part of GCC. 6132718Skan 7132718SkanGCC is free software; you can redistribute it and/or modify it under 8132718Skanthe terms of the GNU General Public License as published by the Free 9132718SkanSoftware Foundation; either version 2, or (at your option) any later 10132718Skanversion. 11132718Skan 12132718SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 13132718SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 14132718SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15132718Skanfor more details. 16132718Skan 17132718SkanYou should have received a copy of the GNU General Public License 18132718Skanalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 21132718Skan 22169689Skan#ifndef GCC_CFGLOOP_H 23169689Skan#define GCC_CFGLOOP_H 24169689Skan 25169689Skan#include "basic-block.h" 26169689Skan/* For rtx_code. */ 27169689Skan#include "rtl.h" 28169689Skan 29132718Skan/* Structure to hold decision about unrolling/peeling. */ 30132718Skanenum lpt_dec 31132718Skan{ 32132718Skan LPT_NONE, 33132718Skan LPT_PEEL_COMPLETELY, 34132718Skan LPT_PEEL_SIMPLE, 35132718Skan LPT_UNROLL_CONSTANT, 36132718Skan LPT_UNROLL_RUNTIME, 37132718Skan LPT_UNROLL_STUPID 38132718Skan}; 39132718Skan 40132718Skanstruct lpt_decision 41132718Skan{ 42132718Skan enum lpt_dec decision; 43132718Skan unsigned times; 44132718Skan}; 45132718Skan 46169689Skan/* The structure describing a bound on number of iterations of a loop. */ 47169689Skan 48169689Skanstruct nb_iter_bound 49132718Skan{ 50169689Skan tree bound; /* The constant expression whose value is an upper 51169689Skan bound on the number of executions of ... */ 52169689Skan tree at_stmt; /* ... this statement during one execution of 53169689Skan a loop. */ 54169689Skan struct nb_iter_bound *next; 55169689Skan /* The next bound in a list. */ 56132718Skan}; 57132718Skan 58132718Skan/* Structure to hold information for each natural loop. */ 59132718Skanstruct loop 60132718Skan{ 61132718Skan /* Index into loops array. */ 62132718Skan int num; 63132718Skan 64132718Skan /* Basic block of loop header. */ 65132718Skan basic_block header; 66132718Skan 67132718Skan /* Basic block of loop latch. */ 68132718Skan basic_block latch; 69132718Skan 70132718Skan /* For loop unrolling/peeling decision. */ 71132718Skan struct lpt_decision lpt_decision; 72132718Skan 73132718Skan /* Number of loop insns. */ 74132718Skan unsigned ninsns; 75132718Skan 76132718Skan /* Average number of executed insns per iteration. */ 77132718Skan unsigned av_ninsns; 78132718Skan 79132718Skan /* Number of blocks contained within the loop. */ 80132718Skan unsigned num_nodes; 81132718Skan 82132718Skan /* The loop nesting depth. */ 83132718Skan int depth; 84132718Skan 85132718Skan /* Superloops of the loop. */ 86132718Skan struct loop **pred; 87132718Skan 88132718Skan /* The height of the loop (enclosed loop levels) within the loop 89132718Skan hierarchy tree. */ 90132718Skan int level; 91132718Skan 92132718Skan /* The outer (parent) loop or NULL if outermost loop. */ 93132718Skan struct loop *outer; 94132718Skan 95132718Skan /* The first inner (child) loop or NULL if innermost loop. */ 96132718Skan struct loop *inner; 97132718Skan 98132718Skan /* Link to the next (sibling) loop. */ 99132718Skan struct loop *next; 100132718Skan 101132718Skan /* Loop that is copy of this loop. */ 102132718Skan struct loop *copy; 103132718Skan 104132718Skan /* Auxiliary info specific to a pass. */ 105132718Skan void *aux; 106132718Skan 107169689Skan /* The probable number of times the loop is executed at runtime. 108169689Skan This is an INTEGER_CST or an expression containing symbolic 109169689Skan names. Don't access this field directly: 110169689Skan number_of_iterations_in_loop computes and caches the computed 111169689Skan information in this field. */ 112169689Skan tree nb_iterations; 113132718Skan 114169689Skan /* An INTEGER_CST estimation of the number of iterations. NULL_TREE 115169689Skan if there is no estimation. */ 116169689Skan tree estimated_nb_iterations; 117132718Skan 118169689Skan /* Upper bound on number of iterations of a loop. */ 119169689Skan struct nb_iter_bound *bounds; 120132718Skan 121169689Skan /* If not NULL, loop has just single exit edge stored here (edges to the 122169689Skan EXIT_BLOCK_PTR do not count. */ 123169689Skan edge single_exit; 124132718Skan 125169689Skan /* True when the loop does not carry data dependences, and 126169689Skan consequently the iterations can be executed in any order. False 127169689Skan when the loop carries data dependences, or when the property is 128169689Skan not decidable. */ 129169689Skan bool parallel_p; 130132718Skan}; 131132718Skan 132132718Skan/* Flags for state of loop structure. */ 133132718Skanenum 134132718Skan{ 135132718Skan LOOPS_HAVE_PREHEADERS = 1, 136132718Skan LOOPS_HAVE_SIMPLE_LATCHES = 2, 137169689Skan LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4, 138169689Skan LOOPS_HAVE_MARKED_SINGLE_EXITS = 8 139132718Skan}; 140132718Skan 141169689Skan#define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \ 142169689Skan | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) 143169689Skan 144132718Skan/* Structure to hold CFG information about natural loops within a function. */ 145132718Skanstruct loops 146132718Skan{ 147132718Skan /* Number of natural loops in the function. */ 148132718Skan unsigned num; 149132718Skan 150169689Skan /* State of loops. */ 151169689Skan int state; 152132718Skan 153169689Skan /* We store just pointers to loops here. 154169689Skan Note that a loop in this array may actually be NULL, if the loop 155169689Skan has been removed and the entire loops structure has not been 156169689Skan recomputed since that time. */ 157132718Skan struct loop **parray; 158132718Skan 159132718Skan /* Pointer to root of loop hierarchy tree. */ 160132718Skan struct loop *tree_root; 161132718Skan 162132718Skan /* Information derived from the CFG. */ 163132718Skan struct cfg 164132718Skan { 165132718Skan /* The ordering of the basic blocks in a depth first search. */ 166132718Skan int *dfs_order; 167132718Skan 168132718Skan /* The reverse completion ordering of the basic blocks found in a 169132718Skan depth first search. */ 170132718Skan int *rc_order; 171132718Skan } cfg; 172132718Skan 173132718Skan /* Headers shared by multiple loops that should be merged. */ 174132718Skan sbitmap shared_headers; 175132718Skan}; 176132718Skan 177169689Skan/* The loop tree currently optimized. */ 178132718Skan 179169689Skanextern struct loops *current_loops; 180132718Skan 181132718Skan/* Loop recognition. */ 182169689Skanextern int flow_loops_find (struct loops *); 183132718Skanextern void flow_loops_free (struct loops *); 184132718Skanextern void flow_loops_dump (const struct loops *, FILE *, 185132718Skan void (*)(const struct loop *, FILE *, int), int); 186132718Skanextern void flow_loop_dump (const struct loop *, FILE *, 187132718Skan void (*)(const struct loop *, FILE *, int), int); 188132718Skanextern void flow_loop_free (struct loop *); 189169689Skanint flow_loop_nodes_find (basic_block, struct loop *); 190169689Skanvoid fix_loop_structure (struct loops *, bitmap changed_bbs); 191132718Skanvoid mark_irreducible_loops (struct loops *); 192169689Skanvoid mark_single_exit_loops (struct loops *); 193132718Skan 194132718Skan/* Loop data structure manipulation/querying. */ 195132718Skanextern void flow_loop_tree_node_add (struct loop *, struct loop *); 196132718Skanextern void flow_loop_tree_node_remove (struct loop *); 197132718Skanextern bool flow_loop_nested_p (const struct loop *, const struct loop *); 198132718Skanextern bool flow_bb_inside_loop_p (const struct loop *, const basic_block); 199132718Skanextern struct loop * find_common_loop (struct loop *, struct loop *); 200169689Skanstruct loop *superloop_at_depth (struct loop *, unsigned); 201169689Skanextern unsigned tree_num_loop_insns (struct loop *); 202132718Skanextern int num_loop_insns (struct loop *); 203132718Skanextern int average_num_loop_insns (struct loop *); 204169689Skanextern unsigned get_loop_level (const struct loop *); 205169689Skanextern bool loop_exit_edge_p (const struct loop *, edge); 206169689Skanextern void mark_loop_exit_edges (struct loops *); 207132718Skan 208132718Skan/* Loops & cfg manipulation. */ 209132718Skanextern basic_block *get_loop_body (const struct loop *); 210169689Skanextern basic_block *get_loop_body_in_dom_order (const struct loop *); 211169689Skanextern basic_block *get_loop_body_in_bfs_order (const struct loop *); 212132718Skanextern edge *get_loop_exit_edges (const struct loop *, unsigned *); 213169689Skanextern unsigned num_loop_branches (const struct loop *); 214132718Skan 215132718Skanextern edge loop_preheader_edge (const struct loop *); 216132718Skanextern edge loop_latch_edge (const struct loop *); 217132718Skan 218132718Skanextern void add_bb_to_loop (basic_block, struct loop *); 219132718Skanextern void remove_bb_from_loops (basic_block); 220132718Skan 221132718Skanextern void cancel_loop_tree (struct loops *, struct loop *); 222132718Skan 223132718Skanextern basic_block loop_split_edge_with (edge, rtx); 224132718Skanextern int fix_loop_placement (struct loop *); 225132718Skan 226132718Skanenum 227132718Skan{ 228132718Skan CP_SIMPLE_PREHEADERS = 1 229132718Skan}; 230132718Skan 231132718Skanextern void create_preheaders (struct loops *, int); 232132718Skanextern void force_single_succ_latches (struct loops *); 233132718Skan 234132718Skanextern void verify_loop_structure (struct loops *); 235132718Skan 236132718Skan/* Loop analysis. */ 237169689Skanextern bool just_once_each_iteration_p (const struct loop *, basic_block); 238132718Skanextern unsigned expected_loop_iterations (const struct loop *); 239169689Skanextern rtx doloop_condition_get (rtx); 240132718Skan 241132718Skan/* Loop manipulation. */ 242132718Skanextern bool can_duplicate_loop_p (struct loop *loop); 243132718Skan 244132718Skan#define DLTHE_FLAG_UPDATE_FREQ 1 /* Update frequencies in 245132718Skan duplicate_loop_to_header_edge. */ 246169689Skan#define DLTHE_RECORD_COPY_NUMBER 2 /* Record copy number in the aux 247169689Skan field of newly create BB. */ 248169689Skan#define DLTHE_FLAG_COMPLETTE_PEEL 4 /* Update frequencies expecting 249169689Skan a complete peeling. */ 250132718Skan 251169689Skanextern struct loop * duplicate_loop (struct loops *, struct loop *, 252169689Skan struct loop *); 253169689Skanextern bool duplicate_loop_to_header_edge (struct loop *, edge, struct loops *, 254169689Skan unsigned, sbitmap, edge, edge *, 255169689Skan unsigned *, int); 256169689Skanextern struct loop *loopify (struct loops *, edge, edge, 257169689Skan basic_block, edge, edge, bool); 258169689Skanstruct loop * loop_version (struct loops *, struct loop *, void *, 259169689Skan basic_block *, bool); 260132718Skanextern bool remove_path (struct loops *, edge); 261132718Skan 262169689Skan/* Induction variable analysis. */ 263169689Skan 264169689Skan/* The description of induction variable. The things are a bit complicated 265169689Skan due to need to handle subregs and extends. The value of the object described 266169689Skan by it can be obtained as follows (all computations are done in extend_mode): 267169689Skan 268169689Skan Value in i-th iteration is 269169689Skan delta + mult * extend_{extend_mode} (subreg_{mode} (base + i * step)). 270169689Skan 271169689Skan If first_special is true, the value in the first iteration is 272169689Skan delta + mult * base 273169689Skan 274169689Skan If extend = UNKNOWN, first_special must be false, delta 0, mult 1 and value is 275169689Skan subreg_{mode} (base + i * step) 276169689Skan 277169689Skan The get_iv_value function can be used to obtain these expressions. 278169689Skan 279169689Skan ??? Add a third mode field that would specify the mode in that inner 280169689Skan computation is done, which would enable it to be different from the 281169689Skan outer one? */ 282169689Skan 283169689Skanstruct rtx_iv 284169689Skan{ 285169689Skan /* Its base and step (mode of base and step is supposed to be extend_mode, 286169689Skan see the description above). */ 287169689Skan rtx base, step; 288169689Skan 289169689Skan /* The type of extend applied to it (SIGN_EXTEND, ZERO_EXTEND or UNKNOWN). */ 290169689Skan enum rtx_code extend; 291169689Skan 292169689Skan /* Operations applied in the extended mode. */ 293169689Skan rtx delta, mult; 294169689Skan 295169689Skan /* The mode it is extended to. */ 296169689Skan enum machine_mode extend_mode; 297169689Skan 298169689Skan /* The mode the variable iterates in. */ 299169689Skan enum machine_mode mode; 300169689Skan 301169689Skan /* Whether the first iteration needs to be handled specially. */ 302169689Skan unsigned first_special : 1; 303169689Skan}; 304169689Skan 305169689Skan/* The description of an exit from the loop and of the number of iterations 306169689Skan till we take the exit. */ 307169689Skan 308169689Skanstruct niter_desc 309169689Skan{ 310169689Skan /* The edge out of the loop. */ 311169689Skan edge out_edge; 312169689Skan 313169689Skan /* The other edge leading from the condition. */ 314169689Skan edge in_edge; 315169689Skan 316169689Skan /* True if we are able to say anything about number of iterations of the 317169689Skan loop. */ 318169689Skan bool simple_p; 319169689Skan 320169689Skan /* True if the loop iterates the constant number of times. */ 321169689Skan bool const_iter; 322169689Skan 323169689Skan /* Number of iterations if constant. */ 324169689Skan unsigned HOST_WIDEST_INT niter; 325169689Skan 326169689Skan /* Upper bound on the number of iterations. */ 327169689Skan unsigned HOST_WIDEST_INT niter_max; 328169689Skan 329169689Skan /* Assumptions under that the rest of the information is valid. */ 330169689Skan rtx assumptions; 331169689Skan 332169689Skan /* Assumptions under that the loop ends before reaching the latch, 333169689Skan even if value of niter_expr says otherwise. */ 334169689Skan rtx noloop_assumptions; 335169689Skan 336169689Skan /* Condition under that the loop is infinite. */ 337169689Skan rtx infinite; 338169689Skan 339169689Skan /* Whether the comparison is signed. */ 340169689Skan bool signed_p; 341169689Skan 342169689Skan /* The mode in that niter_expr should be computed. */ 343169689Skan enum machine_mode mode; 344169689Skan 345169689Skan /* The number of iterations of the loop. */ 346169689Skan rtx niter_expr; 347169689Skan}; 348169689Skan 349169689Skanextern void iv_analysis_loop_init (struct loop *); 350169689Skanextern bool iv_analyze (rtx, rtx, struct rtx_iv *); 351169689Skanextern bool iv_analyze_result (rtx, rtx, struct rtx_iv *); 352169689Skanextern bool iv_analyze_expr (rtx, rtx, enum machine_mode, struct rtx_iv *); 353169689Skanextern rtx get_iv_value (struct rtx_iv *, rtx); 354169689Skanextern bool biv_p (rtx, rtx); 355169689Skanextern void find_simple_exit (struct loop *, struct niter_desc *); 356169689Skanextern void iv_analysis_done (void); 357169689Skanextern struct df *iv_current_loop_df (void); 358169689Skan 359169689Skanextern struct niter_desc *get_simple_loop_desc (struct loop *loop); 360169689Skanextern void free_simple_loop_desc (struct loop *loop); 361169689Skan 362169689Skanstatic inline struct niter_desc * 363169689Skansimple_loop_desc (struct loop *loop) 364169689Skan{ 365169689Skan return (struct niter_desc *) loop->aux; 366169689Skan} 367169689Skan 368169689Skan/* The properties of the target. */ 369169689Skan 370169689Skanextern unsigned target_avail_regs; /* Number of available registers. */ 371169689Skanextern unsigned target_res_regs; /* Number of reserved registers. */ 372169689Skanextern unsigned target_small_cost; /* The cost for register when there 373169689Skan is a free one. */ 374169689Skanextern unsigned target_pres_cost; /* The cost for register when there are 375169689Skan not too many free ones. */ 376169689Skanextern unsigned target_spill_cost; /* The cost for register when we need 377169689Skan to spill. */ 378169689Skan 379169689Skan/* Register pressure estimation for induction variable optimizations & loop 380169689Skan invariant motion. */ 381169689Skanextern unsigned global_cost_for_size (unsigned, unsigned, unsigned); 382169689Skanextern void init_set_costs (void); 383169689Skan 384132718Skan/* Loop optimizer initialization. */ 385169689Skanextern struct loops *loop_optimizer_init (unsigned); 386169689Skanextern void loop_optimizer_finalize (struct loops *); 387132718Skan 388132718Skan/* Optimization passes. */ 389132718Skanextern void unswitch_loops (struct loops *); 390132718Skan 391132718Skanenum 392132718Skan{ 393132718Skan UAP_PEEL = 1, /* Enables loop peeling. */ 394132718Skan UAP_UNROLL = 2, /* Enables peeling of loops if it seems profitable. */ 395132718Skan UAP_UNROLL_ALL = 4 /* Enables peeling of all loops. */ 396132718Skan}; 397132718Skan 398132718Skanextern void unroll_and_peel_loops (struct loops *, int); 399169689Skanextern void doloop_optimize_loops (struct loops *); 400169689Skanextern void move_loop_invariants (struct loops *); 401169689Skanextern void record_estimate (struct loop *, tree, tree, tree); 402169689Skan 403169689Skan#endif /* GCC_CFGLOOP_H */ 404