gcc/gimple-predicate-analysis.h

   1 /* Support for simple predicate analysis.
   2
   3    Copyright (C) 2021-2023 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
  26 /* Represents a simple Boolean predicate.  */
  27 struct pred_info
  28 {
  29   tree pred_lhs;
  30   tree pred_rhs;
  31   enum tree_code cond_code;
  32   bool invert;
  33 };
  34
  35 /* The type to represent a sequence of predicates grouped
  36    with .AND. operation.  */
  37 typedef vec<pred_info, va_heap, vl_ptr> pred_chain;
  38
  39 /* The type to represent a sequence of pred_chains grouped
  40    with .OR. operation.  */
  41 typedef vec<pred_chain, va_heap, vl_ptr> pred_chain_union;
  42
  43 /* Represents a complex Boolean predicate expression.  */
  44 class predicate
  45 {
  46  public:
  47   /* Construct with the specified EVAL object.  */
  48   predicate (bool empty_val) : m_preds (vNULL), m_cval (empty_val) { }
  49
  50   /* Copy.  */
  51   predicate (const predicate &rhs) : m_preds (vNULL) { *this = rhs; }
  52
  53   ~predicate ();
  54
  55   /* Assign.  */
  56   predicate& operator= (const predicate &);
  57
  58   bool is_empty () const
  59   {
  60     return m_preds.is_empty ();
  61   }
  62
  63   bool is_true () const
  64   {
  65     return is_empty () && m_cval;
  66   }
  67
  68   bool is_false () const
  69   {
  70     return is_empty () && !m_cval;
  71   }
  72
  73   bool empty_val () const
  74   {
  75     return m_cval;
  76   }
  77
  78   const pred_chain_union chain () const
  79   {
  80     return m_preds;
  81   }
  82
  83   void init_from_control_deps (const vec<edge> *, unsigned, bool);
  84
  85   void dump (FILE *) const;
  86   void dump (FILE *, gimple *, const char *) const;
  87   void debug () const;
  88
  89   void normalize (gimple * = NULL, bool = false);
  90   void simplify (gimple * = NULL, bool = false);
  91
  92   bool superset_of (const predicate &) const;
  93
  94 private:
  95
  96   bool includes (const pred_chain &) const;
  97   void push_pred (const pred_info &);
  98
  99   /* Normalization functions.  */
 100   void normalize (pred_chain *, pred_info, tree_code, pred_chain *,
 101                   hash_set<tree> *);
 102   void normalize (const pred_info &);
 103   void normalize (const pred_chain &);
 104
 105   /* Simplification functions.  */
 106   bool simplify_2 ();
 107   bool simplify_3 ();
 108   bool simplify_4 ();
 109
 110   /* Representation of the predicate expression(s).  The predicate is
 111      m_cval || m_preds[0] || ...  */
 112   pred_chain_union m_preds;
 113   bool m_cval;
 114 };
 115
 116 /* Represents a complex Boolean predicate expression.  */
 117 class uninit_analysis
 118 {
 119  public:
 120   /* Base function object type used to determine whether an expression
 121      is of interest.  */
 122   struct func_t
 123   {
 124     typedef unsigned phi_arg_set_t;
 125
 126     /* Return a bitset of PHI arguments of interest.  By default returns
 127        bitset with a bit set for each argument.  Should be called in
 128        the overriden function first and, if nonzero, the result then
 129        refined as appropriate.  */
 130     virtual phi_arg_set_t phi_arg_set (gphi *);
 131
 132     /* Maximum number of PHI arguments supported by phi_arg_set().  */
 133     static constexpr unsigned max_phi_args =
 134       sizeof (phi_arg_set_t) * CHAR_BIT;
 135   };
 136
 137   /* Construct with the specified EVAL object.  */
 138   uninit_analysis (func_t &eval)
 139     : m_phi_def_preds (false), m_eval (eval) { }
 140
 141   /* Copy.  */
 142   uninit_analysis (const uninit_analysis &rhs) = delete;
 143
 144   /* Assign.  */
 145   uninit_analysis& operator= (const uninit_analysis&) = delete;
 146
 147   /* Return true if the use by a statement in the basic block of
 148      a PHI operand is ruled out (i.e., guarded) by *THIS.  */
 149   bool is_use_guarded (gimple *, basic_block, gphi *, unsigned);
 150
 151 private:
 152   bool is_use_guarded (gimple *, basic_block, gphi *, unsigned,
 153                        hash_set<gphi *> *);
 154   bool prune_phi_opnds (gphi *, unsigned, gphi *, tree, tree_code,
 155                         hash_set<gphi *> *, bitmap *);
 156   bool overlap (gphi *, unsigned, hash_set<gphi *> *, const predicate &);
 157
 158   void collect_phi_def_edges (gphi *, basic_block, vec<edge> *,
 159                               hash_set<gimple *> *);
 160   bool init_from_phi_def (gphi *);
 161   bool init_use_preds (predicate &, basic_block, basic_block);
 162
 163
 164   /* Representation of the predicate expression(s).  */
 165   predicate m_phi_def_preds;
 166   /* Callback to evaluate an operand.  Return true if it's interesting.  */
 167   func_t &m_eval;
 168 };
 169
 170 /* Bit mask handling macros.  */
 171 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
 172 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
 173 #define MASK_EMPTY(mask) (mask == 0)
 174
 175 #endif // GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED