[interpreter] VisitForTest for bytecode generator

src/interpreter/bytecode-generator.cc

 // Copyright 2015 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/interpreter/bytecode-generator.h"
 
 #include "src/ast/scopes.h"
 #include "src/code-stubs.h"
 #include "src/compiler.h"
 #include "src/interpreter/bytecode-flags.h"
+#include "src/interpreter/bytecode-label.h"
 #include "src/interpreter/bytecode-register-allocator.h"
 #include "src/interpreter/control-flow-builders.h"
 #include "src/objects.h"
 #include "src/parsing/parser.h"
 #include "src/parsing/token.h"
 
 namespace v8 {
 namespace internal {
 namespace interpreter {
 
@@ skipping 417 matching lines @@
     generator_->set_execution_result(this);
   }
 
   virtual ~ExpressionResultScope() {
     generator_->set_execution_result(outer_);
     DCHECK(result_identified() || generator_->HasStackOverflow());
   }
 
   bool IsEffect() const { return kind_ == Expression::kEffect; }
   bool IsValue() const { return kind_ == Expression::kValue; }
+  bool IsTest() const { return kind_ == Expression::kTest; }
+
+  TestResultScope* AsTest() {
+    DCHECK(IsTest());
+    return reinterpret_cast<TestResultScope*>(this);
+  }
 
   virtual void SetResultInAccumulator() = 0;
   virtual void SetResultInRegister(Register reg) = 0;
 
  protected:
   ExpressionResultScope* outer() const { return outer_; }
   BytecodeArrayBuilder* builder() const { return generator_->builder(); }
   BytecodeGenerator* generator() const { return generator_; }
   const RegisterAllocationScope* allocator() const { return &allocator_; }
 
@@ skipping 70 matching lines @@
     if (generator()->HasStackOverflow() && !result_identified()) {
       SetResultInAccumulator();
     }
     return result_register_;
   }
 
  private:
   Register result_register_;
 };
 
+// Scoped class used when the result of the current expression to be
+// evaluated is only tested with jumps to two branches.
+class BytecodeGenerator::TestResultScope final : public ExpressionResultScope {
+ public:
+  TestResultScope(BytecodeGenerator* generator, BytecodeLabels* then_labels,
+                  BytecodeLabels* else_labels, TestFallthrough fallthrough)
+      : ExpressionResultScope(generator, Expression::kTest),
+        then_labels_(then_labels),
+        else_labels_(else_labels),
+        fallthrough_(fallthrough),
+        result_consumed_by_test_(false) {}
+
+  virtual void SetResultInAccumulator() { set_result_identified(); }
+
+  virtual void SetResultInRegister(Register reg) {
+    builder()->LoadAccumulatorWithRegister(reg);
+    set_result_identified();
+  }
+
+  // Used when code special cases for TestResultScope and consumes any
+  // possible value by testing and jumping to a then/else label.
+  void SetResultConsumedByTest() {
+    result_consumed_by_test_ = true;
+    set_result_identified();
+  }
+
+  bool ResultConsumedByTest() { return result_consumed_by_test_; }
+
+  BytecodeLabel* NewThenLabel() { return then_labels_->New(); }
+  BytecodeLabel* NewElseLabel() { return else_labels_->New(); }
+
+  BytecodeLabels* then_labels() const { return then_labels_; }
+  BytecodeLabels* else_labels() const { return else_labels_; }
+
+  TestFallthrough fallthrough() const { return fallthrough_; }
+  TestFallthrough inverted_fallthrough() const {
+    switch (fallthrough_) {
+      case TestFallthrough::kThen:
+        return TestFallthrough::kElse;
+      case TestFallthrough::kElse:
+        return TestFallthrough::kThen;
+      default:
+        return TestFallthrough::kNone;
+    }
+  }
+
+ private:
+  BytecodeLabels* then_labels_;
+  BytecodeLabels* else_labels_;
+  TestFallthrough fallthrough_;
+  bool result_consumed_by_test_;
+
+  DISALLOW_COPY_AND_ASSIGN(TestResultScope);
+};
+
 // Used to build a list of global declaration initial value pairs.
 class BytecodeGenerator::GlobalDeclarationsBuilder final : public ZoneObject {
  public:
   GlobalDeclarationsBuilder(Isolate* isolate, Zone* zone)
       : isolate_(isolate),
         declarations_(0, zone),
         constant_pool_entry_(0),
         has_constant_pool_entry_(false) {}
 
   void AddFunctionDeclaration(FeedbackVectorSlot slot, FunctionLiteral* func) {
@@ skipping 428 matching lines @@
 void BytecodeGenerator::VisitExpressionStatement(ExpressionStatement* stmt) {
   builder()->SetStatementPosition(stmt);
   VisitForEffect(stmt->expression());
 }
 
 void BytecodeGenerator::VisitEmptyStatement(EmptyStatement* stmt) {
 }
 
 void BytecodeGenerator::VisitIfStatement(IfStatement* stmt) {
   builder()->SetStatementPosition(stmt);
-  BytecodeLabel else_label, end_label;
   if (stmt->condition()->ToBooleanIsTrue()) {
     // Generate then block unconditionally as always true.
     Visit(stmt->then_statement());
   } else if (stmt->condition()->ToBooleanIsFalse()) {
     // Generate else block unconditionally if it exists.
     if (stmt->HasElseStatement()) {
       Visit(stmt->else_statement());
     }
   } else {
     // TODO(oth): If then statement is BreakStatement or
     // ContinueStatement we can reduce number of generated
     // jump/jump_ifs here. See BasicLoops test.
-    VisitForAccumulatorValue(stmt->condition());
-    builder()->JumpIfFalse(&else_label);
+    BytecodeLabel end_label;
+    BytecodeLabels then_labels(zone()), else_labels(zone());
+    VisitForTest(stmt->condition(), &then_labels, &else_labels,
+                 TestFallthrough::kThen);
+
+    then_labels.Bind(builder());
     Visit(stmt->then_statement());
+
     if (stmt->HasElseStatement()) {
       builder()->Jump(&end_label);
-      builder()->Bind(&else_label);
+      else_labels.Bind(builder());
       Visit(stmt->else_statement());
     } else {
-      builder()->Bind(&else_label);
+      else_labels.Bind(builder());
     }
     builder()->Bind(&end_label);
   }
 }
 
 void BytecodeGenerator::VisitSloppyBlockFunctionStatement(
     SloppyBlockFunctionStatement* stmt) {
   Visit(stmt->statement());
 }
 
@@ skipping 88 matching lines @@
   if (stmt->cond()->ToBooleanIsFalse()) {
     VisitIterationBody(stmt, &loop_builder);
   } else if (stmt->cond()->ToBooleanIsTrue()) {
     VisitIterationHeader(stmt, &loop_builder);
     VisitIterationBody(stmt, &loop_builder);
     loop_builder.JumpToHeader();
   } else {
     VisitIterationHeader(stmt, &loop_builder);
     VisitIterationBody(stmt, &loop_builder);
     builder()->SetExpressionAsStatementPosition(stmt->cond());
+    // TODO(klaasb) VisitForTest for loop conditions
     VisitForAccumulatorValue(stmt->cond());
     loop_builder.JumpToHeaderIfTrue();
   }
   loop_builder.EndLoop();
 }
 
 void BytecodeGenerator::VisitWhileStatement(WhileStatement* stmt) {
   if (stmt->cond()->ToBooleanIsFalse()) {
     // If the condition is false there is no need to generate the loop.
     return;
   }
 
   LoopBuilder loop_builder(builder());
   VisitIterationHeader(stmt, &loop_builder);
   if (!stmt->cond()->ToBooleanIsTrue()) {
     builder()->SetExpressionAsStatementPosition(stmt->cond());
+    // TODO(klaasb) VisitForTest for loop conditions
     VisitForAccumulatorValue(stmt->cond());
     loop_builder.BreakIfFalse();
   }
   VisitIterationBody(stmt, &loop_builder);
   loop_builder.JumpToHeader();
   loop_builder.EndLoop();
 }
 
 void BytecodeGenerator::VisitForStatement(ForStatement* stmt) {
   if (stmt->init() != nullptr) {
     Visit(stmt->init());
   }
   if (stmt->cond() && stmt->cond()->ToBooleanIsFalse()) {
     // If the condition is known to be false there is no need to generate
     // body, next or condition blocks. Init block should be generated.
     return;
   }
 
   LoopBuilder loop_builder(builder());
   VisitIterationHeader(stmt, &loop_builder);
   if (stmt->cond() && !stmt->cond()->ToBooleanIsTrue()) {
     builder()->SetExpressionAsStatementPosition(stmt->cond());
+    // TODO(klaasb) VisitForTest for loop conditions
     VisitForAccumulatorValue(stmt->cond());
     loop_builder.BreakIfFalse();
   }
   VisitIterationBody(stmt, &loop_builder);
   if (stmt->next() != nullptr) {
     builder()->SetStatementPosition(stmt->next());
     Visit(stmt->next());
   }
   loop_builder.JumpToHeader();
   loop_builder.EndLoop();
@@ skipping 398 matching lines @@
   native_function_literals_.push_back(std::make_pair(expr, entry));
   execution_result()->SetResultInAccumulator();
 }
 
 void BytecodeGenerator::VisitDoExpression(DoExpression* expr) {
   VisitBlock(expr->block());
   VisitVariableProxy(expr->result());
 }
 
 void BytecodeGenerator::VisitConditional(Conditional* expr) {
-  // TODO(rmcilroy): Spot easy cases where there code would not need to
-  // emit the then block or the else block, e.g. condition is
-  // obviously true/1/false/0.
+  if (expr->condition()->ToBooleanIsTrue()) {
+    // Generate then block unconditionally as always true.
+    VisitForAccumulatorValue(expr->then_expression());
+  } else if (expr->condition()->ToBooleanIsFalse()) {
+    // Generate else block unconditionally if it exists.
+    VisitForAccumulatorValue(expr->else_expression());
+  } else {
+    BytecodeLabel end_label;
+    BytecodeLabels then_labels(zone()), else_labels(zone());
 
-  BytecodeLabel else_label, end_label;
+    VisitForTest(expr->condition(), &then_labels, &else_labels,
+                 TestFallthrough::kThen);
 
-  VisitForAccumulatorValue(expr->condition());
-  builder()->JumpIfFalse(&else_label);
+    then_labels.Bind(builder());
+    VisitForAccumulatorValue(expr->then_expression());
+    builder()->Jump(&end_label);
 
-  VisitForAccumulatorValue(expr->then_expression());
-  builder()->Jump(&end_label);
-
-  builder()->Bind(&else_label);
-  VisitForAccumulatorValue(expr->else_expression());
-  builder()->Bind(&end_label);
+    else_labels.Bind(builder());
+    VisitForAccumulatorValue(expr->else_expression());
+    builder()->Bind(&end_label);
+  }
 
   execution_result()->SetResultInAccumulator();
 }
 
 void BytecodeGenerator::VisitLiteral(Literal* expr) {
   if (!execution_result()->IsEffect()) {
     const AstValue* raw_value = expr->raw_value();
     if (raw_value->IsSmi()) {
       builder()->LoadLiteral(raw_value->AsSmi());
     } else if (raw_value->IsUndefined()) {
@@ skipping 262 matching lines @@
     BuildThrowIfHole(variable->name());
   }
 }
 
 void BytecodeGenerator::VisitVariableLoad(Variable* variable,
                                           FeedbackVectorSlot slot,
                                           TypeofMode typeof_mode) {
   switch (variable->location()) {
     case VariableLocation::LOCAL: {
       Register source(Register(variable->index()));
+      // We need to load the variable into the accumulator, even when in a
+      // VisitForRegisterScope, in order to avoid register aliasing if
+      // subsequent expressions assign to the same variable.
       builder()->LoadAccumulatorWithRegister(source);
       BuildHoleCheckForVariableLoad(variable);
       break;
     }
     case VariableLocation::PARAMETER: {
       // The parameter indices are shifted by 1 (receiver is variable
       // index -1 but is parameter index 0 in BytecodeArrayBuilder).
       Register source = builder()->Parameter(variable->index() + 1);
+      // We need to load the variable into the accumulator, even when in a
+      // VisitForRegisterScope, in order to avoid register aliasing if
+      // subsequent expressions assign to the same variable.
       builder()->LoadAccumulatorWithRegister(source);
       BuildHoleCheckForVariableLoad(variable);
       break;
     }
     case VariableLocation::GLOBAL:
     case VariableLocation::UNALLOCATED: {
       builder()->LoadGlobal(feedback_index(slot), typeof_mode);
       break;
     }
     case VariableLocation::CONTEXT: {
@@ skipping 824 matching lines @@
     VisitVariableLoadForAccumulatorValue(
         proxy->var(), proxy->VariableFeedbackSlot(), INSIDE_TYPEOF);
   } else {
     VisitForAccumulatorValue(expr->expression());
   }
   builder()->TypeOf();
   execution_result()->SetResultInAccumulator();
 }
 
 void BytecodeGenerator::VisitNot(UnaryOperation* expr) {
-  VisitForAccumulatorValue(expr->expression());
-  builder()->LogicalNot();
-  execution_result()->SetResultInAccumulator();
+  if (execution_result()->IsEffect()) {
+    VisitForEffect(expr->expression());
+  } else if (execution_result()->IsTest()) {
+    TestResultScope* test_result = execution_result()->AsTest();
+    // No actual logical negation happening, we just swap the control flow by
+    // swapping the target labels and the fallthrough branch.
+    VisitForTest(expr->expression(), test_result->else_labels(),
+                 test_result->then_labels(),
+                 test_result->inverted_fallthrough());
+    test_result->SetResultConsumedByTest();
+  } else {
+    VisitForAccumulatorValue(expr->expression());
+    builder()->LogicalNot();
+    execution_result()->SetResultInAccumulator();
+  }
 }
 
 void BytecodeGenerator::VisitUnaryOperation(UnaryOperation* expr) {
   switch (expr->op()) {
     case Token::Value::NOT:
       VisitNot(expr);
       break;
     case Token::Value::TYPEOF:
       VisitTypeOf(expr);
       break;
@@ skipping 255 matching lines @@
 
 void BytecodeGenerator::VisitCommaExpression(BinaryOperation* binop) {
   VisitForEffect(binop->left());
   Visit(binop->right());
 }
 
 void BytecodeGenerator::VisitLogicalOrExpression(BinaryOperation* binop) {
   Expression* left = binop->left();
   Expression* right = binop->right();
 
-  // Short-circuit evaluation- If it is known that left is always true,
-  // no need to visit right
-  if (left->ToBooleanIsTrue()) {
-    VisitForAccumulatorValue(left);
+  if (execution_result()->IsTest()) {
+    TestResultScope* test_result = execution_result()->AsTest();
+
+    if (left->ToBooleanIsTrue() || right->ToBooleanIsTrue()) {
+      builder()->Jump(test_result->NewThenLabel());
+    } else if (left->ToBooleanIsFalse() && right->ToBooleanIsFalse()) {
+      builder()->Jump(test_result->NewElseLabel());
+    } else {
+      BytecodeLabels test_right(zone());
+      VisitForTest(left, test_result->then_labels(), &test_right,
+                   TestFallthrough::kElse);
+      test_right.Bind(builder());
+      VisitForTest(right, test_result->then_labels(),
+                   test_result->else_labels(), test_result->fallthrough());
+    }
+    test_result->SetResultConsumedByTest();
   } else {
-    BytecodeLabel end_label;
-    VisitForAccumulatorValue(left);
-    builder()->JumpIfTrue(&end_label);
-    VisitForAccumulatorValue(right);
-    builder()->Bind(&end_label);
+    if (left->ToBooleanIsTrue()) {
+      VisitForAccumulatorValue(left);
+    } else if (left->ToBooleanIsFalse()) {
+      VisitForAccumulatorValue(right);
+    } else {
+      BytecodeLabel end_label;
+      VisitForAccumulatorValue(left);
+      builder()->JumpIfTrue(&end_label);
+      VisitForAccumulatorValue(right);
+      builder()->Bind(&end_label);
+    }
+    execution_result()->SetResultInAccumulator();
   }
-  execution_result()->SetResultInAccumulator();
 }
 
 void BytecodeGenerator::VisitLogicalAndExpression(BinaryOperation* binop) {
   Expression* left = binop->left();
   Expression* right = binop->right();
 
-  // Short-circuit evaluation- If it is known that left is always false,
-  // no need to visit right
-  if (left->ToBooleanIsFalse()) {
-    VisitForAccumulatorValue(left);
+  if (execution_result()->IsTest()) {
+    TestResultScope* test_result = execution_result()->AsTest();
+
+    if (left->ToBooleanIsFalse() || right->ToBooleanIsFalse()) {
+      builder()->Jump(test_result->NewElseLabel());
+    } else if (left->ToBooleanIsTrue() && right->ToBooleanIsTrue()) {
+      builder()->Jump(test_result->NewThenLabel());
+    } else {
+      BytecodeLabels test_right(zone());
+      VisitForTest(left, &test_right, test_result->else_labels(),
+                   TestFallthrough::kThen);
+      test_right.Bind(builder());
+      VisitForTest(right, test_result->then_labels(),
+                   test_result->else_labels(), test_result->fallthrough());
+    }
+    test_result->SetResultConsumedByTest();
   } else {
-    BytecodeLabel end_label;
-    VisitForAccumulatorValue(left);
-    builder()->JumpIfFalse(&end_label);
-    VisitForAccumulatorValue(right);
-    builder()->Bind(&end_label);
+    if (left->ToBooleanIsFalse()) {
+      VisitForAccumulatorValue(left);
+    } else if (left->ToBooleanIsTrue()) {
+      VisitForAccumulatorValue(right);
+    } else {
+      BytecodeLabel end_label;
+      VisitForAccumulatorValue(left);
+      builder()->JumpIfFalse(&end_label);
+      VisitForAccumulatorValue(right);
+      builder()->Bind(&end_label);
+    }
+    execution_result()->SetResultInAccumulator();
   }
-  execution_result()->SetResultInAccumulator();
 }
 
 void BytecodeGenerator::VisitRewritableExpression(RewritableExpression* expr) {
   Visit(expr->expression());
 }
 
 void BytecodeGenerator::VisitNewLocalFunctionContext() {
   AccumulatorResultScope accumulator_execution_result(this);
   Scope* scope = this->scope();
 
@@ skipping 221 matching lines @@
 
 // Visits the expression |expr| and stores the expression result in
 // |destination|.
 void BytecodeGenerator::VisitForRegisterValue(Expression* expr,
                                               Register destination) {
   AccumulatorResultScope register_scope(this);
   Visit(expr);
   builder()->StoreAccumulatorInRegister(destination);
 }
 
+// Visits the expression |expr| for testing its boolean value and jumping to the
+// |then| or |other| label depending on value and short-circuit semantics
+void BytecodeGenerator::VisitForTest(Expression* expr,
+                                     BytecodeLabels* then_labels,
+                                     BytecodeLabels* else_labels,
+                                     TestFallthrough fallthrough) {
+  bool result_consumed;
+  {
+    // To make sure that all temporary registers are returned before generating
+    // jumps below, we ensure that the result scope is deleted before doing so.
+    // Dead registers might be materialized otherwise.
+    TestResultScope test_result(this, then_labels, else_labels, fallthrough);
+    Visit(expr);
+    result_consumed = test_result.ResultConsumedByTest();
+  }
+  if (!result_consumed) {
+    switch (fallthrough) {
+      case TestFallthrough::kThen:
+        builder()->JumpIfFalse(else_labels->New());
+        break;
+      case TestFallthrough::kElse:
+        builder()->JumpIfTrue(then_labels->New());
+        break;
+      case TestFallthrough::kNone:
+        builder()->JumpIfTrue(then_labels->New());
+        builder()->Jump(else_labels->New());
+    }
+  }
+}
+
 void BytecodeGenerator::VisitInScope(Statement* stmt, Scope* scope) {
   ContextScope context_scope(this, scope);
   DCHECK(scope->declarations()->is_empty());
   Visit(stmt);
 }
 
 LanguageMode BytecodeGenerator::language_mode() const {
   return execution_context()->scope()->language_mode();
 }
 
 int BytecodeGenerator::feedback_index(FeedbackVectorSlot slot) const {
   return TypeFeedbackVector::GetIndex(slot);
 }
 
 }  // namespace interpreter
 }  // namespace internal
 }  // namespace v8