LCOV - code coverage report
Current view: top level - gcc - tree-scalar-evolution.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 91.2 % 1456 1328
Test Date: 2024-11-30 13:30:02 Functions: 92.3 % 65 60
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* Scalar evolution detector.
       2                 :             :    Copyright (C) 2003-2024 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                 :             : 
     288                 :             : static tree analyze_scalar_evolution_1 (class loop *, tree);
     289                 :             : static tree analyze_scalar_evolution_for_address_of (class loop *loop,
     290                 :             :                                                      tree var);
     291                 :             : 
     292                 :             : /* The cached information about an SSA name with version NAME_VERSION,
     293                 :             :    claiming that below basic block with index INSTANTIATED_BELOW, the
     294                 :             :    value of the SSA name can be expressed as CHREC.  */
     295                 :             : 
     296                 :             : struct GTY((for_user)) scev_info_str {
     297                 :             :   unsigned int name_version;
     298                 :             :   int instantiated_below;
     299                 :             :   tree chrec;
     300                 :             : };
     301                 :             : 
     302                 :             : /* Counters for the scev database.  */
     303                 :             : static unsigned nb_set_scev = 0;
     304                 :             : static unsigned nb_get_scev = 0;
     305                 :             : 
     306                 :             : struct scev_info_hasher : ggc_ptr_hash<scev_info_str>
     307                 :             : {
     308                 :             :   static hashval_t hash (scev_info_str *i);
     309                 :             :   static bool equal (const scev_info_str *a, const scev_info_str *b);
     310                 :             : };
     311                 :             : 
     312                 :             : static GTY (()) hash_table<scev_info_hasher> *scalar_evolution_info;
     313                 :             : 
     314                 :             : 
     315                 :             : /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW.  */
     316                 :             : 
     317                 :             : static inline struct scev_info_str *
     318                 :    51097412 : new_scev_info_str (basic_block instantiated_below, tree var)
     319                 :             : {
     320                 :    51097412 :   struct scev_info_str *res;
     321                 :             : 
     322                 :    51097412 :   res = ggc_alloc<scev_info_str> ();
     323                 :    51097412 :   res->name_version = SSA_NAME_VERSION (var);
     324                 :    51097412 :   res->chrec = chrec_not_analyzed_yet;
     325                 :    51097412 :   res->instantiated_below = instantiated_below->index;
     326                 :             : 
     327                 :    51097412 :   return res;
     328                 :             : }
     329                 :             : 
     330                 :             : /* Computes a hash function for database element ELT.  */
     331                 :             : 
     332                 :             : hashval_t
     333                 :  1018279949 : scev_info_hasher::hash (scev_info_str *elt)
     334                 :             : {
     335                 :  1018279949 :   return elt->name_version ^ elt->instantiated_below;
     336                 :             : }
     337                 :             : 
     338                 :             : /* Compares database elements E1 and E2.  */
     339                 :             : 
     340                 :             : bool
     341                 :  1004528812 : scev_info_hasher::equal (const scev_info_str *elt1, const scev_info_str *elt2)
     342                 :             : {
     343                 :  1004528812 :   return (elt1->name_version == elt2->name_version
     344                 :  1004528812 :           && elt1->instantiated_below == elt2->instantiated_below);
     345                 :             : }
     346                 :             : 
     347                 :             : /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
     348                 :             :    A first query on VAR returns chrec_not_analyzed_yet.  */
     349                 :             : 
     350                 :             : static tree *
     351                 :   201841168 : find_var_scev_info (basic_block instantiated_below, tree var)
     352                 :             : {
     353                 :   201841168 :   struct scev_info_str *res;
     354                 :   201841168 :   struct scev_info_str tmp;
     355                 :             : 
     356                 :   201841168 :   tmp.name_version = SSA_NAME_VERSION (var);
     357                 :   201841168 :   tmp.instantiated_below = instantiated_below->index;
     358                 :   201841168 :   scev_info_str **slot = scalar_evolution_info->find_slot (&tmp, INSERT);
     359                 :             : 
     360                 :   201841168 :   if (!*slot)
     361                 :    51097412 :     *slot = new_scev_info_str (instantiated_below, var);
     362                 :   201841168 :   res = *slot;
     363                 :             : 
     364                 :   201841168 :   return &res->chrec;
     365                 :             : }
     366                 :             : 
     367                 :             : 
     368                 :             : /* Hashtable helpers for a temporary hash-table used when
     369                 :             :    analyzing a scalar evolution, instantiating a CHREC or
     370                 :             :    resolving mixers.  */
     371                 :             : 
     372                 :             : class instantiate_cache_type
     373                 :             : {
     374                 :             : public:
     375                 :             :   htab_t map;
     376                 :             :   vec<scev_info_str> entries;
     377                 :             : 
     378                 :   133840153 :   instantiate_cache_type () : map (NULL), entries (vNULL) {}
     379                 :             :   ~instantiate_cache_type ();
     380                 :   113494108 :   tree get (unsigned slot) { return entries[slot].chrec; }
     381                 :    88164886 :   void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; }
     382                 :             : };
     383                 :             : 
     384                 :   133840153 : instantiate_cache_type::~instantiate_cache_type ()
     385                 :             : {
     386                 :   133840153 :   if (map != NULL)
     387                 :             :     {
     388                 :    26234623 :       htab_delete (map);
     389                 :    26234623 :       entries.release ();
     390                 :             :     }
     391                 :   133840153 : }
     392                 :             : 
     393                 :             : /* Cache to avoid infinite recursion when instantiating an SSA name.
     394                 :             :    Live during the outermost analyze_scalar_evolution, instantiate_scev
     395                 :             :    or resolve_mixers call.  */
     396                 :             : static instantiate_cache_type *global_cache;
     397                 :             : 
     398                 :             : 
     399                 :             : /* Return true when PHI is a loop-phi-node.  */
     400                 :             : 
     401                 :             : static bool
     402                 :    26880691 : loop_phi_node_p (gimple *phi)
     403                 :             : {
     404                 :             :   /* The implementation of this function is based on the following
     405                 :             :      property: "all the loop-phi-nodes of a loop are contained in the
     406                 :             :      loop's header basic block".  */
     407                 :             : 
     408                 :           0 :   return loop_containing_stmt (phi)->header == gimple_bb (phi);
     409                 :             : }
     410                 :             : 
     411                 :             : /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
     412                 :             :    In general, in the case of multivariate evolutions we want to get
     413                 :             :    the evolution in different loops.  LOOP specifies the level for
     414                 :             :    which to get the evolution.
     415                 :             : 
     416                 :             :    Example:
     417                 :             : 
     418                 :             :    | for (j = 0; j < 100; j++)
     419                 :             :    |   {
     420                 :             :    |     for (k = 0; k < 100; k++)
     421                 :             :    |       {
     422                 :             :    |         i = k + j;   - Here the value of i is a function of j, k.
     423                 :             :    |       }
     424                 :             :    |      ... = i         - Here the value of i is a function of j.
     425                 :             :    |   }
     426                 :             :    | ... = i              - Here the value of i is a scalar.
     427                 :             : 
     428                 :             :    Example:
     429                 :             : 
     430                 :             :    | i_0 = ...
     431                 :             :    | loop_1 10 times
     432                 :             :    |   i_1 = phi (i_0, i_2)
     433                 :             :    |   i_2 = i_1 + 2
     434                 :             :    | endloop
     435                 :             : 
     436                 :             :    This loop has the same effect as:
     437                 :             :    LOOP_1 has the same effect as:
     438                 :             : 
     439                 :             :    | i_1 = i_0 + 20
     440                 :             : 
     441                 :             :    The overall effect of the loop, "i_0 + 20" in the previous example,
     442                 :             :    is obtained by passing in the parameters: LOOP = 1,
     443                 :             :    EVOLUTION_FN = {i_0, +, 2}_1.
     444                 :             : */
     445                 :             : 
     446                 :             : tree
     447                 :     5391820 : compute_overall_effect_of_inner_loop (class loop *loop, tree evolution_fn)
     448                 :             : {
     449                 :     6197021 :   bool val = false;
     450                 :             : 
     451                 :     6197021 :   if (evolution_fn == chrec_dont_know)
     452                 :             :     return chrec_dont_know;
     453                 :             : 
     454                 :     6088552 :   else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
     455                 :             :     {
     456                 :     2150245 :       class loop *inner_loop = get_chrec_loop (evolution_fn);
     457                 :             : 
     458                 :     2150245 :       if (inner_loop == loop
     459                 :     2150245 :           || flow_loop_nested_p (loop, inner_loop))
     460                 :             :         {
     461                 :     2150245 :           tree nb_iter = number_of_latch_executions (inner_loop);
     462                 :             : 
     463                 :     2150245 :           if (nb_iter == chrec_dont_know)
     464                 :             :             return chrec_dont_know;
     465                 :             :           else
     466                 :             :             {
     467                 :      805201 :               tree res;
     468                 :             : 
     469                 :             :               /* evolution_fn is the evolution function in LOOP.  Get
     470                 :             :                  its value in the nb_iter-th iteration.  */
     471                 :      805201 :               res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
     472                 :             : 
     473                 :      805201 :               if (chrec_contains_symbols_defined_in_loop (res, loop->num))
     474                 :       55684 :                 res = instantiate_parameters (loop, res);
     475                 :             : 
     476                 :             :               /* Continue the computation until ending on a parent of LOOP.  */
     477                 :      805201 :               return compute_overall_effect_of_inner_loop (loop, res);
     478                 :             :             }
     479                 :             :         }
     480                 :             :       else
     481                 :             :         return evolution_fn;
     482                 :             :      }
     483                 :             : 
     484                 :             :   /* If the evolution function is an invariant, there is nothing to do.  */
     485                 :     3938307 :   else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
     486                 :             :     return evolution_fn;
     487                 :             : 
     488                 :             :   else
     489                 :     3229164 :     return chrec_dont_know;
     490                 :             : }
     491                 :             : 
     492                 :             : /* Associate CHREC to SCALAR.  */
     493                 :             : 
     494                 :             : static void
     495                 :    48799217 : set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
     496                 :             : {
     497                 :    48799217 :   tree *scalar_info;
     498                 :             : 
     499                 :    48799217 :   if (TREE_CODE (scalar) != SSA_NAME)
     500                 :             :     return;
     501                 :             : 
     502                 :    48799217 :   scalar_info = find_var_scev_info (instantiated_below, scalar);
     503                 :             : 
     504                 :    48799217 :   if (dump_file)
     505                 :             :     {
     506                 :       83513 :       if (dump_flags & TDF_SCEV)
     507                 :             :         {
     508                 :           8 :           fprintf (dump_file, "(set_scalar_evolution \n");
     509                 :           8 :           fprintf (dump_file, "  instantiated_below = %d \n",
     510                 :             :                    instantiated_below->index);
     511                 :           8 :           fprintf (dump_file, "  (scalar = ");
     512                 :           8 :           print_generic_expr (dump_file, scalar);
     513                 :           8 :           fprintf (dump_file, ")\n  (scalar_evolution = ");
     514                 :           8 :           print_generic_expr (dump_file, chrec);
     515                 :           8 :           fprintf (dump_file, "))\n");
     516                 :             :         }
     517                 :       83513 :       if (dump_flags & TDF_STATS)
     518                 :        7151 :         nb_set_scev++;
     519                 :             :     }
     520                 :             : 
     521                 :    48799217 :   *scalar_info = chrec;
     522                 :             : }
     523                 :             : 
     524                 :             : /* Retrieve the chrec associated to SCALAR instantiated below
     525                 :             :    INSTANTIATED_BELOW block.  */
     526                 :             : 
     527                 :             : static tree
     528                 :   193027946 : get_scalar_evolution (basic_block instantiated_below, tree scalar)
     529                 :             : {
     530                 :   193027946 :   tree res;
     531                 :             : 
     532                 :   193027946 :   if (dump_file)
     533                 :             :     {
     534                 :      605717 :       if (dump_flags & TDF_SCEV)
     535                 :             :         {
     536                 :          30 :           fprintf (dump_file, "(get_scalar_evolution \n");
     537                 :          30 :           fprintf (dump_file, "  (scalar = ");
     538                 :          30 :           print_generic_expr (dump_file, scalar);
     539                 :          30 :           fprintf (dump_file, ")\n");
     540                 :             :         }
     541                 :      605717 :       if (dump_flags & TDF_STATS)
     542                 :       50501 :         nb_get_scev++;
     543                 :             :     }
     544                 :             : 
     545                 :   193027946 :   if (VECTOR_TYPE_P (TREE_TYPE (scalar))
     546                 :   193027946 :       || TREE_CODE (TREE_TYPE (scalar)) == COMPLEX_TYPE)
     547                 :             :     /* For chrec_dont_know we keep the symbolic form.  */
     548                 :             :     res = scalar;
     549                 :             :   else
     550                 :   192761899 :     switch (TREE_CODE (scalar))
     551                 :             :       {
     552                 :   154997596 :       case SSA_NAME:
     553                 :   154997596 :         if (SSA_NAME_IS_DEFAULT_DEF (scalar))
     554                 :             :           res = scalar;
     555                 :             :         else
     556                 :   153041951 :           res = *find_var_scev_info (instantiated_below, scalar);
     557                 :             :         break;
     558                 :             : 
     559                 :             :       case REAL_CST:
     560                 :             :       case FIXED_CST:
     561                 :             :       case INTEGER_CST:
     562                 :             :         res = scalar;
     563                 :             :         break;
     564                 :             : 
     565                 :             :       default:
     566                 :   193027946 :         res = chrec_not_analyzed_yet;
     567                 :             :         break;
     568                 :             :       }
     569                 :             : 
     570                 :   193027946 :   if (dump_file && (dump_flags & TDF_SCEV))
     571                 :             :     {
     572                 :          30 :       fprintf (dump_file, "  (scalar_evolution = ");
     573                 :          30 :       print_generic_expr (dump_file, res);
     574                 :          30 :       fprintf (dump_file, "))\n");
     575                 :             :     }
     576                 :             : 
     577                 :   193027946 :   return res;
     578                 :             : }
     579                 :             : 
     580                 :             : 
     581                 :             : /* Depth first search algorithm.  */
     582                 :             : 
     583                 :             : enum t_bool {
     584                 :             :   t_false,
     585                 :             :   t_true,
     586                 :             :   t_dont_know
     587                 :             : };
     588                 :             : 
     589                 :             : class scev_dfs
     590                 :             : {
     591                 :             : public:
     592                 :    11407260 :   scev_dfs (class loop *loop_, gphi *phi_, tree init_cond_)
     593                 :    11407260 :       : loop (loop_), loop_phi_node (phi_), init_cond (init_cond_) {}
     594                 :             :   t_bool get_ev (tree *, tree);
     595                 :             : 
     596                 :             : private:
     597                 :             :   t_bool follow_ssa_edge_expr (gimple *, tree, tree *, int);
     598                 :             :   t_bool follow_ssa_edge_binary (gimple *at_stmt,
     599                 :             :                                  tree type, tree rhs0, enum tree_code code,
     600                 :             :                                  tree rhs1, tree *evolution_of_loop, int limit);
     601                 :             :   t_bool follow_ssa_edge_in_condition_phi_branch (int i,
     602                 :             :                                                   gphi *condition_phi,
     603                 :             :                                                   tree *evolution_of_branch,
     604                 :             :                                                   tree init_cond, int limit);
     605                 :             :   t_bool follow_ssa_edge_in_condition_phi (gphi *condition_phi,
     606                 :             :                                            tree *evolution_of_loop, int limit);
     607                 :             :   t_bool follow_ssa_edge_inner_loop_phi (gphi *loop_phi_node,
     608                 :             :                                          tree *evolution_of_loop, int limit);
     609                 :             :   tree add_to_evolution (tree chrec_before, enum tree_code code,
     610                 :             :                          tree to_add, gimple *at_stmt);
     611                 :             :   tree add_to_evolution_1 (tree chrec_before, tree to_add, gimple *at_stmt);
     612                 :             : 
     613                 :             :   class loop *loop;
     614                 :             :   gphi *loop_phi_node;
     615                 :             :   tree init_cond;
     616                 :             : };
     617                 :             : 
     618                 :             : t_bool
     619                 :    11407260 : scev_dfs::get_ev (tree *ev_fn, tree arg)
     620                 :             : {
     621                 :    11407260 :   *ev_fn = chrec_dont_know;
     622                 :    11407260 :   return follow_ssa_edge_expr (loop_phi_node, arg, ev_fn, 0);
     623                 :             : }
     624                 :             : 
     625                 :             : /* Helper function for add_to_evolution.  Returns the evolution
     626                 :             :    function for an assignment of the form "a = b + c", where "a" and
     627                 :             :    "b" are on the strongly connected component.  CHREC_BEFORE is the
     628                 :             :    information that we already have collected up to this point.
     629                 :             :    TO_ADD is the evolution of "c".
     630                 :             : 
     631                 :             :    When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
     632                 :             :    evolution the expression TO_ADD, otherwise construct an evolution
     633                 :             :    part for this loop.  */
     634                 :             : 
     635                 :             : tree
     636                 :     9725744 : scev_dfs::add_to_evolution_1 (tree chrec_before, tree to_add, gimple *at_stmt)
     637                 :             : {
     638                 :     9725744 :   tree type, left, right;
     639                 :     9725744 :   unsigned loop_nb = loop->num;
     640                 :     9725744 :   class loop *chloop;
     641                 :             : 
     642                 :     9725744 :   switch (TREE_CODE (chrec_before))
     643                 :             :     {
     644                 :       99747 :     case POLYNOMIAL_CHREC:
     645                 :       99747 :       chloop = get_chrec_loop (chrec_before);
     646                 :       99747 :       if (chloop == loop
     647                 :       99747 :           || flow_loop_nested_p (chloop, loop))
     648                 :             :         {
     649                 :       99747 :           unsigned var;
     650                 :             : 
     651                 :       99747 :           type = chrec_type (chrec_before);
     652                 :             : 
     653                 :             :           /* When there is no evolution part in this loop, build it.  */
     654                 :       99747 :           if (chloop != loop)
     655                 :             :             {
     656                 :           0 :               var = loop_nb;
     657                 :           0 :               left = chrec_before;
     658                 :           0 :               right = SCALAR_FLOAT_TYPE_P (type)
     659                 :           0 :                 ? build_real (type, dconst0)
     660                 :           0 :                 : build_int_cst (type, 0);
     661                 :             :             }
     662                 :             :           else
     663                 :             :             {
     664                 :       99747 :               var = CHREC_VARIABLE (chrec_before);
     665                 :       99747 :               left = CHREC_LEFT (chrec_before);
     666                 :       99747 :               right = CHREC_RIGHT (chrec_before);
     667                 :             :             }
     668                 :             : 
     669                 :       99747 :           to_add = chrec_convert (type, to_add, at_stmt);
     670                 :       99747 :           right = chrec_convert_rhs (type, right, at_stmt);
     671                 :       99747 :           right = chrec_fold_plus (chrec_type (right), right, to_add);
     672                 :       99747 :           return build_polynomial_chrec (var, left, right);
     673                 :             :         }
     674                 :             :       else
     675                 :             :         {
     676                 :           0 :           gcc_assert (flow_loop_nested_p (loop, chloop));
     677                 :             : 
     678                 :             :           /* Search the evolution in LOOP_NB.  */
     679                 :           0 :           left = add_to_evolution_1 (CHREC_LEFT (chrec_before),
     680                 :             :                                      to_add, at_stmt);
     681                 :           0 :           right = CHREC_RIGHT (chrec_before);
     682                 :           0 :           right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
     683                 :           0 :           return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
     684                 :           0 :                                          left, right);
     685                 :             :         }
     686                 :             : 
     687                 :     9625997 :     default:
     688                 :             :       /* These nodes do not depend on a loop.  */
     689                 :     9625997 :       if (chrec_before == chrec_dont_know)
     690                 :             :         return chrec_dont_know;
     691                 :             : 
     692                 :     9604486 :       left = chrec_before;
     693                 :     9604486 :       right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
     694                 :             :       /* When we add the first evolution we need to replace the symbolic
     695                 :             :          evolution we've put in when the DFS reached the loop PHI node
     696                 :             :          with the initial value.  There's only a limited cases of
     697                 :             :          extra operations ontop of that symbol allowed, namely
     698                 :             :          sign-conversions we can look through.  For other cases we leave
     699                 :             :          the symbolic initial condition which causes build_polynomial_chrec
     700                 :             :          to return chrec_dont_know.  See PR42512, PR66375 and PR107176 for
     701                 :             :          cases we mishandled before.  */
     702                 :     9604486 :       STRIP_NOPS (chrec_before);
     703                 :     9604486 :       if (chrec_before == gimple_phi_result (loop_phi_node))
     704                 :     9603784 :         left = fold_convert (TREE_TYPE (left), init_cond);
     705                 :     9604486 :       return build_polynomial_chrec (loop_nb, left, right);
     706                 :             :     }
     707                 :             : }
     708                 :             : 
     709                 :             : /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
     710                 :             :    of LOOP_NB.
     711                 :             : 
     712                 :             :    Description (provided for completeness, for those who read code in
     713                 :             :    a plane, and for my poor 62 bytes brain that would have forgotten
     714                 :             :    all this in the next two or three months):
     715                 :             : 
     716                 :             :    The algorithm of translation of programs from the SSA representation
     717                 :             :    into the chrecs syntax is based on a pattern matching.  After having
     718                 :             :    reconstructed the overall tree expression for a loop, there are only
     719                 :             :    two cases that can arise:
     720                 :             : 
     721                 :             :    1. a = loop-phi (init, a + expr)
     722                 :             :    2. a = loop-phi (init, expr)
     723                 :             : 
     724                 :             :    where EXPR is either a scalar constant with respect to the analyzed
     725                 :             :    loop (this is a degree 0 polynomial), or an expression containing
     726                 :             :    other loop-phi definitions (these are higher degree polynomials).
     727                 :             : 
     728                 :             :    Examples:
     729                 :             : 
     730                 :             :    1.
     731                 :             :    | init = ...
     732                 :             :    | loop_1
     733                 :             :    |   a = phi (init, a + 5)
     734                 :             :    | endloop
     735                 :             : 
     736                 :             :    2.
     737                 :             :    | inita = ...
     738                 :             :    | initb = ...
     739                 :             :    | loop_1
     740                 :             :    |   a = phi (inita, 2 * b + 3)
     741                 :             :    |   b = phi (initb, b + 1)
     742                 :             :    | endloop
     743                 :             : 
     744                 :             :    For the first case, the semantics of the SSA representation is:
     745                 :             : 
     746                 :             :    | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
     747                 :             : 
     748                 :             :    that is, there is a loop index "x" that determines the scalar value
     749                 :             :    of the variable during the loop execution.  During the first
     750                 :             :    iteration, the value is that of the initial condition INIT, while
     751                 :             :    during the subsequent iterations, it is the sum of the initial
     752                 :             :    condition with the sum of all the values of EXPR from the initial
     753                 :             :    iteration to the before last considered iteration.
     754                 :             : 
     755                 :             :    For the second case, the semantics of the SSA program is:
     756                 :             : 
     757                 :             :    | a (x) = init, if x = 0;
     758                 :             :    |         expr (x - 1), otherwise.
     759                 :             : 
     760                 :             :    The second case corresponds to the PEELED_CHREC, whose syntax is
     761                 :             :    close to the syntax of a loop-phi-node:
     762                 :             : 
     763                 :             :    | phi (init, expr)  vs.  (init, expr)_x
     764                 :             : 
     765                 :             :    The proof of the translation algorithm for the first case is a
     766                 :             :    proof by structural induction based on the degree of EXPR.
     767                 :             : 
     768                 :             :    Degree 0:
     769                 :             :    When EXPR is a constant with respect to the analyzed loop, or in
     770                 :             :    other words when EXPR is a polynomial of degree 0, the evolution of
     771                 :             :    the variable A in the loop is an affine function with an initial
     772                 :             :    condition INIT, and a step EXPR.  In order to show this, we start
     773                 :             :    from the semantics of the SSA representation:
     774                 :             : 
     775                 :             :    f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
     776                 :             : 
     777                 :             :    and since "expr (j)" is a constant with respect to "j",
     778                 :             : 
     779                 :             :    f (x) = init + x * expr
     780                 :             : 
     781                 :             :    Finally, based on the semantics of the pure sum chrecs, by
     782                 :             :    identification we get the corresponding chrecs syntax:
     783                 :             : 
     784                 :             :    f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
     785                 :             :    f (x) -> {init, +, expr}_x
     786                 :             : 
     787                 :             :    Higher degree:
     788                 :             :    Suppose that EXPR is a polynomial of degree N with respect to the
     789                 :             :    analyzed loop_x for which we have already determined that it is
     790                 :             :    written under the chrecs syntax:
     791                 :             : 
     792                 :             :    | expr (x)  ->  {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
     793                 :             : 
     794                 :             :    We start from the semantics of the SSA program:
     795                 :             : 
     796                 :             :    | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
     797                 :             :    |
     798                 :             :    | f (x) = init + \sum_{j = 0}^{x - 1}
     799                 :             :    |                (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
     800                 :             :    |
     801                 :             :    | f (x) = init + \sum_{j = 0}^{x - 1}
     802                 :             :    |                \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
     803                 :             :    |
     804                 :             :    | f (x) = init + \sum_{k = 0}^{n - 1}
     805                 :             :    |                (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
     806                 :             :    |
     807                 :             :    | f (x) = init + \sum_{k = 0}^{n - 1}
     808                 :             :    |                (b_k * \binom{x}{k + 1})
     809                 :             :    |
     810                 :             :    | f (x) = init + b_0 * \binom{x}{1} + ...
     811                 :             :    |              + b_{n-1} * \binom{x}{n}
     812                 :             :    |
     813                 :             :    | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
     814                 :             :    |                             + b_{n-1} * \binom{x}{n}
     815                 :             :    |
     816                 :             : 
     817                 :             :    And finally from the definition of the chrecs syntax, we identify:
     818                 :             :    | f (x)  ->  {init, +, b_0, +, ..., +, b_{n-1}}_x
     819                 :             : 
     820                 :             :    This shows the mechanism that stands behind the add_to_evolution
     821                 :             :    function.  An important point is that the use of symbolic
     822                 :             :    parameters avoids the need of an analysis schedule.
     823                 :             : 
     824                 :             :    Example:
     825                 :             : 
     826                 :             :    | inita = ...
     827                 :             :    | initb = ...
     828                 :             :    | loop_1
     829                 :             :    |   a = phi (inita, a + 2 + b)
     830                 :             :    |   b = phi (initb, b + 1)
     831                 :             :    | endloop
     832                 :             : 
     833                 :             :    When analyzing "a", the algorithm keeps "b" symbolically:
     834                 :             : 
     835                 :             :    | a  ->  {inita, +, 2 + b}_1
     836                 :             : 
     837                 :             :    Then, after instantiation, the analyzer ends on the evolution:
     838                 :             : 
     839                 :             :    | a  ->  {inita, +, 2 + initb, +, 1}_1
     840                 :             : 
     841                 :             : */
     842                 :             : 
     843                 :             : tree
     844                 :     9725744 : scev_dfs::add_to_evolution (tree chrec_before, enum tree_code code,
     845                 :             :                             tree to_add, gimple *at_stmt)
     846                 :             : {
     847                 :     9725744 :   tree type = chrec_type (to_add);
     848                 :     9725744 :   tree res = NULL_TREE;
     849                 :             : 
     850                 :     9725744 :   if (to_add == NULL_TREE)
     851                 :             :     return chrec_before;
     852                 :             : 
     853                 :             :   /* TO_ADD is either a scalar, or a parameter.  TO_ADD is not
     854                 :             :      instantiated at this point.  */
     855                 :     9725744 :   if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
     856                 :             :     /* This should not happen.  */
     857                 :           0 :     return chrec_dont_know;
     858                 :             : 
     859                 :     9725744 :   if (dump_file && (dump_flags & TDF_SCEV))
     860                 :             :     {
     861                 :           0 :       fprintf (dump_file, "(add_to_evolution \n");
     862                 :           0 :       fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
     863                 :           0 :       fprintf (dump_file, "  (chrec_before = ");
     864                 :           0 :       print_generic_expr (dump_file, chrec_before);
     865                 :           0 :       fprintf (dump_file, ")\n  (to_add = ");
     866                 :           0 :       print_generic_expr (dump_file, to_add);
     867                 :           0 :       fprintf (dump_file, ")\n");
     868                 :             :     }
     869                 :             : 
     870                 :     9725744 :   if (code == MINUS_EXPR)
     871                 :     2007914 :     to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
     872                 :        4895 :                                   ? build_real (type, dconstm1)
     873                 :     2003019 :                                   : build_int_cst_type (type, -1));
     874                 :             : 
     875                 :     9725744 :   res = add_to_evolution_1 (chrec_before, to_add, at_stmt);
     876                 :             : 
     877                 :     9725744 :   if (dump_file && (dump_flags & TDF_SCEV))
     878                 :             :     {
     879                 :           0 :       fprintf (dump_file, "  (res = ");
     880                 :           0 :       print_generic_expr (dump_file, res);
     881                 :           0 :       fprintf (dump_file, "))\n");
     882                 :             :     }
     883                 :             : 
     884                 :             :   return res;
     885                 :             : }
     886                 :             : 
     887                 :             : 
     888                 :             : /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
     889                 :             :    Return true if the strongly connected component has been found.  */
     890                 :             : 
     891                 :             : t_bool
     892                 :      961295 : scev_dfs::follow_ssa_edge_binary (gimple *at_stmt, tree type, tree rhs0,
     893                 :             :                                   enum tree_code code, tree rhs1,
     894                 :             :                                   tree *evolution_of_loop, int limit)
     895                 :             : {
     896                 :      961295 :   t_bool res = t_false;
     897                 :      961295 :   tree evol;
     898                 :             : 
     899                 :      961295 :   switch (code)
     900                 :             :     {
     901                 :      957211 :     case POINTER_PLUS_EXPR:
     902                 :      957211 :     case PLUS_EXPR:
     903                 :      957211 :       if (TREE_CODE (rhs0) == SSA_NAME)
     904                 :             :         {
     905                 :      943297 :           if (TREE_CODE (rhs1) == SSA_NAME)
     906                 :             :             {
     907                 :             :               /* Match an assignment under the form:
     908                 :             :                  "a = b + c".  */
     909                 :             : 
     910                 :             :               /* We want only assignments of form "name + name" contribute to
     911                 :             :                  LIMIT, as the other cases do not necessarily contribute to
     912                 :             :                  the complexity of the expression.  */
     913                 :      943297 :               limit++;
     914                 :             : 
     915                 :      943297 :               evol = *evolution_of_loop;
     916                 :      943297 :               res = follow_ssa_edge_expr (at_stmt, rhs0, &evol, limit);
     917                 :      943297 :               if (res == t_true)
     918                 :      394997 :                 *evolution_of_loop = add_to_evolution
     919                 :      394997 :                     (chrec_convert (type, evol, at_stmt), code, rhs1, at_stmt);
     920                 :      548300 :               else if (res == t_false)
     921                 :             :                 {
     922                 :      531912 :                   res = follow_ssa_edge_expr
     923                 :      531912 :                     (at_stmt, rhs1, evolution_of_loop, limit);
     924                 :      531912 :                   if (res == t_true)
     925                 :      392890 :                     *evolution_of_loop = add_to_evolution
     926                 :      392890 :                         (chrec_convert (type, *evolution_of_loop, at_stmt),
     927                 :             :                          code, rhs0, at_stmt);
     928                 :             :                 }
     929                 :             :             }
     930                 :             : 
     931                 :             :           else
     932                 :           0 :             gcc_unreachable ();  /* Handled in caller.  */
     933                 :             :         }
     934                 :             : 
     935                 :       13914 :       else if (TREE_CODE (rhs1) == SSA_NAME)
     936                 :             :         {
     937                 :             :           /* Match an assignment under the form:
     938                 :             :              "a = ... + c".  */
     939                 :        5555 :           res = follow_ssa_edge_expr (at_stmt, rhs1, evolution_of_loop, limit);
     940                 :        5555 :           if (res == t_true)
     941                 :        4852 :             *evolution_of_loop = add_to_evolution
     942                 :        4852 :                 (chrec_convert (type, *evolution_of_loop, at_stmt),
     943                 :             :                  code, rhs0, at_stmt);
     944                 :             :         }
     945                 :             : 
     946                 :             :       else
     947                 :             :         /* Otherwise, match an assignment under the form:
     948                 :             :            "a = ... + ...".  */
     949                 :             :         /* And there is nothing to do.  */
     950                 :             :         res = t_false;
     951                 :             :       break;
     952                 :             : 
     953                 :        4084 :     case MINUS_EXPR:
     954                 :             :       /* This case is under the form "opnd0 = rhs0 - rhs1".  */
     955                 :        4084 :       if (TREE_CODE (rhs0) == SSA_NAME)
     956                 :           0 :         gcc_unreachable (); /* Handled in caller.  */
     957                 :             :       else
     958                 :             :         /* Otherwise, match an assignment under the form:
     959                 :             :            "a = ... - ...".  */
     960                 :             :         /* And there is nothing to do.  */
     961                 :             :         res = t_false;
     962                 :             :       break;
     963                 :             : 
     964                 :             :     default:
     965                 :             :       res = t_false;
     966                 :             :     }
     967                 :             : 
     968                 :      961295 :   return res;
     969                 :             : }
     970                 :             : 
     971                 :             : /* Checks whether the I-th argument of a PHI comes from a backedge.  */
     972                 :             : 
     973                 :             : static bool
     974                 :     7518326 : backedge_phi_arg_p (gphi *phi, int i)
     975                 :             : {
     976                 :     7518326 :   const_edge e = gimple_phi_arg_edge (phi, i);
     977                 :             : 
     978                 :             :   /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
     979                 :             :      about updating it anywhere, and this should work as well most of the
     980                 :             :      time.  */
     981                 :     7518326 :   if (e->flags & EDGE_IRREDUCIBLE_LOOP)
     982                 :       45219 :     return true;
     983                 :             : 
     984                 :             :   return false;
     985                 :             : }
     986                 :             : 
     987                 :             : /* Helper function for one branch of the condition-phi-node.  Return
     988                 :             :    true if the strongly connected component has been found following
     989                 :             :    this path.  */
     990                 :             : 
     991                 :             : t_bool
     992                 :     3012842 : scev_dfs::follow_ssa_edge_in_condition_phi_branch (int i,
     993                 :             :                                                    gphi *condition_phi,
     994                 :             :                                                    tree *evolution_of_branch,
     995                 :             :                                                    tree init_cond, int limit)
     996                 :             : {
     997                 :     3012842 :   tree branch = PHI_ARG_DEF (condition_phi, i);
     998                 :     3012842 :   *evolution_of_branch = chrec_dont_know;
     999                 :             : 
    1000                 :             :   /* Do not follow back edges (they must belong to an irreducible loop, which
    1001                 :             :      we really do not want to worry about).  */
    1002                 :     3012842 :   if (backedge_phi_arg_p (condition_phi, i))
    1003                 :             :     return t_false;
    1004                 :             : 
    1005                 :     3007308 :   if (TREE_CODE (branch) == SSA_NAME)
    1006                 :             :     {
    1007                 :     2794532 :       *evolution_of_branch = init_cond;
    1008                 :     2794532 :       return follow_ssa_edge_expr (condition_phi, branch,
    1009                 :     2794532 :                                    evolution_of_branch, limit);
    1010                 :             :     }
    1011                 :             : 
    1012                 :             :   /* This case occurs when one of the condition branches sets
    1013                 :             :      the variable to a constant: i.e. a phi-node like
    1014                 :             :      "a_2 = PHI <a_7(5), 2(6)>;".
    1015                 :             : 
    1016                 :             :      FIXME:  This case have to be refined correctly:
    1017                 :             :      in some cases it is possible to say something better than
    1018                 :             :      chrec_dont_know, for example using a wrap-around notation.  */
    1019                 :             :   return t_false;
    1020                 :             : }
    1021                 :             : 
    1022                 :             : /* This function merges the branches of a condition-phi-node in a
    1023                 :             :    loop.  */
    1024                 :             : 
    1025                 :             : t_bool
    1026                 :     1958301 : scev_dfs::follow_ssa_edge_in_condition_phi (gphi *condition_phi,
    1027                 :             :                                             tree *evolution_of_loop, int limit)
    1028                 :             : {
    1029                 :     1958301 :   int i, n;
    1030                 :     1958301 :   tree init = *evolution_of_loop;
    1031                 :     1958301 :   tree evolution_of_branch;
    1032                 :     1958301 :   t_bool res = follow_ssa_edge_in_condition_phi_branch (0, condition_phi,
    1033                 :             :                                                         &evolution_of_branch,
    1034                 :             :                                                         init, limit);
    1035                 :     1958301 :   if (res == t_false || res == t_dont_know)
    1036                 :             :     return res;
    1037                 :             : 
    1038                 :     1075421 :   *evolution_of_loop = evolution_of_branch;
    1039                 :             : 
    1040                 :     1075421 :   n = gimple_phi_num_args (condition_phi);
    1041                 :     1557720 :   for (i = 1; i < n; i++)
    1042                 :             :     {
    1043                 :             :       /* Quickly give up when the evolution of one of the branches is
    1044                 :             :          not known.  */
    1045                 :     1166411 :       if (*evolution_of_loop == chrec_dont_know)
    1046                 :             :         return t_true;
    1047                 :             : 
    1048                 :             :       /* Increase the limit by the PHI argument number to avoid exponential
    1049                 :             :          time and memory complexity.  */
    1050                 :     1054541 :       res = follow_ssa_edge_in_condition_phi_branch (i, condition_phi,
    1051                 :             :                                                      &evolution_of_branch,
    1052                 :             :                                                      init, limit + i);
    1053                 :     1054541 :       if (res == t_false || res == t_dont_know)
    1054                 :             :         return res;
    1055                 :             : 
    1056                 :      482299 :       *evolution_of_loop = chrec_merge (*evolution_of_loop,
    1057                 :             :                                         evolution_of_branch);
    1058                 :             :     }
    1059                 :             : 
    1060                 :             :   return t_true;
    1061                 :             : }
    1062                 :             : 
    1063                 :             : /* Follow an SSA edge in an inner loop.  It computes the overall
    1064                 :             :    effect of the loop, and following the symbolic initial conditions,
    1065                 :             :    it follows the edges in the parent loop.  The inner loop is
    1066                 :             :    considered as a single statement.  */
    1067                 :             : 
    1068                 :             : t_bool
    1069                 :      237151 : scev_dfs::follow_ssa_edge_inner_loop_phi (gphi *loop_phi_node,
    1070                 :             :                                           tree *evolution_of_loop, int limit)
    1071                 :             : {
    1072                 :      237151 :   class loop *loop = loop_containing_stmt (loop_phi_node);
    1073                 :      237151 :   tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
    1074                 :             : 
    1075                 :             :   /* Sometimes, the inner loop is too difficult to analyze, and the
    1076                 :             :      result of the analysis is a symbolic parameter.  */
    1077                 :      237151 :   if (ev == PHI_RESULT (loop_phi_node))
    1078                 :             :     {
    1079                 :      100840 :       t_bool res = t_false;
    1080                 :      100840 :       int i, n = gimple_phi_num_args (loop_phi_node);
    1081                 :             : 
    1082                 :      143984 :       for (i = 0; i < n; i++)
    1083                 :             :         {
    1084                 :      136506 :           tree arg = PHI_ARG_DEF (loop_phi_node, i);
    1085                 :      136506 :           basic_block bb;
    1086                 :             : 
    1087                 :             :           /* Follow the edges that exit the inner loop.  */
    1088                 :      136506 :           bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
    1089                 :      136506 :           if (!flow_bb_inside_loop_p (loop, bb))
    1090                 :      100840 :             res = follow_ssa_edge_expr (loop_phi_node,
    1091                 :             :                                         arg, evolution_of_loop, limit);
    1092                 :      136506 :           if (res == t_true)
    1093                 :             :             break;
    1094                 :             :         }
    1095                 :             : 
    1096                 :             :       /* If the path crosses this loop-phi, give up.  */
    1097                 :      100840 :       if (res == t_true)
    1098                 :       93362 :         *evolution_of_loop = chrec_dont_know;
    1099                 :             : 
    1100                 :      100840 :       return res;
    1101                 :             :     }
    1102                 :             : 
    1103                 :             :   /* Otherwise, compute the overall effect of the inner loop.  */
    1104                 :      136311 :   ev = compute_overall_effect_of_inner_loop (loop, ev);
    1105                 :      136311 :   return follow_ssa_edge_expr (loop_phi_node, ev, evolution_of_loop, limit);
    1106                 :             : }
    1107                 :             : 
    1108                 :             : /* Follow the ssa edge into the expression EXPR.
    1109                 :             :    Return true if the strongly connected component has been found.  */
    1110                 :             : 
    1111                 :             : t_bool
    1112                 :    25275502 : scev_dfs::follow_ssa_edge_expr (gimple *at_stmt, tree expr,
    1113                 :             :                                 tree *evolution_of_loop, int limit)
    1114                 :             : {
    1115                 :    25275502 :   gphi *halting_phi = loop_phi_node;
    1116                 :    25275502 :   enum tree_code code;
    1117                 :    25275502 :   tree type, rhs0, rhs1 = NULL_TREE;
    1118                 :             : 
    1119                 :             :   /* The EXPR is one of the following cases:
    1120                 :             :      - an SSA_NAME,
    1121                 :             :      - an INTEGER_CST,
    1122                 :             :      - a PLUS_EXPR,
    1123                 :             :      - a POINTER_PLUS_EXPR,
    1124                 :             :      - a MINUS_EXPR,
    1125                 :             :      - other cases are not yet handled.  */
    1126                 :             : 
    1127                 :             :   /* For SSA_NAME look at the definition statement, handling
    1128                 :             :      PHI nodes and otherwise expand appropriately for the expression
    1129                 :             :      handling below.  */
    1130                 :    25275502 :   if (TREE_CODE (expr) == SSA_NAME)
    1131                 :             :     {
    1132                 :    25128050 :       gimple *def = SSA_NAME_DEF_STMT (expr);
    1133                 :             : 
    1134                 :    25128050 :       if (gimple_nop_p (def))
    1135                 :             :         return t_false;
    1136                 :             : 
    1137                 :             :       /* Give up if the path is longer than the MAX that we allow.  */
    1138                 :    25112663 :       if (limit > param_scev_max_expr_complexity)
    1139                 :             :         {
    1140                 :        6405 :           *evolution_of_loop = chrec_dont_know;
    1141                 :        6405 :           return t_dont_know;
    1142                 :             :         }
    1143                 :             : 
    1144                 :    25106258 :       if (gphi *phi = dyn_cast <gphi *>(def))
    1145                 :             :         {
    1146                 :    25967536 :           if (!loop_phi_node_p (phi))
    1147                 :             :             /* DEF is a condition-phi-node.  Follow the branches, and
    1148                 :             :                record their evolutions.  Finally, merge the collected
    1149                 :             :                information and set the approximation to the main
    1150                 :             :                variable.  */
    1151                 :     1958301 :             return follow_ssa_edge_in_condition_phi (phi, evolution_of_loop,
    1152                 :     1958301 :                                                      limit);
    1153                 :             : 
    1154                 :             :           /* When the analyzed phi is the halting_phi, the
    1155                 :             :              depth-first search is over: we have found a path from
    1156                 :             :              the halting_phi to itself in the loop.  */
    1157                 :    11025467 :           if (phi == halting_phi)
    1158                 :             :             {
    1159                 :    10622332 :               *evolution_of_loop = expr;
    1160                 :    10622332 :               return t_true;
    1161                 :             :             }
    1162                 :             : 
    1163                 :             :           /* Otherwise, the evolution of the HALTING_PHI depends
    1164                 :             :              on the evolution of another loop-phi-node, i.e. the
    1165                 :             :              evolution function is a higher degree polynomial.  */
    1166                 :      403135 :           class loop *def_loop = loop_containing_stmt (def);
    1167                 :      403135 :           if (def_loop == loop)
    1168                 :             :             return t_false;
    1169                 :             : 
    1170                 :             :           /* Inner loop.  */
    1171                 :      256768 :           if (flow_loop_nested_p (loop, def_loop))
    1172                 :      237151 :             return follow_ssa_edge_inner_loop_phi (phi, evolution_of_loop,
    1173                 :      237151 :                                                    limit + 1);
    1174                 :             : 
    1175                 :             :           /* Outer loop.  */
    1176                 :             :           return t_false;
    1177                 :             :         }
    1178                 :             : 
    1179                 :             :       /* At this level of abstraction, the program is just a set
    1180                 :             :          of GIMPLE_ASSIGNs and PHI_NODEs.  In principle there is no
    1181                 :             :          other def to be handled.  */
    1182                 :    12122490 :       if (!is_gimple_assign (def))
    1183                 :             :         return t_false;
    1184                 :             : 
    1185                 :    12022714 :       code = gimple_assign_rhs_code (def);
    1186                 :    12022714 :       switch (get_gimple_rhs_class (code))
    1187                 :             :         {
    1188                 :    10704074 :         case GIMPLE_BINARY_RHS:
    1189                 :    10704074 :           rhs0 = gimple_assign_rhs1 (def);
    1190                 :    10704074 :           rhs1 = gimple_assign_rhs2 (def);
    1191                 :    10704074 :           break;
    1192                 :     1306454 :         case GIMPLE_UNARY_RHS:
    1193                 :     1306454 :         case GIMPLE_SINGLE_RHS:
    1194                 :     1306454 :           rhs0 = gimple_assign_rhs1 (def);
    1195                 :     1306454 :           break;
    1196                 :             :         default:
    1197                 :             :           return t_false;
    1198                 :             :         }
    1199                 :    12010528 :       type = TREE_TYPE (gimple_assign_lhs (def));
    1200                 :    12010528 :       at_stmt = def;
    1201                 :             :     }
    1202                 :             :   else
    1203                 :             :     {
    1204                 :      147452 :       code = TREE_CODE (expr);
    1205                 :      147452 :       type = TREE_TYPE (expr);
    1206                 :             :       /* Via follow_ssa_edge_inner_loop_phi we arrive here with the
    1207                 :             :          GENERIC scalar evolution of the inner loop.  */
    1208                 :      147452 :       switch (code)
    1209                 :             :         {
    1210                 :        9725 :         CASE_CONVERT:
    1211                 :        9725 :           rhs0 = TREE_OPERAND (expr, 0);
    1212                 :        9725 :           break;
    1213                 :       18834 :         case POINTER_PLUS_EXPR:
    1214                 :       18834 :         case PLUS_EXPR:
    1215                 :       18834 :         case MINUS_EXPR:
    1216                 :       18834 :           rhs0 = TREE_OPERAND (expr, 0);
    1217                 :       18834 :           rhs1 = TREE_OPERAND (expr, 1);
    1218                 :       18834 :           STRIP_USELESS_TYPE_CONVERSION (rhs0);
    1219                 :       18834 :           STRIP_USELESS_TYPE_CONVERSION (rhs1);
    1220                 :       18834 :           break;
    1221                 :             :         default:
    1222                 :             :           rhs0 = expr;
    1223                 :             :         }
    1224                 :             :     }
    1225                 :             : 
    1226                 :    12157980 :   switch (code)
    1227                 :             :     {
    1228                 :      307780 :     CASE_CONVERT:
    1229                 :      307780 :       {
    1230                 :             :         /* This assignment is under the form "a_1 = (cast) rhs.  We cannot
    1231                 :             :            validate any precision altering conversion during the SCC
    1232                 :             :            analysis, so don't even try.  */
    1233                 :      307780 :         if (!tree_nop_conversion_p (type, TREE_TYPE (rhs0)))
    1234                 :             :           return t_false;
    1235                 :      207171 :         t_bool res = follow_ssa_edge_expr (at_stmt, rhs0,
    1236                 :             :                                            evolution_of_loop, limit);
    1237                 :      207171 :         if (res == t_true)
    1238                 :      100778 :           *evolution_of_loop = chrec_convert (type, *evolution_of_loop,
    1239                 :             :                                               at_stmt);
    1240                 :             :         return res;
    1241                 :             :       }
    1242                 :             : 
    1243                 :             :     case INTEGER_CST:
    1244                 :             :       /* This assignment is under the form "a_1 = 7".  */
    1245                 :             :       return t_false;
    1246                 :             : 
    1247                 :        1321 :     case ADDR_EXPR:
    1248                 :        1321 :       {
    1249                 :             :         /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR.  */
    1250                 :        1321 :         if (TREE_CODE (TREE_OPERAND (rhs0, 0)) != MEM_REF)
    1251                 :             :           return t_false;
    1252                 :           0 :         tree mem = TREE_OPERAND (rhs0, 0);
    1253                 :           0 :         rhs0 = TREE_OPERAND (mem, 0);
    1254                 :           0 :         rhs1 = TREE_OPERAND (mem, 1);
    1255                 :           0 :         code = POINTER_PLUS_EXPR;
    1256                 :             :       }
    1257                 :             :       /* Fallthru.  */
    1258                 :    10109919 :     case POINTER_PLUS_EXPR:
    1259                 :    10109919 :     case PLUS_EXPR:
    1260                 :    10109919 :     case MINUS_EXPR:
    1261                 :             :       /* This case is under the form "rhs0 +- rhs1".  */
    1262                 :    10109919 :       if (TREE_CODE (rhs0) == SSA_NAME
    1263                 :    10091921 :           && (TREE_CODE (rhs1) != SSA_NAME || code == MINUS_EXPR))
    1264                 :             :         {
    1265                 :             :           /* Match an assignment under the form:
    1266                 :             :              "a = b +- ...".  */
    1267                 :     9148624 :           t_bool res = follow_ssa_edge_expr (at_stmt, rhs0,
    1268                 :             :                                              evolution_of_loop, limit);
    1269                 :     9148624 :           if (res == t_true)
    1270                 :     8933005 :             *evolution_of_loop = add_to_evolution
    1271                 :     8933005 :                 (chrec_convert (type, *evolution_of_loop, at_stmt),
    1272                 :             :                  code, rhs1, at_stmt);
    1273                 :     9148624 :           return res;
    1274                 :             :         }
    1275                 :             :       /* Else search for the SCC in both rhs0 and rhs1.  */
    1276                 :      961295 :       return follow_ssa_edge_binary (at_stmt, type, rhs0, code, rhs1,
    1277                 :      961295 :                                      evolution_of_loop, limit);
    1278                 :             : 
    1279                 :             :     default:
    1280                 :             :       return t_false;
    1281                 :             :     }
    1282                 :             : }
    1283                 :             : 
    1284                 :             : 
    1285                 :             : /* This section selects the loops that will be good candidates for the
    1286                 :             :    scalar evolution analysis.  For the moment, greedily select all the
    1287                 :             :    loop nests we could analyze.  */
    1288                 :             : 
    1289                 :             : /* For a loop with a single exit edge, return the COND_EXPR that
    1290                 :             :    guards the exit edge.  If the expression is too difficult to
    1291                 :             :    analyze, then give up.  */
    1292                 :             : 
    1293                 :             : gcond *
    1294                 :           0 : get_loop_exit_condition (const class loop *loop)
    1295                 :             : {
    1296                 :           0 :   return get_loop_exit_condition (single_exit (loop));
    1297                 :             : }
    1298                 :             : 
    1299                 :             : /* If the statement just before the EXIT_EDGE contains a condition then
    1300                 :             :    return the condition, otherwise NULL. */
    1301                 :             : 
    1302                 :             : gcond *
    1303                 :     6710165 : get_loop_exit_condition (const_edge exit_edge)
    1304                 :             : {
    1305                 :     6710165 :   gcond *res = NULL;
    1306                 :             : 
    1307                 :     6710165 :   if (dump_file && (dump_flags & TDF_SCEV))
    1308                 :           2 :     fprintf (dump_file, "(get_loop_exit_condition \n  ");
    1309                 :             : 
    1310                 :     6710165 :   if (exit_edge)
    1311                 :    20130495 :     res = safe_dyn_cast <gcond *> (*gsi_last_bb (exit_edge->src));
    1312                 :             : 
    1313                 :     6710165 :   if (dump_file && (dump_flags & TDF_SCEV))
    1314                 :             :     {
    1315                 :           2 :       print_gimple_stmt (dump_file, res, 0);
    1316                 :           2 :       fprintf (dump_file, ")\n");
    1317                 :             :     }
    1318                 :             : 
    1319                 :     6710165 :   return res;
    1320                 :             : }
    1321                 :             : 
    1322                 :             : 
    1323                 :             : /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
    1324                 :             :    Handle below case and return the corresponding POLYNOMIAL_CHREC:
    1325                 :             : 
    1326                 :             :    # i_17 = PHI <i_13(5), 0(3)>
    1327                 :             :    # _20 = PHI <_5(5), start_4(D)(3)>
    1328                 :             :    ...
    1329                 :             :    i_13 = i_17 + 1;
    1330                 :             :    _5 = start_4(D) + i_13;
    1331                 :             : 
    1332                 :             :    Though variable _20 appears as a PEELED_CHREC in the form of
    1333                 :             :    (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
    1334                 :             : 
    1335                 :             :    See PR41488.  */
    1336                 :             : 
    1337                 :             : static tree
    1338                 :     1330054 : simplify_peeled_chrec (class loop *loop, tree arg, tree init_cond)
    1339                 :             : {
    1340                 :     2660108 :   aff_tree aff1, aff2;
    1341                 :     1330054 :   tree ev, left, right, type, step_val;
    1342                 :     1330054 :   hash_map<tree, name_expansion *> *peeled_chrec_map = NULL;
    1343                 :             : 
    1344                 :     1330054 :   ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, arg));
    1345                 :     1330054 :   if (ev == NULL_TREE || TREE_CODE (ev) != POLYNOMIAL_CHREC)
    1346                 :     1304661 :     return chrec_dont_know;
    1347                 :             : 
    1348                 :       25393 :   left = CHREC_LEFT (ev);
    1349                 :       25393 :   right = CHREC_RIGHT (ev);
    1350                 :       25393 :   type = TREE_TYPE (left);
    1351                 :       25393 :   step_val = chrec_fold_plus (type, init_cond, right);
    1352                 :             : 
    1353                 :             :   /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
    1354                 :             :      if "left" equals to "init + right".  */
    1355                 :       25393 :   if (operand_equal_p (left, step_val, 0))
    1356                 :             :     {
    1357                 :        9493 :       if (dump_file && (dump_flags & TDF_SCEV))
    1358                 :           1 :         fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
    1359                 :             : 
    1360                 :        9493 :       return build_polynomial_chrec (loop->num, init_cond, right);
    1361                 :             :     }
    1362                 :             : 
    1363                 :             :   /* The affine code only deals with pointer and integer types.  */
    1364                 :       15900 :   if (!POINTER_TYPE_P (type)
    1365                 :       14522 :       && !INTEGRAL_TYPE_P (type))
    1366                 :          15 :     return chrec_dont_know;
    1367                 :             : 
    1368                 :             :   /* Try harder to check if they are equal.  */
    1369                 :       15885 :   tree_to_aff_combination_expand (left, type, &aff1, &peeled_chrec_map);
    1370                 :       15885 :   tree_to_aff_combination_expand (step_val, type, &aff2, &peeled_chrec_map);
    1371                 :       15885 :   free_affine_expand_cache (&peeled_chrec_map);
    1372                 :       15885 :   aff_combination_scale (&aff2, -1);
    1373                 :       15885 :   aff_combination_add (&aff1, &aff2);
    1374                 :             : 
    1375                 :             :   /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
    1376                 :             :      if "left" equals to "init + right".  */
    1377                 :       15885 :   if (aff_combination_zero_p (&aff1))
    1378                 :             :     {
    1379                 :        8543 :       if (dump_file && (dump_flags & TDF_SCEV))
    1380                 :           1 :         fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
    1381                 :             : 
    1382                 :        8543 :       return build_polynomial_chrec (loop->num, init_cond, right);
    1383                 :             :     }
    1384                 :        7342 :   return chrec_dont_know;
    1385                 :     1330054 : }
    1386                 :             : 
    1387                 :             : /* Given a LOOP_PHI_NODE, this function determines the evolution
    1388                 :             :    function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop.  */
    1389                 :             : 
    1390                 :             : static tree
    1391                 :    11524180 : analyze_evolution_in_loop (gphi *loop_phi_node,
    1392                 :             :                            tree init_cond)
    1393                 :             : {
    1394                 :    11524180 :   int i, n = gimple_phi_num_args (loop_phi_node);
    1395                 :    11524180 :   tree evolution_function = chrec_not_analyzed_yet;
    1396                 :    11524180 :   class loop *loop = loop_containing_stmt (loop_phi_node);
    1397                 :    11524180 :   basic_block bb;
    1398                 :    11524180 :   static bool simplify_peeled_chrec_p = true;
    1399                 :             : 
    1400                 :    11524180 :   if (dump_file && (dump_flags & TDF_SCEV))
    1401                 :             :     {
    1402                 :           2 :       fprintf (dump_file, "(analyze_evolution_in_loop \n");
    1403                 :           2 :       fprintf (dump_file, "  (loop_phi_node = ");
    1404                 :           2 :       print_gimple_stmt (dump_file, loop_phi_node, 0);
    1405                 :           2 :       fprintf (dump_file, ")\n");
    1406                 :             :     }
    1407                 :             : 
    1408                 :    31245602 :   for (i = 0; i < n; i++)
    1409                 :             :     {
    1410                 :    21954740 :       tree arg = PHI_ARG_DEF (loop_phi_node, i);
    1411                 :    21954740 :       tree ev_fn = chrec_dont_know;
    1412                 :    21954740 :       t_bool res;
    1413                 :             : 
    1414                 :             :       /* Select the edges that enter the loop body.  */
    1415                 :    21954740 :       bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
    1416                 :    21954740 :       if (!flow_bb_inside_loop_p (loop, bb))
    1417                 :    10430560 :         continue;
    1418                 :             : 
    1419                 :    11524180 :       if (TREE_CODE (arg) == SSA_NAME)
    1420                 :             :         {
    1421                 :    11407260 :           bool val = false;
    1422                 :             : 
    1423                 :             :           /* Pass in the initial condition to the follow edge function.  */
    1424                 :    11407260 :           scev_dfs dfs (loop, loop_phi_node, init_cond);
    1425                 :    11407260 :           res = dfs.get_ev (&ev_fn, arg);
    1426                 :             : 
    1427                 :             :           /* If ev_fn has no evolution in the inner loop, and the
    1428                 :             :              init_cond is not equal to ev_fn, then we have an
    1429                 :             :              ambiguity between two possible values, as we cannot know
    1430                 :             :              the number of iterations at this point.  */
    1431                 :    11407260 :           if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC
    1432                 :     2203110 :               && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
    1433                 :    11407266 :               && !operand_equal_p (init_cond, ev_fn, 0))
    1434                 :           0 :             ev_fn = chrec_dont_know;
    1435                 :             :         }
    1436                 :             :       else
    1437                 :             :         res = t_false;
    1438                 :             : 
    1439                 :             :       /* When it is impossible to go back on the same
    1440                 :             :          loop_phi_node by following the ssa edges, the
    1441                 :             :          evolution is represented by a peeled chrec, i.e. the
    1442                 :             :          first iteration, EV_FN has the value INIT_COND, then
    1443                 :             :          all the other iterations it has the value of ARG.
    1444                 :             :          For the moment, PEELED_CHREC nodes are not built.  */
    1445                 :    11407260 :       if (res != t_true)
    1446                 :             :         {
    1447                 :     1956389 :           ev_fn = chrec_dont_know;
    1448                 :             :           /* Try to recognize POLYNOMIAL_CHREC which appears in
    1449                 :             :              the form of PEELED_CHREC, but guard the process with
    1450                 :             :              a bool variable to keep the analyzer from infinite
    1451                 :             :              recurrence for real PEELED_RECs.  */
    1452                 :     1956389 :           if (simplify_peeled_chrec_p && TREE_CODE (arg) == SSA_NAME)
    1453                 :             :             {
    1454                 :     1330054 :               simplify_peeled_chrec_p = false;
    1455                 :     1330054 :               ev_fn = simplify_peeled_chrec (loop, arg, init_cond);
    1456                 :     1330054 :               simplify_peeled_chrec_p = true;
    1457                 :             :             }
    1458                 :             :         }
    1459                 :             : 
    1460                 :             :       /* When there are multiple back edges of the loop (which in fact never
    1461                 :             :          happens currently, but nevertheless), merge their evolutions.  */
    1462                 :    11524180 :       evolution_function = chrec_merge (evolution_function, ev_fn);
    1463                 :             : 
    1464                 :    11524180 :       if (evolution_function == chrec_dont_know)
    1465                 :             :         break;
    1466                 :             :     }
    1467                 :             : 
    1468                 :    11524180 :   if (dump_file && (dump_flags & TDF_SCEV))
    1469                 :             :     {
    1470                 :           2 :       fprintf (dump_file, "  (evolution_function = ");
    1471                 :           2 :       print_generic_expr (dump_file, evolution_function);
    1472                 :           2 :       fprintf (dump_file, "))\n");
    1473                 :             :     }
    1474                 :             : 
    1475                 :    11524180 :   return evolution_function;
    1476                 :             : }
    1477                 :             : 
    1478                 :             : /* Looks to see if VAR is a copy of a constant (via straightforward assignments
    1479                 :             :    or degenerate phi's).  If so, returns the constant; else, returns VAR.  */
    1480                 :             : 
    1481                 :             : static tree
    1482                 :    22118409 : follow_copies_to_constant (tree var)
    1483                 :             : {
    1484                 :    22118409 :   tree res = var;
    1485                 :    22118409 :   while (TREE_CODE (res) == SSA_NAME
    1486                 :             :          /* We face not updated SSA form in multiple places and this walk
    1487                 :             :             may end up in sibling loops so we have to guard it.  */
    1488                 :    26248751 :          && !name_registered_for_update_p (res))
    1489                 :             :     {
    1490                 :    14801896 :       gimple *def = SSA_NAME_DEF_STMT (res);
    1491                 :    14801896 :       if (gphi *phi = dyn_cast <gphi *> (def))
    1492                 :             :         {
    1493                 :     4173086 :           if (tree rhs = degenerate_phi_result (phi))
    1494                 :             :             res = rhs;
    1495                 :             :           else
    1496                 :             :             break;
    1497                 :             :         }
    1498                 :    10628810 :       else if (gimple_assign_single_p (def))
    1499                 :             :         /* Will exit loop if not an SSA_NAME.  */
    1500                 :     3699922 :         res = gimple_assign_rhs1 (def);
    1501                 :             :       else
    1502                 :             :         break;
    1503                 :             :     }
    1504                 :    22118409 :   if (CONSTANT_CLASS_P (res))
    1505                 :     7637871 :     return res;
    1506                 :             :   return var;
    1507                 :             : }
    1508                 :             : 
    1509                 :             : /* Given a loop-phi-node, return the initial conditions of the
    1510                 :             :    variable on entry of the loop.  When the CCP has propagated
    1511                 :             :    constants into the loop-phi-node, the initial condition is
    1512                 :             :    instantiated, otherwise the initial condition is kept symbolic.
    1513                 :             :    This analyzer does not analyze the evolution outside the current
    1514                 :             :    loop, and leaves this task to the on-demand tree reconstructor.  */
    1515                 :             : 
    1516                 :             : static tree
    1517                 :    11524180 : analyze_initial_condition (gphi *loop_phi_node)
    1518                 :             : {
    1519                 :    11524180 :   int i, n;
    1520                 :    11524180 :   tree init_cond = chrec_not_analyzed_yet;
    1521                 :    11524180 :   class loop *loop = loop_containing_stmt (loop_phi_node);
    1522                 :             : 
    1523                 :    11524180 :   if (dump_file && (dump_flags & TDF_SCEV))
    1524                 :             :     {
    1525                 :           2 :       fprintf (dump_file, "(analyze_initial_condition \n");
    1526                 :           2 :       fprintf (dump_file, "  (loop_phi_node = \n");
    1527                 :           2 :       print_gimple_stmt (dump_file, loop_phi_node, 0);
    1528                 :           2 :       fprintf (dump_file, ")\n");
    1529                 :             :     }
    1530                 :             : 
    1531                 :    11524180 :   n = gimple_phi_num_args (loop_phi_node);
    1532                 :    34572540 :   for (i = 0; i < n; i++)
    1533                 :             :     {
    1534                 :    23048360 :       tree branch = PHI_ARG_DEF (loop_phi_node, i);
    1535                 :    23048360 :       basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
    1536                 :             : 
    1537                 :             :       /* When the branch is oriented to the loop's body, it does
    1538                 :             :          not contribute to the initial condition.  */
    1539                 :    23048360 :       if (flow_bb_inside_loop_p (loop, bb))
    1540                 :    11524180 :         continue;
    1541                 :             : 
    1542                 :    11524180 :       if (init_cond == chrec_not_analyzed_yet)
    1543                 :             :         {
    1544                 :    11524180 :           init_cond = branch;
    1545                 :    11524180 :           continue;
    1546                 :             :         }
    1547                 :             : 
    1548                 :           0 :       if (TREE_CODE (branch) == SSA_NAME)
    1549                 :             :         {
    1550                 :           0 :           init_cond = chrec_dont_know;
    1551                 :           0 :           break;
    1552                 :             :         }
    1553                 :             : 
    1554                 :           0 :       init_cond = chrec_merge (init_cond, branch);
    1555                 :             :     }
    1556                 :             : 
    1557                 :             :   /* Ooops -- a loop without an entry???  */
    1558                 :    11524180 :   if (init_cond == chrec_not_analyzed_yet)
    1559                 :           0 :     init_cond = chrec_dont_know;
    1560                 :             : 
    1561                 :             :   /* We may not have fully constant propagated IL.  Handle degenerate PHIs here
    1562                 :             :      to not miss important early loop unrollings.  */
    1563                 :    11524180 :   init_cond = follow_copies_to_constant (init_cond);
    1564                 :             : 
    1565                 :    11524180 :   if (dump_file && (dump_flags & TDF_SCEV))
    1566                 :             :     {
    1567                 :           2 :       fprintf (dump_file, "  (init_cond = ");
    1568                 :           2 :       print_generic_expr (dump_file, init_cond);
    1569                 :           2 :       fprintf (dump_file, "))\n");
    1570                 :             :     }
    1571                 :             : 
    1572                 :    11524180 :   return init_cond;
    1573                 :             : }
    1574                 :             : 
    1575                 :             : /* Analyze the scalar evolution for LOOP_PHI_NODE.  */
    1576                 :             : 
    1577                 :             : static tree
    1578                 :    11524180 : interpret_loop_phi (class loop *loop, gphi *loop_phi_node)
    1579                 :             : {
    1580                 :    11524180 :   class loop *phi_loop = loop_containing_stmt (loop_phi_node);
    1581                 :    11524180 :   tree init_cond;
    1582                 :             : 
    1583                 :    11524180 :   gcc_assert (phi_loop == loop);
    1584                 :             : 
    1585                 :             :   /* Otherwise really interpret the loop phi.  */
    1586                 :    11524180 :   init_cond = analyze_initial_condition (loop_phi_node);
    1587                 :    11524180 :   return analyze_evolution_in_loop (loop_phi_node, init_cond);
    1588                 :             : }
    1589                 :             : 
    1590                 :             : /* This function merges the branches of a condition-phi-node,
    1591                 :             :    contained in the outermost loop, and whose arguments are already
    1592                 :             :    analyzed.  */
    1593                 :             : 
    1594                 :             : static tree
    1595                 :     2372743 : interpret_condition_phi (class loop *loop, gphi *condition_phi)
    1596                 :             : {
    1597                 :     2372743 :   int i, n = gimple_phi_num_args (condition_phi);
    1598                 :     2372743 :   tree res = chrec_not_analyzed_yet;
    1599                 :             : 
    1600                 :     5041500 :   for (i = 0; i < n; i++)
    1601                 :             :     {
    1602                 :     4505484 :       tree branch_chrec;
    1603                 :             : 
    1604                 :     4505484 :       if (backedge_phi_arg_p (condition_phi, i))
    1605                 :             :         {
    1606                 :       39685 :           res = chrec_dont_know;
    1607                 :       39685 :           break;
    1608                 :             :         }
    1609                 :             : 
    1610                 :     4465799 :       branch_chrec = analyze_scalar_evolution
    1611                 :     4465799 :         (loop, PHI_ARG_DEF (condition_phi, i));
    1612                 :             : 
    1613                 :     4465799 :       res = chrec_merge (res, branch_chrec);
    1614                 :     4465799 :       if (res == chrec_dont_know)
    1615                 :             :         break;
    1616                 :             :     }
    1617                 :             : 
    1618                 :     2372743 :   return res;
    1619                 :             : }
    1620                 :             : 
    1621                 :             : /* Interpret the operation RHS1 OP RHS2.  If we didn't
    1622                 :             :    analyze this node before, follow the definitions until ending
    1623                 :             :    either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node.  On the
    1624                 :             :    return path, this function propagates evolutions (ala constant copy
    1625                 :             :    propagation).  OPND1 is not a GIMPLE expression because we could
    1626                 :             :    analyze the effect of an inner loop: see interpret_loop_phi.  */
    1627                 :             : 
    1628                 :             : static tree
    1629                 :    43750514 : interpret_rhs_expr (class loop *loop, gimple *at_stmt,
    1630                 :             :                     tree type, tree rhs1, enum tree_code code, tree rhs2)
    1631                 :             : {
    1632                 :    43750514 :   tree res, chrec1, chrec2, ctype;
    1633                 :    43750514 :   gimple *def;
    1634                 :             : 
    1635                 :    43750514 :   if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
    1636                 :             :     {
    1637                 :    10573008 :       if (is_gimple_min_invariant (rhs1))
    1638                 :     2723481 :         return chrec_convert (type, rhs1, at_stmt);
    1639                 :             : 
    1640                 :     7849527 :       if (code == SSA_NAME)
    1641                 :      117091 :         return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
    1642                 :      117091 :                               at_stmt);
    1643                 :             :     }
    1644                 :             : 
    1645                 :    40909942 :   switch (code)
    1646                 :             :     {
    1647                 :      286859 :     case ADDR_EXPR:
    1648                 :      286859 :       if (TREE_CODE (TREE_OPERAND (rhs1, 0)) == MEM_REF
    1649                 :      286859 :           || handled_component_p (TREE_OPERAND (rhs1, 0)))
    1650                 :             :         {
    1651                 :      286851 :           machine_mode mode;
    1652                 :      286851 :           poly_int64 bitsize, bitpos;
    1653                 :      286851 :           int unsignedp, reversep;
    1654                 :      286851 :           int volatilep = 0;
    1655                 :      286851 :           tree base, offset;
    1656                 :      286851 :           tree chrec3;
    1657                 :      286851 :           tree unitpos;
    1658                 :             : 
    1659                 :      286851 :           base = get_inner_reference (TREE_OPERAND (rhs1, 0),
    1660                 :             :                                       &bitsize, &bitpos, &offset, &mode,
    1661                 :             :                                       &unsignedp, &reversep, &volatilep);
    1662                 :             : 
    1663                 :      286851 :           if (TREE_CODE (base) == MEM_REF)
    1664                 :             :             {
    1665                 :      210580 :               rhs2 = TREE_OPERAND (base, 1);
    1666                 :      210580 :               rhs1 = TREE_OPERAND (base, 0);
    1667                 :             : 
    1668                 :      210580 :               chrec1 = analyze_scalar_evolution (loop, rhs1);
    1669                 :      210580 :               chrec2 = analyze_scalar_evolution (loop, rhs2);
    1670                 :      210580 :               chrec1 = chrec_convert (type, chrec1, at_stmt);
    1671                 :      210580 :               chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
    1672                 :      210580 :               chrec1 = instantiate_parameters (loop, chrec1);
    1673                 :      210580 :               chrec2 = instantiate_parameters (loop, chrec2);
    1674                 :      210580 :               res = chrec_fold_plus (type, chrec1, chrec2);
    1675                 :             :             }
    1676                 :             :           else
    1677                 :             :             {
    1678                 :       76271 :               chrec1 = analyze_scalar_evolution_for_address_of (loop, base);
    1679                 :       76271 :               chrec1 = chrec_convert (type, chrec1, at_stmt);
    1680                 :       76271 :               res = chrec1;
    1681                 :             :             }
    1682                 :             : 
    1683                 :      286851 :           if (offset != NULL_TREE)
    1684                 :             :             {
    1685                 :      141404 :               chrec2 = analyze_scalar_evolution (loop, offset);
    1686                 :      141404 :               chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt);
    1687                 :      141404 :               chrec2 = instantiate_parameters (loop, chrec2);
    1688                 :      141404 :               res = chrec_fold_plus (type, res, chrec2);
    1689                 :             :             }
    1690                 :             : 
    1691                 :      286851 :           if (maybe_ne (bitpos, 0))
    1692                 :             :             {
    1693                 :      100396 :               unitpos = size_int (exact_div (bitpos, BITS_PER_UNIT));
    1694                 :      100396 :               chrec3 = analyze_scalar_evolution (loop, unitpos);
    1695                 :      100396 :               chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt);
    1696                 :      100396 :               chrec3 = instantiate_parameters (loop, chrec3);
    1697                 :      100396 :               res = chrec_fold_plus (type, res, chrec3);
    1698                 :             :             }
    1699                 :             :         }
    1700                 :             :       else
    1701                 :           8 :         res = chrec_dont_know;
    1702                 :             :       break;
    1703                 :             : 
    1704                 :     3108820 :     case POINTER_PLUS_EXPR:
    1705                 :     3108820 :       chrec1 = analyze_scalar_evolution (loop, rhs1);
    1706                 :     3108820 :       chrec2 = analyze_scalar_evolution (loop, rhs2);
    1707                 :     3108820 :       chrec1 = chrec_convert (type, chrec1, at_stmt);
    1708                 :     3108820 :       chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
    1709                 :     3108820 :       chrec1 = instantiate_parameters (loop, chrec1);
    1710                 :     3108820 :       chrec2 = instantiate_parameters (loop, chrec2);
    1711                 :     3108820 :       res = chrec_fold_plus (type, chrec1, chrec2);
    1712                 :     3108820 :       break;
    1713                 :             : 
    1714                 :    12154259 :     case PLUS_EXPR:
    1715                 :    12154259 :       chrec1 = analyze_scalar_evolution (loop, rhs1);
    1716                 :    12154259 :       chrec2 = analyze_scalar_evolution (loop, rhs2);
    1717                 :    12154259 :       ctype = type;
    1718                 :             :       /* When the stmt is conditionally executed re-write the CHREC
    1719                 :             :          into a form that has well-defined behavior on overflow.  */
    1720                 :    12154259 :       if (at_stmt
    1721                 :    11025562 :           && INTEGRAL_TYPE_P (type)
    1722                 :    10924351 :           && ! TYPE_OVERFLOW_WRAPS (type)
    1723                 :    20689174 :           && ! dominated_by_p (CDI_DOMINATORS, loop->latch,
    1724                 :     8534915 :                                gimple_bb (at_stmt)))
    1725                 :      605936 :         ctype = unsigned_type_for (type);
    1726                 :    12154259 :       chrec1 = chrec_convert (ctype, chrec1, at_stmt);
    1727                 :    12154259 :       chrec2 = chrec_convert (ctype, chrec2, at_stmt);
    1728                 :    12154259 :       chrec1 = instantiate_parameters (loop, chrec1);
    1729                 :    12154259 :       chrec2 = instantiate_parameters (loop, chrec2);
    1730                 :    12154259 :       res = chrec_fold_plus (ctype, chrec1, chrec2);
    1731                 :    12154259 :       if (type != ctype)
    1732                 :      605936 :         res = chrec_convert (type, res, at_stmt);
    1733                 :             :       break;
    1734                 :             : 
    1735                 :     1609188 :     case MINUS_EXPR:
    1736                 :     1609188 :       chrec1 = analyze_scalar_evolution (loop, rhs1);
    1737                 :     1609188 :       chrec2 = analyze_scalar_evolution (loop, rhs2);
    1738                 :     1609188 :       ctype = type;
    1739                 :             :       /* When the stmt is conditionally executed re-write the CHREC
    1740                 :             :          into a form that has well-defined behavior on overflow.  */
    1741                 :     1609188 :       if (at_stmt
    1742                 :     1552717 :           && INTEGRAL_TYPE_P (type)
    1743                 :     1515798 :           && ! TYPE_OVERFLOW_WRAPS (type)
    1744                 :     2071589 :           && ! dominated_by_p (CDI_DOMINATORS,
    1745                 :      462401 :                                loop->latch, gimple_bb (at_stmt)))
    1746                 :       79995 :         ctype = unsigned_type_for (type);
    1747                 :     1609188 :       chrec1 = chrec_convert (ctype, chrec1, at_stmt);
    1748                 :     1609188 :       chrec2 = chrec_convert (ctype, chrec2, at_stmt);
    1749                 :     1609188 :       chrec1 = instantiate_parameters (loop, chrec1);
    1750                 :     1609188 :       chrec2 = instantiate_parameters (loop, chrec2);
    1751                 :     1609188 :       res = chrec_fold_minus (ctype, chrec1, chrec2);
    1752                 :     1609188 :       if (type != ctype)
    1753                 :       79995 :         res = chrec_convert (type, res, at_stmt);
    1754                 :             :       break;
    1755                 :             : 
    1756                 :       74732 :     case NEGATE_EXPR:
    1757                 :       74732 :       chrec1 = analyze_scalar_evolution (loop, rhs1);
    1758                 :       74732 :       ctype = type;
    1759                 :             :       /* When the stmt is conditionally executed re-write the CHREC
    1760                 :             :          into a form that has well-defined behavior on overflow.  */
    1761                 :       74732 :       if (at_stmt
    1762                 :       64583 :           && INTEGRAL_TYPE_P (type)
    1763                 :       62817 :           && ! TYPE_OVERFLOW_WRAPS (type)
    1764                 :      110464 :           && ! dominated_by_p (CDI_DOMINATORS,
    1765                 :       35732 :                                loop->latch, gimple_bb (at_stmt)))
    1766                 :        7732 :         ctype = unsigned_type_for (type);
    1767                 :       74732 :       chrec1 = chrec_convert (ctype, chrec1, at_stmt);
    1768                 :             :       /* TYPE may be integer, real or complex, so use fold_convert.  */
    1769                 :       74732 :       chrec1 = instantiate_parameters (loop, chrec1);
    1770                 :       74732 :       res = chrec_fold_multiply (ctype, chrec1,
    1771                 :             :                                  fold_convert (ctype, integer_minus_one_node));
    1772                 :       74732 :       if (type != ctype)
    1773                 :        7732 :         res = chrec_convert (type, res, at_stmt);
    1774                 :             :       break;
    1775                 :             : 
    1776                 :       26262 :     case BIT_NOT_EXPR:
    1777                 :             :       /* Handle ~X as -1 - X.  */
    1778                 :       26262 :       chrec1 = analyze_scalar_evolution (loop, rhs1);
    1779                 :       26262 :       chrec1 = chrec_convert (type, chrec1, at_stmt);
    1780                 :       26262 :       chrec1 = instantiate_parameters (loop, chrec1);
    1781                 :       26262 :       res = chrec_fold_minus (type,
    1782                 :             :                               fold_convert (type, integer_minus_one_node),
    1783                 :             :                               chrec1);
    1784                 :       26262 :       break;
    1785                 :             : 
    1786                 :     5601968 :     case MULT_EXPR:
    1787                 :     5601968 :       chrec1 = analyze_scalar_evolution (loop, rhs1);
    1788                 :     5601968 :       chrec2 = analyze_scalar_evolution (loop, rhs2);
    1789                 :     5601968 :       ctype = type;
    1790                 :             :       /* When the stmt is conditionally executed re-write the CHREC
    1791                 :             :          into a form that has well-defined behavior on overflow.  */
    1792                 :     5601968 :       if (at_stmt
    1793                 :     3773599 :           && INTEGRAL_TYPE_P (type)
    1794                 :     3654629 :           && ! TYPE_OVERFLOW_WRAPS (type)
    1795                 :     7249594 :           && ! dominated_by_p (CDI_DOMINATORS,
    1796                 :     1647626 :                                loop->latch, gimple_bb (at_stmt)))
    1797                 :      151481 :         ctype = unsigned_type_for (type);
    1798                 :     5601968 :       chrec1 = chrec_convert (ctype, chrec1, at_stmt);
    1799                 :     5601968 :       chrec2 = chrec_convert (ctype, chrec2, at_stmt);
    1800                 :     5601968 :       chrec1 = instantiate_parameters (loop, chrec1);
    1801                 :     5601968 :       chrec2 = instantiate_parameters (loop, chrec2);
    1802                 :     5601968 :       res = chrec_fold_multiply (ctype, chrec1, chrec2);
    1803                 :     5601968 :       if (type != ctype)
    1804                 :      151481 :         res = chrec_convert (type, res, at_stmt);
    1805                 :             :       break;
    1806                 :             : 
    1807                 :      161256 :     case LSHIFT_EXPR:
    1808                 :      161256 :       {
    1809                 :             :         /* Handle A<<B as A * (1<<B).  */
    1810                 :      161256 :         tree uns = unsigned_type_for (type);
    1811                 :      161256 :         chrec1 = analyze_scalar_evolution (loop, rhs1);
    1812                 :      161256 :         chrec2 = analyze_scalar_evolution (loop, rhs2);
    1813                 :      161256 :         chrec1 = chrec_convert (uns, chrec1, at_stmt);
    1814                 :      161256 :         chrec1 = instantiate_parameters (loop, chrec1);
    1815                 :      161256 :         chrec2 = instantiate_parameters (loop, chrec2);
    1816                 :             : 
    1817                 :      161256 :         tree one = build_int_cst (uns, 1);
    1818                 :      161256 :         chrec2 = fold_build2 (LSHIFT_EXPR, uns, one, chrec2);
    1819                 :      161256 :         res = chrec_fold_multiply (uns, chrec1, chrec2);
    1820                 :      161256 :         res = chrec_convert (type, res, at_stmt);
    1821                 :             :       }
    1822                 :      161256 :       break;
    1823                 :             : 
    1824                 :     8372731 :     CASE_CONVERT:
    1825                 :             :       /* In case we have a truncation of a widened operation that in
    1826                 :             :          the truncated type has undefined overflow behavior analyze
    1827                 :             :          the operation done in an unsigned type of the same precision
    1828                 :             :          as the final truncation.  We cannot derive a scalar evolution
    1829                 :             :          for the widened operation but for the truncated result.  */
    1830                 :     8372731 :       if (TREE_CODE (type) == INTEGER_TYPE
    1831                 :     8112325 :           && TREE_CODE (TREE_TYPE (rhs1)) == INTEGER_TYPE
    1832                 :     7646113 :           && TYPE_PRECISION (type) < TYPE_PRECISION (TREE_TYPE (rhs1))
    1833                 :      418269 :           && TYPE_OVERFLOW_UNDEFINED (type)
    1834                 :      240731 :           && TREE_CODE (rhs1) == SSA_NAME
    1835                 :      240573 :           && (def = SSA_NAME_DEF_STMT (rhs1))
    1836                 :      240573 :           && is_gimple_assign (def)
    1837                 :      152399 :           && TREE_CODE_CLASS (gimple_assign_rhs_code (def)) == tcc_binary
    1838                 :     8482193 :           && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST)
    1839                 :             :         {
    1840                 :       77740 :           tree utype = unsigned_type_for (type);
    1841                 :       77740 :           chrec1 = interpret_rhs_expr (loop, at_stmt, utype,
    1842                 :             :                                        gimple_assign_rhs1 (def),
    1843                 :             :                                        gimple_assign_rhs_code (def),
    1844                 :             :                                        gimple_assign_rhs2 (def));
    1845                 :             :         }
    1846                 :             :       else
    1847                 :     8294991 :         chrec1 = analyze_scalar_evolution (loop, rhs1);
    1848                 :     8372731 :       res = chrec_convert (type, chrec1, at_stmt, true, rhs1);
    1849                 :     8372731 :       break;
    1850                 :             : 
    1851                 :      360683 :     case BIT_AND_EXPR:
    1852                 :             :       /* Given int variable A, handle A&0xffff as (int)(unsigned short)A.
    1853                 :             :          If A is SCEV and its value is in the range of representable set
    1854                 :             :          of type unsigned short, the result expression is a (no-overflow)
    1855                 :             :          SCEV.  */
    1856                 :      360683 :       res = chrec_dont_know;
    1857                 :      360683 :       if (tree_fits_uhwi_p (rhs2))
    1858                 :             :         {
    1859                 :      239969 :           int precision;
    1860                 :      239969 :           unsigned HOST_WIDE_INT val = tree_to_uhwi (rhs2);
    1861                 :             : 
    1862                 :      239969 :           val ++;
    1863                 :             :           /* Skip if value of rhs2 wraps in unsigned HOST_WIDE_INT or
    1864                 :             :              it's not the maximum value of a smaller type than rhs1.  */
    1865                 :      239969 :           if (val != 0
    1866                 :      182901 :               && (precision = exact_log2 (val)) > 0
    1867                 :      422870 :               && (unsigned) precision < TYPE_PRECISION (TREE_TYPE (rhs1)))
    1868                 :             :             {
    1869                 :      182901 :               tree utype = build_nonstandard_integer_type (precision, 1);
    1870                 :             : 
    1871                 :      182901 :               if (TYPE_PRECISION (utype) < TYPE_PRECISION (TREE_TYPE (rhs1)))
    1872                 :             :                 {
    1873                 :      182901 :                   chrec1 = analyze_scalar_evolution (loop, rhs1);
    1874                 :      182901 :                   chrec1 = chrec_convert (utype, chrec1, at_stmt);
    1875                 :      182901 :                   res = chrec_convert (TREE_TYPE (rhs1), chrec1, at_stmt);
    1876                 :             :                 }
    1877                 :             :             }
    1878                 :             :         }
    1879                 :             :       break;
    1880                 :             : 
    1881                 :     9153184 :     default:
    1882                 :     9153184 :       res = chrec_dont_know;
    1883                 :     9153184 :       break;
    1884                 :             :     }
    1885                 :             : 
    1886                 :             :   return res;
    1887                 :             : }
    1888                 :             : 
    1889                 :             : /* Interpret the expression EXPR.  */
    1890                 :             : 
    1891                 :             : static tree
    1892                 :     9375134 : interpret_expr (class loop *loop, gimple *at_stmt, tree expr)
    1893                 :             : {
    1894                 :     9375134 :   enum tree_code code;
    1895                 :     9375134 :   tree type = TREE_TYPE (expr), op0, op1;
    1896                 :             : 
    1897                 :     9375134 :   if (automatically_generated_chrec_p (expr))
    1898                 :             :     return expr;
    1899                 :             : 
    1900                 :     9370234 :   if (TREE_CODE (expr) == POLYNOMIAL_CHREC
    1901                 :     9369808 :       || TREE_CODE (expr) == CALL_EXPR
    1902                 :    18739995 :       || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
    1903                 :             :     return chrec_dont_know;
    1904                 :             : 
    1905                 :     9299199 :   extract_ops_from_tree (expr, &code, &op0, &op1);
    1906                 :             : 
    1907                 :     9299199 :   return interpret_rhs_expr (loop, at_stmt, type,
    1908                 :     9299199 :                              op0, code, op1);
    1909                 :             : }
    1910                 :             : 
    1911                 :             : /* Interpret the rhs of the assignment STMT.  */
    1912                 :             : 
    1913                 :             : static tree
    1914                 :    34373575 : interpret_gimple_assign (class loop *loop, gimple *stmt)
    1915                 :             : {
    1916                 :    34373575 :   tree type = TREE_TYPE (gimple_assign_lhs (stmt));
    1917                 :    34373575 :   enum tree_code code = gimple_assign_rhs_code (stmt);
    1918                 :             : 
    1919                 :    34373575 :   return interpret_rhs_expr (loop, stmt, type,
    1920                 :             :                              gimple_assign_rhs1 (stmt), code,
    1921                 :    34373575 :                              gimple_assign_rhs2 (stmt));
    1922                 :             : }
    1923                 :             : 
    1924                 :             : 
    1925                 :             : 
    1926                 :             : /* This section contains all the entry points:
    1927                 :             :    - number_of_iterations_in_loop,
    1928                 :             :    - analyze_scalar_evolution,
    1929                 :             :    - instantiate_parameters.
    1930                 :             : */
    1931                 :             : 
    1932                 :             : /* Helper recursive function.  */
    1933                 :             : 
    1934                 :             : static tree
    1935                 :    72448791 : analyze_scalar_evolution_1 (class loop *loop, tree var)
    1936                 :             : {
    1937                 :    72448791 :   gimple *def;
    1938                 :    72448791 :   basic_block bb;
    1939                 :    72448791 :   class loop *def_loop;
    1940                 :    72448791 :   tree res;
    1941                 :             : 
    1942                 :    72448791 :   if (TREE_CODE (var) != SSA_NAME)
    1943                 :     9375134 :     return interpret_expr (loop, NULL, var);
    1944                 :             : 
    1945                 :    63073657 :   def = SSA_NAME_DEF_STMT (var);
    1946                 :    63073657 :   bb = gimple_bb (def);
    1947                 :    63073657 :   def_loop = bb->loop_father;
    1948                 :             : 
    1949                 :    63073657 :   if (!flow_bb_inside_loop_p (loop, bb))
    1950                 :             :     {
    1951                 :             :       /* Keep symbolic form, but look through obvious copies for constants.  */
    1952                 :    10594229 :       res = follow_copies_to_constant (var);
    1953                 :    10594229 :       goto set_and_end;
    1954                 :             :     }
    1955                 :             : 
    1956                 :    52479428 :   if (loop != def_loop)
    1957                 :             :     {
    1958                 :     3680211 :       res = analyze_scalar_evolution_1 (def_loop, var);
    1959                 :     3680211 :       class loop *loop_to_skip = superloop_at_depth (def_loop,
    1960                 :     3680211 :                                                       loop_depth (loop) + 1);
    1961                 :     3680211 :       res = compute_overall_effect_of_inner_loop (loop_to_skip, res);
    1962                 :     3680211 :       if (chrec_contains_symbols_defined_in_loop (res, loop->num))
    1963                 :      275644 :         res = analyze_scalar_evolution_1 (loop, res);
    1964                 :     3680211 :       goto set_and_end;
    1965                 :             :     }
    1966                 :             : 
    1967                 :    48799217 :   switch (gimple_code (def))
    1968                 :             :     {
    1969                 :    34373575 :     case GIMPLE_ASSIGN:
    1970                 :    34373575 :       res = interpret_gimple_assign (loop, def);
    1971                 :    34373575 :       break;
    1972                 :             : 
    1973                 :    13896923 :     case GIMPLE_PHI:
    1974                 :    27793846 :       if (loop_phi_node_p (def))
    1975                 :    11524180 :         res = interpret_loop_phi (loop, as_a <gphi *> (def));
    1976                 :             :       else
    1977                 :     2372743 :         res = interpret_condition_phi (loop, as_a <gphi *> (def));
    1978                 :             :       break;
    1979                 :             : 
    1980                 :      528719 :     default:
    1981                 :      528719 :       res = chrec_dont_know;
    1982                 :      528719 :       break;
    1983                 :             :     }
    1984                 :             : 
    1985                 :    63073657 :  set_and_end:
    1986                 :             : 
    1987                 :             :   /* Keep the symbolic form.  */
    1988                 :    63073657 :   if (res == chrec_dont_know)
    1989                 :    21796663 :     res = var;
    1990                 :             : 
    1991                 :    63073657 :   if (loop == def_loop)
    1992                 :    48799217 :     set_scalar_evolution (block_before_loop (loop), var, res);
    1993                 :             : 
    1994                 :             :   return res;
    1995                 :             : }
    1996                 :             : 
    1997                 :             : /* Analyzes and returns the scalar evolution of the ssa_name VAR in
    1998                 :             :    LOOP.  LOOP is the loop in which the variable is used.
    1999                 :             : 
    2000                 :             :    Example of use: having a pointer VAR to a SSA_NAME node, STMT a
    2001                 :             :    pointer to the statement that uses this variable, in order to
    2002                 :             :    determine the evolution function of the variable, use the following
    2003                 :             :    calls:
    2004                 :             : 
    2005                 :             :    loop_p loop = loop_containing_stmt (stmt);
    2006                 :             :    tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
    2007                 :             :    tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
    2008                 :             : */
    2009                 :             : 
    2010                 :             : tree
    2011                 :   193144228 : analyze_scalar_evolution (class loop *loop, tree var)
    2012                 :             : {
    2013                 :   193144228 :   tree res;
    2014                 :             : 
    2015                 :             :   /* ???  Fix callers.  */
    2016                 :   193144228 :   if (! loop)
    2017                 :             :     return var;
    2018                 :             : 
    2019                 :   193027946 :   if (dump_file && (dump_flags & TDF_SCEV))
    2020                 :             :     {
    2021                 :          30 :       fprintf (dump_file, "(analyze_scalar_evolution \n");
    2022                 :          30 :       fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
    2023                 :          30 :       fprintf (dump_file, "  (scalar = ");
    2024                 :          30 :       print_generic_expr (dump_file, var);
    2025                 :          30 :       fprintf (dump_file, ")\n");
    2026                 :             :     }
    2027                 :             : 
    2028                 :   193027946 :   res = get_scalar_evolution (block_before_loop (loop), var);
    2029                 :   193027946 :   if (res == chrec_not_analyzed_yet)
    2030                 :             :     {
    2031                 :             :       /* We'll recurse into instantiate_scev, avoid tearing down the
    2032                 :             :          instantiate cache repeatedly and keep it live from here.  */
    2033                 :    68492936 :       bool destr = false;
    2034                 :    68492936 :       if (!global_cache)
    2035                 :             :         {
    2036                 :    42184691 :           global_cache = new instantiate_cache_type;
    2037                 :    42184691 :           destr = true;
    2038                 :             :         }
    2039                 :    68492936 :       res = analyze_scalar_evolution_1 (loop, var);
    2040                 :    68492936 :       if (destr)
    2041                 :             :         {
    2042                 :    42184691 :           delete global_cache;
    2043                 :    42184691 :           global_cache = NULL;
    2044                 :             :         }
    2045                 :             :     }
    2046                 :             : 
    2047                 :   193027946 :   if (dump_file && (dump_flags & TDF_SCEV))
    2048                 :          30 :     fprintf (dump_file, ")\n");
    2049                 :             : 
    2050                 :             :   return res;
    2051                 :             : }
    2052                 :             : 
    2053                 :             : /* If CHREC doesn't overflow, set the nonwrapping flag.  */
    2054                 :             : 
    2055                 :    12731733 : void record_nonwrapping_chrec (tree chrec)
    2056                 :             : {
    2057                 :    12731733 :   CHREC_NOWRAP(chrec) = 1;
    2058                 :             : 
    2059                 :    12731733 :   if (dump_file && (dump_flags & TDF_SCEV))
    2060                 :             :     {
    2061                 :           6 :       fprintf (dump_file, "(record_nonwrapping_chrec: ");
    2062                 :           6 :       print_generic_expr (dump_file, chrec);
    2063                 :           6 :       fprintf (dump_file, ")\n");
    2064                 :             :     }
    2065                 :    12731733 : }
    2066                 :             : 
    2067                 :             : /* Return true if CHREC's nonwrapping flag is set.  */
    2068                 :             : 
    2069                 :      182000 : bool nonwrapping_chrec_p (tree chrec)
    2070                 :             : {
    2071                 :      182000 :   if (!chrec || TREE_CODE(chrec) != POLYNOMIAL_CHREC)
    2072                 :             :     return false;
    2073                 :             : 
    2074                 :      182000 :   return CHREC_NOWRAP(chrec);
    2075                 :             : }
    2076                 :             : 
    2077                 :             : /* Analyzes and returns the scalar evolution of VAR address in LOOP.  */
    2078                 :             : 
    2079                 :             : static tree
    2080                 :       76271 : analyze_scalar_evolution_for_address_of (class loop *loop, tree var)
    2081                 :             : {
    2082                 :       76271 :   return analyze_scalar_evolution (loop, build_fold_addr_expr (var));
    2083                 :             : }
    2084                 :             : 
    2085                 :             : /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
    2086                 :             :    WRTO_LOOP (which should be a superloop of USE_LOOP)
    2087                 :             : 
    2088                 :             :    FOLDED_CASTS is set to true if resolve_mixers used
    2089                 :             :    chrec_convert_aggressive (TODO -- not really, we are way too conservative
    2090                 :             :    at the moment in order to keep things simple).
    2091                 :             : 
    2092                 :             :    To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
    2093                 :             :    example:
    2094                 :             : 
    2095                 :             :    for (i = 0; i < 100; i++)                 -- loop 1
    2096                 :             :      {
    2097                 :             :        for (j = 0; j < 100; j++)             -- loop 2
    2098                 :             :          {
    2099                 :             :            k1 = i;
    2100                 :             :            k2 = j;
    2101                 :             : 
    2102                 :             :            use2 (k1, k2);
    2103                 :             : 
    2104                 :             :            for (t = 0; t < 100; t++)         -- loop 3
    2105                 :             :              use3 (k1, k2);
    2106                 :             : 
    2107                 :             :          }
    2108                 :             :        use1 (k1, k2);
    2109                 :             :      }
    2110                 :             : 
    2111                 :             :    Both k1 and k2 are invariants in loop3, thus
    2112                 :             :      analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
    2113                 :             :      analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
    2114                 :             : 
    2115                 :             :    As they are invariant, it does not matter whether we consider their
    2116                 :             :    usage in loop 3 or loop 2, hence
    2117                 :             :      analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
    2118                 :             :        analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
    2119                 :             :      analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
    2120                 :             :        analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
    2121                 :             : 
    2122                 :             :    Similarly for their evolutions with respect to loop 1.  The values of K2
    2123                 :             :    in the use in loop 2 vary independently on loop 1, thus we cannot express
    2124                 :             :    the evolution with respect to loop 1:
    2125                 :             :      analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
    2126                 :             :        analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
    2127                 :             :      analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
    2128                 :             :        analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
    2129                 :             : 
    2130                 :             :    The value of k2 in the use in loop 1 is known, though:
    2131                 :             :      analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
    2132                 :             :      analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
    2133                 :             :    */
    2134                 :             : 
    2135                 :             : static tree
    2136                 :    52482542 : analyze_scalar_evolution_in_loop (class loop *wrto_loop, class loop *use_loop,
    2137                 :             :                                   tree version, bool *folded_casts)
    2138                 :             : {
    2139                 :    52482542 :   bool val = false;
    2140                 :    52482542 :   tree ev = version, tmp;
    2141                 :             : 
    2142                 :             :   /* We cannot just do
    2143                 :             : 
    2144                 :             :      tmp = analyze_scalar_evolution (use_loop, version);
    2145                 :             :      ev = resolve_mixers (wrto_loop, tmp, folded_casts);
    2146                 :             : 
    2147                 :             :      as resolve_mixers would query the scalar evolution with respect to
    2148                 :             :      wrto_loop.  For example, in the situation described in the function
    2149                 :             :      comment, suppose that wrto_loop = loop1, use_loop = loop3 and
    2150                 :             :      version = k2.  Then
    2151                 :             : 
    2152                 :             :      analyze_scalar_evolution (use_loop, version) = k2
    2153                 :             : 
    2154                 :             :      and resolve_mixers (loop1, k2, folded_casts) finds that the value of
    2155                 :             :      k2 in loop 1 is 100, which is a wrong result, since we are interested
    2156                 :             :      in the value in loop 3.
    2157                 :             : 
    2158                 :             :      Instead, we need to proceed from use_loop to wrto_loop loop by loop,
    2159                 :             :      each time checking that there is no evolution in the inner loop.  */
    2160                 :             : 
    2161                 :    52482542 :   if (folded_casts)
    2162                 :    52482542 :     *folded_casts = false;
    2163                 :    54676162 :   while (1)
    2164                 :             :     {
    2165                 :    53579352 :       tmp = analyze_scalar_evolution (use_loop, ev);
    2166                 :    53579352 :       ev = resolve_mixers (use_loop, tmp, folded_casts);
    2167                 :             : 
    2168                 :    53579352 :       if (use_loop == wrto_loop)
    2169                 :             :         return ev;
    2170                 :             : 
    2171                 :             :       /* If the value of the use changes in the inner loop, we cannot express
    2172                 :             :          its value in the outer loop (we might try to return interval chrec,
    2173                 :             :          but we do not have a user for it anyway)  */
    2174                 :     4124960 :       if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
    2175                 :     4124960 :           || !val)
    2176                 :     3028150 :         return chrec_dont_know;
    2177                 :             : 
    2178                 :     1096810 :       use_loop = loop_outer (use_loop);
    2179                 :             :     }
    2180                 :             : }
    2181                 :             : 
    2182                 :             : 
    2183                 :             : /* Computes a hash function for database element ELT.  */
    2184                 :             : 
    2185                 :             : static inline hashval_t
    2186                 :      285471 : hash_idx_scev_info (const void *elt_)
    2187                 :             : {
    2188                 :      285471 :   unsigned idx = ((size_t) elt_) - 2;
    2189                 :      285471 :   return scev_info_hasher::hash (&global_cache->entries[idx]);
    2190                 :             : }
    2191                 :             : 
    2192                 :             : /* Compares database elements E1 and E2.  */
    2193                 :             : 
    2194                 :             : static inline int
    2195                 :    28342685 : eq_idx_scev_info (const void *e1, const void *e2)
    2196                 :             : {
    2197                 :    28342685 :   unsigned idx1 = ((size_t) e1) - 2;
    2198                 :    28342685 :   return scev_info_hasher::equal (&global_cache->entries[idx1],
    2199                 :    28342685 :                                   (const scev_info_str *) e2);
    2200                 :             : }
    2201                 :             : 
    2202                 :             : /* Returns from CACHE the slot number of the cached chrec for NAME.  */
    2203                 :             : 
    2204                 :             : static unsigned
    2205                 :    56747054 : get_instantiated_value_entry (instantiate_cache_type &cache,
    2206                 :             :                               tree name, edge instantiate_below)
    2207                 :             : {
    2208                 :    56747054 :   if (!cache.map)
    2209                 :             :     {
    2210                 :    26234623 :       cache.map = htab_create (10, hash_idx_scev_info, eq_idx_scev_info, NULL);
    2211                 :    26234623 :       cache.entries.create (10);
    2212                 :             :     }
    2213                 :             : 
    2214                 :    56747054 :   scev_info_str e;
    2215                 :    56747054 :   e.name_version = SSA_NAME_VERSION (name);
    2216                 :    56747054 :   e.instantiated_below = instantiate_below->dest->index;
    2217                 :    56747054 :   void **slot = htab_find_slot_with_hash (cache.map, &e,
    2218                 :             :                                           scev_info_hasher::hash (&e), INSERT);
    2219                 :    56747054 :   if (!*slot)
    2220                 :             :     {
    2221                 :    29425296 :       e.chrec = chrec_not_analyzed_yet;
    2222                 :    29425296 :       *slot = (void *)(size_t)(cache.entries.length () + 2);
    2223                 :    29425296 :       cache.entries.safe_push (e);
    2224                 :             :     }
    2225                 :             : 
    2226                 :    56747054 :   return ((size_t)*slot) - 2;
    2227                 :             : }
    2228                 :             : 
    2229                 :             : 
    2230                 :             : /* Return the closed_loop_phi node for VAR.  If there is none, return
    2231                 :             :    NULL_TREE.  */
    2232                 :             : 
    2233                 :             : static tree
    2234                 :     1775029 : loop_closed_phi_def (tree var)
    2235                 :             : {
    2236                 :     1775029 :   class loop *loop;
    2237                 :     1775029 :   edge exit;
    2238                 :     1775029 :   gphi *phi;
    2239                 :     1775029 :   gphi_iterator psi;
    2240                 :             : 
    2241                 :     1775029 :   if (var == NULL_TREE
    2242                 :     1775029 :       || TREE_CODE (var) != SSA_NAME)
    2243                 :             :     return NULL_TREE;
    2244                 :             : 
    2245                 :     1775029 :   loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
    2246                 :     1775029 :   exit = single_exit (loop);
    2247                 :     1775029 :   if (!exit)
    2248                 :             :     return NULL_TREE;
    2249                 :             : 
    2250                 :     1434505 :   for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
    2251                 :             :     {
    2252                 :      873546 :       phi = psi.phi ();
    2253                 :      873546 :       if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
    2254                 :      229124 :         return PHI_RESULT (phi);
    2255                 :             :     }
    2256                 :             : 
    2257                 :             :   return NULL_TREE;
    2258                 :             : }
    2259                 :             : 
    2260                 :             : static tree instantiate_scev_r (edge, class loop *, class loop *,
    2261                 :             :                                 tree, bool *, int);
    2262                 :             : 
    2263                 :             : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
    2264                 :             :    and EVOLUTION_LOOP, that were left under a symbolic form.
    2265                 :             : 
    2266                 :             :    CHREC is an SSA_NAME to be instantiated.
    2267                 :             : 
    2268                 :             :    CACHE is the cache of already instantiated values.
    2269                 :             : 
    2270                 :             :    Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
    2271                 :             :    conversions that may wrap in signed/pointer type are folded, as long
    2272                 :             :    as the value of the chrec is preserved.  If FOLD_CONVERSIONS is NULL
    2273                 :             :    then we don't do such fold.
    2274                 :             : 
    2275                 :             :    SIZE_EXPR is used for computing the size of the expression to be
    2276                 :             :    instantiated, and to stop if it exceeds some limit.  */
    2277                 :             : 
    2278                 :             : static tree
    2279                 :   101510822 : instantiate_scev_name (edge instantiate_below,
    2280                 :             :                        class loop *evolution_loop, class loop *inner_loop,
    2281                 :             :                        tree chrec,
    2282                 :             :                        bool *fold_conversions,
    2283                 :             :                        int size_expr)
    2284                 :             : {
    2285                 :   101510822 :   tree res;
    2286                 :   101510822 :   class loop *def_loop;
    2287                 :   101510822 :   basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
    2288                 :             : 
    2289                 :             :   /* A parameter, nothing to do.  */
    2290                 :   101510822 :   if (!def_bb
    2291                 :   101510822 :       || !dominated_by_p (CDI_DOMINATORS, def_bb, instantiate_below->dest))
    2292                 :    44763768 :     return chrec;
    2293                 :             : 
    2294                 :             :   /* We cache the value of instantiated variable to avoid exponential
    2295                 :             :      time complexity due to reevaluations.  We also store the convenient
    2296                 :             :      value in the cache in order to prevent infinite recursion -- we do
    2297                 :             :      not want to instantiate the SSA_NAME if it is in a mixer
    2298                 :             :      structure.  This is used for avoiding the instantiation of
    2299                 :             :      recursively defined functions, such as:
    2300                 :             : 
    2301                 :             :      | a_2 -> {0, +, 1, +, a_2}_1  */
    2302                 :             : 
    2303                 :    56747054 :   unsigned si = get_instantiated_value_entry (*global_cache,
    2304                 :             :                                               chrec, instantiate_below);
    2305                 :    56747054 :   if (global_cache->get (si) != chrec_not_analyzed_yet)
    2306                 :             :     return global_cache->get (si);
    2307                 :             : 
    2308                 :             :   /* On recursion return chrec_dont_know.  */
    2309                 :    29425296 :   global_cache->set (si, chrec_dont_know);
    2310                 :             : 
    2311                 :    29425296 :   def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
    2312                 :             : 
    2313                 :    29425296 :   if (! dominated_by_p (CDI_DOMINATORS,
    2314                 :    29425296 :                         def_loop->header, instantiate_below->dest))
    2315                 :             :     {
    2316                 :      178369 :       gimple *def = SSA_NAME_DEF_STMT (chrec);
    2317                 :      178369 :       if (gassign *ass = dyn_cast <gassign *> (def))
    2318                 :             :         {
    2319                 :      126745 :           switch (gimple_assign_rhs_class (ass))
    2320                 :             :             {
    2321                 :        5208 :             case GIMPLE_UNARY_RHS:
    2322                 :        5208 :               {
    2323                 :        5208 :                 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
    2324                 :             :                                                inner_loop, gimple_assign_rhs1 (ass),
    2325                 :             :                                                fold_conversions, size_expr);
    2326                 :        5208 :                 if (op0 == chrec_dont_know)
    2327                 :             :                   return chrec_dont_know;
    2328                 :        1223 :                 res = fold_build1 (gimple_assign_rhs_code (ass),
    2329                 :             :                                    TREE_TYPE (chrec), op0);
    2330                 :        1223 :                 break;
    2331                 :             :               }
    2332                 :       53728 :             case GIMPLE_BINARY_RHS:
    2333                 :       53728 :               {
    2334                 :       53728 :                 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
    2335                 :             :                                                inner_loop, gimple_assign_rhs1 (ass),
    2336                 :             :                                                fold_conversions, size_expr);
    2337                 :       53728 :                 if (op0 == chrec_dont_know)
    2338                 :             :                   return chrec_dont_know;
    2339                 :       11660 :                 tree op1 = instantiate_scev_r (instantiate_below, evolution_loop,
    2340                 :             :                                                inner_loop, gimple_assign_rhs2 (ass),
    2341                 :             :                                                fold_conversions, size_expr);
    2342                 :        5830 :                 if (op1 == chrec_dont_know)
    2343                 :             :                   return chrec_dont_know;
    2344                 :        2212 :                 res = fold_build2 (gimple_assign_rhs_code (ass),
    2345                 :             :                                    TREE_TYPE (chrec), op0, op1);
    2346                 :        2212 :                 break;
    2347                 :             :               }
    2348                 :       67809 :             default:
    2349                 :       67809 :               res = chrec_dont_know;
    2350                 :             :             }
    2351                 :             :         }
    2352                 :             :       else
    2353                 :       51624 :         res = chrec_dont_know;
    2354                 :      122868 :       global_cache->set (si, res);
    2355                 :      122868 :       return res;
    2356                 :             :     }
    2357                 :             : 
    2358                 :             :   /* If the analysis yields a parametric chrec, instantiate the
    2359                 :             :      result again.  */
    2360                 :    29246927 :   res = analyze_scalar_evolution (def_loop, chrec);
    2361                 :             : 
    2362                 :             :   /* Don't instantiate default definitions.  */
    2363                 :    29246927 :   if (TREE_CODE (res) == SSA_NAME
    2364                 :    29246927 :       && SSA_NAME_IS_DEFAULT_DEF (res))
    2365                 :             :     ;
    2366                 :             : 
    2367                 :             :   /* Don't instantiate loop-closed-ssa phi nodes.  */
    2368                 :    29231023 :   else if (TREE_CODE (res) == SSA_NAME
    2369                 :    86132054 :            && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
    2370                 :    28450935 :            > loop_depth (def_loop))
    2371                 :             :     {
    2372                 :     1793704 :       if (res == chrec)
    2373                 :     1775029 :         res = loop_closed_phi_def (chrec);
    2374                 :             :       else
    2375                 :             :         res = chrec;
    2376                 :             : 
    2377                 :             :       /* When there is no loop_closed_phi_def, it means that the
    2378                 :             :          variable is not used after the loop: try to still compute the
    2379                 :             :          value of the variable when exiting the loop.  */
    2380                 :     1793704 :       if (res == NULL_TREE)
    2381                 :             :         {
    2382                 :     1545905 :           loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
    2383                 :     1545905 :           res = analyze_scalar_evolution (loop, chrec);
    2384                 :     1545905 :           res = compute_overall_effect_of_inner_loop (loop, res);
    2385                 :     1545905 :           res = instantiate_scev_r (instantiate_below, evolution_loop,
    2386                 :             :                                     inner_loop, res,
    2387                 :             :                                     fold_conversions, size_expr);
    2388                 :             :         }
    2389                 :      247799 :       else if (dominated_by_p (CDI_DOMINATORS,
    2390                 :      247799 :                                 gimple_bb (SSA_NAME_DEF_STMT (res)),
    2391                 :      247799 :                                 instantiate_below->dest))
    2392                 :      247799 :         res = chrec_dont_know;
    2393                 :             :     }
    2394                 :             : 
    2395                 :    27437319 :   else if (res != chrec_dont_know)
    2396                 :             :     {
    2397                 :    27437319 :       if (inner_loop
    2398                 :     1146220 :           && def_bb->loop_father != inner_loop
    2399                 :    27980265 :           && !flow_loop_nested_p (def_bb->loop_father, inner_loop))
    2400                 :             :         /* ???  We could try to compute the overall effect of the loop here.  */
    2401                 :         320 :         res = chrec_dont_know;
    2402                 :             :       else
    2403                 :    27436999 :         res = instantiate_scev_r (instantiate_below, evolution_loop,
    2404                 :             :                                   inner_loop, res,
    2405                 :             :                                   fold_conversions, size_expr);
    2406                 :             :     }
    2407                 :             : 
    2408                 :             :   /* Store the correct value to the cache.  */
    2409                 :    29246927 :   global_cache->set (si, res);
    2410                 :    29246927 :   return res;
    2411                 :             : }
    2412                 :             : 
    2413                 :             : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
    2414                 :             :    and EVOLUTION_LOOP, that were left under a symbolic form.
    2415                 :             : 
    2416                 :             :    CHREC is a polynomial chain of recurrence to be instantiated.
    2417                 :             : 
    2418                 :             :    CACHE is the cache of already instantiated values.
    2419                 :             : 
    2420                 :             :    Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
    2421                 :             :    conversions that may wrap in signed/pointer type are folded, as long
    2422                 :             :    as the value of the chrec is preserved.  If FOLD_CONVERSIONS is NULL
    2423                 :             :    then we don't do such fold.
    2424                 :             : 
    2425                 :             :    SIZE_EXPR is used for computing the size of the expression to be
    2426                 :             :    instantiated, and to stop if it exceeds some limit.  */
    2427                 :             : 
    2428                 :             : static tree
    2429                 :    65698186 : instantiate_scev_poly (edge instantiate_below,
    2430                 :             :                        class loop *evolution_loop, class loop *,
    2431                 :             :                        tree chrec, bool *fold_conversions, int size_expr)
    2432                 :             : {
    2433                 :    65698186 :   tree op1;
    2434                 :   131396372 :   tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
    2435                 :             :                                  get_chrec_loop (chrec),
    2436                 :    65698186 :                                  CHREC_LEFT (chrec), fold_conversions,
    2437                 :             :                                  size_expr);
    2438                 :    65698186 :   if (op0 == chrec_dont_know)
    2439                 :             :     return chrec_dont_know;
    2440                 :             : 
    2441                 :   131024546 :   op1 = instantiate_scev_r (instantiate_below, evolution_loop,
    2442                 :             :                             get_chrec_loop (chrec),
    2443                 :    65512273 :                             CHREC_RIGHT (chrec), fold_conversions,
    2444                 :             :                             size_expr);
    2445                 :    65512273 :   if (op1 == chrec_dont_know)
    2446                 :             :     return chrec_dont_know;
    2447                 :             : 
    2448                 :    64791942 :   if (CHREC_LEFT (chrec) != op0
    2449                 :    64791942 :       || CHREC_RIGHT (chrec) != op1)
    2450                 :             :     {
    2451                 :     7334102 :       op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
    2452                 :     7334102 :       chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
    2453                 :             :     }
    2454                 :             : 
    2455                 :             :   return chrec;
    2456                 :             : }
    2457                 :             : 
    2458                 :             : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
    2459                 :             :    and EVOLUTION_LOOP, that were left under a symbolic form.
    2460                 :             : 
    2461                 :             :    "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
    2462                 :             : 
    2463                 :             :    CACHE is the cache of already instantiated values.
    2464                 :             : 
    2465                 :             :    Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
    2466                 :             :    conversions that may wrap in signed/pointer type are folded, as long
    2467                 :             :    as the value of the chrec is preserved.  If FOLD_CONVERSIONS is NULL
    2468                 :             :    then we don't do such fold.
    2469                 :             : 
    2470                 :             :    SIZE_EXPR is used for computing the size of the expression to be
    2471                 :             :    instantiated, and to stop if it exceeds some limit.  */
    2472                 :             : 
    2473                 :             : static tree
    2474                 :    23321155 : instantiate_scev_binary (edge instantiate_below,
    2475                 :             :                          class loop *evolution_loop, class loop *inner_loop,
    2476                 :             :                          tree chrec, enum tree_code code,
    2477                 :             :                          tree type, tree c0, tree c1,
    2478                 :             :                          bool *fold_conversions, int size_expr)
    2479                 :             : {
    2480                 :    23321155 :   tree op1;
    2481                 :    23321155 :   tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
    2482                 :             :                                  c0, fold_conversions, size_expr);
    2483                 :    23321155 :   if (op0 == chrec_dont_know)
    2484                 :             :     return chrec_dont_know;
    2485                 :             : 
    2486                 :             :   /* While we eventually compute the same op1 if c0 == c1 the process
    2487                 :             :      of doing this is expensive so the following short-cut prevents
    2488                 :             :      exponential compile-time behavior.  */
    2489                 :    23001312 :   if (c0 != c1)
    2490                 :             :     {
    2491                 :    22980257 :       op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
    2492                 :             :                                 c1, fold_conversions, size_expr);
    2493                 :    22980257 :       if (op1 == chrec_dont_know)
    2494                 :             :         return chrec_dont_know;
    2495                 :             :     }
    2496                 :             :   else
    2497                 :             :     op1 = op0;
    2498                 :             : 
    2499                 :    22947918 :   if (c0 != op0
    2500                 :    22947918 :       || c1 != op1)
    2501                 :             :     {
    2502                 :    13438493 :       op0 = chrec_convert (type, op0, NULL);
    2503                 :    13438493 :       op1 = chrec_convert_rhs (type, op1, NULL);
    2504                 :             : 
    2505                 :    13438493 :       switch (code)
    2506                 :             :         {
    2507                 :     7841549 :         case POINTER_PLUS_EXPR:
    2508                 :     7841549 :         case PLUS_EXPR:
    2509                 :     7841549 :           return chrec_fold_plus (type, op0, op1);
    2510                 :             : 
    2511                 :      795311 :         case MINUS_EXPR:
    2512                 :      795311 :           return chrec_fold_minus (type, op0, op1);
    2513                 :             : 
    2514                 :     4801633 :         case MULT_EXPR:
    2515                 :     4801633 :           return chrec_fold_multiply (type, op0, op1);
    2516                 :             : 
    2517                 :           0 :         default:
    2518                 :           0 :           gcc_unreachable ();
    2519                 :             :         }
    2520                 :             :     }
    2521                 :             : 
    2522                 :     9509425 :   return chrec ? chrec : fold_build2 (code, type, c0, c1);
    2523                 :             : }
    2524                 :             : 
    2525                 :             : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
    2526                 :             :    and EVOLUTION_LOOP, that were left under a symbolic form.
    2527                 :             : 
    2528                 :             :    "CHREC" that stands for a convert expression "(TYPE) OP" is to be
    2529                 :             :    instantiated.
    2530                 :             : 
    2531                 :             :    CACHE is the cache of already instantiated values.
    2532                 :             : 
    2533                 :             :    Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
    2534                 :             :    conversions that may wrap in signed/pointer type are folded, as long
    2535                 :             :    as the value of the chrec is preserved.  If FOLD_CONVERSIONS is NULL
    2536                 :             :    then we don't do such fold.
    2537                 :             : 
    2538                 :             :    SIZE_EXPR is used for computing the size of the expression to be
    2539                 :             :    instantiated, and to stop if it exceeds some limit.  */
    2540                 :             : 
    2541                 :             : static tree
    2542                 :    22441365 : instantiate_scev_convert (edge instantiate_below,
    2543                 :             :                           class loop *evolution_loop, class loop *inner_loop,
    2544                 :             :                           tree chrec, tree type, tree op,
    2545                 :             :                           bool *fold_conversions, int size_expr)
    2546                 :             : {
    2547                 :    22441365 :   tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
    2548                 :             :                                  inner_loop, op,
    2549                 :             :                                  fold_conversions, size_expr);
    2550                 :             : 
    2551                 :    22441365 :   if (op0 == chrec_dont_know)
    2552                 :             :     return chrec_dont_know;
    2553                 :             : 
    2554                 :    18244042 :   if (fold_conversions)
    2555                 :             :     {
    2556                 :     7326588 :       tree tmp = chrec_convert_aggressive (type, op0, fold_conversions);
    2557                 :     7326588 :       if (tmp)
    2558                 :             :         return tmp;
    2559                 :             : 
    2560                 :             :       /* If we used chrec_convert_aggressive, we can no longer assume that
    2561                 :             :          signed chrecs do not overflow, as chrec_convert does, so avoid
    2562                 :             :          calling it in that case.  */
    2563                 :     6857720 :       if (*fold_conversions)
    2564                 :             :         {
    2565                 :        6876 :           if (chrec && op0 == op)
    2566                 :             :             return chrec;
    2567                 :             : 
    2568                 :        6876 :           return fold_convert (type, op0);
    2569                 :             :         }
    2570                 :             :     }
    2571                 :             : 
    2572                 :    17768298 :   return chrec_convert (type, op0, NULL);
    2573                 :             : }
    2574                 :             : 
    2575                 :             : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
    2576                 :             :    and EVOLUTION_LOOP, that were left under a symbolic form.
    2577                 :             : 
    2578                 :             :    CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
    2579                 :             :    Handle ~X as -1 - X.
    2580                 :             :    Handle -X as -1 * X.
    2581                 :             : 
    2582                 :             :    CACHE is the cache of already instantiated values.
    2583                 :             : 
    2584                 :             :    Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
    2585                 :             :    conversions that may wrap in signed/pointer type are folded, as long
    2586                 :             :    as the value of the chrec is preserved.  If FOLD_CONVERSIONS is NULL
    2587                 :             :    then we don't do such fold.
    2588                 :             : 
    2589                 :             :    SIZE_EXPR is used for computing the size of the expression to be
    2590                 :             :    instantiated, and to stop if it exceeds some limit.  */
    2591                 :             : 
    2592                 :             : static tree
    2593                 :      318918 : instantiate_scev_not (edge instantiate_below,
    2594                 :             :                       class loop *evolution_loop, class loop *inner_loop,
    2595                 :             :                       tree chrec,
    2596                 :             :                       enum tree_code code, tree type, tree op,
    2597                 :             :                       bool *fold_conversions, int size_expr)
    2598                 :             : {
    2599                 :      318918 :   tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
    2600                 :             :                                  inner_loop, op,
    2601                 :             :                                  fold_conversions, size_expr);
    2602                 :             : 
    2603                 :      318918 :   if (op0 == chrec_dont_know)
    2604                 :             :     return chrec_dont_know;
    2605                 :             : 
    2606                 :      265986 :   if (op != op0)
    2607                 :             :     {
    2608                 :       36299 :       op0 = chrec_convert (type, op0, NULL);
    2609                 :             : 
    2610                 :       36299 :       switch (code)
    2611                 :             :         {
    2612                 :        9211 :         case BIT_NOT_EXPR:
    2613                 :        9211 :           return chrec_fold_minus
    2614                 :        9211 :             (type, fold_convert (type, integer_minus_one_node), op0);
    2615                 :             : 
    2616                 :       27088 :         case NEGATE_EXPR:
    2617                 :       27088 :           return chrec_fold_multiply
    2618                 :       27088 :             (type, fold_convert (type, integer_minus_one_node), op0);
    2619                 :             : 
    2620                 :           0 :         default:
    2621                 :           0 :           gcc_unreachable ();
    2622                 :             :         }
    2623                 :             :     }
    2624                 :             : 
    2625                 :      229687 :   return chrec ? chrec : fold_build1 (code, type, op0);
    2626                 :             : }
    2627                 :             : 
    2628                 :             : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
    2629                 :             :    and EVOLUTION_LOOP, that were left under a symbolic form.
    2630                 :             : 
    2631                 :             :    CHREC is the scalar evolution to instantiate.
    2632                 :             : 
    2633                 :             :    CACHE is the cache of already instantiated values.
    2634                 :             : 
    2635                 :             :    Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
    2636                 :             :    conversions that may wrap in signed/pointer type are folded, as long
    2637                 :             :    as the value of the chrec is preserved.  If FOLD_CONVERSIONS is NULL
    2638                 :             :    then we don't do such fold.
    2639                 :             : 
    2640                 :             :    SIZE_EXPR is used for computing the size of the expression to be
    2641                 :             :    instantiated, and to stop if it exceeds some limit.  */
    2642                 :             : 
    2643                 :             : static tree
    2644                 :   369858706 : instantiate_scev_r (edge instantiate_below,
    2645                 :             :                     class loop *evolution_loop, class loop *inner_loop,
    2646                 :             :                     tree chrec,
    2647                 :             :                     bool *fold_conversions, int size_expr)
    2648                 :             : {
    2649                 :             :   /* Give up if the expression is larger than the MAX that we allow.  */
    2650                 :   369858706 :   if (size_expr++ > param_scev_max_expr_size)
    2651                 :          11 :     return chrec_dont_know;
    2652                 :             : 
    2653                 :   369858695 :   if (chrec == NULL_TREE
    2654                 :   523907231 :       || automatically_generated_chrec_p (chrec)
    2655                 :   737819907 :       || is_gimple_min_invariant (chrec))
    2656                 :   155946019 :     return chrec;
    2657                 :             : 
    2658                 :   213912676 :   switch (TREE_CODE (chrec))
    2659                 :             :     {
    2660                 :   101510822 :     case SSA_NAME:
    2661                 :   101510822 :       return instantiate_scev_name (instantiate_below, evolution_loop,
    2662                 :             :                                     inner_loop, chrec,
    2663                 :   101510822 :                                     fold_conversions, size_expr);
    2664                 :             : 
    2665                 :    65698186 :     case POLYNOMIAL_CHREC:
    2666                 :    65698186 :       return instantiate_scev_poly (instantiate_below, evolution_loop,
    2667                 :             :                                     inner_loop, chrec,
    2668                 :    65698186 :                                     fold_conversions, size_expr);
    2669                 :             : 
    2670                 :    23321155 :     case POINTER_PLUS_EXPR:
    2671                 :    23321155 :     case PLUS_EXPR:
    2672                 :    23321155 :     case MINUS_EXPR:
    2673                 :    23321155 :     case MULT_EXPR:
    2674                 :    23321155 :       return instantiate_scev_binary (instantiate_below, evolution_loop,
    2675                 :             :                                       inner_loop, chrec,
    2676                 :             :                                       TREE_CODE (chrec), chrec_type (chrec),
    2677                 :    23321155 :                                       TREE_OPERAND (chrec, 0),
    2678                 :    23321155 :                                       TREE_OPERAND (chrec, 1),
    2679                 :    23321155 :                                       fold_conversions, size_expr);
    2680                 :             : 
    2681                 :    22441365 :     CASE_CONVERT:
    2682                 :    22441365 :       return instantiate_scev_convert (instantiate_below, evolution_loop,
    2683                 :             :                                        inner_loop, chrec,
    2684                 :    22441365 :                                        TREE_TYPE (chrec), TREE_OPERAND (chrec, 0),
    2685                 :    22441365 :                                        fold_conversions, size_expr);
    2686                 :             : 
    2687                 :      318918 :     case NEGATE_EXPR:
    2688                 :      318918 :     case BIT_NOT_EXPR:
    2689                 :      318918 :       return instantiate_scev_not (instantiate_below, evolution_loop,
    2690                 :             :                                    inner_loop, chrec,
    2691                 :      318918 :                                    TREE_CODE (chrec), TREE_TYPE (chrec),
    2692                 :      318918 :                                    TREE_OPERAND (chrec, 0),
    2693                 :      318918 :                                    fold_conversions, size_expr);
    2694                 :             : 
    2695                 :           0 :     case ADDR_EXPR:
    2696                 :           0 :       if (is_gimple_min_invariant (chrec))
    2697                 :             :         return chrec;
    2698                 :             :       /* Fallthru.  */
    2699                 :           0 :     case SCEV_NOT_KNOWN:
    2700                 :           0 :       return chrec_dont_know;
    2701                 :             : 
    2702                 :           0 :     case SCEV_KNOWN:
    2703                 :           0 :       return chrec_known;
    2704                 :             : 
    2705                 :      622230 :     default:
    2706                 :      622230 :       if (CONSTANT_CLASS_P (chrec))
    2707                 :             :         return chrec;
    2708                 :      622230 :       return chrec_dont_know;
    2709                 :             :     }
    2710                 :             : }
    2711                 :             : 
    2712                 :             : /* Analyze all the parameters of the chrec that were left under a
    2713                 :             :    symbolic form.  INSTANTIATE_BELOW is the basic block that stops the
    2714                 :             :    recursive instantiation of parameters: a parameter is a variable
    2715                 :             :    that is defined in a basic block that dominates INSTANTIATE_BELOW or
    2716                 :             :    a function parameter.  */
    2717                 :             : 
    2718                 :             : tree
    2719                 :    86959530 : instantiate_scev (edge instantiate_below, class loop *evolution_loop,
    2720                 :             :                   tree chrec)
    2721                 :             : {
    2722                 :    86959530 :   tree res;
    2723                 :             : 
    2724                 :    86959530 :   if (dump_file && (dump_flags & TDF_SCEV))
    2725                 :             :     {
    2726                 :          16 :       fprintf (dump_file, "(instantiate_scev \n");
    2727                 :          16 :       fprintf (dump_file, "  (instantiate_below = %d -> %d)\n",
    2728                 :          16 :                instantiate_below->src->index, instantiate_below->dest->index);
    2729                 :          16 :       if (evolution_loop)
    2730                 :          16 :         fprintf (dump_file, "  (evolution_loop = %d)\n", evolution_loop->num);
    2731                 :          16 :       fprintf (dump_file, "  (chrec = ");
    2732                 :          16 :       print_generic_expr (dump_file, chrec);
    2733                 :          16 :       fprintf (dump_file, ")\n");
    2734                 :             :     }
    2735                 :             : 
    2736                 :    86959530 :   bool destr = false;
    2737                 :    86959530 :   if (!global_cache)
    2738                 :             :     {
    2739                 :    38751166 :       global_cache = new instantiate_cache_type;
    2740                 :    38751166 :       destr = true;
    2741                 :             :     }
    2742                 :             : 
    2743                 :    86959530 :   res = instantiate_scev_r (instantiate_below, evolution_loop,
    2744                 :             :                             NULL, chrec, NULL, 0);
    2745                 :             : 
    2746                 :    86959530 :   if (destr)
    2747                 :             :     {
    2748                 :    38751166 :       delete global_cache;
    2749                 :    38751166 :       global_cache = NULL;
    2750                 :             :     }
    2751                 :             : 
    2752                 :    86959530 :   if (dump_file && (dump_flags & TDF_SCEV))
    2753                 :             :     {
    2754                 :          16 :       fprintf (dump_file, "  (res = ");
    2755                 :          16 :       print_generic_expr (dump_file, res);
    2756                 :          16 :       fprintf (dump_file, "))\n");
    2757                 :             :     }
    2758                 :             : 
    2759                 :    86959530 :   return res;
    2760                 :             : }
    2761                 :             : 
    2762                 :             : /* Similar to instantiate_parameters, but does not introduce the
    2763                 :             :    evolutions in outer loops for LOOP invariants in CHREC, and does not
    2764                 :             :    care about causing overflows, as long as they do not affect value
    2765                 :             :    of an expression.  */
    2766                 :             : 
    2767                 :             : tree
    2768                 :    53579352 : resolve_mixers (class loop *loop, tree chrec, bool *folded_casts)
    2769                 :             : {
    2770                 :    53579352 :   bool destr = false;
    2771                 :    53579352 :   bool fold_conversions = false;
    2772                 :    53579352 :   if (!global_cache)
    2773                 :             :     {
    2774                 :    52904296 :       global_cache = new instantiate_cache_type;
    2775                 :    52904296 :       destr = true;
    2776                 :             :     }
    2777                 :             : 
    2778                 :    53579352 :   tree ret = instantiate_scev_r (loop_preheader_edge (loop), loop, NULL,
    2779                 :             :                                  chrec, &fold_conversions, 0);
    2780                 :             : 
    2781                 :    53579352 :   if (folded_casts && !*folded_casts)
    2782                 :    53579352 :     *folded_casts = fold_conversions;
    2783                 :             : 
    2784                 :    53579352 :   if (destr)
    2785                 :             :     {
    2786                 :    52904296 :       delete global_cache;
    2787                 :    52904296 :       global_cache = NULL;
    2788                 :             :     }
    2789                 :             : 
    2790                 :    53579352 :   return ret;
    2791                 :             : }
    2792                 :             : 
    2793                 :             : /* Entry point for the analysis of the number of iterations pass.
    2794                 :             :    This function tries to safely approximate the number of iterations
    2795                 :             :    the loop will run.  When this property is not decidable at compile
    2796                 :             :    time, the result is chrec_dont_know.  Otherwise the result is a
    2797                 :             :    scalar or a symbolic parameter.  When the number of iterations may
    2798                 :             :    be equal to zero and the property cannot be determined at compile
    2799                 :             :    time, the result is a COND_EXPR that represents in a symbolic form
    2800                 :             :    the conditions under which the number of iterations is not zero.
    2801                 :             : 
    2802                 :             :    Example of analysis: suppose that the loop has an exit condition:
    2803                 :             : 
    2804                 :             :    "if (b > 49) goto end_loop;"
    2805                 :             : 
    2806                 :             :    and that in a previous analysis we have determined that the
    2807                 :             :    variable 'b' has an evolution function:
    2808                 :             : 
    2809                 :             :    "EF = {23, +, 5}_2".
    2810                 :             : 
    2811                 :             :    When we evaluate the function at the point 5, i.e. the value of the
    2812                 :             :    variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
    2813                 :             :    and EF (6) = 53.  In this case the value of 'b' on exit is '53' and
    2814                 :             :    the loop body has been executed 6 times.  */
    2815                 :             : 
    2816                 :             : tree
    2817                 :    10427212 : number_of_latch_executions (class loop *loop)
    2818                 :             : {
    2819                 :    10427212 :   edge exit;
    2820                 :    10427212 :   class tree_niter_desc niter_desc;
    2821                 :    10427212 :   tree may_be_zero;
    2822                 :    10427212 :   tree res;
    2823                 :             : 
    2824                 :             :   /* Determine whether the number of iterations in loop has already
    2825                 :             :      been computed.  */
    2826                 :    10427212 :   res = loop->nb_iterations;
    2827                 :    10427212 :   if (res)
    2828                 :             :     return res;
    2829                 :             : 
    2830                 :     7544354 :   may_be_zero = NULL_TREE;
    2831                 :             : 
    2832                 :     7544354 :   if (dump_file && (dump_flags & TDF_SCEV))
    2833                 :           0 :     fprintf (dump_file, "(number_of_iterations_in_loop = \n");
    2834                 :             : 
    2835                 :     7544354 :   res = chrec_dont_know;
    2836                 :     7544354 :   exit = single_exit (loop);
    2837                 :             : 
    2838                 :     7544354 :   if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
    2839                 :             :     {
    2840                 :     3114394 :       may_be_zero = niter_desc.may_be_zero;
    2841                 :     3114394 :       res = niter_desc.niter;
    2842                 :             :     }
    2843                 :             : 
    2844                 :     7544354 :   if (res == chrec_dont_know
    2845                 :     3114394 :       || !may_be_zero
    2846                 :    10658748 :       || integer_zerop (may_be_zero))
    2847                 :             :     ;
    2848                 :      495478 :   else if (integer_nonzerop (may_be_zero))
    2849                 :          27 :     res = build_int_cst (TREE_TYPE (res), 0);
    2850                 :             : 
    2851                 :      495451 :   else if (COMPARISON_CLASS_P (may_be_zero))
    2852                 :      495451 :     res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
    2853                 :             :                        build_int_cst (TREE_TYPE (res), 0), res);
    2854                 :             :   else
    2855                 :           0 :     res = chrec_dont_know;
    2856                 :             : 
    2857                 :     7544354 :   if (dump_file && (dump_flags & TDF_SCEV))
    2858                 :             :     {
    2859                 :           0 :       fprintf (dump_file, "  (set_nb_iterations_in_loop = ");
    2860                 :           0 :       print_generic_expr (dump_file, res);
    2861                 :           0 :       fprintf (dump_file, "))\n");
    2862                 :             :     }
    2863                 :             : 
    2864                 :     7544354 :   loop->nb_iterations = res;
    2865                 :     7544354 :   return res;
    2866                 :    10427212 : }
    2867                 :             : 
    2868                 :             : 
    2869                 :             : /* Counters for the stats.  */
    2870                 :             : 
    2871                 :             : struct chrec_stats
    2872                 :             : {
    2873                 :             :   unsigned nb_chrecs;
    2874                 :             :   unsigned nb_affine;
    2875                 :             :   unsigned nb_affine_multivar;
    2876                 :             :   unsigned nb_higher_poly;
    2877                 :             :   unsigned nb_chrec_dont_know;
    2878                 :             :   unsigned nb_undetermined;
    2879                 :             : };
    2880                 :             : 
    2881                 :             : /* Reset the counters.  */
    2882                 :             : 
    2883                 :             : static inline void
    2884                 :           0 : reset_chrecs_counters (struct chrec_stats *stats)
    2885                 :             : {
    2886                 :           0 :   stats->nb_chrecs = 0;
    2887                 :           0 :   stats->nb_affine = 0;
    2888                 :           0 :   stats->nb_affine_multivar = 0;
    2889                 :           0 :   stats->nb_higher_poly = 0;
    2890                 :           0 :   stats->nb_chrec_dont_know = 0;
    2891                 :           0 :   stats->nb_undetermined = 0;
    2892                 :             : }
    2893                 :             : 
    2894                 :             : /* Dump the contents of a CHREC_STATS structure.  */
    2895                 :             : 
    2896                 :             : static void
    2897                 :           0 : dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
    2898                 :             : {
    2899                 :           0 :   fprintf (file, "\n(\n");
    2900                 :           0 :   fprintf (file, "-----------------------------------------\n");
    2901                 :           0 :   fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
    2902                 :           0 :   fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
    2903                 :           0 :   fprintf (file, "%d\tdegree greater than 2 polynomials\n",
    2904                 :             :            stats->nb_higher_poly);
    2905                 :           0 :   fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
    2906                 :           0 :   fprintf (file, "-----------------------------------------\n");
    2907                 :           0 :   fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
    2908                 :           0 :   fprintf (file, "%d\twith undetermined coefficients\n",
    2909                 :             :            stats->nb_undetermined);
    2910                 :           0 :   fprintf (file, "-----------------------------------------\n");
    2911                 :           0 :   fprintf (file, "%d\tchrecs in the scev database\n",
    2912                 :           0 :            (int) scalar_evolution_info->elements ());
    2913                 :           0 :   fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
    2914                 :           0 :   fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
    2915                 :           0 :   fprintf (file, "-----------------------------------------\n");
    2916                 :           0 :   fprintf (file, ")\n\n");
    2917                 :           0 : }
    2918                 :             : 
    2919                 :             : /* Gather statistics about CHREC.  */
    2920                 :             : 
    2921                 :             : static void
    2922                 :           0 : gather_chrec_stats (tree chrec, struct chrec_stats *stats)
    2923                 :             : {
    2924                 :           0 :   if (dump_file && (dump_flags & TDF_STATS))
    2925                 :             :     {
    2926                 :           0 :       fprintf (dump_file, "(classify_chrec ");
    2927                 :           0 :       print_generic_expr (dump_file, chrec);
    2928                 :           0 :       fprintf (dump_file, "\n");
    2929                 :             :     }
    2930                 :             : 
    2931                 :           0 :   stats->nb_chrecs++;
    2932                 :             : 
    2933                 :           0 :   if (chrec == NULL_TREE)
    2934                 :             :     {
    2935                 :           0 :       stats->nb_undetermined++;
    2936                 :           0 :       return;
    2937                 :             :     }
    2938                 :             : 
    2939                 :           0 :   switch (TREE_CODE (chrec))
    2940                 :             :     {
    2941                 :           0 :     case POLYNOMIAL_CHREC:
    2942                 :           0 :       if (evolution_function_is_affine_p (chrec))
    2943                 :             :         {
    2944                 :           0 :           if (dump_file && (dump_flags & TDF_STATS))
    2945                 :           0 :             fprintf (dump_file, "  affine_univariate\n");
    2946                 :           0 :           stats->nb_affine++;
    2947                 :             :         }
    2948                 :           0 :       else if (evolution_function_is_affine_multivariate_p (chrec, 0))
    2949                 :             :         {
    2950                 :           0 :           if (dump_file && (dump_flags & TDF_STATS))
    2951                 :           0 :             fprintf (dump_file, "  affine_multivariate\n");
    2952                 :           0 :           stats->nb_affine_multivar++;
    2953                 :             :         }
    2954                 :             :       else
    2955                 :             :         {
    2956                 :           0 :           if (dump_file && (dump_flags & TDF_STATS))
    2957                 :           0 :             fprintf (dump_file, "  higher_degree_polynomial\n");
    2958                 :           0 :           stats->nb_higher_poly++;
    2959                 :             :         }
    2960                 :             : 
    2961                 :             :       break;
    2962                 :             : 
    2963                 :             :     default:
    2964                 :             :       break;
    2965                 :             :     }
    2966                 :             : 
    2967                 :           0 :   if (chrec_contains_undetermined (chrec))
    2968                 :             :     {
    2969                 :           0 :       if (dump_file && (dump_flags & TDF_STATS))
    2970                 :           0 :         fprintf (dump_file, "  undetermined\n");
    2971                 :           0 :       stats->nb_undetermined++;
    2972                 :             :     }
    2973                 :             : 
    2974                 :           0 :   if (dump_file && (dump_flags & TDF_STATS))
    2975                 :           0 :     fprintf (dump_file, ")\n");
    2976                 :             : }
    2977                 :             : 
    2978                 :             : /* Classify the chrecs of the whole database.  */
    2979                 :             : 
    2980                 :             : void
    2981                 :           0 : gather_stats_on_scev_database (void)
    2982                 :             : {
    2983                 :           0 :   struct chrec_stats stats;
    2984                 :             : 
    2985                 :           0 :   if (!dump_file)
    2986                 :           0 :     return;
    2987                 :             : 
    2988                 :           0 :   reset_chrecs_counters (&stats);
    2989                 :             : 
    2990                 :           0 :   hash_table<scev_info_hasher>::iterator iter;
    2991                 :           0 :   scev_info_str *elt;
    2992                 :           0 :   FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info, elt, scev_info_str *,
    2993                 :             :                                iter)
    2994                 :           0 :     gather_chrec_stats (elt->chrec, &stats);
    2995                 :             : 
    2996                 :           0 :   dump_chrecs_stats (dump_file, &stats);
    2997                 :             : }
    2998                 :             : 
    2999                 :             : 
    3000                 :             : /* Initialize the analysis of scalar evolutions for LOOPS.  */
    3001                 :             : 
    3002                 :             : void
    3003                 :    14652644 : scev_initialize (void)
    3004                 :             : {
    3005                 :    14652644 :   gcc_assert (! scev_initialized_p ()
    3006                 :             :               && loops_state_satisfies_p (cfun, LOOPS_NORMAL));
    3007                 :             : 
    3008                 :    14652644 :   scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100);
    3009                 :             : 
    3010                 :    54416017 :   for (auto loop : loops_list (cfun, 0))
    3011                 :    10458085 :     loop->nb_iterations = NULL_TREE;
    3012                 :    14652644 : }
    3013                 :             : 
    3014                 :             : /* Return true if SCEV is initialized.  */
    3015                 :             : 
    3016                 :             : bool
    3017                 :   103350417 : scev_initialized_p (void)
    3018                 :             : {
    3019                 :   103350417 :   return scalar_evolution_info != NULL;
    3020                 :             : }
    3021                 :             : 
    3022                 :             : /* Cleans up the information cached by the scalar evolutions analysis
    3023                 :             :    in the hash table.  */
    3024                 :             : 
    3025                 :             : void
    3026                 :    23268491 : scev_reset_htab (void)
    3027                 :             : {
    3028                 :    23268491 :   if (!scalar_evolution_info)
    3029                 :             :     return;
    3030                 :             : 
    3031                 :     6067152 :   scalar_evolution_info->empty ();
    3032                 :             : }
    3033                 :             : 
    3034                 :             : /* Cleans up the information cached by the scalar evolutions analysis
    3035                 :             :    in the hash table and in the loop->nb_iterations.  */
    3036                 :             : 
    3037                 :             : void
    3038                 :    12817483 : scev_reset (void)
    3039                 :             : {
    3040                 :    12817483 :   scev_reset_htab ();
    3041                 :             : 
    3042                 :    61253902 :   for (auto loop : loops_list (cfun, 0))
    3043                 :    22801453 :     loop->nb_iterations = NULL_TREE;
    3044                 :    12817483 : }
    3045                 :             : 
    3046                 :             : /* Return true if the IV calculation in TYPE can overflow based on the knowledge
    3047                 :             :    of the upper bound on the number of iterations of LOOP, the BASE and STEP
    3048                 :             :    of IV.
    3049                 :             : 
    3050                 :             :    We do not use information whether TYPE can overflow so it is safe to
    3051                 :             :    use this test even for derived IVs not computed every iteration or
    3052                 :             :    hypotetical IVs to be inserted into code.  */
    3053                 :             : 
    3054                 :             : bool
    3055                 :    18027263 : iv_can_overflow_p (class loop *loop, tree type, tree base, tree step)
    3056                 :             : {
    3057                 :    18027263 :   widest_int nit;
    3058                 :    18027263 :   wide_int base_min, base_max, step_min, step_max, type_min, type_max;
    3059                 :    18027263 :   signop sgn = TYPE_SIGN (type);
    3060                 :    18027263 :   int_range_max r;
    3061                 :             : 
    3062                 :    18027263 :   if (integer_zerop (step))
    3063                 :             :     return false;
    3064                 :             : 
    3065                 :    36053876 :   if (!INTEGRAL_TYPE_P (TREE_TYPE (base))
    3066                 :    33744940 :       || !get_range_query (cfun)->range_of_expr (r, base)
    3067                 :    16872470 :       || r.varying_p ()
    3068                 :    33594453 :       || r.undefined_p ())
    3069                 :     2462364 :     return true;
    3070                 :             : 
    3071                 :    15564895 :   base_min = r.lower_bound ();
    3072                 :    15564895 :   base_max = r.upper_bound ();
    3073                 :             : 
    3074                 :    31129215 :   if (!INTEGRAL_TYPE_P (TREE_TYPE (step))
    3075                 :    31129790 :       || !get_range_query (cfun)->range_of_expr (r, step)
    3076                 :    15564895 :       || r.varying_p ()
    3077                 :    31048013 :       || r.undefined_p ())
    3078                 :       81778 :     return true;
    3079                 :             : 
    3080                 :    15483117 :   step_min = r.lower_bound ();
    3081                 :    15483117 :   step_max = r.upper_bound ();
    3082                 :             : 
    3083                 :    15483117 :   if (!get_max_loop_iterations (loop, &nit))
    3084                 :             :     return true;
    3085                 :             : 
    3086                 :    14783387 :   type_min = wi::min_value (type);
    3087                 :    14783387 :   type_max = wi::max_value (type);
    3088                 :             : 
    3089                 :             :   /* Just sanity check that we don't see values out of the range of the type.
    3090                 :             :      In this case the arithmetics bellow would overflow.  */
    3091                 :    14783387 :   gcc_checking_assert (wi::ge_p (base_min, type_min, sgn)
    3092                 :             :                        && wi::le_p (base_max, type_max, sgn));
    3093                 :             : 
    3094                 :             :   /* Account the possible increment in the last ieration.  */
    3095                 :    14783387 :   wi::overflow_type overflow = wi::OVF_NONE;
    3096                 :    14783387 :   nit = wi::add (nit, 1, SIGNED, &overflow);
    3097                 :    14783387 :   if (overflow)
    3098                 :             :     return true;
    3099                 :             : 
    3100                 :             :   /* NIT is typeless and can exceed the precision of the type.  In this case
    3101                 :             :      overflow is always possible, because we know STEP is non-zero.  */
    3102                 :    14783387 :   if (wi::min_precision (nit, UNSIGNED) > TYPE_PRECISION (type))
    3103                 :             :     return true;
    3104                 :    14557654 :   wide_int nit2 = wide_int::from (nit, TYPE_PRECISION (type), UNSIGNED);
    3105                 :             : 
    3106                 :             :   /* If step can be positive, check that nit*step <= type_max-base.
    3107                 :             :      This can be done by unsigned arithmetic and we only need to watch overflow
    3108                 :             :      in the multiplication. The right hand side can always be represented in
    3109                 :             :      the type.  */
    3110                 :    14557654 :   if (sgn == UNSIGNED || !wi::neg_p (step_max))
    3111                 :             :     {
    3112                 :    14514245 :       wi::overflow_type overflow = wi::OVF_NONE;
    3113                 :    14514245 :       if (wi::gtu_p (wi::mul (step_max, nit2, UNSIGNED, &overflow),
    3114                 :    29028490 :                      type_max - base_max)
    3115                 :    29028490 :           || overflow)
    3116                 :     7986784 :         return true;
    3117                 :             :     }
    3118                 :             :   /* If step can be negative, check that nit*(-step) <= base_min-type_min.  */
    3119                 :     6570870 :   if (sgn == SIGNED && wi::neg_p (step_min))
    3120                 :             :     {
    3121                 :       43684 :       wi::overflow_type overflow, overflow2;
    3122                 :       43684 :       overflow = overflow2 = wi::OVF_NONE;
    3123                 :       87368 :       if (wi::gtu_p (wi::mul (wi::neg (step_min, &overflow2),
    3124                 :             :                      nit2, UNSIGNED, &overflow),
    3125                 :       87368 :                      base_min - type_min)
    3126                 :       87368 :           || overflow || overflow2)
    3127                 :       18552 :         return true;
    3128                 :             :     }
    3129                 :             : 
    3130                 :             :   return false;
    3131                 :    18027263 : }
    3132                 :             : 
    3133                 :             : /* Given EV with form of "(type) {inner_base, inner_step}_loop", this
    3134                 :             :    function tries to derive condition under which it can be simplified
    3135                 :             :    into "{(type)inner_base, (type)inner_step}_loop".  The condition is
    3136                 :             :    the maximum number that inner iv can iterate.  */
    3137                 :             : 
    3138                 :             : static tree
    3139                 :       20227 : derive_simple_iv_with_niters (tree ev, tree *niters)
    3140                 :             : {
    3141                 :       20227 :   if (!CONVERT_EXPR_P (ev))
    3142                 :             :     return ev;
    3143                 :             : 
    3144                 :       20227 :   tree inner_ev = TREE_OPERAND (ev, 0);
    3145                 :       20227 :   if (TREE_CODE (inner_ev) != POLYNOMIAL_CHREC)
    3146                 :             :     return ev;
    3147                 :             : 
    3148                 :       20227 :   tree init = CHREC_LEFT (inner_ev);
    3149                 :       20227 :   tree step = CHREC_RIGHT (inner_ev);
    3150                 :       20227 :   if (TREE_CODE (init) != INTEGER_CST
    3151                 :       20227 :       || TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
    3152                 :        7043 :     return ev;
    3153                 :             : 
    3154                 :       13184 :   tree type = TREE_TYPE (ev);
    3155                 :       13184 :   tree inner_type = TREE_TYPE (inner_ev);
    3156                 :       13184 :   if (TYPE_PRECISION (inner_type) >= TYPE_PRECISION (type))
    3157                 :             :     return ev;
    3158                 :             : 
    3159                 :             :   /* Type conversion in "(type) {inner_base, inner_step}_loop" can be
    3160                 :             :      folded only if inner iv won't overflow.  We compute the maximum
    3161                 :             :      number the inner iv can iterate before overflowing and return the
    3162                 :             :      simplified affine iv.  */
    3163                 :       13184 :   tree delta;
    3164                 :       13184 :   init = fold_convert (type, init);
    3165                 :       13184 :   step = fold_convert (type, step);
    3166                 :       13184 :   ev = build_polynomial_chrec (CHREC_VARIABLE (inner_ev), init, step);
    3167                 :       13184 :   if (tree_int_cst_sign_bit (step))
    3168                 :             :     {
    3169                 :           0 :       tree bound = lower_bound_in_type (inner_type, inner_type);
    3170                 :           0 :       delta = fold_build2 (MINUS_EXPR, type, init, fold_convert (type, bound));
    3171                 :           0 :       step = fold_build1 (NEGATE_EXPR, type, step);
    3172                 :             :     }
    3173                 :             :   else
    3174                 :             :     {
    3175                 :       13184 :       tree bound = upper_bound_in_type (inner_type, inner_type);
    3176                 :       13184 :       delta = fold_build2 (MINUS_EXPR, type, fold_convert (type, bound), init);
    3177                 :             :     }
    3178                 :       13184 :   *niters = fold_build2 (FLOOR_DIV_EXPR, type, delta, step);
    3179                 :       13184 :   return ev;
    3180                 :             : }
    3181                 :             : 
    3182                 :             : /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
    3183                 :             :    respect to WRTO_LOOP and returns its base and step in IV if possible
    3184                 :             :    (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
    3185                 :             :    and WRTO_LOOP).  If ALLOW_NONCONSTANT_STEP is true, we want step to be
    3186                 :             :    invariant in LOOP.  Otherwise we require it to be an integer constant.
    3187                 :             : 
    3188                 :             :    IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
    3189                 :             :    because it is computed in signed arithmetics).  Consequently, adding an
    3190                 :             :    induction variable
    3191                 :             : 
    3192                 :             :    for (i = IV->base; ; i += IV->step)
    3193                 :             : 
    3194                 :             :    is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
    3195                 :             :    false for the type of the induction variable, or you can prove that i does
    3196                 :             :    not wrap by some other argument.  Otherwise, this might introduce undefined
    3197                 :             :    behavior, and
    3198                 :             : 
    3199                 :             :    i = iv->base;
    3200                 :             :    for (; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
    3201                 :             : 
    3202                 :             :    must be used instead.
    3203                 :             : 
    3204                 :             :    When IV_NITERS is not NULL, this function also checks case in which OP
    3205                 :             :    is a conversion of an inner simple iv of below form:
    3206                 :             : 
    3207                 :             :      (outer_type){inner_base, inner_step}_loop.
    3208                 :             : 
    3209                 :             :    If type of inner iv has smaller precision than outer_type, it can't be
    3210                 :             :    folded into {(outer_type)inner_base, (outer_type)inner_step}_loop because
    3211                 :             :    the inner iv could overflow/wrap.  In this case, we derive a condition
    3212                 :             :    under which the inner iv won't overflow/wrap and do the simplification.
    3213                 :             :    The derived condition normally is the maximum number the inner iv can
    3214                 :             :    iterate, and will be stored in IV_NITERS.  This is useful in loop niter
    3215                 :             :    analysis, to derive break conditions when a loop must terminate, when is
    3216                 :             :    infinite.  */
    3217                 :             : 
    3218                 :             : bool
    3219                 :    54362646 : simple_iv_with_niters (class loop *wrto_loop, class loop *use_loop,
    3220                 :             :                        tree op, affine_iv *iv, tree *iv_niters,
    3221                 :             :                        bool allow_nonconstant_step)
    3222                 :             : {
    3223                 :    54362646 :   enum tree_code code;
    3224                 :    54362646 :   tree type, ev, base, e;
    3225                 :    54362646 :   wide_int extreme;
    3226                 :    54362646 :   bool folded_casts;
    3227                 :             : 
    3228                 :    54362646 :   iv->base = NULL_TREE;
    3229                 :    54362646 :   iv->step = NULL_TREE;
    3230                 :    54362646 :   iv->no_overflow = false;
    3231                 :             : 
    3232                 :    54362646 :   type = TREE_TYPE (op);
    3233                 :    54362646 :   if (!POINTER_TYPE_P (type)
    3234                 :    46076329 :       && !INTEGRAL_TYPE_P (type))
    3235                 :             :     return false;
    3236                 :             : 
    3237                 :    52386013 :   ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
    3238                 :             :                                          &folded_casts);
    3239                 :    52386013 :   if (chrec_contains_undetermined (ev)
    3240                 :    52386013 :       || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
    3241                 :    12027565 :     return false;
    3242                 :             : 
    3243                 :    40358448 :   if (tree_does_not_contain_chrecs (ev))
    3244                 :             :     {
    3245                 :    17805155 :       iv->base = ev;
    3246                 :    17805155 :       tree ev_type = TREE_TYPE (ev);
    3247                 :    17805155 :       if (POINTER_TYPE_P (ev_type))
    3248                 :     2860646 :         ev_type = sizetype;
    3249                 :             : 
    3250                 :    17805155 :       iv->step = build_int_cst (ev_type, 0);
    3251                 :    17805155 :       iv->no_overflow = true;
    3252                 :    17805155 :       return true;
    3253                 :             :     }
    3254                 :             : 
    3255                 :             :   /* If we can derive valid scalar evolution with assumptions.  */
    3256                 :    22553293 :   if (iv_niters && TREE_CODE (ev) != POLYNOMIAL_CHREC)
    3257                 :       20227 :     ev = derive_simple_iv_with_niters (ev, iv_niters);
    3258                 :             : 
    3259                 :    22553293 :   if (TREE_CODE (ev) != POLYNOMIAL_CHREC)
    3260                 :             :     return false;
    3261                 :             : 
    3262                 :    22512480 :   if (CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
    3263                 :             :     return false;
    3264                 :             : 
    3265                 :    22512466 :   iv->step = CHREC_RIGHT (ev);
    3266                 :    14337940 :   if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
    3267                 :    36604842 :       || tree_contains_chrecs (iv->step, NULL))
    3268                 :      256805 :     return false;
    3269                 :             : 
    3270                 :    22255661 :   iv->base = CHREC_LEFT (ev);
    3271                 :    22255661 :   if (tree_contains_chrecs (iv->base, NULL))
    3272                 :             :     return false;
    3273                 :             : 
    3274                 :    22255661 :   iv->no_overflow = !folded_casts && nowrap_type_p (type);
    3275                 :             : 
    3276                 :    22255661 :   if (!iv->no_overflow
    3277                 :    22255661 :       && !iv_can_overflow_p (wrto_loop, type, iv->base, iv->step))
    3278                 :     4079942 :     iv->no_overflow = true;
    3279                 :             : 
    3280                 :             :   /* Try to simplify iv base:
    3281                 :             : 
    3282                 :             :        (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T
    3283                 :             :          == (signed T)(unsigned T)base + step
    3284                 :             :          == base + step
    3285                 :             : 
    3286                 :             :      If we can prove operation (base + step) doesn't overflow or underflow.
    3287                 :             :      Specifically, we try to prove below conditions are satisfied:
    3288                 :             : 
    3289                 :             :              base <= UPPER_BOUND (type) - step  ;;step > 0
    3290                 :             :              base >= LOWER_BOUND (type) - step  ;;step < 0
    3291                 :             : 
    3292                 :             :      This is done by proving the reverse conditions are false using loop's
    3293                 :             :      initial conditions.
    3294                 :             : 
    3295                 :             :      The is necessary to make loop niter, or iv overflow analysis easier
    3296                 :             :      for below example:
    3297                 :             : 
    3298                 :             :        int foo (int *a, signed char s, signed char l)
    3299                 :             :          {
    3300                 :             :            signed char i;
    3301                 :             :            for (i = s; i < l; i++)
    3302                 :             :              a[i] = 0;
    3303                 :             :            return 0;
    3304                 :             :           }
    3305                 :             : 
    3306                 :             :      Note variable I is firstly converted to type unsigned char, incremented,
    3307                 :             :      then converted back to type signed char.  */
    3308                 :             : 
    3309                 :    22255661 :   if (wrto_loop->num != use_loop->num)
    3310                 :             :     return true;
    3311                 :             : 
    3312                 :    22100894 :   if (!CONVERT_EXPR_P (iv->base) || TREE_CODE (iv->step) != INTEGER_CST)
    3313                 :             :     return true;
    3314                 :             : 
    3315                 :      328954 :   type = TREE_TYPE (iv->base);
    3316                 :      328954 :   e = TREE_OPERAND (iv->base, 0);
    3317                 :      328954 :   if (!tree_nop_conversion_p (type, TREE_TYPE (e))
    3318                 :      300653 :       || TREE_CODE (e) != PLUS_EXPR
    3319                 :      172383 :       || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST
    3320                 :      475373 :       || !tree_int_cst_equal (iv->step,
    3321                 :      146419 :                               fold_convert (type, TREE_OPERAND (e, 1))))
    3322                 :      200112 :     return true;
    3323                 :      128842 :   e = TREE_OPERAND (e, 0);
    3324                 :      128842 :   if (!CONVERT_EXPR_P (e))
    3325                 :             :     return true;
    3326                 :       33310 :   base = TREE_OPERAND (e, 0);
    3327                 :       33310 :   if (!useless_type_conversion_p (type, TREE_TYPE (base)))
    3328                 :             :     return true;
    3329                 :             : 
    3330                 :       24917 :   if (tree_int_cst_sign_bit (iv->step))
    3331                 :             :     {
    3332                 :        9128 :       code = LT_EXPR;
    3333                 :        9128 :       extreme = wi::min_value (type);
    3334                 :             :     }
    3335                 :             :   else
    3336                 :             :     {
    3337                 :       15789 :       code = GT_EXPR;
    3338                 :       15789 :       extreme = wi::max_value (type);
    3339                 :             :     }
    3340                 :       24917 :   wi::overflow_type overflow = wi::OVF_NONE;
    3341                 :       24917 :   extreme = wi::sub (extreme, wi::to_wide (iv->step),
    3342                 :       49834 :                      TYPE_SIGN (type), &overflow);
    3343                 :       24917 :   if (overflow)
    3344                 :             :     return true;
    3345                 :       24893 :   e = fold_build2 (code, boolean_type_node, base,
    3346                 :             :                    wide_int_to_tree (type, extreme));
    3347                 :       24893 :   e = simplify_using_initial_conditions (use_loop, e);
    3348                 :       24893 :   if (!integer_zerop (e))
    3349                 :             :     return true;
    3350                 :             : 
    3351                 :        9781 :   if (POINTER_TYPE_P (TREE_TYPE (base)))
    3352                 :             :     code = POINTER_PLUS_EXPR;
    3353                 :             :   else
    3354                 :             :     code = PLUS_EXPR;
    3355                 :             : 
    3356                 :        9781 :   iv->base = fold_build2 (code, TREE_TYPE (base), base, iv->step);
    3357                 :        9781 :   return true;
    3358                 :    54362646 : }
    3359                 :             : 
    3360                 :             : /* Like simple_iv_with_niters, but return TRUE when OP behaves as a simple
    3361                 :             :    affine iv unconditionally.  */
    3362                 :             : 
    3363                 :             : bool
    3364                 :    22033776 : simple_iv (class loop *wrto_loop, class loop *use_loop, tree op,
    3365                 :             :            affine_iv *iv, bool allow_nonconstant_step)
    3366                 :             : {
    3367                 :    22033776 :   return simple_iv_with_niters (wrto_loop, use_loop, op, iv,
    3368                 :    22033776 :                                 NULL, allow_nonconstant_step);
    3369                 :             : }
    3370                 :             : 
    3371                 :             : /* Finalize the scalar evolution analysis.  */
    3372                 :             : 
    3373                 :             : void
    3374                 :    14652644 : scev_finalize (void)
    3375                 :             : {
    3376                 :    14652644 :   if (!scalar_evolution_info)
    3377                 :             :     return;
    3378                 :    14652644 :   scalar_evolution_info->empty ();
    3379                 :    14652644 :   scalar_evolution_info = NULL;
    3380                 :    14652644 :   free_numbers_of_iterations_estimates (cfun);
    3381                 :             : }
    3382                 :             : 
    3383                 :             : /* Returns true if the expression EXPR is considered to be too expensive
    3384                 :             :    for scev_const_prop.  Sets *COND_OVERFLOW_P to true when the
    3385                 :             :    expression might contain a sub-expression that is subject to undefined
    3386                 :             :    overflow behavior and conditionally evaluated.  */
    3387                 :             : 
    3388                 :             : static bool
    3389                 :    13137263 : expression_expensive_p (tree expr, bool *cond_overflow_p,
    3390                 :             :                         hash_map<tree, uint64_t> &cache, uint64_t &cost)
    3391                 :             : {
    3392                 :    13137263 :   enum tree_code code;
    3393                 :             : 
    3394                 :    13137263 :   if (is_gimple_val (expr))
    3395                 :             :     return false;
    3396                 :             : 
    3397                 :     5217378 :   code = TREE_CODE (expr);
    3398                 :     5217378 :   if (code == TRUNC_DIV_EXPR
    3399                 :             :       || code == CEIL_DIV_EXPR
    3400                 :             :       || code == FLOOR_DIV_EXPR
    3401                 :             :       || code == ROUND_DIV_EXPR
    3402                 :             :       || code == TRUNC_MOD_EXPR
    3403                 :             :       || code == CEIL_MOD_EXPR
    3404                 :             :       || code == FLOOR_MOD_EXPR
    3405                 :     5217378 :       || code == ROUND_MOD_EXPR
    3406                 :     5217378 :       || code == EXACT_DIV_EXPR)
    3407                 :             :     {
    3408                 :             :       /* Division by power of two is usually cheap, so we allow it.
    3409                 :             :          Forbid anything else.  */
    3410                 :       48791 :       if (!integer_pow2p (TREE_OPERAND (expr, 1)))
    3411                 :             :         return true;
    3412                 :             :     }
    3413                 :             : 
    3414                 :     5207657 :   bool visited_p;
    3415                 :     5207657 :   uint64_t &local_cost = cache.get_or_insert (expr, &visited_p);
    3416                 :     5207657 :   if (visited_p)
    3417                 :             :     {
    3418                 :         270 :       uint64_t tem = cost + local_cost;
    3419                 :         270 :       if (tem < cost)
    3420                 :             :         return true;
    3421                 :         270 :       cost = tem;
    3422                 :         270 :       return false;
    3423                 :             :     }
    3424                 :     5207387 :   local_cost = 1;
    3425                 :             : 
    3426                 :     5207387 :   uint64_t op_cost = 0;
    3427                 :     5207387 :   if (code == CALL_EXPR)
    3428                 :             :     {
    3429                 :         102 :       tree arg;
    3430                 :         102 :       call_expr_arg_iterator iter;
    3431                 :             :       /* Even though is_inexpensive_builtin might say true, we will get a
    3432                 :             :          library call for popcount when backend does not have an instruction
    3433                 :             :          to do so.  We consider this to be expensive and generate
    3434                 :             :          __builtin_popcount only when backend defines it.  */
    3435                 :         102 :       optab optab;
    3436                 :         102 :       combined_fn cfn = get_call_combined_fn (expr);
    3437                 :         102 :       switch (cfn)
    3438                 :             :         {
    3439                 :          31 :         CASE_CFN_POPCOUNT:
    3440                 :          31 :           optab = popcount_optab;
    3441                 :          31 :           goto bitcount_call;
    3442                 :          58 :         CASE_CFN_CLZ:
    3443                 :          58 :           optab = clz_optab;
    3444                 :          58 :           goto bitcount_call;
    3445                 :             :         CASE_CFN_CTZ:
    3446                 :             :           optab = ctz_optab;
    3447                 :         102 : bitcount_call:
    3448                 :             :           /* Check if opcode for popcount is available in the mode required.  */
    3449                 :         102 :           if (optab_handler (optab,
    3450                 :         102 :                              TYPE_MODE (TREE_TYPE (CALL_EXPR_ARG (expr, 0))))
    3451                 :             :               == CODE_FOR_nothing)
    3452                 :             :             {
    3453                 :          27 :               machine_mode mode;
    3454                 :          27 :               mode = TYPE_MODE (TREE_TYPE (CALL_EXPR_ARG (expr, 0)));
    3455                 :          27 :               scalar_int_mode int_mode;
    3456                 :             : 
    3457                 :             :               /* If the mode is of 2 * UNITS_PER_WORD size, we can handle
    3458                 :             :                  double-word popcount by emitting two single-word popcount
    3459                 :             :                  instructions.  */
    3460                 :          27 :               if (is_a <scalar_int_mode> (mode, &int_mode)
    3461                 :          29 :                   && GET_MODE_SIZE (int_mode) == 2 * UNITS_PER_WORD
    3462                 :           2 :                   && (optab_handler (optab, word_mode)
    3463                 :             :                       != CODE_FOR_nothing))
    3464                 :             :                   break;
    3465                 :             :               /* If popcount is available for a wider mode, we emulate the
    3466                 :             :                  operation for a narrow mode by first zero-extending the value
    3467                 :             :                  and then computing popcount in the wider mode.  Analogue for
    3468                 :             :                  ctz.  For clz we do the same except that we additionally have
    3469                 :             :                  to subtract the difference of the mode precisions from the
    3470                 :             :                  result.  */
    3471                 :          25 :               if (is_a <scalar_int_mode> (mode, &int_mode))
    3472                 :             :                 {
    3473                 :          25 :                   machine_mode wider_mode_iter;
    3474                 :         124 :                   FOR_EACH_WIDER_MODE (wider_mode_iter, mode)
    3475                 :          99 :                     if (optab_handler (optab, wider_mode_iter)
    3476                 :             :                         != CODE_FOR_nothing)
    3477                 :           0 :                       goto check_call_args;
    3478                 :             :                   /* Operation ctz may be emulated via clz in expand_ctz.  */
    3479                 :          25 :                   if (optab == ctz_optab)
    3480                 :             :                     {
    3481                 :           0 :                       FOR_EACH_WIDER_MODE_FROM (wider_mode_iter, mode)
    3482                 :           0 :                         if (optab_handler (clz_optab, wider_mode_iter)
    3483                 :             :                             != CODE_FOR_nothing)
    3484                 :           0 :                           goto check_call_args;
    3485                 :             :                     }
    3486                 :             :                 }
    3487                 :          25 :               return true;
    3488                 :             :             }
    3489                 :             :           break;
    3490                 :             : 
    3491                 :           0 :         default:
    3492                 :           0 :           if (cfn == CFN_LAST
    3493                 :           0 :               || !is_inexpensive_builtin (get_callee_fndecl (expr)))
    3494                 :           0 :             return true;
    3495                 :             :           break;
    3496                 :             :         }
    3497                 :             : 
    3498                 :          77 : check_call_args:
    3499                 :         231 :       FOR_EACH_CALL_EXPR_ARG (arg, iter, expr)
    3500                 :          77 :         if (expression_expensive_p (arg, cond_overflow_p, cache, op_cost))
    3501                 :             :           return true;
    3502                 :          77 :       *cache.get (expr) += op_cost;
    3503                 :          77 :       cost += op_cost + 1;
    3504                 :          77 :       return false;
    3505                 :             :     }
    3506                 :             : 
    3507                 :     5207285 :   if (code == COND_EXPR)
    3508                 :             :     {
    3509                 :        1677 :       if (expression_expensive_p (TREE_OPERAND (expr, 0), cond_overflow_p,
    3510                 :             :                                   cache, op_cost)
    3511                 :        1677 :           || (EXPR_P (TREE_OPERAND (expr, 1))
    3512                 :        1675 :               && EXPR_P (TREE_OPERAND (expr, 2)))
    3513                 :             :           /* If either branch has side effects or could trap.  */
    3514                 :        1675 :           || TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 1))
    3515                 :        1675 :           || generic_expr_could_trap_p (TREE_OPERAND (expr, 1))
    3516                 :        1674 :           || TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 0))
    3517                 :        1674 :           || generic_expr_could_trap_p (TREE_OPERAND (expr, 0))
    3518                 :        1674 :           || expression_expensive_p (TREE_OPERAND (expr, 1), cond_overflow_p,
    3519                 :             :                                      cache, op_cost)
    3520                 :        3254 :           || expression_expensive_p (TREE_OPERAND (expr, 2), cond_overflow_p,
    3521                 :             :                                      cache, op_cost))
    3522                 :         100 :         return true;
    3523                 :             :       /* Conservatively assume there's overflow for now.  */
    3524                 :        1577 :       *cond_overflow_p = true;
    3525                 :        1577 :       *cache.get (expr) += op_cost;
    3526                 :        1577 :       cost += op_cost + 1;
    3527                 :        1577 :       return false;
    3528                 :             :     }
    3529                 :             : 
    3530                 :     5205608 :   switch (TREE_CODE_CLASS (code))
    3531                 :             :     {
    3532                 :     2687620 :     case tcc_binary:
    3533                 :     2687620 :     case tcc_comparison:
    3534                 :     2687620 :       if (expression_expensive_p (TREE_OPERAND (expr, 1), cond_overflow_p,
    3535                 :             :                                   cache, op_cost))
    3536                 :             :         return true;
    3537                 :             : 
    3538                 :             :       /* Fallthru.  */
    3539                 :     5202933 :     case tcc_unary:
    3540                 :     5202933 :       if (expression_expensive_p (TREE_OPERAND (expr, 0), cond_overflow_p,
    3541                 :             :                                   cache, op_cost))
    3542                 :             :         return true;
    3543                 :     5179236 :       *cache.get (expr) += op_cost;
    3544                 :     5179236 :       cost += op_cost + 1;
    3545                 :     5179236 :       return false;
    3546                 :             : 
    3547                 :             :     default:
    3548                 :             :       return true;
    3549                 :             :     }
    3550                 :             : }
    3551                 :             : 
    3552                 :             : bool
    3553                 :     5241705 : expression_expensive_p (tree expr, bool *cond_overflow_p)
    3554                 :             : {
    3555                 :     5241705 :   hash_map<tree, uint64_t> cache;
    3556                 :     5241705 :   uint64_t expanded_size = 0;
    3557                 :     5241705 :   *cond_overflow_p = false;
    3558                 :     5241705 :   return (expression_expensive_p (expr, cond_overflow_p, cache, expanded_size)
    3559                 :             :           /* ???  Both the explicit unsharing and gimplification of expr will
    3560                 :             :              expand shared trees to multiple copies.
    3561                 :             :              Guard against exponential growth by counting the visits and
    3562                 :             :              comparing againt the number of original nodes.  Allow a tiny
    3563                 :             :              bit of duplication to catch some additional optimizations.  */
    3564                 :     5251543 :           || expanded_size > (cache.elements () + 1));
    3565                 :     5241705 : }
    3566                 :             : 
    3567                 :             : /* Match.pd function to match bitwise inductive expression.
    3568                 :             :    .i.e.
    3569                 :             :    _2 = 1 << _1;
    3570                 :             :    _3 = ~_2;
    3571                 :             :    tmp_9 = _3 & tmp_12;  */
    3572                 :             : extern bool gimple_bitwise_induction_p (tree, tree *, tree (*)(tree));
    3573                 :             : 
    3574                 :             : /* Return the inductive expression of bitwise operation if possible,
    3575                 :             :    otherwise returns DEF.  */
    3576                 :             : static tree
    3577                 :       17031 : analyze_and_compute_bitwise_induction_effect (class loop* loop,
    3578                 :             :                                               tree phidef,
    3579                 :             :                                               unsigned HOST_WIDE_INT niter)
    3580                 :             : {
    3581                 :       17031 :   tree match_op[3],inv, bitwise_scev;
    3582                 :       17031 :   tree type = TREE_TYPE (phidef);
    3583                 :       17031 :   gphi* header_phi = NULL;
    3584                 :             : 
    3585                 :             :   /* Match things like op2(MATCH_OP[2]), op1(MATCH_OP[1]), phidef(PHIDEF)
    3586                 :             : 
    3587                 :             :      op2 = PHI <phidef, inv>
    3588                 :             :      _1 = (int) bit_17;
    3589                 :             :      _3 = 1 << _1;
    3590                 :             :      op1 = ~_3;
    3591                 :             :      phidef = op1 & op2;  */
    3592                 :       17031 :   if (!gimple_bitwise_induction_p (phidef, &match_op[0], NULL)
    3593                 :          96 :       || TREE_CODE (match_op[2]) != SSA_NAME
    3594                 :       17031 :       || !(header_phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (match_op[2])))
    3595                 :          96 :       || gimple_bb (header_phi) != loop->header
    3596                 :       17125 :       || gimple_phi_num_args (header_phi) != 2)
    3597                 :             :     return NULL_TREE;
    3598                 :             : 
    3599                 :          94 :   if (PHI_ARG_DEF_FROM_EDGE (header_phi, loop_latch_edge (loop)) != phidef)
    3600                 :             :     return NULL_TREE;
    3601                 :             : 
    3602                 :          94 :   bitwise_scev = analyze_scalar_evolution (loop, match_op[1]);
    3603                 :          94 :   bitwise_scev = instantiate_parameters (loop, bitwise_scev);
    3604                 :             : 
    3605                 :             :   /* Make sure bits is in range of type precision.  */
    3606                 :          94 :   if (TREE_CODE (bitwise_scev) != POLYNOMIAL_CHREC
    3607                 :          94 :       || !INTEGRAL_TYPE_P (TREE_TYPE (bitwise_scev))
    3608                 :          94 :       || !tree_fits_uhwi_p (CHREC_LEFT (bitwise_scev))
    3609                 :          94 :       || tree_to_uhwi (CHREC_LEFT (bitwise_scev)) >= TYPE_PRECISION (type)
    3610                 :         188 :       || !tree_fits_shwi_p (CHREC_RIGHT (bitwise_scev)))
    3611                 :             :     return NULL_TREE;
    3612                 :             : 
    3613                 :          94 : enum bit_op_kind
    3614                 :             :   {
    3615                 :             :    INDUCTION_BIT_CLEAR,
    3616                 :             :    INDUCTION_BIT_IOR,
    3617                 :             :    INDUCTION_BIT_XOR,
    3618                 :             :    INDUCTION_BIT_RESET,
    3619                 :             :    INDUCTION_ZERO,
    3620                 :             :    INDUCTION_ALL
    3621                 :             :   };
    3622                 :             : 
    3623                 :          94 :   enum bit_op_kind induction_kind;
    3624                 :          94 :   enum tree_code code1
    3625                 :          94 :     = gimple_assign_rhs_code (SSA_NAME_DEF_STMT (phidef));
    3626                 :          94 :   enum tree_code code2
    3627                 :          94 :     = gimple_assign_rhs_code (SSA_NAME_DEF_STMT (match_op[0]));
    3628                 :             : 
    3629                 :             :   /* BIT_CLEAR: A &= ~(1 << bit)
    3630                 :             :      BIT_RESET: A ^= (1 << bit).
    3631                 :             :      BIT_IOR: A |= (1 << bit)
    3632                 :             :      BIT_ZERO: A &= (1 << bit)
    3633                 :             :      BIT_ALL: A |= ~(1 << bit)
    3634                 :             :      BIT_XOR: A ^= ~(1 << bit).
    3635                 :             :      bit is induction variable.  */
    3636                 :          94 :   switch (code1)
    3637                 :             :     {
    3638                 :          24 :     case BIT_AND_EXPR:
    3639                 :          36 :       induction_kind = code2 == BIT_NOT_EXPR
    3640                 :          24 :         ? INDUCTION_BIT_CLEAR
    3641                 :             :         : INDUCTION_ZERO;
    3642                 :          12 :       break;
    3643                 :          46 :     case BIT_IOR_EXPR:
    3644                 :          46 :       induction_kind = code2 == BIT_NOT_EXPR
    3645                 :          46 :         ? INDUCTION_ALL
    3646                 :             :         : INDUCTION_BIT_IOR;
    3647                 :             :       break;
    3648                 :          12 :     case BIT_XOR_EXPR:
    3649                 :          12 :       induction_kind = code2 == BIT_NOT_EXPR
    3650                 :          12 :         ? INDUCTION_BIT_XOR
    3651                 :             :         : INDUCTION_BIT_RESET;
    3652                 :             :       break;
    3653                 :             :       /* A ^ ~(1 << bit) is equal to ~(A ^ (1 << bit)).  */
    3654                 :          12 :     case BIT_NOT_EXPR:
    3655                 :          12 :       gcc_assert (code2 == BIT_XOR_EXPR);
    3656                 :             :       induction_kind = INDUCTION_BIT_XOR;
    3657                 :             :       break;
    3658                 :           0 :     default:
    3659                 :           0 :       gcc_unreachable ();
    3660                 :             :     }
    3661                 :             : 
    3662                 :          12 :   if (induction_kind == INDUCTION_ZERO)
    3663                 :          12 :     return build_zero_cst (type);
    3664                 :          82 :   if (induction_kind == INDUCTION_ALL)
    3665                 :          12 :     return build_all_ones_cst (type);
    3666                 :             : 
    3667                 :         140 :   wide_int bits = wi::zero (TYPE_PRECISION (type));
    3668                 :          70 :   HOST_WIDE_INT bit_start = tree_to_shwi (CHREC_LEFT (bitwise_scev));
    3669                 :          70 :   HOST_WIDE_INT step = tree_to_shwi (CHREC_RIGHT (bitwise_scev));
    3670                 :          70 :   HOST_WIDE_INT bit_final = bit_start + step * niter;
    3671                 :             : 
    3672                 :             :   /* bit_start, bit_final in range of [0,TYPE_PRECISION)
    3673                 :             :      implies all bits are set in range.  */
    3674                 :          70 :   if (bit_final >= TYPE_PRECISION (type)
    3675                 :          70 :       || bit_final < 0)
    3676                 :             :     return NULL_TREE;
    3677                 :             : 
    3678                 :             :   /* Loop tripcount should be niter + 1.  */
    3679                 :        1230 :   for (unsigned i = 0; i != niter + 1; i++)
    3680                 :             :     {
    3681                 :        1160 :       bits = wi::set_bit (bits, bit_start);
    3682                 :        1160 :       bit_start += step;
    3683                 :             :     }
    3684                 :             : 
    3685                 :          70 :   bool inverted = false;
    3686                 :          70 :   switch (induction_kind)
    3687                 :             :     {
    3688                 :             :     case INDUCTION_BIT_CLEAR:
    3689                 :             :       code1 = BIT_AND_EXPR;
    3690                 :             :       inverted = true;
    3691                 :             :       break;
    3692                 :             :     case INDUCTION_BIT_IOR:
    3693                 :          70 :       code1 = BIT_IOR_EXPR;
    3694                 :             :       break;
    3695                 :             :     case INDUCTION_BIT_RESET:
    3696                 :             :       code1 = BIT_XOR_EXPR;
    3697                 :             :       break;
    3698                 :             :     /* A ^= ~(1 << bit) is special, when loop tripcount is even,
    3699                 :             :        it's equal to  A ^= bits, else A ^= ~bits.  */
    3700                 :          12 :     case INDUCTION_BIT_XOR:
    3701                 :          12 :       code1 = BIT_XOR_EXPR;
    3702                 :          12 :       if (niter % 2 == 0)
    3703                 :             :         inverted = true;
    3704                 :             :       break;
    3705                 :             :     default:
    3706                 :             :       gcc_unreachable ();
    3707                 :             :     }
    3708                 :             : 
    3709                 :             :   if (inverted)
    3710                 :          16 :     bits = wi::bit_not (bits);
    3711                 :             : 
    3712                 :          70 :   inv = PHI_ARG_DEF_FROM_EDGE (header_phi, loop_preheader_edge (loop));
    3713                 :          70 :   return fold_build2 (code1, type, inv, wide_int_to_tree (type, bits));
    3714                 :             : }
    3715                 :             : 
    3716                 :             : /* Match.pd function to match bitop with invariant expression
    3717                 :             :   .i.e.
    3718                 :             :   tmp_7 = _0 & _1; */
    3719                 :             : extern bool gimple_bitop_with_inv_p (tree, tree *, tree (*)(tree));
    3720                 :             : 
    3721                 :             : /* Return the inductive expression of bitop with invariant if possible,
    3722                 :             :    otherwise returns DEF.  */
    3723                 :             : static tree
    3724                 :       67136 : analyze_and_compute_bitop_with_inv_effect (class loop* loop, tree phidef,
    3725                 :             :                                            tree niter)
    3726                 :             : {
    3727                 :       67136 :   tree match_op[2],inv;
    3728                 :       67136 :   tree type = TREE_TYPE (phidef);
    3729                 :       67136 :   gphi* header_phi = NULL;
    3730                 :       67136 :   enum tree_code code;
    3731                 :             :   /* match thing like op0 (match[0]), op1 (match[1]), phidef (PHIDEF)
    3732                 :             : 
    3733                 :             :     op1 =  PHI <phidef, inv>
    3734                 :             :     phidef = op0 & op1
    3735                 :             :     if op0 is an invariant, it could change to
    3736                 :             :     phidef = op0 & inv.  */
    3737                 :       67136 :   gimple *def;
    3738                 :       67136 :   def = SSA_NAME_DEF_STMT (phidef);
    3739                 :       67136 :   if (!(is_gimple_assign (def)
    3740                 :       25944 :       && ((code = gimple_assign_rhs_code (def)), true)
    3741                 :       25944 :       && (code == BIT_AND_EXPR || code == BIT_IOR_EXPR
    3742                 :       20491 :           || code == BIT_XOR_EXPR)))
    3743                 :             :     return NULL_TREE;
    3744                 :             : 
    3745                 :        6071 :   match_op[0] = gimple_assign_rhs1 (def);
    3746                 :        6071 :   match_op[1] = gimple_assign_rhs2 (def);
    3747                 :             : 
    3748                 :        6071 :   if (expr_invariant_in_loop_p (loop, match_op[1]))
    3749                 :         203 :     std::swap (match_op[0], match_op[1]);
    3750                 :             : 
    3751                 :        6071 :   if (TREE_CODE (match_op[1]) != SSA_NAME
    3752                 :        6071 :       || !expr_invariant_in_loop_p (loop, match_op[0])
    3753                 :         280 :       || !(header_phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (match_op[1])))
    3754                 :         197 :       || gimple_bb (header_phi) != loop->header
    3755                 :        6253 :       || gimple_phi_num_args (header_phi) != 2)
    3756                 :        5889 :     return NULL_TREE;
    3757                 :             : 
    3758                 :         182 :   if (PHI_ARG_DEF_FROM_EDGE (header_phi, loop_latch_edge (loop)) != phidef)
    3759                 :             :     return NULL_TREE;
    3760                 :             : 
    3761                 :         177 :   enum tree_code code1
    3762                 :         177 :     = gimple_assign_rhs_code (def);
    3763                 :             : 
    3764                 :         177 :   if (code1 == BIT_XOR_EXPR)
    3765                 :             :     {
    3766                 :          42 :        if (!tree_fits_uhwi_p (niter))
    3767                 :             :         return NULL_TREE;
    3768                 :          19 :        unsigned HOST_WIDE_INT niter_num;
    3769                 :          19 :        niter_num = tree_to_uhwi (niter);
    3770                 :          19 :        if (niter_num % 2 != 0)
    3771                 :          10 :         match_op[0] =  build_zero_cst (type);
    3772                 :             :     }
    3773                 :             : 
    3774                 :         154 :   inv = PHI_ARG_DEF_FROM_EDGE (header_phi, loop_preheader_edge (loop));
    3775                 :         154 :   return fold_build2 (code1, type, inv, match_op[0]);
    3776                 :             : }
    3777                 :             : 
    3778                 :             : /* Do final value replacement for LOOP, return true if we did anything.  */
    3779                 :             : 
    3780                 :             : bool
    3781                 :      795576 : final_value_replacement_loop (class loop *loop)
    3782                 :             : {
    3783                 :             :   /* If we do not know exact number of iterations of the loop, we cannot
    3784                 :             :      replace the final value.  */
    3785                 :      795576 :   edge exit = single_exit (loop);
    3786                 :      795576 :   if (!exit)
    3787                 :             :     return false;
    3788                 :             : 
    3789                 :      417301 :   tree niter = number_of_latch_executions (loop);
    3790                 :      417301 :   if (niter == chrec_dont_know)
    3791                 :             :     return false;
    3792                 :             : 
    3793                 :             :   /* Ensure that it is possible to insert new statements somewhere.  */
    3794                 :      310481 :   if (!single_pred_p (exit->dest))
    3795                 :       34875 :     split_loop_exit_edge (exit);
    3796                 :             : 
    3797                 :             :   /* Set stmt insertion pointer.  All stmts are inserted before this point.  */
    3798                 :             : 
    3799                 :      310481 :   class loop *ex_loop
    3800                 :      620962 :     = superloop_at_depth (loop,
    3801                 :      379642 :                           loop_depth (exit->dest->loop_father) + 1);
    3802                 :             : 
    3803                 :      310481 :   bool any = false;
    3804                 :      310481 :   gphi_iterator psi;
    3805                 :      695613 :   for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
    3806                 :             :     {
    3807                 :      385132 :       gphi *phi = psi.phi ();
    3808                 :      385132 :       tree rslt = PHI_RESULT (phi);
    3809                 :      385132 :       tree phidef = PHI_ARG_DEF_FROM_EDGE (phi, exit);
    3810                 :      385132 :       tree def = phidef;
    3811                 :      769705 :       if (virtual_operand_p (def))
    3812                 :             :         {
    3813                 :      214831 :           gsi_next (&psi);
    3814                 :      571979 :           continue;
    3815                 :             :         }
    3816                 :             : 
    3817                 :      325742 :       if (!POINTER_TYPE_P (TREE_TYPE (def))
    3818                 :      325662 :           && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
    3819                 :             :         {
    3820                 :       73772 :           gsi_next (&psi);
    3821                 :       73772 :           continue;
    3822                 :             :         }
    3823                 :             : 
    3824                 :       96529 :       bool folded_casts;
    3825                 :       96529 :       def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
    3826                 :             :                                               &folded_casts);
    3827                 :             : 
    3828                 :       96529 :       tree bitinv_def, bit_def;
    3829                 :       96529 :       unsigned HOST_WIDE_INT niter_num;
    3830                 :             : 
    3831                 :       96529 :       if (def != chrec_dont_know)
    3832                 :       29393 :         def = compute_overall_effect_of_inner_loop (ex_loop, def);
    3833                 :             : 
    3834                 :             :       /* Handle bitop with invariant induction expression.
    3835                 :             : 
    3836                 :             :         .i.e
    3837                 :             :         for (int i =0 ;i < 32; i++)
    3838                 :             :           tmp &= bit2;
    3839                 :             :         if bit2 is an invariant in loop which could simple to
    3840                 :             :         tmp &= bit2.  */
    3841                 :      134272 :       else if ((bitinv_def
    3842                 :       67136 :                 = analyze_and_compute_bitop_with_inv_effect (loop,
    3843                 :             :                                                              phidef, niter)))
    3844                 :             :         def = bitinv_def;
    3845                 :             : 
    3846                 :             :       /* Handle bitwise induction expression.
    3847                 :             : 
    3848                 :             :          .i.e.
    3849                 :             :          for (int i = 0; i != 64; i+=3)
    3850                 :             :            res &= ~(1UL << i);
    3851                 :             : 
    3852                 :             :          RES can't be analyzed out by SCEV because it is not polynomially
    3853                 :             :          expressible, but in fact final value of RES can be replaced by
    3854                 :             :          RES & CONSTANT where CONSTANT all ones with bit {0,3,6,9,... ,63}
    3855                 :             :          being cleared, similar for BIT_IOR_EXPR/BIT_XOR_EXPR.  */
    3856                 :       66982 :       else if (tree_fits_uhwi_p (niter)
    3857                 :       27136 :                && (niter_num = tree_to_uhwi (niter)) != 0
    3858                 :       27123 :                && niter_num < TYPE_PRECISION (TREE_TYPE (phidef))
    3859                 :       66982 :                && (bit_def
    3860                 :       17031 :                    = analyze_and_compute_bitwise_induction_effect (loop,
    3861                 :             :                                                                    phidef,
    3862                 :             :                                                                    niter_num)))
    3863                 :             :         def = bit_def;
    3864                 :             : 
    3865                 :       96529 :       bool cond_overflow_p;
    3866                 :       96529 :       if (!tree_does_not_contain_chrecs (def)
    3867                 :       29057 :           || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
    3868                 :             :           /* Moving the computation from the loop may prolong life range
    3869                 :             :              of some ssa names, which may cause problems if they appear
    3870                 :             :              on abnormal edges.  */
    3871                 :       29057 :           || contains_abnormal_ssa_name_p (def)
    3872                 :             :           /* Do not emit expensive expressions.  The rationale is that
    3873                 :             :              when someone writes a code like
    3874                 :             : 
    3875                 :             :              while (n > 45) n -= 45;
    3876                 :             : 
    3877                 :             :              he probably knows that n is not large, and does not want it
    3878                 :             :              to be turned into n %= 45.  */
    3879                 :      125586 :           || expression_expensive_p (def, &cond_overflow_p))
    3880                 :             :         {
    3881                 :       68545 :           if (dump_file && (dump_flags & TDF_DETAILS))
    3882                 :             :             {
    3883                 :          56 :               fprintf (dump_file, "not replacing:\n  ");
    3884                 :          56 :               print_gimple_stmt (dump_file, phi, 0);
    3885                 :          56 :               fprintf (dump_file, "\n");
    3886                 :             :             }
    3887                 :       68545 :           gsi_next (&psi);
    3888                 :       68545 :           continue;
    3889                 :             :         }
    3890                 :             : 
    3891                 :             :       /* Eliminate the PHI node and replace it by a computation outside
    3892                 :             :          the loop.  */
    3893                 :       27984 :       if (dump_file)
    3894                 :             :         {
    3895                 :         127 :           fprintf (dump_file, "\nfinal value replacement:\n  ");
    3896                 :         127 :           print_gimple_stmt (dump_file, phi, 0);
    3897                 :         127 :           fprintf (dump_file, " with expr: ");
    3898                 :         127 :           print_generic_expr (dump_file, def);
    3899                 :         127 :           fprintf (dump_file, "\n");
    3900                 :             :         }
    3901                 :       27984 :       any = true;
    3902                 :             :       /* ???  Here we'd like to have a unshare_expr that would assign
    3903                 :             :          shared sub-trees to new temporary variables either gimplified
    3904                 :             :          to a GIMPLE sequence or to a statement list (keeping this a
    3905                 :             :          GENERIC interface).  */
    3906                 :       27984 :       def = unshare_expr (def);
    3907                 :       27984 :       auto loc = gimple_phi_arg_location (phi, exit->dest_idx);
    3908                 :       27984 :       remove_phi_node (&psi, false);
    3909                 :             : 
    3910                 :             :       /* Propagate constants immediately, but leave an unused initialization
    3911                 :             :          around to avoid invalidating the SCEV cache.  */
    3912                 :       33960 :       if (CONSTANT_CLASS_P (def) && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rslt))
    3913                 :        5975 :         replace_uses_by (rslt, def);
    3914                 :             : 
    3915                 :             :       /* Create the replacement statements.  */
    3916                 :       27984 :       gimple_seq stmts;
    3917                 :       27984 :       def = force_gimple_operand (def, &stmts, false, NULL_TREE);
    3918                 :       27984 :       gassign *ass = gimple_build_assign (rslt, def);
    3919                 :       27984 :       gimple_set_location (ass, loc);
    3920                 :       27984 :       gimple_seq_add_stmt (&stmts, ass);
    3921                 :             : 
    3922                 :             :       /* If def's type has undefined overflow and there were folded
    3923                 :             :          casts, rewrite all stmts added for def into arithmetics
    3924                 :             :          with defined overflow behavior.  */
    3925                 :       27984 :       if ((folded_casts
    3926                 :         382 :            && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def))
    3927                 :         644 :            && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def)))
    3928                 :       28366 :           || cond_overflow_p)
    3929                 :             :         {
    3930                 :        1810 :           gimple_stmt_iterator gsi2;
    3931                 :        1810 :           gsi2 = gsi_start (stmts);
    3932                 :       21592 :           while (!gsi_end_p (gsi2))
    3933                 :             :             {
    3934                 :       19782 :               gimple *stmt = gsi_stmt (gsi2);
    3935                 :       19782 :               if (is_gimple_assign (stmt)
    3936                 :       39550 :                   && arith_code_with_undefined_signed_overflow
    3937                 :       19768 :                        (gimple_assign_rhs_code (stmt)))
    3938                 :        5581 :                 rewrite_to_defined_overflow (&gsi2);
    3939                 :       19782 :               gsi_next (&gsi2);
    3940                 :             :             }
    3941                 :             :         }
    3942                 :       27984 :       gimple_stmt_iterator gsi = gsi_after_labels (exit->dest);
    3943                 :       27984 :       gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
    3944                 :       27984 :       if (dump_file)
    3945                 :             :         {
    3946                 :         127 :           fprintf (dump_file, " final stmt:\n  ");
    3947                 :         127 :           print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (rslt), 0);
    3948                 :         127 :           fprintf (dump_file, "\n");
    3949                 :             :         }
    3950                 :             :     }
    3951                 :             : 
    3952                 :             :   return any;
    3953                 :             : }
    3954                 :             : 
    3955                 :             : #include "gt-tree-scalar-evolution.h"
        

Generated by: LCOV version 2.1-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.