1579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/* 2579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Copyright (C) 2007 The Android Open Source Project 3579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 4579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * you may not use this file except in compliance with the License. 6579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * You may obtain a copy of the License at 7579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 8579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 10579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * See the License for the specific language governing permissions and 14579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * limitations under the License. 15579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 16579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 17579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpackage com.android.dx.rop.code; 18579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 19579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.Bits; 20579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.IntList; 21579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 22579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/** 23579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Code to figure out which local variables are active at which points in 24579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * a method. 25579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 26579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic final class LocalVariableExtractor { 27579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} method being extracted from */ 28579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final RopMethod method; 29579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 30579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} block list for the method */ 31579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final BasicBlockList blocks; 32579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 33579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} result in-progress */ 34579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final LocalVariableInfo resultInfo; 35579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 36579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} work set indicating blocks needing to be processed */ 37579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final int[] workSet; 38579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 39579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 40579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Extracts out all the local variable information from the given method. 41579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 42579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param method {@code non-null;} the method to extract from 43579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} the extracted information 44579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 45579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static LocalVariableInfo extract(RopMethod method) { 46579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson LocalVariableExtractor lve = new LocalVariableExtractor(method); 47579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return lve.doit(); 48579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 49579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 50579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 51579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Constructs an instance. This method is private. Use {@link #extract}. 52579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 53579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param method {@code non-null;} the method to extract from 54579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 55579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private LocalVariableExtractor(RopMethod method) { 56579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (method == null) { 57579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new NullPointerException("method == null"); 58579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 59579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 60579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BasicBlockList blocks = method.getBlocks(); 61579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int maxLabel = blocks.getMaxLabel(); 62579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 63579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.method = method; 64579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.blocks = blocks; 65579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.resultInfo = new LocalVariableInfo(method); 66579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.workSet = Bits.makeBitSet(maxLabel); 67579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 68579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 69579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 70579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Does the extraction. 71579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 72579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} the extracted information 73579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 74579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private LocalVariableInfo doit() { 75579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int label = method.getFirstLabel(); 76579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson label >= 0; 77579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson label = Bits.findFirst(workSet, 0)) { 78579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Bits.clear(workSet, label); 79579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson processBlock(label); 80579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 81579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 82579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson resultInfo.setImmutable(); 83579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return resultInfo; 84579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 85579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 86579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 87579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Processes a single block. 88579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 89579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param label {@code >= 0;} label of the block to process 90579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 91579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void processBlock(int label) { 92579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecSet primaryState = resultInfo.mutableCopyOfStarts(label); 93579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BasicBlock block = blocks.labelToBlock(label); 94579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson InsnList insns = block.getInsns(); 95579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int insnSz = insns.size(); 96579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 97579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 98579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * We may have to treat the last instruction specially: If it 99579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * can (but doesn't always) throw, and the exception can be 100579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * caught within the same method, then we need to use the 101579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * state *before* executing it to be what is merged into 102579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * exception targets. 103579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 104579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson boolean canThrowDuringLastInsn = block.hasExceptionHandlers() && 105579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson (insns.getLast().getResult() != null); 106579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int freezeSecondaryStateAt = insnSz - 1; 107579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecSet secondaryState = primaryState; 108579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 109579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 110579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Iterate over the instructions, adding information for each place 111579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * that the active variable set changes. 112579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 113579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 114579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < insnSz; i++) { 115579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (canThrowDuringLastInsn && (i == freezeSecondaryStateAt)) { 116579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Until this point, primaryState == secondaryState. 117579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primaryState.setImmutable(); 118579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primaryState = primaryState.mutableCopy(); 119579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 120579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 121579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Insn insn = insns.get(i); 122579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec result; 123579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 124579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result = insn.getLocalAssignment(); 125579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 126579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (result == null) { 127579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 128579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * If an assignment assigns over an existing local, make 129579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * sure to mark the local as going out of scope. 130579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 131579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 132579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result = insn.getResult(); 133579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 134579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (result != null 135579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson && primaryState.get(result.getReg()) != null) { 136579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primaryState.remove(primaryState.get(result.getReg())); 137579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 138579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson continue; 139579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 140579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 141579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result = result.withSimpleType(); 142579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 143579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec already = primaryState.get(result); 144579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 145579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * The equals() check ensures we only add new info if 146579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * the instruction causes a change to the set of 147579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * active variables. 148579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 149579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!result.equals(already)) { 150579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 151579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * If this insn represents a local moving from one register 152579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * to another, remove the association between the old register 153579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * and the local. 154579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 155579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec previous 156579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson = primaryState.localItemToSpec(result.getLocalItem()); 157579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 158579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (previous != null 159579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson && (previous.getReg() != result.getReg())) { 160579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 161579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primaryState.remove(previous); 162579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 163579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 164579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson resultInfo.addAssignment(insn, result); 165579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primaryState.put(result); 166579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 167579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 168579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 169579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primaryState.setImmutable(); 170579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 171579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 172579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Merge this state into the start state for each successor, 173579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * and update the work set where required (that is, in cases 174579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * where the start state for a block changes). 175579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 176579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 177579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntList successors = block.getSuccessors(); 178579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int succSz = successors.size(); 179579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int primarySuccessor = block.getPrimarySuccessor(); 180579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 181579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < succSz; i++) { 182579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int succ = successors.get(i); 183579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecSet state = (succ == primarySuccessor) ? 184579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primaryState : secondaryState; 185579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 186579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (resultInfo.mergeStarts(succ, state)) { 187579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Bits.set(workSet, succ); 188579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 189579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 190579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 191579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson} 192