path: root/vm/compiler/codegen/arm/LocalOptimizations.c

/*
 * Copyright (C) 2009 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.
 */

#include "Dalvik.h"
#include "vm/compiler/CompilerInternals.h"
#include "ArmLIR.h"
#include "Codegen.h"

#define DEBUG_OPT(X)

ArmLIR* dvmCompilerGenCopy(CompilationUnit *cUnit, int rDest, int rSrc);

/* Is this a Dalvik register access? */
static inline bool isDalvikLoad(ArmLIR *lir)
{
    return (lir->useMask != ENCODE_ALL) && (lir->useMask & ENCODE_DALVIK_REG);
}

/* Is this a load from the literal pool? */
static inline bool isLiteralLoad(ArmLIR *lir)
{
    return (lir->useMask != ENCODE_ALL) && (lir->useMask & ENCODE_LITERAL);
}

static inline bool isDalvikStore(ArmLIR *lir)
{
    return (lir->defMask != ENCODE_ALL) && (lir->defMask & ENCODE_DALVIK_REG);
}

static inline bool isDalvikRegisterClobbered(ArmLIR *lir1, ArmLIR *lir2)
{
  int reg1Lo = DECODE_ALIAS_INFO_REG(lir1->aliasInfo);
  int reg1Hi = reg1Lo + DECODE_ALIAS_INFO_WIDE(lir1->aliasInfo);
  int reg2Lo = DECODE_ALIAS_INFO_REG(lir2->aliasInfo);
  int reg2Hi = reg2Lo + DECODE_ALIAS_INFO_WIDE(lir2->aliasInfo);

  return (reg1Lo == reg2Lo) || (reg1Lo == reg2Hi) || (reg1Hi == reg2Lo);
}

#if 0
/* Debugging utility routine */
static void dumpDependentInsnPair(ArmLIR *thisLIR, ArmLIR *checkLIR,
                                  const char *optimization)
{
    LOGD("************ %s ************", optimization);
    dvmDumpLIRInsn((LIR *) thisLIR, 0);
    dvmDumpLIRInsn((LIR *) checkLIR, 0);
}
#endif

/*
 * Perform a pass of top-down walk to
 * 1) Eliminate redundant loads and stores
 * 2) Sink stores to latest possible slot
 */
static void applyLoadStoreElimination(CompilationUnit *cUnit,
                                      ArmLIR *headLIR,
                                      ArmLIR *tailLIR)
{
    ArmLIR *thisLIR;

    cUnit->optRound++;
    for (thisLIR = headLIR;
         thisLIR != tailLIR;
         thisLIR = NEXT_LIR(thisLIR)) {
        /* Skip newly added instructions */
        if (thisLIR->flags.age >= cUnit->optRound) {
            continue;
        }
        if (isDalvikStore(thisLIR)) {
            int nativeRegId = thisLIR->operands[0];
            ArmLIR *checkLIR;
            int sinkDistance = 0;
            /*
             * Add r15 (pc) to the mask to prevent this instruction
             * from sinking past branch instructions. Unset the Dalvik register
             * bit when checking with native resource constraints.
             */
            u8 stopMask = (ENCODE_REG_PC | thisLIR->useMask) &
                          ~ENCODE_DALVIK_REG;

            for (checkLIR = NEXT_LIR(thisLIR);
                 checkLIR != tailLIR;
                 checkLIR = NEXT_LIR(checkLIR)) {

                /* Check if a Dalvik register load is redundant */
                if (isDalvikLoad(checkLIR) &&
                    (checkLIR->aliasInfo == thisLIR->aliasInfo) &&
                    (REGTYPE(checkLIR->operands[0]) == REGTYPE(nativeRegId))) {
                    /* Insert a move to replace the load */
                    if (checkLIR->operands[0] != nativeRegId) {
                        ArmLIR *moveLIR;
                        moveLIR = dvmCompilerRegCopyNoInsert(
                                    cUnit, checkLIR->operands[0], nativeRegId);
                        /*
                         * Insert the converted checkLIR instruction after the
                         * the original checkLIR since the optimization is
                         * scannng in the top-down order and the new instruction
                         * will need to be checked.
                         */
                        dvmCompilerInsertLIRAfter((LIR *) checkLIR,
                                                  (LIR *) moveLIR);
                    }
                    checkLIR->flags.isNop = true;
                    continue;

                /*
                 * Found a true output dependency - nuke the previous store.
                 * The register type doesn't matter here.
                 */
                } else if (isDalvikStore(checkLIR) &&
                           (checkLIR->aliasInfo == thisLIR->aliasInfo)) {
                    thisLIR->flags.isNop = true;
                    break;
                /* Find out the latest slot that the store can be sunk into */
                } else {
                    /* Last instruction reached */
                    bool stopHere = (NEXT_LIR(checkLIR) == tailLIR);

                    /* Store data is clobbered */
                    stopHere |= ((stopMask & checkLIR->defMask) != 0);

                    /* Store data partially clobbers the Dalvik register */
                    if (stopHere == false &&
                        ((checkLIR->useMask | checkLIR->defMask) &
                         ENCODE_DALVIK_REG)) {
                        stopHere = isDalvikRegisterClobbered(thisLIR, checkLIR);
                    }

                    /* Found a new place to put the store - move it here */
                    if (stopHere == true) {
                        DEBUG_OPT(dumpDependentInsnPair(thisLIR, checkLIR,
                                                        "SINK STORE"));
                        /* The store can be sunk for at least one cycle */
                        if (sinkDistance != 0) {
                            ArmLIR *newStoreLIR =
                                (ArmLIR *)dvmCompilerNew(sizeof(ArmLIR), true);
                            *newStoreLIR = *thisLIR;
                            newStoreLIR->flags.age = cUnit->optRound;
                            /*
                             * Stop point found - insert *before* the checkLIR
                             * since the instruction list is scanned in the
                             * top-down order.
                             */
                            dvmCompilerInsertLIRBefore((LIR *) checkLIR,
                                                       (LIR *) newStoreLIR);
                            thisLIR->flags.isNop = true;
                        }
                        break;
                    }

                    /*
                     * Saw a real instruction that the store can be sunk after
                     */
                    if (!isPseudoOpcode(checkLIR->opcode)) {
                        sinkDistance++;
                    }
                }
            }
        }
    }
}

static void applyLoadHoisting(CompilationUnit *cUnit,
                              ArmLIR *headLIR,
                              ArmLIR *tailLIR)
{
    ArmLIR *thisLIR;
    /*
     * Don't want to hoist in front of first load following a barrier (or
     * first instruction of the block.
     */
    bool firstLoad = true;
    int maxHoist = dvmCompilerTargetOptHint(kMaxHoistDistance);

    cUnit->optRound++;
    for (thisLIR = headLIR;
         thisLIR != tailLIR;
         thisLIR = NEXT_LIR(thisLIR)) {
        /* Skip newly added instructions */
        if (thisLIR->flags.age >= cUnit->optRound ||
            thisLIR->flags.isNop == true) {
            continue;
        }

        if (firstLoad && (EncodingMap[thisLIR->opcode].flags & IS_LOAD)) {
            /*
             * Ensure nothing will be hoisted in front of this load because
             * it's result will likely be needed soon.
             */
            thisLIR->defMask |= ENCODE_MEM_USE;
            firstLoad = false;
        }

        firstLoad |= (thisLIR->defMask == ENCODE_ALL);

        if (isDalvikLoad(thisLIR)) {
            int dRegId = DECODE_ALIAS_INFO_REG(thisLIR->aliasInfo);
            int nativeRegId = thisLIR->operands[0];
            ArmLIR *checkLIR;
            int hoistDistance = 0;
            u8 stopUseMask = (ENCODE_REG_PC | thisLIR->useMask);
            u8 stopDefMask = thisLIR->defMask;
            u8 checkResult;

            /* First check if the load can be completely elinimated */
            for (checkLIR = PREV_LIR(thisLIR);
                 checkLIR != headLIR;
                 checkLIR = PREV_LIR(checkLIR)) {

                if (checkLIR->flags.isNop) continue;

                /*
                 * Check if the Dalvik register is previously accessed
                 * with exactly the same type.
                 */
                if ((isDalvikLoad(checkLIR) || isDalvikStore(checkLIR)) &&
                    (checkLIR->aliasInfo == thisLIR->aliasInfo) &&
                    (checkLIR->operands[0] == nativeRegId)) {
                    /*
                     * If it is previously accessed but with a different type,
                     * the search will terminate later at the point checking
                     * for partially overlapping stores.
                     */
                    thisLIR->flags.isNop = true;
                    break;
                }

                /*
                 * No earlier use/def can reach this load if:
                 * 1) Head instruction is reached
                 */
                if (checkLIR == headLIR) {
                    break;
                }

                checkResult = (stopUseMask | stopDefMask) & checkLIR->defMask;

                /*
                 * If both instructions are verified Dalvik accesses, clear the
                 * may- and must-alias bits to detect true resource
                 * dependencies.
                 */
                if (checkResult & ENCODE_DALVIK_REG) {
                    checkResult &= ~(ENCODE_DALVIK_REG | ENCODE_FRAME_REF);
                }

                /*
                 * 2) load target register is clobbered
                 * 3) A branch is seen (stopUseMask has the PC bit set).
                 */
                if (checkResult) {
                    break;
                }

                /* Store data partially clobbers the Dalvik register */
                if (isDalvikStore(checkLIR) &&
                    isDalvikRegisterClobbered(thisLIR, checkLIR)) {
                    break;
                }
            }

            /* The load has been eliminated */
            if (thisLIR->flags.isNop) continue;

            /*
             * The load cannot be eliminated. See if it can be hoisted to an
             * earlier spot.
             */
            for (checkLIR = PREV_LIR(thisLIR);
                 /* empty by intention */;
                 checkLIR = PREV_LIR(checkLIR)) {

                if (checkLIR->flags.isNop) continue;

                /*
                 * Check if the "thisLIR" load is redundant
                 * NOTE: At one point, we also triggered if the checkLIR
                 * instruction was a load.  However, that tended to insert
                 * a load/use dependency because the full scheduler is
                 * not yet complete.  When it is, we chould also trigger
                 * on loads.
                 */
                if (isDalvikStore(checkLIR) &&
                    (checkLIR->aliasInfo == thisLIR->aliasInfo) &&
                    (REGTYPE(checkLIR->operands[0]) == REGTYPE(nativeRegId))) {
                    /* Insert a move to replace the load */
                    if (checkLIR->operands[0] != nativeRegId) {
                        ArmLIR *moveLIR;
                        moveLIR = dvmCompilerRegCopyNoInsert(
                                    cUnit, nativeRegId, checkLIR->operands[0]);
                        /*
                         * Convert *thisLIR* load into a move
                         */
                        dvmCompilerInsertLIRAfter((LIR *) checkLIR,
                                                  (LIR *) moveLIR);
                    }
                    thisLIR->flags.isNop = true;
                    break;

                /* Find out if the load can be yanked past the checkLIR */
                } else {
                    /* Last instruction reached */
                    bool stopHere = (checkLIR == headLIR);

                    /* Base address is clobbered by checkLIR */
                    checkResult = stopUseMask & checkLIR->defMask;
                    if (checkResult & ENCODE_DALVIK_REG) {
                        checkResult &= ~(ENCODE_DALVIK_REG | ENCODE_FRAME_REF);
                    }
                    stopHere |= (checkResult != 0);

                    /* Load target clobbers use/def in checkLIR */
                    checkResult = stopDefMask &
                                  (checkLIR->useMask | checkLIR->defMask);
                    if (checkResult & ENCODE_DALVIK_REG) {
                        checkResult &= ~(ENCODE_DALVIK_REG | ENCODE_FRAME_REF);
                    }
                    stopHere |= (checkResult != 0);

                    /* Store data partially clobbers the Dalvik register */
                    if (stopHere == false &&
                        (checkLIR->defMask & ENCODE_DALVIK_REG)) {
                        stopHere = isDalvikRegisterClobbered(thisLIR, checkLIR);
                    }

                    /*
                     * Stop at an earlier Dalvik load if the offset of checkLIR
                     * is not less than thisLIR
                     *
                     * Experiments show that doing
                     *
                     * ldr     r1, [r5, #16]
                     * ldr     r0, [r5, #20]
                     *
                     * is much faster than
                     *
                     * ldr     r0, [r5, #20]
                     * ldr     r1, [r5, #16]
                     */
                    if (isDalvikLoad(checkLIR)) {
                        int dRegId2 =
                            DECODE_ALIAS_INFO_REG(checkLIR->aliasInfo);
                        if (dRegId2 <= dRegId) {
                            stopHere = true;
                        }
                    }

                    /* Don't go too far */
                    stopHere |= (hoistDistance >= maxHoist);

                    /* Found a new place to put the load - move it here */
                    if (stopHere == true) {
                        DEBUG_OPT(dumpDependentInsnPair(thisLIR, checkLIR,
                                                        "HOIST LOAD"));
                        /* The load can be hoisted for at least one cycle */
                        if (hoistDistance != 0) {
                            ArmLIR *newLoadLIR =
                                (ArmLIR *)dvmCompilerNew(sizeof(ArmLIR), true);
                            *newLoadLIR = *thisLIR;
                            newLoadLIR->flags.age = cUnit->optRound;
                            /*
                             * Stop point found - insert *after* the checkLIR
                             * since the instruction list is scanned in the
                             * bottom-up order.
                             */
                            dvmCompilerInsertLIRAfter((LIR *) checkLIR,
                                                      (LIR *) newLoadLIR);
                            thisLIR->flags.isNop = true;
                        }
                        break;
                    }

                    /*
                     * Saw a real instruction that hosting the load is
                     * beneficial
                     */
                    if (!isPseudoOpcode(checkLIR->opcode)) {
                        hoistDistance++;
                    }
                }
            }
        } else if (isLiteralLoad(thisLIR)) {
            int litVal = thisLIR->aliasInfo;
            int nativeRegId = thisLIR->operands[0];
            ArmLIR *checkLIR;
            int hoistDistance = 0;
            u8 stopUseMask = (ENCODE_REG_PC | thisLIR->useMask) &
                             ~ENCODE_LITPOOL_REF;
            u8 stopDefMask = thisLIR->defMask & ~ENCODE_LITPOOL_REF;

            /* First check if the load can be completely elinimated */
            for (checkLIR = PREV_LIR(thisLIR);
                 checkLIR != headLIR;
                 checkLIR = PREV_LIR(checkLIR)) {

                if (checkLIR->flags.isNop) continue;

                /* Reloading same literal into same tgt reg? Eliminate if so */
                if (isLiteralLoad(checkLIR) &&
                    (checkLIR->aliasInfo == litVal) &&
                    (checkLIR->operands[0] == nativeRegId)) {
                    thisLIR->flags.isNop = true;
                    break;
                }

                /*
                 * No earlier use/def can reach this load if:
                 * 1) Head instruction is reached
                 * 2) load target register is clobbered
                 * 3) A branch is seen (stopUseMask has the PC bit set).
                 */
                if ((checkLIR == headLIR) ||
                    (stopUseMask | stopDefMask) & checkLIR->defMask) {
                    break;
                }
            }

            /* The load has been eliminated */
            if (thisLIR->flags.isNop) continue;

            /*
             * The load cannot be eliminated. See if it can be hoisted to an
             * earlier spot.
             */
            for (checkLIR = PREV_LIR(thisLIR);
                 /* empty by intention */;
                 checkLIR = PREV_LIR(checkLIR)) {

                if (checkLIR->flags.isNop) continue;

                /*
                 * TUNING: once a full scheduler exists, check here
                 * for conversion of a redundant load into a copy similar
                 * to the way redundant loads are handled above.
                 */

                /* Find out if the load can be yanked past the checkLIR */

                /* Last instruction reached */
                bool stopHere = (checkLIR == headLIR);

                /* Base address is clobbered by checkLIR */
                stopHere |= ((stopUseMask & checkLIR->defMask) != 0);

                /* Load target clobbers use/def in checkLIR */
                stopHere |= ((stopDefMask &
                             (checkLIR->useMask | checkLIR->defMask)) != 0);

                /* Avoid re-ordering literal pool loads */
                stopHere |= isLiteralLoad(checkLIR);

                /* Don't go too far */
                stopHere |= (hoistDistance >= maxHoist);

                /* Found a new place to put the load - move it here */
                if (stopHere == true) {
                    DEBUG_OPT(dumpDependentInsnPair(thisLIR, checkLIR,
                                                    "HOIST LOAD"));
                    /* The store can be hoisted for at least one cycle */
                    if (hoistDistance != 0) {
                        ArmLIR *newLoadLIR =
                            (ArmLIR *)dvmCompilerNew(sizeof(ArmLIR), true);
                        *newLoadLIR = *thisLIR;
                        newLoadLIR->flags.age = cUnit->optRound;
                        /*
                         * Insertion is guaranteed to succeed since checkLIR
                         * is never the first LIR on the list
                         */
                        dvmCompilerInsertLIRAfter((LIR *) checkLIR,
                                                  (LIR *) newLoadLIR);
                        thisLIR->flags.isNop = true;
                    }
                    break;
                }

                /*
                 * Saw a real instruction that hosting the load is
                 * beneficial
                 */
                if (!isPseudoOpcode(checkLIR->opcode)) {
                    hoistDistance++;
                }
            }
        }
    }
}

void dvmCompilerApplyLocalOptimizations(CompilationUnit *cUnit, LIR *headLIR,
                                        LIR *tailLIR)
{
    if (!(gDvmJit.disableOpt & (1 << kLoadStoreElimination))) {
        applyLoadStoreElimination(cUnit, (ArmLIR *) headLIR,
                                  (ArmLIR *) tailLIR);
    }
    if (!(gDvmJit.disableOpt & (1 << kLoadHoisting))) {
        applyLoadHoisting(cUnit, (ArmLIR *) headLIR, (ArmLIR *) tailLIR);
    }
}