diff options
author | Benjamin Kramer <benny.kra@googlemail.com> | 2012-10-27 14:25:51 +0000 |
---|---|---|
committer | Benjamin Kramer <benny.kra@googlemail.com> | 2012-10-27 14:25:51 +0000 |
commit | d11c5d08a5f4f030d6e357378d0d46d93efd9a59 (patch) | |
tree | 95e77226ccabfa2fd6c5b171c64f038ccdef512d /lib/Transforms/Scalar | |
parent | 96c8735e28f2f89be37cdd907f680c6c1bf16052 (diff) | |
download | external_llvm-d11c5d08a5f4f030d6e357378d0d46d93efd9a59.zip external_llvm-d11c5d08a5f4f030d6e357378d0d46d93efd9a59.tar.gz external_llvm-d11c5d08a5f4f030d6e357378d0d46d93efd9a59.tar.bz2 |
LoopIdiom: Recognize memmove loops.
This turns loops like
for (unsigned i = 0; i != n; ++i)
p[i] = p[i+1];
into memmove, which has a highly optimized implementation in most libcs.
This was really easy with the new DependenceAnalysis :)
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166875 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Transforms/Scalar')
-rw-r--r-- | lib/Transforms/Scalar/LoopIdiomRecognize.cpp | 34 |
1 files changed, 24 insertions, 10 deletions
diff --git a/lib/Transforms/Scalar/LoopIdiomRecognize.cpp b/lib/Transforms/Scalar/LoopIdiomRecognize.cpp index 3050b1e..495d403 100644 --- a/lib/Transforms/Scalar/LoopIdiomRecognize.cpp +++ b/lib/Transforms/Scalar/LoopIdiomRecognize.cpp @@ -16,7 +16,7 @@ // TODO List: // // Future loop memory idioms to recognize: -// memcmp, memmove, strlen, etc. +// memcmp, strlen, etc. // Future floating point idioms to recognize in -ffast-math mode: // fpowi // Future integer operation idioms to recognize: @@ -60,8 +60,9 @@ #include "llvm/Transforms/Utils/Local.h" using namespace llvm; -STATISTIC(NumMemSet, "Number of memset's formed from loop stores"); -STATISTIC(NumMemCpy, "Number of memcpy's formed from loop load+stores"); +STATISTIC(NumMemSet, "Number of memsets formed from loop stores"); +STATISTIC(NumMemCpy, "Number of memcpys formed from loop load+stores"); +STATISTIC(NumMemMove, "Number of memmoves formed from loop load+stores"); namespace { class LoopIdiomRecognize : public LoopPass { @@ -532,6 +533,7 @@ processLoopStoreOfLoopLoad(StoreInst *SI, unsigned StoreSize, // stores) in the loop. We ignore the direct dependency between SI and LI here // and check it later. DependenceAnalysis &DA = getAnalysis<DependenceAnalysis>(); + bool isMemcpySafe = true; for (Loop::block_iterator BI = CurLoop->block_begin(), BE = CurLoop->block_end(); BI != BE; ++BI) for (BasicBlock::iterator I = (*BI)->begin(), E = (*BI)->end(); I != E; ++I) @@ -552,8 +554,14 @@ processLoopStoreOfLoopLoad(StoreInst *SI, unsigned StoreSize, // Now check the dependency between SI and LI. If there is no dependency we // can safely emit a memcpy. OwningPtr<Dependence> Dep(DA.depends(SI, LI, true)); - if (Dep) - return false; + if (Dep) { + // If there is a dependence but the direction is positive we can still + // safely turn this into memmove. + if (Dep->getLevels() != 1 || + Dep->getDirection(1) != Dependence::DVEntry::GT) + return false; + isMemcpySafe = false; + } // The trip count of the loop and the base pointer of the addrec SCEV is // guaranteed to be loop invariant, which means that it should dominate the @@ -590,12 +598,19 @@ processLoopStoreOfLoopLoad(StoreInst *SI, unsigned StoreSize, Value *NumBytes = Expander.expandCodeFor(NumBytesS, IntPtr, Preheader->getTerminator()); - CallInst *NewCall = - Builder.CreateMemCpy(StoreBasePtr, LoadBasePtr, NumBytes, - std::min(SI->getAlignment(), LI->getAlignment())); + CallInst *NewCall; + unsigned Align = std::min(SI->getAlignment(), LI->getAlignment()); + if (isMemcpySafe) { + NewCall = Builder.CreateMemCpy(StoreBasePtr, LoadBasePtr, NumBytes, Align); + ++NumMemCpy; + } else { + NewCall = Builder.CreateMemMove(StoreBasePtr, LoadBasePtr, NumBytes, Align); + ++NumMemMove; + } NewCall->setDebugLoc(SI->getDebugLoc()); - DEBUG(dbgs() << " Formed memcpy: " << *NewCall << "\n" + DEBUG(dbgs() << " Formed " << (isMemcpySafe ? "memcpy: " : "memmove: ") + << *NewCall << "\n" << " from load ptr=" << *LoadEv << " at: " << *LI << "\n" << " from store ptr=" << *StoreEv << " at: " << *SI << "\n"); @@ -603,6 +618,5 @@ processLoopStoreOfLoopLoad(StoreInst *SI, unsigned StoreSize, // Okay, the memset has been formed. Zap the original store and anything that // feeds into it. deleteDeadInstruction(SI, *SE, TLI); - ++NumMemCpy; return true; } |