[turbofan] Optimize add operations to use 'leal' instruction on x64

src/compiler/node-matchers.h

Index: src/compiler/node-matchers.h
diff --git a/src/compiler/node-matchers.h b/src/compiler/node-matchers.h
index a55e7bf0a22b529ac36304b3458ae426ece9eead..514c53dc505b40b2f19aa0c6302e973fa2c6c0cf 100644
--- a/src/compiler/node-matchers.h
+++ b/src/compiler/node-matchers.h
@@ -116,7 +116,7 @@ struct HeapObjectMatcher FINAL
 // right hand sides of a binary operation and can put constants on the right
 // if they appear on the left hand side of a commutative operation.
 template <typename Left, typename Right>
-struct BinopMatcher FINAL : public NodeMatcher {
+struct BinopMatcher : public NodeMatcher {
   explicit BinopMatcher(Node* node)
       : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) {
     if (HasProperty(Operator::kCommutative)) PutConstantOnRight();
@@ -128,12 +128,17 @@ struct BinopMatcher FINAL : public NodeMatcher {
   bool IsFoldable() const { return left().HasValue() && right().HasValue(); }
   bool LeftEqualsRight() const { return left().node() == right().node(); }
 
+ protected:
+  void SwapInputs() {
+    std::swap(left_, right_);
+    node()->ReplaceInput(0, left().node());
+    node()->ReplaceInput(1, right().node());
+  }
+
  private:
   void PutConstantOnRight() {
     if (left().HasValue() && !right().HasValue()) {
-      std::swap(left_, right_);
-      node()->ReplaceInput(0, left().node());
-      node()->ReplaceInput(1, right().node());
+      SwapInputs();
     }
   }
 
@@ -150,6 +155,184 @@ typedef BinopMatcher<UintPtrMatcher, UintPtrMatcher> UintPtrBinopMatcher;
 typedef BinopMatcher<Float64Matcher, Float64Matcher> Float64BinopMatcher;
 typedef BinopMatcher<NumberMatcher, NumberMatcher> NumberBinopMatcher;
 
+struct Int32AddMatcher : public Int32BinopMatcher {
+  explicit Int32AddMatcher(Node* node)
+      : Int32BinopMatcher(node), has_scaled_input_(false), scale_factor_(-1) {
+    PutScaledInputOnLeft();
+    if (HasScaledInput()) {
+      Int32BinopMatcher m(left().node());
+      if (m.opcode() == IrOpcode::kWord32Shl) {
+        scale_factor_ = 1 << m.right().Value();
+      } else {
+        DCHECK(m.opcode() == IrOpcode::kInt32Mul);
+        scale_factor_ = m.right().Value();
+      }
+    }
+  }
+
+  bool HasScaledInput() const { return has_scaled_input_; }
+  Node* ScaledInput() const {
+    DCHECK(HasScaledInput());
+    return left().node()->InputAt(0);
+  }
+  int ScaleFactor() const {
+    DCHECK(HasScaledInput());
+    return scale_factor_;
+  }
+
+ private:
+  bool IsScaledInput(Node* node) const {

[titzer, 2014/11/06 11:47:06]

You could also have this method return the scaled power of 2, with -1
representing no match.

[danno, 2014/11/06 23:34:07]

Done.

+    if (node->opcode() == IrOpcode::kWord32Shl) {
+      Int32BinopMatcher m(node->InputAt(1));
+      if (m.right().HasValue()) {
+        int32_t value = m.right().Value();
+        return (value == 0) || (value == 1) || (value == 2) || (value == 3);
+      }
+    } else if (node->opcode() == IrOpcode::kInt32Mul) {
+      Int32BinopMatcher m(node->InputAt(1));
+      if (m.right().HasValue()) {
+        int32_t value = m.right().Value();
+        return (value == 1) || (value == 2) || (value == 4) || (value == 8);
+      }
+    }
+    return false;
+  }
+
+  void PutScaledInputOnLeft() {
+    if (IsScaledInput(right().node()) && !IsScaledInput(left().node())) {
+      SwapInputs();
+    }
+
+    if (IsScaledInput(left().node())) {
+      has_scaled_input_ = true;
+    } else {
+      if (right().opcode() == IrOpcode::kInt32Add &&
+          left().opcode() != IrOpcode::kInt32Add) {
+        SwapInputs();
+      }
+    }
+  }
+
+  bool has_scaled_input_;
+  int scale_factor_;
+};
+
+struct ScaledWithOffsetMatcher {
+  explicit ScaledWithOffsetMatcher(Node* node)
+      : matches_(false),
+        scaled_(NULL),
+        scale_factor_(1),
+        offset_(NULL),
+        constant_(NULL) {
+    if (node->opcode() != IrOpcode::kInt32Add) return;
+
+    // The Int32AddMatcher canonicalizes the order of constants and scale
+    // factors that are used as inputs, so instead of enumerating all possible
+    // patterns by brute force, checking for node clusters using the following
+    // templates in the following order suffices to find all of the interesting
+    // cases (S = scaled input, O = offset input, C = constant input):
+    // (S + (O + C))
+    // (S + (O + O))
+    // (S + C)
+    // (S + O)
+    // ((S + C) + O)
+    // ((S + O) + C)
+    // ((O + C) + O)
+    // ((O + O) + C)
+    // (O + C)
+    // (O + O)
+    Int32AddMatcher base_matcher(node);
+    Node* left = base_matcher.left().node();
+    Node* right = base_matcher.right().node();
+    if (base_matcher.HasScaledInput() && left->OwnedBy(node)) {
+      scaled_ = base_matcher.ScaledInput();
+      scale_factor_ = base_matcher.ScaleFactor();
+      if (right->opcode() == IrOpcode::kInt32Add && right->OwnedBy(node)) {
+        Int32AddMatcher right_matcher(right);
+        if (right_matcher.right().HasValue()) {
+          // (S + (O + C))
+          offset_ = right_matcher.left().node();
+          constant_ = right_matcher.right().node();
+        } else {
+          // (S + (O + O))
+          offset_ = right;
+        }
+      } else if (base_matcher.right().HasValue()) {
+        // (S + C)
+        constant_ = right;
+      } else {
+        // (S + O)
+        offset_ = right;
+      }
+    } else {
+      if (left->opcode() == IrOpcode::kInt32Add && left->OwnedBy(node)) {
+        Int32AddMatcher left_matcher(left);
+        Node* left_left = left_matcher.left().node();
+        Node* left_right = left_matcher.right().node();
+        if (left_matcher.HasScaledInput() && left_left->OwnedBy(left)) {
+          scaled_ = left_matcher.ScaledInput();
+          scale_factor_ = left_matcher.ScaleFactor();
+          if (left_matcher.right().HasValue()) {
+            // ((S + C) + O)
+            constant_ = left_right;
+            offset_ = right;
+          } else if (base_matcher.right().HasValue()) {
+            // ((S + O) + C)
+            offset_ = left_right;
+            constant_ = right;
+          } else {
+            // (O + O)
+            scaled_ = left;
+            offset_ = right;
+          }
+        } else {
+          if (left_matcher.right().HasValue()) {
+            // ((O + C) + O)
+            scaled_ = left_left;
+            constant_ = left_right;
+            offset_ = right;
+          } else if (base_matcher.right().HasValue()) {
+            // ((O + O) + C)
+            scaled_ = left_left;
+            offset_ = left_right;
+            constant_ = right;
+          } else {
+            // (O + O)
+            scaled_ = left;
+            offset_ = right;
+          }
+        }
+      } else {
+        if (base_matcher.right().HasValue()) {
+          // (O + C)
+          offset_ = left;
+          constant_ = right;
+        } else {
+          // (O + O)
+          offset_ = left;
+          scaled_ = right;
+        }
+      }
+    }
+    matches_ = true;
+  }
+
+  bool Matches() const { return matches_; }

[titzer, 2014/11/06 11:47:06]

Lower case for simple getters.

[danno, 2014/11/06 23:34:07]

Done.

+  Node* Scaled() const { return scaled_; }
+  int ScaleFactor() const { return scale_factor_; }
+  Node* Offset() const { return offset_; }
+  Node* Constant() const { return constant_; }
+
+ private:
+  bool matches_;
+
+ protected:
+  Node* scaled_;
+  int scale_factor_;
+  Node* offset_;
+  Node* constant_;
+};
+
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8