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:616
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:177
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:66
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:181
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:144
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:346
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:210
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:244
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringLiteral > StandardNames)
Initialize the set of available library functions based on the specified target triple.
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:1093
const BasicBlock & getEntryBlock() const
Definition: Function.h:669
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:223
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:46
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:285
unsigned char Boolean
Definition: ConvertUTF.h:112
Represent the analysis usage information of a pass.
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:165
Annotate SI Control Flow
constexpr double e
Definition: MathExtras.h:57
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:1446
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:653
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:609
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...
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:180
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:74
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:1224