PhiTypeResolver.java revision de75089fb7216d19e9c22cce4dc62a49513477d3 
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