SIAnnotateControlFlow.cpp revision cd81d94322a39503e4a3e87b6ee03d4fcb3465fb 
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/IR/Constants.h"
18#include "llvm/IR/Dominators.h"
19#include "llvm/IR/Instructions.h"
20#include "llvm/IR/Module.h"
21#include "llvm/Pass.h"
22#include "llvm/Transforms/Utils/BasicBlockUtils.h"
23#include "llvm/Transforms/Utils/SSAUpdater.h"
24
25using namespace llvm;
26
27#define DEBUG_TYPE "si-annotate-control-flow"
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
69  bool isTopOfStack(BasicBlock *BB);
70
71  Value *popSaved();
72
73  void push(BasicBlock *BB, Value *Saved);
74
75  bool isElse(PHINode *Phi);
76
77  void eraseIfUnused(PHINode *Phi);
78
79  void openIf(BranchInst *Term);
80
81  void insertElse(BranchInst *Term);
82
83  Value *handleLoopCondition(Value *Cond, PHINode *Broken);
84
85  void handleLoop(BranchInst *Term);
86
87  void closeControlFlow(BasicBlock *BB);
88
89public:
90  SIAnnotateControlFlow():
91    FunctionPass(ID) { }
92
93  bool doInitialization(Module &M) override;
94
95  bool runOnFunction(Function &F) override;
96
97  const char *getPassName() const override {
98    return "SI annotate control flow";
99  }
100
101  void getAnalysisUsage(AnalysisUsage &AU) const override {
102    AU.addRequired<DominatorTreeWrapperPass>();
103    AU.addPreserved<DominatorTreeWrapperPass>();
104    FunctionPass::getAnalysisUsage(AU);
105  }
106
107};
108
109} // end anonymous namespace
110
111char SIAnnotateControlFlow::ID = 0;
112
113/// \brief Initialize all the types and constants used in the pass
114bool SIAnnotateControlFlow::doInitialization(Module &M) {
115  LLVMContext &Context = M.getContext();
116
117  Void = Type::getVoidTy(Context);
118  Boolean = Type::getInt1Ty(Context);
119  Int64 = Type::getInt64Ty(Context);
120  ReturnStruct = StructType::get(Boolean, Int64, (Type *)nullptr);
121
122  BoolTrue = ConstantInt::getTrue(Context);
123  BoolFalse = ConstantInt::getFalse(Context);
124  BoolUndef = UndefValue::get(Boolean);
125  Int64Zero = ConstantInt::get(Int64, 0);
126
127  If = M.getOrInsertFunction(
128    IfIntrinsic, ReturnStruct, Boolean, (Type *)nullptr);
129
130  Else = M.getOrInsertFunction(
131    ElseIntrinsic, ReturnStruct, Int64, (Type *)nullptr);
132
133  Break = M.getOrInsertFunction(
134    BreakIntrinsic, Int64, Int64, (Type *)nullptr);
135
136  IfBreak = M.getOrInsertFunction(
137    IfBreakIntrinsic, Int64, Boolean, Int64, (Type *)nullptr);
138
139  ElseBreak = M.getOrInsertFunction(
140    ElseBreakIntrinsic, Int64, Int64, Int64, (Type *)nullptr);
141
142  Loop = M.getOrInsertFunction(
143    LoopIntrinsic, Boolean, Int64, (Type *)nullptr);
144
145  EndCf = M.getOrInsertFunction(
146    EndCfIntrinsic, Void, Int64, (Type *)nullptr);
147
148  return false;
149}
150
151/// \brief Is BB the last block saved on the stack ?
152bool SIAnnotateControlFlow::isTopOfStack(BasicBlock *BB) {
153  return !Stack.empty() && Stack.back().first == BB;
154}
155
156/// \brief Pop the last saved value from the control flow stack
157Value *SIAnnotateControlFlow::popSaved() {
158  return Stack.pop_back_val().second;
159}
160
161/// \brief Push a BB and saved value to the control flow stack
162void SIAnnotateControlFlow::push(BasicBlock *BB, Value *Saved) {
163  Stack.push_back(std::make_pair(BB, Saved));
164}
165
166/// \brief Can the condition represented by this PHI node treated like
167/// an "Else" block?
168bool SIAnnotateControlFlow::isElse(PHINode *Phi) {
169  BasicBlock *IDom = DT->getNode(Phi->getParent())->getIDom()->getBlock();
170  for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) {
171    if (Phi->getIncomingBlock(i) == IDom) {
172
173      if (Phi->getIncomingValue(i) != BoolTrue)
174        return false;
175
176    } else {
177      if (Phi->getIncomingValue(i) != BoolFalse)
178        return false;
179
180    }
181  }
182  return true;
183}
184
185// \brief Erase "Phi" if it is not used any more
186void SIAnnotateControlFlow::eraseIfUnused(PHINode *Phi) {
187  if (!Phi->hasNUsesOrMore(1))
188    Phi->eraseFromParent();
189}
190
191/// \brief Open a new "If" block
192void SIAnnotateControlFlow::openIf(BranchInst *Term) {
193  Value *Ret = CallInst::Create(If, Term->getCondition(), "", Term);
194  Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term));
195  push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term));
196}
197
198/// \brief Close the last "If" block and open a new "Else" block
199void SIAnnotateControlFlow::insertElse(BranchInst *Term) {
200  Value *Ret = CallInst::Create(Else, popSaved(), "", Term);
201  Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term));
202  push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term));
203}
204
205/// \brief Recursively handle the condition leading to a loop
206Value *SIAnnotateControlFlow::handleLoopCondition(Value *Cond, PHINode *Broken) {
207  if (PHINode *Phi = dyn_cast<PHINode>(Cond)) {
208    BasicBlock *Parent = Phi->getParent();
209    PHINode *NewPhi = PHINode::Create(Int64, 0, "", &Parent->front());
210    Value *Ret = NewPhi;
211
212    // Handle all non-constant incoming values first
213    for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) {
214      Value *Incoming = Phi->getIncomingValue(i);
215      BasicBlock *From = Phi->getIncomingBlock(i);
216      if (isa<ConstantInt>(Incoming)) {
217        NewPhi->addIncoming(Broken, From);
218        continue;
219      }
220
221      Phi->setIncomingValue(i, BoolFalse);
222      Value *PhiArg = handleLoopCondition(Incoming, Broken);
223      NewPhi->addIncoming(PhiArg, From);
224    }
225
226    BasicBlock *IDom = DT->getNode(Parent)->getIDom()->getBlock();
227
228    for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) {
229
230      Value *Incoming = Phi->getIncomingValue(i);
231      if (Incoming != BoolTrue)
232        continue;
233
234      BasicBlock *From = Phi->getIncomingBlock(i);
235      if (From == IDom) {
236        CallInst *OldEnd = dyn_cast<CallInst>(Parent->getFirstInsertionPt());
237        if (OldEnd && OldEnd->getCalledFunction() == EndCf) {
238          Value *Args[] = { OldEnd->getArgOperand(0), NewPhi };
239          Ret = CallInst::Create(ElseBreak, Args, "", OldEnd);
240          continue;
241        }
242      }
243      TerminatorInst *Insert = From->getTerminator();
244      Value *PhiArg = CallInst::Create(Break, Broken, "", Insert);
245      NewPhi->setIncomingValue(i, PhiArg);
246    }
247    eraseIfUnused(Phi);
248    return Ret;
249
250  } else if (Instruction *Inst = dyn_cast<Instruction>(Cond)) {
251    BasicBlock *Parent = Inst->getParent();
252    TerminatorInst *Insert = Parent->getTerminator();
253    Value *Args[] = { Cond, Broken };
254    return CallInst::Create(IfBreak, Args, "", Insert);
255
256  } else {
257    llvm_unreachable("Unhandled loop condition!");
258  }
259  return 0;
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  Value *Cond = Term->getCondition();
268  Term->setCondition(BoolTrue);
269  Value *Arg = handleLoopCondition(Cond, Broken);
270
271  BasicBlock *BB = Term->getParent();
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<DominatorTreeWrapperPass>().getDomTree();
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