diff options
| -rw-r--r-- | include/llvm/Analysis/MemoryDependenceAnalysis.h | 11 | ||||
| -rw-r--r-- | lib/Analysis/MemDepPrinter.cpp | 29 | ||||
| -rw-r--r-- | lib/Analysis/MemoryDependenceAnalysis.cpp | 40 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/DeadStoreElimination.cpp | 25 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/GVN.cpp | 32 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/MemCpyOptimizer.cpp | 2 |
6 files changed, 84 insertions, 55 deletions
diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h index b56fe08e23..34860e712f 100644 --- a/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -90,18 +90,27 @@ namespace llvm { /// get methods: These are static ctor methods for creating various /// MemDepResult kinds. static MemDepResult getDef(Instruction *Inst) { + assert(Inst && "Def requires inst"); return MemDepResult(PairTy(Inst, Def)); } static MemDepResult getClobber(Instruction *Inst) { + assert(Inst && "Clobber requires inst"); return MemDepResult(PairTy(Inst, Clobber)); } static MemDepResult getNonLocal() { return MemDepResult(PairTy(0, NonLocal)); } + static MemDepResult getUnknown() { + return MemDepResult(PairTy(0, Clobber)); + } /// isClobber - Return true if this MemDepResult represents a query that is /// a instruction clobber dependency. - bool isClobber() const { return Value.getInt() == Clobber; } + bool isClobber() const { return Value.getInt() == Clobber && getInst(); } + + /// isUnknown - Return true if this MemDepResult represents a query which + /// cannot and/or will not be computed. + bool isUnknown() const { return Value.getInt() == Clobber && !getInst(); } /// isDef - Return true if this MemDepResult represents a query that is /// a instruction definition dependency. diff --git a/lib/Analysis/MemDepPrinter.cpp b/lib/Analysis/MemDepPrinter.cpp index 64d215c37c..2283db0bc4 100644 --- a/lib/Analysis/MemDepPrinter.cpp +++ b/lib/Analysis/MemDepPrinter.cpp @@ -79,8 +79,8 @@ bool MemDepPrinter::runOnFunction(Function &F) { MemDepResult Res = MDA.getDependency(Inst); if (!Res.isNonLocal()) { - assert(Res.isClobber() != Res.isDef() && - "Local dep should be def or clobber!"); + assert((Res.isUnknown() || Res.isClobber() || Res.isDef()) && + "Local dep should be unknown, def or clobber!"); Deps[Inst].insert(std::make_pair(InstAndClobberFlag(Res.getInst(), Res.isClobber()), static_cast<BasicBlock *>(0))); @@ -92,8 +92,9 @@ bool MemDepPrinter::runOnFunction(Function &F) { for (MemoryDependenceAnalysis::NonLocalDepInfo::const_iterator I = NLDI.begin(), E = NLDI.end(); I != E; ++I) { const MemDepResult &Res = I->getResult(); - assert(Res.isClobber() != Res.isDef() && - "Resolved non-local call dep should be def or clobber!"); + assert((Res.isUnknown() || Res.isClobber() || Res.isDef()) && + "Resolved non-local call dep should be unknown, def or " + "clobber!"); InstDeps.insert(std::make_pair(InstAndClobberFlag(Res.getInst(), Res.isClobber()), I->getBB())); @@ -148,16 +149,24 @@ void MemDepPrinter::print(raw_ostream &OS, const Module *M) const { bool isClobber = I->first.getInt(); const BasicBlock *DepBB = I->second; - OS << " " << (isClobber ? "Clobber" : " Def"); + OS << " "; + if (!DepInst) + OS << "Unknown"; + else if (isClobber) + OS << "Clobber"; + else + OS << " Def"; if (DepBB) { OS << " in block "; WriteAsOperand(OS, DepBB, /*PrintType=*/false, M); } - OS << " from: "; - if (DepInst == Inst) - OS << "<unspecified>"; - else - DepInst->print(OS); + if (DepInst) { + OS << " from: "; + if (DepInst == Inst) + OS << "<unspecified>"; + else + DepInst->print(OS); + } OS << "\n"; } diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp index 5f640c01d2..ed638ff1c0 100644 --- a/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -215,11 +215,11 @@ getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall, } } - // No dependence found. If this is the entry block of the function, it is a - // clobber, otherwise it is non-local. + // No dependence found. If this is the entry block of the function, it is + // unknown, otherwise it is non-local. if (BB != &BB->getParent()->getEntryBlock()) return MemDepResult::getNonLocal(); - return MemDepResult::getClobber(ScanIt); + return MemDepResult::getUnknown(); } /// isLoadLoadClobberIfExtendedToFullWidth - Return true if LI is a load that @@ -458,11 +458,11 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, } } - // No dependence found. If this is the entry block of the function, it is a - // clobber, otherwise it is non-local. + // No dependence found. If this is the entry block of the function, it is + // unknown, otherwise it is non-local. if (BB != &BB->getParent()->getEntryBlock()) return MemDepResult::getNonLocal(); - return MemDepResult::getClobber(ScanIt); + return MemDepResult::getUnknown(); } /// getDependency - Return the instruction on which a memory operation @@ -490,12 +490,12 @@ MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { // Do the scan. if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) { - // No dependence found. If this is the entry block of the function, it is a - // clobber, otherwise it is non-local. + // No dependence found. If this is the entry block of the function, it is + // unknown, otherwise it is non-local. if (QueryParent != &QueryParent->getParent()->getEntryBlock()) LocalCache = MemDepResult::getNonLocal(); else - LocalCache = MemDepResult::getClobber(QueryInst); + LocalCache = MemDepResult::getUnknown(); } else { AliasAnalysis::Location MemLoc; AliasAnalysis::ModRefResult MR = GetLocation(QueryInst, MemLoc, AA); @@ -514,7 +514,7 @@ MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { QueryParent); } else // Non-memory instruction. - LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos)); + LocalCache = MemDepResult::getUnknown(); } // Remember the result! @@ -648,10 +648,10 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { Dep = getCallSiteDependencyFrom(QueryCS, isReadonlyCall,ScanPos, DirtyBB); } else if (DirtyBB != &DirtyBB->getParent()->getEntryBlock()) { // No dependence found. If this is the entry block of the function, it is - // a clobber, otherwise it is non-local. + // a clobber, otherwise it is unknown. Dep = MemDepResult::getNonLocal(); } else { - Dep = MemDepResult::getClobber(ScanPos); + Dep = MemDepResult::getUnknown(); } // If we had a dirty entry for the block, update it. Otherwise, just add @@ -707,7 +707,7 @@ getNonLocalPointerDependency(const AliasAnalysis::Location &Loc, bool isLoad, return; Result.clear(); Result.push_back(NonLocalDepResult(FromBB, - MemDepResult::getClobber(FromBB->begin()), + MemDepResult::getUnknown(), const_cast<Value *>(Loc.Ptr))); } @@ -769,7 +769,7 @@ GetNonLocalInfoForBlock(const AliasAnalysis::Location &Loc, // If the block has a dependency (i.e. it isn't completely transparent to // the value), remember the reverse association because we just added it // to Cache! - if (Dep.isNonLocal()) + if (Dep.isNonLocal() || Dep.isUnknown()) return Dep; // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently @@ -1091,16 +1091,14 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, // If getNonLocalPointerDepFromBB fails here, that means the cached // result conflicted with the Visited list; we have to conservatively - // assume a clobber, but this also does not block PRE of the load. + // assume it is unknown, but this also does not block PRE of the load. if (!CanTranslate || getNonLocalPointerDepFromBB(PredPointer, Loc.getWithNewPtr(PredPtrVal), isLoad, Pred, Result, Visited)) { // Add the entry to the Result list. - NonLocalDepResult Entry(Pred, - MemDepResult::getClobber(Pred->getTerminator()), - PredPtrVal); + NonLocalDepResult Entry(Pred, MemDepResult::getUnknown(), PredPtrVal); Result.push_back(Entry); // Since we had a phi translation failure, the cache for CacheKey won't @@ -1145,8 +1143,7 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, // results from the set". Clear out the indicator for this. CacheInfo->Pair = BBSkipFirstBlockPair(); - // If *nothing* works, mark the pointer as being clobbered by the first - // instruction in this block. + // If *nothing* works, mark the pointer as unknown. // // If this is the magic first block, return this as a clobber of the whole // incoming value. Since we can't phi translate to one of the predecessors, @@ -1161,8 +1158,7 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, assert(I->getResult().isNonLocal() && "Should only be here with transparent block"); - I->setResult(MemDepResult::getClobber(BB->getTerminator())); - ReverseNonLocalPtrDeps[BB->getTerminator()].insert(CacheKey); + I->setResult(MemDepResult::getUnknown()); Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(), Pointer.getAddr())); break; diff --git a/lib/Transforms/Scalar/DeadStoreElimination.cpp b/lib/Transforms/Scalar/DeadStoreElimination.cpp index 53e46400dc..cb9b5bebc5 100644 --- a/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ b/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -437,12 +437,9 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { MemDepResult InstDep = MD->getDependency(Inst); - // Ignore non-local store liveness. + // Ignore any store where we can't find a local dependence. // FIXME: cross-block DSE would be fun. :) - if (InstDep.isNonLocal() || - // Ignore self dependence, which happens in the entry block of the - // function. - InstDep.getInst() == Inst) + if (InstDep.isNonLocal() || InstDep.isUnknown()) continue; // If we're storing the same value back to a pointer that we just @@ -478,7 +475,7 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { if (Loc.Ptr == 0) continue; - while (!InstDep.isNonLocal()) { + while (!InstDep.isNonLocal() && !InstDep.isUnknown()) { // Get the memory clobbered by the instruction we depend on. MemDep will // skip any instructions that 'Loc' clearly doesn't interact with. If we // end up depending on a may- or must-aliased load, then we can't optimize @@ -542,24 +539,26 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { /// HandleFree - Handle frees of entire structures whose dependency is a store /// to a field of that structure. bool DSE::HandleFree(CallInst *F) { + bool MadeChange = false; + MemDepResult Dep = MD->getDependency(F); - do { - if (Dep.isNonLocal()) return false; - + + while (!Dep.isNonLocal() && !Dep.isUnknown()) { Instruction *Dependency = Dep.getInst(); if (!hasMemoryWrite(Dependency) || !isRemovable(Dependency)) - return false; + return MadeChange; Value *DepPointer = GetUnderlyingObject(getStoredPointerOperand(Dependency)); // Check for aliasing. if (!AA->isMustAlias(F->getArgOperand(0), DepPointer)) - return false; + return MadeChange; // DCE instructions only used to calculate that store DeleteDeadInstruction(Dependency, *MD); ++NumFastStores; + MadeChange = true; // Inst's old Dependency is now deleted. Compute the next dependency, // which may also be dead, as in @@ -567,9 +566,9 @@ bool DSE::HandleFree(CallInst *F) { // s[1] = 0; // This has just been deleted. // free(s); Dep = MD->getDependency(F); - } while (!Dep.isNonLocal()); + }; - return true; + return MadeChange; } /// handleEndBlock - Remove dead stores to stack-allocated locations in the diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp index 2515fd112c..0e1e6f32e4 100644 --- a/lib/Transforms/Scalar/GVN.cpp +++ b/lib/Transforms/Scalar/GVN.cpp @@ -227,21 +227,19 @@ uint32_t ValueTable::lookup_or_add_call(CallInst* C) { // Non-local case. const MemoryDependenceAnalysis::NonLocalDepInfo &deps = MD->getNonLocalCallDependency(CallSite(C)); - // FIXME: call/call dependencies for readonly calls should return def, not - // clobber! Move the checking logic to MemDep! + // FIXME: Move the checking logic to MemDep! CallInst* cdep = 0; // Check to see if we have a single dominating call instruction that is // identical to C. for (unsigned i = 0, e = deps.size(); i != e; ++i) { const NonLocalDepEntry *I = &deps[i]; - // Ignore non-local dependencies. if (I->getResult().isNonLocal()) continue; - // We don't handle non-depedencies. If we already have a call, reject + // We don't handle non-definitions. If we already have a call, reject // instruction dependencies. - if (I->getResult().isClobber() || cdep != 0) { + if (!I->getResult().isDef() || cdep != 0) { cdep = 0; break; } @@ -1224,12 +1222,11 @@ bool GVN::processNonLocalLoad(LoadInst *LI) { // If we had a phi translation failure, we'll have a single entry which is a // clobber in the current block. Reject this early. - if (Deps.size() == 1 && Deps[0].getResult().isClobber() && - Deps[0].getResult().getInst()->getParent() == LI->getParent()) { + if (Deps.size() == 1 && Deps[0].getResult().isUnknown()) { DEBUG( dbgs() << "GVN: non-local load "; WriteAsOperand(dbgs(), LI); - dbgs() << " is clobbered by " << *Deps[0].getResult().getInst() << '\n'; + dbgs() << " has unknown dependencies\n"; ); return false; } @@ -1245,6 +1242,11 @@ bool GVN::processNonLocalLoad(LoadInst *LI) { BasicBlock *DepBB = Deps[i].getBB(); MemDepResult DepInfo = Deps[i].getResult(); + if (DepInfo.isUnknown()) { + UnavailableBlocks.push_back(DepBB); + continue; + } + if (DepInfo.isClobber()) { // The address being loaded in this non-local block may not be the same as // the pointer operand of the load if PHI translation occurs. Make sure @@ -1305,6 +1307,8 @@ bool GVN::processNonLocalLoad(LoadInst *LI) { continue; } + assert(DepInfo.isDef() && "Expecting def here"); + Instruction *DepInst = DepInfo.getInst(); // Loading the allocation -> undef. @@ -1691,10 +1695,22 @@ bool GVN::processLoad(LoadInst *L) { return false; } + if (Dep.isUnknown()) { + DEBUG( + // fast print dep, using operator<< on instruction is too slow. + dbgs() << "GVN: load "; + WriteAsOperand(dbgs(), L); + dbgs() << " has unknown dependence\n"; + ); + return false; + } + // If it is defined in another block, try harder. if (Dep.isNonLocal()) return processNonLocalLoad(L); + assert(Dep.isDef() && "Expecting def here"); + Instruction *DepInst = Dep.getInst(); if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) { Value *StoredVal = DepSI->getValueOperand(); diff --git a/lib/Transforms/Scalar/MemCpyOptimizer.cpp b/lib/Transforms/Scalar/MemCpyOptimizer.cpp index be5aa2ea58..3347fc3519 100644 --- a/lib/Transforms/Scalar/MemCpyOptimizer.cpp +++ b/lib/Transforms/Scalar/MemCpyOptimizer.cpp @@ -497,7 +497,7 @@ bool MemCpyOpt::processStore(StoreInst *SI, BasicBlock::iterator &BBI) { // Check that nothing touches the dest of the "copy" between // the call and the store. MemDepResult sdep = MD->getDependency(SI); - if (!sdep.isNonLocal()) { + if (!sdep.isNonLocal() && !sdep.isUnknown()) { bool FoundCall = false; for (BasicBlock::iterator I = SI, E = sdep.getInst(); I != E; --I) { if (&*I == C) { |