2 * abcremoval.h: Array bounds check removal
5 * Massimiliano Mantione (massi@ximian.com)
7 * (C) 2004 Ximian, Inc. http://www.ximian.com
10 #ifndef __MONO_ABCREMOVAL_H__
11 #define __MONO_ABCREMOVAL_H__
19 * All handled value types (expressions) in variable definitions and branch
22 * CONSTANT: an integer constant
23 * VARIABLE: a reference to a variable, with an optional delta (can be zero)
24 * PHI: a PHI definition of the SSA representation
27 MONO_ANY_SUMMARIZED_VALUE,
28 MONO_CONSTANT_SUMMARIZED_VALUE,
29 MONO_VARIABLE_SUMMARIZED_VALUE,
30 MONO_PHI_SUMMARIZED_VALUE
31 } MonoSummarizedValueType;
34 * A MONO_CONSTANT_SUMMARIZED_VALUE value.
37 typedef struct MonoSummarizedConstantValue {
39 } MonoSummarizedConstantValue;
42 * A MONO_VARIABLE_SUMMARIZED_VALUE value
43 * variable: the variable index in the cfg
44 * delta: the delta (can be zero)
46 typedef struct MonoSummarizedVariableValue {
49 } MonoSummarizedVariableValue;
52 * A MONO_PHI_SUMMARIZED_VALUE value.
53 * number_of_alternatives: the number of alternatives in the PHI definition
54 * phi_alternatives: an array of integers with the indexes of the variables
55 * which are the alternatives in this PHI definition
57 typedef struct MonoSummarizedPhiValue {
58 int number_of_alternatives;
59 int *phi_alternatives;
60 } MonoSummarizedPhiValue;
64 * In practice it is a "tagged union".
66 typedef struct MonoSummarizedValue {
67 MonoSummarizedValueType type;
69 MonoSummarizedConstantValue constant;
70 MonoSummarizedVariableValue variable;
71 MonoSummarizedPhiValue phi;
73 } MonoSummarizedValue;
76 * A "relation" between two values.
77 * The enumeration is used as a bit field, with three significant bits.
78 * The degenerated cases are meaningful:
79 * MONO_ANY_RELATION: we know nothing of this relation
80 * MONO_NO_RELATION: no relation is possible (this code is unreachable)
86 MONO_NE_RELATION = (MONO_LT_RELATION|MONO_GT_RELATION),
87 MONO_LE_RELATION = (MONO_LT_RELATION|MONO_EQ_RELATION),
88 MONO_GE_RELATION = (MONO_GT_RELATION|MONO_EQ_RELATION),
89 MONO_ANY_RELATION = (MONO_EQ_RELATION|MONO_LT_RELATION|MONO_GT_RELATION),
94 * A relation between variables (or a variable and a constant).
95 * The first variable (the one "on the left of the expression") is implicit.
96 * relation: the relation between the variable and the value
97 * related_value: the related value
98 * relation_is_static_definition: TRUE if the relation comes from a veriable
99 * definition, FALSE if it comes from a branch
101 * next: pointer to the next relation of this variable in the evaluation area
102 * (relations are always kept in the evaluation area, one list for each
105 typedef struct MonoSummarizedValueRelation {
106 MonoValueRelation relation;
107 MonoSummarizedValue related_value;
108 gboolean relation_is_static_definition;
109 struct MonoSummarizedValueRelation *next;
110 } MonoSummarizedValueRelation;
113 * The evaluation status for one variable.
114 * The enumeration is used as a bit field, because the status has two
116 * The first is the "main" one (bits 0, 1 and 2), which is actually a proper
117 * enumeration (the bits are mutually exclusive, and their meaning is obvious).
118 * The other section (the bits in the MONO_RELATIONS_EVALUATION_IS_RECURSIVE
119 * set) is used to mark an evaluation as recursive (while backtracking through
120 * the evaluation contexts), to state if the graph loop gives a value that is
121 * ascending, descending or indefinite.
122 * The bits are handled separately because the same evaluation context could
123 * belong to more than one loop, so that each loop would set its bits.
124 * After the backtracking, the bits are examined and a decision is taken.
128 MONO_RELATIONS_EVALUATION_NOT_STARTED = 0,
129 MONO_RELATIONS_EVALUATION_IN_PROGRESS = 1,
130 MONO_RELATIONS_EVALUATION_COMPLETED = 2,
131 MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING = 4,
132 MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING = 8,
133 MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE = 16,
134 MONO_RELATIONS_EVALUATION_IS_RECURSIVE = (MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING|MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING|MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE)
135 } MonoRelationsEvaluationStatus;
138 * A range of values (ranges include their limits).
139 * A range from MIN_INT to MAX_INT is "indefinite" (any value).
140 * A range where upper < lower means unreachable code (some of the relations
141 * that generated the range is incompatible, like x = 0 and x > 0).
142 * lower: the lower limit
143 * upper: the upper limit
145 typedef struct MonoRelationsEvaluationRange {
148 } MonoRelationsEvaluationRange;
151 * The two ranges that contain the result of a variable evaluation.
152 * zero: the range with respect to zero
153 * variable: the range with respect to the target variable in this evaluation
155 typedef struct MonoRelationsEvaluationRanges {
156 MonoRelationsEvaluationRange zero;
157 MonoRelationsEvaluationRange variable;
158 } MonoRelationsEvaluationRanges;
161 * The context of a variable evaluation.
162 * status: the evaluation status
163 * current_relation: the relation that is currently evaluated.
164 * ranges: the result of the evaluation.
165 * father: the context of the evaluation that invoked this one (used to
166 * perform the backtracking when loops are detected.
168 typedef struct MonoRelationsEvaluationContext {
169 MonoRelationsEvaluationStatus status;
170 MonoSummarizedValueRelation *current_relation;
171 MonoRelationsEvaluationRanges ranges;
172 struct MonoRelationsEvaluationContext *father;
173 } MonoRelationsEvaluationContext;
176 * Basic macros to initialize and check ranges.
178 #define MONO_MAKE_RELATIONS_EVALUATION_RANGE_WEAK(r) do{\
179 (r).lower = INT_MIN;\
180 (r).upper = INT_MAX;\
182 #define MONO_MAKE_RELATIONS_EVALUATION_RANGES_WEAK(rs) do{\
183 MONO_MAKE_RELATIONS_EVALUATION_RANGE_WEAK ((rs).zero); \
184 MONO_MAKE_RELATIONS_EVALUATION_RANGE_WEAK ((rs).variable); \
186 #define MONO_MAKE_RELATIONS_EVALUATION_RANGE_IMPOSSIBLE(r) do{\
187 (r).lower = INT_MAX;\
188 (r).upper = INT_MIN;\
190 #define MONO_MAKE_RELATIONS_EVALUATION_RANGES_IMPOSSIBLE(rs) do{\
191 MONO_MAKE_RELATIONS_EVALUATION_RANGE_IMPOSSIBLE ((rs).zero); \
192 MONO_MAKE_RELATIONS_EVALUATION_RANGE_IMPOSSIBLE ((rs).variable); \
194 #define MONO_RELATIONS_EVALUATION_RANGE_IS_IMPOSSIBLE(r) (((r).lower==INT_MAX)&&((r).upper==INT_MIN))
195 #define MONO_RELATIONS_EVALUATION_RANGES_IS_IMPOSSIBLE(rs) \
196 (MONO_RELATIONS_EVALUATION_RANGE_IS_IMPOSSIBLE((rs).zero) && \
197 MONO_RELATIONS_EVALUATION_RANGE_IS_IMPOSSIBLE((rs).variable))
200 * The following macros are needed because ranges include theit limits, but
201 * some relations explicitly exclude them (GT and LT).
203 #define MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL(ur) ((((ur)==INT_MIN)||((ur)==INT_MAX))?(ur):((ur)-1))
204 #define MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL(lr) ((((lr)==INT_MIN)||((lr)==INT_MAX))?(lr):((lr)+1))
205 #define MONO_APPLY_INEQUALITY_TO_EVALUATION_RANGE(r) do{\
206 (r).lower = MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL ((r).lower);\
207 (r).upper = MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL ((r).upper);\
209 #define MONO_APPLY_INEQUALITY_TO_EVALUATION_RANGES(rs) do{\
210 MONO_APPLY_INEQUALITY_TO_EVALUATION_RANGE ((rs).zero); \
211 MONO_APPLY_INEQUALITY_TO_EVALUATION_RANGE ((rs).variable); \
215 * The following macros perform union and intersection operations on ranges.
217 #define MONO_LOWER_EVALUATION_RANGE_UNION(lr,other_lr) ((lr)=MIN(lr,other_lr))
218 #define MONO_UPPER_EVALUATION_RANGE_UNION(ur,other_ur) ((ur)=MAX(ur,other_ur))
219 #define MONO_LOWER_EVALUATION_RANGE_INTERSECTION(lr,other_lr) ((lr)=MAX(lr,other_lr))
220 #define MONO_UPPER_EVALUATION_RANGE_INTERSECTION(ur,other_ur) ((ur)=MIN(ur,other_ur))
221 #define MONO_RELATIONS_EVALUATION_RANGE_UNION(r,other_r) do{\
222 MONO_LOWER_EVALUATION_RANGE_UNION((r).lower,(other_r).lower);\
223 MONO_UPPER_EVALUATION_RANGE_UNION((r).upper,(other_r).upper);\
225 #define MONO_RELATIONS_EVALUATION_RANGE_INTERSECTION(r,other_r) do{\
226 MONO_LOWER_EVALUATION_RANGE_INTERSECTION((r).lower,(other_r).lower);\
227 MONO_UPPER_EVALUATION_RANGE_INTERSECTION((r).upper,(other_r).upper);\
229 #define MONO_RELATIONS_EVALUATION_RANGES_UNION(rs,other_rs) do{\
230 MONO_RELATIONS_EVALUATION_RANGE_UNION ((rs).zero,(other_rs).zero); \
231 MONO_RELATIONS_EVALUATION_RANGE_UNION ((rs).variable,(other_rs).variable); \
233 #define MONO_RELATIONS_EVALUATION_RANGES_INTERSECTION(rs,other_rs) do{\
234 MONO_RELATIONS_EVALUATION_RANGE_INTERSECTION ((rs).zero,(other_rs).zero); \
235 MONO_RELATIONS_EVALUATION_RANGE_INTERSECTION ((rs).variable,(other_rs).variable); \
239 * The following macros add or subtract "safely" (without over/under-flow) a
240 * delta (constant) value to a range.
242 #define MONO_ADD_DELTA_SAFELY(v,d) do{\
243 if (((d) > 0) && ((v) != INT_MIN)) {\
244 (v) = (((v)+(d))>(v))?((v)+(d)):INT_MAX;\
245 } else if (((d) < 0) && ((v) != INT_MAX)) {\
246 (v) = (((v)+(d))<(v))?((v)+(d)):INT_MIN;\
249 #define MONO_SUB_DELTA_SAFELY(v,d) do{\
250 if (((d) < 0) && ((v) != INT_MIN)) {\
251 (v) = (((v)-(d))>(v))?((v)-(d)):INT_MAX;\
252 } else if (((d) > 0) && ((v) != INT_MAX)) {\
253 (v) = (((v)-(d))<(v))?((v)-(d)):INT_MIN;\
256 #define MONO_ADD_DELTA_SAFELY_TO_RANGE(r,d) do{\
257 MONO_ADD_DELTA_SAFELY((r).lower,(d));\
258 MONO_ADD_DELTA_SAFELY((r).upper,(d));\
260 #define MONO_SUB_DELTA_SAFELY_FROM_RANGE(r,d) do{\
261 MONO_SUB_DELTA_SAFELY((r).lower,(d));\
262 MONO_SUB_DELTA_SAFELY((r).upper,(d));\
264 #define MONO_ADD_DELTA_SAFELY_TO_RANGES(rs,d) do{\
265 MONO_ADD_DELTA_SAFELY_TO_RANGE((rs).zero,(d));\
266 MONO_ADD_DELTA_SAFELY_TO_RANGE((rs).variable,(d));\
268 #define MONO_SUB_DELTA_SAFELY_FROM_RANGES(rs,d) do{\
269 MONO_SUB_DELTA_SAFELY_FROM_RANGE((rs).zero,(d));\
270 MONO_SUB_DELTA_SAFELY_FROM_RANGE((rs).variable,(d));\
275 * The main evaluation area.
276 * cfg: the cfg of the method that is being examined.
277 * relations: and array of relations, one for each method variable (each
278 * relation is the head of a list); this is the evaluation graph
279 * contexts: an array of evaluation contexts (one for each method variable)
281 typedef struct MonoVariableRelationsEvaluationArea {
283 MonoSummarizedValueRelation *relations;
284 MonoRelationsEvaluationContext *contexts;
285 } MonoVariableRelationsEvaluationArea;
288 * Convenience structure to define an "additional" relation for the main
290 * variable: the variable to which the relation is applied
291 * relation: the relation
292 * insertion_point: the point in the graph where the relation is inserted
293 * (useful for removing it from the list when backtracking
294 * in the traversal of the dominator tree)
296 typedef struct MonoAdditionalVariableRelation {
298 MonoSummarizedValueRelation relation;
299 MonoSummarizedValueRelation *insertion_point;
300 } MonoAdditionalVariableRelation;
303 * Convenience structure that stores two additional relations.
304 * In the current code, each BB can add at most two relations to the main
305 * evaluation graph, so one of these structures is enough to hold all the
306 * modifications to the graph made examining one BB.
308 typedef struct MonoAdditionalVariableRelationsForBB {
309 MonoAdditionalVariableRelation relation1;
310 MonoAdditionalVariableRelation relation2;
311 } MonoAdditionalVariableRelationsForBB;
314 #endif /* __MONO_ABCREMOVAL_H__ */