1917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul/* 2917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Copyright (C) 2007 The Android Open Source Project 3917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 4917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Licensed under the Apache License, Version 2.0 (the "License"); 5917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * you may not use this file except in compliance with the License. 6917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * You may obtain a copy of the License at 7917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 8917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * http://www.apache.org/licenses/LICENSE-2.0 9917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 10917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Unless required by applicable law or agreed to in writing, software 11917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * distributed under the License is distributed on an "AS IS" BASIS, 12917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * See the License for the specific language governing permissions and 14917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * limitations under the License. 15917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 16917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 17917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgulpackage com.android.dexgen.rop.code; 18917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 19917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgulimport com.android.dexgen.util.Bits; 20917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgulimport com.android.dexgen.util.IntList; 21917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 22917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul/** 23917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Code to figure out which local variables are active at which points in 24917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * a method. 25917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 26917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgulpublic final class LocalVariableExtractor { 27917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** {@code non-null;} method being extracted from */ 28917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul private final RopMethod method; 29917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 30917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** {@code non-null;} block list for the method */ 31917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul private final BasicBlockList blocks; 32917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 33917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** {@code non-null;} result in-progress */ 34917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul private final LocalVariableInfo resultInfo; 35917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 36917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** {@code non-null;} work set indicating blocks needing to be processed */ 37917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul private final int[] workSet; 38917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 39917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 40917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Extracts out all the local variable information from the given method. 41917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 42917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param method {@code non-null;} the method to extract from 43917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @return {@code non-null;} the extracted information 44917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 45917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public static LocalVariableInfo extract(RopMethod method) { 46917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul LocalVariableExtractor lve = new LocalVariableExtractor(method); 47917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return lve.doit(); 48917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 49917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 50917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 51917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Constructs an instance. This method is private. Use {@link #extract}. 52917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 53917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param method {@code non-null;} the method to extract from 54917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 55917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul private LocalVariableExtractor(RopMethod method) { 56917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (method == null) { 57917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throw new NullPointerException("method == null"); 58917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 59917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 60917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul BasicBlockList blocks = method.getBlocks(); 61917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int maxLabel = blocks.getMaxLabel(); 62917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 63917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul this.method = method; 64917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul this.blocks = blocks; 65917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul this.resultInfo = new LocalVariableInfo(method); 66917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul this.workSet = Bits.makeBitSet(maxLabel); 67917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 68917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 69917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 70917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Does the extraction. 71917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 72917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @return {@code non-null;} the extracted information 73917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 74917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul private LocalVariableInfo doit() { 75917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul for (int label = method.getFirstLabel(); 76917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul label >= 0; 77917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul label = Bits.findFirst(workSet, 0)) { 78917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul Bits.clear(workSet, label); 79917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul processBlock(label); 80917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 81917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 82917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul resultInfo.setImmutable(); 83917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return resultInfo; 84917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 85917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 86917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 87917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Processes a single block. 88917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 89917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param label {@code >= 0;} label of the block to process 90917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 91917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul private void processBlock(int label) { 92917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul RegisterSpecSet primaryState = resultInfo.mutableCopyOfStarts(label); 93917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul BasicBlock block = blocks.labelToBlock(label); 94917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul InsnList insns = block.getInsns(); 95917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int insnSz = insns.size(); 96917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 97917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /* 98917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * We may have to treat the last instruction specially: If it 99917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * can (but doesn't always) throw, and the exception can be 100917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * caught within the same method, then we need to use the 101917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * state *before* executing it to be what is merged into 102917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * exception targets. 103917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 104917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul boolean canThrowDuringLastInsn = block.hasExceptionHandlers() && 105917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul (insns.getLast().getResult() != null); 106917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int freezeSecondaryStateAt = insnSz - 1; 107917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul RegisterSpecSet secondaryState = primaryState; 108917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 109917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /* 110917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Iterate over the instructions, adding information for each place 111917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * that the active variable set changes. 112917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 113917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 114917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul for (int i = 0; i < insnSz; i++) { 115917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (canThrowDuringLastInsn && (i == freezeSecondaryStateAt)) { 116917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul // Until this point, primaryState == secondaryState. 117917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul primaryState.setImmutable(); 118917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul primaryState = primaryState.mutableCopy(); 119917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 120917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 121917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul Insn insn = insns.get(i); 122917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul RegisterSpec result; 123917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 124917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul result = insn.getLocalAssignment(); 125917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 126917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (result == null) { 127917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /* 128917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * If an assignment assigns over an existing local, make 129917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * sure to mark the local as going out of scope. 130917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 131917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 132917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul result = insn.getResult(); 133917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 134917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (result != null 135917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul && primaryState.get(result.getReg()) != null) { 136917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul primaryState.remove(primaryState.get(result.getReg())); 137917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 138917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul continue; 139917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 140917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 141917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul result = result.withSimpleType(); 142917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 143917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul RegisterSpec already = primaryState.get(result); 144917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /* 145917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * The equals() check ensures we only add new info if 146917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * the instruction causes a change to the set of 147917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * active variables. 148917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 149917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (!result.equals(already)) { 150917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /* 151917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * If this insn represents a local moving from one register 152917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * to another, remove the association between the old register 153917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * and the local. 154917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 155917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul RegisterSpec previous 156917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul = primaryState.localItemToSpec(result.getLocalItem()); 157917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 158917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (previous != null 159917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul && (previous.getReg() != result.getReg())) { 160917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 161917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul primaryState.remove(previous); 162917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 163917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 164917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul resultInfo.addAssignment(insn, result); 165917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul primaryState.put(result); 166917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 167917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 168917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 169917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul primaryState.setImmutable(); 170917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 171917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /* 172917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Merge this state into the start state for each successor, 173917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * and update the work set where required (that is, in cases 174917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * where the start state for a block changes). 175917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 176917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 177917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul IntList successors = block.getSuccessors(); 178917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int succSz = successors.size(); 179917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int primarySuccessor = block.getPrimarySuccessor(); 180917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 181917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul for (int i = 0; i < succSz; i++) { 182917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int succ = successors.get(i); 183917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul RegisterSpecSet state = (succ == primarySuccessor) ? 184917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul primaryState : secondaryState; 185917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 186917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (resultInfo.mergeStarts(succ, state)) { 187917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul Bits.set(workSet, succ); 188917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 189917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 190917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 191917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul} 192