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