41#include "llvm/IR/IntrinsicsAMDGPU.h"
53#define DEBUG_TYPE "amdgpu-unify-divergent-exit-nodes"
57class AMDGPUUnifyDivergentExitNodesImpl {
62 AMDGPUUnifyDivergentExitNodesImpl() =
delete;
74class AMDGPUUnifyDivergentExitNodes :
public FunctionPass {
83char AMDGPUUnifyDivergentExitNodes::ID = 0;
88 "Unify divergent function exit nodes",
false,
false)
95void AMDGPUUnifyDivergentExitNodes::getAnalysisUsage(
AnalysisUsage &AU)
const {
122 while (!Stack.empty()) {
128 if (Visited.
insert(Pred).second)
129 Stack.push_back(Pred);
136BasicBlock *AMDGPUUnifyDivergentExitNodesImpl::unifyReturnBlockSet(
145 PHINode *PN =
nullptr;
146 if (
F.getReturnType()->isVoidTy()) {
150 PN =
B.CreatePHI(
F.getReturnType(), ReturningBlocks.
size(),
157 std::vector<DominatorTree::UpdateType> Updates;
158 Updates.reserve(ReturningBlocks.
size());
159 for (BasicBlock *BB : ReturningBlocks) {
163 PN->
addIncoming(BB->getTerminator()->getOperand(0), BB);
166 BB->getTerminator()->eraseFromParent();
168 Updates.emplace_back(DominatorTree::Insert, BB, NewRetBlock);
175 for (BasicBlock *BB : ReturningBlocks) {
178 SimplifyCFGOptions().bonusInstThreshold(2));
184bool AMDGPUUnifyDivergentExitNodesImpl::run(Function &
F, DominatorTree *DT,
185 const PostDominatorTree &PDT,
203 std::vector<DominatorTree::UpdateType> Updates;
212 PDT.
roots(), [&](
auto BB) { return !isUniformlyReached(UA, *BB); });
214 for (BasicBlock *BB : PDT.
roots()) {
217 if (CI && CI->isMustTailCall())
219 if (HasDivergentExitBlock)
222 if (HasDivergentExitBlock)
227 if (DummyReturnBB ==
nullptr) {
229 "DummyReturnBlock", &
F);
230 Type *RetTy =
F.getReturnType();
233 ReturningBlocks.
push_back(DummyReturnBB);
236 if (BI->isUnconditional()) {
237 BasicBlock *LoopHeaderBB = BI->getSuccessor(0);
238 BI->eraseFromParent();
241 Updates.emplace_back(DominatorTree::Insert, BB, DummyReturnBB);
246 BasicBlock *TransitionBB = BB->splitBasicBlock(BI,
"TransitionBlock");
248 Updates.reserve(Updates.size() + 2 * Successors.size() + 2);
252 Updates.emplace_back(DominatorTree::Insert, BB, TransitionBB);
253 for (BasicBlock *
Successor : Successors) {
254 Updates.emplace_back(DominatorTree::Insert, TransitionBB,
Successor);
255 Updates.emplace_back(DominatorTree::Delete, BB,
Successor);
260 BB->getTerminator()->eraseFromParent();
262 Updates.emplace_back(DominatorTree::Insert, BB, DummyReturnBB);
268 if (!UnreachableBlocks.
empty()) {
271 if (UnreachableBlocks.
size() == 1) {
272 UnreachableBlock = UnreachableBlocks.
front();
275 "UnifiedUnreachableBlock", &
F);
276 new UnreachableInst(
F.getContext(), UnreachableBlock);
278 Updates.reserve(Updates.size() + UnreachableBlocks.
size());
279 for (BasicBlock *BB : UnreachableBlocks) {
281 BB->getTerminator()->eraseFromParent();
283 Updates.emplace_back(DominatorTree::Insert, BB, UnreachableBlock);
288 if (!ReturningBlocks.
empty()) {
292 Type *RetTy =
F.getReturnType();
298 F.getParent(), Intrinsic::amdgcn_unreachable);
308 ReturningBlocks.
push_back(UnreachableBlock);
314 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
320 if (ReturningBlocks.
empty())
323 if (ReturningBlocks.
size() == 1)
326 unifyReturnBlockSet(
F, DTU, ReturningBlocks,
"UnifiedReturnBlock");
330bool AMDGPUUnifyDivergentExitNodes::runOnFunction(Function &
F) {
331 DominatorTree *DT =
nullptr;
333 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
335 getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
336 const auto &UA = getAnalysis<UniformityInfoWrapperPass>().getUniformityInfo();
337 const auto *TranformInfo =
338 &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
339 return AMDGPUUnifyDivergentExitNodesImpl(TranformInfo).run(
F, DT, PDT, UA);
352 return AMDGPUUnifyDivergentExitNodesImpl(TransformInfo).
run(
F, DT, PDT, UA)
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static bool isUniformlyReached(const UniformityInfo &UA, BasicBlock &BB)
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...
static bool runOnFunction(Function &F, bool PostInlining)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - Get the array size.
LLVM Basic Block Representation.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
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...
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
Analysis pass which computes a DominatorTree.
iterator_range< root_iterator > roots()
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
FunctionPass class - This class is used to implement most global optimizations.
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Analysis pass which computes a PostDominatorTree.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
static ReturnInst * Create(LLVMContext &C, Value *retVal=nullptr, InsertPosition 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.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
Analysis pass providing the TargetTransformInfo.
LLVM_ABI Result run(const Function &F, FunctionAnalysisManager &)
bool isVoidTy() const
Return true if this is 'void'.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ BasicBlock
Various leaf nodes.
LLVM_ABI Function * getOrInsertDeclaration(Module *M, ID id, ArrayRef< Type * > Tys={})
Look up the Function declaration of the intrinsic id in the Module M.
This is an optimization pass for GlobalISel generic memory operations.
GenericUniformityInfo< SSAContext > UniformityInfo
FunctionAddr VTableAddr Value
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI bool hasOnlySimpleTerminator(const Function &F)
auto successors(const MachineBasicBlock *BB)
char & AMDGPUUnifyDivergentExitNodesID
auto dyn_cast_or_null(const Y &Val)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI char & BreakCriticalEdgesID
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ABI cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >
LLVM_ABI bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
auto predecessors(const MachineBasicBlock *BB)
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.