diff options
Diffstat (limited to 'dx/src/com/android/dx/ssa/PhiTypeResolver.java')
| -rw-r--r-- | dx/src/com/android/dx/ssa/PhiTypeResolver.java | 200 |
1 files changed, 200 insertions, 0 deletions
diff --git a/dx/src/com/android/dx/ssa/PhiTypeResolver.java b/dx/src/com/android/dx/ssa/PhiTypeResolver.java new file mode 100644 index 0000000..4b8b4e3 --- /dev/null +++ b/dx/src/com/android/dx/ssa/PhiTypeResolver.java @@ -0,0 +1,200 @@ +/* + * 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; + +import com.android.dx.cf.code.Merger; +import com.android.dx.rop.code.RegisterSpec; +import com.android.dx.rop.code.RegisterSpecList; +import com.android.dx.rop.code.LocalItem; +import com.android.dx.rop.type.Type; +import com.android.dx.rop.type.TypeBearer; + +import java.util.BitSet; +import java.util.List; + +/** + * Resolves the result types of phi instructions. When phi instructions + * are inserted, their result types are set to BT_VOID (which is a nonsensical + * type for a register) but must be resolve to a real type before converting + * out of SSA form.<p> + * + * The resolve is done as an iterative merge of each phi's operand types. + * Phi operands may be themselves be the result of unresolved phis, + * and the algorithm tries to find the most-fit type (for example, if every + * operand is the same constant value or the same local variable info, we want + * that to be reflected).<p> + * + * This algorithm assumes a dead-code remover has already removed all + * circular-only phis that may have been inserted. + */ +public class PhiTypeResolver { + + SsaMethod ssaMeth; + /** indexed by register; all registers still defined by unresolved phis */ + private final BitSet worklist; + + /** + * Resolves all phi types in the method + * @param ssaMeth method to process + */ + public static void process (SsaMethod ssaMeth) { + new PhiTypeResolver(ssaMeth).run(); + } + + private PhiTypeResolver(SsaMethod ssaMeth) { + this.ssaMeth = ssaMeth; + worklist = new BitSet(ssaMeth.getRegCount()); + } + + /** + * Runs the phi-type resolver. + */ + private void run() { + + int regCount = ssaMeth.getRegCount(); + + for (int reg = 0; reg < regCount; reg++) { + SsaInsn definsn = ssaMeth.getDefinitionForRegister(reg); + + if (definsn != null + && (definsn.getResult().getBasicType() == Type.BT_VOID)) { + worklist.set(reg); + } + } + + int reg; + while ( 0 <= (reg = worklist.nextSetBit(0))) { + worklist.clear(reg); + + /* + * definitions on the worklist have a type of BT_VOID, which + * must have originated from a PhiInsn. + */ + PhiInsn definsn = (PhiInsn)ssaMeth.getDefinitionForRegister(reg); + + if (resolveResultType(definsn)) { + /* + * If the result type has changed, re-resolve all phis + * that use this. + */ + + List<SsaInsn> useList = ssaMeth.getUseListForRegister(reg); + + int sz = useList.size(); + for (int i = 0; i < sz; i++ ) { + SsaInsn useInsn = useList.get(i); + RegisterSpec resultReg = useInsn.getResult(); + if (resultReg != null && useInsn instanceof PhiInsn) { + worklist.set(resultReg.getReg()); + } + } + } + } + } + + /** + * Returns true if a and b are equal, whether + * or not either of them are null. + * @param a + * @param b + * @return true if equal + */ + private static boolean equalsHandlesNulls(LocalItem a, LocalItem b) { + return (a == b) || ((a != null) && a.equals(b)); + } + + /** + * Resolves the result of a phi insn based on its operands. The "void" + * type, which is a nonsensical type for a register, is used for + * registers defined by as-of-yet-unresolved phi operations. + * + * @return true if the result type changed, false if no change + */ + boolean resolveResultType(PhiInsn insn) { + insn.updateSourcesToDefinitions(ssaMeth); + + RegisterSpecList sources = insn.getSources(); + + // Start by finding the first non-void operand + RegisterSpec first = null; + int firstIndex = -1; + + int szSources = sources.size(); + for (int i = 0 ; i <szSources ; i++) { + RegisterSpec rs = sources.get(i); + + if (rs.getBasicType() != Type.BT_VOID) { + first = rs; + firstIndex = i; + } + } + + if (first == null) { + // All operands are void -- we're not ready to resolve yet + return false; + } + + LocalItem firstLocal = first.getLocalItem(); + TypeBearer mergedType = first.getType(); + boolean sameLocals = true; + for (int i = 0 ; i < szSources ; i++) { + if (i == firstIndex) { + continue; + } + + RegisterSpec rs = sources.get(i); + + // Just skip void (unresolved phi results) for now + if (rs.getBasicType() == Type.BT_VOID){ + continue; + } + + sameLocals = sameLocals + && equalsHandlesNulls(firstLocal, rs.getLocalItem()); + + mergedType = Merger.mergeType(mergedType, rs.getType()); + } + + TypeBearer newResultType; + + if (mergedType != null) { + newResultType = mergedType; + } else { + StringBuilder sb = new StringBuilder(); + + for (int i = 0; i < szSources; i++) { + sb.append(sources.get(i).toString()); + sb.append(' '); + } + + throw new RuntimeException ("Couldn't map types in phi insn:" + sb); + } + + LocalItem newLocal = sameLocals ? firstLocal : null; + + RegisterSpec result = insn.getResult(); + + if ((result.getTypeBearer() == newResultType) + && equalsHandlesNulls(newLocal, result.getLocalItem())) { + return false; + } + + insn.changeResultType(newResultType, newLocal); + + return true; + } +} |