Google Git
Sign in
apache / harmony-drlvm / 5f88006f0f0d0333d92de8857cbb9a9e9a486afe / . / vm / jitrino / src / optimizer / memoryopt.cpp
blob: 4c3fceeb6009488556757440c3b4cf4fd04c2139 [file] [log] [blame]
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You 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.
*/
/**
* @author Intel, Pavel A. Ozhdikhin
*
*/
#include <assert.h>
#include <iostream>
#include <algorithm>
#include "Stl.h"
#include "Log.h"
#include "open/types.h"
#include "Inst.h"
#include "irmanager.h"
#include "Dominator.h"
#include "Loop.h"
#include "Opcode.h"
#include "walkers.h"
#include "optpass.h"
#include "opndmap.h"
#include "memoryopt.h"
#include "aliasanalyzer.h"
#include "memoryoptrep.h"
#include "./ssa/SSA.h"
#include "XTimer.h"
#include "hashvaluenumberer.h"
namespace Jitrino {
DEFINE_SESSION_ACTION(MemoryValueNumberingPass, memopt, "Redundant Ld-St Elimination")
void
MemoryValueNumberingPass::_run(IRManager& irm) {
computeDominators(irm);
DominatorTree* dominatorTree = irm.getDominatorTree();
assert(dominatorTree && dominatorTree->isValid());
computeLoops(irm);
LoopTree* loopTree = irm.getLoopTree();
assert(loopTree && loopTree->isValid());
ControlFlowGraph& flowGraph = irm.getFlowGraph();
MemoryManager& memoryManager = irm.getNestedMemoryManager();
DomFrontier frontier(memoryManager,*dominatorTree,&flowGraph);
TypeAliasAnalyzer aliasAnalyzer;
MemoryOpt mopt(irm, memoryManager, *dominatorTree,
frontier, loopTree, &aliasAnalyzer);
mopt.runPass();
HashValueNumberer valueNumberer(irm, *dominatorTree);
valueNumberer.doValueNumbering(&mopt);
bool do_redstore = irm.getOptimizerFlags().memOptFlags->do_redstore;
if (do_redstore) {
mopt.eliminateRedStores();
}
}
MemoryOpt::MemoryOpt(IRManager &irManager0,
MemoryManager& memManager,
DominatorTree& dom0,
DomFrontier& df0,
LoopTree *loopTree0,
AliasAnalyzer *aa0)
: irManager(irManager0),
fg(irManager0.getFlowGraph()),
mm(memManager),
dominators(dom0),
df(df0),
loopTree(loopTree0),
aliasManager(new (memManager) AliasManager(memManager, aa0, &irManager0.getTypeManager())),
instDoesWhat(new Inst2MemBehavior(memManager)),
aliasDefSites(0),
memPhiSites(0),
renameMap(0),
memUseDefs(memManager),
memDefUses(memManager),
flags(*irManager.getOptimizerFlags().memOptFlags)
{
assert(aliasManager);
U_32 numNodes = df0.getNumNodes();
aliasDefSites = new (mm) AliasDefSites(mm, numNodes);
memPhiSites = new (mm) MemPhiSites(mm, numNodes);
renameMap = new (mm) AliasRenameMap(mm, aliasManager,
2*numNodes,
2*numNodes);
}
MemoryOpt::~MemoryOpt()
{
}
void
MemoryOpt::readFlags(Action* argSource, MemoptFlags* flags)
{
IAction::HPipeline p = NULL; //default pipeline for argSource
const char *res = argSource->getStringArg(p, "memopt.mm", NULL);
flags->model = Model_Default;
if (res) {
if (strncmp(res,"strict",7)==0) {
flags->model = Model_Strict;
} else if (strncmp(res,"reads_kill",11)==0) {
flags->model = Model_ReadsKill;
} else if (strncmp(res,"cse_final",9)==0) {
flags->model = Model_CseFinal;
}
}
res = argSource->getStringArg(p, "memopt.synch", NULL);
flags->synch = Synch_Default;
if (res) {
if (strncmp(res,"fence", 6)==0) {
flags->synch = Synch_Fence;
} else if (strncmp(res,"moveable", 9)==0) {
flags->synch = Synch_Moveable;
} else if (strncmp(res,"only_lock", 10)==0) {
flags->synch = Synch_OnlyLock;
} else if (strncmp(res,"one_thread", 11)==0) {
flags->synch = Synch_OneThread;
}
}
flags->debug = argSource->getBoolArg(p, "memopt.debug", false);
flags->verbose = argSource->getBoolArg(p, "memopt.verbose", false);
flags->redstore = argSource->getBoolArg(p, "memopt.redstore", false);
flags->syncopt = argSource->getBoolArg(p, "memopt.syncopt", false);
flags->do_redstore = argSource->getBoolArg(p, "memopt.do_redstore", true);
}
void MemoryOpt::showFlags(std::ostream& os) {
os << " memopt flags:"<<std::endl;
os << " memopt.mm=strict - no memory optimizations" << std::endl;
os << " memopt.mm=reads_kill - reads kill" << std::endl;
os << " memopt.mm=cse_final - allow final field CSEing, maybe hoisting" << std::endl;
os << " memopt.synch=fence - no memory ops move past lock/unlock" << std::endl;
os << " memopt.synch=moveable - load/store movement into locks allowed" << std::endl;
os << " memopt.synch=only_lock - eliminable local objects not treated as fence" << std::endl;
os << " memopt.synch=one_thread - locks and fences elided freely" << std::endl;
os << " memopt.debug[={ON,off}] - debug memory opts" << std::endl;
os << " memopt.verbose[={ON,off}] - verbose memory opt output" << std::endl;
os << " memopt.redstore[={on,OFF}] - try to eliminate redundant stores" << std::endl;
os << " memopt.syncopt[={on,OFF}] - turn exit/enter into fences" << std::endl;
}
static CountTime memoptPhase1Timer("opt::mem::phase1"); // not thread-safe
static CountTime memoptPhase2Timer("opt::mem::phase2"); // not thread-safe
static CountTime memoptPhase3Timer("opt::mem::phase3"); // not thread-safe
void MemoryOpt::runPass()
{
if (Log::isEnabled()) {
Log::out() << "Starting MemoryOpt Pass" << std::endl;
}
// initialize iDef, iUse for each instr, build initial set of locations
{
AutoTimer t(memoptPhase1Timer);
initMemoryOperations();
}
// walk dominator tree in pre-order,
// building MustDef, MayDef, MustUse for each instruction
// (1) when we see iDef=loc at instruction i
// create loc1 = new SsaMemOpnd(loc), defined by i
// set renameTable(loc)=loc1
// set MustDef(i)=loc1
// (2) for each loc'!=loc defined in renameTable s.t. mayalias(loc',loc)
// create loc'' = AliasSet(loc,loc')
// create loc2 = new SsaMemOpnd(loc''), defined by i
// set renameTable(loc') = loc2
// set MayDef(i)=loc2
// (3) when we see iUse=loc at instruction i
// if lookup loc3=renameTable(loc) is defined
// set MayUse(i)=loc3
// if reads_kill, then also see (3)
// (4) when we enter a block, consider the iPhi functions on the block:
// for each loc=iPhi(loc1,loc2,...),
//
//
if (flags.redstore) {
if (Log::isEnabled()) {
Log::out() << "Trying redundant store elimination" << std::endl;
}
AutoTimer t(memoptPhase2Timer);
eliminateRedStores();
}
if (Log::isEnabled()) {
Log::out() << "Finished MemoryOpt Pass" << std::endl;
}
if (flags.syncopt) {
AutoTimer t(memoptPhase3Timer);
if (Log::isEnabled()) {
Log::out() << "Trying synchronization optimization" << std::endl;
}
doSyncOpt();
}
if (Log::isEnabled()) {
Log::out() << "Finished synchronization optimization" << std::endl;
}
}
// a NodeInstWalker, backwards over instructions
class MemoryOptInitWalker {
MemoryOpt *thePass;
Node *n;
public:
MemoryOptInitWalker(MemoryOpt *thePass0) :
thePass(thePass0), n(0)
{ };
void startNode(Node *node) { n = node; };
void applyToInst(Inst *inst);
void finishNode(Node *node) {};
};
// Phase 1: for each memory access, get an description of the set of
// memory locations which must be considered with it.
static CountTime memoptPhase1bTimer("opt::mem::phase1b"); // not thread-safe
static CountTime memoptPhase1cTimer("opt::mem::phase1c"); // not thread-safe
static CountTime memoptPhase1dTimer("opt::mem::phase1d"); // not thread-safe
void MemoryOpt::initMemoryOperations()
{
// initialize memory locations read/written by each instruction
MemoryOptInitWalker initWalker(this);
typedef NodeInst2NodeWalker<false, MemoryOptInitWalker> InitNodeWalker;
InitNodeWalker initNodeWalker(initWalker);
if (Log::isEnabled()) {
Log::out() << std::endl << "Instruction Memory Effects:" << std::endl;
}
{
AutoTimer t(memoptPhase1bTimer);
// have the first inst, define Any for renaming walk
DominatorNode *domRoot = dominators.getDominatorRoot();
Node *cfgRoot = domRoot->getNode();
Inst *firstInst = (Inst*)cfgRoot->getFirstInst();
assert(firstInst->isLabel());
AliasRep escapingMem = aliasManager->getAny();
renameMap->insert(escapingMem, firstInst);
}
{
AutoTimer t(memoptPhase1cTimer);
// walk over all instructions, inserting memory effects
NodeWalk<InitNodeWalker>(fg, initNodeWalker);
if (Log::isEnabled()) {
Log::out() << std::endl << "END of Instruction Memory Effects" << std::endl;
}
insertMemPhi();
}
if (Log::isEnabled()) {
aliasManager->dumpAliasReps(Log::out());
}
{
AutoTimer t(memoptPhase1dTimer);
createUsesMap();
}
}
/*
0. MemOpnd has
- ptr to address operand(s) read/written
- ptr to defining instruction (normal opt) or block (for a phi)
1. each memory-altering instr at node n
generates a unique MemOpnd,
adds a memPhi node with new MemOpnd at each element of DF+(n)
uses a uniqe MemOpnd
? adds a memSplit node with new input MemOpnd at each element
? of PDF+(n)
2. walk dominator tree in pre-order, carrying set L of live MemOpnd
(1) at each memory instruction i,
(a) consider input MemOpnd mo_in, find narrowest mo_1 in L
containing the mo_in
- union(mo_in, mo_1)
(b) consider output MemOpnd mo_out
- remove from L any mo_l contained in mo_out
- add mo_out to L
(2) at each outedge leading to a memPhi node for mo_in,
(a) find the narrowest mo_l in L containing mo_in, add
mo_l as a parameter to the memPhi
(3) for each inedge leading from a memSplit node with outedge
mo_out, add mo_out to L
*/
InstMemBehavior *
MemoryOpt::getInstEffect(Inst *i)
{
Inst2MemBehavior::iterator
found = instDoesWhat->find(i),
end = instDoesWhat->end();
if (found != end) {
return (*found).second;
} else {
return 0;
}
}
InstMemBehavior *
MemoryOpt::getOrCreateInstEffect(Inst *i)
{
Inst2MemBehavior::iterator
found = instDoesWhat->find(i),
end = instDoesWhat->end();
if (found != end) {
return (*found).second;
} else {
InstMemBehavior *imb = new (mm) InstMemBehavior(mm);
(*instDoesWhat)[i] = imb;
return imb;
}
}
// R/W anything that escapes or is global
void MemoryOpt::effectAnyGlobal(Node *n, Inst *i)
{
AliasRep anyGlobal = aliasManager->getAnyGlobal();
addUseToInstruction(n, i, anyGlobal);
addDefToInstruction(n, i, anyGlobal);
}
// writes opnd.vptr
void MemoryOpt::effectWriteVtable(Node *n, Inst *i, Opnd *opnd)
{
AliasRep vtblMemory = aliasManager->getVtableOf(opnd);
addDefToInstruction(n, i, vtblMemory);
}
void MemoryOpt::effectReadVtable(Node *n, Inst *i, Opnd *opnd)
{
AliasRep vtblMemory = aliasManager->getVtableOf(opnd);
addUseToInstruction(n, i, vtblMemory);
}
void MemoryOpt::effectReadMethodPtr(Node *n, Inst *i, Opnd *obj, MethodDesc *desc)
{
AliasRep methodPtrMem = aliasManager->getMethodPtr(obj, desc);
addUseToInstruction(n, i, methodPtrMem);
}
void MemoryOpt::effectReadMethodPtr(Node *n, Inst *i, MethodDesc *desc)
{
NamedType *theType = desc->getParentType();
AliasRep typeVtable = aliasManager->getVtableOf(theType);
addUseToInstruction(n, i, typeVtable);
}
void MemoryOpt::effectReadFunPtr(Node *n, Inst *i, Opnd *fnptr)
{
}
void MemoryOpt::effectExit(Node *n, Inst *i)
{
AliasRep escapingMem = aliasManager->getAnyEscaping();
addUseToInstruction(n, i, escapingMem);
}
void MemoryOpt::effectInit(Node *n, Inst *i)
{
AliasRep escapingMem = aliasManager->getAny();
addDefToInstruction(n, i, escapingMem);
}
void MemoryOpt::effectEntry(Node *n, Inst *i)
{
AliasRep escapingMem = aliasManager->getAnyEscaping();
addDefToInstruction(n, i, escapingMem);
}
void MemoryOpt::effectRead(Node *n, Inst *i, Opnd *addr)
{
AliasRep thisMem = aliasManager->getReference(addr);
addUseToInstruction(n, i, thisMem);
}
void MemoryOpt::effectWrite(Node *n, Inst *i, Opnd *addr)
{
AliasRep thisMem = aliasManager->getReference(addr);
addDefToInstruction(n, i, thisMem);
}
void MemoryOpt::effectReadClassVtable(Node *n, Inst *i, NamedType *t)
{
AliasRep vtblMemory = aliasManager->getVtableOf(t);
addDefToInstruction(n, i, vtblMemory);
}
void MemoryOpt::effectWriteArrayLength(Node *n, Inst *i, Opnd *opnd)
{
AliasRep arrayLenMem = aliasManager->getArrayLen(opnd);
addDefToInstruction(n, i, arrayLenMem);
}
void MemoryOpt::effectReadArrayLength(Node *n, Inst *i, Opnd *opnd)
{
AliasRep arrayLenMem = aliasManager->getArrayLen(opnd);
addUseToInstruction(n, i, arrayLenMem);
}
void MemoryOpt::effectWriteArrayElements(Node *n, Inst *i, Opnd *array,
Opnd *offset, Opnd *length)
{
AliasRep arrayElemMem = aliasManager->getArrayElements(array, offset, length);
addDefToInstruction(n, i, arrayElemMem);
}
void MemoryOpt::effectReadArrayElements(Node *n, Inst *i, Opnd *array,
Opnd *offset, Opnd *length)
{
AliasRep arrayElemMem = aliasManager->getArrayElements(array, offset, length);
addUseToInstruction(n, i, arrayElemMem);
}
// creates an object/array, returned in opnd:
// writes array length, etc.
void MemoryOpt::effectNew(Node *n, Inst *i, Opnd *dstop)
{
AliasRep objInitMem = aliasManager->getObjectNew(dstop);
addDefToInstruction(n, i, objInitMem);
}
// make sure object's vtable are visible to others before publishing this
void MemoryOpt::effectReleaseObject(Node *n, Inst *i, Opnd *obj)
{
addReleaseToInstruction(n, i);
}
// make sure object's vtable is available to all
void MemoryOpt::effectInitType(Node *n, Inst *i, NamedType *type)
{
AliasRep typeInitMem = aliasManager->getTypeNew(type);
addDefToInstruction(n, i, typeInitMem);
}
// make sure object's vtable is available to all
void MemoryOpt::effectFinishObject(Node *n, Inst *i, Opnd *obj)
{
AliasRep objFinishMem = aliasManager->getFinishObject(obj);
addDefToInstruction(n, i, objFinishMem);
}
// make sure object's vtable is available to all
void MemoryOpt::effectFinishType(Node *n, Inst *i, NamedType *type)
{
AliasRep typeFinishMem = aliasManager->getFinishType(type);
addDefToInstruction(n, i, typeFinishMem);
}
// can commute with any ops, but not be added/removed:
void MemoryOpt::effectIncCounter(Node *n, Inst *i)
{
}
// object may be 0 if lock has been removed
void MemoryOpt::effectIncRecCount(Node *n, Inst *i, Opnd *object)
{
if (object) {
AliasRep thisMem = aliasManager->getLock(object);
addUseToInstruction(n, i, thisMem);
addDefToInstruction(n, i, thisMem);
}
}
// object may be 0 if lock has been removed
void MemoryOpt::effectMonitorEnter(Node *n, Inst *i, Opnd *object)
{
if (object) {
AliasRep thisMem = aliasManager->getLock(object);
addUseToInstruction(n, i, thisMem);
addDefToInstruction(n, i, thisMem);
}
addAcquireToInstruction(n, i);
}
void MemoryOpt::effectMonitorExit(Node *n, Inst *i, Opnd *object)
{
if (object) {
AliasRep thisMem = aliasManager->getLock(object);
addUseToInstruction(n, i, thisMem);
addDefToInstruction(n, i, thisMem);
}
addReleaseToInstruction(n, i);
}
// object may be 0 if lock has been removed
void MemoryOpt::effectTypeMonitorEnter(Node *n, Inst *i, Type *type)
{
assert(type);
AliasRep thisMem = aliasManager->getLock(type);
addUseToInstruction(n, i, thisMem);
addDefToInstruction(n, i, thisMem);
addAcquireToInstruction(n, i);
}
void MemoryOpt::effectTypeMonitorExit(Node *n, Inst *i, Type *type)
{
assert(type);
AliasRep thisMem = aliasManager->getLock(type);
addUseToInstruction(n, i, thisMem);
addDefToInstruction(n, i, thisMem);
addReleaseToInstruction(n, i);
}
void MemoryOpt::addDefToInstruction(Node *n, Inst *i, const AliasRep &thisMem)
{
InstMemBehavior *b = getOrCreateInstEffect(i);
b->defs.insert(thisMem);
if (Log::isEnabled()) {
Log::out() << "Inserting def for ";
thisMem.print(Log::out());
Log::out() << " at node ";
FlowGraph::printLabel(Log::out(), n);
Log::out() << std::endl;
}
// if there is already a definition of an ancestor of this one, then it
// hides this, so skip adding the def
const AliasManager::AliasList *alist = aliasManager->getAncestors(thisMem);
AliasManager::AliasList::const_iterator iter = alist->begin();
AliasManager::AliasList::const_iterator endIter = alist->end();
AliasDefSites::iterator end = aliasDefSites->end();
for ( ; iter != endIter; ++iter) {
AliasRep anc = *iter;
if (aliasDefSites->hasAliasDefSite(anc, n)) {
if (Log::isEnabled()) {
Log::out() << "Not recording def for ";
thisMem.print(Log::out());
Log::out() << " at node ";
FlowGraph::printLabel(Log::out(), n);
Log::out() << " because ancestor ";
anc.print(Log::out());
Log::out() << " has def there" << std::endl;
}
return;
}
}
// if there is no ancestor definition, add a definition for thisMem to the node.
aliasDefSites->addAliasDefSite(thisMem, n);
}
void MemoryOpt::addUseToInstruction(Node *n, Inst *i, const AliasRep &thisMem)
{
InstMemBehavior *b = getOrCreateInstEffect(i);
b->uses.insert(thisMem);
}
void MemoryOpt::addReleaseToInstruction(Node *n, Inst *i)
{
InstMemBehavior *b = getOrCreateInstEffect(i);
b->release = true;
}
void MemoryOpt::addAcquireToInstruction(Node *n, Inst *i)
{
InstMemBehavior *b = getOrCreateInstEffect(i);
b->acquire = true;
}
void
MemoryOptInitWalker::applyToInst(Inst *i)
{
switch (i->getOpcode()) {
case Op_DirectCall:
thePass->effectAnyGlobal(n, i); break;
case Op_TauVirtualCall:
{
// Src(0) and Src(1) are taus
// calls (i->getSrc(2)).method, if we ever get IPA
MethodCallInst *calli = i->asMethodCallInst();
thePass->effectReadVtable(n, i, i->getSrc(2));
thePass->effectReadMethodPtr(n, i, i->getSrc(2),
calli->getMethodDesc());
thePass->effectAnyGlobal(n, i);
}
break;
case Op_IndirectCall:
case Op_IndirectMemoryCall:
{
// calls i->getSrc(0), if we ever get IPA
thePass->effectReadFunPtr(n, i, i->getSrc(0));
thePass->effectAnyGlobal(n, i);
}
break;
case Op_VMHelperCall:
break;
case Op_JitHelperCall:
{
JitHelperCallInst *jitcalli = i->asJitHelperCallInst();
JitHelperCallId callId = jitcalli->getJitHelperId();
switch (callId) {
case Prefetch:
case Memset0:
case InitializeArray:
case SaveThisState:
case ReadThisState:
case LockedCompareAndExchange:
case AddValueProfileValue:
case ArrayCopyDirect:
case ArrayCopyReverse:
case StringCompareTo:
case StringIndexOf:
case StringRegionMatches:
case FillArrayWithConst:
case ClassIsArray:
case ClassGetAllocationHandle:
case ClassGetTypeSize:
case ClassGetArrayElemSize:
case ClassIsInterface:
case ClassIsFinal:
case ClassGetArrayClass:
case ClassIsFinalizable:
case ClassGetFastCheckDepth:
break;
default:
assert(0);
break;
}
}
break;
case Op_PseudoThrow:
break;
case Op_Return:
case Op_Throw:
case Op_ThrowSystemException:
case Op_ThrowLinkingException:
thePass->effectExit(n, i);
break;
case Op_Catch:
thePass->effectEntry(n, i);
break;
case Op_Prefetch:
case Op_Ret:
case Op_SaveRet:
case Op_JSR:
break;
case Op_TauLdInd:
thePass->effectRead(n, i, i->getSrc(0));
break;
case Op_TauLdIntfcVTableAddr:
{
TypeInst *typeInst = i->asTypeInst();
Type *vtableType = typeInst->getTypeInfo();
assert(vtableType->isUserObject());
NamedType *namedType = (NamedType*)vtableType;
thePass->effectReadClassVtable(n, i, namedType);
thePass->effectReadVtable(n, i, i->getSrc(0));
}
break;
case Op_TauLdVirtFunAddr:
case Op_TauLdVirtFunAddrSlot:
{
Opnd *vtableOpnd = i->getSrc(0);
thePass->effectRead(n, i, vtableOpnd);
}
break;
case Op_LdFunAddr:
case Op_LdFunAddrSlot:
{
MethodInst *methodInst = i->asMethodInst();
MethodDesc *methodDesc = methodInst->getMethodDesc();
thePass->effectReadMethodPtr(n, i, methodDesc);
}
break;
case Op_TauArrayLen:
{
thePass->effectReadArrayLength(n, i, i->getSrc(0));
}
break;
case Op_TauStInd:
{
thePass->effectWrite(n, i, i->getSrc(1));
}
break;
case Op_TauStRef:
{
thePass->effectWrite(n, i, i->getSrc(1));
}
break;
case Op_TauCheckElemType:
{
thePass->effectReadVtable(n, i, i->getSrc(0)); // array
thePass->effectReadVtable(n, i, i->getSrc(1)); // to store
}
break;
case Op_NewObj:
{
thePass->effectNew(n, i, i->getDst());
thePass->effectWriteVtable(n, i, i->getDst());
thePass->effectReleaseObject(n, i, i->getDst());
}
break;
case Op_NewMultiArray:
case Op_NewArray:
{
thePass->effectNew(n, i, i->getDst());
thePass->effectWriteVtable(n, i, i->getDst());
thePass->effectWriteArrayLength(n, i, i->getDst());
thePass->effectReleaseObject(n, i, i->getDst());
}
break;
case Op_GetClassObj:
{
thePass->effectNew(n, i, i->getDst());
thePass->effectWriteVtable(n, i, i->getDst());
thePass->effectReleaseObject(n, i, i->getDst());
}
break;
case Op_TypeMonitorEnter:
{
TypeInst *tinst = i->asTypeInst();
Type *thetype = tinst->getTypeInfo();
thePass->effectTypeMonitorEnter(n, i, thetype);
}
break;
case Op_TypeMonitorExit:
{
TypeInst *tinst = i->asTypeInst();
Type *thetype = tinst->getTypeInfo();
thePass->effectTypeMonitorExit(n, i, thetype);
}
break;
case Op_TauMonitorEnter:
{
thePass->effectMonitorEnter(n, i, i->getSrc(0));
}
break;
case Op_TauMonitorExit:
{
thePass->effectMonitorExit(n, i, i->getSrc(0));
}
break;
case Op_LdLockAddr:
// just an address computation
break;
case Op_IncRecCount:
// just an address computation
break;
case Op_TauBalancedMonitorEnter:
{
thePass->effectMonitorEnter(n, i, i->getSrc(0));
}
break;
case Op_BalancedMonitorExit:
{
thePass->effectMonitorExit(n, i, i->getSrc(0));
}
break;
case Op_TauOptimisticBalancedMonitorEnter:
{
thePass->effectMonitorEnter(n, i, i->getSrc(0));
}
break;
case Op_OptimisticBalancedMonitorExit:
{
thePass->effectMonitorExit(n, i, i->getSrc(0));
}
break;
case Op_MonitorEnterFence:
{
thePass->effectMonitorEnter(n, i, 0);
}
break;
case Op_MonitorExitFence:
{
thePass->effectMonitorExit(n, i, 0);
}
break;
case Op_TauCast:
case Op_TauAsType:
case Op_TauInstanceOf:
case Op_TauCheckCast:
{
thePass->effectReadVtable(n, i, i->getSrc(0));
}
break;
case Op_InitType:
{
TypeInst *typeInst = i->asTypeInst();
thePass->effectAnyGlobal(n, i); // could modify unrelated globals
thePass->effectInitType(n, i, (NamedType *)typeInst->getTypeInfo());
}
break;
case Op_MethodEntry:
// this is just a marker for an inlined method, don't use the following effect:
// thePass->effectEntry(n, i);
break;
case Op_MethodEnd:
{
MethodMarkerInst *mmi = i->asMethodMarkerInst();
assert(mmi);
MethodDesc *md = mmi->getMethodDesc();
if (md->isInstanceInitializer()) {
if (mmi->getNumSrcOperands() == 1) {
Opnd *obj = mmi->getSrc(0);
thePass->effectFinishObject(n, i, obj);
} else {
// static method, skip it
}
} else if (md->isClassInitializer()) {
thePass->effectFinishType(n, i, md->getParentType());
}
}
break;
case Op_IncCounter:
thePass->effectIncCounter(n, i);
break;
// loads vtable from object, depends on object initialization
case Op_TauLdVTableAddr:
// THE FOLLOWING ARE JUST ADDRESS COMPUTATIONS
case Op_LdVarAddr:
// mark Var as addr_taken
case Op_LdFieldAddr:
case Op_LdStaticAddr:
case Op_LdElemAddr:
case Op_GetVTableAddr:
case Op_LdArrayBaseAddr:
case Op_AddScaledIndex:
case Op_UncompressRef:
case Op_CompressRef:
case Op_LdFieldOffset:
case Op_LdFieldOffsetPlusHeapbase:
case Op_LdArrayBaseOffset:
case Op_LdArrayBaseOffsetPlusHeapbase:
case Op_LdArrayLenOffset:
case Op_LdArrayLenOffsetPlusHeapbase:
case Op_AddOffset:
case Op_AddOffsetPlusHeapbase:
// the following are irrelevant, but cased so we
// notice any additions:
case Op_Add: case Op_Mul: case Op_Sub: case Op_TauDiv: case Op_TauRem:
case Op_Neg: case Op_MulHi: case Op_Min: case Op_Max: case Op_Abs:
case Op_And: case Op_Or: case Op_Xor:
case Op_Not: case Op_Select: case Op_Conv: case Op_ConvZE: case Op_ConvUnmanaged: case Op_Shladd: case Op_Shl:
case Op_Shr: case Op_Cmp: case Op_Cmp3:
case Op_Branch: case Op_Jump: case Op_Switch:
case Op_LdConstant:
case Op_LdRef: // helper call to load a constant, no memory effect.
case Op_Copy:
case Op_StVar:
case Op_LdVar:
// Reads a variable; may need to check for addr-taken
case Op_DefArg:
// Reads stack; may need to check for addr-taken
case Op_TauCheckBounds: case Op_TauCheckLowerBound: case Op_TauCheckUpperBound:
case Op_TauCheckNull: case Op_TauCheckZero: case Op_TauCheckDivOpnds:
case Op_TauCheckFinite:
case Op_TauStaticCast: // just a compile-time assertion
case Op_Label:
case Op_Phi:
case Op_TauPi:
case Op_TauPoint:
case Op_TauEdge:
case Op_TauAnd:
case Op_TauUnsafe:
case Op_TauSafe:
case Op_TauHasType:
case Op_TauHasExactType:
case Op_TauIsNonNull:
break;
//case Op_TauStRef:
// assert(0);
case Op_TauLdField:
case Op_LdStatic:
case Op_TauLdElem:
case Op_TauStField:
case Op_TauStElem:
case Op_TauStStatic:
assert(0);
break;
default:
assert(0);
break;
}
if (Log::isEnabled()) {
Log::out() << "Inst "; i->print(Log::out());
Log::out() << std::endl;
InstMemBehavior *b = thePass->getInstEffect(i);
if (b) {
StlVectorSet<AliasRep>::iterator
iter1 = b->defs.begin(),
end1 = b->defs.end();
if (iter1 != end1) {
Log::out() << " def: ";
for ( ; iter1 != end1; iter1++) {
const AliasRep &rep = *iter1;
rep.dump(Log::out());
Log::out() << " ";
}
Log::out() << std::endl;
}
StlVectorSet<AliasRep>::iterator
iter2 = b->uses.begin(),
end2 = b->uses.end();
if (iter2 != end2) {
Log::out() << " use: ";
for ( ; iter2 != end2; iter2++) {
const AliasRep &rep = *iter2;
rep.dump(Log::out());
Log::out() << " ";
}
Log::out() << std::endl;
}
}
}
}
bool AliasManager::mayAlias(const AliasRep &a, const AliasRep &b)
{
if ((a.kind == AliasRep::NullKind) || (b.kind == AliasRep::NullKind)) return false;
if ((a.kind == AliasRep::AnyKind) || (b.kind == AliasRep::AnyKind)) return true;
if (a.kind == AliasRep::GlobalKind) {
if ((b.kind == AliasRep::LocalKind) ||
((b.opnd != 0) && !analyzer->mayEscape(b.opnd))) {
return false;
} else {
return true;
}
}
if (b.kind == AliasRep::GlobalKind) {
if ((a.kind == AliasRep::LocalKind) ||
((a.opnd != 0) && !analyzer->mayEscape(a.opnd))) {
return false;
}
return true;
}
if (a.kind == AliasRep::LocalKind) {
if ((b.kind == AliasRep::GlobalKind) ||
((b.opnd == 0) || analyzer->mayEscape(b.opnd))) {
return false;
}
return true;
}
if (b.kind == AliasRep::LocalKind) {
if ((a.kind == AliasRep::GlobalKind) ||
((a.opnd == 0) || analyzer->mayEscape(a.opnd))) {
return false;
}
return true;
}
if (a.kind == AliasRep::FinishObjectKind) {
return (b.isObjectFinal());
}
if (b.kind == AliasRep::FinishObjectKind) {
return (a.isObjectFinal());
}
if (a.kind == AliasRep::FinishTypeKind) {
return (b.isTypeFinal());
}
if (b.kind == AliasRep::FinishTypeKind) {
return (a.isTypeFinal());
}
if (a.kind != b.kind) return false;
if (a.type != b.type) return false;
if (a.desc != b.desc) return false;
if (a.opnd && b.opnd && !analyzer->mayAlias(a.opnd, b.opnd)) return false;
return true;
}
void AliasRep::dump(::std::ostream &os) const
{
switch (kind) {
case NullKind: os << "Null"; break;
case GlobalKind: os << "Global"; break;
case LocalKind: os << "Local"; break;
case AnyKind: os << "Any"; break;
case UnknownKind: os << "Unknown"; break;
case ObjectFieldKind: os << "ObjectField"; break;
case UnresolvedObjectFieldKind: os << "UnresolvedObjectField"; break;
case ArrayElementKind: os << "ArrayElement"; break;
case StaticFieldKind: os << "StaticField"; break;
case UnresolvedStaticFieldKind: os << "UnresolvedStaticField"; break;
case ObjectVtableKind: os << "ObjectVtable"; break;
case MethodPtrKind: os << "MethodPtr"; break;
case FunPtrKind: os << "FunPtr"; break;
case TypeVtableKind: os << "TypeVtable"; break;
case ArrayLenKind: os << "ArrayLen"; break;
case NewObjectKind: os << "NewObject"; break;
case NewTypeKind: os << "NewType"; break;
case FinishObjectKind: os << "Final"; break;
case FinishTypeKind: os << "StaticFinal"; break;
case LockKind: os << "Lock"; break;
case TypeLockKind: os << "TypeLock"; break;
default:
assert(0);
}
if (type || desc || opnd) {
os << "[";
if (opnd) { opnd->print(os); if (type || desc) os << ","; };
if (enclClass) {enclClass->print(os); os<<","; idx->print(os);}
if (type) { type->print(os); if (desc) os << ","; };
if (desc) desc->printFullName(os);
os << "]";
}
if (id) {
os << "(" << id << ")";
}
}
void AliasRep::print(::std::ostream &os) const
{
dump(os);
}
bool AliasRep::isObjectFinal() const {
switch (kind) {
case ObjectFieldKind:
{
FieldDesc *field = (FieldDesc *) desc;
return field->isInitOnly();
};
case ObjectVtableKind:
case ArrayLenKind:
case NewObjectKind:
case FinishObjectKind:
return true;
default:
return false;
}
}
Opnd *AliasRep::getFinalObject() const {
assert(isObjectFinal());
if (kind == FinishObjectKind) {
return 0;
}
return opnd;
}
bool AliasRep::isTypeFinal() const {
switch (kind) {
case StaticFieldKind:
{
FieldDesc *field = (FieldDesc *) desc;
return field->isInitOnly();
};
case TypeVtableKind:
case FinishTypeKind:
return true;
default:
return false;
}
}
NamedType *AliasRep::getFinalType() const {
assert(isTypeFinal());
switch (kind) {
case StaticFieldKind:
return (NamedType *)type;
case TypeVtableKind:
return (NamedType *)type;
case FinishTypeKind:
return 0;
default:
assert(0);
return 0;
}
}
bool
AliasManager::isDuplicate(const AliasRep &a, const AliasRep &b) {
if (a.kind != b.kind) return false;
if (a.type && b.type && !Type::mayAlias(typeManager, a.type, b.type)) return false;
if (a.desc != b.desc) return false;
if ((a.opnd==NULL) != (b.opnd == NULL)) {
return false;
}
if ((a.opnd && b.opnd) &&
(! analyzer->mayAlias(a.opnd, b.opnd))) return false;
return true;
};
void
AliasManager::sawDuplicate(const AliasRep &ar, const AliasRep &canon)
{
if (Log::isEnabled()) {
Log::out() << "Saw duplicate of ";
canon.print(Log::out());
Log::out() << " : ";
ar.print(Log::out());
Log::out() << std::endl;
}
StlVectorSet<AliasRep> *theset = canon2others[canon];
if (!theset) {
theset = new (mm) StlVectorSet<AliasRep>(mm);
canon2others[canon] = theset;
}
theset->insert(ar);
}
AliasRep AliasManager::findOrInsertAlias(AliasRep rep)
{
Alias2Alias::const_iterator
found = other2canon.find(rep),
notfound = other2canon.end();
if (found != notfound) {
return (*found).second;
}
AliasList::iterator
iter = allAliasReps.begin(),
end = allAliasReps.end();
for (; iter != end; iter++) {
AliasRep thisRep = *iter;
if (isDuplicate(thisRep, rep)) {
sawDuplicate(rep, thisRep);
other2canon[rep] = thisRep;
return thisRep;
}
}
other2canon[rep] = rep;
rep.id = ++numAliasReps;
allAliasReps.push_back(rep);
sawDuplicate(rep, rep);
return rep;
}
AliasRep AliasManager::getReference(Opnd *addr)
{
// examine the address
Inst *addri = addr->getInst();
Opcode opcode = addri->getOpcode();
switch (opcode) {
case Op_LdFieldAddr:
{
FieldAccessInst *faInst = addri->asFieldAccessInst();
assert(faInst);
Opnd *obj = faInst->getSrc(0);
FieldDesc *field = faInst->getFieldDesc();
return findOrInsertAlias(getObjectField(obj, field));
}
case Op_LdStaticAddr:
{
FieldAccessInst *faInst = addri->asFieldAccessInst();
assert(faInst);
FieldDesc *field = faInst->getFieldDesc();
return findOrInsertAlias(getStaticField(field));
}
case Op_LdElemAddr:
{
Opnd *theArray = addri->getSrc(0);
Type *theType = theArray->getType();
assert(theType->isArrayType());
ArrayType *arrayType = (ArrayType *)theType;
NamedType *eltType = arrayType->getElementType();
return findOrInsertAlias(getArrayElementByType(eltType));
}
case Op_LdArrayBaseAddr:
{
Opnd *theArray = addri->getSrc(0);
Type *theType = theArray->getType();
assert(theType->isArrayType());
ArrayType *arrayType = (ArrayType *)theType;
NamedType *eltType = arrayType->getElementType();
return findOrInsertAlias(getArrayElementByType(eltType));
}
case Op_AddScaledIndex:
{
Type *eltType = NULL;
Opnd *thePtr = addri->getSrc(0);
Type *theType = thePtr->getType();
if (theType->isManagedPtr() || theType->isUnmanagedPtr()) {
PtrType *thePtrType = (PtrType *) theType;
eltType = thePtrType->getPointedToType();
} else {
assert(0);
}
return findOrInsertAlias(getArrayElementByType(eltType));
}
case Op_TauLdVTableAddr:
{
Opnd *theObject = addri->getSrc(0);
return findOrInsertAlias(getVtableOf(theObject));
}
case Op_GetVTableAddr:
{
TypeInst *typeInst = addri->asTypeInst();
Type *theType = typeInst->getTypeInfo();
return findOrInsertAlias(getVtableOf((NamedType *)theType));
}
case Op_TauLdIntfcVTableAddr:
{
Opnd *theObject = addri->getSrc(0);
return findOrInsertAlias(getVtableOf(theObject));
}
case Op_TauLdVirtFunAddr:
{
Opnd *theObject = addri->getSrc(0);
return findOrInsertAlias(getVtableOf(theObject));
}
case Op_TauLdVirtFunAddrSlot:
{
Opnd *theObject = addri->getSrc(0);
return findOrInsertAlias(getVtableOf(theObject));
}
case Op_LdFunAddr: // static member function address
{
MethodInst *mi = addri->asMethodInst();
MethodDesc *mdesc = mi->getMethodDesc();
NamedType *theType = mdesc->getParentType();
return findOrInsertAlias(getVtableOf(theType));
}
case Op_LdFunAddrSlot:
{
MethodInst *mi = addri->asMethodInst();
MethodDesc *mdesc = mi->getMethodDesc();
NamedType *theType = mdesc->getParentType();
return findOrInsertAlias(getVtableOf(theType));
}
case Op_StVar:
case Op_LdVar:
case Op_UncompressRef:
case Op_CompressRef:
case Op_Copy:
{
return getReference(addri->getSrc(0));
}
case Op_LdFieldOffset:
case Op_LdFieldOffsetPlusHeapbase:
{
FieldAccessInst *faInst = addri->asFieldAccessInst();
assert(faInst);
FieldDesc *field = faInst->getFieldDesc();
return findOrInsertAlias(getObjectField(0, field));
}
case Op_LdArrayBaseOffset:
case Op_LdArrayBaseOffsetPlusHeapbase:
{
TypeInst *tinst = addri->asTypeInst();
assert(tinst);
Type *eltType = tinst->getTypeInfo();
NamedType *namedEltType = (NamedType *)eltType;
return findOrInsertAlias(getArrayElementByType(namedEltType));
}
case Op_LdArrayLenOffset:
case Op_LdArrayLenOffsetPlusHeapbase:
{
return findOrInsertAlias(getArrayLen(0));
}
case Op_AddOffset:
case Op_AddOffsetPlusHeapbase:
{
Opnd *baseOpnd = addri->getSrc(0);
Opnd *offsetOpnd = addri->getSrc(1);
AliasRep offsetRep = getReference(offsetOpnd);
switch (offsetRep.kind) {
case AliasRep::ArrayLenKind:
return findOrInsertAlias(getArrayLen(baseOpnd));
case AliasRep::ArrayElementKind:
return offsetRep;
case AliasRep::ObjectFieldKind:
{
TypeMemberDesc *desc = offsetRep.desc;
assert(offsetRep.opnd == 0);
return findOrInsertAlias(getObjectField(baseOpnd, desc));
}
case AliasRep::UnresolvedObjectFieldKind:
{
assert(offsetRep.opnd == 0);
Opnd* enclClass = offsetRep.enclClass;
Opnd* cpIdx = offsetRep.idx;
assert(enclClass!=NULL && cpIdx!=NULL);
return findOrInsertAlias(getUnresolvedObjectField(baseOpnd, enclClass, cpIdx));
}
case AliasRep::LockKind:
assert(offsetRep.opnd == 0);
return findOrInsertAlias(getLock(baseOpnd));
default:
assert(0);
}
}
case Op_LdVarAddr:
case Op_Phi:
case Op_DefArg: //magic as method param
break;
case Op_Conv: //the result of a conversion
case Op_ConvZE:
case Op_ConvUnmanaged:
case Op_TauLdInd: // the result of static field load
case Op_LdConstant:
break;
case Op_VMHelperCall:
{
VMHelperCallInst* callInst = addri->asVMHelperCallInst();
assert(callInst->getVMHelperId() == VM_RT_GET_NONSTATIC_FIELD_OFFSET_WITHRESOLVE
|| callInst->getVMHelperId() == VM_RT_GET_STATIC_FIELD_ADDR_WITHRESOLVE);
Opnd* enclClass = callInst->getSrc(0);
Opnd* cpIdx = callInst->getSrc(1);
return findOrInsertAlias(getUnresolvedObjectField(0, enclClass, cpIdx));
}
// break; unreachable because of the return above
default:
assert(0);
break;
}
AliasRep theAlias = getAny(); // (AliasRep::UnknownKind);
return findOrInsertAlias(theAlias);
}
AliasRep AliasManager::getAnyGlobal()
{
return findOrInsertAlias(AliasRep(AliasRep::GlobalKind));
}
AliasRep AliasManager::getVtableOf(Opnd *opnd)
{
AliasRep vtblAlias(AliasRep::ObjectVtableKind, opnd);
return findOrInsertAlias(vtblAlias);
}
AliasRep AliasManager::getLock(Opnd *opnd)
{
AliasRep lockAlias(AliasRep::LockKind, opnd);
return findOrInsertAlias(lockAlias);
}
AliasRep AliasManager::getLock(Type *type)
{
AliasRep lockAlias(AliasRep::TypeLockKind, type);
return findOrInsertAlias(lockAlias);
}
AliasRep AliasManager::getMethodPtr(Opnd *opnd, MethodDesc *desc)
{
AliasRep methodAlias(AliasRep::MethodPtrKind, opnd, desc);
return findOrInsertAlias(methodAlias);
}
AliasRep AliasManager::getFunPtr(Opnd *opnd)
{
AliasRep funAlias(AliasRep::FunPtrKind, opnd);
return findOrInsertAlias(funAlias);
}
AliasRep AliasManager::getNoMemory()
{
return findOrInsertAlias(AliasRep(AliasRep::NullKind));
}
AliasRep AliasManager::getAnyEscaping()
{
return findOrInsertAlias(AliasRep(AliasRep::GlobalKind));
}
AliasRep AliasManager::getAny()
{
return findOrInsertAlias(AliasRep(AliasRep::AnyKind));
}
AliasRep AliasManager::getAnyLocal()
{
return findOrInsertAlias(AliasRep(AliasRep::LocalKind));
}
AliasRep AliasManager::getVtableOf(NamedType *type)
{
AliasRep vtblAlias(AliasRep::TypeVtableKind, type);
return findOrInsertAlias(vtblAlias);
}
AliasRep AliasManager::getArrayLen(Opnd *opnd)
{
AliasRep theAlias(AliasRep::ArrayLenKind, opnd);
return findOrInsertAlias(theAlias);
}
AliasRep AliasManager::getArrayElements(Opnd *array, Opnd *offset,
Opnd *length)
{
Type *theType = array->getType();
assert(theType->isArrayType());
ArrayType *arrayType = (ArrayType *)theType;
NamedType *eltType = arrayType->getElementType();
return findOrInsertAlias(getArrayElementByType(eltType));
}
AliasRep AliasManager::getObjectNew(Opnd *opnd)
{
AliasRep theAlias(AliasRep::NewObjectKind, opnd);
return findOrInsertAlias(theAlias);
}
AliasRep AliasManager::getTypeNew(NamedType *type)
{
AliasRep theAlias(AliasRep::NewTypeKind, type);
return findOrInsertAlias(theAlias);
}
AliasRep AliasManager::getFinishObject(Opnd *obj)
{
AliasRep theAlias(AliasRep::FinishObjectKind, obj);
return findOrInsertAlias(theAlias);
}
AliasRep AliasManager::getFinishType(NamedType *type)
{
AliasRep theAlias(AliasRep::FinishTypeKind, type);
return findOrInsertAlias(theAlias);
}
AliasRep AliasManager::getArrayElementByType(Type *elementType)
{
AliasRep theAlias(AliasRep::ArrayElementKind, elementType);
return findOrInsertAlias(theAlias);
}
AliasRep AliasManager::getStaticField(TypeMemberDesc *field)
{
AliasRep theAlias(AliasRep::StaticFieldKind, field);
return findOrInsertAlias(theAlias);
}
AliasRep AliasManager::getObjectField(Opnd *obj, TypeMemberDesc *field)
{
AliasRep theAlias(AliasRep::ObjectFieldKind, obj, field);
return findOrInsertAlias(theAlias);
}
AliasRep AliasManager::getUnresolvedObjectField(Opnd *obj, Opnd* enclClass, Opnd* cpIdx)
{
AliasRep theAlias(AliasRep::UnresolvedObjectFieldKind, obj, enclClass, cpIdx);
return findOrInsertAlias(theAlias);
}
AliasRep AliasManager::getUnresolvedStaticField(Opnd* enclClass, Opnd* cpIdx)
{
AliasRep theAlias(AliasRep::UnresolvedStaticFieldKind, 0, enclClass, cpIdx);
return findOrInsertAlias(theAlias);
}
void
AliasManager::dumpAliasReps(::std::ostream &os) const
{
os << "Alias Sets:" << std::endl;
AliasList::const_iterator
iter = allAliasReps.begin(),
end = allAliasReps.end();
for (; iter != end; iter++) {
const AliasRep &as = *iter;
os << " ";
as.dump(os);
os << " : ";
AliasRep2AliasReps::const_iterator
found = canon2others.find(as),
notfound = canon2others.end();
if (found != notfound) {
const StlVectorSet<AliasRep> *represents = (*found).second;
assert(represents);
StlVectorSet<AliasRep>::const_iterator
iter2 = represents->begin(),
end2 = represents->end();
for (; iter2 != end2; iter2++) {
const AliasRep &as2 = *iter2;
as2.dump(os);
os << " ";
}
} else {
os << "--null--";
}
os << std::endl;
}
os << "End of Alias Sets" << std::endl;
}
// yields a list of ancestors in some order
const AliasManager::AliasList *
AliasManager::getAncestors(const AliasRep &a)
{
Ancestors::iterator
found = ancestors.find(a),
notfound = ancestors.end();
if (found != notfound) {
return (*found).second;
} else {
AliasList *r = new (mm) AliasList(mm);
computeAncestors(a, r);
ancestors[a] = r;
return r;
}
}
// adds parents to result, returning true if nonempty
// yields a list of ancestors in some order
void
AliasManager::computeAncestors(const AliasRep &a,
AliasManager::AliasList *result)
{
switch (a.kind) {
case AliasRep::NullKind: return;
case AliasRep::GlobalKind: result->push_back(getAny()); return;
case AliasRep::LocalKind: result->push_back(getAny()); return;
case AliasRep::AnyKind: return;
case AliasRep::UnknownKind:
case AliasRep::UnresolvedStaticFieldKind:
result->push_back(getAnyGlobal());
result->push_back(getAnyLocal());
result->push_back(getAny());
return;
case AliasRep::ObjectFieldKind:
{
FieldDesc *field = (FieldDesc *) a.desc;
if (a.opnd) {
result->push_back(getObjectField(0, field));
}
if (field->isInitOnly()) {
result->push_back(getFinishObject(a.opnd));
} else {
if ((a.opnd == 0) || analyzer->mayEscape(a.opnd)) {
result->push_back(getAnyGlobal());
}
if ((a.opnd == 0) || !analyzer->mayEscape(a.opnd)) {
result->push_back(getAnyLocal());
}
}
result->push_back(getAny()); return;
}
case AliasRep::UnresolvedObjectFieldKind:
{
if ((a.opnd == 0) || analyzer->mayEscape(a.opnd)) {
result->push_back(getAnyGlobal());
}
if ((a.opnd == 0) || !analyzer->mayEscape(a.opnd)) {
result->push_back(getAnyLocal());
}
result->push_back(getAny()); return;
}
case AliasRep::ArrayElementKind:
{
if ((a.opnd == 0) || analyzer->mayEscape(a.opnd)) {
result->push_back(getAnyGlobal());
}
if ((a.opnd == 0) || !analyzer->mayEscape(a.opnd)) {
result->push_back(getAnyLocal());
}
result->push_back(getAny()); return;
}
case AliasRep::StaticFieldKind:
{
FieldDesc *field = (FieldDesc *) a.desc;
if (field->isInitOnly()) {
result->push_back(getFinishType(field->getParentType()));
} else {
result->push_back(getAnyGlobal());
}
result->push_back(getAny()); return;
}
case AliasRep::ObjectVtableKind:
{
result->push_back(getFinishObject(a.opnd));
result->push_back(getAny()); return;
}
case AliasRep::MethodPtrKind:
{
result->push_back(getFinishObject(a.opnd));
result->push_back(getAny()); return;
}
case AliasRep::FunPtrKind:
{
result->push_back(getFinishObject(a.opnd));
result->push_back(getAny()); return;
}
case AliasRep::TypeVtableKind:
{
result->push_back(getFinishType((NamedType *)a.type));
result->push_back(getAny()); return;
}
case AliasRep::ArrayLenKind:
{
result->push_back(getFinishObject(a.opnd));
result->push_back(getAny()); return;
}
case AliasRep::NewObjectKind:
{
result->push_back(getFinishObject(a.opnd));
result->push_back(getAny()); return;
}
case AliasRep::NewTypeKind:
{
result->push_back(getFinishType((NamedType *)a.type));
result->push_back(getAny()); return;
}
case AliasRep::FinishObjectKind:
{
result->push_back(getAny()); return;
}
case AliasRep::FinishTypeKind:
{
result->push_back(getAny()); return;
}
case AliasRep::LockKind: result->push_back(getAny()); return;
case AliasRep::TypeLockKind: result->push_back(getAny()); return;
default:
assert(0);
};
}
// ancestors of theRep have already been done
void MemoryOpt::insertPhiFor(const AliasRep &theRep, VarDefSites* defSites,
StlList<VarDefSites *> &ancestorDefSites)
{
StlList<VarDefSites *>::iterator ancEnd = ancestorDefSites.end();
Node* node;
while ((node = defSites->removeDefSite()) != NULL) {
bool done = false;
// if an ancestor has a def there, skip it
StlList<VarDefSites *>::iterator ancIter = ancestorDefSites.begin();
for ( ; ancIter != ancEnd; ++ancIter ) {
VarDefSites *ancSites = *ancIter;
if (ancSites->isDefSite(node)) {
done = true;
if (Log::isEnabled()) {
Log::out() << "Skipping node ";
FlowGraph::printLabel(Log::out(), node);
Log::out() << " because ancestor has def there" << std::endl;
}
break;
}
}
if (done) continue;
if (Log::isEnabled()) {
Log::out() << "Consider def at node ";
FlowGraph::printLabel(Log::out(), node);
Log::out() << std::endl;
}
List<Node>* dflist = df.getFrontiersOf(node);
for (; dflist != NULL; dflist = dflist->getNext()) {
// block where phi inst is going to be inserted
Node* insertedLoc = dflist->getElem();
// if phi has been inserted, then skip
// no need to insert phi inst in the epilog because
// there is no var use in the epilog
if (!defSites->beenInsertedPhi(insertedLoc) &&
!insertedLoc->getOutEdges().empty()) {
if (Log::isEnabled()) {
Log::out() << "Queuing DF node ";
FlowGraph::printLabel(Log::out(), insertedLoc);
Log::out() << std::endl;
}
// create a new phi instruction for varOpnd
createMemPhiInst(theRep,insertedLoc);
// record phi(var) inst is created in dflist->getElem() block
defSites->insertPhiSite(insertedLoc);
}
}
}
}
void MemoryOpt::insertMemPhi() {
AliasDefSites::iterator
iter = aliasDefSites->begin(),
end = aliasDefSites->end();
for ( ; iter != end; ++iter ) {
AliasRep aliasRep = (*iter).first;
VarDefSites* defSites = (*iter).second;
if (defSites) {
if (Log::isEnabled()) {
Log::out() << "BEGIN Inserting Phis for ";
aliasRep.print(Log::out());
Log::out() << std::endl;
}
const AliasManager::AliasList *alist = aliasManager->getAncestors(aliasRep);
StlList<VarDefSites *> ancestorDefSites(mm);
AliasManager::AliasList::const_iterator
iter = alist->begin(),
end = alist->end();
AliasDefSites::iterator sitesEnd = aliasDefSites->end();
for ( ; iter != end; ++iter) {
AliasRep ancestor = *iter;
AliasDefSites::iterator found = aliasDefSites->find(ancestor);
if (found != sitesEnd) {
ancestorDefSites.push_back((*found).second);
}
}
insertPhiFor(aliasRep, defSites, ancestorDefSites);
if (Log::isEnabled()) {
Log::out() << "DONE Inserting Phis for ";
aliasRep.print(Log::out());
Log::out() << std::endl;
}
} else {
if (Log::isEnabled()) {
Log::out() << "NO Phis for ";
aliasRep.print(Log::out());
Log::out() << " because it has no defs" << std::endl;
}
}
}
}
void MemoryOpt::createMemPhiInst(const AliasRep &aliasRep, Node *node)
{
if (Log::isEnabled()) {
Log::out() << "Insert MemPhi for ";
aliasRep.print(Log::out());
Log::out() << " at node ";
FlowGraph::printLabel(Log::out(), node);
Log::out() << std::endl;
}
Inst *firstInst = (Inst*)node->getFirstInst();
assert(firstInst->isLabel());
InstMemBehavior *b = getOrCreateInstEffect(firstInst);
b->uses.insert(aliasRep);
b->defs.insert(aliasRep);
memPhiSites->addMemPhi(node, aliasRep);
}
// a ScopedDomNodeInstWalker, to be applied forwards/pre-order
class MemoryRenameWalker {
MemoryOpt *thePass;
U_32 timeCount;
public:
MemoryRenameWalker(MemoryOpt *thePass0) :
thePass(thePass0), timeCount(1)
{
};
void startNode(DominatorNode *domNode0) { };
void applyToInst(Inst *inst);
void finishNode(DominatorNode *domNode);
void enterScope() { thePass->renameMap->enter_scope(); };
void exitScope() { thePass->renameMap->exit_scope(); };
private:
void addUse(Inst *inst, const AliasRep &rep);
void addDef(Inst *inst, const AliasRep &rep);
};
void MemoryOpt::addMemUseDef(Inst *use, Inst *def)
{
// update use->def map:
DefsSet *defSet = memUseDefs[use];
if (!defSet) {
defSet = new (mm) DefsSet(mm);
memUseDefs[use] = defSet;
}
::std::pair<DefsSet::iterator, bool> res = defSet->insert(def);
if (res.second) {
// update def->use map as well:
UsesSet *theSet = memDefUses[def];
if (!theSet) {
theSet = new (mm) UsesSet(mm);
memDefUses[def] = theSet;
}
theSet->insert(use);
}
}
void MemoryOpt::remMemInst(Inst *theInst)
{
if (Log::isEnabled()) {
Log::out() << "Eliminating redundant memory instruction: ";
theInst->print(Log::out());
Log::out() << std::endl;
}
// get defs used by theInst
Use2DefsMap::iterator
found = memUseDefs.find(theInst),
end = memUseDefs.end();
DefsSet *defsReachingInst = 0;
if (found != end) {
defsReachingInst = (*found).second;
memUseDefs.erase(theInst);
}
// get insts using mem defined by theInst
Def2UsesMap::iterator
found2 = memDefUses.find(theInst),
end2 = memDefUses.end();
UsesSet *usersOfInst = 0;
if (found2 != end2) {
usersOfInst = (*found2).second;
memDefUses.erase(theInst);
}
// set all users to point to this instance's reaching def
if (usersOfInst) {
UsesSet::iterator
usersIter = usersOfInst->begin(),
usersEnd = usersOfInst->end();
for ( ; usersIter != usersEnd; ++usersIter) {
Inst *user = *usersIter;
DefsSet *defsOfThisUser = memUseDefs[user];
assert(defsOfThisUser);
assert(defsOfThisUser->has(theInst));
defsOfThisUser->erase(theInst);
if (defsReachingInst) {
defsOfThisUser->insert(defsReachingInst->begin(),
defsReachingInst->end());
}
}
}
if (defsReachingInst) {
DefsSet::const_iterator
defsIter = defsReachingInst->begin(),
defsEnd = defsReachingInst->end();
for ( ; defsIter != defsEnd; ++defsIter) {
Inst *defReachingInst = *defsIter;
UsesSet *theSet = memDefUses[defReachingInst];
assert(theSet);
assert(theSet->has(theInst));
// remove this use
theSet->erase(theInst);
if (usersOfInst) {
// add new transitive uses
theSet->insert(usersOfInst->begin(),
usersOfInst->end());
}
}
}
if (Log::isEnabled()) {
Log::out() << "Finished eliminating redundant memory instruction: ";
theInst->print(Log::out());
Log::out() << std::endl;
}
}
void MemoryOpt::replaceMemInst(Inst *oldInst, Inst *newInst)
{
if (Log::isEnabled()) {
Log::out() << "Replacing memory instruction ";
oldInst->print(Log::out());
Log::out() << " by ";
newInst->print(Log::out());
Log::out() << std::endl;
}
// get defs used by theInst
assert(memUseDefs.find(newInst) == memUseDefs.end());
DefsSet *defs = 0;
Use2DefsMap::iterator
found = memUseDefs.find(oldInst),
end = memUseDefs.end();
if (found != end) {
// point new inst to them
defs = (*found).second;
assert(defs);
memUseDefs[oldInst] = defs;
// and erase old inst from map
memUseDefs.erase(oldInst);
// update each reaching def to have newInst as a use instead of oldInst
DefsSet::const_iterator
iter = defs->begin(),
end = defs->end();
for ( ; iter != end; ++iter) {
Inst *def = *iter;
UsesSet *uses = memDefUses[def];
assert(uses);
uses->erase(oldInst);
uses->insert(newInst);
}
}
// get uses of theInst
assert(memDefUses.find(newInst) == memDefUses.end());
UsesSet *uses = 0;
Def2UsesMap::iterator
foundUses = memDefUses.find(oldInst),
endUses = memDefUses.end();
if (foundUses != endUses) {
// point new inst to them
uses = (*foundUses).second;
assert(uses);
memDefUses[oldInst] = uses;
// and erase old inst from map
memDefUses.erase(oldInst);
// update each user to have newInst as a def instead of oldInst
UsesSet::const_iterator
iter = uses->begin(),
end = uses->end();
for ( ; iter != end; ++iter) {
Inst *use = *iter;
DefsSet *defs = memUseDefs[use];
assert(defs);
defs->erase(oldInst);
defs->insert(newInst);
}
}
}
bool MemoryOpt::hasSameReachingDefs(Inst *i1, Inst *i2)
{
assert(i1 != i2);
if (Log::isEnabled()) {
Log::out() << "checking use2defs(" << (int)i1->getId() << ")==use2defs("
<< (int)i2->getId() << "): ";
}
bool result;
Use2DefsMap::iterator
found1 = memUseDefs.find(i1),
found2 = memUseDefs.find(i2),
end = memUseDefs.end();
if ((found1 == end) || (found2 == end)) {
result = (found1 == found2);
} else {
DefsSet *defs1 = (*found1).second;
DefsSet *defs2 = (*found2).second;
assert(defs1 && defs2);
result = (*defs1 == *defs2);
}
if (Log::isEnabled()) {
Log::out() << (result ? " == > TRUE" : " == > FALSE") << std::endl;
}
return result;
}
bool MemoryOpt::hasDefReachesUse(Inst *def, Inst *use)
{
Use2DefsMap::iterator
found = memUseDefs.find(use),
end = memUseDefs.end();
if (found == end) {
return false;
} else {
DefsSet *defsSet = (*found).second;
assert(defsSet);
return (defsSet->has(def));
}
}
void
MemoryRenameWalker::addDef(Inst *inst, const AliasRep &rep)
{
addUse(inst, rep);
// ok, now add a new binding
thePass->renameMap->insert(rep, inst);
}
void
MemoryRenameWalker::addUse(Inst *inst, const AliasRep &rep)
{
if (Log::isEnabled()) {
Log::out() << "Adding Use of aliasRep ";
rep.print(Log::out());
Log::out() << " to inst ";
inst->print(Log::out());
Log::out() << std::endl;
}
AliasRenameMap::DefsSet defs(thePass->mm);
thePass->renameMap->lookup(rep, defs);
AliasRenameMap::DefsSet::iterator
iter = defs.begin(),
end = defs.end();
for ( ; iter != end; ++iter) {
Inst *defInst = *iter;
thePass->addMemUseDef(inst, defInst);
}
}
void
MemoryRenameWalker::applyToInst(Inst *inst)
{
InstMemBehavior *b = thePass->getInstEffect(inst);
if (Log::isEnabled()) {
Log::out() << "applying renaming to Inst ";
inst->print(Log::out());
Log::out() << std::endl;
}
if (b) {
// compute uses here
if (b->acquire) {
addUse(inst, thePass->aliasManager->getAny());
addDef(inst, thePass->aliasManager->getAny());
return;
}
if (b->release) {
addUse(inst, thePass->aliasManager->getAny());
addDef(inst, thePass->aliasManager->getAny());
return;
}
{
StlVectorSet<AliasRep>::const_iterator
iter = b->uses.begin(),
end = b->uses.end();
for ( ; iter != end; ++iter) {
AliasRep rep = *iter;
if (Log::isEnabled()) {
Log::out() << " has use of ";
rep.print(Log::out());
Log::out() << std::endl;
}
addUse(inst, rep);
}
}
// compute definitions here
{
StlVectorSet<AliasRep>::const_iterator
iter = b->defs.begin(),
end = b->defs.end();
for ( ; iter != end; ++iter) {
AliasRep rep = *iter;
if (Log::isEnabled()) {
Log::out() << " has def of ";
rep.print(Log::out());
Log::out() << std::endl;
}
addDef(inst, rep);
}
}
}
}
void
MemoryRenameWalker::finishNode(DominatorNode *domNode)
{
Node *node = domNode->getNode();
if (Log::isEnabled()) {
Log::out() << "finishing renaming for Node ";
FlowGraph::printLabel(Log::out(), node);
Log::out() << std::endl;
}
const Edges& edges = node->getOutEdges();
Edges::const_iterator eiter;
for(eiter = edges.begin(); eiter != edges.end(); ++eiter) {
Edge* e = *eiter;
Node* succ = e->getTargetNode();
const StlVector<AliasRep> *memPhis = thePass->memPhiSites->getMemPhis(succ);
if (memPhis) {
Inst *succLabel = (Inst*)succ->getFirstInst();
assert(succLabel->isLabel());
StlVector<AliasRep>::const_iterator
iter = memPhis->begin(),
end = memPhis->end();
for ( ; iter != end; ++iter) {
const AliasRep &thisRep = *iter;
addUse(succLabel, thisRep);
}
}
}
if (Log::isEnabled()) {
Log::out() << "finished renaming for Node ";
FlowGraph::printLabel(Log::out(), node);
Log::out() << std::endl;
}
}
// a NodeInstWalker, to be applied forwards
class MemoryDebugWalker {
MemoryOpt *thePass;
public:
MemoryDebugWalker(MemoryOpt *thePass0) :
thePass(thePass0)
{ };
void startNode(Node *node) { };
void applyToInst(Inst *inst);
void finishNode(Node *node) {};
};
void MemoryDebugWalker::applyToInst(Inst *inst)
{
inst->print(Log::out());
Log::out() << std::endl;
MemoryOpt::Use2DefsMap::iterator
found = thePass->memUseDefs.find(inst),
end = thePass->memUseDefs.end();
if (found != end) {
MemoryOpt::DefsSet *defs = (*found).second;
assert(defs);
Log::out() << " depends on instructions: ";
MemoryOpt::DefsSet::iterator
iter2 = defs->begin(),
end2 = defs->end();
for ( ; iter2 != end2; ++iter2) {
Inst *thisDep = *iter2;
thisDep->print(Log::out());
Log::out() << " ";
}
Log::out() << std::endl;
}
}
void MemoryOpt::createUsesMap()
{
MemoryRenameWalker renameWalker(this);
// adapt the ScopedDomNodeInstWalker to a DomWalker
typedef ScopedDomNodeInst2DomWalker<true, MemoryRenameWalker>
MemoryRenameDomWalker;
MemoryRenameDomWalker domRenameWalker(renameWalker);
// do the walk, pre-order
DomTreeWalk<true, MemoryRenameDomWalker>(dominators, domRenameWalker,
mm);
if (Log::isEnabled()) {
MemoryDebugWalker debugWalker(this);
// adapt the forwards NodeInstWalker to a NodeWalker
typedef NodeInst2NodeWalker<true, MemoryDebugWalker>
MemoryDebugNodeWalker;
MemoryDebugNodeWalker debugNodeWalker(debugWalker);
// do the walk over nodes in arbitrary order
NodeWalk<MemoryDebugNodeWalker>(fg, debugNodeWalker);
}
}
void AliasRenameMap::enter_scope()
{
++depth;
defMap.enter_scope();
activeDescendents.enter_scope();
}
void AliasRenameMap::exit_scope()
{
defMap.exit_scope();
activeDescendents.exit_scope();
--depth;
}
void AliasRenameMap::insert(const AliasRep &rep, Inst *defInst)
{
U_32 timeNow = ++timeCount;
AliasBinding newBinding(defInst, timeNow);
if (Log::isEnabled()) {
Log::out() << " adding def of ";
rep.print(Log::out());
Log::out() << " at time " << (int) timeNow << " to inst "
<< (int) defInst->getId() << std::endl;
}
// first, set this value
defMap.insert(rep, newBinding);
// clear active descendants of rep; they are overwritten now,
// so remove their definitions and clear it
DescendentSet *descSet = activeDescendents.lookup(rep);
if (descSet) {
descSet->clear();
}
// Add this rep to the set of active descendants for
// each ancestor.
const AliasManager::AliasList *alist =
aliasManager->getAncestors(rep);
AliasManager::AliasList::const_iterator
iter = alist->begin(),
end = alist->end();
for ( ; iter != end; ++iter) {
const AliasRep &thisAncestor = *iter;
// get the set of descendants of the ancestor, or create it
DescendentSet *descSet = activeDescendents.lookup(thisAncestor);
if (!descSet) {
descSet = new (mm) DescendentSet(mm, depth);
activeDescendents.insert(thisAncestor, descSet);
} else if (descSet->depth != depth) {
// we need to make a copy of the set so we don't overwrite
// the definition in the sibling nodes
descSet = new (mm) DescendentSet(mm, descSet, depth);
activeDescendents.insert(thisAncestor, descSet);
}
// add this rep to the descendant set
descSet->insert(rep);
}
}
void AliasRenameMap::lookup(const AliasRep &rep, DefsSet &defs)
{
// first, find the appropriate binding to use, checking for most recent of
// rep and its ancestors which has been set
AliasBinding bestFound = defMap.lookup(rep);
Inst *bestInst = bestFound.inst;
U_32 bestWhen = bestInst ? bestFound.when : 0;
{
if (!bestInst) {
if (Log::isEnabled()) {
Log::out() << "aliasRep ";
rep.print(Log::out());
Log::out() << " has no binding" << std::endl;
}
} else {
if (Log::isEnabled()) {
Log::out() << "aliasRep ";
rep.print(Log::out());
Log::out() << " has binding at time " << (int) bestWhen << std::endl;
}
}
const AliasManager::AliasList *alist =
aliasManager->getAncestors(rep);
AliasManager::AliasList::const_iterator
iter = alist->begin(),
end = alist->end();
if (Log::isEnabled()) {
if (iter != end) {
Log::out() << "trying ancestors: " << std::endl;
} else {
Log::out() << "has no ancestors" << std::endl;
}
}
for ( ; iter != end; ++iter) {
AliasRep thisAncestor = *iter;
if (Log::isEnabled()) {
thisAncestor.print(Log::out());
Log::out() << " ";
}
AliasBinding newFound = defMap.lookup(thisAncestor);
Inst *thisInst = newFound.inst;
if (thisInst) {
U_32 thisWhen = newFound.when;
if (Log::isEnabled()) {
Log::out() << " ";
thisAncestor.print(Log::out());
Log::out() << " has binding at time " << (int) thisWhen << std::endl;
}
if (newFound.when > bestWhen) {
bestWhen = thisWhen;
bestInst = thisInst;
if (Log::isEnabled()) {
Log::out() << ", replaces bestInst";
}
}
if (Log::isEnabled()) {
Log::out() << std::endl;
}
} else {
if (Log::isEnabled()) {
Log::out() << " ";
thisAncestor.print(Log::out());
Log::out() << " has no binding " << std::endl;
}
}
}
if (Log::isEnabled()) {
Log::out() << std::endl;
}
}
assert(bestInst);
defs.insert(bestInst);
// ok, now look for bindings of this rep's descendants which are
// more recent than the best one we found.
DescendentSet *descSet = activeDescendents.lookup(rep);
if (descSet) {
// has descendants, add those, too;
DescendentSet::iterator
descIter = descSet->begin(),
descEnd = descSet->end();
for ( ; descIter != descEnd; ++descIter) {
const AliasRep &desc = *descIter;
const AliasBinding &descBinding = defMap.lookup(desc);
Inst *desci = descBinding.inst;
U_32 when = descBinding.when;
if (when > bestWhen) { // descendant is newer
defs.insert(desci);
}
}
}
}
// an InstWalker, to be applied forwards
class MemoryRedStoreWalker {
MemoryOpt *thePass;
public:
MemoryRedStoreWalker(MemoryOpt *thePass0) :
thePass(thePass0)
{ };
void applyToInst(Inst *inst);
};
static U_8
getBitWidth(Type::Tag tag)
{
switch (tag) {
case Type::Void: return 0;
case Type::Boolean: return 1;
case Type::Char: return 16;
case Type::Int8: return 8;
case Type::Int16: return 16;
case Type::Int32: return 32;
case Type::Int64: return 64;
case Type::UInt8: return 8;
case Type::UInt16: return 16;
case Type::UInt32: return 32;
case Type::UInt64: return 64;
default: return 0xff; // uses all;
}
}
void
MemoryRedStoreWalker::applyToInst(Inst *inst)
{
switch (inst->getOpcode()) {
case Op_TauStInd:
case Op_TauStField:
case Op_TauStStatic:
case Op_TauStElem:
case Op_TauStRef:
// maybe eliminate inst;
break;
default:
return;
}
MemoryOpt::Def2UsesMap::iterator
foundUses = thePass->memDefUses.find(inst),
endDefUse = thePass->memDefUses.end();
MemoryOpt::UsesSet *usesSet = ((foundUses != endDefUse)
? (*foundUses).second
: 0);
if ((!usesSet) || (usesSet->size() == 0)) {
} else if (usesSet->size() == 1) {
Inst *usingInst = (*usesSet)[0];
if ((usingInst->getOpcode()) == (inst->getOpcode())) {
switch (usingInst->getOpcode()) {
case Op_TauStInd:
{
Opnd *usingAddr = usingInst->getSrc(1);
Opnd *thisAddr = inst->getSrc(1);
if ((usingAddr == thisAddr) &&
(getBitWidth(usingInst->getType()) >=
getBitWidth(inst->getType()))) {
// eliminate inst;
thePass->remMemInst(inst);
inst->unlink();
}
}
break;
case Op_TauStRef:
{
Opnd *usingAddr = usingInst->getSrc(1);
Opnd *thisAddr = inst->getSrc(1);
if ((usingAddr == thisAddr) &&
(getBitWidth(usingInst->getType()) >=
getBitWidth(inst->getType()))) {
// eliminate inst;
thePass->remMemInst(inst);
inst->unlink();
}
}
break;
case Op_TauStField:
{
Opnd *usingBase = usingInst->getSrc(1);
Opnd *thisBase = inst->getSrc(1);
FieldAccessInst *finst = inst->asFieldAccessInst();
FieldAccessInst *fusing = usingInst->asFieldAccessInst();
FieldDesc *instDesc = finst->getFieldDesc();
FieldDesc *usingDesc = fusing->getFieldDesc();
usingDesc = instDesc;
if ((usingBase == thisBase) &&
usingDesc &&
( getBitWidth(usingInst->getType())
>= getBitWidth(inst->getType()) )) {
// eliminate inst;
thePass->remMemInst(inst);
inst->unlink();
}
}
break;
case Op_TauStStatic:
{
FieldAccessInst *finst = inst->asFieldAccessInst();
FieldAccessInst *fusing = usingInst->asFieldAccessInst();
FieldDesc *instDesc = finst->getFieldDesc();
FieldDesc *usingDesc = fusing->getFieldDesc();
usingDesc = instDesc;
if (usingDesc &&
(getBitWidth(usingInst->getType())
>= getBitWidth(inst->getType()))) {
// eliminate inst;
thePass->remMemInst(inst);
inst->unlink();
}
}
break;
case Op_TauStElem:
{
Opnd *usingArray = usingInst->getSrc(1);
Opnd *thisArray = inst->getSrc(1);
Opnd *usingIndex = usingInst->getSrc(2);
Opnd *thisIndex = inst->getSrc(2);
if ((usingArray == thisArray) &&
(usingIndex == thisIndex) &&
(getBitWidth(usingInst->getType()) >=
getBitWidth(inst->getType()))) {
// eliminate inst;
thePass->remMemInst(inst);
inst->unlink();
}
}
break;
default:
break;
}
}
}
}
void MemoryOpt::eliminateRedStores()
{
MemoryRedStoreWalker redStoreWalker(this);
// adapt the forwards NodeInstWalker to a NodeWalker
typedef Inst2NodeWalker<true, MemoryRedStoreWalker>
MemoryRedStoreNodeWalker;
MemoryRedStoreNodeWalker redStoreNodeWalker(redStoreWalker);
// do the walk over nodes in arbitrary order
NodeWalk<MemoryRedStoreNodeWalker>(fg, redStoreNodeWalker);
if (Log::isEnabled()) {
Log::out() << "After red store elimination: " << std::endl;
MemoryDebugWalker debugWalker(this);
// adapt the forwards InstWalker to a NodeWalker
typedef Inst2NodeWalker<true, MemoryDebugWalker>
MemoryDebugNodeWalker;
MemoryDebugNodeWalker debugNodeWalker(debugWalker);
// do the walk over nodes in arbitrary order
NodeWalk<MemoryDebugNodeWalker>(fg, debugNodeWalker);
}
}
// an InstWalker, to be applied forwards
class MemorySyncOptWalker {
MemoryOpt *thePass;
public:
MemorySyncOptWalker(MemoryOpt *thePass0) :
thePass(thePass0)
{ };
void applyToInst(Inst *inst);
};
void
MemorySyncOptWalker::applyToInst(Inst *inst)
{
switch (inst->getOpcode()) {
case Op_BalancedMonitorExit:
return;
case Op_TauBalancedMonitorEnter:
// check whether this is balanced
break;
default:
return;
}
StlVectorSet<Inst *> involved(thePass->mm);
StlVectorSet<Inst *> newlyInvolved(thePass->mm);
newlyInvolved.insert(inst);
Opnd *obj = inst->getSrc(0);
if (Log::isEnabled()) {
Log::out() << "Checking instruction ";
inst->print(Log::out());
Log::out() << std::endl;
}
Opnd *enterLockAddrOpnd = 0;
Opnd *enterLockValueOpnd = 0;
Opnd *exitLockAddrOpnd = 0;
Opnd *exitLockValueOpnd = 0;
while (!newlyInvolved.empty()) {
Inst *monitorInst = *(newlyInvolved.begin());
newlyInvolved.erase(newlyInvolved.begin());
if (involved.count(monitorInst) == 0) {
// don't have it, insert it
involved.insert(monitorInst);
if (Log::isEnabled()) {
Log::out() << "Is involved with instruction ";
monitorInst->print(Log::out());
Log::out() << std::endl;
}
if (monitorInst->isLabel()) {
// acting as memory phi, match both ways
MemoryOpt::Use2DefsMap::iterator
foundDefs = thePass->memUseDefs.find(monitorInst),
endDefs = thePass->memUseDefs.end();
if (foundDefs != endDefs) {
MemoryOpt::DefsSet *defs = (*foundDefs).second;
MemoryOpt::DefsSet::iterator
iter2 = defs->begin(),
end2 = defs->end();
for ( ; iter2 != end2; ++iter2) {
Inst *def = *iter2;
if (!(def->isLabel() ||
(def->getOpcode() == Op_BalancedMonitorExit))) {
// failed
return;
}
}
newlyInvolved.insert(defs->begin(), defs->end());
} else {
// failed to find match
return;
}
MemoryOpt::Def2UsesMap::iterator
foundMatches = thePass->memDefUses.find(monitorInst),
endMatches = thePass->memDefUses.end();
if (foundMatches != endMatches) {
MemoryOpt::UsesSet *foundUses = (*foundMatches).second;
MemoryOpt::UsesSet::iterator
usesIter = foundUses->begin(),
usesEnd = foundUses->end();
for ( ; usesIter != usesEnd; ++usesIter) {
Inst *use = *usesIter;
if (!(use->isLabel() ||
use->getOpcode() == Op_TauBalancedMonitorEnter)) {
// failed
return;
}
}
newlyInvolved.insert(foundUses->begin(), foundUses->end());
}
} else {
switch (monitorInst->getOpcode()) {
case Op_BalancedMonitorExit: {
// getMatch = monitorExit to following monitorEnter
// look at uses
if (obj != monitorInst->getSrc(0)) {
// failed
return;
}
if (!exitLockAddrOpnd) {
exitLockAddrOpnd = monitorInst->getSrc(1);
exitLockValueOpnd = monitorInst->getSrc(2);
} else {
if ((exitLockAddrOpnd != monitorInst->getSrc(1))||
(exitLockValueOpnd != monitorInst->getSrc(2))) {
// failed
return;
}
}
MemoryOpt::Def2UsesMap::iterator
foundMatches = thePass->memDefUses.find(monitorInst),
endMatches = thePass->memDefUses.end();
if (foundMatches != endMatches) {
MemoryOpt::UsesSet *foundUses = (*foundMatches).second;
MemoryOpt::UsesSet::iterator
usesIter = foundUses->begin(),
usesEnd = foundUses->end();
for ( ; usesIter != usesEnd; ++usesIter) {
Inst *use = *usesIter;
if (!(use->isLabel() ||
use->getOpcode() == Op_TauBalancedMonitorEnter)) {
// failed
return;
}
}
newlyInvolved.insert(foundUses->begin(),
foundUses->end());
} else {
// failed
return;
}
}
break;
case Op_TauBalancedMonitorEnter: {
// monitorEnter to preceding monitorExit
if (obj != monitorInst->getSrc(0)) {
// failed
return;
}
MemoryOpt::Use2DefsMap::iterator
foundMatches = thePass->memUseDefs.find(monitorInst),
endMatches = thePass->memUseDefs.end();
if (foundMatches != endMatches) {
MemoryOpt::DefsSet *foundDefs = (*foundMatches).second;
assert(foundDefs);
MemoryOpt::DefsSet::iterator
iter2 = foundDefs->begin(),
end2 = foundDefs->end();
for ( ; iter2 != end2; ++iter2) {
Inst *foundDef = *iter2;
if (!(foundDef->isLabel() ||
(foundDef->getOpcode()==Op_BalancedMonitorExit))) {
// failed
return;
}
}
if (!enterLockAddrOpnd) {
enterLockAddrOpnd = monitorInst->getSrc(1);
enterLockValueOpnd = monitorInst->getDst();
} else {
if ((enterLockAddrOpnd != monitorInst->getSrc(1))||
(enterLockValueOpnd != monitorInst->getDst())) {
// failed
return;
}
}
newlyInvolved.insert(foundDefs->begin(),
foundDefs->end());
} else {
// failed
return;
}
}
break;
default:
// failed
return;
}
}
}
}
// involved contains all exit/enter which match (plus possible labels)
// turn them into fences
if (Log::isEnabled()) {
Log::out() << "Can convert to fence: " << std::endl;
}
InstFactory &instFactory = thePass->irManager.getInstFactory();
StlVector<Inst *>::iterator
invIter = involved.begin(),
invEnd = involved.end();
for ( ; invIter != invEnd; ++invIter) {
Inst *invInst = *invIter;
Inst *newI = 0;
if (invInst->isLabel())
continue;
switch (invInst->getOpcode()) {
case Op_BalancedMonitorExit:
newI = instFactory.makeMonitorExitFence(obj);
break;
case Op_TauBalancedMonitorEnter:
if (enterLockAddrOpnd != exitLockAddrOpnd) {
Inst *enterLockAddrInst = enterLockAddrOpnd->getInst();
Inst *newI2= instFactory.makeCopy(enterLockAddrOpnd, exitLockAddrOpnd);
newI2->insertBefore(enterLockAddrInst);
enterLockAddrInst->unlink();
}
{
Inst *newI3 = instFactory.makeCopy(enterLockValueOpnd,
exitLockValueOpnd);
newI3->insertAfter(invInst);
}
newI = instFactory.makeMonitorEnterFence(obj);
break;
default:
assert(0);
}
if (Log::isEnabled()) {
Log::out() << "Instruction " << std::endl << " ";
invInst->print(Log::out());
Log::out() << std::endl << " becomes " << std::endl << " ";
newI->print(Log::out());
Log::out() << std::endl;
}
newI->insertAfter(invInst);
invInst->unlink();
thePass->replaceMemInst(invInst, newI);
}
}
void MemoryOpt::doSyncOpt()
{
MemorySyncOptWalker memSyncOptWalker(this);
// adapt the forwards NodeInstWalker to a NodeWalker
typedef Inst2NodeWalker<true, MemorySyncOptWalker>
MemorySyncOptNodeWalker;
MemorySyncOptNodeWalker memSyncOptNodeWalker(memSyncOptWalker);
// do the walk over nodes in arbitrary order
NodeWalk<MemorySyncOptNodeWalker>(fg, memSyncOptNodeWalker);
if (Log::isEnabled()) {
Log::out() << "After mem syncopt: " << std::endl;
MemoryDebugWalker debugWalker(this);
// adapt the forwards InstWalker to a NodeWalker
typedef Inst2NodeWalker<true, MemoryDebugWalker>
MemoryDebugNodeWalker;
MemoryDebugNodeWalker debugNodeWalker(debugWalker);
// do the walk over nodes in arbitrary order
NodeWalk<MemoryDebugNodeWalker>(fg, debugNodeWalker);
}
}
} //namespace Jitrino