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