gcc/ipa-predicate.h

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