Reapply "Initial implementation of on-stack replacement (OSR)."

runtime/vm/intermediate_language.cc

 // Copyright (c) 2013, 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/intermediate_language.h"
 
 #include "vm/bigint_operations.h"
 #include "vm/bit_vector.h"
 #include "vm/dart_entry.h"
 #include "vm/flow_graph_allocator.h"
@@ skipping 227 matching lines @@
 
 const Object& Value::BoundConstant() const {
   ASSERT(BindsToConstant());
   ConstantInstr* constant = definition()->AsConstant();
   ASSERT(constant != NULL);
   return constant->value();
 }
 
 
 GraphEntryInstr::GraphEntryInstr(const ParsedFunction& parsed_function,
-                                 TargetEntryInstr* normal_entry)
+                                 TargetEntryInstr* normal_entry,
+                                 intptr_t osr_id)
     : BlockEntryInstr(0, CatchClauseNode::kInvalidTryIndex),
       parsed_function_(parsed_function),
       normal_entry_(normal_entry),
       catch_entries_(),
       initial_definitions_(),
+      osr_id_(osr_id),
       spill_slot_count_(0),
       fixed_slot_count_(0) {
 }
 
 
 ConstantInstr* GraphEntryInstr::constant_null() {
   ASSERT(initial_definitions_.length() > 0);
   for (intptr_t i = 0; i < initial_definitions_.length(); ++i) {
     ConstantInstr* defn = initial_definitions_[i]->AsConstant();
     if (defn != NULL && defn->value().IsNull()) return defn;
@@ skipping 516 matching lines @@
                                          variable_count,
                                          fixed_parameter_count);
   }
 
   // 6. Assign postorder number and add the block entry to the list.
   set_postorder_number(postorder->length());
   postorder->Add(this);
 }
 
 
+bool BlockEntryInstr::PruneUnreachable(FlowGraphBuilder* builder,
+                                       GraphEntryInstr* graph_entry,
+                                       intptr_t osr_id,
+                                       BitVector* block_marks) {
+  // Search for the instruction with the OSR id.  Use a depth first search
+  // because basic blocks have not been discovered yet.  Prune unreachable
+  // blocks by replacing the normal entry with a jump to the block
+  // containing the OSR entry point.
+
+  // Do not visit blocks more than once.
+  if (block_marks->Contains(block_id())) return false;
+  block_marks->Add(block_id());
+
+  // Search this block for the OSR id.
+  Instruction* instr = this;
+  for (ForwardInstructionIterator it(this); !it.Done(); it.Advance()) {
+    instr = it.Current();
+    if (instr->GetDeoptId() == osr_id) {
+      // Sanity check that we found a stack check instruction.
+      ASSERT(instr->IsCheckStackOverflow());
+      // Loop stack check checks are always in join blocks so that they can
+      // be the target of a goto.
+      ASSERT(IsJoinEntry());
+      // The instruction should be the first instruction in the block so
+      // we can simply jump to the beginning of the block.
+      ASSERT(instr->previous() == this);
+
+      GotoInstr* goto_join = new GotoInstr(AsJoinEntry());
+      goto_join->deopt_id_ = deopt_id_;
+      graph_entry->normal_entry()->LinkTo(goto_join);
+      return true;
+    }
+  }
+
+  // Recursively search the successors.
+  for (intptr_t i = instr->SuccessorCount() - 1; i >= 0; --i) {
+    if (instr->SuccessorAt(i)->PruneUnreachable(builder,
+                                                graph_entry,
+                                                osr_id,
+                                                block_marks)) {
+      return true;
+    }
+  }
+  return false;
+}
+
+
 bool BlockEntryInstr::Dominates(BlockEntryInstr* other) const {
   // TODO(fschneider): Make this faster by e.g. storing dominators for each
   // block while computing the dominator tree.
   ASSERT(other != NULL);
   BlockEntryInstr* current = other;
   while (current != NULL && current != this) {
     current = current->dominator();
   }
   return current == this;
 }
@@ skipping 1700 matching lines @@
     default:
       UNREACHABLE();
   }
   return kPowRuntimeEntry;
 }
 
 
 #undef __
 
 }  // namespace dart