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