#define DEBUG_TYPE "lcssa"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Constants.h"
#include "llvm/Pass.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/PredIteratorCache.h"
#include <algorithm>
#include <map>
using namespace llvm;
STATISTIC(NumLCSSA, "Number of live out of a loop variables");
namespace {
struct VISIBILITY_HIDDEN LCSSA : public LoopPass {
static char ID; LCSSA() : LoopPass(&ID) {}
LoopInfo *LI;
DominatorTree *DT;
std::vector<BasicBlock*> LoopBlocks;
PredIteratorCache PredCache;
virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
void ProcessInstruction(Instruction* Instr,
const SmallVector<BasicBlock*, 8>& exitBlocks);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
AU.addRequiredID(LoopSimplifyID);
AU.addPreservedID(LoopSimplifyID);
AU.addRequired<LoopInfo>();
AU.addPreserved<LoopInfo>();
AU.addRequired<DominatorTree>();
AU.addPreserved<ScalarEvolution>();
AU.addPreserved<DominatorTree>();
AU.addRequired<DominanceFrontier>();
AU.addPreserved<DominanceFrontier>();
}
private:
void getLoopValuesUsedOutsideLoop(Loop *L,
SetVector<Instruction*> &AffectedValues,
const SmallVector<BasicBlock*, 8>& exitBlocks);
Value *GetValueForBlock(DomTreeNode *BB, Instruction *OrigInst,
DenseMap<DomTreeNode*, Value*> &Phis);
bool inLoop(BasicBlock* B) {
return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B);
}
};
}
char LCSSA::ID = 0;
static RegisterPass<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass");
Pass *llvm::createLCSSAPass() { return new LCSSA(); }
const PassInfo *const llvm::LCSSAID = &X;
bool LCSSA::runOnLoop(Loop *L, LPPassManager &LPM) {
PredCache.clear();
LI = &LPM.getAnalysis<LoopInfo>();
DT = &getAnalysis<DominatorTree>();
LoopBlocks.clear();
LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());
std::sort(LoopBlocks.begin(), LoopBlocks.end());
SmallVector<BasicBlock*, 8> exitBlocks;
L->getExitBlocks(exitBlocks);
SetVector<Instruction*> AffectedValues;
getLoopValuesUsedOutsideLoop(L, AffectedValues, exitBlocks);
if (AffectedValues.empty())
return false;
for (SetVector<Instruction*>::iterator I = AffectedValues.begin(),
E = AffectedValues.end(); I != E; ++I)
ProcessInstruction(*I, exitBlocks);
assert(L->isLCSSAForm());
return true;
}
void LCSSA::ProcessInstruction(Instruction *Instr,
const SmallVector<BasicBlock*, 8>& exitBlocks) {
++NumLCSSA;
DenseMap<DomTreeNode*, Value*> Phis;
DomTreeNode *InstrNode = DT->getNode(Instr->getParent());
for (SmallVector<BasicBlock*, 8>::const_iterator BBI = exitBlocks.begin(),
BBE = exitBlocks.end(); BBI != BBE; ++BBI) {
BasicBlock *BB = *BBI;
DomTreeNode *ExitBBNode = DT->getNode(BB);
Value *&Phi = Phis[ExitBBNode];
if (!Phi && DT->dominates(InstrNode, ExitBBNode)) {
PHINode *PN = PHINode::Create(Instr->getType(), Instr->getName()+".lcssa",
BB->begin());
PN->reserveOperandSpace(PredCache.GetNumPreds(BB));
Phi = PN;
for (BasicBlock** PI = PredCache.GetPreds(BB); *PI; ++PI)
PN->addIncoming(Instr, *PI);
}
}
for (Value::use_iterator UI = Instr->use_begin(), E = Instr->use_end();
UI != E;) {
BasicBlock *UserBB = cast<Instruction>(*UI)->getParent();
if (PHINode *P = dyn_cast<PHINode>(*UI)) {
UserBB = P->getIncomingBlock(UI);
}
if (UserBB == Instr->getParent() || inLoop(UserBB)) {
++UI;
continue;
}
Value *Val = GetValueForBlock(DT->getNode(UserBB), Instr, Phis);
Use &U = UI.getUse();
++UI;
U.set(Val);
}
}
void LCSSA::getLoopValuesUsedOutsideLoop(Loop *L,
SetVector<Instruction*> &AffectedValues,
const SmallVector<BasicBlock*, 8>& exitBlocks) {
for (Loop::block_iterator BB = L->block_begin(), BE = L->block_end();
BB != BE; ++BB) {
for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I)
for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); UI != UE;
++UI) {
BasicBlock *UserBB = cast<Instruction>(*UI)->getParent();
if (PHINode* p = dyn_cast<PHINode>(*UI)) {
UserBB = p->getIncomingBlock(UI);
}
if (*BB != UserBB && !inLoop(UserBB)) {
AffectedValues.insert(I);
break;
}
}
}
}
Value *LCSSA::GetValueForBlock(DomTreeNode *BB, Instruction *OrigInst,
DenseMap<DomTreeNode*, Value*> &Phis) {
if (BB == 0)
return UndefValue::get(OrigInst->getType());
if (Phis.count(BB)) return Phis[BB];
DomTreeNode *IDom = BB->getIDom();
if (!inLoop(IDom->getBlock())) {
Value* val = GetValueForBlock(IDom, OrigInst, Phis);
Phis.insert(std::make_pair(BB, val));
return val;
}
BasicBlock *BBN = BB->getBlock();
PHINode *PN = PHINode::Create(OrigInst->getType(),
OrigInst->getName() + ".lcssa", BBN->begin());
PN->reserveOperandSpace(PredCache.GetNumPreds(BBN));
Phis.insert(std::make_pair(BB, PN));
for (BasicBlock** PI = PredCache.GetPreds(BBN); *PI; ++PI)
PN->addIncoming(GetValueForBlock(DT->getNode(*PI), OrigInst, Phis), *PI);
return PN;
}