[turbofan] Prefer add/shift over madd on ARM64

src/compiler/arm64/instruction-selector-arm64.cc

 // Copyright 2014 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/compiler/instruction-selector-impl.h"
 #include "src/compiler/node-matchers.h"
 #include "src/compiler/node-properties.h"
 
 namespace v8 {
 namespace internal {
@@ skipping 266 matching lines @@
   if (m.right().HasValue() && (m.right().Value() < 0) &&
       g.CanBeImmediate(-m.right().Value(), kArithmeticImm)) {
     selector->Emit(negate_opcode, g.DefineAsRegister(node),
                    g.UseRegister(m.left().node()),
                    g.TempImmediate(static_cast<int32_t>(-m.right().Value())));
   } else {
     VisitBinop<Matcher>(selector, node, opcode, kArithmeticImm);
   }
 }
 
+
+// For multiplications by immediate of the form x * (2^k + 1), where k > 0,
+// return the value of k, otherwise return zero. This is used to reduce the
+// multiplication to addition with left shift: x + (x << k).
+template <typename Matcher>
+int32_t LeftShiftForReducedMultiply(Matcher* m) {
+  DCHECK(m->IsInt32Mul() || m->IsInt64Mul());
+  if (m->right().HasValue() && m->right().Value() >= 3) {
+    uint64_t value_minus_one = m->right().Value() - 1;
+    if (base::bits::IsPowerOfTwo64(value_minus_one)) {
+      return WhichPowerOf2_64(value_minus_one);
+    }
+  }
+  return 0;
+}
+
 }  // namespace
 
 
 void InstructionSelector::VisitLoad(Node* node) {
   MachineType rep = RepresentationOf(OpParameter<LoadRepresentation>(node));
   MachineType typ = TypeOf(OpParameter<LoadRepresentation>(node));
   Arm64OperandGenerator g(this);
   Node* base = node->InputAt(0);
   Node* index = node->InputAt(1);
   ArchOpcode opcode;
@@ skipping 539 matching lines @@
   Emit(kArm64Clz32, g.DefineAsRegister(node), g.UseRegister(node->InputAt(0)));
 }
 
 
 void InstructionSelector::VisitInt32Add(Node* node) {
   Arm64OperandGenerator g(this);
   Int32BinopMatcher m(node);
   // Select Madd(x, y, z) for Add(Mul(x, y), z).
   if (m.left().IsInt32Mul() && CanCover(node, m.left().node())) {
     Int32BinopMatcher mleft(m.left().node());
-    Emit(kArm64Madd32, g.DefineAsRegister(node),
-         g.UseRegister(mleft.left().node()),
-         g.UseRegister(mleft.right().node()), g.UseRegister(m.right().node()));
-    return;
+    // Check multiply can't be later reduced to addition with shift.
+    if (LeftShiftForReducedMultiply(&mleft) == 0) {
+      Emit(kArm64Madd32, g.DefineAsRegister(node),
+           g.UseRegister(mleft.left().node()),
+           g.UseRegister(mleft.right().node()),
+           g.UseRegister(m.right().node()));
+      return;
+    }
   }
-  // Select Madd(x, y, z) for Add(x, Mul(x, y)).
+  // Select Madd(x, y, z) for Add(z, Mul(x, y)).
   if (m.right().IsInt32Mul() && CanCover(node, m.right().node())) {
     Int32BinopMatcher mright(m.right().node());
-    Emit(kArm64Madd32, g.DefineAsRegister(node),
-         g.UseRegister(mright.left().node()),
-         g.UseRegister(mright.right().node()), g.UseRegister(m.left().node()));
-    return;
+    // Check multiply can't be later reduced to addition with shift.
+    if (LeftShiftForReducedMultiply(&mright) == 0) {
+      Emit(kArm64Madd32, g.DefineAsRegister(node),
+           g.UseRegister(mright.left().node()),
+           g.UseRegister(mright.right().node()),
+           g.UseRegister(m.left().node()));
+      return;
+    }
   }
   VisitAddSub<Int32BinopMatcher>(this, node, kArm64Add32, kArm64Sub32);
 }
 
 
 void InstructionSelector::VisitInt64Add(Node* node) {
   Arm64OperandGenerator g(this);
   Int64BinopMatcher m(node);
   // Select Madd(x, y, z) for Add(Mul(x, y), z).
   if (m.left().IsInt64Mul() && CanCover(node, m.left().node())) {
     Int64BinopMatcher mleft(m.left().node());
-    Emit(kArm64Madd, g.DefineAsRegister(node),
-         g.UseRegister(mleft.left().node()),
-         g.UseRegister(mleft.right().node()), g.UseRegister(m.right().node()));
-    return;
+    // Check multiply can't be later reduced to addition with shift.
+    if (LeftShiftForReducedMultiply(&mleft) == 0) {
+      Emit(kArm64Madd, g.DefineAsRegister(node),
+           g.UseRegister(mleft.left().node()),
+           g.UseRegister(mleft.right().node()),
+           g.UseRegister(m.right().node()));
+      return;
+    }
   }
-  // Select Madd(x, y, z) for Add(x, Mul(x, y)).
+  // Select Madd(x, y, z) for Add(z, Mul(x, y)).
   if (m.right().IsInt64Mul() && CanCover(node, m.right().node())) {
     Int64BinopMatcher mright(m.right().node());
-    Emit(kArm64Madd, g.DefineAsRegister(node),
-         g.UseRegister(mright.left().node()),
-         g.UseRegister(mright.right().node()), g.UseRegister(m.left().node()));
-    return;
+    // Check multiply can't be later reduced to addition with shift.
+    if (LeftShiftForReducedMultiply(&mright) == 0) {
+      Emit(kArm64Madd, g.DefineAsRegister(node),
+           g.UseRegister(mright.left().node()),
+           g.UseRegister(mright.right().node()),
+           g.UseRegister(m.left().node()));
+      return;
+    }
   }
   VisitAddSub<Int64BinopMatcher>(this, node, kArm64Add, kArm64Sub);
 }
 
 
 void InstructionSelector::VisitInt32Sub(Node* node) {
   Arm64OperandGenerator g(this);
   Int32BinopMatcher m(node);
 
-  // Select Msub(a, x, y) for Sub(a, Mul(x, y)).
+  // Select Msub(x, y, a) for Sub(a, Mul(x, y)).
   if (m.right().IsInt32Mul() && CanCover(node, m.right().node())) {
     Int32BinopMatcher mright(m.right().node());
-    Emit(kArm64Msub32, g.DefineAsRegister(node),
-         g.UseRegister(mright.left().node()),
-         g.UseRegister(mright.right().node()), g.UseRegister(m.left().node()));
-    return;
+    // Check multiply can't be later reduced to addition with shift.
+    if (LeftShiftForReducedMultiply(&mright) == 0) {
+      Emit(kArm64Msub32, g.DefineAsRegister(node),
+           g.UseRegister(mright.left().node()),
+           g.UseRegister(mright.right().node()),
+           g.UseRegister(m.left().node()));
+      return;
+    }
   }
 
   if (m.left().Is(0)) {
     Emit(kArm64Neg32, g.DefineAsRegister(node),
          g.UseRegister(m.right().node()));
   } else {
     VisitAddSub<Int32BinopMatcher>(this, node, kArm64Sub32, kArm64Add32);
   }
 }
 
 
 void InstructionSelector::VisitInt64Sub(Node* node) {
   Arm64OperandGenerator g(this);
   Int64BinopMatcher m(node);
 
-  // Select Msub(a, x, y) for Sub(a, Mul(x, y)).
+  // Select Msub(x, y, a) for Sub(a, Mul(x, y)).
   if (m.right().IsInt64Mul() && CanCover(node, m.right().node())) {
     Int64BinopMatcher mright(m.right().node());
-    Emit(kArm64Msub, g.DefineAsRegister(node),
-         g.UseRegister(mright.left().node()),
-         g.UseRegister(mright.right().node()), g.UseRegister(m.left().node()));
-    return;
+    // Check multiply can't be later reduced to addition with shift.
+    if (LeftShiftForReducedMultiply(&mright) == 0) {
+      Emit(kArm64Msub, g.DefineAsRegister(node),
+           g.UseRegister(mright.left().node()),
+           g.UseRegister(mright.right().node()),
+           g.UseRegister(m.left().node()));
+      return;
+    }
   }
 
   if (m.left().Is(0)) {
     Emit(kArm64Neg, g.DefineAsRegister(node), g.UseRegister(m.right().node()));
   } else {
     VisitAddSub<Int64BinopMatcher>(this, node, kArm64Sub, kArm64Add);
   }
 }
 
 
 void InstructionSelector::VisitInt32Mul(Node* node) {
   Arm64OperandGenerator g(this);
   Int32BinopMatcher m(node);
 
+  // First, try to reduce the multiplication to addition with left shift.
+  // x * (2^k + 1) -> x + (x << k)
+  int32_t shift = LeftShiftForReducedMultiply(&m);
+  if (shift > 0) {
+    Emit(kArm64Add32 | AddressingModeField::encode(kMode_Operand2_R_LSL_I),
+         g.DefineAsRegister(node), g.UseRegister(m.left().node()),
+         g.UseRegister(m.left().node()), g.TempImmediate(shift));
+    return;
+  }
+
   if (m.left().IsInt32Sub() && CanCover(node, m.left().node())) {
     Int32BinopMatcher mleft(m.left().node());
 
     // Select Mneg(x, y) for Mul(Sub(0, x), y).
     if (mleft.left().Is(0)) {
       Emit(kArm64Mneg32, g.DefineAsRegister(node),
            g.UseRegister(mleft.right().node()),
            g.UseRegister(m.right().node()));
       return;
     }
   }
 
   if (m.right().IsInt32Sub() && CanCover(node, m.right().node())) {
     Int32BinopMatcher mright(m.right().node());
 
     // Select Mneg(x, y) for Mul(x, Sub(0, y)).
     if (mright.left().Is(0)) {
       Emit(kArm64Mneg32, g.DefineAsRegister(node),
            g.UseRegister(m.left().node()),
            g.UseRegister(mright.right().node()));
       return;
     }
   }
 
-  // x * (2^k + 1) -> x + (x << k)
-  if (m.right().HasValue() && m.right().Value() > 0) {
-    int32_t value = m.right().Value();
-    if (base::bits::IsPowerOfTwo32(value - 1)) {
-      Emit(kArm64Add32 | AddressingModeField::encode(kMode_Operand2_R_LSL_I),
-           g.DefineAsRegister(node), g.UseRegister(m.left().node()),
-           g.UseRegister(m.left().node()),
-           g.TempImmediate(WhichPowerOf2(value - 1)));
-      return;
-    }
-  }
-
   VisitRRR(this, kArm64Mul32, node);
 }
 
 
 void InstructionSelector::VisitInt64Mul(Node* node) {
   Arm64OperandGenerator g(this);
   Int64BinopMatcher m(node);
 
+  // First, try to reduce the multiplication to addition with left shift.
+  // x * (2^k + 1) -> x + (x << k)
+  int32_t shift = LeftShiftForReducedMultiply(&m);
+  if (shift > 0) {
+    Emit(kArm64Add | AddressingModeField::encode(kMode_Operand2_R_LSL_I),
+         g.DefineAsRegister(node), g.UseRegister(m.left().node()),
+         g.UseRegister(m.left().node()), g.TempImmediate(shift));
+    return;
+  }
+
   if (m.left().IsInt64Sub() && CanCover(node, m.left().node())) {
     Int64BinopMatcher mleft(m.left().node());
 
     // Select Mneg(x, y) for Mul(Sub(0, x), y).
     if (mleft.left().Is(0)) {
       Emit(kArm64Mneg, g.DefineAsRegister(node),
            g.UseRegister(mleft.right().node()),
            g.UseRegister(m.right().node()));
       return;
     }
   }
 
   if (m.right().IsInt64Sub() && CanCover(node, m.right().node())) {
     Int64BinopMatcher mright(m.right().node());
 
     // Select Mneg(x, y) for Mul(x, Sub(0, y)).
     if (mright.left().Is(0)) {
       Emit(kArm64Mneg, g.DefineAsRegister(node), g.UseRegister(m.left().node()),
            g.UseRegister(mright.right().node()));
       return;
     }
   }
 
-  // x * (2^k + 1) -> x + (x << k)
-  if (m.right().HasValue() && m.right().Value() > 0) {
-    int64_t value = m.right().Value();
-    if (base::bits::IsPowerOfTwo64(value - 1)) {
-      Emit(kArm64Add | AddressingModeField::encode(kMode_Operand2_R_LSL_I),
-           g.DefineAsRegister(node), g.UseRegister(m.left().node()),
-           g.UseRegister(m.left().node()),
-           g.TempImmediate(WhichPowerOf2_64(value - 1)));
-      return;
-    }
-  }
-
   VisitRRR(this, kArm64Mul, node);
 }
 
 
 void InstructionSelector::VisitInt32MulHigh(Node* node) {
   Arm64OperandGenerator g(this);
   InstructionOperand const smull_operand = g.TempRegister();
   Emit(kArm64Smull, smull_operand, g.UseRegister(node->InputAt(0)),
        g.UseRegister(node->InputAt(1)));
   Emit(kArm64Asr, g.DefineAsRegister(node), smull_operand, g.TempImmediate(32));
@@ skipping 946 matching lines @@
          MachineOperatorBuilder::kFloat64RoundTruncate |
          MachineOperatorBuilder::kFloat64RoundTiesAway |
          MachineOperatorBuilder::kWord32ShiftIsSafe |
          MachineOperatorBuilder::kInt32DivIsSafe |
          MachineOperatorBuilder::kUint32DivIsSafe;
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8