dx/src/com/android/dx/ssa/back/FirstFitAllocator.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.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 }