Array bounds check elimination.

src/hydrogen.cc

Index: src/hydrogen.cc
diff --git a/src/hydrogen.cc b/src/hydrogen.cc
index 1590ab36698d9d5b98605111966ed17b8c7bc2a8..9828220d172cf958b21aec3b83dd9e31ad1b6895 100644
--- a/src/hydrogen.cc
+++ b/src/hydrogen.cc
@@ -71,7 +71,8 @@ HBasicBlock::HBasicBlock(HGraph* graph)
       parent_loop_header_(NULL),
       is_inline_return_target_(false),
       is_deoptimizing_(false),
-      dominates_loop_successors_(false) { }
+      dominates_loop_successors_(false),
+      is_osr_entry_(false) { }
 
 
 void HBasicBlock::AttachLoopInformation() {
@@ -596,6 +597,11 @@ HConstant* HGraph::GetConstantInt32(SetOncePointer<HConstant>* pointer,
 }
 
 
+HConstant* HGraph::GetConstant0() {
+  return GetConstantInt32(&constant_0_, 0);
+}
+
+
 HConstant* HGraph::GetConstant1() {
   return GetConstantInt32(&constant_1_, 1);
 }
@@ -3326,7 +3332,11 @@ bool HGraph::Optimize(SmartArrayPointer<char>* bailout_reason) {
   HStackCheckEliminator sce(this);
   sce.Process();
 
-  EliminateRedundantBoundsChecks();
+  if (FLAG_array_bounds_checks_dehoisting) {
+    EliminateOrDehoistBoundsChecks();
+  } else {
+    EliminateRedundantBoundsChecks();
+  }
   DehoistSimpleArrayIndexComputations();
   if (FLAG_dead_code_elimination) DeadCodeElimination();
 
@@ -3670,6 +3680,886 @@ void HGraph::EliminateRedundantBoundsChecks() {
 }
 
 
+// Helper class for array access index manipulation in
+// BoundsCheckValueInfo::CoverCheckWithBase.
+// The indexes have the form "base + constant" and the manipulations involve
+// changing the constant. Since the original constant HValue could be used
+// elsewhere we cannot change it and must create a new one.
+// However we need to create the HAdd only the first time we manipulate an
+// index, and later on we just reuse the instruction.
+class BoundsCheckManipulationData: public ZoneObject {
+ public:
+  HValue* Base() { return base_; }

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: lower-case names for simple accessors.

+  HBoundsCheck* Check() { return check_; }

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: lower-case names for simple accessors.

+  int Offset() { return offset_; }

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: lower-case names for simple accessors.

+
+  // Change the index to use a new offset.
+  void ChangeOffset(int new_offset) {
+    HConstant* new_constant = new(zone())

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: please break the line after '=', and indent the second line by 4 spaces.

+       HConstant(new_offset, Representation::Integer32());
+    if (added_add_ == NULL) {
+      new_constant->InsertBefore(Check());
+      added_add_ = new(zone()) HAdd(NULL, Base(), new_constant);
+      added_add_->AssumeRepresentation(Check()->index()->representation());
+      added_add_->InsertBefore(Check());
+    } else {
+      new_constant->InsertBefore(added_add_);
+      added_offset_->DeleteAndReplaceWith(new_constant);
+    }
+    added_offset_ = new_constant;
+    Check()->SetOperandAt(0, added_add_);

[Jakob Kummerow, 2012/12/05 15:20:02]

I'd prefer introducing a method HBoundsCheck::SetIndex(HValue* index) {
SetOperandAt(0, index); } for this, to keep the internal ordering of operands
local to the HBoundsCheck class.

+    offset_ = new_offset;
+  }
+
+  // If we ended up creating an "add zero" instruction we can remove it.
+  void RemoveNullAdd() {

[Jakob Kummerow, 2012/12/05 15:20:02]

Why do we have to do this as an additional step? Can't this be folded into
ChangeOffset? Probably something like:
if (new_offset == 0) {
  if (added_add_ != NULL) {
    DeleteAndReplaceWith(...)
    added_add_ = NULL;
  }
  return;
}
Or am I overlooking some reason why that can't work?

+    if (added_add_ != NULL && added_offset_->Integer32Value() == 0) {
+      added_add_->DeleteAndReplaceWith(added_add_->left());
+      added_offset_->DeleteAndReplaceWith(NULL);
+      added_add_ = NULL;
+      added_offset_ = NULL;
+    }
+  }
+
+  BoundsCheckManipulationData(HValue* base, HBoundsCheck* check, int offset) :

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: ':' goes on the next line, with 4-space indentation. Also, the constructor
should be the first thing in the "public:" section.

+    base_(base), check_(check), offset_(offset),
+    added_add_(NULL), added_offset_(NULL) {}
+
+ private:
+  HValue* base_;
+  HBoundsCheck* check_;
+  int offset_;
+  HAdd* added_add_;
+  HConstant* added_offset_;
+
+  Zone* zone() { return Check()->block()->zone(); }

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: methods before data members

+};
+
+
+class BoundsCheckValueInfo;
+
+
+static bool BoundsCheckValueInfoMatch(void* v1, void* v2);
+
+
+// The "knowledge base" used for array bounds check elimination.
+// A hash table indexed by HValue ID and containing a list of known facts for
+// the given value.
+class BoundsCheckValueInfoTable : public ZoneObject {
+ public:
+  Zone* zone() { return zone_; }
+
+  // If the entry is in the table but the list is empty, remove it.
+  void CleanupKey(HValue* key);
+
+  BoundsCheckValueInfo** LookupKey(HValue* key);
+  BoundsCheckValueInfo** LookupOrInsert(HValue* key);
+  BoundsCheckValueInfo** Insert(BoundsCheckValueInfo* data);
+  void Delete(HValue* key);
+
+  explicit BoundsCheckValueInfoTable(Zone* zone)

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: the constructor should be the first thing in the "public:" section.

+      : zone_(zone),
+        map_(BoundsCheckValueInfoMatch,
+             ZoneHashMap::kDefaultHashMapCapacity,
+             ZoneAllocationPolicy(zone)){ }

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: space before '{'

+ private:

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: empty line before "private:" (doesn't presubmit.py complain about this?)

+  Zone* zone_;
+  ZoneHashMap map_;
+};
+
+
+enum ValueInfoRelation {
+  NONE,
+  NE,

[Jakob Kummerow, 2012/12/05 15:20:02]

Feel free to put all values onto the same line (I don't care either way).

+  GT,
+  GE,
+  EQ,
+  LE,
+  LT
+};
+
+
+class BoundsCheckRemovalBlockContext BASE_EMBEDDED {
+ public:
+  HBasicBlock* block() { return block_; }
+  BoundsCheckValueInfoTable* table() { return table_; }
+  BoundsCheckValueInfo* data_list_head() { return bb_data_list_; }
+  BoundsCheckValueInfo** data_insertion_point() { return &bb_data_list_; }
+  BoundsCheckRemovalBlockContext* previous() { return previous_; }
+
+  BoundsCheckValueInfo* NewValueInfo(HValue* v,
+                                     HValue* c,
+                                     ValueInfoRelation r,
+                                     bool is_incremental,
+                                     HBoundsCheck* bounds_check = NULL,
+                                     int check_offset = 0);
+
+  BoundsCheckRemovalBlockContext(

[Jakob Kummerow, 2012/12/05 15:20:02]

again, constructor comes first

+      HBasicBlock* block,
+      BoundsCheckRemovalBlockContext* previous)
+      : table_(previous != NULL ? previous->table() :

[Jakob Kummerow, 2012/12/05 15:20:02]

proper indentation please:
      : table_(previous != NULL
                   ? previous->table()
                   : new(block->graph()->zone())
                       BoundsCheckValueInfoTable(block->graph()->zone())),
        block_(block), bb_data_list_(NULL), previous_(previous) {}

Consider moving the initialization of table_ into the constructor's body
instead:

if (previous_ == NULL) {
  Zone* zone = block_->graph()->zone();
  table_ = new(zone) BoundsCheckValueInfoTable(zone);
} else {
  table_ = previous_->table();
}

+          new(block->graph()->zone())
+          BoundsCheckValueInfoTable(block->graph()->zone())),
+          block_(block), bb_data_list_(NULL), previous_(previous) {}
+
+ private:
+  BoundsCheckValueInfoTable* table_;
+  HBasicBlock* block_;
+  BoundsCheckValueInfo* bb_data_list_;
+  BoundsCheckRemovalBlockContext* previous_;
+};
+
+
+// The individual "fact" in the knowledge base.
+// Each fact has the form "value relation constraint", where value and

[Jakob Kummerow, 2012/12/05 15:20:02]

suggestion:
// Each fact has the form (value, relation, constraint) with types
// (HValue*, ValueInfoRelation, HValue*).

+// constraint are both HValue instances and "relation" can be one of the
+// usual relational operators (less than, greater than, ecc).
+class BoundsCheckValueInfo: public ZoneObject {
+ public:
+  HValue* Value() { return value_; }

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: lower-case names for simple accessors.

+  ValueInfoRelation Relation() { return relation_; }

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: lower-case names for simple accessors.

+  HValue* Constraint() { return constraint_; }

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: lower-case names for simple accessors.

+  // True if Value() will "cover" every single integer value in the range

[Jakob Kummerow, 2012/12/05 15:20:02]

s/"cover"/take/

+  // defined by the relation.
+  // This could be used to detect in advance that an array is not holey
+  // because a loop will write every single array element.
+  bool IsIncremental() { return is_incremental_; }

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: lower-case names for simple accessors.

+
+  bool ConstraintIsZero() {
+    if (!constraint_->IsConstant()) { return false; }
+    HConstant* c = HConstant::cast(constraint_);
+    return c->DoubleValue() == 0.0;

[Jakob Kummerow, 2012/12/05 15:20:02]

This won't work for non-number constants. Use "return c->HasDoubleValue() &&
c->DoubleValue() == 0.0;" instead. Also, why *double* value? Aren't you more
interested in integers?

+  }
+  Zone* zone() { return Value()->block()->zone(); }
+
+  // A HBoundsCheck on the same index; it is equivalent to having...

[Jakob Kummerow, 2012/12/05 15:20:02]

...?

+  HBoundsCheck* BoundsCheck() { return bounds_check_; }

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: lower-case names for simple accessors.

+
+  // The following properties are all helpers for CoverCheckWithBase.

[Jakob Kummerow, 2012/12/05 15:20:02]

If they're helpers for another member, why are they public?

+  // To make things easier at construction time every list head will just copy
+  // the values from the next element (which is the previous one in the
+  // dominator tree traversal).
+  // This simplifies both searching (the list head always holds current values)
+  // and backtracking (the remaining list head has naturally the right values).
+
+  // Offset used by CoverCheckWithBase.
+  int CheckOffset() { return check_offset_; }

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: lower-case names for simple accessors.

+  // Lower check used by CoverCheckWithBase.
+  BoundsCheckManipulationData* LowerCheck() { return lower_check_; }

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: lower-case names for simple accessors.

+  // Upper check used by CoverCheckWithBase.
+  BoundsCheckManipulationData* UpperCheck() { return upper_check_; }

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: lower-case names for simple accessors.

+  // Initial state for CoverCheckWithBase (both checks should be NULL).
+  bool HasNoBaseHandledCheck() { return lower_check_ == NULL; }

[Jakob Kummerow, 2012/12/05 15:20:02]

What's a BaseHandledCheck? Why not just "HasNoCheck"?

+  // "single check" state for CoverCheckWithBase.
+  bool HasSingleBaseHandledCheck() {
+    return lower_check_ != NULL && lower_check_ == upper_check_;
+  }
+  // End of CoverCheckWithBase helpers.
+
+  // Basic block in which this fact was created.
+  HBasicBlock* BasicBlock() const { return basic_block_; }

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: lower-case names for simple accessors.

+  // Next known fact for this value.
+  BoundsCheckValueInfo* NextForValue() { return next_for_value_; }

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: lower-case names for simple accessors.

+  // Next fact created in this basic block.
+  BoundsCheckValueInfo* NextInBasicBlock() { return next_in_basic_block_; }

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: lower-case names for simple accessors.

+
+
+  // This method handles the special case of indexes like "base + constant".
+  // For any given HValue "exp", two bounds checks "exp + c1" and exp + c2"
+  // will obviously "cover" every other array access where the index value is
+  // between "exp + c1" and exp + c2".
+  // Now, suppose that we meet an index "exp + c3" which is out of this range.
+  // If we are in the same basic block we can easily change either c1 or c2
+  // in one of the two previous checks so that the 3rd check is redundant.
+  // (if we are not in the same BB the change would be optimistic and could
+  // lead to "unneeded" deoptimizations so we don't do it).
+  // This method does exactly that, handling changes between these states:
+  // - No previous check was met (HasNoBaseHandledCheck() == true)
+  // - We have one previous check (HasSingleBaseHandledCheck() == true)
+  // - We have two previous checks.
+  // The class BoundsCheckManipulationData helps keeping track of the changed
+  // instructions so that it is easy to change than again if needed.

[Jakob Kummerow, 2012/12/05 15:20:02]

s/than/them/

+  bool CoverCheckWithBase(

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: for method declarations (as opposed to calls), either everything should fit
on one line, or every parameter should be on its own line.

Also, I don't like this method's name. It doesn't make it clear what the method
does, and it also doesn't indicate what it returns. At the very least, a comment
"Returns true iff the new_check should be removed." would be nice.

+      HValue* base, HBoundsCheck* new_check, int32_t new_offset) {
+    ASSERT(new_check->index()->representation().IsInteger32());
+    bool remove_new_check = false;

[Jakob Kummerow, 2012/12/05 15:20:02]

Why do we need a variable for this? Looks like assigning it is always the last
thing that happens before returning, so you could s/remove_new_check =
true;/return true;/ below and finally s/return remove_new_check;/return false;/.

+
+    if (HasNoBaseHandledCheck()) {
+      lower_check_ = new(zone())
+          BoundsCheckManipulationData(base, new_check, new_offset);
+      upper_check_ = lower_check_;
+    } else {
+      if (new_offset > UpperCheck()->Offset()) {
+        if (HasSingleBaseHandledCheck() ||
+            upper_check_->Check()->block() != BasicBlock()) {

[Jakob Kummerow, 2012/12/05 15:20:02]

Why is this check necessary? BoundsCheckValueInfo is per-block anyway, so why
can't you ignore checks from the wrong block in the first place?

+          upper_check_ = new(zone())
+              BoundsCheckManipulationData(base, new_check, new_offset);
+        } else {
+          upper_check_->ChangeOffset(new_offset);
+          remove_new_check = true;
+        }
+      } else if (new_offset < LowerCheck()->Offset()) {
+        if (HasSingleBaseHandledCheck() ||
+            lower_check_->Check()->block() != BasicBlock()) {
+          lower_check_ = new(zone())
+              BoundsCheckManipulationData(base, new_check, new_offset);
+        } else {
+          lower_check_->ChangeOffset(new_offset);
+          remove_new_check = true;
+        }
+      } else {
+        remove_new_check = true;
+      }
+    }
+
+    return remove_new_check;
+  }
+
+  void RemoveNullAdds() {
+    if (lower_check_ == NULL) return;
+    lower_check_->RemoveNullAdd();
+    if (upper_check_ == lower_check_) return;
+    upper_check_->RemoveNullAdd();
+  }
+
+  uint32_t Hash() {
+    return static_cast<uint32_t>(value_->Hashcode());
+  }
+
+  // Instead of doing a graph walk we attempt to simplify the index.
+  // Since simplifications can be recursive we put a limit on the number
+  // of steps we take.
+  // This is roughly equivalent to limiting the graph walks to only a
+  // given number of steps (but is way easier to implement...).
+  static const int kDepthLimit = 3;
+
+  // The main method that queries the knowledge base to see if a given value
+  // has a relation with a given limit ("value" is the array index and
+  // "limit" is the array length).
+  // If, as a result, both *lower_covered and *upper_covered are true then the
+  // bounds check can be eliminated: the lower part stands for "value >= 0"
+  // and the upper part for "value < limit".
+  // Either of them is NULL it means that the caller is not interested in that
+  // part of the relation.
+  // Depth limits the complexity of the attempted value decompositions.
+  static void ComputeIndexRelation(HValue* value,
+                                   HValue* limit,
+                                   HBasicBlock* block,
+                                   HValue** hoisted_limit,
+                                   bool* lower_covered,
+                                   bool* upper_covered,
+                                   BoundsCheckValueInfoTable* table,
+                                   int depth) {
+    BoundsCheckValueInfo** value_head;
+    if (lower_covered == NULL && upper_covered == NULL) return;
+    if (depth == 0) {
+      value_head = table->LookupOrInsert(value);
+    } else if (depth > kDepthLimit) {
+      return;
+    } else {
+      value_head = table->LookupKey(value);
+      if (value_head == NULL) {
+        return;
+      }
+    }
+
+    for (BoundsCheckValueInfo* value_info = *value_head;
+        value_info != NULL;

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: aligning "value_info" with "BoundsCheckValueInfo" (i.e. one more space)
looks slightly better, don't you think?

+        value_info = value_info->NextForValue()) {
+      if (lower_covered != NULL) {
+        if (value_info->ConstraintIsZero() && value_info->Relation() == GE) {
+          *lower_covered = true;
+        }
+      }
+      if (upper_covered != NULL) {

[Jakob Kummerow, 2012/12/05 15:20:02]

Ugh. 5 levels of nested "if"s? I'd prefer the following (even though it's still
messy):
      if (upper_covered != NULL && value_info->Relation() == LT) {
        HValue* constraint = value_info->Constraint();
        if (constraint == limit) {
          *upper_covered = true;
          continue;
        } 
        if (hoisted_limit != NULL &&
            constraint->block()->Dominates(
                block->loop_information()->loop_header()) &&
            (*hoisted_limit == NULL ||
             constraint->block()->Dominates(
                 (*hoisted_limit)->block()))) {
          *hoisted_limit = constraint;
        }
      }

+        if (value_info->Relation() == LT) {
+          if (value_info->Constraint() == limit) {
+            *upper_covered = true;
+          } else if (hoisted_limit != NULL) {
+            HValue* constraint = value_info->Constraint();
+            if (constraint->block()->Dominates(
+                block->loop_information()->loop_header())) {
+              if (*hoisted_limit == NULL ||
+                  constraint->block()->Dominates((*hoisted_limit)->block())) {
+                *hoisted_limit = constraint;
+              }
+            }
+          }
+        }
+      }
+    }
+
+    if (!((lower_covered == NULL || *lower_covered) &&
+        (upper_covered == NULL || *upper_covered))) {

[Jakob Kummerow, 2012/12/05 15:20:02]

Please indent this so that the indentation reflects the nesting structure (i.e.
two more spaces). Also, I think it would be a bit clearer to move the negation
into the leaves:

    if ((lower_covered != NULL && *lower_covered == false) ||
        (upper_covered != NULL && *upper_covered == false)) {

+      bool skip_lower = false;
+      bool skip_upper = false;
+      int32_t constant;
+      HValue* simplified_value = SimplifyValue(
+          value, &skip_lower, &skip_upper, &constant);
+      if (simplified_value != NULL) {
+        ComputeIndexRelation(simplified_value, limit, block, hoisted_limit,
+                             skip_lower ? NULL : lower_covered,
+                             skip_upper ? NULL : upper_covered,
+                             table, depth + 1);
+      }
+    }
+
+    if (!((lower_covered == NULL || *lower_covered) &&

[Jakob Kummerow, 2012/12/05 15:20:02]

same here

+        (upper_covered == NULL || *upper_covered))) {
+      if (value->IsPhi()) {
+        HPhi* phi = HPhi::cast(value);
+        bool lower_skip_state = false;
+        bool upper_skip_state = false;
+        for (int i = 0;
+            i < phi->OperandCount() && !(lower_skip_state && upper_skip_state);
+            i++) {
+          bool lower_skip_argument = false;
+          bool upper_skip_argument = false;
+          ComputeIndexRelation(phi->OperandAt(i), limit, block, hoisted_limit,
+                               &lower_skip_argument,
+                               &upper_skip_argument,
+                               table, depth + 1);
+          if (lower_skip_argument) {
+            lower_skip_state = true;
+          }
+          if (upper_skip_argument) {
+            upper_skip_state = true;
+          }
+        }
+
+        if (lower_covered != NULL && !lower_skip_state) *lower_covered = true;
+        if (upper_covered != NULL && !upper_skip_state) *upper_covered = true;
+      }
+    }
+  }
+
+  static bool CoverBasePlusConstant(HBoundsCheck* check,

[Jakob Kummerow, 2012/12/05 15:20:02]

Another method that doesn't tell me what the method does (what does "cover"
mean?) or what it returns.

+                                    BoundsCheckRemovalBlockContext* context) {
+    HValue* index_base;
+    int32_t offset;
+    if (GetCheckIndexBase(check->index(), &index_base, &offset)) {
+      BoundsCheckValueInfo** base_head =
+          context->table()->LookupOrInsert(index_base);
+      BoundsCheckValueInfo* base_info = *base_head;
+      if (base_info == NULL) {
+        base_info = context->NewValueInfo(
+            index_base, check->length(), NONE, false, check, offset);
+      }
+      return base_info->CoverCheckWithBase(index_base, check, offset);
+    } else {

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: no need for "else", just "return false".

+      return false;
+    }
+  }
+
+  static void HandleCheck(HBoundsCheck* check,
+                          BoundsCheckRemovalBlockContext* context) {
+    HValue* index = check->index();
+    HValue* length = check->length();
+    bool lower_covered = false;
+    bool upper_covered = false;
+    HBasicBlock* block = context->block();
+    HValue* hoisted_limit = NULL;
+    HValue** hoisted_limit_pointer;

[Jakob Kummerow, 2012/12/05 15:20:02]

initialize this to NULL here...

+
+    if (block->graph()->use_optimistic_licm() &&
+        block->loop_information() != NULL &&
+        length->block()->Dominates(block->loop_information()->loop_header())) {
+      hoisted_limit_pointer = &hoisted_limit;
+    } else {
+      hoisted_limit_pointer = NULL;

[Jakob Kummerow, 2012/12/05 15:20:02]

...and drop this.

+    }
+
+    ComputeIndexRelation(
+        index, length, block, hoisted_limit_pointer,

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: no need to break the first line of arguments

+        &lower_covered, &upper_covered, context->table(), 0);
+
+    if (!(lower_covered && upper_covered)) {
+      if (CoverBasePlusConstant(check, context)) {
+        lower_covered = true;
+        upper_covered = true;
+      }
+    }
+
+    if ((!(lower_covered && upper_covered)) && hoisted_limit != NULL) {

[Jakob Kummerow, 2012/12/05 15:20:02]

simplification: you can remove one set of parentheses by moving the negation to
the leaves of the condition tree:
if ((!lower_covered || !upper_covered) && hoisted_limit != NULL) {

+      HBasicBlock* hoisting_block =
+          block->loop_information()->loop_pre_header();
+      BoundsCheckRemovalBlockContext* hoisting_context = context;
+      while (hoisting_context != NULL &&
+          hoisting_context->block() != hoisting_block) {

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: prefer alignment at '(' (i.e. in this case the two occurrences of
"hosting_context" exactly below each other).

+        hoisting_context = hoisting_context->previous();
+      }
+
+      if (hoisting_context != NULL) {
+        HBoundsCheck* new_check =
+            new(context->table()->zone()) HBoundsCheck(hoisted_limit, length);
+        new_check->InsertBefore(hoisting_block->last());
+        context->NewValueInfo(
+            index, block->graph()->GetConstant0(), GE, false);
+        context->NewValueInfo(index, length, LT, false);
+        lower_covered = true;
+        upper_covered = true;
+      }
+    }
+
+    bool remove_check = true;
+    if (!lower_covered) {
+      remove_check = false;
+      context->NewValueInfo(index, block->graph()->GetConstant0(), GE, false);
+    }
+    if (!upper_covered) {
+      remove_check = false;
+      context->NewValueInfo(index, length, LT, false);
+    }
+    if (remove_check) {
+      check->DeleteAndReplaceWith(NULL);
+    }
+  }
+
+  // Handles a HPhi definition, eventually creating a new fact.
+  static void FromPhi(HPhi* phi,

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: some other name please. We commonly use "static Foo* Foo::FromBar(Bar*
bar)" as the name of a factory method that constructs a Foo from a Bar.

+                      BoundsCheckRemovalBlockContext* context) {
+    if (phi->OperandCount() != 2) return;
+
+    ValueInfoRelation relation;
+    bool is_incremental;
+
+    relation = RelationFromMonotonicOperation(
+        phi, phi->OperandAt(0), &is_incremental);
+    if (relation != NONE) {
+      context->NewValueInfo(phi, phi->OperandAt(1), relation, is_incremental);
+      return;
+    }
+
+    relation = RelationFromMonotonicOperation(
+        phi, phi->OperandAt(1), &is_incremental);
+    if (relation != NONE) {
+      context->NewValueInfo(phi, phi->OperandAt(0), relation, is_incremental);
+      return;
+    }
+  }
+
+  // Handles a conditional branch, eventually creating new facts.
+  static void FromConditionalBranch(

[Jakob Kummerow, 2012/12/05 15:20:02]

Again, please choose some name that doesn't sound like a factory method

+      HCompareIDAndBranch* condition,
+      BoundsCheckRemovalBlockContext* context) {
+    HValue* value;
+    HValue* constraint;
+    ValueInfoRelation relation;
+    bool isElseBranch;

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: unix_hacker_style names for variables

+    if (context->block() == condition->SuccessorAt(0)) {
+      isElseBranch = false;
+    } else if (context->block() == condition->SuccessorAt(1)) {
+      isElseBranch = true;
+    } else {
+      return;
+    }
+
+    relation = FromToken(condition->token());
+    if (relation == NONE) return;
+
+    if (isElseBranch) {
+      value = condition->right();
+      constraint = condition->left();
+    } else {
+      value = condition->left();
+      constraint = condition->right();
+    }
+
+    context->NewValueInfo(value, constraint, relation, false);
+    context->NewValueInfo(constraint, value, Switched(relation), false);

[Jakob Kummerow, 2012/12/05 15:20:02]

Whoa. Do we really need to store every fact twice?

+  }
+
+  static const char* RelationName(ValueInfoRelation r) {
+    switch (r) {
+      case NE:
+        return "NE";
+      case GT:
+        return "GT";
+      case GE:
+        return "GE";
+      case EQ:
+        return "EQ";
+      case LE:
+        return "LE";
+      case LT:
+        return "LT";
+      case NONE:
+        return "NONE";
+      default:

[Jakob Kummerow, 2012/12/05 15:20:02]

since you're handling all cases explicitly, you don't need a "default:" case.
Which is preferable anyway, because it turns the UNREACHABLE() run-time error
into a compile-time error.

+        UNREACHABLE();
+        return "UNREACHABLE";
+    }
+  }
+
+  bool UnlinkFromValue() {
+    *previous_for_value_ = next_for_value_;

[Jakob Kummerow, 2012/12/05 15:20:02]

Having different levels of pointer indirection for previous_for_value_ and
next_for_value_ is horribly confusing.

+    if (next_for_value_ != NULL) {
+      next_for_value_->previous_for_value_ = previous_for_value_;
+    }
+    bool result = (next_for_value_ == NULL);
+    previous_for_value_ = NULL;
+    next_for_value_ = NULL;
+    RemoveNullAdds();
+    return result;
+  }
+
+  BoundsCheckValueInfo(HValue* v,

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: constructor should be the first thing in the "public:" section

+                       HValue* c,

[Jakob Kummerow, 2012/12/05 15:20:02]

what do "v" and "c" mean?

+                       ValueInfoRelation r,
+                       bool is_incremental,
+                       BoundsCheckRemovalBlockContext* context,
+                       HBoundsCheck* bounds_check = NULL,
+                       int check_offset = 0) :

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: ':' goes on the next line

+      value_(DiscardOsrValue(v)), constraint_(DiscardOsrValue(c)),
+      relation_(r), is_incremental_(is_incremental),
+      bounds_check_(bounds_check),
+      check_offset_(check_offset),
+      basic_block_(context->block()),
+      previous_for_value_(context->table()->LookupOrInsert(value_)),
+      next_for_value_(*previous_for_value_),
+      next_in_basic_block_(*context->data_insertion_point()),
+      lower_check_(next_for_value_ != NULL ?

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: if a ternary operator doesn't fit on one line, align '?' and ':', as in:
fooooooooooooooooo ? barrrrrrrrrrrrrrrrr
                   : bazzzzzzzzzzzzzzzzz

+          next_for_value_->LowerCheck() : NULL),
+      upper_check_(next_for_value_ != NULL ?
+          next_for_value_->UpperCheck() : NULL) {
+    if (next_for_value_ != NULL) {
+      next_for_value_->previous_for_value_ = &(next_for_value_);
+    }
+    *previous_for_value_ = this;
+    *context->data_insertion_point() = this;
+  }
+
+ private:
+  HValue* value_;

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: member variables come last in the "private:" section

+  HValue* constraint_;
+  ValueInfoRelation relation_;
+  bool is_incremental_;
+  HBoundsCheck* bounds_check_;
+  int check_offset_;
+
+  HBasicBlock* basic_block_;
+  BoundsCheckValueInfo** previous_for_value_;
+  BoundsCheckValueInfo* next_for_value_;
+  BoundsCheckValueInfo* next_in_basic_block_;
+  BoundsCheckManipulationData* lower_check_;
+  BoundsCheckManipulationData* upper_check_;
+
+  // Detect if a value has the form "base plus constant".
+  static bool GetCheckIndexBase(HValue* index,

[Jakob Kummerow, 2012/12/05 15:20:02]

Another method name that puzzles me, especially in combination with the comment
above which seems to say something completely different.

+                                HValue** index_base,
+                                int32_t* offset) {
+    *index_base = NULL;
+    *offset = 0;
+    if (!index->representation().IsInteger32()) return NULL;
+
+    HConstant* constant = NULL;
+    bool is_sub = false;
+
+    if (index->IsAdd()) {
+      HAdd* add = HAdd::cast(index);
+      if (add->left()->IsConstant()) {
+        constant = HConstant::cast(add->left());
+        *index_base = add->right();
+      } else if (add->right()->IsConstant()) {
+        constant = HConstant::cast(add->right());
+        *index_base = add->left();
+      }
+    } else if (index->IsSub()) {
+      HSub* sub = HSub::cast(index);
+      is_sub = true;
+      if (sub->left()->IsConstant()) {

[Jakob Kummerow, 2012/12/05 15:20:02]

This was probably supposed to be sub->right()->IsConstant(), no? It seems that
would be the case much more often, and it matches what you're doing below.

+        constant = HConstant::cast(sub->left());
+        *index_base = sub->right();
+      }
+    }
+
+    if (constant != NULL && constant->HasInteger32Value()) {
+      *offset = is_sub ? - constant->Integer32Value()
+                       : constant->Integer32Value();
+      return true;
+    }
+    return false;
+  }
+
+  // Attempts value simplification or decomposition.
+  static HValue* SimplifyValue(HValue* value,
+                              bool* skip_lower,

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: indentation

+                              bool* skip_upper,
+                              int32_t* constant) {
+    HValue* result = NULL;
+    *constant = 0;
+
+    if (value->IsAdd()) {
+      HAdd* add = HAdd::cast(value);
+      HConstant* constant_operand = NULL;
+      if (add->left()->IsConstant()) {

[Jakob Kummerow, 2012/12/05 15:20:02]

This code here is an almost exact duplicate of the code in GetCheckIndexBase
above. I would suggest to replace it with a call, or factor out the shared
stuff.

+        result = add->right();
+        constant_operand = HConstant::cast(add->left());
+      } else if (add->right()->IsConstant()) {
+        result = add->left();
+        constant_operand = HConstant::cast(add->right());
+      }
+      if (constant_operand != NULL && constant_operand->HasInteger32Value()) {
+        *constant = constant_operand->Integer32Value();
+        if (*constant > 0) {
+          *skip_upper = true;
+        } else if (*constant < 0) {
+          *skip_lower = true;
+        } else {
+          result = value;
+        }
+      } else {
+        result = NULL;
+      }
+    } else if (value->IsSub()) {
+      HSub* sub = HSub::cast(value);
+      HConstant* constant_operand = NULL;
+      if (sub->left()->IsConstant()) {
+        result = sub->right();
+        constant_operand = HConstant::cast(sub->left());
+      } else if (sub->right()->IsConstant()) {
+        result = sub->left();
+        constant_operand = HConstant::cast(sub->right());
+      }
+      if (constant_operand != NULL && constant_operand->HasInteger32Value()) {
+        *constant = constant_operand->Integer32Value();
+        if (*constant > 0) {
+          *skip_lower = true;
+        } else if (*constant > 0) {

[Jakob Kummerow, 2012/12/05 15:20:02]

This is the same condition as before. You probably meant "if (*constant < 0)".

Also, if sub->left()->IsConstant() above, this code almost certainly doesn't do
what you want.

+          *skip_upper = true;
+        } else {
+          result = value;
+        }
+      } else {
+        result = NULL;
+      }
+    }
+
+    return result;
+  }
+
+
+  static ValueInfoRelation FromToken(Token::Value token) {

[Jakob Kummerow, 2012/12/05 15:20:02]

Having such a simple mapping from Token::Value to ValueInfoRelation makes me
wonder why you're not using Token::Value in the first place? We have
Token::IsOrderedRelationalCompareOp(), Token::IsEqualityOp(),
Token::NegateCompareOp(), Token::String(), which should cover all of your use
cases quite nicely.

+    switch (token) {
+      case Token::EQ:
+      case Token::EQ_STRICT:
+        return EQ;
+      case Token::LT:
+        return LT;
+      case Token::GT:
+        return GT;
+      case Token::LTE:
+        return LE;
+      case Token::GTE:
+        return GE;
+      default:
+        return NONE;
+    }
+  }
+
+  // Detects if a HPhi defines a monotonic operation, and if it does
+  // returns the appropriate relation.
+  // *value_increment is true if the value will assume every integer value
+  // in the range.
+  static ValueInfoRelation RelationFromMonotonicOperation(
+      HPhi* base, HValue* operation, bool* value_increment) {

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: for method/function declarations, either everything fits onto one line, or
each parameter gets its own line (except the first if it fits on the line of the
method name and the others can be aligned with that).

+    *value_increment = false;
+
+    if (operation->opcode() == HValue::kAdd) {
+        HAdd* add = HAdd::cast(operation);

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: indentation

+        HValue* maybe_constant;
+        if (add->right() == base) {
+          maybe_constant = add->left();
+        } else if (add->left() == base) {
+          maybe_constant = add->right();
+        } else {
+          return NONE;
+        }
+
+        if (maybe_constant->IsConstant()) {
+          HConstant* c = HConstant::cast(maybe_constant);
+          if ((c->DoubleValue() == 1) || (c->DoubleValue() == -1))

[Jakob Kummerow, 2012/12/05 15:20:02]

Again:
1) why DoubleValue() and not Integer32Value()?
2) you need to check for HasDoubleValue() (or HasInteger32Value()) for this to
work correctly.

+            *value_increment = true;
+          if (c->DoubleValue() > 0) {
+            return GE;
+          } else if (c->DoubleValue() < 0) {
+            return LE;
+          } else if (c->DoubleValue() == 0) {
+            return EQ;
+          } else {
+            return NONE;
+          }
+        }
+        return NONE;
+    } else if (operation->opcode() == HValue::kSub) {
+      HSub* sub = HSub::cast(operation);
+      if (sub->right() == base && sub->left()->IsConstant()) {

[Jakob Kummerow, 2012/12/05 15:20:02]

this looks like another left/right mixup.

+        HConstant* c = HConstant::cast(sub->left());
+        if ((c->DoubleValue() == 1) || (c->DoubleValue() == -1))
+          *value_increment = true;
+        if (c->DoubleValue() > 0) {
+          return LE;
+        } else if (c->DoubleValue() < 0) {
+          return GE;
+        } else if (c->DoubleValue() == 0) {
+          return EQ;
+        } else {
+          return NONE;
+        }
+      } else {
+        return NONE;
+      }
+    }
+    return NONE;
+  }
+
+  static ValueInfoRelation Switched(ValueInfoRelation other) {

[Jakob Kummerow, 2012/12/05 15:20:02]

"Switched"? Into shuffle mode?

Also, we already have Token::NegateCompareOp()

+    switch (other) {
+      case NE:
+        return EQ;
+      case GT:
+        return LE;
+      case GE:
+        return LT;
+      case EQ:
+        return NE;
+      case LE:
+        return GT;
+      case LT:
+        return GE;
+      default:
+        UNREACHABLE();
+        return NONE;
+    }
+  }
+
+  // Helper method to discard a HPhi induced by OSR.
+  static HValue* DiscardOsrValue(HValue* v) {
+    if (!v->IsPhi()) return v;
+    HPhi* phi = HPhi::cast(v);
+    if (phi->OperandCount() != 2) return v;
+    if (phi->OperandAt(0)->block()->is_osr_entry()) {
+      return phi->OperandAt(1);
+    } else if (phi->OperandAt(1)->block()->is_osr_entry()) {
+      return phi->OperandAt(0);
+    } else {
+      return v;
+    }
+  }
+};
+
+
+BoundsCheckValueInfo* BoundsCheckRemovalBlockContext::NewValueInfo(
+    HValue* v,
+    HValue* c,

[Jakob Kummerow, 2012/12/05 15:20:02]

what do "v" and "c" stand for?

+    ValueInfoRelation r,
+    bool is_incremental,
+    HBoundsCheck* bounds_check,
+    int check_offset) {
+  return new (table()->zone()) BoundsCheckValueInfo(
+      v, c, r, is_incremental, this, bounds_check, check_offset);
+}
+
+
+static bool BoundsCheckValueInfoMatch(void* v1, void* v2) {
+  BoundsCheckValueInfo* k1 = static_cast<BoundsCheckValueInfo*>(v1);
+  BoundsCheckValueInfo* k2 = static_cast<BoundsCheckValueInfo*>(v2);
+  return k1->Value() == k2->Value();
+}
+
+
+void BoundsCheckValueInfoTable::CleanupKey(HValue* key) {
+  ZoneHashMap::Entry* e = map_.Lookup(
+      key, static_cast<uint32_t>(key->Hashcode()), false,
+      ZoneAllocationPolicy(zone()));
+  if (e != NULL && e->value == NULL) {
+    map_.Remove(key, key->Hashcode());
+  }
+}
+
+
+BoundsCheckValueInfo** BoundsCheckValueInfoTable::LookupKey(HValue* key) {
+  ZoneHashMap::Entry* entry = map_.Lookup(
+      key, static_cast<uint32_t>(key->Hashcode()), false,
+      ZoneAllocationPolicy(zone()));
+  if (entry != NULL) {
+    return reinterpret_cast<BoundsCheckValueInfo**>(&(entry->value));
+  } else {
+    return NULL;
+  }
+}
+
+
+BoundsCheckValueInfo** BoundsCheckValueInfoTable::LookupOrInsert(HValue* key) {
+  return reinterpret_cast<BoundsCheckValueInfo**>(
+      &(map_.Lookup(key, static_cast<uint32_t>(key->Hashcode()), true,
+               ZoneAllocationPolicy(zone()))->value));

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: please align with "key"

+}
+
+
+BoundsCheckValueInfo** BoundsCheckValueInfoTable::Insert(
+    BoundsCheckValueInfo* data) {
+  BoundsCheckValueInfo** result = LookupOrInsert(data->Value());
+  *result = data;
+  return result;
+}
+
+
+void BoundsCheckValueInfoTable::Delete(HValue* key) {
+  map_.Remove(key, key->Hashcode());
+}
+
+
+// Recursive traversal of the dominator tree to remove array bounds checks.
+void HGraph::EliminateOrDehoistBoundsChecks(
+    HBasicBlock* bb,
+    BoundsCheckRemovalBlockContext* previous_context) {
+  BoundsCheckRemovalBlockContext context(bb, previous_context);
+
+  // Add facts deduced from conditional branches.
+  if (bb->predecessors()->length() == 1) {
+    HBasicBlock* predecessor = bb->predecessors()->at(0);
+    HInstruction* end = predecessor->last();
+    if (end->IsCompareIDAndBranch()) {
+      BoundsCheckValueInfo::FromConditionalBranch(

[Jakob Kummerow, 2012/12/05 15:20:02]

Looks like "static void Foo::Bar(..., Baz*)" could be made cleaner by
refactoring it to "void Baz::Bar(...)", i.e.
BoundsCheckRemovalBlockContext::HandleConditionalBranch(HCompareIdAndBranch*
branch).

+          HCompareIDAndBranch::cast(end), &context);
+    }
+  }
+
+  // Add facts deduced from phi definitions.
+  for (int i = 0; i < bb->phis()->length(); i++) {
+    BoundsCheckValueInfo::FromPhi(bb->phis()->at(i), &context);

[Jakob Kummerow, 2012/12/05 15:20:02]

again, why "void A::B(C, &context)" instead of "context->B(C)"?

+  }
+
+  for (HInstruction* i = bb->first(); i != NULL; i = i->next()) {
+    if (!i->IsBoundsCheck()) continue;
+
+    HBoundsCheck* check = HBoundsCheck::cast(i);
+    check->ReplaceAllUsesWith(check->index());

[Jakob Kummerow, 2012/12/05 15:20:02]

Why this line?

+    BoundsCheckValueInfo::HandleCheck(check, &context);

[Jakob Kummerow, 2012/12/05 15:20:02]

again, why "void A::B(C, &context)" instead of "context->B(C)"?

+  }
+
+  for (int i = 0; i < bb->dominated_blocks()->length(); ++i) {
+    EliminateOrDehoistBoundsChecks(
+        bb->dominated_blocks()->at(i), &context);
+  }
+
+  for (BoundsCheckValueInfo* value_info = context.data_list_head();
+      value_info != NULL;

[Jakob Kummerow, 2012/12/05 15:20:02]

nit: aligning 'v' with 'B' looks better

+      value_info = value_info->NextInBasicBlock()) {
+    if (value_info->UnlinkFromValue()) {
+      context.table()->CleanupKey(value_info->Value());
+    }
+  }
+}
+
+
+void HGraph::EliminateOrDehoistBoundsChecks() {
+  HPhase phase("H_Eliminate or dehoist bounds checks", this);
+  EliminateOrDehoistBoundsChecks(entry_block(), NULL);
+}
+
+
 static void DehoistArrayIndex(ArrayInstructionInterface* array_operation) {
   HValue* index = array_operation->GetKey();
   if (!index->representation().IsInteger32()) return;
@@ -4303,6 +5193,7 @@ bool HGraphBuilder::PreProcessOsrEntry(IterationStatement* statement) {
   non_osr_entry->Goto(loop_predecessor);
 
   set_current_block(osr_entry);
+  osr_entry->set_osr_entry();
   BailoutId osr_entry_id = statement->OsrEntryId();
   int first_expression_index = environment()->first_expression_index();
   int length = environment()->length();