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 #include "src/bootstrapper.h" | 5 #include "src/bootstrapper.h" |
6 #include "src/compiler/graph-inl.h" | 6 #include "src/compiler/graph-inl.h" |
| 7 #include "src/compiler/graph-reducer.h" |
7 #include "src/compiler/js-operator.h" | 8 #include "src/compiler/js-operator.h" |
8 #include "src/compiler/node.h" | 9 #include "src/compiler/node.h" |
9 #include "src/compiler/node-properties-inl.h" | 10 #include "src/compiler/node-properties-inl.h" |
10 #include "src/compiler/node-properties.h" | 11 #include "src/compiler/node-properties.h" |
11 #include "src/compiler/simplified-operator.h" | 12 #include "src/compiler/simplified-operator.h" |
12 #include "src/compiler/typer.h" | 13 #include "src/compiler/typer.h" |
13 | 14 |
14 namespace v8 { | 15 namespace v8 { |
15 namespace internal { | 16 namespace internal { |
16 namespace compiler { | 17 namespace compiler { |
(...skipping 193 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
210 decorator_ = new (zone) Decorator(this); | 211 decorator_ = new (zone) Decorator(this); |
211 graph_->AddDecorator(decorator_); | 212 graph_->AddDecorator(decorator_); |
212 } | 213 } |
213 | 214 |
214 | 215 |
215 Typer::~Typer() { | 216 Typer::~Typer() { |
216 graph_->RemoveDecorator(decorator_); | 217 graph_->RemoveDecorator(decorator_); |
217 } | 218 } |
218 | 219 |
219 | 220 |
220 class Typer::Visitor : public NullNodeVisitor { | 221 class Typer::Visitor : public Reducer { |
221 public: | 222 public: |
222 explicit Visitor(Typer* typer) : typer_(typer) {} | 223 explicit Visitor(Typer* typer) : typer_(typer) {} |
223 | 224 |
| 225 virtual Reduction Reduce(Node* node) OVERRIDE { |
| 226 if (node->op()->ValueOutputCount() == 0) return NoChange(); |
| 227 switch (node->opcode()) { |
| 228 #define DECLARE_CASE(x) \ |
| 229 case IrOpcode::k##x: \ |
| 230 return UpdateBounds(node, TypeBinaryOp(node, x##Typer)); |
| 231 JS_SIMPLE_BINOP_LIST(DECLARE_CASE) |
| 232 #undef DECLARE_CASE |
| 233 |
| 234 #define DECLARE_CASE(x) \ |
| 235 case IrOpcode::k##x: \ |
| 236 return UpdateBounds(node, Type##x(node)); |
| 237 DECLARE_CASE(Start) |
| 238 // VALUE_OP_LIST without JS_SIMPLE_BINOP_LIST: |
| 239 COMMON_OP_LIST(DECLARE_CASE) |
| 240 SIMPLIFIED_OP_LIST(DECLARE_CASE) |
| 241 MACHINE_OP_LIST(DECLARE_CASE) |
| 242 JS_SIMPLE_UNOP_LIST(DECLARE_CASE) |
| 243 JS_OBJECT_OP_LIST(DECLARE_CASE) |
| 244 JS_CONTEXT_OP_LIST(DECLARE_CASE) |
| 245 JS_OTHER_OP_LIST(DECLARE_CASE) |
| 246 #undef DECLARE_CASE |
| 247 |
| 248 #define DECLARE_CASE(x) case IrOpcode::k##x: |
| 249 DECLARE_CASE(End) |
| 250 INNER_CONTROL_OP_LIST(DECLARE_CASE) |
| 251 #undef DECLARE_CASE |
| 252 break; |
| 253 } |
| 254 return NoChange(); |
| 255 } |
| 256 |
224 Bounds TypeNode(Node* node) { | 257 Bounds TypeNode(Node* node) { |
225 switch (node->opcode()) { | 258 switch (node->opcode()) { |
226 #define DECLARE_CASE(x) \ | 259 #define DECLARE_CASE(x) \ |
227 case IrOpcode::k##x: return TypeBinaryOp(node, x##Typer); | 260 case IrOpcode::k##x: return TypeBinaryOp(node, x##Typer); |
228 JS_SIMPLE_BINOP_LIST(DECLARE_CASE) | 261 JS_SIMPLE_BINOP_LIST(DECLARE_CASE) |
229 #undef DECLARE_CASE | 262 #undef DECLARE_CASE |
230 | 263 |
231 #define DECLARE_CASE(x) case IrOpcode::k##x: return Type##x(node); | 264 #define DECLARE_CASE(x) case IrOpcode::k##x: return Type##x(node); |
232 DECLARE_CASE(Start) | 265 DECLARE_CASE(Start) |
233 // VALUE_OP_LIST without JS_SIMPLE_BINOP_LIST: | 266 // VALUE_OP_LIST without JS_SIMPLE_BINOP_LIST: |
(...skipping 11 matching lines...) Expand all Loading... |
245 INNER_CONTROL_OP_LIST(DECLARE_CASE) | 278 INNER_CONTROL_OP_LIST(DECLARE_CASE) |
246 #undef DECLARE_CASE | 279 #undef DECLARE_CASE |
247 break; | 280 break; |
248 } | 281 } |
249 UNREACHABLE(); | 282 UNREACHABLE(); |
250 return Bounds(); | 283 return Bounds(); |
251 } | 284 } |
252 | 285 |
253 Type* TypeConstant(Handle<Object> value); | 286 Type* TypeConstant(Handle<Object> value); |
254 | 287 |
255 protected: | 288 private: |
| 289 Typer* typer_; |
| 290 MaybeHandle<Context> context_; |
| 291 |
256 #define DECLARE_METHOD(x) inline Bounds Type##x(Node* node); | 292 #define DECLARE_METHOD(x) inline Bounds Type##x(Node* node); |
257 DECLARE_METHOD(Start) | 293 DECLARE_METHOD(Start) |
258 VALUE_OP_LIST(DECLARE_METHOD) | 294 VALUE_OP_LIST(DECLARE_METHOD) |
259 #undef DECLARE_METHOD | 295 #undef DECLARE_METHOD |
260 | 296 |
261 Bounds BoundsOrNone(Node* node) { | 297 Bounds BoundsOrNone(Node* node) { |
262 return NodeProperties::IsTyped(node) ? NodeProperties::GetBounds(node) | 298 return NodeProperties::IsTyped(node) ? NodeProperties::GetBounds(node) |
263 : Bounds(Type::None()); | 299 : Bounds(Type::None()); |
264 } | 300 } |
265 | 301 |
(...skipping 10 matching lines...) Expand all Loading... |
276 return result; | 312 return result; |
277 } | 313 } |
278 | 314 |
279 Type* Weaken(Type* current_type, Type* previous_type); | 315 Type* Weaken(Type* current_type, Type* previous_type); |
280 | 316 |
281 Zone* zone() { return typer_->zone(); } | 317 Zone* zone() { return typer_->zone(); } |
282 Isolate* isolate() { return typer_->isolate(); } | 318 Isolate* isolate() { return typer_->isolate(); } |
283 Graph* graph() { return typer_->graph(); } | 319 Graph* graph() { return typer_->graph(); } |
284 MaybeHandle<Context> context() { return typer_->context(); } | 320 MaybeHandle<Context> context() { return typer_->context(); } |
285 | 321 |
286 private: | |
287 Typer* typer_; | |
288 MaybeHandle<Context> context_; | |
289 | |
290 typedef Type* (*UnaryTyperFun)(Type*, Typer* t); | 322 typedef Type* (*UnaryTyperFun)(Type*, Typer* t); |
291 typedef Type* (*BinaryTyperFun)(Type*, Type*, Typer* t); | 323 typedef Type* (*BinaryTyperFun)(Type*, Type*, Typer* t); |
292 | 324 |
293 Bounds TypeUnaryOp(Node* node, UnaryTyperFun); | 325 Bounds TypeUnaryOp(Node* node, UnaryTyperFun); |
294 Bounds TypeBinaryOp(Node* node, BinaryTyperFun); | 326 Bounds TypeBinaryOp(Node* node, BinaryTyperFun); |
295 | 327 |
296 static Type* Invert(Type*, Typer*); | 328 static Type* Invert(Type*, Typer*); |
297 static Type* FalsifyUndefined(Type*, Typer*); | 329 static Type* FalsifyUndefined(Type*, Typer*); |
298 static Type* Rangify(Type*, Typer*); | 330 static Type* Rangify(Type*, Typer*); |
299 | 331 |
(...skipping 12 matching lines...) Expand all Loading... |
312 | 344 |
313 static Type* JSCompareTyper(Type*, Type*, Typer*); | 345 static Type* JSCompareTyper(Type*, Type*, Typer*); |
314 | 346 |
315 #define DECLARE_METHOD(x) static Type* x##Typer(Type*, Type*, Typer*); | 347 #define DECLARE_METHOD(x) static Type* x##Typer(Type*, Type*, Typer*); |
316 JS_SIMPLE_BINOP_LIST(DECLARE_METHOD) | 348 JS_SIMPLE_BINOP_LIST(DECLARE_METHOD) |
317 #undef DECLARE_METHOD | 349 #undef DECLARE_METHOD |
318 | 350 |
319 static Type* JSUnaryNotTyper(Type*, Typer*); | 351 static Type* JSUnaryNotTyper(Type*, Typer*); |
320 static Type* JSLoadPropertyTyper(Type*, Type*, Typer*); | 352 static Type* JSLoadPropertyTyper(Type*, Type*, Typer*); |
321 static Type* JSCallFunctionTyper(Type*, Typer*); | 353 static Type* JSCallFunctionTyper(Type*, Typer*); |
322 }; | |
323 | 354 |
| 355 Reduction UpdateBounds(Node* node, Bounds current) { |
| 356 if (NodeProperties::IsTyped(node)) { |
| 357 // Widen the bounds of a previously typed node. |
| 358 Bounds previous = NodeProperties::GetBounds(node); |
| 359 // Speed up termination in the presence of range types: |
| 360 current.upper = Weaken(current.upper, previous.upper); |
| 361 current.lower = Weaken(current.lower, previous.lower); |
324 | 362 |
325 class Typer::RunVisitor : public Typer::Visitor { | 363 // Types should not get less precise. |
326 public: | 364 DCHECK(previous.lower->Is(current.lower)); |
327 explicit RunVisitor(Typer* typer) | 365 DCHECK(previous.upper->Is(current.upper)); |
328 : Visitor(typer), | |
329 redo(NodeSet::key_compare(), NodeSet::allocator_type(typer->zone())) {} | |
330 | 366 |
331 void Post(Node* node) { | 367 NodeProperties::SetBounds(node, current); |
332 if (node->op()->ValueOutputCount() > 0) { | 368 if (!(previous.Narrows(current) && current.Narrows(previous))) { |
333 Bounds bounds = TypeNode(node); | 369 // If something changed, revisit all uses. |
334 NodeProperties::SetBounds(node, bounds); | 370 return Changed(node); |
335 // Remember incompletely typed nodes for least fixpoint iteration. | 371 } |
336 if (!NodeProperties::AllValueInputsAreTyped(node)) redo.insert(node); | 372 return NoChange(); |
| 373 } else { |
| 374 // No previous type, simply update the bounds. |
| 375 NodeProperties::SetBounds(node, current); |
| 376 return Changed(node); |
337 } | 377 } |
338 } | 378 } |
339 | |
340 NodeSet redo; | |
341 }; | |
342 | |
343 | |
344 class Typer::WidenVisitor : public Typer::Visitor { | |
345 public: | |
346 explicit WidenVisitor(Typer* typer) | |
347 : Visitor(typer), | |
348 local_zone_(zone()->isolate()), | |
349 enabled_(graph()->NodeCount(), true, &local_zone_), | |
350 queue_(&local_zone_) {} | |
351 | |
352 void Run(NodeSet* nodes) { | |
353 // Queue all the roots. | |
354 for (Node* node : *nodes) { | |
355 Queue(node); | |
356 } | |
357 | |
358 while (!queue_.empty()) { | |
359 Node* node = queue_.front(); | |
360 queue_.pop(); | |
361 | |
362 if (node->op()->ValueOutputCount() > 0) { | |
363 // Enable future queuing (and thus re-typing) of this node. | |
364 enabled_[node->id()] = true; | |
365 | |
366 // Compute the new type. | |
367 Bounds previous = BoundsOrNone(node); | |
368 Bounds current = TypeNode(node); | |
369 | |
370 // Speed up termination in the presence of range types: | |
371 current.upper = Weaken(current.upper, previous.upper); | |
372 current.lower = Weaken(current.lower, previous.lower); | |
373 | |
374 // Types should not get less precise. | |
375 DCHECK(previous.lower->Is(current.lower)); | |
376 DCHECK(previous.upper->Is(current.upper)); | |
377 | |
378 NodeProperties::SetBounds(node, current); | |
379 // If something changed, push all uses into the queue. | |
380 if (!(previous.Narrows(current) && current.Narrows(previous))) { | |
381 for (Node* use : node->uses()) { | |
382 Queue(use); | |
383 } | |
384 } | |
385 } | |
386 // If there is no value output, we deliberately leave the node disabled | |
387 // for queuing - there is no need to type it. | |
388 } | |
389 } | |
390 | |
391 void Queue(Node* node) { | |
392 // If the node is enabled for queuing, push it to the queue and disable it | |
393 // (to avoid queuing it multiple times). | |
394 if (enabled_[node->id()]) { | |
395 queue_.push(node); | |
396 enabled_[node->id()] = false; | |
397 } | |
398 } | |
399 | |
400 private: | |
401 Zone local_zone_; | |
402 BoolVector enabled_; | |
403 ZoneQueue<Node*> queue_; | |
404 }; | 379 }; |
405 | 380 |
406 | 381 |
407 void Typer::Run() { | 382 void Typer::Run() { |
408 RunVisitor typing(this); | 383 { |
409 graph_->VisitNodeInputsFromEnd(&typing); | 384 // TODO(titzer): this is a hack. Reset types for interior nodes first. |
410 // Find least fixpoint. | 385 NodeDeque deque(zone()); |
411 WidenVisitor widen(this); | 386 NodeMarker<bool> marked(graph(), 2); |
412 widen.Run(&typing.redo); | 387 deque.push_front(graph()->end()); |
| 388 marked.Set(graph()->end(), true); |
| 389 while (!deque.empty()) { |
| 390 Node* node = deque.front(); |
| 391 deque.pop_front(); |
| 392 // TODO(titzer): there shouldn't be a need to retype constants. |
| 393 if (node->op()->ValueOutputCount() > 0) |
| 394 NodeProperties::RemoveBounds(node); |
| 395 for (Node* input : node->inputs()) { |
| 396 if (!marked.Get(input)) { |
| 397 marked.Set(input, true); |
| 398 deque.push_back(input); |
| 399 } |
| 400 } |
| 401 } |
| 402 } |
| 403 |
| 404 Visitor visitor(this); |
| 405 GraphReducer graph_reducer(graph(), zone()); |
| 406 graph_reducer.AddReducer(&visitor); |
| 407 graph_reducer.ReduceGraph(); |
413 } | 408 } |
414 | 409 |
415 | 410 |
416 void Typer::Decorator::Decorate(Node* node) { | 411 void Typer::Decorator::Decorate(Node* node) { |
417 if (node->op()->ValueOutputCount() > 0) { | 412 if (node->op()->ValueOutputCount() > 0) { |
418 // Only eagerly type-decorate nodes with known input types. | 413 // Only eagerly type-decorate nodes with known input types. |
419 // Other cases will generally require a proper fixpoint iteration with Run. | 414 // Other cases will generally require a proper fixpoint iteration with Run. |
420 bool is_typed = NodeProperties::IsTyped(node); | 415 bool is_typed = NodeProperties::IsTyped(node); |
421 if (is_typed || NodeProperties::AllValueInputsAreTyped(node)) { | 416 if (is_typed || NodeProperties::AllValueInputsAreTyped(node)) { |
422 Visitor typing(typer_); | 417 Visitor typing(typer_); |
(...skipping 872 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1295 Bounds Typer::Visitor::TypeJSInstanceOf(Node* node) { | 1290 Bounds Typer::Visitor::TypeJSInstanceOf(Node* node) { |
1296 return Bounds(Type::None(zone()), Type::Boolean(zone())); | 1291 return Bounds(Type::None(zone()), Type::Boolean(zone())); |
1297 } | 1292 } |
1298 | 1293 |
1299 | 1294 |
1300 // JS context operators. | 1295 // JS context operators. |
1301 | 1296 |
1302 | 1297 |
1303 Bounds Typer::Visitor::TypeJSLoadContext(Node* node) { | 1298 Bounds Typer::Visitor::TypeJSLoadContext(Node* node) { |
1304 Bounds outer = Operand(node, 0); | 1299 Bounds outer = Operand(node, 0); |
1305 DCHECK(outer.upper->Maybe(Type::Internal())); | 1300 Type* context_type = outer.upper; |
| 1301 if (context_type->Is(Type::None())) { |
| 1302 // Upper bound of context is not yet known. |
| 1303 return Bounds(Type::None(), Type::Any()); |
| 1304 } |
| 1305 |
| 1306 DCHECK(context_type->Maybe(Type::Internal())); |
1306 // TODO(rossberg): More precisely, instead of the above assertion, we should | 1307 // TODO(rossberg): More precisely, instead of the above assertion, we should |
1307 // back-propagate the constraint that it has to be a subtype of Internal. | 1308 // back-propagate the constraint that it has to be a subtype of Internal. |
1308 | 1309 |
1309 ContextAccess access = OpParameter<ContextAccess>(node); | 1310 ContextAccess access = OpParameter<ContextAccess>(node); |
1310 Type* context_type = outer.upper; | |
1311 MaybeHandle<Context> context; | 1311 MaybeHandle<Context> context; |
1312 if (context_type->IsConstant()) { | 1312 if (context_type->IsConstant()) { |
1313 context = Handle<Context>::cast(context_type->AsConstant()->Value()); | 1313 context = Handle<Context>::cast(context_type->AsConstant()->Value()); |
1314 } | 1314 } |
1315 // Walk context chain (as far as known), mirroring dynamic lookup. | 1315 // Walk context chain (as far as known), mirroring dynamic lookup. |
1316 // Since contexts are mutable, the information is only useful as a lower | 1316 // Since contexts are mutable, the information is only useful as a lower |
1317 // bound. | 1317 // bound. |
1318 // TODO(rossberg): Could use scope info to fix upper bounds for constant | 1318 // TODO(rossberg): Could use scope info to fix upper bounds for constant |
1319 // bindings if we know that this code is never shared. | 1319 // bindings if we know that this code is never shared. |
1320 for (size_t i = access.depth(); i > 0; --i) { | 1320 for (size_t i = access.depth(); i > 0; --i) { |
(...skipping 753 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2074 return typer_->cache_->Get(kFloat64ArrayFunc); | 2074 return typer_->cache_->Get(kFloat64ArrayFunc); |
2075 } | 2075 } |
2076 } | 2076 } |
2077 } | 2077 } |
2078 return Type::Constant(value, zone()); | 2078 return Type::Constant(value, zone()); |
2079 } | 2079 } |
2080 | 2080 |
2081 } // namespace compiler | 2081 } // namespace compiler |
2082 } // namespace internal | 2082 } // namespace internal |
2083 } // namespace v8 | 2083 } // namespace v8 |
OLD | NEW |