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