1f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 2f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Copyright (C) 2008 The Android Open Source Project 3f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 4f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * you may not use this file except in compliance with the License. 6f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * You may obtain a copy of the License at 7f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 8f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See the License for the specific language governing permissions and 14f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * limitations under the License. 15f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 16f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 17f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpackage com.android.dx.ssa; 18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 19a914f8aeb0729989ad0a3d5dfa8ddcfa6cf0df07jeffhaoimport com.android.dx.rop.code.LocalItem; 20a914f8aeb0729989ad0a3d5dfa8ddcfa6cf0df07jeffhaoimport com.android.dx.rop.code.PlainCstInsn; 21a914f8aeb0729989ad0a3d5dfa8ddcfa6cf0df07jeffhaoimport com.android.dx.rop.code.PlainInsn; 22a914f8aeb0729989ad0a3d5dfa8ddcfa6cf0df07jeffhaoimport com.android.dx.rop.code.RegOps; 23a914f8aeb0729989ad0a3d5dfa8ddcfa6cf0df07jeffhaoimport com.android.dx.rop.code.RegisterSpec; 24a914f8aeb0729989ad0a3d5dfa8ddcfa6cf0df07jeffhaoimport com.android.dx.rop.code.RegisterSpecList; 25a914f8aeb0729989ad0a3d5dfa8ddcfa6cf0df07jeffhaoimport com.android.dx.rop.code.Rop; 26a914f8aeb0729989ad0a3d5dfa8ddcfa6cf0df07jeffhaoimport com.android.dx.rop.code.Rops; 27a914f8aeb0729989ad0a3d5dfa8ddcfa6cf0df07jeffhaoimport com.android.dx.rop.code.SourcePosition; 28a914f8aeb0729989ad0a3d5dfa8ddcfa6cf0df07jeffhaoimport com.android.dx.rop.code.ThrowingCstInsn; 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.cst.Constant; 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.cst.CstString; 314b4413ab3d8de5805276cfcde3d7f535d9f64e85Dan Bornsteinimport com.android.dx.rop.cst.TypedConstant; 324b4413ab3d8de5805276cfcde3d7f535d9f64e85Dan Bornsteinimport com.android.dx.rop.type.StdTypeList; 334b4413ab3d8de5805276cfcde3d7f535d9f64e85Dan Bornsteinimport com.android.dx.rop.type.TypeBearer; 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.ArrayList; 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.Collections; 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.Comparator; 374b4413ab3d8de5805276cfcde3d7f535d9f64e85Dan Bornsteinimport java.util.HashMap; 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.HashSet; 394b4413ab3d8de5805276cfcde3d7f535d9f64e85Dan Bornsteinimport java.util.Map; 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Collects constants that are used more than once at the top of the 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * method block. This increases register usage by about 5% but decreases 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * insn size by about 3%. 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic class ConstCollector { 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** Maximum constants to collect per method. Puts cap on reg use */ 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final int MAX_COLLECTED_CONSTANTS = 5; 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Also collect string consts, although they can throw exceptions. 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This is off now because it just doesn't seem to gain a whole lot. 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * TODO if you turn this on, you must change SsaInsn.hasSideEffect() 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to return false for const-string insns whose exceptions are not 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * caught in the current method. 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static boolean COLLECT_STRINGS = false; 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If true, allow one local var to be involved with a collected const. 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Turned off because it mostly just inserts more moves. 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static boolean COLLECT_ONE_LOCAL = false; 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** method we're processing */ 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final SsaMethod ssaMeth; 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 6999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Processes a method. 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 7199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaMethod {@code non-null;} method to process 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public static void process(SsaMethod ssaMethod) { 7499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project ConstCollector cc = new ConstCollector(ssaMethod); 7599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project cc.run(); 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 7899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** 7999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Constructs an instance. 80de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 8199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaMethod {@code non-null;} method to process 8299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private ConstCollector(SsaMethod ssaMethod) { 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.ssaMeth = ssaMethod; 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Applies the optimization. 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void run() { 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int regSz = ssaMeth.getRegCount(); 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<TypedConstant> constantList 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = getConstsSortedByCountUse(); 95de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int toCollect = Math.min(constantList.size(), MAX_COLLECTED_CONSTANTS); 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock start = ssaMeth.getEntryBlock(); 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Constant to new register containing the constant 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HashMap<TypedConstant, RegisterSpec> newRegs 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = new HashMap<TypedConstant, RegisterSpec> (toCollect); 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < toCollect; i++) { 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project TypedConstant cst = constantList.get(i); 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec result 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = RegisterSpec.make(ssaMeth.makeNewSsaReg(), cst); 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Rop constRop = Rops.opConst(cst); 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (constRop.getBranchingness() == Rop.BRANCH_NONE) { 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project start.addInsnToHead( 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new PlainCstInsn(Rops.opConst(cst), 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SourcePosition.NO_INFO, result, 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.EMPTY, cst)); 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // We need two new basic blocks along with the new insn 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock entryBlock = ssaMeth.getEntryBlock(); 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock successorBlock 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = entryBlock.getPrimarySuccessor(); 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 12299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // Insert a block containing the const insn. 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock constBlock 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = entryBlock.insertNewSuccessor(successorBlock); 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project constBlock.replaceLastInsn( 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new ThrowingCstInsn(constRop, SourcePosition.NO_INFO, 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.EMPTY, 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project StdTypeList.EMPTY, cst)); 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 13199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // Insert a block containing the move-result-pseudo insn. 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock resultBlock 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = constBlock.insertNewSuccessor(successorBlock); 135de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro PlainInsn insn 13699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project = new PlainInsn( 13799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project Rops.opMoveResultPseudo(result.getTypeBearer()), 13899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project SourcePosition.NO_INFO, 13999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project result, RegisterSpecList.EMPTY); 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 14199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project resultBlock.addInsnToHead(insn); 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newRegs.put(cst, result); 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project updateConstUses(newRegs, regSz); 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets all of the collectable constant values used in this method, 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * sorted by most used first. Skips non-collectable consts, such as 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * non-string object constants 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 15599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} list of constants in most-to-least used order 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private ArrayList<TypedConstant> getConstsSortedByCountUse() { 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int regSz = ssaMeth.getRegCount(); 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final HashMap<TypedConstant, Integer> countUses 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = new HashMap<TypedConstant, Integer>(); 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 16399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /* 16499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Each collected constant can be used by just one local 16599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * (used only if COLLECT_ONE_LOCAL is true). 16699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final HashSet<TypedConstant> usedByLocal 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = new HashSet<TypedConstant>(); 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 17099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // Count how many times each const value is used. 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < regSz; i++) { 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn insn = ssaMeth.getDefinitionForRegister(i); 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 174b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao if (insn == null || insn.getOpcode() == null) continue; 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec result = insn.getResult(); 1774b4413ab3d8de5805276cfcde3d7f535d9f64e85Dan Bornstein TypeBearer typeBearer = result.getTypeBearer(); 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!typeBearer.isConstant()) continue; 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project TypedConstant cst = (TypedConstant) typeBearer; 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 183a914f8aeb0729989ad0a3d5dfa8ddcfa6cf0df07jeffhao // Find defining instruction for move-result-pseudo instructions 184a914f8aeb0729989ad0a3d5dfa8ddcfa6cf0df07jeffhao if (insn.getOpcode().getOpcode() == RegOps.MOVE_RESULT_PSEUDO) { 185a914f8aeb0729989ad0a3d5dfa8ddcfa6cf0df07jeffhao int pred = insn.getBlock().getPredecessors().nextSetBit(0); 186a914f8aeb0729989ad0a3d5dfa8ddcfa6cf0df07jeffhao ArrayList<SsaInsn> predInsns; 187a914f8aeb0729989ad0a3d5dfa8ddcfa6cf0df07jeffhao predInsns = ssaMeth.getBlocks().get(pred).getInsns(); 188a914f8aeb0729989ad0a3d5dfa8ddcfa6cf0df07jeffhao insn = predInsns.get(predInsns.size()-1); 189a914f8aeb0729989ad0a3d5dfa8ddcfa6cf0df07jeffhao } 190a914f8aeb0729989ad0a3d5dfa8ddcfa6cf0df07jeffhao 191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn.canThrow()) { 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Don't move anything other than strings -- the risk 19499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * of changing where an exception is thrown is too high. 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!(cst instanceof CstString) || !COLLECT_STRINGS) { 197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 20099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * We can't move any throwable const whose throw will be 201de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * caught, so don't count them. 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn.getBlock().getSuccessors().cardinality() > 1) { 204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 20899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /* 20999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * TODO: Might be nice to try and figure out which local 21099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * wins most when collected. 21199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaMeth.isRegALocal(result)) { 213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!COLLECT_ONE_LOCAL) { 214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (usedByLocal.contains(cst)) { 21799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // Count one local usage only. 218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project usedByLocal.add(cst); 221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 222f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Integer has = countUses.get(cst); 226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (has == null) { 227f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project countUses.put(cst, 1); 228f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 229f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project countUses.put(cst, has + 1); 230f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 23399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // Collect constants that have been reused. 234f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<TypedConstant> constantList = new ArrayList<TypedConstant>(); 2354b4413ab3d8de5805276cfcde3d7f535d9f64e85Dan Bornstein for (Map.Entry<TypedConstant, Integer> entry : countUses.entrySet()) { 2364b4413ab3d8de5805276cfcde3d7f535d9f64e85Dan Bornstein if (entry.getValue() > 1) { 2374b4413ab3d8de5805276cfcde3d7f535d9f64e85Dan Bornstein constantList.add(entry.getKey()); 238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 24199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // Sort by use, with most used at the beginning of the list. 242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Collections.sort(constantList, new Comparator<Constant>() { 243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int compare(Constant a, Constant b) { 244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ret; 245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ret = countUses.get(b) - countUses.get(a); 246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ret == 0) { 248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Provide sorting determinisim for constants with same 250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * usage count. 251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ret = a.compareTo(b); 253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 255f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return ret; 256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2574b4413ab3d8de5805276cfcde3d7f535d9f64e85Dan Bornstein 258a914f8aeb0729989ad0a3d5dfa8ddcfa6cf0df07jeffhao @Override 259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public boolean equals (Object obj) { 260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return obj == this; 261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project }); 26399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 264f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return constantList; 265f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 267f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 268f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Inserts mark-locals if necessary when changing a register. If 26999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * the definition of {@code origReg} is associated with a local 27099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * variable, then insert a mark-local for {@code newReg} just below 27199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * it. We expect the definition of {@code origReg} to ultimately 272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * be removed by the dead code eliminator 273de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 27499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param origReg {@code non-null;} original register 27599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param newReg {@code non-null;} new register that will replace 27699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code origReg} 277f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 27899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private void fixLocalAssignment(RegisterSpec origReg, 27999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project RegisterSpec newReg) { 28099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (SsaInsn use : ssaMeth.getUseListForRegister(origReg.getReg())) { 281f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec localAssignment = use.getLocalAssignment(); 282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (localAssignment == null) { 283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 284f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 285f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 286f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (use.getResult() == null) { 28799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /* 28899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * This is a mark-local. it will be updated when all uses 28999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * are updated. 29099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 293f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 294f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LocalItem local = localAssignment.getLocalItem(); 295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 29699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // Un-associate original use. 297f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project use.setResultLocal(null); 298f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 29999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // Now add a mark-local to the new reg immediately after. 300f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newReg = newReg.withLocalItem(local); 301f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 302f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn newInsn 303f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = SsaInsn.makeFromRop( 304f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new PlainInsn(Rops.opMarkLocal(newReg), 305f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SourcePosition.NO_INFO, null, 306f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.make(newReg)), 307f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project use.getBlock()); 308f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 309f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<SsaInsn> insns = use.getBlock().getInsns(); 310f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 311f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.add(insns.indexOf(use) + 1, newInsn); 312f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 313f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 314f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 315f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 316f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Updates all uses of various consts to use the values in the newly 317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * assigned registers. 318f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 31999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param newRegs {@code non-null;} mapping between constant and new reg 32099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param origRegCount {@code >=0;} original SSA reg count, not including 321f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * newly added constant regs 322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void updateConstUses(HashMap<TypedConstant, RegisterSpec> newRegs, 324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int origRegCount) { 325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 32699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /* 32799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * set of constants associated with a local variable; used 32899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * only if COLLECT_ONE_LOCAL is true. 32999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 330f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final HashSet<TypedConstant> usedByLocal 331f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = new HashSet<TypedConstant>(); 332f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 333f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final ArrayList<SsaInsn>[] useList = ssaMeth.getUseListCopy(); 334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < origRegCount; i++) { 336f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn insn = ssaMeth.getDefinitionForRegister(i); 337f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 338f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn == null) { 339f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 340f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 341f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 342f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final RegisterSpec origReg = insn.getResult(); 343f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project TypeBearer typeBearer = insn.getResult().getTypeBearer(); 344f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 345f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!typeBearer.isConstant()) continue; 346f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 347f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project TypedConstant cst = (TypedConstant) typeBearer; 348f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final RegisterSpec newReg = newRegs.get(cst); 349f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 350f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (newReg == null) { 351f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 352f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 353f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 354f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssaMeth.isRegALocal(origReg)) { 355f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!COLLECT_ONE_LOCAL) { 356de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro continue; 357f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 35899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /* 35999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * TODO: If the same local gets the same cst 36099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * multiple times, it would be nice to reuse the 36199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * register. 36299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 363f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (usedByLocal.contains(cst)) { 364f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 365f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 366f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project usedByLocal.add(cst); 367f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project fixLocalAssignment(origReg, newRegs.get(cst)); 368f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 369f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 370f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 371f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 37299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // maps an original const register to the new collected register 373f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterMapper mapper = new RegisterMapper() { 374f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project @Override 375f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int getNewRegisterCount() { 376f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return ssaMeth.getRegCount(); 377f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 378f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 379f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project @Override 380f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public RegisterSpec map(RegisterSpec registerSpec) { 381f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (registerSpec.getReg() == origReg.getReg()) { 38299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project return newReg.withLocalItem( 38399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project registerSpec.getLocalItem()); 384f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 385f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 386f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return registerSpec; 387f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 388f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project }; 389f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 39099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (SsaInsn use : useList[origReg.getReg()]) { 391f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (use.canThrow() 392f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && use.getBlock().getSuccessors().cardinality() > 1) { 393f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 394f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 395f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project use.mapSourceRegisters(mapper); 396f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 397f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 398f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 399f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 400