1 /* IPA predicates. 2 Copyright (C) 2003-2018 Free Software Foundation, Inc. 3 Contributed by Jan Hubicka 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 /* Representation of inline parameters that do depend on context function is 22 inlined into (i.e. known constant values of function parameters. 23 24 Conditions that are interesting for function body are collected into CONDS 25 vector. They are of simple for function_param OP VAL, where VAL is 26 IPA invariant. The conditions are then referred by predicates. */ 27 28 struct GTY(()) condition 29 { 30 /* If agg_contents is set, this is the offset from which the used data was 31 loaded. */ 32 HOST_WIDE_INT offset; 33 /* Size of the access reading the data (or the PARM_DECL SSA_NAME). */ 34 HOST_WIDE_INT size; 35 tree val; 36 int operand_num; 37 ENUM_BITFIELD(tree_code) code : 16; 38 /* Set if the used data were loaded from an aggregate parameter or from 39 data received by reference. */ 40 unsigned agg_contents : 1; 41 /* If agg_contents is set, this differentiates between loads from data 42 passed by reference and by value. */ 43 unsigned by_ref : 1; 44 }; 45 46 /* Information kept about parameter of call site. */ 47 struct inline_param_summary 48 { 49 /* REG_BR_PROB_BASE based probability that parameter will change in between 50 two invocation of the calls. 51 I.e. loop invariant parameters 52 REG_BR_PROB_BASE/estimated_iterations and regular 53 parameters REG_BR_PROB_BASE. 54 55 Value 0 is reserved for compile time invariants. */ 56 int change_prob; 57 }; 58 59 typedef vec<condition, va_gc> *conditions; 60 61 /* Predicates are used to repesent function parameters (such as runtime) 62 which depend on a context function is called in. 63 64 Predicates are logical formulas in conjunctive-disjunctive form consisting 65 of clauses which are bitmaps specifying a set of condition that must 66 be true for a clause to be satisfied. Physically they are represented as 67 array of clauses terminated by 0. 68 69 In order to make predicate (possibly) true, all of its clauses must 70 be (possibly) true. To make clause (possibly) true, one of conditions 71 it mentions must be (possibly) true. 72 73 There are fixed bounds on number of clauses and conditions and all the 74 manipulation functions are conservative in positive direction. I.e. we 75 may lose precision by thinking that predicate may be true even when it 76 is not. */ 77 78 typedef uint32_t clause_t; 79 class predicate 80 { 81 public: 82 enum predicate_conditions 83 { 84 false_condition = 0, 85 not_inlined_condition = 1, 86 first_dynamic_condition = 2 87 }; 88 89 /* Maximal number of conditions predicate can reffer to. This is limited 90 by using clause_t to be 32bit. */ 91 static const int num_conditions = 32; 92 93 /* Special condition code we use to represent test that operand is compile 94 time constant. */ 95 static const tree_code is_not_constant = ERROR_MARK; 96 97 /* Special condition code we use to represent test that operand is not changed 98 across invocation of the function. When operand IS_NOT_CONSTANT it is 99 always CHANGED, however i.e. loop invariants can be NOT_CHANGED given 100 percentage of executions even when they are not compile time constants. */ 101 static const tree_code changed = IDENTIFIER_NODE; 102 103 104 105 /* Initialize predicate either to true of false depending on P. */ 106 inline predicate (bool p = true) 107 { 108 if (p) 109 /* True predicate. */ 110 m_clause[0] = 0; 111 else 112 /* False predicate. */ 113 set_to_cond (false_condition); 114 } 115 116 /* Sanity check that we do not mix pointers to predicates with predicates. */ 117 inline predicate (predicate *) 118 { 119 gcc_unreachable (); 120 } 121 122 /* Return predicate testing condition I. */ 123 static inline predicate predicate_testing_cond (int i) 124 { 125 class predicate p; 126 p.set_to_cond (i + first_dynamic_condition); 127 return p; 128 } 129 130 /* Return predicate testing that function was not inlined. */ 131 static predicate not_inlined (void) 132 { 133 class predicate p; 134 p.set_to_cond (not_inlined_condition); 135 return p; 136 } 137 138 /* Compute logical and of predicates. */ 139 predicate & operator &= (const predicate &); 140 inline predicate operator &(const predicate &p) const 141 { 142 predicate ret = *this; 143 ret &= p; 144 return ret; 145 } 146 147 /* Compute logical or of predicates. This is not operator because 148 extra parameter CONDITIONS is needed */ 149 predicate or_with (conditions, const predicate &) const; 150 151 /* Return true if predicates are known to be equal. */ 152 inline bool operator==(const predicate &p2) const 153 { 154 int i; 155 for (i = 0; m_clause[i]; i++) 156 { 157 gcc_checking_assert (i < max_clauses); 158 gcc_checking_assert (m_clause[i] > m_clause[i + 1]); 159 gcc_checking_assert (!p2.m_clause[i] 160 || p2.m_clause[i] > p2.m_clause[i + 1]); 161 if (m_clause[i] != p2.m_clause[i]) 162 return false; 163 } 164 return !p2.m_clause[i]; 165 } 166 167 /* Return true if predicates are known to be true or false depending 168 on COND. */ 169 inline bool operator==(const bool cond) const 170 { 171 if (cond) 172 return !m_clause[0]; 173 if (m_clause[0] == (1 << false_condition)) 174 { 175 gcc_checking_assert (!m_clause[1] 176 && m_clause[0] == 1 177 << false_condition); 178 return true; 179 } 180 return false; 181 } 182 183 inline bool operator!=(const predicate &p2) const 184 { 185 return !(*this == p2); 186 } 187 188 inline bool operator!=(const bool cond) const 189 { 190 return !(*this == cond); 191 } 192 193 /* Evaluate if predicate is known to be false given the clause of possible 194 truths. */ 195 bool evaluate (clause_t) const; 196 197 /* Estimate probability that predicate will be true in a given context. */ 198 int probability (conditions, clause_t, vec<inline_param_summary>) const; 199 200 /* Dump predicate to F. Output newline if nl. */ 201 void dump (FILE *f, conditions, bool nl=true) const; 202 void DEBUG_FUNCTION debug (conditions) const; 203 204 /* Return predicate equal to THIS after duplication. */ 205 predicate remap_after_duplication (clause_t); 206 207 /* Return predicate equal to THIS after inlining. */ 208 predicate remap_after_inlining (struct ipa_fn_summary *, 209 struct ipa_fn_summary *, 210 vec<int>, vec<int>, clause_t, const predicate &); 211 212 void stream_in (struct lto_input_block *); 213 void stream_out (struct output_block *); 214 215 private: 216 static const int max_clauses = 8; 217 clause_t m_clause[max_clauses + 1]; 218 219 /* Initialize predicate to one testing single condition number COND. */ 220 inline void set_to_cond (int cond) 221 { 222 m_clause[0] = 1 << cond; 223 m_clause[1] = 0; 224 } 225 226 void add_clause (conditions conditions, clause_t); 227 }; 228 229 void dump_condition (FILE *f, conditions conditions, int cond); 230 predicate add_condition (struct ipa_fn_summary *summary, int operand_num, 231 HOST_WIDE_INT size, struct agg_position_info *aggpos, 232 enum tree_code code, tree val); 233