14 #ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
15 #define LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
23 #define DEBUG_TYPE "ssaupdater"
27 template<
typename T>
class SSAUpdaterTraits;
29 template<
typename UpdaterT>
35 using BlkT =
typename Traits::BlkT;
36 using ValT =
typename Traits::ValT;
37 using PhiT =
typename Traits::PhiT;
57 BBInfo *IDom =
nullptr;
60 unsigned NumPreds = 0;
63 BBInfo **Preds =
nullptr;
66 PhiT *PHITag =
nullptr;
68 BBInfo(BlkT *ThisBB, ValT V)
69 :
BB(ThisBB), AvailableVal(V), DefBB(V ?
this :
nullptr) {}
87 Updater(U), AvailableVals(A), InsertedPHIs(
Ins) {}
98 if (BlockList.size() == 0) {
99 ValT V = Traits::GetUndefVal(
BB, Updater);
100 (*AvailableVals)[
BB] = V;
108 return BBMap[
BB]->DefBB->AvailableVal;
121 WorkList.push_back(
Info);
127 while (!WorkList.empty()) {
130 Traits::FindPredecessorBlocks(
Info->BB, &Preds);
131 Info->NumPreds = Preds.size();
132 if (
Info->NumPreds == 0)
133 Info->Preds =
nullptr;
136 Info->NumPreds *
sizeof(BBInfo *),
alignof(BBInfo *)));
138 for (
unsigned p = 0;
p !=
Info->NumPreds; ++
p) {
139 BlkT *Pred = Preds[
p];
143 if (BBMapBucket.second) {
144 Info->Preds[
p] = BBMapBucket.second;
149 ValT PredVal = AvailableVals->
lookup(Pred);
150 BBInfo *PredInfo =
new (
Allocator) BBInfo(Pred, PredVal);
151 BBMapBucket.second = PredInfo;
152 Info->Preds[
p] = PredInfo;
154 if (PredInfo->AvailableVal) {
155 RootList.push_back(PredInfo);
158 WorkList.push_back(PredInfo);
165 BBInfo *PseudoEntry =
new (
Allocator) BBInfo(
nullptr, 0);
169 while (!RootList.empty()) {
171 Info->IDom = PseudoEntry;
173 WorkList.push_back(
Info);
176 while (!WorkList.empty()) {
177 Info = WorkList.back();
179 if (
Info->BlkNum == -2) {
181 Info->BlkNum = BlkNum++;
183 if (!
Info->AvailableVal)
184 BlockList->push_back(
Info);
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;
203 WorkList.push_back(SuccInfo);
206 PseudoEntry->BlkNum = BlkNum;
215 while (Blk1 != Blk2) {
216 while (Blk1->BlkNum < Blk2->BlkNum) {
221 while (Blk2->BlkNum < Blk1->BlkNum) {
245 for (
typename BlockListTy::reverse_iterator
I = BlockList->rbegin(),
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::GetUndefVal(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)
299 for (
typename BlockListTy::reverse_iterator
I = BlockList->rbegin(),
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;
335 for (
unsigned Idx = 1; Idx <
Info->NumPreds; ++Idx) {
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);
374 Info->AvailableVal = PHI;
375 (*AvailableVals)[
Info->BB] = PHI;
380 for (
typename BlockListTy::reverse_iterator
I = BlockList->rbegin(),
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);
409 if (InsertedPHIs) InsertedPHIs->push_back(PHI);
416 for (
auto &SomePHI :
BB->phis()) {
423 E = BlockList->end();
I !=
E; ++
I)
424 (*I)->PHITag =
nullptr;
432 WorkList.push_back(PHI);
435 BBMap[PHI->getParent()]->PHITag = PHI;
437 while (!WorkList.empty()) {
441 for (
typename Traits::PHI_iterator
I = Traits::PHI_begin(PHI),
442 E = Traits::PHI_end(PHI);
I !=
E; ++
I) {
443 ValT IncomingVal =
I.getIncomingValue();
444 BBInfo *PredInfo = BBMap[
I.getIncomingBlock()];
446 if (PredInfo->DefBB != PredInfo)
447 PredInfo = PredInfo->DefBB;
450 if (PredInfo->AvailableVal) {
451 if (IncomingVal == PredInfo->AvailableVal)
457 PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater);
458 if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB)
462 if (PredInfo->PHITag) {
463 if (IncomingPHIVal == PredInfo->PHITag)
467 PredInfo->PHITag = IncomingPHIVal;
469 WorkList.push_back(IncomingPHIVal);
479 E = BlockList->end();
I !=
E; ++
I)
480 if (PhiT *PHI = (*I)->PHITag) {
481 BlkT *
BB = PHI->getParent();
482 ValT PHIVal = Traits::GetPHIValue(PHI);
483 (*AvailableVals)[
BB] = PHIVal;
484 BBMap[
BB]->AvailableVal = PHIVal;
491 #undef DEBUG_TYPE // "ssaupdater"
493 #endif // LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H