[coverage] Rework continuation counter handling

This changes a few bits about how continuation counters are handled. It introduces a new mechanism that allows removal of a continuation range after it has been created. If coverage is enabled, we run a first post-processing pass on the AST immediately after parsing, which removes problematic continuation ranges in two situations: 1. nested continuation counters - only the outermost stays alive. 2. trailing continuation counters within a block-like structure are removed if the containing structure itself has a continuation. R=bmeurer@chromium.org, jgruber@chromium.org, yangguo@chromium.org Bug: v8:8381, v8:8539 Change-Id: I6bcaea5060d8c481d7bae099f6db9f993cc30ee3 Reviewed-on: https://chromium-review.googlesource.com/c/1339119 Reviewed-by: Yang Guo <yangguo@chromium.org> Reviewed-by: Leszek Swirski <leszeks@chromium.org> Reviewed-by: Georg Neis <neis@chromium.org> Commit-Queue: Jakob Gruber <jgruber@chromium.org> Cr-Commit-Position: refs/heads/master@{#58443}
v8 · Dec 21, 2018 · 9365d09 · 9365d09
1 parent 491eff8
commit 9365d09
Show file tree

Hide file tree

Showing 12 changed files with 382 additions and 162 deletions.
diff --git a/BUILD.gn b/BUILD.gn
@@ -1668,6 +1668,8 @@ v8_source_set("v8_base") {
     "src/ast/prettyprinter.h",
     "src/ast/scopes.cc",
     "src/ast/scopes.h",
+    "src/ast/source-range-ast-visitor.cc",
+    "src/ast/source-range-ast-visitor.h",
     "src/ast/variables.cc",
     "src/ast/variables.h",
     "src/bailout-reason.cc",

diff --git a/src/ast/ast-source-ranges.h b/src/ast/ast-source-ranges.h
@@ -59,6 +59,8 @@ class AstNodeSourceRanges : public ZoneObject {
  public:
   virtual ~AstNodeSourceRanges() = default;
   virtual SourceRange GetRange(SourceRangeKind kind) = 0;
+  virtual bool HasRange(SourceRangeKind kind) = 0;
+  virtual void RemoveContinuationRange() { UNREACHABLE(); }
 };
 
 class BinaryOperationSourceRanges final : public AstNodeSourceRanges {
@@ -67,10 +69,14 @@ class BinaryOperationSourceRanges final : public AstNodeSourceRanges {
       : right_range_(right_range) {}
 
   SourceRange GetRange(SourceRangeKind kind) override {
-    DCHECK_EQ(kind, SourceRangeKind::kRight);
+    DCHECK(HasRange(kind));
     return right_range_;
   }
 
+  bool HasRange(SourceRangeKind kind) override {
+    return kind == SourceRangeKind::kRight;
+  }
+
  private:
   SourceRange right_range_;
 };
@@ -81,10 +87,19 @@ class ContinuationSourceRanges : public AstNodeSourceRanges {
       : continuation_position_(continuation_position) {}
 
   SourceRange GetRange(SourceRangeKind kind) override {
-    DCHECK_EQ(kind, SourceRangeKind::kContinuation);
+    DCHECK(HasRange(kind));
     return SourceRange::OpenEnded(continuation_position_);
   }
 
+  bool HasRange(SourceRangeKind kind) override {
+    return kind == SourceRangeKind::kContinuation;
+  }
+
+  void RemoveContinuationRange() override {
+    DCHECK(HasRange(SourceRangeKind::kContinuation));
+    continuation_position_ = kNoSourcePosition;
+  }
+
  private:
   int32_t continuation_position_;
 };
@@ -101,10 +116,14 @@ class CaseClauseSourceRanges final : public AstNodeSourceRanges {
       : body_range_(body_range) {}
 
   SourceRange GetRange(SourceRangeKind kind) override {
-    DCHECK_EQ(kind, SourceRangeKind::kBody);
+    DCHECK(HasRange(kind));
     return body_range_;
   }
 
+  bool HasRange(SourceRangeKind kind) override {
+    return kind == SourceRangeKind::kBody;
+  }
+
  private:
   SourceRange body_range_;
 };
@@ -116,6 +135,7 @@ class ConditionalSourceRanges final : public AstNodeSourceRanges {
       : then_range_(then_range), else_range_(else_range) {}
 
   SourceRange GetRange(SourceRangeKind kind) override {
+    DCHECK(HasRange(kind));
     switch (kind) {
       case SourceRangeKind::kThen:
         return then_range_;
@@ -126,6 +146,10 @@ class ConditionalSourceRanges final : public AstNodeSourceRanges {
     }
   }
 
+  bool HasRange(SourceRangeKind kind) override {
+    return kind == SourceRangeKind::kThen || kind == SourceRangeKind::kElse;
+  }
+
  private:
   SourceRange then_range_;
   SourceRange else_range_;
@@ -138,12 +162,14 @@ class IfStatementSourceRanges final : public AstNodeSourceRanges {
       : then_range_(then_range), else_range_(else_range) {}
 
   SourceRange GetRange(SourceRangeKind kind) override {
+    DCHECK(HasRange(kind));
     switch (kind) {
       case SourceRangeKind::kElse:
         return else_range_;
       case SourceRangeKind::kThen:
         return then_range_;
       case SourceRangeKind::kContinuation: {
+        if (!has_continuation_) return SourceRange::Empty();
         const SourceRange& trailing_range =
             else_range_.IsEmpty() ? then_range_ : else_range_;
         return SourceRange::ContinuationOf(trailing_range);
@@ -153,9 +179,20 @@ class IfStatementSourceRanges final : public AstNodeSourceRanges {
     }
   }
 
+  bool HasRange(SourceRangeKind kind) override {
+    return kind == SourceRangeKind::kThen || kind == SourceRangeKind::kElse ||
+           kind == SourceRangeKind::kContinuation;
+  }
+
+  void RemoveContinuationRange() override {
+    DCHECK(HasRange(SourceRangeKind::kContinuation));
+    has_continuation_ = false;
+  }
+
  private:
   SourceRange then_range_;
   SourceRange else_range_;
+  bool has_continuation_ = true;
 };
 
 class IterationStatementSourceRanges final : public AstNodeSourceRanges {
@@ -164,18 +201,31 @@ class IterationStatementSourceRanges final : public AstNodeSourceRanges {
       : body_range_(body_range) {}
 
   SourceRange GetRange(SourceRangeKind kind) override {
+    DCHECK(HasRange(kind));
     switch (kind) {
       case SourceRangeKind::kBody:
         return body_range_;
       case SourceRangeKind::kContinuation:
+        if (!has_continuation_) return SourceRange::Empty();
         return SourceRange::ContinuationOf(body_range_);
       default:
         UNREACHABLE();
     }
   }
 
+  bool HasRange(SourceRangeKind kind) override {
+    return kind == SourceRangeKind::kBody ||
+           kind == SourceRangeKind::kContinuation;
+  }
+
+  void RemoveContinuationRange() override {
+    DCHECK(HasRange(SourceRangeKind::kContinuation));
+    has_continuation_ = false;
+  }
+
  private:
   SourceRange body_range_;
+  bool has_continuation_ = true;
 };
 
 class JumpStatementSourceRanges final : public ContinuationSourceRanges {
@@ -200,6 +250,7 @@ class NaryOperationSourceRanges final : public AstNodeSourceRanges {
   size_t RangeCount() const { return ranges_.size(); }
 
   SourceRange GetRange(SourceRangeKind kind) override { UNREACHABLE(); }
+  bool HasRange(SourceRangeKind kind) override { return false; }
 
  private:
   ZoneVector<SourceRange> ranges_;
@@ -229,18 +280,31 @@ class TryCatchStatementSourceRanges final : public AstNodeSourceRanges {
       : catch_range_(catch_range) {}
 
   SourceRange GetRange(SourceRangeKind kind) override {
+    DCHECK(HasRange(kind));
     switch (kind) {
       case SourceRangeKind::kCatch:
         return catch_range_;
       case SourceRangeKind::kContinuation:
+        if (!has_continuation_) return SourceRange::Empty();
         return SourceRange::ContinuationOf(catch_range_);
       default:
         UNREACHABLE();
     }
   }
 
+  bool HasRange(SourceRangeKind kind) override {
+    return kind == SourceRangeKind::kCatch ||
+           kind == SourceRangeKind::kContinuation;
+  }
+
+  void RemoveContinuationRange() override {
+    DCHECK(HasRange(SourceRangeKind::kContinuation));
+    has_continuation_ = false;
+  }
+
  private:
   SourceRange catch_range_;
+  bool has_continuation_ = true;
 };
 
 class TryFinallyStatementSourceRanges final : public AstNodeSourceRanges {
@@ -249,18 +313,31 @@ class TryFinallyStatementSourceRanges final : public AstNodeSourceRanges {
       : finally_range_(finally_range) {}
 
   SourceRange GetRange(SourceRangeKind kind) override {
+    DCHECK(HasRange(kind));
     switch (kind) {
       case SourceRangeKind::kFinally:
         return finally_range_;
       case SourceRangeKind::kContinuation:
+        if (!has_continuation_) return SourceRange::Empty();
         return SourceRange::ContinuationOf(finally_range_);
       default:
         UNREACHABLE();
     }
   }
 
+  bool HasRange(SourceRangeKind kind) override {
+    return kind == SourceRangeKind::kFinally ||
+           kind == SourceRangeKind::kContinuation;
+  }
+
+  void RemoveContinuationRange() override {
+    DCHECK(HasRange(SourceRangeKind::kContinuation));
+    has_continuation_ = false;
+  }
+
  private:
   SourceRange finally_range_;
+  bool has_continuation_ = true;
 };
 
 // Maps ast node pointers to associated source ranges. The parser creates these

diff --git a/src/ast/source-range-ast-visitor.cc b/src/ast/source-range-ast-visitor.cc
@@ -0,0 +1,68 @@
+// Copyright 2018 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "src/ast/source-range-ast-visitor.h"
+
+#include "src/ast/ast-source-ranges.h"
+
+namespace v8 {
+namespace internal {
+
+SourceRangeAstVisitor::SourceRangeAstVisitor(uintptr_t stack_limit,
+                                             Expression* root,
+                                             SourceRangeMap* source_range_map)
+    : AstTraversalVisitor(stack_limit, root),
+      source_range_map_(source_range_map) {}
+
+void SourceRangeAstVisitor::VisitBlock(Block* stmt) {
+  AstTraversalVisitor::VisitBlock(stmt);
+  ZonePtrList<Statement>* stmts = stmt->statements();
+  AstNodeSourceRanges* enclosingSourceRanges = source_range_map_->Find(stmt);
+  if (enclosingSourceRanges != nullptr) {
+    CHECK(enclosingSourceRanges->HasRange(SourceRangeKind::kContinuation));
+    MaybeRemoveLastContinuationRange(stmts);
+  }
+}
+
+void SourceRangeAstVisitor::VisitFunctionLiteral(FunctionLiteral* expr) {
+  AstTraversalVisitor::VisitFunctionLiteral(expr);
+  ZonePtrList<Statement>* stmts = expr->body();
+  MaybeRemoveLastContinuationRange(stmts);
+}
+
+bool SourceRangeAstVisitor::VisitNode(AstNode* node) {
+  AstNodeSourceRanges* range = source_range_map_->Find(node);
+
+  if (range == nullptr) return true;
+  if (!range->HasRange(SourceRangeKind::kContinuation)) return true;
+
+  // Called in pre-order. In case of conflicting continuation ranges, only the
+  // outermost range may survive.
+
+  SourceRange continuation = range->GetRange(SourceRangeKind::kContinuation);
+  if (continuation_positions_.find(continuation.start) !=
+      continuation_positions_.end()) {
+    range->RemoveContinuationRange();
+  } else {
+    continuation_positions_.emplace(continuation.start);
+  }
+
+  return true;
+}
+
+void SourceRangeAstVisitor::MaybeRemoveLastContinuationRange(
+    ZonePtrList<Statement>* statements) {
+  if (statements->is_empty()) return;
+
+  Statement* last_statement = statements->last();
+  AstNodeSourceRanges* last_range = source_range_map_->Find(last_statement);
+  if (last_range == nullptr) return;
+
+  if (last_range->HasRange(SourceRangeKind::kContinuation)) {
+    last_range->RemoveContinuationRange();
+  }
+}
+
+}  // namespace internal
+}  // namespace v8
diff --git a/src/ast/source-range-ast-visitor.h b/src/ast/source-range-ast-visitor.h
@@ -0,0 +1,49 @@
+// Copyright 2018 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef V8_AST_SOURCE_RANGE_AST_VISITOR_H_
+#define V8_AST_SOURCE_RANGE_AST_VISITOR_H_
+
+#include <unordered_set>
+
+#include "src/ast/ast-traversal-visitor.h"
+
+namespace v8 {
+namespace internal {
+
+class SourceRangeMap;
+
+// Post-processes generated source ranges while the AST structure still exists.
+//
+// In particular, SourceRangeAstVisitor
+//
+// 1. deduplicates continuation source ranges, only keeping the outermost one.
+// See also: https://crbug.com/v8/8539.
+//
+// 2. removes the source range associated with the final statement in a block
+// or function body if the parent itself has a source range associated with it.
+// See also: https://crbug.com/v8/8381.
+class SourceRangeAstVisitor final
+    : public AstTraversalVisitor<SourceRangeAstVisitor> {
+ public:
+  SourceRangeAstVisitor(uintptr_t stack_limit, Expression* root,
+                        SourceRangeMap* source_range_map);
+
+ private:
+  friend class AstTraversalVisitor<SourceRangeAstVisitor>;
+
+  void VisitBlock(Block* stmt);
+  void VisitFunctionLiteral(FunctionLiteral* expr);
+  bool VisitNode(AstNode* node);
+
+  void MaybeRemoveLastContinuationRange(ZonePtrList<Statement>* stmts);
+
+  SourceRangeMap* source_range_map_ = nullptr;
+  std::unordered_set<int> continuation_positions_;
+};
+
+}  // namespace internal
+}  // namespace v8
+
+#endif  // V8_AST_SOURCE_RANGE_AST_VISITOR_H_
diff --git a/src/debug/debug-coverage.cc b/src/debug/debug-coverage.cc
@@ -233,25 +233,6 @@ bool HaveSameSourceRange(const CoverageBlock& lhs, const CoverageBlock& rhs) {
   return lhs.start == rhs.start && lhs.end == rhs.end;
 }
 
-void MergeDuplicateSingletons(CoverageFunction* function) {
-  CoverageBlockIterator iter(function);
-
-  while (iter.Next() && iter.HasNext()) {
-    CoverageBlock& block = iter.GetBlock();
-    CoverageBlock& next_block = iter.GetNextBlock();
-
-    // Identical ranges should only occur through singleton ranges. Consider the
-    // ranges for `for (.) break;`: continuation ranges for both the `break` and
-    // `for` statements begin after the trailing semicolon.
-    // Such ranges are merged and keep the maximal execution count.
-    if (!HaveSameSourceRange(block, next_block)) continue;
-
-    DCHECK_EQ(kNoSourcePosition, block.end);  // Singleton range.
-    next_block.count = std::max(block.count, next_block.count);
-    iter.DeleteBlock();
-  }
-}
-
 void MergeDuplicateRanges(CoverageFunction* function) {
   CoverageBlockIterator iter(function);
 
@@ -424,9 +405,6 @@ void CollectBlockCoverage(CoverageFunction* function, SharedFunctionInfo info,
   // If in binary mode, only report counts of 0/1.
   if (mode == debug::Coverage::kBlockBinary) ClampToBinary(function);
 
-  // Remove duplicate singleton ranges, keeping the max count.
-  MergeDuplicateSingletons(function);
-
   // Remove singleton ranges with the same start position as a full range and
   // throw away their counts.
   // Singleton ranges are only intended to split existing full ranges and should

diff --git a/src/interpreter/bytecode-generator.cc b/src/interpreter/bytecode-generator.cc
@@ -368,7 +368,6 @@ class BytecodeGenerator::ControlScopeForBreakable final
  protected:
   bool Execute(Command command, Statement* statement,
                int source_position) override {
-    control_builder_->set_needs_continuation_counter();
     if (statement != statement_) return false;
     switch (command) {
       case CMD_BREAK: