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.ssa;
18
19import com.android.dx.rop.code.RegisterSpecSet;
20import com.android.dx.rop.code.RegisterSpec;
21import com.android.dx.util.IntList;
22
23import java.util.ArrayList;
24import java.util.BitSet;
25import 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 */
35public 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     */
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     */
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     */
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     */
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