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