gcc/range-op.h

   1 /* Header file for range operator class.
   2    Copyright (C) 2017-2022 Free Software Foundation, Inc.
   3    Contributed by Andrew MacLeod <amacleod@redhat.com>
   4    and Aldy Hernandez <aldyh@redhat.com>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16  for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #ifndef GCC_RANGE_OP_H
  23 #define GCC_RANGE_OP_H
  24
  25 // This class is implemented for each kind of operator supported by
  26 // the range generator.  It serves various purposes.
  27 //
  28 // 1 - Generates range information for the specific operation between
  29 //     two ranges.  This provides the ability to fold ranges for an
  30 //     expression.
  31 //
  32 // 2 - Performs range algebra on the expression such that a range can be
  33 //     adjusted in terms of one of the operands:
  34 //
  35 //       def = op1 + op2
  36 //
  37 //     Given a range for def, we can adjust the range so that it is in
  38 //     terms of either operand.
  39 //
  40 //     op1_range (def_range, op2) will adjust the range in place so it
  41 //     is in terms of op1.  Since op1 = def - op2, it will subtract
  42 //     op2 from each element of the range.
  43 //
  44 // 3 - Creates a range for an operand based on whether the result is 0 or
  45 //     non-zero.  This is mostly for logical true false, but can serve other
  46 //     purposes.
  47 //       ie   0 = op1 - op2 implies op2 has the same range as op1.
  48
  49 class range_operator
  50 {
  51 public:
  52   // Perform an operation between 2 ranges and return it.
  53   virtual bool fold_range (irange &r, tree type,
  54                            const irange &lh,
  55                            const irange &rh,
  56                            relation_kind rel = VREL_NONE) const;
  57
  58   // Return the range for op[12] in the general case.  LHS is the range for
  59   // the LHS of the expression, OP[12]is the range for the other
  60   //
  61   // The operand and the result is returned in R.
  62   //
  63   // TYPE is the expected type of the range.
  64   //
  65   // Return TRUE if the operation is performed and a valid range is available.
  66   //
  67   // i.e.  [LHS] = ??? + OP2
  68   // is re-formed as R = [LHS] - OP2.
  69   virtual bool op1_range (irange &r, tree type,
  70                           const irange &lhs,
  71                           const irange &op2,
  72                           relation_kind rel = VREL_NONE) const;
  73   virtual bool op2_range (irange &r, tree type,
  74                           const irange &lhs,
  75                           const irange &op1,
  76                           relation_kind rel = VREL_NONE) const;
  77
  78   // The following routines are used to represent relations between the
  79   // various operations.  If the caller knows where the symbolics are,
  80   // it can query for relationships between them given known ranges.
  81   virtual enum tree_code lhs_op1_relation (const irange &lhs,
  82                                            const irange &op1,
  83                                            const irange &op2) const;
  84   virtual enum tree_code lhs_op2_relation (const irange &lhs,
  85                                            const irange &op1,
  86                                            const irange &op2) const;
  87   virtual enum tree_code op1_op2_relation (const irange &lhs) const;
  88 protected:
  89   // Perform an integral operation between 2 sub-ranges and return it.
  90   virtual void wi_fold (irange &r, tree type,
  91                         const wide_int &lh_lb,
  92                         const wide_int &lh_ub,
  93                         const wide_int &rh_lb,
  94                         const wide_int &rh_ub) const;
  95   // Side effect of relation for generic fold_range clients.
  96   virtual bool op1_op2_relation_effect (irange &lhs_range, tree type,
  97                                         const irange &op1_range,
  98                                         const irange &op2_range,
  99                                         relation_kind rel) const;
 100   // Called by fold range to split small subranges into parts.
 101   void wi_fold_in_parts (irange &r, tree type,
 102                          const wide_int &lh_lb,
 103                          const wide_int &lh_ub,
 104                          const wide_int &rh_lb,
 105                          const wide_int &rh_ub) const;
 106 };
 107
 108 extern range_operator *range_op_handler (enum tree_code code, tree type);
 109 extern void range_cast (irange &, tree type);
 110 extern void wi_set_zero_nonzero_bits (tree type,
 111                                       const wide_int &, const wide_int &,
 112                                       wide_int &maybe_nonzero,
 113                                       wide_int &mustbe_nonzero);
 114
 115 // op1_op2_relation methods that are the same across irange and frange.
 116 enum tree_code equal_op1_op2_relation (const irange &lhs);
 117 enum tree_code not_equal_op1_op2_relation (const irange &lhs);
 118 enum tree_code lt_op1_op2_relation (const irange &lhs);
 119 enum tree_code le_op1_op2_relation (const irange &lhs);
 120 enum tree_code gt_op1_op2_relation (const irange &lhs);
 121 enum tree_code ge_op1_op2_relation (const irange &lhs);
 122
 123 enum bool_range_state { BRS_FALSE, BRS_TRUE, BRS_EMPTY, BRS_FULL };
 124 bool_range_state get_bool_state (irange &r, const irange &lhs, tree val_type);
 125
 126 // If the range of either op1 or op2 is undefined, set the result to
 127 // varying and return TRUE.  If the caller truely cares about a result,
 128 // they should pass in a varying if it has an undefined that it wants
 129 // treated as a varying.
 130
 131 inline bool
 132 empty_range_varying (irange &r, tree type,
 133                      const irange &op1, const irange & op2)
 134 {
 135   if (op1.undefined_p () || op2.undefined_p ())
 136     {
 137       r.set_varying (type);
 138       return true;
 139     }
 140   else
 141     return false;
 142 }
 143
 144 // For relation opcodes, first try to see if the supplied relation
 145 // forces a true or false result, and return that.
 146 // Then check for undefined operands.  If none of this applies,
 147 // return false.
 148
 149 inline bool
 150 relop_early_resolve (irange &r, tree type, const irange &op1,
 151                      const irange &op2, relation_kind rel,
 152                      relation_kind my_rel)
 153 {
 154   // If known relation is a complete subset of this relation, always true.
 155   if (relation_union (rel, my_rel) == my_rel)
 156     {
 157       r = range_true (type);
 158       return true;
 159     }
 160
 161   // If known relation has no subset of this relation, always false.
 162   if (relation_intersect (rel, my_rel) == VREL_EMPTY)
 163     {
 164       r = range_false (type);
 165       return true;
 166     }
 167
 168   // If either operand is undefined, return VARYING.
 169   if (empty_range_varying (r, type, op1, op2))
 170     return true;
 171
 172   return false;
 173 }
 174
 175 // This implements the range operator tables as local objects.
 176
 177 class range_op_table
 178 {
 179 public:
 180   range_operator *operator[] (enum tree_code code);
 181 protected:
 182   void set (enum tree_code code, range_operator &op);
 183 private:
 184   range_operator *m_range_tree[MAX_TREE_CODES];
 185 };
 186
 187 #endif // GCC_RANGE_OP_H