mono/mini/abcremoval.c

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