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.*;
20import com.android.dx.rop.type.Type;
21import com.android.dx.rop.type.TypeBearer;
22import com.android.dx.util.Hex;
23
24import java.util.ArrayList;
25import java.util.List;
26
27/**
28 * A Phi instruction (magical post-control-flow-merge) instruction
29 * in SSA form. Will be converted to moves in predecessor blocks before
30 * conversion back to ROP form.
31 */
32public final class PhiInsn extends SsaInsn {
33    /**
34     * result register. The original result register of the phi insn
35     * is needed during the renaming process after the new result
36     * register has already been chosen.
37     */
38    private final int ropResultReg;
39
40    /**
41     * {@code non-null;} operands of the instruction; built up by
42     * {@link #addPhiOperand}
43     */
44    private final ArrayList<Operand> operands = new ArrayList<Operand>();
45
46    /** {@code null-ok;} source registers; constructed lazily */
47    private RegisterSpecList sources;
48
49    /**
50     * Constructs a new phi insn with no operands.
51     *
52     * @param resultReg the result reg for this phi insn
53     * @param block block containing this insn.
54     */
55    public PhiInsn(RegisterSpec resultReg, SsaBasicBlock block) {
56        super(resultReg, block);
57        ropResultReg = resultReg.getReg();
58    }
59
60    /**
61     * Makes a phi insn with a void result type.
62     *
63     * @param resultReg the result register for this phi insn.
64     * @param block block containing this insn.
65     */
66    public PhiInsn(final int resultReg, final SsaBasicBlock block) {
67        /*
68         * The result type here is bogus: The type depends on the
69         * operand and will be derived later.
70         */
71        super(RegisterSpec.make(resultReg, Type.VOID), block);
72        ropResultReg = resultReg;
73    }
74
75    /** {@inheritDoc} */
76    @Override
77    public PhiInsn clone() {
78        throw new UnsupportedOperationException("can't clone phi");
79    }
80
81    /**
82     * Updates the TypeBearers of all the sources (phi operands) to be
83     * the current TypeBearer of the register-defining instruction's result.
84     * This is used during phi-type resolution.<p>
85     *
86     * Note that local association of operands are preserved in this step.
87     *
88     * @param ssaMeth method that contains this insn
89     */
90    public void updateSourcesToDefinitions(SsaMethod ssaMeth) {
91        for (Operand o : operands) {
92            RegisterSpec def
93                = ssaMeth.getDefinitionForRegister(
94                    o.regSpec.getReg()).getResult();
95
96            o.regSpec = o.regSpec.withType(def.getType());
97        }
98
99        sources = null;
100    }
101
102    /**
103     * Changes the result type. Used during phi type resolution
104     *
105     * @param type {@code non-null;} new TypeBearer
106     * @param local {@code null-ok;} new local info, if available
107     */
108    public void changeResultType(TypeBearer type, LocalItem local) {
109        setResult(RegisterSpec.makeLocalOptional(
110                          getResult().getReg(), type, local));
111    }
112
113    /**
114     * Gets the original rop-form result reg. This is useful during renaming.
115     *
116     * @return the original rop-form result reg
117     */
118    public int getRopResultReg() {
119        return ropResultReg;
120    }
121
122    /**
123     * Adds an operand to this phi instruction.
124     *
125     * @param registerSpec register spec, including type and reg of operand
126     * @param predBlock predecessor block to be associated with this operand
127     */
128    public void addPhiOperand(RegisterSpec registerSpec,
129            SsaBasicBlock predBlock) {
130        operands.add(new Operand(registerSpec, predBlock.getIndex(),
131                predBlock.getRopLabel()));
132
133        // Un-cache sources, in case someone has already called getSources().
134        sources = null;
135    }
136
137    /**
138     * Removes all operand uses of a register from this phi instruction.
139     *
140     * @param registerSpec register spec, including type and reg of operand
141     */
142    public void removePhiRegister(RegisterSpec registerSpec) {
143        ArrayList<Operand> operandsToRemove = new ArrayList<Operand>();
144        for (Operand o : operands) {
145            if (o.regSpec.getReg() == registerSpec.getReg()) {
146                operandsToRemove.add(o);
147            }
148        }
149
150        operands.removeAll(operandsToRemove);
151
152        // Un-cache sources, in case someone has already called getSources().
153        sources = null;
154    }
155
156    /**
157     * Gets the index of the pred block associated with the RegisterSpec
158     * at the particular getSources() index.
159     *
160     * @param sourcesIndex index of source in getSources()
161     * @return block index
162     */
163    public int predBlockIndexForSourcesIndex(int sourcesIndex) {
164        return operands.get(sourcesIndex).blockIndex;
165    }
166
167    /**
168     * {@inheritDoc}
169     *
170     * Always returns null for {@code PhiInsn}s.
171     */
172    @Override
173    public Rop getOpcode() {
174        return null;
175    }
176
177    /**
178     * {@inheritDoc}
179     *
180     * Always returns null for {@code PhiInsn}s.
181     */
182    @Override
183    public Insn getOriginalRopInsn() {
184        return null;
185    }
186
187    /**
188     * {@inheritDoc}
189     *
190     * Always returns false for {@code PhiInsn}s.
191     */
192    @Override
193    public boolean canThrow() {
194        return false;
195    }
196
197    /**
198     * Gets sources. Constructed lazily from phi operand data structures and
199     * then cached.
200     *
201     * @return {@code non-null;} sources list
202     */
203    @Override
204    public RegisterSpecList getSources() {
205        if (sources != null) {
206            return sources;
207        }
208
209        if (operands.size() == 0) {
210            // How'd this happen? A phi insn with no operand?
211            return RegisterSpecList.EMPTY;
212        }
213
214        int szSources = operands.size();
215        sources = new RegisterSpecList(szSources);
216
217        for (int i = 0; i < szSources; i++) {
218            Operand o = operands.get(i);
219
220            sources.set(i, o.regSpec);
221        }
222
223        sources.setImmutable();
224        return sources;
225    }
226
227    /** {@inheritDoc} */
228    @Override
229    public boolean isRegASource(int reg) {
230        /*
231         * Avoid creating a sources list in case it has not already been
232         * created.
233         */
234
235        for (Operand o : operands) {
236            if (o.regSpec.getReg() == reg) {
237                return true;
238            }
239        }
240
241        return false;
242    }
243
244    /**
245     * @return true if all operands use the same register
246     */
247    public boolean areAllOperandsEqual() {
248        if (operands.size() == 0 ) {
249            // This should never happen.
250            return true;
251        }
252
253        int firstReg = operands.get(0).regSpec.getReg();
254        for (Operand o : operands) {
255            if (firstReg != o.regSpec.getReg()) {
256                return false;
257            }
258        }
259
260        return true;
261    }
262
263    /** {@inheritDoc} */
264    @Override
265    public final void mapSourceRegisters(RegisterMapper mapper) {
266        for (Operand o : operands) {
267            RegisterSpec old = o.regSpec;
268            o.regSpec = mapper.map(old);
269            if (old != o.regSpec) {
270                getBlock().getParent().onSourceChanged(this, old, o.regSpec);
271            }
272        }
273        sources = null;
274    }
275
276    /**
277     * Always throws an exeption, since a phi insn may not be
278     * converted back to rop form.
279     *
280     * @return always throws exception
281     */
282    @Override
283    public Insn toRopInsn() {
284        throw new IllegalArgumentException(
285                "Cannot convert phi insns to rop form");
286    }
287
288    /**
289     * Returns the list of predecessor blocks associated with all operands
290     * that have {@code reg} as an operand register.
291     *
292     * @param reg register to look up
293     * @param ssaMeth method we're operating on
294     * @return list of predecessor blocks, empty if none
295     */
296    public List<SsaBasicBlock> predBlocksForReg(int reg, SsaMethod ssaMeth) {
297        ArrayList<SsaBasicBlock> ret = new ArrayList<SsaBasicBlock>();
298
299        for (Operand o : operands) {
300            if (o.regSpec.getReg() == reg) {
301                ret.add(ssaMeth.getBlocks().get(o.blockIndex));
302            }
303        }
304
305        return ret;
306    }
307
308    /** {@inheritDoc} */
309    @Override
310    public boolean isPhiOrMove() {
311        return true;
312    }
313
314    /** {@inheritDoc} */
315    @Override
316    public boolean hasSideEffect() {
317        return Optimizer.getPreserveLocals() && getLocalAssignment() != null;
318    }
319
320    /** {@inheritDoc} */
321    @Override
322    public void accept(SsaInsn.Visitor v) {
323        v.visitPhiInsn(this);
324    }
325
326    /** {@inheritDoc} */
327    public String toHuman() {
328        return toHumanWithInline(null);
329    }
330
331    /**
332     * Returns human-readable string for listing dumps. This method
333     * allows sub-classes to specify extra text.
334     *
335     * @param extra {@code null-ok;} the argument to print after the opcode
336     * @return human-readable string for listing dumps
337     */
338    protected final String toHumanWithInline(String extra) {
339        StringBuffer sb = new StringBuffer(80);
340
341        sb.append(SourcePosition.NO_INFO);
342        sb.append(": phi");
343
344        if (extra != null) {
345            sb.append("(");
346            sb.append(extra);
347            sb.append(")");
348        }
349
350        RegisterSpec result = getResult();
351
352        if (result == null) {
353            sb.append(" .");
354        } else {
355            sb.append(" ");
356            sb.append(result.toHuman());
357        }
358
359        sb.append(" <-");
360
361        int sz = getSources().size();
362        if (sz == 0) {
363            sb.append(" .");
364        } else {
365            for (int i = 0; i < sz; i++) {
366                sb.append(" ");
367                sb.append(sources.get(i).toHuman()
368                        + "[b="
369                        + Hex.u2(operands.get(i).ropLabel)  + "]");
370            }
371        }
372
373        return sb.toString();
374    }
375
376    /**
377     * A single phi operand, consiting of source register and block index
378     * for move.
379     */
380    private static class Operand {
381        public RegisterSpec regSpec;
382        public final int blockIndex;
383        public final int ropLabel;       // only used for debugging
384
385        public Operand(RegisterSpec regSpec, int blockIndex, int ropLabel) {
386            this.regSpec = regSpec;
387            this.blockIndex = blockIndex;
388            this.ropLabel = ropLabel;
389        }
390    }
391
392    /**
393     * Visitor interface for instances of this (outer) class.
394     */
395    public static interface Visitor {
396        public void visitPhiInsn(PhiInsn insn);
397    }
398}
399