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 extern guint8 mono_burg_arity [];
  22
  23 /* Logging conditions */
  24 #define DUMP_LEVEL (4)
  25 #define TRACE_LEVEL (3)
  26 #define STATISTICS_LEVEL (2)
  27 #define LOG_LEVEL (1)
  28 #define DUMP_SSAPRE (area->cfg->verbose_level >= DUMP_LEVEL)
  29 #define TRACE_SSAPRE (area->cfg->verbose_level >= TRACE_LEVEL)
  30 #define STATISTICS_SSAPRE (area->cfg->verbose_level >= STATISTICS_LEVEL)
  31 #define LOG_SSAPRE (area->cfg->verbose_level >= LOG_LEVEL)
  32
  33 /* "Bottom" symbol definition (see paper) */
  34 #define BOTTOM_REDUNDANCY_CLASS (-1)
  35
  36 /* Various printing functions... */
  37 static void
  38 print_argument (MonoSsapreExpressionArgument *argument) {
  39         switch (argument->type) {
  40                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY:
  41                         printf ("ANY");
  42                         break;
  43                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_NOT_PRESENT:
  44                         printf ("NONE");
  45                         break;
  46                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE:
  47                         printf ("ORIGINAL_VARIABLE %d", argument->argument.original_variable);
  48                         break;
  49                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE:
  50                         printf ("SSA_VARIABLE %d", argument->argument.ssa_variable);
  51                         break;
  52                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT:
  53                         printf ("INTEGER_CONSTANT %d", argument->argument.integer_constant);
  54                         break;
  55                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_LONG_COSTANT:
  56                         printf ("LONG_COSTANT %lld", (long long)*(argument->argument.long_constant));
  57                         break;
  58                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT:
  59                         printf ("FLOAT_COSTANT %f", *(argument->argument.float_constant));
  60                         break;
  61                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT:
  62                         printf ("DOUBLE_COSTANT %f", *(argument->argument.double_constant));
  63                         break;
  64                 default:
  65                         printf ("UNKNOWN: %d", argument->type);
  66         }
  67 }
  68
  69
  70 static void
  71 print_expression_description (MonoSsapreExpressionDescription *expression_description) {
  72         if (expression_description->opcode != 0) {
  73                 printf ("%s ([", mono_inst_name (expression_description->opcode) );
  74                 print_argument (&(expression_description->left_argument));
  75                 printf ("],[");
  76                 print_argument (&(expression_description->right_argument));
  77                 printf ("])");
  78         } else {
  79                 printf ("ANY");
  80         }
  81 }
  82
  83 #if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
  84 static void
  85 snprint_argument (GString *string, MonoSsapreExpressionArgument *argument) {
  86         switch (argument->type) {
  87                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY:
  88                         g_string_append_printf (string, "ANY");
  89                         break;
  90                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_NOT_PRESENT:
  91                         g_string_append_printf (string, "NONE");
  92                         break;
  93                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE:
  94                         g_string_append_printf (string, "ORIGINAL_VARIABLE %d", argument->argument.original_variable);
  95                         break;
  96                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE:
  97                         g_string_append_printf (string, "SSA_VARIABLE %d", argument->argument.ssa_variable);
  98                         break;
  99                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT:
 100                         g_string_append_printf (string, "INTEGER_CONSTANT %d", argument->argument.integer_constant);
 101                         break;
 102                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_LONG_COSTANT:
 103                         g_string_append_printf (string, "LONG_COSTANT %lld", *(argument->argument.long_constant));
 104                         break;
 105                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT:
 106                         g_string_append_printf (string, "FLOAT_COSTANT %f", *(argument->argument.float_constant));
 107                         break;
 108                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT:
 109                         g_string_append_printf (string, "DOUBLE_COSTANT %f", *(argument->argument.double_constant));
 110                         break;
 111                 default:
 112                         g_string_append_printf (string, "UNKNOWN: %d", argument->type);
 113         }
 114 }
 115
 116 static void
 117 snprint_expression_description (GString *string, MonoSsapreExpressionDescription *expression_description) {
 118         if (expression_description->opcode != 0) {
 119                 g_string_append_printf (string, "%s ([", mono_inst_name (expression_description->opcode) );
 120                 snprint_argument (string, &(expression_description->left_argument));
 121                 g_string_append_printf (string, "],[");
 122                 snprint_argument (string, &(expression_description->right_argument));
 123                 g_string_append_printf (string, "])");
 124         } else {
 125                 g_string_append_printf (string, "ANY");
 126         }
 127 }
 128 #endif
 129
 130 #define GBOOLEAN_TO_STRING(b) ((b)?"TRUE":"FALSE")
 131
 132 static void
 133 print_expression_occurrence (MonoSsapreExpressionOccurrence *occurrence, int number) {
 134         printf (" ([%d][bb %d [ID %d]][class %d]: ", number, occurrence->bb_info->cfg_dfn, occurrence->bb_info->bb->block_num, occurrence->redundancy_class);
 135         print_expression_description (&(occurrence->description));
 136         if (occurrence->is_first_in_bb) {
 137                 printf (" [FIRST in BB]");
 138         }
 139         if (occurrence->is_last_in_bb) {
 140                 printf (" [LAST in BB]");
 141         }
 142         printf (" (save = %s)", GBOOLEAN_TO_STRING (occurrence->save));
 143         printf (" (reload = %s)", GBOOLEAN_TO_STRING (occurrence->reload));
 144         printf ("\n");
 145         occurrence = occurrence->next;
 146 }
 147
 148 static void
 149 print_expression_occurrences (MonoSsapreExpressionOccurrence *occurrences) {
 150         int i = 0;
 151         while (occurrences != NULL) {
 152                 i++;
 153                 print_expression_occurrence (occurrences, i);
 154                 occurrences = occurrences->next;
 155         }
 156 }
 157
 158 static void
 159 print_worklist (MonoSsapreExpression *expression) {
 160         if (expression != NULL) {
 161                 print_worklist (expression->previous);
 162
 163                 printf ("{%d}: ", expression->tree_size);
 164                 print_expression_description (&(expression->description));
 165                 printf ("\n");
 166                 print_expression_occurrences (expression->occurrences);
 167
 168                 print_worklist (expression->next);
 169         }
 170 }
 171
 172 static void
 173 print_bb_info (MonoSsapreBBInfo *bb_info, gboolean print_occurrences) {
 174         int i;
 175         MonoSsapreExpressionOccurrence *current_occurrence = bb_info->first_expression_in_bb;
 176
 177         printf ("bb %d [ID %d]: IN { ", bb_info->cfg_dfn, bb_info->bb->block_num);
 178         for (i = 0; i < bb_info->in_count; i++) {
 179                 printf ("%d [ID %d] ", bb_info->in_bb [i]->cfg_dfn, bb_info->in_bb [i]->bb->block_num);
 180         }
 181         printf ("}, OUT {");
 182         for (i = 0; i < bb_info->out_count; i++) {
 183                 printf ("%d [ID %d] ", bb_info->out_bb [i]->cfg_dfn, bb_info->out_bb [i]->bb->block_num);
 184         }
 185         printf ("}");
 186         if (bb_info->next_interesting_bb != NULL) {
 187                 printf (", NEXT %d [ID %d]", bb_info->next_interesting_bb->cfg_dfn, bb_info->next_interesting_bb->bb->block_num);
 188         }
 189         if (bb_info->dt_covered_by_interesting_BBs) {
 190                 printf (" (COVERED)");
 191         } else {
 192                 printf (" (NEVER DOWN SAFE)");
 193         }
 194         printf ("\n");
 195         if (bb_info->has_phi) {
 196                 printf (" PHI, class %d [ ", bb_info->phi_redundancy_class);
 197                 for (i = 0; i < bb_info->in_count; i++) {
 198                         int argument_class = bb_info->phi_arguments_classes [i];
 199                         if (argument_class != BOTTOM_REDUNDANCY_CLASS) {
 200                                 printf ("%d ", argument_class);
 201                         } else {
 202                                 printf ("BOTTOM ");
 203                         }
 204                 }
 205                 printf ("]\n(phi_defines_a_real_occurrence:%s) (phi_is_down_safe:%s) (phi_can_be_available:%s) (phi_is_later:%s)\n",
 206                                 GBOOLEAN_TO_STRING (bb_info->phi_defines_a_real_occurrence), GBOOLEAN_TO_STRING (bb_info->phi_is_down_safe),
 207                                 GBOOLEAN_TO_STRING (bb_info->phi_can_be_available), GBOOLEAN_TO_STRING (bb_info->phi_is_later));
 208         }
 209         if (print_occurrences) {
 210                 i = 0;
 211                 while ((current_occurrence != NULL) && (current_occurrence->bb_info == bb_info)) {
 212                         print_expression_occurrence (current_occurrence, i);
 213                         current_occurrence = current_occurrence->next;
 214                         i++;
 215                 }
 216         }
 217         if (bb_info->has_phi_argument) {
 218                 printf (" PHI ARGUMENT, class ");
 219                 if (bb_info->phi_argument_class != BOTTOM_REDUNDANCY_CLASS) {
 220                         printf ("%d ", bb_info->phi_argument_class);
 221                 } else {
 222                         printf ("BOTTOM ");
 223                 }
 224                 if (bb_info->phi_argument_defined_by_real_occurrence != NULL) {
 225                         printf ("(Defined by real occurrence %d)", bb_info->phi_argument_defined_by_real_occurrence->redundancy_class);
 226                 } else if (bb_info->phi_argument_defined_by_phi != NULL) {
 227                         printf ("(Defined by phi %d)", bb_info->phi_argument_defined_by_phi->phi_redundancy_class);
 228                 } else {
 229                         printf ("(Undefined)");
 230                 }
 231                 printf (" (real occurrence arguments: left ");
 232                 if (bb_info->phi_argument_left_argument_version != BOTTOM_REDUNDANCY_CLASS) {
 233                         printf ("%d ", bb_info->phi_argument_left_argument_version);
 234                 } else {
 235                         printf ("NONE ");
 236                 }
 237                 printf (", right ");
 238                 if (bb_info->phi_argument_right_argument_version != BOTTOM_REDUNDANCY_CLASS) {
 239                         printf ("%d ", bb_info->phi_argument_right_argument_version);
 240                 } else {
 241                         printf ("NONE ");
 242                 }
 243                 printf (")\n(phi_argument_has_real_use:%s) (phi_argument_needs_insert:%s) (phi_argument_has_been_processed:%s)\n",
 244                                 GBOOLEAN_TO_STRING (bb_info->phi_argument_has_real_use), GBOOLEAN_TO_STRING (bb_info->phi_argument_needs_insert),
 245                                 GBOOLEAN_TO_STRING (bb_info->phi_argument_has_been_processed));
 246         }
 247 }
 248
 249 static void
 250 print_bb_infos (MonoSsapreWorkArea *area) {
 251         int i;
 252         for (i = 0; i < area->num_bblocks; i++) {
 253                 MonoSsapreBBInfo *bb_info = &(area->bb_infos [i]);
 254                 print_bb_info (bb_info, TRUE);
 255         }
 256 }
 257
 258 static void
 259 print_interesting_bb_infos (MonoSsapreWorkArea *area) {
 260         MonoSsapreBBInfo *current_bb;
 261
 262         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
 263                 print_bb_info (current_bb, FALSE);
 264         }
 265 }
 266
 267 static void dump_code (MonoSsapreWorkArea *area) {
 268         int i;
 269
 270         for (i = 0; i < area->num_bblocks; i++) {
 271                 MonoSsapreBBInfo *current_bb = &(area->bb_infos [i]);
 272                 MonoInst *current_inst;
 273
 274                 print_bb_info (current_bb, TRUE);
 275                 for (current_inst = current_bb->bb->code; current_inst != NULL; current_inst = current_inst->next) {
 276                         mono_print_tree_nl (current_inst);
 277                 }
 278         }
 279 }
 280
 281 /*
 282  * Given a MonoInst, it tries to describe it as an expression argument.
 283  * If this is not possible, the result will be of type
 284  * MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY.
 285  */
 286 static void
 287 analyze_argument (MonoInst *argument, MonoSsapreExpressionArgument *result) {
 288         switch (argument->opcode) {
 289         case CEE_LDIND_I1:
 290         case CEE_LDIND_U1:
 291         case CEE_LDIND_I2:
 292         case CEE_LDIND_U2:
 293         case CEE_LDIND_I4:
 294         case CEE_LDIND_U4:
 295         case CEE_LDIND_I8:
 296         case CEE_LDIND_I:
 297         case CEE_LDIND_R4:
 298         case CEE_LDIND_R8:
 299         case CEE_LDIND_REF:
 300                 if ((argument->inst_left->opcode == OP_LOCAL) || (argument->inst_left->opcode == OP_ARG)) {
 301                         result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE;
 302                         result->argument.ssa_variable = argument->inst_left->inst_c0;
 303                 } else {
 304                         result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 305                 }
 306                 break;
 307         case OP_ICONST:
 308                 result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT;
 309                 result->argument.integer_constant = argument->inst_c0;
 310                 break;
 311         case OP_I8CONST:
 312                 result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_LONG_COSTANT;
 313                 result->argument.long_constant = &(argument->inst_l);
 314                 break;
 315         case OP_R4CONST:
 316                 if (! isnan (*((float*)argument->inst_p0))) {
 317                         result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT;
 318                         result->argument.float_constant = (float*)argument->inst_p0;
 319                 } else {
 320                         result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 321                 }
 322                 break;
 323         case OP_R8CONST:
 324                 if (! isnan (*((double*)argument->inst_p0))) {
 325                         result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT;
 326                         result->argument.double_constant = (double*)argument->inst_p0;
 327                 } else {
 328                         result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 329                 }
 330                 break;
 331         default:
 332                 result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
 333         }
 334 }
 335
 336
 337 /*
 338  * Given a MonoInst, it tries to describe it as an expression.
 339  * If this is not possible, the result will have opcode 0.
 340  */
 341 static void
 342 analyze_expression (MonoInst *expression, MonoSsapreExpressionDescription *result) {
 343         switch (expression->opcode) {
 344 #define OPDEF(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10) case a1:
 345 #include "ssapre-cee-ops.h"
 346 #undef OPDEF
 347 #define MINI_OP(a1,a2) case a1:
 348 #include "ssapre-mini-ops.h"
 349 #undef MINI_OP
 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                                         /*
1267                                          * Major difference from the paper here...
1268                                          * Instead of maintaining "set_for_rename2" (see figure 20), we just
1269                                          * compute "phi_argument_left_argument_version" (and right) here, and
1270                                          * use that in rename2, saving us the hassle of maintaining a set
1271                                          * data structure (and the related allocations).
1272                                          */
1273                                         for (phi_argument = 0; phi_argument < phi_bb->in_count; phi_argument++) {
1274                                                 MonoSsapreBBInfo *previous_bb = phi_bb->in_bb [phi_argument];
1275                                                 if (left_argument_version != BOTTOM_REDUNDANCY_CLASS) {
1276                                                         previous_bb->phi_argument_left_argument_version = get_variable_version_at_predecessor_bb (area,
1277                                                                         left_argument_version, phi_bb, phi_argument);
1278                                                 }
1279                                                 if (right_argument_version != BOTTOM_REDUNDANCY_CLASS) {
1280                                                         previous_bb->phi_argument_right_argument_version = get_variable_version_at_predecessor_bb (area,
1281                                                                         right_argument_version, phi_bb, phi_argument);
1282                                                 }
1283                                         }
1284                                         if (DUMP_SSAPRE) {
1285                                                 printf ("Using class %d for occurrence '", current_expression->redundancy_class);
1286                                                 print_expression_description (&(current_expression->description));
1287                                                 printf ("' in bb %d [ID %d] (Real use flag is now TRUE)\n", current_bb->cfg_dfn, current_bb->bb->block_num);
1288                                         }
1289                                 } else {
1290                                         current_expression->redundancy_class = current_class;
1291                                         current_class++;
1292                                         current_expression->defined_by_phi = NULL;
1293                                         PUSH_REAL_OCCURRENCE (current_expression);
1294                                         phi_bb->phi_is_down_safe = FALSE;
1295                                         if (TRACE_SSAPRE) {
1296                                                 printf ("Assigning class %d to occurrence '", current_expression->redundancy_class);
1297                                                 print_expression_description (&(current_expression->description));
1298                                                 printf ("' in bb %d [ID %d]\n", current_bb->cfg_dfn, current_bb->bb->block_num);
1299                                                 printf ("Clearing down safe in PHI %d because of real occurrence %d\n",
1300                                                                 phi_bb->phi_redundancy_class, current_expression->redundancy_class);
1301                                         }
1302                                 }
1303                                 current_expression->defined_by_real_occurrence = NULL;
1304                         } else {
1305                                 current_expression->redundancy_class = current_class;
1306                                 current_class++;
1307                                 current_expression->defined_by_real_occurrence = NULL;
1308                                 current_expression->defined_by_phi = NULL;
1309                                 PUSH_REAL_OCCURRENCE (current_expression);
1310                                 if (TRACE_SSAPRE) {
1311                                         printf ("Assigning class %d to occurrence '", current_expression->redundancy_class);
1312                                         print_expression_description (&(current_expression->description));
1313                                         printf ("' in bb %d [ID %d]\n", current_bb->cfg_dfn, current_bb->bb->block_num);
1314                                 }
1315                         }
1316                 }
1317
1318                 if (current_bb->has_phi_argument) {
1319                         if (area->top_of_renaming_stack != NULL) {
1320                                 current_bb->phi_argument_defined_by_real_occurrence = area->top_of_renaming_stack;
1321                                 current_bb->phi_argument_class = area->top_of_renaming_stack->redundancy_class;
1322                         } else if (area->bb_on_top_of_renaming_stack != NULL) {
1323                                 current_bb->phi_argument_defined_by_phi = area->bb_on_top_of_renaming_stack;
1324                                 current_bb->phi_argument_class = area->bb_on_top_of_renaming_stack->phi_redundancy_class;
1325                         } else {
1326                                 current_bb->phi_argument_class = BOTTOM_REDUNDANCY_CLASS;
1327                         }
1328                         if ((DUMP_SSAPRE) && (current_bb->phi_argument_class != BOTTOM_REDUNDANCY_CLASS)) {
1329                                 printf ("Temporarily using class %d for PHI argument in bb %d [ID %d]\n",
1330                                                 current_bb->phi_argument_class, current_bb->cfg_dfn, current_bb->bb->block_num);
1331                         }
1332                 }
1333         }
1334         if ((area->bb_on_top_of_renaming_stack != NULL) && (area->top_of_renaming_stack == NULL) && (previous_bb->phi_argument_has_real_use == FALSE)) {
1335                 if (TRACE_SSAPRE) {
1336                         printf ("Clearing down safe in PHI %d because of backtracking (previous block is [bb %d [ID %d]])\n",
1337                                         area->bb_on_top_of_renaming_stack->phi_redundancy_class, previous_bb->cfg_dfn, previous_bb->bb->block_num);
1338                 }
1339                 area->bb_on_top_of_renaming_stack->phi_is_down_safe = FALSE;
1340         }
1341         area->number_of_classes = current_class;
1342
1343         /* This loop is "rename2" */
1344         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1345                 if (current_bb->has_phi_argument) {
1346                         if ((current_bb->phi_argument_left_argument_version != BOTTOM_REDUNDANCY_CLASS) || (current_bb->phi_argument_right_argument_version != BOTTOM_REDUNDANCY_CLASS)) {
1347                                 if (current_bb->phi_argument_defined_by_real_occurrence != NULL) {
1348                                         if (((current_bb->phi_argument_left_argument_version != BOTTOM_REDUNDANCY_CLASS) &&
1349                                                         (current_bb->phi_argument_left_argument_version != current_bb->phi_argument_defined_by_real_occurrence->description.left_argument.argument.ssa_variable)) ||
1350                                                         ((current_bb->phi_argument_right_argument_version != BOTTOM_REDUNDANCY_CLASS) &&
1351                                                         (current_bb->phi_argument_right_argument_version != current_bb->phi_argument_defined_by_real_occurrence->description.right_argument.argument.ssa_variable))) {
1352                                                 current_bb->phi_argument_class = BOTTOM_REDUNDANCY_CLASS;
1353                                         }
1354                                 } else if (current_bb->phi_argument_defined_by_phi != NULL) {
1355                                         MonoSsapreBBInfo *phi_bb = current_bb->phi_argument_defined_by_phi;
1356                                         MonoSsapreBBInfo *left_argument_definition_bb = (current_bb->phi_argument_left_argument_version != BOTTOM_REDUNDANCY_CLASS) ?
1357                                                         get_bb_info_of_definition (area, current_bb->phi_argument_left_argument_version) : NULL;
1358                                         MonoSsapreBBInfo *right_argument_definition_bb = (current_bb->phi_argument_right_argument_version != BOTTOM_REDUNDANCY_CLASS) ?
1359                                                         get_bb_info_of_definition (area, current_bb->phi_argument_right_argument_version) : NULL;
1360                                         /* See remark in section 5.4 about the dominance relation between PHI */
1361                                         /* occurrences and phi definitions */
1362                                         gboolean left_bottom_condition = ((left_argument_definition_bb != NULL) && ! ((left_argument_definition_bb != phi_bb) ? dominates (left_argument_definition_bb, phi_bb) :
1363                                                         (IS_PHI_DEFINITION (current_bb->phi_argument_left_argument_version) ? TRUE : FALSE)));
1364                                         gboolean right_bottom_condition = ((right_argument_definition_bb != NULL) && ! ((right_argument_definition_bb != phi_bb) ? dominates (right_argument_definition_bb, phi_bb) :
1365                                                         (IS_PHI_DEFINITION (current_bb->phi_argument_right_argument_version) ? TRUE : FALSE)));
1366
1367                                         if (left_bottom_condition || right_bottom_condition) {
1368                                                 current_bb->phi_argument_class = BOTTOM_REDUNDANCY_CLASS;
1369                                         }
1370                                 } else {
1371                                         current_bb->phi_argument_class = BOTTOM_REDUNDANCY_CLASS;
1372                                 }
1373                         } else {
1374                                 current_bb->phi_argument_class = BOTTOM_REDUNDANCY_CLASS;
1375                         }
1376
1377                         if (current_bb->phi_argument_class == BOTTOM_REDUNDANCY_CLASS) {
1378                                 if ((current_bb->phi_argument_defined_by_phi != NULL) && (! current_bb->phi_argument_has_real_use)) {
1379                                         if (TRACE_SSAPRE) {
1380                                                 printf ("Clearing down safe in PHI %d because PHI argument in block [bb %d [ID %d]] is BOTTOM\n",
1381                                                                 current_bb->phi_argument_defined_by_phi->phi_redundancy_class, current_bb->cfg_dfn, current_bb->bb->block_num);
1382                                         }
1383                                         current_bb->phi_argument_defined_by_phi->phi_is_down_safe = FALSE;
1384                                 }
1385                                 current_bb->phi_argument_has_real_use = FALSE;
1386
1387                                 if (DUMP_SSAPRE) {
1388                                         printf ("Cleared real use flag in block [bb %d [ID %d]] because phi argument class is now BOTTOM\n",
1389                                                         current_bb->cfg_dfn, current_bb->bb->block_num);
1390                                 }
1391                         }
1392                 }
1393         }
1394
1395         /* Final quick pass to copy the result of "rename2" into PHI nodes */
1396         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1397                 if (current_bb->has_phi) {
1398                         int i;
1399                         for (i = 0; i < current_bb->in_count; i++) {
1400                                 current_bb->phi_arguments_classes [i] = current_bb->in_bb [i]->phi_argument_class;
1401                         }
1402                 }
1403         }
1404 }
1405
1406 #undef PUSH_REAL_OCCURRENCE
1407 #undef PUSH_PHI_OCCURRENCE
1408
1409 /*
1410  * See paper, figure 8
1411  */
1412 static void
1413 reset_down_safe (MonoSsapreBBInfo *phi_argument) {
1414         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)) {
1415                 int i;
1416                 MonoSsapreBBInfo *phi = phi_argument->phi_argument_defined_by_phi;
1417                 phi->phi_is_down_safe = FALSE;
1418                 for (i = 0; i < phi->in_count; i++) {
1419                         reset_down_safe (phi->in_bb [i]);
1420                 }
1421         }
1422 }
1423
1424 /*
1425  * See paper, figure 8
1426  */
1427 static void
1428 down_safety (MonoSsapreWorkArea *area) {
1429         MonoSsapreBBInfo *current_bb = NULL;
1430
1431         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1432                 if (current_bb->has_phi) {
1433                         if (! current_bb->phi_is_down_safe) {
1434                                 int i;
1435                                 for (i = 0; i < current_bb->in_count; i++) {
1436                                         reset_down_safe (current_bb->in_bb [i]);
1437                                 }
1438                         }
1439                 }
1440         }
1441 }
1442
1443 /*
1444  * See paper, figure 10
1445  */
1446 static void
1447 reset_can_be_available (MonoSsapreWorkArea *area, MonoSsapreBBInfo *phi) {
1448         MonoSsapreBBInfo *current_bb = NULL;
1449
1450         if (DUMP_SSAPRE) {
1451                 printf ("Resetting availability for PHI %d in block [bb %d [ID %d]]\n",
1452                                 phi->phi_redundancy_class, phi->cfg_dfn, phi->bb->block_num);
1453         }
1454
1455         phi->phi_can_be_available = FALSE;
1456         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1457                 if (current_bb->has_phi) {
1458                         gboolean phi_is_interesting = FALSE;
1459                         int i;
1460
1461                         for (i = 0; i < current_bb->in_count; i++) {
1462                                 MonoSsapreBBInfo *phi_argument = current_bb->in_bb [i];
1463                                 if ((phi_argument->phi_argument_class == current_bb->phi_redundancy_class) && (! phi_argument->phi_argument_has_real_use)) {
1464                                         phi_is_interesting = TRUE;
1465                                         break;
1466                                 }
1467                         }
1468
1469                         if (phi_is_interesting && (! current_bb->phi_is_down_safe) && (current_bb->phi_can_be_available)) {
1470                                 reset_can_be_available (area, current_bb);
1471                         }
1472                 }
1473         }
1474 }
1475
1476 /*
1477  * See paper, figure 10
1478  */
1479 static void
1480 compute_can_be_available (MonoSsapreWorkArea *area) {
1481         MonoSsapreBBInfo *current_bb = NULL;
1482
1483         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1484                 if (current_bb->has_phi) {
1485                         if ((! current_bb->phi_is_down_safe) && (current_bb->phi_can_be_available)) {
1486                                 gboolean phi_is_interesting = FALSE;
1487                                 int i;
1488
1489                                 for (i = 0; i < current_bb->in_count; i++) {
1490                                         if (current_bb->phi_arguments_classes [i] == BOTTOM_REDUNDANCY_CLASS) {
1491                                                 phi_is_interesting = TRUE;
1492                                                 break;
1493                                         }
1494                                 }
1495
1496                                 if (phi_is_interesting) {
1497                                         if (DUMP_SSAPRE) {
1498                                                 printf ("Availability computation working on PHI %d in block [bb %d [ID %d]]\n",
1499                                                                 current_bb->phi_redundancy_class, current_bb->cfg_dfn, current_bb->bb->block_num);
1500                                         }
1501                                         reset_can_be_available (area, current_bb);
1502                                 }
1503                         }
1504                 }
1505         }
1506 }
1507
1508 /*
1509  * See paper, figure 10
1510  */
1511 static void
1512 reset_later (MonoSsapreWorkArea *area, MonoSsapreBBInfo *phi) {
1513         MonoSsapreBBInfo *current_bb = NULL;
1514
1515         if (phi->phi_is_later) {
1516                 phi->phi_is_later = FALSE;
1517                 for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1518                         if (current_bb->has_phi) {
1519                                 gboolean phi_is_interesting = FALSE;
1520                                 int i;
1521
1522                                 for (i = 0; i < current_bb->in_count; i++) {
1523                                         MonoSsapreBBInfo *phi_argument = current_bb->in_bb [i];
1524                                         if (phi_argument->phi_argument_class == current_bb->phi_redundancy_class) {
1525                                                 phi_is_interesting = TRUE;
1526                                                 break;
1527                                         }
1528                                 }
1529
1530                                 if (phi_is_interesting) {
1531                                         reset_later (area, current_bb);
1532                                 }
1533                         }
1534                 }
1535         }
1536 }
1537
1538 /*
1539  * See paper, figure 10
1540  */
1541 static void
1542 compute_later (MonoSsapreWorkArea *area) {
1543         MonoSsapreBBInfo *current_bb = NULL;
1544
1545         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1546                 if (current_bb->has_phi) {
1547                         current_bb->phi_is_later = current_bb->phi_can_be_available;
1548                 }
1549         }
1550         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1551                 if (current_bb->has_phi) {
1552                         if (current_bb->phi_is_later) {
1553                                 gboolean phi_is_interesting = FALSE;
1554                                 int i;
1555
1556                                 for (i = 0; i < current_bb->in_count; i++) {
1557                                         MonoSsapreBBInfo *phi_argument = current_bb->in_bb [i];
1558                                         if ((phi_argument->phi_argument_class != BOTTOM_REDUNDANCY_CLASS) && (phi_argument->phi_argument_has_real_use)) {
1559                                                 phi_is_interesting = TRUE;
1560                                                 break;
1561                                         }
1562                                 }
1563
1564                                 if (phi_is_interesting) {
1565                                         reset_later (area, current_bb);
1566                                 }
1567                         }
1568                 }
1569         }
1570 }
1571
1572 /*
1573  * See paper, figure 12, function Finalize_1
1574  */
1575 static void finalize_availability_and_reload (MonoSsapreWorkArea *area, MonoSsapreAvailabilityTableElement *availability_table) {
1576         MonoSsapreBBInfo *current_bb = NULL;
1577         MonoSsapreExpressionOccurrence *current_expression = NULL;
1578
1579         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1580                 if (current_bb->has_phi) {
1581                         if (current_bb->phi_can_be_available && ! current_bb->phi_is_later) {
1582                                 availability_table [current_bb->phi_redundancy_class].class_defined_by_phi = current_bb;
1583                         }
1584                 }
1585
1586                 for (current_expression = current_bb->first_expression_in_bb; (current_expression != NULL) && (current_expression->bb_info == current_bb); current_expression = current_expression->next) {
1587                         MonoSsapreBBInfo *defining_bb = availability_table [current_expression->redundancy_class].class_defined_by_phi;
1588                         if (defining_bb == NULL && availability_table [current_expression->redundancy_class].class_defined_by_real_occurrence != NULL) {
1589                                 defining_bb = availability_table [current_expression->redundancy_class].class_defined_by_real_occurrence->bb_info;
1590                         }
1591                         if (defining_bb != NULL) {
1592                                 if (! dominates (defining_bb, current_bb)) {
1593                                         defining_bb = NULL;
1594                                 }
1595                         }
1596
1597                         if (defining_bb == NULL) {
1598                                 current_expression->reload = FALSE;
1599                                 availability_table [current_expression->redundancy_class].class_defined_by_real_occurrence = current_expression;
1600                         } else {
1601                                 current_expression->reload = TRUE;
1602                                 current_expression->defined_by_phi = availability_table [current_expression->redundancy_class].class_defined_by_phi;
1603                                 current_expression->defined_by_real_occurrence = availability_table [current_expression->redundancy_class].class_defined_by_real_occurrence;
1604                         }
1605
1606                         current_expression->save = FALSE;
1607                 }
1608
1609                 if (current_bb->has_phi_argument) {
1610                         MonoSsapreBBInfo *phi_bb = current_bb->out_bb [0];
1611                         if (((phi_bb->phi_can_be_available) && (! phi_bb->phi_is_later)) &&
1612                                         ((current_bb->phi_argument_class == BOTTOM_REDUNDANCY_CLASS) ||
1613                                         ((current_bb->phi_argument_has_real_use == FALSE) && (current_bb->phi_argument_defined_by_phi != NULL) &&
1614                                                 (! ((current_bb->phi_argument_defined_by_phi->phi_can_be_available) && (! current_bb->phi_argument_defined_by_phi->phi_is_later)))
1615                                         ))) {
1616                                 current_bb->phi_argument_needs_insert = TRUE;
1617                                 current_bb->phi_argument_defined_by_real_occurrence = NULL;
1618                                 current_bb->phi_argument_defined_by_phi = NULL;
1619                         } else {
1620                                 current_bb->phi_argument_needs_insert = FALSE;
1621                                 if (current_bb->phi_argument_class != BOTTOM_REDUNDANCY_CLASS) {
1622                                         current_bb->phi_argument_defined_by_real_occurrence = availability_table [current_bb->phi_argument_class].class_defined_by_real_occurrence;
1623                                         current_bb->phi_argument_defined_by_phi = availability_table [current_bb->phi_argument_class].class_defined_by_phi;
1624                                 }
1625                         }
1626
1627                         current_bb->phi_argument_has_been_processed = FALSE;
1628                 }
1629         }
1630 }
1631
1632 /*
1633  * See paper, figure 13, function Set_save
1634  */
1635 static void set_save (MonoSsapreBBInfo *phi_occurrance, MonoSsapreExpressionOccurrence *real_occurrance) {
1636         if (real_occurrance != NULL) {
1637                 real_occurrance->save = TRUE;
1638         } else if (phi_occurrance != NULL) {
1639                 int i;
1640                 for (i = 0; i < phi_occurrance->in_count; i++) {
1641                         MonoSsapreBBInfo *phi_argument = phi_occurrance->in_bb [i];
1642                         if (! phi_argument->phi_argument_has_been_processed) {
1643                                 phi_argument->phi_argument_has_been_processed = TRUE;
1644                                 set_save (phi_argument->phi_argument_defined_by_phi, phi_argument->phi_argument_defined_by_real_occurrence);
1645                         }
1646                 }
1647         }
1648 }
1649
1650 /*
1651  * See paper, figure 13, function Finalize_2 (note that we still don't do
1652  * extraneous PHI elimination, see function Set_replacement)
1653  */
1654 static void finalize_save (MonoSsapreWorkArea *area) {
1655         MonoSsapreBBInfo *current_bb = NULL;
1656         MonoSsapreExpressionOccurrence *current_expression = NULL;
1657
1658         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1659                 for (current_expression = current_bb->first_expression_in_bb; (current_expression != NULL) && (current_expression->bb_info == current_bb); current_expression = current_expression->next) {
1660                         if (current_expression->reload) {
1661                                 set_save (current_expression->defined_by_phi, current_expression->defined_by_real_occurrence);
1662                         }
1663                 }
1664
1665                 if ((current_bb->has_phi_argument) &&
1666                                 (! current_bb->phi_argument_needs_insert) &&
1667                                 (current_bb->phi_argument_class != BOTTOM_REDUNDANCY_CLASS) &&
1668                                 (current_bb->phi_argument_defined_by_real_occurrence != NULL)) {
1669                         current_bb->phi_argument_defined_by_real_occurrence->save = TRUE;
1670                 }
1671         }
1672 }
1673
1674 /*
1675  * Perform all "finalize" steps
1676  */
1677 static void finalize (MonoSsapreWorkArea *area) {
1678         MonoSsapreAvailabilityTableElement *availability_table = alloca (sizeof (MonoSsapreAvailabilityTableElement) * (area->number_of_classes));
1679         int i;
1680
1681         for (i = 0; i < area->number_of_classes; i++) {
1682                 availability_table[i].class_defined_by_phi = NULL;
1683                 availability_table[i].class_defined_by_real_occurrence = NULL;
1684         }
1685
1686         finalize_availability_and_reload (area, availability_table);
1687         finalize_save (area);
1688 }
1689
1690 /*
1691  * Macros that help in creating constants
1692  */
1693 #define NEW_INST(dest,op) do {  \
1694                 (dest) = mono_mempool_alloc0 (area->cfg->mempool, sizeof (MonoInst));   \
1695                 (dest)->opcode = (op);  \
1696         } while (0)
1697
1698 #define NEW_I4(dest,val) do {   \
1699                 NEW_INST ((dest), OP_ICONST); \
1700                 (dest)->inst_c0 = (val);        \
1701                 (dest)->type = STACK_I4;        \
1702         } while (0)
1703
1704 #define NEW_I8(dest,val) do {   \
1705                 NEW_INST ((dest), OP_I8CONST); \
1706                 (dest)->inst_l = (val); \
1707                 (dest)->type = STACK_I8;        \
1708         } while (0)
1709
1710 #define NEW_R4(dest,f) do {     \
1711                 NEW_INST ((dest), OP_R4CONST); \
1712                 (dest)->inst_p0 = f;    \
1713                 (dest)->type = STACK_R8;        \
1714         } while (0)
1715
1716 #define NEW_R8(dest,d) do {     \
1717                 NEW_INST ((dest), OP_R8CONST); \
1718                 (dest)->inst_p0 = d;    \
1719                 (dest)->type = STACK_R8;        \
1720         } while (0)
1721
1722 /*
1723  * Create a MonoInst that represents an expression argument
1724  */
1725 static MonoInst*
1726 create_expression_argument (MonoSsapreWorkArea *area, MonoSsapreExpressionArgument *argument) {
1727         MonoInst *result;
1728
1729         switch (argument->type) {
1730                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_NOT_PRESENT:
1731                         return NULL;
1732                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE:
1733                         return mono_compile_create_var_load (area->cfg, argument->argument.ssa_variable);
1734                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT:
1735                         NEW_I4 (result, argument->argument.integer_constant);
1736                         return result;
1737                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_LONG_COSTANT:
1738                         NEW_I8 (result, *(argument->argument.long_constant));
1739                         return result;
1740                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT:
1741                         NEW_R4 (result, argument->argument.float_constant);
1742                         return result;
1743                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT:
1744                         NEW_R8 (result, argument->argument.double_constant);
1745                         return result;
1746                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE:
1747                 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY:
1748                 default:
1749                         g_assert_not_reached ();
1750                         return NULL;
1751         }
1752 }
1753
1754 /*
1755  * Create a MonoInst that represents an expression
1756  */
1757 static MonoInst*
1758 create_expression (MonoSsapreWorkArea *area, MonoSsapreExpressionDescription *expression, MonoInst *prototype_occurrence) {
1759         MonoInst *result;
1760         NEW_INST (result, expression->opcode);
1761         *result = *prototype_occurrence;
1762         result->inst_left = create_expression_argument (area, &(expression->left_argument));
1763         result->inst_right = create_expression_argument (area, &(expression->right_argument));
1764         return result;
1765 }
1766
1767 /*
1768  * Handles the father expression of a MonoInst that has been turned
1769  * into a load (eventually inserting it into the worklist).
1770  * Assumes "current_expression->father_in_tree != NULL".
1771  */
1772 static void
1773 handle_father_expression (MonoSsapreWorkArea *area, MonoSsapreExpressionOccurrence *current_expression, MonoInst *previous_tree) {
1774         if (DUMP_SSAPRE) {
1775                 printf ("After reload, father expression becomes ");
1776                 mono_print_tree_nl (current_expression->father_in_tree->father_occurrence);
1777         }
1778
1779         analyze_expression (current_expression->father_in_tree->father_occurrence, &(area->current_occurrence->description));
1780         if ((area->current_occurrence->description.opcode != 0) &&
1781                         (area->current_occurrence->description.left_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY) &&
1782                         (area->current_occurrence->description.right_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY)) {
1783                 area->current_occurrence->occurrence = current_expression->father_in_tree->father_occurrence;
1784                 area->current_occurrence->previous_tree = previous_tree;
1785                 area->current_occurrence->father_in_tree = current_expression->father_in_tree->grand_father;
1786                 area->current_occurrence->bb_info = current_expression->bb_info;
1787                 area->current_occurrence->is_first_in_bb = FALSE;
1788                 area->current_occurrence->is_last_in_bb = FALSE;
1789                 add_occurrence_to_worklist (area);
1790         }
1791 }
1792
1793 /*
1794  * See paper, section 3.6
1795  */
1796 static void code_motion (MonoSsapreWorkArea *area) {
1797         MonoSsapreBBInfo *current_bb = NULL;
1798         MonoSsapreExpressionOccurrence *current_expression = NULL;
1799         gssize original_variable_index = BOTTOM_REDUNDANCY_CLASS;
1800         MonoInst prototype_occurrence;
1801         prototype_occurrence.opcode = 0;
1802
1803         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1804                 if ((current_bb->has_phi) && (current_bb->phi_can_be_available && ! current_bb->phi_is_later)) {
1805                         MonoInst *new_var = mono_compile_create_var (area->cfg, area->current_expression->type, OP_LOCAL);
1806                         current_bb->phi_variable_index = new_var->inst_c0;
1807                         if (original_variable_index == BOTTOM_REDUNDANCY_CLASS) {
1808                                 original_variable_index = new_var->inst_c0;
1809                         }
1810                         area->cfg->vars [new_var->inst_c0]->reg = original_variable_index;
1811                         area->cfg->vars [new_var->inst_c0]->def_bb = current_bb->bb;
1812                 } else {
1813                         current_bb->phi_variable_index = BOTTOM_REDUNDANCY_CLASS;
1814                 }
1815
1816                 for (current_expression = current_bb->first_expression_in_bb; (current_expression != NULL) && (current_expression->bb_info == current_bb); current_expression = current_expression->next) {
1817                         if (prototype_occurrence.opcode == 0) {
1818                                 prototype_occurrence = *(current_expression->occurrence);
1819                         }
1820                         if (current_expression->save) {
1821                                 MonoInst *new_var = mono_compile_create_var (area->cfg, area->current_expression->type, OP_LOCAL);
1822                                 current_expression->variable_index = new_var->inst_c0;
1823                                 if (original_variable_index == BOTTOM_REDUNDANCY_CLASS) {
1824                                         original_variable_index = new_var->inst_c0;
1825                                 }
1826                                 area->cfg->vars [new_var->inst_c0]->reg = original_variable_index;
1827                                 area->cfg->vars [new_var->inst_c0]->def_bb = current_bb->bb;
1828                         } else {
1829                                 current_expression->variable_index = BOTTOM_REDUNDANCY_CLASS;
1830                         }
1831                 }
1832
1833                 if ((current_bb->has_phi_argument) && (current_bb->phi_argument_needs_insert)) {
1834                         MonoInst *new_var = mono_compile_create_var (area->cfg, area->current_expression->type, OP_LOCAL);
1835                         current_bb->phi_argument_variable_index = new_var->inst_c0;
1836                         if (original_variable_index == BOTTOM_REDUNDANCY_CLASS) {
1837                                 original_variable_index = new_var->inst_c0;
1838                         }
1839                         area->cfg->vars [new_var->inst_c0]->reg = original_variable_index;
1840                         area->cfg->vars [new_var->inst_c0]->def_bb = current_bb->bb;
1841                 } else {
1842                         current_bb->phi_argument_variable_index = BOTTOM_REDUNDANCY_CLASS;
1843                 }
1844         }
1845
1846         for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1847                 if (current_bb->phi_variable_index != BOTTOM_REDUNDANCY_CLASS) {
1848                         MonoInst *phi;
1849                         MonoInst *store;
1850                         int in_bb;
1851
1852                         NEW_INST (phi, OP_PHI);
1853                         phi->inst_c0 = area->cfg->vars [current_bb->phi_variable_index]->reg;
1854                         phi->inst_phi_args = mono_mempool_alloc (area->cfg->mempool, (sizeof (int) * ((current_bb->in_count) + 1)));
1855                         phi->inst_phi_args [0] = current_bb->in_count;
1856                         for (in_bb = 0; in_bb < current_bb->in_count; in_bb++) {
1857                                 gssize phi_argument_variable_index = current_bb->in_bb [in_bb]->phi_argument_variable_index;
1858                                 if (phi_argument_variable_index == BOTTOM_REDUNDANCY_CLASS) {
1859                                         MonoSsapreBBInfo *phi_argument_bb = current_bb->in_bb [in_bb];
1860                                         if (phi_argument_bb->phi_argument_defined_by_phi !=NULL) {
1861                                                 phi_argument_variable_index = phi_argument_bb->phi_argument_defined_by_phi->phi_variable_index;
1862                                         } else if (phi_argument_bb->phi_argument_defined_by_real_occurrence !=NULL) {
1863                                                 phi_argument_variable_index = phi_argument_bb->phi_argument_defined_by_real_occurrence->variable_index;
1864                                         } else {
1865                                                 g_assert_not_reached ();
1866                                         }
1867                                 }
1868                                 phi->inst_phi_args [in_bb + 1] = phi_argument_variable_index;
1869                         }
1870                         store = mono_compile_create_var_store (area->cfg, current_bb->phi_variable_index, phi);
1871                         if (current_bb->phi_insertion_point != NULL) {
1872                                 store->next = current_bb->phi_insertion_point->next;
1873                                 current_bb->phi_insertion_point->next = store;
1874                         } else {
1875                                 store->next = current_bb->bb->code;
1876                                 current_bb->bb->code = store;
1877                         }
1878                         area->cfg->vars [current_bb->phi_variable_index]->def = store;
1879                         current_bb->phi_insertion_point = store;
1880
1881                         area->added_phis ++;
1882                 }
1883
1884                 for (current_expression = current_bb->first_expression_in_bb; (current_expression != NULL) && (current_expression->bb_info == current_bb); current_expression = current_expression->next) {
1885                         gboolean altered = FALSE;
1886                         if (current_expression->save) {
1887                                 MonoInst *store;
1888                                 MonoInst *moved_expression = mono_mempool_alloc (area->cfg->mempool, sizeof (MonoInst));
1889                                 *moved_expression = *(current_expression->occurrence);
1890                                 store = mono_compile_create_var_store (area->cfg, current_expression->variable_index, moved_expression);
1891                                 if (current_expression->previous_tree != NULL) {
1892                                         store->next = current_expression->previous_tree->next;
1893                                         current_expression->previous_tree->next = store;
1894                                 } else {
1895                                         store->next = current_bb->bb->code;
1896                                         current_bb->bb->code = store;
1897                                 }
1898                                 area->cfg->vars [current_expression->variable_index]->def = store;
1899                                 mono_compile_make_var_load (area->cfg, current_expression->occurrence, current_expression->variable_index);
1900                                 if (current_expression->father_in_tree != NULL) {
1901                                         handle_father_expression (area, current_expression, store);
1902                                 }
1903
1904                                 area->saved_occurrences ++;
1905                                 altered = TRUE;
1906                         }
1907                         if (current_expression->reload) {
1908                                 gssize variable_index;
1909                                 if (current_expression->defined_by_phi != NULL) {
1910                                         variable_index = current_expression->defined_by_phi->phi_variable_index;
1911                                 } else if (current_expression->defined_by_real_occurrence != NULL) {
1912                                         variable_index = current_expression->defined_by_real_occurrence->variable_index;
1913                                 } else {
1914                                         variable_index = BOTTOM_REDUNDANCY_CLASS;
1915                                         g_assert_not_reached ();
1916                                 }
1917                                 mono_compile_make_var_load (area->cfg, current_expression->occurrence, variable_index);
1918                                 if (current_expression->father_in_tree != NULL) {
1919                                         handle_father_expression (area, current_expression, current_expression->previous_tree);
1920                                 }
1921
1922                                 area->reloaded_occurrences ++;
1923                                 altered = TRUE;
1924                         }
1925                         if (! altered) {
1926                                 area->unaltered_occurrences ++;
1927                         }
1928                 }
1929
1930                 if (current_bb->phi_argument_variable_index != BOTTOM_REDUNDANCY_CLASS) {
1931                         MonoSsapreExpressionDescription expression_description;
1932                         MonoInst *inserted_expression;
1933                         MonoInst *store;
1934
1935                         expression_description = area->current_expression->description;
1936                         if (expression_description.left_argument.type == MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE) {
1937                                 expression_description.left_argument.argument.ssa_variable = current_bb->phi_argument_left_argument_version;
1938                                 expression_description.left_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE;
1939                         }
1940                         if (expression_description.right_argument.type == MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE) {
1941                                 expression_description.right_argument.argument.ssa_variable = current_bb->phi_argument_right_argument_version;
1942                                 expression_description.right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE;
1943                         }
1944
1945                         inserted_expression = create_expression (area, &expression_description, &prototype_occurrence);
1946                         store = mono_compile_create_var_store (area->cfg, current_bb->phi_argument_variable_index, inserted_expression);
1947                         area->cfg->vars [current_bb->phi_argument_variable_index]->def = store;
1948                         store->next = NULL;
1949                         mono_add_ins_to_end (current_bb->bb, store);
1950
1951                         area->inserted_occurrences ++;
1952                 }
1953         }
1954 }
1955
1956 /*
1957  * Perform all SSAPRE steps for the current expression
1958  */
1959 static void
1960 process_expression (MonoSsapreWorkArea *area) {
1961         MonoSsapreExpression *expression = area->current_expression;
1962
1963         if (area->cfg->verbose_level >= STATISTICS_LEVEL) {
1964                 printf ("SSAPRE STARTS PROCESSING EXPRESSION ");
1965                 print_expression_description (&(expression->description));
1966                 printf ("\n");
1967         }
1968
1969         clean_area_infos (area);
1970
1971         area->current_expression = expression;
1972         phi_insertion (area, expression);
1973         renaming_pass (area);
1974
1975         if (area->cfg->verbose_level >= TRACE_LEVEL) {
1976                 printf ("START SUMMARY OF BB INFOS\n");
1977                 print_bb_infos (area);
1978                 printf ("END SUMMARY OF BB INFOS\n");
1979         }
1980
1981         down_safety (area);
1982         compute_can_be_available (area);
1983         compute_later (area);
1984         finalize (area);
1985         code_motion (area);
1986
1987         if (area->cfg->verbose_level >= DUMP_LEVEL) {
1988                 printf ("START DUMP OF BB INFOS\n");
1989                 dump_code (area);
1990                 printf ("END DUMP OF BB INFOS\n");
1991         } else if (area->cfg->verbose_level >= TRACE_LEVEL) {
1992                 printf ("START SUMMARY OF BB INFOS\n");
1993                 print_interesting_bb_infos (area);
1994                 printf ("END SUMMARY OF BB INFOS\n");
1995         }
1996
1997         if (area->cfg->verbose_level >= STATISTICS_LEVEL) {
1998                 printf ("STATISTICS: saved_occurrences = %d, reloaded_occurrences = %d, inserted_occurrences = %d, unaltered_occurrences = %d, added_phis = %d\n",
1999                         area->saved_occurrences, area->reloaded_occurrences, area->inserted_occurrences, area->unaltered_occurrences, area->added_phis);
2000         }
2001
2002         if (area->cfg->verbose_level >= TRACE_LEVEL) {
2003                 printf ("SSAPRE ENDS PROCESSING EXPRESSION ");
2004                 print_expression_description (&(expression->description));
2005                 printf ("\n");
2006         }
2007 }
2008
2009 #if (MONO_APPLY_SSAPRE_TO_SINGLE_METHOD)
2010 static char*
2011 mono_ssapre_method_name = NULL;
2012 static gboolean check_ssapre_method_name (MonoCompile *cfg) {
2013         if (mono_ssapre_method_name == NULL) {
2014                 mono_ssapre_method_name = getenv ("MONO_SSAPRE_METHOD_NAME");
2015         }
2016         if (mono_ssapre_method_name != NULL) {
2017                 char *method_name = mono_method_full_name (cfg->method, TRUE);
2018                 if (strstr (method_name, mono_ssapre_method_name) != NULL) {
2019                         return TRUE;
2020                 } else {
2021                         return FALSE;
2022                 }
2023         } else {
2024                 return TRUE;
2025         }
2026 }
2027 #endif
2028
2029 /*
2030  * Apply SSAPRE to a MonoCompile
2031  */
2032 void
2033 mono_perform_ssapre (MonoCompile *cfg) {
2034         MonoSsapreWorkArea area;
2035         int dt_dfn, descendants, block, i;
2036
2037 #if (MONO_APPLY_SSAPRE_TO_SINGLE_METHOD)
2038         if (! check_ssapre_method_name (cfg)) return;
2039 #endif
2040 #if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
2041         area.expression_is_handled_father = FALSE;
2042 #endif
2043
2044         area.cfg = cfg;
2045         area.mempool = mono_mempool_new ();
2046
2047         area.num_bblocks = cfg->num_bblocks;
2048         area.bb_infos = (MonoSsapreBBInfo*) mono_mempool_alloc (area.mempool, sizeof (MonoSsapreBBInfo) * (cfg->num_bblocks));
2049         area.bb_infos_in_cfg_dfn_order = (MonoSsapreBBInfo**) mono_mempool_alloc (area.mempool, sizeof (MonoSsapreBBInfo*) * (cfg->num_bblocks));
2050
2051         area.sizeof_bb_bitset = mono_bitset_alloc_size (cfg->num_bblocks, 0);
2052         area.expression_occurrences_buffer = mono_bitset_mem_new (mono_mempool_alloc (area.mempool, area.sizeof_bb_bitset), area.num_bblocks, 0);
2053         area.bb_iteration_buffer = mono_bitset_mem_new (mono_mempool_alloc (area.mempool, area.sizeof_bb_bitset), area.num_bblocks, 0);
2054         area.iterated_dfrontier_buffer = mono_bitset_mem_new (mono_mempool_alloc (area.mempool, area.sizeof_bb_bitset), area.num_bblocks, 0);
2055         area.left_argument_bb_bitset = mono_bitset_mem_new (mono_mempool_alloc (area.mempool, area.sizeof_bb_bitset), area.num_bblocks, 0);
2056         area.right_argument_bb_bitset = mono_bitset_mem_new (mono_mempool_alloc (area.mempool, area.sizeof_bb_bitset), area.num_bblocks, 0);
2057
2058         area.worklist = NULL;
2059
2060         if (area.cfg->verbose_level >= LOG_LEVEL) {
2061                 printf ("SSAPRE STARTS PROCESSING METHOD %s\n", mono_method_full_name (cfg->method, TRUE));
2062         }
2063
2064         area.first_in_queue = NULL;
2065         area.last_in_queue = NULL;
2066         area.current_occurrence = (MonoSsapreExpressionOccurrence*) mono_mempool_alloc (area.mempool, sizeof (MonoSsapreExpressionOccurrence));
2067         dt_dfn = 0;
2068         descendants = 0;
2069         area.dt_depth = 0;
2070         process_bb (&area, cfg->bblocks [0], &dt_dfn, &descendants, 1);
2071         for (block = 0; block < area.num_bblocks; block++) {
2072                 MonoSsapreBBInfo *bb_info = &(area.bb_infos [block]);
2073                 MonoBasicBlock *bb = bb_info->bb;
2074                 if (bb->idom != NULL) {
2075                         bb_info->idominator = area.bb_infos_in_cfg_dfn_order [bb->idom->dfn];
2076                 } else {
2077                         bb_info->idominator = NULL;
2078                 }
2079                 for (i = 0; i < bb->in_count; i++) {
2080                         bb_info->in_bb [i] = area.bb_infos_in_cfg_dfn_order [bb->in_bb [i]->dfn];
2081                 }
2082                 for (i = 0; i < bb->out_count; i++) {
2083                         bb_info->out_bb [i] = area.bb_infos_in_cfg_dfn_order [bb->out_bb [i]->dfn];
2084                 }
2085         }
2086
2087         if (area.cfg->verbose_level >= TRACE_LEVEL) {
2088                 printf ("SSAPRE START WORKLIST\n");
2089                 print_worklist (area.worklist);
2090                 printf ("SSAPRE END WORKLIST\n");
2091         }
2092
2093 #if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
2094         area.expression_is_handled_father = TRUE;
2095 #endif
2096         for (area.current_expression = area.first_in_queue; area.current_expression != NULL; area.current_expression = area.current_expression->next_in_queue) {
2097                 process_expression (&area);
2098         }
2099
2100         if (area.cfg->verbose_level >= TRACE_LEVEL) {
2101                 printf ("SSAPRE ENDS PROCESSING METHOD %s\n", mono_method_full_name (cfg->method, TRUE));
2102         }
2103
2104         mono_mempool_destroy (area.mempool);
2105 }