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
15namespace v8 {
16namespace internal {
17namespace compiler {
18
19// A pattern matcher for nodes.
20struct 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.
47template <typename T, IrOpcode::Value kOpcode>
48struct 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
70template <>
71inline 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
82template <>
83inline 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
95template <>
96inline 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.
110template <typename T, IrOpcode::Value kOpcode>
111struct 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
133typedef IntMatcher<int32_t, IrOpcode::kInt32Constant> Int32Matcher;
134typedef IntMatcher<uint32_t, IrOpcode::kInt32Constant> Uint32Matcher;
135typedef IntMatcher<int64_t, IrOpcode::kInt64Constant> Int64Matcher;
136typedef IntMatcher<uint64_t, IrOpcode::kInt64Constant> Uint64Matcher;
137#if V8_HOST_ARCH_32_BIT
138typedef Int32Matcher IntPtrMatcher;
139typedef Uint32Matcher UintPtrMatcher;
140#else
141typedef Int64Matcher IntPtrMatcher;
142typedef Uint64Matcher UintPtrMatcher;
143#endif
144
145
146// A pattern matcher for floating point constants.
147template <typename T, IrOpcode::Value kOpcode>
148struct 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
164typedef FloatMatcher<float, IrOpcode::kFloat32Constant> Float32Matcher;
165typedef FloatMatcher<double, IrOpcode::kFloat64Constant> Float64Matcher;
166typedef FloatMatcher<double, IrOpcode::kNumberConstant> NumberMatcher;
167
168
169// A pattern matcher for heap object constants.
170struct 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.
178struct 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.
190template <typename Object>
191struct 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.
209template <typename Left, typename Right>
210struct 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
247typedef BinopMatcher<Int32Matcher, Int32Matcher> Int32BinopMatcher;
248typedef BinopMatcher<Uint32Matcher, Uint32Matcher> Uint32BinopMatcher;
249typedef BinopMatcher<Int64Matcher, Int64Matcher> Int64BinopMatcher;
250typedef BinopMatcher<Uint64Matcher, Uint64Matcher> Uint64BinopMatcher;
251typedef BinopMatcher<IntPtrMatcher, IntPtrMatcher> IntPtrBinopMatcher;
252typedef BinopMatcher<UintPtrMatcher, UintPtrMatcher> UintPtrBinopMatcher;
253typedef BinopMatcher<Float32Matcher, Float32Matcher> Float32BinopMatcher;
254typedef BinopMatcher<Float64Matcher, Float64Matcher> Float64BinopMatcher;
255typedef BinopMatcher<NumberMatcher, NumberMatcher> NumberBinopMatcher;
256
257
258template <class BinopMatcher, IrOpcode::Value kMulOpcode,
259          IrOpcode::Value kShiftOpcode>
260struct ScaleMatcher {
261  explicit ScaleMatcher(Node* node, bool allow_power_of_two_plus_one = false)
262      : scale_(-1), power_of_two_plus_one_(false) {
263    if (node->InputCount() < 2) return;
264    BinopMatcher m(node);
265    if (node->opcode() == kShiftOpcode) {
266      if (m.right().HasValue()) {
267        typename BinopMatcher::RightMatcher::ValueType value =
268            m.right().Value();
269        if (value >= 0 && value <= 3) {
270          scale_ = static_cast<int>(value);
271        }
272      }
273    } else if (node->opcode() == kMulOpcode) {
274      if (m.right().HasValue()) {
275        typename BinopMatcher::RightMatcher::ValueType value =
276            m.right().Value();
277        if (value == 1) {
278          scale_ = 0;
279        } else if (value == 2) {
280          scale_ = 1;
281        } else if (value == 4) {
282          scale_ = 2;
283        } else if (value == 8) {
284          scale_ = 3;
285        } else if (allow_power_of_two_plus_one) {
286          if (value == 3) {
287            scale_ = 1;
288            power_of_two_plus_one_ = true;
289          } else if (value == 5) {
290            scale_ = 2;
291            power_of_two_plus_one_ = true;
292          } else if (value == 9) {
293            scale_ = 3;
294            power_of_two_plus_one_ = true;
295          }
296        }
297      }
298    }
299  }
300
301  bool matches() const { return scale_ != -1; }
302  int scale() const { return scale_; }
303  bool power_of_two_plus_one() const { return power_of_two_plus_one_; }
304
305 private:
306  int scale_;
307  bool power_of_two_plus_one_;
308};
309
310typedef ScaleMatcher<Int32BinopMatcher, IrOpcode::kInt32Mul,
311                     IrOpcode::kWord32Shl> Int32ScaleMatcher;
312typedef ScaleMatcher<Int64BinopMatcher, IrOpcode::kInt64Mul,
313                     IrOpcode::kWord64Shl> Int64ScaleMatcher;
314
315
316template <class BinopMatcher, IrOpcode::Value kAddOpcode,
317          IrOpcode::Value kMulOpcode, IrOpcode::Value kShiftOpcode>
318struct AddMatcher : public BinopMatcher {
319  static const IrOpcode::Value kOpcode = kAddOpcode;
320  typedef ScaleMatcher<BinopMatcher, kMulOpcode, kShiftOpcode> Matcher;
321
322  AddMatcher(Node* node, bool allow_input_swap)
323      : BinopMatcher(node, allow_input_swap),
324        scale_(-1),
325        power_of_two_plus_one_(false) {
326    Initialize(node, allow_input_swap);
327  }
328  explicit AddMatcher(Node* node)
329      : BinopMatcher(node, node->op()->HasProperty(Operator::kCommutative)),
330        scale_(-1),
331        power_of_two_plus_one_(false) {
332    Initialize(node, node->op()->HasProperty(Operator::kCommutative));
333  }
334
335  bool HasIndexInput() const { return scale_ != -1; }
336  Node* IndexInput() const {
337    DCHECK(HasIndexInput());
338    return this->left().node()->InputAt(0);
339  }
340  int scale() const {
341    DCHECK(HasIndexInput());
342    return scale_;
343  }
344  bool power_of_two_plus_one() const { return power_of_two_plus_one_; }
345
346 private:
347  void Initialize(Node* node, bool allow_input_swap) {
348    Matcher left_matcher(this->left().node(), true);
349    if (left_matcher.matches()) {
350      scale_ = left_matcher.scale();
351      power_of_two_plus_one_ = left_matcher.power_of_two_plus_one();
352      return;
353    }
354
355    if (!allow_input_swap) {
356      return;
357    }
358
359    Matcher right_matcher(this->right().node(), true);
360    if (right_matcher.matches()) {
361      scale_ = right_matcher.scale();
362      power_of_two_plus_one_ = right_matcher.power_of_two_plus_one();
363      this->SwapInputs();
364      return;
365    }
366
367    if (this->right().opcode() == kAddOpcode &&
368        this->left().opcode() != kAddOpcode) {
369      this->SwapInputs();
370    }
371  }
372
373  int scale_;
374  bool power_of_two_plus_one_;
375};
376
377typedef AddMatcher<Int32BinopMatcher, IrOpcode::kInt32Add, IrOpcode::kInt32Mul,
378                   IrOpcode::kWord32Shl> Int32AddMatcher;
379typedef AddMatcher<Int64BinopMatcher, IrOpcode::kInt64Add, IrOpcode::kInt64Mul,
380                   IrOpcode::kWord64Shl> Int64AddMatcher;
381
382
383template <class AddMatcher>
384struct BaseWithIndexAndDisplacementMatcher {
385  BaseWithIndexAndDisplacementMatcher(Node* node, bool allow_input_swap)
386      : matches_(false),
387        index_(nullptr),
388        scale_(0),
389        base_(nullptr),
390        displacement_(nullptr) {
391    Initialize(node, allow_input_swap);
392  }
393
394  explicit BaseWithIndexAndDisplacementMatcher(Node* node)
395      : matches_(false),
396        index_(nullptr),
397        scale_(0),
398        base_(nullptr),
399        displacement_(nullptr) {
400    Initialize(node, node->op()->HasProperty(Operator::kCommutative));
401  }
402
403  bool matches() const { return matches_; }
404  Node* index() const { return index_; }
405  int scale() const { return scale_; }
406  Node* base() const { return base_; }
407  Node* displacement() const { return displacement_; }
408
409 private:
410  bool matches_;
411  Node* index_;
412  int scale_;
413  Node* base_;
414  Node* displacement_;
415
416  void Initialize(Node* node, bool allow_input_swap) {
417    // The BaseWithIndexAndDisplacementMatcher canonicalizes the order of
418    // displacements and scale factors that are used as inputs, so instead of
419    // enumerating all possible patterns by brute force, checking for node
420    // clusters using the following templates in the following order suffices to
421    // find all of the interesting cases (S = index * scale, B = base input, D =
422    // displacement input):
423    // (S + (B + D))
424    // (S + (B + B))
425    // (S + D)
426    // (S + B)
427    // ((S + D) + B)
428    // ((S + B) + D)
429    // ((B + D) + B)
430    // ((B + B) + D)
431    // (B + D)
432    // (B + B)
433    if (node->InputCount() < 2) return;
434    AddMatcher m(node, allow_input_swap);
435    Node* left = m.left().node();
436    Node* right = m.right().node();
437    Node* displacement = nullptr;
438    Node* base = nullptr;
439    Node* index = nullptr;
440    Node* scale_expression = nullptr;
441    bool power_of_two_plus_one = false;
442    int scale = 0;
443    if (m.HasIndexInput() && left->OwnedBy(node)) {
444      index = m.IndexInput();
445      scale = m.scale();
446      scale_expression = left;
447      power_of_two_plus_one = m.power_of_two_plus_one();
448      if (right->opcode() == AddMatcher::kOpcode && right->OwnedBy(node)) {
449        AddMatcher right_matcher(right);
450        if (right_matcher.right().HasValue()) {
451          // (S + (B + D))
452          base = right_matcher.left().node();
453          displacement = right_matcher.right().node();
454        } else {
455          // (S + (B + B))
456          base = right;
457        }
458      } else if (m.right().HasValue()) {
459        // (S + D)
460        displacement = right;
461      } else {
462        // (S + B)
463        base = right;
464      }
465    } else {
466      if (left->opcode() == AddMatcher::kOpcode && left->OwnedBy(node)) {
467        AddMatcher left_matcher(left);
468        Node* left_left = left_matcher.left().node();
469        Node* left_right = left_matcher.right().node();
470        if (left_matcher.HasIndexInput() && left_left->OwnedBy(left)) {
471          if (left_matcher.right().HasValue()) {
472            // ((S + D) + B)
473            index = left_matcher.IndexInput();
474            scale = left_matcher.scale();
475            scale_expression = left_left;
476            power_of_two_plus_one = left_matcher.power_of_two_plus_one();
477            displacement = left_right;
478            base = right;
479          } else if (m.right().HasValue()) {
480            // ((S + B) + D)
481            index = left_matcher.IndexInput();
482            scale = left_matcher.scale();
483            scale_expression = left_left;
484            power_of_two_plus_one = left_matcher.power_of_two_plus_one();
485            base = left_right;
486            displacement = right;
487          } else {
488            // (B + B)
489            index = left;
490            base = right;
491          }
492        } else {
493          if (left_matcher.right().HasValue()) {
494            // ((B + D) + B)
495            index = left_left;
496            displacement = left_right;
497            base = right;
498          } else if (m.right().HasValue()) {
499            // ((B + B) + D)
500            index = left_left;
501            base = left_right;
502            displacement = right;
503          } else {
504            // (B + B)
505            index = left;
506            base = right;
507          }
508        }
509      } else {
510        if (m.right().HasValue()) {
511          // (B + D)
512          base = left;
513          displacement = right;
514        } else {
515          // (B + B)
516          base = left;
517          index = right;
518        }
519      }
520    }
521    int64_t value = 0;
522    if (displacement != nullptr) {
523      switch (displacement->opcode()) {
524        case IrOpcode::kInt32Constant: {
525          value = OpParameter<int32_t>(displacement);
526          break;
527        }
528        case IrOpcode::kInt64Constant: {
529          value = OpParameter<int64_t>(displacement);
530          break;
531        }
532        default:
533          UNREACHABLE();
534          break;
535      }
536      if (value == 0) {
537        displacement = nullptr;
538      }
539    }
540    if (power_of_two_plus_one) {
541      if (base != nullptr) {
542        // If the scale requires explicitly using the index as the base, but a
543        // base is already part of the match, then the (1 << N + 1) scale factor
544        // can't be folded into the match and the entire index * scale
545        // calculation must be computed separately.
546        index = scale_expression;
547        scale = 0;
548      } else {
549        base = index;
550      }
551    }
552    base_ = base;
553    displacement_ = displacement;
554    index_ = index;
555    scale_ = scale;
556    matches_ = true;
557  }
558};
559
560typedef BaseWithIndexAndDisplacementMatcher<Int32AddMatcher>
561    BaseWithIndexAndDisplacement32Matcher;
562typedef BaseWithIndexAndDisplacementMatcher<Int64AddMatcher>
563    BaseWithIndexAndDisplacement64Matcher;
564
565struct BranchMatcher : public NodeMatcher {
566  explicit BranchMatcher(Node* branch);
567
568  bool Matched() const { return if_true_ && if_false_; }
569
570  Node* Branch() const { return node(); }
571  Node* IfTrue() const { return if_true_; }
572  Node* IfFalse() const { return if_false_; }
573
574 private:
575  Node* if_true_;
576  Node* if_false_;
577};
578
579
580struct DiamondMatcher : public NodeMatcher {
581  explicit DiamondMatcher(Node* merge);
582
583  bool Matched() const { return branch_; }
584  bool IfProjectionsAreOwned() const {
585    return if_true_->OwnedBy(node()) && if_false_->OwnedBy(node());
586  }
587
588  Node* Branch() const { return branch_; }
589  Node* IfTrue() const { return if_true_; }
590  Node* IfFalse() const { return if_false_; }
591  Node* Merge() const { return node(); }
592
593  Node* TrueInputOf(Node* phi) const {
594    DCHECK(IrOpcode::IsPhiOpcode(phi->opcode()));
595    DCHECK_EQ(3, phi->InputCount());
596    DCHECK_EQ(Merge(), phi->InputAt(2));
597    return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 0 : 1);
598  }
599
600  Node* FalseInputOf(Node* phi) const {
601    DCHECK(IrOpcode::IsPhiOpcode(phi->opcode()));
602    DCHECK_EQ(3, phi->InputCount());
603    DCHECK_EQ(Merge(), phi->InputAt(2));
604    return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 1 : 0);
605  }
606
607 private:
608  Node* branch_;
609  Node* if_true_;
610  Node* if_false_;
611};
612
613}  // namespace compiler
614}  // namespace internal
615}  // namespace v8
616
617#endif  // V8_COMPILER_NODE_MATCHERS_H_
618