lib/Transforms/Scalar/DivRemPairs.cpp

   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 }