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.back;
18
19import com.android.dx.rop.code.BasicBlock;
20import com.android.dx.rop.code.BasicBlockList;
21import com.android.dx.rop.code.InsnList;
22import com.android.dx.rop.code.RegisterSpec;
23import com.android.dx.rop.code.RegisterSpecList;
24import com.android.dx.rop.code.Rop;
25import com.android.dx.rop.code.RopMethod;
26import com.android.dx.rop.code.Rops;
27import com.android.dx.ssa.BasicRegisterMapper;
28import com.android.dx.ssa.PhiInsn;
29import com.android.dx.ssa.RegisterMapper;
30import com.android.dx.ssa.SsaBasicBlock;
31import com.android.dx.ssa.SsaInsn;
32import com.android.dx.ssa.SsaMethod;
33import com.android.dx.util.Hex;
34import com.android.dx.util.IntList;
35import java.util.ArrayList;
36import java.util.Arrays;
37import java.util.BitSet;
38import java.util.Comparator;
39
40/**
41 * Converts a method in SSA form to ROP form.
42 */
43public class SsaToRop {
44    /** local debug flag */
45    private static final boolean DEBUG = false;
46
47    /** {@code non-null;} method to process */
48    private final SsaMethod ssaMeth;
49
50    /**
51     * {@code true} if the converter should attempt to minimize
52     * the rop-form register count
53     */
54    private final boolean minimizeRegisters;
55
56    /** {@code non-null;} interference graph */
57    private final InterferenceGraph interference;
58
59    /**
60     * Converts a method in SSA form to ROP form.
61     *
62     * @param ssaMeth {@code non-null;} method to process
63     * @param minimizeRegisters {@code true} if the converter should
64     * attempt to minimize the rop-form register count
65     * @return {@code non-null;} rop-form output
66     */
67    public static RopMethod convertToRopMethod(SsaMethod ssaMeth,
68            boolean minimizeRegisters) {
69        return new SsaToRop(ssaMeth, minimizeRegisters).convert();
70    }
71
72    /**
73     * Constructs an instance.
74     *
75     * @param ssaMethod {@code non-null;} method to process
76     * @param minimizeRegisters {@code true} if the converter should
77     * attempt to minimize the rop-form register count
78     */
79    private SsaToRop(SsaMethod ssaMethod, boolean minimizeRegisters) {
80        this.minimizeRegisters = minimizeRegisters;
81        this.ssaMeth = ssaMethod;
82        this.interference =
83            LivenessAnalyzer.constructInterferenceGraph(ssaMethod);
84    }
85
86    /**
87     * Performs the conversion.
88     *
89     * @return {@code non-null;} rop-form output
90     */
91    private RopMethod convert() {
92        if (DEBUG) {
93            interference.dumpToStdout();
94        }
95
96        // These are other allocators for debugging or historical comparison:
97        // allocator = new NullRegisterAllocator(ssaMeth, interference);
98        // allocator = new FirstFitAllocator(ssaMeth, interference);
99
100        RegisterAllocator allocator =
101            new FirstFitLocalCombiningAllocator(ssaMeth, interference,
102                    minimizeRegisters);
103
104        RegisterMapper mapper = allocator.allocateRegisters();
105
106        if (DEBUG) {
107            System.out.println("Printing reg map");
108            System.out.println(((BasicRegisterMapper)mapper).toHuman());
109        }
110
111        ssaMeth.setBackMode();
112
113        ssaMeth.mapRegisters(mapper);
114
115        removePhiFunctions();
116
117        if (allocator.wantsParamsMovedHigh()) {
118            moveParametersToHighRegisters();
119        }
120
121        removeEmptyGotos();
122
123        RopMethod ropMethod = new RopMethod(convertBasicBlocks(),
124                ssaMeth.blockIndexToRopLabel(ssaMeth.getEntryBlockIndex()));
125        ropMethod = new IdenticalBlockCombiner(ropMethod).process();
126
127        return ropMethod;
128    }
129
130    /**
131     * Removes all blocks containing only GOTOs from the control flow.
132     * Although much of this work will be done later when converting
133     * from rop to dex, not all simplification cases can be handled
134     * there. Furthermore, any no-op block between the exit block and
135     * blocks containing the real return or throw statements must be
136     * removed.
137     */
138    private void removeEmptyGotos() {
139        final ArrayList<SsaBasicBlock> blocks = ssaMeth.getBlocks();
140
141        ssaMeth.forEachBlockDepthFirst(false, new SsaBasicBlock.Visitor() {
142            @Override
143            public void visitBlock(SsaBasicBlock b, SsaBasicBlock parent) {
144                ArrayList<SsaInsn> insns = b.getInsns();
145
146                if ((insns.size() == 1)
147                        && (insns.get(0).getOpcode() == Rops.GOTO)) {
148                    BitSet preds = (BitSet) b.getPredecessors().clone();
149
150                    for (int i = preds.nextSetBit(0); i >= 0;
151                            i = preds.nextSetBit(i + 1)) {
152                        SsaBasicBlock pb = blocks.get(i);
153                        pb.replaceSuccessor(b.getIndex(),
154                                b.getPrimarySuccessorIndex());
155                    }
156                }
157            }
158        });
159    }
160
161    /**
162     * See Appel 19.6. To remove the phi instructions in an edge-split
163     * SSA representation we know we can always insert a move in a
164     * predecessor block.
165     */
166    private void removePhiFunctions() {
167        ArrayList<SsaBasicBlock> blocks = ssaMeth.getBlocks();
168
169        for (SsaBasicBlock block : blocks) {
170            // Add moves in all the pred blocks for each phi insn.
171            block.forEachPhiInsn(new PhiVisitor(blocks));
172
173            // Delete the phi insns.
174            block.removeAllPhiInsns();
175        }
176
177        /*
178         * After all move insns have been added, sort them so they don't
179         * destructively interfere.
180         */
181        for (SsaBasicBlock block : blocks) {
182            block.scheduleMovesFromPhis();
183        }
184    }
185
186    /**
187     * Helper for {@link #removePhiFunctions}: PhiSuccessorUpdater for
188     * adding move instructions to predecessors based on phi insns.
189     */
190    private static class PhiVisitor implements PhiInsn.Visitor {
191        private final ArrayList<SsaBasicBlock> blocks;
192
193        public PhiVisitor(ArrayList<SsaBasicBlock> blocks) {
194            this.blocks = blocks;
195        }
196
197        @Override
198        public void visitPhiInsn(PhiInsn insn) {
199            RegisterSpecList sources = insn.getSources();
200            RegisterSpec result = insn.getResult();
201            int sz = sources.size();
202
203            for (int i = 0; i < sz; i++) {
204                RegisterSpec source = sources.get(i);
205                SsaBasicBlock predBlock = blocks.get(
206                        insn.predBlockIndexForSourcesIndex(i));
207
208                predBlock.addMoveToEnd(result, source);
209            }
210        }
211    }
212
213    /**
214     * Moves the parameter registers, which allocateRegisters() places
215     * at the bottom of the frame, up to the top of the frame to match
216     * Dalvik calling convention.
217     */
218    private void moveParametersToHighRegisters() {
219        int paramWidth = ssaMeth.getParamWidth();
220        BasicRegisterMapper mapper
221                = new BasicRegisterMapper(ssaMeth.getRegCount());
222        int regCount = ssaMeth.getRegCount();
223
224        for (int i = 0; i < regCount; i++) {
225            if (i < paramWidth) {
226                mapper.addMapping(i, regCount - paramWidth + i, 1);
227            } else {
228                mapper.addMapping(i, i - paramWidth, 1);
229            }
230        }
231
232        if (DEBUG) {
233            System.out.printf("Moving %d registers from 0 to %d\n",
234                    paramWidth, regCount - paramWidth);
235        }
236
237        ssaMeth.mapRegisters(mapper);
238    }
239
240    /**
241     * @return rop-form basic block list
242     */
243    private BasicBlockList convertBasicBlocks() {
244        ArrayList<SsaBasicBlock> blocks = ssaMeth.getBlocks();
245
246        // Exit block may be null.
247        SsaBasicBlock exitBlock = ssaMeth.getExitBlock();
248
249        BitSet reachable = ssaMeth.computeReachability();
250        int ropBlockCount = reachable.cardinality();
251
252        // Don't count the exit block, if it exists and is reachable.
253        if (exitBlock != null && reachable.get(exitBlock.getIndex())) {
254            ropBlockCount -= 1;
255        }
256
257        BasicBlockList result = new BasicBlockList(ropBlockCount);
258
259        // Convert all the reachable blocks except the exit block.
260        int ropBlockIndex = 0;
261        for (SsaBasicBlock b : blocks) {
262            if (reachable.get(b.getIndex()) && b != exitBlock) {
263                result.set(ropBlockIndex++, convertBasicBlock(b));
264            }
265        }
266
267        // The exit block, which is discarded, must do nothing.
268        if (exitBlock != null && !exitBlock.getInsns().isEmpty()) {
269            throw new RuntimeException(
270                    "Exit block must have no insns when leaving SSA form");
271        }
272
273        return result;
274    }
275
276    /**
277     * Validates that a basic block is a valid end predecessor. It must
278     * end in a RETURN or a THROW. Throws a runtime exception on error.
279     *
280     * @param b {@code non-null;} block to validate
281     * @throws RuntimeException on error
282     */
283    private void verifyValidExitPredecessor(SsaBasicBlock b) {
284        ArrayList<SsaInsn> insns = b.getInsns();
285        SsaInsn lastInsn = insns.get(insns.size() - 1);
286        Rop opcode = lastInsn.getOpcode();
287
288        if (opcode.getBranchingness() != Rop.BRANCH_RETURN
289                && opcode != Rops.THROW) {
290            throw new RuntimeException("Exit predecessor must end"
291                    + " in valid exit statement.");
292        }
293    }
294
295    /**
296     * Converts a single basic block to rop form.
297     *
298     * @param block SSA block to process
299     * @return {@code non-null;} ROP block
300     */
301    private BasicBlock convertBasicBlock(SsaBasicBlock block) {
302        IntList successorList = block.getRopLabelSuccessorList();
303        int primarySuccessorLabel = block.getPrimarySuccessorRopLabel();
304
305        // Filter out any reference to the SSA form's exit block.
306
307        // Exit block may be null.
308        SsaBasicBlock exitBlock = ssaMeth.getExitBlock();
309        int exitRopLabel = (exitBlock == null) ? -1 : exitBlock.getRopLabel();
310
311        if (successorList.contains(exitRopLabel)) {
312            if (successorList.size() > 1) {
313                throw new RuntimeException(
314                        "Exit predecessor must have no other successors"
315                                + Hex.u2(block.getRopLabel()));
316            } else {
317                successorList = IntList.EMPTY;
318                primarySuccessorLabel = -1;
319
320                verifyValidExitPredecessor(block);
321            }
322        }
323
324        successorList.setImmutable();
325
326        BasicBlock result = new BasicBlock(
327                block.getRopLabel(), convertInsns(block.getInsns()),
328                successorList,
329                primarySuccessorLabel);
330
331        return result;
332    }
333
334    /**
335     * Converts an insn list to rop form.
336     *
337     * @param ssaInsns {@code non-null;} old instructions
338     * @return {@code non-null;} immutable instruction list
339     */
340    private InsnList convertInsns(ArrayList<SsaInsn> ssaInsns) {
341        int insnCount = ssaInsns.size();
342        InsnList result = new InsnList(insnCount);
343
344        for (int i = 0; i < insnCount; i++) {
345            result.set(i, ssaInsns.get(i).toRopInsn());
346        }
347
348        result.setImmutable();
349
350        return result;
351    }
352
353    /**
354     * <b>Note:</b> This method is not presently used.
355     *
356     * @return a list of registers ordered by most-frequently-used to
357     * least-frequently-used. Each register is listed once and only
358     * once.
359     */
360    public int[] getRegistersByFrequency() {
361        int regCount = ssaMeth.getRegCount();
362        Integer[] ret = new Integer[regCount];
363
364        for (int i = 0; i < regCount; i++) {
365            ret[i] = i;
366        }
367
368        Arrays.sort(ret, new Comparator<Integer>() {
369            @Override
370            public int compare(Integer o1, Integer o2) {
371                return ssaMeth.getUseListForRegister(o2).size()
372                        - ssaMeth.getUseListForRegister(o1).size();
373            }
374        });
375
376        int result[] = new int[regCount];
377
378        for (int i = 0; i < regCount; i++) {
379            result[i] = ret[i];
380        }
381
382        return result;
383    }
384}
385