mono/mini/abcremoval.c

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