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                         MonoType *inst_i0_underlying_type = mono_type_get_underlying_type (tree->inst_i0->inst_vtype);
 497                         MonoType *cp_underlying_type = mono_type_get_underlying_type (cp->inst_vtype);
 498                         if ((inst_i0_underlying_type->type == cp_underlying_type->type) ||
 499                             (tree->type == STACK_OBJ) || (tree->type == STACK_MP)) {
 500                                 if (cfg->opt & MONO_OPT_COPYPROP) {
 501                                         //{ static int c = 0; printf ("VCOPY %d\n", ++c); }
 502                                         if (MONO_DEBUG_LOCAL_PROP) {
 503                                                 printf ("Propagating value, tree->inst_i0 ");
 504                                                 mono_print_tree (tree->inst_i0);
 505                                                 printf (" becomes ");
 506                                                 mono_print_tree (cp);
 507                                                 printf ("\n");
 508                                         }
 509                                         tree->inst_i0 = cp;
 510                                 }
 511                         } else if (MONO_DEBUG_LOCAL_PROP) {
 512                                 char* tree_type_name = mono_type_full_name (tree->inst_i0->inst_vtype);
 513                                 char* cp_type_name = mono_type_full_name (cp->inst_vtype);
 514                                 printf ("Values of tree->inst_i0 ");
 515                                 mono_print_tree (tree->inst_i0);
 516                                 printf (" and cp ");
 517                                 mono_print_tree (cp);
 518                                 printf (" have incompatible types in tree ");
 519                                 mono_print_tree (tree);
 520                                 printf ("\n");
 521                                 printf (" MonoType of tree->inst_i0 is: %s\n", tree_type_name);
 522                                 printf (" MonoType of cp is: %s\n", cp_type_name);
 523                                 g_free (tree_type_name);
 524                                 g_free (cp_type_name);
 525                         }
 526                 }
 527         } else {
 528                 if (MONO_DEBUG_LOCAL_PROP) {
 529                         printf ("Propagation SKIPPED for inst ");
 530                         mono_print_tree (tree);
 531                         printf ("\n");
 532                 }
 533                 if ((tree_mover != NULL) && (cfg->opt & MONO_OPT_CFOLD))
 534                         mono_constant_fold_inst (tree, NULL);
 535
 536                 arity = mono_burg_arity [tree->opcode];
 537
 538                 if (arity) {
 539                         TreeMoverTreeMove *result = mono_cprop_copy_values (cfg, tree_mover, tree->inst_i0, acp);
 540                         if (cfg->opt & MONO_OPT_CFOLD)
 541                                 mono_constant_fold_inst (tree, NULL);
 542                         if (result != NULL) {
 543                                 result->use = &(tree->inst_i0);
 544                                 //printf (" SETTING inst_i0[%p] USE to %p (definition is %p)\n", tree, result->use, result->definition);
 545
 546                         }
 547                         /* The opcode may have changed */
 548                         if (mono_burg_arity [tree->opcode] > 1) {
 549                                 if (cfg->opt & MONO_OPT_CFOLD)
 550                                         mono_constant_fold_inst (tree, NULL);
 551                                 result = mono_cprop_copy_values (cfg, tree_mover, tree->inst_i1, acp);
 552                                 if (result != NULL) {
 553                                         result->use = &(tree->inst_i1);
 554                                         //printf (" SETTING inst_i1[%p] USE to %p (definition is %p)\n", tree, result->use, result->definition);
 555                                 }
 556                         }
 557                         mono_constant_fold_inst (tree, NULL);
 558                 }
 559         }
 560
 561         /* Apply the tree mover after after propagation has been done */
 562         if ((tree_mover != NULL) && (tree->ssa_op == MONO_SSA_LOAD) &&
 563                         (tree->inst_i0->opcode == OP_LOCAL || tree->inst_i0->opcode == OP_ARG)) {
 564                 guint used_index = tree->inst_i0->inst_c0;
 565                 TreeMoverActSlot *used_slot = &(tree_mover->ACT [used_index]);
 566
 567                 /* First, handle waiting flag */
 568                 if (used_slot->waiting_flag) {
 569                         used_slot->unsafe_flag = TRUE;
 570                         used_slot->waiting_flag = FALSE;
 571                 }
 572
 573                 if (!tree->inst_i0->flags) {
 574                         /* Record local use (the tree that contains this use might be movable) */
 575                         tree_mover_add_used_node (tree_mover, used_slot, TRUE);
 576
 577                         /* Start working on the pending move... */
 578                         pending_move = used_slot->pending_move;
 579
 580                         /* If there *is* a pending move... (otherwise, do nothing) */
 581                         if (pending_move != NULL) {
 582                                 /* Check slot state */
 583                                 if (used_slot->pending_move_is_forwarded) {
 584                                         /* If the slot was a "hopefully dead" definition because of a forwarding... */
 585                                         if (MONO_DEBUG_TREE_MOVER) {
 586                                                 printf ("Use should have been dead, killing slot %d: ", used_index);
 587                                                 mono_print_tree_nl (tree);
 588                                                 printf ("Also disabling forwarded definition at slot %d: ", tree_mover_slot_to_index (tree_mover, pending_move->defined_slot));
 589                                                 mono_print_tree_nl (pending_move->definition);
 590                                         }
 591                                         /* ...clear the slot (which also disables the forwarded definition), and... */
 592                                         tree_mover_kill_act_slot_for_use (tree_mover, used_slot);
 593                                         /* ...clear the pending_move */
 594                                         pending_move = NULL;
 595                                 } else if (used_slot->pending_move_is_ready ||
 596                                                 TREE_MOVER_STIND_NEEDS_CONVERSION (pending_move->definition->opcode, pending_move->definition->inst_i1->type) ||
 597                                                 TREE_MOVER_LDIND_NEEDS_CONVERSION (tree->opcode, pending_move->definition->inst_i1->type)) {
 598                                         /* If the move was already in state [U], or if there are type problems... */
 599                                         if (MONO_DEBUG_TREE_MOVER) {
 600                                                 printf ("Definition has too many, wrong or misplaced uses, killing slot %d: ", used_index);
 601                                                 mono_print_tree_nl (tree);
 602                                         }
 603                                         /* ...kill it, and clear the pending_move */
 604                                         tree_mover_kill_act_slot_for_use (tree_mover, used_slot);
 605                                         pending_move = NULL;
 606                                 } else {
 607                                         /* All goes well: set slot state to [U] */
 608                                         TreeMoverDependencyNode *node = used_slot->used_locals;
 609                                         if (MONO_DEBUG_TREE_MOVER) {
 610                                                 printf ("Setting tree move for slot %d as ready: ", used_index);
 611                                                 mono_print_tree_nl (tree);
 612                                         }
 613                                         /* Record indirect uses generated by this move */
 614                                         while (node != NULL) {
 615                                                 tree_mover_add_used_node (tree_mover, node->used_slot, FALSE);
 616                                                 node = node->next_used_local;
 617                                         }
 618
 619                                         /* Setup tree as movable */
 620                                         used_slot->pending_move_is_ready = TRUE;
 621                                 }
 622                         }
 623                 } else {
 624                         if (MONO_DEBUG_TREE_MOVER) {
 625                                 printf ("Tree has side effects, killing slot %d: ", used_index);
 626                                 mono_print_tree_nl (tree);
 627                         }
 628                         /* The whole tree is unmovable (it uses a flagged local) */
 629                         tree_mover->tree_has_side_effects = TRUE;
 630                         /* Moreover, the use of a flagged local kills the definition */
 631                         tree_mover_kill_act_slot_for_use (tree_mover, used_slot);
 632                 }
 633 #if MONO_DUMP_TREE_MOVER
 634                 tree_mover_print_act_slot ("USE", tree_mover, used_slot);
 635 #endif
 636         }
 637         return pending_move;
 638 }
 639
 640 static void
 641 mono_cprop_invalidate_values (MonoInst *tree, TreeMover *tree_mover, MonoInst **acp, int acp_size)
 642 {
 643         int arity;
 644
 645         if (tree_mover != NULL) {
 646                 if ((tree->opcode == CEE_NEWARR) || (mono_find_jit_opcode_emulation (tree->opcode) != NULL)) {
 647                         if (MONO_DEBUG_TREE_MOVER) {
 648                                 printf ("Recording side effect because emulated opcode cannot be moved: ");
 649                                 mono_print_tree_nl (tree);
 650                         }
 651                         tree_mover->tree_has_side_effects = TRUE;
 652                 }
 653         }
 654
 655         switch (tree->opcode) {
 656         case CEE_LDIND_REF:
 657         case CEE_LDIND_I1:
 658         case CEE_LDIND_I2:
 659         case CEE_LDIND_I4:
 660         case CEE_LDIND_U1:
 661         case CEE_LDIND_U2:
 662         case CEE_LDIND_U4:
 663         case CEE_LDIND_I8:
 664         case CEE_LDIND_R4:
 665         case CEE_LDIND_R8:
 666         case CEE_LDIND_I:
 667         case CEE_LDOBJ:
 668                 if ((tree_mover != NULL) && ((tree->ssa_op == MONO_SSA_NOP) || (tree->ssa_op & MONO_SSA_ADDRESS_TAKEN))) {
 669                         if (MONO_DEBUG_TREE_MOVER) {
 670                                 printf ("Recording memory read at inst: ");
 671                                 mono_print_tree_nl (tree);
 672                         }
 673                         tree_mover->tree_reads_memory = TRUE;
 674                 }
 675                 break;
 676         case CEE_STIND_I:
 677         case CEE_STIND_I1:
 678         case CEE_STIND_I2:
 679         case CEE_STIND_I4:
 680         case CEE_STIND_REF:
 681         case CEE_STIND_I8:
 682         case CEE_STIND_R4:
 683         case CEE_STIND_R8:
 684         case CEE_STOBJ:
 685                 if ((tree->ssa_op == MONO_SSA_NOP) || (tree->ssa_op & MONO_SSA_ADDRESS_TAKEN)) {
 686                         if (MONO_DEBUG_LOCAL_PROP) {
 687                                 printf ("Indirect store clears ACP at tree ");
 688                                 mono_print_tree (tree);
 689                                 printf ("\n");
 690                         }
 691                         memset (acp, 0, sizeof (MonoInst *) * acp_size);
 692                         if (tree_mover != NULL) {
 693                                 if (MONO_DEBUG_TREE_MOVER) {
 694                                         printf ("Killing all active slots (and recording side effect) because of inst ");
 695                                         mono_print_tree_nl (tree);
 696                                 }
 697                                 /* Note that this does *not* dispose ready moves (state [U]) */
 698                                 tree_mover_kill_act_for_indirect_local_definition (tree_mover, acp_size);
 699                                 tree_mover->tree_has_side_effects = TRUE;
 700                         }
 701                         return;
 702                 }
 703
 704                 break;
 705         case OP_CALL:
 706         case OP_CALL_REG:
 707         case OP_CALLVIRT:
 708         case OP_LCALL_REG:
 709         case OP_LCALLVIRT:
 710         case OP_LCALL:
 711         case OP_FCALL_REG:
 712         case OP_FCALLVIRT:
 713         case OP_FCALL:
 714         case OP_VCALL_REG:
 715         case OP_VCALLVIRT:
 716         case OP_VCALL:
 717         case OP_VOIDCALL_REG:
 718         case OP_VOIDCALLVIRT:
 719         case OP_VOIDCALL:
 720         case OP_TRAMPCALL_VTABLE:
 721         case OP_CALL_RGCTX:
 722         case OP_FCALL_RGCTX:
 723         case OP_VOIDCALL_RGCTX:
 724         case OP_LCALL_RGCTX:
 725         case OP_VCALL_RGCTX:
 726         case OP_CALL_REG_RGCTX:
 727         case OP_FCALL_REG_RGCTX:
 728         case OP_VOIDCALL_REG_RGCTX:
 729         case OP_LCALL_REG_RGCTX:
 730         case OP_VCALL_REG_RGCTX:
 731         case OP_CALLVIRT_IMT:
 732         case OP_VOIDCALLVIRT_IMT:
 733         case OP_FCALLVIRT_IMT:
 734         case OP_LCALLVIRT_IMT:
 735         case OP_VCALLVIRT_IMT: {
 736                 MonoCallInst *call = (MonoCallInst *)tree;
 737                 MonoMethodSignature *sig = call->signature;
 738                 int i, byref = FALSE;
 739
 740                 if (tree_mover != NULL) {
 741                         if (MONO_DEBUG_TREE_MOVER) {
 742                                 printf ("Recording side effect because of inst ");
 743                                 mono_print_tree_nl (tree);
 744                         }
 745                         tree_mover->tree_has_side_effects = TRUE;
 746                 }
 747
 748                 for (i = 0; i < sig->param_count; i++) {
 749                         if (sig->params [i]->byref) {
 750                                 byref = TRUE;
 751                                 break;
 752                         }
 753                 }
 754
 755                 if (byref) {
 756                         if (MONO_DEBUG_LOCAL_PROP) {
 757                                 printf ("Call with byref parameter clears ACP at tree ");
 758                                 mono_print_tree (tree);
 759                                 printf ("\n");
 760                         }
 761                         memset (acp, 0, sizeof (MonoInst *) * acp_size);
 762                         if (tree_mover != NULL) {
 763                                 if (MONO_DEBUG_TREE_MOVER) {
 764                                         printf ("Killing all active slots because of inst ");
 765                                         mono_print_tree_nl (tree);
 766                                 }
 767                                 tree_mover_kill_act_for_indirect_use (tree_mover, acp_size);
 768                         }
 769                 } else {
 770                         if (tree_mover != NULL) {
 771                                 if (MONO_DEBUG_TREE_MOVER) {
 772                                         printf ("Killing all active slots reading memory because of inst ");
 773                                         mono_print_tree_nl (tree);
 774                                 }
 775                                 tree_mover_kill_act_for_indirect_global_definition (tree_mover, acp_size);
 776                         }
 777                 }
 778                 return;
 779         }
 780 #define TREEMOVE_SPECIFIC_OPS 1
 781 #define OPDEF(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10) case a1:
 782 #include "simple-cee-ops.h"
 783 #undef OPDEF
 784 #define MINI_OP(a1,a2) case a1:
 785 #include "simple-mini-ops.h"
 786 #undef MINI_OP
 787 #undef TREEMOVE_SPECIFIC_OPS
 788                 break;
 789         default:
 790                 if (tree_mover != NULL) {
 791                         if (MONO_DEBUG_TREE_MOVER) {
 792                                 printf ("Recording side effect because of inst ");
 793                                 mono_print_tree_nl (tree);
 794                         }
 795                         tree_mover->tree_has_side_effects = TRUE;
 796                 }
 797                 break;
 798         }
 799
 800         arity = mono_burg_arity [tree->opcode];
 801
 802         switch (arity) {
 803         case 0:
 804                 break;
 805         case 1:
 806                 mono_cprop_invalidate_values (tree->inst_i0, tree_mover, acp, acp_size);
 807                 break;
 808         case 2:
 809                 mono_cprop_invalidate_values (tree->inst_i0, tree_mover, acp, acp_size);
 810                 mono_cprop_invalidate_values (tree->inst_i1, tree_mover, acp, acp_size);
 811                 break;
 812         default:
 813                 g_assert_not_reached ();
 814         }
 815 }
 816
 817 static void
 818 mono_local_cprop_bb (MonoCompile *cfg, TreeMover *tree_mover, MonoBasicBlock *bb, MonoInst **acp, int acp_size)
 819 {
 820         MonoInst *tree;
 821         int i;
 822
 823         if (MONO_INST_LIST_EMPTY (&bb->ins_list))
 824                 return;
 825
 826         if (tree_mover != NULL) {
 827                 tree_mover_set_waiting_flags (tree_mover, acp_size);
 828                 if (MONO_DEBUG_TREE_MOVER) {
 829                         printf ("Running tree mover on BB%d\n", bb->block_num);
 830                 }
 831         }
 832         MONO_BB_FOR_EACH_INS (bb, tree) {
 833                 if (tree_mover != NULL) {
 834                         if (MONO_DEBUG_TREE_MOVER) {
 835                                 printf ("Running tree mover on tree ");
 836                                 mono_print_tree_nl (tree);
 837                         }
 838                         tree_mover->tree_has_side_effects = FALSE;
 839                         tree_mover->tree_reads_memory = FALSE;
 840                 }
 841
 842                 mono_cprop_copy_values (cfg, tree_mover, tree, acp);
 843                 mono_cprop_invalidate_values (tree, tree_mover, acp, acp_size);
 844                 if (MONO_DEBUG_TREE_MOVER) {
 845                         if (tree_mover != NULL) {
 846                                 printf ("After the tree walk, tree_mover->tree_has_side_effects is %d\n", tree_mover->tree_has_side_effects);
 847                         }
 848                 }
 849
 850                 if (tree->ssa_op == MONO_SSA_STORE  &&
 851                     (tree->inst_i0->opcode == OP_LOCAL || tree->inst_i0->opcode == OP_ARG)) {
 852                         MonoInst *i1 = tree->inst_i1;
 853                         TreeMoverActSlot *forwarding_source = NULL;
 854                         gboolean tree_can_be_moved = TRUE;
 855
 856                         acp [tree->inst_i0->inst_c0] = NULL;
 857                         if (MONO_DEBUG_TREE_MOVER) {
 858                                 printf ("Assignment clears ACP[%d] at tree ", tree->inst_i0->inst_c0);
 859                                 mono_print_tree (tree);
 860                                 printf ("\n");
 861                         }
 862
 863                         for (i = 0; i < acp_size; i++) {
 864                                 if (acp [i] && acp [i]->opcode != OP_ICONST &&
 865                                     acp [i]->inst_c0 == tree->inst_i0->inst_c0) {
 866                                         acp [i] = NULL;
 867                                         if (MONO_DEBUG_LOCAL_PROP) {
 868                                                 printf ("  Consequently, ACP[%d] is cleared\n", i);
 869                                         }
 870                                 }
 871                         }
 872
 873                         if (i1->opcode == OP_ICONST) {
 874                                 acp [tree->inst_i0->inst_c0] = i1;
 875                                 tree_can_be_moved = FALSE;
 876                                 if (MONO_DEBUG_LOCAL_PROP) {
 877                                         printf ("  Consequently, ACP[%ld] becomes constant ", (long)tree->inst_i0->inst_c0);
 878                                         mono_print_tree (i1);
 879                                         printf ("\n");
 880                                 }
 881                                 //printf ("DEF1 BB%d %d\n", bb->block_num,tree->inst_i0->inst_c0);
 882                         } else if ((i1->type==STACK_I8) || (i1->opcode==OP_I8CONST) || (i1->opcode==OP_R4CONST) || (i1->opcode==OP_R8CONST) || (i1->opcode==OP_AOTCONST)) {
 883                                 tree_can_be_moved = FALSE;
 884                                 if (MONO_DEBUG_TREE_MOVER) {
 885                                         printf ("Preventing move of constant or long value ");
 886                                         mono_print_tree (i1);
 887                                         printf ("\n");
 888                                 }
 889                         }
 890                         if (i1->ssa_op == MONO_SSA_LOAD &&
 891                             (i1->inst_i0->opcode == OP_LOCAL || i1->inst_i0->opcode == OP_ARG) &&
 892                             (i1->inst_i0->inst_c0 != tree->inst_i0->inst_c0)) {
 893                                 acp [tree->inst_i0->inst_c0] = i1->inst_i0;
 894                                 tree_can_be_moved = FALSE;
 895                                 if (MONO_DEBUG_LOCAL_PROP) {
 896                                         printf ("  Consequently, ACP[%d] becomes local ", tree->inst_i0->inst_c0);
 897                                         mono_print_tree (i1->inst_i0);
 898                                         printf ("\n");
 899                                 }
 900                                 if (tree_mover != NULL) {
 901                                         /* Examine the variable *used* in this definition (the "source") */
 902                                         forwarding_source = tree_mover_slot_from_index (tree_mover, i1->inst_i0->inst_c0);
 903                                         /* Check if source slot is ready to be forwarded */
 904                                         if ((! forwarding_source->pending_move_is_ready) || (forwarding_source->pending_move->prevent_forwarding)) {
 905                                                 /* no forwarding is possible, do nothing */
 906                                                 forwarding_source = NULL;
 907                                         }
 908                                 }
 909                                 //printf ("DEF2 BB%d %d %d\n", bb->block_num,tree->inst_i0->inst_c0,i1->inst_i0->inst_c0);
 910                         }
 911
 912                         /* Apply tree mover */
 913                         if (tree_mover != NULL) {
 914                                 guint defined_index = tree->inst_i0->inst_c0;
 915                                 TreeMoverActSlot *defined_slot = tree_mover_slot_from_index (tree_mover, defined_index);
 916                                 TreeMoverDependencyNode *affected_node;
 917
 918                                 /* First clear the waiting flag... */
 919                                 defined_slot->waiting_flag = FALSE;
 920                                 /* ...and kill this slot (but recording any pending move)*/
 921                                 tree_mover_kill_act_slot_for_definition (tree_mover, defined_slot);
 922                                 if (MONO_DEBUG_TREE_MOVER) {
 923                                         printf ("Definition is clearing slot %d\n", defined_index);
 924                                 }
 925
 926                                 /* Handle "used" nodes... */
 927                                 /* Check if this is a forwarding */
 928                                 if (forwarding_source == NULL) {
 929                                         /* Normal case, no forwarding: */
 930                                         /* Check that consprop or copyprop did not already do the job, */
 931                                         /* and that the tree has no side effects */
 932                                         if (tree_can_be_moved && ! tree_mover->tree_has_side_effects) {
 933                                                 TreeMoverDependencyNode *affecting_node;
 934                                                 if (MONO_DEBUG_TREE_MOVER) {
 935                                                         printf ("Recording definition of slot %d by tree: ", defined_index);
 936                                                         mono_print_tree_nl (tree);
 937                                                 }
 938
 939                                                 /* Then apply the definition */
 940                                                 tree_mover_new_slot_move (tree_mover, defined_slot);
 941                                                 defined_slot->pending_move->definition = tree;
 942                                                 defined_slot->pending_move->defined_slot = defined_slot;
 943                                                 defined_slot->pending_move->tree_reads_memory = tree_mover->tree_reads_memory;
 944
 945                                                 /* Setup "used nodes" list */
 946                                                 defined_slot->used_locals = tree_mover->used_nodes;
 947                                                 defined_slot->last_used_local = tree_mover->last_used_node;
 948                                                 tree_mover->used_nodes = NULL;
 949                                                 tree_mover->last_used_node = NULL;
 950                                                 /* Link used nodes to "affecting" slots (so affected variables are linked) */
 951                                                 /* This is needed *now* so that circular definitions are detected */
 952                                                 for (affecting_node = defined_slot->used_locals; affecting_node != NULL; affecting_node = affecting_node->next_used_local) {
 953                                                         tree_mover_link_affecting_node (affecting_node, defined_slot);
 954                                                 }
 955                                         } else if (MONO_DEBUG_TREE_MOVER) {
 956                                                 /* otherwise, do nothing */
 957                                                 printf ("Skipping definition of slot %d by tree: ", defined_index);
 958                                                 mono_print_tree_nl (tree);
 959                                         }
 960                                 } else {
 961                                         TreeMoverDependencyFromDeadDefinition *dependency;
 962                                         /* forwarding previous definition: */
 963                                         if (MONO_DEBUG_TREE_MOVER) {
 964                                                 printf ("Handling forwarding in slot %d for tree: ", defined_index);
 965                                                 mono_print_tree_nl (tree);
 966                                         }
 967                                         /* Setup slot for forwarding */
 968                                         defined_slot->pending_move = forwarding_source->pending_move;
 969                                         defined_slot->pending_move_is_forwarded = TRUE;
 970                                         /* Setup forwarding dependency node */
 971                                         dependency = mono_mempool_alloc0 (tree_mover->pool, sizeof (TreeMoverDependencyFromDeadDefinition));
 972                                         dependency->defined_slot = defined_slot;
 973                                         dependency->dead_definition = tree;
 974                                         dependency->next = defined_slot->pending_move->slots_that_must_be_safe;
 975                                         defined_slot->pending_move->slots_that_must_be_safe = dependency;
 976                                         /* Clear use (put slot back to state [D]) */
 977                                         defined_slot->pending_move->use = NULL;
 978                                         defined_slot->pending_move->defined_slot->pending_move_is_ready = FALSE;
 979                                 }
 980
 981                                 /* Then kill all affected definitions waiting for a use */
 982                                 affected_node = defined_slot->affected_locals;
 983                                 while (affected_node != NULL) {
 984                                         TreeMoverDependencyNode *next_affected_node = affected_node->next_affected_local;
 985                                         TreeMoverActSlot *affected_slot = affected_node->affected_slot;
 986
 987                                         if (affected_node->use_is_direct) {
 988                                                 /* Direct use: kill affected slot */
 989                                                 if (MONO_DEBUG_TREE_MOVER) {
 990                                                         printf ("  Direct use, killing slot %d with definition:", tree_mover_slot_to_index (tree_mover, affected_node->affected_slot));
 991                                                         mono_print_tree_nl (affected_slot->pending_move->definition);
 992                                                 }
 993                                                 tree_mover_kill_act_slot_because_it_is_affected (tree_mover, affected_slot);
 994                                         } else if ((defined_slot->pending_move!= NULL) &&
 995                                                         (! defined_slot->pending_move_is_ready) &&
 996                                                         (! defined_slot->pending_move_is_forwarded) &&
 997                                                         (affected_slot->pending_move!= NULL) &&
 998                                                         (! affected_slot->pending_move_is_ready) &&
 999                                                         (! affected_slot->pending_move_is_forwarded)) {
1000                                                 if (MONO_DEBUG_TREE_MOVER) {
1001                                                         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));
1002                                                 }
1003                                                 tree_mover_link_affected_moves (tree_mover, defined_slot, affected_slot);
1004                                                 tree_mover_link_affected_moves (tree_mover, affected_slot, defined_slot);
1005                                         }
1006                                         tree_mover_unlink_affecting_node (affected_node);
1007
1008                                         if ((next_affected_node != NULL) && (next_affected_node->affected_slot != NULL)) {
1009                                                 affected_node = next_affected_node;
1010                                         } else {
1011                                                 affected_node = defined_slot->affected_locals;
1012                                         }
1013                                 }
1014                                 if (MONO_DUMP_TREE_MOVER) {
1015                                         tree_mover_print_act_slot ("DEFINITION", tree_mover, defined_slot);
1016                                 }
1017                         }
1018                 }
1019
1020                 /* After we are done with this tree, clear the tree mover area */
1021                 if ((tree_mover != NULL) && (tree_mover->used_nodes != NULL)) {
1022                         tree_mover_dispose_used_nodes (tree_mover);
1023                 }
1024
1025                 /*
1026                   if (tree->opcode == CEE_BEQ) {
1027                   g_assert (tree->inst_i0->opcode == OP_COMPARE);
1028                   if (tree->inst_i0->inst_i0->opcode == OP_ICONST &&
1029                   tree->inst_i0->inst_i1->opcode == OP_ICONST) {
1030
1031                   tree->opcode = OP_BR;
1032                   if (tree->inst_i0->inst_i0->opcode == tree->inst_i0->inst_i1->opcode) {
1033                   tree->inst_target_bb = tree->inst_true_bb;
1034                   } else {
1035                   tree->inst_target_bb = tree->inst_false_bb;
1036                   }
1037                   }
1038                   }
1039                 */
1040         }
1041
1042         if (tree_mover != NULL) {
1043                 /* At BB end, kill all definitions still waiting for a use */
1044                 tree_mover_clear_act_recording_moves (tree_mover, acp_size);
1045                 if (MONO_DEBUG_TREE_MOVER) {
1046                         tree_mover_verify_dependency_nodes_are_clear (tree_mover, acp_size);
1047                 }
1048         }
1049 }
1050
1051
1052 #if (MONO_APPLY_TREE_MOVER_TO_SINGLE_METHOD)
1053 static char*
1054 mono_tree_mover_method_name = NULL;
1055 static gboolean check_tree_mover_method_name (MonoCompile *cfg) {
1056         if (mono_tree_mover_method_name == NULL) {
1057                 mono_tree_mover_method_name = getenv ("MONO_TREE_MOVER_METHOD_NAME");
1058         }
1059         if (mono_tree_mover_method_name != NULL) {
1060                 char *method_name = mono_method_full_name (cfg->method, TRUE);
1061                 if (strstr (method_name, mono_tree_mover_method_name) != NULL) {
1062                         g_free (method_name);
1063                         return TRUE;
1064                 } else {
1065                         g_free (method_name);
1066                         return FALSE;
1067                 }
1068         } else {
1069                 return TRUE;
1070         }
1071 }
1072 #endif
1073
1074 #if (MONO_APPLY_TREE_MOVER_TO_COUNTED_METHODS)
1075 static int
1076 mono_tree_mover_method_limit = -1;
1077 static int
1078 mono_tree_mover_method_count = 0;
1079 static gboolean check_tree_mover_method_count (MonoCompile *cfg) {
1080         if (mono_tree_mover_method_limit == -1) {
1081                 char *limit_string = getenv ("MONO_TREE_MOVER_METHOD_LIMIT");
1082                 if (limit_string != NULL) {
1083                         mono_tree_mover_method_limit = atoi (limit_string);
1084                 } else {
1085                         mono_tree_mover_method_limit = -2;
1086                 }
1087         }
1088         if (mono_tree_mover_method_limit > -1) {
1089                 mono_tree_mover_method_count ++;
1090                 if (mono_tree_mover_method_count == mono_tree_mover_method_limit) {
1091                         char *method_name = mono_method_full_name (cfg->method, TRUE);
1092                         printf ("Last method compiled with treeprop: %s\n", method_name);
1093                         g_free (method_name);
1094
1095                 }
1096                 return (mono_tree_mover_method_count <= mono_tree_mover_method_limit);
1097         } else {
1098                 return TRUE;
1099         }
1100 }
1101 #endif
1102
1103 static void
1104 apply_tree_mover (TreeMover *tree_mover, TreeMoverTreeMove *move) {
1105         TreeMoverDependencyFromDeadDefinition *dependency;
1106         TreeMoverAffectedMove *affected_move;
1107
1108         /* Test if this move has been explicitly disabled */
1109         if (move->skip_this_move) {
1110                 if (MONO_DEBUG_TREE_MOVER) {
1111                         printf ("Move of slot %d must be skipped: ", tree_mover_slot_to_index (tree_mover, move->defined_slot));
1112                         mono_print_tree_nl (move->definition);
1113                 }
1114                 return;
1115         }
1116         /* Test if this move is safe */
1117         if ((! move->move_is_safe) && move->defined_slot->unsafe_flag) {
1118                 if (MONO_DEBUG_TREE_MOVER) {
1119                         printf ("Move of slot %d is unsafe: ", tree_mover_slot_to_index (tree_mover, move->defined_slot));
1120                         mono_print_tree_nl (move->definition);
1121                 }
1122                 return;
1123         }
1124         /* Test if this move depends from a definition that should have been dead */
1125         for (dependency = move->slots_that_must_be_safe; dependency != NULL; dependency = dependency->next) {
1126                 if ((dependency->defined_slot != NULL) && dependency->defined_slot->unsafe_flag) {
1127                         if (MONO_DEBUG_TREE_MOVER) {
1128                                 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));
1129                                 mono_print_tree_nl (move->definition);
1130                         }
1131                         return;
1132                 }
1133         }
1134
1135         if (MONO_DEBUG_TREE_MOVER) {
1136                 printf ("Performing move of slot %d: ", tree_mover_slot_to_index (tree_mover, move->defined_slot));
1137                 mono_print_tree_nl (move->definition);
1138         }
1139         /* All tests passed, apply move */
1140         *(move->use) = move->definition->inst_i1;
1141         move->definition->opcode = OP_NOP;
1142         move->definition->ssa_op = MONO_SSA_NOP;
1143
1144         /* Then disable moves affected by this move */
1145         affected_move = move->affected_moves;
1146         while (affected_move != NULL) {
1147                 if (MONO_DEBUG_TREE_MOVER) {
1148                         printf ("  Consequently, disabling slot %d\n", tree_mover_slot_to_index (tree_mover, affected_move->affected_move->defined_slot));
1149                 }
1150                 affected_move->affected_move->skip_this_move = TRUE;
1151                 affected_move = affected_move->next_affected_move;
1152         }
1153
1154         /* Also kill dead dependency definitions */
1155         for (dependency = move->slots_that_must_be_safe; dependency != NULL; dependency = dependency->next) {
1156                 if (dependency->defined_slot != NULL) {
1157                         if (MONO_DEBUG_TREE_MOVER) {
1158                                 printf ("  Consequently, kill dependent definition %d: ", tree_mover_slot_to_index (tree_mover, dependency->defined_slot));
1159                                 mono_print_tree_nl (dependency->dead_definition);
1160                         }
1161                         dependency->dead_definition->opcode = OP_NOP;
1162                         dependency->dead_definition->ssa_op = MONO_SSA_NOP;
1163                 }
1164         }
1165 }
1166
1167 void
1168 mono_local_cprop (MonoCompile *cfg) {
1169         MonoBasicBlock *bb;
1170         MonoInst **acp;
1171         TreeMover *tree_mover;
1172
1173         acp = alloca (sizeof (MonoInst *) * cfg->num_varinfo);
1174
1175         if (cfg->opt & MONO_OPT_TREEPROP) {
1176                 MonoMemPool *pool = mono_mempool_new();
1177                 tree_mover = mono_mempool_alloc0(pool, sizeof (TreeMover));
1178
1179                 tree_mover->cfg = cfg;
1180                 tree_mover->pool = pool;
1181                 tree_mover->ACT = mono_mempool_alloc0 (pool, sizeof (TreeMoverActSlot) * (cfg->num_varinfo));
1182 #if (MONO_APPLY_TREE_MOVER_TO_SINGLE_METHOD)
1183                 if (! check_tree_mover_method_name (cfg)) {
1184                         mono_mempool_destroy(tree_mover->pool);
1185                         tree_mover = NULL;
1186                 }
1187 #endif
1188 #if (MONO_APPLY_TREE_MOVER_TO_COUNTED_METHODS)
1189                 if (! check_tree_mover_method_count (cfg)) {
1190                         mono_mempool_destroy(tree_mover->pool);
1191                         tree_mover = NULL;
1192                 }
1193 #endif
1194         } else {
1195                 tree_mover = NULL;
1196         }
1197
1198         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
1199                 if (MONO_DEBUG_LOCAL_PROP||MONO_DEBUG_TREE_MOVER) {
1200                         printf ("Applying mono_local_cprop to BB%d\n", bb->block_num);
1201                 }
1202                 memset (acp, 0, sizeof (MonoInst *) * cfg->num_varinfo);
1203                 mono_local_cprop_bb (cfg, tree_mover, bb, acp, cfg->num_varinfo);
1204         }
1205
1206         if (tree_mover != NULL) {
1207                 TreeMoverTreeMove *move;
1208                 /* Move the movable trees */
1209                 if (MONO_DEBUG_TREE_MOVER) {
1210                         printf ("BEFORE TREE MOVER START\n");
1211                         mono_print_code (cfg);
1212                         printf ("BEFORE TREE MOVER END\n");
1213                         printf ("Applying tree mover...\n");
1214                 }
1215                 for (move = tree_mover->scheduled_moves; move != NULL; move = move->next) {
1216                         apply_tree_mover (tree_mover, move);
1217                 }
1218                 if (MONO_DEBUG_TREE_MOVER) {
1219                         printf ("AFTER TREE MOVER START\n");
1220                         mono_print_code (cfg);
1221                         printf ("AFTER TREE MOVER END\n");
1222                 }
1223
1224                 /* Global cleanup of tree mover memory */
1225                 mono_mempool_destroy(tree_mover->pool);
1226         }
1227 }