/*
* 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->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->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->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 =
dvmCompilerNew(sizeof(ArmLIR), true);
*newStoreLIR = *thisLIR;
newStoreLIR->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->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->age >= cUnit->optRound ||
thisLIR->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->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->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->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->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->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 =
dvmCompilerNew(sizeof(ArmLIR), true);
*newLoadLIR = *thisLIR;
newLoadLIR->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->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->isNop) continue;
/* Reloading same literal into same tgt reg? Eliminate if so */
if (isLiteralLoad(checkLIR) &&
(checkLIR->aliasInfo == litVal) &&
(checkLIR->operands[0] == nativeRegId)) {
thisLIR->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->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->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 =
dvmCompilerNew(sizeof(ArmLIR), true);
*newLoadLIR = *thisLIR;
newLoadLIR->age = cUnit->optRound;
/*
* Insertion is guaranteed to succeed since checkLIR
* is never the first LIR on the list
*/
dvmCompilerInsertLIRAfter((LIR *) checkLIR,
(LIR *) newLoadLIR);
thisLIR->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);
}
}