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

Side by Side Diff: lib/compiler/implementation/ssa/optimize.dart

Issue 11238035: Make isEmpty a getter. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Update status file with co19 issue number. Created 8 years, 1 month 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
« no previous file with comments | « lib/compiler/implementation/ssa/nodes.dart ('k') | lib/compiler/implementation/ssa/tracer.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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 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
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
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
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
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
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
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
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 }
OLDNEW
« no previous file with comments | « lib/compiler/implementation/ssa/nodes.dart ('k') | lib/compiler/implementation/ssa/tracer.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698