LCOV - code coverage report
Current view: top level - lib/Target/AMDGPU - SIAnnotateControlFlow.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 154 163 94.5 %
Date: 2017-09-14 15:23:50 Functions: 15 16 93.8 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13