src/compiler/codegen/arm/ArmRallocUtil.cc

/*
 * Copyright (C) 2011 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/*
 * This file contains Arm-specific register alloction support.
 */

#include "../../CompilerUtility.h"
#include "../../CompilerIR.h"
#include "../..//Dataflow.h"
#include "ArmLIR.h"
#include "Codegen.h"
#include "../Ralloc.h"

/*
 * Placeholder routine until we do proper register allocation.
 */

typedef struct RefCounts {
    int count;
    int sReg;
    bool doubleStart;   // Starting vReg for a double
} RefCounts;

/* USE SSA names to count references of base Dalvik vRegs. */
STATIC void countRefs(CompilationUnit *cUnit, BasicBlock* bb,
                      RefCounts* coreCounts, RefCounts* fpCounts)
{
    MIR* mir;
    if (bb->blockType != kDalvikByteCode && bb->blockType != kEntryBlock &&
        bb->blockType != kExitBlock)
        return;

    for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
        SSARepresentation *ssaRep = mir->ssaRep;
        if (ssaRep) {
            for (int i = 0; i < ssaRep->numDefs;) {
                RegLocation loc = cUnit->regLocation[ssaRep->defs[i]];
                RefCounts* counts = loc.fp ? fpCounts : coreCounts;
                int vReg = oatS2VReg(cUnit, ssaRep->defs[i]);
                if (loc.defined) {
                    counts[vReg].count++;
                }
                if (loc.wide) {
                    if (loc.defined) {
                        if (loc.fp) {
                            counts[vReg].doubleStart = true;
                        }
                        counts[vReg+1].count++;
                    }
                    i += 2;
                } else {
                    i++;
                }
            }
            for (int i = 0; i < ssaRep->numUses;) {
                RegLocation loc = cUnit->regLocation[ssaRep->uses[i]];
                RefCounts* counts = loc.fp ? fpCounts : coreCounts;
                int vReg = oatS2VReg(cUnit, ssaRep->uses[i]);
                if (loc.defined) {
                    counts[vReg].count++;
                }
                if (loc.wide) {
                    if (loc.defined) {
                        if (loc.fp) {
                            counts[vReg].doubleStart = true;
                        }
                        counts[vReg+1].count++;
                    }
                    i += 2;
                } else {
                    i++;
                }
            }
        }
    }
}

/* qsort callback function, sort descending */
STATIC int sortCounts(const void *val1, const void *val2)
{
    const RefCounts* op1 = (const RefCounts*)val1;
    const RefCounts* op2 = (const RefCounts*)val2;
    return (op1->count == op2->count) ? 0 : (op1->count < op2->count ? 1 : -1);
}

STATIC void dumpCounts(const RefCounts* arr, int size, const char* msg)
{
    LOG(INFO) << msg;
    for (int i = 0; i < size; i++) {
        LOG(INFO) << "sReg[" << arr[i].sReg << "]: " << arr[i].count;
    }
}

/*
 * Note: some portions of this code required even if the kPromoteRegs
 * optimization is disabled.
 */
extern void oatDoPromotion(CompilationUnit* cUnit)
{
    int numRegs = cUnit->method->NumRegisters();

    /*
     * TUNING: is leaf?  Can't just use "hasInvoke" to determine as some
     * instructions might call out to C/assembly helper functions.  Until
     * machinery is in place, always spill lr.
     */
    cUnit->coreSpillMask |= (1 << rLR);
    cUnit->numCoreSpills++;
    /*
     * Simple hack for testing register allocation.  Just do a static
     * count of the uses of Dalvik registers.  Note that we examine
     * the SSA names, but count based on original Dalvik register name.
     * Count refs separately based on type in order to give allocation
     * preference to fp doubles - which must be allocated sequential
     * physical single fp registers started with an even-numbered
     * reg.
     */
    RefCounts *coreRegs = (RefCounts *)
          oatNew(sizeof(RefCounts) * numRegs, true);
    RefCounts *fpRegs = (RefCounts *)
          oatNew(sizeof(RefCounts) * numRegs, true);
    for (int i = 0; i < numRegs; i++) {
        coreRegs[i].sReg = fpRegs[i].sReg = i;
    }
    GrowableListIterator iterator;
    oatGrowableListIteratorInit(&cUnit->blockList, &iterator);
    while (true) {
        BasicBlock* bb;
        bb = (BasicBlock*)oatGrowableListIteratorNext(&iterator);
        if (bb == NULL) break;
        countRefs(cUnit, bb, coreRegs, fpRegs);
    }

    /*
     * Ideally, we'd allocate doubles starting with an even-numbered
     * register.  Bias the counts to try to allocate any vreg that's
     * used as the start of a pair first.
     */
    for (int i = 0; i < numRegs; i++) {
        if (fpRegs[i].doubleStart) {
            fpRegs[i].count *= 2;
        }
    }

    // Sort the count arrays
    qsort(coreRegs, numRegs, sizeof(RefCounts), sortCounts);
    qsort(fpRegs, numRegs, sizeof(RefCounts), sortCounts);

    if (cUnit->printMe) {
        dumpCounts(coreRegs, numRegs, "Core regs after sort");
        dumpCounts(fpRegs, numRegs, "Fp regs after sort");
    }

    if (!(cUnit->disableOpt & (1 << kPromoteRegs))) {
        // Promote fpRegs
        for (int i = 0; (fpRegs[i].count > 0) && (i < numRegs); i++) {
            if (cUnit->promotionMap[fpRegs[i].sReg].fpLocation != kLocPhysReg) {
                if (fpRegs[i].sReg >= cUnit->numRegs) {
                    // don't promote arg regs
                    continue;
                }
                int reg = oatAllocPreservedFPReg(cUnit, fpRegs[i].sReg,
                    fpRegs[i].doubleStart);
                if (reg < 0) {
                    break;  // No more left
                }
            }
        }

        // Promote core regs
        for (int i = 0; (coreRegs[i].count > 0) && i < numRegs; i++) {
            if (cUnit->promotionMap[coreRegs[i].sReg].coreLocation !=
                    kLocPhysReg) {
                if (coreRegs[i].sReg >= cUnit->numRegs) {
                    // don't promote arg regs
                    continue;
                }
                int reg = oatAllocPreservedCoreReg(cUnit, coreRegs[i].sReg);
                if (reg < 0) {
                   break;  // No more left
                }
            }
        }
    }

    // Now, update SSA names to new home locations
    for (int i = 0; i < cUnit->numSSARegs; i++) {
        RegLocation *curr = &cUnit->regLocation[i];
        int baseVReg = oatS2VReg(cUnit, curr->sRegLow);
        if (!curr->wide) {
            if (curr->fp) {
                if (cUnit->promotionMap[baseVReg].fpLocation == kLocPhysReg) {
                    curr->location = kLocPhysReg;
                    curr->lowReg = cUnit->promotionMap[baseVReg].fpReg;
                    curr->home = true;
                }
            } else {
                if (cUnit->promotionMap[baseVReg].coreLocation == kLocPhysReg) {
                    curr->location = kLocPhysReg;
                    curr->lowReg = cUnit->promotionMap[baseVReg].coreReg;
                    curr->home = true;
                }
            }
            curr->highReg = INVALID_REG;
        } else {
            if (curr->highWord) {
                continue;
            }
            if (curr->fp) {
                if ((cUnit->promotionMap[baseVReg].fpLocation == kLocPhysReg) &&
                    (cUnit->promotionMap[baseVReg+1].fpLocation ==
                    kLocPhysReg)) {
                    int lowReg = cUnit->promotionMap[baseVReg].fpReg;
                    int highReg = cUnit->promotionMap[baseVReg+1].fpReg;
                    // Doubles require pair of singles starting at even reg
                    if (((lowReg & 0x1) == 0) && ((lowReg + 1) == highReg)) {
                        curr->location = kLocPhysReg;
                        curr->lowReg = lowReg;
                        curr->highReg = highReg;
                        curr->home = true;
                    }
                }
            } else {
                if ((cUnit->promotionMap[baseVReg].coreLocation == kLocPhysReg)
                     && (cUnit->promotionMap[baseVReg+1].coreLocation ==
                     kLocPhysReg)) {
                    curr->location = kLocPhysReg;
                    curr->lowReg = cUnit->promotionMap[baseVReg].coreReg;
                    curr->highReg = cUnit->promotionMap[baseVReg+1].coreReg;
                    curr->home = true;
                }
            }
        }
    }
}

/* Returns sp-relative offset in bytes for a VReg */
extern int oatVRegOffset(CompilationUnit* cUnit, int vReg)
{
    return (vReg < cUnit->numRegs) ? cUnit->regsOffset + (vReg << 2) :
            cUnit->insOffset + ((vReg - cUnit->numRegs) << 2);
}

/* Returns sp-relative offset in bytes for a SReg */
extern int oatSRegOffset(CompilationUnit* cUnit, int sReg)
{
    return oatVRegOffset(cUnit, oatS2VReg(cUnit, sReg));
}


/* Return sp-relative offset in bytes using Method* */
extern int oatVRegOffsetFromMethod(Method* method, int reg)
{
    int numIns = method->NumIns();
    int numRegs = method->NumRegisters() - numIns;
    int numOuts = method->NumOuts();
    int numSpills = __builtin_popcount(method->GetCoreSpillMask()) +
                    __builtin_popcount(method->GetFpSpillMask());
    int numPadding = (STACK_ALIGN_WORDS -
        (numSpills + numRegs + numOuts + 2)) & (STACK_ALIGN_WORDS-1);
    int regsOffset = (numOuts + numPadding + 1) * 4;
    int insOffset = method->GetFrameSizeInBytes() + 4;
    return (reg < numRegs) ? regsOffset + (reg << 2) :
           insOffset + ((reg - numRegs) << 2);
}

/* Clobber all regs that might be used by an external C call */
extern void oatClobberCalleeSave(CompilationUnit *cUnit)
{
    oatClobber(cUnit, r0);
    oatClobber(cUnit, r1);
    oatClobber(cUnit, r2);
    oatClobber(cUnit, r3);
    oatClobber(cUnit, r12);
    oatClobber(cUnit, r14lr);
}

extern RegLocation oatGetReturnWide(CompilationUnit* cUnit)
{
    RegLocation res = LOC_C_RETURN_WIDE;
    oatClobber(cUnit, r0);
    oatClobber(cUnit, r1);
    oatMarkInUse(cUnit, r0);
    oatMarkInUse(cUnit, r1);
    oatMarkPair(cUnit, res.lowReg, res.highReg);
    return res;
}

extern RegLocation oatGetReturnWideAlt(CompilationUnit* cUnit)
{
    RegLocation res = LOC_C_RETURN_WIDE;
    res.lowReg = r2;
    res.highReg = r3;
    oatClobber(cUnit, r2);
    oatClobber(cUnit, r3);
    oatMarkInUse(cUnit, r2);
    oatMarkInUse(cUnit, r3);
    oatMarkPair(cUnit, res.lowReg, res.highReg);
    return res;
}

extern RegLocation oatGetReturn(CompilationUnit* cUnit)
{
    RegLocation res = LOC_C_RETURN;
    oatClobber(cUnit, r0);
    oatMarkInUse(cUnit, r0);
    return res;
}

extern RegLocation oatGetReturnAlt(CompilationUnit* cUnit)
{
    RegLocation res = LOC_C_RETURN;
    res.lowReg = r1;
    oatClobber(cUnit, r1);
    oatMarkInUse(cUnit, r1);
    return res;
}

extern RegisterInfo* oatGetRegInfo(CompilationUnit* cUnit, int reg)
{
    return FPREG(reg) ? &cUnit->regPool->FPRegs[reg & FP_REG_MASK]
                      : &cUnit->regPool->coreRegs[reg];
}