/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/AMDGPU/SIAnnotateControlFlow.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- SIAnnotateControlFlow.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 | | /// \file |
10 | | /// Annotates the control flow with hardware specific intrinsics. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #include "AMDGPU.h" |
15 | | #include "AMDGPUSubtarget.h" |
16 | | #include "llvm/ADT/DepthFirstIterator.h" |
17 | | #include "llvm/ADT/STLExtras.h" |
18 | | #include "llvm/ADT/SmallVector.h" |
19 | | #include "llvm/Analysis/LegacyDivergenceAnalysis.h" |
20 | | #include "llvm/Analysis/LoopInfo.h" |
21 | | #include "llvm/CodeGen/TargetPassConfig.h" |
22 | | #include "llvm/IR/BasicBlock.h" |
23 | | #include "llvm/IR/CFG.h" |
24 | | #include "llvm/IR/Constant.h" |
25 | | #include "llvm/IR/Constants.h" |
26 | | #include "llvm/IR/DerivedTypes.h" |
27 | | #include "llvm/IR/Dominators.h" |
28 | | #include "llvm/IR/Function.h" |
29 | | #include "llvm/IR/Instruction.h" |
30 | | #include "llvm/IR/Instructions.h" |
31 | | #include "llvm/IR/Intrinsics.h" |
32 | | #include "llvm/IR/Module.h" |
33 | | #include "llvm/IR/Type.h" |
34 | | #include "llvm/IR/ValueHandle.h" |
35 | | #include "llvm/Pass.h" |
36 | | #include "llvm/Support/Casting.h" |
37 | | #include "llvm/Support/Debug.h" |
38 | | #include "llvm/Support/ErrorHandling.h" |
39 | | #include "llvm/Support/raw_ostream.h" |
40 | | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
41 | | #include "llvm/Transforms/Utils/Local.h" |
42 | | #include <cassert> |
43 | | #include <utility> |
44 | | |
45 | | using namespace llvm; |
46 | | |
47 | | #define DEBUG_TYPE "si-annotate-control-flow" |
48 | | |
49 | | namespace { |
50 | | |
51 | | // Complex types used in this pass |
52 | | using StackEntry = std::pair<BasicBlock *, Value *>; |
53 | | using StackVector = SmallVector<StackEntry, 16>; |
54 | | |
55 | | class SIAnnotateControlFlow : public FunctionPass { |
56 | | LegacyDivergenceAnalysis *DA; |
57 | | |
58 | | Type *Boolean; |
59 | | Type *Void; |
60 | | Type *IntMask; |
61 | | Type *ReturnStruct; |
62 | | |
63 | | ConstantInt *BoolTrue; |
64 | | ConstantInt *BoolFalse; |
65 | | UndefValue *BoolUndef; |
66 | | Constant *IntMaskZero; |
67 | | |
68 | | Function *If; |
69 | | Function *Else; |
70 | | Function *IfBreak; |
71 | | Function *Loop; |
72 | | Function *EndCf; |
73 | | |
74 | | DominatorTree *DT; |
75 | | StackVector Stack; |
76 | | |
77 | | LoopInfo *LI; |
78 | | |
79 | | void initialize(Module &M, const GCNSubtarget &ST); |
80 | | |
81 | | bool isUniform(BranchInst *T); |
82 | | |
83 | | bool isTopOfStack(BasicBlock *BB); |
84 | | |
85 | | Value *popSaved(); |
86 | | |
87 | | void push(BasicBlock *BB, Value *Saved); |
88 | | |
89 | | bool isElse(PHINode *Phi); |
90 | | |
91 | | void eraseIfUnused(PHINode *Phi); |
92 | | |
93 | | void openIf(BranchInst *Term); |
94 | | |
95 | | void insertElse(BranchInst *Term); |
96 | | |
97 | | Value * |
98 | | handleLoopCondition(Value *Cond, PHINode *Broken, llvm::Loop *L, |
99 | | BranchInst *Term); |
100 | | |
101 | | void handleLoop(BranchInst *Term); |
102 | | |
103 | | void closeControlFlow(BasicBlock *BB); |
104 | | |
105 | | public: |
106 | | static char ID; |
107 | | |
108 | 2.45k | SIAnnotateControlFlow() : FunctionPass(ID) {} |
109 | | |
110 | | bool runOnFunction(Function &F) override; |
111 | | |
112 | 25.6k | StringRef getPassName() const override { return "SI annotate control flow"; } |
113 | | |
114 | 2.43k | void getAnalysisUsage(AnalysisUsage &AU) const override { |
115 | 2.43k | AU.addRequired<LoopInfoWrapperPass>(); |
116 | 2.43k | AU.addRequired<DominatorTreeWrapperPass>(); |
117 | 2.43k | AU.addRequired<LegacyDivergenceAnalysis>(); |
118 | 2.43k | AU.addPreserved<DominatorTreeWrapperPass>(); |
119 | 2.43k | AU.addRequired<TargetPassConfig>(); |
120 | 2.43k | FunctionPass::getAnalysisUsage(AU); |
121 | 2.43k | } |
122 | | }; |
123 | | |
124 | | } // end anonymous namespace |
125 | | |
126 | 101k | INITIALIZE_PASS_BEGIN(SIAnnotateControlFlow, DEBUG_TYPE, |
127 | 101k | "Annotate SI Control Flow", false, false) |
128 | 101k | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
129 | 101k | INITIALIZE_PASS_DEPENDENCY(LegacyDivergenceAnalysis) |
130 | 101k | INITIALIZE_PASS_DEPENDENCY(TargetPassConfig) |
131 | 101k | INITIALIZE_PASS_END(SIAnnotateControlFlow, DEBUG_TYPE, |
132 | | "Annotate SI Control Flow", false, false) |
133 | | |
134 | | char SIAnnotateControlFlow::ID = 0; |
135 | | |
136 | | /// Initialize all the types and constants used in the pass |
137 | 25.6k | void SIAnnotateControlFlow::initialize(Module &M, const GCNSubtarget &ST) { |
138 | 25.6k | LLVMContext &Context = M.getContext(); |
139 | 25.6k | |
140 | 25.6k | Void = Type::getVoidTy(Context); |
141 | 25.6k | Boolean = Type::getInt1Ty(Context); |
142 | 25.6k | IntMask = ST.isWave32() ? Type::getInt32Ty(Context)1.92k |
143 | 25.6k | : Type::getInt64Ty(Context)23.7k ; |
144 | 25.6k | ReturnStruct = StructType::get(Boolean, IntMask); |
145 | 25.6k | |
146 | 25.6k | BoolTrue = ConstantInt::getTrue(Context); |
147 | 25.6k | BoolFalse = ConstantInt::getFalse(Context); |
148 | 25.6k | BoolUndef = UndefValue::get(Boolean); |
149 | 25.6k | IntMaskZero = ConstantInt::get(IntMask, 0); |
150 | 25.6k | |
151 | 25.6k | If = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_if, { IntMask }); |
152 | 25.6k | Else = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_else, |
153 | 25.6k | { IntMask, IntMask }); |
154 | 25.6k | IfBreak = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_if_break, |
155 | 25.6k | { IntMask, IntMask }); |
156 | 25.6k | Loop = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_loop, { IntMask }); |
157 | 25.6k | EndCf = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_end_cf, { IntMask }); |
158 | 25.6k | } |
159 | | |
160 | | /// Is the branch condition uniform or did the StructurizeCFG pass |
161 | | /// consider it as such? |
162 | 1.62k | bool SIAnnotateControlFlow::isUniform(BranchInst *T) { |
163 | 1.62k | return DA->isUniform(T) || |
164 | 1.62k | T->getMetadata("structurizecfg.uniform") != nullptr896 ; |
165 | 1.62k | } |
166 | | |
167 | | /// Is BB the last block saved on the stack ? |
168 | 29.1k | bool SIAnnotateControlFlow::isTopOfStack(BasicBlock *BB) { |
169 | 29.1k | return !Stack.empty() && Stack.back().first == BB1.70k ; |
170 | 29.1k | } |
171 | | |
172 | | /// Pop the last saved value from the control flow stack |
173 | 894 | Value *SIAnnotateControlFlow::popSaved() { |
174 | 894 | return Stack.pop_back_val().second; |
175 | 894 | } |
176 | | |
177 | | /// Push a BB and saved value to the control flow stack |
178 | 894 | void SIAnnotateControlFlow::push(BasicBlock *BB, Value *Saved) { |
179 | 894 | Stack.push_back(std::make_pair(BB, Saved)); |
180 | 894 | } |
181 | | |
182 | | /// Can the condition represented by this PHI node treated like |
183 | | /// an "Else" block? |
184 | 138 | bool SIAnnotateControlFlow::isElse(PHINode *Phi) { |
185 | 138 | BasicBlock *IDom = DT->getNode(Phi->getParent())->getIDom()->getBlock(); |
186 | 331 | for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i193 ) { |
187 | 254 | if (Phi->getIncomingBlock(i) == IDom) { |
188 | 110 | |
189 | 110 | if (Phi->getIncomingValue(i) != BoolTrue) |
190 | 33 | return false; |
191 | 144 | |
192 | 144 | } else { |
193 | 144 | if (Phi->getIncomingValue(i) != BoolFalse) |
194 | 28 | return false; |
195 | 144 | |
196 | 144 | } |
197 | 254 | } |
198 | 138 | return true77 ; |
199 | 138 | } |
200 | | |
201 | | // Erase "Phi" if it is not used any more |
202 | 77 | void SIAnnotateControlFlow::eraseIfUnused(PHINode *Phi) { |
203 | 77 | if (RecursivelyDeleteDeadPHINode(Phi)) { |
204 | 77 | LLVM_DEBUG(dbgs() << "Erased unused condition phi\n"); |
205 | 77 | } |
206 | 77 | } |
207 | | |
208 | | /// Open a new "If" block |
209 | 1.30k | void SIAnnotateControlFlow::openIf(BranchInst *Term) { |
210 | 1.30k | if (isUniform(Term)) |
211 | 643 | return; |
212 | 665 | |
213 | 665 | Value *Ret = CallInst::Create(If, Term->getCondition(), "", Term); |
214 | 665 | Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term)); |
215 | 665 | push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term)); |
216 | 665 | } |
217 | | |
218 | | /// Close the last "If" block and open a new "Else" block |
219 | 77 | void SIAnnotateControlFlow::insertElse(BranchInst *Term) { |
220 | 77 | if (isUniform(Term)) { |
221 | 0 | return; |
222 | 0 | } |
223 | 77 | Value *Ret = CallInst::Create(Else, popSaved(), "", Term); |
224 | 77 | Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term)); |
225 | 77 | push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term)); |
226 | 77 | } |
227 | | |
228 | | /// Recursively handle the condition leading to a loop |
229 | | Value *SIAnnotateControlFlow::handleLoopCondition( |
230 | 152 | Value *Cond, PHINode *Broken, llvm::Loop *L, BranchInst *Term) { |
231 | 152 | if (Instruction *Inst = dyn_cast<Instruction>(Cond)) { |
232 | 152 | BasicBlock *Parent = Inst->getParent(); |
233 | 152 | Instruction *Insert; |
234 | 152 | if (L->contains(Inst)) { |
235 | 141 | Insert = Parent->getTerminator(); |
236 | 141 | } else { |
237 | 11 | Insert = L->getHeader()->getFirstNonPHIOrDbgOrLifetime(); |
238 | 11 | } |
239 | 152 | |
240 | 152 | Value *Args[] = { Cond, Broken }; |
241 | 152 | return CallInst::Create(IfBreak, Args, "", Insert); |
242 | 152 | } |
243 | 0 | |
244 | 0 | // Insert IfBreak in the loop header TERM for constant COND other than true. |
245 | 0 | if (isa<Constant>(Cond)) { |
246 | 0 | Instruction *Insert = Cond == BoolTrue ? |
247 | 0 | Term : L->getHeader()->getTerminator(); |
248 | 0 |
|
249 | 0 | Value *Args[] = { Cond, Broken }; |
250 | 0 | return CallInst::Create(IfBreak, Args, "", Insert); |
251 | 0 | } |
252 | 0 |
|
253 | 0 | llvm_unreachable("Unhandled loop condition!"); |
254 | 0 | } |
255 | | |
256 | | /// Handle a back edge (loop) |
257 | 241 | void SIAnnotateControlFlow::handleLoop(BranchInst *Term) { |
258 | 241 | if (isUniform(Term)) |
259 | 87 | return; |
260 | 154 | |
261 | 154 | BasicBlock *BB = Term->getParent(); |
262 | 154 | llvm::Loop *L = LI->getLoopFor(BB); |
263 | 154 | if (!L) |
264 | 2 | return; |
265 | 152 | |
266 | 152 | BasicBlock *Target = Term->getSuccessor(1); |
267 | 152 | PHINode *Broken = PHINode::Create(IntMask, 0, "phi.broken", &Target->front()); |
268 | 152 | |
269 | 152 | Value *Cond = Term->getCondition(); |
270 | 152 | Term->setCondition(BoolTrue); |
271 | 152 | Value *Arg = handleLoopCondition(Cond, Broken, L, Term); |
272 | 152 | |
273 | 310 | for (BasicBlock *Pred : predecessors(Target)) { |
274 | 310 | Value *PHIValue = IntMaskZero; |
275 | 310 | if (Pred == BB) // Remember the value of the previous iteration. |
276 | 152 | PHIValue = Arg; |
277 | 158 | // If the backedge from Pred to Target could be executed before the exit |
278 | 158 | // of the loop at BB, it should not reset or change "Broken", which keeps |
279 | 158 | // track of the number of threads exited the loop at BB. |
280 | 158 | else if (L->contains(Pred) && DT->dominates(Pred, BB)6 ) |
281 | 3 | PHIValue = Broken; |
282 | 310 | Broken->addIncoming(PHIValue, Pred); |
283 | 310 | } |
284 | 152 | |
285 | 152 | Term->setCondition(CallInst::Create(Loop, Arg, "", Term)); |
286 | 152 | |
287 | 152 | push(Term->getSuccessor(0), Arg); |
288 | 152 | } |
289 | | |
290 | | /// Close the last opened control flow |
291 | 817 | void SIAnnotateControlFlow::closeControlFlow(BasicBlock *BB) { |
292 | 817 | llvm::Loop *L = LI->getLoopFor(BB); |
293 | 817 | |
294 | 817 | assert(Stack.back().first == BB); |
295 | 817 | |
296 | 817 | if (L && L->getHeader() == BB77 ) { |
297 | 0 | // We can't insert an EndCF call into a loop header, because it will |
298 | 0 | // get executed on every iteration of the loop, when it should be |
299 | 0 | // executed only once before the loop. |
300 | 0 | SmallVector <BasicBlock *, 8> Latches; |
301 | 0 | L->getLoopLatches(Latches); |
302 | 0 |
|
303 | 0 | SmallVector<BasicBlock *, 2> Preds; |
304 | 0 | for (BasicBlock *Pred : predecessors(BB)) { |
305 | 0 | if (!is_contained(Latches, Pred)) |
306 | 0 | Preds.push_back(Pred); |
307 | 0 | } |
308 | 0 |
|
309 | 0 | BB = SplitBlockPredecessors(BB, Preds, "endcf.split", DT, LI, nullptr, |
310 | 0 | false); |
311 | 0 | } |
312 | 817 | |
313 | 817 | Value *Exec = popSaved(); |
314 | 817 | Instruction *FirstInsertionPt = &*BB->getFirstInsertionPt(); |
315 | 817 | if (!isa<UndefValue>(Exec) && !isa<UnreachableInst>(FirstInsertionPt)) |
316 | 810 | CallInst::Create(EndCf, Exec, "", FirstInsertionPt); |
317 | 817 | } |
318 | | |
319 | | /// Annotate the control flow with intrinsics so the backend can |
320 | | /// recognize if/then/else and loops. |
321 | 25.6k | bool SIAnnotateControlFlow::runOnFunction(Function &F) { |
322 | 25.6k | DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
323 | 25.6k | LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); |
324 | 25.6k | DA = &getAnalysis<LegacyDivergenceAnalysis>(); |
325 | 25.6k | TargetPassConfig &TPC = getAnalysis<TargetPassConfig>(); |
326 | 25.6k | const TargetMachine &TM = TPC.getTM<TargetMachine>(); |
327 | 25.6k | |
328 | 25.6k | initialize(*F.getParent(), TM.getSubtarget<GCNSubtarget>(F)); |
329 | 25.6k | |
330 | 25.6k | for (df_iterator<BasicBlock *> I = df_begin(&F.getEntryBlock()), |
331 | 54.8k | E = df_end(&F.getEntryBlock()); I != E; ++I29.1k ) { |
332 | 29.1k | BasicBlock *BB = *I; |
333 | 29.1k | BranchInst *Term = dyn_cast<BranchInst>(BB->getTerminator()); |
334 | 29.1k | |
335 | 29.1k | if (!Term || Term->isUnconditional()3.39k ) { |
336 | 27.4k | if (isTopOfStack(BB)) |
337 | 681 | closeControlFlow(BB); |
338 | 27.4k | |
339 | 27.4k | continue; |
340 | 27.4k | } |
341 | 1.62k | |
342 | 1.62k | if (I.nodeVisited(Term->getSuccessor(1))) { |
343 | 241 | if (isTopOfStack(BB)) |
344 | 48 | closeControlFlow(BB); |
345 | 241 | |
346 | 241 | handleLoop(Term); |
347 | 241 | continue; |
348 | 241 | } |
349 | 1.38k | |
350 | 1.38k | if (isTopOfStack(BB)) { |
351 | 165 | PHINode *Phi = dyn_cast<PHINode>(Term->getCondition()); |
352 | 165 | if (Phi && Phi->getParent() == BB148 && isElse(Phi)138 ) { |
353 | 77 | insertElse(Term); |
354 | 77 | eraseIfUnused(Phi); |
355 | 77 | continue; |
356 | 77 | } |
357 | 88 | |
358 | 88 | closeControlFlow(BB); |
359 | 88 | } |
360 | 1.38k | |
361 | 1.38k | openIf(Term); |
362 | 1.30k | } |
363 | 25.6k | |
364 | 25.6k | if (!Stack.empty()) { |
365 | 0 | // CFG was probably not structured. |
366 | 0 | report_fatal_error("failed to annotate CFG"); |
367 | 0 | } |
368 | 25.6k | |
369 | 25.6k | return true; |
370 | 25.6k | } |
371 | | |
372 | | /// Create the annotation pass |
373 | 2.44k | FunctionPass *llvm::createSIAnnotateControlFlowPass() { |
374 | 2.44k | return new SIAnnotateControlFlow(); |
375 | 2.44k | } |