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