1 /* Support for simple predicate analysis. 2 3 Copyright (C) 2021-2022 Free Software Foundation, Inc. 4 Contributed by Martin Sebor <msebor@redhat.com> 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 3, or (at your option) 11 any later version. 12 13 GCC is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License 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 GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED 23 #define GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED 24 25 #define MAX_NUM_CHAINS 8 26 #define MAX_CHAIN_LEN 5 27 #define MAX_POSTDOM_CHECK 8 28 #define MAX_SWITCH_CASES 40 29 30 /* Represents a simple Boolean predicate. */ 31 struct pred_info 32 { 33 tree pred_lhs; 34 tree pred_rhs; 35 enum tree_code cond_code; 36 bool invert; 37 }; 38 39 /* The type to represent a sequence of predicates grouped 40 with .AND. operation. */ 41 typedef vec<pred_info, va_heap, vl_ptr> pred_chain; 42 43 /* The type to represent a sequence of pred_chains grouped 44 with .OR. operation. */ 45 typedef vec<pred_chain, va_heap, vl_ptr> pred_chain_union; 46 47 /* Represents a complex Boolean predicate expression. */ 48 class predicate 49 { 50 public: 51 /* Base function object type used to determine whether an expression 52 is of interest. */ 53 struct func_t 54 { 55 typedef unsigned phi_arg_set_t; 56 57 /* Return true if the argument is an expression of interest. */ 58 virtual bool operator()(tree) = 0; 59 /* Return a bitset of PHI arguments of interest. By default returns 60 bitset with a bit set for each argument. Should be called in 61 the overriden function first and, if nonzero, the result then 62 refined as appropriate. */ 63 virtual phi_arg_set_t phi_arg_set (gphi *); 64 65 /* Maximum number of PHI arguments supported by phi_arg_set(). */ 66 static constexpr unsigned max_phi_args = 67 sizeof (phi_arg_set_t) * CHAR_BIT; 68 }; 69 70 /* Construct with the specified EVAL object. */ predicate(func_t & eval)71 predicate (func_t &eval) 72 : m_preds (vNULL), m_eval (eval), m_use_expr () { } 73 74 /* Copy. */ predicate(const predicate & rhs)75 predicate (const predicate &rhs) 76 : m_preds (vNULL), m_eval (rhs.m_eval), m_use_expr () 77 { 78 *this = rhs; 79 } 80 81 predicate (basic_block, basic_block, func_t &); 82 83 ~predicate (); 84 85 /* Assign. */ 86 predicate& operator= (const predicate &); 87 is_empty()88 bool is_empty () const 89 { 90 return m_preds.is_empty (); 91 } 92 chain()93 const pred_chain_union chain () const 94 { 95 return m_preds; 96 } 97 98 /* Return true if the use by a statement in the basic block of 99 a PHI operand is ruled out (i.e., guarded) by *THIS. */ 100 bool is_use_guarded (gimple *, basic_block, gphi *, unsigned); 101 102 void init_from_control_deps (const vec<edge> *, unsigned); 103 104 void dump (gimple *, const char *) const; 105 106 void normalize (gimple * = NULL, bool = false); 107 void simplify (gimple * = NULL, bool = false); 108 109 bool is_use_guarded (gimple *, basic_block, gphi *, unsigned, 110 hash_set<gphi *> *); 111 112 /* Return the predicate expression guarding the definition of 113 the interesting variable, optionally inverted. */ 114 tree def_expr (bool = false) const; 115 /* Return the predicate expression guarding the use of the interesting 116 variable. */ 117 tree use_expr () const; 118 119 tree expr (bool = false) const; 120 121 private: 122 bool includes (const pred_chain &) const; 123 bool superset_of (const predicate &) const; 124 bool overlap (gphi *, unsigned, hash_set<gphi *> *); 125 bool use_cannot_happen (gphi *, unsigned); 126 127 bool init_from_phi_def (gphi *); 128 129 void push_pred (const pred_info &); 130 131 /* Normalization functions. */ 132 void normalize (pred_chain *, pred_info, tree_code, pred_chain *, 133 hash_set<tree> *); 134 135 void normalize (const pred_info &); 136 void normalize (const pred_chain &); 137 138 /* Simplification functions. */ 139 bool simplify_2 (); 140 bool simplify_3 (); 141 bool simplify_4 (); 142 143 private: 144 /* Representation of the predicate expression(s). */ 145 pred_chain_union m_preds; 146 /* Callback to evaluate an operand. Return true if it's interesting. */ 147 func_t &m_eval; 148 /* The predicate expression guarding the use of the interesting 149 variable. */ 150 tree m_use_expr; 151 }; 152 153 /* Bit mask handling macros. */ 154 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos) 155 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos)) 156 #define MASK_EMPTY(mask) (mask == 0) 157 158 #endif // GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED 159