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