123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232 |
- /* IPA predicates.
- Copyright (C) 2003-2019 Free Software Foundation, Inc.
- Contributed by Jan Hubicka
- This file is part of GCC.
- GCC is free software; you can redistribute it and/or modify it under
- the terms of the GNU General Public License as published by the Free
- Software Foundation; either version 3, or (at your option) any later
- version.
- GCC is distributed in the hope that it will be useful, but WITHOUT ANY
- WARRANTY; without even the implied warranty of MERCHANTABILITY or
- FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
- for more details.
- You should have received a copy of the GNU General Public License
- along with GCC; see the file COPYING3. If not see
- <http://www.gnu.org/licenses/>. */
- /* Representation of inline parameters that do depend on context function is
- inlined into (i.e. known constant values of function parameters.
- Conditions that are interesting for function body are collected into CONDS
- vector. They are of simple for function_param OP VAL, where VAL is
- IPA invariant. The conditions are then referred by predicates. */
- struct GTY(()) condition
- {
- /* If agg_contents is set, this is the offset from which the used data was
- loaded. */
- HOST_WIDE_INT offset;
- /* Size of the access reading the data (or the PARM_DECL SSA_NAME). */
- HOST_WIDE_INT size;
- tree val;
- int operand_num;
- ENUM_BITFIELD(tree_code) code : 16;
- /* Set if the used data were loaded from an aggregate parameter or from
- data received by reference. */
- unsigned agg_contents : 1;
- /* If agg_contents is set, this differentiates between loads from data
- passed by reference and by value. */
- unsigned by_ref : 1;
- };
- /* Information kept about parameter of call site. */
- struct inline_param_summary
- {
- /* REG_BR_PROB_BASE based probability that parameter will change in between
- two invocation of the calls.
- I.e. loop invariant parameters
- REG_BR_PROB_BASE/estimated_iterations and regular
- parameters REG_BR_PROB_BASE.
- Value 0 is reserved for compile time invariants. */
- int change_prob;
- };
- typedef vec<condition, va_gc> *conditions;
- /* Predicates are used to repesent function parameters (such as runtime)
- which depend on a context function is called in.
- Predicates are logical formulas in conjunctive-disjunctive form consisting
- of clauses which are bitmaps specifying a set of condition that must
- be true for a clause to be satisfied. Physically they are represented as
- array of clauses terminated by 0.
- In order to make predicate (possibly) true, all of its clauses must
- be (possibly) true. To make clause (possibly) true, one of conditions
- it mentions must be (possibly) true.
- There are fixed bounds on number of clauses and conditions and all the
- manipulation functions are conservative in positive direction. I.e. we
- may lose precision by thinking that predicate may be true even when it
- is not. */
- typedef uint32_t clause_t;
- class predicate
- {
- public:
- enum predicate_conditions
- {
- false_condition = 0,
- not_inlined_condition = 1,
- first_dynamic_condition = 2
- };
- /* Maximal number of conditions predicate can reffer to. This is limited
- by using clause_t to be 32bit. */
- static const int num_conditions = 32;
- /* Special condition code we use to represent test that operand is compile
- time constant. */
- static const tree_code is_not_constant = ERROR_MARK;
- /* Special condition code we use to represent test that operand is not changed
- across invocation of the function. When operand IS_NOT_CONSTANT it is
- always CHANGED, however i.e. loop invariants can be NOT_CHANGED given
- percentage of executions even when they are not compile time constants. */
- static const tree_code changed = IDENTIFIER_NODE;
- /* Initialize predicate either to true of false depending on P. */
- inline predicate (bool p = true)
- {
- if (p)
- /* True predicate. */
- m_clause[0] = 0;
- else
- /* False predicate. */
- set_to_cond (false_condition);
- }
- /* Sanity check that we do not mix pointers to predicates with predicates. */
- inline predicate (predicate *)
- {
- gcc_unreachable ();
- }
- /* Return predicate testing condition I. */
- static inline predicate predicate_testing_cond (int i)
- {
- class predicate p;
- p.set_to_cond (i + first_dynamic_condition);
- return p;
- }
- /* Return predicate testing that function was not inlined. */
- static predicate not_inlined (void)
- {
- class predicate p;
- p.set_to_cond (not_inlined_condition);
- return p;
- }
- /* Compute logical and of predicates. */
- predicate & operator &= (const predicate &);
- inline predicate operator &(const predicate &p) const
- {
- predicate ret = *this;
- ret &= p;
- return ret;
- }
- /* Compute logical or of predicates. This is not operator because
- extra parameter CONDITIONS is needed */
- predicate or_with (conditions, const predicate &) const;
- /* Return true if predicates are known to be equal. */
- inline bool operator==(const predicate &p2) const
- {
- int i;
- for (i = 0; m_clause[i]; i++)
- {
- gcc_checking_assert (i < max_clauses);
- gcc_checking_assert (m_clause[i] > m_clause[i + 1]);
- gcc_checking_assert (!p2.m_clause[i]
- || p2.m_clause[i] > p2.m_clause[i + 1]);
- if (m_clause[i] != p2.m_clause[i])
- return false;
- }
- return !p2.m_clause[i];
- }
- /* Return true if predicates are known to be true or false depending
- on COND. */
- inline bool operator==(const bool cond) const
- {
- if (cond)
- return !m_clause[0];
- if (m_clause[0] == (1 << false_condition))
- {
- gcc_checking_assert (!m_clause[1]
- && m_clause[0] == 1
- << false_condition);
- return true;
- }
- return false;
- }
- inline bool operator!=(const predicate &p2) const
- {
- return !(*this == p2);
- }
- inline bool operator!=(const bool cond) const
- {
- return !(*this == cond);
- }
- /* Evaluate if predicate is known to be false given the clause of possible
- truths. */
- bool evaluate (clause_t) const;
- /* Estimate probability that predicate will be true in a given context. */
- int probability (conditions, clause_t, vec<inline_param_summary>) const;
- /* Dump predicate to F. Output newline if nl. */
- void dump (FILE *f, conditions, bool nl=true) const;
- void DEBUG_FUNCTION debug (conditions) const;
- /* Return predicate equal to THIS after duplication. */
- predicate remap_after_duplication (clause_t);
- /* Return predicate equal to THIS after inlining. */
- predicate remap_after_inlining (struct ipa_fn_summary *,
- struct ipa_fn_summary *,
- vec<int>, vec<int>, clause_t, const predicate &);
- void stream_in (struct lto_input_block *);
- void stream_out (struct output_block *);
- private:
- static const int max_clauses = 8;
- clause_t m_clause[max_clauses + 1];
- /* Initialize predicate to one testing single condition number COND. */
- inline void set_to_cond (int cond)
- {
- m_clause[0] = 1 << cond;
- m_clause[1] = 0;
- }
- void add_clause (conditions conditions, clause_t);
- };
- void dump_condition (FILE *f, conditions conditions, int cond);
- predicate add_condition (struct ipa_fn_summary *summary, int operand_num,
- HOST_WIDE_INT size, struct agg_position_info *aggpos,
- enum tree_code code, tree val);
|