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
|
/* Header file for gimple range GORI structures.
Copyright (C) 2017-2023 Free Software Foundation, Inc.
Contributed by Andrew MacLeod <amacleod@redhat.com>
and Aldy Hernandez <aldyh@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_GIMPLE_RANGE_GORI_H
#define GCC_GIMPLE_RANGE_GORI_H
// RANGE_DEF_CHAIN is used to determine which SSA names in a block can
// have range information calculated for them, and what the
// dependencies on each other are.
class range_def_chain
{
public:
range_def_chain ();
~range_def_chain ();
tree depend1 (tree name) const;
tree depend2 (tree name) const;
bool in_chain_p (tree name, tree def);
bool chain_import_p (tree name, tree import);
void register_dependency (tree name, tree ssa1, basic_block bb = NULL);
void dump (FILE *f, basic_block bb, const char *prefix = NULL);
protected:
bool has_def_chain (tree name);
bool def_chain_in_bitmap_p (tree name, bitmap b);
void add_def_chain_to_bitmap (bitmap b, tree name);
bitmap get_def_chain (tree name);
bitmap get_imports (tree name);
bitmap_obstack m_bitmaps;
private:
struct rdc {
unsigned int ssa1; // First direct dependency
unsigned int ssa2; // Second direct dependency
bitmap bm; // All dependencies
bitmap m_import;
};
vec<rdc> m_def_chain; // SSA_NAME : def chain components.
void set_import (struct rdc &data, tree imp, bitmap b);
int m_logical_depth;
};
// Return the first direct dependency for NAME, if there is one.
// Direct dependencies are those which occur on the definition statement.
// Only the first 2 such names are cached.
inline tree
range_def_chain::depend1 (tree name) const
{
unsigned v = SSA_NAME_VERSION (name);
if (v >= m_def_chain.length ())
return NULL_TREE;
unsigned v1 = m_def_chain[v].ssa1;
if (!v1)
return NULL_TREE;
return ssa_name (v1);
}
// Return the second direct dependency for NAME, if there is one.
inline tree
range_def_chain::depend2 (tree name) const
{
unsigned v = SSA_NAME_VERSION (name);
if (v >= m_def_chain.length ())
return NULL_TREE;
unsigned v2 = m_def_chain[v].ssa2;
if (!v2)
return NULL_TREE;
return ssa_name (v2);
}
// GORI_MAP is used to accumulate what SSA names in a block can
// generate range information, and provides tools for the block ranger
// to enable it to efficiently calculate these ranges.
class gori_map : public range_def_chain
{
public:
gori_map ();
~gori_map ();
bool is_export_p (tree name, basic_block bb = NULL);
bool is_import_p (tree name, basic_block bb);
bitmap exports (basic_block bb);
bitmap imports (basic_block bb);
void set_range_invariant (tree name, bool invariant = true);
void dump (FILE *f);
void dump (FILE *f, basic_block bb, bool verbose = true);
private:
vec<bitmap> m_outgoing; // BB: Outgoing ranges calculable on edges
vec<bitmap> m_incoming; // BB: Incoming ranges which can affect exports.
bitmap m_maybe_variant; // Names which might have outgoing ranges.
void maybe_add_gori (tree name, basic_block bb);
void calculate_gori (basic_block bb);
};
// This class is used to determine which SSA_NAMES can have ranges
// calculated for them on outgoing edges from basic blocks. This represents
// ONLY the effect of the basic block edge->src on a range.
//
// There are 2 primary entry points:
//
// has_edge_range_p (tree name, edge e)
// returns true if the outgoing edge *may* be able to produce range
// information for ssa_name NAME on edge E.
// FALSE is returned if this edge does not affect the range of NAME.
// if no edge is specified, return TRUE if name may have a value calculated
// on *ANY* edge that has been seen. FALSE indicates that the global value
// is applicable everywhere that has been processed.
//
// outgoing_edge_range_p (vrange &range, edge e, tree name)
// Actually does the calculation of RANGE for name on E
// This represents application of whatever static range effect edge E
// may have on NAME, not any cumulative effect.
// There are also some internal APIs
//
// ssa_range_in_bb () is an internal routine which is used to start any
// calculation chain using SSA_NAMES which come from outside the block. ie
// a_2 = b_4 - 8
// if (a_2 < 30)
// on the true edge, a_2 is known to be [0, 29]
// b_4 can be calculated as [8, 37]
// during this calculation, b_4 is considered an "import" and ssa_range_in_bb
// is queried for a starting range which is used in the calculation.
// A default value of VARYING provides the raw static info for the edge.
//
// If there is any known range for b_4 coming into this block, it can refine
// the results. This allows for cascading results to be propagated.
// if b_4 is [100, 200] on entry to the block, feeds into the calculation
// of a_2 = [92, 192], and finally on the true edge the range would be
// an empty range [] because it is not possible for the true edge to be taken.
//
// expr_range_in_bb is simply a wrapper which calls ssa_range_in_bb for
// SSA_NAMES and otherwise simply calculates the range of the expression.
//
// The constructor takes a flag value to use on edges to check for the
// NON_EXECUTABLE_EDGE property. The zero default means no flag is checked.
// All value requests from NON_EXECUTABLE_EDGE edges are returned UNDEFINED.
//
// The remaining routines are internal use only.
class value_relation;
class gori_compute : public gori_map
{
public:
gori_compute (int not_executable_flag = 0);
bool outgoing_edge_range_p (vrange &r, edge e, tree name, range_query &q);
bool condexpr_adjust (vrange &r1, vrange &r2, gimple *s, tree cond, tree op1,
tree op2, fur_source &src);
bool has_edge_range_p (tree name, basic_block bb = NULL);
bool has_edge_range_p (tree name, edge e);
void dump (FILE *f);
bool compute_operand_range (vrange &r, gimple *stmt, const vrange &lhs,
tree name, class fur_source &src,
value_relation *rel = NULL);
private:
bool refine_using_relation (tree op1, vrange &op1_range,
tree op2, vrange &op2_range,
fur_source &src, relation_kind k);
bool may_recompute_p (tree name, edge e, int depth = -1);
bool may_recompute_p (tree name, basic_block bb = NULL, int depth = -1);
bool compute_operand_range_switch (vrange &r, gswitch *s, const vrange &lhs,
tree name, fur_source &src);
bool compute_operand1_range (vrange &r, gimple_range_op_handler &handler,
const vrange &lhs, tree name, fur_source &src,
value_relation *rel = NULL);
bool compute_operand2_range (vrange &r, gimple_range_op_handler &handler,
const vrange &lhs, tree name, fur_source &src,
value_relation *rel = NULL);
bool compute_operand1_and_operand2_range (vrange &r,
gimple_range_op_handler &handler,
const vrange &lhs, tree name,
fur_source &src,
value_relation *rel = NULL);
void compute_logical_operands (vrange &true_range, vrange &false_range,
gimple_range_op_handler &handler,
const irange &lhs, tree name, fur_source &src,
tree op, bool op_in_chain);
bool logical_combine (vrange &r, enum tree_code code, const irange &lhs,
const vrange &op1_true, const vrange &op1_false,
const vrange &op2_true, const vrange &op2_false);
int_range<2> m_bool_zero; // Boolean false cached.
int_range<2> m_bool_one; // Boolean true cached.
gimple_outgoing_range outgoing; // Edge values for COND_EXPR & SWITCH_EXPR.
range_tracer tracer;
int m_not_executable_flag;
};
// For each name that is an import into BB's exports..
#define FOR_EACH_GORI_IMPORT_NAME(gori, bb, name) \
for (gori_export_iterator iter ((gori).imports ((bb))); \
((name) = iter.get_name ()); \
iter.next ())
// For each name possibly exported from block BB.
#define FOR_EACH_GORI_EXPORT_NAME(gori, bb, name) \
for (gori_export_iterator iter ((gori).exports ((bb))); \
((name) = iter.get_name ()); \
iter.next ())
// Used to assist with iterating over the GORI export list in various ways
class gori_export_iterator {
public:
gori_export_iterator (bitmap b);
void next ();
tree get_name ();
protected:
bitmap bm;
bitmap_iterator bi;
unsigned y;
};
#endif // GCC_GIMPLE_RANGE_GORI_H
|
