Mercurial > hg > CbC > CbC_llvm

comparison lib/Analysis/DivergenceAnalysis.cpp @ 120:1172e4bd9c6f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update 4.0.0
author mir3636
date Fri, 25 Nov 2016 19:14:25 +0900
parents 7d135dc70f03
children 803732b1fca8
comparison
equal deleted inserted replaced
101:34baf5011add 120:1172e4bd9c6f
71 #include "llvm/IR/Dominators.h" 71 #include "llvm/IR/Dominators.h"
72 #include "llvm/IR/InstIterator.h" 72 #include "llvm/IR/InstIterator.h"
73 #include "llvm/IR/Instructions.h" 73 #include "llvm/IR/Instructions.h"
74 #include "llvm/IR/IntrinsicInst.h" 74 #include "llvm/IR/IntrinsicInst.h"
75 #include "llvm/IR/Value.h" 75 #include "llvm/IR/Value.h"
76 #include "llvm/Support/CommandLine.h"
77 #include "llvm/Support/Debug.h" 76 #include "llvm/Support/Debug.h"
78 #include "llvm/Support/raw_ostream.h" 77 #include "llvm/Support/raw_ostream.h"
79 #include "llvm/Transforms/Scalar.h"
80 #include <vector> 78 #include <vector>
81 using namespace llvm; 79 using namespace llvm;
82 80
83 namespace { 81 namespace {
84 82
138 // a1 = 1; 136 // a1 = 1;
139 // else 137 // else
140 // a2 = 2; 138 // a2 = 2;
141 // a = phi(a1, a2); // sync dependent on (tid < 5) 139 // a = phi(a1, a2); // sync dependent on (tid < 5)
142 BasicBlock *ThisBB = TI->getParent(); 140 BasicBlock *ThisBB = TI->getParent();
143 BasicBlock *IPostDom = PDT.getNode(ThisBB)->getIDom()->getBlock(); 141
142 // Unreachable blocks may not be in the dominator tree.
143 if (!DT.isReachableFromEntry(ThisBB))
144 return;
145
146 // If the function has no exit blocks or doesn't reach any exit blocks, the
147 // post dominator may be null.
148 DomTreeNode *ThisNode = PDT.getNode(ThisBB);
149 if (!ThisNode)
150 return;
151
152 BasicBlock *IPostDom = ThisNode->getIDom()->getBlock();
144 if (IPostDom == nullptr) 153 if (IPostDom == nullptr)
145 return; 154 return;
146 155
147 for (auto I = IPostDom->begin(); isa<PHINode>(I); ++I) { 156 for (auto I = IPostDom->begin(); isa<PHINode>(I); ++I) {
148 // A PHINode is uniform if it returns the same value no matter which path is 157 // A PHINode is uniform if it returns the same value no matter which path is
149 // taken. 158 // taken.
150 if (!cast<PHINode>(I)->hasConstantValue() && DV.insert(&*I).second) 159 if (!cast<PHINode>(I)->hasConstantOrUndefValue() && DV.insert(&*I).second)
151 Worklist.push_back(&*I); 160 Worklist.push_back(&*I);
152 } 161 }
153 162
154 // Propagation rule 2: if a value defined in a loop is used outside, the user 163 // Propagation rule 2: if a value defined in a loop is used outside, the user
155 // is sync dependent on the condition of the loop exits that dominate the 164 // is sync dependent on the condition of the loop exits that dominate the
257 // Register this pass. 266 // Register this pass.
258 char DivergenceAnalysis::ID = 0; 267 char DivergenceAnalysis::ID = 0;
259 INITIALIZE_PASS_BEGIN(DivergenceAnalysis, "divergence", "Divergence Analysis", 268 INITIALIZE_PASS_BEGIN(DivergenceAnalysis, "divergence", "Divergence Analysis",
260 false, true) 269 false, true)
261 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 270 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
262 INITIALIZE_PASS_DEPENDENCY(PostDominatorTree) 271 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
263 INITIALIZE_PASS_END(DivergenceAnalysis, "divergence", "Divergence Analysis", 272 INITIALIZE_PASS_END(DivergenceAnalysis, "divergence", "Divergence Analysis",
264 false, true) 273 false, true)
265 274
266 FunctionPass *llvm::createDivergenceAnalysisPass() { 275 FunctionPass *llvm::createDivergenceAnalysisPass() {
267 return new DivergenceAnalysis(); 276 return new DivergenceAnalysis();
268 } 277 }
269 278
270 void DivergenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 279 void DivergenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
271 AU.addRequired<DominatorTreeWrapperPass>(); 280 AU.addRequired<DominatorTreeWrapperPass>();
272 AU.addRequired<PostDominatorTree>(); 281 AU.addRequired<PostDominatorTreeWrapperPass>();
273 AU.setPreservesAll(); 282 AU.setPreservesAll();
274 } 283 }
275 284
276 bool DivergenceAnalysis::runOnFunction(Function &F) { 285 bool DivergenceAnalysis::runOnFunction(Function &F) {
277 auto *TTIWP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>(); 286 auto *TTIWP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>();
283 // any branch as divergent. 292 // any branch as divergent.
284 if (!TTI.hasBranchDivergence()) 293 if (!TTI.hasBranchDivergence())
285 return false; 294 return false;
286 295
287 DivergentValues.clear(); 296 DivergentValues.clear();
297 auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
288 DivergencePropagator DP(F, TTI, 298 DivergencePropagator DP(F, TTI,
289 getAnalysis<DominatorTreeWrapperPass>().getDomTree(), 299 getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
290 getAnalysis<PostDominatorTree>(), DivergentValues); 300 PDT, DivergentValues);
291 DP.populateWithSourcesOfDivergence(); 301 DP.populateWithSourcesOfDivergence();
292 DP.propagate(); 302 DP.propagate();
293 return false; 303 return false;
294 } 304 }
295 305