c++: new-expression is potentially constant in C++20
[official-gcc.git] / gcc / value-relation.h
blob19762d8ce2b764f2e95c28540f0e6b44e7445c8d
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>
5 This file is part of GCC.
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.
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.
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/>. */
21 #ifndef GCC_VALUE_RELATION_H
22 #define GCC_VALUE_RELATION_H
25 // This file provides access to a relation oracle which can be used to
26 // maintain and query relations and equivalences between SSA_NAMES.
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.
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.
39 // relation_kind is a typedef of enum tree_code, but has restricted range
40 // and a couple of extra values.
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:
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)
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.
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.
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.
64 typedef enum relation_kind_t
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;
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);
83 class relation_oracle
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);
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;
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);
109 // This class represents an equivalency set, and contains a link to the next
110 // one in the list to be searched.
112 class equiv_chain
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);
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.
127 class equiv_oracle : public relation_oracle
129 public:
130 equiv_oracle ();
131 ~equiv_oracle ();
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);
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;
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.
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;
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);
161 // Summary block header for relations.
163 class relation_chain_head
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;
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.
182 class dom_oracle : public equiv_oracle
184 public:
185 dom_oracle ();
186 ~dom_oracle ();
188 void register_relation (basic_block bb, relation_kind k, tree op1, tree op2);
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);
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 &);
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.
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.
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.
225 // reset_path is used to clear all locally registered paths to initial state.
227 class path_oracle : public relation_oracle
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;
248 bitmap_obstack m_bitmaps;
249 struct obstack m_chain_obstack;
251 #endif /* GCC_VALUE_RELATION_H */