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/InitializePasses.h" 26 #include "llvm/Pass.h" 27 #include "llvm/Support/CommandLine.h" 28 #include "llvm/Support/Debug.h" 29 #include "llvm/Transforms/Scalar.h" 30 #include "llvm/Transforms/Utils/MisExpect.h" 31 32 using namespace llvm; 33 34 #define DEBUG_TYPE "lower-expect-intrinsic" 35 36 STATISTIC(ExpectIntrinsicsHandled, 37 "Number of 'expect' intrinsic instructions handled"); 38 39 // These default values are chosen to represent an extremely skewed outcome for 40 // a condition, but they leave some room for interpretation by later passes. 41 // 42 // If the documentation for __builtin_expect() was made explicit that it should 43 // only be used in extreme cases, we could make this ratio higher. As it stands, 44 // programmers may be using __builtin_expect() / llvm.expect to annotate that a 45 // branch is likely or unlikely to be taken. 46 // 47 // There is a known dependency on this ratio in CodeGenPrepare when transforming 48 // 'select' instructions. It may be worthwhile to hoist these values to some 49 // shared space, so they can be used directly by other passes. 50 51 static cl::opt<uint32_t> LikelyBranchWeight( 52 "likely-branch-weight", cl::Hidden, cl::init(2000), 53 cl::desc("Weight of the branch likely to be taken (default = 2000)")); 54 static cl::opt<uint32_t> UnlikelyBranchWeight( 55 "unlikely-branch-weight", cl::Hidden, cl::init(1), 56 cl::desc("Weight of the branch unlikely to be taken (default = 1)")); 57 58 static bool handleSwitchExpect(SwitchInst &SI) { 59 CallInst *CI = dyn_cast<CallInst>(SI.getCondition()); 60 if (!CI) 61 return false; 62 63 Function *Fn = CI->getCalledFunction(); 64 if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect) 65 return false; 66 67 Value *ArgValue = CI->getArgOperand(0); 68 ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 69 if (!ExpectedValue) 70 return false; 71 72 SwitchInst::CaseHandle Case = *SI.findCaseValue(ExpectedValue); 73 unsigned n = SI.getNumCases(); // +1 for default case. 74 SmallVector<uint32_t, 16> Weights(n + 1, UnlikelyBranchWeight); 75 76 uint64_t Index = (Case == *SI.case_default()) ? 0 : Case.getCaseIndex() + 1; 77 Weights[Index] = LikelyBranchWeight; 78 79 SI.setMetadata( 80 LLVMContext::MD_misexpect, 81 MDBuilder(CI->getContext()) 82 .createMisExpect(Index, LikelyBranchWeight, UnlikelyBranchWeight)); 83 84 SI.setCondition(ArgValue); 85 misexpect::checkFrontendInstrumentation(SI); 86 87 SI.setMetadata(LLVMContext::MD_prof, 88 MDBuilder(CI->getContext()).createBranchWeights(Weights)); 89 90 return true; 91 } 92 93 /// Handler for PHINodes that define the value argument to an 94 /// @llvm.expect call. 95 /// 96 /// If the operand of the phi has a constant value and it 'contradicts' 97 /// with the expected value of phi def, then the corresponding incoming 98 /// edge of the phi is unlikely to be taken. Using that information, 99 /// the branch probability info for the originating branch can be inferred. 100 static void handlePhiDef(CallInst *Expect) { 101 Value &Arg = *Expect->getArgOperand(0); 102 ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(Expect->getArgOperand(1)); 103 if (!ExpectedValue) 104 return; 105 const APInt &ExpectedPhiValue = ExpectedValue->getValue(); 106 107 // Walk up in backward a list of instructions that 108 // have 'copy' semantics by 'stripping' the copies 109 // until a PHI node or an instruction of unknown kind 110 // is reached. Negation via xor is also handled. 111 // 112 // C = PHI(...); 113 // B = C; 114 // A = B; 115 // D = __builtin_expect(A, 0); 116 // 117 Value *V = &Arg; 118 SmallVector<Instruction *, 4> Operations; 119 while (!isa<PHINode>(V)) { 120 if (ZExtInst *ZExt = dyn_cast<ZExtInst>(V)) { 121 V = ZExt->getOperand(0); 122 Operations.push_back(ZExt); 123 continue; 124 } 125 126 if (SExtInst *SExt = dyn_cast<SExtInst>(V)) { 127 V = SExt->getOperand(0); 128 Operations.push_back(SExt); 129 continue; 130 } 131 132 BinaryOperator *BinOp = dyn_cast<BinaryOperator>(V); 133 if (!BinOp || BinOp->getOpcode() != Instruction::Xor) 134 return; 135 136 ConstantInt *CInt = dyn_cast<ConstantInt>(BinOp->getOperand(1)); 137 if (!CInt) 138 return; 139 140 V = BinOp->getOperand(0); 141 Operations.push_back(BinOp); 142 } 143 144 // Executes the recorded operations on input 'Value'. 145 auto ApplyOperations = [&](const APInt &Value) { 146 APInt Result = Value; 147 for (auto Op : llvm::reverse(Operations)) { 148 switch (Op->getOpcode()) { 149 case Instruction::Xor: 150 Result ^= cast<ConstantInt>(Op->getOperand(1))->getValue(); 151 break; 152 case Instruction::ZExt: 153 Result = Result.zext(Op->getType()->getIntegerBitWidth()); 154 break; 155 case Instruction::SExt: 156 Result = Result.sext(Op->getType()->getIntegerBitWidth()); 157 break; 158 default: 159 llvm_unreachable("Unexpected operation"); 160 } 161 } 162 return Result; 163 }; 164 165 auto *PhiDef = cast<PHINode>(V); 166 167 // Get the first dominating conditional branch of the operand 168 // i's incoming block. 169 auto GetDomConditional = [&](unsigned i) -> BranchInst * { 170 BasicBlock *BB = PhiDef->getIncomingBlock(i); 171 BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 172 if (BI && BI->isConditional()) 173 return BI; 174 BB = BB->getSinglePredecessor(); 175 if (!BB) 176 return nullptr; 177 BI = dyn_cast<BranchInst>(BB->getTerminator()); 178 if (!BI || BI->isUnconditional()) 179 return nullptr; 180 return BI; 181 }; 182 183 // Now walk through all Phi operands to find phi oprerands with values 184 // conflicting with the expected phi output value. Any such operand 185 // indicates the incoming edge to that operand is unlikely. 186 for (unsigned i = 0, e = PhiDef->getNumIncomingValues(); i != e; ++i) { 187 188 Value *PhiOpnd = PhiDef->getIncomingValue(i); 189 ConstantInt *CI = dyn_cast<ConstantInt>(PhiOpnd); 190 if (!CI) 191 continue; 192 193 // Not an interesting case when IsUnlikely is false -- we can not infer 194 // anything useful when the operand value matches the expected phi 195 // output. 196 if (ExpectedPhiValue == ApplyOperations(CI->getValue())) 197 continue; 198 199 BranchInst *BI = GetDomConditional(i); 200 if (!BI) 201 continue; 202 203 MDBuilder MDB(PhiDef->getContext()); 204 205 // There are two situations in which an operand of the PhiDef comes 206 // from a given successor of a branch instruction BI. 207 // 1) When the incoming block of the operand is the successor block; 208 // 2) When the incoming block is BI's enclosing block and the 209 // successor is the PhiDef's enclosing block. 210 // 211 // Returns true if the operand which comes from OpndIncomingBB 212 // comes from outgoing edge of BI that leads to Succ block. 213 auto *OpndIncomingBB = PhiDef->getIncomingBlock(i); 214 auto IsOpndComingFromSuccessor = [&](BasicBlock *Succ) { 215 if (OpndIncomingBB == Succ) 216 // If this successor is the incoming block for this 217 // Phi operand, then this successor does lead to the Phi. 218 return true; 219 if (OpndIncomingBB == BI->getParent() && Succ == PhiDef->getParent()) 220 // Otherwise, if the edge is directly from the branch 221 // to the Phi, this successor is the one feeding this 222 // Phi operand. 223 return true; 224 return false; 225 }; 226 227 if (IsOpndComingFromSuccessor(BI->getSuccessor(1))) 228 BI->setMetadata( 229 LLVMContext::MD_prof, 230 MDB.createBranchWeights(LikelyBranchWeight, UnlikelyBranchWeight)); 231 else if (IsOpndComingFromSuccessor(BI->getSuccessor(0))) 232 BI->setMetadata( 233 LLVMContext::MD_prof, 234 MDB.createBranchWeights(UnlikelyBranchWeight, LikelyBranchWeight)); 235 } 236 } 237 238 // Handle both BranchInst and SelectInst. 239 template <class BrSelInst> static bool handleBrSelExpect(BrSelInst &BSI) { 240 241 // Handle non-optimized IR code like: 242 // %expval = call i64 @llvm.expect.i64(i64 %conv1, i64 1) 243 // %tobool = icmp ne i64 %expval, 0 244 // br i1 %tobool, label %if.then, label %if.end 245 // 246 // Or the following simpler case: 247 // %expval = call i1 @llvm.expect.i1(i1 %cmp, i1 1) 248 // br i1 %expval, label %if.then, label %if.end 249 250 CallInst *CI; 251 252 ICmpInst *CmpI = dyn_cast<ICmpInst>(BSI.getCondition()); 253 CmpInst::Predicate Predicate; 254 ConstantInt *CmpConstOperand = nullptr; 255 if (!CmpI) { 256 CI = dyn_cast<CallInst>(BSI.getCondition()); 257 Predicate = CmpInst::ICMP_NE; 258 } else { 259 Predicate = CmpI->getPredicate(); 260 if (Predicate != CmpInst::ICMP_NE && Predicate != CmpInst::ICMP_EQ) 261 return false; 262 263 CmpConstOperand = dyn_cast<ConstantInt>(CmpI->getOperand(1)); 264 if (!CmpConstOperand) 265 return false; 266 CI = dyn_cast<CallInst>(CmpI->getOperand(0)); 267 } 268 269 if (!CI) 270 return false; 271 272 uint64_t ValueComparedTo = 0; 273 if (CmpConstOperand) { 274 if (CmpConstOperand->getBitWidth() > 64) 275 return false; 276 ValueComparedTo = CmpConstOperand->getZExtValue(); 277 } 278 279 Function *Fn = CI->getCalledFunction(); 280 if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect) 281 return false; 282 283 Value *ArgValue = CI->getArgOperand(0); 284 ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 285 if (!ExpectedValue) 286 return false; 287 288 MDBuilder MDB(CI->getContext()); 289 MDNode *Node; 290 MDNode *ExpNode; 291 292 if ((ExpectedValue->getZExtValue() == ValueComparedTo) == 293 (Predicate == CmpInst::ICMP_EQ)) { 294 Node = MDB.createBranchWeights(LikelyBranchWeight, UnlikelyBranchWeight); 295 ExpNode = MDB.createMisExpect(0, LikelyBranchWeight, UnlikelyBranchWeight); 296 } else { 297 Node = MDB.createBranchWeights(UnlikelyBranchWeight, LikelyBranchWeight); 298 ExpNode = MDB.createMisExpect(1, LikelyBranchWeight, UnlikelyBranchWeight); 299 } 300 301 BSI.setMetadata(LLVMContext::MD_misexpect, ExpNode); 302 303 if (CmpI) 304 CmpI->setOperand(0, ArgValue); 305 else 306 BSI.setCondition(ArgValue); 307 308 misexpect::checkFrontendInstrumentation(BSI); 309 310 BSI.setMetadata(LLVMContext::MD_prof, Node); 311 312 return true; 313 } 314 315 static bool handleBranchExpect(BranchInst &BI) { 316 if (BI.isUnconditional()) 317 return false; 318 319 return handleBrSelExpect<BranchInst>(BI); 320 } 321 322 static bool lowerExpectIntrinsic(Function &F) { 323 bool Changed = false; 324 325 for (BasicBlock &BB : F) { 326 // Create "block_weights" metadata. 327 if (BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator())) { 328 if (handleBranchExpect(*BI)) 329 ExpectIntrinsicsHandled++; 330 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB.getTerminator())) { 331 if (handleSwitchExpect(*SI)) 332 ExpectIntrinsicsHandled++; 333 } 334 335 // Remove llvm.expect intrinsics. Iterate backwards in order 336 // to process select instructions before the intrinsic gets 337 // removed. 338 for (auto BI = BB.rbegin(), BE = BB.rend(); BI != BE;) { 339 Instruction *Inst = &*BI++; 340 CallInst *CI = dyn_cast<CallInst>(Inst); 341 if (!CI) { 342 if (SelectInst *SI = dyn_cast<SelectInst>(Inst)) { 343 if (handleBrSelExpect(*SI)) 344 ExpectIntrinsicsHandled++; 345 } 346 continue; 347 } 348 349 Function *Fn = CI->getCalledFunction(); 350 if (Fn && Fn->getIntrinsicID() == Intrinsic::expect) { 351 // Before erasing the llvm.expect, walk backward to find 352 // phi that define llvm.expect's first arg, and 353 // infer branch probability: 354 handlePhiDef(CI); 355 Value *Exp = CI->getArgOperand(0); 356 CI->replaceAllUsesWith(Exp); 357 CI->eraseFromParent(); 358 Changed = true; 359 } 360 } 361 } 362 363 return Changed; 364 } 365 366 PreservedAnalyses LowerExpectIntrinsicPass::run(Function &F, 367 FunctionAnalysisManager &) { 368 if (lowerExpectIntrinsic(F)) 369 return PreservedAnalyses::none(); 370 371 return PreservedAnalyses::all(); 372 } 373 374 namespace { 375 /// Legacy pass for lowering expect intrinsics out of the IR. 376 /// 377 /// When this pass is run over a function it uses expect intrinsics which feed 378 /// branches and switches to provide branch weight metadata for those 379 /// terminators. It then removes the expect intrinsics from the IR so the rest 380 /// of the optimizer can ignore them. 381 class LowerExpectIntrinsic : public FunctionPass { 382 public: 383 static char ID; 384 LowerExpectIntrinsic() : FunctionPass(ID) { 385 initializeLowerExpectIntrinsicPass(*PassRegistry::getPassRegistry()); 386 } 387 388 bool runOnFunction(Function &F) override { return lowerExpectIntrinsic(F); } 389 }; 390 } 391 392 char LowerExpectIntrinsic::ID = 0; 393 INITIALIZE_PASS(LowerExpectIntrinsic, "lower-expect", 394 "Lower 'expect' Intrinsics", false, false) 395 396 FunctionPass *llvm::createLowerExpectIntrinsicPass() { 397 return new LowerExpectIntrinsic(); 398 } 399