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 94 SIAnnotateControlFlow() : FunctionPass(ID) {} 95 96 bool runOnFunction(Function &F) override; 97 98 StringRef getPassName() const override { return "SI annotate control flow"; } 99 100 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 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? 149 bool SIAnnotateControlFlow::isUniform(BranchInst *T) { 150 return UA->isUniform(T) || 151 T->getMetadata("structurizecfg.uniform") != nullptr; 152 } 153 154 /// Is BB the last block saved on the stack ? 155 bool SIAnnotateControlFlow::isTopOfStack(BasicBlock *BB) { 156 return !Stack.empty() && Stack.back().first == BB; 157 } 158 159 /// Pop the last saved value from the control flow stack 160 Value *SIAnnotateControlFlow::popSaved() { 161 return Stack.pop_back_val().second; 162 } 163 164 /// Push a BB and saved value to the control flow stack 165 void SIAnnotateControlFlow::push(BasicBlock *BB, Value *Saved) { 166 Stack.push_back(std::pair(BB, Saved)); 167 } 168 169 /// Can the condition represented by this PHI node treated like 170 /// an "Else" block? 171 bool SIAnnotateControlFlow::isElse(PHINode *Phi) { 172 BasicBlock *IDom = DT->getNode(Phi->getParent())->getIDom()->getBlock(); 173 for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) { 174 if (Phi->getIncomingBlock(i) == IDom) { 175 176 if (Phi->getIncomingValue(i) != BoolTrue) 177 return false; 178 179 } else { 180 if (Phi->getIncomingValue(i) != BoolFalse) 181 return false; 182 183 } 184 } 185 return true; 186 } 187 188 bool SIAnnotateControlFlow::hasKill(const BasicBlock *BB) { 189 for (const Instruction &I : *BB) { 190 if (const CallInst *CI = dyn_cast<CallInst>(&I)) 191 if (CI->getIntrinsicID() == Intrinsic::amdgcn_kill) 192 return true; 193 } 194 return false; 195 } 196 197 // Erase "Phi" if it is not used any more. Return true if any change was made. 198 bool SIAnnotateControlFlow::eraseIfUnused(PHINode *Phi) { 199 bool Changed = RecursivelyDeleteDeadPHINode(Phi); 200 if (Changed) 201 LLVM_DEBUG(dbgs() << "Erased unused condition phi\n"); 202 return Changed; 203 } 204 205 /// Open a new "If" block 206 bool SIAnnotateControlFlow::openIf(BranchInst *Term) { 207 if (isUniform(Term)) 208 return false; 209 210 IRBuilder<> IRB(Term); 211 Value *IfCall = IRB.CreateCall(If, {Term->getCondition()}); 212 Value *Cond = IRB.CreateExtractValue(IfCall, {0}); 213 Value *Mask = IRB.CreateExtractValue(IfCall, {1}); 214 Term->setCondition(Cond); 215 push(Term->getSuccessor(1), Mask); 216 return true; 217 } 218 219 /// Close the last "If" block and open a new "Else" block 220 bool SIAnnotateControlFlow::insertElse(BranchInst *Term) { 221 if (isUniform(Term)) { 222 return false; 223 } 224 225 IRBuilder<> IRB(Term); 226 Value *ElseCall = IRB.CreateCall(Else, {popSaved()}); 227 Value *Cond = IRB.CreateExtractValue(ElseCall, {0}); 228 Value *Mask = IRB.CreateExtractValue(ElseCall, {1}); 229 Term->setCondition(Cond); 230 push(Term->getSuccessor(1), Mask); 231 return true; 232 } 233 234 /// Recursively handle the condition leading to a loop 235 Value *SIAnnotateControlFlow::handleLoopCondition( 236 Value *Cond, PHINode *Broken, llvm::Loop *L, BranchInst *Term) { 237 238 auto CreateBreak = [this, Cond, Broken](Instruction *I) -> CallInst * { 239 return IRBuilder<>(I).CreateCall(IfBreak, {Cond, Broken}); 240 }; 241 242 if (Instruction *Inst = dyn_cast<Instruction>(Cond)) { 243 BasicBlock *Parent = Inst->getParent(); 244 Instruction *Insert; 245 if (L->contains(Inst)) { 246 Insert = Parent->getTerminator(); 247 } else { 248 Insert = L->getHeader()->getFirstNonPHIOrDbgOrLifetime(); 249 } 250 251 return CreateBreak(Insert); 252 } 253 254 // Insert IfBreak in the loop header TERM for constant COND other than true. 255 if (isa<Constant>(Cond)) { 256 Instruction *Insert = Cond == BoolTrue ? 257 Term : L->getHeader()->getTerminator(); 258 259 return CreateBreak(Insert); 260 } 261 262 if (isa<Argument>(Cond)) { 263 Instruction *Insert = L->getHeader()->getFirstNonPHIOrDbgOrLifetime(); 264 return CreateBreak(Insert); 265 } 266 267 llvm_unreachable("Unhandled loop condition!"); 268 } 269 270 /// Handle a back edge (loop) 271 bool SIAnnotateControlFlow::handleLoop(BranchInst *Term) { 272 if (isUniform(Term)) 273 return false; 274 275 BasicBlock *BB = Term->getParent(); 276 llvm::Loop *L = LI->getLoopFor(BB); 277 if (!L) 278 return false; 279 280 BasicBlock *Target = Term->getSuccessor(1); 281 PHINode *Broken = PHINode::Create(IntMask, 0, "phi.broken"); 282 Broken->insertBefore(Target->begin()); 283 284 Value *Cond = Term->getCondition(); 285 Term->setCondition(BoolTrue); 286 Value *Arg = handleLoopCondition(Cond, Broken, L, Term); 287 288 for (BasicBlock *Pred : predecessors(Target)) { 289 Value *PHIValue = IntMaskZero; 290 if (Pred == BB) // Remember the value of the previous iteration. 291 PHIValue = Arg; 292 // If the backedge from Pred to Target could be executed before the exit 293 // of the loop at BB, it should not reset or change "Broken", which keeps 294 // track of the number of threads exited the loop at BB. 295 else if (L->contains(Pred) && DT->dominates(Pred, BB)) 296 PHIValue = Broken; 297 Broken->addIncoming(PHIValue, Pred); 298 } 299 300 CallInst *LoopCall = IRBuilder<>(Term).CreateCall(Loop, {Arg}); 301 Term->setCondition(LoopCall); 302 303 push(Term->getSuccessor(0), Arg); 304 305 return true; 306 } 307 308 /// Close the last opened control flow 309 bool SIAnnotateControlFlow::closeControlFlow(BasicBlock *BB) { 310 llvm::Loop *L = LI->getLoopFor(BB); 311 312 assert(Stack.back().first == BB); 313 314 if (L && L->getHeader() == BB) { 315 // We can't insert an EndCF call into a loop header, because it will 316 // get executed on every iteration of the loop, when it should be 317 // executed only once before the loop. 318 SmallVector <BasicBlock *, 8> Latches; 319 L->getLoopLatches(Latches); 320 321 SmallVector<BasicBlock *, 2> Preds; 322 for (BasicBlock *Pred : predecessors(BB)) { 323 if (!is_contained(Latches, Pred)) 324 Preds.push_back(Pred); 325 } 326 327 BB = SplitBlockPredecessors(BB, Preds, "endcf.split", DT, LI, nullptr, 328 false); 329 } 330 331 Value *Exec = popSaved(); 332 BasicBlock::iterator FirstInsertionPt = BB->getFirstInsertionPt(); 333 if (!isa<UndefValue>(Exec) && !isa<UnreachableInst>(FirstInsertionPt)) { 334 Instruction *ExecDef = cast<Instruction>(Exec); 335 BasicBlock *DefBB = ExecDef->getParent(); 336 if (!DT->dominates(DefBB, BB)) { 337 // Split edge to make Def dominate Use 338 FirstInsertionPt = SplitEdge(DefBB, BB, DT, LI)->getFirstInsertionPt(); 339 } 340 IRBuilder<>(FirstInsertionPt->getParent(), FirstInsertionPt) 341 .CreateCall(EndCf, {Exec}); 342 } 343 344 return true; 345 } 346 347 /// Annotate the control flow with intrinsics so the backend can 348 /// recognize if/then/else and loops. 349 bool SIAnnotateControlFlow::runOnFunction(Function &F) { 350 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 351 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 352 UA = &getAnalysis<UniformityInfoWrapperPass>().getUniformityInfo(); 353 TargetPassConfig &TPC = getAnalysis<TargetPassConfig>(); 354 const TargetMachine &TM = TPC.getTM<TargetMachine>(); 355 356 bool Changed = false; 357 initialize(*F.getParent(), TM.getSubtarget<GCNSubtarget>(F)); 358 for (df_iterator<BasicBlock *> I = df_begin(&F.getEntryBlock()), 359 E = df_end(&F.getEntryBlock()); I != E; ++I) { 360 BasicBlock *BB = *I; 361 BranchInst *Term = dyn_cast<BranchInst>(BB->getTerminator()); 362 363 if (!Term || Term->isUnconditional()) { 364 if (isTopOfStack(BB)) 365 Changed |= closeControlFlow(BB); 366 367 continue; 368 } 369 370 if (I.nodeVisited(Term->getSuccessor(1))) { 371 if (isTopOfStack(BB)) 372 Changed |= closeControlFlow(BB); 373 374 if (DT->dominates(Term->getSuccessor(1), BB)) 375 Changed |= handleLoop(Term); 376 continue; 377 } 378 379 if (isTopOfStack(BB)) { 380 PHINode *Phi = dyn_cast<PHINode>(Term->getCondition()); 381 if (Phi && Phi->getParent() == BB && isElse(Phi) && !hasKill(BB)) { 382 Changed |= insertElse(Term); 383 Changed |= eraseIfUnused(Phi); 384 continue; 385 } 386 387 Changed |= closeControlFlow(BB); 388 } 389 390 Changed |= openIf(Term); 391 } 392 393 if (!Stack.empty()) { 394 // CFG was probably not structured. 395 report_fatal_error("failed to annotate CFG"); 396 } 397 398 return Changed; 399 } 400 401 /// Create the annotation pass 402 FunctionPass *llvm::createSIAnnotateControlFlowPass() { 403 return new SIAnnotateControlFlow(); 404 } 405