1 /* IPA predicates. 2 Copyright (C) 2003-2021 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 short change_prob; 80 unsigned points_to_local_or_readonly_memory : 1; 81 bool equal_to (const inline_param_summary &other) const 82 { 83 return change_prob == other.change_prob 84 && points_to_local_or_readonly_memory 85 == other.points_to_local_or_readonly_memory; 86 } 87 bool useless_p (void) const 88 { 89 return change_prob == REG_BR_PROB_BASE 90 && !points_to_local_or_readonly_memory; 91 } 92 }; 93 94 typedef vec<condition, va_gc> *conditions; 95 96 /* Predicates are used to represent function parameters (such as runtime) 97 which depend on a context function is called in. 98 99 Predicates are logical formulas in conjunctive-disjunctive form consisting 100 of clauses which are bitmaps specifying a set of condition that must 101 be true for a clause to be satisfied. Physically they are represented as 102 array of clauses terminated by 0. 103 104 In order to make predicate (possibly) true, all of its clauses must 105 be (possibly) true. To make clause (possibly) true, one of conditions 106 it mentions must be (possibly) true. 107 108 There are fixed bounds on number of clauses and conditions and all the 109 manipulation functions are conservative in positive direction. I.e. we 110 may lose precision by thinking that predicate may be true even when it 111 is not. */ 112 113 typedef uint32_t clause_t; 114 class predicate 115 { 116 public: 117 enum predicate_conditions 118 { 119 false_condition = 0, 120 not_inlined_condition = 1, 121 first_dynamic_condition = 2 122 }; 123 124 /* Maximal number of conditions predicate can refer to. This is limited 125 by using clause_t to be 32bit. */ 126 static const int num_conditions = 32; 127 128 /* Special condition code we use to represent test that operand is compile 129 time constant. */ 130 static const tree_code is_not_constant = ERROR_MARK; 131 132 /* Special condition code we use to represent test that operand is not changed 133 across invocation of the function. When operand IS_NOT_CONSTANT it is 134 always CHANGED, however i.e. loop invariants can be NOT_CHANGED given 135 percentage of executions even when they are not compile time constants. */ 136 static const tree_code changed = IDENTIFIER_NODE; 137 138 139 140 /* Initialize predicate either to true of false depending on P. */ 141 inline predicate (bool p = true) 142 { 143 if (p) 144 /* True predicate. */ 145 m_clause[0] = 0; 146 else 147 /* False predicate. */ 148 set_to_cond (false_condition); 149 } 150 151 /* Sanity check that we do not mix pointers to predicates with predicates. */ 152 inline predicate (predicate *) 153 { 154 gcc_unreachable (); 155 } 156 157 /* Return predicate testing condition I. */ 158 static inline predicate predicate_testing_cond (int i) 159 { 160 class predicate p; 161 p.set_to_cond (i + first_dynamic_condition); 162 return p; 163 } 164 165 /* Return predicate testing that function was not inlined. */ 166 static predicate not_inlined (void) 167 { 168 class predicate p; 169 p.set_to_cond (not_inlined_condition); 170 return p; 171 } 172 173 /* Compute logical and of predicates. */ 174 predicate & operator &= (const predicate &); 175 inline predicate operator &(const predicate &p) const 176 { 177 predicate ret = *this; 178 ret &= p; 179 return ret; 180 } 181 182 /* Compute logical or of predicates. This is not operator because 183 extra parameter CONDITIONS is needed */ 184 predicate or_with (conditions, const predicate &) const; 185 186 /* Return true if predicates are known to be equal. */ 187 inline bool operator==(const predicate &p2) const 188 { 189 int i; 190 for (i = 0; m_clause[i]; i++) 191 { 192 gcc_checking_assert (i < max_clauses); 193 gcc_checking_assert (m_clause[i] > m_clause[i + 1]); 194 gcc_checking_assert (!p2.m_clause[i] 195 || p2.m_clause[i] > p2.m_clause[i + 1]); 196 if (m_clause[i] != p2.m_clause[i]) 197 return false; 198 } 199 return !p2.m_clause[i]; 200 } 201 202 /* Return true if predicates are known to be true or false depending 203 on COND. */ 204 inline bool operator==(const bool cond) const 205 { 206 if (cond) 207 return !m_clause[0]; 208 if (m_clause[0] == (1 << false_condition)) 209 { 210 gcc_checking_assert (!m_clause[1] 211 && m_clause[0] == 1 212 << false_condition); 213 return true; 214 } 215 return false; 216 } 217 218 inline bool operator!=(const predicate &p2) const 219 { 220 return !(*this == p2); 221 } 222 223 inline bool operator!=(const bool cond) const 224 { 225 return !(*this == cond); 226 } 227 228 /* Evaluate if predicate is known to be false given the clause of possible 229 truths. */ 230 bool evaluate (clause_t) const; 231 232 /* Estimate probability that predicate will be true in a given context. */ 233 int probability (conditions, clause_t, vec<inline_param_summary>) const; 234 235 /* Dump predicate to F. Output newline if nl. */ 236 void dump (FILE *f, conditions, bool nl=true) const; 237 void DEBUG_FUNCTION debug (conditions) const; 238 239 /* Return predicate equal to THIS after duplication. */ 240 predicate remap_after_duplication (clause_t); 241 242 /* Return predicate equal to THIS after inlining. */ 243 predicate remap_after_inlining (class ipa_fn_summary *, 244 class ipa_node_params *params_summary, 245 class ipa_fn_summary *, 246 vec<int>, vec<HOST_WIDE_INT>, 247 clause_t, const predicate &); 248 249 void stream_in (class lto_input_block *); 250 void stream_out (struct output_block *); 251 252 private: 253 static const int max_clauses = 8; 254 clause_t m_clause[max_clauses + 1]; 255 256 /* Initialize predicate to one testing single condition number COND. */ 257 inline void set_to_cond (int cond) 258 { 259 m_clause[0] = 1 << cond; 260 m_clause[1] = 0; 261 } 262 263 void add_clause (conditions conditions, clause_t); 264 }; 265 266 void dump_condition (FILE *f, conditions conditions, int cond); 267 predicate add_condition (class ipa_fn_summary *summary, 268 class ipa_node_params *params_summary, 269 int operand_num, 270 tree type, struct agg_position_info *aggpos, 271 enum tree_code code, tree val, 272 expr_eval_ops param_ops = NULL); 273