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

 /*
  * Copyright (C) 2008 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.LocalItem;
 import com.android.dx.rop.code.PlainCstInsn;
 import com.android.dx.rop.code.PlainInsn;
 import com.android.dx.rop.code.RegOps;
 import com.android.dx.rop.code.RegisterSpec;
 import com.android.dx.rop.code.RegisterSpecList;
 import com.android.dx.rop.code.Rop;
 import com.android.dx.rop.code.Rops;
 import com.android.dx.rop.code.SourcePosition;
 import com.android.dx.rop.code.ThrowingCstInsn;
 import com.android.dx.rop.cst.Constant;
 import com.android.dx.rop.cst.CstString;
 import com.android.dx.rop.cst.TypedConstant;
 import com.android.dx.rop.type.StdTypeList;
 import com.android.dx.rop.type.TypeBearer;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Map;

 /**
  * Collects constants that are used more than once at the top of the
  * method block. This increases register usage by about 5% but decreases
  * insn size by about 3%.
  */
 public class ConstCollector {
     /** Maximum constants to collect per method. Puts cap on reg use */
     private static final int MAX_COLLECTED_CONSTANTS = 5;

     /**
      * Also collect string consts, although they can throw exceptions.
      * This is off now because it just doesn't seem to gain a whole lot.
      * TODO if you turn this on, you must change SsaInsn.hasSideEffect()
      * to return false for const-string insns whose exceptions are not
      * caught in the current method.
      */
     private static boolean COLLECT_STRINGS = false;

     /**
      * If true, allow one local var to be involved with a collected const.
      * Turned off because it mostly just inserts more moves.
      */
     private static boolean COLLECT_ONE_LOCAL = false;

     /** method we're processing */
     private final SsaMethod ssaMeth;

     /**
      * Processes a method.
      *
      * @param ssaMethod {@code non-null;} method to process
      */
     public static void process(SsaMethod ssaMethod) {
         ConstCollector cc = new ConstCollector(ssaMethod);
         cc.run();
     }

     /**
      * Constructs an instance.
      *
      * @param ssaMethod {@code non-null;} method to process
      */
     private ConstCollector(SsaMethod ssaMethod) {
         this.ssaMeth = ssaMethod;
     }

     /**
      * Applies the optimization.
      */
     private void run() {
         int regSz = ssaMeth.getRegCount();

         ArrayList<TypedConstant> constantList
                 = getConstsSortedByCountUse();

         int toCollect = Math.min(constantList.size(), MAX_COLLECTED_CONSTANTS);

         SsaBasicBlock start = ssaMeth.getEntryBlock();

         // Constant to new register containing the constant
         HashMap<TypedConstant, RegisterSpec> newRegs
                 = new HashMap<TypedConstant, RegisterSpec> (toCollect);

         for (int i = 0; i < toCollect; i++) {
             TypedConstant cst = constantList.get(i);
             RegisterSpec result
                     = RegisterSpec.make(ssaMeth.makeNewSsaReg(), cst);

             Rop constRop = Rops.opConst(cst);

             if (constRop.getBranchingness() == Rop.BRANCH_NONE) {
                 start.addInsnToHead(
                         new PlainCstInsn(Rops.opConst(cst),
                                 SourcePosition.NO_INFO, result,
                                 RegisterSpecList.EMPTY, cst));
             } else {
                 // We need two new basic blocks along with the new insn
                 SsaBasicBlock entryBlock = ssaMeth.getEntryBlock();
                 SsaBasicBlock successorBlock
                         = entryBlock.getPrimarySuccessor();

                 // Insert a block containing the const insn.
                 SsaBasicBlock constBlock
                         = entryBlock.insertNewSuccessor(successorBlock);

                 constBlock.replaceLastInsn(
                         new ThrowingCstInsn(constRop, SourcePosition.NO_INFO,
                                 RegisterSpecList.EMPTY,
                                 StdTypeList.EMPTY, cst));

                 // Insert a block containing the move-result-pseudo insn.

                 SsaBasicBlock resultBlock
                         = constBlock.insertNewSuccessor(successorBlock);
                 PlainInsn insn
                     = new PlainInsn(
                             Rops.opMoveResultPseudo(result.getTypeBearer()),
                             SourcePosition.NO_INFO,
                             result, RegisterSpecList.EMPTY);

                 resultBlock.addInsnToHead(insn);
             }

             newRegs.put(cst, result);
         }

         updateConstUses(newRegs, regSz);
     }

     /**
      * Gets all of the collectable constant values used in this method,
      * sorted by most used first. Skips non-collectable consts, such as
      * non-string object constants
      *
      * @return {@code non-null;} list of constants in most-to-least used order
      */
     private ArrayList<TypedConstant> getConstsSortedByCountUse() {
         int regSz = ssaMeth.getRegCount();

         final HashMap<TypedConstant, Integer> countUses
                 = new HashMap<TypedConstant, Integer>();

         /*
          * Each collected constant can be used by just one local
          * (used only if COLLECT_ONE_LOCAL is true).
          */
         final HashSet<TypedConstant> usedByLocal
                 = new HashSet<TypedConstant>();

         // Count how many times each const value is used.
         for (int i = 0; i < regSz; i++) {
             SsaInsn insn = ssaMeth.getDefinitionForRegister(i);

             if (insn == null || insn.getOpcode() == null) continue;

             RegisterSpec result = insn.getResult();
             TypeBearer typeBearer = result.getTypeBearer();

             if (!typeBearer.isConstant()) continue;

             TypedConstant cst = (TypedConstant) typeBearer;

             // Find defining instruction for move-result-pseudo instructions
             if (insn.getOpcode().getOpcode() == RegOps.MOVE_RESULT_PSEUDO) {
                 int pred = insn.getBlock().getPredecessors().nextSetBit(0);
                 ArrayList<SsaInsn> predInsns;
                 predInsns = ssaMeth.getBlocks().get(pred).getInsns();
                 insn = predInsns.get(predInsns.size()-1);
             }

             if (insn.canThrow()) {
                 /*
                  * Don't move anything other than strings -- the risk
                  * of changing where an exception is thrown is too high.
                  */
                 if (!(cst instanceof CstString) || !COLLECT_STRINGS) {
                     continue;
                 }
                 /*
                  * We can't move any throwable const whose throw will be
                  * caught, so don't count them.
                  */
                 if (insn.getBlock().getSuccessors().cardinality() > 1) {
                     continue;
                 }
             }

             /*
              * TODO: Might be nice to try and figure out which local
              * wins most when collected.
              */
             if (ssaMeth.isRegALocal(result)) {
                 if (!COLLECT_ONE_LOCAL) {
                     continue;
                 } else {
                     if (usedByLocal.contains(cst)) {
                         // Count one local usage only.
                         continue;
                     } else {
                         usedByLocal.add(cst);
                     }
                 }
             }

             Integer has = countUses.get(cst);
             if (has == null) {
                 countUses.put(cst, 1);
             } else {
                 countUses.put(cst, has + 1);
             }
         }

         // Collect constants that have been reused.
         ArrayList<TypedConstant> constantList = new ArrayList<TypedConstant>();
         for (Map.Entry<TypedConstant, Integer> entry : countUses.entrySet()) {
             if (entry.getValue() > 1) {
                 constantList.add(entry.getKey());
             }
         }

         // Sort by use, with most used at the beginning of the list.
         Collections.sort(constantList, new Comparator<Constant>() {
             public int compare(Constant a, Constant b) {
                 int ret;
                 ret = countUses.get(b) - countUses.get(a);

                 if (ret == 0) {
                     /*
                      * Provide sorting determinisim for constants with same
                      * usage count.
                      */
                     ret = a.compareTo(b);
                 }

                 return ret;
             }

             @Override
             public boolean equals (Object obj) {
                 return obj == this;
             }
         });

         return constantList;
     }

     /**
      * Inserts mark-locals if necessary when changing a register. If
      * the definition of {@code origReg} is associated with a local
      * variable, then insert a mark-local for {@code newReg} just below
      * it. We expect the definition of  {@code origReg} to ultimately
      * be removed by the dead code eliminator
      *
      * @param origReg {@code non-null;} original register
      * @param newReg {@code non-null;} new register that will replace
      * {@code origReg}
      */
     private void fixLocalAssignment(RegisterSpec origReg,
             RegisterSpec newReg) {
         for (SsaInsn use : ssaMeth.getUseListForRegister(origReg.getReg())) {
             RegisterSpec localAssignment = use.getLocalAssignment();
             if (localAssignment == null) {
                 continue;
             }

             if (use.getResult() == null) {
                 /*
                  * This is a mark-local. it will be updated when all uses
                  * are updated.
                  */
                 continue;
             }

             LocalItem local = localAssignment.getLocalItem();

             // Un-associate original use.
             use.setResultLocal(null);

             // Now add a mark-local to the new reg immediately after.
             newReg = newReg.withLocalItem(local);

             SsaInsn newInsn
                     = SsaInsn.makeFromRop(
                         new PlainInsn(Rops.opMarkLocal(newReg),
                         SourcePosition.NO_INFO, null,
                                 RegisterSpecList.make(newReg)),
                     use.getBlock());

             ArrayList<SsaInsn> insns = use.getBlock().getInsns();

             insns.add(insns.indexOf(use) + 1, newInsn);
         }
     }

     /**
      * Updates all uses of various consts to use the values in the newly
      * assigned registers.
      *
      * @param newRegs {@code non-null;} mapping between constant and new reg
      * @param origRegCount {@code >=0;} original SSA reg count, not including
      * newly added constant regs
      */
     private void updateConstUses(HashMap<TypedConstant, RegisterSpec> newRegs,
             int origRegCount) {

         /*
          * set of constants associated with a local variable; used
          * only if COLLECT_ONE_LOCAL is true.
          */
         final HashSet<TypedConstant> usedByLocal
                 = new HashSet<TypedConstant>();

         final ArrayList<SsaInsn>[] useList = ssaMeth.getUseListCopy();

         for (int i = 0; i < origRegCount; i++) {
             SsaInsn insn = ssaMeth.getDefinitionForRegister(i);

             if (insn == null) {
                 continue;
             }

             final RegisterSpec origReg = insn.getResult();
             TypeBearer typeBearer = insn.getResult().getTypeBearer();

             if (!typeBearer.isConstant()) continue;

             TypedConstant cst = (TypedConstant) typeBearer;
             final RegisterSpec newReg = newRegs.get(cst);

             if (newReg == null) {
                 continue;
             }

             if (ssaMeth.isRegALocal(origReg)) {
                 if (!COLLECT_ONE_LOCAL) {
                     continue;
                 } else {
                     /*
                      * TODO: If the same local gets the same cst
                      * multiple times, it would be nice to reuse the
                      * register.
                      */
                     if (usedByLocal.contains(cst)) {
                         continue;
                     } else {
                         usedByLocal.add(cst);
                         fixLocalAssignment(origReg, newRegs.get(cst));
                     }
                 }
             }

             // maps an original const register to the new collected register
             RegisterMapper mapper = new RegisterMapper() {
                 @Override
                 public int getNewRegisterCount() {
                     return ssaMeth.getRegCount();
                 }

                 @Override
                 public RegisterSpec map(RegisterSpec registerSpec) {
                     if (registerSpec.getReg() == origReg.getReg()) {
                         return newReg.withLocalItem(
                                 registerSpec.getLocalItem());
                     }

                     return registerSpec;
                 }
             };

             for (SsaInsn use : useList[origReg.getReg()]) {
                 if (use.canThrow()
                         && use.getBlock().getSuccessors().cardinality() > 1) {
                     continue;
                 }
                 use.mapSourceRegisters(mapper);
             }
         }
     }
 }
	/*
	* Copyright (C) 2008 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.LocalItem;
	import com.android.dx.rop.code.PlainCstInsn;
	import com.android.dx.rop.code.PlainInsn;
	import com.android.dx.rop.code.RegOps;
	import com.android.dx.rop.code.RegisterSpec;
	import com.android.dx.rop.code.RegisterSpecList;
	import com.android.dx.rop.code.Rop;
	import com.android.dx.rop.code.Rops;
	import com.android.dx.rop.code.SourcePosition;
	import com.android.dx.rop.code.ThrowingCstInsn;
	import com.android.dx.rop.cst.Constant;
	import com.android.dx.rop.cst.CstString;
	import com.android.dx.rop.cst.TypedConstant;
	import com.android.dx.rop.type.StdTypeList;
	import com.android.dx.rop.type.TypeBearer;
	import java.util.ArrayList;
	import java.util.Collections;
	import java.util.Comparator;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.Map;

	/**
	* Collects constants that are used more than once at the top of the
	* method block. This increases register usage by about 5% but decreases
	* insn size by about 3%.
	*/
	public class ConstCollector {
	/** Maximum constants to collect per method. Puts cap on reg use */
	private static final int MAX_COLLECTED_CONSTANTS = 5;

	/**
	* Also collect string consts, although they can throw exceptions.
	* This is off now because it just doesn't seem to gain a whole lot.
	* TODO if you turn this on, you must change SsaInsn.hasSideEffect()
	* to return false for const-string insns whose exceptions are not
	* caught in the current method.
	*/
	private static boolean COLLECT_STRINGS = false;

	/**
	* If true, allow one local var to be involved with a collected const.
	* Turned off because it mostly just inserts more moves.
	*/
	private static boolean COLLECT_ONE_LOCAL = false;

	/** method we're processing */
	private final SsaMethod ssaMeth;

	/**
	* Processes a method.
	*
	* @param ssaMethod {@code non-null;} method to process
	*/
	public static void process(SsaMethod ssaMethod) {
	ConstCollector cc = new ConstCollector(ssaMethod);
	cc.run();
	}

	/**
	* Constructs an instance.
	*
	* @param ssaMethod {@code non-null;} method to process
	*/
	private ConstCollector(SsaMethod ssaMethod) {
	this.ssaMeth = ssaMethod;
	}

	/**
	* Applies the optimization.
	*/
	private void run() {
	int regSz = ssaMeth.getRegCount();

	ArrayList<TypedConstant> constantList
	= getConstsSortedByCountUse();

	int toCollect = Math.min(constantList.size(), MAX_COLLECTED_CONSTANTS);

	SsaBasicBlock start = ssaMeth.getEntryBlock();

	// Constant to new register containing the constant
	HashMap<TypedConstant, RegisterSpec> newRegs
	= new HashMap<TypedConstant, RegisterSpec> (toCollect);

	for (int i = 0; i < toCollect; i++) {
	TypedConstant cst = constantList.get(i);
	RegisterSpec result
	= RegisterSpec.make(ssaMeth.makeNewSsaReg(), cst);

	Rop constRop = Rops.opConst(cst);

	if (constRop.getBranchingness() == Rop.BRANCH_NONE) {
	start.addInsnToHead(
	new PlainCstInsn(Rops.opConst(cst),
	SourcePosition.NO_INFO, result,
	RegisterSpecList.EMPTY, cst));
	} else {
	// We need two new basic blocks along with the new insn
	SsaBasicBlock entryBlock = ssaMeth.getEntryBlock();
	SsaBasicBlock successorBlock
	= entryBlock.getPrimarySuccessor();

	// Insert a block containing the const insn.
	SsaBasicBlock constBlock
	= entryBlock.insertNewSuccessor(successorBlock);

	constBlock.replaceLastInsn(
	new ThrowingCstInsn(constRop, SourcePosition.NO_INFO,
	RegisterSpecList.EMPTY,
	StdTypeList.EMPTY, cst));

	// Insert a block containing the move-result-pseudo insn.

	SsaBasicBlock resultBlock
	= constBlock.insertNewSuccessor(successorBlock);
	PlainInsn insn
	= new PlainInsn(
	Rops.opMoveResultPseudo(result.getTypeBearer()),
	SourcePosition.NO_INFO,
	result, RegisterSpecList.EMPTY);

	resultBlock.addInsnToHead(insn);
	}

	newRegs.put(cst, result);
	}

	updateConstUses(newRegs, regSz);
	}

	/**
	* Gets all of the collectable constant values used in this method,
	* sorted by most used first. Skips non-collectable consts, such as
	* non-string object constants
	*
	* @return {@code non-null;} list of constants in most-to-least used order
	*/
	private ArrayList<TypedConstant> getConstsSortedByCountUse() {
	int regSz = ssaMeth.getRegCount();

	final HashMap<TypedConstant, Integer> countUses
	= new HashMap<TypedConstant, Integer>();

	/*
	* Each collected constant can be used by just one local
	* (used only if COLLECT_ONE_LOCAL is true).
	*/
	final HashSet<TypedConstant> usedByLocal
	= new HashSet<TypedConstant>();

	// Count how many times each const value is used.
	for (int i = 0; i < regSz; i++) {
	SsaInsn insn = ssaMeth.getDefinitionForRegister(i);

	if (insn == null \|\| insn.getOpcode() == null) continue;

	RegisterSpec result = insn.getResult();
	TypeBearer typeBearer = result.getTypeBearer();

	if (!typeBearer.isConstant()) continue;

	TypedConstant cst = (TypedConstant) typeBearer;

	// Find defining instruction for move-result-pseudo instructions
	if (insn.getOpcode().getOpcode() == RegOps.MOVE_RESULT_PSEUDO) {
	int pred = insn.getBlock().getPredecessors().nextSetBit(0);
	ArrayList<SsaInsn> predInsns;
	predInsns = ssaMeth.getBlocks().get(pred).getInsns();
	insn = predInsns.get(predInsns.size()-1);
	}

	if (insn.canThrow()) {
	/*
	* Don't move anything other than strings -- the risk
	* of changing where an exception is thrown is too high.
	*/
	if (!(cst instanceof CstString) \|\| !COLLECT_STRINGS) {
	continue;
	}
	/*
	* We can't move any throwable const whose throw will be
	* caught, so don't count them.
	*/
	if (insn.getBlock().getSuccessors().cardinality() > 1) {
	continue;
	}
	}

	/*
	* TODO: Might be nice to try and figure out which local
	* wins most when collected.
	*/
	if (ssaMeth.isRegALocal(result)) {
	if (!COLLECT_ONE_LOCAL) {
	continue;
	} else {
	if (usedByLocal.contains(cst)) {
	// Count one local usage only.
	continue;
	} else {
	usedByLocal.add(cst);
	}
	}
	}

	Integer has = countUses.get(cst);
	if (has == null) {
	countUses.put(cst, 1);
	} else {
	countUses.put(cst, has + 1);
	}
	}

	// Collect constants that have been reused.
	ArrayList<TypedConstant> constantList = new ArrayList<TypedConstant>();
	for (Map.Entry<TypedConstant, Integer> entry : countUses.entrySet()) {
	if (entry.getValue() > 1) {
	constantList.add(entry.getKey());
	}
	}

	// Sort by use, with most used at the beginning of the list.
	Collections.sort(constantList, new Comparator<Constant>() {
	public int compare(Constant a, Constant b) {
	int ret;
	ret = countUses.get(b) - countUses.get(a);

	if (ret == 0) {
	/*
	* Provide sorting determinisim for constants with same
	* usage count.
	*/
	ret = a.compareTo(b);
	}

	return ret;
	}

	@Override
	public boolean equals (Object obj) {
	return obj == this;
	}
	});

	return constantList;
	}

	/**
	* Inserts mark-locals if necessary when changing a register. If
	* the definition of {@code origReg} is associated with a local
	* variable, then insert a mark-local for {@code newReg} just below
	* it. We expect the definition of {@code origReg} to ultimately
	* be removed by the dead code eliminator
	*
	* @param origReg {@code non-null;} original register
	* @param newReg {@code non-null;} new register that will replace
	* {@code origReg}
	*/
	private void fixLocalAssignment(RegisterSpec origReg,
	RegisterSpec newReg) {
	for (SsaInsn use : ssaMeth.getUseListForRegister(origReg.getReg())) {
	RegisterSpec localAssignment = use.getLocalAssignment();
	if (localAssignment == null) {
	continue;
	}

	if (use.getResult() == null) {
	/*
	* This is a mark-local. it will be updated when all uses
	* are updated.
	*/
	continue;
	}

	LocalItem local = localAssignment.getLocalItem();

	// Un-associate original use.
	use.setResultLocal(null);

	// Now add a mark-local to the new reg immediately after.
	newReg = newReg.withLocalItem(local);

	SsaInsn newInsn
	= SsaInsn.makeFromRop(
	new PlainInsn(Rops.opMarkLocal(newReg),
	SourcePosition.NO_INFO, null,
	RegisterSpecList.make(newReg)),
	use.getBlock());

	ArrayList<SsaInsn> insns = use.getBlock().getInsns();

	insns.add(insns.indexOf(use) + 1, newInsn);
	}
	}

	/**
	* Updates all uses of various consts to use the values in the newly
	* assigned registers.
	*
	* @param newRegs {@code non-null;} mapping between constant and new reg
	* @param origRegCount {@code >=0;} original SSA reg count, not including
	* newly added constant regs
	*/
	private void updateConstUses(HashMap<TypedConstant, RegisterSpec> newRegs,
	int origRegCount) {

	/*
	* set of constants associated with a local variable; used
	* only if COLLECT_ONE_LOCAL is true.
	*/
	final HashSet<TypedConstant> usedByLocal
	= new HashSet<TypedConstant>();

	final ArrayList<SsaInsn>[] useList = ssaMeth.getUseListCopy();

	for (int i = 0; i < origRegCount; i++) {
	SsaInsn insn = ssaMeth.getDefinitionForRegister(i);

	if (insn == null) {
	continue;
	}

	final RegisterSpec origReg = insn.getResult();
	TypeBearer typeBearer = insn.getResult().getTypeBearer();

	if (!typeBearer.isConstant()) continue;

	TypedConstant cst = (TypedConstant) typeBearer;
	final RegisterSpec newReg = newRegs.get(cst);

	if (newReg == null) {
	continue;
	}

	if (ssaMeth.isRegALocal(origReg)) {
	if (!COLLECT_ONE_LOCAL) {
	continue;
	} else {
	/*
	* TODO: If the same local gets the same cst
	* multiple times, it would be nice to reuse the
	* register.
	*/
	if (usedByLocal.contains(cst)) {
	continue;
	} else {
	usedByLocal.add(cst);
	fixLocalAssignment(origReg, newRegs.get(cst));
	}
	}
	}

	// maps an original const register to the new collected register
	RegisterMapper mapper = new RegisterMapper() {
	@Override
	public int getNewRegisterCount() {
	return ssaMeth.getRegCount();
	}

	@Override
	public RegisterSpec map(RegisterSpec registerSpec) {
	if (registerSpec.getReg() == origReg.getReg()) {
	return newReg.withLocalItem(
	registerSpec.getLocalItem());
	}

	return registerSpec;
	}
	};

	for (SsaInsn use : useList[origReg.getReg()]) {
	if (use.canThrow()
	&& use.getBlock().getSuccessors().cardinality() > 1) {
	continue;
	}
	use.mapSourceRegisters(mapper);
	}
	}
	}
	}