gcc/value-relation.h

   1 /* Header file for the value range relational processing.
   2    Copyright (C) 2020-2022 Free Software Foundation, Inc.
   3    Contributed by Andrew MacLeod <amacleod@redhat.com>
   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 #ifndef GCC_VALUE_RELATION_H
  22 #define GCC_VALUE_RELATION_H
  23
  24
  25 // This file provides access to a relation oracle which can be used to
  26 // maintain and query relations and equivalences between SSA_NAMES.
  27 //
  28 // The general range_query object provided in value-query.h provides
  29 // access to an oracle, if one is available, via the oracle() method.
  30 // Thre are also a couple of access routines provided, which even if there is
  31 // no oracle, will return the default VREL_VARYING no relation.
  32 //
  33 // Typically, when a ranger object is active, there will be an oracle, and
  34 // any information available can be directly queried.  Ranger also sets and
  35 // utilizes the relation information to enhance it's range calculations, this
  36 // is totally transparent to the client, and they are free to make queries.
  37 //
  38 //
  39 // relation_kind is a typedef of enum tree_code, but has restricted range
  40 // and a couple of extra values.
  41 //
  42 // A query is made requesting the relation between SSA1 and SSA@ in a basic
  43 // block, or on an edge, the possible return values are:
  44 //
  45 //  EQ_EXPR, NE_EXPR, LT_EXPR, LE_EXPR, GT_EXPR, and GE_EXPR mean the same.
  46 //  VREL_VARYING : No relation between the 2 names.
  47 //  VREL_UNDEFINED : Impossible relation (ie, A < B && A > B)
  48 //
  49 // The oracle maintains EQ_EXPR relations with equivalency sets, so if a
  50 // relation comes back EQ_EXPR, it is also possible to query the set of
  51 // equivlaencies.  These are basically bitmaps over ssa_names.
  52 //
  53 // Relations are maintained via the dominace trees and are optimized assuming
  54 // they are registered in dominance order.   When a new relation is added, it
  55 // is intersected with whatever existing relation exists in the dominance tree
  56 // and registered at the specified block.
  57
  58
  59 // Rather than introduce a new enumerated type for relations, we can use the
  60 // existing tree_codes for relations, plus add a couple of #defines for
  61 // the other cases.  These codes are arranged such that VREL_VARYING is the
  62 // first code, and all the rest are contiguous.
  63
  64 typedef enum relation_kind_t
  65 {
  66   VREL_VARYING = 0,     // No known relation,  AKA varying.
  67   VREL_UNDEFINED,       // Impossible relation, ie (r1 < r2) && (r2 > r1)
  68   VREL_LT,              // r1 < r2
  69   VREL_LE,              // r1 <= r2
  70   VREL_GT,              // r1 > r2
  71   VREL_GE,              // r1 >= r2
  72   VREL_EQ,              // r1 == r2
  73   VREL_NE               // r1 != r2
  74 } relation_kind;
  75
  76 // General relation kind transformations.
  77 relation_kind relation_union (relation_kind r1, relation_kind r2);
  78 relation_kind relation_intersect (relation_kind r1, relation_kind r2);
  79 relation_kind relation_negate (relation_kind r);
  80 relation_kind relation_swap (relation_kind r);
  81 inline bool relation_lt_le_gt_ge_p (relation_kind r)
  82                                     { return (r >= VREL_LT && r <= VREL_GE); }
  83 void print_relation (FILE *f, relation_kind rel);
  84
  85 class relation_oracle
  86 {
  87 public:
  88   virtual ~relation_oracle () { }
  89   // register a relation between 2 ssa names at a stmt.
  90   void register_stmt (gimple *, relation_kind, tree, tree);
  91   // register a relation between 2 ssa names on an edge.
  92   void register_edge (edge, relation_kind, tree, tree);
  93
  94   // Return equivalency set for an SSA name in a basic block.
  95   virtual const_bitmap equiv_set (tree, basic_block) = 0;
  96   // register a relation between 2 ssa names in a basic block.
  97   virtual void register_relation (basic_block, relation_kind, tree, tree) = 0;
  98   // Query for a relation between two ssa names in a basic block.
  99   virtual relation_kind query_relation (basic_block, tree, tree) = 0;
 100
 101   relation_kind validate_relation (relation_kind, tree, tree);
 102   relation_kind validate_relation (relation_kind, vrange &, vrange &);
 103
 104   virtual void dump (FILE *, basic_block) const = 0;
 105   virtual void dump (FILE *) const = 0;
 106   void debug () const;
 107 protected:
 108   void valid_equivs (bitmap b, const_bitmap equivs, basic_block bb);
 109   // Query for a relation between two equivalency sets in a basic block.
 110   virtual relation_kind query_relation (basic_block, const_bitmap,
 111                                         const_bitmap) = 0;
 112   friend class path_oracle;
 113 };
 114
 115 // This class represents an equivalency set, and contains a link to the next
 116 // one in the list to be searched.
 117
 118 class equiv_chain
 119 {
 120 public:
 121   bitmap m_names;               // ssa-names in equiv set.
 122   basic_block m_bb;             // Block this belongs to
 123   equiv_chain *m_next;          // Next in block list.
 124   void dump (FILE *f) const;    // Show names in this list.
 125   equiv_chain *find (unsigned ssa);
 126 };
 127
 128 // The equivalency oracle maintains equivalencies using the dominator tree.
 129 // Equivalencies apply to an entire basic block.  Equivalencies on edges
 130 // can be represented only on edges whose destination is a single-pred block,
 131 // and the equivalence is simply applied to that succesor block.
 132
 133 class equiv_oracle : public relation_oracle
 134 {
 135 public:
 136   equiv_oracle ();
 137   ~equiv_oracle ();
 138
 139   const_bitmap equiv_set (tree ssa, basic_block bb) final override;
 140   void register_relation (basic_block bb, relation_kind k, tree ssa1,
 141                           tree ssa2) override;
 142
 143   relation_kind query_relation (basic_block, tree, tree) override;
 144   relation_kind query_relation (basic_block, const_bitmap, const_bitmap)
 145     override;
 146   void dump (FILE *f, basic_block bb) const override;
 147   void dump (FILE *f) const override;
 148
 149 protected:
 150   bitmap_obstack m_bitmaps;
 151   struct obstack m_chain_obstack;
 152 private:
 153   bitmap m_equiv_set;   // Index by ssa-name. true if an equivalence exists.
 154   vec <equiv_chain *> m_equiv;  // Index by BB.  list of equivalences.
 155   vec <bitmap> m_self_equiv;  // Index by ssa-name, self equivalency set.
 156
 157   void limit_check (basic_block bb = NULL);
 158   equiv_chain *find_equiv_block (unsigned ssa, int bb) const;
 159   equiv_chain *find_equiv_dom (tree name, basic_block bb) const;
 160
 161   bitmap register_equiv (basic_block bb, unsigned v, equiv_chain *equiv_1);
 162   bitmap register_equiv (basic_block bb, equiv_chain *equiv_1,
 163                          equiv_chain *equiv_2);
 164   void register_initial_def (tree ssa);
 165   void add_equiv_to_block (basic_block bb, bitmap equiv);
 166 };
 167
 168 // Summary block header for relations.
 169
 170 class relation_chain_head
 171 {
 172 public:
 173   bitmap m_names;               // ssa_names with relations in this block.
 174   class relation_chain *m_head; // List of relations in block.
 175   int m_num_relations;          // Number of relations in block.
 176   relation_kind find_relation (const_bitmap b1, const_bitmap b2) const;
 177 };
 178
 179 // A relation oracle maintains a set of relations between ssa_names using the
 180 // dominator tree structures.  Equivalencies are considered a subset of
 181 // a general relation and maintained by an equivalence oracle by transparently
 182 // passing any EQ_EXPR relations to it.
 183 // Relations are handled at the basic block level.  All relations apply to
 184 // an entire block, and are thus kept in a summary index by block.
 185 // Similar to the equivalence oracle, edges are handled by applying the
 186 // relation to the destination block of the edge, but ONLY if that block
 187 // has a single successor.  For now.
 188
 189 class dom_oracle : public equiv_oracle
 190 {
 191 public:
 192   dom_oracle ();
 193   ~dom_oracle ();
 194
 195   void register_relation (basic_block bb, relation_kind k, tree op1, tree op2)
 196     final override;
 197
 198   relation_kind query_relation (basic_block bb, tree ssa1, tree ssa2)
 199     final override;
 200   relation_kind query_relation (basic_block bb, const_bitmap b1,
 201                                 const_bitmap b2) final override;
 202
 203   void dump (FILE *f, basic_block bb) const final override;
 204   void dump (FILE *f) const final override;
 205 private:
 206   bitmap m_tmp, m_tmp2;
 207   bitmap m_relation_set;  // Index by ssa-name. True if a relation exists
 208   vec <relation_chain_head> m_relations;  // Index by BB, list of relations.
 209   relation_kind find_relation_block (unsigned bb, const_bitmap b1,
 210                                      const_bitmap b2) const;
 211   relation_kind find_relation_block (int bb, unsigned v1, unsigned v2,
 212                                      relation_chain **obj = NULL) const;
 213   relation_kind find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const;
 214   relation_chain *set_one_relation (basic_block bb, relation_kind k, tree op1,
 215                                     tree op2);
 216   void register_transitives (basic_block, const class value_relation &);
 217
 218 };
 219
 220 // A path_oracle implements relations in a list.  The only sense of ordering
 221 // is the latest registered relation is the first found during a search.
 222 // It can be constructed with an optional "root" oracle which will be used
 223 // to look up any relations not found in the list.
 224 // This allows the client to walk paths starting at some block and register
 225 // and query relations along that path, ignoring other edges.
 226 //
 227 // For registering a relation, a query if made of the root oracle if there is
 228 // any known relationship at block BB, and it is combined with this new
 229 // relation and entered in the list.
 230 //
 231 // Queries are resolved by looking first in the list, and only if nothing is
 232 // found is the root oracle queried at block BB.
 233 //
 234 // reset_path is used to clear all locally registered paths to initial state.
 235
 236 class path_oracle : public relation_oracle
 237 {
 238 public:
 239   path_oracle (relation_oracle *oracle = NULL);
 240   ~path_oracle ();
 241   const_bitmap equiv_set (tree, basic_block) final override;
 242   void register_relation (basic_block, relation_kind, tree, tree) final override;
 243   void killing_def (tree);
 244   relation_kind query_relation (basic_block, tree, tree) final override;
 245   relation_kind query_relation (basic_block, const_bitmap, const_bitmap)
 246     final override;
 247   void reset_path (relation_oracle *oracle = NULL);
 248   void set_root_oracle (relation_oracle *oracle) { m_root = oracle; }
 249   void dump (FILE *, basic_block) const final override;
 250   void dump (FILE *) const final override;
 251 private:
 252   void register_equiv (basic_block bb, tree ssa1, tree ssa2);
 253   equiv_chain m_equiv;
 254   relation_chain_head m_relations;
 255   relation_oracle *m_root;
 256   bitmap m_killed_defs;
 257
 258   bitmap_obstack m_bitmaps;
 259   struct obstack m_chain_obstack;
 260 };
 261
 262 // The value-relation class is used to encapsulate the represention of an
 263 // individual relation between 2 ssa-names, and to facilitate operating on
 264 // the relation.
 265
 266 class value_relation
 267 {
 268 public:
 269   value_relation ();
 270   value_relation (relation_kind kind, tree n1, tree n2);
 271   void set_relation (relation_kind kind, tree n1, tree n2);
 272
 273   inline relation_kind kind () const { return related; }
 274   inline tree op1 () const { return name1; }
 275   inline tree op2 () const { return name2; }
 276
 277   bool union_ (value_relation &p);
 278   bool intersect (value_relation &p);
 279   void negate ();
 280   bool apply_transitive (const value_relation &rel);
 281
 282   void dump (FILE *f) const;
 283 private:
 284   relation_kind related;
 285   tree name1, name2;
 286 };
 287
 288 // Set relation R between ssa_name N1 and N2.
 289
 290 inline void
 291 value_relation::set_relation (relation_kind r, tree n1, tree n2)
 292 {
 293   gcc_checking_assert (TREE_CODE (n1) == SSA_NAME
 294                        && TREE_CODE (n2) == SSA_NAME);
 295   related = r;
 296   name1 = n1;
 297   name2 = n2;
 298 }
 299
 300 // Default constructor.
 301
 302 inline
 303 value_relation::value_relation ()
 304 {
 305   related = VREL_VARYING;
 306   name1 = NULL_TREE;
 307   name2 = NULL_TREE;
 308 }
 309
 310 // Constructor for relation R between SSA version N1 nd N2.
 311
 312 inline
 313 value_relation::value_relation (relation_kind kind, tree n1, tree n2)
 314 {
 315   set_relation (kind, n1, n2);
 316 }
 317
 318 #endif  /* GCC_VALUE_RELATION_H */