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