deps/v8/src/compiler/node-matchers.h

   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/compiler/node.h"
  11 #include "src/compiler/operator.h"
  12 #include "src/unique.h"
  13
  14 namespace v8 {
  15 namespace internal {
  16 namespace compiler {
  17
  18 // A pattern matcher for nodes.
  19 struct NodeMatcher {
  20   explicit NodeMatcher(Node* node) : node_(node) {}
  21
  22   Node* node() const { return node_; }
  23   const Operator* op() const { return node()->op(); }
  24   IrOpcode::Value opcode() const { return node()->opcode(); }
  25
  26   bool HasProperty(Operator::Property property) const {
  27     return op()->HasProperty(property);
  28   }
  29   Node* InputAt(int index) const { return node()->InputAt(index); }
  30
  31 #define DEFINE_IS_OPCODE(Opcode) \
  32   bool Is##Opcode() const { return opcode() == IrOpcode::k##Opcode; }
  33   ALL_OP_LIST(DEFINE_IS_OPCODE)
  34 #undef DEFINE_IS_OPCODE
  35
  36  private:
  37   Node* node_;
  38 };
  39
  40
  41 // A pattern matcher for abitrary value constants.
  42 template <typename T, IrOpcode::Value kOpcode>
  43 struct ValueMatcher : public NodeMatcher {
  44   typedef T ValueType;
  45
  46   explicit ValueMatcher(Node* node)
  47       : NodeMatcher(node), value_(), has_value_(opcode() == kOpcode) {
  48     if (has_value_) {
  49       value_ = OpParameter<T>(node);
  50     }
  51   }
  52
  53   bool HasValue() const { return has_value_; }
  54   const T& Value() const {
  55     DCHECK(HasValue());
  56     return value_;
  57   }
  58
  59   bool Is(const T& value) const {
  60     return this->HasValue() && this->Value() == value;
  61   }
  62
  63   bool IsInRange(const T& low, const T& high) const {
  64     return this->HasValue() && low <= this->Value() && this->Value() <= high;
  65   }
  66
  67  private:
  68   T value_;
  69   bool has_value_;
  70 };
  71
  72
  73 template <>
  74 inline ValueMatcher<int64_t, IrOpcode::kInt64Constant>::ValueMatcher(Node* node)
  75     : NodeMatcher(node), value_(), has_value_(false) {
  76   if (opcode() == IrOpcode::kInt32Constant) {
  77     value_ = OpParameter<int32_t>(node);
  78     has_value_ = true;
  79   } else if (opcode() == IrOpcode::kInt64Constant) {
  80     value_ = OpParameter<int64_t>(node);
  81     has_value_ = true;
  82   }
  83 }
  84
  85
  86 template <>
  87 inline ValueMatcher<uint64_t, IrOpcode::kInt64Constant>::ValueMatcher(
  88     Node* node)
  89     : NodeMatcher(node), value_(), has_value_(false) {
  90   if (opcode() == IrOpcode::kInt32Constant) {
  91     value_ = OpParameter<uint32_t>(node);
  92     has_value_ = true;
  93   } else if (opcode() == IrOpcode::kInt64Constant) {
  94     value_ = OpParameter<uint64_t>(node);
  95     has_value_ = true;
  96   }
  97 }
  98
  99
 100 // A pattern matcher for integer constants.
 101 template <typename T, IrOpcode::Value kOpcode>
 102 struct IntMatcher FINAL : public ValueMatcher<T, kOpcode> {
 103   explicit IntMatcher(Node* node) : ValueMatcher<T, kOpcode>(node) {}
 104
 105   bool IsMultipleOf(T n) const {
 106     return this->HasValue() && (this->Value() % n) == 0;
 107   }
 108   bool IsPowerOf2() const {
 109     return this->HasValue() && this->Value() > 0 &&
 110            (this->Value() & (this->Value() - 1)) == 0;
 111   }
 112   bool IsNegativePowerOf2() const {
 113     return this->HasValue() && this->Value() < 0 &&
 114            (-this->Value() & (-this->Value() - 1)) == 0;
 115   }
 116 };
 117
 118 typedef IntMatcher<int32_t, IrOpcode::kInt32Constant> Int32Matcher;
 119 typedef IntMatcher<uint32_t, IrOpcode::kInt32Constant> Uint32Matcher;
 120 typedef IntMatcher<int64_t, IrOpcode::kInt64Constant> Int64Matcher;
 121 typedef IntMatcher<uint64_t, IrOpcode::kInt64Constant> Uint64Matcher;
 122 #if V8_HOST_ARCH_32_BIT
 123 typedef Int32Matcher IntPtrMatcher;
 124 typedef Uint32Matcher UintPtrMatcher;
 125 #else
 126 typedef Int64Matcher IntPtrMatcher;
 127 typedef Uint64Matcher UintPtrMatcher;
 128 #endif
 129
 130
 131 // A pattern matcher for floating point constants.
 132 template <typename T, IrOpcode::Value kOpcode>
 133 struct FloatMatcher FINAL : public ValueMatcher<T, kOpcode> {
 134   explicit FloatMatcher(Node* node) : ValueMatcher<T, kOpcode>(node) {}
 135
 136   bool IsMinusZero() const {
 137     return this->Is(0.0) && std::signbit(this->Value());
 138   }
 139   bool IsNaN() const { return this->HasValue() && std::isnan(this->Value()); }
 140 };
 141
 142 typedef FloatMatcher<float, IrOpcode::kFloat32Constant> Float32Matcher;
 143 typedef FloatMatcher<double, IrOpcode::kFloat64Constant> Float64Matcher;
 144 typedef FloatMatcher<double, IrOpcode::kNumberConstant> NumberMatcher;
 145
 146
 147 // A pattern matcher for heap object constants.
 148 template <typename T>
 149 struct HeapObjectMatcher FINAL
 150     : public ValueMatcher<Unique<T>, IrOpcode::kHeapConstant> {
 151   explicit HeapObjectMatcher(Node* node)
 152       : ValueMatcher<Unique<T>, IrOpcode::kHeapConstant>(node) {}
 153 };
 154
 155
 156 // For shorter pattern matching code, this struct matches both the left and
 157 // right hand sides of a binary operation and can put constants on the right
 158 // if they appear on the left hand side of a commutative operation.
 159 template <typename Left, typename Right>
 160 struct BinopMatcher : public NodeMatcher {
 161   explicit BinopMatcher(Node* node)
 162       : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) {
 163     if (HasProperty(Operator::kCommutative)) PutConstantOnRight();
 164   }
 165   BinopMatcher(Node* node, bool allow_input_swap)
 166       : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) {
 167     if (allow_input_swap) PutConstantOnRight();
 168   }
 169
 170   typedef Left LeftMatcher;
 171   typedef Right RightMatcher;
 172
 173   const Left& left() const { return left_; }
 174   const Right& right() const { return right_; }
 175
 176   bool IsFoldable() const { return left().HasValue() && right().HasValue(); }
 177   bool LeftEqualsRight() const { return left().node() == right().node(); }
 178
 179  protected:
 180   void SwapInputs() {
 181     std::swap(left_, right_);
 182     node()->ReplaceInput(0, left().node());
 183     node()->ReplaceInput(1, right().node());
 184   }
 185
 186  private:
 187   void PutConstantOnRight() {
 188     if (left().HasValue() && !right().HasValue()) {
 189       SwapInputs();
 190     }
 191   }
 192
 193   Left left_;
 194   Right right_;
 195 };
 196
 197 typedef BinopMatcher<Int32Matcher, Int32Matcher> Int32BinopMatcher;
 198 typedef BinopMatcher<Uint32Matcher, Uint32Matcher> Uint32BinopMatcher;
 199 typedef BinopMatcher<Int64Matcher, Int64Matcher> Int64BinopMatcher;
 200 typedef BinopMatcher<Uint64Matcher, Uint64Matcher> Uint64BinopMatcher;
 201 typedef BinopMatcher<IntPtrMatcher, IntPtrMatcher> IntPtrBinopMatcher;
 202 typedef BinopMatcher<UintPtrMatcher, UintPtrMatcher> UintPtrBinopMatcher;
 203 typedef BinopMatcher<Float64Matcher, Float64Matcher> Float64BinopMatcher;
 204 typedef BinopMatcher<NumberMatcher, NumberMatcher> NumberBinopMatcher;
 205
 206
 207 template <class BinopMatcher, IrOpcode::Value kMulOpcode,
 208           IrOpcode::Value kShiftOpcode>
 209 struct ScaleMatcher {
 210   explicit ScaleMatcher(Node* node, bool allow_power_of_two_plus_one = false)
 211       : scale_(-1), power_of_two_plus_one_(false) {
 212     if (node->InputCount() < 2) return;
 213     BinopMatcher m(node);
 214     if (node->opcode() == kShiftOpcode) {
 215       if (m.right().HasValue()) {
 216         typename BinopMatcher::RightMatcher::ValueType value =
 217             m.right().Value();
 218         if (value >= 0 && value <= 3) {
 219           scale_ = static_cast<int>(value);
 220         }
 221       }
 222     } else if (node->opcode() == kMulOpcode) {
 223       if (m.right().HasValue()) {
 224         typename BinopMatcher::RightMatcher::ValueType value =
 225             m.right().Value();
 226         if (value == 1) {
 227           scale_ = 0;
 228         } else if (value == 2) {
 229           scale_ = 1;
 230         } else if (value == 4) {
 231           scale_ = 2;
 232         } else if (value == 8) {
 233           scale_ = 3;
 234         } else if (allow_power_of_two_plus_one) {
 235           if (value == 3) {
 236             scale_ = 1;
 237             power_of_two_plus_one_ = true;
 238           } else if (value == 5) {
 239             scale_ = 2;
 240             power_of_two_plus_one_ = true;
 241           } else if (value == 9) {
 242             scale_ = 3;
 243             power_of_two_plus_one_ = true;
 244           }
 245         }
 246       }
 247     }
 248   }
 249
 250   bool matches() const { return scale_ != -1; }
 251   int scale() const { return scale_; }
 252   bool power_of_two_plus_one() const { return power_of_two_plus_one_; }
 253
 254  private:
 255   int scale_;
 256   bool power_of_two_plus_one_;
 257 };
 258
 259 typedef ScaleMatcher<Int32BinopMatcher, IrOpcode::kInt32Mul,
 260                      IrOpcode::kWord32Shl> Int32ScaleMatcher;
 261 typedef ScaleMatcher<Int64BinopMatcher, IrOpcode::kInt64Mul,
 262                      IrOpcode::kWord64Shl> Int64ScaleMatcher;
 263
 264
 265 template <class BinopMatcher, IrOpcode::Value kAddOpcode,
 266           IrOpcode::Value kMulOpcode, IrOpcode::Value kShiftOpcode>
 267 struct AddMatcher : public BinopMatcher {
 268   static const IrOpcode::Value kOpcode = kAddOpcode;
 269   typedef ScaleMatcher<BinopMatcher, kMulOpcode, kShiftOpcode> Matcher;
 270
 271   AddMatcher(Node* node, bool allow_input_swap)
 272       : BinopMatcher(node, allow_input_swap),
 273         scale_(-1),
 274         power_of_two_plus_one_(false) {
 275     Initialize(node, allow_input_swap);
 276   }
 277   explicit AddMatcher(Node* node)
 278       : BinopMatcher(node, node->op()->HasProperty(Operator::kCommutative)),
 279         scale_(-1),
 280         power_of_two_plus_one_(false) {
 281     Initialize(node, node->op()->HasProperty(Operator::kCommutative));
 282   }
 283
 284   bool HasIndexInput() const { return scale_ != -1; }
 285   Node* IndexInput() const {
 286     DCHECK(HasIndexInput());
 287     return this->left().node()->InputAt(0);
 288   }
 289   int scale() const {
 290     DCHECK(HasIndexInput());
 291     return scale_;
 292   }
 293   bool power_of_two_plus_one() const { return power_of_two_plus_one_; }
 294
 295  private:
 296   void Initialize(Node* node, bool allow_input_swap) {
 297     Matcher left_matcher(this->left().node(), true);
 298     if (left_matcher.matches()) {
 299       scale_ = left_matcher.scale();
 300       power_of_two_plus_one_ = left_matcher.power_of_two_plus_one();
 301       return;
 302     }
 303
 304     if (!allow_input_swap) {
 305       return;
 306     }
 307
 308     Matcher right_matcher(this->right().node(), true);
 309     if (right_matcher.matches()) {
 310       scale_ = right_matcher.scale();
 311       power_of_two_plus_one_ = right_matcher.power_of_two_plus_one();
 312       this->SwapInputs();
 313       return;
 314     }
 315
 316     if (this->right().opcode() == kAddOpcode &&
 317         this->left().opcode() != kAddOpcode) {
 318       this->SwapInputs();
 319     }
 320   }
 321
 322   int scale_;
 323   bool power_of_two_plus_one_;
 324 };
 325
 326 typedef AddMatcher<Int32BinopMatcher, IrOpcode::kInt32Add, IrOpcode::kInt32Mul,
 327                    IrOpcode::kWord32Shl> Int32AddMatcher;
 328 typedef AddMatcher<Int64BinopMatcher, IrOpcode::kInt64Add, IrOpcode::kInt64Mul,
 329                    IrOpcode::kWord64Shl> Int64AddMatcher;
 330
 331
 332 template <class AddMatcher>
 333 struct BaseWithIndexAndDisplacementMatcher {
 334   BaseWithIndexAndDisplacementMatcher(Node* node, bool allow_input_swap)
 335       : matches_(false),
 336         index_(NULL),
 337         scale_(0),
 338         base_(NULL),
 339         displacement_(NULL) {
 340     Initialize(node, allow_input_swap);
 341   }
 342
 343   explicit BaseWithIndexAndDisplacementMatcher(Node* node)
 344       : matches_(false),
 345         index_(NULL),
 346         scale_(0),
 347         base_(NULL),
 348         displacement_(NULL) {
 349     Initialize(node, node->op()->HasProperty(Operator::kCommutative));
 350   }
 351
 352   bool matches() const { return matches_; }
 353   Node* index() const { return index_; }
 354   int scale() const { return scale_; }
 355   Node* base() const { return base_; }
 356   Node* displacement() const { return displacement_; }
 357
 358  private:
 359   bool matches_;
 360   Node* index_;
 361   int scale_;
 362   Node* base_;
 363   Node* displacement_;
 364
 365   void Initialize(Node* node, bool allow_input_swap) {
 366     // The BaseWithIndexAndDisplacementMatcher canonicalizes the order of
 367     // displacements and scale factors that are used as inputs, so instead of
 368     // enumerating all possible patterns by brute force, checking for node
 369     // clusters using the following templates in the following order suffices to
 370     // find all of the interesting cases (S = index * scale, B = base input, D =
 371     // displacement input):
 372     // (S + (B + D))
 373     // (S + (B + B))
 374     // (S + D)
 375     // (S + B)
 376     // ((S + D) + B)
 377     // ((S + B) + D)
 378     // ((B + D) + B)
 379     // ((B + B) + D)
 380     // (B + D)
 381     // (B + B)
 382     if (node->InputCount() < 2) return;
 383     AddMatcher m(node, allow_input_swap);
 384     Node* left = m.left().node();
 385     Node* right = m.right().node();
 386     Node* displacement = NULL;
 387     Node* base = NULL;
 388     Node* index = NULL;
 389     Node* scale_expression = NULL;
 390     bool power_of_two_plus_one = false;
 391     int scale = 0;
 392     if (m.HasIndexInput() && left->OwnedBy(node)) {
 393       index = m.IndexInput();
 394       scale = m.scale();
 395       scale_expression = left;
 396       power_of_two_plus_one = m.power_of_two_plus_one();
 397       if (right->opcode() == AddMatcher::kOpcode && right->OwnedBy(node)) {
 398         AddMatcher right_matcher(right);
 399         if (right_matcher.right().HasValue()) {
 400           // (S + (B + D))
 401           base = right_matcher.left().node();
 402           displacement = right_matcher.right().node();
 403         } else {
 404           // (S + (B + B))
 405           base = right;
 406         }
 407       } else if (m.right().HasValue()) {
 408         // (S + D)
 409         displacement = right;
 410       } else {
 411         // (S + B)
 412         base = right;
 413       }
 414     } else {
 415       if (left->opcode() == AddMatcher::kOpcode && left->OwnedBy(node)) {
 416         AddMatcher left_matcher(left);
 417         Node* left_left = left_matcher.left().node();
 418         Node* left_right = left_matcher.right().node();
 419         if (left_matcher.HasIndexInput() && left_left->OwnedBy(left)) {
 420           if (left_matcher.right().HasValue()) {
 421             // ((S + D) + B)
 422             index = left_matcher.IndexInput();
 423             scale = left_matcher.scale();
 424             scale_expression = left_left;
 425             power_of_two_plus_one = left_matcher.power_of_two_plus_one();
 426             displacement = left_right;
 427             base = right;
 428           } else if (m.right().HasValue()) {
 429             // ((S + B) + D)
 430             index = left_matcher.IndexInput();
 431             scale = left_matcher.scale();
 432             scale_expression = left_left;
 433             power_of_two_plus_one = left_matcher.power_of_two_plus_one();
 434             base = left_right;
 435             displacement = right;
 436           } else {
 437             // (B + B)
 438             index = left;
 439             base = right;
 440           }
 441         } else {
 442           if (left_matcher.right().HasValue()) {
 443             // ((B + D) + B)
 444             index = left_left;
 445             displacement = left_right;
 446             base = right;
 447           } else if (m.right().HasValue()) {
 448             // ((B + B) + D)
 449             index = left_left;
 450             base = left_right;
 451             displacement = right;
 452           } else {
 453             // (B + B)
 454             index = left;
 455             base = right;
 456           }
 457         }
 458       } else {
 459         if (m.right().HasValue()) {
 460           // (B + D)
 461           base = left;
 462           displacement = right;
 463         } else {
 464           // (B + B)
 465           base = left;
 466           index = right;
 467         }
 468       }
 469     }
 470     int64_t value = 0;
 471     if (displacement != NULL) {
 472       switch (displacement->opcode()) {
 473         case IrOpcode::kInt32Constant: {
 474           value = OpParameter<int32_t>(displacement);
 475           break;
 476         }
 477         case IrOpcode::kInt64Constant: {
 478           value = OpParameter<int64_t>(displacement);
 479           break;
 480         }
 481         default:
 482           UNREACHABLE();
 483           break;
 484       }
 485       if (value == 0) {
 486         displacement = NULL;
 487       }
 488     }
 489     if (power_of_two_plus_one) {
 490       if (base != NULL) {
 491         // If the scale requires explicitly using the index as the base, but a
 492         // base is already part of the match, then the (1 << N + 1) scale factor
 493         // can't be folded into the match and the entire index * scale
 494         // calculation must be computed separately.
 495         index = scale_expression;
 496         scale = 0;
 497       } else {
 498         base = index;
 499       }
 500     }
 501     base_ = base;
 502     displacement_ = displacement;
 503     index_ = index;
 504     scale_ = scale;
 505     matches_ = true;
 506   }
 507 };
 508
 509 typedef BaseWithIndexAndDisplacementMatcher<Int32AddMatcher>
 510     BaseWithIndexAndDisplacement32Matcher;
 511 typedef BaseWithIndexAndDisplacementMatcher<Int64AddMatcher>
 512     BaseWithIndexAndDisplacement64Matcher;
 513
 514 }  // namespace compiler
 515 }  // namespace internal
 516 }  // namespace v8
 517
 518 #endif  // V8_COMPILER_NODE_MATCHERS_H_