Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 8 | #include <cmath> |
| 9 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 10 | // TODO(turbofan): Move ExternalReference out of assembler.h |
| 11 | #include "src/assembler.h" |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 12 | #include "src/compiler/node.h" |
| 13 | #include "src/compiler/operator.h" |
| 14 | |
| 15 | namespace v8 { |
| 16 | namespace internal { |
| 17 | namespace compiler { |
| 18 | |
| 19 | // A pattern matcher for nodes. |
| 20 | struct NodeMatcher { |
| 21 | explicit NodeMatcher(Node* node) : node_(node) {} |
| 22 | |
| 23 | Node* node() const { return node_; } |
| 24 | const Operator* op() const { return node()->op(); } |
| 25 | IrOpcode::Value opcode() const { return node()->opcode(); } |
| 26 | |
| 27 | bool HasProperty(Operator::Property property) const { |
| 28 | return op()->HasProperty(property); |
| 29 | } |
| 30 | Node* InputAt(int index) const { return node()->InputAt(index); } |
| 31 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 32 | bool Equals(const Node* node) const { return node_ == node; } |
| 33 | |
| 34 | bool IsComparison() const; |
| 35 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 36 | #define DEFINE_IS_OPCODE(Opcode) \ |
| 37 | bool Is##Opcode() const { return opcode() == IrOpcode::k##Opcode; } |
| 38 | ALL_OP_LIST(DEFINE_IS_OPCODE) |
| 39 | #undef DEFINE_IS_OPCODE |
| 40 | |
| 41 | private: |
| 42 | Node* node_; |
| 43 | }; |
| 44 | |
| 45 | |
| 46 | // A pattern matcher for abitrary value constants. |
| 47 | template <typename T, IrOpcode::Value kOpcode> |
| 48 | struct ValueMatcher : public NodeMatcher { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 49 | typedef T ValueType; |
| 50 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 64 | private: |
| 65 | T value_; |
| 66 | bool has_value_; |
| 67 | }; |
| 68 | |
| 69 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 70 | template <> |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 71 | inline ValueMatcher<uint32_t, IrOpcode::kInt32Constant>::ValueMatcher( |
| 72 | Node* node) |
| 73 | : NodeMatcher(node), |
| 74 | value_(), |
| 75 | has_value_(opcode() == IrOpcode::kInt32Constant) { |
| 76 | if (has_value_) { |
| 77 | value_ = static_cast<uint32_t>(OpParameter<int32_t>(node)); |
| 78 | } |
| 79 | } |
| 80 | |
| 81 | |
| 82 | template <> |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 83 | inline ValueMatcher<int64_t, IrOpcode::kInt64Constant>::ValueMatcher(Node* node) |
| 84 | : NodeMatcher(node), value_(), has_value_(false) { |
| 85 | if (opcode() == IrOpcode::kInt32Constant) { |
| 86 | value_ = OpParameter<int32_t>(node); |
| 87 | has_value_ = true; |
| 88 | } else if (opcode() == IrOpcode::kInt64Constant) { |
| 89 | value_ = OpParameter<int64_t>(node); |
| 90 | has_value_ = true; |
| 91 | } |
| 92 | } |
| 93 | |
| 94 | |
| 95 | template <> |
| 96 | inline ValueMatcher<uint64_t, IrOpcode::kInt64Constant>::ValueMatcher( |
| 97 | Node* node) |
| 98 | : NodeMatcher(node), value_(), has_value_(false) { |
| 99 | if (opcode() == IrOpcode::kInt32Constant) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 100 | value_ = static_cast<uint32_t>(OpParameter<int32_t>(node)); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 101 | has_value_ = true; |
| 102 | } else if (opcode() == IrOpcode::kInt64Constant) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 103 | value_ = static_cast<uint64_t>(OpParameter<int64_t>(node)); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 104 | has_value_ = true; |
| 105 | } |
| 106 | } |
| 107 | |
| 108 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 109 | // A pattern matcher for integer constants. |
| 110 | template <typename T, IrOpcode::Value kOpcode> |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 111 | struct IntMatcher final : public ValueMatcher<T, kOpcode> { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 112 | explicit IntMatcher(Node* node) : ValueMatcher<T, kOpcode>(node) {} |
| 113 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 | } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 120 | bool IsMultipleOf(T n) const { |
| 121 | return this->HasValue() && (this->Value() % n) == 0; |
| 122 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 123 | bool IsPowerOf2() const { |
| 124 | return this->HasValue() && this->Value() > 0 && |
| 125 | (this->Value() & (this->Value() - 1)) == 0; |
| 126 | } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 127 | bool IsNegativePowerOf2() const { |
| 128 | return this->HasValue() && this->Value() < 0 && |
| 129 | (-this->Value() & (-this->Value() - 1)) == 0; |
| 130 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 131 | }; |
| 132 | |
| 133 | typedef IntMatcher<int32_t, IrOpcode::kInt32Constant> Int32Matcher; |
| 134 | typedef IntMatcher<uint32_t, IrOpcode::kInt32Constant> Uint32Matcher; |
| 135 | typedef IntMatcher<int64_t, IrOpcode::kInt64Constant> Int64Matcher; |
| 136 | typedef IntMatcher<uint64_t, IrOpcode::kInt64Constant> Uint64Matcher; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 137 | #if V8_HOST_ARCH_32_BIT |
| 138 | typedef Int32Matcher IntPtrMatcher; |
| 139 | typedef Uint32Matcher UintPtrMatcher; |
| 140 | #else |
| 141 | typedef Int64Matcher IntPtrMatcher; |
| 142 | typedef Uint64Matcher UintPtrMatcher; |
| 143 | #endif |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 144 | |
| 145 | |
| 146 | // A pattern matcher for floating point constants. |
| 147 | template <typename T, IrOpcode::Value kOpcode> |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 148 | struct FloatMatcher final : public ValueMatcher<T, kOpcode> { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 149 | explicit FloatMatcher(Node* node) : ValueMatcher<T, kOpcode>(node) {} |
| 150 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 | } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 157 | bool IsMinusZero() const { |
| 158 | return this->Is(0.0) && std::signbit(this->Value()); |
| 159 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 160 | bool IsNaN() const { return this->HasValue() && std::isnan(this->Value()); } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 161 | bool IsZero() const { return this->Is(0.0) && !std::signbit(this->Value()); } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 162 | }; |
| 163 | |
| 164 | typedef FloatMatcher<float, IrOpcode::kFloat32Constant> Float32Matcher; |
| 165 | typedef FloatMatcher<double, IrOpcode::kFloat64Constant> Float64Matcher; |
| 166 | typedef FloatMatcher<double, IrOpcode::kNumberConstant> NumberMatcher; |
| 167 | |
| 168 | |
| 169 | // A pattern matcher for heap object constants. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 170 | struct HeapObjectMatcher final |
| 171 | : public ValueMatcher<Handle<HeapObject>, IrOpcode::kHeapConstant> { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 172 | explicit HeapObjectMatcher(Node* node) |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 173 | : ValueMatcher<Handle<HeapObject>, IrOpcode::kHeapConstant>(node) {} |
| 174 | }; |
| 175 | |
| 176 | |
| 177 | // A pattern matcher for external reference constants. |
| 178 | struct ExternalReferenceMatcher final |
| 179 | : public ValueMatcher<ExternalReference, IrOpcode::kExternalConstant> { |
| 180 | explicit ExternalReferenceMatcher(Node* node) |
| 181 | : ValueMatcher<ExternalReference, IrOpcode::kExternalConstant>(node) {} |
| 182 | bool Is(const ExternalReference& value) const { |
| 183 | return this->HasValue() && this->Value() == value; |
| 184 | } |
| 185 | }; |
| 186 | |
| 187 | |
| 188 | // For shorter pattern matching code, this struct matches the inputs to |
| 189 | // machine-level load operations. |
| 190 | template <typename Object> |
| 191 | struct LoadMatcher : public NodeMatcher { |
| 192 | explicit LoadMatcher(Node* node) |
| 193 | : NodeMatcher(node), object_(InputAt(0)), index_(InputAt(1)) {} |
| 194 | |
| 195 | typedef Object ObjectMatcher; |
| 196 | |
| 197 | Object const& object() const { return object_; } |
| 198 | IntPtrMatcher const& index() const { return index_; } |
| 199 | |
| 200 | private: |
| 201 | Object const object_; |
| 202 | IntPtrMatcher const index_; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 203 | }; |
| 204 | |
| 205 | |
| 206 | // For shorter pattern matching code, this struct matches both the left and |
| 207 | // right hand sides of a binary operation and can put constants on the right |
| 208 | // if they appear on the left hand side of a commutative operation. |
| 209 | template <typename Left, typename Right> |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 210 | struct BinopMatcher : public NodeMatcher { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 211 | explicit BinopMatcher(Node* node) |
| 212 | : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) { |
| 213 | if (HasProperty(Operator::kCommutative)) PutConstantOnRight(); |
| 214 | } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 229 | protected: |
| 230 | void SwapInputs() { |
| 231 | std::swap(left_, right_); |
| 232 | node()->ReplaceInput(0, left().node()); |
| 233 | node()->ReplaceInput(1, right().node()); |
| 234 | } |
| 235 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 236 | private: |
| 237 | void PutConstantOnRight() { |
| 238 | if (left().HasValue() && !right().HasValue()) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 239 | SwapInputs(); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 240 | } |
| 241 | } |
| 242 | |
| 243 | Left left_; |
| 244 | Right right_; |
| 245 | }; |
| 246 | |
| 247 | typedef BinopMatcher<Int32Matcher, Int32Matcher> Int32BinopMatcher; |
| 248 | typedef BinopMatcher<Uint32Matcher, Uint32Matcher> Uint32BinopMatcher; |
| 249 | typedef BinopMatcher<Int64Matcher, Int64Matcher> Int64BinopMatcher; |
| 250 | typedef BinopMatcher<Uint64Matcher, Uint64Matcher> Uint64BinopMatcher; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 251 | typedef BinopMatcher<IntPtrMatcher, IntPtrMatcher> IntPtrBinopMatcher; |
| 252 | typedef BinopMatcher<UintPtrMatcher, UintPtrMatcher> UintPtrBinopMatcher; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 253 | typedef BinopMatcher<Float32Matcher, Float32Matcher> Float32BinopMatcher; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 254 | typedef BinopMatcher<Float64Matcher, Float64Matcher> Float64BinopMatcher; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 255 | typedef BinopMatcher<NumberMatcher, NumberMatcher> NumberBinopMatcher; |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 256 | typedef BinopMatcher<HeapObjectMatcher, HeapObjectMatcher> |
| 257 | HeapObjectBinopMatcher; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 258 | |
| 259 | template <class BinopMatcher, IrOpcode::Value kMulOpcode, |
| 260 | IrOpcode::Value kShiftOpcode> |
| 261 | struct ScaleMatcher { |
| 262 | explicit ScaleMatcher(Node* node, bool allow_power_of_two_plus_one = false) |
| 263 | : scale_(-1), power_of_two_plus_one_(false) { |
| 264 | if (node->InputCount() < 2) return; |
| 265 | BinopMatcher m(node); |
| 266 | if (node->opcode() == kShiftOpcode) { |
| 267 | if (m.right().HasValue()) { |
| 268 | typename BinopMatcher::RightMatcher::ValueType value = |
| 269 | m.right().Value(); |
| 270 | if (value >= 0 && value <= 3) { |
| 271 | scale_ = static_cast<int>(value); |
| 272 | } |
| 273 | } |
| 274 | } else if (node->opcode() == kMulOpcode) { |
| 275 | if (m.right().HasValue()) { |
| 276 | typename BinopMatcher::RightMatcher::ValueType value = |
| 277 | m.right().Value(); |
| 278 | if (value == 1) { |
| 279 | scale_ = 0; |
| 280 | } else if (value == 2) { |
| 281 | scale_ = 1; |
| 282 | } else if (value == 4) { |
| 283 | scale_ = 2; |
| 284 | } else if (value == 8) { |
| 285 | scale_ = 3; |
| 286 | } else if (allow_power_of_two_plus_one) { |
| 287 | if (value == 3) { |
| 288 | scale_ = 1; |
| 289 | power_of_two_plus_one_ = true; |
| 290 | } else if (value == 5) { |
| 291 | scale_ = 2; |
| 292 | power_of_two_plus_one_ = true; |
| 293 | } else if (value == 9) { |
| 294 | scale_ = 3; |
| 295 | power_of_two_plus_one_ = true; |
| 296 | } |
| 297 | } |
| 298 | } |
| 299 | } |
| 300 | } |
| 301 | |
| 302 | bool matches() const { return scale_ != -1; } |
| 303 | int scale() const { return scale_; } |
| 304 | bool power_of_two_plus_one() const { return power_of_two_plus_one_; } |
| 305 | |
| 306 | private: |
| 307 | int scale_; |
| 308 | bool power_of_two_plus_one_; |
| 309 | }; |
| 310 | |
| 311 | typedef ScaleMatcher<Int32BinopMatcher, IrOpcode::kInt32Mul, |
| 312 | IrOpcode::kWord32Shl> Int32ScaleMatcher; |
| 313 | typedef ScaleMatcher<Int64BinopMatcher, IrOpcode::kInt64Mul, |
| 314 | IrOpcode::kWord64Shl> Int64ScaleMatcher; |
| 315 | |
| 316 | |
| 317 | template <class BinopMatcher, IrOpcode::Value kAddOpcode, |
| 318 | IrOpcode::Value kMulOpcode, IrOpcode::Value kShiftOpcode> |
| 319 | struct AddMatcher : public BinopMatcher { |
| 320 | static const IrOpcode::Value kOpcode = kAddOpcode; |
| 321 | typedef ScaleMatcher<BinopMatcher, kMulOpcode, kShiftOpcode> Matcher; |
| 322 | |
| 323 | AddMatcher(Node* node, bool allow_input_swap) |
| 324 | : BinopMatcher(node, allow_input_swap), |
| 325 | scale_(-1), |
| 326 | power_of_two_plus_one_(false) { |
| 327 | Initialize(node, allow_input_swap); |
| 328 | } |
| 329 | explicit AddMatcher(Node* node) |
| 330 | : BinopMatcher(node, node->op()->HasProperty(Operator::kCommutative)), |
| 331 | scale_(-1), |
| 332 | power_of_two_plus_one_(false) { |
| 333 | Initialize(node, node->op()->HasProperty(Operator::kCommutative)); |
| 334 | } |
| 335 | |
| 336 | bool HasIndexInput() const { return scale_ != -1; } |
| 337 | Node* IndexInput() const { |
| 338 | DCHECK(HasIndexInput()); |
| 339 | return this->left().node()->InputAt(0); |
| 340 | } |
| 341 | int scale() const { |
| 342 | DCHECK(HasIndexInput()); |
| 343 | return scale_; |
| 344 | } |
| 345 | bool power_of_two_plus_one() const { return power_of_two_plus_one_; } |
| 346 | |
| 347 | private: |
| 348 | void Initialize(Node* node, bool allow_input_swap) { |
| 349 | Matcher left_matcher(this->left().node(), true); |
| 350 | if (left_matcher.matches()) { |
| 351 | scale_ = left_matcher.scale(); |
| 352 | power_of_two_plus_one_ = left_matcher.power_of_two_plus_one(); |
| 353 | return; |
| 354 | } |
| 355 | |
| 356 | if (!allow_input_swap) { |
| 357 | return; |
| 358 | } |
| 359 | |
| 360 | Matcher right_matcher(this->right().node(), true); |
| 361 | if (right_matcher.matches()) { |
| 362 | scale_ = right_matcher.scale(); |
| 363 | power_of_two_plus_one_ = right_matcher.power_of_two_plus_one(); |
| 364 | this->SwapInputs(); |
| 365 | return; |
| 366 | } |
| 367 | |
| 368 | if (this->right().opcode() == kAddOpcode && |
| 369 | this->left().opcode() != kAddOpcode) { |
| 370 | this->SwapInputs(); |
| 371 | } |
| 372 | } |
| 373 | |
| 374 | int scale_; |
| 375 | bool power_of_two_plus_one_; |
| 376 | }; |
| 377 | |
| 378 | typedef AddMatcher<Int32BinopMatcher, IrOpcode::kInt32Add, IrOpcode::kInt32Mul, |
| 379 | IrOpcode::kWord32Shl> Int32AddMatcher; |
| 380 | typedef AddMatcher<Int64BinopMatcher, IrOpcode::kInt64Add, IrOpcode::kInt64Mul, |
| 381 | IrOpcode::kWord64Shl> Int64AddMatcher; |
| 382 | |
| 383 | |
| 384 | template <class AddMatcher> |
| 385 | struct BaseWithIndexAndDisplacementMatcher { |
| 386 | BaseWithIndexAndDisplacementMatcher(Node* node, bool allow_input_swap) |
| 387 | : matches_(false), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 388 | index_(nullptr), |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 389 | scale_(0), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 390 | base_(nullptr), |
| 391 | displacement_(nullptr) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 392 | Initialize(node, allow_input_swap); |
| 393 | } |
| 394 | |
| 395 | explicit BaseWithIndexAndDisplacementMatcher(Node* node) |
| 396 | : matches_(false), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 397 | index_(nullptr), |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 398 | scale_(0), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 399 | base_(nullptr), |
| 400 | displacement_(nullptr) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 401 | Initialize(node, node->op()->HasProperty(Operator::kCommutative)); |
| 402 | } |
| 403 | |
| 404 | bool matches() const { return matches_; } |
| 405 | Node* index() const { return index_; } |
| 406 | int scale() const { return scale_; } |
| 407 | Node* base() const { return base_; } |
| 408 | Node* displacement() const { return displacement_; } |
| 409 | |
| 410 | private: |
| 411 | bool matches_; |
| 412 | Node* index_; |
| 413 | int scale_; |
| 414 | Node* base_; |
| 415 | Node* displacement_; |
| 416 | |
| 417 | void Initialize(Node* node, bool allow_input_swap) { |
| 418 | // The BaseWithIndexAndDisplacementMatcher canonicalizes the order of |
| 419 | // displacements and scale factors that are used as inputs, so instead of |
| 420 | // enumerating all possible patterns by brute force, checking for node |
| 421 | // clusters using the following templates in the following order suffices to |
| 422 | // find all of the interesting cases (S = index * scale, B = base input, D = |
| 423 | // displacement input): |
| 424 | // (S + (B + D)) |
| 425 | // (S + (B + B)) |
| 426 | // (S + D) |
| 427 | // (S + B) |
| 428 | // ((S + D) + B) |
| 429 | // ((S + B) + D) |
| 430 | // ((B + D) + B) |
| 431 | // ((B + B) + D) |
| 432 | // (B + D) |
| 433 | // (B + B) |
| 434 | if (node->InputCount() < 2) return; |
| 435 | AddMatcher m(node, allow_input_swap); |
| 436 | Node* left = m.left().node(); |
| 437 | Node* right = m.right().node(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 438 | Node* displacement = nullptr; |
| 439 | Node* base = nullptr; |
| 440 | Node* index = nullptr; |
| 441 | Node* scale_expression = nullptr; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 442 | bool power_of_two_plus_one = false; |
| 443 | int scale = 0; |
| 444 | if (m.HasIndexInput() && left->OwnedBy(node)) { |
| 445 | index = m.IndexInput(); |
| 446 | scale = m.scale(); |
| 447 | scale_expression = left; |
| 448 | power_of_two_plus_one = m.power_of_two_plus_one(); |
| 449 | if (right->opcode() == AddMatcher::kOpcode && right->OwnedBy(node)) { |
| 450 | AddMatcher right_matcher(right); |
| 451 | if (right_matcher.right().HasValue()) { |
| 452 | // (S + (B + D)) |
| 453 | base = right_matcher.left().node(); |
| 454 | displacement = right_matcher.right().node(); |
| 455 | } else { |
| 456 | // (S + (B + B)) |
| 457 | base = right; |
| 458 | } |
| 459 | } else if (m.right().HasValue()) { |
| 460 | // (S + D) |
| 461 | displacement = right; |
| 462 | } else { |
| 463 | // (S + B) |
| 464 | base = right; |
| 465 | } |
| 466 | } else { |
| 467 | if (left->opcode() == AddMatcher::kOpcode && left->OwnedBy(node)) { |
| 468 | AddMatcher left_matcher(left); |
| 469 | Node* left_left = left_matcher.left().node(); |
| 470 | Node* left_right = left_matcher.right().node(); |
| 471 | if (left_matcher.HasIndexInput() && left_left->OwnedBy(left)) { |
| 472 | if (left_matcher.right().HasValue()) { |
| 473 | // ((S + D) + B) |
| 474 | index = left_matcher.IndexInput(); |
| 475 | scale = left_matcher.scale(); |
| 476 | scale_expression = left_left; |
| 477 | power_of_two_plus_one = left_matcher.power_of_two_plus_one(); |
| 478 | displacement = left_right; |
| 479 | base = right; |
| 480 | } else if (m.right().HasValue()) { |
| 481 | // ((S + B) + D) |
| 482 | index = left_matcher.IndexInput(); |
| 483 | scale = left_matcher.scale(); |
| 484 | scale_expression = left_left; |
| 485 | power_of_two_plus_one = left_matcher.power_of_two_plus_one(); |
| 486 | base = left_right; |
| 487 | displacement = right; |
| 488 | } else { |
| 489 | // (B + B) |
| 490 | index = left; |
| 491 | base = right; |
| 492 | } |
| 493 | } else { |
| 494 | if (left_matcher.right().HasValue()) { |
| 495 | // ((B + D) + B) |
| 496 | index = left_left; |
| 497 | displacement = left_right; |
| 498 | base = right; |
| 499 | } else if (m.right().HasValue()) { |
| 500 | // ((B + B) + D) |
| 501 | index = left_left; |
| 502 | base = left_right; |
| 503 | displacement = right; |
| 504 | } else { |
| 505 | // (B + B) |
| 506 | index = left; |
| 507 | base = right; |
| 508 | } |
| 509 | } |
| 510 | } else { |
| 511 | if (m.right().HasValue()) { |
| 512 | // (B + D) |
| 513 | base = left; |
| 514 | displacement = right; |
| 515 | } else { |
| 516 | // (B + B) |
| 517 | base = left; |
| 518 | index = right; |
| 519 | } |
| 520 | } |
| 521 | } |
| 522 | int64_t value = 0; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 523 | if (displacement != nullptr) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 524 | switch (displacement->opcode()) { |
| 525 | case IrOpcode::kInt32Constant: { |
| 526 | value = OpParameter<int32_t>(displacement); |
| 527 | break; |
| 528 | } |
| 529 | case IrOpcode::kInt64Constant: { |
| 530 | value = OpParameter<int64_t>(displacement); |
| 531 | break; |
| 532 | } |
| 533 | default: |
| 534 | UNREACHABLE(); |
| 535 | break; |
| 536 | } |
| 537 | if (value == 0) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 538 | displacement = nullptr; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 539 | } |
| 540 | } |
| 541 | if (power_of_two_plus_one) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 542 | if (base != nullptr) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 543 | // If the scale requires explicitly using the index as the base, but a |
| 544 | // base is already part of the match, then the (1 << N + 1) scale factor |
| 545 | // can't be folded into the match and the entire index * scale |
| 546 | // calculation must be computed separately. |
| 547 | index = scale_expression; |
| 548 | scale = 0; |
| 549 | } else { |
| 550 | base = index; |
| 551 | } |
| 552 | } |
| 553 | base_ = base; |
| 554 | displacement_ = displacement; |
| 555 | index_ = index; |
| 556 | scale_ = scale; |
| 557 | matches_ = true; |
| 558 | } |
| 559 | }; |
| 560 | |
| 561 | typedef BaseWithIndexAndDisplacementMatcher<Int32AddMatcher> |
| 562 | BaseWithIndexAndDisplacement32Matcher; |
| 563 | typedef BaseWithIndexAndDisplacementMatcher<Int64AddMatcher> |
| 564 | BaseWithIndexAndDisplacement64Matcher; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 565 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 566 | struct BranchMatcher : public NodeMatcher { |
| 567 | explicit BranchMatcher(Node* branch); |
| 568 | |
| 569 | bool Matched() const { return if_true_ && if_false_; } |
| 570 | |
| 571 | Node* Branch() const { return node(); } |
| 572 | Node* IfTrue() const { return if_true_; } |
| 573 | Node* IfFalse() const { return if_false_; } |
| 574 | |
| 575 | private: |
| 576 | Node* if_true_; |
| 577 | Node* if_false_; |
| 578 | }; |
| 579 | |
| 580 | |
| 581 | struct DiamondMatcher : public NodeMatcher { |
| 582 | explicit DiamondMatcher(Node* merge); |
| 583 | |
| 584 | bool Matched() const { return branch_; } |
| 585 | bool IfProjectionsAreOwned() const { |
| 586 | return if_true_->OwnedBy(node()) && if_false_->OwnedBy(node()); |
| 587 | } |
| 588 | |
| 589 | Node* Branch() const { return branch_; } |
| 590 | Node* IfTrue() const { return if_true_; } |
| 591 | Node* IfFalse() const { return if_false_; } |
| 592 | Node* Merge() const { return node(); } |
| 593 | |
| 594 | Node* TrueInputOf(Node* phi) const { |
| 595 | DCHECK(IrOpcode::IsPhiOpcode(phi->opcode())); |
| 596 | DCHECK_EQ(3, phi->InputCount()); |
| 597 | DCHECK_EQ(Merge(), phi->InputAt(2)); |
| 598 | return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 0 : 1); |
| 599 | } |
| 600 | |
| 601 | Node* FalseInputOf(Node* phi) const { |
| 602 | DCHECK(IrOpcode::IsPhiOpcode(phi->opcode())); |
| 603 | DCHECK_EQ(3, phi->InputCount()); |
| 604 | DCHECK_EQ(Merge(), phi->InputAt(2)); |
| 605 | return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 1 : 0); |
| 606 | } |
| 607 | |
| 608 | private: |
| 609 | Node* branch_; |
| 610 | Node* if_true_; |
| 611 | Node* if_false_; |
| 612 | }; |
| 613 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 614 | } // namespace compiler |
| 615 | } // namespace internal |
| 616 | } // namespace v8 |
| 617 | |
| 618 | #endif // V8_COMPILER_NODE_MATCHERS_H_ |