1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
|
/* Header file for the value range relational processing.
Copyright (C) 2020-2021 Free Software Foundation, Inc.
Contributed by Andrew MacLeod <amacleod@redhat.com>
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
#ifndef GCC_VALUE_RELATION_H
#define GCC_VALUE_RELATION_H
// This file provides access to a relation oracle which can be used to
// maintain and query relations and equivalences between SSA_NAMES.
//
// The general range_query object provided in value-query.h provides
// access to an oracle, if one is available, via the oracle() method.
// Thre are also a couple of access routines provided, which even if there is
// no oracle, will return the default VREL_NONE no relation.
//
// Typically, when a ranger object is active, there will be an oracle, and
// any information available can be directly queried. Ranger also sets and
// utilizes the relation information to enhance it's range calculations, this
// is totally transparent to the client, and they are free to make queries.
//
//
// relation_kind is a typedef of enum tree_code, but has restricted range
// and a couple of extra values.
//
// A query is made requesting the relation between SSA1 and SSA@ in a basic
// block, or on an edge, the possible return values are:
//
// EQ_EXPR, NE_EXPR, LT_EXPR, LE_EXPR, GT_EXPR, and GE_EXPR mean the same.
// VREL_NONE : No relation between the 2 names.
// VREL_EMPTY : Impossible relation (ie, A < B && A > B produces VREL_EMPTY.
//
// The oracle maintains EQ_EXPR relations with equivalency sets, so if a
// relation comes back EQ_EXPR, it is also possible to query the set of
// equivlaencies. These are basically bitmaps over ssa_names.
//
// relations are maintained via the dominace trees, are are optimized assuming
// they are registered in dominance order. When a new relation is added, it
// is intersected with whatever existing relation exists in the dominance tree
// and registered at the specified block.
// Rather than introduce a new enumerated type for relations, we can use the
// existing tree_codes for relations, plus add a couple of #defines for
// the other cases. These codes are arranged such that VREL_NONE is the first
// code, and all the rest are contiguous.
typedef enum tree_code relation_kind;
#define VREL_NONE TRUTH_NOT_EXPR
#define VREL_EMPTY LTGT_EXPR
// General relation kind transformations.
relation_kind relation_union (relation_kind r1, relation_kind r2);
relation_kind relation_intersect (relation_kind r1, relation_kind r2);
relation_kind relation_negate (relation_kind r);
relation_kind relation_swap (relation_kind r);
void print_relation (FILE *f, relation_kind rel);
class relation_oracle
{
public:
virtual ~relation_oracle () { }
// register a relation between 2 ssa names at a stmt.
void register_stmt (gimple *, relation_kind, tree, tree);
// register a relation between 2 ssa names on an edge.
void register_edge (edge, relation_kind, tree, tree);
// Return equivalency set for an SSA name in a basic block.
virtual const_bitmap equiv_set (tree, basic_block) = 0;
// register a relation between 2 ssa names in a basic block.
virtual void register_relation (basic_block, relation_kind, tree, tree) = 0;
// Query for a relation between two ssa names in a basic block.
virtual relation_kind query_relation (basic_block, tree, tree) = 0;
// Query for a relation between two equivalency stes in a basic block.
virtual relation_kind query_relation (basic_block, const_bitmap,
const_bitmap) = 0;
virtual void dump (FILE *, basic_block) const = 0;
virtual void dump (FILE *) const = 0;
void debug () const;
};
// This class represents an equivalency set, and contains a link to the next
// one in the list to be searched.
class equiv_chain
{
public:
bitmap m_names; // ssa-names in equiv set.
basic_block m_bb; // Block this belongs to
equiv_chain *m_next; // Next in block list.
void dump (FILE *f) const; // Show names in this list.
equiv_chain *find (unsigned ssa);
};
// The equivalency oracle maintains equivalencies using the dominator tree.
// Equivalencies apply to an entire basic block. Equivalencies on edges
// can be represented only on edges whose destination is a single-pred block,
// and the equivalence is simply applied to that succesor block.
class equiv_oracle : public relation_oracle
{
public:
equiv_oracle ();
~equiv_oracle ();
const_bitmap equiv_set (tree ssa, basic_block bb);
void register_relation (basic_block bb, relation_kind k, tree ssa1,
tree ssa2);
relation_kind query_relation (basic_block, tree, tree);
relation_kind query_relation (basic_block, const_bitmap, const_bitmap);
void dump (FILE *f, basic_block bb) const;
void dump (FILE *f) const;
protected:
bitmap_obstack m_bitmaps;
struct obstack m_chain_obstack;
private:
bitmap m_equiv_set; // Index by ssa-name. true if an equivalence exists.
vec <equiv_chain *> m_equiv; // Index by BB. list of equivalences.
vec <bitmap> m_self_equiv; // Index by ssa-name, self equivalency set.
void limit_check (basic_block bb = NULL);
equiv_chain *find_equiv_block (unsigned ssa, int bb) const;
equiv_chain *find_equiv_dom (tree name, basic_block bb) const;
bitmap register_equiv (basic_block bb, unsigned v, equiv_chain *equiv_1);
bitmap register_equiv (basic_block bb, equiv_chain *equiv_1,
equiv_chain *equiv_2);
};
// Summary block header for relations.
class relation_chain_head
{
public:
bitmap m_names; // ssa_names with relations in this block.
class relation_chain *m_head; // List of relations in block.
relation_kind find_relation (const_bitmap b1, const_bitmap b2) const;
};
// A relation oracle maintains a set of relations between ssa_names using the
// dominator tree structures. Equivalencies are considered a subset of
// a general relation and maintained by an equivalence oracle by transparently
// passing any EQ_EXPR relations to it.
// Relations are handled at the basic block level. All relations apply to
// an entire block, and are thus kept in a summary index by block.
// Similar to the equivalence oracle, edges are handled by applying the
// relation to the destination block of the edge, but ONLY if that block
// has a single successor. For now.
class dom_oracle : public equiv_oracle
{
public:
dom_oracle ();
~dom_oracle ();
void register_relation (basic_block bb, relation_kind k, tree op1, tree op2);
relation_kind query_relation (basic_block bb, tree ssa1, tree ssa2);
relation_kind query_relation (basic_block bb, const_bitmap b1,
const_bitmap b2);
void dump (FILE *f, basic_block bb) const;
void dump (FILE *f) const;
private:
bitmap m_tmp, m_tmp2;
bitmap m_relation_set; // Index by ssa-name. True if a relation exists
vec <relation_chain_head> m_relations; // Index by BB, list of relations.
relation_kind find_relation_block (unsigned bb, const_bitmap b1,
const_bitmap b2) const;
relation_kind find_relation_block (int bb, unsigned v1, unsigned v2,
relation_chain **obj = NULL) const;
relation_kind find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const;
relation_chain *set_one_relation (basic_block bb, relation_kind k, tree op1,
tree op2);
void register_transitives (basic_block, const class value_relation &);
};
// A path_oracle implements relations in a list. The only sense of ordering
// is the latest registered relation is the first found during a search.
// It can be constructed with an optional "root" oracle which will be used
// to look up any relations not found in the list.
// This allows the client to walk paths starting at some block and register
// and query relations along that path, ignoring other edges.
//
// For registering a relation, a query if made of the root oracle if there is
// any known relationship at block BB, and it is combined with this new
// relation and entered in the list.
//
// Queries are resolved by looking first in the list, and only if nothing is
// found is the root oracle queried at block BB.
//
// reset_path is used to clear all locally registered paths to initial state.
class path_oracle : public relation_oracle
{
public:
path_oracle (relation_oracle *oracle = NULL);
~path_oracle ();
const_bitmap equiv_set (tree, basic_block);
void register_relation (basic_block, relation_kind, tree, tree);
relation_kind query_relation (basic_block, tree, tree);
relation_kind query_relation (basic_block, const_bitmap, const_bitmap);
void reset_path ();
void dump (FILE *, basic_block) const;
void dump (FILE *) const;
private:
void register_equiv (basic_block bb, tree ssa1, tree ssa2);
equiv_chain m_equiv;
relation_chain_head m_relations;
relation_oracle *m_root;
bitmap_obstack m_bitmaps;
struct obstack m_chain_obstack;
};
#endif /* GCC_VALUE_RELATION_H */
|
