LoopIdiomRecognize.cpp [plain text]
#define DEBUG_TYPE "loop-idiom"
#include "llvm/Transforms/Scalar.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Module.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Target/TargetLibraryInfo.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/IRBuilder.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/Statistic.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");
namespace {
class LoopIdiomRecognize : public LoopPass {
Loop *CurLoop;
const TargetData *TD;
DominatorTree *DT;
ScalarEvolution *SE;
TargetLibraryInfo *TLI;
public:
static char ID;
explicit LoopIdiomRecognize() : LoopPass(ID) {
initializeLoopIdiomRecognizePass(*PassRegistry::getPassRegistry());
}
bool runOnLoop(Loop *L, LPPassManager &LPM);
bool runOnLoopBlock(BasicBlock *BB, const SCEV *BECount,
SmallVectorImpl<BasicBlock*> &ExitBlocks);
bool processLoopStore(StoreInst *SI, const SCEV *BECount);
bool processLoopMemSet(MemSetInst *MSI, const SCEV *BECount);
bool processLoopStridedStore(Value *DestPtr, unsigned StoreSize,
unsigned StoreAlignment,
Value *SplatValue, Instruction *TheStore,
const SCEVAddRecExpr *Ev,
const SCEV *BECount);
bool processLoopStoreOfLoopLoad(StoreInst *SI, unsigned StoreSize,
const SCEVAddRecExpr *StoreEv,
const SCEVAddRecExpr *LoadEv,
const SCEV *BECount);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<LoopInfo>();
AU.addPreserved<LoopInfo>();
AU.addRequiredID(LoopSimplifyID);
AU.addPreservedID(LoopSimplifyID);
AU.addRequiredID(LCSSAID);
AU.addPreservedID(LCSSAID);
AU.addRequired<AliasAnalysis>();
AU.addPreserved<AliasAnalysis>();
AU.addRequired<ScalarEvolution>();
AU.addPreserved<ScalarEvolution>();
AU.addPreserved<DominatorTree>();
AU.addRequired<DominatorTree>();
AU.addRequired<TargetLibraryInfo>();
}
};
}
char LoopIdiomRecognize::ID = 0;
INITIALIZE_PASS_BEGIN(LoopIdiomRecognize, "loop-idiom", "Recognize loop idioms",
false, false)
INITIALIZE_PASS_DEPENDENCY(LoopInfo)
INITIALIZE_PASS_DEPENDENCY(DominatorTree)
INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
INITIALIZE_PASS_DEPENDENCY(LCSSA)
INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
INITIALIZE_PASS_END(LoopIdiomRecognize, "loop-idiom", "Recognize loop idioms",
false, false)
Pass *llvm::createLoopIdiomPass() { return new LoopIdiomRecognize(); }
static void deleteDeadInstruction(Instruction *I, ScalarEvolution &SE) {
SmallVector<Instruction*, 32> NowDeadInsts;
NowDeadInsts.push_back(I);
do {
Instruction *DeadInst = NowDeadInsts.pop_back_val();
SE.forgetValue(DeadInst);
for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) {
Value *Op = DeadInst->getOperand(op);
DeadInst->setOperand(op, 0);
if (!Op->use_empty()) continue;
if (Instruction *OpI = dyn_cast<Instruction>(Op))
if (isInstructionTriviallyDead(OpI))
NowDeadInsts.push_back(OpI);
}
DeadInst->eraseFromParent();
} while (!NowDeadInsts.empty());
}
static void deleteIfDeadInstruction(Value *V, ScalarEvolution &SE) {
if (Instruction *I = dyn_cast<Instruction>(V))
if (isInstructionTriviallyDead(I))
deleteDeadInstruction(I, SE);
}
bool LoopIdiomRecognize::runOnLoop(Loop *L, LPPassManager &LPM) {
CurLoop = L;
StringRef Name = L->getHeader()->getParent()->getName();
if (Name == "memset" || Name == "memcpy")
return false;
SE = &getAnalysis<ScalarEvolution>();
if (!SE->hasLoopInvariantBackedgeTakenCount(L))
return false;
const SCEV *BECount = SE->getBackedgeTakenCount(L);
if (isa<SCEVCouldNotCompute>(BECount)) return false;
if (const SCEVConstant *BECst = dyn_cast<SCEVConstant>(BECount))
if (BECst->getValue()->getValue() == 0)
return false;
TD = getAnalysisIfAvailable<TargetData>();
if (TD == 0) return false;
DT = &getAnalysis<DominatorTree>();
LoopInfo &LI = getAnalysis<LoopInfo>();
TLI = &getAnalysis<TargetLibraryInfo>();
SmallVector<BasicBlock*, 8> ExitBlocks;
CurLoop->getUniqueExitBlocks(ExitBlocks);
DEBUG(dbgs() << "loop-idiom Scanning: F["
<< L->getHeader()->getParent()->getName()
<< "] Loop %" << L->getHeader()->getName() << "\n");
bool MadeChange = false;
for (Loop::block_iterator BI = L->block_begin(), E = L->block_end(); BI != E;
++BI) {
if (LI.getLoopFor(*BI) != CurLoop)
continue;
MadeChange |= runOnLoopBlock(*BI, BECount, ExitBlocks);
}
return MadeChange;
}
bool LoopIdiomRecognize::runOnLoopBlock(BasicBlock *BB, const SCEV *BECount,
SmallVectorImpl<BasicBlock*> &ExitBlocks) {
for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
if (!DT->dominates(BB, ExitBlocks[i]))
return false;
bool MadeChange = false;
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
Instruction *Inst = I++;
if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
WeakVH InstPtr(I);
if (!processLoopStore(SI, BECount)) continue;
MadeChange = true;
if (InstPtr == 0)
I = BB->begin();
continue;
}
if (MemSetInst *MSI = dyn_cast<MemSetInst>(Inst)) {
WeakVH InstPtr(I);
if (!processLoopMemSet(MSI, BECount)) continue;
MadeChange = true;
if (InstPtr == 0)
I = BB->begin();
continue;
}
}
return MadeChange;
}
bool LoopIdiomRecognize::processLoopStore(StoreInst *SI, const SCEV *BECount) {
if (!SI->isSimple()) return false;
Value *StoredVal = SI->getValueOperand();
Value *StorePtr = SI->getPointerOperand();
uint64_t SizeInBits = TD->getTypeSizeInBits(StoredVal->getType());
if ((SizeInBits & 7) || (SizeInBits >> 32) != 0)
return false;
const SCEVAddRecExpr *StoreEv =
dyn_cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr));
if (StoreEv == 0 || StoreEv->getLoop() != CurLoop || !StoreEv->isAffine())
return false;
unsigned StoreSize = (unsigned)SizeInBits >> 3;
const SCEVConstant *Stride = dyn_cast<SCEVConstant>(StoreEv->getOperand(1));
if (Stride == 0 || StoreSize != Stride->getValue()->getValue()) {
if (0 && Stride && StoreSize == -Stride->getValue()->getValue()) {
dbgs() << "NEGATIVE STRIDE: " << *SI << "\n";
dbgs() << "BB: " << *SI->getParent();
}
return false;
}
if (processLoopStridedStore(StorePtr, StoreSize, SI->getAlignment(),
StoredVal, SI, StoreEv, BECount))
return true;
if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) {
const SCEVAddRecExpr *LoadEv =
dyn_cast<SCEVAddRecExpr>(SE->getSCEV(LI->getOperand(0)));
if (LoadEv && LoadEv->getLoop() == CurLoop && LoadEv->isAffine() &&
StoreEv->getOperand(1) == LoadEv->getOperand(1) && LI->isSimple())
if (processLoopStoreOfLoopLoad(SI, StoreSize, StoreEv, LoadEv, BECount))
return true;
}
return false;
}
bool LoopIdiomRecognize::
processLoopMemSet(MemSetInst *MSI, const SCEV *BECount) {
if (MSI->isVolatile() || !isa<ConstantInt>(MSI->getLength())) return false;
if (!TLI->has(LibFunc::memset))
return false;
Value *Pointer = MSI->getDest();
const SCEVAddRecExpr *Ev = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Pointer));
if (Ev == 0 || Ev->getLoop() != CurLoop || !Ev->isAffine())
return false;
uint64_t SizeInBytes = cast<ConstantInt>(MSI->getLength())->getZExtValue();
if ((SizeInBytes >> 32) != 0)
return false;
const SCEVConstant *Stride = dyn_cast<SCEVConstant>(Ev->getOperand(1));
if (Stride == 0 || MSI->getLength() != Stride->getValue())
return false;
return processLoopStridedStore(Pointer, (unsigned)SizeInBytes,
MSI->getAlignment(), MSI->getValue(),
MSI, Ev, BECount);
}
static bool mayLoopAccessLocation(Value *Ptr,AliasAnalysis::ModRefResult Access,
Loop *L, const SCEV *BECount,
unsigned StoreSize, AliasAnalysis &AA,
Instruction *IgnoredStore) {
uint64_t AccessSize = AliasAnalysis::UnknownSize;
if (const SCEVConstant *BECst = dyn_cast<SCEVConstant>(BECount))
AccessSize = (BECst->getValue()->getZExtValue()+1)*StoreSize;
AliasAnalysis::Location StoreLoc(Ptr, AccessSize);
for (Loop::block_iterator BI = L->block_begin(), E = L->block_end(); BI != E;
++BI)
for (BasicBlock::iterator I = (*BI)->begin(), E = (*BI)->end(); I != E; ++I)
if (&*I != IgnoredStore &&
(AA.getModRefInfo(I, StoreLoc) & Access))
return true;
return false;
}
static Constant *getMemSetPatternValue(Value *V, const TargetData &TD) {
Constant *C = dyn_cast<Constant>(V);
if (C == 0) return 0;
uint64_t Size = TD.getTypeSizeInBits(V->getType());
if (Size == 0 || (Size & 7) || (Size & (Size-1)))
return 0;
if (TD.isBigEndian())
return 0;
Size /= 8;
if (Size > 16) return 0;
if (Size == 16) return C;
unsigned ArraySize = 16/Size;
ArrayType *AT = ArrayType::get(V->getType(), ArraySize);
return ConstantArray::get(AT, std::vector<Constant*>(ArraySize, C));
}
bool LoopIdiomRecognize::
processLoopStridedStore(Value *DestPtr, unsigned StoreSize,
unsigned StoreAlignment, Value *StoredVal,
Instruction *TheStore, const SCEVAddRecExpr *Ev,
const SCEV *BECount) {
Value *SplatValue = isBytewiseValue(StoredVal);
Constant *PatternValue = 0;
if (SplatValue && TLI->has(LibFunc::memset) &&
CurLoop->isLoopInvariant(SplatValue)) {
PatternValue = 0;
} else if (TLI->has(LibFunc::memset_pattern16) &&
(PatternValue = getMemSetPatternValue(StoredVal, *TD))) {
SplatValue = 0;
} else {
return false;
}
BasicBlock *Preheader = CurLoop->getLoopPreheader();
IRBuilder<> Builder(Preheader->getTerminator());
SCEVExpander Expander(*SE, "loop-idiom");
unsigned AddrSpace = cast<PointerType>(DestPtr->getType())->getAddressSpace();
Value *BasePtr =
Expander.expandCodeFor(Ev->getStart(), Builder.getInt8PtrTy(AddrSpace),
Preheader->getTerminator());
if (mayLoopAccessLocation(BasePtr, AliasAnalysis::ModRef,
CurLoop, BECount,
StoreSize, getAnalysis<AliasAnalysis>(), TheStore)){
Expander.clear();
deleteIfDeadInstruction(BasePtr, *SE);
return false;
}
Type *IntPtr = TD->getIntPtrType(DestPtr->getContext());
BECount = SE->getTruncateOrZeroExtend(BECount, IntPtr);
const SCEV *NumBytesS = SE->getAddExpr(BECount, SE->getConstant(IntPtr, 1),
SCEV::FlagNUW);
if (StoreSize != 1)
NumBytesS = SE->getMulExpr(NumBytesS, SE->getConstant(IntPtr, StoreSize),
SCEV::FlagNUW);
Value *NumBytes =
Expander.expandCodeFor(NumBytesS, IntPtr, Preheader->getTerminator());
CallInst *NewCall;
if (SplatValue)
NewCall = Builder.CreateMemSet(BasePtr, SplatValue,NumBytes,StoreAlignment);
else {
Module *M = TheStore->getParent()->getParent()->getParent();
Value *MSP = M->getOrInsertFunction("memset_pattern16",
Builder.getVoidTy(),
Builder.getInt8PtrTy(),
Builder.getInt8PtrTy(), IntPtr,
(void*)0);
GlobalVariable *GV = new GlobalVariable(*M, PatternValue->getType(), true,
GlobalValue::InternalLinkage,
PatternValue, ".memset_pattern");
GV->setUnnamedAddr(true); GV->setAlignment(16);
Value *PatternPtr = ConstantExpr::getBitCast(GV, Builder.getInt8PtrTy());
NewCall = Builder.CreateCall3(MSP, BasePtr, PatternPtr, NumBytes);
}
DEBUG(dbgs() << " Formed memset: " << *NewCall << "\n"
<< " from store to: " << *Ev << " at: " << *TheStore << "\n");
NewCall->setDebugLoc(TheStore->getDebugLoc());
deleteDeadInstruction(TheStore, *SE);
++NumMemSet;
return true;
}
bool LoopIdiomRecognize::
processLoopStoreOfLoopLoad(StoreInst *SI, unsigned StoreSize,
const SCEVAddRecExpr *StoreEv,
const SCEVAddRecExpr *LoadEv,
const SCEV *BECount) {
if (!TLI->has(LibFunc::memcpy))
return false;
LoadInst *LI = cast<LoadInst>(SI->getValueOperand());
BasicBlock *Preheader = CurLoop->getLoopPreheader();
IRBuilder<> Builder(Preheader->getTerminator());
SCEVExpander Expander(*SE, "loop-idiom");
Value *StoreBasePtr =
Expander.expandCodeFor(StoreEv->getStart(),
Builder.getInt8PtrTy(SI->getPointerAddressSpace()),
Preheader->getTerminator());
if (mayLoopAccessLocation(StoreBasePtr, AliasAnalysis::ModRef,
CurLoop, BECount, StoreSize,
getAnalysis<AliasAnalysis>(), SI)) {
Expander.clear();
deleteIfDeadInstruction(StoreBasePtr, *SE);
return false;
}
Value *LoadBasePtr =
Expander.expandCodeFor(LoadEv->getStart(),
Builder.getInt8PtrTy(LI->getPointerAddressSpace()),
Preheader->getTerminator());
if (mayLoopAccessLocation(LoadBasePtr, AliasAnalysis::Mod, CurLoop, BECount,
StoreSize, getAnalysis<AliasAnalysis>(), SI)) {
Expander.clear();
deleteIfDeadInstruction(LoadBasePtr, *SE);
deleteIfDeadInstruction(StoreBasePtr, *SE);
return false;
}
Type *IntPtr = TD->getIntPtrType(SI->getContext());
BECount = SE->getTruncateOrZeroExtend(BECount, IntPtr);
const SCEV *NumBytesS = SE->getAddExpr(BECount, SE->getConstant(IntPtr, 1),
SCEV::FlagNUW);
if (StoreSize != 1)
NumBytesS = SE->getMulExpr(NumBytesS, SE->getConstant(IntPtr, StoreSize),
SCEV::FlagNUW);
Value *NumBytes =
Expander.expandCodeFor(NumBytesS, IntPtr, Preheader->getTerminator());
CallInst *NewCall =
Builder.CreateMemCpy(StoreBasePtr, LoadBasePtr, NumBytes,
std::min(SI->getAlignment(), LI->getAlignment()));
NewCall->setDebugLoc(SI->getDebugLoc());
DEBUG(dbgs() << " Formed memcpy: " << *NewCall << "\n"
<< " from load ptr=" << *LoadEv << " at: " << *LI << "\n"
<< " from store ptr=" << *StoreEv << " at: " << *SI << "\n");
deleteDeadInstruction(SI, *SE);
++NumMemCpy;
return true;
}