gcc/cfgloop.h

   1 /* Natural loop functions
   2    Copyright (C) 1987-2019 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   /* Preferred vectorization factor for the loop if non-zero.  */
 178   int simdlen;
 179
 180   /* Constraints are generally set by consumers and affect certain
 181      semantics of niter analyzer APIs.  Currently the APIs affected are
 182      number_of_iterations_exit* functions and their callers.  One typical
 183      use case of constraints is to vectorize possibly infinite loop:
 184
 185        1) Compute niter->assumptions by calling niter analyzer API and
 186           record it as possible condition for loop versioning.
 187        2) Clear buffered result of niter/scev analyzer.
 188        3) Set constraint LOOP_C_FINITE assuming the loop is finite.
 189        4) Analyze data references.  Since data reference analysis depends
 190           on niter/scev analyzer, the point is that niter/scev analysis
 191           is done under circumstance of LOOP_C_FINITE constraint.
 192        5) Version the loop with niter->assumptions computed in step 1).
 193        6) Vectorize the versioned loop in which niter->assumptions is
 194           checked to be true.
 195        7) Update constraints in versioned loops so that niter analyzer
 196           in following passes can use it.
 197
 198      Note consumers are usually the loop optimizers and it is consumers'
 199      responsibility to set/clear constraints correctly.  Failing to do
 200      that might result in hard to track down bugs in niter/scev consumers.  */
 201   unsigned constraints;
 202
 203   /* An integer estimation of the number of iterations.  Estimate_state
 204      describes what is the state of the estimation.  */
 205   ENUM_BITFIELD(loop_estimation) estimate_state : 8;
 206
 207   unsigned any_upper_bound : 1;
 208   unsigned any_estimate : 1;
 209   unsigned any_likely_upper_bound : 1;
 210
 211   /* True if the loop can be parallel.  */
 212   unsigned can_be_parallel : 1;
 213
 214   /* True if -Waggressive-loop-optimizations warned about this loop
 215      already.  */
 216   unsigned warned_aggressive_loop_optimizations : 1;
 217
 218   /* True if this loop should never be vectorized.  */
 219   unsigned dont_vectorize : 1;
 220
 221   /* True if we should try harder to vectorize this loop.  */
 222   unsigned force_vectorize : 1;
 223
 224   /* True if the loop is part of an oacc kernels region.  */
 225   unsigned in_oacc_kernels_region : 1;
 226
 227   /* The number of times to unroll the loop.  0 means no information given,
 228      just do what we always do.  A value of 1 means do not unroll the loop.
 229      A value of USHRT_MAX means unroll with no specific unrolling factor.
 230      Other values means unroll with the given unrolling factor.  */
 231   unsigned short unroll;
 232
 233   /* If this loop was inlined the main clique of the callee which does
 234      not need remapping when copying the loop body.  */
 235   unsigned short owned_clique;
 236
 237   /* For SIMD loops, this is a unique identifier of the loop, referenced
 238      by IFN_GOMP_SIMD_VF, IFN_GOMP_SIMD_LANE and IFN_GOMP_SIMD_LAST_LANE
 239      builtins.  */
 240   tree simduid;
 241
 242   /* In loop optimization, it's common to generate loops from the original
 243      loop.  This field records the index of the original loop which can be
 244      used to track the original loop from newly generated loops.  This can
 245      be done by calling function get_loop (cfun, orig_loop_num).  Note the
 246      original loop could be destroyed for various reasons thus no longer
 247      exists, as a result, function call to get_loop returns NULL pointer.
 248      In this case, this field should not be used and needs to be cleared
 249      whenever possible.  */
 250   int orig_loop_num;
 251
 252   /* Upper bound on number of iterations of a loop.  */
 253   struct nb_iter_bound *bounds;
 254
 255   /* Non-overflow control ivs of a loop.  */
 256   struct control_iv *control_ivs;
 257
 258   /* Head of the cyclic list of the exits of the loop.  */
 259   struct loop_exit *exits;
 260
 261   /* Number of iteration analysis data for RTL.  */
 262   struct niter_desc *simple_loop_desc;
 263
 264   /* For sanity checking during loop fixup we record here the former
 265      loop header for loops marked for removal.  Note that this prevents
 266      the basic-block from being collected but its index can still be
 267      reused.  */
 268   basic_block former_header;
 269 };
 270
 271 /* Set if the loop is known to be infinite.  */
 272 #define LOOP_C_INFINITE         (1 << 0)
 273 /* Set if the loop is known to be finite without any assumptions.  */
 274 #define LOOP_C_FINITE           (1 << 1)
 275
 276 /* Set C to the LOOP constraint.  */
 277 static inline void
 278 loop_constraint_set (struct loop *loop, unsigned c)
 279 {
 280   loop->constraints |= c;
 281 }
 282
 283 /* Clear C from the LOOP constraint.  */
 284 static inline void
 285 loop_constraint_clear (struct loop *loop, unsigned c)
 286 {
 287   loop->constraints &= ~c;
 288 }
 289
 290 /* Check if C is set in the LOOP constraint.  */
 291 static inline bool
 292 loop_constraint_set_p (struct loop *loop, unsigned c)
 293 {
 294   return (loop->constraints & c) == c;
 295 }
 296
 297 /* Flags for state of loop structure.  */
 298 enum
 299 {
 300   LOOPS_HAVE_PREHEADERS = 1,
 301   LOOPS_HAVE_SIMPLE_LATCHES = 2,
 302   LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4,
 303   LOOPS_HAVE_RECORDED_EXITS = 8,
 304   LOOPS_MAY_HAVE_MULTIPLE_LATCHES = 16,
 305   LOOP_CLOSED_SSA = 32,
 306   LOOPS_NEED_FIXUP = 64,
 307   LOOPS_HAVE_FALLTHRU_PREHEADERS = 128
 308 };
 309
 310 #define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \
 311                       | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
 312 #define AVOID_CFG_MODIFICATIONS (LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
 313
 314 /* Structure to hold CFG information about natural loops within a function.  */
 315 struct GTY (()) loops {
 316   /* State of loops.  */
 317   int state;
 318
 319   /* Array of the loops.  */
 320   vec<loop_p, va_gc> *larray;
 321
 322   /* Maps edges to the list of their descriptions as loop exits.  Edges
 323      whose sources or destinations have loop_father == NULL (which may
 324      happen during the cfg manipulations) should not appear in EXITS.  */
 325   hash_table<loop_exit_hasher> *GTY(()) exits;
 326
 327   /* Pointer to root of loop hierarchy tree.  */
 328   struct loop *tree_root;
 329 };
 330
 331 /* Loop recognition.  */
 332 bool bb_loop_header_p (basic_block);
 333 void init_loops_structure (struct function *, struct loops *, unsigned);
 334 extern struct loops *flow_loops_find (struct loops *);
 335 extern void disambiguate_loops_with_multiple_latches (void);
 336 extern void flow_loops_free (struct loops *);
 337 extern void flow_loops_dump (FILE *,
 338                              void (*)(const struct loop *, FILE *, int), int);
 339 extern void flow_loop_dump (const struct loop *, FILE *,
 340                             void (*)(const struct loop *, FILE *, int), int);
 341 struct loop *alloc_loop (void);
 342 extern void flow_loop_free (struct loop *);
 343 int flow_loop_nodes_find (basic_block, struct loop *);
 344 unsigned fix_loop_structure (bitmap changed_bbs);
 345 bool mark_irreducible_loops (void);
 346 void release_recorded_exits (function *);
 347 void record_loop_exits (void);
 348 void rescan_loop_exit (edge, bool, bool);
 349 void sort_sibling_loops (function *);
 350
 351 /* Loop data structure manipulation/querying.  */
 352 extern void flow_loop_tree_node_add (struct loop *, struct loop *,
 353                                      struct loop * = NULL);
 354 extern void flow_loop_tree_node_remove (struct loop *);
 355 extern bool flow_loop_nested_p  (const struct loop *, const struct loop *);
 356 extern bool flow_bb_inside_loop_p (const struct loop *, const_basic_block);
 357 extern struct loop * find_common_loop (struct loop *, struct loop *);
 358 struct loop *superloop_at_depth (struct loop *, unsigned);
 359 struct eni_weights;
 360 extern int num_loop_insns (const struct loop *);
 361 extern int average_num_loop_insns (const struct loop *);
 362 extern unsigned get_loop_level (const struct loop *);
 363 extern bool loop_exit_edge_p (const struct loop *, const_edge);
 364 extern bool loop_exits_to_bb_p (struct loop *, basic_block);
 365 extern bool loop_exits_from_bb_p (struct loop *, basic_block);
 366 extern void mark_loop_exit_edges (void);
 367 extern dump_user_location_t get_loop_location (struct loop *loop);
 368
 369 /* Loops & cfg manipulation.  */
 370 extern basic_block *get_loop_body (const struct loop *);
 371 extern unsigned get_loop_body_with_size (const struct loop *, basic_block *,
 372                                          unsigned);
 373 extern basic_block *get_loop_body_in_dom_order (const struct loop *);
 374 extern basic_block *get_loop_body_in_bfs_order (const struct loop *);
 375 extern basic_block *get_loop_body_in_custom_order (const struct loop *,
 376                                int (*) (const void *, const void *));
 377
 378 extern vec<edge> get_loop_exit_edges (const struct loop *);
 379 extern edge single_exit (const struct loop *);
 380 extern edge single_likely_exit (struct loop *loop);
 381 extern unsigned num_loop_branches (const struct loop *);
 382
 383 extern edge loop_preheader_edge (const struct loop *);
 384 extern edge loop_latch_edge (const struct loop *);
 385
 386 extern void add_bb_to_loop (basic_block, struct loop *);
 387 extern void remove_bb_from_loops (basic_block);
 388
 389 extern void cancel_loop_tree (struct loop *);
 390 extern void delete_loop (struct loop *);
 391
 392
 393 extern void verify_loop_structure (void);
 394
 395 /* Loop analysis.  */
 396 extern bool just_once_each_iteration_p (const struct loop *, const_basic_block);
 397 gcov_type expected_loop_iterations_unbounded (const struct loop *,
 398                                               bool *read_profile_p = NULL, bool by_profile_only = false);
 399 extern unsigned expected_loop_iterations (struct loop *);
 400 extern rtx doloop_condition_get (rtx_insn *);
 401
 402 void mark_loop_for_removal (loop_p);
 403
 404 /* Induction variable analysis.  */
 405
 406 /* The description of induction variable.  The things are a bit complicated
 407    due to need to handle subregs and extends.  The value of the object described
 408    by it can be obtained as follows (all computations are done in extend_mode):
 409
 410    Value in i-th iteration is
 411      delta + mult * extend_{extend_mode} (subreg_{mode} (base + i * step)).
 412
 413    If first_special is true, the value in the first iteration is
 414      delta + mult * base
 415
 416    If extend = UNKNOWN, first_special must be false, delta 0, mult 1 and value is
 417      subreg_{mode} (base + i * step)
 418
 419    The get_iv_value function can be used to obtain these expressions.
 420
 421    ??? Add a third mode field that would specify the mode in that inner
 422    computation is done, which would enable it to be different from the
 423    outer one?  */
 424
 425 struct rtx_iv
 426 {
 427   /* Its base and step (mode of base and step is supposed to be extend_mode,
 428      see the description above).  */
 429   rtx base, step;
 430
 431   /* The type of extend applied to it (IV_SIGN_EXTEND, IV_ZERO_EXTEND,
 432      or IV_UNKNOWN_EXTEND).  */
 433   enum iv_extend_code extend;
 434
 435   /* Operations applied in the extended mode.  */
 436   rtx delta, mult;
 437
 438   /* The mode it is extended to.  */
 439   scalar_int_mode extend_mode;
 440
 441   /* The mode the variable iterates in.  */
 442   scalar_int_mode mode;
 443
 444   /* Whether the first iteration needs to be handled specially.  */
 445   unsigned first_special : 1;
 446 };
 447
 448 /* The description of an exit from the loop and of the number of iterations
 449    till we take the exit.  */
 450
 451 struct GTY(()) niter_desc
 452 {
 453   /* The edge out of the loop.  */
 454   edge out_edge;
 455
 456   /* The other edge leading from the condition.  */
 457   edge in_edge;
 458
 459   /* True if we are able to say anything about number of iterations of the
 460      loop.  */
 461   bool simple_p;
 462
 463   /* True if the loop iterates the constant number of times.  */
 464   bool const_iter;
 465
 466   /* Number of iterations if constant.  */
 467   uint64_t niter;
 468
 469   /* Assumptions under that the rest of the information is valid.  */
 470   rtx assumptions;
 471
 472   /* Assumptions under that the loop ends before reaching the latch,
 473      even if value of niter_expr says otherwise.  */
 474   rtx noloop_assumptions;
 475
 476   /* Condition under that the loop is infinite.  */
 477   rtx infinite;
 478
 479   /* Whether the comparison is signed.  */
 480   bool signed_p;
 481
 482   /* The mode in that niter_expr should be computed.  */
 483   scalar_int_mode mode;
 484
 485   /* The number of iterations of the loop.  */
 486   rtx niter_expr;
 487 };
 488
 489 extern void iv_analysis_loop_init (struct loop *);
 490 extern bool iv_analyze (rtx_insn *, scalar_int_mode, rtx, struct rtx_iv *);
 491 extern bool iv_analyze_result (rtx_insn *, rtx, struct rtx_iv *);
 492 extern bool iv_analyze_expr (rtx_insn *, scalar_int_mode, rtx,
 493                              struct rtx_iv *);
 494 extern rtx get_iv_value (struct rtx_iv *, rtx);
 495 extern bool biv_p (rtx_insn *, scalar_int_mode, rtx);
 496 extern void find_simple_exit (struct loop *, struct niter_desc *);
 497 extern void iv_analysis_done (void);
 498
 499 extern struct niter_desc *get_simple_loop_desc (struct loop *loop);
 500 extern void free_simple_loop_desc (struct loop *loop);
 501
 502 static inline struct niter_desc *
 503 simple_loop_desc (struct loop *loop)
 504 {
 505   return loop->simple_loop_desc;
 506 }
 507
 508 /* Accessors for the loop structures.  */
 509
 510 /* Returns the loop with index NUM from FNs loop tree.  */
 511
 512 static inline struct loop *
 513 get_loop (struct function *fn, unsigned num)
 514 {
 515   return (*loops_for_fn (fn)->larray)[num];
 516 }
 517
 518 /* Returns the number of superloops of LOOP.  */
 519
 520 static inline unsigned
 521 loop_depth (const struct loop *loop)
 522 {
 523   return vec_safe_length (loop->superloops);
 524 }
 525
 526 /* Returns the immediate superloop of LOOP, or NULL if LOOP is the outermost
 527    loop.  */
 528
 529 static inline struct loop *
 530 loop_outer (const struct loop *loop)
 531 {
 532   unsigned n = vec_safe_length (loop->superloops);
 533
 534   if (n == 0)
 535     return NULL;
 536
 537   return (*loop->superloops)[n - 1];
 538 }
 539
 540 /* Returns true if LOOP has at least one exit edge.  */
 541
 542 static inline bool
 543 loop_has_exit_edges (const struct loop *loop)
 544 {
 545   return loop->exits->next->e != NULL;
 546 }
 547
 548 /* Returns the list of loops in FN.  */
 549
 550 inline vec<loop_p, va_gc> *
 551 get_loops (struct function *fn)
 552 {
 553   struct loops *loops = loops_for_fn (fn);
 554   if (!loops)
 555     return NULL;
 556
 557   return loops->larray;
 558 }
 559
 560 /* Returns the number of loops in FN (including the removed
 561    ones and the fake loop that forms the root of the loop tree).  */
 562
 563 static inline unsigned
 564 number_of_loops (struct function *fn)
 565 {
 566   struct loops *loops = loops_for_fn (fn);
 567   if (!loops)
 568     return 0;
 569
 570   return vec_safe_length (loops->larray);
 571 }
 572
 573 /* Returns true if state of the loops satisfies all properties
 574    described by FLAGS.  */
 575
 576 static inline bool
 577 loops_state_satisfies_p (function *fn, unsigned flags)
 578 {
 579   return (loops_for_fn (fn)->state & flags) == flags;
 580 }
 581
 582 static inline bool
 583 loops_state_satisfies_p (unsigned flags)
 584 {
 585   return loops_state_satisfies_p (cfun, flags);
 586 }
 587
 588 /* Sets FLAGS to the loops state.  */
 589
 590 static inline void
 591 loops_state_set (function *fn, unsigned flags)
 592 {
 593   loops_for_fn (fn)->state |= flags;
 594 }
 595
 596 static inline void
 597 loops_state_set (unsigned flags)
 598 {
 599   loops_state_set (cfun, flags);
 600 }
 601
 602 /* Clears FLAGS from the loops state.  */
 603
 604 static inline void
 605 loops_state_clear (function *fn, unsigned flags)
 606 {
 607   loops_for_fn (fn)->state &= ~flags;
 608 }
 609
 610 static inline void
 611 loops_state_clear (unsigned flags)
 612 {
 613   if (!current_loops)
 614     return;
 615   loops_state_clear (cfun, flags);
 616 }
 617
 618 /* Check loop structure invariants, if internal consistency checks are
 619    enabled.  */
 620
 621 static inline void
 622 checking_verify_loop_structure (void)
 623 {
 624   /* VERIFY_LOOP_STRUCTURE essentially asserts that no loops need fixups.
 625
 626      The loop optimizers should never make changes to the CFG which
 627      require loop fixups.  But the low level CFG manipulation code may
 628      set the flag conservatively.
 629
 630      Go ahead and clear the flag here.  That avoids the assert inside
 631      VERIFY_LOOP_STRUCTURE, and if there is an inconsistency in the loop
 632      structures VERIFY_LOOP_STRUCTURE will detect it.
 633
 634      This also avoid the compile time cost of excessive fixups.  */
 635   loops_state_clear (LOOPS_NEED_FIXUP);
 636   if (flag_checking)
 637     verify_loop_structure ();
 638 }
 639
 640 /* Loop iterators.  */
 641
 642 /* Flags for loop iteration.  */
 643
 644 enum li_flags
 645 {
 646   LI_INCLUDE_ROOT = 1,          /* Include the fake root of the loop tree.  */
 647   LI_FROM_INNERMOST = 2,        /* Iterate over the loops in the reverse order,
 648                                    starting from innermost ones.  */
 649   LI_ONLY_INNERMOST = 4         /* Iterate only over innermost loops.  */
 650 };
 651
 652 /* The iterator for loops.  */
 653
 654 struct loop_iterator
 655 {
 656   loop_iterator (function *fn, loop_p *loop, unsigned flags);
 657   ~loop_iterator ();
 658
 659   inline loop_p next ();
 660
 661   /* The function we are visiting.  */
 662   function *fn;
 663
 664   /* The list of loops to visit.  */
 665   vec<int> to_visit;
 666
 667   /* The index of the actual loop.  */
 668   unsigned idx;
 669 };
 670
 671 inline loop_p
 672 loop_iterator::next ()
 673 {
 674   int anum;
 675
 676   while (this->to_visit.iterate (this->idx, &anum))
 677     {
 678       this->idx++;
 679       loop_p loop = get_loop (fn, anum);
 680       if (loop)
 681         return loop;
 682     }
 683
 684   return NULL;
 685 }
 686
 687 inline
 688 loop_iterator::loop_iterator (function *fn, loop_p *loop, unsigned flags)
 689 {
 690   struct loop *aloop;
 691   unsigned i;
 692   int mn;
 693
 694   this->idx = 0;
 695   this->fn = fn;
 696   if (!loops_for_fn (fn))
 697     {
 698       this->to_visit.create (0);
 699       *loop = NULL;
 700       return;
 701     }
 702
 703   this->to_visit.create (number_of_loops (fn));
 704   mn = (flags & LI_INCLUDE_ROOT) ? 0 : 1;
 705
 706   if (flags & LI_ONLY_INNERMOST)
 707     {
 708       for (i = 0; vec_safe_iterate (loops_for_fn (fn)->larray, i, &aloop); i++)
 709         if (aloop != NULL
 710             && aloop->inner == NULL
 711             && aloop->num >= mn)
 712           this->to_visit.quick_push (aloop->num);
 713     }
 714   else if (flags & LI_FROM_INNERMOST)
 715     {
 716       /* Push the loops to LI->TO_VISIT in postorder.  */
 717       for (aloop = loops_for_fn (fn)->tree_root;
 718            aloop->inner != NULL;
 719            aloop = aloop->inner)
 720         continue;
 721
 722       while (1)
 723         {
 724           if (aloop->num >= mn)
 725             this->to_visit.quick_push (aloop->num);
 726
 727           if (aloop->next)
 728             {
 729               for (aloop = aloop->next;
 730                    aloop->inner != NULL;
 731                    aloop = aloop->inner)
 732                 continue;
 733             }
 734           else if (!loop_outer (aloop))
 735             break;
 736           else
 737             aloop = loop_outer (aloop);
 738         }
 739     }
 740   else
 741     {
 742       /* Push the loops to LI->TO_VISIT in preorder.  */
 743       aloop = loops_for_fn (fn)->tree_root;
 744       while (1)
 745         {
 746           if (aloop->num >= mn)
 747             this->to_visit.quick_push (aloop->num);
 748
 749           if (aloop->inner != NULL)
 750             aloop = aloop->inner;
 751           else
 752             {
 753               while (aloop != NULL && aloop->next == NULL)
 754                 aloop = loop_outer (aloop);
 755               if (aloop == NULL)
 756                 break;
 757               aloop = aloop->next;
 758             }
 759         }
 760     }
 761
 762   *loop = this->next ();
 763 }
 764
 765 inline
 766 loop_iterator::~loop_iterator ()
 767 {
 768   this->to_visit.release ();
 769 }
 770
 771 #define FOR_EACH_LOOP(LOOP, FLAGS) \
 772   for (loop_iterator li(cfun, &(LOOP), FLAGS); \
 773        (LOOP); \
 774        (LOOP) = li.next ())
 775
 776 #define FOR_EACH_LOOP_FN(FN, LOOP, FLAGS) \
 777   for (loop_iterator li(FN, &(LOOP), FLAGS); \
 778        (LOOP); \
 779        (LOOP) = li.next ())
 780
 781 /* The properties of the target.  */
 782 struct target_cfgloop {
 783   /* Number of available registers.  */
 784   unsigned x_target_avail_regs;
 785
 786   /* Number of available registers that are call-clobbered.  */
 787   unsigned x_target_clobbered_regs;
 788
 789   /* Number of registers reserved for temporary expressions.  */
 790   unsigned x_target_res_regs;
 791
 792   /* The cost for register when there still is some reserve, but we are
 793      approaching the number of available registers.  */
 794   unsigned x_target_reg_cost[2];
 795
 796   /* The cost for register when we need to spill.  */
 797   unsigned x_target_spill_cost[2];
 798 };
 799
 800 extern struct target_cfgloop default_target_cfgloop;
 801 #if SWITCHABLE_TARGET
 802 extern struct target_cfgloop *this_target_cfgloop;
 803 #else
 804 #define this_target_cfgloop (&default_target_cfgloop)
 805 #endif
 806
 807 #define target_avail_regs \
 808   (this_target_cfgloop->x_target_avail_regs)
 809 #define target_clobbered_regs \
 810   (this_target_cfgloop->x_target_clobbered_regs)
 811 #define target_res_regs \
 812   (this_target_cfgloop->x_target_res_regs)
 813 #define target_reg_cost \
 814   (this_target_cfgloop->x_target_reg_cost)
 815 #define target_spill_cost \
 816   (this_target_cfgloop->x_target_spill_cost)
 817
 818 /* Register pressure estimation for induction variable optimizations & loop
 819    invariant motion.  */
 820 extern unsigned estimate_reg_pressure_cost (unsigned, unsigned, bool, bool);
 821 extern void init_set_costs (void);
 822
 823 /* Loop optimizer initialization.  */
 824 extern void loop_optimizer_init (unsigned);
 825 extern void loop_optimizer_finalize (function *);
 826 inline void
 827 loop_optimizer_finalize ()
 828 {
 829   loop_optimizer_finalize (cfun);
 830 }
 831
 832 /* Optimization passes.  */
 833 enum
 834 {
 835   UAP_UNROLL = 1,       /* Enables unrolling of loops if it seems profitable.  */
 836   UAP_UNROLL_ALL = 2    /* Enables unrolling of all loops.  */
 837 };
 838
 839 extern void doloop_optimize_loops (void);
 840 extern void move_loop_invariants (void);
 841 extern vec<basic_block> get_loop_hot_path (const struct loop *loop);
 842
 843 /* Returns the outermost loop of the loop nest that contains LOOP.*/
 844 static inline struct loop *
 845 loop_outermost (struct loop *loop)
 846 {
 847   unsigned n = vec_safe_length (loop->superloops);
 848
 849   if (n <= 1)
 850     return loop;
 851
 852   return (*loop->superloops)[1];
 853 }
 854
 855 extern void record_niter_bound (struct loop *, const widest_int &, bool, bool);
 856 extern HOST_WIDE_INT get_estimated_loop_iterations_int (struct loop *);
 857 extern HOST_WIDE_INT get_max_loop_iterations_int (const struct loop *);
 858 extern HOST_WIDE_INT get_likely_max_loop_iterations_int (struct loop *);
 859 extern bool get_estimated_loop_iterations (struct loop *loop, widest_int *nit);
 860 extern bool get_max_loop_iterations (const struct loop *loop, widest_int *nit);
 861 extern bool get_likely_max_loop_iterations (struct loop *loop, widest_int *nit);
 862 extern int bb_loop_depth (const_basic_block);
 863
 864 /* Converts VAL to widest_int.  */
 865
 866 static inline widest_int
 867 gcov_type_to_wide_int (gcov_type val)
 868 {
 869   HOST_WIDE_INT a[2];
 870
 871   a[0] = (unsigned HOST_WIDE_INT) val;
 872   /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
 873      the size of type.  */
 874   val >>= HOST_BITS_PER_WIDE_INT - 1;
 875   val >>= 1;
 876   a[1] = (unsigned HOST_WIDE_INT) val;
 877
 878   return widest_int::from_array (a, 2);
 879 }
 880 #endif /* GCC_CFGLOOP_H */