#include "llvm/Transforms/Scalar.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AliasSetTracker.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/PredIteratorCache.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetLibraryInfo.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
#include <algorithm>
using namespace llvm;
#define DEBUG_TYPE "licm"
STATISTIC(NumSunk , "Number of instructions sunk out of loop");
STATISTIC(NumHoisted , "Number of instructions hoisted out of loop");
STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk");
STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk");
STATISTIC(NumPromoted , "Number of memory locations promoted to registers");
static cl::opt<bool>
DisablePromotion("disable-licm-promotion", cl::Hidden,
cl::desc("Disable memory promotion in LICM pass"));
namespace {
struct LICM : public LoopPass {
static char ID; LICM() : LoopPass(ID) {
initializeLICMPass(*PassRegistry::getPassRegistry());
}
bool runOnLoop(Loop *L, LPPassManager &LPM) override;
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
AU.addRequired<DominatorTreeWrapperPass>();
AU.addRequired<LoopInfo>();
AU.addRequiredID(LoopSimplifyID);
AU.addPreservedID(LoopSimplifyID);
AU.addRequiredID(LCSSAID);
AU.addPreservedID(LCSSAID);
AU.addRequired<AliasAnalysis>();
AU.addPreserved<AliasAnalysis>();
AU.addPreserved<ScalarEvolution>();
AU.addRequired<TargetLibraryInfo>();
}
using llvm::Pass::doFinalization;
bool doFinalization() override {
assert(LoopToAliasSetMap.empty() && "Didn't free loop alias sets");
return false;
}
private:
AliasAnalysis *AA; LoopInfo *LI; DominatorTree *DT;
const DataLayout *DL; TargetLibraryInfo *TLI;
bool Changed; BasicBlock *Preheader; Loop *CurLoop; AliasSetTracker *CurAST; bool MayThrow; DenseMap<Loop*, AliasSetTracker*> LoopToAliasSetMap;
void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To,
Loop *L) override;
void deleteAnalysisValue(Value *V, Loop *L) override;
void SinkRegion(DomTreeNode *N);
void HoistRegion(DomTreeNode *N);
bool inSubLoop(BasicBlock *BB) {
assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
return LI->getLoopFor(BB) != CurLoop;
}
void sink(Instruction &I);
void hoist(Instruction &I);
bool isSafeToExecuteUnconditionally(Instruction &I);
bool isGuaranteedToExecute(Instruction &I);
bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
const AAMDNodes &AAInfo) {
return CurAST->getAliasSetForPointer(V, Size, AAInfo).isMod();
}
bool canSinkOrHoistInst(Instruction &I);
bool isNotUsedInLoop(Instruction &I);
void PromoteAliasSet(AliasSet &AS,
SmallVectorImpl<BasicBlock*> &ExitBlocks,
SmallVectorImpl<Instruction*> &InsertPts,
PredIteratorCache &PIC);
Instruction *CloneInstructionInExitBlock(Instruction &I,
BasicBlock &ExitBlock,
PHINode &PN);
};
}
char LICM::ID = 0;
INITIALIZE_PASS_BEGIN(LICM, "licm", "Loop Invariant Code Motion", false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopInfo)
INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
INITIALIZE_PASS_DEPENDENCY(LCSSA)
INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
INITIALIZE_PASS_END(LICM, "licm", "Loop Invariant Code Motion", false, false)
Pass *llvm::createLICMPass() { return new LICM(); }
bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) {
if (skipOptnoneFunction(L))
return false;
Changed = false;
LI = &getAnalysis<LoopInfo>();
AA = &getAnalysis<AliasAnalysis>();
DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
DL = DLP ? &DLP->getDataLayout() : nullptr;
TLI = &getAnalysis<TargetLibraryInfo>();
assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
CurAST = new AliasSetTracker(*AA);
for (Loop::iterator LoopItr = L->begin(), LoopItrE = L->end();
LoopItr != LoopItrE; ++LoopItr) {
Loop *InnerL = *LoopItr;
AliasSetTracker *InnerAST = LoopToAliasSetMap[InnerL];
assert(InnerAST && "Where is my AST?");
CurAST->add(*InnerAST);
delete InnerAST;
LoopToAliasSetMap.erase(InnerL);
}
CurLoop = L;
Preheader = L->getLoopPreheader();
for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
I != E; ++I) {
BasicBlock *BB = *I;
if (LI->getLoopFor(BB) == L) CurAST->add(*BB); }
MayThrow = false;
for (Loop::block_iterator BB = L->block_begin(), BBE = L->block_end();
(BB != BBE) && !MayThrow ; ++BB)
for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end();
(I != E) && !MayThrow; ++I)
MayThrow |= I->mayThrow();
if (L->hasDedicatedExits())
SinkRegion(DT->getNode(L->getHeader()));
if (Preheader)
HoistRegion(DT->getNode(L->getHeader()));
if (!DisablePromotion && (Preheader || L->hasDedicatedExits())) {
SmallVector<BasicBlock *, 8> ExitBlocks;
SmallVector<Instruction *, 8> InsertPts;
PredIteratorCache PIC;
for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end();
I != E; ++I)
PromoteAliasSet(*I, ExitBlocks, InsertPts, PIC);
if (Changed)
formLCSSARecursively(*L, *DT, getAnalysisIfAvailable<ScalarEvolution>());
}
assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!");
assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) &&
"Parent loop not left in LCSSA form after LICM!");
CurLoop = nullptr;
Preheader = nullptr;
if (L->getParentLoop())
LoopToAliasSetMap[L] = CurAST;
else
delete CurAST;
return Changed;
}
void LICM::SinkRegion(DomTreeNode *N) {
assert(N != nullptr && "Null dominator tree node?");
BasicBlock *BB = N->getBlock();
if (!CurLoop->contains(BB)) return;
const std::vector<DomTreeNode*> &Children = N->getChildren();
for (unsigned i = 0, e = Children.size(); i != e; ++i)
SinkRegion(Children[i]);
if (inSubLoop(BB)) return;
for (BasicBlock::iterator II = BB->end(); II != BB->begin(); ) {
Instruction &I = *--II;
if (isInstructionTriviallyDead(&I, TLI)) {
DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n');
++II;
CurAST->deleteValue(&I);
I.eraseFromParent();
Changed = true;
continue;
}
if (isNotUsedInLoop(I) && canSinkOrHoistInst(I)) {
++II;
sink(I);
}
}
}
void LICM::HoistRegion(DomTreeNode *N) {
assert(N != nullptr && "Null dominator tree node?");
BasicBlock *BB = N->getBlock();
if (!CurLoop->contains(BB)) return;
if (!inSubLoop(BB))
for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) {
Instruction &I = *II++;
if (Constant *C = ConstantFoldInstruction(&I, DL, TLI)) {
DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *C << '\n');
CurAST->copyValue(&I, C);
CurAST->deleteValue(&I);
I.replaceAllUsesWith(C);
I.eraseFromParent();
continue;
}
if (CurLoop->hasLoopInvariantOperands(&I) && canSinkOrHoistInst(I) &&
isSafeToExecuteUnconditionally(I))
hoist(I);
}
const std::vector<DomTreeNode*> &Children = N->getChildren();
for (unsigned i = 0, e = Children.size(); i != e; ++i)
HoistRegion(Children[i]);
}
bool LICM::canSinkOrHoistInst(Instruction &I) {
if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
if (!LI->isUnordered())
return false;
if (AA->pointsToConstantMemory(LI->getOperand(0)))
return true;
if (LI->getMetadata("invariant.load"))
return true;
uint64_t Size = 0;
if (LI->getType()->isSized())
Size = AA->getTypeStoreSize(LI->getType());
AAMDNodes AAInfo;
LI->getAAMetadata(AAInfo);
return !pointerInvalidatedByLoop(LI->getOperand(0), Size, AAInfo);
} else if (CallInst *CI = dyn_cast<CallInst>(&I)) {
if (isa<DbgInfoIntrinsic>(I))
return false;
AliasAnalysis::ModRefBehavior Behavior = AA->getModRefBehavior(CI);
if (Behavior == AliasAnalysis::DoesNotAccessMemory)
return true;
if (AliasAnalysis::onlyReadsMemory(Behavior)) {
bool FoundMod = false;
for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end();
I != E; ++I) {
AliasSet &AS = *I;
if (!AS.isForwardingAliasSet() && AS.isMod()) {
FoundMod = true;
break;
}
}
if (!FoundMod) return true;
}
return false;
}
if (!isa<BinaryOperator>(I) && !isa<CastInst>(I) && !isa<SelectInst>(I) &&
!isa<GetElementPtrInst>(I) && !isa<CmpInst>(I) &&
!isa<InsertElementInst>(I) && !isa<ExtractElementInst>(I) &&
!isa<ShuffleVectorInst>(I) && !isa<ExtractValueInst>(I) &&
!isa<InsertValueInst>(I))
return false;
return isSafeToExecuteUnconditionally(I);
}
static bool isTriviallyReplacablePHI(PHINode &PN, Instruction &I) {
for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
if (PN.getIncomingValue(i) != &I)
return false;
return true;
}
bool LICM::isNotUsedInLoop(Instruction &I) {
for (User *U : I.users()) {
Instruction *UI = cast<Instruction>(U);
if (PHINode *PN = dyn_cast<PHINode>(UI)) {
if (isTriviallyReplacablePHI(*PN, I)) {
if (CurLoop->contains(PN))
return false;
else
continue;
}
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
if (PN->getIncomingValue(i) == &I)
if (CurLoop->contains(PN->getIncomingBlock(i)))
return false;
continue;
}
if (CurLoop->contains(UI))
return false;
}
return true;
}
Instruction *LICM::CloneInstructionInExitBlock(Instruction &I,
BasicBlock &ExitBlock,
PHINode &PN) {
Instruction *New = I.clone();
ExitBlock.getInstList().insert(ExitBlock.getFirstInsertionPt(), New);
if (!I.getName().empty()) New->setName(I.getName() + ".le");
for (User::op_iterator OI = New->op_begin(), OE = New->op_end(); OI != OE;
++OI)
if (Instruction *OInst = dyn_cast<Instruction>(*OI))
if (Loop *OLoop = LI->getLoopFor(OInst->getParent()))
if (!OLoop->contains(&PN)) {
PHINode *OpPN =
PHINode::Create(OInst->getType(), PN.getNumIncomingValues(),
OInst->getName() + ".lcssa", ExitBlock.begin());
for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
OpPN->addIncoming(OInst, PN.getIncomingBlock(i));
*OI = OpPN;
}
return New;
}
void LICM::sink(Instruction &I) {
DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
if (isa<LoadInst>(I)) ++NumMovedLoads;
else if (isa<CallInst>(I)) ++NumMovedCalls;
++NumSunk;
Changed = true;
#ifndef NDEBUG
SmallVector<BasicBlock *, 32> ExitBlocks;
CurLoop->getUniqueExitBlocks(ExitBlocks);
SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end());
#endif
SmallDenseMap<BasicBlock *, Instruction *, 32> SunkCopies;
while (!I.use_empty()) {
Instruction *User = I.user_back();
if (!DT->isReachableFromEntry(User->getParent())) {
User->replaceUsesOfWith(&I, UndefValue::get(I.getType()));
continue;
}
PHINode *PN = cast<PHINode>(User);
BasicBlock *ExitBlock = PN->getParent();
assert(ExitBlockSet.count(ExitBlock) &&
"The LCSSA PHI is not in an exit block!");
Instruction *New;
auto It = SunkCopies.find(ExitBlock);
if (It != SunkCopies.end())
New = It->second;
else
New = SunkCopies[ExitBlock] =
CloneInstructionInExitBlock(I, *ExitBlock, *PN);
PN->replaceAllUsesWith(New);
PN->eraseFromParent();
}
CurAST->deleteValue(&I);
I.eraseFromParent();
}
void LICM::hoist(Instruction &I) {
DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": "
<< I << "\n");
I.moveBefore(Preheader->getTerminator());
if (isa<LoadInst>(I)) ++NumMovedLoads;
else if (isa<CallInst>(I)) ++NumMovedCalls;
++NumHoisted;
Changed = true;
}
bool LICM::isSafeToExecuteUnconditionally(Instruction &Inst) {
if (isSafeToSpeculativelyExecute(&Inst, DL))
return true;
return isGuaranteedToExecute(Inst);
}
bool LICM::isGuaranteedToExecute(Instruction &Inst) {
if (MayThrow)
return false;
if (Inst.getParent() == CurLoop->getHeader())
return true;
SmallVector<BasicBlock*, 8> ExitBlocks;
CurLoop->getExitBlocks(ExitBlocks);
for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
if (!DT->dominates(Inst.getParent(), ExitBlocks[i]))
return false;
if (ExitBlocks.empty())
return false;
return true;
}
namespace {
class LoopPromoter : public LoadAndStorePromoter {
Value *SomePtr; SmallPtrSet<Value*, 4> &PointerMustAliases;
SmallVectorImpl<BasicBlock*> &LoopExitBlocks;
SmallVectorImpl<Instruction*> &LoopInsertPts;
PredIteratorCache &PredCache;
AliasSetTracker &AST;
LoopInfo &LI;
DebugLoc DL;
int Alignment;
AAMDNodes AATags;
Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
if (Instruction *I = dyn_cast<Instruction>(V))
if (Loop *L = LI.getLoopFor(I->getParent()))
if (!L->contains(BB)) {
PHINode *PN = PHINode::Create(
I->getType(), PredCache.GetNumPreds(BB),
I->getName() + ".lcssa", BB->begin());
for (BasicBlock **PI = PredCache.GetPreds(BB); *PI; ++PI)
PN->addIncoming(I, *PI);
return PN;
}
return V;
}
public:
LoopPromoter(Value *SP, const SmallVectorImpl<Instruction *> &Insts,
SSAUpdater &S, SmallPtrSet<Value *, 4> &PMA,
SmallVectorImpl<BasicBlock *> &LEB,
SmallVectorImpl<Instruction *> &LIP, PredIteratorCache &PIC,
AliasSetTracker &ast, LoopInfo &li, DebugLoc dl, int alignment,
const AAMDNodes &AATags)
: LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA),
LoopExitBlocks(LEB), LoopInsertPts(LIP), PredCache(PIC), AST(ast),
LI(li), DL(dl), Alignment(alignment), AATags(AATags) {}
bool isInstInList(Instruction *I,
const SmallVectorImpl<Instruction*> &) const override {
Value *Ptr;
if (LoadInst *LI = dyn_cast<LoadInst>(I))
Ptr = LI->getOperand(0);
else
Ptr = cast<StoreInst>(I)->getPointerOperand();
return PointerMustAliases.count(Ptr);
}
void doExtraRewritesBeforeFinalDeletion() const override {
for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
BasicBlock *ExitBlock = LoopExitBlocks[i];
Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock);
LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
Value *Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
Instruction *InsertPos = LoopInsertPts[i];
StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos);
NewSI->setAlignment(Alignment);
NewSI->setDebugLoc(DL);
if (AATags) NewSI->setAAMetadata(AATags);
}
}
void replaceLoadWithValue(LoadInst *LI, Value *V) const override {
AST.copyValue(LI, V);
}
void instructionDeleted(Instruction *I) const override {
AST.deleteValue(I);
}
};
}
void LICM::PromoteAliasSet(AliasSet &AS,
SmallVectorImpl<BasicBlock*> &ExitBlocks,
SmallVectorImpl<Instruction*> &InsertPts,
PredIteratorCache &PIC) {
if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() ||
AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->getValue()))
return;
assert(!AS.empty() &&
"Must alias set should have at least one pointer element in it!");
Value *SomePtr = AS.begin()->getValue();
bool GuaranteedToExecute = false;
SmallVector<Instruction*, 64> LoopUses;
SmallPtrSet<Value*, 4> PointerMustAliases;
unsigned Alignment = 1;
AAMDNodes AATags;
for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) {
Value *ASIV = ASI->getValue();
PointerMustAliases.insert(ASIV);
if (SomePtr->getType() != ASIV->getType())
return;
for (User *U : ASIV->users()) {
Instruction *UI = dyn_cast<Instruction>(U);
if (!UI || !CurLoop->contains(UI))
continue;
if (LoadInst *load = dyn_cast<LoadInst>(UI)) {
assert(!load->isVolatile() && "AST broken");
if (!load->isSimple())
return;
} else if (StoreInst *store = dyn_cast<StoreInst>(UI)) {
if (UI->getOperand(1) != ASIV)
continue;
assert(!store->isVolatile() && "AST broken");
if (!store->isSimple())
return;
unsigned InstAlignment = store->getAlignment();
if ((InstAlignment > Alignment || InstAlignment == 0) && Alignment != 0)
if (isGuaranteedToExecute(*UI)) {
GuaranteedToExecute = true;
Alignment = InstAlignment;
}
if (!GuaranteedToExecute)
GuaranteedToExecute = isGuaranteedToExecute(*UI);
} else
return;
if (LoopUses.empty()) {
UI->getAAMetadata(AATags);
} else if (AATags) {
UI->getAAMetadata(AATags, true);
}
LoopUses.push_back(UI);
}
}
if (!GuaranteedToExecute)
return;
DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " <<*SomePtr<<'\n');
Changed = true;
++NumPromoted;
DebugLoc DL = LoopUses[0]->getDebugLoc();
if (ExitBlocks.empty()) {
CurLoop->getUniqueExitBlocks(ExitBlocks);
InsertPts.resize(ExitBlocks.size());
for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
InsertPts[i] = ExitBlocks[i]->getFirstInsertionPt();
}
SmallVector<PHINode*, 16> NewPHIs;
SSAUpdater SSA(&NewPHIs);
LoopPromoter Promoter(SomePtr, LoopUses, SSA, PointerMustAliases, ExitBlocks,
InsertPts, PIC, *CurAST, *LI, DL, Alignment, AATags);
LoadInst *PreheaderLoad =
new LoadInst(SomePtr, SomePtr->getName()+".promoted",
Preheader->getTerminator());
PreheaderLoad->setAlignment(Alignment);
PreheaderLoad->setDebugLoc(DL);
if (AATags) PreheaderLoad->setAAMetadata(AATags);
SSA.AddAvailableValue(Preheader, PreheaderLoad);
Promoter.run(LoopUses);
if (PreheaderLoad->use_empty())
PreheaderLoad->eraseFromParent();
}
void LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) {
AliasSetTracker *AST = LoopToAliasSetMap.lookup(L);
if (!AST)
return;
AST->copyValue(From, To);
}
void LICM::deleteAnalysisValue(Value *V, Loop *L) {
AliasSetTracker *AST = LoopToAliasSetMap.lookup(L);
if (!AST)
return;
AST->deleteValue(V);
}