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 26using namespace llvm; 27 28#define DEBUG_TYPE "si-annotate-control-flow" 29 30namespace { 31 32// Complex types used in this pass 33typedef std::pair<BasicBlock *, Value *> StackEntry; 34typedef SmallVector<StackEntry, 16> StackVector; 35 36// Intrinsic names the control flow is annotated with 37static const char *const IfIntrinsic = "llvm.SI.if"; 38static const char *const ElseIntrinsic = "llvm.SI.else"; 39static const char *const BreakIntrinsic = "llvm.SI.break"; 40static const char *const IfBreakIntrinsic = "llvm.SI.if.break"; 41static const char *const ElseBreakIntrinsic = "llvm.SI.else.break"; 42static const char *const LoopIntrinsic = "llvm.SI.loop"; 43static const char *const EndCfIntrinsic = "llvm.SI.end.cf"; 44 45class 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 92public: 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 115char SIAnnotateControlFlow::ID = 0; 116 117/// \brief Initialize all the types and constants used in the pass 118bool 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 ? 156bool 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 161Value *SIAnnotateControlFlow::popSaved() { 162 return Stack.pop_back_val().second; 163} 164 165/// \brief Push a BB and saved value to the control flow stack 166void 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? 172bool 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 190void SIAnnotateControlFlow::eraseIfUnused(PHINode *Phi) { 191 if (!Phi->hasNUsesOrMore(1)) 192 Phi->eraseFromParent(); 193} 194 195/// \brief Open a new "If" block 196void 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 203void 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 210Value *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) 273void 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 292void 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. 316bool 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 355FunctionPass *llvm::createSIAnnotateControlFlowPass() { 356 return new SIAnnotateControlFlow(); 357} 358