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/Analysis/DivergenceAnalysis.h" 18 #include "llvm/Analysis/LoopInfo.h" 19 #include "llvm/IR/Constants.h" 20 #include "llvm/IR/Dominators.h" 21 #include "llvm/IR/Instructions.h" 22 #include "llvm/IR/Module.h" 23 #include "llvm/Pass.h" 24 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 25 #include "llvm/Transforms/Utils/SSAUpdater.h" 26 27 using namespace llvm; 28 29 #define DEBUG_TYPE "si-annotate-control-flow" 30 31 namespace { 32 33 // Complex types used in this pass 34 typedef std::pair<BasicBlock *, Value *> StackEntry; 35 typedef SmallVector<StackEntry, 16> StackVector; 36 37 // Intrinsic names the control flow is annotated with 38 static const char *const IfIntrinsic = "llvm.amdgcn.if"; 39 static const char *const ElseIntrinsic = "llvm.amdgcn.else"; 40 static const char *const BreakIntrinsic = "llvm.amdgcn.break"; 41 static const char *const IfBreakIntrinsic = "llvm.amdgcn.if.break"; 42 static const char *const ElseBreakIntrinsic = "llvm.amdgcn.else.break"; 43 static const char *const LoopIntrinsic = "llvm.amdgcn.loop"; 44 static const char *const EndCfIntrinsic = "llvm.amdgcn.end.cf"; 45 46 class SIAnnotateControlFlow : public FunctionPass { 47 DivergenceAnalysis *DA; 48 49 Type *Boolean; 50 Type *Void; 51 Type *Int64; 52 Type *ReturnStruct; 53 54 ConstantInt *BoolTrue; 55 ConstantInt *BoolFalse; 56 UndefValue *BoolUndef; 57 Constant *Int64Zero; 58 59 Constant *If; 60 Constant *Else; 61 Constant *Break; 62 Constant *IfBreak; 63 Constant *ElseBreak; 64 Constant *Loop; 65 Constant *EndCf; 66 67 DominatorTree *DT; 68 StackVector Stack; 69 70 LoopInfo *LI; 71 72 bool isUniform(BranchInst *T); 73 74 bool isTopOfStack(BasicBlock *BB); 75 76 Value *popSaved(); 77 78 void push(BasicBlock *BB, Value *Saved); 79 80 bool isElse(PHINode *Phi); 81 82 void eraseIfUnused(PHINode *Phi); 83 84 void openIf(BranchInst *Term); 85 86 void insertElse(BranchInst *Term); 87 88 Value *handleLoopCondition(Value *Cond, PHINode *Broken, 89 llvm::Loop *L, BranchInst *Term); 90 91 void handleLoop(BranchInst *Term); 92 93 void closeControlFlow(BasicBlock *BB); 94 95 public: 96 static char ID; 97 98 SIAnnotateControlFlow(): 99 FunctionPass(ID) { } 100 101 bool doInitialization(Module &M) override; 102 103 bool runOnFunction(Function &F) override; 104 105 const char *getPassName() const override { 106 return "SI annotate control flow"; 107 } 108 109 void getAnalysisUsage(AnalysisUsage &AU) const override { 110 AU.addRequired<LoopInfoWrapperPass>(); 111 AU.addRequired<DominatorTreeWrapperPass>(); 112 AU.addRequired<DivergenceAnalysis>(); 113 AU.addPreserved<DominatorTreeWrapperPass>(); 114 FunctionPass::getAnalysisUsage(AU); 115 } 116 117 }; 118 119 } // end anonymous namespace 120 121 INITIALIZE_PASS_BEGIN(SIAnnotateControlFlow, DEBUG_TYPE, 122 "Annotate SI Control Flow", false, false) 123 INITIALIZE_PASS_DEPENDENCY(DivergenceAnalysis) 124 INITIALIZE_PASS_END(SIAnnotateControlFlow, DEBUG_TYPE, 125 "Annotate SI Control Flow", false, false) 126 127 char SIAnnotateControlFlow::ID = 0; 128 129 /// \brief Initialize all the types and constants used in the pass 130 bool SIAnnotateControlFlow::doInitialization(Module &M) { 131 LLVMContext &Context = M.getContext(); 132 133 Void = Type::getVoidTy(Context); 134 Boolean = Type::getInt1Ty(Context); 135 Int64 = Type::getInt64Ty(Context); 136 ReturnStruct = StructType::get(Boolean, Int64, (Type *)nullptr); 137 138 BoolTrue = ConstantInt::getTrue(Context); 139 BoolFalse = ConstantInt::getFalse(Context); 140 BoolUndef = UndefValue::get(Boolean); 141 Int64Zero = ConstantInt::get(Int64, 0); 142 143 If = M.getOrInsertFunction( 144 IfIntrinsic, ReturnStruct, Boolean, (Type *)nullptr); 145 146 Else = M.getOrInsertFunction( 147 ElseIntrinsic, ReturnStruct, Int64, (Type *)nullptr); 148 149 Break = M.getOrInsertFunction( 150 BreakIntrinsic, Int64, Int64, (Type *)nullptr); 151 152 IfBreak = M.getOrInsertFunction( 153 IfBreakIntrinsic, Int64, Boolean, Int64, (Type *)nullptr); 154 155 ElseBreak = M.getOrInsertFunction( 156 ElseBreakIntrinsic, Int64, Int64, Int64, (Type *)nullptr); 157 158 Loop = M.getOrInsertFunction( 159 LoopIntrinsic, Boolean, Int64, (Type *)nullptr); 160 161 EndCf = M.getOrInsertFunction( 162 EndCfIntrinsic, Void, Int64, (Type *)nullptr); 163 164 return false; 165 } 166 167 /// \brief Is the branch condition uniform or did the StructurizeCFG pass 168 /// consider it as such? 169 bool SIAnnotateControlFlow::isUniform(BranchInst *T) { 170 return DA->isUniform(T->getCondition()) || 171 T->getMetadata("structurizecfg.uniform") != nullptr; 172 } 173 174 /// \brief Is BB the last block saved on the stack ? 175 bool SIAnnotateControlFlow::isTopOfStack(BasicBlock *BB) { 176 return !Stack.empty() && Stack.back().first == BB; 177 } 178 179 /// \brief Pop the last saved value from the control flow stack 180 Value *SIAnnotateControlFlow::popSaved() { 181 return Stack.pop_back_val().second; 182 } 183 184 /// \brief Push a BB and saved value to the control flow stack 185 void SIAnnotateControlFlow::push(BasicBlock *BB, Value *Saved) { 186 Stack.push_back(std::make_pair(BB, Saved)); 187 } 188 189 /// \brief Can the condition represented by this PHI node treated like 190 /// an "Else" block? 191 bool SIAnnotateControlFlow::isElse(PHINode *Phi) { 192 BasicBlock *IDom = DT->getNode(Phi->getParent())->getIDom()->getBlock(); 193 for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) { 194 if (Phi->getIncomingBlock(i) == IDom) { 195 196 if (Phi->getIncomingValue(i) != BoolTrue) 197 return false; 198 199 } else { 200 if (Phi->getIncomingValue(i) != BoolFalse) 201 return false; 202 203 } 204 } 205 return true; 206 } 207 208 // \brief Erase "Phi" if it is not used any more 209 void SIAnnotateControlFlow::eraseIfUnused(PHINode *Phi) { 210 if (!Phi->hasNUsesOrMore(1)) 211 Phi->eraseFromParent(); 212 } 213 214 /// \brief Open a new "If" block 215 void SIAnnotateControlFlow::openIf(BranchInst *Term) { 216 if (isUniform(Term)) { 217 return; 218 } 219 Value *Ret = CallInst::Create(If, Term->getCondition(), "", Term); 220 Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term)); 221 push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term)); 222 } 223 224 /// \brief Close the last "If" block and open a new "Else" block 225 void SIAnnotateControlFlow::insertElse(BranchInst *Term) { 226 if (isUniform(Term)) { 227 return; 228 } 229 Value *Ret = CallInst::Create(Else, popSaved(), "", Term); 230 Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term)); 231 push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term)); 232 } 233 234 /// \brief Recursively handle the condition leading to a loop 235 Value *SIAnnotateControlFlow::handleLoopCondition(Value *Cond, PHINode *Broken, 236 llvm::Loop *L, BranchInst *Term) { 237 238 // Only search through PHI nodes which are inside the loop. If we try this 239 // with PHI nodes that are outside of the loop, we end up inserting new PHI 240 // nodes outside of the loop which depend on values defined inside the loop. 241 // This will break the module with 242 // 'Instruction does not dominate all users!' errors. 243 PHINode *Phi = nullptr; 244 if ((Phi = dyn_cast<PHINode>(Cond)) && L->contains(Phi)) { 245 246 BasicBlock *Parent = Phi->getParent(); 247 PHINode *NewPhi = PHINode::Create(Int64, 0, "", &Parent->front()); 248 Value *Ret = NewPhi; 249 250 // Handle all non-constant incoming values first 251 for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) { 252 Value *Incoming = Phi->getIncomingValue(i); 253 BasicBlock *From = Phi->getIncomingBlock(i); 254 if (isa<ConstantInt>(Incoming)) { 255 NewPhi->addIncoming(Broken, From); 256 continue; 257 } 258 259 Phi->setIncomingValue(i, BoolFalse); 260 Value *PhiArg = handleLoopCondition(Incoming, Broken, L, Term); 261 NewPhi->addIncoming(PhiArg, From); 262 } 263 264 BasicBlock *IDom = DT->getNode(Parent)->getIDom()->getBlock(); 265 266 for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) { 267 268 Value *Incoming = Phi->getIncomingValue(i); 269 if (Incoming != BoolTrue) 270 continue; 271 272 BasicBlock *From = Phi->getIncomingBlock(i); 273 if (From == IDom) { 274 // We're in the following situation: 275 // IDom/From 276 // | \ 277 // | If-block 278 // | / 279 // Parent 280 // where we want to break out of the loop if the If-block is not taken. 281 // Due to the depth-first traversal, there should be an end.cf 282 // intrinsic in Parent, and we insert an else.break before it. 283 // 284 // Note that the end.cf need not be the first non-phi instruction 285 // of parent, particularly when we're dealing with a multi-level 286 // break, but it should occur within a group of intrinsic calls 287 // at the beginning of the block. 288 CallInst *OldEnd = dyn_cast<CallInst>(Parent->getFirstInsertionPt()); 289 while (OldEnd && OldEnd->getCalledFunction() != EndCf) 290 OldEnd = dyn_cast<CallInst>(OldEnd->getNextNode()); 291 if (OldEnd && OldEnd->getCalledFunction() == EndCf) { 292 Value *Args[] = { OldEnd->getArgOperand(0), NewPhi }; 293 Ret = CallInst::Create(ElseBreak, Args, "", OldEnd); 294 continue; 295 } 296 } 297 TerminatorInst *Insert = From->getTerminator(); 298 Value *PhiArg = CallInst::Create(Break, Broken, "", Insert); 299 NewPhi->setIncomingValue(i, PhiArg); 300 } 301 eraseIfUnused(Phi); 302 return Ret; 303 304 } else if (Instruction *Inst = dyn_cast<Instruction>(Cond)) { 305 BasicBlock *Parent = Inst->getParent(); 306 Instruction *Insert; 307 if (L->contains(Inst)) { 308 Insert = Parent->getTerminator(); 309 } else { 310 Insert = L->getHeader()->getFirstNonPHIOrDbgOrLifetime(); 311 } 312 Value *Args[] = { Cond, Broken }; 313 return CallInst::Create(IfBreak, Args, "", Insert); 314 315 // Insert IfBreak before TERM for constant COND. 316 } else if (isa<ConstantInt>(Cond)) { 317 Value *Args[] = { Cond, Broken }; 318 return CallInst::Create(IfBreak, Args, "", Term); 319 320 } else { 321 llvm_unreachable("Unhandled loop condition!"); 322 } 323 return nullptr; 324 } 325 326 /// \brief Handle a back edge (loop) 327 void SIAnnotateControlFlow::handleLoop(BranchInst *Term) { 328 if (isUniform(Term)) { 329 return; 330 } 331 332 BasicBlock *BB = Term->getParent(); 333 llvm::Loop *L = LI->getLoopFor(BB); 334 BasicBlock *Target = Term->getSuccessor(1); 335 PHINode *Broken = PHINode::Create(Int64, 0, "", &Target->front()); 336 337 Value *Cond = Term->getCondition(); 338 Term->setCondition(BoolTrue); 339 Value *Arg = handleLoopCondition(Cond, Broken, L, Term); 340 341 for (pred_iterator PI = pred_begin(Target), PE = pred_end(Target); 342 PI != PE; ++PI) { 343 344 Broken->addIncoming(*PI == BB ? Arg : Int64Zero, *PI); 345 } 346 347 Term->setCondition(CallInst::Create(Loop, Arg, "", Term)); 348 push(Term->getSuccessor(0), Arg); 349 }/// \brief Close the last opened control flow 350 void SIAnnotateControlFlow::closeControlFlow(BasicBlock *BB) { 351 llvm::Loop *L = LI->getLoopFor(BB); 352 353 assert(Stack.back().first == BB); 354 355 if (L && L->getHeader() == BB) { 356 // We can't insert an EndCF call into a loop header, because it will 357 // get executed on every iteration of the loop, when it should be 358 // executed only once before the loop. 359 SmallVector <BasicBlock*, 8> Latches; 360 L->getLoopLatches(Latches); 361 362 std::vector<BasicBlock*> Preds; 363 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) { 364 if (std::find(Latches.begin(), Latches.end(), *PI) == Latches.end()) 365 Preds.push_back(*PI); 366 } 367 BB = llvm::SplitBlockPredecessors(BB, Preds, "endcf.split", DT, LI, false); 368 } 369 370 Value *Exec = popSaved(); 371 if (!isa<UndefValue>(Exec)) 372 CallInst::Create(EndCf, Exec, "", &*BB->getFirstInsertionPt()); 373 } 374 375 /// \brief Annotate the control flow with intrinsics so the backend can 376 /// recognize if/then/else and loops. 377 bool SIAnnotateControlFlow::runOnFunction(Function &F) { 378 379 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 380 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 381 DA = &getAnalysis<DivergenceAnalysis>(); 382 383 for (df_iterator<BasicBlock *> I = df_begin(&F.getEntryBlock()), 384 E = df_end(&F.getEntryBlock()); I != E; ++I) { 385 386 BranchInst *Term = dyn_cast<BranchInst>((*I)->getTerminator()); 387 388 if (!Term || Term->isUnconditional()) { 389 if (isTopOfStack(*I)) 390 closeControlFlow(*I); 391 392 continue; 393 } 394 395 if (I.nodeVisited(Term->getSuccessor(1))) { 396 if (isTopOfStack(*I)) 397 closeControlFlow(*I); 398 399 handleLoop(Term); 400 continue; 401 } 402 403 if (isTopOfStack(*I)) { 404 PHINode *Phi = dyn_cast<PHINode>(Term->getCondition()); 405 if (Phi && Phi->getParent() == *I && isElse(Phi)) { 406 insertElse(Term); 407 eraseIfUnused(Phi); 408 continue; 409 } 410 closeControlFlow(*I); 411 } 412 openIf(Term); 413 } 414 415 assert(Stack.empty()); 416 return true; 417 } 418 419 /// \brief Create the annotation pass 420 FunctionPass *llvm::createSIAnnotateControlFlowPass() { 421 return new SIAnnotateControlFlow(); 422 } 423
