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