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