1579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/* 2579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Copyright (C) 2007 The Android Open Source Project 3579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 4579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * you may not use this file except in compliance with the License. 6579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * You may obtain a copy of the License at 7579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 8579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 10579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * See the License for the specific language governing permissions and 14579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * limitations under the License. 15579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 16579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 17579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpackage com.android.dx.ssa; 18579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 19579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.cf.code.Merger; 20579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RegisterSpec; 21579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RegisterSpecList; 22579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.LocalItem; 23579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.type.Type; 24579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.type.TypeBearer; 25579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 26579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.BitSet; 27579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.List; 28579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 29579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/** 30579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Resolves the result types of phi instructions. When phi instructions 31579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * are inserted, their result types are set to BT_VOID (which is a nonsensical 32579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * type for a register) but must be resolve to a real type before converting 33579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * out of SSA form.<p> 34579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 35579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * The resolve is done as an iterative merge of each phi's operand types. 36579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Phi operands may be themselves be the result of unresolved phis, 37579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * and the algorithm tries to find the most-fit type (for example, if every 38579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * operand is the same constant value or the same local variable info, we want 39579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * that to be reflected).<p> 40579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 41579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * This algorithm assumes a dead-code remover has already removed all 42579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * circular-only phis that may have been inserted. 43579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 44579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic class PhiTypeResolver { 45579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 46579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaMethod ssaMeth; 47579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** indexed by register; all registers still defined by unresolved phis */ 48579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final BitSet worklist; 49579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 50579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 51579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Resolves all phi types in the method 52579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param ssaMeth method to process 53579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 54579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static void process (SsaMethod ssaMeth) { 55579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson new PhiTypeResolver(ssaMeth).run(); 56579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 57579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 58579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private PhiTypeResolver(SsaMethod ssaMeth) { 59579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.ssaMeth = ssaMeth; 60579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson worklist = new BitSet(ssaMeth.getRegCount()); 61579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 62579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 63579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 64579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Runs the phi-type resolver. 65579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 66579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void run() { 67579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 68579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int regCount = ssaMeth.getRegCount(); 69579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 70579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int reg = 0; reg < regCount; reg++) { 71579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn definsn = ssaMeth.getDefinitionForRegister(reg); 72579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 73579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (definsn != null 74579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson && (definsn.getResult().getBasicType() == Type.BT_VOID)) { 75579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson worklist.set(reg); 76579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 77579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 78579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 79579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int reg; 80579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson while ( 0 <= (reg = worklist.nextSetBit(0))) { 81579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson worklist.clear(reg); 82579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 83579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 84579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * definitions on the worklist have a type of BT_VOID, which 85579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * must have originated from a PhiInsn. 86579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 87579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson PhiInsn definsn = (PhiInsn)ssaMeth.getDefinitionForRegister(reg); 88579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 89579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (resolveResultType(definsn)) { 90579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 91579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * If the result type has changed, re-resolve all phis 92579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * that use this. 93579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 94579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 95579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson List<SsaInsn> useList = ssaMeth.getUseListForRegister(reg); 96579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 97579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int sz = useList.size(); 98579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < sz; i++ ) { 99579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn useInsn = useList.get(i); 100579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec resultReg = useInsn.getResult(); 101579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (resultReg != null && useInsn instanceof PhiInsn) { 102579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson worklist.set(resultReg.getReg()); 103579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 104579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 105579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 106579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 107579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 108579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 109579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 110579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns true if a and b are equal, whether 111579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * or not either of them are null. 112579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param a 113579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param b 114579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return true if equal 115579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 116579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static boolean equalsHandlesNulls(LocalItem a, LocalItem b) { 117579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return (a == b) || ((a != null) && a.equals(b)); 118579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 119579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 120579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 121579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Resolves the result of a phi insn based on its operands. The "void" 122579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * type, which is a nonsensical type for a register, is used for 123579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * registers defined by as-of-yet-unresolved phi operations. 124579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 125579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return true if the result type changed, false if no change 126579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 127579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson boolean resolveResultType(PhiInsn insn) { 128579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insn.updateSourcesToDefinitions(ssaMeth); 129579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 130579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecList sources = insn.getSources(); 131579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 132579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Start by finding the first non-void operand 133579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec first = null; 134579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int firstIndex = -1; 135579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 136579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int szSources = sources.size(); 137579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0 ; i <szSources ; i++) { 138579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec rs = sources.get(i); 139579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 140579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (rs.getBasicType() != Type.BT_VOID) { 141579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson first = rs; 142579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson firstIndex = i; 143579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 144579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 145579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 146579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (first == null) { 147579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // All operands are void -- we're not ready to resolve yet 148579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return false; 149579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 150579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 151579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson LocalItem firstLocal = first.getLocalItem(); 152579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson TypeBearer mergedType = first.getType(); 153579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson boolean sameLocals = true; 154579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0 ; i < szSources ; i++) { 155579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (i == firstIndex) { 156579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson continue; 157579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 158579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 159579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec rs = sources.get(i); 160579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 161579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Just skip void (unresolved phi results) for now 162579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (rs.getBasicType() == Type.BT_VOID){ 163579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson continue; 164579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 165579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 166579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sameLocals = sameLocals 167579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson && equalsHandlesNulls(firstLocal, rs.getLocalItem()); 168579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 169579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson mergedType = Merger.mergeType(mergedType, rs.getType()); 170579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 171579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 172579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson TypeBearer newResultType; 173579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 174579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (mergedType != null) { 175579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newResultType = mergedType; 176579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 177579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson StringBuilder sb = new StringBuilder(); 178579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 179579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < szSources; i++) { 180579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(sources.get(i).toString()); 181579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(' '); 182579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 183579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 184579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new RuntimeException ("Couldn't map types in phi insn:" + sb); 185579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 186579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 187579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson LocalItem newLocal = sameLocals ? firstLocal : null; 188579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 189579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec result = insn.getResult(); 190579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 191579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if ((result.getTypeBearer() == newResultType) 192579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson && equalsHandlesNulls(newLocal, result.getLocalItem())) { 193579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return false; 194579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 195579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 196579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insn.changeResultType(newResultType, newLocal); 197579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 198579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return true; 199579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 200579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson} 201