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 void print_relation (FILE *f, relation_kind rel);
  82
  83 class relation_oracle
  84 {
  85 public:
  86   virtual ~relation_oracle () { }
  87   // register a relation between 2 ssa names at a stmt.
  88   void register_stmt (gimple *, relation_kind, tree, tree);
  89   // register a relation between 2 ssa names on an edge.
  90   void register_edge (edge, relation_kind, tree, tree);
  91
  92   // Return equivalency set for an SSA name in a basic block.
  93   virtual const_bitmap equiv_set (tree, basic_block) = 0;
  94   // register a relation between 2 ssa names in a basic block.
  95   virtual void register_relation (basic_block, relation_kind, tree, tree) = 0;
  96   // Query for a relation between two ssa names in a basic block.
  97   virtual relation_kind query_relation (basic_block, tree, tree) = 0;
  98   // Query for a relation between two equivalency stes in a basic block.
  99   virtual relation_kind query_relation (basic_block, const_bitmap,
 100                                         const_bitmap) = 0;
 101
 102   virtual void dump (FILE *, basic_block) const = 0;
 103   virtual void dump (FILE *) const = 0;
 104   void debug () const;
 105 protected:
 106   void valid_equivs (bitmap b, const_bitmap equivs, basic_block bb);
 107 };
 108
 109 // This class represents an equivalency set, and contains a link to the next
 110 // one in the list to be searched.
 111
 112 class equiv_chain
 113 {
 114 public:
 115   bitmap m_names;               // ssa-names in equiv set.
 116   basic_block m_bb;             // Block this belongs to
 117   equiv_chain *m_next;          // Next in block list.
 118   void dump (FILE *f) const;    // Show names in this list.
 119   equiv_chain *find (unsigned ssa);
 120 };
 121
 122 // The equivalency oracle maintains equivalencies using the dominator tree.
 123 // Equivalencies apply to an entire basic block.  Equivalencies on edges
 124 // can be represented only on edges whose destination is a single-pred block,
 125 // and the equivalence is simply applied to that succesor block.
 126
 127 class equiv_oracle : public relation_oracle
 128 {
 129 public:
 130   equiv_oracle ();
 131   ~equiv_oracle ();
 132
 133   const_bitmap equiv_set (tree ssa, basic_block bb);
 134   void register_relation (basic_block bb, relation_kind k, tree ssa1,
 135                           tree ssa2);
 136
 137   relation_kind query_relation (basic_block, tree, tree);
 138   relation_kind query_relation (basic_block, const_bitmap, const_bitmap);
 139   void dump (FILE *f, basic_block bb) const;
 140   void dump (FILE *f) const;
 141
 142 protected:
 143   bitmap_obstack m_bitmaps;
 144   struct obstack m_chain_obstack;
 145 private:
 146   bitmap m_equiv_set;   // Index by ssa-name. true if an equivalence exists.
 147   vec <equiv_chain *> m_equiv;  // Index by BB.  list of equivalences.
 148   vec <bitmap> m_self_equiv;  // Index by ssa-name, self equivalency set.
 149
 150   void limit_check (basic_block bb = NULL);
 151   equiv_chain *find_equiv_block (unsigned ssa, int bb) const;
 152   equiv_chain *find_equiv_dom (tree name, basic_block bb) const;
 153
 154   bitmap register_equiv (basic_block bb, unsigned v, equiv_chain *equiv_1);
 155   bitmap register_equiv (basic_block bb, equiv_chain *equiv_1,
 156                          equiv_chain *equiv_2);
 157   void register_initial_def (tree ssa);
 158   void add_equiv_to_block (basic_block bb, bitmap equiv);
 159 };
 160
 161 // Summary block header for relations.
 162
 163 class relation_chain_head
 164 {
 165 public:
 166   bitmap m_names;               // ssa_names with relations in this block.
 167   class relation_chain *m_head; // List of relations in block.
 168   int m_num_relations;          // Number of relations in block.
 169   relation_kind find_relation (const_bitmap b1, const_bitmap b2) const;
 170 };
 171
 172 // A relation oracle maintains a set of relations between ssa_names using the
 173 // dominator tree structures.  Equivalencies are considered a subset of
 174 // a general relation and maintained by an equivalence oracle by transparently
 175 // passing any EQ_EXPR relations to it.
 176 // Relations are handled at the basic block level.  All relations apply to
 177 // an entire block, and are thus kept in a summary index by block.
 178 // Similar to the equivalence oracle, edges are handled by applying the
 179 // relation to the destination block of the edge, but ONLY if that block
 180 // has a single successor.  For now.
 181
 182 class dom_oracle : public equiv_oracle
 183 {
 184 public:
 185   dom_oracle ();
 186   ~dom_oracle ();
 187
 188   void register_relation (basic_block bb, relation_kind k, tree op1, tree op2);
 189
 190   relation_kind query_relation (basic_block bb, tree ssa1, tree ssa2);
 191   relation_kind query_relation (basic_block bb, const_bitmap b1,
 192                                    const_bitmap b2);
 193
 194   void dump (FILE *f, basic_block bb) const;
 195   void dump (FILE *f) const;
 196 private:
 197   bitmap m_tmp, m_tmp2;
 198   bitmap m_relation_set;  // Index by ssa-name. True if a relation exists
 199   vec <relation_chain_head> m_relations;  // Index by BB, list of relations.
 200   relation_kind find_relation_block (unsigned bb, const_bitmap b1,
 201                                      const_bitmap b2) const;
 202   relation_kind find_relation_block (int bb, unsigned v1, unsigned v2,
 203                                      relation_chain **obj = NULL) const;
 204   relation_kind find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const;
 205   relation_chain *set_one_relation (basic_block bb, relation_kind k, tree op1,
 206                                     tree op2);
 207   void register_transitives (basic_block, const class value_relation &);
 208
 209 };
 210
 211 // A path_oracle implements relations in a list.  The only sense of ordering
 212 // is the latest registered relation is the first found during a search.
 213 // It can be constructed with an optional "root" oracle which will be used
 214 // to look up any relations not found in the list.
 215 // This allows the client to walk paths starting at some block and register
 216 // and query relations along that path, ignoring other edges.
 217 //
 218 // For registering a relation, a query if made of the root oracle if there is
 219 // any known relationship at block BB, and it is combined with this new
 220 // relation and entered in the list.
 221 //
 222 // Queries are resolved by looking first in the list, and only if nothing is
 223 // found is the root oracle queried at block BB.
 224 //
 225 // reset_path is used to clear all locally registered paths to initial state.
 226
 227 class path_oracle : public relation_oracle
 228 {
 229 public:
 230   path_oracle (relation_oracle *oracle = NULL);
 231   ~path_oracle ();
 232   const_bitmap equiv_set (tree, basic_block);
 233   void register_relation (basic_block, relation_kind, tree, tree);
 234   void killing_def (tree);
 235   relation_kind query_relation (basic_block, tree, tree);
 236   relation_kind query_relation (basic_block, const_bitmap, const_bitmap);
 237   void reset_path ();
 238   void set_root_oracle (relation_oracle *oracle) { m_root = oracle; }
 239   void dump (FILE *, basic_block) const;
 240   void dump (FILE *) const;
 241 private:
 242   void register_equiv (basic_block bb, tree ssa1, tree ssa2);
 243   equiv_chain m_equiv;
 244   relation_chain_head m_relations;
 245   relation_oracle *m_root;
 246   bitmap m_killed_defs;
 247
 248   bitmap_obstack m_bitmaps;
 249   struct obstack m_chain_obstack;
 250 };
 251 #endif  /* GCC_VALUE_RELATION_H */