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 213 // Only search through PHI nodes which are inside the loop. If we try this 214 // with PHI nodes that are outside of the loop, we end up inserting new PHI 215 // nodes outside of the loop which depend on values defined inside the loop. 216 // This will break the module with 217 // 'Instruction does not dominate all users!' errors. 218 PHINode *Phi = nullptr; 219 if ((Phi = dyn_cast<PHINode>(Cond)) && L->contains(Phi)) { 220 221 BasicBlock *Parent = Phi->getParent(); 222 PHINode *NewPhi = PHINode::Create(Int64, 0, "", &Parent->front()); 223 Value *Ret = NewPhi; 224 225 // Handle all non-constant incoming values first 226 for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) { 227 Value *Incoming = Phi->getIncomingValue(i); 228 BasicBlock *From = Phi->getIncomingBlock(i); 229 if (isa<ConstantInt>(Incoming)) { 230 NewPhi->addIncoming(Broken, From); 231 continue; 232 } 233 234 Phi->setIncomingValue(i, BoolFalse); 235 Value *PhiArg = handleLoopCondition(Incoming, Broken, L); 236 NewPhi->addIncoming(PhiArg, From); 237 } 238 239 BasicBlock *IDom = DT->getNode(Parent)->getIDom()->getBlock(); 240 241 for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) { 242 243 Value *Incoming = Phi->getIncomingValue(i); 244 if (Incoming != BoolTrue) 245 continue; 246 247 BasicBlock *From = Phi->getIncomingBlock(i); 248 if (From == IDom) { 249 CallInst *OldEnd = dyn_cast<CallInst>(Parent->getFirstInsertionPt()); 250 if (OldEnd && OldEnd->getCalledFunction() == EndCf) { 251 Value *Args[] = { OldEnd->getArgOperand(0), NewPhi }; 252 Ret = CallInst::Create(ElseBreak, Args, "", OldEnd); 253 continue; 254 } 255 } 256 TerminatorInst *Insert = From->getTerminator(); 257 Value *PhiArg = CallInst::Create(Break, Broken, "", Insert); 258 NewPhi->setIncomingValue(i, PhiArg); 259 } 260 eraseIfUnused(Phi); 261 return Ret; 262 263 } else if (Instruction *Inst = dyn_cast<Instruction>(Cond)) { 264 BasicBlock *Parent = Inst->getParent(); 265 Instruction *Insert; 266 if (L->contains(Inst)) { 267 Insert = Parent->getTerminator(); 268 } else { 269 Insert = L->getHeader()->getFirstNonPHIOrDbgOrLifetime(); 270 } 271 Value *Args[] = { Cond, Broken }; 272 return CallInst::Create(IfBreak, Args, "", Insert); 273 274 } else { 275 llvm_unreachable("Unhandled loop condition!"); 276 } 277 return 0; 278 } 279 280 /// \brief Handle a back edge (loop) 281 void SIAnnotateControlFlow::handleLoop(BranchInst *Term) { 282 BasicBlock *BB = Term->getParent(); 283 llvm::Loop *L = LI->getLoopFor(BB); 284 BasicBlock *Target = Term->getSuccessor(1); 285 PHINode *Broken = PHINode::Create(Int64, 0, "", &Target->front()); 286 287 Value *Cond = Term->getCondition(); 288 Term->setCondition(BoolTrue); 289 Value *Arg = handleLoopCondition(Cond, Broken, L); 290 291 for (pred_iterator PI = pred_begin(Target), PE = pred_end(Target); 292 PI != PE; ++PI) { 293 294 Broken->addIncoming(*PI == BB ? Arg : Int64Zero, *PI); 295 } 296 297 Term->setCondition(CallInst::Create(Loop, Arg, "", Term)); 298 push(Term->getSuccessor(0), Arg); 299 }/// \brief Close the last opened control flow 300 void SIAnnotateControlFlow::closeControlFlow(BasicBlock *BB) { 301 llvm::Loop *L = LI->getLoopFor(BB); 302 303 if (L && L->getHeader() == BB) { 304 // We can't insert an EndCF call into a loop header, because it will 305 // get executed on every iteration of the loop, when it should be 306 // executed only once before the loop. 307 SmallVector <BasicBlock*, 8> Latches; 308 L->getLoopLatches(Latches); 309 310 std::vector<BasicBlock*> Preds; 311 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) { 312 if (std::find(Latches.begin(), Latches.end(), *PI) == Latches.end()) 313 Preds.push_back(*PI); 314 } 315 BB = llvm::SplitBlockPredecessors(BB, Preds, "endcf.split", DT, LI, false); 316 } 317 318 CallInst::Create(EndCf, popSaved(), "", &*BB->getFirstInsertionPt()); 319 } 320 321 /// \brief Annotate the control flow with intrinsics so the backend can 322 /// recognize if/then/else and loops. 323 bool SIAnnotateControlFlow::runOnFunction(Function &F) { 324 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 325 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 326 327 for (df_iterator<BasicBlock *> I = df_begin(&F.getEntryBlock()), 328 E = df_end(&F.getEntryBlock()); I != E; ++I) { 329 330 BranchInst *Term = dyn_cast<BranchInst>((*I)->getTerminator()); 331 332 if (!Term || Term->isUnconditional()) { 333 if (isTopOfStack(*I)) 334 closeControlFlow(*I); 335 continue; 336 } 337 338 if (I.nodeVisited(Term->getSuccessor(1))) { 339 if (isTopOfStack(*I)) 340 closeControlFlow(*I); 341 handleLoop(Term); 342 continue; 343 } 344 345 if (isTopOfStack(*I)) { 346 PHINode *Phi = dyn_cast<PHINode>(Term->getCondition()); 347 if (Phi && Phi->getParent() == *I && isElse(Phi)) { 348 insertElse(Term); 349 eraseIfUnused(Phi); 350 continue; 351 } 352 closeControlFlow(*I); 353 } 354 openIf(Term); 355 } 356 357 assert(Stack.empty()); 358 return true; 359 } 360 361 /// \brief Create the annotation pass 362 FunctionPass *llvm::createSIAnnotateControlFlowPass() { 363 return new SIAnnotateControlFlow(); 364 } 365
