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 155344087 : explicit NodeMatcher(Node* node) : node_(node) {}
27 :
28 90689827 : Node* node() const { return node_; }
29 33228206 : const Operator* op() const { return node()->op(); }
30 158168667 : 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 740 : 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 : typedef T ValueType;
55 :
56 10104782 : explicit ValueMatcher(Node* node)
57 51183706 : : NodeMatcher(node), value_(), has_value_(opcode() == kOpcode) {
58 34760205 : if (has_value_) {
59 12743343 : 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 711873 : Node* node)
78 : : NodeMatcher(node),
79 : value_(),
80 3591315 : has_value_(opcode() == IrOpcode::kInt32Constant) {
81 2259635 : if (has_value_) {
82 1226891 : 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 75709909 : : NodeMatcher(node), value_(), has_value_(false) {
90 83302237 : if (opcode() == IrOpcode::kInt32Constant) {
91 6686015 : value_ = OpParameter<int32_t>(node->op());
92 6450050 : has_value_ = true;
93 76616222 : } else if (opcode() == IrOpcode::kInt64Constant) {
94 26216761 : value_ = OpParameter<int64_t>(node->op());
95 24241987 : has_value_ = true;
96 : }
97 : }
98 :
99 :
100 : template <>
101 : inline ValueMatcher<uint64_t, IrOpcode::kInt64Constant>::ValueMatcher(
102 : Node* node)
103 95704 : : NodeMatcher(node), value_(), has_value_(false) {
104 156274 : if (opcode() == IrOpcode::kInt32Constant) {
105 5 : value_ = static_cast<uint32_t>(OpParameter<int32_t>(node->op()));
106 5 : has_value_ = true;
107 156269 : } else if (opcode() == IrOpcode::kInt64Constant) {
108 129140 : value_ = static_cast<uint64_t>(OpParameter<int64_t>(node->op()));
109 73762 : 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 12813522 : return this->HasValue() && this->Value() == value;
121 : }
122 : bool IsInRange(const T& low, const T& high) const {
123 727831 : return this->HasValue() && low <= this->Value() && this->Value() <= high;
124 : }
125 : bool IsMultipleOf(T n) const {
126 16797 : return this->HasValue() && (this->Value() % n) == 0;
127 : }
128 : bool IsPowerOf2() const {
129 : return this->HasValue() && this->Value() > 0 &&
130 26002 : (this->Value() & (this->Value() - 1)) == 0;
131 : }
132 : bool IsNegativePowerOf2() const {
133 601283 : return this->HasValue() && this->Value() < 0 &&
134 : ((this->Value() == kMinInt) ||
135 601283 : (-this->Value() & (-this->Value() - 1)) == 0);
136 : }
137 3462 : bool IsNegative() const { return this->HasValue() && this->Value() < 0; }
138 : };
139 :
140 : typedef IntMatcher<int32_t, IrOpcode::kInt32Constant> Int32Matcher;
141 : typedef IntMatcher<uint32_t, IrOpcode::kInt32Constant> Uint32Matcher;
142 : typedef IntMatcher<int64_t, IrOpcode::kInt64Constant> Int64Matcher;
143 : typedef IntMatcher<uint64_t, IrOpcode::kInt64Constant> Uint64Matcher;
144 : #if V8_HOST_ARCH_32_BIT
145 : typedef Int32Matcher IntPtrMatcher;
146 : typedef Uint32Matcher UintPtrMatcher;
147 : #else
148 : typedef Int64Matcher IntPtrMatcher;
149 : typedef Uint64Matcher UintPtrMatcher;
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 336061 : return this->HasValue() && this->Value() == value;
160 : }
161 : bool IsInRange(const T& low, const T& high) const {
162 2227 : return this->HasValue() && low <= this->Value() && this->Value() <= high;
163 : }
164 23543 : bool IsMinusZero() const {
165 32069 : return this->Is(0.0) && std::signbit(this->Value());
166 : }
167 : bool IsNegative() const { return this->HasValue() && this->Value() < 0.0; }
168 305256 : 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 36482 : return this->HasValue() && std::isnormal(this->Value());
172 : }
173 : bool IsInteger() const {
174 6962 : return this->HasValue() && std::nearbyint(this->Value()) == this->Value();
175 : }
176 9396 : bool IsPositiveOrNegativePowerOf2() const {
177 9396 : if (!this->HasValue() || (this->Value() == 0.0)) {
178 : return false;
179 : }
180 9396 : Double value = Double(this->Value());
181 18792 : return !value.IsInfinite() && base::bits::IsPowerOfTwo(value.Significand());
182 : }
183 : };
184 :
185 : typedef FloatMatcher<float, IrOpcode::kFloat32Constant> Float32Matcher;
186 : typedef FloatMatcher<double, IrOpcode::kFloat64Constant> Float64Matcher;
187 : typedef FloatMatcher<double, IrOpcode::kNumberConstant> NumberMatcher;
188 :
189 :
190 : // A pattern matcher for heap object constants.
191 : struct HeapObjectMatcher final
192 : : public ValueMatcher<Handle<HeapObject>, IrOpcode::kHeapConstant> {
193 : explicit HeapObjectMatcher(Node* node)
194 : : ValueMatcher<Handle<HeapObject>, IrOpcode::kHeapConstant>(node) {}
195 :
196 242129 : bool Is(Handle<HeapObject> const& value) const {
197 415358 : return this->HasValue() && this->Value().address() == value.address();
198 : }
199 :
200 : ObjectRef Ref(JSHeapBroker* broker) const {
201 1050090 : return ObjectRef(broker, this->Value());
202 : }
203 : };
204 :
205 :
206 : // A pattern matcher for external reference constants.
207 : struct ExternalReferenceMatcher final
208 : : public ValueMatcher<ExternalReference, IrOpcode::kExternalConstant> {
209 : explicit ExternalReferenceMatcher(Node* node)
210 : : ValueMatcher<ExternalReference, IrOpcode::kExternalConstant>(node) {}
211 : bool Is(const ExternalReference& value) const {
212 554400 : return this->HasValue() && this->Value() == value;
213 : }
214 : };
215 :
216 :
217 : // For shorter pattern matching code, this struct matches the inputs to
218 : // machine-level load operations.
219 : template <typename Object>
220 : struct LoadMatcher : public NodeMatcher {
221 3840857 : explicit LoadMatcher(Node* node)
222 3862605 : : NodeMatcher(node), object_(InputAt(0)), index_(InputAt(1)) {}
223 :
224 : typedef Object ObjectMatcher;
225 :
226 : Object const& object() const { return object_; }
227 : IntPtrMatcher const& index() const { return index_; }
228 :
229 : private:
230 : Object const object_;
231 : IntPtrMatcher const index_;
232 : };
233 :
234 :
235 : // For shorter pattern matching code, this struct matches both the left and
236 : // right hand sides of a binary operation and can put constants on the right
237 : // if they appear on the left hand side of a commutative operation.
238 : template <typename Left, typename Right>
239 : struct BinopMatcher : public NodeMatcher {
240 33228206 : explicit BinopMatcher(Node* node)
241 : : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) {
242 33228206 : if (HasProperty(Operator::kCommutative)) PutConstantOnRight();
243 33228186 : }
244 14409757 : BinopMatcher(Node* node, bool allow_input_swap)
245 : : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) {
246 14409757 : if (allow_input_swap) PutConstantOnRight();
247 14409782 : }
248 :
249 : typedef Left LeftMatcher;
250 : typedef Right RightMatcher;
251 :
252 : const Left& left() const { return left_; }
253 : const Right& right() const { return right_; }
254 :
255 9019518 : bool IsFoldable() const { return left().HasValue() && right().HasValue(); }
256 : bool LeftEqualsRight() const { return left().node() == right().node(); }
257 :
258 : protected:
259 744177 : void SwapInputs() {
260 : std::swap(left_, right_);
261 : // TODO(tebbi): This modification should notify the reducers using
262 : // BinopMatcher. Alternatively, all reducers (especially value numbering)
263 : // could ignore the ordering for commutative binops.
264 744177 : node()->ReplaceInput(0, left().node());
265 744183 : node()->ReplaceInput(1, right().node());
266 744181 : }
267 :
268 : private:
269 29922709 : void PutConstantOnRight() {
270 29922709 : if (left().HasValue() && !right().HasValue()) {
271 302650 : SwapInputs();
272 : }
273 29922710 : }
274 :
275 : Left left_;
276 : Right right_;
277 : };
278 :
279 : typedef BinopMatcher<Int32Matcher, Int32Matcher> Int32BinopMatcher;
280 : typedef BinopMatcher<Uint32Matcher, Uint32Matcher> Uint32BinopMatcher;
281 : typedef BinopMatcher<Int64Matcher, Int64Matcher> Int64BinopMatcher;
282 : typedef BinopMatcher<Uint64Matcher, Uint64Matcher> Uint64BinopMatcher;
283 : typedef BinopMatcher<IntPtrMatcher, IntPtrMatcher> IntPtrBinopMatcher;
284 : typedef BinopMatcher<UintPtrMatcher, UintPtrMatcher> UintPtrBinopMatcher;
285 : typedef BinopMatcher<Float32Matcher, Float32Matcher> Float32BinopMatcher;
286 : typedef BinopMatcher<Float64Matcher, Float64Matcher> Float64BinopMatcher;
287 : typedef BinopMatcher<NumberMatcher, NumberMatcher> NumberBinopMatcher;
288 : typedef BinopMatcher<HeapObjectMatcher, HeapObjectMatcher>
289 : HeapObjectBinopMatcher;
290 :
291 : template <class BinopMatcher, IrOpcode::Value kMulOpcode,
292 : IrOpcode::Value kShiftOpcode>
293 : struct ScaleMatcher {
294 40518973 : explicit ScaleMatcher(Node* node, bool allow_power_of_two_plus_one = false)
295 28755766 : : scale_(-1), power_of_two_plus_one_(false) {
296 45748342 : if (node->InputCount() < 2) return;
297 11763190 : BinopMatcher m(node);
298 11763207 : if (node->opcode() == kShiftOpcode) {
299 1105540 : if (m.right().HasValue()) {
300 : typename BinopMatcher::RightMatcher::ValueType value =
301 1097804 : m.right().Value();
302 1097804 : if (value >= 0 && value <= 3) {
303 689043 : scale_ = static_cast<int>(value);
304 : }
305 : }
306 10657667 : } else if (node->opcode() == kMulOpcode) {
307 171908 : if (m.right().HasValue()) {
308 : typename BinopMatcher::RightMatcher::ValueType value =
309 166046 : m.right().Value();
310 166046 : if (value == 1) {
311 2101 : scale_ = 0;
312 163945 : } else if (value == 2) {
313 1974 : scale_ = 1;
314 161971 : } else if (value == 4) {
315 927 : scale_ = 2;
316 161044 : } else if (value == 8) {
317 2078 : scale_ = 3;
318 158966 : } else if (allow_power_of_two_plus_one) {
319 158966 : if (value == 3) {
320 72583 : scale_ = 1;
321 72583 : power_of_two_plus_one_ = true;
322 86383 : } else if (value == 5) {
323 4197 : scale_ = 2;
324 4197 : power_of_two_plus_one_ = true;
325 82186 : } else if (value == 9) {
326 1022 : scale_ = 3;
327 1022 : power_of_two_plus_one_ = true;
328 : }
329 : }
330 : }
331 : }
332 : }
333 :
334 : bool matches() const { return scale_ != -1; }
335 : int scale() const { return scale_; }
336 : bool power_of_two_plus_one() const { return power_of_two_plus_one_; }
337 :
338 : private:
339 : int scale_;
340 : bool power_of_two_plus_one_;
341 : };
342 :
343 : typedef ScaleMatcher<Int32BinopMatcher, IrOpcode::kInt32Mul,
344 : IrOpcode::kWord32Shl> Int32ScaleMatcher;
345 : typedef ScaleMatcher<Int64BinopMatcher, IrOpcode::kInt64Mul,
346 : IrOpcode::kWord64Shl> Int64ScaleMatcher;
347 :
348 : template <class BinopMatcher, IrOpcode::Value AddOpcode,
349 : IrOpcode::Value SubOpcode, IrOpcode::Value kMulOpcode,
350 : IrOpcode::Value kShiftOpcode>
351 : struct AddMatcher : public BinopMatcher {
352 : static const IrOpcode::Value kAddOpcode = AddOpcode;
353 : static const IrOpcode::Value kSubOpcode = SubOpcode;
354 : typedef ScaleMatcher<BinopMatcher, kMulOpcode, kShiftOpcode> Matcher;
355 :
356 13784508 : AddMatcher(Node* node, bool allow_input_swap)
357 : : BinopMatcher(node, allow_input_swap),
358 : scale_(-1),
359 13784508 : power_of_two_plus_one_(false) {
360 13784570 : Initialize(node, allow_input_swap);
361 13784618 : }
362 1250476 : explicit AddMatcher(Node* node)
363 : : BinopMatcher(node, node->op()->HasProperty(Operator::kCommutative)),
364 : scale_(-1),
365 625249 : power_of_two_plus_one_(false) {
366 625227 : Initialize(node, node->op()->HasProperty(Operator::kCommutative));
367 625240 : }
368 :
369 : bool HasIndexInput() const { return scale_ != -1; }
370 : Node* IndexInput() const {
371 : DCHECK(HasIndexInput());
372 : return this->left().node()->InputAt(0);
373 : }
374 : int scale() const {
375 : DCHECK(HasIndexInput());
376 : return scale_;
377 : }
378 : bool power_of_two_plus_one() const { return power_of_two_plus_one_; }
379 :
380 : private:
381 14409797 : void Initialize(Node* node, bool allow_input_swap) {
382 14409797 : Matcher left_matcher(this->left().node(), true);
383 14409808 : if (left_matcher.matches()) {
384 604923 : scale_ = left_matcher.scale();
385 604923 : power_of_two_plus_one_ = left_matcher.power_of_two_plus_one();
386 1309347 : return;
387 : }
388 :
389 13804885 : if (!allow_input_swap) {
390 : return;
391 : }
392 :
393 13795882 : Matcher right_matcher(this->right().node(), true);
394 13795849 : if (right_matcher.matches()) {
395 90498 : scale_ = right_matcher.scale();
396 90498 : power_of_two_plus_one_ = right_matcher.power_of_two_plus_one();
397 90498 : this->SwapInputs();
398 90498 : return;
399 : }
400 :
401 26740616 : if ((this->left().opcode() != kSubOpcode &&
402 : this->left().opcode() != kAddOpcode) &&
403 : (this->right().opcode() == kAddOpcode ||
404 : this->right().opcode() == kSubOpcode)) {
405 351032 : this->SwapInputs();
406 : }
407 : }
408 :
409 : int scale_;
410 : bool power_of_two_plus_one_;
411 : };
412 :
413 : typedef AddMatcher<Int32BinopMatcher, IrOpcode::kInt32Add, IrOpcode::kInt32Sub,
414 : IrOpcode::kInt32Mul, IrOpcode::kWord32Shl>
415 : Int32AddMatcher;
416 : typedef AddMatcher<Int64BinopMatcher, IrOpcode::kInt64Add, IrOpcode::kInt64Sub,
417 : IrOpcode::kInt64Mul, IrOpcode::kWord64Shl>
418 : Int64AddMatcher;
419 :
420 : enum DisplacementMode { kPositiveDisplacement, kNegativeDisplacement };
421 :
422 : enum class AddressOption : uint8_t {
423 : kAllowNone = 0u,
424 : kAllowInputSwap = 1u << 0,
425 : kAllowScale = 1u << 1,
426 : kAllowAll = kAllowInputSwap | kAllowScale
427 : };
428 :
429 : typedef base::Flags<AddressOption, uint8_t> AddressOptions;
430 : DEFINE_OPERATORS_FOR_FLAGS(AddressOptions);
431 :
432 : template <class AddMatcher>
433 : struct BaseWithIndexAndDisplacementMatcher {
434 : BaseWithIndexAndDisplacementMatcher(Node* node, AddressOptions options)
435 : : matches_(false),
436 : index_(nullptr),
437 : scale_(0),
438 : base_(nullptr),
439 : displacement_(nullptr),
440 11348255 : displacement_mode_(kPositiveDisplacement) {
441 11348255 : Initialize(node, options);
442 : }
443 :
444 4872584 : explicit BaseWithIndexAndDisplacementMatcher(Node* node)
445 : : matches_(false),
446 : index_(nullptr),
447 : scale_(0),
448 : base_(nullptr),
449 : displacement_(nullptr),
450 2436292 : displacement_mode_(kPositiveDisplacement) {
451 2436292 : Initialize(node, AddressOption::kAllowScale |
452 : (node->op()->HasProperty(Operator::kCommutative)
453 : ? AddressOption::kAllowInputSwap
454 2436292 : : AddressOption::kAllowNone));
455 2436350 : }
456 :
457 : bool matches() const { return matches_; }
458 : Node* index() const { return index_; }
459 : int scale() const { return scale_; }
460 : Node* base() const { return base_; }
461 : Node* displacement() const { return displacement_; }
462 : DisplacementMode displacement_mode() const { return displacement_mode_; }
463 :
464 : private:
465 : bool matches_;
466 : Node* index_;
467 : int scale_;
468 : Node* base_;
469 : Node* displacement_;
470 : DisplacementMode displacement_mode_;
471 :
472 13784509 : void Initialize(Node* node, AddressOptions options) {
473 : // The BaseWithIndexAndDisplacementMatcher canonicalizes the order of
474 : // displacements and scale factors that are used as inputs, so instead of
475 : // enumerating all possible patterns by brute force, checking for node
476 : // clusters using the following templates in the following order suffices to
477 : // find all of the interesting cases (S = index * scale, B = base input, D =
478 : // displacement input):
479 : // (S + (B + D))
480 : // (S + (B + B))
481 : // (S + D)
482 : // (S + B)
483 : // ((S + D) + B)
484 : // ((S + B) + D)
485 : // ((B + D) + B)
486 : // ((B + B) + D)
487 : // (B + D)
488 : // (B + B)
489 13784511 : if (node->InputCount() < 2) return;
490 13784507 : AddMatcher m(node, options & AddressOption::kAllowInputSwap);
491 26901204 : Node* left = m.left().node();
492 710846 : Node* right = m.right().node();
493 12858347 : Node* displacement = nullptr;
494 : Node* base = nullptr;
495 : Node* index = nullptr;
496 : Node* scale_expression = nullptr;
497 : bool power_of_two_plus_one = false;
498 : DisplacementMode displacement_mode = kPositiveDisplacement;
499 : int scale = 0;
500 13784632 : if (m.HasIndexInput() && OwnedByAddressingOperand(left)) {
501 : index = m.IndexInput();
502 : scale = m.scale();
503 : scale_expression = left;
504 355427 : power_of_two_plus_one = m.power_of_two_plus_one();
505 : bool match_found = false;
506 355439 : if (right->opcode() == AddMatcher::kSubOpcode &&
507 12 : OwnedByAddressingOperand(right)) {
508 8 : AddMatcher right_matcher(right);
509 8 : if (right_matcher.right().HasValue()) {
510 : // (S + (B - D))
511 : base = right_matcher.left().node();
512 : displacement = right_matcher.right().node();
513 : displacement_mode = kNegativeDisplacement;
514 : match_found = true;
515 : }
516 : }
517 355427 : if (!match_found) {
518 367465 : if (right->opcode() == AddMatcher::kAddOpcode &&
519 12046 : OwnedByAddressingOperand(right)) {
520 10225 : AddMatcher right_matcher(right);
521 10225 : if (right_matcher.right().HasValue()) {
522 : // (S + (B + D))
523 : base = right_matcher.left().node();
524 : displacement = right_matcher.right().node();
525 : } else {
526 : // (S + (B + B))
527 : base = right;
528 : }
529 345194 : } else if (m.right().HasValue()) {
530 : // (S + D)
531 : displacement = right;
532 : } else {
533 : // (S + B)
534 : base = right;
535 : }
536 : }
537 : } else {
538 : bool match_found = false;
539 13433629 : if (left->opcode() == AddMatcher::kSubOpcode &&
540 4424 : OwnedByAddressingOperand(left)) {
541 2266 : AddMatcher left_matcher(left);
542 0 : Node* left_left = left_matcher.left().node();
543 : Node* left_right = left_matcher.right().node();
544 2266 : if (left_matcher.right().HasValue()) {
545 4 : if (left_matcher.HasIndexInput() && left_left->OwnedBy(left)) {
546 : // ((S - D) + B)
547 : index = left_matcher.IndexInput();
548 : scale = left_matcher.scale();
549 : scale_expression = left_left;
550 0 : power_of_two_plus_one = left_matcher.power_of_two_plus_one();
551 : displacement = left_right;
552 : displacement_mode = kNegativeDisplacement;
553 : base = right;
554 : } else {
555 : // ((B - D) + B)
556 : index = left_left;
557 : displacement = left_right;
558 : displacement_mode = kNegativeDisplacement;
559 : base = right;
560 : }
561 : match_found = true;
562 : }
563 : }
564 13429205 : if (!match_found) {
565 14383565 : if (left->opcode() == AddMatcher::kAddOpcode &&
566 954394 : OwnedByAddressingOperand(left)) {
567 612766 : AddMatcher left_matcher(left);
568 324302 : Node* left_left = left_matcher.left().node();
569 : Node* left_right = left_matcher.right().node();
570 937026 : if (left_matcher.HasIndexInput() && left_left->OwnedBy(left)) {
571 309435 : if (left_matcher.right().HasValue()) {
572 : // ((S + D) + B)
573 : index = left_matcher.IndexInput();
574 : scale = left_matcher.scale();
575 : scale_expression = left_left;
576 297484 : power_of_two_plus_one = left_matcher.power_of_two_plus_one();
577 : displacement = left_right;
578 : base = right;
579 11951 : } else if (m.right().HasValue()) {
580 11239 : if (left->OwnedBy(node)) {
581 : // ((S + B) + D)
582 : index = left_matcher.IndexInput();
583 : scale = left_matcher.scale();
584 : scale_expression = left_left;
585 2799 : power_of_two_plus_one = left_matcher.power_of_two_plus_one();
586 : base = left_right;
587 : displacement = right;
588 : } else {
589 : // (B + D)
590 : base = left;
591 : displacement = right;
592 : }
593 : } else {
594 : // (B + B)
595 : index = left;
596 : base = right;
597 : }
598 : } else {
599 303289 : if (left_matcher.right().HasValue()) {
600 : // ((B + D) + B)
601 : index = left_left;
602 : displacement = left_right;
603 : base = right;
604 62986 : } else if (m.right().HasValue()) {
605 31615 : if (left->OwnedBy(node)) {
606 : // ((B + B) + D)
607 : index = left_left;
608 : base = left_right;
609 : displacement = right;
610 : } else {
611 : // (B + D)
612 : base = left;
613 : displacement = right;
614 : }
615 : } else {
616 : // (B + B)
617 : index = left;
618 : base = right;
619 : }
620 : }
621 : } else {
622 12816405 : if (m.right().HasValue()) {
623 : // (B + D)
624 : base = left;
625 : displacement = right;
626 : } else {
627 : // (B + B)
628 : base = left;
629 : index = right;
630 : }
631 : }
632 : }
633 : }
634 : int64_t value = 0;
635 13784620 : if (displacement != nullptr) {
636 12858347 : switch (displacement->opcode()) {
637 : case IrOpcode::kInt32Constant: {
638 3710873 : value = OpParameter<int32_t>(displacement->op());
639 3710873 : break;
640 : }
641 : case IrOpcode::kInt64Constant: {
642 9147474 : value = OpParameter<int64_t>(displacement->op());
643 9147474 : break;
644 : }
645 : default:
646 0 : UNREACHABLE();
647 : break;
648 : }
649 12858347 : if (value == 0) {
650 : displacement = nullptr;
651 : }
652 : }
653 13784620 : if (power_of_two_plus_one) {
654 52369 : if (base != nullptr) {
655 : // If the scale requires explicitly using the index as the base, but a
656 : // base is already part of the match, then the (1 << N + 1) scale factor
657 : // can't be folded into the match and the entire index * scale
658 : // calculation must be computed separately.
659 : index = scale_expression;
660 : scale = 0;
661 : } else {
662 : base = index;
663 : }
664 : }
665 13784620 : if (!(options & AddressOption::kAllowScale) && scale != 0) {
666 : index = scale_expression;
667 : scale = 0;
668 : }
669 13784620 : base_ = base;
670 13784620 : displacement_ = displacement;
671 13784620 : displacement_mode_ = displacement_mode;
672 13784620 : index_ = index;
673 13784620 : scale_ = scale;
674 13784620 : matches_ = true;
675 : }
676 :
677 1340196 : static bool OwnedByAddressingOperand(Node* node) {
678 5218341 : for (auto use : node->use_edges()) {
679 2897462 : Node* from = use.from();
680 2897462 : switch (from->opcode()) {
681 : case IrOpcode::kLoad:
682 : case IrOpcode::kPoisonedLoad:
683 : case IrOpcode::kProtectedLoad:
684 : case IrOpcode::kInt32Add:
685 : case IrOpcode::kInt64Add:
686 : // Skip addressing uses.
687 : break;
688 : case IrOpcode::kStore:
689 : case IrOpcode::kProtectedStore:
690 : // If the stored value is this node, it is not an addressing use.
691 285605 : if (from->InputAt(2) == node) return false;
692 : // Otherwise it is used as an address and skipped.
693 : break;
694 : default:
695 : // Non-addressing use found.
696 : return false;
697 : }
698 : }
699 980683 : return true;
700 : }
701 : };
702 :
703 : typedef BaseWithIndexAndDisplacementMatcher<Int32AddMatcher>
704 : BaseWithIndexAndDisplacement32Matcher;
705 : typedef BaseWithIndexAndDisplacementMatcher<Int64AddMatcher>
706 : BaseWithIndexAndDisplacement64Matcher;
707 :
708 : struct V8_EXPORT_PRIVATE BranchMatcher : public NON_EXPORTED_BASE(NodeMatcher) {
709 : explicit BranchMatcher(Node* branch);
710 :
711 15 : bool Matched() const { return if_true_ && if_false_; }
712 :
713 : Node* Branch() const { return node(); }
714 : Node* IfTrue() const { return if_true_; }
715 : Node* IfFalse() const { return if_false_; }
716 :
717 : private:
718 : Node* if_true_;
719 : Node* if_false_;
720 : };
721 :
722 : struct V8_EXPORT_PRIVATE DiamondMatcher
723 : : public NON_EXPORTED_BASE(NodeMatcher) {
724 : explicit DiamondMatcher(Node* merge);
725 :
726 4 : bool Matched() const { return branch_; }
727 : bool IfProjectionsAreOwned() const {
728 : return if_true_->OwnedBy(node()) && if_false_->OwnedBy(node());
729 : }
730 :
731 : Node* Branch() const { return branch_; }
732 : Node* IfTrue() const { return if_true_; }
733 : Node* IfFalse() const { return if_false_; }
734 : Node* Merge() const { return node(); }
735 :
736 : Node* TrueInputOf(Node* phi) const {
737 : DCHECK(IrOpcode::IsPhiOpcode(phi->opcode()));
738 : DCHECK_EQ(3, phi->InputCount());
739 : DCHECK_EQ(Merge(), phi->InputAt(2));
740 : return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 0 : 1);
741 : }
742 :
743 : Node* FalseInputOf(Node* phi) const {
744 : DCHECK(IrOpcode::IsPhiOpcode(phi->opcode()));
745 : DCHECK_EQ(3, phi->InputCount());
746 : DCHECK_EQ(Merge(), phi->InputAt(2));
747 : return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 1 : 0);
748 : }
749 :
750 : private:
751 : Node* branch_;
752 : Node* if_true_;
753 : Node* if_false_;
754 : };
755 :
756 : template <class BinopMatcher, IrOpcode::Value expected_opcode>
757 : struct WasmStackCheckMatcher {
758 1301773 : explicit WasmStackCheckMatcher(Node* compare) : compare_(compare) {}
759 :
760 1301780 : bool Matched() {
761 2603560 : if (compare_->opcode() != expected_opcode) return false;
762 382677 : BinopMatcher m(compare_);
763 382683 : return MatchedInternal(m.left(), m.right());
764 : }
765 :
766 : private:
767 382673 : bool MatchedInternal(const typename BinopMatcher::LeftMatcher& l,
768 : const typename BinopMatcher::RightMatcher& r) {
769 : // In wasm, the stack check is performed by loading the value given by
770 : // the address of a field stored in the instance object. That object is
771 : // passed as a parameter.
772 404458 : if (l.IsLoad() && r.IsLoadStackPointer()) {
773 21749 : LoadMatcher<LoadMatcher<NodeMatcher>> mleft(l.node());
774 65252 : if (mleft.object().IsLoad() && mleft.index().Is(0) &&
775 : mleft.object().object().IsParameter()) {
776 21751 : return true;
777 : }
778 : }
779 : return false;
780 : }
781 : Node* compare_;
782 : };
783 :
784 : template <class BinopMatcher, IrOpcode::Value expected_opcode>
785 : struct StackCheckMatcher {
786 : StackCheckMatcher(Isolate* isolate, Node* compare)
787 1761163 : : isolate_(isolate), compare_(compare) {
788 : DCHECK_NOT_NULL(isolate);
789 : }
790 1761152 : bool Matched() {
791 : // TODO(jgruber): Ideally, we could be more flexible here and also match the
792 : // same pattern with switched operands (i.e.: left is LoadStackPointer and
793 : // right is the js_stack_limit load). But to be correct in all cases, we'd
794 : // then have to invert the outcome of the stack check comparison.
795 3522304 : if (compare_->opcode() != expected_opcode) return false;
796 853618 : BinopMatcher m(compare_);
797 853602 : return MatchedInternal(m.left(), m.right());
798 : }
799 :
800 : private:
801 853601 : bool MatchedInternal(const typename BinopMatcher::LeftMatcher& l,
802 : const typename BinopMatcher::RightMatcher& r) {
803 1408048 : if (l.IsLoad() && r.IsLoadStackPointer()) {
804 554419 : LoadMatcher<ExternalReferenceMatcher> mleft(l.node());
805 : ExternalReference js_stack_limit =
806 554417 : ExternalReference::address_of_stack_limit(isolate_);
807 1108828 : if (mleft.object().Is(js_stack_limit) && mleft.index().Is(0)) return true;
808 : }
809 : return false;
810 : }
811 :
812 : Isolate* isolate_;
813 : Node* compare_;
814 : };
815 :
816 : } // namespace compiler
817 : } // namespace internal
818 : } // namespace v8
819 :
820 : #endif // V8_COMPILER_NODE_MATCHERS_H_
|
