1//===- LowerExpectIntrinsic.cpp - Lower expect intrinsic ------------------===// 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// This pass lowers the 'expect' intrinsic to LLVM metadata. 11// 12//===----------------------------------------------------------------------===// 13 14#include "llvm/Transforms/Scalar/LowerExpectIntrinsic.h" 15#include "llvm/ADT/SmallVector.h" 16#include "llvm/ADT/Statistic.h" 17#include "llvm/IR/BasicBlock.h" 18#include "llvm/IR/Constants.h" 19#include "llvm/IR/Function.h" 20#include "llvm/IR/Instructions.h" 21#include "llvm/IR/Intrinsics.h" 22#include "llvm/IR/LLVMContext.h" 23#include "llvm/IR/MDBuilder.h" 24#include "llvm/IR/Metadata.h" 25#include "llvm/Pass.h" 26#include "llvm/Support/CommandLine.h" 27#include "llvm/Support/Debug.h" 28#include "llvm/Transforms/Scalar.h" 29 30using namespace llvm; 31 32#define DEBUG_TYPE "lower-expect-intrinsic" 33 34STATISTIC(ExpectIntrinsicsHandled, 35 "Number of 'expect' intrinsic instructions handled"); 36 37static cl::opt<uint32_t> 38LikelyBranchWeight("likely-branch-weight", cl::Hidden, cl::init(64), 39 cl::desc("Weight of the branch likely to be taken (default = 64)")); 40static cl::opt<uint32_t> 41UnlikelyBranchWeight("unlikely-branch-weight", cl::Hidden, cl::init(4), 42 cl::desc("Weight of the branch unlikely to be taken (default = 4)")); 43 44static bool handleSwitchExpect(SwitchInst &SI) { 45 CallInst *CI = dyn_cast<CallInst>(SI.getCondition()); 46 if (!CI) 47 return false; 48 49 Function *Fn = CI->getCalledFunction(); 50 if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect) 51 return false; 52 53 Value *ArgValue = CI->getArgOperand(0); 54 ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 55 if (!ExpectedValue) 56 return false; 57 58 SwitchInst::CaseIt Case = SI.findCaseValue(ExpectedValue); 59 unsigned n = SI.getNumCases(); // +1 for default case. 60 SmallVector<uint32_t, 16> Weights(n + 1, UnlikelyBranchWeight); 61 62 if (Case == SI.case_default()) 63 Weights[0] = LikelyBranchWeight; 64 else 65 Weights[Case.getCaseIndex() + 1] = LikelyBranchWeight; 66 67 SI.setMetadata(LLVMContext::MD_prof, 68 MDBuilder(CI->getContext()).createBranchWeights(Weights)); 69 70 SI.setCondition(ArgValue); 71 return true; 72} 73 74static bool handleBranchExpect(BranchInst &BI) { 75 if (BI.isUnconditional()) 76 return false; 77 78 // Handle non-optimized IR code like: 79 // %expval = call i64 @llvm.expect.i64(i64 %conv1, i64 1) 80 // %tobool = icmp ne i64 %expval, 0 81 // br i1 %tobool, label %if.then, label %if.end 82 // 83 // Or the following simpler case: 84 // %expval = call i1 @llvm.expect.i1(i1 %cmp, i1 1) 85 // br i1 %expval, label %if.then, label %if.end 86 87 CallInst *CI; 88 89 ICmpInst *CmpI = dyn_cast<ICmpInst>(BI.getCondition()); 90 if (!CmpI) { 91 CI = dyn_cast<CallInst>(BI.getCondition()); 92 } else { 93 if (CmpI->getPredicate() != CmpInst::ICMP_NE) 94 return false; 95 CI = dyn_cast<CallInst>(CmpI->getOperand(0)); 96 } 97 98 if (!CI) 99 return false; 100 101 Function *Fn = CI->getCalledFunction(); 102 if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect) 103 return false; 104 105 Value *ArgValue = CI->getArgOperand(0); 106 ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 107 if (!ExpectedValue) 108 return false; 109 110 MDBuilder MDB(CI->getContext()); 111 MDNode *Node; 112 113 // If expect value is equal to 1 it means that we are more likely to take 114 // branch 0, in other case more likely is branch 1. 115 if (ExpectedValue->isOne()) 116 Node = MDB.createBranchWeights(LikelyBranchWeight, UnlikelyBranchWeight); 117 else 118 Node = MDB.createBranchWeights(UnlikelyBranchWeight, LikelyBranchWeight); 119 120 BI.setMetadata(LLVMContext::MD_prof, Node); 121 122 if (CmpI) 123 CmpI->setOperand(0, ArgValue); 124 else 125 BI.setCondition(ArgValue); 126 return true; 127} 128 129static bool lowerExpectIntrinsic(Function &F) { 130 bool Changed = false; 131 132 for (BasicBlock &BB : F) { 133 // Create "block_weights" metadata. 134 if (BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator())) { 135 if (handleBranchExpect(*BI)) 136 ExpectIntrinsicsHandled++; 137 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB.getTerminator())) { 138 if (handleSwitchExpect(*SI)) 139 ExpectIntrinsicsHandled++; 140 } 141 142 // remove llvm.expect intrinsics. 143 for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) { 144 CallInst *CI = dyn_cast<CallInst>(BI++); 145 if (!CI) 146 continue; 147 148 Function *Fn = CI->getCalledFunction(); 149 if (Fn && Fn->getIntrinsicID() == Intrinsic::expect) { 150 Value *Exp = CI->getArgOperand(0); 151 CI->replaceAllUsesWith(Exp); 152 CI->eraseFromParent(); 153 Changed = true; 154 } 155 } 156 } 157 158 return Changed; 159} 160 161PreservedAnalyses LowerExpectIntrinsicPass::run(Function &F) { 162 if (lowerExpectIntrinsic(F)) 163 return PreservedAnalyses::none(); 164 165 return PreservedAnalyses::all(); 166} 167 168namespace { 169/// \brief Legacy pass for lowering expect intrinsics out of the IR. 170/// 171/// When this pass is run over a function it uses expect intrinsics which feed 172/// branches and switches to provide branch weight metadata for those 173/// terminators. It then removes the expect intrinsics from the IR so the rest 174/// of the optimizer can ignore them. 175class LowerExpectIntrinsic : public FunctionPass { 176public: 177 static char ID; 178 LowerExpectIntrinsic() : FunctionPass(ID) { 179 initializeLowerExpectIntrinsicPass(*PassRegistry::getPassRegistry()); 180 } 181 182 bool runOnFunction(Function &F) override { return lowerExpectIntrinsic(F); } 183}; 184} 185 186char LowerExpectIntrinsic::ID = 0; 187INITIALIZE_PASS(LowerExpectIntrinsic, "lower-expect", 188 "Lower 'expect' Intrinsics", false, false) 189 190FunctionPass *llvm::createLowerExpectIntrinsicPass() { 191 return new LowerExpectIntrinsic(); 192} 193