LCOV - code coverage report
Current view: top level - gcc - tree-chrec.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 56 67 83.6 %
Date: 2020-04-04 11:58:09 Functions: 5 6 83.3 %
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                 :            : #ifndef GCC_TREE_CHREC_H
      22                 :            : #define GCC_TREE_CHREC_H
      23                 :            : 
      24                 :            : /* The following trees are unique elements.  Thus the comparison of another
      25                 :            :    element to these elements should be done on the pointer to these trees,
      26                 :            :    and not on their value.
      27                 :            : 
      28                 :            :    extern tree chrec_not_analyzed_yet;
      29                 :            :    extern tree chrec_dont_know;
      30                 :            :    extern tree chrec_known;
      31                 :            : 
      32                 :            :    chrec_not_analyzed_yet is NULL_TREE and the others are defined
      33                 :            :    in global_trees[].  */
      34                 :            : 
      35                 :            : /* After having added an automatically generated element, please
      36                 :            :    include it in the following function.  */
      37                 :            : 
      38                 :            : static inline bool
      39                 :  827958538 : automatically_generated_chrec_p (const_tree chrec)
      40                 :            : {
      41                 :  827958538 :   return (chrec == chrec_dont_know
      42                 :  772194538 :           || chrec == chrec_known);
      43                 :            : }
      44                 :            : 
      45                 :            : /* The tree nodes aka. CHRECs.  */
      46                 :            : 
      47                 :            : static inline bool
      48                 :  234398188 : tree_is_chrec (const_tree expr)
      49                 :            : {
      50                 :  234398188 :   if (TREE_CODE (expr) == POLYNOMIAL_CHREC
      51                 :  457015795 :       || automatically_generated_chrec_p (expr))
      52                 :          0 :     return true;
      53                 :            :   else
      54                 :            :     return false;
      55                 :            : }
      56                 :            : 
      57                 :            : 
      58                 :            : enum ev_direction {EV_DIR_GROWS, EV_DIR_DECREASES, EV_DIR_UNKNOWN};
      59                 :            : enum ev_direction scev_direction (const_tree);
      60                 :            : 
      61                 :            : /* Chrec folding functions.  */
      62                 :            : extern tree chrec_fold_plus (tree, tree, tree);
      63                 :            : extern tree chrec_fold_minus (tree, tree, tree);
      64                 :            : extern tree chrec_fold_multiply (tree, tree, tree);
      65                 :            : extern tree chrec_convert (tree, tree, gimple *, bool = true, tree = NULL);
      66                 :            : extern tree chrec_convert_rhs (tree, tree, gimple *);
      67                 :            : extern tree chrec_convert_aggressive (tree, tree, bool *);
      68                 :            : 
      69                 :            : /* Operations.  */
      70                 :            : extern tree chrec_apply (unsigned, tree, tree);
      71                 :            : extern tree chrec_apply_map (tree, vec<tree> );
      72                 :            : extern tree chrec_replace_initial_condition (tree, tree);
      73                 :            : extern tree initial_condition (tree);
      74                 :            : extern tree initial_condition_in_loop_num (tree, unsigned);
      75                 :            : extern tree evolution_part_in_loop_num (tree, unsigned);
      76                 :            : extern tree hide_evolution_in_other_loops_than_loop (tree, unsigned);
      77                 :            : extern tree reset_evolution_in_loop (unsigned, tree, tree);
      78                 :            : extern tree chrec_merge (tree, tree);
      79                 :            : extern void for_each_scev_op (tree *, bool (*) (tree *, void *), void *);
      80                 :            : extern bool convert_affine_scev (class loop *, tree, tree *, tree *, gimple *,
      81                 :            :                                  bool, tree = NULL);
      82                 :            : 
      83                 :            : /* Observers.  */
      84                 :            : extern bool eq_evolutions_p (const_tree, const_tree);
      85                 :            : extern bool is_multivariate_chrec (const_tree);
      86                 :            : extern bool chrec_contains_symbols (const_tree, class loop * = NULL);
      87                 :            : extern bool chrec_contains_symbols_defined_in_loop (const_tree, unsigned);
      88                 :            : extern bool chrec_contains_undetermined (const_tree);
      89                 :            : extern bool tree_contains_chrecs (const_tree, int *);
      90                 :            : extern bool evolution_function_is_affine_multivariate_p (const_tree, int);
      91                 :            : extern bool evolution_function_is_univariate_p (const_tree, int = 0);
      92                 :            : extern unsigned nb_vars_in_chrec (tree);
      93                 :            : extern bool evolution_function_is_invariant_p (tree, int);
      94                 :            : extern bool scev_is_linear_expression (tree);
      95                 :            : extern bool evolution_function_right_is_integer_cst (const_tree);
      96                 :            : 
      97                 :            : /* Determines whether CHREC is equal to zero.  */
      98                 :            : 
      99                 :            : static inline bool
     100                 :   23122856 : chrec_zerop (const_tree chrec)
     101                 :            : {
     102                 :   10368193 :   if (chrec == NULL_TREE)
     103                 :            :     return false;
     104                 :            : 
     105                 :   23122856 :   if (TREE_CODE (chrec) == INTEGER_CST)
     106                 :   19183476 :     return integer_zerop (chrec);
     107                 :            : 
     108                 :            :   return false;
     109                 :            : }
     110                 :            : 
     111                 :            : /* Determines whether CHREC is a loop invariant with respect to LOOP_NUM.
     112                 :            :    Set the result in RES and return true when the property can be computed.  */
     113                 :            : 
     114                 :            : static inline bool
     115                 :   30319056 : no_evolution_in_loop_p (tree chrec, unsigned loop_num, bool *res)
     116                 :            : {
     117                 :   30319056 :   tree scev;
     118                 :            : 
     119                 :   30319056 :   if (chrec == chrec_not_analyzed_yet
     120                 :   30319056 :       || chrec == chrec_dont_know
     121                 :   59454412 :       || chrec_contains_symbols_defined_in_loop (chrec, loop_num))
     122                 :    2690840 :     return false;
     123                 :            : 
     124                 :   27628156 :   STRIP_NOPS (chrec);
     125                 :   27628156 :   scev = hide_evolution_in_other_loops_than_loop (chrec, loop_num);
     126                 :   27628156 :   *res = !tree_contains_chrecs (scev, NULL);
     127                 :   27628156 :   return true;
     128                 :            : }
     129                 :            : 
     130                 :            : /* Build a polynomial chain of recurrence.  */
     131                 :            : 
     132                 :            : static inline tree
     133                 :   23100256 : build_polynomial_chrec (unsigned loop_num,
     134                 :            :                         tree left,
     135                 :            :                         tree right)
     136                 :            : {
     137                 :   23100256 :   bool val;
     138                 :            : 
     139                 :   23100256 :   if (left == chrec_dont_know
     140                 :   23100156 :       || right == chrec_dont_know)
     141                 :            :     return chrec_dont_know;
     142                 :            : 
     143                 :   23099656 :   if (!no_evolution_in_loop_p (left, loop_num, &val)
     144                 :   23099656 :       || !val)
     145                 :      11278 :     return chrec_dont_know;
     146                 :            : 
     147                 :            :   /* Types of left and right sides of a chrec should be compatible, but
     148                 :            :      pointer CHRECs are special in that the evolution is of ptroff type.  */
     149                 :   23088356 :   if (POINTER_TYPE_P (TREE_TYPE (left)))
     150                 :    5005360 :     gcc_checking_assert (ptrofftype_p (TREE_TYPE (right)));
     151                 :            :   else
     152                 :            :     {
     153                 :            :       /* Pointer types should occur only on the left hand side, i.e. in
     154                 :            :          the base of the chrec, and not in the step.  */
     155                 :   18083026 :       gcc_checking_assert (!POINTER_TYPE_P (TREE_TYPE (right))
     156                 :            :                            && types_compatible_p (TREE_TYPE (left),
     157                 :            :                                                   TREE_TYPE (right)));
     158                 :            :     }
     159                 :            : 
     160                 :   42252812 :   if (chrec_zerop (right))
     161                 :            :     return left;
     162                 :            : 
     163                 :   23087156 :   tree chrec = build2 (POLYNOMIAL_CHREC, TREE_TYPE (left), left, right);
     164                 :   23087156 :   CHREC_VARIABLE (chrec) = loop_num;
     165                 :   23087156 :   return chrec;
     166                 :            : }
     167                 :            : 
     168                 :            : /* Determines whether the expression CHREC is a constant.  */
     169                 :            : 
     170                 :            : static inline bool
     171                 :   23609840 : evolution_function_is_constant_p (const_tree chrec)
     172                 :            : {
     173                 :   23609840 :   if (chrec == NULL_TREE)
     174                 :            :     return false;
     175                 :            : 
     176                 :   23609840 :   return is_gimple_min_invariant (chrec);
     177                 :            : }
     178                 :            : 
     179                 :            : /* Determine whether CHREC is an affine evolution function in LOOPNUM.  */
     180                 :            : 
     181                 :            : static inline bool
     182                 :    1683930 : evolution_function_is_affine_in_loop (const_tree chrec, int loopnum)
     183                 :            : {
     184                 :    1683930 :   if (chrec == NULL_TREE)
     185                 :            :     return false;
     186                 :            : 
     187                 :    1683930 :   switch (TREE_CODE (chrec))
     188                 :            :     {
     189                 :    1681860 :     case POLYNOMIAL_CHREC:
     190                 :    1681860 :       if (evolution_function_is_invariant_p (CHREC_LEFT (chrec), loopnum)
     191                 :    3361410 :           && evolution_function_is_invariant_p (CHREC_RIGHT (chrec), loopnum))
     192                 :            :         return true;
     193                 :            :       else
     194                 :       2307 :         return false;
     195                 :            : 
     196                 :            :     default:
     197                 :            :       return false;
     198                 :            :     }
     199                 :            : }
     200                 :            : 
     201                 :            : /* Determine whether CHREC is an affine evolution function or not.  */
     202                 :            : 
     203                 :            : static inline bool
     204                 :   26340200 : evolution_function_is_affine_p (const_tree chrec)
     205                 :            : {
     206                 :   26340200 :   return chrec
     207                 :   26340200 :     && TREE_CODE (chrec) == POLYNOMIAL_CHREC
     208                 :    5119390 :     && evolution_function_is_invariant_p (CHREC_RIGHT (chrec),
     209                 :    5119390 :                                           CHREC_VARIABLE (chrec))
     210                 :   31403200 :     && (TREE_CODE (CHREC_RIGHT (chrec)) != POLYNOMIAL_CHREC
     211                 :         50 :         || evolution_function_is_affine_p (CHREC_RIGHT (chrec)));
     212                 :            : }
     213                 :            : 
     214                 :            : /* Determines whether EXPR does not contains chrec expressions.  */
     215                 :            : 
     216                 :            : static inline bool
     217                 :   17711518 : tree_does_not_contain_chrecs (const_tree expr)
     218                 :            : {
     219                 :   17711518 :   return !tree_contains_chrecs (expr, NULL);
     220                 :            : }
     221                 :            : 
     222                 :            : /* Returns the type of the chrec.  */
     223                 :            : 
     224                 :            : static inline tree
     225                 :  128174937 : chrec_type (const_tree chrec)
     226                 :            : {
     227                 :  128174937 :   if (automatically_generated_chrec_p (chrec))
     228                 :            :     return NULL_TREE;
     229                 :            : 
     230                 :  128174937 :   return TREE_TYPE (chrec);
     231                 :            : }
     232                 :            : 
     233                 :            : static inline tree
     234                 :          0 : chrec_fold_op (enum tree_code code, tree type, tree op0, tree op1)
     235                 :            : {
     236                 :          0 :   switch (code)
     237                 :            :     {
     238                 :          0 :     case PLUS_EXPR:
     239                 :          0 :       return chrec_fold_plus (type, op0, op1);
     240                 :            : 
     241                 :          0 :     case MINUS_EXPR:
     242                 :          0 :       return chrec_fold_minus (type, op0, op1);
     243                 :            : 
     244                 :          0 :     case MULT_EXPR:
     245                 :          0 :       return chrec_fold_multiply (type, op0, op1);
     246                 :            : 
     247                 :          0 :     default:
     248                 :          0 :       gcc_unreachable ();
     249                 :            :     }
     250                 :            : 
     251                 :            : }
     252                 :            : 
     253                 :            : #endif  /* GCC_TREE_CHREC_H  */

Generated by: LCOV version 1.0

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