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