1f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 2f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Copyright (C) 2007 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 19f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RegisterSpec; 20fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.RegisterSpecSet; 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.IntList; 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.ArrayList; 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.BitSet; 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.List; 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Code to figure out which local variables are active at which points in 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * a method. Stolen and retrofitted from 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * com.android.dx.rop.code.LocalVariableExtractor 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * TODO remove this. Allow Rop-form LocalVariableInfo to be passed in, 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * converted, and adapted through edge-splitting. 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic class LocalVariableExtractor { 3599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} method being extracted from */ 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final SsaMethod method; 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 3899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} block list for the method */ 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final ArrayList<SsaBasicBlock> blocks; 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 4199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} result in-progress */ 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final LocalVariableInfo resultInfo; 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 4499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} work set indicating blocks needing to be processed */ 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final BitSet workSet; 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Extracts out all the local variable information from the given method. 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 5099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param method {@code non-null;} the method to extract from 5199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the extracted information 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public static LocalVariableInfo extract(SsaMethod method) { 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LocalVariableExtractor lve = new LocalVariableExtractor(method); 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return lve.doit(); 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs an instance. This method is private. Use {@link #extract}. 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 6199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param method {@code non-null;} the method to extract from 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private LocalVariableExtractor(SsaMethod method) { 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (method == null) { 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NullPointerException("method == null"); 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<SsaBasicBlock> blocks = method.getBlocks(); 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.method = method; 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.blocks = blocks; 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.resultInfo = new LocalVariableInfo(method); 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.workSet = new BitSet(blocks.size()); 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Does the extraction. 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 7999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the extracted information 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private LocalVariableInfo doit() { 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project //FIXME why is this needed here? 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (method.getRegCount() > 0 ) { 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int bi = method.getEntryBlockIndex(); 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bi >= 0; 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bi = workSet.nextSetBit(0)) { 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project workSet.clear(bi); 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project processBlock(bi); 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultInfo.setImmutable(); 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return resultInfo; 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Processes a single block. 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param blockIndex {@code >= 0;} block index of the block to process 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void processBlock(int blockIndex) { 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecSet primaryState 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = resultInfo.mutableCopyOfStarts(blockIndex); 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock block = blocks.get(blockIndex); 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project List<SsaInsn> insns = block.getInsns(); 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int insnSz = insns.size(); 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // The exit block has no insns and no successors 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (blockIndex == method.getExitBlockIndex()) { 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * We may have to treat the last instruction specially: If it 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * can (but doesn't always) throw, and the exception can be 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * caught within the same method, then we need to use the 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * state *before* executing it to be what is merged into 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * exception targets. 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn lastInsn = insns.get(insnSz - 1); 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean hasExceptionHandlers 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = lastInsn.getOriginalRopInsn().getCatches().size() !=0 ; 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean canThrowDuringLastInsn = hasExceptionHandlers 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && (lastInsn.getResult() != null); 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int freezeSecondaryStateAt = insnSz - 1; 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecSet secondaryState = primaryState; 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Iterate over the instructions, adding information for each place 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * that the active variable set changes. 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < insnSz; i++) { 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (canThrowDuringLastInsn && (i == freezeSecondaryStateAt)) { 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Until this point, primaryState == secondaryState. 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primaryState.setImmutable(); 138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primaryState = primaryState.mutableCopy(); 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn insn = insns.get(i); 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec result; 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result = insn.getLocalAssignment(); 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (result == null) { 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // We may be nuking an existing local 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result = insn.getResult(); 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (result != null && primaryState.get(result.getReg()) != null) { 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primaryState.remove(primaryState.get(result.getReg())); 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result = result.withSimpleType(); 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec already = primaryState.get(result); 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The equals() check ensures we only add new info if 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the instruction causes a change to the set of 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * active variables. 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!result.equals(already)) { 166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If this insn represents a local moving from one register 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to another, remove the association between the old register 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and the local. 170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec previous 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = primaryState.localItemToSpec(result.getLocalItem()); 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (previous != null 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && (previous.getReg() != result.getReg())) { 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primaryState.remove(previous); 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultInfo.addAssignment(insn, result); 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primaryState.put(result); 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primaryState.setImmutable(); 186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Merge this state into the start state for each successor, 189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and update the work set where required (that is, in cases 190f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * where the start state for a block changes). 191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList successors = block.getSuccessorList(); 194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int succSz = successors.size(); 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int primarySuccessor = block.getPrimarySuccessorIndex(); 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < succSz; i++) { 198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int succ = successors.get(i); 199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecSet state = (succ == primarySuccessor) ? 200f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primaryState : secondaryState; 201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (resultInfo.mergeStarts(succ, state)) { 203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project workSet.set(succ); 204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 208