Chromium Code Reviews Chromium Code Reviews
Issue 1087973002:
Rewrite for-in loop as indexing loop for JavaScript indexable arrays (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart| OLD | NEW |
|---|---|
| 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 part of ssa; | 5 part of ssa; |
| 6 | 6 |
| 7 class SsaFunctionCompiler implements FunctionCompiler { | 7 class SsaFunctionCompiler implements FunctionCompiler { |
| 8 SsaCodeGeneratorTask generator; | 8 SsaCodeGeneratorTask generator; |
| 9 SsaBuilderTask builder; | 9 SsaBuilderTask builder; |
| 10 SsaOptimizerTask optimizer; | 10 SsaOptimizerTask optimizer; |
| (...skipping 5507 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 5518 }, () { | 5518 }, () { |
| 5519 pushInvokeDynamic(node, new Selector.call("cancel", null, 0), | 5519 pushInvokeDynamic(node, new Selector.call("cancel", null, 0), |
| 5520 [streamIterator]); | 5520 [streamIterator]); |
| 5521 push(new HAwait(pop(), new TypeMask.subclass(compiler.objectClass, | 5521 push(new HAwait(pop(), new TypeMask.subclass(compiler.objectClass, |
| 5522 compiler.world))); | 5522 compiler.world))); |
| 5523 pop(); | 5523 pop(); |
| 5524 }); | 5524 }); |
| 5525 } | 5525 } |
| 5526 | 5526 |
| 5527 visitSyncForIn(ast.SyncForIn node) { | 5527 visitSyncForIn(ast.SyncForIn node) { |
| 5528 // The 'get iterator' selector for this node has the inferred receiver type. | |
| 5529 // If the receiver supports JavaScript indexing we should generate an | |
|
floitsch
2015/04/17 12:40:33
-should-
sra1
2015/04/17 18:16:56
Done.
| |
| 5530 // indexing loop instead of allocating an iterator object. | |
| 5531 | |
| 5532 // This scheme recognizes for-in on direct lists. It does not recognize all | |
| 5533 // uses of ArrayIterator. They still occur when the receiver is an Iterable | |
| 5534 // with a `get iterator` method that delegate to another Iterable and the | |
| 5535 // method is inlined. We would require full scalar replacement in that | |
| 5536 // case. | |
| 5537 | |
| 5538 Selector selector = elements.getIteratorSelector(node); | |
| 5539 TypeMask mask = selector.mask; | |
| 5540 | |
| 5541 ClassWorld classWorld = compiler.world; | |
| 5542 if (mask != null && mask.satisfies(backend.jsIndexableClass, classWorld)) { | |
| 5543 return buildSyncForInIndexable(node, mask); | |
| 5544 } | |
| 5545 buildSyncForInIterator(node); | |
| 5546 } | |
| 5547 | |
| 5548 buildSyncForInIterator(ast.SyncForIn node) { | |
| 5528 // Generate a structure equivalent to: | 5549 // Generate a structure equivalent to: |
| 5529 // Iterator<E> $iter = <iterable>.iterator; | 5550 // Iterator<E> $iter = <iterable>.iterator; |
| 5530 // while ($iter.moveNext()) { | 5551 // while ($iter.moveNext()) { |
| 5531 // E <declaredIdentifier> = $iter.current; | 5552 // E <declaredIdentifier> = $iter.current; |
| 5532 // <body> | 5553 // <body> |
| 5533 // } | 5554 // } |
| 5534 | 5555 |
| 5535 // The iterator is shared between initializer, condition and body. | 5556 // The iterator is shared between initializer, condition and body. |
| 5536 HInstruction iterator; | 5557 HInstruction iterator; |
| 5558 | |
| 5537 void buildInitializer() { | 5559 void buildInitializer() { |
| 5538 Selector selector = elements.getIteratorSelector(node); | 5560 Selector selector = elements.getIteratorSelector(node); |
| 5539 visit(node.expression); | 5561 visit(node.expression); |
| 5540 HInstruction receiver = pop(); | 5562 HInstruction receiver = pop(); |
| 5541 pushInvokeDynamic(node, selector, [receiver]); | 5563 pushInvokeDynamic(node, selector, [receiver]); |
| 5542 iterator = pop(); | 5564 iterator = pop(); |
| 5543 } | 5565 } |
| 5566 | |
| 5544 HInstruction buildCondition() { | 5567 HInstruction buildCondition() { |
| 5545 Selector selector = elements.getMoveNextSelector(node); | 5568 Selector selector = elements.getMoveNextSelector(node); |
| 5546 pushInvokeDynamic(node, selector, [iterator]); | 5569 pushInvokeDynamic(node, selector, [iterator]); |
| 5547 return popBoolified(); | 5570 return popBoolified(); |
| 5548 } | 5571 } |
| 5572 | |
| 5549 void buildBody() { | 5573 void buildBody() { |
| 5550 Selector call = elements.getCurrentSelector(node); | 5574 Selector call = elements.getCurrentSelector(node); |
| 5551 pushInvokeDynamic(node, call, [iterator]); | 5575 pushInvokeDynamic(node, call, [iterator]); |
| 5552 | 5576 |
| 5553 ast.Node identifier = node.declaredIdentifier; | 5577 ast.Node identifier = node.declaredIdentifier; |
| 5554 Element variable = elements.getForInVariable(node); | 5578 Element variable = elements.getForInVariable(node); |
| 5555 Selector selector = elements.getSelector(identifier); | 5579 Selector selector = elements.getSelector(identifier); |
| 5556 | 5580 |
| 5557 HInstruction value = pop(); | 5581 HInstruction value = pop(); |
| 5558 if (identifier.asSend() != null | 5582 if (identifier.asSend() != null |
| 5559 && Elements.isInstanceSend(identifier, elements)) { | 5583 && Elements.isInstanceSend(identifier, elements)) { |
| 5560 HInstruction receiver = generateInstanceSendReceiver(identifier); | 5584 HInstruction receiver = generateInstanceSendReceiver(identifier); |
| 5561 assert(receiver != null); | 5585 assert(receiver != null); |
| 5562 generateInstanceSetterWithCompiledReceiver( | 5586 generateInstanceSetterWithCompiledReceiver( |
| 5563 null, | 5587 null, |
| 5564 receiver, | 5588 receiver, |
| 5565 value, | 5589 value, |
| 5566 selector: selector, | 5590 selector: selector, |
| 5567 location: identifier); | 5591 location: identifier); |
| 5568 } else { | 5592 } else { |
| 5569 generateNonInstanceSetter(null, variable, value, location: identifier); | 5593 generateNonInstanceSetter(null, variable, value, location: identifier); |
| 5570 } | 5594 } |
| 5571 pop(); // Pop the value pushed by the setter call. | 5595 pop(); // Pop the value pushed by the setter call. |
| 5572 | 5596 |
| 5573 visit(node.body); | 5597 visit(node.body); |
| 5574 } | 5598 } |
| 5599 | |
| 5575 handleLoop(node, buildInitializer, buildCondition, () {}, buildBody); | 5600 handleLoop(node, buildInitializer, buildCondition, () {}, buildBody); |
| 5576 } | 5601 } |
| 5577 | 5602 |
| 5603 buildSyncForInIndexable(ast.ForIn node, TypeMask arrayType) { | |
| 5604 // Generate a structure equivalent to: | |
| 5605 // | |
| 5606 // int end = a.length; | |
| 5607 // for (int i = 0; | |
| 5608 // i < a.length; | |
| 5609 // checkConcurrentModificationError(a.length == end, a), ++i) { | |
| 5610 // E <declaredIdentifier> = array[i]; | |
| 5611 // <body> | |
| 5612 // } | |
| 5613 Element loopVariable = elements.getForInVariable(node); | |
| 5614 SyntheticLocal indexVariable = new SyntheticLocal('_i', loopVariable); | |
| 5615 TypeMask boolType = backend.boolType; | |
| 5616 | |
| 5617 // These variables are shared by initializer, condition, body and update. | |
| 5618 HInstruction array; // Set in buildInitializer. | |
| 5619 bool isFixed; // Set in buildInitializer. | |
| 5620 HInstruction originalLength = null; // Set for growable lists. | |
| 5621 | |
| 5622 HInstruction buildGetLength() { | |
| 5623 Element lengthElement = backend.jsIndexableLength; | |
| 5624 HFieldGet result = new HFieldGet( | |
| 5625 lengthElement, array, backend.positiveIntType, | |
| 5626 isAssignable: !isFixed); | |
| 5627 add(result); | |
| 5628 return result; | |
| 5629 } | |
| 5630 | |
| 5631 void buildConcurrentModificationErrorCheck() { | |
| 5632 if (originalLength == null) return; | |
| 5633 // The static call checkConcurrentModificationError() is expanded in | |
| 5634 // codegen to: | |
| 5635 // | |
| 5636 // array.length == _end || throwConcurrentModificationError(array) | |
| 5637 // | |
| 5638 HInstruction length = buildGetLength(); | |
| 5639 push(new HIdentity(length, originalLength, null, boolType)); | |
| 5640 pushInvokeStatic(node, | |
| 5641 backend.getCheckConcurrentModificationError(), | |
| 5642 [pop(), array]); | |
| 5643 pop(); | |
| 5644 } | |
| 5645 | |
| 5646 void buildInitializer() { | |
| 5647 visit(node.expression); | |
| 5648 array = pop(); | |
| 5649 isFixed = isFixedLength(array.instructionType, compiler); | |
| 5650 localsHandler.updateLocal(indexVariable, | |
| 5651 graph.addConstantInt(0, compiler)); | |
| 5652 originalLength = buildGetLength(); | |
| 5653 } | |
| 5654 | |
| 5655 HInstruction buildCondition() { | |
| 5656 HInstruction index = localsHandler.readLocal(indexVariable); | |
| 5657 HInstruction length = buildGetLength(); | |
| 5658 HInstruction compare = new HLess(index, length, null, boolType); | |
| 5659 add(compare); | |
| 5660 return compare; | |
| 5661 } | |
| 5662 | |
| 5663 void buildBody() { | |
| 5664 // If we had mechanically inlined ArrayIterator.moveNext(), it would have | |
| 5665 // inserted the ConcurrentModificationError check as part of the | |
| 5666 // condition. It is not necessary on the first iteration since there is | |
| 5667 // no code between calls to `get iterator` and `moveNext`, so the test is | |
| 5668 // moved to the loop update. | |
| 5669 | |
| 5670 // Find a type for the element. Use the element type of the indexer of the | |
| 5671 // array, as this is stronger than the iterator's `get current` type, for | |
| 5672 // example, `get current` includes null. | |
| 5673 // TODO(sra): The element type of a container type mask might be better. | |
| 5674 Selector selector = new Selector.index(); | |
| 5675 Selector refined = new TypedSelector(arrayType, selector, compiler.world); | |
| 5676 TypeMask type = | |
| 5677 TypeMaskFactory.inferredTypeForSelector(refined, compiler); | |
| 5678 | |
| 5679 HInstruction index = localsHandler.readLocal(indexVariable); | |
| 5680 HInstruction value = new HIndex(array, index, null, type); | |
| 5681 add(value); | |
| 5682 | |
| 5683 // Assign value to the loop variable. | |
| 5684 ast.Node identifier = node.declaredIdentifier; | |
| 5685 if (identifier.asSend() != null | |
| 5686 && Elements.isInstanceSend(identifier, elements)) { | |
| 5687 HInstruction receiver = generateInstanceSendReceiver(identifier); | |
| 5688 assert(receiver != null); | |
| 5689 generateInstanceSetterWithCompiledReceiver( | |
| 5690 null, | |
| 5691 receiver, | |
| 5692 value, | |
| 5693 selector: selector, | |
| 5694 location: identifier); | |
| 5695 } else { | |
| 5696 generateNonInstanceSetter( | |
| 5697 null, loopVariable, value, location: identifier); | |
| 5698 } | |
| 5699 pop(); // Pop the value pushed by the setter call. | |
| 5700 | |
| 5701 visit(node.body); | |
| 5702 } | |
| 5703 | |
| 5704 void buildUpdate() { | |
| 5705 // See buildBody as to why we check here. | |
| 5706 buildConcurrentModificationErrorCheck(); | |
| 5707 | |
| 5708 // TODO(sra): It would be slightly shorter to generate `a[i++]` in the | |
| 5709 // body (and that more closely follows what an inlined iterator would do) | |
| 5710 // but the code is horrible as `i+1` is carried around the loop in an | |
| 5711 // additional variable. | |
| 5712 HInstruction index = localsHandler.readLocal(indexVariable); | |
| 5713 HInstruction one = graph.addConstantInt(1, compiler); | |
| 5714 HInstruction addInstruction = | |
| 5715 new HAdd(index, one, null, backend.positiveIntType); | |
| 5716 add(addInstruction); | |
| 5717 localsHandler.updateLocal(indexVariable, addInstruction); | |
| 5718 } | |
| 5719 | |
| 5720 handleLoop(node, buildInitializer, buildCondition, buildUpdate, buildBody); | |
| 5721 } | |
| 5722 | |
| 5578 visitLabel(ast.Label node) { | 5723 visitLabel(ast.Label node) { |
| 5579 compiler.internalError(node, 'SsaFromAstMixin.visitLabel.'); | 5724 compiler.internalError(node, 'SsaFromAstMixin.visitLabel.'); |
| 5580 } | 5725 } |
| 5581 | 5726 |
| 5582 visitLabeledStatement(ast.LabeledStatement node) { | 5727 visitLabeledStatement(ast.LabeledStatement node) { |
| 5583 ast.Statement body = node.statement; | 5728 ast.Statement body = node.statement; |
| 5584 if (body is ast.Loop | 5729 if (body is ast.Loop |
| 5585 || body is ast.SwitchStatement | 5730 || body is ast.SwitchStatement |
| 5586 || Elements.isUnusedLabel(node, elements)) { | 5731 || Elements.isUnusedLabel(node, elements)) { |
| 5587 // Loops and switches handle their own labels. | 5732 // Loops and switches handle their own labels. |
| (...skipping 1415 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 7003 if (unaliased is TypedefType) throw 'unable to unalias $type'; | 7148 if (unaliased is TypedefType) throw 'unable to unalias $type'; |
| 7004 unaliased.accept(this, builder); | 7149 unaliased.accept(this, builder); |
| 7005 } | 7150 } |
| 7006 | 7151 |
| 7007 void visitDynamicType(DynamicType type, SsaBuilder builder) { | 7152 void visitDynamicType(DynamicType type, SsaBuilder builder) { |
| 7008 JavaScriptBackend backend = builder.compiler.backend; | 7153 JavaScriptBackend backend = builder.compiler.backend; |
| 7009 ClassElement cls = backend.findHelper('DynamicRuntimeType'); | 7154 ClassElement cls = backend.findHelper('DynamicRuntimeType'); |
| 7010 builder.push(new HDynamicType(type, new TypeMask.exact(cls, classWorld))); | 7155 builder.push(new HDynamicType(type, new TypeMask.exact(cls, classWorld))); |
| 7011 } | 7156 } |
| 7012 } | 7157 } |
| OLD | NEW |
