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.CstInsn;
     20 import com.android.dx.rop.cst.CstInteger;
     21 import com.android.dx.ssa.BasicRegisterMapper;
     22 import com.android.dx.ssa.NormalSsaInsn;
     23 import com.android.dx.ssa.RegisterMapper;
     24 import com.android.dx.ssa.SsaMethod;
     25 import com.android.dx.util.BitIntSet;
     26 import com.android.dx.util.IntSet;
     27 import java.util.BitSet;
     28 
     29 /**
     30  * Allocates registers via a naive n^2 register allocator.
     31  * This allocator does not try to co-locate local variables or deal
     32  * intelligently with different size register uses.
     33  */
     34 public class FirstFitAllocator extends RegisterAllocator {
     35     /**
     36      * If true, allocator places parameters at the top of the frame
     37      * in calling-convention order.
     38      */
     39     private static final boolean PRESLOT_PARAMS = true;
     40 
     41     /** indexed by old reg; the set of old regs we've mapped */
     42     private final BitSet mapped;
     43 
     44     /** {@inheritDoc} */
     45     public FirstFitAllocator(
     46             final SsaMethod ssaMeth, final InterferenceGraph interference) {
     47         super(ssaMeth, interference);
     48 
     49         mapped = new BitSet(ssaMeth.getRegCount());
     50     }
     51 
     52     /** {@inheritDoc} */
     53     @Override
     54     public boolean wantsParamsMovedHigh() {
     55         return PRESLOT_PARAMS;
     56     }
     57 
     58     /** {@inheritDoc} */
     59     @Override
     60     public RegisterMapper allocateRegisters() {
     61         int oldRegCount = ssaMeth.getRegCount();
     62 
     63         BasicRegisterMapper mapper
     64                 = new BasicRegisterMapper(oldRegCount);
     65 
     66         int nextNewRegister = 0;
     67 
     68         if (PRESLOT_PARAMS) {
     69             /*
     70              * Reserve space for the params at the bottom of the register
     71              * space. Later, we'll flip the params to the end of the register
     72              * space.
     73              */
     74 
     75             nextNewRegister = ssaMeth.getParamWidth();
     76         }
     77 
     78         for (int i = 0; i < oldRegCount; i++) {
     79             if (mapped.get(i)) {
     80                 // we already got this one
     81                 continue;
     82             }
     83 
     84             int maxCategory = getCategoryForSsaReg(i);
     85             IntSet current = new BitIntSet(oldRegCount);
     86 
     87             interference.mergeInterferenceSet(i, current);
     88 
     89             boolean isPreslotted = false;
     90             int newReg = 0;
     91 
     92             if (PRESLOT_PARAMS && isDefinitionMoveParam(i)) {
     93                 // Any move-param definition must be a NormalSsaInsn
     94                 NormalSsaInsn defInsn = (NormalSsaInsn)
     95                        ssaMeth.getDefinitionForRegister(i);
     96 
     97                 newReg = paramNumberFromMoveParam(defInsn);
     98 
     99                 mapper.addMapping(i, newReg, maxCategory);
    100                 isPreslotted = true;
    101             } else {
    102                 mapper.addMapping(i, nextNewRegister, maxCategory);
    103                 newReg = nextNewRegister;
    104             }
    105 
    106             for (int j = i + 1; j < oldRegCount; j++) {
    107                 if (mapped.get(j) || isDefinitionMoveParam(j)) {
    108                     continue;
    109                 }
    110 
    111                 /*
    112                  * If reg j doesn't interfere with the current mapping.
    113                  * Also, if this is a pre-slotted method parameter, we
    114                  * can't use more than the original param width.
    115                  */
    116                 if (!current.has(j)
    117                         && !(isPreslotted
    118                             && (maxCategory < getCategoryForSsaReg(j)))) {
    119 
    120                     interference.mergeInterferenceSet(j, current);
    121 
    122                     maxCategory = Math.max(maxCategory,
    123                             getCategoryForSsaReg(j));
    124 
    125                     mapper.addMapping(j, newReg, maxCategory);
    126                     mapped.set(j);
    127                 }
    128             }
    129 
    130             mapped.set(i);
    131             if (!isPreslotted) {
    132                 nextNewRegister += maxCategory;
    133             }
    134         }
    135 
    136         return mapper;
    137     }
    138 
    139     /**
    140      * Returns the parameter number that this move-param insn refers to
    141      * @param ndefInsn a move-param insn (otherwise, exceptions will be thrown)
    142      * @return parameter number (offset in the total parameter width)
    143      */
    144     private int paramNumberFromMoveParam(NormalSsaInsn ndefInsn) {
    145         CstInsn origInsn = (CstInsn) ndefInsn.getOriginalRopInsn();
    146 
    147         return ((CstInteger) origInsn.getConstant()).getValue();
    148     }
    149 }
    150