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.rop.code.PlainInsn;
     20 import com.android.dx.rop.code.RegOps;
     21 import com.android.dx.rop.code.RegisterSpec;
     22 import com.android.dx.rop.code.RegisterSpecList;
     23 import com.android.dx.rop.code.Rops;
     24 import com.android.dx.rop.code.SourcePosition;
     25 import com.android.dx.ssa.NormalSsaInsn;
     26 import com.android.dx.ssa.RegisterMapper;
     27 import com.android.dx.ssa.SsaBasicBlock;
     28 import com.android.dx.ssa.SsaInsn;
     29 import com.android.dx.ssa.SsaMethod;
     30 import com.android.dx.util.IntIterator;
     31 import com.android.dx.util.IntSet;
     32 import java.util.ArrayList;
     33 
     34 /**
     35  * Base class of all register allocators.
     36  */
     37 public abstract class RegisterAllocator {
     38     /** method being processed */
     39     protected final SsaMethod ssaMeth;
     40 
     41     /** interference graph, indexed by register in both dimensions */
     42     protected final InterferenceGraph interference;
     43 
     44     /**
     45      * Creates an instance. Call {@code allocateRegisters} to run.
     46      * @param ssaMeth method to process.
     47      * @param interference Interference graph, indexed by register in both
     48      * dimensions.
     49      */
     50     public RegisterAllocator(SsaMethod ssaMeth,
     51             InterferenceGraph interference) {
     52         this.ssaMeth = ssaMeth;
     53         this.interference = interference;
     54     }
     55 
     56     /**
     57      * Indicates whether the method params were allocated at the bottom
     58      * of the namespace, and thus should be moved up to the top of the
     59      * namespace after phi removal.
     60      *
     61      * @return {@code true} if params should be moved from low to high
     62      */
     63     public abstract boolean wantsParamsMovedHigh();
     64 
     65     /**
     66      * Runs the algorithm.
     67      *
     68      * @return a register mapper to apply to the {@code SsaMethod}
     69      */
     70     public abstract RegisterMapper allocateRegisters();
     71 
     72     /**
     73      * Returns the category (width) of the definition site of the register.
     74      * Returns {@code 1} for undefined registers.
     75      *
     76      * @param reg register
     77      * @return {@code 1..2}
     78      */
     79     protected final int getCategoryForSsaReg(int reg) {
     80         SsaInsn definition = ssaMeth.getDefinitionForRegister(reg);
     81 
     82         if (definition == null) {
     83             // an undefined reg
     84             return 1;
     85         } else {
     86             return definition.getResult().getCategory();
     87         }
     88     }
     89 
     90     /**
     91      * Returns the RegisterSpec of the definition of the register.
     92      *
     93      * @param reg {@code >= 0;} SSA register
     94      * @return definition spec of the register or null if it is never defined
     95      * (for the case of "version 0" SSA registers)
     96      */
     97     protected final RegisterSpec getDefinitionSpecForSsaReg(int reg) {
     98         SsaInsn definition = ssaMeth.getDefinitionForRegister(reg);
     99 
    100         return definition == null ? null : definition.getResult();
    101     }
    102 
    103     /**
    104      * Returns true if the definition site of this register is a
    105      * move-param (ie, this is a method parameter).
    106      *
    107      * @param reg register in question
    108      * @return {@code true} if this is a method parameter
    109      */
    110     protected boolean isDefinitionMoveParam(int reg) {
    111         SsaInsn defInsn = ssaMeth.getDefinitionForRegister(reg);
    112 
    113         if (defInsn instanceof NormalSsaInsn) {
    114             NormalSsaInsn ndefInsn = (NormalSsaInsn) defInsn;
    115 
    116             return ndefInsn.getOpcode().getOpcode() == RegOps.MOVE_PARAM;
    117         }
    118 
    119         return false;
    120     }
    121 
    122     /**
    123      * Inserts a move instruction for a specified SSA register before a
    124      * specified instruction, creating a new SSA register and adjusting the
    125      * interference graph in the process. The insn currently must be the
    126      * last insn in a block.
    127      *
    128      * @param insn {@code non-null;} insn to insert move before, must
    129      * be last insn in block
    130      * @param reg {@code non-null;} SSA register to duplicate
    131      * @return {@code non-null;} spec of new SSA register created by move
    132      */
    133     protected final RegisterSpec insertMoveBefore(SsaInsn insn,
    134             RegisterSpec reg) {
    135         SsaBasicBlock block = insn.getBlock();
    136         ArrayList<SsaInsn> insns = block.getInsns();
    137         int insnIndex = insns.indexOf(insn);
    138 
    139         if (insnIndex < 0) {
    140             throw new IllegalArgumentException (
    141                     "specified insn is not in this block");
    142         }
    143 
    144         if (insnIndex != insns.size() - 1) {
    145             /*
    146              * Presently, the interference updater only works when
    147              * adding before the last insn, and the last insn must have no
    148              * result
    149              */
    150             throw new IllegalArgumentException(
    151                     "Adding move here not supported:" + insn.toHuman());
    152         }
    153 
    154         /*
    155          * Get new register and make new move instruction.
    156          */
    157 
    158         // The new result must not have an associated local variable.
    159         RegisterSpec newRegSpec = RegisterSpec.make(ssaMeth.makeNewSsaReg(),
    160                 reg.getTypeBearer());
    161 
    162         SsaInsn toAdd = SsaInsn.makeFromRop(
    163                 new PlainInsn(Rops.opMove(newRegSpec.getType()),
    164                         SourcePosition.NO_INFO, newRegSpec,
    165                         RegisterSpecList.make(reg)), block);
    166 
    167         insns.add(insnIndex, toAdd);
    168 
    169         int newReg = newRegSpec.getReg();
    170 
    171         /*
    172          * Adjust interference graph based on what's live out of the current
    173          * block and what's used by the final instruction.
    174          */
    175 
    176         IntSet liveOut = block.getLiveOutRegs();
    177         IntIterator liveOutIter = liveOut.iterator();
    178 
    179         while (liveOutIter.hasNext()) {
    180             interference.add(newReg, liveOutIter.next());
    181         }
    182 
    183         // Everything that's a source in the last insn interferes.
    184         RegisterSpecList sources = insn.getSources();
    185         int szSources = sources.size();
    186 
    187         for (int i = 0; i < szSources; i++) {
    188             interference.add(newReg, sources.get(i).getReg());
    189         }
    190 
    191         ssaMeth.onInsnsChanged();
    192 
    193         return newRegSpec;
    194     }
    195 }
    196