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