Initial implementation of on-stack replacement (OSR).

runtime/vm/intermediate_language.h

 // 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.
 
 #ifndef VM_INTERMEDIATE_LANGUAGE_H_
 #define VM_INTERMEDIATE_LANGUAGE_H_
 
 #include "vm/allocation.h"
 #include "vm/ast.h"
 #include "vm/growable_array.h"
 #include "vm/handles_impl.h"
 #include "vm/locations.h"
 #include "vm/object.h"
 
 namespace dart {
 
 class BitVector;
 class BlockEntryInstr;
 class BufferFormatter;
 class CatchBlockEntryInstr;
 class ComparisonInstr;
 class ControlInstruction;
 class Definition;
 class Environment;
 class FlowGraph;
+class FlowGraphBuilder;
 class FlowGraphCompiler;
 class FlowGraphVisitor;
 class Instruction;
 class LocalVariable;
 class ParsedFunction;
 class Range;
 
 
 // TODO(srdjan): Unify with INTRINSIC_LIST.
 // (class-name, function-name, recognized enum, fingerprint).
@@ skipping 825 matching lines @@
 
  protected:
   // Fetch deopt id without checking if this computation can deoptimize.
   intptr_t GetDeoptId() const {
     return deopt_id_;
   }
 
  private:
   friend class Definition;  // Needed for InsertBefore, InsertAfter.
 
-  // Classes that set deopt_id_.
+  // Classes that set or read deopt_id_.
   friend class UnboxIntegerInstr;
   friend class UnboxDoubleInstr;
   friend class UnboxFloat32x4Instr;
   friend class UnboxUint32x4Instr;
   friend class BinaryDoubleOpInstr;
   friend class BinaryFloat32x4OpInstr;
   friend class Float32x4ZeroInstr;
   friend class Float32x4SplatInstr;
   friend class Float32x4ShuffleInstr;
   friend class Float32x4ConstructorInstr;
@@ skipping 32 matching lines @@
   friend class StoreInstanceFieldInstr;
   friend class ControlInstruction;
   friend class ComparisonInstr;
   friend class TargetEntryInstr;
   friend class JoinEntryInstr;
   friend class InstanceOfInstr;
   friend class PolymorphicInstanceCallInstr;
   friend class SmiToDoubleInstr;
   friend class DoubleToIntegerInstr;
   friend class BranchSimplifier;
+  friend class BlockEntryInstr;
 
   virtual void RawSetInputAt(intptr_t i, Value* value) = 0;
 
   enum {
     kNoExprId = -1
   };
 
   intptr_t deopt_id_;
   intptr_t lifetime_position_;  // Position used by register allocator.
   Instruction* previous_;
@@ skipping 202 matching lines @@
   // block entry instructions of predecessor blocks) and also the last
   // instruction in the block is recorded in each entry instruction.
   void DiscoverBlocks(
       BlockEntryInstr* predecessor,
       GrowableArray<BlockEntryInstr*>* preorder,
       GrowableArray<BlockEntryInstr*>* postorder,
       GrowableArray<intptr_t>* parent,
       intptr_t variable_count,
       intptr_t fixed_parameter_count);
 
+  // Perform a depth first search to prune code not reachable from an OSR
+  // entry point.
+  bool PruneUnreachable(FlowGraphBuilder* builder,
+                        GraphEntryInstr* graph_entry,
+                        intptr_t osr_id,
+                        BitVector* block_marks);
+
   virtual intptr_t InputCount() const { return 0; }
   virtual Value* InputAt(intptr_t i) const {
     UNREACHABLE();
     return NULL;
   }
 
   virtual intptr_t ArgumentCount() const { return 0; }
 
   virtual bool CanBecomeDeoptimizationTarget() const {
     // BlockEntry environment is copied to Goto and Branch instructions
@@ skipping 118 matching lines @@
 
  private:
   BlockEntryInstr* block_entry_;
   Instruction* current_;
 };
 
 
 class GraphEntryInstr : public BlockEntryInstr {
  public:
   GraphEntryInstr(const ParsedFunction& parsed_function,
-                  TargetEntryInstr* normal_entry);
+                  TargetEntryInstr* normal_entry,
+                  intptr_t osr_id);
 
   DECLARE_INSTRUCTION(GraphEntry)
 
   virtual intptr_t PredecessorCount() const { return 0; }
   virtual BlockEntryInstr* PredecessorAt(intptr_t index) const {
     UNREACHABLE();
     return NULL;
   }
   virtual intptr_t SuccessorCount() const;
   virtual BlockEntryInstr* SuccessorAt(intptr_t index) const;
 
   void AddCatchEntry(CatchBlockEntryInstr* entry) { catch_entries_.Add(entry); }
 
   CatchBlockEntryInstr* GetCatchEntry(intptr_t index);
 
   GrowableArray<Definition*>* initial_definitions() {
     return &initial_definitions_;
   }
   ConstantInstr* constant_null();
 
+  bool IsCompiledForOsr() const { return osr_id_ != Isolate::kNoDeoptId; }
+
   intptr_t spill_slot_count() const { return spill_slot_count_; }
   void set_spill_slot_count(intptr_t count) {
     ASSERT(count >= 0);
     spill_slot_count_ = count;
   }
 
   // Number of stack slots reserved for compiling try-catch. For functions
   // without try-catch, this is 0. Otherwise, it is the number of local
   // variables.
   intptr_t fixed_slot_count() const { return fixed_slot_count_; }
@@ skipping 14 matching lines @@
   virtual void PrintTo(BufferFormatter* f) const;
 
  private:
   virtual void ClearPredecessors() {}
   virtual void AddPredecessor(BlockEntryInstr* predecessor) { UNREACHABLE(); }
 
   const ParsedFunction& parsed_function_;
   TargetEntryInstr* normal_entry_;
   GrowableArray<CatchBlockEntryInstr*> catch_entries_;
   GrowableArray<Definition*> initial_definitions_;
+  const intptr_t osr_id_;
   intptr_t spill_slot_count_;
   intptr_t fixed_slot_count_;  // For try-catch in optimized code.
 
   DISALLOW_COPY_AND_ASSIGN(GraphEntryInstr);
 };
 
 
 class JoinEntryInstr : public BlockEntryInstr {
  public:
   JoinEntryInstr(intptr_t block_id, intptr_t try_index)
@@ skipping 4547 matching lines @@
 
  private:
   const Token::Kind op_kind_;
 
   DISALLOW_COPY_AND_ASSIGN(UnarySmiOpInstr);
 };
 
 
 class CheckStackOverflowInstr : public TemplateInstruction<0> {
  public:
-  explicit CheckStackOverflowInstr(intptr_t token_pos)
-      : token_pos_(token_pos) {}
+  CheckStackOverflowInstr(intptr_t token_pos, bool is_loop)
+      : token_pos_(token_pos), is_loop_(is_loop) {}
 
   intptr_t token_pos() const { return token_pos_; }
+  bool is_loop() const { return is_loop_; }

[srdjan, 2013/06/11 17:12:02]

Maybe call it 'in_loop' instead?

[Kevin Millikin (Google), 2013/06/14 10:10:42]

Done.

 
   DECLARE_INSTRUCTION(CheckStackOverflow)
 
   virtual intptr_t ArgumentCount() const { return 0; }
 
   virtual bool CanDeoptimize() const { return true; }
 
   virtual EffectSet Effects() const { return EffectSet::None(); }
 
   virtual bool MayThrow() const { return false; }
 
+  virtual void PrintOperandsTo(BufferFormatter* f) const;
+
  private:
   const intptr_t token_pos_;
+  const bool is_loop_;
 
   DISALLOW_COPY_AND_ASSIGN(CheckStackOverflowInstr);
 };
 
 
 class SmiToDoubleInstr : public TemplateDefinition<1> {
  public:
   explicit SmiToDoubleInstr(Value* value) {
     SetInputAt(0, value);
   }
@@ skipping 534 matching lines @@
   ForwardInstructionIterator* current_iterator_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_