1 //===- DivRemPairs.cpp - Hoist/[dr]ecompose division and remainder --------===// 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 hoists and/or decomposes/recomposes integer division and remainder 10 // instructions to enable CFG improvements and better codegen. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Transforms/Scalar/DivRemPairs.h" 15 #include "llvm/ADT/DenseMap.h" 16 #include "llvm/ADT/MapVector.h" 17 #include "llvm/ADT/Statistic.h" 18 #include "llvm/Analysis/GlobalsModRef.h" 19 #include "llvm/Analysis/TargetTransformInfo.h" 20 #include "llvm/Analysis/ValueTracking.h" 21 #include "llvm/IR/Dominators.h" 22 #include "llvm/IR/Function.h" 23 #include "llvm/IR/PatternMatch.h" 24 #include "llvm/InitializePasses.h" 25 #include "llvm/Pass.h" 26 #include "llvm/Support/DebugCounter.h" 27 #include "llvm/Transforms/Scalar.h" 28 #include "llvm/Transforms/Utils/BypassSlowDivision.h" 29 30 using namespace llvm; 31 using namespace llvm::PatternMatch; 32 33 #define DEBUG_TYPE "div-rem-pairs" 34 STATISTIC(NumPairs, "Number of div/rem pairs"); 35 STATISTIC(NumRecomposed, "Number of instructions recomposed"); 36 STATISTIC(NumHoisted, "Number of instructions hoisted"); 37 STATISTIC(NumDecomposed, "Number of instructions decomposed"); 38 DEBUG_COUNTER(DRPCounter, "div-rem-pairs-transform", 39 "Controls transformations in div-rem-pairs pass"); 40 41 namespace { 42 struct ExpandedMatch { 43 DivRemMapKey Key; 44 Instruction *Value; 45 }; 46 } // namespace 47 48 /// See if we can match: (which is the form we expand into) 49 /// X - ((X ?/ Y) * Y) 50 /// which is equivalent to: 51 /// X ?% Y 52 static llvm::Optional<ExpandedMatch> matchExpandedRem(Instruction &I) { 53 Value *Dividend, *XroundedDownToMultipleOfY; 54 if (!match(&I, m_Sub(m_Value(Dividend), m_Value(XroundedDownToMultipleOfY)))) 55 return llvm::None; 56 57 Value *Divisor; 58 Instruction *Div; 59 // Look for ((X / Y) * Y) 60 if (!match( 61 XroundedDownToMultipleOfY, 62 m_c_Mul(m_CombineAnd(m_IDiv(m_Specific(Dividend), m_Value(Divisor)), 63 m_Instruction(Div)), 64 m_Deferred(Divisor)))) 65 return llvm::None; 66 67 ExpandedMatch M; 68 M.Key.SignedOp = Div->getOpcode() == Instruction::SDiv; 69 M.Key.Dividend = Dividend; 70 M.Key.Divisor = Divisor; 71 M.Value = &I; 72 return M; 73 } 74 75 namespace { 76 /// A thin wrapper to store two values that we matched as div-rem pair. 77 /// We want this extra indirection to avoid dealing with RAUW'ing the map keys. 78 struct DivRemPairWorklistEntry { 79 /// The actual udiv/sdiv instruction. Source of truth. 80 AssertingVH<Instruction> DivInst; 81 82 /// The instruction that we have matched as a remainder instruction. 83 /// Should only be used as Value, don't introspect it. 84 AssertingVH<Instruction> RemInst; 85 86 DivRemPairWorklistEntry(Instruction *DivInst_, Instruction *RemInst_) 87 : DivInst(DivInst_), RemInst(RemInst_) { 88 assert((DivInst->getOpcode() == Instruction::UDiv || 89 DivInst->getOpcode() == Instruction::SDiv) && 90 "Not a division."); 91 assert(DivInst->getType() == RemInst->getType() && "Types should match."); 92 // We can't check anything else about remainder instruction, 93 // it's not strictly required to be a urem/srem. 94 } 95 96 /// The type for this pair, identical for both the div and rem. 97 Type *getType() const { return DivInst->getType(); } 98 99 /// Is this pair signed or unsigned? 100 bool isSigned() const { return DivInst->getOpcode() == Instruction::SDiv; } 101 102 /// In this pair, what are the divident and divisor? 103 Value *getDividend() const { return DivInst->getOperand(0); } 104 Value *getDivisor() const { return DivInst->getOperand(1); } 105 106 bool isRemExpanded() const { 107 switch (RemInst->getOpcode()) { 108 case Instruction::SRem: 109 case Instruction::URem: 110 return false; // single 'rem' instruction - unexpanded form. 111 default: 112 return true; // anything else means we have remainder in expanded form. 113 } 114 } 115 }; 116 } // namespace 117 using DivRemWorklistTy = SmallVector<DivRemPairWorklistEntry, 4>; 118 119 /// Find matching pairs of integer div/rem ops (they have the same numerator, 120 /// denominator, and signedness). Place those pairs into a worklist for further 121 /// processing. This indirection is needed because we have to use TrackingVH<> 122 /// because we will be doing RAUW, and if one of the rem instructions we change 123 /// happens to be an input to another div/rem in the maps, we'd have problems. 124 static DivRemWorklistTy getWorklist(Function &F) { 125 // Insert all divide and remainder instructions into maps keyed by their 126 // operands and opcode (signed or unsigned). 127 DenseMap<DivRemMapKey, Instruction *> DivMap; 128 // Use a MapVector for RemMap so that instructions are moved/inserted in a 129 // deterministic order. 130 MapVector<DivRemMapKey, Instruction *> RemMap; 131 for (auto &BB : F) { 132 for (auto &I : BB) { 133 if (I.getOpcode() == Instruction::SDiv) 134 DivMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I; 135 else if (I.getOpcode() == Instruction::UDiv) 136 DivMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I; 137 else if (I.getOpcode() == Instruction::SRem) 138 RemMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I; 139 else if (I.getOpcode() == Instruction::URem) 140 RemMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I; 141 else if (auto Match = matchExpandedRem(I)) 142 RemMap[Match->Key] = Match->Value; 143 } 144 } 145 146 // We'll accumulate the matching pairs of div-rem instructions here. 147 DivRemWorklistTy Worklist; 148 149 // We can iterate over either map because we are only looking for matched 150 // pairs. Choose remainders for efficiency because they are usually even more 151 // rare than division. 152 for (auto &RemPair : RemMap) { 153 // Find the matching division instruction from the division map. 154 auto It = DivMap.find(RemPair.first); 155 if (It == DivMap.end()) 156 continue; 157 158 // We have a matching pair of div/rem instructions. 159 NumPairs++; 160 Instruction *RemInst = RemPair.second; 161 162 // Place it in the worklist. 163 Worklist.emplace_back(It->second, RemInst); 164 } 165 166 return Worklist; 167 } 168 169 /// Find matching pairs of integer div/rem ops (they have the same numerator, 170 /// denominator, and signedness). If they exist in different basic blocks, bring 171 /// them together by hoisting or replace the common division operation that is 172 /// implicit in the remainder: 173 /// X % Y <--> X - ((X / Y) * Y). 174 /// 175 /// We can largely ignore the normal safety and cost constraints on speculation 176 /// of these ops when we find a matching pair. This is because we are already 177 /// guaranteed that any exceptions and most cost are already incurred by the 178 /// first member of the pair. 179 /// 180 /// Note: This transform could be an oddball enhancement to EarlyCSE, GVN, or 181 /// SimplifyCFG, but it's split off on its own because it's different enough 182 /// that it doesn't quite match the stated objectives of those passes. 183 static bool optimizeDivRem(Function &F, const TargetTransformInfo &TTI, 184 const DominatorTree &DT) { 185 bool Changed = false; 186 187 // Get the matching pairs of div-rem instructions. We want this extra 188 // indirection to avoid dealing with having to RAUW the keys of the maps. 189 DivRemWorklistTy Worklist = getWorklist(F); 190 191 // Process each entry in the worklist. 192 for (DivRemPairWorklistEntry &E : Worklist) { 193 if (!DebugCounter::shouldExecute(DRPCounter)) 194 continue; 195 196 bool HasDivRemOp = TTI.hasDivRemOp(E.getType(), E.isSigned()); 197 198 auto &DivInst = E.DivInst; 199 auto &RemInst = E.RemInst; 200 201 const bool RemOriginallyWasInExpandedForm = E.isRemExpanded(); 202 (void)RemOriginallyWasInExpandedForm; // suppress unused variable warning 203 204 if (HasDivRemOp && E.isRemExpanded()) { 205 // The target supports div+rem but the rem is expanded. 206 // We should recompose it first. 207 Value *X = E.getDividend(); 208 Value *Y = E.getDivisor(); 209 Instruction *RealRem = E.isSigned() ? BinaryOperator::CreateSRem(X, Y) 210 : BinaryOperator::CreateURem(X, Y); 211 // Note that we place it right next to the original expanded instruction, 212 // and letting further handling to move it if needed. 213 RealRem->setName(RemInst->getName() + ".recomposed"); 214 RealRem->insertAfter(RemInst); 215 Instruction *OrigRemInst = RemInst; 216 // Update AssertingVH<> with new instruction so it doesn't assert. 217 RemInst = RealRem; 218 // And replace the original instruction with the new one. 219 OrigRemInst->replaceAllUsesWith(RealRem); 220 OrigRemInst->eraseFromParent(); 221 NumRecomposed++; 222 // Note that we have left ((X / Y) * Y) around. 223 // If it had other uses we could rewrite it as X - X % Y 224 Changed = true; 225 } 226 227 assert((!E.isRemExpanded() || !HasDivRemOp) && 228 "*If* the target supports div-rem, then by now the RemInst *is* " 229 "Instruction::[US]Rem."); 230 231 // If the target supports div+rem and the instructions are in the same block 232 // already, there's nothing to do. The backend should handle this. If the 233 // target does not support div+rem, then we will decompose the rem. 234 if (HasDivRemOp && RemInst->getParent() == DivInst->getParent()) 235 continue; 236 237 bool DivDominates = DT.dominates(DivInst, RemInst); 238 if (!DivDominates && !DT.dominates(RemInst, DivInst)) { 239 // We have matching div-rem pair, but they are in two different blocks, 240 // neither of which dominates one another. 241 242 BasicBlock *PredBB = nullptr; 243 BasicBlock *DivBB = DivInst->getParent(); 244 BasicBlock *RemBB = RemInst->getParent(); 245 246 // It's only safe to hoist if every instruction before the Div/Rem in the 247 // basic block is guaranteed to transfer execution. 248 auto IsSafeToHoist = [](Instruction *DivOrRem, BasicBlock *ParentBB) { 249 for (auto I = ParentBB->begin(), E = DivOrRem->getIterator(); I != E; 250 ++I) 251 if (!isGuaranteedToTransferExecutionToSuccessor(&*I)) 252 return false; 253 254 return true; 255 }; 256 257 // Look for something like this 258 // PredBB 259 // | \ 260 // | Rem 261 // | / 262 // Div 263 // 264 // If the Rem block has a single predecessor and successor, and all paths 265 // from PredBB go to either RemBB or DivBB, and execution of RemBB and 266 // DivBB will always reach the Div/Rem, we can hoist Div to PredBB. If 267 // we have a DivRem operation we can also hoist Rem. Otherwise we'll leave 268 // Rem where it is and rewrite it to mul/sub. 269 // FIXME: We could handle more hoisting cases. 270 if (RemBB->getSingleSuccessor() == DivBB) 271 PredBB = RemBB->getUniquePredecessor(); 272 273 if (PredBB && IsSafeToHoist(RemInst, RemBB) && 274 IsSafeToHoist(DivInst, DivBB) && 275 llvm::all_of(successors(PredBB), [&](BasicBlock *BB) { 276 return BB == DivBB || BB == RemBB; 277 })) { 278 DivDominates = true; 279 DivInst->moveBefore(PredBB->getTerminator()); 280 Changed = true; 281 if (HasDivRemOp) { 282 RemInst->moveBefore(PredBB->getTerminator()); 283 continue; 284 } 285 } else 286 continue; 287 } 288 289 // The target does not have a single div/rem operation, 290 // and the rem is already in expanded form. Nothing to do. 291 if (!HasDivRemOp && E.isRemExpanded()) 292 continue; 293 294 if (HasDivRemOp) { 295 // The target has a single div/rem operation. Hoist the lower instruction 296 // to make the matched pair visible to the backend. 297 if (DivDominates) 298 RemInst->moveAfter(DivInst); 299 else 300 DivInst->moveAfter(RemInst); 301 NumHoisted++; 302 } else { 303 // The target does not have a single div/rem operation, 304 // and the rem is *not* in a already-expanded form. 305 // Decompose the remainder calculation as: 306 // X % Y --> X - ((X / Y) * Y). 307 308 assert(!RemOriginallyWasInExpandedForm && 309 "We should not be expanding if the rem was in expanded form to " 310 "begin with."); 311 312 Value *X = E.getDividend(); 313 Value *Y = E.getDivisor(); 314 Instruction *Mul = BinaryOperator::CreateMul(DivInst, Y); 315 Instruction *Sub = BinaryOperator::CreateSub(X, Mul); 316 317 // If the remainder dominates, then hoist the division up to that block: 318 // 319 // bb1: 320 // %rem = srem %x, %y 321 // bb2: 322 // %div = sdiv %x, %y 323 // --> 324 // bb1: 325 // %div = sdiv %x, %y 326 // %mul = mul %div, %y 327 // %rem = sub %x, %mul 328 // 329 // If the division dominates, it's already in the right place. The mul+sub 330 // will be in a different block because we don't assume that they are 331 // cheap to speculatively execute: 332 // 333 // bb1: 334 // %div = sdiv %x, %y 335 // bb2: 336 // %rem = srem %x, %y 337 // --> 338 // bb1: 339 // %div = sdiv %x, %y 340 // bb2: 341 // %mul = mul %div, %y 342 // %rem = sub %x, %mul 343 // 344 // If the div and rem are in the same block, we do the same transform, 345 // but any code movement would be within the same block. 346 347 if (!DivDominates) 348 DivInst->moveBefore(RemInst); 349 Mul->insertAfter(RemInst); 350 Sub->insertAfter(Mul); 351 352 // If X can be undef, X should be frozen first. 353 // For example, let's assume that Y = 1 & X = undef: 354 // %div = sdiv undef, 1 // %div = undef 355 // %rem = srem undef, 1 // %rem = 0 356 // => 357 // %div = sdiv undef, 1 // %div = undef 358 // %mul = mul %div, 1 // %mul = undef 359 // %rem = sub %x, %mul // %rem = undef - undef = undef 360 // If X is not frozen, %rem becomes undef after transformation. 361 // TODO: We need a undef-specific checking function in ValueTracking 362 if (!isGuaranteedNotToBeUndefOrPoison(X, nullptr, DivInst, &DT)) { 363 auto *FrX = new FreezeInst(X, X->getName() + ".frozen", DivInst); 364 DivInst->setOperand(0, FrX); 365 Sub->setOperand(0, FrX); 366 } 367 // Same for Y. If X = 1 and Y = (undef | 1), %rem in src is either 1 or 0, 368 // but %rem in tgt can be one of many integer values. 369 if (!isGuaranteedNotToBeUndefOrPoison(Y, nullptr, DivInst, &DT)) { 370 auto *FrY = new FreezeInst(Y, Y->getName() + ".frozen", DivInst); 371 DivInst->setOperand(1, FrY); 372 Mul->setOperand(1, FrY); 373 } 374 375 // Now kill the explicit remainder. We have replaced it with: 376 // (sub X, (mul (div X, Y), Y) 377 Sub->setName(RemInst->getName() + ".decomposed"); 378 Instruction *OrigRemInst = RemInst; 379 // Update AssertingVH<> with new instruction so it doesn't assert. 380 RemInst = Sub; 381 // And replace the original instruction with the new one. 382 OrigRemInst->replaceAllUsesWith(Sub); 383 OrigRemInst->eraseFromParent(); 384 NumDecomposed++; 385 } 386 Changed = true; 387 } 388 389 return Changed; 390 } 391 392 // Pass manager boilerplate below here. 393 394 namespace { 395 struct DivRemPairsLegacyPass : public FunctionPass { 396 static char ID; 397 DivRemPairsLegacyPass() : FunctionPass(ID) { 398 initializeDivRemPairsLegacyPassPass(*PassRegistry::getPassRegistry()); 399 } 400 401 void getAnalysisUsage(AnalysisUsage &AU) const override { 402 AU.addRequired<DominatorTreeWrapperPass>(); 403 AU.addRequired<TargetTransformInfoWrapperPass>(); 404 AU.setPreservesCFG(); 405 AU.addPreserved<DominatorTreeWrapperPass>(); 406 AU.addPreserved<GlobalsAAWrapperPass>(); 407 FunctionPass::getAnalysisUsage(AU); 408 } 409 410 bool runOnFunction(Function &F) override { 411 if (skipFunction(F)) 412 return false; 413 auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 414 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 415 return optimizeDivRem(F, TTI, DT); 416 } 417 }; 418 } // namespace 419 420 char DivRemPairsLegacyPass::ID = 0; 421 INITIALIZE_PASS_BEGIN(DivRemPairsLegacyPass, "div-rem-pairs", 422 "Hoist/decompose integer division and remainder", false, 423 false) 424 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 425 INITIALIZE_PASS_END(DivRemPairsLegacyPass, "div-rem-pairs", 426 "Hoist/decompose integer division and remainder", false, 427 false) 428 FunctionPass *llvm::createDivRemPairsPass() { 429 return new DivRemPairsLegacyPass(); 430 } 431 432 PreservedAnalyses DivRemPairsPass::run(Function &F, 433 FunctionAnalysisManager &FAM) { 434 TargetTransformInfo &TTI = FAM.getResult<TargetIRAnalysis>(F); 435 DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F); 436 if (!optimizeDivRem(F, TTI, DT)) 437 return PreservedAnalyses::all(); 438 // TODO: This pass just hoists/replaces math ops - all analyses are preserved? 439 PreservedAnalyses PA; 440 PA.preserveSet<CFGAnalyses>(); 441 return PA; 442 } 443