LLVM  9.0.0svn
SIAnnotateControlFlow.cpp
Go to the documentation of this file.
1 //===- SIAnnotateControlFlow.cpp ------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// \file
10 /// Annotates the control flow with hardware specific intrinsics.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "AMDGPU.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/Analysis/LoopInfo.h"
21 #include "llvm/IR/BasicBlock.h"
22 #include "llvm/IR/CFG.h"
23 #include "llvm/IR/Constant.h"
24 #include "llvm/IR/Constants.h"
25 #include "llvm/IR/DerivedTypes.h"
26 #include "llvm/IR/Dominators.h"
27 #include "llvm/IR/Function.h"
28 #include "llvm/IR/Instruction.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/Intrinsics.h"
31 #include "llvm/IR/Module.h"
32 #include "llvm/IR/Type.h"
33 #include "llvm/IR/ValueHandle.h"
34 #include "llvm/Pass.h"
35 #include "llvm/Support/Casting.h"
36 #include "llvm/Support/Debug.h"
40 #include <cassert>
41 #include <utility>
42 
43 using namespace llvm;
44 
45 #define DEBUG_TYPE "si-annotate-control-flow"
46 
47 namespace {
48 
49 // Complex types used in this pass
50 using StackEntry = std::pair<BasicBlock *, Value *>;
51 using StackVector = SmallVector<StackEntry, 16>;
52 
53 class SIAnnotateControlFlow : public FunctionPass {
55 
56  Type *Boolean;
57  Type *Void;
58  Type *Int64;
59  Type *ReturnStruct;
60 
61  ConstantInt *BoolTrue;
62  ConstantInt *BoolFalse;
63  UndefValue *BoolUndef;
64  Constant *Int64Zero;
65 
66  Function *If;
67  Function *Else;
68  Function *IfBreak;
69  Function *Loop;
70  Function *EndCf;
71 
72  DominatorTree *DT;
73  StackVector Stack;
74 
75  LoopInfo *LI;
76 
77  bool isUniform(BranchInst *T);
78 
79  bool isTopOfStack(BasicBlock *BB);
80 
81  Value *popSaved();
82 
83  void push(BasicBlock *BB, Value *Saved);
84 
85  bool isElse(PHINode *Phi);
86 
87  void eraseIfUnused(PHINode *Phi);
88 
89  void openIf(BranchInst *Term);
90 
91  void insertElse(BranchInst *Term);
92 
93  Value *
94  handleLoopCondition(Value *Cond, PHINode *Broken, llvm::Loop *L,
95  BranchInst *Term);
96 
97  void handleLoop(BranchInst *Term);
98 
99  void closeControlFlow(BasicBlock *BB);
100 
101 public:
102  static char ID;
103 
104  SIAnnotateControlFlow() : FunctionPass(ID) {}
105 
106  bool doInitialization(Module &M) override;
107 
108  bool runOnFunction(Function &F) override;
109 
110  StringRef getPassName() const override { return "SI annotate control flow"; }
111 
112  void getAnalysisUsage(AnalysisUsage &AU) const override {
118  }
119 };
120 
121 } // end anonymous namespace
122 
123 INITIALIZE_PASS_BEGIN(SIAnnotateControlFlow, DEBUG_TYPE,
124  "Annotate SI Control Flow", false, false)
127 INITIALIZE_PASS_END(SIAnnotateControlFlow, DEBUG_TYPE,
128  "Annotate SI Control Flow", false, false)
129 
130 char SIAnnotateControlFlow::ID = 0;
131 
132 /// Initialize all the types and constants used in the pass
133 bool SIAnnotateControlFlow::doInitialization(Module &M) {
134  LLVMContext &Context = M.getContext();
135 
136  Void = Type::getVoidTy(Context);
137  Boolean = Type::getInt1Ty(Context);
138  Int64 = Type::getInt64Ty(Context);
139  ReturnStruct = StructType::get(Boolean, Int64);
140 
141  BoolTrue = ConstantInt::getTrue(Context);
142  BoolFalse = ConstantInt::getFalse(Context);
143  BoolUndef = UndefValue::get(Boolean);
144  Int64Zero = ConstantInt::get(Int64, 0);
145 
146  If = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_if);
147  Else = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_else);
148  IfBreak = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_if_break);
149  Loop = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_loop);
150  EndCf = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_end_cf);
151  return false;
152 }
153 
154 /// Is the branch condition uniform or did the StructurizeCFG pass
155 /// consider it as such?
156 bool SIAnnotateControlFlow::isUniform(BranchInst *T) {
157  return DA->isUniform(T) ||
158  T->getMetadata("structurizecfg.uniform") != nullptr;
159 }
160 
161 /// Is BB the last block saved on the stack ?
162 bool SIAnnotateControlFlow::isTopOfStack(BasicBlock *BB) {
163  return !Stack.empty() && Stack.back().first == BB;
164 }
165 
166 /// Pop the last saved value from the control flow stack
167 Value *SIAnnotateControlFlow::popSaved() {
168  return Stack.pop_back_val().second;
169 }
170 
171 /// Push a BB and saved value to the control flow stack
172 void SIAnnotateControlFlow::push(BasicBlock *BB, Value *Saved) {
173  Stack.push_back(std::make_pair(BB, Saved));
174 }
175 
176 /// Can the condition represented by this PHI node treated like
177 /// an "Else" block?
178 bool SIAnnotateControlFlow::isElse(PHINode *Phi) {
179  BasicBlock *IDom = DT->getNode(Phi->getParent())->getIDom()->getBlock();
180  for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) {
181  if (Phi->getIncomingBlock(i) == IDom) {
182 
183  if (Phi->getIncomingValue(i) != BoolTrue)
184  return false;
185 
186  } else {
187  if (Phi->getIncomingValue(i) != BoolFalse)
188  return false;
189 
190  }
191  }
192  return true;
193 }
194 
195 // Erase "Phi" if it is not used any more
196 void SIAnnotateControlFlow::eraseIfUnused(PHINode *Phi) {
197  if (RecursivelyDeleteDeadPHINode(Phi)) {
198  LLVM_DEBUG(dbgs() << "Erased unused condition phi\n");
199  }
200 }
201 
202 /// Open a new "If" block
203 void SIAnnotateControlFlow::openIf(BranchInst *Term) {
204  if (isUniform(Term))
205  return;
206 
207  Value *Ret = CallInst::Create(If, Term->getCondition(), "", Term);
208  Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term));
209  push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term));
210 }
211 
212 /// Close the last "If" block and open a new "Else" block
213 void SIAnnotateControlFlow::insertElse(BranchInst *Term) {
214  if (isUniform(Term)) {
215  return;
216  }
217  Value *Ret = CallInst::Create(Else, popSaved(), "", Term);
218  Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term));
219  push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term));
220 }
221 
222 /// Recursively handle the condition leading to a loop
223 Value *SIAnnotateControlFlow::handleLoopCondition(
224  Value *Cond, PHINode *Broken, llvm::Loop *L, BranchInst *Term) {
225  if (Instruction *Inst = dyn_cast<Instruction>(Cond)) {
226  BasicBlock *Parent = Inst->getParent();
227  Instruction *Insert;
228  if (L->contains(Inst)) {
229  Insert = Parent->getTerminator();
230  } else {
231  Insert = L->getHeader()->getFirstNonPHIOrDbgOrLifetime();
232  }
233 
234  Value *Args[] = { Cond, Broken };
235  return CallInst::Create(IfBreak, Args, "", Insert);
236  }
237 
238  // Insert IfBreak in the loop header TERM for constant COND other than true.
239  if (isa<Constant>(Cond)) {
240  Instruction *Insert = Cond == BoolTrue ?
241  Term : L->getHeader()->getTerminator();
242 
243  Value *Args[] = { Cond, Broken };
244  return CallInst::Create(IfBreak, Args, "", Insert);
245  }
246 
247  llvm_unreachable("Unhandled loop condition!");
248 }
249 
250 /// Handle a back edge (loop)
251 void SIAnnotateControlFlow::handleLoop(BranchInst *Term) {
252  if (isUniform(Term))
253  return;
254 
255  BasicBlock *BB = Term->getParent();
256  llvm::Loop *L = LI->getLoopFor(BB);
257  if (!L)
258  return;
259 
260  BasicBlock *Target = Term->getSuccessor(1);
261  PHINode *Broken = PHINode::Create(Int64, 0, "phi.broken", &Target->front());
262 
263  Value *Cond = Term->getCondition();
264  Term->setCondition(BoolTrue);
265  Value *Arg = handleLoopCondition(Cond, Broken, L, Term);
266 
267  for (BasicBlock *Pred : predecessors(Target)) {
268  Value *PHIValue = Int64Zero;
269  if (Pred == BB) // Remember the value of the previous iteration.
270  PHIValue = Arg;
271  // If the backedge from Pred to Target could be executed before the exit
272  // of the loop at BB, it should not reset or change "Broken", which keeps
273  // track of the number of threads exited the loop at BB.
274  else if (L->contains(Pred) && DT->dominates(Pred, BB))
275  PHIValue = Broken;
276  Broken->addIncoming(PHIValue, Pred);
277  }
278 
279  Term->setCondition(CallInst::Create(Loop, Arg, "", Term));
280 
281  push(Term->getSuccessor(0), Arg);
282 }
283 
284 /// Close the last opened control flow
285 void SIAnnotateControlFlow::closeControlFlow(BasicBlock *BB) {
286  llvm::Loop *L = LI->getLoopFor(BB);
287 
288  assert(Stack.back().first == BB);
289 
290  if (L && L->getHeader() == BB) {
291  // We can't insert an EndCF call into a loop header, because it will
292  // get executed on every iteration of the loop, when it should be
293  // executed only once before the loop.
295  L->getLoopLatches(Latches);
296 
298  for (BasicBlock *Pred : predecessors(BB)) {
299  if (!is_contained(Latches, Pred))
300  Preds.push_back(Pred);
301  }
302 
303  BB = SplitBlockPredecessors(BB, Preds, "endcf.split", DT, LI, nullptr,
304  false);
305  }
306 
307  Value *Exec = popSaved();
308  Instruction *FirstInsertionPt = &*BB->getFirstInsertionPt();
309  if (!isa<UndefValue>(Exec) && !isa<UnreachableInst>(FirstInsertionPt))
310  CallInst::Create(EndCf, Exec, "", FirstInsertionPt);
311 }
312 
313 /// Annotate the control flow with intrinsics so the backend can
314 /// recognize if/then/else and loops.
316  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
317  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
318  DA = &getAnalysis<LegacyDivergenceAnalysis>();
319 
321  E = df_end(&F.getEntryBlock()); I != E; ++I) {
322  BasicBlock *BB = *I;
324 
325  if (!Term || Term->isUnconditional()) {
326  if (isTopOfStack(BB))
327  closeControlFlow(BB);
328 
329  continue;
330  }
331 
332  if (I.nodeVisited(Term->getSuccessor(1))) {
333  if (isTopOfStack(BB))
334  closeControlFlow(BB);
335 
336  handleLoop(Term);
337  continue;
338  }
339 
340  if (isTopOfStack(BB)) {
341  PHINode *Phi = dyn_cast<PHINode>(Term->getCondition());
342  if (Phi && Phi->getParent() == BB && isElse(Phi)) {
343  insertElse(Term);
344  eraseIfUnused(Phi);
345  continue;
346  }
347 
348  closeControlFlow(BB);
349  }
350 
351  openIf(Term);
352  }
353 
354  if (!Stack.empty()) {
355  // CFG was probably not structured.
356  report_fatal_error("failed to annotate CFG");
357  }
358 
359  return true;
360 }
361 
362 /// Create the annotation pass
364  return new SIAnnotateControlFlow();
365 }
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:594
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:172
FunctionPass * createSIAnnotateControlFlowPass()
Create the annotation pass.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
LLVMContext & Context
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:139
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
INITIALIZE_PASS_BEGIN(SIAnnotateControlFlow, DEBUG_TYPE, "Annotate SI Control Flow", false, false) INITIALIZE_PASS_END(SIAnnotateControlFlow
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
F(f)
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:176
Value * getCondition() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
&#39;undef&#39; values are things that do not have specified contents.
Definition: Constants.h:1285
void getLoopLatches(SmallVectorImpl< BlockT *> &LoopLatches) const
Return all loop latch blocks of this loop.
Definition: LoopInfo.h:303
static StructType * get(LLVMContext &Context, ArrayRef< Type *> Elements, bool isPacked=false)
This static method is the primary way to create a literal StructType.
Definition: Type.cpp:341
BlockT * getHeader() const
Definition: LoopInfo.h:99
const Instruction * getFirstNonPHIOrDbgOrLifetime() const
Returns a pointer to the first instruction in this block that is not a PHINode, a debug intrinsic...
Definition: BasicBlock.cpp:203
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:96
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:234
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Function * getDeclaration(Module *M, ID id, ArrayRef< Type *> Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1018
const BasicBlock & getEntryBlock() const
Definition: Function.h:642
static bool runOnFunction(Function &F, bool PostInlining)
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock *> Preds, const char *Suffix, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:216
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
Conditional or Unconditional Branch instruction.
static ExtractValueInst * Create(Value *Agg, ArrayRef< unsigned > Idxs, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
df_iterator< T > df_end(const T &G)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:41
This file contains the declarations for the subclasses of Constant, which represent the different fla...
const Instruction & front() const
Definition: BasicBlock.h:280
unsigned char Boolean
Definition: ConvertUTF.h:112
Represent the analysis usage information of a pass.
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:160
Annotate SI Control Flow
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1424
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:109
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
Module.h This file contains the declarations for the Module class.
bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=nullptr)
If the specified value is an effectively dead PHI node, due to being a def-use chain of single-use no...
Definition: Local.cpp:513
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:631
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:124
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:587
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
df_iterator< T > df_begin(const T &G)
Target - Wrapper for Target specific information.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:464
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
bool isUnconditional() const
void setCondition(Value *V)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:72
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:974
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
#define LLVM_DEBUG(X)
Definition: Debug.h:122
#define DEBUG_TYPE
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
const BasicBlock * getParent() const
Definition: Instruction.h:66
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1244