OLD | NEW |
1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2011, 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 interface HVisitor<R> { | 5 interface HVisitor<R> { |
6 R visitAdd(HAdd node); | 6 R visitAdd(HAdd node); |
7 R visitBitAnd(HBitAnd node); | 7 R visitBitAnd(HBitAnd node); |
8 R visitBitNot(HBitNot node); | 8 R visitBitNot(HBitNot node); |
9 R visitBitOr(HBitOr node); | 9 R visitBitOr(HBitOr node); |
10 R visitBitXor(HBitXor node); | 10 R visitBitXor(HBitXor node); |
(...skipping 120 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
131 blocks.add(block); | 131 blocks.add(block); |
132 assert(blocks[id] === block); | 132 assert(blocks[id] === block); |
133 } | 133 } |
134 | 134 |
135 HBasicBlock addNewBlock() { | 135 HBasicBlock addNewBlock() { |
136 HBasicBlock result = new HBasicBlock(); | 136 HBasicBlock result = new HBasicBlock(); |
137 addBlock(result); | 137 addBlock(result); |
138 return result; | 138 return result; |
139 } | 139 } |
140 | 140 |
141 HBasicBlock addNewLoopHeaderBlock(int type, | 141 HBasicBlock addNewLoopHeaderBlock(int kind, |
142 TargetElement target, | 142 TargetElement target, |
143 List<LabelElement> labels) { | 143 List<LabelElement> labels) { |
144 HBasicBlock result = addNewBlock(); | 144 HBasicBlock result = addNewBlock(); |
145 result.loopInformation = new HLoopInformation(type, result, target, labels); | 145 result.blockInformation = |
| 146 new HLoopInformation(kind, result, target, labels); |
146 return result; | 147 return result; |
147 } | 148 } |
148 | 149 |
149 static HType mapConstantTypeToSsaType(Constant constant) { | 150 static HType mapConstantTypeToSsaType(Constant constant) { |
150 if (constant.isNull()) return HType.UNKNOWN; | 151 if (constant.isNull()) return HType.UNKNOWN; |
151 if (constant.isBool()) return HType.BOOLEAN; | 152 if (constant.isBool()) return HType.BOOLEAN; |
152 if (constant.isInt()) return HType.INTEGER; | 153 if (constant.isInt()) return HType.INTEGER; |
153 if (constant.isDouble()) return HType.DOUBLE; | 154 if (constant.isDouble()) return HType.DOUBLE; |
154 if (constant.isString()) return HType.STRING; | 155 if (constant.isString()) return HType.STRING; |
155 if (constant.isList()) return HType.READABLE_ARRAY; | 156 if (constant.isList()) return HType.READABLE_ARRAY; |
(...skipping 250 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
406 // this [id]. The exception are back-edges. | 407 // this [id]. The exception are back-edges. |
407 int id; | 408 int id; |
408 | 409 |
409 static final int STATUS_NEW = 0; | 410 static final int STATUS_NEW = 0; |
410 static final int STATUS_OPEN = 1; | 411 static final int STATUS_OPEN = 1; |
411 static final int STATUS_CLOSED = 2; | 412 static final int STATUS_CLOSED = 2; |
412 int status = STATUS_NEW; | 413 int status = STATUS_NEW; |
413 | 414 |
414 HInstructionList phis; | 415 HInstructionList phis; |
415 | 416 |
416 HLoopInformation loopInformation = null; | 417 HBlockInformation blockInformation = null; |
417 HLabeledBlockInformation labeledBlockInformation = null; | |
418 HBasicBlock parentLoopHeader = null; | 418 HBasicBlock parentLoopHeader = null; |
419 List<HTypeGuard> guards; | 419 List<HTypeGuard> guards; |
420 | 420 |
421 final List<HBasicBlock> predecessors; | 421 final List<HBasicBlock> predecessors; |
422 List<HBasicBlock> successors; | 422 List<HBasicBlock> successors; |
423 | 423 |
424 HBasicBlock dominator = null; | 424 HBasicBlock dominator = null; |
425 final List<HBasicBlock> dominatedBlocks; | 425 final List<HBasicBlock> dominatedBlocks; |
426 | 426 |
427 HBasicBlock() : this.withId(null); | 427 HBasicBlock() : this.withId(null); |
428 HBasicBlock.withId(this.id) | 428 HBasicBlock.withId(this.id) |
429 : phis = new HInstructionList(), | 429 : phis = new HInstructionList(), |
430 predecessors = <HBasicBlock>[], | 430 predecessors = <HBasicBlock>[], |
431 successors = const <HBasicBlock>[], | 431 successors = const <HBasicBlock>[], |
432 dominatedBlocks = <HBasicBlock>[], | 432 dominatedBlocks = <HBasicBlock>[], |
433 guards = <HTypeGuard>[]; | 433 guards = <HTypeGuard>[]; |
434 | 434 |
435 int hashCode() => id; | 435 int hashCode() => id; |
436 | 436 |
437 bool isNew() => status == STATUS_NEW; | 437 bool isNew() => status == STATUS_NEW; |
438 bool isOpen() => status == STATUS_OPEN; | 438 bool isOpen() => status == STATUS_OPEN; |
439 bool isClosed() => status == STATUS_CLOSED; | 439 bool isClosed() => status == STATUS_CLOSED; |
440 | 440 |
441 bool isLoopHeader() => loopInformation !== null; | 441 bool isLoopHeader() => blockInformation is HLoopInformation; |
442 bool hasLabeledBlockInformation() => labeledBlockInformation !== null; | 442 bool isLabeledBlock() => blockInformation is HLabeledBlockInformation; |
443 | 443 |
444 bool hasGuards() => !guards.isEmpty(); | 444 bool hasGuards() => !guards.isEmpty(); |
445 | 445 |
446 void open() { | 446 void open() { |
447 assert(isNew()); | 447 assert(isNew()); |
448 status = STATUS_OPEN; | 448 status = STATUS_OPEN; |
449 } | 449 } |
450 | 450 |
451 void close(HControlFlow end) { | 451 void close(HControlFlow end) { |
452 assert(isOpen()); | 452 assert(isOpen()); |
(...skipping 88 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
541 } else { | 541 } else { |
542 successors.add(block); | 542 successors.add(block); |
543 } | 543 } |
544 block.predecessors.add(this); | 544 block.predecessors.add(this); |
545 } | 545 } |
546 | 546 |
547 void postProcessLoopHeader() { | 547 void postProcessLoopHeader() { |
548 assert(isLoopHeader()); | 548 assert(isLoopHeader()); |
549 // Only the first entry into the loop is from outside the | 549 // Only the first entry into the loop is from outside the |
550 // loop. All other entries must be back edges. | 550 // loop. All other entries must be back edges. |
| 551 HLoopInformation loopInformation = this.blockInformation; |
551 for (int i = 1, length = predecessors.length; i < length; i++) { | 552 for (int i = 1, length = predecessors.length; i < length; i++) { |
552 loopInformation.addBackEdge(predecessors[i]); | 553 loopInformation.addBackEdge(predecessors[i]); |
553 } | 554 } |
554 } | 555 } |
555 | 556 |
556 /** | 557 /** |
557 * Rewrites all uses of the [from] instruction to using the [to] | 558 * Rewrites all uses of the [from] instruction to using the [to] |
558 * instruction instead. | 559 * instruction instead. |
559 */ | 560 */ |
560 void rewrite(HInstruction from, HInstruction to) { | 561 void rewrite(HInstruction from, HInstruction to) { |
(...skipping 87 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
648 } | 649 } |
649 | 650 |
650 bool isValid() { | 651 bool isValid() { |
651 assert(isClosed()); | 652 assert(isClosed()); |
652 HValidator validator = new HValidator(); | 653 HValidator validator = new HValidator(); |
653 validator.visitBasicBlock(this); | 654 validator.visitBasicBlock(this); |
654 return validator.isValid; | 655 return validator.isValid; |
655 } | 656 } |
656 } | 657 } |
657 | 658 |
658 interface HBlockInformation {} | |
659 | |
660 class HLabeledBlockInformation implements HBlockInformation { | |
661 final SubGraph body; | |
662 final HBasicBlock joinBlock; | |
663 final List<LabelElement> labels; | |
664 final TargetElement target; | |
665 final bool isContinue; | |
666 | |
667 HLabeledBlockInformation(this.body, this.joinBlock, | |
668 List<LabelElement> labels, | |
669 [this.isContinue = false]) : | |
670 this.labels = labels, this.target = labels[0].target; | |
671 | |
672 HLabeledBlockInformation.implicit(this.body, | |
673 this.joinBlock, | |
674 this.target, | |
675 [this.isContinue = false]) | |
676 : this.labels = const<LabelElement>[]; | |
677 } | |
678 | |
679 class LoopTypeVisitor extends AbstractVisitor { | |
680 const LoopTypeVisitor(); | |
681 int visitNode(Node node) { | |
682 unreachable(); | |
683 } | |
684 int visitWhile(While node) => HLoopInformation.WHILE_LOOP; | |
685 int visitFor(For node) => HLoopInformation.FOR_LOOP; | |
686 int visitDoWhile(DoWhile node) => HLoopInformation.DO_WHILE_LOOP; | |
687 int visitForIn(ForIn node) => HLoopInformation.FOR_IN_LOOP; | |
688 } | |
689 | |
690 class HLoopInformation implements HBlockInformation { | |
691 static final int WHILE_LOOP = 0; | |
692 static final int FOR_LOOP = 1; | |
693 static final int DO_WHILE_LOOP = 2; | |
694 static final int FOR_IN_LOOP = 3; | |
695 | |
696 final int type; | |
697 final HBasicBlock header; | |
698 final List<HBasicBlock> blocks; | |
699 final List<HBasicBlock> backEdges; | |
700 final List<LabelElement> labels; | |
701 final TargetElement target; | |
702 SubGraph initializer = null; | |
703 SubExpression condition = null; | |
704 SubGraph body = null; | |
705 SubGraph updates = null; | |
706 HBasicBlock joinBlock; | |
707 | |
708 HLoopInformation(this.type, this.header, this.target, this.labels) | |
709 : blocks = new List<HBasicBlock>(), | |
710 backEdges = new List<HBasicBlock>(); | |
711 | |
712 static int loopType(Node node) { | |
713 return node.accept(const LoopTypeVisitor()); | |
714 } | |
715 | |
716 void addBackEdge(HBasicBlock predecessor) { | |
717 backEdges.add(predecessor); | |
718 addBlock(predecessor); | |
719 } | |
720 | |
721 // Adds a block and transitively all its predecessors in the loop as | |
722 // loop blocks. | |
723 void addBlock(HBasicBlock block) { | |
724 if (block === header) return; | |
725 HBasicBlock parentHeader = block.parentLoopHeader; | |
726 if (parentHeader === header) { | |
727 // Nothing to do in this case. | |
728 } else if (parentHeader !== null) { | |
729 addBlock(parentHeader); | |
730 } else { | |
731 block.parentLoopHeader = header; | |
732 blocks.add(block); | |
733 for (int i = 0, length = block.predecessors.length; i < length; i++) { | |
734 addBlock(block.predecessors[i]); | |
735 } | |
736 } | |
737 } | |
738 | |
739 HBasicBlock getLastBackEdge() { | |
740 int maxId = -1; | |
741 HBasicBlock result = null; | |
742 for (int i = 0, length = backEdges.length; i < length; i++) { | |
743 HBasicBlock current = backEdges[i]; | |
744 if (current.id > maxId) { | |
745 maxId = current.id; | |
746 result = current; | |
747 } | |
748 } | |
749 return result; | |
750 } | |
751 } | |
752 | 659 |
753 class HType { | 660 class HType { |
754 final int flag; | 661 final int flag; |
755 const HType(int this.flag); | 662 const HType(int this.flag); |
756 | 663 |
757 static final int FLAG_CONFLICTING = 0; | 664 static final int FLAG_CONFLICTING = 0; |
758 static final int FLAG_UNKNOWN = 1; | 665 static final int FLAG_UNKNOWN = 1; |
759 static final int FLAG_BOOLEAN = FLAG_UNKNOWN << 1; | 666 static final int FLAG_BOOLEAN = FLAG_UNKNOWN << 1; |
760 static final int FLAG_INTEGER = FLAG_BOOLEAN << 1; | 667 static final int FLAG_INTEGER = FLAG_BOOLEAN << 1; |
761 static final int FLAG_STRING = FLAG_INTEGER << 1; | 668 static final int FLAG_STRING = FLAG_INTEGER << 1; |
(...skipping 140 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
902 * | 809 * |
903 * Note that the [propagatedType] may only be set to [HType.CONFLICTING] with | 810 * Note that the [propagatedType] may only be set to [HType.CONFLICTING] with |
904 * speculative types (as otherwise the instruction either sets the output | 811 * speculative types (as otherwise the instruction either sets the output |
905 * type to [HType.UNKNOWN] or a specific type. | 812 * type to [HType.UNKNOWN] or a specific type. |
906 */ | 813 */ |
907 HType propagatedType = HType.UNKNOWN; | 814 HType propagatedType = HType.UNKNOWN; |
908 | 815 |
909 /** | 816 /** |
910 * Some instructions have a good idea of their return type, but cannot | 817 * Some instructions have a good idea of their return type, but cannot |
911 * guarantee the type. The [likelyType] does not need to be more specialized | 818 * guarantee the type. The [likelyType] does not need to be more specialized |
912 * than the [propagatedType]. | 819 * than the [propagatedType]. |
913 * | 820 * |
914 * Examples: the [likelyType] of [:x == y:] is a boolean. In most cases this | 821 * Examples: the [likelyType] of [:x == y:] is a boolean. In most cases this |
915 * cannot be guaranteed, but when merging types we still want to use this | 822 * cannot be guaranteed, but when merging types we still want to use this |
916 * information. | 823 * information. |
917 * | 824 * |
918 * Similarily the [HAdd] instruction is likely a number. Note that, even if | 825 * Similarily the [HAdd] instruction is likely a number. Note that, even if |
919 * the [propagatedType] is already set to integer, the [likelyType] still | 826 * the [propagatedType] is already set to integer, the [likelyType] still |
920 * might just return the number type. | 827 * might just return the number type. |
921 */ | 828 */ |
922 HType get likelyType() => propagatedType; | 829 HType get likelyType() => propagatedType; |
923 | 830 |
924 /** | 831 /** |
925 * Compute the type of the instruction by propagating the input types through | 832 * Compute the type of the instruction by propagating the input types through |
926 * the instruction. | 833 * the instruction. |
927 * | 834 * |
928 * By default just copy the guaranteed type. | 835 * By default just copy the guaranteed type. |
929 */ | 836 */ |
930 HType computeTypeFromInputTypes() => guaranteedType; | 837 HType computeTypeFromInputTypes() => guaranteedType; |
931 | 838 |
(...skipping 1068 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2000 | 1907 |
2001 HType computeDesiredTypeForNonTargetInput(HInstruction input) { | 1908 HType computeDesiredTypeForNonTargetInput(HInstruction input) { |
2002 if (input == left && right.propagatedType.isUseful()) { | 1909 if (input == left && right.propagatedType.isUseful()) { |
2003 // All our useful types have === semantics. But we don't want to | 1910 // All our useful types have === semantics. But we don't want to |
2004 // speculatively test for all possible types. Therefore we try to match | 1911 // speculatively test for all possible types. Therefore we try to match |
2005 // the two types. That is, if we see x == 3, then we speculatively test | 1912 // the two types. That is, if we see x == 3, then we speculatively test |
2006 // if x is a number and bailout if it isn't. | 1913 // if x is a number and bailout if it isn't. |
2007 if (right.isNumber()) return HType.NUMBER; // No need to be more precise. | 1914 if (right.isNumber()) return HType.NUMBER; // No need to be more precise. |
2008 // String equality testing is much more common than array equality | 1915 // String equality testing is much more common than array equality |
2009 // testing. | 1916 // testing. |
2010 if (right.isStringOrArray()) return HType.STRING; | 1917 if (right.isStringOrArray()) return HType.STRING; |
2011 return right.propagatedType; | 1918 return right.propagatedType; |
2012 } | 1919 } |
2013 // String equality testing is much more common than array equality testing. | 1920 // String equality testing is much more common than array equality testing. |
2014 if (input == left && left.isStringOrArray()) { | 1921 if (input == left && left.isStringOrArray()) { |
2015 return HType.READABLE_ARRAY; | 1922 return HType.READABLE_ARRAY; |
2016 } | 1923 } |
2017 // String equality testing is much more common than array equality testing. | 1924 // String equality testing is much more common than array equality testing. |
2018 if (input == right && right.isStringOrArray()) { | 1925 if (input == right && right.isStringOrArray()) { |
2019 return HType.STRING; | 1926 return HType.STRING; |
2020 } | 1927 } |
(...skipping 195 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2216 | 2123 |
2217 HInstruction get expression() => inputs[0]; | 2124 HInstruction get expression() => inputs[0]; |
2218 | 2125 |
2219 HType get guaranteedType() => HType.BOOLEAN; | 2126 HType get guaranteedType() => HType.BOOLEAN; |
2220 | 2127 |
2221 accept(HVisitor visitor) => visitor.visitIs(this); | 2128 accept(HVisitor visitor) => visitor.visitIs(this); |
2222 | 2129 |
2223 toString() => "$expression is $typeName"; | 2130 toString() => "$expression is $typeName"; |
2224 } | 2131 } |
2225 | 2132 |
2226 class HIfBlockInformation { | 2133 |
2227 final HIf branch; | 2134 interface HBlockInformation { |
| 2135 bool accept(HBlockInformationVisitor visitor); |
| 2136 } |
| 2137 |
| 2138 interface HBlockInformationVisitor { |
| 2139 bool visitLabeledBlockInfo(HLabeledBlockInformation info); |
| 2140 bool visitLoopInfo(HLoopInformation info); |
| 2141 bool visitIfInfo(HIfBlockInformation info); |
| 2142 bool visitAndOrInfo(HAndOrBlockInformation info); |
| 2143 } |
| 2144 |
| 2145 class HLabeledBlockInformation implements HBlockInformation { |
| 2146 final SubGraph body; |
| 2147 final HBasicBlock joinBlock; |
| 2148 final List<LabelElement> labels; |
| 2149 final TargetElement target; |
| 2150 final bool isContinue; |
| 2151 |
| 2152 HLabeledBlockInformation(this.body, this.joinBlock, |
| 2153 List<LabelElement> labels, |
| 2154 [this.isContinue = false]) : |
| 2155 this.labels = labels, this.target = labels[0].target; |
| 2156 |
| 2157 HLabeledBlockInformation.implicit(this.body, |
| 2158 this.joinBlock, |
| 2159 this.target, |
| 2160 [this.isContinue = false]) |
| 2161 : this.labels = const<LabelElement>[]; |
| 2162 |
| 2163 bool accept(HBlockInformationVisitor visitor) => |
| 2164 visitor.visitLabeledBlockInfo(this); |
| 2165 } |
| 2166 |
| 2167 class LoopTypeVisitor extends AbstractVisitor { |
| 2168 const LoopTypeVisitor(); |
| 2169 int visitNode(Node node) { |
| 2170 unreachable(); |
| 2171 } |
| 2172 int visitWhile(While node) => HLoopInformation.WHILE_LOOP; |
| 2173 int visitFor(For node) => HLoopInformation.FOR_LOOP; |
| 2174 int visitDoWhile(DoWhile node) => HLoopInformation.DO_WHILE_LOOP; |
| 2175 int visitForIn(ForIn node) => HLoopInformation.FOR_IN_LOOP; |
| 2176 } |
| 2177 |
| 2178 class HLoopInformation implements HBlockInformation { |
| 2179 static final int WHILE_LOOP = 0; |
| 2180 static final int FOR_LOOP = 1; |
| 2181 static final int DO_WHILE_LOOP = 2; |
| 2182 static final int FOR_IN_LOOP = 3; |
| 2183 |
| 2184 final int kind; |
| 2185 final HBasicBlock header; |
| 2186 final List<HBasicBlock> blocks; |
| 2187 final List<HBasicBlock> backEdges; |
| 2188 final List<LabelElement> labels; |
| 2189 final TargetElement target; |
| 2190 SubGraph initializer = null; |
| 2191 SubExpression condition = null; |
| 2192 SubGraph body = null; |
| 2193 SubGraph updates = null; |
| 2194 HBasicBlock joinBlock; |
| 2195 |
| 2196 HLoopInformation(this.kind, this.header, this.target, this.labels) |
| 2197 : blocks = new List<HBasicBlock>(), |
| 2198 backEdges = new List<HBasicBlock>(); |
| 2199 |
| 2200 static int loopType(Node node) { |
| 2201 return node.accept(const LoopTypeVisitor()); |
| 2202 } |
| 2203 |
| 2204 void addBackEdge(HBasicBlock predecessor) { |
| 2205 backEdges.add(predecessor); |
| 2206 addBlock(predecessor); |
| 2207 } |
| 2208 |
| 2209 // Adds a block and transitively all its predecessors in the loop as |
| 2210 // loop blocks. |
| 2211 void addBlock(HBasicBlock block) { |
| 2212 if (block === header) return; |
| 2213 HBasicBlock parentHeader = block.parentLoopHeader; |
| 2214 if (parentHeader === header) { |
| 2215 // Nothing to do in this case. |
| 2216 } else if (parentHeader !== null) { |
| 2217 addBlock(parentHeader); |
| 2218 } else { |
| 2219 block.parentLoopHeader = header; |
| 2220 blocks.add(block); |
| 2221 for (int i = 0, length = block.predecessors.length; i < length; i++) { |
| 2222 addBlock(block.predecessors[i]); |
| 2223 } |
| 2224 } |
| 2225 } |
| 2226 |
| 2227 HBasicBlock getLastBackEdge() { |
| 2228 int maxId = -1; |
| 2229 HBasicBlock result = null; |
| 2230 for (int i = 0, length = backEdges.length; i < length; i++) { |
| 2231 HBasicBlock current = backEdges[i]; |
| 2232 if (current.id > maxId) { |
| 2233 maxId = current.id; |
| 2234 result = current; |
| 2235 } |
| 2236 } |
| 2237 return result; |
| 2238 } |
| 2239 |
| 2240 bool accept(HBlockInformationVisitor visitor) => visitor.visitLoopInfo(this); |
| 2241 } |
| 2242 |
| 2243 class HIfBlockInformation implements HBlockInformation { |
| 2244 final SubExpression condition; |
2228 final SubGraph thenGraph; | 2245 final SubGraph thenGraph; |
2229 final SubGraph elseGraph; | 2246 final SubGraph elseGraph; |
2230 final HBasicBlock joinBlock; | 2247 final HBasicBlock joinBlock; |
2231 HIfBlockInformation(this.branch, | 2248 HIfBlockInformation(this.condition, |
2232 this.thenGraph, | 2249 this.thenGraph, |
2233 this.elseGraph, | 2250 this.elseGraph, |
2234 this.joinBlock); | 2251 this.joinBlock); |
| 2252 bool accept(HBlockInformationVisitor visitor) => visitor.visitIfInfo(this); |
2235 } | 2253 } |
| 2254 |
| 2255 class HAndOrBlockInformation implements HBlockInformation { |
| 2256 final bool isAnd; |
| 2257 final SubExpression left; |
| 2258 final SubExpression right; |
| 2259 final HBasicBlock joinBlock; |
| 2260 HAndOrBlockInformation(this.isAnd, |
| 2261 this.left, |
| 2262 this.right, |
| 2263 this.joinBlock); |
| 2264 bool accept(HBlockInformationVisitor visitor) => visitor.visitAndOrInfo(this); |
| 2265 } |
OLD | NEW |