gcc/range-op.h

   1 /* Header file for range operator class.
   2    Copyright (C) 2017-2024 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 // 4 - All supported range combinations are explicitly specified.
  50 //     Any desired combinations should be implemented for each operator.
  51 //     When new range classes are added, new matching prototypes should be
  52 //     added.
  53
  54 class range_operator
  55 {
  56   friend class range_op_table;
  57 public:
  58   // Perform an operation between 2 ranges and return it.
  59   virtual bool fold_range (irange &r, tree type,
  60                            const irange &lh,
  61                            const irange &rh,
  62                            relation_trio = TRIO_VARYING) const;
  63   virtual bool fold_range (frange &r, tree type,
  64                            const frange &lh,
  65                            const frange &rh,
  66                            relation_trio = TRIO_VARYING) const;
  67   virtual bool fold_range (irange &r, tree type,
  68                            const frange &lh,
  69                            const irange &rh,
  70                            relation_trio = TRIO_VARYING) const;
  71   virtual bool fold_range (irange &r, tree type,
  72                            const frange &lh,
  73                            const frange &rh,
  74                            relation_trio = TRIO_VARYING) const;
  75   virtual bool fold_range (frange &r, tree type,
  76                            const irange &lh,
  77                            const irange &rh,
  78                            relation_trio = TRIO_VARYING) const;
  79
  80   // Return the range for op[12] in the general case.  LHS is the range for
  81   // the LHS of the expression, OP[12]is the range for the other
  82   //
  83   // The operand and the result is returned in R.
  84   //
  85   // TYPE is the expected type of the range.
  86   //
  87   // Return TRUE if the operation is performed and a valid range is available.
  88   //
  89   // i.e.  [LHS] = ??? + OP2
  90   // is re-formed as R = [LHS] - OP2.
  91   virtual bool op1_range (irange &r, tree type,
  92                           const irange &lhs,
  93                           const irange &op2,
  94                           relation_trio = TRIO_VARYING) const;
  95   virtual bool op1_range (frange &r, tree type,
  96                           const frange &lhs,
  97                           const frange &op2,
  98                           relation_trio = TRIO_VARYING) const;
  99   virtual bool op1_range (frange &r, tree type,
 100                           const irange &lhs,
 101                           const frange &op2,
 102                           relation_trio = TRIO_VARYING) const;
 103
 104
 105   virtual bool op2_range (irange &r, tree type,
 106                           const irange &lhs,
 107                           const irange &op1,
 108                           relation_trio = TRIO_VARYING) const;
 109   virtual bool op2_range (frange &r, tree type,
 110                           const frange &lhs,
 111                           const frange &op1,
 112                           relation_trio = TRIO_VARYING) const;
 113   virtual bool op2_range (frange &r, tree type,
 114                           const irange &lhs,
 115                           const frange &op1,
 116                           relation_trio = TRIO_VARYING) const;
 117
 118   // The following routines are used to represent relations between the
 119   // various operations.  If the caller knows where the symbolics are,
 120   // it can query for relationships between them given known ranges.
 121   // the optional relation passed in is the relation between op1 and op2.
 122   virtual relation_kind lhs_op1_relation (const irange &lhs,
 123                                           const irange &op1,
 124                                           const irange &op2,
 125                                           relation_kind = VREL_VARYING) const;
 126   virtual relation_kind lhs_op1_relation (const frange &lhs,
 127                                           const frange &op1,
 128                                           const frange &op2,
 129                                           relation_kind = VREL_VARYING) const;
 130   virtual relation_kind lhs_op1_relation (const irange &lhs,
 131                                           const frange &op1,
 132                                           const frange &op2,
 133                                           relation_kind = VREL_VARYING) const;
 134
 135   virtual relation_kind lhs_op2_relation (const irange &lhs,
 136                                           const irange &op1,
 137                                           const irange &op2,
 138                                           relation_kind = VREL_VARYING) const;
 139   virtual relation_kind lhs_op2_relation (const frange &lhs,
 140                                           const frange &op1,
 141                                           const frange &op2,
 142                                           relation_kind = VREL_VARYING) const;
 143   virtual relation_kind lhs_op2_relation (const irange &lhs,
 144                                           const frange &op1,
 145                                           const frange &op2,
 146                                           relation_kind = VREL_VARYING) const;
 147
 148   virtual relation_kind op1_op2_relation (const irange &lhs,
 149                                           const irange &op1,
 150                                           const irange &op2) const;
 151   virtual relation_kind op1_op2_relation (const irange &lhs,
 152                                           const frange &op1,
 153                                           const frange &op2) const;
 154   virtual relation_kind op1_op2_relation (const frange &lhs,
 155                                           const frange &op1,
 156                                           const frange &op2) const;
 157
 158   virtual bool overflow_free_p (const irange &lh, const irange &rh,
 159                                 relation_trio = TRIO_VARYING) const;
 160
 161   // Compatability check for operands.
 162   virtual bool operand_check_p (tree, tree, tree) const;
 163
 164 protected:
 165   // Perform an integral operation between 2 sub-ranges and return it.
 166   virtual void wi_fold (irange &r, tree type,
 167                         const wide_int &lh_lb,
 168                         const wide_int &lh_ub,
 169                         const wide_int &rh_lb,
 170                         const wide_int &rh_ub) const;
 171   // Effect of relation for generic fold_range clients.
 172   virtual bool op1_op2_relation_effect (irange &lhs_range, tree type,
 173                                         const irange &op1_range,
 174                                         const irange &op2_range,
 175                                         relation_kind rel) const;
 176   // Called by fold range to split small subranges into parts.
 177   void wi_fold_in_parts (irange &r, tree type,
 178                          const wide_int &lh_lb,
 179                          const wide_int &lh_ub,
 180                          const wide_int &rh_lb,
 181                          const wide_int &rh_ub) const;
 182
 183   // Called by fold range to split small subranges into parts when op1 == op2
 184   void wi_fold_in_parts_equiv (irange &r, tree type,
 185                                const wide_int &lb,
 186                                const wide_int &ub,
 187                                unsigned limit) const;
 188   // Apply any bitmasks implied by these ranges.
 189   virtual void update_bitmask (irange &, const irange &, const irange &) const;
 190
 191   // Perform an float operation between 2 ranges and return it.
 192   virtual void rv_fold (frange &r, tree type,
 193                         const REAL_VALUE_TYPE &lh_lb,
 194                         const REAL_VALUE_TYPE &lh_ub,
 195                         const REAL_VALUE_TYPE &rh_lb,
 196                         const REAL_VALUE_TYPE &rh_ub,
 197                         relation_kind) const;
 198 };
 199
 200 class range_op_handler
 201 {
 202 public:
 203   range_op_handler ();
 204   range_op_handler (unsigned);
 205   operator bool () const;
 206   range_operator *range_op () const;
 207
 208   bool fold_range (vrange &r, tree type,
 209                    const vrange &lh,
 210                    const vrange &rh,
 211                    relation_trio = TRIO_VARYING) const;
 212   bool op1_range (vrange &r, tree type,
 213                   const vrange &lhs,
 214                   const vrange &op2,
 215                   relation_trio = TRIO_VARYING) const;
 216   bool op2_range (vrange &r, tree type,
 217                   const vrange &lhs,
 218                   const vrange &op1,
 219                   relation_trio = TRIO_VARYING) const;
 220   relation_kind lhs_op1_relation (const vrange &lhs,
 221                                   const vrange &op1,
 222                                   const vrange &op2,
 223                                   relation_kind = VREL_VARYING) const;
 224   relation_kind lhs_op2_relation (const vrange &lhs,
 225                                   const vrange &op1,
 226                                   const vrange &op2,
 227                                   relation_kind = VREL_VARYING) const;
 228   relation_kind op1_op2_relation (const vrange &lhs,
 229                                   const vrange &op1,
 230                                   const vrange &op2) const;
 231   bool overflow_free_p (const vrange &lh, const vrange &rh,
 232                         relation_trio = TRIO_VARYING) const;
 233   bool operand_check_p (tree, tree, tree) const;
 234 protected:
 235   unsigned dispatch_kind (const vrange &lhs, const vrange &op1,
 236                           const vrange& op2) const;
 237   range_operator *m_operator;
 238 };
 239
 240 // Cast the range in R to TYPE if R supports TYPE.
 241
 242 inline bool
 243 range_cast (vrange &r, tree type)
 244 {
 245   gcc_checking_assert (r.supports_type_p (type));
 246   Value_Range tmp (r);
 247   Value_Range varying (type);
 248   varying.set_varying (type);
 249   // Call op_convert, if it fails, the result is varying.
 250   if (!range_op_handler (CONVERT_EXPR).fold_range (r, type, tmp, varying))
 251     {
 252       r.set_varying (type);
 253       return false;
 254     }
 255   return true;
 256 }
 257
 258 // Range cast which is capable of switching range kinds.
 259 // ie for float to int.
 260
 261 inline bool
 262 range_cast (Value_Range &r, tree type)
 263 {
 264   Value_Range tmp (r);
 265   Value_Range varying (type);
 266   varying.set_varying (type);
 267
 268   // Ensure we are in the correct mode for the call to fold.
 269   r.set_type (type);
 270
 271   // Call op_convert, if it fails, the result is varying.
 272   if (!range_op_handler (CONVERT_EXPR).fold_range (r, type, tmp, varying))
 273     {
 274       r.set_varying (type);
 275       return false;
 276     }
 277   return true;
 278 }
 279
 280
 281 extern void wi_set_zero_nonzero_bits (tree type,
 282                                       const wide_int &, const wide_int &,
 283                                       wide_int &maybe_nonzero,
 284                                       wide_int &mustbe_nonzero);
 285
 286 // These are extra operators that do not fit in the normal scheme of things.
 287 // Add them to the end of the tree-code vector, and provide a name for
 288 // each allowing for easy access when required.
 289
 290 #define OP_WIDEN_MULT_SIGNED    ((unsigned) MAX_TREE_CODES)
 291 #define OP_WIDEN_MULT_UNSIGNED  ((unsigned) MAX_TREE_CODES + 1)
 292 #define OP_WIDEN_PLUS_SIGNED    ((unsigned) MAX_TREE_CODES + 2)
 293 #define OP_WIDEN_PLUS_UNSIGNED  ((unsigned) MAX_TREE_CODES + 3)
 294 #define RANGE_OP_TABLE_SIZE     ((unsigned) MAX_TREE_CODES + 4)
 295
 296 // This implements the range operator tables as local objects.
 297
 298 class range_op_table
 299 {
 300 public:
 301   range_op_table ();
 302   inline range_operator *operator[] (unsigned code)
 303     {
 304       gcc_checking_assert (code < RANGE_OP_TABLE_SIZE);
 305       return m_range_tree[code];
 306     }
 307 protected:
 308   inline void set (unsigned code, range_operator &op)
 309     {
 310       gcc_checking_assert (code < RANGE_OP_TABLE_SIZE);
 311       gcc_checking_assert (m_range_tree[code] == NULL);
 312       m_range_tree[code] = &op;
 313     }
 314   range_operator *m_range_tree[RANGE_OP_TABLE_SIZE];
 315   void initialize_integral_ops ();
 316   void initialize_pointer_ops ();
 317   void initialize_float_ops ();
 318 };
 319 #endif // GCC_RANGE_OP_H