/*
* 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 "MipsLIR.h"
#include "Codegen.h"
#define DEBUG_OPT(X)
/* Check RAW, WAR, and WAR dependency on the register operands */
#define CHECK_REG_DEP(use, def, check) ((def & check->useMask) || \
((use | def) & check->defMask))
/* Scheduler heuristics */
#define MAX_HOIST_DISTANCE 20
#define LDLD_DISTANCE 4
#define LD_LATENCY 2
static inline bool isDalvikRegisterClobbered(MipsLIR *lir1, MipsLIR *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(MipsLIR *thisLIR, MipsLIR *checkLIR,
const char *optimization)
{
LOGD("************ %s ************", optimization);
dvmDumpLIRInsn((LIR *) thisLIR, 0);
dvmDumpLIRInsn((LIR *) checkLIR, 0);
}
#endif
/* Convert a more expensive instruction (ie load) into a move */
static void convertMemOpIntoMove(CompilationUnit *cUnit, MipsLIR *origLIR,
int dest, int src)
{
/* Insert a move to replace the load */
MipsLIR *moveLIR;
moveLIR = dvmCompilerRegCopyNoInsert( cUnit, dest, src);
/*
* Insert the converted instruction after the original since the
* optimization is scannng in the top-down order and the new instruction
* will need to be re-checked (eg the new dest clobbers the src used in
* thisLIR).
*/
dvmCompilerInsertLIRAfter((LIR *) origLIR, (LIR *) moveLIR);
}
/*
* Perform a pass of top-down walk, from the second-last instruction in the
* superblock, to eliminate redundant loads and stores.
*
* An earlier load can eliminate a later load iff
* 1) They are must-aliases
* 2) The native register is not clobbered in between
* 3) The memory location is not written to in between
*
* An earlier store can eliminate a later load iff
* 1) They are must-aliases
* 2) The native register is not clobbered in between
* 3) The memory location is not written to in between
*
* A later store can be eliminated by an earlier store iff
* 1) They are must-aliases
* 2) The memory location is not written to in between
*/
static void applyLoadStoreElimination(CompilationUnit *cUnit,
MipsLIR *headLIR,
MipsLIR *tailLIR)
{
MipsLIR *thisLIR;
if (headLIR == tailLIR) return;
for (thisLIR = PREV_LIR(tailLIR);
thisLIR != headLIR;
thisLIR = PREV_LIR(thisLIR)) {
int sinkDistance = 0;
/* Skip non-interesting instructions */
if ((thisLIR->flags.isNop == true) ||
isPseudoOpCode(thisLIR->opcode) ||
!(EncodingMap[thisLIR->opcode].flags & (IS_LOAD | IS_STORE))) {
continue;
}
int nativeRegId = thisLIR->operands[0];
bool isThisLIRLoad = EncodingMap[thisLIR->opcode].flags & IS_LOAD;
MipsLIR *checkLIR;
/* Use the mem mask to determine the rough memory location */
u8 thisMemMask = (thisLIR->useMask | thisLIR->defMask) & ENCODE_MEM;
/*
* Currently only eliminate redundant ld/st for constant and Dalvik
* register accesses.
*/
if (!(thisMemMask & (ENCODE_LITERAL | ENCODE_DALVIK_REG))) continue;
/*
* Add r15 (pc) to the resource mask to prevent this instruction
* from sinking past branch instructions. Also take out the memory
* region bits since stopMask is used to check data/control
* dependencies.
*/
u8 stopUseRegMask = (ENCODE_REG_PC | thisLIR->useMask) &
~ENCODE_MEM;
u8 stopDefRegMask = thisLIR->defMask & ~ENCODE_MEM;
for (checkLIR = NEXT_LIR(thisLIR);
checkLIR != tailLIR;
checkLIR = NEXT_LIR(checkLIR)) {
/*
* Skip already dead instructions (whose dataflow information is
* outdated and misleading).
*/
if (checkLIR->flags.isNop) continue;
u8 checkMemMask = (checkLIR->useMask | checkLIR->defMask) &
ENCODE_MEM;
u8 aliasCondition = thisMemMask & checkMemMask;
bool stopHere = false;
/*
* Potential aliases seen - check the alias relations
*/
if (checkMemMask != ENCODE_MEM && aliasCondition != 0) {
bool isCheckLIRLoad = EncodingMap[checkLIR->opcode].flags &
IS_LOAD;
if (aliasCondition == ENCODE_LITERAL) {
/*
* Should only see literal loads in the instruction
* stream.
*/
assert(!(EncodingMap[checkLIR->opcode].flags &
IS_STORE));
/* Same value && same register type */
if (checkLIR->aliasInfo == thisLIR->aliasInfo &&
REGTYPE(checkLIR->operands[0]) == REGTYPE(nativeRegId)){
/*
* Different destination register - insert
* a move
*/
if (checkLIR->operands[0] != nativeRegId) {
convertMemOpIntoMove(cUnit, checkLIR,
checkLIR->operands[0],
nativeRegId);
}
checkLIR->flags.isNop = true;
}
} else if (aliasCondition == ENCODE_DALVIK_REG) {
/* Must alias */
if (checkLIR->aliasInfo == thisLIR->aliasInfo) {
/* Only optimize compatible registers */
bool regCompatible =
REGTYPE(checkLIR->operands[0]) ==
REGTYPE(nativeRegId);
if ((isThisLIRLoad && isCheckLIRLoad) ||
(!isThisLIRLoad && isCheckLIRLoad)) {
/* RAR or RAW */
if (regCompatible) {
/*
* Different destination register -
* insert a move
*/
if (checkLIR->operands[0] !=
nativeRegId) {
convertMemOpIntoMove(cUnit,
checkLIR,
checkLIR->operands[0],
nativeRegId);
}
checkLIR->flags.isNop = true;
} else {
/*
* Destinaions are of different types -
* something complicated going on so
* stop looking now.
*/
stopHere = true;
}
} else if (isThisLIRLoad && !isCheckLIRLoad) {
/* WAR - register value is killed */
stopHere = true;
} else if (!isThisLIRLoad && !isCheckLIRLoad) {
/* WAW - nuke the earlier store */
thisLIR->flags.isNop = true;
stopHere = true;
}
/* Partial overlap */
} else if (isDalvikRegisterClobbered(thisLIR, checkLIR)) {
/*
* It is actually ok to continue if checkLIR
* is a read. But it is hard to make a test
* case for this so we just stop here to be
* conservative.
*/
stopHere = true;
}
}
/* Memory content may be updated. Stop looking now. */
if (stopHere) {
break;
/* The checkLIR has been transformed - check the next one */
} else if (checkLIR->flags.isNop) {
continue;
}
}
/*
* this and check LIRs have no memory dependency. Now check if
* their register operands have any RAW, WAR, and WAW
* dependencies. If so, stop looking.
*/
if (stopHere == false) {
stopHere = CHECK_REG_DEP(stopUseRegMask, stopDefRegMask,
checkLIR);
}
if (stopHere == true) {
DEBUG_OPT(dumpDependentInsnPair(thisLIR, checkLIR,
"REG CLOBBERED"));
/* Only sink store instructions */
if (sinkDistance && !isThisLIRLoad) {
MipsLIR *newStoreLIR =
(MipsLIR *) dvmCompilerNew(sizeof(MipsLIR), true);
*newStoreLIR = *thisLIR;
/*
* 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;
} else if (!checkLIR->flags.isNop) {
sinkDistance++;
}
}
}
}
/*
* Perform a pass of bottom-up walk, from the second instruction in the
* superblock, to try to hoist loads to earlier slots.
*/
static void applyLoadHoisting(CompilationUnit *cUnit,
MipsLIR *headLIR,
MipsLIR *tailLIR)
{
MipsLIR *thisLIR, *checkLIR;
/*
* Store the list of independent instructions that can be hoisted past.
* Will decide the best place to insert later.
*/
MipsLIR *prevInstList[MAX_HOIST_DISTANCE];
/* Empty block */
if (headLIR == tailLIR) return;
/* Start from the second instruction */
for (thisLIR = NEXT_LIR(headLIR);
thisLIR != tailLIR;
thisLIR = NEXT_LIR(thisLIR)) {
/* Skip non-interesting instructions */
if ((thisLIR->flags.isNop == true) ||
isPseudoOpCode(thisLIR->opcode) ||
!(EncodingMap[thisLIR->opcode].flags & IS_LOAD)) {
continue;
}
u8 stopUseAllMask = thisLIR->useMask;
/*
* Branches for null/range checks are marked with the true resource
* bits, and loads to Dalvik registers, constant pools, and non-alias
* locations are safe to be hoisted. So only mark the heap references
* conservatively here.
*/
if (stopUseAllMask & ENCODE_HEAP_REF) {
stopUseAllMask |= ENCODE_REG_PC;
}
/* Similar as above, but just check for pure register dependency */
u8 stopUseRegMask = stopUseAllMask & ~ENCODE_MEM;
u8 stopDefRegMask = thisLIR->defMask & ~ENCODE_MEM;
int nextSlot = 0;
bool stopHere = false;
/* Try to hoist the load to a good spot */
for (checkLIR = PREV_LIR(thisLIR);
checkLIR != headLIR;
checkLIR = PREV_LIR(checkLIR)) {
/*
* Skip already dead instructions (whose dataflow information is
* outdated and misleading).
*/
if (checkLIR->flags.isNop) continue;
u8 checkMemMask = checkLIR->defMask & ENCODE_MEM;
u8 aliasCondition = stopUseAllMask & checkMemMask;
stopHere = false;
/* Potential WAR alias seen - check the exact relation */
if (checkMemMask != ENCODE_MEM && aliasCondition != 0) {
/* We can fully disambiguate Dalvik references */
if (aliasCondition == ENCODE_DALVIK_REG) {
/* Must alias or partually overlap */
if ((checkLIR->aliasInfo == thisLIR->aliasInfo) ||
isDalvikRegisterClobbered(thisLIR, checkLIR)) {
stopHere = true;
}
/* Conservatively treat all heap refs as may-alias */
} else {
assert(aliasCondition == ENCODE_HEAP_REF);
stopHere = true;
}
/* Memory content may be updated. Stop looking now. */
if (stopHere) {
prevInstList[nextSlot++] = checkLIR;
break;
}
}
if (stopHere == false) {
stopHere = CHECK_REG_DEP(stopUseRegMask, stopDefRegMask,
checkLIR);
}
/*
* Store the dependent or non-pseudo/indepedent instruction to the
* list.
*/
if (stopHere || !isPseudoOpCode(checkLIR->opcode)) {
prevInstList[nextSlot++] = checkLIR;
if (nextSlot == MAX_HOIST_DISTANCE) break;
}
/* Found a new place to put the load - move it here */
if (stopHere == true) {
DEBUG_OPT(dumpDependentInsnPair(checkLIR, thisLIR
"HOIST STOP"));
break;
}
}
/*
* Reached the top - use headLIR as the dependent marker as all labels
* are barriers.
*/
if (stopHere == false && nextSlot < MAX_HOIST_DISTANCE) {
prevInstList[nextSlot++] = headLIR;
}
/*
* At least one independent instruction is found. Scan in the reversed
* direction to find a beneficial slot.
*/
if (nextSlot >= 2) {
int firstSlot = nextSlot - 2;
int slot;
MipsLIR *depLIR = prevInstList[nextSlot-1];
/* If there is ld-ld dependency, wait LDLD_DISTANCE cycles */
if (!isPseudoOpCode(depLIR->opcode) &&
(EncodingMap[depLIR->opcode].flags & IS_LOAD)) {
firstSlot -= LDLD_DISTANCE;
}
/*
* Make sure we check slot >= 0 since firstSlot may be negative
* when the loop is first entered.
*/
for (slot = firstSlot; slot >= 0; slot--) {
MipsLIR *curLIR = prevInstList[slot];
MipsLIR *prevLIR = prevInstList[slot+1];
/*
* Check the highest instruction.
* ENCODE_ALL represents a scheduling barrier.
*/
if (prevLIR->defMask == ENCODE_ALL) {
/*
* If the first instruction is a load, don't hoist anything
* above it since it is unlikely to be beneficial.
*/
if (EncodingMap[curLIR->opcode].flags & IS_LOAD) continue;
/*
* Need to unconditionally break here even if the hoisted
* distance is greater than LD_LATENCY (ie more than enough
* cycles are inserted to hide the load latency) since theu
* subsequent code doesn't expect to compare against a
* pseudo opcode (whose opcode value is negative).
*/
break;
}
/*
* NOTE: now prevLIR is guaranteed to be a non-pseudo
* instruction (ie accessing EncodingMap[prevLIR->opcode] is
* safe).
*
* Try to find two instructions with load/use dependency until
* the remaining instructions are less than LD_LATENCY.
*/
if (((curLIR->useMask & prevLIR->defMask) &&
(EncodingMap[prevLIR->opcode].flags & IS_LOAD)) ||
(slot < LD_LATENCY)) {
break;
}
}
/* Found a slot to hoist to */
if (slot >= 0) {
MipsLIR *curLIR = prevInstList[slot];
MipsLIR *newLoadLIR = (MipsLIR *) dvmCompilerNew(sizeof(MipsLIR),
true);
*newLoadLIR = *thisLIR;
/*
* Insertion is guaranteed to succeed since checkLIR
* is never the first LIR on the list
*/
dvmCompilerInsertLIRBefore((LIR *) curLIR,
(LIR *) newLoadLIR);
thisLIR->flags.isNop = true;
}
}
}
}
void dvmCompilerApplyLocalOptimizations(CompilationUnit *cUnit, LIR *headLIR,
LIR *tailLIR)
{
if (!(gDvmJit.disableOpt & (1 << kLoadStoreElimination))) {
applyLoadStoreElimination(cUnit, (MipsLIR *) headLIR,
(MipsLIR *) tailLIR);
}
if (!(gDvmJit.disableOpt & (1 << kLoadHoisting))) {
applyLoadHoisting(cUnit, (MipsLIR *) headLIR, (MipsLIR *) tailLIR);
}
}