mono/mini/ssapre.c

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