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>
24 #include "abcremoval.h"
26 #if SIZEOF_VOID_P == 8
27 #define OP_PCONST OP_I8CONST
29 #define OP_PCONST OP_ICONST
33 #define TRACE_ABC_REMOVAL (verbose_level > 2)
34 #define REPORT_ABC_REMOVAL (verbose_level > 0)
37 * A little hack for the verbosity level.
38 * The verbosity level is stored in the cfg, but not all functions that must
39 * print something see the cfg, so we store the verbosity level here at the
40 * beginning of the algorithm.
41 * This is not thread safe (does not handle correctly different verbosity
42 * levels in different threads), and is not exact in case of dynamic changes
43 * of the verbosity level...
44 * Anyway, this is not needed, all that can happen is that something more
45 * (or less) is logged, the result is in any case correct.
47 static int verbose_level;
50 #define RELATION_BETWEEN_VALUES(value,related_value) (\
51 ((value) > (related_value))? MONO_GT_RELATION :\
52 (((value) < (related_value))? MONO_LT_RELATION : MONO_EQ_RELATION))
54 #define MAKE_VALUE_ANY(v) do{\
55 (v).type = MONO_ANY_SUMMARIZED_VALUE;\
58 #define MAKE_VALUE_RELATION_ANY(r) do{\
59 (r)->relation = MONO_ANY_RELATION;\
60 MAKE_VALUE_ANY((r)->related_value);\
63 #define INITIALIZE_VALUE_RELATION(r) do{\
64 MAKE_VALUE_RELATION_ANY((r));\
68 #define MONO_NEGATED_RELATION(r) ((~(r))&MONO_ANY_RELATION)
69 #define MONO_SYMMETRIC_RELATION(r) (((r)&MONO_EQ_RELATION)|(((r)&MONO_LT_RELATION)<<1)|((r&MONO_GT_RELATION)>>1))
74 print_relation (int relation) {
77 if (relation & MONO_LT_RELATION) {
81 if (relation & MONO_EQ_RELATION) {
88 if (relation & MONO_GT_RELATION) {
99 print_summarized_value (MonoSummarizedValue *value) {
100 switch (value->type) {
101 case MONO_ANY_SUMMARIZED_VALUE:
104 case MONO_CONSTANT_SUMMARIZED_VALUE:
105 printf ("CONSTANT %d", value->value.constant.value);
107 case MONO_VARIABLE_SUMMARIZED_VALUE:
108 printf ("VARIABLE %d, delta %d", value->value.variable.variable, value->value.variable.delta);
110 case MONO_PHI_SUMMARIZED_VALUE: {
113 for (phi = 0; phi < value->value.phi.number_of_alternatives; phi++) {
114 if (phi) printf (",");
115 printf ("%d", value->value.phi.phi_alternatives [phi]);
121 g_assert_not_reached ();
126 print_summarized_value_relation (MonoSummarizedValueRelation *relation) {
127 printf ("Relation ");
128 print_relation (relation->relation);
129 printf (" with value ");
130 print_summarized_value (&(relation->related_value));
135 print_summarized_value_relation_chain (MonoSummarizedValueRelation *relation) {
136 printf ("Relations:\n");
138 print_summarized_value_relation (relation);
140 relation = relation->next;
146 print_evaluation_context_status (MonoRelationsEvaluationStatus status) {
147 if (status == MONO_RELATIONS_EVALUATION_NOT_STARTED) {
148 printf ("EVALUATION_NOT_STARTED");
150 gboolean print_or = FALSE;
153 if (status & MONO_RELATIONS_EVALUATION_IN_PROGRESS) {
154 if (print_or) printf ("|");
155 printf ("EVALUATION_IN_PROGRESS");
158 if (status & MONO_RELATIONS_EVALUATION_COMPLETED) {
159 if (print_or) printf ("|");
160 printf ("EVALUATION_COMPLETED");
163 if (status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING) {
164 if (print_or) printf ("|");
165 printf ("RECURSIVELY_ASCENDING");
168 if (status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING) {
169 if (print_or) printf ("|");
170 printf ("RECURSIVELY_DESCENDING");
173 if (status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE) {
174 if (print_or) printf ("|");
175 printf ("RECURSIVELY_INDEFINITE");
184 print_evaluation_context_ranges (MonoRelationsEvaluationRanges *ranges) {
185 printf ("(ranges: zero [%d,%d], variable [%d,%d])", ranges->zero.lower, ranges->zero.upper, ranges->variable.lower, ranges->variable.upper);
189 print_evaluation_context (MonoRelationsEvaluationContext *context) {
190 printf ("Context status: ");
191 print_evaluation_context_status (context->status);
192 if (context->status & (MONO_RELATIONS_EVALUATION_IN_PROGRESS|MONO_RELATIONS_EVALUATION_COMPLETED)) {
193 print_evaluation_context_ranges (&(context->ranges));
200 print_evaluation_area (MonoVariableRelationsEvaluationArea *area) {
202 printf ("Dump of evaluation area (%d variables):\n", area->cfg->num_varinfo);
203 for (i = 0; i < area->cfg->num_varinfo; i++) {
204 printf ("Variable %d: ", i);
205 print_evaluation_context (&(area->contexts [i]));
206 print_summarized_value_relation_chain (&(area->relations [i]));
211 print_evaluation_area_contexts (MonoVariableRelationsEvaluationArea *area) {
213 printf ("Dump of evaluation area contexts (%d variables):\n", area->cfg->num_varinfo);
214 for (i = 0; i < area->cfg->num_varinfo; i++) {
215 printf ("Variable %d: ", i);
216 print_evaluation_context (&(area->contexts [i]));
222 * Given a MonoInst, if it is a store to a variable return the MonoInst that
223 * represents the stored value.
224 * If anything goes wrong, return NULL.
225 * store: the MonoInst that should be a store
226 * expected_variable_index: the variable where the value should be stored
227 * return: either the stored value, or NULL
230 get_variable_value_from_store_instruction (MonoInst *store, int expected_variable_index) {
231 switch (store->opcode) {
240 if (TRACE_ABC_REMOVAL) {
241 printf ("[store instruction found]");
243 if ((store->inst_left->opcode == OP_LOCAL) || (store->inst_left->opcode == OP_ARG)) {
244 int variable_index = store->inst_left->inst_c0;
245 if (TRACE_ABC_REMOVAL) {
246 printf ("[value put in local %d (expected %d)]", variable_index, expected_variable_index);
248 if (variable_index == expected_variable_index) {
249 return store->inst_right;
265 * Check if the delta of an integer variable value is safe with respect
266 * to the variable size in bytes and its kind (signed or unsigned).
267 * If the delta is not safe, make the value an "any".
270 check_delta_safety (MonoVariableRelationsEvaluationArea *area, MonoSummarizedValue *value) {
271 if (value->type == MONO_VARIABLE_SUMMARIZED_VALUE) {
272 int variable = value->value.variable.variable;
273 int delta = value->value.variable.delta;
274 if ((area->variable_value_kind [variable]) & MONO_UNSIGNED_VALUE_FLAG) {
276 MAKE_VALUE_ANY (*value);
279 if (((area->variable_value_kind [variable]) & MONO_INTEGER_VALUE_SIZE_BITMASK) < 4) {
280 MAKE_VALUE_ANY (*value);
281 } else if (delta > 16) {
282 MAKE_VALUE_ANY (*value);
288 /* Prototype, definition comes later */
290 summarize_array_value (MonoVariableRelationsEvaluationArea *area, MonoInst *value, MonoSummarizedValue *result, gboolean is_array_type);
293 * Given a MonoInst representing an integer value, store it in "summarized" form.
294 * result_value_kind: the "expected" kind of result;
295 * result: the "summarized" value
296 * returns the "actual" kind of result, if guessable (otherwise MONO_UNKNOWN_INTEGER_VALUE)
298 static MonoIntegerValueKind
299 summarize_integer_value (MonoVariableRelationsEvaluationArea *area, MonoInst *value, MonoSummarizedValue *result, MonoIntegerValueKind result_value_kind) {
300 MonoIntegerValueKind value_kind;
302 if (value->type == STACK_I8) {
303 value_kind = MONO_INTEGER_VALUE_SIZE_8;
304 } else if (value->type == STACK_I4) {
305 value_kind = MONO_INTEGER_VALUE_SIZE_4;
307 value_kind = MONO_UNKNOWN_INTEGER_VALUE;
310 switch (value->opcode) {
312 result->type = MONO_CONSTANT_SUMMARIZED_VALUE;
313 result->value.constant.value = value->inst_c0;
317 result->type = MONO_VARIABLE_SUMMARIZED_VALUE;
318 result->value.variable.variable = value->inst_c0;
319 result->value.variable.delta = 0;
320 value_kind = area->variable_value_kind [value->inst_c0];
323 value_kind = MONO_INTEGER_VALUE_SIZE_1;
326 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_1;
329 value_kind = MONO_INTEGER_VALUE_SIZE_2;
332 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_2;
335 value_kind = MONO_INTEGER_VALUE_SIZE_4;
338 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_4;
341 value_kind = MONO_INTEGER_VALUE_SIZE_8;
344 value_kind = SIZEOF_VOID_P;
346 if ((value->inst_left->opcode == OP_LOCAL) || (value->inst_left->opcode == OP_ARG)) {
347 value_kind = summarize_integer_value (area, value->inst_left, result, result_value_kind);
349 MAKE_VALUE_ANY (*result);
353 MonoSummarizedValue left_value;
354 MonoSummarizedValue right_value;
355 summarize_integer_value (area, value->inst_left, &left_value, result_value_kind);
356 summarize_integer_value (area, value->inst_right, &right_value, result_value_kind);
358 if (left_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
359 if (right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
360 result->type = MONO_VARIABLE_SUMMARIZED_VALUE;
361 result->value.variable.variable = left_value.value.variable.variable;
362 result->value.variable.delta = left_value.value.variable.delta + right_value.value.constant.value;
364 MAKE_VALUE_ANY (*result);
366 } else if (right_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
367 if (left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
368 result->type = MONO_VARIABLE_SUMMARIZED_VALUE;
369 result->value.variable.variable = right_value.value.variable.variable;
370 result->value.variable.delta = left_value.value.constant.value + right_value.value.variable.delta;
372 MAKE_VALUE_ANY (*result);
374 } else if ((right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) && (left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE)) {
375 /* This should not happen if constant folding has been done */
376 result->type = MONO_CONSTANT_SUMMARIZED_VALUE;
377 result->value.constant.value = left_value.value.constant.value + right_value.value.constant.value;
379 MAKE_VALUE_ANY (*result);
381 if (result->type == MONO_VARIABLE_SUMMARIZED_VALUE) {
382 check_delta_safety (area, result);
387 MonoSummarizedValue left_value;
388 MonoSummarizedValue right_value;
389 summarize_integer_value (area, value->inst_left, &left_value, result_value_kind);
390 summarize_integer_value (area, value->inst_right, &right_value, result_value_kind);
392 if (left_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
393 if (right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
394 result->type = MONO_VARIABLE_SUMMARIZED_VALUE;
395 result->value.variable.variable = left_value.value.variable.variable;
396 result->value.variable.delta = left_value.value.variable.delta - right_value.value.constant.value;
398 MAKE_VALUE_ANY (*result);
400 } else if ((right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) && (left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE)) {
401 /* This should not happen if constant folding has been done */
402 result->type = MONO_CONSTANT_SUMMARIZED_VALUE;
403 result->value.constant.value = left_value.value.constant.value - right_value.value.constant.value;
405 MAKE_VALUE_ANY (*result);
407 if (result->type == MONO_VARIABLE_SUMMARIZED_VALUE) {
408 check_delta_safety (area, result);
413 MonoSummarizedValue left_value;
414 MonoSummarizedValue right_value;
415 int constant_operand_value;
417 summarize_integer_value (area, value->inst_left, &left_value, result_value_kind);
418 summarize_integer_value (area, value->inst_right, &right_value, result_value_kind);
420 if (left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
421 constant_operand_value = left_value.value.constant.value;
422 } else if (right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
423 constant_operand_value = right_value.value.constant.value;
425 constant_operand_value = 0;
428 if (constant_operand_value > 0) {
429 if (constant_operand_value <= 0xff) {
430 if ((result_value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) > 1) {
431 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_1;
433 } else if (constant_operand_value <= 0xffff) {
434 if ((result_value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) > 2) {
435 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_2;
440 MAKE_VALUE_ANY (*result);
444 case CEE_CONV_OVF_I1:
445 case CEE_CONV_OVF_I1_UN:
446 value_kind = MONO_INTEGER_VALUE_SIZE_1;
447 MAKE_VALUE_ANY (*result);
450 case CEE_CONV_OVF_U1:
451 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_1;
452 MAKE_VALUE_ANY (*result);
455 case CEE_CONV_OVF_I2:
456 case CEE_CONV_OVF_I2_UN:
457 value_kind = MONO_INTEGER_VALUE_SIZE_2;
458 MAKE_VALUE_ANY (*result);
461 case CEE_CONV_OVF_U2:
462 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_2;
463 MAKE_VALUE_ANY (*result);
466 summarize_array_value (area, value->inst_left, result, TRUE);
467 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_4;
470 value_kind = summarize_integer_value (area, value->inst_left, result, result_value_kind);
473 result->type = MONO_PHI_SUMMARIZED_VALUE;
474 result->value.phi.number_of_alternatives = *(value->inst_phi_args);
475 result->value.phi.phi_alternatives = value->inst_phi_args + 1;
478 MAKE_VALUE_ANY (*result);
484 * Given a MonoInst representing an array value, store it in "summarized" form.
485 * result: the "summarized" value
486 * is_array_type: TRUE of we are *sure* that an eventual OP_PCONST will point
487 * to a MonoArray (this can happen for already initialized readonly static fields,
488 * in which case we will get the array length directly from the MonoArray)
491 summarize_array_value (MonoVariableRelationsEvaluationArea *area, MonoInst *value, MonoSummarizedValue *result, gboolean is_array_type) {
492 switch (value->opcode) {
495 result->type = MONO_VARIABLE_SUMMARIZED_VALUE;
496 result->value.variable.variable = value->inst_c0;
497 result->value.variable.delta = 0;
500 summarize_array_value (area, value->inst_left, result, FALSE);
503 summarize_integer_value (area, value->inst_newa_len, result, MONO_UNKNOWN_INTEGER_VALUE);
506 if ((is_array_type) && (value->inst_p0 != NULL)) {
507 MonoArray *array = (MonoArray *) (value->inst_p0);
508 result->type = MONO_CONSTANT_SUMMARIZED_VALUE;
509 result->value.constant.value = array->max_length;
511 MAKE_VALUE_ANY (*result);
515 result->type = MONO_PHI_SUMMARIZED_VALUE;
516 result->value.phi.number_of_alternatives = *(value->inst_phi_args);
517 result->value.phi.phi_alternatives = value->inst_phi_args + 1;
520 MAKE_VALUE_ANY (*result);
524 static MonoValueRelation
525 get_relation_from_branch_instruction (int opcode) {
528 return MONO_EQ_RELATION;
531 return MONO_LT_RELATION;
534 return MONO_LE_RELATION;
537 return MONO_GT_RELATION;
540 return MONO_GE_RELATION;
542 return MONO_NE_RELATION;
544 return MONO_ANY_RELATION;
549 * Given a BB, find its entry condition and put its relations in a
550 * "MonoAdditionalVariableRelationsForBB" structure.
552 * relations: the resulting relations (entry condition of the given BB)
555 get_relations_from_previous_bb (MonoVariableRelationsEvaluationArea *area, MonoBasicBlock *bb, MonoAdditionalVariableRelationsForBB *relations) {
556 MonoBasicBlock *in_bb;
558 MonoValueRelation branch_relation;
559 MonoValueRelation symmetric_relation;
561 INITIALIZE_VALUE_RELATION (&(relations->relation1.relation));
562 relations->relation1.relation.relation_is_static_definition = FALSE;
563 relations->relation1.insertion_point = NULL;
564 relations->relation1.variable = -1;
565 INITIALIZE_VALUE_RELATION (&(relations->relation2.relation));
566 relations->relation2.relation.relation_is_static_definition = FALSE;
567 relations->relation2.insertion_point = NULL;
568 relations->relation2.variable = -1;
571 if (bb->in_count == 1) { /* Should write the code to "sum" conditions... */
572 in_bb = bb->in_bb [0];
573 branch = in_bb->last_ins;
574 if (branch == NULL) return;
575 branch_relation = get_relation_from_branch_instruction (branch->opcode);
576 if ((branch_relation != MONO_ANY_RELATION) && (branch->inst_left->opcode == OP_COMPARE)) {
577 MonoSummarizedValue left_value;
578 MonoSummarizedValue right_value;
581 if (branch->inst_true_bb == bb) {
583 } else if (branch->inst_false_bb == bb) {
587 g_assert_not_reached ();
591 branch_relation = MONO_NEGATED_RELATION (branch_relation);
593 symmetric_relation = MONO_SYMMETRIC_RELATION (branch_relation);
595 summarize_integer_value (area, branch->inst_left->inst_left, &left_value, MONO_UNKNOWN_INTEGER_VALUE);
596 summarize_integer_value (area, branch->inst_left->inst_right, &right_value, MONO_UNKNOWN_INTEGER_VALUE);
598 if ((left_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) && ((right_value.type == MONO_VARIABLE_SUMMARIZED_VALUE)||(right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE))) {
599 relations->relation1.variable = left_value.value.variable.variable;
600 relations->relation1.relation.relation = branch_relation;
601 relations->relation1.relation.related_value = right_value;
602 if (right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
603 relations->relation1.relation.related_value.value.constant.value -= left_value.value.variable.delta;
605 relations->relation1.relation.related_value.value.variable.delta -= left_value.value.variable.delta;
608 if ((right_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) && ((left_value.type == MONO_VARIABLE_SUMMARIZED_VALUE)||(left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE))) {
609 relations->relation2.variable = right_value.value.variable.variable;
610 relations->relation2.relation.relation = symmetric_relation;
611 relations->relation2.relation.related_value = left_value;
612 if (left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
613 relations->relation2.relation.related_value.value.constant.value -= right_value.value.variable.delta;
615 relations->relation2.relation.related_value.value.variable.delta -= right_value.value.variable.delta;
624 * Add the given relations to the evaluation area.
625 * area: the evaluation area
626 * change: the relations that must be added
629 apply_change_to_evaluation_area (MonoVariableRelationsEvaluationArea *area, MonoAdditionalVariableRelation *change) {
630 MonoSummarizedValueRelation *base_relation;
632 if (change->relation.relation != MONO_ANY_RELATION) {
633 base_relation = &(area->relations [change->variable]);
634 while ((base_relation->next != NULL) && (base_relation->next->relation_is_static_definition)) {
635 base_relation = base_relation->next;
637 change->insertion_point = base_relation;
638 change->relation.next = base_relation->next;
639 base_relation->next = &(change->relation);
644 * Remove the given relation from the evaluation area.
645 * change: the relation that must be removed
648 remove_change_from_evaluation_area (MonoAdditionalVariableRelation *change) {
649 if (change->insertion_point != NULL) {
650 change->insertion_point->next = change->relation.next;
651 change->relation.next = NULL;
657 clean_contexts (MonoRelationsEvaluationContext *contexts, int number) {
659 for (i = 0; i < number; i++) {
660 contexts [i].status = MONO_RELATIONS_EVALUATION_NOT_STARTED;
666 * Perform the intersection of a range and a constant value (taking into
667 * account the relation that the value has with the range).
668 * range: the range that will be intersected with the value
669 * value: the value that will be intersected with the range
670 * relation: the relation between the range and the value
673 intersect_value( MonoRelationsEvaluationRange *range, int value, MonoValueRelation relation ) {
675 case MONO_NO_RELATION:
676 MONO_MAKE_RELATIONS_EVALUATION_RANGE_IMPOSSIBLE (*range);
678 case MONO_ANY_RELATION:
680 case MONO_EQ_RELATION:
681 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, value);
682 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, value);
684 case MONO_NE_RELATION: {
685 /* IMPROVEMENT Figure this out! (ignoring it is safe anyway) */
688 case MONO_LT_RELATION:
689 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (value));
691 case MONO_LE_RELATION:
692 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, value);
694 case MONO_GT_RELATION:
695 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (value));
697 case MONO_GE_RELATION:
698 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, value);
701 g_assert_not_reached();
707 * Perform the intersection of two pairs of ranges (taking into account the
708 * relation between the ranges and a given delta).
709 * ranges: the ranges that will be intersected
710 * other_ranges the other ranges that will be intersected
711 * delta: the delta between the pairs of ranges
712 * relation: the relation between the pairs of ranges
715 intersect_ranges( MonoRelationsEvaluationRanges *ranges, MonoRelationsEvaluationRanges *other_ranges, int delta, MonoValueRelation relation ) {
718 case MONO_NO_RELATION:
719 MONO_MAKE_RELATIONS_EVALUATION_RANGES_IMPOSSIBLE (*ranges);
721 case MONO_ANY_RELATION:
723 case MONO_EQ_RELATION:
724 MONO_RELATIONS_EVALUATION_RANGES_INTERSECTION (*ranges, *other_ranges);
726 case MONO_NE_RELATION: {
727 /* FIXME Figure this out! (ignoring it is safe anyway) */
730 case MONO_LT_RELATION:
731 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->zero.upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->zero.upper));
732 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->variable.upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->variable.upper));
734 case MONO_LE_RELATION:
735 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->zero.upper, other_ranges->zero.upper);
736 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->variable.upper, other_ranges->variable.upper);
738 case MONO_GT_RELATION:
739 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->zero.lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->zero.lower));
740 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->variable.lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->variable.lower));
742 case MONO_GE_RELATION:
743 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->zero.lower, other_ranges->zero.lower);
744 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->variable.lower, other_ranges->variable.lower);
747 g_assert_not_reached();
750 MonoRelationsEvaluationRanges translated_ranges = *other_ranges;
751 MONO_ADD_DELTA_SAFELY_TO_RANGES (translated_ranges, delta);
752 intersect_ranges( ranges, &translated_ranges, FALSE, relation );
757 * Recursive method that traverses the relation graph to evaluate the
758 * relation between two variables.
759 * At the end of the execution, the resulting ranges are in the context of
760 * the "starting" variable.
761 * area: the current evaluation area (it contains the relation graph and
762 * memory for all the evaluation contexts is already allocated)
763 * variable: starting variable (the value ranges in its context are the result
764 * of the execution of this procedure)
765 * target_variable: the variable with respect to which the starting variable
766 * is evaluated (tipically the starting variable is the index
767 * and the target one is the array (which means its length))
768 * father_context: the previous evaluation context in recursive invocations
769 * (or NULL for the first invocation)
772 evaluate_relation_with_target_variable (MonoVariableRelationsEvaluationArea *area, int variable, int target_variable, MonoRelationsEvaluationContext *father_context) {
773 MonoRelationsEvaluationContext *context = &(area->contexts [variable]);
775 // First of all, we check the evaluation status
776 // (what must be done is *very* different in each case)
777 switch (context->status) {
778 case MONO_RELATIONS_EVALUATION_NOT_STARTED: {
779 MonoSummarizedValueRelation *relation = &(area->relations [variable]);
781 if (TRACE_ABC_REMOVAL) {
782 printf ("Evaluating varible %d (target variable %d)\n", variable, target_variable);
783 print_summarized_value_relation (relation);
787 // We properly inizialize the context
788 context->status = MONO_RELATIONS_EVALUATION_IN_PROGRESS;
789 context->father = father_context;
790 MONO_MAKE_RELATIONS_EVALUATION_RANGES_WEAK (context->ranges);
792 // If we have found the target variable, we can set the range
793 // related to it in the context to "equal" (which is [0,0])
794 if (variable == target_variable) {
795 if (TRACE_ABC_REMOVAL) {
796 printf ("Target variable reached (%d), continuing to evaluate relations with constants\n", variable);
798 context->ranges.variable.lower = 0;
799 context->ranges.variable.upper = 0;
802 // Examine all relations for this variable (scan the list)
803 // The contribute of each relation will be intersected (logical and)
804 while (relation != NULL) {
805 context->current_relation = relation;
807 if (TRACE_ABC_REMOVAL) {
808 printf ("Processing (%d): ", variable);
809 print_summarized_value_relation (relation);
813 // We decie what to do according the the type of the related value
814 switch (relation->related_value.type) {
815 case MONO_ANY_SUMMARIZED_VALUE:
816 // No added information, skip it
818 case MONO_CONSTANT_SUMMARIZED_VALUE:
819 // Intersect range with constant (taking into account the relation)
820 intersect_value (&(context->ranges.zero), relation->related_value.value.constant.value, relation->relation);
822 case MONO_VARIABLE_SUMMARIZED_VALUE:
823 // Generally, evaluate related variable and intersect ranges.
824 // However, some check is necessary...
826 // If the relation is "ANY", nothing to do (no added information)
827 if (relation->relation != MONO_ANY_RELATION) {
828 int related_variable = relation->related_value.value.variable.variable;
829 MonoRelationsEvaluationContext *related_context = &(area->contexts [related_variable]);
831 // The second condition in the "or" avoids messing with "back edges" in the graph traversal
832 // (they are simply ignored instead of triggering the handling of recursion)
833 if ( (related_context->status == MONO_RELATIONS_EVALUATION_NOT_STARTED) || !
834 ((related_context->current_relation->related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) &&
835 (related_context->current_relation->related_value.value.variable.variable == variable))) {
836 // Evaluate the related variable
837 evaluate_relation_with_target_variable (area, related_variable, target_variable, context);
839 // Check if we are part of a recursive loop
840 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) {
841 if (TRACE_ABC_REMOVAL) {
842 printf ("Recursivity detected for varible %d (target variable %d), status ", variable, target_variable);
843 print_evaluation_context_status (context->status);
846 // If we are, check if the evaluation of the related variable is complete
847 if (related_context->status == MONO_RELATIONS_EVALUATION_COMPLETED) {
848 // If it is complete, we are part of a recursive definition.
849 // Since it is a *definition* (and definitions are evaluated *before*
850 // conditions because they are first in the list), intersection is not
851 // strictly necessary, we simply copy the ranges and apply the delta
852 context->ranges = related_context->ranges;
853 /* Delta has already been checked for over/under-flow when evaluating values */
854 MONO_ADD_DELTA_SAFELY_TO_RANGES (context->ranges, relation->related_value.value.variable.delta);
855 context->status = MONO_RELATIONS_EVALUATION_COMPLETED;
856 if (TRACE_ABC_REMOVAL) {
857 printf (", ranges already computed, result: \n");
858 print_evaluation_context_ranges (&(context->ranges));
859 printf (" (delta is %d)\n", relation->related_value.value.variable.delta);
862 // If it is not complete, do nothing (we do not have enough information)
863 if (TRACE_ABC_REMOVAL) {
864 printf (", ranges not computed\n");
868 // If we are not (the common case) intersect the result
869 intersect_ranges( &(context->ranges), &(related_context->ranges), relation->related_value.value.variable.delta, relation->relation );
872 if (TRACE_ABC_REMOVAL) {
873 printf ("Relation is a back-edge in this traversal, skipping\n");
878 case MONO_PHI_SUMMARIZED_VALUE: {
879 // We must compute all PHI alternatives, combining the results (with a union, which is a logical "or"),
880 // and intersect this result with the ranges in the context; we must also take into account recursions
881 // (with loops that can be ascending, descending, or indefinite)
882 MonoRelationsEvaluationRanges phi_ranges;
884 gboolean is_ascending = FALSE;
885 gboolean is_descending = FALSE;
887 MONO_MAKE_RELATIONS_EVALUATION_RANGES_IMPOSSIBLE (phi_ranges);
888 for (phi = 0; phi < relation->related_value.value.phi.number_of_alternatives; phi++) {
889 int phi_alternative = relation->related_value.value.phi.phi_alternatives [phi];
890 evaluate_relation_with_target_variable (area, phi_alternative, target_variable, context);
892 // This means we are part of a recursive loop
893 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) {
894 if (TRACE_ABC_REMOVAL) {
895 printf ("Recursivity detected for varible %d (target variable %d), status ", variable, target_variable);
896 print_evaluation_context_status (context->status);
899 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING) {
902 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING) {
903 is_descending = TRUE;
905 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE) {
907 is_descending = TRUE;
910 // Clear "recursivity" bits in the status (recursion has been handled)
911 context->status = MONO_RELATIONS_EVALUATION_IN_PROGRESS;
913 MONO_RELATIONS_EVALUATION_RANGES_UNION (phi_ranges, area->contexts [phi_alternative].ranges);
917 // Apply the effects of all recursive loops
919 phi_ranges.zero.upper = INT_MAX;
920 phi_ranges.variable.upper = INT_MAX;
923 phi_ranges.zero.lower = INT_MIN;
924 phi_ranges.variable.lower = INT_MIN;
927 // Intersect final result
928 MONO_RELATIONS_EVALUATION_RANGES_INTERSECTION (context->ranges, phi_ranges);
932 g_assert_not_reached();
935 // Pass to next relation
936 relation = relation->next;
939 // Check if any recursivity bits are still in the status, and in any case clear them
940 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) {
941 if (TRACE_ABC_REMOVAL) {
942 printf ("Recursivity for varible %d (target variable %d) discards computation, status ", variable, target_variable);
943 print_evaluation_context_status (context->status);
946 // If yes, we did not have enough information (most likely we were evaluated inside a PHI, but we also
947 // depended on the same PHI, which was still in evaluation...), so clear the status to "NOT_STARTED"
948 // (if we will be evaluated again, the PHI will be already done, so our evaluation will succeed)
949 context->status = MONO_RELATIONS_EVALUATION_NOT_STARTED;
951 if (TRACE_ABC_REMOVAL) {
952 printf ("Ranges for varible %d (target variable %d) computed: ", variable, target_variable);
953 print_evaluation_context_ranges (&(context->ranges));
956 // If not (the common case) the evaluation is complete, and the result is in the context
957 context->status = MONO_RELATIONS_EVALUATION_COMPLETED;
961 case MONO_RELATIONS_EVALUATION_IN_PROGRESS: {
962 // This means we are in a recursive loop
963 MonoRelationsEvaluationContext *current_context = father_context;
964 MonoRelationsEvaluationContext *last_context = context->father;
965 gboolean evaluation_can_be_recursive = TRUE;
966 gboolean evaluation_is_definition = TRUE;
969 if (TRACE_ABC_REMOVAL) {
970 printf ("Evaluation of varible %d (target variable %d) already in progress\n", variable, target_variable);
971 print_evaluation_context (context);
972 print_summarized_value_relation (context->current_relation);
976 // We must check if the loop can be a recursive definition (we scan the whole loop)
977 while (current_context != last_context) {
978 if (current_context == NULL) {
979 printf ("Broken recursive ring in ABC removal\n");
980 g_assert_not_reached ();
983 if (current_context->current_relation->relation_is_static_definition) {
984 if (current_context->current_relation->related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
985 /* No need to check path_value for over/under-flow, since delta should be safe */
986 path_value += current_context->current_relation->related_value.value.variable.delta;
987 } else if (current_context->current_relation->related_value.type != MONO_PHI_SUMMARIZED_VALUE) {
988 evaluation_can_be_recursive = FALSE;
991 evaluation_is_definition = FALSE;
992 evaluation_can_be_recursive = FALSE;
995 current_context = current_context->father;
998 // If this is a recursive definition, we properly flag the status in all the involved contexts
999 if (evaluation_is_definition) {
1000 MonoRelationsEvaluationStatus recursive_status;
1001 if (evaluation_can_be_recursive) {
1002 if (path_value > 0) {
1003 recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING;
1004 } else if (path_value < 0) {
1005 recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING;
1007 recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE;
1010 recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE;
1013 if (TRACE_ABC_REMOVAL) {
1014 printf ("Recursivity accepted (");
1015 print_evaluation_context_status (recursive_status);
1019 current_context = father_context;
1020 while (current_context != last_context) {
1021 current_context->status |= recursive_status;
1022 current_context = current_context->father;
1025 if (TRACE_ABC_REMOVAL) {
1026 printf ("Recursivity rejected (some relation in the cycle is not a defintion)\n");
1031 case MONO_RELATIONS_EVALUATION_COMPLETED: {
1035 if (TRACE_ABC_REMOVAL) {
1036 printf ("Varible %d (target variable %d) already in a recursive ring, skipping\n", variable, target_variable);
1037 print_evaluation_context (context);
1038 print_summarized_value_relation (context->current_relation);
1047 * Apply the given value kind to the given range
1049 static void apply_value_kind_to_range (MonoRelationsEvaluationRange *range, MonoIntegerValueKind value_kind) {
1050 if (value_kind != MONO_UNKNOWN_INTEGER_VALUE) {
1051 if (value_kind & MONO_UNSIGNED_VALUE_FLAG) {
1052 if (range->lower < 0) {
1055 if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 1) {
1056 if (range->upper > 0xff) {
1057 range->upper = 0xff;
1059 } else if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 2) {
1060 if (range->upper > 0xffff) {
1061 range->upper = 0xffff;
1065 if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 1) {
1066 if (range->lower < -0x80) {
1067 range->lower = -0x80;
1069 if (range->upper > 0x7f) {
1070 range->upper = 0x7f;
1072 } else if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 2) {
1073 if (range->lower < -0x8000) {
1074 range->lower = -0x8000;
1076 if (range->upper > 0x7fff) {
1077 range->upper = 0x7fff;
1085 * Attempt the removal of bounds checks from a MonoInst.
1086 * inst: the MonoInst
1087 * area: the current evaluation area (it contains the relation graph and
1088 * memory for all the evaluation contexts is already allocated)
1091 remove_abc_from_inst (MonoInst *inst, MonoVariableRelationsEvaluationArea *area) {
1092 if (inst->opcode == CEE_LDELEMA) {
1093 MonoInst *array_inst = inst->inst_left;
1094 MonoInst *index_inst = inst->inst_right;
1095 MonoSummarizedValue array_value;
1096 MonoSummarizedValue index_value;
1097 MonoIntegerValueKind index_value_kind;
1099 /* First of all, examine the CEE_LDELEMA operands */
1100 summarize_array_value (area, array_inst, &array_value, TRUE);
1101 index_value_kind = summarize_integer_value (area, index_inst, &index_value, MONO_UNKNOWN_INTEGER_VALUE);
1103 /* If the array is a local variable... */
1104 if (array_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
1105 int array_variable = array_value.value.variable.variable;
1106 MonoRelationsEvaluationContext *array_context = &(area->contexts [array_variable]);
1108 if (index_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
1109 // The easiest case: we just evaluate the array length, to see if it has some relation
1110 // with the index constant, and act accordingly
1112 clean_contexts (area->contexts, area->cfg->num_varinfo);
1113 evaluate_relation_with_target_variable (area, array_variable, array_variable, NULL);
1115 if ((index_value.value.constant.value >= 0) && (index_value.value.constant.value < array_context->ranges.zero.lower)) {
1116 if (REPORT_ABC_REMOVAL) {
1117 printf ("ARRAY-ACCESS: removed bounds check on array %d with constant index %d in method %s\n",
1118 array_variable, index_value.value.constant.value, mono_method_full_name (area->cfg->method, TRUE));
1120 inst->flags |= (MONO_INST_NORANGECHECK);
1122 } else if (index_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
1123 // The common case: we must evaluate both the index and the array length, and check for relevant
1124 // relations both through variable definitions and as constant definitions
1126 int index_variable = index_value.value.variable.variable;
1127 MonoRelationsEvaluationContext *index_context = &(area->contexts [index_variable]);
1129 clean_contexts (area->contexts, area->cfg->num_varinfo);
1131 evaluate_relation_with_target_variable (area, index_variable, array_variable, NULL);
1132 evaluate_relation_with_target_variable (area, array_variable, array_variable, NULL);
1134 MONO_SUB_DELTA_SAFELY_FROM_RANGES (index_context->ranges, index_value.value.variable.delta);
1135 /* Apply index value kind */
1136 apply_value_kind_to_range (&(index_context->ranges.zero), index_value_kind);
1138 if (index_context->ranges.zero.lower >= 0) {
1139 if (TRACE_ABC_REMOVAL) {
1140 printf ("ARRAY-ACCESS: Removed lower bound check on array %d with index %d\n", array_variable, index_variable);
1142 if ((index_context->ranges.variable.upper < 0)||(index_context->ranges.zero.upper < array_context->ranges.zero.lower)) {
1143 if (REPORT_ABC_REMOVAL) {
1144 printf ("ARRAY-ACCESS: removed bounds check on array %d with index %d in method %s\n",
1145 array_variable, index_variable, mono_method_full_name (area->cfg->method, TRUE));
1147 inst->flags |= (MONO_INST_NORANGECHECK);
1150 if (TRACE_ABC_REMOVAL) {
1151 if (index_context->ranges.variable.upper < 0) {
1152 printf ("ARRAY-ACCESS: Removed upper bound check (through variable) on array %d with index %d\n", array_variable, index_variable);
1154 if (index_context->ranges.zero.upper < array_context->ranges.zero.lower) {
1155 printf ("ARRAY-ACCESS: Removed upper bound check (through constant) on array %d with index %d\n", array_variable, index_variable);
1159 } else if (array_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
1160 if (index_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
1161 /* The easiest possible case: constant with constant */
1162 if ((index_value.value.constant.value >= 0) && (index_value.value.constant.value < array_value.value.constant.value)) {
1163 if (REPORT_ABC_REMOVAL) {
1164 printf ("ARRAY-ACCESS: removed bounds check on array of constant length %d with constant index %d in method %s\n",
1165 array_value.value.constant.value, index_value.value.constant.value, mono_method_full_name (area->cfg->method, TRUE));
1167 inst->flags |= (MONO_INST_NORANGECHECK);
1169 } else if (index_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
1170 /* The index has a variable related value, which must be evaluated */
1171 int index_variable = index_value.value.variable.variable;
1172 MonoRelationsEvaluationContext *index_context = &(area->contexts [index_variable]);
1174 clean_contexts (area->contexts, area->cfg->num_varinfo);
1175 evaluate_relation_with_target_variable (area, index_variable, index_variable, NULL);
1176 /* Apply index value kind */
1177 apply_value_kind_to_range (&(index_context->ranges.zero), index_value_kind);
1179 if ((index_context->ranges.zero.lower >= 0) && (index_context->ranges.zero.upper < array_value.value.constant.value)) {
1180 if (REPORT_ABC_REMOVAL) {
1181 printf ("ARRAY-ACCESS: removed bounds check on array of constant length %d with index %d ranging from %d to %d in method %s\n",
1182 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));
1184 inst->flags |= (MONO_INST_NORANGECHECK);
1186 } else if (index_value_kind != MONO_UNKNOWN_INTEGER_VALUE) {
1187 /* The index has an unknown but bounded value */
1188 MonoRelationsEvaluationRange range;
1189 MONO_MAKE_RELATIONS_EVALUATION_RANGE_WEAK (range);
1190 apply_value_kind_to_range (&range, index_value_kind);
1192 if ((range.lower >= 0) && (range.upper < array_value.value.constant.value)) {
1193 if (REPORT_ABC_REMOVAL) {
1194 printf ("ARRAY-ACCESS: removed bounds check on array of constant length %d with unknown index ranging from %d to %d in method %s\n",
1195 array_value.value.constant.value, range.lower, range.upper, mono_method_full_name (area->cfg->method, TRUE));
1197 inst->flags |= (MONO_INST_NORANGECHECK);
1205 * Recursively scan a tree of MonoInst looking for array accesses.
1206 * inst: the root of the MonoInst tree
1207 * area: the current evaluation area (it contains the relation graph and
1208 * memory for all the evaluation contexts is already allocated)
1211 process_inst (MonoInst *inst, MonoVariableRelationsEvaluationArea *area) {
1212 if (inst->opcode == CEE_LDELEMA) { /* Handle OP_LDELEMA2D, too */
1213 if (TRACE_ABC_REMOVAL) {
1214 printf ("Attempting check removal...\n");
1217 remove_abc_from_inst (inst, area);
1220 if (mono_burg_arity [inst->opcode]) {
1221 process_inst (inst->inst_left, area);
1222 if (mono_burg_arity [inst->opcode] > 1) {
1223 process_inst (inst->inst_right, area);
1232 * Process a BB removing bounds checks from array accesses.
1233 * It does the following (in sequence):
1234 * - Get the BB entry condition
1235 * - Add its relations to the relation graph in the evaluation area
1236 * - Process all the MonoInst trees in the BB
1237 * - Recursively process all the children BBs in the dominator tree
1238 * - Remove the relations previously added to the relation graph
1240 * bb: the BB that must be processed
1241 * area: the current evaluation area (it contains the relation graph and
1242 * memory for all the evaluation contexts is already allocated)
1245 process_block (MonoBasicBlock *bb, MonoVariableRelationsEvaluationArea *area) {
1247 MonoInst *current_inst;
1248 MonoAdditionalVariableRelationsForBB additional_relations;
1249 GSList *dominated_bb;
1251 if (TRACE_ABC_REMOVAL) {
1252 printf ("Processing block %d [dfn %d]...\n", bb->block_num, bb->dfn);
1255 get_relations_from_previous_bb (area, bb, &additional_relations);
1256 if (TRACE_ABC_REMOVAL) {
1257 if (additional_relations.relation1.relation.relation != MONO_ANY_RELATION) {
1258 printf ("Adding relation 1 on variable %d: ", additional_relations.relation1.variable);
1259 print_summarized_value_relation (&(additional_relations.relation1.relation));
1262 if (additional_relations.relation2.relation.relation != MONO_ANY_RELATION) {
1263 printf ("Adding relation 2 on variable %d: ", additional_relations.relation2.variable);
1264 print_summarized_value_relation (&(additional_relations.relation2.relation));
1268 apply_change_to_evaluation_area (area, &(additional_relations.relation1));
1269 apply_change_to_evaluation_area (area, &(additional_relations.relation2));
1272 MONO_BB_FOR_EACH_INS (bb, current_inst) {
1273 if (TRACE_ABC_REMOVAL) {
1274 printf ("Processing instruction %d\n", inst_index);
1278 process_inst (current_inst, area);
1282 if (TRACE_ABC_REMOVAL) {
1283 printf ("Processing block %d [dfn %d] done.\n", bb->block_num, bb->dfn);
1286 for (dominated_bb = bb->dominated; dominated_bb != NULL; dominated_bb = dominated_bb->next) {
1287 process_block ((MonoBasicBlock*) (dominated_bb->data), area);
1290 remove_change_from_evaluation_area (&(additional_relations.relation1));
1291 remove_change_from_evaluation_area (&(additional_relations.relation2));
1297 * mono_perform_abc_removal:
1298 * @cfg: Control Flow Graph
1300 * Performs the ABC removal from a cfg in SSA form.
1301 * It does the following:
1302 * - Prepare the evaluation area
1303 * - Allocate memory for the relation graph in the evaluation area
1304 * (of course, only for variable definitions) and summarize there all
1305 * variable definitions
1306 * - Allocate memory for the evaluation contexts in the evaluation area
1307 * - Recursively process all the BBs in the dominator tree (it is enough
1308 * to invoke the processing on the entry BB)
1310 * cfg: the method code
1313 mono_perform_abc_removal (MonoCompile *cfg)
1315 MonoVariableRelationsEvaluationArea area;
1318 verbose_level = cfg->verbose_level;
1320 if (TRACE_ABC_REMOVAL) {
1321 printf ("Removing array bound checks in %s\n", mono_method_full_name (cfg->method, TRUE));
1325 area.relations = (MonoSummarizedValueRelation *)
1326 mono_mempool_alloc (cfg->mempool, sizeof (MonoSummarizedValueRelation) * (cfg->num_varinfo) * 2);
1327 area.contexts = (MonoRelationsEvaluationContext *)
1328 mono_mempool_alloc (cfg->mempool, sizeof (MonoRelationsEvaluationContext) * (cfg->num_varinfo));
1329 area.variable_value_kind = (MonoIntegerValueKind *)
1330 mono_mempool_alloc (cfg->mempool, sizeof (MonoIntegerValueKind) * (cfg->num_varinfo));
1331 for (i = 0; i < cfg->num_varinfo; i++) {
1332 area.variable_value_kind [i] = MONO_UNKNOWN_INTEGER_VALUE;
1333 area.relations [i].relation = MONO_EQ_RELATION;
1334 area.relations [i].relation_is_static_definition = TRUE;
1335 area.relations [i].next = NULL;
1336 if (MONO_VARINFO (cfg, i)->def != NULL) {
1337 MonoInst *value = get_variable_value_from_store_instruction (MONO_VARINFO (cfg, i)->def, i);
1338 if (value != NULL) {
1339 gboolean is_array_type;
1340 MonoIntegerValueKind effective_value_kind;
1341 MonoRelationsEvaluationRange range;
1342 MonoSummarizedValueRelation *type_relation;
1344 switch (cfg->varinfo [i]->inst_vtype->type) {
1345 case MONO_TYPE_ARRAY:
1346 case MONO_TYPE_SZARRAY:
1347 is_array_type = TRUE;
1348 goto handle_array_value;
1349 case MONO_TYPE_OBJECT:
1350 is_array_type = FALSE;
1352 summarize_array_value (&area, value, &(area.relations [i].related_value), is_array_type);
1353 if (TRACE_ABC_REMOVAL) {
1354 printf ("Summarized variable %d as array (is_array_type = %s): ", i, (is_array_type?"TRUE":"FALSE"));
1355 print_summarized_value (&(area.relations [i].related_value));
1360 area.variable_value_kind [i] = MONO_INTEGER_VALUE_SIZE_1;
1361 goto handle_integer_value;
1363 area.variable_value_kind [i] = MONO_UNSIGNED_INTEGER_VALUE_SIZE_1;
1364 goto handle_integer_value;
1366 area.variable_value_kind [i] = MONO_INTEGER_VALUE_SIZE_2;
1367 goto handle_integer_value;
1369 area.variable_value_kind [i] = MONO_UNSIGNED_INTEGER_VALUE_SIZE_2;
1370 goto handle_integer_value;
1372 area.variable_value_kind [i] = MONO_INTEGER_VALUE_SIZE_4;
1373 goto handle_integer_value;
1375 area.variable_value_kind [i] = MONO_UNSIGNED_INTEGER_VALUE_SIZE_4;
1376 goto handle_integer_value;
1378 area.variable_value_kind [i] = SIZEOF_VOID_P;
1379 goto handle_integer_value;
1381 area.variable_value_kind [i] = (MONO_UNSIGNED_VALUE_FLAG|SIZEOF_VOID_P);
1382 goto handle_integer_value;
1384 area.variable_value_kind [i] = MONO_INTEGER_VALUE_SIZE_8;
1385 goto handle_integer_value;
1387 area.variable_value_kind [i] = MONO_UNSIGNED_INTEGER_VALUE_SIZE_8;
1388 handle_integer_value:
1389 effective_value_kind = summarize_integer_value (&area, value, &(area.relations [i].related_value), area.variable_value_kind [i]);
1390 MONO_MAKE_RELATIONS_EVALUATION_RANGE_WEAK (range);
1391 apply_value_kind_to_range (&range, area.variable_value_kind [i]);
1392 apply_value_kind_to_range (&range, effective_value_kind);
1394 if (range.upper < INT_MAX) {
1395 type_relation = (MonoSummarizedValueRelation *) mono_mempool_alloc (cfg->mempool, sizeof (MonoSummarizedValueRelation));
1396 type_relation->relation = MONO_LE_RELATION;
1397 type_relation->related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE;
1398 type_relation->related_value.value.constant.value = range.upper;
1399 type_relation->relation_is_static_definition = TRUE;
1400 type_relation->next = area.relations [i].next;
1401 area.relations [i].next = type_relation;
1402 if (TRACE_ABC_REMOVAL) {
1403 printf ("[var%d <= %d]", i, range.upper);
1406 if (range.lower > INT_MIN) {
1407 type_relation = (MonoSummarizedValueRelation *) mono_mempool_alloc (cfg->mempool, sizeof (MonoSummarizedValueRelation));
1408 type_relation->relation = MONO_GE_RELATION;
1409 type_relation->related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE;
1410 type_relation->related_value.value.constant.value = range.lower;
1411 type_relation->relation_is_static_definition = TRUE;
1412 type_relation->next = area.relations [i].next;
1413 area.relations [i].next = type_relation;
1414 if (TRACE_ABC_REMOVAL) {
1415 printf ("[var%d >= %d]", i, range.lower);
1418 if (TRACE_ABC_REMOVAL) {
1419 printf ("Summarized variable %d: ", i);
1420 print_summarized_value (&(area.relations [i].related_value));
1425 MAKE_VALUE_ANY (area.relations [i].related_value);
1426 if (TRACE_ABC_REMOVAL) {
1427 printf ("Variable %d not handled (type %d)\n", i, cfg->varinfo [i]->inst_vtype->type);
1431 MAKE_VALUE_ANY (area.relations [i].related_value);
1432 if (TRACE_ABC_REMOVAL) {
1433 printf ("Definition of variable %d is not a proper store\n", i);
1437 MAKE_VALUE_ANY (area.relations [i].related_value);
1438 if (TRACE_ABC_REMOVAL) {
1439 printf ("Variable %d has no definition, probably it is an argument\n", i);
1443 for (i = 0; i < cfg->num_varinfo; i++) {
1444 if (area.relations [i].related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
1445 int related_index = cfg->num_varinfo + i;
1446 int related_variable = area.relations [i].related_value.value.variable.variable;
1448 area.relations [related_index].relation = MONO_EQ_RELATION;
1449 area.relations [related_index].relation_is_static_definition = TRUE;
1450 area.relations [related_index].related_value.type = MONO_VARIABLE_SUMMARIZED_VALUE;
1451 area.relations [related_index].related_value.value.variable.variable = i;
1452 area.relations [related_index].related_value.value.variable.delta = - area.relations [i].related_value.value.variable.delta;
1454 area.relations [related_index].next = area.relations [related_variable].next;
1455 area.relations [related_variable].next = &(area.relations [related_index]);
1457 if (TRACE_ABC_REMOVAL) {
1458 printf ("Added symmetric summarized value for variable variable %d (to %d): ", i, related_variable);
1459 print_summarized_value (&(area.relations [related_index].related_value));
1465 process_block (cfg->bblocks [0], &area);
1468 #endif /* DISABLE_SSA */
1470 #endif /* DISABLE_JIT */