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