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