Home | History | Annotate | Download | only in ssa 
      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;
     18 
     19 import com.android.dx.cf.code.Merger;
     20 import com.android.dx.rop.code.LocalItem;
     21 import com.android.dx.rop.code.RegisterSpec;
     22 import com.android.dx.rop.code.RegisterSpecList;
     23 import com.android.dx.rop.type.Type;
     24 import com.android.dx.rop.type.TypeBearer;
     25 import java.util.BitSet;
     26 import java.util.List;
     27 
     28 /**
     29  * Resolves the result types of phi instructions. When phi instructions
     30  * are inserted, their result types are set to BT_VOID (which is a nonsensical
     31  * type for a register) but must be resolve to a real type before converting
     32  * out of SSA form.<p>
     33  *
     34  * The resolve is done as an iterative merge of each phi's operand types.
     35  * Phi operands may be themselves be the result of unresolved phis,
     36  * and the algorithm tries to find the most-fit type (for example, if every
     37  * operand is the same constant value or the same local variable info, we want
     38  * that to be reflected).<p>
     39  *
     40  * This algorithm assumes a dead-code remover has already removed all
     41  * circular-only phis that may have been inserted.
     42  */
     43 public class PhiTypeResolver {
     44 
     45     SsaMethod ssaMeth;
     46     /** indexed by register; all registers still defined by unresolved phis */
     47     private final BitSet worklist;
     48 
     49     /**
     50      * Resolves all phi types in the method
     51      * @param ssaMeth method to process
     52      */
     53     public static void process (SsaMethod ssaMeth) {
     54         new PhiTypeResolver(ssaMeth).run();
     55     }
     56 
     57     private PhiTypeResolver(SsaMethod ssaMeth) {
     58         this.ssaMeth = ssaMeth;
     59         worklist = new BitSet(ssaMeth.getRegCount());
     60     }
     61 
     62     /**
     63      * Runs the phi-type resolver.
     64      */
     65     private void run() {
     66 
     67         int regCount = ssaMeth.getRegCount();
     68 
     69         for (int reg = 0; reg < regCount; reg++) {
     70             SsaInsn definsn = ssaMeth.getDefinitionForRegister(reg);
     71 
     72             if (definsn != null
     73                     && (definsn.getResult().getBasicType() == Type.BT_VOID)) {
     74                 worklist.set(reg);
     75             }
     76         }
     77 
     78         int reg;
     79         while ( 0 <= (reg = worklist.nextSetBit(0))) {
     80             worklist.clear(reg);
     81 
     82             /*
     83              * definitions on the worklist have a type of BT_VOID, which
     84              * must have originated from a PhiInsn.
     85              */
     86             PhiInsn definsn = (PhiInsn)ssaMeth.getDefinitionForRegister(reg);
     87 
     88             if (resolveResultType(definsn)) {
     89                 /*
     90                  * If the result type has changed, re-resolve all phis
     91                  * that use this.
     92                  */
     93 
     94                 List<SsaInsn> useList = ssaMeth.getUseListForRegister(reg);
     95 
     96                 int sz = useList.size();
     97                 for (int i = 0; i < sz; i++ ) {
     98                     SsaInsn useInsn = useList.get(i);
     99                     RegisterSpec resultReg = useInsn.getResult();
    100                     if (resultReg != null && useInsn instanceof PhiInsn) {
    101                         worklist.set(resultReg.getReg());
    102                     }
    103                 }
    104             }
    105         }
    106     }
    107 
    108     /**
    109      * Returns true if a and b are equal, whether
    110      * or not either of them are null.
    111      * @param a
    112      * @param b
    113      * @return true if equal
    114      */
    115     private static boolean equalsHandlesNulls(LocalItem a, LocalItem b) {
    116         return (a == b) || ((a != null) && a.equals(b));
    117     }
    118 
    119     /**
    120      * Resolves the result of a phi insn based on its operands. The "void"
    121      * type, which is a nonsensical type for a register, is used for
    122      * registers defined by as-of-yet-unresolved phi operations.
    123      *
    124      * @return true if the result type changed, false if no change
    125      */
    126     boolean resolveResultType(PhiInsn insn) {
    127         insn.updateSourcesToDefinitions(ssaMeth);
    128 
    129         RegisterSpecList sources = insn.getSources();
    130 
    131         // Start by finding the first non-void operand
    132         RegisterSpec first = null;
    133         int firstIndex = -1;
    134 
    135         int szSources = sources.size();
    136         for (int i = 0 ; i <szSources ; i++) {
    137             RegisterSpec rs = sources.get(i);
    138 
    139             if (rs.getBasicType() != Type.BT_VOID) {
    140                 first = rs;
    141                 firstIndex = i;
    142             }
    143         }
    144 
    145         if (first == null) {
    146             // All operands are void -- we're not ready to resolve yet
    147             return false;
    148         }
    149 
    150         LocalItem firstLocal = first.getLocalItem();
    151         TypeBearer mergedType = first.getType();
    152         boolean sameLocals = true;
    153         for (int i = 0 ; i < szSources ; i++) {
    154             if (i == firstIndex) {
    155                 continue;
    156             }
    157 
    158             RegisterSpec rs = sources.get(i);
    159 
    160             // Just skip void (unresolved phi results) for now
    161             if (rs.getBasicType() == Type.BT_VOID){
    162                 continue;
    163             }
    164 
    165             sameLocals = sameLocals
    166                     && equalsHandlesNulls(firstLocal, rs.getLocalItem());
    167 
    168             mergedType = Merger.mergeType(mergedType, rs.getType());
    169         }
    170 
    171         TypeBearer newResultType;
    172 
    173         if (mergedType != null) {
    174             newResultType = mergedType;
    175         } else {
    176             StringBuilder sb = new StringBuilder();
    177 
    178             for (int i = 0; i < szSources; i++) {
    179                 sb.append(sources.get(i).toString());
    180                 sb.append(' ');
    181             }
    182 
    183             throw new RuntimeException ("Couldn't map types in phi insn:" + sb);
    184         }
    185 
    186         LocalItem newLocal = sameLocals ? firstLocal : null;
    187 
    188         RegisterSpec result = insn.getResult();
    189 
    190         if ((result.getTypeBearer() == newResultType)
    191                 && equalsHandlesNulls(newLocal, result.getLocalItem())) {
    192             return false;
    193         }
    194 
    195         insn.changeResultType(newResultType, newLocal);
    196 
    197         return true;
    198     }
    199 }
    200