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