gcc/gimple-range-gori.h

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