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>
15 #include <mono/metadata/mempool-internals.h>
21 #include "abcremoval.h"
23 #if SIZEOF_VOID_P == 8
24 #define OP_PCONST OP_I8CONST
26 #define OP_PCONST OP_ICONST
30 #define TRACE_ABC_REMOVAL (verbose_level > 2)
31 #define REPORT_ABC_REMOVAL (verbose_level > 1)
34 * A little hack for the verbosity level.
35 * The verbosity level is stored in the cfg, but not all functions that must
36 * print something see the cfg, so we store the verbosity level here at the
37 * beginning of the algorithm.
38 * This is not thread safe (does not handle correctly different verbosity
39 * levels in different threads), and is not exact in case of dynamic changes
40 * of the verbosity level...
41 * Anyway, this is not needed, all that can happen is that something more
42 * (or less) is logged, the result is in any case correct.
44 static int verbose_level;
47 #define RELATION_BETWEEN_VALUES(value,related_value) (\
48 ((value) > (related_value))? MONO_GT_RELATION :\
49 (((value) < (related_value))? MONO_LT_RELATION : MONO_EQ_RELATION))
51 #define MAKE_VALUE_ANY(v) do{\
52 (v).type = MONO_ANY_SUMMARIZED_VALUE;\
55 #define MAKE_VALUE_RELATION_ANY(r) do{\
56 (r)->relation = MONO_ANY_RELATION;\
57 MAKE_VALUE_ANY((r)->related_value);\
60 #define INITIALIZE_VALUE_RELATION(r) do{\
61 MAKE_VALUE_RELATION_ANY((r));\
65 #define MONO_NEGATED_RELATION(r) ((MonoValueRelation)((~(r))&MONO_ANY_RELATION))
66 #define MONO_SYMMETRIC_RELATION(r) ((MonoValueRelation)(((r)&MONO_EQ_RELATION)|(((r)&MONO_LT_RELATION)<<1)|((r&MONO_GT_RELATION)>>1)))
71 print_relation (int relation) {
74 if (relation & MONO_LT_RELATION) {
78 if (relation & MONO_EQ_RELATION) {
85 if (relation & MONO_GT_RELATION) {
96 print_summarized_value (MonoSummarizedValue *value) {
97 switch (value->type) {
98 case MONO_ANY_SUMMARIZED_VALUE:
101 case MONO_CONSTANT_SUMMARIZED_VALUE:
102 printf ("CONSTANT %d", value->value.constant.value);
104 case MONO_VARIABLE_SUMMARIZED_VALUE:
105 printf ("VARIABLE %d, delta %d", value->value.variable.variable, value->value.variable.delta);
107 case MONO_PHI_SUMMARIZED_VALUE: {
110 for (phi = 0; phi < value->value.phi.number_of_alternatives; phi++) {
111 if (phi) printf (",");
112 printf ("%d", value->value.phi.phi_alternatives [phi]);
118 g_assert_not_reached ();
123 print_summarized_value_relation (MonoSummarizedValueRelation *relation) {
124 printf ("Relation ");
125 print_relation (relation->relation);
126 printf (" with value ");
127 print_summarized_value (&(relation->related_value));
132 print_summarized_value_relation_chain (MonoSummarizedValueRelation *relation) {
133 printf ("Relations:\n");
135 print_summarized_value_relation (relation);
137 relation = relation->next;
143 print_evaluation_context_status (MonoRelationsEvaluationStatus status) {
144 if (status == MONO_RELATIONS_EVALUATION_NOT_STARTED) {
145 printf ("EVALUATION_NOT_STARTED");
147 gboolean print_or = FALSE;
150 if (status & MONO_RELATIONS_EVALUATION_IN_PROGRESS) {
151 if (print_or) printf ("|");
152 printf ("EVALUATION_IN_PROGRESS");
155 if (status & MONO_RELATIONS_EVALUATION_COMPLETED) {
156 if (print_or) printf ("|");
157 printf ("EVALUATION_COMPLETED");
160 if (status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING) {
161 if (print_or) printf ("|");
162 printf ("RECURSIVELY_ASCENDING");
165 if (status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING) {
166 if (print_or) printf ("|");
167 printf ("RECURSIVELY_DESCENDING");
170 if (status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE) {
171 if (print_or) printf ("|");
172 printf ("RECURSIVELY_INDEFINITE");
181 print_evaluation_context_ranges (MonoRelationsEvaluationRanges *ranges) {
182 printf ("(ranges: zero [%d,%d], variable [%d,%d])", ranges->zero.lower, ranges->zero.upper, ranges->variable.lower, ranges->variable.upper);
186 print_evaluation_context (MonoRelationsEvaluationContext *context, MonoRelationsEvaluationStatus status) {
187 print_evaluation_context_status (status);
188 if (status & (MONO_RELATIONS_EVALUATION_IN_PROGRESS|MONO_RELATIONS_EVALUATION_COMPLETED)) {
189 print_evaluation_context_ranges (&(context->ranges));
196 print_evaluation_area (MonoVariableRelationsEvaluationArea *area) {
198 printf ("Dump of evaluation area (%d variables):\n", area->cfg->num_varinfo);
199 for (i = 0; i < area->cfg->num_varinfo; i++) {
200 printf ("Variable %d: ", i);
201 print_evaluation_context (&(area->contexts [i]));
202 print_summarized_value_relation_chain (&(area->relations [i]));
207 print_evaluation_area_contexts (MonoVariableRelationsEvaluationArea *area) {
209 printf ("Dump of evaluation area contexts (%d variables):\n", area->cfg->num_varinfo);
210 for (i = 0; i < area->cfg->num_varinfo; i++) {
211 printf ("Variable %d: ", i);
212 print_evaluation_context (&(area->contexts [i]));
218 * Check if the delta of an integer variable value is safe with respect
219 * to the variable size in bytes and its kind (signed or unsigned).
220 * If the delta is not safe, make the value an "any".
222 static G_GNUC_UNUSED void
223 check_delta_safety (MonoVariableRelationsEvaluationArea *area, MonoSummarizedValue *value) {
224 if (value->type == MONO_VARIABLE_SUMMARIZED_VALUE) {
225 int variable = value->value.variable.variable;
226 int delta = value->value.variable.delta;
227 if ((area->variable_value_kind [variable]) & MONO_UNSIGNED_VALUE_FLAG) {
229 MAKE_VALUE_ANY (*value);
232 if (((area->variable_value_kind [variable]) & MONO_INTEGER_VALUE_SIZE_BITMASK) < 4) {
233 MAKE_VALUE_ANY (*value);
234 } else if (delta > 16) {
235 MAKE_VALUE_ANY (*value);
242 * get_relation_from_ins:
244 * Obtain relations from a MonoInst.
246 * result_value_kind: the "expected" kind of result;
247 * result: the "summarized" value
248 * returns the "actual" kind of result, if guessable (otherwise MONO_UNKNOWN_INTEGER_VALUE)
250 static MonoIntegerValueKind
251 get_relation_from_ins (MonoVariableRelationsEvaluationArea *area, MonoInst *ins, MonoSummarizedValueRelation *result, MonoIntegerValueKind result_value_kind)
253 MonoIntegerValueKind value_kind;
254 MonoSummarizedValue *value = &result->related_value;
256 if (ins->type == STACK_I8) {
257 value_kind = MONO_INTEGER_VALUE_SIZE_8;
258 } else if (ins->type == STACK_I4) {
259 value_kind = MONO_INTEGER_VALUE_SIZE_4;
261 value_kind = MONO_UNKNOWN_INTEGER_VALUE;
264 result->relation = MONO_EQ_RELATION;
265 MAKE_VALUE_ANY (*value);
267 switch (ins->opcode) {
269 value->type = MONO_CONSTANT_SUMMARIZED_VALUE;
270 value->value.constant.value = ins->inst_c0;
273 value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
274 value->value.variable.variable = ins->sreg1;
275 value->value.variable.delta = 0;
278 value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
279 value->value.variable.variable = ins->sreg1;
280 value->value.variable.delta = 0;
281 value_kind = MONO_INTEGER_VALUE_SIZE_8;
284 value->type = MONO_PHI_SUMMARIZED_VALUE;
285 value->value.phi.number_of_alternatives = *(ins->inst_phi_args);
286 value->value.phi.phi_alternatives = ins->inst_phi_args + 1;
289 value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
290 value->value.variable.variable = ins->sreg1;
291 value->value.variable.delta = ins->inst_imm;
293 //check_delta_safety (area, result);
296 value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
297 value->value.variable.variable = ins->sreg1;
298 value->value.variable.delta = -ins->inst_imm;
300 //check_delta_safety (area, result);
303 /* The result of an unsigned remainder is 0 < x < the divisor */
304 result->relation = MONO_LT_RELATION;
305 value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
306 value->value.variable.variable = ins->sreg2;
307 value->value.variable.delta = 0;
308 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_4;
312 * We represent arrays by their length, so r1<-ldlen r2 is stored
313 * as r1 == r2 in the evaluation graph.
315 value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
316 value->value.variable.variable = ins->sreg1;
317 value->value.variable.delta = 0;
318 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_4;
321 value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
322 value->value.variable.variable = ins->sreg1;
323 value->value.variable.delta = 0;
324 area->defs [ins->dreg] = ins;
327 /* The result is non-null */
328 result->relation = MONO_GT_RELATION;
329 value->type = MONO_CONSTANT_SUMMARIZED_VALUE;
330 value->value.constant.value = 0;
333 /* FIXME: Add more opcodes */
335 /* These opcodes are not currently handled while running SciMark, first
336 * column is the number of times the warning was shown:
368 * 12 outarg_vtretaddr
396 static MonoValueRelation
397 get_relation_from_branch_instruction (MonoInst *ins)
399 if (MONO_IS_COND_BRANCH_OP (ins)) {
400 CompRelation rel = mono_opcode_to_cond (ins->opcode);
404 return MONO_EQ_RELATION;
406 return MONO_NE_RELATION;
409 return MONO_LE_RELATION;
412 return MONO_GE_RELATION;
415 return MONO_LT_RELATION;
418 return MONO_GT_RELATION;
420 g_assert_not_reached ();
421 return MONO_ANY_RELATION;
424 return MONO_ANY_RELATION;
429 * Given a BB, find its entry condition and put its relations in a
430 * "MonoAdditionalVariableRelationsForBB" structure.
432 * relations: the resulting relations (entry condition of the given BB)
435 get_relations_from_previous_bb (MonoVariableRelationsEvaluationArea *area, MonoBasicBlock *bb, MonoAdditionalVariableRelationsForBB *relations)
437 MonoBasicBlock *in_bb;
438 MonoInst *ins, *compare, *branch;
439 MonoValueRelation branch_relation;
440 MonoValueRelation symmetric_relation;
443 INITIALIZE_VALUE_RELATION (&(relations->relation1.relation));
444 relations->relation1.relation.relation_is_static_definition = FALSE;
445 relations->relation1.relation.next = NULL;
446 relations->relation1.insertion_point = NULL;
447 relations->relation1.variable = -1;
448 INITIALIZE_VALUE_RELATION (&(relations->relation2.relation));
449 relations->relation2.relation.relation_is_static_definition = FALSE;
450 relations->relation2.relation.next = NULL;
451 relations->relation2.insertion_point = NULL;
452 relations->relation2.variable = -1;
454 if (bb->in_count == 1) { /* Should write the code to "sum" conditions... */
455 in_bb = bb->in_bb [0];
457 if ((in_bb->last_ins == NULL) || (in_bb->code == in_bb->last_ins))
460 for (ins = in_bb->code; ins->next != in_bb->last_ins; ins = ins->next)
465 branch_relation = get_relation_from_branch_instruction (branch);
467 if (branch_relation != MONO_ANY_RELATION) {
468 if (branch->inst_true_bb == bb) {
470 } else if (branch->inst_false_bb == bb) {
474 g_assert_not_reached ();
477 branch_relation = MONO_NEGATED_RELATION (branch_relation);
478 symmetric_relation = MONO_SYMMETRIC_RELATION (branch_relation);
480 /* FIXME: Other compare opcodes */
481 if (compare->opcode == OP_ICOMPARE) {
482 relations->relation1.variable = compare->sreg1;
483 relations->relation1.relation.relation = branch_relation;
484 relations->relation1.relation.related_value.type = MONO_VARIABLE_SUMMARIZED_VALUE;
485 relations->relation1.relation.related_value.value.variable.variable = compare->sreg2;
486 relations->relation1.relation.related_value.value.variable.delta = 0;
488 relations->relation2.variable = compare->sreg2;
489 relations->relation2.relation.relation = symmetric_relation;
490 relations->relation2.relation.related_value.type = MONO_VARIABLE_SUMMARIZED_VALUE;
491 relations->relation2.relation.related_value.value.variable.variable = compare->sreg1;
492 relations->relation2.relation.related_value.value.variable.delta = 0;
493 } else if (compare->opcode == OP_ICOMPARE_IMM) {
494 relations->relation1.variable = compare->sreg1;
495 relations->relation1.relation.relation = branch_relation;
496 relations->relation1.relation.related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE;
497 relations->relation1.relation.related_value.value.constant.value = compare->inst_imm;
504 * Add the given relations to the evaluation area.
505 * area: the evaluation area
506 * change: the relations that must be added
509 apply_change_to_evaluation_area (MonoVariableRelationsEvaluationArea *area, MonoAdditionalVariableRelation *change)
511 MonoSummarizedValueRelation *base_relation;
513 if (change->relation.relation != MONO_ANY_RELATION) {
514 base_relation = &(area->relations [change->variable]);
515 while ((base_relation->next != NULL) && (base_relation->next->relation_is_static_definition)) {
516 base_relation = base_relation->next;
518 change->insertion_point = base_relation;
519 change->relation.next = base_relation->next;
520 base_relation->next = &(change->relation);
525 * Remove the given relation from the evaluation area.
526 * change: the relation that must be removed
529 remove_change_from_evaluation_area (MonoAdditionalVariableRelation *change)
531 if (change->insertion_point != NULL) {
532 change->insertion_point->next = change->relation.next;
533 change->relation.next = NULL;
539 clean_contexts (MonoVariableRelationsEvaluationArea *area, int number)
541 memset(area->statuses, MONO_RELATIONS_EVALUATION_NOT_STARTED, number * sizeof(MonoRelationsEvaluationStatus));
546 * Perform the intersection of a range and a constant value (taking into
547 * account the relation that the value has with the range).
548 * range: the range that will be intersected with the value
549 * value: the value that will be intersected with the range
550 * relation: the relation between the range and the value
553 intersect_value( MonoRelationsEvaluationRange *range, int value, MonoValueRelation relation )
556 case MONO_NO_RELATION:
557 MONO_MAKE_RELATIONS_EVALUATION_RANGE_IMPOSSIBLE (*range);
559 case MONO_ANY_RELATION:
561 case MONO_EQ_RELATION:
562 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, value);
563 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, value);
565 case MONO_NE_RELATION: {
566 /* IMPROVEMENT Figure this out! (ignoring it is safe anyway) */
569 case MONO_LT_RELATION:
570 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (value));
572 case MONO_LE_RELATION:
573 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, value);
575 case MONO_GT_RELATION:
576 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (value));
578 case MONO_GE_RELATION:
579 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, value);
582 g_assert_not_reached();
588 * Perform the intersection of two pairs of ranges (taking into account the
589 * relation between the ranges and a given delta).
590 * ranges: the ranges that will be intersected
591 * other_ranges the other ranges that will be intersected
592 * delta: the delta between the pairs of ranges
593 * relation: the relation between the pairs of ranges
596 intersect_ranges( MonoRelationsEvaluationRanges *ranges, MonoRelationsEvaluationRanges *other_ranges, int delta, MonoValueRelation relation )
600 case MONO_NO_RELATION:
601 MONO_MAKE_RELATIONS_EVALUATION_RANGES_IMPOSSIBLE (*ranges);
603 case MONO_ANY_RELATION:
605 case MONO_EQ_RELATION:
606 MONO_RELATIONS_EVALUATION_RANGES_INTERSECTION (*ranges, *other_ranges);
608 case MONO_NE_RELATION: {
609 /* FIXME Figure this out! (ignoring it is safe anyway) */
612 case MONO_LT_RELATION:
613 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->zero.upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->zero.upper));
614 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->variable.upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->variable.upper));
616 case MONO_LE_RELATION:
617 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->zero.upper, other_ranges->zero.upper);
618 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->variable.upper, other_ranges->variable.upper);
620 case MONO_GT_RELATION:
621 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->zero.lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->zero.lower));
622 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->variable.lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->variable.lower));
624 case MONO_GE_RELATION:
625 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->zero.lower, other_ranges->zero.lower);
626 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->variable.lower, other_ranges->variable.lower);
629 g_assert_not_reached();
632 MonoRelationsEvaluationRanges translated_ranges = *other_ranges;
633 MONO_ADD_DELTA_SAFELY_TO_RANGES (translated_ranges, delta);
634 intersect_ranges( ranges, &translated_ranges, FALSE, relation );
639 * Recursive method that traverses the relation graph to evaluate the
640 * relation between two variables.
641 * At the end of the execution, the resulting ranges are in the context of
642 * the "starting" variable.
643 * area: the current evaluation area (it contains the relation graph and
644 * memory for all the evaluation contexts is already allocated)
645 * variable: starting variable (the value ranges in its context are the result
646 * of the execution of this procedure)
647 * target_variable: the variable with respect to which the starting variable
648 * is evaluated (tipically the starting variable is the index
649 * and the target one is the array (which means its length))
650 * father_context: the previous evaluation context in recursive invocations
651 * (or NULL for the first invocation)
654 evaluate_relation_with_target_variable (MonoVariableRelationsEvaluationArea *area, const int variable, const int target_variable, MonoRelationsEvaluationContext *father_context)
656 MonoRelationsEvaluationContext * const context = &(area->contexts [variable]);
657 MonoRelationsEvaluationStatus * const status = &(area->statuses [variable]);
659 // First of all, we check the evaluation status
660 // (what must be done is *very* different in each case)
662 case MONO_RELATIONS_EVALUATION_NOT_STARTED: {
663 MonoSummarizedValueRelation *relation = &(area->relations [variable]);
665 if (TRACE_ABC_REMOVAL) {
666 printf ("Evaluating variable %d (target variable %d)\n", variable, target_variable);
667 print_summarized_value_relation (relation);
671 // We properly inizialize the context
672 *status = MONO_RELATIONS_EVALUATION_IN_PROGRESS;
673 context->father = father_context;
674 MONO_MAKE_RELATIONS_EVALUATION_RANGES_WEAK (context->ranges);
676 // If we have found the target variable, we can set the range
677 // related to it in the context to "equal" (which is [0,0])
678 if (variable == target_variable) {
679 if (TRACE_ABC_REMOVAL) {
680 printf ("Target variable reached (%d), continuing to evaluate relations with constants\n", variable);
682 context->ranges.variable.lower = 0;
683 context->ranges.variable.upper = 0;
686 // Examine all relations for this variable (scan the list)
687 // The contribute of each relation will be intersected (logical and)
688 while (relation != NULL) {
689 context->current_relation = relation;
691 if (TRACE_ABC_REMOVAL) {
692 printf ("Processing (%d): ", variable);
693 print_summarized_value_relation (relation);
697 // We decie what to do according the the type of the related value
698 switch (relation->related_value.type) {
699 case MONO_ANY_SUMMARIZED_VALUE:
700 // No added information, skip it
702 case MONO_CONSTANT_SUMMARIZED_VALUE:
703 // Intersect range with constant (taking into account the relation)
704 intersect_value (&(context->ranges.zero), relation->related_value.value.constant.value, relation->relation);
706 case MONO_VARIABLE_SUMMARIZED_VALUE:
707 // Generally, evaluate related variable and intersect ranges.
708 // However, some check is necessary...
710 // If the relation is "ANY", nothing to do (no added information)
711 if (relation->relation != MONO_ANY_RELATION) {
712 int related_variable = relation->related_value.value.variable.variable;
713 MonoRelationsEvaluationContext *related_context = &(area->contexts [related_variable]);
714 MonoRelationsEvaluationStatus related_status = area->statuses [related_variable];
716 // The second condition in the "or" avoids messing with "back edges" in the graph traversal
717 // (they are simply ignored instead of triggering the handling of recursion)
718 if ( (related_status == MONO_RELATIONS_EVALUATION_NOT_STARTED) || !
719 ((related_context->current_relation->related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) &&
720 (related_context->current_relation->related_value.value.variable.variable == variable))) {
721 // Evaluate the related variable
722 evaluate_relation_with_target_variable (area, related_variable, target_variable, context);
724 // Check if we are part of a recursive loop
725 if (*status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) {
726 if (TRACE_ABC_REMOVAL) {
727 printf ("Recursivity detected for variable %d (target variable %d), status ", variable, target_variable);
728 print_evaluation_context_status (*status);
731 // If we are, check if the evaluation of the related variable is complete
732 if (related_status == MONO_RELATIONS_EVALUATION_COMPLETED) {
733 // If it is complete, we are part of a recursive definition.
734 // Since it is a *definition* (and definitions are evaluated *before*
735 // conditions because they are first in the list), intersection is not
736 // strictly necessary, we simply copy the ranges and apply the delta
737 context->ranges = related_context->ranges;
738 /* Delta has already been checked for over/under-flow when evaluating values */
739 MONO_ADD_DELTA_SAFELY_TO_RANGES (context->ranges, relation->related_value.value.variable.delta);
740 *status = MONO_RELATIONS_EVALUATION_COMPLETED;
741 if (TRACE_ABC_REMOVAL) {
742 printf (", ranges already computed, result: \n");
743 print_evaluation_context_ranges (&(context->ranges));
744 printf (" (delta is %d)\n", relation->related_value.value.variable.delta);
747 // If it is not complete, do nothing (we do not have enough information)
748 if (TRACE_ABC_REMOVAL) {
749 printf (", ranges not computed\n");
753 // If we are not (the common case) intersect the result
754 intersect_ranges( &(context->ranges), &(related_context->ranges), relation->related_value.value.variable.delta, relation->relation );
757 if (TRACE_ABC_REMOVAL) {
758 printf ("Relation is a back-edge in this traversal, skipping\n");
763 case MONO_PHI_SUMMARIZED_VALUE: {
764 // We must compute all PHI alternatives, combining the results (with a union, which is a logical "or"),
765 // and intersect this result with the ranges in the context; we must also take into account recursions
766 // (with loops that can be ascending, descending, or indefinite)
767 MonoRelationsEvaluationRanges phi_ranges;
769 gboolean is_ascending = FALSE;
770 gboolean is_descending = FALSE;
772 MONO_MAKE_RELATIONS_EVALUATION_RANGES_IMPOSSIBLE (phi_ranges);
773 for (phi = 0; phi < relation->related_value.value.phi.number_of_alternatives; phi++) {
774 int phi_alternative = relation->related_value.value.phi.phi_alternatives [phi];
775 evaluate_relation_with_target_variable (area, phi_alternative, target_variable, context);
777 // This means we are part of a recursive loop
778 if (*status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) {
779 if (TRACE_ABC_REMOVAL) {
780 printf ("Recursivity detected for variable %d (target variable %d), status ", variable, target_variable);
781 print_evaluation_context_status (*status);
784 if (*status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING) {
787 if (*status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING) {
788 is_descending = TRUE;
790 if (*status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE) {
792 is_descending = TRUE;
795 // Clear "recursivity" bits in the status (recursion has been handled)
796 *status = MONO_RELATIONS_EVALUATION_IN_PROGRESS;
798 MONO_RELATIONS_EVALUATION_RANGES_UNION (phi_ranges, area->contexts [phi_alternative].ranges);
802 // Apply the effects of all recursive loops
804 phi_ranges.zero.upper = INT_MAX;
805 phi_ranges.variable.upper = INT_MAX;
808 phi_ranges.zero.lower = INT_MIN;
809 phi_ranges.variable.lower = INT_MIN;
812 // Intersect final result
813 MONO_RELATIONS_EVALUATION_RANGES_INTERSECTION (context->ranges, phi_ranges);
817 g_assert_not_reached();
820 // Pass to next relation
821 relation = relation->next;
824 // Check if any recursivity bits are still in the status, and in any case clear them
825 if (*status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) {
826 if (TRACE_ABC_REMOVAL) {
827 printf ("Recursivity for variable %d (target variable %d) discards computation, status ", variable, target_variable);
828 print_evaluation_context_status (*status);
831 // If yes, we did not have enough information (most likely we were evaluated inside a PHI, but we also
832 // depended on the same PHI, which was still in evaluation...), so clear the status to "NOT_STARTED"
833 // (if we will be evaluated again, the PHI will be already done, so our evaluation will succeed)
834 *status = MONO_RELATIONS_EVALUATION_NOT_STARTED;
836 if (TRACE_ABC_REMOVAL) {
837 printf ("Ranges for variable %d (target variable %d) computed: ", variable, target_variable);
838 print_evaluation_context_ranges (&(context->ranges));
841 // If not (the common case) the evaluation is complete, and the result is in the context
842 *status = MONO_RELATIONS_EVALUATION_COMPLETED;
846 case MONO_RELATIONS_EVALUATION_IN_PROGRESS: {
847 // This means we are in a recursive loop
848 MonoRelationsEvaluationContext *current_context = father_context;
849 MonoRelationsEvaluationContext *last_context = context->father;
850 gboolean evaluation_can_be_recursive = TRUE;
851 gboolean evaluation_is_definition = TRUE;
854 if (TRACE_ABC_REMOVAL) {
855 printf ("Evaluation of variable %d (target variable %d) already in progress\n", variable, target_variable);
856 print_evaluation_context (context, *status);
857 print_summarized_value_relation (context->current_relation);
861 // We must check if the loop can be a recursive definition (we scan the whole loop)
862 while (current_context != last_context) {
863 if (current_context == NULL) {
864 printf ("Broken recursive ring in ABC removal\n");
865 g_assert_not_reached ();
868 if (current_context->current_relation->relation_is_static_definition) {
869 if (current_context->current_relation->related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
870 /* No need to check path_value for over/under-flow, since delta should be safe */
871 path_value += current_context->current_relation->related_value.value.variable.delta;
872 } else if (current_context->current_relation->related_value.type != MONO_PHI_SUMMARIZED_VALUE) {
873 evaluation_can_be_recursive = FALSE;
876 evaluation_is_definition = FALSE;
877 evaluation_can_be_recursive = FALSE;
880 current_context = current_context->father;
883 // If this is a recursive definition, we properly flag the status in all the involved contexts
884 if (evaluation_is_definition) {
885 MonoRelationsEvaluationStatus recursive_status;
886 if (evaluation_can_be_recursive) {
887 if (path_value > 0) {
888 recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING;
889 } else if (path_value < 0) {
890 recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING;
892 recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE;
895 recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE;
898 if (TRACE_ABC_REMOVAL) {
899 printf ("Recursivity accepted (");
900 print_evaluation_context_status (recursive_status);
904 current_context = father_context;
905 while (current_context != last_context) {
906 int index = father_context - area->contexts;
907 MonoRelationsEvaluationStatus *current_status = &(area->statuses [index]);
908 *current_status = (MonoRelationsEvaluationStatus)(*current_status | recursive_status);
909 current_context = current_context->father;
912 if (TRACE_ABC_REMOVAL) {
913 printf ("Recursivity rejected (some relation in the cycle is not a defintion)\n");
918 case MONO_RELATIONS_EVALUATION_COMPLETED: {
922 if (TRACE_ABC_REMOVAL) {
923 printf ("Variable %d (target variable %d) already in a recursive ring, skipping\n", variable, target_variable);
924 print_evaluation_context (context, *status);
925 print_summarized_value_relation (context->current_relation);
934 * Apply the given value kind to the given range
937 apply_value_kind_to_range (MonoRelationsEvaluationRange *range, MonoIntegerValueKind value_kind)
939 if (value_kind != MONO_UNKNOWN_INTEGER_VALUE) {
940 if (value_kind & MONO_UNSIGNED_VALUE_FLAG) {
941 if (range->lower < 0) {
944 if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 1) {
945 if (range->upper > 0xff) {
948 } else if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 2) {
949 if (range->upper > 0xffff) {
950 range->upper = 0xffff;
954 if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 1) {
955 if (range->lower < -0x80) {
956 range->lower = -0x80;
958 if (range->upper > 0x7f) {
961 } else if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 2) {
962 if (range->lower < -0x8000) {
963 range->lower = -0x8000;
965 if (range->upper > 0x7fff) {
966 range->upper = 0x7fff;
974 * Attempt the removal of bounds checks from a MonoInst.
976 * area: the current evaluation area (it contains the relation graph and
977 * memory for all the evaluation contexts is already allocated)
980 remove_abc_from_inst (MonoInst *ins, MonoVariableRelationsEvaluationArea *area)
982 /* FIXME: Add support for 'constant' arrays and constant indexes */
984 int array_variable = ins->sreg1;
985 int index_variable = ins->sreg2;
986 MonoRelationsEvaluationContext *array_context = &(area->contexts [array_variable]);
987 MonoRelationsEvaluationContext *index_context = &(area->contexts [index_variable]);
989 clean_contexts (area, area->cfg->next_vreg);
991 evaluate_relation_with_target_variable (area, index_variable, array_variable, NULL);
992 evaluate_relation_with_target_variable (area, array_variable, array_variable, NULL);
994 if ((index_context->ranges.zero.lower >=0) && ((index_context->ranges.variable.upper < 0)||(index_context->ranges.zero.upper < array_context->ranges.zero.lower))) {
995 if (REPORT_ABC_REMOVAL) {
996 printf ("ARRAY-ACCESS: removed bounds check on array %d with index %d\n",
997 array_variable, index_variable);
1001 if (TRACE_ABC_REMOVAL) {
1002 if (index_context->ranges.zero.lower >= 0) {
1003 printf ("ARRAY-ACCESS: Removed lower bound check on array %d with index %d\n", array_variable, index_variable);
1005 if (index_context->ranges.variable.upper < 0) {
1006 printf ("ARRAY-ACCESS: Removed upper bound check (through variable) on array %d with index %d\n", array_variable, index_variable);
1008 if (index_context->ranges.zero.upper < array_context->ranges.zero.lower) {
1009 printf ("ARRAY-ACCESS: Removed upper bound check (through constant) on array %d with index %d\n", array_variable, index_variable);
1016 eval_non_null (MonoVariableRelationsEvaluationArea *area, int reg)
1018 MonoRelationsEvaluationContext *context = &(area->contexts [reg]);
1020 clean_contexts (area, area->cfg->next_vreg);
1021 evaluate_relation_with_target_variable (area, reg, reg, NULL);
1023 return context->ranges.zero.lower > 0;
1027 add_non_null (MonoVariableRelationsEvaluationArea *area, MonoCompile *cfg, int reg,
1028 GSList **check_relations)
1030 MonoAdditionalVariableRelation *rel;
1032 rel = (MonoAdditionalVariableRelation *)mono_mempool_alloc0 (cfg->mempool, sizeof (MonoAdditionalVariableRelation));
1033 rel->variable = reg;
1034 rel->relation.relation = MONO_GT_RELATION;
1035 rel->relation.related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE;
1036 rel->relation.related_value.value.constant.value = 0;
1038 apply_change_to_evaluation_area (area, rel);
1040 *check_relations = g_slist_append_mempool (cfg->mempool, *check_relations, rel);
1044 * Process a BB removing bounds checks from array accesses.
1045 * It does the following (in sequence):
1046 * - Get the BB entry condition
1047 * - Add its relations to the relation graph in the evaluation area
1048 * - Process all the MonoInst trees in the BB
1049 * - Recursively process all the children BBs in the dominator tree
1050 * - Remove the relations previously added to the relation graph
1052 * bb: the BB that must be processed
1053 * area: the current evaluation area (it contains the relation graph and
1054 * memory for all the evaluation contexts is already allocated)
1057 process_block (MonoCompile *cfg, MonoBasicBlock *bb, MonoVariableRelationsEvaluationArea *area) {
1060 MonoAdditionalVariableRelationsForBB additional_relations;
1061 GSList *dominated_bb, *l;
1062 GSList *check_relations = NULL;
1064 if (TRACE_ABC_REMOVAL) {
1065 printf ("\nProcessing block %d [dfn %d]...\n", bb->block_num, bb->dfn);
1068 if (bb->region != -1)
1071 get_relations_from_previous_bb (area, bb, &additional_relations);
1072 if (TRACE_ABC_REMOVAL) {
1073 if (additional_relations.relation1.relation.relation != MONO_ANY_RELATION) {
1074 printf ("Adding relation 1 on variable %d: ", additional_relations.relation1.variable);
1075 print_summarized_value_relation (&(additional_relations.relation1.relation));
1078 if (additional_relations.relation2.relation.relation != MONO_ANY_RELATION) {
1079 printf ("Adding relation 2 on variable %d: ", additional_relations.relation2.variable);
1080 print_summarized_value_relation (&(additional_relations.relation2.relation));
1084 apply_change_to_evaluation_area (area, &(additional_relations.relation1));
1085 apply_change_to_evaluation_area (area, &(additional_relations.relation2));
1088 for (ins = bb->code; ins; ins = ins->next) {
1089 MonoAdditionalVariableRelation *rel;
1090 int array_var, index_var;
1092 if (TRACE_ABC_REMOVAL) {
1093 printf ("Processing instruction %d\n", inst_index);
1097 if (ins->opcode == OP_BOUNDS_CHECK) { /* Handle OP_LDELEMA2D, too */
1098 if (TRACE_ABC_REMOVAL) {
1099 printf ("Attempting check removal...\n");
1102 array_var = ins->sreg1;
1103 index_var = ins->sreg2;
1105 remove_abc_from_inst (ins, area);
1107 /* We can derive additional relations from the bounds check */
1108 if (ins->opcode != OP_NOP) {
1109 rel = (MonoAdditionalVariableRelation *)mono_mempool_alloc0 (cfg->mempool, sizeof (MonoAdditionalVariableRelation));
1110 rel->variable = index_var;
1111 rel->relation.relation = MONO_LT_RELATION;
1112 rel->relation.related_value.type = MONO_VARIABLE_SUMMARIZED_VALUE;
1113 rel->relation.related_value.value.variable.variable = array_var;
1114 rel->relation.related_value.value.variable.delta = 0;
1116 apply_change_to_evaluation_area (area, rel);
1118 check_relations = g_slist_append_mempool (cfg->mempool, check_relations, rel);
1120 rel = (MonoAdditionalVariableRelation *)mono_mempool_alloc0 (cfg->mempool, sizeof (MonoAdditionalVariableRelation));
1121 rel->variable = index_var;
1122 rel->relation.relation = MONO_GE_RELATION;
1123 rel->relation.related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE;
1124 rel->relation.related_value.value.constant.value = 0;
1126 apply_change_to_evaluation_area (area, rel);
1128 check_relations = g_slist_append_mempool (cfg->mempool, check_relations, rel);
1132 if (ins->opcode == OP_CHECK_THIS) {
1133 if (eval_non_null (area, ins->sreg1)) {
1134 if (REPORT_ABC_REMOVAL)
1135 printf ("ARRAY-ACCESS: removed check_this instruction.\n");
1140 if (ins->opcode == OP_NOT_NULL)
1141 add_non_null (area, cfg, ins->sreg1, &check_relations);
1144 * FIXME: abcrem equates an array with its length,
1145 * so a = new int [100] implies a != null, but a = new int [0] doesn't.
1148 * Eliminate MONO_INST_FAULT flags if possible.
1150 if (COMPILE_LLVM (cfg) && (ins->opcode == OP_LDLEN ||
1151 ins->opcode == OP_BOUNDS_CHECK ||
1152 ins->opcode == OP_STRLEN ||
1153 (MONO_IS_LOAD_MEMBASE (ins) && (ins->flags & MONO_INST_FAULT)) ||
1154 (MONO_IS_STORE_MEMBASE (ins) && (ins->flags & MONO_INST_FAULT)))) {
1157 if (MONO_IS_STORE_MEMBASE (ins))
1158 reg = ins->inst_destbasereg;
1159 else if (MONO_IS_LOAD_MEMBASE (ins))
1160 reg = ins->inst_basereg;
1165 * This doesn't work because LLVM can move the non-faulting loads before the faulting
1166 * ones (test_0_llvm_moving_faulting_loads ()).
1167 * So only do it if we know the load cannot be moved before the instruction which ensures it is not
1168 * null (i.e. the def of its sreg).
1170 if (area->defs [reg] && area->defs [reg]->opcode == OP_NEWARR) {
1171 if (REPORT_ABC_REMOVAL)
1172 printf ("ARRAY-ACCESS: removed MONO_INST_FAULT flag.\n");
1173 ins->flags &= ~MONO_INST_FAULT;
1176 if (eval_non_null (area, reg)) {
1177 if (REPORT_ABC_REMOVAL)
1178 printf ("ARRAY-ACCESS: removed MONO_INST_FAULT flag.\n");
1179 ins->flags &= ~MONO_INST_FAULT;
1181 add_non_null (area, cfg, reg, &check_relations);
1187 if (TRACE_ABC_REMOVAL) {
1188 printf ("Processing block %d [dfn %d] done.\n", bb->block_num, bb->dfn);
1191 for (dominated_bb = bb->dominated; dominated_bb != NULL; dominated_bb = dominated_bb->next) {
1192 process_block (cfg, (MonoBasicBlock*) (dominated_bb->data), area);
1195 for (l = check_relations; l; l = l->next)
1196 remove_change_from_evaluation_area ((MonoAdditionalVariableRelation *)l->data);
1198 remove_change_from_evaluation_area (&(additional_relations.relation1));
1199 remove_change_from_evaluation_area (&(additional_relations.relation2));
1202 static MonoIntegerValueKind
1203 type_to_value_kind (MonoType *type)
1206 return MONO_UNKNOWN_INTEGER_VALUE;
1207 switch (type->type) {
1209 return MONO_INTEGER_VALUE_SIZE_1;
1212 return MONO_UNSIGNED_INTEGER_VALUE_SIZE_1;
1215 return MONO_INTEGER_VALUE_SIZE_2;
1218 return MONO_UNSIGNED_INTEGER_VALUE_SIZE_2;
1221 return MONO_INTEGER_VALUE_SIZE_4;
1224 return MONO_UNSIGNED_INTEGER_VALUE_SIZE_4;
1227 return (MonoIntegerValueKind)SIZEOF_VOID_P;
1230 return (MonoIntegerValueKind)(MONO_UNSIGNED_VALUE_FLAG | SIZEOF_VOID_P);
1233 return MONO_INTEGER_VALUE_SIZE_8;
1236 return MONO_UNSIGNED_INTEGER_VALUE_SIZE_8;
1238 return MONO_UNKNOWN_INTEGER_VALUE;
1243 * mono_perform_abc_removal:
1244 * @cfg: Control Flow Graph
1246 * Performs the ABC removal from a cfg in SSA form.
1247 * It does the following:
1248 * - Prepare the evaluation area
1249 * - Allocate memory for the relation graph in the evaluation area
1250 * (of course, only for variable definitions) and summarize there all
1251 * variable definitions
1252 * - Allocate memory for the evaluation contexts in the evaluation area
1253 * - Recursively process all the BBs in the dominator tree (it is enough
1254 * to invoke the processing on the entry BB)
1256 * cfg: the method code
1259 mono_perform_abc_removal (MonoCompile *cfg)
1261 MonoVariableRelationsEvaluationArea area;
1265 verbose_level = cfg->verbose_level;
1267 if (TRACE_ABC_REMOVAL) {
1268 printf ("\nRemoving array bound checks in %s\n", mono_method_full_name (cfg->method, TRUE));
1272 area.relations = (MonoSummarizedValueRelation *)
1273 mono_mempool_alloc (cfg->mempool, sizeof (MonoSummarizedValueRelation) * (cfg->next_vreg) * 2);
1275 area.contexts = (MonoRelationsEvaluationContext *)
1276 mono_mempool_alloc0 (cfg->mempool, sizeof (MonoRelationsEvaluationContext) * (cfg->next_vreg));
1278 area.statuses = (MonoRelationsEvaluationStatus *)
1279 mono_mempool_alloc0 (cfg->mempool, sizeof (MonoRelationsEvaluationStatus) * (cfg->next_vreg));
1281 area.variable_value_kind = (MonoIntegerValueKind *)
1282 mono_mempool_alloc (cfg->mempool, sizeof (MonoIntegerValueKind) * (cfg->next_vreg));
1283 area.defs = (MonoInst **)mono_mempool_alloc (cfg->mempool, sizeof (MonoInst*) * cfg->next_vreg);
1284 for (i = 0; i < cfg->next_vreg; i++) {
1285 area.variable_value_kind [i] = MONO_UNKNOWN_INTEGER_VALUE;
1286 area.relations [i].relation = MONO_EQ_RELATION;
1287 area.relations [i].relation_is_static_definition = TRUE;
1288 MAKE_VALUE_ANY (area.relations [i].related_value);
1289 area.relations [i].next = NULL;
1290 area.defs [i] = NULL;
1293 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
1296 if (TRACE_ABC_REMOVAL)
1297 printf ("\nABCREM BLOCK %d:\n", bb->block_num);
1299 for (ins = bb->code; ins; ins = ins->next) {
1300 const char *spec = INS_INFO (ins->opcode);
1302 if (spec [MONO_INST_DEST] == ' ' || MONO_IS_STORE_MEMBASE (ins))
1305 if (spec [MONO_INST_DEST] == 'i') {
1306 MonoIntegerValueKind effective_value_kind;
1307 MonoRelationsEvaluationRange range;
1308 MonoSummarizedValueRelation *type_relation;
1311 if (TRACE_ABC_REMOVAL)
1312 mono_print_ins (ins);
1314 var = get_vreg_to_inst (cfg, ins->dreg);
1316 area.variable_value_kind [ins->dreg] = type_to_value_kind (var->inst_vtype);
1318 effective_value_kind = get_relation_from_ins (&area, ins, &area.relations [ins->dreg], area.variable_value_kind [ins->dreg]);
1320 MONO_MAKE_RELATIONS_EVALUATION_RANGE_WEAK (range);
1321 apply_value_kind_to_range (&range, area.variable_value_kind [ins->dreg]);
1322 apply_value_kind_to_range (&range, effective_value_kind);
1324 if (range.upper < INT_MAX) {
1325 type_relation = (MonoSummarizedValueRelation *) mono_mempool_alloc (cfg->mempool, sizeof (MonoSummarizedValueRelation));
1326 type_relation->relation = MONO_LE_RELATION;
1327 type_relation->related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE;
1328 type_relation->related_value.value.constant.value = range.upper;
1329 type_relation->relation_is_static_definition = TRUE;
1330 type_relation->next = area.relations [ins->dreg].next;
1331 area.relations [ins->dreg].next = type_relation;
1332 if (TRACE_ABC_REMOVAL) {
1333 printf ("[var%d <= %d]", ins->dreg, range.upper);
1336 if (range.lower > INT_MIN) {
1337 type_relation = (MonoSummarizedValueRelation *) mono_mempool_alloc (cfg->mempool, sizeof (MonoSummarizedValueRelation));
1338 type_relation->relation = MONO_GE_RELATION;
1339 type_relation->related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE;
1340 type_relation->related_value.value.constant.value = range.lower;
1341 type_relation->relation_is_static_definition = TRUE;
1342 type_relation->next = area.relations [ins->dreg].next;
1343 area.relations [ins->dreg].next = type_relation;
1344 if (TRACE_ABC_REMOVAL) {
1345 printf ("[var%d >= %d]", ins->dreg, range.lower);
1348 if (TRACE_ABC_REMOVAL) {
1349 printf ("Summarized variable %d: ", ins->dreg);
1350 print_summarized_value (&(area.relations [ins->dreg].related_value));
1357 /* Add symmetric relations */
1358 for (i = 0; i < cfg->next_vreg; i++) {
1359 if (area.relations [i].related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
1360 int related_index = cfg->next_vreg + i;
1361 int related_variable = area.relations [i].related_value.value.variable.variable;
1363 area.relations [related_index].relation = MONO_EQ_RELATION;
1364 area.relations [related_index].relation_is_static_definition = TRUE;
1365 area.relations [related_index].related_value.type = MONO_VARIABLE_SUMMARIZED_VALUE;
1366 area.relations [related_index].related_value.value.variable.variable = i;
1367 area.relations [related_index].related_value.value.variable.delta = - area.relations [i].related_value.value.variable.delta;
1369 area.relations [related_index].next = area.relations [related_variable].next;
1370 area.relations [related_variable].next = &(area.relations [related_index]);
1372 if (TRACE_ABC_REMOVAL) {
1373 printf ("Added symmetric summarized value for variable variable %d (to %d): ", i, related_variable);
1374 print_summarized_value (&(area.relations [related_index].related_value));
1380 process_block (cfg, cfg->bblocks [0], &area);
1383 #endif /* DISABLE_JIT */