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