Make bounds check elimination iterative instead of recursive.

src/hydrogen-bce.cc

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 300 matching lines @@
                               Zone* zone) {
   Lookup(key, key->Hash(), true, ZoneAllocationPolicy(zone))->value = data;
 }
 
 
 void BoundsCheckTable::Delete(BoundsCheckKey* key) {
   Remove(key, key->Hash());
 }
 
 
+class HBoundsCheckEliminationState {
+ public:
+  HBasicBlock* block_;
+  BoundsCheckBbData* bb_data_list_;
+  int index_;
+};
+
+
 // Eliminates checks in bb and recursively in the dominated blocks.
 // Also replace the results of check instructions with the original value, if
 // the result is used. This is safe now, since we don't do code motion after
 // this point. It enables better register allocation since the value produced
 // by check instructions is really a copy of the original value.
 void HBoundsCheckEliminationPhase::EliminateRedundantBoundsChecks(
+    HBasicBlock* entry) {
+  // Allocate the stack.
+  HBoundsCheckEliminationState* stack =
+    zone()->NewArray<HBoundsCheckEliminationState>(graph()->blocks()->length());
+
+  // Explicitly push the entry block.
+  stack[0].block_ = entry;
+  stack[0].bb_data_list_ = PreProcessBlock(entry);
+  stack[0].index_ = 0;
+  int stack_depth = 1;
+
+  // Implement depth-first traversal with a stack.
+  while (stack_depth > 0) {
+    int current = stack_depth - 1;
+    HBoundsCheckEliminationState* state = &stack[current];
+    const ZoneList<HBasicBlock*>* children = state->block_->dominated_blocks();
+
+    if (state->index_ < children->length()) {
+      // Recursively visit children blocks.
+      HBasicBlock* child = children->at(state->index_++);
+      int next = stack_depth++;
+      stack[next].block_ = child;
+      stack[next].bb_data_list_ = PreProcessBlock(child);
+      stack[next].index_ = 0;
+    } else {
+      // Finished with all children; post process the block.
+      PostProcessBlock(state->block_, state->bb_data_list_);
+      stack_depth--;
+    }
+  }
+}
+
+
+BoundsCheckBbData* HBoundsCheckEliminationPhase::PreProcessBlock(
     HBasicBlock* bb) {
   BoundsCheckBbData* bb_data_list = NULL;
 
   for (HInstructionIterator it(bb); !it.Done(); it.Advance()) {
     HInstruction* i = it.Current();
     if (!i->IsBoundsCheck()) continue;
 
     HBoundsCheck* check = HBoundsCheck::cast(i);
     int32_t offset;
     BoundsCheckKey* key =
@@ skipping 31 matching lines @@
                                                    new_upper_offset,
                                                    bb,
                                                    data->LowerCheck(),
                                                    data->UpperCheck(),
                                                    bb_data_list,
                                                    data);
       table_.Insert(key, bb_data_list, zone());
     }
   }
 
-  for (int i = 0; i < bb->dominated_blocks()->length(); ++i) {
-    EliminateRedundantBoundsChecks(bb->dominated_blocks()->at(i));
-  }
+  return bb_data_list;
+}
 
-  for (BoundsCheckBbData* data = bb_data_list;
-       data != NULL;
-       data = data->NextInBasicBlock()) {
+
+void HBoundsCheckEliminationPhase::PostProcessBlock(
+    HBasicBlock* block, BoundsCheckBbData* data) {
+  while (data != NULL) {
     data->RemoveZeroOperations();
     if (data->FatherInDominatorTree()) {
       table_.Insert(data->Key(), data->FatherInDominatorTree(), zone());
     } else {
       table_.Delete(data->Key());
     }
+    data = data->NextInBasicBlock();
   }
 }
 
 } }  // namespace v8::internal