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 void sort_sibling_loops (function *);
 337
 338 /* Loop data structure manipulation/querying.  */
 339 extern void flow_loop_tree_node_add (struct loop *, struct loop *);
 340 extern void flow_loop_tree_node_remove (struct loop *);
 341 extern bool flow_loop_nested_p  (const struct loop *, const struct loop *);
 342 extern bool flow_bb_inside_loop_p (const struct loop *, const_basic_block);
 343 extern struct loop * find_common_loop (struct loop *, struct loop *);
 344 struct loop *superloop_at_depth (struct loop *, unsigned);
 345 struct eni_weights;
 346 extern int num_loop_insns (const struct loop *);
 347 extern int average_num_loop_insns (const struct loop *);
 348 extern unsigned get_loop_level (const struct loop *);
 349 extern bool loop_exit_edge_p (const struct loop *, const_edge);
 350 extern bool loop_exits_to_bb_p (struct loop *, basic_block);
 351 extern bool loop_exits_from_bb_p (struct loop *, basic_block);
 352 extern void mark_loop_exit_edges (void);
 353 extern location_t get_loop_location (struct loop *loop);
 354
 355 /* Loops & cfg manipulation.  */
 356 extern basic_block *get_loop_body (const struct loop *);
 357 extern unsigned get_loop_body_with_size (const struct loop *, basic_block *,
 358                                          unsigned);
 359 extern basic_block *get_loop_body_in_dom_order (const struct loop *);
 360 extern basic_block *get_loop_body_in_bfs_order (const struct loop *);
 361 extern basic_block *get_loop_body_in_custom_order (const struct loop *,
 362                                int (*) (const void *, const void *));
 363
 364 extern vec<edge> get_loop_exit_edges (const struct loop *);
 365 extern edge single_exit (const struct loop *);
 366 extern edge single_likely_exit (struct loop *loop);
 367 extern unsigned num_loop_branches (const struct loop *);
 368
 369 extern edge loop_preheader_edge (const struct loop *);
 370 extern edge loop_latch_edge (const struct loop *);
 371
 372 extern void add_bb_to_loop (basic_block, struct loop *);
 373 extern void remove_bb_from_loops (basic_block);
 374
 375 extern void cancel_loop_tree (struct loop *);
 376 extern void delete_loop (struct loop *);
 377
 378
 379 extern void verify_loop_structure (void);
 380
 381 /* Loop analysis.  */
 382 extern bool just_once_each_iteration_p (const struct loop *, const_basic_block);
 383 gcov_type expected_loop_iterations_unbounded (const struct loop *,
 384                                               bool *read_profile_p = NULL);
 385 extern unsigned expected_loop_iterations (struct loop *);
 386 extern rtx doloop_condition_get (rtx_insn *);
 387
 388 void mark_loop_for_removal (loop_p);
 389
 390 /* Induction variable analysis.  */
 391
 392 /* The description of induction variable.  The things are a bit complicated
 393    due to need to handle subregs and extends.  The value of the object described
 394    by it can be obtained as follows (all computations are done in extend_mode):
 395
 396    Value in i-th iteration is
 397      delta + mult * extend_{extend_mode} (subreg_{mode} (base + i * step)).
 398
 399    If first_special is true, the value in the first iteration is
 400      delta + mult * base
 401
 402    If extend = UNKNOWN, first_special must be false, delta 0, mult 1 and value is
 403      subreg_{mode} (base + i * step)
 404
 405    The get_iv_value function can be used to obtain these expressions.
 406
 407    ??? Add a third mode field that would specify the mode in that inner
 408    computation is done, which would enable it to be different from the
 409    outer one?  */
 410
 411 struct rtx_iv
 412 {
 413   /* Its base and step (mode of base and step is supposed to be extend_mode,
 414      see the description above).  */
 415   rtx base, step;
 416
 417   /* The type of extend applied to it (IV_SIGN_EXTEND, IV_ZERO_EXTEND,
 418      or IV_UNKNOWN_EXTEND).  */
 419   enum iv_extend_code extend;
 420
 421   /* Operations applied in the extended mode.  */
 422   rtx delta, mult;
 423
 424   /* The mode it is extended to.  */
 425   scalar_int_mode extend_mode;
 426
 427   /* The mode the variable iterates in.  */
 428   scalar_int_mode mode;
 429
 430   /* Whether the first iteration needs to be handled specially.  */
 431   unsigned first_special : 1;
 432 };
 433
 434 /* The description of an exit from the loop and of the number of iterations
 435    till we take the exit.  */
 436
 437 struct GTY(()) niter_desc
 438 {
 439   /* The edge out of the loop.  */
 440   edge out_edge;
 441
 442   /* The other edge leading from the condition.  */
 443   edge in_edge;
 444
 445   /* True if we are able to say anything about number of iterations of the
 446      loop.  */
 447   bool simple_p;
 448
 449   /* True if the loop iterates the constant number of times.  */
 450   bool const_iter;
 451
 452   /* Number of iterations if constant.  */
 453   uint64_t niter;
 454
 455   /* Assumptions under that the rest of the information is valid.  */
 456   rtx assumptions;
 457
 458   /* Assumptions under that the loop ends before reaching the latch,
 459      even if value of niter_expr says otherwise.  */
 460   rtx noloop_assumptions;
 461
 462   /* Condition under that the loop is infinite.  */
 463   rtx infinite;
 464
 465   /* Whether the comparison is signed.  */
 466   bool signed_p;
 467
 468   /* The mode in that niter_expr should be computed.  */
 469   scalar_int_mode mode;
 470
 471   /* The number of iterations of the loop.  */
 472   rtx niter_expr;
 473 };
 474
 475 extern void iv_analysis_loop_init (struct loop *);
 476 extern bool iv_analyze (rtx_insn *, scalar_int_mode, rtx, struct rtx_iv *);
 477 extern bool iv_analyze_result (rtx_insn *, rtx, struct rtx_iv *);
 478 extern bool iv_analyze_expr (rtx_insn *, scalar_int_mode, rtx,
 479                              struct rtx_iv *);
 480 extern rtx get_iv_value (struct rtx_iv *, rtx);
 481 extern bool biv_p (rtx_insn *, scalar_int_mode, rtx);
 482 extern void find_simple_exit (struct loop *, struct niter_desc *);
 483 extern void iv_analysis_done (void);
 484
 485 extern struct niter_desc *get_simple_loop_desc (struct loop *loop);
 486 extern void free_simple_loop_desc (struct loop *loop);
 487
 488 static inline struct niter_desc *
 489 simple_loop_desc (struct loop *loop)
 490 {
 491   return loop->simple_loop_desc;
 492 }
 493
 494 /* Accessors for the loop structures.  */
 495
 496 /* Returns the loop with index NUM from FNs loop tree.  */
 497
 498 static inline struct loop *
 499 get_loop (struct function *fn, unsigned num)
 500 {
 501   return (*loops_for_fn (fn)->larray)[num];
 502 }
 503
 504 /* Returns the number of superloops of LOOP.  */
 505
 506 static inline unsigned
 507 loop_depth (const struct loop *loop)
 508 {
 509   return vec_safe_length (loop->superloops);
 510 }
 511
 512 /* Returns the immediate superloop of LOOP, or NULL if LOOP is the outermost
 513    loop.  */
 514
 515 static inline struct loop *
 516 loop_outer (const struct loop *loop)
 517 {
 518   unsigned n = vec_safe_length (loop->superloops);
 519
 520   if (n == 0)
 521     return NULL;
 522
 523   return (*loop->superloops)[n - 1];
 524 }
 525
 526 /* Returns true if LOOP has at least one exit edge.  */
 527
 528 static inline bool
 529 loop_has_exit_edges (const struct loop *loop)
 530 {
 531   return loop->exits->next->e != NULL;
 532 }
 533
 534 /* Returns the list of loops in FN.  */
 535
 536 inline vec<loop_p, va_gc> *
 537 get_loops (struct function *fn)
 538 {
 539   struct loops *loops = loops_for_fn (fn);
 540   if (!loops)
 541     return NULL;
 542
 543   return loops->larray;
 544 }
 545
 546 /* Returns the number of loops in FN (including the removed
 547    ones and the fake loop that forms the root of the loop tree).  */
 548
 549 static inline unsigned
 550 number_of_loops (struct function *fn)
 551 {
 552   struct loops *loops = loops_for_fn (fn);
 553   if (!loops)
 554     return 0;
 555
 556   return vec_safe_length (loops->larray);
 557 }
 558
 559 /* Returns true if state of the loops satisfies all properties
 560    described by FLAGS.  */
 561
 562 static inline bool
 563 loops_state_satisfies_p (function *fn, unsigned flags)
 564 {
 565   return (loops_for_fn (fn)->state & flags) == flags;
 566 }
 567
 568 static inline bool
 569 loops_state_satisfies_p (unsigned flags)
 570 {
 571   return loops_state_satisfies_p (cfun, flags);
 572 }
 573
 574 /* Sets FLAGS to the loops state.  */
 575
 576 static inline void
 577 loops_state_set (function *fn, unsigned flags)
 578 {
 579   loops_for_fn (fn)->state |= flags;
 580 }
 581
 582 static inline void
 583 loops_state_set (unsigned flags)
 584 {
 585   loops_state_set (cfun, flags);
 586 }
 587
 588 /* Clears FLAGS from the loops state.  */
 589
 590 static inline void
 591 loops_state_clear (function *fn, unsigned flags)
 592 {
 593   loops_for_fn (fn)->state &= ~flags;
 594 }
 595
 596 static inline void
 597 loops_state_clear (unsigned flags)
 598 {
 599   if (!current_loops)
 600     return;
 601   loops_state_clear (cfun, flags);
 602 }
 603
 604 /* Check loop structure invariants, if internal consistency checks are
 605    enabled.  */
 606
 607 static inline void
 608 checking_verify_loop_structure (void)
 609 {
 610   /* VERIFY_LOOP_STRUCTURE essentially asserts that no loops need fixups.
 611
 612      The loop optimizers should never make changes to the CFG which
 613      require loop fixups.  But the low level CFG manipulation code may
 614      set the flag conservatively.
 615
 616      Go ahead and clear the flag here.  That avoids the assert inside
 617      VERIFY_LOOP_STRUCTURE, and if there is an inconsistency in the loop
 618      structures VERIFY_LOOP_STRUCTURE will detect it.
 619
 620      This also avoid the compile time cost of excessive fixups.  */
 621   loops_state_clear (LOOPS_NEED_FIXUP);
 622   if (flag_checking)
 623     verify_loop_structure ();
 624 }
 625
 626 /* Loop iterators.  */
 627
 628 /* Flags for loop iteration.  */
 629
 630 enum li_flags
 631 {
 632   LI_INCLUDE_ROOT = 1,          /* Include the fake root of the loop tree.  */
 633   LI_FROM_INNERMOST = 2,        /* Iterate over the loops in the reverse order,
 634                                    starting from innermost ones.  */
 635   LI_ONLY_INNERMOST = 4         /* Iterate only over innermost loops.  */
 636 };
 637
 638 /* The iterator for loops.  */
 639
 640 struct loop_iterator
 641 {
 642   loop_iterator (function *fn, loop_p *loop, unsigned flags);
 643   ~loop_iterator ();
 644
 645   inline loop_p next ();
 646
 647   /* The function we are visiting.  */
 648   function *fn;
 649
 650   /* The list of loops to visit.  */
 651   vec<int> to_visit;
 652
 653   /* The index of the actual loop.  */
 654   unsigned idx;
 655 };
 656
 657 inline loop_p
 658 loop_iterator::next ()
 659 {
 660   int anum;
 661
 662   while (this->to_visit.iterate (this->idx, &anum))
 663     {
 664       this->idx++;
 665       loop_p loop = get_loop (fn, anum);
 666       if (loop)
 667         return loop;
 668     }
 669
 670   return NULL;
 671 }
 672
 673 inline
 674 loop_iterator::loop_iterator (function *fn, loop_p *loop, unsigned flags)
 675 {
 676   struct loop *aloop;
 677   unsigned i;
 678   int mn;
 679
 680   this->idx = 0;
 681   this->fn = fn;
 682   if (!loops_for_fn (fn))
 683     {
 684       this->to_visit.create (0);
 685       *loop = NULL;
 686       return;
 687     }
 688
 689   this->to_visit.create (number_of_loops (fn));
 690   mn = (flags & LI_INCLUDE_ROOT) ? 0 : 1;
 691
 692   if (flags & LI_ONLY_INNERMOST)
 693     {
 694       for (i = 0; vec_safe_iterate (loops_for_fn (fn)->larray, i, &aloop); i++)
 695         if (aloop != NULL
 696             && aloop->inner == NULL
 697             && aloop->num >= mn)
 698           this->to_visit.quick_push (aloop->num);
 699     }
 700   else if (flags & LI_FROM_INNERMOST)
 701     {
 702       /* Push the loops to LI->TO_VISIT in postorder.  */
 703       for (aloop = loops_for_fn (fn)->tree_root;
 704            aloop->inner != NULL;
 705            aloop = aloop->inner)
 706         continue;
 707
 708       while (1)
 709         {
 710           if (aloop->num >= mn)
 711             this->to_visit.quick_push (aloop->num);
 712
 713           if (aloop->next)
 714             {
 715               for (aloop = aloop->next;
 716                    aloop->inner != NULL;
 717                    aloop = aloop->inner)
 718                 continue;
 719             }
 720           else if (!loop_outer (aloop))
 721             break;
 722           else
 723             aloop = loop_outer (aloop);
 724         }
 725     }
 726   else
 727     {
 728       /* Push the loops to LI->TO_VISIT in preorder.  */
 729       aloop = loops_for_fn (fn)->tree_root;
 730       while (1)
 731         {
 732           if (aloop->num >= mn)
 733             this->to_visit.quick_push (aloop->num);
 734
 735           if (aloop->inner != NULL)
 736             aloop = aloop->inner;
 737           else
 738             {
 739               while (aloop != NULL && aloop->next == NULL)
 740                 aloop = loop_outer (aloop);
 741               if (aloop == NULL)
 742                 break;
 743               aloop = aloop->next;
 744             }
 745         }
 746     }
 747
 748   *loop = this->next ();
 749 }
 750
 751 inline
 752 loop_iterator::~loop_iterator ()
 753 {
 754   this->to_visit.release ();
 755 }
 756
 757 #define FOR_EACH_LOOP(LOOP, FLAGS) \
 758   for (loop_iterator li(cfun, &(LOOP), FLAGS); \
 759        (LOOP); \
 760        (LOOP) = li.next ())
 761
 762 #define FOR_EACH_LOOP_FN(FN, LOOP, FLAGS) \
 763   for (loop_iterator li(fn, &(LOOP), FLAGS); \
 764        (LOOP); \
 765        (LOOP) = li.next ())
 766
 767 /* The properties of the target.  */
 768 struct target_cfgloop {
 769   /* Number of available registers.  */
 770   unsigned x_target_avail_regs;
 771
 772   /* Number of available registers that are call-clobbered.  */
 773   unsigned x_target_clobbered_regs;
 774
 775   /* Number of registers reserved for temporary expressions.  */
 776   unsigned x_target_res_regs;
 777
 778   /* The cost for register when there still is some reserve, but we are
 779      approaching the number of available registers.  */
 780   unsigned x_target_reg_cost[2];
 781
 782   /* The cost for register when we need to spill.  */
 783   unsigned x_target_spill_cost[2];
 784 };
 785
 786 extern struct target_cfgloop default_target_cfgloop;
 787 #if SWITCHABLE_TARGET
 788 extern struct target_cfgloop *this_target_cfgloop;
 789 #else
 790 #define this_target_cfgloop (&default_target_cfgloop)
 791 #endif
 792
 793 #define target_avail_regs \
 794   (this_target_cfgloop->x_target_avail_regs)
 795 #define target_clobbered_regs \
 796   (this_target_cfgloop->x_target_clobbered_regs)
 797 #define target_res_regs \
 798   (this_target_cfgloop->x_target_res_regs)
 799 #define target_reg_cost \
 800   (this_target_cfgloop->x_target_reg_cost)
 801 #define target_spill_cost \
 802   (this_target_cfgloop->x_target_spill_cost)
 803
 804 /* Register pressure estimation for induction variable optimizations & loop
 805    invariant motion.  */
 806 extern unsigned estimate_reg_pressure_cost (unsigned, unsigned, bool, bool);
 807 extern void init_set_costs (void);
 808
 809 /* Loop optimizer initialization.  */
 810 extern void loop_optimizer_init (unsigned);
 811 extern void loop_optimizer_finalize (function *);
 812 inline void
 813 loop_optimizer_finalize ()
 814 {
 815   loop_optimizer_finalize (cfun);
 816 }
 817
 818 /* Optimization passes.  */
 819 enum
 820 {
 821   UAP_UNROLL = 1,       /* Enables unrolling of loops if it seems profitable.  */
 822   UAP_UNROLL_ALL = 2    /* Enables unrolling of all loops.  */
 823 };
 824
 825 extern void doloop_optimize_loops (void);
 826 extern void move_loop_invariants (void);
 827 extern vec<basic_block> get_loop_hot_path (const struct loop *loop);
 828
 829 /* Returns the outermost loop of the loop nest that contains LOOP.*/
 830 static inline struct loop *
 831 loop_outermost (struct loop *loop)
 832 {
 833   unsigned n = vec_safe_length (loop->superloops);
 834
 835   if (n <= 1)
 836     return loop;
 837
 838   return (*loop->superloops)[1];
 839 }
 840
 841 extern void record_niter_bound (struct loop *, const widest_int &, bool, bool);
 842 extern HOST_WIDE_INT get_estimated_loop_iterations_int (struct loop *);
 843 extern HOST_WIDE_INT get_max_loop_iterations_int (const struct loop *);
 844 extern HOST_WIDE_INT get_likely_max_loop_iterations_int (struct loop *);
 845 extern bool get_estimated_loop_iterations (struct loop *loop, widest_int *nit);
 846 extern bool get_max_loop_iterations (const struct loop *loop, widest_int *nit);
 847 extern bool get_likely_max_loop_iterations (struct loop *loop, widest_int *nit);
 848 extern int bb_loop_depth (const_basic_block);
 849
 850 /* Converts VAL to widest_int.  */
 851
 852 static inline widest_int
 853 gcov_type_to_wide_int (gcov_type val)
 854 {
 855   HOST_WIDE_INT a[2];
 856
 857   a[0] = (unsigned HOST_WIDE_INT) val;
 858   /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
 859      the size of type.  */
 860   val >>= HOST_BITS_PER_WIDE_INT - 1;
 861   val >>= 1;
 862   a[1] = (unsigned HOST_WIDE_INT) val;
 863
 864   return widest_int::from_array (a, 2);
 865 }
 866 #endif /* GCC_CFGLOOP_H */