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   virtual bool pointers_handled_p (enum range_op_dispatch_type, unsigned) const;
 233
 234 protected:
 235   // Perform an integral operation between 2 sub-ranges and return it.
 236   virtual void wi_fold (irange &r, tree type,
 237                         const wide_int &lh_lb,
 238                         const wide_int &lh_ub,
 239                         const wide_int &rh_lb,
 240                         const wide_int &rh_ub) const;
 241   // Effect of relation for generic fold_range clients.
 242   virtual bool op1_op2_relation_effect (irange &lhs_range, tree type,
 243                                         const irange &op1_range,
 244                                         const irange &op2_range,
 245                                         relation_kind rel) const;
 246   virtual bool op1_op2_relation_effect (prange &lhs_range, tree type,
 247                                         const prange &op1_range,
 248                                         const prange &op2_range,
 249                                         relation_kind rel) const;
 250   virtual bool op1_op2_relation_effect (prange &lhs_range, tree type,
 251                                         const prange &op1_range,
 252                                         const irange &op2_range,
 253                                         relation_kind rel) const;
 254   virtual bool op1_op2_relation_effect (irange &lhs_range, tree type,
 255                                         const prange &op1_range,
 256                                         const prange &op2_range,
 257                                         relation_kind rel) const;
 258   virtual bool op1_op2_relation_effect (prange &lhs_range, tree type,
 259                                         const irange &op1_range,
 260                                         const prange &op2_range,
 261                                         relation_kind rel) const;
 262   virtual bool op1_op2_relation_effect (irange &lhs_range, tree type,
 263                                         const prange &op1_range,
 264                                         const irange &op2_range,
 265                                         relation_kind rel) const;
 266   // Called by fold range to split small subranges into parts.
 267   void wi_fold_in_parts (irange &r, tree type,
 268                          const wide_int &lh_lb,
 269                          const wide_int &lh_ub,
 270                          const wide_int &rh_lb,
 271                          const wide_int &rh_ub) const;
 272
 273   // Called by fold range to split small subranges into parts when op1 == op2
 274   void wi_fold_in_parts_equiv (irange &r, tree type,
 275                                const wide_int &lb,
 276                                const wide_int &ub,
 277                                unsigned limit) const;
 278   // Apply any bitmasks implied by these ranges.
 279   virtual void update_bitmask (irange &, const irange &, const irange &) const;
 280   virtual void update_bitmask (irange &, const prange &, const prange &) const;
 281
 282   // Perform an float operation between 2 ranges and return it.
 283   virtual void rv_fold (frange &r, tree type,
 284                         const REAL_VALUE_TYPE &lh_lb,
 285                         const REAL_VALUE_TYPE &lh_ub,
 286                         const REAL_VALUE_TYPE &rh_lb,
 287                         const REAL_VALUE_TYPE &rh_ub,
 288                         relation_kind) const;
 289 };
 290
 291 class range_op_handler
 292 {
 293 public:
 294   range_op_handler ();
 295   range_op_handler (unsigned);
 296   operator bool () const;
 297   range_operator *range_op () const;
 298
 299   bool fold_range (vrange &r, tree type,
 300                    const vrange &lh,
 301                    const vrange &rh,
 302                    relation_trio = TRIO_VARYING) const;
 303   bool op1_range (vrange &r, tree type,
 304                   const vrange &lhs,
 305                   const vrange &op2,
 306                   relation_trio = TRIO_VARYING) const;
 307   bool op2_range (vrange &r, tree type,
 308                   const vrange &lhs,
 309                   const vrange &op1,
 310                   relation_trio = TRIO_VARYING) const;
 311   relation_kind lhs_op1_relation (const vrange &lhs,
 312                                   const vrange &op1,
 313                                   const vrange &op2,
 314                                   relation_kind = VREL_VARYING) const;
 315   relation_kind lhs_op2_relation (const vrange &lhs,
 316                                   const vrange &op1,
 317                                   const vrange &op2,
 318                                   relation_kind = VREL_VARYING) const;
 319   relation_kind op1_op2_relation (const vrange &lhs,
 320                                   const vrange &op1,
 321                                   const vrange &op2) const;
 322   bool overflow_free_p (const vrange &lh, const vrange &rh,
 323                         relation_trio = TRIO_VARYING) const;
 324   bool operand_check_p (tree, tree, tree) const;
 325 protected:
 326   unsigned dispatch_kind (const vrange &lhs, const vrange &op1,
 327                           const vrange& op2) const;
 328   void discriminator_fail (const vrange &,
 329                            const vrange &,
 330                            const vrange &) const;
 331   range_operator *m_operator;
 332 };
 333
 334 // Cast the range in R to TYPE if R supports TYPE.
 335
 336 inline bool
 337 range_cast (vrange &r, tree type)
 338 {
 339   gcc_checking_assert (r.supports_type_p (type));
 340   Value_Range tmp (r);
 341   Value_Range varying (type);
 342   varying.set_varying (type);
 343   // Call op_convert, if it fails, the result is varying.
 344   if (!range_op_handler (CONVERT_EXPR).fold_range (r, type, tmp, varying))
 345     {
 346       r.set_varying (type);
 347       return false;
 348     }
 349   return true;
 350 }
 351
 352 // Range cast which is capable of switching range kinds.
 353 // ie for float to int.
 354
 355 inline bool
 356 range_cast (Value_Range &r, tree type)
 357 {
 358   Value_Range tmp (r);
 359   Value_Range varying (type);
 360   varying.set_varying (type);
 361
 362   // Ensure we are in the correct mode for the call to fold.
 363   r.set_type (type);
 364
 365   // Call op_convert, if it fails, the result is varying.
 366   if (!range_op_handler (CONVERT_EXPR).fold_range (r, type, tmp, varying))
 367     {
 368       r.set_varying (type);
 369       return false;
 370     }
 371   return true;
 372 }
 373
 374
 375 extern void wi_set_zero_nonzero_bits (tree type,
 376                                       const wide_int &, const wide_int &,
 377                                       wide_int &maybe_nonzero,
 378                                       wide_int &mustbe_nonzero);
 379
 380 // These are extra operators that do not fit in the normal scheme of things.
 381 // Add them to the end of the tree-code vector, and provide a name for
 382 // each allowing for easy access when required.
 383
 384 #define OP_WIDEN_MULT_SIGNED    ((unsigned) MAX_TREE_CODES)
 385 #define OP_WIDEN_MULT_UNSIGNED  ((unsigned) MAX_TREE_CODES + 1)
 386 #define OP_WIDEN_PLUS_SIGNED    ((unsigned) MAX_TREE_CODES + 2)
 387 #define OP_WIDEN_PLUS_UNSIGNED  ((unsigned) MAX_TREE_CODES + 3)
 388 #define RANGE_OP_TABLE_SIZE     ((unsigned) MAX_TREE_CODES + 4)
 389
 390 // This implements the range operator tables as local objects.
 391
 392 class range_op_table
 393 {
 394 public:
 395   range_op_table ();
 396   inline range_operator *operator[] (unsigned code)
 397     {
 398       gcc_checking_assert (code < RANGE_OP_TABLE_SIZE);
 399       return m_range_tree[code];
 400     }
 401 protected:
 402   inline void set (unsigned code, range_operator &op)
 403     {
 404       gcc_checking_assert (code < RANGE_OP_TABLE_SIZE);
 405       gcc_checking_assert (m_range_tree[code] == NULL);
 406       m_range_tree[code] = &op;
 407     }
 408   range_operator *m_range_tree[RANGE_OP_TABLE_SIZE];
 409   void initialize_integral_ops ();
 410   void initialize_pointer_ops ();
 411   void initialize_float_ops ();
 412 };
 413
 414 // Temporary exports so the pointers_handled_p() sanity code can see
 415 // which pointer combination is being attempted.  This will be deleted
 416 // once pointers_handled_p is gone.
 417 extern const unsigned RO_III;
 418 extern const unsigned RO_IFI;
 419 extern const unsigned RO_IFF;
 420 extern const unsigned RO_FFF;
 421 extern const unsigned RO_FIF;
 422 extern const unsigned RO_FII;
 423 extern const unsigned RO_PPP;
 424 extern const unsigned RO_PPI;
 425 extern const unsigned RO_IPP;
 426 extern const unsigned RO_IPI;
 427 extern const unsigned RO_PIP;
 428 extern const unsigned RO_PII;
 429
 430 #endif // GCC_RANGE_OP_H