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.ssa; 18579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 19579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RegisterSpecSet; 20579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RegisterSpec; 21579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.IntList; 22579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 23579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.ArrayList; 24579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.BitSet; 25579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.List; 26579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 27579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/** 28579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Code to figure out which local variables are active at which points in 29579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * a method. Stolen and retrofitted from 30579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * com.android.dx.rop.code.LocalVariableExtractor 31579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 32579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * TODO remove this. Allow Rop-form LocalVariableInfo to be passed in, 33579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * converted, and adapted through edge-splitting. 34579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 35579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic class LocalVariableExtractor { 36579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} method being extracted from */ 37579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final SsaMethod method; 38579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 39579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} block list for the method */ 40579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final ArrayList<SsaBasicBlock> blocks; 41579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 42579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} result in-progress */ 43579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final LocalVariableInfo resultInfo; 44579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 45579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} work set indicating blocks needing to be processed */ 46579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final BitSet workSet; 47579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 48579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 49579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Extracts out all the local variable information from the given method. 50579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 51579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param method {@code non-null;} the method to extract from 52579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} the extracted information 53579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 54579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static LocalVariableInfo extract(SsaMethod method) { 55579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson LocalVariableExtractor lve = new LocalVariableExtractor(method); 56579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return lve.doit(); 57579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 58579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 59579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 60579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Constructs an instance. This method is private. Use {@link #extract}. 61579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 62579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param method {@code non-null;} the method to extract from 63579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 64579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private LocalVariableExtractor(SsaMethod method) { 65579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (method == null) { 66579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new NullPointerException("method == null"); 67579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 68579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 69579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<SsaBasicBlock> blocks = method.getBlocks(); 70579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 71579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.method = method; 72579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.blocks = blocks; 73579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.resultInfo = new LocalVariableInfo(method); 74579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.workSet = new BitSet(blocks.size()); 75579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 76579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 77579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 78579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Does the extraction. 79579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 80579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} the extracted information 81579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 82579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private LocalVariableInfo doit() { 83579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 84579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson //FIXME why is this needed here? 85579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (method.getRegCount() > 0 ) { 86579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int bi = method.getEntryBlockIndex(); 87579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson bi >= 0; 88579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson bi = workSet.nextSetBit(0)) { 89579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson workSet.clear(bi); 90579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson processBlock(bi); 91579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 92579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 93579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 94579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson resultInfo.setImmutable(); 95579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return resultInfo; 96579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 97579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 98579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 99579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Processes a single block. 100579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 101579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param blockIndex {@code >= 0;} block index of the block to process 102579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 103579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void processBlock(int blockIndex) { 104579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecSet primaryState 105579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson = resultInfo.mutableCopyOfStarts(blockIndex); 106579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock block = blocks.get(blockIndex); 107579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson List<SsaInsn> insns = block.getInsns(); 108579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int insnSz = insns.size(); 109579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 110579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // The exit block has no insns and no successors 111579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (blockIndex == method.getExitBlockIndex()) { 112579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return; 113579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 114579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 115579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 116579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * We may have to treat the last instruction specially: If it 117579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * can (but doesn't always) throw, and the exception can be 118579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * caught within the same method, then we need to use the 119579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * state *before* executing it to be what is merged into 120579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * exception targets. 121579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 122579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn lastInsn = insns.get(insnSz - 1); 123579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson boolean hasExceptionHandlers 124579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson = lastInsn.getOriginalRopInsn().getCatches().size() !=0 ; 125579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson boolean canThrowDuringLastInsn = hasExceptionHandlers 126579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson && (lastInsn.getResult() != null); 127579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int freezeSecondaryStateAt = insnSz - 1; 128579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecSet secondaryState = primaryState; 129579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 130579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 131579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Iterate over the instructions, adding information for each place 132579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * that the active variable set changes. 133579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 134579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 135579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < insnSz; i++) { 136579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (canThrowDuringLastInsn && (i == freezeSecondaryStateAt)) { 137579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Until this point, primaryState == secondaryState. 138579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primaryState.setImmutable(); 139579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primaryState = primaryState.mutableCopy(); 140579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 141579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 142579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn insn = insns.get(i); 143579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec result; 144579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 145579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result = insn.getLocalAssignment(); 146579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 147579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (result == null) { 148579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // We may be nuking an existing local 149579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 150579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result = insn.getResult(); 151579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 152579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (result != null && primaryState.get(result.getReg()) != null) { 153579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primaryState.remove(primaryState.get(result.getReg())); 154579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 155579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson continue; 156579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 157579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 158579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result = result.withSimpleType(); 159579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 160579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec already = primaryState.get(result); 161579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 162579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * The equals() check ensures we only add new info if 163579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * the instruction causes a change to the set of 164579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * active variables. 165579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 166579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!result.equals(already)) { 167579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 168579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * If this insn represents a local moving from one register 169579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * to another, remove the association between the old register 170579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * and the local. 171579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 172579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec previous 173579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson = primaryState.localItemToSpec(result.getLocalItem()); 174579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 175579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (previous != null 176579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson && (previous.getReg() != result.getReg())) { 177579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 178579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primaryState.remove(previous); 179579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 180579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 181579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson resultInfo.addAssignment(insn, result); 182579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primaryState.put(result); 183579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 184579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 185579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 186579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primaryState.setImmutable(); 187579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 188579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 189579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Merge this state into the start state for each successor, 190579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * and update the work set where required (that is, in cases 191579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * where the start state for a block changes). 192579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 193579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 194579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntList successors = block.getSuccessorList(); 195579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int succSz = successors.size(); 196579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int primarySuccessor = block.getPrimarySuccessorIndex(); 197579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 198579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < succSz; i++) { 199579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int succ = successors.get(i); 200579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecSet state = (succ == primarySuccessor) ? 201579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primaryState : secondaryState; 202579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 203579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (resultInfo.mergeStarts(succ, state)) { 204579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson workSet.set(succ); 205579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 206579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 207579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 208579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson} 209