lib/Transforms/Utils/BypassSlowDivision.cpp

   1 //===-- BypassSlowDivision.cpp - Bypass slow division ---------------------===//
   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 file contains an optimization for div and rem on architectures that
  11 // execute short instructions significantly faster than longer instructions.
  12 // For example, on Intel Atom 32-bit divides are slow enough that during
  13 // runtime it is profitable to check the value of the operands, and if they are
  14 // positive and less than 256 use an unsigned 8-bit divide.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #define DEBUG_TYPE "bypass-slow-division"
  19 #include "llvm/Instructions.h"
  20 #include "llvm/Function.h"
  21 #include "llvm/IRBuilder.h"
  22 #include "llvm/ADT/DenseMap.h"
  23 #include "llvm/Transforms/Utils/BypassSlowDivision.h"
  24
  25 using namespace llvm;
  26
  27 namespace llvm {
  28   struct DivOpInfo {
  29     bool SignedOp;
  30     Value *Dividend;
  31     Value *Divisor;
  32
  33     DivOpInfo(bool InSignedOp, Value *InDividend, Value *InDivisor)
  34       : SignedOp(InSignedOp), Dividend(InDividend), Divisor(InDivisor) {}
  35   };
  36
  37   struct DivPhiNodes {
  38     PHINode *Quotient;
  39     PHINode *Remainder;
  40
  41     DivPhiNodes(PHINode *InQuotient, PHINode *InRemainder)
  42       : Quotient(InQuotient), Remainder(InRemainder) {}
  43   };
  44
  45   template<>
  46   struct DenseMapInfo<DivOpInfo> {
  47     static bool isEqual(const DivOpInfo &Val1, const DivOpInfo &Val2) {
  48       return Val1.SignedOp == Val2.SignedOp &&
  49              Val1.Dividend == Val2.Dividend &&
  50              Val1.Divisor == Val2.Divisor;
  51     }
  52
  53     static DivOpInfo getEmptyKey() {
  54       return DivOpInfo(false, 0, 0);
  55     }
  56
  57     static DivOpInfo getTombstoneKey() {
  58       return DivOpInfo(true, 0, 0);
  59     }
  60
  61     static unsigned getHashValue(const DivOpInfo &Val) {
  62       return (unsigned)(reinterpret_cast<uintptr_t>(Val.Dividend) ^
  63                         reinterpret_cast<uintptr_t>(Val.Divisor)) ^
  64                        (unsigned)Val.SignedOp;
  65     }
  66   };
  67
  68   typedef DenseMap<DivOpInfo, DivPhiNodes> DivCacheTy;
  69 }
  70
  71 // insertFastDiv - Substitutes the div/rem instruction with code that checks the
  72 // value of the operands and uses a shorter-faster div/rem instruction when
  73 // possible and the longer-slower div/rem instruction otherwise.
  74 static void insertFastDiv(Function &F,
  75                           Function::iterator &I,
  76                           BasicBlock::iterator &J,
  77                           IntegerType *BypassType,
  78                           bool UseDivOp,
  79                           bool UseSignedOp,
  80                           DivCacheTy &PerBBDivCache)
  81 {
  82   // Get instruction operands
  83   Instruction *Instr = J;
  84   Value *Dividend = Instr->getOperand(0);
  85   Value *Divisor = Instr->getOperand(1);
  86
  87   if (dyn_cast<ConstantInt>(Divisor) != 0 ||
  88       (dyn_cast<ConstantInt>(Dividend) != 0 &&
  89        dyn_cast<ConstantInt>(Divisor) != 0)) {
  90     // Operations with immediate values should have
  91     // been solved and replaced during compile time.
  92     return;
  93   }
  94
  95   // Basic Block is split before divide
  96   BasicBlock *MainBB = I;
  97   BasicBlock *SuccessorBB = I->splitBasicBlock(J);
  98   I++; //advance iterator I to successorBB
  99
 100   // Add new basic block for slow divide operation
 101   BasicBlock *SlowBB = BasicBlock::Create(F.getContext(), "",
 102                                           MainBB->getParent(), SuccessorBB);
 103   SlowBB->moveBefore(SuccessorBB);
 104   IRBuilder<> SlowBuilder(SlowBB, SlowBB->begin());
 105   Value *SlowQuotientV;
 106   Value *SlowRemainderV;
 107   if (UseSignedOp) {
 108     SlowQuotientV = SlowBuilder.CreateSDiv(Dividend, Divisor);
 109     SlowRemainderV = SlowBuilder.CreateSRem(Dividend, Divisor);
 110   } else {
 111     SlowQuotientV = SlowBuilder.CreateUDiv(Dividend, Divisor);
 112     SlowRemainderV = SlowBuilder.CreateURem(Dividend, Divisor);
 113   }
 114   SlowBuilder.CreateBr(SuccessorBB);
 115
 116   // Add new basic block for fast divide operation
 117   BasicBlock *FastBB = BasicBlock::Create(F.getContext(), "",
 118                                           MainBB->getParent(), SuccessorBB);
 119   FastBB->moveBefore(SlowBB);
 120   IRBuilder<> FastBuilder(FastBB, FastBB->begin());
 121   Value *ShortDivisorV = FastBuilder.CreateCast(Instruction::Trunc, Divisor, BypassType);
 122   Value *ShortDividendV = FastBuilder.CreateCast(Instruction::Trunc, Dividend, BypassType);
 123
 124   // udiv/urem because optimization only handles positive numbers
 125   Value *ShortQuotientV = FastBuilder.CreateExactUDiv(ShortDividendV,
 126                                                        ShortDivisorV);
 127   Value *ShortRemainderV = FastBuilder.CreateURem(ShortDividendV,
 128                                                   ShortDivisorV);
 129   Value *FastQuotientV = FastBuilder.CreateCast(Instruction::ZExt,
 130                                                  ShortQuotientV,
 131                                                  Dividend->getType());
 132   Value *FastRemainderV = FastBuilder.CreateCast(Instruction::ZExt,
 133                                                  ShortRemainderV,
 134                                                  Dividend->getType());
 135   FastBuilder.CreateBr(SuccessorBB);
 136
 137   // Phi nodes for result of div and rem
 138   IRBuilder<> SuccessorBuilder(SuccessorBB, SuccessorBB->begin());
 139   PHINode *QuoPhi = SuccessorBuilder.CreatePHI(Instr->getType(), 2);
 140   QuoPhi->addIncoming(SlowQuotientV, SlowBB);
 141   QuoPhi->addIncoming(FastQuotientV, FastBB);
 142   PHINode *RemPhi = SuccessorBuilder.CreatePHI(Instr->getType(), 2);
 143   RemPhi->addIncoming(SlowRemainderV, SlowBB);
 144   RemPhi->addIncoming(FastRemainderV, FastBB);
 145
 146   // Replace Instr with appropriate phi node
 147   if (UseDivOp) {
 148     Instr->replaceAllUsesWith(QuoPhi);
 149   } else {
 150     Instr->replaceAllUsesWith(RemPhi);
 151   }
 152   Instr->eraseFromParent();
 153
 154   // Combine operands into a single value with OR for value testing below
 155   MainBB->getInstList().back().eraseFromParent();
 156   IRBuilder<> MainBuilder(MainBB, MainBB->end());
 157   Value *OrV = MainBuilder.CreateOr(Dividend, Divisor);
 158
 159   // BitMask is inverted to check if the operands are
 160   // larger than the bypass type
 161   uint64_t BitMask = ~BypassType->getBitMask();
 162   Value *AndV = MainBuilder.CreateAnd(OrV, BitMask);
 163
 164   // Compare operand values and branch
 165   Value *ZeroV = MainBuilder.getInt32(0);
 166   Value *CmpV = MainBuilder.CreateICmpEQ(AndV, ZeroV);
 167   MainBuilder.CreateCondBr(CmpV, FastBB, SlowBB);
 168
 169   // point iterator J at first instruction of successorBB
 170   J = I->begin();
 171
 172   // Cache phi nodes to be used later in place of other instances
 173   // of div or rem with the same sign, dividend, and divisor
 174   DivOpInfo Key(UseSignedOp, Dividend, Divisor);
 175   DivPhiNodes Value(QuoPhi, RemPhi);
 176   PerBBDivCache.insert(std::pair<DivOpInfo, DivPhiNodes>(Key, Value));
 177 }
 178
 179 // reuseOrInsertFastDiv - Reuses previously computed dividend or remainder if
 180 // operands and operation are identical. Otherwise call insertFastDiv to perform
 181 // the optimization and cache the resulting dividend and remainder.
 182 static void reuseOrInsertFastDiv(Function &F,
 183                                  Function::iterator &I,
 184                                  BasicBlock::iterator &J,
 185                                  IntegerType *BypassType,
 186                                  bool UseDivOp,
 187                                  bool UseSignedOp,
 188                                  DivCacheTy &PerBBDivCache)
 189 {
 190   // Get instruction operands
 191   Instruction *Instr = J;
 192   DivOpInfo Key(UseSignedOp, Instr->getOperand(0), Instr->getOperand(1));
 193   DivCacheTy::const_iterator CacheI = PerBBDivCache.find(Key);
 194
 195   if (CacheI == PerBBDivCache.end()) {
 196     // If previous instance does not exist, insert fast div
 197     insertFastDiv(F, I, J, BypassType, UseDivOp, UseSignedOp, PerBBDivCache);
 198     return;
 199   }
 200
 201   // Replace operation value with previously generated phi node
 202   DivPhiNodes Value = CacheI->second;
 203   if (UseDivOp) {
 204     // Replace all uses of div instruction with quotient phi node
 205     J->replaceAllUsesWith(Value.Quotient);
 206   } else {
 207     // Replace all uses of rem instruction with remainder phi node
 208     J->replaceAllUsesWith(Value.Remainder);
 209   }
 210
 211   // Advance to next operation
 212   J++;
 213
 214   // Remove redundant operation
 215   Instr->eraseFromParent();
 216 }
 217
 218 // bypassSlowDivision - This optimization identifies DIV instructions that can
 219 // be profitably bypassed and carried out with a shorter, faster divide.
 220 bool bypassSlowDivision(Function &F,
 221                         Function::iterator &I,
 222                         const llvm::DenseMap<Type *, Type *> &BypassTypeMap)
 223 {
 224   DivCacheTy DivCache;
 225
 226   bool MadeChange = false;
 227   for (BasicBlock::iterator J = I->begin(); J != I->end(); J++) {
 228
 229     // Get instruction details
 230     unsigned Opcode = J->getOpcode();
 231     bool UseDivOp = Opcode == Instruction::SDiv || Opcode == Instruction::UDiv;
 232     bool UseRemOp = Opcode == Instruction::SRem || Opcode == Instruction::URem;
 233     bool UseSignedOp = Opcode == Instruction::SDiv || Opcode == Instruction::SRem;
 234
 235     // Only optimize div or rem ops
 236     if (!UseDivOp && !UseRemOp) {
 237       continue;
 238     }
 239     // Continue if div/rem type is not bypassed
 240     DenseMap<Type *, Type *>::const_iterator BT = BypassTypeMap.find(J->getType());
 241     if (BT == BypassTypeMap.end()) {
 242       continue;
 243     }
 244
 245     IntegerType *BypassType = (IntegerType *)BT->second;
 246     reuseOrInsertFastDiv(F, I, J, BypassType, UseDivOp, UseSignedOp, DivCache);
 247     MadeChange = true;
 248   }
 249
 250   return MadeChange;
 251 }