gcc/range-op.h

   1 /* Header file for range operator class.
   2    Copyright (C) 2017-2023 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   friend class range_op_table;
  52 public:
  53   range_operator () : m_code (ERROR_MARK) { }
  54   // Perform an operation between 2 ranges and return it.
  55   virtual bool fold_range (irange &r, tree type,
  56                            const irange &lh,
  57                            const irange &rh,
  58                            relation_trio = TRIO_VARYING) const;
  59
  60   // Return the range for op[12] in the general case.  LHS is the range for
  61   // the LHS of the expression, OP[12]is the range for the other
  62   //
  63   // The operand and the result is returned in R.
  64   //
  65   // TYPE is the expected type of the range.
  66   //
  67   // Return TRUE if the operation is performed and a valid range is available.
  68   //
  69   // i.e.  [LHS] = ??? + OP2
  70   // is re-formed as R = [LHS] - OP2.
  71   virtual bool op1_range (irange &r, tree type,
  72                           const irange &lhs,
  73                           const irange &op2,
  74                           relation_trio = TRIO_VARYING) const;
  75   virtual bool op2_range (irange &r, tree type,
  76                           const irange &lhs,
  77                           const irange &op1,
  78                           relation_trio = TRIO_VARYING) const;
  79
  80   // The following routines are used to represent relations between the
  81   // various operations.  If the caller knows where the symbolics are,
  82   // it can query for relationships between them given known ranges.
  83   // the optional relation passed in is the relation between op1 and op2.
  84   virtual relation_kind lhs_op1_relation (const irange &lhs,
  85                                           const irange &op1,
  86                                           const irange &op2,
  87                                           relation_kind = VREL_VARYING) const;
  88   virtual relation_kind lhs_op2_relation (const irange &lhs,
  89                                           const irange &op1,
  90                                           const irange &op2,
  91                                           relation_kind = VREL_VARYING) const;
  92   virtual relation_kind op1_op2_relation (const irange &lhs) const;
  93 protected:
  94   // Perform an integral operation between 2 sub-ranges and return it.
  95   virtual void wi_fold (irange &r, tree type,
  96                         const wide_int &lh_lb,
  97                         const wide_int &lh_ub,
  98                         const wide_int &rh_lb,
  99                         const wide_int &rh_ub) const;
 100   // Effect of relation for generic fold_range clients.
 101   virtual bool op1_op2_relation_effect (irange &lhs_range, tree type,
 102                                         const irange &op1_range,
 103                                         const irange &op2_range,
 104                                         relation_kind rel) const;
 105   // Called by fold range to split small subranges into parts.
 106   void wi_fold_in_parts (irange &r, tree type,
 107                          const wide_int &lh_lb,
 108                          const wide_int &lh_ub,
 109                          const wide_int &rh_lb,
 110                          const wide_int &rh_ub) const;
 111
 112   // Called by fold range to split small subranges into parts when op1 == op2
 113   void wi_fold_in_parts_equiv (irange &r, tree type,
 114                                const wide_int &lb,
 115                                const wide_int &ub,
 116                                unsigned limit) const;
 117
 118   // Tree code of the range operator or ERROR_MARK if unknown.
 119   tree_code m_code;
 120 };
 121
 122 // Like range_operator above, but for floating point operators.
 123
 124 class range_operator_float
 125 {
 126 public:
 127   virtual bool fold_range (frange &r, tree type,
 128                            const frange &lh,
 129                            const frange &rh,
 130                            relation_trio = TRIO_VARYING) const;
 131   virtual void rv_fold (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub,
 132                         bool &maybe_nan,
 133                         tree type,
 134                         const REAL_VALUE_TYPE &lh_lb,
 135                         const REAL_VALUE_TYPE &lh_ub,
 136                         const REAL_VALUE_TYPE &rh_lb,
 137                         const REAL_VALUE_TYPE &rh_ub,
 138                         relation_kind) const;
 139   // Unary operations have the range of the LHS as op2.
 140   virtual bool fold_range (irange &r, tree type,
 141                            const frange &lh,
 142                            const irange &rh,
 143                            relation_trio = TRIO_VARYING) const;
 144   virtual bool fold_range (irange &r, tree type,
 145                            const frange &lh,
 146                            const frange &rh,
 147                            relation_trio = TRIO_VARYING) const;
 148   virtual bool op1_range (frange &r, tree type,
 149                           const frange &lhs,
 150                           const frange &op2,
 151                           relation_trio = TRIO_VARYING) const;
 152   virtual bool op1_range (frange &r, tree type,
 153                           const irange &lhs,
 154                           const frange &op2,
 155                           relation_trio = TRIO_VARYING) const;
 156   virtual bool op2_range (frange &r, tree type,
 157                           const frange &lhs,
 158                           const frange &op1,
 159                           relation_trio = TRIO_VARYING) const;
 160   virtual bool op2_range (frange &r, tree type,
 161                           const irange &lhs,
 162                           const frange &op1,
 163                           relation_trio = TRIO_VARYING) const;
 164
 165   virtual relation_kind lhs_op1_relation (const frange &lhs,
 166                                           const frange &op1,
 167                                           const frange &op2,
 168                                           relation_kind = VREL_VARYING) const;
 169   virtual relation_kind lhs_op1_relation (const irange &lhs,
 170                                           const frange &op1,
 171                                           const frange &op2,
 172                                           relation_kind = VREL_VARYING) const;
 173   virtual relation_kind lhs_op2_relation (const frange &lhs,
 174                                           const frange &op1,
 175                                           const frange &op2,
 176                                           relation_kind = VREL_VARYING) const;
 177   virtual relation_kind lhs_op2_relation (const irange &lhs,
 178                                           const frange &op1,
 179                                           const frange &op2,
 180                                           relation_kind = VREL_VARYING) const;
 181   virtual relation_kind op1_op2_relation (const irange &lhs) const;
 182   virtual relation_kind op1_op2_relation (const frange &lhs) const;
 183 };
 184
 185 class range_op_handler
 186 {
 187 public:
 188   range_op_handler ();
 189   range_op_handler (enum tree_code code, tree type);
 190   inline operator bool () const { return m_valid; }
 191
 192   bool fold_range (vrange &r, tree type,
 193                    const vrange &lh,
 194                    const vrange &rh,
 195                    relation_trio = TRIO_VARYING) const;
 196   bool op1_range (vrange &r, tree type,
 197                   const vrange &lhs,
 198                   const vrange &op2,
 199                   relation_trio = TRIO_VARYING) const;
 200   bool op2_range (vrange &r, tree type,
 201                   const vrange &lhs,
 202                   const vrange &op1,
 203                   relation_trio = TRIO_VARYING) const;
 204   relation_kind lhs_op1_relation (const vrange &lhs,
 205                                   const vrange &op1,
 206                                   const vrange &op2,
 207                                   relation_kind = VREL_VARYING) const;
 208   relation_kind lhs_op2_relation (const vrange &lhs,
 209                                   const vrange &op1,
 210                                   const vrange &op2,
 211                                   relation_kind = VREL_VARYING) const;
 212   relation_kind op1_op2_relation (const vrange &lhs) const;
 213 protected:
 214   void set_op_handler (enum tree_code code, tree type);
 215   bool m_valid;
 216   range_operator *m_int;
 217   range_operator_float *m_float;
 218 };
 219
 220 extern bool range_cast (vrange &, tree type);
 221 extern void wi_set_zero_nonzero_bits (tree type,
 222                                       const wide_int &, const wide_int &,
 223                                       wide_int &maybe_nonzero,
 224                                       wide_int &mustbe_nonzero);
 225
 226 // op1_op2_relation methods that are the same across irange and frange.
 227 relation_kind equal_op1_op2_relation (const irange &lhs);
 228 relation_kind not_equal_op1_op2_relation (const irange &lhs);
 229 relation_kind lt_op1_op2_relation (const irange &lhs);
 230 relation_kind le_op1_op2_relation (const irange &lhs);
 231 relation_kind gt_op1_op2_relation (const irange &lhs);
 232 relation_kind ge_op1_op2_relation (const irange &lhs);
 233
 234 enum bool_range_state { BRS_FALSE, BRS_TRUE, BRS_EMPTY, BRS_FULL };
 235 bool_range_state get_bool_state (vrange &r, const vrange &lhs, tree val_type);
 236
 237 // If the range of either op1 or op2 is undefined, set the result to
 238 // varying and return TRUE.  If the caller truely cares about a result,
 239 // they should pass in a varying if it has an undefined that it wants
 240 // treated as a varying.
 241
 242 inline bool
 243 empty_range_varying (vrange &r, tree type,
 244                      const vrange &op1, const vrange & op2)
 245 {
 246   if (op1.undefined_p () || op2.undefined_p ())
 247     {
 248       r.set_varying (type);
 249       return true;
 250     }
 251   else
 252     return false;
 253 }
 254
 255 // For relation opcodes, first try to see if the supplied relation
 256 // forces a true or false result, and return that.
 257 // Then check for undefined operands.  If none of this applies,
 258 // return false.
 259
 260 inline bool
 261 relop_early_resolve (irange &r, tree type, const vrange &op1,
 262                      const vrange &op2, relation_trio trio,
 263                      relation_kind my_rel)
 264 {
 265   relation_kind rel = trio.op1_op2 ();
 266   // If known relation is a complete subset of this relation, always true.
 267   if (relation_union (rel, my_rel) == my_rel)
 268     {
 269       r = range_true (type);
 270       return true;
 271     }
 272
 273   // If known relation has no subset of this relation, always false.
 274   if (relation_intersect (rel, my_rel) == VREL_UNDEFINED)
 275     {
 276       r = range_false (type);
 277       return true;
 278     }
 279
 280   // If either operand is undefined, return VARYING.
 281   if (empty_range_varying (r, type, op1, op2))
 282     return true;
 283
 284   return false;
 285 }
 286
 287 // This implements the range operator tables as local objects.
 288
 289 class range_op_table
 290 {
 291 public:
 292   range_operator *operator[] (enum tree_code code);
 293 protected:
 294   void set (enum tree_code code, range_operator &op);
 295 private:
 296   range_operator *m_range_tree[MAX_TREE_CODES];
 297 };
 298
 299 // Like above, but for floating point operators.
 300
 301 class floating_op_table
 302 {
 303 public:
 304   floating_op_table ();
 305   range_operator_float *operator[] (enum tree_code code);
 306 private:
 307   void set (enum tree_code code, range_operator_float &op);
 308   range_operator_float *m_range_tree[MAX_TREE_CODES];
 309 };
 310
 311 // This holds the range op table for floating point operations.
 312 extern floating_op_table *floating_tree_table;
 313
 314 #endif // GCC_RANGE_OP_H