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

runtime/vm/flow_graph_allocator.cc

Index: runtime/vm/flow_graph_allocator.cc
diff --git a/runtime/vm/flow_graph_allocator.cc b/runtime/vm/flow_graph_allocator.cc
index 780ed6174ec7cb16861f68e8f7932dd65711a4ad..98ea75300bb1c93543bb4aa0410c5016ea55cddf 100644
--- a/runtime/vm/flow_graph_allocator.cc
+++ b/runtime/vm/flow_graph_allocator.cc
@@ -1128,6 +1128,9 @@ void FlowGraphAllocator::NumberInstructions() {
 
 // 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;
@@ -1144,8 +1147,8 @@ void FlowGraphAllocator::DiscoverLoops() {
         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();