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