gcc/ipa-predicate.h

   1 /* IPA predicates.
   2    Copyright (C) 2003-2017 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 for  function_param OP VAL, where VAL is
  26    IPA invariant.  The conditions are then referred by predicates.  */
  27
  28 struct GTY(()) condition
  29 {
  30   /* If agg_contents is set, this is the offset from which the used data was
  31      loaded.  */
  32   HOST_WIDE_INT offset;
  33   /* Size of the access reading the data (or the PARM_DECL SSA_NAME).  */
  34   HOST_WIDE_INT size;
  35   tree val;
  36   int operand_num;
  37   ENUM_BITFIELD(tree_code) code : 16;
  38   /* Set if the used data were loaded from an aggregate parameter or from
  39      data received by reference.  */
  40   unsigned agg_contents : 1;
  41   /* If agg_contents is set, this differentiates between loads from data
  42      passed by reference and by value.  */
  43   unsigned by_ref : 1;
  44 };
  45
  46 /* Information kept about parameter of call site.  */
  47 struct inline_param_summary
  48 {
  49   /* REG_BR_PROB_BASE based probability that parameter will change in between
  50      two invocation of the calls.
  51      I.e. loop invariant parameters
  52      REG_BR_PROB_BASE/estimated_iterations and regular
  53      parameters REG_BR_PROB_BASE.
  54
  55      Value 0 is reserved for compile time invariants. */
  56   int change_prob;
  57 };
  58
  59 typedef vec<condition, va_gc> *conditions;
  60
  61 /* Predicates are used to repesent function parameters (such as runtime)
  62    which depend on a context function is called in.
  63
  64    Predicates are logical formulas in conjunctive-disjunctive form consisting
  65    of clauses which are bitmaps specifying a set of condition that must
  66    be true for a clause to be satisfied. Physically they are represented as
  67    array of clauses terminated by 0.
  68
  69    In order to make predicate (possibly) true, all of its clauses must
  70    be (possibly) true. To make clause (possibly) true, one of conditions
  71    it mentions must be (possibly) true.
  72
  73    There are fixed bounds on number of clauses and conditions and all the
  74    manipulation functions are conservative in positive direction. I.e. we
  75    may lose precision by thinking that predicate may be true even when it
  76    is not.  */
  77
  78 typedef uint32_t clause_t;
  79 class predicate
  80 {
  81 public:
  82   enum predicate_conditions
  83     {
  84       false_condition = 0,
  85       not_inlined_condition = 1,
  86       first_dynamic_condition = 2
  87     };
  88
  89   /* Maximal number of conditions predicate can reffer to.  This is limited
  90      by using clause_t to be 32bit.  */
  91   static const int num_conditions = 32;
  92
  93   /* Special condition code we use to represent test that operand is compile
  94      time constant.  */
  95   static const tree_code is_not_constant = ERROR_MARK;
  96
  97   /* Special condition code we use to represent test that operand is not changed
  98      across invocation of the function.  When operand IS_NOT_CONSTANT it is
  99      always CHANGED, however i.e. loop invariants can be NOT_CHANGED given
 100      percentage of executions even when they are not compile time constants.  */
 101   static const tree_code changed = IDENTIFIER_NODE;
 102
 103
 104
 105   /* Initialize predicate either to true of false depending on P.  */
 106   inline predicate (bool p = true)
 107     {
 108       if (p)
 109         /* True predicate.  */
 110         m_clause[0] = 0;
 111       else
 112         /* False predicate. */
 113         set_to_cond (false_condition);
 114     }
 115
 116   /* Sanity check that we do not mix pointers to predicates with predicates.  */
 117   inline predicate (predicate *)
 118     {
 119       gcc_unreachable ();
 120     }
 121
 122   /* Return predicate testing condition I.  */
 123   static inline predicate predicate_testing_cond (int i)
 124     {
 125       class predicate p;
 126       p.set_to_cond (i + first_dynamic_condition);
 127       return p;
 128     }
 129
 130   /* Return predicate testing that function was not inlined.  */
 131   static predicate not_inlined (void)
 132     {
 133       class predicate p;
 134       p.set_to_cond (not_inlined_condition);
 135       return p;
 136     }
 137
 138   /* Compute logical and of predicates.  */
 139   predicate & operator &= (const predicate &);
 140   inline predicate operator &(const predicate &p) const
 141     {
 142       predicate ret = *this;
 143       ret &= p;
 144       return ret;
 145     }
 146
 147   /* Compute logical or of predicates.  This is not operator because
 148      extra parameter CONDITIONS is needed  */
 149   predicate or_with (conditions, const predicate &) const;
 150
 151   /* Return true if predicates are known to be equal.  */
 152   inline bool operator==(const predicate &p2) const
 153     {
 154       int i;
 155       for (i = 0; m_clause[i]; i++)
 156         {
 157           gcc_checking_assert (i < max_clauses);
 158           gcc_checking_assert (m_clause[i] > m_clause[i + 1]);
 159           gcc_checking_assert (!p2.m_clause[i]
 160                                || p2.m_clause[i] > p2.m_clause[i + 1]);
 161           if (m_clause[i] != p2.m_clause[i])
 162             return false;
 163         }
 164       return !p2.m_clause[i];
 165     }
 166
 167   /* Return true if predicates are known to be true or false depending
 168      on COND.  */
 169   inline bool operator==(const bool cond) const
 170     {
 171       if (cond)
 172         return !m_clause[0];
 173       if (m_clause[0] == (1 << false_condition))
 174         {
 175           gcc_checking_assert (!m_clause[1]
 176                                && m_clause[0] == 1
 177                                   << false_condition);
 178           return true;
 179         }
 180       return false;
 181     }
 182
 183   inline bool operator!=(const predicate &p2) const
 184     {
 185       return !(*this == p2);
 186     }
 187
 188   inline bool operator!=(const bool cond) const
 189     {
 190       return !(*this == cond);
 191     }
 192
 193   /* Evaluate if predicate is known to be false given the clause of possible
 194      truths.  */
 195   bool evaluate (clause_t) const;
 196
 197   /* Estimate probability that predicate will be true in a given context.  */
 198   int probability (conditions, clause_t, vec<inline_param_summary>) const;
 199
 200   /* Dump predicate to F. Output newline if nl.  */
 201   void dump (FILE *f, conditions, bool nl=true) const;
 202   void DEBUG_FUNCTION debug (conditions) const;
 203
 204   /* Return predicate equal to THIS after duplication.  */
 205   predicate remap_after_duplication (clause_t);
 206
 207   /* Return predicate equal to THIS after inlining.  */
 208   predicate remap_after_inlining (struct ipa_fn_summary *,
 209                                   struct ipa_fn_summary *,
 210                                   vec<int>, vec<int>, clause_t, const predicate &);
 211
 212   void stream_in (struct lto_input_block *);
 213   void stream_out (struct output_block *);
 214
 215 private:
 216   static const int max_clauses = 8;
 217   clause_t m_clause[max_clauses + 1];
 218
 219   /* Initialize predicate to one testing single condition number COND.  */
 220   inline void set_to_cond (int cond)
 221     {
 222       m_clause[0] = 1 << cond;
 223       m_clause[1] = 0;
 224     }
 225
 226   void add_clause (conditions conditions, clause_t);
 227 };
 228
 229 void dump_condition (FILE *f, conditions conditions, int cond);
 230 predicate add_condition (struct ipa_fn_summary *summary, int operand_num,
 231                          HOST_WIDE_INT size, struct agg_position_info *aggpos,
 232                          enum tree_code code, tree val);