dalvik/dx/src/com/android/dx/ssa/PhiInsn.java

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