Implement loop invariant code motion for check instructions.

runtime/vm/intermediate_language.h

 // 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.
 
 #ifndef VM_INTERMEDIATE_LANGUAGE_H_
 #define VM_INTERMEDIATE_LANGUAGE_H_
 
 #include "vm/allocation.h"
 #include "vm/ast.h"
 #include "vm/growable_array.h"
@@ skipping 410 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.
+  friend class LICM;

[srdjan, 2012/09/06 13:44:26]

Please add why, or move the comment if it is valid for both.

[Florian Schneider, 2012/09/06 13:49:30]

 Moved it to below where the comment applies.

 
   // Classes that set deopt_id_.
   friend class UnboxDoubleInstr;
   friend class UnboxedDoubleBinaryOpInstr;
   friend class CheckClassInstr;
   friend class CheckSmiInstr;
   friend class CheckNonSmiInstr;
   friend class CheckArrayBoundInstr;
   friend class CheckEitherNonSmiInstr;
 
@@ skipping 156 matching lines @@
   void set_dominator(BlockEntryInstr* instr) { dominator_ = instr; }
 
   const GrowableArray<BlockEntryInstr*>& dominated_blocks() {
     return dominated_blocks_;
   }
 
   void AddDominatedBlock(BlockEntryInstr* block) {
     dominated_blocks_.Add(block);
   }
 
+  bool Dominates(BlockEntryInstr* other) const;
+
   Instruction* last_instruction() const { return last_instruction_; }
   void set_last_instruction(Instruction* instr) { last_instruction_ = instr; }
 
   ParallelMoveInstr* parallel_move() const {
     return parallel_move_;
   }
 
   bool HasParallelMove() const {
     return parallel_move_ != NULL;
   }
@@ skipping 20 matching lines @@
     return NULL;
   }
   virtual void SetInputAt(intptr_t i, Value* value) { UNREACHABLE(); }
 
   virtual intptr_t ArgumentCount() const { return 0; }
 
   virtual bool CanDeoptimize() const { return false; }
 
   intptr_t try_index() const { return try_index_; }
 
+  const ZoneGrowableArray<BlockEntryInstr*>* loop_info() const {
+    return loop_info_;
+  }
+  void set_loop_info(const ZoneGrowableArray<BlockEntryInstr*>* loop_info) {
+    loop_info_ = loop_info;
+  }
+
  protected:
   explicit BlockEntryInstr(intptr_t try_index)
       : try_index_(try_index),
         preorder_number_(-1),
         postorder_number_(-1),
         block_id_(-1),
         dominator_(NULL),
         dominated_blocks_(1),
         last_instruction_(NULL),
-        parallel_move_(NULL) { }
+        parallel_move_(NULL),
+        loop_info_(NULL) { }
 
  private:
   const intptr_t try_index_;
   intptr_t preorder_number_;
   intptr_t postorder_number_;
   // Starting and ending lifetime positions for this block.  Used by
   // the linear scan register allocator.
   intptr_t block_id_;
   intptr_t start_pos_;
   intptr_t end_pos_;
   BlockEntryInstr* dominator_;  // Immediate dominator, NULL for graph entry.
   // TODO(fschneider): Optimize the case of one child to save space.
   GrowableArray<BlockEntryInstr*> dominated_blocks_;
   Instruction* last_instruction_;
 
   // Parallel move that will be used by linear scan register allocator to
   // connect live ranges at the start of the block.
   ParallelMoveInstr* parallel_move_;
 
+  const ZoneGrowableArray<BlockEntryInstr*>* loop_info_;
+
   DISALLOW_COPY_AND_ASSIGN(BlockEntryInstr);
 };
 
 
 class ForwardInstructionIterator : public ValueObject {
  public:
   explicit ForwardInstructionIterator(BlockEntryInstr* block_entry)
       : block_entry_(block_entry), current_(block_entry) {
     ASSERT(block_entry_->last_instruction()->next() == NULL);
     Advance();
@@ skipping 310 matching lines @@
     UNREACHABLE();
     return false;
   }
 
   // Returns a hash code for use with hash maps.
   virtual intptr_t Hashcode() const;
 
   virtual void RecordAssignedVars(BitVector* assigned_vars,
                                   intptr_t fixed_parameter_count);
 
+  // Get the block entry for that instruction.
+  virtual BlockEntryInstr* GetBlock() const;
+
   // Printing support. These functions are sometimes overridden for custom
   // formatting. Otherwise, it prints in the format "opcode(op1, op2, op3)".
   virtual void PrintTo(BufferFormatter* f) const;
   virtual void PrintOperandsTo(BufferFormatter* f) const;
   virtual void PrintToVisualizer(BufferFormatter* f) const;
 
  private:
   intptr_t temp_index_;
   intptr_t ssa_temp_index_;
   // TODO(regis): GrowableArray<const AbstractType*> propagated_types_;
@@ skipping 13 matching lines @@
   explicit PhiInstr(JoinEntryInstr* block, intptr_t num_inputs)
     : block_(block),
       inputs_(num_inputs),
       is_alive_(false),
       representation_(kTagged) {
     for (intptr_t i = 0; i < num_inputs; ++i) {
       inputs_.Add(NULL);
     }
   }
 
+  // Get the block entry for that instruction.
+  virtual BlockEntryInstr* GetBlock() const { return block(); }
   JoinEntryInstr* block() const { return block_; }
 
   virtual RawAbstractType* CompileType() const;
   virtual intptr_t GetPropagatedCid();
 
   virtual intptr_t ArgumentCount() const { return 0; }
 
   intptr_t InputCount() const { return inputs_.length(); }
 
   Value* InputAt(intptr_t i) const { return inputs_[i]; }
@@ skipping 41 matching lines @@
   GrowableArray<Value*> inputs_;
   bool is_alive_;
   Representation representation_;
 
   DISALLOW_COPY_AND_ASSIGN(PhiInstr);
 };
 
 
 class ParameterInstr : public Definition {
  public:
-  explicit ParameterInstr(intptr_t index) : index_(index) { }
+  explicit ParameterInstr(intptr_t index, GraphEntryInstr* block)
+      : index_(index), block_(block) { }
 
   DECLARE_INSTRUCTION(Parameter)
 
   intptr_t index() const { return index_; }
 
+  // Get the block entry for that instruction.
+  virtual BlockEntryInstr* GetBlock() const { return block_; }
+
   // Compile type of the passed-in parameter.
   virtual RawAbstractType* CompileType() const;
 
   // No known propagated cid for parameters.
   virtual intptr_t GetPropagatedCid();
 
   virtual intptr_t ArgumentCount() const { return 0; }
 
   intptr_t InputCount() const { return 0; }
   Value* InputAt(intptr_t i) const {
@@ skipping 12 matching lines @@
   virtual intptr_t ResultCid() const {
     UNREACHABLE();
     return kIllegalCid;
   }
 
   virtual void PrintTo(BufferFormatter* f) const;
   virtual void PrintToVisualizer(BufferFormatter* f) const;
 
  private:
   const intptr_t index_;
+  GraphEntryInstr* block_;
 
   DISALLOW_COPY_AND_ASSIGN(ParameterInstr);
 };
 
 
 class PushArgumentInstr : public Definition {
  public:
   explicit PushArgumentInstr(Value* value) : value_(value), locs_(NULL) {
     ASSERT(value != NULL);
     set_use_kind(kEffect);  // Override the default.
@@ skipping 2122 matching lines @@
   ForwardInstructionIterator* current_iterator_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_