1//===- StructurizeCFG.cpp -------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "llvm/Transforms/Scalar/StructurizeCFG.h"
10#include "ScalarOptions.h"
11#include "llvm/ADT/DenseMap.h"
12#include "llvm/ADT/EquivalenceClasses.h"
13#include "llvm/ADT/MapVector.h"
14#include "llvm/ADT/SCCIterator.h"
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/SmallPtrSet.h"
17#include "llvm/ADT/SmallVector.h"
18#include "llvm/Analysis/InstructionSimplify.h"
19#include "llvm/Analysis/RegionInfo.h"
20#include "llvm/Analysis/RegionIterator.h"
21#include "llvm/Analysis/TargetTransformInfo.h"
22#include "llvm/Analysis/UniformityAnalysis.h"
23#include "llvm/IR/BasicBlock.h"
24#include "llvm/IR/CFG.h"
25#include "llvm/IR/Constants.h"
26#include "llvm/IR/Dominators.h"
27#include "llvm/IR/Function.h"
28#include "llvm/IR/InstrTypes.h"
29#include "llvm/IR/Instruction.h"
30#include "llvm/IR/Instructions.h"
31#include "llvm/IR/Metadata.h"
32#include "llvm/IR/PassManager.h"
33#include "llvm/IR/PatternMatch.h"
34#include "llvm/IR/ProfDataUtils.h"
35#include "llvm/IR/Type.h"
36#include "llvm/IR/Use.h"
37#include "llvm/IR/Value.h"
38#include "llvm/IR/ValueHandle.h"
39#include "llvm/InitializePasses.h"
40#include "llvm/Pass.h"
41#include "llvm/Support/Casting.h"
42#include "llvm/Support/Debug.h"
43#include "llvm/Support/raw_ostream.h"
44#include "llvm/Transforms/Scalar.h"
45#include "llvm/Transforms/Utils.h"
46#include "llvm/Transforms/Utils/BasicBlockUtils.h"
47#include "llvm/Transforms/Utils/Local.h"
48#include "llvm/Transforms/Utils/SSAUpdater.h"
49#include "llvm/Transforms/Utils/SSAUpdaterBulk.h"
50#include <cassert>
51#include <utility>
52
53using namespace llvm;
54using namespace llvm::PatternMatch;
55
56#define DEBUG_TYPE "structurizecfg"
57
58// The name for newly created blocks.
59const char FlowBlockName[] = "Flow";
60
61namespace {
62
63// Definition of the complex types used in this pass.
64
65using BBValuePair = std::pair<BasicBlock *, Value *>;
66
67using RNVector = SmallVector<RegionNode *, 8>;
68using BBVector = SmallVector<BasicBlock *, 8>;
69// Branch paired with the block whose predicates define its condition.
70using BranchVector = SmallVector<std::pair<CondBrInst *, BasicBlock *>, 8>;
71using BBValueVector = SmallVector<BBValuePair, 2>;
72
73using BBSet = SmallPtrSet<BasicBlock *, 8>;
74
75using PhiMap = MapVector<PHINode *, BBValueVector>;
76using BB2BBVecMap = MapVector<BasicBlock *, BBVector>;
77
78using BBPhiMap = DenseMap<BasicBlock *, PhiMap>;
79
80using MaybeCondBranchWeights = std::optional<class CondBranchWeights>;
81
82class CondBranchWeights {
83 uint32_t TrueWeight;
84 uint32_t FalseWeight;
85
86 CondBranchWeights(uint32_t T, uint32_t F) : TrueWeight(T), FalseWeight(F) {}
87
88public:
89 static MaybeCondBranchWeights tryParse(const CondBrInst &Br) {
90 uint64_t T, F;
91 if (!extractBranchWeights(I: Br, TrueVal&: T, FalseVal&: F))
92 return std::nullopt;
93
94 return CondBranchWeights(T, F);
95 }
96
97 static void setMetadata(CondBrInst &Br,
98 const MaybeCondBranchWeights &Weights) {
99 if (!Weights)
100 return;
101 uint32_t Arr[] = {Weights->TrueWeight, Weights->FalseWeight};
102 setBranchWeights(I&: Br, Weights: Arr, IsExpected: false);
103 }
104
105 CondBranchWeights invert() const {
106 return CondBranchWeights{FalseWeight, TrueWeight};
107 }
108};
109
110struct PredInfo {
111 Value *Pred;
112 MaybeCondBranchWeights Weights;
113};
114
115using BBPredicates = DenseMap<BasicBlock *, PredInfo>;
116using PredMap = DenseMap<BasicBlock *, BBPredicates>;
117using BB2BBMap = DenseMap<BasicBlock *, BasicBlock *>;
118using Val2BBMap = DenseMap<Value *, BasicBlock *>;
119
120// A traits type that is intended to be used in graph algorithms. The graph
121// traits starts at an entry node, and traverses the RegionNodes that are in
122// the Nodes set.
123struct SubGraphTraits {
124 using NodeRef = std::pair<RegionNode *, SmallDenseSet<RegionNode *> *>;
125 using BaseSuccIterator = GraphTraits<RegionNode *>::ChildIteratorType;
126
127 // This wraps a set of Nodes into the iterator, so we know which edges to
128 // filter out.
129 class WrappedSuccIterator
130 : public iterator_adaptor_base<
131 WrappedSuccIterator, BaseSuccIterator,
132 std::iterator_traits<BaseSuccIterator>::iterator_category, NodeRef,
133 std::ptrdiff_t, NodeRef *, NodeRef> {
134 SmallDenseSet<RegionNode *> *Nodes;
135
136 public:
137 WrappedSuccIterator(BaseSuccIterator It, SmallDenseSet<RegionNode *> *Nodes)
138 : iterator_adaptor_base(It), Nodes(Nodes) {}
139
140 NodeRef operator*() const { return {*I, Nodes}; }
141 };
142
143 static bool filterAll(const NodeRef &N) { return true; }
144 static bool filterSet(const NodeRef &N) { return N.second->count(V: N.first); }
145
146 using ChildIteratorType =
147 filter_iterator<WrappedSuccIterator, bool (*)(const NodeRef &)>;
148
149 static NodeRef getEntryNode(Region *R) {
150 return {GraphTraits<Region *>::getEntryNode(R), nullptr};
151 }
152
153 static NodeRef getEntryNode(NodeRef N) { return N; }
154
155 static iterator_range<ChildIteratorType> children(const NodeRef &N) {
156 auto *filter = N.second ? &filterSet : &filterAll;
157 return make_filter_range(
158 Range: make_range<WrappedSuccIterator>(
159 x: {GraphTraits<RegionNode *>::child_begin(N: N.first), N.second},
160 y: {GraphTraits<RegionNode *>::child_end(N: N.first), N.second}),
161 Pred: filter);
162 }
163
164 static ChildIteratorType child_begin(const NodeRef &N) {
165 return children(N).begin();
166 }
167
168 static ChildIteratorType child_end(const NodeRef &N) {
169 return children(N).end();
170 }
171};
172
173/// Finds the nearest common dominator of a set of BasicBlocks.
174///
175/// For every BB you add to the set, you can specify whether we "remember" the
176/// block. When you get the common dominator, you can also ask whether it's one
177/// of the blocks we remembered.
178class NearestCommonDominator {
179 DominatorTree *DT;
180 BasicBlock *Result = nullptr;
181 bool ResultIsRemembered = false;
182
183 /// Add BB to the resulting dominator.
184 void addBlock(BasicBlock *BB, bool Remember) {
185 if (!Result) {
186 Result = BB;
187 ResultIsRemembered = Remember;
188 return;
189 }
190
191 BasicBlock *NewResult = DT->findNearestCommonDominator(A: Result, B: BB);
192 if (NewResult != Result)
193 ResultIsRemembered = false;
194 if (NewResult == BB)
195 ResultIsRemembered |= Remember;
196 Result = NewResult;
197 }
198
199public:
200 explicit NearestCommonDominator(DominatorTree *DomTree) : DT(DomTree) {}
201
202 void addBlock(BasicBlock *BB) {
203 addBlock(BB, /* Remember = */ false);
204 }
205
206 void addAndRememberBlock(BasicBlock *BB) {
207 addBlock(BB, /* Remember = */ true);
208 }
209
210 /// Get the nearest common dominator of all the BBs added via addBlock() and
211 /// addAndRememberBlock().
212 BasicBlock *result() { return Result; }
213
214 /// Is the BB returned by getResult() one of the blocks we added to the set
215 /// with addAndRememberBlock()?
216 bool resultIsRememberedBlock() { return ResultIsRemembered; }
217};
218
219/// Transforms the control flow graph on one single entry/exit region
220/// at a time.
221///
222/// After the transform all "If"/"Then"/"Else" style control flow looks like
223/// this:
224///
225/// \verbatim
226/// 1
227/// ||
228/// | |
229/// 2 |
230/// | /
231/// |/
232/// 3
233/// || Where:
234/// | | 1 = "If" block, calculates the condition
235/// 4 | 2 = "Then" subregion, runs if the condition is true
236/// | / 3 = "Flow" blocks, newly inserted flow blocks, rejoins the flow
237/// |/ 4 = "Else" optional subregion, runs if the condition is false
238/// 5 5 = "End" block, also rejoins the control flow
239/// \endverbatim
240///
241/// Control flow is expressed as a branch where the true exit goes into the
242/// "Then"/"Else" region, while the false exit skips the region
243/// The condition for the optional "Else" region is expressed as a PHI node.
244/// The incoming values of the PHI node are true for the "If" edge and false
245/// for the "Then" edge.
246///
247/// Additionally to that even complicated loops look like this:
248///
249/// \verbatim
250/// 1
251/// ||
252/// | |
253/// 2 ^ Where:
254/// | / 1 = "Entry" block
255/// |/ 2 = "Loop" optional subregion, with all exits at "Flow" block
256/// 3 3 = "Flow" block, with back edge to entry block
257/// |
258/// \endverbatim
259///
260/// The back edge of the "Flow" block is always on the false side of the branch
261/// while the true side continues the general flow. So the loop condition
262/// consist of a network of PHI nodes where the true incoming values expresses
263/// breaks and the false values expresses continue states.
264
265class StructurizeCFG {
266 Type *Boolean;
267 ConstantInt *BoolTrue;
268 ConstantInt *BoolFalse;
269 Value *BoolPoison;
270 const TargetTransformInfo *TTI;
271 Function *Func;
272 Region *ParentRegion;
273
274 DominatorTree *DT;
275
276 SmallVector<RegionNode *, 8> Order;
277 BBSet Visited;
278 BBSet FlowSet;
279
280 SmallVector<WeakVH, 8> AffectedPhis;
281 BBPhiMap DeletedPhis;
282 BB2BBVecMap AddedPhis;
283
284 PredMap Predicates;
285 BranchVector Conditions;
286
287 BB2BBMap Loops;
288 PredMap LoopPreds;
289 BranchVector LoopConds;
290
291 Val2BBMap HoistedValues;
292
293 RegionNode *PrevNode;
294
295 void hoistZeroCostElseBlockPhiValues(BasicBlock *ElseBB, BasicBlock *ThenBB);
296
297 bool isHoistableInstruction(Instruction *I, BasicBlock *BB,
298 BasicBlock *HoistTo);
299
300 void orderNodes();
301
302 void analyzeLoops(RegionNode *N);
303
304 PredInfo buildCondition(CondBrInst *Term, unsigned Idx, bool Invert);
305
306 void gatherPredicates(RegionNode *N);
307
308 void collectInfos();
309
310 void insertConditions(bool Loops, SSAUpdaterBulk &PhiInserter);
311
312 void simplifyConditions();
313
314 void delPhiValues(BasicBlock *From, BasicBlock *To);
315
316 void addPhiValues(BasicBlock *From, BasicBlock *To);
317
318 void findUndefBlocks(BasicBlock *PHIBlock,
319 const SmallPtrSet<BasicBlock *, 8> &Incomings,
320 SmallVector<BasicBlock *> &UndefBlks) const;
321
322 void mergeIfCompatible(EquivalenceClasses<PHINode *> &PhiClasses, PHINode *A,
323 PHINode *B);
324
325 void setPhiValues();
326
327 void simplifyAffectedPhis();
328
329 void simplifyHoistedPhis();
330
331 DebugLoc killTerminator(BasicBlock *BB);
332
333 void changeExit(RegionNode *Node, BasicBlock *NewExit,
334 bool IncludeDominator);
335
336 BasicBlock *getNextFlow(BasicBlock *Dominator);
337
338 std::pair<BasicBlock *, DebugLoc> needPrefix(bool NeedEmpty);
339
340 BasicBlock *needPostfix(BasicBlock *Flow, bool ExitUseAllowed);
341
342 void setPrevNode(BasicBlock *BB);
343
344 bool dominatesPredicates(BasicBlock *BB, RegionNode *Node);
345
346 bool isPredictableTrue(RegionNode *Node);
347
348 void wireFlow(bool ExitUseAllowed, BasicBlock *LoopEnd);
349
350 void handleLoops(bool ExitUseAllowed, BasicBlock *LoopEnd);
351
352 void createFlow();
353
354 void rebuildSSA();
355
356public:
357 void init(Region *R);
358 bool run(Region *R, DominatorTree *DT, const TargetTransformInfo *TTI);
359 bool makeUniformRegion(Region *R, const UniformityInfo &UA);
360};
361
362class StructurizeCFGLegacyPass : public FunctionPass {
363 bool SkipUniformRegions;
364
365public:
366 static char ID;
367
368 explicit StructurizeCFGLegacyPass(bool SkipUniformRegions_ = false)
369 : FunctionPass(ID), SkipUniformRegions(SkipUniformRegions_) {
370 initializeStructurizeCFGLegacyPassPass(*PassRegistry::getPassRegistry());
371 }
372
373 bool runOnFunction(Function &F) override;
374
375 StringRef getPassName() const override { return "Structurize control flow"; }
376
377 void getAnalysisUsage(AnalysisUsage &AU) const override {
378 AU.addRequired<UniformityInfoWrapperPass>();
379 AU.addRequired<DominatorTreeWrapperPass>();
380 AU.addRequired<TargetTransformInfoWrapperPass>();
381 AU.addRequired<RegionInfoPass>();
382
383 AU.addPreserved<DominatorTreeWrapperPass>();
384 }
385};
386
387} // end anonymous namespace
388
389char StructurizeCFGLegacyPass::ID = 0;
390
391INITIALIZE_PASS_BEGIN(StructurizeCFGLegacyPass, "structurizecfg",
392 "Structurize the CFG", false, false)
393INITIALIZE_PASS_DEPENDENCY(UniformityInfoWrapperPass)
394INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
395INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
396INITIALIZE_PASS_DEPENDENCY(RegionInfoPass)
397INITIALIZE_PASS_END(StructurizeCFGLegacyPass, "structurizecfg",
398 "Structurize the CFG", false, false)
399
400/// Checks whether an instruction is zero cost instruction and checks if the
401/// operands are from different BB. If so, this instruction can be coalesced
402/// if its hoisted to predecessor block. So, this returns true.
403bool StructurizeCFG::isHoistableInstruction(Instruction *I, BasicBlock *BB,
404 BasicBlock *HoistTo) {
405 if (I->getParent() != BB || isa<PHINode>(Val: I))
406 return false;
407
408 // If the instruction is not a zero cost instruction, return false.
409 auto Cost = TTI->getInstructionCost(U: I, CostKind: TargetTransformInfo::TCK_Latency);
410 InstructionCost::CostType CostVal =
411 Cost.isValid()
412 ? Cost.getValue()
413 : (InstructionCost::CostType)TargetTransformInfo::TCC_Expensive;
414 if (CostVal != 0)
415 return false;
416
417 // Check if all operands are available at the hoisting destination.
418 for (auto &Op : I->operands()) {
419 if (auto *OpI = dyn_cast<Instruction>(Val&: Op)) {
420 // Operand must dominate the hoisting destination.
421 if (!DT->dominates(A: OpI->getParent(), B: HoistTo))
422 return false;
423 }
424 }
425
426 return true;
427}
428
429/// Structurization can introduce unnecessary VGPR copies due to register
430/// coalescing interference. For example, if the Else block has a zero-cost
431/// instruction and the Then block modifies the VGPR value, only one value is
432/// live at a time in merge block before structurization. After structurization,
433/// the coalescer may incorrectly treat the Then value as live in the Else block
434/// (via the path Then → Flow → Else), leading to unnecessary VGPR copies.
435///
436/// This function examines phi nodes whose incoming values are zero-cost
437/// instructions in the Else block. It identifies such values that can be safely
438/// hoisted and moves them to the nearest common dominator of Then and Else
439/// blocks. A follow-up function after setting PhiNodes assigns the hoisted
440/// value to poison phi nodes along the if→flow edge, aiding register coalescing
441/// and minimizing unnecessary live ranges.
442void StructurizeCFG::hoistZeroCostElseBlockPhiValues(BasicBlock *ElseBB,
443 BasicBlock *ThenBB) {
444
445 BasicBlock *ElseSucc = ElseBB->getSingleSuccessor();
446 BasicBlock *CommonDominator = DT->findNearestCommonDominator(A: ElseBB, B: ThenBB);
447
448 if (!ElseSucc || !CommonDominator)
449 return;
450 // Only hoist in a simple if-else: ThenBB must branch directly to ElseSucc
451 // and ElseSucc must have exactly 2 predecessors (ThenBB and ElseBB).
452 // simplifyHoistedPhis assumes this exact shape; with additional predecessors
453 // the hoisted value leaks into unrelated control-flow paths.
454 if (ThenBB->getSingleSuccessor() != ElseSucc ||
455 !ElseSucc->hasNPredecessors(N: 2))
456 return;
457 Instruction *Term = CommonDominator->getTerminator();
458 for (PHINode &Phi : ElseSucc->phis()) {
459 Value *ElseVal = Phi.getIncomingValueForBlock(BB: ElseBB);
460 auto *Inst = dyn_cast<Instruction>(Val: ElseVal);
461 if (!Inst || !isHoistableInstruction(I: Inst, BB: ElseBB, HoistTo: CommonDominator))
462 continue;
463 Inst->removeFromParent();
464 Inst->insertInto(ParentBB: CommonDominator, It: Term->getIterator());
465 HoistedValues[Inst] = CommonDominator;
466 }
467}
468
469/// Build up the general order of nodes, by performing a topological sort of the
470/// parent region's nodes, while ensuring that there is no outer cycle node
471/// between any two inner cycle nodes.
472void StructurizeCFG::orderNodes() {
473 Order.resize(N: std::distance(first: GraphTraits<Region *>::nodes_begin(R: ParentRegion),
474 last: GraphTraits<Region *>::nodes_end(R: ParentRegion)));
475 if (Order.empty())
476 return;
477
478 SmallDenseSet<RegionNode *> Nodes;
479 auto EntryNode = SubGraphTraits::getEntryNode(R: ParentRegion);
480
481 // A list of range indices of SCCs in Order, to be processed.
482 SmallVector<std::pair<unsigned, unsigned>, 8> WorkList;
483 unsigned I = 0, E = Order.size();
484 while (true) {
485 // Run through all the SCCs in the subgraph starting with Entry.
486 for (auto SCCI =
487 scc_iterator<SubGraphTraits::NodeRef, SubGraphTraits>::begin(
488 G: EntryNode);
489 !SCCI.isAtEnd(); ++SCCI) {
490 auto &SCC = *SCCI;
491
492 // An SCC up to the size of 2, can be reduced to an entry (the last node),
493 // and a possible additional node. Therefore, it is already in order, and
494 // there is no need to add it to the work-list.
495 unsigned Size = SCC.size();
496 if (Size > 2)
497 WorkList.emplace_back(Args&: I, Args: I + Size);
498
499 // Add the SCC nodes to the Order array.
500 for (const auto &N : SCC) {
501 assert(I < E && "SCC size mismatch!");
502 Order[I++] = N.first;
503 }
504 }
505 assert(I == E && "SCC size mismatch!");
506
507 // If there are no more SCCs to order, then we are done.
508 if (WorkList.empty())
509 break;
510
511 std::tie(args&: I, args&: E) = WorkList.pop_back_val();
512
513 // Collect the set of nodes in the SCC's subgraph. These are only the
514 // possible child nodes; we do not add the entry (last node) otherwise we
515 // will have the same exact SCC all over again.
516 Nodes.clear();
517 Nodes.insert(I: Order.begin() + I, E: Order.begin() + E - 1);
518
519 // Update the entry node.
520 EntryNode.first = Order[E - 1];
521 EntryNode.second = &Nodes;
522 }
523}
524
525/// Determine the end of the loops
526void StructurizeCFG::analyzeLoops(RegionNode *N) {
527 if (N->isSubRegion()) {
528 // Test for exit as back edge
529 BasicBlock *Exit = N->getNodeAs<Region>()->getExit();
530 if (Visited.count(Ptr: Exit))
531 Loops[Exit] = N->getEntry();
532
533 } else {
534 // Test for successors as back edge
535 // TODO: support other terminators other than branches.
536 BasicBlock *BB = N->getNodeAs<BasicBlock>();
537 if (isa<UncondBrInst, CondBrInst>(Val: BB->getTerminator()))
538 for (BasicBlock *Succ : successors(BB))
539 if (Visited.count(Ptr: Succ))
540 Loops[Succ] = BB;
541 }
542}
543
544/// Build the condition for one edge
545PredInfo StructurizeCFG::buildCondition(CondBrInst *Term, unsigned Idx,
546 bool Invert) {
547 Value *Cond = Term->getCondition();
548 auto Weights = CondBranchWeights::tryParse(Br: *Term);
549 if (Idx != (unsigned)Invert) {
550 Cond = invertCondition(Condition: Cond);
551 if (Weights)
552 Weights = Weights->invert();
553 }
554 return {.Pred: Cond, .Weights: Weights};
555}
556
557/// Analyze the predecessors of each block and build up predicates
558void StructurizeCFG::gatherPredicates(RegionNode *N) {
559 RegionInfo *RI = ParentRegion->getRegionInfo();
560 BasicBlock *BB = N->getEntry();
561 BBPredicates &Pred = Predicates[BB];
562 BBPredicates &LPred = LoopPreds[BB];
563
564 for (BasicBlock *P : predecessors(BB)) {
565 // Ignore it if it's a branch from outside into our region entry
566 if (!ParentRegion->contains(BB: P))
567 continue;
568
569 Region *R = RI->getRegionFor(BB: P);
570 if (R == ParentRegion) {
571 if (isa<UncondBrInst>(Val: P->getTerminator())) {
572 if (Visited.count(Ptr: P))
573 Pred[P] = {.Pred: BoolTrue, .Weights: std::nullopt};
574 else
575 LPred[P] = {.Pred: BoolFalse, .Weights: std::nullopt};
576 } else if (auto *CondBr = dyn_cast<CondBrInst>(Val: P->getTerminator())) {
577 bool Idx = CondBr->getSuccessor(i: 0) == BB ? 0 : 1;
578 if (Visited.count(Ptr: P)) {
579 // Normal forward edge
580 // Try to treat Other like an ELSE block
581 BasicBlock *Other = CondBr->getSuccessor(i: !Idx);
582 if (Visited.count(Ptr: Other) && !Loops.count(Val: Other) &&
583 !Pred.count(Val: Other) && !Pred.count(Val: P)) {
584 hoistZeroCostElseBlockPhiValues(ElseBB: BB, ThenBB: Other);
585 Pred[Other] = {.Pred: BoolFalse, .Weights: std::nullopt};
586 Pred[P] = {.Pred: BoolTrue, .Weights: std::nullopt};
587 } else
588 Pred[P] = buildCondition(Term: CondBr, Idx, Invert: false);
589 } else {
590 // Back edge
591 LPred[P] = buildCondition(Term: CondBr, Idx, Invert: true);
592 }
593 }
594 } else {
595 // It's an exit from a sub region
596 while (R->getParent() != ParentRegion)
597 R = R->getParent();
598
599 // Edge from inside a subregion to its entry, ignore it
600 if (*R == *N)
601 continue;
602
603 BasicBlock *Entry = R->getEntry();
604 if (Visited.count(Ptr: Entry))
605 Pred[Entry] = {.Pred: BoolTrue, .Weights: std::nullopt};
606 else
607 LPred[Entry] = {.Pred: BoolFalse, .Weights: std::nullopt};
608 }
609 }
610}
611
612/// Collect various loop and predicate infos
613void StructurizeCFG::collectInfos() {
614 // Reset predicate
615 Predicates.clear();
616
617 // and loop infos
618 Loops.clear();
619 LoopPreds.clear();
620
621 // Reset the visited nodes
622 Visited.clear();
623
624 for (RegionNode *RN : reverse(C&: Order)) {
625 LLVM_DEBUG(dbgs() << "Visiting: "
626 << (RN->isSubRegion() ? "SubRegion with entry: " : "")
627 << RN->getEntry()->getName() << "\n");
628
629 // Analyze all the conditions leading to a node
630 gatherPredicates(N: RN);
631
632 // Remember that we've seen this node
633 Visited.insert(Ptr: RN->getEntry());
634
635 // Find the last back edges
636 analyzeLoops(N: RN);
637 }
638}
639
640/// Insert the missing branch conditions
641void StructurizeCFG::insertConditions(bool Loops, SSAUpdaterBulk &PhiInserter) {
642 BranchVector &Conds = Loops ? LoopConds : Conditions;
643 Value *Default = Loops ? BoolTrue : BoolFalse;
644
645 for (auto [Term, Target] : Conds) {
646 BasicBlock *Parent = Term->getParent();
647 BasicBlock *SuccFalse = Term->getSuccessor(i: 1);
648
649 unsigned Variable = PhiInserter.AddVariable(Name: "", Ty: Boolean);
650 PhiInserter.AddAvailableValue(Var: Variable, BB: Loops ? SuccFalse : Parent,
651 V: Default);
652
653 BBPredicates &Preds = Loops ? LoopPreds[Target] : Predicates[Target];
654
655 NearestCommonDominator Dominator(DT);
656 Dominator.addBlock(BB: Parent);
657
658 PredInfo ParentInfo{.Pred: nullptr, .Weights: std::nullopt};
659 for (auto [BB, PI] : Preds) {
660 if (BB == Parent) {
661 ParentInfo = PI;
662 break;
663 }
664 PhiInserter.AddAvailableValue(Var: Variable, BB, V: PI.Pred);
665 Dominator.addAndRememberBlock(BB);
666 }
667
668 if (ParentInfo.Pred) {
669 Term->setCondition(ParentInfo.Pred);
670 CondBranchWeights::setMetadata(Br&: *Term, Weights: ParentInfo.Weights);
671 } else {
672 if (!Dominator.resultIsRememberedBlock())
673 PhiInserter.AddAvailableValue(Var: Variable, BB: Dominator.result(), V: Default);
674
675 PhiInserter.AddUse(Var: Variable, U: &Term->getOperandUse(i: 0));
676 }
677 }
678}
679
680/// Simplify any inverted conditions that were built by buildConditions.
681void StructurizeCFG::simplifyConditions() {
682 SmallVector<Instruction *> InstToErase;
683 for (auto &I : concat<PredMap::value_type>(Ranges&: Predicates, Ranges&: LoopPreds)) {
684 auto &Preds = I.second;
685 for (auto [BB, PI] : Preds) {
686 Instruction *Inverted;
687 if (match(V: PI.Pred, P: m_Not(V: m_OneUse(SubPattern: m_Instruction(I&: Inverted)))) &&
688 !PI.Pred->use_empty()) {
689 if (auto *InvertedCmp = dyn_cast<CmpInst>(Val: Inverted)) {
690 InvertedCmp->setPredicate(InvertedCmp->getInversePredicate());
691 PI.Pred->replaceAllUsesWith(V: InvertedCmp);
692 InstToErase.push_back(Elt: cast<Instruction>(Val: PI.Pred));
693 }
694 }
695 }
696 }
697 for (auto *I : InstToErase)
698 I->eraseFromParent();
699}
700
701/// Remove all PHI values coming from "From" into "To" and remember
702/// them in DeletedPhis
703void StructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) {
704 PhiMap &Map = DeletedPhis[To];
705 for (PHINode &Phi : To->phis()) {
706 bool Recorded = false;
707 while (Phi.getBasicBlockIndex(BB: From) != -1) {
708 Value *Deleted = Phi.removeIncomingValue(BB: From, DeletePHIIfEmpty: false);
709 Map[&Phi].push_back(Elt: std::make_pair(x&: From, y&: Deleted));
710 if (!Recorded) {
711 AffectedPhis.push_back(Elt: &Phi);
712 Recorded = true;
713 }
714 }
715 }
716}
717
718/// Add a dummy PHI value as soon as we knew the new predecessor
719void StructurizeCFG::addPhiValues(BasicBlock *From, BasicBlock *To) {
720 for (PHINode &Phi : To->phis()) {
721 Value *Poison = PoisonValue::get(T: Phi.getType());
722 Phi.addIncoming(V: Poison, BB: From);
723 }
724 AddedPhis[To].push_back(Elt: From);
725}
726
727/// When we are reconstructing a PHI inside \p PHIBlock with incoming values
728/// from predecessors \p Incomings, we have a chance to mark the available value
729/// from some blocks as undefined. The function will find out all such blocks
730/// and return in \p UndefBlks.
731void StructurizeCFG::findUndefBlocks(
732 BasicBlock *PHIBlock, const SmallPtrSet<BasicBlock *, 8> &Incomings,
733 SmallVector<BasicBlock *> &UndefBlks) const {
734 // We may get a post-structured CFG like below:
735 //
736 // | P1
737 // |/
738 // F1
739 // |\
740 // | N
741 // |/
742 // F2
743 // |\
744 // | P2
745 // |/
746 // F3
747 // |\
748 // B
749 //
750 // B is the block that has a PHI being reconstructed. P1/P2 are predecessors
751 // of B before structurization. F1/F2/F3 are flow blocks inserted during
752 // structurization process. Block N is not a predecessor of B before
753 // structurization, but are placed between the predecessors(P1/P2) of B after
754 // structurization. This usually means that threads went to N never take the
755 // path N->F2->F3->B. For example, the threads take the branch F1->N may
756 // always take the branch F2->P2. So, when we are reconstructing a PHI
757 // originally in B, we can safely say the incoming value from N is undefined.
758 SmallPtrSet<BasicBlock *, 8> VisitedBlock;
759 SmallVector<BasicBlock *, 8> Stack;
760 if (PHIBlock == ParentRegion->getExit()) {
761 for (auto P : predecessors(BB: PHIBlock)) {
762 if (ParentRegion->contains(BB: P))
763 Stack.push_back(Elt: P);
764 }
765 } else {
766 append_range(C&: Stack, R: predecessors(BB: PHIBlock));
767 }
768
769 // Do a backward traversal over the CFG, and stop further searching if
770 // the block is not a Flow. If a block is neither flow block nor the
771 // incoming predecessor, then the incoming value from the block is
772 // undefined value for the PHI being reconstructed.
773 while (!Stack.empty()) {
774 BasicBlock *Current = Stack.pop_back_val();
775 if (!VisitedBlock.insert(Ptr: Current).second)
776 continue;
777
778 if (FlowSet.contains(Ptr: Current))
779 llvm::append_range(C&: Stack, R: predecessors(BB: Current));
780 else if (!Incomings.contains(Ptr: Current))
781 UndefBlks.push_back(Elt: Current);
782 }
783}
784
785// If two phi nodes have compatible incoming values (for each
786// incoming block, either they have the same incoming value or only one phi
787// node has an incoming value), let them share the merged incoming values. The
788// merge process is guided by the equivalence information from \p PhiClasses.
789// The function will possibly update the incoming values of leader phi in
790// DeletedPhis.
791void StructurizeCFG::mergeIfCompatible(
792 EquivalenceClasses<PHINode *> &PhiClasses, PHINode *A, PHINode *B) {
793 auto ItA = PhiClasses.findLeader(ECV: PhiClasses.insert(Data: A));
794 auto ItB = PhiClasses.findLeader(ECV: PhiClasses.insert(Data: B));
795 // They are already in the same class, no work needed.
796 if (ItA == ItB)
797 return;
798
799 PHINode *LeaderA = *ItA;
800 PHINode *LeaderB = *ItB;
801 BBValueVector &IncomingA = DeletedPhis[LeaderA->getParent()][LeaderA];
802 BBValueVector &IncomingB = DeletedPhis[LeaderB->getParent()][LeaderB];
803
804 DenseMap<BasicBlock *, Value *> Mergeable(IncomingA.begin(), IncomingA.end());
805 for (auto [BB, V] : IncomingB) {
806 auto BBIt = Mergeable.find(Val: BB);
807 if (BBIt != Mergeable.end() && BBIt->second != V)
808 return;
809 // Either IncomingA does not have this value or IncomingA has the same
810 // value.
811 Mergeable.insert(KV: {BB, V});
812 }
813
814 // Update the incoming value of leaderA.
815 IncomingA.assign(in_start: Mergeable.begin(), in_end: Mergeable.end());
816 PhiClasses.unionSets(L1: ItA, L2: ItB);
817}
818
819/// Add the real PHI value as soon as everything is set up
820void StructurizeCFG::setPhiValues() {
821 SmallVector<PHINode *, 8> InsertedPhis;
822 SSAUpdater Updater(&InsertedPhis);
823 DenseMap<BasicBlock *, SmallVector<BasicBlock *>> UndefBlksMap;
824
825 // Find phi nodes that have compatible incoming values (either they have
826 // the same value for the same block or only one phi node has an incoming
827 // value, see example below). We only search again the phi's that are
828 // referenced by another phi, which is the case we care about.
829 //
830 // For example (-- means no incoming value):
831 // phi1 : BB1:phi2 BB2:v BB3:--
832 // phi2: BB1:-- BB2:v BB3:w
833 //
834 // Then we can merge these incoming values and let phi1, phi2 use the
835 // same set of incoming values:
836 //
837 // phi1&phi2: BB1:phi2 BB2:v BB3:w
838 //
839 // By doing this, phi1 and phi2 would share more intermediate phi nodes.
840 // This would help reduce the number of phi nodes during SSA reconstruction
841 // and ultimately result in fewer COPY instructions.
842 //
843 // This should be correct, because if a phi node does not have incoming
844 // value from certain block, this means the block is not the predecessor
845 // of the parent block, so we actually don't care about its incoming value.
846 EquivalenceClasses<PHINode *> PhiClasses;
847 for (const auto &[To, From] : AddedPhis) {
848 auto OldPhiIt = DeletedPhis.find(Val: To);
849 if (OldPhiIt == DeletedPhis.end())
850 continue;
851
852 PhiMap &BlkPhis = OldPhiIt->second;
853 SmallVector<BasicBlock *> &UndefBlks = UndefBlksMap[To];
854 SmallPtrSet<BasicBlock *, 8> Incomings;
855
856 // Get the undefined blocks shared by all the phi nodes.
857 if (!BlkPhis.empty()) {
858 Incomings.insert_range(R: llvm::make_first_range(c&: BlkPhis.front().second));
859 findUndefBlocks(PHIBlock: To, Incomings, UndefBlks);
860 }
861
862 for (const auto &[Phi, Incomings] : OldPhiIt->second) {
863 SmallVector<PHINode *> IncomingPHIs;
864 for (const auto &[BB, V] : Incomings) {
865 // First, for each phi, check whether it has incoming value which is
866 // another phi.
867 if (PHINode *P = dyn_cast<PHINode>(Val: V))
868 IncomingPHIs.push_back(Elt: P);
869 }
870
871 for (auto *OtherPhi : IncomingPHIs) {
872 // Skip phis that are unrelated to the phi reconstruction for now.
873 if (!DeletedPhis.contains(Val: OtherPhi->getParent()))
874 continue;
875 mergeIfCompatible(PhiClasses, A: Phi, B: OtherPhi);
876 }
877 }
878 }
879
880 for (const auto &AddedPhi : AddedPhis) {
881 BasicBlock *To = AddedPhi.first;
882 const BBVector &From = AddedPhi.second;
883
884 auto It = DeletedPhis.find(Val: To);
885 if (It == DeletedPhis.end())
886 continue;
887
888 PhiMap &Map = It->second;
889 SmallVector<BasicBlock *> &UndefBlks = UndefBlksMap[To];
890 for (const auto &[Phi, Incoming] : Map) {
891 Value *Poison = PoisonValue::get(T: Phi->getType());
892 Updater.Initialize(Ty: Phi->getType(), Name: "");
893 Updater.AddAvailableValue(BB: &Func->getEntryBlock(), V: Poison);
894 Updater.AddAvailableValue(BB: To, V: Poison);
895
896 // Use leader phi's incoming if there is.
897 auto LeaderIt = PhiClasses.findLeader(V: Phi);
898 bool UseIncomingOfLeader =
899 LeaderIt != PhiClasses.member_end() && *LeaderIt != Phi;
900 const auto &IncomingMap =
901 UseIncomingOfLeader ? DeletedPhis[(*LeaderIt)->getParent()][*LeaderIt]
902 : Incoming;
903
904 SmallVector<BasicBlock *> ConstantPreds;
905 for (const auto &[BB, V] : IncomingMap) {
906 Updater.AddAvailableValue(BB, V);
907 if (isa<Constant>(Val: V))
908 ConstantPreds.push_back(Elt: BB);
909 }
910
911 for (auto UB : UndefBlks) {
912 // If this undef block is dominated by any predecessor(before
913 // structurization) of reconstructed PHI with constant incoming value,
914 // don't mark the available value as undefined. Setting undef to such
915 // block will stop us from getting optimal phi insertion.
916 if (any_of(Range&: ConstantPreds,
917 P: [&](BasicBlock *CP) { return DT->dominates(A: CP, B: UB); }))
918 continue;
919 // Maybe already get a value through sharing with other phi nodes.
920 if (Updater.HasValueForBlock(BB: UB))
921 continue;
922
923 Updater.AddAvailableValue(BB: UB, V: Poison);
924 }
925
926 for (BasicBlock *FI : From)
927 Phi->setIncomingValueForBlock(BB: FI, V: Updater.GetValueAtEndOfBlock(BB: FI));
928 AffectedPhis.push_back(Elt: Phi);
929 }
930 }
931
932 AffectedPhis.append(in_start: InsertedPhis.begin(), in_end: InsertedPhis.end());
933}
934
935/// Updates PHI nodes after hoisted zero cost instructions by replacing poison
936/// entries on Flow nodes with the appropriate hoisted values
937void StructurizeCFG::simplifyHoistedPhis() {
938 for (WeakVH VH : AffectedPhis) {
939 PHINode *Phi = dyn_cast_or_null<PHINode>(Val&: VH);
940 if (!Phi || Phi->getNumIncomingValues() != 2)
941 continue;
942
943 for (int i = 0; i < 2; i++) {
944 Value *V = Phi->getIncomingValue(i);
945 auto BBIt = HoistedValues.find(Val: V);
946
947 if (BBIt == HoistedValues.end())
948 continue;
949
950 Value *OtherV = Phi->getIncomingValue(i: !i);
951 PHINode *OtherPhi = dyn_cast<PHINode>(Val: OtherV);
952 if (!OtherPhi)
953 continue;
954
955 int PoisonValBBIdx = -1;
956 for (size_t i = 0; i < OtherPhi->getNumIncomingValues(); i++) {
957 if (!isa<PoisonValue>(Val: OtherPhi->getIncomingValue(i)))
958 continue;
959 PoisonValBBIdx = i;
960 break;
961 }
962 if (PoisonValBBIdx == -1 ||
963 !DT->dominates(A: BBIt->second,
964 B: OtherPhi->getIncomingBlock(i: PoisonValBBIdx)))
965 continue;
966
967 OtherPhi->setIncomingValue(i: PoisonValBBIdx, V);
968 if (DT->dominates(Def: OtherV, User: Phi))
969 Phi->setIncomingValue(i, V: OtherV);
970 }
971 }
972}
973
974void StructurizeCFG::simplifyAffectedPhis() {
975 bool Changed;
976 do {
977 Changed = false;
978 SimplifyQuery Q(Func->getDataLayout());
979 Q.DT = DT;
980 // Setting CanUseUndef to true might extend value liveness, set it to false
981 // to achieve better register pressure.
982 Q.CanUseUndef = false;
983 for (WeakVH VH : AffectedPhis) {
984 if (auto Phi = dyn_cast_or_null<PHINode>(Val&: VH)) {
985 if (auto NewValue = simplifyInstruction(I: Phi, Q)) {
986 Phi->replaceAllUsesWith(V: NewValue);
987 Phi->eraseFromParent();
988 Changed = true;
989 }
990 }
991 }
992 } while (Changed);
993}
994
995/// Remove phi values from all successors and then remove the terminator.
996DebugLoc StructurizeCFG::killTerminator(BasicBlock *BB) {
997 Instruction *Term = BB->getTerminatorOrNull();
998 if (!Term)
999 return DebugLoc();
1000
1001 for (BasicBlock *Succ : successors(BB))
1002 delPhiValues(From: BB, To: Succ);
1003
1004 DebugLoc DL = Term->getDebugLoc();
1005 Term->eraseFromParent();
1006 return DL;
1007}
1008
1009/// Let node exit(s) point to NewExit
1010void StructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit,
1011 bool IncludeDominator) {
1012 if (Node->isSubRegion()) {
1013 Region *SubRegion = Node->getNodeAs<Region>();
1014 BasicBlock *OldExit = SubRegion->getExit();
1015 BasicBlock *Dominator = nullptr;
1016
1017 // Find all the edges from the sub region to the exit.
1018 // We use make_early_inc_range here because we modify BB's terminator.
1019 for (BasicBlock *BB : llvm::make_early_inc_range(Range: predecessors(BB: OldExit))) {
1020 if (!SubRegion->contains(BB))
1021 continue;
1022
1023 // Modify the edges to point to the new exit
1024 delPhiValues(From: BB, To: OldExit);
1025 BB->getTerminator()->replaceUsesOfWith(From: OldExit, To: NewExit);
1026 addPhiValues(From: BB, To: NewExit);
1027
1028 // Find the new dominator (if requested)
1029 if (IncludeDominator) {
1030 if (!Dominator)
1031 Dominator = BB;
1032 else
1033 Dominator = DT->findNearestCommonDominator(A: Dominator, B: BB);
1034 }
1035 }
1036
1037 // Change the dominator (if requested)
1038 if (Dominator)
1039 DT->changeImmediateDominator(BB: NewExit, NewBB: Dominator);
1040
1041 // Update the region info
1042 SubRegion->replaceExit(BB: NewExit);
1043 } else {
1044 BasicBlock *BB = Node->getNodeAs<BasicBlock>();
1045 DebugLoc DL = killTerminator(BB);
1046 UncondBrInst *Br = UncondBrInst::Create(Target: NewExit, InsertBefore: BB);
1047 Br->setDebugLoc(DL);
1048 addPhiValues(From: BB, To: NewExit);
1049 if (IncludeDominator)
1050 DT->changeImmediateDominator(BB: NewExit, NewBB: BB);
1051 }
1052}
1053
1054/// Create a new flow node and update dominator tree and region info
1055BasicBlock *StructurizeCFG::getNextFlow(BasicBlock *Dominator) {
1056 LLVMContext &Context = Func->getContext();
1057 BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() :
1058 Order.back()->getEntry();
1059 BasicBlock *Flow = BasicBlock::Create(Context, Name: FlowBlockName,
1060 Parent: Func, InsertBefore: Insert);
1061 FlowSet.insert(Ptr: Flow);
1062 DT->addNewBlock(BB: Flow, DomBB: Dominator);
1063 ParentRegion->getRegionInfo()->setRegionFor(BB: Flow, R: ParentRegion);
1064 return Flow;
1065}
1066
1067/// Create a new or reuse the previous node as flow node. Returns a block and a
1068/// debug location to be used for new instructions in that block.
1069std::pair<BasicBlock *, DebugLoc> StructurizeCFG::needPrefix(bool NeedEmpty) {
1070 BasicBlock *Entry = PrevNode->getEntry();
1071
1072 if (!PrevNode->isSubRegion()) {
1073 DebugLoc DL = killTerminator(BB: Entry);
1074 if (!NeedEmpty || Entry->getFirstInsertionPt() == Entry->end())
1075 return {Entry, DL};
1076 }
1077
1078 // create a new flow node
1079 BasicBlock *Flow = getNextFlow(Dominator: Entry);
1080
1081 // and wire it up
1082 changeExit(Node: PrevNode, NewExit: Flow, IncludeDominator: true);
1083 PrevNode = ParentRegion->getBBNode(BB: Flow);
1084 return {Flow, DebugLoc()};
1085}
1086
1087/// Returns the region exit if possible, otherwise just a new flow node
1088BasicBlock *StructurizeCFG::needPostfix(BasicBlock *Flow,
1089 bool ExitUseAllowed) {
1090 if (!Order.empty() || !ExitUseAllowed)
1091 return getNextFlow(Dominator: Flow);
1092
1093 BasicBlock *Exit = ParentRegion->getExit();
1094 DT->changeImmediateDominator(BB: Exit, NewBB: Flow);
1095 addPhiValues(From: Flow, To: Exit);
1096 return Exit;
1097}
1098
1099/// Set the previous node
1100void StructurizeCFG::setPrevNode(BasicBlock *BB) {
1101 PrevNode = ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB)
1102 : nullptr;
1103}
1104
1105/// Does BB dominate all the predicates of Node?
1106bool StructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) {
1107 BBPredicates &Preds = Predicates[Node->getEntry()];
1108 return llvm::all_of(
1109 Range&: Preds, P: [&](const auto &Pred) { return DT->dominates(BB, Pred.first); });
1110}
1111
1112/// Can we predict that this node will always be called?
1113bool StructurizeCFG::isPredictableTrue(RegionNode *Node) {
1114 BBPredicates &Preds = Predicates[Node->getEntry()];
1115 bool Dominated = false;
1116
1117 // Regionentry is always true
1118 if (!PrevNode)
1119 return true;
1120
1121 for (auto [BB, PI] : Preds) {
1122 if (PI.Pred != BoolTrue)
1123 return false;
1124
1125 if (!Dominated && DT->dominates(A: BB, B: PrevNode->getEntry()))
1126 Dominated = true;
1127 }
1128
1129 // TODO: The dominator check is too strict
1130 return Dominated;
1131}
1132
1133/// Take one node from the order vector and wire it up
1134void StructurizeCFG::wireFlow(bool ExitUseAllowed,
1135 BasicBlock *LoopEnd) {
1136 RegionNode *Node = Order.pop_back_val();
1137 Visited.insert(Ptr: Node->getEntry());
1138
1139 if (isPredictableTrue(Node)) {
1140 // Just a linear flow
1141 if (PrevNode) {
1142 changeExit(Node: PrevNode, NewExit: Node->getEntry(), IncludeDominator: true);
1143 }
1144 PrevNode = Node;
1145 } else {
1146 // Insert extra prefix node (or reuse last one)
1147 auto [Flow, DL] = needPrefix(NeedEmpty: false);
1148
1149 // Insert extra postfix node (or use exit instead)
1150 BasicBlock *Entry = Node->getEntry();
1151 BasicBlock *Next = needPostfix(Flow, ExitUseAllowed);
1152
1153 // let it point to entry and next block
1154 CondBrInst *Br = CondBrInst::Create(Cond: BoolPoison, IfTrue: Entry, IfFalse: Next, InsertBefore: Flow);
1155 Br->setDebugLoc(DL);
1156 Conditions.push_back(Elt: {Br, Entry});
1157 addPhiValues(From: Flow, To: Entry);
1158 DT->changeImmediateDominator(BB: Entry, NewBB: Flow);
1159
1160 PrevNode = Node;
1161 while (!Order.empty() && !Visited.count(Ptr: LoopEnd) &&
1162 dominatesPredicates(BB: Entry, Node: Order.back())) {
1163 handleLoops(ExitUseAllowed: false, LoopEnd);
1164 }
1165
1166 changeExit(Node: PrevNode, NewExit: Next, IncludeDominator: false);
1167 setPrevNode(Next);
1168 }
1169}
1170
1171void StructurizeCFG::handleLoops(bool ExitUseAllowed,
1172 BasicBlock *LoopEnd) {
1173 RegionNode *Node = Order.back();
1174 BasicBlock *LoopStart = Node->getEntry();
1175
1176 if (!Loops.count(Val: LoopStart)) {
1177 wireFlow(ExitUseAllowed, LoopEnd);
1178 return;
1179 }
1180
1181 if (!isPredictableTrue(Node))
1182 LoopStart = needPrefix(NeedEmpty: true).first;
1183
1184 LoopEnd = Loops[Node->getEntry()];
1185 wireFlow(ExitUseAllowed: false, LoopEnd);
1186 while (!Visited.count(Ptr: LoopEnd)) {
1187 handleLoops(ExitUseAllowed: false, LoopEnd);
1188 }
1189
1190 assert(LoopStart != &LoopStart->getParent()->getEntryBlock());
1191
1192 // Create an extra loop end node
1193 DebugLoc DL;
1194 std::tie(args&: LoopEnd, args&: DL) = needPrefix(NeedEmpty: false);
1195 BasicBlock *Next = needPostfix(Flow: LoopEnd, ExitUseAllowed);
1196 CondBrInst *Br = CondBrInst::Create(Cond: BoolPoison, IfTrue: Next, IfFalse: LoopStart, InsertBefore: LoopEnd);
1197 Br->setDebugLoc(DL);
1198 BasicBlock *Header = Node->getEntry();
1199 LoopConds.push_back(Elt: {Br, Header});
1200
1201 // The backedge targets the prefix block, so it must always enter the header.
1202 if (LoopStart != Header)
1203 Predicates[Header][LoopEnd] = {.Pred: BoolTrue, .Weights: std::nullopt};
1204
1205 addPhiValues(From: LoopEnd, To: LoopStart);
1206 setPrevNode(Next);
1207}
1208
1209/// After this function control flow looks like it should be, but
1210/// branches and PHI nodes only have undefined conditions.
1211void StructurizeCFG::createFlow() {
1212 BasicBlock *Exit = ParentRegion->getExit();
1213 bool EntryDominatesExit = DT->dominates(A: ParentRegion->getEntry(), B: Exit);
1214
1215 AffectedPhis.clear();
1216 DeletedPhis.clear();
1217 AddedPhis.clear();
1218 Conditions.clear();
1219 LoopConds.clear();
1220
1221 PrevNode = nullptr;
1222 Visited.clear();
1223
1224 while (!Order.empty()) {
1225 handleLoops(ExitUseAllowed: EntryDominatesExit, LoopEnd: nullptr);
1226 }
1227
1228 if (PrevNode)
1229 changeExit(Node: PrevNode, NewExit: Exit, IncludeDominator: EntryDominatesExit);
1230 else
1231 assert(EntryDominatesExit);
1232}
1233
1234/// Handle a rare case where the disintegrated nodes instructions
1235/// no longer dominate all their uses.
1236void StructurizeCFG::rebuildSSA() {
1237 SSAUpdater Updater;
1238 for (BasicBlock *BB : ParentRegion->blocks())
1239 for (Instruction &I : *BB) {
1240 bool Initialized = false;
1241 // We may modify the use list as we iterate over it, so we use
1242 // make_early_inc_range.
1243 for (Use &U : llvm::make_early_inc_range(Range: I.uses())) {
1244 Instruction *User = cast<Instruction>(Val: U.getUser());
1245 if (User->getParent() == BB) {
1246 continue;
1247 } else if (PHINode *UserPN = dyn_cast<PHINode>(Val: User)) {
1248 if (UserPN->getIncomingBlock(U) == BB)
1249 continue;
1250 }
1251
1252 if (DT->dominates(Def: &I, User))
1253 continue;
1254
1255 if (!Initialized) {
1256 Value *Poison = PoisonValue::get(T: I.getType());
1257 Updater.Initialize(Ty: I.getType(), Name: "");
1258 Updater.AddAvailableValue(BB: &Func->getEntryBlock(), V: Poison);
1259 Updater.AddAvailableValue(BB, V: &I);
1260 Initialized = true;
1261 }
1262 Updater.RewriteUseAfterInsertions(U);
1263 }
1264 }
1265}
1266
1267/// Can region \p R be left unstructurized because all of its own control flow
1268/// is uniform?
1269///
1270/// Only the terminators of direct child blocks are checked. Sub-regions are
1271/// processed before their parent, so any divergent control flow inside a
1272/// sub-region has already been structurized and is self-contained: it is
1273/// entered only through the sub-region's entry, and it rejoins either at Flow
1274/// blocks inside the sub-region or, if the sub-region's entry dominates its
1275/// exit, at the exit block itself. Uniform control flow around a sub-region
1276/// therefore does not need structurizing, whatever the sub-region contains.
1277/// (The branches inside sub-regions could not be checked anyway, because they
1278/// may have been removed and re-created since UniformityAnalysis ran.)
1279///
1280/// FIXME: This does not hold for a sub-region whose entry block ends in a
1281/// callbr, because run() leaves such regions unstructurized.
1282static bool hasOnlyUniformBranches(Region *R, const UniformityInfo &UA) {
1283 return none_of(Range: R->elements(), P: [&](RegionNode *E) {
1284 if (E->isSubRegion())
1285 return false;
1286 auto *Br = dyn_cast<CondBrInst>(Val: E->getEntry()->getTerminator());
1287 return Br && UA.isDivergentTerminator(I: Br);
1288 });
1289}
1290
1291void StructurizeCFG::init(Region *R) {
1292 LLVMContext &Context = R->getEntry()->getContext();
1293
1294 Boolean = Type::getInt1Ty(C&: Context);
1295 BoolTrue = ConstantInt::getTrue(Context);
1296 BoolFalse = ConstantInt::getFalse(Context);
1297 BoolPoison = PoisonValue::get(T: Boolean);
1298}
1299
1300bool StructurizeCFG::makeUniformRegion(Region *R, const UniformityInfo &UA) {
1301 if (R->isTopLevelRegion())
1302 return false;
1303
1304 if (hasOnlyUniformBranches(R, UA)) {
1305 LLVM_DEBUG(dbgs() << "Skipping region with uniform control flow: " << *R
1306 << '\n');
1307
1308 // Mark all direct child block terminators as having been treated as
1309 // uniform. Indirect children must not be marked, because sub-regions may
1310 // contain divergent control flow.
1311 LLVMContext &Ctx = R->getEntry()->getContext();
1312 unsigned UniformMDKindID = Ctx.getMDKindID(Name: "structurizecfg.uniform");
1313 MDNode *MD = MDNode::get(Context&: Ctx, MDs: {});
1314 for (RegionNode *E : R->elements()) {
1315 if (E->isSubRegion())
1316 continue;
1317
1318 E->getEntry()->getTerminator()->setMetadata(KindID: UniformMDKindID, Node: MD);
1319 }
1320
1321 return true;
1322 }
1323 return false;
1324}
1325
1326/// Run the transformation for each region found
1327bool StructurizeCFG::run(Region *R, DominatorTree *DT,
1328 const TargetTransformInfo *TTI) {
1329 // CallBr and its corresponding direct target blocks are for now ignored by
1330 // this pass. This is not a limitation for the currently intended uses cases
1331 // of callbr in the AMDGPU backend.
1332 // Parent and child regions are not affected by this (current) restriction.
1333 // See `llvm/test/Transforms/StructurizeCFG/callbr.ll` for details.
1334 if (R->isTopLevelRegion() || isa<CallBrInst>(Val: R->getEntry()->getTerminator()))
1335 return false;
1336
1337 this->DT = DT;
1338 this->TTI = TTI;
1339 Func = R->getEntry()->getParent();
1340
1341 ParentRegion = R;
1342
1343 orderNodes();
1344 collectInfos();
1345 createFlow();
1346
1347 SSAUpdaterBulk PhiInserter;
1348 insertConditions(Loops: false, PhiInserter);
1349 insertConditions(Loops: true, PhiInserter);
1350 PhiInserter.RewriteAndOptimizeAllUses(DT&: *DT);
1351
1352 setPhiValues();
1353 simplifyHoistedPhis();
1354 simplifyConditions();
1355 simplifyAffectedPhis();
1356 rebuildSSA();
1357
1358 // Cleanup
1359 Order.clear();
1360 Visited.clear();
1361 DeletedPhis.clear();
1362 AddedPhis.clear();
1363 Predicates.clear();
1364 Conditions.clear();
1365 Loops.clear();
1366 LoopPreds.clear();
1367 LoopConds.clear();
1368 FlowSet.clear();
1369
1370 return true;
1371}
1372
1373Pass *llvm::createStructurizeCFGPass(bool SkipUniformRegions) {
1374 return new StructurizeCFGLegacyPass(SkipUniformRegions);
1375}
1376
1377static void addRegionIntoQueue(Region &R, std::vector<Region *> &Regions) {
1378 Regions.push_back(x: &R);
1379 for (const auto &E : R)
1380 addRegionIntoQueue(R&: *E, Regions);
1381}
1382
1383StructurizeCFGPass::StructurizeCFGPass(bool SkipUniformRegions_)
1384 : SkipUniformRegions(SkipUniformRegions_) {}
1385
1386void StructurizeCFGPass::printPipeline(
1387 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
1388 static_cast<PassInfoMixin<StructurizeCFGPass> *>(this)->printPipeline(
1389 OS, MapClassName2PassName);
1390 if (SkipUniformRegions)
1391 OS << "<skip-uniform-regions>";
1392}
1393
1394/// Structurize every region in \p RI, processing inner regions before the
1395/// regions that contain them. If \p UI is non-null, skip uniform regions.
1396static bool runImpl(DominatorTree &DT, RegionInfo &RI,
1397 const TargetTransformInfo &TTI, const UniformityInfo *UI) {
1398 bool Changed = false;
1399 std::vector<Region *> Regions;
1400 addRegionIntoQueue(R&: *RI.getTopLevelRegion(), Regions);
1401 while (!Regions.empty()) {
1402 Region *R = Regions.back();
1403 Regions.pop_back();
1404
1405 StructurizeCFG SCFG;
1406 SCFG.init(R);
1407
1408 if (UI && SCFG.makeUniformRegion(R, UA: *UI)) {
1409 Changed = true; // May have added metadata.
1410 continue;
1411 }
1412
1413 Changed |= SCFG.run(R, DT: &DT, TTI: &TTI);
1414 }
1415 return Changed;
1416}
1417
1418bool StructurizeCFGLegacyPass::runOnFunction(Function &F) {
1419 const ScalarOptions &Opts = getScalarOptions(F);
1420 const UniformityInfo *UI = nullptr;
1421 if (valueOr(X: Opts.structurizecfg_skip_uniform_regions, Default: SkipUniformRegions))
1422 UI = &getAnalysis<UniformityInfoWrapperPass>().getUniformityInfo();
1423 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1424 RegionInfo &RI = getAnalysis<RegionInfoPass>().getRegionInfo();
1425 const TargetTransformInfo &TTI =
1426 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1427 return runImpl(DT, RI, TTI, UI);
1428}
1429
1430PreservedAnalyses StructurizeCFGPass::run(Function &F,
1431 FunctionAnalysisManager &AM) {
1432 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
1433 auto &RI = AM.getResult<RegionInfoAnalysis>(IR&: F);
1434 TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(IR&: F);
1435 const ScalarOptions &Opts = getScalarOptions(F);
1436 const UniformityInfo *UI = nullptr;
1437 if (valueOr(X: Opts.structurizecfg_skip_uniform_regions, Default: SkipUniformRegions))
1438 UI = &AM.getResult<UniformityInfoAnalysis>(IR&: F);
1439
1440 if (!runImpl(DT, RI, TTI, UI))
1441 return PreservedAnalyses::all();
1442 PreservedAnalyses PA;
1443 PA.preserve<DominatorTreeAnalysis>();
1444 return PA;
1445}
1446