1 /* 2 * Copyright (C) 2007 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.dx.ssa.back; 18 19 import com.android.dx.rop.code.RegisterSpec; 20 import com.android.dx.ssa.PhiInsn; 21 import com.android.dx.ssa.SsaBasicBlock; 22 import com.android.dx.ssa.SsaInsn; 23 import com.android.dx.ssa.SsaMethod; 24 import java.util.ArrayList; 25 import java.util.BitSet; 26 import java.util.List; 27 28 /** 29 * From Appel "Modern Compiler Implementation in Java" algorithm 19.17 30 * Calculate the live ranges for register {@code reg}.<p> 31 * 32 * v = regV <p> 33 * s = insn <p> 34 * M = visitedBlocks <p> 35 */ 36 public class LivenessAnalyzer { 37 /** 38 * {@code non-null;} index by basic block indexed set of basic blocks 39 * that have already been visited. "M" as written in the original Appel 40 * algorithm. 41 */ 42 private final BitSet visitedBlocks; 43 44 /** 45 * {@code non-null;} set of blocks remaing to visit as "live out as block" 46 */ 47 private final BitSet liveOutBlocks; 48 49 /** 50 * {@code >=0;} SSA register currently being analyzed. 51 * "v" in the original Appel algorithm. 52 */ 53 private final int regV; 54 55 /** method to process */ 56 private final SsaMethod ssaMeth; 57 58 /** interference graph being updated */ 59 private final InterferenceGraph interference; 60 61 /** block "n" in Appel 19.17 */ 62 private SsaBasicBlock blockN; 63 64 /** index of statement {@code s} in {@code blockN} */ 65 private int statementIndex; 66 67 /** the next function to call */ 68 private NextFunction nextFunction; 69 70 /** constants for {@link #nextFunction} */ 71 private static enum NextFunction { 72 LIVE_IN_AT_STATEMENT, 73 LIVE_OUT_AT_STATEMENT, 74 LIVE_OUT_AT_BLOCK, 75 DONE; 76 } 77 78 /** 79 * Runs register liveness algorithm for a method, updating the 80 * live in/out information in {@code SsaBasicBlock} instances and 81 * returning an interference graph. 82 * 83 * @param ssaMeth {@code non-null;} method to process 84 * @return {@code non-null;} interference graph indexed by SSA 85 * registers in both directions 86 */ constructInterferenceGraph( SsaMethod ssaMeth)87 public static InterferenceGraph constructInterferenceGraph( 88 SsaMethod ssaMeth) { 89 int szRegs = ssaMeth.getRegCount(); 90 InterferenceGraph interference = new InterferenceGraph(szRegs); 91 92 for (int i = 0; i < szRegs; i++) { 93 new LivenessAnalyzer(ssaMeth, i, interference).run(); 94 } 95 96 coInterferePhis(ssaMeth, interference); 97 98 return interference; 99 } 100 101 /** 102 * Makes liveness analyzer instance for specific register. 103 * 104 * @param ssaMeth {@code non-null;} method to process 105 * @param reg register whose liveness to analyze 106 * @param interference {@code non-null;} indexed by SSA reg in 107 * both dimensions; graph to update 108 * 109 */ LivenessAnalyzer(SsaMethod ssaMeth, int reg, InterferenceGraph interference)110 private LivenessAnalyzer(SsaMethod ssaMeth, int reg, 111 InterferenceGraph interference) { 112 int blocksSz = ssaMeth.getBlocks().size(); 113 114 this.ssaMeth = ssaMeth; 115 this.regV = reg; 116 visitedBlocks = new BitSet(blocksSz); 117 liveOutBlocks = new BitSet(blocksSz); 118 this.interference = interference; 119 } 120 121 /** 122 * The algorithm in Appel is presented in partial tail-recursion 123 * form. Obviously, that's not efficient in java, so this function 124 * serves as the dispatcher instead. 125 */ handleTailRecursion()126 private void handleTailRecursion() { 127 while (nextFunction != NextFunction.DONE) { 128 switch (nextFunction) { 129 case LIVE_IN_AT_STATEMENT: 130 nextFunction = NextFunction.DONE; 131 liveInAtStatement(); 132 break; 133 134 case LIVE_OUT_AT_STATEMENT: 135 nextFunction = NextFunction.DONE; 136 liveOutAtStatement(); 137 break; 138 139 case LIVE_OUT_AT_BLOCK: 140 nextFunction = NextFunction.DONE; 141 liveOutAtBlock(); 142 break; 143 144 default: 145 } 146 } 147 } 148 149 /** 150 * From Appel algorithm 19.17. 151 */ run()152 public void run() { 153 List<SsaInsn> useList = ssaMeth.getUseListForRegister(regV); 154 155 for (SsaInsn insn : useList) { 156 nextFunction = NextFunction.DONE; 157 158 if (insn instanceof PhiInsn) { 159 // If s is a phi-function with V as it's ith argument. 160 PhiInsn phi = (PhiInsn) insn; 161 162 for (SsaBasicBlock pred : 163 phi.predBlocksForReg(regV, ssaMeth)) { 164 blockN = pred; 165 166 nextFunction = NextFunction.LIVE_OUT_AT_BLOCK; 167 handleTailRecursion(); 168 } 169 } else { 170 blockN = insn.getBlock(); 171 statementIndex = blockN.getInsns().indexOf(insn); 172 173 if (statementIndex < 0) { 174 throw new RuntimeException( 175 "insn not found in it's own block"); 176 } 177 178 nextFunction = NextFunction.LIVE_IN_AT_STATEMENT; 179 handleTailRecursion(); 180 } 181 } 182 183 int nextLiveOutBlock; 184 while ((nextLiveOutBlock = liveOutBlocks.nextSetBit(0)) >= 0) { 185 blockN = ssaMeth.getBlocks().get(nextLiveOutBlock); 186 liveOutBlocks.clear(nextLiveOutBlock); 187 nextFunction = NextFunction.LIVE_OUT_AT_BLOCK; 188 handleTailRecursion(); 189 } 190 } 191 192 /** 193 * "v is live-out at n." 194 */ liveOutAtBlock()195 private void liveOutAtBlock() { 196 if (! visitedBlocks.get(blockN.getIndex())) { 197 visitedBlocks.set(blockN.getIndex()); 198 199 blockN.addLiveOut(regV); 200 201 ArrayList<SsaInsn> insns; 202 203 insns = blockN.getInsns(); 204 205 // Live out at last statement in blockN 206 statementIndex = insns.size() - 1; 207 nextFunction = NextFunction.LIVE_OUT_AT_STATEMENT; 208 } 209 } 210 211 /** 212 * "v is live-in at s." 213 */ liveInAtStatement()214 private void liveInAtStatement() { 215 // if s is the first statement in block N 216 if (statementIndex == 0) { 217 // v is live-in at n 218 blockN.addLiveIn(regV); 219 220 BitSet preds = blockN.getPredecessors(); 221 222 liveOutBlocks.or(preds); 223 } else { 224 // Let s' be the statement preceeding s 225 statementIndex -= 1; 226 nextFunction = NextFunction.LIVE_OUT_AT_STATEMENT; 227 } 228 } 229 230 /** 231 * "v is live-out at s." 232 */ liveOutAtStatement()233 private void liveOutAtStatement() { 234 SsaInsn statement = blockN.getInsns().get(statementIndex); 235 RegisterSpec rs = statement.getResult(); 236 237 if (!statement.isResultReg(regV)) { 238 if (rs != null) { 239 interference.add(regV, rs.getReg()); 240 } 241 nextFunction = NextFunction.LIVE_IN_AT_STATEMENT; 242 } 243 } 244 245 /** 246 * Ensures that all the phi result registers for all the phis in the 247 * same basic block interfere with each other. This is needed since 248 * the dead code remover has allowed through "dead-end phis" whose 249 * results are not used except as local assignments. Without this step, 250 * a the result of a dead-end phi might be assigned the same register 251 * as the result of another phi, and the phi removal move scheduler may 252 * generate moves that over-write the live result. 253 * 254 * @param ssaMeth {@code non-null;} method to pricess 255 * @param interference {@code non-null;} interference graph 256 */ coInterferePhis(SsaMethod ssaMeth, InterferenceGraph interference)257 private static void coInterferePhis(SsaMethod ssaMeth, 258 InterferenceGraph interference) { 259 for (SsaBasicBlock b : ssaMeth.getBlocks()) { 260 List<SsaInsn> phis = b.getPhiInsns(); 261 262 int szPhis = phis.size(); 263 264 for (int i = 0; i < szPhis; i++) { 265 for (int j = 0; j < szPhis; j++) { 266 if (i == j) { 267 continue; 268 } 269 270 interference.add(phis.get(i).getResult().getReg(), 271 phis.get(j).getResult().getReg()); 272 } 273 } 274 } 275 } 276 } 277