2 * abcremoval.c: Array bounds check removal
5 * Massimiliano Mantione (massi@ximian.com)
7 * (C) 2004 Ximian, Inc. http://www.ximian.com
12 #include <mono/metadata/debug-helpers.h>
13 #include <mono/metadata/mempool.h>
14 #include <mono/metadata/opcodes.h>
18 #include "abcremoval.h"
20 #if SIZEOF_VOID_P == 8
21 #define OP_PCONST OP_I8CONST
23 #define OP_PCONST OP_ICONST
27 #define TRACE_ABC_REMOVAL (verbose_level > 2)
28 #define REPORT_ABC_REMOVAL (verbose_level > 0)
31 * A little hack for the verbosity level.
32 * The verbosity level is stored in the cfg, but not all functions that must
33 * print something see the cfg, so we store the verbosity level here at the
34 * beginning of the algorithm.
35 * This is not thread safe (does not handle correctly different verbosity
36 * levels in different threads), and is not exact in case of dynamic changes
37 * of the verbosity level...
38 * Anyway, this is not needed, all that can happen is that something more
39 * (or less) is logged, the result is in any case correct.
41 static int verbose_level
;
44 #define RELATION_BETWEEN_VALUES(value,related_value) (\
45 ((value) > (related_value))? MONO_GT_RELATION :\
46 (((value) < (related_value))? MONO_LT_RELATION : MONO_EQ_RELATION))
48 #define MAKE_VALUE_ANY(v) do{\
49 (v).type = MONO_ANY_SUMMARIZED_VALUE;\
52 #define MAKE_VALUE_RELATION_ANY(r) do{\
53 (r)->relation = MONO_ANY_RELATION;\
54 MAKE_VALUE_ANY((r)->related_value);\
57 #define INITIALIZE_VALUE_RELATION(r) do{\
58 MAKE_VALUE_RELATION_ANY((r));\
62 #define MONO_NEGATED_RELATION(r) ((~(r))&MONO_ANY_RELATION)
63 #define MONO_SYMMETRIC_RELATION(r) (((r)&MONO_EQ_RELATION)|(((r)&MONO_LT_RELATION)<<1)|((r&MONO_GT_RELATION)>>1))
68 print_relation (int relation
) {
71 if (relation
& MONO_LT_RELATION
) {
75 if (relation
& MONO_EQ_RELATION
) {
82 if (relation
& MONO_GT_RELATION
) {
93 print_summarized_value (MonoSummarizedValue
*value
) {
94 switch (value
->type
) {
95 case MONO_ANY_SUMMARIZED_VALUE
:
98 case MONO_CONSTANT_SUMMARIZED_VALUE
:
99 printf ("CONSTANT %d", value
->value
.constant
.value
);
101 case MONO_VARIABLE_SUMMARIZED_VALUE
:
102 printf ("VARIABLE %d, delta %d", value
->value
.variable
.variable
, value
->value
.variable
.delta
);
104 case MONO_PHI_SUMMARIZED_VALUE
: {
107 for (phi
= 0; phi
< value
->value
.phi
.number_of_alternatives
; phi
++) {
108 if (phi
) printf (",");
109 printf ("%d", value
->value
.phi
.phi_alternatives
[phi
]);
115 g_assert_not_reached ();
120 print_summarized_value_relation (MonoSummarizedValueRelation
*relation
) {
121 printf ("Relation ");
122 print_relation (relation
->relation
);
123 printf (" with value ");
124 print_summarized_value (&(relation
->related_value
));
129 print_summarized_value_relation_chain (MonoSummarizedValueRelation
*relation
) {
130 printf ("Relations:\n");
132 print_summarized_value_relation (relation
);
134 relation
= relation
->next
;
140 print_evaluation_context_status (MonoRelationsEvaluationStatus status
) {
141 if (status
== MONO_RELATIONS_EVALUATION_NOT_STARTED
) {
142 printf ("EVALUATION_NOT_STARTED");
144 gboolean print_or
= FALSE
;
147 if (status
& MONO_RELATIONS_EVALUATION_IN_PROGRESS
) {
148 if (print_or
) printf ("|");
149 printf ("EVALUATION_IN_PROGRESS");
152 if (status
& MONO_RELATIONS_EVALUATION_COMPLETED
) {
153 if (print_or
) printf ("|");
154 printf ("EVALUATION_COMPLETED");
157 if (status
& MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING
) {
158 if (print_or
) printf ("|");
159 printf ("RECURSIVELY_ASCENDING");
162 if (status
& MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING
) {
163 if (print_or
) printf ("|");
164 printf ("RECURSIVELY_DESCENDING");
167 if (status
& MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE
) {
168 if (print_or
) printf ("|");
169 printf ("RECURSIVELY_INDEFINITE");
178 print_evaluation_context_ranges (MonoRelationsEvaluationRanges
*ranges
) {
179 printf ("(ranges: zero [%d,%d], variable [%d,%d])", ranges
->zero
.lower
, ranges
->zero
.upper
, ranges
->variable
.lower
, ranges
->variable
.upper
);
183 print_evaluation_context (MonoRelationsEvaluationContext
*context
) {
184 printf ("Context status: ");
185 print_evaluation_context_status (context
->status
);
186 if (context
->status
& (MONO_RELATIONS_EVALUATION_IN_PROGRESS
|MONO_RELATIONS_EVALUATION_COMPLETED
)) {
187 print_evaluation_context_ranges (&(context
->ranges
));
194 print_evaluation_area (MonoVariableRelationsEvaluationArea
*area
) {
196 printf ("Dump of evaluation area (%d variables):\n", area
->cfg
->num_varinfo
);
197 for (i
= 0; i
< area
->cfg
->num_varinfo
; i
++) {
198 printf ("Variable %d: ", i
);
199 print_evaluation_context (&(area
->contexts
[i
]));
200 print_summarized_value_relation_chain (&(area
->relations
[i
]));
205 print_evaluation_area_contexts (MonoVariableRelationsEvaluationArea
*area
) {
207 printf ("Dump of evaluation area contexts (%d variables):\n", area
->cfg
->num_varinfo
);
208 for (i
= 0; i
< area
->cfg
->num_varinfo
; i
++) {
209 printf ("Variable %d: ", i
);
210 print_evaluation_context (&(area
->contexts
[i
]));
216 * Given a MonoInst, if it is a store to a variable return the MonoInst that
217 * represents the stored value.
218 * If anything goes wrong, return NULL.
219 * store: the MonoInst that should be a store
220 * expected_variable_index: the variable where the value should be stored
221 * return: either the stored value, or NULL
224 get_variable_value_from_store_instruction (MonoInst
*store
, int expected_variable_index
) {
225 switch (store
->opcode
) {
234 if (TRACE_ABC_REMOVAL
) {
235 printf ("[store instruction found]");
237 if ((store
->inst_left
->opcode
== OP_LOCAL
) || (store
->inst_left
->opcode
== OP_ARG
)) {
238 int variable_index
= store
->inst_left
->inst_c0
;
239 if (TRACE_ABC_REMOVAL
) {
240 printf ("[value put in local %d (expected %d)]", variable_index
, expected_variable_index
);
242 if (variable_index
== expected_variable_index
) {
243 return store
->inst_right
;
259 * Check if the delta of an integer variable value is safe with respect
260 * to the variable size in bytes and its kind (signed or unsigned).
261 * If the delta is not safe, make the value an "any".
264 check_delta_safety (MonoVariableRelationsEvaluationArea
*area
, MonoSummarizedValue
*value
) {
265 if (value
->type
== MONO_VARIABLE_SUMMARIZED_VALUE
) {
266 int variable
= value
->value
.variable
.variable
;
267 int delta
= value
->value
.variable
.delta
;
268 if ((area
->variable_value_kind
[variable
]) & MONO_UNSIGNED_VALUE_FLAG
) {
270 MAKE_VALUE_ANY (*value
);
273 if (((area
->variable_value_kind
[variable
]) & MONO_INTEGER_VALUE_SIZE_BITMASK
) < 4) {
274 MAKE_VALUE_ANY (*value
);
275 } else if (delta
> 16) {
276 MAKE_VALUE_ANY (*value
);
282 /* Prototype, definition comes later */
284 summarize_array_value (MonoVariableRelationsEvaluationArea
*area
, MonoInst
*value
, MonoSummarizedValue
*result
, gboolean is_array_type
);
287 * Given a MonoInst representing an integer value, store it in "summarized" form.
288 * result_value_kind: the "expected" kind of result;
289 * result: the "summarized" value
290 * returns the "actual" kind of result, if guessable (otherwise MONO_UNKNOWN_INTEGER_VALUE)
292 static MonoIntegerValueKind
293 summarize_integer_value (MonoVariableRelationsEvaluationArea
*area
, MonoInst
*value
, MonoSummarizedValue
*result
, MonoIntegerValueKind result_value_kind
) {
294 MonoIntegerValueKind value_kind
;
296 if (value
->type
== STACK_I8
) {
297 value_kind
= MONO_INTEGER_VALUE_SIZE_8
;
298 } else if (value
->type
== STACK_I4
) {
299 value_kind
= MONO_INTEGER_VALUE_SIZE_4
;
301 value_kind
= MONO_UNKNOWN_INTEGER_VALUE
;
304 switch (value
->opcode
) {
306 result
->type
= MONO_CONSTANT_SUMMARIZED_VALUE
;
307 result
->value
.constant
.value
= value
->inst_c0
;
311 result
->type
= MONO_VARIABLE_SUMMARIZED_VALUE
;
312 result
->value
.variable
.variable
= value
->inst_c0
;
313 result
->value
.variable
.delta
= 0;
314 value_kind
= area
->variable_value_kind
[value
->inst_c0
];
317 value_kind
= MONO_INTEGER_VALUE_SIZE_1
;
320 value_kind
= MONO_UNSIGNED_INTEGER_VALUE_SIZE_1
;
323 value_kind
= MONO_INTEGER_VALUE_SIZE_2
;
326 value_kind
= MONO_UNSIGNED_INTEGER_VALUE_SIZE_2
;
329 value_kind
= MONO_INTEGER_VALUE_SIZE_4
;
332 value_kind
= MONO_UNSIGNED_INTEGER_VALUE_SIZE_4
;
335 value_kind
= MONO_INTEGER_VALUE_SIZE_8
;
338 value_kind
= SIZEOF_VOID_P
;
340 if ((value
->inst_left
->opcode
== OP_LOCAL
) || (value
->inst_left
->opcode
== OP_ARG
)) {
341 value_kind
= summarize_integer_value (area
, value
->inst_left
, result
, result_value_kind
);
343 MAKE_VALUE_ANY (*result
);
347 MonoSummarizedValue left_value
;
348 MonoSummarizedValue right_value
;
349 summarize_integer_value (area
, value
->inst_left
, &left_value
, result_value_kind
);
350 summarize_integer_value (area
, value
->inst_right
, &right_value
, result_value_kind
);
352 if (left_value
.type
== MONO_VARIABLE_SUMMARIZED_VALUE
) {
353 if (right_value
.type
== MONO_CONSTANT_SUMMARIZED_VALUE
) {
354 result
->type
= MONO_VARIABLE_SUMMARIZED_VALUE
;
355 result
->value
.variable
.variable
= left_value
.value
.variable
.variable
;
356 result
->value
.variable
.delta
= left_value
.value
.variable
.delta
+ right_value
.value
.constant
.value
;
358 MAKE_VALUE_ANY (*result
);
360 } else if (right_value
.type
== MONO_VARIABLE_SUMMARIZED_VALUE
) {
361 if (left_value
.type
== MONO_CONSTANT_SUMMARIZED_VALUE
) {
362 result
->type
= MONO_VARIABLE_SUMMARIZED_VALUE
;
363 result
->value
.variable
.variable
= right_value
.value
.variable
.variable
;
364 result
->value
.variable
.delta
= left_value
.value
.constant
.value
+ right_value
.value
.variable
.delta
;
366 MAKE_VALUE_ANY (*result
);
368 } else if ((right_value
.type
== MONO_CONSTANT_SUMMARIZED_VALUE
) && (left_value
.type
== MONO_CONSTANT_SUMMARIZED_VALUE
)) {
369 /* This should not happen if constant folding has been done */
370 result
->type
= MONO_CONSTANT_SUMMARIZED_VALUE
;
371 result
->value
.constant
.value
= left_value
.value
.constant
.value
+ right_value
.value
.constant
.value
;
373 MAKE_VALUE_ANY (*result
);
375 if (result
->type
== MONO_VARIABLE_SUMMARIZED_VALUE
) {
376 check_delta_safety (area
, result
);
381 MonoSummarizedValue left_value
;
382 MonoSummarizedValue right_value
;
383 summarize_integer_value (area
, value
->inst_left
, &left_value
, result_value_kind
);
384 summarize_integer_value (area
, value
->inst_right
, &right_value
, result_value_kind
);
386 if (left_value
.type
== MONO_VARIABLE_SUMMARIZED_VALUE
) {
387 if (right_value
.type
== MONO_CONSTANT_SUMMARIZED_VALUE
) {
388 result
->type
= MONO_VARIABLE_SUMMARIZED_VALUE
;
389 result
->value
.variable
.variable
= left_value
.value
.variable
.variable
;
390 result
->value
.variable
.delta
= left_value
.value
.variable
.delta
- right_value
.value
.constant
.value
;
392 MAKE_VALUE_ANY (*result
);
394 } else if ((right_value
.type
== MONO_CONSTANT_SUMMARIZED_VALUE
) && (left_value
.type
== MONO_CONSTANT_SUMMARIZED_VALUE
)) {
395 /* This should not happen if constant folding has been done */
396 result
->type
= MONO_CONSTANT_SUMMARIZED_VALUE
;
397 result
->value
.constant
.value
= left_value
.value
.constant
.value
- right_value
.value
.constant
.value
;
399 MAKE_VALUE_ANY (*result
);
401 if (result
->type
== MONO_VARIABLE_SUMMARIZED_VALUE
) {
402 check_delta_safety (area
, result
);
407 MonoSummarizedValue left_value
;
408 MonoSummarizedValue right_value
;
409 int constant_operand_value
;
411 summarize_integer_value (area
, value
->inst_left
, &left_value
, result_value_kind
);
412 summarize_integer_value (area
, value
->inst_right
, &right_value
, result_value_kind
);
414 if (left_value
.type
== MONO_CONSTANT_SUMMARIZED_VALUE
) {
415 constant_operand_value
= left_value
.value
.constant
.value
;
416 } else if (right_value
.type
== MONO_CONSTANT_SUMMARIZED_VALUE
) {
417 constant_operand_value
= right_value
.value
.constant
.value
;
419 constant_operand_value
= 0;
422 if (constant_operand_value
> 0) {
423 if (constant_operand_value
<= 0xff) {
424 if ((result_value_kind
& MONO_INTEGER_VALUE_SIZE_BITMASK
) > 1) {
425 value_kind
= MONO_UNSIGNED_INTEGER_VALUE_SIZE_1
;
427 } else if (constant_operand_value
<= 0xffff) {
428 if ((result_value_kind
& MONO_INTEGER_VALUE_SIZE_BITMASK
) > 2) {
429 value_kind
= MONO_UNSIGNED_INTEGER_VALUE_SIZE_2
;
434 MAKE_VALUE_ANY (*result
);
438 case CEE_CONV_OVF_I1
:
439 case CEE_CONV_OVF_I1_UN
:
440 value_kind
= MONO_INTEGER_VALUE_SIZE_1
;
441 MAKE_VALUE_ANY (*result
);
444 case CEE_CONV_OVF_U1
:
445 value_kind
= MONO_UNSIGNED_INTEGER_VALUE_SIZE_1
;
446 MAKE_VALUE_ANY (*result
);
449 case CEE_CONV_OVF_I2
:
450 case CEE_CONV_OVF_I2_UN
:
451 value_kind
= MONO_INTEGER_VALUE_SIZE_2
;
452 MAKE_VALUE_ANY (*result
);
455 case CEE_CONV_OVF_U2
:
456 value_kind
= MONO_UNSIGNED_INTEGER_VALUE_SIZE_2
;
457 MAKE_VALUE_ANY (*result
);
460 summarize_array_value (area
, value
->inst_left
, result
, TRUE
);
461 value_kind
= MONO_UNSIGNED_INTEGER_VALUE_SIZE_4
;
464 result
->type
= MONO_PHI_SUMMARIZED_VALUE
;
465 result
->value
.phi
.number_of_alternatives
= *(value
->inst_phi_args
);
466 result
->value
.phi
.phi_alternatives
= value
->inst_phi_args
+ 1;
469 MAKE_VALUE_ANY (*result
);
475 * Given a MonoInst representing an array value, store it in "summarized" form.
476 * result: the "summarized" value
477 * is_array_type: TRUE of we are *sure* that an eventual OP_PCONST will point
478 * to a MonoArray (this can happen for already initialized readonly static fields,
479 * in which case we will get the array length directly from the MonoArray)
482 summarize_array_value (MonoVariableRelationsEvaluationArea
*area
, MonoInst
*value
, MonoSummarizedValue
*result
, gboolean is_array_type
) {
483 switch (value
->opcode
) {
486 result
->type
= MONO_VARIABLE_SUMMARIZED_VALUE
;
487 result
->value
.variable
.variable
= value
->inst_c0
;
488 result
->value
.variable
.delta
= 0;
491 summarize_array_value (area
, value
->inst_left
, result
, FALSE
);
494 summarize_integer_value (area
, value
->inst_newa_len
, result
, MONO_UNKNOWN_INTEGER_VALUE
);
497 if ((is_array_type
) && (value
->inst_p0
!= NULL
)) {
498 MonoArray
*array
= (MonoArray
*) (value
->inst_p0
);
499 result
->type
= MONO_CONSTANT_SUMMARIZED_VALUE
;
500 result
->value
.constant
.value
= array
->max_length
;
502 MAKE_VALUE_ANY (*result
);
506 result
->type
= MONO_PHI_SUMMARIZED_VALUE
;
507 result
->value
.phi
.number_of_alternatives
= *(value
->inst_phi_args
);
508 result
->value
.phi
.phi_alternatives
= value
->inst_phi_args
+ 1;
511 MAKE_VALUE_ANY (*result
);
515 static MonoValueRelation
516 get_relation_from_branch_instruction (int opcode
) {
519 return MONO_EQ_RELATION
;
522 return MONO_LT_RELATION
;
525 return MONO_LE_RELATION
;
528 return MONO_GT_RELATION
;
531 return MONO_GE_RELATION
;
533 return MONO_NE_RELATION
;
535 return MONO_ANY_RELATION
;
540 * Given a BB, find its entry condition and put its relations in a
541 * "MonoAdditionalVariableRelationsForBB" structure.
543 * relations: the resulting relations (entry condition of the given BB)
546 get_relations_from_previous_bb (MonoVariableRelationsEvaluationArea
*area
, MonoBasicBlock
*bb
, MonoAdditionalVariableRelationsForBB
*relations
) {
547 MonoBasicBlock
*in_bb
;
549 MonoValueRelation branch_relation
;
550 MonoValueRelation symmetric_relation
;
552 INITIALIZE_VALUE_RELATION (&(relations
->relation1
.relation
));
553 relations
->relation1
.relation
.relation_is_static_definition
= FALSE
;
554 relations
->relation1
.insertion_point
= NULL
;
555 relations
->relation1
.variable
= -1;
556 INITIALIZE_VALUE_RELATION (&(relations
->relation2
.relation
));
557 relations
->relation2
.relation
.relation_is_static_definition
= FALSE
;
558 relations
->relation2
.insertion_point
= NULL
;
559 relations
->relation2
.variable
= -1;
562 if (bb
->in_count
== 1) { /* Should write the code to "sum" conditions... */
563 in_bb
= bb
->in_bb
[0];
564 branch
= in_bb
->last_ins
;
565 if (branch
== NULL
) return;
566 branch_relation
= get_relation_from_branch_instruction (branch
->opcode
);
567 if ((branch_relation
!= MONO_ANY_RELATION
) && (branch
->inst_left
->opcode
== OP_COMPARE
)) {
568 MonoSummarizedValue left_value
;
569 MonoSummarizedValue right_value
;
572 if (branch
->inst_true_bb
== bb
) {
574 } else if (branch
->inst_false_bb
== bb
) {
578 g_assert_not_reached ();
582 branch_relation
= MONO_NEGATED_RELATION (branch_relation
);
584 symmetric_relation
= MONO_SYMMETRIC_RELATION (branch_relation
);
586 summarize_integer_value (area
, branch
->inst_left
->inst_left
, &left_value
, MONO_UNKNOWN_INTEGER_VALUE
);
587 summarize_integer_value (area
, branch
->inst_left
->inst_right
, &right_value
, MONO_UNKNOWN_INTEGER_VALUE
);
589 if ((left_value
.type
== MONO_VARIABLE_SUMMARIZED_VALUE
) && ((right_value
.type
== MONO_VARIABLE_SUMMARIZED_VALUE
)||(right_value
.type
== MONO_CONSTANT_SUMMARIZED_VALUE
))) {
590 relations
->relation1
.variable
= left_value
.value
.variable
.variable
;
591 relations
->relation1
.relation
.relation
= branch_relation
;
592 relations
->relation1
.relation
.related_value
= right_value
;
593 if (right_value
.type
== MONO_CONSTANT_SUMMARIZED_VALUE
) {
594 relations
->relation1
.relation
.related_value
.value
.constant
.value
-= left_value
.value
.variable
.delta
;
596 relations
->relation1
.relation
.related_value
.value
.variable
.delta
-= left_value
.value
.variable
.delta
;
599 if ((right_value
.type
== MONO_VARIABLE_SUMMARIZED_VALUE
) && ((left_value
.type
== MONO_VARIABLE_SUMMARIZED_VALUE
)||(left_value
.type
== MONO_CONSTANT_SUMMARIZED_VALUE
))) {
600 relations
->relation2
.variable
= right_value
.value
.variable
.variable
;
601 relations
->relation2
.relation
.relation
= symmetric_relation
;
602 relations
->relation2
.relation
.related_value
= left_value
;
603 if (left_value
.type
== MONO_CONSTANT_SUMMARIZED_VALUE
) {
604 relations
->relation2
.relation
.related_value
.value
.constant
.value
-= right_value
.value
.variable
.delta
;
606 relations
->relation2
.relation
.related_value
.value
.variable
.delta
-= right_value
.value
.variable
.delta
;
615 * Add the given relations to the evaluation area.
616 * area: the evaluation area
617 * change: the relations that must be added
620 apply_change_to_evaluation_area (MonoVariableRelationsEvaluationArea
*area
, MonoAdditionalVariableRelation
*change
) {
621 MonoSummarizedValueRelation
*base_relation
;
623 if (change
->relation
.relation
!= MONO_ANY_RELATION
) {
624 base_relation
= &(area
->relations
[change
->variable
]);
625 while ((base_relation
->next
!= NULL
) && (base_relation
->next
->relation_is_static_definition
)) {
626 base_relation
= base_relation
->next
;
628 change
->insertion_point
= base_relation
;
629 change
->relation
.next
= base_relation
->next
;
630 base_relation
->next
= &(change
->relation
);
635 * Remove the given relation from the evaluation area.
636 * change: the relation that must be removed
639 remove_change_from_evaluation_area (MonoAdditionalVariableRelation
*change
) {
640 if (change
->insertion_point
!= NULL
) {
641 change
->insertion_point
->next
= change
->relation
.next
;
642 change
->relation
.next
= NULL
;
648 clean_contexts (MonoRelationsEvaluationContext
*contexts
, int number
) {
650 for (i
= 0; i
< number
; i
++) {
651 contexts
[i
].status
= MONO_RELATIONS_EVALUATION_NOT_STARTED
;
657 * Perform the intersection of a range and a constant value (taking into
658 * account the relation that the value has with the range).
659 * range: the range that will be intersected with the value
660 * value: the value that will be intersected with the range
661 * relation: the relation between the range and the value
664 intersect_value( MonoRelationsEvaluationRange
*range
, int value
, MonoValueRelation relation
) {
666 case MONO_NO_RELATION
:
667 MONO_MAKE_RELATIONS_EVALUATION_RANGE_IMPOSSIBLE (*range
);
669 case MONO_ANY_RELATION
:
671 case MONO_EQ_RELATION
:
672 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range
->upper
, value
);
673 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range
->lower
, value
);
675 case MONO_NE_RELATION
: {
676 /* IMPROVEMENT Figure this out! (ignoring it is safe anyway) */
679 case MONO_LT_RELATION
:
680 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range
->upper
, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (value
));
682 case MONO_LE_RELATION
:
683 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range
->upper
, value
);
685 case MONO_GT_RELATION
:
686 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range
->lower
, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (value
));
688 case MONO_GE_RELATION
:
689 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range
->lower
, value
);
692 g_assert_not_reached();
698 * Perform the intersection of two pairs of ranges (taking into account the
699 * relation between the ranges and a given delta).
700 * ranges: the ranges that will be intersected
701 * other_ranges the other ranges that will be intersected
702 * delta: the delta between the pairs of ranges
703 * relation: the relation between the pairs of ranges
706 intersect_ranges( MonoRelationsEvaluationRanges
*ranges
, MonoRelationsEvaluationRanges
*other_ranges
, int delta
, MonoValueRelation relation
) {
709 case MONO_NO_RELATION
:
710 MONO_MAKE_RELATIONS_EVALUATION_RANGES_IMPOSSIBLE (*ranges
);
712 case MONO_ANY_RELATION
:
714 case MONO_EQ_RELATION
:
715 MONO_RELATIONS_EVALUATION_RANGES_INTERSECTION (*ranges
, *other_ranges
);
717 case MONO_NE_RELATION
: {
718 /* FIXME Figure this out! (ignoring it is safe anyway) */
721 case MONO_LT_RELATION
:
722 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges
->zero
.upper
, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (other_ranges
->zero
.upper
));
723 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges
->variable
.upper
, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (other_ranges
->variable
.upper
));
725 case MONO_LE_RELATION
:
726 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges
->zero
.upper
, other_ranges
->zero
.upper
);
727 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges
->variable
.upper
, other_ranges
->variable
.upper
);
729 case MONO_GT_RELATION
:
730 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges
->zero
.lower
, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (other_ranges
->zero
.lower
));
731 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges
->variable
.lower
, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (other_ranges
->variable
.lower
));
733 case MONO_GE_RELATION
:
734 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges
->zero
.lower
, other_ranges
->zero
.lower
);
735 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges
->variable
.lower
, other_ranges
->variable
.lower
);
738 g_assert_not_reached();
741 MonoRelationsEvaluationRanges translated_ranges
= *other_ranges
;
742 MONO_ADD_DELTA_SAFELY_TO_RANGES (translated_ranges
, delta
);
743 intersect_ranges( ranges
, &translated_ranges
, FALSE
, relation
);
748 * Recursive method that traverses the relation graph to evaluate the
749 * relation between two variables.
750 * At the end of the execution, the resulting ranges are in the context of
751 * the "starting" variable.
752 * area: the current evaluation area (it contains the relation graph and
753 * memory for all the evaluation contexts is already allocated)
754 * variable: starting variable (the value ranges in its context are the result
755 * of the execution of this procedure)
756 * target_variable: the variable with respect to which the starting variable
757 * is evaluated (tipically the starting variable is the index
758 * and the target one is the array (which means its length))
759 * father_context: the previous evaluation context in recursive invocations
760 * (or NULL for the first invocation)
763 evaluate_relation_with_target_variable (MonoVariableRelationsEvaluationArea
*area
, int variable
, int target_variable
, MonoRelationsEvaluationContext
*father_context
) {
764 MonoRelationsEvaluationContext
*context
= &(area
->contexts
[variable
]);
766 // First of all, we check the evaluation status
767 // (what must be done is *very* different in each case)
768 switch (context
->status
) {
769 case MONO_RELATIONS_EVALUATION_NOT_STARTED
: {
770 MonoSummarizedValueRelation
*relation
= &(area
->relations
[variable
]);
772 if (TRACE_ABC_REMOVAL
) {
773 printf ("Evaluating varible %d (target variable %d)\n", variable
, target_variable
);
774 print_summarized_value_relation (relation
);
778 // We properly inizialize the context
779 context
->status
= MONO_RELATIONS_EVALUATION_IN_PROGRESS
;
780 context
->father
= father_context
;
781 MONO_MAKE_RELATIONS_EVALUATION_RANGES_WEAK (context
->ranges
);
783 // If we have found the target variable, we can set the range
784 // related to it in the context to "equal" (which is [0,0])
785 if (variable
== target_variable
) {
786 if (TRACE_ABC_REMOVAL
) {
787 printf ("Target variable reached (%d), continuing to evaluate relations with constants\n", variable
);
789 context
->ranges
.variable
.lower
= 0;
790 context
->ranges
.variable
.upper
= 0;
793 // Examine all relations for this variable (scan the list)
794 // The contribute of each relation will be intersected (logical and)
795 while (relation
!= NULL
) {
796 context
->current_relation
= relation
;
798 if (TRACE_ABC_REMOVAL
) {
799 printf ("Processing (%d): ", variable
);
800 print_summarized_value_relation (relation
);
804 // We decie what to do according the the type of the related value
805 switch (relation
->related_value
.type
) {
806 case MONO_ANY_SUMMARIZED_VALUE
:
807 // No added information, skip it
809 case MONO_CONSTANT_SUMMARIZED_VALUE
:
810 // Intersect range with constant (taking into account the relation)
811 intersect_value (&(context
->ranges
.zero
), relation
->related_value
.value
.constant
.value
, relation
->relation
);
813 case MONO_VARIABLE_SUMMARIZED_VALUE
:
814 // Generally, evaluate related variable and intersect ranges.
815 // However, some check is necessary...
817 // If the relation is "ANY", nothing to do (no added information)
818 if (relation
->relation
!= MONO_ANY_RELATION
) {
819 int related_variable
= relation
->related_value
.value
.variable
.variable
;
820 MonoRelationsEvaluationContext
*related_context
= &(area
->contexts
[related_variable
]);
822 // The second condition in the "or" avoids messing with "back edges" in the graph traversal
823 // (they are simply ignored instead of triggering the handling of recursion)
824 if ( (related_context
->status
== MONO_RELATIONS_EVALUATION_NOT_STARTED
) || !
825 ((related_context
->current_relation
->related_value
.type
== MONO_VARIABLE_SUMMARIZED_VALUE
) &&
826 (related_context
->current_relation
->related_value
.value
.variable
.variable
== variable
))) {
827 // Evaluate the related variable
828 evaluate_relation_with_target_variable (area
, related_variable
, target_variable
, context
);
830 // Check if we are part of a recursive loop
831 if (context
->status
& MONO_RELATIONS_EVALUATION_IS_RECURSIVE
) {
832 if (TRACE_ABC_REMOVAL
) {
833 printf ("Recursivity detected for varible %d (target variable %d), status ", variable
, target_variable
);
834 print_evaluation_context_status (context
->status
);
837 // If we are, check if the evaluation of the related variable is complete
838 if (related_context
->status
== MONO_RELATIONS_EVALUATION_COMPLETED
) {
839 // If it is complete, we are part of a recursive definition.
840 // Since it is a *definition* (and definitions are evaluated *before*
841 // conditions because they are first in the list), intersection is not
842 // strictly necessary, we simply copy the ranges and apply the delta
843 context
->ranges
= related_context
->ranges
;
844 /* Delta has already been checked for over/under-flow when evaluating values */
845 MONO_ADD_DELTA_SAFELY_TO_RANGES (context
->ranges
, relation
->related_value
.value
.variable
.delta
);
846 context
->status
= MONO_RELATIONS_EVALUATION_COMPLETED
;
847 if (TRACE_ABC_REMOVAL
) {
848 printf (", ranges already computed, result: \n");
849 print_evaluation_context_ranges (&(context
->ranges
));
850 printf (" (delta is %d)\n", relation
->related_value
.value
.variable
.delta
);
853 // If it is not complete, do nothing (we do not have enough information)
854 if (TRACE_ABC_REMOVAL
) {
855 printf (", ranges not computed\n");
859 // If we are not (the common case) intersect the result
860 intersect_ranges( &(context
->ranges
), &(related_context
->ranges
), relation
->related_value
.value
.variable
.delta
, relation
->relation
);
863 if (TRACE_ABC_REMOVAL
) {
864 printf ("Relation is a back-edge in this traversal, skipping\n");
869 case MONO_PHI_SUMMARIZED_VALUE
: {
870 // We must compute all PHI alternatives, combining the results (with a union, which is a logical "or"),
871 // and intersect this result with the ranges in the context; we must also take into account recursions
872 // (with loops that can be ascending, descending, or indefinite)
873 MonoRelationsEvaluationRanges phi_ranges
;
875 gboolean is_ascending
= FALSE
;
876 gboolean is_descending
= FALSE
;
878 MONO_MAKE_RELATIONS_EVALUATION_RANGES_IMPOSSIBLE (phi_ranges
);
879 for (phi
= 0; phi
< relation
->related_value
.value
.phi
.number_of_alternatives
; phi
++) {
880 int phi_alternative
= relation
->related_value
.value
.phi
.phi_alternatives
[phi
];
881 evaluate_relation_with_target_variable (area
, phi_alternative
, target_variable
, context
);
883 // This means we are part of a recursive loop
884 if (context
->status
& MONO_RELATIONS_EVALUATION_IS_RECURSIVE
) {
885 if (TRACE_ABC_REMOVAL
) {
886 printf ("Recursivity detected for varible %d (target variable %d), status ", variable
, target_variable
);
887 print_evaluation_context_status (context
->status
);
890 if (context
->status
& MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING
) {
893 if (context
->status
& MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING
) {
894 is_descending
= TRUE
;
896 if (context
->status
& MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE
) {
898 is_descending
= TRUE
;
901 // Clear "recursivity" bits in the status (recursion has been handled)
902 context
->status
= MONO_RELATIONS_EVALUATION_IN_PROGRESS
;
904 MONO_RELATIONS_EVALUATION_RANGES_UNION (phi_ranges
, area
->contexts
[phi_alternative
].ranges
);
908 // Apply the effects of all recursive loops
910 phi_ranges
.zero
.upper
= INT_MAX
;
911 phi_ranges
.variable
.upper
= INT_MAX
;
914 phi_ranges
.zero
.lower
= INT_MIN
;
915 phi_ranges
.variable
.lower
= INT_MIN
;
918 // Intersect final result
919 MONO_RELATIONS_EVALUATION_RANGES_INTERSECTION (context
->ranges
, phi_ranges
);
923 g_assert_not_reached();
926 // Pass to next relation
927 relation
= relation
->next
;
930 // Check if any recursivity bits are still in the status, and in any case clear them
931 if (context
->status
& MONO_RELATIONS_EVALUATION_IS_RECURSIVE
) {
932 if (TRACE_ABC_REMOVAL
) {
933 printf ("Recursivity for varible %d (target variable %d) discards computation, status ", variable
, target_variable
);
934 print_evaluation_context_status (context
->status
);
937 // If yes, we did not have enough information (most likely we were evaluated inside a PHI, but we also
938 // depended on the same PHI, which was still in evaluation...), so clear the status to "NOT_STARTED"
939 // (if we will be evaluated again, the PHI will be already done, so our evaluation will succeed)
940 context
->status
= MONO_RELATIONS_EVALUATION_NOT_STARTED
;
942 if (TRACE_ABC_REMOVAL
) {
943 printf ("Ranges for varible %d (target variable %d) computed: ", variable
, target_variable
);
944 print_evaluation_context_ranges (&(context
->ranges
));
947 // If not (the common case) the evaluation is complete, and the result is in the context
948 context
->status
= MONO_RELATIONS_EVALUATION_COMPLETED
;
952 case MONO_RELATIONS_EVALUATION_IN_PROGRESS
: {
953 // This means we are in a recursive loop
954 MonoRelationsEvaluationContext
*current_context
= father_context
;
955 MonoRelationsEvaluationContext
*last_context
= context
->father
;
956 gboolean evaluation_can_be_recursive
= TRUE
;
957 gboolean evaluation_is_definition
= TRUE
;
960 if (TRACE_ABC_REMOVAL
) {
961 printf ("Evaluation of varible %d (target variable %d) already in progress\n", variable
, target_variable
);
962 print_evaluation_context (context
);
963 print_summarized_value_relation (context
->current_relation
);
967 // We must check if the loop can be a recursive definition (we scan the whole loop)
968 while (current_context
!= last_context
) {
969 if (current_context
== NULL
) {
970 printf ("Broken recursive ring in ABC removal\n");
971 g_assert_not_reached ();
974 if (current_context
->current_relation
->relation_is_static_definition
) {
975 if (current_context
->current_relation
->related_value
.type
== MONO_VARIABLE_SUMMARIZED_VALUE
) {
976 /* No need to check path_value for over/under-flow, since delta should be safe */
977 path_value
+= current_context
->current_relation
->related_value
.value
.variable
.delta
;
978 } else if (current_context
->current_relation
->related_value
.type
!= MONO_PHI_SUMMARIZED_VALUE
) {
979 evaluation_can_be_recursive
= FALSE
;
982 evaluation_is_definition
= FALSE
;
983 evaluation_can_be_recursive
= FALSE
;
986 current_context
= current_context
->father
;
989 // If this is a recursive definition, we properly flag the status in all the involved contexts
990 if (evaluation_is_definition
) {
991 MonoRelationsEvaluationStatus recursive_status
;
992 if (evaluation_can_be_recursive
) {
993 if (path_value
> 0) {
994 recursive_status
= MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING
;
995 } else if (path_value
< 0) {
996 recursive_status
= MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING
;
998 recursive_status
= MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE
;
1001 recursive_status
= MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE
;
1004 if (TRACE_ABC_REMOVAL
) {
1005 printf ("Recursivity accepted (");
1006 print_evaluation_context_status (recursive_status
);
1010 current_context
= father_context
;
1011 while (current_context
!= last_context
) {
1012 current_context
->status
|= recursive_status
;
1013 current_context
= current_context
->father
;
1016 if (TRACE_ABC_REMOVAL
) {
1017 printf ("Recursivity rejected (some relation in the cycle is not a defintion)\n");
1022 case MONO_RELATIONS_EVALUATION_COMPLETED
: {
1026 if (TRACE_ABC_REMOVAL
) {
1027 printf ("Varible %d (target variable %d) already in a recursive ring, skipping\n", variable
, target_variable
);
1028 print_evaluation_context (context
);
1029 print_summarized_value_relation (context
->current_relation
);
1038 * Apply the given value kind to the given range
1040 static void apply_value_kind_to_range (MonoRelationsEvaluationRange
*range
, MonoIntegerValueKind value_kind
) {
1041 if (value_kind
!= MONO_UNKNOWN_INTEGER_VALUE
) {
1042 if (value_kind
& MONO_UNSIGNED_VALUE_FLAG
) {
1043 if (range
->lower
< 0) {
1046 if ((value_kind
& MONO_INTEGER_VALUE_SIZE_BITMASK
) == 1) {
1047 if (range
->upper
> 0xff) {
1048 range
->upper
= 0xff;
1050 } else if ((value_kind
& MONO_INTEGER_VALUE_SIZE_BITMASK
) == 2) {
1051 if (range
->upper
> 0xffff) {
1052 range
->upper
= 0xffff;
1056 if ((value_kind
& MONO_INTEGER_VALUE_SIZE_BITMASK
) == 1) {
1057 if (range
->lower
< -0x80) {
1058 range
->lower
= -0x80;
1060 if (range
->upper
> 0x7f) {
1061 range
->upper
= 0x7f;
1063 } else if ((value_kind
& MONO_INTEGER_VALUE_SIZE_BITMASK
) == 2) {
1064 if (range
->lower
< -0x8000) {
1065 range
->lower
= -0x8000;
1067 if (range
->upper
> 0x7fff) {
1068 range
->upper
= 0x7fff;
1076 * Attempt the removal of bounds checks from a MonoInst.
1077 * inst: the MonoInst
1078 * area: the current evaluation area (it contains the relation graph and
1079 * memory for all the evaluation contexts is already allocated)
1082 remove_abc_from_inst (MonoInst
*inst
, MonoVariableRelationsEvaluationArea
*area
) {
1083 if (inst
->opcode
== CEE_LDELEMA
) {
1084 MonoInst
*array_inst
= inst
->inst_left
;
1085 MonoInst
*index_inst
= inst
->inst_right
;
1086 MonoSummarizedValue array_value
;
1087 MonoSummarizedValue index_value
;
1088 MonoIntegerValueKind index_value_kind
;
1090 /* First of all, examine the CEE_LDELEMA operands */
1091 summarize_array_value (area
, array_inst
, &array_value
, TRUE
);
1092 index_value_kind
= summarize_integer_value (area
, index_inst
, &index_value
, MONO_UNKNOWN_INTEGER_VALUE
);
1094 /* If the array is a local variable... */
1095 if (array_value
.type
== MONO_VARIABLE_SUMMARIZED_VALUE
) {
1096 int array_variable
= array_value
.value
.variable
.variable
;
1097 MonoRelationsEvaluationContext
*array_context
= &(area
->contexts
[array_variable
]);
1099 if (index_value
.type
== MONO_CONSTANT_SUMMARIZED_VALUE
) {
1100 // The easiest case: we just evaluate the array length, to see if it has some relation
1101 // with the index constant, and act accordingly
1103 clean_contexts (area
->contexts
, area
->cfg
->num_varinfo
);
1104 evaluate_relation_with_target_variable (area
, array_variable
, array_variable
, NULL
);
1106 if ((index_value
.value
.constant
.value
>= 0) && (index_value
.value
.constant
.value
< array_context
->ranges
.zero
.lower
)) {
1107 if (REPORT_ABC_REMOVAL
) {
1108 printf ("ARRAY-ACCESS: removed bounds check on array %d with constant index %d in method %s\n",
1109 array_variable
, index_value
.value
.constant
.value
, mono_method_full_name (area
->cfg
->method
, TRUE
));
1111 inst
->flags
|= (MONO_INST_NORANGECHECK
);
1113 } else if (index_value
.type
== MONO_VARIABLE_SUMMARIZED_VALUE
) {
1114 // The common case: we must evaluate both the index and the array length, and check for relevant
1115 // relations both through variable definitions and as constant definitions
1117 int index_variable
= index_value
.value
.variable
.variable
;
1118 MonoRelationsEvaluationContext
*index_context
= &(area
->contexts
[index_variable
]);
1120 clean_contexts (area
->contexts
, area
->cfg
->num_varinfo
);
1122 evaluate_relation_with_target_variable (area
, index_variable
, array_variable
, NULL
);
1123 evaluate_relation_with_target_variable (area
, array_variable
, array_variable
, NULL
);
1125 MONO_SUB_DELTA_SAFELY_FROM_RANGES (index_context
->ranges
, index_value
.value
.variable
.delta
);
1126 /* Apply index value kind */
1127 apply_value_kind_to_range (&(index_context
->ranges
.zero
), index_value_kind
);
1129 if (index_context
->ranges
.zero
.lower
>= 0) {
1130 if (TRACE_ABC_REMOVAL
) {
1131 printf ("ARRAY-ACCESS: Removed lower bound check on array %d with index %d\n", array_variable
, index_variable
);
1133 if ((index_context
->ranges
.variable
.upper
< 0)||(index_context
->ranges
.zero
.upper
< array_context
->ranges
.zero
.lower
)) {
1134 if (REPORT_ABC_REMOVAL
) {
1135 printf ("ARRAY-ACCESS: removed bounds check on array %d with index %d in method %s\n",
1136 array_variable
, index_variable
, mono_method_full_name (area
->cfg
->method
, TRUE
));
1138 inst
->flags
|= (MONO_INST_NORANGECHECK
);
1141 if (TRACE_ABC_REMOVAL
) {
1142 if (index_context
->ranges
.variable
.upper
< 0) {
1143 printf ("ARRAY-ACCESS: Removed upper bound check (through variable) on array %d with index %d\n", array_variable
, index_variable
);
1145 if (index_context
->ranges
.zero
.upper
< array_context
->ranges
.zero
.lower
) {
1146 printf ("ARRAY-ACCESS: Removed upper bound check (through constant) on array %d with index %d\n", array_variable
, index_variable
);
1150 } else if (array_value
.type
== MONO_CONSTANT_SUMMARIZED_VALUE
) {
1151 if (index_value
.type
== MONO_CONSTANT_SUMMARIZED_VALUE
) {
1152 /* The easiest possible case: constant with constant */
1153 if ((index_value
.value
.constant
.value
>= 0) && (index_value
.value
.constant
.value
< array_value
.value
.constant
.value
)) {
1154 if (REPORT_ABC_REMOVAL
) {
1155 printf ("ARRAY-ACCESS: removed bounds check on array of constant length %d with constant index %d in method %s\n",
1156 array_value
.value
.constant
.value
, index_value
.value
.constant
.value
, mono_method_full_name (area
->cfg
->method
, TRUE
));
1158 inst
->flags
|= (MONO_INST_NORANGECHECK
);
1160 } else if (index_value
.type
== MONO_VARIABLE_SUMMARIZED_VALUE
) {
1161 /* The index has a variable related value, which must be evaluated */
1162 int index_variable
= index_value
.value
.variable
.variable
;
1163 MonoRelationsEvaluationContext
*index_context
= &(area
->contexts
[index_variable
]);
1165 clean_contexts (area
->contexts
, area
->cfg
->num_varinfo
);
1166 evaluate_relation_with_target_variable (area
, index_variable
, index_variable
, NULL
);
1167 /* Apply index value kind */
1168 apply_value_kind_to_range (&(index_context
->ranges
.zero
), index_value_kind
);
1170 if ((index_context
->ranges
.zero
.lower
>= 0) && (index_context
->ranges
.zero
.upper
< array_value
.value
.constant
.value
)) {
1171 if (REPORT_ABC_REMOVAL
) {
1172 printf ("ARRAY-ACCESS: removed bounds check on array of constant length %d with index %d ranging from %d to %d in method %s\n",
1173 array_value
.value
.constant
.value
, index_variable
, index_context
->ranges
.zero
.lower
, index_context
->ranges
.zero
.upper
, mono_method_full_name (area
->cfg
->method
, TRUE
));
1175 inst
->flags
|= (MONO_INST_NORANGECHECK
);
1177 } else if (index_value_kind
!= MONO_UNKNOWN_INTEGER_VALUE
) {
1178 /* The index has an unknown but bounded value */
1179 MonoRelationsEvaluationRange range
;
1180 MONO_MAKE_RELATIONS_EVALUATION_RANGE_WEAK (range
);
1181 apply_value_kind_to_range (&range
, index_value_kind
);
1183 if ((range
.lower
>= 0) && (range
.upper
< array_value
.value
.constant
.value
)) {
1184 if (REPORT_ABC_REMOVAL
) {
1185 printf ("ARRAY-ACCESS: removed bounds check on array of constant length %d with unknown index ranging from %d to %d in method %s\n",
1186 array_value
.value
.constant
.value
, range
.lower
, range
.upper
, mono_method_full_name (area
->cfg
->method
, TRUE
));
1188 inst
->flags
|= (MONO_INST_NORANGECHECK
);
1196 * Recursively scan a tree of MonoInst looking for array accesses.
1197 * inst: the root of the MonoInst tree
1198 * area: the current evaluation area (it contains the relation graph and
1199 * memory for all the evaluation contexts is already allocated)
1202 process_inst (MonoInst
*inst
, MonoVariableRelationsEvaluationArea
*area
) {
1203 if (inst
->opcode
== CEE_LDELEMA
) { /* Handle OP_LDELEMA2D, too */
1204 if (TRACE_ABC_REMOVAL
) {
1205 printf ("Attempting check removal...\n");
1208 remove_abc_from_inst (inst
, area
);
1211 if (mono_burg_arity
[inst
->opcode
]) {
1212 process_inst (inst
->inst_left
, area
);
1213 if (mono_burg_arity
[inst
->opcode
] > 1) {
1214 process_inst (inst
->inst_right
, area
);
1223 * Process a BB removing bounds checks from array accesses.
1224 * It does the following (in sequence):
1225 * - Get the BB entry condition
1226 * - Add its relations to the relation graph in the evaluation area
1227 * - Process all the MonoInst trees in the BB
1228 * - Recursively process all the children BBs in the dominator tree
1229 * - Remove the relations previously added to the relation graph
1231 * bb: the BB that must be processed
1232 * area: the current evaluation area (it contains the relation graph and
1233 * memory for all the evaluation contexts is already allocated)
1236 process_block (MonoBasicBlock
*bb
, MonoVariableRelationsEvaluationArea
*area
) {
1238 MonoInst
*current_inst
;
1239 MonoAdditionalVariableRelationsForBB additional_relations
;
1240 GList
*dominated_bb
;
1242 if (TRACE_ABC_REMOVAL
) {
1243 printf ("Processing block %d [dfn %d]...\n", bb
->block_num
, bb
->dfn
);
1246 get_relations_from_previous_bb (area
, bb
, &additional_relations
);
1247 if (TRACE_ABC_REMOVAL
) {
1248 if (additional_relations
.relation1
.relation
.relation
!= MONO_ANY_RELATION
) {
1249 printf ("Adding relation 1 on variable %d: ", additional_relations
.relation1
.variable
);
1250 print_summarized_value_relation (&(additional_relations
.relation1
.relation
));
1253 if (additional_relations
.relation2
.relation
.relation
!= MONO_ANY_RELATION
) {
1254 printf ("Adding relation 2 on variable %d: ", additional_relations
.relation2
.variable
);
1255 print_summarized_value_relation (&(additional_relations
.relation2
.relation
));
1259 apply_change_to_evaluation_area (area
, &(additional_relations
.relation1
));
1260 apply_change_to_evaluation_area (area
, &(additional_relations
.relation2
));
1263 current_inst
= bb
->code
;
1264 while (current_inst
!= NULL
) {
1265 if (TRACE_ABC_REMOVAL
) {
1266 printf ("Processing instruction %d\n", inst_index
);
1270 process_inst (current_inst
, area
);
1272 current_inst
= current_inst
->next
;
1276 if (TRACE_ABC_REMOVAL
) {
1277 printf ("Processing block %d [dfn %d] done.\n", bb
->block_num
, bb
->dfn
);
1280 for (dominated_bb
= g_list_first (bb
->dominated
); dominated_bb
!= NULL
; dominated_bb
= g_list_next (dominated_bb
)) {
1281 process_block ((MonoBasicBlock
*) (dominated_bb
->data
), area
);
1284 remove_change_from_evaluation_area (&(additional_relations
.relation1
));
1285 remove_change_from_evaluation_area (&(additional_relations
.relation2
));
1291 * mono_perform_abc_removal:
1292 * @cfg: Control Flow Graph
1294 * Performs the ABC removal from a cfg in SSA form.
1295 * It does the following:
1296 * - Prepare the evaluation area
1297 * - Allocate memory for the relation graph in the evaluation area
1298 * (of course, only for variable definitions) and summarize there all
1299 * variable definitions
1300 * - Allocate memory for the evaluation contexts in the evaluation area
1301 * - Recursively process all the BBs in the dominator tree (it is enough
1302 * to invoke the processing on the entry BB)
1304 * cfg: the method code
1307 mono_perform_abc_removal (MonoCompile
*cfg
)
1309 MonoVariableRelationsEvaluationArea area
;
1312 verbose_level
= cfg
->verbose_level
;
1314 if (TRACE_ABC_REMOVAL
) {
1315 printf ("Removing array bound checks in %s\n", mono_method_full_name (cfg
->method
, TRUE
));
1319 area
.relations
= (MonoSummarizedValueRelation
*)
1320 alloca (sizeof (MonoSummarizedValueRelation
) * (cfg
->num_varinfo
) * 2);
1321 area
.contexts
= (MonoRelationsEvaluationContext
*)
1322 alloca (sizeof (MonoRelationsEvaluationContext
) * (cfg
->num_varinfo
));
1323 area
.variable_value_kind
= (MonoIntegerValueKind
*)
1324 alloca (sizeof (MonoIntegerValueKind
) * (cfg
->num_varinfo
));
1325 for (i
= 0; i
< cfg
->num_varinfo
; i
++) {
1326 area
.variable_value_kind
[i
] = MONO_UNKNOWN_INTEGER_VALUE
;
1327 area
.relations
[i
].relation
= MONO_EQ_RELATION
;
1328 area
.relations
[i
].relation_is_static_definition
= TRUE
;
1329 area
.relations
[i
].next
= NULL
;
1330 if (cfg
->vars
[i
]->def
!= NULL
) {
1331 MonoInst
*value
= get_variable_value_from_store_instruction (cfg
->vars
[i
]->def
, i
);
1332 if (value
!= NULL
) {
1333 gboolean is_array_type
;
1334 MonoIntegerValueKind effective_value_kind
;
1335 MonoRelationsEvaluationRange range
;
1336 MonoSummarizedValueRelation
*type_relation
;
1338 switch (cfg
->varinfo
[i
]->inst_vtype
->type
) {
1339 case MONO_TYPE_ARRAY
:
1340 case MONO_TYPE_SZARRAY
:
1341 is_array_type
= TRUE
;
1342 goto handle_array_value
;
1343 case MONO_TYPE_OBJECT
:
1344 is_array_type
= FALSE
;
1346 summarize_array_value (&area
, value
, &(area
.relations
[i
].related_value
), is_array_type
);
1347 if (TRACE_ABC_REMOVAL
) {
1348 printf ("Summarized variable %d as array (is_array_type = %s): ", i
, (is_array_type
?"TRUE":"FALSE"));
1349 print_summarized_value (&(area
.relations
[i
].related_value
));
1354 area
.variable_value_kind
[i
] = MONO_INTEGER_VALUE_SIZE_1
;
1355 goto handle_integer_value
;
1357 area
.variable_value_kind
[i
] = MONO_UNSIGNED_INTEGER_VALUE_SIZE_1
;
1358 goto handle_integer_value
;
1360 area
.variable_value_kind
[i
] = MONO_INTEGER_VALUE_SIZE_2
;
1361 goto handle_integer_value
;
1363 area
.variable_value_kind
[i
] = MONO_UNSIGNED_INTEGER_VALUE_SIZE_2
;
1364 goto handle_integer_value
;
1366 area
.variable_value_kind
[i
] = MONO_INTEGER_VALUE_SIZE_4
;
1367 goto handle_integer_value
;
1369 area
.variable_value_kind
[i
] = MONO_UNSIGNED_INTEGER_VALUE_SIZE_4
;
1370 goto handle_integer_value
;
1372 area
.variable_value_kind
[i
] = SIZEOF_VOID_P
;
1373 goto handle_integer_value
;
1375 area
.variable_value_kind
[i
] = (MONO_UNSIGNED_VALUE_FLAG
|SIZEOF_VOID_P
);
1376 goto handle_integer_value
;
1378 area
.variable_value_kind
[i
] = MONO_INTEGER_VALUE_SIZE_8
;
1379 goto handle_integer_value
;
1381 area
.variable_value_kind
[i
] = MONO_UNSIGNED_INTEGER_VALUE_SIZE_8
;
1382 handle_integer_value
:
1383 effective_value_kind
= summarize_integer_value (&area
, value
, &(area
.relations
[i
].related_value
), area
.variable_value_kind
[i
]);
1384 MONO_MAKE_RELATIONS_EVALUATION_RANGE_WEAK (range
);
1385 apply_value_kind_to_range (&range
, area
.variable_value_kind
[i
]);
1386 apply_value_kind_to_range (&range
, effective_value_kind
);
1388 if (range
.upper
< INT_MAX
) {
1389 type_relation
= (MonoSummarizedValueRelation
*) alloca (sizeof (MonoSummarizedValueRelation
));
1390 type_relation
->relation
= MONO_LE_RELATION
;
1391 type_relation
->related_value
.type
= MONO_CONSTANT_SUMMARIZED_VALUE
;
1392 type_relation
->related_value
.value
.constant
.value
= range
.upper
;
1393 type_relation
->relation_is_static_definition
= TRUE
;
1394 type_relation
->next
= area
.relations
[i
].next
;
1395 area
.relations
[i
].next
= type_relation
;
1396 if (TRACE_ABC_REMOVAL
) {
1397 printf ("[var%d <= %d]", i
, range
.upper
);
1400 if (range
.lower
> INT_MIN
) {
1401 type_relation
= (MonoSummarizedValueRelation
*) alloca (sizeof (MonoSummarizedValueRelation
));
1402 type_relation
->relation
= MONO_GE_RELATION
;
1403 type_relation
->related_value
.type
= MONO_CONSTANT_SUMMARIZED_VALUE
;
1404 type_relation
->related_value
.value
.constant
.value
= range
.lower
;
1405 type_relation
->relation_is_static_definition
= TRUE
;
1406 type_relation
->next
= area
.relations
[i
].next
;
1407 area
.relations
[i
].next
= type_relation
;
1408 if (TRACE_ABC_REMOVAL
) {
1409 printf ("[var%d >= %d]", i
, range
.lower
);
1412 if (TRACE_ABC_REMOVAL
) {
1413 printf ("Summarized variable %d: ", i
);
1414 print_summarized_value (&(area
.relations
[i
].related_value
));
1419 MAKE_VALUE_ANY (area
.relations
[i
].related_value
);
1420 if (TRACE_ABC_REMOVAL
) {
1421 printf ("Variable %d not handled (type %d)\n", i
, cfg
->varinfo
[i
]->inst_vtype
->type
);
1425 MAKE_VALUE_ANY (area
.relations
[i
].related_value
);
1426 if (TRACE_ABC_REMOVAL
) {
1427 printf ("Definition of variable %d is not a proper store\n", i
);
1431 MAKE_VALUE_ANY (area
.relations
[i
].related_value
);
1432 if (TRACE_ABC_REMOVAL
) {
1433 printf ("Variable %d has no definition, probably it is an argument\n", i
);
1437 for (i
= 0; i
< cfg
->num_varinfo
; i
++) {
1438 if (area
.relations
[i
].related_value
.type
== MONO_VARIABLE_SUMMARIZED_VALUE
) {
1439 int related_index
= cfg
->num_varinfo
+ i
;
1440 int related_variable
= area
.relations
[i
].related_value
.value
.variable
.variable
;
1442 area
.relations
[related_index
].relation
= MONO_EQ_RELATION
;
1443 area
.relations
[related_index
].relation_is_static_definition
= TRUE
;
1444 area
.relations
[related_index
].related_value
.type
= MONO_VARIABLE_SUMMARIZED_VALUE
;
1445 area
.relations
[related_index
].related_value
.value
.variable
.variable
= i
;
1446 area
.relations
[related_index
].related_value
.value
.variable
.delta
= - area
.relations
[i
].related_value
.value
.variable
.delta
;
1448 area
.relations
[related_index
].next
= area
.relations
[related_variable
].next
;
1449 area
.relations
[related_variable
].next
= &(area
.relations
[related_index
]);
1451 if (TRACE_ABC_REMOVAL
) {
1452 printf ("Added symmetric summarized value for variable variable %d (to %d): ", i
, related_variable
);
1453 print_summarized_value (&(area
.relations
[related_index
].related_value
));
1459 process_block (cfg
->bblocks
[0], &area
);