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/compiler/node.h"
13 #include "src/compiler/operator.h"
14
15 namespace v8 {
16 namespace internal {
17 namespace compiler {
18
19 // A pattern matcher for nodes.
20 struct NodeMatcher {
NodeMatcherNodeMatcher21 explicit NodeMatcher(Node* node) : node_(node) {}
22
nodeNodeMatcher23 Node* node() const { return node_; }
opNodeMatcher24 const Operator* op() const { return node()->op(); }
opcodeNodeMatcher25 IrOpcode::Value opcode() const { return node()->opcode(); }
26
HasPropertyNodeMatcher27 bool HasProperty(Operator::Property property) const {
28 return op()->HasProperty(property);
29 }
InputAtNodeMatcher30 Node* InputAt(int index) const { return node()->InputAt(index); }
31
EqualsNodeMatcher32 bool Equals(const Node* node) const { return node_ == node; }
33
34 bool IsComparison() const;
35
36 #define DEFINE_IS_OPCODE(Opcode) \
37 bool Is##Opcode() const { return opcode() == IrOpcode::k##Opcode; }
38 ALL_OP_LIST(DEFINE_IS_OPCODE)
39 #undef DEFINE_IS_OPCODE
40
41 private:
42 Node* node_;
43 };
44
45
46 // A pattern matcher for abitrary value constants.
47 template <typename T, IrOpcode::Value kOpcode>
48 struct ValueMatcher : public NodeMatcher {
49 typedef T ValueType;
50
ValueMatcherValueMatcher51 explicit ValueMatcher(Node* node)
52 : NodeMatcher(node), value_(), has_value_(opcode() == kOpcode) {
53 if (has_value_) {
54 value_ = OpParameter<T>(node);
55 }
56 }
57
HasValueValueMatcher58 bool HasValue() const { return has_value_; }
ValueValueMatcher59 const T& Value() const {
60 DCHECK(HasValue());
61 return value_;
62 }
63
64 private:
65 T value_;
66 bool has_value_;
67 };
68
69
70 template <>
ValueMatcher(Node * node)71 inline ValueMatcher<uint32_t, IrOpcode::kInt32Constant>::ValueMatcher(
72 Node* node)
73 : NodeMatcher(node),
74 value_(),
75 has_value_(opcode() == IrOpcode::kInt32Constant) {
76 if (has_value_) {
77 value_ = static_cast<uint32_t>(OpParameter<int32_t>(node));
78 }
79 }
80
81
82 template <>
ValueMatcher(Node * node)83 inline ValueMatcher<int64_t, IrOpcode::kInt64Constant>::ValueMatcher(Node* node)
84 : NodeMatcher(node), value_(), has_value_(false) {
85 if (opcode() == IrOpcode::kInt32Constant) {
86 value_ = OpParameter<int32_t>(node);
87 has_value_ = true;
88 } else if (opcode() == IrOpcode::kInt64Constant) {
89 value_ = OpParameter<int64_t>(node);
90 has_value_ = true;
91 }
92 }
93
94
95 template <>
ValueMatcher(Node * node)96 inline ValueMatcher<uint64_t, IrOpcode::kInt64Constant>::ValueMatcher(
97 Node* node)
98 : NodeMatcher(node), value_(), has_value_(false) {
99 if (opcode() == IrOpcode::kInt32Constant) {
100 value_ = static_cast<uint32_t>(OpParameter<int32_t>(node));
101 has_value_ = true;
102 } else if (opcode() == IrOpcode::kInt64Constant) {
103 value_ = static_cast<uint64_t>(OpParameter<int64_t>(node));
104 has_value_ = true;
105 }
106 }
107
108
109 // A pattern matcher for integer constants.
110 template <typename T, IrOpcode::Value kOpcode>
111 struct IntMatcher final : public ValueMatcher<T, kOpcode> {
IntMatcherfinal112 explicit IntMatcher(Node* node) : ValueMatcher<T, kOpcode>(node) {}
113
Isfinal114 bool Is(const T& value) const {
115 return this->HasValue() && this->Value() == value;
116 }
IsInRangefinal117 bool IsInRange(const T& low, const T& high) const {
118 return this->HasValue() && low <= this->Value() && this->Value() <= high;
119 }
IsMultipleOffinal120 bool IsMultipleOf(T n) const {
121 return this->HasValue() && (this->Value() % n) == 0;
122 }
IsPowerOf2final123 bool IsPowerOf2() const {
124 return this->HasValue() && this->Value() > 0 &&
125 (this->Value() & (this->Value() - 1)) == 0;
126 }
IsNegativePowerOf2final127 bool IsNegativePowerOf2() const {
128 return this->HasValue() && this->Value() < 0 &&
129 (-this->Value() & (-this->Value() - 1)) == 0;
130 }
131 };
132
133 typedef IntMatcher<int32_t, IrOpcode::kInt32Constant> Int32Matcher;
134 typedef IntMatcher<uint32_t, IrOpcode::kInt32Constant> Uint32Matcher;
135 typedef IntMatcher<int64_t, IrOpcode::kInt64Constant> Int64Matcher;
136 typedef IntMatcher<uint64_t, IrOpcode::kInt64Constant> Uint64Matcher;
137 #if V8_HOST_ARCH_32_BIT
138 typedef Int32Matcher IntPtrMatcher;
139 typedef Uint32Matcher UintPtrMatcher;
140 #else
141 typedef Int64Matcher IntPtrMatcher;
142 typedef Uint64Matcher UintPtrMatcher;
143 #endif
144
145
146 // A pattern matcher for floating point constants.
147 template <typename T, IrOpcode::Value kOpcode>
148 struct FloatMatcher final : public ValueMatcher<T, kOpcode> {
FloatMatcherfinal149 explicit FloatMatcher(Node* node) : ValueMatcher<T, kOpcode>(node) {}
150
Isfinal151 bool Is(const T& value) const {
152 return this->HasValue() && this->Value() == value;
153 }
IsInRangefinal154 bool IsInRange(const T& low, const T& high) const {
155 return this->HasValue() && low <= this->Value() && this->Value() <= high;
156 }
IsMinusZerofinal157 bool IsMinusZero() const {
158 return this->Is(0.0) && std::signbit(this->Value());
159 }
IsNaNfinal160 bool IsNaN() const { return this->HasValue() && std::isnan(this->Value()); }
IsZerofinal161 bool IsZero() const { return this->Is(0.0) && !std::signbit(this->Value()); }
162 };
163
164 typedef FloatMatcher<float, IrOpcode::kFloat32Constant> Float32Matcher;
165 typedef FloatMatcher<double, IrOpcode::kFloat64Constant> Float64Matcher;
166 typedef FloatMatcher<double, IrOpcode::kNumberConstant> NumberMatcher;
167
168
169 // A pattern matcher for heap object constants.
170 struct HeapObjectMatcher final
171 : public ValueMatcher<Handle<HeapObject>, IrOpcode::kHeapConstant> {
HeapObjectMatcherfinal172 explicit HeapObjectMatcher(Node* node)
173 : ValueMatcher<Handle<HeapObject>, IrOpcode::kHeapConstant>(node) {}
174 };
175
176
177 // A pattern matcher for external reference constants.
178 struct ExternalReferenceMatcher final
179 : public ValueMatcher<ExternalReference, IrOpcode::kExternalConstant> {
ExternalReferenceMatcherfinal180 explicit ExternalReferenceMatcher(Node* node)
181 : ValueMatcher<ExternalReference, IrOpcode::kExternalConstant>(node) {}
Isfinal182 bool Is(const ExternalReference& value) const {
183 return this->HasValue() && this->Value() == value;
184 }
185 };
186
187
188 // For shorter pattern matching code, this struct matches the inputs to
189 // machine-level load operations.
190 template <typename Object>
191 struct LoadMatcher : public NodeMatcher {
LoadMatcherLoadMatcher192 explicit LoadMatcher(Node* node)
193 : NodeMatcher(node), object_(InputAt(0)), index_(InputAt(1)) {}
194
195 typedef Object ObjectMatcher;
196
objectLoadMatcher197 Object const& object() const { return object_; }
indexLoadMatcher198 IntPtrMatcher const& index() const { return index_; }
199
200 private:
201 Object const object_;
202 IntPtrMatcher const index_;
203 };
204
205
206 // For shorter pattern matching code, this struct matches both the left and
207 // right hand sides of a binary operation and can put constants on the right
208 // if they appear on the left hand side of a commutative operation.
209 template <typename Left, typename Right>
210 struct BinopMatcher : public NodeMatcher {
BinopMatcherBinopMatcher211 explicit BinopMatcher(Node* node)
212 : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) {
213 if (HasProperty(Operator::kCommutative)) PutConstantOnRight();
214 }
BinopMatcherBinopMatcher215 BinopMatcher(Node* node, bool allow_input_swap)
216 : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) {
217 if (allow_input_swap) PutConstantOnRight();
218 }
219
220 typedef Left LeftMatcher;
221 typedef Right RightMatcher;
222
leftBinopMatcher223 const Left& left() const { return left_; }
rightBinopMatcher224 const Right& right() const { return right_; }
225
IsFoldableBinopMatcher226 bool IsFoldable() const { return left().HasValue() && right().HasValue(); }
LeftEqualsRightBinopMatcher227 bool LeftEqualsRight() const { return left().node() == right().node(); }
228
229 protected:
SwapInputsBinopMatcher230 void SwapInputs() {
231 std::swap(left_, right_);
232 node()->ReplaceInput(0, left().node());
233 node()->ReplaceInput(1, right().node());
234 }
235
236 private:
PutConstantOnRightBinopMatcher237 void PutConstantOnRight() {
238 if (left().HasValue() && !right().HasValue()) {
239 SwapInputs();
240 }
241 }
242
243 Left left_;
244 Right right_;
245 };
246
247 typedef BinopMatcher<Int32Matcher, Int32Matcher> Int32BinopMatcher;
248 typedef BinopMatcher<Uint32Matcher, Uint32Matcher> Uint32BinopMatcher;
249 typedef BinopMatcher<Int64Matcher, Int64Matcher> Int64BinopMatcher;
250 typedef BinopMatcher<Uint64Matcher, Uint64Matcher> Uint64BinopMatcher;
251 typedef BinopMatcher<IntPtrMatcher, IntPtrMatcher> IntPtrBinopMatcher;
252 typedef BinopMatcher<UintPtrMatcher, UintPtrMatcher> UintPtrBinopMatcher;
253 typedef BinopMatcher<Float32Matcher, Float32Matcher> Float32BinopMatcher;
254 typedef BinopMatcher<Float64Matcher, Float64Matcher> Float64BinopMatcher;
255 typedef BinopMatcher<NumberMatcher, NumberMatcher> NumberBinopMatcher;
256
257
258 template <class BinopMatcher, IrOpcode::Value kMulOpcode,
259 IrOpcode::Value kShiftOpcode>
260 struct ScaleMatcher {
261 explicit ScaleMatcher(Node* node, bool allow_power_of_two_plus_one = false)
262 : scale_(-1), power_of_two_plus_one_(false) {
263 if (node->InputCount() < 2) return;
264 BinopMatcher m(node);
265 if (node->opcode() == kShiftOpcode) {
266 if (m.right().HasValue()) {
267 typename BinopMatcher::RightMatcher::ValueType value =
268 m.right().Value();
269 if (value >= 0 && value <= 3) {
270 scale_ = static_cast<int>(value);
271 }
272 }
273 } else if (node->opcode() == kMulOpcode) {
274 if (m.right().HasValue()) {
275 typename BinopMatcher::RightMatcher::ValueType value =
276 m.right().Value();
277 if (value == 1) {
278 scale_ = 0;
279 } else if (value == 2) {
280 scale_ = 1;
281 } else if (value == 4) {
282 scale_ = 2;
283 } else if (value == 8) {
284 scale_ = 3;
285 } else if (allow_power_of_two_plus_one) {
286 if (value == 3) {
287 scale_ = 1;
288 power_of_two_plus_one_ = true;
289 } else if (value == 5) {
290 scale_ = 2;
291 power_of_two_plus_one_ = true;
292 } else if (value == 9) {
293 scale_ = 3;
294 power_of_two_plus_one_ = true;
295 }
296 }
297 }
298 }
299 }
300
matchesScaleMatcher301 bool matches() const { return scale_ != -1; }
scaleScaleMatcher302 int scale() const { return scale_; }
power_of_two_plus_oneScaleMatcher303 bool power_of_two_plus_one() const { return power_of_two_plus_one_; }
304
305 private:
306 int scale_;
307 bool power_of_two_plus_one_;
308 };
309
310 typedef ScaleMatcher<Int32BinopMatcher, IrOpcode::kInt32Mul,
311 IrOpcode::kWord32Shl> Int32ScaleMatcher;
312 typedef ScaleMatcher<Int64BinopMatcher, IrOpcode::kInt64Mul,
313 IrOpcode::kWord64Shl> Int64ScaleMatcher;
314
315
316 template <class BinopMatcher, IrOpcode::Value kAddOpcode,
317 IrOpcode::Value kMulOpcode, IrOpcode::Value kShiftOpcode>
318 struct AddMatcher : public BinopMatcher {
319 static const IrOpcode::Value kOpcode = kAddOpcode;
320 typedef ScaleMatcher<BinopMatcher, kMulOpcode, kShiftOpcode> Matcher;
321
AddMatcherAddMatcher322 AddMatcher(Node* node, bool allow_input_swap)
323 : BinopMatcher(node, allow_input_swap),
324 scale_(-1),
325 power_of_two_plus_one_(false) {
326 Initialize(node, allow_input_swap);
327 }
AddMatcherAddMatcher328 explicit AddMatcher(Node* node)
329 : BinopMatcher(node, node->op()->HasProperty(Operator::kCommutative)),
330 scale_(-1),
331 power_of_two_plus_one_(false) {
332 Initialize(node, node->op()->HasProperty(Operator::kCommutative));
333 }
334
HasIndexInputAddMatcher335 bool HasIndexInput() const { return scale_ != -1; }
IndexInputAddMatcher336 Node* IndexInput() const {
337 DCHECK(HasIndexInput());
338 return this->left().node()->InputAt(0);
339 }
scaleAddMatcher340 int scale() const {
341 DCHECK(HasIndexInput());
342 return scale_;
343 }
power_of_two_plus_oneAddMatcher344 bool power_of_two_plus_one() const { return power_of_two_plus_one_; }
345
346 private:
InitializeAddMatcher347 void Initialize(Node* node, bool allow_input_swap) {
348 Matcher left_matcher(this->left().node(), true);
349 if (left_matcher.matches()) {
350 scale_ = left_matcher.scale();
351 power_of_two_plus_one_ = left_matcher.power_of_two_plus_one();
352 return;
353 }
354
355 if (!allow_input_swap) {
356 return;
357 }
358
359 Matcher right_matcher(this->right().node(), true);
360 if (right_matcher.matches()) {
361 scale_ = right_matcher.scale();
362 power_of_two_plus_one_ = right_matcher.power_of_two_plus_one();
363 this->SwapInputs();
364 return;
365 }
366
367 if (this->right().opcode() == kAddOpcode &&
368 this->left().opcode() != kAddOpcode) {
369 this->SwapInputs();
370 }
371 }
372
373 int scale_;
374 bool power_of_two_plus_one_;
375 };
376
377 typedef AddMatcher<Int32BinopMatcher, IrOpcode::kInt32Add, IrOpcode::kInt32Mul,
378 IrOpcode::kWord32Shl> Int32AddMatcher;
379 typedef AddMatcher<Int64BinopMatcher, IrOpcode::kInt64Add, IrOpcode::kInt64Mul,
380 IrOpcode::kWord64Shl> Int64AddMatcher;
381
382
383 template <class AddMatcher>
384 struct BaseWithIndexAndDisplacementMatcher {
BaseWithIndexAndDisplacementMatcherBaseWithIndexAndDisplacementMatcher385 BaseWithIndexAndDisplacementMatcher(Node* node, bool allow_input_swap)
386 : matches_(false),
387 index_(nullptr),
388 scale_(0),
389 base_(nullptr),
390 displacement_(nullptr) {
391 Initialize(node, allow_input_swap);
392 }
393
BaseWithIndexAndDisplacementMatcherBaseWithIndexAndDisplacementMatcher394 explicit BaseWithIndexAndDisplacementMatcher(Node* node)
395 : matches_(false),
396 index_(nullptr),
397 scale_(0),
398 base_(nullptr),
399 displacement_(nullptr) {
400 Initialize(node, node->op()->HasProperty(Operator::kCommutative));
401 }
402
matchesBaseWithIndexAndDisplacementMatcher403 bool matches() const { return matches_; }
indexBaseWithIndexAndDisplacementMatcher404 Node* index() const { return index_; }
scaleBaseWithIndexAndDisplacementMatcher405 int scale() const { return scale_; }
baseBaseWithIndexAndDisplacementMatcher406 Node* base() const { return base_; }
displacementBaseWithIndexAndDisplacementMatcher407 Node* displacement() const { return displacement_; }
408
409 private:
410 bool matches_;
411 Node* index_;
412 int scale_;
413 Node* base_;
414 Node* displacement_;
415
InitializeBaseWithIndexAndDisplacementMatcher416 void Initialize(Node* node, bool allow_input_swap) {
417 // The BaseWithIndexAndDisplacementMatcher canonicalizes the order of
418 // displacements and scale factors that are used as inputs, so instead of
419 // enumerating all possible patterns by brute force, checking for node
420 // clusters using the following templates in the following order suffices to
421 // find all of the interesting cases (S = index * scale, B = base input, D =
422 // displacement input):
423 // (S + (B + D))
424 // (S + (B + B))
425 // (S + D)
426 // (S + B)
427 // ((S + D) + B)
428 // ((S + B) + D)
429 // ((B + D) + B)
430 // ((B + B) + D)
431 // (B + D)
432 // (B + B)
433 if (node->InputCount() < 2) return;
434 AddMatcher m(node, allow_input_swap);
435 Node* left = m.left().node();
436 Node* right = m.right().node();
437 Node* displacement = nullptr;
438 Node* base = nullptr;
439 Node* index = nullptr;
440 Node* scale_expression = nullptr;
441 bool power_of_two_plus_one = false;
442 int scale = 0;
443 if (m.HasIndexInput() && left->OwnedBy(node)) {
444 index = m.IndexInput();
445 scale = m.scale();
446 scale_expression = left;
447 power_of_two_plus_one = m.power_of_two_plus_one();
448 if (right->opcode() == AddMatcher::kOpcode && right->OwnedBy(node)) {
449 AddMatcher right_matcher(right);
450 if (right_matcher.right().HasValue()) {
451 // (S + (B + D))
452 base = right_matcher.left().node();
453 displacement = right_matcher.right().node();
454 } else {
455 // (S + (B + B))
456 base = right;
457 }
458 } else if (m.right().HasValue()) {
459 // (S + D)
460 displacement = right;
461 } else {
462 // (S + B)
463 base = right;
464 }
465 } else {
466 if (left->opcode() == AddMatcher::kOpcode && left->OwnedBy(node)) {
467 AddMatcher left_matcher(left);
468 Node* left_left = left_matcher.left().node();
469 Node* left_right = left_matcher.right().node();
470 if (left_matcher.HasIndexInput() && left_left->OwnedBy(left)) {
471 if (left_matcher.right().HasValue()) {
472 // ((S + D) + B)
473 index = left_matcher.IndexInput();
474 scale = left_matcher.scale();
475 scale_expression = left_left;
476 power_of_two_plus_one = left_matcher.power_of_two_plus_one();
477 displacement = left_right;
478 base = right;
479 } else if (m.right().HasValue()) {
480 // ((S + B) + D)
481 index = left_matcher.IndexInput();
482 scale = left_matcher.scale();
483 scale_expression = left_left;
484 power_of_two_plus_one = left_matcher.power_of_two_plus_one();
485 base = left_right;
486 displacement = right;
487 } else {
488 // (B + B)
489 index = left;
490 base = right;
491 }
492 } else {
493 if (left_matcher.right().HasValue()) {
494 // ((B + D) + B)
495 index = left_left;
496 displacement = left_right;
497 base = right;
498 } else if (m.right().HasValue()) {
499 // ((B + B) + D)
500 index = left_left;
501 base = left_right;
502 displacement = right;
503 } else {
504 // (B + B)
505 index = left;
506 base = right;
507 }
508 }
509 } else {
510 if (m.right().HasValue()) {
511 // (B + D)
512 base = left;
513 displacement = right;
514 } else {
515 // (B + B)
516 base = left;
517 index = right;
518 }
519 }
520 }
521 int64_t value = 0;
522 if (displacement != nullptr) {
523 switch (displacement->opcode()) {
524 case IrOpcode::kInt32Constant: {
525 value = OpParameter<int32_t>(displacement);
526 break;
527 }
528 case IrOpcode::kInt64Constant: {
529 value = OpParameter<int64_t>(displacement);
530 break;
531 }
532 default:
533 UNREACHABLE();
534 break;
535 }
536 if (value == 0) {
537 displacement = nullptr;
538 }
539 }
540 if (power_of_two_plus_one) {
541 if (base != nullptr) {
542 // If the scale requires explicitly using the index as the base, but a
543 // base is already part of the match, then the (1 << N + 1) scale factor
544 // can't be folded into the match and the entire index * scale
545 // calculation must be computed separately.
546 index = scale_expression;
547 scale = 0;
548 } else {
549 base = index;
550 }
551 }
552 base_ = base;
553 displacement_ = displacement;
554 index_ = index;
555 scale_ = scale;
556 matches_ = true;
557 }
558 };
559
560 typedef BaseWithIndexAndDisplacementMatcher<Int32AddMatcher>
561 BaseWithIndexAndDisplacement32Matcher;
562 typedef BaseWithIndexAndDisplacementMatcher<Int64AddMatcher>
563 BaseWithIndexAndDisplacement64Matcher;
564
565 struct BranchMatcher : public NodeMatcher {
566 explicit BranchMatcher(Node* branch);
567
MatchedBranchMatcher568 bool Matched() const { return if_true_ && if_false_; }
569
BranchBranchMatcher570 Node* Branch() const { return node(); }
IfTrueBranchMatcher571 Node* IfTrue() const { return if_true_; }
IfFalseBranchMatcher572 Node* IfFalse() const { return if_false_; }
573
574 private:
575 Node* if_true_;
576 Node* if_false_;
577 };
578
579
580 struct DiamondMatcher : public NodeMatcher {
581 explicit DiamondMatcher(Node* merge);
582
MatchedDiamondMatcher583 bool Matched() const { return branch_; }
IfProjectionsAreOwnedDiamondMatcher584 bool IfProjectionsAreOwned() const {
585 return if_true_->OwnedBy(node()) && if_false_->OwnedBy(node());
586 }
587
BranchDiamondMatcher588 Node* Branch() const { return branch_; }
IfTrueDiamondMatcher589 Node* IfTrue() const { return if_true_; }
IfFalseDiamondMatcher590 Node* IfFalse() const { return if_false_; }
MergeDiamondMatcher591 Node* Merge() const { return node(); }
592
TrueInputOfDiamondMatcher593 Node* TrueInputOf(Node* phi) const {
594 DCHECK(IrOpcode::IsPhiOpcode(phi->opcode()));
595 DCHECK_EQ(3, phi->InputCount());
596 DCHECK_EQ(Merge(), phi->InputAt(2));
597 return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 0 : 1);
598 }
599
FalseInputOfDiamondMatcher600 Node* FalseInputOf(Node* phi) const {
601 DCHECK(IrOpcode::IsPhiOpcode(phi->opcode()));
602 DCHECK_EQ(3, phi->InputCount());
603 DCHECK_EQ(Merge(), phi->InputAt(2));
604 return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 1 : 0);
605 }
606
607 private:
608 Node* branch_;
609 Node* if_true_;
610 Node* if_false_;
611 };
612
613 } // namespace compiler
614 } // namespace internal
615 } // namespace v8
616
617 #endif // V8_COMPILER_NODE_MATCHERS_H_
618