#define DEBUG_TYPE "lcssa"
#include "llvm/Transforms/Scalar.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/Pass.h"
#include "llvm/Support/PredIteratorCache.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
using namespace llvm;
STATISTIC(NumLCSSA, "Number of live out of a loop variables");
namespace {
struct LCSSA : public LoopPass {
static char ID; LCSSA() : LoopPass(ID) {
initializeLCSSAPass(*PassRegistry::getPassRegistry());
}
DominatorTree *DT;
LoopInfo *LI;
ScalarEvolution *SE;
std::vector<BasicBlock*> LoopBlocks;
PredIteratorCache PredCache;
Loop *L;
virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
AU.addRequired<DominatorTree>();
AU.addRequired<LoopInfo>();
AU.addPreservedID(LoopSimplifyID);
AU.addPreserved<ScalarEvolution>();
}
private:
bool ProcessInstruction(Instruction *Inst,
const SmallVectorImpl<BasicBlock*> &ExitBlocks);
virtual void verifyAnalysis() const {
assert(L->isLCSSAForm(*DT) && "LCSSA form not preserved!");
}
bool inLoop(BasicBlock *B) const {
return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B);
}
};
}
char LCSSA::ID = 0;
INITIALIZE_PASS_BEGIN(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTree)
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;
static bool BlockDominatesAnExit(BasicBlock *BB,
const SmallVectorImpl<BasicBlock*> &ExitBlocks,
DominatorTree *DT) {
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 LCSSA::runOnLoop(Loop *TheLoop, LPPassManager &LPM) {
L = TheLoop;
DT = &getAnalysis<DominatorTree>();
LI = &getAnalysis<LoopInfo>();
SE = getAnalysisIfAvailable<ScalarEvolution>();
SmallVector<BasicBlock*, 8> ExitBlocks;
L->getExitBlocks(ExitBlocks);
if (ExitBlocks.empty())
return false;
LoopBlocks.clear();
LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());
array_pod_sort(LoopBlocks.begin(), LoopBlocks.end());
bool MadeChange = false;
for (Loop::block_iterator BBI = L->block_begin(), E = L->block_end();
BBI != E; ++BBI) {
BasicBlock *BB = *BBI;
if (!BlockDominatesAnExit(BB, ExitBlocks, DT))
continue;
for (BasicBlock::iterator I = BB->begin(), E = BB->end();
I != E; ++I) {
if (I->use_empty() ||
(I->hasOneUse() && I->use_back()->getParent() == BB &&
!isa<PHINode>(I->use_back())))
continue;
MadeChange |= ProcessInstruction(I, ExitBlocks);
}
}
if (SE && MadeChange)
SE->forgetLoop(L);
assert(L->isLCSSAForm(*DT));
PredCache.clear();
return MadeChange;
}
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;
}
bool LCSSA::ProcessInstruction(Instruction *Inst,
const SmallVectorImpl<BasicBlock*> &ExitBlocks) {
SmallVector<Use*, 16> UsesToRewrite;
BasicBlock *InstBB = Inst->getParent();
for (Value::use_iterator UI = Inst->use_begin(), E = Inst->use_end();
UI != E; ++UI) {
User *U = *UI;
BasicBlock *UserBB = cast<Instruction>(U)->getParent();
if (PHINode *PN = dyn_cast<PHINode>(U))
UserBB = PN->getIncomingBlock(UI);
if (InstBB != UserBB && !inLoop(UserBB))
UsesToRewrite.push_back(&UI.getUse());
}
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 (!inLoop(*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;
}