16b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard//===-- SIAnnotateControlFlow.cpp - ------------------===// 26b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// 36b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// The LLVM Compiler Infrastructure 46b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// 56b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// This file is distributed under the University of Illinois Open Source 66b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// License. See LICENSE.TXT for details. 76b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// 86b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard//===----------------------------------------------------------------------===// 96b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// 106b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \file 116b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// Annotates the control flow with hardware specific intrinsics. 126b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// 136b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard//===----------------------------------------------------------------------===// 146b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 156b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard#include "AMDGPU.h" 1658a2cbef4aac9ee7d530dfb690c78d6fc11a2371Chandler Carruth#include "llvm/ADT/DepthFirstIterator.h" 176f3b49323cd061f4beb18aa77b94612bcd4f71c0Tom Stellard#include "llvm/IR/Constants.h" 1836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Dominators.h" 196f3b49323cd061f4beb18aa77b94612bcd4f71c0Tom Stellard#include "llvm/IR/Instructions.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 2158a2cbef4aac9ee7d530dfb690c78d6fc11a2371Chandler Carruth#include "llvm/Pass.h" 226b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard#include "llvm/Transforms/Utils/BasicBlockUtils.h" 236b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard#include "llvm/Transforms/Utils/SSAUpdater.h" 246b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 256b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardusing namespace llvm; 266b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 27dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "si-annotate-control-flow" 28dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 296b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardnamespace { 306b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 316b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// Complex types used in this pass 326b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardtypedef std::pair<BasicBlock *, Value *> StackEntry; 336b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardtypedef SmallVector<StackEntry, 16> StackVector; 346b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 356b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// Intrinsic names the control flow is annotated with 364172a8abbabea2359d91bb07101166565127d798Craig Topperstatic const char *const IfIntrinsic = "llvm.SI.if"; 374172a8abbabea2359d91bb07101166565127d798Craig Topperstatic const char *const ElseIntrinsic = "llvm.SI.else"; 384172a8abbabea2359d91bb07101166565127d798Craig Topperstatic const char *const BreakIntrinsic = "llvm.SI.break"; 394172a8abbabea2359d91bb07101166565127d798Craig Topperstatic const char *const IfBreakIntrinsic = "llvm.SI.if.break"; 404172a8abbabea2359d91bb07101166565127d798Craig Topperstatic const char *const ElseBreakIntrinsic = "llvm.SI.else.break"; 414172a8abbabea2359d91bb07101166565127d798Craig Topperstatic const char *const LoopIntrinsic = "llvm.SI.loop"; 424172a8abbabea2359d91bb07101166565127d798Craig Topperstatic const char *const EndCfIntrinsic = "llvm.SI.end.cf"; 436b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 446b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardclass SIAnnotateControlFlow : public FunctionPass { 456b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 466b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard static char ID; 476b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 486b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Type *Boolean; 496b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Type *Void; 506b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Type *Int64; 516b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Type *ReturnStruct; 526b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 536b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard ConstantInt *BoolTrue; 546b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard ConstantInt *BoolFalse; 556b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard UndefValue *BoolUndef; 566b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Constant *Int64Zero; 576b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 586b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Constant *If; 596b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Constant *Else; 606b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Constant *Break; 616b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Constant *IfBreak; 626b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Constant *ElseBreak; 636b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Constant *Loop; 646b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Constant *EndCf; 656b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 666b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard DominatorTree *DT; 676b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard StackVector Stack; 686b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 696b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard bool isTopOfStack(BasicBlock *BB); 706b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 716b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Value *popSaved(); 726b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 736b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard void push(BasicBlock *BB, Value *Saved); 746b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 756b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard bool isElse(PHINode *Phi); 766b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 776b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard void eraseIfUnused(PHINode *Phi); 786b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 796b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard void openIf(BranchInst *Term); 806b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 816b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard void insertElse(BranchInst *Term); 826b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 83cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Value *handleLoopCondition(Value *Cond, PHINode *Broken); 846b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 856b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard void handleLoop(BranchInst *Term); 866b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 876b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard void closeControlFlow(BasicBlock *BB); 886b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 896b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardpublic: 906b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard SIAnnotateControlFlow(): 916b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard FunctionPass(ID) { } 926b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 93dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool doInitialization(Module &M) override; 946b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 95dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool runOnFunction(Function &F) override; 966b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 97dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const char *getPassName() const override { 986b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard return "SI annotate control flow"; 996b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 1006b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 101dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 10236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addRequired<DominatorTreeWrapperPass>(); 10336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addPreserved<DominatorTreeWrapperPass>(); 1046b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard FunctionPass::getAnalysisUsage(AU); 1056b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 1066b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1076b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard}; 1086b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1096b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} // end anonymous namespace 1106b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1116b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardchar SIAnnotateControlFlow::ID = 0; 1126b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1136b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \brief Initialize all the types and constants used in the pass 1146b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardbool SIAnnotateControlFlow::doInitialization(Module &M) { 1156b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard LLVMContext &Context = M.getContext(); 1166b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1176b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Void = Type::getVoidTy(Context); 1186b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Boolean = Type::getInt1Ty(Context); 1196b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Int64 = Type::getInt64Ty(Context); 120dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ReturnStruct = StructType::get(Boolean, Int64, (Type *)nullptr); 1216b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1226b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard BoolTrue = ConstantInt::getTrue(Context); 1236b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard BoolFalse = ConstantInt::getFalse(Context); 1246b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard BoolUndef = UndefValue::get(Boolean); 1256b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Int64Zero = ConstantInt::get(Int64, 0); 1266b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1276b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard If = M.getOrInsertFunction( 128dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines IfIntrinsic, ReturnStruct, Boolean, (Type *)nullptr); 1296b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1306b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Else = M.getOrInsertFunction( 131dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ElseIntrinsic, ReturnStruct, Int64, (Type *)nullptr); 1326b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1336b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Break = M.getOrInsertFunction( 134dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BreakIntrinsic, Int64, Int64, (Type *)nullptr); 1356b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1366b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard IfBreak = M.getOrInsertFunction( 137dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines IfBreakIntrinsic, Int64, Boolean, Int64, (Type *)nullptr); 1386b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1396b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard ElseBreak = M.getOrInsertFunction( 140dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ElseBreakIntrinsic, Int64, Int64, Int64, (Type *)nullptr); 1416b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1426b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Loop = M.getOrInsertFunction( 143dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LoopIntrinsic, Boolean, Int64, (Type *)nullptr); 1446b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1456b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard EndCf = M.getOrInsertFunction( 146dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EndCfIntrinsic, Void, Int64, (Type *)nullptr); 1476b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1486b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard return false; 1496b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 1506b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1516b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \brief Is BB the last block saved on the stack ? 1526b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardbool SIAnnotateControlFlow::isTopOfStack(BasicBlock *BB) { 153c556fcc153a727945dbbe222a5b7c1dfce141a33Michel Danzer return !Stack.empty() && Stack.back().first == BB; 1546b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 1556b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1566b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \brief Pop the last saved value from the control flow stack 1576b7d99d47321ebb478b22afd2e317fe89d2149dbTom StellardValue *SIAnnotateControlFlow::popSaved() { 1586b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard return Stack.pop_back_val().second; 1596b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 1606b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1616b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \brief Push a BB and saved value to the control flow stack 1626b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardvoid SIAnnotateControlFlow::push(BasicBlock *BB, Value *Saved) { 1636b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Stack.push_back(std::make_pair(BB, Saved)); 1646b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 1656b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1666b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \brief Can the condition represented by this PHI node treated like 1676b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// an "Else" block? 1686b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardbool SIAnnotateControlFlow::isElse(PHINode *Phi) { 1696b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard BasicBlock *IDom = DT->getNode(Phi->getParent())->getIDom()->getBlock(); 1706b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) { 1716b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (Phi->getIncomingBlock(i) == IDom) { 1726b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1736b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (Phi->getIncomingValue(i) != BoolTrue) 1746b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard return false; 1756b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1766b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } else { 1776b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (Phi->getIncomingValue(i) != BoolFalse) 1786b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard return false; 179cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 1806b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 1816b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 1826b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard return true; 1836b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 1846b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1856b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// \brief Erase "Phi" if it is not used any more 1866b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardvoid SIAnnotateControlFlow::eraseIfUnused(PHINode *Phi) { 1876b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (!Phi->hasNUsesOrMore(1)) 1886b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Phi->eraseFromParent(); 1896b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 1906b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1916b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \brief Open a new "If" block 1926b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardvoid SIAnnotateControlFlow::openIf(BranchInst *Term) { 1936b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Value *Ret = CallInst::Create(If, Term->getCondition(), "", Term); 1946b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term)); 1956b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term)); 1966b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 1976b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1986b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \brief Close the last "If" block and open a new "Else" block 1996b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardvoid SIAnnotateControlFlow::insertElse(BranchInst *Term) { 2006b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Value *Ret = CallInst::Create(Else, popSaved(), "", Term); 2016b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Term->setCondition(ExtractValueInst::Create(Ret, 0, "", Term)); 2026b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard push(Term->getSuccessor(1), ExtractValueInst::Create(Ret, 1, "", Term)); 2036b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 2046b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2056b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \brief Recursively handle the condition leading to a loop 206cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesValue *SIAnnotateControlFlow::handleLoopCondition(Value *Cond, PHINode *Broken) { 2076b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (PHINode *Phi = dyn_cast<PHINode>(Cond)) { 208cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines BasicBlock *Parent = Phi->getParent(); 209cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines PHINode *NewPhi = PHINode::Create(Int64, 0, "", &Parent->front()); 210cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Value *Ret = NewPhi; 2116b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 21236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Handle all non-constant incoming values first 2136b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) { 2146b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Value *Incoming = Phi->getIncomingValue(i); 215cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines BasicBlock *From = Phi->getIncomingBlock(i); 216cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (isa<ConstantInt>(Incoming)) { 217cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines NewPhi->addIncoming(Broken, From); 2186b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard continue; 219cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 2206b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2216b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Phi->setIncomingValue(i, BoolFalse); 222cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Value *PhiArg = handleLoopCondition(Incoming, Broken); 223cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines NewPhi->addIncoming(PhiArg, From); 2246b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 2256b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2266b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard BasicBlock *IDom = DT->getNode(Parent)->getIDom()->getBlock(); 2276b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2286b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) { 2296b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2306b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Value *Incoming = Phi->getIncomingValue(i); 2316b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (Incoming != BoolTrue) 2326b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard continue; 2336b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2346b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard BasicBlock *From = Phi->getIncomingBlock(i); 2356b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (From == IDom) { 2366b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard CallInst *OldEnd = dyn_cast<CallInst>(Parent->getFirstInsertionPt()); 2376b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (OldEnd && OldEnd->getCalledFunction() == EndCf) { 238cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Value *Args[] = { OldEnd->getArgOperand(0), NewPhi }; 239cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Ret = CallInst::Create(ElseBreak, Args, "", OldEnd); 2406b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard continue; 2416b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 2426b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 2436b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard TerminatorInst *Insert = From->getTerminator(); 244cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Value *PhiArg = CallInst::Create(Break, Broken, "", Insert); 245cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines NewPhi->setIncomingValue(i, PhiArg); 2466b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 2476b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard eraseIfUnused(Phi); 248cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return Ret; 2496b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2506b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } else if (Instruction *Inst = dyn_cast<Instruction>(Cond)) { 2516b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard BasicBlock *Parent = Inst->getParent(); 2526b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard TerminatorInst *Insert = Parent->getTerminator(); 253cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Value *Args[] = { Cond, Broken }; 254cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return CallInst::Create(IfBreak, Args, "", Insert); 2556b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2566b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } else { 25736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines llvm_unreachable("Unhandled loop condition!"); 2586b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 259cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return 0; 2606b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 2616b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2626b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \brief Handle a back edge (loop) 2636b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardvoid SIAnnotateControlFlow::handleLoop(BranchInst *Term) { 2646b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard BasicBlock *Target = Term->getSuccessor(1); 2656b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard PHINode *Broken = PHINode::Create(Int64, 0, "", &Target->front()); 2666b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2676b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Value *Cond = Term->getCondition(); 2686b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Term->setCondition(BoolTrue); 269cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Value *Arg = handleLoopCondition(Cond, Broken); 2706b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2716b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard BasicBlock *BB = Term->getParent(); 2726b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard for (pred_iterator PI = pred_begin(Target), PE = pred_end(Target); 2736b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard PI != PE; ++PI) { 2746b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2756b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Broken->addIncoming(*PI == BB ? Arg : Int64Zero, *PI); 2766b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 2776b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2786b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Term->setCondition(CallInst::Create(Loop, Arg, "", Term)); 2796b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard push(Term->getSuccessor(0), Arg); 2806b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 2816b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2826b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \brief Close the last opened control flow 2836b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardvoid SIAnnotateControlFlow::closeControlFlow(BasicBlock *BB) { 2846b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard CallInst::Create(EndCf, popSaved(), "", BB->getFirstInsertionPt()); 2856b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 2866b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2876b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \brief Annotate the control flow with intrinsics so the backend can 2886b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// recognize if/then/else and loops. 2896b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardbool SIAnnotateControlFlow::runOnFunction(Function &F) { 29036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 2916b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2926b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard for (df_iterator<BasicBlock *> I = df_begin(&F.getEntryBlock()), 2936b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard E = df_end(&F.getEntryBlock()); I != E; ++I) { 2946b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2956b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard BranchInst *Term = dyn_cast<BranchInst>((*I)->getTerminator()); 2966b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2976b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (!Term || Term->isUnconditional()) { 2986b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (isTopOfStack(*I)) 2996b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard closeControlFlow(*I); 3006b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard continue; 3016b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 3026b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 3036b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (I.nodeVisited(Term->getSuccessor(1))) { 3046b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (isTopOfStack(*I)) 3056b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard closeControlFlow(*I); 3066b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard handleLoop(Term); 3076b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard continue; 3086b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 3096b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 3106b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (isTopOfStack(*I)) { 3116b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard PHINode *Phi = dyn_cast<PHINode>(Term->getCondition()); 3126b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (Phi && Phi->getParent() == *I && isElse(Phi)) { 3136b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard insertElse(Term); 3146b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard eraseIfUnused(Phi); 3156b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard continue; 3166b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 3176b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard closeControlFlow(*I); 3186b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 3196b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard openIf(Term); 3206b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 3216b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 3226b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard assert(Stack.empty()); 3236b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard return true; 3246b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 3256b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 3266b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \brief Create the annotation pass 3276b7d99d47321ebb478b22afd2e317fe89d2149dbTom StellardFunctionPass *llvm::createSIAnnotateControlFlowPass() { 3286b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard return new SIAnnotateControlFlow(); 3296b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 330