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