1283625Sdim//===- LowerExpectIntrinsic.cpp - Lower expect intrinsic ------------------===// 2283625Sdim// 3283625Sdim// The LLVM Compiler Infrastructure 4283625Sdim// 5283625Sdim// This file is distributed under the University of Illinois Open Source 6283625Sdim// License. See LICENSE.TXT for details. 7283625Sdim// 8283625Sdim//===----------------------------------------------------------------------===// 9283625Sdim// 10283625Sdim// This pass lowers the 'expect' intrinsic to LLVM metadata. 11283625Sdim// 12283625Sdim//===----------------------------------------------------------------------===// 13283625Sdim 14283625Sdim#include "llvm/Transforms/Scalar/LowerExpectIntrinsic.h" 15283625Sdim#include "llvm/ADT/SmallVector.h" 16283625Sdim#include "llvm/ADT/Statistic.h" 17283625Sdim#include "llvm/IR/BasicBlock.h" 18283625Sdim#include "llvm/IR/Constants.h" 19283625Sdim#include "llvm/IR/Function.h" 20283625Sdim#include "llvm/IR/Instructions.h" 21283625Sdim#include "llvm/IR/Intrinsics.h" 22283625Sdim#include "llvm/IR/LLVMContext.h" 23283625Sdim#include "llvm/IR/MDBuilder.h" 24283625Sdim#include "llvm/IR/Metadata.h" 25283625Sdim#include "llvm/Pass.h" 26283625Sdim#include "llvm/Support/CommandLine.h" 27283625Sdim#include "llvm/Support/Debug.h" 28283625Sdim#include "llvm/Transforms/Scalar.h" 29283625Sdim 30283625Sdimusing namespace llvm; 31283625Sdim 32283625Sdim#define DEBUG_TYPE "lower-expect-intrinsic" 33283625Sdim 34283625SdimSTATISTIC(ExpectIntrinsicsHandled, 35283625Sdim "Number of 'expect' intrinsic instructions handled"); 36283625Sdim 37283625Sdimstatic cl::opt<uint32_t> 38283625SdimLikelyBranchWeight("likely-branch-weight", cl::Hidden, cl::init(64), 39283625Sdim cl::desc("Weight of the branch likely to be taken (default = 64)")); 40283625Sdimstatic cl::opt<uint32_t> 41283625SdimUnlikelyBranchWeight("unlikely-branch-weight", cl::Hidden, cl::init(4), 42283625Sdim cl::desc("Weight of the branch unlikely to be taken (default = 4)")); 43283625Sdim 44283625Sdimstatic bool handleSwitchExpect(SwitchInst &SI) { 45283625Sdim CallInst *CI = dyn_cast<CallInst>(SI.getCondition()); 46283625Sdim if (!CI) 47283625Sdim return false; 48283625Sdim 49283625Sdim Function *Fn = CI->getCalledFunction(); 50283625Sdim if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect) 51283625Sdim return false; 52283625Sdim 53283625Sdim Value *ArgValue = CI->getArgOperand(0); 54283625Sdim ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 55283625Sdim if (!ExpectedValue) 56283625Sdim return false; 57283625Sdim 58283625Sdim SwitchInst::CaseIt Case = SI.findCaseValue(ExpectedValue); 59283625Sdim unsigned n = SI.getNumCases(); // +1 for default case. 60283625Sdim SmallVector<uint32_t, 16> Weights(n + 1, UnlikelyBranchWeight); 61283625Sdim 62283625Sdim if (Case == SI.case_default()) 63283625Sdim Weights[0] = LikelyBranchWeight; 64283625Sdim else 65283625Sdim Weights[Case.getCaseIndex() + 1] = LikelyBranchWeight; 66283625Sdim 67283625Sdim SI.setMetadata(LLVMContext::MD_prof, 68283625Sdim MDBuilder(CI->getContext()).createBranchWeights(Weights)); 69283625Sdim 70283625Sdim SI.setCondition(ArgValue); 71283625Sdim return true; 72283625Sdim} 73283625Sdim 74283625Sdimstatic bool handleBranchExpect(BranchInst &BI) { 75283625Sdim if (BI.isUnconditional()) 76283625Sdim return false; 77283625Sdim 78283625Sdim // Handle non-optimized IR code like: 79283625Sdim // %expval = call i64 @llvm.expect.i64(i64 %conv1, i64 1) 80283625Sdim // %tobool = icmp ne i64 %expval, 0 81283625Sdim // br i1 %tobool, label %if.then, label %if.end 82283625Sdim // 83283625Sdim // Or the following simpler case: 84283625Sdim // %expval = call i1 @llvm.expect.i1(i1 %cmp, i1 1) 85283625Sdim // br i1 %expval, label %if.then, label %if.end 86283625Sdim 87283625Sdim CallInst *CI; 88283625Sdim 89283625Sdim ICmpInst *CmpI = dyn_cast<ICmpInst>(BI.getCondition()); 90283625Sdim if (!CmpI) { 91283625Sdim CI = dyn_cast<CallInst>(BI.getCondition()); 92283625Sdim } else { 93283625Sdim if (CmpI->getPredicate() != CmpInst::ICMP_NE) 94283625Sdim return false; 95283625Sdim CI = dyn_cast<CallInst>(CmpI->getOperand(0)); 96283625Sdim } 97283625Sdim 98283625Sdim if (!CI) 99283625Sdim return false; 100283625Sdim 101283625Sdim Function *Fn = CI->getCalledFunction(); 102283625Sdim if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect) 103283625Sdim return false; 104283625Sdim 105283625Sdim Value *ArgValue = CI->getArgOperand(0); 106283625Sdim ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 107283625Sdim if (!ExpectedValue) 108283625Sdim return false; 109283625Sdim 110283625Sdim MDBuilder MDB(CI->getContext()); 111283625Sdim MDNode *Node; 112283625Sdim 113283625Sdim // If expect value is equal to 1 it means that we are more likely to take 114283625Sdim // branch 0, in other case more likely is branch 1. 115283625Sdim if (ExpectedValue->isOne()) 116283625Sdim Node = MDB.createBranchWeights(LikelyBranchWeight, UnlikelyBranchWeight); 117283625Sdim else 118283625Sdim Node = MDB.createBranchWeights(UnlikelyBranchWeight, LikelyBranchWeight); 119283625Sdim 120283625Sdim BI.setMetadata(LLVMContext::MD_prof, Node); 121283625Sdim 122283625Sdim if (CmpI) 123283625Sdim CmpI->setOperand(0, ArgValue); 124283625Sdim else 125283625Sdim BI.setCondition(ArgValue); 126283625Sdim return true; 127283625Sdim} 128283625Sdim 129283625Sdimstatic bool lowerExpectIntrinsic(Function &F) { 130283625Sdim bool Changed = false; 131283625Sdim 132283625Sdim for (BasicBlock &BB : F) { 133283625Sdim // Create "block_weights" metadata. 134283625Sdim if (BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator())) { 135283625Sdim if (handleBranchExpect(*BI)) 136283625Sdim ExpectIntrinsicsHandled++; 137283625Sdim } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB.getTerminator())) { 138283625Sdim if (handleSwitchExpect(*SI)) 139283625Sdim ExpectIntrinsicsHandled++; 140283625Sdim } 141283625Sdim 142296417Sdim // Remove llvm.expect intrinsics. 143283625Sdim for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) { 144283625Sdim CallInst *CI = dyn_cast<CallInst>(BI++); 145283625Sdim if (!CI) 146283625Sdim continue; 147283625Sdim 148283625Sdim Function *Fn = CI->getCalledFunction(); 149283625Sdim if (Fn && Fn->getIntrinsicID() == Intrinsic::expect) { 150283625Sdim Value *Exp = CI->getArgOperand(0); 151283625Sdim CI->replaceAllUsesWith(Exp); 152283625Sdim CI->eraseFromParent(); 153283625Sdim Changed = true; 154283625Sdim } 155283625Sdim } 156283625Sdim } 157283625Sdim 158283625Sdim return Changed; 159283625Sdim} 160283625Sdim 161283625SdimPreservedAnalyses LowerExpectIntrinsicPass::run(Function &F) { 162283625Sdim if (lowerExpectIntrinsic(F)) 163283625Sdim return PreservedAnalyses::none(); 164283625Sdim 165283625Sdim return PreservedAnalyses::all(); 166283625Sdim} 167283625Sdim 168283625Sdimnamespace { 169283625Sdim/// \brief Legacy pass for lowering expect intrinsics out of the IR. 170283625Sdim/// 171283625Sdim/// When this pass is run over a function it uses expect intrinsics which feed 172283625Sdim/// branches and switches to provide branch weight metadata for those 173283625Sdim/// terminators. It then removes the expect intrinsics from the IR so the rest 174283625Sdim/// of the optimizer can ignore them. 175283625Sdimclass LowerExpectIntrinsic : public FunctionPass { 176283625Sdimpublic: 177283625Sdim static char ID; 178283625Sdim LowerExpectIntrinsic() : FunctionPass(ID) { 179283625Sdim initializeLowerExpectIntrinsicPass(*PassRegistry::getPassRegistry()); 180283625Sdim } 181283625Sdim 182283625Sdim bool runOnFunction(Function &F) override { return lowerExpectIntrinsic(F); } 183283625Sdim}; 184285181Sdim} 185283625Sdim 186283625Sdimchar LowerExpectIntrinsic::ID = 0; 187283625SdimINITIALIZE_PASS(LowerExpectIntrinsic, "lower-expect", 188283625Sdim "Lower 'expect' Intrinsics", false, false) 189283625Sdim 190283625SdimFunctionPass *llvm::createLowerExpectIntrinsicPass() { 191283625Sdim return new LowerExpectIntrinsic(); 192283625Sdim} 193