Reapply "A simpler scheme for garbage collection of ureachable phi inputs."

runtime/vm/flow_graph_allocator.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/flow_graph_allocator.h"
 
 #include "vm/bit_vector.h"
 #include "vm/intermediate_language.h"
 #include "vm/il_printer.h"
 #include "vm/flow_graph.h"
@@ skipping 1110 matching lines @@
           move->AddMove(Location::NoLocation(), Location::NoLocation());
         }
       }
     }
   }
 }
 
 
 // Discover structural (reducible) loops nesting structure.
 void FlowGraphAllocator::DiscoverLoops() {
+  // This algorithm relies on the assumption that we emit blocks in reverse

[Kevin Millikin (Google), 2012/09/20 13:48:17]

Look here.

+  // postorder, so postorder number can be used to identify loop nesting.
+  //
   // TODO(vegorov): consider using a generic algorithm to correctly discover
   // both headers of reducible and irreducible loops.
   BlockInfo* current_loop = NULL;
 
   const intptr_t block_count = postorder_.length();
   for (intptr_t i = 0; i < block_count; i++) {
     BlockEntryInstr* block = postorder_[i];
     GotoInstr* goto_instr = block->last_instruction()->AsGoto();
     if (goto_instr != NULL) {
       JoinEntryInstr* successor = goto_instr->successor();
       if (successor->postorder_number() > i) {
         // This is back-edge.
         BlockInfo* successor_info = BlockInfoAt(successor->lifetime_position());
         ASSERT(successor_info->entry() == successor);
         if (!successor_info->is_loop_header() &&
             ((current_loop == NULL) ||
-             (current_loop->entry()->block_id() <
-                  successor_info->entry()->block_id()))) {
+             (current_loop->entry()->postorder_number() >
+                  successor_info->entry()->postorder_number()))) {
           ASSERT(successor_info != current_loop);
 
           successor_info->mark_loop_header();
           // For loop header loop information points to the outer loop.
           successor_info->set_loop(current_loop);
           current_loop = successor_info;
         }
       }
     }
 
@@ skipping 1035 matching lines @@
     OS::Print("-- [after ssa allocator] ir [%s] -------------\n",
               function.ToFullyQualifiedCString());
     FlowGraphPrinter printer(flow_graph_, true);
     printer.PrintBlocks();
     OS::Print("----------------------------------------------\n");
   }
 }
 
 
 }  // namespace dart