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.dex.code;
18
19import com.android.dx.dex.DexOptions;
20import com.android.dx.io.Opcodes;
21import com.android.dx.rop.code.LocalItem;
22import com.android.dx.rop.code.RegisterSpec;
23import com.android.dx.rop.code.RegisterSpecList;
24import com.android.dx.rop.code.RegisterSpecSet;
25import com.android.dx.rop.code.SourcePosition;
26import com.android.dx.rop.cst.Constant;
27import com.android.dx.rop.cst.CstMemberRef;
28import com.android.dx.rop.cst.CstType;
29import com.android.dx.rop.cst.CstString;
30import com.android.dx.rop.type.Type;
31
32import com.android.dx.util.DexException;
33import java.util.ArrayList;
34import java.util.BitSet;
35import java.util.HashSet;
36
37/**
38 * Processor for instruction lists, which takes a "first cut" of
39 * instruction selection as a basis and produces a "final cut" in the
40 * form of a {@link DalvInsnList} instance.
41 */
42public final class OutputFinisher {
43    /** {@code non-null;} options for dex output */
44    private final DexOptions dexOptions;
45
46    /**
47     * {@code >= 0;} register count for the method, not including any extra
48     * "reserved" registers needed to translate "difficult" instructions
49     */
50    private final int unreservedRegCount;
51
52    /** {@code non-null;} the list of instructions, per se */
53    private ArrayList<DalvInsn> insns;
54
55    /** whether any instruction has position info */
56    private boolean hasAnyPositionInfo;
57
58    /** whether any instruction has local variable info */
59    private boolean hasAnyLocalInfo;
60
61    /**
62     * {@code >= 0;} the count of reserved registers (low-numbered
63     * registers used when expanding instructions that can't be
64     * represented simply); becomes valid after a call to {@link
65     * #massageInstructions}
66     */
67    private int reservedCount;
68
69    /**
70     * Constructs an instance. It initially contains no instructions.
71     *
72     * @param dexOptions {@code non-null;} options for dex output
73     * @param regCount {@code >= 0;} register count for the method
74     * @param initialCapacity {@code >= 0;} initial capacity of the
75     * instructions list
76     */
77    public OutputFinisher(DexOptions dexOptions, int initialCapacity, int regCount) {
78        this.dexOptions = dexOptions;
79        this.unreservedRegCount = regCount;
80        this.insns = new ArrayList<DalvInsn>(initialCapacity);
81        this.reservedCount = -1;
82        this.hasAnyPositionInfo = false;
83        this.hasAnyLocalInfo = false;
84    }
85
86    /**
87     * Returns whether any of the instructions added to this instance
88     * come with position info.
89     *
90     * @return whether any of the instructions added to this instance
91     * come with position info
92     */
93    public boolean hasAnyPositionInfo() {
94        return hasAnyPositionInfo;
95    }
96
97    /**
98     * Returns whether this instance has any local variable information.
99     *
100     * @return whether this instance has any local variable information
101     */
102    public boolean hasAnyLocalInfo() {
103        return hasAnyLocalInfo;
104    }
105
106    /**
107     * Helper for {@link #add} which scrutinizes a single
108     * instruction for local variable information.
109     *
110     * @param insn {@code non-null;} instruction to scrutinize
111     * @return {@code true} iff the instruction refers to any
112     * named locals
113     */
114    private static boolean hasLocalInfo(DalvInsn insn) {
115        if (insn instanceof LocalSnapshot) {
116            RegisterSpecSet specs = ((LocalSnapshot) insn).getLocals();
117            int size = specs.size();
118            for (int i = 0; i < size; i++) {
119                if (hasLocalInfo(specs.get(i))) {
120                    return true;
121                }
122            }
123        } else if (insn instanceof LocalStart) {
124            RegisterSpec spec = ((LocalStart) insn).getLocal();
125            if (hasLocalInfo(spec)) {
126                return true;
127            }
128        }
129
130        return false;
131    }
132
133    /**
134     * Helper for {@link #hasAnyLocalInfo} which scrutinizes a single
135     * register spec.
136     *
137     * @param spec {@code non-null;} spec to scrutinize
138     * @return {@code true} iff the spec refers to any
139     * named locals
140     */
141    private static boolean hasLocalInfo(RegisterSpec spec) {
142        return (spec != null)
143            && (spec.getLocalItem().getName() != null);
144    }
145
146    /**
147     * Returns the set of all constants referred to by instructions added
148     * to this instance.
149     *
150     * @return {@code non-null;} the set of constants
151     */
152    public HashSet<Constant> getAllConstants() {
153        HashSet<Constant> result = new HashSet<Constant>(20);
154
155        for (DalvInsn insn : insns) {
156            addConstants(result, insn);
157        }
158
159        return result;
160    }
161
162    /**
163     * Helper for {@link #getAllConstants} which adds all the info for
164     * a single instruction.
165     *
166     * @param result {@code non-null;} result set to add to
167     * @param insn {@code non-null;} instruction to scrutinize
168     */
169    private static void addConstants(HashSet<Constant> result,
170            DalvInsn insn) {
171        if (insn instanceof CstInsn) {
172            Constant cst = ((CstInsn) insn).getConstant();
173            result.add(cst);
174        } else if (insn instanceof LocalSnapshot) {
175            RegisterSpecSet specs = ((LocalSnapshot) insn).getLocals();
176            int size = specs.size();
177            for (int i = 0; i < size; i++) {
178                addConstants(result, specs.get(i));
179            }
180        } else if (insn instanceof LocalStart) {
181            RegisterSpec spec = ((LocalStart) insn).getLocal();
182            addConstants(result, spec);
183        }
184    }
185
186    /**
187     * Helper for {@link #getAllConstants} which adds all the info for
188     * a single {@code RegisterSpec}.
189     *
190     * @param result {@code non-null;} result set to add to
191     * @param spec {@code null-ok;} register spec to add
192     */
193    private static void addConstants(HashSet<Constant> result,
194            RegisterSpec spec) {
195        if (spec == null) {
196            return;
197        }
198
199        LocalItem local = spec.getLocalItem();
200        CstString name = local.getName();
201        CstString signature = local.getSignature();
202        Type type = spec.getType();
203
204        if (type != Type.KNOWN_NULL) {
205            result.add(CstType.intern(type));
206        }
207
208        if (name != null) {
209            result.add(name);
210        }
211
212        if (signature != null) {
213            result.add(signature);
214        }
215    }
216
217    /**
218     * Adds an instruction to the output.
219     *
220     * @param insn {@code non-null;} the instruction to add
221     */
222    public void add(DalvInsn insn) {
223        insns.add(insn);
224        updateInfo(insn);
225    }
226
227    /**
228     * Inserts an instruction in the output at the given offset.
229     *
230     * @param at {@code >= 0;} what index to insert at
231     * @param insn {@code non-null;} the instruction to insert
232     */
233    public void insert(int at, DalvInsn insn) {
234        insns.add(at, insn);
235        updateInfo(insn);
236    }
237
238    /**
239     * Helper for {@link #add} and {@link #insert},
240     * which updates the position and local info flags.
241     *
242     * @param insn {@code non-null;} an instruction that was just introduced
243     */
244    private void updateInfo(DalvInsn insn) {
245        if (! hasAnyPositionInfo) {
246            SourcePosition pos = insn.getPosition();
247            if (pos.getLine() >= 0) {
248                hasAnyPositionInfo = true;
249            }
250        }
251
252        if (! hasAnyLocalInfo) {
253            if (hasLocalInfo(insn)) {
254                hasAnyLocalInfo = true;
255            }
256        }
257    }
258
259    /**
260     * Reverses a branch which is buried a given number of instructions
261     * backward in the output. It is illegal to call this unless the
262     * indicated instruction really is a reversible branch.
263     *
264     * @param which how many instructions back to find the branch;
265     * {@code 0} is the most recently added instruction,
266     * {@code 1} is the instruction before that, etc.
267     * @param newTarget {@code non-null;} the new target for the
268     * reversed branch
269     */
270    public void reverseBranch(int which, CodeAddress newTarget) {
271        int size = insns.size();
272        int index = size - which - 1;
273        TargetInsn targetInsn;
274
275        try {
276            targetInsn = (TargetInsn) insns.get(index);
277        } catch (IndexOutOfBoundsException ex) {
278            // Translate the exception.
279            throw new IllegalArgumentException("too few instructions");
280        } catch (ClassCastException ex) {
281            // Translate the exception.
282            throw new IllegalArgumentException("non-reversible instruction");
283        }
284
285        /*
286         * No need to call this.set(), since the format and other info
287         * are the same.
288         */
289        insns.set(index, targetInsn.withNewTargetAndReversed(newTarget));
290    }
291
292    /**
293     * Assigns indices in all instructions that need them, using the
294     * given callback to perform lookups. This should be called before
295     * calling {@link #finishProcessingAndGetList}.
296     *
297     * @param callback {@code non-null;} callback object
298     */
299    public void assignIndices(DalvCode.AssignIndicesCallback callback) {
300        for (DalvInsn insn : insns) {
301            if (insn instanceof CstInsn) {
302                assignIndices((CstInsn) insn, callback);
303            }
304        }
305    }
306
307    /**
308     * Helper for {@link #assignIndices} which does assignment for one
309     * instruction.
310     *
311     * @param insn {@code non-null;} the instruction
312     * @param callback {@code non-null;} the callback
313     */
314    private static void assignIndices(CstInsn insn,
315            DalvCode.AssignIndicesCallback callback) {
316        Constant cst = insn.getConstant();
317        int index = callback.getIndex(cst);
318
319        if (index >= 0) {
320            insn.setIndex(index);
321        }
322
323        if (cst instanceof CstMemberRef) {
324            CstMemberRef member = (CstMemberRef) cst;
325            CstType definer = member.getDefiningClass();
326            index = callback.getIndex(definer);
327            if (index >= 0) {
328                insn.setClassIndex(index);
329            }
330        }
331    }
332
333    /**
334     * Does final processing on this instance and gets the output as
335     * a {@link DalvInsnList}. Final processing consists of:
336     *
337     * <ul>
338     *   <li>optionally renumbering registers (to make room as needed for
339     *   expanded instructions)</li>
340     *   <li>picking a final opcode for each instruction</li>
341     *   <li>rewriting instructions, because of register number,
342     *   constant pool index, or branch target size issues</li>
343     *   <li>assigning final addresses</li>
344     * </ul>
345     *
346     * <p><b>Note:</b> This method may only be called once per instance
347     * of this class.</p>
348     *
349     * @return {@code non-null;} the output list
350     * @throws UnsupportedOperationException if this method has
351     * already been called
352     */
353    public DalvInsnList finishProcessingAndGetList() {
354        if (reservedCount >= 0) {
355            throw new UnsupportedOperationException("already processed");
356        }
357
358        Dop[] opcodes = makeOpcodesArray();
359        reserveRegisters(opcodes);
360        massageInstructions(opcodes);
361        assignAddressesAndFixBranches();
362
363        return DalvInsnList.makeImmutable(insns,
364                reservedCount + unreservedRegCount);
365    }
366
367    /**
368     * Helper for {@link #finishProcessingAndGetList}, which extracts
369     * the opcode out of each instruction into a separate array, to be
370     * further manipulated as things progress.
371     *
372     * @return {@code non-null;} the array of opcodes
373     */
374    private Dop[] makeOpcodesArray() {
375        int size = insns.size();
376        Dop[] result = new Dop[size];
377
378        for (int i = 0; i < size; i++) {
379            result[i] = insns.get(i).getOpcode();
380        }
381
382        return result;
383    }
384
385    /**
386     * Helper for {@link #finishProcessingAndGetList}, which figures
387     * out how many reserved registers are required and then reserving
388     * them. It also updates the given {@code opcodes} array so
389     * as to avoid extra work when constructing the massaged
390     * instruction list.
391     *
392     * @param opcodes {@code non-null;} array of per-instruction
393     * opcode selections
394     */
395    private void reserveRegisters(Dop[] opcodes) {
396        int oldReservedCount = (reservedCount < 0) ? 0 : reservedCount;
397
398        /*
399         * Call calculateReservedCount() and then perform register
400         * reservation, repeatedly until no new reservations happen.
401         */
402        for (;;) {
403            int newReservedCount = calculateReservedCount(opcodes);
404            if (oldReservedCount >= newReservedCount) {
405                break;
406            }
407
408            int reservedDifference = newReservedCount - oldReservedCount;
409            int size = insns.size();
410
411            for (int i = 0; i < size; i++) {
412                /*
413                 * CodeAddress instance identity is used to link
414                 * TargetInsns to their targets, so it is
415                 * inappropriate to make replacements, and they don't
416                 * have registers in any case. Hence, the instanceof
417                 * test below.
418                 */
419                DalvInsn insn = insns.get(i);
420                if (!(insn instanceof CodeAddress)) {
421                    /*
422                     * No need to call this.set() since the format and
423                     * other info are the same.
424                     */
425                    insns.set(i, insn.withRegisterOffset(reservedDifference));
426                }
427            }
428
429            oldReservedCount = newReservedCount;
430        }
431
432        reservedCount = oldReservedCount;
433    }
434
435    /**
436     * Helper for {@link #reserveRegisters}, which does one
437     * pass over the instructions, calculating the number of
438     * registers that need to be reserved. It also updates the
439     * {@code opcodes} list to help avoid extra work in future
440     * register reservation passes.
441     *
442     * @param opcodes {@code non-null;} array of per-instruction
443     * opcode selections
444     * @return {@code >= 0;} the count of reserved registers
445     */
446    private int calculateReservedCount(Dop[] opcodes) {
447        int size = insns.size();
448
449        /*
450         * Potential new value of reservedCount, which gets updated in the
451         * following loop. It starts out with the existing reservedCount
452         * and gets increased if it turns out that additional registers
453         * need to be reserved.
454         */
455        int newReservedCount = reservedCount;
456
457        for (int i = 0; i < size; i++) {
458            DalvInsn insn = insns.get(i);
459            Dop originalOpcode = opcodes[i];
460            Dop newOpcode = findOpcodeForInsn(insn, originalOpcode);
461
462            if (newOpcode == null) {
463                /*
464                 * The instruction will need to be expanded, so find the
465                 * expanded opcode and reserve registers for it.
466                 */
467                Dop expandedOp = findExpandedOpcodeForInsn(insn);
468                BitSet compatRegs = expandedOp.getFormat().compatibleRegs(insn);
469                int reserve = insn.getMinimumRegisterRequirement(compatRegs);
470                if (reserve > newReservedCount) {
471                    newReservedCount = reserve;
472                }
473            } else if (originalOpcode == newOpcode) {
474                continue;
475            }
476
477            opcodes[i] = newOpcode;
478        }
479
480        return newReservedCount;
481    }
482
483    /**
484     * Attempts to fit the given instruction into a specific opcode,
485     * returning the opcode whose format that the instruction fits
486     * into or {@code null} to indicate that the instruction will need
487     * to be expanded. This fitting process starts with the given
488     * opcode as a first "best guess" and then pessimizes from there
489     * if necessary.
490     *
491     * @param insn {@code non-null;} the instruction in question
492     * @param guess {@code null-ok;} the current guess as to the best
493     * opcode; {@code null} means that no simple opcode fits
494     * @return {@code null-ok;} a possibly-different opcode; either a
495     * {@code non-null} good fit or {@code null} to indicate that no
496     * simple opcode fits
497     */
498    private Dop findOpcodeForInsn(DalvInsn insn, Dop guess) {
499        /*
500         * Note: The initial guess might be null, meaning that an
501         * earlier call to this method already determined that there
502         * was no possible simple opcode fit.
503         */
504
505        while (guess != null) {
506            if (guess.getFormat().isCompatible(insn)) {
507                break;
508            }
509
510            guess = Dops.getNextOrNull(guess, dexOptions);
511        }
512
513        return guess;
514    }
515
516    /**
517     * Finds the proper opcode for the given instruction, ignoring
518     * register constraints.
519     *
520     * @param insn {@code non-null;} the instruction in question
521     * @return {@code non-null;} the opcode that fits
522     */
523    private Dop findExpandedOpcodeForInsn(DalvInsn insn) {
524        Dop result = findOpcodeForInsn(insn.getLowRegVersion(), insn.getOpcode());
525        if (result == null) {
526            throw new DexException("No expanded opcode for " + insn);
527        }
528        return result;
529    }
530
531    /**
532     * Helper for {@link #finishProcessingAndGetList}, which goes
533     * through each instruction in the output, making sure its opcode
534     * can accomodate its arguments. In cases where the opcode is
535     * unable to do so, this replaces the instruction with a larger
536     * instruction with identical semantics that <i>will</i> work.
537     *
538     * <p>This method may also reserve a number of low-numbered
539     * registers, renumbering the instructions' original registers, in
540     * order to have register space available in which to move
541     * very-high registers when expanding instructions into
542     * multi-instruction sequences. This expansion is done when no
543     * simple instruction format can be found for a given instruction that
544     * is able to accomodate that instruction's registers.</p>
545     *
546     * <p>This method ignores issues of branch target size, since
547     * final addresses aren't known at the point that this method is
548     * called.</p>
549     *
550     * @param opcodes {@code non-null;} array of per-instruction
551     * opcode selections
552     */
553    private void massageInstructions(Dop[] opcodes) {
554        if (reservedCount == 0) {
555            /*
556             * The easy common case: No registers were reserved, so we
557             * merely need to replace any instructions whose format
558             * (and hence whose opcode) changed during the reservation
559             * pass, but all instructions will stay at their original
560             * indices, and the instruction list doesn't grow.
561             */
562            int size = insns.size();
563
564            for (int i = 0; i < size; i++) {
565                DalvInsn insn = insns.get(i);
566                Dop originalOpcode = insn.getOpcode();
567                Dop currentOpcode = opcodes[i];
568
569                if (originalOpcode != currentOpcode) {
570                    insns.set(i, insn.withOpcode(currentOpcode));
571                }
572            }
573        } else {
574            /*
575             * The difficult uncommon case: Some instructions have to be
576             * expanded to deal with high registers.
577             */
578            insns = performExpansion(opcodes);
579        }
580    }
581
582    /**
583     * Helper for {@link #massageInstructions}, which constructs a
584     * replacement list, where each {link DalvInsn} instance that
585     * couldn't be represented simply (due to register representation
586     * problems) is expanded into a series of instances that together
587     * perform the proper function.
588     *
589     * @param opcodes {@code non-null;} array of per-instruction
590     * opcode selections
591     * @return {@code non-null;} the replacement list
592     */
593    private ArrayList<DalvInsn> performExpansion(Dop[] opcodes) {
594        int size = insns.size();
595        ArrayList<DalvInsn> result = new ArrayList<DalvInsn>(size * 2);
596
597        for (int i = 0; i < size; i++) {
598            DalvInsn insn = insns.get(i);
599            Dop originalOpcode = insn.getOpcode();
600            Dop currentOpcode = opcodes[i];
601            DalvInsn prefix;
602            DalvInsn suffix;
603
604            if (currentOpcode != null) {
605                // No expansion is necessary.
606                prefix = null;
607                suffix = null;
608            } else {
609                // Expansion is required.
610                currentOpcode = findExpandedOpcodeForInsn(insn);
611                BitSet compatRegs =
612                    currentOpcode.getFormat().compatibleRegs(insn);
613                prefix = insn.expandedPrefix(compatRegs);
614                suffix = insn.expandedSuffix(compatRegs);
615
616                // Expand necessary registers to fit the new format
617                insn = insn.expandedVersion(compatRegs);
618            }
619
620            if (prefix != null) {
621                result.add(prefix);
622            }
623
624            if (currentOpcode != originalOpcode) {
625                insn = insn.withOpcode(currentOpcode);
626            }
627            result.add(insn);
628
629            if (suffix != null) {
630                result.add(suffix);
631            }
632        }
633
634        return result;
635    }
636
637    /**
638     * Helper for {@link #finishProcessingAndGetList}, which assigns
639     * addresses to each instruction, possibly rewriting branches to
640     * fix ones that wouldn't otherwise be able to reach their
641     * targets.
642     */
643    private void assignAddressesAndFixBranches() {
644        for (;;) {
645            assignAddresses();
646            if (!fixBranches()) {
647                break;
648            }
649        }
650    }
651
652    /**
653     * Helper for {@link #assignAddressesAndFixBranches}, which
654     * assigns an address to each instruction, in order.
655     */
656    private void assignAddresses() {
657        int address = 0;
658        int size = insns.size();
659
660        for (int i = 0; i < size; i++) {
661            DalvInsn insn = insns.get(i);
662            insn.setAddress(address);
663            address += insn.codeSize();
664        }
665    }
666
667    /**
668     * Helper for {@link #assignAddressesAndFixBranches}, which checks
669     * the branch target size requirement of each branch instruction
670     * to make sure it fits. For instructions that don't fit, this
671     * rewrites them to use a {@code goto} of some sort. In the
672     * case of a conditional branch that doesn't fit, the sense of the
673     * test is reversed in order to branch around a {@code goto}
674     * to the original target.
675     *
676     * @return whether any branches had to be fixed
677     */
678    private boolean fixBranches() {
679        int size = insns.size();
680        boolean anyFixed = false;
681
682        for (int i = 0; i < size; i++) {
683            DalvInsn insn = insns.get(i);
684            if (!(insn instanceof TargetInsn)) {
685                // This loop only needs to inspect TargetInsns.
686                continue;
687            }
688
689            Dop opcode = insn.getOpcode();
690            TargetInsn target = (TargetInsn) insn;
691
692            if (opcode.getFormat().branchFits(target)) {
693                continue;
694            }
695
696            if (opcode.getFamily() == Opcodes.GOTO) {
697                // It is a goto; widen it if possible.
698                opcode = findOpcodeForInsn(insn, opcode);
699                if (opcode == null) {
700                    /*
701                     * The branch is already maximally large. This should
702                     * only be possible if a method somehow manages to have
703                     * more than 2^31 code units.
704                     */
705                    throw new UnsupportedOperationException("method too long");
706                }
707                insns.set(i, insn.withOpcode(opcode));
708            } else {
709                /*
710                 * It is a conditional: Reverse its sense, and arrange for
711                 * it to branch around an absolute goto to the original
712                 * branch target.
713                 *
714                 * Note: An invariant of the list being processed is
715                 * that every TargetInsn is followed by a CodeAddress.
716                 * Hence, it is always safe to get the next element
717                 * after a TargetInsn and cast it to CodeAddress, as
718                 * is happening a few lines down.
719                 *
720                 * Also note: Size gets incremented by one here, as we
721                 * have -- in the net -- added one additional element
722                 * to the list, so we increment i to match. The added
723                 * and changed elements will be inspected by a repeat
724                 * call to this method after this invocation returns.
725                 */
726                CodeAddress newTarget;
727                try {
728                    newTarget = (CodeAddress) insns.get(i + 1);
729                } catch (IndexOutOfBoundsException ex) {
730                    // The TargetInsn / CodeAddress invariant was violated.
731                    throw new IllegalStateException(
732                            "unpaired TargetInsn (dangling)");
733                } catch (ClassCastException ex) {
734                    // The TargetInsn / CodeAddress invariant was violated.
735                    throw new IllegalStateException("unpaired TargetInsn");
736                }
737                TargetInsn gotoInsn =
738                    new TargetInsn(Dops.GOTO, target.getPosition(),
739                            RegisterSpecList.EMPTY, target.getTarget());
740                insns.set(i, gotoInsn);
741                insns.add(i, target.withNewTargetAndReversed(newTarget));
742                size++;
743                i++;
744            }
745
746            anyFixed = true;
747        }
748
749        return anyFixed;
750    }
751}
752