PhiTypeResolver.java revision fe107fb6e3f308ac5174ebdc5a794ee880c741d9 
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.LocalItem;
21import com.android.dx.rop.code.RegisterSpec;
22import com.android.dx.rop.code.RegisterSpecList;
23import com.android.dx.rop.type.Type;
24import com.android.dx.rop.type.TypeBearer;
25import java.util.BitSet;
26import 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 */
43public 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