OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_COMPILER_NODE_MATCHERS_H_ | 5 #ifndef V8_COMPILER_NODE_MATCHERS_H_ |
6 #define V8_COMPILER_NODE_MATCHERS_H_ | 6 #define V8_COMPILER_NODE_MATCHERS_H_ |
7 | 7 |
8 #include <cmath> | 8 #include <cmath> |
9 | 9 |
10 #include "src/compiler/node.h" | 10 #include "src/compiler/node.h" |
(...skipping 115 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
126 | 126 |
127 // For shorter pattern matching code, this struct matches both the left and | 127 // For shorter pattern matching code, this struct matches both the left and |
128 // right hand sides of a binary operation and can put constants on the right | 128 // right hand sides of a binary operation and can put constants on the right |
129 // if they appear on the left hand side of a commutative operation. | 129 // if they appear on the left hand side of a commutative operation. |
130 template <typename Left, typename Right> | 130 template <typename Left, typename Right> |
131 struct BinopMatcher : public NodeMatcher { | 131 struct BinopMatcher : public NodeMatcher { |
132 explicit BinopMatcher(Node* node) | 132 explicit BinopMatcher(Node* node) |
133 : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) { | 133 : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) { |
134 if (HasProperty(Operator::kCommutative)) PutConstantOnRight(); | 134 if (HasProperty(Operator::kCommutative)) PutConstantOnRight(); |
135 } | 135 } |
| 136 BinopMatcher(Node* node, bool allow_input_swap) |
| 137 : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) { |
| 138 if (allow_input_swap) PutConstantOnRight(); |
| 139 } |
136 | 140 |
137 typedef Left LeftMatcher; | 141 typedef Left LeftMatcher; |
138 typedef Right RightMatcher; | 142 typedef Right RightMatcher; |
139 | 143 |
140 const Left& left() const { return left_; } | 144 const Left& left() const { return left_; } |
141 const Right& right() const { return right_; } | 145 const Right& right() const { return right_; } |
142 | 146 |
143 bool IsFoldable() const { return left().HasValue() && right().HasValue(); } | 147 bool IsFoldable() const { return left().HasValue() && right().HasValue(); } |
144 bool LeftEqualsRight() const { return left().node() == right().node(); } | 148 bool LeftEqualsRight() const { return left().node() == right().node(); } |
145 | 149 |
(...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
228 typedef ScaleMatcher<Int64BinopMatcher, IrOpcode::kInt64Mul, | 232 typedef ScaleMatcher<Int64BinopMatcher, IrOpcode::kInt64Mul, |
229 IrOpcode::kWord64Shl> Int64ScaleMatcher; | 233 IrOpcode::kWord64Shl> Int64ScaleMatcher; |
230 | 234 |
231 | 235 |
232 template <class BinopMatcher, IrOpcode::Value kAddOpcode, | 236 template <class BinopMatcher, IrOpcode::Value kAddOpcode, |
233 IrOpcode::Value kMulOpcode, IrOpcode::Value kShiftOpcode> | 237 IrOpcode::Value kMulOpcode, IrOpcode::Value kShiftOpcode> |
234 struct AddMatcher : public BinopMatcher { | 238 struct AddMatcher : public BinopMatcher { |
235 static const IrOpcode::Value kOpcode = kAddOpcode; | 239 static const IrOpcode::Value kOpcode = kAddOpcode; |
236 typedef ScaleMatcher<BinopMatcher, kMulOpcode, kShiftOpcode> Matcher; | 240 typedef ScaleMatcher<BinopMatcher, kMulOpcode, kShiftOpcode> Matcher; |
237 | 241 |
| 242 AddMatcher(Node* node, bool allow_input_swap) |
| 243 : BinopMatcher(node, allow_input_swap), |
| 244 scale_(-1), |
| 245 power_of_two_plus_one_(false) { |
| 246 Initialize(node, allow_input_swap); |
| 247 } |
238 explicit AddMatcher(Node* node) | 248 explicit AddMatcher(Node* node) |
239 : BinopMatcher(node), scale_(-1), power_of_two_plus_one_(false) { | 249 : BinopMatcher(node, node->op()->HasProperty(Operator::kCommutative)), |
| 250 scale_(-1), |
| 251 power_of_two_plus_one_(false) { |
| 252 Initialize(node, node->op()->HasProperty(Operator::kCommutative)); |
| 253 } |
| 254 |
| 255 bool HasIndexInput() const { return scale_ != -1; } |
| 256 Node* IndexInput() const { |
| 257 DCHECK(HasIndexInput()); |
| 258 return this->left().node()->InputAt(0); |
| 259 } |
| 260 int scale() const { |
| 261 DCHECK(HasIndexInput()); |
| 262 return scale_; |
| 263 } |
| 264 bool power_of_two_plus_one() const { return power_of_two_plus_one_; } |
| 265 |
| 266 private: |
| 267 void Initialize(Node* node, bool allow_input_swap) { |
240 Matcher left_matcher(this->left().node(), true); | 268 Matcher left_matcher(this->left().node(), true); |
241 if (left_matcher.matches()) { | 269 if (left_matcher.matches()) { |
242 scale_ = left_matcher.scale(); | 270 scale_ = left_matcher.scale(); |
243 power_of_two_plus_one_ = left_matcher.power_of_two_plus_one(); | 271 power_of_two_plus_one_ = left_matcher.power_of_two_plus_one(); |
244 return; | 272 return; |
245 } | 273 } |
246 | 274 |
247 if (!this->HasProperty(Operator::kCommutative)) { | 275 if (!allow_input_swap) { |
248 return; | 276 return; |
249 } | 277 } |
250 | 278 |
251 Matcher right_matcher(this->right().node(), true); | 279 Matcher right_matcher(this->right().node(), true); |
252 if (right_matcher.matches()) { | 280 if (right_matcher.matches()) { |
253 scale_ = right_matcher.scale(); | 281 scale_ = right_matcher.scale(); |
254 power_of_two_plus_one_ = right_matcher.power_of_two_plus_one(); | 282 power_of_two_plus_one_ = right_matcher.power_of_two_plus_one(); |
255 this->SwapInputs(); | 283 this->SwapInputs(); |
256 return; | 284 return; |
257 } | 285 } |
258 | 286 |
259 if (this->right().opcode() == kAddOpcode && | 287 if (this->right().opcode() == kAddOpcode && |
260 this->left().opcode() != kAddOpcode) { | 288 this->left().opcode() != kAddOpcode) { |
261 this->SwapInputs(); | 289 this->SwapInputs(); |
262 } | 290 } |
263 } | 291 } |
264 | 292 |
265 bool HasIndexInput() const { return scale_ != -1; } | |
266 Node* IndexInput() const { | |
267 DCHECK(HasIndexInput()); | |
268 return this->left().node()->InputAt(0); | |
269 } | |
270 int scale() const { | |
271 DCHECK(HasIndexInput()); | |
272 return scale_; | |
273 } | |
274 bool power_of_two_plus_one() const { return power_of_two_plus_one_; } | |
275 | |
276 private: | |
277 int scale_; | 293 int scale_; |
278 bool power_of_two_plus_one_; | 294 bool power_of_two_plus_one_; |
279 }; | 295 }; |
280 | 296 |
281 typedef AddMatcher<Int32BinopMatcher, IrOpcode::kInt32Add, IrOpcode::kInt32Mul, | 297 typedef AddMatcher<Int32BinopMatcher, IrOpcode::kInt32Add, IrOpcode::kInt32Mul, |
282 IrOpcode::kWord32Shl> Int32AddMatcher; | 298 IrOpcode::kWord32Shl> Int32AddMatcher; |
283 typedef AddMatcher<Int64BinopMatcher, IrOpcode::kInt64Add, IrOpcode::kInt64Mul, | 299 typedef AddMatcher<Int64BinopMatcher, IrOpcode::kInt64Add, IrOpcode::kInt64Mul, |
284 IrOpcode::kWord64Shl> Int64AddMatcher; | 300 IrOpcode::kWord64Shl> Int64AddMatcher; |
285 | 301 |
286 | 302 |
287 template <class AddMatcher> | 303 template <class AddMatcher> |
288 struct BaseWithIndexAndDisplacementMatcher { | 304 struct BaseWithIndexAndDisplacementMatcher { |
| 305 BaseWithIndexAndDisplacementMatcher(Node* node, bool allow_input_swap) |
| 306 : matches_(false), |
| 307 index_(NULL), |
| 308 scale_(0), |
| 309 base_(NULL), |
| 310 displacement_(NULL) { |
| 311 Initialize(node, allow_input_swap); |
| 312 } |
| 313 |
289 explicit BaseWithIndexAndDisplacementMatcher(Node* node) | 314 explicit BaseWithIndexAndDisplacementMatcher(Node* node) |
290 : matches_(false), | 315 : matches_(false), |
291 index_(NULL), | 316 index_(NULL), |
292 scale_(0), | 317 scale_(0), |
293 base_(NULL), | 318 base_(NULL), |
294 displacement_(NULL) { | 319 displacement_(NULL) { |
| 320 Initialize(node, node->op()->HasProperty(Operator::kCommutative)); |
| 321 } |
| 322 |
| 323 bool matches() const { return matches_; } |
| 324 Node* index() const { return index_; } |
| 325 int scale() const { return scale_; } |
| 326 Node* base() const { return base_; } |
| 327 Node* displacement() const { return displacement_; } |
| 328 |
| 329 private: |
| 330 bool matches_; |
| 331 Node* index_; |
| 332 int scale_; |
| 333 Node* base_; |
| 334 Node* displacement_; |
| 335 |
| 336 void Initialize(Node* node, bool allow_input_swap) { |
295 // The BaseWithIndexAndDisplacementMatcher canonicalizes the order of | 337 // The BaseWithIndexAndDisplacementMatcher canonicalizes the order of |
296 // displacements and scale factors that are used as inputs, so instead of | 338 // displacements and scale factors that are used as inputs, so instead of |
297 // enumerating all possible patterns by brute force, checking for node | 339 // enumerating all possible patterns by brute force, checking for node |
298 // clusters using the following templates in the following order suffices to | 340 // clusters using the following templates in the following order suffices to |
299 // find all of the interesting cases (S = index * scale, B = base input, D = | 341 // find all of the interesting cases (S = index * scale, B = base input, D = |
300 // displacement input): | 342 // displacement input): |
301 // (S + (B + D)) | 343 // (S + (B + D)) |
302 // (S + (B + B)) | 344 // (S + (B + B)) |
303 // (S + D) | 345 // (S + D) |
304 // (S + B) | 346 // (S + B) |
305 // ((S + D) + B) | 347 // ((S + D) + B) |
306 // ((S + B) + D) | 348 // ((S + B) + D) |
307 // ((B + D) + B) | 349 // ((B + D) + B) |
308 // ((B + B) + D) | 350 // ((B + B) + D) |
309 // (B + D) | 351 // (B + D) |
310 // (B + B) | 352 // (B + B) |
311 if (node->InputCount() < 2) return; | 353 if (node->InputCount() < 2) return; |
312 AddMatcher m(node); | 354 AddMatcher m(node, allow_input_swap); |
313 Node* left = m.left().node(); | 355 Node* left = m.left().node(); |
314 Node* right = m.right().node(); | 356 Node* right = m.right().node(); |
315 Node* displacement = NULL; | 357 Node* displacement = NULL; |
316 Node* base = NULL; | 358 Node* base = NULL; |
317 Node* index = NULL; | 359 Node* index = NULL; |
318 Node* scale_expression = NULL; | 360 Node* scale_expression = NULL; |
319 bool power_of_two_plus_one = false; | 361 bool power_of_two_plus_one = false; |
320 int scale = 0; | 362 int scale = 0; |
321 if (m.HasIndexInput() && left->OwnedBy(node)) { | 363 if (m.HasIndexInput() && left->OwnedBy(node)) { |
322 index = m.IndexInput(); | 364 index = m.IndexInput(); |
(...skipping 103 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
426 } else { | 468 } else { |
427 base = index; | 469 base = index; |
428 } | 470 } |
429 } | 471 } |
430 base_ = base; | 472 base_ = base; |
431 displacement_ = displacement; | 473 displacement_ = displacement; |
432 index_ = index; | 474 index_ = index; |
433 scale_ = scale; | 475 scale_ = scale; |
434 matches_ = true; | 476 matches_ = true; |
435 } | 477 } |
436 | |
437 bool matches() const { return matches_; } | |
438 Node* index() const { return index_; } | |
439 int scale() const { return scale_; } | |
440 Node* base() const { return base_; } | |
441 Node* displacement() const { return displacement_; } | |
442 | |
443 private: | |
444 bool matches_; | |
445 | |
446 protected: | |
447 Node* index_; | |
448 int scale_; | |
449 Node* base_; | |
450 Node* displacement_; | |
451 }; | 478 }; |
452 | 479 |
453 typedef BaseWithIndexAndDisplacementMatcher<Int32AddMatcher> | 480 typedef BaseWithIndexAndDisplacementMatcher<Int32AddMatcher> |
454 BaseWithIndexAndDisplacement32Matcher; | 481 BaseWithIndexAndDisplacement32Matcher; |
455 typedef BaseWithIndexAndDisplacementMatcher<Int64AddMatcher> | 482 typedef BaseWithIndexAndDisplacementMatcher<Int64AddMatcher> |
456 BaseWithIndexAndDisplacement64Matcher; | 483 BaseWithIndexAndDisplacement64Matcher; |
457 | 484 |
458 } // namespace compiler | 485 } // namespace compiler |
459 } // namespace internal | 486 } // namespace internal |
460 } // namespace v8 | 487 } // namespace v8 |
461 | 488 |
462 #endif // V8_COMPILER_NODE_MATCHERS_H_ | 489 #endif // V8_COMPILER_NODE_MATCHERS_H_ |
OLD | NEW |