LCOV - code coverage report
Current view: top level - gcc - tree-scalar-evolution.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 92.8 % 1574 1460
Test Date: 2026-11-14 16:39:50 Functions: 95.5 % 67 64
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Scalar evolution detector.
       2              :    Copyright (C) 2003-2026 Free Software Foundation, Inc.
       3              :    Contributed by Sebastian Pop <s.pop@laposte.net>
       4              : 
       5              : This file is part of GCC.
       6              : 
       7              : GCC is free software; you can redistribute it and/or modify it under
       8              : the terms of the GNU General Public License as published by the Free
       9              : Software Foundation; either version 3, or (at your option) any later
      10              : version.
      11              : 
      12              : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      13              : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      14              : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      15              : for more details.
      16              : 
      17              : You should have received a copy of the GNU General Public License
      18              : along with GCC; see the file COPYING3.  If not see
      19              : <http://www.gnu.org/licenses/>.  */
      20              : 
      21              : /*
      22              :    Description:
      23              : 
      24              :    This pass analyzes the evolution of scalar variables in loop
      25              :    structures.  The algorithm is based on the SSA representation,
      26              :    and on the loop hierarchy tree.  This algorithm is not based on
      27              :    the notion of versions of a variable, as it was the case for the
      28              :    previous implementations of the scalar evolution algorithm, but
      29              :    it assumes that each defined name is unique.
      30              : 
      31              :    The notation used in this file is called "chains of recurrences",
      32              :    and has been proposed by Eugene Zima, Robert Van Engelen, and
      33              :    others for describing induction variables in programs.  For example
      34              :    "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
      35              :    when entering in the loop_1 and has a step 2 in this loop, in other
      36              :    words "for (b = 0; b < N; b+=2);".  Note that the coefficients of
      37              :    this chain of recurrence (or chrec [shrek]) can contain the name of
      38              :    other variables, in which case they are called parametric chrecs.
      39              :    For example, "b -> {a, +, 2}_1" means that the initial value of "b"
      40              :    is the value of "a".  In most of the cases these parametric chrecs
      41              :    are fully instantiated before their use because symbolic names can
      42              :    hide some difficult cases such as self-references described later
      43              :    (see the Fibonacci example).
      44              : 
      45              :    A short sketch of the algorithm is:
      46              : 
      47              :    Given a scalar variable to be analyzed, follow the SSA edge to
      48              :    its definition:
      49              : 
      50              :    - When the definition is a GIMPLE_ASSIGN: if the right hand side
      51              :    (RHS) of the definition cannot be statically analyzed, the answer
      52              :    of the analyzer is: "don't know".
      53              :    Otherwise, for all the variables that are not yet analyzed in the
      54              :    RHS, try to determine their evolution, and finally try to
      55              :    evaluate the operation of the RHS that gives the evolution
      56              :    function of the analyzed variable.
      57              : 
      58              :    - When the definition is a condition-phi-node: determine the
      59              :    evolution function for all the branches of the phi node, and
      60              :    finally merge these evolutions (see chrec_merge).
      61              : 
      62              :    - When the definition is a loop-phi-node: determine its initial
      63              :    condition, that is the SSA edge defined in an outer loop, and
      64              :    keep it symbolic.  Then determine the SSA edges that are defined
      65              :    in the body of the loop.  Follow the inner edges until ending on
      66              :    another loop-phi-node of the same analyzed loop.  If the reached
      67              :    loop-phi-node is not the starting loop-phi-node, then we keep
      68              :    this definition under a symbolic form.  If the reached
      69              :    loop-phi-node is the same as the starting one, then we compute a
      70              :    symbolic stride on the return path.  The result is then the
      71              :    symbolic chrec {initial_condition, +, symbolic_stride}_loop.
      72              : 
      73              :    Examples:
      74              : 
      75              :    Example 1: Illustration of the basic algorithm.
      76              : 
      77              :    | a = 3
      78              :    | loop_1
      79              :    |   b = phi (a, c)
      80              :    |   c = b + 1
      81              :    |   if (c > 10) exit_loop
      82              :    | endloop
      83              : 
      84              :    Suppose that we want to know the number of iterations of the
      85              :    loop_1.  The exit_loop is controlled by a COND_EXPR (c > 10).  We
      86              :    ask the scalar evolution analyzer two questions: what's the
      87              :    scalar evolution (scev) of "c", and what's the scev of "10".  For
      88              :    "10" the answer is "10" since it is a scalar constant.  For the
      89              :    scalar variable "c", it follows the SSA edge to its definition,
      90              :    "c = b + 1", and then asks again what's the scev of "b".
      91              :    Following the SSA edge, we end on a loop-phi-node "b = phi (a,
      92              :    c)", where the initial condition is "a", and the inner loop edge
      93              :    is "c".  The initial condition is kept under a symbolic form (it
      94              :    may be the case that the copy constant propagation has done its
      95              :    work and we end with the constant "3" as one of the edges of the
      96              :    loop-phi-node).  The update edge is followed to the end of the
      97              :    loop, and until reaching again the starting loop-phi-node: b -> c
      98              :    -> b.  At this point we have drawn a path from "b" to "b" from
      99              :    which we compute the stride in the loop: in this example it is
     100              :    "+1".  The resulting scev for "b" is "b -> {a, +, 1}_1".  Now
     101              :    that the scev for "b" is known, it is possible to compute the
     102              :    scev for "c", that is "c -> {a + 1, +, 1}_1".  In order to
     103              :    determine the number of iterations in the loop_1, we have to
     104              :    instantiate_parameters (loop_1, {a + 1, +, 1}_1), that gives after some
     105              :    more analysis the scev {4, +, 1}_1, or in other words, this is
     106              :    the function "f (x) = x + 4", where x is the iteration count of
     107              :    the loop_1.  Now we have to solve the inequality "x + 4 > 10",
     108              :    and take the smallest iteration number for which the loop is
     109              :    exited: x = 7.  This loop runs from x = 0 to x = 7, and in total
     110              :    there are 8 iterations.  In terms of loop normalization, we have
     111              :    created a variable that is implicitly defined, "x" or just "_1",
     112              :    and all the other analyzed scalars of the loop are defined in
     113              :    function of this variable:
     114              : 
     115              :    a -> 3
     116              :    b -> {3, +, 1}_1
     117              :    c -> {4, +, 1}_1
     118              : 
     119              :    or in terms of a C program:
     120              : 
     121              :    | a = 3
     122              :    | for (x = 0; x <= 7; x++)
     123              :    |   {
     124              :    |     b = x + 3
     125              :    |     c = x + 4
     126              :    |   }
     127              : 
     128              :    Example 2a: Illustration of the algorithm on nested loops.
     129              : 
     130              :    | loop_1
     131              :    |   a = phi (1, b)
     132              :    |   c = a + 2
     133              :    |   loop_2  10 times
     134              :    |     b = phi (c, d)
     135              :    |     d = b + 3
     136              :    |   endloop
     137              :    | endloop
     138              : 
     139              :    For analyzing the scalar evolution of "a", the algorithm follows
     140              :    the SSA edge into the loop's body: "a -> b".  "b" is an inner
     141              :    loop-phi-node, and its analysis as in Example 1, gives:
     142              : 
     143              :    b -> {c, +, 3}_2
     144              :    d -> {c + 3, +, 3}_2
     145              : 
     146              :    Following the SSA edge for the initial condition, we end on "c = a
     147              :    + 2", and then on the starting loop-phi-node "a".  From this point,
     148              :    the loop stride is computed: back on "c = a + 2" we get a "+2" in
     149              :    the loop_1, then on the loop-phi-node "b" we compute the overall
     150              :    effect of the inner loop that is "b = c + 30", and we get a "+30"
     151              :    in the loop_1.  That means that the overall stride in loop_1 is
     152              :    equal to "+32", and the result is:
     153              : 
     154              :    a -> {1, +, 32}_1
     155              :    c -> {3, +, 32}_1
     156              : 
     157              :    Example 2b: Multivariate chains of recurrences.
     158              : 
     159              :    | loop_1
     160              :    |   k = phi (0, k + 1)
     161              :    |   loop_2  4 times
     162              :    |     j = phi (0, j + 1)
     163              :    |     loop_3 4 times
     164              :    |       i = phi (0, i + 1)
     165              :    |       A[j + k] = ...
     166              :    |     endloop
     167              :    |   endloop
     168              :    | endloop
     169              : 
     170              :    Analyzing the access function of array A with
     171              :    instantiate_parameters (loop_1, "j + k"), we obtain the
     172              :    instantiation and the analysis of the scalar variables "j" and "k"
     173              :    in loop_1.  This leads to the scalar evolution {4, +, 1}_1: the end
     174              :    value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is
     175              :    {0, +, 1}_1.  To obtain the evolution function in loop_3 and
     176              :    instantiate the scalar variables up to loop_1, one has to use:
     177              :    instantiate_scev (block_before_loop (loop_1), loop_3, "j + k").
     178              :    The result of this call is {{0, +, 1}_1, +, 1}_2.
     179              : 
     180              :    Example 3: Higher degree polynomials.
     181              : 
     182              :    | loop_1
     183              :    |   a = phi (2, b)
     184              :    |   c = phi (5, d)
     185              :    |   b = a + 1
     186              :    |   d = c + a
     187              :    | endloop
     188              : 
     189              :    a -> {2, +, 1}_1
     190              :    b -> {3, +, 1}_1
     191              :    c -> {5, +, a}_1
     192              :    d -> {5 + a, +, a}_1
     193              : 
     194              :    instantiate_parameters (loop_1, {5, +, a}_1) -> {5, +, 2, +, 1}_1
     195              :    instantiate_parameters (loop_1, {5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
     196              : 
     197              :    Example 4: Lucas, Fibonacci, or mixers in general.
     198              : 
     199              :    | loop_1
     200              :    |   a = phi (1, b)
     201              :    |   c = phi (3, d)
     202              :    |   b = c
     203              :    |   d = c + a
     204              :    | endloop
     205              : 
     206              :    a -> (1, c)_1
     207              :    c -> {3, +, a}_1
     208              : 
     209              :    The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
     210              :    following semantics: during the first iteration of the loop_1, the
     211              :    variable contains the value 1, and then it contains the value "c".
     212              :    Note that this syntax is close to the syntax of the loop-phi-node:
     213              :    "a -> (1, c)_1" vs. "a = phi (1, c)".
     214              : 
     215              :    The symbolic chrec representation contains all the semantics of the
     216              :    original code.  What is more difficult is to use this information.
     217              : 
     218              :    Example 5: Flip-flops, or exchangers.
     219              : 
     220              :    | loop_1
     221              :    |   a = phi (1, b)
     222              :    |   c = phi (3, d)
     223              :    |   b = c
     224              :    |   d = a
     225              :    | endloop
     226              : 
     227              :    a -> (1, c)_1
     228              :    c -> (3, a)_1
     229              : 
     230              :    Based on these symbolic chrecs, it is possible to refine this
     231              :    information into the more precise PERIODIC_CHRECs:
     232              : 
     233              :    a -> |1, 3|_1
     234              :    c -> |3, 1|_1
     235              : 
     236              :    This transformation is not yet implemented.
     237              : 
     238              :    Further readings:
     239              : 
     240              :    You can find a more detailed description of the algorithm in:
     241              :    http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
     242              :    http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz.  But note that
     243              :    this is a preliminary report and some of the details of the
     244              :    algorithm have changed.  I'm working on a research report that
     245              :    updates the description of the algorithms to reflect the design
     246              :    choices used in this implementation.
     247              : 
     248              :    A set of slides show a high level overview of the algorithm and run
     249              :    an example through the scalar evolution analyzer:
     250              :    http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
     251              : 
     252              :    The slides that I have presented at the GCC Summit'04 are available
     253              :    at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
     254              : */
     255              : 
     256              : #include "config.h"
     257              : #include "system.h"
     258              : #include "coretypes.h"
     259              : #include "backend.h"
     260              : #include "target.h"
     261              : #include "rtl.h"
     262              : #include "optabs-query.h"
     263              : #include "tree.h"
     264              : #include "gimple.h"
     265              : #include "ssa.h"
     266              : #include "gimple-pretty-print.h"
     267              : #include "fold-const.h"
     268              : #include "gimplify.h"
     269              : #include "gimple-iterator.h"
     270              : #include "gimplify-me.h"
     271              : #include "tree-cfg.h"
     272              : #include "tree-ssa-loop-ivopts.h"
     273              : #include "tree-ssa-loop-manip.h"
     274              : #include "tree-ssa-loop-niter.h"
     275              : #include "tree-ssa-loop.h"
     276              : #include "tree-ssa.h"
     277              : #include "cfgloop.h"
     278              : #include "tree-chrec.h"
     279              : #include "tree-affine.h"
     280              : #include "tree-scalar-evolution.h"
     281              : #include "dumpfile.h"
     282              : #include "tree-ssa-propagate.h"
     283              : #include "gimple-fold.h"
     284              : #include "tree-into-ssa.h"
     285              : #include "builtins.h"
     286              : #include "case-cfn-macros.h"
     287              : #include "tree-eh.h"
     288              : 
     289              : static tree analyze_scalar_evolution_1 (class loop *, tree, tree * = nullptr);
     290              : static tree analyze_scalar_evolution_for_address_of (class loop *loop,
     291              :                                                      tree var,
     292              :                                                      tree * = nullptr);
     293              : 
     294              : /* The cached information about an SSA name with version NAME_VERSION,
     295              :    claiming that below basic block with index INSTANTIATED_BELOW, the
     296              :    value of the SSA name can be expressed as CHREC.
     297              :    NOWRAP_BOUND can store an assumption to guarantee that the SSA name
     298              :    doesn't wrap.  */
     299              : 
     300              : struct GTY((for_user)) scev_info_str {
     301              :   unsigned int name_version;
     302              :   int instantiated_below;
     303              :   tree chrec;
     304              :   tree nowrap_bound;
     305              : };
     306              : 
     307              : /* Counters for the scev database.  */
     308              : static unsigned nb_set_scev = 0;
     309              : static unsigned nb_get_scev = 0;
     310              : 
     311              : struct scev_info_hasher : ggc_ptr_hash<scev_info_str>
     312              : {
     313              :   static hashval_t hash (scev_info_str *i);
     314              :   static bool equal (const scev_info_str *a, const scev_info_str *b);
     315              : };
     316              : 
     317              : /* Keep regular hash entries and entries that have nowrap assumptions separate
     318              :    by using two hash tables.  */
     319              : static GTY (()) hash_table<scev_info_hasher> *scalar_evolution_info;
     320              : static GTY (()) hash_table<scev_info_hasher> *scalar_evolution_nowrap_info;
     321              : 
     322              : 
     323              : /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW.  */
     324              : 
     325              : static inline struct scev_info_str *
     326     55700262 : new_scev_info_str (basic_block instantiated_below, tree var)
     327              : {
     328     55700262 :   struct scev_info_str *res;
     329              : 
     330     55700262 :   res = ggc_alloc<scev_info_str> ();
     331     55700262 :   res->name_version = SSA_NAME_VERSION (var);
     332     55700262 :   res->instantiated_below = instantiated_below->index;
     333     55700262 :   res->chrec = chrec_not_analyzed_yet;
     334     55700262 :   res->nowrap_bound = NULL_TREE;
     335              : 
     336     55700262 :   return res;
     337              : }
     338              : 
     339              : /* Computes a hash function for database element ELT.  */
     340              : 
     341              : hashval_t
     342   1112579931 : scev_info_hasher::hash (scev_info_str *elt)
     343              : {
     344   1112579931 :   return (elt->name_version ^ elt->instantiated_below);
     345              : }
     346              : 
     347              : /* Compares database elements E1 and E2.  */
     348              : 
     349              : bool
     350   1104143796 : scev_info_hasher::equal (const scev_info_str *elt1, const scev_info_str *elt2)
     351              : {
     352   1104143796 :   return (elt1->name_version == elt2->name_version
     353   1104143796 :           && elt1->instantiated_below == elt2->instantiated_below);
     354              : }
     355              : 
     356              : /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
     357              :    A first query on VAR returns chrec_not_analyzed_yet.  */
     358              : 
     359              : static scev_info_str *
     360    215442836 : find_var_scev_info (basic_block instantiated_below, tree var,
     361              :                     bool nowrap_assumption_p)
     362              : {
     363    215442836 :   struct scev_info_str tmp;
     364              : 
     365    215442836 :   tmp.name_version = SSA_NAME_VERSION (var);
     366    215442836 :   tmp.instantiated_below = instantiated_below->index;
     367    215442836 :   scev_info_str **slot;
     368    215442836 :   if (!nowrap_assumption_p)
     369    212812054 :     slot = scalar_evolution_info->find_slot (&tmp, INSERT);
     370              :   else
     371      2630782 :     slot = scalar_evolution_nowrap_info->find_slot (&tmp, INSERT);
     372              : 
     373    215442836 :   if (!*slot)
     374     55700262 :     *slot = new_scev_info_str (instantiated_below, var);
     375              : 
     376    215442836 :   return *slot;
     377              : }
     378              : 
     379              : 
     380              : /* Hashtable helpers for a temporary hash-table used when
     381              :    analyzing a scalar evolution, instantiating a CHREC or
     382              :    resolving mixers.  */
     383              : 
     384              : class instantiate_cache_type
     385              : {
     386              : public:
     387              :   htab_t map;
     388              :   vec<scev_info_str> entries;
     389              : 
     390    134523619 :   instantiate_cache_type () : map (NULL), entries (vNULL) {}
     391              :   ~instantiate_cache_type ();
     392    131303860 :   tree get (unsigned slot) { return entries[slot].chrec; }
     393    101598034 :   void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; }
     394              : };
     395              : 
     396    134523619 : instantiate_cache_type::~instantiate_cache_type ()
     397              : {
     398    134523619 :   if (map != NULL)
     399              :     {
     400     29817701 :       htab_delete (map);
     401     29817701 :       entries.release ();
     402              :     }
     403    134523619 : }
     404              : 
     405              : /* Cache to avoid infinite recursion when instantiating an SSA name.
     406              :    Live during the outermost analyze_scalar_evolution, instantiate_scev
     407              :    or resolve_mixers call.  */
     408              : static instantiate_cache_type *global_cache;
     409              : 
     410              : /* Build a combined bound from BASE and BOUND by taking the minimum
     411              :    of both.  The result is stored in BASE.  */
     412              : 
     413              : void
     414     81314516 : scev_combine_nowrap_bounds (tree *base, tree bound)
     415              : {
     416     81314516 :   if (!base || !bound)
     417              :     return;
     418        34441 :   if (!*base)
     419              :     {
     420        26098 :       *base = bound;
     421        26098 :       return;
     422              :     }
     423              : 
     424         8343 :   tree t1 = TREE_TYPE (*base);
     425         8343 :   tree t2 = TREE_TYPE (bound);
     426              : 
     427              :   /* We should always be getting unsigned types from
     428              :      get_niter_type_bound.  */
     429         8343 :   gcc_assert (TYPE_UNSIGNED (t1) && TYPE_UNSIGNED (t2));
     430              : 
     431         8343 :   tree wide_type = TYPE_PRECISION (t1) >= TYPE_PRECISION (t2) ? t1 : t2;
     432         8343 :   *base = fold_build2 (MIN_EXPR, wide_type,
     433              :                        fold_convert (wide_type, *base),
     434              :                        fold_convert (wide_type, bound));
     435              : }
     436              : 
     437              : /* Return true when PHI is a loop-phi-node.  */
     438              : 
     439              : static bool
     440     27984972 : loop_phi_node_p (gimple *phi)
     441              : {
     442              :   /* The implementation of this function is based on the following
     443              :      property: "all the loop-phi-nodes of a loop are contained in the
     444              :      loop's header basic block".  */
     445              : 
     446            0 :   return loop_containing_stmt (phi)->header == gimple_bb (phi);
     447              : }
     448              : 
     449              : /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
     450              :    In general, in the case of multivariate evolutions we want to get
     451              :    the evolution in different loops.  LOOP specifies the level for
     452              :    which to get the evolution.
     453              : 
     454              :    Example:
     455              : 
     456              :    | for (j = 0; j < 100; j++)
     457              :    |   {
     458              :    |     for (k = 0; k < 100; k++)
     459              :    |       {
     460              :    |         i = k + j;   - Here the value of i is a function of j, k.
     461              :    |       }
     462              :    |      ... = i         - Here the value of i is a function of j.
     463              :    |   }
     464              :    | ... = i              - Here the value of i is a scalar.
     465              : 
     466              :    Example:
     467              : 
     468              :    | i_0 = ...
     469              :    | loop_1 10 times
     470              :    |   i_1 = phi (i_0, i_2)
     471              :    |   i_2 = i_1 + 2
     472              :    | endloop
     473              : 
     474              :    This loop has the same effect as:
     475              :    LOOP_1 has the same effect as:
     476              : 
     477              :    | i_1 = i_0 + 20
     478              : 
     479              :    The overall effect of the loop, "i_0 + 20" in the previous example,
     480              :    is obtained by passing in the parameters: LOOP = 1,
     481              :    EVOLUTION_FN = {i_0, +, 2}_1.
     482              : */
     483              : 
     484              : tree
     485      6089932 : compute_overall_effect_of_inner_loop (class loop *loop, tree evolution_fn)
     486              : {
     487      7011091 :   bool val = false;
     488              : 
     489      7011091 :   if (evolution_fn == chrec_dont_know)
     490              :     return chrec_dont_know;
     491              : 
     492      6874696 :   else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
     493              :     {
     494      2540089 :       class loop *inner_loop = get_chrec_loop (evolution_fn);
     495              : 
     496      2540089 :       if (inner_loop == loop
     497      2540089 :           || flow_loop_nested_p (loop, inner_loop))
     498              :         {
     499      2540089 :           tree nb_iter = number_of_latch_executions (inner_loop);
     500              : 
     501      2540089 :           if (nb_iter == chrec_dont_know)
     502              :             return chrec_dont_know;
     503              :           else
     504              :             {
     505       921159 :               tree res;
     506              : 
     507              :               /* evolution_fn is the evolution function in LOOP.  Get
     508              :                  its value in the nb_iter-th iteration.  */
     509       921159 :               res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
     510              : 
     511       921159 :               if (chrec_contains_symbols_defined_in_loop (res, loop->num))
     512        61422 :                 res = instantiate_parameters (loop, res);
     513              : 
     514              :               /* Continue the computation until ending on a parent of LOOP.  */
     515       921159 :               return compute_overall_effect_of_inner_loop (loop, res);
     516              :             }
     517              :         }
     518              :       else
     519              :         return evolution_fn;
     520              :      }
     521              : 
     522              :   /* If the evolution function is an invariant, there is nothing to do.  */
     523      4334607 :   else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
     524              :     return evolution_fn;
     525              : 
     526              :   else
     527      3544333 :     return chrec_dont_know;
     528              : }
     529              : 
     530              : /* Associate CHREC to SCALAR.  */
     531              : 
     532              : static void
     533     53008887 : set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec,
     534              :                       tree *nowrap_bound)
     535              : {
     536     53008887 :   scev_info_str *scalar_info;
     537              : 
     538     53008887 :   if (TREE_CODE (scalar) != SSA_NAME)
     539              :     return;
     540              : 
     541     53008887 :   scalar_info = find_var_scev_info (instantiated_below, scalar,
     542              :                                     nowrap_bound != nullptr);
     543              : 
     544     53008887 :   if (dump_file)
     545              :     {
     546       129970 :       if (dump_flags & TDF_SCEV)
     547              :         {
     548           11 :           fprintf (dump_file, "(set_scalar_evolution \n");
     549           11 :           fprintf (dump_file, "  instantiated_below = %d \n",
     550              :                    instantiated_below->index);
     551           11 :           fprintf (dump_file, "  (scalar = ");
     552           11 :           print_generic_expr (dump_file, scalar);
     553           11 :           fprintf (dump_file, ")\n  (scalar_evolution = ");
     554           11 :           print_generic_expr (dump_file, chrec);
     555           11 :           fprintf (dump_file, "))\n");
     556              :         }
     557       129970 :       if (dump_flags & TDF_STATS)
     558         7200 :         nb_set_scev++;
     559              :     }
     560              : 
     561     53008887 :   scalar_info->chrec = chrec;
     562     53008887 :   if (nowrap_bound)
     563       748983 :     scalar_info->nowrap_bound = *nowrap_bound;
     564              : }
     565              : 
     566              : /* Retrieve the chrec associated to SCALAR instantiated below
     567              :    INSTANTIATED_BELOW block.  */
     568              : 
     569              : static tree
     570    202546230 : get_scalar_evolution (basic_block instantiated_below, tree scalar,
     571              :                       tree *nowrap_bound)
     572              : {
     573    202546230 :   tree res;
     574              : 
     575    202546230 :   if (dump_file)
     576              :     {
     577       780745 :       if (dump_flags & TDF_SCEV)
     578              :         {
     579           38 :           fprintf (dump_file, "(get_scalar_evolution \n");
     580           38 :           fprintf (dump_file, "  (scalar = ");
     581           38 :           print_generic_expr (dump_file, scalar);
     582           38 :           fprintf (dump_file, ")\n");
     583              :         }
     584       780745 :       if (dump_flags & TDF_STATS)
     585        51048 :         nb_get_scev++;
     586              :     }
     587              : 
     588    202546230 :   if (VECTOR_TYPE_P (TREE_TYPE (scalar))
     589    202546230 :       || TREE_CODE (TREE_TYPE (scalar)) == COMPLEX_TYPE)
     590              :     /* For chrec_dont_know we keep the symbolic form.  */
     591              :     res = scalar;
     592              :   else
     593    202232515 :     switch (TREE_CODE (scalar))
     594              :       {
     595    164661929 :       case SSA_NAME:
     596    164661929 :         if (SSA_NAME_IS_DEFAULT_DEF (scalar))
     597              :           res = scalar;
     598              :         else
     599              :           {
     600    162433949 :             scev_info_str *info
     601    162433949 :               = find_var_scev_info (instantiated_below, scalar,
     602              :                                     nowrap_bound != nullptr);
     603    162433949 :             res = info->chrec;
     604    162433949 :             if (info->nowrap_bound
     605         6550 :                 && res != chrec_not_analyzed_yet)
     606         6550 :               scev_combine_nowrap_bounds (nowrap_bound, info->nowrap_bound);
     607              :           }
     608              :         break;
     609              : 
     610              :       case REAL_CST:
     611              :       case FIXED_CST:
     612              :       case INTEGER_CST:
     613              :         res = scalar;
     614              :         break;
     615              : 
     616              :       default:
     617    202546230 :         res = chrec_not_analyzed_yet;
     618              :         break;
     619              :       }
     620              : 
     621    202546230 :   if (dump_file && (dump_flags & TDF_SCEV))
     622              :     {
     623           38 :       fprintf (dump_file, "  (scalar_evolution = ");
     624           38 :       print_generic_expr (dump_file, res);
     625           38 :       fprintf (dump_file, "))\n");
     626              :     }
     627              : 
     628    202546230 :   return res;
     629              : }
     630              : 
     631              : 
     632              : /* Depth first search algorithm.  */
     633              : 
     634              : enum t_bool {
     635              :   t_false,
     636              :   t_true,
     637              :   t_dont_know
     638              : };
     639              : 
     640              : class scev_dfs
     641              : {
     642              : public:
     643     11584570 :   scev_dfs (class loop *loop_, gphi *phi_, tree init_cond_)
     644     11584570 :       : loop (loop_), loop_phi_node (phi_), init_cond (init_cond_) {}
     645              :   t_bool get_ev (tree *, tree);
     646              : 
     647              : private:
     648              :   t_bool follow_ssa_edge_expr (gimple *, tree, tree *, int);
     649              :   t_bool follow_ssa_edge_binary (gimple *at_stmt,
     650              :                                  tree type, tree rhs0, enum tree_code code,
     651              :                                  tree rhs1, tree *evolution_of_loop, int limit);
     652              :   t_bool follow_ssa_edge_in_condition_phi_branch (int i,
     653              :                                                   gphi *condition_phi,
     654              :                                                   tree *evolution_of_branch,
     655              :                                                   tree init_cond, int limit);
     656              :   t_bool follow_ssa_edge_in_condition_phi (gphi *condition_phi,
     657              :                                            tree *evolution_of_loop, int limit);
     658              :   t_bool follow_ssa_edge_inner_loop_phi (gphi *loop_phi_node,
     659              :                                          tree *evolution_of_loop, int limit);
     660              :   tree add_to_evolution (tree chrec_before, tree to_add, gimple *at_stmt);
     661              :   tree add_to_evolution_1 (tree chrec_before, tree to_add, gimple *at_stmt);
     662              : 
     663              :   class loop *loop;
     664              :   gphi *loop_phi_node;
     665              :   tree init_cond;
     666              : };
     667              : 
     668              : t_bool
     669     11584570 : scev_dfs::get_ev (tree *ev_fn, tree arg)
     670              : {
     671     11584570 :   *ev_fn = chrec_dont_know;
     672     11584570 :   return follow_ssa_edge_expr (loop_phi_node, arg, ev_fn, 0);
     673              : }
     674              : 
     675              : /* Helper function for add_to_evolution.  Returns the evolution
     676              :    function for an assignment of the form "a = b + c", where "a" and
     677              :    "b" are on the strongly connected component.  CHREC_BEFORE is the
     678              :    information that we already have collected up to this point.
     679              :    TO_ADD is the evolution of "c".
     680              : 
     681              :    When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
     682              :    evolution the expression TO_ADD, otherwise construct an evolution
     683              :    part for this loop.  */
     684              : 
     685              : tree
     686      9493398 : scev_dfs::add_to_evolution_1 (tree chrec_before, tree to_add, gimple *at_stmt)
     687              : {
     688      9493398 :   tree type, left, right;
     689      9493398 :   unsigned loop_nb = loop->num;
     690      9493398 :   class loop *chloop;
     691              : 
     692      9493398 :   switch (TREE_CODE (chrec_before))
     693              :     {
     694       117161 :     case POLYNOMIAL_CHREC:
     695       117161 :       chloop = get_chrec_loop (chrec_before);
     696       117161 :       if (chloop == loop
     697       117161 :           || flow_loop_nested_p (chloop, loop))
     698              :         {
     699       117161 :           unsigned var;
     700              : 
     701       117161 :           type = chrec_type (chrec_before);
     702              : 
     703              :           /* When there is no evolution part in this loop, build it.  */
     704       117161 :           if (chloop != loop)
     705              :             {
     706            0 :               var = loop_nb;
     707            0 :               left = chrec_before;
     708            0 :               right = SCALAR_FLOAT_TYPE_P (type)
     709            0 :                 ? build_real (type, dconst0)
     710            0 :                 : build_int_cst (type, 0);
     711              :             }
     712              :           else
     713              :             {
     714       117161 :               var = CHREC_VARIABLE (chrec_before);
     715       117161 :               left = CHREC_LEFT (chrec_before);
     716       117161 :               right = CHREC_RIGHT (chrec_before);
     717              :             }
     718              : 
     719       117161 :           to_add = chrec_convert (type, to_add, at_stmt);
     720       117161 :           right = chrec_convert_rhs (type, right, at_stmt);
     721       117161 :           right = chrec_fold_plus (chrec_type (right), right, to_add);
     722              :           /* When we have an evolution in a non-wrapping type and
     723              :              in the process of accumulating CHREC_RIGHT there was
     724              :              overflow this indicates in the association that happened
     725              :              in building the CHREC clearly involved UB.  Avoid this.
     726              :              In building a CHREC we basically turn (a + INCR1) + INCR2
     727              :              into a + (INCR1 + INCR2) which is not always valid.
     728              :              Note this check only catches few invalid cases.  */
     729        60781 :           if ((INTEGRAL_TYPE_P (type) && ! TYPE_OVERFLOW_WRAPS (type))
     730        34335 :               && TREE_CODE (right) == INTEGER_CST
     731       119479 :               && TREE_OVERFLOW (right))
     732            5 :             return chrec_dont_know;
     733       117156 :           return build_polynomial_chrec (var, left, right);
     734              :         }
     735              :       else
     736              :         {
     737            0 :           gcc_assert (flow_loop_nested_p (loop, chloop));
     738              : 
     739              :           /* Search the evolution in LOOP_NB.  */
     740            0 :           left = add_to_evolution_1 (CHREC_LEFT (chrec_before),
     741              :                                      to_add, at_stmt);
     742            0 :           right = CHREC_RIGHT (chrec_before);
     743            0 :           right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
     744            0 :           return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
     745            0 :                                          left, right);
     746              :         }
     747              : 
     748      9376237 :     default:
     749              :       /* These nodes do not depend on a loop.  */
     750      9376237 :       if (chrec_before == chrec_dont_know)
     751              :         return chrec_dont_know;
     752              : 
     753      9357231 :       left = chrec_before;
     754      9357231 :       right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
     755              :       /* When we add the first evolution we need to replace the symbolic
     756              :          evolution we've put in when the DFS reached the loop PHI node
     757              :          with the initial value.  There's only a limited cases of
     758              :          extra operations on top of that symbol allowed, namely
     759              :          sign-conversions we can look through.  For other cases we leave
     760              :          the symbolic initial condition which causes build_polynomial_chrec
     761              :          to return chrec_dont_know.  See PR42512, PR66375 and PR107176 for
     762              :          cases we mishandled before.  */
     763      9357231 :       STRIP_NOPS (chrec_before);
     764      9357231 :       if (chrec_before == gimple_phi_result (loop_phi_node))
     765      9356438 :         left = fold_convert (TREE_TYPE (left), init_cond);
     766      9357231 :       return build_polynomial_chrec (loop_nb, left, right);
     767              :     }
     768              : }
     769              : 
     770              : /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
     771              :    of LOOP_NB.
     772              : 
     773              :    Description (provided for completeness, for those who read code in
     774              :    a plane, and for my poor 62 bytes brain that would have forgotten
     775              :    all this in the next two or three months):
     776              : 
     777              :    The algorithm of translation of programs from the SSA representation
     778              :    into the chrecs syntax is based on a pattern matching.  After having
     779              :    reconstructed the overall tree expression for a loop, there are only
     780              :    two cases that can arise:
     781              : 
     782              :    1. a = loop-phi (init, a + expr)
     783              :    2. a = loop-phi (init, expr)
     784              : 
     785              :    where EXPR is either a scalar constant with respect to the analyzed
     786              :    loop (this is a degree 0 polynomial), or an expression containing
     787              :    other loop-phi definitions (these are higher degree polynomials).
     788              : 
     789              :    Examples:
     790              : 
     791              :    1.
     792              :    | init = ...
     793              :    | loop_1
     794              :    |   a = phi (init, a + 5)
     795              :    | endloop
     796              : 
     797              :    2.
     798              :    | inita = ...
     799              :    | initb = ...
     800              :    | loop_1
     801              :    |   a = phi (inita, 2 * b + 3)
     802              :    |   b = phi (initb, b + 1)
     803              :    | endloop
     804              : 
     805              :    For the first case, the semantics of the SSA representation is:
     806              : 
     807              :    | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
     808              : 
     809              :    that is, there is a loop index "x" that determines the scalar value
     810              :    of the variable during the loop execution.  During the first
     811              :    iteration, the value is that of the initial condition INIT, while
     812              :    during the subsequent iterations, it is the sum of the initial
     813              :    condition with the sum of all the values of EXPR from the initial
     814              :    iteration to the before last considered iteration.
     815              : 
     816              :    For the second case, the semantics of the SSA program is:
     817              : 
     818              :    | a (x) = init, if x = 0;
     819              :    |         expr (x - 1), otherwise.
     820              : 
     821              :    The second case corresponds to the PEELED_CHREC, whose syntax is
     822              :    close to the syntax of a loop-phi-node:
     823              : 
     824              :    | phi (init, expr)  vs.  (init, expr)_x
     825              : 
     826              :    The proof of the translation algorithm for the first case is a
     827              :    proof by structural induction based on the degree of EXPR.
     828              : 
     829              :    Degree 0:
     830              :    When EXPR is a constant with respect to the analyzed loop, or in
     831              :    other words when EXPR is a polynomial of degree 0, the evolution of
     832              :    the variable A in the loop is an affine function with an initial
     833              :    condition INIT, and a step EXPR.  In order to show this, we start
     834              :    from the semantics of the SSA representation:
     835              : 
     836              :    f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
     837              : 
     838              :    and since "expr (j)" is a constant with respect to "j",
     839              : 
     840              :    f (x) = init + x * expr
     841              : 
     842              :    Finally, based on the semantics of the pure sum chrecs, by
     843              :    identification we get the corresponding chrecs syntax:
     844              : 
     845              :    f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
     846              :    f (x) -> {init, +, expr}_x
     847              : 
     848              :    Higher degree:
     849              :    Suppose that EXPR is a polynomial of degree N with respect to the
     850              :    analyzed loop_x for which we have already determined that it is
     851              :    written under the chrecs syntax:
     852              : 
     853              :    | expr (x)  ->  {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
     854              : 
     855              :    We start from the semantics of the SSA program:
     856              : 
     857              :    | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
     858              :    |
     859              :    | f (x) = init + \sum_{j = 0}^{x - 1}
     860              :    |                (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
     861              :    |
     862              :    | f (x) = init + \sum_{j = 0}^{x - 1}
     863              :    |                \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
     864              :    |
     865              :    | f (x) = init + \sum_{k = 0}^{n - 1}
     866              :    |                (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
     867              :    |
     868              :    | f (x) = init + \sum_{k = 0}^{n - 1}
     869              :    |                (b_k * \binom{x}{k + 1})
     870              :    |
     871              :    | f (x) = init + b_0 * \binom{x}{1} + ...
     872              :    |              + b_{n-1} * \binom{x}{n}
     873              :    |
     874              :    | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
     875              :    |                             + b_{n-1} * \binom{x}{n}
     876              :    |
     877              : 
     878              :    And finally from the definition of the chrecs syntax, we identify:
     879              :    | f (x)  ->  {init, +, b_0, +, ..., +, b_{n-1}}_x
     880              : 
     881              :    This shows the mechanism that stands behind the add_to_evolution
     882              :    function.  An important point is that the use of symbolic
     883              :    parameters avoids the need of an analysis schedule.
     884              : 
     885              :    Example:
     886              : 
     887              :    | inita = ...
     888              :    | initb = ...
     889              :    | loop_1
     890              :    |   a = phi (inita, a + 2 + b)
     891              :    |   b = phi (initb, b + 1)
     892              :    | endloop
     893              : 
     894              :    When analyzing "a", the algorithm keeps "b" symbolically:
     895              : 
     896              :    | a  ->  {inita, +, 2 + b}_1
     897              : 
     898              :    Then, after instantiation, the analyzer ends on the evolution:
     899              : 
     900              :    | a  ->  {inita, +, 2 + initb, +, 1}_1
     901              : 
     902              : */
     903              : 
     904              : tree
     905      9493398 : scev_dfs::add_to_evolution (tree chrec_before, tree to_add, gimple *at_stmt)
     906              : {
     907      9493398 :   tree res = NULL_TREE;
     908              : 
     909      9493398 :   if (to_add == NULL_TREE)
     910              :     return chrec_before;
     911              : 
     912              :   /* TO_ADD is either a scalar, or a parameter.  TO_ADD is not
     913              :      instantiated at this point.  */
     914      9493398 :   if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
     915              :     /* This should not happen.  */
     916            0 :     return chrec_dont_know;
     917              : 
     918      9493398 :   if (dump_file && (dump_flags & TDF_SCEV))
     919              :     {
     920            1 :       fprintf (dump_file, "(add_to_evolution \n");
     921            1 :       fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
     922            1 :       fprintf (dump_file, "  (chrec_before = ");
     923            1 :       print_generic_expr (dump_file, chrec_before);
     924            1 :       fprintf (dump_file, ")\n  (to_add = ");
     925            1 :       print_generic_expr (dump_file, to_add);
     926            1 :       fprintf (dump_file, ")\n");
     927              :     }
     928              : 
     929      9493398 :   res = add_to_evolution_1 (chrec_before, to_add, at_stmt);
     930              : 
     931      9493398 :   if (dump_file && (dump_flags & TDF_SCEV))
     932              :     {
     933            1 :       fprintf (dump_file, "  (res = ");
     934            1 :       print_generic_expr (dump_file, res);
     935            1 :       fprintf (dump_file, "))\n");
     936              :     }
     937              : 
     938              :   return res;
     939              : }
     940              : 
     941              : 
     942              : /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
     943              :    Return true if the strongly connected component has been found.  */
     944              : 
     945              : t_bool
     946      1165604 : scev_dfs::follow_ssa_edge_binary (gimple *at_stmt, tree type, tree rhs0,
     947              :                                   enum tree_code code, tree rhs1,
     948              :                                   tree *evolution_of_loop, int limit)
     949              : {
     950      1165604 :   t_bool res = t_false;
     951      1165604 :   tree evol;
     952              : 
     953      1165604 :   switch (code)
     954              :     {
     955      1165604 :     case POINTER_PLUS_EXPR:
     956      1165604 :     case PLUS_EXPR:
     957      1165604 :       if (TREE_CODE (rhs0) == SSA_NAME)
     958              :         {
     959      1146445 :           if (TREE_CODE (rhs1) == SSA_NAME)
     960              :             {
     961              :               /* Match an assignment under the form:
     962              :                  "a = b + c".  */
     963              : 
     964              :               /* We want only assignments of form "name + name" contribute to
     965              :                  LIMIT, as the other cases do not necessarily contribute to
     966              :                  the complexity of the expression.  */
     967      1146445 :               limit++;
     968              : 
     969      1146445 :               evol = *evolution_of_loop;
     970      1146445 :               res = follow_ssa_edge_expr (at_stmt, rhs0, &evol, limit);
     971      1146445 :               if (res == t_true)
     972       435682 :                 *evolution_of_loop = add_to_evolution
     973       435682 :                     (chrec_convert (type, evol, at_stmt), rhs1, at_stmt);
     974       710763 :               else if (res == t_false)
     975              :                 {
     976       690437 :                   res = follow_ssa_edge_expr
     977       690437 :                     (at_stmt, rhs1, evolution_of_loop, limit);
     978       690437 :                   if (res == t_true)
     979       523488 :                     *evolution_of_loop = add_to_evolution
     980       523488 :                         (chrec_convert (type, *evolution_of_loop, at_stmt),
     981              :                          rhs0, at_stmt);
     982              :                 }
     983              :             }
     984              : 
     985              :           else
     986            0 :             gcc_unreachable ();  /* Handled in caller.  */
     987              :         }
     988              : 
     989        19159 :       else if (TREE_CODE (rhs1) == SSA_NAME)
     990              :         {
     991              :           /* Match an assignment under the form:
     992              :              "a = ... + c".  */
     993         7409 :           res = follow_ssa_edge_expr (at_stmt, rhs1, evolution_of_loop, limit);
     994         7409 :           if (res == t_true)
     995         6651 :             *evolution_of_loop = add_to_evolution
     996         6651 :                 (chrec_convert (type, *evolution_of_loop, at_stmt),
     997              :                  rhs0, at_stmt);
     998              :         }
     999              : 
    1000              :       else
    1001              :         /* Otherwise, match an assignment under the form:
    1002              :            "a = ... + ...".  */
    1003              :         /* And there is nothing to do.  */
    1004              :         res = t_false;
    1005              :       break;
    1006              : 
    1007              :     default:
    1008              :       res = t_false;
    1009              :     }
    1010              : 
    1011      1165604 :   return res;
    1012              : }
    1013              : 
    1014              : /* Checks whether the I-th argument of a PHI comes from a backedge.  */
    1015              : 
    1016              : static bool
    1017      9112317 : backedge_phi_arg_p (gphi *phi, int i)
    1018              : {
    1019      9112317 :   const_edge e = gimple_phi_arg_edge (phi, i);
    1020              : 
    1021              :   /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
    1022              :      about updating it anywhere, and this should work as well most of the
    1023              :      time.  */
    1024      9112317 :   if (e->flags & EDGE_IRREDUCIBLE_LOOP)
    1025        57633 :     return true;
    1026              : 
    1027              :   return false;
    1028              : }
    1029              : 
    1030              : /* Helper function for one branch of the condition-phi-node.  Return
    1031              :    true if the strongly connected component has been found following
    1032              :    this path.  */
    1033              : 
    1034              : t_bool
    1035      3763496 : scev_dfs::follow_ssa_edge_in_condition_phi_branch (int i,
    1036              :                                                    gphi *condition_phi,
    1037              :                                                    tree *evolution_of_branch,
    1038              :                                                    tree init_cond, int limit)
    1039              : {
    1040      3763496 :   tree branch = PHI_ARG_DEF (condition_phi, i);
    1041      3763496 :   *evolution_of_branch = chrec_dont_know;
    1042              : 
    1043              :   /* Do not follow back edges (they must belong to an irreducible loop, which
    1044              :      we really do not want to worry about).  */
    1045      3763496 :   if (backedge_phi_arg_p (condition_phi, i))
    1046              :     return t_false;
    1047              : 
    1048      3755054 :   if (TREE_CODE (branch) == SSA_NAME)
    1049              :     {
    1050      3503277 :       *evolution_of_branch = init_cond;
    1051      3503277 :       return follow_ssa_edge_expr (condition_phi, branch,
    1052      3503277 :                                    evolution_of_branch, limit);
    1053              :     }
    1054              : 
    1055              :   /* This case occurs when one of the condition branches sets
    1056              :      the variable to a constant: i.e. a phi-node like
    1057              :      "a_2 = PHI <a_7(5), 2(6)>;".
    1058              : 
    1059              :      FIXME:  This case have to be refined correctly:
    1060              :      in some cases it is possible to say something better than
    1061              :      chrec_dont_know, for example using a wrap-around notation.  */
    1062              :   return t_false;
    1063              : }
    1064              : 
    1065              : /* This function merges the branches of a condition-phi-node in a
    1066              :    loop.  */
    1067              : 
    1068              : t_bool
    1069      2372310 : scev_dfs::follow_ssa_edge_in_condition_phi (gphi *condition_phi,
    1070              :                                             tree *evolution_of_loop, int limit)
    1071              : {
    1072      2372310 :   int i, n;
    1073      2372310 :   tree init = *evolution_of_loop;
    1074      2372310 :   tree evolution_of_branch;
    1075      2372310 :   t_bool res = follow_ssa_edge_in_condition_phi_branch (0, condition_phi,
    1076              :                                                         &evolution_of_branch,
    1077              :                                                         init, limit);
    1078      2372310 :   if (res == t_false || res == t_dont_know)
    1079              :     return res;
    1080              : 
    1081      1357133 :   *evolution_of_loop = evolution_of_branch;
    1082              : 
    1083      1357133 :   n = gimple_phi_num_args (condition_phi);
    1084      1955233 :   for (i = 1; i < n; i++)
    1085              :     {
    1086              :       /* Quickly give up when the evolution of one of the branches is
    1087              :          not known.  */
    1088      1543172 :       if (*evolution_of_loop == chrec_dont_know)
    1089              :         return t_true;
    1090              : 
    1091              :       /* Increase the limit by the PHI argument number to avoid exponential
    1092              :          time and memory complexity.  */
    1093      1391186 :       res = follow_ssa_edge_in_condition_phi_branch (i, condition_phi,
    1094              :                                                      &evolution_of_branch,
    1095              :                                                      init, limit + i);
    1096      1391186 :       if (res == t_false || res == t_dont_know)
    1097              :         return res;
    1098              : 
    1099       598100 :       *evolution_of_loop = chrec_merge (*evolution_of_loop,
    1100              :                                         evolution_of_branch);
    1101              :     }
    1102              : 
    1103              :   return t_true;
    1104              : }
    1105              : 
    1106              : /* Follow an SSA edge in an inner loop.  It computes the overall
    1107              :    effect of the loop, and following the symbolic initial conditions,
    1108              :    it follows the edges in the parent loop.  The inner loop is
    1109              :    considered as a single statement.  */
    1110              : 
    1111              : t_bool
    1112       297175 : scev_dfs::follow_ssa_edge_inner_loop_phi (gphi *loop_phi_node,
    1113              :                                           tree *evolution_of_loop, int limit)
    1114              : {
    1115       297175 :   class loop *loop = loop_containing_stmt (loop_phi_node);
    1116       297175 :   tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
    1117              : 
    1118              :   /* Sometimes, the inner loop is too difficult to analyze, and the
    1119              :      result of the analysis is a symbolic parameter.  */
    1120       297175 :   if (ev == PHI_RESULT (loop_phi_node))
    1121              :     {
    1122       112972 :       t_bool res = t_false;
    1123       112972 :       int i, n = gimple_phi_num_args (loop_phi_node);
    1124              : 
    1125       165854 :       for (i = 0; i < n; i++)
    1126              :         {
    1127       156413 :           tree arg = PHI_ARG_DEF (loop_phi_node, i);
    1128       156413 :           basic_block bb;
    1129              : 
    1130              :           /* Follow the edges that exit the inner loop.  */
    1131       156413 :           bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
    1132       156413 :           if (!flow_bb_inside_loop_p (loop, bb))
    1133       112972 :             res = follow_ssa_edge_expr (loop_phi_node,
    1134              :                                         arg, evolution_of_loop, limit);
    1135       156413 :           if (res == t_true)
    1136              :             break;
    1137              :         }
    1138              : 
    1139              :       /* If the path crosses this loop-phi, give up.  */
    1140       112972 :       if (res == t_true)
    1141       103531 :         *evolution_of_loop = chrec_dont_know;
    1142              : 
    1143              :       return res;
    1144              :     }
    1145              : 
    1146              :   /* Otherwise, compute the overall effect of the inner loop.  */
    1147       184203 :   ev = compute_overall_effect_of_inner_loop (loop, ev);
    1148       184203 :   return follow_ssa_edge_expr (loop_phi_node, ev, evolution_of_loop, limit);
    1149              : }
    1150              : 
    1151              : /* Follow the ssa edge into the expression EXPR.
    1152              :    Return true if the strongly connected component has been found.  */
    1153              : 
    1154              : t_bool
    1155     26263282 : scev_dfs::follow_ssa_edge_expr (gimple *at_stmt, tree expr,
    1156              :                                 tree *evolution_of_loop, int limit)
    1157              : {
    1158     26263282 :   gphi *halting_phi = loop_phi_node;
    1159     26263282 :   enum tree_code code;
    1160     26263282 :   tree type, rhs0, rhs1 = NULL_TREE;
    1161              : 
    1162              :   /* The EXPR is one of the following cases:
    1163              :      - an SSA_NAME,
    1164              :      - an INTEGER_CST,
    1165              :      - a PLUS_EXPR,
    1166              :      - a POINTER_PLUS_EXPR,
    1167              :      - a MINUS_EXPR,
    1168              :      - other cases are not yet handled.  */
    1169              : 
    1170              :   /* For SSA_NAME look at the definition statement, handling
    1171              :      PHI nodes and otherwise expand appropriately for the expression
    1172              :      handling below.  */
    1173     26263282 :   if (TREE_CODE (expr) == SSA_NAME)
    1174              :     {
    1175     26066062 :       gimple *def = SSA_NAME_DEF_STMT (expr);
    1176              : 
    1177     26066062 :       if (gimple_nop_p (def))
    1178              :         return t_false;
    1179              : 
    1180              :       /* Give up if the path is longer than the MAX that we allow.  */
    1181     26049591 :       if (limit > param_scev_max_expr_complexity)
    1182              :         {
    1183         8416 :           *evolution_of_loop = chrec_dont_know;
    1184         8416 :           return t_dont_know;
    1185              :         }
    1186              : 
    1187     26041175 :       if (gphi *phi = dyn_cast <gphi *>(def))
    1188              :         {
    1189     26972282 :           if (!loop_phi_node_p (phi))
    1190              :             /* DEF is a condition-phi-node.  Follow the branches, and
    1191              :                record their evolutions.  Finally, merge the collected
    1192              :                information and set the approximation to the main
    1193              :                variable.  */
    1194      2372310 :             return follow_ssa_edge_in_condition_phi (phi, evolution_of_loop,
    1195      2372310 :                                                      limit);
    1196              : 
    1197              :           /* When the analyzed phi is the halting_phi, the
    1198              :              depth-first search is over: we have found a path from
    1199              :              the halting_phi to itself in the loop.  */
    1200     11113831 :           if (phi == halting_phi)
    1201              :             {
    1202     10567603 :               *evolution_of_loop = expr;
    1203     10567603 :               return t_true;
    1204              :             }
    1205              : 
    1206              :           /* Otherwise, the evolution of the HALTING_PHI depends
    1207              :              on the evolution of another loop-phi-node, i.e. the
    1208              :              evolution function is a higher degree polynomial.  */
    1209       546228 :           class loop *def_loop = loop_containing_stmt (def);
    1210       546228 :           if (def_loop == loop)
    1211              :             return t_false;
    1212              : 
    1213              :           /* Inner loop.  */
    1214       322340 :           if (flow_loop_nested_p (loop, def_loop))
    1215       297175 :             return follow_ssa_edge_inner_loop_phi (phi, evolution_of_loop,
    1216       297175 :                                                    limit + 1);
    1217              : 
    1218              :           /* Outer loop.  */
    1219              :           return t_false;
    1220              :         }
    1221              : 
    1222              :       /* At this level of abstraction, the program is just a set
    1223              :          of GIMPLE_ASSIGNs and PHI_NODEs.  In principle there is no
    1224              :          other def to be handled.  */
    1225     12555034 :       if (!is_gimple_assign (def))
    1226              :         return t_false;
    1227              : 
    1228     12439686 :       code = gimple_assign_rhs_code (def);
    1229     12439686 :       switch (get_gimple_rhs_class (code))
    1230              :         {
    1231     10767180 :         case GIMPLE_BINARY_RHS:
    1232     10767180 :           rhs0 = gimple_assign_rhs1 (def);
    1233     10767180 :           rhs1 = gimple_assign_rhs2 (def);
    1234     10767180 :           break;
    1235      1632270 :         case GIMPLE_UNARY_RHS:
    1236      1632270 :         case GIMPLE_SINGLE_RHS:
    1237      1632270 :           rhs0 = gimple_assign_rhs1 (def);
    1238      1632270 :           break;
    1239              :         default:
    1240              :           return t_false;
    1241              :         }
    1242     12399450 :       type = TREE_TYPE (gimple_assign_lhs (def));
    1243     12399450 :       at_stmt = def;
    1244              :     }
    1245              :   else
    1246              :     {
    1247       197220 :       code = TREE_CODE (expr);
    1248       197220 :       type = TREE_TYPE (expr);
    1249              :       /* Via follow_ssa_edge_inner_loop_phi we arrive here with the
    1250              :          GENERIC scalar evolution of the inner loop.  */
    1251       197220 :       switch (code)
    1252              :         {
    1253        11726 :         CASE_CONVERT:
    1254        11726 :           rhs0 = TREE_OPERAND (expr, 0);
    1255        11726 :           break;
    1256        26104 :         case POINTER_PLUS_EXPR:
    1257        26104 :         case PLUS_EXPR:
    1258        26104 :         case MINUS_EXPR:
    1259        26104 :           rhs0 = TREE_OPERAND (expr, 0);
    1260        26104 :           rhs1 = TREE_OPERAND (expr, 1);
    1261        26104 :           STRIP_USELESS_TYPE_CONVERSION (rhs0);
    1262        26104 :           STRIP_USELESS_TYPE_CONVERSION (rhs1);
    1263        26104 :           break;
    1264              :         default:
    1265              :           rhs0 = expr;
    1266              :         }
    1267              :     }
    1268              : 
    1269     12596670 :   switch (code)
    1270              :     {
    1271       369541 :     CASE_CONVERT:
    1272       369541 :       {
    1273              :         /* This assignment is under the form "a_1 = (cast) rhs.  We cannot
    1274              :            validate any precision altering conversion during the SCC
    1275              :            analysis, so don't even try.  */
    1276       369541 :         if (!tree_nop_conversion_p (type, TREE_TYPE (rhs0)))
    1277              :           return t_false;
    1278       239363 :         t_bool res = follow_ssa_edge_expr (at_stmt, rhs0,
    1279              :                                            evolution_of_loop, limit);
    1280       239363 :         if (res == t_true)
    1281        94162 :           *evolution_of_loop = chrec_convert (type, *evolution_of_loop,
    1282              :                                               at_stmt);
    1283              :         return res;
    1284              :       }
    1285              : 
    1286              :     case INTEGER_CST:
    1287              :       /* This assignment is under the form "a_1 = 7".  */
    1288              :       return t_false;
    1289              : 
    1290         2405 :     case ADDR_EXPR:
    1291         2405 :       {
    1292              :         /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR.  */
    1293         2405 :         if (TREE_CODE (TREE_OPERAND (rhs0, 0)) != MEM_REF)
    1294              :           return t_false;
    1295            0 :         tree mem = TREE_OPERAND (rhs0, 0);
    1296            0 :         rhs0 = TREE_OPERAND (mem, 0);
    1297            0 :         rhs1 = TREE_OPERAND (mem, 1);
    1298            0 :         code = POINTER_PLUS_EXPR;
    1299              :       }
    1300              :       /* Fallthru.  */
    1301      9073253 :     case POINTER_PLUS_EXPR:
    1302      9073253 :     case PLUS_EXPR:
    1303              :       /* This case is under the form "rhs0 +- rhs1".  */
    1304      9073253 :       if (TREE_CODE (rhs0) == SSA_NAME && TREE_CODE (rhs1) != SSA_NAME)
    1305              :         {
    1306              :           /* Match an assignment under the form:
    1307              :              "a = b +- ...".  */
    1308      7907649 :           t_bool res = follow_ssa_edge_expr (at_stmt, rhs0,
    1309              :                                              evolution_of_loop, limit);
    1310      7907649 :           if (res == t_true)
    1311      7686064 :             *evolution_of_loop = add_to_evolution
    1312      7686064 :                 (chrec_convert (type, *evolution_of_loop, at_stmt),
    1313              :                  rhs1, at_stmt);
    1314              :           return res;
    1315              :         }
    1316              :       /* Else search for the SCC in both rhs0 and rhs1.  */
    1317      1165604 :       return follow_ssa_edge_binary (at_stmt, type, rhs0, code, rhs1,
    1318      1165604 :                                      evolution_of_loop, limit);
    1319              : 
    1320              : 
    1321       893554 :     case MINUS_EXPR:
    1322              :       /* This case is under the form "rhs0 - rhs1".  */
    1323       893554 :       if (TREE_CODE (rhs0) == SSA_NAME)
    1324              :         {
    1325              :           /* Match an assignment under the form:
    1326              :              "a = b +- ...".  */
    1327       886957 :           t_bool res = follow_ssa_edge_expr (at_stmt, rhs0,
    1328              :                                              evolution_of_loop, limit);
    1329       886957 :           if (res != t_true)
    1330              :             return res;
    1331              :           /* We have to avoid negating INT_MIN given that a) invokes UB,
    1332              :              b) results in a wrong scev_direction.  See PR126171.  */
    1333      1683026 :           if (INTEGRAL_TYPE_P (type)
    1334       836497 :               && TYPE_OVERFLOW_UNDEFINED (type)
    1335       920910 :               && !expr_not_equal_to (rhs1,
    1336       920910 :                                      wi::to_wide (TYPE_MIN_VALUE (type))))
    1337              :             {
    1338        47253 :               tree utype = unsigned_type_for (type);
    1339        47253 :               tree to_add = chrec_convert_rhs (utype, rhs1);
    1340        47253 :               to_add = chrec_fold_multiply (utype, to_add,
    1341              :                                             build_int_cst_type (utype, -1));
    1342        47253 :               *evolution_of_loop
    1343        47253 :                 = chrec_convert (utype, *evolution_of_loop, at_stmt);
    1344        47253 :               *evolution_of_loop = add_to_evolution (*evolution_of_loop,
    1345              :                                                      to_add, at_stmt);
    1346        47253 :               *evolution_of_loop
    1347        47253 :                 = chrec_convert (type, *evolution_of_loop, at_stmt);
    1348              :             }
    1349              :           else
    1350              :             {
    1351       794260 :               tree to_add = chrec_fold_multiply (type, rhs1,
    1352              :                                                  build_minus_one_cst (type));
    1353       794260 :               *evolution_of_loop
    1354       794260 :                 = add_to_evolution (chrec_convert (type, *evolution_of_loop,
    1355              :                                                    at_stmt),
    1356              :                                     to_add, at_stmt);
    1357              :             }
    1358       841513 :           return res;
    1359              :         }
    1360              :       /* There is nothing to do.  */
    1361              :       return t_false;
    1362              : 
    1363              :     default:
    1364              :       return t_false;
    1365              :     }
    1366              : }
    1367              : 
    1368              : 
    1369              : /* This section selects the loops that will be good candidates for the
    1370              :    scalar evolution analysis.  For the moment, greedily select all the
    1371              :    loop nests we could analyze.  */
    1372              : 
    1373              : /* For a loop with a single exit edge, return the COND_EXPR that
    1374              :    guards the exit edge.  If the expression is too difficult to
    1375              :    analyze, then give up.  */
    1376              : 
    1377              : gcond *
    1378          343 : get_loop_exit_condition (const class loop *loop)
    1379              : {
    1380          343 :   return get_loop_exit_condition (single_exit (loop));
    1381              : }
    1382              : 
    1383              : /* If the statement just before the EXIT_EDGE contains a condition then
    1384              :    return the condition, otherwise NULL. */
    1385              : 
    1386              : gcond *
    1387      5278060 : get_loop_exit_condition (const_edge exit_edge)
    1388              : {
    1389      5278060 :   gcond *res = NULL;
    1390              : 
    1391      5278060 :   if (dump_file && (dump_flags & TDF_SCEV))
    1392            2 :     fprintf (dump_file, "(get_loop_exit_condition \n  ");
    1393              : 
    1394      5278060 :   if (exit_edge)
    1395     10556120 :     res = safe_dyn_cast <gcond *> (*gsi_last_bb (exit_edge->src));
    1396              : 
    1397      5278060 :   if (dump_file && (dump_flags & TDF_SCEV))
    1398              :     {
    1399            2 :       print_gimple_stmt (dump_file, res, 0);
    1400            2 :       fprintf (dump_file, ")\n");
    1401              :     }
    1402              : 
    1403      5278060 :   return res;
    1404              : }
    1405              : 
    1406              : 
    1407              : /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
    1408              :    Handle below case and return the corresponding POLYNOMIAL_CHREC:
    1409              : 
    1410              :    # i_17 = PHI <i_13(5), 0(3)>
    1411              :    # _20 = PHI <_5(5), start_4(D)(3)>
    1412              :    ...
    1413              :    i_13 = i_17 + 1;
    1414              :    _5 = start_4(D) + i_13;
    1415              : 
    1416              :    Though variable _20 appears as a PEELED_CHREC in the form of
    1417              :    (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
    1418              : 
    1419              :    See PR41488.  */
    1420              : 
    1421              : static tree
    1422      1715638 : simplify_peeled_chrec (class loop *loop, tree arg, tree init_cond,
    1423              :                        tree *nowrap_bound = nullptr)
    1424              : {
    1425      3431276 :   aff_tree aff1, aff2;
    1426      1715638 :   tree ev, left, right, type, step_val;
    1427      1715638 :   hash_map<tree, name_expansion *> *peeled_chrec_map = NULL;
    1428              : 
    1429      1715638 :   tree local_nowrap_bound = NULL_TREE;
    1430      1715638 :   tree *bound = nullptr;
    1431      1715638 :   if (nowrap_bound)
    1432        33852 :     bound = &local_nowrap_bound;
    1433              : 
    1434      1715638 :   ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, arg));
    1435      1715638 :   if (ev == NULL_TREE)
    1436            0 :     return chrec_dont_know;
    1437              : 
    1438              :   /* Support the case where we can derive the original CHREC from the
    1439              :      peeled one if that's a converted other IV.  This can be done
    1440              :      when the original unpeeled converted IV does not overflow and
    1441              :      has the same initial value.  */
    1442      1704730 :   if (CONVERT_EXPR_P (ev)
    1443        10908 :       && TREE_CODE (init_cond) == INTEGER_CST
    1444         3674 :       && TREE_CODE (TREE_OPERAND (ev, 0)) == POLYNOMIAL_CHREC
    1445         3410 :       && (TYPE_PRECISION (TREE_TYPE (ev))
    1446         3410 :           > TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (ev, 0))))
    1447      1718887 :       && (!TYPE_UNSIGNED (TREE_TYPE (ev))
    1448         3243 :           || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (ev, 0)))))
    1449              :     {
    1450         3249 :       left = CHREC_LEFT (TREE_OPERAND (ev, 0));
    1451         3249 :       right = CHREC_RIGHT (TREE_OPERAND (ev, 0));
    1452         3249 :       tree left_before = chrec_fold_minus (TREE_TYPE (TREE_OPERAND (ev, 0)),
    1453              :                                            left, right);
    1454         3249 :       if (TREE_CODE (left_before) == INTEGER_CST
    1455         3248 :           && wi::to_widest (init_cond) == wi::to_widest (left_before)
    1456         6497 :           && !scev_probably_wraps_p (NULL_TREE, left_before, right, NULL,
    1457              :                                      loop, false, bound))
    1458              :         {
    1459          317 :           tree tp = TREE_TYPE (right);
    1460              : 
    1461              :           /* We need a sign-extension to make things like
    1462              :              u8(6, 4, 2) => i32(6, 4, 2), instead of i32(6, 260, 514).  */
    1463          317 :           if (TYPE_UNSIGNED (tp))
    1464          317 :             right = fold_convert (signed_type_for (tp), right);
    1465              : 
    1466          317 :           scev_combine_nowrap_bounds (nowrap_bound, local_nowrap_bound);
    1467          317 :           return build_polynomial_chrec
    1468          317 :             (loop->num, init_cond, chrec_convert (TREE_TYPE (ev), right, NULL,
    1469              :                                                   nullptr, false,
    1470          317 :                                                   NULL_TREE));
    1471              :         }
    1472         2932 :       return chrec_dont_know;
    1473              :     }
    1474              : 
    1475      1712389 :   if (TREE_CODE (ev) != POLYNOMIAL_CHREC)
    1476      1667325 :     return chrec_dont_know;
    1477              : 
    1478        45064 :   left = CHREC_LEFT (ev);
    1479        45064 :   right = CHREC_RIGHT (ev);
    1480        45064 :   type = TREE_TYPE (left);
    1481        45064 :   step_val = chrec_fold_plus (type, init_cond, right);
    1482              : 
    1483              :   /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
    1484              :      if "left" equals to "init + right".  */
    1485        45064 :   if (operand_equal_p (left, step_val, 0)
    1486        45064 :       && ((!POINTER_TYPE_P (type) && !INTEGRAL_TYPE_P (type))
    1487        22303 :           || TYPE_OVERFLOW_WRAPS (type)
    1488              :           /* When overflow in the type doesn't wrap, make sure the
    1489              :              resulting CHREC does not either.  */
    1490         3819 :           || !scev_probably_wraps_p (NULL_TREE, init_cond, right, NULL,
    1491              :                                      loop, false)))
    1492              :     {
    1493        20462 :       if (dump_file && (dump_flags & TDF_SCEV))
    1494            1 :         fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
    1495              : 
    1496        20462 :       scev_combine_nowrap_bounds (nowrap_bound, local_nowrap_bound);
    1497        20462 :       return build_polynomial_chrec (loop->num, init_cond, right);
    1498              :     }
    1499              : 
    1500              :   /* The affine code only deals with pointer and integer types.  */
    1501        24602 :   if (!POINTER_TYPE_P (type)
    1502        18104 :       && !INTEGRAL_TYPE_P (type))
    1503           13 :     return chrec_dont_know;
    1504              : 
    1505              :   /* Try harder to check if they are equal.  */
    1506        24589 :   tree_to_aff_combination_expand (left, type, &aff1, &peeled_chrec_map);
    1507        24589 :   tree_to_aff_combination_expand (step_val, type, &aff2, &peeled_chrec_map);
    1508        24589 :   free_affine_expand_cache (&peeled_chrec_map);
    1509        24589 :   aff_combination_scale (&aff2, -1);
    1510        24589 :   aff_combination_add (&aff1, &aff2);
    1511              : 
    1512              :   /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
    1513              :      if "left" equals to "init + right".  */
    1514        24589 :   if (aff_combination_zero_p (&aff1)
    1515        24589 :       && ((!POINTER_TYPE_P (type) && !INTEGRAL_TYPE_P (type))
    1516        16895 :           || TYPE_OVERFLOW_WRAPS (type)
    1517              :           /* When overflow in the type doesn't wrap, make sure the
    1518              :              resulting CHREC does not either.  */
    1519        12580 :           || !scev_probably_wraps_p (NULL_TREE, init_cond, right, NULL,
    1520              :                                      loop, false)))
    1521              :     {
    1522         4362 :       if (dump_file && (dump_flags & TDF_SCEV))
    1523            1 :         fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
    1524              : 
    1525         4362 :       scev_combine_nowrap_bounds (nowrap_bound, local_nowrap_bound);
    1526         4362 :       return build_polynomial_chrec (loop->num, init_cond, right);
    1527              :     }
    1528        20227 :   return chrec_dont_know;
    1529      1715638 : }
    1530              : 
    1531              : /* Given a LOOP_PHI_NODE, this function determines the evolution
    1532              :    function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop.  */
    1533              : 
    1534              : static tree
    1535     11701913 : analyze_evolution_in_loop (gphi *loop_phi_node,
    1536              :                            tree init_cond,
    1537              :                            tree *nowrap_bound = nullptr)
    1538              : {
    1539     11701913 :   int i, n = gimple_phi_num_args (loop_phi_node);
    1540     11701913 :   tree evolution_function = chrec_not_analyzed_yet;
    1541     11701913 :   class loop *loop = loop_containing_stmt (loop_phi_node);
    1542     11701913 :   basic_block bb;
    1543     11701913 :   static bool simplify_peeled_chrec_p = true;
    1544              : 
    1545     11701913 :   if (dump_file && (dump_flags & TDF_SCEV))
    1546              :     {
    1547            3 :       fprintf (dump_file, "(analyze_evolution_in_loop \n");
    1548            3 :       fprintf (dump_file, "  (loop_phi_node = ");
    1549            3 :       print_gimple_stmt (dump_file, loop_phi_node, 0);
    1550            3 :       fprintf (dump_file, ")\n");
    1551              :     }
    1552              : 
    1553     30818249 :   for (i = 0; i < n; i++)
    1554              :     {
    1555     21995772 :       tree arg = PHI_ARG_DEF (loop_phi_node, i);
    1556     21995772 :       tree ev_fn = chrec_dont_know;
    1557     21995772 :       t_bool res;
    1558              : 
    1559              :       /* Select the edges that enter the loop body.  */
    1560     21995772 :       bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
    1561     21995772 :       if (!flow_bb_inside_loop_p (loop, bb))
    1562     10293859 :         continue;
    1563              : 
    1564     11701913 :       if (TREE_CODE (arg) == SSA_NAME)
    1565              :         {
    1566     11584570 :           bool val = false;
    1567              : 
    1568              :           /* Pass in the initial condition to the follow edge function.  */
    1569     11584570 :           scev_dfs dfs (loop, loop_phi_node, init_cond);
    1570     11584570 :           res = dfs.get_ev (&ev_fn, arg);
    1571              : 
    1572              :           /* If ev_fn has no evolution in the inner loop, and the
    1573              :              init_cond is not equal to ev_fn, then we have an
    1574              :              ambiguity between two possible values, as we cannot know
    1575              :              the number of iterations at this point.  */
    1576     11584570 :           if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC
    1577      2765031 :               && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
    1578     11584570 :               && !operand_equal_p (init_cond, ev_fn, 0))
    1579            0 :             ev_fn = chrec_dont_know;
    1580              :         }
    1581              :       else
    1582              :         res = t_false;
    1583              : 
    1584              :       /* When it is impossible to go back on the same
    1585              :          loop_phi_node by following the ssa edges, the
    1586              :          evolution is represented by a peeled chrec, i.e. the
    1587              :          first iteration, EV_FN has the value INIT_COND, then
    1588              :          all the other iterations it has the value of ARG.
    1589              :          For the moment, PEELED_CHREC nodes are not built.  */
    1590     11584570 :       if (res != t_true)
    1591              :         {
    1592      2525496 :           ev_fn = chrec_dont_know;
    1593              :           /* Try to recognize POLYNOMIAL_CHREC which appears in
    1594              :              the form of PEELED_CHREC, but guard the process with
    1595              :              a bool variable to keep the analyzer from infinite
    1596              :              recurrence for real PEELED_RECs.  */
    1597      2525496 :           if (simplify_peeled_chrec_p && TREE_CODE (arg) == SSA_NAME)
    1598              :             {
    1599      1715638 :               simplify_peeled_chrec_p = false;
    1600      3431276 :               ev_fn = simplify_peeled_chrec
    1601      1715638 :                 (loop, arg, init_cond, nowrap_bound);
    1602      1715638 :               simplify_peeled_chrec_p = true;
    1603              :             }
    1604              :         }
    1605              : 
    1606              :       /* When there are multiple back edges of the loop (which in fact never
    1607              :          happens currently, but nevertheless), merge their evolutions.  */
    1608     11701913 :       evolution_function = chrec_merge (evolution_function, ev_fn);
    1609              : 
    1610     11701913 :       if (evolution_function == chrec_dont_know)
    1611              :         break;
    1612              :     }
    1613              : 
    1614     11701913 :   if (dump_file && (dump_flags & TDF_SCEV))
    1615              :     {
    1616            3 :       fprintf (dump_file, "  (evolution_function = ");
    1617            3 :       print_generic_expr (dump_file, evolution_function);
    1618            3 :       fprintf (dump_file, "))\n");
    1619              :     }
    1620              : 
    1621     11701913 :   return evolution_function;
    1622              : }
    1623              : 
    1624              : /* Looks to see if VAR is a copy of a constant (via straightforward assignments
    1625              :    or degenerate phi's).  If so, returns the constant; else, returns VAR.  */
    1626              : 
    1627              : static tree
    1628     23905599 : follow_copies_to_constant (tree var)
    1629              : {
    1630     23905599 :   tree res = var;
    1631     23905599 :   while (TREE_CODE (res) == SSA_NAME
    1632              :          /* We face not updated SSA form in multiple places and this walk
    1633              :             may end up in sibling loops so we have to guard it.  */
    1634     28919319 :          && !name_registered_for_update_p (res))
    1635              :     {
    1636     16884020 :       gimple *def = SSA_NAME_DEF_STMT (res);
    1637     16884020 :       if (gphi *phi = dyn_cast <gphi *> (def))
    1638              :         {
    1639      4234718 :           if (tree rhs = degenerate_phi_result (phi))
    1640              :             res = rhs;
    1641              :           else
    1642              :             break;
    1643              :         }
    1644     12649302 :       else if (gimple_assign_single_p (def))
    1645              :         /* Will exit loop if not an SSA_NAME.  */
    1646      4764018 :         res = gimple_assign_rhs1 (def);
    1647              :       else
    1648              :         break;
    1649              :     }
    1650     23905599 :   if (CONSTANT_CLASS_P (res))
    1651      7110750 :     return res;
    1652              :   return var;
    1653              : }
    1654              : 
    1655              : /* Given a loop-phi-node, return the initial conditions of the
    1656              :    variable on entry of the loop.  When the CCP has propagated
    1657              :    constants into the loop-phi-node, the initial condition is
    1658              :    instantiated, otherwise the initial condition is kept symbolic.
    1659              :    This analyzer does not analyze the evolution outside the current
    1660              :    loop, and leaves this task to the on-demand tree reconstructor.  */
    1661              : 
    1662              : static tree
    1663     11701913 : analyze_initial_condition (gphi *loop_phi_node)
    1664              : {
    1665     11701913 :   int i, n;
    1666     11701913 :   tree init_cond = chrec_not_analyzed_yet;
    1667     11701913 :   class loop *loop = loop_containing_stmt (loop_phi_node);
    1668              : 
    1669     11701913 :   if (dump_file && (dump_flags & TDF_SCEV))
    1670              :     {
    1671            3 :       fprintf (dump_file, "(analyze_initial_condition \n");
    1672            3 :       fprintf (dump_file, "  (loop_phi_node = \n");
    1673            3 :       print_gimple_stmt (dump_file, loop_phi_node, 0);
    1674            3 :       fprintf (dump_file, ")\n");
    1675              :     }
    1676              : 
    1677     11701913 :   n = gimple_phi_num_args (loop_phi_node);
    1678     35105739 :   for (i = 0; i < n; i++)
    1679              :     {
    1680     23403826 :       tree branch = PHI_ARG_DEF (loop_phi_node, i);
    1681     23403826 :       basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
    1682              : 
    1683              :       /* When the branch is oriented to the loop's body, it does
    1684              :          not contribute to the initial condition.  */
    1685     23403826 :       if (flow_bb_inside_loop_p (loop, bb))
    1686     11701913 :         continue;
    1687              : 
    1688     11701913 :       if (init_cond == chrec_not_analyzed_yet)
    1689              :         {
    1690     11701913 :           init_cond = branch;
    1691     11701913 :           continue;
    1692              :         }
    1693              : 
    1694            0 :       if (TREE_CODE (branch) == SSA_NAME)
    1695              :         {
    1696            0 :           init_cond = chrec_dont_know;
    1697            0 :           break;
    1698              :         }
    1699              : 
    1700            0 :       init_cond = chrec_merge (init_cond, branch);
    1701              :     }
    1702              : 
    1703              :   /* Ooops -- a loop without an entry???  */
    1704     11701913 :   if (init_cond == chrec_not_analyzed_yet)
    1705            0 :     init_cond = chrec_dont_know;
    1706              : 
    1707              :   /* We may not have fully constant propagated IL.  Handle degenerate PHIs here
    1708              :      to not miss important early loop unrollings.  */
    1709     11701913 :   init_cond = follow_copies_to_constant (init_cond);
    1710              : 
    1711     11701913 :   if (dump_file && (dump_flags & TDF_SCEV))
    1712              :     {
    1713            3 :       fprintf (dump_file, "  (init_cond = ");
    1714            3 :       print_generic_expr (dump_file, init_cond);
    1715            3 :       fprintf (dump_file, "))\n");
    1716              :     }
    1717              : 
    1718     11701913 :   return init_cond;
    1719              : }
    1720              : 
    1721              : /* Analyze the scalar evolution for LOOP_PHI_NODE.  */
    1722              : 
    1723              : static tree
    1724     11701913 : interpret_loop_phi (class loop *loop, gphi *loop_phi_node,
    1725              :                     tree *nowrap_bound = nullptr)
    1726              : {
    1727     11701913 :   class loop *phi_loop = loop_containing_stmt (loop_phi_node);
    1728     11701913 :   tree init_cond;
    1729              : 
    1730     11701913 :   gcc_assert (phi_loop == loop);
    1731              : 
    1732              :   /* Otherwise really interpret the loop phi.  */
    1733     11701913 :   init_cond = analyze_initial_condition (loop_phi_node);
    1734     11701913 :   return analyze_evolution_in_loop (loop_phi_node, init_cond, nowrap_bound);
    1735              : }
    1736              : 
    1737              : /* This function merges the branches of a condition-phi-node,
    1738              :    contained in the outermost loop, and whose arguments are already
    1739              :    analyzed.  */
    1740              : 
    1741              : static tree
    1742      2796918 : interpret_condition_phi (class loop *loop, gphi *condition_phi,
    1743              :                          tree *nowrap_bound)
    1744              : {
    1745      2796918 :   int i, n = gimple_phi_num_args (condition_phi);
    1746      2796918 :   tree res = chrec_not_analyzed_yet;
    1747              : 
    1748      5899685 :   for (i = 0; i < n; i++)
    1749              :     {
    1750      5348821 :       tree branch_chrec;
    1751              : 
    1752      5348821 :       if (backedge_phi_arg_p (condition_phi, i))
    1753              :         {
    1754        49191 :           res = chrec_dont_know;
    1755        49191 :           break;
    1756              :         }
    1757              : 
    1758      5299630 :       branch_chrec = analyze_scalar_evolution
    1759      5299630 :         (loop, PHI_ARG_DEF (condition_phi, i), nowrap_bound);
    1760              : 
    1761      5299630 :       res = chrec_merge (res, branch_chrec);
    1762      5299630 :       if (res == chrec_dont_know)
    1763              :         break;
    1764              :     }
    1765              : 
    1766      2796918 :   return res;
    1767              : }
    1768              : 
    1769              : /* Interpret the operation RHS1 OP RHS2.  If we didn't
    1770              :    analyze this node before, follow the definitions until ending
    1771              :    either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node.  On the
    1772              :    return path, this function propagates evolutions (ala constant copy
    1773              :    propagation).  OPND1 is not a GIMPLE expression because we could
    1774              :    analyze the effect of an inner loop: see interpret_loop_phi.  */
    1775              : 
    1776              : static tree
    1777     47239190 : interpret_rhs_expr (class loop *loop, gimple *at_stmt,
    1778              :                     tree type, tree rhs1, enum tree_code code, tree rhs2,
    1779              :                     tree *nowrap_bound = nullptr)
    1780              : {
    1781     47239190 :   tree res, chrec1, chrec2, ctype;
    1782     47239190 :   gimple *def;
    1783              : 
    1784     47239190 :   if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
    1785              :     {
    1786     11438078 :       if (is_gimple_min_invariant (rhs1))
    1787      2514290 :         return chrec_convert (type, rhs1, at_stmt);
    1788              : 
    1789      8923788 :       if (code == SSA_NAME)
    1790       134887 :         return chrec_convert (type,
    1791              :                               analyze_scalar_evolution (loop, rhs1,
    1792              :                                                         nowrap_bound),
    1793       134887 :                               at_stmt, nowrap_bound);
    1794              :     }
    1795              : 
    1796     44590013 :   switch (code)
    1797              :     {
    1798       353475 :     case ADDR_EXPR:
    1799       353475 :       if (TREE_CODE (TREE_OPERAND (rhs1, 0)) == MEM_REF
    1800       353475 :           || handled_component_p (TREE_OPERAND (rhs1, 0)))
    1801              :         {
    1802       353361 :           machine_mode mode;
    1803       353361 :           poly_int64 bitsize, bitpos;
    1804       353361 :           int unsignedp, reversep;
    1805       353361 :           int volatilep = 0;
    1806       353361 :           tree base, offset;
    1807       353361 :           tree chrec3;
    1808       353361 :           tree unitpos;
    1809              : 
    1810       353361 :           base = get_inner_reference (TREE_OPERAND (rhs1, 0),
    1811              :                                       &bitsize, &bitpos, &offset, &mode,
    1812              :                                       &unsignedp, &reversep, &volatilep);
    1813              : 
    1814       353361 :           if (TREE_CODE (base) == MEM_REF)
    1815              :             {
    1816       270796 :               rhs2 = TREE_OPERAND (base, 1);
    1817       270796 :               rhs1 = TREE_OPERAND (base, 0);
    1818              : 
    1819       270796 :               chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
    1820       270796 :               chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound);
    1821       270796 :               chrec1 = chrec_convert (type, chrec1, at_stmt, nowrap_bound);
    1822       270796 :               chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt,
    1823              :                                       nowrap_bound);
    1824       270796 :               chrec1 = instantiate_parameters (loop, chrec1);
    1825       270796 :               chrec2 = instantiate_parameters (loop, chrec2);
    1826       270796 :               res = chrec_fold_plus (type, chrec1, chrec2);
    1827              :             }
    1828              :           else
    1829              :             {
    1830        82565 :               chrec1 = analyze_scalar_evolution_for_address_of (loop, base,
    1831              :                                                                 nowrap_bound);
    1832        82565 :               chrec1 = chrec_convert (type, chrec1, at_stmt, nowrap_bound);
    1833        82565 :               res = chrec1;
    1834              :             }
    1835              : 
    1836       353361 :           if (offset != NULL_TREE)
    1837              :             {
    1838       155075 :               chrec2 = analyze_scalar_evolution (loop, offset, nowrap_bound);
    1839       155075 :               chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt,
    1840              :                                       nowrap_bound);
    1841       155075 :               chrec2 = instantiate_parameters (loop, chrec2);
    1842       155075 :               res = chrec_fold_plus (type, res, chrec2);
    1843              :             }
    1844              : 
    1845       353361 :           if (maybe_ne (bitpos, 0))
    1846              :             {
    1847       129398 :               unitpos = size_int (exact_div (bitpos, BITS_PER_UNIT));
    1848       129398 :               chrec3 = analyze_scalar_evolution (loop, unitpos, nowrap_bound);
    1849       129398 :               chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt,
    1850              :                                       nowrap_bound);
    1851       129398 :               chrec3 = instantiate_parameters (loop, chrec3);
    1852       129398 :               res = chrec_fold_plus (type, res, chrec3);
    1853              :             }
    1854              :         }
    1855              :       else
    1856          114 :         res = chrec_dont_know;
    1857              :       break;
    1858              : 
    1859      3688506 :     case POINTER_PLUS_EXPR:
    1860      3688506 :       chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
    1861      3688506 :       chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound);
    1862      3688506 :       chrec1 = chrec_convert (type, chrec1, at_stmt, nowrap_bound);
    1863      3688506 :       chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt,
    1864              :                               nowrap_bound);
    1865      3688506 :       chrec1 = instantiate_parameters (loop, chrec1);
    1866      3688506 :       chrec2 = instantiate_parameters (loop, chrec2);
    1867      3688506 :       res = chrec_fold_plus (type, chrec1, chrec2);
    1868      3688506 :       break;
    1869              : 
    1870       135538 :     case POINTER_DIFF_EXPR:
    1871       135538 :       {
    1872       135538 :         tree utype = unsigned_type_for (type);
    1873       135538 :         chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
    1874       135538 :         chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound);
    1875       135538 :         chrec1 = chrec_convert (utype, chrec1, at_stmt, nowrap_bound);
    1876       135538 :         chrec2 = chrec_convert (utype, chrec2, at_stmt, nowrap_bound);
    1877       135538 :         chrec1 = instantiate_parameters (loop, chrec1);
    1878       135538 :         chrec2 = instantiate_parameters (loop, chrec2);
    1879       135538 :         res = chrec_fold_minus (utype, chrec1, chrec2);
    1880       135538 :         res = chrec_convert (type, res, at_stmt, nowrap_bound);
    1881       135538 :         break;
    1882              :       }
    1883              : 
    1884     12348591 :     case PLUS_EXPR:
    1885     12348591 :       chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
    1886     12348591 :       chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound);
    1887     12348591 :       ctype = type;
    1888              :       /* When the stmt is conditionally executed re-write the CHREC
    1889              :          into a form that has well-defined behavior on overflow.  */
    1890     12348591 :       if (at_stmt
    1891     11146950 :           && INTEGRAL_TYPE_P (type)
    1892     11052414 :           && ! TYPE_OVERFLOW_WRAPS (type)
    1893     20757543 :           && ! dominated_by_p (CDI_DOMINATORS, loop->latch,
    1894      8408952 :                                gimple_bb (at_stmt)))
    1895       752715 :         ctype = unsigned_type_for (type);
    1896     12348591 :       chrec1 = chrec_convert (ctype, chrec1, at_stmt, nowrap_bound);
    1897     12348591 :       chrec2 = chrec_convert (ctype, chrec2, at_stmt, nowrap_bound);
    1898     12348591 :       chrec1 = instantiate_parameters (loop, chrec1);
    1899     12348591 :       chrec2 = instantiate_parameters (loop, chrec2);
    1900     12348591 :       res = chrec_fold_plus (ctype, chrec1, chrec2);
    1901     12348591 :       if (type != ctype)
    1902       752715 :         res = chrec_convert (type, res, at_stmt, nowrap_bound);
    1903              :       break;
    1904              : 
    1905      1531663 :     case MINUS_EXPR:
    1906      1531663 :       chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
    1907      1531663 :       chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound);
    1908      1531663 :       ctype = type;
    1909              :       /* When the stmt is conditionally executed re-write the CHREC
    1910              :          into a form that has well-defined behavior on overflow.  */
    1911      1531663 :       if (at_stmt
    1912      1456269 :           && INTEGRAL_TYPE_P (type)
    1913      1418320 :           && ! TYPE_OVERFLOW_WRAPS (type)
    1914      2081994 :           && ! dominated_by_p (CDI_DOMINATORS,
    1915       550331 :                                loop->latch, gimple_bb (at_stmt)))
    1916       141373 :         ctype = unsigned_type_for (type);
    1917      1531663 :       chrec1 = chrec_convert (ctype, chrec1, at_stmt, nowrap_bound);
    1918      1531663 :       chrec2 = chrec_convert (ctype, chrec2, at_stmt, nowrap_bound);
    1919      1531663 :       chrec1 = instantiate_parameters (loop, chrec1);
    1920      1531663 :       chrec2 = instantiate_parameters (loop, chrec2);
    1921      1531663 :       res = chrec_fold_minus (ctype, chrec1, chrec2);
    1922      1531663 :       if (type != ctype)
    1923       141373 :         res = chrec_convert (type, res, at_stmt, nowrap_bound);
    1924              :       break;
    1925              : 
    1926        77833 :     case NEGATE_EXPR:
    1927        77833 :       chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
    1928        77833 :       ctype = type;
    1929              :       /* When the stmt is conditionally executed re-write the CHREC
    1930              :          into a form that has well-defined behavior on overflow.  */
    1931        77833 :       if (at_stmt
    1932        70651 :           && INTEGRAL_TYPE_P (type)
    1933        68758 :           && ! TYPE_OVERFLOW_WRAPS (type)
    1934       117506 :           && ! dominated_by_p (CDI_DOMINATORS,
    1935        39673 :                                loop->latch, gimple_bb (at_stmt)))
    1936         5766 :         ctype = unsigned_type_for (type);
    1937        77833 :       chrec1 = chrec_convert (ctype, chrec1, at_stmt, nowrap_bound);
    1938              :       /* TYPE may be integer, real or complex, so use fold_convert.  */
    1939        77833 :       chrec1 = instantiate_parameters (loop, chrec1);
    1940        77833 :       res = chrec_fold_multiply (ctype, chrec1,
    1941              :                                  fold_convert (ctype, integer_minus_one_node));
    1942        77833 :       if (type != ctype)
    1943         5766 :         res = chrec_convert (type, res, at_stmt, nowrap_bound);
    1944              :       break;
    1945              : 
    1946        38336 :     case BIT_NOT_EXPR:
    1947              :       /* Handle ~X as -1 - X.  */
    1948        38336 :       chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
    1949        38336 :       chrec1 = chrec_convert (type, chrec1, at_stmt, nowrap_bound);
    1950        38336 :       chrec1 = instantiate_parameters (loop, chrec1);
    1951        38336 :       res = chrec_fold_minus (type,
    1952              :                               fold_convert (type, integer_minus_one_node),
    1953              :                               chrec1);
    1954        38336 :       break;
    1955              : 
    1956      6424250 :     case MULT_EXPR:
    1957      6424250 :       chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
    1958      6424250 :       chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound);
    1959      6424250 :       ctype = type;
    1960              :       /* When the stmt is conditionally executed re-write the CHREC
    1961              :          into a form that has well-defined behavior on overflow.  */
    1962      6424250 :       if (at_stmt
    1963      4446879 :           && INTEGRAL_TYPE_P (type)
    1964      4324837 :           && ! TYPE_OVERFLOW_WRAPS (type)
    1965      8388241 :           && ! dominated_by_p (CDI_DOMINATORS,
    1966      1963991 :                                loop->latch, gimple_bb (at_stmt)))
    1967       191428 :         ctype = unsigned_type_for (type);
    1968      6424250 :       chrec1 = chrec_convert (ctype, chrec1, at_stmt, nowrap_bound);
    1969      6424250 :       chrec2 = chrec_convert (ctype, chrec2, at_stmt, nowrap_bound);
    1970      6424250 :       chrec1 = instantiate_parameters (loop, chrec1);
    1971      6424250 :       chrec2 = instantiate_parameters (loop, chrec2);
    1972      6424250 :       res = chrec_fold_multiply (ctype, chrec1, chrec2);
    1973      6424250 :       if (type != ctype)
    1974       191428 :         res = chrec_convert (type, res, at_stmt, nowrap_bound);
    1975              :       break;
    1976              : 
    1977       163278 :     case LSHIFT_EXPR:
    1978       163278 :       {
    1979              :         /* Handle A<<B as A * (1<<B).  */
    1980       163278 :         tree uns = unsigned_type_for (type);
    1981       163278 :         chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
    1982       163278 :         chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound);
    1983       163278 :         chrec1 = chrec_convert (uns, chrec1, at_stmt, nowrap_bound);
    1984       163278 :         chrec1 = instantiate_parameters (loop, chrec1);
    1985       163278 :         chrec2 = instantiate_parameters (loop, chrec2);
    1986              : 
    1987       163278 :         tree one = build_int_cst (uns, 1);
    1988       163278 :         chrec2 = fold_build2 (LSHIFT_EXPR, uns, one, chrec2);
    1989       163278 :         res = chrec_fold_multiply (uns, chrec1, chrec2);
    1990       163278 :         res = chrec_convert (type, res, at_stmt, nowrap_bound);
    1991              :       }
    1992       163278 :       break;
    1993              : 
    1994      9017976 :     CASE_CONVERT:
    1995              :       /* In case we have a truncation of a widened operation that in
    1996              :          the truncated type has undefined overflow behavior analyze
    1997              :          the operation done in an unsigned type of the same precision
    1998              :          as the final truncation.  We cannot derive a scalar evolution
    1999              :          for the widened operation but for the truncated result.  */
    2000      9015152 :       if (INTEGRAL_NB_TYPE_P (type)
    2001      8686065 :           && INTEGRAL_NB_TYPE_P (TREE_TYPE (rhs1))
    2002      8033815 :           && TYPE_PRECISION (type) < TYPE_PRECISION (TREE_TYPE (rhs1))
    2003       551143 :           && TYPE_OVERFLOW_UNDEFINED (type)
    2004       359400 :           && TREE_CODE (rhs1) == SSA_NAME
    2005       359264 :           && (def = SSA_NAME_DEF_STMT (rhs1))
    2006       359264 :           && is_gimple_assign (def)
    2007       201682 :           && TREE_CODE_CLASS (gimple_assign_rhs_code (def)) == tcc_binary
    2008      9162834 :           && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST)
    2009              :         {
    2010       107967 :           tree utype = unsigned_type_for (type);
    2011       107967 :           chrec1 = interpret_rhs_expr (loop, at_stmt, utype,
    2012              :                                        gimple_assign_rhs1 (def),
    2013              :                                        gimple_assign_rhs_code (def),
    2014              :                                        gimple_assign_rhs2 (def),
    2015              :                                        nowrap_bound);
    2016              :         }
    2017              :       else
    2018      8910009 :         chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
    2019      9017976 :       res = chrec_convert (type, chrec1, at_stmt, nowrap_bound, true, rhs1);
    2020      9017976 :       break;
    2021              : 
    2022       410066 :     case BIT_AND_EXPR:
    2023              :       /* Given int variable A, handle A&0xffff as (int)(unsigned short)A.
    2024              :          If A is SCEV and its value is in the range of representable set
    2025              :          of type unsigned short, the result expression is a (no-overflow)
    2026              :          SCEV.  */
    2027       410066 :       res = chrec_dont_know;
    2028       410066 :       if (tree_fits_uhwi_p (rhs2))
    2029              :         {
    2030       274426 :           int precision;
    2031       274426 :           unsigned HOST_WIDE_INT val = tree_to_uhwi (rhs2);
    2032              : 
    2033       274426 :           val ++;
    2034              :           /* Skip if value of rhs2 wraps in unsigned HOST_WIDE_INT or
    2035              :              it's not the maximum value of a smaller type than rhs1.  */
    2036       274426 :           if (val != 0
    2037       212865 :               && (precision = exact_log2 (val)) > 0
    2038       487291 :               && (unsigned) precision < TYPE_PRECISION (TREE_TYPE (rhs1)))
    2039              :             {
    2040       212865 :               tree utype = build_nonstandard_integer_type (precision, 1);
    2041              : 
    2042       212865 :               if (TYPE_PRECISION (utype) < TYPE_PRECISION (TREE_TYPE (rhs1)))
    2043              :                 {
    2044       212865 :                   chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
    2045       212865 :                   chrec1 = chrec_convert (utype, chrec1, at_stmt,
    2046              :                                           nowrap_bound);
    2047       212865 :                   res = chrec_convert (TREE_TYPE (rhs1), chrec1, at_stmt,
    2048              :                                        nowrap_bound);
    2049              :                 }
    2050              :             }
    2051              :         }
    2052              :       break;
    2053              : 
    2054     10400501 :     default:
    2055     10400501 :       res = chrec_dont_know;
    2056     10400501 :       break;
    2057              :     }
    2058              : 
    2059              :   return res;
    2060              : }
    2061              : 
    2062              : /* Interpret the expression EXPR.  */
    2063              : 
    2064              : static tree
    2065      9259896 : interpret_expr (class loop *loop, gimple *at_stmt, tree expr,
    2066              :                 tree *nowrap_bound)
    2067              : {
    2068      9259896 :   enum tree_code code;
    2069      9259896 :   tree type = TREE_TYPE (expr), op0, op1;
    2070              : 
    2071      9259896 :   if (automatically_generated_chrec_p (expr))
    2072              :     return expr;
    2073              : 
    2074      9254783 :   if (TREE_CODE (expr) == POLYNOMIAL_CHREC
    2075      9254213 :       || TREE_CODE (expr) == CALL_EXPR
    2076     18508857 :       || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
    2077              :     return chrec_dont_know;
    2078              : 
    2079      9182423 :   extract_ops_from_tree (expr, &code, &op0, &op1);
    2080              : 
    2081      9182423 :   return interpret_rhs_expr (loop, at_stmt, type,
    2082      9182423 :                              op0, code, op1, nowrap_bound);
    2083              : }
    2084              : 
    2085              : /* Interpret the rhs of the assignment STMT.  */
    2086              : 
    2087              : static tree
    2088     37948800 : interpret_gimple_assign (class loop *loop, gimple *stmt, tree *nowrap_bound)
    2089              : {
    2090     37948800 :   tree type = TREE_TYPE (gimple_assign_lhs (stmt));
    2091     37948800 :   enum tree_code code = gimple_assign_rhs_code (stmt);
    2092              : 
    2093     37948800 :   return interpret_rhs_expr (loop, stmt, type,
    2094              :                              gimple_assign_rhs1 (stmt), code,
    2095     37948800 :                              gimple_assign_rhs2 (stmt), nowrap_bound);
    2096              : }
    2097              : 
    2098              : 
    2099              : 
    2100              : /* This section contains all the entry points:
    2101              :    - number_of_iterations_in_loop,
    2102              :    - analyze_scalar_evolution,
    2103              :    - instantiate_parameters.
    2104              : */
    2105              : 
    2106              : /* Helper recursive function.  */
    2107              : 
    2108              : static tree
    2109     78598724 : analyze_scalar_evolution_1 (class loop *loop, tree var, tree *nowrap_bound)
    2110              : {
    2111     78598724 :   gimple *def;
    2112     78598724 :   basic_block bb;
    2113     78598724 :   class loop *def_loop;
    2114     78598724 :   tree res;
    2115              : 
    2116     78598724 :   if (TREE_CODE (var) != SSA_NAME)
    2117      9259896 :     return interpret_expr (loop, NULL, var, nowrap_bound);
    2118              : 
    2119     69338828 :   tree local_nowrap_bound = NULL_TREE;
    2120     69338828 :   tree *bound = nullptr;
    2121     69338828 :   if (nowrap_bound)
    2122       988101 :     bound = &local_nowrap_bound;
    2123              : 
    2124     69338828 :   def = SSA_NAME_DEF_STMT (var);
    2125     69338828 :   bb = gimple_bb (def);
    2126     69338828 :   def_loop = bb->loop_father;
    2127              : 
    2128     69338828 :   if (!flow_bb_inside_loop_p (loop, bb))
    2129              :     {
    2130              :       /* Keep symbolic form, but look through obvious copies for constants.  */
    2131     12203686 :       res = follow_copies_to_constant (var);
    2132     12203686 :       goto set_and_end;
    2133              :     }
    2134              : 
    2135     57135142 :   if (loop != def_loop)
    2136              :     {
    2137      4126255 :       res = analyze_scalar_evolution_1 (def_loop, var, bound);
    2138      4126255 :       class loop *loop_to_skip = superloop_at_depth (def_loop,
    2139      4126255 :                                                       loop_depth (loop) + 1);
    2140      4126255 :       res = compute_overall_effect_of_inner_loop (loop_to_skip, res);
    2141      4126255 :       if (chrec_contains_symbols_defined_in_loop (res, loop->num))
    2142       296607 :         res = analyze_scalar_evolution_1 (loop, res, bound);
    2143      4126255 :       goto set_and_end;
    2144              :     }
    2145              : 
    2146     53008887 :   switch (gimple_code (def))
    2147              :     {
    2148     37948800 :     case GIMPLE_ASSIGN:
    2149     37948800 :       res = interpret_gimple_assign (loop, def, bound);
    2150     37948800 :       break;
    2151              : 
    2152     14498831 :     case GIMPLE_PHI:
    2153     28997662 :       if (loop_phi_node_p (def))
    2154     11701913 :         res = interpret_loop_phi (loop, as_a <gphi *> (def), bound);
    2155              :       else
    2156      2796918 :         res = interpret_condition_phi (loop, as_a <gphi *> (def), bound);
    2157              :       break;
    2158              : 
    2159       561256 :     default:
    2160       561256 :       res = chrec_dont_know;
    2161       561256 :       break;
    2162              :     }
    2163              : 
    2164     69338828 :  set_and_end:
    2165              : 
    2166              :   /* Keep the symbolic form.  */
    2167     69338828 :   if (res == chrec_dont_know)
    2168     25726656 :     res = var;
    2169              : 
    2170     69338828 :   if (loop == def_loop)
    2171     53008887 :     set_scalar_evolution (block_before_loop (loop), var, res, bound);
    2172              : 
    2173     69338828 :   scev_combine_nowrap_bounds (nowrap_bound, local_nowrap_bound);
    2174              : 
    2175     69338828 :   return res;
    2176              : }
    2177              : 
    2178              : /* Analyzes and returns the scalar evolution of the ssa_name VAR in
    2179              :    LOOP.  LOOP is the loop in which the variable is used.
    2180              : 
    2181              :    Example of use: having a pointer VAR to a SSA_NAME node, STMT a
    2182              :    pointer to the statement that uses this variable, in order to
    2183              :    determine the evolution function of the variable, use the following
    2184              :    calls:
    2185              : 
    2186              :    loop_p loop = loop_containing_stmt (stmt);
    2187              :    tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
    2188              :    tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
    2189              : */
    2190              : 
    2191              : tree
    2192    202740632 : analyze_scalar_evolution (class loop *loop, tree var, tree *nowrap_bound)
    2193              : {
    2194    202740632 :   tree res;
    2195              : 
    2196              :   /* ???  Fix callers.  */
    2197    202740632 :   if (! loop)
    2198              :     return var;
    2199              : 
    2200    202546230 :   if (dump_file && (dump_flags & TDF_SCEV))
    2201              :     {
    2202           38 :       fprintf (dump_file, "(analyze_scalar_evolution \n");
    2203           38 :       fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
    2204           38 :       fprintf (dump_file, "  (scalar = ");
    2205           38 :       print_generic_expr (dump_file, var);
    2206           38 :       fprintf (dump_file, ")\n");
    2207              :     }
    2208              : 
    2209    202546230 :   res = get_scalar_evolution (block_before_loop (loop), var, nowrap_bound);
    2210    202546230 :   if (res == chrec_not_analyzed_yet)
    2211              :     {
    2212              :       /* We'll recurse into instantiate_scev, avoid tearing down the
    2213              :          instantiate cache repeatedly and keep it live from here.  */
    2214     74175862 :       bool destr = false;
    2215     74175862 :       if (!global_cache)
    2216              :         {
    2217     43823620 :           global_cache = new instantiate_cache_type;
    2218     43823620 :           destr = true;
    2219              :         }
    2220     74175862 :       res = analyze_scalar_evolution_1 (loop, var, nowrap_bound);
    2221     74175862 :       if (destr)
    2222              :         {
    2223     43823620 :           delete global_cache;
    2224     43823620 :           global_cache = NULL;
    2225              :         }
    2226              :     }
    2227              : 
    2228    202546230 :   if (dump_file && (dump_flags & TDF_SCEV))
    2229           38 :     fprintf (dump_file, ")\n");
    2230              : 
    2231              :   return res;
    2232              : }
    2233              : 
    2234              : /* If CHREC doesn't overflow, set the nonwrapping flag.  */
    2235              : 
    2236     11041590 : void record_nonwrapping_chrec (tree chrec)
    2237              : {
    2238     11041590 :   CHREC_NOWRAP(chrec) = 1;
    2239              : 
    2240     11041590 :   if (dump_file && (dump_flags & TDF_SCEV))
    2241              :     {
    2242            6 :       fprintf (dump_file, "(record_nonwrapping_chrec: ");
    2243            6 :       print_generic_expr (dump_file, chrec);
    2244            6 :       fprintf (dump_file, ")\n");
    2245              :     }
    2246     11041590 : }
    2247              : 
    2248              : /* Return true if CHREC's nonwrapping flag is set.  */
    2249              : 
    2250       225655 : bool nonwrapping_chrec_p (tree chrec)
    2251              : {
    2252       225655 :   if (!chrec || TREE_CODE(chrec) != POLYNOMIAL_CHREC)
    2253              :     return false;
    2254              : 
    2255       225306 :   return CHREC_NOWRAP(chrec);
    2256              : }
    2257              : 
    2258              : /* Analyzes and returns the scalar evolution of VAR address in LOOP.  */
    2259              : 
    2260              : static tree
    2261        82565 : analyze_scalar_evolution_for_address_of (class loop *loop, tree var,
    2262              :                                          tree *nowrap_bound)
    2263              : {
    2264        82565 :   return analyze_scalar_evolution (loop, build_fold_addr_expr (var),
    2265        82565 :                                    nowrap_bound);
    2266              : }
    2267              : 
    2268              : /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
    2269              :    WRTO_LOOP (which should be a superloop of USE_LOOP)
    2270              : 
    2271              :    FOLDED_CASTS is set to true if resolve_mixers used
    2272              :    chrec_convert_aggressive (TODO -- not really, we are way too conservative
    2273              :    at the moment in order to keep things simple).
    2274              : 
    2275              :    To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
    2276              :    example:
    2277              : 
    2278              :    for (i = 0; i < 100; i++)                 -- loop 1
    2279              :      {
    2280              :        for (j = 0; j < 100; j++)             -- loop 2
    2281              :          {
    2282              :            k1 = i;
    2283              :            k2 = j;
    2284              : 
    2285              :            use2 (k1, k2);
    2286              : 
    2287              :            for (t = 0; t < 100; t++)         -- loop 3
    2288              :              use3 (k1, k2);
    2289              : 
    2290              :          }
    2291              :        use1 (k1, k2);
    2292              :      }
    2293              : 
    2294              :    Both k1 and k2 are invariants in loop3, thus
    2295              :      analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
    2296              :      analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
    2297              : 
    2298              :    As they are invariant, it does not matter whether we consider their
    2299              :    usage in loop 3 or loop 2, hence
    2300              :      analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
    2301              :        analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
    2302              :      analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
    2303              :        analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
    2304              : 
    2305              :    Similarly for their evolutions with respect to loop 1.  The values of K2
    2306              :    in the use in loop 2 vary independently on loop 1, thus we cannot express
    2307              :    the evolution with respect to loop 1:
    2308              :      analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
    2309              :        analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
    2310              :      analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
    2311              :        analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
    2312              : 
    2313              :    The value of k2 in the use in loop 1 is known, though:
    2314              :      analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
    2315              :      analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
    2316              :    */
    2317              : 
    2318              : static tree
    2319     51515889 : analyze_scalar_evolution_in_loop (class loop *wrto_loop, class loop *use_loop,
    2320              :                                   tree version, bool *folded_casts,
    2321              :                                   tree *nowrap_bound = nullptr)
    2322              : {
    2323     51515889 :   bool val = false;
    2324     51515889 :   tree ev = version, tmp;
    2325              : 
    2326              :   /* We cannot just do
    2327              : 
    2328              :      tmp = analyze_scalar_evolution (use_loop, version);
    2329              :      ev = resolve_mixers (wrto_loop, tmp, folded_casts);
    2330              : 
    2331              :      as resolve_mixers would query the scalar evolution with respect to
    2332              :      wrto_loop.  For example, in the situation described in the function
    2333              :      comment, suppose that wrto_loop = loop1, use_loop = loop3 and
    2334              :      version = k2.  Then
    2335              : 
    2336              :      analyze_scalar_evolution (use_loop, version) = k2
    2337              : 
    2338              :      and resolve_mixers (loop1, k2, folded_casts) finds that the value of
    2339              :      k2 in loop 1 is 100, which is a wrong result, since we are interested
    2340              :      in the value in loop 3.
    2341              : 
    2342              :      Instead, we need to proceed from use_loop to wrto_loop loop by loop,
    2343              :      each time checking that there is no evolution in the inner loop.  */
    2344              : 
    2345     51515889 :   if (folded_casts)
    2346     51515889 :     *folded_casts = false;
    2347     53997127 :   while (1)
    2348              :     {
    2349     52756508 :       tmp = analyze_scalar_evolution (use_loop, ev, nowrap_bound);
    2350     52756508 :       ev = resolve_mixers (use_loop, tmp, folded_casts);
    2351              : 
    2352     52756508 :       if (use_loop == wrto_loop)
    2353              :         return ev;
    2354              : 
    2355              :       /* If the value of the use changes in the inner loop, we cannot express
    2356              :          its value in the outer loop (we might try to return interval chrec,
    2357              :          but we do not have a user for it anyway)  */
    2358      4401922 :       if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
    2359      4401922 :           || !val)
    2360      3161303 :         return chrec_dont_know;
    2361              : 
    2362      1240619 :       use_loop = loop_outer (use_loop);
    2363              :     }
    2364              : }
    2365              : 
    2366              : 
    2367              : /* Computes a hash function for database element ELT.  */
    2368              : 
    2369              : static inline hashval_t
    2370       458009 : hash_idx_scev_info (const void *elt_)
    2371              : {
    2372       458009 :   unsigned idx = ((size_t) elt_) - 2;
    2373       458009 :   return scev_info_hasher::hash (&global_cache->entries[idx]);
    2374              : }
    2375              : 
    2376              : /* Compares database elements E1 and E2.  */
    2377              : 
    2378              : static inline int
    2379     33170345 : eq_idx_scev_info (const void *e1, const void *e2)
    2380              : {
    2381     33170345 :   unsigned idx1 = ((size_t) e1) - 2;
    2382     33170345 :   return scev_info_hasher::equal (&global_cache->entries[idx1],
    2383     33170345 :                                   (const scev_info_str *) e2);
    2384              : }
    2385              : 
    2386              : /* Returns from CACHE the slot number of the cached chrec for NAME.  */
    2387              : 
    2388              : static unsigned
    2389     65651930 : get_instantiated_value_entry (instantiate_cache_type &cache,
    2390              :                               tree name, edge instantiate_below)
    2391              : {
    2392     65651930 :   if (!cache.map)
    2393              :     {
    2394     29817701 :       cache.map = htab_create (10, hash_idx_scev_info, eq_idx_scev_info, NULL);
    2395     29817701 :       cache.entries.create (10);
    2396              :     }
    2397              : 
    2398     65651930 :   scev_info_str e;
    2399     65651930 :   e.name_version = SSA_NAME_VERSION (name);
    2400     65651930 :   e.instantiated_below = instantiate_below->dest->index;
    2401     65651930 :   void **slot = htab_find_slot_with_hash (cache.map, &e,
    2402              :                                           scev_info_hasher::hash (&e), INSERT);
    2403     65651930 :   if (!*slot)
    2404              :     {
    2405     33901610 :       e.chrec = chrec_not_analyzed_yet;
    2406     33901610 :       *slot = (void *)(size_t)(cache.entries.length () + 2);
    2407     33901610 :       cache.entries.safe_push (e);
    2408              :     }
    2409              : 
    2410     65651930 :   return ((size_t)*slot) - 2;
    2411              : }
    2412              : 
    2413              : 
    2414              : /* Return the closed_loop_phi node for VAR.  If there is none, return
    2415              :    NULL_TREE.  */
    2416              : 
    2417              : static tree
    2418      1967503 : loop_closed_phi_def (tree var)
    2419              : {
    2420      1967503 :   class loop *loop;
    2421      1967503 :   edge exit;
    2422      1967503 :   gphi *phi;
    2423      1967503 :   gphi_iterator psi;
    2424              : 
    2425      1967503 :   if (var == NULL_TREE
    2426      1967503 :       || TREE_CODE (var) != SSA_NAME)
    2427              :     return NULL_TREE;
    2428              : 
    2429      1967503 :   loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
    2430      1967503 :   exit = single_exit (loop);
    2431      1967503 :   if (!exit)
    2432              :     return NULL_TREE;
    2433              : 
    2434      1527946 :   for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
    2435              :     {
    2436       869720 :       phi = psi.phi ();
    2437       869720 :       if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
    2438       223683 :         return PHI_RESULT (phi);
    2439              :     }
    2440              : 
    2441              :   return NULL_TREE;
    2442              : }
    2443              : 
    2444              : static tree instantiate_scev_r (edge, class loop *, class loop *,
    2445              :                                 tree, bool *, int);
    2446              : 
    2447              : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
    2448              :    and EVOLUTION_LOOP, that were left under a symbolic form.
    2449              : 
    2450              :    CHREC is an SSA_NAME to be instantiated.
    2451              : 
    2452              :    CACHE is the cache of already instantiated values.
    2453              : 
    2454              :    Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
    2455              :    conversions that may wrap in signed/pointer type are folded, as long
    2456              :    as the value of the chrec is preserved.  If FOLD_CONVERSIONS is NULL
    2457              :    then we don't do such fold.
    2458              : 
    2459              :    SIZE_EXPR is used for computing the size of the expression to be
    2460              :    instantiated, and to stop if it exceeds some limit.  */
    2461              : 
    2462              : static tree
    2463    114689962 : instantiate_scev_name (edge instantiate_below,
    2464              :                        class loop *evolution_loop, class loop *inner_loop,
    2465              :                        tree chrec,
    2466              :                        bool *fold_conversions,
    2467              :                        int size_expr)
    2468              : {
    2469    114689962 :   tree res;
    2470    114689962 :   class loop *def_loop;
    2471    114689962 :   basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
    2472              : 
    2473              :   /* A parameter, nothing to do.  */
    2474    114689962 :   if (!def_bb
    2475    114689962 :       || !dominated_by_p (CDI_DOMINATORS, def_bb, instantiate_below->dest))
    2476              :     return chrec;
    2477              : 
    2478              :   /* We cache the value of instantiated variable to avoid exponential
    2479              :      time complexity due to reevaluations.  We also store the convenient
    2480              :      value in the cache in order to prevent infinite recursion -- we do
    2481              :      not want to instantiate the SSA_NAME if it is in a mixer
    2482              :      structure.  This is used for avoiding the instantiation of
    2483              :      recursively defined functions, such as:
    2484              : 
    2485              :      | a_2 -> {0, +, 1, +, a_2}_1  */
    2486              : 
    2487     65651930 :   unsigned si = get_instantiated_value_entry (*global_cache,
    2488              :                                               chrec, instantiate_below);
    2489     65651930 :   if (global_cache->get (si) != chrec_not_analyzed_yet)
    2490              :     return global_cache->get (si);
    2491              : 
    2492              :   /* On recursion return chrec_dont_know.  */
    2493     33901610 :   global_cache->set (si, chrec_dont_know);
    2494              : 
    2495     33901610 :   def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
    2496              : 
    2497     33901610 :   if (! dominated_by_p (CDI_DOMINATORS,
    2498     33901610 :                         def_loop->header, instantiate_below->dest))
    2499              :     {
    2500       188631 :       gimple *def = SSA_NAME_DEF_STMT (chrec);
    2501       188631 :       if (gassign *ass = dyn_cast <gassign *> (def))
    2502              :         {
    2503       143390 :           switch (gimple_assign_rhs_class (ass))
    2504              :             {
    2505         4663 :             case GIMPLE_UNARY_RHS:
    2506         4663 :               {
    2507         4663 :                 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
    2508              :                                                inner_loop, gimple_assign_rhs1 (ass),
    2509              :                                                fold_conversions, size_expr);
    2510         4663 :                 if (op0 == chrec_dont_know)
    2511              :                   return chrec_dont_know;
    2512         1199 :                 res = fold_build1 (gimple_assign_rhs_code (ass),
    2513              :                                    TREE_TYPE (chrec), op0);
    2514         1199 :                 break;
    2515              :               }
    2516        51783 :             case GIMPLE_BINARY_RHS:
    2517        51783 :               {
    2518        51783 :                 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
    2519              :                                                inner_loop, gimple_assign_rhs1 (ass),
    2520              :                                                fold_conversions, size_expr);
    2521        51783 :                 if (op0 == chrec_dont_know)
    2522              :                   return chrec_dont_know;
    2523        11542 :                 tree op1 = instantiate_scev_r (instantiate_below, evolution_loop,
    2524              :                                                inner_loop, gimple_assign_rhs2 (ass),
    2525              :                                                fold_conversions, size_expr);
    2526         5771 :                 if (op1 == chrec_dont_know)
    2527              :                   return chrec_dont_know;
    2528         1849 :                 res = fold_build2 (gimple_assign_rhs_code (ass),
    2529              :                                    TREE_TYPE (chrec), op0, op1);
    2530         1849 :                 break;
    2531              :               }
    2532        86944 :             default:
    2533        86944 :               res = chrec_dont_know;
    2534              :             }
    2535              :         }
    2536              :       else
    2537        45241 :         res = chrec_dont_know;
    2538       135233 :       global_cache->set (si, res);
    2539       135233 :       return res;
    2540              :     }
    2541              : 
    2542              :   /* If the analysis yields a parametric chrec, instantiate the
    2543              :      result again.  */
    2544     33712979 :   res = analyze_scalar_evolution (def_loop, chrec);
    2545              : 
    2546              :   /* Don't instantiate default definitions.  */
    2547     33712979 :   if (TREE_CODE (res) == SSA_NAME
    2548     33712979 :       && SSA_NAME_IS_DEFAULT_DEF (res))
    2549              :     ;
    2550              : 
    2551              :   /* Don't instantiate loop-closed-ssa phi nodes.  */
    2552     33696599 :   else if (TREE_CODE (res) == SSA_NAME
    2553     99354069 :            && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
    2554     32829122 :            > loop_depth (def_loop))
    2555              :     {
    2556      1993090 :       if (res == chrec)
    2557      1967503 :         res = loop_closed_phi_def (chrec);
    2558              :       else
    2559              :         res = chrec;
    2560              : 
    2561              :       /* When there is no loop_closed_phi_def, it means that the
    2562              :          variable is not used after the loop: try to still compute the
    2563              :          value of the variable when exiting the loop.  */
    2564      1993090 :       if (res == NULL_TREE)
    2565              :         {
    2566      1743820 :           loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
    2567      1743820 :           res = analyze_scalar_evolution (loop, chrec);
    2568      1743820 :           res = compute_overall_effect_of_inner_loop (loop, res);
    2569      1743820 :           res = instantiate_scev_r (instantiate_below, evolution_loop,
    2570              :                                     inner_loop, res,
    2571              :                                     fold_conversions, size_expr);
    2572              :         }
    2573       249270 :       else if (dominated_by_p (CDI_DOMINATORS,
    2574       249270 :                                 gimple_bb (SSA_NAME_DEF_STMT (res)),
    2575       249270 :                                 instantiate_below->dest))
    2576       249270 :         res = chrec_dont_know;
    2577              :     }
    2578              : 
    2579     31703509 :   else if (res != chrec_dont_know)
    2580              :     {
    2581     31703509 :       if (inner_loop
    2582      1184269 :           && def_bb->loop_father != inner_loop
    2583     32318541 :           && !flow_loop_nested_p (def_bb->loop_father, inner_loop))
    2584              :         /* ???  We could try to compute the overall effect of the loop here.  */
    2585          319 :         res = chrec_dont_know;
    2586              :       else
    2587     31703190 :         res = instantiate_scev_r (instantiate_below, evolution_loop,
    2588              :                                   inner_loop, res,
    2589              :                                   fold_conversions, size_expr);
    2590              :     }
    2591              : 
    2592              :   /* Store the correct value to the cache.  */
    2593     33712979 :   global_cache->set (si, res);
    2594     33712979 :   return res;
    2595              : }
    2596              : 
    2597              : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
    2598              :    and EVOLUTION_LOOP, that were left under a symbolic form.
    2599              : 
    2600              :    CHREC is a polynomial chain of recurrence to be instantiated.
    2601              : 
    2602              :    CACHE is the cache of already instantiated values.
    2603              : 
    2604              :    Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
    2605              :    conversions that may wrap in signed/pointer type are folded, as long
    2606              :    as the value of the chrec is preserved.  If FOLD_CONVERSIONS is NULL
    2607              :    then we don't do such fold.
    2608              : 
    2609              :    SIZE_EXPR is used for computing the size of the expression to be
    2610              :    instantiated, and to stop if it exceeds some limit.  */
    2611              : 
    2612              : static tree
    2613     62634984 : instantiate_scev_poly (edge instantiate_below,
    2614              :                        class loop *evolution_loop, class loop *,
    2615              :                        tree chrec, bool *fold_conversions, int size_expr)
    2616              : {
    2617     62634984 :   tree op1;
    2618    125269968 :   tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
    2619              :                                  get_chrec_loop (chrec),
    2620     62634984 :                                  CHREC_LEFT (chrec), fold_conversions,
    2621              :                                  size_expr);
    2622     62634984 :   if (op0 == chrec_dont_know)
    2623              :     return chrec_dont_know;
    2624              : 
    2625    124828014 :   op1 = instantiate_scev_r (instantiate_below, evolution_loop,
    2626              :                             get_chrec_loop (chrec),
    2627     62414007 :                             CHREC_RIGHT (chrec), fold_conversions,
    2628              :                             size_expr);
    2629     62414007 :   if (op1 == chrec_dont_know)
    2630              :     return chrec_dont_know;
    2631              : 
    2632     61730200 :   if (CHREC_LEFT (chrec) != op0
    2633     61730200 :       || CHREC_RIGHT (chrec) != op1)
    2634              :     {
    2635      8162175 :       op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
    2636      8162175 :       chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
    2637              :     }
    2638              : 
    2639              :   return chrec;
    2640              : }
    2641              : 
    2642              : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
    2643              :    and EVOLUTION_LOOP, that were left under a symbolic form.
    2644              : 
    2645              :    "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
    2646              : 
    2647              :    CACHE is the cache of already instantiated values.
    2648              : 
    2649              :    Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
    2650              :    conversions that may wrap in signed/pointer type are folded, as long
    2651              :    as the value of the chrec is preserved.  If FOLD_CONVERSIONS is NULL
    2652              :    then we don't do such fold.
    2653              : 
    2654              :    SIZE_EXPR is used for computing the size of the expression to be
    2655              :    instantiated, and to stop if it exceeds some limit.  */
    2656              : 
    2657              : static tree
    2658     24864603 : instantiate_scev_binary (edge instantiate_below,
    2659              :                          class loop *evolution_loop, class loop *inner_loop,
    2660              :                          tree chrec, enum tree_code code,
    2661              :                          tree type, tree c0, tree c1,
    2662              :                          bool *fold_conversions, int size_expr)
    2663              : {
    2664     24864603 :   tree op1;
    2665     24864603 :   tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
    2666              :                                  c0, fold_conversions, size_expr);
    2667     24864603 :   if (op0 == chrec_dont_know)
    2668              :     return chrec_dont_know;
    2669              : 
    2670              :   /* While we eventually compute the same op1 if c0 == c1 the process
    2671              :      of doing this is expensive so the following short-cut prevents
    2672              :      exponential compile-time behavior.  */
    2673     24502831 :   if (c0 != c1)
    2674              :     {
    2675     24481597 :       op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
    2676              :                                 c1, fold_conversions, size_expr);
    2677     24481597 :       if (op1 == chrec_dont_know)
    2678              :         return chrec_dont_know;
    2679              :     }
    2680              :   else
    2681              :     op1 = op0;
    2682              : 
    2683     24433395 :   if (c0 != op0
    2684     24433395 :       || c1 != op1)
    2685              :     {
    2686     14100350 :       op0 = chrec_convert (type, op0, NULL);
    2687     14100350 :       op1 = chrec_convert_rhs (type, op1, NULL);
    2688              : 
    2689     14100350 :       switch (code)
    2690              :         {
    2691      8240296 :         case POINTER_PLUS_EXPR:
    2692      8240296 :         case PLUS_EXPR:
    2693      8240296 :           return chrec_fold_plus (type, op0, op1);
    2694              : 
    2695       909565 :         case MINUS_EXPR:
    2696       909565 :           return chrec_fold_minus (type, op0, op1);
    2697              : 
    2698      4950489 :         case MULT_EXPR:
    2699      4950489 :           return chrec_fold_multiply (type, op0, op1);
    2700              : 
    2701            0 :         default:
    2702            0 :           gcc_unreachable ();
    2703              :         }
    2704              :     }
    2705              : 
    2706     10333045 :   return chrec ? chrec : fold_build2 (code, type, c0, c1);
    2707              : }
    2708              : 
    2709              : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
    2710              :    and EVOLUTION_LOOP, that were left under a symbolic form.
    2711              : 
    2712              :    "CHREC" that stands for a convert expression "(TYPE) OP" is to be
    2713              :    instantiated.
    2714              : 
    2715              :    CACHE is the cache of already instantiated values.
    2716              : 
    2717              :    Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
    2718              :    conversions that may wrap in signed/pointer type are folded, as long
    2719              :    as the value of the chrec is preserved.  If FOLD_CONVERSIONS is NULL
    2720              :    then we don't do such fold.
    2721              : 
    2722              :    SIZE_EXPR is used for computing the size of the expression to be
    2723              :    instantiated, and to stop if it exceeds some limit.  */
    2724              : 
    2725              : static tree
    2726     25728428 : instantiate_scev_convert (edge instantiate_below,
    2727              :                           class loop *evolution_loop, class loop *inner_loop,
    2728              :                           tree chrec, tree type, tree op,
    2729              :                           bool *fold_conversions, int size_expr)
    2730              : {
    2731     25728428 :   tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
    2732              :                                  inner_loop, op,
    2733              :                                  fold_conversions, size_expr);
    2734              : 
    2735     25728428 :   if (op0 == chrec_dont_know)
    2736              :     return chrec_dont_know;
    2737              : 
    2738     20381501 :   if (fold_conversions)
    2739              :     {
    2740      7899264 :       tree tmp = chrec_convert_aggressive (type, op0, fold_conversions);
    2741      7899264 :       if (tmp)
    2742              :         return tmp;
    2743              : 
    2744              :       /* If we used chrec_convert_aggressive, we can no longer assume that
    2745              :          signed chrecs do not overflow, as chrec_convert does, so avoid
    2746              :          calling it in that case.  */
    2747      7358447 :       if (*fold_conversions)
    2748              :         {
    2749        13845 :           if (chrec && op0 == op)
    2750              :             return chrec;
    2751              : 
    2752        13845 :           return fold_convert (type, op0);
    2753              :         }
    2754              :     }
    2755              : 
    2756     19826839 :   return chrec_convert (type, op0, NULL);
    2757              : }
    2758              : 
    2759              : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
    2760              :    and EVOLUTION_LOOP, that were left under a symbolic form.
    2761              : 
    2762              :    CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
    2763              :    Handle ~X as -1 - X.
    2764              :    Handle -X as -1 * X.
    2765              : 
    2766              :    CACHE is the cache of already instantiated values.
    2767              : 
    2768              :    Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
    2769              :    conversions that may wrap in signed/pointer type are folded, as long
    2770              :    as the value of the chrec is preserved.  If FOLD_CONVERSIONS is NULL
    2771              :    then we don't do such fold.
    2772              : 
    2773              :    SIZE_EXPR is used for computing the size of the expression to be
    2774              :    instantiated, and to stop if it exceeds some limit.  */
    2775              : 
    2776              : static tree
    2777       289612 : instantiate_scev_not (edge instantiate_below,
    2778              :                       class loop *evolution_loop, class loop *inner_loop,
    2779              :                       tree chrec,
    2780              :                       enum tree_code code, tree type, tree op,
    2781              :                       bool *fold_conversions, int size_expr)
    2782              : {
    2783       289612 :   tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
    2784              :                                  inner_loop, op,
    2785              :                                  fold_conversions, size_expr);
    2786              : 
    2787       289612 :   if (op0 == chrec_dont_know)
    2788              :     return chrec_dont_know;
    2789              : 
    2790       221745 :   if (op != op0)
    2791              :     {
    2792       156306 :       op0 = chrec_convert (type, op0, NULL);
    2793              : 
    2794       156306 :       switch (code)
    2795              :         {
    2796         2387 :         case BIT_NOT_EXPR:
    2797         2387 :           return chrec_fold_minus
    2798         2387 :             (type, fold_convert (type, integer_minus_one_node), op0);
    2799              : 
    2800       153919 :         case NEGATE_EXPR:
    2801       153919 :           return chrec_fold_multiply
    2802       153919 :             (type, fold_convert (type, integer_minus_one_node), op0);
    2803              : 
    2804            0 :         default:
    2805            0 :           gcc_unreachable ();
    2806              :         }
    2807              :     }
    2808              : 
    2809        65439 :   return chrec ? chrec : fold_build1 (code, type, op0);
    2810              : }
    2811              : 
    2812              : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
    2813              :    and EVOLUTION_LOOP, that were left under a symbolic form.
    2814              : 
    2815              :    CHREC is the scalar evolution to instantiate.
    2816              : 
    2817              :    CACHE is the cache of already instantiated values.
    2818              : 
    2819              :    Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
    2820              :    conversions that may wrap in signed/pointer type are folded, as long
    2821              :    as the value of the chrec is preserved.  If FOLD_CONVERSIONS is NULL
    2822              :    then we don't do such fold.
    2823              : 
    2824              :    SIZE_EXPR is used for computing the size of the expression to be
    2825              :    instantiated, and to stop if it exceeds some limit.  */
    2826              : 
    2827              : static tree
    2828    377927696 : instantiate_scev_r (edge instantiate_below,
    2829              :                     class loop *evolution_loop, class loop *inner_loop,
    2830              :                     tree chrec,
    2831              :                     bool *fold_conversions, int size_expr)
    2832              : {
    2833              :   /* Give up if the expression is larger than the MAX that we allow.  */
    2834    377927696 :   if (size_expr++ > param_scev_max_expr_size)
    2835           11 :     return chrec_dont_know;
    2836              : 
    2837    377927685 :   if (chrec == NULL_TREE
    2838    753744866 :       || automatically_generated_chrec_p (chrec)
    2839    753744855 :       || is_gimple_min_invariant (chrec))
    2840              :     return chrec;
    2841              : 
    2842    228946717 :   switch (TREE_CODE (chrec))
    2843              :     {
    2844    114689962 :     case SSA_NAME:
    2845    114689962 :       return instantiate_scev_name (instantiate_below, evolution_loop,
    2846              :                                     inner_loop, chrec,
    2847    114689962 :                                     fold_conversions, size_expr);
    2848              : 
    2849     62634984 :     case POLYNOMIAL_CHREC:
    2850     62634984 :       return instantiate_scev_poly (instantiate_below, evolution_loop,
    2851              :                                     inner_loop, chrec,
    2852     62634984 :                                     fold_conversions, size_expr);
    2853              : 
    2854     24864603 :     case POINTER_PLUS_EXPR:
    2855     24864603 :     case PLUS_EXPR:
    2856     24864603 :     case MINUS_EXPR:
    2857     24864603 :     case MULT_EXPR:
    2858     24864603 :       return instantiate_scev_binary (instantiate_below, evolution_loop,
    2859              :                                       inner_loop, chrec,
    2860              :                                       TREE_CODE (chrec), chrec_type (chrec),
    2861     24864603 :                                       TREE_OPERAND (chrec, 0),
    2862     24864603 :                                       TREE_OPERAND (chrec, 1),
    2863     24864603 :                                       fold_conversions, size_expr);
    2864              : 
    2865     25728428 :     CASE_CONVERT:
    2866     25728428 :       return instantiate_scev_convert (instantiate_below, evolution_loop,
    2867              :                                        inner_loop, chrec,
    2868     25728428 :                                        TREE_TYPE (chrec), TREE_OPERAND (chrec, 0),
    2869     25728428 :                                        fold_conversions, size_expr);
    2870              : 
    2871       289612 :     case NEGATE_EXPR:
    2872       289612 :     case BIT_NOT_EXPR:
    2873       289612 :       return instantiate_scev_not (instantiate_below, evolution_loop,
    2874              :                                    inner_loop, chrec,
    2875       289612 :                                    TREE_CODE (chrec), TREE_TYPE (chrec),
    2876       289612 :                                    TREE_OPERAND (chrec, 0),
    2877       289612 :                                    fold_conversions, size_expr);
    2878              : 
    2879            0 :     case ADDR_EXPR:
    2880            0 :       if (is_gimple_min_invariant (chrec))
    2881              :         return chrec;
    2882              :       /* Fallthru.  */
    2883            0 :     case SCEV_NOT_KNOWN:
    2884            0 :       return chrec_dont_know;
    2885              : 
    2886            0 :     case SCEV_KNOWN:
    2887            0 :       return chrec_known;
    2888              : 
    2889       739128 :     default:
    2890       739128 :       if (CONSTANT_CLASS_P (chrec))
    2891              :         return chrec;
    2892       739128 :       return chrec_dont_know;
    2893              :     }
    2894              : }
    2895              : 
    2896              : /* Analyze all the parameters of the chrec that were left under a
    2897              :    symbolic form.  INSTANTIATE_BELOW is the basic block that stops the
    2898              :    recursive instantiation of parameters: a parameter is a variable
    2899              :    that is defined in a basic block that dominates INSTANTIATE_BELOW or
    2900              :    a function parameter.  */
    2901              : 
    2902              : tree
    2903     91248730 : instantiate_scev (edge instantiate_below, class loop *evolution_loop,
    2904              :                   tree chrec)
    2905              : {
    2906     91248730 :   tree res;
    2907              : 
    2908     91248730 :   if (dump_file && (dump_flags & TDF_SCEV))
    2909              :     {
    2910           20 :       fprintf (dump_file, "(instantiate_scev \n");
    2911           20 :       fprintf (dump_file, "  (instantiate_below = %d -> %d)\n",
    2912           20 :                instantiate_below->src->index, instantiate_below->dest->index);
    2913           20 :       if (evolution_loop)
    2914           20 :         fprintf (dump_file, "  (evolution_loop = %d)\n", evolution_loop->num);
    2915           20 :       fprintf (dump_file, "  (chrec = ");
    2916           20 :       print_generic_expr (dump_file, chrec);
    2917           20 :       fprintf (dump_file, ")\n");
    2918              :     }
    2919              : 
    2920     91248730 :   bool destr = false;
    2921     91248730 :   if (!global_cache)
    2922              :     {
    2923     38799751 :       global_cache = new instantiate_cache_type;
    2924     38799751 :       destr = true;
    2925              :     }
    2926              : 
    2927     91248730 :   res = instantiate_scev_r (instantiate_below, evolution_loop,
    2928              :                             NULL, chrec, NULL, 0);
    2929              : 
    2930     91248730 :   if (destr)
    2931              :     {
    2932     38799751 :       delete global_cache;
    2933     38799751 :       global_cache = NULL;
    2934              :     }
    2935              : 
    2936     91248730 :   if (dump_file && (dump_flags & TDF_SCEV))
    2937              :     {
    2938           20 :       fprintf (dump_file, "  (res = ");
    2939           20 :       print_generic_expr (dump_file, res);
    2940           20 :       fprintf (dump_file, "))\n");
    2941              :     }
    2942              : 
    2943     91248730 :   return res;
    2944              : }
    2945              : 
    2946              : /* Similar to instantiate_parameters, but does not introduce the
    2947              :    evolutions in outer loops for LOOP invariants in CHREC, and does not
    2948              :    care about causing overflows, as long as they do not affect value
    2949              :    of an expression.  */
    2950              : 
    2951              : tree
    2952     52756508 : resolve_mixers (class loop *loop, tree chrec, bool *folded_casts)
    2953              : {
    2954     52756508 :   bool destr = false;
    2955     52756508 :   bool fold_conversions = false;
    2956     52756508 :   if (!global_cache)
    2957              :     {
    2958     51900248 :       global_cache = new instantiate_cache_type;
    2959     51900248 :       destr = true;
    2960              :     }
    2961              : 
    2962     52756508 :   tree ret = instantiate_scev_r (loop_preheader_edge (loop), loop, NULL,
    2963              :                                  chrec, &fold_conversions, 0);
    2964              : 
    2965     52756508 :   if (folded_casts && !*folded_casts)
    2966     52756508 :     *folded_casts = fold_conversions;
    2967              : 
    2968     52756508 :   if (destr)
    2969              :     {
    2970     51900248 :       delete global_cache;
    2971     51900248 :       global_cache = NULL;
    2972              :     }
    2973              : 
    2974     52756508 :   return ret;
    2975              : }
    2976              : 
    2977              : /* Entry point for the analysis of the number of iterations pass.
    2978              :    This function tries to safely approximate the number of iterations
    2979              :    the loop will run.  When this property is not decidable at compile
    2980              :    time, the result is chrec_dont_know.  Otherwise the result is a
    2981              :    scalar or a symbolic parameter.  When the number of iterations may
    2982              :    be equal to zero and the property cannot be determined at compile
    2983              :    time, the result is a COND_EXPR that represents in a symbolic form
    2984              :    the conditions under which the number of iterations is not zero.
    2985              : 
    2986              :    Example of analysis: suppose that the loop has an exit condition:
    2987              : 
    2988              :    "if (b > 49) goto end_loop;"
    2989              : 
    2990              :    and that in a previous analysis we have determined that the
    2991              :    variable 'b' has an evolution function:
    2992              : 
    2993              :    "EF = {23, +, 5}_2".
    2994              : 
    2995              :    When we evaluate the function at the point 5, i.e. the value of the
    2996              :    variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
    2997              :    and EF (6) = 53.  In this case the value of 'b' on exit is '53' and
    2998              :    the loop body has been executed 6 times.  */
    2999              : 
    3000              : tree
    3001     10455855 : number_of_latch_executions (class loop *loop)
    3002              : {
    3003     10455855 :   edge exit;
    3004     10455855 :   class tree_niter_desc niter_desc;
    3005     10455855 :   tree may_be_zero;
    3006     10455855 :   tree res;
    3007              : 
    3008              :   /* Determine whether the number of iterations in loop has already
    3009              :      been computed.  */
    3010     10455855 :   res = loop->nb_iterations;
    3011     10455855 :   if (res)
    3012              :     return res;
    3013              : 
    3014      7091438 :   may_be_zero = NULL_TREE;
    3015              : 
    3016      7091438 :   if (dump_file && (dump_flags & TDF_SCEV))
    3017            2 :     fprintf (dump_file, "(number_of_iterations_in_loop = \n");
    3018              : 
    3019      7091438 :   res = chrec_dont_know;
    3020      7091438 :   exit = single_exit (loop);
    3021              : 
    3022      7091438 :   if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
    3023              :     {
    3024      3563552 :       may_be_zero = niter_desc.may_be_zero;
    3025      3563552 :       res = niter_desc.niter;
    3026              :     }
    3027              : 
    3028      7091438 :   if (res == chrec_dont_know
    3029      3563552 :       || !may_be_zero
    3030     10654990 :       || integer_zerop (may_be_zero))
    3031              :     ;
    3032       562108 :   else if (integer_nonzerop (may_be_zero))
    3033           27 :     res = build_int_cst (TREE_TYPE (res), 0);
    3034              : 
    3035       562081 :   else if (COMPARISON_CLASS_P (may_be_zero))
    3036       562081 :     res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
    3037              :                        build_int_cst (TREE_TYPE (res), 0), res);
    3038              :   else
    3039            0 :     res = chrec_dont_know;
    3040              : 
    3041      7091438 :   if (dump_file && (dump_flags & TDF_SCEV))
    3042              :     {
    3043            2 :       fprintf (dump_file, "  (set_nb_iterations_in_loop = ");
    3044            2 :       print_generic_expr (dump_file, res);
    3045            2 :       fprintf (dump_file, "))\n");
    3046              :     }
    3047              : 
    3048      7091438 :   loop->nb_iterations = res;
    3049      7091438 :   return res;
    3050     10455855 : }
    3051              : 
    3052              : 
    3053              : /* Counters for the stats.  */
    3054              : 
    3055              : struct chrec_stats
    3056              : {
    3057              :   unsigned nb_chrecs;
    3058              :   unsigned nb_affine;
    3059              :   unsigned nb_affine_multivar;
    3060              :   unsigned nb_higher_poly;
    3061              :   unsigned nb_chrec_dont_know;
    3062              :   unsigned nb_undetermined;
    3063              : };
    3064              : 
    3065              : /* Reset the counters.  */
    3066              : 
    3067              : static inline void
    3068            0 : reset_chrecs_counters (struct chrec_stats *stats)
    3069              : {
    3070            0 :   stats->nb_chrecs = 0;
    3071            0 :   stats->nb_affine = 0;
    3072            0 :   stats->nb_affine_multivar = 0;
    3073            0 :   stats->nb_higher_poly = 0;
    3074            0 :   stats->nb_chrec_dont_know = 0;
    3075            0 :   stats->nb_undetermined = 0;
    3076              : }
    3077              : 
    3078              : /* Dump the contents of a CHREC_STATS structure.  */
    3079              : 
    3080              : static void
    3081            0 : dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
    3082              : {
    3083            0 :   fprintf (file, "\n(\n");
    3084            0 :   fprintf (file, "-----------------------------------------\n");
    3085            0 :   fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
    3086            0 :   fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
    3087            0 :   fprintf (file, "%d\tdegree greater than 2 polynomials\n",
    3088              :            stats->nb_higher_poly);
    3089            0 :   fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
    3090            0 :   fprintf (file, "-----------------------------------------\n");
    3091            0 :   fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
    3092            0 :   fprintf (file, "%d\twith undetermined coefficients\n",
    3093              :            stats->nb_undetermined);
    3094            0 :   fprintf (file, "-----------------------------------------\n");
    3095            0 :   fprintf (file, "%d\tchrecs in the scev database\n",
    3096            0 :            (int) scalar_evolution_info->elements ());
    3097            0 :   fprintf (file, "%d\tchrecs in the nowrap scev database\n",
    3098            0 :            (int) scalar_evolution_nowrap_info->elements ());
    3099            0 :   fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
    3100            0 :   fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
    3101            0 :   fprintf (file, "-----------------------------------------\n");
    3102            0 :   fprintf (file, ")\n\n");
    3103            0 : }
    3104              : 
    3105              : /* Gather statistics about CHREC.  */
    3106              : 
    3107              : static void
    3108            0 : gather_chrec_stats (tree chrec, struct chrec_stats *stats)
    3109              : {
    3110            0 :   if (dump_file && (dump_flags & TDF_STATS))
    3111              :     {
    3112            0 :       fprintf (dump_file, "(classify_chrec ");
    3113            0 :       print_generic_expr (dump_file, chrec);
    3114            0 :       fprintf (dump_file, "\n");
    3115              :     }
    3116              : 
    3117            0 :   stats->nb_chrecs++;
    3118              : 
    3119            0 :   if (chrec == NULL_TREE)
    3120              :     {
    3121            0 :       stats->nb_undetermined++;
    3122            0 :       return;
    3123              :     }
    3124              : 
    3125            0 :   switch (TREE_CODE (chrec))
    3126              :     {
    3127            0 :     case POLYNOMIAL_CHREC:
    3128            0 :       if (evolution_function_is_affine_p (chrec))
    3129              :         {
    3130            0 :           if (dump_file && (dump_flags & TDF_STATS))
    3131            0 :             fprintf (dump_file, "  affine_univariate\n");
    3132            0 :           stats->nb_affine++;
    3133              :         }
    3134            0 :       else if (evolution_function_is_affine_multivariate_p (chrec, 0))
    3135              :         {
    3136            0 :           if (dump_file && (dump_flags & TDF_STATS))
    3137            0 :             fprintf (dump_file, "  affine_multivariate\n");
    3138            0 :           stats->nb_affine_multivar++;
    3139              :         }
    3140              :       else
    3141              :         {
    3142            0 :           if (dump_file && (dump_flags & TDF_STATS))
    3143            0 :             fprintf (dump_file, "  higher_degree_polynomial\n");
    3144            0 :           stats->nb_higher_poly++;
    3145              :         }
    3146              : 
    3147              :       break;
    3148              : 
    3149              :     default:
    3150              :       break;
    3151              :     }
    3152              : 
    3153            0 :   if (chrec_contains_undetermined (chrec))
    3154              :     {
    3155            0 :       if (dump_file && (dump_flags & TDF_STATS))
    3156            0 :         fprintf (dump_file, "  undetermined\n");
    3157            0 :       stats->nb_undetermined++;
    3158              :     }
    3159              : 
    3160            0 :   if (dump_file && (dump_flags & TDF_STATS))
    3161            0 :     fprintf (dump_file, ")\n");
    3162              : }
    3163              : 
    3164              : /* Classify the chrecs of the whole database.  */
    3165              : 
    3166              : void
    3167            0 : gather_stats_on_scev_database (void)
    3168              : {
    3169            0 :   struct chrec_stats stats;
    3170              : 
    3171            0 :   if (!dump_file)
    3172            0 :     return;
    3173              : 
    3174            0 :   reset_chrecs_counters (&stats);
    3175              : 
    3176            0 :   hash_table<scev_info_hasher>::iterator iter;
    3177            0 :   scev_info_str *elt;
    3178            0 :   FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info, elt, scev_info_str *,
    3179              :                                iter)
    3180            0 :     gather_chrec_stats (elt->chrec, &stats);
    3181            0 :   FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_nowrap_info, elt,
    3182              :                                scev_info_str *, iter)
    3183            0 :     gather_chrec_stats (elt->chrec, &stats);
    3184              : 
    3185            0 :   dump_chrecs_stats (dump_file, &stats);
    3186              : }
    3187              : 
    3188              : 
    3189              : /* Initialize the analysis of scalar evolutions for LOOPS.  */
    3190              : 
    3191              : void
    3192     15775837 : scev_initialize (void)
    3193              : {
    3194     15775837 :   gcc_assert (! scev_initialized_p ()
    3195              :               && loops_state_satisfies_p (cfun, LOOPS_NORMAL));
    3196              : 
    3197     15775837 :   scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100);
    3198     15775837 :   scalar_evolution_nowrap_info = hash_table<scev_info_hasher>::create_ggc (100);
    3199              : 
    3200     57961208 :   for (auto loop : loops_list (cfun, 0))
    3201     10633697 :     loop->nb_iterations = NULL_TREE;
    3202     15775837 : }
    3203              : 
    3204              : /* Return true if SCEV is initialized.  */
    3205              : 
    3206              : bool
    3207     99605409 : scev_initialized_p (void)
    3208              : {
    3209     99605409 :   return scalar_evolution_info != NULL && scalar_evolution_nowrap_info != NULL;
    3210              : }
    3211              : 
    3212              : /* Cleans up the information cached by the scalar evolutions analysis
    3213              :    in the hash table.  */
    3214              : 
    3215              : void
    3216     24762830 : scev_reset_htab (void)
    3217              : {
    3218     24762830 :   if (!scalar_evolution_info && !scalar_evolution_nowrap_info)
    3219              :     return;
    3220              : 
    3221      6331591 :   if (scalar_evolution_info)
    3222      6331591 :     scalar_evolution_info->empty ();
    3223      6331591 :   if (scalar_evolution_nowrap_info)
    3224      6331591 :     scalar_evolution_nowrap_info->empty ();
    3225              : }
    3226              : 
    3227              : /* Cleans up the information cached by the scalar evolutions analysis
    3228              :    in the hash table and in the loop->nb_iterations.  */
    3229              : 
    3230              : void
    3231     13385209 : scev_reset (void)
    3232              : {
    3233     13385209 :   scev_reset_htab ();
    3234              : 
    3235     65999795 :   for (auto loop : loops_list (cfun, 0))
    3236     25844168 :     loop->nb_iterations = NULL_TREE;
    3237     13385209 : }
    3238              : 
    3239              : /* Return true if the IV calculation in TYPE can overflow based on the knowledge
    3240              :    of the upper bound on the number of iterations of LOOP, the BASE and STEP
    3241              :    of IV.
    3242              : 
    3243              :    We do not use information whether TYPE can overflow so it is safe to
    3244              :    use this test even for derived IVs not computed every iteration or
    3245              :    hypothetical IVs to be inserted into code.  */
    3246              : 
    3247              : bool
    3248     15489004 : iv_can_overflow_p (class loop *loop, tree type, tree base, tree step)
    3249              : {
    3250     15489004 :   widest_int nit;
    3251     15489004 :   wide_int base_min, base_max, step_min, step_max, type_min, type_max;
    3252     15489004 :   signop sgn = TYPE_SIGN (type);
    3253     15489004 :   int_range_max r;
    3254              : 
    3255     15489004 :   if (integer_zerop (step))
    3256              :     return false;
    3257              : 
    3258     30974500 :   if (!INTEGRAL_TYPE_P (TREE_TYPE (base))
    3259     28779408 :       || !get_range_query (cfun)->range_of_expr (r, base)
    3260     14389704 :       || r.varying_p ()
    3261     28398279 :       || r.undefined_p ())
    3262              :     return true;
    3263              : 
    3264     12907042 :   base_min = r.lower_bound ();
    3265     12907042 :   base_max = r.upper_bound ();
    3266              : 
    3267     25810689 :   if (!INTEGRAL_TYPE_P (TREE_TYPE (step))
    3268     25814084 :       || !get_range_query (cfun)->range_of_expr (r, step)
    3269     12907042 :       || r.varying_p ()
    3270     25742194 :       || r.undefined_p ())
    3271              :     return true;
    3272              : 
    3273     12835152 :   step_min = r.lower_bound ();
    3274     12835152 :   step_max = r.upper_bound ();
    3275              : 
    3276     12835152 :   if (!get_max_loop_iterations (loop, &nit))
    3277              :     return true;
    3278              : 
    3279     12157223 :   type_min = wi::min_value (type);
    3280     12157223 :   type_max = wi::max_value (type);
    3281              : 
    3282              :   /* Just sanity check that we don't see values out of the range of the type.
    3283              :      In this case the arithmetics below would overflow.  */
    3284     12157223 :   gcc_checking_assert (wi::ge_p (base_min, type_min, sgn)
    3285              :                        && wi::le_p (base_max, type_max, sgn));
    3286              : 
    3287              :   /* Account the possible increment in the last ieration.  */
    3288     12157223 :   wi::overflow_type overflow = wi::OVF_NONE;
    3289     12157223 :   nit = wi::add (nit, 1, SIGNED, &overflow);
    3290     12157223 :   if (overflow)
    3291              :     return true;
    3292              : 
    3293              :   /* NIT is typeless and can exceed the precision of the type.  In this case
    3294              :      overflow is always possible, because we know STEP is non-zero.  */
    3295     12157223 :   if (wi::min_precision (nit, UNSIGNED) > TYPE_PRECISION (type))
    3296              :     return true;
    3297     11919915 :   wide_int nit2 = wide_int::from (nit, TYPE_PRECISION (type), UNSIGNED);
    3298              : 
    3299              :   /* If step can be positive, check that nit*step <= type_max-base.
    3300              :      This can be done by unsigned arithmetic and we only need to watch overflow
    3301              :      in the multiplication. The right hand side can always be represented in
    3302              :      the type.  */
    3303     11919915 :   if (sgn == UNSIGNED || !wi::neg_p (step_max))
    3304              :     {
    3305     11873703 :       wi::overflow_type overflow = wi::OVF_NONE;
    3306     11873703 :       if (wi::gtu_p (wi::mul (step_max, nit2, UNSIGNED, &overflow),
    3307     23747406 :                      type_max - base_max)
    3308     23747406 :           || overflow)
    3309      6006140 :         return true;
    3310              :     }
    3311              :   /* If step can be negative, check that nit*(-step) <= base_min-type_min.  */
    3312      5913775 :   if (sgn == SIGNED && wi::neg_p (step_min))
    3313              :     {
    3314        46527 :       wi::overflow_type overflow, overflow2;
    3315        46527 :       overflow = overflow2 = wi::OVF_NONE;
    3316        93054 :       if (wi::gtu_p (wi::mul (wi::neg (step_min, &overflow2),
    3317              :                      nit2, UNSIGNED, &overflow),
    3318        93054 :                      base_min - type_min)
    3319        93054 :           || overflow || overflow2)
    3320        15087 :         return true;
    3321              :     }
    3322              : 
    3323              :   return false;
    3324     15489004 : }
    3325              : 
    3326              : /* Given EV with form of "(type) {inner_base, inner_step}_loop", this
    3327              :    function tries to derive condition under which it can be simplified
    3328              :    into "{(type)inner_base, (type)inner_step}_loop".  The condition is
    3329              :    the maximum number that inner iv can iterate.  */
    3330              : 
    3331              : static tree
    3332        38932 : derive_simple_iv_with_niters (tree ev, tree *niters)
    3333              : {
    3334        38932 :   if (!CONVERT_EXPR_P (ev))
    3335              :     return ev;
    3336              : 
    3337        38932 :   tree inner_ev = TREE_OPERAND (ev, 0);
    3338        38932 :   if (TREE_CODE (inner_ev) != POLYNOMIAL_CHREC)
    3339              :     return ev;
    3340              : 
    3341        38932 :   tree init = CHREC_LEFT (inner_ev);
    3342        38932 :   tree step = CHREC_RIGHT (inner_ev);
    3343        38932 :   if (TREE_CODE (init) != INTEGER_CST
    3344        38932 :       || TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
    3345              :     return ev;
    3346              : 
    3347        30474 :   tree type = TREE_TYPE (ev);
    3348        30474 :   tree inner_type = TREE_TYPE (inner_ev);
    3349        30474 :   if (TYPE_PRECISION (inner_type) >= TYPE_PRECISION (type))
    3350              :     return ev;
    3351              : 
    3352              :   /* Type conversion in "(type) {inner_base, inner_step}_loop" can be
    3353              :      folded only if inner iv won't overflow.  We compute the maximum
    3354              :      number the inner iv can iterate before overflowing and return the
    3355              :      simplified affine iv.  */
    3356        30474 :   ev = build_polynomial_chrec (CHREC_VARIABLE (inner_ev),
    3357              :                                fold_convert (type, init),
    3358              :                                fold_convert (type, step));
    3359        30474 :   *niters = get_niter_type_bound (inner_type, init, step);
    3360        30474 :   return ev;
    3361              : }
    3362              : 
    3363              : /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
    3364              :    respect to WRTO_LOOP and returns its base and step in IV if possible
    3365              :    (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
    3366              :    and WRTO_LOOP).  If ALLOW_NONCONSTANT_STEP is true, we want step to be
    3367              :    invariant in LOOP.  Otherwise we require it to be an integer constant.
    3368              : 
    3369              :    IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
    3370              :    because it is computed in signed arithmetics).  Consequently, adding an
    3371              :    induction variable
    3372              : 
    3373              :    for (i = IV->base; ; i += IV->step)
    3374              : 
    3375              :    is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
    3376              :    false for the type of the induction variable, or you can prove that i does
    3377              :    not wrap by some other argument.  Otherwise, this might introduce undefined
    3378              :    behavior, and
    3379              : 
    3380              :    i = iv->base;
    3381              :    for (; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
    3382              : 
    3383              :    must be used instead.
    3384              : 
    3385              :    When IV_NITERS is not NULL, this function also checks case in which OP
    3386              :    is a conversion of an inner simple iv of below form:
    3387              : 
    3388              :      (outer_type){inner_base, inner_step}_loop.
    3389              : 
    3390              :    If type of inner iv has smaller precision than outer_type, it can't be
    3391              :    folded into {(outer_type)inner_base, (outer_type)inner_step}_loop because
    3392              :    the inner iv could overflow/wrap.  In this case, we derive a condition
    3393              :    under which the inner iv won't overflow/wrap and do the simplification.
    3394              :    The derived condition normally is the maximum number the inner iv can
    3395              :    iterate, and will be stored in IV_NITERS.  This is useful in loop niter
    3396              :    analysis, to derive break conditions when a loop must terminate, when is
    3397              :    infinite.
    3398              : 
    3399              :    If RECORD_NOWRAP_BOUNDS is true, let scev analysis continue rather than
    3400              :    stop if an IV might wrap.  In such a case, store the recorded bound under
    3401              :    which no wrapping occurs in IV's nowrap_bound.  */
    3402              : 
    3403              : bool
    3404     53509386 : simple_iv_with_niters (class loop *wrto_loop, class loop *use_loop,
    3405              :                        tree op, affine_iv *iv, tree *iv_niters,
    3406              :                        bool allow_nonconstant_step,
    3407              :                        bool record_nowrap_bounds)
    3408              : {
    3409     53509386 :   enum tree_code code;
    3410     53509386 :   tree type, ev, base, e;
    3411     53509386 :   wide_int extreme;
    3412     53509386 :   bool folded_casts;
    3413              : 
    3414     53509386 :   iv->base = NULL_TREE;
    3415     53509386 :   iv->step = NULL_TREE;
    3416     53509386 :   iv->no_overflow = false;
    3417     53509386 :   iv->nowrap_bound = NULL_TREE;
    3418              : 
    3419     53509386 :   type = TREE_TYPE (op);
    3420     53509386 :   if (!POINTER_TYPE_P (type)
    3421     44097009 :       && !INTEGRAL_TYPE_P (type))
    3422              :     return false;
    3423              : 
    3424     51403557 :   tree nowrap_bound = NULL_TREE;
    3425    101850363 :   ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
    3426              :                                          &folded_casts,
    3427              :                                          record_nowrap_bounds ? &nowrap_bound
    3428              :                                                         : nullptr);
    3429              : 
    3430              :   /* If there was a nontrivial nowrap bound, add it to the IV.  */
    3431     51403557 :   if (record_nowrap_bounds && nowrap_bound)
    3432         6390 :     iv->nowrap_bound = nowrap_bound;
    3433              : 
    3434     51403557 :   if (chrec_contains_undetermined (ev)
    3435     51403557 :       || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
    3436              :     return false;
    3437              : 
    3438     38212598 :   if (tree_does_not_contain_chrecs (ev))
    3439              :     {
    3440     16968657 :       iv->base = ev;
    3441     16968657 :       tree ev_type = TREE_TYPE (ev);
    3442     16968657 :       if (POINTER_TYPE_P (ev_type))
    3443      2748856 :         ev_type = sizetype;
    3444              : 
    3445     16968657 :       iv->step = build_int_cst (ev_type, 0);
    3446     16968657 :       iv->no_overflow = true;
    3447     16968657 :       return true;
    3448              :     }
    3449              : 
    3450              :   /* If we can derive valid scalar evolution with assumptions.  */
    3451     21243941 :   if (iv_niters && TREE_CODE (ev) != POLYNOMIAL_CHREC)
    3452        38932 :     ev = derive_simple_iv_with_niters (ev, iv_niters);
    3453              : 
    3454     21243941 :   if (TREE_CODE (ev) != POLYNOMIAL_CHREC)
    3455              :     return false;
    3456              : 
    3457     21195353 :   if (CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
    3458              :     return false;
    3459              : 
    3460     21195339 :   iv->step = CHREC_RIGHT (ev);
    3461     13640996 :   if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
    3462     34576758 :       || tree_contains_chrecs (iv->step, NULL))
    3463              :     return false;
    3464              : 
    3465     20923859 :   iv->base = CHREC_LEFT (ev);
    3466     20923859 :   if (tree_contains_chrecs (iv->base, NULL))
    3467              :     return false;
    3468              : 
    3469     20923859 :   iv->no_overflow = !folded_casts && nowrap_type_p (type);
    3470              : 
    3471     20923859 :   if (!iv->no_overflow
    3472     20923859 :       && !iv_can_overflow_p (wrto_loop, type, iv->base, iv->step))
    3473      3983581 :     iv->no_overflow = true;
    3474              : 
    3475              :   /* Try to simplify iv base:
    3476              : 
    3477              :        (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T
    3478              :          == (signed T)(unsigned T)base + step
    3479              :          == base + step
    3480              : 
    3481              :      If we can prove operation (base + step) doesn't overflow or underflow.
    3482              :      Specifically, we try to prove below conditions are satisfied:
    3483              : 
    3484              :              base <= UPPER_BOUND (type) - step  ;;step > 0
    3485              :              base >= LOWER_BOUND (type) - step  ;;step < 0
    3486              : 
    3487              :      This is done by proving the reverse conditions are false using loop's
    3488              :      initial conditions.
    3489              : 
    3490              :      The is necessary to make loop niter, or iv overflow analysis easier
    3491              :      for below example:
    3492              : 
    3493              :        int foo (int *a, signed char s, signed char l)
    3494              :          {
    3495              :            signed char i;
    3496              :            for (i = s; i < l; i++)
    3497              :              a[i] = 0;
    3498              :            return 0;
    3499              :           }
    3500              : 
    3501              :      Note variable I is firstly converted to type unsigned char, incremented,
    3502              :      then converted back to type signed char.  */
    3503              : 
    3504     20923859 :   if (wrto_loop->num != use_loop->num)
    3505              :     return true;
    3506              : 
    3507     20741923 :   if (!CONVERT_EXPR_P (iv->base) || TREE_CODE (iv->step) != INTEGER_CST)
    3508              :     return true;
    3509              : 
    3510       232126 :   type = TREE_TYPE (iv->base);
    3511       232126 :   e = TREE_OPERAND (iv->base, 0);
    3512       232126 :   if (!tree_nop_conversion_p (type, TREE_TYPE (e))
    3513       199662 :       || TREE_CODE (e) != PLUS_EXPR
    3514       109160 :       || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST
    3515       314241 :       || !tree_int_cst_equal (iv->step,
    3516        82115 :                               fold_convert (type, TREE_OPERAND (e, 1))))
    3517              :     return true;
    3518        64510 :   e = TREE_OPERAND (e, 0);
    3519        64510 :   if (!CONVERT_EXPR_P (e))
    3520              :     return true;
    3521        35732 :   base = TREE_OPERAND (e, 0);
    3522        35732 :   if (!useless_type_conversion_p (type, TREE_TYPE (base)))
    3523              :     return true;
    3524              : 
    3525        27165 :   if (tree_int_cst_sign_bit (iv->step))
    3526              :     {
    3527         7131 :       code = LT_EXPR;
    3528         7131 :       extreme = wi::min_value (type);
    3529              :     }
    3530              :   else
    3531              :     {
    3532        20034 :       code = GT_EXPR;
    3533        20034 :       extreme = wi::max_value (type);
    3534              :     }
    3535        27165 :   wi::overflow_type overflow = wi::OVF_NONE;
    3536        27165 :   extreme = wi::sub (extreme, wi::to_wide (iv->step),
    3537        54330 :                      TYPE_SIGN (type), &overflow);
    3538        27165 :   if (overflow)
    3539              :     return true;
    3540        27141 :   e = fold_build2 (code, boolean_type_node, base,
    3541              :                    wide_int_to_tree (type, extreme));
    3542        27141 :   e = simplify_using_initial_conditions (use_loop, e);
    3543        27141 :   if (!integer_zerop (e))
    3544              :     return true;
    3545              : 
    3546        15913 :   if (POINTER_TYPE_P (TREE_TYPE (base)))
    3547              :     code = POINTER_PLUS_EXPR;
    3548              :   else
    3549              :     code = PLUS_EXPR;
    3550              : 
    3551        15913 :   iv->base = fold_build2 (code, TREE_TYPE (base), base, iv->step);
    3552        15913 :   return true;
    3553     53509386 : }
    3554              : 
    3555              : /* Like simple_iv_with_niters, but return TRUE when OP behaves as a simple
    3556              :    affine iv unconditionally.  */
    3557              : 
    3558              : bool
    3559     21637611 : simple_iv (class loop *wrto_loop, class loop *use_loop, tree op,
    3560              :            affine_iv *iv, bool allow_nonconstant_step,
    3561              :            bool record_nowrap_bounds)
    3562              : {
    3563     21637611 :   return simple_iv_with_niters (wrto_loop, use_loop, op, iv,
    3564              :                                 NULL, allow_nonconstant_step,
    3565     21637611 :                                 record_nowrap_bounds);
    3566              : }
    3567              : 
    3568              : /* Finalize the scalar evolution analysis.  */
    3569              : 
    3570              : void
    3571     15775838 : scev_finalize (void)
    3572              : {
    3573     15775838 :   if (!scalar_evolution_info && !scalar_evolution_nowrap_info)
    3574              :     return;
    3575              : 
    3576     15775837 :   if (scalar_evolution_info)
    3577              :     {
    3578     15775837 :       scalar_evolution_info->empty ();
    3579     15775837 :       scalar_evolution_info = NULL;
    3580              :     }
    3581              : 
    3582     15775837 :   if (scalar_evolution_nowrap_info)
    3583              :     {
    3584     15775837 :       scalar_evolution_nowrap_info->empty ();
    3585     15775837 :       scalar_evolution_nowrap_info = NULL;
    3586              :     }
    3587              : 
    3588     15775837 :   free_numbers_of_iterations_estimates (cfun);
    3589              : }
    3590              : 
    3591              : /* Returns true if the expression EXPR is considered to be too expensive
    3592              :    for scev_const_prop.  Sets *COND_OVERFLOW_P to true when the
    3593              :    expression might contain a sub-expression that is subject to undefined
    3594              :    overflow behavior and conditionally evaluated.  */
    3595              : 
    3596              : static bool
    3597     10087656 : expression_expensive_p (tree expr, bool *cond_overflow_p,
    3598              :                         hash_map<tree, uint64_t> &cache, uint64_t &cost)
    3599              : {
    3600     10087656 :   enum tree_code code;
    3601              : 
    3602     10087656 :   if (is_gimple_val (expr))
    3603              :     return false;
    3604              : 
    3605      4151999 :   code = TREE_CODE (expr);
    3606      4151999 :   if (code == TRUNC_DIV_EXPR
    3607              :       || code == CEIL_DIV_EXPR
    3608              :       || code == FLOOR_DIV_EXPR
    3609              :       || code == ROUND_DIV_EXPR
    3610              :       || code == TRUNC_MOD_EXPR
    3611              :       || code == CEIL_MOD_EXPR
    3612              :       || code == FLOOR_MOD_EXPR
    3613      4151999 :       || code == ROUND_MOD_EXPR
    3614      4151999 :       || code == EXACT_DIV_EXPR)
    3615              :     {
    3616              :       /* Division by power of two is usually cheap, so we allow it.
    3617              :          Forbid anything else.  */
    3618        53084 :       if (!integer_pow2p (TREE_OPERAND (expr, 1)))
    3619              :         return true;
    3620              :     }
    3621              : 
    3622      4144020 :   bool visited_p;
    3623      4144020 :   uint64_t &local_cost = cache.get_or_insert (expr, &visited_p);
    3624      4144020 :   if (visited_p)
    3625              :     {
    3626          346 :       uint64_t tem = cost + local_cost;
    3627          346 :       if (tem < cost)
    3628              :         return true;
    3629          346 :       cost = tem;
    3630          346 :       return false;
    3631              :     }
    3632      4143674 :   local_cost = 1;
    3633              : 
    3634      4143674 :   uint64_t op_cost = 0;
    3635      4143674 :   if (code == CALL_EXPR)
    3636              :     {
    3637          163 :       tree arg;
    3638          163 :       call_expr_arg_iterator iter;
    3639              :       /* Even though is_inexpensive_builtin might say true, we will get a
    3640              :          library call for popcount when backend does not have an instruction
    3641              :          to do so.  We consider this to be expensive and generate
    3642              :          __builtin_popcount only when backend defines it.  */
    3643          163 :       optab optab;
    3644          163 :       combined_fn cfn = get_call_combined_fn (expr);
    3645          163 :       switch (cfn)
    3646              :         {
    3647           36 :         CASE_CFN_POPCOUNT:
    3648           36 :           optab = popcount_optab;
    3649           36 :           goto bitcount_call;
    3650           94 :         CASE_CFN_CLZ:
    3651           94 :           optab = clz_optab;
    3652           94 :           goto bitcount_call;
    3653              :         CASE_CFN_CTZ:
    3654              :           optab = ctz_optab;
    3655          163 : bitcount_call:
    3656              :           /* Check if opcode for popcount is available in the mode required.  */
    3657          163 :           if (optab_handler (optab,
    3658          163 :                              TYPE_MODE (TREE_TYPE (CALL_EXPR_ARG (expr, 0))))
    3659              :               == CODE_FOR_nothing)
    3660              :             {
    3661           32 :               machine_mode mode;
    3662           32 :               mode = TYPE_MODE (TREE_TYPE (CALL_EXPR_ARG (expr, 0)));
    3663           32 :               scalar_int_mode int_mode;
    3664              : 
    3665              :               /* If the mode is of 2 * UNITS_PER_WORD size, we can handle
    3666              :                  double-word popcount by emitting two single-word popcount
    3667              :                  instructions.  */
    3668           32 :               if (is_a <scalar_int_mode> (mode, &int_mode)
    3669           34 :                   && GET_MODE_SIZE (int_mode) == 2 * UNITS_PER_WORD
    3670            2 :                   && (optab_handler (optab, word_mode)
    3671              :                       != CODE_FOR_nothing))
    3672              :                   break;
    3673              :               /* If popcount is available for a wider mode, we emulate the
    3674              :                  operation for a narrow mode by first zero-extending the value
    3675              :                  and then computing popcount in the wider mode.  Analogue for
    3676              :                  ctz.  For clz we do the same except that we additionally have
    3677              :                  to subtract the difference of the mode precisions from the
    3678              :                  result.  */
    3679           30 :               if (is_a <scalar_int_mode> (mode, &int_mode))
    3680              :                 {
    3681           30 :                   machine_mode wider_mode_iter;
    3682          149 :                   FOR_EACH_WIDER_MODE (wider_mode_iter, mode)
    3683          119 :                     if (optab_handler (optab, wider_mode_iter)
    3684              :                         != CODE_FOR_nothing)
    3685            0 :                       goto check_call_args;
    3686              :                   /* Operation ctz may be emulated via clz in expand_ctz.  */
    3687           30 :                   if (optab == ctz_optab)
    3688              :                     {
    3689            0 :                       FOR_EACH_WIDER_MODE_FROM (wider_mode_iter, mode)
    3690            0 :                         if (optab_handler (clz_optab, wider_mode_iter)
    3691              :                             != CODE_FOR_nothing)
    3692            0 :                           goto check_call_args;
    3693              :                     }
    3694              :                 }
    3695          163 :               return true;
    3696              :             }
    3697              :           break;
    3698              : 
    3699            0 :         default:
    3700            0 :           if (cfn == CFN_LAST
    3701            0 :               || !is_inexpensive_builtin (get_callee_fndecl (expr)))
    3702              :             return true;
    3703              :           break;
    3704              :         }
    3705              : 
    3706          133 : check_call_args:
    3707          443 :       FOR_EACH_CALL_EXPR_ARG (arg, iter, expr)
    3708          177 :         if (expression_expensive_p (arg, cond_overflow_p, cache, op_cost))
    3709              :           return true;
    3710          133 :       *cache.get (expr) += op_cost;
    3711          133 :       cost += op_cost + 1;
    3712          133 :       return false;
    3713              :     }
    3714              : 
    3715      4143511 :   if (code == COND_EXPR)
    3716              :     {
    3717         2058 :       if (expression_expensive_p (TREE_OPERAND (expr, 0), cond_overflow_p,
    3718              :                                   cache, op_cost)
    3719         2058 :           || (EXPR_P (TREE_OPERAND (expr, 1))
    3720         2057 :               && EXPR_P (TREE_OPERAND (expr, 2)))
    3721              :           /* If either branch has side effects or could trap.  */
    3722         2050 :           || TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 1))
    3723         2050 :           || generic_expr_could_trap_p (TREE_OPERAND (expr, 1))
    3724         2049 :           || TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 0))
    3725         2049 :           || generic_expr_could_trap_p (TREE_OPERAND (expr, 0))
    3726         2049 :           || expression_expensive_p (TREE_OPERAND (expr, 1), cond_overflow_p,
    3727              :                                      cache, op_cost)
    3728         4004 :           || expression_expensive_p (TREE_OPERAND (expr, 2), cond_overflow_p,
    3729              :                                      cache, op_cost))
    3730              :         return true;
    3731              :       /* Conservatively assume there's overflow for now.  */
    3732         1946 :       *cond_overflow_p = true;
    3733         1946 :       *cache.get (expr) += op_cost;
    3734         1946 :       cost += op_cost + 1;
    3735         1946 :       return false;
    3736              :     }
    3737              : 
    3738      4141453 :   switch (TREE_CODE_CLASS (code))
    3739              :     {
    3740      2162189 :     case tcc_binary:
    3741      2162189 :     case tcc_comparison:
    3742      2162189 :       if (expression_expensive_p (TREE_OPERAND (expr, 1), cond_overflow_p,
    3743              :                                   cache, op_cost))
    3744              :         return true;
    3745              : 
    3746              :       /* Fallthru.  */
    3747      4139022 :     case tcc_unary:
    3748      4139022 :       if (expression_expensive_p (TREE_OPERAND (expr, 0), cond_overflow_p,
    3749              :                                   cache, op_cost))
    3750              :         return true;
    3751      4118453 :       *cache.get (expr) += op_cost;
    3752      4118453 :       cost += op_cost + 1;
    3753      4118453 :       return false;
    3754              : 
    3755              :     default:
    3756              :       return true;
    3757              :     }
    3758              : }
    3759              : 
    3760              : bool
    3761      3780215 : expression_expensive_p (tree expr, bool *cond_overflow_p)
    3762              : {
    3763      3780215 :   hash_map<tree, uint64_t> cache;
    3764      3780215 :   uint64_t expanded_size = 0;
    3765      3780215 :   *cond_overflow_p = false;
    3766      3780215 :   return (expression_expensive_p (expr, cond_overflow_p, cache, expanded_size)
    3767              :           /* ???  Both the explicit unsharing and gimplification of expr will
    3768              :              expand shared trees to multiple copies.
    3769              :              Guard against exponential growth by counting the visits and
    3770              :              comparing against the number of original nodes.  Allow a tiny
    3771              :              bit of duplication to catch some additional optimizations.  */
    3772      3788373 :           || expanded_size > (cache.elements () + 1));
    3773      3780215 : }
    3774              : 
    3775              : /* Match.pd function to match bitwise inductive expression.
    3776              :    .i.e.
    3777              :    _2 = 1 << _1;
    3778              :    _3 = ~_2;
    3779              :    tmp_9 = _3 & tmp_12;  */
    3780              : extern bool gimple_bitwise_induction_p (tree, tree *, tree (*)(tree));
    3781              : 
    3782              : /* Return the inductive expression of bitwise operation if possible,
    3783              :    otherwise returns DEF.  */
    3784              : static tree
    3785        21070 : analyze_and_compute_bitwise_induction_effect (class loop* loop,
    3786              :                                               tree phidef,
    3787              :                                               unsigned HOST_WIDE_INT niter)
    3788              : {
    3789        21070 :   tree match_op[3],inv, bitwise_scev;
    3790        21070 :   tree type = TREE_TYPE (phidef);
    3791        21070 :   gphi* header_phi = NULL;
    3792              : 
    3793              :   /* Match things like op2(MATCH_OP[2]), op1(MATCH_OP[1]), phidef(PHIDEF)
    3794              : 
    3795              :      op2 = PHI <phidef, inv>
    3796              :      _1 = (int) bit_17;
    3797              :      _3 = 1 << _1;
    3798              :      op1 = ~_3;
    3799              :      phidef = op1 & op2;  */
    3800        21070 :   if (!gimple_bitwise_induction_p (phidef, &match_op[0], NULL)
    3801          100 :       || TREE_CODE (match_op[2]) != SSA_NAME
    3802          100 :       || !(header_phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (match_op[2])))
    3803          100 :       || gimple_bb (header_phi) != loop->header
    3804        21170 :       || gimple_phi_num_args (header_phi) != 2)
    3805              :     return NULL_TREE;
    3806              : 
    3807          100 :   if (PHI_ARG_DEF_FROM_EDGE (header_phi, loop_latch_edge (loop)) != phidef)
    3808              :     return NULL_TREE;
    3809              : 
    3810          100 :   bitwise_scev = analyze_scalar_evolution (loop, match_op[1]);
    3811          100 :   bitwise_scev = instantiate_parameters (loop, bitwise_scev);
    3812              : 
    3813              :   /* Make sure bits is in range of type precision.  */
    3814          100 :   if (TREE_CODE (bitwise_scev) != POLYNOMIAL_CHREC
    3815          100 :       || !INTEGRAL_TYPE_P (TREE_TYPE (bitwise_scev))
    3816          100 :       || !tree_fits_uhwi_p (CHREC_LEFT (bitwise_scev))
    3817          100 :       || tree_to_uhwi (CHREC_LEFT (bitwise_scev)) >= TYPE_PRECISION (type)
    3818          200 :       || !tree_fits_shwi_p (CHREC_RIGHT (bitwise_scev)))
    3819              :     return NULL_TREE;
    3820              : 
    3821          100 : enum bit_op_kind
    3822              :   {
    3823              :    INDUCTION_BIT_CLEAR,
    3824              :    INDUCTION_BIT_IOR,
    3825              :    INDUCTION_BIT_XOR,
    3826              :    INDUCTION_BIT_RESET,
    3827              :    INDUCTION_ZERO,
    3828              :    INDUCTION_ALL
    3829              :   };
    3830              : 
    3831          100 :   enum bit_op_kind induction_kind;
    3832          100 :   enum tree_code code1
    3833          100 :     = gimple_assign_rhs_code (SSA_NAME_DEF_STMT (phidef));
    3834          100 :   enum tree_code code2
    3835          100 :     = gimple_assign_rhs_code (SSA_NAME_DEF_STMT (match_op[0]));
    3836              : 
    3837              :   /* BIT_CLEAR: A &= ~(1 << bit)
    3838              :      BIT_RESET: A ^= (1 << bit).
    3839              :      BIT_IOR: A |= (1 << bit)
    3840              :      BIT_ZERO: A &= (1 << bit)
    3841              :      BIT_ALL: A |= ~(1 << bit)
    3842              :      BIT_XOR: A ^= ~(1 << bit).
    3843              :      bit is induction variable.  */
    3844          100 :   switch (code1)
    3845              :     {
    3846           27 :     case BIT_AND_EXPR:
    3847           27 :       induction_kind = code2 == BIT_NOT_EXPR
    3848           27 :         ? INDUCTION_BIT_CLEAR
    3849              :         : INDUCTION_ZERO;
    3850              :       break;
    3851           49 :     case BIT_IOR_EXPR:
    3852           49 :       induction_kind = code2 == BIT_NOT_EXPR
    3853           49 :         ? INDUCTION_ALL
    3854              :         : INDUCTION_BIT_IOR;
    3855              :       break;
    3856           12 :     case BIT_XOR_EXPR:
    3857           12 :       induction_kind = code2 == BIT_NOT_EXPR
    3858           12 :         ? INDUCTION_BIT_XOR
    3859              :         : INDUCTION_BIT_RESET;
    3860              :       break;
    3861              :       /* A ^ ~(1 << bit) is equal to ~(A ^ (1 << bit)).  */
    3862           12 :     case BIT_NOT_EXPR:
    3863           12 :       gcc_assert (code2 == BIT_XOR_EXPR);
    3864              :       induction_kind = INDUCTION_BIT_XOR;
    3865              :       break;
    3866            0 :     default:
    3867            0 :       gcc_unreachable ();
    3868              :     }
    3869              : 
    3870           37 :   if (induction_kind == INDUCTION_ZERO)
    3871           12 :     return build_zero_cst (type);
    3872           88 :   if (induction_kind == INDUCTION_ALL)
    3873           12 :     return build_all_ones_cst (type);
    3874              : 
    3875          152 :   wide_int bits = wi::zero (TYPE_PRECISION (type));
    3876           76 :   HOST_WIDE_INT bit_start = tree_to_shwi (CHREC_LEFT (bitwise_scev));
    3877           76 :   HOST_WIDE_INT step = tree_to_shwi (CHREC_RIGHT (bitwise_scev));
    3878           76 :   HOST_WIDE_INT bit_final = bit_start + step * niter;
    3879              : 
    3880              :   /* bit_start, bit_final in range of [0,TYPE_PRECISION)
    3881              :      implies all bits are set in range.  */
    3882           76 :   if (bit_final >= TYPE_PRECISION (type)
    3883           76 :       || bit_final < 0)
    3884              :     return NULL_TREE;
    3885              : 
    3886              :   /* Loop tripcount should be niter + 1.  */
    3887         1296 :   for (unsigned i = 0; i != niter + 1; i++)
    3888              :     {
    3889         1220 :       bits = wi::set_bit (bits, bit_start);
    3890         1220 :       bit_start += step;
    3891              :     }
    3892              : 
    3893           76 :   bool inverted = false;
    3894           76 :   switch (induction_kind)
    3895              :     {
    3896              :     case INDUCTION_BIT_CLEAR:
    3897              :       code1 = BIT_AND_EXPR;
    3898              :       inverted = true;
    3899              :       break;
    3900              :     case INDUCTION_BIT_IOR:
    3901              :       code1 = BIT_IOR_EXPR;
    3902              :       break;
    3903              :     case INDUCTION_BIT_RESET:
    3904              :       code1 = BIT_XOR_EXPR;
    3905              :       break;
    3906              :     /* A ^= ~(1 << bit) is special, when loop tripcount is even,
    3907              :        it's equal to  A ^= bits, else A ^= ~bits.  */
    3908           12 :     case INDUCTION_BIT_XOR:
    3909           12 :       code1 = BIT_XOR_EXPR;
    3910           12 :       if (niter % 2 == 0)
    3911              :         inverted = true;
    3912              :       break;
    3913              :     default:
    3914              :       gcc_unreachable ();
    3915              :     }
    3916              : 
    3917              :   if (inverted)
    3918           19 :     bits = wi::bit_not (bits);
    3919              : 
    3920           76 :   inv = PHI_ARG_DEF_FROM_EDGE (header_phi, loop_preheader_edge (loop));
    3921           76 :   return fold_build2 (code1, type, inv, wide_int_to_tree (type, bits));
    3922              : }
    3923              : 
    3924              : /* Match.pd function to match bitop with invariant expression
    3925              :   .i.e.
    3926              :   tmp_7 = _0 & _1; */
    3927              : extern bool gimple_bitop_with_inv_p (tree, tree *, tree (*)(tree));
    3928              : 
    3929              : /* Return the inductive expression of bitop with invariant if possible,
    3930              :    otherwise returns DEF.  */
    3931              : static tree
    3932        69367 : analyze_and_compute_bitop_with_inv_effect (class loop* loop, tree phidef,
    3933              :                                            tree niter)
    3934              : {
    3935        69367 :   tree match_op[2],inv;
    3936        69367 :   tree type = TREE_TYPE (phidef);
    3937        69367 :   gphi* header_phi = NULL;
    3938        69367 :   enum tree_code code;
    3939              :   /* match thing like op0 (match[0]), op1 (match[1]), phidef (PHIDEF)
    3940              : 
    3941              :     op1 =  PHI <phidef, inv>
    3942              :     phidef = op0 & op1
    3943              :     if op0 is an invariant, it could change to
    3944              :     phidef = op0 & inv.  */
    3945        69367 :   gimple *def;
    3946        69367 :   def = SSA_NAME_DEF_STMT (phidef);
    3947        69367 :   if (!(is_gimple_assign (def)
    3948        24858 :       && ((code = gimple_assign_rhs_code (def)), true)
    3949        24858 :       && (code == BIT_AND_EXPR || code == BIT_IOR_EXPR
    3950        22376 :           || code == BIT_XOR_EXPR)))
    3951              :     return NULL_TREE;
    3952              : 
    3953         3247 :   match_op[0] = gimple_assign_rhs1 (def);
    3954         3247 :   match_op[1] = gimple_assign_rhs2 (def);
    3955              : 
    3956         3247 :   if (expr_invariant_in_loop_p (loop, match_op[1]))
    3957          251 :     std::swap (match_op[0], match_op[1]);
    3958              : 
    3959         3247 :   if (TREE_CODE (match_op[1]) != SSA_NAME
    3960         3247 :       || !expr_invariant_in_loop_p (loop, match_op[0])
    3961          367 :       || !(header_phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (match_op[1])))
    3962          228 :       || gimple_bb (header_phi) != loop->header
    3963         3467 :       || gimple_phi_num_args (header_phi) != 2)
    3964              :     return NULL_TREE;
    3965              : 
    3966          220 :   if (PHI_ARG_DEF_FROM_EDGE (header_phi, loop_latch_edge (loop)) != phidef)
    3967              :     return NULL_TREE;
    3968              : 
    3969          215 :   enum tree_code code1
    3970          215 :     = gimple_assign_rhs_code (def);
    3971              : 
    3972          215 :   if (code1 == BIT_XOR_EXPR)
    3973              :     {
    3974           61 :       tree niter_type = TREE_TYPE (niter);
    3975           61 :       tree one = build_one_cst (niter_type);
    3976           61 :       tree contributes = fold_build2 (BIT_XOR_EXPR, niter_type,
    3977              :                                       fold_build2 (BIT_AND_EXPR, niter_type,
    3978              :                                                    niter, one),
    3979              :                                       one);
    3980              :       /* mask is all-ones when the invariant contributes, zero otherwise.  */
    3981           61 :       tree mask = fold_build1 (NEGATE_EXPR, type,
    3982              :                                fold_convert (type, contributes));
    3983           61 :       match_op[0] = fold_build2 (BIT_AND_EXPR, type, match_op[0], mask);
    3984              :     }
    3985              : 
    3986          215 :   inv = PHI_ARG_DEF_FROM_EDGE (header_phi, loop_preheader_edge (loop));
    3987          215 :   return fold_build2 (code1, type, inv, match_op[0]);
    3988              : }
    3989              : 
    3990              : /* Try to compute the final value of PHIDEF when PHIDEF is the result of a
    3991              :    loop-header PHI.
    3992              : 
    3993              :    This handles the nonzero-latch-count delayed-value form:
    3994              : 
    3995              :      y_phi = PHI <latch_arg (latch), init (preheader)>
    3996              : 
    3997              :    If the latch count is known to be nonzero, the final value is:
    3998              : 
    3999              :      latch_arg evaluated at iteration niter - 1
    4000              : 
    4001              :    Return NULL_TREE if the pattern does not apply.  */
    4002              : static tree
    4003        42412 : compute_final_value_from_loop_phi_latch (class loop *loop,
    4004              :         class loop *ex_loop, gphi *header_phi, tree niter, bool* folded_casts)
    4005              : {
    4006        42412 :   if (gimple_bb (header_phi) != loop->header
    4007        44881 :       || gimple_phi_num_args (header_phi) != 2)
    4008              :     return NULL_TREE;
    4009              : 
    4010              :   /* If niter is a symbolic value make sure it can never be zero, otherwise we
    4011              :      do a bad replacement.  */
    4012         2469 :   if (!tree_expr_nonzero_p (niter))
    4013              :     return NULL_TREE;
    4014              : 
    4015         1071 :   tree latch_arg = PHI_ARG_DEF_FROM_EDGE (header_phi,
    4016              :                                           loop_latch_edge (loop));
    4017              : 
    4018         1071 :   tree ev = analyze_scalar_evolution_in_loop (ex_loop,
    4019              :                                               loop,
    4020              :                                               latch_arg,
    4021              :                                               folded_casts);
    4022         1071 :   if (ev == chrec_dont_know)
    4023              :     return NULL_TREE;
    4024              : 
    4025          491 :   bool invariant_p;
    4026          491 :   if (no_evolution_in_loop_p (ev, ex_loop->num, &invariant_p) && invariant_p)
    4027              :     return ev;
    4028           14 :   else if (TREE_CODE (ev) == POLYNOMIAL_CHREC
    4029           14 :            && get_chrec_loop (ev) == ex_loop)
    4030              :   {
    4031           14 :     tree niter_type = TREE_TYPE (niter);
    4032           14 :     tree prev_iter = fold_build2 (MINUS_EXPR,
    4033              :                                   niter_type,
    4034              :                                   niter,
    4035              :                                   build_one_cst (niter_type));
    4036              : 
    4037           14 :     tree res = chrec_apply (ex_loop->num, ev, prev_iter);
    4038           14 :     if (res == chrec_dont_know)
    4039              :       return NULL_TREE;
    4040              : 
    4041           14 :     if (chrec_contains_symbols_defined_in_loop (res, ex_loop->num))
    4042              :     {
    4043            0 :       res = instantiate_parameters (ex_loop, res);
    4044            0 :       if (res == chrec_dont_know)
    4045              :         return NULL_TREE;
    4046              :     }
    4047              : 
    4048           14 :     return res;
    4049              :   }
    4050              :   return NULL_TREE;
    4051              : }
    4052              : 
    4053              : /* Do final value replacement for LOOP, return true if we did anything.  */
    4054              : 
    4055              : bool
    4056       706798 : final_value_replacement_loop (class loop *loop)
    4057              : {
    4058              :   /* If we do not know exact number of iterations of the loop, we cannot
    4059              :      replace the final value.  */
    4060       706798 :   edge exit = single_exit (loop);
    4061       706798 :   if (!exit)
    4062              :     return false;
    4063              : 
    4064       470540 :   class tree_niter_desc niter_desc;
    4065       470540 :   if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
    4066              :     return false;
    4067              : 
    4068       353633 :   tree niter = niter_desc.niter;
    4069       353633 :   if (niter == chrec_dont_know)
    4070              :     return false;
    4071              : 
    4072              :   /* Ensure that it is possible to insert new statements somewhere.  */
    4073       353633 :   if (!single_pred_p (exit->dest))
    4074        39225 :     split_loop_exit_edge (exit);
    4075              : 
    4076              :   /* Set stmt insertion pointer.  All stmts are inserted before this point.  */
    4077              : 
    4078       353633 :   class loop *ex_loop
    4079       707266 :     = superloop_at_depth (loop,
    4080       432463 :                           loop_depth (exit->dest->loop_father) + 1);
    4081              : 
    4082       353633 :   bool any = false;
    4083       353633 :   gphi_iterator psi;
    4084       789119 :   for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
    4085              :     {
    4086       435486 :       gphi *phi = psi.phi ();
    4087       435486 :       tree rslt = PHI_RESULT (phi);
    4088       435486 :       tree phidef = PHI_ARG_DEF_FROM_EDGE (phi, exit);
    4089       435486 :       tree def = phidef;
    4090       870286 :       if (virtual_operand_p (def))
    4091              :         {
    4092       249960 :           gsi_next (&psi);
    4093       400751 :           continue;
    4094              :         }
    4095              : 
    4096       352172 :       if (!POINTER_TYPE_P (TREE_TYPE (def))
    4097       352069 :           && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
    4098              :         {
    4099        74265 :           gsi_next (&psi);
    4100        74265 :           continue;
    4101              :         }
    4102              : 
    4103       111261 :       bool folded_casts;
    4104       111261 :       def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
    4105              :                                               &folded_casts);
    4106              : 
    4107       111261 :       tree bitinv_def, bit_def, phi_latch_final_value;
    4108       111261 :       unsigned HOST_WIDE_INT niter_num;
    4109              : 
    4110       111261 :       gphi *header_phi = TREE_CODE (phidef) == SSA_NAME
    4111       111261 :                          ? dyn_cast<gphi*> (SSA_NAME_DEF_STMT (phidef))
    4112              :                          : NULL;
    4113              : 
    4114       111261 :       if (def != chrec_dont_know)
    4115        35654 :         def = compute_overall_effect_of_inner_loop (ex_loop, def);
    4116              : 
    4117              :       /* Handle bitop with invariant induction expression.
    4118              : 
    4119              :         .i.e
    4120              :         for (int i =0 ;i < 32; i++)
    4121              :           tmp &= bit2;
    4122              :         if bit2 is an invariant in loop which could simple to
    4123              :         tmp &= bit2.  */
    4124        75607 :       else if (integer_zerop (niter_desc.may_be_zero)
    4125        75607 :                && (bitinv_def
    4126        69367 :                    = analyze_and_compute_bitop_with_inv_effect (loop,
    4127              :                                                                 phidef,
    4128              :                                                                 niter)))
    4129              :         def = bitinv_def;
    4130              : 
    4131              :       /* Handle bitwise induction expression.
    4132              : 
    4133              :          .i.e.
    4134              :          for (int i = 0; i != 64; i+=3)
    4135              :            res &= ~(1UL << i);
    4136              : 
    4137              :          RES can't be analyzed out by SCEV because it is not polynomially
    4138              :          expressible, but in fact final value of RES can be replaced by
    4139              :          RES & CONSTANT where CONSTANT all ones with bit {0,3,6,9,... ,63}
    4140              :          being cleared, similar for BIT_IOR_EXPR/BIT_XOR_EXPR.  */
    4141        75392 :       else if (tree_fits_uhwi_p (niter)
    4142        31691 :                && (niter_num = tree_to_uhwi (niter)) != 0
    4143        31676 :                && niter_num < TYPE_PRECISION (TREE_TYPE (phidef))
    4144        75392 :                && (bit_def
    4145        21070 :                    = analyze_and_compute_bitwise_induction_effect (loop,
    4146              :                                                                    phidef,
    4147              :                                                                    niter_num)))
    4148              :         def = bit_def;
    4149              : 
    4150        75292 :       else if (header_phi
    4151        44890 :                && integer_zerop (niter_desc.may_be_zero)
    4152        75292 :                && (phi_latch_final_value
    4153        42412 :                    = compute_final_value_from_loop_phi_latch (loop,
    4154              :                                                               ex_loop,
    4155              :                                                               header_phi,
    4156              :                                                               niter,
    4157              :                                                               &folded_casts)))
    4158              :         def = phi_latch_final_value;
    4159              : 
    4160       111261 :       bool cond_overflow_p;
    4161       111261 :       if (!tree_does_not_contain_chrecs (def)
    4162        35841 :           || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
    4163              :           /* Moving the computation from the loop may prolong life range
    4164              :              of some ssa names, which may cause problems if they appear
    4165              :              on abnormal edges.  */
    4166        35841 :           || contains_abnormal_ssa_name_p (def)
    4167              :           /* Do not emit expensive expressions.  The rationale is that
    4168              :              when someone writes a code like
    4169              : 
    4170              :              while (n > 45) n -= 45;
    4171              : 
    4172              :              he probably knows that n is not large, and does not want it
    4173              :              to be turned into n %= 45.  */
    4174       147102 :           || expression_expensive_p (def, &cond_overflow_p))
    4175              :         {
    4176        76526 :           if (dump_file && (dump_flags & TDF_DETAILS))
    4177              :             {
    4178           60 :               fprintf (dump_file, "not replacing:\n  ");
    4179           60 :               print_gimple_stmt (dump_file, phi, 0);
    4180           60 :               fprintf (dump_file, "\n");
    4181              :             }
    4182        76526 :           gsi_next (&psi);
    4183        76526 :           continue;
    4184              :         }
    4185              : 
    4186              :       /* Eliminate the PHI node and replace it by a computation outside
    4187              :          the loop.  */
    4188        34735 :       if (dump_file)
    4189              :         {
    4190           96 :           fprintf (dump_file, "\nfinal value replacement:\n  ");
    4191           96 :           print_gimple_stmt (dump_file, phi, 0);
    4192           96 :           fprintf (dump_file, " with expr: ");
    4193           96 :           print_generic_expr (dump_file, def);
    4194           96 :           fprintf (dump_file, "\n");
    4195              :         }
    4196        34735 :       any = true;
    4197              :       /* ???  Here we'd like to have a unshare_expr that would assign
    4198              :          shared sub-trees to new temporary variables either gimplified
    4199              :          to a GIMPLE sequence or to a statement list (keeping this a
    4200              :          GENERIC interface).  */
    4201        34735 :       def = unshare_expr (def);
    4202        34735 :       auto loc = gimple_phi_arg_location (phi, exit->dest_idx);
    4203              : 
    4204              :       /* Create the replacement statements.  */
    4205        34735 :       gimple_seq stmts;
    4206        34735 :       def = force_gimple_operand (def, &stmts, false, NULL_TREE);
    4207              : 
    4208              :       /* Propagate constants immediately, but leave an unused initialization
    4209              :          around to avoid invalidating the SCEV cache.  */
    4210        41735 :       if (CONSTANT_CLASS_P (def) && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rslt))
    4211         6999 :         replace_uses_by (rslt, def);
    4212              : 
    4213              :       /* Remove the old phi after the gimplification to make sure the
    4214              :          SSA name is defined by a statement so that fold_stmt during
    4215              :          the gimplification does not crash. */
    4216        34735 :       remove_phi_node (&psi, false);
    4217        34735 :       gassign *ass = gimple_build_assign (rslt, def);
    4218        34735 :       gimple_set_location (ass, loc);
    4219        34735 :       gimple_seq_add_stmt (&stmts, ass);
    4220              : 
    4221              :       /* If def's type has undefined overflow and there were folded
    4222              :          casts, rewrite all stmts added for def into arithmetics
    4223              :          with defined overflow behavior.  */
    4224        34735 :       if ((folded_casts
    4225          426 :            && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def))
    4226          720 :            && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def)))
    4227        35161 :           || cond_overflow_p)
    4228              :         {
    4229         2209 :           gimple_stmt_iterator gsi2;
    4230         2209 :           gsi2 = gsi_start (stmts);
    4231        20404 :           while (!gsi_end_p (gsi2))
    4232              :             {
    4233        18195 :               if (gimple_needing_rewrite_undefined (gsi_stmt (gsi2)))
    4234          532 :                 rewrite_to_defined_unconditional (&gsi2);
    4235        18195 :               gsi_next (&gsi2);
    4236              :             }
    4237              :         }
    4238        34735 :       gimple_stmt_iterator gsi = gsi_after_labels (exit->dest);
    4239        34735 :       gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
    4240        34735 :       if (dump_file)
    4241              :         {
    4242           96 :           fprintf (dump_file, " final stmt:\n  ");
    4243           96 :           print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (rslt), 0);
    4244           96 :           fprintf (dump_file, "\n");
    4245              :         }
    4246              : 
    4247              :       /* Re-fold immediate uses of the replaced def, but avoid
    4248              :          CFG manipulations from this function.  For now only do
    4249              :          a single-level re-folding, not re-folding uses of
    4250              :          folded uses.  */
    4251        34735 :       if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rslt))
    4252              :         {
    4253        34734 :           gimple *use_stmt;
    4254        34734 :           imm_use_iterator imm_iter;
    4255        34734 :           auto_vec<gimple *, 4> to_fold;
    4256        70187 :           FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, rslt)
    4257        35453 :             if (!stmt_can_throw_internal (cfun, use_stmt))
    4258        35449 :               to_fold.safe_push (use_stmt);
    4259              :           /* Delay folding until after the immediate use walk is completed
    4260              :              as we have an active ranger and that might walk immediate
    4261              :              uses of rslt again.  See PR122502.  */
    4262       139651 :           for (gimple *use_stmt : to_fold)
    4263              :             {
    4264        35449 :               gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
    4265        35449 :               if (fold_stmt (&gsi, follow_all_ssa_edges))
    4266         1997 :                 update_stmt (gsi_stmt (gsi));
    4267              :             }
    4268        34734 :         }
    4269              :     }
    4270              : 
    4271              :   return any;
    4272       706798 : }
    4273              : 
    4274              : #include "gt-tree-scalar-evolution.h"
        

Generated by: LCOV version 2.5.0-beta

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,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.