dalvik/dx/src/com/android/dx/ssa/InterferenceRegisterMapper.java

   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 }