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 extern guint8 mono_burg_arity [];
  21
  22 #define TRACE_ABC_REMOVAL (verbose_level > 2)
  23 #define REPORT_ABC_REMOVAL (verbose_level > 0)
  24
  25 /*
  26  * A little hack for the verbosity level.
  27  * The verbosity level is stored in the cfg, but not all functions that must
  28  * print something see the cfg, so we store the verbosity level here at the
  29  * beginning of the algorithm.
  30  * This is not thread safe (does not handle correctly different verbosity
  31  * levels in different threads), and is not exact in case of dynamic changes
  32  * of the verbosity level...
  33  * Anyway, this is not needed, all that can happen is that something more
  34  * (or less) is logged, the result is in any case correct.
  35  */
  36 static int verbose_level;
  37
  38
  39 #define RELATION_BETWEEN_VALUES(value,related_value) (\
  40         ((value) > (related_value))? MONO_GT_RELATION :\
  41         (((value) < (related_value))? MONO_LT_RELATION : MONO_EQ_RELATION))
  42
  43 #define MAKE_VALUE_ANY(v) do{\
  44                 (v).type = MONO_ANY_SUMMARIZED_VALUE;\
  45         } while (0)
  46
  47 #define MAKE_VALUE_RELATION_ANY(r) do{\
  48                 (r)->relation = MONO_ANY_RELATION;\
  49                 MAKE_VALUE_ANY((r)->related_value);\
  50         } while (0)
  51
  52 #define INITIALIZE_VALUE_RELATION(r) do{\
  53                 MAKE_VALUE_RELATION_ANY((r));\
  54                 (r)->next = NULL;\
  55         } while (0)
  56
  57 #define MONO_NEGATED_RELATION(r) ((~(r))&MONO_ANY_RELATION)
  58 #define MONO_SYMMETRIC_RELATION(r) (((r)&MONO_EQ_RELATION)|(((r)&MONO_LT_RELATION)<<1)|((r&MONO_GT_RELATION)>>1))
  59
  60
  61
  62 static void
  63 print_relation (int relation) {
  64         int print_or = 0;
  65         printf ("(");
  66         if (relation & MONO_LT_RELATION) {
  67                 printf ("LT");
  68                 print_or = 1;
  69         }
  70         if (relation & MONO_EQ_RELATION) {
  71                 if (print_or) {
  72                         printf ("|");
  73                 }
  74                 printf ("EQ");
  75                 print_or = 1;
  76         }
  77         if (relation & MONO_GT_RELATION) {
  78                 if (print_or) {
  79                         printf ("|");
  80                 }
  81                 printf ("GT");
  82                 print_or = 1;
  83         }
  84         printf (")");
  85 }
  86
  87 static void
  88 print_summarized_value (MonoSummarizedValue *value) {
  89         switch (value->type) {
  90         case MONO_ANY_SUMMARIZED_VALUE:
  91                 printf ("ANY");
  92                 break;
  93         case MONO_CONSTANT_SUMMARIZED_VALUE:
  94                 printf ("CONSTANT %d", value->value.constant.value);
  95                 break;
  96         case MONO_VARIABLE_SUMMARIZED_VALUE:
  97                 printf ("VARIABLE %d, delta %d", value->value.variable.variable, value->value.variable.delta);
  98                 break;
  99         case MONO_PHI_SUMMARIZED_VALUE: {
 100                 int phi;
 101                 printf ("PHI (");
 102                 for (phi = 0; phi < value->value.phi.number_of_alternatives; phi++) {
 103                         if (phi) printf (",");
 104                         printf ("%d", value->value.phi.phi_alternatives [phi]);
 105                 }
 106                 printf (")");
 107                 break;
 108         }
 109         default:
 110                 g_assert_not_reached ();
 111         }
 112 }
 113
 114 static void
 115 print_summarized_value_relation (MonoSummarizedValueRelation *relation) {
 116         printf ("Relation ");
 117         print_relation (relation->relation);
 118         printf (" with value ");
 119         print_summarized_value (&(relation->related_value));
 120 }
 121
 122 #if 0
 123 static void
 124 print_summarized_value_relation_chain (MonoSummarizedValueRelation *relation) {
 125         printf ("Relations:\n");
 126         while (relation) {
 127                 print_summarized_value_relation (relation);
 128                 printf ("\n");
 129                 relation = relation->next;
 130         }
 131 }
 132 #endif
 133
 134 static void
 135 print_evaluation_context_status (MonoRelationsEvaluationStatus status) {
 136         if (status == MONO_RELATIONS_EVALUATION_NOT_STARTED) {
 137                 printf ("EVALUATION_NOT_STARTED");
 138         } else {
 139                 gboolean print_or = FALSE;
 140
 141                 printf ("(");
 142                 if (status & MONO_RELATIONS_EVALUATION_IN_PROGRESS) {
 143                         if (print_or) printf ("|");
 144                         printf ("EVALUATION_IN_PROGRESS");
 145                         print_or = TRUE;
 146                 }
 147                 if (status & MONO_RELATIONS_EVALUATION_COMPLETED) {
 148                         if (print_or) printf ("|");
 149                         printf ("EVALUATION_COMPLETED");
 150                         print_or = TRUE;
 151                 }
 152                 if (status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING) {
 153                         if (print_or) printf ("|");
 154                         printf ("RECURSIVELY_ASCENDING");
 155                         print_or = TRUE;
 156                 }
 157                 if (status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING) {
 158                         if (print_or) printf ("|");
 159                         printf ("RECURSIVELY_DESCENDING");
 160                         print_or = TRUE;
 161                 }
 162                 if (status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE) {
 163                         if (print_or) printf ("|");
 164                         printf ("RECURSIVELY_INDEFINITE");
 165                         print_or = TRUE;
 166                 }
 167                 printf (")");
 168         }
 169 }
 170
 171
 172 static void
 173 print_evaluation_context_ranges (MonoRelationsEvaluationRanges *ranges) {
 174         printf ("(ranges: zero [%d,%d], variable [%d,%d])", ranges->zero.lower, ranges->zero.upper, ranges->variable.lower, ranges->variable.upper);
 175 }
 176
 177 static void
 178 print_evaluation_context (MonoRelationsEvaluationContext *context) {
 179         printf ("Context status: ");
 180         print_evaluation_context_status (context->status);
 181         if (context->status & (MONO_RELATIONS_EVALUATION_IN_PROGRESS|MONO_RELATIONS_EVALUATION_COMPLETED)) {
 182                 print_evaluation_context_ranges (&(context->ranges));
 183         }
 184         printf ("\n");
 185 }
 186
 187 #if 0
 188 static void
 189 print_evaluation_area (MonoVariableRelationsEvaluationArea *area) {
 190         int i;
 191         printf ("Dump of evaluation area (%d variables):\n", area->cfg->num_varinfo);
 192         for (i = 0; i < area->cfg->num_varinfo; i++) {
 193                 printf ("Variable %d: ", i);
 194                 print_evaluation_context (&(area->contexts [i]));
 195                 print_summarized_value_relation_chain (&(area->relations [i]));
 196         }
 197 }
 198
 199 static void
 200 print_evaluation_area_contexts (MonoVariableRelationsEvaluationArea *area) {
 201         int i;
 202         printf ("Dump of evaluation area contexts (%d variables):\n", area->cfg->num_varinfo);
 203         for (i = 0; i < area->cfg->num_varinfo; i++) {
 204                 printf ("Variable %d: ", i);
 205                 print_evaluation_context (&(area->contexts [i]));
 206         }
 207 }
 208 #endif
 209
 210 /*
 211  * Given a MonoInst, if it is a store to a variable return the MonoInst that
 212  * represents the stored value.
 213  * If anything goes wrong, return NULL.
 214  * store: the MonoInst that should be a store
 215  * expected_variable_index: the variable where the value should be stored
 216  * return: either the stored value, or NULL
 217  */
 218 static MonoInst *
 219 get_variable_value_from_store_instruction (MonoInst *store, int expected_variable_index) {
 220         switch (store->opcode) {
 221         case CEE_STIND_REF:
 222         case CEE_STIND_I:
 223         case CEE_STIND_I4:
 224         case CEE_STIND_I1:
 225         case CEE_STIND_I2:
 226         case CEE_STIND_I8:
 227         case CEE_STIND_R4:
 228         case CEE_STIND_R8:
 229                 if (TRACE_ABC_REMOVAL) {
 230                         printf ("[store instruction found]");
 231                 }
 232                 if (store->inst_left->opcode == OP_LOCAL) {
 233                         int variable_index = store->inst_left->inst_c0;
 234                         if (TRACE_ABC_REMOVAL) {
 235                                 printf ("[value put in local %d (expected %d)]", variable_index, expected_variable_index);
 236                         }
 237                         if (variable_index == expected_variable_index) {
 238                                 return store->inst_right;
 239                         } else {
 240                                 return NULL;
 241                         }
 242                 }
 243                 else
 244                 {
 245                         return NULL;
 246                 }
 247                 break;
 248         default:
 249                 return NULL;
 250         }
 251 }
 252
 253 /*
 254  * Given a MonoInst representing a value, store it in "summarized" form.
 255  * result: the "summarized" value
 256  */
 257 static void
 258 summarize_value (MonoInst *value, MonoSummarizedValue *result) {
 259         switch (value->opcode) {
 260         case OP_ICONST:
 261                 result->type = MONO_CONSTANT_SUMMARIZED_VALUE;
 262                 result->value.constant.value = value->inst_c0;
 263                 break;
 264         case OP_LOCAL:
 265         case OP_ARG:
 266                 result->type = MONO_VARIABLE_SUMMARIZED_VALUE;
 267                 result->value.variable.variable = value->inst_c0;
 268                 result->value.variable.delta = 0;
 269                 break;
 270         case CEE_LDIND_I1:
 271         case CEE_LDIND_U1:
 272         case CEE_LDIND_I2:
 273         case CEE_LDIND_U2:
 274         case CEE_LDIND_I4:
 275         case CEE_LDIND_U4:
 276         case CEE_LDIND_REF:
 277                 if ((value->inst_left->opcode == OP_LOCAL) || (value->inst_left->opcode == OP_ARG)) {
 278                         summarize_value (value->inst_left, result);
 279                 } else {
 280                         MAKE_VALUE_ANY (*result);
 281                 }
 282                 break;
 283         case CEE_ADD: {
 284                 MonoSummarizedValue left_value;
 285                 MonoSummarizedValue right_value;
 286                 summarize_value (value->inst_left, &left_value);
 287                 summarize_value (value->inst_right, &right_value);
 288
 289                 if (left_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
 290                         if (right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
 291                                 result->type = MONO_VARIABLE_SUMMARIZED_VALUE;
 292                                 result->value.variable.variable = left_value.value.variable.variable;
 293                                 result->value.variable.delta = left_value.value.variable.delta + right_value.value.constant.value;
 294                         } else {
 295                                 MAKE_VALUE_ANY (*result);
 296                         }
 297                 } else if (right_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
 298                         if (left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
 299                                 result->type = MONO_VARIABLE_SUMMARIZED_VALUE;
 300                                 result->value.variable.variable = right_value.value.variable.variable;
 301                                 result->value.variable.delta = left_value.value.constant.value + right_value.value.variable.delta;
 302                         } else {
 303                                 MAKE_VALUE_ANY (*result);
 304                         }
 305                 } else if ((right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) && (left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE)) {
 306                         /* This should not happen if constant folding has been done */
 307                         result->type = MONO_CONSTANT_SUMMARIZED_VALUE;
 308                         result->value.constant.value = left_value.value.constant.value + right_value.value.constant.value;
 309                 } else {
 310                         MAKE_VALUE_ANY (*result);
 311                 }
 312                 break;
 313         }
 314         case CEE_SUB: {
 315                 MonoSummarizedValue left_value;
 316                 MonoSummarizedValue right_value;
 317                 summarize_value (value->inst_left, &left_value);
 318                 summarize_value (value->inst_right, &right_value);
 319
 320                 if (left_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
 321                         if (right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
 322                                 result->type = MONO_VARIABLE_SUMMARIZED_VALUE;
 323                                 result->value.variable.variable = left_value.value.variable.variable;
 324                                 result->value.variable.delta = left_value.value.variable.delta - right_value.value.constant.value;
 325                         } else {
 326                                 MAKE_VALUE_ANY (*result);
 327                         }
 328                 } else if ((right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) && (left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE)) {
 329                         /* This should not happen if constant folding has been done */
 330                         result->type = MONO_CONSTANT_SUMMARIZED_VALUE;
 331                         result->value.constant.value = left_value.value.constant.value - right_value.value.constant.value;
 332                 } else {
 333                         MAKE_VALUE_ANY (*result);
 334                 }
 335                 break;
 336         }
 337         case CEE_NEWARR:
 338                 summarize_value (value->inst_newa_len, result);
 339                 break;
 340         case CEE_LDLEN:
 341                 summarize_value (value->inst_left, result);
 342                 break;
 343         case OP_PHI:
 344                 result->type = MONO_PHI_SUMMARIZED_VALUE;
 345                 result->value.phi.number_of_alternatives = *(value->inst_phi_args);
 346                 result->value.phi.phi_alternatives = value->inst_phi_args + 1;
 347                 break;
 348         default:
 349                 MAKE_VALUE_ANY (*result);
 350         }
 351 }
 352
 353 static MonoValueRelation
 354 get_relation_from_branch_instruction (int opcode) {
 355         switch (opcode) {
 356         case CEE_BEQ:
 357                 return MONO_EQ_RELATION;
 358         case CEE_BLT:
 359         case CEE_BLT_UN:
 360                 return MONO_LT_RELATION;
 361         case CEE_BLE:
 362         case CEE_BLE_UN:
 363                 return MONO_LE_RELATION;
 364         case CEE_BGT:
 365         case CEE_BGT_UN:
 366                 return MONO_GT_RELATION;
 367         case CEE_BGE:
 368         case CEE_BGE_UN:
 369                 return MONO_GE_RELATION;
 370         case CEE_BNE_UN:
 371                 return MONO_NE_RELATION;
 372         default:
 373                 return MONO_ANY_RELATION;
 374         }
 375 }
 376
 377 /*
 378  * Given a BB, find its entry condition and put its relations in a
 379  * "MonoAdditionalVariableRelationsForBB" structure.
 380  * bb: the BB
 381  * relations: the resulting relations (entry condition of the given BB)
 382  */
 383 static void
 384 get_relations_from_previous_bb (MonoBasicBlock *bb, MonoAdditionalVariableRelationsForBB *relations) {
 385         MonoBasicBlock *in_bb;
 386         MonoInst *branch;
 387         MonoValueRelation branch_relation;
 388         MonoValueRelation symmetric_relation;
 389
 390         INITIALIZE_VALUE_RELATION (&(relations->relation1.relation));
 391         relations->relation1.relation.relation_is_static_definition = FALSE;
 392         relations->relation1.insertion_point = NULL;
 393         relations->relation1.variable = -1;
 394         INITIALIZE_VALUE_RELATION (&(relations->relation2.relation));
 395         relations->relation2.relation.relation_is_static_definition = FALSE;
 396         relations->relation2.insertion_point = NULL;
 397         relations->relation2.variable = -1;
 398
 399
 400         if (bb->in_count == 1) { /* Should write the code to "sum" conditions... */
 401                 in_bb = bb->in_bb [0];
 402                 branch = in_bb->last_ins;
 403                 if (branch == NULL) return;
 404                 branch_relation = get_relation_from_branch_instruction (branch->opcode);
 405                 if ((branch_relation != MONO_ANY_RELATION) && (branch->inst_left->opcode == OP_COMPARE)) {
 406                         MonoSummarizedValue left_value;
 407                         MonoSummarizedValue right_value;
 408                         gboolean code_path;
 409
 410                         if (branch->inst_true_bb == bb) {
 411                                 code_path = TRUE;
 412                         } else if (branch->inst_false_bb == bb) {
 413                                 code_path = FALSE;
 414                         } else {
 415                                 code_path = TRUE;
 416                                 g_assert_not_reached ();
 417                         }
 418
 419                         if (!code_path) {
 420                                 branch_relation = MONO_NEGATED_RELATION (branch_relation);
 421                         }
 422                         symmetric_relation = MONO_SYMMETRIC_RELATION (branch_relation);
 423
 424                         summarize_value (branch->inst_left->inst_left, &left_value);
 425                         summarize_value (branch->inst_left->inst_right, &right_value);
 426
 427                         if ((left_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) && ((right_value.type == MONO_VARIABLE_SUMMARIZED_VALUE)||(right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE))) {
 428                                 relations->relation1.variable = left_value.value.variable.variable;
 429                                 relations->relation1.relation.relation = branch_relation;
 430                                 relations->relation1.relation.related_value = right_value;
 431                                 if (right_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
 432                                         relations->relation1.relation.related_value.value.constant.value -= left_value.value.variable.delta;
 433                                 } else {
 434                                         relations->relation1.relation.related_value.value.variable.delta -= left_value.value.variable.delta;
 435                                 }
 436                         }
 437                         if ((right_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) && ((left_value.type == MONO_VARIABLE_SUMMARIZED_VALUE)||(left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE))) {
 438                                 relations->relation2.variable = right_value.value.variable.variable;
 439                                 relations->relation2.relation.relation = symmetric_relation;
 440                                 relations->relation2.relation.related_value = left_value;
 441                                 if (left_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
 442                                         relations->relation2.relation.related_value.value.constant.value -= right_value.value.variable.delta;
 443                                 } else {
 444                                         relations->relation2.relation.related_value.value.variable.delta -= right_value.value.variable.delta;
 445                                 }
 446                         }
 447                 }
 448         }
 449 }
 450
 451
 452 /*
 453  * Add the given relations to the evaluation area.
 454  * area: the evaluation area
 455  * change: the relations that must be added
 456  */
 457 static void
 458 apply_change_to_evaluation_area (MonoVariableRelationsEvaluationArea *area, MonoAdditionalVariableRelation *change) {
 459         MonoSummarizedValueRelation *base_relation;
 460
 461         if (change->relation.relation != MONO_ANY_RELATION) {
 462                 base_relation = &(area->relations [change->variable]);
 463                 while ((base_relation->next != NULL) && (base_relation->next->relation_is_static_definition)) {
 464                         base_relation = base_relation->next;
 465                 }
 466                 change->insertion_point = base_relation;
 467                 change->relation.next = base_relation->next;
 468                 base_relation->next = &(change->relation);
 469         }
 470 }
 471
 472 /*
 473  * Remove the given relation from the evaluation area.
 474  * change: the relation that must be removed
 475  */
 476 static void
 477 remove_change_from_evaluation_area (MonoAdditionalVariableRelation *change) {
 478         if (change->insertion_point != NULL) {
 479                 change->insertion_point->next = change->relation.next;
 480                 change->relation.next = NULL;
 481         }
 482 }
 483
 484
 485 static void
 486 clean_contexts (MonoRelationsEvaluationContext *contexts, int number) {
 487         int i;
 488         for (i = 0; i < number; i++) {
 489                 contexts [i].status = MONO_RELATIONS_EVALUATION_NOT_STARTED;
 490         }
 491 }
 492
 493
 494 /*
 495  * Perform the intersection of a range and a constant value (taking into
 496  * account the relation that the value has with the range).
 497  * range: the range that will be intersected with the value
 498  * value: the value that will be intersected with the range
 499  * relation: the relation between the range and the value
 500  */
 501 static void
 502 intersect_value( MonoRelationsEvaluationRange *range, int value, MonoValueRelation relation ) {
 503         switch (relation) {
 504         case MONO_NO_RELATION:
 505                 MONO_MAKE_RELATIONS_EVALUATION_RANGE_IMPOSSIBLE (*range);
 506                 break;
 507         case MONO_ANY_RELATION:
 508                 break;
 509         case MONO_EQ_RELATION:
 510                 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, value);
 511                 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, value);
 512                 break;
 513         case MONO_NE_RELATION: {
 514                 /* IMPROVEMENT Figure this out! (ignoring it is safe anyway) */
 515                 break;
 516         }
 517         case MONO_LT_RELATION:
 518                 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (value));
 519                 break;
 520         case MONO_LE_RELATION:
 521                 MONO_UPPER_EVALUATION_RANGE_INTERSECTION (range->upper, value);
 522                 break;
 523         case MONO_GT_RELATION:
 524                 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (value));
 525                 break;
 526         case MONO_GE_RELATION:
 527                 MONO_LOWER_EVALUATION_RANGE_INTERSECTION (range->lower, value);
 528                 break;
 529         default:
 530                 g_assert_not_reached();
 531         }
 532 }
 533
 534
 535 /*
 536  * Perform the intersection of two pairs of ranges (taking into account the
 537  * relation between the ranges and a given delta).
 538  * ranges: the ranges that will be intersected
 539  * other_ranges the other ranges that will be intersected
 540  * delta: the delta between the pairs of ranges
 541  * relation: the relation between the pairs of ranges
 542  */
 543 static void
 544 intersect_ranges( MonoRelationsEvaluationRanges *ranges, MonoRelationsEvaluationRanges *other_ranges, int delta, MonoValueRelation relation ) {
 545         if (delta == 0) {
 546                 switch (relation) {
 547                 case MONO_NO_RELATION:
 548                         MONO_MAKE_RELATIONS_EVALUATION_RANGES_IMPOSSIBLE (*ranges);
 549                         break;
 550                 case MONO_ANY_RELATION:
 551                         break;
 552                 case MONO_EQ_RELATION:
 553                         MONO_RELATIONS_EVALUATION_RANGES_INTERSECTION (*ranges, *other_ranges);
 554                         break;
 555                 case MONO_NE_RELATION: {
 556                         /* FIXME Figure this out! (ignoring it is safe anyway) */
 557                         break;
 558                 }
 559                 case MONO_LT_RELATION:
 560                         MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->zero.upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->zero.upper));
 561                         MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->variable.upper, MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->variable.upper));
 562                         break;
 563                 case MONO_LE_RELATION:
 564                         MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->zero.upper, other_ranges->zero.upper);
 565                         MONO_UPPER_EVALUATION_RANGE_INTERSECTION (ranges->variable.upper, other_ranges->variable.upper);
 566                         break;
 567                 case MONO_GT_RELATION:
 568                         MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->zero.lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->zero.lower));
 569                         MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->variable.lower, MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL (other_ranges->variable.lower));
 570                         break;
 571                 case MONO_GE_RELATION:
 572                         MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->zero.lower, other_ranges->zero.lower);
 573                         MONO_LOWER_EVALUATION_RANGE_INTERSECTION (ranges->variable.lower, other_ranges->variable.lower);
 574                         break;
 575                 default:
 576                         g_assert_not_reached();
 577                 }
 578         } else {
 579                 MonoRelationsEvaluationRanges translated_ranges = *other_ranges;
 580                 MONO_ADD_DELTA_SAFELY_TO_RANGES (translated_ranges, delta);
 581                 intersect_ranges( ranges, &translated_ranges, FALSE, relation );
 582         }
 583 }
 584
 585 /*
 586  * Recursive method that traverses the relation graph to evaluate the
 587  * relation between two variables.
 588  * At the end of the execution, the resulting ranges are in the context of
 589  * the "starting" variable.
 590  * area: the current evaluation area (it contains the relation graph and
 591  *       memory for all the evaluation contexts is already allocated)
 592  * variable: starting variable (the value ranges in its context are the result
 593  *           of the execution of this procedure)
 594  * target_variable: the variable with respect to which the starting variable
 595  *                  is evaluated (tipically the starting variable is the index
 596  *                  and the target one is the array (which means its length))
 597  * father_context: the previous evaluation context in recursive invocations
 598  *                 (or NULL for the first invocation)
 599  */
 600 static void
 601 evaluate_relation_with_target_variable (MonoVariableRelationsEvaluationArea *area, int variable, int target_variable, MonoRelationsEvaluationContext *father_context) {
 602         MonoRelationsEvaluationContext *context = &(area->contexts [variable]);
 603
 604         // First of all, we check the evaluation status
 605         // (what must be done is *very* different in each case)
 606         switch (context->status) {
 607         case MONO_RELATIONS_EVALUATION_NOT_STARTED: {
 608                 MonoSummarizedValueRelation *relation = &(area->relations [variable]);
 609
 610                 if (TRACE_ABC_REMOVAL) {
 611                         printf ("Evaluating varible %d (target variable %d)\n", variable, target_variable);
 612                         print_summarized_value_relation (relation);
 613                         printf ("\n");
 614                 }
 615
 616                 // We properly inizialize the context
 617                 context->status = MONO_RELATIONS_EVALUATION_IN_PROGRESS;
 618                 context->father = father_context;
 619                 MONO_MAKE_RELATIONS_EVALUATION_RANGES_WEAK (context->ranges);
 620
 621                 // If we have found the target variable, we can set the range
 622                 // related to it in the context to "equal" (which is [0,0])
 623                 if (variable == target_variable) {
 624                         if (TRACE_ABC_REMOVAL) {
 625                                 printf ("Target variable reached (%d), continuing to evaluate relations with constants\n", variable);
 626                         }
 627                         context->ranges.variable.lower = 0;
 628                         context->ranges.variable.upper = 0;
 629                 }
 630
 631                 // Examine all relations for this variable (scan the list)
 632                 // The contribute of each relation will be intersected (logical and)
 633                 while (relation != NULL) {
 634                         context->current_relation = relation;
 635
 636                         if (TRACE_ABC_REMOVAL) {
 637                                 printf ("Processing (%d): ", variable);
 638                                 print_summarized_value_relation (relation);
 639                                 printf ("\n");
 640                         }
 641
 642                         // We decie what to do according the the type of the related value
 643                         switch (relation->related_value.type) {
 644                         case MONO_ANY_SUMMARIZED_VALUE:
 645                                 // No added information, skip it
 646                                 break;
 647                         case MONO_CONSTANT_SUMMARIZED_VALUE:
 648                                 // Intersect range with constant (taking into account the relation)
 649                                 intersect_value (&(context->ranges.zero), relation->related_value.value.constant.value, relation->relation);
 650                                 break;
 651                         case MONO_VARIABLE_SUMMARIZED_VALUE:
 652                                 // Generally, evaluate related variable and intersect ranges.
 653                                 // However, some check is necessary...
 654
 655                                 // If the relation is "ANY", nothing to do (no added information)
 656                                 if (relation->relation != MONO_ANY_RELATION) {
 657                                         gssize related_variable = relation->related_value.value.variable.variable;
 658                                         MonoRelationsEvaluationContext *related_context = &(area->contexts [related_variable]);
 659
 660                                         // The second condition in the "or" avoids messing with "back edges" in the graph traversal
 661                                         // (they are simply ignored instead of triggering the handling of recursion)
 662                                         if ( (related_context->status == MONO_RELATIONS_EVALUATION_NOT_STARTED) || !
 663                                                         ((related_context->current_relation->related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) &&
 664                                                         (related_context->current_relation->related_value.value.variable.variable == variable))) {
 665                                                 // Evaluate the related variable
 666                                                 evaluate_relation_with_target_variable (area, related_variable, target_variable, context);
 667
 668                                                 // Check if we are part of a recursive loop
 669                                                 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) {
 670                                                         if (TRACE_ABC_REMOVAL) {
 671                                                                 printf ("Recursivity detected for varible %d (target variable %d), status ", variable, target_variable);
 672                                                                 print_evaluation_context_status (context->status);
 673                                                         }
 674
 675                                                         // If we are, check if the evaluation of the related variable is complete
 676                                                         if (related_context->status == MONO_RELATIONS_EVALUATION_COMPLETED) {
 677                                                                 // If it is complete, we are part of a recursive definition.
 678                                                                 // Since it is a *definition* (and definitions are evaluated *before*
 679                                                                 // conditions because they are first in the list), intersection is not
 680                                                                 // strictly necessary, we simply copy the ranges and apply the delta
 681                                                                 context->ranges = related_context->ranges;
 682                                                                 MONO_ADD_DELTA_SAFELY_TO_RANGES (context->ranges, relation->related_value.value.variable.delta);
 683                                                                 context->status = MONO_RELATIONS_EVALUATION_COMPLETED;
 684                                                                 if (TRACE_ABC_REMOVAL) {
 685                                                                         printf (", ranges already computed, result: \n");
 686                                                                         print_evaluation_context_ranges (&(context->ranges));
 687                                                                         printf (" (delta is %d)\n", relation->related_value.value.variable.delta);
 688                                                                 }
 689                                                         } else {
 690                                                                 // If it is not complete, do nothing (we do not have enough information)
 691                                                                 if (TRACE_ABC_REMOVAL) {
 692                                                                         printf (", ranges not computed\n");
 693                                                                 }
 694                                                         }
 695                                                 } else {
 696                                                         // If we are not (the common case) intersect the result
 697                                                         intersect_ranges( &(context->ranges), &(related_context->ranges), relation->related_value.value.variable.delta, relation->relation );
 698                                                 }
 699                                         } else {
 700                                                 if (TRACE_ABC_REMOVAL) {
 701                                                         printf ("Relation is a back-edge in this traversal, skipping\n");
 702                                                 }
 703                                         }
 704                                 }
 705                                 break;
 706                         case MONO_PHI_SUMMARIZED_VALUE: {
 707                                 // We must compute all PHI alternatives, combining the results (with a union, which is a logical "or"),
 708                                 // and intersect this result with the ranges in the context; we must also take into account recursions
 709                                 // (with loops that can be ascending, descending, or indefinite)
 710                                 MonoRelationsEvaluationRanges phi_ranges;
 711                                 int phi;
 712                                 gboolean is_ascending = FALSE;
 713                                 gboolean is_descending = FALSE;
 714
 715                                 MONO_MAKE_RELATIONS_EVALUATION_RANGES_IMPOSSIBLE (phi_ranges);
 716                                 for (phi = 0; phi < relation->related_value.value.phi.number_of_alternatives; phi++) {
 717                                         int phi_alternative = relation->related_value.value.phi.phi_alternatives [phi];
 718                                         evaluate_relation_with_target_variable (area, phi_alternative, target_variable, context);
 719
 720                                         // This means we are part of a recursive loop
 721                                         if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) {
 722                                                 if (TRACE_ABC_REMOVAL) {
 723                                                         printf ("Recursivity detected for varible %d (target variable %d), status ", variable, target_variable);
 724                                                         print_evaluation_context_status (context->status);
 725                                                         printf ("\n");
 726                                                 }
 727                                                 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING) {
 728                                                         is_ascending = TRUE;
 729                                                 }
 730                                                 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING) {
 731                                                         is_descending = TRUE;
 732                                                 }
 733                                                 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE) {
 734                                                         is_ascending = TRUE;
 735                                                         is_descending = TRUE;
 736                                                 }
 737
 738                                                 // Clear "recursivity" bits in the status (recursion has been handled)
 739                                                 context->status = MONO_RELATIONS_EVALUATION_IN_PROGRESS;
 740                                         } else {
 741                                                 MONO_RELATIONS_EVALUATION_RANGES_UNION (phi_ranges, area->contexts [phi_alternative].ranges);
 742                                         }
 743                                 }
 744
 745                                 // Apply the effects of all recursive loops
 746                                 if (is_ascending) {
 747                                         phi_ranges.zero.upper = INT_MAX;
 748                                         phi_ranges.variable.upper = INT_MAX;
 749                                 }
 750                                 if (is_descending) {
 751                                         phi_ranges.zero.lower = INT_MIN;
 752                                         phi_ranges.variable.lower = INT_MIN;
 753                                 }
 754
 755                                 // Intersect final result
 756                                 MONO_RELATIONS_EVALUATION_RANGES_INTERSECTION (context->ranges, phi_ranges);
 757                                 break;
 758                         }
 759                         default:
 760                                 g_assert_not_reached();
 761                         }
 762
 763                         // Pass to next relation
 764                         relation = relation->next;
 765                 }
 766
 767                 // Check if any recursivity bits are still in the status, and in any case clear them
 768                 if (context->status & MONO_RELATIONS_EVALUATION_IS_RECURSIVE) {
 769                         if (TRACE_ABC_REMOVAL) {
 770                                 printf ("Recursivity for varible %d (target variable %d) discards computation, status ", variable, target_variable);
 771                                 print_evaluation_context_status (context->status);
 772                                 printf ("\n");
 773                         }
 774                         // If yes, we did not have enough information (most likely we were evaluated inside a PHI, but we also
 775                         // depended on the same PHI, which was still in evaluation...), so clear the status to "NOT_STARTED"
 776                         // (if we will be evaluated again, the PHI will be already done, so our evaluation will succeed)
 777                         context->status = MONO_RELATIONS_EVALUATION_NOT_STARTED;
 778                 } else {
 779                         if (TRACE_ABC_REMOVAL) {
 780                                 printf ("Ranges for varible %d (target variable %d) computated: ", variable, target_variable);
 781                                 print_evaluation_context_ranges (&(context->ranges));
 782                                 printf ("\n");
 783                         }
 784                         // If not (the common case) the evaluation is complete, and the result is in the context
 785                         context->status = MONO_RELATIONS_EVALUATION_COMPLETED;
 786                 }
 787                 break;
 788         }
 789         case MONO_RELATIONS_EVALUATION_IN_PROGRESS: {
 790                 // This means we are in a recursive loop
 791                 MonoRelationsEvaluationContext *current_context = father_context;
 792                 MonoRelationsEvaluationContext *last_context = context->father;
 793                 gboolean evaluation_can_be_recursive = TRUE;
 794                 gboolean evaluation_is_definition = TRUE;
 795                 int path_value = 0;
 796
 797                 if (TRACE_ABC_REMOVAL) {
 798                         printf ("Evaluation of varible %d (target variable %d) already in progress\n", variable, target_variable);
 799                         print_evaluation_context (context);
 800                         print_summarized_value_relation (context->current_relation);
 801                         printf ("\n");
 802                 }
 803
 804                 // We must check if the loop can be a recursive definition (we scan the whole loop)
 805                 while (current_context != last_context) {
 806                         if (current_context == NULL) {
 807                                 printf ("Broken recursive ring in ABC removal\n");
 808                                 g_assert_not_reached ();
 809                         }
 810
 811                         if (current_context->current_relation->relation_is_static_definition) {
 812                                 if (current_context->current_relation->related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
 813                                         path_value += current_context->current_relation->related_value.value.variable.delta;
 814                                 } else if (current_context->current_relation->related_value.type != MONO_PHI_SUMMARIZED_VALUE) {
 815                                         evaluation_can_be_recursive = FALSE;
 816                                 }
 817                         } else {
 818                                 evaluation_is_definition = FALSE;
 819                                 evaluation_can_be_recursive = FALSE;
 820                         }
 821
 822                         current_context = current_context->father;
 823                 }
 824
 825                 // If this is a recursive definition, we properly flag the status in all the involved contexts
 826                 if (evaluation_is_definition) {
 827                         MonoRelationsEvaluationStatus recursive_status;
 828                         if (evaluation_can_be_recursive) {
 829                                 if (path_value > 0) {
 830                                         recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING;
 831                                 } else if (path_value < 0) {
 832                                         recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING;
 833                                 } else {
 834                                         recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE;
 835                                 }
 836                         } else {
 837                                 recursive_status = MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE;
 838                         }
 839
 840                         if (TRACE_ABC_REMOVAL) {
 841                                 printf ("Recursivity accepted (");
 842                                 print_evaluation_context_status (recursive_status);
 843                                 printf (")\n");
 844                         }
 845
 846                         current_context = father_context;
 847                         while (current_context != last_context) {
 848                                 current_context->status |= recursive_status;
 849                                 current_context = current_context->father;
 850                         }
 851                 } else {
 852                         if (TRACE_ABC_REMOVAL) {
 853                                 printf ("Recursivity rejected (some relation in the cycle is not a defintion)\n");
 854                         }
 855                 }
 856                 break;
 857         }
 858         case MONO_RELATIONS_EVALUATION_COMPLETED: {
 859                 return;
 860         }
 861         default:
 862                 if (TRACE_ABC_REMOVAL) {
 863                         printf ("Varible %d (target variable %d) already in a recursive ring, skipping\n", variable, target_variable);
 864                         print_evaluation_context (context);
 865                         print_summarized_value_relation (context->current_relation);
 866                         printf ("\n");
 867                 }
 868                 break;
 869         }
 870
 871 }
 872
 873
 874 /*
 875  * Attempt the removal of bounds checks from a MonoInst.
 876  * inst: the MonoInst
 877  * area: the current evaluation area (it contains the relation graph and
 878  *       memory for all the evaluation contexts is already allocated)
 879  */
 880 static void
 881 remove_abc_from_inst (MonoInst *inst, MonoVariableRelationsEvaluationArea *area) {
 882         if (inst->opcode == CEE_LDELEMA) {
 883                 MonoInst *array_inst = inst->inst_left;
 884                 MonoInst *index_inst = inst->inst_right;
 885
 886                 // The array must be a local variable and the index must be a properly summarized value
 887                 if ((array_inst->opcode == CEE_LDIND_REF) &&
 888                                 ((array_inst->inst_left->opcode == OP_LOCAL)||(array_inst->inst_left->opcode == OP_ARG))) {
 889                         gssize array_variable = array_inst->inst_left->inst_c0;
 890                         MonoRelationsEvaluationContext *array_context = &(area->contexts [array_variable]);
 891                         MonoSummarizedValue index_value;
 892
 893                         summarize_value (index_inst, &index_value);
 894                         if (index_value.type == MONO_CONSTANT_SUMMARIZED_VALUE) {
 895                                 // The easiest case: we just evaluate the array length, to see if it has some relation
 896                                 // with the index constant, and act accordingly
 897
 898                                 clean_contexts (area->contexts, area->cfg->num_varinfo);
 899                                 evaluate_relation_with_target_variable (area, array_variable, array_variable, NULL);
 900
 901                                 if ((index_value.value.constant.value >= 0) && (index_value.value.constant.value < array_context->ranges.zero.lower)) {
 902                                         if (REPORT_ABC_REMOVAL) {
 903                                                 printf ("ARRAY-ACCESS: removed bounds check on array %d with constant index %d in method %s\n",
 904                                                                 array_variable, index_value.value.constant.value, mono_method_full_name (area->cfg->method, TRUE));
 905                                         }
 906                                         inst->flags |= (MONO_INST_NORANGECHECK);
 907                                 }
 908                         } else if (index_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
 909                                 // The common case: we must evaluate both the index and the array length, and check for relevant
 910                                 // relations both through variable definitions and as constant definitions
 911
 912                                 gssize index_variable = index_value.value.variable.variable;
 913                                 MonoRelationsEvaluationContext *index_context = &(area->contexts [index_variable]);
 914
 915                                 clean_contexts (area->contexts, area->cfg->num_varinfo);
 916
 917                                 evaluate_relation_with_target_variable (area, index_variable, array_variable, NULL);
 918                                 evaluate_relation_with_target_variable (area, array_variable, array_variable, NULL);
 919
 920                                 MONO_SUB_DELTA_SAFELY_FROM_RANGES (index_context->ranges, index_value.value.variable.delta);
 921
 922                                 if (index_context->ranges.zero.lower >= 0) {
 923                                         if (TRACE_ABC_REMOVAL) {
 924                                                 printf ("ARRAY-ACCESS: Removed lower bound check on array %d with index %d\n", array_variable, index_variable);
 925                                         }
 926                                         if ((index_context->ranges.variable.upper < 0)||(index_context->ranges.zero.upper < array_context->ranges.zero.lower)) {
 927                                                 if (REPORT_ABC_REMOVAL) {
 928                                                         printf ("ARRAY-ACCESS: removed bounds check on array %d with index %d in method %s\n",
 929                                                                         array_variable, index_variable, mono_method_full_name (area->cfg->method, TRUE));
 930                                                 }
 931                                                 inst->flags |= (MONO_INST_NORANGECHECK);
 932                                         }
 933                                 }
 934                                 if (TRACE_ABC_REMOVAL) {
 935                                         if (index_context->ranges.variable.upper < 0) {
 936                                                 printf ("ARRAY-ACCESS: Removed upper bound check (through variable) on array %d with index %d\n", array_variable, index_variable);
 937                                         }
 938                                         if (index_context->ranges.zero.upper < array_context->ranges.zero.lower) {
 939                                                 printf ("ARRAY-ACCESS: Removed upper bound check (through constant) on array %d with index %d\n", array_variable, index_variable);
 940                                         }
 941                                 }
 942                         }
 943
 944                 }
 945         }
 946 }
 947
 948 /*
 949  * Recursively scan a tree of MonoInst looking for array accesses.
 950  * inst: the root of the MonoInst tree
 951  * area: the current evaluation area (it contains the relation graph and
 952  *       memory for all the evaluation contexts is already allocated)
 953  */
 954 static void
 955 process_inst (MonoInst *inst, MonoVariableRelationsEvaluationArea *area) {
 956         if (inst->opcode == CEE_LDELEMA) { /* Handle OP_LDELEMA2D, too */
 957                 if (TRACE_ABC_REMOVAL) {
 958                         printf ("Attempting check removal...\n");
 959                 }
 960
 961                 remove_abc_from_inst (inst, area);
 962         }
 963
 964         if (mono_burg_arity [inst->opcode]) {
 965                 process_inst (inst->inst_left, area);
 966                 if (mono_burg_arity [inst->opcode] > 1) {
 967                         process_inst (inst->inst_right, area);
 968                 }
 969         }
 970 }
 971
 972
 973
 974
 975 /*
 976  * Process a BB removing bounds checks from array accesses.
 977  * It does the following (in sequence):
 978  * - Get the BB entry condition
 979  * - Add its relations to the relation graph in the evaluation area
 980  * - Process all the MonoInst trees in the BB
 981  * - Recursively process all the children BBs in the dominator tree
 982  * - Remove the relations previously added to the relation graph
 983  *
 984  * bb: the BB that must be processed
 985  * area: the current evaluation area (it contains the relation graph and
 986  *       memory for all the evaluation contexts is already allocated)
 987  */
 988 static void
 989 process_block (MonoBasicBlock *bb, MonoVariableRelationsEvaluationArea *area) {
 990         int inst_index;
 991         MonoInst *current_inst;
 992         MonoAdditionalVariableRelationsForBB additional_relations;
 993         GList *dominated_bb;
 994
 995         if (TRACE_ABC_REMOVAL) {
 996                 printf ("Processing block %d [dfn %d]...\n", bb->block_num, bb->dfn);
 997         }
 998
 999         get_relations_from_previous_bb (bb, &additional_relations);
1000         if (TRACE_ABC_REMOVAL) {
1001                 if (additional_relations.relation1.relation.relation != MONO_ANY_RELATION) {
1002                         printf ("Adding relation 1 on variable %d: ", additional_relations.relation1.variable);
1003                         print_summarized_value_relation (&(additional_relations.relation1.relation));
1004                         printf ("\n");
1005                 }
1006                 if (additional_relations.relation2.relation.relation != MONO_ANY_RELATION) {
1007                         printf ("Adding relation 2 on variable %d: ", additional_relations.relation2.variable);
1008                         print_summarized_value_relation (&(additional_relations.relation2.relation));
1009                         printf ("\n");
1010                 }
1011         }
1012         apply_change_to_evaluation_area (area, &(additional_relations.relation1));
1013         apply_change_to_evaluation_area (area, &(additional_relations.relation2));
1014
1015         inst_index = 0;
1016         current_inst = bb->code;
1017         while (current_inst != NULL) {
1018                 if (TRACE_ABC_REMOVAL) {
1019                         printf ("Processing instruction %d\n", inst_index);
1020                         inst_index++;
1021                 }
1022
1023                 process_inst (current_inst, area);
1024
1025                 current_inst = current_inst->next;
1026         }
1027
1028
1029         if (TRACE_ABC_REMOVAL) {
1030                 printf ("Processing block %d [dfn %d] done.\n", bb->block_num, bb->dfn);
1031         }
1032
1033         for (dominated_bb = g_list_first (bb->dominated); dominated_bb != NULL; dominated_bb = g_list_next (dominated_bb)) {
1034                 process_block ((MonoBasicBlock*) (dominated_bb->data), area);
1035         }
1036
1037         remove_change_from_evaluation_area (&(additional_relations.relation1));
1038         remove_change_from_evaluation_area (&(additional_relations.relation2));
1039 }
1040
1041
1042
1043 /**
1044  * mono_perform_abc_removal:
1045  * @cfg: Control Flow Graph
1046  *
1047  * Performs the ABC removal from a cfg in SSA form.
1048  * It does the following:
1049  * - Prepare the evaluation area
1050  * - Allocate memory for the relation graph in the evaluation area
1051  *   (of course, only for variable definitions) and summarize there all
1052  *   variable definitions
1053  * - Allocate memory for the evaluation contexts in the evaluation area
1054  * - Recursively process all the BBs in the dominator tree (it is enough
1055  *   to invoke the processing on the entry BB)
1056  *
1057  * cfg: the method code
1058  */
1059 void
1060 mono_perform_abc_removal (MonoCompile *cfg)
1061 {
1062         MonoVariableRelationsEvaluationArea area;
1063         int i;
1064
1065         verbose_level = cfg->verbose_level;
1066
1067         if (TRACE_ABC_REMOVAL) {
1068                 printf ("Removing array bound checks in %s\n", mono_method_full_name (cfg->method, TRUE));
1069         }
1070
1071         area.cfg = cfg;
1072         area.relations = (MonoSummarizedValueRelation *)
1073                 alloca (sizeof (MonoSummarizedValueRelation) * (cfg->num_varinfo) * 2);
1074         area.contexts = (MonoRelationsEvaluationContext *)
1075                 alloca (sizeof (MonoRelationsEvaluationContext) * (cfg->num_varinfo));
1076         for (i = 0; i < cfg->num_varinfo; i++) {
1077                 area.relations [i].relation = MONO_EQ_RELATION;
1078                 area.relations [i].relation_is_static_definition = TRUE;
1079                 area.relations [i].next = NULL;
1080                 if (cfg->vars [i]->def != NULL) {
1081                         MonoInst *value = get_variable_value_from_store_instruction (cfg->vars [i]->def, i);
1082                         if (value != NULL) {
1083                                 summarize_value (value, &(area.relations [i].related_value));
1084                                 if (TRACE_ABC_REMOVAL) {
1085                                         printf ("Summarized variable %d: ", i);
1086                                         print_summarized_value (&(area.relations [i].related_value));
1087                                         printf ("\n");
1088                                 }
1089                         } else {
1090                                 MAKE_VALUE_ANY (area.relations [i].related_value);
1091                                 if (TRACE_ABC_REMOVAL) {
1092                                         printf ("Definition of variable %d is not a proper store\n", i);
1093                                 }
1094                         }
1095                 } else {
1096                         MAKE_VALUE_ANY (area.relations [i].related_value);
1097                         if (TRACE_ABC_REMOVAL) {
1098                                 printf ("Variable %d has no definition, probably it is an argument\n", i);
1099                         }
1100                 }
1101         }
1102         for (i = 0; i < cfg->num_varinfo; i++) {
1103                 if (area.relations [i].related_value.type == MONO_VARIABLE_SUMMARIZED_VALUE) {
1104                         int related_index = cfg->num_varinfo + i;
1105                         int related_variable = area.relations [i].related_value.value.variable.variable;
1106
1107                         area.relations [related_index].relation = MONO_EQ_RELATION;
1108                         area.relations [related_index].relation_is_static_definition = TRUE;
1109                         area.relations [related_index].related_value.type = MONO_VARIABLE_SUMMARIZED_VALUE;
1110                         area.relations [related_index].related_value.value.variable.variable = i;
1111                         area.relations [related_index].related_value.value.variable.delta = - area.relations [i].related_value.value.variable.delta;
1112
1113                         area.relations [related_index].next = area.relations [related_variable].next;
1114                         area.relations [related_variable].next = &(area.relations [related_index]);
1115
1116                         if (TRACE_ABC_REMOVAL) {
1117                                 printf ("Added symmetric summarized value for variable variable %d (to %d): ", i, related_variable);
1118                                 print_summarized_value (&(area.relations [related_index].related_value));
1119                                 printf ("\n");
1120                         }
1121                 }
1122         }
1123
1124         process_block (cfg->bblocks [0], &area);
1125 }
1126