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