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