diff options
| -rw-r--r-- | include/llvm/Analysis/MemoryDependenceAnalysis.h | 60 | ||||
| -rw-r--r-- | lib/Analysis/MemoryDependenceAnalysis.cpp | 90 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/DeadStoreElimination.cpp | 30 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/GVN.cpp | 171 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/MemCpyOptimizer.cpp | 7 |
5 files changed, 175 insertions, 183 deletions
diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h index b9138ef808..c30a85266d 100644 --- a/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -36,20 +36,36 @@ namespace llvm { /// Invalid - Clients of MemDep never see this. Invalid = 0, - /// Normal - This is a normal instruction dependence. The pointer member - /// of the MemDepResult pair holds the instruction. - Normal, + /// Clobber - This is a dependence on the specified instruction which + /// clobbers the desired value. The pointer member of the MemDepResult + /// pair holds the instruction that clobbers the memory. For example, + /// this occurs when we see a may-aliased store to the memory location we + /// care about. + Clobber, + /// Def - This is a dependence on the specified instruction which + /// defines/produces the desired memory location. The pointer member of + /// the MemDepResult pair holds the instruction that defines the memory. + /// Cases of interest: + /// 1. This could be a load or store for dependence queries on + /// load/store. The value loaded or stored is the produced value. + /// Note that the pointer operand may be different than that of the + /// queried pointer due to must aliases and phi translation. Note + /// that the def may not be the same type as the query, the pointers + /// may just be must aliases. + /// 2. For loads and stores, this could be an allocation instruction. In + /// this case, the load is loading an undef value or a store is the + /// first store to (that part of) the allocation. + /// 3. Dependence queries on calls return Def only when they are + /// readonly calls with identical callees and no intervening + /// clobbers. No validation is done that the operands to the calls + /// are the same. + Def, + /// NonLocal - This marker indicates that the query has no dependency in /// the specified block. To find out more, the client should query other /// predecessor blocks. - NonLocal, - - /// None - This dependence type indicates that the query does not depend - /// on any instructions, either because it is not a memory instruction or - /// because it scanned to the definition of the memory (alloca/malloc) - /// being accessed. - None + NonLocal }; typedef PointerIntPair<Instruction*, 2, DepType> PairTy; PairTy Value; @@ -59,29 +75,29 @@ namespace llvm { /// get methods: These are static ctor methods for creating various /// MemDepResult kinds. - static MemDepResult get(Instruction *Inst) { - return MemDepResult(PairTy(Inst, Normal)); + static MemDepResult getDef(Instruction *Inst) { + return MemDepResult(PairTy(Inst, Def)); + } + static MemDepResult getClobber(Instruction *Inst) { + return MemDepResult(PairTy(Inst, Clobber)); } static MemDepResult getNonLocal() { return MemDepResult(PairTy(0, NonLocal)); } - static MemDepResult getNone() { - return MemDepResult(PairTy(0, None)); - } - /// isNormal - Return true if this MemDepResult represents a query that is - /// a normal instruction dependency. - bool isNormal() const { return Value.getInt() == Normal; } + /// isClobber - Return true if this MemDepResult represents a query that is + /// a instruction clobber dependency. + bool isClobber() const { return Value.getInt() == Clobber; } + + /// isDef - Return true if this MemDepResult represents a query that is + /// a instruction definition dependency. + bool isDef() const { return Value.getInt() == Def; } /// isNonLocal - Return true if this MemDepResult represents an query that /// is transparent to the start of the block, but where a non-local hasn't /// been done. bool isNonLocal() const { return Value.getInt() == NonLocal; } - /// isNone - Return true if this MemDepResult represents a query that - /// doesn't depend on any instruction. - bool isNone() const { return Value.getInt() == None; } - /// getInst() - If this is a normal dependency, return the instruction that /// is depended on. Otherwise, return null. Instruction *getInst() const { return Value.getPointer(); } diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp index c75cbf2c59..44119d7b6b 100644 --- a/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -55,8 +55,7 @@ bool MemoryDependenceAnalysis::runOnFunction(Function &) { /// getCallSiteDependency - Private helper for finding the local dependencies /// of a call site. MemDepResult MemoryDependenceAnalysis:: -getCallSiteDependency(CallSite C, BasicBlock::iterator ScanIt, BasicBlock *BB) { - +getCallSiteDependency(CallSite CS, BasicBlock::iterator ScanIt, BasicBlock *BB) { // Walk backwards through the block, looking for dependencies while (ScanIt != BB->begin()) { Instruction *Inst = --ScanIt; @@ -76,17 +75,29 @@ getCallSiteDependency(CallSite C, BasicBlock::iterator ScanIt, BasicBlock *BB) { // FreeInsts erase the entire structure PointerSize = ~0UL; } else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) { - if (AA->getModRefBehavior(CallSite::get(Inst)) == - AliasAnalysis::DoesNotAccessMemory) + CallSite InstCS = CallSite::get(Inst); + // If these two calls do not interfere, look past it. + if (AA->getModRefInfo(CS, InstCS) == AliasAnalysis::NoModRef) continue; - return MemDepResult::get(Inst); + + // FIXME: If this is a ref/ref result, we should ignore it! + // X = strlen(P); + // Y = strlen(Q); + // Z = strlen(P); // Z = X + + // If they interfere, we generally return clobber. However, if they are + // calls to the same read-only functions we return Def. + if (!AA->onlyReadsMemory(CS) || CS.getCalledFunction() == 0 || + CS.getCalledFunction() != InstCS.getCalledFunction()) + return MemDepResult::getClobber(Inst); + return MemDepResult::getDef(Inst); } else { // Non-memory instruction. continue; } - if (AA->getModRefInfo(C, Pointer, PointerSize) != AliasAnalysis::NoModRef) - return MemDepResult::get(Inst); + if (AA->getModRefInfo(CS, Pointer, PointerSize) != AliasAnalysis::NoModRef) + return MemDepResult::getClobber(Inst); } // No dependence found. @@ -107,10 +118,10 @@ getDependencyFrom(Instruction *QueryInst, BasicBlock::iterator ScanIt, MemPtr = S->getPointerOperand(); MemSize = TD->getTypeStoreSize(S->getOperand(0)->getType()); MemVolatile = S->isVolatile(); - } else if (LoadInst* L = dyn_cast<LoadInst>(QueryInst)) { - MemPtr = L->getPointerOperand(); - MemSize = TD->getTypeStoreSize(L->getType()); - MemVolatile = L->isVolatile(); + } else if (LoadInst* LI = dyn_cast<LoadInst>(QueryInst)) { + MemPtr = LI->getPointerOperand(); + MemSize = TD->getTypeStoreSize(LI->getType()); + MemVolatile = LI->isVolatile(); } else if (VAArgInst* V = dyn_cast<VAArgInst>(QueryInst)) { MemPtr = V->getOperand(0); MemSize = TD->getTypeStoreSize(V->getType()); @@ -128,34 +139,49 @@ getDependencyFrom(Instruction *QueryInst, BasicBlock::iterator ScanIt, while (ScanIt != BB->begin()) { Instruction *Inst = --ScanIt; - // If the access is volatile and this is a volatile load/store, return a - // dependence. - if (MemVolatile && - ((isa<LoadInst>(Inst) && cast<LoadInst>(Inst)->isVolatile()) || - (isa<StoreInst>(Inst) && cast<StoreInst>(Inst)->isVolatile()))) - return MemDepResult::get(Inst); - // Values depend on loads if the pointers are must aliased. This means that // a load depends on another must aliased load from the same value. - if (LoadInst *L = dyn_cast<LoadInst>(Inst)) { - Value *Pointer = L->getPointerOperand(); - uint64_t PointerSize = TD->getTypeStoreSize(L->getType()); + if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { + // If the access is volatile and this is volatile, return a dependence. + if (MemVolatile && LI->isVolatile()) + return MemDepResult::getClobber(LI); + + Value *Pointer = LI->getPointerOperand(); + uint64_t PointerSize = TD->getTypeStoreSize(LI->getType()); - // If we found a pointer, check if it could be the same as our pointer + // If we found a pointer, check if it could be the same as our pointer. AliasAnalysis::AliasResult R = AA->alias(Pointer, PointerSize, MemPtr, MemSize); - if (R == AliasAnalysis::NoAlias) continue; // May-alias loads don't depend on each other without a dependence. if (isa<LoadInst>(QueryInst) && R == AliasAnalysis::MayAlias) continue; - return MemDepResult::get(Inst); + return MemDepResult::getDef(Inst); + } + + if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { + // If the access is volatile and this is volatile, return a dependence. + if (MemVolatile && SI->isVolatile()) + return MemDepResult::getClobber(SI); + + Value *Pointer = SI->getPointerOperand(); + uint64_t PointerSize = TD->getTypeStoreSize(SI->getOperand(0)->getType()); + + // If we found a pointer, check if it could be the same as our pointer. + AliasAnalysis::AliasResult R = + AA->alias(Pointer, PointerSize, MemPtr, MemSize); + + if (R == AliasAnalysis::NoAlias) + continue; + if (R == AliasAnalysis::MayAlias) + return MemDepResult::getClobber(Inst); + return MemDepResult::getDef(Inst); } // If this is an allocation, and if we know that the accessed pointer is to - // the allocation, return None. This means that there is no dependence and + // the allocation, return Def. This means that there is no dependence and // the access can be optimized based on that. For example, a load could // turn into undef. if (AllocationInst *AI = dyn_cast<AllocationInst>(Inst)) { @@ -163,22 +189,16 @@ getDependencyFrom(Instruction *QueryInst, BasicBlock::iterator ScanIt, if (AccessPtr == AI || AA->alias(AI, 1, AccessPtr, 1) == AliasAnalysis::MustAlias) - return MemDepResult::getNone(); + return MemDepResult::getDef(AI); continue; } - // See if this instruction mod/ref's the pointer. - AliasAnalysis::ModRefResult MRR = AA->getModRefInfo(Inst, MemPtr, MemSize); - - if (MRR == AliasAnalysis::NoModRef) - continue; - - // Loads don't depend on read-only instructions. - if (isa<LoadInst>(QueryInst) && MRR == AliasAnalysis::Ref) + // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer. + if (AA->getModRefInfo(Inst, MemPtr, MemSize) == AliasAnalysis::NoModRef) continue; // Otherwise, there is a dependence. - return MemDepResult::get(Inst); + return MemDepResult::getClobber(Inst); } // If we found nothing, return the non-local flag. diff --git a/lib/Transforms/Scalar/DeadStoreElimination.cpp b/lib/Transforms/Scalar/DeadStoreElimination.cpp index 0acc995e87..fa6f10b6b9 100644 --- a/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ b/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -148,25 +148,27 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { // If we're storing the same value back to a pointer that we just // loaded from, then the store can be removed; if (LoadInst* L = dyn_cast<LoadInst>(S->getOperand(0))) { - // FIXME: Don't do dep query if Parents don't match and other stuff! - MemDepResult dep = MD.getDependency(S); - DominatorTree& DT = getAnalysis<DominatorTree>(); - if (!S->isVolatile() && S->getParent() == L->getParent() && - S->getPointerOperand() == L->getPointerOperand() && - (!dep.isNormal() || DT.dominates(dep.getInst(), L))) { - - DeleteDeadInstruction(S); - if (BBI != BB.begin()) - --BBI; - NumFastStores++; - MadeChange = true; - } else + S->getPointerOperand() == L->getPointerOperand()) { + MemDepResult dep = MD.getDependency(S); + if (dep.isDef() && dep.getInst() == L) { + DeleteDeadInstruction(S); + if (BBI != BB.begin()) + --BBI; + NumFastStores++; + MadeChange = true; + } else { + // Update our most-recent-store map. + last = S; + } + } else { // Update our most-recent-store map. last = S; - } else + } + } else { // Update our most-recent-store map. last = S; + } } } diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp index 6e0296d210..c59b4abf76 100644 --- a/lib/Transforms/Scalar/GVN.cpp +++ b/lib/Transforms/Scalar/GVN.cpp @@ -461,30 +461,19 @@ uint32_t ValueTable::lookup_or_add(Value* V) { MemDepResult local_dep = MD->getDependency(C); - if (local_dep.isNone()) { + if (!local_dep.isDef() && !local_dep.isNonLocal()) { valueNumbering.insert(std::make_pair(V, nextValueNumber)); return nextValueNumber++; } - - if (Instruction *LocalDepInst = local_dep.getInst()) { - if (!isa<CallInst>(LocalDepInst)) { - valueNumbering.insert(std::make_pair(V, nextValueNumber)); - return nextValueNumber++; - } - - CallInst* local_cdep = cast<CallInst>(LocalDepInst); - - if (local_cdep->getCalledFunction() != C->getCalledFunction() || - local_cdep->getNumOperands() != C->getNumOperands()) { - valueNumbering.insert(std::make_pair(V, nextValueNumber)); - return nextValueNumber++; - } + + if (local_dep.isDef()) { + CallInst* local_cdep = cast<CallInst>(local_dep.getInst()); - if (!C->getCalledFunction()) { + if (local_cdep->getNumOperands() != C->getNumOperands()) { valueNumbering.insert(std::make_pair(V, nextValueNumber)); return nextValueNumber++; } - + for (unsigned i = 1; i < C->getNumOperands(); ++i) { uint32_t c_vn = lookup_or_add(C->getOperand(i)); uint32_t cd_vn = lookup_or_add(local_cdep->getOperand(i)); @@ -498,10 +487,12 @@ uint32_t ValueTable::lookup_or_add(Value* V) { valueNumbering.insert(std::make_pair(V, v)); return v; } - + // Non-local case. const MemoryDependenceAnalysis::NonLocalDepInfo &deps = MD->getNonLocalDependency(C); + // FIXME: call/call dependencies for readonly calls should return def, not + // clobber! Move the checking logic to MemDep! CallInst* cdep = 0; // Check to see if we have a single dominating call instruction that is @@ -514,7 +505,7 @@ uint32_t ValueTable::lookup_or_add(Value* V) { // We don't handle non-depedencies. If we already have a call, reject // instruction dependencies. - if (I->second.isNone() || cdep != 0) { + if (I->second.isClobber() || cdep != 0) { cdep = 0; break; } @@ -535,12 +526,7 @@ uint32_t ValueTable::lookup_or_add(Value* V) { return nextValueNumber++; } - if (cdep->getCalledFunction() != C->getCalledFunction() || - cdep->getNumOperands() != C->getNumOperands()) { - valueNumbering.insert(std::make_pair(V, nextValueNumber)); - return nextValueNumber++; - } - if (!C->getCalledFunction()) { + if (cdep->getNumOperands() != C->getNumOperands()) { valueNumbering.insert(std::make_pair(V, nextValueNumber)); return nextValueNumber++; } @@ -736,10 +722,8 @@ namespace { // Helper fuctions // FIXME: eliminate or document these better bool processLoad(LoadInst* L, - DenseMap<Value*, LoadInst*> &lastLoad, SmallVectorImpl<Instruction*> &toErase); bool processInstruction(Instruction* I, - DenseMap<Value*, LoadInst*>& lastSeenLoad, SmallVectorImpl<Instruction*> &toErase); bool processNonLocalLoad(LoadInst* L, SmallVectorImpl<Instruction*> &toErase); @@ -979,7 +963,15 @@ bool GVN::processNonLocalLoad(LoadInst *LI, continue; } - if (DepInfo.isNone()) { + if (DepInfo.isClobber()) { + UnavailableBlocks.push_back(DepBB); + continue; + } + + Instruction *DepInst = DepInfo.getInst(); + + // Loading the allocation -> undef. + if (isa<AllocationInst>(DepInst)) { ValuesPerBlock.push_back(std::make_pair(DepBB, UndefValue::get(LI->getType()))); continue; @@ -996,13 +988,6 @@ bool GVN::processNonLocalLoad(LoadInst *LI, continue; } - if (S->getPointerOperand() != LI->getPointerOperand() && - VN.getAliasAnalysis()->alias(S->getPointerOperand(), 1, - LI->getPointerOperand(), 1) - != AliasAnalysis::MustAlias) { - UnavailableBlocks.push_back(DepBB); - continue; - } ValuesPerBlock.push_back(std::make_pair(DepBB, S->getOperand(0))); } else if (LoadInst* LD = dyn_cast<LoadInst>(DepInfo.getInst())) { @@ -1010,14 +995,6 @@ bool GVN::processNonLocalLoad(LoadInst *LI, UnavailableBlocks.push_back(DepBB); continue; } - - if (LD->getPointerOperand() != LI->getPointerOperand() && - VN.getAliasAnalysis()->alias(LD->getPointerOperand(), 1, - LI->getPointerOperand(), 1) - != AliasAnalysis::MustAlias) { - UnavailableBlocks.push_back(DepBB); - continue; - } ValuesPerBlock.push_back(std::make_pair(DepBB, LD)); } else { UnavailableBlocks.push_back(DepBB); @@ -1156,84 +1133,64 @@ bool GVN::processNonLocalLoad(LoadInst *LI, /// processLoad - Attempt to eliminate a load, first by eliminating it /// locally, and then attempting non-local elimination if that fails. -bool GVN::processLoad(LoadInst *L, DenseMap<Value*, LoadInst*> &lastLoad, - SmallVectorImpl<Instruction*> &toErase) { - if (L->isVolatile()) { - lastLoad[L->getPointerOperand()] = L; +bool GVN::processLoad(LoadInst *L, SmallVectorImpl<Instruction*> &toErase) { + if (L->isVolatile()) return false; - } Value* pointer = L->getPointerOperand(); - LoadInst*& last = lastLoad[pointer]; - + // ... to a pointer that has been loaded from before... - bool removedNonLocal = false; MemDepResult dep = MD->getDependency(L); - if (dep.isNonLocal() && - L->getParent() != &L->getParent()->getParent()->getEntryBlock()) { - removedNonLocal = processNonLocalLoad(L, toErase); + + // If the value isn't available, don't do anything! + if (dep.isClobber()) + return false; + + // If it is defined in another block, try harder. + if (dep.isNonLocal()) { + if (L->getParent() == &L->getParent()->getParent()->getEntryBlock()) + return false; + return processNonLocalLoad(L, toErase); + } + + Instruction *DepInst = dep.getInst(); + if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) { + // Only forward substitute stores to loads of the same type. + // FIXME: Could do better! + if (DepSI->getPointerOperand()->getType() != pointer->getType()) + return false; - if (!removedNonLocal) - last = L; + // Remove it! + L->replaceAllUsesWith(DepSI->getOperand(0)); + toErase.push_back(L); + NumGVNLoad++; + return true; + } + + if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInst)) { + // Only forward substitute stores to loads of the same type. + // FIXME: Could do better! load i32 -> load i8 -> truncate on little endian. + if (DepLI->getType() != L->getType()) + return false; - return removedNonLocal; + // Remove it! + L->replaceAllUsesWith(DepLI); + toErase.push_back(L); + NumGVNLoad++; + return true; } - - bool deletedLoad = false; - - // Walk up the dependency chain until we either find - // a dependency we can use, or we can't walk any further - while (Instruction *DepInst = dep.getInst()) { - // ... that depends on a store ... - if (StoreInst* S = dyn_cast<StoreInst>(DepInst)) { - if (S->getPointerOperand() == pointer) { - // Remove it! - L->replaceAllUsesWith(S->getOperand(0)); - toErase.push_back(L); - deletedLoad = true; - NumGVNLoad++; - } - - // Whether we removed it or not, we can't - // go any further - break; - } else if (!isa<LoadInst>(DepInst)) { - // Only want to handle loads below. - break; - } else if (!last) { - // If we don't depend on a store, and we haven't - // been loaded before, bail. - break; - } else if (DepInst == last) { - // Remove it! - L->replaceAllUsesWith(last); - toErase.push_back(L); - deletedLoad = true; - NumGVNLoad++; - break; - } else { - dep = MD->getDependencyFrom(L, DepInst, DepInst->getParent()); - } - } - // If this load really doesn't depend on anything, then we must be loading an // undef value. This can happen when loading for a fresh allocation with no // intervening stores, for example. - if (dep.isNone()) { - // If this load depends directly on an allocation, there isn't - // anything stored there; therefore, we can optimize this load - // to undef. + if (isa<AllocationInst>(DepInst)) { L->replaceAllUsesWith(UndefValue::get(L->getType())); toErase.push_back(L); - deletedLoad = true; NumGVNLoad++; + return true; } - if (!deletedLoad) - last = L; - - return deletedLoad; + return false; } Value* GVN::lookupNumber(BasicBlock* BB, uint32_t num) { @@ -1257,10 +1214,9 @@ Value* GVN::lookupNumber(BasicBlock* BB, uint32_t num) { /// processInstruction - When calculating availability, handle an instruction /// by inserting it into the appropriate sets bool GVN::processInstruction(Instruction *I, - DenseMap<Value*, LoadInst*> &lastSeenLoad, SmallVectorImpl<Instruction*> &toErase) { if (LoadInst* L = dyn_cast<LoadInst>(I)) { - bool changed = processLoad(L, lastSeenLoad, toErase); + bool changed = processLoad(L, toErase); if (!changed) { unsigned num = VN.lookup_or_add(L); @@ -1362,7 +1318,6 @@ bool GVN::runOnFunction(Function& F) { bool GVN::processBlock(DomTreeNode* DTN) { BasicBlock* BB = DTN->getBlock(); SmallVector<Instruction*, 8> toErase; - DenseMap<Value*, LoadInst*> lastSeenLoad; bool changed_function = false; if (DTN->getIDom()) @@ -1373,7 +1328,7 @@ bool GVN::processBlock(DomTreeNode* DTN) { for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) { - changed_function |= processInstruction(BI, lastSeenLoad, toErase); + changed_function |= processInstruction(BI, toErase); if (toErase.empty()) { ++BI; continue; diff --git a/lib/Transforms/Scalar/MemCpyOptimizer.cpp b/lib/Transforms/Scalar/MemCpyOptimizer.cpp index 5d68388a99..5e9c5ea3d8 100644 --- a/lib/Transforms/Scalar/MemCpyOptimizer.cpp +++ b/lib/Transforms/Scalar/MemCpyOptimizer.cpp @@ -630,13 +630,12 @@ bool MemCpyOpt::processMemCpy(MemCpyInst* M) { // a) memcpy-memcpy xform which exposes redundance for DSE // b) call-memcpy xform for return slot optimization MemDepResult dep = MD.getDependency(M); - if (!dep.isNormal()) + if (!dep.isClobber()) return false; - else if (!isa<MemCpyInst>(dep.getInst())) { + if (!isa<MemCpyInst>(dep.getInst())) { if (CallInst* C = dyn_cast<CallInst>(dep.getInst())) return performCallSlotOptzn(M, C); - else - return false; + return false; } MemCpyInst* MDep = cast<MemCpyInst>(dep.getInst()); |