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 30 using namespace llvm; 31 32 #define DEBUG_TYPE "lower-expect-intrinsic" 33 34 STATISTIC(ExpectIntrinsicsHandled, 35 "Number of 'expect' intrinsic instructions handled"); 36 37 // These default values are chosen to represent an extremely skewed outcome for 38 // a condition, but they leave some room for interpretation by later passes. 39 // 40 // If the documentation for __builtin_expect() was made explicit that it should 41 // only be used in extreme cases, we could make this ratio higher. As it stands, 42 // programmers may be using __builtin_expect() / llvm.expect to annotate that a 43 // branch is likely or unlikely to be taken. 44 // 45 // There is a known dependency on this ratio in CodeGenPrepare when transforming 46 // 'select' instructions. It may be worthwhile to hoist these values to some 47 // shared space, so they can be used directly by other passes. 48 49 static cl::opt<uint32_t> LikelyBranchWeight( 50 "likely-branch-weight", cl::Hidden, cl::init(2000), 51 cl::desc("Weight of the branch likely to be taken (default = 2000)")); 52 static cl::opt<uint32_t> UnlikelyBranchWeight( 53 "unlikely-branch-weight", cl::Hidden, cl::init(1), 54 cl::desc("Weight of the branch unlikely to be taken (default = 1)")); 55 56 static bool handleSwitchExpect(SwitchInst &SI) { 57 CallInst *CI = dyn_cast<CallInst>(SI.getCondition()); 58 if (!CI) 59 return false; 60 61 Function *Fn = CI->getCalledFunction(); 62 if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect) 63 return false; 64 65 Value *ArgValue = CI->getArgOperand(0); 66 ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 67 if (!ExpectedValue) 68 return false; 69 70 SwitchInst::CaseIt Case = SI.findCaseValue(ExpectedValue); 71 unsigned n = SI.getNumCases(); // +1 for default case. 72 SmallVector<uint32_t, 16> Weights(n + 1, UnlikelyBranchWeight); 73 74 if (Case == SI.case_default()) 75 Weights[0] = LikelyBranchWeight; 76 else 77 Weights[Case.getCaseIndex() + 1] = LikelyBranchWeight; 78 79 SI.setMetadata(LLVMContext::MD_prof, 80 MDBuilder(CI->getContext()).createBranchWeights(Weights)); 81 82 SI.setCondition(ArgValue); 83 return true; 84 } 85 86 static bool handleBranchExpect(BranchInst &BI) { 87 if (BI.isUnconditional()) 88 return false; 89 90 // Handle non-optimized IR code like: 91 // %expval = call i64 @llvm.expect.i64(i64 %conv1, i64 1) 92 // %tobool = icmp ne i64 %expval, 0 93 // br i1 %tobool, label %if.then, label %if.end 94 // 95 // Or the following simpler case: 96 // %expval = call i1 @llvm.expect.i1(i1 %cmp, i1 1) 97 // br i1 %expval, label %if.then, label %if.end 98 99 CallInst *CI; 100 101 ICmpInst *CmpI = dyn_cast<ICmpInst>(BI.getCondition()); 102 if (!CmpI) { 103 CI = dyn_cast<CallInst>(BI.getCondition()); 104 } else { 105 if (CmpI->getPredicate() != CmpInst::ICMP_NE) 106 return false; 107 CI = dyn_cast<CallInst>(CmpI->getOperand(0)); 108 } 109 110 if (!CI) 111 return false; 112 113 Function *Fn = CI->getCalledFunction(); 114 if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect) 115 return false; 116 117 Value *ArgValue = CI->getArgOperand(0); 118 ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 119 if (!ExpectedValue) 120 return false; 121 122 MDBuilder MDB(CI->getContext()); 123 MDNode *Node; 124 125 // If expect value is equal to 1 it means that we are more likely to take 126 // branch 0, in other case more likely is branch 1. 127 if (ExpectedValue->isOne()) 128 Node = MDB.createBranchWeights(LikelyBranchWeight, UnlikelyBranchWeight); 129 else 130 Node = MDB.createBranchWeights(UnlikelyBranchWeight, LikelyBranchWeight); 131 132 BI.setMetadata(LLVMContext::MD_prof, Node); 133 134 if (CmpI) 135 CmpI->setOperand(0, ArgValue); 136 else 137 BI.setCondition(ArgValue); 138 return true; 139 } 140 141 static bool lowerExpectIntrinsic(Function &F) { 142 bool Changed = false; 143 144 for (BasicBlock &BB : F) { 145 // Create "block_weights" metadata. 146 if (BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator())) { 147 if (handleBranchExpect(*BI)) 148 ExpectIntrinsicsHandled++; 149 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB.getTerminator())) { 150 if (handleSwitchExpect(*SI)) 151 ExpectIntrinsicsHandled++; 152 } 153 154 // Remove llvm.expect intrinsics. 155 for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) { 156 CallInst *CI = dyn_cast<CallInst>(BI++); 157 if (!CI) 158 continue; 159 160 Function *Fn = CI->getCalledFunction(); 161 if (Fn && Fn->getIntrinsicID() == Intrinsic::expect) { 162 Value *Exp = CI->getArgOperand(0); 163 CI->replaceAllUsesWith(Exp); 164 CI->eraseFromParent(); 165 Changed = true; 166 } 167 } 168 } 169 170 return Changed; 171 } 172 173 PreservedAnalyses LowerExpectIntrinsicPass::run(Function &F, 174 FunctionAnalysisManager &) { 175 if (lowerExpectIntrinsic(F)) 176 return PreservedAnalyses::none(); 177 178 return PreservedAnalyses::all(); 179 } 180 181 namespace { 182 /// \brief Legacy pass for lowering expect intrinsics out of the IR. 183 /// 184 /// When this pass is run over a function it uses expect intrinsics which feed 185 /// branches and switches to provide branch weight metadata for those 186 /// terminators. It then removes the expect intrinsics from the IR so the rest 187 /// of the optimizer can ignore them. 188 class LowerExpectIntrinsic : public FunctionPass { 189 public: 190 static char ID; 191 LowerExpectIntrinsic() : FunctionPass(ID) { 192 initializeLowerExpectIntrinsicPass(*PassRegistry::getPassRegistry()); 193 } 194 195 bool runOnFunction(Function &F) override { return lowerExpectIntrinsic(F); } 196 }; 197 } 198 199 char LowerExpectIntrinsic::ID = 0; 200 INITIALIZE_PASS(LowerExpectIntrinsic, "lower-expect", 201 "Lower 'expect' Intrinsics", false, false) 202 203 FunctionPass *llvm::createLowerExpectIntrinsicPass() { 204 return new LowerExpectIntrinsic(); 205 } 206