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->op());
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->op()));
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->op());
90 has_value_ = true;
91 } else if (opcode() == IrOpcode::kInt64Constant) {
92 value_ = OpParameter<int64_t>(node->op());
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->op()));
104 has_value_ = true;
105 } else if (opcode() == IrOpcode::kInt64Constant) {
106 value_ = static_cast<uint64_t>(OpParameter<int64_t>(node->op()));
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() && base::bits::IsPowerOfTwo(value.Significand());
179 }
180 };
181
182 typedef FloatMatcher<float, IrOpcode::kFloat32Constant> Float32Matcher;
183 typedef FloatMatcher<double, IrOpcode::kFloat64Constant> Float64Matcher;
184 typedef FloatMatcher<double, IrOpcode::kNumberConstant> NumberMatcher;
185
186
187 // A pattern matcher for heap object constants.
188 struct HeapObjectMatcher final
189 : public ValueMatcher<Handle<HeapObject>, IrOpcode::kHeapConstant> {
HeapObjectMatcherfinal190 explicit HeapObjectMatcher(Node* node)
191 : ValueMatcher<Handle<HeapObject>, IrOpcode::kHeapConstant>(node) {}
192
Isfinal193 bool Is(Handle<HeapObject> const& value) const {
194 return this->HasValue() && this->Value().address() == value.address();
195 }
196 };
197
198
199 // A pattern matcher for external reference constants.
200 struct ExternalReferenceMatcher final
201 : public ValueMatcher<ExternalReference, IrOpcode::kExternalConstant> {
ExternalReferenceMatcherfinal202 explicit ExternalReferenceMatcher(Node* node)
203 : ValueMatcher<ExternalReference, IrOpcode::kExternalConstant>(node) {}
Isfinal204 bool Is(const ExternalReference& value) const {
205 return this->HasValue() && this->Value() == value;
206 }
207 };
208
209
210 // For shorter pattern matching code, this struct matches the inputs to
211 // machine-level load operations.
212 template <typename Object>
213 struct LoadMatcher : public NodeMatcher {
LoadMatcherLoadMatcher214 explicit LoadMatcher(Node* node)
215 : NodeMatcher(node), object_(InputAt(0)), index_(InputAt(1)) {}
216
217 typedef Object ObjectMatcher;
218
objectLoadMatcher219 Object const& object() const { return object_; }
indexLoadMatcher220 IntPtrMatcher const& index() const { return index_; }
221
222 private:
223 Object const object_;
224 IntPtrMatcher const index_;
225 };
226
227
228 // For shorter pattern matching code, this struct matches both the left and
229 // right hand sides of a binary operation and can put constants on the right
230 // if they appear on the left hand side of a commutative operation.
231 template <typename Left, typename Right>
232 struct BinopMatcher : public NodeMatcher {
BinopMatcherBinopMatcher233 explicit BinopMatcher(Node* node)
234 : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) {
235 if (HasProperty(Operator::kCommutative)) PutConstantOnRight();
236 }
BinopMatcherBinopMatcher237 BinopMatcher(Node* node, bool allow_input_swap)
238 : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) {
239 if (allow_input_swap) PutConstantOnRight();
240 }
241
242 typedef Left LeftMatcher;
243 typedef Right RightMatcher;
244
leftBinopMatcher245 const Left& left() const { return left_; }
rightBinopMatcher246 const Right& right() const { return right_; }
247
IsFoldableBinopMatcher248 bool IsFoldable() const { return left().HasValue() && right().HasValue(); }
LeftEqualsRightBinopMatcher249 bool LeftEqualsRight() const { return left().node() == right().node(); }
250
251 protected:
SwapInputsBinopMatcher252 void SwapInputs() {
253 std::swap(left_, right_);
254 // TODO(tebbi): This modification should notify the reducers using
255 // BinopMatcher. Alternatively, all reducers (especially value numbering)
256 // could ignore the ordering for commutative binops.
257 node()->ReplaceInput(0, left().node());
258 node()->ReplaceInput(1, right().node());
259 }
260
261 private:
PutConstantOnRightBinopMatcher262 void PutConstantOnRight() {
263 if (left().HasValue() && !right().HasValue()) {
264 SwapInputs();
265 }
266 }
267
268 Left left_;
269 Right right_;
270 };
271
272 typedef BinopMatcher<Int32Matcher, Int32Matcher> Int32BinopMatcher;
273 typedef BinopMatcher<Uint32Matcher, Uint32Matcher> Uint32BinopMatcher;
274 typedef BinopMatcher<Int64Matcher, Int64Matcher> Int64BinopMatcher;
275 typedef BinopMatcher<Uint64Matcher, Uint64Matcher> Uint64BinopMatcher;
276 typedef BinopMatcher<IntPtrMatcher, IntPtrMatcher> IntPtrBinopMatcher;
277 typedef BinopMatcher<UintPtrMatcher, UintPtrMatcher> UintPtrBinopMatcher;
278 typedef BinopMatcher<Float32Matcher, Float32Matcher> Float32BinopMatcher;
279 typedef BinopMatcher<Float64Matcher, Float64Matcher> Float64BinopMatcher;
280 typedef BinopMatcher<NumberMatcher, NumberMatcher> NumberBinopMatcher;
281 typedef BinopMatcher<HeapObjectMatcher, HeapObjectMatcher>
282 HeapObjectBinopMatcher;
283
284 template <class BinopMatcher, IrOpcode::Value kMulOpcode,
285 IrOpcode::Value kShiftOpcode>
286 struct ScaleMatcher {
287 explicit ScaleMatcher(Node* node, bool allow_power_of_two_plus_one = false)
288 : scale_(-1), power_of_two_plus_one_(false) {
289 if (node->InputCount() < 2) return;
290 BinopMatcher m(node);
291 if (node->opcode() == kShiftOpcode) {
292 if (m.right().HasValue()) {
293 typename BinopMatcher::RightMatcher::ValueType value =
294 m.right().Value();
295 if (value >= 0 && value <= 3) {
296 scale_ = static_cast<int>(value);
297 }
298 }
299 } else if (node->opcode() == kMulOpcode) {
300 if (m.right().HasValue()) {
301 typename BinopMatcher::RightMatcher::ValueType value =
302 m.right().Value();
303 if (value == 1) {
304 scale_ = 0;
305 } else if (value == 2) {
306 scale_ = 1;
307 } else if (value == 4) {
308 scale_ = 2;
309 } else if (value == 8) {
310 scale_ = 3;
311 } else if (allow_power_of_two_plus_one) {
312 if (value == 3) {
313 scale_ = 1;
314 power_of_two_plus_one_ = true;
315 } else if (value == 5) {
316 scale_ = 2;
317 power_of_two_plus_one_ = true;
318 } else if (value == 9) {
319 scale_ = 3;
320 power_of_two_plus_one_ = true;
321 }
322 }
323 }
324 }
325 }
326
matchesScaleMatcher327 bool matches() const { return scale_ != -1; }
scaleScaleMatcher328 int scale() const { return scale_; }
power_of_two_plus_oneScaleMatcher329 bool power_of_two_plus_one() const { return power_of_two_plus_one_; }
330
331 private:
332 int scale_;
333 bool power_of_two_plus_one_;
334 };
335
336 typedef ScaleMatcher<Int32BinopMatcher, IrOpcode::kInt32Mul,
337 IrOpcode::kWord32Shl> Int32ScaleMatcher;
338 typedef ScaleMatcher<Int64BinopMatcher, IrOpcode::kInt64Mul,
339 IrOpcode::kWord64Shl> Int64ScaleMatcher;
340
341 template <class BinopMatcher, IrOpcode::Value AddOpcode,
342 IrOpcode::Value SubOpcode, IrOpcode::Value kMulOpcode,
343 IrOpcode::Value kShiftOpcode>
344 struct AddMatcher : public BinopMatcher {
345 static const IrOpcode::Value kAddOpcode = AddOpcode;
346 static const IrOpcode::Value kSubOpcode = SubOpcode;
347 typedef ScaleMatcher<BinopMatcher, kMulOpcode, kShiftOpcode> Matcher;
348
AddMatcherAddMatcher349 AddMatcher(Node* node, bool allow_input_swap)
350 : BinopMatcher(node, allow_input_swap),
351 scale_(-1),
352 power_of_two_plus_one_(false) {
353 Initialize(node, allow_input_swap);
354 }
AddMatcherAddMatcher355 explicit AddMatcher(Node* node)
356 : BinopMatcher(node, node->op()->HasProperty(Operator::kCommutative)),
357 scale_(-1),
358 power_of_two_plus_one_(false) {
359 Initialize(node, node->op()->HasProperty(Operator::kCommutative));
360 }
361
HasIndexInputAddMatcher362 bool HasIndexInput() const { return scale_ != -1; }
IndexInputAddMatcher363 Node* IndexInput() const {
364 DCHECK(HasIndexInput());
365 return this->left().node()->InputAt(0);
366 }
scaleAddMatcher367 int scale() const {
368 DCHECK(HasIndexInput());
369 return scale_;
370 }
power_of_two_plus_oneAddMatcher371 bool power_of_two_plus_one() const { return power_of_two_plus_one_; }
372
373 private:
InitializeAddMatcher374 void Initialize(Node* node, bool allow_input_swap) {
375 Matcher left_matcher(this->left().node(), true);
376 if (left_matcher.matches()) {
377 scale_ = left_matcher.scale();
378 power_of_two_plus_one_ = left_matcher.power_of_two_plus_one();
379 return;
380 }
381
382 if (!allow_input_swap) {
383 return;
384 }
385
386 Matcher right_matcher(this->right().node(), true);
387 if (right_matcher.matches()) {
388 scale_ = right_matcher.scale();
389 power_of_two_plus_one_ = right_matcher.power_of_two_plus_one();
390 this->SwapInputs();
391 return;
392 }
393
394 if (this->right().opcode() == kAddOpcode &&
395 this->left().opcode() != kAddOpcode) {
396 this->SwapInputs();
397 } else if (this->right().opcode() == kSubOpcode &&
398 this->left().opcode() != kSubOpcode) {
399 this->SwapInputs();
400 }
401 }
402
403 int scale_;
404 bool power_of_two_plus_one_;
405 };
406
407 typedef AddMatcher<Int32BinopMatcher, IrOpcode::kInt32Add, IrOpcode::kInt32Sub,
408 IrOpcode::kInt32Mul, IrOpcode::kWord32Shl>
409 Int32AddMatcher;
410 typedef AddMatcher<Int64BinopMatcher, IrOpcode::kInt64Add, IrOpcode::kInt64Sub,
411 IrOpcode::kInt64Mul, IrOpcode::kWord64Shl>
412 Int64AddMatcher;
413
414 enum DisplacementMode { kPositiveDisplacement, kNegativeDisplacement };
415
416 enum class AddressOption : uint8_t {
417 kAllowNone = 0u,
418 kAllowInputSwap = 1u << 0,
419 kAllowScale = 1u << 1,
420 kAllowAll = kAllowInputSwap | kAllowScale
421 };
422
423 typedef base::Flags<AddressOption, uint8_t> AddressOptions;
424 DEFINE_OPERATORS_FOR_FLAGS(AddressOptions);
425
426 template <class AddMatcher>
427 struct BaseWithIndexAndDisplacementMatcher {
BaseWithIndexAndDisplacementMatcherBaseWithIndexAndDisplacementMatcher428 BaseWithIndexAndDisplacementMatcher(Node* node, AddressOptions options)
429 : matches_(false),
430 index_(nullptr),
431 scale_(0),
432 base_(nullptr),
433 displacement_(nullptr),
434 displacement_mode_(kPositiveDisplacement) {
435 Initialize(node, options);
436 }
437
BaseWithIndexAndDisplacementMatcherBaseWithIndexAndDisplacementMatcher438 explicit BaseWithIndexAndDisplacementMatcher(Node* node)
439 : matches_(false),
440 index_(nullptr),
441 scale_(0),
442 base_(nullptr),
443 displacement_(nullptr),
444 displacement_mode_(kPositiveDisplacement) {
445 Initialize(node, AddressOption::kAllowScale |
446 (node->op()->HasProperty(Operator::kCommutative)
447 ? AddressOption::kAllowInputSwap
448 : AddressOption::kAllowNone));
449 }
450
matchesBaseWithIndexAndDisplacementMatcher451 bool matches() const { return matches_; }
indexBaseWithIndexAndDisplacementMatcher452 Node* index() const { return index_; }
scaleBaseWithIndexAndDisplacementMatcher453 int scale() const { return scale_; }
baseBaseWithIndexAndDisplacementMatcher454 Node* base() const { return base_; }
displacementBaseWithIndexAndDisplacementMatcher455 Node* displacement() const { return displacement_; }
displacement_modeBaseWithIndexAndDisplacementMatcher456 DisplacementMode displacement_mode() const { return displacement_mode_; }
457
458 private:
459 bool matches_;
460 Node* index_;
461 int scale_;
462 Node* base_;
463 Node* displacement_;
464 DisplacementMode displacement_mode_;
465
InitializeBaseWithIndexAndDisplacementMatcher466 void Initialize(Node* node, AddressOptions options) {
467 // The BaseWithIndexAndDisplacementMatcher canonicalizes the order of
468 // displacements and scale factors that are used as inputs, so instead of
469 // enumerating all possible patterns by brute force, checking for node
470 // clusters using the following templates in the following order suffices to
471 // find all of the interesting cases (S = index * scale, B = base input, D =
472 // displacement input):
473 // (S + (B + D))
474 // (S + (B + B))
475 // (S + D)
476 // (S + B)
477 // ((S + D) + B)
478 // ((S + B) + D)
479 // ((B + D) + B)
480 // ((B + B) + D)
481 // (B + D)
482 // (B + B)
483 if (node->InputCount() < 2) return;
484 AddMatcher m(node, options & AddressOption::kAllowInputSwap);
485 Node* left = m.left().node();
486 Node* right = m.right().node();
487 Node* displacement = nullptr;
488 Node* base = nullptr;
489 Node* index = nullptr;
490 Node* scale_expression = nullptr;
491 bool power_of_two_plus_one = false;
492 DisplacementMode displacement_mode = kPositiveDisplacement;
493 int scale = 0;
494 if (m.HasIndexInput() && left->OwnedByAddressingOperand()) {
495 index = m.IndexInput();
496 scale = m.scale();
497 scale_expression = left;
498 power_of_two_plus_one = m.power_of_two_plus_one();
499 bool match_found = false;
500 if (right->opcode() == AddMatcher::kSubOpcode &&
501 right->OwnedByAddressingOperand()) {
502 AddMatcher right_matcher(right);
503 if (right_matcher.right().HasValue()) {
504 // (S + (B - D))
505 base = right_matcher.left().node();
506 displacement = right_matcher.right().node();
507 displacement_mode = kNegativeDisplacement;
508 match_found = true;
509 }
510 }
511 if (!match_found) {
512 if (right->opcode() == AddMatcher::kAddOpcode &&
513 right->OwnedByAddressingOperand()) {
514 AddMatcher right_matcher(right);
515 if (right_matcher.right().HasValue()) {
516 // (S + (B + D))
517 base = right_matcher.left().node();
518 displacement = right_matcher.right().node();
519 } else {
520 // (S + (B + B))
521 base = right;
522 }
523 } else if (m.right().HasValue()) {
524 // (S + D)
525 displacement = right;
526 } else {
527 // (S + B)
528 base = right;
529 }
530 }
531 } else {
532 bool match_found = false;
533 if (left->opcode() == AddMatcher::kSubOpcode &&
534 left->OwnedByAddressingOperand()) {
535 AddMatcher left_matcher(left);
536 Node* left_left = left_matcher.left().node();
537 Node* left_right = left_matcher.right().node();
538 if (left_matcher.right().HasValue()) {
539 if (left_matcher.HasIndexInput() && left_left->OwnedBy(left)) {
540 // ((S - D) + B)
541 index = left_matcher.IndexInput();
542 scale = left_matcher.scale();
543 scale_expression = left_left;
544 power_of_two_plus_one = left_matcher.power_of_two_plus_one();
545 displacement = left_right;
546 displacement_mode = kNegativeDisplacement;
547 base = right;
548 } else {
549 // ((B - D) + B)
550 index = left_left;
551 displacement = left_right;
552 displacement_mode = kNegativeDisplacement;
553 base = right;
554 }
555 match_found = true;
556 }
557 }
558 if (!match_found) {
559 if (left->opcode() == AddMatcher::kAddOpcode &&
560 left->OwnedByAddressingOperand()) {
561 AddMatcher left_matcher(left);
562 Node* left_left = left_matcher.left().node();
563 Node* left_right = left_matcher.right().node();
564 if (left_matcher.HasIndexInput() && left_left->OwnedBy(left)) {
565 if (left_matcher.right().HasValue()) {
566 // ((S + D) + B)
567 index = left_matcher.IndexInput();
568 scale = left_matcher.scale();
569 scale_expression = left_left;
570 power_of_two_plus_one = left_matcher.power_of_two_plus_one();
571 displacement = left_right;
572 base = right;
573 } else if (m.right().HasValue()) {
574 if (left->OwnedBy(node)) {
575 // ((S + B) + D)
576 index = left_matcher.IndexInput();
577 scale = left_matcher.scale();
578 scale_expression = left_left;
579 power_of_two_plus_one = left_matcher.power_of_two_plus_one();
580 base = left_right;
581 displacement = right;
582 } else {
583 // (B + D)
584 base = left;
585 displacement = right;
586 }
587 } else {
588 // (B + B)
589 index = left;
590 base = right;
591 }
592 } else {
593 if (left_matcher.right().HasValue()) {
594 // ((B + D) + B)
595 index = left_left;
596 displacement = left_right;
597 base = right;
598 } else if (m.right().HasValue()) {
599 if (left->OwnedBy(node)) {
600 // ((B + B) + D)
601 index = left_left;
602 base = left_right;
603 displacement = right;
604 } else {
605 // (B + D)
606 base = left;
607 displacement = right;
608 }
609 } else {
610 // (B + B)
611 index = left;
612 base = right;
613 }
614 }
615 } else {
616 if (m.right().HasValue()) {
617 // (B + D)
618 base = left;
619 displacement = right;
620 } else {
621 // (B + B)
622 base = left;
623 index = right;
624 }
625 }
626 }
627 }
628 int64_t value = 0;
629 if (displacement != nullptr) {
630 switch (displacement->opcode()) {
631 case IrOpcode::kInt32Constant: {
632 value = OpParameter<int32_t>(displacement->op());
633 break;
634 }
635 case IrOpcode::kInt64Constant: {
636 value = OpParameter<int64_t>(displacement->op());
637 break;
638 }
639 default:
640 UNREACHABLE();
641 break;
642 }
643 if (value == 0) {
644 displacement = nullptr;
645 }
646 }
647 if (power_of_two_plus_one) {
648 if (base != nullptr) {
649 // If the scale requires explicitly using the index as the base, but a
650 // base is already part of the match, then the (1 << N + 1) scale factor
651 // can't be folded into the match and the entire index * scale
652 // calculation must be computed separately.
653 index = scale_expression;
654 scale = 0;
655 } else {
656 base = index;
657 }
658 }
659 if (!(options & AddressOption::kAllowScale) && scale != 0) {
660 index = scale_expression;
661 scale = 0;
662 }
663 base_ = base;
664 displacement_ = displacement;
665 displacement_mode_ = displacement_mode;
666 index_ = index;
667 scale_ = scale;
668 matches_ = true;
669 }
670 };
671
672 typedef BaseWithIndexAndDisplacementMatcher<Int32AddMatcher>
673 BaseWithIndexAndDisplacement32Matcher;
674 typedef BaseWithIndexAndDisplacementMatcher<Int64AddMatcher>
675 BaseWithIndexAndDisplacement64Matcher;
676
677 struct V8_EXPORT_PRIVATE BranchMatcher : public NON_EXPORTED_BASE(NodeMatcher) {
678 explicit BranchMatcher(Node* branch);
679
MatchedBranchMatcher680 bool Matched() const { return if_true_ && if_false_; }
681
BranchBranchMatcher682 Node* Branch() const { return node(); }
IfTrueBranchMatcher683 Node* IfTrue() const { return if_true_; }
IfFalseBranchMatcher684 Node* IfFalse() const { return if_false_; }
685
686 private:
687 Node* if_true_;
688 Node* if_false_;
689 };
690
691 struct V8_EXPORT_PRIVATE DiamondMatcher
692 : public NON_EXPORTED_BASE(NodeMatcher) {
693 explicit DiamondMatcher(Node* merge);
694
MatchedDiamondMatcher695 bool Matched() const { return branch_; }
IfProjectionsAreOwnedDiamondMatcher696 bool IfProjectionsAreOwned() const {
697 return if_true_->OwnedBy(node()) && if_false_->OwnedBy(node());
698 }
699
BranchDiamondMatcher700 Node* Branch() const { return branch_; }
IfTrueDiamondMatcher701 Node* IfTrue() const { return if_true_; }
IfFalseDiamondMatcher702 Node* IfFalse() const { return if_false_; }
MergeDiamondMatcher703 Node* Merge() const { return node(); }
704
TrueInputOfDiamondMatcher705 Node* TrueInputOf(Node* phi) const {
706 DCHECK(IrOpcode::IsPhiOpcode(phi->opcode()));
707 DCHECK_EQ(3, phi->InputCount());
708 DCHECK_EQ(Merge(), phi->InputAt(2));
709 return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 0 : 1);
710 }
711
FalseInputOfDiamondMatcher712 Node* FalseInputOf(Node* phi) const {
713 DCHECK(IrOpcode::IsPhiOpcode(phi->opcode()));
714 DCHECK_EQ(3, phi->InputCount());
715 DCHECK_EQ(Merge(), phi->InputAt(2));
716 return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 1 : 0);
717 }
718
719 private:
720 Node* branch_;
721 Node* if_true_;
722 Node* if_false_;
723 };
724
725 } // namespace compiler
726 } // namespace internal
727 } // namespace v8
728
729 #endif // V8_COMPILER_NODE_MATCHERS_H_
730