Index: lib/Transforms/Utils/BypassSlowDivision.cpp =================================================================== --- lib/Transforms/Utils/BypassSlowDivision.cpp +++ lib/Transforms/Utils/BypassSlowDivision.cpp @@ -70,91 +70,191 @@ }; typedef DenseMap DivCacheTy; + typedef DenseMap BypassWidthsTy; } -// 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 bool insertFastDiv(Instruction *I, IntegerType *BypassType, - bool UseDivOp, bool UseSignedOp, - DivCacheTy &PerBBDivCache) { - Function *F = I->getParent()->getParent(); - // Get instruction operands - Value *Dividend = I->getOperand(0); - Value *Divisor = I->getOperand(1); +namespace { +class FastDivInsertionTask { + // These fields are set during initialization. + bool IsSlowDivision; + unsigned Opcode; + Instruction *SlowDiv; + IntegerType *SlowType; + IntegerType *BypassType; + BasicBlock *MainBB; + Value *Dividend; + Value *Divisor; + DivCacheTy &Cache; + + // These fields are used to pass intermediate results through private + // methods. + Value *ShortQuotientV; + Value *ShortRemainderV; + Value *LongQuotientV; + Value *LongRemainderV; + + BasicBlock *createSlowBB(BasicBlock *Successor); + BasicBlock *createFastBB(BasicBlock *Successor); + void createDivRemPhiNodes(BasicBlock *ShortBB, BasicBlock *LongBB, + BasicBlock *PhiBB); + Value *createDivRuntimeCheck(); + void insertFastDiv(); + +public: + FastDivInsertionTask(Instruction *I, DivCacheTy &Cache, + const BypassWidthsTy &BypassWidths); + Value *getReplacement(); + + Instruction *getSlowDiv() { return SlowDiv; } + IntegerType *getSlowType() { return SlowType; } + Value *getDividend() { return Dividend; } + Value *getDivisor() { return Divisor; } + + bool isSignedDiv() { + return Opcode == Instruction::SDiv || Opcode == Instruction::SRem; + } + bool isDivisionOp() { + return Opcode == Instruction::SDiv || Opcode == Instruction::UDiv; + } +}; +} // anonymous namespace + +FastDivInsertionTask::FastDivInsertionTask(Instruction *I, DivCacheTy &Cache, + const BypassWidthsTy &BypassWidths) + : IsSlowDivision(false), Cache(Cache), ShortQuotientV(nullptr), + ShortRemainderV(nullptr), LongQuotientV(nullptr), + LongRemainderV(nullptr) { + SlowDiv = I; + Opcode = I->getOpcode(); + + switch (Opcode) { + case Instruction::UDiv: + case Instruction::SDiv: + case Instruction::URem: + case Instruction::SRem: + break; + default: + // I is not a div/rem operation. + return; + } - if (isa(Divisor)) { - // Division by a constant should have been been solved and replaced earlier - // in the pipeline. - return false; + // Skip division on vector types, only optimize integer instructions + if (!I->getType()->isIntegerTy()) + return; + + SlowType = cast(I->getType()); + unsigned bitwidth = SlowType->getBitWidth(); + + // Skip if bitwidth is not bypassed + BypassWidthsTy::const_iterator BI = BypassWidths.find(bitwidth); + if (BI == BypassWidths.end()) + return; + + // Get type for div/rem instruction with bypass bitwidth + IntegerType *BT = IntegerType::get(I->getContext(), BI->second); + BypassType = BT; + + // Initialize the rest of the object. + MainBB = I->getParent(); + Dividend = SlowDiv->getOperand(0); + Divisor = SlowDiv->getOperand(1); + + // The instruction is indeed a slow division operation. + IsSlowDivision = true; +} + +/// Reuses previously computed dividend or remainder from the current BB if +/// operands and operation are identical. Otherwise calls insertFastDiv to +/// perform the optimization and caches the resulting dividend and remainder. +/// If no replacement can be generated, nullptr is returned. +Value *FastDivInsertionTask::getReplacement() { + // First, make sure that the task is valid. + if (!IsSlowDivision) + return nullptr; + + // Then, look for a value in Cache. + DivOpInfo Key(isSignedDiv(), Dividend, Divisor); + DivCacheTy::iterator CacheI = Cache.find(Key); + + if (CacheI == Cache.end()) { + // If previous instance does not exist, try to insert fast div + insertFastDiv(); + CacheI = Cache.find(Key); } - // If the numerator is a constant, bail if it doesn't fit into BypassType. - if (ConstantInt *ConstDividend = dyn_cast(Dividend)) - if (ConstDividend->getValue().getActiveBits() > BypassType->getBitWidth()) - return false; + // If it's still not in Cache, there's nothing we can do. + if (CacheI == Cache.end()) + return nullptr; - // Basic Block is split before divide - BasicBlock *MainBB = &*I->getParent(); - BasicBlock *SuccessorBB = MainBB->splitBasicBlock(I); - - // Add new basic block for slow divide operation - 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); + DivPhiNodes &Value = CacheI->second; + if (isDivisionOp()) + return Value.Quotient; + else + return Value.Remainder; +} + +/// Add new basic block for slow divide operation and put it before SuccessorBB. +BasicBlock *FastDivInsertionTask::createSlowBB(BasicBlock *SuccessorBB) { + BasicBlock *SlowBB = BasicBlock::Create(MainBB->getParent()->getContext(), "", + MainBB->getParent(), SuccessorBB); + IRBuilder<> Builder(SlowBB, SlowBB->begin()); + + if (isSignedDiv()) { + LongQuotientV = Builder.CreateSDiv(Dividend, Divisor); + LongRemainderV = Builder.CreateSRem(Dividend, Divisor); } else { - SlowQuotientV = SlowBuilder.CreateUDiv(Dividend, Divisor); - SlowRemainderV = SlowBuilder.CreateURem(Dividend, Divisor); + LongQuotientV = Builder.CreateUDiv(Dividend, Divisor); + LongRemainderV = Builder.CreateURem(Dividend, Divisor); } - SlowBuilder.CreateBr(SuccessorBB); - - // Add new basic block for fast divide operation - 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); + + Builder.CreateBr(SuccessorBB); + return SlowBB; +} + +/// Add new basic block for fast divide operation and put it before SuccessorBB. +BasicBlock *FastDivInsertionTask::createFastBB(BasicBlock *SuccessorBB) { + BasicBlock *FastBB = BasicBlock::Create(MainBB->getParent()->getContext(), "", + MainBB->getParent(), SuccessorBB); + IRBuilder<> Builder(FastBB, FastBB->begin()); + Value *ShortDivisorV = + Builder.CreateCast(Instruction::Trunc, Divisor, BypassType); + Value *ShortDividendV = + Builder.CreateCast(Instruction::Trunc, Dividend, BypassType); // udiv/urem because optimization only handles positive numbers - Value *ShortQuotientV = FastBuilder.CreateUDiv(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); - - // Phi nodes for result of div and rem - IRBuilder<> SuccessorBuilder(SuccessorBB, SuccessorBB->begin()); - PHINode *QuoPhi = SuccessorBuilder.CreatePHI(I->getType(), 2); - QuoPhi->addIncoming(SlowQuotientV, SlowBB); - QuoPhi->addIncoming(FastQuotientV, FastBB); - PHINode *RemPhi = SuccessorBuilder.CreatePHI(I->getType(), 2); - RemPhi->addIncoming(SlowRemainderV, SlowBB); - RemPhi->addIncoming(FastRemainderV, FastBB); - - // Replace I with appropriate phi node - if (UseDivOp) - I->replaceAllUsesWith(QuoPhi); - else - I->replaceAllUsesWith(RemPhi); - I->eraseFromParent(); + Value *ShortQV = Builder.CreateUDiv(ShortDividendV, ShortDivisorV); + Value *ShortRV = Builder.CreateURem(ShortDividendV, ShortDivisorV); + ShortQuotientV = Builder.CreateCast(Instruction::ZExt, ShortQV, SlowType); + ShortRemainderV = Builder.CreateCast(Instruction::ZExt, ShortRV, SlowType); + Builder.CreateBr(SuccessorBB); - // Combine operands into a single value with OR for value testing below - MainBB->getInstList().back().eraseFromParent(); - IRBuilder<> MainBuilder(MainBB, MainBB->end()); + return FastBB; +} + +/// Creates Phi nodes for result of Div and Rem and stores them in Cache. +void FastDivInsertionTask::createDivRemPhiNodes(BasicBlock *ShortBB, + BasicBlock *LongBB, + BasicBlock *PhiBB) { + IRBuilder<> Builder(PhiBB, PhiBB->begin()); + PHINode *QuoPhi = Builder.CreatePHI(SlowType, 2); + QuoPhi->addIncoming(LongQuotientV, LongBB); + QuoPhi->addIncoming(ShortQuotientV, ShortBB); + PHINode *RemPhi = Builder.CreatePHI(SlowType, 2); + RemPhi->addIncoming(LongRemainderV, LongBB); + RemPhi->addIncoming(ShortRemainderV, ShortBB); + + // Cache phi nodes to be used later in place of other instances + // of div or rem with the same sign, dividend, and divisor + DivOpInfo Key(isSignedDiv(), Dividend, Divisor); + DivPhiNodes Val(QuoPhi, RemPhi); + Cache.insert(std::pair(Key, Val)); +} + +/// Creates a run-time check to test whether both operands fit the shorter type. +/// The check is inserted at the end of MainBB. +/// True return value means that the operands fit. +Value *FastDivInsertionTask::createDivRuntimeCheck() { + IRBuilder<> Builder(MainBB, MainBB->end()); // We should have bailed out above if the divisor is a constant, but the // dividend may still be a constant. Set OrV to our non-constant operands @@ -163,65 +263,51 @@ Value *OrV; if (!isa(Dividend)) - OrV = MainBuilder.CreateOr(Dividend, Divisor); + OrV = Builder.CreateOr(Dividend, Divisor); else OrV = Divisor; // BitMask is inverted to check if the operands are // larger than the bypass type uint64_t BitMask = ~BypassType->getBitMask(); - Value *AndV = MainBuilder.CreateAnd(OrV, BitMask); + Value *AndV = Builder.CreateAnd(OrV, BitMask); - // Compare operand values and branch - Value *ZeroV = ConstantInt::getSigned(Dividend->getType(), 0); - Value *CmpV = MainBuilder.CreateICmpEQ(AndV, ZeroV); - MainBuilder.CreateCondBr(CmpV, FastBB, SlowBB); - - // Cache phi nodes to be used later in place of other instances - // of div or rem with the same sign, dividend, and divisor - DivOpInfo Key(UseSignedOp, Dividend, Divisor); - DivPhiNodes Value(QuoPhi, RemPhi); - PerBBDivCache.insert(std::pair(Key, Value)); - return true; + // Compare operand values + Value *ZeroV = ConstantInt::getSigned(SlowType, 0); + return Builder.CreateICmpEQ(AndV, ZeroV); } -// reuseOrInsertFastDiv - Reuses previously computed dividend or remainder from -// the current BB if operands and operation are identical. Otherwise calls -// insertFastDiv to perform the optimization and caches the resulting dividend -// and remainder. -static bool reuseOrInsertFastDiv(Instruction *I, IntegerType *BypassType, - bool UseDivOp, bool UseSignedOp, - DivCacheTy &PerBBDivCache) { - // Get instruction operands - DivOpInfo Key(UseSignedOp, I->getOperand(0), I->getOperand(1)); - DivCacheTy::iterator CacheI = PerBBDivCache.find(Key); - - if (CacheI == PerBBDivCache.end()) { - // If previous instance does not exist, insert fast div - return insertFastDiv(I, BypassType, UseDivOp, UseSignedOp, PerBBDivCache); +/// 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. +void FastDivInsertionTask::insertFastDiv() { + if (isa(Divisor)) { + // Division by a constant should have been been solved and replaced earlier + // in the pipeline. + return; } - // Replace operation value with previously generated phi node - DivPhiNodes &Value = CacheI->second; - if (UseDivOp) { - // Replace all uses of div instruction with quotient phi node - I->replaceAllUsesWith(Value.Quotient); - } else { - // Replace all uses of rem instruction with remainder phi node - I->replaceAllUsesWith(Value.Remainder); - } + // If the numerator is a constant, bail if it doesn't fit into BypassType. + if (ConstantInt *ConstDividend = dyn_cast(Dividend)) + if (ConstDividend->getValue().getActiveBits() > BypassType->getBitWidth()) + return; - // Remove redundant operation - I->eraseFromParent(); - return true; + // Basic Block is split before divide + BasicBlock *SuccessorBB = MainBB->splitBasicBlock(SlowDiv); + MainBB->getInstList().back().eraseFromParent(); + BasicBlock *FastBB = createFastBB(SuccessorBB); + BasicBlock *SlowBB = createSlowBB(SuccessorBB); + createDivRemPhiNodes(FastBB, SlowBB, SuccessorBB); + Value *CmpV = createDivRuntimeCheck(); + IRBuilder<> Builder(MainBB, MainBB->end()); + Builder.CreateCondBr(CmpV, FastBB, SlowBB); } -// bypassSlowDivision - This optimization identifies DIV instructions in a BB -// that can be profitably bypassed and carried out with a shorter, faster -// divide. -bool llvm::bypassSlowDivision( - BasicBlock *BB, const DenseMap &BypassWidths) { - DivCacheTy DivCache; +/// This optimization identifies DIV instructions in a BB that can be profitably +/// bypassed and carried out with a shorter, faster divide. +bool llvm::bypassSlowDivision(BasicBlock *BB, + const BypassWidthsTy &BypassWidths) { + DivCacheTy PerBBDivCache; bool MadeChange = false; Instruction* Next = &*BB->begin(); @@ -231,40 +317,18 @@ Instruction* I = Next; Next = Next->getNextNode(); - // Get instruction details - unsigned Opcode = I->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; - - // Only optimize div or rem ops - if (!UseDivOp && !UseRemOp) - continue; - - // Skip division on vector types, only optimize integer instructions - if (!I->getType()->isIntegerTy()) - continue; - - // Get bitwidth of div/rem instruction - IntegerType *T = cast(I->getType()); - unsigned int bitwidth = T->getBitWidth(); - - // Continue if bitwidth is not bypassed - DenseMap::const_iterator BI = BypassWidths.find(bitwidth); - if (BI == BypassWidths.end()) - continue; - - // Get type for div/rem instruction with bypass bitwidth - IntegerType *BT = IntegerType::get(I->getContext(), BI->second); - - MadeChange |= reuseOrInsertFastDiv(I, BT, UseDivOp, UseSignedOp, DivCache); + FastDivInsertionTask Task(I, PerBBDivCache, BypassWidths); + if (Value *Replacement = Task.getReplacement()) { + I->replaceAllUsesWith(Replacement); + I->eraseFromParent(); + MadeChange |= true; + } } // Above we eagerly create divs and rems, as pairs, so that we can efficiently // create divrem machine instructions. Now erase any unused divs / rems so we // don't leave extra instructions sitting around. - for (auto &KV : DivCache) + for (auto &KV : PerBBDivCache) for (Instruction *Phi : {KV.second.Quotient, KV.second.Remainder}) RecursivelyDeleteTriviallyDeadInstructions(Phi);