#include "llvm/Transforms/Scalar.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/PredIteratorCache.h"
#include "llvm/Pass.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
using namespace llvm;
#define DEBUG_TYPE "lcssa"
STATISTIC(NumLCSSA, "Number of live out of a loop variables");
static bool isExitBlock(BasicBlock *BB,
const SmallVectorImpl<BasicBlock *> &ExitBlocks) {
for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
if (ExitBlocks[i] == BB)
return true;
return false;
}
static bool processInstruction(Loop &L, Instruction &Inst, DominatorTree &DT,
const SmallVectorImpl<BasicBlock *> &ExitBlocks,
PredIteratorCache &PredCache) {
SmallVector<Use *, 16> UsesToRewrite;
BasicBlock *InstBB = Inst.getParent();
for (Use &U : Inst.uses()) {
Instruction *User = cast<Instruction>(U.getUser());
BasicBlock *UserBB = User->getParent();
if (PHINode *PN = dyn_cast<PHINode>(User))
UserBB = PN->getIncomingBlock(U);
if (InstBB != UserBB && !L.contains(UserBB))
UsesToRewrite.push_back(&U);
}
if (UsesToRewrite.empty())
return false;
++NumLCSSA;
BasicBlock *DomBB = Inst.getParent();
if (InvokeInst *Inv = dyn_cast<InvokeInst>(&Inst))
DomBB = Inv->getNormalDest();
DomTreeNode *DomNode = DT.getNode(DomBB);
SmallVector<PHINode *, 16> AddedPHIs;
SSAUpdater SSAUpdate;
SSAUpdate.Initialize(Inst.getType(), Inst.getName());
for (SmallVectorImpl<BasicBlock *>::const_iterator BBI = ExitBlocks.begin(),
BBE = ExitBlocks.end();
BBI != BBE; ++BBI) {
BasicBlock *ExitBB = *BBI;
if (!DT.dominates(DomNode, DT.getNode(ExitBB)))
continue;
if (SSAUpdate.HasValueForBlock(ExitBB))
continue;
PHINode *PN = PHINode::Create(Inst.getType(), PredCache.GetNumPreds(ExitBB),
Inst.getName() + ".lcssa", ExitBB->begin());
for (BasicBlock **PI = PredCache.GetPreds(ExitBB); *PI; ++PI) {
PN->addIncoming(&Inst, *PI);
if (!L.contains(*PI))
UsesToRewrite.push_back(
&PN->getOperandUse(PN->getOperandNumForIncomingValue(
PN->getNumIncomingValues() - 1)));
}
AddedPHIs.push_back(PN);
SSAUpdate.AddAvailableValue(ExitBB, PN);
}
for (unsigned i = 0, e = UsesToRewrite.size(); i != e; ++i) {
Instruction *User = cast<Instruction>(UsesToRewrite[i]->getUser());
BasicBlock *UserBB = User->getParent();
if (PHINode *PN = dyn_cast<PHINode>(User))
UserBB = PN->getIncomingBlock(*UsesToRewrite[i]);
if (isa<PHINode>(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) {
if (UsesToRewrite[i]->get()->hasValueHandle())
ValueHandleBase::ValueIsRAUWd(*UsesToRewrite[i], UserBB->begin());
UsesToRewrite[i]->set(UserBB->begin());
continue;
}
SSAUpdate.RewriteUse(*UsesToRewrite[i]);
}
for (unsigned i = 0, e = AddedPHIs.size(); i != e; ++i) {
if (AddedPHIs[i]->use_empty())
AddedPHIs[i]->eraseFromParent();
}
return true;
}
static bool
blockDominatesAnExit(BasicBlock *BB,
DominatorTree &DT,
const SmallVectorImpl<BasicBlock *> &ExitBlocks) {
DomTreeNode *DomNode = DT.getNode(BB);
for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
if (DT.dominates(DomNode, DT.getNode(ExitBlocks[i])))
return true;
return false;
}
bool llvm::formLCSSA(Loop &L, DominatorTree &DT, ScalarEvolution *SE) {
bool Changed = false;
SmallVector<BasicBlock *, 8> ExitBlocks;
L.getExitBlocks(ExitBlocks);
if (ExitBlocks.empty())
return false;
PredIteratorCache PredCache;
for (Loop::block_iterator BBI = L.block_begin(), BBE = L.block_end();
BBI != BBE; ++BBI) {
BasicBlock *BB = *BBI;
if (!blockDominatesAnExit(BB, DT, ExitBlocks))
continue;
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
if (I->use_empty() ||
(I->hasOneUse() && I->user_back()->getParent() == BB &&
!isa<PHINode>(I->user_back())))
continue;
Changed |= processInstruction(L, *I, DT, ExitBlocks, PredCache);
}
}
if (SE && Changed)
SE->forgetLoop(&L);
assert(L.isLCSSAForm(DT));
return Changed;
}
bool llvm::formLCSSARecursively(Loop &L, DominatorTree &DT,
ScalarEvolution *SE) {
bool Changed = false;
for (Loop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI)
Changed |= formLCSSARecursively(**LI, DT, SE);
Changed |= formLCSSA(L, DT, SE);
return Changed;
}
namespace {
struct LCSSA : public FunctionPass {
static char ID; LCSSA() : FunctionPass(ID) {
initializeLCSSAPass(*PassRegistry::getPassRegistry());
}
DominatorTree *DT;
LoopInfo *LI;
ScalarEvolution *SE;
bool runOnFunction(Function &F) override;
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
AU.addRequired<DominatorTreeWrapperPass>();
AU.addRequired<LoopInfo>();
AU.addPreservedID(LoopSimplifyID);
AU.addPreserved<AliasAnalysis>();
AU.addPreserved<ScalarEvolution>();
}
private:
void verifyAnalysis() const override;
};
}
char LCSSA::ID = 0;
INITIALIZE_PASS_BEGIN(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopInfo)
INITIALIZE_PASS_END(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false)
Pass *llvm::createLCSSAPass() { return new LCSSA(); }
char &llvm::LCSSAID = LCSSA::ID;
bool LCSSA::runOnFunction(Function &F) {
bool Changed = false;
LI = &getAnalysis<LoopInfo>();
DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
SE = getAnalysisIfAvailable<ScalarEvolution>();
for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
Changed |= formLCSSARecursively(**I, *DT, SE);
return Changed;
}
static void verifyLoop(Loop &L, DominatorTree &DT) {
for (Loop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI)
verifyLoop(**LI, DT);
}
void LCSSA::verifyAnalysis() const {
for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
verifyLoop(**I, *DT);
}