Generalize bounds checks.

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"
@@ skipping 763 matching lines @@
   void InsertBefore(Instruction* next) { InsertAfter(next->previous()); }
 
   // Insert this instruction after 'prev' after use lists are computed.
   void InsertAfter(Instruction* prev);
 
   // Append an instruction to the current one and return the tail.
   // This function updated def-use chains of the newly appended
   // instruction.
   Instruction* AppendInstruction(Instruction* tail);
 
+  virtual bool AllowsDCE() const {
+    return false;
+  }
+
   // Returns true if CSE and LICM are allowed for this instruction.
   virtual bool AllowsCSE() const {
     return false;
   }
 
   // Returns set of effects created by this instruction.
   virtual EffectSet Effects() const = 0;
 
   // Returns set of effects that affect this instruction.
   virtual EffectSet Dependencies() const {
@@ skipping 33 matching lines @@
   }
 
   virtual bool CanBecomeDeoptimizationTarget() const {
     return false;
   }
 
   void InheritDeoptTargetAfter(Isolate* isolate, Instruction* other);
 
   virtual bool MayThrow() const = 0;
 
+  bool IsDominatedBy(Instruction* dom);
+
  protected:
   // Fetch deopt id without checking if this computation can deoptimize.
   intptr_t GetDeoptId() const {
     return deopt_id_;
   }
 
  private:
   friend class FlowGraphPrinter;
   friend class Definition;  // Needed for InsertBefore, InsertAfter.
   friend class CallSiteInliner;
@@ skipping 39 matching lines @@
   friend class UnaryDoubleOpInstr;
   friend class MathUnaryInstr;
   friend class MathMinMaxInstr;
   friend class CheckClassInstr;
   friend class CheckClassIdInstr;
   friend class GuardFieldInstr;
   friend class CheckSmiInstr;
   friend class CheckArrayBoundInstr;
   friend class CheckEitherNonSmiInstr;
   friend class LICM;
+  friend class Scheduler;
   friend class DoubleToSmiInstr;
   friend class DoubleToDoubleInstr;
   friend class DoubleToFloatInstr;
   friend class FloatToDoubleInstr;
   friend class InvokeMathCFunctionInstr;
   friend class MergedMathInstr;
   friend class FlowGraphOptimizer;
   friend class LoadIndexedInstr;
   friend class StoreIndexedInstr;
   friend class StoreInstanceFieldInstr;
@@ skipping 193 matching lines @@
   void set_postorder_number(intptr_t number) { postorder_number_ = number; }
 
   intptr_t block_id() const { return block_id_; }
 
   void set_start_pos(intptr_t pos) { start_pos_ = pos; }
   intptr_t start_pos() const { return start_pos_; }
   void  set_end_pos(intptr_t pos) { end_pos_ = pos; }
   intptr_t end_pos() const { return end_pos_; }
 
   BlockEntryInstr* dominator() const { return dominator_; }
+  BlockEntryInstr* ImmediateDominator() const;
 
   const GrowableArray<BlockEntryInstr*>& dominated_blocks() {
     return dominated_blocks_;
   }
 
   void AddDominatedBlock(BlockEntryInstr* block) {
     block->set_dominator(this);
     dominated_blocks_.Add(block);
   }
   void ClearDominatedBlocks() { dominated_blocks_.Clear(); }
@@ skipping 724 matching lines @@
 };
 
 
 struct BranchLabels {
   Label* true_label;
   Label* false_label;
   Label* fall_through;
 };
 
 
+struct InductionVariableInfo;
+
+
 class PhiInstr : public Definition {
  public:
   PhiInstr(JoinEntryInstr* block, intptr_t num_inputs)
     : block_(block),
       inputs_(num_inputs),
       is_alive_(false),
       representation_(kTagged),
-      reaching_defs_(NULL) {
+      reaching_defs_(NULL),
+      loop_variable_info_(NULL) {
     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 CompileType ComputeType() const;
@@ skipping 43 matching lines @@
 
   void set_reaching_defs(BitVector* reaching_defs) {
     reaching_defs_ = reaching_defs;
   }
 
   virtual bool MayThrow() const { return false; }
 
   // A phi is redundant if all input operands are the same.
   bool IsRedundant() const;
 
+  void set_induction_variable_info(InductionVariableInfo* info) {
+    loop_variable_info_ = info;
+  }
+
+  InductionVariableInfo* induction_variable_info() {
+    return loop_variable_info_;
+  }
+
  private:
   // Direct access to inputs_ in order to resize it due to unreachable
   // predecessors.
   friend class ConstantPropagator;
 
   void RawSetInputAt(intptr_t i, Value* value) { inputs_[i] = value; }
 
   JoinEntryInstr* block_;
   GrowableArray<Value*> inputs_;
   bool is_alive_;
   Representation representation_;
 
   BitVector* reaching_defs_;
+  InductionVariableInfo* loop_variable_info_;
 
   DISALLOW_COPY_AND_ASSIGN(PhiInstr);
 };
 
 
 class ParameterInstr : public Definition {
  public:
   ParameterInstr(intptr_t index,
                  BlockEntryInstr* block,
                  Register base_reg = FPREG)
@@ skipping 457 matching lines @@
   virtual EffectSet Dependencies() const { return EffectSet::None(); }
   virtual EffectSet Effects() const { return EffectSet::None(); }
 
   virtual bool MayThrow() const { return false; }
 
  private:
   DISALLOW_COPY_AND_ASSIGN(RedefinitionInstr);
 };
 
 
-class ConstraintInstr : public TemplateDefinition<2> {
+class ConstraintInstr : public TemplateDefinition<1> {
  public:
   ConstraintInstr(Value* value, Range* constraint)
       : constraint_(constraint),
         target_(NULL) {
     SetInputAt(0, value);
   }
 
   DECLARE_INSTRUCTION(Constraint)
 
-  virtual intptr_t InputCount() const {
-    return (inputs_[1] == NULL) ? 1 : 2;
-  }
-
   virtual CompileType ComputeType() const;
 
   virtual bool CanDeoptimize() const { return false; }
 
   virtual EffectSet Effects() const { return EffectSet::None(); }
 
   virtual bool AttributesEqual(Instruction* other) const {
     UNREACHABLE();
     return false;
   }
 
   virtual bool MayThrow() const { return false; }
 
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   Value* value() const { return inputs_[0]; }
   Range* constraint() const { return constraint_; }
 
   virtual void InferRange(RangeAnalysis* analysis, Range* range);
 
-  void AddDependency(Definition* defn) {
-    Value* val = new Value(defn);
-    defn->AddInputUse(val);
-    SetInputAt(1, val);
-  }
-
   // Constraints for branches have their target block stored in order
   // to find the the comparsion that generated the constraint:
   // target->predecessor->last_instruction->comparison.
   void set_target(TargetEntryInstr* target) {
     target_ = target;
   }
   TargetEntryInstr* target() const {
     return target_;
   }
 
  private:
-  Value* dependency() {
-    return inputs_[1];
-  }
-
   Range* constraint_;
   TargetEntryInstr* target_;
 
   DISALLOW_COPY_AND_ASSIGN(ConstraintInstr);
 };
 
 
 class ConstantInstr : public TemplateDefinition<0> {
  public:
   explicit ConstantInstr(const Object& value);
@@ skipping 4451 matching lines @@
   }
 
   // Returns true if right is a non-zero Smi constant which absolute value is
   // a power of two.
   bool RightIsPowerOfTwoConstant() const;
 
   RawInteger* Evaluate(const Integer& left, const Integer& right) const;
 
   virtual Definition* Canonicalize(FlowGraph* flow_graph);
 
+  virtual bool AllowsDCE() const {
+    switch (op_kind()) {
+      case Token::kADD:
+      case Token::kSUB:
+      case Token::kMUL:
+      case Token::kBIT_AND:
+      case Token::kBIT_OR:
+      case Token::kBIT_XOR:
+        return true;
+
+      case Token::kSHR:
+      case Token::kSHL:
+        // These instructions throw on negative shifts.
+        return !CanDeoptimize();
+
+      default:
+        return false;
+    }
+  }
   virtual bool AllowsCSE() const { return true; }
   virtual EffectSet Effects() const { return EffectSet::None(); }
   virtual EffectSet Dependencies() const { return EffectSet::None(); }
   virtual bool AttributesEqual(Instruction* other) const;
 
   virtual intptr_t DeoptimizationTarget() const { return deopt_id_; }
 
   virtual bool MayThrow() const { return false; }
 
   virtual void PrintOperandsTo(BufferFormatter* f) const;
@@ skipping 950 matching lines @@
 
  private:
   intptr_t cid_;
 
   DISALLOW_COPY_AND_ASSIGN(CheckClassIdInstr);
 };
 
 
 class CheckArrayBoundInstr : public TemplateInstruction<2> {
  public:
-  CheckArrayBoundInstr(Value* length, Value* index, intptr_t deopt_id) {
+  CheckArrayBoundInstr(Value* length, Value* index, intptr_t deopt_id)
+      : generalized_(false) {
     SetInputAt(kLengthPos, length);
     SetInputAt(kIndexPos, index);
     // Override generated deopt-id.
     deopt_id_ = deopt_id;
   }
 
   Value* length() const { return inputs_[kLengthPos]; }
   Value* index() const { return inputs_[kIndexPos]; }
 
   DECLARE_INSTRUCTION(CheckArrayBound)
 
   virtual intptr_t ArgumentCount() const { return 0; }
 
   virtual bool CanDeoptimize() const { return true; }
 
   bool IsRedundant(const RangeBoundary& length);
 
+  void mark_generalized() {
+    generalized_ = true;
+  }
+
   virtual Instruction* Canonicalize(FlowGraph* flow_graph);
 
   // Returns the length offset for array and string types.
   static intptr_t LengthOffsetFor(intptr_t class_id);
 
   static bool IsFixedLengthArrayType(intptr_t class_id);
 
   virtual bool AllowsCSE() const { return true; }
   virtual EffectSet Effects() const { return EffectSet::None(); }
   virtual EffectSet Dependencies() const { return EffectSet::None(); }
   virtual bool AttributesEqual(Instruction* other) const { return true; }
 
   virtual bool MayThrow() const { return false; }
 
   // Give a name to the location/input indices.
   enum {
     kLengthPos = 0,
     kIndexPos = 1
   };
 
  private:
+  bool generalized_;
+
   DISALLOW_COPY_AND_ASSIGN(CheckArrayBoundInstr);
 };
 
 
 class BoxIntNInstr : public TemplateDefinition<1> {
  public:
   BoxIntNInstr(Representation representation, Value* value)
       : from_representation_(representation) {
     SetInputAt(0, value);
   }
@@ skipping 452 matching lines @@
       Isolate* isolate, bool opt) const {                                     \
     UNIMPLEMENTED();                                                          \
     return NULL;                                                              \
   }                                                                           \
   void Name::EmitNativeCode(FlowGraphCompiler* compiler) { UNIMPLEMENTED(); }
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_