14#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
15#define LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
24#define DEBUG_TYPE "ssaupdater"
28template<
typename T>
class SSAUpdaterTraits;
30template<
typename UpdaterT>
36 using BlkT =
typename Traits::BlkT;
37 using ValT =
typename Traits::ValT;
38 using PhiT =
typename Traits::PhiT;
58 BBInfo *IDom =
nullptr;
61 unsigned NumPreds = 0;
64 BBInfo **Preds =
nullptr;
67 PhiT *PHITag =
nullptr;
69 BBInfo(BlkT *ThisBB, ValT V)
70 : BB(ThisBB), AvailableVal(V), DefBB(V ?
this :
nullptr) {}
88 Updater(U), AvailableVals(
A), InsertedPHIs(Ins) {}
99 if (BlockList.
size() == 0) {
100 ValT V = Traits::GetPoisonVal(BB, Updater);
101 (*AvailableVals)[BB] = V;
109 return BBMap[BB]->DefBB->AvailableVal;
128 while (!WorkList.
empty()) {
131 Traits::FindPredecessorBlocks(
Info->BB, &Preds);
133 if (
Info->NumPreds == 0)
134 Info->Preds =
nullptr;
137 Info->NumPreds *
sizeof(BBInfo *),
alignof(BBInfo *)));
139 for (
unsigned p = 0; p !=
Info->NumPreds; ++p) {
140 BlkT *Pred = Preds[p];
142 BBInfo *&BBMapBucket = BBMap[Pred];
144 Info->Preds[p] = BBMapBucket;
149 ValT PredVal = AvailableVals->
lookup(Pred);
150 BBInfo *PredInfo =
new (
Allocator) BBInfo(Pred, PredVal);
151 BBMapBucket = PredInfo;
152 Info->Preds[p] = PredInfo;
154 if (PredInfo->AvailableVal) {
165 BBInfo *PseudoEntry =
new (
Allocator) BBInfo(
nullptr, 0);
169 while (!RootList.
empty()) {
171 Info->IDom = PseudoEntry;
176 while (!WorkList.
empty()) {
179 if (
Info->BlkNum == -2) {
181 Info->BlkNum = BlkNum++;
183 if (!
Info->AvailableVal)
196 for (
typename Traits::BlkSucc_iterator SI =
197 Traits::BlkSucc_begin(
Info->BB),
198 E = Traits::BlkSucc_end(
Info->BB); SI !=
E; ++SI) {
199 BBInfo *SuccInfo = BBMap[*SI];
200 if (!SuccInfo || SuccInfo->BlkNum)
202 SuccInfo->BlkNum = -1;
206 PseudoEntry->BlkNum = BlkNum;
215 while (Blk1 != Blk2) {
216 while (Blk1->BlkNum < Blk2->BlkNum) {
221 while (Blk2->BlkNum < Blk1->BlkNum) {
246 E = BlockList->
rend();
I !=
E; ++
I) {
248 BBInfo *NewIDom =
nullptr;
251 for (
unsigned p = 0; p !=
Info->NumPreds; ++p) {
252 BBInfo *Pred =
Info->Preds[p];
255 if (Pred->BlkNum == 0) {
256 Pred->AvailableVal = Traits::GetPoisonVal(Pred->BB, Updater);
257 (*AvailableVals)[Pred->BB] = Pred->AvailableVal;
259 Pred->BlkNum = PseudoEntry->BlkNum;
260 PseudoEntry->BlkNum++;
270 if (NewIDom && NewIDom !=
Info->IDom) {
271 Info->IDom = NewIDom;
283 for (; Pred != IDom; Pred = Pred->IDom) {
284 if (Pred->DefBB == Pred)
300 E = BlockList->
rend();
I !=
E; ++
I) {
308 BBInfo *NewDefBB =
Info->IDom->DefBB;
309 for (
unsigned p = 0; p !=
Info->NumPreds; ++p) {
318 if (NewDefBB !=
Info->DefBB) {
319 Info->DefBB = NewDefBB;
332 ValT Singular =
Info->Preds[0]->DefBB->AvailableVal;
336 ValT PredVal =
Info->Preds[
Idx]->DefBB->AvailableVal;
337 if (!PredVal || Singular != PredVal)
341 (*AvailableVals)[
Info->BB] = Singular;
343 Info->AvailableVal = Singular;
344 Info->DefBB =
Info->Preds[0]->DefBB;
358 E = BlockList->
end();
I !=
E; ++
I) {
370 if (
Info->AvailableVal)
373 ValT
PHI = Traits::CreateEmptyPHI(
Info->BB,
Info->NumPreds, Updater);
375 (*AvailableVals)[
Info->BB] =
PHI;
381 E = BlockList->
rend();
I !=
E; ++
I) {
387 (*AvailableVals)[
Info->BB] =
Info->DefBB->AvailableVal;
392 PhiT *
PHI = Traits::ValueIsNewPHI(
Info->AvailableVal, Updater);
397 for (
unsigned p = 0; p !=
Info->NumPreds; ++p) {
398 BBInfo *PredInfo =
Info->Preds[p];
399 BlkT *Pred = PredInfo->BB;
401 if (PredInfo->DefBB != PredInfo)
402 PredInfo = PredInfo->DefBB;
403 Traits::AddPHIOperand(
PHI, PredInfo->AvailableVal, Pred);
417 for (
auto &SomePHI : BB->phis()) {
431 for (BBInfo *TaggedBlock : TaggedBlocks)
432 TaggedBlock->PHITag =
nullptr;
433 TaggedBlocks.clear();
440 BBInfo *PHIBlock = BBMap[
PHI->getParent()];
441 PHIBlock->PHITag =
PHI;
444 while (!WorkList.empty()) {
445 PHI = WorkList.pop_back_val();
448 for (
typename Traits::PHI_iterator
I = Traits::PHI_begin(
PHI),
449 E = Traits::PHI_end(
PHI);
I !=
E; ++
I) {
450 ValT IncomingVal =
I.getIncomingValue();
451 BBInfo *PredInfo = BBMap[
I.getIncomingBlock()];
453 if (PredInfo->DefBB != PredInfo)
454 PredInfo = PredInfo->DefBB;
457 if (PredInfo->AvailableVal) {
458 if (IncomingVal == PredInfo->AvailableVal)
464 PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater);
465 if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB)
469 if (PredInfo->PHITag) {
470 if (IncomingPHIVal == PredInfo->PHITag)
474 PredInfo->PHITag = IncomingPHIVal;
477 WorkList.push_back(IncomingPHIVal);
488 for (BBInfo *
Block : TaggedBlocks) {
491 BlkT *BB =
PHI->getParent();
492 ValT PHIVal = Traits::GetPHIValue(
PHI);
493 (*AvailableVals)[BB] = PHIVal;
494 BBMap[BB]->AvailableVal = PHIVal;
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Analysis containing CSE Info
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
static const HTTPClientCleanup Cleanup
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
This file defines the SmallVector class.
Allocate memory in an ever growing pool, as if by bump-pointer.
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry)
FindDominators - Calculate the dominator tree for the subset of the CFG corresponding to the basic bl...
void FindAvailableVals(BlockListTy *BlockList)
FindAvailableVal - If this block requires a PHI, first check if an existing PHI matches the PHI place...
bool IsDefInDomFrontier(const BBInfo *Pred, const BBInfo *IDom)
IsDefInDomFrontier - Search up the dominator tree from Pred to IDom for any blocks containing definit...
ValT GetValue(BlkT *BB)
GetValue - Check to see if AvailableVals has an entry for the specified BB and if so,...
SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A, SmallVectorImpl< PhiT * > *Ins)
BBInfo * BuildBlockList(BlkT *BB, BlockListTy *BlockList)
BuildBlockList - Starting from the specified basic block, traverse back through its predecessors unti...
bool FindSingularVal(BBInfo *Info)
Check all predecessors and if all of them have the same AvailableVal use it as value for block repres...
void FindPHIPlacement(BlockListTy *BlockList)
FindPHIPlacement - PHIs are needed in the iterated dominance frontiers of the known definitions.
void FindExistingPHI(BlkT *BB)
FindExistingPHI - Look through the PHI nodes in a block to see if any of them match what is needed.
BBInfo * IntersectDominators(BBInfo *Blk1, BBInfo *Blk2)
IntersectDominators - This is the dataflow lattice "meet" operation for finding dominators.
void RecordMatchingPHIs(BlockListTy &TaggedBlocks)
RecordMatchingPHIs - For each PHI node that matches, record it in both the BBMap and the AvailableVal...
bool CheckIfPHIMatches(PhiT *PHI, BlockListTy &TaggedBlocks)
CheckIfPHIMatches - Check if a PHI node matches the placement and values in the BBMap.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
typename SuperClass::iterator iterator
void push_back(const T &Elt)
reverse_iterator rbegin()
std::reverse_iterator< iterator > reverse_iterator
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
This is an optimization pass for GlobalISel generic memory operations.
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.