LLVM 18.0.0git
AMDGPUUnifyDivergentExitNodes.cpp
Go to the documentation of this file.
1//===- AMDGPUUnifyDivergentExitNodes.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// This is a variant of the UnifyFunctionExitNodes pass. Rather than ensuring
10// there is at most one ret and one unreachable instruction, it ensures there is
11// at most one divergent exiting block.
12//
13// StructurizeCFG can't deal with multi-exit regions formed by branches to
14// multiple return nodes. It is not desirable to structurize regions with
15// uniform branches, so unifying those to the same return block as divergent
16// branches inhibits use of scalar branching. It still can't deal with the case
17// where one branch goes to return, and one unreachable. Replace unreachable in
18// this case with a return.
19//
20//===----------------------------------------------------------------------===//
21
23#include "AMDGPU.h"
24#include "SIDefines.h"
25#include "llvm/ADT/ArrayRef.h"
28#include "llvm/ADT/StringRef.h"
33#include "llvm/IR/BasicBlock.h"
34#include "llvm/IR/CFG.h"
35#include "llvm/IR/Constants.h"
36#include "llvm/IR/Dominators.h"
37#include "llvm/IR/Function.h"
38#include "llvm/IR/IRBuilder.h"
39#include "llvm/IR/InstrTypes.h"
41#include "llvm/IR/Intrinsics.h"
42#include "llvm/IR/IntrinsicsAMDGPU.h"
43#include "llvm/IR/Type.h"
45#include "llvm/Pass.h"
51
52using namespace llvm;
53
54#define DEBUG_TYPE "amdgpu-unify-divergent-exit-nodes"
55
56namespace {
57
58class AMDGPUUnifyDivergentExitNodesImpl {
59private:
60 const TargetTransformInfo *TTI = nullptr;
61
62public:
63 AMDGPUUnifyDivergentExitNodesImpl() = delete;
64 AMDGPUUnifyDivergentExitNodesImpl(const TargetTransformInfo *TTI)
65 : TTI(TTI) {}
66
67 // We can preserve non-critical-edgeness when we unify function exit nodes
68 BasicBlock *unifyReturnBlockSet(Function &F, DomTreeUpdater &DTU,
69 ArrayRef<BasicBlock *> ReturningBlocks,
71 bool run(Function &F, DominatorTree *DT, const PostDominatorTree &PDT,
72 const UniformityInfo &UA);
73};
74
75class AMDGPUUnifyDivergentExitNodes : public FunctionPass {
76public:
77 static char ID;
78 AMDGPUUnifyDivergentExitNodes() : FunctionPass(ID) {
81 }
82 void getAnalysisUsage(AnalysisUsage &AU) const override;
83 bool runOnFunction(Function &F) override;
84};
85} // end anonymous namespace
86
87char AMDGPUUnifyDivergentExitNodes::ID = 0;
88
89char &llvm::AMDGPUUnifyDivergentExitNodesID = AMDGPUUnifyDivergentExitNodes::ID;
90
91INITIALIZE_PASS_BEGIN(AMDGPUUnifyDivergentExitNodes, DEBUG_TYPE,
92 "Unify divergent function exit nodes", false, false)
96INITIALIZE_PASS_END(AMDGPUUnifyDivergentExitNodes, DEBUG_TYPE,
97 "Unify divergent function exit nodes", false, false)
98
99void AMDGPUUnifyDivergentExitNodes::getAnalysisUsage(AnalysisUsage &AU) const {
101 AU.addRequired<DominatorTreeWrapperPass>();
102
103 AU.addRequired<PostDominatorTreeWrapperPass>();
104
105 AU.addRequired<UniformityInfoWrapperPass>();
106
108 AU.addPreserved<DominatorTreeWrapperPass>();
109 // FIXME: preserve PostDominatorTreeWrapperPass
110 }
111
112 // No divergent values are changed, only blocks and branch edges.
113 AU.addPreserved<UniformityInfoWrapperPass>();
114
115 // We preserve the non-critical-edgeness property
116 AU.addPreservedID(BreakCriticalEdgesID);
117
118 FunctionPass::getAnalysisUsage(AU);
119
120 AU.addRequired<TargetTransformInfoWrapperPass>();
121}
122
123/// \returns true if \p BB is reachable through only uniform branches.
124/// XXX - Is there a more efficient way to find this?
125static bool isUniformlyReached(const UniformityInfo &UA, BasicBlock &BB) {
128
129 while (!Stack.empty()) {
130 BasicBlock *Top = Stack.pop_back_val();
131 if (!UA.isUniform(Top->getTerminator()))
132 return false;
133
134 for (BasicBlock *Pred : predecessors(Top)) {
135 if (Visited.insert(Pred).second)
136 Stack.push_back(Pred);
137 }
138 }
139
140 return true;
141}
142
143BasicBlock *AMDGPUUnifyDivergentExitNodesImpl::unifyReturnBlockSet(
144 Function &F, DomTreeUpdater &DTU, ArrayRef<BasicBlock *> ReturningBlocks,
145 StringRef Name) {
146 // Otherwise, we need to insert a new basic block into the function, add a PHI
147 // nodes (if the function returns values), and convert all of the return
148 // instructions into unconditional branches.
149 BasicBlock *NewRetBlock = BasicBlock::Create(F.getContext(), Name, &F);
150 IRBuilder<> B(NewRetBlock);
151
152 PHINode *PN = nullptr;
153 if (F.getReturnType()->isVoidTy()) {
154 B.CreateRetVoid();
155 } else {
156 // If the function doesn't return void... add a PHI node to the block...
157 PN = B.CreatePHI(F.getReturnType(), ReturningBlocks.size(),
158 "UnifiedRetVal");
159 B.CreateRet(PN);
160 }
161
162 // Loop over all of the blocks, replacing the return instruction with an
163 // unconditional branch.
164 std::vector<DominatorTree::UpdateType> Updates;
165 Updates.reserve(ReturningBlocks.size());
166 for (BasicBlock *BB : ReturningBlocks) {
167 // Add an incoming element to the PHI node for every return instruction that
168 // is merging into this new block...
169 if (PN)
170 PN->addIncoming(BB->getTerminator()->getOperand(0), BB);
171
172 // Remove and delete the return inst.
173 BB->getTerminator()->eraseFromParent();
174 BranchInst::Create(NewRetBlock, BB);
175 Updates.push_back({DominatorTree::Insert, BB, NewRetBlock});
176 }
177
179 DTU.applyUpdates(Updates);
180 Updates.clear();
181
182 for (BasicBlock *BB : ReturningBlocks) {
183 // Cleanup possible branch to unconditional branch to the return.
184 simplifyCFG(BB, *TTI, RequireAndPreserveDomTree ? &DTU : nullptr,
185 SimplifyCFGOptions().bonusInstThreshold(2));
186 }
187
188 return NewRetBlock;
189}
190
191bool AMDGPUUnifyDivergentExitNodesImpl::run(Function &F, DominatorTree *DT,
192 const PostDominatorTree &PDT,
193 const UniformityInfo &UA) {
194 assert(hasOnlySimpleTerminator(F) && "Unsupported block terminator.");
195
196 if (PDT.root_size() == 0 ||
197 (PDT.root_size() == 1 &&
198 !isa<BranchInst>(PDT.getRoot()->getTerminator())))
199 return false;
200
201 // Loop over all of the blocks in a function, tracking all of the blocks that
202 // return.
203 SmallVector<BasicBlock *, 4> ReturningBlocks;
204 SmallVector<BasicBlock *, 4> UnreachableBlocks;
205
206 // Dummy return block for infinite loop.
207 BasicBlock *DummyReturnBB = nullptr;
208
209 bool Changed = false;
210 std::vector<DominatorTree::UpdateType> Updates;
211
212 // TODO: For now we unify all exit blocks, even though they are uniformly
213 // reachable, if there are any exits not uniformly reached. This is to
214 // workaround the limitation of structurizer, which can not handle multiple
215 // function exits. After structurizer is able to handle multiple function
216 // exits, we should only unify UnreachableBlocks that are not uniformly
217 // reachable.
218 bool HasDivergentExitBlock = llvm::any_of(
219 PDT.roots(), [&](auto BB) { return !isUniformlyReached(UA, *BB); });
220
221 for (BasicBlock *BB : PDT.roots()) {
222 if (isa<ReturnInst>(BB->getTerminator())) {
223 if (HasDivergentExitBlock)
224 ReturningBlocks.push_back(BB);
225 } else if (isa<UnreachableInst>(BB->getTerminator())) {
226 if (HasDivergentExitBlock)
227 UnreachableBlocks.push_back(BB);
228 } else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
229
230 ConstantInt *BoolTrue = ConstantInt::getTrue(F.getContext());
231 if (DummyReturnBB == nullptr) {
232 DummyReturnBB = BasicBlock::Create(F.getContext(),
233 "DummyReturnBlock", &F);
234 Type *RetTy = F.getReturnType();
235 Value *RetVal = RetTy->isVoidTy() ? nullptr : PoisonValue::get(RetTy);
236 ReturnInst::Create(F.getContext(), RetVal, DummyReturnBB);
237 ReturningBlocks.push_back(DummyReturnBB);
238 }
239
240 if (BI->isUnconditional()) {
241 BasicBlock *LoopHeaderBB = BI->getSuccessor(0);
242 BI->eraseFromParent(); // Delete the unconditional branch.
243 // Add a new conditional branch with a dummy edge to the return block.
244 BranchInst::Create(LoopHeaderBB, DummyReturnBB, BoolTrue, BB);
245 Updates.push_back({DominatorTree::Insert, BB, DummyReturnBB});
246 } else { // Conditional branch.
248
249 // Create a new transition block to hold the conditional branch.
250 BasicBlock *TransitionBB = BB->splitBasicBlock(BI, "TransitionBlock");
251
252 Updates.reserve(Updates.size() + 2 * Successors.size() + 2);
253
254 // 'Successors' become successors of TransitionBB instead of BB,
255 // and TransitionBB becomes a single successor of BB.
256 Updates.push_back({DominatorTree::Insert, BB, TransitionBB});
257 for (BasicBlock *Successor : Successors) {
258 Updates.push_back({DominatorTree::Insert, TransitionBB, Successor});
259 Updates.push_back({DominatorTree::Delete, BB, Successor});
260 }
261
262 // Create a branch that will always branch to the transition block and
263 // references DummyReturnBB.
265 BranchInst::Create(TransitionBB, DummyReturnBB, BoolTrue, BB);
266 Updates.push_back({DominatorTree::Insert, BB, DummyReturnBB});
267 }
268 Changed = true;
269 }
270 }
271
272 if (!UnreachableBlocks.empty()) {
273 BasicBlock *UnreachableBlock = nullptr;
274
275 if (UnreachableBlocks.size() == 1) {
276 UnreachableBlock = UnreachableBlocks.front();
277 } else {
278 UnreachableBlock = BasicBlock::Create(F.getContext(),
279 "UnifiedUnreachableBlock", &F);
280 new UnreachableInst(F.getContext(), UnreachableBlock);
281
282 Updates.reserve(Updates.size() + UnreachableBlocks.size());
283 for (BasicBlock *BB : UnreachableBlocks) {
284 // Remove and delete the unreachable inst.
285 BB->getTerminator()->eraseFromParent();
286 BranchInst::Create(UnreachableBlock, BB);
287 Updates.push_back({DominatorTree::Insert, BB, UnreachableBlock});
288 }
289 Changed = true;
290 }
291
292 if (!ReturningBlocks.empty()) {
293 // Don't create a new unreachable inst if we have a return. The
294 // structurizer/annotator can't handle the multiple exits
295
296 Type *RetTy = F.getReturnType();
297 Value *RetVal = RetTy->isVoidTy() ? nullptr : PoisonValue::get(RetTy);
298 // Remove and delete the unreachable inst.
299 UnreachableBlock->getTerminator()->eraseFromParent();
300
301 Function *UnreachableIntrin =
302 Intrinsic::getDeclaration(F.getParent(), Intrinsic::amdgcn_unreachable);
303
304 // Insert a call to an intrinsic tracking that this is an unreachable
305 // point, in case we want to kill the active lanes or something later.
306 CallInst::Create(UnreachableIntrin, {}, "", UnreachableBlock);
307
308 // Don't create a scalar trap. We would only want to trap if this code was
309 // really reached, but a scalar trap would happen even if no lanes
310 // actually reached here.
311 ReturnInst::Create(F.getContext(), RetVal, UnreachableBlock);
312 ReturningBlocks.push_back(UnreachableBlock);
313 Changed = true;
314 }
315 }
316
317 // FIXME: add PDT here once simplifycfg is ready.
318 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
320 DTU.applyUpdates(Updates);
321 Updates.clear();
322
323 // Now handle return blocks.
324 if (ReturningBlocks.empty())
325 return Changed; // No blocks return
326
327 if (ReturningBlocks.size() == 1)
328 return Changed; // Already has a single return block
329
330 unifyReturnBlockSet(F, DTU, ReturningBlocks, "UnifiedReturnBlock");
331 return true;
332}
333
334bool AMDGPUUnifyDivergentExitNodes::runOnFunction(Function &F) {
335 DominatorTree *DT = nullptr;
337 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
338 const auto &PDT =
339 getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
340 const auto &UA = getAnalysis<UniformityInfoWrapperPass>().getUniformityInfo();
341 const auto *TranformInfo =
342 &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
343 return AMDGPUUnifyDivergentExitNodesImpl(TranformInfo).run(F, DT, PDT, UA);
344}
345
349 DominatorTree *DT = nullptr;
352
353 const auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
354 const auto &UA = AM.getResult<UniformityInfoAnalysis>(F);
355 const auto *TransformInfo = &AM.getResult<TargetIRAnalysis>(F);
356 return AMDGPUUnifyDivergentExitNodesImpl(TransformInfo).run(F, DT, PDT, UA)
359}
static bool isUniformlyReached(const UniformityInfo &UA, BasicBlock &BB)
Unify divergent function exit nodes
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
return RetTy
Performs the initial survey of the specified function
std::string Name
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
#define F(x, y, z)
Definition: MD5.cpp:55
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This pass exposes codegen information to IR-level passes.
LLVM IR instance of the generic uniformity analysis.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:649
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:803
Represent the analysis usage information of a pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:206
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:607
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
Definition: BasicBlock.cpp:315
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:228
Conditional or Unconditional Branch instruction.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:833
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:277
iterator_range< root_iterator > roots()
size_t root_size() const
NodeT * getRoot() const
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:312
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:164
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
bool isUniform(ConstValueRefT V) const
Whether V is uniform/non-divergent.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2639
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:93
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1743
Analysis pass which computes a PostDominatorTree.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:172
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:175
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:178
static ReturnInst * Create(LLVMContext &C, Value *retVal=nullptr, Instruction *InsertBefore=nullptr)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
Analysis pass providing the TargetTransformInfo.
Result run(const Function &F, FunctionAnalysisManager &)
Wrapper pass for TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
Analysis pass which computes UniformityInfo.
Legacy analysis pass which computes a CycleInfo.
This function has undefined behavior.
LLVM Value Representation.
Definition: Value.h:74
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1444
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool hasOnlySimpleTerminator(const Function &F)
auto successors(const MachineBasicBlock *BB)
char & AMDGPUUnifyDivergentExitNodesID
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1733
cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
char & BreakCriticalEdgesID
auto predecessors(const MachineBasicBlock *BB)
void initializeAMDGPUUnifyDivergentExitNodesPass(PassRegistry &)