53 #define DEBUG_TYPE "structurizecfg"
61 "structurizecfg-skip-uniform-regions",
63 cl::desc(
"Force whether the StructurizeCFG pass skips uniform regions"),
67 RelaxedUniformRegions(
"structurizecfg-relaxed-uniform-regions",
cl::Hidden,
68 cl::desc(
"Allow relaxed uniform region checks"),
73 using BBValuePair = std::pair<BasicBlock *, Value *>;
93 struct SubGraphTraits {
94 using NodeRef = std::pair<RegionNode *, SmallDenseSet<RegionNode *> *>;
99 class WrappedSuccIterator
101 WrappedSuccIterator, BaseSuccIterator,
102 typename std::iterator_traits<BaseSuccIterator>::iterator_category,
103 NodeRef, std::ptrdiff_t, NodeRef *, NodeRef> {
113 static bool filterAll(
const NodeRef &
N) {
return true; }
114 static bool filterSet(
const NodeRef &
N) {
return N.second->count(
N.first); }
116 using ChildIteratorType =
126 auto *filter =
N.second ? &filterSet : &filterAll;
128 make_range<WrappedSuccIterator>(
134 static ChildIteratorType child_begin(
const NodeRef &
N) {
138 static ChildIteratorType child_end(
const NodeRef &
N) {
148 class NearestCommonDominator {
151 bool ResultIsRemembered =
false;
157 ResultIsRemembered = Remember;
162 if (NewResult != Result)
163 ResultIsRemembered =
false;
165 ResultIsRemembered |= Remember;
170 explicit NearestCommonDominator(
DominatorTree *DomTree) : DT(DomTree) {}
186 bool resultIsRememberedBlock() {
return ResultIsRemembered; }
235 class StructurizeCFG {
251 BBPhiMap DeletedPhis;
252 BB2BBVecMap AddedPhis;
255 BranchVector Conditions;
259 BranchVector LoopConds;
273 void insertConditions(
bool Loops);
275 void simplifyConditions();
283 void simplifyAffectedPhis();
288 bool IncludeDominator);
302 void wireFlow(
bool ExitUseAllowed,
BasicBlock *LoopEnd);
304 void handleLoops(
bool ExitUseAllowed,
BasicBlock *LoopEnd);
316 class StructurizeCFGLegacyPass :
public RegionPass {
317 bool SkipUniformRegions;
322 explicit StructurizeCFGLegacyPass(
bool SkipUniformRegions_ =
false)
323 :
RegionPass(
ID), SkipUniformRegions(SkipUniformRegions_) {
325 SkipUniformRegions = ForceSkipUniformRegions.
getValue();
332 if (SkipUniformRegions) {
334 if (SCFG.makeUniformRegion(R,
DA))
337 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
338 return SCFG.run(R, DT);
341 StringRef getPassName()
const override {
return "Structurize control flow"; }
344 if (SkipUniformRegions)
359 "Structurize the CFG",
false,
false)
370 void StructurizeCFG::orderNodes() {
377 auto EntryNode = SubGraphTraits::getEntryNode(ParentRegion);
381 unsigned I = 0,
E = Order.size();
393 unsigned Size =
SCC.size();
398 for (
auto &
N :
SCC) {
399 assert(
I <
E &&
"SCC size mismatch!");
400 Order[
I++] =
N.first;
403 assert(
I ==
E &&
"SCC size mismatch!");
406 if (WorkList.empty())
415 Nodes.
insert(Order.begin() +
I, Order.begin() +
E - 1);
418 EntryNode.first = Order[
E - 1];
419 EntryNode.second = &Nodes;
425 if (
N->isSubRegion()) {
428 if (Visited.count(Exit))
429 Loops[Exit] =
N->getEntry();
437 if (Visited.count(Succ))
445 Value *
Cond = Invert ? BoolFalse : BoolTrue;
446 if (
Term->isConditional()) {
449 if (Idx != (
unsigned)Invert)
456 void StructurizeCFG::gatherPredicates(
RegionNode *
N) {
457 RegionInfo *RI = ParentRegion->getRegionInfo();
464 if (!ParentRegion->contains(
P))
468 if (R == ParentRegion) {
471 for (
unsigned i = 0,
e =
Term->getNumSuccessors();
i !=
e; ++
i) {
476 if (Visited.count(
P)) {
478 if (
Term->isConditional()) {
481 if (Visited.count(Other) && !
Loops.count(Other) &&
484 Pred[
Other] = BoolFalse;
489 Pred[
P] = buildCondition(
Term,
i,
false);
492 LPred[
P] = buildCondition(
Term,
i,
true);
497 while (
R->getParent() != ParentRegion)
505 if (Visited.count(Entry))
506 Pred[Entry] = BoolTrue;
508 LPred[Entry] = BoolFalse;
514 void StructurizeCFG::collectInfos() {
527 << (
RN->isSubRegion() ?
"SubRegion with entry: " :
"")
528 <<
RN->getEntry()->getName() <<
"\n");
531 gatherPredicates(
RN);
534 Visited.insert(
RN->getEntry());
542 void StructurizeCFG::insertConditions(
bool Loops) {
543 BranchVector &Conds =
Loops ? LoopConds : Conditions;
560 NearestCommonDominator Dominator(DT);
561 Dominator.addBlock(Parent);
563 Value *ParentValue =
nullptr;
564 for (std::pair<BasicBlock *, Value *> BBAndPred : Preds) {
566 Value *Pred = BBAndPred.second;
573 Dominator.addAndRememberBlock(
BB);
577 Term->setCondition(ParentValue);
579 if (!Dominator.resultIsRememberedBlock())
588 void StructurizeCFG::simplifyConditions() {
590 for (
auto &
I : concat<PredMap::value_type>(Predicates, LoopPreds)) {
591 auto &Preds =
I.second;
592 for (
auto &J : Preds) {
593 auto &
Cond = J.second;
596 !
Cond->use_empty()) {
597 if (
auto *InvertedCmp = dyn_cast<CmpInst>(Inverted)) {
598 InvertedCmp->setPredicate(InvertedCmp->getInversePredicate());
599 Cond->replaceAllUsesWith(InvertedCmp);
600 InstToErase.push_back(cast<Instruction>(
Cond));
605 for (
auto *
I : InstToErase)
606 I->eraseFromParent();
612 PhiMap &
Map = DeletedPhis[To];
614 bool Recorded =
false;
615 while (Phi.getBasicBlockIndex(
From) != -1) {
617 Map[&Phi].push_back(std::make_pair(
From, Deleted));
619 AffectedPhis.push_back(&Phi);
632 AddedPhis[To].push_back(
From);
636 void StructurizeCFG::setPhiValues() {
639 for (
const auto &AddedPhi : AddedPhis) {
641 const BBVector &
From = AddedPhi.second;
643 if (!DeletedPhis.count(To))
646 PhiMap &
Map = DeletedPhis[To];
647 for (
const auto &PI : Map) {
650 Updater.Initialize(Phi->
getType(),
"");
651 Updater.AddAvailableValue(&
Func->getEntryBlock(),
Undef);
652 Updater.AddAvailableValue(To,
Undef);
654 NearestCommonDominator Dominator(DT);
655 Dominator.addBlock(To);
656 for (
const auto &
VI : PI.second) {
657 Updater.AddAvailableValue(
VI.first,
VI.second);
658 Dominator.addAndRememberBlock(
VI.first);
661 if (!Dominator.resultIsRememberedBlock())
662 Updater.AddAvailableValue(Dominator.result(),
Undef);
666 AffectedPhis.push_back(Phi);
669 DeletedPhis.erase(To);
671 assert(DeletedPhis.empty());
673 AffectedPhis.append(InsertedPhis.begin(), InsertedPhis.end());
676 void StructurizeCFG::simplifyAffectedPhis() {
682 for (
WeakVH VH : AffectedPhis) {
683 if (
auto Phi = dyn_cast_or_null<PHINode>(VH)) {
701 delPhiValues(
BB, Succ);
705 Term->eraseFromParent();
710 bool IncludeDominator) {
711 if (Node->isSubRegion()) {
723 delPhiValues(
BB, OldExit);
724 BB->getTerminator()->replaceUsesOfWith(OldExit, NewExit);
725 addPhiValues(
BB, NewExit);
728 if (IncludeDominator) {
732 Dominator = DT->findNearestCommonDominator(Dominator,
BB);
738 DT->changeImmediateDominator(NewExit, Dominator);
746 addPhiValues(
BB, NewExit);
747 if (IncludeDominator)
748 DT->changeImmediateDominator(NewExit,
BB);
756 Order.back()->getEntry();
759 DT->addNewBlock(
Flow, Dominator);
760 ParentRegion->getRegionInfo()->setRegionFor(
Flow, ParentRegion);
765 BasicBlock *StructurizeCFG::needPrefix(
bool NeedEmpty) {
768 if (!PrevNode->isSubRegion()) {
769 killTerminator(Entry);
770 if (!NeedEmpty || Entry->getFirstInsertionPt() == Entry->end())
778 changeExit(PrevNode,
Flow,
true);
779 PrevNode = ParentRegion->getBBNode(
Flow);
785 bool ExitUseAllowed) {
786 if (!Order.empty() || !ExitUseAllowed)
787 return getNextFlow(
Flow);
790 DT->changeImmediateDominator(Exit,
Flow);
791 addPhiValues(
Flow, Exit);
797 PrevNode = ParentRegion->contains(
BB) ? ParentRegion->getBBNode(
BB)
804 return llvm::all_of(Preds, [&](std::pair<BasicBlock *, Value *> Pred) {
805 return DT->dominates(
BB, Pred.first);
810 bool StructurizeCFG::isPredictableTrue(
RegionNode *Node) {
812 bool Dominated =
false;
818 for (std::pair<BasicBlock*, Value*> Pred : Preds) {
820 Value *V = Pred.second;
825 if (!Dominated && DT->dominates(
BB, PrevNode->getEntry()))
834 void StructurizeCFG::wireFlow(
bool ExitUseAllowed,
837 Visited.insert(Node->getEntry());
839 if (isPredictableTrue(Node)) {
842 changeExit(PrevNode, Node->getEntry(),
true);
855 addPhiValues(
Flow, Entry);
856 DT->changeImmediateDominator(Entry,
Flow);
859 while (!Order.empty() && !Visited.count(LoopEnd) &&
860 dominatesPredicates(Entry, Order.back())) {
861 handleLoops(
false, LoopEnd);
864 changeExit(PrevNode, Next,
false);
869 void StructurizeCFG::handleLoops(
bool ExitUseAllowed,
874 if (!
Loops.count(LoopStart)) {
875 wireFlow(ExitUseAllowed, LoopEnd);
879 if (!isPredictableTrue(Node))
880 LoopStart = needPrefix(
true);
882 LoopEnd =
Loops[Node->getEntry()];
883 wireFlow(
false, LoopEnd);
884 while (!Visited.count(LoopEnd)) {
885 handleLoops(
false, LoopEnd);
892 LoopStart->
setName(
"entry.orig");
900 DT->setNewRoot(NewEntry);
904 LoopEnd = needPrefix(
false);
905 BasicBlock *Next = needPostfix(LoopEnd, ExitUseAllowed);
907 BoolUndef, LoopEnd));
908 addPhiValues(LoopEnd, LoopStart);
914 void StructurizeCFG::createFlow() {
916 bool EntryDominatesExit = DT->dominates(ParentRegion->getEntry(), Exit);
918 AffectedPhis.clear();
927 while (!Order.empty()) {
928 handleLoops(EntryDominatesExit,
nullptr);
932 changeExit(PrevNode, Exit, EntryDominatesExit);
934 assert(EntryDominatesExit);
939 void StructurizeCFG::rebuildSSA() {
943 bool Initialized =
false;
948 if (
User->getParent() ==
BB) {
950 }
else if (
PHINode *UserPN = dyn_cast<PHINode>(
User)) {
951 if (UserPN->getIncomingBlock(U) ==
BB)
955 if (DT->dominates(&
I,
User))
973 bool SubRegionsAreUniform =
true;
975 unsigned ConditionalDirectChildren = 0;
977 for (
auto E : R->elements()) {
978 if (!
E->isSubRegion()) {
979 auto Br = dyn_cast<BranchInst>(
E->getEntry()->getTerminator());
980 if (!Br || !Br->isConditional())
983 if (!
DA.isUniform(Br))
987 ConditionalDirectChildren++;
990 <<
" has uniform terminator\n");
1002 auto Br = dyn_cast<BranchInst>(
BB->getTerminator());
1003 if (!Br || !Br->isConditional())
1006 if (!Br->getMetadata(UniformMDKindID)) {
1008 if (!RelaxedUniformRegions)
1011 SubRegionsAreUniform =
false;
1024 return SubRegionsAreUniform || (ConditionalDirectChildren <= 1);
1038 bool StructurizeCFG::makeUniformRegion(
Region *R,
1040 if (
R->isTopLevelRegion())
1048 unsigned UniformMDKindID =
1049 R->getEntry()->getContext().getMDKindID(
"structurizecfg.uniform");
1052 LLVM_DEBUG(
dbgs() <<
"Skipping region with uniform control flow: " << *R
1061 if (
E->isSubRegion())
1065 Term->setMetadata(UniformMDKindID, MD);
1075 if (
R->isTopLevelRegion())
1080 Func =
R->getEntry()->getParent();
1086 insertConditions(
false);
1087 insertConditions(
true);
1089 simplifyConditions();
1090 simplifyAffectedPhis();
1096 DeletedPhis.clear();
1108 return new StructurizeCFGLegacyPass(SkipUniformRegions);
1112 Regions.push_back(&R);
1113 for (
const auto &
E : R)
1120 bool Changed =
false;
1123 std::vector<Region *> Regions;
1125 while (!Regions.empty()) {
1126 Region *R = Regions.back();
1127 StructurizeCFG SCFG;
1129 Changed |= SCFG.run(R, DT);