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