| /* |
| * Copyright (C) 2007 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package com.android.dx.ssa.back; |
| |
| import com.android.dx.ssa.SsaMethod; |
| import com.android.dx.ssa.SsaBasicBlock; |
| import com.android.dx.ssa.SsaInsn; |
| import com.android.dx.ssa.PhiInsn; |
| import com.android.dx.rop.code.RegisterSpec; |
| |
| import java.util.BitSet; |
| import java.util.List; |
| import java.util.ArrayList; |
| |
| /** |
| * From Appel "Modern Compiler Implementation in Java" algorithm 19.17 |
| * Calculate the live ranges for register {@code reg}.<p> |
| * |
| * v = regV <p> |
| * s = insn <p> |
| * M = visitedBlocks <p> |
| */ |
| public class LivenessAnalyzer { |
| /** |
| * {@code non-null;} index by basic block indexed set of basic blocks |
| * that have already been visited. "M" as written in the original Appel |
| * algorithm. |
| */ |
| private final BitSet visitedBlocks; |
| |
| /** |
| * {@code non-null;} set of blocks remaing to visit as "live out as block" |
| */ |
| private final BitSet liveOutBlocks; |
| |
| /** |
| * {@code >=0;} SSA register currently being analyzed. |
| * "v" in the original Appel algorithm. |
| */ |
| private final int regV; |
| |
| /** method to process */ |
| private final SsaMethod ssaMeth; |
| |
| /** interference graph being updated */ |
| private final InterferenceGraph interference; |
| |
| /** block "n" in Appel 19.17 */ |
| private SsaBasicBlock blockN; |
| |
| /** index of statement {@code s} in {@code blockN} */ |
| private int statementIndex; |
| |
| /** the next function to call */ |
| private NextFunction nextFunction; |
| |
| /** constants for {@link #nextFunction} */ |
| private static enum NextFunction { |
| LIVE_IN_AT_STATEMENT, |
| LIVE_OUT_AT_STATEMENT, |
| LIVE_OUT_AT_BLOCK, |
| DONE; |
| } |
| |
| /** |
| * Runs register liveness algorithm for a method, updating the |
| * live in/out information in {@code SsaBasicBlock} instances and |
| * returning an interference graph. |
| * |
| * @param ssaMeth {@code non-null;} method to process |
| * @return {@code non-null;} interference graph indexed by SSA |
| * registers in both directions |
| */ |
| public static InterferenceGraph constructInterferenceGraph( |
| SsaMethod ssaMeth) { |
| int szRegs = ssaMeth.getRegCount(); |
| InterferenceGraph interference = new InterferenceGraph(szRegs); |
| |
| for (int i = 0; i < szRegs; i++) { |
| new LivenessAnalyzer(ssaMeth, i, interference).run(); |
| } |
| |
| coInterferePhis(ssaMeth, interference); |
| |
| return interference; |
| } |
| |
| /** |
| * Makes liveness analyzer instance for specific register. |
| * |
| * @param ssaMeth {@code non-null;} method to process |
| * @param reg register whose liveness to analyze |
| * @param interference {@code non-null;} indexed by SSA reg in |
| * both dimensions; graph to update |
| * |
| */ |
| private LivenessAnalyzer(SsaMethod ssaMeth, int reg, |
| InterferenceGraph interference) { |
| int blocksSz = ssaMeth.getBlocks().size(); |
| |
| this.ssaMeth = ssaMeth; |
| this.regV = reg; |
| visitedBlocks = new BitSet(blocksSz); |
| liveOutBlocks = new BitSet(blocksSz); |
| this.interference = interference; |
| } |
| |
| /** |
| * The algorithm in Appel is presented in partial tail-recursion |
| * form. Obviously, that's not efficient in java, so this function |
| * serves as the dispatcher instead. |
| */ |
| private void handleTailRecursion() { |
| while (nextFunction != NextFunction.DONE) { |
| switch (nextFunction) { |
| case LIVE_IN_AT_STATEMENT: |
| nextFunction = NextFunction.DONE; |
| liveInAtStatement(); |
| break; |
| |
| case LIVE_OUT_AT_STATEMENT: |
| nextFunction = NextFunction.DONE; |
| liveOutAtStatement(); |
| break; |
| |
| case LIVE_OUT_AT_BLOCK: |
| nextFunction = NextFunction.DONE; |
| liveOutAtBlock(); |
| break; |
| |
| default: |
| } |
| } |
| } |
| |
| /** |
| * From Appel algorithm 19.17. |
| */ |
| public void run() { |
| List<SsaInsn> useList = ssaMeth.getUseListForRegister(regV); |
| |
| for (SsaInsn insn : useList) { |
| nextFunction = NextFunction.DONE; |
| |
| if (insn instanceof PhiInsn) { |
| // If s is a phi-function with V as it's ith argument. |
| PhiInsn phi = (PhiInsn) insn; |
| |
| for (SsaBasicBlock pred : |
| phi.predBlocksForReg(regV, ssaMeth)) { |
| blockN = pred; |
| |
| nextFunction = NextFunction.LIVE_OUT_AT_BLOCK; |
| handleTailRecursion(); |
| } |
| } else { |
| blockN = insn.getBlock(); |
| statementIndex = blockN.getInsns().indexOf(insn); |
| |
| if (statementIndex < 0) { |
| throw new RuntimeException( |
| "insn not found in it's own block"); |
| } |
| |
| nextFunction = NextFunction.LIVE_IN_AT_STATEMENT; |
| handleTailRecursion(); |
| } |
| } |
| |
| int nextLiveOutBlock; |
| while ((nextLiveOutBlock = liveOutBlocks.nextSetBit(0)) >= 0) { |
| blockN = ssaMeth.getBlocks().get(nextLiveOutBlock); |
| liveOutBlocks.clear(nextLiveOutBlock); |
| nextFunction = NextFunction.LIVE_OUT_AT_BLOCK; |
| handleTailRecursion(); |
| } |
| } |
| |
| /** |
| * "v is live-out at n." |
| */ |
| private void liveOutAtBlock() { |
| if (! visitedBlocks.get(blockN.getIndex())) { |
| visitedBlocks.set(blockN.getIndex()); |
| |
| blockN.addLiveOut(regV); |
| |
| ArrayList<SsaInsn> insns; |
| |
| insns = blockN.getInsns(); |
| |
| // Live out at last statement in blockN |
| statementIndex = insns.size() - 1; |
| nextFunction = NextFunction.LIVE_OUT_AT_STATEMENT; |
| } |
| } |
| |
| /** |
| * "v is live-in at s." |
| */ |
| private void liveInAtStatement() { |
| // if s is the first statement in block N |
| if (statementIndex == 0) { |
| // v is live-in at n |
| blockN.addLiveIn(regV); |
| |
| BitSet preds = blockN.getPredecessors(); |
| |
| liveOutBlocks.or(preds); |
| } else { |
| // Let s' be the statement preceeding s |
| statementIndex -= 1; |
| nextFunction = NextFunction.LIVE_OUT_AT_STATEMENT; |
| } |
| } |
| |
| /** |
| * "v is live-out at s." |
| */ |
| private void liveOutAtStatement() { |
| SsaInsn statement = blockN.getInsns().get(statementIndex); |
| RegisterSpec rs = statement.getResult(); |
| |
| if (!statement.isResultReg(regV)) { |
| if (rs != null) { |
| interference.add(regV, rs.getReg()); |
| } |
| nextFunction = NextFunction.LIVE_IN_AT_STATEMENT; |
| } |
| } |
| |
| /** |
| * Ensures that all the phi result registers for all the phis in the |
| * same basic block interfere with each other. This is needed since |
| * the dead code remover has allowed through "dead-end phis" whose |
| * results are not used except as local assignments. Without this step, |
| * a the result of a dead-end phi might be assigned the same register |
| * as the result of another phi, and the phi removal move scheduler may |
| * generate moves that over-write the live result. |
| * |
| * @param ssaMeth {@code non-null;} method to pricess |
| * @param interference {@code non-null;} interference graph |
| */ |
| private static void coInterferePhis(SsaMethod ssaMeth, |
| InterferenceGraph interference) { |
| for (SsaBasicBlock b : ssaMeth.getBlocks()) { |
| List<SsaInsn> phis = b.getPhiInsns(); |
| |
| int szPhis = phis.size(); |
| |
| for (int i = 0; i < szPhis; i++) { |
| for (int j = 0; j < szPhis; j++) { |
| if (i == j) { |
| continue; |
| } |
| |
| interference.add(phis.get(i).getResult().getReg(), |
| phis.get(j).getResult().getReg()); |
| } |
| } |
| } |
| } |
| } |