[turbofan] Support subtraction displacements in BaseWithIndexAndDisplacementMatcher

src/compiler/node-matchers.h

 // 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.
 
 #ifndef V8_COMPILER_NODE_MATCHERS_H_
 #define V8_COMPILER_NODE_MATCHERS_H_
 
 #include <cmath>
 
 // TODO(turbofan): Move ExternalReference out of assembler.h
@@ skipping 300 matching lines @@
  private:
   int scale_;
   bool power_of_two_plus_one_;
 };
 
 typedef ScaleMatcher<Int32BinopMatcher, IrOpcode::kInt32Mul,
                      IrOpcode::kWord32Shl> Int32ScaleMatcher;
 typedef ScaleMatcher<Int64BinopMatcher, IrOpcode::kInt64Mul,
                      IrOpcode::kWord64Shl> Int64ScaleMatcher;
 
-
-template <class BinopMatcher, IrOpcode::Value kAddOpcode,
-          IrOpcode::Value kMulOpcode, IrOpcode::Value kShiftOpcode>
+template <class BinopMatcher, IrOpcode::Value AddOpcode,
+          IrOpcode::Value SubOpcode, IrOpcode::Value kMulOpcode,
+          IrOpcode::Value kShiftOpcode>
 struct AddMatcher : public BinopMatcher {
-  static const IrOpcode::Value kOpcode = kAddOpcode;
+  static const IrOpcode::Value kAddOpcode = AddOpcode;
+  static const IrOpcode::Value kSubOpcode = SubOpcode;
   typedef ScaleMatcher<BinopMatcher, kMulOpcode, kShiftOpcode> Matcher;
 
   AddMatcher(Node* node, bool allow_input_swap)
       : BinopMatcher(node, allow_input_swap),
         scale_(-1),
         power_of_two_plus_one_(false) {
     Initialize(node, allow_input_swap);
   }
   explicit AddMatcher(Node* node)
       : BinopMatcher(node, node->op()->HasProperty(Operator::kCommutative)),
@@ skipping 30 matching lines @@
     if (right_matcher.matches()) {
       scale_ = right_matcher.scale();
       power_of_two_plus_one_ = right_matcher.power_of_two_plus_one();
       this->SwapInputs();
       return;
     }
 
     if (this->right().opcode() == kAddOpcode &&
         this->left().opcode() != kAddOpcode) {
       this->SwapInputs();
+    } else if (this->right().opcode() == kSubOpcode &&
+               this->left().opcode() != kSubOpcode) {
+      this->SwapInputs();
     }
   }
 
   int scale_;
   bool power_of_two_plus_one_;
 };
 
-typedef AddMatcher<Int32BinopMatcher, IrOpcode::kInt32Add, IrOpcode::kInt32Mul,
-                   IrOpcode::kWord32Shl> Int32AddMatcher;
-typedef AddMatcher<Int64BinopMatcher, IrOpcode::kInt64Add, IrOpcode::kInt64Mul,
-                   IrOpcode::kWord64Shl> Int64AddMatcher;
+typedef AddMatcher<Int32BinopMatcher, IrOpcode::kInt32Add, IrOpcode::kInt32Sub,
+                   IrOpcode::kInt32Mul, IrOpcode::kWord32Shl>
+    Int32AddMatcher;
+typedef AddMatcher<Int64BinopMatcher, IrOpcode::kInt64Add, IrOpcode::kInt64Sub,
+                   IrOpcode::kInt64Mul, IrOpcode::kWord64Shl>
+    Int64AddMatcher;
 
+enum DisplacementMode { kPositiveDisplacement, kNegativeDisplacement };
 
 template <class AddMatcher>
 struct BaseWithIndexAndDisplacementMatcher {
   BaseWithIndexAndDisplacementMatcher(Node* node, bool allow_input_swap)
       : matches_(false),
         index_(nullptr),
         scale_(0),
         base_(nullptr),
-        displacement_(nullptr) {
+        displacement_(nullptr),
+        displacement_mode_(kPositiveDisplacement) {
     Initialize(node, allow_input_swap);
   }
 
   explicit BaseWithIndexAndDisplacementMatcher(Node* node)
       : matches_(false),
         index_(nullptr),
         scale_(0),
         base_(nullptr),
-        displacement_(nullptr) {
+        displacement_(nullptr),
+        displacement_mode_(kPositiveDisplacement) {
     Initialize(node, node->op()->HasProperty(Operator::kCommutative));
   }
 
   bool matches() const { return matches_; }
   Node* index() const { return index_; }
   int scale() const { return scale_; }
   Node* base() const { return base_; }
   Node* displacement() const { return displacement_; }
+  DisplacementMode displacement_mode() const { return displacement_mode_; }
 
  private:
   bool matches_;
   Node* index_;
   int scale_;
   Node* base_;
   Node* displacement_;
+  DisplacementMode displacement_mode_;
 
   void Initialize(Node* node, bool allow_input_swap) {
     // The BaseWithIndexAndDisplacementMatcher canonicalizes the order of
     // displacements 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 = index * scale, B = base input, D =
     // displacement input):
     // (S + (B + D))
     // (S + (B + B))
     // (S + D)
     // (S + B)
     // ((S + D) + B)
     // ((S + B) + D)
     // ((B + D) + B)
     // ((B + B) + D)
     // (B + D)
     // (B + B)
     if (node->InputCount() < 2) return;
     AddMatcher m(node, allow_input_swap);
     Node* left = m.left().node();
     Node* right = m.right().node();
     Node* displacement = nullptr;
     Node* base = nullptr;
     Node* index = nullptr;
     Node* scale_expression = nullptr;
     bool power_of_two_plus_one = false;
+    DisplacementMode displacement_mode = kPositiveDisplacement;
     int scale = 0;
     if (m.HasIndexInput() && left->OwnedBy(node)) {
       index = m.IndexInput();
       scale = m.scale();
       scale_expression = left;
       power_of_two_plus_one = m.power_of_two_plus_one();
-      if (right->opcode() == AddMatcher::kOpcode && right->OwnedBy(node)) {
+      bool match_found = false;
+      if (right->opcode() == AddMatcher::kSubOpcode && right->OwnedBy(node)) {
         AddMatcher right_matcher(right);
         if (right_matcher.right().HasValue()) {
-          // (S + (B + D))
+          // (S + (B - D))
           base = right_matcher.left().node();
           displacement = right_matcher.right().node();
+          displacement_mode = kNegativeDisplacement;
+          match_found = true;
+        }
+      }
+      if (!match_found) {
+        if (right->opcode() == AddMatcher::kAddOpcode && right->OwnedBy(node)) {
+          AddMatcher right_matcher(right);
+          if (right_matcher.right().HasValue()) {
+            // (S + (B + D))
+            base = right_matcher.left().node();
+            displacement = right_matcher.right().node();
+          } else {
+            // (S + (B + B))
+            base = right;
+          }
+        } else if (m.right().HasValue()) {
+          // (S + D)
+          displacement = right;
         } else {
-          // (S + (B + B))
+          // (S + B)
           base = right;
         }
-      } else if (m.right().HasValue()) {
-        // (S + D)
-        displacement = right;
-      } else {
-        // (S + B)
-        base = right;
       }
     } else {
-      if (left->opcode() == AddMatcher::kOpcode && left->OwnedBy(node)) {
+      bool match_found = false;
+      if (left->opcode() == AddMatcher::kSubOpcode && left->OwnedBy(node)) {
         AddMatcher left_matcher(left);
         Node* left_left = left_matcher.left().node();
         Node* left_right = left_matcher.right().node();
-        if (left_matcher.HasIndexInput() && left_left->OwnedBy(left)) {
-          if (left_matcher.right().HasValue()) {
-            // ((S + D) + B)
+        if (left_matcher.right().HasValue()) {
+          if (left_matcher.HasIndexInput() && left_left->OwnedBy(left)) {
+            // ((S - D) + B)
             index = left_matcher.IndexInput();
             scale = left_matcher.scale();
             scale_expression = left_left;
             power_of_two_plus_one = left_matcher.power_of_two_plus_one();
             displacement = left_right;
+            displacement_mode = kNegativeDisplacement;
             base = right;
-          } else if (m.right().HasValue()) {
-            // ((S + B) + D)
-            index = left_matcher.IndexInput();
-            scale = left_matcher.scale();
-            scale_expression = left_left;
-            power_of_two_plus_one = left_matcher.power_of_two_plus_one();
-            base = left_right;
+          } else {
+            // ((B - D) + B)
+            index = left_left;
+            displacement = left_right;
+            displacement_mode = kNegativeDisplacement;
+            base = right;
+          }
+          match_found = true;
+        }
+      }
+      if (!match_found) {
+        if (left->opcode() == AddMatcher::kAddOpcode && left->OwnedBy(node)) {
+          AddMatcher left_matcher(left);
+          Node* left_left = left_matcher.left().node();
+          Node* left_right = left_matcher.right().node();
+          if (left_matcher.HasIndexInput() && left_left->OwnedBy(left)) {
+            if (left_matcher.right().HasValue()) {
+              // ((S + D) + B)
+              index = left_matcher.IndexInput();
+              scale = left_matcher.scale();
+              scale_expression = left_left;
+              power_of_two_plus_one = left_matcher.power_of_two_plus_one();
+              displacement = left_right;
+              base = right;
+            } else if (m.right().HasValue()) {
+              // ((S + B) + D)
+              index = left_matcher.IndexInput();
+              scale = left_matcher.scale();
+              scale_expression = left_left;
+              power_of_two_plus_one = left_matcher.power_of_two_plus_one();
+              base = left_right;
+              displacement = right;
+            } else {
+              // (B + B)
+              index = left;
+              base = right;
+            }
+          } else {
+            if (left_matcher.right().HasValue()) {
+              // ((B + D) + B)
+              index = left_left;
+              displacement = left_right;
+              base = right;
+            } else if (m.right().HasValue()) {
+              // ((B + B) + D)
+              index = left_left;
+              base = left_right;
+              displacement = right;
+            } else {
+              // (B + B)
+              index = left;
+              base = right;
+            }
+          }
+        } else {
+          if (m.right().HasValue()) {
+            // (B + D)
+            base = left;
             displacement = right;
           } else {
             // (B + B)
-            index = left;
-            base = right;
+            base = left;
+            index = right;
           }
-        } else {
-          if (left_matcher.right().HasValue()) {
-            // ((B + D) + B)
-            index = left_left;
-            displacement = left_right;
-            base = right;
-          } else if (m.right().HasValue()) {
-            // ((B + B) + D)
-            index = left_left;
-            base = left_right;
-            displacement = right;
-          } else {
-            // (B + B)
-            index = left;
-            base = right;
-          }
-        }
-      } else {
-        if (m.right().HasValue()) {
-          // (B + D)
-          base = left;
-          displacement = right;
-        } else {
-          // (B + B)
-          base = left;
-          index = right;
         }
       }
     }
     int64_t value = 0;
     if (displacement != nullptr) {
       switch (displacement->opcode()) {
         case IrOpcode::kInt32Constant: {
           value = OpParameter<int32_t>(displacement);
           break;
         }
@@ skipping 16 matching lines @@
         // can't be folded into the match and the entire index * scale
         // calculation must be computed separately.
         index = scale_expression;
         scale = 0;
       } else {
         base = index;
       }
     }
     base_ = base;
     displacement_ = displacement;
+    displacement_mode_ = displacement_mode;
     index_ = index;
     scale_ = scale;
     matches_ = true;
   }
 };
 
 typedef BaseWithIndexAndDisplacementMatcher<Int32AddMatcher>
     BaseWithIndexAndDisplacement32Matcher;
 typedef BaseWithIndexAndDisplacementMatcher<Int64AddMatcher>
     BaseWithIndexAndDisplacement64Matcher;
@@ skipping 44 matching lines @@
   Node* branch_;
   Node* if_true_;
   Node* if_false_;
 };
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_COMPILER_NODE_MATCHERS_H_