gcc/ipa-predicate.h

   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;
  80   bool equal_to (const inline_param_summary &other) const
  81   {
  82     return change_prob == other.change_prob;
  83   }
  84   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.  */
 148   inline predicate (predicate *)
 149     {
 150       gcc_unreachable ();
 151     }
 152
 153   /* Return predicate testing condition 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.  */
 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.  */
 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);