gcc/gimple-range-gori.h

   1 /* Header file for gimple range GORI structures.
   2    Copyright (C) 2017-2021 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_GIMPLE_RANGE_GORI_H
  23 #define GCC_GIMPLE_RANGE_GORI_H
  24
  25
  26 // This class is used to determine which SSA_NAMES can have ranges
  27 // calculated for them on outgoing edges from basic blocks.  This represents
  28 // ONLY the effect of the basic block edge->src on a range.
  29 //
  30 // There are 2 primary entry points:
  31 //
  32 // has_edge_range_p (tree name, edge e)
  33 //   returns true if the outgoing edge *may* be able to produce range
  34 //   information for ssa_name NAME on edge E.
  35 //   FALSE is returned if this edge does not affect the range of NAME.
  36 //   if no edge is specified, return TRUE if name may have a value calculated
  37 //   on *ANY* edge that has been seen.  FALSE indicates that the global value
  38 //   is applicable everywhere that has been processed.
  39 //
  40 // outgoing_edge_range_p (irange &range, edge e, tree name)
  41 //   Actually does the calculation of RANGE for name on E
  42 //   This represents application of whatever static range effect edge E
  43 //   may have on NAME, not any cumulative effect.
  44
  45 // There are also some internal APIs
  46 //
  47 // ssa_range_in_bb ()  is an internal routine which is used to start any
  48 // calculation chain using SSA_NAMES which come from outside the block. ie
  49 //      a_2 = b_4 - 8
  50 //      if (a_2 < 30)
  51 // on the true edge, a_2 is known to be [0, 29]
  52 // b_4 can be calculated as [8, 37]
  53 // during this calculation, b_4 is considered an "import" and ssa_range_in_bb
  54 // is queried for a starting range which is used in the calculation.
  55 // A default value of VARYING provides the raw static info for the edge.
  56 //
  57 // If there is any known range for b_4 coming into this block, it can refine
  58 // the results.  This allows for cascading results to be propogated.
  59 // if b_4 is [100, 200] on entry to the block, feeds into the calculation
  60 // of a_2 = [92, 192], and finally on the true edge the range would be
  61 // an empty range [] because it is not possible for the true edge to be taken.
  62 //
  63 // expr_range_in_bb is simply a wrapper which calls ssa_range_in_bb for
  64 // SSA_NAMES and otherwise simply calculates the range of the expression.
  65 //
  66 // The remaining routines are internal use only.
  67
  68 class gori_compute
  69 {
  70 public:
  71   gori_compute ();
  72   ~gori_compute ();
  73   bool outgoing_edge_range_p (irange &r, edge e, tree name);
  74   bool has_edge_range_p (tree name, edge e = NULL);
  75   void set_range_invariant (tree name);
  76   void dump (FILE *f);
  77 protected:
  78   virtual void ssa_range_in_bb (irange &r, tree name, basic_block bb);
  79   virtual bool compute_operand_range (irange &r, gimple *stmt,
  80                                       const irange &lhs, tree name);
  81
  82   void expr_range_in_bb (irange &r, tree expr, basic_block bb);
  83   bool compute_logical_operands (irange &r, gimple *stmt,
  84                                  const irange &lhs,
  85                                  tree name);
  86   void compute_logical_operands_in_chain (class tf_range &range,
  87                                           gimple *stmt, const irange &lhs,
  88                                           tree name, tree op,
  89                                           bool op_in_chain);
  90   bool optimize_logical_operands (tf_range &range, gimple *stmt,
  91                                   const irange &lhs, tree name, tree op);
  92   bool logical_combine (irange &r, enum tree_code code, const irange &lhs,
  93                         const class tf_range &op1_range,
  94                         const class tf_range &op2_range);
  95   int_range<2> m_bool_zero;           // Boolean false cached.
  96   int_range<2> m_bool_one;            // Boolean true cached.
  97
  98 private:
  99   bool compute_operand_range_switch (irange &r, gswitch *stmt,
 100                                      const irange &lhs, tree name);
 101   bool compute_name_range_op (irange &r, gimple *stmt, const irange &lhs,
 102                               tree name);
 103   bool compute_operand1_range (irange &r, gimple *stmt, const irange &lhs,
 104                                tree name);
 105   bool compute_operand2_range (irange &r, gimple *stmt, const irange &lhs,
 106                                tree name);
 107   bool compute_operand1_and_operand2_range (irange &r, gimple *stmt,
 108                                             const irange &lhs, tree name);
 109
 110   class gori_map *m_gori_map;
 111   outgoing_range outgoing;      // Edge values for COND_EXPR & SWITCH_EXPR.
 112 };
 113
 114
 115 // This class adds a cache to gori_computes for logical expressions.
 116 //       bool result = x && y
 117 // requires calcuation of both X and Y for both true and false results.
 118 // There are 4 combinations [0,0][0,0] [0,0][1,1] [1,1][0,0] and [1,1][1,1].
 119 // Note that each pair of possible results for X and Y are used twice, and
 120 // the calcuation of those results are the same each time.
 121 //
 122 // The cache simply checks if a stmt is cachable, and if so, saves both the
 123 // true and false results for the next time the query is made.
 124 //
 125 // This is used to speed up long chains of logical operations which
 126 // quickly become exponential.
 127
 128 class gori_compute_cache : public gori_compute
 129 {
 130 public:
 131   gori_compute_cache ();
 132   ~gori_compute_cache ();
 133 protected:
 134   virtual bool compute_operand_range (irange &r, gimple *stmt,
 135                                       const irange &lhs, tree name);
 136 private:
 137   void cache_stmt (gimple *);
 138   typedef gori_compute super;
 139   class logical_stmt_cache *m_cache;
 140 };
 141
 142 #endif // GCC_GIMPLE_RANGE_GORI_H