Home | History | Annotate | Download | only in compiler 
      1 // Copyright 2014 the V8 project authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #ifndef V8_COMPILER_NODE_MATCHERS_H_
      6 #define V8_COMPILER_NODE_MATCHERS_H_
      7 
      8 #include <cmath>
      9 
     10 #include "src/base/compiler-specific.h"
     11 #include "src/compiler/node.h"
     12 #include "src/compiler/operator.h"
     13 #include "src/double.h"
     14 #include "src/external-reference.h"
     15 #include "src/globals.h"
     16 
     17 namespace v8 {
     18 namespace internal {
     19 namespace compiler {
     20 
     21 class JSHeapBroker;
     22 
     23 // A pattern matcher for nodes.
     24 struct NodeMatcher {
     25   explicit NodeMatcher(Node* node) : node_(node) {}
     26 
     27   Node* node() const { return node_; }
     28   const Operator* op() const { return node()->op(); }
     29   IrOpcode::Value opcode() const { return node()->opcode(); }
     30 
     31   bool HasProperty(Operator::Property property) const {
     32     return op()->HasProperty(property);
     33   }
     34   Node* InputAt(int index) const { return node()->InputAt(index); }
     35 
     36   bool Equals(const Node* node) const { return node_ == node; }
     37 
     38   bool IsComparison() const;
     39 
     40 #define DEFINE_IS_OPCODE(Opcode) \
     41   bool Is##Opcode() const { return opcode() == IrOpcode::k##Opcode; }
     42   ALL_OP_LIST(DEFINE_IS_OPCODE)
     43 #undef DEFINE_IS_OPCODE
     44 
     45  private:
     46   Node* node_;
     47 };
     48 
     49 
     50 // A pattern matcher for abitrary value constants.
     51 template <typename T, IrOpcode::Value kOpcode>
     52 struct ValueMatcher : public NodeMatcher {
     53   typedef T ValueType;
     54 
     55   explicit ValueMatcher(Node* node)
     56       : NodeMatcher(node), value_(), has_value_(opcode() == kOpcode) {
     57     if (has_value_) {
     58       value_ = OpParameter<T>(node->op());
     59     }
     60   }
     61 
     62   bool HasValue() const { return has_value_; }
     63   const T& Value() const {
     64     DCHECK(HasValue());
     65     return value_;
     66   }
     67 
     68  private:
     69   T value_;
     70   bool has_value_;
     71 };
     72 
     73 
     74 template <>
     75 inline ValueMatcher<uint32_t, IrOpcode::kInt32Constant>::ValueMatcher(
     76     Node* node)
     77     : NodeMatcher(node),
     78       value_(),
     79       has_value_(opcode() == IrOpcode::kInt32Constant) {
     80   if (has_value_) {
     81     value_ = static_cast<uint32_t>(OpParameter<int32_t>(node->op()));
     82   }
     83 }
     84 
     85 
     86 template <>
     87 inline ValueMatcher<int64_t, IrOpcode::kInt64Constant>::ValueMatcher(Node* node)
     88     : NodeMatcher(node), value_(), has_value_(false) {
     89   if (opcode() == IrOpcode::kInt32Constant) {
     90     value_ = OpParameter<int32_t>(node->op());
     91     has_value_ = true;
     92   } else if (opcode() == IrOpcode::kInt64Constant) {
     93     value_ = OpParameter<int64_t>(node->op());
     94     has_value_ = true;
     95   }
     96 }
     97 
     98 
     99 template <>
    100 inline ValueMatcher<uint64_t, IrOpcode::kInt64Constant>::ValueMatcher(
    101     Node* node)
    102     : NodeMatcher(node), value_(), has_value_(false) {
    103   if (opcode() == IrOpcode::kInt32Constant) {
    104     value_ = static_cast<uint32_t>(OpParameter<int32_t>(node->op()));
    105     has_value_ = true;
    106   } else if (opcode() == IrOpcode::kInt64Constant) {
    107     value_ = static_cast<uint64_t>(OpParameter<int64_t>(node->op()));
    108     has_value_ = true;
    109   }
    110 }
    111 
    112 
    113 // A pattern matcher for integer constants.
    114 template <typename T, IrOpcode::Value kOpcode>
    115 struct IntMatcher final : public ValueMatcher<T, kOpcode> {
    116   explicit IntMatcher(Node* node) : ValueMatcher<T, kOpcode>(node) {}
    117 
    118   bool Is(const T& value) const {
    119     return this->HasValue() && this->Value() == value;
    120   }
    121   bool IsInRange(const T& low, const T& high) const {
    122     return this->HasValue() && low <= this->Value() && this->Value() <= high;
    123   }
    124   bool IsMultipleOf(T n) const {
    125     return this->HasValue() && (this->Value() % n) == 0;
    126   }
    127   bool IsPowerOf2() const {
    128     return this->HasValue() && this->Value() > 0 &&
    129            (this->Value() & (this->Value() - 1)) == 0;
    130   }
    131   bool IsNegativePowerOf2() const {
    132     return this->HasValue() && this->Value() < 0 &&
    133            (-this->Value() & (-this->Value() - 1)) == 0;
    134   }
    135   bool IsNegative() const { return this->HasValue() && this->Value() < 0; }
    136 };
    137 
    138 typedef IntMatcher<int32_t, IrOpcode::kInt32Constant> Int32Matcher;
    139 typedef IntMatcher<uint32_t, IrOpcode::kInt32Constant> Uint32Matcher;
    140 typedef IntMatcher<int64_t, IrOpcode::kInt64Constant> Int64Matcher;
    141 typedef IntMatcher<uint64_t, IrOpcode::kInt64Constant> Uint64Matcher;
    142 #if V8_HOST_ARCH_32_BIT
    143 typedef Int32Matcher IntPtrMatcher;
    144 typedef Uint32Matcher UintPtrMatcher;
    145 #else
    146 typedef Int64Matcher IntPtrMatcher;
    147 typedef Uint64Matcher UintPtrMatcher;
    148 #endif
    149 
    150 
    151 // A pattern matcher for floating point constants.
    152 template <typename T, IrOpcode::Value kOpcode>
    153 struct FloatMatcher final : public ValueMatcher<T, kOpcode> {
    154   explicit FloatMatcher(Node* node) : ValueMatcher<T, kOpcode>(node) {}
    155 
    156   bool Is(const T& value) const {
    157     return this->HasValue() && this->Value() == value;
    158   }
    159   bool IsInRange(const T& low, const T& high) const {
    160     return this->HasValue() && low <= this->Value() && this->Value() <= high;
    161   }
    162   bool IsMinusZero() const {
    163     return this->Is(0.0) && std::signbit(this->Value());
    164   }
    165   bool IsNegative() const { return this->HasValue() && this->Value() < 0.0; }
    166   bool IsNaN() const { return this->HasValue() && std::isnan(this->Value()); }
    167   bool IsZero() const { return this->Is(0.0) && !std::signbit(this->Value()); }
    168   bool IsNormal() const {
    169     return this->HasValue() && std::isnormal(this->Value());
    170   }
    171   bool IsInteger() const {
    172     return this->HasValue() && std::nearbyint(this->Value()) == this->Value();
    173   }
    174   bool IsPositiveOrNegativePowerOf2() const {
    175     if (!this->HasValue() || (this->Value() == 0.0)) {
    176       return false;
    177     }
    178     Double value = Double(this->Value());
    179     return !value.IsInfinite() && base::bits::IsPowerOfTwo(value.Significand());
    180   }
    181 };
    182 
    183 typedef FloatMatcher<float, IrOpcode::kFloat32Constant> Float32Matcher;
    184 typedef FloatMatcher<double, IrOpcode::kFloat64Constant> Float64Matcher;
    185 typedef FloatMatcher<double, IrOpcode::kNumberConstant> NumberMatcher;
    186 
    187 
    188 // A pattern matcher for heap object constants.
    189 struct HeapObjectMatcher final
    190     : public ValueMatcher<Handle<HeapObject>, IrOpcode::kHeapConstant> {
    191   explicit HeapObjectMatcher(Node* node)
    192       : ValueMatcher<Handle<HeapObject>, IrOpcode::kHeapConstant>(node) {}
    193 
    194   bool Is(Handle<HeapObject> const& value) const {
    195     return this->HasValue() && this->Value().address() == value.address();
    196   }
    197 
    198   ObjectRef Ref(JSHeapBroker* broker) const {
    199     return ObjectRef(broker, this->Value());
    200   }
    201 };
    202 
    203 
    204 // A pattern matcher for external reference constants.
    205 struct ExternalReferenceMatcher final
    206     : public ValueMatcher<ExternalReference, IrOpcode::kExternalConstant> {
    207   explicit ExternalReferenceMatcher(Node* node)
    208       : ValueMatcher<ExternalReference, IrOpcode::kExternalConstant>(node) {}
    209   bool Is(const ExternalReference& value) const {
    210     return this->HasValue() && this->Value() == value;
    211   }
    212 };
    213 
    214 
    215 // For shorter pattern matching code, this struct matches the inputs to
    216 // machine-level load operations.
    217 template <typename Object>
    218 struct LoadMatcher : public NodeMatcher {
    219   explicit LoadMatcher(Node* node)
    220       : NodeMatcher(node), object_(InputAt(0)), index_(InputAt(1)) {}
    221 
    222   typedef Object ObjectMatcher;
    223 
    224   Object const& object() const { return object_; }
    225   IntPtrMatcher const& index() const { return index_; }
    226 
    227  private:
    228   Object const object_;
    229   IntPtrMatcher const index_;
    230 };
    231 
    232 
    233 // For shorter pattern matching code, this struct matches both the left and
    234 // right hand sides of a binary operation and can put constants on the right
    235 // if they appear on the left hand side of a commutative operation.
    236 template <typename Left, typename Right>
    237 struct BinopMatcher : public NodeMatcher {
    238   explicit BinopMatcher(Node* node)
    239       : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) {
    240     if (HasProperty(Operator::kCommutative)) PutConstantOnRight();
    241   }
    242   BinopMatcher(Node* node, bool allow_input_swap)
    243       : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) {
    244     if (allow_input_swap) PutConstantOnRight();
    245   }
    246 
    247   typedef Left LeftMatcher;
    248   typedef Right RightMatcher;
    249 
    250   const Left& left() const { return left_; }
    251   const Right& right() const { return right_; }
    252 
    253   bool IsFoldable() const { return left().HasValue() && right().HasValue(); }
    254   bool LeftEqualsRight() const { return left().node() == right().node(); }
    255 
    256  protected:
    257   void SwapInputs() {
    258     std::swap(left_, right_);
    259     // TODO(tebbi): This modification should notify the reducers using
    260     // BinopMatcher. Alternatively, all reducers (especially value numbering)
    261     // could ignore the ordering for commutative binops.
    262     node()->ReplaceInput(0, left().node());
    263     node()->ReplaceInput(1, right().node());
    264   }
    265 
    266  private:
    267   void PutConstantOnRight() {
    268     if (left().HasValue() && !right().HasValue()) {
    269       SwapInputs();
    270     }
    271   }
    272 
    273   Left left_;
    274   Right right_;
    275 };
    276 
    277 typedef BinopMatcher<Int32Matcher, Int32Matcher> Int32BinopMatcher;
    278 typedef BinopMatcher<Uint32Matcher, Uint32Matcher> Uint32BinopMatcher;
    279 typedef BinopMatcher<Int64Matcher, Int64Matcher> Int64BinopMatcher;
    280 typedef BinopMatcher<Uint64Matcher, Uint64Matcher> Uint64BinopMatcher;
    281 typedef BinopMatcher<IntPtrMatcher, IntPtrMatcher> IntPtrBinopMatcher;
    282 typedef BinopMatcher<UintPtrMatcher, UintPtrMatcher> UintPtrBinopMatcher;
    283 typedef BinopMatcher<Float32Matcher, Float32Matcher> Float32BinopMatcher;
    284 typedef BinopMatcher<Float64Matcher, Float64Matcher> Float64BinopMatcher;
    285 typedef BinopMatcher<NumberMatcher, NumberMatcher> NumberBinopMatcher;
    286 typedef BinopMatcher<HeapObjectMatcher, HeapObjectMatcher>
    287     HeapObjectBinopMatcher;
    288 
    289 template <class BinopMatcher, IrOpcode::Value kMulOpcode,
    290           IrOpcode::Value kShiftOpcode>
    291 struct ScaleMatcher {
    292   explicit ScaleMatcher(Node* node, bool allow_power_of_two_plus_one = false)
    293       : scale_(-1), power_of_two_plus_one_(false) {
    294     if (node->InputCount() < 2) return;
    295     BinopMatcher m(node);
    296     if (node->opcode() == kShiftOpcode) {
    297       if (m.right().HasValue()) {
    298         typename BinopMatcher::RightMatcher::ValueType value =
    299             m.right().Value();
    300         if (value >= 0 && value <= 3) {
    301           scale_ = static_cast<int>(value);
    302         }
    303       }
    304     } else if (node->opcode() == kMulOpcode) {
    305       if (m.right().HasValue()) {
    306         typename BinopMatcher::RightMatcher::ValueType value =
    307             m.right().Value();
    308         if (value == 1) {
    309           scale_ = 0;
    310         } else if (value == 2) {
    311           scale_ = 1;
    312         } else if (value == 4) {
    313           scale_ = 2;
    314         } else if (value == 8) {
    315           scale_ = 3;
    316         } else if (allow_power_of_two_plus_one) {
    317           if (value == 3) {
    318             scale_ = 1;
    319             power_of_two_plus_one_ = true;
    320           } else if (value == 5) {
    321             scale_ = 2;
    322             power_of_two_plus_one_ = true;
    323           } else if (value == 9) {
    324             scale_ = 3;
    325             power_of_two_plus_one_ = true;
    326           }
    327         }
    328       }
    329     }
    330   }
    331 
    332   bool matches() const { return scale_ != -1; }
    333   int scale() const { return scale_; }
    334   bool power_of_two_plus_one() const { return power_of_two_plus_one_; }
    335 
    336  private:
    337   int scale_;
    338   bool power_of_two_plus_one_;
    339 };
    340 
    341 typedef ScaleMatcher<Int32BinopMatcher, IrOpcode::kInt32Mul,
    342                      IrOpcode::kWord32Shl> Int32ScaleMatcher;
    343 typedef ScaleMatcher<Int64BinopMatcher, IrOpcode::kInt64Mul,
    344                      IrOpcode::kWord64Shl> Int64ScaleMatcher;
    345 
    346 template <class BinopMatcher, IrOpcode::Value AddOpcode,
    347           IrOpcode::Value SubOpcode, IrOpcode::Value kMulOpcode,
    348           IrOpcode::Value kShiftOpcode>
    349 struct AddMatcher : public BinopMatcher {
    350   static const IrOpcode::Value kAddOpcode = AddOpcode;
    351   static const IrOpcode::Value kSubOpcode = SubOpcode;
    352   typedef ScaleMatcher<BinopMatcher, kMulOpcode, kShiftOpcode> Matcher;
    353 
    354   AddMatcher(Node* node, bool allow_input_swap)
    355       : BinopMatcher(node, allow_input_swap),
    356         scale_(-1),
    357         power_of_two_plus_one_(false) {
    358     Initialize(node, allow_input_swap);
    359   }
    360   explicit AddMatcher(Node* node)
    361       : BinopMatcher(node, node->op()->HasProperty(Operator::kCommutative)),
    362         scale_(-1),
    363         power_of_two_plus_one_(false) {
    364     Initialize(node, node->op()->HasProperty(Operator::kCommutative));
    365   }
    366 
    367   bool HasIndexInput() const { return scale_ != -1; }
    368   Node* IndexInput() const {
    369     DCHECK(HasIndexInput());
    370     return this->left().node()->InputAt(0);
    371   }
    372   int scale() const {
    373     DCHECK(HasIndexInput());
    374     return scale_;
    375   }
    376   bool power_of_two_plus_one() const { return power_of_two_plus_one_; }
    377 
    378  private:
    379   void Initialize(Node* node, bool allow_input_swap) {
    380     Matcher left_matcher(this->left().node(), true);
    381     if (left_matcher.matches()) {
    382       scale_ = left_matcher.scale();
    383       power_of_two_plus_one_ = left_matcher.power_of_two_plus_one();
    384       return;
    385     }
    386 
    387     if (!allow_input_swap) {
    388       return;
    389     }
    390 
    391     Matcher right_matcher(this->right().node(), true);
    392     if (right_matcher.matches()) {
    393       scale_ = right_matcher.scale();
    394       power_of_two_plus_one_ = right_matcher.power_of_two_plus_one();
    395       this->SwapInputs();
    396       return;
    397     }
    398 
    399     if ((this->left().opcode() != kSubOpcode &&
    400          this->left().opcode() != kAddOpcode) &&
    401         (this->right().opcode() == kAddOpcode ||
    402          this->right().opcode() == kSubOpcode)) {
    403       this->SwapInputs();
    404     }
    405   }
    406 
    407   int scale_;
    408   bool power_of_two_plus_one_;
    409 };
    410 
    411 typedef AddMatcher<Int32BinopMatcher, IrOpcode::kInt32Add, IrOpcode::kInt32Sub,
    412                    IrOpcode::kInt32Mul, IrOpcode::kWord32Shl>
    413     Int32AddMatcher;
    414 typedef AddMatcher<Int64BinopMatcher, IrOpcode::kInt64Add, IrOpcode::kInt64Sub,
    415                    IrOpcode::kInt64Mul, IrOpcode::kWord64Shl>
    416     Int64AddMatcher;
    417 
    418 enum DisplacementMode { kPositiveDisplacement, kNegativeDisplacement };
    419 
    420 enum class AddressOption : uint8_t {
    421   kAllowNone = 0u,
    422   kAllowInputSwap = 1u << 0,
    423   kAllowScale = 1u << 1,
    424   kAllowAll = kAllowInputSwap | kAllowScale
    425 };
    426 
    427 typedef base::Flags<AddressOption, uint8_t> AddressOptions;
    428 DEFINE_OPERATORS_FOR_FLAGS(AddressOptions);
    429 
    430 template <class AddMatcher>
    431 struct BaseWithIndexAndDisplacementMatcher {
    432   BaseWithIndexAndDisplacementMatcher(Node* node, AddressOptions options)
    433       : matches_(false),
    434         index_(nullptr),
    435         scale_(0),
    436         base_(nullptr),
    437         displacement_(nullptr),
    438         displacement_mode_(kPositiveDisplacement) {
    439     Initialize(node, options);
    440   }
    441 
    442   explicit BaseWithIndexAndDisplacementMatcher(Node* node)
    443       : matches_(false),
    444         index_(nullptr),
    445         scale_(0),
    446         base_(nullptr),
    447         displacement_(nullptr),
    448         displacement_mode_(kPositiveDisplacement) {
    449     Initialize(node, AddressOption::kAllowScale |
    450                          (node->op()->HasProperty(Operator::kCommutative)
    451                               ? AddressOption::kAllowInputSwap
    452                               : AddressOption::kAllowNone));
    453   }
    454 
    455   bool matches() const { return matches_; }
    456   Node* index() const { return index_; }
    457   int scale() const { return scale_; }
    458   Node* base() const { return base_; }
    459   Node* displacement() const { return displacement_; }
    460   DisplacementMode displacement_mode() const { return displacement_mode_; }
    461 
    462  private:
    463   bool matches_;
    464   Node* index_;
    465   int scale_;
    466   Node* base_;
    467   Node* displacement_;
    468   DisplacementMode displacement_mode_;
    469 
    470   void Initialize(Node* node, AddressOptions options) {
    471     // The BaseWithIndexAndDisplacementMatcher canonicalizes the order of
    472     // displacements and scale factors that are used as inputs, so instead of
    473     // enumerating all possible patterns by brute force, checking for node
    474     // clusters using the following templates in the following order suffices to
    475     // find all of the interesting cases (S = index * scale, B = base input, D =
    476     // displacement input):
    477     // (S + (B + D))
    478     // (S + (B + B))
    479     // (S + D)
    480     // (S + B)
    481     // ((S + D) + B)
    482     // ((S + B) + D)
    483     // ((B + D) + B)
    484     // ((B + B) + D)
    485     // (B + D)
    486     // (B + B)
    487     if (node->InputCount() < 2) return;
    488     AddMatcher m(node, options & AddressOption::kAllowInputSwap);
    489     Node* left = m.left().node();
    490     Node* right = m.right().node();
    491     Node* displacement = nullptr;
    492     Node* base = nullptr;
    493     Node* index = nullptr;
    494     Node* scale_expression = nullptr;
    495     bool power_of_two_plus_one = false;
    496     DisplacementMode displacement_mode = kPositiveDisplacement;
    497     int scale = 0;
    498     if (m.HasIndexInput() && OwnedByAddressingOperand(left)) {
    499       index = m.IndexInput();
    500       scale = m.scale();
    501       scale_expression = left;
    502       power_of_two_plus_one = m.power_of_two_plus_one();
    503       bool match_found = false;
    504       if (right->opcode() == AddMatcher::kSubOpcode &&
    505           OwnedByAddressingOperand(right)) {
    506         AddMatcher right_matcher(right);
    507         if (right_matcher.right().HasValue()) {
    508           // (S + (B - D))
    509           base = right_matcher.left().node();
    510           displacement = right_matcher.right().node();
    511           displacement_mode = kNegativeDisplacement;
    512           match_found = true;
    513         }
    514       }
    515       if (!match_found) {
    516         if (right->opcode() == AddMatcher::kAddOpcode &&
    517             OwnedByAddressingOperand(right)) {
    518           AddMatcher right_matcher(right);
    519           if (right_matcher.right().HasValue()) {
    520             // (S + (B + D))
    521             base = right_matcher.left().node();
    522             displacement = right_matcher.right().node();
    523           } else {
    524             // (S + (B + B))
    525             base = right;
    526           }
    527         } else if (m.right().HasValue()) {
    528           // (S + D)
    529           displacement = right;
    530         } else {
    531           // (S + B)
    532           base = right;
    533         }
    534       }
    535     } else {
    536       bool match_found = false;
    537       if (left->opcode() == AddMatcher::kSubOpcode &&
    538           OwnedByAddressingOperand(left)) {
    539         AddMatcher left_matcher(left);
    540         Node* left_left = left_matcher.left().node();
    541         Node* left_right = left_matcher.right().node();
    542         if (left_matcher.right().HasValue()) {
    543           if (left_matcher.HasIndexInput() && left_left->OwnedBy(left)) {
    544             // ((S - D) + B)
    545             index = left_matcher.IndexInput();
    546             scale = left_matcher.scale();
    547             scale_expression = left_left;
    548             power_of_two_plus_one = left_matcher.power_of_two_plus_one();
    549             displacement = left_right;
    550             displacement_mode = kNegativeDisplacement;
    551             base = right;
    552           } else {
    553             // ((B - D) + B)
    554             index = left_left;
    555             displacement = left_right;
    556             displacement_mode = kNegativeDisplacement;
    557             base = right;
    558           }
    559           match_found = true;
    560         }
    561       }
    562       if (!match_found) {
    563         if (left->opcode() == AddMatcher::kAddOpcode &&
    564             OwnedByAddressingOperand(left)) {
    565           AddMatcher left_matcher(left);
    566           Node* left_left = left_matcher.left().node();
    567           Node* left_right = left_matcher.right().node();
    568           if (left_matcher.HasIndexInput() && left_left->OwnedBy(left)) {
    569             if (left_matcher.right().HasValue()) {
    570               // ((S + D) + B)
    571               index = left_matcher.IndexInput();
    572               scale = left_matcher.scale();
    573               scale_expression = left_left;
    574               power_of_two_plus_one = left_matcher.power_of_two_plus_one();
    575               displacement = left_right;
    576               base = right;
    577             } else if (m.right().HasValue()) {
    578               if (left->OwnedBy(node)) {
    579                 // ((S + B) + D)
    580                 index = left_matcher.IndexInput();
    581                 scale = left_matcher.scale();
    582                 scale_expression = left_left;
    583                 power_of_two_plus_one = left_matcher.power_of_two_plus_one();
    584                 base = left_right;
    585                 displacement = right;
    586               } else {
    587                 // (B + D)
    588                 base = left;
    589                 displacement = right;
    590               }
    591             } else {
    592               // (B + B)
    593               index = left;
    594               base = right;
    595             }
    596           } else {
    597             if (left_matcher.right().HasValue()) {
    598               // ((B + D) + B)
    599               index = left_left;
    600               displacement = left_right;
    601               base = right;
    602             } else if (m.right().HasValue()) {
    603               if (left->OwnedBy(node)) {
    604                 // ((B + B) + D)
    605                 index = left_left;
    606                 base = left_right;
    607                 displacement = right;
    608               } else {
    609                 // (B + D)
    610                 base = left;
    611                 displacement = right;
    612               }
    613             } else {
    614               // (B + B)
    615               index = left;
    616               base = right;
    617             }
    618           }
    619         } else {
    620           if (m.right().HasValue()) {
    621             // (B + D)
    622             base = left;
    623             displacement = right;
    624           } else {
    625             // (B + B)
    626             base = left;
    627             index = right;
    628           }
    629         }
    630       }
    631     }
    632     int64_t value = 0;
    633     if (displacement != nullptr) {
    634       switch (displacement->opcode()) {
    635         case IrOpcode::kInt32Constant: {
    636           value = OpParameter<int32_t>(displacement->op());
    637           break;
    638         }
    639         case IrOpcode::kInt64Constant: {
    640           value = OpParameter<int64_t>(displacement->op());
    641           break;
    642         }
    643         default:
    644           UNREACHABLE();
    645           break;
    646       }
    647       if (value == 0) {
    648         displacement = nullptr;
    649       }
    650     }
    651     if (power_of_two_plus_one) {
    652       if (base != nullptr) {
    653         // If the scale requires explicitly using the index as the base, but a
    654         // base is already part of the match, then the (1 << N + 1) scale factor
    655         // can't be folded into the match and the entire index * scale
    656         // calculation must be computed separately.
    657         index = scale_expression;
    658         scale = 0;
    659       } else {
    660         base = index;
    661       }
    662     }
    663     if (!(options & AddressOption::kAllowScale) && scale != 0) {
    664       index = scale_expression;
    665       scale = 0;
    666     }
    667     base_ = base;
    668     displacement_ = displacement;
    669     displacement_mode_ = displacement_mode;
    670     index_ = index;
    671     scale_ = scale;
    672     matches_ = true;
    673   }
    674 
    675   static bool OwnedByAddressingOperand(Node* node) {
    676     for (auto use : node->use_edges()) {
    677       Node* from = use.from();
    678       switch (from->opcode()) {
    679         case IrOpcode::kLoad:
    680         case IrOpcode::kPoisonedLoad:
    681         case IrOpcode::kInt32Add:
    682         case IrOpcode::kInt64Add:
    683           // Skip addressing uses.
    684           break;
    685         case IrOpcode::kStore:
    686           // If the stored value is this node, it is not an addressing use.
    687           if (from->InputAt(2) == node) return false;
    688           // Otherwise it is used as an address and skipped.
    689           break;
    690         default:
    691           // Non-addressing use found.
    692           return false;
    693       }
    694     }
    695     return true;
    696   }
    697 };
    698 
    699 typedef BaseWithIndexAndDisplacementMatcher<Int32AddMatcher>
    700     BaseWithIndexAndDisplacement32Matcher;
    701 typedef BaseWithIndexAndDisplacementMatcher<Int64AddMatcher>
    702     BaseWithIndexAndDisplacement64Matcher;
    703 
    704 struct V8_EXPORT_PRIVATE BranchMatcher : public NON_EXPORTED_BASE(NodeMatcher) {
    705   explicit BranchMatcher(Node* branch);
    706 
    707   bool Matched() const { return if_true_ && if_false_; }
    708 
    709   Node* Branch() const { return node(); }
    710   Node* IfTrue() const { return if_true_; }
    711   Node* IfFalse() const { return if_false_; }
    712 
    713  private:
    714   Node* if_true_;
    715   Node* if_false_;
    716 };
    717 
    718 struct V8_EXPORT_PRIVATE DiamondMatcher
    719     : public NON_EXPORTED_BASE(NodeMatcher) {
    720   explicit DiamondMatcher(Node* merge);
    721 
    722   bool Matched() const { return branch_; }
    723   bool IfProjectionsAreOwned() const {
    724     return if_true_->OwnedBy(node()) && if_false_->OwnedBy(node());
    725   }
    726 
    727   Node* Branch() const { return branch_; }
    728   Node* IfTrue() const { return if_true_; }
    729   Node* IfFalse() const { return if_false_; }
    730   Node* Merge() const { return node(); }
    731 
    732   Node* TrueInputOf(Node* phi) const {
    733     DCHECK(IrOpcode::IsPhiOpcode(phi->opcode()));
    734     DCHECK_EQ(3, phi->InputCount());
    735     DCHECK_EQ(Merge(), phi->InputAt(2));
    736     return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 0 : 1);
    737   }
    738 
    739   Node* FalseInputOf(Node* phi) const {
    740     DCHECK(IrOpcode::IsPhiOpcode(phi->opcode()));
    741     DCHECK_EQ(3, phi->InputCount());
    742     DCHECK_EQ(Merge(), phi->InputAt(2));
    743     return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 1 : 0);
    744   }
    745 
    746  private:
    747   Node* branch_;
    748   Node* if_true_;
    749   Node* if_false_;
    750 };
    751 
    752 template <class BinopMatcher, IrOpcode::Value expected_opcode>
    753 struct WasmStackCheckMatcher {
    754   explicit WasmStackCheckMatcher(Node* compare) : compare_(compare) {}
    755 
    756   bool Matched() {
    757     if (compare_->opcode() != expected_opcode) return false;
    758     BinopMatcher m(compare_);
    759     return MatchedInternal(m.left(), m.right());
    760   }
    761 
    762  private:
    763   bool MatchedInternal(const typename BinopMatcher::LeftMatcher& l,
    764                        const typename BinopMatcher::RightMatcher& r) {
    765     // In wasm, the stack check is performed by loading the value given by
    766     // the address of a field stored in the instance object. That object is
    767     // passed as a parameter.
    768     if (l.IsLoad() && r.IsLoadStackPointer()) {
    769       LoadMatcher<LoadMatcher<NodeMatcher>> mleft(l.node());
    770       if (mleft.object().IsLoad() && mleft.index().Is(0) &&
    771           mleft.object().object().IsParameter()) {
    772         return true;
    773       }
    774     }
    775     return false;
    776   }
    777   Node* compare_;
    778 };
    779 
    780 template <class BinopMatcher, IrOpcode::Value expected_opcode>
    781 struct StackCheckMatcher {
    782   StackCheckMatcher(Isolate* isolate, Node* compare)
    783       : isolate_(isolate), compare_(compare) {}
    784   bool Matched() {
    785     // TODO(jgruber): Ideally, we could be more flexible here and also match the
    786     // same pattern with switched operands (i.e.: left is LoadStackPointer and
    787     // right is the js_stack_limit load). But to be correct in all cases, we'd
    788     // then have to invert the outcome of the stack check comparison.
    789     if (compare_->opcode() != expected_opcode) return false;
    790     BinopMatcher m(compare_);
    791     return MatchedInternal(m.left(), m.right());
    792   }
    793 
    794  private:
    795   bool MatchedInternal(const typename BinopMatcher::LeftMatcher& l,
    796                        const typename BinopMatcher::RightMatcher& r) {
    797     if (l.IsLoad() && r.IsLoadStackPointer()) {
    798       LoadMatcher<ExternalReferenceMatcher> mleft(l.node());
    799       ExternalReference js_stack_limit =
    800           ExternalReference::address_of_stack_limit(isolate_);
    801       if (mleft.object().Is(js_stack_limit) && mleft.index().Is(0)) return true;
    802     }
    803     return false;
    804   }
    805 
    806   Isolate* isolate_;
    807   Node* compare_;
    808 };
    809 
    810 }  // namespace compiler
    811 }  // namespace internal
    812 }  // namespace v8
    813 
    814 #endif  // V8_COMPILER_NODE_MATCHERS_H_
    815