Home | History | Annotate | Download | only in code 
      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 
     17 package com.android.dexgen.rop.code;
     18 
     19 import com.android.dexgen.util.Bits;
     20 import com.android.dexgen.util.IntList;
     21 
     22 /**
     23  * Code to figure out which local variables are active at which points in
     24  * a method.
     25  */
     26 public final class LocalVariableExtractor {
     27     /** {@code non-null;} method being extracted from */
     28     private final RopMethod method;
     29 
     30     /** {@code non-null;} block list for the method */
     31     private final BasicBlockList blocks;
     32 
     33     /** {@code non-null;} result in-progress */
     34     private final LocalVariableInfo resultInfo;
     35 
     36     /** {@code non-null;} work set indicating blocks needing to be processed */
     37     private final int[] workSet;
     38 
     39     /**
     40      * Extracts out all the local variable information from the given method.
     41      *
     42      * @param method {@code non-null;} the method to extract from
     43      * @return {@code non-null;} the extracted information
     44      */
     45     public static LocalVariableInfo extract(RopMethod method) {
     46         LocalVariableExtractor lve = new LocalVariableExtractor(method);
     47         return lve.doit();
     48     }
     49 
     50     /**
     51      * Constructs an instance. This method is private. Use {@link #extract}.
     52      *
     53      * @param method {@code non-null;} the method to extract from
     54      */
     55     private LocalVariableExtractor(RopMethod method) {
     56         if (method == null) {
     57             throw new NullPointerException("method == null");
     58         }
     59 
     60         BasicBlockList blocks = method.getBlocks();
     61         int maxLabel = blocks.getMaxLabel();
     62 
     63         this.method = method;
     64         this.blocks = blocks;
     65         this.resultInfo = new LocalVariableInfo(method);
     66         this.workSet = Bits.makeBitSet(maxLabel);
     67     }
     68 
     69     /**
     70      * Does the extraction.
     71      *
     72      * @return {@code non-null;} the extracted information
     73      */
     74     private LocalVariableInfo doit() {
     75         for (int label = method.getFirstLabel();
     76              label >= 0;
     77              label = Bits.findFirst(workSet, 0)) {
     78             Bits.clear(workSet, label);
     79             processBlock(label);
     80         }
     81 
     82         resultInfo.setImmutable();
     83         return resultInfo;
     84     }
     85 
     86     /**
     87      * Processes a single block.
     88      *
     89      * @param label {@code >= 0;} label of the block to process
     90      */
     91     private void processBlock(int label) {
     92         RegisterSpecSet primaryState = resultInfo.mutableCopyOfStarts(label);
     93         BasicBlock block = blocks.labelToBlock(label);
     94         InsnList insns = block.getInsns();
     95         int insnSz = insns.size();
     96 
     97         /*
     98          * We may have to treat the last instruction specially: If it
     99          * can (but doesn't always) throw, and the exception can be
    100          * caught within the same method, then we need to use the
    101          * state *before* executing it to be what is merged into
    102          * exception targets.
    103          */
    104         boolean canThrowDuringLastInsn = block.hasExceptionHandlers() &&
    105             (insns.getLast().getResult() != null);
    106         int freezeSecondaryStateAt = insnSz - 1;
    107         RegisterSpecSet secondaryState = primaryState;
    108 
    109         /*
    110          * Iterate over the instructions, adding information for each place
    111          * that the active variable set changes.
    112          */
    113 
    114         for (int i = 0; i < insnSz; i++) {
    115             if (canThrowDuringLastInsn && (i == freezeSecondaryStateAt)) {
    116                 // Until this point, primaryState == secondaryState.
    117                 primaryState.setImmutable();
    118                 primaryState = primaryState.mutableCopy();
    119             }
    120 
    121             Insn insn = insns.get(i);
    122             RegisterSpec result;
    123 
    124             result = insn.getLocalAssignment();
    125 
    126             if (result == null) {
    127                 /*
    128                  * If an assignment assigns over an existing local, make
    129                  * sure to mark the local as going out of scope.
    130                  */
    131 
    132                 result = insn.getResult();
    133 
    134                 if (result != null
    135                         && primaryState.get(result.getReg()) != null) {
    136                     primaryState.remove(primaryState.get(result.getReg()));
    137                 }
    138                 continue;
    139             }
    140 
    141             result = result.withSimpleType();
    142 
    143             RegisterSpec already = primaryState.get(result);
    144             /*
    145              * The equals() check ensures we only add new info if
    146              * the instruction causes a change to the set of
    147              * active variables.
    148              */
    149             if (!result.equals(already)) {
    150                 /*
    151                  * If this insn represents a local moving from one register
    152                  * to another, remove the association between the old register
    153                  * and the local.
    154                  */
    155                 RegisterSpec previous
    156                         = primaryState.localItemToSpec(result.getLocalItem());
    157 
    158                 if (previous != null
    159                         && (previous.getReg() != result.getReg())) {
    160 
    161                     primaryState.remove(previous);
    162                 }
    163 
    164                 resultInfo.addAssignment(insn, result);
    165                 primaryState.put(result);
    166             }
    167         }
    168 
    169         primaryState.setImmutable();
    170 
    171         /*
    172          * Merge this state into the start state for each successor,
    173          * and update the work set where required (that is, in cases
    174          * where the start state for a block changes).
    175          */
    176 
    177         IntList successors = block.getSuccessors();
    178         int succSz = successors.size();
    179         int primarySuccessor = block.getPrimarySuccessor();
    180 
    181         for (int i = 0; i < succSz; i++) {
    182             int succ = successors.get(i);
    183             RegisterSpecSet state = (succ == primarySuccessor) ?
    184                 primaryState : secondaryState;
    185 
    186             if (resultInfo.mergeStarts(succ, state)) {
    187                 Bits.set(workSet, succ);
    188             }
    189         }
    190     }
    191 }
    192