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