BypassSlowDivision.cpp [plain text]
#define DEBUG_TYPE "bypass-slow-division"
#include "llvm/Instructions.h"
#include "llvm/Function.h"
#include "llvm/IRBuilder.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/Transforms/Utils/BypassSlowDivision.h"
using namespace llvm;
namespace {
struct DivOpInfo {
bool SignedOp;
Value *Dividend;
Value *Divisor;
DivOpInfo(bool InSignedOp, Value *InDividend, Value *InDivisor)
: SignedOp(InSignedOp), Dividend(InDividend), Divisor(InDivisor) {}
};
struct DivPhiNodes {
PHINode *Quotient;
PHINode *Remainder;
DivPhiNodes(PHINode *InQuotient, PHINode *InRemainder)
: Quotient(InQuotient), Remainder(InRemainder) {}
};
}
namespace llvm {
template<>
struct DenseMapInfo<DivOpInfo> {
static bool isEqual(const DivOpInfo &Val1, const DivOpInfo &Val2) {
return Val1.SignedOp == Val2.SignedOp &&
Val1.Dividend == Val2.Dividend &&
Val1.Divisor == Val2.Divisor;
}
static DivOpInfo getEmptyKey() {
return DivOpInfo(false, 0, 0);
}
static DivOpInfo getTombstoneKey() {
return DivOpInfo(true, 0, 0);
}
static unsigned getHashValue(const DivOpInfo &Val) {
return (unsigned)(reinterpret_cast<uintptr_t>(Val.Dividend) ^
reinterpret_cast<uintptr_t>(Val.Divisor)) ^
(unsigned)Val.SignedOp;
}
};
typedef DenseMap<DivOpInfo, DivPhiNodes> DivCacheTy;
}
static bool insertFastDiv(Function &F,
Function::iterator &I,
BasicBlock::iterator &J,
IntegerType *BypassType,
bool UseDivOp,
bool UseSignedOp,
DivCacheTy &PerBBDivCache) {
Instruction *Instr = J;
Value *Dividend = Instr->getOperand(0);
Value *Divisor = Instr->getOperand(1);
if (isa<ConstantInt>(Divisor) ||
(isa<ConstantInt>(Dividend) && isa<ConstantInt>(Divisor))) {
return false;
}
BasicBlock *MainBB = I;
BasicBlock *SuccessorBB = I->splitBasicBlock(J);
++I;
BasicBlock *SlowBB = BasicBlock::Create(F.getContext(), "",
MainBB->getParent(), SuccessorBB);
SlowBB->moveBefore(SuccessorBB);
IRBuilder<> SlowBuilder(SlowBB, SlowBB->begin());
Value *SlowQuotientV;
Value *SlowRemainderV;
if (UseSignedOp) {
SlowQuotientV = SlowBuilder.CreateSDiv(Dividend, Divisor);
SlowRemainderV = SlowBuilder.CreateSRem(Dividend, Divisor);
} else {
SlowQuotientV = SlowBuilder.CreateUDiv(Dividend, Divisor);
SlowRemainderV = SlowBuilder.CreateURem(Dividend, Divisor);
}
SlowBuilder.CreateBr(SuccessorBB);
BasicBlock *FastBB = BasicBlock::Create(F.getContext(), "",
MainBB->getParent(), SuccessorBB);
FastBB->moveBefore(SlowBB);
IRBuilder<> FastBuilder(FastBB, FastBB->begin());
Value *ShortDivisorV = FastBuilder.CreateCast(Instruction::Trunc, Divisor,
BypassType);
Value *ShortDividendV = FastBuilder.CreateCast(Instruction::Trunc, Dividend,
BypassType);
Value *ShortQuotientV = FastBuilder.CreateExactUDiv(ShortDividendV,
ShortDivisorV);
Value *ShortRemainderV = FastBuilder.CreateURem(ShortDividendV,
ShortDivisorV);
Value *FastQuotientV = FastBuilder.CreateCast(Instruction::ZExt,
ShortQuotientV,
Dividend->getType());
Value *FastRemainderV = FastBuilder.CreateCast(Instruction::ZExt,
ShortRemainderV,
Dividend->getType());
FastBuilder.CreateBr(SuccessorBB);
IRBuilder<> SuccessorBuilder(SuccessorBB, SuccessorBB->begin());
PHINode *QuoPhi = SuccessorBuilder.CreatePHI(Instr->getType(), 2);
QuoPhi->addIncoming(SlowQuotientV, SlowBB);
QuoPhi->addIncoming(FastQuotientV, FastBB);
PHINode *RemPhi = SuccessorBuilder.CreatePHI(Instr->getType(), 2);
RemPhi->addIncoming(SlowRemainderV, SlowBB);
RemPhi->addIncoming(FastRemainderV, FastBB);
if (UseDivOp)
Instr->replaceAllUsesWith(QuoPhi);
else
Instr->replaceAllUsesWith(RemPhi);
Instr->eraseFromParent();
MainBB->getInstList().back().eraseFromParent();
IRBuilder<> MainBuilder(MainBB, MainBB->end());
Value *OrV = MainBuilder.CreateOr(Dividend, Divisor);
uint64_t BitMask = ~BypassType->getBitMask();
Value *AndV = MainBuilder.CreateAnd(OrV, BitMask);
Value *ZeroV = MainBuilder.getInt32(0);
Value *CmpV = MainBuilder.CreateICmpEQ(AndV, ZeroV);
MainBuilder.CreateCondBr(CmpV, FastBB, SlowBB);
J = I->begin();
DivOpInfo Key(UseSignedOp, Dividend, Divisor);
DivPhiNodes Value(QuoPhi, RemPhi);
PerBBDivCache.insert(std::pair<DivOpInfo, DivPhiNodes>(Key, Value));
return true;
}
static bool reuseOrInsertFastDiv(Function &F,
Function::iterator &I,
BasicBlock::iterator &J,
IntegerType *BypassType,
bool UseDivOp,
bool UseSignedOp,
DivCacheTy &PerBBDivCache) {
Instruction *Instr = J;
DivOpInfo Key(UseSignedOp, Instr->getOperand(0), Instr->getOperand(1));
DivCacheTy::iterator CacheI = PerBBDivCache.find(Key);
if (CacheI == PerBBDivCache.end()) {
return insertFastDiv(F, I, J, BypassType, UseDivOp, UseSignedOp,
PerBBDivCache);
}
DivPhiNodes &Value = CacheI->second;
if (UseDivOp) {
J->replaceAllUsesWith(Value.Quotient);
} else {
J->replaceAllUsesWith(Value.Remainder);
}
++J;
Instr->eraseFromParent();
return true;
}
bool llvm::bypassSlowDivision(Function &F,
Function::iterator &I,
const DenseMap<Type*, Type*> &BypassTypeMap) {
DivCacheTy DivCache;
bool MadeChange = false;
for (BasicBlock::iterator J = I->begin(); J != I->end(); J++) {
unsigned Opcode = J->getOpcode();
bool UseDivOp = Opcode == Instruction::SDiv || Opcode == Instruction::UDiv;
bool UseRemOp = Opcode == Instruction::SRem || Opcode == Instruction::URem;
bool UseSignedOp = Opcode == Instruction::SDiv ||
Opcode == Instruction::SRem;
if (!UseDivOp && !UseRemOp)
continue;
DenseMap<Type *, Type *>::const_iterator BT =
BypassTypeMap.find(J->getType());
if (BT == BypassTypeMap.end())
continue;
IntegerType *BypassType = cast<IntegerType>(BT->second);
MadeChange |= reuseOrInsertFastDiv(F, I, J, BypassType, UseDivOp,
UseSignedOp, DivCache);
}
return MadeChange;
}