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