]>
Commit | Line | Data |
---|---|---|
3aaa69e5 | 1 | /* Header file for the value range relational processing. |
7adcbafe | 2 | Copyright (C) 2020-2022 Free Software Foundation, Inc. |
3aaa69e5 AM |
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 | // | |
027e3041 | 53 | // Relations are maintained via the dominace trees and are optimized assuming |
3aaa69e5 AM |
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 | ||
3674d8e6 AM |
76 | |
77 | class relation_oracle | |
78 | { | |
79 | public: | |
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; | |
6b73c07e AM |
99 | protected: |
100 | void valid_equivs (bitmap b, const_bitmap equivs, basic_block bb); | |
3674d8e6 AM |
101 | }; |
102 | ||
534c5352 AM |
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 | }; | |
3aaa69e5 AM |
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 | ||
3674d8e6 | 121 | class equiv_oracle : public relation_oracle |
3aaa69e5 AM |
122 | { |
123 | public: | |
124 | equiv_oracle (); | |
125 | ~equiv_oracle (); | |
126 | ||
3674d8e6 AM |
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); | |
3aaa69e5 | 130 | |
3674d8e6 AM |
131 | relation_kind query_relation (basic_block, tree, tree); |
132 | relation_kind query_relation (basic_block, const_bitmap, const_bitmap); | |
3aaa69e5 AM |
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. | |
3674d8e6 | 142 | vec <bitmap> m_self_equiv; // Index by ssa-name, self equivalency set. |
3aaa69e5 AM |
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); | |
5d110fe9 AM |
151 | void register_initial_def (tree ssa); |
152 | void add_equiv_to_block (basic_block bb, bitmap equiv); | |
3aaa69e5 AM |
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. | |
254ada46 | 162 | int m_num_relations; // Number of relations in block. |
3674d8e6 | 163 | relation_kind find_relation (const_bitmap b1, const_bitmap b2) const; |
3aaa69e5 AM |
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 | ||
3674d8e6 | 176 | class dom_oracle : public equiv_oracle |
3aaa69e5 AM |
177 | { |
178 | public: | |
3674d8e6 AM |
179 | dom_oracle (); |
180 | ~dom_oracle (); | |
3aaa69e5 | 181 | |
3674d8e6 | 182 | void register_relation (basic_block bb, relation_kind k, tree op1, tree op2); |
3aaa69e5 AM |
183 | |
184 | relation_kind query_relation (basic_block bb, tree ssa1, tree ssa2); | |
3674d8e6 AM |
185 | relation_kind query_relation (basic_block bb, const_bitmap b1, |
186 | const_bitmap b2); | |
3aaa69e5 AM |
187 | |
188 | void dump (FILE *f, basic_block bb) const; | |
189 | void dump (FILE *f) const; | |
190 | private: | |
675a3e40 | 191 | bitmap m_tmp, m_tmp2; |
3aaa69e5 AM |
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, | |
3674d8e6 | 195 | const_bitmap b2) const; |
3aaa69e5 | 196 | relation_kind find_relation_block (int bb, unsigned v1, unsigned v2, |
3674d8e6 AM |
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); | |
675a3e40 | 201 | void register_transitives (basic_block, const class value_relation &); |
675a3e40 | 202 | |
3aaa69e5 AM |
203 | }; |
204 | ||
534c5352 AM |
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); | |
8a0fadda | 228 | void killing_def (tree); |
534c5352 AM |
229 | relation_kind query_relation (basic_block, tree, tree); |
230 | relation_kind query_relation (basic_block, const_bitmap, const_bitmap); | |
231 | void reset_path (); | |
eb5ee646 | 232 | void set_root_oracle (relation_oracle *oracle) { m_root = oracle; } |
534c5352 AM |
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; | |
4856699e | 240 | bitmap m_killed_defs; |
534c5352 AM |
241 | |
242 | bitmap_obstack m_bitmaps; | |
243 | struct obstack m_chain_obstack; | |
244 | }; | |
3aaa69e5 | 245 | #endif /* GCC_VALUE_RELATION_H */ |