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.Insn;
20import com.android.dx.rop.code.PlainCstInsn;
21import com.android.dx.rop.code.PlainInsn;
22import com.android.dx.rop.code.RegOps;
23import com.android.dx.rop.code.RegisterSpec;
24import com.android.dx.rop.code.RegisterSpecList;
25import com.android.dx.rop.code.Rop;
26import com.android.dx.rop.code.Rops;
27import com.android.dx.rop.code.TranslationAdvice;
28import com.android.dx.rop.cst.Constant;
29import com.android.dx.rop.cst.CstLiteralBits;
30import com.android.dx.rop.type.Type;
31import com.android.dx.rop.type.TypeBearer;
32import java.util.ArrayList;
33import java.util.List;
34
35/**
36 * Upgrades insn to their literal (constant-immediate) equivalent if possible.
37 * Also switches IF instructions that compare with a constant zero or null
38 * to be their IF_*Z equivalents.
39 */
40public class LiteralOpUpgrader {
41
42    /** method we're processing */
43    private final SsaMethod ssaMeth;
44
45    /**
46     * Process a method.
47     *
48     * @param ssaMethod {@code non-null;} method to process
49     */
50    public static void process(SsaMethod ssaMethod) {
51        LiteralOpUpgrader dc;
52
53        dc = new LiteralOpUpgrader(ssaMethod);
54
55        dc.run();
56    }
57
58    private LiteralOpUpgrader(SsaMethod ssaMethod) {
59        this.ssaMeth = ssaMethod;
60    }
61
62    /**
63     * Returns true if the register contains an integer 0 or a known-null
64     * object reference
65     *
66     * @param spec non-null spec
67     * @return true for 0 or null type bearers
68     */
69    private static boolean isConstIntZeroOrKnownNull(RegisterSpec spec) {
70        TypeBearer tb = spec.getTypeBearer();
71        if (tb instanceof CstLiteralBits) {
72            CstLiteralBits clb = (CstLiteralBits) tb;
73            return (clb.getLongBits() == 0);
74        }
75        return false;
76    }
77
78    /**
79     * Run the literal op upgrader
80     */
81    private void run() {
82        final TranslationAdvice advice = Optimizer.getAdvice();
83
84        ssaMeth.forEachInsn(new SsaInsn.Visitor() {
85            public void visitMoveInsn(NormalSsaInsn insn) {
86                // do nothing
87            }
88
89            public void visitPhiInsn(PhiInsn insn) {
90                // do nothing
91            }
92
93            public void visitNonMoveInsn(NormalSsaInsn insn) {
94
95                Insn originalRopInsn = insn.getOriginalRopInsn();
96                Rop opcode = originalRopInsn.getOpcode();
97                RegisterSpecList sources = insn.getSources();
98
99                // Replace insns with constant results with const insns
100                if (tryReplacingWithConstant(insn)) return;
101
102                if (sources.size() != 2 ) {
103                    // We're only dealing with two-source insns here.
104                    return;
105                }
106
107                if (opcode.getBranchingness() == Rop.BRANCH_IF) {
108                    /*
109                     * An if instruction can become an if-*z instruction.
110                     */
111                    if (isConstIntZeroOrKnownNull(sources.get(0))) {
112                        replacePlainInsn(insn, sources.withoutFirst(),
113                              RegOps.flippedIfOpcode(opcode.getOpcode()), null);
114                    } else if (isConstIntZeroOrKnownNull(sources.get(1))) {
115                        replacePlainInsn(insn, sources.withoutLast(),
116                              opcode.getOpcode(), null);
117                    }
118                } else if (advice.hasConstantOperation(
119                        opcode, sources.get(0), sources.get(1))) {
120                    insn.upgradeToLiteral();
121                } else  if (opcode.isCommutative()
122                        && advice.hasConstantOperation(
123                        opcode, sources.get(1), sources.get(0))) {
124                    /*
125                     * An instruction can be commuted to a literal operation
126                     */
127
128                    insn.setNewSources(
129                            RegisterSpecList.make(
130                                    sources.get(1), sources.get(0)));
131
132                    insn.upgradeToLiteral();
133                }
134            }
135        });
136    }
137
138    /**
139     * Tries to replace an instruction with a const instruction. The given
140     * instruction must have a constant result for it to be replaced.
141     *
142     * @param insn {@code non-null;} instruction to try to replace
143     * @return true if the instruction was replaced
144     */
145    private boolean tryReplacingWithConstant(NormalSsaInsn insn) {
146        Insn originalRopInsn = insn.getOriginalRopInsn();
147        Rop opcode = originalRopInsn.getOpcode();
148        RegisterSpec result = insn.getResult();
149
150        if (result != null && !ssaMeth.isRegALocal(result) &&
151                opcode.getOpcode() != RegOps.CONST) {
152            TypeBearer type = insn.getResult().getTypeBearer();
153            if (type.isConstant() && type.getBasicType() == Type.BT_INT) {
154                // Replace the instruction with a constant
155                replacePlainInsn(insn, RegisterSpecList.EMPTY,
156                        RegOps.CONST, (Constant) type);
157
158                // Remove the source as well if this is a move-result-pseudo
159                if (opcode.getOpcode() == RegOps.MOVE_RESULT_PSEUDO) {
160                    int pred = insn.getBlock().getPredecessors().nextSetBit(0);
161                    ArrayList<SsaInsn> predInsns =
162                            ssaMeth.getBlocks().get(pred).getInsns();
163                    NormalSsaInsn sourceInsn =
164                            (NormalSsaInsn) predInsns.get(predInsns.size()-1);
165                    replacePlainInsn(sourceInsn, RegisterSpecList.EMPTY,
166                            RegOps.GOTO, null);
167                }
168                return true;
169            }
170        }
171        return false;
172    }
173
174    /**
175     * Replaces an SsaInsn containing a PlainInsn with a new PlainInsn. The
176     * new PlainInsn is constructed with a new RegOp and new sources.
177     *
178     * TODO move this somewhere else.
179     *
180     * @param insn {@code non-null;} an SsaInsn containing a PlainInsn
181     * @param newSources {@code non-null;} new sources list for new insn
182     * @param newOpcode A RegOp from {@link RegOps}
183     * @param cst {@code null-ok;} constant for new instruction, if any
184     */
185    private void replacePlainInsn(NormalSsaInsn insn,
186            RegisterSpecList newSources, int newOpcode, Constant cst) {
187
188        Insn originalRopInsn = insn.getOriginalRopInsn();
189        Rop newRop = Rops.ropFor(newOpcode, insn.getResult(), newSources, cst);
190        Insn newRopInsn;
191        if (cst == null) {
192            newRopInsn = new PlainInsn(newRop, originalRopInsn.getPosition(),
193                    insn.getResult(), newSources);
194        } else {
195            newRopInsn = new PlainCstInsn(newRop, originalRopInsn.getPosition(),
196                    insn.getResult(), newSources, cst);
197        }
198        NormalSsaInsn newInsn = new NormalSsaInsn(newRopInsn, insn.getBlock());
199
200        List<SsaInsn> insns = insn.getBlock().getInsns();
201
202        ssaMeth.onInsnRemoved(insn);
203        insns.set(insns.lastIndexOf(insn), newInsn);
204        ssaMeth.onInsnAdded(newInsn);
205    }
206}
207