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 "GCNSubtarget.h" 16 #include "llvm/Analysis/LoopInfo.h" 17 #include "llvm/Analysis/UniformityAnalysis.h" 18 #include "llvm/CodeGen/TargetPassConfig.h" 19 #include "llvm/IR/BasicBlock.h" 20 #include "llvm/IR/Constants.h" 21 #include "llvm/IR/Dominators.h" 22 #include "llvm/IR/IRBuilder.h" 23 #include "llvm/IR/IntrinsicsAMDGPU.h" 24 #include "llvm/InitializePasses.h" 25 #include "llvm/Target/TargetMachine.h" 26 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 27 #include "llvm/Transforms/Utils/Local.h" 28 29 using namespace llvm; 30 31 #define DEBUG_TYPE "si-annotate-control-flow" 32 33 namespace { 34 35 // Complex types used in this pass 36 using StackEntry = std::pair<BasicBlock *, Value *>; 37 using StackVector = SmallVector<StackEntry, 16>; 38 39 class SIAnnotateControlFlow : public FunctionPass { 40 UniformityInfo *UA; 41 42 Type *Boolean; 43 Type *Void; 44 Type *IntMask; 45 Type *ReturnStruct; 46 47 ConstantInt *BoolTrue; 48 ConstantInt *BoolFalse; 49 UndefValue *BoolUndef; 50 Constant *IntMaskZero; 51 52 Function *If; 53 Function *Else; 54 Function *IfBreak; 55 Function *Loop; 56 Function *EndCf; 57 58 DominatorTree *DT; 59 StackVector Stack; 60 61 LoopInfo *LI; 62 63 void initialize(Module &M, const GCNSubtarget &ST); 64 65 bool isUniform(BranchInst *T); 66 67 bool isTopOfStack(BasicBlock *BB); 68 69 Value *popSaved(); 70 71 void push(BasicBlock *BB, Value *Saved); 72 73 bool isElse(PHINode *Phi); 74 75 bool hasKill(const BasicBlock *BB); 76 77 bool eraseIfUnused(PHINode *Phi); 78 79 bool openIf(BranchInst *Term); 80 81 bool insertElse(BranchInst *Term); 82 83 Value * 84 handleLoopCondition(Value *Cond, PHINode *Broken, llvm::Loop *L, 85 BranchInst *Term); 86 87 bool handleLoop(BranchInst *Term); 88 89 bool closeControlFlow(BasicBlock *BB); 90 91 public: 92 static char ID; 93 SIAnnotateControlFlow()94 SIAnnotateControlFlow() : FunctionPass(ID) {} 95 96 bool runOnFunction(Function &F) override; 97 getPassName() const98 StringRef getPassName() const override { return "SI annotate control flow"; } 99 getAnalysisUsage(AnalysisUsage & AU) const100 void getAnalysisUsage(AnalysisUsage &AU) const override { 101 AU.addRequired<LoopInfoWrapperPass>(); 102 AU.addRequired<DominatorTreeWrapperPass>(); 103 AU.addRequired<UniformityInfoWrapperPass>(); 104 AU.addPreserved<LoopInfoWrapperPass>(); 105 AU.addPreserved<DominatorTreeWrapperPass>(); 106 AU.addRequired<TargetPassConfig>(); 107 FunctionPass::getAnalysisUsage(AU); 108 } 109 }; 110 111 } // end anonymous namespace 112 113 INITIALIZE_PASS_BEGIN(SIAnnotateControlFlow, DEBUG_TYPE, 114 "Annotate SI Control Flow", false, false) 115 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 116 INITIALIZE_PASS_DEPENDENCY(UniformityInfoWrapperPass) 117 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig) 118 INITIALIZE_PASS_END(SIAnnotateControlFlow, DEBUG_TYPE, 119 "Annotate SI Control Flow", false, false) 120 121 char SIAnnotateControlFlow::ID = 0; 122 123 /// Initialize all the types and constants used in the pass initialize(Module & M,const GCNSubtarget & ST)124 void SIAnnotateControlFlow::initialize(Module &M, const GCNSubtarget &ST) { 125 LLVMContext &Context = M.getContext(); 126 127 Void = Type::getVoidTy(Context); 128 Boolean = Type::getInt1Ty(Context); 129 IntMask = ST.isWave32() ? Type::getInt32Ty(Context) 130 : Type::getInt64Ty(Context); 131 ReturnStruct = StructType::get(Boolean, IntMask); 132 133 BoolTrue = ConstantInt::getTrue(Context); 134 BoolFalse = ConstantInt::getFalse(Context); 135 BoolUndef = PoisonValue::get(Boolean); 136 IntMaskZero = ConstantInt::get(IntMask, 0); 137 138 If = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_if, { IntMask }); 139 Else = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_else, 140 { IntMask, IntMask }); 141 IfBreak = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_if_break, 142 { IntMask }); 143 Loop = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_loop, { IntMask }); 144 EndCf = Intrinsic::getDeclaration(&M, Intrinsic::amdgcn_end_cf, { IntMask }); 145 } 146 147 /// Is the branch condition uniform or did the StructurizeCFG pass 148 /// consider it as such? isUniform(BranchInst * T)149 bool SIAnnotateControlFlow::isUniform(BranchInst *T) { 150 return UA->isUniform(T) || T->hasMetadata("structurizecfg.uniform"); 151 } 152 153 /// Is BB the last block saved on the stack ? isTopOfStack(BasicBlock * BB)154 bool SIAnnotateControlFlow::isTopOfStack(BasicBlock *BB) { 155 return !Stack.empty() && Stack.back().first == BB; 156 } 157 158 /// Pop the last saved value from the control flow stack popSaved()159 Value *SIAnnotateControlFlow::popSaved() { 160 return Stack.pop_back_val().second; 161 } 162 163 /// Push a BB and saved value to the control flow stack push(BasicBlock * BB,Value * Saved)164 void SIAnnotateControlFlow::push(BasicBlock *BB, Value *Saved) { 165 Stack.push_back(std::pair(BB, Saved)); 166 } 167 168 /// Can the condition represented by this PHI node treated like 169 /// an "Else" block? isElse(PHINode * Phi)170 bool SIAnnotateControlFlow::isElse(PHINode *Phi) { 171 BasicBlock *IDom = DT->getNode(Phi->getParent())->getIDom()->getBlock(); 172 for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) { 173 if (Phi->getIncomingBlock(i) == IDom) { 174 175 if (Phi->getIncomingValue(i) != BoolTrue) 176 return false; 177 178 } else { 179 if (Phi->getIncomingValue(i) != BoolFalse) 180 return false; 181 182 } 183 } 184 return true; 185 } 186 hasKill(const BasicBlock * BB)187 bool SIAnnotateControlFlow::hasKill(const BasicBlock *BB) { 188 for (const Instruction &I : *BB) { 189 if (const CallInst *CI = dyn_cast<CallInst>(&I)) 190 if (CI->getIntrinsicID() == Intrinsic::amdgcn_kill) 191 return true; 192 } 193 return false; 194 } 195 196 // Erase "Phi" if it is not used any more. Return true if any change was made. eraseIfUnused(PHINode * Phi)197 bool SIAnnotateControlFlow::eraseIfUnused(PHINode *Phi) { 198 bool Changed = RecursivelyDeleteDeadPHINode(Phi); 199 if (Changed) 200 LLVM_DEBUG(dbgs() << "Erased unused condition phi\n"); 201 return Changed; 202 } 203 204 /// Open a new "If" block openIf(BranchInst * Term)205 bool SIAnnotateControlFlow::openIf(BranchInst *Term) { 206 if (isUniform(Term)) 207 return false; 208 209 IRBuilder<> IRB(Term); 210 Value *IfCall = IRB.CreateCall(If, {Term->getCondition()}); 211 Value *Cond = IRB.CreateExtractValue(IfCall, {0}); 212 Value *Mask = IRB.CreateExtractValue(IfCall, {1}); 213 Term->setCondition(Cond); 214 push(Term->getSuccessor(1), Mask); 215 return true; 216 } 217 218 /// Close the last "If" block and open a new "Else" block insertElse(BranchInst * Term)219 bool SIAnnotateControlFlow::insertElse(BranchInst *Term) { 220 if (isUniform(Term)) { 221 return false; 222 } 223 224 IRBuilder<> IRB(Term); 225 Value *ElseCall = IRB.CreateCall(Else, {popSaved()}); 226 Value *Cond = IRB.CreateExtractValue(ElseCall, {0}); 227 Value *Mask = IRB.CreateExtractValue(ElseCall, {1}); 228 Term->setCondition(Cond); 229 push(Term->getSuccessor(1), Mask); 230 return true; 231 } 232 233 /// Recursively handle the condition leading to a loop handleLoopCondition(Value * Cond,PHINode * Broken,llvm::Loop * L,BranchInst * Term)234 Value *SIAnnotateControlFlow::handleLoopCondition( 235 Value *Cond, PHINode *Broken, llvm::Loop *L, BranchInst *Term) { 236 237 auto CreateBreak = [this, Cond, Broken](Instruction *I) -> CallInst * { 238 return IRBuilder<>(I).CreateCall(IfBreak, {Cond, Broken}); 239 }; 240 241 if (Instruction *Inst = dyn_cast<Instruction>(Cond)) { 242 BasicBlock *Parent = Inst->getParent(); 243 Instruction *Insert; 244 if (L->contains(Inst)) { 245 Insert = Parent->getTerminator(); 246 } else { 247 Insert = L->getHeader()->getFirstNonPHIOrDbgOrLifetime(); 248 } 249 250 return CreateBreak(Insert); 251 } 252 253 // Insert IfBreak in the loop header TERM for constant COND other than true. 254 if (isa<Constant>(Cond)) { 255 Instruction *Insert = Cond == BoolTrue ? 256 Term : L->getHeader()->getTerminator(); 257 258 return CreateBreak(Insert); 259 } 260 261 if (isa<Argument>(Cond)) { 262 Instruction *Insert = L->getHeader()->getFirstNonPHIOrDbgOrLifetime(); 263 return CreateBreak(Insert); 264 } 265 266 llvm_unreachable("Unhandled loop condition!"); 267 } 268 269 /// Handle a back edge (loop) handleLoop(BranchInst * Term)270 bool SIAnnotateControlFlow::handleLoop(BranchInst *Term) { 271 if (isUniform(Term)) 272 return false; 273 274 BasicBlock *BB = Term->getParent(); 275 llvm::Loop *L = LI->getLoopFor(BB); 276 if (!L) 277 return false; 278 279 BasicBlock *Target = Term->getSuccessor(1); 280 PHINode *Broken = PHINode::Create(IntMask, 0, "phi.broken"); 281 Broken->insertBefore(Target->begin()); 282 283 Value *Cond = Term->getCondition(); 284 Term->setCondition(BoolTrue); 285 Value *Arg = handleLoopCondition(Cond, Broken, L, Term); 286 287 for (BasicBlock *Pred : predecessors(Target)) { 288 Value *PHIValue = IntMaskZero; 289 if (Pred == BB) // Remember the value of the previous iteration. 290 PHIValue = Arg; 291 // If the backedge from Pred to Target could be executed before the exit 292 // of the loop at BB, it should not reset or change "Broken", which keeps 293 // track of the number of threads exited the loop at BB. 294 else if (L->contains(Pred) && DT->dominates(Pred, BB)) 295 PHIValue = Broken; 296 Broken->addIncoming(PHIValue, Pred); 297 } 298 299 CallInst *LoopCall = IRBuilder<>(Term).CreateCall(Loop, {Arg}); 300 Term->setCondition(LoopCall); 301 302 push(Term->getSuccessor(0), Arg); 303 304 return true; 305 } 306 307 /// Close the last opened control flow closeControlFlow(BasicBlock * BB)308 bool SIAnnotateControlFlow::closeControlFlow(BasicBlock *BB) { 309 llvm::Loop *L = LI->getLoopFor(BB); 310 311 assert(Stack.back().first == BB); 312 313 if (L && L->getHeader() == BB) { 314 // We can't insert an EndCF call into a loop header, because it will 315 // get executed on every iteration of the loop, when it should be 316 // executed only once before the loop. 317 SmallVector <BasicBlock *, 8> Latches; 318 L->getLoopLatches(Latches); 319 320 SmallVector<BasicBlock *, 2> Preds; 321 for (BasicBlock *Pred : predecessors(BB)) { 322 if (!is_contained(Latches, Pred)) 323 Preds.push_back(Pred); 324 } 325 326 BB = SplitBlockPredecessors(BB, Preds, "endcf.split", DT, LI, nullptr, 327 false); 328 } 329 330 Value *Exec = popSaved(); 331 BasicBlock::iterator FirstInsertionPt = BB->getFirstInsertionPt(); 332 if (!isa<UndefValue>(Exec) && !isa<UnreachableInst>(FirstInsertionPt)) { 333 Instruction *ExecDef = cast<Instruction>(Exec); 334 BasicBlock *DefBB = ExecDef->getParent(); 335 if (!DT->dominates(DefBB, BB)) { 336 // Split edge to make Def dominate Use 337 FirstInsertionPt = SplitEdge(DefBB, BB, DT, LI)->getFirstInsertionPt(); 338 } 339 IRBuilder<> IRB(FirstInsertionPt->getParent(), FirstInsertionPt); 340 // TODO: StructurizeCFG 'Flow' blocks have debug locations from the 341 // condition, for now just avoid copying these DebugLocs so that stepping 342 // out of the then/else block in a debugger doesn't step to the condition. 343 IRB.SetCurrentDebugLocation(DebugLoc()); 344 IRB.CreateCall(EndCf, {Exec}); 345 } 346 347 return true; 348 } 349 350 /// Annotate the control flow with intrinsics so the backend can 351 /// recognize if/then/else and loops. runOnFunction(Function & F)352 bool SIAnnotateControlFlow::runOnFunction(Function &F) { 353 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 354 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 355 UA = &getAnalysis<UniformityInfoWrapperPass>().getUniformityInfo(); 356 TargetPassConfig &TPC = getAnalysis<TargetPassConfig>(); 357 const TargetMachine &TM = TPC.getTM<TargetMachine>(); 358 359 bool Changed = false; 360 initialize(*F.getParent(), TM.getSubtarget<GCNSubtarget>(F)); 361 for (df_iterator<BasicBlock *> I = df_begin(&F.getEntryBlock()), 362 E = df_end(&F.getEntryBlock()); I != E; ++I) { 363 BasicBlock *BB = *I; 364 BranchInst *Term = dyn_cast<BranchInst>(BB->getTerminator()); 365 366 if (!Term || Term->isUnconditional()) { 367 if (isTopOfStack(BB)) 368 Changed |= closeControlFlow(BB); 369 370 continue; 371 } 372 373 if (I.nodeVisited(Term->getSuccessor(1))) { 374 if (isTopOfStack(BB)) 375 Changed |= closeControlFlow(BB); 376 377 if (DT->dominates(Term->getSuccessor(1), BB)) 378 Changed |= handleLoop(Term); 379 continue; 380 } 381 382 if (isTopOfStack(BB)) { 383 PHINode *Phi = dyn_cast<PHINode>(Term->getCondition()); 384 if (Phi && Phi->getParent() == BB && isElse(Phi) && !hasKill(BB)) { 385 Changed |= insertElse(Term); 386 Changed |= eraseIfUnused(Phi); 387 continue; 388 } 389 390 Changed |= closeControlFlow(BB); 391 } 392 393 Changed |= openIf(Term); 394 } 395 396 if (!Stack.empty()) { 397 // CFG was probably not structured. 398 report_fatal_error("failed to annotate CFG"); 399 } 400 401 return Changed; 402 } 403 404 /// Create the annotation pass createSIAnnotateControlFlowPass()405 FunctionPass *llvm::createSIAnnotateControlFlowPass() { 406 return new SIAnnotateControlFlow(); 407 } 408