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