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 143