1249259Sdim//===-- SIAnnotateControlFlow.cpp - ------------------===// 2249259Sdim// 3249259Sdim// The LLVM Compiler Infrastructure 4249259Sdim// 5249259Sdim// This file is distributed under the University of Illinois Open Source 6249259Sdim// License. See LICENSE.TXT for details. 7249259Sdim// 8249259Sdim//===----------------------------------------------------------------------===// 9249259Sdim// 10249259Sdim/// \file 11249259Sdim/// Annotates the control flow with hardware specific intrinsics. 12249259Sdim// 13249259Sdim//===----------------------------------------------------------------------===// 14249259Sdim 15249259Sdim#include "AMDGPU.h" 16249259Sdim#include "llvm/ADT/DepthFirstIterator.h" 17249259Sdim#include "llvm/Analysis/Dominators.h" 18263508Sdim#include "llvm/IR/Constants.h" 19263508Sdim#include "llvm/IR/Instructions.h" 20249259Sdim#include "llvm/IR/Module.h" 21249259Sdim#include "llvm/Pass.h" 22249259Sdim#include "llvm/Transforms/Utils/BasicBlockUtils.h" 23249259Sdim#include "llvm/Transforms/Utils/SSAUpdater.h" 24249259Sdim 25249259Sdimusing namespace llvm; 26249259Sdim 27249259Sdimnamespace { 28249259Sdim 29249259Sdim// Complex types used in this pass 30249259Sdimtypedef std::pair<BasicBlock *, Value *> StackEntry; 31249259Sdimtypedef SmallVector<StackEntry, 16> StackVector; 32249259Sdim 33249259Sdim// Intrinsic names the control flow is annotated with 34263508Sdimstatic const char *const IfIntrinsic = "llvm.SI.if"; 35263508Sdimstatic const char *const ElseIntrinsic = "llvm.SI.else"; 36263508Sdimstatic const char *const BreakIntrinsic = "llvm.SI.break"; 37263508Sdimstatic const char *const IfBreakIntrinsic = "llvm.SI.if.break"; 38263508Sdimstatic const char *const ElseBreakIntrinsic = "llvm.SI.else.break"; 39263508Sdimstatic const char *const LoopIntrinsic = "llvm.SI.loop"; 40263508Sdimstatic const char *const EndCfIntrinsic = "llvm.SI.end.cf"; 41249259Sdim 42249259Sdimclass SIAnnotateControlFlow : public FunctionPass { 43249259Sdim 44249259Sdim static char ID; 45249259Sdim 46249259Sdim Type *Boolean; 47249259Sdim Type *Void; 48249259Sdim Type *Int64; 49249259Sdim Type *ReturnStruct; 50249259Sdim 51249259Sdim ConstantInt *BoolTrue; 52249259Sdim ConstantInt *BoolFalse; 53249259Sdim UndefValue *BoolUndef; 54249259Sdim Constant *Int64Zero; 55249259Sdim 56249259Sdim Constant *If; 57249259Sdim Constant *Else; 58249259Sdim Constant *Break; 59249259Sdim Constant *IfBreak; 60249259Sdim Constant *ElseBreak; 61249259Sdim Constant *Loop; 62249259Sdim Constant *EndCf; 63249259Sdim 64249259Sdim DominatorTree *DT; 65249259Sdim StackVector Stack; 66249259Sdim SSAUpdater PhiInserter; 67249259Sdim 68249259Sdim bool isTopOfStack(BasicBlock *BB); 69249259Sdim 70249259Sdim Value *popSaved(); 71249259Sdim 72249259Sdim void push(BasicBlock *BB, Value *Saved); 73249259Sdim 74249259Sdim bool isElse(PHINode *Phi); 75249259Sdim 76249259Sdim void eraseIfUnused(PHINode *Phi); 77249259Sdim 78249259Sdim void openIf(BranchInst *Term); 79249259Sdim 80249259Sdim void insertElse(BranchInst *Term); 81249259Sdim 82249259Sdim void handleLoopCondition(Value *Cond); 83249259Sdim 84249259Sdim void handleLoop(BranchInst *Term); 85249259Sdim 86249259Sdim void closeControlFlow(BasicBlock *BB); 87249259Sdim 88249259Sdimpublic: 89249259Sdim SIAnnotateControlFlow(): 90249259Sdim FunctionPass(ID) { } 91249259Sdim 92249259Sdim virtual bool doInitialization(Module &M); 93249259Sdim 94249259Sdim virtual bool runOnFunction(Function &F); 95249259Sdim 96249259Sdim virtual const char *getPassName() const { 97249259Sdim return "SI annotate control flow"; 98249259Sdim } 99249259Sdim 100249259Sdim virtual void getAnalysisUsage(AnalysisUsage &AU) const { 101249259Sdim AU.addRequired<DominatorTree>(); 102249259Sdim AU.addPreserved<DominatorTree>(); 103249259Sdim FunctionPass::getAnalysisUsage(AU); 104249259Sdim } 105249259Sdim 106249259Sdim}; 107249259Sdim 108249259Sdim} // end anonymous namespace 109249259Sdim 110249259Sdimchar SIAnnotateControlFlow::ID = 0; 111249259Sdim 112249259Sdim/// \brief Initialize all the types and constants used in the pass 113249259Sdimbool SIAnnotateControlFlow::doInitialization(Module &M) { 114249259Sdim LLVMContext &Context = M.getContext(); 115249259Sdim 116249259Sdim Void = Type::getVoidTy(Context); 117249259Sdim Boolean = Type::getInt1Ty(Context); 118249259Sdim Int64 = Type::getInt64Ty(Context); 119249259Sdim ReturnStruct = StructType::get(Boolean, Int64, (Type *)0); 120249259Sdim 121249259Sdim BoolTrue = ConstantInt::getTrue(Context); 122249259Sdim BoolFalse = ConstantInt::getFalse(Context); 123249259Sdim BoolUndef = UndefValue::get(Boolean); 124249259Sdim Int64Zero = ConstantInt::get(Int64, 0); 125249259Sdim 126249259Sdim If = M.getOrInsertFunction( 127249259Sdim IfIntrinsic, ReturnStruct, Boolean, (Type *)0); 128249259Sdim 129249259Sdim Else = M.getOrInsertFunction( 130249259Sdim ElseIntrinsic, ReturnStruct, Int64, (Type *)0); 131249259Sdim 132249259Sdim Break = M.getOrInsertFunction( 133249259Sdim BreakIntrinsic, Int64, Int64, (Type *)0); 134249259Sdim 135249259Sdim IfBreak = M.getOrInsertFunction( 136249259Sdim IfBreakIntrinsic, Int64, Boolean, Int64, (Type *)0); 137249259Sdim 138249259Sdim ElseBreak = M.getOrInsertFunction( 139249259Sdim ElseBreakIntrinsic, Int64, Int64, Int64, (Type *)0); 140249259Sdim 141249259Sdim Loop = M.getOrInsertFunction( 142249259Sdim LoopIntrinsic, Boolean, Int64, (Type *)0); 143249259Sdim 144249259Sdim EndCf = M.getOrInsertFunction( 145249259Sdim EndCfIntrinsic, Void, Int64, (Type *)0); 146249259Sdim 147249259Sdim return false; 148249259Sdim} 149249259Sdim 150249259Sdim/// \brief Is BB the last block saved on the stack ? 151249259Sdimbool SIAnnotateControlFlow::isTopOfStack(BasicBlock *BB) { 152249259Sdim return !Stack.empty() && Stack.back().first == BB; 153249259Sdim} 154249259Sdim 155249259Sdim/// \brief Pop the last saved value from the control flow stack 156249259SdimValue *SIAnnotateControlFlow::popSaved() { 157249259Sdim return Stack.pop_back_val().second; 158249259Sdim} 159249259Sdim 160249259Sdim/// \brief Push a BB and saved value to the control flow stack 161249259Sdimvoid SIAnnotateControlFlow::push(BasicBlock *BB, Value *Saved) { 162249259Sdim Stack.push_back(std::make_pair(BB, Saved)); 163249259Sdim} 164249259Sdim 165249259Sdim/// \brief Can the condition represented by this PHI node treated like 166249259Sdim/// an "Else" block? 167249259Sdimbool SIAnnotateControlFlow::isElse(PHINode *Phi) { 168249259Sdim BasicBlock *IDom = DT->getNode(Phi->getParent())->getIDom()->getBlock(); 169249259Sdim for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) { 170249259Sdim if (Phi->getIncomingBlock(i) == IDom) { 171249259Sdim 172249259Sdim if (Phi->getIncomingValue(i) != BoolTrue) 173249259Sdim return false; 174249259Sdim 175249259Sdim } else { 176249259Sdim if (Phi->getIncomingValue(i) != BoolFalse) 177249259Sdim return false; 178249259Sdim 179249259Sdim } 180249259Sdim } 181249259Sdim return true; 182249259Sdim} 183249259Sdim 184249259Sdim// \brief Erase "Phi" if it is not used any more 185249259Sdimvoid SIAnnotateControlFlow::eraseIfUnused(PHINode *Phi) { 186249259Sdim if (!Phi->hasNUsesOrMore(1)) 187249259Sdim Phi->eraseFromParent(); 188249259Sdim} 189249259Sdim 190249259Sdim/// \brief Open a new "If" block 191249259Sdimvoid SIAnnotateControlFlow::openIf(BranchInst *Term) { 192249259Sdim Value *Ret = CallInst::Create(If, Term->getCondition(), "", Term); 193249259Sdim Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term)); 194249259Sdim push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term)); 195249259Sdim} 196249259Sdim 197249259Sdim/// \brief Close the last "If" block and open a new "Else" block 198249259Sdimvoid SIAnnotateControlFlow::insertElse(BranchInst *Term) { 199249259Sdim Value *Ret = CallInst::Create(Else, popSaved(), "", Term); 200249259Sdim Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term)); 201249259Sdim push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term)); 202249259Sdim} 203249259Sdim 204249259Sdim/// \brief Recursively handle the condition leading to a loop 205249259Sdimvoid SIAnnotateControlFlow::handleLoopCondition(Value *Cond) { 206249259Sdim if (PHINode *Phi = dyn_cast<PHINode>(Cond)) { 207249259Sdim 208249259Sdim // Handle all non constant incoming values first 209249259Sdim for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) { 210249259Sdim Value *Incoming = Phi->getIncomingValue(i); 211249259Sdim if (isa<ConstantInt>(Incoming)) 212249259Sdim continue; 213249259Sdim 214249259Sdim Phi->setIncomingValue(i, BoolFalse); 215249259Sdim handleLoopCondition(Incoming); 216249259Sdim } 217249259Sdim 218249259Sdim BasicBlock *Parent = Phi->getParent(); 219249259Sdim BasicBlock *IDom = DT->getNode(Parent)->getIDom()->getBlock(); 220249259Sdim 221249259Sdim for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) { 222249259Sdim 223249259Sdim Value *Incoming = Phi->getIncomingValue(i); 224249259Sdim if (Incoming != BoolTrue) 225249259Sdim continue; 226249259Sdim 227249259Sdim BasicBlock *From = Phi->getIncomingBlock(i); 228249259Sdim if (From == IDom) { 229249259Sdim CallInst *OldEnd = dyn_cast<CallInst>(Parent->getFirstInsertionPt()); 230249259Sdim if (OldEnd && OldEnd->getCalledFunction() == EndCf) { 231249259Sdim Value *Args[] = { 232249259Sdim OldEnd->getArgOperand(0), 233249259Sdim PhiInserter.GetValueAtEndOfBlock(Parent) 234249259Sdim }; 235249259Sdim Value *Ret = CallInst::Create(ElseBreak, Args, "", OldEnd); 236249259Sdim PhiInserter.AddAvailableValue(Parent, Ret); 237249259Sdim continue; 238249259Sdim } 239249259Sdim } 240249259Sdim 241249259Sdim TerminatorInst *Insert = From->getTerminator(); 242249259Sdim Value *Arg = PhiInserter.GetValueAtEndOfBlock(From); 243249259Sdim Value *Ret = CallInst::Create(Break, Arg, "", Insert); 244249259Sdim PhiInserter.AddAvailableValue(From, Ret); 245249259Sdim } 246249259Sdim eraseIfUnused(Phi); 247249259Sdim 248249259Sdim } else if (Instruction *Inst = dyn_cast<Instruction>(Cond)) { 249249259Sdim BasicBlock *Parent = Inst->getParent(); 250249259Sdim TerminatorInst *Insert = Parent->getTerminator(); 251249259Sdim Value *Args[] = { Cond, PhiInserter.GetValueAtEndOfBlock(Parent) }; 252249259Sdim Value *Ret = CallInst::Create(IfBreak, Args, "", Insert); 253249259Sdim PhiInserter.AddAvailableValue(Parent, Ret); 254249259Sdim 255249259Sdim } else { 256249259Sdim assert(0 && "Unhandled loop condition!"); 257249259Sdim } 258249259Sdim} 259249259Sdim 260249259Sdim/// \brief Handle a back edge (loop) 261249259Sdimvoid SIAnnotateControlFlow::handleLoop(BranchInst *Term) { 262249259Sdim BasicBlock *Target = Term->getSuccessor(1); 263249259Sdim PHINode *Broken = PHINode::Create(Int64, 0, "", &Target->front()); 264249259Sdim 265249259Sdim PhiInserter.Initialize(Int64, ""); 266249259Sdim PhiInserter.AddAvailableValue(Target, Broken); 267249259Sdim 268249259Sdim Value *Cond = Term->getCondition(); 269249259Sdim Term->setCondition(BoolTrue); 270249259Sdim handleLoopCondition(Cond); 271249259Sdim 272249259Sdim BasicBlock *BB = Term->getParent(); 273249259Sdim Value *Arg = PhiInserter.GetValueAtEndOfBlock(BB); 274249259Sdim for (pred_iterator PI = pred_begin(Target), PE = pred_end(Target); 275249259Sdim PI != PE; ++PI) { 276249259Sdim 277249259Sdim Broken->addIncoming(*PI == BB ? Arg : Int64Zero, *PI); 278249259Sdim } 279249259Sdim 280249259Sdim Term->setCondition(CallInst::Create(Loop, Arg, "", Term)); 281249259Sdim push(Term->getSuccessor(0), Arg); 282249259Sdim} 283249259Sdim 284249259Sdim/// \brief Close the last opened control flow 285249259Sdimvoid SIAnnotateControlFlow::closeControlFlow(BasicBlock *BB) { 286249259Sdim CallInst::Create(EndCf, popSaved(), "", BB->getFirstInsertionPt()); 287249259Sdim} 288249259Sdim 289249259Sdim/// \brief Annotate the control flow with intrinsics so the backend can 290249259Sdim/// recognize if/then/else and loops. 291249259Sdimbool SIAnnotateControlFlow::runOnFunction(Function &F) { 292249259Sdim DT = &getAnalysis<DominatorTree>(); 293249259Sdim 294249259Sdim for (df_iterator<BasicBlock *> I = df_begin(&F.getEntryBlock()), 295249259Sdim E = df_end(&F.getEntryBlock()); I != E; ++I) { 296249259Sdim 297249259Sdim BranchInst *Term = dyn_cast<BranchInst>((*I)->getTerminator()); 298249259Sdim 299249259Sdim if (!Term || Term->isUnconditional()) { 300249259Sdim if (isTopOfStack(*I)) 301249259Sdim closeControlFlow(*I); 302249259Sdim continue; 303249259Sdim } 304249259Sdim 305249259Sdim if (I.nodeVisited(Term->getSuccessor(1))) { 306249259Sdim if (isTopOfStack(*I)) 307249259Sdim closeControlFlow(*I); 308249259Sdim handleLoop(Term); 309249259Sdim continue; 310249259Sdim } 311249259Sdim 312249259Sdim if (isTopOfStack(*I)) { 313249259Sdim PHINode *Phi = dyn_cast<PHINode>(Term->getCondition()); 314249259Sdim if (Phi && Phi->getParent() == *I && isElse(Phi)) { 315249259Sdim insertElse(Term); 316249259Sdim eraseIfUnused(Phi); 317249259Sdim continue; 318249259Sdim } 319249259Sdim closeControlFlow(*I); 320249259Sdim } 321249259Sdim openIf(Term); 322249259Sdim } 323249259Sdim 324249259Sdim assert(Stack.empty()); 325249259Sdim return true; 326249259Sdim} 327249259Sdim 328249259Sdim/// \brief Create the annotation pass 329249259SdimFunctionPass *llvm::createSIAnnotateControlFlowPass() { 330249259Sdim return new SIAnnotateControlFlow(); 331249259Sdim} 332