gcc/value-relation.h

   1 /* Header file for the value range relational processing.
   2    Copyright (C) 2020-2021 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_NONE 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_NONE : No relation between the 2 names.
  47 //  VREL_EMPTY : Impossible relation (ie, A < B && A > B produces VREL_EMPTY.
  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, are 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_NONE is the first
  62 // code, and all the rest are contiguous.
  63
  64 typedef enum tree_code relation_kind;
  65
  66 #define VREL_NONE               TRUTH_NOT_EXPR
  67 #define VREL_EMPTY              LTGT_EXPR
  68
  69 // General relation kind transformations.
  70 relation_kind relation_union (relation_kind r1, relation_kind r2);
  71 relation_kind relation_intersect (relation_kind r1, relation_kind r2);
  72 relation_kind relation_negate (relation_kind r);
  73 relation_kind relation_swap (relation_kind r);
  74 void print_relation (FILE *f, relation_kind rel);
  75
  76 // Declared internally in value-relation.cc
  77 class equiv_chain;
  78
  79 // The equivalency oracle maintains equivalencies using the dominator tree.
  80 // Equivalencies apply to an entire basic block.  Equivalencies on edges
  81 // can be represented only on edges whose destination is a single-pred block,
  82 // and the equivalence is simply applied to that succesor block.
  83
  84 class equiv_oracle
  85 {
  86 public:
  87   equiv_oracle ();
  88   ~equiv_oracle ();
  89
  90   const_bitmap equiv_set (tree ssa, basic_block bb) const;
  91   void register_equiv (basic_block bb, tree ssa1, tree ssa2);
  92
  93   void dump (FILE *f, basic_block bb) const;
  94   void dump (FILE *f) const;
  95
  96 protected:
  97   bitmap_obstack m_bitmaps;
  98   struct obstack m_chain_obstack;
  99 private:
 100   bitmap m_equiv_set;   // Index by ssa-name. true if an equivalence exists.
 101   vec <equiv_chain *> m_equiv;  // Index by BB.  list of equivalences.
 102
 103   void limit_check (basic_block bb = NULL);
 104   equiv_chain *find_equiv_block (unsigned ssa, int bb) const;
 105   equiv_chain *find_equiv_dom (tree name, basic_block bb) const;
 106
 107   bitmap register_equiv (basic_block bb, unsigned v, equiv_chain *equiv_1);
 108   bitmap register_equiv (basic_block bb, equiv_chain *equiv_1,
 109                          equiv_chain *equiv_2);
 110
 111 };
 112
 113 // Summary block header for relations.
 114
 115 class relation_chain_head
 116 {
 117 public:
 118   bitmap m_names;               // ssa_names with relations in this block.
 119   class relation_chain *m_head; // List of relations in block.
 120 };
 121
 122 // A relation oracle maintains a set of relations between ssa_names using the
 123 // dominator tree structures.  Equivalencies are considered a subset of
 124 // a general relation and maintained by an equivalence oracle by transparently
 125 // passing any EQ_EXPR relations to it.
 126 // Relations are handled at the basic block level.  All relations apply to
 127 // an entire block, and are thus kept in a summary index by block.
 128 // Similar to the equivalence oracle, edges are handled by applying the
 129 // relation to the destination block of the edge, but ONLY if that block
 130 // has a single successor.  For now.
 131
 132 class relation_oracle : public equiv_oracle
 133 {
 134 public:
 135   relation_oracle ();
 136   ~relation_oracle ();
 137
 138   void register_relation (gimple *stmt, relation_kind k, tree op1, tree op2);
 139   void register_relation (edge e, relation_kind k, tree op1, tree op2);
 140
 141   relation_kind query_relation (basic_block bb, tree ssa1, tree ssa2);
 142
 143   void dump (FILE *f, basic_block bb) const;
 144   void dump (FILE *f) const;
 145 private:
 146   bitmap m_tmp;
 147   bitmap m_relation_set;  // Index by ssa-name. True if a relation exists
 148   vec <relation_chain_head> m_relations;  // Index by BB, list of relations.
 149   relation_kind find_relation_block (unsigned bb, const_bitmap b1,
 150                                      const_bitmap b2);
 151   relation_kind find_relation_dom (basic_block bb, const_bitmap b1,
 152                                    const_bitmap b2);
 153   relation_kind find_relation_block (int bb, unsigned v1, unsigned v2,
 154                                      relation_chain **obj = NULL);
 155   relation_kind find_relation_dom (basic_block bb, unsigned v1, unsigned v2);
 156   void register_relation (basic_block bb, relation_kind k, tree op1, tree op2);
 157 };
 158
 159 #endif  /* GCC_VALUE_RELATION_H */