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