1  /* Operations with affine combinations of trees.
       2     Copyright (C) 2005-2023 Free Software Foundation, Inc.
       3  
       4  This file is part of GCC.
       5  
       6  GCC is free software; you can redistribute it and/or modify it
       7  under the terms of the GNU General Public License as published by the
       8  Free Software Foundation; either version 3, or (at your option) any
       9  later version.
      10  
      11  GCC is distributed in the hope that it will be useful, but WITHOUT
      12  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13  FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14  for more details.
      15  
      16  You should have received a copy of the GNU General Public License
      17  along with GCC; see the file COPYING3.  If not see
      18  <http://www.gnu.org/licenses/>.  */
      19  
      20  /* Affine combination of trees.  We keep track of at most MAX_AFF_ELTS elements
      21     to make things simpler; this is sufficient in most cases.  */
      22  
      23  #ifndef GCC_TREE_AFFINE_H
      24  #define GCC_TREE_AFFINE_H
      25  
      26  
      27  #define MAX_AFF_ELTS 8
      28  
      29  /* Element of an affine combination.  */
      30  
      31  class aff_comb_elt
      32  {
      33  public:
      34    /* The value of the element.  */
      35    tree val;
      36  
      37    /* Its coefficient in the combination.  */
      38    widest_int coef;
      39  };
      40  
      41  class aff_tree
      42  {
      43  public:
      44    /* Type of the result of the combination.  */
      45    tree type;
      46  
      47    /* Constant offset.  */
      48    poly_widest_int offset;
      49  
      50    /* Number of elements of the combination.  */
      51    unsigned n;
      52  
      53    /* Elements and their coefficients.  Type of elements may be different from
      54       TYPE, but their sizes must be the same (STRIP_NOPS is applied to the
      55       elements).
      56  
      57       The coefficients are always sign extended from the precision of TYPE
      58       (regardless of signedness of TYPE).  */
      59    class aff_comb_elt elts[MAX_AFF_ELTS];
      60  
      61    /* Remainder of the expression.  Usually NULL, used only if there are more
      62       than MAX_AFF_ELTS elements.  Type of REST will be either sizetype for
      63       TYPE of POINTER_TYPEs or TYPE.  */
      64    tree rest;
      65  };
      66  
      67  class name_expansion;
      68  
      69  void aff_combination_const (aff_tree *, tree, const poly_widest_int &);
      70  void aff_combination_elt (aff_tree *, tree, tree);
      71  void aff_combination_scale (aff_tree *, const widest_int &);
      72  void aff_combination_mult (aff_tree *, aff_tree *, aff_tree *);
      73  void aff_combination_add (aff_tree *, aff_tree *);
      74  void aff_combination_add_elt (aff_tree *, tree, const widest_int &);
      75  void aff_combination_remove_elt (aff_tree *, unsigned);
      76  void aff_combination_convert (aff_tree *, tree);
      77  void tree_to_aff_combination (tree, tree, aff_tree *);
      78  tree aff_combination_to_tree (aff_tree *);
      79  void unshare_aff_combination (aff_tree *);
      80  bool aff_combination_constant_multiple_p (aff_tree *, aff_tree *,
      81  					  poly_widest_int *);
      82  void aff_combination_expand (aff_tree *, hash_map<tree, name_expansion *> **);
      83  void tree_to_aff_combination_expand (tree, tree, aff_tree *,
      84  				     hash_map<tree, name_expansion *> **);
      85  tree get_inner_reference_aff (tree, aff_tree *, poly_widest_int *);
      86  void free_affine_expand_cache (hash_map<tree, name_expansion *> **);
      87  bool aff_comb_cannot_overlap_p (aff_tree *, const poly_widest_int &,
      88  				const poly_widest_int &);
      89  
      90  /* Debugging functions.  */
      91  void debug_aff (aff_tree *);
      92  
      93  /* Return AFF's type.  */
      94  inline tree
      95  aff_combination_type (aff_tree *aff)
      96  {
      97    return aff->type;
      98  }
      99  
     100  /* Return true if AFF is actually ZERO.  */
     101  inline bool
     102  aff_combination_zero_p (aff_tree *aff)
     103  {
     104    if (!aff)
     105      return true;
     106  
     107    if (aff->n == 0 && known_eq (aff->offset, 0))
     108      return true;
     109  
     110    return false;
     111  }
     112  
     113  /* Return true if AFF is actually const.  */
     114  inline bool
     115  aff_combination_const_p (aff_tree *aff)
     116  {
     117    return (aff == NULL || aff->n == 0);
     118  }
     119  
     120  /* Return true iff AFF contains one (negated) singleton variable.  Users need
     121     to make sure AFF points to a valid combination.  */
     122  inline bool
     123  aff_combination_singleton_var_p (aff_tree *aff)
     124  {
     125    return (aff->n == 1
     126  	  && known_eq (aff->offset, 0)
     127  	  && (aff->elts[0].coef == 1 || aff->elts[0].coef == -1));
     128  }
     129  #endif /* GCC_TREE_AFFINE_H */