Home | History | Annotate | Download | only in R600 
      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/Analysis/LoopInfo.h"
     18 #include "llvm/IR/Constants.h"
     19 #include "llvm/IR/Dominators.h"
     20 #include "llvm/IR/Instructions.h"
     21 #include "llvm/IR/Module.h"
     22 #include "llvm/Pass.h"
     23 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
     24 #include "llvm/Transforms/Utils/SSAUpdater.h"
     25 
     26 using namespace llvm;
     27 
     28 #define DEBUG_TYPE "si-annotate-control-flow"
     29 
     30 namespace {
     31 
     32 // Complex types used in this pass
     33 typedef std::pair<BasicBlock *, Value *> StackEntry;
     34 typedef SmallVector<StackEntry, 16> StackVector;
     35 
     36 // Intrinsic names the control flow is annotated with
     37 static const char *const IfIntrinsic = "llvm.SI.if";
     38 static const char *const ElseIntrinsic = "llvm.SI.else";
     39 static const char *const BreakIntrinsic = "llvm.SI.break";
     40 static const char *const IfBreakIntrinsic = "llvm.SI.if.break";
     41 static const char *const ElseBreakIntrinsic = "llvm.SI.else.break";
     42 static const char *const LoopIntrinsic = "llvm.SI.loop";
     43 static const char *const EndCfIntrinsic = "llvm.SI.end.cf";
     44 
     45 class SIAnnotateControlFlow : public FunctionPass {
     46 
     47   static char ID;
     48 
     49   Type *Boolean;
     50   Type *Void;
     51   Type *Int64;
     52   Type *ReturnStruct;
     53 
     54   ConstantInt *BoolTrue;
     55   ConstantInt *BoolFalse;
     56   UndefValue *BoolUndef;
     57   Constant *Int64Zero;
     58 
     59   Constant *If;
     60   Constant *Else;
     61   Constant *Break;
     62   Constant *IfBreak;
     63   Constant *ElseBreak;
     64   Constant *Loop;
     65   Constant *EndCf;
     66 
     67   DominatorTree *DT;
     68   StackVector Stack;
     69 
     70   LoopInfo *LI;
     71 
     72   bool isTopOfStack(BasicBlock *BB);
     73 
     74   Value *popSaved();
     75 
     76   void push(BasicBlock *BB, Value *Saved);
     77 
     78   bool isElse(PHINode *Phi);
     79 
     80   void eraseIfUnused(PHINode *Phi);
     81 
     82   void openIf(BranchInst *Term);
     83 
     84   void insertElse(BranchInst *Term);
     85 
     86   Value *handleLoopCondition(Value *Cond, PHINode *Broken, llvm::Loop *L);
     87 
     88   void handleLoop(BranchInst *Term);
     89 
     90   void closeControlFlow(BasicBlock *BB);
     91 
     92 public:
     93   SIAnnotateControlFlow():
     94     FunctionPass(ID) { }
     95 
     96   bool doInitialization(Module &M) override;
     97 
     98   bool runOnFunction(Function &F) override;
     99 
    100   const char *getPassName() const override {
    101     return "SI annotate control flow";
    102   }
    103 
    104   void getAnalysisUsage(AnalysisUsage &AU) const override {
    105     AU.addRequired<LoopInfoWrapperPass>();
    106     AU.addRequired<DominatorTreeWrapperPass>();
    107     AU.addPreserved<DominatorTreeWrapperPass>();
    108     FunctionPass::getAnalysisUsage(AU);
    109   }
    110 
    111 };
    112 
    113 } // end anonymous namespace
    114 
    115 char SIAnnotateControlFlow::ID = 0;
    116 
    117 /// \brief Initialize all the types and constants used in the pass
    118 bool SIAnnotateControlFlow::doInitialization(Module &M) {
    119   LLVMContext &Context = M.getContext();
    120 
    121   Void = Type::getVoidTy(Context);
    122   Boolean = Type::getInt1Ty(Context);
    123   Int64 = Type::getInt64Ty(Context);
    124   ReturnStruct = StructType::get(Boolean, Int64, (Type *)nullptr);
    125 
    126   BoolTrue = ConstantInt::getTrue(Context);
    127   BoolFalse = ConstantInt::getFalse(Context);
    128   BoolUndef = UndefValue::get(Boolean);
    129   Int64Zero = ConstantInt::get(Int64, 0);
    130 
    131   If = M.getOrInsertFunction(
    132     IfIntrinsic, ReturnStruct, Boolean, (Type *)nullptr);
    133 
    134   Else = M.getOrInsertFunction(
    135     ElseIntrinsic, ReturnStruct, Int64, (Type *)nullptr);
    136 
    137   Break = M.getOrInsertFunction(
    138     BreakIntrinsic, Int64, Int64, (Type *)nullptr);
    139 
    140   IfBreak = M.getOrInsertFunction(
    141     IfBreakIntrinsic, Int64, Boolean, Int64, (Type *)nullptr);
    142 
    143   ElseBreak = M.getOrInsertFunction(
    144     ElseBreakIntrinsic, Int64, Int64, Int64, (Type *)nullptr);
    145 
    146   Loop = M.getOrInsertFunction(
    147     LoopIntrinsic, Boolean, Int64, (Type *)nullptr);
    148 
    149   EndCf = M.getOrInsertFunction(
    150     EndCfIntrinsic, Void, Int64, (Type *)nullptr);
    151 
    152   return false;
    153 }
    154 
    155 /// \brief Is BB the last block saved on the stack ?
    156 bool SIAnnotateControlFlow::isTopOfStack(BasicBlock *BB) {
    157   return !Stack.empty() && Stack.back().first == BB;
    158 }
    159 
    160 /// \brief Pop the last saved value from the control flow stack
    161 Value *SIAnnotateControlFlow::popSaved() {
    162   return Stack.pop_back_val().second;
    163 }
    164 
    165 /// \brief Push a BB and saved value to the control flow stack
    166 void SIAnnotateControlFlow::push(BasicBlock *BB, Value *Saved) {
    167   Stack.push_back(std::make_pair(BB, Saved));
    168 }
    169 
    170 /// \brief Can the condition represented by this PHI node treated like
    171 /// an "Else" block?
    172 bool SIAnnotateControlFlow::isElse(PHINode *Phi) {
    173   BasicBlock *IDom = DT->getNode(Phi->getParent())->getIDom()->getBlock();
    174   for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) {
    175     if (Phi->getIncomingBlock(i) == IDom) {
    176 
    177       if (Phi->getIncomingValue(i) != BoolTrue)
    178         return false;
    179 
    180     } else {
    181       if (Phi->getIncomingValue(i) != BoolFalse)
    182         return false;
    183 
    184     }
    185   }
    186   return true;
    187 }
    188 
    189 // \brief Erase "Phi" if it is not used any more
    190 void SIAnnotateControlFlow::eraseIfUnused(PHINode *Phi) {
    191   if (!Phi->hasNUsesOrMore(1))
    192     Phi->eraseFromParent();
    193 }
    194 
    195 /// \brief Open a new "If" block
    196 void SIAnnotateControlFlow::openIf(BranchInst *Term) {
    197   Value *Ret = CallInst::Create(If, Term->getCondition(), "", Term);
    198   Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term));
    199   push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term));
    200 }
    201 
    202 /// \brief Close the last "If" block and open a new "Else" block
    203 void SIAnnotateControlFlow::insertElse(BranchInst *Term) {
    204   Value *Ret = CallInst::Create(Else, popSaved(), "", Term);
    205   Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term));
    206   push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term));
    207 }
    208 
    209 /// \brief Recursively handle the condition leading to a loop
    210 Value *SIAnnotateControlFlow::handleLoopCondition(Value *Cond, PHINode *Broken,
    211                                                   llvm::Loop *L) {
    212   if (PHINode *Phi = dyn_cast<PHINode>(Cond)) {
    213     BasicBlock *Parent = Phi->getParent();
    214     PHINode *NewPhi = PHINode::Create(Int64, 0, "", &Parent->front());
    215     Value *Ret = NewPhi;
    216 
    217     // Handle all non-constant incoming values first
    218     for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) {
    219       Value *Incoming = Phi->getIncomingValue(i);
    220       BasicBlock *From = Phi->getIncomingBlock(i);
    221       if (isa<ConstantInt>(Incoming)) {
    222         NewPhi->addIncoming(Broken, From);
    223         continue;
    224       }
    225 
    226       Phi->setIncomingValue(i, BoolFalse);
    227       Value *PhiArg = handleLoopCondition(Incoming, Broken, L);
    228       NewPhi->addIncoming(PhiArg, From);
    229     }
    230 
    231     BasicBlock *IDom = DT->getNode(Parent)->getIDom()->getBlock();
    232 
    233     for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) {
    234 
    235       Value *Incoming = Phi->getIncomingValue(i);
    236       if (Incoming != BoolTrue)
    237         continue;
    238 
    239       BasicBlock *From = Phi->getIncomingBlock(i);
    240       if (From == IDom) {
    241         CallInst *OldEnd = dyn_cast<CallInst>(Parent->getFirstInsertionPt());
    242         if (OldEnd && OldEnd->getCalledFunction() == EndCf) {
    243           Value *Args[] = { OldEnd->getArgOperand(0), NewPhi };
    244           Ret = CallInst::Create(ElseBreak, Args, "", OldEnd);
    245           continue;
    246         }
    247       }
    248       TerminatorInst *Insert = From->getTerminator();
    249       Value *PhiArg = CallInst::Create(Break, Broken, "", Insert);
    250       NewPhi->setIncomingValue(i, PhiArg);
    251     }
    252     eraseIfUnused(Phi);
    253     return Ret;
    254 
    255   } else if (Instruction *Inst = dyn_cast<Instruction>(Cond)) {
    256     BasicBlock *Parent = Inst->getParent();
    257     Instruction *Insert;
    258     if (L->contains(Inst)) {
    259       Insert = Parent->getTerminator();
    260     } else {
    261       Insert = L->getHeader()->getFirstNonPHIOrDbgOrLifetime();
    262     }
    263     Value *Args[] = { Cond, Broken };
    264     return CallInst::Create(IfBreak, Args, "", Insert);
    265 
    266   } else {
    267     llvm_unreachable("Unhandled loop condition!");
    268   }
    269   return 0;
    270 }
    271 
    272 /// \brief Handle a back edge (loop)
    273 void SIAnnotateControlFlow::handleLoop(BranchInst *Term) {
    274   BasicBlock *BB = Term->getParent();
    275   llvm::Loop *L = LI->getLoopFor(BB);
    276   BasicBlock *Target = Term->getSuccessor(1);
    277   PHINode *Broken = PHINode::Create(Int64, 0, "", &Target->front());
    278 
    279   Value *Cond = Term->getCondition();
    280   Term->setCondition(BoolTrue);
    281   Value *Arg = handleLoopCondition(Cond, Broken, L);
    282 
    283   for (pred_iterator PI = pred_begin(Target), PE = pred_end(Target);
    284        PI != PE; ++PI) {
    285 
    286     Broken->addIncoming(*PI == BB ? Arg : Int64Zero, *PI);
    287   }
    288 
    289   Term->setCondition(CallInst::Create(Loop, Arg, "", Term));
    290   push(Term->getSuccessor(0), Arg);
    291 }/// \brief Close the last opened control flow
    292 void SIAnnotateControlFlow::closeControlFlow(BasicBlock *BB) {
    293   llvm::Loop *L = LI->getLoopFor(BB);
    294 
    295   if (L && L->getHeader() == BB) {
    296     // We can't insert an EndCF call into a loop header, because it will
    297     // get executed on every iteration of the loop, when it should be
    298     // executed only once before the loop.
    299     SmallVector <BasicBlock*, 8> Latches;
    300     L->getLoopLatches(Latches);
    301 
    302     std::vector<BasicBlock*> Preds;
    303     for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
    304       if (std::find(Latches.begin(), Latches.end(), *PI) == Latches.end())
    305         Preds.push_back(*PI);
    306     }
    307     BB = llvm::SplitBlockPredecessors(BB, Preds, "endcf.split", nullptr, DT,
    308                                       LI, false);
    309   }
    310 
    311   CallInst::Create(EndCf, popSaved(), "", BB->getFirstInsertionPt());
    312 }
    313 
    314 /// \brief Annotate the control flow with intrinsics so the backend can
    315 /// recognize if/then/else and loops.
    316 bool SIAnnotateControlFlow::runOnFunction(Function &F) {
    317   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
    318   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
    319 
    320   for (df_iterator<BasicBlock *> I = df_begin(&F.getEntryBlock()),
    321        E = df_end(&F.getEntryBlock()); I != E; ++I) {
    322 
    323     BranchInst *Term = dyn_cast<BranchInst>((*I)->getTerminator());
    324 
    325     if (!Term || Term->isUnconditional()) {
    326       if (isTopOfStack(*I))
    327         closeControlFlow(*I);
    328       continue;
    329     }
    330 
    331     if (I.nodeVisited(Term->getSuccessor(1))) {
    332       if (isTopOfStack(*I))
    333         closeControlFlow(*I);
    334       handleLoop(Term);
    335       continue;
    336     }
    337 
    338     if (isTopOfStack(*I)) {
    339       PHINode *Phi = dyn_cast<PHINode>(Term->getCondition());
    340       if (Phi && Phi->getParent() == *I && isElse(Phi)) {
    341         insertElse(Term);
    342         eraseIfUnused(Phi);
    343         continue;
    344       }
    345       closeControlFlow(*I);
    346     }
    347     openIf(Term);
    348   }
    349 
    350   assert(Stack.empty());
    351   return true;
    352 }
    353 
    354 /// \brief Create the annotation pass
    355 FunctionPass *llvm::createSIAnnotateControlFlowPass() {
    356   return new SIAnnotateControlFlow();
    357 }
    358