Reland "[interpeter] Move to table based peephole optimizer."

src/interpreter/bytecode-peephole-optimizer.cc

-// Copyright 2015 the V8 project authors. All rights reserved.
+// Copyright 2016 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-peephole-optimizer.h"
 
 #include "src/interpreter/constant-array-builder.h"
 #include "src/objects-inl.h"
 #include "src/objects.h"
 
 namespace v8 {
@@ skipping 10 matching lines @@
 // override
 Handle<BytecodeArray> BytecodePeepholeOptimizer::ToBytecodeArray(
     int fixed_register_count, int parameter_count,
     Handle<FixedArray> handler_table) {
   Flush();
   return next_stage_->ToBytecodeArray(fixed_register_count, parameter_count,
                                       handler_table);
 }
 
 // override
-void BytecodePeepholeOptimizer::Write(BytecodeNode* node) {
-  node = OptimizeAndEmitLast(node);
-  if (node != nullptr) {
-    SetLast(node);
-  }
-}
-
-// override
-void BytecodePeepholeOptimizer::WriteJump(BytecodeNode* node,
-                                          BytecodeLabel* label) {
-  node = OptimizeAndEmitLast(node);
-  next_stage_->WriteJump(node, label);
-}
-
-// override
 void BytecodePeepholeOptimizer::BindLabel(BytecodeLabel* label) {
   Flush();
   next_stage_->BindLabel(label);
 }
 
 // override
 void BytecodePeepholeOptimizer::BindLabel(const BytecodeLabel& target,
                                           BytecodeLabel* label) {
-  // There is no need to flush here, it will have been flushed when |target|
-  // was bound.
+  // There is no need to flush here, it will have been flushed when
+  // |target| was bound.
   next_stage_->BindLabel(target, label);
 }
 
+// override
+void BytecodePeepholeOptimizer::WriteJump(BytecodeNode* node,
+                                          BytecodeLabel* label) {
+  // Handlers for jump bytecodes do not emit |node| as WriteJump()
+  // requires the |label| and having a label argument in all action
+  // handlers results in dead work in the non-jump case.
+  ApplyPeepholeAction(node);
+  next_stage()->WriteJump(node, label);
+}
+
+// override
+void BytecodePeepholeOptimizer::Write(BytecodeNode* node) {
+  // Handlers for non-jump bytecodes run to completion emitting
+  // bytecode to next stage as appropriate.
+  ApplyPeepholeAction(node);
+}
+
 void BytecodePeepholeOptimizer::Flush() {
-  // TODO(oth/rmcilroy): We could check CanElideLast() here to potentially
-  // eliminate last rather than writing it.
   if (LastIsValid()) {
     next_stage_->Write(&last_);
     InvalidateLast();
   }
 }
 
 void BytecodePeepholeOptimizer::InvalidateLast() {
   last_.set_bytecode(Bytecode::kIllegal);
 }
 
 bool BytecodePeepholeOptimizer::LastIsValid() const {
   return last_.bytecode() != Bytecode::kIllegal;
 }
 
 void BytecodePeepholeOptimizer::SetLast(const BytecodeNode* const node) {
+  // An action shouldn't leave a NOP as last bytecode unless it has
+  // source position information. NOP without source information can
+  // always be elided.
+  DCHECK(node->bytecode() != Bytecode::kNop || node->source_info().is_valid());
+
   last_.Clone(node);
 }
 
 Handle<Object> BytecodePeepholeOptimizer::GetConstantForIndexOperand(
     const BytecodeNode* const node, int index) const {
   DCHECK_LE(index, node->operand_count());
   DCHECK_EQ(Bytecodes::GetOperandType(node->bytecode(), 0), OperandType::kIdx);
   uint32_t index_operand = node->operand(0);
   return constant_array_builder_->At(index_operand);
 }
 
-bool BytecodePeepholeOptimizer::LastBytecodePutsNameInAccumulator() const {
-  DCHECK(LastIsValid());
-  return (last_.bytecode() == Bytecode::kTypeOf ||
-          last_.bytecode() == Bytecode::kToName ||
-          (last_.bytecode() == Bytecode::kLdaConstant &&
-           GetConstantForIndexOperand(&last_, 0)->IsName()));
-}
-
-void BytecodePeepholeOptimizer::TryToRemoveLastExpressionPosition(
-    const BytecodeNode* const current) {
-  if (current->source_info().is_valid() &&
-      last_.source_info().is_expression() &&
-      Bytecodes::IsWithoutExternalSideEffects(last_.bytecode())) {
-    // The last bytecode has been marked as expression. It has no
-    // external effects so can't throw and the current bytecode is a
-    // source position. Remove the expression position on the last
-    // bytecode to open up potential peephole optimizations and to
-    // save the memory and perf cost of storing the unneeded
-    // expression position.
-    last_.source_info().set_invalid();
-  }
-}
-
-bool BytecodePeepholeOptimizer::CanElideCurrent(
-    const BytecodeNode* const current) const {
-  if (Bytecodes::IsLdarOrStar(last_.bytecode()) &&
-      Bytecodes::IsLdarOrStar(current->bytecode()) &&
-      current->operand(0) == last_.operand(0)) {
-    // Ldar and Star make the accumulator and register hold equivalent
-    // values. Only the first bytecode is needed if there's a sequence
-    // of back-to-back Ldar and Star bytecodes with the same operand.
-    return true;
-  } else if (current->bytecode() == Bytecode::kToName &&
-             LastBytecodePutsNameInAccumulator()) {
-    // If the previous bytecode ensured a name was in the accumulator,
-    // the type coercion ToName() can be elided.
-    return true;
-  } else {
-    // Additional candidates for eliding current:
-    // (i) current is Nop.
-    // (ii) ToNumber if the last puts a number in the accumulator.
-    return false;
-  }
-}
-
 bool BytecodePeepholeOptimizer::CanElideLastBasedOnSourcePosition(
     const BytecodeNode* const current) const {
   //
   // The rules for allowing the elision of the last bytecode based
   // on source position are:
   //
   //                     C U R R E N T
   //              +--------+--------+--------+
   //              |  None  |  Expr  |  Stmt  |
   //  L  +--------+--------+--------+--------+
   //     |  None  |  YES   |  YES   |  YES   |
   //  A  +--------+--------+--------+--------+
   //     |  Expr  |  YES   | MAYBE  |  MAYBE |
   //  S  +--------+--------+--------+--------+
   //     |  Stmt  |  YES   |   NO   |   NO   |
   //  T  +--------+--------+--------+--------+
   //
   // The goal is not lose any statement positions and not lose useful
   // expression positions. Whenever the last bytecode is elided it's
   // source position information is applied to the current node
   // updating it if necessary.
   //
-  // The last bytecode can be elided for the MAYBE cases if the last
+  // The last bytecode could be elided for the MAYBE cases if the last
   // bytecode is known not to throw. If it throws, the system would
   // not have correct stack trace information. The appropriate check
-  // for this would be Bytecodes::IsWithoutExternalSideEffects(),
-  // which is checked in
-  // BytecodePeepholeOptimizer::TransformLastAndCurrentBytecodes() to
-  // keep the check here simple.
-  //
-  // In rare cases, bytecode generation produces consecutive bytecodes
-  // with the same expression positions. In principle, the latter of
-  // these can be elided, but would make this function more expensive.
+  // for this would be Bytecodes::IsWithoutExternalSideEffects(). By
+  // default, the upstream bytecode generator filters out unneeded
+  // expression position information so there is neglible benefit to
+  // handling MAYBE specially. Hence MAYBE is treated the same as NO.
   //
   return (!last_.source_info().is_valid() ||
           !current->source_info().is_valid());
 }
 
 namespace {
 
 void TransformLdaStarToLdrLdar(Bytecode new_bytecode, BytecodeNode* const last,
                                BytecodeNode* const current) {
   DCHECK_EQ(current->bytecode(), Bytecode::kStar);
 
   //
   // An example transformation here would be:
   //
   //   LdaGlobal i0, i1  ____\  LdrGlobal i0, i1, R
   //   Star R            ====/  Ldar R
   //
   // which loads a global value into both a register and the
   // accumulator. However, in the second form the Ldar can often be
   // peephole optimized away unlike the Star in the first form.
   //
   last->Transform(new_bytecode, current->operand(0));
   current->set_bytecode(Bytecode::kLdar, current->operand(0));
 }
 
-void TransformToBinaryOpWithSmiOnRhs(Bytecode new_bytecode,
-                                     BytecodeNode* const last,
-                                     BytecodeNode* const current) {
-  DCHECK(Bytecodes::IsLdaSmiOrLdaZero(last->bytecode()));
-  uint32_t imm_operand =
-      last->bytecode() == Bytecode::kLdaSmi ? last->operand(0) : 0;
-  current->set_bytecode(new_bytecode, imm_operand, current->operand(0));
+void TransformLdaSmiBinaryOpToBinaryOpWithSmi(Bytecode new_bytecode,
+                                              BytecodeNode* const last,
+                                              BytecodeNode* const current) {
+  DCHECK_EQ(last->bytecode(), Bytecode::kLdaSmi);
+  current->set_bytecode(new_bytecode, last->operand(0), current->operand(0));
   if (last->source_info().is_valid()) {
     current->source_info().Clone(last->source_info());
   }
+}
+
+void TransformLdaZeroBinaryOpToBinaryOpWithZero(Bytecode new_bytecode,
+                                                BytecodeNode* const last,
+                                                BytecodeNode* const current) {
+  DCHECK_EQ(last->bytecode(), Bytecode::kLdaZero);
+  current->set_bytecode(new_bytecode, 0, current->operand(0));
+  if (last->source_info().is_valid()) {
+    current->source_info().Clone(last->source_info());
+  }
 }
 
 }  // namespace
 
-bool BytecodePeepholeOptimizer::TransformLastAndCurrentBytecodes(
-    BytecodeNode* const current) {
-  if (current->bytecode() == Bytecode::kStar &&
-      !current->source_info().is_statement()) {
-    // Note: If the Star is tagged with a statement position, we can't
-    // perform this transform as the store to the register will
-    // have the wrong ordering for stepping in the debugger.
-    switch (last_.bytecode()) {
-      case Bytecode::kLdaNamedProperty:
-        TransformLdaStarToLdrLdar(Bytecode::kLdrNamedProperty, &last_, current);
-        return true;
-      case Bytecode::kLdaKeyedProperty:
-        TransformLdaStarToLdrLdar(Bytecode::kLdrKeyedProperty, &last_, current);
-        return true;
-      case Bytecode::kLdaGlobal:
-        TransformLdaStarToLdrLdar(Bytecode::kLdrGlobal, &last_, current);
-        return true;
-      case Bytecode::kLdaContextSlot:
-        TransformLdaStarToLdrLdar(Bytecode::kLdrContextSlot, &last_, current);
-        return true;
-      case Bytecode::kLdaUndefined:
-        TransformLdaStarToLdrLdar(Bytecode::kLdrUndefined, &last_, current);
-        return true;
-      default:
-        break;
-    }
-  } else if (Bytecodes::IsLdaSmiOrLdaZero(last_.bytecode()) &&
-             (!last_.source_info().is_valid() ||
-              !current->source_info().is_valid())) {
-    switch (current->bytecode()) {
-      case Bytecode::kAdd:
-        TransformToBinaryOpWithSmiOnRhs(Bytecode::kAddSmi, &last_, current);
-        InvalidateLast();
-        return true;
-      case Bytecode::kSub:
-        TransformToBinaryOpWithSmiOnRhs(Bytecode::kSubSmi, &last_, current);
-        InvalidateLast();
-        return true;
-      case Bytecode::kBitwiseOr:
-        TransformToBinaryOpWithSmiOnRhs(Bytecode::kBitwiseOrSmi, &last_,
-                                        current);
-        InvalidateLast();
-        return true;
-      case Bytecode::kBitwiseAnd:
-        TransformToBinaryOpWithSmiOnRhs(Bytecode::kBitwiseAndSmi, &last_,
-                                        current);
-        InvalidateLast();
-        return true;
-      case Bytecode::kShiftLeft:
-        TransformToBinaryOpWithSmiOnRhs(Bytecode::kShiftLeftSmi, &last_,
-                                        current);
-        InvalidateLast();
-        return true;
-      case Bytecode::kShiftRight:
-        TransformToBinaryOpWithSmiOnRhs(Bytecode::kShiftRightSmi, &last_,
-                                        current);
-        InvalidateLast();
-        return true;
-      default:
-        break;
-    }
-  }
+void BytecodePeepholeOptimizer::DefaultAction(
+    BytecodeNode* const node, const PeepholeActionAndData* action_data) {
+  DCHECK(LastIsValid());
+  DCHECK(!Bytecodes::IsJump(node->bytecode()));
 
-  return false;
+  next_stage()->Write(last());
+  SetLast(node);
 }
 
-bool BytecodePeepholeOptimizer::RemoveToBooleanFromJump(
-    BytecodeNode* const current) {
-  bool can_remove = Bytecodes::IsJumpIfToBoolean(current->bytecode()) &&
-                    Bytecodes::WritesBooleanToAccumulator(last_.bytecode());
-  if (can_remove) {
-    // Conditional jumps with boolean conditions are emiitted in
-    // ToBoolean form by the bytecode array builder,
-    // i.e. JumpIfToBooleanTrue rather JumpIfTrue. The ToBoolean
-    // element can be removed if the previous bytecode put a boolean
-    // value in the accumulator.
-    Bytecode jump = Bytecodes::GetJumpWithoutToBoolean(current->bytecode());
-    current->set_bytecode(jump, current->operand(0));
-  }
-  return can_remove;
+void BytecodePeepholeOptimizer::UpdateLastAction(
+    BytecodeNode* const node, const PeepholeActionAndData* action_data) {
+  DCHECK(!LastIsValid());
+  DCHECK(!Bytecodes::IsJump(node->bytecode()));
+
+  SetLast(node);
 }
 
-bool BytecodePeepholeOptimizer::RemoveToBooleanFromLogicalNot(
-    BytecodeNode* const current) {
-  bool can_remove = current->bytecode() == Bytecode::kToBooleanLogicalNot &&
-                    Bytecodes::WritesBooleanToAccumulator(last_.bytecode());
-  if (can_remove) {
-    // Logical-nots are emitted in ToBoolean form by the bytecode array
-    // builder, The ToBoolean element can be removed if the previous bytecode
-    // put a boolean value in the accumulator.
-    current->set_bytecode(Bytecode::kLogicalNot);
-  }
-  return can_remove;
-}
+void BytecodePeepholeOptimizer::UpdateLastIfSourceInfoPresentAction(
+    BytecodeNode* const node, const PeepholeActionAndData* action_data) {
+  DCHECK(!LastIsValid());
+  DCHECK(!Bytecodes::IsJump(node->bytecode()));
 
-bool BytecodePeepholeOptimizer::TransformCurrentBytecode(
-    BytecodeNode* const current) {
-  return RemoveToBooleanFromJump(current) ||
-         RemoveToBooleanFromLogicalNot(current);
-}
-
-bool BytecodePeepholeOptimizer::CanElideLast(
-    const BytecodeNode* const current) const {
-  if (last_.bytecode() == Bytecode::kNop) {
-    // Nop are placeholders for holding source position information.
-    return true;
-  } else if (Bytecodes::IsAccumulatorLoadWithoutEffects(current->bytecode()) &&
-             Bytecodes::IsAccumulatorLoadWithoutEffects(last_.bytecode())) {
-    // The accumulator is invisible to the debugger. If there is a sequence of
-    // consecutive accumulator loads (that don't have side effects) then only
-    // the final load is potentially visible.
-    return true;
-  } else if (Bytecodes::GetAccumulatorUse(current->bytecode()) ==
-                 AccumulatorUse::kWrite &&
-             Bytecodes::IsAccumulatorLoadWithoutEffects(last_.bytecode())) {
-    // The current instruction clobbers the accumulator without reading it. The
-    // load in the last instruction can be elided as it has no effect.
-    return true;
-  } else {
-    return false;
+  if (node->source_info().is_valid()) {
+    SetLast(node);
   }
 }
 
-BytecodeNode* BytecodePeepholeOptimizer::Optimize(BytecodeNode* current) {
-  TryToRemoveLastExpressionPosition(current);
-  if (TransformCurrentBytecode(current) ||
-      TransformLastAndCurrentBytecodes(current)) {
-    return current;
+void BytecodePeepholeOptimizer::ElideCurrentAction(
+    BytecodeNode* const node, const PeepholeActionAndData* action_data) {
+  DCHECK(LastIsValid());
+  DCHECK(!Bytecodes::IsJump(node->bytecode()));
+
+  if (node->source_info().is_valid()) {
+    // Preserve the source information by replacing the node bytecode
+    // with a no op bytecode.
+    node->set_bytecode(Bytecode::kNop);
+    DefaultAction(node);
+  } else {
+    // Nothing to do, keep last and wait for next bytecode to pair with it.
   }
-
-  if (CanElideCurrent(current)) {
-    if (current->source_info().is_valid()) {
-      // Preserve the source information by replacing the current bytecode
-      // with a no op bytecode.
-      current->set_bytecode(Bytecode::kNop);
-    } else {
-      current = nullptr;
-    }
-    return current;
-  }
-
-  if (CanElideLast(current) && CanElideLastBasedOnSourcePosition(current)) {
-    if (last_.source_info().is_valid()) {
-      // Current can not be valid per CanElideLastBasedOnSourcePosition().
-      current->source_info().Clone(last_.source_info());
-    }
-    InvalidateLast();
-    return current;
-  }
-
-  return current;
 }
 
-BytecodeNode* BytecodePeepholeOptimizer::OptimizeAndEmitLast(
-    BytecodeNode* current) {
-  // Attempt optimization if there is an earlier node to optimize with.
-  if (LastIsValid()) {
-    current = Optimize(current);
-    // Only output the last node if it wasn't invalidated by the optimization.
-    if (LastIsValid()) {
-      next_stage_->Write(&last_);
-      InvalidateLast();
+void BytecodePeepholeOptimizer::ElideCurrentIfOperand0MatchesAction(
+    BytecodeNode* const node, const PeepholeActionAndData* action_data) {
+  DCHECK(LastIsValid());
+  DCHECK(!Bytecodes::IsJump(node->bytecode()));
+
+  if (last()->operand(0) == node->operand(0)) {
+    ElideCurrentAction(node);
+  } else {
+    DefaultAction(node);
+  }
+}
+
+void BytecodePeepholeOptimizer::ElideCurrentIfLoadingNameConstantAction(
+    BytecodeNode* const node, const PeepholeActionAndData* action_data) {
+  DCHECK_EQ(last()->bytecode(), Bytecode::kLdaConstant);
+  DCHECK(!Bytecodes::IsJump(node->bytecode()));
+
+  if (GetConstantForIndexOperand(last(), 0)->IsName()) {
+    ElideCurrentAction(node);
+  } else {
+    DefaultAction(node);
+  }
+}
+
+void BytecodePeepholeOptimizer::ElideLastAction(
+    BytecodeNode* const node, const PeepholeActionAndData* action_data) {
+  DCHECK(LastIsValid());
+  DCHECK(!Bytecodes::IsJump(node->bytecode()));
+
+  if (CanElideLastBasedOnSourcePosition(node)) {
+    if (last()->source_info().is_valid()) {
+      // |node| can not have a valid source position if the source
+      // position of last() is valid (per rules in
+      // CanElideLastBasedOnSourcePosition()).
+      node->source_info().Clone(last()->source_info());
     }
+    SetLast(node);
+  } else {
+    DefaultAction(node);
   }
-  return current;
+}
+
+void BytecodePeepholeOptimizer::ChangeBytecodeAction(
+    BytecodeNode* const node, const PeepholeActionAndData* action_data) {
+  DCHECK(LastIsValid());
+  DCHECK(!Bytecodes::IsJump(node->bytecode()));
+
+  node->set_bytecode(action_data->bytecode);
+  DefaultAction(node);
+}
+
+void BytecodePeepholeOptimizer::TransformLdaStarToLdrLdarAction(
+    BytecodeNode* const node, const PeepholeActionAndData* action_data) {
+  DCHECK(LastIsValid());
+  DCHECK(!Bytecodes::IsJump(node->bytecode()));
+
+  if (!node->source_info().is_statement()) {
+    TransformLdaStarToLdrLdar(action_data->bytecode, last(), node);
+  }
+  DefaultAction(node);
+}
+
+void BytecodePeepholeOptimizer::TransformLdaSmiBinaryOpToBinaryOpWithSmiAction(
+    BytecodeNode* const node, const PeepholeActionAndData* action_data) {
+  DCHECK(LastIsValid());
+  DCHECK(!Bytecodes::IsJump(node->bytecode()));
+
+  if (!node->source_info().is_valid() || !last()->source_info().is_valid()) {
+    // Fused last and current into current.
+    TransformLdaSmiBinaryOpToBinaryOpWithSmi(action_data->bytecode, last(),
+                                             node);
+    SetLast(node);
+  } else {
+    DefaultAction(node);
+  }
+}
+
+void BytecodePeepholeOptimizer::
+    TransformLdaZeroBinaryOpToBinaryOpWithZeroAction(
+        BytecodeNode* const node, const PeepholeActionAndData* action_data) {
+  DCHECK(LastIsValid());
+  DCHECK(!Bytecodes::IsJump(node->bytecode()));
+  if (!node->source_info().is_valid() || !last()->source_info().is_valid()) {
+    // Fused last and current into current.
+    TransformLdaZeroBinaryOpToBinaryOpWithZero(action_data->bytecode, last(),
+                                               node);
+    SetLast(node);
+  } else {
+    DefaultAction(node);
+  }
+}
+
+void BytecodePeepholeOptimizer::DefaultJumpAction(
+    BytecodeNode* const node, const PeepholeActionAndData* action_data) {
+  DCHECK(LastIsValid());
+  DCHECK(Bytecodes::IsJump(node->bytecode()));
+
+  next_stage()->Write(last());
+  InvalidateLast();
+}
+
+void BytecodePeepholeOptimizer::UpdateLastJumpAction(
+    BytecodeNode* const node, const PeepholeActionAndData* action_data) {
+  DCHECK(!LastIsValid());
+  DCHECK(Bytecodes::IsJump(node->bytecode()));
+}
+
+void BytecodePeepholeOptimizer::ChangeJumpBytecodeAction(
+    BytecodeNode* const node, const PeepholeActionAndData* action_data) {
+  DCHECK(LastIsValid());
+  DCHECK(Bytecodes::IsJump(node->bytecode()));
+
+  next_stage()->Write(last());
+  InvalidateLast();
+  node->set_bytecode(action_data->bytecode, node->operand(0));
+}
+
+void BytecodePeepholeOptimizer::ElideLastBeforeJumpAction(
+    BytecodeNode* const node, const PeepholeActionAndData* action_data) {
+  DCHECK(LastIsValid());
+  DCHECK(Bytecodes::IsJump(node->bytecode()));
+  DCHECK(CanElideLastBasedOnSourcePosition(node));
+
+  if (!node->source_info().is_valid()) {
+    node->source_info().Clone(last()->source_info());
+  } else {
+    next_stage()->Write(last());
+  }
+  InvalidateLast();
+}
+
+void BytecodePeepholeOptimizer::ApplyPeepholeAction(BytecodeNode* const node) {
+  // A single table is used for looking up peephole optimization
+  // matches as it is observed to have better performance. This is
+  // inspite of the fact that jump bytecodes and non-jump bytecodes
+  // have different processing logic, in particular a jump bytecode
+  // always needs to emit the jump via WriteJump().
+  const PeepholeActionAndData* const action_data =
+      PeepholeActionTable::Lookup(last()->bytecode(), node->bytecode());
+  switch (action_data->action) {
+#define CASE(Action)              \
+  case PeepholeAction::k##Action: \
+    Action(node, action_data);    \
+    break;
+    PEEPHOLE_ACTION_LIST(CASE)
+#undef CASE
+    default:
+      UNREACHABLE();
+      break;
+  }
 }
 
 }  // namespace interpreter
 }  // namespace internal
 }  // namespace v8