ipa-predicate.h 7.3 KB

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