mono/mini/abcremoval.c

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