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>
19 #include "abcremoval.h"
21 extern guint8 mono_burg_arity [];
23 #define TRACE_ABC_REMOVAL (verbose_level > 2)
24 #define REPORT_ABC_REMOVAL (verbose_level > 0)
26 #define CHEAT_AND_REMOVE_ALL_CHECKS 0
28 static int verbose_level;
30 #if (!CHEAT_AND_REMOVE_ALL_CHECKS)
33 #define IS_SUMMARIZED_VALUE_CONSTANT(value) ((value).value_type==MONO_CONSTANT_SUMMARIZED_VALUE)
34 #define IS_SUMMARIZED_VALUE_VARIABLE(value) ((value).value_type==MONO_VARIABLE_SUMMARIZED_VALUE)
36 #define RELATION_BETWEEN_VALUES(value,related_value) (\
37 ((value) > (related_value))? MONO_GT_RELATION :\
38 (((value) < (related_value))? MONO_LT_RELATION : MONO_EQ_RELATION))
40 #define MAKE_VALUE_ANY(v) do{\
41 (v)->relation_with_zero = MONO_ANY_RELATION;\
42 (v)->relation_with_one = MONO_ANY_RELATION;\
43 (v)->relation_with_value = MONO_ANY_RELATION;\
44 (v)->value_type = MONO_CONSTANT_SUMMARIZED_VALUE;\
45 (v)->value.constant = 0;\
48 #define MONO_NEGATED_RELATION(r) ((~(r))&MONO_ANY_RELATION)
49 #define MONO_SYMMETRIC_RELATION(r) (((r)&MONO_EQ_RELATION)|(((r)&MONO_LT_RELATION)<<1)|((r&MONO_GT_RELATION)>>1))
51 #define RELATION_ADDS_INFORMATION(r,r_maybe_adds_information) ((r)&(~(r_maybe_adds_information)))
53 unsigned char propagated_relations_table [] = {
54 #include "propagated_relations_table.def"
57 #define PROPAGATED_RELATION(r,r_to_propagate) (propagated_relations_table [((r)<<3)|(r_to_propagate)])
61 print_relation (int relation) {
64 if (relation & MONO_LT_RELATION) {
68 if (relation & MONO_EQ_RELATION) {
75 if (relation & MONO_GT_RELATION) {
86 print_summarized_value (MonoSummarizedValue *value) {
87 printf ("relation_with_zero: ");
88 print_relation (value->relation_with_zero);
90 printf ("relation_with_one: ");
91 print_relation (value->relation_with_one);
93 printf ("relation_with_value: ");
94 print_relation (value->relation_with_value);
96 switch (value->value_type) {
97 case MONO_CONSTANT_SUMMARIZED_VALUE:
98 printf ("Constant value: %d\n", value->value.constant);
100 case MONO_VARIABLE_SUMMARIZED_VALUE:
101 printf ("Variable value: %d\n", value->value.variable);
103 case MONO_PHI_SUMMARIZED_VALUE: {
105 printf ("PHI value: (");
106 for (i = 0; i < *(value->value.phi_variables); i++) {
108 printf ("%d", *(value->value.phi_variables + i + 1));
114 printf ("Unknown value type: %d\n", value->value_type);
119 print_branch_condition (MonoBranchCondition *condition, int n) {
120 printf ("Branch condition %d, on variable %d\n", n, condition->variable);
121 print_summarized_value (&(condition->value));
125 print_branch_data (MonoBranchData *branch, int n) {
127 printf ("Branch %d, destination BB %d [dfn %d], conditions %d\n",
128 n, branch->destination_block->block_num, branch->destination_block->dfn, branch->number_of_conditions);
129 for (i = 0; i < branch->number_of_conditions; i++) {
130 print_branch_condition (&(branch->conditions [i]), i);
135 print_summarized_block (MonoSummarizedBasicBlock *block) {
137 printf ("Summarization of BB %d [dfn %d] (has array accesses: %d), branches: %d\n",
138 block->block->block_num, block->block->dfn, block->has_array_access_instructions, block->number_of_branches);
139 for (i = 0; i < block->number_of_branches; i++) {
140 print_branch_data (&(block->branches [i]), i);
145 print_variable_relations (MonoVariableRelations *relations, gssize variable, int n) {
147 int significantRelations = 0;
148 for (i = 0; i < n; i++) {
149 if (relations->relations_with_variables [i] != MONO_ANY_RELATION) {
150 significantRelations++;
153 if ((relations->relation_with_zero != MONO_ANY_RELATION) ||
154 (relations->relation_with_one != MONO_ANY_RELATION) ||
155 (significantRelations > 0)) {
156 printf ("Relations for variable %d:\n", variable);
157 if (relations->relation_with_zero != MONO_ANY_RELATION) {
158 printf ("relation_with_zero: ");
159 print_relation (relations->relation_with_zero);
162 if (relations->relation_with_one != MONO_ANY_RELATION) {
163 printf ("relation_with_one: ");
164 print_relation (relations->relation_with_one);
167 if (significantRelations > 0) {
168 printf ("relations_with_variables (%d significant)\n", significantRelations);
169 for (i = 0; i < n; i++) {
170 if (relations->relations_with_variables [i] != MONO_ANY_RELATION) {
171 printf ("relation with variable %d: ", i);
172 print_relation (relations->relations_with_variables [i]);
181 print_all_variable_relations (MonoVariableRelationsEvaluationArea *evaluation_area) {
183 printf ("relations in evaluation area:\n");
184 for (i = 0; i < evaluation_area->cfg->num_varinfo; i++) {
185 print_variable_relations (&(evaluation_area->variable_relations [i]), i, evaluation_area->cfg->num_varinfo);
190 static MonoValueRelation
191 relation_for_sum_of_variable_and_constant (
192 MonoValueRelation variable_relation, MonoValueRelation constant_relation_with_zero) {
193 switch (variable_relation) {
194 case MONO_EQ_RELATION:
195 return constant_relation_with_zero;
196 case MONO_GE_RELATION:
197 if (constant_relation_with_zero & MONO_LT_RELATION) {
198 return MONO_ANY_RELATION;
200 return constant_relation_with_zero;
202 case MONO_LE_RELATION:
203 if (constant_relation_with_zero & MONO_GT_RELATION) {
204 return MONO_ANY_RELATION;
206 return constant_relation_with_zero;
208 case MONO_GT_RELATION:
209 if (constant_relation_with_zero & MONO_LT_RELATION) {
210 return MONO_ANY_RELATION;
212 return MONO_GT_RELATION;
214 case MONO_LT_RELATION:
215 if (constant_relation_with_zero & MONO_GT_RELATION) {
216 return MONO_ANY_RELATION;
218 return MONO_LE_RELATION;
221 g_assert_not_reached ();
222 return MONO_ANY_RELATION;
227 get_variable_value_from_ssa_store (MonoInst *store, int expected_variable_index) {
228 switch (store->opcode) {
237 if (TRACE_ABC_REMOVAL) {
238 printf ("Store instruction found...\n");
240 if (store->inst_left->opcode == OP_LOCAL) {
241 int variable_index = store->inst_left->inst_c0;
242 if (TRACE_ABC_REMOVAL) {
243 printf ("Value put in local %d (expected %d)\n", variable_index, expected_variable_index);
245 if (variable_index == expected_variable_index) {
246 return store->inst_right;
262 summarize_value (MonoInst *value, MonoSummarizedValue *result) {
263 switch (value->opcode) {
265 result->relation_with_zero = RELATION_BETWEEN_VALUES (value->inst_c0, 0);
266 result->relation_with_one = RELATION_BETWEEN_VALUES (abs (value->inst_c0), 1);
267 result->relation_with_value = MONO_EQ_RELATION;
268 result->value_type = MONO_CONSTANT_SUMMARIZED_VALUE;
269 result->value.constant = value->inst_c0;
273 result->relation_with_zero = MONO_ANY_RELATION;
274 result->relation_with_one = MONO_ANY_RELATION;
275 result->relation_with_value = MONO_EQ_RELATION;
276 result->value_type = MONO_VARIABLE_SUMMARIZED_VALUE;
277 result->value.variable = value->inst_c0;
280 if ((value->inst_left->opcode == OP_LOCAL) || (value->inst_left->opcode == OP_ARG)) {
281 summarize_value (value->inst_left, result);
283 MAKE_VALUE_ANY (result);
288 if ((value->inst_left->opcode == OP_LOCAL) || (value->inst_left->opcode == OP_ARG)) {
289 summarize_value (value->inst_left, result);
291 MAKE_VALUE_ANY (result);
296 MonoSummarizedValue left_value;
297 MonoSummarizedValue right_value;
298 summarize_value (value->inst_left, &left_value);
299 summarize_value (value->inst_right, &right_value);
301 if (IS_SUMMARIZED_VALUE_VARIABLE (left_value)) {
302 if (IS_SUMMARIZED_VALUE_CONSTANT (right_value)&& (right_value.value.constant = 1)) {
303 MonoValueRelation constant_relation_with_zero = right_value.relation_with_zero;
304 if (value->opcode == CEE_SUB) {
305 constant_relation_with_zero = MONO_SYMMETRIC_RELATION (constant_relation_with_zero);
307 result->relation_with_value = relation_for_sum_of_variable_and_constant (
308 left_value.relation_with_value, constant_relation_with_zero);
309 if (result->relation_with_value != MONO_ANY_RELATION) {
310 result->relation_with_zero = MONO_ANY_RELATION;
311 result->relation_with_one = MONO_ANY_RELATION;
312 result->value_type = MONO_VARIABLE_SUMMARIZED_VALUE;
313 result->value.variable = left_value.value.variable;
315 MAKE_VALUE_ANY (result);
318 MAKE_VALUE_ANY (result);
320 } else if (IS_SUMMARIZED_VALUE_VARIABLE (right_value)) {
321 if (IS_SUMMARIZED_VALUE_CONSTANT (left_value)&& (left_value.value.constant == 1)) {
322 MonoValueRelation constant_relation_with_zero = left_value.relation_with_zero;
323 if (value->opcode == CEE_SUB) {
324 constant_relation_with_zero = MONO_SYMMETRIC_RELATION (constant_relation_with_zero);
326 result->relation_with_value = relation_for_sum_of_variable_and_constant (
327 right_value.relation_with_value, constant_relation_with_zero);
328 if (result->relation_with_value != MONO_ANY_RELATION) {
329 result->relation_with_zero = MONO_ANY_RELATION;
330 result->relation_with_one = MONO_ANY_RELATION;
331 result->value_type = MONO_VARIABLE_SUMMARIZED_VALUE;
332 result->value.variable = right_value.value.variable;
334 MAKE_VALUE_ANY (result);
337 MAKE_VALUE_ANY (result);
339 } else if (IS_SUMMARIZED_VALUE_CONSTANT (right_value)&& IS_SUMMARIZED_VALUE_CONSTANT (left_value)) {
340 /* This should not happen if constant folding has been done */
341 if (right_value.relation_with_value == MONO_EQ_RELATION && left_value.relation_with_value == MONO_EQ_RELATION) {
343 if (value->opcode == CEE_ADD) {
344 constant = right_value.value.constant + left_value.value.constant;
347 constant = right_value.value.constant - left_value.value.constant;
349 result->relation_with_zero = RELATION_BETWEEN_VALUES (constant, 0);
350 result->relation_with_one = RELATION_BETWEEN_VALUES (abs (constant), 1);
351 result->relation_with_value = MONO_EQ_RELATION;
352 result->value_type = MONO_CONSTANT_SUMMARIZED_VALUE;
353 result->value.constant = constant;
355 MAKE_VALUE_ANY (result);
358 MAKE_VALUE_ANY (result);
363 summarize_value (value->inst_newa_len, result);
366 summarize_value (value->inst_left, result);
369 result->relation_with_zero = MONO_ANY_RELATION;
370 result->relation_with_one = MONO_ANY_RELATION;
371 result->relation_with_value = MONO_EQ_RELATION;
372 result->value_type = MONO_PHI_SUMMARIZED_VALUE;
373 result->value.phi_variables = value->inst_phi_args;
376 MAKE_VALUE_ANY (result);
380 static MonoValueRelation
381 get_relation_from_branch_instruction (int opcode) {
384 return MONO_EQ_RELATION;
387 return MONO_LT_RELATION;
390 return MONO_LE_RELATION;
393 return MONO_GT_RELATION;
396 return MONO_GE_RELATION;
398 return MONO_NE_RELATION;
400 g_assert_not_reached ();
401 return MONO_ANY_RELATION;
406 contains_array_access (MonoInst *inst) {
407 if (inst->opcode == CEE_LDELEMA) { /* Handle OP_LDELEMA2D, too */
411 if (mono_burg_arity [inst->opcode]) {
412 if (contains_array_access (inst->inst_left)) {
415 if (mono_burg_arity [inst->opcode] > 1) {
416 return contains_array_access (inst->inst_right);
423 analyze_block (MonoBasicBlock *bb, MonoVariableRelationsEvaluationArea *evaluation_area) {
424 MonoSummarizedBasicBlock *b = &(evaluation_area->blocks [bb->dfn]);
425 MonoInst *current_inst = bb->code;
426 MonoInst *last_inst = NULL;
429 if (TRACE_ABC_REMOVAL) {
430 printf ("Analyzing block %d [dfn %d]\n", bb->block_num, bb->dfn);
433 g_assert (bb->dfn < evaluation_area->cfg->num_bblocks);
434 b->has_array_access_instructions = 0;
437 while (current_inst != NULL) {
438 if (TRACE_ABC_REMOVAL) {
439 printf ("Analyzing instruction %d\n", inst_index);
443 if (contains_array_access (current_inst)) {
444 b->has_array_access_instructions = 1;
447 if (current_inst->next == NULL) {
448 last_inst = current_inst;
450 current_inst = current_inst->next;
453 if (last_inst != NULL) {
454 switch (last_inst->opcode) {
465 if (last_inst->inst_left->opcode == OP_COMPARE) {
466 int number_of_variables = 0;
467 int current_variable = 0;
469 MonoSummarizedValue left_value;
470 MonoSummarizedValue right_value;
471 MonoValueRelation relation = get_relation_from_branch_instruction (last_inst->opcode);
472 MonoValueRelation symmetric_relation = MONO_SYMMETRIC_RELATION (relation);
473 summarize_value (last_inst->inst_left->inst_left, &left_value);
474 summarize_value (last_inst->inst_left->inst_right, &right_value);
475 /* It is actually possible to handle some more case... */
476 if ((left_value.relation_with_value == MONO_EQ_RELATION) &&
477 (right_value.relation_with_value == MONO_EQ_RELATION)) {
478 if (left_value.value_type == MONO_VARIABLE_SUMMARIZED_VALUE)number_of_variables++;
479 if (right_value.value_type == MONO_VARIABLE_SUMMARIZED_VALUE)number_of_variables++;
480 if (number_of_variables > 0) {
481 MonoBranchData *branch_true;
482 MonoBranchData *branch_false;
484 b->number_of_branches = 2;
485 b->branches = (MonoBranchData*) mono_mempool_alloc (
486 evaluation_area->pool, sizeof (MonoBranchData) * 2);
487 branch_true = &(b->branches [0]);
488 branch_true->destination_block = last_inst->inst_true_bb;
489 branch_true->number_of_conditions = number_of_variables;
490 branch_true->conditions = (MonoBranchCondition*)
491 mono_mempool_alloc (evaluation_area->pool, sizeof (MonoBranchCondition) * number_of_variables);
492 branch_false = &(b->branches [1]);
493 branch_false->destination_block = last_inst->inst_false_bb;
494 branch_false->number_of_conditions = number_of_variables;
495 branch_false->conditions = (MonoBranchCondition*)
496 mono_mempool_alloc (evaluation_area->pool, sizeof (MonoBranchCondition) * number_of_variables);
497 if (left_value.value_type == MONO_VARIABLE_SUMMARIZED_VALUE) {
498 MonoBranchCondition *condition_true = &(branch_true->conditions [current_variable]);
499 MonoBranchCondition *condition_false;
501 condition_true->variable = left_value.value.variable;
502 condition_true->value = right_value;
503 condition_true->value.relation_with_zero = MONO_ANY_RELATION;
504 condition_true->value.relation_with_one = MONO_ANY_RELATION;
505 condition_true->value.relation_with_value = relation;
506 condition_false = &(branch_false->conditions [current_variable]);
507 condition_false->variable = left_value.value.variable;
508 condition_false->value = right_value;
509 condition_false->value.relation_with_zero = MONO_ANY_RELATION;
510 condition_false->value.relation_with_one = MONO_ANY_RELATION;
511 condition_false->value.relation_with_value = MONO_NEGATED_RELATION (relation);
514 if (right_value.value_type == MONO_VARIABLE_SUMMARIZED_VALUE) {
515 MonoBranchCondition *condition_true = &(branch_true->conditions [current_variable]);
516 MonoBranchCondition *condition_false;
518 condition_true->variable = right_value.value.variable;
519 condition_true->value = left_value;
520 condition_true->value.relation_with_zero = MONO_ANY_RELATION;
521 condition_true->value.relation_with_one = MONO_ANY_RELATION;
522 condition_true->value.relation_with_value = symmetric_relation;
523 condition_false = &(branch_false->conditions [current_variable]);
524 condition_false->variable = right_value.value.variable;
525 condition_false->value = left_value;
526 condition_false->value.relation_with_zero = MONO_ANY_RELATION;
527 condition_false->value.relation_with_one = MONO_ANY_RELATION;
528 condition_false->value.relation_with_value = MONO_NEGATED_RELATION (symmetric_relation);
531 b->number_of_branches = 0;
535 b->number_of_branches = 0;
539 b->number_of_branches = 0;
544 /* Should handle switches... */
545 /* switch_operand = last_inst->inst_right; */
546 /* number_of_cases = GPOINTER_TO_INT (last_inst->klass); */
547 /* cases = last_inst->inst_many_bb; */
548 b->number_of_branches = 0;
552 b->number_of_branches = 0;
556 b->number_of_branches = 0;
560 if (TRACE_ABC_REMOVAL) {
561 print_summarized_block (b);
565 #define SET_VARIABLE_RELATIONS(vr, relation, n)do {\
566 (vr)->relation_with_zero = (relation);\
567 (vr)->relation_with_one = (relation);\
568 memset ((vr)->relations_with_variables,(relation),(n));\
571 #define COMBINE_VARIABLE_RELATIONS(operator, vr, related_vr, n)do {\
573 operator ((vr)->relation_with_zero, (related_vr)->relation_with_zero);\
574 operator ((vr)->relation_with_one, (related_vr)->relation_with_one);\
575 for (i = 0; i < (n); i++) {\
576 operator ((vr)->relations_with_variables [i], (related_vr)->relations_with_variables [i]);\
580 #define RELATION_ASSIGNMENT(destination,source) (destination)=(source)
581 #define RELATION_UNION(destination,source) (destination)|=(source)
582 #define RELATION_INTERSECTION(destination,source) (destination)&=(source)
587 evaluate_variable_relations (gssize variable, MonoVariableRelationsEvaluationArea *evaluation_area, MonoRelationsEvaluationContext *father_context) {
588 MonoVariableRelations *relations = &(evaluation_area->variable_relations [variable]);
589 MonoRelationsEvaluationContext context;
590 if (TRACE_ABC_REMOVAL) {
591 printf ("Applying definition of variable %d\n", variable);
593 context.father_context = father_context;
594 context.variable = variable;
595 switch (relations->evaluation_step) {
596 case MONO_RELATIONS_EVALUATION_NOT_STARTED: {
597 MonoSummarizedValue *value = &(evaluation_area->variable_definitions [variable]);
598 relations->evaluation_step = MONO_RELATIONS_EVALUATION_IN_PROGRESS;
599 if (TRACE_ABC_REMOVAL) {
600 printf ("Current step is MONO_RELATIONS_EVALUATION_NOT_STARTED, summarized value is:\n");
601 print_summarized_value (value);
603 switch (value->value_type) {
604 case MONO_CONSTANT_SUMMARIZED_VALUE:
605 if (value->relation_with_value == MONO_EQ_RELATION) {
606 relations->relation_with_zero &= RELATION_BETWEEN_VALUES (value->value.constant, 0);
607 relations->relation_with_one &= RELATION_BETWEEN_VALUES (abs (value->value.constant), 1);
609 /* Other cases should not happen... */
611 case MONO_VARIABLE_SUMMARIZED_VALUE: {
612 gssize related_variable = value->value.variable;
613 relations->relations_with_variables [related_variable] = value->relation_with_value;
614 evaluate_variable_relations (related_variable, evaluation_area, &context);
615 if (value->relation_with_value == MONO_EQ_RELATION) {
616 COMBINE_VARIABLE_RELATIONS (RELATION_INTERSECTION, relations,
617 &(evaluation_area->variable_relations [related_variable]), evaluation_area->cfg->num_varinfo);
619 /* Other cases should be handled... */
622 case MONO_PHI_SUMMARIZED_VALUE:
623 if (value->relation_with_value == MONO_EQ_RELATION) {
625 MonoVariableRelations *phi_union = (MonoVariableRelations*) alloca (sizeof (MonoVariableRelations));
626 phi_union->relations_with_variables = (unsigned char*) alloca (evaluation_area->cfg->num_varinfo);
627 SET_VARIABLE_RELATIONS (phi_union, MONO_NO_RELATION, evaluation_area->cfg->num_varinfo);
628 for (phi = 0; phi < *(value->value.phi_variables); phi++) {
629 gssize related_variable = value->value.phi_variables [phi+1];
630 evaluate_variable_relations (related_variable, evaluation_area, &context);
631 COMBINE_VARIABLE_RELATIONS (RELATION_UNION, phi_union,
632 &(evaluation_area->variable_relations [related_variable]), evaluation_area->cfg->num_varinfo);
634 if (TRACE_ABC_REMOVAL) {
635 printf ("Resulting phi_union is:\n");
636 print_variable_relations (phi_union, variable, evaluation_area->cfg->num_varinfo);
638 COMBINE_VARIABLE_RELATIONS (RELATION_INTERSECTION, relations,
639 phi_union, evaluation_area->cfg->num_varinfo);
641 /* Other cases should not happen... */
644 g_assert_not_reached ();
648 case MONO_RELATIONS_EVALUATION_IN_PROGRESS: {
649 MonoVariableRelations *recursive_value_relations = NULL;
650 unsigned char recursive_relation = MONO_ANY_RELATION;
651 MonoRelationsEvaluationContext *current_context = context.father_context;
652 if (TRACE_ABC_REMOVAL) {
653 printf ("Current step is MONO_RELATIONS_EVALUATION_IN_PROGRESS\n");
655 relations->definition_is_recursive = 1;
656 while (current_context != NULL && current_context->variable != variable) {
657 MonoVariableRelations *context_relations = &(evaluation_area->variable_relations [current_context->variable]);
658 MonoSummarizedValue *context_value = &(evaluation_area->variable_definitions [current_context->variable]);
659 if (TRACE_ABC_REMOVAL) {
660 printf ("Backtracing to context %d\n", current_context->variable);
662 if (recursive_value_relations == NULL) {
663 if (context_value->relation_with_value != MONO_EQ_RELATION) {
664 recursive_value_relations = context_relations;
665 recursive_relation = context_value->relation_with_value;
666 if (TRACE_ABC_REMOVAL) {
667 printf ("Accepted recursive definition, relation is ");
668 print_relation (recursive_relation);
673 if (context_value->relation_with_value != MONO_EQ_RELATION) {
674 recursive_relation = MONO_NO_RELATION;
675 if (TRACE_ABC_REMOVAL) {
676 printf ("Rejected recursive definition, bad relation is ");
677 print_relation (context_value->relation_with_value);
682 current_context = current_context->father_context;
684 if (recursive_value_relations != NULL && recursive_relation != MONO_NO_RELATION) {
686 /* This should handle "grows" and "decreases" cases */
687 recursive_value_relations->relation_with_zero &= recursive_relation;
688 for (i = 0; i < evaluation_area->cfg->num_varinfo; i++) {
689 recursive_value_relations->relations_with_variables [i] &= recursive_relation;
694 case MONO_RELATIONS_EVALUATION_COMPLETED:
695 if (TRACE_ABC_REMOVAL) {
696 printf ("Current step is MONO_RELATIONS_EVALUATION_COMPLETED\n");
700 g_assert_not_reached ();
703 relations->evaluation_step = MONO_RELATIONS_EVALUATION_COMPLETED;
707 propagate_relations (MonoVariableRelationsEvaluationArea *evaluation_area) {
710 for (variable = 0; variable < evaluation_area->cfg->num_varinfo; variable++) {
711 MonoVariableRelations *relations = &(evaluation_area->variable_relations [variable]);
712 gssize related_variable;
713 for (related_variable = 0; related_variable < evaluation_area->cfg->num_varinfo; related_variable++) {
714 unsigned char relation_with_variable = relations->relations_with_variables [related_variable];
715 if (relation_with_variable != MONO_ANY_RELATION) {
716 MonoVariableRelations *related_relations = &(evaluation_area->variable_relations [related_variable]);
717 gssize variable_related_to_related_variable;
718 unsigned char new_relation_with_zero = PROPAGATED_RELATION (relation_with_variable, related_relations->relation_with_zero);
719 if (RELATION_ADDS_INFORMATION (relations->relation_with_zero, new_relation_with_zero)) {
720 if (TRACE_ABC_REMOVAL) {
721 printf ("RELATION_ADDS_INFORMATION variable %d, related_variable %d, relation_with_zero ",
722 variable, related_variable);
723 print_relation (relations->relation_with_zero);
725 print_relation (new_relation_with_zero);
728 relations->relation_with_zero &= new_relation_with_zero;
729 if (TRACE_ABC_REMOVAL) {
730 print_relation (relations->relation_with_zero);
735 for (variable_related_to_related_variable = 0; variable_related_to_related_variable < evaluation_area->cfg->num_varinfo; variable_related_to_related_variable++) {
736 unsigned char relation_of_variable = related_relations->relations_with_variables [variable_related_to_related_variable];
737 unsigned char relation_with_other_variable = relations->relations_with_variables [variable_related_to_related_variable];
738 unsigned char new_relation_with_other_variable = PROPAGATED_RELATION (relation_with_variable, relation_of_variable);
739 if (RELATION_ADDS_INFORMATION (relation_with_other_variable, new_relation_with_other_variable)) {
740 if (TRACE_ABC_REMOVAL) {
741 printf ("RELATION_ADDS_INFORMATION variable %d, related_variable %d, variable_related_to_related_variable %d, ",
742 variable, related_variable, variable_related_to_related_variable);
743 print_relation (relation_with_variable);
745 print_relation (new_relation_with_other_variable);
748 relations->relations_with_variables [variable_related_to_related_variable] &= new_relation_with_other_variable;
749 if (TRACE_ABC_REMOVAL) {
750 print_relation (relations->relations_with_variables [variable_related_to_related_variable]);
763 remove_abc_from_inst (MonoInst *inst, MonoVariableRelationsEvaluationArea *evaluation_area) {
764 if (inst->opcode == CEE_LDELEMA) {
765 MonoInst *array_inst = inst->inst_left;
766 MonoInst *index_inst = inst->inst_right;
767 /* Both the array and the index must be local variables */
768 if ((array_inst->opcode == CEE_LDIND_REF) &&
769 ((array_inst->inst_left->opcode == OP_LOCAL)||(array_inst->inst_left->opcode == OP_ARG)) &&
770 ((index_inst->opcode == CEE_LDIND_I1) ||
771 (index_inst->opcode == CEE_LDIND_U1) ||
772 (index_inst->opcode == CEE_LDIND_I2) ||
773 (index_inst->opcode == CEE_LDIND_U2) ||
774 (index_inst->opcode == CEE_LDIND_I4) ||
775 (index_inst->opcode == CEE_LDIND_U4))&&
776 ((index_inst->inst_left->opcode == OP_LOCAL)||(index_inst->inst_left->opcode == OP_ARG))) {
777 gssize array_variable = array_inst->inst_left->inst_c0;
778 gssize index_variable = index_inst->inst_left->inst_c0;
779 MonoVariableRelations *index_relations = &(evaluation_area->variable_relations [index_variable]);
780 if ( (! (index_relations->relation_with_zero & ~MONO_GE_RELATION)) &&
781 (! (index_relations->relations_with_variables [array_variable] & ~MONO_LT_RELATION)) ) {
782 inst->flags |= (MONO_INST_NORANGECHECK);
784 if (TRACE_ABC_REMOVAL) {
785 if (! (index_relations->relation_with_zero & ~MONO_GE_RELATION)) {
786 printf ("ARRAY-ACCESS: Removed lower bound check on array %d with index %d\n", array_variable, index_variable);
788 printf ("ARRAY-ACCESS: Left lower bound check on array %d with index %d\n", array_variable, index_variable);
790 if (! (index_relations->relations_with_variables [array_variable] & ~MONO_LT_RELATION)) {
791 printf ("ARRAY-ACCESS: Removed upper bound check on array %d with index %d\n", array_variable, index_variable);
793 printf ("ARRAY-ACCESS: Left upper bound check on array %d with index %d\n", array_variable, index_variable);
796 if (REPORT_ABC_REMOVAL) {
797 if (inst->flags & (MONO_INST_NORANGECHECK)) {
798 printf ("ARRAY-ACCESS: removed bounds check on array %d with index %d in method %s\n",
799 array_variable, index_variable, mono_method_full_name (evaluation_area->cfg->method, TRUE));
805 if (mono_burg_arity [inst->opcode]) {
806 remove_abc_from_inst (inst->inst_left, evaluation_area);
807 if (mono_burg_arity [inst->opcode] > 1) {
808 remove_abc_from_inst (inst->inst_right, evaluation_area);
814 remove_abc_from_block (MonoSummarizedBasicBlock *b, MonoVariableRelationsEvaluationArea *evaluation_area) {
818 MonoInst *current_inst = b->block->code;
820 if (TRACE_ABC_REMOVAL) {
821 printf ("Working on block %d [dfn %d], has_array_access_instructions is %d\n",
822 b->block->block_num, b->block->dfn, b->has_array_access_instructions);
825 if (b->has_array_access_instructions) {
826 for (i = 0; i < evaluation_area->cfg->num_varinfo; i++) {
827 evaluation_area->variable_relations [i].evaluation_step = MONO_RELATIONS_EVALUATION_NOT_STARTED;
828 evaluation_area->variable_relations [i].definition_is_recursive = 0;
829 SET_VARIABLE_RELATIONS (&(evaluation_area->variable_relations [i]), MONO_ANY_RELATION, evaluation_area->cfg->num_varinfo);
834 /* Walk up dominators tree to put conditions in area */
836 /* for (in_index = 0; in_index < bb->in_count; in_index++) { */
837 if (bb->in_count == 1) { /* Should write the code to "sum" conditions... */
839 MonoBasicBlock *in_bb = bb->in_bb [in_index];
840 MonoSummarizedBasicBlock *in_b = &(evaluation_area->blocks [in_bb->dfn]);
841 for (out_index = 0; out_index < in_b->number_of_branches; out_index++) {
842 if (in_b->branches [out_index].destination_block == bb) {
843 MonoBranchData *branch;
845 if (TRACE_ABC_REMOVAL) {
846 printf ("Applying conditions of branch %d -> %d\n", in_b->block->block_num, bb->block_num);
848 branch = &(in_b->branches [out_index]);
849 for (condition_index = 0; condition_index < branch->number_of_conditions; condition_index++) {
850 MonoBranchCondition *condition = &(branch->conditions [condition_index]);
851 MonoVariableRelations *relations = &(evaluation_area->variable_relations [condition->variable]);
852 switch (condition->value.value_type) {
853 case MONO_CONSTANT_SUMMARIZED_VALUE: {
854 if (condition->value.relation_with_value == MONO_EQ_RELATION) {
855 relations->relation_with_zero &= RELATION_BETWEEN_VALUES (condition->value.value.constant, 0);
856 relations->relation_with_one &= RELATION_BETWEEN_VALUES (abs (condition->value.value.constant), 1);
857 if (TRACE_ABC_REMOVAL) {
858 printf ("Applied equality condition with constant to variable %d; relatrion with 0: ", condition->variable);
859 print_relation (relations->relation_with_zero);
862 } else if (condition->value.value.constant == 0) {
863 relations->relation_with_zero &= condition->value.relation_with_value;
864 if (TRACE_ABC_REMOVAL) {
865 printf ("Applied relation with 0 to variable %d: ", condition->variable);
866 print_relation (relations->relation_with_zero);
870 /* Other cases should be handled */
873 case MONO_VARIABLE_SUMMARIZED_VALUE: {
874 relations->relations_with_variables [condition->value.value.variable] &= condition->value.relation_with_value;
875 if (TRACE_ABC_REMOVAL) {
876 printf ("Applied relation between variables %d and %d: ", condition->variable, condition->value.value.variable);
877 print_relation (relations->relations_with_variables [condition->value.value.variable]);
883 g_assert_not_reached (); /* PHIs are not OK here */
892 if (TRACE_ABC_REMOVAL) {
893 printf ("Branch conditions applied... ");
894 print_all_variable_relations (evaluation_area);
897 for (i = 0; i < evaluation_area->cfg->num_varinfo; i++) {
898 evaluate_variable_relations (i, evaluation_area, NULL);
901 if (TRACE_ABC_REMOVAL) {
902 printf ("Variable definitions applied... ");
903 print_all_variable_relations (evaluation_area);
908 changes = propagate_relations (evaluation_area);
910 if (TRACE_ABC_REMOVAL) {
911 printf ("Propagated %d changes\n", changes);
913 } while ((changes > 0) && (i < evaluation_area->cfg->num_varinfo));
915 if (TRACE_ABC_REMOVAL) {
916 printf ("Relations fully propagated... ");
917 print_all_variable_relations (evaluation_area);
920 /* Area is ready, look for array access instructions */
921 if (TRACE_ABC_REMOVAL) {
922 printf ("Going after array accesses...\n");
924 while (current_inst != NULL) {
925 remove_abc_from_inst (current_inst, evaluation_area);
926 current_inst = current_inst->next;
932 mono_perform_abc_removal (MonoCompile *cfg)
934 MonoVariableRelationsEvaluationArea evaluation_area;
936 verbose_level = cfg->verbose_level;
939 if (TRACE_ABC_REMOVAL) {
940 printf ("Removing array bound checks in %s\n", mono_method_full_name (cfg->method, TRUE));
943 if (cfg->num_varinfo > 250) {
944 if (TRACE_ABC_REMOVAL) {
945 printf ("Too many variables (%d), giving up...\n", cfg->num_varinfo);
950 evaluation_area.pool = mono_mempool_new ();
951 evaluation_area.cfg = cfg;
952 evaluation_area.variable_relations = (MonoVariableRelations *)
953 mono_mempool_alloc (evaluation_area.pool, sizeof (MonoVariableRelations) * (cfg->num_varinfo));
954 //printf ("Allocated %d bytes for %d variable relations at pointer %p\n",
955 // sizeof (MonoVariableRelations) * (cfg->num_varinfo), (cfg->num_varinfo), evaluation_area.variable_relations);
956 for (i = 0; i < cfg->num_varinfo; i++ ) {
957 evaluation_area.variable_relations [i].relations_with_variables = (unsigned char *)
958 mono_mempool_alloc (evaluation_area.pool, (cfg->num_varinfo));
959 //printf ("Allocated %d bytes [%d] at pointer %p\n",
960 // cfg->num_varinfo, i, evaluation_area.variable_relations [i].relations_with_variables);
962 evaluation_area.variable_definitions = (MonoSummarizedValue *)
963 mono_mempool_alloc (evaluation_area.pool, sizeof (MonoSummarizedValue) * (cfg->num_varinfo));
964 //printf ("Allocated %d bytes for %d variable definitions at pointer %p\n",
965 // sizeof (MonoSummarizedValue) * (cfg->num_varinfo), (cfg->num_varinfo), evaluation_area.variable_definitions);
966 if (TRACE_ABC_REMOVAL) {
967 printf ("Method contains %d variables\n", i);
969 for (i = 0; i < cfg->num_varinfo; i++) {
970 if (cfg->vars [i]->def != NULL) {
971 MonoInst *value = get_variable_value_from_ssa_store (cfg->vars [i]->def, i);
973 summarize_value (value, evaluation_area.variable_definitions + i);
974 if (TRACE_ABC_REMOVAL) {
975 printf ("Summarized variable %d\n", i);
976 print_summarized_value (evaluation_area.variable_definitions + i);
979 MAKE_VALUE_ANY (evaluation_area.variable_definitions + i);
980 if (TRACE_ABC_REMOVAL) {
981 printf ("Definition of variable %d is not a proper store\n", i);
985 MAKE_VALUE_ANY (evaluation_area.variable_definitions + i);
986 if (TRACE_ABC_REMOVAL) {
987 printf ("Variable %d has no definition, probably it is an argument\n", i);
988 print_summarized_value (evaluation_area.variable_definitions + i);
993 evaluation_area.blocks = (MonoSummarizedBasicBlock *)
994 mono_mempool_alloc (evaluation_area.pool, sizeof (MonoSummarizedBasicBlock) * (cfg->num_bblocks));
995 //printf ("Allocated %d bytes for %d blocks at pointer %p\n",
996 // sizeof (MonoSummarizedBasicBlock) * (cfg->num_bblocks), (cfg->num_bblocks), evaluation_area.blocks);
998 for (i = 0; i < cfg->num_bblocks; i++) {
999 analyze_block (cfg->bblocks [i], &evaluation_area);
1002 for (i = 0; i < cfg->num_bblocks; i++) {
1003 remove_abc_from_block (&(evaluation_area.blocks [i]), &evaluation_area);
1006 mono_mempool_destroy (evaluation_area.pool);
1010 static void remove_abc (MonoInst *inst) {
1011 if (inst->opcode == CEE_LDELEMA) {
1012 if (TRACE_ABC_REMOVAL||REPORT_ABC_REMOVAL) {
1013 printf ("Performing removal...\n");
1015 inst->flags |= (MONO_INST_NORANGECHECK);
1018 if (mono_burg_arity [inst->opcode]) {
1019 remove_abc (inst->inst_left);
1020 if (mono_burg_arity [inst->opcode] > 1) {
1021 remove_abc (inst->inst_right);
1027 mono_perform_abc_removal (MonoCompile *cfg) {
1028 verbose_level = cfg->verbose_level;
1031 #if (TRACE_ABC_REMOVAL)
1032 printf ("Removing array bound checks in %s\n", mono_method_full_name (cfg->method, TRUE));
1035 for (i = 0; i < cfg->num_bblocks; i++) {
1036 #if (TRACE_ABC_REMOVAL)
1037 printf (" Working on block %d [dfn %d]\n", cfg->bblocks [i]->block_num, i);
1040 MonoBasicBlock *bb = cfg->bblocks [i];
1041 MonoInst *inst = bb->code;
1042 while (inst != NULL) {