mono/mini/ssapre.c

   1 /*
   2  * ssapre.h: SSA Partial Redundancy Elimination
   3  *
   4  * Author:
   5  *   Massimiliano Mantione (massi@ximian.com)
   6  *
   7  * (C) 2004 Novell, Inc.  http://www.novell.com
   8  */
   9
  10 #include <string.h>
  11 #include <stdio.h>
  12 #include <math.h>
  13
  14 #include <mono/metadata/debug-helpers.h>
  15 #include <mono/metadata/opcodes.h>
  16
  17 #include "config.h"
  18
  19 #ifndef DISABLE_SSA
  20 #include "inssel.h"
  21
  22 #include "ssapre.h"
  23
  24 /* Logging conditions */
  25 #define DUMP_LEVEL (4)
  26 #define TRACE_LEVEL (3)
  27 #define STATISTICS_LEVEL (2)
  28 #define LOG_LEVEL (1)
  29 #define DUMP_SSAPRE (area->cfg->verbose_level >= DUMP_LEVEL)
  30 #define TRACE_SSAPRE (area->cfg->verbose_level >= TRACE_LEVEL)
  31 #define STATISTICS_SSAPRE (area->cfg->verbose_level >= STATISTICS_LEVEL)
  32 #define LOG_SSAPRE (area->cfg->verbose_level >= LOG_LEVEL)
  33
  34 /* "Bottom" symbol definition (see paper) */
  35 #define BOTTOM_REDUNDANCY_CLASS (-1)
  36
  37 /* Various printing functions... */
  38 static void
  39 print_argument (MonoSsapreExpressionArgument *argument) {
  40         switch (argument->type) {
  41                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY:
  42                         printf ("ANY");
  43                         break;
  44                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_NOT_PRESENT:
  45                         printf ("NONE");
  46                         break;
  47                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE:
  48                         printf ("ORIGINAL_VARIABLE %d", argument->argument.original_variable);
  49                         break;
  50                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE:
  51                         printf ("SSA_VARIABLE %d", argument->argument.ssa_variable);
  52                         break;
  53                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT:
  54                         printf ("INTEGER_CONSTANT %d", argument->argument.integer_constant);
  55                         break;
  56                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_LONG_COSTANT:
  57                         printf ("LONG_COSTANT %lld", (long long)*(argument->argument.long_constant));
  58                         break;
  59                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT:
  60                         printf ("FLOAT_COSTANT %f", *(argument->argument.float_constant));
  61                         break;
  62                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT:
  63                         printf ("DOUBLE_COSTANT %f", *(argument->argument.double_constant));
  64                         break;
  65                 default:
  66                         printf ("UNKNOWN: %d", argument->type);
  67         }
  68 }
  69
  70
  71 static void
  72 print_expression_description (MonoSsapreExpressionDescription *expression_description) {
  73         if (expression_description->opcode != 0) {
  74                 printf ("%s ([", mono_inst_name (expression_description->opcode) );
  75                 print_argument (&(expression_description->left_argument));
  76                 printf ("],[");
  77                 print_argument (&(expression_description->right_argument));
  78                 printf ("])");
  79         } else {
  80                 printf ("ANY");
  81         }
  82 }
  83
  84 #if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
  85 static void
  86 snprint_argument (GString *string, MonoSsapreExpressionArgument *argument) {
  87         switch (argument->type) {
  88                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY:
  89                         g_string_append_printf (string, "ANY");
  90                         break;
  91                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_NOT_PRESENT:
  92                         g_string_append_printf (string, "NONE");
  93                         break;
  94                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE:
  95                         g_string_append_printf (string, "ORIGINAL_VARIABLE %d", argument->argument.original_variable);
  96                         break;
  97                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE:
  98                         g_string_append_printf (string, "SSA_VARIABLE %d", argument->argument.ssa_variable);
  99                         break;
 100                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT:
 101                         g_string_append_printf (string, "INTEGER_CONSTANT %d", argument->argument.integer_constant);
 102                         break;
 103                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_LONG_COSTANT:
 104                         g_string_append_printf (string, "LONG_COSTANT %lld", *(argument->argument.long_constant));
 105                         break;
 106                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT:
 107                         g_string_append_printf (string, "FLOAT_COSTANT %f", *(argument->argument.float_constant));
 108                         break;
 109                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT:
 110                         g_string_append_printf (string, "DOUBLE_COSTANT %f", *(argument->argument.double_constant));
 111                         break;
 112                 default:
 113                         g_string_append_printf (string, "UNKNOWN: %d", argument->type);
 114         }
 115 }
 116
 117 static void
 118 snprint_expression_description (GString *string, MonoSsapreExpressionDescription *expression_description) {
 119         if (expression_description->opcode != 0) {
 120                 g_string_append_printf (string, "%s ([", mono_inst_name (expression_description->opcode) );
 121                 snprint_argument (string, &(expression_description->left_argument));
 122                 g_string_append_printf (string, "],[");
 123                 snprint_argument (string, &(expression_description->right_argument));
 124                 g_string_append_printf (string, "])");
 125         } else {
 126                 g_string_append_printf (string, "ANY");
 127         }
 128 }
 129 #endif
 130
 131 #define GBOOLEAN_TO_STRING(b) ((b)?"TRUE":"FALSE")
 132
 133 static void
 134 print_expression_occurrence (MonoSsapreExpressionOccurrence *occurrence, int number) {
 135         printf (" ([%d][bb %d [ID %d]][class %d]: ", number, occurrence->bb_info->cfg_dfn, occurrence->bb_info->bb->block_num, occurrence->redundancy_class);
 136         print_expression_description (&(occurrence->description));
 137         if (occurrence->is_first_in_bb) {
 138                 printf (" [FIRST in BB]");
 139         }
 140         if (occurrence->is_last_in_bb) {
 141                 printf (" [LAST in BB]");
 142         }
 143         printf (" (save = %s)", GBOOLEAN_TO_STRING (occurrence->save));
 144         printf (" (reload = %s)", GBOOLEAN_TO_STRING (occurrence->reload));
 145         printf ("\n");
 146         occurrence = occurrence->next;
 147 }
 148
 149 static void
 150 print_expression_occurrences (MonoSsapreExpressionOccurrence *occurrences) {
 151         int i = 0;
 152         while (occurrences != NULL) {
 153                 i++;
 154                 print_expression_occurrence (occurrences, i);
 155                 occurrences = occurrences->next;
 156         }
 157 }
 158
 159 static void
 160 print_worklist (MonoSsapreExpression *expression) {
 161         if (expression != NULL) {
 162                 print_worklist (expression->previous);
 163
 164                 printf ("{%d}: ", expression->tree_size);
 165                 print_expression_description (&(expression->description));
 166                 printf ("\n");
 167                 print_expression_occurrences (expression->occurrences);
 168
 169                 print_worklist (expression->next);
 170         }
 171 }
 172
 173 static void
 174 print_bb_info (MonoSsapreBBInfo *bb_info, gboolean print_occurrences) {
 175         int i;
 176         MonoSsapreExpressionOccurrence *current_occurrence = bb_info->first_expression_in_bb;
 177
 178         printf ("bb %d [ID %d]: IN { ", bb_info->cfg_dfn, bb_info->bb->block_num);
 179         for (i = 0; i < bb_info->in_count; i++) {
 180                 printf ("%d [ID %d] ", bb_info->in_bb [i]->cfg_dfn, bb_info->in_bb [i]->bb->block_num);
 181         }
 182         printf ("}, OUT {");
 183         for (i = 0; i < bb_info->out_count; i++) {
 184                 printf ("%d [ID %d] ", bb_info->out_bb [i]->cfg_dfn, bb_info->out_bb [i]->bb->block_num);
 185         }
 186         printf ("}");
 187         if (bb_info->next_interesting_bb != NULL) {
 188                 printf (", NEXT %d [ID %d]", bb_info->next_interesting_bb->cfg_dfn, bb_info->next_interesting_bb->bb->block_num);
 189         }
 190         if (bb_info->dt_covered_by_interesting_BBs) {
 191                 printf (" (COVERED)");
 192         } else {
 193                 printf (" (NEVER DOWN SAFE)");
 194         }
 195         printf ("\n");
 196         if (bb_info->has_phi) {
 197                 printf (" PHI, class %d [ ", bb_info->phi_redundancy_class);
 198                 for (i = 0; i < bb_info->in_count; i++) {
 199                         int argument_class = bb_info->phi_arguments_classes [i];
 200                         if (argument_class != BOTTOM_REDUNDANCY_CLASS) {
 201                                 printf ("%d ", argument_class);
 202                         } else {
 203                                 printf ("BOTTOM ");
 204                         }
 205                 }
 206                 printf ("]\n(phi_defines_a_real_occurrence:%s) (phi_is_down_safe:%s) (phi_can_be_available:%s) (phi_is_later:%s)\n",
 207                                 GBOOLEAN_TO_STRING (bb_info->phi_defines_a_real_occurrence), GBOOLEAN_TO_STRING (bb_info->phi_is_down_safe),
 208                                 GBOOLEAN_TO_STRING (bb_info->phi_can_be_available), GBOOLEAN_TO_STRING (bb_info->phi_is_later));
 209         }
 210         if (print_occurrences) {
 211                 i = 0;
 212                 while ((current_occurrence != NULL) && (current_occurrence->bb_info == bb_info)) {
 213                         print_expression_occurrence (current_occurrence, i);
 214                         current_occurrence = current_occurrence->next;
 215                         i++;
 216                 }
 217         }
 218         if (bb_info->has_phi_argument) {
 219                 printf (" PHI ARGUMENT, class ");
 220                 if (bb_info->phi_argument_class != BOTTOM_REDUNDANCY_CLASS) {
 221                         printf ("%d ", bb_info->phi_argument_class);
 222                 } else {
 223                         printf ("BOTTOM ");
 224                 }
 225                 if (bb_info->phi_argument_defined_by_real_occurrence != NULL) {
 226                         printf ("(Defined by real occurrence %d)", bb_info->phi_argument_defined_by_real_occurrence->redundancy_class);
 227                 } else if (bb_info->phi_argument_defined_by_phi != NULL) {
 228                         printf ("(Defined by phi %d)", bb_info->phi_argument_defined_by_phi->phi_redundancy_class);
 229                 } else {
 230                         printf ("(Undefined)");
 231                 }
 232                 printf (" (real occurrence arguments: left ");
 233                 if (bb_info->phi_argument_left_argument_version != BOTTOM_REDUNDANCY_CLASS) {
 234                         printf ("%d ", bb_info->phi_argument_left_argument_version);
 235                 } else {
 236                         printf ("NONE ");
 237                 }
 238                 printf (", right ");
 239                 if (bb_info->phi_argument_right_argument_version != BOTTOM_REDUNDANCY_CLASS) {
 240                         printf ("%d ", bb_info->phi_argument_right_argument_version);
 241                 } else {
 242                         printf ("NONE ");
 243                 }
 244                 printf (")\n(phi_argument_has_real_use:%s) (phi_argument_needs_insert:%s) (phi_argument_has_been_processed:%s)\n",
 245                                 GBOOLEAN_TO_STRING (bb_info->phi_argument_has_real_use), GBOOLEAN_TO_STRING (bb_info->phi_argument_needs_insert),
 246                                 GBOOLEAN_TO_STRING (bb_info->phi_argument_has_been_processed));
 247         }
 248 }
 249
 250 static void
 251 print_bb_infos (MonoSsapreWorkArea *area) {
 252         int i;
 253         for (i = 0; i < area->num_bblocks; i++) {
 254                 MonoSsapreBBInfo *bb_info = &(area->bb_infos [i]);
 255                 print_bb_info (bb_info, TRUE);
 256         }
 257 }
 258
 259 static void
 260 print_interesting_bb_infos (MonoSsapreWorkArea *area) {
 261         MonoSsapreBBInfo *current_bb;
 262
 263         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
 264                 print_bb_info (current_bb, FALSE);
 265         }
 266 }
 267
 268 static void dump_code (MonoSsapreWorkArea *area) {
 269         int i;
 270
 271         for (i = 0; i < area->num_bblocks; i++) {
 272                 MonoSsapreBBInfo *current_bb = &(area->bb_infos [i]);
 273                 MonoInst *current_inst;
 274
 275                 print_bb_info (current_bb, TRUE);
 276                 MONO_BB_FOR_EACH_INS (current_bb->bb, current_inst)
 277                         mono_print_tree_nl (current_inst);
 278         }
 279 }
 280
 281 /*
 282  * Given a MonoInst, it tries to describe it as an expression argument.
 283  * If this is not possible, the result will be of type
 284  * MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY.
 285  */
 286 static void
 287 analyze_argument (MonoInst *argument, MonoSsapreExpressionArgument *result) {
 288         switch (argument->opcode) {
 289         case CEE_LDIND_I1:
 290         case CEE_LDIND_U1:
 291         case CEE_LDIND_I2:
 292         case CEE_LDIND_U2:
 293         case CEE_LDIND_I4:
 294         case CEE_LDIND_U4:
 295         case CEE_LDIND_I8:
 296         case CEE_LDIND_I:
 297         case CEE_LDIND_R4:
 298         case CEE_LDIND_R8:
 299         case CEE_LDIND_REF:
 300                 if ((argument->inst_left->opcode == OP_LOCAL) || (argument->inst_left->opcode == OP_ARG)) {
 301                         result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE;
 302                         result->argument.ssa_variable = argument->inst_left->inst_c0;
 303                 } else {
 304                         result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 305                 }
 306                 break;
 307         case OP_ICONST:
 308                 result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT;
 309                 result->argument.integer_constant = argument->inst_c0;
 310                 break;
 311         case OP_I8CONST:
 312                 result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_LONG_COSTANT;
 313                 result->argument.long_constant = &(argument->inst_l);
 314                 break;
 315         case OP_R4CONST:
 316                 if (! isnan (*((float*)argument->inst_p0))) {
 317                         result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT;
 318                         result->argument.float_constant = (float*)argument->inst_p0;
 319                 } else {
 320                         result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 321                 }
 322                 break;
 323         case OP_R8CONST:
 324                 if (! isnan (*((double*)argument->inst_p0))) {
 325                         result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT;
 326                         result->argument.double_constant = (double*)argument->inst_p0;
 327                 } else {
 328                         result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 329                 }
 330                 break;
 331         default:
 332                 result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 333         }
 334 }
 335
 336
 337 /*
 338  * Given a MonoInst, it tries to describe it as an expression.
 339  * If this is not possible, the result will have opcode 0.
 340  */
 341 static void
 342 analyze_expression (MonoInst *expression, MonoSsapreExpressionDescription *result) {
 343         switch (expression->opcode) {
 344 #define SSAPRE_SPECIFIC_OPS 1
 345 #define OPDEF(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10) case a1:
 346 #include "simple-cee-ops.h"
 347 #undef OPDEF
 348 #define MINI_OP(a1,a2) case a1:
 349 #include "simple-mini-ops.h"
 350 #undef MINI_OP
 351 #undef SSAPRE_SPECIFIC_OPS
 352                 if ( (expression->type == STACK_I4) ||
 353                                 (expression->type == STACK_PTR) ||
 354                                 (expression->type == STACK_MP) ||
 355                                 (expression->type == STACK_I8) ||
 356                                 (expression->type == STACK_R8) ) {
 357                         if (mono_burg_arity [expression->opcode] > 0) {
 358                                 result->opcode = expression->opcode;
 359                                 analyze_argument (expression->inst_left, &(result->left_argument));
 360                                 if (mono_burg_arity [expression->opcode] > 1) {
 361                                         analyze_argument (expression->inst_right, &(result->right_argument));
 362                                 } else {
 363                                         result->right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_NOT_PRESENT;
 364                                 }
 365                         } else {
 366                                 result->opcode = 0;
 367                         }
 368                 } else {
 369                         result->opcode = 0;
 370                         //~ if (expression->type != 0) {
 371                                 //~ MonoType *type = mono_type_from_stack_type (expression);
 372                                 //~ printf ("SSAPRE refuses opcode %s (%d) with type %s (%d)\n", mono_inst_name (expression->opcode), expression->opcode, mono_type_full_name (type), expression->type);
 373                         //~ } else {
 374                                 //~ printf ("SSAPRE cannot really handle expression of opcode %s (%d)\n", mono_inst_name (expression->opcode), expression->opcode);
 375                         //~ }
 376                 }
 377                 break;
 378         default:
 379                 result->opcode = 0;
 380                 result->left_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 381                 result->right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 382         }
 383         //~ switch (expression->opcode) {
 384         //~ case CEE_ADD:
 385                 //~ if ((result->left_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT) &&
 386                                 //~ (result->right_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT)) {
 387                         //~ break;
 388                 //~ }
 389         //~ case CEE_LDELEMA:
 390         //~ case CEE_LDLEN:
 391                 //~ result->opcode = 0;
 392                 //~ result->left_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 393                 //~ result->right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 394         //~ }
 395 }
 396
 397 /*
 398  * Given an expression description, if any of its arguments has type
 399  * MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE it transforms it to a
 400  * MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE, converting the
 401  * variable index to its "original" one.
 402  * The resulting description is OK for a "MonoSsapreExpression" (the
 403  * initial description came from a "MonoSsapreExpressionOccurrence").
 404  */
 405 static void
 406 convert_ssa_variables_to_original_names (MonoSsapreExpressionDescription *result, MonoSsapreExpressionDescription *expression, MonoCompile *cfg) {
 407         gssize original_variable;
 408
 409         result->opcode = expression->opcode;
 410         if (expression->left_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE) {
 411                 result->left_argument = expression->left_argument;
 412         } else {
 413                 result->left_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE;
 414                 original_variable = MONO_VARINFO (cfg, expression->left_argument.argument.ssa_variable)->reg;
 415                 if (original_variable >= 0) {
 416                         result->left_argument.argument.original_variable = original_variable;
 417                 } else {
 418                         result->left_argument.argument.original_variable = expression->left_argument.argument.ssa_variable;
 419                 }
 420         }
 421         if (expression->right_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE) {
 422                 result->right_argument = expression->right_argument;
 423         } else {
 424                 result->right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE;
 425                 original_variable = MONO_VARINFO (cfg, expression->right_argument.argument.ssa_variable)->reg;
 426                 if (original_variable >= 0) {
 427                         result->right_argument.argument.original_variable = original_variable;
 428                 } else {
 429                         result->right_argument.argument.original_variable = expression->right_argument.argument.ssa_variable;
 430                 }
 431         }
 432 }
 433
 434 /*
 435  * Given a MonoInst, checks if it is a phi definition.
 436  */
 437 static gboolean
 438 is_phi_definition (MonoInst *definition) {
 439         if (definition != NULL) {
 440                 switch (definition->opcode) {
 441                 case CEE_STIND_REF:
 442                 case CEE_STIND_I:
 443                 case CEE_STIND_I4:
 444                 case CEE_STIND_I1:
 445                 case CEE_STIND_I2:
 446                 case CEE_STIND_I8:
 447                 case CEE_STIND_R4:
 448                 case CEE_STIND_R8:
 449                         if ((definition->inst_left->opcode == OP_LOCAL) &&
 450                                         (definition->inst_right->opcode == OP_PHI)) {
 451                                 return TRUE;
 452                         } else {
 453                                 return FALSE;
 454                         }
 455                 default:
 456                         return FALSE;
 457                 }
 458         } else {
 459                 return FALSE;
 460         }
 461 }
 462
 463 /*
 464  * Given a variable index, checks if it is a phi definition
 465  * (it assumes the "area" is visible).
 466  */
 467 #define IS_PHI_DEFINITION(v) is_phi_definition (MONO_VARINFO (area->cfg, v)->def)
 468
 469 /*
 470  * Given a variable index, checks if it is a phi definition.
 471  * If it is so, it returns the array of integers pointed to by the phi MonoInst
 472  * (the one containing the length and the phi arguments), otherwise returns NULL.
 473  */
 474 static int*
 475 get_phi_definition (MonoCompile *cfg, gssize variable) {
 476         MonoInst *definition = MONO_VARINFO (cfg, variable)->def;
 477         if (is_phi_definition (definition) && (definition->inst_left->inst_c0 == variable)) {
 478                 return definition->inst_right->inst_phi_args;
 479         } else {
 480                 return NULL;
 481         }
 482 }
 483
 484 /*
 485  * Given a variable index, returns the BB where the variable is defined.
 486  * If the variable appears to have no definition, it returns the entry BB
 487  * (the logic is that if it has no definition it is an argument, or a sort
 488  * of constant, and in both cases it is defined in the entry BB).
 489  */
 490 static MonoSsapreBBInfo*
 491 get_bb_info_of_definition (MonoSsapreWorkArea *area, gssize variable) {
 492         MonoBasicBlock *def_bb = MONO_VARINFO (area->cfg, variable)->def_bb;
 493         if (def_bb != NULL) {
 494                 return area->bb_infos_in_cfg_dfn_order [def_bb->dfn];
 495         } else {
 496                 return area->bb_infos;
 497         }
 498 }
 499
 500 /*
 501  * Given:
 502  * - a variable index,
 503  * - a BB (the "current" BB), and
 504  * - a "phi argument index" (or index in the "in_bb" of the current BB),
 505  * it checks if the variable is a phi.
 506  * If it is so, it returns the variable index at the in_bb corresponding to
 507  * the given index, otherwise it return the variable index unchanged.
 508  * The logic is to return the variable version at the given predecessor BB.
 509  */
 510 static gssize
 511 get_variable_version_at_predecessor_bb (MonoSsapreWorkArea *area, gssize variable, MonoSsapreBBInfo *current_bb, int phi_operand) {
 512         MonoSsapreBBInfo *definition_bb = get_bb_info_of_definition (area, variable);
 513         int *phi_definition = get_phi_definition (area->cfg, variable);
 514         if ((definition_bb == current_bb) && (phi_definition != NULL)) {
 515                 return phi_definition [phi_operand + 1];
 516         } else {
 517                 return variable;
 518         }
 519 }
 520
 521 /*
 522  * Adds an expression to an autobalancing binary tree of expressions.
 523  * Returns the new tree root (it can be different from "tree" because of the
 524  * autobalancing).
 525  */
 526 static MonoSsapreExpression*
 527 add_expression_to_tree (MonoSsapreExpression *tree, MonoSsapreExpression *expression) {
 528         MonoSsapreExpression *subtree;
 529         MonoSsapreExpression **subtree_reference;
 530         int comparison;
 531         gssize max_tree_depth, max_subtree_size;
 532
 533         if (tree == NULL) {
 534                 expression->previous = NULL;
 535                 expression->next = NULL;
 536                 expression->tree_size = 1;
 537                 return expression;
 538         }
 539
 540         tree->tree_size++;
 541
 542         comparison = MONO_COMPARE_SSAPRE_EXPRESSION_DESCRIPTIONS (expression->description, tree->description);
 543         if (comparison > 0) {
 544                 if (tree->next != NULL) {
 545                         subtree = tree->next;
 546                         subtree_reference = &(tree->next);
 547                 } else {
 548                         tree->next = expression;
 549                         expression->father = tree;
 550                         expression->previous = NULL;
 551                         expression->next = NULL;
 552                         expression->tree_size = 1;
 553                         return tree;
 554                 }
 555         } else if (comparison < 0) {
 556                 if (tree->previous != NULL) {
 557                         subtree = tree->previous;
 558                         subtree_reference = &(tree->previous);
 559                 } else {
 560                         tree->previous = expression;
 561                         expression->father = tree;
 562                         expression->previous = NULL;
 563                         expression->next = NULL;
 564                         expression->tree_size = 1;
 565                         return tree;
 566                 }
 567         } else {
 568                 g_assert_not_reached ();
 569                 return NULL;
 570         }
 571
 572         MONO_SSAPRE_MAX_TREE_DEPTH (tree->tree_size, max_tree_depth);
 573         max_subtree_size = (1 << max_tree_depth) -1;
 574
 575         if (subtree->tree_size < max_subtree_size) {
 576                 *subtree_reference = add_expression_to_tree (subtree, expression);
 577                 (*subtree_reference)->father = tree;
 578                 return tree;
 579         } else {
 580                 MonoSsapreExpression *other_subtree;
 581                 MonoSsapreExpression *border_expression;
 582                 MonoSsapreExpression *border_expression_subtree;
 583                 MonoSsapreExpression **border_expression_reference_from_father;
 584                 int comparison_with_border;
 585
 586                 border_expression = subtree;
 587                 if (comparison > 0) {
 588                         other_subtree = tree->previous;
 589                         MONO_SSAPRE_GOTO_FIRST_EXPRESSION (border_expression);
 590                         border_expression_subtree = border_expression->next;
 591                         border_expression_reference_from_father = &(border_expression->father->previous);
 592                 } else if (comparison < 0) {
 593                         other_subtree = tree->next;
 594                         MONO_SSAPRE_GOTO_LAST_EXPRESSION (border_expression);
 595                         border_expression_subtree = border_expression->previous;
 596                         border_expression_reference_from_father = &(border_expression->father->next);
 597                 } else {
 598                         g_assert_not_reached ();
 599                         return NULL;
 600                 }
 601                 comparison_with_border = MONO_COMPARE_SSAPRE_EXPRESSION_DESCRIPTIONS (expression->description, border_expression->description);
 602
 603                 if ((comparison + comparison_with_border) != 0) {
 604                         MonoSsapreExpression *border_expression_iterator = border_expression->father;
 605                         while (border_expression_iterator != tree) {
 606                                 border_expression_iterator->tree_size--;
 607                                 border_expression_iterator = border_expression_iterator->father;
 608                         }
 609
 610                         if (border_expression != subtree) {
 611                                 *border_expression_reference_from_father = border_expression_subtree;
 612                         } else {
 613                                 subtree = border_expression_subtree;
 614                         }
 615                         if (border_expression_subtree != NULL) {
 616                                 border_expression_subtree->father = border_expression->father;
 617                         }
 618
 619                         if (comparison > 0) {
 620                                 border_expression->previous = add_expression_to_tree (other_subtree, tree);
 621                                 border_expression->next = add_expression_to_tree (subtree, expression);
 622                         } else if (comparison < 0) {
 623                                 border_expression->previous = add_expression_to_tree (subtree, expression);
 624                                 border_expression->next = add_expression_to_tree (other_subtree, tree);
 625                         } else {
 626                                 g_assert_not_reached ();
 627                                 return NULL;
 628                         }
 629                         border_expression->tree_size = 1 + border_expression->previous->tree_size + border_expression->next->tree_size;
 630                         return border_expression;
 631                 } else {
 632                         if (comparison > 0) {
 633                                 expression->previous = add_expression_to_tree (other_subtree, tree);
 634                                 expression->next = subtree;
 635                         } else if (comparison < 0) {
 636                                 expression->previous = subtree;
 637                                 expression->next = add_expression_to_tree (other_subtree, tree);
 638                         } else {
 639                                 g_assert_not_reached ();
 640                                 return NULL;
 641                         }
 642                         expression->tree_size = 1 + expression->previous->tree_size + expression->next->tree_size;
 643                         return expression;
 644                 }
 645         }
 646 }
 647
 648 #if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
 649 static char *mono_ssapre_expression_name = NULL;
 650 static gboolean
 651 check_ssapre_expression_name (MonoSsapreWorkArea *area, MonoSsapreExpressionDescription *expression_description) {
 652         if (area->expression_is_handled_father) {
 653                 return TRUE;
 654         }
 655         if (mono_ssapre_expression_name == NULL) {
 656                 mono_ssapre_expression_name = getenv ("MONO_SSAPRE_EXPRESSION_NAME");
 657         }
 658         if (mono_ssapre_expression_name != NULL) {
 659                 GString *expression_name = g_string_new_len ("", 256);
 660                 gboolean return_value;
 661                 snprint_expression_description (expression_name, expression_description);
 662                 if (strstr (expression_name->str, mono_ssapre_expression_name) != NULL) {
 663                         return_value = TRUE;
 664                 } else {
 665                         return_value = FALSE;
 666                 }
 667                 g_string_free (expression_name, TRUE);
 668                 return return_value;
 669         } else {
 670                 return TRUE;
 671         }
 672 }
 673 #endif
 674
 675 /*
 676  * Adds an expression to the worklist (putting the current occurrence as first
 677  * occurrence of this expression).
 678  */
 679 static void
 680 add_expression_to_worklist (MonoSsapreWorkArea *area) {
 681         MonoSsapreExpressionOccurrence *occurrence = area->current_occurrence;
 682         MonoSsapreExpression *expression = (MonoSsapreExpression*) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreExpression));
 683
 684         convert_ssa_variables_to_original_names (&(expression->description), &(occurrence->description), area->cfg);
 685
 686 #if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
 687         if (! check_ssapre_expression_name (area, &(expression->description))) return;
 688 #endif
 689
 690         expression->type = mono_type_from_stack_type (occurrence->occurrence);
 691         expression->occurrences = NULL;
 692         expression->last_occurrence = NULL;
 693         expression->next_in_queue = NULL;
 694         if (area->last_in_queue != NULL) {
 695                 area->last_in_queue->next_in_queue = expression;
 696         } else {
 697                 area->first_in_queue = expression;
 698         }
 699         area->last_in_queue = expression;
 700         MONO_SSAPRE_ADD_EXPRESSION_OCCURRANCE (expression, occurrence);
 701
 702         area->worklist = add_expression_to_tree (area->worklist, expression);
 703         area->worklist->father = NULL;
 704 }
 705
 706 /*
 707  * Adds the current expression occurrence to the worklist.
 708  * If its expression is not yet in the worklist, it is created.
 709  */
 710 static void
 711 add_occurrence_to_worklist (MonoSsapreWorkArea *area) {
 712         MonoSsapreExpressionDescription description;
 713         MonoSsapreExpression *current_expression;
 714         int comparison;
 715
 716         convert_ssa_variables_to_original_names (&description, &(area->current_occurrence->description), area->cfg);
 717         current_expression = area->worklist;
 718
 719         do {
 720                 if (current_expression != NULL) {
 721                         comparison = MONO_COMPARE_SSAPRE_EXPRESSION_DESCRIPTIONS (description, current_expression->description);
 722
 723                         if (comparison > 0) {
 724                                 current_expression = current_expression->next;
 725                         } else if (comparison < 0) {
 726                                 current_expression = current_expression->previous;
 727                         } else {
 728                                 MONO_SSAPRE_ADD_EXPRESSION_OCCURRANCE (current_expression, area->current_occurrence);
 729                         }
 730                 } else {
 731                         add_expression_to_worklist (area);
 732                         comparison = 0;
 733                 }
 734         } while (comparison != 0);
 735
 736         area->current_occurrence = (MonoSsapreExpressionOccurrence*) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreExpressionOccurrence));
 737 }
 738
 739 /*
 740  * Process a MonoInst, and of it is a valid expression add it to the worklist.
 741  */
 742 static void
 743 process_inst (MonoSsapreWorkArea *area, MonoInst* inst, MonoInst* previous_inst, MonoSsapreFatherExpression*** father_in_tree, MonoSsapreBBInfo *bb_info) {
 744         MonoSsapreFatherExpression** left_father_in_tree = NULL;
 745         MonoSsapreFatherExpression** right_father_in_tree = NULL;
 746
 747         if (mono_burg_arity [inst->opcode] > 0) {
 748                 process_inst (area, inst->inst_left, previous_inst, &left_father_in_tree, bb_info);
 749                 if (mono_burg_arity [inst->opcode] > 1) {
 750                         process_inst (area, inst->inst_right, previous_inst, &right_father_in_tree, bb_info);
 751                 }
 752         }
 753
 754         analyze_expression (inst, &(area->current_occurrence->description));
 755         if (area->current_occurrence->description.opcode != 0) {
 756                 if ((left_father_in_tree != NULL) || (right_father_in_tree != NULL)) {
 757                         MonoSsapreFatherExpression *current_inst_as_father = (MonoSsapreFatherExpression*) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreFatherExpression));
 758                         current_inst_as_father->father_occurrence = inst;
 759                         current_inst_as_father->grand_father = NULL;
 760                         *father_in_tree = &(current_inst_as_father->grand_father);
 761                         if (left_father_in_tree != NULL) {
 762                                 *left_father_in_tree = current_inst_as_father;
 763                         }
 764                         if (right_father_in_tree != NULL) {
 765                                 *right_father_in_tree = current_inst_as_father;
 766                         }
 767                         if (DUMP_SSAPRE) {
 768                                 printf ("Expression '");
 769                                 mono_print_tree (inst);
 770                                 printf ("' is a potential father ( ");
 771                                 if (left_father_in_tree != NULL) {
 772                                         printf ("LEFT ");
 773                                 }
 774                                 if (right_father_in_tree != NULL) {
 775                                         printf ("RIGHT ");
 776                                 }
 777                                 printf (")\n");
 778                         }
 779                 } else if ((area->current_occurrence->description.left_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY) &&
 780                                 (area->current_occurrence->description.right_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY)) {
 781                         area->current_occurrence->occurrence = inst;
 782                         area->current_occurrence->previous_tree = previous_inst;
 783                         area->current_occurrence->bb_info = bb_info;
 784                         area->current_occurrence->is_first_in_bb = FALSE;
 785                         area->current_occurrence->is_last_in_bb = FALSE;
 786
 787                         area->current_occurrence->father_in_tree = NULL;
 788                         *father_in_tree = &(area->current_occurrence->father_in_tree);
 789
 790                         add_occurrence_to_worklist (area);
 791                 } else {
 792                         *father_in_tree = NULL;
 793                 }
 794         } else {
 795                 *father_in_tree = NULL;
 796         }
 797 }
 798
 799 /*
 800  * Process a BB, and (recursively) all its children in the dominator tree.
 801  * The result is that all the expressions end up in the worklist, and the
 802  * auxiliary MonoSsapreBBInfo fields (dt_dfn, dt_descendants) are initialized
 803  * (with all the info that comes from the MonoBasicBlock).
 804  */
 805 static void
 806 process_bb (MonoSsapreWorkArea *area, MonoBasicBlock *bb, int *dt_dfn, int *upper_descendants, int current_depth) {
 807         MonoSsapreBBInfo *bb_info;
 808         int descendants;
 809         GSList *dominated_bb;
 810         MonoInst* current_inst;
 811         MonoInst* previous_inst;
 812         MonoSsapreFatherExpression** dummy_father_in_tree;
 813
 814         bb_info = &(area->bb_infos [*dt_dfn]);
 815         bb_info->dt_dfn = *dt_dfn;
 816         (*dt_dfn)++;
 817         bb_info->cfg_dfn = bb->dfn;
 818         area->bb_infos_in_cfg_dfn_order [bb->dfn] = bb_info;
 819         bb_info->in_count = bb->in_count;
 820         bb_info->out_count = bb->out_count;
 821         bb_info->dfrontier = bb->dfrontier;
 822         bb_info->bb = bb;
 823         bb_info->in_bb = (MonoSsapreBBInfo**) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreBBInfo*) * (bb->in_count));
 824         bb_info->out_bb = (MonoSsapreBBInfo**) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreBBInfo*) * (bb->out_count));
 825         bb_info->phi_arguments_classes = (int*) mono_mempool_alloc (area->mempool, sizeof (int) * (bb->in_count));
 826
 827         bb_info->phi_insertion_point = NULL;
 828
 829         previous_inst = NULL;
 830         MONO_BB_FOR_EACH_INS (bb, current_inst) {
 831                 /* Ugly hack to fix missing variable definitions */
 832                 /* (the SSA construction code should have done it already!) */
 833                 switch (current_inst->opcode) {
 834                 case CEE_STIND_REF:
 835                 case CEE_STIND_I:
 836                 case CEE_STIND_I4:
 837                 case CEE_STIND_I1:
 838                 case CEE_STIND_I2:
 839                 case CEE_STIND_I8:
 840                 case CEE_STIND_R4:
 841                 case CEE_STIND_R8:
 842                         if ((current_inst->inst_left->opcode == OP_LOCAL) || (current_inst->inst_left->opcode == OP_ARG)) {
 843                                 int variable_index = current_inst->inst_left->inst_c0;
 844
 845                                 if (MONO_VARINFO (area->cfg, variable_index)->def_bb == NULL) {
 846                                         if (area->cfg->verbose_level >= 4) {
 847                                                 printf ("SSAPRE WARNING: variable %d has no definition, fixing.\n", variable_index);
 848                                         }
 849                                         MONO_VARINFO (area->cfg, variable_index)->def_bb = bb_info->bb;
 850                                 }
 851                         }
 852                         break;
 853                 default:
 854                         break;
 855                 }
 856
 857                 if (is_phi_definition (current_inst)) {
 858                         bb_info->phi_insertion_point = current_inst;
 859                 }
 860
 861                 if (mono_burg_arity [current_inst->opcode] > 0) {
 862                         process_inst (area, current_inst->inst_left, previous_inst, &dummy_father_in_tree, bb_info);
 863                         if (mono_burg_arity [current_inst->opcode] > 1) {
 864                                 process_inst (area, current_inst->inst_right, previous_inst, &dummy_father_in_tree, bb_info);
 865                         }
 866                 }
 867
 868                 previous_inst = current_inst;
 869         }
 870
 871         if (current_depth > area->dt_depth) {
 872                 area->dt_depth = current_depth;
 873         }
 874         descendants = 0;
 875         for (dominated_bb = bb->dominated; dominated_bb != NULL; dominated_bb = dominated_bb->next) {
 876                 process_bb (area, (MonoBasicBlock*) (dominated_bb->data), dt_dfn, &descendants, current_depth + 1);
 877         }
 878         bb_info->dt_descendants = descendants;
 879         *upper_descendants += (descendants + 1);
 880 }
 881
 882 /*
 883  * Reset the MonoSsapreBBInfo fields that must be recomputed for each expression.
 884  */
 885 static void
 886 clean_bb_infos (MonoSsapreWorkArea *area) {
 887         int i;
 888         for (i = 0; i < area->num_bblocks; i++) {
 889                 MonoSsapreBBInfo *bb_info = &(area->bb_infos [i]);
 890                 bb_info->dt_covered_by_interesting_BBs = FALSE;
 891                 bb_info->has_phi = FALSE;
 892                 bb_info->phi_defines_a_real_occurrence = FALSE;
 893                 bb_info->phi_is_down_safe = FALSE;
 894                 bb_info->phi_can_be_available = FALSE;
 895                 bb_info->phi_is_later = FALSE;
 896                 bb_info->phi_redundancy_class = BOTTOM_REDUNDANCY_CLASS;
 897                 bb_info->phi_variable_index = BOTTOM_REDUNDANCY_CLASS;
 898                 bb_info->has_phi_argument = FALSE;
 899                 bb_info->phi_argument_has_real_use = FALSE;
 900                 bb_info->phi_argument_needs_insert = FALSE;
 901                 bb_info->phi_argument_has_been_processed = FALSE;
 902                 bb_info->phi_argument_class = BOTTOM_REDUNDANCY_CLASS;
 903                 bb_info->phi_argument_variable_index = BOTTOM_REDUNDANCY_CLASS;
 904                 bb_info->phi_argument_defined_by_real_occurrence = NULL;
 905                 bb_info->phi_argument_defined_by_phi = NULL;
 906                 bb_info->phi_argument_left_argument_version = BOTTOM_REDUNDANCY_CLASS;
 907                 bb_info->phi_argument_right_argument_version = BOTTOM_REDUNDANCY_CLASS;
 908                 bb_info->first_expression_in_bb = NULL;
 909                 bb_info->next_interesting_bb = NULL;
 910                 bb_info->next_in_renaming_stack = NULL;
 911                 bb_info->top_of_local_renaming_stack = NULL;
 912         }
 913 }
 914
 915 /*
 916  * Reset the MonoSsapreWorkArea fields that must be recomputed for each expression.
 917  */
 918 static void
 919 clean_area_infos (MonoSsapreWorkArea *area) {
 920         mono_bitset_clear_all (area->left_argument_bb_bitset);
 921         mono_bitset_clear_all (area->right_argument_bb_bitset);
 922         area->num_vars = area->cfg->num_varinfo;
 923         area->top_of_renaming_stack = NULL;
 924         area->bb_on_top_of_renaming_stack = NULL;
 925         area->first_interesting_bb = NULL;
 926         area->saved_occurrences = 0;
 927         area->reloaded_occurrences = 0;
 928         area->inserted_occurrences = 0;
 929         area->unaltered_occurrences = 0;
 930         area->added_phis = 0;
 931         clean_bb_infos (area);
 932 }
 933
 934 /*
 935  * Utility function to combine the dominance frontiers of a set of BBs.
 936  */
 937 static void
 938 compute_combined_dfrontier (MonoSsapreWorkArea *area, MonoBitSet* result, MonoBitSet *bblocks)
 939 {
 940         int i;
 941         mono_bitset_clear_all (result);
 942         mono_bitset_foreach_bit (bblocks, i, area->num_bblocks) {
 943                 mono_bitset_union (result, area->bb_infos_in_cfg_dfn_order [i]->dfrontier);
 944         }
 945 }
 946
 947 /*
 948  * Utility function to compute the combined dominance frontier of a set of BBs.
 949  */
 950 static void
 951 compute_combined_iterated_dfrontier (MonoSsapreWorkArea *area, MonoBitSet *result, MonoBitSet *bblocks, MonoBitSet *buffer)
 952 {
 953         gboolean change = TRUE;
 954
 955         compute_combined_dfrontier (area, result, bblocks);
 956         do {
 957                 change = FALSE;
 958                 compute_combined_dfrontier (area, buffer, result);
 959                 mono_bitset_union (buffer, result);
 960
 961                 if (!mono_bitset_equal (buffer, result)) {
 962                         mono_bitset_copyto (buffer, result);
 963                         change = TRUE;
 964                 }
 965         } while (change);
 966 }
 967
 968 /*
 969  * See paper, section 5.1, definition of "Dominate"
 970  */
 971 static gboolean
 972 dominates (MonoSsapreBBInfo *dominator, MonoSsapreBBInfo *dominated) {
 973         if ((dominator->dt_dfn <= dominated->dt_dfn) && (dominated->dt_dfn <= (dominator->dt_dfn + dominator->dt_descendants))) {
 974                 return TRUE;
 975         } else {
 976                 return FALSE;
 977         }
 978 }
 979
 980 /*
 981  * See paper, figure 18, function Set_var_phis
 982  */
 983 static void process_phi_variable_in_phi_insertion (MonoSsapreWorkArea *area, gssize variable, MonoBitSet *phi_bbs) {
 984         int* phi_definition = get_phi_definition (area->cfg, variable);
 985
 986         if (phi_definition != NULL) {
 987                 int definition_bb = MONO_VARINFO (area->cfg, variable)->def_bb->dfn;
 988                 if (! mono_bitset_test (phi_bbs, definition_bb)) {
 989                         int i;
 990                         mono_bitset_set (phi_bbs, definition_bb);
 991                         for (i = 0; i < *phi_definition; i++) {
 992                                 process_phi_variable_in_phi_insertion (area, phi_definition [i+1], phi_bbs);
 993                         }
 994                 }
 995         }
 996 }
 997
 998 /*
 999  * See paper, figure 18, function phi_insertion
1000  */
1001 static void
1002 phi_insertion (MonoSsapreWorkArea *area, MonoSsapreExpression *expression) {
1003         MonoSsapreExpressionOccurrence *current_expression = NULL;
1004         MonoSsapreExpressionOccurrence *previous_expression = NULL;
1005         MonoSsapreBBInfo *current_bb = NULL;
1006         MonoSsapreBBInfo *previous_interesting_bb = NULL;
1007         int i, j, current_bb_dt_dfn;
1008         int top;
1009         MonoSsapreBBInfo **stack;
1010         gboolean *interesting_stack;
1011
1012         mono_bitset_clear_all (area->expression_occurrences_buffer);
1013         for (current_expression = expression->occurrences; current_expression != NULL; current_expression = current_expression->next) {
1014                 mono_bitset_set (area->expression_occurrences_buffer, current_expression->bb_info->cfg_dfn);
1015                 if (current_expression->description.left_argument.type == MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE) {
1016                         process_phi_variable_in_phi_insertion (area, current_expression->description.left_argument.argument.ssa_variable, area->left_argument_bb_bitset);
1017                 }
1018                 if (current_expression->description.right_argument.type == MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE) {
1019                         process_phi_variable_in_phi_insertion (area, current_expression->description.right_argument.argument.ssa_variable, area->right_argument_bb_bitset);
1020                 }
1021
1022                 if (previous_expression != NULL) {
1023                         if (previous_expression->bb_info != current_expression->bb_info) {
1024                                 previous_expression->is_last_in_bb = TRUE;
1025                                 current_expression->is_first_in_bb = TRUE;
1026                                 current_expression->bb_info->first_expression_in_bb = current_expression;
1027                         }
1028                 } else {
1029                         current_expression->is_first_in_bb = TRUE;
1030                         current_expression->bb_info->first_expression_in_bb = current_expression;
1031                 }
1032
1033                 previous_expression = current_expression;
1034         }
1035         previous_expression->is_last_in_bb = TRUE;
1036
1037         compute_combined_iterated_dfrontier (area, area->iterated_dfrontier_buffer, area->expression_occurrences_buffer, area->bb_iteration_buffer);
1038
1039         mono_bitset_union (area->iterated_dfrontier_buffer, area->left_argument_bb_bitset);
1040         mono_bitset_union (area->iterated_dfrontier_buffer, area->right_argument_bb_bitset);
1041
1042         mono_bitset_foreach_bit (area->iterated_dfrontier_buffer, i, area->num_bblocks) {
1043                 area->bb_infos_in_cfg_dfn_order [i]->has_phi = TRUE;
1044                 area->bb_infos_in_cfg_dfn_order [i]->phi_can_be_available = TRUE;
1045                 for (j = 0; j < area->bb_infos_in_cfg_dfn_order [i]->in_count; j++) {
1046                         area->bb_infos_in_cfg_dfn_order [i]->in_bb [j]->has_phi_argument = TRUE;
1047                 }
1048         }
1049
1050         top = -1;
1051         stack = (MonoSsapreBBInfo **) alloca (sizeof (MonoSsapreBBInfo *) * (area->dt_depth));
1052         interesting_stack = (gboolean *) alloca (sizeof (gboolean) * (area->dt_depth));
1053
1054         /* Setup the list of interesting BBs, and their "DT coverage" */
1055         for (current_bb = area->bb_infos, current_bb_dt_dfn = 0; current_bb_dt_dfn < area->num_bblocks; current_bb++, current_bb_dt_dfn++) {
1056                 gboolean current_bb_is_interesting;
1057
1058                 if ((current_bb->first_expression_in_bb != NULL) || (current_bb->has_phi) || (current_bb->has_phi_argument)) {
1059                         current_bb_is_interesting = TRUE;
1060
1061                         if (previous_interesting_bb != NULL) {
1062                                 previous_interesting_bb->next_interesting_bb = current_bb;
1063                         } else {
1064                                 area->first_interesting_bb = current_bb;
1065                         }
1066                         previous_interesting_bb = current_bb;
1067                 } else {
1068                         current_bb_is_interesting = FALSE;
1069                 }
1070
1071                 if (top >= 0) {
1072                         while ((top >= 0) && (! dominates (stack [top], current_bb))) {
1073                                 gboolean top_covers_his_idominator = ((interesting_stack [top]) || (stack [top]->dt_covered_by_interesting_BBs));
1074
1075                                 if ((top > 0) && (! top_covers_his_idominator)) {
1076                                         stack [top - 1]->dt_covered_by_interesting_BBs = FALSE;
1077                                 }
1078
1079                                 top--;
1080                         }
1081                 } else {
1082                         top = -1;
1083                 }
1084
1085                 top++;
1086
1087                 interesting_stack [top] = current_bb_is_interesting;
1088                 stack [top] = current_bb;
1089                 if (stack [top]->dt_descendants == 0) {
1090                         stack [top]->dt_covered_by_interesting_BBs = FALSE;
1091                 } else {
1092                         stack [top]->dt_covered_by_interesting_BBs = TRUE;
1093                 }
1094         }
1095         while (top > 0) {
1096                 gboolean top_covers_his_idominator = ((interesting_stack [top]) || (stack [top]->dt_covered_by_interesting_BBs));
1097
1098                 if (! top_covers_his_idominator) {
1099                         stack [top - 1]->dt_covered_by_interesting_BBs = FALSE;
1100                 }
1101
1102                 top--;
1103         }
1104 }
1105
1106 /*
1107  * Macro that pushes a real occurrence on the stack
1108  */
1109 #define PUSH_REAL_OCCURRENCE(o) do{\
1110                         if (area->bb_on_top_of_renaming_stack != (o)->bb_info) { \
1111                                 (o)->bb_info->next_in_renaming_stack = area->bb_on_top_of_renaming_stack; \
1112                                 area->bb_on_top_of_renaming_stack =(o)->bb_info; \
1113                                 (o)->next_in_renaming_stack = NULL; \
1114                         } else { \
1115                                 (o)->next_in_renaming_stack = area->top_of_renaming_stack; \
1116                         } \
1117                         (o)->bb_info->top_of_local_renaming_stack = (o); \
1118                         area->top_of_renaming_stack = (o); \
1119                         area->bb_on_top_of_renaming_stack->phi_argument_has_real_use = FALSE; \
1120                 } while(0)
1121
1122 /*
1123  * Macro that pushes a PHI occurrence on the stack
1124  */
1125 #define PUSH_PHI_OCCURRENCE(b) do{\
1126                         if (area->bb_on_top_of_renaming_stack != (b)) { \
1127                                 (b)->next_in_renaming_stack = area->bb_on_top_of_renaming_stack; \
1128                                 area->bb_on_top_of_renaming_stack = (b); \
1129                         } \
1130                         (b)->top_of_local_renaming_stack = NULL; \
1131                         area->top_of_renaming_stack = NULL; \
1132                         area->bb_on_top_of_renaming_stack->phi_argument_has_real_use = FALSE; \
1133                 } while(0)
1134
1135 /*
1136  * See paper, section 5.4.
1137  * The two passes are coded sequentially (no separate "rename1" and "rename2" functions).
1138  */
1139 static void
1140 renaming_pass (MonoSsapreWorkArea *area) {
1141         MonoSsapreBBInfo *current_bb = NULL;
1142         MonoSsapreBBInfo *previous_bb = NULL;
1143         MonoSsapreExpressionOccurrence *current_expression = NULL;
1144         gssize current_class = 0;
1145
1146         /* This loop is "rename1" */
1147         for (current_bb = area->first_interesting_bb, previous_bb = NULL; current_bb != NULL; previous_bb = current_bb, current_bb = current_bb->next_interesting_bb) {
1148                 if (previous_bb != NULL) {
1149                         if (! dominates (previous_bb, current_bb)) {
1150                                 /* This means we are backtracking in the dominator tree */
1151                                 MonoSsapreBBInfo *first_interesting_dominator = current_bb->idominator;
1152                                 while ((first_interesting_dominator->next_interesting_bb == NULL) && (first_interesting_dominator->idominator != NULL)) {
1153                                         first_interesting_dominator = first_interesting_dominator->idominator;
1154                                 }
1155                                 current_bb->phi_argument_has_real_use = first_interesting_dominator->phi_argument_has_real_use;
1156
1157                                 if ((area->bb_on_top_of_renaming_stack != NULL) && (area->top_of_renaming_stack == NULL) && (previous_bb->phi_argument_has_real_use == FALSE)) {
1158                                         if (TRACE_SSAPRE) {
1159                                                 printf ("Clearing down safe in PHI %d because of backtracking (current block is [bb %d [ID %d]], previous block is [bb %d [ID %d]])\n",
1160                                                                 area->bb_on_top_of_renaming_stack->phi_redundancy_class, current_bb->cfg_dfn, current_bb->bb->block_num, previous_bb->cfg_dfn, previous_bb->bb->block_num);
1161                                         }
1162                                         area->bb_on_top_of_renaming_stack->phi_is_down_safe = FALSE;
1163                                 }
1164                                 while ((area->bb_on_top_of_renaming_stack != NULL) && ! dominates (area->bb_on_top_of_renaming_stack, current_bb)) {
1165                                         MonoSsapreBBInfo *top_bb = area->bb_on_top_of_renaming_stack;
1166                                         if (top_bb->next_in_renaming_stack != NULL) {
1167                                                 area->top_of_renaming_stack = top_bb->next_in_renaming_stack->top_of_local_renaming_stack;
1168                                         } else {
1169                                                 area->top_of_renaming_stack = NULL;
1170                                         }
1171                                         area->bb_on_top_of_renaming_stack = top_bb->next_in_renaming_stack;
1172                                 }
1173                                 if (DUMP_SSAPRE) {
1174                                         printf ("Backtracked, getting real use flag from bb %d [ID %d], current top of the stack is class ",
1175                                                         first_interesting_dominator->cfg_dfn, first_interesting_dominator->bb->block_num);
1176                                         if (area->top_of_renaming_stack != NULL) {
1177                                                 printf ("%d\n", area->top_of_renaming_stack->redundancy_class);
1178                                         } else if (area->bb_on_top_of_renaming_stack != NULL) {
1179                                                 printf ("%d\n", area->bb_on_top_of_renaming_stack->phi_redundancy_class);
1180                                         } else {
1181                                                 printf ("BOTTOM\n");
1182                                         }
1183                                 }
1184                         } else {
1185                                 /* With no backtracking we just propagate the flag */
1186                                 current_bb->phi_argument_has_real_use = previous_bb->phi_argument_has_real_use;
1187                         }
1188                 } else {
1189                         /* Start condition */
1190                         current_bb->phi_argument_has_real_use = FALSE;
1191                 }
1192                 if (DUMP_SSAPRE) {
1193                         printf ("Real use flag is %s at the beginning of block [bb %d [ID %d]]\n",
1194                                         GBOOLEAN_TO_STRING (current_bb->phi_argument_has_real_use), current_bb->cfg_dfn, current_bb->bb->block_num);
1195                 }
1196
1197                 if (current_bb->has_phi) {
1198                         if (current_bb->dt_covered_by_interesting_BBs) {
1199                                 current_bb->phi_is_down_safe = TRUE;
1200                         } else {
1201                                 current_bb->phi_is_down_safe = FALSE;
1202                         }
1203                         current_bb->phi_redundancy_class = current_class;
1204                         current_class++;
1205                         PUSH_PHI_OCCURRENCE (current_bb);
1206                         if (TRACE_SSAPRE) {
1207                                 printf ("Assigning class %d to PHI in bb %d [ID %d]\n",
1208                                                 current_bb->phi_redundancy_class, current_bb->cfg_dfn, current_bb->bb->block_num);
1209                         }
1210                 }
1211
1212                 for (current_expression = current_bb->first_expression_in_bb; (current_expression != NULL) && (current_expression->bb_info == current_bb); current_expression = current_expression->next) {
1213                         if (area->top_of_renaming_stack != NULL) {
1214                                 MonoSsapreExpressionOccurrence *top = area->top_of_renaming_stack;
1215
1216                                 if (((current_expression->description.left_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE) ||
1217                                                 (current_expression->description.left_argument.argument.ssa_variable == top->description.left_argument.argument.ssa_variable)) &&
1218                                                 ((current_expression->description.right_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE) ||
1219                                                 (current_expression->description.right_argument.argument.ssa_variable == top->description.right_argument.argument.ssa_variable))) {
1220                                         current_expression->redundancy_class = top->redundancy_class;
1221                                         current_expression->defined_by_real_occurrence = top;
1222                                         if (DUMP_SSAPRE) {
1223                                                 printf ("Using class %d for occurrence '", current_expression->redundancy_class);
1224                                                 print_expression_description (&(current_expression->description));
1225                                                 printf ("' in bb %d [ID %d]\n", current_bb->cfg_dfn, current_bb->bb->block_num);
1226                                         }
1227                                 } else {
1228                                         current_expression->redundancy_class = current_class;
1229                                         current_class++;
1230                                         current_expression->defined_by_real_occurrence = NULL;
1231                                         PUSH_REAL_OCCURRENCE (current_expression);
1232                                         if (TRACE_SSAPRE) {
1233                                                 printf ("Assigning class %d to occurrence '", current_expression->redundancy_class);
1234                                                 print_expression_description (&(current_expression->description));
1235                                                 printf ("' in bb %d [ID %d]\n", current_bb->cfg_dfn, current_bb->bb->block_num);
1236                                         }
1237                                 }
1238                                 current_expression->defined_by_phi = NULL;
1239                         } else if (area->bb_on_top_of_renaming_stack != NULL) {
1240                                 MonoSsapreBBInfo *phi_bb = area->bb_on_top_of_renaming_stack;
1241                                 gssize left_argument_version = ((current_expression->description.left_argument.type == MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE)?
1242                                                 (current_expression->description.left_argument.argument.ssa_variable):BOTTOM_REDUNDANCY_CLASS);
1243                                 gssize right_argument_version = ((current_expression->description.right_argument.type == MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE)?
1244                                                 (current_expression->description.right_argument.argument.ssa_variable):BOTTOM_REDUNDANCY_CLASS);
1245
1246                                 /* See remark in section 5.4 about the dominance relation between PHI */
1247                                 /* occurrences and phi definitions */
1248                                 MonoSsapreBBInfo *left_argument_definition_bb = ((left_argument_version != BOTTOM_REDUNDANCY_CLASS)?
1249                                                 (get_bb_info_of_definition (area, left_argument_version)):NULL);
1250                                 MonoSsapreBBInfo *right_argument_definition_bb = ((right_argument_version != BOTTOM_REDUNDANCY_CLASS)?
1251                                                 (get_bb_info_of_definition (area, right_argument_version)):NULL);
1252
1253                                 gboolean left_same_class_condition = ((left_argument_definition_bb == NULL) || ((left_argument_definition_bb != phi_bb) ? dominates (left_argument_definition_bb, phi_bb) :
1254                                                 (IS_PHI_DEFINITION (left_argument_version) ? TRUE : FALSE)));
1255                                 gboolean right_same_class_condition = ((right_argument_definition_bb == NULL) || ((right_argument_definition_bb != phi_bb) ? dominates (right_argument_definition_bb, phi_bb) :
1256                                                 (IS_PHI_DEFINITION (right_argument_version) ? TRUE : FALSE)));
1257
1258                                 if (left_same_class_condition && right_same_class_condition) {
1259                                         int phi_argument;
1260
1261                                         phi_bb->phi_defines_a_real_occurrence = TRUE;
1262                                         current_bb->phi_argument_has_real_use = TRUE;
1263                                         current_expression->redundancy_class = phi_bb->phi_redundancy_class;
1264                                         current_expression->defined_by_phi = phi_bb;
1265
1266                                         /* If this PHI was not "covered", it is not down safe. */
1267                                         /* However, if the real occurrence is in the same BB, it */
1268                                         /* actually is down safe */
1269                                         if (phi_bb == current_bb) {
1270                                                 if (DUMP_SSAPRE) {
1271                                                         printf ("PHI in bb %d [ID %d] defined occurrence %d in the same BB, so it is down safe\n", phi_bb->cfg_dfn, phi_bb->bb->block_num, current_expression->redundancy_class);
1272                                                 }
1273                                                 phi_bb->phi_is_down_safe = TRUE;
1274                                         }
1275
1276                                         /*
1277                                          * Major difference from the paper here...
1278                                          * Instead of maintaining "set_for_rename2" (see figure 20), we just
1279                                          * compute "phi_argument_left_argument_version" (and right) here, and
1280                                          * use that in rename2, saving us the hassle of maintaining a set
1281                                          * data structure (and the related allocations).
1282                                          */
1283                                         for (phi_argument = 0; phi_argument < phi_bb->in_count; phi_argument++) {
1284                                                 MonoSsapreBBInfo *previous_bb = phi_bb->in_bb [phi_argument];
1285                                                 if (left_argument_version != BOTTOM_REDUNDANCY_CLASS) {
1286                                                         previous_bb->phi_argument_left_argument_version = get_variable_version_at_predecessor_bb (area,
1287                                                                         left_argument_version, phi_bb, phi_argument);
1288                                                 }
1289                                                 if (right_argument_version != BOTTOM_REDUNDANCY_CLASS) {
1290                                                         previous_bb->phi_argument_right_argument_version = get_variable_version_at_predecessor_bb (area,
1291                                                                         right_argument_version, phi_bb, phi_argument);
1292                                                 }
1293                                         }
1294                                         if (DUMP_SSAPRE) {
1295                                                 printf ("Using class %d for occurrence '", current_expression->redundancy_class);
1296                                                 print_expression_description (&(current_expression->description));
1297                                                 printf ("' in bb %d [ID %d] (Real use flag is now TRUE)\n", current_bb->cfg_dfn, current_bb->bb->block_num);
1298                                         }
1299                                 } else {
1300                                         current_expression->redundancy_class = current_class;
1301                                         current_class++;
1302                                         current_expression->defined_by_phi = NULL;
1303                                         PUSH_REAL_OCCURRENCE (current_expression);
1304                                         phi_bb->phi_is_down_safe = FALSE;
1305                                         if (TRACE_SSAPRE) {
1306                                                 printf ("Assigning class %d to occurrence '", current_expression->redundancy_class);
1307                                                 print_expression_description (&(current_expression->description));
1308                                                 printf ("' in bb %d [ID %d]\n", current_bb->cfg_dfn, current_bb->bb->block_num);
1309                                                 printf ("Clearing down safe in PHI %d because of real occurrence %d\n",
1310                                                                 phi_bb->phi_redundancy_class, current_expression->redundancy_class);
1311                                         }
1312                                 }
1313                                 current_expression->defined_by_real_occurrence = NULL;
1314                         } else {
1315                                 current_expression->redundancy_class = current_class;
1316                                 current_class++;
1317                                 current_expression->defined_by_real_occurrence = NULL;
1318                                 current_expression->defined_by_phi = NULL;
1319                                 PUSH_REAL_OCCURRENCE (current_expression);
1320                                 if (TRACE_SSAPRE) {
1321                                         printf ("Assigning class %d to occurrence '", current_expression->redundancy_class);
1322                                         print_expression_description (&(current_expression->description));
1323                                         printf ("' in bb %d [ID %d]\n", current_bb->cfg_dfn, current_bb->bb->block_num);
1324                                 }
1325                         }
1326                 }
1327
1328                 if (current_bb->has_phi_argument) {
1329                         if (area->top_of_renaming_stack != NULL) {
1330                                 current_bb->phi_argument_defined_by_real_occurrence = area->top_of_renaming_stack;
1331                                 current_bb->phi_argument_class = area->top_of_renaming_stack->redundancy_class;
1332                         } else if (area->bb_on_top_of_renaming_stack != NULL) {
1333                                 current_bb->phi_argument_defined_by_phi = area->bb_on_top_of_renaming_stack;
1334                                 current_bb->phi_argument_class = area->bb_on_top_of_renaming_stack->phi_redundancy_class;
1335                         } else {
1336                                 current_bb->phi_argument_class = BOTTOM_REDUNDANCY_CLASS;
1337                         }
1338                         if ((DUMP_SSAPRE) && (current_bb->phi_argument_class != BOTTOM_REDUNDANCY_CLASS)) {
1339                                 printf ("Temporarily using class %d for PHI argument in bb %d [ID %d]\n",
1340                                                 current_bb->phi_argument_class, current_bb->cfg_dfn, current_bb->bb->block_num);
1341                         }
1342                 }
1343         }
1344         if ((area->bb_on_top_of_renaming_stack != NULL) && (area->top_of_renaming_stack == NULL) && (previous_bb->phi_argument_has_real_use == FALSE)) {
1345                 if (TRACE_SSAPRE) {
1346                         printf ("Clearing down safe in PHI %d because of backtracking (previous block is [bb %d [ID %d]])\n",
1347                                         area->bb_on_top_of_renaming_stack->phi_redundancy_class, previous_bb->cfg_dfn, previous_bb->bb->block_num);
1348                 }
1349                 area->bb_on_top_of_renaming_stack->phi_is_down_safe = FALSE;
1350         }
1351         area->number_of_classes = current_class;
1352
1353         /* This loop is "rename2" */
1354         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1355                 if (current_bb->has_phi_argument) {
1356                         if ((current_bb->phi_argument_left_argument_version != BOTTOM_REDUNDANCY_CLASS) || (current_bb->phi_argument_right_argument_version != BOTTOM_REDUNDANCY_CLASS)) {
1357                                 if (current_bb->phi_argument_defined_by_real_occurrence != NULL) {
1358                                         if (((current_bb->phi_argument_left_argument_version != BOTTOM_REDUNDANCY_CLASS) &&
1359                                                         (current_bb->phi_argument_left_argument_version != current_bb->phi_argument_defined_by_real_occurrence->description.left_argument.argument.ssa_variable)) ||
1360                                                         ((current_bb->phi_argument_right_argument_version != BOTTOM_REDUNDANCY_CLASS) &&
1361                                                         (current_bb->phi_argument_right_argument_version != current_bb->phi_argument_defined_by_real_occurrence->description.right_argument.argument.ssa_variable))) {
1362                                                 current_bb->phi_argument_class = BOTTOM_REDUNDANCY_CLASS;
1363                                         }
1364                                 } else if (current_bb->phi_argument_defined_by_phi != NULL) {
1365                                         MonoSsapreBBInfo *phi_bb = current_bb->phi_argument_defined_by_phi;
1366                                         MonoSsapreBBInfo *left_argument_definition_bb = (current_bb->phi_argument_left_argument_version != BOTTOM_REDUNDANCY_CLASS) ?
1367                                                         get_bb_info_of_definition (area, current_bb->phi_argument_left_argument_version) : NULL;
1368                                         MonoSsapreBBInfo *right_argument_definition_bb = (current_bb->phi_argument_right_argument_version != BOTTOM_REDUNDANCY_CLASS) ?
1369                                                         get_bb_info_of_definition (area, current_bb->phi_argument_right_argument_version) : NULL;
1370                                         /* See remark in section 5.4 about the dominance relation between PHI */
1371                                         /* occurrences and phi definitions */
1372                                         gboolean left_bottom_condition = ((left_argument_definition_bb != NULL) && ! ((left_argument_definition_bb != phi_bb) ? dominates (left_argument_definition_bb, phi_bb) :
1373                                                         (IS_PHI_DEFINITION (current_bb->phi_argument_left_argument_version) ? TRUE : FALSE)));
1374                                         gboolean right_bottom_condition = ((right_argument_definition_bb != NULL) && ! ((right_argument_definition_bb != phi_bb) ? dominates (right_argument_definition_bb, phi_bb) :
1375                                                         (IS_PHI_DEFINITION (current_bb->phi_argument_right_argument_version) ? TRUE : FALSE)));
1376
1377                                         if (left_bottom_condition || right_bottom_condition) {
1378                                                 current_bb->phi_argument_class = BOTTOM_REDUNDANCY_CLASS;
1379                                         }
1380                                 } else {
1381                                         current_bb->phi_argument_class = BOTTOM_REDUNDANCY_CLASS;
1382                                 }
1383                         } else {
1384                                 current_bb->phi_argument_class = BOTTOM_REDUNDANCY_CLASS;
1385                         }
1386
1387                         if (current_bb->phi_argument_class == BOTTOM_REDUNDANCY_CLASS) {
1388                                 if ((current_bb->phi_argument_defined_by_phi != NULL) && (! current_bb->phi_argument_has_real_use)) {
1389                                         if (TRACE_SSAPRE) {
1390                                                 printf ("Clearing down safe in PHI %d because PHI argument in block [bb %d [ID %d]] is BOTTOM\n",
1391                                                                 current_bb->phi_argument_defined_by_phi->phi_redundancy_class, current_bb->cfg_dfn, current_bb->bb->block_num);
1392                                         }
1393                                         current_bb->phi_argument_defined_by_phi->phi_is_down_safe = FALSE;
1394                                 }
1395                                 current_bb->phi_argument_has_real_use = FALSE;
1396
1397                                 if (DUMP_SSAPRE) {
1398                                         printf ("Cleared real use flag in block [bb %d [ID %d]] because phi argument class is now BOTTOM\n",
1399                                                         current_bb->cfg_dfn, current_bb->bb->block_num);
1400                                 }
1401                         }
1402                 }
1403         }
1404
1405         /* Final quick pass to copy the result of "rename2" into PHI nodes */
1406         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1407                 if (current_bb->has_phi) {
1408                         int i;
1409                         for (i = 0; i < current_bb->in_count; i++) {
1410                                 current_bb->phi_arguments_classes [i] = current_bb->in_bb [i]->phi_argument_class;
1411                         }
1412                 }
1413         }
1414 }
1415
1416 #undef PUSH_REAL_OCCURRENCE
1417 #undef PUSH_PHI_OCCURRENCE
1418
1419 /*
1420  * See paper, figure 8
1421  */
1422 static void
1423 reset_down_safe (MonoSsapreBBInfo *phi_argument) {
1424         if ((phi_argument->phi_argument_class != BOTTOM_REDUNDANCY_CLASS) && (! phi_argument->phi_argument_has_real_use) && (phi_argument->phi_argument_defined_by_phi != NULL) && (phi_argument->phi_argument_defined_by_phi->phi_is_down_safe)) {
1425                 int i;
1426                 MonoSsapreBBInfo *phi = phi_argument->phi_argument_defined_by_phi;
1427                 phi->phi_is_down_safe = FALSE;
1428                 for (i = 0; i < phi->in_count; i++) {
1429                         reset_down_safe (phi->in_bb [i]);
1430                 }
1431         }
1432 }
1433
1434 /*
1435  * See paper, figure 8
1436  */
1437 static void
1438 down_safety (MonoSsapreWorkArea *area) {
1439         MonoSsapreBBInfo *current_bb = NULL;
1440
1441         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1442                 if (current_bb->has_phi) {
1443                         if (! current_bb->phi_is_down_safe) {
1444                                 int i;
1445                                 for (i = 0; i < current_bb->in_count; i++) {
1446                                         reset_down_safe (current_bb->in_bb [i]);
1447                                 }
1448                         }
1449                 }
1450         }
1451 }
1452
1453 /*
1454  * See paper, figure 10
1455  */
1456 static void
1457 reset_can_be_available (MonoSsapreWorkArea *area, MonoSsapreBBInfo *phi) {
1458         MonoSsapreBBInfo *current_bb = NULL;
1459
1460         if (DUMP_SSAPRE) {
1461                 printf ("Resetting availability for PHI %d in block [bb %d [ID %d]]\n",
1462                                 phi->phi_redundancy_class, phi->cfg_dfn, phi->bb->block_num);
1463         }
1464
1465         phi->phi_can_be_available = FALSE;
1466         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1467                 if (current_bb->has_phi) {
1468                         gboolean phi_is_interesting = FALSE;
1469                         int i;
1470
1471                         for (i = 0; i < current_bb->in_count; i++) {
1472                                 MonoSsapreBBInfo *phi_argument = current_bb->in_bb [i];
1473                                 if ((phi_argument->phi_argument_class == current_bb->phi_redundancy_class) && (! phi_argument->phi_argument_has_real_use)) {
1474                                         phi_is_interesting = TRUE;
1475                                         break;
1476                                 }
1477                         }
1478
1479                         if (phi_is_interesting && (! current_bb->phi_is_down_safe) && (current_bb->phi_can_be_available)) {
1480                                 reset_can_be_available (area, current_bb);
1481                         }
1482                 }
1483         }
1484 }
1485
1486 /*
1487  * See paper, figure 10
1488  */
1489 static void
1490 compute_can_be_available (MonoSsapreWorkArea *area) {
1491         MonoSsapreBBInfo *current_bb = NULL;
1492
1493         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1494                 if (current_bb->has_phi) {
1495                         if ((! current_bb->phi_is_down_safe) && (current_bb->phi_can_be_available)) {
1496                                 gboolean phi_is_interesting = FALSE;
1497                                 int i;
1498
1499                                 for (i = 0; i < current_bb->in_count; i++) {
1500                                         if (current_bb->phi_arguments_classes [i] == BOTTOM_REDUNDANCY_CLASS) {
1501                                                 phi_is_interesting = TRUE;
1502                                                 break;
1503                                         }
1504                                 }
1505
1506                                 if (phi_is_interesting) {
1507                                         if (DUMP_SSAPRE) {
1508                                                 printf ("Availability computation working on PHI %d in block [bb %d [ID %d]]\n",
1509                                                                 current_bb->phi_redundancy_class, current_bb->cfg_dfn, current_bb->bb->block_num);
1510                                         }
1511                                         reset_can_be_available (area, current_bb);
1512                                 }
1513                         }
1514                 }
1515         }
1516 }
1517
1518 /*
1519  * See paper, figure 10
1520  */
1521 static void
1522 reset_later (MonoSsapreWorkArea *area, MonoSsapreBBInfo *phi) {
1523         MonoSsapreBBInfo *current_bb = NULL;
1524
1525         if (phi->phi_is_later) {
1526                 phi->phi_is_later = FALSE;
1527                 for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1528                         if (current_bb->has_phi) {
1529                                 gboolean phi_is_interesting = FALSE;
1530                                 int i;
1531
1532                                 for (i = 0; i < current_bb->in_count; i++) {
1533                                         MonoSsapreBBInfo *phi_argument = current_bb->in_bb [i];
1534                                         if (phi_argument->phi_argument_class == current_bb->phi_redundancy_class) {
1535                                                 phi_is_interesting = TRUE;
1536                                                 break;
1537                                         }
1538                                 }
1539
1540                                 if (phi_is_interesting) {
1541                                         reset_later (area, current_bb);
1542                                 }
1543                         }
1544                 }
1545         }
1546 }
1547
1548 /*
1549  * See paper, figure 10
1550  */
1551 static void
1552 compute_later (MonoSsapreWorkArea *area) {
1553         MonoSsapreBBInfo *current_bb = NULL;
1554
1555         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1556                 if (current_bb->has_phi) {
1557                         current_bb->phi_is_later = current_bb->phi_can_be_available;
1558                 }
1559         }
1560         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1561                 if (current_bb->has_phi) {
1562                         if (current_bb->phi_is_later) {
1563                                 gboolean phi_is_interesting = FALSE;
1564                                 int i;
1565
1566                                 for (i = 0; i < current_bb->in_count; i++) {
1567                                         MonoSsapreBBInfo *phi_argument = current_bb->in_bb [i];
1568                                         if ((phi_argument->phi_argument_class != BOTTOM_REDUNDANCY_CLASS) && (phi_argument->phi_argument_has_real_use)) {
1569                                                 phi_is_interesting = TRUE;
1570                                                 break;
1571                                         }
1572                                 }
1573
1574                                 if (phi_is_interesting) {
1575                                         reset_later (area, current_bb);
1576                                 }
1577                         }
1578                 }
1579         }
1580 }
1581
1582 /*
1583  * See paper, figure 12, function Finalize_1
1584  */
1585 static void finalize_availability_and_reload (MonoSsapreWorkArea *area, MonoSsapreAvailabilityTableElement *availability_table) {
1586         MonoSsapreBBInfo *current_bb = NULL;
1587         MonoSsapreExpressionOccurrence *current_expression = NULL;
1588
1589         area->occurrences_scheduled_for_reloading = 0;
1590         area->arguments_scheduled_for_insertion = 0;
1591         area->dominating_arguments_scheduled_for_insertion = 0;
1592
1593         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1594                 if (current_bb->has_phi) {
1595                         if (current_bb->phi_can_be_available && ! current_bb->phi_is_later) {
1596                                 availability_table [current_bb->phi_redundancy_class].class_defined_by_phi = current_bb;
1597                         }
1598                 }
1599
1600                 for (current_expression = current_bb->first_expression_in_bb; (current_expression != NULL) && (current_expression->bb_info == current_bb); current_expression = current_expression->next) {
1601                         MonoSsapreBBInfo *defining_bb = availability_table [current_expression->redundancy_class].class_defined_by_phi;
1602                         if (defining_bb == NULL && availability_table [current_expression->redundancy_class].class_defined_by_real_occurrence != NULL) {
1603                                 defining_bb = availability_table [current_expression->redundancy_class].class_defined_by_real_occurrence->bb_info;
1604                         }
1605                         if (defining_bb != NULL) {
1606                                 if (! dominates (defining_bb, current_bb)) {
1607                                         defining_bb = NULL;
1608                                 }
1609                         }
1610
1611                         if (defining_bb == NULL) {
1612                                 current_expression->reload = FALSE;
1613                                 availability_table [current_expression->redundancy_class].class_defined_by_real_occurrence = current_expression;
1614                         } else {
1615                                 current_expression->reload = TRUE;
1616
1617                                 area->occurrences_scheduled_for_reloading ++;
1618
1619                                 current_expression->defined_by_phi = availability_table [current_expression->redundancy_class].class_defined_by_phi;
1620                                 current_expression->defined_by_real_occurrence = availability_table [current_expression->redundancy_class].class_defined_by_real_occurrence;
1621                         }
1622
1623                         current_expression->save = FALSE;
1624                 }
1625
1626                 if (current_bb->has_phi_argument) {
1627                         MonoSsapreBBInfo *phi_bb = current_bb->out_bb [0];
1628                         if (((phi_bb->phi_can_be_available) && (! phi_bb->phi_is_later)) &&
1629                                         ((current_bb->phi_argument_class == BOTTOM_REDUNDANCY_CLASS) ||
1630                                         ((current_bb->phi_argument_has_real_use == FALSE) && (current_bb->phi_argument_defined_by_phi != NULL) &&
1631                                                 (! ((current_bb->phi_argument_defined_by_phi->phi_can_be_available) && (! current_bb->phi_argument_defined_by_phi->phi_is_later)))
1632                                         ))) {
1633                                 current_bb->phi_argument_needs_insert = TRUE;
1634
1635                                 area->arguments_scheduled_for_insertion ++;
1636                                 if (dominates (current_bb, phi_bb)) {
1637                                         area->dominating_arguments_scheduled_for_insertion ++;
1638                                 }
1639
1640                                 current_bb->phi_argument_defined_by_real_occurrence = NULL;
1641                                 current_bb->phi_argument_defined_by_phi = NULL;
1642                         } else {
1643                                 current_bb->phi_argument_needs_insert = FALSE;
1644                                 if (current_bb->phi_argument_class != BOTTOM_REDUNDANCY_CLASS) {
1645                                         current_bb->phi_argument_defined_by_real_occurrence = availability_table [current_bb->phi_argument_class].class_defined_by_real_occurrence;
1646                                         current_bb->phi_argument_defined_by_phi = availability_table [current_bb->phi_argument_class].class_defined_by_phi;
1647                                 }
1648                         }
1649
1650                         current_bb->phi_argument_has_been_processed = FALSE;
1651                 }
1652         }
1653 }
1654
1655 /*
1656  * See paper, figure 13, function Set_save
1657  */
1658 static void set_save (MonoSsapreBBInfo *phi_occurrance, MonoSsapreExpressionOccurrence *real_occurrance) {
1659         if (real_occurrance != NULL) {
1660                 real_occurrance->save = TRUE;
1661         } else if (phi_occurrance != NULL) {
1662                 int i;
1663                 for (i = 0; i < phi_occurrance->in_count; i++) {
1664                         MonoSsapreBBInfo *phi_argument = phi_occurrance->in_bb [i];
1665                         if (! phi_argument->phi_argument_has_been_processed) {
1666                                 phi_argument->phi_argument_has_been_processed = TRUE;
1667                                 set_save (phi_argument->phi_argument_defined_by_phi, phi_argument->phi_argument_defined_by_real_occurrence);
1668                         }
1669                 }
1670         }
1671 }
1672
1673 /*
1674  * See paper, figure 13, function Finalize_2 (note that we still don't do
1675  * extraneous PHI elimination, see function Set_replacement)
1676  */
1677 static void finalize_save (MonoSsapreWorkArea *area) {
1678         MonoSsapreBBInfo *current_bb = NULL;
1679         MonoSsapreExpressionOccurrence *current_expression = NULL;
1680
1681         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1682                 for (current_expression = current_bb->first_expression_in_bb; (current_expression != NULL) && (current_expression->bb_info == current_bb); current_expression = current_expression->next) {
1683                         if (current_expression->reload) {
1684                                 set_save (current_expression->defined_by_phi, current_expression->defined_by_real_occurrence);
1685                         }
1686                 }
1687
1688                 if ((current_bb->has_phi_argument) &&
1689                                 (! current_bb->phi_argument_needs_insert) &&
1690                                 (current_bb->phi_argument_class != BOTTOM_REDUNDANCY_CLASS) &&
1691                                 (current_bb->phi_argument_defined_by_real_occurrence != NULL)) {
1692                         current_bb->phi_argument_defined_by_real_occurrence->save = TRUE;
1693                 }
1694         }
1695 }
1696
1697 #define OP_IS_CHEAP(op) (((op)==CEE_ADD)||((op)==CEE_SUB))
1698 #define EXPRESSION_HAS_ICONST(d) (((d).left_argument.type==MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT)||((d).right_argument.type==MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT))
1699 #define EXPRESSION_IS_CHEAP(d) ((OP_IS_CHEAP ((d).opcode))&&(EXPRESSION_HAS_ICONST ((d))))
1700 #define REDUNDANCY_IS_SMALL(a) (((a)->occurrences_scheduled_for_reloading < 2)&&((a)->dominating_arguments_scheduled_for_insertion < 1))
1701
1702 /*
1703  * Perform all "finalize" steps.
1704  * Return TRUE if we must go on with code_motion.
1705  */
1706 static gboolean finalize (MonoSsapreWorkArea *area) {
1707         MonoSsapreAvailabilityTableElement *availability_table = alloca (sizeof (MonoSsapreAvailabilityTableElement) * (area->number_of_classes));
1708         int i;
1709
1710         for (i = 0; i < area->number_of_classes; i++) {
1711                 availability_table[i].class_defined_by_phi = NULL;
1712                 availability_table[i].class_defined_by_real_occurrence = NULL;
1713         }
1714
1715         finalize_availability_and_reload (area, availability_table);
1716
1717         /* Tuning: if the redundancy is not worth handling, give up */
1718         if ((EXPRESSION_IS_CHEAP (area->current_expression->description)) && (REDUNDANCY_IS_SMALL (area))) {
1719                 return FALSE;
1720         } else {
1721                 finalize_save (area);
1722                 return TRUE;
1723         }
1724 }
1725
1726 /*
1727  * Macros that help in creating constants
1728  */
1729 #define NEW_INST(dest,op) do {  \
1730                 (dest) = mono_mempool_alloc0 (area->cfg->mempool, sizeof (MonoInst));   \
1731                 (dest)->opcode = (op);  \
1732         } while (0)
1733
1734 #define NEW_I4(dest,val) do {   \
1735                 NEW_INST ((dest), OP_ICONST); \
1736                 (dest)->inst_c0 = (val);        \
1737                 (dest)->type = STACK_I4;        \
1738         } while (0)
1739
1740 #define NEW_I8(dest,val) do {   \
1741                 NEW_INST ((dest), OP_I8CONST); \
1742                 (dest)->inst_l = (val); \
1743                 (dest)->type = STACK_I8;        \
1744         } while (0)
1745
1746 #define NEW_R4(dest,f) do {     \
1747                 NEW_INST ((dest), OP_R4CONST); \
1748                 (dest)->inst_p0 = f;    \
1749                 (dest)->type = STACK_R8;        \
1750         } while (0)
1751
1752 #define NEW_R8(dest,d) do {     \
1753                 NEW_INST ((dest), OP_R8CONST); \
1754                 (dest)->inst_p0 = d;    \
1755                 (dest)->type = STACK_R8;        \
1756         } while (0)
1757
1758 /*
1759  * Create a MonoInst that represents an expression argument
1760  */
1761 static MonoInst*
1762 create_expression_argument (MonoSsapreWorkArea *area, MonoSsapreExpressionArgument *argument) {
1763         MonoInst *result;
1764
1765         switch (argument->type) {
1766                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_NOT_PRESENT:
1767                         return NULL;
1768                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE:
1769                         return mono_compile_create_var_load (area->cfg, argument->argument.ssa_variable);
1770                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT:
1771                         NEW_I4 (result, argument->argument.integer_constant);
1772                         return result;
1773                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_LONG_COSTANT:
1774                         NEW_I8 (result, *(argument->argument.long_constant));
1775                         return result;
1776                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT:
1777                         NEW_R4 (result, argument->argument.float_constant);
1778                         return result;
1779                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT:
1780                         NEW_R8 (result, argument->argument.double_constant);
1781                         return result;
1782                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE:
1783                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY:
1784                 default:
1785                         g_assert_not_reached ();
1786                         return NULL;
1787         }
1788 }
1789
1790 /*
1791  * Create a MonoInst that represents an expression
1792  */
1793 static MonoInst*
1794 create_expression (MonoSsapreWorkArea *area, MonoSsapreExpressionDescription *expression, MonoInst *prototype_occurrence) {
1795         MonoInst *result;
1796         NEW_INST (result, expression->opcode);
1797         *result = *prototype_occurrence;
1798         result->inst_left = create_expression_argument (area, &(expression->left_argument));
1799         result->inst_right = create_expression_argument (area, &(expression->right_argument));
1800         return result;
1801 }
1802
1803 /*
1804  * Handles the father expression of a MonoInst that has been turned
1805  * into a load (eventually inserting it into the worklist).
1806  * Assumes "current_expression->father_in_tree != NULL".
1807  */
1808 static void
1809 handle_father_expression (MonoSsapreWorkArea *area, MonoSsapreExpressionOccurrence *current_expression, MonoInst *previous_tree) {
1810         if (DUMP_SSAPRE) {
1811                 printf ("After reload, father expression becomes ");
1812                 mono_print_tree_nl (current_expression->father_in_tree->father_occurrence);
1813         }
1814
1815         analyze_expression (current_expression->father_in_tree->father_occurrence, &(area->current_occurrence->description));
1816         if ((area->current_occurrence->description.opcode != 0) &&
1817                         (area->current_occurrence->description.left_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY) &&
1818                         (area->current_occurrence->description.right_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY)) {
1819                 area->current_occurrence->occurrence = current_expression->father_in_tree->father_occurrence;
1820                 area->current_occurrence->previous_tree = previous_tree;
1821                 area->current_occurrence->father_in_tree = current_expression->father_in_tree->grand_father;
1822                 area->current_occurrence->bb_info = current_expression->bb_info;
1823                 area->current_occurrence->is_first_in_bb = FALSE;
1824                 area->current_occurrence->is_last_in_bb = FALSE;
1825                 add_occurrence_to_worklist (area);
1826         }
1827 }
1828
1829 /*
1830  * See paper, section 3.6
1831  */
1832 static void code_motion (MonoSsapreWorkArea *area) {
1833         MonoSsapreBBInfo *current_bb = NULL;
1834         MonoSsapreExpressionOccurrence *current_expression = NULL;
1835         gssize original_variable_index = BOTTOM_REDUNDANCY_CLASS;
1836         MonoInst prototype_occurrence;
1837         prototype_occurrence.opcode = 0;
1838
1839         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1840                 if ((current_bb->has_phi) && (current_bb->phi_can_be_available && ! current_bb->phi_is_later)) {
1841                         MonoInst *new_var = mono_compile_create_var (area->cfg, area->current_expression->type, OP_LOCAL);
1842                         current_bb->phi_variable_index = new_var->inst_c0;
1843                         if (original_variable_index == BOTTOM_REDUNDANCY_CLASS) {
1844                                 original_variable_index = new_var->inst_c0;
1845                         }
1846                         MONO_VARINFO (area->cfg, new_var->inst_c0)->reg = original_variable_index;
1847                         MONO_VARINFO (area->cfg, new_var->inst_c0)->def_bb = current_bb->bb;
1848                 } else {
1849                         current_bb->phi_variable_index = BOTTOM_REDUNDANCY_CLASS;
1850                 }
1851
1852                 for (current_expression = current_bb->first_expression_in_bb; (current_expression != NULL) && (current_expression->bb_info == current_bb); current_expression = current_expression->next) {
1853                         if (prototype_occurrence.opcode == 0) {
1854                                 prototype_occurrence = *(current_expression->occurrence);
1855                         }
1856                         if (current_expression->save) {
1857                                 MonoInst *new_var = mono_compile_create_var (area->cfg, area->current_expression->type, OP_LOCAL);
1858                                 current_expression->variable_index = new_var->inst_c0;
1859                                 if (original_variable_index == BOTTOM_REDUNDANCY_CLASS) {
1860                                         original_variable_index = new_var->inst_c0;
1861                                 }
1862                                 MONO_VARINFO (area->cfg, new_var->inst_c0)->reg = original_variable_index;
1863                                 MONO_VARINFO (area->cfg, new_var->inst_c0)->def_bb = current_bb->bb;
1864                         } else {
1865                                 current_expression->variable_index = BOTTOM_REDUNDANCY_CLASS;
1866                         }
1867                 }
1868
1869                 if ((current_bb->has_phi_argument) && (current_bb->phi_argument_needs_insert)) {
1870                         MonoInst *new_var = mono_compile_create_var (area->cfg, area->current_expression->type, OP_LOCAL);
1871                         current_bb->phi_argument_variable_index = new_var->inst_c0;
1872                         if (original_variable_index == BOTTOM_REDUNDANCY_CLASS) {
1873                                 original_variable_index = new_var->inst_c0;
1874                         }
1875                         MONO_VARINFO (area->cfg, new_var->inst_c0)->reg = original_variable_index;
1876                         MONO_VARINFO (area->cfg, new_var->inst_c0)->def_bb = current_bb->bb;
1877                 } else {
1878                         current_bb->phi_argument_variable_index = BOTTOM_REDUNDANCY_CLASS;
1879                 }
1880         }
1881
1882         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1883                 if (current_bb->phi_variable_index != BOTTOM_REDUNDANCY_CLASS) {
1884                         MonoInst *phi;
1885                         MonoInst *store;
1886                         int in_bb;
1887
1888                         NEW_INST (phi, OP_PHI);
1889                         phi->inst_c0 = MONO_VARINFO (area->cfg, current_bb->phi_variable_index)->reg;
1890                         phi->inst_phi_args = mono_mempool_alloc (area->cfg->mempool, (sizeof (int) * ((current_bb->in_count) + 1)));
1891                         phi->inst_phi_args [0] = current_bb->in_count;
1892                         for (in_bb = 0; in_bb < current_bb->in_count; in_bb++) {
1893                                 gssize phi_argument_variable_index = current_bb->in_bb [in_bb]->phi_argument_variable_index;
1894                                 if (phi_argument_variable_index == BOTTOM_REDUNDANCY_CLASS) {
1895                                         MonoSsapreBBInfo *phi_argument_bb = current_bb->in_bb [in_bb];
1896                                         if (phi_argument_bb->phi_argument_defined_by_phi !=NULL) {
1897                                                 phi_argument_variable_index = phi_argument_bb->phi_argument_defined_by_phi->phi_variable_index;
1898                                         } else if (phi_argument_bb->phi_argument_defined_by_real_occurrence !=NULL) {
1899                                                 phi_argument_variable_index = phi_argument_bb->phi_argument_defined_by_real_occurrence->variable_index;
1900                                         } else {
1901                                                 g_assert_not_reached ();
1902                                         }
1903                                 }
1904                                 phi->inst_phi_args [in_bb + 1] = phi_argument_variable_index;
1905                         }
1906                         store = mono_compile_create_var_store (area->cfg, current_bb->phi_variable_index, phi);
1907                         if (current_bb->phi_insertion_point != NULL) {
1908                                 store->next = current_bb->phi_insertion_point->next;
1909                                 current_bb->phi_insertion_point->next = store;
1910                         } else {
1911                                 store->next = current_bb->bb->code;
1912                                 current_bb->bb->code = store;
1913                         }
1914                         MONO_VARINFO (area->cfg, current_bb->phi_variable_index)->def = store;
1915                         current_bb->phi_insertion_point = store;
1916
1917                         area->added_phis ++;
1918                 }
1919
1920                 for (current_expression = current_bb->first_expression_in_bb; (current_expression != NULL) && (current_expression->bb_info == current_bb); current_expression = current_expression->next) {
1921                         gboolean altered = FALSE;
1922                         if (current_expression->save) {
1923                                 MonoInst *store;
1924                                 MonoInst *moved_expression = mono_mempool_alloc (area->cfg->mempool, sizeof (MonoInst));
1925                                 *moved_expression = *(current_expression->occurrence);
1926                                 store = mono_compile_create_var_store (area->cfg, current_expression->variable_index, moved_expression);
1927                                 if (current_expression->previous_tree != NULL) {
1928                                         store->next = current_expression->previous_tree->next;
1929                                         current_expression->previous_tree->next = store;
1930                                 } else {
1931                                         store->next = current_bb->bb->code;
1932                                         current_bb->bb->code = store;
1933                                 }
1934                                 MONO_VARINFO (area->cfg, current_expression->variable_index)->def = store;
1935                                 mono_compile_make_var_load (area->cfg, current_expression->occurrence, current_expression->variable_index);
1936                                 if (current_expression->father_in_tree != NULL) {
1937                                         handle_father_expression (area, current_expression, store);
1938                                 }
1939
1940                                 area->saved_occurrences ++;
1941                                 altered = TRUE;
1942                         }
1943                         if (current_expression->reload) {
1944                                 gssize variable_index;
1945                                 if (current_expression->defined_by_phi != NULL) {
1946                                         variable_index = current_expression->defined_by_phi->phi_variable_index;
1947                                 } else if (current_expression->defined_by_real_occurrence != NULL) {
1948                                         variable_index = current_expression->defined_by_real_occurrence->variable_index;
1949                                 } else {
1950                                         variable_index = BOTTOM_REDUNDANCY_CLASS;
1951                                         g_assert_not_reached ();
1952                                 }
1953                                 mono_compile_make_var_load (area->cfg, current_expression->occurrence, variable_index);
1954                                 if (current_expression->father_in_tree != NULL) {
1955                                         handle_father_expression (area, current_expression, current_expression->previous_tree);
1956                                 }
1957
1958                                 area->reloaded_occurrences ++;
1959                                 altered = TRUE;
1960                         }
1961                         if (! altered) {
1962                                 area->unaltered_occurrences ++;
1963                         }
1964                 }
1965
1966                 if (current_bb->phi_argument_variable_index != BOTTOM_REDUNDANCY_CLASS) {
1967                         MonoSsapreExpressionDescription expression_description;
1968                         MonoInst *inserted_expression;
1969                         MonoInst *store;
1970
1971                         expression_description = area->current_expression->description;
1972                         if (expression_description.left_argument.type == MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE) {
1973                                 expression_description.left_argument.argument.ssa_variable = current_bb->phi_argument_left_argument_version;
1974                                 expression_description.left_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE;
1975                         }
1976                         if (expression_description.right_argument.type == MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE) {
1977                                 expression_description.right_argument.argument.ssa_variable = current_bb->phi_argument_right_argument_version;
1978                                 expression_description.right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE;
1979                         }
1980
1981                         inserted_expression = create_expression (area, &expression_description, &prototype_occurrence);
1982                         store = mono_compile_create_var_store (area->cfg, current_bb->phi_argument_variable_index, inserted_expression);
1983                         MONO_VARINFO (area->cfg, current_bb->phi_argument_variable_index)->def = store;
1984                         store->next = NULL;
1985                         mono_add_ins_to_end (current_bb->bb, store);
1986
1987                         area->inserted_occurrences ++;
1988                 }
1989         }
1990 }
1991
1992 /*
1993  * Perform all SSAPRE steps for the current expression
1994  */
1995 static void
1996 process_expression (MonoSsapreWorkArea *area) {
1997         MonoSsapreExpression *expression = area->current_expression;
1998
1999         if (area->cfg->verbose_level >= STATISTICS_LEVEL) {
2000                 printf ("SSAPRE STARTS PROCESSING EXPRESSION ");
2001                 print_expression_description (&(expression->description));
2002                 printf ("\n");
2003         }
2004
2005         clean_area_infos (area);
2006
2007         area->current_expression = expression;
2008         phi_insertion (area, expression);
2009         renaming_pass (area);
2010
2011         if (area->cfg->verbose_level >= TRACE_LEVEL) {
2012                 printf ("START SUMMARY OF BB INFOS\n");
2013                 print_bb_infos (area);
2014                 printf ("END SUMMARY OF BB INFOS\n");
2015         }
2016
2017         down_safety (area);
2018         compute_can_be_available (area);
2019         compute_later (area);
2020         if (finalize (area)) {
2021                 code_motion (area);
2022         } else {
2023                 if (area->cfg->verbose_level >= TRACE_LEVEL) {
2024                         printf ("SSAPRE CODE MOTION SKIPPED\n");
2025                 }
2026         }
2027
2028
2029         if (area->cfg->verbose_level >= DUMP_LEVEL) {
2030                 printf ("START DUMP OF BB INFOS\n");
2031                 dump_code (area);
2032                 printf ("END DUMP OF BB INFOS\n");
2033         } else if (area->cfg->verbose_level >= TRACE_LEVEL) {
2034                 printf ("START SUMMARY OF BB INFOS\n");
2035                 print_interesting_bb_infos (area);
2036                 printf ("END SUMMARY OF BB INFOS\n");
2037         }
2038
2039         if (area->cfg->verbose_level >= STATISTICS_LEVEL) {
2040                 printf ("STATISTICS: saved_occurrences = %d, reloaded_occurrences = %d, inserted_occurrences = %d, unaltered_occurrences = %d, added_phis = %d\n",
2041                         area->saved_occurrences, area->reloaded_occurrences, area->inserted_occurrences, area->unaltered_occurrences, area->added_phis);
2042         }
2043
2044         if (area->cfg->verbose_level >= TRACE_LEVEL) {
2045                 printf ("SSAPRE ENDS PROCESSING EXPRESSION ");
2046                 print_expression_description (&(expression->description));
2047                 printf ("\n");
2048         }
2049 }
2050
2051 #if (MONO_APPLY_SSAPRE_TO_SINGLE_METHOD)
2052 static char*
2053 mono_ssapre_method_name = NULL;
2054 static gboolean check_ssapre_method_name (MonoCompile *cfg) {
2055         if (mono_ssapre_method_name == NULL) {
2056                 mono_ssapre_method_name = getenv ("MONO_SSAPRE_METHOD_NAME");
2057         }
2058         if (mono_ssapre_method_name != NULL) {
2059                 char *method_name = mono_method_full_name (cfg->method, TRUE);
2060                 if (strstr (method_name, mono_ssapre_method_name) != NULL) {
2061                         return TRUE;
2062                 } else {
2063                         return FALSE;
2064                 }
2065         } else {
2066                 return TRUE;
2067         }
2068 }
2069 #endif
2070
2071 /*
2072  * Apply SSAPRE to a MonoCompile
2073  */
2074 void
2075 mono_perform_ssapre (MonoCompile *cfg) {
2076         MonoSsapreWorkArea area;
2077         int dt_dfn, descendants, block, i;
2078
2079 #if (MONO_APPLY_SSAPRE_TO_SINGLE_METHOD)
2080         if (! check_ssapre_method_name (cfg)) return;
2081 #endif
2082 #if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
2083         area.expression_is_handled_father = FALSE;
2084 #endif
2085
2086         area.cfg = cfg;
2087         area.mempool = mono_mempool_new ();
2088
2089         area.num_bblocks = cfg->num_bblocks;
2090         area.bb_infos = (MonoSsapreBBInfo*) mono_mempool_alloc (area.mempool, sizeof (MonoSsapreBBInfo) * (cfg->num_bblocks));
2091         area.bb_infos_in_cfg_dfn_order = (MonoSsapreBBInfo**) mono_mempool_alloc (area.mempool, sizeof (MonoSsapreBBInfo*) * (cfg->num_bblocks));
2092
2093         area.sizeof_bb_bitset = mono_bitset_alloc_size (cfg->num_bblocks, 0);
2094         area.expression_occurrences_buffer = mono_bitset_mem_new (mono_mempool_alloc (area.mempool, area.sizeof_bb_bitset), area.num_bblocks, 0);
2095         area.bb_iteration_buffer = mono_bitset_mem_new (mono_mempool_alloc (area.mempool, area.sizeof_bb_bitset), area.num_bblocks, 0);
2096         area.iterated_dfrontier_buffer = mono_bitset_mem_new (mono_mempool_alloc (area.mempool, area.sizeof_bb_bitset), area.num_bblocks, 0);
2097         area.left_argument_bb_bitset = mono_bitset_mem_new (mono_mempool_alloc (area.mempool, area.sizeof_bb_bitset), area.num_bblocks, 0);
2098         area.right_argument_bb_bitset = mono_bitset_mem_new (mono_mempool_alloc (area.mempool, area.sizeof_bb_bitset), area.num_bblocks, 0);
2099
2100         area.worklist = NULL;
2101
2102         if (area.cfg->verbose_level >= LOG_LEVEL) {
2103                 printf ("SSAPRE STARTS PROCESSING METHOD %s\n", mono_method_full_name (cfg->method, TRUE));
2104         }
2105         if (area.cfg->verbose_level >= DUMP_LEVEL) {
2106                 mono_print_code (area.cfg, "BEFORE SSAPRE");
2107         }
2108
2109         area.first_in_queue = NULL;
2110         area.last_in_queue = NULL;
2111         area.current_occurrence = (MonoSsapreExpressionOccurrence*) mono_mempool_alloc (area.mempool, sizeof (MonoSsapreExpressionOccurrence));
2112         dt_dfn = 0;
2113         descendants = 0;
2114         area.dt_depth = 0;
2115         process_bb (&area, cfg->bblocks [0], &dt_dfn, &descendants, 1);
2116         for (block = 0; block < area.num_bblocks; block++) {
2117                 MonoSsapreBBInfo *bb_info = &(area.bb_infos [block]);
2118                 MonoBasicBlock *bb = bb_info->bb;
2119                 if (bb->idom != NULL) {
2120                         bb_info->idominator = area.bb_infos_in_cfg_dfn_order [bb->idom->dfn];
2121                 } else {
2122                         bb_info->idominator = NULL;
2123                 }
2124                 for (i = 0; i < bb->in_count; i++) {
2125                         bb_info->in_bb [i] = area.bb_infos_in_cfg_dfn_order [bb->in_bb [i]->dfn];
2126                 }
2127                 for (i = 0; i < bb->out_count; i++) {
2128                         bb_info->out_bb [i] = area.bb_infos_in_cfg_dfn_order [bb->out_bb [i]->dfn];
2129                 }
2130         }
2131
2132         if (area.cfg->verbose_level >= TRACE_LEVEL) {
2133                 printf ("SSAPRE START WORKLIST\n");
2134                 print_worklist (area.worklist);
2135                 printf ("SSAPRE END WORKLIST\n");
2136         }
2137
2138 #if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
2139         area.expression_is_handled_father = TRUE;
2140 #endif
2141         for (area.current_expression = area.first_in_queue; area.current_expression != NULL; area.current_expression = area.current_expression->next_in_queue) {
2142                 process_expression (&area);
2143         }
2144
2145         if (area.cfg->verbose_level >= DUMP_LEVEL) {
2146                 mono_print_code (area.cfg, "AFTER SSAPRE");
2147         }
2148         if (area.cfg->verbose_level >= TRACE_LEVEL) {
2149                 printf ("SSAPRE ENDS PROCESSING METHOD %s\n", mono_method_full_name (cfg->method, TRUE));
2150         }
2151
2152         mono_mempool_destroy (area.mempool);
2153 }
2154
2155 #endif /* DISABLE_SSA */
2156