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