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 abstract class OptimizationPhase { | 5 abstract class OptimizationPhase { |
6 String get name; | 6 String get name; |
7 void visitGraph(HGraph graph); | 7 void visitGraph(HGraph graph); |
8 } | 8 } |
9 | 9 |
10 class SsaOptimizerTask extends CompilerTask { | 10 class SsaOptimizerTask extends CompilerTask { |
(...skipping 63 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
74 // version. | 74 // version. |
75 // Note that we do this even if there were no guards inserted. If a | 75 // Note that we do this even if there were no guards inserted. If a |
76 // guard is not beneficial enough we don't emit one, but there might | 76 // guard is not beneficial enough we don't emit one, but there might |
77 // still be speculative types on the instructions. | 77 // still be speculative types on the instructions. |
78 new SsaTypePropagator(compiler, types), | 78 new SsaTypePropagator(compiler, types), |
79 // Then run the [SsaCheckInserter] because the type propagator also | 79 // Then run the [SsaCheckInserter] because the type propagator also |
80 // propagated types non-speculatively. For example, it might have | 80 // propagated types non-speculatively. For example, it might have |
81 // propagated the type array for a call to the List constructor. | 81 // propagated the type array for a call to the List constructor. |
82 new SsaCheckInserter(backend, types, context.boundsChecked)]; | 82 new SsaCheckInserter(backend, types, context.boundsChecked)]; |
83 runPhases(graph, phases); | 83 runPhases(graph, phases); |
84 return !work.guards.isEmpty(); | 84 return !work.guards.isEmpty; |
85 }); | 85 }); |
86 } | 86 } |
87 | 87 |
88 void prepareForSpeculativeOptimizations(WorkItem work, HGraph graph) { | 88 void prepareForSpeculativeOptimizations(WorkItem work, HGraph graph) { |
89 JavaScriptItemCompilationContext context = work.compilationContext; | 89 JavaScriptItemCompilationContext context = work.compilationContext; |
90 HTypeMap types = context.types; | 90 HTypeMap types = context.types; |
91 measure(() { | 91 measure(() { |
92 // In order to generate correct code for the bailout version, we did not | 92 // In order to generate correct code for the bailout version, we did not |
93 // propagate types from the instruction to the type guard. We do it | 93 // propagate types from the instruction to the type guard. We do it |
94 // now to be able to optimize further. | 94 // now to be able to optimize further. |
(...skipping 637 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
732 } | 732 } |
733 | 733 |
734 class SsaDeadCodeEliminator extends HGraphVisitor implements OptimizationPhase { | 734 class SsaDeadCodeEliminator extends HGraphVisitor implements OptimizationPhase { |
735 final HTypeMap types; | 735 final HTypeMap types; |
736 final String name = "SsaDeadCodeEliminator"; | 736 final String name = "SsaDeadCodeEliminator"; |
737 | 737 |
738 SsaDeadCodeEliminator(this.types); | 738 SsaDeadCodeEliminator(this.types); |
739 | 739 |
740 bool isDeadCode(HInstruction instruction) { | 740 bool isDeadCode(HInstruction instruction) { |
741 return !instruction.hasSideEffects(types) | 741 return !instruction.hasSideEffects(types) |
742 && instruction.usedBy.isEmpty() | 742 && instruction.usedBy.isEmpty |
743 // A dynamic getter that has no side effect can still throw | 743 // A dynamic getter that has no side effect can still throw |
744 // a NoSuchMethodError or a NullPointerException. | 744 // a NoSuchMethodError or a NullPointerException. |
745 && instruction is !HInvokeDynamicGetter | 745 && instruction is !HInvokeDynamicGetter |
746 && instruction is !HCheck | 746 && instruction is !HCheck |
747 && instruction is !HTypeGuard | 747 && instruction is !HTypeGuard |
748 && !instruction.isControlFlow(); | 748 && !instruction.isControlFlow(); |
749 } | 749 } |
750 | 750 |
751 void visitGraph(HGraph graph) { | 751 void visitGraph(HGraph graph) { |
752 visitPostDominatorTree(graph); | 752 visitPostDominatorTree(graph); |
(...skipping 25 matching lines...) Expand all Loading... |
778 if (user is !HPhi) { | 778 if (user is !HPhi) { |
779 worklist.add(phi); | 779 worklist.add(phi); |
780 livePhis.add(phi); | 780 livePhis.add(phi); |
781 break; | 781 break; |
782 } | 782 } |
783 } | 783 } |
784 }); | 784 }); |
785 } | 785 } |
786 | 786 |
787 // Process the worklist by propagating liveness to phi inputs. | 787 // Process the worklist by propagating liveness to phi inputs. |
788 while (!worklist.isEmpty()) { | 788 while (!worklist.isEmpty) { |
789 HPhi phi = worklist.removeLast(); | 789 HPhi phi = worklist.removeLast(); |
790 for (final input in phi.inputs) { | 790 for (final input in phi.inputs) { |
791 if (input is HPhi && !livePhis.contains(input)) { | 791 if (input is HPhi && !livePhis.contains(input)) { |
792 worklist.add(input); | 792 worklist.add(input); |
793 livePhis.add(input); | 793 livePhis.add(input); |
794 } | 794 } |
795 } | 795 } |
796 } | 796 } |
797 | 797 |
798 // Remove phis that are not live. | 798 // Remove phis that are not live. |
799 // Traverse in reverse order to remove phis with no uses before the | 799 // Traverse in reverse order to remove phis with no uses before the |
800 // phis that they might use. | 800 // phis that they might use. |
801 // NOTICE: Doesn't handle circular references, but we don't currently | 801 // NOTICE: Doesn't handle circular references, but we don't currently |
802 // create any. | 802 // create any. |
803 List<HBasicBlock> blocks = graph.blocks; | 803 List<HBasicBlock> blocks = graph.blocks; |
804 for (int i = blocks.length - 1; i >= 0; i--) { | 804 for (int i = blocks.length - 1; i >= 0; i--) { |
805 HBasicBlock block = blocks[i]; | 805 HBasicBlock block = blocks[i]; |
806 HPhi current = block.phis.first; | 806 HPhi current = block.phis.first; |
807 HPhi next = null; | 807 HPhi next = null; |
808 while (current != null) { | 808 while (current != null) { |
809 next = current.next; | 809 next = current.next; |
810 if (!livePhis.contains(current) | 810 if (!livePhis.contains(current) |
811 // TODO(ahe): Not sure the following is correct. | 811 // TODO(ahe): Not sure the following is correct. |
812 && current.usedBy.isEmpty()) { | 812 && current.usedBy.isEmpty) { |
813 block.removePhi(current); | 813 block.removePhi(current); |
814 } | 814 } |
815 current = next; | 815 current = next; |
816 } | 816 } |
817 } | 817 } |
818 } | 818 } |
819 } | 819 } |
820 | 820 |
821 class SsaRedundantPhiEliminator implements OptimizationPhase { | 821 class SsaRedundantPhiEliminator implements OptimizationPhase { |
822 final String name = "SsaRedundantPhiEliminator"; | 822 final String name = "SsaRedundantPhiEliminator"; |
823 | 823 |
824 void visitGraph(HGraph graph) { | 824 void visitGraph(HGraph graph) { |
825 final List<HPhi> worklist = <HPhi>[]; | 825 final List<HPhi> worklist = <HPhi>[]; |
826 | 826 |
827 // Add all phis in the worklist. | 827 // Add all phis in the worklist. |
828 for (final block in graph.blocks) { | 828 for (final block in graph.blocks) { |
829 block.forEachPhi((HPhi phi) => worklist.add(phi)); | 829 block.forEachPhi((HPhi phi) => worklist.add(phi)); |
830 } | 830 } |
831 | 831 |
832 while (!worklist.isEmpty()) { | 832 while (!worklist.isEmpty) { |
833 HPhi phi = worklist.removeLast(); | 833 HPhi phi = worklist.removeLast(); |
834 | 834 |
835 // If the phi has already been processed, continue. | 835 // If the phi has already been processed, continue. |
836 if (!phi.isInBasicBlock()) continue; | 836 if (!phi.isInBasicBlock()) continue; |
837 | 837 |
838 // Find if the inputs of the phi are the same instruction. | 838 // Find if the inputs of the phi are the same instruction. |
839 // The builder ensures that phi.inputs[0] cannot be the phi | 839 // The builder ensures that phi.inputs[0] cannot be the phi |
840 // itself. | 840 // itself. |
841 assert(!identical(phi.inputs[0], phi)); | 841 assert(!identical(phi.inputs[0], phi)); |
842 HInstruction candidate = phi.inputs[0]; | 842 HInstruction candidate = phi.inputs[0]; |
(...skipping 122 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
965 for (int i = 0, length = dominatedBlocks.length; i < length; i++) { | 965 for (int i = 0, length = dominatedBlocks.length; i < length; i++) { |
966 HBasicBlock dominated = dominatedBlocks[i]; | 966 HBasicBlock dominated = dominatedBlocks[i]; |
967 // No need to copy the value set for the last child. | 967 // No need to copy the value set for the last child. |
968 ValueSet successorValues = (i == length - 1) ? values : values.copy(); | 968 ValueSet successorValues = (i == length - 1) ? values : values.copy(); |
969 // If we have no values in our set, we do not have to kill | 969 // If we have no values in our set, we do not have to kill |
970 // anything. Also, if the range of block ids from the current | 970 // anything. Also, if the range of block ids from the current |
971 // block to the dominated block is empty, there is no blocks on | 971 // block to the dominated block is empty, there is no blocks on |
972 // any path from the current block to the dominated block so we | 972 // any path from the current block to the dominated block so we |
973 // don't have to do anything either. | 973 // don't have to do anything either. |
974 assert(block.id < dominated.id); | 974 assert(block.id < dominated.id); |
975 if (!successorValues.isEmpty() && block.id + 1 < dominated.id) { | 975 if (!successorValues.isEmpty && block.id + 1 < dominated.id) { |
976 visited.clear(); | 976 visited.clear(); |
977 int changesFlags = getChangesFlagsForDominatedBlock(block, dominated); | 977 int changesFlags = getChangesFlagsForDominatedBlock(block, dominated); |
978 successorValues.kill(changesFlags); | 978 successorValues.kill(changesFlags); |
979 } | 979 } |
980 visitBasicBlock(dominated, successorValues); | 980 visitBasicBlock(dominated, successorValues); |
981 } | 981 } |
982 } | 982 } |
983 | 983 |
984 void computeChangesFlags(HGraph graph) { | 984 void computeChangesFlags(HGraph graph) { |
985 // Create the changes flags lists. Make sure to initialize the | 985 // Create the changes flags lists. Make sure to initialize the |
(...skipping 90 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1076 // Phase 1: get the ValueSet of all successors (if there are more than one), | 1076 // Phase 1: get the ValueSet of all successors (if there are more than one), |
1077 // compute the intersection and move the instructions of the intersection | 1077 // compute the intersection and move the instructions of the intersection |
1078 // into this block. | 1078 // into this block. |
1079 if (successors.length > 1) { | 1079 if (successors.length > 1) { |
1080 ValueSet instructions = values[successors[0].id]; | 1080 ValueSet instructions = values[successors[0].id]; |
1081 for (int i = 1; i < successors.length; i++) { | 1081 for (int i = 1; i < successors.length; i++) { |
1082 ValueSet other = values[successors[i].id]; | 1082 ValueSet other = values[successors[i].id]; |
1083 instructions = instructions.intersection(other); | 1083 instructions = instructions.intersection(other); |
1084 } | 1084 } |
1085 | 1085 |
1086 if (!instructions.isEmpty()) { | 1086 if (!instructions.isEmpty) { |
1087 List<HInstruction> list = instructions.toList(); | 1087 List<HInstruction> list = instructions.toList(); |
1088 for (HInstruction instruction in list) { | 1088 for (HInstruction instruction in list) { |
1089 // Move the instruction to the current block. | 1089 // Move the instruction to the current block. |
1090 instruction.block.detach(instruction); | 1090 instruction.block.detach(instruction); |
1091 block.moveAtExit(instruction); | 1091 block.moveAtExit(instruction); |
1092 // Go through all successors and rewrite their instruction | 1092 // Go through all successors and rewrite their instruction |
1093 // to the shared one. | 1093 // to the shared one. |
1094 for (final successor in successors) { | 1094 for (final successor in successors) { |
1095 HInstruction toRewrite = values[successor.id].lookup(instruction); | 1095 HInstruction toRewrite = values[successor.id].lookup(instruction); |
1096 if (toRewrite != instruction) { | 1096 if (toRewrite != instruction) { |
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1151 visitDominatorTree(graph); | 1151 visitDominatorTree(graph); |
1152 } | 1152 } |
1153 | 1153 |
1154 | 1154 |
1155 // Update users of [input] that are dominated by [:dominator.first:] | 1155 // Update users of [input] that are dominated by [:dominator.first:] |
1156 // to use [newInput] instead. | 1156 // to use [newInput] instead. |
1157 void changeUsesDominatedBy(HBasicBlock dominator, | 1157 void changeUsesDominatedBy(HBasicBlock dominator, |
1158 HInstruction input, | 1158 HInstruction input, |
1159 HType convertedType) { | 1159 HType convertedType) { |
1160 Set<HInstruction> dominatedUsers = input.dominatedUsers(dominator.first); | 1160 Set<HInstruction> dominatedUsers = input.dominatedUsers(dominator.first); |
1161 if (dominatedUsers.isEmpty()) return; | 1161 if (dominatedUsers.isEmpty) return; |
1162 | 1162 |
1163 HTypeConversion newInput = new HTypeConversion(convertedType, input); | 1163 HTypeConversion newInput = new HTypeConversion(convertedType, input); |
1164 dominator.addBefore(dominator.first, newInput); | 1164 dominator.addBefore(dominator.first, newInput); |
1165 dominatedUsers.forEach((HInstruction user) { | 1165 dominatedUsers.forEach((HInstruction user) { |
1166 user.changeUse(input, newInput); | 1166 user.changeUse(input, newInput); |
1167 }); | 1167 }); |
1168 } | 1168 } |
1169 | 1169 |
1170 void visitIs(HIs instruction) { | 1170 void visitIs(HIs instruction) { |
1171 HInstruction input = instruction.expression; | 1171 HInstruction input = instruction.expression; |
1172 HType convertedType = | 1172 HType convertedType = |
1173 new HType.fromBoundedType(instruction.typeExpression, compiler); | 1173 new HType.fromBoundedType(instruction.typeExpression, compiler); |
1174 | 1174 |
1175 List<HInstruction> ifUsers = <HInstruction>[]; | 1175 List<HInstruction> ifUsers = <HInstruction>[]; |
1176 List<HInstruction> notIfUsers = <HInstruction>[]; | 1176 List<HInstruction> notIfUsers = <HInstruction>[]; |
1177 | 1177 |
1178 for (HInstruction user in instruction.usedBy) { | 1178 for (HInstruction user in instruction.usedBy) { |
1179 if (user is HIf) { | 1179 if (user is HIf) { |
1180 ifUsers.add(user); | 1180 ifUsers.add(user); |
1181 } else if (user is HNot) { | 1181 } else if (user is HNot) { |
1182 for (HInstruction notUser in user.usedBy) { | 1182 for (HInstruction notUser in user.usedBy) { |
1183 if (notUser is HIf) notIfUsers.add(notUser); | 1183 if (notUser is HIf) notIfUsers.add(notUser); |
1184 } | 1184 } |
1185 } | 1185 } |
1186 } | 1186 } |
1187 | 1187 |
1188 if (ifUsers.isEmpty() && notIfUsers.isEmpty()) return; | 1188 if (ifUsers.isEmpty && notIfUsers.isEmpty) return; |
1189 | 1189 |
1190 for (HIf ifUser in ifUsers) { | 1190 for (HIf ifUser in ifUsers) { |
1191 changeUsesDominatedBy(ifUser.thenBlock, input, convertedType); | 1191 changeUsesDominatedBy(ifUser.thenBlock, input, convertedType); |
1192 // TODO(ngeoffray): Also change uses for the else block on a HType | 1192 // TODO(ngeoffray): Also change uses for the else block on a HType |
1193 // that knows it is not of a specific Type. | 1193 // that knows it is not of a specific Type. |
1194 } | 1194 } |
1195 | 1195 |
1196 for (HIf ifUser in notIfUsers) { | 1196 for (HIf ifUser in notIfUsers) { |
1197 changeUsesDominatedBy(ifUser.elseBlock, input, convertedType); | 1197 changeUsesDominatedBy(ifUser.elseBlock, input, convertedType); |
1198 // TODO(ngeoffray): Also change uses for the then block on a HType | 1198 // TODO(ngeoffray): Also change uses for the then block on a HType |
(...skipping 138 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1337 } | 1337 } |
1338 | 1338 |
1339 // For other fields having setters in the generative constructor body, set | 1339 // For other fields having setters in the generative constructor body, set |
1340 // the type to UNKNOWN to avoid relying on the type set in the initializer | 1340 // the type to UNKNOWN to avoid relying on the type set in the initializer |
1341 // list. | 1341 // list. |
1342 allSetters.forEach((Element element) { | 1342 allSetters.forEach((Element element) { |
1343 backend.registerFieldConstructor(element, HType.UNKNOWN); | 1343 backend.registerFieldConstructor(element, HType.UNKNOWN); |
1344 }); | 1344 }); |
1345 } | 1345 } |
1346 } | 1346 } |
OLD | NEW |