Home | History | Annotate | Download | only in back 
      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.back;
     18 
     19 import com.android.dx.ssa.SsaMethod;
     20 import com.android.dx.ssa.SsaBasicBlock;
     21 import com.android.dx.ssa.SsaInsn;
     22 import com.android.dx.ssa.PhiInsn;
     23 import com.android.dx.ssa.SetFactory;
     24 import com.android.dx.rop.code.RegisterSpec;
     25 import com.android.dx.util.IntSet;
     26 import com.android.dx.util.BitIntSet;
     27 import com.android.dx.util.ListIntSet;
     28 
     29 import java.util.BitSet;
     30 import java.util.List;
     31 import java.util.ArrayList;
     32 
     33 /**
     34  * A register interference graph
     35  */
     36 public class InterferenceGraph {
     37     /**
     38      * {@code non-null;} interference graph, indexed by register in
     39      * both dimensions
     40      */
     41     private final ArrayList<IntSet> interference;
     42 
     43     /**
     44      * Creates a new graph.
     45      *
     46      * @param countRegs {@code >= 0;} the start count of registers in
     47      * the namespace. New registers can be added subsequently.
     48      */
     49     public InterferenceGraph(int countRegs) {
     50         interference = new ArrayList<IntSet>(countRegs);
     51 
     52         for (int i = 0; i < countRegs; i++) {
     53             interference.add(SetFactory.makeInterferenceSet(countRegs));
     54         }
     55     }
     56 
     57     /**
     58      * Adds a register pair to the interference/liveness graph. Parameter
     59      * order is insignificant.
     60      *
     61      * @param regV one register index
     62      * @param regW another register index
     63      */
     64     public void add(int regV, int regW) {
     65         ensureCapacity(Math.max(regV, regW) + 1);
     66 
     67         interference.get(regV).add(regW);
     68         interference.get(regW).add(regV);
     69     }
     70 
     71     /**
     72      * Dumps interference graph to stdout for debugging.
     73      */
     74     public void dumpToStdout() {
     75         int oldRegCount = interference.size();
     76 
     77         for (int i = 0; i < oldRegCount; i++) {
     78             StringBuilder sb = new StringBuilder();
     79 
     80             sb.append("Reg " + i + ":" + interference.get(i).toString());
     81 
     82             System.out.println(sb.toString());
     83         }
     84     }
     85 
     86     /**
     87      * Merges the interference set for a register into a given bit set
     88      *
     89      * @param reg {@code >= 0;} register
     90      * @param set {@code non-null;} interference set; will be merged
     91      * with set for given register
     92      */
     93     public void mergeInterferenceSet(int reg, IntSet set) {
     94         if (reg < interference.size()) {
     95             set.merge(interference.get(reg));
     96         }
     97     }
     98 
     99     /**
    100      * Ensures that the interference graph is appropriately sized.
    101      *
    102      * @param size requested minumum size
    103      */
    104     private void ensureCapacity(int size) {
    105         int countRegs = interference.size();
    106 
    107         interference.ensureCapacity(size);
    108 
    109         for (int i = countRegs; i < size; i++) {
    110             interference.add(SetFactory.makeInterferenceSet(size));
    111         }
    112     }
    113 }
    114