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