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 14d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Scalar.h" 15d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 160b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/BasicBlock.h" 170b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 180b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 190b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Intrinsics.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/LLVMContext.h" 220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/MDBuilder.h" 230b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Metadata.h" 249da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak#include "llvm/Pass.h" 259da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak#include "llvm/Support/CommandLine.h" 269da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak#include "llvm/Support/Debug.h" 279da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak#include <vector> 289da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 299da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszakusing namespace llvm; 309da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 31dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "lower-expect-intrinsic" 32dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 33f80a63fa23862e578de919f4b44d4fcdee68fd0dRobert WilhelmSTATISTIC(IfHandled, "Number of 'expect' intrinsic instructions handled"); 349da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 359da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszakstatic cl::opt<uint32_t> 369da9934e27dfb48de77b80a3e20ed2d869b52024Jakub StaszakLikelyBranchWeight("likely-branch-weight", cl::Hidden, cl::init(64), 379da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak cl::desc("Weight of the branch likely to be taken (default = 64)")); 389da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszakstatic cl::opt<uint32_t> 399da9934e27dfb48de77b80a3e20ed2d869b52024Jakub StaszakUnlikelyBranchWeight("unlikely-branch-weight", cl::Hidden, cl::init(4), 409da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak cl::desc("Weight of the branch unlikely to be taken (default = 4)")); 419da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 429da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszaknamespace { 439da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 449da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak class LowerExpectIntrinsic : public FunctionPass { 459da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 469da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak bool HandleSwitchExpect(SwitchInst *SI); 479da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 489da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak bool HandleIfExpect(BranchInst *BI); 499da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 509da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak public: 519da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak static char ID; 529da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak LowerExpectIntrinsic() : FunctionPass(ID) { 539da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak initializeLowerExpectIntrinsicPass(*PassRegistry::getPassRegistry()); 549da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak } 559da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 5636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 579da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak }; 589da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak} 599da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 609da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 619da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszakbool LowerExpectIntrinsic::HandleSwitchExpect(SwitchInst *SI) { 629da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak CallInst *CI = dyn_cast<CallInst>(SI->getCondition()); 639da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (!CI) 649da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return false; 659da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 669da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak Function *Fn = CI->getCalledFunction(); 679da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect) 689da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return false; 699da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 709da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak Value *ArgValue = CI->getArgOperand(0); 719da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 729da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (!ExpectedValue) 739da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return false; 749da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 75c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy SwitchInst::CaseIt Case = SI->findCaseValue(ExpectedValue); 76937338cf64350a7d05d0c956dc8e8564e959cb7bBenjamin Kramer unsigned n = SI->getNumCases(); // +1 for default case. 77937338cf64350a7d05d0c956dc8e8564e959cb7bBenjamin Kramer std::vector<uint32_t> Weights(n + 1); 789da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 79937338cf64350a7d05d0c956dc8e8564e959cb7bBenjamin Kramer Weights[0] = Case == SI->case_default() ? LikelyBranchWeight 80937338cf64350a7d05d0c956dc8e8564e959cb7bBenjamin Kramer : UnlikelyBranchWeight; 81937338cf64350a7d05d0c956dc8e8564e959cb7bBenjamin Kramer for (unsigned i = 0; i != n; ++i) 82937338cf64350a7d05d0c956dc8e8564e959cb7bBenjamin Kramer Weights[i + 1] = i == Case.getCaseIndex() ? LikelyBranchWeight 83937338cf64350a7d05d0c956dc8e8564e959cb7bBenjamin Kramer : UnlikelyBranchWeight; 849da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 85937338cf64350a7d05d0c956dc8e8564e959cb7bBenjamin Kramer SI->setMetadata(LLVMContext::MD_prof, 86937338cf64350a7d05d0c956dc8e8564e959cb7bBenjamin Kramer MDBuilder(CI->getContext()).createBranchWeights(Weights)); 879da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 889da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak SI->setCondition(ArgValue); 899da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return true; 909da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak} 919da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 929da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 939da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszakbool LowerExpectIntrinsic::HandleIfExpect(BranchInst *BI) { 949da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (BI->isUnconditional()) 959da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return false; 969da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 979da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak // Handle non-optimized IR code like: 9836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // %expval = call i64 @llvm.expect.i64(i64 %conv1, i64 1) 999da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak // %tobool = icmp ne i64 %expval, 0 1009da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak // br i1 %tobool, label %if.then, label %if.end 10136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 10236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Or the following simpler case: 10336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // %expval = call i1 @llvm.expect.i1(i1 %cmp, i1 1) 10436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // br i1 %expval, label %if.then, label %if.end 10536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 10636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CallInst *CI; 1079da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1089da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak ICmpInst *CmpI = dyn_cast<ICmpInst>(BI->getCondition()); 10936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!CmpI) { 11036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CI = dyn_cast<CallInst>(BI->getCondition()); 11136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else { 11236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (CmpI->getPredicate() != CmpInst::ICMP_NE) 11336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 11436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CI = dyn_cast<CallInst>(CmpI->getOperand(0)); 11536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 1169da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1179da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (!CI) 1189da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return false; 1199da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1209da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak Function *Fn = CI->getCalledFunction(); 1219da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect) 1229da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return false; 1239da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1249da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak Value *ArgValue = CI->getArgOperand(0); 1259da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 1269da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (!ExpectedValue) 1279da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return false; 1289da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 129937338cf64350a7d05d0c956dc8e8564e959cb7bBenjamin Kramer MDBuilder MDB(CI->getContext()); 130937338cf64350a7d05d0c956dc8e8564e959cb7bBenjamin Kramer MDNode *Node; 1319da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1329da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak // If expect value is equal to 1 it means that we are more likely to take 1339da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak // branch 0, in other case more likely is branch 1. 134937338cf64350a7d05d0c956dc8e8564e959cb7bBenjamin Kramer if (ExpectedValue->isOne()) 135937338cf64350a7d05d0c956dc8e8564e959cb7bBenjamin Kramer Node = MDB.createBranchWeights(LikelyBranchWeight, UnlikelyBranchWeight); 136937338cf64350a7d05d0c956dc8e8564e959cb7bBenjamin Kramer else 137937338cf64350a7d05d0c956dc8e8564e959cb7bBenjamin Kramer Node = MDB.createBranchWeights(UnlikelyBranchWeight, LikelyBranchWeight); 1389da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 139937338cf64350a7d05d0c956dc8e8564e959cb7bBenjamin Kramer BI->setMetadata(LLVMContext::MD_prof, Node); 1409da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 14136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (CmpI) 14236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CmpI->setOperand(0, ArgValue); 14336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines else 14436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BI->setCondition(ArgValue); 1459da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return true; 1469da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak} 1479da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1489da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1499da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszakbool LowerExpectIntrinsic::runOnFunction(Function &F) { 1509da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak for (Function::iterator I = F.begin(), E = F.end(); I != E;) { 1519da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak BasicBlock *BB = I++; 1529da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1539da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak // Create "block_weights" metadata. 1549da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 1559da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (HandleIfExpect(BI)) 1569da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak IfHandled++; 1579da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { 1589da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (HandleSwitchExpect(SI)) 1599da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak IfHandled++; 1609da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak } 1619da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1629da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak // remove llvm.expect intrinsics. 1639da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 1649da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak BI != BE; ) { 1659da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak CallInst *CI = dyn_cast<CallInst>(BI++); 1669da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak if (!CI) 1679da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak continue; 1689da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1699da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak Function *Fn = CI->getCalledFunction(); 170447c40c4028f1563826ea75f47fd3ec48c7a74adJakub Staszak if (Fn && Fn->getIntrinsicID() == Intrinsic::expect) { 171447c40c4028f1563826ea75f47fd3ec48c7a74adJakub Staszak Value *Exp = CI->getArgOperand(0); 172447c40c4028f1563826ea75f47fd3ec48c7a74adJakub Staszak CI->replaceAllUsesWith(Exp); 1739da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak CI->eraseFromParent(); 174447c40c4028f1563826ea75f47fd3ec48c7a74adJakub Staszak } 1759da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak } 1769da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak } 1779da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1789da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return false; 1799da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak} 1809da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1819da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1829da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszakchar LowerExpectIntrinsic::ID = 0; 1839da9934e27dfb48de77b80a3e20ed2d869b52024Jakub StaszakINITIALIZE_PASS(LowerExpectIntrinsic, "lower-expect", "Lower 'expect' " 1849da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak "Intrinsics", false, false) 1859da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak 1869da9934e27dfb48de77b80a3e20ed2d869b52024Jakub StaszakFunctionPass *llvm::createLowerExpectIntrinsicPass() { 1879da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak return new LowerExpectIntrinsic(); 1889da9934e27dfb48de77b80a3e20ed2d869b52024Jakub Staszak} 189