1 //===- DivRemPairs.cpp - Hoist/decompose division and remainder -*- C++ -*-===// 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 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/IR/Dominators.h" 21 #include "llvm/IR/Function.h" 22 #include "llvm/Pass.h" 23 #include "llvm/Support/DebugCounter.h" 24 #include "llvm/Transforms/Scalar.h" 25 #include "llvm/Transforms/Utils/BypassSlowDivision.h" 26 using namespace llvm; 27 28 #define DEBUG_TYPE "div-rem-pairs" 29 STATISTIC(NumPairs, "Number of div/rem pairs"); 30 STATISTIC(NumHoisted, "Number of instructions hoisted"); 31 STATISTIC(NumDecomposed, "Number of instructions decomposed"); 32 DEBUG_COUNTER(DRPCounter, "div-rem-pairs-transform", 33 "Controls transformations in div-rem-pairs pass"); 34 35 /// Find matching pairs of integer div/rem ops (they have the same numerator, 36 /// denominator, and signedness). If they exist in different basic blocks, bring 37 /// them together by hoisting or replace the common division operation that is 38 /// implicit in the remainder: 39 /// X % Y <--> X - ((X / Y) * Y). 40 /// 41 /// We can largely ignore the normal safety and cost constraints on speculation 42 /// of these ops when we find a matching pair. This is because we are already 43 /// guaranteed that any exceptions and most cost are already incurred by the 44 /// first member of the pair. 45 /// 46 /// Note: This transform could be an oddball enhancement to EarlyCSE, GVN, or 47 /// SimplifyCFG, but it's split off on its own because it's different enough 48 /// that it doesn't quite match the stated objectives of those passes. 49 static bool optimizeDivRem(Function &F, const TargetTransformInfo &TTI, 50 const DominatorTree &DT) { 51 bool Changed = false; 52 53 // Insert all divide and remainder instructions into maps keyed by their 54 // operands and opcode (signed or unsigned). 55 DenseMap<DivRemMapKey, Instruction *> DivMap; 56 // Use a MapVector for RemMap so that instructions are moved/inserted in a 57 // deterministic order. 58 MapVector<DivRemMapKey, Instruction *> RemMap; 59 for (auto &BB : F) { 60 for (auto &I : BB) { 61 if (I.getOpcode() == Instruction::SDiv) 62 DivMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I; 63 else if (I.getOpcode() == Instruction::UDiv) 64 DivMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I; 65 else if (I.getOpcode() == Instruction::SRem) 66 RemMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I; 67 else if (I.getOpcode() == Instruction::URem) 68 RemMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I; 69 } 70 } 71 72 // We can iterate over either map because we are only looking for matched 73 // pairs. Choose remainders for efficiency because they are usually even more 74 // rare than division. 75 for (auto &RemPair : RemMap) { 76 // Find the matching division instruction from the division map. 77 Instruction *DivInst = DivMap[RemPair.first]; 78 if (!DivInst) 79 continue; 80 81 // We have a matching pair of div/rem instructions. If one dominates the 82 // other, hoist and/or replace one. 83 NumPairs++; 84 Instruction *RemInst = RemPair.second; 85 bool IsSigned = DivInst->getOpcode() == Instruction::SDiv; 86 bool HasDivRemOp = TTI.hasDivRemOp(DivInst->getType(), IsSigned); 87 88 // If the target supports div+rem and the instructions are in the same block 89 // already, there's nothing to do. The backend should handle this. If the 90 // target does not support div+rem, then we will decompose the rem. 91 if (HasDivRemOp && RemInst->getParent() == DivInst->getParent()) 92 continue; 93 94 bool DivDominates = DT.dominates(DivInst, RemInst); 95 if (!DivDominates && !DT.dominates(RemInst, DivInst)) 96 continue; 97 98 if (!DebugCounter::shouldExecute(DRPCounter)) 99 continue; 100 101 if (HasDivRemOp) { 102 // The target has a single div/rem operation. Hoist the lower instruction 103 // to make the matched pair visible to the backend. 104 if (DivDominates) 105 RemInst->moveAfter(DivInst); 106 else 107 DivInst->moveAfter(RemInst); 108 NumHoisted++; 109 } else { 110 // The target does not have a single div/rem operation. Decompose the 111 // remainder calculation as: 112 // X % Y --> X - ((X / Y) * Y). 113 Value *X = RemInst->getOperand(0); 114 Value *Y = RemInst->getOperand(1); 115 Instruction *Mul = BinaryOperator::CreateMul(DivInst, Y); 116 Instruction *Sub = BinaryOperator::CreateSub(X, Mul); 117 118 // If the remainder dominates, then hoist the division up to that block: 119 // 120 // bb1: 121 // %rem = srem %x, %y 122 // bb2: 123 // %div = sdiv %x, %y 124 // --> 125 // bb1: 126 // %div = sdiv %x, %y 127 // %mul = mul %div, %y 128 // %rem = sub %x, %mul 129 // 130 // If the division dominates, it's already in the right place. The mul+sub 131 // will be in a different block because we don't assume that they are 132 // cheap to speculatively execute: 133 // 134 // bb1: 135 // %div = sdiv %x, %y 136 // bb2: 137 // %rem = srem %x, %y 138 // --> 139 // bb1: 140 // %div = sdiv %x, %y 141 // bb2: 142 // %mul = mul %div, %y 143 // %rem = sub %x, %mul 144 // 145 // If the div and rem are in the same block, we do the same transform, 146 // but any code movement would be within the same block. 147 148 if (!DivDominates) 149 DivInst->moveBefore(RemInst); 150 Mul->insertAfter(RemInst); 151 Sub->insertAfter(Mul); 152 153 // Now kill the explicit remainder. We have replaced it with: 154 // (sub X, (mul (div X, Y), Y) 155 RemInst->replaceAllUsesWith(Sub); 156 RemInst->eraseFromParent(); 157 NumDecomposed++; 158 } 159 Changed = true; 160 } 161 162 return Changed; 163 } 164 165 // Pass manager boilerplate below here. 166 167 namespace { 168 struct DivRemPairsLegacyPass : public FunctionPass { 169 static char ID; 170 DivRemPairsLegacyPass() : FunctionPass(ID) { 171 initializeDivRemPairsLegacyPassPass(*PassRegistry::getPassRegistry()); 172 } 173 174 void getAnalysisUsage(AnalysisUsage &AU) const override { 175 AU.addRequired<DominatorTreeWrapperPass>(); 176 AU.addRequired<TargetTransformInfoWrapperPass>(); 177 AU.setPreservesCFG(); 178 AU.addPreserved<DominatorTreeWrapperPass>(); 179 AU.addPreserved<GlobalsAAWrapperPass>(); 180 FunctionPass::getAnalysisUsage(AU); 181 } 182 183 bool runOnFunction(Function &F) override { 184 if (skipFunction(F)) 185 return false; 186 auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 187 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 188 return optimizeDivRem(F, TTI, DT); 189 } 190 }; 191 } 192 193 char DivRemPairsLegacyPass::ID = 0; 194 INITIALIZE_PASS_BEGIN(DivRemPairsLegacyPass, "div-rem-pairs", 195 "Hoist/decompose integer division and remainder", false, 196 false) 197 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 198 INITIALIZE_PASS_END(DivRemPairsLegacyPass, "div-rem-pairs", 199 "Hoist/decompose integer division and remainder", false, 200 false) 201 FunctionPass *llvm::createDivRemPairsPass() { 202 return new DivRemPairsLegacyPass(); 203 } 204 205 PreservedAnalyses DivRemPairsPass::run(Function &F, 206 FunctionAnalysisManager &FAM) { 207 TargetTransformInfo &TTI = FAM.getResult<TargetIRAnalysis>(F); 208 DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F); 209 if (!optimizeDivRem(F, TTI, DT)) 210 return PreservedAnalyses::all(); 211 // TODO: This pass just hoists/replaces math ops - all analyses are preserved? 212 PreservedAnalyses PA; 213 PA.preserveSet<CFGAnalyses>(); 214 PA.preserve<GlobalsAA>(); 215 return PA; 216 } 217