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