//
//===----------------------------------------------------------------------===//
-#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"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Instructions.h"
using namespace llvm;
-namespace llvm {
+#define DEBUG_TYPE "bypass-slow-division"
+
+namespace {
struct DivOpInfo {
bool SignedOp;
Value *Dividend;
DivPhiNodes(PHINode *InQuotient, PHINode *InRemainder)
: Quotient(InQuotient), Remainder(InRemainder) {}
};
+}
+namespace llvm {
template<>
struct DenseMapInfo<DivOpInfo> {
static bool isEqual(const DivOpInfo &Val1, const DivOpInfo &Val2) {
}
static DivOpInfo getEmptyKey() {
- return DivOpInfo(false, 0, 0);
+ return DivOpInfo(false, nullptr, nullptr);
}
static DivOpInfo getTombstoneKey() {
- return DivOpInfo(true, 0, 0);
+ return DivOpInfo(true, nullptr, nullptr);
}
static unsigned getHashValue(const DivOpInfo &Val) {
return (unsigned)(reinterpret_cast<uintptr_t>(Val.Dividend) ^
reinterpret_cast<uintptr_t>(Val.Divisor)) ^
- (unsigned)Val.SignedOp;
+ (unsigned)Val.SignedOp;
}
};
// insertFastDiv - Substitutes the div/rem instruction with code that checks the
// value of the operands and uses a shorter-faster div/rem instruction when
// possible and the longer-slower div/rem instruction otherwise.
-static void insertFastDiv(Function &F,
+static bool insertFastDiv(Function &F,
Function::iterator &I,
BasicBlock::iterator &J,
IntegerType *BypassType,
bool UseDivOp,
bool UseSignedOp,
- DivCacheTy &PerBBDivCache)
-{
+ DivCacheTy &PerBBDivCache) {
// Get instruction operands
Instruction *Instr = J;
Value *Dividend = Instr->getOperand(0);
Value *Divisor = Instr->getOperand(1);
- if (dyn_cast<ConstantInt>(Divisor) != 0 ||
- (dyn_cast<ConstantInt>(Dividend) != 0 &&
- dyn_cast<ConstantInt>(Divisor) != 0)) {
+ if (isa<ConstantInt>(Divisor) ||
+ (isa<ConstantInt>(Dividend) && isa<ConstantInt>(Divisor))) {
// Operations with immediate values should have
// been solved and replaced during compile time.
- return;
+ return false;
}
// Basic Block is split before divide
BasicBlock *MainBB = I;
BasicBlock *SuccessorBB = I->splitBasicBlock(J);
- I++; //advance iterator I to successorBB
+ ++I; //advance iterator I to successorBB
// Add new basic block for slow divide operation
BasicBlock *SlowBB = 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 *ShortDivisorV = FastBuilder.CreateCast(Instruction::Trunc, Divisor,
+ BypassType);
+ Value *ShortDividendV = FastBuilder.CreateCast(Instruction::Trunc, Dividend,
+ BypassType);
// udiv/urem because optimization only handles positive numbers
Value *ShortQuotientV = FastBuilder.CreateExactUDiv(ShortDividendV,
- ShortDivisorV);
+ ShortDivisorV);
Value *ShortRemainderV = FastBuilder.CreateURem(ShortDividendV,
ShortDivisorV);
Value *FastQuotientV = FastBuilder.CreateCast(Instruction::ZExt,
- ShortQuotientV,
- Dividend->getType());
+ ShortQuotientV,
+ Dividend->getType());
Value *FastRemainderV = FastBuilder.CreateCast(Instruction::ZExt,
ShortRemainderV,
Dividend->getType());
RemPhi->addIncoming(FastRemainderV, FastBB);
// Replace Instr with appropriate phi node
- if (UseDivOp) {
+ if (UseDivOp)
Instr->replaceAllUsesWith(QuoPhi);
- } else {
+ else
Instr->replaceAllUsesWith(RemPhi);
- }
Instr->eraseFromParent();
// Combine operands into a single value with OR for value testing below
Value *AndV = MainBuilder.CreateAnd(OrV, BitMask);
// Compare operand values and branch
- Value *ZeroV = MainBuilder.getInt32(0);
+ Value *ZeroV = ConstantInt::getSigned(Dividend->getType(), 0);
Value *CmpV = MainBuilder.CreateICmpEQ(AndV, ZeroV);
MainBuilder.CreateCondBr(CmpV, FastBB, SlowBB);
DivOpInfo Key(UseSignedOp, Dividend, Divisor);
DivPhiNodes Value(QuoPhi, RemPhi);
PerBBDivCache.insert(std::pair<DivOpInfo, DivPhiNodes>(Key, Value));
+ return true;
}
// reuseOrInsertFastDiv - Reuses previously computed dividend or remainder if
// operands and operation are identical. Otherwise call insertFastDiv to perform
// the optimization and cache the resulting dividend and remainder.
-static void reuseOrInsertFastDiv(Function &F,
+static bool reuseOrInsertFastDiv(Function &F,
Function::iterator &I,
BasicBlock::iterator &J,
IntegerType *BypassType,
bool UseDivOp,
bool UseSignedOp,
- DivCacheTy &PerBBDivCache)
-{
+ DivCacheTy &PerBBDivCache) {
// Get instruction operands
Instruction *Instr = J;
DivOpInfo Key(UseSignedOp, Instr->getOperand(0), Instr->getOperand(1));
- DivCacheTy::const_iterator CacheI = PerBBDivCache.find(Key);
+ DivCacheTy::iterator CacheI = PerBBDivCache.find(Key);
if (CacheI == PerBBDivCache.end()) {
// If previous instance does not exist, insert fast div
- insertFastDiv(F, I, J, BypassType, UseDivOp, UseSignedOp, PerBBDivCache);
- return;
+ return insertFastDiv(F, I, J, BypassType, UseDivOp, UseSignedOp,
+ PerBBDivCache);
}
// Replace operation value with previously generated phi node
- DivPhiNodes Value = CacheI->second;
+ DivPhiNodes &Value = CacheI->second;
if (UseDivOp) {
// Replace all uses of div instruction with quotient phi node
J->replaceAllUsesWith(Value.Quotient);
}
// Advance to next operation
- J++;
+ ++J;
// Remove redundant operation
Instr->eraseFromParent();
+ return true;
}
// bypassSlowDivision - This optimization identifies DIV instructions that can
// be profitably bypassed and carried out with a shorter, faster divide.
-bool bypassSlowDivision(Function &F,
- Function::iterator &I,
- const llvm::DenseMap<Type *, Type *> &BypassTypeMap)
-{
+bool llvm::bypassSlowDivision(Function &F,
+ Function::iterator &I,
+ const DenseMap<unsigned int, unsigned int> &BypassWidths) {
DivCacheTy DivCache;
bool MadeChange = false;
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;
+ bool UseSignedOp = Opcode == Instruction::SDiv ||
+ Opcode == Instruction::SRem;
// Only optimize div or rem ops
- if (!UseDivOp && !UseRemOp) {
+ if (!UseDivOp && !UseRemOp)
continue;
- }
- // Continue if div/rem type is not bypassed
- DenseMap<Type *, Type *>::const_iterator BT = BypassTypeMap.find(J->getType());
- if (BT == BypassTypeMap.end()) {
+
+ // Skip division on vector types, only optimize integer instructions
+ if (!J->getType()->isIntegerTy())
continue;
- }
- IntegerType *BypassType = (IntegerType *)BT->second;
- reuseOrInsertFastDiv(F, I, J, BypassType, UseDivOp, UseSignedOp, DivCache);
- MadeChange = true;
+ // Get bitwidth of div/rem instruction
+ IntegerType *T = cast<IntegerType>(J->getType());
+ unsigned int bitwidth = T->getBitWidth();
+
+ // Continue if bitwidth is not bypassed
+ DenseMap<unsigned int, unsigned int>::const_iterator BI = BypassWidths.find(bitwidth);
+ if (BI == BypassWidths.end())
+ continue;
+
+ // Get type for div/rem instruction with bypass bitwidth
+ IntegerType *BT = IntegerType::get(J->getContext(), BI->second);
+
+ MadeChange |= reuseOrInsertFastDiv(F, I, J, BT, UseDivOp,
+ UseSignedOp, DivCache);
}
return MadeChange;
projects / oota-llvm.git / blobdiff