dx/src/com/android/dx/ssa/PhiInsn.java - platform/dalvik - Git at Google

 /*
  * Copyright (C) 2007 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 package com.android.dx.ssa;

 import com.android.dx.rop.code.*;
 import com.android.dx.rop.type.Type;
 import com.android.dx.rop.type.TypeBearer;
 import com.android.dx.util.Hex;

 import java.util.ArrayList;
 import java.util.List;

 /**
  * A Phi instruction (magical post-control-flow-merge) instruction
  * in SSA form. Will be converted to moves in predecessor blocks before
  * conversion back to ROP form.
  */
 public final class PhiInsn extends SsaInsn {
     /**
      * result register. The original result register of the phi insn
      * is needed during the renaming process after the new result
      * register has already been chosen.
      */
     private final int ropResultReg;

     /**
      * {@code non-null;} operands of the instruction; built up by
      * {@link #addPhiOperand}
      */
     private final ArrayList<Operand> operands = new ArrayList<Operand>();

     /** {@code null-ok;} source registers; constructed lazily */
     private RegisterSpecList sources;

     /**
      * Constructs a new phi insn with no operands.
      *
      * @param resultReg the result reg for this phi insn
      * @param block block containing this insn.
      */
     public PhiInsn(RegisterSpec resultReg, SsaBasicBlock block) {
         super(resultReg, block);
         ropResultReg = resultReg.getReg();
     }

     /**
      * Makes a phi insn with a void result type.
      *
      * @param resultReg the result register for this phi insn.
      * @param block block containing this insn.
      */
     public PhiInsn(final int resultReg, final SsaBasicBlock block) {
         /*
          * The result type here is bogus: The type depends on the
          * operand and will be derived later.
          */
         super(RegisterSpec.make(resultReg, Type.VOID), block);
         ropResultReg = resultReg;
     }

     /** {@inheritDoc} */
     public PhiInsn clone() {
         throw new UnsupportedOperationException("can't clone phi");
     }

     /**
      * Updates the TypeBearers of all the sources (phi operands) to be
      * the current TypeBearer of the register-defining instruction's result.
      * This is used during phi-type resolution.<p>
      *
      * Note that local association of operands are preserved in this step.
      *
      * @param ssaMeth method that contains this insn
      */
     public void updateSourcesToDefinitions(SsaMethod ssaMeth) {
         for (Operand o : operands) {
             RegisterSpec def
                 = ssaMeth.getDefinitionForRegister(
                     o.regSpec.getReg()).getResult();

             o.regSpec = o.regSpec.withType(def.getType());
         }

         sources = null;
     }

     /**
      * Changes the result type. Used during phi type resolution
      *
      * @param type {@code non-null;} new TypeBearer
      * @param local {@code null-ok;} new local info, if available
      */
     public void changeResultType(TypeBearer type, LocalItem local) {
         setResult(RegisterSpec.makeLocalOptional(
                           getResult().getReg(), type, local));
     }

     /**
      * Gets the original rop-form result reg. This is useful during renaming.
      *
      * @return the original rop-form result reg
      */
     public int getRopResultReg() {
         return ropResultReg;
     }

     /**
      * Adds an operand to this phi instruction.
      *
      * @param registerSpec register spec, including type and reg of operand
      * @param predBlock predecessor block to be associated with this operand
      */
     public void addPhiOperand(RegisterSpec registerSpec,
             SsaBasicBlock predBlock) {
         operands.add(new Operand(registerSpec, predBlock.getIndex(),
                 predBlock.getRopLabel()));

         // Un-cache sources, in case someone has already called getSources().
         sources = null;
     }

     /**
      * Gets the index of the pred block associated with the RegisterSpec
      * at the particular getSources() index.
      *
      * @param sourcesIndex index of source in getSources()
      * @return block index
      */
     public int predBlockIndexForSourcesIndex(int sourcesIndex) {
         return operands.get(sourcesIndex).blockIndex;
     }

     /**
      * {@inheritDoc}
      *
      * Always returns null for {@code PhiInsn}s.
      */
     @Override
     public Rop getOpcode() {
         return null;
     }

     /**
      * {@inheritDoc}
      *
      * Always returns null for {@code PhiInsn}s.
      */
     @Override
     public Insn getOriginalRopInsn() {
         return null;
     }

     /**
      * {@inheritDoc}
      *
      * Always returns false for {@code PhiInsn}s.
      */
     @Override
     public boolean canThrow() {
         return false;
     }

     /**
      * Gets sources. Constructed lazily from phi operand data structures and
      * then cached.
      *
      * @return {@code non-null;} sources list
      */
     public RegisterSpecList getSources() {
         if (sources != null) {
             return sources;
         }

         if (operands.size() == 0) {
             // How'd this happen? A phi insn with no operand?
             return RegisterSpecList.EMPTY;
         }

         int szSources = operands.size();
         sources = new RegisterSpecList(szSources);

         for (int i = 0; i < szSources; i++) {
             Operand o = operands.get(i);

             sources.set(i, o.regSpec);
         }

         sources.setImmutable();
         return sources;
     }

     /** {@inheritDoc} */
     @Override
     public boolean isRegASource(int reg) {
         /*
          * Avoid creating a sources list in case it has not already been
          * created.
          */

         for (Operand o : operands) {
             if (o.regSpec.getReg() == reg) {
                 return true;
             }
         }

         return false;
     }

     /**
      * @return true if all operands use the same register
      */
     public boolean areAllOperandsEqual() {
         if (operands.size() == 0 ) {
             // This should never happen.
             return true;
         }

         int firstReg = operands.get(0).regSpec.getReg();
         for (Operand o : operands) {
             if (firstReg != o.regSpec.getReg()) {
                 return false;
             }
         }

         return true;
     }

     /** {@inheritDoc} */
     @Override
     public final void mapSourceRegisters(RegisterMapper mapper) {
         for (Operand o : operands) {
             RegisterSpec old = o.regSpec;
             o.regSpec = mapper.map(old);
             if (old != o.regSpec) {
                 getBlock().getParent().onSourceChanged(this, old, o.regSpec);
             }
         }
         sources = null;
     }

     /**
      * Always throws an exeption, since a phi insn may not be
      * converted back to rop form.
      *
      * @return always throws exception
      */
     @Override
     public Insn toRopInsn() {
         throw new IllegalArgumentException(
                 "Cannot convert phi insns to rop form");
     }

     /**
      * Returns the list of predecessor blocks associated with all operands
      * that have {@code reg} as an operand register.
      *
      * @param reg register to look up
      * @param ssaMeth method we're operating on
      * @return list of predecessor blocks, empty if none
      */
     public List<SsaBasicBlock> predBlocksForReg(int reg, SsaMethod ssaMeth) {
         ArrayList<SsaBasicBlock> ret = new ArrayList<SsaBasicBlock>();

         for (Operand o : operands) {
             if (o.regSpec.getReg() == reg) {
                 ret.add(ssaMeth.getBlocks().get(o.blockIndex));
             }
         }

         return ret;
     }

     /** {@inheritDoc} */
     @Override
     public boolean isPhiOrMove() {
         return true;
     }

     /** {@inheritDoc} */
     @Override
     public boolean hasSideEffect() {
         return Optimizer.getPreserveLocals() && getLocalAssignment() != null;
     }

     /** {@inheritDoc} */
     @Override
     public void accept(SsaInsn.Visitor v) {
         v.visitPhiInsn(this);
     }

     /** {@inheritDoc} */
     public String toHuman() {
         return toHumanWithInline(null);
     }

     /**
      * Returns human-readable string for listing dumps. This method
      * allows sub-classes to specify extra text.
      *
      * @param extra {@code null-ok;} the argument to print after the opcode
      * @return human-readable string for listing dumps
      */
     protected final String toHumanWithInline(String extra) {
         StringBuffer sb = new StringBuffer(80);

         sb.append(SourcePosition.NO_INFO);
         sb.append(": phi");

         if (extra != null) {
             sb.append("(");
             sb.append(extra);
             sb.append(")");
         }

         RegisterSpec result = getResult();

         if (result == null) {
             sb.append(" .");
         } else {
             sb.append(" ");
             sb.append(result.toHuman());
         }

         sb.append(" <-");

         int sz = getSources().size();
         if (sz == 0) {
             sb.append(" .");
         } else {
             for (int i = 0; i < sz; i++) {
                 sb.append(" ");
                 sb.append(sources.get(i).toHuman()
                         + "[b="
                         + Hex.u2(operands.get(i).ropLabel)  + "]");
             }
         }

         return sb.toString();
     }

     /**
      * A single phi operand, consiting of source register and block index
      * for move.
      */
     private static class Operand {
         public RegisterSpec regSpec;
         public final int blockIndex;
         public final int ropLabel;       // only used for debugging

         public Operand(RegisterSpec regSpec, int blockIndex, int ropLabel) {
             this.regSpec = regSpec;
             this.blockIndex = blockIndex;
             this.ropLabel = ropLabel;
         }
     }

     /**
      * Visitor interface for instances of this (outer) class.
      */
     public static interface Visitor {
         public void visitPhiInsn(PhiInsn insn);
     }
 }
	/*
	* Copyright (C) 2007 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	package com.android.dx.ssa;

	import com.android.dx.rop.code.*;
	import com.android.dx.rop.type.Type;
	import com.android.dx.rop.type.TypeBearer;
	import com.android.dx.util.Hex;

	import java.util.ArrayList;
	import java.util.List;

	/**
	* A Phi instruction (magical post-control-flow-merge) instruction
	* in SSA form. Will be converted to moves in predecessor blocks before
	* conversion back to ROP form.
	*/
	public final class PhiInsn extends SsaInsn {
	/**
	* result register. The original result register of the phi insn
	* is needed during the renaming process after the new result
	* register has already been chosen.
	*/
	private final int ropResultReg;

	/**
	* {@code non-null;} operands of the instruction; built up by
	* {@link #addPhiOperand}
	*/
	private final ArrayList<Operand> operands = new ArrayList<Operand>();

	/** {@code null-ok;} source registers; constructed lazily */
	private RegisterSpecList sources;

	/**
	* Constructs a new phi insn with no operands.
	*
	* @param resultReg the result reg for this phi insn
	* @param block block containing this insn.
	*/
	public PhiInsn(RegisterSpec resultReg, SsaBasicBlock block) {
	super(resultReg, block);
	ropResultReg = resultReg.getReg();
	}

	/**
	* Makes a phi insn with a void result type.
	*
	* @param resultReg the result register for this phi insn.
	* @param block block containing this insn.
	*/
	public PhiInsn(final int resultReg, final SsaBasicBlock block) {
	/*
	* The result type here is bogus: The type depends on the
	* operand and will be derived later.
	*/
	super(RegisterSpec.make(resultReg, Type.VOID), block);
	ropResultReg = resultReg;
	}

	/** {@inheritDoc} */
	public PhiInsn clone() {
	throw new UnsupportedOperationException("can't clone phi");
	}

	/**
	* Updates the TypeBearers of all the sources (phi operands) to be
	* the current TypeBearer of the register-defining instruction's result.
	* This is used during phi-type resolution.<p>
	*
	* Note that local association of operands are preserved in this step.
	*
	* @param ssaMeth method that contains this insn
	*/
	public void updateSourcesToDefinitions(SsaMethod ssaMeth) {
	for (Operand o : operands) {
	RegisterSpec def
	= ssaMeth.getDefinitionForRegister(
	o.regSpec.getReg()).getResult();

	o.regSpec = o.regSpec.withType(def.getType());
	}

	sources = null;
	}

	/**
	* Changes the result type. Used during phi type resolution
	*
	* @param type {@code non-null;} new TypeBearer
	* @param local {@code null-ok;} new local info, if available
	*/
	public void changeResultType(TypeBearer type, LocalItem local) {
	setResult(RegisterSpec.makeLocalOptional(
	getResult().getReg(), type, local));
	}

	/**
	* Gets the original rop-form result reg. This is useful during renaming.
	*
	* @return the original rop-form result reg
	*/
	public int getRopResultReg() {
	return ropResultReg;
	}

	/**
	* Adds an operand to this phi instruction.
	*
	* @param registerSpec register spec, including type and reg of operand
	* @param predBlock predecessor block to be associated with this operand
	*/
	public void addPhiOperand(RegisterSpec registerSpec,
	SsaBasicBlock predBlock) {
	operands.add(new Operand(registerSpec, predBlock.getIndex(),
	predBlock.getRopLabel()));

	// Un-cache sources, in case someone has already called getSources().
	sources = null;
	}

	/**
	* Gets the index of the pred block associated with the RegisterSpec
	* at the particular getSources() index.
	*
	* @param sourcesIndex index of source in getSources()
	* @return block index
	*/
	public int predBlockIndexForSourcesIndex(int sourcesIndex) {
	return operands.get(sourcesIndex).blockIndex;
	}

	/**
	* {@inheritDoc}
	*
	* Always returns null for {@code PhiInsn}s.
	*/
	@Override
	public Rop getOpcode() {
	return null;
	}

	/**
	* {@inheritDoc}
	*
	* Always returns null for {@code PhiInsn}s.
	*/
	@Override
	public Insn getOriginalRopInsn() {
	return null;
	}

	/**
	* {@inheritDoc}
	*
	* Always returns false for {@code PhiInsn}s.
	*/
	@Override
	public boolean canThrow() {
	return false;
	}

	/**
	* Gets sources. Constructed lazily from phi operand data structures and
	* then cached.
	*
	* @return {@code non-null;} sources list
	*/
	public RegisterSpecList getSources() {
	if (sources != null) {
	return sources;
	}

	if (operands.size() == 0) {
	// How'd this happen? A phi insn with no operand?
	return RegisterSpecList.EMPTY;
	}

	int szSources = operands.size();
	sources = new RegisterSpecList(szSources);

	for (int i = 0; i < szSources; i++) {
	Operand o = operands.get(i);

	sources.set(i, o.regSpec);
	}

	sources.setImmutable();
	return sources;
	}

	/** {@inheritDoc} */
	@Override
	public boolean isRegASource(int reg) {
	/*
	* Avoid creating a sources list in case it has not already been
	* created.
	*/

	for (Operand o : operands) {
	if (o.regSpec.getReg() == reg) {
	return true;
	}
	}

	return false;
	}

	/**
	* @return true if all operands use the same register
	*/
	public boolean areAllOperandsEqual() {
	if (operands.size() == 0 ) {
	// This should never happen.
	return true;
	}

	int firstReg = operands.get(0).regSpec.getReg();
	for (Operand o : operands) {
	if (firstReg != o.regSpec.getReg()) {
	return false;
	}
	}

	return true;
	}

	/** {@inheritDoc} */
	@Override
	public final void mapSourceRegisters(RegisterMapper mapper) {
	for (Operand o : operands) {
	RegisterSpec old = o.regSpec;
	o.regSpec = mapper.map(old);
	if (old != o.regSpec) {
	getBlock().getParent().onSourceChanged(this, old, o.regSpec);
	}
	}
	sources = null;
	}

	/**
	* Always throws an exeption, since a phi insn may not be
	* converted back to rop form.
	*
	* @return always throws exception
	*/
	@Override
	public Insn toRopInsn() {
	throw new IllegalArgumentException(
	"Cannot convert phi insns to rop form");
	}

	/**
	* Returns the list of predecessor blocks associated with all operands
	* that have {@code reg} as an operand register.
	*
	* @param reg register to look up
	* @param ssaMeth method we're operating on
	* @return list of predecessor blocks, empty if none
	*/
	public List<SsaBasicBlock> predBlocksForReg(int reg, SsaMethod ssaMeth) {
	ArrayList<SsaBasicBlock> ret = new ArrayList<SsaBasicBlock>();

	for (Operand o : operands) {
	if (o.regSpec.getReg() == reg) {
	ret.add(ssaMeth.getBlocks().get(o.blockIndex));
	}
	}

	return ret;
	}

	/** {@inheritDoc} */
	@Override
	public boolean isPhiOrMove() {
	return true;
	}

	/** {@inheritDoc} */
	@Override
	public boolean hasSideEffect() {
	return Optimizer.getPreserveLocals() && getLocalAssignment() != null;
	}

	/** {@inheritDoc} */
	@Override
	public void accept(SsaInsn.Visitor v) {
	v.visitPhiInsn(this);
	}

	/** {@inheritDoc} */
	public String toHuman() {
	return toHumanWithInline(null);
	}

	/**
	* Returns human-readable string for listing dumps. This method
	* allows sub-classes to specify extra text.
	*
	* @param extra {@code null-ok;} the argument to print after the opcode
	* @return human-readable string for listing dumps
	*/
	protected final String toHumanWithInline(String extra) {
	StringBuffer sb = new StringBuffer(80);

	sb.append(SourcePosition.NO_INFO);
	sb.append(": phi");

	if (extra != null) {
	sb.append("(");
	sb.append(extra);
	sb.append(")");
	}

	RegisterSpec result = getResult();

	if (result == null) {
	sb.append(" .");
	} else {
	sb.append(" ");
	sb.append(result.toHuman());
	}

	sb.append(" <-");

	int sz = getSources().size();
	if (sz == 0) {
	sb.append(" .");
	} else {
	for (int i = 0; i < sz; i++) {
	sb.append(" ");
	sb.append(sources.get(i).toHuman()
	+ "[b="
	+ Hex.u2(operands.get(i).ropLabel) + "]");
	}
	}

	return sb.toString();
	}

	/**
	* A single phi operand, consiting of source register and block index
	* for move.
	*/
	private static class Operand {
	public RegisterSpec regSpec;
	public final int blockIndex;
	public final int ropLabel; // only used for debugging

	public Operand(RegisterSpec regSpec, int blockIndex, int ropLabel) {
	this.regSpec = regSpec;
	this.blockIndex = blockIndex;
	this.ropLabel = ropLabel;
	}
	}

	/**
	* Visitor interface for instances of this (outer) class.
	*/
	public static interface Visitor {
	public void visitPhiInsn(PhiInsn insn);
	}
	}