gcc/analyzer/constraint-manager.h

   1 /* Tracking equivalence classes and constraints at a point on an execution path.
   2    Copyright (C) 2019-2020 Free Software Foundation, Inc.
   3    Contributed by David Malcolm <dmalcolm@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 General Public License 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 #ifndef GCC_ANALYZER_CONSTRAINT_MANAGER_H
  22 #define GCC_ANALYZER_CONSTRAINT_MANAGER_H
  23
  24 namespace ana {
  25
  26 class constraint_manager;
  27
  28 /* One of the end-points of a range.  */
  29
  30 struct bound
  31 {
  32   bound () : m_constant (NULL_TREE), m_closed (false) {}
  33   bound (tree constant, bool closed)
  34   : m_constant (constant), m_closed (closed) {}
  35
  36   void ensure_closed (bool is_upper);
  37
  38   const char * get_relation_as_str () const;
  39
  40   tree m_constant;
  41   bool m_closed;
  42 };
  43
  44 /* A range of values, used for determining if a value has been
  45    constrained to just one possible constant value.  */
  46
  47 struct range
  48 {
  49   range () : m_lower_bound (), m_upper_bound () {}
  50   range (const bound &lower, const bound &upper)
  51   : m_lower_bound (lower), m_upper_bound (upper) {}
  52
  53   void dump_to_pp (pretty_printer *pp) const;
  54   void dump () const;
  55
  56   tree constrained_to_single_element ();
  57
  58   tristate eval_condition (enum tree_code op,
  59                            tree rhs_const) const;
  60   bool below_lower_bound (tree rhs_const) const;
  61   bool above_upper_bound (tree rhs_const) const;
  62
  63   bound m_lower_bound;
  64   bound m_upper_bound;
  65 };
  66
  67 /* An equivalence class within a constraint manager: a set of
  68    svalues that are known to all be equal to each other,
  69    together with an optional tree constant that they are equal to.  */
  70
  71 class equiv_class
  72 {
  73 public:
  74   equiv_class ();
  75   equiv_class (const equiv_class &other);
  76
  77   hashval_t hash () const;
  78   bool operator== (const equiv_class &other);
  79
  80   void add (const svalue *sval);
  81   bool del (const svalue *sval);
  82
  83   tree get_any_constant () const { return m_constant; }
  84
  85   const svalue *get_representative () const;
  86
  87   void canonicalize ();
  88
  89   void print (pretty_printer *pp) const;
  90
  91   /* An equivalence class can contain multiple constants (e.g. multiple
  92      different zeroes, for different types); these are just for the last
  93      constant added.  */
  94   tree m_constant;
  95   const svalue *m_cst_sval;
  96
  97   // TODO: should this be a set rather than a vec?
  98   auto_vec<const svalue *> m_vars;
  99 };
 100
 101 /* The various kinds of constraint.  */
 102
 103 enum constraint_op
 104 {
 105   CONSTRAINT_NE,
 106   CONSTRAINT_LT,
 107   CONSTRAINT_LE
 108 };
 109
 110 const char *constraint_op_code (enum constraint_op c_op);
 111
 112 /* An ID for an equiv_class within a constraint_manager.  Internally, this
 113    is an index into a vector of equiv_class * within the constraint_manager.  */
 114
 115 class equiv_class_id
 116 {
 117 public:
 118   static equiv_class_id null () { return equiv_class_id (-1); }
 119
 120   equiv_class_id (unsigned idx) : m_idx (idx) {}
 121   const equiv_class &get_obj (const constraint_manager &cm) const;
 122   equiv_class &get_obj (constraint_manager &cm) const;
 123
 124   bool operator== (const equiv_class_id &other) const
 125   {
 126     return m_idx == other.m_idx;
 127   }
 128   bool operator!= (const equiv_class_id &other) const
 129   {
 130     return m_idx != other.m_idx;
 131   }
 132
 133   bool null_p () const { return m_idx == -1; }
 134
 135   static equiv_class_id from_int (int idx) { return equiv_class_id (idx); }
 136   int as_int () const { return m_idx; }
 137
 138   void print (pretty_printer *pp) const;
 139
 140   void update_for_removal (equiv_class_id other)
 141   {
 142     if (m_idx > other.m_idx)
 143       m_idx--;
 144   }
 145
 146   int m_idx;
 147 };
 148
 149 /* A relationship between two equivalence classes in a constraint_manager.  */
 150
 151 class constraint
 152 {
 153  public:
 154   constraint (equiv_class_id lhs, enum constraint_op c_op, equiv_class_id rhs)
 155   : m_lhs (lhs), m_op (c_op), m_rhs (rhs)
 156   {
 157     gcc_assert (!lhs.null_p ());
 158     gcc_assert (!rhs.null_p ());
 159   }
 160
 161   void print (pretty_printer *pp, const constraint_manager &cm) const;
 162
 163   hashval_t hash () const;
 164   bool operator== (const constraint &other) const;
 165
 166   /* Is this an ordering, rather than a "!=".  */
 167   bool is_ordering_p () const
 168   {
 169     return m_op != CONSTRAINT_NE;
 170   }
 171
 172   bool implied_by (const constraint &other,
 173                    const constraint_manager &cm) const;
 174
 175   equiv_class_id m_lhs;
 176   enum constraint_op m_op;
 177   equiv_class_id m_rhs;
 178 };
 179
 180 /* An abstract base class for use with constraint_manager::for_each_fact.  */
 181
 182 class fact_visitor
 183 {
 184  public:
 185   virtual ~fact_visitor () {}
 186   virtual void on_fact (const svalue *lhs,
 187                         enum tree_code,
 188                         const svalue *rhs) = 0;
 189 };
 190
 191 /* A collection of equivalence classes and constraints on them.
 192
 193    Given N svalues, this can be thought of as representing a subset of
 194    N-dimensional space.  When we call add_constraint,
 195    we are effectively taking an intersection with that constraint.  */
 196
 197 class constraint_manager
 198 {
 199 public:
 200   constraint_manager (region_model_manager *mgr) : m_mgr (mgr) {}
 201   constraint_manager (const constraint_manager &other);
 202   virtual ~constraint_manager () {}
 203
 204   constraint_manager& operator= (const constraint_manager &other);
 205
 206   hashval_t hash () const;
 207   bool operator== (const constraint_manager &other) const;
 208   bool operator!= (const constraint_manager &other) const
 209   {
 210     return !(*this == other);
 211   }
 212
 213   void print (pretty_printer *pp) const;
 214   void dump_to_pp (pretty_printer *pp, bool multiline) const;
 215   void dump (FILE *fp) const;
 216   void dump () const;
 217
 218   const equiv_class &get_equiv_class_by_index (unsigned idx) const
 219   {
 220     return *m_equiv_classes[idx];
 221   }
 222   equiv_class &get_equiv_class_by_index (unsigned idx)
 223   {
 224     return *m_equiv_classes[idx];
 225   }
 226
 227   equiv_class &get_equiv_class (const svalue *sval)
 228   {
 229     equiv_class_id ec_id = get_or_add_equiv_class (sval);
 230     return ec_id.get_obj (*this);
 231   }
 232
 233   bool add_constraint (const svalue *lhs,
 234                        enum tree_code op,
 235                        const svalue *rhs);
 236
 237   bool add_constraint (equiv_class_id lhs_ec_id,
 238                        enum tree_code op,
 239                        equiv_class_id rhs_ec_id);
 240
 241   void add_unknown_constraint (equiv_class_id lhs_ec_id,
 242                                enum tree_code op,
 243                                equiv_class_id rhs_ec_id);
 244
 245   bool get_equiv_class_by_svalue (const svalue *sval,
 246                                     equiv_class_id *out) const;
 247   equiv_class_id get_or_add_equiv_class (const svalue *sval);
 248   tristate eval_condition (equiv_class_id lhs,
 249                            enum tree_code op,
 250                            equiv_class_id rhs) const;
 251   tristate eval_condition (equiv_class_id lhs_ec,
 252                            enum tree_code op,
 253                            tree rhs_const) const;
 254   tristate eval_condition (const svalue *lhs,
 255                            enum tree_code op,
 256                            const svalue *rhs) const;
 257   range get_ec_bounds (equiv_class_id ec_id) const;
 258
 259   /* PurgeCriteria should have:
 260      bool should_purge_p (const svalue *sval) const.  */
 261   template <typename PurgeCriteria>
 262   void purge (const PurgeCriteria &p, purge_stats *stats);
 263
 264   void on_liveness_change (const svalue_set &live_svalues,
 265                            const region_model *model);
 266
 267   void canonicalize ();
 268
 269   static void merge (const constraint_manager &cm_a,
 270                      const constraint_manager &cm_b,
 271                      constraint_manager *out,
 272                      const model_merger &merger);
 273
 274   void for_each_fact (fact_visitor *) const;
 275
 276   void validate () const;
 277
 278   auto_delete_vec<equiv_class> m_equiv_classes;
 279   auto_vec<constraint> m_constraints;
 280
 281  private:
 282   void add_constraint_internal (equiv_class_id lhs_id,
 283                                 enum constraint_op c_op,
 284                                 equiv_class_id rhs_id);
 285
 286   region_model_manager *m_mgr;
 287 };
 288
 289 } // namespace ana
 290
 291 #endif /* GCC_ANALYZER_CONSTRAINT_MANAGER_H */