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