?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Update spec file to 4.5 profile
[mono-project.git] / mono / mini / abcremoval.c
blob5e97cba1516fa5fedebc55f7fdbf4901e0e8a17d
1 /*
2 * abcremoval.c: Array bounds check removal
3 *
4 * Author:
5 * Massimiliano Mantione (massi@ximian.com)
6 *
7 * (C) 2004 Ximian, Inc. http://www.ximian.com
8 */
9 #include <string.h>
10 #include <stdio.h>
11
12 #include <mono/metadata/debug-helpers.h>
13 #include <mono/metadata/mempool.h>
14 #include <mono/metadata/opcodes.h>
15 #include <mono/metadata/mempool-internals.h>
16
17 #include <config.h>
18
19 #ifndef DISABLE_JIT
20
21 #include "abcremoval.h"
22
23 #if SIZEOF_VOID_P == 8
24 #define OP_PCONST OP_I8CONST
25 #else
26 #define OP_PCONST OP_ICONST
27 #endif
28
29
30 #define TRACE_ABC_REMOVAL (verbose_level > 2)
31 #define REPORT_ABC_REMOVAL (verbose_level > 1)
32
33 /*
34 * A little hack for the verbosity level.
35 * The verbosity level is stored in the cfg, but not all functions that must
36 * print something see the cfg, so we store the verbosity level here at the
37 * beginning of the algorithm.
38 * This is not thread safe (does not handle correctly different verbosity
39 * levels in different threads), and is not exact in case of dynamic changes
40 * of the verbosity level...
41 * Anyway, this is not needed, all that can happen is that something more
42 * (or less) is logged, the result is in any case correct.
43 */
44 static int verbose_level;
45
46
47 #define RELATION_BETWEEN_VALUES(value,related_value) (\
48 ((value) > (related_value))? MONO_GT_RELATION :\
49 (((value) < (related_value))? MONO_LT_RELATION : MONO_EQ_RELATION))
50
51 #define MAKE_VALUE_ANY(v) do{\
52 (v).type = MONO_ANY_SUMMARIZED_VALUE;\
53 } while (0)
54
55 #define MAKE_VALUE_RELATION_ANY(r) do{\
56 (r)->relation = MONO_ANY_RELATION;\
57 MAKE_VALUE_ANY((r)->related_value);\
58 } while (0)
59
60 #define INITIALIZE_VALUE_RELATION(r) do{\
61 MAKE_VALUE_RELATION_ANY((r));\
62 (r)->next = NULL;\
63 } while (0)
64
65 #define MONO_NEGATED_RELATION(r) ((~(r))&MONO_ANY_RELATION)
66 #define MONO_SYMMETRIC_RELATION(r) (((r)&MONO_EQ_RELATION)|(((r)&MONO_LT_RELATION)<<1)|((r&MONO_GT_RELATION)>>1))
67
68
69
70 static void
71 print_relation (int relation) {
72 int print_or = 0;
73 printf ("(");
74 if (relation & MONO_LT_RELATION) {
75 printf ("LT");
76 print_or = 1;
77 }
78 if (relation & MONO_EQ_RELATION) {
79 if (print_or) {
80 printf ("|");
81 }
82 printf ("EQ");
83 print_or = 1;
84 }
85 if (relation & MONO_GT_RELATION) {
86 if (print_or) {
87 printf ("|");
88 }
89 printf ("GT");
90 print_or = 1;
91 }
92 printf (")");
93 }
94
95 static void
96 print_summarized_value (MonoSummarizedValue *value) {
97 switch (value->type) {
98 case MONO_ANY_SUMMARIZED_VALUE:
99 printf ("ANY");
100 break;
101 case MONO_CONSTANT_SUMMARIZED_VALUE:
102 printf ("CONSTANT %d", value->value.constant.value);
103 break;
104 case MONO_VARIABLE_SUMMARIZED_VALUE:
105 printf ("VARIABLE %d, delta %d", value->value.variable.variable, value->value.variable.delta);
106 break;
107 case MONO_PHI_SUMMARIZED_VALUE: {
108 int phi;
109 printf ("PHI (");
110 for (phi = 0; phi < value->value.phi.number_of_alternatives; phi++) {
111 if (phi) printf (",");
112 printf ("%d", value->value.phi.phi_alternatives [phi]);
113 }
114 printf (")");
115 break;
116 }
117 default:
118 g_assert_not_reached ();
119 }
120 }
121
122 static void
123 print_summarized_value_relation (MonoSummarizedValueRelation *relation) {
124 printf ("Relation ");
125 print_relation (relation->relation);
126 printf (" with value ");
127 print_summarized_value (&(relation->related_value));
128 }
129
130 #if 0
131 static void
132 print_summarized_value_relation_chain (MonoSummarizedValueRelation *relation) {
133 printf ("Relations:\n");
134 while (relation) {
135 print_summarized_value_relation (relation);
136 printf ("\n");
137 relation = relation->next;
138 }
139 }
140 #endif
141
142 static void
143 print_evaluation_context_status (MonoRelationsEvaluationStatus status) {
144 if (status == MONO_RELATIONS_EVALUATION_NOT_STARTED) {
145 printf ("EVALUATION_NOT_STARTED");
146 } else {
147 gboolean print_or = FALSE;
148
149 printf ("(");
150 if (status & MONO_RELATIONS_EVALUATION_IN_PROGRESS) {
151 if (print_or) printf ("|");
152 printf ("EVALUATION_IN_PROGRESS");
153 print_or = TRUE;
154 }
155 if (status & MONO_RELATIONS_EVALUATION_COMPLETED) {
156 if (print_or) printf ("|");
157 printf ("EVALUATION_COMPLETED");
158 print_or = TRUE;
159 }
160 if (status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING) {
161 if (print_or) printf ("|");
162 printf ("RECURSIVELY_ASCENDING");
163 print_or = TRUE;
164 }
165 if (status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING) {
166 if (print_or) printf ("|");
167 printf ("RECURSIVELY_DESCENDING");
168 print_or = TRUE;
169 }
170 if (status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE) {
171 if (print_or) printf ("|");
172 printf ("RECURSIVELY_INDEFINITE");
173 print_or = TRUE;
174 }
175 printf (")");
176 }
177 }
178
179
180 static void
181 print_evaluation_context_ranges (MonoRelationsEvaluationRanges *ranges) {
182 printf ("(ranges: zero [%d,%d], variable [%d,%d])", ranges->zero.lower, ranges->zero.upper, ranges->variable.lower, ranges->variable.upper);
183 }
184
185 static void
186 print_evaluation_context (MonoRelationsEvaluationContext *context) {
187 printf ("Context status: ");
188 print_evaluation_context_status (context->status);
189 if (context->status & (MONO_RELATIONS_EVALUATION_IN_PROGRESS|MONO_RELATIONS_EVALUATION_COMPLETED)) {
190 print_evaluation_context_ranges (&(context->ranges));
191 }
192 printf ("\n");
193 }
194
195 #if 0
196 static void
197 print_evaluation_area (MonoVariableRelationsEvaluationArea *area) {
198 int i;
199 printf ("Dump of evaluation area (%d variables):\n", area->cfg->num_varinfo);
200 for (i = 0; i < area->cfg->num_varinfo; i++) {
201 printf ("Variable %d: ", i);
202 print_evaluation_context (&(area->contexts [i]));
203 print_summarized_value_relation_chain (&(area->relations [i]));
204 }
205 }
206
207 static void
208 print_evaluation_area_contexts (MonoVariableRelationsEvaluationArea *area) {
209 int i;
210 printf ("Dump of evaluation area contexts (%d variables):\n", area->cfg->num_varinfo);
211 for (i = 0; i < area->cfg->num_varinfo; i++) {
212 printf ("Variable %d: ", i);
213 print_evaluation_context (&(area->contexts [i]));
214 }
215 }
216 #endif
217
218 /*
219 * Check if the delta of an integer variable value is safe with respect
220 * to the variable size in bytes and its kind (signed or unsigned).
221 * If the delta is not safe, make the value an "any".
222 */
223 static G_GNUC_UNUSED void
224 check_delta_safety (MonoVariableRelationsEvaluationArea *area, MonoSummarizedValue *value) {
225 if (value->type == MONO_VARIABLE_SUMMARIZED_VALUE) {
226 int variable = value->value.variable.variable;
227 int delta = value->value.variable.delta;
228 if ((area->variable_value_kind [variable]) & MONO_UNSIGNED_VALUE_FLAG) {
229 if (delta < 0) {
230 MAKE_VALUE_ANY (*value);
231 }
232 } else {
233 if (((area->variable_value_kind [variable]) & MONO_INTEGER_VALUE_SIZE_BITMASK) < 4) {
234 MAKE_VALUE_ANY (*value);
235 } else if (delta > 16) {
236 MAKE_VALUE_ANY (*value);
237 }
238 }
239 }
240 }
241
242 /*
243 * get_relation_from_ins:
244 *
245 * Obtain relations from a MonoInst.
246 *
247 * result_value_kind: the "expected" kind of result;
248 * result: the "summarized" value
249 * returns the "actual" kind of result, if guessable (otherwise MONO_UNKNOWN_INTEGER_VALUE)
250 */
251 static MonoIntegerValueKind
252 get_relation_from_ins (MonoVariableRelationsEvaluationArea *area, MonoInst *ins, MonoSummarizedValueRelation *result, MonoIntegerValueKind result_value_kind)
253 {
254 MonoIntegerValueKind value_kind;
255 MonoSummarizedValue *value = &result->related_value;
256
257 if (ins->type == STACK_I8) {
258 value_kind = MONO_INTEGER_VALUE_SIZE_8;
259 } else if (ins->type == STACK_I4) {
260 value_kind = MONO_INTEGER_VALUE_SIZE_4;
261 } else {
262 value_kind = MONO_UNKNOWN_INTEGER_VALUE;
263 }
264
265 result->relation = MONO_EQ_RELATION;
266 MAKE_VALUE_ANY (*value);
267
268 switch (ins->opcode) {
269 case OP_ICONST:
270 value->type = MONO_CONSTANT_SUMMARIZED_VALUE;
271 value->value.constant.value = ins->inst_c0;
272 break;
273 case OP_MOVE:
274 value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
275 value->value.variable.variable = ins->sreg1;
276 value->value.variable.delta = 0;
277 break;
278 case OP_PHI:
279 value->type = MONO_PHI_SUMMARIZED_VALUE;
280 value->value.phi.number_of_alternatives = *(ins->inst_phi_args);
281 value->value.phi.phi_alternatives = ins->inst_phi_args + 1;
282 break;
283 case OP_IADD_IMM:
284 value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
285 value->value.variable.variable = ins->sreg1;
286 value->value.variable.delta = ins->inst_imm;
287 /* FIXME: */
288 //check_delta_safety (area, result);
289 break;
290 case OP_ISUB_IMM:
291 value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
292 value->value.variable.variable = ins->sreg1;
293 value->value.variable.delta = ins->inst_imm;
294 /* FIXME: */
295 //check_delta_safety (area, result);
296 break;
297 case OP_IREM_UN:
298 /* The result of an unsigned remainder is 0 < x < the divisor */
299 result->relation = MONO_LT_RELATION;
300 value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
301 value->value.variable.variable = ins->sreg2;
302 value->value.variable.delta = 0;
303 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_4;
304 break;
305 case OP_LDLEN:
306 /*
307 * We represent arrays by their length, so r1<-ldlen r2 is stored
308 * as r1 == r2 in the evaluation graph.
309 */
310 value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
311 value->value.variable.variable = ins->sreg1;
312 value->value.variable.delta = 0;
313 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_4;
314 break;
315 case OP_NEWARR:
316 value->type = MONO_VARIABLE_SUMMARIZED_VALUE;
317 value->value.variable.variable = ins->sreg1;
318 value->value.variable.delta = 0;
319 area->defs [ins->dreg] = ins;
320 break;
321
322 /* FIXME: Add more opcodes */
323 default:
324 /* These opcodes are not currently handled while running SciMark, first
325 * column is the number of times the warning was shown:
326 *
327 * 1 add_imm
328 * 1 float_conv_to_i8
329 * 1 int_mul_ovf_un
330 * 1 int_neg
331 * 1 int_or
332 * 1 int_shr_un
333 * 1 localloc
334 * 1 long_ceq
335 * 1 long_rem
336 * 1 long_sub
337 * 2 int_ceq
338 * 2 int_conv_to_i2
339 * 2 int_min
340 * 2 lcall
341 * 2 long_div
342 * 3 int_conv_to_u2
343 * 3 long_shr_imm
344 * 4 int_rem
345 * 4 int_rem_imm
346 * 4 loadi1_membase
347 * 4 loadu4_membase
348 * 5 int_div
349 * 5 shl_imm
350 * 6 int_div_imm
351 * 6 int_mul
352 * 9 int_mul_imm
353 * 9 zext_i4
354 * 10 int_shr_imm
355 * 12 int_shr_un_imm
356 * 12 long_add_imm
357 * 12 outarg_vtretaddr
358 * 12 strlen
359 * 13 int_or_imm
360 * 23 call_membase
361 * 23 int_conv_to_u1
362 * 23 long_add
363 * 24 int_and_imm
364 * 24 int_shl_imm
365 * 24 loadu2_membase
366 * 29 loadi8_membase
367 * 31 llvm_outarg_vt
368 * 34 int_sub
369 * 34 loadu1_membase
370 * 42 int_add
371 * 85 ldaddr
372 * 116 loadi4_membase
373 * 159 x86_lea
374 * 179 sext_i4
375 * 291 load_membase
376 * 462 i8const
377 * 472 call
378 */
379
380 break;
381 }
382 return value_kind;
383 }
384
385 static MonoValueRelation
386 get_relation_from_branch_instruction (MonoInst *ins)
387 {
388 if (MONO_IS_COND_BRANCH_OP (ins)) {
389 CompRelation rel = mono_opcode_to_cond (ins->opcode);
390
391 switch (rel) {
392 case CMP_EQ:
393 return MONO_EQ_RELATION;
394 case CMP_NE:
395 return MONO_NE_RELATION;
396 case CMP_LE:
397 case CMP_LE_UN:
398 return MONO_LE_RELATION;
399 case CMP_GE:
400 case CMP_GE_UN:
401 return MONO_GE_RELATION;
402 case CMP_LT:
403 case CMP_LT_UN:
404 return MONO_LT_RELATION;
405 case CMP_GT:
406 case CMP_GT_UN:
407 return MONO_GT_RELATION;
408 default:
409 g_assert_not_reached ();
410 return MONO_ANY_RELATION;
411 }
412 } else {
413 return MONO_ANY_RELATION;
414 }
415 }
416
417 /*
418 * Given a BB, find its entry condition and put its relations in a
419 * "MonoAdditionalVariableRelationsForBB" structure.
420 * bb: the BB
421 * relations: the resulting relations (entry condition of the given BB)
422 */
423 static void
424 get_relations_from_previous_bb (MonoVariableRelationsEvaluationArea *area, MonoBasicBlock *bb, MonoAdditionalVariableRelationsForBB *relations)
425 {
426 MonoBasicBlock *in_bb;
427 MonoInst *ins, *compare, *branch;
428 MonoValueRelation branch_relation;
429 MonoValueRelation symmetric_relation;
430 gboolean code_path;
431
432 INITIALIZE_VALUE_RELATION (&(relations->relation1.relation));
433 relations->relation1.relation.relation_is_static_definition = FALSE;
434 relations->relation1.relation.next = NULL;
435 relations->relation1.insertion_point = NULL;
436 relations->relation1.variable = -1;
437 INITIALIZE_VALUE_RELATION (&(relations->relation2.relation));
438 relations->relation2.relation.relation_is_static_definition = FALSE;
439 relations->relation2.relation.next = NULL;
440 relations->relation2.insertion_point = NULL;
441 relations->relation2.variable = -1;
442
443 if (bb->in_count == 1) { /* Should write the code to "sum" conditions... */
444 in_bb = bb->in_bb [0];
445
446 if ((in_bb->last_ins == NULL) || (in_bb->code == in_bb->last_ins))
447 return;
448
449 for (ins = in_bb->code; ins->next != in_bb->last_ins; ins = ins->next)
450 ;
451
452 compare = ins;
453 branch = ins->next;
454 branch_relation = get_relation_from_branch_instruction (branch);
455
456 if (branch_relation != MONO_ANY_RELATION) {
457 if (branch->inst_true_bb == bb) {
458 code_path = TRUE;
459 } else if (branch->inst_false_bb == bb) {
460 code_path = FALSE;
461 } else {
462 code_path = TRUE;
463 g_assert_not_reached ();
464 }
465 if (!code_path)
466 branch_relation = MONO_NEGATED_RELATION (branch_relation);
467 symmetric_relation = MONO_SYMMETRIC_RELATION (branch_relation);
468
469 /* FIXME: Other compare opcodes */
470 if (compare->opcode == OP_ICOMPARE) {
471 relations->relation1.variable = compare->sreg1;
472 relations->relation1.relation.relation = branch_relation;
473 relations->relation1.relation.related_value.type = MONO_VARIABLE_SUMMARIZED_VALUE;
474 relations->relation1.relation.related_value.value.variable.variable = compare->sreg2;
475 relations->relation1.relation.related_value.value.variable.delta = 0;
476
477 relations->relation2.variable = compare->sreg2;
478 relations->relation2.relation.relation = symmetric_relation;
479 relations->relation2.relation.related_value.type = MONO_VARIABLE_SUMMARIZED_VALUE;
480 relations->relation2.relation.related_value.value.variable.variable = compare->sreg1;
481 relations->relation2.relation.related_value.value.variable.delta = 0;
482 } else if (compare->opcode == OP_ICOMPARE_IMM) {
483 relations->relation1.variable = compare->sreg1;
484 relations->relation1.relation.relation = branch_relation;
485 relations->relation1.relation.related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE;
486 relations->relation1.relation.related_value.value.constant.value = compare->inst_imm;
487 }
488 }
489 }
490 }
491
492 /*
493 * Add the given relations to the evaluation area.
494 * area: the evaluation area
495 * change: the relations that must be added
496 */
497 static void
498 apply_change_to_evaluation_area (MonoVariableRelationsEvaluationArea *area, MonoAdditionalVariableRelation *change)
499 {
500 MonoSummarizedValueRelation *base_relation;
501
502 if (change->relation.relation != MONO_ANY_RELATION) {
503 base_relation = &(area->relations [change->variable]);
504 while ((base_relation->next != NULL) && (base_relation->next->relation_is_static_definition)) {
505 base_relation = base_relation->next;
506 }
507 change->insertion_point = base_relation;
508 change->relation.next = base_relation->next;
509 base_relation->next = &(change->relation);
510 }
511 }
512
513 /*
514 * Remove the given relation from the evaluation area.
515 * change: the relation that must be removed
516 */
517 static void
518 remove_change_from_evaluation_area (MonoAdditionalVariableRelation *change)
519 {
520 if (change->insertion_point != NULL) {
521 change->insertion_point->next = change->relation.next;
522 change->relation.next = NULL;
523 }
524 }
525
526
527 static void
528 clean_contexts (MonoRelationsEvaluationContext *contexts, int number)
529 {
530 int i;
531 for (i = 0; i < number; i++) {
532 contexts [i].status = MONO_RELATIONS_EVALUATION_NOT_STARTED;
533 }
534 }
535
536
537 /*
538 * Perform the intersection of a range and a constant value (taking into
539 * account the relation that the value has with the range).
540 * range: the range that will be intersected with the value
541 * value: the value that will be intersected with the range
542 * relation: the relation between the range and the value
543 */
544 static void
545 intersect_value( MonoRelationsEvaluationRange *range, int value, MonoValueRelation relation )
546 {
547 switch (relation) {
548 case MONO_NO_RELATION:
549 MONO_MAKE_RELATIONS_EVALUATION_RANGE_IMPOSSIBLE (*range);
550 break;
551 case MONO_ANY_RELATION:
552 break;
553 case MONO_EQ_RELATION:
554 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, value);
555 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, value);
556 break;
557 case MONO_NE_RELATION: {
558 /* IMPROVEMENT Figure this out! (ignoring it is safe anyway) */
559 break;
560 }
561 case MONO_LT_RELATION:
562 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (value));
563 break;
564 case MONO_LE_RELATION:
565 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, value);
566 break;
567 case MONO_GT_RELATION:
568 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (value));
569 break;
570 case MONO_GE_RELATION:
571 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, value);
572 break;
573 default:
574 g_assert_not_reached();
575 }
576 }
577
578
579 /*
580 * Perform the intersection of two pairs of ranges (taking into account the
581 * relation between the ranges and a given delta).
582 * ranges: the ranges that will be intersected
583 * other_ranges the other ranges that will be intersected
584 * delta: the delta between the pairs of ranges
585 * relation: the relation between the pairs of ranges
586 */
587 static void
588 intersect_ranges( MonoRelationsEvaluationRanges *ranges, MonoRelationsEvaluationRanges *other_ranges, int delta, MonoValueRelation relation )
589 {
590 if (delta == 0) {
591 switch (relation) {
592 case MONO_NO_RELATION:
593 MONO_MAKE_RELATIONS_EVALUATION_RANGES_IMPOSSIBLE (*ranges);
594 break;
595 case MONO_ANY_RELATION:
596 break;
597 case MONO_EQ_RELATION:
598 MONO_RELATIONS_EVALUATION_RANGES_INTERSECTION (*ranges, *other_ranges);
599 break;
600 case MONO_NE_RELATION: {
601 /* FIXME Figure this out! (ignoring it is safe anyway) */
602 break;
603 }
604 case MONO_LT_RELATION:
605 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->zero.upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->zero.upper));
606 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->variable.upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->variable.upper));
607 break;
608 case MONO_LE_RELATION:
609 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->zero.upper, other_ranges->zero.upper);
610 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->variable.upper, other_ranges->variable.upper);
611 break;
612 case MONO_GT_RELATION:
613 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->zero.lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->zero.lower));
614 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->variable.lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->variable.lower));
615 break;
616 case MONO_GE_RELATION:
617 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->zero.lower, other_ranges->zero.lower);
618 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->variable.lower, other_ranges->variable.lower);
619 break;
620 default:
621 g_assert_not_reached();
622 }
623 } else {
624 MonoRelationsEvaluationRanges translated_ranges = *other_ranges;
625 MONO_ADD_DELTA_SAFELY_TO_RANGES (translated_ranges, delta);
626 intersect_ranges( ranges, &translated_ranges, FALSE, relation );
627 }
628 }
629
630 /*
631 * Recursive method that traverses the relation graph to evaluate the
632 * relation between two variables.
633 * At the end of the execution, the resulting ranges are in the context of
634 * the "starting" variable.
635 * area: the current evaluation area (it contains the relation graph and
636 * memory for all the evaluation contexts is already allocated)
637 * variable: starting variable (the value ranges in its context are the result
638 * of the execution of this procedure)
639 * target_variable: the variable with respect to which the starting variable
640 * is evaluated (tipically the starting variable is the index
641 * and the target one is the array (which means its length))
642 * father_context: the previous evaluation context in recursive invocations
643 * (or NULL for the first invocation)
644 */
645 static void
646 evaluate_relation_with_target_variable (MonoVariableRelationsEvaluationArea *area, int variable, int target_variable, MonoRelationsEvaluationContext *father_context)
647 {
648 MonoRelationsEvaluationContext *context = &(area->contexts [variable]);
649
650 // First of all, we check the evaluation status
651 // (what must be done is *very* different in each case)
652 switch (context->status) {
653 case MONO_RELATIONS_EVALUATION_NOT_STARTED: {
654 MonoSummarizedValueRelation *relation = &(area->relations [variable]);
655
656 if (TRACE_ABC_REMOVAL) {
657 printf ("Evaluating variable %d (target variable %d)\n", variable, target_variable);
658 print_summarized_value_relation (relation);
659 printf ("\n");
660 }
661
662 // We properly inizialize the context
663 context->status = MONO_RELATIONS_EVALUATION_IN_PROGRESS;
664 context->father = father_context;
665 MONO_MAKE_RELATIONS_EVALUATION_RANGES_WEAK (context->ranges);
666
667 // If we have found the target variable, we can set the range
668 // related to it in the context to "equal" (which is [0,0])
669 if (variable == target_variable) {
670 if (TRACE_ABC_REMOVAL) {
671 printf ("Target variable reached (%d), continuing to evaluate relations with constants\n", variable);
672 }
673 context->ranges.variable.lower = 0;
674 context->ranges.variable.upper = 0;
675 }
676
677 // Examine all relations for this variable (scan the list)
678 // The contribute of each relation will be intersected (logical and)
679 while (relation != NULL) {
680 context->current_relation = relation;
681
682 if (TRACE_ABC_REMOVAL) {
683 printf ("Processing (%d): ", variable);
684 print_summarized_value_relation (relation);
685 printf ("\n");
686 }
687
688 // We decie what to do according the the type of the related value
689 switch (relation->related_value.type) {
690 case MONO_ANY_SUMMARIZED_VALUE:
691 // No added information, skip it
692 break;
693 case MONO_CONSTANT_SUMMARIZED_VALUE:
694 // Intersect range with constant (taking into account the relation)
695 intersect_value (&(context->ranges.zero), relation->related_value.value.constant.value, relation->relation);
696 break;
697 case MONO_VARIABLE_SUMMARIZED_VALUE:
698 // Generally, evaluate related variable and intersect ranges.
699 // However, some check is necessary...
700
701 // If the relation is "ANY", nothing to do (no added information)
702 if (relation->relation != MONO_ANY_RELATION) {
703 int related_variable = relation->related_value.value.variable.variable;
704 MonoRelationsEvaluationContext *related_context = &(area->contexts [related_variable]);
705
706 // The second condition in the "or" avoids messing with "back edges" in the graph traversal
707 // (they are simply ignored instead of triggering the handling of recursion)
708 if ( (related_context->status == MONO_RELATIONS_EVALUATION_NOT_STARTED) || !
709 ((related_context->current_relation->related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) &&
710 (related_context->current_relation->related_value.value.variable.variable == variable))) {
711 // Evaluate the related variable
712 evaluate_relation_with_target_variable (area, related_variable, target_variable, context);
713
714 // Check if we are part of a recursive loop
715 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) {
716 if (TRACE_ABC_REMOVAL) {
717 printf ("Recursivity detected for variable %d (target variable %d), status ", variable, target_variable);
718 print_evaluation_context_status (context->status);
719 }
720
721 // If we are, check if the evaluation of the related variable is complete
722 if (related_context->status == MONO_RELATIONS_EVALUATION_COMPLETED) {
723 // If it is complete, we are part of a recursive definition.
724 // Since it is a *definition* (and definitions are evaluated *before*
725 // conditions because they are first in the list), intersection is not
726 // strictly necessary, we simply copy the ranges and apply the delta
727 context->ranges = related_context->ranges;
728 /* Delta has already been checked for over/under-flow when evaluating values */
729 MONO_ADD_DELTA_SAFELY_TO_RANGES (context->ranges, relation->related_value.value.variable.delta);
730 context->status = MONO_RELATIONS_EVALUATION_COMPLETED;
731 if (TRACE_ABC_REMOVAL) {
732 printf (", ranges already computed, result: \n");
733 print_evaluation_context_ranges (&(context->ranges));
734 printf (" (delta is %d)\n", relation->related_value.value.variable.delta);
735 }
736 } else {
737 // If it is not complete, do nothing (we do not have enough information)
738 if (TRACE_ABC_REMOVAL) {
739 printf (", ranges not computed\n");
740 }
741 }
742 } else {
743 // If we are not (the common case) intersect the result
744 intersect_ranges( &(context->ranges), &(related_context->ranges), relation->related_value.value.variable.delta, relation->relation );
745 }
746 } else {
747 if (TRACE_ABC_REMOVAL) {
748 printf ("Relation is a back-edge in this traversal, skipping\n");
749 }
750 }
751 }
752 break;
753 case MONO_PHI_SUMMARIZED_VALUE: {
754 // We must compute all PHI alternatives, combining the results (with a union, which is a logical "or"),
755 // and intersect this result with the ranges in the context; we must also take into account recursions
756 // (with loops that can be ascending, descending, or indefinite)
757 MonoRelationsEvaluationRanges phi_ranges;
758 int phi;
759 gboolean is_ascending = FALSE;
760 gboolean is_descending = FALSE;
761
762 MONO_MAKE_RELATIONS_EVALUATION_RANGES_IMPOSSIBLE (phi_ranges);
763 for (phi = 0; phi < relation->related_value.value.phi.number_of_alternatives; phi++) {
764 int phi_alternative = relation->related_value.value.phi.phi_alternatives [phi];
765 evaluate_relation_with_target_variable (area, phi_alternative, target_variable, context);
766
767 // This means we are part of a recursive loop
768 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) {
769 if (TRACE_ABC_REMOVAL) {
770 printf ("Recursivity detected for variable %d (target variable %d), status ", variable, target_variable);
771 print_evaluation_context_status (context->status);
772 printf ("\n");
773 }
774 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING) {
775 is_ascending = TRUE;
776 }
777 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING) {
778 is_descending = TRUE;
779 }
780 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE) {
781 is_ascending = TRUE;
782 is_descending = TRUE;
783 }
784
785 // Clear "recursivity" bits in the status (recursion has been handled)
786 context->status = MONO_RELATIONS_EVALUATION_IN_PROGRESS;
787 } else {
788 MONO_RELATIONS_EVALUATION_RANGES_UNION (phi_ranges, area->contexts [phi_alternative].ranges);
789 }
790 }
791
792 // Apply the effects of all recursive loops
793 if (is_ascending) {
794 phi_ranges.zero.upper = INT_MAX;
795 phi_ranges.variable.upper = INT_MAX;
796 }
797 if (is_descending) {
798 phi_ranges.zero.lower = INT_MIN;
799 phi_ranges.variable.lower = INT_MIN;
800 }
801
802 // Intersect final result
803 MONO_RELATIONS_EVALUATION_RANGES_INTERSECTION (context->ranges, phi_ranges);
804 break;
805 }
806 default:
807 g_assert_not_reached();
808 }
809
810 // Pass to next relation
811 relation = relation->next;
812 }
813
814 // Check if any recursivity bits are still in the status, and in any case clear them
815 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) {
816 if (TRACE_ABC_REMOVAL) {
817 printf ("Recursivity for variable %d (target variable %d) discards computation, status ", variable, target_variable);
818 print_evaluation_context_status (context->status);
819 printf ("\n");
820 }
821 // If yes, we did not have enough information (most likely we were evaluated inside a PHI, but we also
822 // depended on the same PHI, which was still in evaluation...), so clear the status to "NOT_STARTED"
823 // (if we will be evaluated again, the PHI will be already done, so our evaluation will succeed)
824 context->status = MONO_RELATIONS_EVALUATION_NOT_STARTED;
825 } else {
826 if (TRACE_ABC_REMOVAL) {
827 printf ("Ranges for variable %d (target variable %d) computed: ", variable, target_variable);
828 print_evaluation_context_ranges (&(context->ranges));
829 printf ("\n");
830 }
831 // If not (the common case) the evaluation is complete, and the result is in the context
832 context->status = MONO_RELATIONS_EVALUATION_COMPLETED;
833 }
834 break;
835 }
836 case MONO_RELATIONS_EVALUATION_IN_PROGRESS: {
837 // This means we are in a recursive loop
838 MonoRelationsEvaluationContext *current_context = father_context;
839 MonoRelationsEvaluationContext *last_context = context->father;
840 gboolean evaluation_can_be_recursive = TRUE;
841 gboolean evaluation_is_definition = TRUE;
842 int path_value = 0;
843
844 if (TRACE_ABC_REMOVAL) {
845 printf ("Evaluation of variable %d (target variable %d) already in progress\n", variable, target_variable);
846 print_evaluation_context (context);
847 print_summarized_value_relation (context->current_relation);
848 printf ("\n");
849 }
850
851 // We must check if the loop can be a recursive definition (we scan the whole loop)
852 while (current_context != last_context) {
853 if (current_context == NULL) {
854 printf ("Broken recursive ring in ABC removal\n");
855 g_assert_not_reached ();
856 }
857
858 if (current_context->current_relation->relation_is_static_definition) {
859 if (current_context->current_relation->related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
860 /* No need to check path_value for over/under-flow, since delta should be safe */
861 path_value += current_context->current_relation->related_value.value.variable.delta;
862 } else if (current_context->current_relation->related_value.type != MONO_PHI_SUMMARIZED_VALUE) {
863 evaluation_can_be_recursive = FALSE;
864 }
865 } else {
866 evaluation_is_definition = FALSE;
867 evaluation_can_be_recursive = FALSE;
868 }
869
870 current_context = current_context->father;
871 }
872
873 // If this is a recursive definition, we properly flag the status in all the involved contexts
874 if (evaluation_is_definition) {
875 MonoRelationsEvaluationStatus recursive_status;
876 if (evaluation_can_be_recursive) {
877 if (path_value > 0) {
878 recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING;
879 } else if (path_value < 0) {
880 recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING;
881 } else {
882 recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE;
883 }
884 } else {
885 recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE;
886 }
887
888 if (TRACE_ABC_REMOVAL) {
889 printf ("Recursivity accepted (");
890 print_evaluation_context_status (recursive_status);
891 printf (")\n");
892 }
893
894 current_context = father_context;
895 while (current_context != last_context) {
896 current_context->status |= recursive_status;
897 current_context = current_context->father;
898 }
899 } else {
900 if (TRACE_ABC_REMOVAL) {
901 printf ("Recursivity rejected (some relation in the cycle is not a defintion)\n");
902 }
903 }
904 break;
905 }
906 case MONO_RELATIONS_EVALUATION_COMPLETED: {
907 return;
908 }
909 default:
910 if (TRACE_ABC_REMOVAL) {
911 printf ("Variable %d (target variable %d) already in a recursive ring, skipping\n", variable, target_variable);
912 print_evaluation_context (context);
913 print_summarized_value_relation (context->current_relation);
914 printf ("\n");
915 }
916 break;
917 }
918
919 }
920
921 /*
922 * Apply the given value kind to the given range
923 */
924 static void
925 apply_value_kind_to_range (MonoRelationsEvaluationRange *range, MonoIntegerValueKind value_kind)
926 {
927 if (value_kind != MONO_UNKNOWN_INTEGER_VALUE) {
928 if (value_kind & MONO_UNSIGNED_VALUE_FLAG) {
929 if (range->lower < 0) {
930 range->lower = 0;
931 }
932 if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 1) {
933 if (range->upper > 0xff) {
934 range->upper = 0xff;
935 }
936 } else if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 2) {
937 if (range->upper > 0xffff) {
938 range->upper = 0xffff;
939 }
940 }
941 } else {
942 if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 1) {
943 if (range->lower < -0x80) {
944 range->lower = -0x80;
945 }
946 if (range->upper > 0x7f) {
947 range->upper = 0x7f;
948 }
949 } else if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 2) {
950 if (range->lower < -0x8000) {
951 range->lower = -0x8000;
952 }
953 if (range->upper > 0x7fff) {
954 range->upper = 0x7fff;
955 }
956 }
957 }
958 }
959 }
960
961 /*
962 * Attempt the removal of bounds checks from a MonoInst.
963 * inst: the MonoInst
964 * area: the current evaluation area (it contains the relation graph and
965 * memory for all the evaluation contexts is already allocated)
966 */
967 static void
968 remove_abc_from_inst (MonoInst *ins, MonoVariableRelationsEvaluationArea *area)
969 {
970 /* FIXME: Add support for 'constant' arrays and constant indexes */
971
972 int array_variable = ins->sreg1;
973 int index_variable = ins->sreg2;
974 MonoRelationsEvaluationContext *array_context = &(area->contexts [array_variable]);
975 MonoRelationsEvaluationContext *index_context = &(area->contexts [index_variable]);
976
977 clean_contexts (area->contexts, area->cfg->next_vreg);
978
979 evaluate_relation_with_target_variable (area, index_variable, array_variable, NULL);
980 evaluate_relation_with_target_variable (area, array_variable, array_variable, NULL);
981
982 if ((index_context->ranges.zero.lower >=0) && ((index_context->ranges.variable.upper < 0)||(index_context->ranges.zero.upper < array_context->ranges.zero.lower))) {
983 if (REPORT_ABC_REMOVAL) {
984 printf ("ARRAY-ACCESS: removed bounds check on array %d with index %d\n",
985 array_variable, index_variable);
986 NULLIFY_INS (ins);
987 }
988 } else {
989 if (TRACE_ABC_REMOVAL) {
990 if (index_context->ranges.zero.lower >= 0) {
991 printf ("ARRAY-ACCESS: Removed lower bound check on array %d with index %d\n", array_variable, index_variable);
992 }
993 if (index_context->ranges.variable.upper < 0) {
994 printf ("ARRAY-ACCESS: Removed upper bound check (through variable) on array %d with index %d\n", array_variable, index_variable);
995 }
996 if (index_context->ranges.zero.upper < array_context->ranges.zero.lower) {
997 printf ("ARRAY-ACCESS: Removed upper bound check (through constant) on array %d with index %d\n", array_variable, index_variable);
998 }
999 }
1000 }
1001 }
1002
1003 static gboolean
1004 eval_non_null (MonoVariableRelationsEvaluationArea *area, int reg)
1005 {
1006 MonoRelationsEvaluationContext *context = &(area->contexts [reg]);
1007
1008 clean_contexts (area->contexts, area->cfg->next_vreg);
1009 evaluate_relation_with_target_variable (area, reg, reg, NULL);
1010
1011 return context->ranges.zero.lower > 0;
1012 }
1013
1014 static void
1015 add_non_null (MonoVariableRelationsEvaluationArea *area, MonoCompile *cfg, int reg,
1016 GSList **check_relations)
1017 {
1018 MonoAdditionalVariableRelation *rel;
1019
1020 rel = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoAdditionalVariableRelation));
1021 rel->variable = reg;
1022 rel->relation.relation = MONO_GT_RELATION;
1023 rel->relation.related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE;
1024 rel->relation.related_value.value.constant.value = 0;
1025
1026 apply_change_to_evaluation_area (area, rel);
1027
1028 *check_relations = g_slist_append_mempool (cfg->mempool, *check_relations, rel);
1029 }
1030
1031 /*
1032 * Process a BB removing bounds checks from array accesses.
1033 * It does the following (in sequence):
1034 * - Get the BB entry condition
1035 * - Add its relations to the relation graph in the evaluation area
1036 * - Process all the MonoInst trees in the BB
1037 * - Recursively process all the children BBs in the dominator tree
1038 * - Remove the relations previously added to the relation graph
1039 *
1040 * bb: the BB that must be processed
1041 * area: the current evaluation area (it contains the relation graph and
1042 * memory for all the evaluation contexts is already allocated)
1043 */
1044 static void
1045 process_block (MonoCompile *cfg, MonoBasicBlock *bb, MonoVariableRelationsEvaluationArea *area) {
1046 int inst_index;
1047 MonoInst *ins;
1048 MonoAdditionalVariableRelationsForBB additional_relations;
1049 GSList *dominated_bb, *l;
1050 GSList *check_relations = NULL;
1051
1052 if (TRACE_ABC_REMOVAL) {
1053 printf ("\nProcessing block %d [dfn %d]...\n", bb->block_num, bb->dfn);
1054 }
1055
1056 if (bb->region != -1)
1057 return;
1058
1059 get_relations_from_previous_bb (area, bb, &additional_relations);
1060 if (TRACE_ABC_REMOVAL) {
1061 if (additional_relations.relation1.relation.relation != MONO_ANY_RELATION) {
1062 printf ("Adding relation 1 on variable %d: ", additional_relations.relation1.variable);
1063 print_summarized_value_relation (&(additional_relations.relation1.relation));
1064 printf ("\n");
1065 }
1066 if (additional_relations.relation2.relation.relation != MONO_ANY_RELATION) {
1067 printf ("Adding relation 2 on variable %d: ", additional_relations.relation2.variable);
1068 print_summarized_value_relation (&(additional_relations.relation2.relation));
1069 printf ("\n");
1070 }
1071 }
1072 apply_change_to_evaluation_area (area, &(additional_relations.relation1));
1073 apply_change_to_evaluation_area (area, &(additional_relations.relation2));
1074
1075 inst_index = 0;
1076 for (ins = bb->code; ins; ins = ins->next) {
1077 MonoAdditionalVariableRelation *rel;
1078 int array_var, index_var;
1079
1080 if (TRACE_ABC_REMOVAL) {
1081 printf ("Processing instruction %d\n", inst_index);
1082 inst_index++;
1083 }
1084
1085 if (ins->opcode == OP_BOUNDS_CHECK) { /* Handle OP_LDELEMA2D, too */
1086 if (TRACE_ABC_REMOVAL) {
1087 printf ("Attempting check removal...\n");
1088 }
1089
1090 array_var = ins->sreg1;
1091 index_var = ins->sreg2;
1092
1093 remove_abc_from_inst (ins, area);
1094
1095 /* We can derive additional relations from the bounds check */
1096 if (ins->opcode != OP_NOP) {
1097 rel = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoAdditionalVariableRelation));
1098 rel->variable = index_var;
1099 rel->relation.relation = MONO_LT_RELATION;
1100 rel->relation.related_value.type = MONO_VARIABLE_SUMMARIZED_VALUE;
1101 rel->relation.related_value.value.variable.variable = array_var;
1102 rel->relation.related_value.value.variable.delta = 0;
1103
1104 apply_change_to_evaluation_area (area, rel);
1105
1106 check_relations = g_slist_append_mempool (cfg->mempool, check_relations, rel);
1107
1108 rel = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoAdditionalVariableRelation));
1109 rel->variable = index_var;
1110 rel->relation.relation = MONO_GE_RELATION;
1111 rel->relation.related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE;
1112 rel->relation.related_value.value.constant.value = 0;
1113
1114 apply_change_to_evaluation_area (area, rel);
1115
1116 check_relations = g_slist_append_mempool (cfg->mempool, check_relations, rel);
1117 }
1118 }
1119
1120 if (ins->opcode == OP_CHECK_THIS) {
1121 if (eval_non_null (area, ins->sreg1)) {
1122 if (REPORT_ABC_REMOVAL)
1123 printf ("ARRAY-ACCESS: removed check_this instruction.\n");
1124 NULLIFY_INS (ins);
1125 }
1126 }
1127
1128 if (ins->opcode == OP_NOT_NULL)
1129 add_non_null (area, cfg, ins->sreg1, &check_relations);
1130
1131 /*
1132 * FIXME: abcrem equates an array with its length,
1133 * so a = new int [100] implies a != null, but a = new int [0] doesn't.
1134 */
1135 /*
1136 * Eliminate MONO_INST_FAULT flags if possible.
1137 */
1138 if (COMPILE_LLVM (cfg) && (ins->opcode == OP_LDLEN ||
1139 ins->opcode == OP_BOUNDS_CHECK ||
1140 ins->opcode == OP_STRLEN ||
1141 (MONO_IS_LOAD_MEMBASE (ins) && (ins->flags & MONO_INST_FAULT)) ||
1142 (MONO_IS_STORE_MEMBASE (ins) && (ins->flags & MONO_INST_FAULT)))) {
1143 int reg;
1144
1145 if (MONO_IS_STORE_MEMBASE (ins))
1146 reg = ins->inst_destbasereg;
1147 else if (MONO_IS_LOAD_MEMBASE (ins))
1148 reg = ins->inst_basereg;
1149 else
1150 reg = ins->sreg1;
1151
1152 /*
1153 * This doesn't work because LLVM can move the non-faulting loads before the faulting
1154 * ones (test_0_llvm_moving_faulting_loads ()).
1155 * So only do it if we know the load cannot be moved before the instruction which ensures it is not
1156 * null (i.e. the def of its sreg).
1157 */
1158 if (area->defs [reg] && area->defs [reg]->opcode == OP_NEWARR) {
1159 if (REPORT_ABC_REMOVAL)
1160 printf ("ARRAY-ACCESS: removed MONO_INST_FAULT flag.\n");
1161 ins->flags &= ~MONO_INST_FAULT;
1162 }
1163 /*
1164 if (eval_non_null (area, reg)) {
1165 if (REPORT_ABC_REMOVAL)
1166 printf ("ARRAY-ACCESS: removed MONO_INST_FAULT flag.\n");
1167 ins->flags &= ~MONO_INST_FAULT;
1168 } else {
1169 add_non_null (area, cfg, reg, &check_relations);
1170 }
1171 */
1172 }
1173 }
1174
1175 if (TRACE_ABC_REMOVAL) {
1176 printf ("Processing block %d [dfn %d] done.\n", bb->block_num, bb->dfn);
1177 }
1178
1179 for (dominated_bb = bb->dominated; dominated_bb != NULL; dominated_bb = dominated_bb->next) {
1180 process_block (cfg, (MonoBasicBlock*) (dominated_bb->data), area);
1181 }
1182
1183 for (l = check_relations; l; l = l->next)
1184 remove_change_from_evaluation_area (l->data);
1185
1186 remove_change_from_evaluation_area (&(additional_relations.relation1));
1187 remove_change_from_evaluation_area (&(additional_relations.relation2));
1188 }
1189
1190 static MonoIntegerValueKind
1191 type_to_value_kind (MonoType *type)
1192 {
1193 if (type->byref)
1194 return MONO_UNKNOWN_INTEGER_VALUE;
1195 switch (type->type) {
1196 case MONO_TYPE_I1:
1197 return MONO_INTEGER_VALUE_SIZE_1;
1198 break;
1199 case MONO_TYPE_U1:
1200 return MONO_UNSIGNED_INTEGER_VALUE_SIZE_1;
1201 break;
1202 case MONO_TYPE_I2:
1203 return MONO_INTEGER_VALUE_SIZE_2;
1204 break;
1205 case MONO_TYPE_U2:
1206 return MONO_UNSIGNED_INTEGER_VALUE_SIZE_2;
1207 break;
1208 case MONO_TYPE_I4:
1209 return MONO_INTEGER_VALUE_SIZE_4;
1210 break;
1211 case MONO_TYPE_U4:
1212 return MONO_UNSIGNED_INTEGER_VALUE_SIZE_4;
1213 break;
1214 case MONO_TYPE_I:
1215 return SIZEOF_VOID_P;
1216 break;
1217 case MONO_TYPE_U:
1218 return (MONO_UNSIGNED_VALUE_FLAG|SIZEOF_VOID_P);
1219 break;
1220 case MONO_TYPE_I8:
1221 return MONO_INTEGER_VALUE_SIZE_8;
1222 break;
1223 case MONO_TYPE_U8:
1224 return MONO_UNSIGNED_INTEGER_VALUE_SIZE_8;
1225 default:
1226 return MONO_UNKNOWN_INTEGER_VALUE;
1227 }
1228 }
1229
1230 /**
1231 * mono_perform_abc_removal:
1232 * @cfg: Control Flow Graph
1233 *
1234 * Performs the ABC removal from a cfg in SSA form.
1235 * It does the following:
1236 * - Prepare the evaluation area
1237 * - Allocate memory for the relation graph in the evaluation area
1238 * (of course, only for variable definitions) and summarize there all
1239 * variable definitions
1240 * - Allocate memory for the evaluation contexts in the evaluation area
1241 * - Recursively process all the BBs in the dominator tree (it is enough
1242 * to invoke the processing on the entry BB)
1243 *
1244 * cfg: the method code
1245 */
1246 void
1247 mono_perform_abc_removal (MonoCompile *cfg)
1248 {
1249 MonoVariableRelationsEvaluationArea area;
1250 MonoBasicBlock *bb;
1251 int i;
1252
1253 verbose_level = cfg->verbose_level;
1254
1255 if (TRACE_ABC_REMOVAL) {
1256 printf ("\nRemoving array bound checks in %s\n", mono_method_full_name (cfg->method, TRUE));
1257 }
1258
1259 area.cfg = cfg;
1260 area.relations = (MonoSummarizedValueRelation *)
1261 mono_mempool_alloc (cfg->mempool, sizeof (MonoSummarizedValueRelation) * (cfg->next_vreg) * 2);
1262 area.contexts = (MonoRelationsEvaluationContext *)
1263 mono_mempool_alloc (cfg->mempool, sizeof (MonoRelationsEvaluationContext) * (cfg->next_vreg));
1264 area.variable_value_kind = (MonoIntegerValueKind *)
1265 mono_mempool_alloc (cfg->mempool, sizeof (MonoIntegerValueKind) * (cfg->next_vreg));
1266 area.defs = mono_mempool_alloc (cfg->mempool, sizeof (MonoInst*) * cfg->next_vreg);
1267 for (i = 0; i < cfg->next_vreg; i++) {
1268 area.variable_value_kind [i] = MONO_UNKNOWN_INTEGER_VALUE;
1269 area.relations [i].relation = MONO_EQ_RELATION;
1270 area.relations [i].relation_is_static_definition = TRUE;
1271 MAKE_VALUE_ANY (area.relations [i].related_value);
1272 area.relations [i].next = NULL;
1273 area.defs [i] = NULL;
1274 }
1275
1276 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
1277 MonoInst *ins;
1278
1279 if (TRACE_ABC_REMOVAL)
1280 printf ("\nABCREM BLOCK %d:\n", bb->block_num);
1281
1282 for (ins = bb->code; ins; ins = ins->next) {
1283 const char *spec = INS_INFO (ins->opcode);
1284
1285 if (spec [MONO_INST_DEST] == ' ' || MONO_IS_STORE_MEMBASE (ins))
1286 continue;
1287
1288 if (spec [MONO_INST_DEST] == 'i') {
1289 MonoIntegerValueKind effective_value_kind;
1290 MonoRelationsEvaluationRange range;
1291 MonoSummarizedValueRelation *type_relation;
1292 MonoInst *var;
1293
1294 if (TRACE_ABC_REMOVAL)
1295 mono_print_ins (ins);
1296
1297 var = get_vreg_to_inst (cfg, ins->dreg);
1298 if (var)
1299 area.variable_value_kind [ins->dreg] = type_to_value_kind (var->inst_vtype);
1300
1301 effective_value_kind = get_relation_from_ins (&area, ins, &area.relations [ins->dreg], area.variable_value_kind [ins->dreg]);
1302
1303 MONO_MAKE_RELATIONS_EVALUATION_RANGE_WEAK (range);
1304 apply_value_kind_to_range (&range, area.variable_value_kind [ins->dreg]);
1305 apply_value_kind_to_range (&range, effective_value_kind);
1306
1307 if (range.upper < INT_MAX) {
1308 type_relation = (MonoSummarizedValueRelation *) mono_mempool_alloc (cfg->mempool, sizeof (MonoSummarizedValueRelation));
1309 type_relation->relation = MONO_LE_RELATION;
1310 type_relation->related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE;
1311 type_relation->related_value.value.constant.value = range.upper;
1312 type_relation->relation_is_static_definition = TRUE;
1313 type_relation->next = area.relations [ins->dreg].next;
1314 area.relations [ins->dreg].next = type_relation;
1315 if (TRACE_ABC_REMOVAL) {
1316 printf ("[var%d <= %d]", ins->dreg, range.upper);
1317 }
1318 }
1319 if (range.lower > INT_MIN) {
1320 type_relation = (MonoSummarizedValueRelation *) mono_mempool_alloc (cfg->mempool, sizeof (MonoSummarizedValueRelation));
1321 type_relation->relation = MONO_GE_RELATION;
1322 type_relation->related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE;
1323 type_relation->related_value.value.constant.value = range.lower;
1324 type_relation->relation_is_static_definition = TRUE;
1325 type_relation->next = area.relations [ins->dreg].next;
1326 area.relations [ins->dreg].next = type_relation;
1327 if (TRACE_ABC_REMOVAL) {
1328 printf ("[var%d >= %d]", ins->dreg, range.lower);
1329 }
1330 }
1331 if (TRACE_ABC_REMOVAL) {
1332 printf ("Summarized variable %d: ", ins->dreg);
1333 print_summarized_value (&(area.relations [ins->dreg].related_value));
1334 printf ("\n");
1335 }
1336 }
1337 }
1338 }
1339
1340 /* Add symmetric relations */
1341 for (i = 0; i < cfg->next_vreg; i++) {
1342 if (area.relations [i].related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
1343 int related_index = cfg->next_vreg + i;
1344 int related_variable = area.relations [i].related_value.value.variable.variable;
1345
1346 area.relations [related_index].relation = MONO_EQ_RELATION;
1347 area.relations [related_index].relation_is_static_definition = TRUE;
1348 area.relations [related_index].related_value.type = MONO_VARIABLE_SUMMARIZED_VALUE;
1349 area.relations [related_index].related_value.value.variable.variable = i;
1350 area.relations [related_index].related_value.value.variable.delta = - area.relations [i].related_value.value.variable.delta;
1351
1352 area.relations [related_index].next = area.relations [related_variable].next;
1353 area.relations [related_variable].next = &(area.relations [related_index]);
1354
1355 if (TRACE_ABC_REMOVAL) {
1356 printf ("Added symmetric summarized value for variable variable %d (to %d): ", i, related_variable);
1357 print_summarized_value (&(area.relations [related_index].related_value));
1358 printf ("\n");
1359 }
1360 }
1361 }
1362
1363 process_block (cfg, cfg->bblocks [0], &area);
1364 }
1365
1366 #endif /* DISABLE_JIT */
Mirror of the official Mono project git repository