Lines Matching +full:dt +full:- +full:node
1 //===- StructurizeCFG.cpp -------------------------------------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
63 "structurizecfg-skip-uniform-regions",
69 RelaxedUniformRegions("structurizecfg-relaxed-uniform-regions", cl::Hidden,
95 // traits starts at an entry node, and traverses the RegionNodes that are in
118 static bool filterSet(const NodeRef &N) { return N.second->count(N.first); }
153 DominatorTree *DT;
165 BasicBlock *NewResult = DT->findNearestCommonDominator(Result, BB);
174 explicit NearestCommonDominator(DominatorTree *DomTree) : DT(DomTree) {}
217 /// The condition for the optional "Else" region is expressed as a PHI node.
218 /// The incoming values of the PHI node are true for the "If" edge and false
249 DominatorTree *DT;
297 void changeExit(RegionNode *Node, BasicBlock *NewExit,
308 bool dominatesPredicates(BasicBlock *BB, RegionNode *Node);
310 bool isPredictableTrue(RegionNode *Node);
322 bool run(Region *R, DominatorTree *DT);
348 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
349 return SCFG.run(R, DT);
377 /// parent region's nodes, while ensuring that there is no outer cycle node
399 // An SCC up to the size of 2, can be reduced to an entry (the last node),
400 // and a possible additional node. Therefore, it is already in order, and
401 // there is no need to add it to the work-list.
421 // possible child nodes; we do not add the entry (last node) otherwise we
424 Nodes.insert(Order.begin() + I, Order.begin() + E - 1);
426 // Update the entry node.
427 EntryNode.first = Order[E - 1];
434 if (N->isSubRegion()) {
436 BasicBlock *Exit = N->getNodeAs<Region>()->getExit();
438 Loops[Exit] = N->getEntry();
442 BasicBlock *BB = N->getNodeAs<BasicBlock>();
443 BranchInst *Term = cast<BranchInst>(BB->getTerminator());
445 for (BasicBlock *Succ : Term->successors())
455 if (Term->isConditional()) {
456 Cond = Term->getCondition();
466 RegionInfo *RI = ParentRegion->getRegionInfo();
467 BasicBlock *BB = N->getEntry();
473 if (!ParentRegion->contains(P))
476 Region *R = RI->getRegionFor(P);
479 BranchInst *Term = cast<BranchInst>(P->getTerminator());
480 for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
481 BasicBlock *Succ = Term->getSuccessor(i);
487 if (Term->isConditional()) {
489 BasicBlock *Other = Term->getSuccessor(!i);
506 while (R->getParent() != ParentRegion)
507 R = R->getParent();
513 BasicBlock *Entry = R->getEntry();
536 << (RN->isSubRegion() ? "SubRegion with entry: " : "")
537 << RN->getEntry()->getName() << "\n");
539 // Analyze all the conditions leading to a node
542 // Remember that we've seen this node
543 Visited.insert(RN->getEntry());
553 if (const DebugLoc &DL = BB.getTerminator()->getDebugLoc())
565 assert(Term->isConditional());
567 BasicBlock *Parent = Term->getParent();
568 BasicBlock *SuccTrue = Term->getSuccessor(0);
569 BasicBlock *SuccFalse = Term->getSuccessor(1);
572 PhiInserter.AddAvailableValue(&Func->getEntryBlock(), Default);
577 NearestCommonDominator Dominator(DT);
594 Term->setCondition(ParentValue);
599 Term->setCondition(PhiInserter.GetValueInMiddleOfBlock(Parent));
613 !Cond->use_empty()) {
615 InvertedCmp->setPredicate(InvertedCmp->getInversePredicate());
616 Cond->replaceAllUsesWith(InvertedCmp);
623 I->eraseFromParent();
630 for (PHINode &Phi : To->phis()) {
632 while (Phi.getBasicBlockIndex(From) != -1) {
645 for (PHINode &Phi : To->phis()) {
659 // We may get a post-structured CFG like below:
680 // path N->F2->F3->B. For example, the threads take the branch F1->N may
681 // always take the branch F2->P2. So, when we are reconstructing a PHI
685 if (PHIBlock == ParentRegion->getExit()) {
687 if (ParentRegion->contains(P))
729 Value *Undef = UndefValue::get(Phi->getType());
730 Updater.Initialize(Phi->getType(), "");
731 Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
754 [&](BasicBlock *CP) { return DT->dominates(CP, UB); }))
760 Phi->setIncomingValueForBlock(FI, Updater.GetValueAtEndOfBlock(FI));
775 SimplifyQuery Q(Func->getDataLayout());
776 Q.DT = DT;
783 Phi->replaceAllUsesWith(NewValue);
784 Phi->eraseFromParent();
794 Instruction *Term = BB->getTerminator();
801 Term->eraseFromParent();
804 /// Let node exit(s) point to NewExit
805 void StructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit,
807 if (Node->isSubRegion()) {
808 Region *SubRegion = Node->getNodeAs<Region>();
809 BasicBlock *OldExit = SubRegion->getExit();
815 if (!SubRegion->contains(BB))
820 BB->getTerminator()->replaceUsesOfWith(OldExit, NewExit);
828 Dominator = DT->findNearestCommonDominator(Dominator, BB);
834 DT->changeImmediateDominator(NewExit, Dominator);
837 SubRegion->replaceExit(NewExit);
839 BasicBlock *BB = Node->getNodeAs<BasicBlock>();
842 Br->setDebugLoc(TermDL[BB]);
845 DT->changeImmediateDominator(NewExit, BB);
849 /// Create a new flow node and update dominator tree and region info
851 LLVMContext &Context = Func->getContext();
852 BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() :
853 Order.back()->getEntry();
858 // use a temporary variable to avoid a use-after-free if the map's storage is
863 DT->addNewBlock(Flow, Dominator);
864 ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion);
868 /// Create a new or reuse the previous node as flow node
870 BasicBlock *Entry = PrevNode->getEntry();
872 if (!PrevNode->isSubRegion()) {
874 if (!NeedEmpty || Entry->getFirstInsertionPt() == Entry->end())
878 // create a new flow node
883 PrevNode = ParentRegion->getBBNode(Flow);
887 /// Returns the region exit if possible, otherwise just a new flow node
893 BasicBlock *Exit = ParentRegion->getExit();
894 DT->changeImmediateDominator(Exit, Flow);
899 /// Set the previous node
901 PrevNode = ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB)
905 /// Does BB dominate all the predicates of Node?
906 bool StructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) {
907 BBPredicates &Preds = Predicates[Node->getEntry()];
909 return DT->dominates(BB, Pred.first);
913 /// Can we predict that this node will always be called?
914 bool StructurizeCFG::isPredictableTrue(RegionNode *Node) {
915 BBPredicates &Preds = Predicates[Node->getEntry()];
929 if (!Dominated && DT->dominates(BB, PrevNode->getEntry()))
937 /// Take one node from the order vector and wire it up
940 RegionNode *Node = Order.pop_back_val();
941 Visited.insert(Node->getEntry());
943 if (isPredictableTrue(Node)) {
946 changeExit(PrevNode, Node->getEntry(), true);
948 PrevNode = Node;
950 // Insert extra prefix node (or reuse last one)
953 // Insert extra postfix node (or use exit instead)
954 BasicBlock *Entry = Node->getEntry();
959 Br->setDebugLoc(TermDL[Flow]);
962 DT->changeImmediateDominator(Entry, Flow);
964 PrevNode = Node;
977 RegionNode *Node = Order.back();
978 BasicBlock *LoopStart = Node->getEntry();
985 if (!isPredictableTrue(Node))
988 LoopEnd = Loops[Node->getEntry()];
994 assert(LoopStart != &LoopStart->getParent()->getEntryBlock());
996 // Create an extra loop end node
1000 Br->setDebugLoc(TermDL[LoopEnd]);
1009 BasicBlock *Exit = ParentRegion->getExit();
1010 bool EntryDominatesExit = DT->dominates(ParentRegion->getEntry(), Exit);
1035 for (BasicBlock *BB : ParentRegion->blocks())
1042 if (User->getParent() == BB) {
1045 if (UserPN->getIncomingBlock(U) == BB)
1049 if (DT->dominates(&I, User))
1055 Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
1066 // Bool for if all sub-regions are uniform.
1071 for (auto *E : R->elements()) {
1072 if (!E->isSubRegion()) {
1073 auto Br = dyn_cast<BranchInst>(E->getEntry()->getTerminator());
1074 if (!Br || !Br->isConditional())
1083 LLVM_DEBUG(dbgs() << "BB: " << Br->getParent()->getName()
1086 // Explicitly refuse to treat regions as uniform if they have non-uniform
1088 // subregions because those branches may have been removed and re-created,
1095 for (auto *BB : E->getNodeAs<Region>()->blocks()) {
1096 auto Br = dyn_cast<BranchInst>(BB->getTerminator());
1097 if (!Br || !Br->isConditional())
1100 if (!Br->getMetadata(UniformMDKindID)) {
1116 // a. All sub-regions are uniform.
1122 LLVMContext &Context = R->getEntry()->getContext();
1129 this->UA = nullptr;
1133 if (R->isTopLevelRegion())
1136 this->UA = &UA;
1138 // TODO: We could probably be smarter here with how we handle sub-regions.
1140 // of the pass on sub-regions, and that this metadata doesn't get lost --
1143 R->getEntry()->getContext().getMDKindID("structurizecfg.uniform");
1150 // uniform. To account for a possible future in which non-uniform
1151 // sub-regions are treated more cleverly, indirect children are not
1153 MDNode *MD = MDNode::get(R->getEntry()->getParent()->getContext(), {});
1154 for (RegionNode *E : R->elements()) {
1155 if (E->isSubRegion())
1158 if (Instruction *Term = E->getEntry()->getTerminator())
1159 Term->setMetadata(UniformMDKindID, MD);
1168 bool StructurizeCFG::run(Region *R, DominatorTree *DT) {
1169 if (R->isTopLevelRegion())
1172 this->DT = DT;
1174 Func = R->getEntry()->getParent();
1219 DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(F);
1227 Changed |= SCFG.run(R, DT);