1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
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;
}
}
|
