DivergenceAnalysis.cpp [plain text]
#include "llvm/Analysis/DivergenceAnalysis.h"
#include "llvm/Analysis/Passes.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include <vector>
using namespace llvm;
namespace {
class DivergencePropagator {
public:
DivergencePropagator(Function &F, TargetTransformInfo &TTI, DominatorTree &DT,
PostDominatorTree &PDT, DenseSet<const Value *> &DV)
: F(F), TTI(TTI), DT(DT), PDT(PDT), DV(DV) {}
void populateWithSourcesOfDivergence();
void propagate();
private:
void exploreDataDependency(Value *V);
void exploreSyncDependency(TerminatorInst *TI);
void computeInfluenceRegion(BasicBlock *Start, BasicBlock *End,
DenseSet<BasicBlock *> &InfluenceRegion);
void findUsersOutsideInfluenceRegion(
Instruction &I, const DenseSet<BasicBlock *> &InfluenceRegion);
Function &F;
TargetTransformInfo &TTI;
DominatorTree &DT;
PostDominatorTree &PDT;
std::vector<Value *> Worklist; DenseSet<const Value *> &DV; };
void DivergencePropagator::populateWithSourcesOfDivergence() {
Worklist.clear();
DV.clear();
for (auto &I : instructions(F)) {
if (TTI.isSourceOfDivergence(&I)) {
Worklist.push_back(&I);
DV.insert(&I);
}
}
for (auto &Arg : F.args()) {
if (TTI.isSourceOfDivergence(&Arg)) {
Worklist.push_back(&Arg);
DV.insert(&Arg);
}
}
}
void DivergencePropagator::exploreSyncDependency(TerminatorInst *TI) {
BasicBlock *ThisBB = TI->getParent();
BasicBlock *IPostDom = PDT.getNode(ThisBB)->getIDom()->getBlock();
if (IPostDom == nullptr)
return;
for (auto I = IPostDom->begin(); isa<PHINode>(I); ++I) {
if (!cast<PHINode>(I)->hasConstantValue() && DV.insert(&*I).second)
Worklist.push_back(&*I);
}
DenseSet<BasicBlock *> InfluenceRegion;
computeInfluenceRegion(ThisBB, IPostDom, InfluenceRegion);
BasicBlock *InfluencedBB = ThisBB;
while (InfluenceRegion.count(InfluencedBB)) {
for (auto &I : *InfluencedBB)
findUsersOutsideInfluenceRegion(I, InfluenceRegion);
DomTreeNode *IDomNode = DT.getNode(InfluencedBB)->getIDom();
if (IDomNode == nullptr)
break;
InfluencedBB = IDomNode->getBlock();
}
}
void DivergencePropagator::findUsersOutsideInfluenceRegion(
Instruction &I, const DenseSet<BasicBlock *> &InfluenceRegion) {
for (User *U : I.users()) {
Instruction *UserInst = cast<Instruction>(U);
if (!InfluenceRegion.count(UserInst->getParent())) {
if (DV.insert(UserInst).second)
Worklist.push_back(UserInst);
}
}
}
static void
addSuccessorsToInfluenceRegion(BasicBlock *ThisBB, BasicBlock *End,
DenseSet<BasicBlock *> &InfluenceRegion,
std::vector<BasicBlock *> &InfluenceStack) {
for (BasicBlock *Succ : successors(ThisBB)) {
if (Succ != End && InfluenceRegion.insert(Succ).second)
InfluenceStack.push_back(Succ);
}
}
void DivergencePropagator::computeInfluenceRegion(
BasicBlock *Start, BasicBlock *End,
DenseSet<BasicBlock *> &InfluenceRegion) {
assert(PDT.properlyDominates(End, Start) &&
"End does not properly dominate Start");
std::vector<BasicBlock *> InfluenceStack;
addSuccessorsToInfluenceRegion(Start, End, InfluenceRegion, InfluenceStack);
while (!InfluenceStack.empty()) {
BasicBlock *BB = InfluenceStack.back();
InfluenceStack.pop_back();
addSuccessorsToInfluenceRegion(BB, End, InfluenceRegion, InfluenceStack);
}
}
void DivergencePropagator::exploreDataDependency(Value *V) {
for (User *U : V->users()) {
Instruction *UserInst = cast<Instruction>(U);
if (DV.insert(UserInst).second)
Worklist.push_back(UserInst);
}
}
void DivergencePropagator::propagate() {
while (!Worklist.empty()) {
Value *V = Worklist.back();
Worklist.pop_back();
if (TerminatorInst *TI = dyn_cast<TerminatorInst>(V)) {
if (TI->getNumSuccessors() > 1)
exploreSyncDependency(TI);
}
exploreDataDependency(V);
}
}
}
char DivergenceAnalysis::ID = 0;
INITIALIZE_PASS_BEGIN(DivergenceAnalysis, "divergence", "Divergence Analysis",
false, true)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
INITIALIZE_PASS_END(DivergenceAnalysis, "divergence", "Divergence Analysis",
false, true)
FunctionPass *llvm::createDivergenceAnalysisPass() {
return new DivergenceAnalysis();
}
void DivergenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<DominatorTreeWrapperPass>();
AU.addRequired<PostDominatorTree>();
AU.setPreservesAll();
}
bool DivergenceAnalysis::runOnFunction(Function &F) {
auto *TTIWP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>();
if (TTIWP == nullptr)
return false;
TargetTransformInfo &TTI = TTIWP->getTTI(F);
if (!TTI.hasBranchDivergence())
return false;
DivergentValues.clear();
DivergencePropagator DP(F, TTI,
getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
getAnalysis<PostDominatorTree>(), DivergentValues);
DP.populateWithSourcesOfDivergence();
DP.propagate();
return false;
}
void DivergenceAnalysis::print(raw_ostream &OS, const Module *) const {
if (DivergentValues.empty())
return;
const Value *FirstDivergentValue = *DivergentValues.begin();
const Function *F;
if (const Argument *Arg = dyn_cast<Argument>(FirstDivergentValue)) {
F = Arg->getParent();
} else if (const Instruction *I =
dyn_cast<Instruction>(FirstDivergentValue)) {
F = I->getParent()->getParent();
} else {
llvm_unreachable("Only arguments and instructions can be divergent");
}
for (auto &Arg : F->args()) {
if (DivergentValues.count(&Arg))
OS << "DIVERGENT: " << Arg << "\n";
}
for (auto &I : instructions(F)) {
if (DivergentValues.count(&I))
OS << "DIVERGENT:" << I << "\n";
}
}