LLVM API Documentation

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