Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(161)

Side by Side Diff: src/compiler/typer.cc

Issue 780623002: Reland "[turbofan] Reuse forward fixpoint algorithm in Typer by making it a Reducer." (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 6 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/compiler/typer.h ('k') | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
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
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
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
OLDNEW
« no previous file with comments | « src/compiler/typer.h ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698