LCOV - code coverage report
Current view: top level - gcc - tree-chrec.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 83.3 % 66 55
Test Date: 2026-11-14 16:39:50 Functions: 85.7 % 7 6
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Chains of recurrences.
       2              :    Copyright (C) 2003-2026 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              : inline bool
      39   1573031772 : automatically_generated_chrec_p (const_tree chrec)
      40              : {
      41   1573031772 :   return (chrec == chrec_dont_know
      42   1473562940 :           || chrec == chrec_known);
      43              : }
      44              : 
      45              : /* The tree nodes aka. CHRECs.  */
      46              : 
      47              : inline bool
      48    504955909 : tree_is_chrec (const_tree expr)
      49              : {
      50    504955909 :   if (TREE_CODE (expr) == POLYNOMIAL_CHREC
      51    998116001 :       || 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 *, tree * = nullptr,
      66              :                            bool = true, tree = NULL);
      67              : extern tree chrec_convert_rhs (tree, tree, gimple * = NULL, tree * = nullptr);
      68              : extern tree chrec_convert_aggressive (tree, tree, bool *);
      69              : 
      70              : /* Operations.  */
      71              : extern tree chrec_apply (unsigned, tree, tree);
      72              : extern tree chrec_apply_map (tree, vec<tree> );
      73              : extern tree chrec_replace_initial_condition (tree, tree);
      74              : extern tree initial_condition (tree);
      75              : extern tree initial_condition_in_loop_num (tree, unsigned);
      76              : extern tree evolution_part_in_loop_num (tree, unsigned);
      77              : extern tree hide_evolution_in_other_loops_than_loop (tree, unsigned);
      78              : extern tree reset_evolution_in_loop (unsigned, tree, tree);
      79              : extern tree chrec_merge (tree, tree);
      80              : extern void for_each_scev_op (tree *, bool (*) (tree *, void *), void *);
      81              : extern bool convert_affine_scev (class loop *, tree, tree *, tree *, gimple *,
      82              :                                  bool, tree = NULL, tree * = nullptr);
      83              : 
      84              : /* Observers.  */
      85              : extern bool eq_evolutions_p (const_tree, const_tree);
      86              : extern bool is_multivariate_chrec (const_tree);
      87              : extern bool chrec_contains_symbols (const_tree, class loop * = NULL);
      88              : extern bool chrec_contains_symbols_defined_in_loop (const_tree, unsigned);
      89              : extern bool chrec_contains_undetermined (const_tree);
      90              : extern bool tree_contains_chrecs (const_tree, int *);
      91              : extern bool evolution_function_is_affine_multivariate_p (const_tree, int);
      92              : extern bool evolution_function_is_univariate_p (const_tree, int = 0);
      93              : extern unsigned nb_vars_in_chrec (tree);
      94              : extern bool evolution_function_is_invariant_p (tree, int);
      95              : extern bool scev_is_linear_expression (tree);
      96              : extern bool evolution_function_right_is_integer_cst (const_tree);
      97              : 
      98              : /* Determines whether CHREC is equal to zero.  */
      99              : 
     100              : inline bool
     101     44225266 : chrec_zerop (const_tree chrec)
     102              : {
     103     44225266 :   if (chrec == NULL_TREE)
     104              :     return false;
     105              : 
     106     44225266 :   if (TREE_CODE (chrec) == INTEGER_CST)
     107     37962413 :     return integer_zerop (chrec);
     108              : 
     109              :   return false;
     110              : }
     111              : 
     112              : /* Determines whether CHREC is a loop invariant with respect to LOOP_NUM.
     113              :    Set the result in RES and return true when the property can be computed.  */
     114              : 
     115              : inline bool
     116     55641815 : no_evolution_in_loop_p (tree chrec, unsigned loop_num, bool *res)
     117              : {
     118     55641815 :   tree scev;
     119              : 
     120     55641815 :   if (chrec == chrec_not_analyzed_yet
     121     55641815 :       || chrec == chrec_dont_know
     122    107912178 :       || chrec_contains_symbols_defined_in_loop (chrec, loop_num))
     123              :     return false;
     124              : 
     125     48335241 :   STRIP_NOPS (chrec);
     126     48335241 :   scev = hide_evolution_in_other_loops_than_loop (chrec, loop_num);
     127     48335241 :   *res = !tree_contains_chrecs (scev, NULL);
     128     48335241 :   return true;
     129              : }
     130              : 
     131              : /* Build a polynomial chain of recurrence.  */
     132              : 
     133              : inline tree
     134     44140819 : build_polynomial_chrec (unsigned loop_num,
     135              :                         tree left,
     136              :                         tree right)
     137              : {
     138     44140819 :   bool val;
     139              : 
     140     44140819 :   if (left == chrec_dont_know
     141     44140367 :       || right == chrec_dont_know)
     142              :     return chrec_dont_know;
     143              : 
     144     44139764 :   if (!no_evolution_in_loop_p (left, loop_num, &val)
     145     44139764 :       || !val)
     146         1774 :     return chrec_dont_know;
     147              : 
     148              :   /* Types of left and right sides of a chrec should be compatible, but
     149              :      pointer CHRECs are special in that the evolution is of ptroff type.  */
     150     44137990 :   if (POINTER_TYPE_P (TREE_TYPE (left)))
     151      8952885 :     gcc_checking_assert (ptrofftype_p (TREE_TYPE (right)));
     152              :   else
     153              :     {
     154              :       /* Pointer types should occur only on the left hand side, i.e. in
     155              :          the base of the chrec, and not in the step.  */
     156     35185105 :       gcc_checking_assert (!POINTER_TYPE_P (TREE_TYPE (right))
     157              :                            && types_compatible_p (TREE_TYPE (left),
     158              :                                                   TREE_TYPE (right)));
     159              :     }
     160              : 
     161     44137990 :   if (chrec_zerop (right))
     162              :     return left;
     163              : 
     164     44137778 :   tree chrec = build2 (POLYNOMIAL_CHREC, TREE_TYPE (left), left, right);
     165     44137778 :   CHREC_VARIABLE (chrec) = loop_num;
     166     44137778 :   return chrec;
     167              : }
     168              : 
     169              : /* Determines whether the expression CHREC is a constant.  */
     170              : 
     171              : inline bool
     172     56628653 : evolution_function_is_constant_p (const_tree chrec)
     173              : {
     174     56628653 :   if (chrec == NULL_TREE)
     175              :     return false;
     176              : 
     177     56628653 :   return is_gimple_min_invariant (chrec);
     178              : }
     179              : 
     180              : /* Determine whether CHREC is an affine evolution function in LOOPNUM.  */
     181              : 
     182              : inline bool
     183      5139190 : evolution_function_is_affine_in_loop (const_tree chrec, int loopnum)
     184              : {
     185      5139190 :   if (chrec == NULL_TREE)
     186              :     return false;
     187              : 
     188      5139190 :   switch (TREE_CODE (chrec))
     189              :     {
     190      5136073 :     case POLYNOMIAL_CHREC:
     191      5136073 :       if (evolution_function_is_invariant_p (CHREC_LEFT (chrec), loopnum)
     192     10268576 :           && evolution_function_is_invariant_p (CHREC_RIGHT (chrec), loopnum))
     193              :         return true;
     194              :       else
     195         3570 :         return false;
     196              : 
     197              :     default:
     198              :       return false;
     199              :     }
     200              : }
     201              : 
     202              : /* Determine whether CHREC is an affine evolution function or not.  */
     203              : 
     204              : inline bool
     205     48683607 : evolution_function_is_affine_p (const_tree chrec)
     206              : {
     207     48683607 :   return chrec
     208     48683607 :     && TREE_CODE (chrec) == POLYNOMIAL_CHREC
     209     11235422 :     && evolution_function_is_invariant_p (CHREC_RIGHT (chrec),
     210     11235422 :                                           CHREC_VARIABLE (chrec))
     211     59869497 :     && (TREE_CODE (CHREC_RIGHT (chrec)) != POLYNOMIAL_CHREC
     212           63 :         || evolution_function_is_affine_p (CHREC_RIGHT (chrec)));
     213              : }
     214              : 
     215              : /* Determines whether EXPR does not contains chrec expressions.  */
     216              : 
     217              : inline bool
     218     38324347 : tree_does_not_contain_chrecs (const_tree expr)
     219              : {
     220     38324347 :   return !tree_contains_chrecs (expr, NULL);
     221              : }
     222              : 
     223              : /* Returns the type of the chrec.  */
     224              : 
     225              : inline tree
     226    211518121 : chrec_type (const_tree chrec)
     227              : {
     228    211518121 :   if (automatically_generated_chrec_p (chrec))
     229              :     return NULL_TREE;
     230              : 
     231    211518121 :   return TREE_TYPE (chrec);
     232              : }
     233              : 
     234              : inline tree
     235            0 : chrec_fold_op (enum tree_code code, tree type, tree op0, tree op1)
     236              : {
     237            0 :   switch (code)
     238              :     {
     239            0 :     case PLUS_EXPR:
     240            0 :       return chrec_fold_plus (type, op0, op1);
     241              : 
     242            0 :     case MINUS_EXPR:
     243            0 :       return chrec_fold_minus (type, op0, op1);
     244              : 
     245            0 :     case MULT_EXPR:
     246            0 :       return chrec_fold_multiply (type, op0, op1);
     247              : 
     248            0 :     default:
     249            0 :       gcc_unreachable ();
     250              :     }
     251              : 
     252              : }
     253              : 
     254              : #endif  /* GCC_TREE_CHREC_H  */
        

Generated by: LCOV version 2.5.0-beta

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