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>
20 #include "abcremoval.h"
22 #if SIZEOF_VOID_P == 8
23 #define OP_PCONST OP_I8CONST
25 #define OP_PCONST OP_ICONST
29 #define TRACE_ABC_REMOVAL (verbose_level > 2)
30 #define REPORT_ABC_REMOVAL (verbose_level > 0)
33 * A little hack for the verbosity level.
34 * The verbosity level is stored in the cfg, but not all functions that must
35 * print something see the cfg, so we store the verbosity level here at the
36 * beginning of the algorithm.
37 * This is not thread safe (does not handle correctly different verbosity
38 * levels in different threads), and is not exact in case of dynamic changes
39 * of the verbosity level...
40 * Anyway, this is not needed, all that can happen is that something more
41 * (or less) is logged, the result is in any case correct.
43 static int verbose_level;
46 #define RELATION_BETWEEN_VALUES(value,related_value) (\
47 ((value) > (related_value))? MONO_GT_RELATION :\
48 (((value) < (related_value))? MONO_LT_RELATION : MONO_EQ_RELATION))
50 #define MAKE_VALUE_ANY(v) do{\
51 (v).type = MONO_ANY_SUMMARIZED_VALUE;\
54 #define MAKE_VALUE_RELATION_ANY(r) do{\
55 (r)->relation = MONO_ANY_RELATION;\
56 MAKE_VALUE_ANY((r)->related_value);\
59 #define INITIALIZE_VALUE_RELATION(r) do{\
60 MAKE_VALUE_RELATION_ANY((r));\
64 #define MONO_NEGATED_RELATION(r) ((~(r))&MONO_ANY_RELATION)
65 #define MONO_SYMMETRIC_RELATION(r) (((r)&MONO_EQ_RELATION)|(((r)&MONO_LT_RELATION)<<1)|((r&MONO_GT_RELATION)>>1))
70 print_relation (int relation) {
73 if (relation & MONO_LT_RELATION) {
77 if (relation & MONO_EQ_RELATION) {
84 if (relation & MONO_GT_RELATION) {
95 print_summarized_value (MonoSummarizedValue *value) {
96 switch (value->type) {
97 case MONO_ANY_SUMMARIZED_VALUE:
100 case MONO_CONSTANT_SUMMARIZED_VALUE:
101 printf ("CONSTANT %d", value->value.constant.value);
103 case MONO_VARIABLE_SUMMARIZED_VALUE:
104 printf ("VARIABLE %d, delta %d", value->value.variable.variable, value->value.variable.delta);
106 case MONO_PHI_SUMMARIZED_VALUE: {
109 for (phi = 0; phi < value->value.phi.number_of_alternatives; phi++) {
110 if (phi) printf (",");
111 printf ("%d", value->value.phi.phi_alternatives [phi]);
117 g_assert_not_reached ();
122 print_summarized_value_relation (MonoSummarizedValueRelation *relation) {
123 printf ("Relation ");
124 print_relation (relation->relation);
125 printf (" with value ");
126 print_summarized_value (&(relation->related_value));
131 print_summarized_value_relation_chain (MonoSummarizedValueRelation *relation) {
132 printf ("Relations:\n");
134 print_summarized_value_relation (relation);
136 relation = relation->next;
142 print_evaluation_context_status (MonoRelationsEvaluationStatus status) {
143 if (status == MONO_RELATIONS_EVALUATION_NOT_STARTED) {
144 printf ("EVALUATION_NOT_STARTED");
146 gboolean print_or = FALSE;
149 if (status & MONO_RELATIONS_EVALUATION_IN_PROGRESS) {
150 if (print_or) printf ("|");
151 printf ("EVALUATION_IN_PROGRESS");
154 if (status & MONO_RELATIONS_EVALUATION_COMPLETED) {
155 if (print_or) printf ("|");
156 printf ("EVALUATION_COMPLETED");
159 if (status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING) {
160 if (print_or) printf ("|");
161 printf ("RECURSIVELY_ASCENDING");
164 if (status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING) {
165 if (print_or) printf ("|");
166 printf ("RECURSIVELY_DESCENDING");
169 if (status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE) {
170 if (print_or) printf ("|");
171 printf ("RECURSIVELY_INDEFINITE");
180 print_evaluation_context_ranges (MonoRelationsEvaluationRanges *ranges) {
181 printf ("(ranges: zero [%d,%d], variable [%d,%d])", ranges->zero.lower, ranges->zero.upper, ranges->variable.lower, ranges->variable.upper);
185 print_evaluation_context (MonoRelationsEvaluationContext *context) {
186 printf ("Context status: ");
187 print_evaluation_context_status (context->status);
188 if (context->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]));
217 static inline GSList*
218 g_slist_append_mempool (MonoMemPool *mp, GSList *list, gpointer data)
223 new_list = mono_mempool_alloc (mp, sizeof (GSList));
224 new_list->data = data;
225 new_list->next = NULL;
231 last->next = new_list;
239 * Check if the delta of an integer variable value is safe with respect
240 * to the variable size in bytes and its kind (signed or unsigned).
241 * If the delta is not safe, make the value an "any".
243 static G_GNUC_UNUSED void
244 check_delta_safety (MonoVariableRelationsEvaluationArea *area, MonoSummarizedValue *value) {
245 if (value->type == MONO_VARIABLE_SUMMARIZED_VALUE) {
246 int variable = value->value.variable.variable;
247 int delta = value->value.variable.delta;
248 if ((area->variable_value_kind [variable]) & MONO_UNSIGNED_VALUE_FLAG) {
250 MAKE_VALUE_ANY (*value);
253 if (((area->variable_value_kind [variable]) & MONO_INTEGER_VALUE_SIZE_BITMASK) < 4) {
254 MAKE_VALUE_ANY (*value);
255 } else if (delta > 16) {
256 MAKE_VALUE_ANY (*value);
263 * get_relation_from_ins:
265 * Obtain relations from a MonoInst.
267 * result_value_kind: the "expected" kind of result;
268 * result: the "summarized" value
269 * returns the "actual" kind of result, if guessable (otherwise MONO_UNKNOWN_INTEGER_VALUE)
271 static MonoIntegerValueKind
272 get_relation_from_ins (MonoVariableRelationsEvaluationArea *area, MonoInst *ins, MonoSummarizedValueRelation *result, MonoIntegerValueKind result_value_kind)
274 MonoIntegerValueKind value_kind;
275 MonoSummarizedValue *value = &result->related_value;
277 if (ins->type == STACK_I8) {
278 value_kind = MONO_INTEGER_VALUE_SIZE_8;
279 } else if (ins->type == STACK_I4) {
280 value_kind = MONO_INTEGER_VALUE_SIZE_4;
282 value_kind = MONO_UNKNOWN_INTEGER_VALUE;
285 result->relation = MONO_EQ_RELATION;
286 MAKE_VALUE_ANY (*value);
288 switch (ins->opcode) {
290 value->type = MONO_CONSTANT_SUMMARIZED_VALUE;
291 value->value.constant.value = ins->inst_c0;
294 value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
295 value->value.variable.variable = ins->sreg1;
296 value->value.variable.delta = 0;
299 value->type = MONO_PHI_SUMMARIZED_VALUE;
300 value->value.phi.number_of_alternatives = *(ins->inst_phi_args);
301 value->value.phi.phi_alternatives = ins->inst_phi_args + 1;
304 value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
305 value->value.variable.variable = ins->sreg1;
306 value->value.variable.delta = ins->inst_imm;
308 //check_delta_safety (area, result);
311 value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
312 value->value.variable.variable = ins->sreg1;
313 value->value.variable.delta = ins->inst_imm;
315 //check_delta_safety (area, result);
318 /* The result of an unsigned remainder is 0 < x < the divisor */
319 result->relation = MONO_LT_RELATION;
320 value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
321 value->value.variable.variable = ins->sreg2;
322 value->value.variable.delta = 0;
323 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_4;
327 * We represent arrays by their length, so r1<-ldlen r2 is stored
328 * as r1 == r2 in the evaluation graph.
330 value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
331 value->value.variable.variable = ins->sreg1;
332 value->value.variable.delta = 0;
333 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_4;
336 value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
337 value->value.variable.variable = ins->sreg1;
338 value->value.variable.delta = 0;
341 /* FIXME: Add more opcodes */
348 static MonoValueRelation
349 get_relation_from_branch_instruction (MonoInst *ins)
351 if (MONO_IS_COND_BRANCH_OP (ins)) {
352 CompRelation rel = mono_opcode_to_cond (ins->opcode);
356 return MONO_EQ_RELATION;
358 return MONO_NE_RELATION;
361 return MONO_LE_RELATION;
364 return MONO_GE_RELATION;
367 return MONO_LT_RELATION;
370 return MONO_GT_RELATION;
372 g_assert_not_reached ();
373 return MONO_ANY_RELATION;
376 return MONO_ANY_RELATION;
381 * Given a BB, find its entry condition and put its relations in a
382 * "MonoAdditionalVariableRelationsForBB" structure.
384 * relations: the resulting relations (entry condition of the given BB)
387 get_relations_from_previous_bb (MonoVariableRelationsEvaluationArea *area, MonoBasicBlock *bb, MonoAdditionalVariableRelationsForBB *relations)
389 MonoBasicBlock *in_bb;
390 MonoInst *ins, *compare, *branch;
391 MonoValueRelation branch_relation;
392 MonoValueRelation symmetric_relation;
395 INITIALIZE_VALUE_RELATION (&(relations->relation1.relation));
396 relations->relation1.relation.relation_is_static_definition = FALSE;
397 relations->relation1.relation.next = NULL;
398 relations->relation1.insertion_point = NULL;
399 relations->relation1.variable = -1;
400 INITIALIZE_VALUE_RELATION (&(relations->relation2.relation));
401 relations->relation2.relation.relation_is_static_definition = FALSE;
402 relations->relation2.relation.next = NULL;
403 relations->relation2.insertion_point = NULL;
404 relations->relation2.variable = -1;
406 if (bb->in_count == 1) { /* Should write the code to "sum" conditions... */
407 in_bb = bb->in_bb [0];
409 if ((in_bb->last_ins == NULL) || (in_bb->code == in_bb->last_ins))
412 for (ins = in_bb->code; ins->next != in_bb->last_ins; ins = ins->next)
417 branch_relation = get_relation_from_branch_instruction (branch);
419 if (branch_relation != MONO_ANY_RELATION) {
420 if (branch->inst_true_bb == bb) {
422 } else if (branch->inst_false_bb == bb) {
426 g_assert_not_reached ();
429 branch_relation = MONO_NEGATED_RELATION (branch_relation);
430 symmetric_relation = MONO_SYMMETRIC_RELATION (branch_relation);
432 /* FIXME: Other compare opcodes */
433 if (compare->opcode == OP_ICOMPARE) {
434 relations->relation1.variable = compare->sreg1;
435 relations->relation1.relation.relation = branch_relation;
436 relations->relation1.relation.related_value.type = MONO_VARIABLE_SUMMARIZED_VALUE;
437 relations->relation1.relation.related_value.value.variable.variable = compare->sreg2;
438 relations->relation1.relation.related_value.value.variable.delta = 0;
440 relations->relation2.variable = compare->sreg2;
441 relations->relation2.relation.relation = symmetric_relation;
442 relations->relation2.relation.related_value.type = MONO_VARIABLE_SUMMARIZED_VALUE;
443 relations->relation2.relation.related_value.value.variable.variable = compare->sreg1;
444 relations->relation2.relation.related_value.value.variable.delta = 0;
445 } else if (compare->opcode == OP_ICOMPARE_IMM) {
446 relations->relation1.variable = compare->sreg1;
447 relations->relation1.relation.relation = branch_relation;
448 relations->relation1.relation.related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE;
449 relations->relation1.relation.related_value.value.constant.value = compare->inst_imm;
456 * Add the given relations to the evaluation area.
457 * area: the evaluation area
458 * change: the relations that must be added
461 apply_change_to_evaluation_area (MonoVariableRelationsEvaluationArea *area, MonoAdditionalVariableRelation *change)
463 MonoSummarizedValueRelation *base_relation;
465 if (change->relation.relation != MONO_ANY_RELATION) {
466 base_relation = &(area->relations [change->variable]);
467 while ((base_relation->next != NULL) && (base_relation->next->relation_is_static_definition)) {
468 base_relation = base_relation->next;
470 change->insertion_point = base_relation;
471 change->relation.next = base_relation->next;
472 base_relation->next = &(change->relation);
477 * Remove the given relation from the evaluation area.
478 * change: the relation that must be removed
481 remove_change_from_evaluation_area (MonoAdditionalVariableRelation *change)
483 if (change->insertion_point != NULL) {
484 change->insertion_point->next = change->relation.next;
485 change->relation.next = NULL;
491 clean_contexts (MonoRelationsEvaluationContext *contexts, int number)
494 for (i = 0; i < number; i++) {
495 contexts [i].status = MONO_RELATIONS_EVALUATION_NOT_STARTED;
501 * Perform the intersection of a range and a constant value (taking into
502 * account the relation that the value has with the range).
503 * range: the range that will be intersected with the value
504 * value: the value that will be intersected with the range
505 * relation: the relation between the range and the value
508 intersect_value( MonoRelationsEvaluationRange *range, int value, MonoValueRelation relation )
511 case MONO_NO_RELATION:
512 MONO_MAKE_RELATIONS_EVALUATION_RANGE_IMPOSSIBLE (*range);
514 case MONO_ANY_RELATION:
516 case MONO_EQ_RELATION:
517 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, value);
518 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, value);
520 case MONO_NE_RELATION: {
521 /* IMPROVEMENT Figure this out! (ignoring it is safe anyway) */
524 case MONO_LT_RELATION:
525 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (value));
527 case MONO_LE_RELATION:
528 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, value);
530 case MONO_GT_RELATION:
531 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (value));
533 case MONO_GE_RELATION:
534 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, value);
537 g_assert_not_reached();
543 * Perform the intersection of two pairs of ranges (taking into account the
544 * relation between the ranges and a given delta).
545 * ranges: the ranges that will be intersected
546 * other_ranges the other ranges that will be intersected
547 * delta: the delta between the pairs of ranges
548 * relation: the relation between the pairs of ranges
551 intersect_ranges( MonoRelationsEvaluationRanges *ranges, MonoRelationsEvaluationRanges *other_ranges, int delta, MonoValueRelation relation )
555 case MONO_NO_RELATION:
556 MONO_MAKE_RELATIONS_EVALUATION_RANGES_IMPOSSIBLE (*ranges);
558 case MONO_ANY_RELATION:
560 case MONO_EQ_RELATION:
561 MONO_RELATIONS_EVALUATION_RANGES_INTERSECTION (*ranges, *other_ranges);
563 case MONO_NE_RELATION: {
564 /* FIXME Figure this out! (ignoring it is safe anyway) */
567 case MONO_LT_RELATION:
568 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->zero.upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->zero.upper));
569 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->variable.upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->variable.upper));
571 case MONO_LE_RELATION:
572 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->zero.upper, other_ranges->zero.upper);
573 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->variable.upper, other_ranges->variable.upper);
575 case MONO_GT_RELATION:
576 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->zero.lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->zero.lower));
577 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->variable.lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->variable.lower));
579 case MONO_GE_RELATION:
580 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->zero.lower, other_ranges->zero.lower);
581 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->variable.lower, other_ranges->variable.lower);
584 g_assert_not_reached();
587 MonoRelationsEvaluationRanges translated_ranges = *other_ranges;
588 MONO_ADD_DELTA_SAFELY_TO_RANGES (translated_ranges, delta);
589 intersect_ranges( ranges, &translated_ranges, FALSE, relation );
594 * Recursive method that traverses the relation graph to evaluate the
595 * relation between two variables.
596 * At the end of the execution, the resulting ranges are in the context of
597 * the "starting" variable.
598 * area: the current evaluation area (it contains the relation graph and
599 * memory for all the evaluation contexts is already allocated)
600 * variable: starting variable (the value ranges in its context are the result
601 * of the execution of this procedure)
602 * target_variable: the variable with respect to which the starting variable
603 * is evaluated (tipically the starting variable is the index
604 * and the target one is the array (which means its length))
605 * father_context: the previous evaluation context in recursive invocations
606 * (or NULL for the first invocation)
609 evaluate_relation_with_target_variable (MonoVariableRelationsEvaluationArea *area, int variable, int target_variable, MonoRelationsEvaluationContext *father_context)
611 MonoRelationsEvaluationContext *context = &(area->contexts [variable]);
613 // First of all, we check the evaluation status
614 // (what must be done is *very* different in each case)
615 switch (context->status) {
616 case MONO_RELATIONS_EVALUATION_NOT_STARTED: {
617 MonoSummarizedValueRelation *relation = &(area->relations [variable]);
619 if (TRACE_ABC_REMOVAL) {
620 printf ("Evaluating variable %d (target variable %d)\n", variable, target_variable);
621 print_summarized_value_relation (relation);
625 // We properly inizialize the context
626 context->status = MONO_RELATIONS_EVALUATION_IN_PROGRESS;
627 context->father = father_context;
628 MONO_MAKE_RELATIONS_EVALUATION_RANGES_WEAK (context->ranges);
630 // If we have found the target variable, we can set the range
631 // related to it in the context to "equal" (which is [0,0])
632 if (variable == target_variable) {
633 if (TRACE_ABC_REMOVAL) {
634 printf ("Target variable reached (%d), continuing to evaluate relations with constants\n", variable);
636 context->ranges.variable.lower = 0;
637 context->ranges.variable.upper = 0;
640 // Examine all relations for this variable (scan the list)
641 // The contribute of each relation will be intersected (logical and)
642 while (relation != NULL) {
643 context->current_relation = relation;
645 if (TRACE_ABC_REMOVAL) {
646 printf ("Processing (%d): ", variable);
647 print_summarized_value_relation (relation);
651 // We decie what to do according the the type of the related value
652 switch (relation->related_value.type) {
653 case MONO_ANY_SUMMARIZED_VALUE:
654 // No added information, skip it
656 case MONO_CONSTANT_SUMMARIZED_VALUE:
657 // Intersect range with constant (taking into account the relation)
658 intersect_value (&(context->ranges.zero), relation->related_value.value.constant.value, relation->relation);
660 case MONO_VARIABLE_SUMMARIZED_VALUE:
661 // Generally, evaluate related variable and intersect ranges.
662 // However, some check is necessary...
664 // If the relation is "ANY", nothing to do (no added information)
665 if (relation->relation != MONO_ANY_RELATION) {
666 int related_variable = relation->related_value.value.variable.variable;
667 MonoRelationsEvaluationContext *related_context = &(area->contexts [related_variable]);
669 // The second condition in the "or" avoids messing with "back edges" in the graph traversal
670 // (they are simply ignored instead of triggering the handling of recursion)
671 if ( (related_context->status == MONO_RELATIONS_EVALUATION_NOT_STARTED) || !
672 ((related_context->current_relation->related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) &&
673 (related_context->current_relation->related_value.value.variable.variable == variable))) {
674 // Evaluate the related variable
675 evaluate_relation_with_target_variable (area, related_variable, target_variable, context);
677 // Check if we are part of a recursive loop
678 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) {
679 if (TRACE_ABC_REMOVAL) {
680 printf ("Recursivity detected for variable %d (target variable %d), status ", variable, target_variable);
681 print_evaluation_context_status (context->status);
684 // If we are, check if the evaluation of the related variable is complete
685 if (related_context->status == MONO_RELATIONS_EVALUATION_COMPLETED) {
686 // If it is complete, we are part of a recursive definition.
687 // Since it is a *definition* (and definitions are evaluated *before*
688 // conditions because they are first in the list), intersection is not
689 // strictly necessary, we simply copy the ranges and apply the delta
690 context->ranges = related_context->ranges;
691 /* Delta has already been checked for over/under-flow when evaluating values */
692 MONO_ADD_DELTA_SAFELY_TO_RANGES (context->ranges, relation->related_value.value.variable.delta);
693 context->status = MONO_RELATIONS_EVALUATION_COMPLETED;
694 if (TRACE_ABC_REMOVAL) {
695 printf (", ranges already computed, result: \n");
696 print_evaluation_context_ranges (&(context->ranges));
697 printf (" (delta is %d)\n", relation->related_value.value.variable.delta);
700 // If it is not complete, do nothing (we do not have enough information)
701 if (TRACE_ABC_REMOVAL) {
702 printf (", ranges not computed\n");
706 // If we are not (the common case) intersect the result
707 intersect_ranges( &(context->ranges), &(related_context->ranges), relation->related_value.value.variable.delta, relation->relation );
710 if (TRACE_ABC_REMOVAL) {
711 printf ("Relation is a back-edge in this traversal, skipping\n");
716 case MONO_PHI_SUMMARIZED_VALUE: {
717 // We must compute all PHI alternatives, combining the results (with a union, which is a logical "or"),
718 // and intersect this result with the ranges in the context; we must also take into account recursions
719 // (with loops that can be ascending, descending, or indefinite)
720 MonoRelationsEvaluationRanges phi_ranges;
722 gboolean is_ascending = FALSE;
723 gboolean is_descending = FALSE;
725 MONO_MAKE_RELATIONS_EVALUATION_RANGES_IMPOSSIBLE (phi_ranges);
726 for (phi = 0; phi < relation->related_value.value.phi.number_of_alternatives; phi++) {
727 int phi_alternative = relation->related_value.value.phi.phi_alternatives [phi];
728 evaluate_relation_with_target_variable (area, phi_alternative, target_variable, context);
730 // This means we are part of a recursive loop
731 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) {
732 if (TRACE_ABC_REMOVAL) {
733 printf ("Recursivity detected for variable %d (target variable %d), status ", variable, target_variable);
734 print_evaluation_context_status (context->status);
737 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING) {
740 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING) {
741 is_descending = TRUE;
743 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE) {
745 is_descending = TRUE;
748 // Clear "recursivity" bits in the status (recursion has been handled)
749 context->status = MONO_RELATIONS_EVALUATION_IN_PROGRESS;
751 MONO_RELATIONS_EVALUATION_RANGES_UNION (phi_ranges, area->contexts [phi_alternative].ranges);
755 // Apply the effects of all recursive loops
757 phi_ranges.zero.upper = INT_MAX;
758 phi_ranges.variable.upper = INT_MAX;
761 phi_ranges.zero.lower = INT_MIN;
762 phi_ranges.variable.lower = INT_MIN;
765 // Intersect final result
766 MONO_RELATIONS_EVALUATION_RANGES_INTERSECTION (context->ranges, phi_ranges);
770 g_assert_not_reached();
773 // Pass to next relation
774 relation = relation->next;
777 // Check if any recursivity bits are still in the status, and in any case clear them
778 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) {
779 if (TRACE_ABC_REMOVAL) {
780 printf ("Recursivity for variable %d (target variable %d) discards computation, status ", variable, target_variable);
781 print_evaluation_context_status (context->status);
784 // If yes, we did not have enough information (most likely we were evaluated inside a PHI, but we also
785 // depended on the same PHI, which was still in evaluation...), so clear the status to "NOT_STARTED"
786 // (if we will be evaluated again, the PHI will be already done, so our evaluation will succeed)
787 context->status = MONO_RELATIONS_EVALUATION_NOT_STARTED;
789 if (TRACE_ABC_REMOVAL) {
790 printf ("Ranges for variable %d (target variable %d) computed: ", variable, target_variable);
791 print_evaluation_context_ranges (&(context->ranges));
794 // If not (the common case) the evaluation is complete, and the result is in the context
795 context->status = MONO_RELATIONS_EVALUATION_COMPLETED;
799 case MONO_RELATIONS_EVALUATION_IN_PROGRESS: {
800 // This means we are in a recursive loop
801 MonoRelationsEvaluationContext *current_context = father_context;
802 MonoRelationsEvaluationContext *last_context = context->father;
803 gboolean evaluation_can_be_recursive = TRUE;
804 gboolean evaluation_is_definition = TRUE;
807 if (TRACE_ABC_REMOVAL) {
808 printf ("Evaluation of variable %d (target variable %d) already in progress\n", variable, target_variable);
809 print_evaluation_context (context);
810 print_summarized_value_relation (context->current_relation);
814 // We must check if the loop can be a recursive definition (we scan the whole loop)
815 while (current_context != last_context) {
816 if (current_context == NULL) {
817 printf ("Broken recursive ring in ABC removal\n");
818 g_assert_not_reached ();
821 if (current_context->current_relation->relation_is_static_definition) {
822 if (current_context->current_relation->related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
823 /* No need to check path_value for over/under-flow, since delta should be safe */
824 path_value += current_context->current_relation->related_value.value.variable.delta;
825 } else if (current_context->current_relation->related_value.type != MONO_PHI_SUMMARIZED_VALUE) {
826 evaluation_can_be_recursive = FALSE;
829 evaluation_is_definition = FALSE;
830 evaluation_can_be_recursive = FALSE;
833 current_context = current_context->father;
836 // If this is a recursive definition, we properly flag the status in all the involved contexts
837 if (evaluation_is_definition) {
838 MonoRelationsEvaluationStatus recursive_status;
839 if (evaluation_can_be_recursive) {
840 if (path_value > 0) {
841 recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING;
842 } else if (path_value < 0) {
843 recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING;
845 recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE;
848 recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE;
851 if (TRACE_ABC_REMOVAL) {
852 printf ("Recursivity accepted (");
853 print_evaluation_context_status (recursive_status);
857 current_context = father_context;
858 while (current_context != last_context) {
859 current_context->status |= recursive_status;
860 current_context = current_context->father;
863 if (TRACE_ABC_REMOVAL) {
864 printf ("Recursivity rejected (some relation in the cycle is not a defintion)\n");
869 case MONO_RELATIONS_EVALUATION_COMPLETED: {
873 if (TRACE_ABC_REMOVAL) {
874 printf ("Variable %d (target variable %d) already in a recursive ring, skipping\n", variable, target_variable);
875 print_evaluation_context (context);
876 print_summarized_value_relation (context->current_relation);
885 * Apply the given value kind to the given range
888 apply_value_kind_to_range (MonoRelationsEvaluationRange *range, MonoIntegerValueKind value_kind)
890 if (value_kind != MONO_UNKNOWN_INTEGER_VALUE) {
891 if (value_kind & MONO_UNSIGNED_VALUE_FLAG) {
892 if (range->lower < 0) {
895 if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 1) {
896 if (range->upper > 0xff) {
899 } else if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 2) {
900 if (range->upper > 0xffff) {
901 range->upper = 0xffff;
905 if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 1) {
906 if (range->lower < -0x80) {
907 range->lower = -0x80;
909 if (range->upper > 0x7f) {
912 } else if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 2) {
913 if (range->lower < -0x8000) {
914 range->lower = -0x8000;
916 if (range->upper > 0x7fff) {
917 range->upper = 0x7fff;
925 * Attempt the removal of bounds checks from a MonoInst.
927 * area: the current evaluation area (it contains the relation graph and
928 * memory for all the evaluation contexts is already allocated)
931 remove_abc_from_inst (MonoInst *ins, MonoVariableRelationsEvaluationArea *area)
933 /* FIXME: Add support for 'constant' arrays and constant indexes */
935 int array_variable = ins->sreg1;
936 int index_variable = ins->sreg2;
937 MonoRelationsEvaluationContext *array_context = &(area->contexts [array_variable]);
938 MonoRelationsEvaluationContext *index_context = &(area->contexts [index_variable]);
940 clean_contexts (area->contexts, area->cfg->next_vreg);
942 evaluate_relation_with_target_variable (area, index_variable, array_variable, NULL);
943 evaluate_relation_with_target_variable (area, array_variable, array_variable, NULL);
945 if ((index_context->ranges.zero.lower >=0) && ((index_context->ranges.variable.upper < 0)||(index_context->ranges.zero.upper < array_context->ranges.zero.lower))) {
946 if (REPORT_ABC_REMOVAL) {
947 printf ("ARRAY-ACCESS: removed bounds check on array %d with index %d\n",
948 array_variable, index_variable);
952 if (TRACE_ABC_REMOVAL) {
953 if (index_context->ranges.zero.lower >= 0) {
954 printf ("ARRAY-ACCESS: Removed lower bound check on array %d with index %d\n", array_variable, index_variable);
956 if (index_context->ranges.variable.upper < 0) {
957 printf ("ARRAY-ACCESS: Removed upper bound check (through variable) on array %d with index %d\n", array_variable, index_variable);
959 if (index_context->ranges.zero.upper < array_context->ranges.zero.lower) {
960 printf ("ARRAY-ACCESS: Removed upper bound check (through constant) on array %d with index %d\n", array_variable, index_variable);
967 * Process a BB removing bounds checks from array accesses.
968 * It does the following (in sequence):
969 * - Get the BB entry condition
970 * - Add its relations to the relation graph in the evaluation area
971 * - Process all the MonoInst trees in the BB
972 * - Recursively process all the children BBs in the dominator tree
973 * - Remove the relations previously added to the relation graph
975 * bb: the BB that must be processed
976 * area: the current evaluation area (it contains the relation graph and
977 * memory for all the evaluation contexts is already allocated)
980 process_block (MonoCompile *cfg, MonoBasicBlock *bb, MonoVariableRelationsEvaluationArea *area) {
983 MonoAdditionalVariableRelationsForBB additional_relations;
984 GSList *dominated_bb, *l;
985 GSList *check_relations = NULL;
987 if (TRACE_ABC_REMOVAL) {
988 printf ("\nProcessing block %d [dfn %d]...\n", bb->block_num, bb->dfn);
991 get_relations_from_previous_bb (area, bb, &additional_relations);
992 if (TRACE_ABC_REMOVAL) {
993 if (additional_relations.relation1.relation.relation != MONO_ANY_RELATION) {
994 printf ("Adding relation 1 on variable %d: ", additional_relations.relation1.variable);
995 print_summarized_value_relation (&(additional_relations.relation1.relation));
998 if (additional_relations.relation2.relation.relation != MONO_ANY_RELATION) {
999 printf ("Adding relation 2 on variable %d: ", additional_relations.relation2.variable);
1000 print_summarized_value_relation (&(additional_relations.relation2.relation));
1004 apply_change_to_evaluation_area (area, &(additional_relations.relation1));
1005 apply_change_to_evaluation_area (area, &(additional_relations.relation2));
1008 for (ins = bb->code; ins; ins = ins->next) {
1009 MonoAdditionalVariableRelation *rel;
1010 int array_var, index_var;
1012 if (TRACE_ABC_REMOVAL) {
1013 printf ("Processing instruction %d\n", inst_index);
1017 if (ins->opcode == OP_BOUNDS_CHECK) { /* Handle OP_LDELEMA2D, too */
1018 if (TRACE_ABC_REMOVAL) {
1019 printf ("Attempting check removal...\n");
1022 array_var = ins->sreg1;
1023 index_var = ins->sreg2;
1025 remove_abc_from_inst (ins, area);
1027 /* We can derive additional relations from the bounds check */
1028 if (ins->opcode != OP_NOP) {
1029 rel = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoAdditionalVariableRelation));
1030 rel->variable = index_var;
1031 rel->relation.relation = MONO_LT_RELATION;
1032 rel->relation.related_value.type = MONO_VARIABLE_SUMMARIZED_VALUE;
1033 rel->relation.related_value.value.variable.variable = array_var;
1034 rel->relation.related_value.value.variable.delta = 0;
1036 apply_change_to_evaluation_area (area, rel);
1038 check_relations = g_slist_append_mempool (cfg->mempool, check_relations, rel);
1040 rel = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoAdditionalVariableRelation));
1041 rel->variable = index_var;
1042 rel->relation.relation = MONO_GE_RELATION;
1043 rel->relation.related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE;
1044 rel->relation.related_value.value.constant.value = 0;
1046 apply_change_to_evaluation_area (area, rel);
1048 check_relations = g_slist_append_mempool (cfg->mempool, check_relations, rel);
1052 if (ins->opcode == OP_CHECK_THIS) {
1053 MonoRelationsEvaluationContext *context = &(area->contexts [ins->sreg1]);
1055 clean_contexts (area->contexts, area->cfg->next_vreg);
1056 evaluate_relation_with_target_variable (area, ins->sreg1, ins->sreg1, NULL);
1058 if (context->ranges.zero.lower > 0) {
1059 if (REPORT_ABC_REMOVAL)
1060 printf ("ARRAY-ACCESS: removed check_this instruction.\n");
1065 if (ins->opcode == OP_NOT_NULL) {
1066 rel = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoAdditionalVariableRelation));
1067 rel->variable = ins->sreg1;
1068 rel->relation.relation = MONO_GT_RELATION;
1069 rel->relation.related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE;
1070 rel->relation.related_value.value.constant.value = 0;
1072 apply_change_to_evaluation_area (area, rel);
1074 check_relations = g_slist_append_mempool (cfg->mempool, check_relations, rel);
1078 if (TRACE_ABC_REMOVAL) {
1079 printf ("Processing block %d [dfn %d] done.\n", bb->block_num, bb->dfn);
1082 for (dominated_bb = bb->dominated; dominated_bb != NULL; dominated_bb = dominated_bb->next) {
1083 process_block (cfg, (MonoBasicBlock*) (dominated_bb->data), area);
1086 for (l = check_relations; l; l = l->next)
1087 remove_change_from_evaluation_area (l->data);
1089 remove_change_from_evaluation_area (&(additional_relations.relation1));
1090 remove_change_from_evaluation_area (&(additional_relations.relation2));
1093 static MonoIntegerValueKind
1094 type_to_value_kind (MonoType *type)
1097 return MONO_UNKNOWN_INTEGER_VALUE;
1098 switch (type->type) {
1100 return MONO_INTEGER_VALUE_SIZE_1;
1103 return MONO_UNSIGNED_INTEGER_VALUE_SIZE_1;
1106 return MONO_INTEGER_VALUE_SIZE_2;
1109 return MONO_UNSIGNED_INTEGER_VALUE_SIZE_2;
1112 return MONO_INTEGER_VALUE_SIZE_4;
1115 return MONO_UNSIGNED_INTEGER_VALUE_SIZE_4;
1118 return SIZEOF_VOID_P;
1121 return (MONO_UNSIGNED_VALUE_FLAG|SIZEOF_VOID_P);
1124 return MONO_INTEGER_VALUE_SIZE_8;
1127 return MONO_UNSIGNED_INTEGER_VALUE_SIZE_8;
1129 return MONO_UNKNOWN_INTEGER_VALUE;
1134 * mono_perform_abc_removal:
1135 * @cfg: Control Flow Graph
1137 * Performs the ABC removal from a cfg in SSA form.
1138 * It does the following:
1139 * - Prepare the evaluation area
1140 * - Allocate memory for the relation graph in the evaluation area
1141 * (of course, only for variable definitions) and summarize there all
1142 * variable definitions
1143 * - Allocate memory for the evaluation contexts in the evaluation area
1144 * - Recursively process all the BBs in the dominator tree (it is enough
1145 * to invoke the processing on the entry BB)
1147 * cfg: the method code
1150 mono_perform_abc_removal2 (MonoCompile *cfg)
1152 MonoVariableRelationsEvaluationArea area;
1156 verbose_level = cfg->verbose_level;
1158 if (TRACE_ABC_REMOVAL) {
1159 printf ("\nRemoving array bound checks in %s\n", mono_method_full_name (cfg->method, TRUE));
1163 area.relations = (MonoSummarizedValueRelation *)
1164 mono_mempool_alloc (cfg->mempool, sizeof (MonoSummarizedValueRelation) * (cfg->next_vreg) * 2);
1165 area.contexts = (MonoRelationsEvaluationContext *)
1166 mono_mempool_alloc (cfg->mempool, sizeof (MonoRelationsEvaluationContext) * (cfg->next_vreg));
1167 area.variable_value_kind = (MonoIntegerValueKind *)
1168 mono_mempool_alloc (cfg->mempool, sizeof (MonoIntegerValueKind) * (cfg->next_vreg));
1169 for (i = 0; i < cfg->next_vreg; i++) {
1170 area.variable_value_kind [i] = MONO_UNKNOWN_INTEGER_VALUE;
1171 area.relations [i].relation = MONO_EQ_RELATION;
1172 area.relations [i].relation_is_static_definition = TRUE;
1173 MAKE_VALUE_ANY (area.relations [i].related_value);
1174 area.relations [i].next = NULL;
1177 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
1180 if (TRACE_ABC_REMOVAL)
1181 printf ("\nABCREM BLOCK %d:\n", bb->block_num);
1183 for (ins = bb->code; ins; ins = ins->next) {
1184 const char *spec = INS_INFO (ins->opcode);
1186 if (spec [MONO_INST_DEST] == ' ' || MONO_IS_STORE_MEMBASE (ins))
1189 if (spec [MONO_INST_DEST] == 'i') {
1190 MonoIntegerValueKind effective_value_kind;
1191 MonoRelationsEvaluationRange range;
1192 MonoSummarizedValueRelation *type_relation;
1195 if (TRACE_ABC_REMOVAL)
1196 mono_print_ins (ins);
1198 var = get_vreg_to_inst (cfg, ins->dreg);
1200 area.variable_value_kind [ins->dreg] = type_to_value_kind (var->inst_vtype);
1202 effective_value_kind = get_relation_from_ins (&area, ins, &area.relations [ins->dreg], area.variable_value_kind [ins->dreg]);
1204 MONO_MAKE_RELATIONS_EVALUATION_RANGE_WEAK (range);
1205 apply_value_kind_to_range (&range, area.variable_value_kind [ins->dreg]);
1206 apply_value_kind_to_range (&range, effective_value_kind);
1208 if (range.upper < INT_MAX) {
1209 type_relation = (MonoSummarizedValueRelation *) mono_mempool_alloc (cfg->mempool, sizeof (MonoSummarizedValueRelation));
1210 type_relation->relation = MONO_LE_RELATION;
1211 type_relation->related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE;
1212 type_relation->related_value.value.constant.value = range.upper;
1213 type_relation->relation_is_static_definition = TRUE;
1214 type_relation->next = area.relations [ins->dreg].next;
1215 area.relations [ins->dreg].next = type_relation;
1216 if (TRACE_ABC_REMOVAL) {
1217 printf ("[var%d <= %d]", ins->dreg, range.upper);
1220 if (range.lower > INT_MIN) {
1221 type_relation = (MonoSummarizedValueRelation *) mono_mempool_alloc (cfg->mempool, sizeof (MonoSummarizedValueRelation));
1222 type_relation->relation = MONO_GE_RELATION;
1223 type_relation->related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE;
1224 type_relation->related_value.value.constant.value = range.lower;
1225 type_relation->relation_is_static_definition = TRUE;
1226 type_relation->next = area.relations [ins->dreg].next;
1227 area.relations [ins->dreg].next = type_relation;
1228 if (TRACE_ABC_REMOVAL) {
1229 printf ("[var%d >= %d]", ins->dreg, range.lower);
1232 if (TRACE_ABC_REMOVAL) {
1233 printf ("Summarized variable %d: ", ins->dreg);
1234 print_summarized_value (&(area.relations [ins->dreg].related_value));
1241 /* Add symmetric relations */
1242 for (i = 0; i < cfg->next_vreg; i++) {
1243 if (area.relations [i].related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
1244 int related_index = cfg->next_vreg + i;
1245 int related_variable = area.relations [i].related_value.value.variable.variable;
1247 area.relations [related_index].relation = MONO_EQ_RELATION;
1248 area.relations [related_index].relation_is_static_definition = TRUE;
1249 area.relations [related_index].related_value.type = MONO_VARIABLE_SUMMARIZED_VALUE;
1250 area.relations [related_index].related_value.value.variable.variable = i;
1251 area.relations [related_index].related_value.value.variable.delta = - area.relations [i].related_value.value.variable.delta;
1253 area.relations [related_index].next = area.relations [related_variable].next;
1254 area.relations [related_variable].next = &(area.relations [related_index]);
1256 if (TRACE_ABC_REMOVAL) {
1257 printf ("Added symmetric summarized value for variable variable %d (to %d): ", i, related_variable);
1258 print_summarized_value (&(area.relations [related_index].related_value));
1264 process_block (cfg, cfg->bblocks [0], &area);
1267 #endif /* DISABLE_JIT */