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 { 21 explicit NodeMatcher(Node* node) : node_(node) {} 22 23 Node* node() const { return node_; } 24 const Operator* op() const { return node()->op(); } 25 IrOpcode::Value opcode() const { return node()->opcode(); } 26 27 bool HasProperty(Operator::Property property) const { 28 return op()->HasProperty(property); 29 } 30 Node* InputAt(int index) const { return node()->InputAt(index); } 31 32 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 51 explicit ValueMatcher(Node* node) 52 : NodeMatcher(node), value_(), has_value_(opcode() == kOpcode) { 53 if (has_value_) { 54 value_ = OpParameter<T>(node); 55 } 56 } 57 58 bool HasValue() const { return has_value_; } 59 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 <> 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 <> 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 <> 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> { 112 explicit IntMatcher(Node* node) : ValueMatcher<T, kOpcode>(node) {} 113 114 bool Is(const T& value) const { 115 return this->HasValue() && this->Value() == value; 116 } 117 bool IsInRange(const T& low, const T& high) const { 118 return this->HasValue() && low <= this->Value() && this->Value() <= high; 119 } 120 bool IsMultipleOf(T n) const { 121 return this->HasValue() && (this->Value() % n) == 0; 122 } 123 bool IsPowerOf2() const { 124 return this->HasValue() && this->Value() > 0 && 125 (this->Value() & (this->Value() - 1)) == 0; 126 } 127 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> { 149 explicit FloatMatcher(Node* node) : ValueMatcher<T, kOpcode>(node) {} 150 151 bool Is(const T& value) const { 152 return this->HasValue() && this->Value() == value; 153 } 154 bool IsInRange(const T& low, const T& high) const { 155 return this->HasValue() && low <= this->Value() && this->Value() <= high; 156 } 157 bool IsMinusZero() const { 158 return this->Is(0.0) && std::signbit(this->Value()); 159 } 160 bool IsNaN() const { return this->HasValue() && std::isnan(this->Value()); } 161 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> { 172 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> { 180 explicit ExternalReferenceMatcher(Node* node) 181 : ValueMatcher<ExternalReference, IrOpcode::kExternalConstant>(node) {} 182 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 { 192 explicit LoadMatcher(Node* node) 193 : NodeMatcher(node), object_(InputAt(0)), index_(InputAt(1)) {} 194 195 typedef Object ObjectMatcher; 196 197 Object const& object() const { return object_; } 198 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 { 211 explicit BinopMatcher(Node* node) 212 : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) { 213 if (HasProperty(Operator::kCommutative)) PutConstantOnRight(); 214 } 215 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 223 const Left& left() const { return left_; } 224 const Right& right() const { return right_; } 225 226 bool IsFoldable() const { return left().HasValue() && right().HasValue(); } 227 bool LeftEqualsRight() const { return left().node() == right().node(); } 228 229 protected: 230 void SwapInputs() { 231 std::swap(left_, right_); 232 node()->ReplaceInput(0, left().node()); 233 node()->ReplaceInput(1, right().node()); 234 } 235 236 private: 237 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 302 bool matches() const { return scale_ != -1; } 303 int scale() const { return scale_; } 304 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 323 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 } 329 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 336 bool HasIndexInput() const { return scale_ != -1; } 337 Node* IndexInput() const { 338 DCHECK(HasIndexInput()); 339 return this->left().node()->InputAt(0); 340 } 341 int scale() const { 342 DCHECK(HasIndexInput()); 343 return scale_; 344 } 345 bool power_of_two_plus_one() const { return power_of_two_plus_one_; } 346 347 private: 348 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 { 386 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 395 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 404 bool matches() const { return matches_; } 405 Node* index() const { return index_; } 406 int scale() const { return scale_; } 407 Node* base() const { return base_; } 408 Node* displacement() const { return displacement_; } 409 410 private: 411 bool matches_; 412 Node* index_; 413 int scale_; 414 Node* base_; 415 Node* displacement_; 416 417 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 569 bool Matched() const { return if_true_ && if_false_; } 570 571 Node* Branch() const { return node(); } 572 Node* IfTrue() const { return if_true_; } 573 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 584 bool Matched() const { return branch_; } 585 bool IfProjectionsAreOwned() const { 586 return if_true_->OwnedBy(node()) && if_false_->OwnedBy(node()); 587 } 588 589 Node* Branch() const { return branch_; } 590 Node* IfTrue() const { return if_true_; } 591 Node* IfFalse() const { return if_false_; } 592 Node* Merge() const { return node(); } 593 594 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 601 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