Home | History | Annotate | Download | only in ssa 
      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.dx.ssa;
     18 
     19 import com.android.dx.rop.code.RegisterSpecList;
     20 import com.android.dx.rop.code.RegisterSpec;
     21 import com.android.dx.ssa.back.InterferenceGraph;
     22 import com.android.dx.util.IntSet;
     23 import com.android.dx.util.BitIntSet;
     24 
     25 import java.util.ArrayList;
     26 import java.util.BitSet;
     27 
     28 /**
     29  * A register mapper that keeps track of the accumulated interference
     30  * information for the registers in the new namespace.
     31  *
     32  * Please note that this mapper requires that the old namespace does not
     33  * have variable register widths/categories, and the new namespace does.
     34  */
     35 public class InterferenceRegisterMapper extends BasicRegisterMapper {
     36     /**
     37      * Array of interference sets. ArrayList is indexed by new namespace
     38      * and BitIntSet's are indexed by old namespace.  The list expands
     39      * as needed and missing items are assumed to interfere with nothing.
     40      *
     41      * Bit sets are always used here, unlike elsewhere, because the max
     42      * size of this matrix will be (countSsaRegs * countRopRegs), which may
     43      * grow to hundreds of K but not megabytes.
     44      */
     45     private final ArrayList<BitIntSet> newRegInterference;
     46 
     47     /** the interference graph for the old namespace */
     48     private final InterferenceGraph oldRegInterference;
     49 
     50     /**
     51      * Constructs an instance
     52      *
     53      * @param countOldRegisters number of registers in old namespace
     54      */
     55     public InterferenceRegisterMapper(InterferenceGraph oldRegInterference,
     56             int countOldRegisters) {
     57         super(countOldRegisters);
     58 
     59         newRegInterference = new ArrayList<BitIntSet>();
     60         this.oldRegInterference = oldRegInterference;
     61     }
     62 
     63     /** {@inheritDoc} */
     64     @Override
     65     public void addMapping(int oldReg, int newReg, int category) {
     66         super.addMapping(oldReg, newReg, category);
     67 
     68         addInterfence(newReg, oldReg);
     69 
     70         if (category == 2) {
     71             addInterfence(newReg + 1, oldReg);
     72         }
     73     }
     74 
     75     /**
     76      * Checks to see if old namespace reg {@code oldReg} interferes
     77      * with what currently maps to {@code newReg}.
     78      *
     79      * @param oldReg old namespace register
     80      * @param newReg new namespace register
     81      * @param category category of old namespace register
     82      * @return true if oldReg will interfere with newReg
     83      */
     84     public boolean interferes(int oldReg, int newReg, int category) {
     85         if (newReg >= newRegInterference.size()) {
     86             return false;
     87         } else {
     88             IntSet existing = newRegInterference.get(newReg);
     89 
     90             if (existing == null) {
     91                 return false;
     92             } else if (category == 1) {
     93                 return existing.has(oldReg);
     94             } else {
     95                 return existing.has(oldReg)
     96                         || (interferes(oldReg, newReg+1, category-1));
     97             }
     98         }
     99     }
    100 
    101     /**
    102      * Checks to see if old namespace reg {@code oldReg} interferes
    103      * with what currently maps to {@code newReg}.
    104      *
    105      * @param oldSpec {@code non-null;} old namespace register
    106      * @param newReg new namespace register
    107      * @return true if oldReg will interfere with newReg
    108      */
    109     public boolean interferes(RegisterSpec oldSpec, int newReg) {
    110         return interferes(oldSpec.getReg(), newReg, oldSpec.getCategory());
    111     }
    112 
    113     /**
    114      * Adds a register's interference set to the interference list,
    115      * growing it if necessary.
    116      *
    117      * @param newReg register in new namespace
    118      * @param oldReg register in old namespace
    119      */
    120     private void addInterfence(int newReg, int oldReg) {
    121         newRegInterference.ensureCapacity(newReg + 1);
    122 
    123         while (newReg >= newRegInterference.size()) {
    124             newRegInterference.add(new BitIntSet(newReg +1));
    125         }
    126 
    127         oldRegInterference.mergeInterferenceSet(
    128                 oldReg, newRegInterference.get(newReg));
    129     }
    130 
    131     /**
    132      * Checks to see if any of a set of old-namespace registers are
    133      * pinned to the specified new-namespace reg + category. Takes into
    134      * account the category of the old-namespace registers.
    135      *
    136      * @param oldSpecs {@code non-null;} set of old-namespace regs
    137      * @param newReg {@code >= 0;} new-namespace register
    138      * @param targetCategory {@code 1..2;} the number of adjacent new-namespace
    139      * registers (starting at ropReg) to consider
    140      * @return true if any of the old-namespace register have been mapped
    141      * to the new-namespace register + category
    142      */
    143     public boolean areAnyPinned(RegisterSpecList oldSpecs,
    144             int newReg, int targetCategory) {
    145         int sz = oldSpecs.size();
    146 
    147         for (int i = 0; i < sz; i++) {
    148             RegisterSpec oldSpec = oldSpecs.get(i);
    149             int r = oldToNew(oldSpec.getReg());
    150 
    151             /*
    152              * If oldSpec is a category-2 register, then check both newReg
    153              * and newReg - 1.
    154              */
    155             if (r == newReg
    156                 || (oldSpec.getCategory() == 2 && (r + 1) == newReg)
    157                 || (targetCategory == 2 && (r == newReg + 1))) {
    158                 return true;
    159             }
    160         }
    161 
    162         return false;
    163     }
    164 }
    165