contrib/llvm/lib/Transforms/Scalar/DivRemPairs.cpp

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