gcc/analyzer/constraint-manager.h

   1 /* Tracking equivalence classes and constraints at a point on an execution path.
   2    Copyright (C) 2019-2021 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   json::object *to_json () const;
  92
  93   /* An equivalence class can contain multiple constants (e.g. multiple
  94      different zeroes, for different types); these are just for the last
  95      constant added.  */
  96   tree m_constant;
  97   const svalue *m_cst_sval;
  98
  99   // TODO: should this be a set rather than a vec?
 100   auto_vec<const svalue *> m_vars;
 101 };
 102
 103 /* The various kinds of constraint.  */
 104
 105 enum constraint_op
 106 {
 107   CONSTRAINT_NE,
 108   CONSTRAINT_LT,
 109   CONSTRAINT_LE
 110 };
 111
 112 const char *constraint_op_code (enum constraint_op c_op);
 113
 114 /* An ID for an equiv_class within a constraint_manager.  Internally, this
 115    is an index into a vector of equiv_class * within the constraint_manager.  */
 116
 117 class equiv_class_id
 118 {
 119 public:
 120   static equiv_class_id null () { return equiv_class_id (-1); }
 121
 122   equiv_class_id (unsigned idx) : m_idx (idx) {}
 123   const equiv_class &get_obj (const constraint_manager &cm) const;
 124   equiv_class &get_obj (constraint_manager &cm) const;
 125
 126   bool operator== (const equiv_class_id &other) const
 127   {
 128     return m_idx == other.m_idx;
 129   }
 130   bool operator!= (const equiv_class_id &other) const
 131   {
 132     return m_idx != other.m_idx;
 133   }
 134
 135   bool null_p () const { return m_idx == -1; }
 136
 137   static equiv_class_id from_int (int idx) { return equiv_class_id (idx); }
 138   int as_int () const { return m_idx; }
 139
 140   void print (pretty_printer *pp) const;
 141
 142   void update_for_removal (equiv_class_id other)
 143   {
 144     if (m_idx > other.m_idx)
 145       m_idx--;
 146   }
 147
 148   int m_idx;
 149 };
 150
 151 /* A relationship between two equivalence classes in a constraint_manager.  */
 152
 153 class constraint
 154 {
 155  public:
 156   constraint (equiv_class_id lhs, enum constraint_op c_op, equiv_class_id rhs)
 157   : m_lhs (lhs), m_op (c_op), m_rhs (rhs)
 158   {
 159     gcc_assert (!lhs.null_p ());
 160     gcc_assert (!rhs.null_p ());
 161   }
 162
 163   void print (pretty_printer *pp, const constraint_manager &cm) const;
 164
 165   json::object *to_json () const;
 166
 167   hashval_t hash () const;
 168   bool operator== (const constraint &other) const;
 169
 170   /* Is this an ordering, rather than a "!=".  */
 171   bool is_ordering_p () const
 172   {
 173     return m_op != CONSTRAINT_NE;
 174   }
 175
 176   bool implied_by (const constraint &other,
 177                    const constraint_manager &cm) const;
 178
 179   equiv_class_id m_lhs;
 180   enum constraint_op m_op;
 181   equiv_class_id m_rhs;
 182 };
 183
 184 /* An abstract base class for use with constraint_manager::for_each_fact.  */
 185
 186 class fact_visitor
 187 {
 188  public:
 189   virtual ~fact_visitor () {}
 190   virtual void on_fact (const svalue *lhs,
 191                         enum tree_code,
 192                         const svalue *rhs) = 0;
 193 };
 194
 195 /* A collection of equivalence classes and constraints on them.
 196
 197    Given N svalues, this can be thought of as representing a subset of
 198    N-dimensional space.  When we call add_constraint,
 199    we are effectively taking an intersection with that constraint.  */
 200
 201 class constraint_manager
 202 {
 203 public:
 204   constraint_manager (region_model_manager *mgr) : m_mgr (mgr) {}
 205   constraint_manager (const constraint_manager &other);
 206   virtual ~constraint_manager () {}
 207
 208   constraint_manager& operator= (const constraint_manager &other);
 209
 210   hashval_t hash () const;
 211   bool operator== (const constraint_manager &other) const;
 212   bool operator!= (const constraint_manager &other) const
 213   {
 214     return !(*this == other);
 215   }
 216
 217   void print (pretty_printer *pp) const;
 218   void dump_to_pp (pretty_printer *pp, bool multiline) const;
 219   void dump (FILE *fp) const;
 220   void dump () const;
 221
 222   json::object *to_json () const;
 223
 224   const equiv_class &get_equiv_class_by_index (unsigned idx) const
 225   {
 226     return *m_equiv_classes[idx];
 227   }
 228   equiv_class &get_equiv_class_by_index (unsigned idx)
 229   {
 230     return *m_equiv_classes[idx];
 231   }
 232
 233   equiv_class &get_equiv_class (const svalue *sval)
 234   {
 235     equiv_class_id ec_id = get_or_add_equiv_class (sval);
 236     return ec_id.get_obj (*this);
 237   }
 238
 239   bool add_constraint (const svalue *lhs,
 240                        enum tree_code op,
 241                        const svalue *rhs);
 242
 243   bool add_constraint (equiv_class_id lhs_ec_id,
 244                        enum tree_code op,
 245                        equiv_class_id rhs_ec_id);
 246
 247   void add_unknown_constraint (equiv_class_id lhs_ec_id,
 248                                enum tree_code op,
 249                                equiv_class_id rhs_ec_id);
 250
 251   bool get_equiv_class_by_svalue (const svalue *sval,
 252                                     equiv_class_id *out) const;
 253   equiv_class_id get_or_add_equiv_class (const svalue *sval);
 254   tristate eval_condition (equiv_class_id lhs,
 255                            enum tree_code op,
 256                            equiv_class_id rhs) const;
 257   tristate eval_condition (equiv_class_id lhs_ec,
 258                            enum tree_code op,
 259                            tree rhs_const) const;
 260   tristate eval_condition (const svalue *lhs,
 261                            enum tree_code op,
 262                            const svalue *rhs) const;
 263   range get_ec_bounds (equiv_class_id ec_id) const;
 264
 265   /* PurgeCriteria should have:
 266      bool should_purge_p (const svalue *sval) const.  */
 267   template <typename PurgeCriteria>
 268   void purge (const PurgeCriteria &p, purge_stats *stats);
 269
 270   void on_liveness_change (const svalue_set &live_svalues,
 271                            const region_model *model);
 272
 273   void canonicalize ();
 274
 275   static void merge (const constraint_manager &cm_a,
 276                      const constraint_manager &cm_b,
 277                      constraint_manager *out);
 278
 279   void for_each_fact (fact_visitor *) const;
 280
 281   void validate () const;
 282
 283   auto_delete_vec<equiv_class> m_equiv_classes;
 284   auto_vec<constraint> m_constraints;
 285
 286  private:
 287   void add_constraint_internal (equiv_class_id lhs_id,
 288                                 enum constraint_op c_op,
 289                                 equiv_class_id rhs_id);
 290
 291   region_model_manager *m_mgr;
 292 };
 293
 294 } // namespace ana
 295
 296 #endif /* GCC_ANALYZER_CONSTRAINT_MANAGER_H */