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