| 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 |