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 #include "inssel.h"
  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 /*
 216  * Given a MonoInst, if it is a store to a variable return the MonoInst that
 217  * represents the stored value.
 218  * If anything goes wrong, return NULL.
 219  * store: the MonoInst that should be a store
 220  * expected_variable_index: the variable where the value should be stored
 221  * return: either the stored value, or NULL
 222  */
 223 static MonoInst *
 224 get_variable_value_from_store_instruction (MonoInst *store, int expected_variable_index) {
 225         switch (store->opcode) {
 226         case CEE_STIND_REF:
 227         case CEE_STIND_I:
 228         case CEE_STIND_I4:
 229         case CEE_STIND_I1:
 230         case CEE_STIND_I2:
 231         case CEE_STIND_I8:
 232         case CEE_STIND_R4:
 233         case CEE_STIND_R8:
 234                 if (TRACE_ABC_REMOVAL) {
 235                         printf ("[store instruction found]");
 236                 }
 237                 if ((store->inst_left->opcode == OP_LOCAL) || (store->inst_left->opcode == OP_ARG)) {
 238                         int variable_index = store->inst_left->inst_c0;
 239                         if (TRACE_ABC_REMOVAL) {
 240                                 printf ("[value put in local %d (expected %d)]", variable_index, expected_variable_index);
 241                         }
 242                         if (variable_index == expected_variable_index) {
 243                                 return store->inst_right;
 244                         } else {
 245                                 return NULL;
 246                         }
 247                 }
 248                 else
 249                 {
 250                         return NULL;
 251                 }
 252                 break;
 253         default:
 254                 return NULL;
 255         }
 256 }
 257
 258 /*
 259  * Check if the delta of an integer variable value is safe with respect
 260  * to the variable size in bytes and its kind (signed or unsigned).
 261  * If the delta is not safe, make the value an "any".
 262  */
 263 static void
 264 check_delta_safety (MonoVariableRelationsEvaluationArea *area, MonoSummarizedValue *value) {
 265         if (value->type == MONO_VARIABLE_SUMMARIZED_VALUE) {
 266                 int variable = value->value.variable.variable;
 267                 int delta = value->value.variable.delta;
 268                 if ((area->variable_value_kind [variable]) & MONO_UNSIGNED_VALUE_FLAG) {
 269                         if (delta < 0) {
 270                                 MAKE_VALUE_ANY (*value);
 271                         }
 272                 } else {
 273                         if (((area->variable_value_kind [variable]) & MONO_INTEGER_VALUE_SIZE_BITMASK) < 4) {
 274                                 MAKE_VALUE_ANY (*value);
 275                         } else if (delta > 16) {
 276                                 MAKE_VALUE_ANY (*value);
 277                         }
 278                 }
 279         }
 280 }
 281
 282 /* Prototype, definition comes later */
 283 static void
 284 summarize_array_value (MonoVariableRelationsEvaluationArea *area, MonoInst *value, MonoSummarizedValue *result, gboolean is_array_type);
 285
 286 /*
 287  * Given a MonoInst representing an integer value, store it in "summarized" form.
 288  * result_value_kind: the "expected" kind of result;
 289  * result: the "summarized" value
 290  * returns the "actual" kind of result, if guessable (otherwise MONO_UNKNOWN_INTEGER_VALUE)
 291  */
 292 static MonoIntegerValueKind
 293 summarize_integer_value (MonoVariableRelationsEvaluationArea *area, MonoInst *value, MonoSummarizedValue *result, MonoIntegerValueKind result_value_kind) {
 294         MonoIntegerValueKind value_kind;
 295
 296         if (value->type == STACK_I8) {
 297                 value_kind = MONO_INTEGER_VALUE_SIZE_8;
 298         } else if (value->type == STACK_I4) {
 299                 value_kind = MONO_INTEGER_VALUE_SIZE_4;
 300         } else {
 301                 value_kind = MONO_UNKNOWN_INTEGER_VALUE;
 302         }
 303
 304         switch (value->opcode) {
 305         case OP_ICONST:
 306                 result->type = MONO_CONSTANT_SUMMARIZED_VALUE;
 307                 result->value.constant.value = value->inst_c0;
 308                 break;
 309         case OP_LOCAL:
 310         case OP_ARG:
 311                 result->type = MONO_VARIABLE_SUMMARIZED_VALUE;
 312                 result->value.variable.variable = value->inst_c0;
 313                 result->value.variable.delta = 0;
 314                 value_kind = area->variable_value_kind [value->inst_c0];
 315                 break;
 316         case CEE_LDIND_I1:
 317                 value_kind = MONO_INTEGER_VALUE_SIZE_1;
 318                 goto handle_load;
 319         case CEE_LDIND_U1:
 320                 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_1;
 321                 goto handle_load;
 322         case CEE_LDIND_I2:
 323                 value_kind = MONO_INTEGER_VALUE_SIZE_2;
 324                 goto handle_load;
 325         case CEE_LDIND_U2:
 326                 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_2;
 327                 goto handle_load;
 328         case CEE_LDIND_I4:
 329                 value_kind = MONO_INTEGER_VALUE_SIZE_4;
 330                 goto handle_load;
 331         case CEE_LDIND_U4:
 332                 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_4;
 333                 goto handle_load;
 334         case CEE_LDIND_I8:
 335                 value_kind = MONO_INTEGER_VALUE_SIZE_8;
 336                 goto handle_load;
 337         case CEE_LDIND_I:
 338                 value_kind = SIZEOF_VOID_P;
 339 handle_load:
 340                 if ((value->inst_left->opcode == OP_LOCAL) || (value->inst_left->opcode == OP_ARG)) {
 341                         value_kind = summarize_integer_value (area, value->inst_left, result, result_value_kind);
 342                 } else {
 343                         MAKE_VALUE_ANY (*result);
 344                 }
 345                 break;
 346         case CEE_ADD: {
 347                 MonoSummarizedValue left_value;
 348                 MonoSummarizedValue right_value;
 349                 summarize_integer_value (area, value->inst_left, &left_value, result_value_kind);
 350                 summarize_integer_value (area, value->inst_right, &right_value, result_value_kind);
 351
 352                 if (left_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
 353                         if (right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
 354                                 result->type = MONO_VARIABLE_SUMMARIZED_VALUE;
 355                                 result->value.variable.variable = left_value.value.variable.variable;
 356                                 result->value.variable.delta = left_value.value.variable.delta + right_value.value.constant.value;
 357                         } else {
 358                                 MAKE_VALUE_ANY (*result);
 359                         }
 360                 } else if (right_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
 361                         if (left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
 362                                 result->type = MONO_VARIABLE_SUMMARIZED_VALUE;
 363                                 result->value.variable.variable = right_value.value.variable.variable;
 364                                 result->value.variable.delta = left_value.value.constant.value + right_value.value.variable.delta;
 365                         } else {
 366                                 MAKE_VALUE_ANY (*result);
 367                         }
 368                 } else if ((right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) && (left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE)) {
 369                         /* This should not happen if constant folding has been done */
 370                         result->type = MONO_CONSTANT_SUMMARIZED_VALUE;
 371                         result->value.constant.value = left_value.value.constant.value + right_value.value.constant.value;
 372                 } else {
 373                         MAKE_VALUE_ANY (*result);
 374                 }
 375                 if (result->type == MONO_VARIABLE_SUMMARIZED_VALUE) {
 376                         check_delta_safety (area, result);
 377                 }
 378                 break;
 379         }
 380         case CEE_SUB: {
 381                 MonoSummarizedValue left_value;
 382                 MonoSummarizedValue right_value;
 383                 summarize_integer_value (area, value->inst_left, &left_value, result_value_kind);
 384                 summarize_integer_value (area, value->inst_right, &right_value, result_value_kind);
 385
 386                 if (left_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
 387                         if (right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
 388                                 result->type = MONO_VARIABLE_SUMMARIZED_VALUE;
 389                                 result->value.variable.variable = left_value.value.variable.variable;
 390                                 result->value.variable.delta = left_value.value.variable.delta - right_value.value.constant.value;
 391                         } else {
 392                                 MAKE_VALUE_ANY (*result);
 393                         }
 394                 } else if ((right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) && (left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE)) {
 395                         /* This should not happen if constant folding has been done */
 396                         result->type = MONO_CONSTANT_SUMMARIZED_VALUE;
 397                         result->value.constant.value = left_value.value.constant.value - right_value.value.constant.value;
 398                 } else {
 399                         MAKE_VALUE_ANY (*result);
 400                 }
 401                 if (result->type == MONO_VARIABLE_SUMMARIZED_VALUE) {
 402                         check_delta_safety (area, result);
 403                 }
 404                 break;
 405         }
 406         case CEE_AND: {
 407                 MonoSummarizedValue left_value;
 408                 MonoSummarizedValue right_value;
 409                 int constant_operand_value;
 410
 411                 summarize_integer_value (area, value->inst_left, &left_value, result_value_kind);
 412                 summarize_integer_value (area, value->inst_right, &right_value, result_value_kind);
 413
 414                 if (left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
 415                         constant_operand_value = left_value.value.constant.value;
 416                 } else if (right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
 417                         constant_operand_value = right_value.value.constant.value;
 418                 } else {
 419                         constant_operand_value = 0;
 420                 }
 421
 422                 if (constant_operand_value > 0) {
 423                         if (constant_operand_value <= 0xff) {
 424                                 if ((result_value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) > 1) {
 425                                         value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_1;
 426                                 }
 427                         } else if (constant_operand_value <= 0xffff) {
 428                                 if ((result_value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) > 2) {
 429                                         value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_2;
 430                                 }
 431                         }
 432                 }
 433
 434                 MAKE_VALUE_ANY (*result);
 435                 break;
 436         }
 437         case CEE_CONV_I1:
 438         case CEE_CONV_OVF_I1:
 439         case CEE_CONV_OVF_I1_UN:
 440                 value_kind = MONO_INTEGER_VALUE_SIZE_1;
 441                 MAKE_VALUE_ANY (*result);
 442                 break;
 443         case CEE_CONV_U1:
 444         case CEE_CONV_OVF_U1:
 445                 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_1;
 446                 MAKE_VALUE_ANY (*result);
 447                 break;
 448         case CEE_CONV_I2:
 449         case CEE_CONV_OVF_I2:
 450         case CEE_CONV_OVF_I2_UN:
 451                 value_kind = MONO_INTEGER_VALUE_SIZE_2;
 452                 MAKE_VALUE_ANY (*result);
 453                 break;
 454         case CEE_CONV_U2:
 455         case CEE_CONV_OVF_U2:
 456                 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_2;
 457                 MAKE_VALUE_ANY (*result);
 458                 break;
 459         case CEE_LDLEN:
 460                 summarize_array_value (area, value->inst_left, result, TRUE);
 461                 value_kind = MONO_UNSIGNED_INTEGER_VALUE_SIZE_4;
 462                 break;
 463         case OP_LCONV_TO_I4:
 464                 value_kind = summarize_integer_value (area, value->inst_left, result, result_value_kind);
 465                 break;
 466         case OP_PHI:
 467                 result->type = MONO_PHI_SUMMARIZED_VALUE;
 468                 result->value.phi.number_of_alternatives = *(value->inst_phi_args);
 469                 result->value.phi.phi_alternatives = value->inst_phi_args + 1;
 470                 break;
 471         default:
 472                 MAKE_VALUE_ANY (*result);
 473         }
 474         return value_kind;
 475 }
 476
 477 /*
 478  * Given a MonoInst representing an array value, store it in "summarized" form.
 479  * result: the "summarized" value
 480  * is_array_type: TRUE of we are *sure* that an eventual OP_PCONST will point
 481  * to a MonoArray (this can happen for already initialized readonly static fields,
 482  * in which case we will get the array length directly from the MonoArray)
 483  */
 484 static void
 485 summarize_array_value (MonoVariableRelationsEvaluationArea *area, MonoInst *value, MonoSummarizedValue *result, gboolean is_array_type) {
 486         switch (value->opcode) {
 487         case OP_LOCAL:
 488         case OP_ARG:
 489                 result->type = MONO_VARIABLE_SUMMARIZED_VALUE;
 490                 result->value.variable.variable = value->inst_c0;
 491                 result->value.variable.delta = 0;
 492                 break;
 493         case CEE_LDIND_REF:
 494                 summarize_array_value (area, value->inst_left, result, FALSE);
 495                 break;
 496         case CEE_NEWARR:
 497                 summarize_integer_value (area, value->inst_newa_len, result, MONO_UNKNOWN_INTEGER_VALUE);
 498                 break;
 499         case OP_PCONST:
 500                 if ((is_array_type) && (value->inst_p0 != NULL)) {
 501                         MonoArray *array = (MonoArray *) (value->inst_p0);
 502                         result->type = MONO_CONSTANT_SUMMARIZED_VALUE;
 503                         result->value.constant.value = array->max_length;
 504                 } else {
 505                         MAKE_VALUE_ANY (*result);
 506                 }
 507                 break;
 508         case OP_PHI:
 509                 result->type = MONO_PHI_SUMMARIZED_VALUE;
 510                 result->value.phi.number_of_alternatives = *(value->inst_phi_args);
 511                 result->value.phi.phi_alternatives = value->inst_phi_args + 1;
 512                 break;
 513         default:
 514                 MAKE_VALUE_ANY (*result);
 515         }
 516 }
 517
 518 static MonoValueRelation
 519 get_relation_from_branch_instruction (int opcode) {
 520         switch (opcode) {
 521         case CEE_BEQ:
 522                 return MONO_EQ_RELATION;
 523         case CEE_BLT:
 524         case CEE_BLT_UN:
 525                 return MONO_LT_RELATION;
 526         case CEE_BLE:
 527         case CEE_BLE_UN:
 528                 return MONO_LE_RELATION;
 529         case CEE_BGT:
 530         case CEE_BGT_UN:
 531                 return MONO_GT_RELATION;
 532         case CEE_BGE:
 533         case CEE_BGE_UN:
 534                 return MONO_GE_RELATION;
 535         case CEE_BNE_UN:
 536                 return MONO_NE_RELATION;
 537         default:
 538                 return MONO_ANY_RELATION;
 539         }
 540 }
 541
 542 /*
 543  * Given a BB, find its entry condition and put its relations in a
 544  * "MonoAdditionalVariableRelationsForBB" structure.
 545  * bb: the BB
 546  * relations: the resulting relations (entry condition of the given BB)
 547  */
 548 static void
 549 get_relations_from_previous_bb (MonoVariableRelationsEvaluationArea *area, MonoBasicBlock *bb, MonoAdditionalVariableRelationsForBB *relations) {
 550         MonoBasicBlock *in_bb;
 551         MonoInst *branch;
 552         MonoValueRelation branch_relation;
 553         MonoValueRelation symmetric_relation;
 554
 555         INITIALIZE_VALUE_RELATION (&(relations->relation1.relation));
 556         relations->relation1.relation.relation_is_static_definition = FALSE;
 557         relations->relation1.insertion_point = NULL;
 558         relations->relation1.variable = -1;
 559         INITIALIZE_VALUE_RELATION (&(relations->relation2.relation));
 560         relations->relation2.relation.relation_is_static_definition = FALSE;
 561         relations->relation2.insertion_point = NULL;
 562         relations->relation2.variable = -1;
 563
 564
 565         if (bb->in_count == 1) { /* Should write the code to "sum" conditions... */
 566                 in_bb = bb->in_bb [0];
 567                 branch = in_bb->last_ins;
 568                 if (branch == NULL) return;
 569                 branch_relation = get_relation_from_branch_instruction (branch->opcode);
 570                 if ((branch_relation != MONO_ANY_RELATION) && (branch->inst_left->opcode == OP_COMPARE)) {
 571                         MonoSummarizedValue left_value;
 572                         MonoSummarizedValue right_value;
 573                         gboolean code_path;
 574
 575                         if (branch->inst_true_bb == bb) {
 576                                 code_path = TRUE;
 577                         } else if (branch->inst_false_bb == bb) {
 578                                 code_path = FALSE;
 579                         } else {
 580                                 code_path = TRUE;
 581                                 g_assert_not_reached ();
 582                         }
 583
 584                         if (!code_path) {
 585                                 branch_relation = MONO_NEGATED_RELATION (branch_relation);
 586                         }
 587                         symmetric_relation = MONO_SYMMETRIC_RELATION (branch_relation);
 588
 589                         summarize_integer_value (area, branch->inst_left->inst_left, &left_value, MONO_UNKNOWN_INTEGER_VALUE);
 590                         summarize_integer_value (area, branch->inst_left->inst_right, &right_value, MONO_UNKNOWN_INTEGER_VALUE);
 591
 592                         if ((left_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) && ((right_value.type == MONO_VARIABLE_SUMMARIZED_VALUE)||(right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE))) {
 593                                 relations->relation1.variable = left_value.value.variable.variable;
 594                                 relations->relation1.relation.relation = branch_relation;
 595                                 relations->relation1.relation.related_value = right_value;
 596                                 if (right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
 597                                         relations->relation1.relation.related_value.value.constant.value -= left_value.value.variable.delta;
 598                                 } else {
 599                                         relations->relation1.relation.related_value.value.variable.delta -= left_value.value.variable.delta;
 600                                 }
 601                         }
 602                         if ((right_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) && ((left_value.type == MONO_VARIABLE_SUMMARIZED_VALUE)||(left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE))) {
 603                                 relations->relation2.variable = right_value.value.variable.variable;
 604                                 relations->relation2.relation.relation = symmetric_relation;
 605                                 relations->relation2.relation.related_value = left_value;
 606                                 if (left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
 607                                         relations->relation2.relation.related_value.value.constant.value -= right_value.value.variable.delta;
 608                                 } else {
 609                                         relations->relation2.relation.related_value.value.variable.delta -= right_value.value.variable.delta;
 610                                 }
 611                         }
 612                 }
 613         }
 614 }
 615
 616
 617 /*
 618  * Add the given relations to the evaluation area.
 619  * area: the evaluation area
 620  * change: the relations that must be added
 621  */
 622 static void
 623 apply_change_to_evaluation_area (MonoVariableRelationsEvaluationArea *area, MonoAdditionalVariableRelation *change) {
 624         MonoSummarizedValueRelation *base_relation;
 625
 626         if (change->relation.relation != MONO_ANY_RELATION) {
 627                 base_relation = &(area->relations [change->variable]);
 628                 while ((base_relation->next != NULL) && (base_relation->next->relation_is_static_definition)) {
 629                         base_relation = base_relation->next;
 630                 }
 631                 change->insertion_point = base_relation;
 632                 change->relation.next = base_relation->next;
 633                 base_relation->next = &(change->relation);
 634         }
 635 }
 636
 637 /*
 638  * Remove the given relation from the evaluation area.
 639  * change: the relation that must be removed
 640  */
 641 static void
 642 remove_change_from_evaluation_area (MonoAdditionalVariableRelation *change) {
 643         if (change->insertion_point != NULL) {
 644                 change->insertion_point->next = change->relation.next;
 645                 change->relation.next = NULL;
 646         }
 647 }
 648
 649
 650 static void
 651 clean_contexts (MonoRelationsEvaluationContext *contexts, int number) {
 652         int i;
 653         for (i = 0; i < number; i++) {
 654                 contexts [i].status = MONO_RELATIONS_EVALUATION_NOT_STARTED;
 655         }
 656 }
 657
 658
 659 /*
 660  * Perform the intersection of a range and a constant value (taking into
 661  * account the relation that the value has with the range).
 662  * range: the range that will be intersected with the value
 663  * value: the value that will be intersected with the range
 664  * relation: the relation between the range and the value
 665  */
 666 static void
 667 intersect_value( MonoRelationsEvaluationRange *range, int value, MonoValueRelation relation ) {
 668         switch (relation) {
 669         case MONO_NO_RELATION:
 670                 MONO_MAKE_RELATIONS_EVALUATION_RANGE_IMPOSSIBLE (*range);
 671                 break;
 672         case MONO_ANY_RELATION:
 673                 break;
 674         case MONO_EQ_RELATION:
 675                 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, value);
 676                 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, value);
 677                 break;
 678         case MONO_NE_RELATION: {
 679                 /* IMPROVEMENT Figure this out! (ignoring it is safe anyway) */
 680                 break;
 681         }
 682         case MONO_LT_RELATION:
 683                 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (value));
 684                 break;
 685         case MONO_LE_RELATION:
 686                 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, value);
 687                 break;
 688         case MONO_GT_RELATION:
 689                 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (value));
 690                 break;
 691         case MONO_GE_RELATION:
 692                 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, value);
 693                 break;
 694         default:
 695                 g_assert_not_reached();
 696         }
 697 }
 698
 699
 700 /*
 701  * Perform the intersection of two pairs of ranges (taking into account the
 702  * relation between the ranges and a given delta).
 703  * ranges: the ranges that will be intersected
 704  * other_ranges the other ranges that will be intersected
 705  * delta: the delta between the pairs of ranges
 706  * relation: the relation between the pairs of ranges
 707  */
 708 static void
 709 intersect_ranges( MonoRelationsEvaluationRanges *ranges, MonoRelationsEvaluationRanges *other_ranges, int delta, MonoValueRelation relation ) {
 710         if (delta == 0) {
 711                 switch (relation) {
 712                 case MONO_NO_RELATION:
 713                         MONO_MAKE_RELATIONS_EVALUATION_RANGES_IMPOSSIBLE (*ranges);
 714                         break;
 715                 case MONO_ANY_RELATION:
 716                         break;
 717                 case MONO_EQ_RELATION:
 718                         MONO_RELATIONS_EVALUATION_RANGES_INTERSECTION (*ranges, *other_ranges);
 719                         break;
 720                 case MONO_NE_RELATION: {
 721                         /* FIXME Figure this out! (ignoring it is safe anyway) */
 722                         break;
 723                 }
 724                 case MONO_LT_RELATION:
 725                         MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->zero.upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->zero.upper));
 726                         MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->variable.upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->variable.upper));
 727                         break;
 728                 case MONO_LE_RELATION:
 729                         MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->zero.upper, other_ranges->zero.upper);
 730                         MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->variable.upper, other_ranges->variable.upper);
 731                         break;
 732                 case MONO_GT_RELATION:
 733                         MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->zero.lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->zero.lower));
 734                         MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->variable.lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->variable.lower));
 735                         break;
 736                 case MONO_GE_RELATION:
 737                         MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->zero.lower, other_ranges->zero.lower);
 738                         MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->variable.lower, other_ranges->variable.lower);
 739                         break;
 740                 default:
 741                         g_assert_not_reached();
 742                 }
 743         } else {
 744                 MonoRelationsEvaluationRanges translated_ranges = *other_ranges;
 745                 MONO_ADD_DELTA_SAFELY_TO_RANGES (translated_ranges, delta);
 746                 intersect_ranges( ranges, &translated_ranges, FALSE, relation );
 747         }
 748 }
 749
 750 /*
 751  * Recursive method that traverses the relation graph to evaluate the
 752  * relation between two variables.
 753  * At the end of the execution, the resulting ranges are in the context of
 754  * the "starting" variable.
 755  * area: the current evaluation area (it contains the relation graph and
 756  *       memory for all the evaluation contexts is already allocated)
 757  * variable: starting variable (the value ranges in its context are the result
 758  *           of the execution of this procedure)
 759  * target_variable: the variable with respect to which the starting variable
 760  *                  is evaluated (tipically the starting variable is the index
 761  *                  and the target one is the array (which means its length))
 762  * father_context: the previous evaluation context in recursive invocations
 763  *                 (or NULL for the first invocation)
 764  */
 765 static void
 766 evaluate_relation_with_target_variable (MonoVariableRelationsEvaluationArea *area, int variable, int target_variable, MonoRelationsEvaluationContext *father_context) {
 767         MonoRelationsEvaluationContext *context = &(area->contexts [variable]);
 768
 769         // First of all, we check the evaluation status
 770         // (what must be done is *very* different in each case)
 771         switch (context->status) {
 772         case MONO_RELATIONS_EVALUATION_NOT_STARTED: {
 773                 MonoSummarizedValueRelation *relation = &(area->relations [variable]);
 774
 775                 if (TRACE_ABC_REMOVAL) {
 776                         printf ("Evaluating varible %d (target variable %d)\n", variable, target_variable);
 777                         print_summarized_value_relation (relation);
 778                         printf ("\n");
 779                 }
 780
 781                 // We properly inizialize the context
 782                 context->status = MONO_RELATIONS_EVALUATION_IN_PROGRESS;
 783                 context->father = father_context;
 784                 MONO_MAKE_RELATIONS_EVALUATION_RANGES_WEAK (context->ranges);
 785
 786                 // If we have found the target variable, we can set the range
 787                 // related to it in the context to "equal" (which is [0,0])
 788                 if (variable == target_variable) {
 789                         if (TRACE_ABC_REMOVAL) {
 790                                 printf ("Target variable reached (%d), continuing to evaluate relations with constants\n", variable);
 791                         }
 792                         context->ranges.variable.lower = 0;
 793                         context->ranges.variable.upper = 0;
 794                 }
 795
 796                 // Examine all relations for this variable (scan the list)
 797                 // The contribute of each relation will be intersected (logical and)
 798                 while (relation != NULL) {
 799                         context->current_relation = relation;
 800
 801                         if (TRACE_ABC_REMOVAL) {
 802                                 printf ("Processing (%d): ", variable);
 803                                 print_summarized_value_relation (relation);
 804                                 printf ("\n");
 805                         }
 806
 807                         // We decie what to do according the the type of the related value
 808                         switch (relation->related_value.type) {
 809                         case MONO_ANY_SUMMARIZED_VALUE:
 810                                 // No added information, skip it
 811                                 break;
 812                         case MONO_CONSTANT_SUMMARIZED_VALUE:
 813                                 // Intersect range with constant (taking into account the relation)
 814                                 intersect_value (&(context->ranges.zero), relation->related_value.value.constant.value, relation->relation);
 815                                 break;
 816                         case MONO_VARIABLE_SUMMARIZED_VALUE:
 817                                 // Generally, evaluate related variable and intersect ranges.
 818                                 // However, some check is necessary...
 819
 820                                 // If the relation is "ANY", nothing to do (no added information)
 821                                 if (relation->relation != MONO_ANY_RELATION) {
 822                                         int related_variable = relation->related_value.value.variable.variable;
 823                                         MonoRelationsEvaluationContext *related_context = &(area->contexts [related_variable]);
 824
 825                                         // The second condition in the "or" avoids messing with "back edges" in the graph traversal
 826                                         // (they are simply ignored instead of triggering the handling of recursion)
 827                                         if ( (related_context->status == MONO_RELATIONS_EVALUATION_NOT_STARTED) || !
 828                                                         ((related_context->current_relation->related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) &&
 829                                                         (related_context->current_relation->related_value.value.variable.variable == variable))) {
 830                                                 // Evaluate the related variable
 831                                                 evaluate_relation_with_target_variable (area, related_variable, target_variable, context);
 832
 833                                                 // Check if we are part of a recursive loop
 834                                                 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) {
 835                                                         if (TRACE_ABC_REMOVAL) {
 836                                                                 printf ("Recursivity detected for varible %d (target variable %d), status ", variable, target_variable);
 837                                                                 print_evaluation_context_status (context->status);
 838                                                         }
 839
 840                                                         // If we are, check if the evaluation of the related variable is complete
 841                                                         if (related_context->status == MONO_RELATIONS_EVALUATION_COMPLETED) {
 842                                                                 // If it is complete, we are part of a recursive definition.
 843                                                                 // Since it is a *definition* (and definitions are evaluated *before*
 844                                                                 // conditions because they are first in the list), intersection is not
 845                                                                 // strictly necessary, we simply copy the ranges and apply the delta
 846                                                                 context->ranges = related_context->ranges;
 847                                                                 /* Delta has already been checked for over/under-flow when evaluating values */
 848                                                                 MONO_ADD_DELTA_SAFELY_TO_RANGES (context->ranges, relation->related_value.value.variable.delta);
 849                                                                 context->status = MONO_RELATIONS_EVALUATION_COMPLETED;
 850                                                                 if (TRACE_ABC_REMOVAL) {
 851                                                                         printf (", ranges already computed, result: \n");
 852                                                                         print_evaluation_context_ranges (&(context->ranges));
 853                                                                         printf (" (delta is %d)\n", relation->related_value.value.variable.delta);
 854                                                                 }
 855                                                         } else {
 856                                                                 // If it is not complete, do nothing (we do not have enough information)
 857                                                                 if (TRACE_ABC_REMOVAL) {
 858                                                                         printf (", ranges not computed\n");
 859                                                                 }
 860                                                         }
 861                                                 } else {
 862                                                         // If we are not (the common case) intersect the result
 863                                                         intersect_ranges( &(context->ranges), &(related_context->ranges), relation->related_value.value.variable.delta, relation->relation );
 864                                                 }
 865                                         } else {
 866                                                 if (TRACE_ABC_REMOVAL) {
 867                                                         printf ("Relation is a back-edge in this traversal, skipping\n");
 868                                                 }
 869                                         }
 870                                 }
 871                                 break;
 872                         case MONO_PHI_SUMMARIZED_VALUE: {
 873                                 // We must compute all PHI alternatives, combining the results (with a union, which is a logical "or"),
 874                                 // and intersect this result with the ranges in the context; we must also take into account recursions
 875                                 // (with loops that can be ascending, descending, or indefinite)
 876                                 MonoRelationsEvaluationRanges phi_ranges;
 877                                 int phi;
 878                                 gboolean is_ascending = FALSE;
 879                                 gboolean is_descending = FALSE;
 880
 881                                 MONO_MAKE_RELATIONS_EVALUATION_RANGES_IMPOSSIBLE (phi_ranges);
 882                                 for (phi = 0; phi < relation->related_value.value.phi.number_of_alternatives; phi++) {
 883                                         int phi_alternative = relation->related_value.value.phi.phi_alternatives [phi];
 884                                         evaluate_relation_with_target_variable (area, phi_alternative, target_variable, context);
 885
 886                                         // This means we are part of a recursive loop
 887                                         if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) {
 888                                                 if (TRACE_ABC_REMOVAL) {
 889                                                         printf ("Recursivity detected for varible %d (target variable %d), status ", variable, target_variable);
 890                                                         print_evaluation_context_status (context->status);
 891                                                         printf ("\n");
 892                                                 }
 893                                                 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING) {
 894                                                         is_ascending = TRUE;
 895                                                 }
 896                                                 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING) {
 897                                                         is_descending = TRUE;
 898                                                 }
 899                                                 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE) {
 900                                                         is_ascending = TRUE;
 901                                                         is_descending = TRUE;
 902                                                 }
 903
 904                                                 // Clear "recursivity" bits in the status (recursion has been handled)
 905                                                 context->status = MONO_RELATIONS_EVALUATION_IN_PROGRESS;
 906                                         } else {
 907                                                 MONO_RELATIONS_EVALUATION_RANGES_UNION (phi_ranges, area->contexts [phi_alternative].ranges);
 908                                         }
 909                                 }
 910
 911                                 // Apply the effects of all recursive loops
 912                                 if (is_ascending) {
 913                                         phi_ranges.zero.upper = INT_MAX;
 914                                         phi_ranges.variable.upper = INT_MAX;
 915                                 }
 916                                 if (is_descending) {
 917                                         phi_ranges.zero.lower = INT_MIN;
 918                                         phi_ranges.variable.lower = INT_MIN;
 919                                 }
 920
 921                                 // Intersect final result
 922                                 MONO_RELATIONS_EVALUATION_RANGES_INTERSECTION (context->ranges, phi_ranges);
 923                                 break;
 924                         }
 925                         default:
 926                                 g_assert_not_reached();
 927                         }
 928
 929                         // Pass to next relation
 930                         relation = relation->next;
 931                 }
 932
 933                 // Check if any recursivity bits are still in the status, and in any case clear them
 934                 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) {
 935                         if (TRACE_ABC_REMOVAL) {
 936                                 printf ("Recursivity for varible %d (target variable %d) discards computation, status ", variable, target_variable);
 937                                 print_evaluation_context_status (context->status);
 938                                 printf ("\n");
 939                         }
 940                         // If yes, we did not have enough information (most likely we were evaluated inside a PHI, but we also
 941                         // depended on the same PHI, which was still in evaluation...), so clear the status to "NOT_STARTED"
 942                         // (if we will be evaluated again, the PHI will be already done, so our evaluation will succeed)
 943                         context->status = MONO_RELATIONS_EVALUATION_NOT_STARTED;
 944                 } else {
 945                         if (TRACE_ABC_REMOVAL) {
 946                                 printf ("Ranges for varible %d (target variable %d) computed: ", variable, target_variable);
 947                                 print_evaluation_context_ranges (&(context->ranges));
 948                                 printf ("\n");
 949                         }
 950                         // If not (the common case) the evaluation is complete, and the result is in the context
 951                         context->status = MONO_RELATIONS_EVALUATION_COMPLETED;
 952                 }
 953                 break;
 954         }
 955         case MONO_RELATIONS_EVALUATION_IN_PROGRESS: {
 956                 // This means we are in a recursive loop
 957                 MonoRelationsEvaluationContext *current_context = father_context;
 958                 MonoRelationsEvaluationContext *last_context = context->father;
 959                 gboolean evaluation_can_be_recursive = TRUE;
 960                 gboolean evaluation_is_definition = TRUE;
 961                 int path_value = 0;
 962
 963                 if (TRACE_ABC_REMOVAL) {
 964                         printf ("Evaluation of varible %d (target variable %d) already in progress\n", variable, target_variable);
 965                         print_evaluation_context (context);
 966                         print_summarized_value_relation (context->current_relation);
 967                         printf ("\n");
 968                 }
 969
 970                 // We must check if the loop can be a recursive definition (we scan the whole loop)
 971                 while (current_context != last_context) {
 972                         if (current_context == NULL) {
 973                                 printf ("Broken recursive ring in ABC removal\n");
 974                                 g_assert_not_reached ();
 975                         }
 976
 977                         if (current_context->current_relation->relation_is_static_definition) {
 978                                 if (current_context->current_relation->related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
 979                                         /* No need to check path_value for over/under-flow, since delta should be safe */
 980                                         path_value += current_context->current_relation->related_value.value.variable.delta;
 981                                 } else if (current_context->current_relation->related_value.type != MONO_PHI_SUMMARIZED_VALUE) {
 982                                         evaluation_can_be_recursive = FALSE;
 983                                 }
 984                         } else {
 985                                 evaluation_is_definition = FALSE;
 986                                 evaluation_can_be_recursive = FALSE;
 987                         }
 988
 989                         current_context = current_context->father;
 990                 }
 991
 992                 // If this is a recursive definition, we properly flag the status in all the involved contexts
 993                 if (evaluation_is_definition) {
 994                         MonoRelationsEvaluationStatus recursive_status;
 995                         if (evaluation_can_be_recursive) {
 996                                 if (path_value > 0) {
 997                                         recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING;
 998                                 } else if (path_value < 0) {
 999                                         recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING;
1000                                 } else {
1001                                         recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE;
1002                                 }
1003                         } else {
1004                                 recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE;
1005                         }
1006
1007                         if (TRACE_ABC_REMOVAL) {
1008                                 printf ("Recursivity accepted (");
1009                                 print_evaluation_context_status (recursive_status);
1010                                 printf (")\n");
1011                         }
1012
1013                         current_context = father_context;
1014                         while (current_context != last_context) {
1015                                 current_context->status |= recursive_status;
1016                                 current_context = current_context->father;
1017                         }
1018                 } else {
1019                         if (TRACE_ABC_REMOVAL) {
1020                                 printf ("Recursivity rejected (some relation in the cycle is not a defintion)\n");
1021                         }
1022                 }
1023                 break;
1024         }
1025         case MONO_RELATIONS_EVALUATION_COMPLETED: {
1026                 return;
1027         }
1028         default:
1029                 if (TRACE_ABC_REMOVAL) {
1030                         printf ("Varible %d (target variable %d) already in a recursive ring, skipping\n", variable, target_variable);
1031                         print_evaluation_context (context);
1032                         print_summarized_value_relation (context->current_relation);
1033                         printf ("\n");
1034                 }
1035                 break;
1036         }
1037
1038 }
1039
1040 /*
1041  * Apply the given value kind to the given range
1042  */
1043 static void apply_value_kind_to_range (MonoRelationsEvaluationRange *range, MonoIntegerValueKind value_kind) {
1044         if (value_kind != MONO_UNKNOWN_INTEGER_VALUE) {
1045                 if (value_kind & MONO_UNSIGNED_VALUE_FLAG) {
1046                         if (range->lower < 0) {
1047                                 range->lower = 0;
1048                         }
1049                         if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 1) {
1050                                 if (range->upper > 0xff) {
1051                                         range->upper = 0xff;
1052                                 }
1053                         } else if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 2) {
1054                                 if (range->upper > 0xffff) {
1055                                         range->upper = 0xffff;
1056                                 }
1057                         }
1058                 } else {
1059                         if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 1) {
1060                                 if (range->lower < -0x80) {
1061                                         range->lower = -0x80;
1062                                 }
1063                                 if (range->upper > 0x7f) {
1064                                         range->upper = 0x7f;
1065                                 }
1066                         } else if ((value_kind & MONO_INTEGER_VALUE_SIZE_BITMASK) == 2) {
1067                                 if (range->lower < -0x8000) {
1068                                         range->lower = -0x8000;
1069                                 }
1070                                 if (range->upper > 0x7fff) {
1071                                         range->upper = 0x7fff;
1072                                 }
1073                         }
1074                 }
1075         }
1076 }
1077
1078 /*
1079  * Attempt the removal of bounds checks from a MonoInst.
1080  * inst: the MonoInst
1081  * area: the current evaluation area (it contains the relation graph and
1082  *       memory for all the evaluation contexts is already allocated)
1083  */
1084 static void
1085 remove_abc_from_inst (MonoInst *inst, MonoVariableRelationsEvaluationArea *area) {
1086         if (inst->opcode == CEE_LDELEMA) {
1087                 MonoInst *array_inst = inst->inst_left;
1088                 MonoInst *index_inst = inst->inst_right;
1089                 MonoSummarizedValue array_value;
1090                 MonoSummarizedValue index_value;
1091                 MonoIntegerValueKind index_value_kind;
1092
1093                 /* First of all, examine the CEE_LDELEMA operands */
1094                 summarize_array_value (area, array_inst, &array_value, TRUE);
1095                 index_value_kind = summarize_integer_value (area, index_inst, &index_value, MONO_UNKNOWN_INTEGER_VALUE);
1096
1097                 /* If the array is a local variable... */
1098                 if (array_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
1099                         int array_variable = array_value.value.variable.variable;
1100                         MonoRelationsEvaluationContext *array_context = &(area->contexts [array_variable]);
1101
1102                         if (index_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
1103                                 // The easiest case: we just evaluate the array length, to see if it has some relation
1104                                 // with the index constant, and act accordingly
1105
1106                                 clean_contexts (area->contexts, area->cfg->num_varinfo);
1107                                 evaluate_relation_with_target_variable (area, array_variable, array_variable, NULL);
1108
1109                                 if ((index_value.value.constant.value >= 0) && (index_value.value.constant.value < array_context->ranges.zero.lower)) {
1110                                         if (REPORT_ABC_REMOVAL) {
1111                                                 printf ("ARRAY-ACCESS: removed bounds check on array %d with constant index %d in method %s\n",
1112                                                                 array_variable, index_value.value.constant.value, mono_method_full_name (area->cfg->method, TRUE));
1113                                         }
1114                                         inst->flags |= (MONO_INST_NORANGECHECK);
1115                                 }
1116                         } else if (index_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
1117                                 // The common case: we must evaluate both the index and the array length, and check for relevant
1118                                 // relations both through variable definitions and as constant definitions
1119
1120                                 int index_variable = index_value.value.variable.variable;
1121                                 MonoRelationsEvaluationContext *index_context = &(area->contexts [index_variable]);
1122
1123                                 clean_contexts (area->contexts, area->cfg->num_varinfo);
1124
1125                                 evaluate_relation_with_target_variable (area, index_variable, array_variable, NULL);
1126                                 evaluate_relation_with_target_variable (area, array_variable, array_variable, NULL);
1127
1128                                 MONO_SUB_DELTA_SAFELY_FROM_RANGES (index_context->ranges, index_value.value.variable.delta);
1129                                 /* Apply index value kind */
1130                                 apply_value_kind_to_range (&(index_context->ranges.zero), index_value_kind);
1131
1132                                 if (index_context->ranges.zero.lower >= 0) {
1133                                         if (TRACE_ABC_REMOVAL) {
1134                                                 printf ("ARRAY-ACCESS: Removed lower bound check on array %d with index %d\n", array_variable, index_variable);
1135                                         }
1136                                         if ((index_context->ranges.variable.upper < 0)||(index_context->ranges.zero.upper < array_context->ranges.zero.lower)) {
1137                                                 if (REPORT_ABC_REMOVAL) {
1138                                                         printf ("ARRAY-ACCESS: removed bounds check on array %d with index %d in method %s\n",
1139                                                                         array_variable, index_variable, mono_method_full_name (area->cfg->method, TRUE));
1140                                                 }
1141                                                 inst->flags |= (MONO_INST_NORANGECHECK);
1142                                         }
1143                                 }
1144                                 if (TRACE_ABC_REMOVAL) {
1145                                         if (index_context->ranges.variable.upper < 0) {
1146                                                 printf ("ARRAY-ACCESS: Removed upper bound check (through variable) on array %d with index %d\n", array_variable, index_variable);
1147                                         }
1148                                         if (index_context->ranges.zero.upper < array_context->ranges.zero.lower) {
1149                                                 printf ("ARRAY-ACCESS: Removed upper bound check (through constant) on array %d with index %d\n", array_variable, index_variable);
1150                                         }
1151                                 }
1152                         }
1153                 } else if (array_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
1154                         if (index_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
1155                                 /* The easiest possible case: constant with constant */
1156                                 if ((index_value.value.constant.value >= 0) && (index_value.value.constant.value < array_value.value.constant.value)) {
1157                                         if (REPORT_ABC_REMOVAL) {
1158                                                 printf ("ARRAY-ACCESS: removed bounds check on array of constant length %d with constant index %d in method %s\n",
1159                                                                 array_value.value.constant.value, index_value.value.constant.value, mono_method_full_name (area->cfg->method, TRUE));
1160                                         }
1161                                         inst->flags |= (MONO_INST_NORANGECHECK);
1162                                 }
1163                         } else if (index_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
1164                                 /* The index has a variable related value, which must be evaluated */
1165                                 int index_variable = index_value.value.variable.variable;
1166                                 MonoRelationsEvaluationContext *index_context = &(area->contexts [index_variable]);
1167
1168                                 clean_contexts (area->contexts, area->cfg->num_varinfo);
1169                                 evaluate_relation_with_target_variable (area, index_variable, index_variable, NULL);
1170                                 /* Apply index value kind */
1171                                 apply_value_kind_to_range (&(index_context->ranges.zero), index_value_kind);
1172
1173                                 if ((index_context->ranges.zero.lower >= 0) && (index_context->ranges.zero.upper < array_value.value.constant.value)) {
1174                                         if (REPORT_ABC_REMOVAL) {
1175                                                 printf ("ARRAY-ACCESS: removed bounds check on array of constant length %d with index %d ranging from %d to %d in method %s\n",
1176                                                                 array_value.value.constant.value, index_variable, index_context->ranges.zero.lower, index_context->ranges.zero.upper, mono_method_full_name (area->cfg->method, TRUE));
1177                                         }
1178                                         inst->flags |= (MONO_INST_NORANGECHECK);
1179                                 }
1180                         } else if (index_value_kind != MONO_UNKNOWN_INTEGER_VALUE) {
1181                                 /* The index has an unknown but bounded value */
1182                                 MonoRelationsEvaluationRange range;
1183                                 MONO_MAKE_RELATIONS_EVALUATION_RANGE_WEAK (range);
1184                                 apply_value_kind_to_range (&range, index_value_kind);
1185
1186                                 if ((range.lower >= 0) && (range.upper < array_value.value.constant.value)) {
1187                                         if (REPORT_ABC_REMOVAL) {
1188                                                 printf ("ARRAY-ACCESS: removed bounds check on array of constant length %d with unknown index ranging from %d to %d in method %s\n",
1189                                                                 array_value.value.constant.value, range.lower, range.upper, mono_method_full_name (area->cfg->method, TRUE));
1190                                         }
1191                                         inst->flags |= (MONO_INST_NORANGECHECK);
1192                                 }
1193                         }
1194                 }
1195         }
1196 }
1197
1198 /*
1199  * Recursively scan a tree of MonoInst looking for array accesses.
1200  * inst: the root of the MonoInst tree
1201  * area: the current evaluation area (it contains the relation graph and
1202  *       memory for all the evaluation contexts is already allocated)
1203  */
1204 static void
1205 process_inst (MonoInst *inst, MonoVariableRelationsEvaluationArea *area) {
1206         if (inst->opcode == CEE_LDELEMA) { /* Handle OP_LDELEMA2D, too */
1207                 if (TRACE_ABC_REMOVAL) {
1208                         printf ("Attempting check removal...\n");
1209                 }
1210
1211                 remove_abc_from_inst (inst, area);
1212         }
1213
1214         if (mono_burg_arity [inst->opcode]) {
1215                 process_inst (inst->inst_left, area);
1216                 if (mono_burg_arity [inst->opcode] > 1) {
1217                         process_inst (inst->inst_right, area);
1218                 }
1219         }
1220 }
1221
1222
1223
1224
1225 /*
1226  * Process a BB removing bounds checks from array accesses.
1227  * It does the following (in sequence):
1228  * - Get the BB entry condition
1229  * - Add its relations to the relation graph in the evaluation area
1230  * - Process all the MonoInst trees in the BB
1231  * - Recursively process all the children BBs in the dominator tree
1232  * - Remove the relations previously added to the relation graph
1233  *
1234  * bb: the BB that must be processed
1235  * area: the current evaluation area (it contains the relation graph and
1236  *       memory for all the evaluation contexts is already allocated)
1237  */
1238 static void
1239 process_block (MonoBasicBlock *bb, MonoVariableRelationsEvaluationArea *area) {
1240         int inst_index;
1241         MonoInst *current_inst;
1242         MonoAdditionalVariableRelationsForBB additional_relations;
1243         GSList *dominated_bb;
1244
1245         if (TRACE_ABC_REMOVAL) {
1246                 printf ("Processing block %d [dfn %d]...\n", bb->block_num, bb->dfn);
1247         }
1248
1249         get_relations_from_previous_bb (area, bb, &additional_relations);
1250         if (TRACE_ABC_REMOVAL) {
1251                 if (additional_relations.relation1.relation.relation != MONO_ANY_RELATION) {
1252                         printf ("Adding relation 1 on variable %d: ", additional_relations.relation1.variable);
1253                         print_summarized_value_relation (&(additional_relations.relation1.relation));
1254                         printf ("\n");
1255                 }
1256                 if (additional_relations.relation2.relation.relation != MONO_ANY_RELATION) {
1257                         printf ("Adding relation 2 on variable %d: ", additional_relations.relation2.variable);
1258                         print_summarized_value_relation (&(additional_relations.relation2.relation));
1259                         printf ("\n");
1260                 }
1261         }
1262         apply_change_to_evaluation_area (area, &(additional_relations.relation1));
1263         apply_change_to_evaluation_area (area, &(additional_relations.relation2));
1264
1265         inst_index = 0;
1266         current_inst = bb->code;
1267         while (current_inst != NULL) {
1268                 if (TRACE_ABC_REMOVAL) {
1269                         printf ("Processing instruction %d\n", inst_index);
1270                         inst_index++;
1271                 }
1272
1273                 process_inst (current_inst, area);
1274
1275                 current_inst = current_inst->next;
1276         }
1277
1278
1279         if (TRACE_ABC_REMOVAL) {
1280                 printf ("Processing block %d [dfn %d] done.\n", bb->block_num, bb->dfn);
1281         }
1282
1283         for (dominated_bb = bb->dominated; dominated_bb != NULL; dominated_bb = dominated_bb->next) {
1284                 process_block ((MonoBasicBlock*) (dominated_bb->data), area);
1285         }
1286
1287         remove_change_from_evaluation_area (&(additional_relations.relation1));
1288         remove_change_from_evaluation_area (&(additional_relations.relation2));
1289 }
1290
1291
1292
1293 /**
1294  * mono_perform_abc_removal:
1295  * @cfg: Control Flow Graph
1296  *
1297  * Performs the ABC removal from a cfg in SSA form.
1298  * It does the following:
1299  * - Prepare the evaluation area
1300  * - Allocate memory for the relation graph in the evaluation area
1301  *   (of course, only for variable definitions) and summarize there all
1302  *   variable definitions
1303  * - Allocate memory for the evaluation contexts in the evaluation area
1304  * - Recursively process all the BBs in the dominator tree (it is enough
1305  *   to invoke the processing on the entry BB)
1306  *
1307  * cfg: the method code
1308  */
1309 void
1310 mono_perform_abc_removal (MonoCompile *cfg)
1311 {
1312         MonoVariableRelationsEvaluationArea area;
1313         int i;
1314
1315         verbose_level = cfg->verbose_level;
1316
1317         if (TRACE_ABC_REMOVAL) {
1318                 printf ("Removing array bound checks in %s\n", mono_method_full_name (cfg->method, TRUE));
1319         }
1320
1321         area.cfg = cfg;
1322         area.relations = (MonoSummarizedValueRelation *)
1323                 mono_mempool_alloc (cfg->mempool, sizeof (MonoSummarizedValueRelation) * (cfg->num_varinfo) * 2);
1324         area.contexts = (MonoRelationsEvaluationContext *)
1325                 mono_mempool_alloc (cfg->mempool, sizeof (MonoRelationsEvaluationContext) * (cfg->num_varinfo));
1326         area.variable_value_kind = (MonoIntegerValueKind *)
1327                 mono_mempool_alloc (cfg->mempool, sizeof (MonoIntegerValueKind) * (cfg->num_varinfo));
1328         for (i = 0; i < cfg->num_varinfo; i++) {
1329                 area.variable_value_kind [i] = MONO_UNKNOWN_INTEGER_VALUE;
1330                 area.relations [i].relation = MONO_EQ_RELATION;
1331                 area.relations [i].relation_is_static_definition = TRUE;
1332                 area.relations [i].next = NULL;
1333                 if (cfg->vars [i]->def != NULL) {
1334                         MonoInst *value = get_variable_value_from_store_instruction (cfg->vars [i]->def, i);
1335                         if (value != NULL) {
1336                                 gboolean is_array_type;
1337                                 MonoIntegerValueKind effective_value_kind;
1338                                 MonoRelationsEvaluationRange range;
1339                                 MonoSummarizedValueRelation *type_relation;
1340
1341                                 switch (cfg->varinfo [i]->inst_vtype->type) {
1342                                 case MONO_TYPE_ARRAY:
1343                                 case MONO_TYPE_SZARRAY:
1344                                         is_array_type = TRUE;
1345                                         goto handle_array_value;
1346                                 case MONO_TYPE_OBJECT:
1347                                         is_array_type = FALSE;
1348 handle_array_value:
1349                                         summarize_array_value (&area, value, &(area.relations [i].related_value), is_array_type);
1350                                         if (TRACE_ABC_REMOVAL) {
1351                                                 printf ("Summarized variable %d as array (is_array_type = %s): ", i, (is_array_type?"TRUE":"FALSE"));
1352                                                 print_summarized_value (&(area.relations [i].related_value));
1353                                                 printf ("\n");
1354                                         }
1355                                         break;
1356                                 case MONO_TYPE_I1:
1357                                         area.variable_value_kind [i] = MONO_INTEGER_VALUE_SIZE_1;
1358                                         goto handle_integer_value;
1359                                 case MONO_TYPE_U1:
1360                                         area.variable_value_kind [i] = MONO_UNSIGNED_INTEGER_VALUE_SIZE_1;
1361                                         goto handle_integer_value;
1362                                 case MONO_TYPE_I2:
1363                                         area.variable_value_kind [i] = MONO_INTEGER_VALUE_SIZE_2;
1364                                         goto handle_integer_value;
1365                                 case MONO_TYPE_U2:
1366                                         area.variable_value_kind [i] = MONO_UNSIGNED_INTEGER_VALUE_SIZE_2;
1367                                         goto handle_integer_value;
1368                                 case MONO_TYPE_I4:
1369                                         area.variable_value_kind [i] = MONO_INTEGER_VALUE_SIZE_4;
1370                                         goto handle_integer_value;
1371                                 case MONO_TYPE_U4:
1372                                         area.variable_value_kind [i] = MONO_UNSIGNED_INTEGER_VALUE_SIZE_4;
1373                                         goto handle_integer_value;
1374                                 case MONO_TYPE_I:
1375                                         area.variable_value_kind [i] = SIZEOF_VOID_P;
1376                                         goto handle_integer_value;
1377                                 case MONO_TYPE_U:
1378                                         area.variable_value_kind [i] = (MONO_UNSIGNED_VALUE_FLAG|SIZEOF_VOID_P);
1379                                         goto handle_integer_value;
1380                                 case MONO_TYPE_I8:
1381                                         area.variable_value_kind [i] = MONO_INTEGER_VALUE_SIZE_8;
1382                                         goto handle_integer_value;
1383                                 case MONO_TYPE_U8:
1384                                         area.variable_value_kind [i] = MONO_UNSIGNED_INTEGER_VALUE_SIZE_8;
1385 handle_integer_value:
1386                                         effective_value_kind = summarize_integer_value (&area, value, &(area.relations [i].related_value), area.variable_value_kind [i]);
1387                                         MONO_MAKE_RELATIONS_EVALUATION_RANGE_WEAK (range);
1388                                         apply_value_kind_to_range (&range, area.variable_value_kind [i]);
1389                                         apply_value_kind_to_range (&range, effective_value_kind);
1390
1391                                         if (range.upper < INT_MAX) {
1392                                                 type_relation = (MonoSummarizedValueRelation *) mono_mempool_alloc (cfg->mempool, sizeof (MonoSummarizedValueRelation));
1393                                                 type_relation->relation = MONO_LE_RELATION;
1394                                                 type_relation->related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE;
1395                                                 type_relation->related_value.value.constant.value = range.upper;
1396                                                 type_relation->relation_is_static_definition = TRUE;
1397                                                 type_relation->next = area.relations [i].next;
1398                                                 area.relations [i].next = type_relation;
1399                                                 if (TRACE_ABC_REMOVAL) {
1400                                                         printf ("[var%d <= %d]", i, range.upper);
1401                                                 }
1402                                         }
1403                                         if (range.lower > INT_MIN) {
1404                                                 type_relation = (MonoSummarizedValueRelation *) mono_mempool_alloc (cfg->mempool, sizeof (MonoSummarizedValueRelation));
1405                                                 type_relation->relation = MONO_GE_RELATION;
1406                                                 type_relation->related_value.type = MONO_CONSTANT_SUMMARIZED_VALUE;
1407                                                 type_relation->related_value.value.constant.value = range.lower;
1408                                                 type_relation->relation_is_static_definition = TRUE;
1409                                                 type_relation->next = area.relations [i].next;
1410                                                 area.relations [i].next = type_relation;
1411                                                 if (TRACE_ABC_REMOVAL) {
1412                                                         printf ("[var%d >= %d]", i, range.lower);
1413                                                 }
1414                                         }
1415                                         if (TRACE_ABC_REMOVAL) {
1416                                                 printf ("Summarized variable %d: ", i);
1417                                                 print_summarized_value (&(area.relations [i].related_value));
1418                                                 printf ("\n");
1419                                         }
1420                                         break;
1421                                 default:
1422                                         MAKE_VALUE_ANY (area.relations [i].related_value);
1423                                         if (TRACE_ABC_REMOVAL) {
1424                                                 printf ("Variable %d not handled (type %d)\n", i, cfg->varinfo [i]->inst_vtype->type);
1425                                         }
1426                                 }
1427                         } else {
1428                                 MAKE_VALUE_ANY (area.relations [i].related_value);
1429                                 if (TRACE_ABC_REMOVAL) {
1430                                         printf ("Definition of variable %d is not a proper store\n", i);
1431                                 }
1432                         }
1433                 } else {
1434                         MAKE_VALUE_ANY (area.relations [i].related_value);
1435                         if (TRACE_ABC_REMOVAL) {
1436                                 printf ("Variable %d has no definition, probably it is an argument\n", i);
1437                         }
1438                 }
1439         }
1440         for (i = 0; i < cfg->num_varinfo; i++) {
1441                 if (area.relations [i].related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
1442                         int related_index = cfg->num_varinfo + i;
1443                         int related_variable = area.relations [i].related_value.value.variable.variable;
1444
1445                         area.relations [related_index].relation = MONO_EQ_RELATION;
1446                         area.relations [related_index].relation_is_static_definition = TRUE;
1447                         area.relations [related_index].related_value.type = MONO_VARIABLE_SUMMARIZED_VALUE;
1448                         area.relations [related_index].related_value.value.variable.variable = i;
1449                         area.relations [related_index].related_value.value.variable.delta = - area.relations [i].related_value.value.variable.delta;
1450
1451                         area.relations [related_index].next = area.relations [related_variable].next;
1452                         area.relations [related_variable].next = &(area.relations [related_index]);
1453
1454                         if (TRACE_ABC_REMOVAL) {
1455                                 printf ("Added symmetric summarized value for variable variable %d (to %d): ", i, related_variable);
1456                                 print_summarized_value (&(area.relations [related_index].related_value));
1457                                 printf ("\n");
1458                         }
1459                 }
1460         }
1461
1462         process_block (cfg->bblocks [0], &area);
1463 }