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