Line data Source code
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/compiler/node.h"
12 : #include "src/compiler/operator.h"
13 : #include "src/double.h"
14 : #include "src/external-reference.h"
15 : #include "src/globals.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 {
26 172470648 : explicit NodeMatcher(Node* node) : node_(node) {}
27 :
28 102350563 : Node* node() const { return node_; }
29 : const Operator* op() const { return node()->op(); }
30 : IrOpcode::Value opcode() const { return node()->opcode(); }
31 :
32 : bool HasProperty(Operator::Property property) const {
33 : return op()->HasProperty(property);
34 : }
35 : Node* InputAt(int index) const { return node()->InputAt(index); }
36 :
37 772 : 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 :
56 : explicit ValueMatcher(Node* node)
57 56226665 : : NodeMatcher(node), value_(), has_value_(opcode() == kOpcode) {
58 39483703 : if (has_value_) {
59 12294485 : value_ = OpParameter<T>(node->op());
60 : }
61 : }
62 :
63 : bool HasValue() const { return has_value_; }
64 : const T& Value() const {
65 : DCHECK(HasValue());
66 : return value_;
67 : }
68 :
69 : private:
70 : T value_;
71 : bool has_value_;
72 : };
73 :
74 :
75 : template <>
76 : inline ValueMatcher<uint32_t, IrOpcode::kInt32Constant>::ValueMatcher(
77 : Node* node)
78 : : NodeMatcher(node),
79 : value_(),
80 3567471 : has_value_(opcode() == IrOpcode::kInt32Constant) {
81 2131643 : if (has_value_) {
82 1011615 : value_ = static_cast<uint32_t>(OpParameter<int32_t>(node->op()));
83 : }
84 : }
85 :
86 :
87 : template <>
88 : inline ValueMatcher<int64_t, IrOpcode::kInt64Constant>::ValueMatcher(Node* node)
89 85089805 : : NodeMatcher(node), value_(), has_value_(false) {
90 92652471 : if (opcode() == IrOpcode::kInt32Constant) {
91 7367953 : value_ = OpParameter<int32_t>(node->op());
92 7201419 : has_value_ = true;
93 85284518 : } else if (opcode() == IrOpcode::kInt64Constant) {
94 29349676 : value_ = OpParameter<int64_t>(node->op());
95 27249441 : has_value_ = true;
96 : }
97 : }
98 :
99 :
100 : template <>
101 : inline ValueMatcher<uint64_t, IrOpcode::kInt64Constant>::ValueMatcher(
102 : Node* node)
103 101854 : : NodeMatcher(node), value_(), has_value_(false) {
104 162824 : if (opcode() == IrOpcode::kInt32Constant) {
105 5 : value_ = static_cast<uint32_t>(OpParameter<int32_t>(node->op()));
106 5 : has_value_ = true;
107 162819 : } else if (opcode() == IrOpcode::kInt64Constant) {
108 130994 : value_ = static_cast<uint64_t>(OpParameter<int64_t>(node->op()));
109 75901 : has_value_ = true;
110 : }
111 : }
112 :
113 :
114 : // A pattern matcher for integer constants.
115 : template <typename T, IrOpcode::Value kOpcode>
116 : struct IntMatcher final : public ValueMatcher<T, kOpcode> {
117 : explicit IntMatcher(Node* node) : ValueMatcher<T, kOpcode>(node) {}
118 :
119 : bool Is(const T& value) const {
120 13340457 : return this->HasValue() && this->Value() == value;
121 : }
122 : bool IsInRange(const T& low, const T& high) const {
123 705851 : return this->HasValue() && low <= this->Value() && this->Value() <= high;
124 : }
125 : bool IsMultipleOf(T n) const {
126 15969 : return this->HasValue() && (this->Value() % n) == 0;
127 : }
128 : bool IsPowerOf2() const {
129 : return this->HasValue() && this->Value() > 0 &&
130 27641 : (this->Value() & (this->Value() - 1)) == 0;
131 : }
132 : bool IsNegativePowerOf2() const {
133 : return this->HasValue() && this->Value() < 0 &&
134 : ((this->Value() == kMinInt) ||
135 720331 : (-this->Value() & (-this->Value() - 1)) == 0);
136 : }
137 4330 : bool IsNegative() const { return this->HasValue() && this->Value() < 0; }
138 : };
139 :
140 : using Int32Matcher = IntMatcher<int32_t, IrOpcode::kInt32Constant>;
141 : using Uint32Matcher = IntMatcher<uint32_t, IrOpcode::kInt32Constant>;
142 : using Int64Matcher = IntMatcher<int64_t, IrOpcode::kInt64Constant>;
143 : using Uint64Matcher = IntMatcher<uint64_t, IrOpcode::kInt64Constant>;
144 : #if V8_HOST_ARCH_32_BIT
145 : using IntPtrMatcher = Int32Matcher;
146 : using UintPtrMatcher = Uint32Matcher;
147 : #else
148 : using IntPtrMatcher = Int64Matcher;
149 : using UintPtrMatcher = Uint64Matcher;
150 : #endif
151 :
152 :
153 : // A pattern matcher for floating point constants.
154 : template <typename T, IrOpcode::Value kOpcode>
155 : struct FloatMatcher final : public ValueMatcher<T, kOpcode> {
156 : explicit FloatMatcher(Node* node) : ValueMatcher<T, kOpcode>(node) {}
157 :
158 : bool Is(const T& value) const {
159 360769 : return this->HasValue() && this->Value() == value;
160 : }
161 : bool IsInRange(const T& low, const T& high) const {
162 1576 : return this->HasValue() && low <= this->Value() && this->Value() <= high;
163 : }
164 27395 : bool IsMinusZero() const {
165 35846 : return this->Is(0.0) && std::signbit(this->Value());
166 : }
167 : bool IsNegative() const { return this->HasValue() && this->Value() < 0.0; }
168 325424 : bool IsNaN() const { return this->HasValue() && std::isnan(this->Value()); }
169 12 : bool IsZero() const { return this->Is(0.0) && !std::signbit(this->Value()); }
170 : bool IsNormal() const {
171 48335 : return this->HasValue() && std::isnormal(this->Value());
172 : }
173 : bool IsInteger() const {
174 5182 : return this->HasValue() && std::nearbyint(this->Value()) == this->Value();
175 : }
176 12306 : bool IsPositiveOrNegativePowerOf2() const {
177 12306 : if (!this->HasValue() || (this->Value() == 0.0)) {
178 : return false;
179 : }
180 12306 : Double value = Double(this->Value());
181 24612 : return !value.IsInfinite() && base::bits::IsPowerOfTwo(value.Significand());
182 : }
183 : };
184 :
185 : using Float32Matcher = FloatMatcher<float, IrOpcode::kFloat32Constant>;
186 : using Float64Matcher = FloatMatcher<double, IrOpcode::kFloat64Constant>;
187 : using NumberMatcher = FloatMatcher<double, IrOpcode::kNumberConstant>;
188 :
189 : // A pattern matcher for heap object constants.
190 : struct HeapObjectMatcher final
191 : : public ValueMatcher<Handle<HeapObject>, IrOpcode::kHeapConstant> {
192 : explicit HeapObjectMatcher(Node* node)
193 : : ValueMatcher<Handle<HeapObject>, IrOpcode::kHeapConstant>(node) {}
194 :
195 : bool Is(Handle<HeapObject> const& value) const {
196 255156 : return this->HasValue() && this->Value().address() == value.address();
197 : }
198 :
199 : HeapObjectRef Ref(JSHeapBroker* broker) const {
200 1261457 : return HeapObjectRef(broker, this->Value());
201 : }
202 : };
203 :
204 :
205 : // A pattern matcher for external reference constants.
206 : struct ExternalReferenceMatcher final
207 : : public ValueMatcher<ExternalReference, IrOpcode::kExternalConstant> {
208 : explicit ExternalReferenceMatcher(Node* node)
209 : : ValueMatcher<ExternalReference, IrOpcode::kExternalConstant>(node) {}
210 : bool Is(const ExternalReference& value) const {
211 563169 : return this->HasValue() && this->Value() == value;
212 : }
213 : };
214 :
215 :
216 : // For shorter pattern matching code, this struct matches the inputs to
217 : // machine-level load operations.
218 : template <typename Object>
219 : struct LoadMatcher : public NodeMatcher {
220 5305025 : explicit LoadMatcher(Node* node)
221 5434582 : : NodeMatcher(node), object_(InputAt(0)), index_(InputAt(1)) {}
222 :
223 : using ObjectMatcher = Object;
224 :
225 : Object const& object() const { return object_; }
226 : IntPtrMatcher const& index() const { return index_; }
227 :
228 : private:
229 : Object const object_;
230 : IntPtrMatcher const index_;
231 : };
232 :
233 :
234 : // For shorter pattern matching code, this struct matches both the left and
235 : // right hand sides of a binary operation and can put constants on the right
236 : // if they appear on the left hand side of a commutative operation.
237 : template <typename Left, typename Right>
238 : struct BinopMatcher : public NodeMatcher {
239 36154072 : explicit BinopMatcher(Node* node)
240 : : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) {
241 36154072 : if (HasProperty(Operator::kCommutative)) PutConstantOnRight();
242 36154072 : }
243 15976339 : BinopMatcher(Node* node, bool allow_input_swap)
244 : : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) {
245 15976339 : if (allow_input_swap) PutConstantOnRight();
246 15976336 : }
247 :
248 : using LeftMatcher = Left;
249 : using RightMatcher = Right;
250 :
251 : const Left& left() const { return left_; }
252 : const Right& right() const { return right_; }
253 :
254 11137295 : bool IsFoldable() const { return left().HasValue() && right().HasValue(); }
255 : bool LeftEqualsRight() const { return left().node() == right().node(); }
256 :
257 : protected:
258 680915 : void SwapInputs() {
259 : std::swap(left_, right_);
260 : // TODO(tebbi): This modification should notify the reducers using
261 : // BinopMatcher. Alternatively, all reducers (especially value numbering)
262 : // could ignore the ordering for commutative binops.
263 680915 : node()->ReplaceInput(0, left().node());
264 680921 : node()->ReplaceInput(1, right().node());
265 680916 : }
266 :
267 : private:
268 : void PutConstantOnRight() {
269 32651067 : if (left().HasValue() && !right().HasValue()) {
270 270696 : SwapInputs();
271 : }
272 : }
273 :
274 : Left left_;
275 : Right right_;
276 : };
277 :
278 : using Int32BinopMatcher = BinopMatcher<Int32Matcher, Int32Matcher>;
279 : using Uint32BinopMatcher = BinopMatcher<Uint32Matcher, Uint32Matcher>;
280 : using Int64BinopMatcher = BinopMatcher<Int64Matcher, Int64Matcher>;
281 : using Uint64BinopMatcher = BinopMatcher<Uint64Matcher, Uint64Matcher>;
282 : using IntPtrBinopMatcher = BinopMatcher<IntPtrMatcher, IntPtrMatcher>;
283 : using UintPtrBinopMatcher = BinopMatcher<UintPtrMatcher, UintPtrMatcher>;
284 : using Float32BinopMatcher = BinopMatcher<Float32Matcher, Float32Matcher>;
285 : using Float64BinopMatcher = BinopMatcher<Float64Matcher, Float64Matcher>;
286 : using NumberBinopMatcher = BinopMatcher<NumberMatcher, NumberMatcher>;
287 : using HeapObjectBinopMatcher =
288 : BinopMatcher<HeapObjectMatcher, HeapObjectMatcher>;
289 :
290 : template <class BinopMatcher, IrOpcode::Value kMulOpcode,
291 : IrOpcode::Value kShiftOpcode>
292 : struct ScaleMatcher {
293 31914948 : explicit ScaleMatcher(Node* node, bool allow_power_of_two_plus_one = false)
294 31914948 : : scale_(-1), power_of_two_plus_one_(false) {
295 51188204 : if (node->InputCount() < 2) return;
296 12641692 : BinopMatcher m(node);
297 12641940 : if (node->opcode() == kShiftOpcode) {
298 992046 : if (m.right().HasValue()) {
299 : typename BinopMatcher::RightMatcher::ValueType value =
300 985125 : m.right().Value();
301 985125 : if (value >= 0 && value <= 3) {
302 615476 : scale_ = static_cast<int>(value);
303 : }
304 : }
305 11649894 : } else if (node->opcode() == kMulOpcode) {
306 104312 : if (m.right().HasValue()) {
307 : typename BinopMatcher::RightMatcher::ValueType value =
308 99687 : m.right().Value();
309 99687 : if (value == 1) {
310 1456 : scale_ = 0;
311 98231 : } else if (value == 2) {
312 1351 : scale_ = 1;
313 96880 : } else if (value == 4) {
314 519 : scale_ = 2;
315 96361 : } else if (value == 8) {
316 1581 : scale_ = 3;
317 94780 : } else if (allow_power_of_two_plus_one) {
318 94780 : if (value == 3) {
319 38420 : scale_ = 1;
320 38420 : power_of_two_plus_one_ = true;
321 56360 : } else if (value == 5) {
322 1650 : scale_ = 2;
323 1650 : power_of_two_plus_one_ = true;
324 54710 : } else if (value == 9) {
325 655 : scale_ = 3;
326 655 : power_of_two_plus_one_ = true;
327 : }
328 : }
329 : }
330 : }
331 : }
332 :
333 : bool matches() const { return scale_ != -1; }
334 : int scale() const { return scale_; }
335 : bool power_of_two_plus_one() const { return power_of_two_plus_one_; }
336 :
337 : private:
338 : int scale_;
339 : bool power_of_two_plus_one_;
340 : };
341 :
342 : using Int32ScaleMatcher =
343 : ScaleMatcher<Int32BinopMatcher, IrOpcode::kInt32Mul, IrOpcode::kWord32Shl>;
344 : using Int64ScaleMatcher =
345 : ScaleMatcher<Int64BinopMatcher, IrOpcode::kInt64Mul, IrOpcode::kWord64Shl>;
346 :
347 : template <class BinopMatcher, IrOpcode::Value AddOpcode,
348 : IrOpcode::Value SubOpcode, IrOpcode::Value kMulOpcode,
349 : IrOpcode::Value kShiftOpcode>
350 : struct AddMatcher : public BinopMatcher {
351 : static const IrOpcode::Value kAddOpcode = AddOpcode;
352 : static const IrOpcode::Value kSubOpcode = SubOpcode;
353 : using Matcher = ScaleMatcher<BinopMatcher, kMulOpcode, kShiftOpcode>;
354 :
355 15413718 : AddMatcher(Node* node, bool allow_input_swap)
356 : : BinopMatcher(node, allow_input_swap),
357 : scale_(-1),
358 15413718 : power_of_two_plus_one_(false) {
359 15414139 : Initialize(node, allow_input_swap);
360 15413807 : }
361 561686 : explicit AddMatcher(Node* node)
362 : : BinopMatcher(node, node->op()->HasProperty(Operator::kCommutative)),
363 : scale_(-1),
364 561686 : power_of_two_plus_one_(false) {
365 561699 : Initialize(node, node->op()->HasProperty(Operator::kCommutative));
366 561710 : }
367 :
368 : bool HasIndexInput() const { return scale_ != -1; }
369 : Node* IndexInput() const {
370 : DCHECK(HasIndexInput());
371 : return this->left().node()->InputAt(0);
372 : }
373 : int scale() const {
374 : DCHECK(HasIndexInput());
375 : return scale_;
376 : }
377 : bool power_of_two_plus_one() const { return power_of_two_plus_one_; }
378 :
379 : private:
380 15975601 : void Initialize(Node* node, bool allow_input_swap) {
381 15975601 : Matcher left_matcher(this->left().node(), true);
382 15975178 : if (left_matcher.matches()) {
383 503814 : scale_ = left_matcher.scale();
384 503814 : power_of_two_plus_one_ = left_matcher.power_of_two_plus_one();
385 1104933 : return;
386 : }
387 :
388 15471364 : if (!allow_input_swap) {
389 : return;
390 : }
391 :
392 15462484 : Matcher right_matcher(this->right().node(), true);
393 15462544 : if (right_matcher.matches()) {
394 88425 : scale_ = right_matcher.scale();
395 88425 : power_of_two_plus_one_ = right_matcher.power_of_two_plus_one();
396 88425 : this->SwapInputs();
397 88425 : return;
398 : }
399 :
400 30109557 : if ((this->left().opcode() != kSubOpcode &&
401 : this->left().opcode() != kAddOpcode) &&
402 : (this->right().opcode() == kAddOpcode ||
403 : this->right().opcode() == kSubOpcode)) {
404 321798 : this->SwapInputs();
405 : }
406 : }
407 :
408 : int scale_;
409 : bool power_of_two_plus_one_;
410 : };
411 :
412 : using Int32AddMatcher =
413 : AddMatcher<Int32BinopMatcher, IrOpcode::kInt32Add, IrOpcode::kInt32Sub,
414 : IrOpcode::kInt32Mul, IrOpcode::kWord32Shl>;
415 : using Int64AddMatcher =
416 : AddMatcher<Int64BinopMatcher, IrOpcode::kInt64Add, IrOpcode::kInt64Sub,
417 : IrOpcode::kInt64Mul, IrOpcode::kWord64Shl>;
418 :
419 : enum DisplacementMode { kPositiveDisplacement, kNegativeDisplacement };
420 :
421 : enum class AddressOption : uint8_t {
422 : kAllowNone = 0u,
423 : kAllowInputSwap = 1u << 0,
424 : kAllowScale = 1u << 1,
425 : kAllowAll = kAllowInputSwap | kAllowScale
426 : };
427 :
428 : using AddressOptions = base::Flags<AddressOption, uint8_t>;
429 : DEFINE_OPERATORS_FOR_FLAGS(AddressOptions)
430 :
431 : template <class AddMatcher>
432 : struct BaseWithIndexAndDisplacementMatcher {
433 : BaseWithIndexAndDisplacementMatcher(Node* node, AddressOptions options)
434 : : matches_(false),
435 : index_(nullptr),
436 : scale_(0),
437 : base_(nullptr),
438 : displacement_(nullptr),
439 13199426 : displacement_mode_(kPositiveDisplacement) {
440 13199426 : Initialize(node, options);
441 : }
442 :
443 2214806 : explicit BaseWithIndexAndDisplacementMatcher(Node* node)
444 : : matches_(false),
445 : index_(nullptr),
446 : scale_(0),
447 : base_(nullptr),
448 : displacement_(nullptr),
449 2214806 : displacement_mode_(kPositiveDisplacement) {
450 4429612 : Initialize(node, AddressOption::kAllowScale |
451 : (node->op()->HasProperty(Operator::kCommutative)
452 : ? AddressOption::kAllowInputSwap
453 : : AddressOption::kAllowNone));
454 2214946 : }
455 :
456 : bool matches() const { return matches_; }
457 : Node* index() const { return index_; }
458 : int scale() const { return scale_; }
459 : Node* base() const { return base_; }
460 : Node* displacement() const { return displacement_; }
461 : DisplacementMode displacement_mode() const { return displacement_mode_; }
462 :
463 : private:
464 : bool matches_;
465 : Node* index_;
466 : int scale_;
467 : Node* base_;
468 : Node* displacement_;
469 : DisplacementMode displacement_mode_;
470 :
471 15413780 : void Initialize(Node* node, AddressOptions options) {
472 : // The BaseWithIndexAndDisplacementMatcher canonicalizes the order of
473 : // displacements and scale factors that are used as inputs, so instead of
474 : // enumerating all possible patterns by brute force, checking for node
475 : // clusters using the following templates in the following order suffices to
476 : // find all of the interesting cases (S = index * scale, B = base input, D =
477 : // displacement input):
478 : // (S + (B + D))
479 : // (S + (B + B))
480 : // (S + D)
481 : // (S + B)
482 : // ((S + D) + B)
483 : // ((S + B) + D)
484 : // ((B + D) + B)
485 : // ((B + B) + D)
486 : // (B + D)
487 : // (B + B)
488 15413782 : if (node->InputCount() < 2) return;
489 15413778 : AddMatcher m(node, options & AddressOption::kAllowInputSwap);
490 : Node* left = m.left().node();
491 : Node* right = m.right().node();
492 : Node* displacement = nullptr;
493 : Node* base = nullptr;
494 : Node* index = nullptr;
495 : Node* scale_expression = nullptr;
496 : bool power_of_two_plus_one = false;
497 : DisplacementMode displacement_mode = kPositiveDisplacement;
498 : int scale = 0;
499 15413659 : if (m.HasIndexInput() && OwnedByAddressingOperand(left)) {
500 : index = m.IndexInput();
501 : scale = m.scale();
502 : scale_expression = left;
503 : power_of_two_plus_one = m.power_of_two_plus_one();
504 : bool match_found = false;
505 304674 : if (right->opcode() == AddMatcher::kSubOpcode &&
506 12 : OwnedByAddressingOperand(right)) {
507 8 : AddMatcher right_matcher(right);
508 8 : if (right_matcher.right().HasValue()) {
509 : // (S + (B - D))
510 : base = right_matcher.left().node();
511 : displacement = right_matcher.right().node();
512 : displacement_mode = kNegativeDisplacement;
513 : match_found = true;
514 : }
515 : }
516 304662 : if (!match_found) {
517 316285 : if (right->opcode() == AddMatcher::kAddOpcode &&
518 11631 : OwnedByAddressingOperand(right)) {
519 9812 : AddMatcher right_matcher(right);
520 9812 : if (right_matcher.right().HasValue()) {
521 : // (S + (B + D))
522 : base = right_matcher.left().node();
523 : displacement = right_matcher.right().node();
524 : } else {
525 : // (S + (B + B))
526 : base = right;
527 : }
528 294842 : } else if (m.right().HasValue()) {
529 : // (S + D)
530 : displacement = right;
531 : } else {
532 : // (S + B)
533 : base = right;
534 : }
535 : }
536 : } else {
537 : bool match_found = false;
538 15113151 : if (left->opcode() == AddMatcher::kSubOpcode &&
539 4154 : OwnedByAddressingOperand(left)) {
540 2089 : AddMatcher left_matcher(left);
541 : Node* left_left = left_matcher.left().node();
542 : Node* left_right = left_matcher.right().node();
543 2089 : if (left_matcher.right().HasValue()) {
544 4 : if (left_matcher.HasIndexInput() && left_left->OwnedBy(left)) {
545 : // ((S - D) + B)
546 : index = left_matcher.IndexInput();
547 : scale = left_matcher.scale();
548 : scale_expression = left_left;
549 : power_of_two_plus_one = left_matcher.power_of_two_plus_one();
550 : displacement = left_right;
551 : displacement_mode = kNegativeDisplacement;
552 : base = right;
553 : } else {
554 : // ((B - D) + B)
555 : index = left_left;
556 : displacement = left_right;
557 : displacement_mode = kNegativeDisplacement;
558 : base = right;
559 : }
560 : match_found = true;
561 : }
562 : }
563 15108997 : if (!match_found) {
564 15998892 : if (left->opcode() == AddMatcher::kAddOpcode &&
565 890007 : OwnedByAddressingOperand(left)) {
566 549787 : AddMatcher left_matcher(left);
567 : Node* left_left = left_matcher.left().node();
568 : Node* left_right = left_matcher.right().node();
569 822646 : if (left_matcher.HasIndexInput() && left_left->OwnedBy(left)) {
570 253628 : if (left_matcher.right().HasValue()) {
571 : // ((S + D) + B)
572 : index = left_matcher.IndexInput();
573 : scale = left_matcher.scale();
574 : scale_expression = left_left;
575 : power_of_two_plus_one = left_matcher.power_of_two_plus_one();
576 : displacement = left_right;
577 : base = right;
578 11733 : } else if (m.right().HasValue()) {
579 11170 : if (left->OwnedBy(node)) {
580 : // ((S + B) + D)
581 : index = left_matcher.IndexInput();
582 : scale = left_matcher.scale();
583 : scale_expression = left_left;
584 : power_of_two_plus_one = left_matcher.power_of_two_plus_one();
585 : base = left_right;
586 : displacement = right;
587 : } else {
588 : // (B + D)
589 : base = left;
590 : displacement = right;
591 : }
592 : } else {
593 : // (B + B)
594 : index = left;
595 : base = right;
596 : }
597 : } else {
598 296098 : if (left_matcher.right().HasValue()) {
599 : // ((B + D) + B)
600 : index = left_left;
601 : displacement = left_right;
602 : base = right;
603 57676 : } else if (m.right().HasValue()) {
604 36756 : if (left->OwnedBy(node)) {
605 : // ((B + B) + D)
606 : index = left_left;
607 : base = left_right;
608 : displacement = right;
609 : } else {
610 : // (B + D)
611 : base = left;
612 : displacement = right;
613 : }
614 : } else {
615 : // (B + B)
616 : index = left;
617 : base = right;
618 : }
619 : }
620 : } else {
621 14559098 : if (m.right().HasValue()) {
622 : // (B + D)
623 : base = left;
624 : displacement = right;
625 : } else {
626 : // (B + B)
627 : base = left;
628 : index = right;
629 : }
630 : }
631 : }
632 : }
633 : int64_t value = 0;
634 15413616 : if (displacement != nullptr) {
635 14565996 : switch (displacement->opcode()) {
636 : case IrOpcode::kInt32Constant: {
637 4503019 : value = OpParameter<int32_t>(displacement->op());
638 4503019 : break;
639 : }
640 : case IrOpcode::kInt64Constant: {
641 10062977 : value = OpParameter<int64_t>(displacement->op());
642 10062977 : break;
643 : }
644 : default:
645 0 : UNREACHABLE();
646 : break;
647 : }
648 14565996 : if (value == 0) {
649 : displacement = nullptr;
650 : }
651 : }
652 15413616 : if (power_of_two_plus_one) {
653 19469 : if (base != nullptr) {
654 : // If the scale requires explicitly using the index as the base, but a
655 : // base is already part of the match, then the (1 << N + 1) scale factor
656 : // can't be folded into the match and the entire index * scale
657 : // calculation must be computed separately.
658 : index = scale_expression;
659 : scale = 0;
660 : } else {
661 : base = index;
662 : }
663 : }
664 15413616 : if (!(options & AddressOption::kAllowScale) && scale != 0) {
665 : index = scale_expression;
666 : scale = 0;
667 : }
668 15413616 : base_ = base;
669 15413616 : displacement_ = displacement;
670 15413616 : displacement_mode_ = displacement_mode;
671 15413616 : index_ = index;
672 15413616 : scale_ = scale;
673 15413616 : matches_ = true;
674 : }
675 :
676 1223607 : static bool OwnedByAddressingOperand(Node* node) {
677 3568707 : for (auto use : node->use_edges()) {
678 : Node* from = use.from();
679 2702344 : switch (from->opcode()) {
680 : case IrOpcode::kLoad:
681 : case IrOpcode::kPoisonedLoad:
682 : case IrOpcode::kProtectedLoad:
683 : case IrOpcode::kInt32Add:
684 : case IrOpcode::kInt64Add:
685 : // Skip addressing uses.
686 : break;
687 : case IrOpcode::kStore:
688 : case IrOpcode::kProtectedStore:
689 : // If the stored value is this node, it is not an addressing use.
690 281754 : if (from->InputAt(2) == node) return false;
691 : // Otherwise it is used as an address and skipped.
692 : break;
693 : default:
694 : // Non-addressing use found.
695 : return false;
696 : }
697 : }
698 866363 : return true;
699 : }
700 : };
701 :
702 : using BaseWithIndexAndDisplacement32Matcher =
703 : BaseWithIndexAndDisplacementMatcher<Int32AddMatcher>;
704 : using BaseWithIndexAndDisplacement64Matcher =
705 : BaseWithIndexAndDisplacementMatcher<Int64AddMatcher>;
706 :
707 : struct V8_EXPORT_PRIVATE BranchMatcher : public NON_EXPORTED_BASE(NodeMatcher) {
708 : explicit BranchMatcher(Node* branch);
709 :
710 15 : bool Matched() const { return if_true_ && if_false_; }
711 :
712 : Node* Branch() const { return node(); }
713 : Node* IfTrue() const { return if_true_; }
714 : Node* IfFalse() const { return if_false_; }
715 :
716 : private:
717 : Node* if_true_;
718 : Node* if_false_;
719 : };
720 :
721 : struct V8_EXPORT_PRIVATE DiamondMatcher
722 : : public NON_EXPORTED_BASE(NodeMatcher) {
723 : explicit DiamondMatcher(Node* merge);
724 :
725 4 : bool Matched() const { return branch_; }
726 : bool IfProjectionsAreOwned() const {
727 : return if_true_->OwnedBy(node()) && if_false_->OwnedBy(node());
728 : }
729 :
730 : Node* Branch() const { return branch_; }
731 : Node* IfTrue() const { return if_true_; }
732 : Node* IfFalse() const { return if_false_; }
733 : Node* Merge() const { return node(); }
734 :
735 : Node* TrueInputOf(Node* phi) const {
736 : DCHECK(IrOpcode::IsPhiOpcode(phi->opcode()));
737 : DCHECK_EQ(3, phi->InputCount());
738 : DCHECK_EQ(Merge(), phi->InputAt(2));
739 : return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 0 : 1);
740 : }
741 :
742 : Node* FalseInputOf(Node* phi) const {
743 : DCHECK(IrOpcode::IsPhiOpcode(phi->opcode()));
744 : DCHECK_EQ(3, phi->InputCount());
745 : DCHECK_EQ(Merge(), phi->InputAt(2));
746 : return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 1 : 0);
747 : }
748 :
749 : private:
750 : Node* branch_;
751 : Node* if_true_;
752 : Node* if_false_;
753 : };
754 :
755 : template <class BinopMatcher, IrOpcode::Value expected_opcode>
756 : struct WasmStackCheckMatcher {
757 1428563 : explicit WasmStackCheckMatcher(Node* compare) : compare_(compare) {}
758 :
759 1428510 : bool Matched() {
760 2857020 : if (compare_->opcode() != expected_opcode) return false;
761 590779 : BinopMatcher m(compare_);
762 590788 : return MatchedInternal(m.left(), m.right());
763 : }
764 :
765 : private:
766 590722 : bool MatchedInternal(const typename BinopMatcher::LeftMatcher& l,
767 : const typename BinopMatcher::RightMatcher& r) {
768 : // In wasm, the stack check is performed by loading the value given by
769 : // the address of a field stored in the instance object. That object is
770 : // passed as a parameter.
771 720555 : if (l.IsLoad() && r.IsLoadStackPointer()) {
772 129600 : LoadMatcher<LoadMatcher<NodeMatcher>> mleft(l.node());
773 388787 : if (mleft.object().IsLoad() && mleft.index().Is(0) &&
774 : mleft.object().object().IsParameter()) {
775 129607 : return true;
776 : }
777 : }
778 : return false;
779 : }
780 : Node* compare_;
781 : };
782 :
783 : template <class BinopMatcher, IrOpcode::Value expected_opcode>
784 : struct StackCheckMatcher {
785 : StackCheckMatcher(Isolate* isolate, Node* compare)
786 1767372 : : isolate_(isolate), compare_(compare) {
787 : DCHECK_NOT_NULL(isolate);
788 : }
789 1767373 : bool Matched() {
790 : // TODO(jgruber): Ideally, we could be more flexible here and also match the
791 : // same pattern with switched operands (i.e.: left is LoadStackPointer and
792 : // right is the js_stack_limit load). But to be correct in all cases, we'd
793 : // then have to invert the outcome of the stack check comparison.
794 3534746 : if (compare_->opcode() != expected_opcode) return false;
795 970761 : BinopMatcher m(compare_);
796 970759 : return MatchedInternal(m.left(), m.right());
797 : }
798 :
799 : private:
800 970757 : bool MatchedInternal(const typename BinopMatcher::LeftMatcher& l,
801 : const typename BinopMatcher::RightMatcher& r) {
802 1534188 : if (l.IsLoad() && r.IsLoadStackPointer()) {
803 563175 : LoadMatcher<ExternalReferenceMatcher> mleft(l.node());
804 : ExternalReference js_stack_limit =
805 563170 : ExternalReference::address_of_stack_limit(isolate_);
806 1126349 : if (mleft.object().Is(js_stack_limit) && mleft.index().Is(0)) return true;
807 : }
808 : return false;
809 : }
810 :
811 : Isolate* isolate_;
812 : Node* compare_;
813 : };
814 :
815 : } // namespace compiler
816 : } // namespace internal
817 : } // namespace v8
818 :
819 : #endif // V8_COMPILER_NODE_MATCHERS_H_
|
