[interpreter] VisitForTest for bytecode generator

src/interpreter/bytecode-generator.cc

Index: src/interpreter/bytecode-generator.cc
diff --git a/src/interpreter/bytecode-generator.cc b/src/interpreter/bytecode-generator.cc
index 1637fbb777a36a23e184d7ae74123cb1cbc6abc4..4589c2982d9ac69d3f9cd973cadeb3171e494d61 100644
--- a/src/interpreter/bytecode-generator.cc
+++ b/src/interpreter/bytecode-generator.cc
@@ -445,6 +445,7 @@ class BytecodeGenerator::ExpressionResultScope {
 
   bool IsEffect() const { return kind_ == Expression::kEffect; }
   bool IsValue() const { return kind_ == Expression::kValue; }
+  bool IsTest() const { return kind_ == Expression::kTest; }
 
   virtual void SetResultInAccumulator() = 0;
   virtual void SetResultInRegister(Register reg) = 0;
@@ -535,6 +536,92 @@ class BytecodeGenerator::RegisterResultScope final
   Register result_register_;
 };
 
+enum class BytecodeGenerator::ControlFallthrough { THEN, ELSE, NONE };

[rmcilroy, 2016/08/12 11:15:25]

Just define this in the header. Also, enum class uses "kConstant" notation
(i.e., kThen, kElse, kNone)

[klaasb, 2016/08/12 16:00:12]

Done.

+
+// Scoped class used for generating multiple jumps to the same location
+class BytecodeGenerator::BytecodeLabels {

[rmcilroy, 2016/08/12 11:15:26]

How about moving this to bytecode-label.h/cc?

[klaasb, 2016/08/12 16:00:12]

Done.

+ public:
+  BytecodeLabels() = default;
+
+  BytecodeLabel* New() {
+    labels_.emplace_back();
+    return &labels_.back();
+  }
+
+  void Bind(BytecodeArrayBuilder* builder) {
+    for (auto label : labels_) {
+      builder->Bind(&label);
+    }
+  }
+
+ private:
+  std::vector<BytecodeLabel> labels_;

[rmcilroy, 2016/08/12 11:15:25]

use ZoneVector (which means you will need to pass the zone to the constructor).

[klaasb, 2016/08/12 16:00:13]

Done.

+
+  DISALLOW_COPY_AND_ASSIGN(BytecodeLabels);
+};
+
+// Scoped class used when the result of the current expression to be
+// evaluated is only tested with jumps to two branches.
+class BytecodeGenerator::ControlResultScope final
+    : public ExpressionResultScope {
+ public:
+  ControlResultScope(BytecodeGenerator* generator, BytecodeLabels* then_labels,
+                     BytecodeLabels* else_labels,
+                     ControlFallthrough fallthrough)
+      : ExpressionResultScope(generator, Expression::kTest),
+        then_labels_(then_labels),
+        else_labels_(else_labels),
+        fallthrough_(fallthrough),
+        has_result_(true) {}
+
+  virtual void SetResultInAccumulator() {
+    DCHECK(has_result_);

[rmcilroy, 2016/08/12 11:15:26]

No need for these DCHECKS - the set_result_identified will DCHECK if it is
called twice.

[klaasb, 2016/08/12 16:00:12]

Done.

+    set_result_identified();
+  }
+
+  virtual void SetResultInRegister(Register reg) {
+    DCHECK(has_result_);
+    builder()->LoadAccumulatorWithRegister(reg);
+    set_result_identified();
+  }
+
+  // Used when code special cases for ControlResultScope and consumes any
+  // possible value by testing and jumping to a then/else label.
+  void SetNoResult() {

[rmcilroy, 2016/08/12 11:15:25]

How about SetResultConsumedByTest

[klaasb, 2016/08/12 16:00:12]

Done.

+    DCHECK(has_result_);
+    has_result_ = false;
+    set_result_identified();
+  }
+
+  bool HasResultValue() { return has_result_; }

[rmcilroy, 2016/08/12 11:15:26]

ResultConsumedByTest() (and invert the boolean)

[klaasb, 2016/08/12 16:00:13]

Done.

+
+  BytecodeLabel* NewThenLabel() { return then_labels_->New(); }
+  BytecodeLabel* NewElseLabel() { return else_labels_->New(); }
+
+  BytecodeLabels* ThenLabels() { return then_labels_; }
+  BytecodeLabels* ElseLabels() { return else_labels_; }
+
+  ControlFallthrough Fallthrough() { return fallthrough_; }
+  ControlFallthrough InvertedFallthrough() {

[rmcilroy, 2016/08/12 11:15:26]

These are all getters, so lowercase - then_labels, else_labels, fallthrough and
inverted_fallthrough. Also add "const" to all of them.

[klaasb, 2016/08/12 16:00:12]

Done.

+    switch (fallthrough_) {
+      case ControlFallthrough::THEN:
+        return ControlFallthrough::ELSE;
+      case ControlFallthrough::ELSE:
+        return ControlFallthrough::THEN;
+      default:
+        return ControlFallthrough::NONE;
+    }
+  }
+
+ private:
+  BytecodeLabels* then_labels_;
+  BytecodeLabels* else_labels_;
+  ControlFallthrough fallthrough_;
+  bool has_result_;
+
+  DISALLOW_COPY_AND_ASSIGN(ControlResultScope);
+};
+
 // Used to build a list of global declaration initial value pairs.
 class BytecodeGenerator::GlobalDeclarationsBuilder final : public ZoneObject {
  public:
@@ -979,7 +1066,7 @@ void BytecodeGenerator::VisitEmptyStatement(EmptyStatement* stmt) {
 
 void BytecodeGenerator::VisitIfStatement(IfStatement* stmt) {
   builder()->SetStatementPosition(stmt);
-  BytecodeLabel else_label, end_label;
+  BytecodeLabel end_label;

[rmcilroy, 2016/08/12 11:15:26]

nit - move end_label into inner else branch too.

[klaasb, 2016/08/12 16:00:12]

Done.

   if (stmt->condition()->ToBooleanIsTrue()) {
     // Generate then block unconditionally as always true.
     Visit(stmt->then_statement());
@@ -992,15 +1079,20 @@ void BytecodeGenerator::VisitIfStatement(IfStatement* stmt) {
     // 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);
+    BytecodeLabels then_labels;

[rmcilroy, 2016/08/12 11:15:26]

nit - BytecodeLabels then_labels, else_labels;

[klaasb, 2016/08/12 16:00:12]

Done.

+    BytecodeLabels else_labels;
+    VisitForControl(stmt->condition(), &then_labels, &else_labels,
+                    ControlFallthrough::THEN);
+
+    then_labels.Bind(builder());
     Visit(stmt->then_statement());
+
     if (stmt->HasElseStatement()) {
       builder()->Jump(&end_label);
-      builder()->Bind(&else_label);
+    }
+    else_labels.Bind(builder());
+    if (stmt->HasElseStatement()) {

[rmcilroy, 2016/08/12 11:15:26]

could you keep the if/else form:

if (stmt->HasElseStatement()) {
  builder()->Jump(&end_label);
  else_labels.Bind(builder());
  Visit(stmt->else_statement());
} else {
  else_labels.Bind(builder());
}

[klaasb, 2016/08/12 16:00:12]

Done.

       Visit(stmt->else_statement());
-    } else {
-      builder()->Bind(&else_label);
     }
     builder()->Bind(&end_label);
   }
@@ -1109,6 +1201,7 @@ void BytecodeGenerator::VisitDoWhileStatement(DoWhileStatement* stmt) {
     VisitIterationHeader(stmt, &loop_builder);
     VisitIterationBody(stmt, &loop_builder);
     builder()->SetExpressionAsStatementPosition(stmt->cond());
+    // TODO(klaasb) VisitForControl for loop conditions
     VisitForAccumulatorValue(stmt->cond());
     loop_builder.JumpToHeaderIfTrue();
   }
@@ -1125,6 +1218,7 @@ void BytecodeGenerator::VisitWhileStatement(WhileStatement* stmt) {
   VisitIterationHeader(stmt, &loop_builder);
   if (!stmt->cond()->ToBooleanIsTrue()) {
     builder()->SetExpressionAsStatementPosition(stmt->cond());
+    // TODO(klaasb) VisitForControl for loop conditions
     VisitForAccumulatorValue(stmt->cond());
     loop_builder.BreakIfFalse();
   }
@@ -1147,6 +1241,7 @@ void BytecodeGenerator::VisitForStatement(ForStatement* stmt) {
   VisitIterationHeader(stmt, &loop_builder);
   if (stmt->cond() && !stmt->cond()->ToBooleanIsTrue()) {
     builder()->SetExpressionAsStatementPosition(stmt->cond());
+    // TODO(klaasb) VisitForControl for loop conditions
     VisitForAccumulatorValue(stmt->cond());
     loop_builder.BreakIfFalse();
   }
@@ -1565,21 +1660,28 @@ void BytecodeGenerator::VisitDoExpression(DoExpression* expr) {
 }
 
 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.
-
-  BytecodeLabel else_label, end_label;
+  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;
+    BytecodeLabels else_labels;

[rmcilroy, 2016/08/12 11:15:26]

nit - BytecodeLabels then_labels, else_labels;

[klaasb, 2016/08/12 16:00:12]

Done.

 
-  VisitForAccumulatorValue(expr->condition());
-  builder()->JumpIfFalse(&else_label);
+    VisitForControl(expr->condition(), &then_labels, &else_labels,
+                    ControlFallthrough::THEN);
 
-  VisitForAccumulatorValue(expr->then_expression());
-  builder()->Jump(&end_label);
+    then_labels.Bind(builder());
+    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();
 }
@@ -1868,6 +1970,8 @@ void BytecodeGenerator::VisitVariableLoad(Variable* variable,
       Register source(Register(variable->index()));
       builder()->LoadAccumulatorWithRegister(source);
       BuildHoleCheckForVariableLoad(variable);
+      // this will generate a new register when within a RegisterResultScope

[rmcilroy, 2016/08/12 11:15:26]

Thanks for updating this. How about:

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.

[klaasb, 2016/08/12 16:00:12]

Done.

+      // which is needed when expressions assign to variables as side-effect
       execution_result()->SetResultInAccumulator();
       break;
     }
@@ -1877,6 +1981,8 @@ void BytecodeGenerator::VisitVariableLoad(Variable* variable,
       Register source = builder()->Parameter(variable->index() + 1);
       builder()->LoadAccumulatorWithRegister(source);
       BuildHoleCheckForVariableLoad(variable);
+      // this will generate a new register when within a RegisterResultScope

[rmcilroy, 2016/08/12 11:15:25]

ditto

[klaasb, 2016/08/12 16:00:12]

Done.

+      // which is needed when expressions assign to variables as side-effect
       execution_result()->SetResultInAccumulator();
       break;
     }
@@ -2736,9 +2842,18 @@ void BytecodeGenerator::VisitTypeOf(UnaryOperation* expr) {
 }
 
 void BytecodeGenerator::VisitNot(UnaryOperation* expr) {
-  VisitForAccumulatorValue(expr->expression());
-  builder()->LogicalNot();
-  execution_result()->SetResultInAccumulator();
+  if (execution_result()->IsTest()) {

[rmcilroy, 2016/08/12 11:15:26]

Could you also add the IsEffect shortcut here (just VisitForEffect the value).

[klaasb, 2016/08/12 16:00:12]

Done.

+    ControlResultScope* control_result =
+        static_cast<ControlResultScope*>(execution_result());

[rmcilroy, 2016/08/12 11:15:26]

Could you add an AsTest() function with DCHECKS to ExecutionResult. Also, this
should be reinterpreter_cast<...>

[klaasb, 2016/08/12 16:00:12]

Done.

+    VisitForControl(expr->expression(), control_result->ElseLabels(),

[rmcilroy, 2016/08/12 11:15:26]

nit - comment that you are swapping the control flow.

[klaasb, 2016/08/12 16:00:12]

Done.

+                    control_result->ThenLabels(),
+                    control_result->InvertedFallthrough());
+    control_result->SetNoResult();
+  } else {
+    VisitForAccumulatorValue(expr->expression());
+    builder()->LogicalNot();
+    execution_result()->SetResultInAccumulator();
+  }
 }
 
 void BytecodeGenerator::VisitUnaryOperation(UnaryOperation* expr) {
@@ -3017,36 +3132,72 @@ 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()) {
+    ControlResultScope* control_result =
+        static_cast<ControlResultScope*>(execution_result());
+
+    if (left->ToBooleanIsTrue()) {

[rmcilroy, 2016/08/12 11:15:26]

I think you could do:
 if (left->ToBooleanIsTrue() || right->ToBooleanIsTrue) {
   builder()->Jump(control_result->NewThenLabel());
 } else if (left->ToBooleanIsFalse() && right->ToBooleanIsFalse()) {
   builder()->Jump(control_result->NewElseLabel());
 ...

[klaasb, 2016/08/12 16:00:12]

Done.

+      builder()->Jump(control_result->NewThenLabel());
+    } else {
+      BytecodeLabels test_right;
+      VisitForControl(left, control_result->ThenLabels(), &test_right,
+                      ControlFallthrough::ELSE);
+      test_right.Bind(builder());
+      VisitForControl(right, control_result->ThenLabels(),
+                      control_result->ElseLabels(),
+                      control_result->Fallthrough());
+    }
+    control_result->SetNoResult();
   } else {
-    BytecodeLabel end_label;
-    VisitForAccumulatorValue(left);
-    builder()->JumpIfTrue(&end_label);
-    VisitForAccumulatorValue(right);
-    builder()->Bind(&end_label);
+    // Short-circuit evaluation- If it is known that left is always true,
+    // no need to visit right

[rmcilroy, 2016/08/12 11:15:26]

Just remove this comment (ditto below)

[klaasb, 2016/08/12 16:00:13]

Done.

+    if (left->ToBooleanIsTrue()) {
+      VisitForAccumulatorValue(left);
+    } else {

[rmcilroy, 2016/08/12 11:15:25]

I know this isn't your code, but we should also be able to do:
else if (left->ToBooleanIsFalse()) {
  VisitForAccumulatorValue(right);
}

[klaasb, 2016/08/12 16:00:12]

Done.

+      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()) {
+    ControlResultScope* control_result =
+        static_cast<ControlResultScope*>(execution_result());
+
+    if (left->ToBooleanIsFalse()) {

[rmcilroy, 2016/08/12 11:15:26]

Same suggestion (for AND) as above for OR.

[klaasb, 2016/08/12 16:00:12]

Done.

+      builder()->Jump(control_result->NewElseLabel());
+    } else {
+      BytecodeLabels test_right;
+      VisitForControl(left, &test_right, control_result->ElseLabels(),
+                      ControlFallthrough::THEN);
+      test_right.Bind(builder());
+      VisitForControl(right, control_result->ThenLabels(),
+                      control_result->ElseLabels(),
+                      control_result->Fallthrough());
+    }
+    control_result->SetNoResult();
   } else {
-    BytecodeLabel end_label;
-    VisitForAccumulatorValue(left);
-    builder()->JumpIfFalse(&end_label);
-    VisitForAccumulatorValue(right);
-    builder()->Bind(&end_label);
+    // Short-circuit evaluation- If it is known that left is always false,
+    // no need to visit right

[rmcilroy, 2016/08/12 11:15:26]

ditto

[klaasb, 2016/08/12 16:00:12]

Done.

+    if (left->ToBooleanIsFalse()) {

[rmcilroy, 2016/08/12 11:15:25]

Same suggestion as above.

[klaasb, 2016/08/12 16:00:12]

Done.

+      VisitForAccumulatorValue(left);
+    } 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) {
@@ -3288,6 +3439,37 @@ void BytecodeGenerator::VisitForRegisterValue(Expression* 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::VisitForControl(Expression* expr,
+                                        BytecodeLabels* then_labels,
+                                        BytecodeLabels* else_labels,
+                                        ControlFallthrough fallthrough) {
+  bool has_result;
+  {
+    // to make sure that all temporary registers are returned before generating

[rmcilroy, 2016/08/12 11:15:26]

/s/to/To

[klaasb, 2016/08/12 16:00:12]

Done.

+    // jumps below, we assure that the result scope is deleted before
+    // otherwise dead registers might be materialized

[rmcilroy, 2016/08/12 11:15:26]

fullstop

[klaasb, 2016/08/12 16:00:11]

Done.

+    ControlResultScope control_result(this, then_labels, else_labels,
+                                      fallthrough);
+    Visit(expr);
+    has_result = control_result.HasResultValue();
+  }
+  if (has_result) {
+    switch (fallthrough) {
+      case ControlFallthrough::THEN:
+        builder()->JumpIfFalse(else_labels->New());
+        break;
+      case ControlFallthrough::ELSE:
+        builder()->JumpIfTrue(then_labels->New());
+        break;
+      default:

[rmcilroy, 2016/08/12 11:15:26]

Make this explicitly case ControlFallthrough::kNone

[klaasb, 2016/08/12 16:00:12]

Done.

+        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());