gcc/ipa-predicate.h

   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                                   const vec<int> &, const 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);