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 typedef BinopMatcher<HeapObjectMatcher, HeapObjectMatcher>
257 HeapObjectBinopMatcher;
258
259 template <class BinopMatcher, IrOpcode::Value kMulOpcode,
260 IrOpcode::Value kShiftOpcode>
261 struct ScaleMatcher {
262 explicit ScaleMatcher(Node* node, bool allow_power_of_two_plus_one = false)
263 : scale_(-1), power_of_two_plus_one_(false) {
264 if (node->InputCount() < 2) return;
265 BinopMatcher m(node);
266 if (node->opcode() == kShiftOpcode) {
267 if (m.right().HasValue()) {
268 typename BinopMatcher::RightMatcher::ValueType value =
269 m.right().Value();
270 if (value >= 0 && value <= 3) {
271 scale_ = static_cast<int>(value);
272 }
273 }
274 } else if (node->opcode() == kMulOpcode) {
275 if (m.right().HasValue()) {
276 typename BinopMatcher::RightMatcher::ValueType value =
277 m.right().Value();
278 if (value == 1) {
279 scale_ = 0;
280 } else if (value == 2) {
281 scale_ = 1;
282 } else if (value == 4) {
283 scale_ = 2;
284 } else if (value == 8) {
285 scale_ = 3;
286 } else if (allow_power_of_two_plus_one) {
287 if (value == 3) {
288 scale_ = 1;
289 power_of_two_plus_one_ = true;
290 } else if (value == 5) {
291 scale_ = 2;
292 power_of_two_plus_one_ = true;
293 } else if (value == 9) {
294 scale_ = 3;
295 power_of_two_plus_one_ = true;
296 }
297 }
298 }
299 }
300 }
301
matchesScaleMatcher302 bool matches() const { return scale_ != -1; }
scaleScaleMatcher303 int scale() const { return scale_; }
power_of_two_plus_oneScaleMatcher304 bool power_of_two_plus_one() const { return power_of_two_plus_one_; }
305
306 private:
307 int scale_;
308 bool power_of_two_plus_one_;
309 };
310
311 typedef ScaleMatcher<Int32BinopMatcher, IrOpcode::kInt32Mul,
312 IrOpcode::kWord32Shl> Int32ScaleMatcher;
313 typedef ScaleMatcher<Int64BinopMatcher, IrOpcode::kInt64Mul,
314 IrOpcode::kWord64Shl> Int64ScaleMatcher;
315
316
317 template <class BinopMatcher, IrOpcode::Value kAddOpcode,
318 IrOpcode::Value kMulOpcode, IrOpcode::Value kShiftOpcode>
319 struct AddMatcher : public BinopMatcher {
320 static const IrOpcode::Value kOpcode = kAddOpcode;
321 typedef ScaleMatcher<BinopMatcher, kMulOpcode, kShiftOpcode> Matcher;
322
AddMatcherAddMatcher323 AddMatcher(Node* node, bool allow_input_swap)
324 : BinopMatcher(node, allow_input_swap),
325 scale_(-1),
326 power_of_two_plus_one_(false) {
327 Initialize(node, allow_input_swap);
328 }
AddMatcherAddMatcher329 explicit AddMatcher(Node* node)
330 : BinopMatcher(node, node->op()->HasProperty(Operator::kCommutative)),
331 scale_(-1),
332 power_of_two_plus_one_(false) {
333 Initialize(node, node->op()->HasProperty(Operator::kCommutative));
334 }
335
HasIndexInputAddMatcher336 bool HasIndexInput() const { return scale_ != -1; }
IndexInputAddMatcher337 Node* IndexInput() const {
338 DCHECK(HasIndexInput());
339 return this->left().node()->InputAt(0);
340 }
scaleAddMatcher341 int scale() const {
342 DCHECK(HasIndexInput());
343 return scale_;
344 }
power_of_two_plus_oneAddMatcher345 bool power_of_two_plus_one() const { return power_of_two_plus_one_; }
346
347 private:
InitializeAddMatcher348 void Initialize(Node* node, bool allow_input_swap) {
349 Matcher left_matcher(this->left().node(), true);
350 if (left_matcher.matches()) {
351 scale_ = left_matcher.scale();
352 power_of_two_plus_one_ = left_matcher.power_of_two_plus_one();
353 return;
354 }
355
356 if (!allow_input_swap) {
357 return;
358 }
359
360 Matcher right_matcher(this->right().node(), true);
361 if (right_matcher.matches()) {
362 scale_ = right_matcher.scale();
363 power_of_two_plus_one_ = right_matcher.power_of_two_plus_one();
364 this->SwapInputs();
365 return;
366 }
367
368 if (this->right().opcode() == kAddOpcode &&
369 this->left().opcode() != kAddOpcode) {
370 this->SwapInputs();
371 }
372 }
373
374 int scale_;
375 bool power_of_two_plus_one_;
376 };
377
378 typedef AddMatcher<Int32BinopMatcher, IrOpcode::kInt32Add, IrOpcode::kInt32Mul,
379 IrOpcode::kWord32Shl> Int32AddMatcher;
380 typedef AddMatcher<Int64BinopMatcher, IrOpcode::kInt64Add, IrOpcode::kInt64Mul,
381 IrOpcode::kWord64Shl> Int64AddMatcher;
382
383
384 template <class AddMatcher>
385 struct BaseWithIndexAndDisplacementMatcher {
BaseWithIndexAndDisplacementMatcherBaseWithIndexAndDisplacementMatcher386 BaseWithIndexAndDisplacementMatcher(Node* node, bool allow_input_swap)
387 : matches_(false),
388 index_(nullptr),
389 scale_(0),
390 base_(nullptr),
391 displacement_(nullptr) {
392 Initialize(node, allow_input_swap);
393 }
394
BaseWithIndexAndDisplacementMatcherBaseWithIndexAndDisplacementMatcher395 explicit BaseWithIndexAndDisplacementMatcher(Node* node)
396 : matches_(false),
397 index_(nullptr),
398 scale_(0),
399 base_(nullptr),
400 displacement_(nullptr) {
401 Initialize(node, node->op()->HasProperty(Operator::kCommutative));
402 }
403
matchesBaseWithIndexAndDisplacementMatcher404 bool matches() const { return matches_; }
indexBaseWithIndexAndDisplacementMatcher405 Node* index() const { return index_; }
scaleBaseWithIndexAndDisplacementMatcher406 int scale() const { return scale_; }
baseBaseWithIndexAndDisplacementMatcher407 Node* base() const { return base_; }
displacementBaseWithIndexAndDisplacementMatcher408 Node* displacement() const { return displacement_; }
409
410 private:
411 bool matches_;
412 Node* index_;
413 int scale_;
414 Node* base_;
415 Node* displacement_;
416
InitializeBaseWithIndexAndDisplacementMatcher417 void Initialize(Node* node, bool allow_input_swap) {
418 // The BaseWithIndexAndDisplacementMatcher canonicalizes the order of
419 // displacements and scale factors that are used as inputs, so instead of
420 // enumerating all possible patterns by brute force, checking for node
421 // clusters using the following templates in the following order suffices to
422 // find all of the interesting cases (S = index * scale, B = base input, D =
423 // displacement input):
424 // (S + (B + D))
425 // (S + (B + B))
426 // (S + D)
427 // (S + B)
428 // ((S + D) + B)
429 // ((S + B) + D)
430 // ((B + D) + B)
431 // ((B + B) + D)
432 // (B + D)
433 // (B + B)
434 if (node->InputCount() < 2) return;
435 AddMatcher m(node, allow_input_swap);
436 Node* left = m.left().node();
437 Node* right = m.right().node();
438 Node* displacement = nullptr;
439 Node* base = nullptr;
440 Node* index = nullptr;
441 Node* scale_expression = nullptr;
442 bool power_of_two_plus_one = false;
443 int scale = 0;
444 if (m.HasIndexInput() && left->OwnedBy(node)) {
445 index = m.IndexInput();
446 scale = m.scale();
447 scale_expression = left;
448 power_of_two_plus_one = m.power_of_two_plus_one();
449 if (right->opcode() == AddMatcher::kOpcode && right->OwnedBy(node)) {
450 AddMatcher right_matcher(right);
451 if (right_matcher.right().HasValue()) {
452 // (S + (B + D))
453 base = right_matcher.left().node();
454 displacement = right_matcher.right().node();
455 } else {
456 // (S + (B + B))
457 base = right;
458 }
459 } else if (m.right().HasValue()) {
460 // (S + D)
461 displacement = right;
462 } else {
463 // (S + B)
464 base = right;
465 }
466 } else {
467 if (left->opcode() == AddMatcher::kOpcode && left->OwnedBy(node)) {
468 AddMatcher left_matcher(left);
469 Node* left_left = left_matcher.left().node();
470 Node* left_right = left_matcher.right().node();
471 if (left_matcher.HasIndexInput() && left_left->OwnedBy(left)) {
472 if (left_matcher.right().HasValue()) {
473 // ((S + D) + B)
474 index = left_matcher.IndexInput();
475 scale = left_matcher.scale();
476 scale_expression = left_left;
477 power_of_two_plus_one = left_matcher.power_of_two_plus_one();
478 displacement = left_right;
479 base = right;
480 } else if (m.right().HasValue()) {
481 // ((S + B) + D)
482 index = left_matcher.IndexInput();
483 scale = left_matcher.scale();
484 scale_expression = left_left;
485 power_of_two_plus_one = left_matcher.power_of_two_plus_one();
486 base = left_right;
487 displacement = right;
488 } else {
489 // (B + B)
490 index = left;
491 base = right;
492 }
493 } else {
494 if (left_matcher.right().HasValue()) {
495 // ((B + D) + B)
496 index = left_left;
497 displacement = left_right;
498 base = right;
499 } else if (m.right().HasValue()) {
500 // ((B + B) + D)
501 index = left_left;
502 base = left_right;
503 displacement = right;
504 } else {
505 // (B + B)
506 index = left;
507 base = right;
508 }
509 }
510 } else {
511 if (m.right().HasValue()) {
512 // (B + D)
513 base = left;
514 displacement = right;
515 } else {
516 // (B + B)
517 base = left;
518 index = right;
519 }
520 }
521 }
522 int64_t value = 0;
523 if (displacement != nullptr) {
524 switch (displacement->opcode()) {
525 case IrOpcode::kInt32Constant: {
526 value = OpParameter<int32_t>(displacement);
527 break;
528 }
529 case IrOpcode::kInt64Constant: {
530 value = OpParameter<int64_t>(displacement);
531 break;
532 }
533 default:
534 UNREACHABLE();
535 break;
536 }
537 if (value == 0) {
538 displacement = nullptr;
539 }
540 }
541 if (power_of_two_plus_one) {
542 if (base != nullptr) {
543 // If the scale requires explicitly using the index as the base, but a
544 // base is already part of the match, then the (1 << N + 1) scale factor
545 // can't be folded into the match and the entire index * scale
546 // calculation must be computed separately.
547 index = scale_expression;
548 scale = 0;
549 } else {
550 base = index;
551 }
552 }
553 base_ = base;
554 displacement_ = displacement;
555 index_ = index;
556 scale_ = scale;
557 matches_ = true;
558 }
559 };
560
561 typedef BaseWithIndexAndDisplacementMatcher<Int32AddMatcher>
562 BaseWithIndexAndDisplacement32Matcher;
563 typedef BaseWithIndexAndDisplacementMatcher<Int64AddMatcher>
564 BaseWithIndexAndDisplacement64Matcher;
565
566 struct BranchMatcher : public NodeMatcher {
567 explicit BranchMatcher(Node* branch);
568
MatchedBranchMatcher569 bool Matched() const { return if_true_ && if_false_; }
570
BranchBranchMatcher571 Node* Branch() const { return node(); }
IfTrueBranchMatcher572 Node* IfTrue() const { return if_true_; }
IfFalseBranchMatcher573 Node* IfFalse() const { return if_false_; }
574
575 private:
576 Node* if_true_;
577 Node* if_false_;
578 };
579
580
581 struct DiamondMatcher : public NodeMatcher {
582 explicit DiamondMatcher(Node* merge);
583
MatchedDiamondMatcher584 bool Matched() const { return branch_; }
IfProjectionsAreOwnedDiamondMatcher585 bool IfProjectionsAreOwned() const {
586 return if_true_->OwnedBy(node()) && if_false_->OwnedBy(node());
587 }
588
BranchDiamondMatcher589 Node* Branch() const { return branch_; }
IfTrueDiamondMatcher590 Node* IfTrue() const { return if_true_; }
IfFalseDiamondMatcher591 Node* IfFalse() const { return if_false_; }
MergeDiamondMatcher592 Node* Merge() const { return node(); }
593
TrueInputOfDiamondMatcher594 Node* TrueInputOf(Node* phi) const {
595 DCHECK(IrOpcode::IsPhiOpcode(phi->opcode()));
596 DCHECK_EQ(3, phi->InputCount());
597 DCHECK_EQ(Merge(), phi->InputAt(2));
598 return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 0 : 1);
599 }
600
FalseInputOfDiamondMatcher601 Node* FalseInputOf(Node* phi) const {
602 DCHECK(IrOpcode::IsPhiOpcode(phi->opcode()));
603 DCHECK_EQ(3, phi->InputCount());
604 DCHECK_EQ(Merge(), phi->InputAt(2));
605 return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 1 : 0);
606 }
607
608 private:
609 Node* branch_;
610 Node* if_true_;
611 Node* if_false_;
612 };
613
614 } // namespace compiler
615 } // namespace internal
616 } // namespace v8
617
618 #endif // V8_COMPILER_NODE_MATCHERS_H_
619