LCOV - code coverage report
Current view: top level - gcc - cfgloop.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 110 112 98.2 %
Date: 2020-03-28 11:57:23 Functions: 3 3 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

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

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.