From 01080fa7dcdc3a7ddfcd5d67c1d912398a871f4f Mon Sep 17 00:00:00 2001
From: "bmeurer@chromium.org"
 <bmeurer@chromium.org@ce2b1a6d-e550-0410-aec6-3dcde31c8c00>
Date: Mon, 15 Jul 2013 09:53:46 +0000
Subject: [PATCH] Fix possible stack overflow in range analysis.

Avoid the implicit recursion for range analysis, using a loop with
an explicit stack instead.

BUG=chromium:259452
R=dslomov@chromium.org

Review URL: https://codereview.chromium.org/19145002

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@15661 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
---
 src/hydrogen-range-analysis.cc | 84 ++++++++++++++++++++++++++++--------------
 src/hydrogen-range-analysis.h  |  5 +--
 2 files changed, 58 insertions(+), 31 deletions(-)

diff --git a/src/hydrogen-range-analysis.cc b/src/hydrogen-range-analysis.cc
index ed254db..76fd5f3 100644
--- a/src/hydrogen-range-analysis.cc
+++ b/src/hydrogen-range-analysis.cc
@@ -31,6 +31,20 @@ namespace v8 {
 namespace internal {
 
 
+class Pending {
+ public:
+  Pending(HBasicBlock* block, int last_changed_range)
+      : block_(block), last_changed_range_(last_changed_range) {}
+
+  HBasicBlock* block() const { return block_; }
+  int last_changed_range() const { return last_changed_range_; }
+
+ private:
+  HBasicBlock* block_;
+  int last_changed_range_;
+};
+
+
 void HRangeAnalysisPhase::TraceRange(const char* msg, ...) {
   if (FLAG_trace_range) {
     va_list arguments;
@@ -41,37 +55,52 @@ void HRangeAnalysisPhase::TraceRange(const char* msg, ...) {
 }
 
 
-void HRangeAnalysisPhase::Analyze(HBasicBlock* block) {
-  TraceRange("Analyzing block B%d\n", block->block_id());
-
-  int last_changed_range = changed_ranges_.length() - 1;
+void HRangeAnalysisPhase::Run() {
+  HBasicBlock* block(graph()->entry_block());
+  ZoneList<Pending> stack(graph()->blocks()->length(), zone());
+  while (block != NULL) {
+    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);
+    // 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);
-  }
+    // 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());
-  }
+    // 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));
+    // 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() - 1; i > 0; --i) {
+        stack.Add(Pending(dominated_blocks->at(i), last_changed_range), zone());
+      }
+      block = dominated_blocks->at(0);
+    } else if (!stack.is_empty()) {
+      // Pop next pending block from stack.
+      Pending pending = stack.RemoveLast();
+      RollBackTo(pending.last_changed_range());
+      block = pending.block();
+    } else {
+      // All blocks done.
+      block = NULL;
+    }
   }
-
-  RollBackTo(last_changed_range);
 }
 
 
@@ -140,10 +169,11 @@ void HRangeAnalysisPhase::InferRange(HValue* value) {
 
 
 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);
 }
 
 
diff --git a/src/hydrogen-range-analysis.h b/src/hydrogen-range-analysis.h
index b699d3a..a1e9737 100644
--- a/src/hydrogen-range-analysis.h
+++ b/src/hydrogen-range-analysis.h
@@ -39,13 +39,10 @@ class HRangeAnalysisPhase : public HPhase {
   explicit HRangeAnalysisPhase(HGraph* graph)
       : HPhase("H_Range analysis", graph), changed_ranges_(16, zone()) { }
 
-  void Run() {
-    Analyze(graph()->entry_block());
-  }
+  void Run();
 
  private:
   void TraceRange(const char* msg, ...);
-  void Analyze(HBasicBlock* block);
   void InferControlFlowRange(HCompareNumericAndBranch* test,
                              HBasicBlock* dest);
   void UpdateControlFlowRange(Token::Value op, HValue* value, HValue* other);
-- 
2.7.4