Fix possible stack overflow in range analysis.

src/hydrogen-range-analysis.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 13 matching lines @@
 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
 #include "hydrogen-range-analysis.h"
 
 namespace v8 {
 namespace internal {
 
 
-void HRangeAnalysisPhase::TraceRange(const char* msg, ...) {
+static void TraceRange(const char* msg, ...) {

[Dmitry Lomov (no reviews), 2013/07/15 09:12:06]

nit: Why this change? I liked the original one better, when this trace function
belonged to the class.

[Benedikt Meurer, 2013/07/15 09:17:29]

Done.

   if (FLAG_trace_range) {
     va_list arguments;
     va_start(arguments, msg);
     OS::VPrint(msg, arguments);
     va_end(arguments);
   }
 }
 
 
-void HRangeAnalysisPhase::Analyze(HBasicBlock* block) {
-  TraceRange("Analyzing block B%d\n", block->block_id());
+class Pending {
+ public:
+  Pending(HBasicBlock* block, int last_changed_range)
+      : block_(block), last_changed_range_(last_changed_range) {}
 
-  int last_changed_range = changed_ranges_.length() - 1;
+  HBasicBlock* block() const { return block_; }
+  int last_changed_range() const { return last_changed_range_; }
 
-  // Infer range based on control flow.
-  if (block->predecessors()->length() == 1) {
-    HBasicBlock* pred = block->predecessors()->first();
-    if (pred->end()->IsCompareNumericAndBranch()) {
-      InferControlFlowRange(HCompareNumericAndBranch::cast(pred->end()),
-                            block);
+ private:
+  HBasicBlock* block_;
+  int last_changed_range_;
+};
+
+
+void HRangeAnalysisPhase::Run() {
+  HBasicBlock* block(graph()->entry_block());
+  ZoneList<Pending> stack(graph()->blocks()->length(), zone());
+  for (;;) {

[Dmitry Lomov (no reviews), 2013/07/15 09:12:06]

Can we make the terminating condition for this loop more clear? block here is
"inlined" top of the stack, so how about having 'block != NULL' as a loop guard?

[Benedikt Meurer, 2013/07/15 09:17:29]

Done.

+    TraceRange("Analyzing block B%d\n", block->block_id());
+
+    // Infer range based on control flow.
+    if (block->predecessors()->length() == 1) {
+      HBasicBlock* pred = block->predecessors()->first();
+      if (pred->end()->IsCompareNumericAndBranch()) {
+        InferControlFlowRange(HCompareNumericAndBranch::cast(pred->end()),
+                              block);
+      }
+    }
+
+    // Process phi instructions.
+    for (int i = 0; i < block->phis()->length(); ++i) {
+      HPhi* phi = block->phis()->at(i);
+      InferRange(phi);
+    }
+
+    // Go through all instructions of the current block.
+    for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
+      InferRange(it.Current());
+    }
+
+    // Continue analysis in all dominated blocks.
+    const ZoneList<HBasicBlock*>* dominated_blocks(block->dominated_blocks());
+    if (!dominated_blocks->is_empty()) {
+      // Continue with first dominated block, and push the
+      // remaining blocks on the stack (in reverse order).
+      int last_changed_range = changed_ranges_.length();
+      for (int i = dominated_blocks->length(); --i > 0; ) {
+        stack.Add(Pending(dominated_blocks->at(i), last_changed_range), zone());
+      }
+      block = dominated_blocks->at(0);
+    } else if (stack.is_empty()) {
+      break;
+    } else {
+      // Pop next pending block from stack.
+      Pending pending = stack.RemoveLast();
+      RollBackTo(pending.last_changed_range());
+      block = pending.block();
     }
   }
-
-  // Process phi instructions.
-  for (int i = 0; i < block->phis()->length(); ++i) {
-    HPhi* phi = block->phis()->at(i);
-    InferRange(phi);
-  }
-
-  // Go through all instructions of the current block.
-  for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
-    InferRange(it.Current());
-  }
-
-  // Continue analysis in all dominated blocks.
-  for (int i = 0; i < block->dominated_blocks()->length(); ++i) {
-    Analyze(block->dominated_blocks()->at(i));
-  }
-
-  RollBackTo(last_changed_range);
 }
 
 
 void HRangeAnalysisPhase::InferControlFlowRange(HCompareNumericAndBranch* test,
                                                 HBasicBlock* dest) {
   ASSERT((test->FirstSuccessor() == dest) == (test->SecondSuccessor() != dest));
   if (test->representation().IsSmiOrInteger32()) {
     Token::Value op = test->token();
     if (test->SecondSuccessor() == dest) {
       op = Token::NegateCompareOp(op);
@@ skipping 48 matching lines @@
     TraceRange("Initial inferred range of %d (%s) set to [%d,%d]\n",
                value->id(),
                value->Mnemonic(),
                range->lower(),
                range->upper());
   }
 }
 
 
 void HRangeAnalysisPhase::RollBackTo(int index) {
-  for (int i = index + 1; i < changed_ranges_.length(); ++i) {
+  ASSERT(index <= changed_ranges_.length());
+  for (int i = index; i < changed_ranges_.length(); ++i) {
     changed_ranges_[i]->RemoveLastAddedRange();
   }
-  changed_ranges_.Rewind(index + 1);
+  changed_ranges_.Rewind(index);
 }
 
 
 void HRangeAnalysisPhase::AddRange(HValue* value, Range* range) {
   Range* original_range = value->range();
   value->AddNewRange(range, graph()->zone());
   changed_ranges_.Add(value, zone());
   Range* new_range = value->range();
   TraceRange("Updated range of %d set to [%d,%d]\n",
              value->id(),
              new_range->lower(),
              new_range->upper());
   if (original_range != NULL) {
     TraceRange("Original range was [%d,%d]\n",
                original_range->lower(),
                original_range->upper());
   }
   TraceRange("New information was [%d,%d]\n",
              range->lower(),
              range->upper());
 }
 
 
 } }  // namespace v8::internal