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/codegen/external-reference.h"
12 #include "src/common/globals.h"
13 #include "src/compiler/node.h"
14 #include "src/compiler/operator.h"
15 #include "src/numbers/double.h"
16 #include "src/objects/heap-object.h"
17
18 namespace v8 {
19 namespace internal {
20 namespace compiler {
21
22 class JSHeapBroker;
23
24 // A pattern matcher for nodes.
25 struct NodeMatcher {
NodeMatcherNodeMatcher26 explicit NodeMatcher(Node* node) : node_(node) {}
27
nodeNodeMatcher28 Node* node() const { return node_; }
opNodeMatcher29 const Operator* op() const { return node()->op(); }
opcodeNodeMatcher30 IrOpcode::Value opcode() const { return node()->opcode(); }
31
HasPropertyNodeMatcher32 bool HasProperty(Operator::Property property) const {
33 return op()->HasProperty(property);
34 }
InputAtNodeMatcher35 Node* InputAt(int index) const { return node()->InputAt(index); }
36
EqualsNodeMatcher37 bool Equals(const Node* node) const { return node_ == node; }
38
39 bool IsComparison() const;
40
41 #define DEFINE_IS_OPCODE(Opcode) \
42 bool Is##Opcode() const { return opcode() == IrOpcode::k##Opcode; }
43 ALL_OP_LIST(DEFINE_IS_OPCODE)
44 #undef DEFINE_IS_OPCODE
45
46 private:
47 Node* node_;
48 };
49
50
51 // A pattern matcher for abitrary value constants.
52 template <typename T, IrOpcode::Value kOpcode>
53 struct ValueMatcher : public NodeMatcher {
54 using ValueType = T;
55
ValueMatcherValueMatcher56 explicit ValueMatcher(Node* node) : NodeMatcher(node) {
57 static_assert(kOpcode != IrOpcode::kFoldConstant, "unsupported opcode");
58 if (node->opcode() == IrOpcode::kFoldConstant) {
59 node = node->InputAt(1);
60 }
61 DCHECK_NE(node->opcode(), IrOpcode::kFoldConstant);
62 has_value_ = opcode() == kOpcode;
63 if (has_value_) {
64 value_ = OpParameter<T>(node->op());
65 }
66 }
67
HasValueValueMatcher68 bool HasValue() const { return has_value_; }
ValueValueMatcher69 const T& Value() const {
70 DCHECK(HasValue());
71 return value_;
72 }
73
74 private:
75 T value_;
76 bool has_value_;
77 };
78
79
80 template <>
ValueMatcher(Node * node)81 inline ValueMatcher<uint32_t, IrOpcode::kInt32Constant>::ValueMatcher(
82 Node* node)
83 : NodeMatcher(node),
84 value_(),
85 has_value_(opcode() == IrOpcode::kInt32Constant) {
86 if (has_value_) {
87 value_ = static_cast<uint32_t>(OpParameter<int32_t>(node->op()));
88 }
89 }
90
91
92 template <>
ValueMatcher(Node * node)93 inline ValueMatcher<int64_t, IrOpcode::kInt64Constant>::ValueMatcher(Node* node)
94 : NodeMatcher(node), value_(), has_value_(false) {
95 if (opcode() == IrOpcode::kInt32Constant) {
96 value_ = OpParameter<int32_t>(node->op());
97 has_value_ = true;
98 } else if (opcode() == IrOpcode::kInt64Constant) {
99 value_ = OpParameter<int64_t>(node->op());
100 has_value_ = true;
101 }
102 }
103
104
105 template <>
ValueMatcher(Node * node)106 inline ValueMatcher<uint64_t, IrOpcode::kInt64Constant>::ValueMatcher(
107 Node* node)
108 : NodeMatcher(node), value_(), has_value_(false) {
109 if (opcode() == IrOpcode::kInt32Constant) {
110 value_ = static_cast<uint32_t>(OpParameter<int32_t>(node->op()));
111 has_value_ = true;
112 } else if (opcode() == IrOpcode::kInt64Constant) {
113 value_ = static_cast<uint64_t>(OpParameter<int64_t>(node->op()));
114 has_value_ = true;
115 }
116 }
117
118 template <>
ValueMatcher(Node * node)119 inline ValueMatcher<double, IrOpcode::kNumberConstant>::ValueMatcher(Node* node)
120 : NodeMatcher(node), value_(), has_value_(false) {
121 if (node->opcode() == IrOpcode::kNumberConstant) {
122 value_ = OpParameter<double>(node->op());
123 has_value_ = true;
124 } else if (node->opcode() == IrOpcode::kFoldConstant) {
125 node = node->InputAt(1);
126 DCHECK_NE(node->opcode(), IrOpcode::kFoldConstant);
127 }
128 }
129
130 template <>
ValueMatcher(Node * node)131 inline ValueMatcher<Handle<HeapObject>, IrOpcode::kHeapConstant>::ValueMatcher(
132 Node* node)
133 : NodeMatcher(node), value_(), has_value_(false) {
134 if (node->opcode() == IrOpcode::kHeapConstant) {
135 value_ = OpParameter<Handle<HeapObject>>(node->op());
136 has_value_ = true;
137 } else if (node->opcode() == IrOpcode::kFoldConstant) {
138 node = node->InputAt(1);
139 DCHECK_NE(node->opcode(), IrOpcode::kFoldConstant);
140 }
141 }
142
143 // A pattern matcher for integer constants.
144 template <typename T, IrOpcode::Value kOpcode>
145 struct IntMatcher final : public ValueMatcher<T, kOpcode> {
IntMatcherfinal146 explicit IntMatcher(Node* node) : ValueMatcher<T, kOpcode>(node) {}
147
Isfinal148 bool Is(const T& value) const {
149 return this->HasValue() && this->Value() == value;
150 }
IsInRangefinal151 bool IsInRange(const T& low, const T& high) const {
152 return this->HasValue() && low <= this->Value() && this->Value() <= high;
153 }
IsMultipleOffinal154 bool IsMultipleOf(T n) const {
155 return this->HasValue() && (this->Value() % n) == 0;
156 }
IsPowerOf2final157 bool IsPowerOf2() const {
158 return this->HasValue() && this->Value() > 0 &&
159 (this->Value() & (this->Value() - 1)) == 0;
160 }
IsNegativePowerOf2final161 bool IsNegativePowerOf2() const {
162 return this->HasValue() && this->Value() < 0 &&
163 ((this->Value() == kMinInt) ||
164 (-this->Value() & (-this->Value() - 1)) == 0);
165 }
IsNegativefinal166 bool IsNegative() const { return this->HasValue() && this->Value() < 0; }
167 };
168
169 using Int32Matcher = IntMatcher<int32_t, IrOpcode::kInt32Constant>;
170 using Uint32Matcher = IntMatcher<uint32_t, IrOpcode::kInt32Constant>;
171 using Int64Matcher = IntMatcher<int64_t, IrOpcode::kInt64Constant>;
172 using Uint64Matcher = IntMatcher<uint64_t, IrOpcode::kInt64Constant>;
173 #if V8_HOST_ARCH_32_BIT
174 using IntPtrMatcher = Int32Matcher;
175 using UintPtrMatcher = Uint32Matcher;
176 #else
177 using IntPtrMatcher = Int64Matcher;
178 using UintPtrMatcher = Uint64Matcher;
179 #endif
180
181
182 // A pattern matcher for floating point constants.
183 template <typename T, IrOpcode::Value kOpcode>
184 struct FloatMatcher final : public ValueMatcher<T, kOpcode> {
FloatMatcherfinal185 explicit FloatMatcher(Node* node) : ValueMatcher<T, kOpcode>(node) {}
186
Isfinal187 bool Is(const T& value) const {
188 return this->HasValue() && this->Value() == value;
189 }
IsInRangefinal190 bool IsInRange(const T& low, const T& high) const {
191 return this->HasValue() && low <= this->Value() && this->Value() <= high;
192 }
IsMinusZerofinal193 bool IsMinusZero() const {
194 return this->Is(0.0) && std::signbit(this->Value());
195 }
IsNegativefinal196 bool IsNegative() const { return this->HasValue() && this->Value() < 0.0; }
IsNaNfinal197 bool IsNaN() const { return this->HasValue() && std::isnan(this->Value()); }
IsZerofinal198 bool IsZero() const { return this->Is(0.0) && !std::signbit(this->Value()); }
IsNormalfinal199 bool IsNormal() const {
200 return this->HasValue() && std::isnormal(this->Value());
201 }
IsIntegerfinal202 bool IsInteger() const {
203 return this->HasValue() && std::nearbyint(this->Value()) == this->Value();
204 }
IsPositiveOrNegativePowerOf2final205 bool IsPositiveOrNegativePowerOf2() const {
206 if (!this->HasValue() || (this->Value() == 0.0)) {
207 return false;
208 }
209 Double value = Double(this->Value());
210 return !value.IsInfinite() && base::bits::IsPowerOfTwo(value.Significand());
211 }
212 };
213
214 using Float32Matcher = FloatMatcher<float, IrOpcode::kFloat32Constant>;
215 using Float64Matcher = FloatMatcher<double, IrOpcode::kFloat64Constant>;
216 using NumberMatcher = FloatMatcher<double, IrOpcode::kNumberConstant>;
217
218 // A pattern matcher for heap object constants.
219 template <IrOpcode::Value kHeapConstantOpcode>
220 struct HeapObjectMatcherImpl final
221 : public ValueMatcher<Handle<HeapObject>, kHeapConstantOpcode> {
HeapObjectMatcherImplfinal222 explicit HeapObjectMatcherImpl(Node* node)
223 : ValueMatcher<Handle<HeapObject>, kHeapConstantOpcode>(node) {}
224
Isfinal225 bool Is(Handle<HeapObject> const& value) const {
226 return this->HasValue() && this->Value().address() == value.address();
227 }
228
Reffinal229 HeapObjectRef Ref(JSHeapBroker* broker) const {
230 return HeapObjectRef(broker, this->Value());
231 }
232 };
233
234 using HeapObjectMatcher = HeapObjectMatcherImpl<IrOpcode::kHeapConstant>;
235 using CompressedHeapObjectMatcher =
236 HeapObjectMatcherImpl<IrOpcode::kCompressedHeapConstant>;
237
238 // A pattern matcher for external reference constants.
239 struct ExternalReferenceMatcher final
240 : public ValueMatcher<ExternalReference, IrOpcode::kExternalConstant> {
ExternalReferenceMatcherfinal241 explicit ExternalReferenceMatcher(Node* node)
242 : ValueMatcher<ExternalReference, IrOpcode::kExternalConstant>(node) {}
Isfinal243 bool Is(const ExternalReference& value) const {
244 return this->HasValue() && this->Value() == value;
245 }
246 };
247
248
249 // For shorter pattern matching code, this struct matches the inputs to
250 // machine-level load operations.
251 template <typename Object>
252 struct LoadMatcher : public NodeMatcher {
LoadMatcherLoadMatcher253 explicit LoadMatcher(Node* node)
254 : NodeMatcher(node), object_(InputAt(0)), index_(InputAt(1)) {}
255
256 using ObjectMatcher = Object;
257
objectLoadMatcher258 Object const& object() const { return object_; }
indexLoadMatcher259 IntPtrMatcher const& index() const { return index_; }
260
261 private:
262 Object const object_;
263 IntPtrMatcher const index_;
264 };
265
266
267 // For shorter pattern matching code, this struct matches both the left and
268 // right hand sides of a binary operation and can put constants on the right
269 // if they appear on the left hand side of a commutative operation.
270 template <typename Left, typename Right>
271 struct BinopMatcher : public NodeMatcher {
BinopMatcherBinopMatcher272 explicit BinopMatcher(Node* node)
273 : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) {
274 if (HasProperty(Operator::kCommutative)) PutConstantOnRight();
275 }
BinopMatcherBinopMatcher276 BinopMatcher(Node* node, bool allow_input_swap)
277 : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) {
278 if (allow_input_swap) PutConstantOnRight();
279 }
280
281 using LeftMatcher = Left;
282 using RightMatcher = Right;
283
leftBinopMatcher284 const Left& left() const { return left_; }
rightBinopMatcher285 const Right& right() const { return right_; }
286
IsFoldableBinopMatcher287 bool IsFoldable() const { return left().HasValue() && right().HasValue(); }
LeftEqualsRightBinopMatcher288 bool LeftEqualsRight() const { return left().node() == right().node(); }
289
OwnsInputBinopMatcher290 bool OwnsInput(Node* input) {
291 for (Node* use : input->uses()) {
292 if (use != node()) {
293 return false;
294 }
295 }
296 return true;
297 }
298
299 protected:
SwapInputsBinopMatcher300 void SwapInputs() {
301 std::swap(left_, right_);
302 // TODO(tebbi): This modification should notify the reducers using
303 // BinopMatcher. Alternatively, all reducers (especially value numbering)
304 // could ignore the ordering for commutative binops.
305 node()->ReplaceInput(0, left().node());
306 node()->ReplaceInput(1, right().node());
307 }
308
309 private:
PutConstantOnRightBinopMatcher310 void PutConstantOnRight() {
311 if (left().HasValue() && !right().HasValue()) {
312 SwapInputs();
313 }
314 }
315
316 Left left_;
317 Right right_;
318 };
319
320 using Int32BinopMatcher = BinopMatcher<Int32Matcher, Int32Matcher>;
321 using Uint32BinopMatcher = BinopMatcher<Uint32Matcher, Uint32Matcher>;
322 using Int64BinopMatcher = BinopMatcher<Int64Matcher, Int64Matcher>;
323 using Uint64BinopMatcher = BinopMatcher<Uint64Matcher, Uint64Matcher>;
324 using IntPtrBinopMatcher = BinopMatcher<IntPtrMatcher, IntPtrMatcher>;
325 using UintPtrBinopMatcher = BinopMatcher<UintPtrMatcher, UintPtrMatcher>;
326 using Float32BinopMatcher = BinopMatcher<Float32Matcher, Float32Matcher>;
327 using Float64BinopMatcher = BinopMatcher<Float64Matcher, Float64Matcher>;
328 using NumberBinopMatcher = BinopMatcher<NumberMatcher, NumberMatcher>;
329 using HeapObjectBinopMatcher =
330 BinopMatcher<HeapObjectMatcher, HeapObjectMatcher>;
331 using CompressedHeapObjectBinopMatcher =
332 BinopMatcher<CompressedHeapObjectMatcher, CompressedHeapObjectMatcher>;
333
334 template <class BinopMatcher, IrOpcode::Value kMulOpcode,
335 IrOpcode::Value kShiftOpcode>
336 struct ScaleMatcher {
337 explicit ScaleMatcher(Node* node, bool allow_power_of_two_plus_one = false)
338 : scale_(-1), power_of_two_plus_one_(false) {
339 if (node->InputCount() < 2) return;
340 BinopMatcher m(node);
341 if (node->opcode() == kShiftOpcode) {
342 if (m.right().HasValue()) {
343 typename BinopMatcher::RightMatcher::ValueType value =
344 m.right().Value();
345 if (value >= 0 && value <= 3) {
346 scale_ = static_cast<int>(value);
347 }
348 }
349 } else if (node->opcode() == kMulOpcode) {
350 if (m.right().HasValue()) {
351 typename BinopMatcher::RightMatcher::ValueType value =
352 m.right().Value();
353 if (value == 1) {
354 scale_ = 0;
355 } else if (value == 2) {
356 scale_ = 1;
357 } else if (value == 4) {
358 scale_ = 2;
359 } else if (value == 8) {
360 scale_ = 3;
361 } else if (allow_power_of_two_plus_one) {
362 if (value == 3) {
363 scale_ = 1;
364 power_of_two_plus_one_ = true;
365 } else if (value == 5) {
366 scale_ = 2;
367 power_of_two_plus_one_ = true;
368 } else if (value == 9) {
369 scale_ = 3;
370 power_of_two_plus_one_ = true;
371 }
372 }
373 }
374 }
375 }
376
matchesScaleMatcher377 bool matches() const { return scale_ != -1; }
scaleScaleMatcher378 int scale() const { return scale_; }
power_of_two_plus_oneScaleMatcher379 bool power_of_two_plus_one() const { return power_of_two_plus_one_; }
380
381 private:
382 int scale_;
383 bool power_of_two_plus_one_;
384 };
385
386 using Int32ScaleMatcher =
387 ScaleMatcher<Int32BinopMatcher, IrOpcode::kInt32Mul, IrOpcode::kWord32Shl>;
388 using Int64ScaleMatcher =
389 ScaleMatcher<Int64BinopMatcher, IrOpcode::kInt64Mul, IrOpcode::kWord64Shl>;
390
391 template <class BinopMatcher, IrOpcode::Value AddOpcode,
392 IrOpcode::Value SubOpcode, IrOpcode::Value kMulOpcode,
393 IrOpcode::Value kShiftOpcode>
394 struct AddMatcher : public BinopMatcher {
395 static const IrOpcode::Value kAddOpcode = AddOpcode;
396 static const IrOpcode::Value kSubOpcode = SubOpcode;
397 using Matcher = ScaleMatcher<BinopMatcher, kMulOpcode, kShiftOpcode>;
398
AddMatcherAddMatcher399 AddMatcher(Node* node, bool allow_input_swap)
400 : BinopMatcher(node, allow_input_swap),
401 scale_(-1),
402 power_of_two_plus_one_(false) {
403 Initialize(node, allow_input_swap);
404 }
AddMatcherAddMatcher405 explicit AddMatcher(Node* node)
406 : BinopMatcher(node, node->op()->HasProperty(Operator::kCommutative)),
407 scale_(-1),
408 power_of_two_plus_one_(false) {
409 Initialize(node, node->op()->HasProperty(Operator::kCommutative));
410 }
411
HasIndexInputAddMatcher412 bool HasIndexInput() const { return scale_ != -1; }
IndexInputAddMatcher413 Node* IndexInput() const {
414 DCHECK(HasIndexInput());
415 return this->left().node()->InputAt(0);
416 }
scaleAddMatcher417 int scale() const {
418 DCHECK(HasIndexInput());
419 return scale_;
420 }
power_of_two_plus_oneAddMatcher421 bool power_of_two_plus_one() const { return power_of_two_plus_one_; }
422
423 private:
InitializeAddMatcher424 void Initialize(Node* node, bool allow_input_swap) {
425 Matcher left_matcher(this->left().node(), true);
426 if (left_matcher.matches()) {
427 scale_ = left_matcher.scale();
428 power_of_two_plus_one_ = left_matcher.power_of_two_plus_one();
429 return;
430 }
431
432 if (!allow_input_swap) {
433 return;
434 }
435
436 Matcher right_matcher(this->right().node(), true);
437 if (right_matcher.matches()) {
438 scale_ = right_matcher.scale();
439 power_of_two_plus_one_ = right_matcher.power_of_two_plus_one();
440 this->SwapInputs();
441 return;
442 }
443
444 if ((this->left().opcode() != kSubOpcode &&
445 this->left().opcode() != kAddOpcode) &&
446 (this->right().opcode() == kAddOpcode ||
447 this->right().opcode() == kSubOpcode)) {
448 this->SwapInputs();
449 }
450 }
451
452 int scale_;
453 bool power_of_two_plus_one_;
454 };
455
456 using Int32AddMatcher =
457 AddMatcher<Int32BinopMatcher, IrOpcode::kInt32Add, IrOpcode::kInt32Sub,
458 IrOpcode::kInt32Mul, IrOpcode::kWord32Shl>;
459 using Int64AddMatcher =
460 AddMatcher<Int64BinopMatcher, IrOpcode::kInt64Add, IrOpcode::kInt64Sub,
461 IrOpcode::kInt64Mul, IrOpcode::kWord64Shl>;
462
463 enum DisplacementMode { kPositiveDisplacement, kNegativeDisplacement };
464
465 enum class AddressOption : uint8_t {
466 kAllowNone = 0u,
467 kAllowInputSwap = 1u << 0,
468 kAllowScale = 1u << 1,
469 kAllowAll = kAllowInputSwap | kAllowScale
470 };
471
472 using AddressOptions = base::Flags<AddressOption, uint8_t>;
473 DEFINE_OPERATORS_FOR_FLAGS(AddressOptions)
474
475 template <class AddMatcher>
476 struct BaseWithIndexAndDisplacementMatcher {
BaseWithIndexAndDisplacementMatcherBaseWithIndexAndDisplacementMatcher477 BaseWithIndexAndDisplacementMatcher(Node* node, AddressOptions options)
478 : matches_(false),
479 index_(nullptr),
480 scale_(0),
481 base_(nullptr),
482 displacement_(nullptr),
483 displacement_mode_(kPositiveDisplacement) {
484 Initialize(node, options);
485 }
486
BaseWithIndexAndDisplacementMatcherBaseWithIndexAndDisplacementMatcher487 explicit BaseWithIndexAndDisplacementMatcher(Node* node)
488 : matches_(false),
489 index_(nullptr),
490 scale_(0),
491 base_(nullptr),
492 displacement_(nullptr),
493 displacement_mode_(kPositiveDisplacement) {
494 Initialize(node, AddressOption::kAllowScale |
495 (node->op()->HasProperty(Operator::kCommutative)
496 ? AddressOption::kAllowInputSwap
497 : AddressOption::kAllowNone));
498 }
499
matchesBaseWithIndexAndDisplacementMatcher500 bool matches() const { return matches_; }
indexBaseWithIndexAndDisplacementMatcher501 Node* index() const { return index_; }
scaleBaseWithIndexAndDisplacementMatcher502 int scale() const { return scale_; }
baseBaseWithIndexAndDisplacementMatcher503 Node* base() const { return base_; }
displacementBaseWithIndexAndDisplacementMatcher504 Node* displacement() const { return displacement_; }
displacement_modeBaseWithIndexAndDisplacementMatcher505 DisplacementMode displacement_mode() const { return displacement_mode_; }
506
507 private:
508 bool matches_;
509 Node* index_;
510 int scale_;
511 Node* base_;
512 Node* displacement_;
513 DisplacementMode displacement_mode_;
514
InitializeBaseWithIndexAndDisplacementMatcher515 void Initialize(Node* node, AddressOptions options) {
516 // The BaseWithIndexAndDisplacementMatcher canonicalizes the order of
517 // displacements and scale factors that are used as inputs, so instead of
518 // enumerating all possible patterns by brute force, checking for node
519 // clusters using the following templates in the following order suffices to
520 // find all of the interesting cases (S = index * scale, B = base input, D =
521 // displacement input):
522 // (S + (B + D))
523 // (S + (B + B))
524 // (S + D)
525 // (S + B)
526 // ((S + D) + B)
527 // ((S + B) + D)
528 // ((B + D) + B)
529 // ((B + B) + D)
530 // (B + D)
531 // (B + B)
532 if (node->InputCount() < 2) return;
533 AddMatcher m(node, options & AddressOption::kAllowInputSwap);
534 Node* left = m.left().node();
535 Node* right = m.right().node();
536 Node* displacement = nullptr;
537 Node* base = nullptr;
538 Node* index = nullptr;
539 Node* scale_expression = nullptr;
540 bool power_of_two_plus_one = false;
541 DisplacementMode displacement_mode = kPositiveDisplacement;
542 int scale = 0;
543 if (m.HasIndexInput() && OwnedByAddressingOperand(left)) {
544 index = m.IndexInput();
545 scale = m.scale();
546 scale_expression = left;
547 power_of_two_plus_one = m.power_of_two_plus_one();
548 bool match_found = false;
549 if (right->opcode() == AddMatcher::kSubOpcode &&
550 OwnedByAddressingOperand(right)) {
551 AddMatcher right_matcher(right);
552 if (right_matcher.right().HasValue()) {
553 // (S + (B - D))
554 base = right_matcher.left().node();
555 displacement = right_matcher.right().node();
556 displacement_mode = kNegativeDisplacement;
557 match_found = true;
558 }
559 }
560 if (!match_found) {
561 if (right->opcode() == AddMatcher::kAddOpcode &&
562 OwnedByAddressingOperand(right)) {
563 AddMatcher right_matcher(right);
564 if (right_matcher.right().HasValue()) {
565 // (S + (B + D))
566 base = right_matcher.left().node();
567 displacement = right_matcher.right().node();
568 } else {
569 // (S + (B + B))
570 base = right;
571 }
572 } else if (m.right().HasValue()) {
573 // (S + D)
574 displacement = right;
575 } else {
576 // (S + B)
577 base = right;
578 }
579 }
580 } else {
581 bool match_found = false;
582 if (left->opcode() == AddMatcher::kSubOpcode &&
583 OwnedByAddressingOperand(left)) {
584 AddMatcher left_matcher(left);
585 Node* left_left = left_matcher.left().node();
586 Node* left_right = left_matcher.right().node();
587 if (left_matcher.right().HasValue()) {
588 if (left_matcher.HasIndexInput() && left_left->OwnedBy(left)) {
589 // ((S - D) + B)
590 index = left_matcher.IndexInput();
591 scale = left_matcher.scale();
592 scale_expression = left_left;
593 power_of_two_plus_one = left_matcher.power_of_two_plus_one();
594 displacement = left_right;
595 displacement_mode = kNegativeDisplacement;
596 base = right;
597 } else {
598 // ((B - D) + B)
599 index = left_left;
600 displacement = left_right;
601 displacement_mode = kNegativeDisplacement;
602 base = right;
603 }
604 match_found = true;
605 }
606 }
607 if (!match_found) {
608 if (left->opcode() == AddMatcher::kAddOpcode &&
609 OwnedByAddressingOperand(left)) {
610 AddMatcher left_matcher(left);
611 Node* left_left = left_matcher.left().node();
612 Node* left_right = left_matcher.right().node();
613 if (left_matcher.HasIndexInput() && left_left->OwnedBy(left)) {
614 if (left_matcher.right().HasValue()) {
615 // ((S + D) + B)
616 index = left_matcher.IndexInput();
617 scale = left_matcher.scale();
618 scale_expression = left_left;
619 power_of_two_plus_one = left_matcher.power_of_two_plus_one();
620 displacement = left_right;
621 base = right;
622 } else if (m.right().HasValue()) {
623 if (left->OwnedBy(node)) {
624 // ((S + B) + D)
625 index = left_matcher.IndexInput();
626 scale = left_matcher.scale();
627 scale_expression = left_left;
628 power_of_two_plus_one = left_matcher.power_of_two_plus_one();
629 base = left_right;
630 displacement = right;
631 } else {
632 // (B + D)
633 base = left;
634 displacement = right;
635 }
636 } else {
637 // (B + B)
638 index = left;
639 base = right;
640 }
641 } else {
642 if (left_matcher.right().HasValue()) {
643 // ((B + D) + B)
644 index = left_left;
645 displacement = left_right;
646 base = right;
647 } else if (m.right().HasValue()) {
648 if (left->OwnedBy(node)) {
649 // ((B + B) + D)
650 index = left_left;
651 base = left_right;
652 displacement = right;
653 } else {
654 // (B + D)
655 base = left;
656 displacement = right;
657 }
658 } else {
659 // (B + B)
660 index = left;
661 base = right;
662 }
663 }
664 } else {
665 if (m.right().HasValue()) {
666 // (B + D)
667 base = left;
668 displacement = right;
669 } else {
670 // (B + B)
671 base = left;
672 index = right;
673 }
674 }
675 }
676 }
677 int64_t value = 0;
678 if (displacement != nullptr) {
679 switch (displacement->opcode()) {
680 case IrOpcode::kInt32Constant: {
681 value = OpParameter<int32_t>(displacement->op());
682 break;
683 }
684 case IrOpcode::kInt64Constant: {
685 value = OpParameter<int64_t>(displacement->op());
686 break;
687 }
688 default:
689 UNREACHABLE();
690 break;
691 }
692 if (value == 0) {
693 displacement = nullptr;
694 }
695 }
696 if (power_of_two_plus_one) {
697 if (base != nullptr) {
698 // If the scale requires explicitly using the index as the base, but a
699 // base is already part of the match, then the (1 << N + 1) scale factor
700 // can't be folded into the match and the entire index * scale
701 // calculation must be computed separately.
702 index = scale_expression;
703 scale = 0;
704 } else {
705 base = index;
706 }
707 }
708 if (!(options & AddressOption::kAllowScale) && scale != 0) {
709 index = scale_expression;
710 scale = 0;
711 }
712 base_ = base;
713 displacement_ = displacement;
714 displacement_mode_ = displacement_mode;
715 index_ = index;
716 scale_ = scale;
717 matches_ = true;
718 }
719
OwnedByAddressingOperandBaseWithIndexAndDisplacementMatcher720 static bool OwnedByAddressingOperand(Node* node) {
721 for (auto use : node->use_edges()) {
722 Node* from = use.from();
723 switch (from->opcode()) {
724 case IrOpcode::kLoad:
725 case IrOpcode::kPoisonedLoad:
726 case IrOpcode::kProtectedLoad:
727 case IrOpcode::kInt32Add:
728 case IrOpcode::kInt64Add:
729 // Skip addressing uses.
730 break;
731 case IrOpcode::kStore:
732 case IrOpcode::kProtectedStore:
733 // If the stored value is this node, it is not an addressing use.
734 if (from->InputAt(2) == node) return false;
735 // Otherwise it is used as an address and skipped.
736 break;
737 default:
738 // Non-addressing use found.
739 return false;
740 }
741 }
742 return true;
743 }
744 };
745
746 using BaseWithIndexAndDisplacement32Matcher =
747 BaseWithIndexAndDisplacementMatcher<Int32AddMatcher>;
748 using BaseWithIndexAndDisplacement64Matcher =
749 BaseWithIndexAndDisplacementMatcher<Int64AddMatcher>;
750
751 struct V8_EXPORT_PRIVATE BranchMatcher : public NON_EXPORTED_BASE(NodeMatcher) {
752 explicit BranchMatcher(Node* branch);
753
MatchedBranchMatcher754 bool Matched() const { return if_true_ && if_false_; }
755
BranchBranchMatcher756 Node* Branch() const { return node(); }
IfTrueBranchMatcher757 Node* IfTrue() const { return if_true_; }
IfFalseBranchMatcher758 Node* IfFalse() const { return if_false_; }
759
760 private:
761 Node* if_true_;
762 Node* if_false_;
763 };
764
765 struct V8_EXPORT_PRIVATE DiamondMatcher
766 : public NON_EXPORTED_BASE(NodeMatcher) {
767 explicit DiamondMatcher(Node* merge);
768
MatchedDiamondMatcher769 bool Matched() const { return branch_; }
IfProjectionsAreOwnedDiamondMatcher770 bool IfProjectionsAreOwned() const {
771 return if_true_->OwnedBy(node()) && if_false_->OwnedBy(node());
772 }
773
BranchDiamondMatcher774 Node* Branch() const { return branch_; }
IfTrueDiamondMatcher775 Node* IfTrue() const { return if_true_; }
IfFalseDiamondMatcher776 Node* IfFalse() const { return if_false_; }
MergeDiamondMatcher777 Node* Merge() const { return node(); }
778
TrueInputOfDiamondMatcher779 Node* TrueInputOf(Node* phi) const {
780 DCHECK(IrOpcode::IsPhiOpcode(phi->opcode()));
781 DCHECK_EQ(3, phi->InputCount());
782 DCHECK_EQ(Merge(), phi->InputAt(2));
783 return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 0 : 1);
784 }
785
FalseInputOfDiamondMatcher786 Node* FalseInputOf(Node* phi) const {
787 DCHECK(IrOpcode::IsPhiOpcode(phi->opcode()));
788 DCHECK_EQ(3, phi->InputCount());
789 DCHECK_EQ(Merge(), phi->InputAt(2));
790 return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 1 : 0);
791 }
792
793 private:
794 Node* branch_;
795 Node* if_true_;
796 Node* if_false_;
797 };
798
799 } // namespace compiler
800 } // namespace internal
801 } // namespace v8
802
803 #endif // V8_COMPILER_NODE_MATCHERS_H_
804