LCOV - code coverage report
Current view: top level - gcc - tree-chrec.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 641 742 86.4 %
Date: 2020-03-28 11:57:23 Functions: 40 44 90.9 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Chains of recurrences.
       2                 :            :    Copyright (C) 2003-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Sebastian Pop <pop@cri.ensmp.fr>
       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                 :            : /* This file implements operations on chains of recurrences.  Chains
      22                 :            :    of recurrences are used for modeling evolution functions of scalar
      23                 :            :    variables.
      24                 :            : */
      25                 :            : 
      26                 :            : #include "config.h"
      27                 :            : #include "system.h"
      28                 :            : #include "coretypes.h"
      29                 :            : #include "backend.h"
      30                 :            : #include "tree.h"
      31                 :            : #include "gimple-expr.h"
      32                 :            : #include "tree-pretty-print.h"
      33                 :            : #include "fold-const.h"
      34                 :            : #include "cfgloop.h"
      35                 :            : #include "tree-ssa-loop-ivopts.h"
      36                 :            : #include "tree-ssa-loop-niter.h"
      37                 :            : #include "tree-chrec.h"
      38                 :            : #include "gimple.h"
      39                 :            : #include "tree-ssa-loop.h"
      40                 :            : #include "dumpfile.h"
      41                 :            : #include "tree-scalar-evolution.h"
      42                 :            : 
      43                 :            : /* Extended folder for chrecs.  */
      44                 :            : 
      45                 :            : /* Fold the addition of two polynomial functions.  */
      46                 :            : 
      47                 :            : static inline tree
      48                 :      35107 : chrec_fold_plus_poly_poly (enum tree_code code,
      49                 :            :                            tree type,
      50                 :            :                            tree poly0,
      51                 :            :                            tree poly1)
      52                 :            : {
      53                 :      35107 :   tree left, right;
      54                 :      35107 :   class loop *loop0 = get_chrec_loop (poly0);
      55                 :      35107 :   class loop *loop1 = get_chrec_loop (poly1);
      56                 :      35107 :   tree rtype = code == POINTER_PLUS_EXPR ? chrec_type (poly1) : type;
      57                 :            : 
      58                 :      35107 :   gcc_assert (poly0);
      59                 :      35107 :   gcc_assert (poly1);
      60                 :      35107 :   gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
      61                 :      35107 :   gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
      62                 :      35107 :   if (POINTER_TYPE_P (chrec_type (poly0)))
      63                 :         79 :     gcc_checking_assert (ptrofftype_p (chrec_type (poly1))
      64                 :            :                          && useless_type_conversion_p (type, chrec_type (poly0)));
      65                 :            :   else
      66                 :      35028 :     gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0))
      67                 :            :                          && useless_type_conversion_p (type, chrec_type (poly1)));
      68                 :            : 
      69                 :            :   /*
      70                 :            :     {a, +, b}_1 + {c, +, d}_2  ->  {{a, +, b}_1 + c, +, d}_2,
      71                 :            :     {a, +, b}_2 + {c, +, d}_1  ->  {{c, +, d}_1 + a, +, b}_2,
      72                 :            :     {a, +, b}_x + {c, +, d}_x  ->  {a+c, +, b+d}_x.  */
      73                 :      35107 :   if (flow_loop_nested_p (loop0, loop1))
      74                 :            :     {
      75                 :        164 :       if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
      76                 :         82 :         return build_polynomial_chrec
      77                 :         82 :           (CHREC_VARIABLE (poly1),
      78                 :         82 :            chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
      79                 :        164 :            CHREC_RIGHT (poly1));
      80                 :            :       else
      81                 :         82 :         return build_polynomial_chrec
      82                 :        164 :           (CHREC_VARIABLE (poly1),
      83                 :         82 :            chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
      84                 :         82 :            chrec_fold_multiply (type, CHREC_RIGHT (poly1),
      85                 :         82 :                                 SCALAR_FLOAT_TYPE_P (type)
      86                 :          0 :                                 ? build_real (type, dconstm1)
      87                 :        164 :                                 : build_int_cst_type (type, -1)));
      88                 :            :     }
      89                 :            : 
      90                 :      34943 :   if (flow_loop_nested_p (loop1, loop0))
      91                 :            :     {
      92                 :        402 :       if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
      93                 :        363 :         return build_polynomial_chrec
      94                 :        363 :           (CHREC_VARIABLE (poly0),
      95                 :        363 :            chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
      96                 :        726 :            CHREC_RIGHT (poly0));
      97                 :            :       else
      98                 :         39 :         return build_polynomial_chrec
      99                 :         39 :           (CHREC_VARIABLE (poly0),
     100                 :         39 :            chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
     101                 :         78 :            CHREC_RIGHT (poly0));
     102                 :            :     }
     103                 :            : 
     104                 :            :   /* This function should never be called for chrecs of loops that
     105                 :            :      do not belong to the same loop nest.  */
     106                 :      34541 :   if (loop0 != loop1)
     107                 :            :     {
     108                 :            :       /* It still can happen if we are not in loop-closed SSA form.  */
     109                 :          3 :       gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA));
     110                 :          3 :       return chrec_dont_know;
     111                 :            :     }
     112                 :            : 
     113                 :      34538 :   if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
     114                 :            :     {
     115                 :      20609 :       left = chrec_fold_plus
     116                 :      20609 :         (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
     117                 :      20609 :       right = chrec_fold_plus
     118                 :      20609 :         (rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
     119                 :            :     }
     120                 :            :   else
     121                 :            :     {
     122                 :      13929 :       left = chrec_fold_minus
     123                 :      13929 :         (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
     124                 :      13929 :       right = chrec_fold_minus
     125                 :      13929 :         (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
     126                 :            :     }
     127                 :            : 
     128                 :      53520 :   if (chrec_zerop (right))
     129                 :            :     return left;
     130                 :            :   else
     131                 :      18933 :     return build_polynomial_chrec
     132                 :      18933 :       (CHREC_VARIABLE (poly0), left, right);
     133                 :            : }
     134                 :            : 
     135                 :            : 
     136                 :            : 
     137                 :            : /* Fold the multiplication of two polynomial functions.  */
     138                 :            : 
     139                 :            : static inline tree
     140                 :      10258 : chrec_fold_multiply_poly_poly (tree type,
     141                 :            :                                tree poly0,
     142                 :            :                                tree poly1)
     143                 :            : {
     144                 :      10258 :   tree t0, t1, t2;
     145                 :      10258 :   int var;
     146                 :      10258 :   class loop *loop0 = get_chrec_loop (poly0);
     147                 :      10258 :   class loop *loop1 = get_chrec_loop (poly1);
     148                 :            : 
     149                 :      10258 :   gcc_assert (poly0);
     150                 :      10258 :   gcc_assert (poly1);
     151                 :      10258 :   gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
     152                 :      10258 :   gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
     153                 :      10258 :   gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0))
     154                 :            :                        && useless_type_conversion_p (type, chrec_type (poly1)));
     155                 :            : 
     156                 :            :   /* {a, +, b}_1 * {c, +, d}_2  ->  {c*{a, +, b}_1, +, d}_2,
     157                 :            :      {a, +, b}_2 * {c, +, d}_1  ->  {a*{c, +, d}_1, +, b}_2,
     158                 :            :      {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
     159                 :      10258 :   if (flow_loop_nested_p (loop0, loop1))
     160                 :            :     /* poly0 is a constant wrt. poly1.  */
     161                 :          0 :     return build_polynomial_chrec
     162                 :          0 :       (CHREC_VARIABLE (poly1),
     163                 :          0 :        chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
     164                 :          0 :        CHREC_RIGHT (poly1));
     165                 :            : 
     166                 :      10258 :   if (flow_loop_nested_p (loop1, loop0))
     167                 :            :     /* poly1 is a constant wrt. poly0.  */
     168                 :          0 :     return build_polynomial_chrec
     169                 :          0 :       (CHREC_VARIABLE (poly0),
     170                 :          0 :        chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
     171                 :          0 :        CHREC_RIGHT (poly0));
     172                 :            : 
     173                 :      10258 :   if (loop0 != loop1)
     174                 :            :     {
     175                 :            :       /* It still can happen if we are not in loop-closed SSA form.  */
     176                 :          0 :       gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA));
     177                 :          0 :       return chrec_dont_know;
     178                 :            :     }
     179                 :            : 
     180                 :            :   /* poly0 and poly1 are two polynomials in the same variable,
     181                 :            :      {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
     182                 :            : 
     183                 :            :   /* "a*c".  */
     184                 :      10258 :   t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
     185                 :            : 
     186                 :            :   /* "a*d + b*c".  */
     187                 :      10258 :   t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
     188                 :      30774 :   t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
     189                 :      10258 :                                                        CHREC_RIGHT (poly0),
     190                 :      10258 :                                                        CHREC_LEFT (poly1)));
     191                 :            :   /* "b*d".  */
     192                 :      10258 :   t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
     193                 :            :   /* "a*d + b*c + b*d".  */
     194                 :      10258 :   t1 = chrec_fold_plus (type, t1, t2);
     195                 :            :   /* "2*b*d".  */
     196                 :      20516 :   t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
     197                 :          6 :                             ? build_real (type, dconst2)
     198                 :      10252 :                             : build_int_cst (type, 2), t2);
     199                 :            : 
     200                 :      10258 :   var = CHREC_VARIABLE (poly0);
     201                 :      10258 :   return build_polynomial_chrec (var, t0,
     202                 :      10258 :                                  build_polynomial_chrec (var, t1, t2));
     203                 :            : }
     204                 :            : 
     205                 :            : /* When the operands are automatically_generated_chrec_p, the fold has
     206                 :            :    to respect the semantics of the operands.  */
     207                 :            : 
     208                 :            : static inline tree
     209                 :    3027070 : chrec_fold_automatically_generated_operands (tree op0,
     210                 :            :                                              tree op1)
     211                 :            : {
     212                 :    3027070 :   if (op0 == chrec_dont_know
     213                 :     460979 :       || op1 == chrec_dont_know)
     214                 :            :     return chrec_dont_know;
     215                 :            : 
     216                 :          0 :   if (op0 == chrec_known
     217                 :          0 :       || op1 == chrec_known)
     218                 :            :     return chrec_known;
     219                 :            : 
     220                 :          0 :   if (op0 == chrec_not_analyzed_yet
     221                 :          0 :       || op1 == chrec_not_analyzed_yet)
     222                 :          0 :     return chrec_not_analyzed_yet;
     223                 :            : 
     224                 :            :   /* The default case produces a safe result.  */
     225                 :            :   return chrec_dont_know;
     226                 :            : }
     227                 :            : 
     228                 :            : /* Fold the addition of two chrecs.  */
     229                 :            : 
     230                 :            : static tree
     231                 :   19319800 : chrec_fold_plus_1 (enum tree_code code, tree type,
     232                 :            :                    tree op0, tree op1)
     233                 :            : {
     234                 :   38639500 :   if (automatically_generated_chrec_p (op0)
     235                 :   19319800 :       || automatically_generated_chrec_p (op1))
     236                 :          0 :     return chrec_fold_automatically_generated_operands (op0, op1);
     237                 :            : 
     238                 :   19319800 :   switch (TREE_CODE (op0))
     239                 :            :     {
     240                 :    5175390 :     case POLYNOMIAL_CHREC:
     241                 :    5175390 :       gcc_checking_assert
     242                 :            :         (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
     243                 :    5175390 :       switch (TREE_CODE (op1))
     244                 :            :         {
     245                 :      35107 :         case POLYNOMIAL_CHREC:
     246                 :      35107 :           gcc_checking_assert
     247                 :            :             (!chrec_contains_symbols_defined_in_loop (op1,
     248                 :            :                                                       CHREC_VARIABLE (op1)));
     249                 :      35107 :           return chrec_fold_plus_poly_poly (code, type, op0, op1);
     250                 :            : 
     251                 :     140331 :         CASE_CONVERT:
     252                 :     140331 :           {
     253                 :            :             /* We can strip sign-conversions to signed by performing the
     254                 :            :                operation in unsigned.  */
     255                 :     140331 :             tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
     256                 :     140331 :             if (INTEGRAL_TYPE_P (type)
     257                 :     139622 :                 && INTEGRAL_TYPE_P (optype)
     258                 :     130020 :                 && tree_nop_conversion_p (type, optype)
     259                 :     248103 :                 && TYPE_UNSIGNED (optype))
     260                 :      16687 :               return chrec_convert (type,
     261                 :            :                                     chrec_fold_plus_1 (code, optype,
     262                 :            :                                                        chrec_convert (optype,
     263                 :            :                                                                       op0, NULL),
     264                 :      16687 :                                                        TREE_OPERAND (op1, 0)),
     265                 :      16687 :                                     NULL);
     266                 :     123644 :             if (tree_contains_chrecs (op1, NULL))
     267                 :        445 :               return chrec_dont_know;
     268                 :            :           }
     269                 :            :           /* FALLTHRU */
     270                 :            : 
     271                 :    5123150 :         default:
     272                 :    5123150 :           if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
     273                 :    4811100 :             return build_polynomial_chrec
     274                 :    4811100 :               (CHREC_VARIABLE (op0),
     275                 :    4811100 :                chrec_fold_plus (type, CHREC_LEFT (op0), op1),
     276                 :    9622190 :                CHREC_RIGHT (op0));
     277                 :            :           else
     278                 :     312058 :             return build_polynomial_chrec
     279                 :     312058 :               (CHREC_VARIABLE (op0),
     280                 :     312058 :                chrec_fold_minus (type, CHREC_LEFT (op0), op1),
     281                 :     624116 :                CHREC_RIGHT (op0));
     282                 :            :         }
     283                 :            : 
     284                 :    1946330 :     CASE_CONVERT:
     285                 :    1946330 :       {
     286                 :            :         /* We can strip sign-conversions to signed by performing the
     287                 :            :            operation in unsigned.  */
     288                 :    1946330 :         tree optype = TREE_TYPE (TREE_OPERAND (op0, 0));
     289                 :    1946330 :         if (INTEGRAL_TYPE_P (type)
     290                 :    1945170 :             && INTEGRAL_TYPE_P (optype)
     291                 :    1894950 :             && tree_nop_conversion_p (type, optype)
     292                 :    3469720 :             && TYPE_UNSIGNED (optype))
     293                 :      43040 :           return chrec_convert (type,
     294                 :            :                                 chrec_fold_plus_1 (code, optype,
     295                 :      21520 :                                                    TREE_OPERAND (op0, 0),
     296                 :            :                                                    chrec_convert (optype,
     297                 :            :                                                                   op1, NULL)),
     298                 :      21520 :                                 NULL);
     299                 :    1924810 :         if (tree_contains_chrecs (op0, NULL))
     300                 :       7382 :           return chrec_dont_know;
     301                 :            :       }
     302                 :            :       /* FALLTHRU */
     303                 :            : 
     304                 :   14115500 :     default:
     305                 :   14115500 :       switch (TREE_CODE (op1))
     306                 :            :         {
     307                 :    1388850 :         case POLYNOMIAL_CHREC:
     308                 :    1388850 :           gcc_checking_assert
     309                 :            :             (!chrec_contains_symbols_defined_in_loop (op1,
     310                 :            :                                                       CHREC_VARIABLE (op1)));
     311                 :    1388850 :           if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
     312                 :    1348440 :             return build_polynomial_chrec
     313                 :    1348440 :               (CHREC_VARIABLE (op1),
     314                 :    1348440 :                chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
     315                 :    2696880 :                CHREC_RIGHT (op1));
     316                 :            :           else
     317                 :      40408 :             return build_polynomial_chrec
     318                 :      80816 :               (CHREC_VARIABLE (op1),
     319                 :      40408 :                chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
     320                 :      40408 :                chrec_fold_multiply (type, CHREC_RIGHT (op1),
     321                 :      40408 :                                     SCALAR_FLOAT_TYPE_P (type)
     322                 :          2 :                                     ? build_real (type, dconstm1)
     323                 :      80814 :                                     : build_int_cst_type (type, -1)));
     324                 :            : 
     325                 :    1440380 :         CASE_CONVERT:
     326                 :    1440380 :           if (tree_contains_chrecs (op1, NULL))
     327                 :      10099 :             return chrec_dont_know;
     328                 :            :           /* FALLTHRU */
     329                 :            : 
     330                 :   12716500 :         default:
     331                 :   12716500 :           {
     332                 :   12716500 :             int size = 0;
     333                 :   12716500 :             if ((tree_contains_chrecs (op0, &size)
     334                 :   12716500 :                  || tree_contains_chrecs (op1, &size))
     335                 :   12716500 :                 && size < param_scev_max_expr_size)
     336                 :          0 :               return build2 (code, type, op0, op1);
     337                 :   12716500 :             else if (size < param_scev_max_expr_size)
     338                 :            :               {
     339                 :   12716400 :                 if (code == POINTER_PLUS_EXPR)
     340                 :    2457130 :                   return fold_build_pointer_plus (fold_convert (type, op0),
     341                 :            :                                                   op1);
     342                 :            :                 else
     343                 :   10259300 :                   return fold_build2 (code, type,
     344                 :            :                                       fold_convert (type, op0),
     345                 :            :                                       fold_convert (type, op1));
     346                 :            :               }
     347                 :            :             else
     348                 :         83 :               return chrec_dont_know;
     349                 :            :           }
     350                 :            :         }
     351                 :            :     }
     352                 :            : }
     353                 :            : 
     354                 :            : /* Fold the addition of two chrecs.  */
     355                 :            : 
     356                 :            : tree
     357                 :   22108700 : chrec_fold_plus (tree type,
     358                 :            :                  tree op0,
     359                 :            :                  tree op1)
     360                 :            : {
     361                 :   22108700 :   enum tree_code code;
     362                 :   42655900 :   if (automatically_generated_chrec_p (op0)
     363                 :   22108700 :       || automatically_generated_chrec_p (op1))
     364                 :    1897890 :     return chrec_fold_automatically_generated_operands (op0, op1);
     365                 :            : 
     366                 :   20210800 :   if (integer_zerop (op0))
     367                 :    1983170 :     return chrec_convert (type, op1, NULL);
     368                 :   18227600 :   if (integer_zerop (op1))
     369                 :     600486 :     return chrec_convert (type, op0, NULL);
     370                 :            : 
     371                 :   17627100 :   if (POINTER_TYPE_P (type))
     372                 :            :     code = POINTER_PLUS_EXPR;
     373                 :            :   else
     374                 :   13766700 :     code = PLUS_EXPR;
     375                 :            : 
     376                 :   17627100 :   return chrec_fold_plus_1 (code, type, op0, op1);
     377                 :            : }
     378                 :            : 
     379                 :            : /* Fold the subtraction of two chrecs.  */
     380                 :            : 
     381                 :            : tree
     382                 :    1997770 : chrec_fold_minus (tree type,
     383                 :            :                   tree op0,
     384                 :            :                   tree op1)
     385                 :            : {
     386                 :    3754590 :   if (automatically_generated_chrec_p (op0)
     387                 :    1997770 :       || automatically_generated_chrec_p (op1))
     388                 :     290708 :     return chrec_fold_automatically_generated_operands (op0, op1);
     389                 :            : 
     390                 :    1707060 :   if (integer_zerop (op1))
     391                 :            :     return op0;
     392                 :            : 
     393                 :    1654430 :   return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
     394                 :            : }
     395                 :            : 
     396                 :            : /* Fold the multiplication of two chrecs.  */
     397                 :            : 
     398                 :            : tree
     399                 :   11076900 : chrec_fold_multiply (tree type,
     400                 :            :                      tree op0,
     401                 :            :                      tree op1)
     402                 :            : {
     403                 :   21390100 :   if (automatically_generated_chrec_p (op0)
     404                 :   11076900 :       || automatically_generated_chrec_p (op1))
     405                 :     838472 :     return chrec_fold_automatically_generated_operands (op0, op1);
     406                 :            : 
     407                 :   10238400 :   switch (TREE_CODE (op0))
     408                 :            :     {
     409                 :    1521180 :     case POLYNOMIAL_CHREC:
     410                 :    1521180 :       gcc_checking_assert
     411                 :            :         (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
     412                 :    1521180 :       switch (TREE_CODE (op1))
     413                 :            :         {
     414                 :      10258 :         case POLYNOMIAL_CHREC:
     415                 :      10258 :           gcc_checking_assert
     416                 :            :             (!chrec_contains_symbols_defined_in_loop (op1,
     417                 :            :                                                       CHREC_VARIABLE (op1)));
     418                 :      10258 :           return chrec_fold_multiply_poly_poly (type, op0, op1);
     419                 :            : 
     420                 :      24829 :         CASE_CONVERT:
     421                 :      24829 :           if (tree_contains_chrecs (op1, NULL))
     422                 :         92 :             return chrec_dont_know;
     423                 :            :           /* FALLTHRU */
     424                 :            : 
     425                 :    1510840 :         default:
     426                 :    1510840 :           if (integer_onep (op1))
     427                 :            :             return op0;
     428                 :    1510460 :           if (integer_zerop (op1))
     429                 :        289 :             return build_int_cst (type, 0);
     430                 :            : 
     431                 :    1510170 :           return build_polynomial_chrec
     432                 :    3020340 :             (CHREC_VARIABLE (op0),
     433                 :    1510170 :              chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
     434                 :    3020340 :              chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
     435                 :            :         }
     436                 :            : 
     437                 :    3320920 :     CASE_CONVERT:
     438                 :    3320920 :       if (tree_contains_chrecs (op0, NULL))
     439                 :      12816 :         return chrec_dont_know;
     440                 :            :       /* FALLTHRU */
     441                 :            : 
     442                 :    8704390 :     default:
     443                 :    8704390 :       if (integer_onep (op0))
     444                 :            :         return op1;
     445                 :            : 
     446                 :    6766940 :       if (integer_zerop (op0))
     447                 :     736812 :         return build_int_cst (type, 0);
     448                 :            : 
     449                 :    6030130 :       switch (TREE_CODE (op1))
     450                 :            :         {
     451                 :     129455 :         case POLYNOMIAL_CHREC:
     452                 :     129455 :           gcc_checking_assert
     453                 :            :             (!chrec_contains_symbols_defined_in_loop (op1,
     454                 :            :                                                       CHREC_VARIABLE (op1)));
     455                 :     129455 :           return build_polynomial_chrec
     456                 :     258910 :             (CHREC_VARIABLE (op1),
     457                 :     129455 :              chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
     458                 :     258910 :              chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
     459                 :            : 
     460                 :     951392 :         CASE_CONVERT:
     461                 :     951392 :           if (tree_contains_chrecs (op1, NULL))
     462                 :        133 :             return chrec_dont_know;
     463                 :            :           /* FALLTHRU */
     464                 :            : 
     465                 :    5900540 :         default:
     466                 :    5900540 :           if (integer_onep (op1))
     467                 :            :             return op0;
     468                 :    5859480 :           if (integer_zerop (op1))
     469                 :        328 :             return build_int_cst (type, 0);
     470                 :    5859160 :           return fold_build2 (MULT_EXPR, type, op0, op1);
     471                 :            :         }
     472                 :            :     }
     473                 :            : }
     474                 :            : 
     475                 :            : 
     476                 :            : 
     477                 :            : /* Operations.  */
     478                 :            : 
     479                 :            : /* Evaluate the binomial coefficient.  Return NULL_TREE if the intermediate
     480                 :            :    calculation overflows, otherwise return C(n,k) with type TYPE.  */
     481                 :            : 
     482                 :            : static tree
     483                 :        857 : tree_fold_binomial (tree type, tree n, unsigned int k)
     484                 :            : {
     485                 :        857 :   wi::overflow_type overflow;
     486                 :        857 :   unsigned int i;
     487                 :            : 
     488                 :            :   /* Handle the most frequent cases.  */
     489                 :        857 :   if (k == 0)
     490                 :        281 :     return build_int_cst (type, 1);
     491                 :        576 :   if (k == 1)
     492                 :        281 :     return fold_convert (type, n);
     493                 :            : 
     494                 :        295 :   widest_int num = wi::to_widest (n);
     495                 :            : 
     496                 :            :   /* Check that k <= n.  */
     497                 :        295 :   if (wi::ltu_p (num, k))
     498                 :            :     return NULL_TREE;
     499                 :            : 
     500                 :            :   /* Denominator = 2.  */
     501                 :        291 :   widest_int denom = 2;
     502                 :            : 
     503                 :            :   /* Index = Numerator-1.  */
     504                 :        291 :   widest_int idx = num - 1;
     505                 :            : 
     506                 :            :   /* Numerator = Numerator*Index = n*(n-1).  */
     507                 :        291 :   num = wi::smul (num, idx, &overflow);
     508                 :        291 :   if (overflow)
     509                 :            :     return NULL_TREE;
     510                 :            : 
     511                 :        291 :   for (i = 3; i <= k; i++)
     512                 :            :     {
     513                 :            :       /* Index--.  */
     514                 :          0 :       --idx;
     515                 :            : 
     516                 :            :       /* Numerator *= Index.  */
     517                 :          0 :       num = wi::smul (num, idx, &overflow);
     518                 :          0 :       if (overflow)
     519                 :            :         return NULL_TREE;
     520                 :            : 
     521                 :            :       /* Denominator *= i.  */
     522                 :          0 :       denom *= i;
     523                 :            :     }
     524                 :            : 
     525                 :            :   /* Result = Numerator / Denominator.  */
     526                 :        291 :   num = wi::udiv_trunc (num, denom);
     527                 :        291 :   if (! wi::fits_to_tree_p (num, type))
     528                 :            :     return NULL_TREE;
     529                 :        281 :   return wide_int_to_tree (type, num);
     530                 :            : }
     531                 :            : 
     532                 :            : /* Helper function.  Use the Newton's interpolating formula for
     533                 :            :    evaluating the value of the evolution function.
     534                 :            :    The result may be in an unsigned type of CHREC.  */
     535                 :            : 
     536                 :            : static tree
     537                 :        885 : chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
     538                 :            : {
     539                 :        885 :   tree arg0, arg1, binomial_n_k;
     540                 :        885 :   tree type = TREE_TYPE (chrec);
     541                 :        885 :   class loop *var_loop = get_loop (cfun, var);
     542                 :            : 
     543                 :        885 :   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
     544                 :        885 :          && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
     545                 :          0 :     chrec = CHREC_LEFT (chrec);
     546                 :            : 
     547                 :            :   /* The formula associates the expression and thus we have to make
     548                 :            :      sure to not introduce undefined overflow.  */
     549                 :        885 :   tree ctype = type;
     550                 :        885 :   if (INTEGRAL_TYPE_P (type)
     551                 :       1659 :       && ! TYPE_OVERFLOW_WRAPS (type))
     552                 :        774 :     ctype = unsigned_type_for (type);
     553                 :            : 
     554                 :        885 :   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
     555                 :        885 :       && CHREC_VARIABLE (chrec) == var)
     556                 :            :     {
     557                 :        590 :       arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
     558                 :        590 :       if (arg1 == chrec_dont_know)
     559                 :            :         return chrec_dont_know;
     560                 :        562 :       binomial_n_k = tree_fold_binomial (ctype, n, k);
     561                 :        562 :       if (!binomial_n_k)
     562                 :          0 :         return chrec_dont_know;
     563                 :        562 :       tree l = chrec_convert (ctype, CHREC_LEFT (chrec), NULL);
     564                 :        562 :       arg0 = fold_build2 (MULT_EXPR, ctype, l, binomial_n_k);
     565                 :        562 :       return chrec_fold_plus (ctype, arg0, arg1);
     566                 :            :     }
     567                 :            : 
     568                 :        295 :   binomial_n_k = tree_fold_binomial (ctype, n, k);
     569                 :        295 :   if (!binomial_n_k)
     570                 :         14 :     return chrec_dont_know;
     571                 :            : 
     572                 :        281 :   return fold_build2 (MULT_EXPR, ctype,
     573                 :            :                       chrec_convert (ctype, chrec, NULL), binomial_n_k);
     574                 :            : }
     575                 :            : 
     576                 :            : /* Evaluates "CHREC (X)" when the varying variable is VAR.
     577                 :            :    Example:  Given the following parameters,
     578                 :            : 
     579                 :            :    var = 1
     580                 :            :    chrec = {3, +, 4}_1
     581                 :            :    x = 10
     582                 :            : 
     583                 :            :    The result is given by the Newton's interpolating formula:
     584                 :            :    3 * \binom{10}{0} + 4 * \binom{10}{1}.
     585                 :            : */
     586                 :            : 
     587                 :            : tree
     588                 :     445533 : chrec_apply (unsigned var,
     589                 :            :              tree chrec,
     590                 :            :              tree x)
     591                 :            : {
     592                 :     445533 :   tree type = chrec_type (chrec);
     593                 :     445533 :   tree res = chrec_dont_know;
     594                 :            : 
     595                 :     891066 :   if (automatically_generated_chrec_p (chrec)
     596                 :     466523 :       || automatically_generated_chrec_p (x)
     597                 :            : 
     598                 :            :       /* When the symbols are defined in an outer loop, it is possible
     599                 :            :          to symbolically compute the apply, since the symbols are
     600                 :            :          constants with respect to the varying loop.  */
     601                 :     445533 :       || chrec_contains_symbols_defined_in_loop (chrec, var))
     602                 :      20990 :     return chrec_dont_know;
     603                 :            : 
     604                 :     424543 :   if (dump_file && (dump_flags & TDF_SCEV))
     605                 :          0 :     fprintf (dump_file, "(chrec_apply \n");
     606                 :            : 
     607                 :     424543 :   if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
     608                 :         30 :     x = build_real_from_int_cst (type, x);
     609                 :            : 
     610                 :     424543 :   switch (TREE_CODE (chrec))
     611                 :            :     {
     612                 :     423424 :     case POLYNOMIAL_CHREC:
     613                 :     423424 :       if (evolution_function_is_affine_p (chrec))
     614                 :            :         {
     615                 :     422332 :           if (CHREC_VARIABLE (chrec) != var)
     616                 :        431 :             return build_polynomial_chrec
     617                 :        862 :               (CHREC_VARIABLE (chrec),
     618                 :        431 :                chrec_apply (var, CHREC_LEFT (chrec), x),
     619                 :        862 :                chrec_apply (var, CHREC_RIGHT (chrec), x));
     620                 :            : 
     621                 :            :           /* "{a, +, b} (x)"  ->  "a + b*x".  */
     622                 :     421901 :           x = chrec_convert_rhs (type, x, NULL);
     623                 :     421901 :           res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x);
     624                 :     421901 :           res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
     625                 :            :         }
     626                 :       1092 :       else if (TREE_CODE (x) == INTEGER_CST
     627                 :       1092 :                && tree_int_cst_sgn (x) == 1)
     628                 :            :         /* testsuite/.../ssa-chrec-38.c.  */
     629                 :        295 :         res = chrec_convert (type, chrec_evaluate (var, chrec, x, 0), NULL);
     630                 :            :       else
     631                 :        797 :         res = chrec_dont_know;
     632                 :            :       break;
     633                 :            : 
     634                 :        177 :     CASE_CONVERT:
     635                 :        177 :       res = chrec_convert (TREE_TYPE (chrec),
     636                 :        177 :                            chrec_apply (var, TREE_OPERAND (chrec, 0), x),
     637                 :            :                            NULL);
     638                 :        177 :       break;
     639                 :            : 
     640                 :            :     default:
     641                 :            :       res = chrec;
     642                 :            :       break;
     643                 :            :     }
     644                 :            : 
     645                 :     424112 :   if (dump_file && (dump_flags & TDF_SCEV))
     646                 :            :     {
     647                 :          0 :       fprintf (dump_file, "  (varying_loop = %d\n", var);
     648                 :          0 :       fprintf (dump_file, ")\n  (chrec = ");
     649                 :          0 :       print_generic_expr (dump_file, chrec);
     650                 :          0 :       fprintf (dump_file, ")\n  (x = ");
     651                 :          0 :       print_generic_expr (dump_file, x);
     652                 :          0 :       fprintf (dump_file, ")\n  (res = ");
     653                 :          0 :       print_generic_expr (dump_file, res);
     654                 :          0 :       fprintf (dump_file, "))\n");
     655                 :            :     }
     656                 :            : 
     657                 :            :   return res;
     658                 :            : }
     659                 :            : 
     660                 :            : /* For a given CHREC and an induction variable map IV_MAP that maps
     661                 :            :    (loop->num, expr) for every loop number of the current_loops an
     662                 :            :    expression, calls chrec_apply when the expression is not NULL.  */
     663                 :            : 
     664                 :            : tree
     665                 :        779 : chrec_apply_map (tree chrec, vec<tree> iv_map)
     666                 :            : {
     667                 :        779 :   int i;
     668                 :        779 :   tree expr;
     669                 :            : 
     670                 :       7310 :   FOR_EACH_VEC_ELT (iv_map, i, expr)
     671                 :       6531 :     if (expr)
     672                 :       1353 :       chrec = chrec_apply (i, chrec, expr);
     673                 :            : 
     674                 :        779 :   return chrec;
     675                 :            : }
     676                 :            : 
     677                 :            : /* Replaces the initial condition in CHREC with INIT_COND.  */
     678                 :            : 
     679                 :            : tree
     680                 :     400343 : chrec_replace_initial_condition (tree chrec,
     681                 :            :                                  tree init_cond)
     682                 :            : {
     683                 :     400343 :   if (automatically_generated_chrec_p (chrec))
     684                 :            :     return chrec;
     685                 :            : 
     686                 :     400343 :   gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
     687                 :            : 
     688                 :     400343 :   switch (TREE_CODE (chrec))
     689                 :            :     {
     690                 :     202986 :     case POLYNOMIAL_CHREC:
     691                 :     202986 :       return build_polynomial_chrec
     692                 :     202986 :         (CHREC_VARIABLE (chrec),
     693                 :     202986 :          chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
     694                 :     405972 :          CHREC_RIGHT (chrec));
     695                 :            : 
     696                 :            :     default:
     697                 :            :       return init_cond;
     698                 :            :     }
     699                 :            : }
     700                 :            : 
     701                 :            : /* Returns the initial condition of a given CHREC.  */
     702                 :            : 
     703                 :            : tree
     704                 :    6221290 : initial_condition (tree chrec)
     705                 :            : {
     706                 :    9780540 :   if (automatically_generated_chrec_p (chrec))
     707                 :            :     return chrec;
     708                 :            : 
     709                 :    8998700 :   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
     710                 :    3559250 :     return initial_condition (CHREC_LEFT (chrec));
     711                 :            :   else
     712                 :            :     return chrec;
     713                 :            : }
     714                 :            : 
     715                 :            : /* Returns a univariate function that represents the evolution in
     716                 :            :    LOOP_NUM.  Mask the evolution of any other loop.  */
     717                 :            : 
     718                 :            : tree
     719                 :   29427500 : hide_evolution_in_other_loops_than_loop (tree chrec,
     720                 :            :                                          unsigned loop_num)
     721                 :            : {
     722                 :   29428400 :   class loop *loop = get_loop (cfun, loop_num), *chloop;
     723                 :   29428400 :   if (automatically_generated_chrec_p (chrec))
     724                 :            :     return chrec;
     725                 :            : 
     726                 :   29428400 :   switch (TREE_CODE (chrec))
     727                 :            :     {
     728                 :    2045910 :     case POLYNOMIAL_CHREC:
     729                 :    2045910 :       chloop = get_chrec_loop (chrec);
     730                 :            : 
     731                 :    2045910 :       if (chloop == loop)
     732                 :    1821730 :         return build_polynomial_chrec
     733                 :    1821730 :           (loop_num,
     734                 :    1821730 :            hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
     735                 :            :                                                     loop_num),
     736                 :    3643450 :            CHREC_RIGHT (chrec));
     737                 :            : 
     738                 :     224181 :       else if (flow_loop_nested_p (chloop, loop))
     739                 :            :         /* There is no evolution in this loop.  */
     740                 :     223193 :         return initial_condition (chrec);
     741                 :            : 
     742                 :        988 :       else if (flow_loop_nested_p (loop, chloop))
     743                 :        988 :         return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
     744                 :        988 :                                                         loop_num);
     745                 :            : 
     746                 :            :       else
     747                 :          0 :         return chrec_dont_know;
     748                 :            : 
     749                 :            :     default:
     750                 :            :       return chrec;
     751                 :            :     }
     752                 :            : }
     753                 :            : 
     754                 :            : /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
     755                 :            :    true, otherwise returns the initial condition in LOOP_NUM.  */
     756                 :            : 
     757                 :            : static tree
     758                 :   20759900 : chrec_component_in_loop_num (tree chrec,
     759                 :            :                              unsigned loop_num,
     760                 :            :                              bool right)
     761                 :            : {
     762                 :   20759900 :   tree component;
     763                 :   20759900 :   class loop *loop = get_loop (cfun, loop_num), *chloop;
     764                 :            : 
     765                 :   20759900 :   if (automatically_generated_chrec_p (chrec))
     766                 :            :     return chrec;
     767                 :            : 
     768                 :   19978000 :   switch (TREE_CODE (chrec))
     769                 :            :     {
     770                 :   16402300 :     case POLYNOMIAL_CHREC:
     771                 :   16402300 :       chloop = get_chrec_loop (chrec);
     772                 :            : 
     773                 :   16402300 :       if (chloop == loop)
     774                 :            :         {
     775                 :   15677800 :           if (right)
     776                 :    8432720 :             component = CHREC_RIGHT (chrec);
     777                 :            :           else
     778                 :    7245060 :             component = CHREC_LEFT (chrec);
     779                 :            : 
     780                 :   15677800 :           if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
     781                 :   15677800 :               || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
     782                 :            :             return component;
     783                 :            : 
     784                 :            :           else
     785                 :          0 :             return build_polynomial_chrec
     786                 :          0 :               (loop_num,
     787                 :          0 :                chrec_component_in_loop_num (CHREC_LEFT (chrec),
     788                 :            :                                             loop_num,
     789                 :            :                                             right),
     790                 :          0 :                component);
     791                 :            :         }
     792                 :            : 
     793                 :     724552 :       else if (flow_loop_nested_p (chloop, loop))
     794                 :            :         /* There is no evolution part in this loop.  */
     795                 :            :         return NULL_TREE;
     796                 :            : 
     797                 :            :       else
     798                 :            :         {
     799                 :     724552 :           gcc_assert (flow_loop_nested_p (loop, chloop));
     800                 :     724552 :           return chrec_component_in_loop_num (CHREC_LEFT (chrec),
     801                 :            :                                               loop_num,
     802                 :     724552 :                                               right);
     803                 :            :         }
     804                 :            : 
     805                 :    3575700 :      default:
     806                 :    3575700 :       if (right)
     807                 :            :         return NULL_TREE;
     808                 :            :       else
     809                 :     527589 :         return chrec;
     810                 :            :     }
     811                 :            : }
     812                 :            : 
     813                 :            : /* Returns the evolution part in LOOP_NUM.  Example: the call
     814                 :            :    evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
     815                 :            :    {1, +, 2}_1  */
     816                 :            : 
     817                 :            : tree
     818                 :   12262700 : evolution_part_in_loop_num (tree chrec,
     819                 :            :                             unsigned loop_num)
     820                 :            : {
     821                 :   12262700 :   return chrec_component_in_loop_num (chrec, loop_num, true);
     822                 :            : }
     823                 :            : 
     824                 :            : /* Returns the initial condition in LOOP_NUM.  Example: the call
     825                 :            :    initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
     826                 :            :    {0, +, 1}_1  */
     827                 :            : 
     828                 :            : tree
     829                 :    7772650 : initial_condition_in_loop_num (tree chrec,
     830                 :            :                                unsigned loop_num)
     831                 :            : {
     832                 :    7772650 :   return chrec_component_in_loop_num (chrec, loop_num, false);
     833                 :            : }
     834                 :            : 
     835                 :            : /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
     836                 :            :    This function is essentially used for setting the evolution to
     837                 :            :    chrec_dont_know, for example after having determined that it is
     838                 :            :    impossible to say how many times a loop will execute.  */
     839                 :            : 
     840                 :            : tree
     841                 :          0 : reset_evolution_in_loop (unsigned loop_num,
     842                 :            :                          tree chrec,
     843                 :            :                          tree new_evol)
     844                 :            : {
     845                 :          0 :   class loop *loop = get_loop (cfun, loop_num);
     846                 :            : 
     847                 :          0 :   if (POINTER_TYPE_P (chrec_type (chrec)))
     848                 :          0 :     gcc_assert (ptrofftype_p (chrec_type (new_evol)));
     849                 :            :   else
     850                 :          0 :     gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
     851                 :            : 
     852                 :          0 :   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
     853                 :          0 :       && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
     854                 :            :     {
     855                 :          0 :       tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
     856                 :            :                                            new_evol);
     857                 :          0 :       tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
     858                 :            :                                             new_evol);
     859                 :          0 :       return build_polynomial_chrec (CHREC_VARIABLE (chrec), left, right);
     860                 :            :     }
     861                 :            : 
     862                 :          0 :   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
     863                 :          0 :          && CHREC_VARIABLE (chrec) == loop_num)
     864                 :          0 :     chrec = CHREC_LEFT (chrec);
     865                 :            : 
     866                 :          0 :   return build_polynomial_chrec (loop_num, chrec, new_evol);
     867                 :            : }
     868                 :            : 
     869                 :            : /* Merges two evolution functions that were found by following two
     870                 :            :    alternate paths of a conditional expression.  */
     871                 :            : 
     872                 :            : tree
     873                 :    8055960 : chrec_merge (tree chrec1,
     874                 :            :              tree chrec2)
     875                 :            : {
     876                 :    8055960 :   if (chrec1 == chrec_dont_know
     877                 :    8055960 :       || chrec2 == chrec_dont_know)
     878                 :            :     return chrec_dont_know;
     879                 :            : 
     880                 :    6504470 :   if (chrec1 == chrec_known
     881                 :    6504470 :       || chrec2 == chrec_known)
     882                 :            :     return chrec_known;
     883                 :            : 
     884                 :    6504470 :   if (chrec1 == chrec_not_analyzed_yet)
     885                 :            :     return chrec2;
     886                 :    1370680 :   if (chrec2 == chrec_not_analyzed_yet)
     887                 :            :     return chrec1;
     888                 :            : 
     889                 :    1370680 :   if (eq_evolutions_p (chrec1, chrec2))
     890                 :            :     return chrec1;
     891                 :            : 
     892                 :     953795 :   return chrec_dont_know;
     893                 :            : }
     894                 :            : 
     895                 :            : 
     896                 :            : 
     897                 :            : /* Observers.  */
     898                 :            : 
     899                 :            : /* Helper function for is_multivariate_chrec.  */
     900                 :            : 
     901                 :            : static bool
     902                 :          0 : is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
     903                 :            : {
     904                 :          0 :   if (chrec == NULL_TREE)
     905                 :            :     return false;
     906                 :            : 
     907                 :          0 :   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
     908                 :            :     {
     909                 :          0 :       if (CHREC_VARIABLE (chrec) != rec_var)
     910                 :            :         return true;
     911                 :            :       else
     912                 :          0 :         return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
     913                 :          0 :                 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
     914                 :            :     }
     915                 :            :   else
     916                 :            :     return false;
     917                 :            : }
     918                 :            : 
     919                 :            : /* Determine whether the given chrec is multivariate or not.  */
     920                 :            : 
     921                 :            : bool
     922                 :          0 : is_multivariate_chrec (const_tree chrec)
     923                 :            : {
     924                 :          0 :   if (chrec == NULL_TREE)
     925                 :            :     return false;
     926                 :            : 
     927                 :          0 :   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
     928                 :          0 :     return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
     929                 :          0 :                                        CHREC_VARIABLE (chrec))
     930                 :          0 :             || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
     931                 :          0 :                                           CHREC_VARIABLE (chrec)));
     932                 :            :   else
     933                 :            :     return false;
     934                 :            : }
     935                 :            : 
     936                 :            : /* Determines whether the chrec contains symbolic names or not.  If LOOP isn't
     937                 :            :    NULL, we also consider chrec wrto outer loops of LOOP as symbol.  */
     938                 :            : 
     939                 :            : static bool
     940                 :   15570200 : chrec_contains_symbols (const_tree chrec, hash_set<const_tree> &visited,
     941                 :            :                         class loop *loop)
     942                 :            : {
     943                 :   15570200 :   int i, n;
     944                 :            : 
     945                 :   15570200 :   if (chrec == NULL_TREE)
     946                 :            :     return false;
     947                 :            : 
     948                 :   15570200 :   if (TREE_CODE (chrec) == SSA_NAME
     949                 :   15570200 :       || VAR_P (chrec)
     950                 :   12473700 :       || TREE_CODE (chrec) == POLY_INT_CST
     951                 :   12473700 :       || TREE_CODE (chrec) == PARM_DECL
     952                 :   12473700 :       || TREE_CODE (chrec) == FUNCTION_DECL
     953                 :   12473100 :       || TREE_CODE (chrec) == LABEL_DECL
     954                 :   12473100 :       || TREE_CODE (chrec) == RESULT_DECL
     955                 :   12473000 :       || TREE_CODE (chrec) == FIELD_DECL)
     956                 :            :     return true;
     957                 :            : 
     958                 :   12473000 :   if (loop != NULL
     959                 :        576 :       && TREE_CODE (chrec) == POLYNOMIAL_CHREC
     960                 :   12473200 :       && flow_loop_nested_p (get_chrec_loop (chrec), loop))
     961                 :            :     return true;
     962                 :            : 
     963                 :   12473000 :   if (visited.add (chrec))
     964                 :            :     return false;
     965                 :            : 
     966                 :   12132700 :   n = TREE_OPERAND_LENGTH (chrec);
     967                 :   18581900 :   for (i = 0; i < n; i++)
     968                 :    8804380 :     if (chrec_contains_symbols (TREE_OPERAND (chrec, i), visited, loop))
     969                 :            :       return true;
     970                 :            :   return false;
     971                 :            : }
     972                 :            : 
     973                 :            : /* Return true if CHREC contains any symbols.  If LOOP is not NULL, check if
     974                 :            :    CHREC contains any chrec which is invariant wrto the loop (nest), in other
     975                 :            :    words, chrec defined by outer loops of loop, so from LOOP's point of view,
     976                 :            :    the chrec is considered as a SYMBOL.  */
     977                 :            : 
     978                 :            : bool
     979                 :    6765820 : chrec_contains_symbols (const_tree chrec, class loop* loop)
     980                 :            : {
     981                 :    6765820 :   hash_set<const_tree> visited;
     982                 :    6765820 :   return chrec_contains_symbols (chrec, visited, loop);
     983                 :            : }
     984                 :            : 
     985                 :            : /* Return true when CHREC contains symbolic names defined in
     986                 :            :    LOOP_NB.  */
     987                 :            : 
     988                 :            : static bool
     989                 :  195735000 : chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb,
     990                 :            :                                         hash_set<const_tree> &visited)
     991                 :            : {
     992                 :  195735000 :   int i, n;
     993                 :            : 
     994                 :  195735000 :   if (chrec == NULL_TREE)
     995                 :            :     return false;
     996                 :            : 
     997                 :  195734000 :   if (is_gimple_min_invariant (chrec))
     998                 :            :     return false;
     999                 :            : 
    1000                 :  123430000 :   if (TREE_CODE (chrec) == SSA_NAME)
    1001                 :            :     {
    1002                 :   43878200 :       gimple *def;
    1003                 :   43878200 :       loop_p def_loop, loop;
    1004                 :            : 
    1005                 :   43878200 :       if (SSA_NAME_IS_DEFAULT_DEF (chrec))
    1006                 :            :         return false;
    1007                 :            : 
    1008                 :   41416700 :       def = SSA_NAME_DEF_STMT (chrec);
    1009                 :   41416700 :       def_loop = loop_containing_stmt (def);
    1010                 :   41416700 :       loop = get_loop (cfun, loop_nb);
    1011                 :            : 
    1012                 :   41416700 :       if (def_loop == NULL)
    1013                 :            :         return false;
    1014                 :            : 
    1015                 :   41416700 :       if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
    1016                 :    1718350 :         return true;
    1017                 :            : 
    1018                 :            :       return false;
    1019                 :            :     }
    1020                 :            : 
    1021                 :   79551400 :   if (visited.add (chrec))
    1022                 :            :     return false;
    1023                 :            : 
    1024                 :   79533000 :   n = TREE_OPERAND_LENGTH (chrec);
    1025                 :  209569000 :   for (i = 0; i < n; i++)
    1026                 :  130585000 :     if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
    1027                 :            :                                                 loop_nb, visited))
    1028                 :            :       return true;
    1029                 :            :   return false;
    1030                 :            : }
    1031                 :            : 
    1032                 :            : /* Return true when CHREC contains symbolic names defined in
    1033                 :            :    LOOP_NB.  */
    1034                 :            : 
    1035                 :            : bool
    1036                 :   65150600 : chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
    1037                 :            : {
    1038                 :   65150600 :   hash_set<const_tree> visited;
    1039                 :   65150600 :   return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited);
    1040                 :            : }
    1041                 :            : 
    1042                 :            : /* Determines whether the chrec contains undetermined coefficients.  */
    1043                 :            : 
    1044                 :            : static bool
    1045                 :  114344000 : chrec_contains_undetermined (const_tree chrec, hash_set<const_tree> &visited)
    1046                 :            : {
    1047                 :  114344000 :   int i, n;
    1048                 :            : 
    1049                 :  114344000 :   if (chrec == chrec_dont_know)
    1050                 :            :     return true;
    1051                 :            : 
    1052                 :  100828000 :   if (chrec == NULL_TREE)
    1053                 :            :     return false;
    1054                 :            : 
    1055                 :  100746000 :   if (visited.add (chrec))
    1056                 :            :     return false;
    1057                 :            : 
    1058                 :   94003800 :   n = TREE_OPERAND_LENGTH (chrec);
    1059                 :  158033000 :   for (i = 0; i < n; i++)
    1060                 :   64029700 :     if (chrec_contains_undetermined (TREE_OPERAND (chrec, i), visited))
    1061                 :            :       return true;
    1062                 :            :   return false;
    1063                 :            : }
    1064                 :            : 
    1065                 :            : bool
    1066                 :   50314100 : chrec_contains_undetermined (const_tree chrec)
    1067                 :            : {
    1068                 :   50314100 :   hash_set<const_tree> visited;
    1069                 :   50314100 :   return chrec_contains_undetermined (chrec, visited);
    1070                 :            : }
    1071                 :            : 
    1072                 :            : /* Determines whether the tree EXPR contains chrecs, and increment
    1073                 :            :    SIZE if it is not a NULL pointer by an estimation of the depth of
    1074                 :            :    the tree.  */
    1075                 :            : 
    1076                 :            : static bool
    1077                 :  226955000 : tree_contains_chrecs (const_tree expr, int *size, hash_set<const_tree> &visited)
    1078                 :            : {
    1079                 :  226955000 :   int i, n;
    1080                 :            : 
    1081                 :  226955000 :   if (expr == NULL_TREE)
    1082                 :            :     return false;
    1083                 :            : 
    1084                 :  226816000 :   if (size)
    1085                 :   58793400 :     (*size)++;
    1086                 :            : 
    1087                 :  226816000 :   if (tree_is_chrec (expr))
    1088                 :            :     return true;
    1089                 :            : 
    1090                 :  214971000 :   if (visited.add (expr))
    1091                 :            :     return false;
    1092                 :            : 
    1093                 :  213997000 :   n = TREE_OPERAND_LENGTH (expr);
    1094                 :  334265000 :   for (i = 0; i < n; i++)
    1095                 :  120373000 :     if (tree_contains_chrecs (TREE_OPERAND (expr, i), size, visited))
    1096                 :            :       return true;
    1097                 :            :   return false;
    1098                 :            : }
    1099                 :            : 
    1100                 :            : bool
    1101                 :  106582000 : tree_contains_chrecs (const_tree expr, int *size)
    1102                 :            : {
    1103                 :  106582000 :   hash_set<const_tree> visited;
    1104                 :  106582000 :   return tree_contains_chrecs (expr, size, visited);
    1105                 :            : }
    1106                 :            : 
    1107                 :            : 
    1108                 :            : /* Recursive helper function.  */
    1109                 :            : 
    1110                 :            : static bool
    1111                 :   19940700 : evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
    1112                 :            : {
    1113                 :   39881500 :   if (evolution_function_is_constant_p (chrec))
    1114                 :            :     return true;
    1115                 :            : 
    1116                 :    5923200 :   if (TREE_CODE (chrec) == SSA_NAME
    1117                 :    5923200 :       && (loopnum == 0
    1118                 :    2022300 :           || expr_invariant_in_loop_p (get_loop (cfun, loopnum), chrec)))
    1119                 :    1973000 :     return true;
    1120                 :            : 
    1121                 :    3950210 :   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
    1122                 :            :     {
    1123                 :    1950730 :       if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
    1124                 :     104902 :           || flow_loop_nested_p (get_loop (cfun, loopnum),
    1125                 :     104902 :                                  get_chrec_loop (chrec))
    1126                 :       2885 :           || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
    1127                 :            :                                                      loopnum)
    1128                 :    1953610 :           || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
    1129                 :            :                                                      loopnum))
    1130                 :    1947840 :         return false;
    1131                 :            :       return true;
    1132                 :            :     }
    1133                 :            : 
    1134                 :    1999480 :   switch (TREE_OPERAND_LENGTH (chrec))
    1135                 :            :     {
    1136                 :    1481830 :     case 2:
    1137                 :    1481830 :       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
    1138                 :            :                                                   loopnum))
    1139                 :            :         return false;
    1140                 :            :       /* FALLTHRU */
    1141                 :            : 
    1142                 :    1935200 :     case 1:
    1143                 :    1935200 :       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
    1144                 :            :                                                   loopnum))
    1145                 :      19056 :         return false;
    1146                 :            :       return true;
    1147                 :            : 
    1148                 :            :     default:
    1149                 :            :       return false;
    1150                 :            :     }
    1151                 :            : 
    1152                 :            :   return false;
    1153                 :            : }
    1154                 :            : 
    1155                 :            : /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
    1156                 :            : 
    1157                 :            : bool
    1158                 :   11843500 : evolution_function_is_invariant_p (tree chrec, int loopnum)
    1159                 :            : {
    1160                 :   11843500 :   return evolution_function_is_invariant_rec_p (chrec, loopnum);
    1161                 :            : }
    1162                 :            : 
    1163                 :            : /* Determine whether the given tree is an affine multivariate
    1164                 :            :    evolution.  */
    1165                 :            : 
    1166                 :            : bool
    1167                 :    2487980 : evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
    1168                 :            : {
    1169                 :    2487980 :   if (chrec == NULL_TREE)
    1170                 :            :     return false;
    1171                 :            : 
    1172                 :    2487980 :   switch (TREE_CODE (chrec))
    1173                 :            :     {
    1174                 :    2337240 :     case POLYNOMIAL_CHREC:
    1175                 :    2337240 :       if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
    1176                 :            :         {
    1177                 :    2305510 :           if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
    1178                 :            :             return true;
    1179                 :            :           else
    1180                 :            :             {
    1181                 :        248 :               if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
    1182                 :        248 :                   && CHREC_VARIABLE (CHREC_RIGHT (chrec))
    1183                 :        248 :                      != CHREC_VARIABLE (chrec)
    1184                 :        248 :                   && evolution_function_is_affine_multivariate_p
    1185                 :          0 :                   (CHREC_RIGHT (chrec), loopnum))
    1186                 :            :                 return true;
    1187                 :            :               else
    1188                 :        248 :                 return false;
    1189                 :            :             }
    1190                 :            :         }
    1191                 :            :       else
    1192                 :            :         {
    1193                 :      31736 :           if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
    1194                 :      31736 :               && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
    1195                 :      31726 :               && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
    1196                 :      63462 :               && evolution_function_is_affine_multivariate_p
    1197                 :      31726 :               (CHREC_LEFT (chrec), loopnum))
    1198                 :            :             return true;
    1199                 :            :           else
    1200                 :         10 :             return false;
    1201                 :            :         }
    1202                 :            : 
    1203                 :            :     default:
    1204                 :            :       return false;
    1205                 :            :     }
    1206                 :            : }
    1207                 :            : 
    1208                 :            : /* Determine whether the given tree is a function in zero or one
    1209                 :            :    variables with respect to loop specified by LOOPNUM.  Note only positive
    1210                 :            :    LOOPNUM stands for a real loop.  */
    1211                 :            : 
    1212                 :            : bool
    1213                 :    1144360 : evolution_function_is_univariate_p (const_tree chrec, int loopnum)
    1214                 :            : {
    1215                 :    1144360 :   if (chrec == NULL_TREE)
    1216                 :            :     return true;
    1217                 :            : 
    1218                 :    1144360 :   tree sub_chrec;
    1219                 :    1144360 :   switch (TREE_CODE (chrec))
    1220                 :            :     {
    1221                 :    1144360 :     case POLYNOMIAL_CHREC:
    1222                 :    1144360 :       switch (TREE_CODE (CHREC_LEFT (chrec)))
    1223                 :            :         {
    1224                 :       9599 :         case POLYNOMIAL_CHREC:
    1225                 :       9599 :           sub_chrec = CHREC_LEFT (chrec);
    1226                 :       9599 :           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
    1227                 :       9599 :               && (loopnum <= 0
    1228                 :       2308 :                   || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
    1229                 :          5 :                   || flow_loop_nested_p (get_loop (cfun, loopnum),
    1230                 :          5 :                                          get_chrec_loop (sub_chrec))))
    1231                 :       9598 :             return false;
    1232                 :          1 :           if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
    1233                 :            :             return false;
    1234                 :            :           break;
    1235                 :            : 
    1236                 :    1134760 :         default:
    1237                 :    1134760 :           if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL))
    1238                 :            :             return false;
    1239                 :            :           break;
    1240                 :            :         }
    1241                 :            : 
    1242                 :    1134760 :       switch (TREE_CODE (CHREC_RIGHT (chrec)))
    1243                 :            :         {
    1244                 :          0 :         case POLYNOMIAL_CHREC:
    1245                 :          0 :           sub_chrec = CHREC_RIGHT (chrec);
    1246                 :          0 :           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
    1247                 :          0 :               && (loopnum <= 0
    1248                 :          0 :                   || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
    1249                 :          0 :                   || flow_loop_nested_p (get_loop (cfun, loopnum),
    1250                 :          0 :                                          get_chrec_loop (sub_chrec))))
    1251                 :          0 :             return false;
    1252                 :          0 :           if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
    1253                 :          0 :             return false;
    1254                 :            :           break;
    1255                 :            : 
    1256                 :    1134760 :         default:
    1257                 :    1134760 :           if (tree_contains_chrecs (CHREC_RIGHT (chrec), NULL))
    1258                 :          0 :             return false;
    1259                 :            :           break;
    1260                 :            :         }
    1261                 :            :       return true;
    1262                 :            : 
    1263                 :            :     default:
    1264                 :            :       return true;
    1265                 :            :     }
    1266                 :            : }
    1267                 :            : 
    1268                 :            : /* Returns the number of variables of CHREC.  Example: the call
    1269                 :            :    nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.  */
    1270                 :            : 
    1271                 :            : unsigned
    1272                 :    1024850 : nb_vars_in_chrec (tree chrec)
    1273                 :            : {
    1274                 :    2049710 :   if (chrec == NULL_TREE)
    1275                 :            :     return 0;
    1276                 :            : 
    1277                 :    2049710 :   switch (TREE_CODE (chrec))
    1278                 :            :     {
    1279                 :    1024850 :     case POLYNOMIAL_CHREC:
    1280                 :    1024850 :       return 1 + nb_vars_in_chrec
    1281                 :    1024850 :         (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
    1282                 :            : 
    1283                 :            :     default:
    1284                 :            :       return 0;
    1285                 :            :     }
    1286                 :            : }
    1287                 :            : 
    1288                 :            : /* Converts BASE and STEP of affine scev to TYPE.  LOOP is the loop whose iv
    1289                 :            :    the scev corresponds to.  AT_STMT is the statement at that the scev is
    1290                 :            :    evaluated.  USE_OVERFLOW_SEMANTICS is true if this function should assume
    1291                 :            :    that the rules for overflow of the given language apply (e.g., that signed
    1292                 :            :    arithmetics in C does not overflow) -- i.e., to use them to avoid
    1293                 :            :    unnecessary tests, but also to enforce that the result follows them.
    1294                 :            :    FROM is the source variable converted if it's not NULL.  Returns true if
    1295                 :            :    the conversion succeeded, false otherwise.  */
    1296                 :            : 
    1297                 :            : bool
    1298                 :    3791450 : convert_affine_scev (class loop *loop, tree type,
    1299                 :            :                      tree *base, tree *step, gimple *at_stmt,
    1300                 :            :                      bool use_overflow_semantics, tree from)
    1301                 :            : {
    1302                 :    3791450 :   tree ct = TREE_TYPE (*step);
    1303                 :    3791450 :   bool enforce_overflow_semantics;
    1304                 :    3791450 :   bool must_check_src_overflow, must_check_rslt_overflow;
    1305                 :    3791450 :   tree new_base, new_step;
    1306                 :    3791450 :   tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
    1307                 :            : 
    1308                 :            :   /* In general,
    1309                 :            :      (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
    1310                 :            :      but we must check some assumptions.
    1311                 :            : 
    1312                 :            :      1) If [BASE, +, STEP] wraps, the equation is not valid when precision
    1313                 :            :         of CT is smaller than the precision of TYPE.  For example, when we
    1314                 :            :         cast unsigned char [254, +, 1] to unsigned, the values on left side
    1315                 :            :         are 254, 255, 0, 1, ..., but those on the right side are
    1316                 :            :         254, 255, 256, 257, ...
    1317                 :            :      2) In case that we must also preserve the fact that signed ivs do not
    1318                 :            :         overflow, we must additionally check that the new iv does not wrap.
    1319                 :            :         For example, unsigned char [125, +, 1] casted to signed char could
    1320                 :            :         become a wrapping variable with values 125, 126, 127, -128, -127, ...,
    1321                 :            :         which would confuse optimizers that assume that this does not
    1322                 :            :         happen.  */
    1323                 :    3791450 :   must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
    1324                 :            : 
    1325                 :    8908860 :   enforce_overflow_semantics = (use_overflow_semantics
    1326                 :    3791450 :                                 && nowrap_type_p (type));
    1327                 :    1642870 :   if (enforce_overflow_semantics)
    1328                 :            :     {
    1329                 :            :       /* We can avoid checking whether the result overflows in the following
    1330                 :            :          cases:
    1331                 :            : 
    1332                 :            :          -- must_check_src_overflow is true, and the range of TYPE is superset
    1333                 :            :             of the range of CT -- i.e., in all cases except if CT signed and
    1334                 :            :             TYPE unsigned.
    1335                 :            :          -- both CT and TYPE have the same precision and signedness, and we
    1336                 :            :             verify instead that the source does not overflow (this may be
    1337                 :            :             easier than verifying it for the result, as we may use the
    1338                 :            :             information about the semantics of overflow in CT).  */
    1339                 :    1642870 :       if (must_check_src_overflow)
    1340                 :            :         {
    1341                 :     288801 :           if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
    1342                 :            :             must_check_rslt_overflow = true;
    1343                 :            :           else
    1344                 :            :             must_check_rslt_overflow = false;
    1345                 :            :         }
    1346                 :    1354060 :       else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
    1347                 :    1354060 :                && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
    1348                 :            :         {
    1349                 :            :           must_check_rslt_overflow = false;
    1350                 :            :           must_check_src_overflow = true;
    1351                 :            :         }
    1352                 :            :       else
    1353                 :            :         must_check_rslt_overflow = true;
    1354                 :            :     }
    1355                 :            :   else
    1356                 :            :     must_check_rslt_overflow = false;
    1357                 :            : 
    1358                 :    3474540 :   if (must_check_src_overflow
    1359                 :    3791450 :       && scev_probably_wraps_p (from, *base, *step, at_stmt, loop,
    1360                 :            :                                 use_overflow_semantics))
    1361                 :            :     return false;
    1362                 :            : 
    1363                 :    3350200 :   new_base = chrec_convert (type, *base, at_stmt, use_overflow_semantics);
    1364                 :            :   /* The step must be sign extended, regardless of the signedness
    1365                 :            :      of CT and TYPE.  This only needs to be handled specially when
    1366                 :            :      CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
    1367                 :            :      (with values 100, 99, 98, ...) from becoming signed or unsigned
    1368                 :            :      [100, +, 255] with values 100, 355, ...; the sign-extension is
    1369                 :            :      performed by default when CT is signed.  */
    1370                 :    3350200 :   new_step = *step;
    1371                 :    3350200 :   if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
    1372                 :            :     {
    1373                 :      37970 :       tree signed_ct = build_nonstandard_integer_type (TYPE_PRECISION (ct), 0);
    1374                 :      37970 :       new_step = chrec_convert (signed_ct, new_step, at_stmt,
    1375                 :            :                                 use_overflow_semantics);
    1376                 :            :     }
    1377                 :    3350200 :   new_step = chrec_convert (step_type, new_step, at_stmt,
    1378                 :            :                             use_overflow_semantics);
    1379                 :            : 
    1380                 :    6700400 :   if (automatically_generated_chrec_p (new_base)
    1381                 :    7141650 :       || automatically_generated_chrec_p (new_step))
    1382                 :            :     return false;
    1383                 :            : 
    1384                 :    3350200 :   if (must_check_rslt_overflow
    1385                 :            :       /* Note that in this case we cannot use the fact that signed variables
    1386                 :            :          do not overflow, as this is what we are verifying for the new iv.  */
    1387                 :    3350200 :       && scev_probably_wraps_p (NULL_TREE, new_base, new_step,
    1388                 :            :                                 at_stmt, loop, false))
    1389                 :            :     return false;
    1390                 :            : 
    1391                 :    2583180 :   *base = new_base;
    1392                 :    2583180 :   *step = new_step;
    1393                 :    2583180 :   return true;
    1394                 :            : }
    1395                 :            : 
    1396                 :            : 
    1397                 :            : /* Convert CHREC for the right hand side of a CHREC.
    1398                 :            :    The increment for a pointer type is always sizetype.  */
    1399                 :            : 
    1400                 :            : tree
    1401                 :   21611700 : chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt)
    1402                 :            : {
    1403                 :   21611700 :   if (POINTER_TYPE_P (type))
    1404                 :    4067240 :     type = sizetype;
    1405                 :            : 
    1406                 :   21611700 :   return chrec_convert (type, chrec, at_stmt);
    1407                 :            : }
    1408                 :            : 
    1409                 :            : /* Convert CHREC to TYPE.  When the analyzer knows the context in
    1410                 :            :    which the CHREC is built, it sets AT_STMT to the statement that
    1411                 :            :    contains the definition of the analyzed variable, otherwise the
    1412                 :            :    conversion is less accurate: the information is used for
    1413                 :            :    determining a more accurate estimation of the number of iterations.
    1414                 :            :    By default AT_STMT could be safely set to NULL_TREE.
    1415                 :            : 
    1416                 :            :    USE_OVERFLOW_SEMANTICS is true if this function should assume that
    1417                 :            :    the rules for overflow of the given language apply (e.g., that signed
    1418                 :            :    arithmetics in C does not overflow) -- i.e., to use them to avoid
    1419                 :            :    unnecessary tests, but also to enforce that the result follows them.
    1420                 :            : 
    1421                 :            :    FROM is the source variable converted if it's not NULL.  */
    1422                 :            : 
    1423                 :            : static tree
    1424                 :   93859000 : chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
    1425                 :            :                  bool use_overflow_semantics, tree from)
    1426                 :            : {
    1427                 :   93859000 :   tree ct, res;
    1428                 :   93859000 :   tree base, step;
    1429                 :   93859000 :   class loop *loop;
    1430                 :            : 
    1431                 :   93859000 :   if (automatically_generated_chrec_p (chrec))
    1432                 :            :     return chrec;
    1433                 :            : 
    1434                 :   93309200 :   ct = chrec_type (chrec);
    1435                 :   93309200 :   if (useless_type_conversion_p (type, ct))
    1436                 :            :     return chrec;
    1437                 :            : 
    1438                 :   24096700 :   if (!evolution_function_is_affine_p (chrec))
    1439                 :   21253400 :     goto keep_cast;
    1440                 :            : 
    1441                 :    2843240 :   loop = get_chrec_loop (chrec);
    1442                 :    2843240 :   base = CHREC_LEFT (chrec);
    1443                 :    2843240 :   step = CHREC_RIGHT (chrec);
    1444                 :            : 
    1445                 :    2843240 :   if (convert_affine_scev (loop, type, &base, &step, at_stmt,
    1446                 :            :                            use_overflow_semantics, from))
    1447                 :    2071840 :     return build_polynomial_chrec (loop->num, base, step);
    1448                 :            : 
    1449                 :            :   /* If we cannot propagate the cast inside the chrec, just keep the cast.  */
    1450                 :     771405 : keep_cast:
    1451                 :            :   /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
    1452                 :            :      may be more expensive.  We do want to perform this optimization here
    1453                 :            :      though for canonicalization reasons.  */
    1454                 :   22024800 :   if (use_overflow_semantics
    1455                 :   21694800 :       && (TREE_CODE (chrec) == PLUS_EXPR
    1456                 :   21694800 :           || TREE_CODE (chrec) == MINUS_EXPR)
    1457                 :    2249190 :       && TREE_CODE (type) == INTEGER_TYPE
    1458                 :    2212330 :       && TREE_CODE (ct) == INTEGER_TYPE
    1459                 :    2212220 :       && TYPE_PRECISION (type) > TYPE_PRECISION (ct)
    1460                 :   22105800 :       && TYPE_OVERFLOW_UNDEFINED (ct))
    1461                 :      42362 :     res = fold_build2 (TREE_CODE (chrec), type,
    1462                 :            :                        fold_convert (type, TREE_OPERAND (chrec, 0)),
    1463                 :            :                        fold_convert (type, TREE_OPERAND (chrec, 1)));
    1464                 :            :   /* Similar perform the trick that (signed char)((int)x + 2) can be
    1465                 :            :      narrowed to (signed char)((unsigned char)x + 2).  */
    1466                 :   21982500 :   else if (use_overflow_semantics
    1467                 :   21652400 :            && TREE_CODE (chrec) == POLYNOMIAL_CHREC
    1468                 :     825723 :            && TREE_CODE (ct) == INTEGER_TYPE
    1469                 :     808279 :            && TREE_CODE (type) == INTEGER_TYPE
    1470                 :     705363 :            && TYPE_OVERFLOW_UNDEFINED (type)
    1471                 :   22645100 :            && TYPE_PRECISION (type) < TYPE_PRECISION (ct))
    1472                 :            :     {
    1473                 :      23097 :       tree utype = unsigned_type_for (type);
    1474                 :      69291 :       res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
    1475                 :      23097 :                                     fold_convert (utype,
    1476                 :            :                                                   CHREC_LEFT (chrec)),
    1477                 :      23097 :                                     fold_convert (utype,
    1478                 :            :                                                   CHREC_RIGHT (chrec)));
    1479                 :      23097 :       res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from);
    1480                 :            :     }
    1481                 :            :   else
    1482                 :   21959400 :     res = fold_convert (type, chrec);
    1483                 :            : 
    1484                 :            :   /* Don't propagate overflows.  */
    1485                 :   22024800 :   if (CONSTANT_CLASS_P (res))
    1486                 :    5915790 :     TREE_OVERFLOW (res) = 0;
    1487                 :            : 
    1488                 :            :   /* But reject constants that don't fit in their type after conversion.
    1489                 :            :      This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
    1490                 :            :      natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
    1491                 :            :      and can cause problems later when computing niters of loops.  Note
    1492                 :            :      that we don't do the check before converting because we don't want
    1493                 :            :      to reject conversions of negative chrecs to unsigned types.  */
    1494                 :   22024800 :   if (TREE_CODE (res) == INTEGER_CST
    1495                 :    5915780 :       && TREE_CODE (type) == INTEGER_TYPE
    1496                 :    5469630 :       && !int_fits_type_p (res, type))
    1497                 :          0 :     res = chrec_dont_know;
    1498                 :            : 
    1499                 :            :   return res;
    1500                 :            : }
    1501                 :            : 
    1502                 :            : /* Convert CHREC to TYPE.  When the analyzer knows the context in
    1503                 :            :    which the CHREC is built, it sets AT_STMT to the statement that
    1504                 :            :    contains the definition of the analyzed variable, otherwise the
    1505                 :            :    conversion is less accurate: the information is used for
    1506                 :            :    determining a more accurate estimation of the number of iterations.
    1507                 :            :    By default AT_STMT could be safely set to NULL_TREE.
    1508                 :            : 
    1509                 :            :    The following rule is always true: TREE_TYPE (chrec) ==
    1510                 :            :    TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
    1511                 :            :    An example of what could happen when adding two chrecs and the type
    1512                 :            :    of the CHREC_RIGHT is different than CHREC_LEFT is:
    1513                 :            : 
    1514                 :            :    {(uint) 0, +, (uchar) 10} +
    1515                 :            :    {(uint) 0, +, (uchar) 250}
    1516                 :            : 
    1517                 :            :    that would produce a wrong result if CHREC_RIGHT is not (uint):
    1518                 :            : 
    1519                 :            :    {(uint) 0, +, (uchar) 4}
    1520                 :            : 
    1521                 :            :    instead of
    1522                 :            : 
    1523                 :            :    {(uint) 0, +, (uint) 260}
    1524                 :            : 
    1525                 :            :    USE_OVERFLOW_SEMANTICS is true if this function should assume that
    1526                 :            :    the rules for overflow of the given language apply (e.g., that signed
    1527                 :            :    arithmetics in C does not overflow) -- i.e., to use them to avoid
    1528                 :            :    unnecessary tests, but also to enforce that the result follows them.
    1529                 :            : 
    1530                 :            :    FROM is the source variable converted if it's not NULL.  */
    1531                 :            : 
    1532                 :            : tree
    1533                 :   93835900 : chrec_convert (tree type, tree chrec, gimple *at_stmt,
    1534                 :            :                bool use_overflow_semantics, tree from)
    1535                 :            : {
    1536                 :   93835900 :   return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from);
    1537                 :            : }
    1538                 :            : 
    1539                 :            : /* Convert CHREC to TYPE, without regard to signed overflows.  Returns the new
    1540                 :            :    chrec if something else than what chrec_convert would do happens, NULL_TREE
    1541                 :            :    otherwise.  This function set TRUE to variable pointed by FOLD_CONVERSIONS
    1542                 :            :    if the result chrec may overflow.  */
    1543                 :            : 
    1544                 :            : tree
    1545                 :    7078480 : chrec_convert_aggressive (tree type, tree chrec, bool *fold_conversions)
    1546                 :            : {
    1547                 :    7078480 :   tree inner_type, left, right, lc, rc, rtype;
    1548                 :            : 
    1549                 :    7078480 :   gcc_assert (fold_conversions != NULL);
    1550                 :            : 
    1551                 :    7078480 :   if (automatically_generated_chrec_p (chrec)
    1552                 :    7078480 :       || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
    1553                 :            :     return NULL_TREE;
    1554                 :            : 
    1555                 :     533632 :   inner_type = TREE_TYPE (chrec);
    1556                 :     533632 :   if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
    1557                 :            :     return NULL_TREE;
    1558                 :            : 
    1559                 :     506996 :   if (useless_type_conversion_p (type, inner_type))
    1560                 :            :     return NULL_TREE;
    1561                 :            : 
    1562                 :     437885 :   if (!*fold_conversions && evolution_function_is_affine_p (chrec))
    1563                 :            :     {
    1564                 :     437106 :       tree base, step;
    1565                 :     437106 :       class loop *loop;
    1566                 :            : 
    1567                 :     437106 :       loop = get_chrec_loop (chrec);
    1568                 :     437106 :       base = CHREC_LEFT (chrec);
    1569                 :     437106 :       step = CHREC_RIGHT (chrec);
    1570                 :     437106 :       if (convert_affine_scev (loop, type, &base, &step, NULL, true))
    1571                 :       1314 :         return build_polynomial_chrec (loop->num, base, step);
    1572                 :            :     }
    1573                 :     436571 :   rtype = POINTER_TYPE_P (type) ? sizetype : type;
    1574                 :            : 
    1575                 :     436571 :   left = CHREC_LEFT (chrec);
    1576                 :     436571 :   right = CHREC_RIGHT (chrec);
    1577                 :     436571 :   lc = chrec_convert_aggressive (type, left, fold_conversions);
    1578                 :     436571 :   if (!lc)
    1579                 :     436571 :     lc = chrec_convert (type, left, NULL);
    1580                 :     436571 :   rc = chrec_convert_aggressive (rtype, right, fold_conversions);
    1581                 :     436571 :   if (!rc)
    1582                 :     435875 :     rc = chrec_convert (rtype, right, NULL);
    1583                 :            : 
    1584                 :     436571 :   *fold_conversions = true;
    1585                 :            : 
    1586                 :     436571 :   return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
    1587                 :            : }
    1588                 :            : 
    1589                 :            : /* Returns true when CHREC0 == CHREC1.  */
    1590                 :            : 
    1591                 :            : bool
    1592                 :    5218680 : eq_evolutions_p (const_tree chrec0, const_tree chrec1)
    1593                 :            : {
    1594                 :    5269810 :   if (chrec0 == NULL_TREE
    1595                 :    5269810 :       || chrec1 == NULL_TREE
    1596                 :    5269810 :       || TREE_CODE (chrec0) != TREE_CODE (chrec1))
    1597                 :            :     return false;
    1598                 :            : 
    1599                 :    4862420 :   if (chrec0 == chrec1)
    1600                 :            :     return true;
    1601                 :            : 
    1602                 :    3422320 :   if (! types_compatible_p (TREE_TYPE (chrec0), TREE_TYPE (chrec1)))
    1603                 :            :     return false;
    1604                 :            : 
    1605                 :    3422020 :   switch (TREE_CODE (chrec0))
    1606                 :            :     {
    1607                 :    1391700 :     case POLYNOMIAL_CHREC:
    1608                 :    1391700 :       return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
    1609                 :    1391340 :               && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
    1610                 :    1675100 :               && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
    1611                 :            : 
    1612                 :     137737 :     case PLUS_EXPR:
    1613                 :     137737 :     case MULT_EXPR:
    1614                 :     137737 :     case MINUS_EXPR:
    1615                 :     137737 :     case POINTER_PLUS_EXPR:
    1616                 :     137737 :       return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
    1617                 :     137737 :                               TREE_OPERAND (chrec1, 0))
    1618                 :     237788 :           && eq_evolutions_p (TREE_OPERAND (chrec0, 1),
    1619                 :     100051 :                               TREE_OPERAND (chrec1, 1));
    1620                 :            : 
    1621                 :      51126 :     CASE_CONVERT:
    1622                 :      51126 :       return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
    1623                 :     102252 :                               TREE_OPERAND (chrec1, 0));
    1624                 :            : 
    1625                 :    1841460 :     default:
    1626                 :    1841460 :       return operand_equal_p (chrec0, chrec1, 0);
    1627                 :            :     }
    1628                 :            : }
    1629                 :            : 
    1630                 :            : /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
    1631                 :            :    EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
    1632                 :            :    which of these cases happens.  */
    1633                 :            : 
    1634                 :            : enum ev_direction
    1635                 :    1354700 : scev_direction (const_tree chrec)
    1636                 :            : {
    1637                 :    1354700 :   const_tree step;
    1638                 :            : 
    1639                 :    1354700 :   if (!evolution_function_is_affine_p (chrec))
    1640                 :            :     return EV_DIR_UNKNOWN;
    1641                 :            : 
    1642                 :    1354700 :   step = CHREC_RIGHT (chrec);
    1643                 :    1354700 :   if (TREE_CODE (step) != INTEGER_CST)
    1644                 :            :     return EV_DIR_UNKNOWN;
    1645                 :            : 
    1646                 :    1354580 :   if (tree_int_cst_sign_bit (step))
    1647                 :            :     return EV_DIR_DECREASES;
    1648                 :            :   else
    1649                 :    1257280 :     return EV_DIR_GROWS;
    1650                 :            : }
    1651                 :            : 
    1652                 :            : /* Iterates over all the components of SCEV, and calls CBCK.  */
    1653                 :            : 
    1654                 :            : void
    1655                 :          0 : for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
    1656                 :            : {
    1657                 :          0 :   switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
    1658                 :            :     {
    1659                 :          0 :     case 3:
    1660                 :          0 :       for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
    1661                 :            :       /* FALLTHRU */
    1662                 :            : 
    1663                 :          0 :     case 2:
    1664                 :          0 :       for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
    1665                 :            :       /* FALLTHRU */
    1666                 :            : 
    1667                 :          0 :     case 1:
    1668                 :          0 :       for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
    1669                 :            :       /* FALLTHRU */
    1670                 :            : 
    1671                 :          0 :     default:
    1672                 :          0 :       cbck (scev, data);
    1673                 :          0 :       break;
    1674                 :            :     }
    1675                 :          0 : }
    1676                 :            : 
    1677                 :            : /* Returns true when the operation can be part of a linear
    1678                 :            :    expression.  */
    1679                 :            : 
    1680                 :            : static inline bool
    1681                 :      33171 : operator_is_linear (tree scev)
    1682                 :            : {
    1683                 :      33171 :   switch (TREE_CODE (scev))
    1684                 :            :     {
    1685                 :            :     case INTEGER_CST:
    1686                 :            :     case POLYNOMIAL_CHREC:
    1687                 :            :     case PLUS_EXPR:
    1688                 :            :     case POINTER_PLUS_EXPR:
    1689                 :            :     case MULT_EXPR:
    1690                 :            :     case MINUS_EXPR:
    1691                 :            :     case NEGATE_EXPR:
    1692                 :            :     case SSA_NAME:
    1693                 :            :     case NON_LVALUE_EXPR:
    1694                 :            :     case BIT_NOT_EXPR:
    1695                 :            :     CASE_CONVERT:
    1696                 :            :       return true;
    1697                 :            : 
    1698                 :         29 :     default:
    1699                 :         29 :       return false;
    1700                 :            :     }
    1701                 :            : }
    1702                 :            : 
    1703                 :            : /* Return true when SCEV is a linear expression.  Linear expressions
    1704                 :            :    can contain additions, substractions and multiplications.
    1705                 :            :    Multiplications are restricted to constant scaling: "cst * x".  */
    1706                 :            : 
    1707                 :            : bool
    1708                 :      73559 : scev_is_linear_expression (tree scev)
    1709                 :            : {
    1710                 :     151212 :   if (evolution_function_is_constant_p (scev))
    1711                 :            :     return true;
    1712                 :            : 
    1713                 :      33171 :   if (scev == NULL
    1714                 :      33171 :       || !operator_is_linear (scev))
    1715                 :            :     return false;
    1716                 :            : 
    1717                 :      33142 :   if (TREE_CODE (scev) == MULT_EXPR)
    1718                 :        604 :     return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
    1719                 :          0 :              && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
    1720                 :            : 
    1721                 :      32538 :   if (TREE_CODE (scev) == POLYNOMIAL_CHREC
    1722                 :      32538 :       && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)))
    1723                 :            :     return false;
    1724                 :            : 
    1725                 :      32290 :   switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
    1726                 :            :     {
    1727                 :          0 :     case 3:
    1728                 :          0 :       return scev_is_linear_expression (TREE_OPERAND (scev, 0))
    1729                 :          0 :         && scev_is_linear_expression (TREE_OPERAND (scev, 1))
    1730                 :          0 :         && scev_is_linear_expression (TREE_OPERAND (scev, 2));
    1731                 :            : 
    1732                 :      23073 :     case 2:
    1733                 :      23073 :       return scev_is_linear_expression (TREE_OPERAND (scev, 0))
    1734                 :      23073 :         && scev_is_linear_expression (TREE_OPERAND (scev, 1));
    1735                 :            : 
    1736                 :       2047 :     case 1:
    1737                 :       2047 :       return scev_is_linear_expression (TREE_OPERAND (scev, 0));
    1738                 :            : 
    1739                 :            :     case 0:
    1740                 :            :       return true;
    1741                 :            : 
    1742                 :          0 :     default:
    1743                 :          0 :       return false;
    1744                 :            :     }
    1745                 :            : }
    1746                 :            : 
    1747                 :            : /* Determines whether the expression CHREC contains only interger consts
    1748                 :            :    in the right parts.  */
    1749                 :            : 
    1750                 :            : bool
    1751                 :       4499 : evolution_function_right_is_integer_cst (const_tree chrec)
    1752                 :            : {
    1753                 :       4499 :   if (chrec == NULL_TREE)
    1754                 :            :     return false;
    1755                 :            : 
    1756                 :       4499 :   switch (TREE_CODE (chrec))
    1757                 :            :     {
    1758                 :            :     case INTEGER_CST:
    1759                 :            :       return true;
    1760                 :            : 
    1761                 :       4499 :     case POLYNOMIAL_CHREC:
    1762                 :       4499 :       return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
    1763                 :       4499 :         && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
    1764                 :        578 :             || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
    1765                 :            : 
    1766                 :          0 :     CASE_CONVERT:
    1767                 :          0 :       return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
    1768                 :            : 
    1769                 :          0 :     default:
    1770                 :          0 :       return false;
    1771                 :            :     }
    1772                 :            : }

Generated by: LCOV version 1.0

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