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.LocalItem;
20import com.android.dx.rop.code.PlainInsn;
21import com.android.dx.rop.code.RegisterSpec;
22import com.android.dx.rop.code.RegisterSpecList;
23import com.android.dx.rop.code.Rops;
24import com.android.dx.rop.code.SourcePosition;
25import com.android.dx.rop.type.Type;
26import com.android.dx.util.IntList;
27
28import java.util.ArrayList;
29import java.util.BitSet;
30import java.util.HashMap;
31import java.util.HashSet;
32
33/**
34 * Complete transformation to SSA form by renaming all registers accessed.<p>
35 *
36 * See Appel algorithm 19.7<p>
37 *
38 * Unlike the original algorithm presented in Appel, this renamer converts
39 * to a new flat (versionless) register space. The "version 0" registers,
40 * which represent the initial state of the Rop registers and should never
41 * actually be meaningfully accessed in a legal program, are represented
42 * as the first N registers in the SSA namespace. Subsequent assignments
43 * are assigned new unique names. Note that the incoming Rop representation
44 * has a concept of register widths, where 64-bit values are stored into
45 * two adjoining Rop registers. This adjoining register representation is
46 * ignored in SSA form conversion and while in SSA form, each register can be e
47 * either 32 or 64 bits wide depending on use. The adjoining-register
48 * represention is re-created later when converting back to Rop form. <p>
49 *
50 * But, please note, the SSA Renamer's ignoring of the adjoining-register ROP
51 * representation means that unaligned accesses to 64-bit registers are not
52 * supported. For example, you cannot do a 32-bit operation on a portion of
53 * a 64-bit register. This will never be observed to happen when coming
54 * from Java code, of course.<p>
55 *
56 * The implementation here, rather than keeping a single register version
57 * stack for the entire method as the dom tree is walked, instead keeps
58 * a mapping table for the current block being processed. Once the
59 * current block has been processed, this mapping table is then copied
60 * and used as the initial state for child blocks.<p>
61 */
62public class SsaRenamer implements Runnable {
63    /** debug flag */
64    private static final boolean DEBUG = false;
65
66    /** method we're processing */
67    private final SsaMethod ssaMeth;
68
69    /** next available SSA register */
70    private int nextSsaReg;
71
72    /** the number of original rop registers */
73    private final int ropRegCount;
74
75    /** work only on registers above this value */
76    private int threshold;
77
78    /**
79     * indexed by block index; register version state for each block start.
80     * This list is updated by each dom parent for its children. The only
81     * sub-arrays that exist at any one time are the start states for blocks
82     * yet to be processed by a {@code BlockRenamer} instance.
83     */
84    private final RegisterSpec[][] startsForBlocks;
85
86    /** map of SSA register number to debug (local var names) or null of n/a */
87    private final ArrayList<LocalItem> ssaRegToLocalItems;
88
89    /**
90     * maps SSA registers back to the original rop number. Used for
91     * debug only.
92     */
93    private IntList ssaRegToRopReg;
94
95    /**
96     * Constructs an instance of the renamer
97     *
98     * @param ssaMeth {@code non-null;} un-renamed SSA method that will
99     * be renamed.
100     */
101    public SsaRenamer(SsaMethod ssaMeth) {
102        ropRegCount = ssaMeth.getRegCount();
103
104        this.ssaMeth = ssaMeth;
105
106        /*
107         * Reserve the first N registers in the SSA register space for
108         * "version 0" registers.
109         */
110        nextSsaReg = ropRegCount;
111        threshold = 0;
112        startsForBlocks = new RegisterSpec[ssaMeth.getBlocks().size()][];
113
114        ssaRegToLocalItems = new ArrayList<LocalItem>();
115
116        if (DEBUG) {
117            ssaRegToRopReg = new IntList(ropRegCount);
118        }
119
120        /*
121         * Appel 19.7
122         *
123         * Initialization:
124         *   for each variable a        // register i
125         *      Count[a] <- 0           // nextSsaReg, flattened
126         *      Stack[a] <- 0           // versionStack
127         *      push 0 onto Stack[a]
128         *
129         */
130
131        // top entry for the version stack is version 0
132        RegisterSpec[] initialRegMapping = new RegisterSpec[ropRegCount];
133        for (int i = 0; i < ropRegCount; i++) {
134            // everyone starts with a version 0 register
135            initialRegMapping[i] = RegisterSpec.make(i, Type.VOID);
136
137            if (DEBUG) {
138                ssaRegToRopReg.add(i);
139            }
140        }
141
142        // Initial state for entry block
143        startsForBlocks[ssaMeth.getEntryBlockIndex()] = initialRegMapping;
144    }
145
146    /**
147    * Constructs an instance of the renamer with threshold set
148    *
149    * @param ssaMeth {@code non-null;} un-renamed SSA method that will
150    * be renamed.
151    * @param thresh registers below this number are unchanged
152    */
153   public SsaRenamer(SsaMethod ssaMeth, int thresh) {
154       this(ssaMeth);
155       threshold = thresh;
156   }
157
158    /**
159     * Performs renaming transformation, modifying the method's instructions
160     * in-place.
161     */
162    public void run() {
163        // Rename each block in dom-tree DFS order.
164        ssaMeth.forEachBlockDepthFirstDom(new SsaBasicBlock.Visitor() {
165            public void visitBlock (SsaBasicBlock block,
166                    SsaBasicBlock unused) {
167                new BlockRenamer(block).process();
168            }
169        });
170
171        ssaMeth.setNewRegCount(nextSsaReg);
172        ssaMeth.onInsnsChanged();
173
174        if (DEBUG) {
175            System.out.println("SSA\tRop");
176            /*
177             * We're going to compute the version of the rop register
178             * by keeping a running total of how many times the rop
179             * register has been mapped.
180             */
181            int[] versions = new int[ropRegCount];
182
183            int sz = ssaRegToRopReg.size();
184            for (int i = 0; i < sz; i++) {
185                int ropReg = ssaRegToRopReg.get(i);
186                System.out.println(i + "\t" + ropReg + "["
187                        + versions[ropReg] + "]");
188                versions[ropReg]++;
189            }
190        }
191    }
192
193    /**
194     * Duplicates a RegisterSpec array.
195     *
196     * @param orig {@code non-null;} array to duplicate
197     * @return {@code non-null;} new instance
198     */
199    private static  RegisterSpec[] dupArray(RegisterSpec[] orig) {
200        RegisterSpec[] copy = new RegisterSpec[orig.length];
201
202        System.arraycopy(orig, 0, copy, 0, orig.length);
203
204        return copy;
205    }
206
207    /**
208     * Gets a local variable item for a specified register.
209     *
210     * @param ssaReg register in SSA name space
211     * @return {@code null-ok;} Local variable name or null if none
212     */
213    private LocalItem getLocalForNewReg(int ssaReg) {
214        if (ssaReg < ssaRegToLocalItems.size()) {
215            return ssaRegToLocalItems.get(ssaReg);
216        } else {
217            return null;
218        }
219    }
220
221    /**
222     * Records a debug (local variable) name for a specified register.
223     *
224     * @param ssaReg non-null named register spec in SSA name space
225     */
226    private void setNameForSsaReg(RegisterSpec ssaReg) {
227        int reg = ssaReg.getReg();
228        LocalItem local = ssaReg.getLocalItem();
229
230        ssaRegToLocalItems.ensureCapacity(reg + 1);
231        while (ssaRegToLocalItems.size() <= reg) {
232            ssaRegToLocalItems.add(null);
233        }
234
235        ssaRegToLocalItems.set(reg, local);
236    }
237
238    /**
239     * Returns true if this SSA register is below the specified threshold.
240     * Used when most code is already in SSA form, and renaming is needed only
241     * for registers above a certain threshold.
242     *
243     * @param ssaReg the SSA register in question
244     * @return {@code true} if its register number is below the threshold
245     */
246    private boolean isBelowThresholdRegister(int ssaReg) {
247        return ssaReg < threshold;
248    }
249
250    /**
251     * Returns true if this SSA register is a "version 0"
252     * register. All version 0 registers are assigned the first N register
253     * numbers, where N is the count of original rop registers.
254     *
255     * @param ssaReg the SSA register in question
256     * @return true if it is a version 0 register.
257     */
258    private boolean isVersionZeroRegister(int ssaReg) {
259        return ssaReg < ropRegCount;
260    }
261
262    /**
263     * Returns true if a and b are equal or are both null.
264     *
265     * @param a null-ok
266     * @param b null-ok
267     * @return Returns true if a and b are equal or are both null
268     */
269    private static boolean equalsHandlesNulls(Object a, Object b) {
270        return a == b ||  (a != null && a.equals(b));
271    }
272
273    /**
274     * Processes all insns in a block and renames their registers
275     * as appropriate.
276     */
277    private class BlockRenamer implements SsaInsn.Visitor{
278        /** {@code non-null;} block we're processing. */
279        private final SsaBasicBlock block;
280
281        /**
282         * {@code non-null;} indexed by old register name. The current
283         * top of the version stack as seen by this block. It's
284         * initialized from the ending state of its dom parent,
285         * updated as the block's instructions are processed, and then
286         * copied to each one of its dom children.
287         */
288        private final RegisterSpec[] currentMapping;
289
290        /**
291         * contains the set of moves we need to keep to preserve local
292         * var info. All other moves will be deleted.
293         */
294        private final HashSet<SsaInsn> movesToKeep;
295
296        /**
297         * maps the set of insns to replace after renaming is finished
298         * on the block.
299         */
300        private final HashMap<SsaInsn, SsaInsn> insnsToReplace;
301
302        private final RenamingMapper mapper;
303
304        /**
305         * Constructs a block renamer instance. Call {@code process}
306         * to process.
307         *
308         * @param block {@code non-null;} block to process
309         */
310        BlockRenamer(final SsaBasicBlock block) {
311            this.block = block;
312            currentMapping = startsForBlocks[block.getIndex()];
313            movesToKeep = new HashSet<SsaInsn>();
314            insnsToReplace = new HashMap<SsaInsn, SsaInsn>();
315            mapper =  new RenamingMapper();
316
317            // We don't need our own start state anymore
318            startsForBlocks[block.getIndex()] = null;
319        }
320
321        /**
322         * Provides a register mapping between the old register space
323         * and the current renaming mapping. The mapping is updated
324         * as the current block's instructions are processed.
325         */
326        private class RenamingMapper extends RegisterMapper {
327            public RenamingMapper() {
328                // This space intentionally left blank.
329            }
330
331            /** {@inheritDoc} */
332            @Override
333            public int getNewRegisterCount() {
334                return nextSsaReg;
335            }
336
337            /** {@inheritDoc} */
338            @Override
339            public RegisterSpec map(RegisterSpec registerSpec) {
340                if (registerSpec == null) return null;
341
342                int reg = registerSpec.getReg();
343
344                // For debugging: assert that the mapped types are compatible.
345                if (DEBUG) {
346                    RegisterSpec newVersion = currentMapping[reg];
347                    if (newVersion.getBasicType() != Type.BT_VOID
348                            && registerSpec.getBasicFrameType()
349                                != newVersion.getBasicFrameType()) {
350
351                        throw new RuntimeException(
352                                "mapping registers of incompatible types! "
353                                + registerSpec
354                                + " " + currentMapping[reg]);
355                    }
356                }
357
358                return registerSpec.withReg(currentMapping[reg].getReg());
359            }
360        }
361
362        /**
363         * Renames all the variables in this block and inserts appriopriate
364         * phis in successor blocks.
365         */
366        public void process() {
367            /*
368             * From Appel:
369             *
370             * Rename(n) =
371             *   for each statement S in block n   // 'statement' in 'block'
372             */
373
374            block.forEachInsn(this);
375
376            updateSuccessorPhis();
377
378            // Delete all move insns in this block.
379            ArrayList<SsaInsn> insns = block.getInsns();
380            int szInsns = insns.size();
381
382            for (int i = szInsns - 1; i >= 0 ; i--) {
383                SsaInsn insn = insns.get(i);
384                SsaInsn replaceInsn;
385
386                replaceInsn = insnsToReplace.get(insn);
387
388                if (replaceInsn != null) {
389                    insns.set(i, replaceInsn);
390                } else if (insn.isNormalMoveInsn()
391                        && !movesToKeep.contains(insn)) {
392                    insns.remove(i);
393                }
394            }
395
396            // Store the start states for our dom children.
397            boolean first = true;
398            for (SsaBasicBlock child : block.getDomChildren()) {
399                if (child != block) {
400                    // Don't bother duplicating the array for the first child.
401                    RegisterSpec[] childStart = first ? currentMapping
402                        : dupArray(currentMapping);
403
404                    startsForBlocks[child.getIndex()] = childStart;
405                    first = false;
406                }
407            }
408
409            // currentMapping is owned by a child now.
410        }
411
412        /**
413         * Enforces a few contraints when a register mapping is added.
414         *
415         * <ol>
416         * <li> Ensures that all new SSA registers specs in the mapping
417         * table with the same register number are identical. In effect, once
418         * an SSA register spec has received or lost a local variable name,
419         * then every old-namespace register that maps to it should gain or
420         * lose its local variable name as well.
421         * <li> Records the local name associated with the
422         * register so that a register is never associated with more than one
423         * local.
424         * <li> ensures that only one SSA register
425         * at a time is considered to be associated with a local variable. When
426         * {@code currentMapping} is updated and the newly added element
427         * is named, strip that name from any other SSA registers.
428         * </ol>
429         *
430         * @param ropReg {@code >= 0;} rop register number
431         * @param ssaReg {@code non-null;} an SSA register that has just
432         * been added to {@code currentMapping}
433         */
434        private void addMapping(int ropReg, RegisterSpec ssaReg) {
435            int ssaRegNum = ssaReg.getReg();
436            LocalItem ssaRegLocal = ssaReg.getLocalItem();
437
438            currentMapping[ropReg] = ssaReg;
439
440            /*
441             * Ensure all SSA register specs with the same reg are identical.
442             */
443            for (int i = currentMapping.length - 1; i >= 0; i--) {
444                RegisterSpec cur = currentMapping[i];
445
446                if (ssaRegNum == cur.getReg()) {
447                    currentMapping[i] = ssaReg;
448                }
449            }
450
451            // All further steps are for registers with local information.
452            if (ssaRegLocal == null) {
453                return;
454            }
455
456            // Record that this SSA reg has been associated with a local.
457            setNameForSsaReg(ssaReg);
458
459            // Ensure that no other SSA regs are associated with this local.
460            for (int i = currentMapping.length - 1; i >= 0; i--) {
461                RegisterSpec cur = currentMapping[i];
462
463                if (ssaRegNum != cur.getReg()
464                        && ssaRegLocal.equals(cur.getLocalItem())) {
465                    currentMapping[i] = cur.withLocalItem(null);
466                }
467            }
468        }
469
470        /**
471         * {@inheritDoc}
472         *
473         * Phi insns have their result registers renamed.
474         */
475        public void visitPhiInsn(PhiInsn phi) {
476            /* don't process sources for phi's */
477            processResultReg(phi);
478        }
479
480        /**
481         * {@inheritDoc}
482         *
483         * Move insns are treated as a simple mapping operation, and
484         * will later be removed unless they represent a local variable
485         * assignment. If they represent a local variable assignement, they
486         * are preserved.
487         */
488        public void visitMoveInsn(NormalSsaInsn insn) {
489            /*
490             * For moves: copy propogate the move if we can, but don't
491             * if we need to preserve local variable info and the
492             * result has a different name than the source.
493             */
494
495            RegisterSpec ropResult = insn.getResult();
496            int ropResultReg = ropResult.getReg();
497            int ropSourceReg = insn.getSources().get(0).getReg();
498
499            insn.mapSourceRegisters(mapper);
500            int ssaSourceReg = insn.getSources().get(0).getReg();
501
502            LocalItem sourceLocal
503                = currentMapping[ropSourceReg].getLocalItem();
504            LocalItem resultLocal = ropResult.getLocalItem();
505
506            /*
507             * A move from a register that's currently associated with a local
508             * to one that will not be associated with a local does not need
509             * to be preserved, but the local association should remain.
510             * Hence, we inherit the sourceLocal where the resultLocal is null.
511             */
512
513            LocalItem newLocal
514                = (resultLocal == null) ? sourceLocal : resultLocal;
515            LocalItem associatedLocal = getLocalForNewReg(ssaSourceReg);
516
517            /*
518             * If we take the new local, will only one local have ever
519             * been associated with this SSA reg?
520             */
521            boolean onlyOneAssociatedLocal
522                    = associatedLocal == null || newLocal == null
523                    || newLocal.equals(associatedLocal);
524
525            /*
526             * If we're going to copy-propogate, then the ssa register
527             * spec that's going to go into the mapping is made up of
528             * the source register number mapped from above, the type
529             * of the result, and the name either from the result (if
530             * specified) or inherited from the existing mapping.
531             *
532             * The move source has incomplete type information in null
533             * object cases, so the result type is used.
534             */
535            RegisterSpec ssaReg
536                    = RegisterSpec.makeLocalOptional(
537                        ssaSourceReg, ropResult.getType(), newLocal);
538
539            if (!Optimizer.getPreserveLocals() || (onlyOneAssociatedLocal
540                    && equalsHandlesNulls(newLocal, sourceLocal)) &&
541                    threshold == 0) {
542                /*
543                 * We don't have to keep this move to preserve local
544                 * information. Either the name is the same, or the result
545                 * register spec is unnamed.
546                 */
547
548                addMapping(ropResultReg, ssaReg);
549            } else if (onlyOneAssociatedLocal && sourceLocal == null &&
550                    threshold == 0) {
551                /*
552                 * The register was previously unnamed. This means that a
553                 * local starts after it's first assignment in SSA form
554                 */
555
556                RegisterSpecList ssaSources = RegisterSpecList.make(
557                        RegisterSpec.make(ssaReg.getReg(),
558                                ssaReg.getType(), newLocal));
559
560                SsaInsn newInsn
561                        = SsaInsn.makeFromRop(
562                            new PlainInsn(Rops.opMarkLocal(ssaReg),
563                            SourcePosition.NO_INFO, null, ssaSources),block);
564
565                insnsToReplace.put(insn, newInsn);
566
567                // Just map as above.
568                addMapping(ropResultReg, ssaReg);
569            } else {
570                /*
571                 * Do not copy-propogate, since the two registers have
572                 * two different local-variable names.
573                 */
574                processResultReg(insn);
575
576                movesToKeep.add(insn);
577            }
578        }
579
580        /**
581         * {@inheritDoc}
582         *
583         * All insns that are not move or phi insns have their source registers
584         * mapped ot the current mapping. Their result registers are then
585         * renamed to a new SSA register which is then added to the current
586         * register mapping.
587         */
588        public void visitNonMoveInsn(NormalSsaInsn insn) {
589            /* for each use of some variable X in S */
590            insn.mapSourceRegisters(mapper);
591
592            processResultReg(insn);
593        }
594
595        /**
596         * Renames the result register of this insn and updates the
597         * current register mapping. Does nothing if this insn has no result.
598         * Applied to all non-move insns.
599         *
600         * @param insn insn to process.
601         */
602        void processResultReg(SsaInsn insn) {
603            RegisterSpec ropResult = insn.getResult();
604
605            if (ropResult == null) {
606                return;
607            }
608
609            int ropReg = ropResult.getReg();
610            if (isBelowThresholdRegister(ropReg)) {
611                return;
612            }
613
614            insn.changeResultReg(nextSsaReg);
615            addMapping(ropReg, insn.getResult());
616
617            if (DEBUG) {
618                ssaRegToRopReg.add(ropReg);
619            }
620
621            nextSsaReg++;
622        }
623
624        /**
625         * Updates the phi insns in successor blocks with operands based
626         * on the current mapping of the rop register the phis represent.
627         */
628        private void updateSuccessorPhis() {
629            PhiInsn.Visitor visitor = new PhiInsn.Visitor() {
630                public void visitPhiInsn (PhiInsn insn) {
631                    int ropReg;
632
633                    ropReg = insn.getRopResultReg();
634                    if (isBelowThresholdRegister(ropReg)) {
635                        return;
636                    }
637
638                    /*
639                     * Never add a version 0 register as a phi
640                     * operand. Version 0 registers represent the
641                     * initial register state, and thus are never
642                     * significant. Furthermore, the register liveness
643                     * algorithm doesn't properly count them as "live
644                     * in" at the beginning of the method.
645                     */
646
647                    RegisterSpec stackTop = currentMapping[ropReg];
648                    if (!isVersionZeroRegister(stackTop.getReg())) {
649                        insn.addPhiOperand(stackTop, block);
650                    }
651                }
652            };
653
654            BitSet successors = block.getSuccessors();
655            for (int i = successors.nextSetBit(0); i >= 0;
656                    i = successors.nextSetBit(i + 1)) {
657                SsaBasicBlock successor = ssaMeth.getBlocks().get(i);
658                successor.forEachPhiInsn(visitor);
659            }
660        }
661    }
662}
663