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 enum range_op_dispatch_type
  26 {
  27   DISPATCH_FOLD_RANGE,
  28   DISPATCH_OP1_RANGE,
  29   DISPATCH_OP2_RANGE,
  30   DISPATCH_LHS_OP1_RELATION,
  31   DISPATCH_LHS_OP2_RELATION,
  32   DISPATCH_OP1_OP2_RELATION
  33 };
  34
  35 // This class is implemented for each kind of operator supported by
  36 // the range generator.  It serves various purposes.
  37 //
  38 // 1 - Generates range information for the specific operation between
  39 //     two ranges.  This provides the ability to fold ranges for an
  40 //     expression.
  41 //
  42 // 2 - Performs range algebra on the expression such that a range can be
  43 //     adjusted in terms of one of the operands:
  44 //
  45 //       def = op1 + op2
  46 //
  47 //     Given a range for def, we can adjust the range so that it is in
  48 //     terms of either operand.
  49 //
  50 //     op1_range (def_range, op2) will adjust the range in place so it
  51 //     is in terms of op1.  Since op1 = def - op2, it will subtract
  52 //     op2 from each element of the range.
  53 //
  54 // 3 - Creates a range for an operand based on whether the result is 0 or
  55 //     non-zero.  This is mostly for logical true false, but can serve other
  56 //     purposes.
  57 //       ie   0 = op1 - op2 implies op2 has the same range as op1.
  58 //
  59 // 4 - All supported range combinations are explicitly specified.
  60 //     Any desired combinations should be implemented for each operator.
  61 //     When new range classes are added, new matching prototypes should be
  62 //     added.
  63
  64 class range_operator
  65 {
  66   friend class range_op_table;
  67 public:
  68   // Perform an operation between 2 ranges and return it.
  69   virtual bool fold_range (irange &r, tree type,
  70                            const irange &lh,
  71                            const irange &rh,
  72                            relation_trio = TRIO_VARYING) const;
  73   virtual bool fold_range (frange &r, tree type,
  74                            const frange &lh,
  75                            const frange &rh,
  76                            relation_trio = TRIO_VARYING) const;
  77   virtual bool fold_range (irange &r, tree type,
  78                            const frange &lh,
  79                            const irange &rh,
  80                            relation_trio = TRIO_VARYING) const;
  81   virtual bool fold_range (irange &r, tree type,
  82                            const frange &lh,
  83                            const frange &rh,
  84                            relation_trio = TRIO_VARYING) const;
  85   virtual bool fold_range (frange &r, tree type,
  86                            const irange &lh,
  87                            const irange &rh,
  88                            relation_trio = TRIO_VARYING) const;
  89   virtual bool fold_range (prange &r, tree type,
  90                            const prange &lh,
  91                            const prange &rh,
  92                            relation_trio = TRIO_VARYING) const;
  93   virtual bool fold_range (prange &r, tree type,
  94                            const prange &lh,
  95                            const irange &rh,
  96                            relation_trio = TRIO_VARYING) const;
  97   virtual bool fold_range (irange &r, tree type,
  98                            const prange &lh,
  99                            const prange &rh,
 100                            relation_trio = TRIO_VARYING) const;
 101   virtual bool fold_range (prange &r, tree type,
 102                            const irange &lh,
 103                            const prange &rh,
 104                            relation_trio = TRIO_VARYING) const;
 105   virtual bool fold_range (irange &r, tree type,
 106                            const prange &lh,
 107                            const irange &rh,
 108                            relation_trio = TRIO_VARYING) const;
 109
 110   // Return the range for op[12] in the general case.  LHS is the range for
 111   // the LHS of the expression, OP[12]is the range for the other
 112   //
 113   // The operand and the result is returned in R.
 114   //
 115   // TYPE is the expected type of the range.
 116   //
 117   // Return TRUE if the operation is performed and a valid range is available.
 118   //
 119   // i.e.  [LHS] = ??? + OP2
 120   // is re-formed as R = [LHS] - OP2.
 121   virtual bool op1_range (irange &r, tree type,
 122                           const irange &lhs,
 123                           const irange &op2,
 124                           relation_trio = TRIO_VARYING) const;
 125   virtual bool op1_range (prange &r, tree type,
 126                           const prange &lhs,
 127                           const prange &op2,
 128                           relation_trio = TRIO_VARYING) const;
 129   virtual bool op1_range (prange &r, tree type,
 130                           const irange &lhs,
 131                           const prange &op2,
 132                           relation_trio = TRIO_VARYING) const;
 133   virtual bool op1_range (prange &r, tree type,
 134                           const prange &lhs,
 135                           const irange &op2,
 136                           relation_trio = TRIO_VARYING) const;
 137   virtual bool op1_range (irange &r, tree type,
 138                           const prange &lhs,
 139                           const irange &op2,
 140                           relation_trio = TRIO_VARYING) const;
 141   virtual bool op1_range (frange &r, tree type,
 142                           const frange &lhs,
 143                           const frange &op2,
 144                           relation_trio = TRIO_VARYING) const;
 145   virtual bool op1_range (frange &r, tree type,
 146                           const irange &lhs,
 147                           const frange &op2,
 148                           relation_trio = TRIO_VARYING) const;
 149
 150
 151   virtual bool op2_range (irange &r, tree type,
 152                           const irange &lhs,
 153                           const irange &op1,
 154                           relation_trio = TRIO_VARYING) const;
 155   virtual bool op2_range (prange &r, tree type,
 156                           const irange &lhs,
 157                           const prange &op1,
 158                           relation_trio = TRIO_VARYING) const;
 159   virtual bool op2_range (irange &r, tree type,
 160                           const prange &lhs,
 161                           const prange &op1,
 162                           relation_trio = TRIO_VARYING) const;
 163   virtual bool op2_range (frange &r, tree type,
 164                           const frange &lhs,
 165                           const frange &op1,
 166                           relation_trio = TRIO_VARYING) const;
 167   virtual bool op2_range (frange &r, tree type,
 168                           const irange &lhs,
 169                           const frange &op1,
 170                           relation_trio = TRIO_VARYING) const;
 171
 172   // The following routines are used to represent relations between the
 173   // various operations.  If the caller knows where the symbolics are,
 174   // it can query for relationships between them given known ranges.
 175   // the optional relation passed in is the relation between op1 and op2.
 176   virtual relation_kind lhs_op1_relation (const irange &lhs,
 177                                           const irange &op1,
 178                                           const irange &op2,
 179                                           relation_kind = VREL_VARYING) const;
 180   virtual relation_kind lhs_op1_relation (const prange &lhs,
 181                                           const prange &op1,
 182                                           const prange &op2,
 183                                           relation_kind = VREL_VARYING) const;
 184   virtual relation_kind lhs_op1_relation (const prange &lhs,
 185                                           const irange &op1,
 186                                           const irange &op2,
 187                                           relation_kind = VREL_VARYING) const;
 188   virtual relation_kind lhs_op1_relation (const irange &lhs,
 189                                           const prange &op1,
 190                                           const prange &op2,
 191                                           relation_kind = VREL_VARYING) const;
 192   virtual relation_kind lhs_op1_relation (const frange &lhs,
 193                                           const frange &op1,
 194                                           const frange &op2,
 195                                           relation_kind = VREL_VARYING) const;
 196   virtual relation_kind lhs_op1_relation (const irange &lhs,
 197                                           const frange &op1,
 198                                           const frange &op2,
 199                                           relation_kind = VREL_VARYING) const;
 200
 201   virtual relation_kind lhs_op2_relation (const irange &lhs,
 202                                           const irange &op1,
 203                                           const irange &op2,
 204                                           relation_kind = VREL_VARYING) const;
 205   virtual relation_kind lhs_op2_relation (const frange &lhs,
 206                                           const frange &op1,
 207                                           const frange &op2,
 208                                           relation_kind = VREL_VARYING) const;
 209   virtual relation_kind lhs_op2_relation (const irange &lhs,
 210                                           const frange &op1,
 211                                           const frange &op2,
 212                                           relation_kind = VREL_VARYING) const;
 213
 214   virtual relation_kind op1_op2_relation (const irange &lhs,
 215                                           const irange &op1,
 216                                           const irange &op2) const;
 217   virtual relation_kind op1_op2_relation (const irange &lhs,
 218                                           const prange &op1,
 219                                           const prange &op2) const;
 220   virtual relation_kind op1_op2_relation (const irange &lhs,
 221                                           const frange &op1,
 222                                           const frange &op2) const;
 223   virtual relation_kind op1_op2_relation (const frange &lhs,
 224                                           const frange &op1,
 225                                           const frange &op2) const;
 226
 227   virtual bool overflow_free_p (const irange &lh, const irange &rh,
 228                                 relation_trio = TRIO_VARYING) const;
 229
 230   // Compatability check for operands.
 231   virtual bool operand_check_p (tree, tree, tree) const;
 232
 233 protected:
 234   // Perform an integral operation between 2 sub-ranges and return it.
 235   virtual void wi_fold (irange &r, tree type,
 236                         const wide_int &lh_lb,
 237                         const wide_int &lh_ub,
 238                         const wide_int &rh_lb,
 239                         const wide_int &rh_ub) const;
 240   // Effect of relation for generic fold_range clients.
 241   virtual bool op1_op2_relation_effect (irange &lhs_range, tree type,
 242                                         const irange &op1_range,
 243                                         const irange &op2_range,
 244                                         relation_kind rel) const;
 245   virtual bool op1_op2_relation_effect (prange &lhs_range, tree type,
 246                                         const prange &op1_range,
 247                                         const prange &op2_range,
 248                                         relation_kind rel) const;
 249   virtual bool op1_op2_relation_effect (prange &lhs_range, tree type,
 250                                         const prange &op1_range,
 251                                         const irange &op2_range,
 252                                         relation_kind rel) const;
 253   virtual bool op1_op2_relation_effect (irange &lhs_range, tree type,
 254                                         const prange &op1_range,
 255                                         const prange &op2_range,
 256                                         relation_kind rel) const;
 257   virtual bool op1_op2_relation_effect (prange &lhs_range, tree type,
 258                                         const irange &op1_range,
 259                                         const prange &op2_range,
 260                                         relation_kind rel) const;
 261   virtual bool op1_op2_relation_effect (irange &lhs_range, tree type,
 262                                         const prange &op1_range,
 263                                         const irange &op2_range,
 264                                         relation_kind rel) const;
 265   // Called by fold range to split small subranges into parts.
 266   void wi_fold_in_parts (irange &r, tree type,
 267                          const wide_int &lh_lb,
 268                          const wide_int &lh_ub,
 269                          const wide_int &rh_lb,
 270                          const wide_int &rh_ub) const;
 271
 272   // Called by fold range to split small subranges into parts when op1 == op2
 273   void wi_fold_in_parts_equiv (irange &r, tree type,
 274                                const wide_int &lb,
 275                                const wide_int &ub,
 276                                unsigned limit) const;
 277   // Apply any bitmasks implied by these ranges.
 278   virtual void update_bitmask (irange &, const irange &, const irange &) const;
 279   virtual void update_bitmask (irange &, const prange &, const prange &) const;
 280
 281   // Perform an float operation between 2 ranges and return it.
 282   virtual void rv_fold (frange &r, tree type,
 283                         const REAL_VALUE_TYPE &lh_lb,
 284                         const REAL_VALUE_TYPE &lh_ub,
 285                         const REAL_VALUE_TYPE &rh_lb,
 286                         const REAL_VALUE_TYPE &rh_ub,
 287                         relation_kind) const;
 288 };
 289
 290 class range_op_handler
 291 {
 292 public:
 293   range_op_handler ();
 294   range_op_handler (unsigned);
 295   operator bool () const;
 296   range_operator *range_op () const;
 297
 298   bool fold_range (vrange &r, tree type,
 299                    const vrange &lh,
 300                    const vrange &rh,
 301                    relation_trio = TRIO_VARYING) const;
 302   bool op1_range (vrange &r, tree type,
 303                   const vrange &lhs,
 304                   const vrange &op2,
 305                   relation_trio = TRIO_VARYING) const;
 306   bool op2_range (vrange &r, tree type,
 307                   const vrange &lhs,
 308                   const vrange &op1,
 309                   relation_trio = TRIO_VARYING) const;
 310   relation_kind lhs_op1_relation (const vrange &lhs,
 311                                   const vrange &op1,
 312                                   const vrange &op2,
 313                                   relation_kind = VREL_VARYING) const;
 314   relation_kind lhs_op2_relation (const vrange &lhs,
 315                                   const vrange &op1,
 316                                   const vrange &op2,
 317                                   relation_kind = VREL_VARYING) const;
 318   relation_kind op1_op2_relation (const vrange &lhs,
 319                                   const vrange &op1,
 320                                   const vrange &op2) const;
 321   bool overflow_free_p (const vrange &lh, const vrange &rh,
 322                         relation_trio = TRIO_VARYING) const;
 323   bool operand_check_p (tree, tree, tree) const;
 324 protected:
 325   unsigned dispatch_kind (const vrange &lhs, const vrange &op1,
 326                           const vrange& op2) const;
 327   void discriminator_fail (const vrange &,
 328                            const vrange &,
 329                            const vrange &) const;
 330   range_operator *m_operator;
 331 };
 332
 333 // Cast the range in R to TYPE if R supports TYPE.
 334
 335 inline bool
 336 range_cast (vrange &r, tree type)
 337 {
 338   gcc_checking_assert (r.supports_type_p (type));
 339   value_range tmp (r);
 340   value_range varying (type);
 341   varying.set_varying (type);
 342   // Call op_convert, if it fails, the result is varying.
 343   if (!range_op_handler (CONVERT_EXPR).fold_range (r, type, tmp, varying))
 344     {
 345       r.set_varying (type);
 346       return false;
 347     }
 348   return true;
 349 }
 350
 351 // Range cast which is capable of switching range kinds.
 352 // ie for float to int.
 353
 354 inline bool
 355 range_cast (value_range &r, tree type)
 356 {
 357   value_range tmp (r);
 358   value_range varying (type);
 359   varying.set_varying (type);
 360
 361   // Ensure we are in the correct mode for the call to fold.
 362   r.set_type (type);
 363
 364   // Call op_convert, if it fails, the result is varying.
 365   if (!range_op_handler (CONVERT_EXPR).fold_range (r, type, tmp, varying))
 366     {
 367       r.set_varying (type);
 368       return false;
 369     }
 370   return true;
 371 }
 372
 373
 374 extern void wi_set_zero_nonzero_bits (tree type,
 375                                       const wide_int &, const wide_int &,
 376                                       wide_int &maybe_nonzero,
 377                                       wide_int &mustbe_nonzero);
 378
 379 // These are extra operators that do not fit in the normal scheme of things.
 380 // Add them to the end of the tree-code vector, and provide a name for
 381 // each allowing for easy access when required.
 382
 383 #define OP_WIDEN_MULT_SIGNED    ((unsigned) MAX_TREE_CODES)
 384 #define OP_WIDEN_MULT_UNSIGNED  ((unsigned) MAX_TREE_CODES + 1)
 385 #define OP_WIDEN_PLUS_SIGNED    ((unsigned) MAX_TREE_CODES + 2)
 386 #define OP_WIDEN_PLUS_UNSIGNED  ((unsigned) MAX_TREE_CODES + 3)
 387 #define RANGE_OP_TABLE_SIZE     ((unsigned) MAX_TREE_CODES + 4)
 388
 389 // This implements the range operator tables as local objects.
 390
 391 class range_op_table
 392 {
 393 public:
 394   range_op_table ();
 395   inline range_operator *operator[] (unsigned code)
 396     {
 397       gcc_checking_assert (code < RANGE_OP_TABLE_SIZE);
 398       return m_range_tree[code];
 399     }
 400 protected:
 401   inline void set (unsigned code, range_operator &op)
 402     {
 403       gcc_checking_assert (code < RANGE_OP_TABLE_SIZE);
 404       gcc_checking_assert (m_range_tree[code] == NULL);
 405       m_range_tree[code] = &op;
 406     }
 407   range_operator *m_range_tree[RANGE_OP_TABLE_SIZE];
 408   void initialize_integral_ops ();
 409   void initialize_pointer_ops ();
 410   void initialize_float_ops ();
 411 };
 412
 413 #endif // GCC_RANGE_OP_H