100fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com/* 200fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * [The "BSD licence"] 300fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * Copyright (c) 2010 Ben Gruver (JesusFreke) 400fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * All rights reserved. 500fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * 600fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * Redistribution and use in source and binary forms, with or without 700fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * modification, are permitted provided that the following conditions 800fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * are met: 900fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * 1. Redistributions of source code must retain the above copyright 1000fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * notice, this list of conditions and the following disclaimer. 1100fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * 2. Redistributions in binary form must reproduce the above copyright 1200fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * notice, this list of conditions and the following disclaimer in the 1300fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * documentation and/or other materials provided with the distribution. 1400fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * 3. The name of the author may not be used to endorse or promote products 1500fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * derived from this software without specific prior written permission. 1600fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * 1700fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 1800fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 1900fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 2000fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 2100fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 2200fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2300fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2400fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2500fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 2600fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2700fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com */ 2800fc68adf2e39aeb9fed35293f2576bbe729ec4bJesusFreke@JesusFreke.com 29d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.compackage org.jf.dexlib.Code.Analysis; 30d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com 31fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.comimport org.jf.dexlib.Code.*; 32a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.comimport org.jf.dexlib.Item; 33a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.comimport org.jf.dexlib.ItemType; 34a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.comimport org.jf.dexlib.MethodIdItem; 35fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.comimport org.jf.dexlib.Util.ExceptionWithContext; 36d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com 370c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.comimport java.util.*; 38d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com 390c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.compublic class AnalyzedInstruction implements Comparable<AnalyzedInstruction> { 40d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com /** 41d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com * The actual instruction 42d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com */ 430c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com protected Instruction instruction; 44d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com 45d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com /** 46fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com * The index of the instruction, where the first instruction in the method is at index 0, and so on 47d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com */ 48fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com protected final int instructionIndex; 49d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com 50d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com /** 51d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com * Instructions that can pass on execution to this one during normal execution 52d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com */ 530c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com protected final TreeSet<AnalyzedInstruction> predecessors = new TreeSet<AnalyzedInstruction>(); 54d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com 55d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com /** 56d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com * Instructions that can execution could pass on to next during normal execution 57d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com */ 58fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com protected final LinkedList<AnalyzedInstruction> successors = new LinkedList<AnalyzedInstruction>(); 59fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com 60fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com /** 610c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com * This contains the register types *before* the instruction has executed 620c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com */ 630c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com protected final RegisterType[] preRegisterMap; 640c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com 650c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com /** 66fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com * This contains the register types *after* the instruction has executed 67fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com */ 68fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com protected final RegisterType[] postRegisterMap; 69d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com 70d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com /** 710c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com * When deodexing, we might need to deodex this instruction multiple times, when we merge in new register 720c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com * information. When this happens, we need to restore the original (odexed) instruction, so we can deodex it again 730c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com */ 740c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com protected final Instruction originalInstruction; 750c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com 760c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com /** 77e01409c11f10de58a47df9bc02c6c715b75c6289JesusFreke@JesusFreke.com * An analyzed instruction's "deadness" is set during analysis (i.e. MethodAnalyzer.analyzer()). A dead instruction 78e01409c11f10de58a47df9bc02c6c715b75c6289JesusFreke@JesusFreke.com * is one that the analyzer never reaches. This occurs either with natural "dead code" - code that simply has no 79e01409c11f10de58a47df9bc02c6c715b75c6289JesusFreke@JesusFreke.com * code path that can ever reach it, or code that follows an odexed instruction that can't be deodexed. 80d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com */ 81d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com protected boolean dead = false; 82d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com 83fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com public AnalyzedInstruction(Instruction instruction, int instructionIndex, int registerCount) { 84d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com this.instruction = instruction; 850c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com this.originalInstruction = instruction; 86fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com this.instructionIndex = instructionIndex; 87fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com this.postRegisterMap = new RegisterType[registerCount]; 880c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com this.preRegisterMap = new RegisterType[registerCount]; 897e24a9f010eeeff54f7ca0cb589a75cc251fabddJesusFreke@JesusFreke.com RegisterType unknown = RegisterType.getRegisterType(RegisterType.Category.Unknown, null); 907e24a9f010eeeff54f7ca0cb589a75cc251fabddJesusFreke@JesusFreke.com for (int i=0; i<registerCount; i++) { 910c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com preRegisterMap[i] = unknown; 927e24a9f010eeeff54f7ca0cb589a75cc251fabddJesusFreke@JesusFreke.com postRegisterMap[i] = unknown; 937e24a9f010eeeff54f7ca0cb589a75cc251fabddJesusFreke@JesusFreke.com } 94d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com } 95d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com 96fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com public int getInstructionIndex() { 97fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com return instructionIndex; 98d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com } 99d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com 1007e24a9f010eeeff54f7ca0cb589a75cc251fabddJesusFreke@JesusFreke.com public int getPredecessorCount() { 1017e24a9f010eeeff54f7ca0cb589a75cc251fabddJesusFreke@JesusFreke.com return predecessors.size(); 1027e24a9f010eeeff54f7ca0cb589a75cc251fabddJesusFreke@JesusFreke.com } 1037e24a9f010eeeff54f7ca0cb589a75cc251fabddJesusFreke@JesusFreke.com 1040c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com public SortedSet<AnalyzedInstruction> getPredecessors() { 1050c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com return Collections.unmodifiableSortedSet(predecessors); 1061c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com } 1071c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com 1080c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com protected boolean addPredecessor(AnalyzedInstruction predecessor) { 1090c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com return predecessors.add(predecessor); 1100c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com } 1111c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com 1120c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com protected void addSuccessor(AnalyzedInstruction successor) { 1130c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com successors.add(successor); 1141c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com } 1151c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com 1160c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com protected void setDeodexedInstruction(Instruction instruction) { 1170c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com assert originalInstruction.opcode.odexOnly(); 1180c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com this.instruction = instruction; 119d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com } 120d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com 1210c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com protected void restoreOdexedInstruction() { 1220c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com assert originalInstruction.opcode.odexOnly(); 1230c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com instruction = originalInstruction; 124d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com } 125fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com 1261c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com public int getSuccessorCount() { 1271c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com return successors.size(); 1281c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com } 1291c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com 1301c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com public List<AnalyzedInstruction> getSuccesors() { 1311c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com return Collections.unmodifiableList(successors); 1321c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com } 1331c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com 1340c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com public Instruction getInstruction() { 1350c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com return instruction; 1360c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com } 1370c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com 1380c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com public Instruction getOriginalInstruction() { 1390c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com return originalInstruction; 1400c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com } 1410c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com 1420c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com public boolean isDead() { 1430c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com return dead; 1440c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com } 1450c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com 1461c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com /** 1471c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com * Is this instruction a "beginning instruction". A beginning instruction is defined to be an instruction 1481c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com * that can be the first successfully executed instruction in the method. The first instruction is always a 1491c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com * beginning instruction. If the first instruction can throw an exception, and is covered by a try block, then 1501c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com * the first instruction of any exception handler for that try block is also a beginning instruction. And likewise, 1511c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com * if any of those instructions can throw an exception and are covered by try blocks, the first instruction of the 1521c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com * corresponding exception handler is a beginning instruction, etc. 1530c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com * 1540c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com * To determine this, we simply check if the first predecessor is the fake "StartOfMethod" instruction, which has 1550c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com * an instruction index of -1. 1561c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com * @return a boolean value indicating whether this instruction is a beginning instruction 1571c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com */ 1581c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com public boolean isBeginningInstruction() { 159ef24b31c9872b24f60c88bdae9b2d8c93eb36feeJesusFreke@JesusFreke.com //if this instruction has no predecessors, it is either the fake "StartOfMethod" instruction or it is an 160ef24b31c9872b24f60c88bdae9b2d8c93eb36feeJesusFreke@JesusFreke.com //unreachable instruction. 1611c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com if (predecessors.size() == 0) { 1621c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com return false; 1631c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com } 1641c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com 1650c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com if (predecessors.first().instructionIndex == -1) { 1661c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com return true; 1671c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com } 1681c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com return false; 1691c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com } 1701c56c7e7507dc24ae1ed2f693c793d94df814c76JesusFreke@JesusFreke.com 171fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com /* 1720c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com * Merges the given register type into the specified pre-instruction register, and also sets the post-instruction 1730c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com * register type accordingly if it isn't a destination register for this instruction 174fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com * @param registerNumber Which register to set 1750c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com * @param registerType The register type 1760c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com * @returns true If the post-instruction register type was changed. This might be false if either the specified 1770c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com * register is a destination register for this instruction, or if the pre-instruction register type didn't change 1780c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com * after merging in the given register type 179fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com */ 1800c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com protected boolean mergeRegister(int registerNumber, RegisterType registerType, BitSet verifiedInstructions) { 181fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com assert registerNumber >= 0 && registerNumber < postRegisterMap.length; 182fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com assert registerType != null; 183fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com 1840c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com RegisterType oldRegisterType = preRegisterMap[registerNumber]; 1850c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com RegisterType mergedRegisterType = oldRegisterType.merge(registerType); 1860c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com 1870c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com if (mergedRegisterType == oldRegisterType) { 188fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com return false; 189fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com } 190fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com 1910c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com preRegisterMap[registerNumber] = mergedRegisterType; 1920c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com verifiedInstructions.clear(instructionIndex); 1930c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com 1940c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com if (!setsRegister(registerNumber)) { 1950c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com postRegisterMap[registerNumber] = mergedRegisterType; 1960c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com return true; 1970c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com } 1980c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com 1990c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com return false; 200fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com } 201fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com 2020c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com /** 2030c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com * Iterates over the predecessors of this instruction, and merges all the post-instruction register types for the 2040c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com * given register. Any dead, unreachable, or odexed predecessor is ignored 205e9b722eab0b0932be59cb99c8c6f403b00abad6fJesusFreke@JesusFreke.com * @param registerNumber the register number 2060c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com * @return The register type resulting from merging the post-instruction register types from all predecessors 2070c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com */ 2080c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com protected RegisterType mergePreRegisterTypeFromPredecessors(int registerNumber) { 209fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com RegisterType mergedRegisterType = null; 210fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com for (AnalyzedInstruction predecessor: predecessors) { 211fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com RegisterType predecessorRegisterType = predecessor.postRegisterMap[registerNumber]; 212fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com assert predecessorRegisterType != null; 213fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com mergedRegisterType = predecessorRegisterType.merge(mergedRegisterType); 214fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com } 215fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com return mergedRegisterType; 216fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com } 217fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com 2180c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com /* 2190c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com * Sets the "post-instruction" register type as indicated. 2200c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com * @param registerNumber Which register to set 2210c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com * @param registerType The "post-instruction" register type 2220c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com * @returns true if the given register type is different than the existing post-instruction register type 2230c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com */ 2240c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com protected boolean setPostRegisterType(int registerNumber, RegisterType registerType) { 2250c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com assert registerNumber >= 0 && registerNumber < postRegisterMap.length; 2260c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com assert registerType != null; 2270c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com 2280c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com RegisterType oldRegisterType = postRegisterMap[registerNumber]; 2290c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com if (oldRegisterType == registerType) { 2300c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com return false; 2310c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com } 2320c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com 2330c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com postRegisterMap[registerNumber] = registerType; 2340c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com return true; 2350c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com } 2360c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com 2370c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com 238a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com protected boolean isInvokeInit() { 2399e78b6b0216638032a180ac1768a70643652bb76Ben Gruver if (instruction == null || !instruction.opcode.canInitializeReference()) { 240a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com return false; 241a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com } 242a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com 24389e1413ef3d2438f7126b2c55f6f57d62361e775JesusFreke@JesusFreke.com //TODO: check access flags instead of name? 24489e1413ef3d2438f7126b2c55f6f57d62361e775JesusFreke@JesusFreke.com 245a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com InstructionWithReference instruction = (InstructionWithReference)this.instruction; 246a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com Item item = instruction.getReferencedItem(); 247a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com assert item.getItemType() == ItemType.TYPE_METHOD_ID_ITEM; 248a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com MethodIdItem method = (MethodIdItem)item; 249a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com 2507e24a9f010eeeff54f7ca0cb589a75cc251fabddJesusFreke@JesusFreke.com if (!method.getMethodName().getStringValue().equals("<init>")) { 251a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com return false; 252a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com } 253a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com 254a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com return true; 255a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com } 256a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com 257fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com public boolean setsRegister() { 258fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com return instruction.opcode.setsRegister(); 259fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com } 260fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com 261fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com public boolean setsWideRegister() { 262fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com return instruction.opcode.setsWideRegister(); 263fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com } 264fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com 265fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com public boolean setsRegister(int registerNumber) { 266a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com //When constructing a new object, the register type will be an uninitialized reference after the new-instance 267a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com //instruction, but becomes an initialized reference once the <init> method is called. So even though invoke 268a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com //instructions don't normally change any registers, calling an <init> method will change the type of its 269a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com //object register. If the uninitialized reference has been copied to other registers, they will be initialized 270a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com //as well, so we need to check for that too 271a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com if (isInvokeInit()) { 272c9be5e13034da9827b5598a6257376164745b827JesusFreke@JesusFreke.com int destinationRegister; 273c9be5e13034da9827b5598a6257376164745b827JesusFreke@JesusFreke.com if (instruction instanceof FiveRegisterInstruction) { 274c9be5e13034da9827b5598a6257376164745b827JesusFreke@JesusFreke.com destinationRegister = ((FiveRegisterInstruction)instruction).getRegisterD(); 275c9be5e13034da9827b5598a6257376164745b827JesusFreke@JesusFreke.com } else { 276c9be5e13034da9827b5598a6257376164745b827JesusFreke@JesusFreke.com assert instruction instanceof RegisterRangeInstruction; 277c9be5e13034da9827b5598a6257376164745b827JesusFreke@JesusFreke.com RegisterRangeInstruction rangeInstruction = (RegisterRangeInstruction)instruction; 278c9be5e13034da9827b5598a6257376164745b827JesusFreke@JesusFreke.com assert rangeInstruction.getRegCount() > 0; 279c9be5e13034da9827b5598a6257376164745b827JesusFreke@JesusFreke.com destinationRegister = rangeInstruction.getStartRegister(); 280c9be5e13034da9827b5598a6257376164745b827JesusFreke@JesusFreke.com } 281c9be5e13034da9827b5598a6257376164745b827JesusFreke@JesusFreke.com 282a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com if (registerNumber == destinationRegister) { 283a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com return true; 284a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com } 2850c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com RegisterType preInstructionDestRegisterType = getPreInstructionRegisterType(registerNumber); 286c9be5e13034da9827b5598a6257376164745b827JesusFreke@JesusFreke.com if (preInstructionDestRegisterType.category != RegisterType.Category.UninitRef && 287c9be5e13034da9827b5598a6257376164745b827JesusFreke@JesusFreke.com preInstructionDestRegisterType.category != RegisterType.Category.UninitThis) { 288c9be5e13034da9827b5598a6257376164745b827JesusFreke@JesusFreke.com 289a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com return false; 290a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com } 291a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com //check if the uninit ref has been copied to another register 2920c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com if (getPreInstructionRegisterType(registerNumber) == preInstructionDestRegisterType) { 293a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com return true; 294a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com } 295a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com return false; 296a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com } 297a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com 298fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com if (!setsRegister()) { 299fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com return false; 300fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com } 301fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com int destinationRegister = getDestinationRegister(); 302a0314c265e76426e3e05e615cc713cf36c78cb85JesusFreke@JesusFreke.com 303fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com if (registerNumber == destinationRegister) { 304fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com return true; 305fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com } 306fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com if (setsWideRegister() && registerNumber == (destinationRegister + 1)) { 307fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com return true; 308fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com } 309fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com return false; 310fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com } 311fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com 312fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com public int getDestinationRegister() { 313fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com if (!this.instruction.opcode.setsRegister()) { 314fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com throw new ExceptionWithContext("Cannot call getDestinationRegister() for an instruction that doesn't " + 315fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com "store a value"); 316fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com } 317fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com return ((SingleRegisterInstruction)instruction).getRegisterA(); 318fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com } 319fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com 3207e24a9f010eeeff54f7ca0cb589a75cc251fabddJesusFreke@JesusFreke.com public int getRegisterCount() { 3217e24a9f010eeeff54f7ca0cb589a75cc251fabddJesusFreke@JesusFreke.com return postRegisterMap.length; 3227e24a9f010eeeff54f7ca0cb589a75cc251fabddJesusFreke@JesusFreke.com } 3237e24a9f010eeeff54f7ca0cb589a75cc251fabddJesusFreke@JesusFreke.com 3247e24a9f010eeeff54f7ca0cb589a75cc251fabddJesusFreke@JesusFreke.com public RegisterType getPostInstructionRegisterType(int registerNumber) { 3257e24a9f010eeeff54f7ca0cb589a75cc251fabddJesusFreke@JesusFreke.com return postRegisterMap[registerNumber]; 3267e24a9f010eeeff54f7ca0cb589a75cc251fabddJesusFreke@JesusFreke.com } 3277e24a9f010eeeff54f7ca0cb589a75cc251fabddJesusFreke@JesusFreke.com 328fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com public RegisterType getPreInstructionRegisterType(int registerNumber) { 3290c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com return preRegisterMap[registerNumber]; 3300c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com } 331fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com 3320c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com public int compareTo(AnalyzedInstruction analyzedInstruction) { 3330c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com //TODO: out of curiosity, check the disassembly of this to see if it retrieves the value of analyzedInstruction.instructionIndex for every access. It should, because the field is final. What about if we set the field to non-final? 3340c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com if (instructionIndex < analyzedInstruction.instructionIndex) { 3350c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com return -1; 3360c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com } else if (instructionIndex == analyzedInstruction.instructionIndex) { 3370c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com return 0; 338fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com } else { 3390c65e0f4f54ead8fd2832c954d516367b3556ae3JesusFreke@JesusFreke.com return 1; 340fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com } 341fffb29fd9d67ba1396bd2999de4f0d9a44b79837JesusFreke@JesusFreke.com } 342d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com} 343d27ca7f7a61cfbe60e1c490bf645257d7d59fd39JesusFreke@JesusFreke.com 344