1 //===- LowerExpectIntrinsic.cpp - Lower expect intrinsic ------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This pass lowers the 'expect' intrinsic to LLVM metadata. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/Transforms/Scalar/LowerExpectIntrinsic.h" 14 #include "llvm/ADT/SmallVector.h" 15 #include "llvm/ADT/Statistic.h" 16 #include "llvm/ADT/iterator_range.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::CaseHandle 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 /// Handler for PHINodes that define the value argument to an 87 /// @llvm.expect call. 88 /// 89 /// If the operand of the phi has a constant value and it 'contradicts' 90 /// with the expected value of phi def, then the corresponding incoming 91 /// edge of the phi is unlikely to be taken. Using that information, 92 /// the branch probability info for the originating branch can be inferred. 93 static void handlePhiDef(CallInst *Expect) { 94 Value &Arg = *Expect->getArgOperand(0); 95 ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(Expect->getArgOperand(1)); 96 if (!ExpectedValue) 97 return; 98 const APInt &ExpectedPhiValue = ExpectedValue->getValue(); 99 100 // Walk up in backward a list of instructions that 101 // have 'copy' semantics by 'stripping' the copies 102 // until a PHI node or an instruction of unknown kind 103 // is reached. Negation via xor is also handled. 104 // 105 // C = PHI(...); 106 // B = C; 107 // A = B; 108 // D = __builtin_expect(A, 0); 109 // 110 Value *V = &Arg; 111 SmallVector<Instruction *, 4> Operations; 112 while (!isa<PHINode>(V)) { 113 if (ZExtInst *ZExt = dyn_cast<ZExtInst>(V)) { 114 V = ZExt->getOperand(0); 115 Operations.push_back(ZExt); 116 continue; 117 } 118 119 if (SExtInst *SExt = dyn_cast<SExtInst>(V)) { 120 V = SExt->getOperand(0); 121 Operations.push_back(SExt); 122 continue; 123 } 124 125 BinaryOperator *BinOp = dyn_cast<BinaryOperator>(V); 126 if (!BinOp || BinOp->getOpcode() != Instruction::Xor) 127 return; 128 129 ConstantInt *CInt = dyn_cast<ConstantInt>(BinOp->getOperand(1)); 130 if (!CInt) 131 return; 132 133 V = BinOp->getOperand(0); 134 Operations.push_back(BinOp); 135 } 136 137 // Executes the recorded operations on input 'Value'. 138 auto ApplyOperations = [&](const APInt &Value) { 139 APInt Result = Value; 140 for (auto Op : llvm::reverse(Operations)) { 141 switch (Op->getOpcode()) { 142 case Instruction::Xor: 143 Result ^= cast<ConstantInt>(Op->getOperand(1))->getValue(); 144 break; 145 case Instruction::ZExt: 146 Result = Result.zext(Op->getType()->getIntegerBitWidth()); 147 break; 148 case Instruction::SExt: 149 Result = Result.sext(Op->getType()->getIntegerBitWidth()); 150 break; 151 default: 152 llvm_unreachable("Unexpected operation"); 153 } 154 } 155 return Result; 156 }; 157 158 auto *PhiDef = dyn_cast<PHINode>(V); 159 160 // Get the first dominating conditional branch of the operand 161 // i's incoming block. 162 auto GetDomConditional = [&](unsigned i) -> BranchInst * { 163 BasicBlock *BB = PhiDef->getIncomingBlock(i); 164 BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 165 if (BI && BI->isConditional()) 166 return BI; 167 BB = BB->getSinglePredecessor(); 168 if (!BB) 169 return nullptr; 170 BI = dyn_cast<BranchInst>(BB->getTerminator()); 171 if (!BI || BI->isUnconditional()) 172 return nullptr; 173 return BI; 174 }; 175 176 // Now walk through all Phi operands to find phi oprerands with values 177 // conflicting with the expected phi output value. Any such operand 178 // indicates the incoming edge to that operand is unlikely. 179 for (unsigned i = 0, e = PhiDef->getNumIncomingValues(); i != e; ++i) { 180 181 Value *PhiOpnd = PhiDef->getIncomingValue(i); 182 ConstantInt *CI = dyn_cast<ConstantInt>(PhiOpnd); 183 if (!CI) 184 continue; 185 186 // Not an interesting case when IsUnlikely is false -- we can not infer 187 // anything useful when the operand value matches the expected phi 188 // output. 189 if (ExpectedPhiValue == ApplyOperations(CI->getValue())) 190 continue; 191 192 BranchInst *BI = GetDomConditional(i); 193 if (!BI) 194 continue; 195 196 MDBuilder MDB(PhiDef->getContext()); 197 198 // There are two situations in which an operand of the PhiDef comes 199 // from a given successor of a branch instruction BI. 200 // 1) When the incoming block of the operand is the successor block; 201 // 2) When the incoming block is BI's enclosing block and the 202 // successor is the PhiDef's enclosing block. 203 // 204 // Returns true if the operand which comes from OpndIncomingBB 205 // comes from outgoing edge of BI that leads to Succ block. 206 auto *OpndIncomingBB = PhiDef->getIncomingBlock(i); 207 auto IsOpndComingFromSuccessor = [&](BasicBlock *Succ) { 208 if (OpndIncomingBB == Succ) 209 // If this successor is the incoming block for this 210 // Phi operand, then this successor does lead to the Phi. 211 return true; 212 if (OpndIncomingBB == BI->getParent() && Succ == PhiDef->getParent()) 213 // Otherwise, if the edge is directly from the branch 214 // to the Phi, this successor is the one feeding this 215 // Phi operand. 216 return true; 217 return false; 218 }; 219 220 if (IsOpndComingFromSuccessor(BI->getSuccessor(1))) 221 BI->setMetadata( 222 LLVMContext::MD_prof, 223 MDB.createBranchWeights(LikelyBranchWeight, UnlikelyBranchWeight)); 224 else if (IsOpndComingFromSuccessor(BI->getSuccessor(0))) 225 BI->setMetadata( 226 LLVMContext::MD_prof, 227 MDB.createBranchWeights(UnlikelyBranchWeight, LikelyBranchWeight)); 228 } 229 } 230 231 // Handle both BranchInst and SelectInst. 232 template <class BrSelInst> static bool handleBrSelExpect(BrSelInst &BSI) { 233 234 // Handle non-optimized IR code like: 235 // %expval = call i64 @llvm.expect.i64(i64 %conv1, i64 1) 236 // %tobool = icmp ne i64 %expval, 0 237 // br i1 %tobool, label %if.then, label %if.end 238 // 239 // Or the following simpler case: 240 // %expval = call i1 @llvm.expect.i1(i1 %cmp, i1 1) 241 // br i1 %expval, label %if.then, label %if.end 242 243 CallInst *CI; 244 245 ICmpInst *CmpI = dyn_cast<ICmpInst>(BSI.getCondition()); 246 CmpInst::Predicate Predicate; 247 ConstantInt *CmpConstOperand = nullptr; 248 if (!CmpI) { 249 CI = dyn_cast<CallInst>(BSI.getCondition()); 250 Predicate = CmpInst::ICMP_NE; 251 } else { 252 Predicate = CmpI->getPredicate(); 253 if (Predicate != CmpInst::ICMP_NE && Predicate != CmpInst::ICMP_EQ) 254 return false; 255 256 CmpConstOperand = dyn_cast<ConstantInt>(CmpI->getOperand(1)); 257 if (!CmpConstOperand) 258 return false; 259 CI = dyn_cast<CallInst>(CmpI->getOperand(0)); 260 } 261 262 if (!CI) 263 return false; 264 265 uint64_t ValueComparedTo = 0; 266 if (CmpConstOperand) { 267 if (CmpConstOperand->getBitWidth() > 64) 268 return false; 269 ValueComparedTo = CmpConstOperand->getZExtValue(); 270 } 271 272 Function *Fn = CI->getCalledFunction(); 273 if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect) 274 return false; 275 276 Value *ArgValue = CI->getArgOperand(0); 277 ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 278 if (!ExpectedValue) 279 return false; 280 281 MDBuilder MDB(CI->getContext()); 282 MDNode *Node; 283 284 if ((ExpectedValue->getZExtValue() == ValueComparedTo) == 285 (Predicate == CmpInst::ICMP_EQ)) 286 Node = MDB.createBranchWeights(LikelyBranchWeight, UnlikelyBranchWeight); 287 else 288 Node = MDB.createBranchWeights(UnlikelyBranchWeight, LikelyBranchWeight); 289 290 BSI.setMetadata(LLVMContext::MD_prof, Node); 291 292 if (CmpI) 293 CmpI->setOperand(0, ArgValue); 294 else 295 BSI.setCondition(ArgValue); 296 return true; 297 } 298 299 static bool handleBranchExpect(BranchInst &BI) { 300 if (BI.isUnconditional()) 301 return false; 302 303 return handleBrSelExpect<BranchInst>(BI); 304 } 305 306 static bool lowerExpectIntrinsic(Function &F) { 307 bool Changed = false; 308 309 for (BasicBlock &BB : F) { 310 // Create "block_weights" metadata. 311 if (BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator())) { 312 if (handleBranchExpect(*BI)) 313 ExpectIntrinsicsHandled++; 314 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB.getTerminator())) { 315 if (handleSwitchExpect(*SI)) 316 ExpectIntrinsicsHandled++; 317 } 318 319 // Remove llvm.expect intrinsics. Iterate backwards in order 320 // to process select instructions before the intrinsic gets 321 // removed. 322 for (auto BI = BB.rbegin(), BE = BB.rend(); BI != BE;) { 323 Instruction *Inst = &*BI++; 324 CallInst *CI = dyn_cast<CallInst>(Inst); 325 if (!CI) { 326 if (SelectInst *SI = dyn_cast<SelectInst>(Inst)) { 327 if (handleBrSelExpect(*SI)) 328 ExpectIntrinsicsHandled++; 329 } 330 continue; 331 } 332 333 Function *Fn = CI->getCalledFunction(); 334 if (Fn && Fn->getIntrinsicID() == Intrinsic::expect) { 335 // Before erasing the llvm.expect, walk backward to find 336 // phi that define llvm.expect's first arg, and 337 // infer branch probability: 338 handlePhiDef(CI); 339 Value *Exp = CI->getArgOperand(0); 340 CI->replaceAllUsesWith(Exp); 341 CI->eraseFromParent(); 342 Changed = true; 343 } 344 } 345 } 346 347 return Changed; 348 } 349 350 PreservedAnalyses LowerExpectIntrinsicPass::run(Function &F, 351 FunctionAnalysisManager &) { 352 if (lowerExpectIntrinsic(F)) 353 return PreservedAnalyses::none(); 354 355 return PreservedAnalyses::all(); 356 } 357 358 namespace { 359 /// Legacy pass for lowering expect intrinsics out of the IR. 360 /// 361 /// When this pass is run over a function it uses expect intrinsics which feed 362 /// branches and switches to provide branch weight metadata for those 363 /// terminators. It then removes the expect intrinsics from the IR so the rest 364 /// of the optimizer can ignore them. 365 class LowerExpectIntrinsic : public FunctionPass { 366 public: 367 static char ID; 368 LowerExpectIntrinsic() : FunctionPass(ID) { 369 initializeLowerExpectIntrinsicPass(*PassRegistry::getPassRegistry()); 370 } 371 372 bool runOnFunction(Function &F) override { return lowerExpectIntrinsic(F); } 373 }; 374 } 375 376 char LowerExpectIntrinsic::ID = 0; 377 INITIALIZE_PASS(LowerExpectIntrinsic, "lower-expect", 378 "Lower 'expect' Intrinsics", false, false) 379 380 FunctionPass *llvm::createLowerExpectIntrinsicPass() { 381 return new LowerExpectIntrinsic(); 382 } 383