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