mono/mini/local-propagation.c

   1 /*
   2  * local-propagation.c: Local constant, copy and tree propagation.
   3  *
   4  * To make some sense of the tree mover, read mono/docs/tree-mover.txt
   5  *
   6  * Author:
   7  *   Paolo Molaro (lupus@ximian.com)
   8  *   Dietmar Maurer (dietmar@ximian.com)
   9  *   Massimiliano Mantione (massi@ximian.com)
  10  *
  11  * (C) 2006 Novell, Inc.  http://www.novell.com
  12  */
  13
  14
  15 #include <string.h>
  16 #include <stdio.h>
  17
  18 #include <mono/metadata/debug-helpers.h>
  19 #include <mono/metadata/mempool.h>
  20 #include <mono/metadata/opcodes.h>
  21 #include "mini.h"
  22
  23
  24 #define MONO_DEBUG_LOCAL_PROP 0
  25 #define MONO_DEBUG_TREE_MOVER 0
  26 #define MONO_DUMP_TREE_MOVER 0
  27 #define MONO_APPLY_TREE_MOVER_TO_SINGLE_METHOD 0
  28 #define MONO_APPLY_TREE_MOVER_TO_COUNTED_METHODS 0
  29
  30 struct TreeMoverActSlot;
  31 /*
  32  * A node describing one dependency between a tree and a local
  33  */
  34 typedef struct TreeMoverDependencyNode {
  35         /* The local used in the tree */
  36         struct TreeMoverActSlot *used_slot;
  37         /* The local defined by the tree */
  38         struct TreeMoverActSlot *affected_slot;
  39         /* Next in the list of used locals */
  40         struct TreeMoverDependencyNode *next_used_local;
  41         /* Next in the list of affected locals */
  42         struct TreeMoverDependencyNode *next_affected_local;
  43         /* Previous in the list of affected locals */
  44         struct TreeMoverDependencyNode *previous_affected_local;
  45         /* False if the local is used in a tree that defines a used local */
  46         guchar use_is_direct;
  47 } TreeMoverDependencyNode;
  48
  49 struct TreeMoverTreeMove;
  50 /*
  51  * A node in a list of affected TreeMoverTreeMove
  52  */
  53 typedef struct TreeMoverAffectedMove {
  54         struct TreeMoverTreeMove *affected_move;
  55         struct TreeMoverAffectedMove *next_affected_move;
  56 } TreeMoverAffectedMove;
  57
  58 /*
  59  * A node in a list of TreeMoverDependencyFromDeadDefinition
  60  */
  61 typedef struct TreeMoverDependencyFromDeadDefinition {
  62         /* The ACT slot of the defined local */
  63         struct TreeMoverActSlot *defined_slot;
  64         /* The definition that will hopefully be dead */
  65         MonoInst *dead_definition;
  66         /* Next in the list */
  67         struct TreeMoverDependencyFromDeadDefinition *next;
  68 } TreeMoverDependencyFromDeadDefinition;
  69
  70 /*
  71  * A "tree move"
  72  */
  73 typedef struct TreeMoverTreeMove {
  74         /* ACT slot of the defined local */
  75         struct TreeMoverActSlot *defined_slot;
  76         /* Code location of the definition */
  77         MonoInst *definition;
  78         /* Code location where the tree must be replaced with the local */
  79         MonoInst **use;
  80         /* Moves that must not be performed of we perform this one */
  81         TreeMoverAffectedMove *affected_moves;
  82         /* Definitions that must be dead to be allowed to perform this move */
  83         struct TreeMoverDependencyFromDeadDefinition *slots_that_must_be_safe;
  84         /* Next in the list of scheduled moves */
  85         struct TreeMoverTreeMove *next;
  86         /* The used tree accesses heap memory */
  87         guchar tree_reads_memory;
  88         /* A subsequent definitions makes this move globally safe */
  89         guchar move_is_safe;
  90         /* This move has been affected by something, ignore it */
  91         guchar skip_this_move;
  92         /* "tree forwarding" cannot continue for this definition */
  93         guchar prevent_forwarding;
  94 } TreeMoverTreeMove;
  95
  96 /*
  97  * An ACT slot (there is one for each local in the ACT array)
  98  */
  99 typedef struct TreeMoverActSlot {
 100         /* List of used locals (directly and indirectly) */
 101         TreeMoverDependencyNode *used_locals;
 102         /* Last element (so that we can move all the nodes quickly) */
 103         TreeMoverDependencyNode *last_used_local;
 104         /* List of affected locals (definitions that use this local) */
 105         TreeMoverDependencyNode *affected_locals;
 106         /* The current pending move */
 107         TreeMoverTreeMove *pending_move;
 108         /* True if the move has already met its use use */
 109         guchar pending_move_is_ready;
 110         /* See [W] flag */
 111         guchar waiting_flag;
 112         /* See [X] flag */
 113         guchar unsafe_flag;
 114         /* A "tree forwarding" is in progress */
 115         guchar pending_move_is_forwarded;
 116 } TreeMoverActSlot;
 117
 118 /*
 119  * Main tree mover work area
 120  */
 121 typedef struct TreeMover {
 122         /* Pool used for allocating everything */
 123         MonoMemPool *pool;
 124         /* Current method */
 125         MonoCompile *cfg;
 126
 127         /* Free (recycled) TreeMoverDependencyNode structs */
 128         TreeMoverDependencyNode *free_nodes;
 129         /* Free (recycled) TreeMoverTreeMove structs */
 130         TreeMoverTreeMove *free_moves;
 131
 132         /* ACT array */
 133         TreeMoverActSlot *ACT;
 134         /* List of tree moves that could be performed */
 135         TreeMoverTreeMove *scheduled_moves;
 136
 137         /* The following fields are reset at each tree traversal */
 138         /* List of used locals */
 139         TreeMoverDependencyNode *used_nodes;
 140         /* Last node in the list (to free it in one block) */
 141         TreeMoverDependencyNode *last_used_node;
 142         /* The current tree cannot be moved (it can still receive moves!) */
 143         guchar tree_has_side_effects;
 144         /* The current tree reads heap locations */
 145         guchar tree_reads_memory;
 146 } TreeMover;
 147
 148 inline static TreeMoverDependencyNode*
 149 tree_mover_new_node (TreeMover *tree_mover) {
 150         TreeMoverDependencyNode *node;
 151
 152         if (tree_mover->free_nodes != NULL) {
 153                 node = tree_mover->free_nodes;
 154                 tree_mover->free_nodes = tree_mover->free_nodes->next_used_local;
 155                 node->next_used_local = NULL;
 156                 node->next_affected_local = NULL;
 157                 node->previous_affected_local = NULL;
 158         } else {
 159                 node = (TreeMoverDependencyNode*) mono_mempool_alloc0 (tree_mover->pool, sizeof (TreeMoverDependencyNode));
 160         }
 161
 162         return node;
 163 }
 164
 165 inline static void
 166 tree_mover_new_slot_move (TreeMover *tree_mover, TreeMoverActSlot *slot) {
 167         TreeMoverTreeMove *move;
 168
 169         if (tree_mover->free_moves != NULL) {
 170                 move = tree_mover->free_moves;
 171                 tree_mover->free_moves = tree_mover->free_moves->next;
 172                 memset (move, 0, sizeof (TreeMoverTreeMove));
 173         } else {
 174                 move = (TreeMoverTreeMove*) mono_mempool_alloc0 (tree_mover->pool, sizeof (TreeMoverTreeMove));
 175         }
 176
 177         slot->pending_move = move;
 178 }
 179
 180 inline static void
 181 tree_mover_dispose_used_nodes (TreeMover *tree_mover) {
 182         tree_mover->last_used_node->next_used_local = tree_mover->free_nodes;
 183         tree_mover->free_nodes = tree_mover->used_nodes;
 184         tree_mover->used_nodes = NULL;
 185         tree_mover->last_used_node = NULL;
 186 }
 187
 188 inline static void
 189 tree_mover_dispose_slot_nodes (TreeMover *tree_mover, TreeMoverActSlot *slot) {
 190         slot->last_used_local->next_used_local = tree_mover->free_nodes;
 191         tree_mover->free_nodes = slot->used_locals;
 192         slot->used_locals = NULL;
 193         slot->last_used_local = NULL;
 194 }
 195
 196 inline static void
 197 tree_mover_dispose_slot_move (TreeMover *tree_mover, TreeMoverActSlot *slot) {
 198         slot->pending_move->next = tree_mover->free_moves;
 199         tree_mover->free_moves = slot->pending_move;
 200         slot->pending_move = NULL;
 201 }
 202
 203 inline static TreeMoverActSlot*
 204 tree_mover_slot_from_index (TreeMover *tree_mover, int index) {
 205         return & (tree_mover->ACT [index]);
 206 }
 207
 208 inline static int
 209 tree_mover_slot_to_index (TreeMover *tree_mover, TreeMoverActSlot *slot) {
 210         return slot - tree_mover->ACT;
 211 }
 212
 213 inline static void
 214 tree_mover_add_used_node (TreeMover *tree_mover, TreeMoverActSlot *slot, gboolean use_is_direct) {
 215         TreeMoverDependencyNode *node;
 216
 217         node = tree_mover_new_node (tree_mover);
 218         node->used_slot = slot;
 219         node->affected_slot = NULL;
 220         node->use_is_direct = use_is_direct;
 221         if (tree_mover->last_used_node != NULL) {
 222                 tree_mover->last_used_node->next_used_local = node;
 223         } else {\
 224                 tree_mover->used_nodes = node;
 225         }\
 226         tree_mover->last_used_node = node;
 227 }
 228
 229 inline static void
 230 tree_mover_link_affecting_node (TreeMoverDependencyNode *node, TreeMoverActSlot *affected_slot) {
 231         TreeMoverActSlot *affecting_slot = node->used_slot;
 232         node->affected_slot = affected_slot;
 233         node->next_affected_local = affecting_slot->affected_locals;
 234         affecting_slot->affected_locals = node;
 235         if (node->next_affected_local != NULL) {
 236                 node->next_affected_local->previous_affected_local = node;
 237         }
 238         node->previous_affected_local = NULL;
 239 }
 240
 241 inline static void
 242 tree_mover_unlink_affecting_node (TreeMoverDependencyNode *node) {
 243         if (node->next_affected_local != NULL) {
 244                 node->next_affected_local->previous_affected_local = node->previous_affected_local;
 245         }
 246         if (node->previous_affected_local != NULL) {
 247                 node->previous_affected_local->next_affected_local = node->next_affected_local;
 248         } else {
 249                 TreeMoverActSlot *slot = node->used_slot;
 250                 slot->affected_locals = node->next_affected_local;
 251         }
 252         node->next_affected_local = NULL;
 253         node->previous_affected_local = NULL;
 254         node->affected_slot = NULL;
 255 }
 256
 257 inline static void
 258 tree_mover_link_affected_moves (TreeMover *tree_mover, TreeMoverActSlot *source_slot, TreeMoverActSlot *destination_slot) {
 259         TreeMoverAffectedMove *node = (TreeMoverAffectedMove*) mono_mempool_alloc0 (tree_mover->pool, sizeof (TreeMoverAffectedMove));
 260         node->affected_move = destination_slot->pending_move;
 261         node->next_affected_move = source_slot->pending_move->affected_moves;
 262         source_slot->pending_move->affected_moves = node;
 263 }
 264
 265
 266 inline static void
 267 tree_mover_record_pending_move (TreeMover *tree_mover, TreeMoverActSlot *slot, gboolean move_is_safe) {
 268         if (slot->pending_move_is_ready) {
 269                 slot->pending_move->move_is_safe = move_is_safe;
 270                 slot->pending_move->next = tree_mover->scheduled_moves;
 271                 tree_mover->scheduled_moves = slot->pending_move;
 272                 slot->pending_move = NULL;
 273                 slot->pending_move_is_ready = FALSE;
 274         }
 275 }
 276
 277 inline static void
 278 tree_mover_clear_forwarding_dependency (TreeMoverActSlot *slot) {
 279         if (slot->pending_move_is_forwarded) {
 280                 TreeMoverDependencyFromDeadDefinition *dependency = slot->pending_move->slots_that_must_be_safe;
 281                 while (dependency != NULL) {
 282                         if (dependency->defined_slot == slot) {
 283                                 dependency->defined_slot = NULL;
 284                         }
 285                         dependency = dependency->next;
 286                 }
 287                 slot->pending_move = NULL;
 288         }
 289 }
 290
 291 inline static void
 292 tree_mover_enforce_forwarding_dependency (TreeMoverActSlot *slot) {
 293         if (slot->pending_move_is_forwarded) {
 294                 slot->pending_move->skip_this_move = TRUE;
 295                 slot->pending_move_is_forwarded = FALSE;
 296                 slot->pending_move = NULL;
 297         }
 298 }
 299
 300 inline static void
 301 tree_mover_clean_act_slot_dependency_nodes (TreeMover *tree_mover, TreeMoverActSlot *slot) {
 302         TreeMoverDependencyNode *current_node = slot->used_locals;
 303         while (current_node != NULL) {
 304                 tree_mover_unlink_affecting_node (current_node);
 305                 current_node = current_node->next_used_local;
 306         }
 307         if (slot->used_locals != NULL) {
 308                 tree_mover_dispose_slot_nodes (tree_mover, slot);
 309         }
 310 }
 311
 312 inline static void
 313 tree_mover_clean_act_slot_pending_move (TreeMover *tree_mover, TreeMoverActSlot *slot) {
 314         if (slot->pending_move != NULL) {
 315                 if (! slot->pending_move_is_forwarded) {
 316                         tree_mover_dispose_slot_move (tree_mover, slot);
 317                 } else {\
 318                         slot->pending_move = NULL;
 319                 }
 320         }
 321         slot->pending_move_is_ready = FALSE;
 322         slot->pending_move_is_forwarded = FALSE;
 323 }
 324
 325 inline static void
 326 tree_mover_clean_act_slot (TreeMover *tree_mover, TreeMoverActSlot *slot) {
 327         tree_mover_clean_act_slot_dependency_nodes (tree_mover, slot);
 328         tree_mover_clean_act_slot_pending_move (tree_mover, slot);
 329 }
 330
 331 inline static void
 332 tree_mover_kill_act_slot_for_definition (TreeMover *tree_mover, TreeMoverActSlot *slot) {
 333         tree_mover_record_pending_move (tree_mover, slot, TRUE);
 334         tree_mover_clear_forwarding_dependency (slot);
 335         tree_mover_clean_act_slot (tree_mover, slot);
 336 }
 337
 338 inline static void
 339 tree_mover_kill_act_slot_because_it_is_affected (TreeMover *tree_mover, TreeMoverActSlot *slot) {
 340         if ((! slot->pending_move_is_ready) && (! slot->pending_move_is_forwarded)) {
 341                 tree_mover_clean_act_slot (tree_mover, slot);
 342         }
 343 }
 344
 345 inline static void
 346 tree_mover_kill_act_slot_for_use (TreeMover *tree_mover, TreeMoverActSlot *slot) {
 347         tree_mover_enforce_forwarding_dependency (slot);
 348         tree_mover_clean_act_slot (tree_mover, slot);
 349 }
 350
 351 inline static void
 352 tree_mover_kill_act_for_indirect_local_definition (TreeMover *tree_mover, int size) {
 353         int i;
 354         for (i = 0; i < size; i++) {
 355                 TreeMoverActSlot *slot = &(tree_mover->ACT [i]);
 356                 if (slot->pending_move != NULL) {
 357                         slot->pending_move->prevent_forwarding = TRUE;
 358                 }
 359                 tree_mover_kill_act_slot_because_it_is_affected (tree_mover, slot);
 360         }
 361 }
 362
 363 inline static void
 364 tree_mover_kill_act_for_indirect_global_definition (TreeMover *tree_mover, int size) {
 365         int i;
 366         for (i = 0; i < size; i++) {
 367                 TreeMoverActSlot *slot = &(tree_mover->ACT [i]);
 368                 if ((slot->pending_move != NULL) && slot->pending_move->tree_reads_memory) {
 369                         tree_mover_kill_act_slot_because_it_is_affected (tree_mover, slot);
 370                 }
 371         }
 372 }
 373
 374 inline static void
 375 tree_mover_kill_act_for_indirect_use (TreeMover *tree_mover, int size) {
 376         int i;
 377         for (i = 0; i < size; i++) {
 378                 TreeMoverActSlot *slot = &(tree_mover->ACT [i]);
 379                 tree_mover_kill_act_slot_for_use (tree_mover, slot);
 380         }
 381 }
 382
 383 inline static void
 384 tree_mover_clear_act_recording_moves (TreeMover *tree_mover, int size) {
 385         int i;
 386         for (i = 0; i < size; i++) {
 387                 TreeMoverActSlot *slot = &(tree_mover->ACT [i]);
 388                 tree_mover_record_pending_move (tree_mover, slot, FALSE);
 389                 tree_mover_clean_act_slot (tree_mover, slot);
 390         }
 391 }
 392
 393 inline static void
 394 tree_mover_set_waiting_flags (TreeMover *tree_mover, int size) {
 395         int i;
 396         for (i = 0; i < size; i++) {
 397                 TreeMoverActSlot *slot = &(tree_mover->ACT [i]);
 398                 slot->waiting_flag = TRUE;
 399         }
 400 }
 401
 402 inline static void
 403 tree_mover_verify_dependency_nodes_are_clear (TreeMover *tree_mover, int size) {
 404         int i;
 405         for (i = 0; i < size; i++) {
 406                 TreeMoverActSlot *slot = &(tree_mover->ACT [i]);
 407                 if (slot->affected_locals != NULL) {
 408                         printf ("Slot %d has still affected variables\n", i);
 409                         g_assert_not_reached ();
 410                 }
 411                 if (slot->used_locals != NULL) {
 412                         printf ("Slot %d has still used variables\n", i);
 413                         g_assert_not_reached ();
 414                 }
 415                 if (slot->last_used_local != NULL) {
 416                         printf ("Slot %d has still a last used variable\n", i);
 417                         g_assert_not_reached ();
 418                 }
 419         }
 420 }
 421
 422
 423 static const guchar stind_needs_conversion[(CEE_STIND_R8-CEE_STIND_REF)+1][STACK_MAX] = {
 424         /* INV I4    I8    PTR   R8    MP    OBJ   VTYPE */
 425         {TRUE ,TRUE, TRUE, FALSE,TRUE, FALSE,FALSE,TRUE}, /* CEE_STIND_REF */
 426         {TRUE ,TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE}, /* CEE_STIND_I1  */
 427         {TRUE ,TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE}, /* CEE_STIND_I2  */
 428         {TRUE ,FALSE,TRUE, TRUE, TRUE, TRUE, TRUE, TRUE}, /* CEE_STIND_I4  */
 429         {TRUE ,TRUE, FALSE,TRUE, TRUE, TRUE, TRUE, TRUE}, /* CEE_STIND_I8  */
 430         {TRUE ,TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE}, /* CEE_STIND_R4  */
 431         {TRUE ,TRUE, TRUE, TRUE, FALSE,TRUE, TRUE, TRUE}  /* CEE_STIND_R8  */
 432 };
 433 static const guchar stind_i_needs_conversion[STACK_MAX] = {TRUE ,TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, TRUE};
 434 static const guchar ldind_needs_conversion[(CEE_LDIND_REF-CEE_LDIND_I1)+1][STACK_MAX] = {
 435         /* INV I4    I8    PTR   R8    MP    OBJ   VTYPE */
 436         {TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE}, /* CEE_LDIND_I1  */
 437         {TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE}, /* CEE_LDIND_U1  */
 438         {TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE}, /* CEE_LDIND_I2  */
 439         {TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE}, /* CEE_LDIND_U2  */
 440         {TRUE, FALSE,TRUE, TRUE, TRUE, TRUE, TRUE, TRUE}, /* CEE_LDIND_I4  */
 441         {TRUE, FALSE,TRUE, TRUE, TRUE, TRUE, TRUE, TRUE}, /* CEE_LDIND_U4  */
 442         {TRUE, TRUE, FALSE,TRUE, TRUE, TRUE, TRUE, TRUE}, /* CEE_LDIND_I8  */
 443         {TRUE, TRUE, TRUE, FALSE,TRUE, FALSE,FALSE,TRUE}, /* CEE_LDIND_I   */
 444         {TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE}, /* CEE_LDIND_R4  */
 445         {TRUE, TRUE, TRUE, TRUE, FALSE,TRUE, TRUE, TRUE}, /* CEE_LDIND_R8  */
 446         {TRUE, TRUE, TRUE, FALSE,TRUE, FALSE,FALSE,TRUE}  /* CEE_LDIND_REF */
 447 };
 448
 449 #define TREE_MOVER_LDIND_TO_CONV(__opcode) (ldind_to_conv [(__opcode) - CEE_LDIND_I1])
 450 #define TREE_MOVER_STIND_NEEDS_CONVERSION(__opcode,__type) (((__opcode) != CEE_STIND_I) ? (stind_needs_conversion [(__opcode) - CEE_STIND_REF][(__type)]) : (stind_i_needs_conversion [(__type)]))
 451 #define TREE_MOVER_LDIND_NEEDS_CONVERSION(__opcode,__type) (ldind_needs_conversion [(__opcode) - CEE_LDIND_I1][(__type)])
 452
 453 static void
 454 tree_mover_print_act_slot (const char* message, TreeMover *tree_mover, TreeMoverActSlot *slot) {
 455         TreeMoverDependencyNode *node;
 456         printf ("  [%s] Slot %d uses {", message, tree_mover_slot_to_index (tree_mover, slot));
 457         for (node = slot->used_locals; node != NULL; node = node->next_used_local) {
 458                 printf (" %d", tree_mover_slot_to_index (tree_mover, node->used_slot));
 459         }
 460         printf (" } affects {");
 461         for (node = slot->affected_locals; node != NULL; node = node->next_affected_local) {
 462                 printf (" %d", tree_mover_slot_to_index (tree_mover, node->affected_slot));
 463         }
 464         printf (" } R%d F%d W%d U%d", slot->pending_move_is_ready, slot->pending_move_is_forwarded, slot->waiting_flag, slot->unsafe_flag);
 465         if (slot->pending_move != NULL) {
 466                 printf (" DEFINITION:");
 467                 //printf (" DEFINITION[%p]:", slot->pending_move->definition);
 468                 mono_print_tree (slot->pending_move->definition);
 469         }
 470         printf ("\n");
 471 }
 472
 473 static TreeMoverTreeMove*
 474 mono_cprop_copy_values (MonoCompile *cfg, TreeMover *tree_mover, MonoInst *tree, MonoInst **acp)
 475 {
 476         MonoInst *cp;
 477         int arity;
 478         TreeMoverTreeMove *pending_move = NULL;
 479
 480         if (tree->ssa_op == MONO_SSA_LOAD && (tree->inst_i0->opcode == OP_LOCAL || tree->inst_i0->opcode == OP_ARG) &&
 481             (cp = acp [tree->inst_i0->inst_c0]) && !tree->inst_i0->flags) {
 482
 483                 if (cp->opcode == OP_ICONST) {
 484                         if (cfg->opt & MONO_OPT_CONSPROP) {
 485                                 //{ static int c = 0; printf ("CCOPY %d %d %s\n", c++, cp->inst_c0, mono_method_full_name (cfg->method, TRUE)); }
 486                                 if (MONO_DEBUG_LOCAL_PROP) {
 487                                         printf ("Propagating constant, tree ");
 488                                         mono_print_tree (tree);
 489                                         printf (" becomes ");
 490                                         mono_print_tree (cp);
 491                                         printf ("\n");
 492                                 }
 493                                 *tree = *cp;
 494                         }
 495                 } else {
 496                         if ((tree->inst_i0->inst_vtype->type == cp->inst_vtype->type) ||
 497                             (tree->type == STACK_OBJ) || (tree->type == STACK_MP)) {
 498                                 if (cfg->opt & MONO_OPT_COPYPROP) {
 499                                         //{ static int c = 0; printf ("VCOPY %d\n", ++c); }
 500                                         if (MONO_DEBUG_LOCAL_PROP) {
 501                                                 printf ("Propagating value, tree->inst_i0 ");
 502                                                 mono_print_tree (tree->inst_i0);
 503                                                 printf (" becomes ");
 504                                                 mono_print_tree (cp);
 505                                                 printf ("\n");
 506                                         }
 507                                         tree->inst_i0 = cp;
 508                                 }
 509                         } else if (MONO_DEBUG_LOCAL_PROP) {
 510                                 char* tree_type_name = mono_type_full_name (tree->inst_i0->inst_vtype);
 511                                 char* cp_type_name = mono_type_full_name (cp->inst_vtype);
 512                                 printf ("Values of tree->inst_i0 ");
 513                                 mono_print_tree (tree->inst_i0);
 514                                 printf (" and cp ");
 515                                 mono_print_tree (cp);
 516                                 printf (" have incompatible types in tree ");
 517                                 mono_print_tree (tree);
 518                                 printf ("\n");
 519                                 printf (" MonoType of tree->inst_i0 is: %s\n", tree_type_name);
 520                                 printf (" MonoType of cp is: %s\n", cp_type_name);
 521                                 g_free (tree_type_name);
 522                                 g_free (cp_type_name);
 523                         }
 524                 }
 525         } else {
 526                 if (MONO_DEBUG_LOCAL_PROP) {
 527                         printf ("Propagation SKIPPED for inst ");
 528                         mono_print_tree (tree);
 529                         printf ("\n");
 530                 }
 531                 if ((tree_mover != NULL) && (cfg->opt & MONO_OPT_CFOLD))
 532                         mono_constant_fold_inst (tree, NULL);
 533
 534                 arity = mono_burg_arity [tree->opcode];
 535
 536                 if (arity) {
 537                         TreeMoverTreeMove *result = mono_cprop_copy_values (cfg, tree_mover, tree->inst_i0, acp);
 538                         if (cfg->opt & MONO_OPT_CFOLD)
 539                                 mono_constant_fold_inst (tree, NULL);
 540                         if (result != NULL) {
 541                                 result->use = &(tree->inst_i0);
 542                                 //printf (" SETTING inst_i0[%p] USE to %p (definition is %p)\n", tree, result->use, result->definition);
 543
 544                         }
 545                         /* The opcode may have changed */
 546                         if (mono_burg_arity [tree->opcode] > 1) {
 547                                 if (cfg->opt & MONO_OPT_CFOLD)
 548                                         mono_constant_fold_inst (tree, NULL);
 549                                 result = mono_cprop_copy_values (cfg, tree_mover, tree->inst_i1, acp);
 550                                 if (result != NULL) {
 551                                         result->use = &(tree->inst_i1);
 552                                         //printf (" SETTING inst_i1[%p] USE to %p (definition is %p)\n", tree, result->use, result->definition);
 553                                 }
 554                         }
 555                         mono_constant_fold_inst (tree, NULL);
 556                 }
 557         }
 558
 559         /* Apply the tree mover after after propagation has been done */
 560         if ((tree_mover != NULL) && (tree->ssa_op == MONO_SSA_LOAD) &&
 561                         (tree->inst_i0->opcode == OP_LOCAL || tree->inst_i0->opcode == OP_ARG)) {
 562                 guint used_index = tree->inst_i0->inst_c0;
 563                 TreeMoverActSlot *used_slot = &(tree_mover->ACT [used_index]);
 564
 565                 /* First, handle waiting flag */
 566                 if (used_slot->waiting_flag) {
 567                         used_slot->unsafe_flag = TRUE;
 568                         used_slot->waiting_flag = FALSE;
 569                 }
 570
 571                 if (!tree->inst_i0->flags) {
 572                         /* Record local use (the tree that contains this use might be movable) */
 573                         tree_mover_add_used_node (tree_mover, used_slot, TRUE);
 574
 575                         /* Start working on the pending move... */
 576                         pending_move = used_slot->pending_move;
 577
 578                         /* If there *is* a pending move... (otherwise, do nothing) */
 579                         if (pending_move != NULL) {
 580                                 /* Check slot state */
 581                                 if (used_slot->pending_move_is_forwarded) {
 582                                         /* If the slot was a "hopefully dead" definition because of a forwarding... */
 583                                         if (MONO_DEBUG_TREE_MOVER) {
 584                                                 printf ("Use should have been dead, killing slot %d: ", used_index);
 585                                                 mono_print_tree_nl (tree);
 586                                                 printf ("Also disabling forwarded definition at slot %d: ", tree_mover_slot_to_index (tree_mover, pending_move->defined_slot));
 587                                                 mono_print_tree_nl (pending_move->definition);
 588                                         }
 589                                         /* ...clear the slot (which also disables the forwarded definition), and... */
 590                                         tree_mover_kill_act_slot_for_use (tree_mover, used_slot);
 591                                         /* ...clear the pending_move */
 592                                         pending_move = NULL;
 593                                 } else if (used_slot->pending_move_is_ready ||
 594                                                 TREE_MOVER_STIND_NEEDS_CONVERSION (pending_move->definition->opcode, pending_move->definition->inst_i1->type) ||
 595                                                 TREE_MOVER_LDIND_NEEDS_CONVERSION (tree->opcode, pending_move->definition->inst_i1->type)) {
 596                                         /* If the move was already in state [U], or if there are type problems... */
 597                                         if (MONO_DEBUG_TREE_MOVER) {
 598                                                 printf ("Definition has too many, wrong or misplaced uses, killing slot %d: ", used_index);
 599                                                 mono_print_tree_nl (tree);
 600                                         }
 601                                         /* ...kill it, and clear the pending_move */
 602                                         tree_mover_kill_act_slot_for_use (tree_mover, used_slot);
 603                                         pending_move = NULL;
 604                                 } else {
 605                                         /* All goes well: set slot state to [U] */
 606                                         TreeMoverDependencyNode *node = used_slot->used_locals;
 607                                         if (MONO_DEBUG_TREE_MOVER) {
 608                                                 printf ("Setting tree move for slot %d as ready: ", used_index);
 609                                                 mono_print_tree_nl (tree);
 610                                         }
 611                                         /* Record indirect uses generated by this move */
 612                                         while (node != NULL) {
 613                                                 tree_mover_add_used_node (tree_mover, node->used_slot, FALSE);
 614                                                 node = node->next_used_local;
 615                                         }
 616
 617                                         /* Setup tree as movable */
 618                                         used_slot->pending_move_is_ready = TRUE;
 619                                 }
 620                         }
 621                 } else {
 622                         if (MONO_DEBUG_TREE_MOVER) {
 623                                 printf ("Tree has side effects, killing slot %d: ", used_index);
 624                                 mono_print_tree_nl (tree);
 625                         }
 626                         /* The whole tree is unmovable (it uses a flagged local) */
 627                         tree_mover->tree_has_side_effects = TRUE;
 628                         /* Moreover, the use of a flagged local kills the definition */
 629                         tree_mover_kill_act_slot_for_use (tree_mover, used_slot);
 630                 }
 631 #if MONO_DUMP_TREE_MOVER
 632                 tree_mover_print_act_slot ("USE", tree_mover, used_slot);
 633 #endif
 634         }
 635         return pending_move;
 636 }
 637
 638 static void
 639 mono_cprop_invalidate_values (MonoInst *tree, TreeMover *tree_mover, MonoInst **acp, int acp_size)
 640 {
 641         int arity;
 642
 643         if (tree_mover != NULL) {
 644                 if ((tree->opcode == CEE_NEWARR) || (mono_find_jit_opcode_emulation (tree->opcode) != NULL)) {
 645                         if (MONO_DEBUG_TREE_MOVER) {
 646                                 printf ("Recording side effect because emulated opcode cannot be moved: ");
 647                                 mono_print_tree_nl (tree);
 648                         }
 649                         tree_mover->tree_has_side_effects = TRUE;
 650                 }
 651         }
 652
 653         switch (tree->opcode) {
 654         case CEE_LDIND_REF:
 655         case CEE_LDIND_I1:
 656         case CEE_LDIND_I2:
 657         case CEE_LDIND_I4:
 658         case CEE_LDIND_U1:
 659         case CEE_LDIND_U2:
 660         case CEE_LDIND_U4:
 661         case CEE_LDIND_I8:
 662         case CEE_LDIND_R4:
 663         case CEE_LDIND_R8:
 664         case CEE_LDIND_I:
 665         case CEE_LDOBJ:
 666                 if ((tree_mover != NULL) && ((tree->ssa_op == MONO_SSA_NOP) || (tree->ssa_op & MONO_SSA_ADDRESS_TAKEN))) {
 667                         if (MONO_DEBUG_TREE_MOVER) {
 668                                 printf ("Recording memory read at inst: ");
 669                                 mono_print_tree_nl (tree);
 670                         }
 671                         tree_mover->tree_reads_memory = TRUE;
 672                 }
 673                 break;
 674         case CEE_STIND_I:
 675         case CEE_STIND_I1:
 676         case CEE_STIND_I2:
 677         case CEE_STIND_I4:
 678         case CEE_STIND_REF:
 679         case CEE_STIND_I8:
 680         case CEE_STIND_R4:
 681         case CEE_STIND_R8:
 682         case CEE_STOBJ:
 683                 if ((tree->ssa_op == MONO_SSA_NOP) || (tree->ssa_op & MONO_SSA_ADDRESS_TAKEN)) {
 684                         if (MONO_DEBUG_LOCAL_PROP) {
 685                                 printf ("Indirect store clears ACP at tree ");
 686                                 mono_print_tree (tree);
 687                                 printf ("\n");
 688                         }
 689                         memset (acp, 0, sizeof (MonoInst *) * acp_size);
 690                         if (tree_mover != NULL) {
 691                                 if (MONO_DEBUG_TREE_MOVER) {
 692                                         printf ("Killing all active slots (and recording side effect) because of inst ");
 693                                         mono_print_tree_nl (tree);
 694                                 }
 695                                 /* Note that this does *not* dispose ready moves (state [U]) */
 696                                 tree_mover_kill_act_for_indirect_local_definition (tree_mover, acp_size);
 697                                 tree_mover->tree_has_side_effects = TRUE;
 698                         }
 699                         return;
 700                 }
 701
 702                 break;
 703         case CEE_CALL:
 704         case OP_CALL_REG:
 705         case CEE_CALLVIRT:
 706         case OP_LCALL_REG:
 707         case OP_LCALLVIRT:
 708         case OP_LCALL:
 709         case OP_FCALL_REG:
 710         case OP_FCALLVIRT:
 711         case OP_FCALL:
 712         case OP_VCALL_REG:
 713         case OP_VCALLVIRT:
 714         case OP_VCALL:
 715         case OP_VOIDCALL_REG:
 716         case OP_VOIDCALLVIRT:
 717         case OP_VOIDCALL: {
 718                 MonoCallInst *call = (MonoCallInst *)tree;
 719                 MonoMethodSignature *sig = call->signature;
 720                 int i, byref = FALSE;
 721
 722                 if (tree_mover != NULL) {
 723                         if (MONO_DEBUG_TREE_MOVER) {
 724                                 printf ("Recording side effect because of inst ");
 725                                 mono_print_tree_nl (tree);
 726                         }
 727                         tree_mover->tree_has_side_effects = TRUE;
 728                 }
 729
 730                 for (i = 0; i < sig->param_count; i++) {
 731                         if (sig->params [i]->byref) {
 732                                 byref = TRUE;
 733                                 break;
 734                         }
 735                 }
 736
 737                 if (byref) {
 738                         if (MONO_DEBUG_LOCAL_PROP) {
 739                                 printf ("Call with byref parameter clears ACP at tree ");
 740                                 mono_print_tree (tree);
 741                                 printf ("\n");
 742                         }
 743                         memset (acp, 0, sizeof (MonoInst *) * acp_size);
 744                         if (tree_mover != NULL) {
 745                                 if (MONO_DEBUG_TREE_MOVER) {
 746                                         printf ("Killing all active slots because of inst ");
 747                                         mono_print_tree_nl (tree);
 748                                 }
 749                                 tree_mover_kill_act_for_indirect_use (tree_mover, acp_size);
 750                         }
 751                 } else {
 752                         if (tree_mover != NULL) {
 753                                 if (MONO_DEBUG_TREE_MOVER) {
 754                                         printf ("Killing all active slots reading memory because of inst ");
 755                                         mono_print_tree_nl (tree);
 756                                 }
 757                                 tree_mover_kill_act_for_indirect_global_definition (tree_mover, acp_size);
 758                         }
 759                 }
 760                 return;
 761         }
 762 #define TREEMOVE_SPECIFIC_OPS 1
 763 #define OPDEF(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10) case a1:
 764 #include "simple-cee-ops.h"
 765 #undef OPDEF
 766 #define MINI_OP(a1,a2) case a1:
 767 #include "simple-mini-ops.h"
 768 #undef MINI_OP
 769 #undef TREEMOVE_SPECIFIC_OPS
 770                 break;
 771         default:
 772                 if (tree_mover != NULL) {
 773                         if (MONO_DEBUG_TREE_MOVER) {
 774                                 printf ("Recording side effect because of inst ");
 775                                 mono_print_tree_nl (tree);
 776                         }
 777                         tree_mover->tree_has_side_effects = TRUE;
 778                 }
 779                 break;
 780         }
 781
 782         arity = mono_burg_arity [tree->opcode];
 783
 784         switch (arity) {
 785         case 0:
 786                 break;
 787         case 1:
 788                 mono_cprop_invalidate_values (tree->inst_i0, tree_mover, acp, acp_size);
 789                 break;
 790         case 2:
 791                 mono_cprop_invalidate_values (tree->inst_i0, tree_mover, acp, acp_size);
 792                 mono_cprop_invalidate_values (tree->inst_i1, tree_mover, acp, acp_size);
 793                 break;
 794         default:
 795                 g_assert_not_reached ();
 796         }
 797 }
 798
 799 static void
 800 mono_local_cprop_bb (MonoCompile *cfg, TreeMover *tree_mover, MonoBasicBlock *bb, MonoInst **acp, int acp_size)
 801 {
 802         MonoInst *tree = bb->code;
 803         int i;
 804
 805         if (!tree)
 806                 return;
 807
 808         if (tree_mover != NULL) {
 809                 tree_mover_set_waiting_flags (tree_mover, acp_size);
 810                 if (MONO_DEBUG_TREE_MOVER) {
 811                         printf ("Running tree mover on BB%d\n", bb->block_num);
 812                 }
 813         }
 814         for (; tree; tree = tree->next) {
 815                 if (tree_mover != NULL) {
 816                         if (MONO_DEBUG_TREE_MOVER) {
 817                                 printf ("Running tree mover on tree ");
 818                                 mono_print_tree_nl (tree);
 819                         }
 820                         tree_mover->tree_has_side_effects = FALSE;
 821                         tree_mover->tree_reads_memory = FALSE;
 822                 }
 823
 824                 mono_cprop_copy_values (cfg, tree_mover, tree, acp);
 825                 mono_cprop_invalidate_values (tree, tree_mover, acp, acp_size);
 826                 if (MONO_DEBUG_TREE_MOVER) {
 827                         if (tree_mover != NULL) {
 828                                 printf ("After the tree walk, tree_mover->tree_has_side_effects is %d\n", tree_mover->tree_has_side_effects);
 829                         }
 830                 }
 831
 832                 if (tree->ssa_op == MONO_SSA_STORE  &&
 833                     (tree->inst_i0->opcode == OP_LOCAL || tree->inst_i0->opcode == OP_ARG)) {
 834                         MonoInst *i1 = tree->inst_i1;
 835                         TreeMoverActSlot *forwarding_source = NULL;
 836                         gboolean tree_can_be_moved = TRUE;
 837
 838                         acp [tree->inst_i0->inst_c0] = NULL;
 839                         if (MONO_DEBUG_TREE_MOVER) {
 840                                 printf ("Assignment clears ACP[%d] at tree ", tree->inst_i0->inst_c0);
 841                                 mono_print_tree (tree);
 842                                 printf ("\n");
 843                         }
 844
 845                         for (i = 0; i < acp_size; i++) {
 846                                 if (acp [i] && acp [i]->opcode != OP_ICONST &&
 847                                     acp [i]->inst_c0 == tree->inst_i0->inst_c0) {
 848                                         acp [i] = NULL;
 849                                         if (MONO_DEBUG_LOCAL_PROP) {
 850                                                 printf ("  Consequently, ACP[%d] is cleared\n", i);
 851                                         }
 852                                 }
 853                         }
 854
 855                         if (i1->opcode == OP_ICONST) {
 856                                 acp [tree->inst_i0->inst_c0] = i1;
 857                                 tree_can_be_moved = FALSE;
 858                                 if (MONO_DEBUG_LOCAL_PROP) {
 859                                         printf ("  Consequently, ACP[%d] becomes constant ", tree->inst_i0->inst_c0);
 860                                         mono_print_tree (i1);
 861                                         printf ("\n");
 862                                 }
 863                                 //printf ("DEF1 BB%d %d\n", bb->block_num,tree->inst_i0->inst_c0);
 864                         } else if ((i1->type==STACK_I8) || (i1->opcode==OP_I8CONST) || (i1->opcode==OP_R4CONST) || (i1->opcode==OP_R8CONST) || (i1->opcode==OP_AOTCONST)) {
 865                                 tree_can_be_moved = FALSE;
 866                                 if (MONO_DEBUG_TREE_MOVER) {
 867                                         printf ("Preventing move of constant or long value ");
 868                                         mono_print_tree (i1);
 869                                         printf ("\n");
 870                                 }
 871                         }
 872                         if (i1->ssa_op == MONO_SSA_LOAD &&
 873                             (i1->inst_i0->opcode == OP_LOCAL || i1->inst_i0->opcode == OP_ARG) &&
 874                             (i1->inst_i0->inst_c0 != tree->inst_i0->inst_c0)) {
 875                                 acp [tree->inst_i0->inst_c0] = i1->inst_i0;
 876                                 tree_can_be_moved = FALSE;
 877                                 if (MONO_DEBUG_LOCAL_PROP) {
 878                                         printf ("  Consequently, ACP[%d] becomes local ", tree->inst_i0->inst_c0);
 879                                         mono_print_tree (i1->inst_i0);
 880                                         printf ("\n");
 881                                 }
 882                                 if (tree_mover != NULL) {
 883                                         /* Examine the variable *used* in this definition (the "source") */
 884                                         forwarding_source = tree_mover_slot_from_index (tree_mover, i1->inst_i0->inst_c0);
 885                                         /* Check if source slot is ready to be forwarded */
 886                                         if ((! forwarding_source->pending_move_is_ready) || (forwarding_source->pending_move->prevent_forwarding)) {
 887                                                 /* no forwarding is possible, do nothing */
 888                                                 forwarding_source = NULL;
 889                                         }
 890                                 }
 891                                 //printf ("DEF2 BB%d %d %d\n", bb->block_num,tree->inst_i0->inst_c0,i1->inst_i0->inst_c0);
 892                         }
 893
 894                         /* Apply tree mover */
 895                         if (tree_mover != NULL) {
 896                                 guint defined_index = tree->inst_i0->inst_c0;
 897                                 TreeMoverActSlot *defined_slot = tree_mover_slot_from_index (tree_mover, defined_index);
 898                                 TreeMoverDependencyNode *affected_node;
 899
 900                                 /* First clear the waiting flag... */
 901                                 defined_slot->waiting_flag = FALSE;
 902                                 /* ...and kill this slot (but recording any pending move)*/
 903                                 tree_mover_kill_act_slot_for_definition (tree_mover, defined_slot);
 904                                 if (MONO_DEBUG_TREE_MOVER) {
 905                                         printf ("Definition is clearing slot %d\n", defined_index);
 906                                 }
 907
 908                                 /* Handle "used" nodes... */
 909                                 /* Check if this is a forwarding */
 910                                 if (forwarding_source == NULL) {
 911                                         /* Normal case, no forwarding: */
 912                                         /* Check that consprop or copyprop did not already do the job, */
 913                                         /* and that the tree has no side effects */
 914                                         if (tree_can_be_moved && ! tree_mover->tree_has_side_effects) {
 915                                                 TreeMoverDependencyNode *affecting_node;
 916                                                 if (MONO_DEBUG_TREE_MOVER) {
 917                                                         printf ("Recording definition of slot %d by tree: ", defined_index);
 918                                                         mono_print_tree_nl (tree);
 919                                                 }
 920
 921                                                 /* Then apply the definition */
 922                                                 tree_mover_new_slot_move (tree_mover, defined_slot);
 923                                                 defined_slot->pending_move->definition = tree;
 924                                                 defined_slot->pending_move->defined_slot = defined_slot;
 925                                                 defined_slot->pending_move->tree_reads_memory = tree_mover->tree_reads_memory;
 926
 927                                                 /* Setup "used nodes" list */
 928                                                 defined_slot->used_locals = tree_mover->used_nodes;
 929                                                 defined_slot->last_used_local = tree_mover->last_used_node;
 930                                                 tree_mover->used_nodes = NULL;
 931                                                 tree_mover->last_used_node = NULL;
 932                                                 /* Link used nodes to "affecting" slots (so affected variables are linked) */
 933                                                 /* This is needed *now* so that circular definitions are detected */
 934                                                 for (affecting_node = defined_slot->used_locals; affecting_node != NULL; affecting_node = affecting_node->next_used_local) {
 935                                                         tree_mover_link_affecting_node (affecting_node, defined_slot);
 936                                                 }
 937                                         } else if (MONO_DEBUG_TREE_MOVER) {
 938                                                 /* otherwise, do nothing */
 939                                                 printf ("Skipping definition of slot %d by tree: ", defined_index);
 940                                                 mono_print_tree_nl (tree);
 941                                         }
 942                                 } else {
 943                                         TreeMoverDependencyFromDeadDefinition *dependency;
 944                                         /* forwarding previous definition: */
 945                                         if (MONO_DEBUG_TREE_MOVER) {
 946                                                 printf ("Handling forwarding in slot %d for tree: ", defined_index);
 947                                                 mono_print_tree_nl (tree);
 948                                         }
 949                                         /* Setup slot for forwarding */
 950                                         defined_slot->pending_move = forwarding_source->pending_move;
 951                                         defined_slot->pending_move_is_forwarded = TRUE;
 952                                         /* Setup forwarding dependency node */
 953                                         dependency = mono_mempool_alloc0 (tree_mover->pool, sizeof (TreeMoverDependencyFromDeadDefinition));
 954                                         dependency->defined_slot = defined_slot;
 955                                         dependency->dead_definition = tree;
 956                                         dependency->next = defined_slot->pending_move->slots_that_must_be_safe;
 957                                         defined_slot->pending_move->slots_that_must_be_safe = dependency;
 958                                         /* Clear use (put slot back to state [D]) */
 959                                         defined_slot->pending_move->use = NULL;
 960                                         defined_slot->pending_move->defined_slot->pending_move_is_ready = FALSE;
 961                                 }
 962
 963                                 /* Then kill all affected definitions waiting for a use */
 964                                 affected_node = defined_slot->affected_locals;
 965                                 while (affected_node != NULL) {
 966                                         TreeMoverDependencyNode *next_affected_node = affected_node->next_affected_local;
 967                                         TreeMoverActSlot *affected_slot = affected_node->affected_slot;
 968
 969                                         if (affected_node->use_is_direct) {
 970                                                 /* Direct use: kill affected slot */
 971                                                 if (MONO_DEBUG_TREE_MOVER) {
 972                                                         printf ("  Direct use, killing slot %d with definition:", tree_mover_slot_to_index (tree_mover, affected_node->affected_slot));
 973                                                         mono_print_tree_nl (affected_slot->pending_move->definition);
 974                                                 }
 975                                                 tree_mover_kill_act_slot_because_it_is_affected (tree_mover, affected_slot);
 976                                         } else if ((defined_slot->pending_move!= NULL) &&
 977                                                         (! defined_slot->pending_move_is_ready) &&
 978                                                         (! defined_slot->pending_move_is_forwarded) &&
 979                                                         (affected_slot->pending_move!= NULL) &&
 980                                                         (! affected_slot->pending_move_is_ready) &&
 981                                                         (! affected_slot->pending_move_is_forwarded)) {
 982                                                 if (MONO_DEBUG_TREE_MOVER) {
 983                                                         printf ("  Indirect use, linking slots %d and %d\n", tree_mover_slot_to_index (tree_mover, affected_node->used_slot), tree_mover_slot_to_index (tree_mover, affected_node->affected_slot));
 984                                                 }
 985                                                 tree_mover_link_affected_moves (tree_mover, defined_slot, affected_slot);
 986                                                 tree_mover_link_affected_moves (tree_mover, affected_slot, defined_slot);
 987                                         }
 988                                         tree_mover_unlink_affecting_node (affected_node);
 989
 990                                         if ((next_affected_node != NULL) && (next_affected_node->affected_slot != NULL)) {
 991                                                 affected_node = next_affected_node;
 992                                         } else {
 993                                                 affected_node = defined_slot->affected_locals;
 994                                         }
 995                                 }
 996                                 if (MONO_DUMP_TREE_MOVER) {
 997                                         tree_mover_print_act_slot ("DEFINITION", tree_mover, defined_slot);
 998                                 }
 999                         }
1000                 }
1001
1002                 /* After we are done with this tree, clear the tree mover area */
1003                 if ((tree_mover != NULL) && (tree_mover->used_nodes != NULL)) {
1004                         tree_mover_dispose_used_nodes (tree_mover);
1005                 }
1006
1007                 /*
1008                   if (tree->opcode == CEE_BEQ) {
1009                   g_assert (tree->inst_i0->opcode == OP_COMPARE);
1010                   if (tree->inst_i0->inst_i0->opcode == OP_ICONST &&
1011                   tree->inst_i0->inst_i1->opcode == OP_ICONST) {
1012
1013                   tree->opcode = CEE_BR;
1014                   if (tree->inst_i0->inst_i0->opcode == tree->inst_i0->inst_i1->opcode) {
1015                   tree->inst_target_bb = tree->inst_true_bb;
1016                   } else {
1017                   tree->inst_target_bb = tree->inst_false_bb;
1018                   }
1019                   }
1020                   }
1021                 */
1022         }
1023
1024         if (tree_mover != NULL) {
1025                 /* At BB end, kill all definitions still waiting for a use */
1026                 tree_mover_clear_act_recording_moves (tree_mover, acp_size);
1027                 if (MONO_DEBUG_TREE_MOVER) {
1028                         tree_mover_verify_dependency_nodes_are_clear (tree_mover, acp_size);
1029                 }
1030         }
1031 }
1032
1033
1034 #if (MONO_APPLY_TREE_MOVER_TO_SINGLE_METHOD)
1035 static char*
1036 mono_tree_mover_method_name = NULL;
1037 static gboolean check_tree_mover_method_name (MonoCompile *cfg) {
1038         if (mono_tree_mover_method_name == NULL) {
1039                 mono_tree_mover_method_name = getenv ("MONO_TREE_MOVER_METHOD_NAME");
1040         }
1041         if (mono_tree_mover_method_name != NULL) {
1042                 char *method_name = mono_method_full_name (cfg->method, TRUE);
1043                 if (strstr (method_name, mono_tree_mover_method_name) != NULL) {
1044                         g_free (method_name);
1045                         return TRUE;
1046                 } else {
1047                         g_free (method_name);
1048                         return FALSE;
1049                 }
1050         } else {
1051                 return TRUE;
1052         }
1053 }
1054 #endif
1055
1056 #if (MONO_APPLY_TREE_MOVER_TO_COUNTED_METHODS)
1057 static int
1058 mono_tree_mover_method_limit = -1;
1059 static int
1060 mono_tree_mover_method_count = 0;
1061 static gboolean check_tree_mover_method_count (MonoCompile *cfg) {
1062         if (mono_tree_mover_method_limit == -1) {
1063                 char *limit_string = getenv ("MONO_TREE_MOVER_METHOD_LIMIT");
1064                 if (limit_string != NULL) {
1065                         mono_tree_mover_method_limit = atoi (limit_string);
1066                 } else {
1067                         mono_tree_mover_method_limit = -2;
1068                 }
1069         }
1070         if (mono_tree_mover_method_limit > -1) {
1071                 mono_tree_mover_method_count ++;
1072                 if (mono_tree_mover_method_count == mono_tree_mover_method_limit) {
1073                         char *method_name = mono_method_full_name (cfg->method, TRUE);
1074                         printf ("Last method compiled with treeprop: %s\n", method_name);
1075                         g_free (method_name);
1076
1077                 }
1078                 return (mono_tree_mover_method_count <= mono_tree_mover_method_limit);
1079         } else {
1080                 return TRUE;
1081         }
1082 }
1083 #endif
1084
1085 static void
1086 apply_tree_mover (TreeMover *tree_mover, TreeMoverTreeMove *move) {
1087         TreeMoverDependencyFromDeadDefinition *dependency;
1088         TreeMoverAffectedMove *affected_move;
1089
1090         /* Test if this move has been explicitly disabled */
1091         if (move->skip_this_move) {
1092                 if (MONO_DEBUG_TREE_MOVER) {
1093                         printf ("Move of slot %d must be skipped: ", tree_mover_slot_to_index (tree_mover, move->defined_slot));
1094                         mono_print_tree_nl (move->definition);
1095                 }
1096                 return;
1097         }
1098         /* Test if this move is safe */
1099         if ((! move->move_is_safe) && move->defined_slot->unsafe_flag) {
1100                 if (MONO_DEBUG_TREE_MOVER) {
1101                         printf ("Move of slot %d is unsafe: ", tree_mover_slot_to_index (tree_mover, move->defined_slot));
1102                         mono_print_tree_nl (move->definition);
1103                 }
1104                 return;
1105         }
1106         /* Test if this move depends from a definition that should have been dead */
1107         for (dependency = move->slots_that_must_be_safe; dependency != NULL; dependency = dependency->next) {
1108                 if ((dependency->defined_slot != NULL) && dependency->defined_slot->unsafe_flag) {
1109                         if (MONO_DEBUG_TREE_MOVER) {
1110                                 printf ("Move of slot %d depended from unsafe slot %d: ", tree_mover_slot_to_index (tree_mover, move->defined_slot), tree_mover_slot_to_index (tree_mover, dependency->defined_slot));
1111                                 mono_print_tree_nl (move->definition);
1112                         }
1113                         return;
1114                 }
1115         }
1116
1117         if (MONO_DEBUG_TREE_MOVER) {
1118                 printf ("Performing move of slot %d: ", tree_mover_slot_to_index (tree_mover, move->defined_slot));
1119                 mono_print_tree_nl (move->definition);
1120         }
1121         /* All tests passed, apply move */
1122         *(move->use) = move->definition->inst_i1;
1123         move->definition->opcode = CEE_NOP;
1124         move->definition->ssa_op = MONO_SSA_NOP;
1125
1126         /* Then disable moves affected by this move */
1127         affected_move = move->affected_moves;
1128         while (affected_move != NULL) {
1129                 if (MONO_DEBUG_TREE_MOVER) {
1130                         printf ("  Consequently, disabling slot %d\n", tree_mover_slot_to_index (tree_mover, affected_move->affected_move->defined_slot));
1131                 }
1132                 affected_move->affected_move->skip_this_move = TRUE;
1133                 affected_move = affected_move->next_affected_move;
1134         }
1135
1136         /* Also kill dead dependency definitions */
1137         for (dependency = move->slots_that_must_be_safe; dependency != NULL; dependency = dependency->next) {
1138                 if (dependency->defined_slot != NULL) {
1139                         if (MONO_DEBUG_TREE_MOVER) {
1140                                 printf ("  Consequently, kill dependent definition %d: ", tree_mover_slot_to_index (tree_mover, dependency->defined_slot));
1141                                 mono_print_tree_nl (dependency->dead_definition);
1142                         }
1143                         dependency->dead_definition->opcode = CEE_NOP;
1144                         dependency->dead_definition->ssa_op = MONO_SSA_NOP;
1145                 }
1146         }
1147 }
1148
1149 void
1150 mono_local_cprop (MonoCompile *cfg) {
1151         MonoBasicBlock *bb;
1152         MonoInst **acp;
1153         TreeMover *tree_mover;
1154
1155         acp = alloca (sizeof (MonoInst *) * cfg->num_varinfo);
1156
1157         if (cfg->opt & MONO_OPT_TREEPROP) {
1158                 MonoMemPool *pool = mono_mempool_new();
1159                 tree_mover = mono_mempool_alloc0(pool, sizeof (TreeMover));
1160
1161                 tree_mover->cfg = cfg;
1162                 tree_mover->pool = pool;
1163                 tree_mover->ACT = mono_mempool_alloc0 (pool, sizeof (TreeMoverActSlot) * (cfg->num_varinfo));
1164 #if (MONO_APPLY_TREE_MOVER_TO_SINGLE_METHOD)
1165                 if (! check_tree_mover_method_name (cfg)) {
1166                         mono_mempool_destroy(tree_mover->pool);
1167                         tree_mover = NULL;
1168                 }
1169 #endif
1170 #if (MONO_APPLY_TREE_MOVER_TO_COUNTED_METHODS)
1171                 if (! check_tree_mover_method_count (cfg)) {
1172                         mono_mempool_destroy(tree_mover->pool);
1173                         tree_mover = NULL;
1174                 }
1175 #endif
1176         } else {
1177                 tree_mover = NULL;
1178         }
1179
1180         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
1181                 if (MONO_DEBUG_LOCAL_PROP||MONO_DEBUG_TREE_MOVER) {
1182                         printf ("Applying mono_local_cprop to BB%d\n", bb->block_num);
1183                 }
1184                 memset (acp, 0, sizeof (MonoInst *) * cfg->num_varinfo);
1185                 mono_local_cprop_bb (cfg, tree_mover, bb, acp, cfg->num_varinfo);
1186         }
1187
1188         if (tree_mover != NULL) {
1189                 TreeMoverTreeMove *move;
1190                 /* Move the movable trees */
1191                 if (MONO_DEBUG_TREE_MOVER) {
1192                         printf ("BEFORE TREE MOVER START\n");
1193                         mono_print_code (cfg);
1194                         printf ("BEFORE TREE MOVER END\n");
1195                         printf ("Applying tree mover...\n");
1196                 }
1197                 for (move = tree_mover->scheduled_moves; move != NULL; move = move->next) {
1198                         apply_tree_mover (tree_mover, move);
1199                 }
1200                 if (MONO_DEBUG_TREE_MOVER) {
1201                         printf ("AFTER TREE MOVER START\n");
1202                         mono_print_code (cfg);
1203                         printf ("AFTER TREE MOVER END\n");
1204                 }
1205
1206                 /* Global cleanup of tree mover memory */
1207                 mono_mempool_destroy(tree_mover->pool);
1208         }
1209 }