LocalVariableExtractor.java revision 579d7739c53a2707ad711a2d2cae46d7d782f061 
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.rop.code;
18
19import com.android.dx.util.Bits;
20import 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 */
26public 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     */
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     */
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     */
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     */
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