LLVM  10.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"
15 #include "AMDGPUSubtarget.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/Analysis/LoopInfo.h"
22 #include "llvm/IR/BasicBlock.h"
23 #include "llvm/IR/CFG.h"
24 #include "llvm/IR/Constant.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/DerivedTypes.h"
27 #include "llvm/IR/Dominators.h"
28 #include "llvm/IR/Function.h"
29 #include "llvm/IR/Instruction.h"
30 #include "llvm/IR/Instructions.h"
31 #include "llvm/IR/Intrinsics.h"
32 #include "llvm/IR/Module.h"
33 #include "llvm/IR/Type.h"
34 #include "llvm/IR/ValueHandle.h"
35 #include "llvm/Pass.h"
36 #include "llvm/Support/Casting.h"
37 #include "llvm/Support/Debug.h"
42 #include <cassert>
43 #include <utility>
44 
45 using namespace llvm;
46 
47 #define DEBUG_TYPE "si-annotate-control-flow"
48 
49 namespace {
50 
51 // Complex types used in this pass
52 using StackEntry = std::pair<BasicBlock *, Value *>;
53 using StackVector = SmallVector<StackEntry, 16>;
54 
55 class SIAnnotateControlFlow : public FunctionPass {
57 
58  Type *Boolean;
59  Type *Void;
60  Type *IntMask;
61  Type *ReturnStruct;
62 
63  ConstantInt *BoolTrue;
64  ConstantInt *BoolFalse;
65  UndefValue *BoolUndef;
66  Constant *IntMaskZero;
67 
68  Function *If;
69  Function *Else;
70  Function *IfBreak;
71  Function *Loop;
72  Function *EndCf;
73 
74  DominatorTree *DT;
75  StackVector Stack;
76 
77  LoopInfo *LI;
78 
79  void initialize(Module &M, const GCNSubtarget &ST);
80 
81  bool isUniform(BranchInst *T);
82 
83  bool isTopOfStack(BasicBlock *BB);
84 
85  Value *popSaved();
86 
87  void push(BasicBlock *BB, Value *Saved);
88 
89  bool isElse(PHINode *Phi);
90 
91  void eraseIfUnused(PHINode *Phi);
92 
93  void openIf(BranchInst *Term);
94 
95  void insertElse(BranchInst *Term);
96 
97  Value *
98  handleLoopCondition(Value *Cond, PHINode *Broken, llvm::Loop *L,
99  BranchInst *Term);
100 
101  void handleLoop(BranchInst *Term);
102 
103  void closeControlFlow(BasicBlock *BB);
104 
105 public:
106  static char ID;
107 
108  SIAnnotateControlFlow() : FunctionPass(ID) {}
109 
110  bool runOnFunction(Function &F) override;
111 
112  StringRef getPassName() const override { return "SI annotate control flow"; }
113 
114  void getAnalysisUsage(AnalysisUsage &AU) const override {
121  }
122 };
123 
124 } // end anonymous namespace
125 
126 INITIALIZE_PASS_BEGIN(SIAnnotateControlFlow, DEBUG_TYPE,
127  "Annotate SI Control Flow", false, false)
131 INITIALIZE_PASS_END(SIAnnotateControlFlow, DEBUG_TYPE,
132  "Annotate SI Control Flow", false, false)
133 
134 char SIAnnotateControlFlow::ID = 0;
135 
136 /// Initialize all the types and constants used in the pass
137 void SIAnnotateControlFlow::initialize(Module &M, const GCNSubtarget &ST) {
138  LLVMContext &Context = M.getContext();
139 
140  Void = Type::getVoidTy(Context);
141  Boolean = Type::getInt1Ty(Context);
142  IntMask = ST.isWave32() ? Type::getInt32Ty(Context)
143  : Type::getInt64Ty(Context);
144  ReturnStruct = StructType::get(Boolean, IntMask);
145 
146  BoolTrue = ConstantInt::getTrue(Context);
147  BoolFalse = ConstantInt::getFalse(Context);
148  BoolUndef = UndefValue::get(Boolean);
149  IntMaskZero = ConstantInt::get(IntMask, 0);
150 
151  If = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_if, { IntMask });
152  Else = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_else,
153  { IntMask, IntMask });
154  IfBreak = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_if_break,
155  { IntMask, IntMask });
156  Loop = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_loop, { IntMask });
157  EndCf = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_end_cf, { IntMask });
158 }
159 
160 /// Is the branch condition uniform or did the StructurizeCFG pass
161 /// consider it as such?
162 bool SIAnnotateControlFlow::isUniform(BranchInst *T) {
163  return DA->isUniform(T) ||
164  T->getMetadata("structurizecfg.uniform") != nullptr;
165 }
166 
167 /// Is BB the last block saved on the stack ?
168 bool SIAnnotateControlFlow::isTopOfStack(BasicBlock *BB) {
169  return !Stack.empty() && Stack.back().first == BB;
170 }
171 
172 /// Pop the last saved value from the control flow stack
173 Value *SIAnnotateControlFlow::popSaved() {
174  return Stack.pop_back_val().second;
175 }
176 
177 /// Push a BB and saved value to the control flow stack
178 void SIAnnotateControlFlow::push(BasicBlock *BB, Value *Saved) {
179  Stack.push_back(std::make_pair(BB, Saved));
180 }
181 
182 /// Can the condition represented by this PHI node treated like
183 /// an "Else" block?
184 bool SIAnnotateControlFlow::isElse(PHINode *Phi) {
185  BasicBlock *IDom = DT->getNode(Phi->getParent())->getIDom()->getBlock();
186  for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) {
187  if (Phi->getIncomingBlock(i) == IDom) {
188 
189  if (Phi->getIncomingValue(i) != BoolTrue)
190  return false;
191 
192  } else {
193  if (Phi->getIncomingValue(i) != BoolFalse)
194  return false;
195 
196  }
197  }
198  return true;
199 }
200 
201 // Erase "Phi" if it is not used any more
202 void SIAnnotateControlFlow::eraseIfUnused(PHINode *Phi) {
203  if (RecursivelyDeleteDeadPHINode(Phi)) {
204  LLVM_DEBUG(dbgs() << "Erased unused condition phi\n");
205  }
206 }
207 
208 /// Open a new "If" block
209 void SIAnnotateControlFlow::openIf(BranchInst *Term) {
210  if (isUniform(Term))
211  return;
212 
213  Value *Ret = CallInst::Create(If, Term->getCondition(), "", Term);
214  Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term));
215  push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term));
216 }
217 
218 /// Close the last "If" block and open a new "Else" block
219 void SIAnnotateControlFlow::insertElse(BranchInst *Term) {
220  if (isUniform(Term)) {
221  return;
222  }
223  Value *Ret = CallInst::Create(Else, popSaved(), "", Term);
224  Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term));
225  push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term));
226 }
227 
228 /// Recursively handle the condition leading to a loop
229 Value *SIAnnotateControlFlow::handleLoopCondition(
230  Value *Cond, PHINode *Broken, llvm::Loop *L, BranchInst *Term) {
231  if (Instruction *Inst = dyn_cast<Instruction>(Cond)) {
232  BasicBlock *Parent = Inst->getParent();
233  Instruction *Insert;
234  if (L->contains(Inst)) {
235  Insert = Parent->getTerminator();
236  } else {
237  Insert = L->getHeader()->getFirstNonPHIOrDbgOrLifetime();
238  }
239 
240  Value *Args[] = { Cond, Broken };
241  return CallInst::Create(IfBreak, Args, "", Insert);
242  }
243 
244  // Insert IfBreak in the loop header TERM for constant COND other than true.
245  if (isa<Constant>(Cond)) {
246  Instruction *Insert = Cond == BoolTrue ?
247  Term : L->getHeader()->getTerminator();
248 
249  Value *Args[] = { Cond, Broken };
250  return CallInst::Create(IfBreak, Args, "", Insert);
251  }
252 
253  llvm_unreachable("Unhandled loop condition!");
254 }
255 
256 /// Handle a back edge (loop)
257 void SIAnnotateControlFlow::handleLoop(BranchInst *Term) {
258  if (isUniform(Term))
259  return;
260 
261  BasicBlock *BB = Term->getParent();
262  llvm::Loop *L = LI->getLoopFor(BB);
263  if (!L)
264  return;
265 
266  BasicBlock *Target = Term->getSuccessor(1);
267  PHINode *Broken = PHINode::Create(IntMask, 0, "phi.broken", &Target->front());
268 
269  Value *Cond = Term->getCondition();
270  Term->setCondition(BoolTrue);
271  Value *Arg = handleLoopCondition(Cond, Broken, L, Term);
272 
273  for (BasicBlock *Pred : predecessors(Target)) {
274  Value *PHIValue = IntMaskZero;
275  if (Pred == BB) // Remember the value of the previous iteration.
276  PHIValue = Arg;
277  // If the backedge from Pred to Target could be executed before the exit
278  // of the loop at BB, it should not reset or change "Broken", which keeps
279  // track of the number of threads exited the loop at BB.
280  else if (L->contains(Pred) && DT->dominates(Pred, BB))
281  PHIValue = Broken;
282  Broken->addIncoming(PHIValue, Pred);
283  }
284 
285  Term->setCondition(CallInst::Create(Loop, Arg, "", Term));
286 
287  push(Term->getSuccessor(0), Arg);
288 }
289 
290 /// Close the last opened control flow
291 void SIAnnotateControlFlow::closeControlFlow(BasicBlock *BB) {
292  llvm::Loop *L = LI->getLoopFor(BB);
293 
294  assert(Stack.back().first == BB);
295 
296  if (L && L->getHeader() == BB) {
297  // We can't insert an EndCF call into a loop header, because it will
298  // get executed on every iteration of the loop, when it should be
299  // executed only once before the loop.
301  L->getLoopLatches(Latches);
302 
304  for (BasicBlock *Pred : predecessors(BB)) {
305  if (!is_contained(Latches, Pred))
306  Preds.push_back(Pred);
307  }
308 
309  BB = SplitBlockPredecessors(BB, Preds, "endcf.split", DT, LI, nullptr,
310  false);
311  }
312 
313  Value *Exec = popSaved();
314  Instruction *FirstInsertionPt = &*BB->getFirstInsertionPt();
315  if (!isa<UndefValue>(Exec) && !isa<UnreachableInst>(FirstInsertionPt))
316  CallInst::Create(EndCf, Exec, "", FirstInsertionPt);
317 }
318 
319 /// Annotate the control flow with intrinsics so the backend can
320 /// recognize if/then/else and loops.
322  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
323  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
324  DA = &getAnalysis<LegacyDivergenceAnalysis>();
325  TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
326  const TargetMachine &TM = TPC.getTM<TargetMachine>();
327 
328  initialize(*F.getParent(), TM.getSubtarget<GCNSubtarget>(F));
329 
331  E = df_end(&F.getEntryBlock()); I != E; ++I) {
332  BasicBlock *BB = *I;
334 
335  if (!Term || Term->isUnconditional()) {
336  if (isTopOfStack(BB))
337  closeControlFlow(BB);
338 
339  continue;
340  }
341 
342  if (I.nodeVisited(Term->getSuccessor(1))) {
343  if (isTopOfStack(BB))
344  closeControlFlow(BB);
345 
346  handleLoop(Term);
347  continue;
348  }
349 
350  if (isTopOfStack(BB)) {
351  PHINode *Phi = dyn_cast<PHINode>(Term->getCondition());
352  if (Phi && Phi->getParent() == BB && isElse(Phi)) {
353  insertElse(Term);
354  eraseIfUnused(Phi);
355  continue;
356  }
357 
358  closeControlFlow(BB);
359  }
360 
361  openIf(Term);
362  }
363 
364  if (!Stack.empty()) {
365  // CFG was probably not structured.
366  report_fatal_error("failed to annotate CFG");
367  }
368 
369  return true;
370 }
371 
372 /// Create the annotation pass
374  return new SIAnnotateControlFlow();
375 }
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:603
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
AMDGPU specific subclass of TargetSubtarget.
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:314
Target-Independent Code Generator Pass Configuration Options.
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:105
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:1043
const BasicBlock & getEntryBlock() const
Definition: Function.h:664
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
static void push(SmallVectorImpl< uint64_t > &R, StringRef Str)
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:1433
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:115
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:837
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:523
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:640
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:596
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.
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringRef > StandardNames)
Initialize the set of available library functions based on the specified target triple.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:175
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
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())
aarch64 promote const
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:575
LLVM Value Representation.
Definition: Value.h:73
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:65
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:1208
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:1236