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 
17 package com.android.dx.ssa;
18 
19 import com.android.dx.rop.code.RegisterSpecSet;
20 import com.android.dx.rop.code.RegisterSpec;
21 import com.android.dx.util.IntList;
22 
23 import java.util.ArrayList;
24 import java.util.BitSet;
25 import java.util.List;
26 
27 /**
28  * Code to figure out which local variables are active at which points in
29  * a method. Stolen and retrofitted from
30  * com.android.dx.rop.code.LocalVariableExtractor
31  *
32  * TODO remove this. Allow Rop-form LocalVariableInfo to be passed in,
33  * converted, and adapted through edge-splitting.
34  */
35 public class LocalVariableExtractor {
36     /** {@code non-null;} method being extracted from */
37     private final SsaMethod method;
38 
39     /** {@code non-null;} block list for the method */
40     private final ArrayList<SsaBasicBlock> blocks;
41 
42     /** {@code non-null;} result in-progress */
43     private final LocalVariableInfo resultInfo;
44 
45     /** {@code non-null;} work set indicating blocks needing to be processed */
46     private final BitSet workSet;
47 
48     /**
49      * Extracts out all the local variable information from the given method.
50      *
51      * @param method {@code non-null;} the method to extract from
52      * @return {@code non-null;} the extracted information
53      */
extract(SsaMethod method)54     public static LocalVariableInfo extract(SsaMethod method) {
55         LocalVariableExtractor lve = new LocalVariableExtractor(method);
56         return lve.doit();
57     }
58 
59     /**
60      * Constructs an instance. This method is private. Use {@link #extract}.
61      *
62      * @param method {@code non-null;} the method to extract from
63      */
LocalVariableExtractor(SsaMethod method)64     private LocalVariableExtractor(SsaMethod method) {
65         if (method == null) {
66             throw new NullPointerException("method == null");
67         }
68 
69         ArrayList<SsaBasicBlock> blocks = method.getBlocks();
70 
71         this.method = method;
72         this.blocks = blocks;
73         this.resultInfo = new LocalVariableInfo(method);
74         this.workSet = new BitSet(blocks.size());
75     }
76 
77     /**
78      * Does the extraction.
79      *
80      * @return {@code non-null;} the extracted information
81      */
doit()82     private LocalVariableInfo doit() {
83 
84         //FIXME why is this needed here?
85         if (method.getRegCount() > 0 ) {
86             for (int bi = method.getEntryBlockIndex();
87                  bi >= 0;
88                  bi = workSet.nextSetBit(0)) {
89                 workSet.clear(bi);
90                 processBlock(bi);
91             }
92         }
93 
94         resultInfo.setImmutable();
95         return resultInfo;
96     }
97 
98     /**
99      * Processes a single block.
100      *
101      * @param blockIndex {@code >= 0;} block index of the block to process
102      */
processBlock(int blockIndex)103     private void processBlock(int blockIndex) {
104         RegisterSpecSet primaryState
105                 = resultInfo.mutableCopyOfStarts(blockIndex);
106         SsaBasicBlock block = blocks.get(blockIndex);
107         List<SsaInsn> insns = block.getInsns();
108         int insnSz = insns.size();
109 
110         // The exit block has no insns and no successors
111         if (blockIndex == method.getExitBlockIndex()) {
112             return;
113         }
114 
115         /*
116          * We may have to treat the last instruction specially: If it
117          * can (but doesn't always) throw, and the exception can be
118          * caught within the same method, then we need to use the
119          * state *before* executing it to be what is merged into
120          * exception targets.
121          */
122         SsaInsn lastInsn = insns.get(insnSz - 1);
123         boolean hasExceptionHandlers
124                 = lastInsn.getOriginalRopInsn().getCatches().size() !=0 ;
125         boolean canThrowDuringLastInsn = hasExceptionHandlers
126                 && (lastInsn.getResult() != null);
127         int freezeSecondaryStateAt = insnSz - 1;
128         RegisterSpecSet secondaryState = primaryState;
129 
130         /*
131          * Iterate over the instructions, adding information for each place
132          * that the active variable set changes.
133          */
134 
135         for (int i = 0; i < insnSz; i++) {
136             if (canThrowDuringLastInsn && (i == freezeSecondaryStateAt)) {
137                 // Until this point, primaryState == secondaryState.
138                 primaryState.setImmutable();
139                 primaryState = primaryState.mutableCopy();
140             }
141 
142             SsaInsn insn = insns.get(i);
143             RegisterSpec result;
144 
145             result = insn.getLocalAssignment();
146 
147             if (result == null) {
148                 // We may be nuking an existing local
149 
150                 result = insn.getResult();
151 
152                 if (result != null && primaryState.get(result.getReg()) != null) {
153                     primaryState.remove(primaryState.get(result.getReg()));
154                 }
155                 continue;
156             }
157 
158             result = result.withSimpleType();
159 
160             RegisterSpec already = primaryState.get(result);
161             /*
162              * The equals() check ensures we only add new info if
163              * the instruction causes a change to the set of
164              * active variables.
165              */
166             if (!result.equals(already)) {
167                 /*
168                  * If this insn represents a local moving from one register
169                  * to another, remove the association between the old register
170                  * and the local.
171                  */
172                 RegisterSpec previous
173                         = primaryState.localItemToSpec(result.getLocalItem());
174 
175                 if (previous != null
176                         && (previous.getReg() != result.getReg())) {
177 
178                     primaryState.remove(previous);
179                 }
180 
181                 resultInfo.addAssignment(insn, result);
182                 primaryState.put(result);
183             }
184         }
185 
186         primaryState.setImmutable();
187 
188         /*
189          * Merge this state into the start state for each successor,
190          * and update the work set where required (that is, in cases
191          * where the start state for a block changes).
192          */
193 
194         IntList successors = block.getSuccessorList();
195         int succSz = successors.size();
196         int primarySuccessor = block.getPrimarySuccessorIndex();
197 
198         for (int i = 0; i < succSz; i++) {
199             int succ = successors.get(i);
200             RegisterSpecSet state = (succ == primarySuccessor) ?
201                 primaryState : secondaryState;
202 
203             if (resultInfo.mergeStarts(succ, state)) {
204                 workSet.set(succ);
205             }
206         }
207     }
208 }
209