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