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 "src/compiler/generic-node.h" | 8 #include "src/compiler/generic-node.h" |
9 #include "src/compiler/generic-node-inl.h" | 9 #include "src/compiler/generic-node-inl.h" |
10 #include "src/compiler/node.h" | 10 #include "src/compiler/node.h" |
(...skipping 21 matching lines...) Expand all Loading... |
32 bool Is##Opcode() const { return opcode() == IrOpcode::k##Opcode; } | 32 bool Is##Opcode() const { return opcode() == IrOpcode::k##Opcode; } |
33 ALL_OP_LIST(DEFINE_IS_OPCODE) | 33 ALL_OP_LIST(DEFINE_IS_OPCODE) |
34 #undef DEFINE_IS_OPCODE | 34 #undef DEFINE_IS_OPCODE |
35 | 35 |
36 private: | 36 private: |
37 Node* node_; | 37 Node* node_; |
38 }; | 38 }; |
39 | 39 |
40 | 40 |
41 // A pattern matcher for abitrary value constants. | 41 // A pattern matcher for abitrary value constants. |
42 template <typename T, IrOpcode::Value kOpcode> | 42 template <typename T, IrOpcode::Value kMatchOpcode> |
43 struct ValueMatcher : public NodeMatcher { | 43 struct ValueMatcher : public NodeMatcher { |
| 44 typedef T ValueType; |
| 45 static const IrOpcode::Value kOpcode = kMatchOpcode; |
| 46 |
44 explicit ValueMatcher(Node* node) | 47 explicit ValueMatcher(Node* node) |
45 : NodeMatcher(node), value_(), has_value_(opcode() == kOpcode) { | 48 : NodeMatcher(node), value_(), has_value_(opcode() == kOpcode) { |
46 if (has_value_) { | 49 if (has_value_) { |
47 value_ = OpParameter<T>(node); | 50 value_ = OpParameter<T>(node); |
48 } | 51 } |
49 } | 52 } |
50 | 53 |
51 bool HasValue() const { return has_value_; } | 54 bool HasValue() const { return has_value_; } |
52 const T& Value() const { | 55 const T& Value() const { |
53 DCHECK(HasValue()); | 56 DCHECK(HasValue()); |
(...skipping 63 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
117 // For shorter pattern matching code, this struct matches both the left and | 120 // For shorter pattern matching code, this struct matches both the left and |
118 // right hand sides of a binary operation and can put constants on the right | 121 // right hand sides of a binary operation and can put constants on the right |
119 // if they appear on the left hand side of a commutative operation. | 122 // if they appear on the left hand side of a commutative operation. |
120 template <typename Left, typename Right> | 123 template <typename Left, typename Right> |
121 struct BinopMatcher : public NodeMatcher { | 124 struct BinopMatcher : public NodeMatcher { |
122 explicit BinopMatcher(Node* node) | 125 explicit BinopMatcher(Node* node) |
123 : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) { | 126 : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) { |
124 if (HasProperty(Operator::kCommutative)) PutConstantOnRight(); | 127 if (HasProperty(Operator::kCommutative)) PutConstantOnRight(); |
125 } | 128 } |
126 | 129 |
| 130 typedef Left LeftMatcher; |
| 131 typedef Right RightMatcher; |
| 132 |
127 const Left& left() const { return left_; } | 133 const Left& left() const { return left_; } |
128 const Right& right() const { return right_; } | 134 const Right& right() const { return right_; } |
129 | 135 |
130 bool IsFoldable() const { return left().HasValue() && right().HasValue(); } | 136 bool IsFoldable() const { return left().HasValue() && right().HasValue(); } |
131 bool LeftEqualsRight() const { return left().node() == right().node(); } | 137 bool LeftEqualsRight() const { return left().node() == right().node(); } |
132 | 138 |
133 protected: | 139 protected: |
134 void SwapInputs() { | 140 void SwapInputs() { |
135 std::swap(left_, right_); | 141 std::swap(left_, right_); |
136 node()->ReplaceInput(0, left().node()); | 142 node()->ReplaceInput(0, left().node()); |
(...skipping 13 matching lines...) Expand all Loading... |
150 | 156 |
151 typedef BinopMatcher<Int32Matcher, Int32Matcher> Int32BinopMatcher; | 157 typedef BinopMatcher<Int32Matcher, Int32Matcher> Int32BinopMatcher; |
152 typedef BinopMatcher<Uint32Matcher, Uint32Matcher> Uint32BinopMatcher; | 158 typedef BinopMatcher<Uint32Matcher, Uint32Matcher> Uint32BinopMatcher; |
153 typedef BinopMatcher<Int64Matcher, Int64Matcher> Int64BinopMatcher; | 159 typedef BinopMatcher<Int64Matcher, Int64Matcher> Int64BinopMatcher; |
154 typedef BinopMatcher<Uint64Matcher, Uint64Matcher> Uint64BinopMatcher; | 160 typedef BinopMatcher<Uint64Matcher, Uint64Matcher> Uint64BinopMatcher; |
155 typedef BinopMatcher<IntPtrMatcher, IntPtrMatcher> IntPtrBinopMatcher; | 161 typedef BinopMatcher<IntPtrMatcher, IntPtrMatcher> IntPtrBinopMatcher; |
156 typedef BinopMatcher<UintPtrMatcher, UintPtrMatcher> UintPtrBinopMatcher; | 162 typedef BinopMatcher<UintPtrMatcher, UintPtrMatcher> UintPtrBinopMatcher; |
157 typedef BinopMatcher<Float64Matcher, Float64Matcher> Float64BinopMatcher; | 163 typedef BinopMatcher<Float64Matcher, Float64Matcher> Float64BinopMatcher; |
158 typedef BinopMatcher<NumberMatcher, NumberMatcher> NumberBinopMatcher; | 164 typedef BinopMatcher<NumberMatcher, NumberMatcher> NumberBinopMatcher; |
159 | 165 |
160 struct Int32AddMatcher : public Int32BinopMatcher { | 166 template <class BinopMatcher, IrOpcode::Value kAddOpcode, |
161 explicit Int32AddMatcher(Node* node) | 167 IrOpcode::Value kMulOpcode, IrOpcode::Value kShiftOpcode> |
162 : Int32BinopMatcher(node), scale_exponent_(-1) { | 168 struct AddMatcher : public BinopMatcher { |
163 PutScaledInputOnLeft(); | 169 static const IrOpcode::Value kOpcode = kAddOpcode; |
| 170 |
| 171 explicit AddMatcher(Node* node) : BinopMatcher(node), scale_exponent_(-1) { |
| 172 if (this->HasProperty(Operator::kCommutative)) PutScaledInputOnLeft(); |
164 } | 173 } |
165 | 174 |
166 bool HasScaledInput() const { return scale_exponent_ != -1; } | 175 bool HasScaledInput() const { return scale_exponent_ != -1; } |
167 Node* ScaledInput() const { | 176 Node* ScaledInput() const { |
168 DCHECK(HasScaledInput()); | 177 DCHECK(HasScaledInput()); |
169 return left().node()->InputAt(0); | 178 return this->left().node()->InputAt(0); |
170 } | 179 } |
171 int ScaleExponent() const { | 180 int ScaleExponent() const { |
172 DCHECK(HasScaledInput()); | 181 DCHECK(HasScaledInput()); |
173 return scale_exponent_; | 182 return scale_exponent_; |
174 } | 183 } |
175 | 184 |
176 private: | 185 private: |
177 int GetInputScaleExponent(Node* node) const { | 186 int GetInputScaleExponent(Node* node) const { |
178 if (node->opcode() == IrOpcode::kWord32Shl) { | 187 if (node->opcode() == kShiftOpcode) { |
179 Int32BinopMatcher m(node); | 188 BinopMatcher m(node); |
180 if (m.right().HasValue()) { | 189 if (m.right().HasValue()) { |
181 int32_t value = m.right().Value(); | 190 typename BinopMatcher::RightMatcher::ValueType value = |
| 191 m.right().Value(); |
182 if (value >= 0 && value <= 3) { | 192 if (value >= 0 && value <= 3) { |
183 return value; | 193 return value; |
184 } | 194 } |
185 } | 195 } |
186 } else if (node->opcode() == IrOpcode::kInt32Mul) { | 196 } else if (node->opcode() == kMulOpcode) { |
187 Int32BinopMatcher m(node); | 197 BinopMatcher m(node); |
188 if (m.right().HasValue()) { | 198 if (m.right().HasValue()) { |
189 int32_t value = m.right().Value(); | 199 typename BinopMatcher::RightMatcher::ValueType value = |
| 200 m.right().Value(); |
190 if (value == 1) { | 201 if (value == 1) { |
191 return 0; | 202 return 0; |
192 } else if (value == 2) { | 203 } else if (value == 2) { |
193 return 1; | 204 return 1; |
194 } else if (value == 4) { | 205 } else if (value == 4) { |
195 return 2; | 206 return 2; |
196 } else if (value == 8) { | 207 } else if (value == 8) { |
197 return 3; | 208 return 3; |
198 } | 209 } |
199 } | 210 } |
200 } | 211 } |
201 return -1; | 212 return -1; |
202 } | 213 } |
203 | 214 |
204 void PutScaledInputOnLeft() { | 215 void PutScaledInputOnLeft() { |
205 scale_exponent_ = GetInputScaleExponent(right().node()); | 216 scale_exponent_ = GetInputScaleExponent(this->right().node()); |
206 if (scale_exponent_ >= 0) { | 217 if (scale_exponent_ >= 0) { |
207 int left_scale_exponent = GetInputScaleExponent(left().node()); | 218 int left_scale_exponent = GetInputScaleExponent(this->left().node()); |
208 if (left_scale_exponent == -1) { | 219 if (left_scale_exponent == -1) { |
209 SwapInputs(); | 220 this->SwapInputs(); |
210 } else { | 221 } else { |
211 scale_exponent_ = left_scale_exponent; | 222 scale_exponent_ = left_scale_exponent; |
212 } | 223 } |
213 } else { | 224 } else { |
214 scale_exponent_ = GetInputScaleExponent(left().node()); | 225 scale_exponent_ = GetInputScaleExponent(this->left().node()); |
215 if (scale_exponent_ == -1) { | 226 if (scale_exponent_ == -1) { |
216 if (right().opcode() == IrOpcode::kInt32Add && | 227 if (this->right().opcode() == kAddOpcode && |
217 left().opcode() != IrOpcode::kInt32Add) { | 228 this->left().opcode() != kAddOpcode) { |
218 SwapInputs(); | 229 this->SwapInputs(); |
219 } | 230 } |
220 } | 231 } |
221 } | 232 } |
222 } | 233 } |
223 | 234 |
224 int scale_exponent_; | 235 int scale_exponent_; |
225 }; | 236 }; |
226 | 237 |
| 238 typedef AddMatcher<Int32BinopMatcher, IrOpcode::kInt32Add, IrOpcode::kInt32Mul, |
| 239 IrOpcode::kWord32Shl> Int32AddMatcher; |
| 240 typedef AddMatcher<Int64BinopMatcher, IrOpcode::kInt64Add, IrOpcode::kInt64Mul, |
| 241 IrOpcode::kWord64Shl> Int64AddMatcher; |
| 242 |
| 243 template <class AddMatcher> |
227 struct ScaledWithOffsetMatcher { | 244 struct ScaledWithOffsetMatcher { |
228 explicit ScaledWithOffsetMatcher(Node* node) | 245 explicit ScaledWithOffsetMatcher(Node* node) |
229 : matches_(false), | 246 : matches_(false), |
230 scaled_(NULL), | 247 scaled_(NULL), |
231 scale_exponent_(0), | 248 scale_exponent_(0), |
232 offset_(NULL), | 249 offset_(NULL), |
233 constant_(NULL) { | 250 constant_(NULL) { |
234 if (node->opcode() != IrOpcode::kInt32Add) return; | 251 // The ScaledWithOffsetMatcher canonicalizes the order of constants and |
235 | 252 // scale factors that are used as inputs, so instead of enumerating all |
236 // The Int32AddMatcher canonicalizes the order of constants and scale | 253 // possible patterns by brute force, checking for node clusters using the |
237 // factors that are used as inputs, so instead of enumerating all possible | 254 // following templates in the following order suffices to find all of the |
238 // patterns by brute force, checking for node clusters using the following | 255 // interesting cases (S = scaled input, O = offset input, C = constant |
239 // templates in the following order suffices to find all of the interesting | 256 // input): |
240 // cases (S = scaled input, O = offset input, C = constant input): | |
241 // (S + (O + C)) | 257 // (S + (O + C)) |
242 // (S + (O + O)) | 258 // (S + (O + O)) |
243 // (S + C) | 259 // (S + C) |
244 // (S + O) | 260 // (S + O) |
245 // ((S + C) + O) | 261 // ((S + C) + O) |
246 // ((S + O) + C) | 262 // ((S + O) + C) |
247 // ((O + C) + O) | 263 // ((O + C) + O) |
248 // ((O + O) + C) | 264 // ((O + O) + C) |
249 // (O + C) | 265 // (O + C) |
250 // (O + O) | 266 // (O + O) |
251 Int32AddMatcher base_matcher(node); | 267 if (node->InputCount() < 2) return; |
| 268 AddMatcher base_matcher(node); |
252 Node* left = base_matcher.left().node(); | 269 Node* left = base_matcher.left().node(); |
253 Node* right = base_matcher.right().node(); | 270 Node* right = base_matcher.right().node(); |
254 if (base_matcher.HasScaledInput() && left->OwnedBy(node)) { | 271 if (base_matcher.HasScaledInput() && left->OwnedBy(node)) { |
255 scaled_ = base_matcher.ScaledInput(); | 272 scaled_ = base_matcher.ScaledInput(); |
256 scale_exponent_ = base_matcher.ScaleExponent(); | 273 scale_exponent_ = base_matcher.ScaleExponent(); |
257 if (right->opcode() == IrOpcode::kInt32Add && right->OwnedBy(node)) { | 274 if (right->opcode() == AddMatcher::kOpcode && right->OwnedBy(node)) { |
258 Int32AddMatcher right_matcher(right); | 275 AddMatcher right_matcher(right); |
259 if (right_matcher.right().HasValue()) { | 276 if (right_matcher.right().HasValue()) { |
260 // (S + (O + C)) | 277 // (S + (O + C)) |
261 offset_ = right_matcher.left().node(); | 278 offset_ = right_matcher.left().node(); |
262 constant_ = right_matcher.right().node(); | 279 constant_ = right_matcher.right().node(); |
263 } else { | 280 } else { |
264 // (S + (O + O)) | 281 // (S + (O + O)) |
265 offset_ = right; | 282 offset_ = right; |
266 } | 283 } |
267 } else if (base_matcher.right().HasValue()) { | 284 } else if (base_matcher.right().HasValue()) { |
268 // (S + C) | 285 // (S + C) |
269 constant_ = right; | 286 constant_ = right; |
270 } else { | 287 } else { |
271 // (S + O) | 288 // (S + O) |
272 offset_ = right; | 289 offset_ = right; |
273 } | 290 } |
274 } else { | 291 } else { |
275 if (left->opcode() == IrOpcode::kInt32Add && left->OwnedBy(node)) { | 292 if (left->opcode() == AddMatcher::kOpcode && left->OwnedBy(node)) { |
276 Int32AddMatcher left_matcher(left); | 293 AddMatcher left_matcher(left); |
277 Node* left_left = left_matcher.left().node(); | 294 Node* left_left = left_matcher.left().node(); |
278 Node* left_right = left_matcher.right().node(); | 295 Node* left_right = left_matcher.right().node(); |
279 if (left_matcher.HasScaledInput() && left_left->OwnedBy(left)) { | 296 if (left_matcher.HasScaledInput() && left_left->OwnedBy(left)) { |
280 scaled_ = left_matcher.ScaledInput(); | 297 scaled_ = left_matcher.ScaledInput(); |
281 scale_exponent_ = left_matcher.ScaleExponent(); | 298 scale_exponent_ = left_matcher.ScaleExponent(); |
282 if (left_matcher.right().HasValue()) { | 299 if (left_matcher.right().HasValue()) { |
283 // ((S + C) + O) | 300 // ((S + C) + O) |
284 constant_ = left_right; | 301 constant_ = left_right; |
285 offset_ = right; | 302 offset_ = right; |
286 } else if (base_matcher.right().HasValue()) { | 303 } else if (base_matcher.right().HasValue()) { |
(...skipping 27 matching lines...) Expand all Loading... |
314 // (O + C) | 331 // (O + C) |
315 offset_ = left; | 332 offset_ = left; |
316 constant_ = right; | 333 constant_ = right; |
317 } else { | 334 } else { |
318 // (O + O) | 335 // (O + O) |
319 offset_ = left; | 336 offset_ = left; |
320 scaled_ = right; | 337 scaled_ = right; |
321 } | 338 } |
322 } | 339 } |
323 } | 340 } |
| 341 int64_t value = 0; |
| 342 if (constant_ != NULL) { |
| 343 switch (constant_->opcode()) { |
| 344 case IrOpcode::kInt32Constant: { |
| 345 value = OpParameter<int32_t>(constant_); |
| 346 break; |
| 347 } |
| 348 case IrOpcode::kInt64Constant: { |
| 349 value = OpParameter<int64_t>(constant_); |
| 350 break; |
| 351 } |
| 352 default: |
| 353 UNREACHABLE(); |
| 354 break; |
| 355 } |
| 356 if (value == 0) { |
| 357 constant_ = NULL; |
| 358 } |
| 359 } |
324 matches_ = true; | 360 matches_ = true; |
325 } | 361 } |
326 | 362 |
327 bool matches() const { return matches_; } | 363 bool matches() const { return matches_; } |
328 Node* scaled() const { return scaled_; } | 364 Node* scaled() const { return scaled_; } |
329 int scale_exponent() const { return scale_exponent_; } | 365 int scale_exponent() const { return scale_exponent_; } |
330 Node* offset() const { return offset_; } | 366 Node* offset() const { return offset_; } |
331 Node* constant() const { return constant_; } | 367 Node* constant() const { return constant_; } |
332 | 368 |
333 private: | 369 private: |
334 bool matches_; | 370 bool matches_; |
335 | 371 |
336 protected: | 372 protected: |
337 Node* scaled_; | 373 Node* scaled_; |
338 int scale_exponent_; | 374 int scale_exponent_; |
339 Node* offset_; | 375 Node* offset_; |
340 Node* constant_; | 376 Node* constant_; |
341 }; | 377 }; |
342 | 378 |
| 379 typedef ScaledWithOffsetMatcher<Int32AddMatcher> ScaledWithOffset32Matcher; |
| 380 typedef ScaledWithOffsetMatcher<Int64AddMatcher> ScaledWithOffset64Matcher; |
| 381 |
343 } // namespace compiler | 382 } // namespace compiler |
344 } // namespace internal | 383 } // namespace internal |
345 } // namespace v8 | 384 } // namespace v8 |
346 | 385 |
347 #endif // V8_COMPILER_NODE_MATCHERS_H_ | 386 #endif // V8_COMPILER_NODE_MATCHERS_H_ |
OLD | NEW |