#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
#define LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
namespace llvm {
template<typename T> class SSAUpdaterTraits;
template<typename UpdaterT>
class SSAUpdaterImpl {
private:
UpdaterT *Updater;
typedef SSAUpdaterTraits<UpdaterT> Traits;
typedef typename Traits::BlkT BlkT;
typedef typename Traits::ValT ValT;
typedef typename Traits::PhiT PhiT;
class BBInfo {
public:
BlkT *BB; ValT AvailableVal; BBInfo *DefBB; int BlkNum; BBInfo *IDom; unsigned NumPreds; BBInfo **Preds; PhiT *PHITag;
BBInfo(BlkT *ThisBB, ValT V)
: BB(ThisBB), AvailableVal(V), DefBB(V ? this : 0), BlkNum(0), IDom(0),
NumPreds(0), Preds(0), PHITag(0) { }
};
typedef DenseMap<BlkT*, ValT> AvailableValsTy;
AvailableValsTy *AvailableVals;
SmallVectorImpl<PhiT*> *InsertedPHIs;
typedef SmallVectorImpl<BBInfo*> BlockListTy;
typedef DenseMap<BlkT*, BBInfo*> BBMapTy;
BBMapTy BBMap;
BumpPtrAllocator Allocator;
public:
explicit SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A,
SmallVectorImpl<PhiT*> *Ins) :
Updater(U), AvailableVals(A), InsertedPHIs(Ins) { }
ValT GetValue(BlkT *BB) {
SmallVector<BBInfo*, 100> BlockList;
BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList);
if (BlockList.size() == 0) {
ValT V = Traits::GetUndefVal(BB, Updater);
(*AvailableVals)[BB] = V;
return V;
}
FindDominators(&BlockList, PseudoEntry);
FindPHIPlacement(&BlockList);
FindAvailableVals(&BlockList);
return BBMap[BB]->DefBB->AvailableVal;
}
BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) {
SmallVector<BBInfo*, 10> RootList;
SmallVector<BBInfo*, 64> WorkList;
BBInfo *Info = new (Allocator) BBInfo(BB, 0);
BBMap[BB] = Info;
WorkList.push_back(Info);
SmallVector<BlkT*, 10> Preds;
while (!WorkList.empty()) {
Info = WorkList.pop_back_val();
Preds.clear();
Traits::FindPredecessorBlocks(Info->BB, &Preds);
Info->NumPreds = Preds.size();
if (Info->NumPreds == 0)
Info->Preds = 0;
else
Info->Preds = static_cast<BBInfo**>
(Allocator.Allocate(Info->NumPreds * sizeof(BBInfo*),
AlignOf<BBInfo*>::Alignment));
for (unsigned p = 0; p != Info->NumPreds; ++p) {
BlkT *Pred = Preds[p];
typename BBMapTy::value_type &BBMapBucket =
BBMap.FindAndConstruct(Pred);
if (BBMapBucket.second) {
Info->Preds[p] = BBMapBucket.second;
continue;
}
ValT PredVal = AvailableVals->lookup(Pred);
BBInfo *PredInfo = new (Allocator) BBInfo(Pred, PredVal);
BBMapBucket.second = PredInfo;
Info->Preds[p] = PredInfo;
if (PredInfo->AvailableVal) {
RootList.push_back(PredInfo);
continue;
}
WorkList.push_back(PredInfo);
}
}
BBInfo *PseudoEntry = new (Allocator) BBInfo(0, 0);
unsigned BlkNum = 1;
while (!RootList.empty()) {
Info = RootList.pop_back_val();
Info->IDom = PseudoEntry;
Info->BlkNum = -1;
WorkList.push_back(Info);
}
while (!WorkList.empty()) {
Info = WorkList.back();
if (Info->BlkNum == -2) {
Info->BlkNum = BlkNum++;
if (!Info->AvailableVal)
BlockList->push_back(Info);
WorkList.pop_back();
continue;
}
Info->BlkNum = -2;
for (typename Traits::BlkSucc_iterator SI =
Traits::BlkSucc_begin(Info->BB),
E = Traits::BlkSucc_end(Info->BB); SI != E; ++SI) {
BBInfo *SuccInfo = BBMap[*SI];
if (!SuccInfo || SuccInfo->BlkNum)
continue;
SuccInfo->BlkNum = -1;
WorkList.push_back(SuccInfo);
}
}
PseudoEntry->BlkNum = BlkNum;
return PseudoEntry;
}
BBInfo *IntersectDominators(BBInfo *Blk1, BBInfo *Blk2) {
while (Blk1 != Blk2) {
while (Blk1->BlkNum < Blk2->BlkNum) {
Blk1 = Blk1->IDom;
if (!Blk1)
return Blk2;
}
while (Blk2->BlkNum < Blk1->BlkNum) {
Blk2 = Blk2->IDom;
if (!Blk2)
return Blk1;
}
}
return Blk1;
}
void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry) {
bool Changed;
do {
Changed = false;
for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
E = BlockList->rend(); I != E; ++I) {
BBInfo *Info = *I;
BBInfo *NewIDom = 0;
for (unsigned p = 0; p != Info->NumPreds; ++p) {
BBInfo *Pred = Info->Preds[p];
if (Pred->BlkNum == 0) {
Pred->AvailableVal = Traits::GetUndefVal(Pred->BB, Updater);
(*AvailableVals)[Pred->BB] = Pred->AvailableVal;
Pred->DefBB = Pred;
Pred->BlkNum = PseudoEntry->BlkNum;
PseudoEntry->BlkNum++;
}
if (!NewIDom)
NewIDom = Pred;
else
NewIDom = IntersectDominators(NewIDom, Pred);
}
if (NewIDom && NewIDom != Info->IDom) {
Info->IDom = NewIDom;
Changed = true;
}
}
} while (Changed);
}
bool IsDefInDomFrontier(const BBInfo *Pred, const BBInfo *IDom) {
for (; Pred != IDom; Pred = Pred->IDom) {
if (Pred->DefBB == Pred)
return true;
}
return false;
}
void FindPHIPlacement(BlockListTy *BlockList) {
bool Changed;
do {
Changed = false;
for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
E = BlockList->rend(); I != E; ++I) {
BBInfo *Info = *I;
if (Info->DefBB == Info)
continue;
BBInfo *NewDefBB = Info->IDom->DefBB;
for (unsigned p = 0; p != Info->NumPreds; ++p) {
if (IsDefInDomFrontier(Info->Preds[p], Info->IDom)) {
NewDefBB = Info;
break;
}
}
if (NewDefBB != Info->DefBB) {
Info->DefBB = NewDefBB;
Changed = true;
}
}
} while (Changed);
}
void FindAvailableVals(BlockListTy *BlockList) {
for (typename BlockListTy::iterator I = BlockList->begin(),
E = BlockList->end(); I != E; ++I) {
BBInfo *Info = *I;
if (Info->DefBB != Info)
continue;
FindExistingPHI(Info->BB, BlockList);
if (Info->AvailableVal)
continue;
ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater);
Info->AvailableVal = PHI;
(*AvailableVals)[Info->BB] = PHI;
}
for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
E = BlockList->rend(); I != E; ++I) {
BBInfo *Info = *I;
if (Info->DefBB != Info) {
if (Info->NumPreds > 1)
(*AvailableVals)[Info->BB] = Info->DefBB->AvailableVal;
continue;
}
PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater);
if (!PHI)
continue;
for (unsigned p = 0; p != Info->NumPreds; ++p) {
BBInfo *PredInfo = Info->Preds[p];
BlkT *Pred = PredInfo->BB;
if (PredInfo->DefBB != PredInfo)
PredInfo = PredInfo->DefBB;
Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred);
}
DEBUG(dbgs() << " Inserted PHI: " << *PHI << "\n");
if (InsertedPHIs) InsertedPHIs->push_back(PHI);
}
}
void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) {
for (typename BlkT::iterator BBI = BB->begin(), BBE = BB->end();
BBI != BBE; ++BBI) {
PhiT *SomePHI = Traits::InstrIsPHI(BBI);
if (!SomePHI)
break;
if (CheckIfPHIMatches(SomePHI)) {
RecordMatchingPHI(SomePHI);
break;
}
for (typename BlockListTy::iterator I = BlockList->begin(),
E = BlockList->end(); I != E; ++I)
(*I)->PHITag = 0;
}
}
bool CheckIfPHIMatches(PhiT *PHI) {
SmallVector<PhiT*, 20> WorkList;
WorkList.push_back(PHI);
BBMap[PHI->getParent()]->PHITag = PHI;
while (!WorkList.empty()) {
PHI = WorkList.pop_back_val();
for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI),
E = Traits::PHI_end(PHI); I != E; ++I) {
ValT IncomingVal = I.getIncomingValue();
BBInfo *PredInfo = BBMap[I.getIncomingBlock()];
if (PredInfo->DefBB != PredInfo)
PredInfo = PredInfo->DefBB;
if (PredInfo->AvailableVal) {
if (IncomingVal == PredInfo->AvailableVal)
continue;
return false;
}
PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater);
if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB)
return false;
if (PredInfo->PHITag) {
if (IncomingPHIVal == PredInfo->PHITag)
continue;
return false;
}
PredInfo->PHITag = IncomingPHIVal;
WorkList.push_back(IncomingPHIVal);
}
}
return true;
}
void RecordMatchingPHI(PhiT *PHI) {
SmallVector<PhiT*, 20> WorkList;
WorkList.push_back(PHI);
BlkT *BB = PHI->getParent();
ValT PHIVal = Traits::GetPHIValue(PHI);
(*AvailableVals)[BB] = PHIVal;
BBMap[BB]->AvailableVal = PHIVal;
while (!WorkList.empty()) {
PHI = WorkList.pop_back_val();
for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI),
E = Traits::PHI_end(PHI); I != E; ++I) {
ValT IncomingVal = I.getIncomingValue();
PhiT *IncomingPHI = Traits::ValueIsPHI(IncomingVal, Updater);
if (!IncomingPHI) continue;
BB = IncomingPHI->getParent();
BBInfo *Info = BBMap[BB];
if (!Info || Info->AvailableVal)
continue;
(*AvailableVals)[BB] = IncomingVal;
Info->AvailableVal = IncomingVal;
WorkList.push_back(IncomingPHI);
}
}
}
};
}
#endif