gcc/cfgloop.h

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