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 "inssel.h"
  18
  19 #include "ssapre.h"
  20
  21 /* Logging conditions */
  22 #define DUMP_LEVEL (4)
  23 #define TRACE_LEVEL (3)
  24 #define STATISTICS_LEVEL (2)
  25 #define LOG_LEVEL (1)
  26 #define DUMP_SSAPRE (area->cfg->verbose_level >= DUMP_LEVEL)
  27 #define TRACE_SSAPRE (area->cfg->verbose_level >= TRACE_LEVEL)
  28 #define STATISTICS_SSAPRE (area->cfg->verbose_level >= STATISTICS_LEVEL)
  29 #define LOG_SSAPRE (area->cfg->verbose_level >= LOG_LEVEL)
  30
  31 /* "Bottom" symbol definition (see paper) */
  32 #define BOTTOM_REDUNDANCY_CLASS (-1)
  33
  34 /* Various printing functions... */
  35 static void
  36 print_argument (MonoSsapreExpressionArgument *argument) {
  37         switch (argument->type) {
  38                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY:
  39                         printf ("ANY");
  40                         break;
  41                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_NOT_PRESENT:
  42                         printf ("NONE");
  43                         break;
  44                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE:
  45                         printf ("ORIGINAL_VARIABLE %d", argument->argument.original_variable);
  46                         break;
  47                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE:
  48                         printf ("SSA_VARIABLE %d", argument->argument.ssa_variable);
  49                         break;
  50                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT:
  51                         printf ("INTEGER_CONSTANT %d", argument->argument.integer_constant);
  52                         break;
  53                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_LONG_COSTANT:
  54                         printf ("LONG_COSTANT %lld", (long long)*(argument->argument.long_constant));
  55                         break;
  56                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT:
  57                         printf ("FLOAT_COSTANT %f", *(argument->argument.float_constant));
  58                         break;
  59                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT:
  60                         printf ("DOUBLE_COSTANT %f", *(argument->argument.double_constant));
  61                         break;
  62                 default:
  63                         printf ("UNKNOWN: %d", argument->type);
  64         }
  65 }
  66
  67
  68 static void
  69 print_expression_description (MonoSsapreExpressionDescription *expression_description) {
  70         if (expression_description->opcode != 0) {
  71                 printf ("%s ([", mono_inst_name (expression_description->opcode) );
  72                 print_argument (&(expression_description->left_argument));
  73                 printf ("],[");
  74                 print_argument (&(expression_description->right_argument));
  75                 printf ("])");
  76         } else {
  77                 printf ("ANY");
  78         }
  79 }
  80
  81 #if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
  82 static void
  83 snprint_argument (GString *string, MonoSsapreExpressionArgument *argument) {
  84         switch (argument->type) {
  85                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY:
  86                         g_string_append_printf (string, "ANY");
  87                         break;
  88                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_NOT_PRESENT:
  89                         g_string_append_printf (string, "NONE");
  90                         break;
  91                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE:
  92                         g_string_append_printf (string, "ORIGINAL_VARIABLE %d", argument->argument.original_variable);
  93                         break;
  94                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE:
  95                         g_string_append_printf (string, "SSA_VARIABLE %d", argument->argument.ssa_variable);
  96                         break;
  97                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT:
  98                         g_string_append_printf (string, "INTEGER_CONSTANT %d", argument->argument.integer_constant);
  99                         break;
 100                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_LONG_COSTANT:
 101                         g_string_append_printf (string, "LONG_COSTANT %lld", *(argument->argument.long_constant));
 102                         break;
 103                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT:
 104                         g_string_append_printf (string, "FLOAT_COSTANT %f", *(argument->argument.float_constant));
 105                         break;
 106                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT:
 107                         g_string_append_printf (string, "DOUBLE_COSTANT %f", *(argument->argument.double_constant));
 108                         break;
 109                 default:
 110                         g_string_append_printf (string, "UNKNOWN: %d", argument->type);
 111         }
 112 }
 113
 114 static void
 115 snprint_expression_description (GString *string, MonoSsapreExpressionDescription *expression_description) {
 116         if (expression_description->opcode != 0) {
 117                 g_string_append_printf (string, "%s ([", mono_inst_name (expression_description->opcode) );
 118                 snprint_argument (string, &(expression_description->left_argument));
 119                 g_string_append_printf (string, "],[");
 120                 snprint_argument (string, &(expression_description->right_argument));
 121                 g_string_append_printf (string, "])");
 122         } else {
 123                 g_string_append_printf (string, "ANY");
 124         }
 125 }
 126 #endif
 127
 128 #define GBOOLEAN_TO_STRING(b) ((b)?"TRUE":"FALSE")
 129
 130 static void
 131 print_expression_occurrence (MonoSsapreExpressionOccurrence *occurrence, int number) {
 132         printf (" ([%d][bb %d [ID %d]][class %d]: ", number, occurrence->bb_info->cfg_dfn, occurrence->bb_info->bb->block_num, occurrence->redundancy_class);
 133         print_expression_description (&(occurrence->description));
 134         if (occurrence->is_first_in_bb) {
 135                 printf (" [FIRST in BB]");
 136         }
 137         if (occurrence->is_last_in_bb) {
 138                 printf (" [LAST in BB]");
 139         }
 140         printf (" (save = %s)", GBOOLEAN_TO_STRING (occurrence->save));
 141         printf (" (reload = %s)", GBOOLEAN_TO_STRING (occurrence->reload));
 142         printf ("\n");
 143         occurrence = occurrence->next;
 144 }
 145
 146 static void
 147 print_expression_occurrences (MonoSsapreExpressionOccurrence *occurrences) {
 148         int i = 0;
 149         while (occurrences != NULL) {
 150                 i++;
 151                 print_expression_occurrence (occurrences, i);
 152                 occurrences = occurrences->next;
 153         }
 154 }
 155
 156 static void
 157 print_worklist (MonoSsapreExpression *expression) {
 158         if (expression != NULL) {
 159                 print_worklist (expression->previous);
 160
 161                 printf ("{%d}: ", expression->tree_size);
 162                 print_expression_description (&(expression->description));
 163                 printf ("\n");
 164                 print_expression_occurrences (expression->occurrences);
 165
 166                 print_worklist (expression->next);
 167         }
 168 }
 169
 170 static void
 171 print_bb_info (MonoSsapreBBInfo *bb_info, gboolean print_occurrences) {
 172         int i;
 173         MonoSsapreExpressionOccurrence *current_occurrence = bb_info->first_expression_in_bb;
 174
 175         printf ("bb %d [ID %d]: IN { ", bb_info->cfg_dfn, bb_info->bb->block_num);
 176         for (i = 0; i < bb_info->in_count; i++) {
 177                 printf ("%d [ID %d] ", bb_info->in_bb [i]->cfg_dfn, bb_info->in_bb [i]->bb->block_num);
 178         }
 179         printf ("}, OUT {");
 180         for (i = 0; i < bb_info->out_count; i++) {
 181                 printf ("%d [ID %d] ", bb_info->out_bb [i]->cfg_dfn, bb_info->out_bb [i]->bb->block_num);
 182         }
 183         printf ("}");
 184         if (bb_info->next_interesting_bb != NULL) {
 185                 printf (", NEXT %d [ID %d]", bb_info->next_interesting_bb->cfg_dfn, bb_info->next_interesting_bb->bb->block_num);
 186         }
 187         if (bb_info->dt_covered_by_interesting_BBs) {
 188                 printf (" (COVERED)");
 189         } else {
 190                 printf (" (NEVER DOWN SAFE)");
 191         }
 192         printf ("\n");
 193         if (bb_info->has_phi) {
 194                 printf (" PHI, class %d [ ", bb_info->phi_redundancy_class);
 195                 for (i = 0; i < bb_info->in_count; i++) {
 196                         int argument_class = bb_info->phi_arguments_classes [i];
 197                         if (argument_class != BOTTOM_REDUNDANCY_CLASS) {
 198                                 printf ("%d ", argument_class);
 199                         } else {
 200                                 printf ("BOTTOM ");
 201                         }
 202                 }
 203                 printf ("]\n(phi_defines_a_real_occurrence:%s) (phi_is_down_safe:%s) (phi_can_be_available:%s) (phi_is_later:%s)\n",
 204                                 GBOOLEAN_TO_STRING (bb_info->phi_defines_a_real_occurrence), GBOOLEAN_TO_STRING (bb_info->phi_is_down_safe),
 205                                 GBOOLEAN_TO_STRING (bb_info->phi_can_be_available), GBOOLEAN_TO_STRING (bb_info->phi_is_later));
 206         }
 207         if (print_occurrences) {
 208                 i = 0;
 209                 while ((current_occurrence != NULL) && (current_occurrence->bb_info == bb_info)) {
 210                         print_expression_occurrence (current_occurrence, i);
 211                         current_occurrence = current_occurrence->next;
 212                         i++;
 213                 }
 214         }
 215         if (bb_info->has_phi_argument) {
 216                 printf (" PHI ARGUMENT, class ");
 217                 if (bb_info->phi_argument_class != BOTTOM_REDUNDANCY_CLASS) {
 218                         printf ("%d ", bb_info->phi_argument_class);
 219                 } else {
 220                         printf ("BOTTOM ");
 221                 }
 222                 if (bb_info->phi_argument_defined_by_real_occurrence != NULL) {
 223                         printf ("(Defined by real occurrence %d)", bb_info->phi_argument_defined_by_real_occurrence->redundancy_class);
 224                 } else if (bb_info->phi_argument_defined_by_phi != NULL) {
 225                         printf ("(Defined by phi %d)", bb_info->phi_argument_defined_by_phi->phi_redundancy_class);
 226                 } else {
 227                         printf ("(Undefined)");
 228                 }
 229                 printf (" (real occurrence arguments: left ");
 230                 if (bb_info->phi_argument_left_argument_version != BOTTOM_REDUNDANCY_CLASS) {
 231                         printf ("%d ", bb_info->phi_argument_left_argument_version);
 232                 } else {
 233                         printf ("NONE ");
 234                 }
 235                 printf (", right ");
 236                 if (bb_info->phi_argument_right_argument_version != BOTTOM_REDUNDANCY_CLASS) {
 237                         printf ("%d ", bb_info->phi_argument_right_argument_version);
 238                 } else {
 239                         printf ("NONE ");
 240                 }
 241                 printf (")\n(phi_argument_has_real_use:%s) (phi_argument_needs_insert:%s) (phi_argument_has_been_processed:%s)\n",
 242                                 GBOOLEAN_TO_STRING (bb_info->phi_argument_has_real_use), GBOOLEAN_TO_STRING (bb_info->phi_argument_needs_insert),
 243                                 GBOOLEAN_TO_STRING (bb_info->phi_argument_has_been_processed));
 244         }
 245 }
 246
 247 static void
 248 print_bb_infos (MonoSsapreWorkArea *area) {
 249         int i;
 250         for (i = 0; i < area->num_bblocks; i++) {
 251                 MonoSsapreBBInfo *bb_info = &(area->bb_infos [i]);
 252                 print_bb_info (bb_info, TRUE);
 253         }
 254 }
 255
 256 static void
 257 print_interesting_bb_infos (MonoSsapreWorkArea *area) {
 258         MonoSsapreBBInfo *current_bb;
 259
 260         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
 261                 print_bb_info (current_bb, FALSE);
 262         }
 263 }
 264
 265 static void dump_code (MonoSsapreWorkArea *area) {
 266         int i;
 267
 268         for (i = 0; i < area->num_bblocks; i++) {
 269                 MonoSsapreBBInfo *current_bb = &(area->bb_infos [i]);
 270                 MonoInst *current_inst;
 271
 272                 print_bb_info (current_bb, TRUE);
 273                 for (current_inst = current_bb->bb->code; current_inst != NULL; current_inst = current_inst->next) {
 274                         mono_print_tree_nl (current_inst);
 275                 }
 276         }
 277 }
 278
 279 /*
 280  * Given a MonoInst, it tries to describe it as an expression argument.
 281  * If this is not possible, the result will be of type
 282  * MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY.
 283  */
 284 static void
 285 analyze_argument (MonoInst *argument, MonoSsapreExpressionArgument *result) {
 286         switch (argument->opcode) {
 287         case CEE_LDIND_I1:
 288         case CEE_LDIND_U1:
 289         case CEE_LDIND_I2:
 290         case CEE_LDIND_U2:
 291         case CEE_LDIND_I4:
 292         case CEE_LDIND_U4:
 293         case CEE_LDIND_I8:
 294         case CEE_LDIND_I:
 295         case CEE_LDIND_R4:
 296         case CEE_LDIND_R8:
 297         case CEE_LDIND_REF:
 298                 if ((argument->inst_left->opcode == OP_LOCAL) || (argument->inst_left->opcode == OP_ARG)) {
 299                         result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE;
 300                         result->argument.ssa_variable = argument->inst_left->inst_c0;
 301                 } else {
 302                         result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 303                 }
 304                 break;
 305         case OP_ICONST:
 306                 result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT;
 307                 result->argument.integer_constant = argument->inst_c0;
 308                 break;
 309         case OP_I8CONST:
 310                 result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_LONG_COSTANT;
 311                 result->argument.long_constant = &(argument->inst_l);
 312                 break;
 313         case OP_R4CONST:
 314                 if (! isnan (*((float*)argument->inst_p0))) {
 315                         result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT;
 316                         result->argument.float_constant = (float*)argument->inst_p0;
 317                 } else {
 318                         result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 319                 }
 320                 break;
 321         case OP_R8CONST:
 322                 if (! isnan (*((double*)argument->inst_p0))) {
 323                         result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT;
 324                         result->argument.double_constant = (double*)argument->inst_p0;
 325                 } else {
 326                         result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 327                 }
 328                 break;
 329         default:
 330                 result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 331         }
 332 }
 333
 334
 335 /*
 336  * Given a MonoInst, it tries to describe it as an expression.
 337  * If this is not possible, the result will have opcode 0.
 338  */
 339 static void
 340 analyze_expression (MonoInst *expression, MonoSsapreExpressionDescription *result) {
 341         switch (expression->opcode) {
 342 #define SSAPRE_SPECIFIC_OPS 1
 343 #define OPDEF(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10) case a1:
 344 #include "simple-cee-ops.h"
 345 #undef OPDEF
 346 #define MINI_OP(a1,a2) case a1:
 347 #include "simple-mini-ops.h"
 348 #undef MINI_OP
 349 #undef SSAPRE_SPECIFIC_OPS
 350                 if ( (expression->type == STACK_I4) ||
 351                                 (expression->type == STACK_PTR) ||
 352                                 (expression->type == STACK_MP) ||
 353                                 (expression->type == STACK_I8) ||
 354                                 (expression->type == STACK_R8) ) {
 355                         if (mono_burg_arity [expression->opcode] > 0) {
 356                                 result->opcode = expression->opcode;
 357                                 analyze_argument (expression->inst_left, &(result->left_argument));
 358                                 if (mono_burg_arity [expression->opcode] > 1) {
 359                                         analyze_argument (expression->inst_right, &(result->right_argument));
 360                                 } else {
 361                                         result->right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_NOT_PRESENT;
 362                                 }
 363                         } else {
 364                                 result->opcode = 0;
 365                         }
 366                 } else {
 367                         result->opcode = 0;
 368                         //~ if (expression->type != 0) {
 369                                 //~ MonoType *type = mono_type_from_stack_type (expression);
 370                                 //~ 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);
 371                         //~ } else {
 372                                 //~ printf ("SSAPRE cannot really handle expression of opcode %s (%d)\n", mono_inst_name (expression->opcode), expression->opcode);
 373                         //~ }
 374                 }
 375                 break;
 376         default:
 377                 result->opcode = 0;
 378                 result->left_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 379                 result->right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 380         }
 381         //~ switch (expression->opcode) {
 382         //~ case CEE_ADD:
 383                 //~ if ((result->left_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT) &&
 384                                 //~ (result->right_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT)) {
 385                         //~ break;
 386                 //~ }
 387         //~ case CEE_LDELEMA:
 388         //~ case CEE_LDLEN:
 389                 //~ result->opcode = 0;
 390                 //~ result->left_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 391                 //~ result->right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 392         //~ }
 393 }
 394
 395 /*
 396  * Given an expression description, if any of its arguments has type
 397  * MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE it transforms it to a
 398  * MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE, converting the
 399  * variable index to its "original" one.
 400  * The resulting description is OK for a "MonoSsapreExpression" (the
 401  * initial description came from a "MonoSsapreExpressionOccurrence").
 402  */
 403 static void
 404 convert_ssa_variables_to_original_names (MonoSsapreExpressionDescription *result, MonoSsapreExpressionDescription *expression, MonoCompile *cfg) {
 405         gssize original_variable;
 406
 407         result->opcode = expression->opcode;
 408         if (expression->left_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE) {
 409                 result->left_argument = expression->left_argument;
 410         } else {
 411                 result->left_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE;
 412                 original_variable = cfg->vars [expression->left_argument.argument.ssa_variable]->reg;
 413                 if (original_variable >= 0) {
 414                         result->left_argument.argument.original_variable = original_variable;
 415                 } else {
 416                         result->left_argument.argument.original_variable = expression->left_argument.argument.ssa_variable;
 417                 }
 418         }
 419         if (expression->right_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE) {
 420                 result->right_argument = expression->right_argument;
 421         } else {
 422                 result->right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE;
 423                 original_variable = cfg->vars [expression->right_argument.argument.ssa_variable]->reg;
 424                 if (original_variable >= 0) {
 425                         result->right_argument.argument.original_variable = original_variable;
 426                 } else {
 427                         result->right_argument.argument.original_variable = expression->right_argument.argument.ssa_variable;
 428                 }
 429         }
 430 }
 431
 432 /*
 433  * Given a MonoInst, checks if it is a phi definition.
 434  */
 435 static gboolean
 436 is_phi_definition (MonoInst *definition) {
 437         if (definition != NULL) {
 438                 switch (definition->opcode) {
 439                 case CEE_STIND_REF:
 440                 case CEE_STIND_I:
 441                 case CEE_STIND_I4:
 442                 case CEE_STIND_I1:
 443                 case CEE_STIND_I2:
 444                 case CEE_STIND_I8:
 445                 case CEE_STIND_R4:
 446                 case CEE_STIND_R8:
 447                         if ((definition->inst_left->opcode == OP_LOCAL) &&
 448                                         (definition->inst_right->opcode == OP_PHI)) {
 449                                 return TRUE;
 450                         } else {
 451                                 return FALSE;
 452                         }
 453                 default:
 454                         return FALSE;
 455                 }
 456         } else {
 457                 return FALSE;
 458         }
 459 }
 460
 461 /*
 462  * Given a variable index, checks if it is a phi definition
 463  * (it assumes the "area" is visible).
 464  */
 465 #define IS_PHI_DEFINITION(v) is_phi_definition (area->cfg->vars [v]->def)
 466
 467 /*
 468  * Given a variable index, checks if it is a phi definition.
 469  * If it is so, it returns the array of integers pointed to by the phi MonoInst
 470  * (the one containing the length and the phi arguments), otherwise returns NULL.
 471  */
 472 static int*
 473 get_phi_definition (MonoCompile *cfg, gssize variable) {
 474         MonoInst *definition = cfg->vars [variable]->def;
 475         if (is_phi_definition (definition) && (definition->inst_left->inst_c0 == variable)) {
 476                 return definition->inst_right->inst_phi_args;
 477         } else {
 478                 return NULL;
 479         }
 480 }
 481
 482 /*
 483  * Given a variable index, returns the BB where the variable is defined.
 484  * If the variable appears to have no definition, it returns the entry BB
 485  * (the logic is that if it has no definition it is an argument, or a sort
 486  * of constant, and in both cases it is defined in the entry BB).
 487  */
 488 static MonoSsapreBBInfo*
 489 get_bb_info_of_definition (MonoSsapreWorkArea *area, gssize variable) {
 490         MonoBasicBlock *def_bb = area->cfg->vars [variable]->def_bb;
 491         if (def_bb != NULL) {
 492                 return area->bb_infos_in_cfg_dfn_order [def_bb->dfn];
 493         } else {
 494                 return area->bb_infos;
 495         }
 496 }
 497
 498 /*
 499  * Given:
 500  * - a variable index,
 501  * - a BB (the "current" BB), and
 502  * - a "phi argument index" (or index in the "in_bb" of the current BB),
 503  * it checks if the variable is a phi.
 504  * If it is so, it returns the variable index at the in_bb corresponding to
 505  * the given index, otherwise it return the variable index unchanged.
 506  * The logic is to return the variable version at the given predecessor BB.
 507  */
 508 static gssize
 509 get_variable_version_at_predecessor_bb (MonoSsapreWorkArea *area, gssize variable, MonoSsapreBBInfo *current_bb, int phi_operand) {
 510         MonoSsapreBBInfo *definition_bb = get_bb_info_of_definition (area, variable);
 511         int *phi_definition = get_phi_definition (area->cfg, variable);
 512         if ((definition_bb == current_bb) && (phi_definition != NULL)) {
 513                 return phi_definition [phi_operand + 1];
 514         } else {
 515                 return variable;
 516         }
 517 }
 518
 519 /*
 520  * Adds an expression to an autobalancing binary tree of expressions.
 521  * Returns the new tree root (it can be different from "tree" because of the
 522  * autobalancing).
 523  */
 524 static MonoSsapreExpression*
 525 add_expression_to_tree (MonoSsapreExpression *tree, MonoSsapreExpression *expression) {
 526         MonoSsapreExpression *subtree;
 527         MonoSsapreExpression **subtree_reference;
 528         int comparison;
 529         gssize max_tree_depth, max_subtree_size;
 530
 531         if (tree == NULL) {
 532                 expression->previous = NULL;
 533                 expression->next = NULL;
 534                 expression->tree_size = 1;
 535                 return expression;
 536         }
 537
 538         tree->tree_size++;
 539
 540         comparison = MONO_COMPARE_SSAPRE_EXPRESSION_DESCRIPTIONS (expression->description, tree->description);
 541         if (comparison > 0) {
 542                 if (tree->next != NULL) {
 543                         subtree = tree->next;
 544                         subtree_reference = &(tree->next);
 545                 } else {
 546                         tree->next = expression;
 547                         expression->father = tree;
 548                         expression->previous = NULL;
 549                         expression->next = NULL;
 550                         expression->tree_size = 1;
 551                         return tree;
 552                 }
 553         } else if (comparison < 0) {
 554                 if (tree->previous != NULL) {
 555                         subtree = tree->previous;
 556                         subtree_reference = &(tree->previous);
 557                 } else {
 558                         tree->previous = expression;
 559                         expression->father = tree;
 560                         expression->previous = NULL;
 561                         expression->next = NULL;
 562                         expression->tree_size = 1;
 563                         return tree;
 564                 }
 565         } else {
 566                 g_assert_not_reached ();
 567                 return NULL;
 568         }
 569
 570         MONO_SSAPRE_MAX_TREE_DEPTH (tree->tree_size, max_tree_depth);
 571         max_subtree_size = (1 << max_tree_depth) -1;
 572
 573         if (subtree->tree_size < max_subtree_size) {
 574                 *subtree_reference = add_expression_to_tree (subtree, expression);
 575                 (*subtree_reference)->father = tree;
 576                 return tree;
 577         } else {
 578                 MonoSsapreExpression *other_subtree;
 579                 MonoSsapreExpression *border_expression;
 580                 MonoSsapreExpression *border_expression_subtree;
 581                 MonoSsapreExpression **border_expression_reference_from_father;
 582                 int comparison_with_border;
 583
 584                 border_expression = subtree;
 585                 if (comparison > 0) {
 586                         other_subtree = tree->previous;
 587                         MONO_SSAPRE_GOTO_FIRST_EXPRESSION (border_expression);
 588                         border_expression_subtree = border_expression->next;
 589                         border_expression_reference_from_father = &(border_expression->father->previous);
 590                 } else if (comparison < 0) {
 591                         other_subtree = tree->next;
 592                         MONO_SSAPRE_GOTO_LAST_EXPRESSION (border_expression);
 593                         border_expression_subtree = border_expression->previous;
 594                         border_expression_reference_from_father = &(border_expression->father->next);
 595                 } else {
 596                         g_assert_not_reached ();
 597                         return NULL;
 598                 }
 599                 comparison_with_border = MONO_COMPARE_SSAPRE_EXPRESSION_DESCRIPTIONS (expression->description, border_expression->description);
 600
 601                 if ((comparison + comparison_with_border) != 0) {
 602                         MonoSsapreExpression *border_expression_iterator = border_expression->father;
 603                         while (border_expression_iterator != tree) {
 604                                 border_expression_iterator->tree_size--;
 605                                 border_expression_iterator = border_expression_iterator->father;
 606                         }
 607
 608                         if (border_expression != subtree) {
 609                                 *border_expression_reference_from_father = border_expression_subtree;
 610                         } else {
 611                                 subtree = border_expression_subtree;
 612                         }
 613                         if (border_expression_subtree != NULL) {
 614                                 border_expression_subtree->father = border_expression->father;
 615                         }
 616
 617                         if (comparison > 0) {
 618                                 border_expression->previous = add_expression_to_tree (other_subtree, tree);
 619                                 border_expression->next = add_expression_to_tree (subtree, expression);
 620                         } else if (comparison < 0) {
 621                                 border_expression->previous = add_expression_to_tree (subtree, expression);
 622                                 border_expression->next = add_expression_to_tree (other_subtree, tree);
 623                         } else {
 624                                 g_assert_not_reached ();
 625                                 return NULL;
 626                         }
 627                         border_expression->tree_size = 1 + border_expression->previous->tree_size + border_expression->next->tree_size;
 628                         return border_expression;
 629                 } else {
 630                         if (comparison > 0) {
 631                                 expression->previous = add_expression_to_tree (other_subtree, tree);
 632                                 expression->next = subtree;
 633                         } else if (comparison < 0) {
 634                                 expression->previous = subtree;
 635                                 expression->next = add_expression_to_tree (other_subtree, tree);
 636                         } else {
 637                                 g_assert_not_reached ();
 638                                 return NULL;
 639                         }
 640                         expression->tree_size = 1 + expression->previous->tree_size + expression->next->tree_size;
 641                         return expression;
 642                 }
 643         }
 644 }
 645
 646 #if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
 647 static char *mono_ssapre_expression_name = NULL;
 648 static gboolean
 649 check_ssapre_expression_name (MonoSsapreWorkArea *area, MonoSsapreExpressionDescription *expression_description) {
 650         if (area->expression_is_handled_father) {
 651                 return TRUE;
 652         }
 653         if (mono_ssapre_expression_name == NULL) {
 654                 mono_ssapre_expression_name = getenv ("MONO_SSAPRE_EXPRESSION_NAME");
 655         }
 656         if (mono_ssapre_expression_name != NULL) {
 657                 GString *expression_name = g_string_new_len ("", 256);
 658                 gboolean return_value;
 659                 snprint_expression_description (expression_name, expression_description);
 660                 if (strstr (expression_name->str, mono_ssapre_expression_name) != NULL) {
 661                         return_value = TRUE;
 662                 } else {
 663                         return_value = FALSE;
 664                 }
 665                 g_string_free (expression_name, TRUE);
 666                 return return_value;
 667         } else {
 668                 return TRUE;
 669         }
 670 }
 671 #endif
 672
 673 /*
 674  * Adds an expression to the worklist (putting the current occurrence as first
 675  * occurrence of this expression).
 676  */
 677 static void
 678 add_expression_to_worklist (MonoSsapreWorkArea *area) {
 679         MonoSsapreExpressionOccurrence *occurrence = area->current_occurrence;
 680         MonoSsapreExpression *expression = (MonoSsapreExpression*) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreExpression));
 681
 682         convert_ssa_variables_to_original_names (&(expression->description), &(occurrence->description), area->cfg);
 683
 684 #if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
 685         if (! check_ssapre_expression_name (area, &(expression->description))) return;
 686 #endif
 687
 688         expression->type = mono_type_from_stack_type (occurrence->occurrence);
 689         expression->occurrences = NULL;
 690         expression->last_occurrence = NULL;
 691         expression->next_in_queue = NULL;
 692         if (area->last_in_queue != NULL) {
 693                 area->last_in_queue->next_in_queue = expression;
 694         } else {
 695                 area->first_in_queue = expression;
 696         }
 697         area->last_in_queue = expression;
 698         MONO_SSAPRE_ADD_EXPRESSION_OCCURRANCE (expression, occurrence);
 699
 700         area->worklist = add_expression_to_tree (area->worklist, expression);
 701         area->worklist->father = NULL;
 702 }
 703
 704 /*
 705  * Adds the current expression occurrence to the worklist.
 706  * If its expression is not yet in the worklist, it is created.
 707  */
 708 static void
 709 add_occurrence_to_worklist (MonoSsapreWorkArea *area) {
 710         MonoSsapreExpressionDescription description;
 711         MonoSsapreExpression *current_expression;
 712         int comparison;
 713
 714         convert_ssa_variables_to_original_names (&description, &(area->current_occurrence->description), area->cfg);
 715         current_expression = area->worklist;
 716
 717         do {
 718                 if (current_expression != NULL) {
 719                         comparison = MONO_COMPARE_SSAPRE_EXPRESSION_DESCRIPTIONS (description, current_expression->description);
 720
 721                         if (comparison > 0) {
 722                                 current_expression = current_expression->next;
 723                         } else if (comparison < 0) {
 724                                 current_expression = current_expression->previous;
 725                         } else {
 726                                 MONO_SSAPRE_ADD_EXPRESSION_OCCURRANCE (current_expression, area->current_occurrence);
 727                         }
 728                 } else {
 729                         add_expression_to_worklist (area);
 730                         comparison = 0;
 731                 }
 732         } while (comparison != 0);
 733
 734         area->current_occurrence = (MonoSsapreExpressionOccurrence*) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreExpressionOccurrence));
 735 }
 736
 737 /*
 738  * Process a MonoInst, and of it is a valid expression add it to the worklist.
 739  */
 740 static void
 741 process_inst (MonoSsapreWorkArea *area, MonoInst* inst, MonoInst* previous_inst, MonoSsapreFatherExpression*** father_in_tree, MonoSsapreBBInfo *bb_info) {
 742         MonoSsapreFatherExpression** left_father_in_tree = NULL;
 743         MonoSsapreFatherExpression** right_father_in_tree = NULL;
 744
 745         if (mono_burg_arity [inst->opcode] > 0) {
 746                 process_inst (area, inst->inst_left, previous_inst, &left_father_in_tree, bb_info);
 747                 if (mono_burg_arity [inst->opcode] > 1) {
 748                         process_inst (area, inst->inst_right, previous_inst, &right_father_in_tree, bb_info);
 749                 }
 750         }
 751
 752         analyze_expression (inst, &(area->current_occurrence->description));
 753         if (area->current_occurrence->description.opcode != 0) {
 754                 if ((left_father_in_tree != NULL) || (right_father_in_tree != NULL)) {
 755                         MonoSsapreFatherExpression *current_inst_as_father = (MonoSsapreFatherExpression*) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreFatherExpression));
 756                         current_inst_as_father->father_occurrence = inst;
 757                         current_inst_as_father->grand_father = NULL;
 758                         *father_in_tree = &(current_inst_as_father->grand_father);
 759                         if (left_father_in_tree != NULL) {
 760                                 *left_father_in_tree = current_inst_as_father;
 761                         }
 762                         if (right_father_in_tree != NULL) {
 763                                 *right_father_in_tree = current_inst_as_father;
 764                         }
 765                         if (DUMP_SSAPRE) {
 766                                 printf ("Expression '");
 767                                 mono_print_tree (inst);
 768                                 printf ("' is a potential father ( ");
 769                                 if (left_father_in_tree != NULL) {
 770                                         printf ("LEFT ");
 771                                 }
 772                                 if (right_father_in_tree != NULL) {
 773                                         printf ("RIGHT ");
 774                                 }
 775                                 printf (")\n");
 776                         }
 777                 } else if ((area->current_occurrence->description.left_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY) &&
 778                                 (area->current_occurrence->description.right_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY)) {
 779                         area->current_occurrence->occurrence = inst;
 780                         area->current_occurrence->previous_tree = previous_inst;
 781                         area->current_occurrence->bb_info = bb_info;
 782                         area->current_occurrence->is_first_in_bb = FALSE;
 783                         area->current_occurrence->is_last_in_bb = FALSE;
 784
 785                         area->current_occurrence->father_in_tree = NULL;
 786                         *father_in_tree = &(area->current_occurrence->father_in_tree);
 787
 788                         add_occurrence_to_worklist (area);
 789                 } else {
 790                         *father_in_tree = NULL;
 791                 }
 792         } else {
 793                 *father_in_tree = NULL;
 794         }
 795 }
 796
 797 /*
 798  * Process a BB, and (recursively) all its children in the dominator tree.
 799  * The result is that all the expressions end up in the worklist, and the
 800  * auxiliary MonoSsapreBBInfo fields (dt_dfn, dt_descendants) are initialized
 801  * (with all the info that comes from the MonoBasicBlock).
 802  */
 803 static void
 804 process_bb (MonoSsapreWorkArea *area, MonoBasicBlock *bb, int *dt_dfn, int *upper_descendants, int current_depth) {
 805         MonoSsapreBBInfo *bb_info;
 806         int descendants;
 807         GList *dominated_bb;
 808         MonoInst* current_inst;
 809         MonoInst* previous_inst;
 810         MonoSsapreFatherExpression** dummy_father_in_tree;
 811
 812         bb_info = &(area->bb_infos [*dt_dfn]);
 813         bb_info->dt_dfn = *dt_dfn;
 814         (*dt_dfn)++;
 815         bb_info->cfg_dfn = bb->dfn;
 816         area->bb_infos_in_cfg_dfn_order [bb->dfn] = bb_info;
 817         bb_info->in_count = bb->in_count;
 818         bb_info->out_count = bb->out_count;
 819         bb_info->dfrontier = bb->dfrontier;
 820         bb_info->bb = bb;
 821         bb_info->in_bb = (MonoSsapreBBInfo**) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreBBInfo*) * (bb->in_count));
 822         bb_info->out_bb = (MonoSsapreBBInfo**) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreBBInfo*) * (bb->out_count));
 823         bb_info->phi_arguments_classes = (int*) mono_mempool_alloc (area->mempool, sizeof (int) * (bb->in_count));
 824
 825         bb_info->phi_insertion_point = NULL;
 826
 827         current_inst = bb->code;
 828         previous_inst = NULL;
 829         while (current_inst != NULL) {
 830                 /* Ugly hack to fix missing variable definitions */
 831                 /* (the SSA construction code should have done it already!) */
 832                 switch (current_inst->opcode) {
 833                 case CEE_STIND_REF:
 834                 case CEE_STIND_I:
 835                 case CEE_STIND_I4:
 836                 case CEE_STIND_I1:
 837                 case CEE_STIND_I2:
 838                 case CEE_STIND_I8:
 839                 case CEE_STIND_R4:
 840                 case CEE_STIND_R8:
 841                         if ((current_inst->inst_left->opcode == OP_LOCAL) || (current_inst->inst_left->opcode == OP_ARG)) {
 842                                 int variable_index = current_inst->inst_left->inst_c0;
 843
 844                                 if (area->cfg->vars [variable_index]->def_bb == NULL) {
 845                                         if (area->cfg->verbose_level >= 4) {
 846                                                 printf ("SSAPRE WARNING: variable %d has no definition, fixing.\n", variable_index);
 847                                         }
 848                                         area->cfg->vars [variable_index]->def_bb = bb_info->bb;
 849                                 }
 850                         }
 851                         break;
 852                 default:
 853                         break;
 854                 }
 855
 856                 if (is_phi_definition (current_inst)) {
 857                         bb_info->phi_insertion_point = current_inst;
 858                 }
 859
 860                 if (mono_burg_arity [current_inst->opcode] > 0) {
 861                         process_inst (area, current_inst->inst_left, previous_inst, &dummy_father_in_tree, bb_info);
 862                         if (mono_burg_arity [current_inst->opcode] > 1) {
 863                                 process_inst (area, current_inst->inst_right, previous_inst, &dummy_father_in_tree, bb_info);
 864                         }
 865                 }
 866
 867                 previous_inst = current_inst;
 868                 current_inst = current_inst->next;
 869         }
 870
 871         if (current_depth > area->dt_depth) {
 872                 area->dt_depth = current_depth;
 873         }
 874         descendants = 0;
 875         for (dominated_bb = g_list_first (bb->dominated); dominated_bb != NULL; dominated_bb = g_list_next (dominated_bb)) {
 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 = area->cfg->vars [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                         area->cfg->vars [new_var->inst_c0]->reg = original_variable_index;
1847                         area->cfg->vars [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                                 area->cfg->vars [new_var->inst_c0]->reg = original_variable_index;
1863                                 area->cfg->vars [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                         area->cfg->vars [new_var->inst_c0]->reg = original_variable_index;
1876                         area->cfg->vars [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 = area->cfg->vars [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                         area->cfg->vars [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                                 area->cfg->vars [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                         area->cfg->vars [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                 printf ("BEFORE SSAPRE START\n");
2107                 mono_print_code (area.cfg);
2108                 printf ("BEFORE SSAPRE END\n");
2109         }
2110
2111         area.first_in_queue = NULL;
2112         area.last_in_queue = NULL;
2113         area.current_occurrence = (MonoSsapreExpressionOccurrence*) mono_mempool_alloc (area.mempool, sizeof (MonoSsapreExpressionOccurrence));
2114         dt_dfn = 0;
2115         descendants = 0;
2116         area.dt_depth = 0;
2117         process_bb (&area, cfg->bblocks [0], &dt_dfn, &descendants, 1);
2118         for (block = 0; block < area.num_bblocks; block++) {
2119                 MonoSsapreBBInfo *bb_info = &(area.bb_infos [block]);
2120                 MonoBasicBlock *bb = bb_info->bb;
2121                 if (bb->idom != NULL) {
2122                         bb_info->idominator = area.bb_infos_in_cfg_dfn_order [bb->idom->dfn];
2123                 } else {
2124                         bb_info->idominator = NULL;
2125                 }
2126                 for (i = 0; i < bb->in_count; i++) {
2127                         bb_info->in_bb [i] = area.bb_infos_in_cfg_dfn_order [bb->in_bb [i]->dfn];
2128                 }
2129                 for (i = 0; i < bb->out_count; i++) {
2130                         bb_info->out_bb [i] = area.bb_infos_in_cfg_dfn_order [bb->out_bb [i]->dfn];
2131                 }
2132         }
2133
2134         if (area.cfg->verbose_level >= TRACE_LEVEL) {
2135                 printf ("SSAPRE START WORKLIST\n");
2136                 print_worklist (area.worklist);
2137                 printf ("SSAPRE END WORKLIST\n");
2138         }
2139
2140 #if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
2141         area.expression_is_handled_father = TRUE;
2142 #endif
2143         for (area.current_expression = area.first_in_queue; area.current_expression != NULL; area.current_expression = area.current_expression->next_in_queue) {
2144                 process_expression (&area);
2145         }
2146
2147         if (area.cfg->verbose_level >= DUMP_LEVEL) {
2148                 printf ("AFTER SSAPRE START\n");
2149                 mono_print_code (area.cfg);
2150                 printf ("AFTER SSAPRE END\n");
2151         }
2152         if (area.cfg->verbose_level >= TRACE_LEVEL) {
2153                 printf ("SSAPRE ENDS PROCESSING METHOD %s\n", mono_method_full_name (cfg->method, TRUE));
2154         }
2155
2156         mono_mempool_destroy (area.mempool);
2157 }