| 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 class SsaPhiEliminator extends HGraphVisitor { | 5 class SsaPhiEliminator extends HGraphVisitor { |
| 6 HBasicBlock entry; | 6 HBasicBlock entry; |
| 7 HBasicBlock currentBlock; | 7 HBasicBlock currentBlock; |
| 8 | 8 |
| 9 visitGraph(HGraph graph) { | 9 visitGraph(HGraph graph) { |
| 10 entry = graph.entry; | 10 entry = graph.entry; |
| (...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 51 | 51 |
| 52 // We could not get to the definition, just put the store in the | 52 // We could not get to the definition, just put the store in the |
| 53 // predecessor. | 53 // predecessor. |
| 54 assert(store !== null); | 54 assert(store !== null); |
| 55 predecessor.addAtExit(store); | 55 predecessor.addAtExit(store); |
| 56 return store; | 56 return store; |
| 57 } | 57 } |
| 58 | 58 |
| 59 visitBasicBlock(HBasicBlock block) { | 59 visitBasicBlock(HBasicBlock block) { |
| 60 currentBlock = block; | 60 currentBlock = block; |
| 61 List<HLoad> loads = <HLoad>[]; | |
| 62 HPhi phi = block.phis.first; | 61 HPhi phi = block.phis.first; |
| 63 while (phi != null) { | 62 while (phi != null) { |
| 64 HPhi next = phi.next; | 63 HPhi next = phi.next; |
| 65 visitPhi(phi, loads); | 64 visitPhi(phi); |
| 66 phi = next; | 65 phi = next; |
| 67 } | 66 } |
| 68 } | 67 } |
| 69 | 68 |
| 70 visitPhi(HPhi phi, List<HLoad> loads) { | 69 visitPhi(HPhi phi) { |
| 71 assert(phi !== null); | 70 assert(phi !== null); |
| 72 if (phi.isLogicalOperator()) return; | 71 if (phi.isLogicalOperator()) return; |
| 73 HLocal local; | 72 HLocal local; |
| 74 if (phi.element != null) { | 73 if (phi.element != null) { |
| 75 local = new HLocal(phi.element); | 74 local = new HLocal(phi.element); |
| 76 entry.addAtEntry(local); | 75 entry.addAtEntry(local); |
| 77 if (phi.element.kind === ElementKind.PARAMETER) { | 76 if (phi.element.kind === ElementKind.PARAMETER) { |
| 78 // No need to generate the local, so move it out of the | 77 // No need to generate the local, so move it out of the |
| 79 // graph. | 78 // graph. |
| 80 entry.detach(local); | 79 entry.detach(local); |
| 81 } | 80 } |
| 82 } else { | 81 } else { |
| 83 local = new HLocal(null); | 82 local = new HLocal(null); |
| 84 entry.addAtEntry(local); | 83 entry.addAtEntry(local); |
| 85 } | 84 } |
| 86 | 85 |
| 87 | 86 |
| 88 List<HBasicBlock> predecessors = currentBlock.predecessors; | 87 List<HBasicBlock> predecessors = currentBlock.predecessors; |
| 89 List<HStore> stores = <HStore>[]; | |
| 90 | 88 |
| 91 for (int i = 0, len = predecessors.length; i < len; i++) { | 89 for (int i = 0, len = predecessors.length; i < len; i++) { |
| 92 HInstruction value = phi.inputs[i]; | 90 HInstruction value = phi.inputs[i]; |
| 93 | 91 |
| 94 // Storing a load of itself to a local can be safely eliminated. | 92 // Storing a load of itself to a local can be safely eliminated. |
| 95 if (value is HLoad && value.dynamic.local === local) continue; | 93 if (value is HLoad && value.dynamic.local === local) continue; |
| 96 | 94 |
| 97 HStore store = addStore(predecessors[i], | 95 HStore store = addStore(predecessors[i], |
| 98 currentBlock.dominator, | 96 currentBlock.dominator, |
| 99 local, | 97 local, |
| 100 value); | 98 value); |
| 101 | 99 |
| 102 if (store != null) { | 100 if (store != null) { |
| 103 if (local.declaredBy === local) { | 101 if (local.declaredBy === local) { |
| 104 HBasicBlock storeBlock = store.block; | 102 HBasicBlock storeBlock = store.block; |
| 105 // Check if the store occurs in or just after the entry block. | 103 // Check if the store occurs in or just after the entry block. |
| 106 if (storeBlock === entry || storeBlock === entry.successors[0]) { | 104 if (storeBlock === entry || storeBlock === entry.successors[0]) { |
| 107 if (phi.element != null && | 105 if (phi.element != null && |
| 108 phi.element.kind !== ElementKind.PARAMETER) { | 106 phi.element.kind !== ElementKind.PARAMETER) { |
| 109 entry.detach(local); | 107 entry.detach(local); |
| 110 } | 108 } |
| 111 local.declaredBy = store; | 109 local.declaredBy = store; |
| 112 } | 110 } |
| 113 } | 111 } |
| 114 stores.add(store); | |
| 115 } | 112 } |
| 116 } | 113 } |
| 117 | 114 |
| 118 // We propagate the type of the phi to the load instruction rather | 115 // We propagate the type of the phi to the load instruction rather |
| 119 // than the local because we may end up sharing a single local | 116 // than the local because we may end up sharing a single local |
| 120 // between different phis of different types. | 117 // between different phis of different types. |
| 121 HLoad load = new HLoad(local, phi.type); | 118 HLoad load = new HLoad(local, phi.type); |
| 122 loads.add(load); | |
| 123 | |
| 124 currentBlock.addAtEntry(load); | 119 currentBlock.addAtEntry(load); |
| 125 currentBlock.rewrite(phi, load); | 120 currentBlock.rewrite(phi, load); |
| 126 currentBlock.removePhi(phi); | 121 currentBlock.removePhi(phi); |
| 127 | 122 |
| 128 if (!currentBlock.isLoopHeader() || !hasLoopPhiAsInput(stores, loads)) { | 123 if (!currentBlock.isLoopHeader()) load.setGenerateAtUseSite(); |
| 129 load.setGenerateAtUseSite(); | |
| 130 } | |
| 131 } | |
| 132 | |
| 133 bool hasLoopPhiAsInput(List<HStore> stores, List<HLoad> loads) { | |
| 134 // [stores] contains the stores of a specific phi. | |
| 135 // [loads] contains the phis that were converted to loads. | |
| 136 assert(currentBlock.isLoopHeader()); | |
| 137 for (HStore store in stores) { | |
| 138 HInstruction value = store.value; | |
| 139 if (value is HPhi && value.block == currentBlock) { | |
| 140 return true; | |
| 141 } else if (value is HLoad && loads.indexOf(value) != -1) { | |
| 142 return true; | |
| 143 } | |
| 144 } | |
| 145 return false; | |
| 146 } | 124 } |
| 147 } | 125 } |
| OLD | NEW |