gcc/gimple-predicate-analysis.h

   1 /* Support for simple predicate analysis.
   2
   3    Copyright (C) 2021 Free Software Foundation, Inc.
   4    Contributed by Martin Sebor <msebor@redhat.com>
   5
   6    This file is part of GCC.
   7
   8    GCC is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 3, or (at your option)
  11    any later version.
  12
  13    GCC is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with GCC; see the file COPYING3.  If not see
  20    <http://www.gnu.org/licenses/>.  */
  21
  22 #ifndef GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED
  23 #define GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED
  24
  25 #define MAX_NUM_CHAINS 8
  26 #define MAX_CHAIN_LEN 5
  27 #define MAX_POSTDOM_CHECK 8
  28 #define MAX_SWITCH_CASES 40
  29
  30 /* Represents a simple Boolean predicate.  */
  31 struct pred_info
  32 {
  33   tree pred_lhs;
  34   tree pred_rhs;
  35   enum tree_code cond_code;
  36   bool invert;
  37 };
  38
  39 /* The type to represent a sequence of predicates grouped
  40    with .AND. operation.  */
  41 typedef vec<pred_info, va_heap, vl_ptr> pred_chain;
  42
  43 /* The type to represent a sequence of pred_chains grouped
  44    with .OR. operation.  */
  45 typedef vec<pred_chain, va_heap, vl_ptr> pred_chain_union;
  46
  47 /* Represents a complex Boolean predicate expression.  */
  48 class predicate
  49 {
  50  public:
  51   /* Base function object type used to determine whether an expression
  52      is of interest.  */
  53   struct func_t
  54   {
  55     typedef unsigned phi_arg_set_t;
  56
  57     /* Return true if the argument is an expression of interest.  */
  58     virtual bool operator()(tree) = 0;
  59     /* Return a bitset of PHI arguments of interest.  By default returns
  60        bitset with a bit set for each argument.  Should be called in
  61        the overriden function first and, if nonzero, the result then
  62        refined as appropriate.  */
  63     virtual phi_arg_set_t phi_arg_set (gphi *);
  64
  65     /* Maximum number of PHI arguments supported by phi_arg_set().  */
  66     static constexpr unsigned max_phi_args =
  67       sizeof (phi_arg_set_t) * CHAR_BIT;
  68   };
  69
  70   /* Construct with the specified EVAL object.  */
  71   predicate (func_t &eval)
  72     : m_preds (vNULL), m_eval (eval), m_use_expr () { }
  73
  74   /* Copy.  */
  75   predicate (const predicate &rhs)
  76     : m_preds (vNULL), m_eval (rhs.m_eval), m_use_expr ()
  77     {
  78       *this = rhs;
  79     }
  80
  81   predicate (basic_block, basic_block, func_t &);
  82
  83   ~predicate ();
  84
  85   /* Assign.  */
  86   predicate& operator= (const predicate &);
  87
  88   bool is_empty () const
  89   {
  90     return m_preds.is_empty ();
  91   }
  92
  93   const pred_chain_union chain () const
  94   {
  95     return m_preds;
  96   }
  97
  98   /* Return true if the use by a statement in the basic block of
  99      a PHI operand is ruled out (i.e., guarded) by *THIS.  */
 100   bool is_use_guarded (gimple *, basic_block, gphi *, unsigned);
 101
 102   void init_from_control_deps (const vec<edge> *, unsigned);
 103
 104   void dump (gimple *, const char *) const;
 105
 106   void normalize (gimple * = NULL, bool = false);
 107   void simplify (gimple * = NULL, bool = false);
 108
 109   bool is_use_guarded (gimple *, basic_block, gphi *, unsigned,
 110                        hash_set<gphi *> *);
 111
 112   /* Return the predicate expression guarding the definition of
 113      the interesting variable, optionally inverted.  */
 114   tree def_expr (bool = false) const;
 115   /* Return the predicate expression guarding the use of the interesting
 116      variable.  */
 117   tree use_expr () const;
 118
 119   tree expr (bool = false) const;
 120
 121 private:
 122   bool includes (const pred_chain &) const;
 123   bool superset_of (const predicate &) const;
 124   bool overlap (gphi *, unsigned, hash_set<gphi *> *);
 125   bool use_cannot_happen (gphi *, unsigned);
 126
 127   bool init_from_phi_def (gphi *);
 128
 129   void push_pred (const pred_info &);
 130
 131   /* Normalization functions.  */
 132   void normalize (pred_chain *, pred_info, tree_code, pred_chain *,
 133                   hash_set<tree> *);
 134
 135   void normalize (const pred_info &);
 136   void normalize (const pred_chain &);
 137
 138   /* Simplification functions.  */
 139   bool simplify_2 ();
 140   bool simplify_3 ();
 141   bool simplify_4 ();
 142
 143 private:
 144   /* Representation of the predicate expression(s).  */
 145   pred_chain_union m_preds;
 146   /* Callback to evaluate an operand.  Return true if it's interesting.  */
 147   func_t &m_eval;
 148   /* The predicate expression guarding the use of the interesting
 149      variable.  */
 150   tree m_use_expr;
 151 };
 152
 153 /* Bit mask handling macros.  */
 154 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
 155 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
 156 #define MASK_EMPTY(mask) (mask == 0)
 157
 158 #endif // GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED