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

Side by Side Diff: sdk/lib/_internal/compiler/implementation/ssa/builder.dart

Issue 13723002: dart2js: Fix SSA corner case with always breaking loop and failing assert (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 7 years, 8 months 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 | Annotate | Revision Log
OLDNEW
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 /** 7 /**
8 * A special element for the extra parameter taken by intercepted 8 * A special element for the extra parameter taken by intercepted
9 * methods. We need to override [Element.computeType] because our 9 * methods. We need to override [Element.computeType] because our
10 * optimizers may look at its declared type. 10 * optimizers may look at its declared type.
(...skipping 478 matching lines...) Expand 10 before | Expand all | Expand 10 after
489 if (scopeData == null) return; 489 if (scopeData == null) return;
490 if (scopeData.hasBoxedLoopVariables()) { 490 if (scopeData.hasBoxedLoopVariables()) {
491 // If there are boxed loop variables then we set up the box and 491 // If there are boxed loop variables then we set up the box and
492 // redirections already now. This way the initializer can write its 492 // redirections already now. This way the initializer can write its
493 // values into the box. 493 // values into the box.
494 // For other loops the box will be created when entering the body. 494 // For other loops the box will be created when entering the body.
495 enterScope(node, null); 495 enterScope(node, null);
496 } 496 }
497 } 497 }
498 498
499 void beginLoopHeader(Node node, HBasicBlock loopEntry) { 499 /**
500 * Create phis at the loop entry for local variables (ready for the values
501 * from the back edge). Populate the phis with the current values.
502 */
503 void beginLoopHeader(HBasicBlock loopEntry) {
500 // Create a copy because we modify the map while iterating over it. 504 // Create a copy because we modify the map while iterating over it.
501 Map<Element, HInstruction> saved = 505 Map<Element, HInstruction> savedDirectLocals =
502 new LinkedHashMap<Element, HInstruction>.from(directLocals); 506 new LinkedHashMap<Element, HInstruction>.from(directLocals);
503 507
504 // Create phis for all elements in the definitions environment. 508 // Create phis for all elements in the definitions environment.
505 saved.forEach((Element element, HInstruction instruction) { 509 savedDirectLocals.forEach((Element element, HInstruction instruction) {
506 if (isAccessedDirectly(element)) { 510 if (isAccessedDirectly(element)) {
507 // We know 'this' cannot be modified. 511 // We know 'this' cannot be modified.
508 if (!identical(element, closureData.thisElement)) { 512 if (!identical(element, closureData.thisElement)) {
509 HPhi phi = new HPhi.singleInput(element, instruction); 513 HPhi phi = new HPhi.singleInput(element, instruction);
510 loopEntry.addPhi(phi); 514 loopEntry.addPhi(phi);
511 directLocals[element] = phi; 515 directLocals[element] = phi;
512 } else { 516 } else {
513 directLocals[element] = instruction; 517 directLocals[element] = instruction;
514 } 518 }
515 } 519 }
(...skipping 16 matching lines...) Expand all
532 // updates. 536 // updates.
533 // In all other cases a new box will be created when entering the body of 537 // In all other cases a new box will be created when entering the body of
534 // the next iteration. 538 // the next iteration.
535 ClosureScope scopeData = closureData.capturingScopes[node]; 539 ClosureScope scopeData = closureData.capturingScopes[node];
536 if (scopeData == null) return; 540 if (scopeData == null) return;
537 if (scopeData.hasBoxedLoopVariables()) { 541 if (scopeData.hasBoxedLoopVariables()) {
538 updateCaptureBox(scopeData.boxElement, scopeData.boxedLoopVariables); 542 updateCaptureBox(scopeData.boxElement, scopeData.boxedLoopVariables);
539 } 543 }
540 } 544 }
541 545
546 /**
547 * Goes through the phis created in beginLoopHeader entry and adds the
548 * input from the back edge (from the current value of directLocals) to them.
549 */
542 void endLoop(HBasicBlock loopEntry) { 550 void endLoop(HBasicBlock loopEntry) {
543 // If the loop has an aborting body, we don't update the loop 551 // If the loop has an aborting body, we don't update the loop
544 // phis. 552 // phis.
545 if (loopEntry.predecessors.length == 1) return; 553 if (loopEntry.predecessors.length == 1) return;
546 loopEntry.forEachPhi((HPhi phi) { 554 loopEntry.forEachPhi((HPhi phi) {
547 Element element = phi.sourceElement; 555 Element element = phi.sourceElement;
548 HInstruction postLoopDefinition = directLocals[element]; 556 HInstruction postLoopDefinition = directLocals[element];
549 phi.addInput(postLoopDefinition); 557 phi.addInput(postLoopDefinition);
550 }); 558 });
551 } 559 }
(...skipping 27 matching lines...) Expand all
579 new HPhi.manyInputs(element, <HInstruction>[mine, instruction]); 587 new HPhi.manyInputs(element, <HInstruction>[mine, instruction]);
580 joinBlock.addPhi(phi); 588 joinBlock.addPhi(phi);
581 joinedLocals[element] = phi; 589 joinedLocals[element] = phi;
582 } 590 }
583 } 591 }
584 }); 592 });
585 directLocals = joinedLocals; 593 directLocals = joinedLocals;
586 } 594 }
587 595
588 /** 596 /**
589 * The current localsHandler is not used for its values, only for its 597 * When control flow merges, this method can be used to merge several
590 * declared variables. This is a way to exclude local values from the 598 * localsHandlers into a new one using phis. The new localsHandler is
591 * result when they are no longer in scope. 599 * returned. Unless it is also in the list, the current localsHandler is not
592 * Returns the new LocalsHandler to use (may not be [this]). 600 * used for its values, only for its declared variables. This is a way to
601 * exclude local values from the result when they are no longer in scope.
593 */ 602 */
594 LocalsHandler mergeMultiple(List<LocalsHandler> locals, 603 LocalsHandler mergeMultiple(List<LocalsHandler> localsHandlers,
595 HBasicBlock joinBlock) { 604 HBasicBlock joinBlock) {
596 assert(locals.length > 0); 605 assert(localsHandlers.length > 0);
597 if (locals.length == 1) return locals[0]; 606 if (localsHandlers.length == 1) return localsHandlers[0];
598 Map<Element, HInstruction> joinedLocals = 607 Map<Element, HInstruction> joinedLocals =
599 new LinkedHashMap<Element,HInstruction>(); 608 new LinkedHashMap<Element,HInstruction>();
600 HInstruction thisValue = null; 609 HInstruction thisValue = null;
601 directLocals.forEach((Element element, HInstruction instruction) { 610 directLocals.forEach((Element element, HInstruction instruction) {
602 if (!identical(element, closureData.thisElement)) { 611 if (!identical(element, closureData.thisElement)) {
603 HPhi phi = new HPhi.noInputs(element); 612 HPhi phi = new HPhi.noInputs(element);
604 joinedLocals[element] = phi; 613 joinedLocals[element] = phi;
605 joinBlock.addPhi(phi); 614 joinBlock.addPhi(phi);
606 } else { 615 } else {
607 // We know that "this" never changes, if it's there. 616 // We know that "this" never changes, if it's there.
608 // Save it for later. While merging, there is no phi for "this", 617 // Save it for later. While merging, there is no phi for "this",
609 // so we don't have to special case it in the merge loop. 618 // so we don't have to special case it in the merge loop.
610 thisValue = instruction; 619 thisValue = instruction;
611 } 620 }
612 }); 621 });
613 for (LocalsHandler local in locals) { 622 for (LocalsHandler handler in localsHandlers) {
614 local.directLocals.forEach((Element element, HInstruction instruction) { 623 handler.directLocals.forEach((Element element, HInstruction instruction) {
615 HPhi phi = joinedLocals[element]; 624 HPhi phi = joinedLocals[element];
616 if (phi != null) { 625 if (phi != null) {
617 phi.addInput(instruction); 626 phi.addInput(instruction);
618 } 627 }
619 }); 628 });
620 } 629 }
621 if (thisValue != null) { 630 if (thisValue != null) {
622 // If there was a "this" for the scope, add it to the new locals. 631 // If there was a "this" for the scope, add it to the new locals.
623 joinedLocals[closureData.thisElement] = thisValue; 632 joinedLocals[closureData.thisElement] = thisValue;
624 } 633 }
(...skipping 1104 matching lines...) Expand 10 before | Expand all | Expand 10 after
1729 Script script = element.getCompilationUnit().script; 1738 Script script = element.getCompilationUnit().script;
1730 SourceFile sourceFile = script.file; 1739 SourceFile sourceFile = script.file;
1731 SourceFileLocation location = new SourceFileLocation(sourceFile, token); 1740 SourceFileLocation location = new SourceFileLocation(sourceFile, token);
1732 if (!location.isValid()) { 1741 if (!location.isValid()) {
1733 throw MessageKind.INVALID_SOURCE_FILE_LOCATION.message( 1742 throw MessageKind.INVALID_SOURCE_FILE_LOCATION.message(
1734 {'offset': token.charOffset, 1743 {'offset': token.charOffset,
1735 'fileName': sourceFile.filename, 1744 'fileName': sourceFile.filename,
1736 'length': sourceFile.text.length}); 1745 'length': sourceFile.text.length});
1737 } 1746 }
1738 return location; 1747 return location;
1739 } 1748 }
1740 1749
1741 void visit(Node node) { 1750 void visit(Node node) {
1742 if (node != null) node.accept(this); 1751 if (node != null) node.accept(this);
1743 } 1752 }
1744 1753
1745 visitBlock(Block node) { 1754 visitBlock(Block node) {
1746 for (Link<Node> link = node.statements.nodes; 1755 for (Link<Node> link = node.statements.nodes;
1747 !link.isEmpty; 1756 !link.isEmpty;
1748 link = link.tail) { 1757 link = link.tail) {
1749 visit(link.head); 1758 visit(link.head);
(...skipping 25 matching lines...) Expand all
1775 assert(!isAborted()); 1784 assert(!isAborted());
1776 HBasicBlock previousBlock = close(new HGoto()); 1785 HBasicBlock previousBlock = close(new HGoto());
1777 1786
1778 JumpHandler jumpHandler = createJumpHandler(node); 1787 JumpHandler jumpHandler = createJumpHandler(node);
1779 HBasicBlock loopEntry = graph.addNewLoopHeaderBlock( 1788 HBasicBlock loopEntry = graph.addNewLoopHeaderBlock(
1780 jumpHandler.target, 1789 jumpHandler.target,
1781 jumpHandler.labels()); 1790 jumpHandler.labels());
1782 previousBlock.addSuccessor(loopEntry); 1791 previousBlock.addSuccessor(loopEntry);
1783 open(loopEntry); 1792 open(loopEntry);
1784 1793
1785 localsHandler.beginLoopHeader(node, loopEntry); 1794 localsHandler.beginLoopHeader(loopEntry);
1786 return jumpHandler; 1795 return jumpHandler;
1787 } 1796 }
1788 1797
1789 /** 1798 /**
1790 * Ends the loop: 1799 * Ends the loop:
1791 * - creates a new block and adds it as successor to the [branchBlock]. 1800 * - creates a new block and adds it as successor to the [branchBlock] and
1801 * any blocks that end in break.
1792 * - opens the new block (setting as [current]). 1802 * - opens the new block (setting as [current]).
1793 * - notifies the locals handler that we're exiting a loop. 1803 * - notifies the locals handler that we're exiting a loop.
1804 * [savedLocals] are the locals from the end of the loop condition.
1805 * [branchBlock] is the exit (branching) block of the condition. For the
1806 * while and for loops this is at the top of the loop. For do-while it is
1807 * the end of the body. It is null for degenerate do-while loops that have
1808 * no back edge because they abort (throw/return/break in the body and have
1809 * no continues).
1794 */ 1810 */
1795 void endLoop(HBasicBlock loopEntry, 1811 void endLoop(HBasicBlock loopEntry,
1796 HBasicBlock branchBlock, 1812 HBasicBlock branchBlock,
1797 JumpHandler jumpHandler, 1813 JumpHandler jumpHandler,
1798 LocalsHandler savedLocals) { 1814 LocalsHandler savedLocals) {
1799 if (branchBlock == null && !jumpHandler.hasAnyBreak()) return;
1800
1801 HBasicBlock loopExitBlock = addNewBlock(); 1815 HBasicBlock loopExitBlock = addNewBlock();
1802 assert(branchBlock == null || branchBlock.successors.length == 1); 1816 List<LocalsHandler> breakHandlers = <LocalsHandler>[];
1803 List<LocalsHandler> breakLocals = <LocalsHandler>[]; 1817 // Collect data for the successors and the phis at each break.
1804 jumpHandler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) { 1818 jumpHandler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) {
1805 breakInstruction.block.addSuccessor(loopExitBlock); 1819 breakInstruction.block.addSuccessor(loopExitBlock);
1806 breakLocals.add(locals); 1820 breakHandlers.add(locals);
1807 }); 1821 });
1822 // The exit block is a successor of the loop condition if it is reached.
1823 // We don't add the successor in the case of a while/for loop that aborts
1824 // because the caller of endLoop will be wiring up a special empty else
1825 // block instead.
1808 if (branchBlock != null) { 1826 if (branchBlock != null) {
1809 branchBlock.addSuccessor(loopExitBlock); 1827 branchBlock.addSuccessor(loopExitBlock);
1810 } 1828 }
1829 // Update the phis at the loop entry with the current values of locals.
1830 localsHandler.endLoop(loopEntry);
1831
1832 // Start generating code for the exit block.
1811 open(loopExitBlock); 1833 open(loopExitBlock);
1812 localsHandler.endLoop(loopEntry); 1834
1813 if (!breakLocals.isEmpty) { 1835 // Create a new localsHandler for the loopExitBlock with the correct phis.
1814 breakLocals.add(savedLocals); 1836 if (!breakHandlers.isEmpty) {
1815 localsHandler = savedLocals.mergeMultiple(breakLocals, loopExitBlock); 1837 if (branchBlock != null) {
1838 // Add the values of the locals at the end of the condition block to
1839 // the phis. These are the values that flow to the exit if the
1840 // condition fails.
1841 breakHandlers.add(savedLocals);
1842 }
1843 localsHandler = savedLocals.mergeMultiple(breakHandlers, loopExitBlock);
1816 } else { 1844 } else {
1817 localsHandler = savedLocals; 1845 localsHandler = savedLocals;
1818 } 1846 }
1819 } 1847 }
1820 1848
1821 HSubGraphBlockInformation wrapStatementGraph(SubGraph statements) { 1849 HSubGraphBlockInformation wrapStatementGraph(SubGraph statements) {
1822 if (statements == null) return null; 1850 if (statements == null) return null;
1823 return new HSubGraphBlockInformation(statements); 1851 return new HSubGraphBlockInformation(statements);
1824 } 1852 }
1825 1853
(...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after
1863 HLoopInformation loopInfo = current.loopInformation; 1891 HLoopInformation loopInfo = current.loopInformation;
1864 HBasicBlock conditionBlock = current; 1892 HBasicBlock conditionBlock = current;
1865 if (startBlock == null) startBlock = conditionBlock; 1893 if (startBlock == null) startBlock = conditionBlock;
1866 1894
1867 HInstruction conditionInstruction = condition(); 1895 HInstruction conditionInstruction = condition();
1868 HBasicBlock conditionExitBlock = 1896 HBasicBlock conditionExitBlock =
1869 close(new HLoopBranch(conditionInstruction)); 1897 close(new HLoopBranch(conditionInstruction));
1870 SubExpression conditionExpression = 1898 SubExpression conditionExpression =
1871 new SubExpression(conditionBlock, conditionExitBlock); 1899 new SubExpression(conditionBlock, conditionExitBlock);
1872 1900
1901 // Save the values of the local variables at the end of the condition
1902 // block. These are the values that will flow to the loop exit if the
1903 // condition fails.
1873 LocalsHandler savedLocals = new LocalsHandler.from(localsHandler); 1904 LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
1874 1905
1875 // The body. 1906 // The body.
1876 HBasicBlock beginBodyBlock = addNewBlock(); 1907 HBasicBlock beginBodyBlock = addNewBlock();
1877 conditionExitBlock.addSuccessor(beginBodyBlock); 1908 conditionExitBlock.addSuccessor(beginBodyBlock);
1878 open(beginBodyBlock); 1909 open(beginBodyBlock);
1879 1910
1880 localsHandler.enterLoopBody(loop); 1911 localsHandler.enterLoopBody(loop);
1881 body(); 1912 body();
1882 1913
1883 SubGraph bodyGraph = new SubGraph(beginBodyBlock, lastOpenedBlock); 1914 SubGraph bodyGraph = new SubGraph(beginBodyBlock, lastOpenedBlock);
1884 HBasicBlock bodyBlock = current; 1915 HBasicBlock bodyBlock = current;
1885 if (current != null) close(new HGoto()); 1916 if (current != null) close(new HGoto());
1886 1917
1887 SubExpression updateGraph; 1918 SubExpression updateGraph;
1888 1919
1889 // Check that the loop has at least one back-edge. 1920 bool loopIsDegenerate = !jumpHandler.hasAnyContinue() && bodyBlock == null;
1890 if (jumpHandler.hasAnyContinue() || bodyBlock != null) { 1921 if (!loopIsDegenerate) {
1891 // Update. 1922 // Update.
1892 // We create an update block, even when we are in a while loop. There the 1923 // We create an update block, even when we are in a while loop. There the
1893 // update block is the jump-target for continue statements. We could avoid 1924 // update block is the jump-target for continue statements. We could avoid
1894 // the creation if there is no continue, but for now we always create it. 1925 // the creation if there is no continue, but for now we always create it.
1895 HBasicBlock updateBlock = addNewBlock(); 1926 HBasicBlock updateBlock = addNewBlock();
1896 1927
1897 List<LocalsHandler> continueLocals = <LocalsHandler>[]; 1928 List<LocalsHandler> continueHandlers = <LocalsHandler>[];
1898 jumpHandler.forEachContinue((HContinue instruction, 1929 jumpHandler.forEachContinue((HContinue instruction,
1899 LocalsHandler locals) { 1930 LocalsHandler locals) {
1900 instruction.block.addSuccessor(updateBlock); 1931 instruction.block.addSuccessor(updateBlock);
1901 continueLocals.add(locals); 1932 continueHandlers.add(locals);
1902 }); 1933 });
1903 1934
1904 1935
1905 if (bodyBlock != null) { 1936 if (bodyBlock != null) {
1906 continueLocals.add(localsHandler); 1937 continueHandlers.add(localsHandler);
1907 bodyBlock.addSuccessor(updateBlock); 1938 bodyBlock.addSuccessor(updateBlock);
1908 } 1939 }
1909 1940
1910 open(updateBlock); 1941 open(updateBlock);
1911 localsHandler = 1942 localsHandler =
1912 continueLocals[0].mergeMultiple(continueLocals, updateBlock); 1943 continueHandlers[0].mergeMultiple(continueHandlers, updateBlock);
1913 1944
1914 HLabeledBlockInformation labelInfo; 1945 HLabeledBlockInformation labelInfo;
1915 List<LabelElement> labels = jumpHandler.labels(); 1946 List<LabelElement> labels = jumpHandler.labels();
1916 TargetElement target = elements[loop]; 1947 TargetElement target = elements[loop];
1917 if (!labels.isEmpty) { 1948 if (!labels.isEmpty) {
1918 beginBodyBlock.setBlockFlow( 1949 beginBodyBlock.setBlockFlow(
1919 new HLabeledBlockInformation( 1950 new HLabeledBlockInformation(
1920 new HSubGraphBlockInformation(bodyGraph), 1951 new HSubGraphBlockInformation(bodyGraph),
1921 jumpHandler.labels(), 1952 jumpHandler.labels(),
1922 isContinue: true), 1953 isContinue: true),
1923 updateBlock); 1954 updateBlock);
1924 } else if (target != null && target.isContinueTarget) { 1955 } else if (target != null && target.isContinueTarget) {
1925 beginBodyBlock.setBlockFlow( 1956 beginBodyBlock.setBlockFlow(
1926 new HLabeledBlockInformation.implicit( 1957 new HLabeledBlockInformation.implicit(
1927 new HSubGraphBlockInformation(bodyGraph), 1958 new HSubGraphBlockInformation(bodyGraph),
1928 target, 1959 target,
1929 isContinue: true), 1960 isContinue: true),
1930 updateBlock); 1961 updateBlock);
1931 } 1962 }
1932 1963
1933 localsHandler.enterLoopUpdates(loop); 1964 localsHandler.enterLoopUpdates(loop);
1934 1965
1935 update(); 1966 update();
1936 1967
1937 HBasicBlock updateEndBlock = close(new HGoto()); 1968 HBasicBlock updateEndBlock = close(new HGoto());
1938 // The back-edge completing the cycle. 1969 // The back-edge completing the cycle.
1939 updateEndBlock.addSuccessor(conditionBlock); 1970 updateEndBlock.addSuccessor(conditionBlock);
1940 updateGraph = new SubExpression(updateBlock, updateEndBlock); 1971 updateGraph = new SubExpression(updateBlock, updateEndBlock);
1941 }
1942 1972
1943 if (jumpHandler.hasAnyContinue() || bodyBlock != null) {
1944 endLoop(conditionBlock, conditionExitBlock, jumpHandler, savedLocals); 1973 endLoop(conditionBlock, conditionExitBlock, jumpHandler, savedLocals);
1974
1945 conditionBlock.postProcessLoopHeader(); 1975 conditionBlock.postProcessLoopHeader();
1946 HLoopBlockInformation info = 1976 HLoopBlockInformation info =
1947 new HLoopBlockInformation( 1977 new HLoopBlockInformation(
1948 HLoopBlockInformation.loopType(loop), 1978 HLoopBlockInformation.loopType(loop),
1949 wrapExpressionGraph(initializerGraph), 1979 wrapExpressionGraph(initializerGraph),
1950 wrapExpressionGraph(conditionExpression), 1980 wrapExpressionGraph(conditionExpression),
1951 wrapStatementGraph(bodyGraph), 1981 wrapStatementGraph(bodyGraph),
1952 wrapExpressionGraph(updateGraph), 1982 wrapExpressionGraph(updateGraph),
1953 conditionBlock.loopInformation.target, 1983 conditionBlock.loopInformation.target,
1954 conditionBlock.loopInformation.labels, 1984 conditionBlock.loopInformation.labels,
1955 sourceFileLocationForBeginToken(loop), 1985 sourceFileLocationForBeginToken(loop),
1956 sourceFileLocationForEndToken(loop)); 1986 sourceFileLocationForEndToken(loop));
1957 1987
1958 startBlock.setBlockFlow(info, current); 1988 startBlock.setBlockFlow(info, current);
1959 loopInfo.loopBlockInformation = info; 1989 loopInfo.loopBlockInformation = info;
1960 } else { 1990 } else {
1961 // There is no back edge for the loop, so we turn the code into: 1991 // The body of the for/while loop always aborts, so there is no back edge.
1992 // We turn the code into:
1962 // if (condition) { 1993 // if (condition) {
1963 // body; 1994 // body;
1964 // } else { 1995 // } else {
1965 // // We always create an empty else block to avoid critical edges. 1996 // // We always create an empty else block to avoid critical edges.
1966 // } 1997 // }
1967 // 1998 //
1968 // If there is any break in the body, we attach a synthetic 1999 // If there is any break in the body, we attach a synthetic
1969 // label to the if. 2000 // label to the if.
1970 HBasicBlock elseBlock = addNewBlock(); 2001 HBasicBlock elseBlock = addNewBlock();
1971 open(elseBlock); 2002 open(elseBlock);
1972 close(new HGoto()); 2003 close(new HGoto());
1973 endLoop(conditionBlock, null, jumpHandler, savedLocals); 2004 // Pass the elseBlock as the branchBlock, because that's the block we go
2005 // to just before leaving the 'loop'.
2006 endLoop(conditionBlock, elseBlock, jumpHandler, savedLocals);
1974 2007
1975 // [endLoop] will not create an exit block if there are no
1976 // breaks.
1977 if (current == null) open(addNewBlock());
1978 elseBlock.addSuccessor(current);
1979 SubGraph elseGraph = new SubGraph(elseBlock, elseBlock); 2008 SubGraph elseGraph = new SubGraph(elseBlock, elseBlock);
1980 // Remove the loop information attached to the header. 2009 // Remove the loop information attached to the header.
1981 conditionBlock.loopInformation = null; 2010 conditionBlock.loopInformation = null;
1982 2011
1983 // Remove the [HLoopBranch] instruction and replace it with 2012 // Remove the [HLoopBranch] instruction and replace it with
1984 // [HIf]. 2013 // [HIf].
1985 HInstruction condition = conditionExitBlock.last.inputs[0]; 2014 HInstruction condition = conditionExitBlock.last.inputs[0];
1986 conditionExitBlock.addAtExit(new HIf(condition)); 2015 conditionExitBlock.addAtExit(new HIf(condition));
1987 conditionExitBlock.addSuccessor(elseBlock); 2016 conditionExitBlock.addSuccessor(elseBlock);
1988 conditionExitBlock.remove(conditionExitBlock.last); 2017 conditionExitBlock.remove(conditionExitBlock.last);
(...skipping 103 matching lines...) Expand 10 before | Expand all | Expand 10 after
2092 HBasicBlock bodyExitBlock; 2121 HBasicBlock bodyExitBlock;
2093 bool isAbortingBody = false; 2122 bool isAbortingBody = false;
2094 if (current != null) { 2123 if (current != null) {
2095 bodyExitBlock = close(new HGoto()); 2124 bodyExitBlock = close(new HGoto());
2096 } else { 2125 } else {
2097 isAbortingBody = true; 2126 isAbortingBody = true;
2098 bodyExitBlock = lastOpenedBlock; 2127 bodyExitBlock = lastOpenedBlock;
2099 } 2128 }
2100 2129
2101 SubExpression conditionExpression; 2130 SubExpression conditionExpression;
2102 HBasicBlock conditionEndBlock; 2131 bool loopIsDegenerate = isAbortingBody && !hasContinues;
2103 if (!isAbortingBody || hasContinues) { 2132 if (!loopIsDegenerate) {
2104 HBasicBlock conditionBlock = addNewBlock(); 2133 HBasicBlock conditionBlock = addNewBlock();
2105 2134
2106 List<LocalsHandler> continueLocals = <LocalsHandler>[]; 2135 List<LocalsHandler> continueHandlers = <LocalsHandler>[];
2107 jumpHandler.forEachContinue((HContinue instruction, 2136 jumpHandler.forEachContinue((HContinue instruction,
2108 LocalsHandler locals) { 2137 LocalsHandler locals) {
2109 instruction.block.addSuccessor(conditionBlock); 2138 instruction.block.addSuccessor(conditionBlock);
2110 continueLocals.add(locals); 2139 continueHandlers.add(locals);
2111 }); 2140 });
2112 2141
2113 if (!isAbortingBody) { 2142 if (!isAbortingBody) {
2114 bodyExitBlock.addSuccessor(conditionBlock); 2143 bodyExitBlock.addSuccessor(conditionBlock);
2115 } 2144 }
2116 2145
2117 if (!continueLocals.isEmpty) { 2146 if (!continueHandlers.isEmpty) {
2118 if (!isAbortingBody) continueLocals.add(localsHandler); 2147 if (!isAbortingBody) continueHandlers.add(localsHandler);
2119 localsHandler = 2148 localsHandler =
2120 savedLocals.mergeMultiple(continueLocals, conditionBlock); 2149 savedLocals.mergeMultiple(continueHandlers, conditionBlock);
2121 SubGraph bodyGraph = new SubGraph(bodyEntryBlock, bodyExitBlock); 2150 SubGraph bodyGraph = new SubGraph(bodyEntryBlock, bodyExitBlock);
2122 List<LabelElement> labels = jumpHandler.labels(); 2151 List<LabelElement> labels = jumpHandler.labels();
2123 HSubGraphBlockInformation bodyInfo = 2152 HSubGraphBlockInformation bodyInfo =
2124 new HSubGraphBlockInformation(bodyGraph); 2153 new HSubGraphBlockInformation(bodyGraph);
2125 HLabeledBlockInformation info; 2154 HLabeledBlockInformation info;
2126 if (!labels.isEmpty) { 2155 if (!labels.isEmpty) {
2127 info = new HLabeledBlockInformation(bodyInfo, labels, 2156 info = new HLabeledBlockInformation(bodyInfo, labels,
2128 isContinue: true); 2157 isContinue: true);
2129 } else { 2158 } else {
2130 info = new HLabeledBlockInformation.implicit(bodyInfo, target, 2159 info = new HLabeledBlockInformation.implicit(bodyInfo, target,
2131 isContinue: true); 2160 isContinue: true);
2132 } 2161 }
2133 bodyEntryBlock.setBlockFlow(info, conditionBlock); 2162 bodyEntryBlock.setBlockFlow(info, conditionBlock);
2134 } 2163 }
2135 open(conditionBlock); 2164 open(conditionBlock);
2136 2165
2137 visit(node.condition); 2166 visit(node.condition);
2138 assert(!isAborted()); 2167 assert(!isAborted());
2139 HInstruction conditionInstruction = popBoolified(); 2168 HInstruction conditionInstruction = popBoolified();
2140 conditionEndBlock = close( 2169 HBasicBlock conditionEndBlock = close(
2141 new HLoopBranch(conditionInstruction, HLoopBranch.DO_WHILE_LOOP)); 2170 new HLoopBranch(conditionInstruction, HLoopBranch.DO_WHILE_LOOP));
2142 2171
2143 HBasicBlock avoidCriticalEdge = addNewBlock(); 2172 HBasicBlock avoidCriticalEdge = addNewBlock();
2144 conditionEndBlock.addSuccessor(avoidCriticalEdge); 2173 conditionEndBlock.addSuccessor(avoidCriticalEdge);
2145 open(avoidCriticalEdge); 2174 open(avoidCriticalEdge);
2146 close(new HGoto()); 2175 close(new HGoto());
2147 avoidCriticalEdge.addSuccessor(loopEntryBlock); // The back-edge. 2176 avoidCriticalEdge.addSuccessor(loopEntryBlock); // The back-edge.
2148 2177
2149 conditionExpression = 2178 conditionExpression =
2150 new SubExpression(conditionBlock, conditionEndBlock); 2179 new SubExpression(conditionBlock, conditionEndBlock);
2151 }
2152 2180
2153 endLoop(loopEntryBlock, conditionEndBlock, jumpHandler, localsHandler); 2181 endLoop(loopEntryBlock, conditionEndBlock, jumpHandler, localsHandler);
2154 if (!isAbortingBody || hasContinues) { 2182
2155 loopEntryBlock.postProcessLoopHeader(); 2183 loopEntryBlock.postProcessLoopHeader();
2156 SubGraph bodyGraph = new SubGraph(loopEntryBlock, bodyExitBlock); 2184 SubGraph bodyGraph = new SubGraph(loopEntryBlock, bodyExitBlock);
2157 HLoopBlockInformation loopBlockInfo = 2185 HLoopBlockInformation loopBlockInfo =
2158 new HLoopBlockInformation( 2186 new HLoopBlockInformation(
2159 HLoopBlockInformation.DO_WHILE_LOOP, 2187 HLoopBlockInformation.DO_WHILE_LOOP,
2160 null, 2188 null,
2161 wrapExpressionGraph(conditionExpression), 2189 wrapExpressionGraph(conditionExpression),
2162 wrapStatementGraph(bodyGraph), 2190 wrapStatementGraph(bodyGraph),
2163 null, 2191 null,
2164 loopEntryBlock.loopInformation.target, 2192 loopEntryBlock.loopInformation.target,
2165 loopEntryBlock.loopInformation.labels, 2193 loopEntryBlock.loopInformation.labels,
2166 sourceFileLocationForBeginToken(node), 2194 sourceFileLocationForBeginToken(node),
2167 sourceFileLocationForEndToken(node)); 2195 sourceFileLocationForEndToken(node));
2168 loopEntryBlock.setBlockFlow(loopBlockInfo, current); 2196 loopEntryBlock.setBlockFlow(loopBlockInfo, current);
2169 loopInfo.loopBlockInformation = loopBlockInfo; 2197 loopInfo.loopBlockInformation = loopBlockInfo;
2170 } else { 2198 } else {
2171 // If the loop has no back edge, we remove the loop information 2199 // Since the loop has no back edge, we remove the loop information on the
2172 // on the header. 2200 // header.
2173 loopEntryBlock.loopInformation = null; 2201 loopEntryBlock.loopInformation = null;
2174 2202
2175 // If the body of the loop has any break, we attach a
2176 // synthesized label to the body.
2177 if (jumpHandler.hasAnyBreak()) { 2203 if (jumpHandler.hasAnyBreak()) {
2204 // Null branchBlock because the body of the do-while loop always aborts,
2205 // so we never get to the condition.
2206 endLoop(loopEntryBlock, null, jumpHandler, localsHandler);
2207
2208 // Since the body of the loop has a break, we attach a synthesized label
2209 // to the body.
2178 SubGraph bodyGraph = new SubGraph(bodyEntryBlock, bodyExitBlock); 2210 SubGraph bodyGraph = new SubGraph(bodyEntryBlock, bodyExitBlock);
2179 TargetElement target = elements[node]; 2211 TargetElement target = elements[node];
2180 LabelElement label = target.addLabel(null, 'loop'); 2212 LabelElement label = target.addLabel(null, 'loop');
2181 label.setBreakTarget(); 2213 label.setBreakTarget();
2182 HLabeledBlockInformation info = new HLabeledBlockInformation( 2214 HLabeledBlockInformation info = new HLabeledBlockInformation(
2183 new HSubGraphBlockInformation(bodyGraph), <LabelElement>[label]); 2215 new HSubGraphBlockInformation(bodyGraph), <LabelElement>[label]);
2184 loopEntryBlock.setBlockFlow(info, current); 2216 loopEntryBlock.setBlockFlow(info, current);
2185 jumpHandler.forEachBreak((HBreak breakInstruction, _) { 2217 jumpHandler.forEachBreak((HBreak breakInstruction, _) {
2186 HBasicBlock block = breakInstruction.block; 2218 HBasicBlock block = breakInstruction.block;
2187 block.addAtExit(new HBreak.toLabel(label)); 2219 block.addAtExit(new HBreak.toLabel(label));
(...skipping 1882 matching lines...) Expand 10 before | Expand all | Expand 10 after
4070 } 4102 }
4071 LocalsHandler beforeLocals = new LocalsHandler.from(localsHandler); 4103 LocalsHandler beforeLocals = new LocalsHandler.from(localsHandler);
4072 assert(targetElement.isBreakTarget); 4104 assert(targetElement.isBreakTarget);
4073 JumpHandler handler = new JumpHandler(this, targetElement); 4105 JumpHandler handler = new JumpHandler(this, targetElement);
4074 // Introduce a new basic block. 4106 // Introduce a new basic block.
4075 HBasicBlock entryBlock = openNewBlock(); 4107 HBasicBlock entryBlock = openNewBlock();
4076 visit(body); 4108 visit(body);
4077 SubGraph bodyGraph = new SubGraph(entryBlock, lastOpenedBlock); 4109 SubGraph bodyGraph = new SubGraph(entryBlock, lastOpenedBlock);
4078 4110
4079 HBasicBlock joinBlock = graph.addNewBlock(); 4111 HBasicBlock joinBlock = graph.addNewBlock();
4080 List<LocalsHandler> breakLocals = <LocalsHandler>[]; 4112 List<LocalsHandler> breakHandlers = <LocalsHandler>[];
4081 handler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) { 4113 handler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) {
4082 breakInstruction.block.addSuccessor(joinBlock); 4114 breakInstruction.block.addSuccessor(joinBlock);
4083 breakLocals.add(locals); 4115 breakHandlers.add(locals);
4084 }); 4116 });
4085 bool hasBreak = breakLocals.length > 0; 4117 bool hasBreak = breakHandlers.length > 0;
4086 if (!isAborted()) { 4118 if (!isAborted()) {
4087 goto(current, joinBlock); 4119 goto(current, joinBlock);
4088 breakLocals.add(localsHandler); 4120 breakHandlers.add(localsHandler);
4089 } 4121 }
4090 open(joinBlock); 4122 open(joinBlock);
4091 localsHandler = beforeLocals.mergeMultiple(breakLocals, joinBlock); 4123 localsHandler = beforeLocals.mergeMultiple(breakHandlers, joinBlock);
4092 4124
4093 if (hasBreak) { 4125 if (hasBreak) {
4094 // There was at least one reachable break, so the label is needed. 4126 // There was at least one reachable break, so the label is needed.
4095 entryBlock.setBlockFlow( 4127 entryBlock.setBlockFlow(
4096 new HLabeledBlockInformation(new HSubGraphBlockInformation(bodyGraph), 4128 new HLabeledBlockInformation(new HSubGraphBlockInformation(bodyGraph),
4097 handler.labels()), 4129 handler.labels()),
4098 joinBlock); 4130 joinBlock);
4099 } 4131 }
4100 handler.close(); 4132 handler.close();
4101 } 4133 }
(...skipping 42 matching lines...) Expand 10 before | Expand all | Expand 10 after
4144 4176
4145 Link<Node> cases = node.cases.nodes; 4177 Link<Node> cases = node.cases.nodes;
4146 JumpHandler jumpHandler = createJumpHandler(node); 4178 JumpHandler jumpHandler = createJumpHandler(node);
4147 4179
4148 buildSwitchCases(cases, expression); 4180 buildSwitchCases(cases, expression);
4149 4181
4150 HBasicBlock lastBlock = lastOpenedBlock; 4182 HBasicBlock lastBlock = lastOpenedBlock;
4151 4183
4152 // Create merge block for break targets. 4184 // Create merge block for break targets.
4153 HBasicBlock joinBlock = new HBasicBlock(); 4185 HBasicBlock joinBlock = new HBasicBlock();
4154 List<LocalsHandler> caseLocals = <LocalsHandler>[]; 4186 List<LocalsHandler> caseHandlers = <LocalsHandler>[];
4155 jumpHandler.forEachBreak((HBreak instruction, LocalsHandler locals) { 4187 jumpHandler.forEachBreak((HBreak instruction, LocalsHandler locals) {
4156 instruction.block.addSuccessor(joinBlock); 4188 instruction.block.addSuccessor(joinBlock);
4157 caseLocals.add(locals); 4189 caseHandlers.add(locals);
4158 }); 4190 });
4159 if (!isAborted()) { 4191 if (!isAborted()) {
4160 // The current flow is only aborted if the switch has a default that 4192 // The current flow is only aborted if the switch has a default that
4161 // aborts (all previous cases must abort, and if there is no default, 4193 // aborts (all previous cases must abort, and if there is no default,
4162 // it's possible to miss all the cases). 4194 // it's possible to miss all the cases).
4163 caseLocals.add(localsHandler); 4195 caseHandlers.add(localsHandler);
4164 goto(current, joinBlock); 4196 goto(current, joinBlock);
4165 } 4197 }
4166 if (caseLocals.length != 0) { 4198 if (caseHandlers.length != 0) {
4167 graph.addBlock(joinBlock); 4199 graph.addBlock(joinBlock);
4168 open(joinBlock); 4200 open(joinBlock);
4169 if (caseLocals.length == 1) { 4201 if (caseHandlers.length == 1) {
4170 localsHandler = caseLocals[0]; 4202 localsHandler = caseHandlers[0];
4171 } else { 4203 } else {
4172 localsHandler = savedLocals.mergeMultiple(caseLocals, joinBlock); 4204 localsHandler = savedLocals.mergeMultiple(caseHandlers, joinBlock);
4173 } 4205 }
4174 } else { 4206 } else {
4175 // The joinblock is not used. 4207 // The joinblock is not used.
4176 joinBlock = null; 4208 joinBlock = null;
4177 } 4209 }
4178 startBlock.setBlockFlow( 4210 startBlock.setBlockFlow(
4179 new HLabeledBlockInformation.implicit( 4211 new HLabeledBlockInformation.implicit(
4180 new HSubGraphBlockInformation(new SubGraph(startBlock, lastBlock)), 4212 new HSubGraphBlockInformation(new SubGraph(startBlock, lastBlock)),
4181 elements[node]), 4213 elements[node]),
4182 joinBlock); 4214 joinBlock);
(...skipping 100 matching lines...) Expand 10 before | Expand all | Expand 10 after
4283 HInstruction error = pop(); 4315 HInstruction error = pop();
4284 close(new HThrow(error)); 4316 close(new HThrow(error));
4285 } 4317 }
4286 statements.add( 4318 statements.add(
4287 new HSubGraphBlockInformation(new SubGraph(block, lastOpenedBlock))); 4319 new HSubGraphBlockInformation(new SubGraph(block, lastOpenedBlock)));
4288 } 4320 }
4289 4321
4290 // Add a join-block if necessary. 4322 // Add a join-block if necessary.
4291 // We create [joinBlock] early, and then go through the cases that might 4323 // We create [joinBlock] early, and then go through the cases that might
4292 // want to jump to it. In each case, if we add [joinBlock] as a successor 4324 // want to jump to it. In each case, if we add [joinBlock] as a successor
4293 // of another block, we also add an element to [caseLocals] that is used 4325 // of another block, we also add an element to [caseHandlers] that is used
4294 // to create the phis in [joinBlock]. 4326 // to create the phis in [joinBlock].
4295 // If we never jump to the join block, [caseLocals] will stay empty, and 4327 // If we never jump to the join block, [caseHandlers] will stay empty, and
4296 // the join block is never added to the graph. 4328 // the join block is never added to the graph.
4297 HBasicBlock joinBlock = new HBasicBlock(); 4329 HBasicBlock joinBlock = new HBasicBlock();
4298 List<LocalsHandler> caseLocals = <LocalsHandler>[]; 4330 List<LocalsHandler> caseHandlers = <LocalsHandler>[];
4299 jumpHandler.forEachBreak((HBreak instruction, LocalsHandler locals) { 4331 jumpHandler.forEachBreak((HBreak instruction, LocalsHandler locals) {
4300 instruction.block.addSuccessor(joinBlock); 4332 instruction.block.addSuccessor(joinBlock);
4301 caseLocals.add(locals); 4333 caseHandlers.add(locals);
4302 }); 4334 });
4303 if (!isAborted()) { 4335 if (!isAborted()) {
4304 current.close(new HGoto()); 4336 current.close(new HGoto());
4305 lastOpenedBlock.addSuccessor(joinBlock); 4337 lastOpenedBlock.addSuccessor(joinBlock);
4306 caseLocals.add(localsHandler); 4338 caseHandlers.add(localsHandler);
4307 } 4339 }
4308 if (!hasDefault) { 4340 if (!hasDefault) {
4309 // The current flow is only aborted if the switch has a default that 4341 // The current flow is only aborted if the switch has a default that
4310 // aborts (all previous cases must abort, and if there is no default, 4342 // aborts (all previous cases must abort, and if there is no default,
4311 // it's possible to miss all the cases). 4343 // it's possible to miss all the cases).
4312 expressionEnd.addSuccessor(joinBlock); 4344 expressionEnd.addSuccessor(joinBlock);
4313 caseLocals.add(savedLocals); 4345 caseHandlers.add(savedLocals);
4314 } 4346 }
4315 assert(caseLocals.length == joinBlock.predecessors.length); 4347 assert(caseHandlers.length == joinBlock.predecessors.length);
4316 if (caseLocals.length != 0) { 4348 if (caseHandlers.length != 0) {
4317 graph.addBlock(joinBlock); 4349 graph.addBlock(joinBlock);
4318 open(joinBlock); 4350 open(joinBlock);
4319 if (caseLocals.length == 1) { 4351 if (caseHandlers.length == 1) {
4320 localsHandler = caseLocals[0]; 4352 localsHandler = caseHandlers[0];
4321 } else { 4353 } else {
4322 localsHandler = savedLocals.mergeMultiple(caseLocals, joinBlock); 4354 localsHandler = savedLocals.mergeMultiple(caseHandlers, joinBlock);
4323 } 4355 }
4324 } else { 4356 } else {
4325 // The joinblock is not used. 4357 // The joinblock is not used.
4326 joinBlock = null; 4358 joinBlock = null;
4327 } 4359 }
4328 4360
4329 HSubExpressionBlockInformation expressionInfo = 4361 HSubExpressionBlockInformation expressionInfo =
4330 new HSubExpressionBlockInformation(new SubExpression(expressionStart, 4362 new HSubExpressionBlockInformation(new SubExpression(expressionStart,
4331 expressionEnd)); 4363 expressionEnd));
4332 expressionStart.setBlockFlow( 4364 expressionStart.setBlockFlow(
(...skipping 532 matching lines...) Expand 10 before | Expand all | Expand 10 after
4865 } 4897 }
4866 node.visitChildren(this); 4898 node.visitChildren(this);
4867 seenReturn = true; 4899 seenReturn = true;
4868 } 4900 }
4869 4901
4870 void visitTryStatement(Node node) { 4902 void visitTryStatement(Node node) {
4871 if (!registerNode()) return; 4903 if (!registerNode()) return;
4872 tooDifficult = true; 4904 tooDifficult = true;
4873 } 4905 }
4874 4906
4875 void visitThrow(Node node) { 4907 void visitThrow(Node node) {
ngeoffray 2013/04/07 09:48:50 Why is that restriction not removed? Is that not w
4876 if (!registerNode()) return; 4908 if (!registerNode()) return;
4877 tooDifficult = true; 4909 tooDifficult = true;
4878 } 4910 }
4879 } 4911 }
4880 4912
4881 class InliningState { 4913 class InliningState {
4882 /** 4914 /**
4883 * Documentation wanted -- johnniwinther 4915 * Documentation wanted -- johnniwinther
4884 * 4916 *
4885 * Invariant: [function] must be an implementation element. 4917 * Invariant: [function] must be an implementation element.
(...skipping 243 matching lines...) Expand 10 before | Expand all | Expand 10 after
5129 new HSubGraphBlockInformation(elseBranch.graph)); 5161 new HSubGraphBlockInformation(elseBranch.graph));
5130 5162
5131 HBasicBlock conditionStartBlock = conditionBranch.block; 5163 HBasicBlock conditionStartBlock = conditionBranch.block;
5132 conditionStartBlock.setBlockFlow(info, joinBlock); 5164 conditionStartBlock.setBlockFlow(info, joinBlock);
5133 SubGraph conditionGraph = conditionBranch.graph; 5165 SubGraph conditionGraph = conditionBranch.graph;
5134 HIf branch = conditionGraph.end.last; 5166 HIf branch = conditionGraph.end.last;
5135 assert(branch is HIf); 5167 assert(branch is HIf);
5136 branch.blockInformation = conditionStartBlock.blockFlow; 5168 branch.blockInformation = conditionStartBlock.blockFlow;
5137 } 5169 }
5138 } 5170 }
OLDNEW
« no previous file with comments | « no previous file | sdk/lib/_internal/compiler/implementation/ssa/nodes.dart » ('j') | tests/language/inlined_throw_test.dart » ('J')

Powered by Google App Engine
This is Rietveld 408576698