/* * abcremoval.c: Array bounds check removal * * Author: * Massimiliano Mantione (massi@ximian.com) * * (C) 2004 Ximian, Inc. http://www.ximian.com */ #include #include #include #include #include #include #include #ifndef DISABLE_JIT #include "abcremoval.h" #if SIZEOF_VOID_P == 8 #define OP_PCONST OP_I8CONST #else #define OP_PCONST OP_ICONST #endif #define TRACE_ABC_REMOVAL (verbose_level > 2) #define REPORT_ABC_REMOVAL (verbose_level > 1) /* * A little hack for the verbosity level. * The verbosity level is stored in the cfg, but not all functions that must * print something see the cfg, so we store the verbosity level here at the * beginning of the algorithm. * This is not thread safe (does not handle correctly different verbosity * levels in different threads), and is not exact in case of dynamic changes * of the verbosity level... * Anyway, this is not needed, all that can happen is that something more * (or less) is logged, the result is in any case correct. */ static int verbose_level; #define RELATION_BETWEEN_VALUES(value,related_value) (\ ((value) > (related_value))? MONO_GT_RELATION :\ (((value) < (related_value))? MONO_LT_RELATION : MONO_EQ_RELATION)) #define MAKE_VALUE_ANY(v) do{\ (v).type = MONO_ANY_SUMMARIZED_VALUE;\ } while (0) #define MAKE_VALUE_RELATION_ANY(r) do{\ (r)->relation = MONO_ANY_RELATION;\ MAKE_VALUE_ANY((r)->related_value);\ } while (0) #define INITIALIZE_VALUE_RELATION(r) do{\ MAKE_VALUE_RELATION_ANY((r));\ (r)->next = NULL;\ } while (0) #define MONO_NEGATED_RELATION(r) ((~(r))&MONO_ANY_RELATION) #define MONO_SYMMETRIC_RELATION(r) (((r)&MONO_EQ_RELATION)|(((r)&MONO_LT_RELATION)<<1)|((r&MONO_GT_RELATION)>>1)) static void print_relation (int relation) { int print_or = 0; printf ("("); if (relation & MONO_LT_RELATION) { printf ("LT"); print_or = 1; } if (relation & MONO_EQ_RELATION) { if (print_or) { printf ("|"); } printf ("EQ"); print_or = 1; } if (relation & MONO_GT_RELATION) { if (print_or) { printf ("|"); } printf ("GT"); print_or = 1; } printf (")"); } static void print_summarized_value (MonoSummarizedValue *value) { switch (value->type) { case MONO_ANY_SUMMARIZED_VALUE: printf ("ANY"); break; case MONO_CONSTANT_SUMMARIZED_VALUE: printf ("CONSTANT %d", value->value.constant.value); break; case MONO_VARIABLE_SUMMARIZED_VALUE: printf ("VARIABLE %d, delta %d", value->value.variable.variable, value->value.variable.delta); break; case MONO_PHI_SUMMARIZED_VALUE: { int phi; printf ("PHI ("); for (phi = 0; phi < value->value.phi.number_of_alternatives; phi++) { if (phi) printf (","); printf ("%d", value->value.phi.phi_alternatives [phi]); } printf (")"); break; } default: g_assert_not_reached (); } } static void print_summarized_value_relation (MonoSummarizedValueRelation *relation) { printf ("Relation "); print_relation (relation->relation); printf (" with value "); print_summarized_value (&(relation->related_value)); } #if 0 static void print_summarized_value_relation_chain (MonoSummarizedValueRelation *relation) { printf ("Relations:\n"); while (relation) { print_summarized_value_relation (relation); printf ("\n"); relation = relation->next; } } #endif static void print_evaluation_context_status (MonoRelationsEvaluationStatus status) { if (status == MONO_RELATIONS_EVALUATION_NOT_STARTED) { printf ("EVALUATION_NOT_STARTED"); } else { gboolean print_or = FALSE; printf ("("); if (status & MONO_RELATIONS_EVALUATION_IN_PROGRESS) { if (print_or) printf ("|"); printf ("EVALUATION_IN_PROGRESS"); print_or = TRUE; } if (status & MONO_RELATIONS_EVALUATION_COMPLETED) { if (print_or) printf ("|"); printf ("EVALUATION_COMPLETED"); print_or = TRUE; } if (status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING) { if (print_or) printf ("|"); printf ("RECURSIVELY_ASCENDING"); print_or = TRUE; } if (status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING) { if (print_or) printf ("|"); printf ("RECURSIVELY_DESCENDING"); print_or = TRUE; } if (status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE) { if (print_or) printf ("|"); printf ("RECURSIVELY_INDEFINITE"); print_or = TRUE; } printf (")"); } } static void print_evaluation_context_ranges (MonoRelationsEvaluationRanges *ranges) { printf ("(ranges: zero [%d,%d], variable [%d,%d])", ranges->zero.lower, ranges->zero.upper, ranges->variable.lower, ranges->variable.upper); } static void print_evaluation_context (MonoRelationsEvaluationContext *context) { printf ("Context status: "); print_evaluation_context_status (context->status); if (context->status & (MONO_RELATIONS_EVALUATION_IN_PROGRESS|MONO_RELATIONS_EVALUATION_COMPLETED)) { print_evaluation_context_ranges (&(context->ranges)); } printf ("\n"); } #if 0 static void print_evaluation_area (MonoVariableRelationsEvaluationArea *area) { int i; printf ("Dump of evaluation area (%d variables):\n", area->cfg->num_varinfo); for (i = 0; i < area->cfg->num_varinfo; i++) { printf ("Variable %d: ", i); print_evaluation_context (&(area->contexts [i])); print_summarized_value_relation_chain (&(area->relations [i])); } } static void print_evaluation_area_contexts (MonoVariableRelationsEvaluationArea *area) { int i; printf ("Dump of evaluation area contexts (%d variables):\n", area->cfg->num_varinfo); for (i = 0; i < area->cfg->num_varinfo; i++) { printf ("Variable %d: ", i); print_evaluation_context (&(area->contexts [i])); } } #endif /* * Check if the delta of an integer variable value is safe with respect * to the variable size in bytes and its kind (signed or unsigned). * If the delta is not safe, make the value an "any". */ static G_GNUC_UNUSED void check_delta_safety (MonoVariableRelationsEvaluationArea *area, MonoSummarizedValue *value) { if (value->type == MONO_VARIABLE_SUMMARIZED_VALUE) { int variable = value->value.variable.variable; int delta = value->value.variable.delta; if ((area->variable_value_kind [variable]) & MONO_UNSIGNED_VALUE_FLAG) { if (delta < 0) { MAKE_VALUE_ANY (*value); } } else { if (((area->variable_value_kind [variable]) & MONO_INTEGER_VALUE_SIZE_BITMASK) < 4) { MAKE_VALUE_ANY (*value); } else if (delta > 16) { MAKE_VALUE_ANY (*value); } } } } /* * get_relation_from_ins: * * Obtain relations from a MonoInst. * * result_value_kind: the "expected" kind of result; * result: the "summarized" value * returns the "actual" kind of result, if guessable (otherwise MONO_UNKNOWN_INTEGER_VALUE) */ static MonoIntegerValueKind get_relation_from_ins (MonoVariableRelationsEvaluationArea *area, MonoInst *ins, MonoSummarizedValueRelation *result, MonoIntegerValueKind result_value_kind) { MonoIntegerValueKind value_kind; MonoSummarizedValue *value = &result->related_value; if (ins->type == STACK_I8) { value_kind = MONO_INTEGER_VALUE_SIZE_8; } else if (ins->type == STACK_I4) { value_kind = MONO_INTEGER_VALUE_SIZE_4; } else { value_kind = MONO_UNKNOWN_INTEGER_VALUE; } result->relation = MONO_EQ_RELATION; MAKE_VALUE_ANY (*value); switch (ins->opcode) { case OP_ICONST: value->type = MONO_CONSTANT_SUMMARIZED_VALUE; value->value.constant.value = ins->inst_c0; break; case OP_MOVE: value->type = MONO_VARIABLE_SUMMARIZED_VALUE; value->value.variable.variable = ins->sreg1; value->value.variable.delta = 0; break; case OP_SEXT_I4: value->type = MONO_VARIABLE_SUMMARIZED_VALUE; value->value.variable.variable = ins->sreg1; value->value.variable.delta = 0; value_kind = MONO_INTEGER_VALUE_SIZE_8; break; case OP_PHI: value->type = MONO_PHI_SUMMARIZED_VALUE; value->value.phi.number_of_alternatives = *(ins->inst_phi_args); value->value.phi.phi_alternatives = ins->inst_phi_args + 1; break; case OP_IADD_IMM: value->type = MONO_VARIABLE_SUMMARIZED_VALUE; value->value.variable.variable = ins->sreg1; value->value.variable.delta = ins->inst_imm; /* FIXME: */ //check_delta_safety (area, result); break; case OP_ISUB_IMM: value->type = MONO_VARIABLE_SUMMARIZED_VALUE; value->value.variable.variable = ins->sreg1; value->value.variable.delta = -ins->inst_imm; /* FIXME: */ //check_delta_safety (area, result); break; case OP_IREM_UN: /* The result of an unsigned remainder is 0 < x < the divisor */ result->relation = MONO_LT_RELATION; value->type = MONO_VARIABLE_SUMMARIZED_VALUE; value->value.variable.variable = ins->sreg2; value->value.variable.delta = 0; value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_4; break; case OP_LDLEN: /* * We represent arrays by their length, so r1<-ldlen r2 is stored * as r1 == r2 in the evaluation graph. */ value->type = MONO_VARIABLE_SUMMARIZED_VALUE; value->value.variable.variable = ins->sreg1; value->value.variable.delta = 0; value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_4; break; case OP_NEWARR: value->type = MONO_VARIABLE_SUMMARIZED_VALUE; value->value.variable.variable = ins->sreg1; value->value.variable.delta = 0; area->defs [ins->dreg] = ins; break; case OP_LDADDR: /* The result is non-null */ result->relation = MONO_GT_RELATION; value->type = MONO_CONSTANT_SUMMARIZED_VALUE; value->value.constant.value = 0; break; /* FIXME: Add more opcodes */ default: /* These opcodes are not currently handled while running SciMark, first * column is the number of times the warning was shown: * * 1 add_imm * 1 float_conv_to_i8 * 1 int_mul_ovf_un * 1 int_neg * 1 int_or * 1 int_shr_un * 1 localloc * 1 long_ceq * 1 long_rem * 1 long_sub * 2 int_ceq * 2 int_conv_to_i2 * 2 int_min * 2 lcall * 2 long_div * 3 int_conv_to_u2 * 3 long_shr_imm * 4 int_rem * 4 int_rem_imm * 4 loadi1_membase * 4 loadu4_membase * 5 int_div * 5 shl_imm * 6 int_div_imm * 6 int_mul * 9 int_mul_imm * 9 zext_i4 * 10 int_shr_imm * 12 int_shr_un_imm * 12 long_add_imm * 12 outarg_vtretaddr * 12 strlen * 13 int_or_imm * 23 call_membase * 23 int_conv_to_u1 * 23 long_add * 24 int_and_imm * 24 int_shl_imm * 24 loadu2_membase * 29 loadi8_membase * 31 llvm_outarg_vt * 34 int_sub * 34 loadu1_membase * 42 int_add * 85 ldaddr * 116 loadi4_membase * 159 x86_lea * 179 sext_i4 * 291 load_membase * 462 i8const * 472 call */ break; } return value_kind; } static MonoValueRelation get_relation_from_branch_instruction (MonoInst *ins) { if (MONO_IS_COND_BRANCH_OP (ins)) { CompRelation rel = mono_opcode_to_cond (ins->opcode); switch (rel) { case CMP_EQ: return MONO_EQ_RELATION; case CMP_NE: return MONO_NE_RELATION; case CMP_LE: case CMP_LE_UN: return MONO_LE_RELATION; case CMP_GE: case CMP_GE_UN: return MONO_GE_RELATION; case CMP_LT: case CMP_LT_UN: return MONO_LT_RELATION; case CMP_GT: case CMP_GT_UN: return MONO_GT_RELATION; default: g_assert_not_reached (); return MONO_ANY_RELATION; } } else { return MONO_ANY_RELATION; } } /* * Given a BB, find its entry condition and put its relations in a * "MonoAdditionalVariableRelationsForBB" structure. * bb: the BB * relations: the resulting relations (entry condition of the given BB) */ static void get_relations_from_previous_bb (MonoVariableRelationsEvaluationArea *area, MonoBasicBlock *bb, MonoAdditionalVariableRelationsForBB *relations) { MonoBasicBlock *in_bb; MonoInst *ins, *compare, *branch; MonoValueRelation branch_relation; MonoValueRelation symmetric_relation; gboolean code_path; INITIALIZE_VALUE_RELATION (&(relations->relation1.relation)); relations->relation1.relation.relation_is_static_definition = FALSE; relations->relation1.relation.next = NULL; relations->relation1.insertion_point = NULL; relations->relation1.variable = -1; INITIALIZE_VALUE_RELATION (&(relations->relation2.relation)); relations->relation2.relation.relation_is_static_definition = FALSE; relations->relation2.relation.next = NULL; relations->relation2.insertion_point = NULL; relations->relation2.variable = -1; if (bb->in_count == 1) { /* Should write the code to "sum" conditions... */ in_bb = bb->in_bb [0]; if ((in_bb->last_ins == NULL) || (in_bb->code == in_bb->last_ins)) return; for (ins = in_bb->code; ins->next != in_bb->last_ins; ins = ins->next) ; compare = ins; branch = ins->next; branch_relation = get_relation_from_branch_instruction (branch); if (branch_relation != MONO_ANY_RELATION) { if (branch->inst_true_bb == bb) { code_path = TRUE; } else if (branch->inst_false_bb == bb) { code_path = FALSE; } else { code_path = TRUE; g_assert_not_reached (); } if (!code_path) branch_relation = MONO_NEGATED_RELATION (branch_relation); symmetric_relation = MONO_SYMMETRIC_RELATION (branch_relation); /* FIXME: Other compare opcodes */ if (compare->opcode == OP_ICOMPARE) { relations->relation1.variable = compare->sreg1; relations->relation1.relation.relation = branch_relation; relations->relation1.relation.related_value.type = MONO_VARIABLE_SUMMARIZED_VALUE; relations->relation1.relation.related_value.value.variable.variable = compare->sreg2; relations->relation1.relation.related_value.value.variable.delta = 0; relations->relation2.variable = compare->sreg2; relations->relation2.relation.relation = symmetric_relation; relations->relation2.relation.related_value.type = MONO_VARIABLE_SUMMARIZED_VALUE; relations->relation2.relation.related_value.value.variable.variable = compare->sreg1; relations->relation2.relation.related_value.value.variable.delta = 0; } else if (compare->opcode == OP_ICOMPARE_IMM) { relations->relation1.variable = compare->sreg1; relations->relation1.relation.relation = branch_relation; relations->relation1.relation.related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE; relations->relation1.relation.related_value.value.constant.value = compare->inst_imm; } } } } /* * Add the given relations to the evaluation area. * area: the evaluation area * change: the relations that must be added */ static void apply_change_to_evaluation_area (MonoVariableRelationsEvaluationArea *area, MonoAdditionalVariableRelation *change) { MonoSummarizedValueRelation *base_relation; if (change->relation.relation != MONO_ANY_RELATION) { base_relation = &(area->relations [change->variable]); while ((base_relation->next != NULL) && (base_relation->next->relation_is_static_definition)) { base_relation = base_relation->next; } change->insertion_point = base_relation; change->relation.next = base_relation->next; base_relation->next = &(change->relation); } } /* * Remove the given relation from the evaluation area. * change: the relation that must be removed */ static void remove_change_from_evaluation_area (MonoAdditionalVariableRelation *change) { if (change->insertion_point != NULL) { change->insertion_point->next = change->relation.next; change->relation.next = NULL; } } static void clean_contexts (MonoRelationsEvaluationContext *contexts, int number) { int i; for (i = 0; i < number; i++) { contexts [i].status = MONO_RELATIONS_EVALUATION_NOT_STARTED; } } /* * Perform the intersection of a range and a constant value (taking into * account the relation that the value has with the range). * range: the range that will be intersected with the value * value: the value that will be intersected with the range * relation: the relation between the range and the value */ static void intersect_value( MonoRelationsEvaluationRange *range, int value, MonoValueRelation relation ) { switch (relation) { case MONO_NO_RELATION: MONO_MAKE_RELATIONS_EVALUATION_RANGE_IMPOSSIBLE (*range); break; case MONO_ANY_RELATION: break; case MONO_EQ_RELATION: MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, value); MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, value); break; case MONO_NE_RELATION: { /* IMPROVEMENT Figure this out! (ignoring it is safe anyway) */ break; } case MONO_LT_RELATION: MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (value)); break; case MONO_LE_RELATION: MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, value); break; case MONO_GT_RELATION: MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (value)); break; case MONO_GE_RELATION: MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, value); break; default: g_assert_not_reached(); } } /* * Perform the intersection of two pairs of ranges (taking into account the * relation between the ranges and a given delta). * ranges: the ranges that will be intersected * other_ranges the other ranges that will be intersected * delta: the delta between the pairs of ranges * relation: the relation between the pairs of ranges */ static void intersect_ranges( MonoRelationsEvaluationRanges *ranges, MonoRelationsEvaluationRanges *other_ranges, int delta, MonoValueRelation relation ) { if (delta == 0) { switch (relation) { case MONO_NO_RELATION: MONO_MAKE_RELATIONS_EVALUATION_RANGES_IMPOSSIBLE (*ranges); break; case MONO_ANY_RELATION: break; case MONO_EQ_RELATION: MONO_RELATIONS_EVALUATION_RANGES_INTERSECTION (*ranges, *other_ranges); break; case MONO_NE_RELATION: { /* FIXME Figure this out! (ignoring it is safe anyway) */ break; } case MONO_LT_RELATION: MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->zero.upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->zero.upper)); MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->variable.upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->variable.upper)); break; case MONO_LE_RELATION: MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->zero.upper, other_ranges->zero.upper); MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->variable.upper, other_ranges->variable.upper); break; case MONO_GT_RELATION: MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->zero.lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->zero.lower)); MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->variable.lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->variable.lower)); break; case MONO_GE_RELATION: MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->zero.lower, other_ranges->zero.lower); MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->variable.lower, other_ranges->variable.lower); break; default: g_assert_not_reached(); } } else { MonoRelationsEvaluationRanges translated_ranges = *other_ranges; MONO_ADD_DELTA_SAFELY_TO_RANGES (translated_ranges, delta); intersect_ranges( ranges, &translated_ranges, FALSE, relation ); } } /* * Recursive method that traverses the relation graph to evaluate the * relation between two variables. * At the end of the execution, the resulting ranges are in the context of * the "starting" variable. * area: the current evaluation area (it contains the relation graph and * memory for all the evaluation contexts is already allocated) * variable: starting variable (the value ranges in its context are the result * of the execution of this procedure) * target_variable: the variable with respect to which the starting variable * is evaluated (tipically the starting variable is the index * and the target one is the array (which means its length)) * father_context: the previous evaluation context in recursive invocations * (or NULL for the first invocation) */ static void evaluate_relation_with_target_variable (MonoVariableRelationsEvaluationArea *area, int variable, int target_variable, MonoRelationsEvaluationContext *father_context) { MonoRelationsEvaluationContext *context = &(area->contexts [variable]); // First of all, we check the evaluation status // (what must be done is *very* different in each case) switch (context->status) { case MONO_RELATIONS_EVALUATION_NOT_STARTED: { MonoSummarizedValueRelation *relation = &(area->relations [variable]); if (TRACE_ABC_REMOVAL) { printf ("Evaluating variable %d (target variable %d)\n", variable, target_variable); print_summarized_value_relation (relation); printf ("\n"); } // We properly inizialize the context context->status = MONO_RELATIONS_EVALUATION_IN_PROGRESS; context->father = father_context; MONO_MAKE_RELATIONS_EVALUATION_RANGES_WEAK (context->ranges); // If we have found the target variable, we can set the range // related to it in the context to "equal" (which is [0,0]) if (variable == target_variable) { if (TRACE_ABC_REMOVAL) { printf ("Target variable reached (%d), continuing to evaluate relations with constants\n", variable); } context->ranges.variable.lower = 0; context->ranges.variable.upper = 0; } // Examine all relations for this variable (scan the list) // The contribute of each relation will be intersected (logical and) while (relation != NULL) { context->current_relation = relation; if (TRACE_ABC_REMOVAL) { printf ("Processing (%d): ", variable); print_summarized_value_relation (relation); printf ("\n"); } // We decie what to do according the the type of the related value switch (relation->related_value.type) { case MONO_ANY_SUMMARIZED_VALUE: // No added information, skip it break; case MONO_CONSTANT_SUMMARIZED_VALUE: // Intersect range with constant (taking into account the relation) intersect_value (&(context->ranges.zero), relation->related_value.value.constant.value, relation->relation); break; case MONO_VARIABLE_SUMMARIZED_VALUE: // Generally, evaluate related variable and intersect ranges. // However, some check is necessary... // If the relation is "ANY", nothing to do (no added information) if (relation->relation != MONO_ANY_RELATION) { int related_variable = relation->related_value.value.variable.variable; MonoRelationsEvaluationContext *related_context = &(area->contexts [related_variable]); // The second condition in the "or" avoids messing with "back edges" in the graph traversal // (they are simply ignored instead of triggering the handling of recursion) if ( (related_context->status == MONO_RELATIONS_EVALUATION_NOT_STARTED) || ! ((related_context->current_relation->related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) && (related_context->current_relation->related_value.value.variable.variable == variable))) { // Evaluate the related variable evaluate_relation_with_target_variable (area, related_variable, target_variable, context); // Check if we are part of a recursive loop if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) { if (TRACE_ABC_REMOVAL) { printf ("Recursivity detected for variable %d (target variable %d), status ", variable, target_variable); print_evaluation_context_status (context->status); } // If we are, check if the evaluation of the related variable is complete if (related_context->status == MONO_RELATIONS_EVALUATION_COMPLETED) { // If it is complete, we are part of a recursive definition. // Since it is a *definition* (and definitions are evaluated *before* // conditions because they are first in the list), intersection is not // strictly necessary, we simply copy the ranges and apply the delta context->ranges = related_context->ranges; /* Delta has already been checked for over/under-flow when evaluating values */ MONO_ADD_DELTA_SAFELY_TO_RANGES (context->ranges, relation->related_value.value.variable.delta); context->status = MONO_RELATIONS_EVALUATION_COMPLETED; if (TRACE_ABC_REMOVAL) { printf (", ranges already computed, result: \n"); print_evaluation_context_ranges (&(context->ranges)); printf (" (delta is %d)\n", relation->related_value.value.variable.delta); } } else { // If it is not complete, do nothing (we do not have enough information) if (TRACE_ABC_REMOVAL) { printf (", ranges not computed\n"); } } } else { // If we are not (the common case) intersect the result intersect_ranges( &(context->ranges), &(related_context->ranges), relation->related_value.value.variable.delta, relation->relation ); } } else { if (TRACE_ABC_REMOVAL) { printf ("Relation is a back-edge in this traversal, skipping\n"); } } } break; case MONO_PHI_SUMMARIZED_VALUE: { // We must compute all PHI alternatives, combining the results (with a union, which is a logical "or"), // and intersect this result with the ranges in the context; we must also take into account recursions // (with loops that can be ascending, descending, or indefinite) MonoRelationsEvaluationRanges phi_ranges; int phi; gboolean is_ascending = FALSE; gboolean is_descending = FALSE; MONO_MAKE_RELATIONS_EVALUATION_RANGES_IMPOSSIBLE (phi_ranges); for (phi = 0; phi < relation->related_value.value.phi.number_of_alternatives; phi++) { int phi_alternative = relation->related_value.value.phi.phi_alternatives [phi]; evaluate_relation_with_target_variable (area, phi_alternative, target_variable, context); // This means we are part of a recursive loop if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) { if (TRACE_ABC_REMOVAL) { printf ("Recursivity detected for variable %d (target variable %d), status ", variable, target_variable); print_evaluation_context_status (context->status); printf ("\n"); } if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING) { is_ascending = TRUE; } if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING) { is_descending = TRUE; } if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE) { is_ascending = TRUE; is_descending = TRUE; } // Clear "recursivity" bits in the status (recursion has been handled) context->status = MONO_RELATIONS_EVALUATION_IN_PROGRESS; } else { MONO_RELATIONS_EVALUATION_RANGES_UNION (phi_ranges, area->contexts [phi_alternative].ranges); } } // Apply the effects of all recursive loops if (is_ascending) { phi_ranges.zero.upper = INT_MAX; phi_ranges.variable.upper = INT_MAX; } if (is_descending) { phi_ranges.zero.lower = INT_MIN; phi_ranges.variable.lower = INT_MIN; } // Intersect final result MONO_RELATIONS_EVALUATION_RANGES_INTERSECTION (context->ranges, phi_ranges); break; } default: g_assert_not_reached(); } // Pass to next relation relation = relation->next; } // Check if any recursivity bits are still in the status, and in any case clear them if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) { if (TRACE_ABC_REMOVAL) { printf ("Recursivity for variable %d (target variable %d) discards computation, status ", variable, target_variable); print_evaluation_context_status (context->status); printf ("\n"); } // If yes, we did not have enough information (most likely we were evaluated inside a PHI, but we also // depended on the same PHI, which was still in evaluation...), so clear the status to "NOT_STARTED" // (if we will be evaluated again, the PHI will be already done, so our evaluation will succeed) context->status = MONO_RELATIONS_EVALUATION_NOT_STARTED; } else { if (TRACE_ABC_REMOVAL) { printf ("Ranges for variable %d (target variable %d) computed: ", variable, target_variable); print_evaluation_context_ranges (&(context->ranges)); printf ("\n"); } // If not (the common case) the evaluation is complete, and the result is in the context context->status = MONO_RELATIONS_EVALUATION_COMPLETED; } break; } case MONO_RELATIONS_EVALUATION_IN_PROGRESS: { // This means we are in a recursive loop MonoRelationsEvaluationContext *current_context = father_context; MonoRelationsEvaluationContext *last_context = context->father; gboolean evaluation_can_be_recursive = TRUE; gboolean evaluation_is_definition = TRUE; int path_value = 0; if (TRACE_ABC_REMOVAL) { printf ("Evaluation of variable %d (target variable %d) already in progress\n", variable, target_variable); print_evaluation_context (context); print_summarized_value_relation (context->current_relation); printf ("\n"); } // We must check if the loop can be a recursive definition (we scan the whole loop) while (current_context != last_context) { if (current_context == NULL) { printf ("Broken recursive ring in ABC removal\n"); g_assert_not_reached (); } if (current_context->current_relation->relation_is_static_definition) { if (current_context->current_relation->related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) { /* No need to check path_value for over/under-flow, since delta should be safe */ path_value += current_context->current_relation->related_value.value.variable.delta; } else if (current_context->current_relation->related_value.type != MONO_PHI_SUMMARIZED_VALUE) { evaluation_can_be_recursive = FALSE; } } else { evaluation_is_definition = FALSE; evaluation_can_be_recursive = FALSE; } current_context = current_context->father; } // If this is a recursive definition, we properly flag the status in all the involved contexts if (evaluation_is_definition) { MonoRelationsEvaluationStatus recursive_status; if (evaluation_can_be_recursive) { if (path_value > 0) { recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING; } else if (path_value < 0) { recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING; } else { recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE; } } else { recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE; } if (TRACE_ABC_REMOVAL) { printf ("Recursivity accepted ("); print_evaluation_context_status (recursive_status); printf (")\n"); } current_context = father_context; while (current_context != last_context) { current_context->status |= recursive_status; current_context = current_context->father; } } else { if (TRACE_ABC_REMOVAL) { printf ("Recursivity rejected (some relation in the cycle is not a defintion)\n"); } } break; } case MONO_RELATIONS_EVALUATION_COMPLETED: { return; } default: if (TRACE_ABC_REMOVAL) { printf ("Variable %d (target variable %d) already in a recursive ring, skipping\n", variable, target_variable); print_evaluation_context (context); print_summarized_value_relation (context->current_relation); printf ("\n"); } break; } } /* * Apply the given value kind to the given range */ static void apply_value_kind_to_range (MonoRelationsEvaluationRange *range, MonoIntegerValueKind value_kind) { if (value_kind != MONO_UNKNOWN_INTEGER_VALUE) { if (value_kind & MONO_UNSIGNED_VALUE_FLAG) { if (range->lower < 0) { range->lower = 0; } if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 1) { if (range->upper > 0xff) { range->upper = 0xff; } } else if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 2) { if (range->upper > 0xffff) { range->upper = 0xffff; } } } else { if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 1) { if (range->lower < -0x80) { range->lower = -0x80; } if (range->upper > 0x7f) { range->upper = 0x7f; } } else if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 2) { if (range->lower < -0x8000) { range->lower = -0x8000; } if (range->upper > 0x7fff) { range->upper = 0x7fff; } } } } } /* * Attempt the removal of bounds checks from a MonoInst. * inst: the MonoInst * area: the current evaluation area (it contains the relation graph and * memory for all the evaluation contexts is already allocated) */ static void remove_abc_from_inst (MonoInst *ins, MonoVariableRelationsEvaluationArea *area) { /* FIXME: Add support for 'constant' arrays and constant indexes */ int array_variable = ins->sreg1; int index_variable = ins->sreg2; MonoRelationsEvaluationContext *array_context = &(area->contexts [array_variable]); MonoRelationsEvaluationContext *index_context = &(area->contexts [index_variable]); clean_contexts (area->contexts, area->cfg->next_vreg); evaluate_relation_with_target_variable (area, index_variable, array_variable, NULL); evaluate_relation_with_target_variable (area, array_variable, array_variable, NULL); if ((index_context->ranges.zero.lower >=0) && ((index_context->ranges.variable.upper < 0)||(index_context->ranges.zero.upper < array_context->ranges.zero.lower))) { if (REPORT_ABC_REMOVAL) { printf ("ARRAY-ACCESS: removed bounds check on array %d with index %d\n", array_variable, index_variable); } NULLIFY_INS (ins); } else { if (TRACE_ABC_REMOVAL) { if (index_context->ranges.zero.lower >= 0) { printf ("ARRAY-ACCESS: Removed lower bound check on array %d with index %d\n", array_variable, index_variable); } if (index_context->ranges.variable.upper < 0) { printf ("ARRAY-ACCESS: Removed upper bound check (through variable) on array %d with index %d\n", array_variable, index_variable); } if (index_context->ranges.zero.upper < array_context->ranges.zero.lower) { printf ("ARRAY-ACCESS: Removed upper bound check (through constant) on array %d with index %d\n", array_variable, index_variable); } } } } static gboolean eval_non_null (MonoVariableRelationsEvaluationArea *area, int reg) { MonoRelationsEvaluationContext *context = &(area->contexts [reg]); clean_contexts (area->contexts, area->cfg->next_vreg); evaluate_relation_with_target_variable (area, reg, reg, NULL); return context->ranges.zero.lower > 0; } static void add_non_null (MonoVariableRelationsEvaluationArea *area, MonoCompile *cfg, int reg, GSList **check_relations) { MonoAdditionalVariableRelation *rel; rel = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoAdditionalVariableRelation)); rel->variable = reg; rel->relation.relation = MONO_GT_RELATION; rel->relation.related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE; rel->relation.related_value.value.constant.value = 0; apply_change_to_evaluation_area (area, rel); *check_relations = g_slist_append_mempool (cfg->mempool, *check_relations, rel); } /* * Process a BB removing bounds checks from array accesses. * It does the following (in sequence): * - Get the BB entry condition * - Add its relations to the relation graph in the evaluation area * - Process all the MonoInst trees in the BB * - Recursively process all the children BBs in the dominator tree * - Remove the relations previously added to the relation graph * * bb: the BB that must be processed * area: the current evaluation area (it contains the relation graph and * memory for all the evaluation contexts is already allocated) */ static void process_block (MonoCompile *cfg, MonoBasicBlock *bb, MonoVariableRelationsEvaluationArea *area) { int inst_index; MonoInst *ins; MonoAdditionalVariableRelationsForBB additional_relations; GSList *dominated_bb, *l; GSList *check_relations = NULL; if (TRACE_ABC_REMOVAL) { printf ("\nProcessing block %d [dfn %d]...\n", bb->block_num, bb->dfn); } if (bb->region != -1) return; get_relations_from_previous_bb (area, bb, &additional_relations); if (TRACE_ABC_REMOVAL) { if (additional_relations.relation1.relation.relation != MONO_ANY_RELATION) { printf ("Adding relation 1 on variable %d: ", additional_relations.relation1.variable); print_summarized_value_relation (&(additional_relations.relation1.relation)); printf ("\n"); } if (additional_relations.relation2.relation.relation != MONO_ANY_RELATION) { printf ("Adding relation 2 on variable %d: ", additional_relations.relation2.variable); print_summarized_value_relation (&(additional_relations.relation2.relation)); printf ("\n"); } } apply_change_to_evaluation_area (area, &(additional_relations.relation1)); apply_change_to_evaluation_area (area, &(additional_relations.relation2)); inst_index = 0; for (ins = bb->code; ins; ins = ins->next) { MonoAdditionalVariableRelation *rel; int array_var, index_var; if (TRACE_ABC_REMOVAL) { printf ("Processing instruction %d\n", inst_index); inst_index++; } if (ins->opcode == OP_BOUNDS_CHECK) { /* Handle OP_LDELEMA2D, too */ if (TRACE_ABC_REMOVAL) { printf ("Attempting check removal...\n"); } array_var = ins->sreg1; index_var = ins->sreg2; remove_abc_from_inst (ins, area); /* We can derive additional relations from the bounds check */ if (ins->opcode != OP_NOP) { rel = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoAdditionalVariableRelation)); rel->variable = index_var; rel->relation.relation = MONO_LT_RELATION; rel->relation.related_value.type = MONO_VARIABLE_SUMMARIZED_VALUE; rel->relation.related_value.value.variable.variable = array_var; rel->relation.related_value.value.variable.delta = 0; apply_change_to_evaluation_area (area, rel); check_relations = g_slist_append_mempool (cfg->mempool, check_relations, rel); rel = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoAdditionalVariableRelation)); rel->variable = index_var; rel->relation.relation = MONO_GE_RELATION; rel->relation.related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE; rel->relation.related_value.value.constant.value = 0; apply_change_to_evaluation_area (area, rel); check_relations = g_slist_append_mempool (cfg->mempool, check_relations, rel); } } if (ins->opcode == OP_CHECK_THIS) { if (eval_non_null (area, ins->sreg1)) { if (REPORT_ABC_REMOVAL) printf ("ARRAY-ACCESS: removed check_this instruction.\n"); NULLIFY_INS (ins); } } if (ins->opcode == OP_NOT_NULL) add_non_null (area, cfg, ins->sreg1, &check_relations); /* * FIXME: abcrem equates an array with its length, * so a = new int [100] implies a != null, but a = new int [0] doesn't. */ /* * Eliminate MONO_INST_FAULT flags if possible. */ if (COMPILE_LLVM (cfg) && (ins->opcode == OP_LDLEN || ins->opcode == OP_BOUNDS_CHECK || ins->opcode == OP_STRLEN || (MONO_IS_LOAD_MEMBASE (ins) && (ins->flags & MONO_INST_FAULT)) || (MONO_IS_STORE_MEMBASE (ins) && (ins->flags & MONO_INST_FAULT)))) { int reg; if (MONO_IS_STORE_MEMBASE (ins)) reg = ins->inst_destbasereg; else if (MONO_IS_LOAD_MEMBASE (ins)) reg = ins->inst_basereg; else reg = ins->sreg1; /* * This doesn't work because LLVM can move the non-faulting loads before the faulting * ones (test_0_llvm_moving_faulting_loads ()). * So only do it if we know the load cannot be moved before the instruction which ensures it is not * null (i.e. the def of its sreg). */ if (area->defs [reg] && area->defs [reg]->opcode == OP_NEWARR) { if (REPORT_ABC_REMOVAL) printf ("ARRAY-ACCESS: removed MONO_INST_FAULT flag.\n"); ins->flags &= ~MONO_INST_FAULT; } /* if (eval_non_null (area, reg)) { if (REPORT_ABC_REMOVAL) printf ("ARRAY-ACCESS: removed MONO_INST_FAULT flag.\n"); ins->flags &= ~MONO_INST_FAULT; } else { add_non_null (area, cfg, reg, &check_relations); } */ } } if (TRACE_ABC_REMOVAL) { printf ("Processing block %d [dfn %d] done.\n", bb->block_num, bb->dfn); } for (dominated_bb = bb->dominated; dominated_bb != NULL; dominated_bb = dominated_bb->next) { process_block (cfg, (MonoBasicBlock*) (dominated_bb->data), area); } for (l = check_relations; l; l = l->next) remove_change_from_evaluation_area (l->data); remove_change_from_evaluation_area (&(additional_relations.relation1)); remove_change_from_evaluation_area (&(additional_relations.relation2)); } static MonoIntegerValueKind type_to_value_kind (MonoType *type) { if (type->byref) return MONO_UNKNOWN_INTEGER_VALUE; switch (type->type) { case MONO_TYPE_I1: return MONO_INTEGER_VALUE_SIZE_1; break; case MONO_TYPE_U1: return MONO_UNSIGNED_INTEGER_VALUE_SIZE_1; break; case MONO_TYPE_I2: return MONO_INTEGER_VALUE_SIZE_2; break; case MONO_TYPE_U2: return MONO_UNSIGNED_INTEGER_VALUE_SIZE_2; break; case MONO_TYPE_I4: return MONO_INTEGER_VALUE_SIZE_4; break; case MONO_TYPE_U4: return MONO_UNSIGNED_INTEGER_VALUE_SIZE_4; break; case MONO_TYPE_I: return SIZEOF_VOID_P; break; case MONO_TYPE_U: return (MONO_UNSIGNED_VALUE_FLAG|SIZEOF_VOID_P); break; case MONO_TYPE_I8: return MONO_INTEGER_VALUE_SIZE_8; break; case MONO_TYPE_U8: return MONO_UNSIGNED_INTEGER_VALUE_SIZE_8; default: return MONO_UNKNOWN_INTEGER_VALUE; } } /** * mono_perform_abc_removal: * @cfg: Control Flow Graph * * Performs the ABC removal from a cfg in SSA form. * It does the following: * - Prepare the evaluation area * - Allocate memory for the relation graph in the evaluation area * (of course, only for variable definitions) and summarize there all * variable definitions * - Allocate memory for the evaluation contexts in the evaluation area * - Recursively process all the BBs in the dominator tree (it is enough * to invoke the processing on the entry BB) * * cfg: the method code */ void mono_perform_abc_removal (MonoCompile *cfg) { MonoVariableRelationsEvaluationArea area; MonoBasicBlock *bb; int i; verbose_level = cfg->verbose_level; if (TRACE_ABC_REMOVAL) { printf ("\nRemoving array bound checks in %s\n", mono_method_full_name (cfg->method, TRUE)); } area.cfg = cfg; area.relations = (MonoSummarizedValueRelation *) mono_mempool_alloc (cfg->mempool, sizeof (MonoSummarizedValueRelation) * (cfg->next_vreg) * 2); area.contexts = (MonoRelationsEvaluationContext *) mono_mempool_alloc (cfg->mempool, sizeof (MonoRelationsEvaluationContext) * (cfg->next_vreg)); area.variable_value_kind = (MonoIntegerValueKind *) mono_mempool_alloc (cfg->mempool, sizeof (MonoIntegerValueKind) * (cfg->next_vreg)); area.defs = mono_mempool_alloc (cfg->mempool, sizeof (MonoInst*) * cfg->next_vreg); for (i = 0; i < cfg->next_vreg; i++) { area.variable_value_kind [i] = MONO_UNKNOWN_INTEGER_VALUE; area.relations [i].relation = MONO_EQ_RELATION; area.relations [i].relation_is_static_definition = TRUE; MAKE_VALUE_ANY (area.relations [i].related_value); area.relations [i].next = NULL; area.defs [i] = NULL; } for (bb = cfg->bb_entry; bb; bb = bb->next_bb) { MonoInst *ins; if (TRACE_ABC_REMOVAL) printf ("\nABCREM BLOCK %d:\n", bb->block_num); for (ins = bb->code; ins; ins = ins->next) { const char *spec = INS_INFO (ins->opcode); if (spec [MONO_INST_DEST] == ' ' || MONO_IS_STORE_MEMBASE (ins)) continue; if (spec [MONO_INST_DEST] == 'i') { MonoIntegerValueKind effective_value_kind; MonoRelationsEvaluationRange range; MonoSummarizedValueRelation *type_relation; MonoInst *var; if (TRACE_ABC_REMOVAL) mono_print_ins (ins); var = get_vreg_to_inst (cfg, ins->dreg); if (var) area.variable_value_kind [ins->dreg] = type_to_value_kind (var->inst_vtype); effective_value_kind = get_relation_from_ins (&area, ins, &area.relations [ins->dreg], area.variable_value_kind [ins->dreg]); MONO_MAKE_RELATIONS_EVALUATION_RANGE_WEAK (range); apply_value_kind_to_range (&range, area.variable_value_kind [ins->dreg]); apply_value_kind_to_range (&range, effective_value_kind); if (range.upper < INT_MAX) { type_relation = (MonoSummarizedValueRelation *) mono_mempool_alloc (cfg->mempool, sizeof (MonoSummarizedValueRelation)); type_relation->relation = MONO_LE_RELATION; type_relation->related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE; type_relation->related_value.value.constant.value = range.upper; type_relation->relation_is_static_definition = TRUE; type_relation->next = area.relations [ins->dreg].next; area.relations [ins->dreg].next = type_relation; if (TRACE_ABC_REMOVAL) { printf ("[var%d <= %d]", ins->dreg, range.upper); } } if (range.lower > INT_MIN) { type_relation = (MonoSummarizedValueRelation *) mono_mempool_alloc (cfg->mempool, sizeof (MonoSummarizedValueRelation)); type_relation->relation = MONO_GE_RELATION; type_relation->related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE; type_relation->related_value.value.constant.value = range.lower; type_relation->relation_is_static_definition = TRUE; type_relation->next = area.relations [ins->dreg].next; area.relations [ins->dreg].next = type_relation; if (TRACE_ABC_REMOVAL) { printf ("[var%d >= %d]", ins->dreg, range.lower); } } if (TRACE_ABC_REMOVAL) { printf ("Summarized variable %d: ", ins->dreg); print_summarized_value (&(area.relations [ins->dreg].related_value)); printf ("\n"); } } } } /* Add symmetric relations */ for (i = 0; i < cfg->next_vreg; i++) { if (area.relations [i].related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) { int related_index = cfg->next_vreg + i; int related_variable = area.relations [i].related_value.value.variable.variable; area.relations [related_index].relation = MONO_EQ_RELATION; area.relations [related_index].relation_is_static_definition = TRUE; area.relations [related_index].related_value.type = MONO_VARIABLE_SUMMARIZED_VALUE; area.relations [related_index].related_value.value.variable.variable = i; area.relations [related_index].related_value.value.variable.delta = - area.relations [i].related_value.value.variable.delta; area.relations [related_index].next = area.relations [related_variable].next; area.relations [related_variable].next = &(area.relations [related_index]); if (TRACE_ABC_REMOVAL) { printf ("Added symmetric summarized value for variable variable %d (to %d): ", i, related_variable); print_summarized_value (&(area.relations [related_index].related_value)); printf ("\n"); } } } process_block (cfg, cfg->bblocks [0], &area); } #endif /* DISABLE_JIT */