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