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