82 class DivergencePropagator {
86 : F(F), TTI(TTI), DT(DT), PDT(PDT), DV(DV) {}
87 void populateWithSourcesOfDivergence();
92 void exploreDataDependency(
Value *V);
101 void findUsersOutsideInfluenceRegion(
108 std::vector<Value *> Worklist;
112 void DivergencePropagator::populateWithSourcesOfDivergence() {
116 if (TTI.isSourceOfDivergence(&
I)) {
117 Worklist.push_back(&
I);
121 for (
auto &
Arg :
F.args()) {
122 if (TTI.isSourceOfDivergence(&
Arg)) {
123 Worklist.push_back(&
Arg);
129 void DivergencePropagator::exploreSyncDependency(
TerminatorInst *TI) {
142 if (!DT.isReachableFromEntry(ThisBB))
152 if (IPostDom ==
nullptr)
155 for (
auto I = IPostDom->
begin(); isa<PHINode>(
I); ++
I) {
158 if (!cast<PHINode>(
I)->hasConstantOrUndefValue() && DV.insert(&*
I).second)
159 Worklist.push_back(&*
I);
182 computeInfluenceRegion(ThisBB, IPostDom, InfluenceRegion);
188 while (InfluenceRegion.
count(InfluencedBB)) {
189 for (
auto &
I : *InfluencedBB)
190 findUsersOutsideInfluenceRegion(
I, InfluenceRegion);
192 if (IDomNode ==
nullptr)
194 InfluencedBB = IDomNode->
getBlock();
198 void DivergencePropagator::findUsersOutsideInfluenceRegion(
203 if (DV.insert(UserInst).second)
204 Worklist.push_back(UserInst);
214 std::vector<BasicBlock *> &InfluenceStack) {
216 if (Succ != End && InfluenceRegion.
insert(Succ).second)
217 InfluenceStack.push_back(Succ);
221 void DivergencePropagator::computeInfluenceRegion(
224 assert(PDT.properlyDominates(End, Start) &&
225 "End does not properly dominate Start");
230 std::vector<BasicBlock *> InfluenceStack;
231 addSuccessorsToInfluenceRegion(Start, End, InfluenceRegion, InfluenceStack);
232 while (!InfluenceStack.empty()) {
234 InfluenceStack.pop_back();
235 addSuccessorsToInfluenceRegion(BB, End, InfluenceRegion, InfluenceStack);
239 void DivergencePropagator::exploreDataDependency(
Value *V) {
243 if (!TTI.isAlwaysUniform(U) && DV.insert(UserInst).second)
244 Worklist.push_back(UserInst);
250 while (!Worklist.empty()) {
251 Value *V = Worklist.back();
257 exploreSyncDependency(TI);
259 exploreDataDependency(V);
275 return new DivergenceAnalysis();
285 auto *TTIWP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>();
286 if (TTIWP ==
nullptr)
295 DivergentValues.clear();
296 auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
297 DivergencePropagator DP(F, TTI,
298 getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
299 PDT, DivergentValues);
300 DP.populateWithSourcesOfDivergence();
306 if (DivergentValues.empty())
308 const Value *FirstDivergentValue = *DivergentValues.begin();
310 if (
const Argument *
Arg = dyn_cast<Argument>(FirstDivergentValue)) {
311 F =
Arg->getParent();
313 dyn_cast<Instruction>(FirstDivergentValue)) {
321 if (DivergentValues.count(&
Arg))
322 OS <<
"DIVERGENT: " <<
Arg <<
"\n";
326 if (DivergentValues.count(&I))
327 OS <<
"DIVERGENT:" << I <<
"\n";
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
This class represents an incoming formal argument to a Function.
Compute iterated dominance frontiers using a linear time algorithm.
A Module instance is used to store all the information related to an LLVM module. ...
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
iterator begin()
Instruction iterator methods.
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
FunctionPass * createDivergenceAnalysisPass()
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Subclasses of this class are all able to terminate a basic block.
LLVM Basic Block Representation.
void print(raw_ostream &OS, const Module *) const override
print - Print out the internal state of the pass.
DomTreeNodeBase * getIDom() const
std::pair< iterator, bool > insert(const ValueT &V)
Represent the analysis usage information of a pass.
const Instruction & back() const
static const unsigned End
FunctionPass class - This class is used to implement most global optimizations.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
static char ID
end namespace anonymous
void setPreservesAll()
Set by analyses that do not transform their input at all.
iterator_range< user_iterator > users()
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
static void propagate(InstantiatedValue From, InstantiatedValue To, MatchState State, ReachabilitySet &ReachSet, std::vector< WorkListItem > &WorkList)
amdgpu Simplify well known AMD library false Value Value * Arg
const Function * getParent() const
Return the enclosing method, or null if none.
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getNumSuccessors() const
Return the number of successors that this terminator has.
LLVM Value Representation.
succ_range successors(BasicBlock *BB)
This class implements an extremely fast bulk output stream that can only output to a stream...
inst_range instructions(Function *F)
Legacy analysis pass which computes a DominatorTree.
INITIALIZE_PASS_BEGIN(DivergenceAnalysis, "divergence", "Divergence Analysis", false, true) INITIALIZE_PASS_END(DivergenceAnalysis
iterator_range< arg_iterator > args()
const BasicBlock * getParent() const