#include <mono/metadata/debug-helpers.h>
#include <mono/metadata/mempool.h>
#include <mono/metadata/opcodes.h>
+#include <mono/metadata/mempool-internals.h>
-#include "inssel.h"
+#ifndef DISABLE_JIT
#include "abcremoval.h"
-extern guint8 mono_burg_arity [];
+#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 > 0)
+#define REPORT_ABC_REMOVAL (verbose_level > 1)
/*
* A little hack for the verbosity level.
#endif
/*
- * Given a MonoInst, if it is a store to a variable return the MonoInst that
- * represents the stored value.
- * If anything goes wrong, return NULL.
- * store: the MonoInst that should be a store
- * expected_variable_index: the variable where the value should be stored
- * return: either the stored value, or NULL
+ * 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 MonoInst *
-get_variable_value_from_store_instruction (MonoInst *store, int expected_variable_index) {
- switch (store->opcode) {
- case CEE_STIND_REF:
- case CEE_STIND_I:
- case CEE_STIND_I4:
- case CEE_STIND_I1:
- case CEE_STIND_I2:
- case CEE_STIND_I8:
- case CEE_STIND_R4:
- case CEE_STIND_R8:
- if (TRACE_ABC_REMOVAL) {
- printf ("[store instruction found]");
- }
- if (store->inst_left->opcode == OP_LOCAL) {
- int variable_index = store->inst_left->inst_c0;
- if (TRACE_ABC_REMOVAL) {
- printf ("[value put in local %d (expected %d)]", variable_index, expected_variable_index);
+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);
}
- if (variable_index == expected_variable_index) {
- return store->inst_right;
- } else {
- return NULL;
+ } 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);
}
}
- else
- {
- return NULL;
- }
- break;
- default:
- return NULL;
}
}
/*
- * Given a MonoInst representing a value, store it in "summarized" form.
+ * 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 void
-summarize_value (MonoInst *value, MonoSummarizedValue *result) {
- switch (value->opcode) {
+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:
- result->type = MONO_CONSTANT_SUMMARIZED_VALUE;
- result->value.constant.value = value->inst_c0;
+ value->type = MONO_CONSTANT_SUMMARIZED_VALUE;
+ value->value.constant.value = ins->inst_c0;
break;
- case OP_LOCAL:
- case OP_ARG:
- result->type = MONO_VARIABLE_SUMMARIZED_VALUE;
- result->value.variable.variable = value->inst_c0;
- result->value.variable.delta = 0;
+ case OP_MOVE:
+ value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
+ value->value.variable.variable = ins->sreg1;
+ value->value.variable.delta = 0;
break;
- case CEE_LDIND_I1:
- case CEE_LDIND_U1:
- case CEE_LDIND_I2:
- case CEE_LDIND_U2:
- case CEE_LDIND_I4:
- case CEE_LDIND_U4:
- case CEE_LDIND_REF:
- if ((value->inst_left->opcode == OP_LOCAL) || (value->inst_left->opcode == OP_ARG)) {
- summarize_value (value->inst_left, result);
- } else {
- MAKE_VALUE_ANY (*result);
- }
+ 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 CEE_ADD: {
- MonoSummarizedValue left_value;
- MonoSummarizedValue right_value;
- summarize_value (value->inst_left, &left_value);
- summarize_value (value->inst_right, &right_value);
-
- if (left_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
- if (right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
- result->type = MONO_VARIABLE_SUMMARIZED_VALUE;
- result->value.variable.variable = left_value.value.variable.variable;
- result->value.variable.delta = left_value.value.variable.delta + right_value.value.constant.value;
- } else {
- MAKE_VALUE_ANY (*result);
- }
- } else if (right_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
- if (left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
- result->type = MONO_VARIABLE_SUMMARIZED_VALUE;
- result->value.variable.variable = right_value.value.variable.variable;
- result->value.variable.delta = left_value.value.constant.value + right_value.value.variable.delta;
- } else {
- MAKE_VALUE_ANY (*result);
- }
- } else if ((right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) && (left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE)) {
- /* This should not happen if constant folding has been done */
- result->type = MONO_CONSTANT_SUMMARIZED_VALUE;
- result->value.constant.value = left_value.value.constant.value + right_value.value.constant.value;
- } else {
- MAKE_VALUE_ANY (*result);
- }
+ 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 CEE_SUB: {
- MonoSummarizedValue left_value;
- MonoSummarizedValue right_value;
- summarize_value (value->inst_left, &left_value);
- summarize_value (value->inst_right, &right_value);
-
- if (left_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
- if (right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
- result->type = MONO_VARIABLE_SUMMARIZED_VALUE;
- result->value.variable.variable = left_value.value.variable.variable;
- result->value.variable.delta = left_value.value.variable.delta - right_value.value.constant.value;
- } else {
- MAKE_VALUE_ANY (*result);
- }
- } else if ((right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) && (left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE)) {
- /* This should not happen if constant folding has been done */
- result->type = MONO_CONSTANT_SUMMARIZED_VALUE;
- result->value.constant.value = left_value.value.constant.value - right_value.value.constant.value;
- } else {
- MAKE_VALUE_ANY (*result);
- }
+ 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 CEE_NEWARR:
- summarize_value (value->inst_newa_len, result);
+ 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 CEE_LDLEN:
- summarize_value (value->inst_left, result);
+ 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_PHI:
- result->type = MONO_PHI_SUMMARIZED_VALUE;
- result->value.phi.number_of_alternatives = *(value->inst_phi_args);
- result->value.phi.phi_alternatives = value->inst_phi_args + 1;
+ case OP_NEWARR:
+ value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
+ value->value.variable.variable = ins->sreg1;
+ value->value.variable.delta = 0;
break;
+
+ /* FIXME: Add more opcodes */
default:
- MAKE_VALUE_ANY (*result);
+ /* 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 (int opcode) {
- switch (opcode) {
- case CEE_BEQ:
- return MONO_EQ_RELATION;
- case CEE_BLT:
- case CEE_BLT_UN:
- return MONO_LT_RELATION;
- case CEE_BLE:
- case CEE_BLE_UN:
- return MONO_LE_RELATION;
- case CEE_BGT:
- case CEE_BGT_UN:
- return MONO_GT_RELATION;
- case CEE_BGE:
- case CEE_BGE_UN:
- return MONO_GE_RELATION;
- case CEE_BNE_UN:
- return MONO_NE_RELATION;
- default:
+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;
}
}
* relations: the resulting relations (entry condition of the given BB)
*/
static void
-get_relations_from_previous_bb (MonoBasicBlock *bb, MonoAdditionalVariableRelationsForBB *relations) {
+get_relations_from_previous_bb (MonoVariableRelationsEvaluationArea *area, MonoBasicBlock *bb, MonoAdditionalVariableRelationsForBB *relations)
+{
MonoBasicBlock *in_bb;
- MonoInst *branch;
+ 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];
- branch = in_bb->last_ins;
- if (branch == NULL) return;
- branch_relation = get_relation_from_branch_instruction (branch->opcode);
- if ((branch_relation != MONO_ANY_RELATION) && (branch->inst_left->opcode == OP_COMPARE)) {
- MonoSummarizedValue left_value;
- MonoSummarizedValue right_value;
- gboolean code_path;
+ 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 = TRUE;
g_assert_not_reached ();
}
-
- if (!code_path) {
+ if (!code_path)
branch_relation = MONO_NEGATED_RELATION (branch_relation);
- }
symmetric_relation = MONO_SYMMETRIC_RELATION (branch_relation);
- summarize_value (branch->inst_left->inst_left, &left_value);
- summarize_value (branch->inst_left->inst_right, &right_value);
-
- if ((left_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) && ((right_value.type == MONO_VARIABLE_SUMMARIZED_VALUE)||(right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE))) {
- relations->relation1.variable = left_value.value.variable.variable;
+ /* 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 = right_value;
- if (right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
- relations->relation1.relation.related_value.value.constant.value -= left_value.value.variable.delta;
- } else {
- relations->relation1.relation.related_value.value.variable.delta -= left_value.value.variable.delta;
- }
- }
- if ((right_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) && ((left_value.type == MONO_VARIABLE_SUMMARIZED_VALUE)||(left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE))) {
- relations->relation2.variable = right_value.value.variable.variable;
+ 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 = left_value;
- if (left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
- relations->relation2.relation.related_value.value.constant.value -= right_value.value.variable.delta;
- } else {
- relations->relation2.relation.related_value.value.variable.delta -= right_value.value.variable.delta;
- }
+ 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) {
+apply_change_to_evaluation_area (MonoVariableRelationsEvaluationArea *area, MonoAdditionalVariableRelation *change)
+{
MonoSummarizedValueRelation *base_relation;
if (change->relation.relation != MONO_ANY_RELATION) {
* change: the relation that must be removed
*/
static void
-remove_change_from_evaluation_area (MonoAdditionalVariableRelation *change) {
+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) {
+clean_contexts (MonoRelationsEvaluationContext *contexts, int number)
+{
int i;
for (i = 0; i < number; i++) {
contexts [i].status = MONO_RELATIONS_EVALUATION_NOT_STARTED;
* relation: the relation between the range and the value
*/
static void
-intersect_value( MonoRelationsEvaluationRange *range, int value, MonoValueRelation relation ) {
+intersect_value( MonoRelationsEvaluationRange *range, int value, MonoValueRelation relation )
+{
switch (relation) {
case MONO_NO_RELATION:
MONO_MAKE_RELATIONS_EVALUATION_RANGE_IMPOSSIBLE (*range);
* relation: the relation between the pairs of ranges
*/
static void
-intersect_ranges( MonoRelationsEvaluationRanges *ranges, MonoRelationsEvaluationRanges *other_ranges, int delta, MonoValueRelation relation ) {
+intersect_ranges( MonoRelationsEvaluationRanges *ranges, MonoRelationsEvaluationRanges *other_ranges, int delta, MonoValueRelation relation )
+{
if (delta == 0) {
switch (relation) {
case MONO_NO_RELATION:
* (or NULL for the first invocation)
*/
static void
-evaluate_relation_with_target_variable (MonoVariableRelationsEvaluationArea *area, int variable, int target_variable, MonoRelationsEvaluationContext *father_context) {
+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
MonoSummarizedValueRelation *relation = &(area->relations [variable]);
if (TRACE_ABC_REMOVAL) {
- printf ("Evaluating varible %d (target variable %d)\n", variable, target_variable);
+ printf ("Evaluating variable %d (target variable %d)\n", variable, target_variable);
print_summarized_value_relation (relation);
printf ("\n");
}
// If the relation is "ANY", nothing to do (no added information)
if (relation->relation != MONO_ANY_RELATION) {
- gssize related_variable = relation->related_value.value.variable.variable;
+ 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
// 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 varible %d (target variable %d), status ", variable, target_variable);
+ printf ("Recursivity detected for variable %d (target variable %d), status ", variable, target_variable);
print_evaluation_context_status (context->status);
}
// 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) {
// 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 varible %d (target variable %d), status ", variable, target_variable);
+ printf ("Recursivity detected for variable %d (target variable %d), status ", variable, target_variable);
print_evaluation_context_status (context->status);
printf ("\n");
}
// 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 varible %d (target variable %d) discards computation, status ", variable, target_variable);
+ printf ("Recursivity for variable %d (target variable %d) discards computation, status ", variable, target_variable);
print_evaluation_context_status (context->status);
printf ("\n");
}
context->status = MONO_RELATIONS_EVALUATION_NOT_STARTED;
} else {
if (TRACE_ABC_REMOVAL) {
- printf ("Ranges for varible %d (target variable %d) computated: ", variable, target_variable);
+ printf ("Ranges for variable %d (target variable %d) computed: ", variable, target_variable);
print_evaluation_context_ranges (&(context->ranges));
printf ("\n");
}
int path_value = 0;
if (TRACE_ABC_REMOVAL) {
- printf ("Evaluation of varible %d (target variable %d) already in progress\n", variable, target_variable);
+ 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");
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;
}
default:
if (TRACE_ABC_REMOVAL) {
- printf ("Varible %d (target variable %d) already in a recursive ring, skipping\n", variable, target_variable);
+ 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");
}
-
/*
- * 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)
+ * Apply the given value kind to the given range
*/
static void
-remove_abc_from_inst (MonoInst *inst, MonoVariableRelationsEvaluationArea *area) {
- if (inst->opcode == CEE_LDELEMA) {
- MonoInst *array_inst = inst->inst_left;
- MonoInst *index_inst = inst->inst_right;
-
- // The array must be a local variable and the index must be a properly summarized value
- if ((array_inst->opcode == CEE_LDIND_REF) &&
- ((array_inst->inst_left->opcode == OP_LOCAL)||(array_inst->inst_left->opcode == OP_ARG))) {
- gssize array_variable = array_inst->inst_left->inst_c0;
- MonoRelationsEvaluationContext *array_context = &(area->contexts [array_variable]);
- MonoSummarizedValue index_value;
-
- summarize_value (index_inst, &index_value);
- if (index_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
- // The easiest case: we just evaluate the array length, to see if it has some relation
- // with the index constant, and act accordingly
-
- clean_contexts (area->contexts, area->cfg->num_varinfo);
- evaluate_relation_with_target_variable (area, array_variable, array_variable, NULL);
-
- if ((index_value.value.constant.value >= 0) && (index_value.value.constant.value < array_context->ranges.zero.lower)) {
- if (REPORT_ABC_REMOVAL) {
- printf ("ARRAY-ACCESS: removed bounds check on array %d with constant index %d in method %s\n",
- array_variable, index_value.value.constant.value, mono_method_full_name (area->cfg->method, TRUE));
- }
- inst->flags |= (MONO_INST_NORANGECHECK);
+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 (index_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
- // The common case: we must evaluate both the index and the array length, and check for relevant
- // relations both through variable definitions and as constant definitions
-
- gssize index_variable = index_value.value.variable.variable;
- MonoRelationsEvaluationContext *index_context = &(area->contexts [index_variable]);
-
- clean_contexts (area->contexts, area->cfg->num_varinfo);
-
- evaluate_relation_with_target_variable (area, index_variable, array_variable, NULL);
- evaluate_relation_with_target_variable (area, array_variable, array_variable, NULL);
-
- MONO_SUB_DELTA_SAFELY_FROM_RANGES (index_context->ranges, index_value.value.variable.delta);
-
- if (index_context->ranges.zero.lower >= 0) {
- if (TRACE_ABC_REMOVAL) {
- 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)||(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 in method %s\n",
- array_variable, index_variable, mono_method_full_name (area->cfg->method, TRUE));
- }
- inst->flags |= (MONO_INST_NORANGECHECK);
- }
+ } else if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 2) {
+ if (range->upper > 0xffff) {
+ range->upper = 0xffff;
}
- if (TRACE_ABC_REMOVAL) {
- 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);
- }
+ }
+ } 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;
}
}
-
}
}
}
/*
- * Recursively scan a tree of MonoInst looking for array accesses.
- * inst: the root of the MonoInst tree
+ * 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
-process_inst (MonoInst *inst, MonoVariableRelationsEvaluationArea *area) {
- if (inst->opcode == CEE_LDELEMA) { /* Handle OP_LDELEMA2D, too */
- if (TRACE_ABC_REMOVAL) {
- printf ("Attempting check removal...\n");
- }
-
- remove_abc_from_inst (inst, area);
- }
+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 (mono_burg_arity [inst->opcode]) {
- process_inst (inst->inst_left, area);
- if (mono_burg_arity [inst->opcode] > 1) {
- process_inst (inst->inst_right, area);
+ 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);
+ }
}
}
}
-
-
-
/*
* Process a BB removing bounds checks from array accesses.
* It does the following (in sequence):
* memory for all the evaluation contexts is already allocated)
*/
static void
-process_block (MonoBasicBlock *bb, MonoVariableRelationsEvaluationArea *area) {
+process_block (MonoCompile *cfg, MonoBasicBlock *bb, MonoVariableRelationsEvaluationArea *area) {
int inst_index;
- MonoInst *current_inst;
+ MonoInst *ins;
MonoAdditionalVariableRelationsForBB additional_relations;
- GList *dominated_bb;
+ GSList *dominated_bb, *l;
+ GSList *check_relations = NULL;
if (TRACE_ABC_REMOVAL) {
- printf ("Processing block %d [dfn %d]...\n", bb->block_num, bb->dfn);
+ printf ("\nProcessing block %d [dfn %d]...\n", bb->block_num, bb->dfn);
}
-
- get_relations_from_previous_bb (bb, &additional_relations);
+
+ 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);
}
apply_change_to_evaluation_area (area, &(additional_relations.relation1));
apply_change_to_evaluation_area (area, &(additional_relations.relation2));
-
+
inst_index = 0;
- current_inst = bb->code;
- while (current_inst != NULL) {
+ 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;
- process_inst (current_inst, area);
-
- current_inst = current_inst->next;
- }
-
+ 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) {
+ MonoRelationsEvaluationContext *context = &(area->contexts [ins->sreg1]);
+
+ clean_contexts (area->contexts, area->cfg->next_vreg);
+ evaluate_relation_with_target_variable (area, ins->sreg1, ins->sreg1, NULL);
+
+ if (context->ranges.zero.lower > 0) {
+ if (REPORT_ABC_REMOVAL)
+ printf ("ARRAY-ACCESS: removed check_this instruction.\n");
+ NULLIFY_INS (ins);
+ }
+ }
+
+ if (ins->opcode == OP_NOT_NULL) {
+ rel = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoAdditionalVariableRelation));
+ rel->variable = ins->sreg1;
+ 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);
+ }
+ }
if (TRACE_ABC_REMOVAL) {
printf ("Processing block %d [dfn %d] done.\n", bb->block_num, bb->dfn);
}
- for (dominated_bb = g_list_first (bb->dominated); dominated_bb != NULL; dominated_bb = g_list_next (dominated_bb)) {
- process_block ((MonoBasicBlock*) (dominated_bb->data), area);
+ 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:
mono_perform_abc_removal (MonoCompile *cfg)
{
MonoVariableRelationsEvaluationArea area;
+ MonoBasicBlock *bb;
int i;
verbose_level = cfg->verbose_level;
if (TRACE_ABC_REMOVAL) {
- printf ("Removing array bound checks in %s\n", mono_method_full_name (cfg->method, TRUE));
+ printf ("\nRemoving array bound checks in %s\n", mono_method_full_name (cfg->method, TRUE));
}
-
+
area.cfg = cfg;
area.relations = (MonoSummarizedValueRelation *)
- alloca (sizeof (MonoSummarizedValueRelation) * (cfg->num_varinfo) * 2);
+ mono_mempool_alloc (cfg->mempool, sizeof (MonoSummarizedValueRelation) * (cfg->next_vreg) * 2);
area.contexts = (MonoRelationsEvaluationContext *)
- alloca (sizeof (MonoRelationsEvaluationContext) * (cfg->num_varinfo));
- for (i = 0; i < cfg->num_varinfo; i++) {
+ 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));
+ 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;
- if (cfg->vars [i]->def != NULL) {
- MonoInst *value = get_variable_value_from_store_instruction (cfg->vars [i]->def, i);
- if (value != NULL) {
- summarize_value (value, &(area.relations [i].related_value));
- if (TRACE_ABC_REMOVAL) {
- printf ("Summarized variable %d: ", i);
- print_summarized_value (&(area.relations [i].related_value));
- printf ("\n");
+ }
+
+ 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);
+ }
}
- } else {
- MAKE_VALUE_ANY (area.relations [i].related_value);
if (TRACE_ABC_REMOVAL) {
- printf ("Definition of variable %d is not a proper store\n", i);
+ printf ("Summarized variable %d: ", ins->dreg);
+ print_summarized_value (&(area.relations [ins->dreg].related_value));
+ printf ("\n");
}
}
- } else {
- MAKE_VALUE_ANY (area.relations [i].related_value);
- if (TRACE_ABC_REMOVAL) {
- printf ("Variable %d has no definition, probably it is an argument\n", i);
- }
}
}
- for (i = 0; i < cfg->num_varinfo; i++) {
+
+ /* 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->num_varinfo + i;
+ 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;
}
}
}
-
- process_block (cfg->bblocks [0], &area);
+
+ process_block (cfg, cfg->bblocks [0], &area);
}
+#endif /* DISABLE_JIT */
projects / mono.git / blobdiff