1 /* IPA predicates. 2 Copyright (C) 2003-2020 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 as kind of a mathematical transformation on 26 function parameter, T(function_param), in which the parameter occurs only 27 once, and other operands are IPA invariant. The conditions are then 28 referred by predicates. */ 29 30 31 /* A simplified representation of tree node, for unary, binary and ternary 32 operation. Computations on parameter are decomposed to a series of this 33 kind of structure. */ 34 struct GTY(()) expr_eval_op 35 { 36 /* Result type of expression. */ 37 tree type; 38 /* Constant operands in expression, there are at most two. */ 39 tree val[2]; 40 /* Index of parameter operand in expression. */ 41 unsigned index : 2; 42 /* Operation code of expression. */ 43 ENUM_BITFIELD(tree_code) code : 16; 44 }; 45 46 typedef vec<expr_eval_op, va_gc> *expr_eval_ops; 47 48 struct GTY(()) condition 49 { 50 /* If agg_contents is set, this is the offset from which the used data was 51 loaded. */ 52 HOST_WIDE_INT offset; 53 /* Type of the access reading the data (or the PARM_DECL SSA_NAME). */ 54 tree type; 55 tree val; 56 int operand_num; 57 ENUM_BITFIELD(tree_code) code : 16; 58 /* Set if the used data were loaded from an aggregate parameter or from 59 data received by reference. */ 60 unsigned agg_contents : 1; 61 /* If agg_contents is set, this differentiates between loads from data 62 passed by reference and by value. */ 63 unsigned by_ref : 1; 64 /* A set of sequential operations on the parameter, which can be seen as 65 a mathematical function on the parameter. */ 66 expr_eval_ops param_ops; 67 }; 68 69 /* Information kept about parameter of call site. */ 70 struct inline_param_summary 71 { 72 /* REG_BR_PROB_BASE based probability that parameter will change in between 73 two invocation of the calls. 74 I.e. loop invariant parameters 75 REG_BR_PROB_BASE/estimated_iterations and regular 76 parameters REG_BR_PROB_BASE. 77 78 Value 0 is reserved for compile time invariants. */ 79 int change_prob; equal_toinline_param_summary80 bool equal_to (const inline_param_summary &other) const 81 { 82 return change_prob == other.change_prob; 83 } useless_pinline_param_summary84 bool useless_p (void) const 85 { 86 return change_prob == REG_BR_PROB_BASE; 87 } 88 }; 89 90 typedef vec<condition, va_gc> *conditions; 91 92 /* Predicates are used to represent function parameters (such as runtime) 93 which depend on a context function is called in. 94 95 Predicates are logical formulas in conjunctive-disjunctive form consisting 96 of clauses which are bitmaps specifying a set of condition that must 97 be true for a clause to be satisfied. Physically they are represented as 98 array of clauses terminated by 0. 99 100 In order to make predicate (possibly) true, all of its clauses must 101 be (possibly) true. To make clause (possibly) true, one of conditions 102 it mentions must be (possibly) true. 103 104 There are fixed bounds on number of clauses and conditions and all the 105 manipulation functions are conservative in positive direction. I.e. we 106 may lose precision by thinking that predicate may be true even when it 107 is not. */ 108 109 typedef uint32_t clause_t; 110 class predicate 111 { 112 public: 113 enum predicate_conditions 114 { 115 false_condition = 0, 116 not_inlined_condition = 1, 117 first_dynamic_condition = 2 118 }; 119 120 /* Maximal number of conditions predicate can refer to. This is limited 121 by using clause_t to be 32bit. */ 122 static const int num_conditions = 32; 123 124 /* Special condition code we use to represent test that operand is compile 125 time constant. */ 126 static const tree_code is_not_constant = ERROR_MARK; 127 128 /* Special condition code we use to represent test that operand is not changed 129 across invocation of the function. When operand IS_NOT_CONSTANT it is 130 always CHANGED, however i.e. loop invariants can be NOT_CHANGED given 131 percentage of executions even when they are not compile time constants. */ 132 static const tree_code changed = IDENTIFIER_NODE; 133 134 135 136 /* Initialize predicate either to true of false depending on P. */ 137 inline predicate (bool p = true) 138 { 139 if (p) 140 /* True predicate. */ 141 m_clause[0] = 0; 142 else 143 /* False predicate. */ 144 set_to_cond (false_condition); 145 } 146 147 /* Sanity check that we do not mix pointers to predicates with predicates. */ predicate(predicate *)148 inline predicate (predicate *) 149 { 150 gcc_unreachable (); 151 } 152 153 /* Return predicate testing condition I. */ predicate_testing_cond(int i)154 static inline predicate predicate_testing_cond (int i) 155 { 156 class predicate p; 157 p.set_to_cond (i + first_dynamic_condition); 158 return p; 159 } 160 161 /* Return predicate testing that function was not inlined. */ not_inlined(void)162 static predicate not_inlined (void) 163 { 164 class predicate p; 165 p.set_to_cond (not_inlined_condition); 166 return p; 167 } 168 169 /* Compute logical and of predicates. */ 170 predicate & operator &= (const predicate &); 171 inline predicate operator &(const predicate &p) const 172 { 173 predicate ret = *this; 174 ret &= p; 175 return ret; 176 } 177 178 /* Compute logical or of predicates. This is not operator because 179 extra parameter CONDITIONS is needed */ 180 predicate or_with (conditions, const predicate &) const; 181 182 /* Return true if predicates are known to be equal. */ 183 inline bool operator==(const predicate &p2) const 184 { 185 int i; 186 for (i = 0; m_clause[i]; i++) 187 { 188 gcc_checking_assert (i < max_clauses); 189 gcc_checking_assert (m_clause[i] > m_clause[i + 1]); 190 gcc_checking_assert (!p2.m_clause[i] 191 || p2.m_clause[i] > p2.m_clause[i + 1]); 192 if (m_clause[i] != p2.m_clause[i]) 193 return false; 194 } 195 return !p2.m_clause[i]; 196 } 197 198 /* Return true if predicates are known to be true or false depending 199 on COND. */ 200 inline bool operator==(const bool cond) const 201 { 202 if (cond) 203 return !m_clause[0]; 204 if (m_clause[0] == (1 << false_condition)) 205 { 206 gcc_checking_assert (!m_clause[1] 207 && m_clause[0] == 1 208 << false_condition); 209 return true; 210 } 211 return false; 212 } 213 214 inline bool operator!=(const predicate &p2) const 215 { 216 return !(*this == p2); 217 } 218 219 inline bool operator!=(const bool cond) const 220 { 221 return !(*this == cond); 222 } 223 224 /* Evaluate if predicate is known to be false given the clause of possible 225 truths. */ 226 bool evaluate (clause_t) const; 227 228 /* Estimate probability that predicate will be true in a given context. */ 229 int probability (conditions, clause_t, vec<inline_param_summary>) const; 230 231 /* Dump predicate to F. Output newline if nl. */ 232 void dump (FILE *f, conditions, bool nl=true) const; 233 void DEBUG_FUNCTION debug (conditions) const; 234 235 /* Return predicate equal to THIS after duplication. */ 236 predicate remap_after_duplication (clause_t); 237 238 /* Return predicate equal to THIS after inlining. */ 239 predicate remap_after_inlining (class ipa_fn_summary *, 240 class ipa_node_params *params_summary, 241 class ipa_fn_summary *, 242 vec<int>, vec<int>, clause_t, const predicate &); 243 244 void stream_in (class lto_input_block *); 245 void stream_out (struct output_block *); 246 247 private: 248 static const int max_clauses = 8; 249 clause_t m_clause[max_clauses + 1]; 250 251 /* Initialize predicate to one testing single condition number COND. */ set_to_cond(int cond)252 inline void set_to_cond (int cond) 253 { 254 m_clause[0] = 1 << cond; 255 m_clause[1] = 0; 256 } 257 258 void add_clause (conditions conditions, clause_t); 259 }; 260 261 void dump_condition (FILE *f, conditions conditions, int cond); 262 predicate add_condition (class ipa_fn_summary *summary, 263 class ipa_node_params *params_summary, 264 int operand_num, 265 tree type, struct agg_position_info *aggpos, 266 enum tree_code code, tree val, 267 expr_eval_ops param_ops = NULL); 268