1/* Natural loop functions 2 Copyright (C) 1987-2015 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 3, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING3. If not see 18<http://www.gnu.org/licenses/>. */ 19 20#ifndef GCC_CFGLOOP_H 21#define GCC_CFGLOOP_H 22 23#include "double-int.h" 24#include "wide-int.h" 25#include "bitmap.h" 26#include "sbitmap.h" 27#include "hashtab.h" 28#include "hash-set.h" 29#include "vec.h" 30#include "machmode.h" 31#include "tm.h" 32#include "hard-reg-set.h" 33#include "input.h" 34#include "function.h" 35#include "cfgloopmanip.h" 36 37/* Structure to hold decision about unrolling/peeling. */ 38enum lpt_dec 39{ 40 LPT_NONE, 41 LPT_UNROLL_CONSTANT, 42 LPT_UNROLL_RUNTIME, 43 LPT_UNROLL_STUPID 44}; 45 46struct GTY (()) lpt_decision { 47 enum lpt_dec decision; 48 unsigned times; 49}; 50 51/* The type of extend applied to an IV. */ 52enum iv_extend_code 53{ 54 IV_SIGN_EXTEND, 55 IV_ZERO_EXTEND, 56 IV_UNKNOWN_EXTEND 57}; 58 59/* The structure describing a bound on number of iterations of a loop. */ 60 61struct GTY ((chain_next ("%h.next"))) nb_iter_bound { 62 /* The statement STMT is executed at most ... */ 63 gimple stmt; 64 65 /* ... BOUND + 1 times (BOUND must be an unsigned constant). 66 The + 1 is added for the following reasons: 67 68 a) 0 would otherwise be unused, while we would need to care more about 69 overflows (as MAX + 1 is sometimes produced as the estimate on number 70 of executions of STMT). 71 b) it is consistent with the result of number_of_iterations_exit. */ 72 widest_int bound; 73 74 /* True if the statement will cause the loop to be leaved the (at most) 75 BOUND + 1-st time it is executed, that is, all the statements after it 76 are executed at most BOUND times. */ 77 bool is_exit; 78 79 /* The next bound in the list. */ 80 struct nb_iter_bound *next; 81}; 82 83/* Description of the loop exit. */ 84 85struct GTY ((for_user)) loop_exit { 86 /* The exit edge. */ 87 edge e; 88 89 /* Previous and next exit in the list of the exits of the loop. */ 90 struct loop_exit *prev; 91 struct loop_exit *next; 92 93 /* Next element in the list of loops from that E exits. */ 94 struct loop_exit *next_e; 95}; 96 97struct loop_exit_hasher : ggc_hasher<loop_exit *> 98{ 99 typedef edge compare_type; 100 101 static hashval_t hash (loop_exit *); 102 static bool equal (loop_exit *, edge); 103 static void remove (loop_exit *); 104}; 105 106typedef struct loop *loop_p; 107 108/* An integer estimation of the number of iterations. Estimate_state 109 describes what is the state of the estimation. */ 110enum loop_estimation 111{ 112 /* Estimate was not computed yet. */ 113 EST_NOT_COMPUTED, 114 /* Estimate is ready. */ 115 EST_AVAILABLE, 116 EST_LAST 117}; 118 119/* Structure to hold information for each natural loop. */ 120struct GTY ((chain_next ("%h.next"))) loop { 121 /* Index into loops array. */ 122 int num; 123 124 /* Number of loop insns. */ 125 unsigned ninsns; 126 127 /* Basic block of loop header. */ 128 basic_block header; 129 130 /* Basic block of loop latch. */ 131 basic_block latch; 132 133 /* For loop unrolling/peeling decision. */ 134 struct lpt_decision lpt_decision; 135 136 /* Average number of executed insns per iteration. */ 137 unsigned av_ninsns; 138 139 /* Number of blocks contained within the loop. */ 140 unsigned num_nodes; 141 142 /* Superloops of the loop, starting with the outermost loop. */ 143 vec<loop_p, va_gc> *superloops; 144 145 /* The first inner (child) loop or NULL if innermost loop. */ 146 struct loop *inner; 147 148 /* Link to the next (sibling) loop. */ 149 struct loop *next; 150 151 /* Auxiliary info specific to a pass. */ 152 PTR GTY ((skip (""))) aux; 153 154 /* The number of times the latch of the loop is executed. This can be an 155 INTEGER_CST, or a symbolic expression representing the number of 156 iterations like "N - 1", or a COND_EXPR containing the runtime 157 conditions under which the number of iterations is non zero. 158 159 Don't access this field directly: number_of_latch_executions 160 computes and caches the computed information in this field. */ 161 tree nb_iterations; 162 163 /* An integer guaranteed to be greater or equal to nb_iterations. Only 164 valid if any_upper_bound is true. */ 165 widest_int nb_iterations_upper_bound; 166 167 /* An integer giving an estimate on nb_iterations. Unlike 168 nb_iterations_upper_bound, there is no guarantee that it is at least 169 nb_iterations. */ 170 widest_int nb_iterations_estimate; 171 172 bool any_upper_bound; 173 bool any_estimate; 174 175 /* True if the loop can be parallel. */ 176 bool can_be_parallel; 177 178 /* True if -Waggressive-loop-optimizations warned about this loop 179 already. */ 180 bool warned_aggressive_loop_optimizations; 181 182 /* An integer estimation of the number of iterations. Estimate_state 183 describes what is the state of the estimation. */ 184 enum loop_estimation estimate_state; 185 186 /* If > 0, an integer, where the user asserted that for any 187 I in [ 0, nb_iterations ) and for any J in 188 [ I, min ( I + safelen, nb_iterations ) ), the Ith and Jth iterations 189 of the loop can be safely evaluated concurrently. */ 190 int safelen; 191 192 /* True if this loop should never be vectorized. */ 193 bool dont_vectorize; 194 195 /* True if we should try harder to vectorize this loop. */ 196 bool force_vectorize; 197 198 /* For SIMD loops, this is a unique identifier of the loop, referenced 199 by IFN_GOMP_SIMD_VF, IFN_GOMP_SIMD_LANE and IFN_GOMP_SIMD_LAST_LANE 200 builtins. */ 201 tree simduid; 202 203 /* Upper bound on number of iterations of a loop. */ 204 struct nb_iter_bound *bounds; 205 206 /* Head of the cyclic list of the exits of the loop. */ 207 struct loop_exit *exits; 208 209 /* Number of iteration analysis data for RTL. */ 210 struct niter_desc *simple_loop_desc; 211 212 /* For sanity checking during loop fixup we record here the former 213 loop header for loops marked for removal. Note that this prevents 214 the basic-block from being collected but its index can still be 215 reused. */ 216 basic_block former_header; 217}; 218 219/* Flags for state of loop structure. */ 220enum 221{ 222 LOOPS_HAVE_PREHEADERS = 1, 223 LOOPS_HAVE_SIMPLE_LATCHES = 2, 224 LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4, 225 LOOPS_HAVE_RECORDED_EXITS = 8, 226 LOOPS_MAY_HAVE_MULTIPLE_LATCHES = 16, 227 LOOP_CLOSED_SSA = 32, 228 LOOPS_NEED_FIXUP = 64, 229 LOOPS_HAVE_FALLTHRU_PREHEADERS = 128 230}; 231 232#define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \ 233 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) 234#define AVOID_CFG_MODIFICATIONS (LOOPS_MAY_HAVE_MULTIPLE_LATCHES) 235 236/* Structure to hold CFG information about natural loops within a function. */ 237struct GTY (()) loops { 238 /* State of loops. */ 239 int state; 240 241 /* Array of the loops. */ 242 vec<loop_p, va_gc> *larray; 243 244 /* Maps edges to the list of their descriptions as loop exits. Edges 245 whose sources or destinations have loop_father == NULL (which may 246 happen during the cfg manipulations) should not appear in EXITS. */ 247 hash_table<loop_exit_hasher> *GTY(()) exits; 248 249 /* Pointer to root of loop hierarchy tree. */ 250 struct loop *tree_root; 251}; 252 253/* Loop recognition. */ 254bool bb_loop_header_p (basic_block); 255void init_loops_structure (struct function *, struct loops *, unsigned); 256extern struct loops *flow_loops_find (struct loops *); 257extern void disambiguate_loops_with_multiple_latches (void); 258extern void flow_loops_free (struct loops *); 259extern void flow_loops_dump (FILE *, 260 void (*)(const struct loop *, FILE *, int), int); 261extern void flow_loop_dump (const struct loop *, FILE *, 262 void (*)(const struct loop *, FILE *, int), int); 263struct loop *alloc_loop (void); 264extern void flow_loop_free (struct loop *); 265int flow_loop_nodes_find (basic_block, struct loop *); 266unsigned fix_loop_structure (bitmap changed_bbs); 267bool mark_irreducible_loops (void); 268void release_recorded_exits (void); 269void record_loop_exits (void); 270void rescan_loop_exit (edge, bool, bool); 271 272/* Loop data structure manipulation/querying. */ 273extern void flow_loop_tree_node_add (struct loop *, struct loop *); 274extern void flow_loop_tree_node_remove (struct loop *); 275extern bool flow_loop_nested_p (const struct loop *, const struct loop *); 276extern bool flow_bb_inside_loop_p (const struct loop *, const_basic_block); 277extern struct loop * find_common_loop (struct loop *, struct loop *); 278struct loop *superloop_at_depth (struct loop *, unsigned); 279struct eni_weights_d; 280extern int num_loop_insns (const struct loop *); 281extern int average_num_loop_insns (const struct loop *); 282extern unsigned get_loop_level (const struct loop *); 283extern bool loop_exit_edge_p (const struct loop *, const_edge); 284extern bool loop_exits_to_bb_p (struct loop *, basic_block); 285extern bool loop_exits_from_bb_p (struct loop *, basic_block); 286extern void mark_loop_exit_edges (void); 287extern location_t get_loop_location (struct loop *loop); 288 289/* Loops & cfg manipulation. */ 290extern basic_block *get_loop_body (const struct loop *); 291extern unsigned get_loop_body_with_size (const struct loop *, basic_block *, 292 unsigned); 293extern basic_block *get_loop_body_in_dom_order (const struct loop *); 294extern basic_block *get_loop_body_in_bfs_order (const struct loop *); 295extern basic_block *get_loop_body_in_custom_order (const struct loop *, 296 int (*) (const void *, const void *)); 297 298extern vec<edge> get_loop_exit_edges (const struct loop *); 299extern edge single_exit (const struct loop *); 300extern edge single_likely_exit (struct loop *loop); 301extern unsigned num_loop_branches (const struct loop *); 302 303extern edge loop_preheader_edge (const struct loop *); 304extern edge loop_latch_edge (const struct loop *); 305 306extern void add_bb_to_loop (basic_block, struct loop *); 307extern void remove_bb_from_loops (basic_block); 308 309extern void cancel_loop_tree (struct loop *); 310extern void delete_loop (struct loop *); 311 312 313extern void verify_loop_structure (void); 314 315/* Loop analysis. */ 316extern bool just_once_each_iteration_p (const struct loop *, const_basic_block); 317gcov_type expected_loop_iterations_unbounded (const struct loop *); 318extern unsigned expected_loop_iterations (const struct loop *); 319extern rtx doloop_condition_get (rtx); 320 321void mark_loop_for_removal (loop_p); 322 323/* Induction variable analysis. */ 324 325/* The description of induction variable. The things are a bit complicated 326 due to need to handle subregs and extends. The value of the object described 327 by it can be obtained as follows (all computations are done in extend_mode): 328 329 Value in i-th iteration is 330 delta + mult * extend_{extend_mode} (subreg_{mode} (base + i * step)). 331 332 If first_special is true, the value in the first iteration is 333 delta + mult * base 334 335 If extend = UNKNOWN, first_special must be false, delta 0, mult 1 and value is 336 subreg_{mode} (base + i * step) 337 338 The get_iv_value function can be used to obtain these expressions. 339 340 ??? Add a third mode field that would specify the mode in that inner 341 computation is done, which would enable it to be different from the 342 outer one? */ 343 344struct rtx_iv 345{ 346 /* Its base and step (mode of base and step is supposed to be extend_mode, 347 see the description above). */ 348 rtx base, step; 349 350 /* The type of extend applied to it (IV_SIGN_EXTEND, IV_ZERO_EXTEND, 351 or IV_UNKNOWN_EXTEND). */ 352 enum iv_extend_code extend; 353 354 /* Operations applied in the extended mode. */ 355 rtx delta, mult; 356 357 /* The mode it is extended to. */ 358 machine_mode extend_mode; 359 360 /* The mode the variable iterates in. */ 361 machine_mode mode; 362 363 /* Whether the first iteration needs to be handled specially. */ 364 unsigned first_special : 1; 365}; 366 367/* The description of an exit from the loop and of the number of iterations 368 till we take the exit. */ 369 370struct GTY(()) niter_desc 371{ 372 /* The edge out of the loop. */ 373 edge out_edge; 374 375 /* The other edge leading from the condition. */ 376 edge in_edge; 377 378 /* True if we are able to say anything about number of iterations of the 379 loop. */ 380 bool simple_p; 381 382 /* True if the loop iterates the constant number of times. */ 383 bool const_iter; 384 385 /* Number of iterations if constant. */ 386 uint64_t niter; 387 388 /* Assumptions under that the rest of the information is valid. */ 389 rtx assumptions; 390 391 /* Assumptions under that the loop ends before reaching the latch, 392 even if value of niter_expr says otherwise. */ 393 rtx noloop_assumptions; 394 395 /* Condition under that the loop is infinite. */ 396 rtx infinite; 397 398 /* Whether the comparison is signed. */ 399 bool signed_p; 400 401 /* The mode in that niter_expr should be computed. */ 402 machine_mode mode; 403 404 /* The number of iterations of the loop. */ 405 rtx niter_expr; 406}; 407 408extern void iv_analysis_loop_init (struct loop *); 409extern bool iv_analyze (rtx_insn *, rtx, struct rtx_iv *); 410extern bool iv_analyze_result (rtx_insn *, rtx, struct rtx_iv *); 411extern bool iv_analyze_expr (rtx_insn *, rtx, machine_mode, 412 struct rtx_iv *); 413extern rtx get_iv_value (struct rtx_iv *, rtx); 414extern bool biv_p (rtx_insn *, rtx); 415extern void find_simple_exit (struct loop *, struct niter_desc *); 416extern void iv_analysis_done (void); 417 418extern struct niter_desc *get_simple_loop_desc (struct loop *loop); 419extern void free_simple_loop_desc (struct loop *loop); 420 421static inline struct niter_desc * 422simple_loop_desc (struct loop *loop) 423{ 424 return loop->simple_loop_desc; 425} 426 427/* Accessors for the loop structures. */ 428 429/* Returns the loop with index NUM from FNs loop tree. */ 430 431static inline struct loop * 432get_loop (struct function *fn, unsigned num) 433{ 434 return (*loops_for_fn (fn)->larray)[num]; 435} 436 437/* Returns the number of superloops of LOOP. */ 438 439static inline unsigned 440loop_depth (const struct loop *loop) 441{ 442 return vec_safe_length (loop->superloops); 443} 444 445/* Returns the immediate superloop of LOOP, or NULL if LOOP is the outermost 446 loop. */ 447 448static inline struct loop * 449loop_outer (const struct loop *loop) 450{ 451 unsigned n = vec_safe_length (loop->superloops); 452 453 if (n == 0) 454 return NULL; 455 456 return (*loop->superloops)[n - 1]; 457} 458 459/* Returns true if LOOP has at least one exit edge. */ 460 461static inline bool 462loop_has_exit_edges (const struct loop *loop) 463{ 464 return loop->exits->next->e != NULL; 465} 466 467/* Returns the list of loops in FN. */ 468 469inline vec<loop_p, va_gc> * 470get_loops (struct function *fn) 471{ 472 struct loops *loops = loops_for_fn (fn); 473 if (!loops) 474 return NULL; 475 476 return loops->larray; 477} 478 479/* Returns the number of loops in FN (including the removed 480 ones and the fake loop that forms the root of the loop tree). */ 481 482static inline unsigned 483number_of_loops (struct function *fn) 484{ 485 struct loops *loops = loops_for_fn (fn); 486 if (!loops) 487 return 0; 488 489 return vec_safe_length (loops->larray); 490} 491 492/* Returns true if state of the loops satisfies all properties 493 described by FLAGS. */ 494 495static inline bool 496loops_state_satisfies_p (unsigned flags) 497{ 498 return (current_loops->state & flags) == flags; 499} 500 501/* Sets FLAGS to the loops state. */ 502 503static inline void 504loops_state_set (unsigned flags) 505{ 506 current_loops->state |= flags; 507} 508 509/* Clears FLAGS from the loops state. */ 510 511static inline void 512loops_state_clear (unsigned flags) 513{ 514 if (!current_loops) 515 return; 516 current_loops->state &= ~flags; 517} 518 519/* Loop iterators. */ 520 521/* Flags for loop iteration. */ 522 523enum li_flags 524{ 525 LI_INCLUDE_ROOT = 1, /* Include the fake root of the loop tree. */ 526 LI_FROM_INNERMOST = 2, /* Iterate over the loops in the reverse order, 527 starting from innermost ones. */ 528 LI_ONLY_INNERMOST = 4 /* Iterate only over innermost loops. */ 529}; 530 531/* The iterator for loops. */ 532 533struct loop_iterator 534{ 535 loop_iterator (loop_p *loop, unsigned flags); 536 ~loop_iterator (); 537 538 inline loop_p next (); 539 540 /* The list of loops to visit. */ 541 vec<int> to_visit; 542 543 /* The index of the actual loop. */ 544 unsigned idx; 545}; 546 547inline loop_p 548loop_iterator::next () 549{ 550 int anum; 551 552 while (this->to_visit.iterate (this->idx, &anum)) 553 { 554 this->idx++; 555 loop_p loop = get_loop (cfun, anum); 556 if (loop) 557 return loop; 558 } 559 560 return NULL; 561} 562 563inline 564loop_iterator::loop_iterator (loop_p *loop, unsigned flags) 565{ 566 struct loop *aloop; 567 unsigned i; 568 int mn; 569 570 this->idx = 0; 571 if (!current_loops) 572 { 573 this->to_visit.create (0); 574 *loop = NULL; 575 return; 576 } 577 578 this->to_visit.create (number_of_loops (cfun)); 579 mn = (flags & LI_INCLUDE_ROOT) ? 0 : 1; 580 581 if (flags & LI_ONLY_INNERMOST) 582 { 583 for (i = 0; vec_safe_iterate (current_loops->larray, i, &aloop); i++) 584 if (aloop != NULL 585 && aloop->inner == NULL 586 && aloop->num >= mn) 587 this->to_visit.quick_push (aloop->num); 588 } 589 else if (flags & LI_FROM_INNERMOST) 590 { 591 /* Push the loops to LI->TO_VISIT in postorder. */ 592 for (aloop = current_loops->tree_root; 593 aloop->inner != NULL; 594 aloop = aloop->inner) 595 continue; 596 597 while (1) 598 { 599 if (aloop->num >= mn) 600 this->to_visit.quick_push (aloop->num); 601 602 if (aloop->next) 603 { 604 for (aloop = aloop->next; 605 aloop->inner != NULL; 606 aloop = aloop->inner) 607 continue; 608 } 609 else if (!loop_outer (aloop)) 610 break; 611 else 612 aloop = loop_outer (aloop); 613 } 614 } 615 else 616 { 617 /* Push the loops to LI->TO_VISIT in preorder. */ 618 aloop = current_loops->tree_root; 619 while (1) 620 { 621 if (aloop->num >= mn) 622 this->to_visit.quick_push (aloop->num); 623 624 if (aloop->inner != NULL) 625 aloop = aloop->inner; 626 else 627 { 628 while (aloop != NULL && aloop->next == NULL) 629 aloop = loop_outer (aloop); 630 if (aloop == NULL) 631 break; 632 aloop = aloop->next; 633 } 634 } 635 } 636 637 *loop = this->next (); 638} 639 640inline 641loop_iterator::~loop_iterator () 642{ 643 this->to_visit.release (); 644} 645 646#define FOR_EACH_LOOP(LOOP, FLAGS) \ 647 for (loop_iterator li(&(LOOP), FLAGS); \ 648 (LOOP); \ 649 (LOOP) = li.next ()) 650 651/* The properties of the target. */ 652struct target_cfgloop { 653 /* Number of available registers. */ 654 unsigned x_target_avail_regs; 655 656 /* Number of available registers that are call-clobbered. */ 657 unsigned x_target_clobbered_regs; 658 659 /* Number of registers reserved for temporary expressions. */ 660 unsigned x_target_res_regs; 661 662 /* The cost for register when there still is some reserve, but we are 663 approaching the number of available registers. */ 664 unsigned x_target_reg_cost[2]; 665 666 /* The cost for register when we need to spill. */ 667 unsigned x_target_spill_cost[2]; 668}; 669 670extern struct target_cfgloop default_target_cfgloop; 671#if SWITCHABLE_TARGET 672extern struct target_cfgloop *this_target_cfgloop; 673#else 674#define this_target_cfgloop (&default_target_cfgloop) 675#endif 676 677#define target_avail_regs \ 678 (this_target_cfgloop->x_target_avail_regs) 679#define target_clobbered_regs \ 680 (this_target_cfgloop->x_target_clobbered_regs) 681#define target_res_regs \ 682 (this_target_cfgloop->x_target_res_regs) 683#define target_reg_cost \ 684 (this_target_cfgloop->x_target_reg_cost) 685#define target_spill_cost \ 686 (this_target_cfgloop->x_target_spill_cost) 687 688/* Register pressure estimation for induction variable optimizations & loop 689 invariant motion. */ 690extern unsigned estimate_reg_pressure_cost (unsigned, unsigned, bool, bool); 691extern void init_set_costs (void); 692 693/* Loop optimizer initialization. */ 694extern void loop_optimizer_init (unsigned); 695extern void loop_optimizer_finalize (void); 696 697/* Optimization passes. */ 698enum 699{ 700 UAP_UNROLL = 1, /* Enables unrolling of loops if it seems profitable. */ 701 UAP_UNROLL_ALL = 2 /* Enables unrolling of all loops. */ 702}; 703 704extern void doloop_optimize_loops (void); 705extern void move_loop_invariants (void); 706extern vec<basic_block> get_loop_hot_path (const struct loop *loop); 707 708/* Returns the outermost loop of the loop nest that contains LOOP.*/ 709static inline struct loop * 710loop_outermost (struct loop *loop) 711{ 712 unsigned n = vec_safe_length (loop->superloops); 713 714 if (n <= 1) 715 return loop; 716 717 return (*loop->superloops)[1]; 718} 719 720extern void record_niter_bound (struct loop *, const widest_int &, bool, bool); 721extern HOST_WIDE_INT get_estimated_loop_iterations_int (struct loop *); 722extern HOST_WIDE_INT get_max_loop_iterations_int (struct loop *); 723extern bool get_estimated_loop_iterations (struct loop *loop, widest_int *nit); 724extern bool get_max_loop_iterations (struct loop *loop, widest_int *nit); 725extern int bb_loop_depth (const_basic_block); 726 727/* Converts VAL to widest_int. */ 728 729static inline widest_int 730gcov_type_to_wide_int (gcov_type val) 731{ 732 HOST_WIDE_INT a[2]; 733 734 a[0] = (unsigned HOST_WIDE_INT) val; 735 /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by 736 the size of type. */ 737 val >>= HOST_BITS_PER_WIDE_INT - 1; 738 val >>= 1; 739 a[1] = (unsigned HOST_WIDE_INT) val; 740 741 return widest_int::from_array (a, 2); 742} 743#endif /* GCC_CFGLOOP_H */ 744