LCOV - code coverage report
Current view: top level - src/compiler - node-matchers.h (source / functions) Hit Total Coverage
Test: app.info Lines: 192 193 99.5 %
Date: 2019-04-17 Functions: 41 42 97.6 %

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

Generated by: LCOV version 1.10