15820d6280375716df3f18f39966eb2c595befabeChandler Carruth//===- LowerExpectIntrinsic.cpp - Lower expect intrinsic ------------------===// 25820d6280375716df3f18f39966eb2c595befabeChandler Carruth// 35820d6280375716df3f18f39966eb2c595befabeChandler Carruth// The LLVM Compiler Infrastructure 45820d6280375716df3f18f39966eb2c595befabeChandler Carruth// 55820d6280375716df3f18f39966eb2c595befabeChandler Carruth// This file is distributed under the University of Illinois Open Source 65820d6280375716df3f18f39966eb2c595befabeChandler Carruth// License. See LICENSE.TXT for details. 75820d6280375716df3f18f39966eb2c595befabeChandler Carruth// 85820d6280375716df3f18f39966eb2c595befabeChandler Carruth//===----------------------------------------------------------------------===// 95820d6280375716df3f18f39966eb2c595befabeChandler Carruth// 105820d6280375716df3f18f39966eb2c595befabeChandler Carruth// This pass lowers the 'expect' intrinsic to LLVM metadata. 115820d6280375716df3f18f39966eb2c595befabeChandler Carruth// 125820d6280375716df3f18f39966eb2c595befabeChandler Carruth//===----------------------------------------------------------------------===// 135820d6280375716df3f18f39966eb2c595befabeChandler Carruth 149da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak#define DEBUG_TYPE "lower-expect-intrinsic" 159da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak#include "llvm/Constants.h" 169da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak#include "llvm/Function.h" 179da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak#include "llvm/BasicBlock.h" 189da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak#include "llvm/LLVMContext.h" 199da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak#include "llvm/Instructions.h" 209da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak#include "llvm/Intrinsics.h" 219da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak#include "llvm/Metadata.h" 229da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak#include "llvm/Pass.h" 239da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak#include "llvm/Transforms/Scalar.h" 249da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak#include "llvm/Support/CommandLine.h" 259da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak#include "llvm/Support/Debug.h" 269da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak#include "llvm/ADT/Statistic.h" 279da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak#include <vector> 289da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 299da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszakusing namespace llvm; 309da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 319da9934e27dfb48de77b80a3e20ed2d869b52024Jakub StaszakSTATISTIC(IfHandled, "Number of 'expect' intrinsic intructions handled"); 329da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 339da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszakstatic cl::opt<uint32_t> 349da9934e27dfb48de77b80a3e20ed2d869b52024Jakub StaszakLikelyBranchWeight("likely-branch-weight", cl::Hidden, cl::init(64), 359da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak cl::desc("Weight of the branch likely to be taken (default = 64)")); 369da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszakstatic cl::opt<uint32_t> 379da9934e27dfb48de77b80a3e20ed2d869b52024Jakub StaszakUnlikelyBranchWeight("unlikely-branch-weight", cl::Hidden, cl::init(4), 389da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak cl::desc("Weight of the branch unlikely to be taken (default = 4)")); 399da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 409da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszaknamespace { 419da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 429da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak class LowerExpectIntrinsic : public FunctionPass { 439da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 449da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak bool HandleSwitchExpect(SwitchInst *SI); 459da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 469da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak bool HandleIfExpect(BranchInst *BI); 479da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 489da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak public: 499da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak static char ID; 509da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak LowerExpectIntrinsic() : FunctionPass(ID) { 519da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak initializeLowerExpectIntrinsicPass(*PassRegistry::getPassRegistry()); 529da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak } 539da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 549da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak bool runOnFunction(Function &F); 559da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak }; 569da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak} 579da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 589da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 599da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszakbool LowerExpectIntrinsic::HandleSwitchExpect(SwitchInst *SI) { 609da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak CallInst *CI = dyn_cast<CallInst>(SI->getCondition()); 619da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (!CI) 629da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return false; 639da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 649da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak Function *Fn = CI->getCalledFunction(); 659da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect) 669da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return false; 679da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 689da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak Value *ArgValue = CI->getArgOperand(0); 699da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 709da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (!ExpectedValue) 719da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return false; 729da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 739da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak LLVMContext &Context = CI->getContext(); 74db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Int32Ty = Type::getInt32Ty(Context); 759da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 769da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak unsigned caseNo = SI->findCaseValue(ExpectedValue); 779da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak std::vector<Value *> Vec; 789da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak unsigned n = SI->getNumCases(); 799da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak Vec.resize(n + 1); // +1 for MDString 809da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 819da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak Vec[0] = MDString::get(Context, "branch_weights"); 829da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak for (unsigned i = 0; i < n; ++i) { 839da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak Vec[i + 1] = ConstantInt::get(Int32Ty, i == caseNo ? LikelyBranchWeight : UnlikelyBranchWeight); 849da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak } 859da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 869da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak MDNode *WeightsNode = llvm::MDNode::get(Context, Vec); 879da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak SI->setMetadata(LLVMContext::MD_prof, WeightsNode); 889da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 899da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak SI->setCondition(ArgValue); 909da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return true; 919da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak} 929da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 939da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 949da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszakbool LowerExpectIntrinsic::HandleIfExpect(BranchInst *BI) { 959da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (BI->isUnconditional()) 969da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return false; 979da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 989da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak // Handle non-optimized IR code like: 999da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak // %expval = call i64 @llvm.expect.i64.i64(i64 %conv1, i64 1) 1009da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak // %tobool = icmp ne i64 %expval, 0 1019da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak // br i1 %tobool, label %if.then, label %if.end 1029da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1039da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak ICmpInst *CmpI = dyn_cast<ICmpInst>(BI->getCondition()); 1049da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (!CmpI || CmpI->getPredicate() != CmpInst::ICMP_NE) 1059da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return false; 1069da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1079da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak CallInst *CI = dyn_cast<CallInst>(CmpI->getOperand(0)); 1089da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (!CI) 1099da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return false; 1109da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1119da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak Function *Fn = CI->getCalledFunction(); 1129da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect) 1139da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return false; 1149da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1159da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak Value *ArgValue = CI->getArgOperand(0); 1169da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 1179da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (!ExpectedValue) 1189da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return false; 1199da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1209da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak LLVMContext &Context = CI->getContext(); 121db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Int32Ty = Type::getInt32Ty(Context); 1229da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak bool Likely = ExpectedValue->isOne(); 1239da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1249da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak // If expect value is equal to 1 it means that we are more likely to take 1259da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak // branch 0, in other case more likely is branch 1. 1269da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak Value *Ops[] = { 1279da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak MDString::get(Context, "branch_weights"), 1289da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak ConstantInt::get(Int32Ty, Likely ? LikelyBranchWeight : UnlikelyBranchWeight), 1299da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak ConstantInt::get(Int32Ty, Likely ? UnlikelyBranchWeight : LikelyBranchWeight) 1309da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak }; 1319da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 132037a60f9090a4d034093520de268a0ad4b6b8e30Frits van Bommel MDNode *WeightsNode = MDNode::get(Context, Ops); 1339da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak BI->setMetadata(LLVMContext::MD_prof, WeightsNode); 1349da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1359da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak CmpI->setOperand(0, ArgValue); 1369da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return true; 1379da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak} 1389da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1399da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1409da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszakbool LowerExpectIntrinsic::runOnFunction(Function &F) { 1419da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak for (Function::iterator I = F.begin(), E = F.end(); I != E;) { 1429da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak BasicBlock *BB = I++; 1439da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1449da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak // Create "block_weights" metadata. 1459da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 1469da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (HandleIfExpect(BI)) 1479da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak IfHandled++; 1489da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { 1499da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (HandleSwitchExpect(SI)) 1509da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak IfHandled++; 1519da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak } 1529da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1539da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak // remove llvm.expect intrinsics. 1549da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 1559da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak BI != BE; ) { 1569da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak CallInst *CI = dyn_cast<CallInst>(BI++); 1579da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (!CI) 1589da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak continue; 1599da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1609da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak Function *Fn = CI->getCalledFunction(); 161447c40c4028f1563826ea75f47fd3ec48c7a74adJakub Staszak if (Fn && Fn->getIntrinsicID() == Intrinsic::expect) { 162447c40c4028f1563826ea75f47fd3ec48c7a74adJakub Staszak Value *Exp = CI->getArgOperand(0); 163447c40c4028f1563826ea75f47fd3ec48c7a74adJakub Staszak CI->replaceAllUsesWith(Exp); 1649da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak CI->eraseFromParent(); 165447c40c4028f1563826ea75f47fd3ec48c7a74adJakub Staszak } 1669da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak } 1679da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak } 1689da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1699da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return false; 1709da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak} 1719da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1729da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1739da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszakchar LowerExpectIntrinsic::ID = 0; 1749da9934e27dfb48de77b80a3e20ed2d869b52024Jakub StaszakINITIALIZE_PASS(LowerExpectIntrinsic, "lower-expect", "Lower 'expect' " 1759da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak "Intrinsics", false, false) 1769da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1779da9934e27dfb48de77b80a3e20ed2d869b52024Jakub StaszakFunctionPass *llvm::createLowerExpectIntrinsicPass() { 1789da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return new LowerExpectIntrinsic(); 1799da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak} 180