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/Analysis/Dominators.h"
18#include "llvm/IR/Module.h"
19#include "llvm/Pass.h"
20#include "llvm/Transforms/Utils/BasicBlockUtils.h"
21#include "llvm/Transforms/Utils/SSAUpdater.h"
22
23using namespace llvm;
24
25namespace {
26
27// Complex types used in this pass
28typedef std::pair<BasicBlock *, Value *> StackEntry;
29typedef SmallVector<StackEntry, 16> StackVector;
30
31// Intrinsic names the control flow is annotated with
32static const char *IfIntrinsic = "llvm.SI.if";
33static const char *ElseIntrinsic = "llvm.SI.else";
34static const char *BreakIntrinsic = "llvm.SI.break";
35static const char *IfBreakIntrinsic = "llvm.SI.if.break";
36static const char *ElseBreakIntrinsic = "llvm.SI.else.break";
37static const char *LoopIntrinsic = "llvm.SI.loop";
38static const char *EndCfIntrinsic = "llvm.SI.end.cf";
39
40class SIAnnotateControlFlow : public FunctionPass {
41
42  static char ID;
43
44  Type *Boolean;
45  Type *Void;
46  Type *Int64;
47  Type *ReturnStruct;
48
49  ConstantInt *BoolTrue;
50  ConstantInt *BoolFalse;
51  UndefValue *BoolUndef;
52  Constant *Int64Zero;
53
54  Constant *If;
55  Constant *Else;
56  Constant *Break;
57  Constant *IfBreak;
58  Constant *ElseBreak;
59  Constant *Loop;
60  Constant *EndCf;
61
62  DominatorTree *DT;
63  StackVector Stack;
64  SSAUpdater PhiInserter;
65
66  bool isTopOfStack(BasicBlock *BB);
67
68  Value *popSaved();
69
70  void push(BasicBlock *BB, Value *Saved);
71
72  bool isElse(PHINode *Phi);
73
74  void eraseIfUnused(PHINode *Phi);
75
76  void openIf(BranchInst *Term);
77
78  void insertElse(BranchInst *Term);
79
80  void handleLoopCondition(Value *Cond);
81
82  void handleLoop(BranchInst *Term);
83
84  void closeControlFlow(BasicBlock *BB);
85
86public:
87  SIAnnotateControlFlow():
88    FunctionPass(ID) { }
89
90  virtual bool doInitialization(Module &M);
91
92  virtual bool runOnFunction(Function &F);
93
94  virtual const char *getPassName() const {
95    return "SI annotate control flow";
96  }
97
98  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
99    AU.addRequired<DominatorTree>();
100    AU.addPreserved<DominatorTree>();
101    FunctionPass::getAnalysisUsage(AU);
102  }
103
104};
105
106} // end anonymous namespace
107
108char SIAnnotateControlFlow::ID = 0;
109
110/// \brief Initialize all the types and constants used in the pass
111bool SIAnnotateControlFlow::doInitialization(Module &M) {
112  LLVMContext &Context = M.getContext();
113
114  Void = Type::getVoidTy(Context);
115  Boolean = Type::getInt1Ty(Context);
116  Int64 = Type::getInt64Ty(Context);
117  ReturnStruct = StructType::get(Boolean, Int64, (Type *)0);
118
119  BoolTrue = ConstantInt::getTrue(Context);
120  BoolFalse = ConstantInt::getFalse(Context);
121  BoolUndef = UndefValue::get(Boolean);
122  Int64Zero = ConstantInt::get(Int64, 0);
123
124  If = M.getOrInsertFunction(
125    IfIntrinsic, ReturnStruct, Boolean, (Type *)0);
126
127  Else = M.getOrInsertFunction(
128    ElseIntrinsic, ReturnStruct, Int64, (Type *)0);
129
130  Break = M.getOrInsertFunction(
131    BreakIntrinsic, Int64, Int64, (Type *)0);
132
133  IfBreak = M.getOrInsertFunction(
134    IfBreakIntrinsic, Int64, Boolean, Int64, (Type *)0);
135
136  ElseBreak = M.getOrInsertFunction(
137    ElseBreakIntrinsic, Int64, Int64, Int64, (Type *)0);
138
139  Loop = M.getOrInsertFunction(
140    LoopIntrinsic, Boolean, Int64, (Type *)0);
141
142  EndCf = M.getOrInsertFunction(
143    EndCfIntrinsic, Void, Int64, (Type *)0);
144
145  return false;
146}
147
148/// \brief Is BB the last block saved on the stack ?
149bool SIAnnotateControlFlow::isTopOfStack(BasicBlock *BB) {
150  return !Stack.empty() && Stack.back().first == BB;
151}
152
153/// \brief Pop the last saved value from the control flow stack
154Value *SIAnnotateControlFlow::popSaved() {
155  return Stack.pop_back_val().second;
156}
157
158/// \brief Push a BB and saved value to the control flow stack
159void SIAnnotateControlFlow::push(BasicBlock *BB, Value *Saved) {
160  Stack.push_back(std::make_pair(BB, Saved));
161}
162
163/// \brief Can the condition represented by this PHI node treated like
164/// an "Else" block?
165bool SIAnnotateControlFlow::isElse(PHINode *Phi) {
166  BasicBlock *IDom = DT->getNode(Phi->getParent())->getIDom()->getBlock();
167  for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) {
168    if (Phi->getIncomingBlock(i) == IDom) {
169
170      if (Phi->getIncomingValue(i) != BoolTrue)
171        return false;
172
173    } else {
174      if (Phi->getIncomingValue(i) != BoolFalse)
175        return false;
176
177    }
178  }
179  return true;
180}
181
182// \brief Erase "Phi" if it is not used any more
183void SIAnnotateControlFlow::eraseIfUnused(PHINode *Phi) {
184  if (!Phi->hasNUsesOrMore(1))
185    Phi->eraseFromParent();
186}
187
188/// \brief Open a new "If" block
189void SIAnnotateControlFlow::openIf(BranchInst *Term) {
190  Value *Ret = CallInst::Create(If, Term->getCondition(), "", Term);
191  Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term));
192  push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term));
193}
194
195/// \brief Close the last "If" block and open a new "Else" block
196void SIAnnotateControlFlow::insertElse(BranchInst *Term) {
197  Value *Ret = CallInst::Create(Else, popSaved(), "", Term);
198  Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term));
199  push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term));
200}
201
202/// \brief Recursively handle the condition leading to a loop
203void SIAnnotateControlFlow::handleLoopCondition(Value *Cond) {
204  if (PHINode *Phi = dyn_cast<PHINode>(Cond)) {
205
206    // Handle all non constant incoming values first
207    for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) {
208      Value *Incoming = Phi->getIncomingValue(i);
209      if (isa<ConstantInt>(Incoming))
210        continue;
211
212      Phi->setIncomingValue(i, BoolFalse);
213      handleLoopCondition(Incoming);
214    }
215
216    BasicBlock *Parent = Phi->getParent();
217    BasicBlock *IDom = DT->getNode(Parent)->getIDom()->getBlock();
218
219    for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) {
220
221      Value *Incoming = Phi->getIncomingValue(i);
222      if (Incoming != BoolTrue)
223        continue;
224
225      BasicBlock *From = Phi->getIncomingBlock(i);
226      if (From == IDom) {
227        CallInst *OldEnd = dyn_cast<CallInst>(Parent->getFirstInsertionPt());
228        if (OldEnd && OldEnd->getCalledFunction() == EndCf) {
229          Value *Args[] = {
230            OldEnd->getArgOperand(0),
231            PhiInserter.GetValueAtEndOfBlock(Parent)
232          };
233          Value *Ret = CallInst::Create(ElseBreak, Args, "", OldEnd);
234          PhiInserter.AddAvailableValue(Parent, Ret);
235          continue;
236        }
237      }
238
239      TerminatorInst *Insert = From->getTerminator();
240      Value *Arg = PhiInserter.GetValueAtEndOfBlock(From);
241      Value *Ret = CallInst::Create(Break, Arg, "", Insert);
242      PhiInserter.AddAvailableValue(From, Ret);
243    }
244    eraseIfUnused(Phi);
245
246  } else if (Instruction *Inst = dyn_cast<Instruction>(Cond)) {
247    BasicBlock *Parent = Inst->getParent();
248    TerminatorInst *Insert = Parent->getTerminator();
249    Value *Args[] = { Cond, PhiInserter.GetValueAtEndOfBlock(Parent) };
250    Value *Ret = CallInst::Create(IfBreak, Args, "", Insert);
251    PhiInserter.AddAvailableValue(Parent, Ret);
252
253  } else {
254    assert(0 && "Unhandled loop condition!");
255  }
256}
257
258/// \brief Handle a back edge (loop)
259void SIAnnotateControlFlow::handleLoop(BranchInst *Term) {
260  BasicBlock *Target = Term->getSuccessor(1);
261  PHINode *Broken = PHINode::Create(Int64, 0, "", &Target->front());
262
263  PhiInserter.Initialize(Int64, "");
264  PhiInserter.AddAvailableValue(Target, Broken);
265
266  Value *Cond = Term->getCondition();
267  Term->setCondition(BoolTrue);
268  handleLoopCondition(Cond);
269
270  BasicBlock *BB = Term->getParent();
271  Value *Arg = PhiInserter.GetValueAtEndOfBlock(BB);
272  for (pred_iterator PI = pred_begin(Target), PE = pred_end(Target);
273       PI != PE; ++PI) {
274
275    Broken->addIncoming(*PI == BB ? Arg : Int64Zero, *PI);
276  }
277
278  Term->setCondition(CallInst::Create(Loop, Arg, "", Term));
279  push(Term->getSuccessor(0), Arg);
280}
281
282/// \brief Close the last opened control flow
283void SIAnnotateControlFlow::closeControlFlow(BasicBlock *BB) {
284  CallInst::Create(EndCf, popSaved(), "", BB->getFirstInsertionPt());
285}
286
287/// \brief Annotate the control flow with intrinsics so the backend can
288/// recognize if/then/else and loops.
289bool SIAnnotateControlFlow::runOnFunction(Function &F) {
290  DT = &getAnalysis<DominatorTree>();
291
292  for (df_iterator<BasicBlock *> I = df_begin(&F.getEntryBlock()),
293       E = df_end(&F.getEntryBlock()); I != E; ++I) {
294
295    BranchInst *Term = dyn_cast<BranchInst>((*I)->getTerminator());
296
297    if (!Term || Term->isUnconditional()) {
298      if (isTopOfStack(*I))
299        closeControlFlow(*I);
300      continue;
301    }
302
303    if (I.nodeVisited(Term->getSuccessor(1))) {
304      if (isTopOfStack(*I))
305        closeControlFlow(*I);
306      handleLoop(Term);
307      continue;
308    }
309
310    if (isTopOfStack(*I)) {
311      PHINode *Phi = dyn_cast<PHINode>(Term->getCondition());
312      if (Phi && Phi->getParent() == *I && isElse(Phi)) {
313        insertElse(Term);
314        eraseIfUnused(Phi);
315        continue;
316      }
317      closeControlFlow(*I);
318    }
319    openIf(Term);
320  }
321
322  assert(Stack.empty());
323  return true;
324}
325
326/// \brief Create the annotation pass
327FunctionPass *llvm::createSIAnnotateControlFlowPass() {
328  return new SIAnnotateControlFlow();
329}
330