Line data Source code
1 : //===- SIAnnotateControlFlow.cpp ------------------------------------------===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : /// \file
11 : /// Annotates the control flow with hardware specific intrinsics.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #include "AMDGPU.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/Transforms/Utils/Local.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 <cassert>
42 : #include <utility>
43 :
44 : using namespace llvm;
45 :
46 : #define DEBUG_TYPE "si-annotate-control-flow"
47 :
48 : namespace {
49 :
50 : // Complex types used in this pass
51 : using StackEntry = std::pair<BasicBlock *, Value *>;
52 : using StackVector = SmallVector<StackEntry, 16>;
53 :
54 : class SIAnnotateControlFlow : public FunctionPass {
55 : LegacyDivergenceAnalysis *DA;
56 :
57 : Type *Boolean;
58 : Type *Void;
59 : Type *Int64;
60 : Type *ReturnStruct;
61 :
62 : ConstantInt *BoolTrue;
63 : ConstantInt *BoolFalse;
64 : UndefValue *BoolUndef;
65 : Constant *Int64Zero;
66 :
67 : Function *If;
68 : Function *Else;
69 : Function *Break;
70 : Function *IfBreak;
71 : Function *ElseBreak;
72 : Function *Loop;
73 : Function *EndCf;
74 :
75 : DominatorTree *DT;
76 : StackVector Stack;
77 :
78 : LoopInfo *LI;
79 :
80 : bool isUniform(BranchInst *T);
81 :
82 : bool isTopOfStack(BasicBlock *BB);
83 :
84 : Value *popSaved();
85 :
86 : void push(BasicBlock *BB, Value *Saved);
87 :
88 : bool isElse(PHINode *Phi);
89 :
90 : void eraseIfUnused(PHINode *Phi);
91 :
92 : void openIf(BranchInst *Term);
93 :
94 : void insertElse(BranchInst *Term);
95 :
96 : Value *
97 : handleLoopCondition(Value *Cond, PHINode *Broken, llvm::Loop *L,
98 : BranchInst *Term,
99 : SmallVectorImpl<WeakTrackingVH> &LoopPhiConditions);
100 :
101 : void handleLoop(BranchInst *Term);
102 :
103 : void closeControlFlow(BasicBlock *BB);
104 :
105 : public:
106 : static char ID;
107 :
108 3940 : SIAnnotateControlFlow() : FunctionPass(ID) {}
109 :
110 : bool doInitialization(Module &M) override;
111 :
112 : bool runOnFunction(Function &F) override;
113 :
114 1 : StringRef getPassName() const override { return "SI annotate control flow"; }
115 :
116 1960 : void getAnalysisUsage(AnalysisUsage &AU) const override {
117 : AU.addRequired<LoopInfoWrapperPass>();
118 : AU.addRequired<DominatorTreeWrapperPass>();
119 : AU.addRequired<LegacyDivergenceAnalysis>();
120 : AU.addPreserved<DominatorTreeWrapperPass>();
121 1960 : FunctionPass::getAnalysisUsage(AU);
122 1960 : }
123 : };
124 :
125 : } // end anonymous namespace
126 :
127 85105 : INITIALIZE_PASS_BEGIN(SIAnnotateControlFlow, DEBUG_TYPE,
128 : "Annotate SI Control Flow", false, false)
129 85105 : INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
130 85105 : INITIALIZE_PASS_DEPENDENCY(LegacyDivergenceAnalysis)
131 199024 : 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 1959 : bool SIAnnotateControlFlow::doInitialization(Module &M) {
138 1959 : LLVMContext &Context = M.getContext();
139 :
140 1959 : Void = Type::getVoidTy(Context);
141 1959 : Boolean = Type::getInt1Ty(Context);
142 1959 : Int64 = Type::getInt64Ty(Context);
143 1959 : ReturnStruct = StructType::get(Boolean, Int64);
144 :
145 1959 : BoolTrue = ConstantInt::getTrue(Context);
146 1959 : BoolFalse = ConstantInt::getFalse(Context);
147 1959 : BoolUndef = UndefValue::get(Boolean);
148 1959 : Int64Zero = ConstantInt::get(Int64, 0);
149 :
150 1959 : If = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_if);
151 1959 : Else = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_else);
152 1959 : Break = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_break);
153 1959 : IfBreak = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_if_break);
154 1959 : ElseBreak = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_else_break);
155 1959 : Loop = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_loop);
156 1959 : EndCf = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_end_cf);
157 1959 : return false;
158 : }
159 :
160 : /// Is the branch condition uniform or did the StructurizeCFG pass
161 : /// consider it as such?
162 0 : bool SIAnnotateControlFlow::isUniform(BranchInst *T) {
163 0 : return DA->isUniform(T->getCondition()) ||
164 0 : T->getMetadata("structurizecfg.uniform") != nullptr;
165 : }
166 :
167 : /// Is BB the last block saved on the stack ?
168 : bool SIAnnotateControlFlow::isTopOfStack(BasicBlock *BB) {
169 22472 : return !Stack.empty() && Stack.back().first == BB;
170 : }
171 :
172 : /// Pop the last saved value from the control flow stack
173 : Value *SIAnnotateControlFlow::popSaved() {
174 : return Stack.pop_back_val().second;
175 : }
176 :
177 : /// Push a BB and saved value to the control flow stack
178 : void SIAnnotateControlFlow::push(BasicBlock *BB, Value *Saved) {
179 669 : Stack.push_back(std::make_pair(BB, Saved));
180 : }
181 :
182 : /// Can the condition represented by this PHI node treated like
183 : /// an "Else" block?
184 116 : bool SIAnnotateControlFlow::isElse(PHINode *Phi) {
185 232 : BasicBlock *IDom = DT->getNode(Phi->getParent())->getIDom()->getBlock();
186 280 : for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) {
187 215 : if (Phi->getIncomingBlock(i) == IDom) {
188 :
189 93 : if (Phi->getIncomingValue(i) != BoolTrue)
190 : return false;
191 :
192 : } else {
193 122 : if (Phi->getIncomingValue(i) != BoolFalse)
194 : return false;
195 :
196 : }
197 : }
198 : return true;
199 : }
200 :
201 : // Erase "Phi" if it is not used any more
202 0 : void SIAnnotateControlFlow::eraseIfUnused(PHINode *Phi) {
203 127 : if (RecursivelyDeleteDeadPHINode(Phi)) {
204 : LLVM_DEBUG(dbgs() << "Erased unused condition phi\n");
205 : }
206 0 : }
207 :
208 : /// Open a new "If" block
209 1049 : void SIAnnotateControlFlow::openIf(BranchInst *Term) {
210 1049 : if (isUniform(Term))
211 : return;
212 :
213 518 : Value *Ret = CallInst::Create(If, Term->getCondition(), "", Term);
214 1554 : Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term));
215 1554 : push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term));
216 : }
217 :
218 : /// Close the last "If" block and open a new "Else" block
219 65 : void SIAnnotateControlFlow::insertElse(BranchInst *Term) {
220 65 : if (isUniform(Term)) {
221 : return;
222 : }
223 65 : Value *Ret = CallInst::Create(Else, popSaved(), "", Term);
224 195 : Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term));
225 195 : push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term));
226 : }
227 :
228 : /// Recursively handle the condition leading to a loop
229 132 : Value *SIAnnotateControlFlow::handleLoopCondition(
230 : Value *Cond, PHINode *Broken, llvm::Loop *L, BranchInst *Term,
231 : SmallVectorImpl<WeakTrackingVH> &LoopPhiConditions) {
232 : // Only search through PHI nodes which are inside the loop. If we try this
233 : // with PHI nodes that are outside of the loop, we end up inserting new PHI
234 : // nodes outside of the loop which depend on values defined inside the loop.
235 : // This will break the module with
236 : // 'Instruction does not dominate all users!' errors.
237 : PHINode *Phi = nullptr;
238 67 : if ((Phi = dyn_cast<PHINode>(Cond)) && L->contains(Phi)) {
239 65 : BasicBlock *Parent = Phi->getParent();
240 130 : PHINode *NewPhi = PHINode::Create(Int64, 0, "loop.phi", &Parent->front());
241 : Value *Ret = NewPhi;
242 :
243 : // Handle all non-constant incoming values first
244 204 : for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) {
245 : Value *Incoming = Phi->getIncomingValue(i);
246 : BasicBlock *From = Phi->getIncomingBlock(i);
247 139 : if (isa<ConstantInt>(Incoming)) {
248 93 : NewPhi->addIncoming(Broken, From);
249 : continue;
250 : }
251 :
252 46 : Phi->setIncomingValue(i, BoolFalse);
253 46 : Value *PhiArg = handleLoopCondition(Incoming, Broken, L,
254 : Term, LoopPhiConditions);
255 46 : NewPhi->addIncoming(PhiArg, From);
256 : }
257 :
258 130 : BasicBlock *IDom = DT->getNode(Parent)->getIDom()->getBlock();
259 :
260 204 : for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) {
261 : Value *Incoming = Phi->getIncomingValue(i);
262 139 : if (Incoming != BoolTrue)
263 : continue;
264 :
265 : BasicBlock *From = Phi->getIncomingBlock(i);
266 52 : if (From == IDom) {
267 : // We're in the following situation:
268 : // IDom/From
269 : // | \
270 : // | If-block
271 : // | /
272 : // Parent
273 : // where we want to break out of the loop if the If-block is not taken.
274 : // Due to the depth-first traversal, there should be an end.cf
275 : // intrinsic in Parent, and we insert an else.break before it.
276 : //
277 : // Note that the end.cf need not be the first non-phi instruction
278 : // of parent, particularly when we're dealing with a multi-level
279 : // break, but it should occur within a group of intrinsic calls
280 : // at the beginning of the block.
281 : CallInst *OldEnd = dyn_cast<CallInst>(Parent->getFirstInsertionPt());
282 91 : while (OldEnd && OldEnd->getCalledFunction() != EndCf)
283 : OldEnd = dyn_cast<CallInst>(OldEnd->getNextNode());
284 87 : if (OldEnd && OldEnd->getCalledFunction() == EndCf) {
285 35 : Value *Args[] = { OldEnd->getArgOperand(0), NewPhi };
286 35 : Ret = CallInst::Create(ElseBreak, Args, "", OldEnd);
287 : continue;
288 : }
289 : }
290 :
291 : Instruction *Insert = From->getTerminator();
292 17 : Value *PhiArg = CallInst::Create(Break, Broken, "", Insert);
293 : NewPhi->setIncomingValue(i, PhiArg);
294 : }
295 :
296 130 : LoopPhiConditions.push_back(WeakTrackingVH(Phi));
297 65 : return Ret;
298 : }
299 :
300 : if (Instruction *Inst = dyn_cast<Instruction>(Cond)) {
301 63 : BasicBlock *Parent = Inst->getParent();
302 : Instruction *Insert;
303 63 : if (L->contains(Inst)) {
304 : Insert = Parent->getTerminator();
305 : } else {
306 : Insert = L->getHeader()->getFirstNonPHIOrDbgOrLifetime();
307 : }
308 :
309 63 : Value *Args[] = { Cond, Broken };
310 63 : return CallInst::Create(IfBreak, Args, "", Insert);
311 : }
312 :
313 : // Insert IfBreak in the loop header TERM for constant COND other than true.
314 4 : if (isa<Constant>(Cond)) {
315 4 : Instruction *Insert = Cond == BoolTrue ?
316 : Term : L->getHeader()->getTerminator();
317 :
318 4 : Value *Args[] = { Cond, Broken };
319 4 : return CallInst::Create(IfBreak, Args, "", Insert);
320 : }
321 :
322 0 : llvm_unreachable("Unhandled loop condition!");
323 : }
324 :
325 : /// Handle a back edge (loop)
326 164 : void SIAnnotateControlFlow::handleLoop(BranchInst *Term) {
327 164 : if (isUniform(Term))
328 78 : return;
329 :
330 88 : BasicBlock *BB = Term->getParent();
331 88 : llvm::Loop *L = LI->getLoopFor(BB);
332 86 : if (!L)
333 2 : return;
334 :
335 : BasicBlock *Target = Term->getSuccessor(1);
336 172 : PHINode *Broken = PHINode::Create(Int64, 0, "phi.broken", &Target->front());
337 :
338 86 : SmallVector<WeakTrackingVH, 8> LoopPhiConditions;
339 : Value *Cond = Term->getCondition();
340 86 : Term->setCondition(BoolTrue);
341 86 : Value *Arg = handleLoopCondition(Cond, Broken, L, Term, LoopPhiConditions);
342 :
343 263 : for (BasicBlock *Pred : predecessors(Target))
344 177 : Broken->addIncoming(Pred == BB ? Arg : Int64Zero, Pred);
345 :
346 86 : Term->setCondition(CallInst::Create(Loop, Arg, "", Term));
347 :
348 151 : for (WeakTrackingVH Val : llvm::reverse(LoopPhiConditions)) {
349 : if (PHINode *Cond = cast_or_null<PHINode>(Val))
350 : eraseIfUnused(Cond);
351 : }
352 :
353 86 : push(Term->getSuccessor(0), Arg);
354 : }
355 :
356 : /// Close the last opened control flow
357 604 : void SIAnnotateControlFlow::closeControlFlow(BasicBlock *BB) {
358 604 : llvm::Loop *L = LI->getLoopFor(BB);
359 :
360 : assert(Stack.back().first == BB);
361 :
362 52 : if (L && L->getHeader() == BB) {
363 : // We can't insert an EndCF call into a loop header, because it will
364 : // get executed on every iteration of the loop, when it should be
365 : // executed only once before the loop.
366 : SmallVector <BasicBlock *, 8> Latches;
367 0 : L->getLoopLatches(Latches);
368 :
369 : SmallVector<BasicBlock *, 2> Preds;
370 0 : for (BasicBlock *Pred : predecessors(BB)) {
371 0 : if (!is_contained(Latches, Pred))
372 0 : Preds.push_back(Pred);
373 : }
374 :
375 0 : BB = SplitBlockPredecessors(BB, Preds, "endcf.split", DT, LI, nullptr,
376 : false);
377 : }
378 :
379 604 : Value *Exec = popSaved();
380 : Instruction *FirstInsertionPt = &*BB->getFirstInsertionPt();
381 1208 : if (!isa<UndefValue>(Exec) && !isa<UnreachableInst>(FirstInsertionPt))
382 599 : CallInst::Create(EndCf, Exec, "", FirstInsertionPt);
383 604 : }
384 :
385 : /// Annotate the control flow with intrinsics so the backend can
386 : /// recognize if/then/else and loops.
387 19798 : bool SIAnnotateControlFlow::runOnFunction(Function &F) {
388 19798 : DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
389 19798 : LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
390 19798 : DA = &getAnalysis<LegacyDivergenceAnalysis>();
391 :
392 19798 : for (df_iterator<BasicBlock *> I = df_begin(&F.getEntryBlock()),
393 42270 : E = df_end(&F.getEntryBlock()); I != E; ++I) {
394 22472 : BasicBlock *BB = *I;
395 : BranchInst *Term = dyn_cast<BranchInst>(BB->getTerminator());
396 :
397 2639 : if (!Term || Term->isUnconditional()) {
398 : if (isTopOfStack(BB))
399 490 : closeControlFlow(BB);
400 :
401 21194 : continue;
402 : }
403 :
404 1278 : if (I.nodeVisited(Term->getSuccessor(1))) {
405 : if (isTopOfStack(BB))
406 39 : closeControlFlow(BB);
407 :
408 164 : handleLoop(Term);
409 164 : continue;
410 : }
411 :
412 : if (isTopOfStack(BB)) {
413 : PHINode *Phi = dyn_cast<PHINode>(Term->getCondition());
414 124 : if (Phi && Phi->getParent() == BB && isElse(Phi)) {
415 65 : insertElse(Term);
416 : eraseIfUnused(Phi);
417 65 : continue;
418 : }
419 :
420 75 : closeControlFlow(BB);
421 : }
422 :
423 1049 : openIf(Term);
424 : }
425 :
426 19798 : if (!Stack.empty()) {
427 : // CFG was probably not structured.
428 0 : report_fatal_error("failed to annotate CFG");
429 : }
430 :
431 19798 : return true;
432 : }
433 :
434 : /// Create the annotation pass
435 1964 : FunctionPass *llvm::createSIAnnotateControlFlowPass() {
436 1964 : return new SIAnnotateControlFlow();
437 : }
|
