diff options
author | Michael Zolotukhin <mzolotukhin@apple.com> | 2014-04-21 12:01:33 +0000 |
---|---|---|
committer | Michael Zolotukhin <mzolotukhin@apple.com> | 2014-04-21 12:01:33 +0000 |
commit | d329c79f164b5bd876014c4c0225ae298640bd81 (patch) | |
tree | ded4f1ac6e6abb0f9b92781c0df2ef5f55ef1610 /lib/CodeGen/CodeGenPrepare.cpp | |
parent | acbc9cb577e816c57c37c95b7dddb4cad835b0ba (diff) | |
download | llvm-d329c79f164b5bd876014c4c0225ae298640bd81.tar.gz llvm-d329c79f164b5bd876014c4c0225ae298640bd81.tar.bz2 llvm-d329c79f164b5bd876014c4c0225ae298640bd81.tar.xz |
Reapply r206732. This time without optimization of branches.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206749 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/CodeGen/CodeGenPrepare.cpp')
-rw-r--r-- | lib/CodeGen/CodeGenPrepare.cpp | 236 |
1 files changed, 236 insertions, 0 deletions
diff --git a/lib/CodeGen/CodeGenPrepare.cpp b/lib/CodeGen/CodeGenPrepare.cpp index 1ab24162dc..009e153e0e 100644 --- a/lib/CodeGen/CodeGenPrepare.cpp +++ b/lib/CodeGen/CodeGenPrepare.cpp @@ -688,6 +688,242 @@ bool CodeGenPrepare::OptimizeCallInst(CallInst *CI) { } return true; } + // Lower all uses of llvm.safe.[us]{div|rem}... + if (II && + (II->getIntrinsicID() == Intrinsic::safe_sdiv || + II->getIntrinsicID() == Intrinsic::safe_udiv || + II->getIntrinsicID() == Intrinsic::safe_srem || + II->getIntrinsicID() == Intrinsic::safe_urem)) { + // Given + // result_struct = type {iN, i1} + // %R = call result_struct llvm.safe.sdiv.iN(iN %x, iN %y) + // Expand it to actual IR, which produces result to the same variable %R. + // First element of the result %R.1 is the result of division, second + // element shows whether the division was correct or not. + // If %y is 0, %R.1 is 0, %R.2 is 1. (1) + // If %x is minSignedValue and %y is -1, %R.1 is %x, %R.2 is 1. (2) + // In other cases %R.1 is (sdiv %x, %y), %R.2 is 0. (3) + // + // Similar applies to srem, udiv, and urem builtins, except that in unsigned + // variants we don't check condition (2). + + bool IsSigned; + BinaryOperator::BinaryOps Op; + switch (II->getIntrinsicID()) { + case Intrinsic::safe_sdiv: + IsSigned = true; + Op = Instruction::SDiv; + break; + case Intrinsic::safe_udiv: + IsSigned = false; + Op = Instruction::UDiv; + break; + case Intrinsic::safe_srem: + IsSigned = true; + Op = Instruction::SRem; + break; + case Intrinsic::safe_urem: + IsSigned = false; + Op = Instruction::URem; + break; + default: + llvm_unreachable("Only Div/Rem intrinsics are handled here."); + } + + Value *LHS = II->getOperand(0), *RHS = II->getOperand(1); + bool DivWellDefined = TLI && TLI->isDivWellDefined(); + + bool ResultNeeded[2] = {false, false}; + SmallVector<User*, 1> ResultsUsers[2]; + bool BadCase = false; + for (User *U: II->users()) { + ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(U); + if (!EVI || EVI->getNumIndices() > 1 || EVI->getIndices()[0] > 1) { + BadCase = true; + break; + } + ResultNeeded[EVI->getIndices()[0]] = true; + ResultsUsers[EVI->getIndices()[0]].push_back(U); + } + // Behave conservatively, if there is an unusual user of the results. + if (BadCase) + ResultNeeded[0] = ResultNeeded[1] = true; + + // Early exit if non of the results is ever used. + if (!ResultNeeded[0] && !ResultNeeded[1]) { + II->eraseFromParent(); + return true; + } + + // Early exit if the second result (flag) isn't used and target + // div-instruction computes exactly what we want to get as the first result + // and never traps. + if (ResultNeeded[0] && !ResultNeeded[1] && DivWellDefined) { + BinaryOperator *Div = BinaryOperator::Create(Op, LHS, RHS); + Div->insertAfter(II); + for (User *U: ResultsUsers[0]) { + Instruction *UserInst = dyn_cast<Instruction>(U); + assert(UserInst && "Unexpected null-instruction"); + UserInst->replaceAllUsesWith(Div); + UserInst->eraseFromParent(); + } + II->eraseFromParent(); + CurInstIterator = Div; + ModifiedDT = true; + return true; + } + + Value *MinusOne = Constant::getAllOnesValue(LHS->getType()); + Value *Zero = Constant::getNullValue(LHS->getType()); + + // Split the original BB and create other basic blocks that will be used + // for checks. + BasicBlock *StartBB = II->getParent(); + BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(II)); + BasicBlock *NextBB = StartBB->splitBasicBlock(SplitPt, "div.end"); + + BasicBlock *DivByZeroBB; + DivByZeroBB = BasicBlock::Create(II->getContext(), "div.divz", + NextBB->getParent(), NextBB); + BranchInst::Create(NextBB, DivByZeroBB); + BasicBlock *DivBB = BasicBlock::Create(II->getContext(), "div.div", + NextBB->getParent(), NextBB); + BranchInst::Create(NextBB, DivBB); + + // For signed variants, check the condition (2): + // LHS == SignedMinValue, RHS == -1. + Value *CmpMinusOne; + Value *CmpMinValue; + BasicBlock *ChkDivMinBB; + BasicBlock *DivMinBB; + Value *MinValue; + if (IsSigned) { + APInt SignedMinValue = + APInt::getSignedMinValue(LHS->getType()->getPrimitiveSizeInBits()); + MinValue = Constant::getIntegerValue(LHS->getType(), SignedMinValue); + ChkDivMinBB = BasicBlock::Create(II->getContext(), "div.chkdivmin", + NextBB->getParent(), NextBB); + BranchInst::Create(NextBB, ChkDivMinBB); + DivMinBB = BasicBlock::Create(II->getContext(), "div.divmin", + NextBB->getParent(), NextBB); + BranchInst::Create(NextBB, DivMinBB); + CmpMinusOne = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, + RHS, MinusOne, "cmp.rhs.minus.one", + ChkDivMinBB->getTerminator()); + CmpMinValue = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, + LHS, MinValue, "cmp.lhs.signed.min", + ChkDivMinBB->getTerminator()); + BinaryOperator *CmpSignedOvf = BinaryOperator::Create(Instruction::And, + CmpMinusOne, + CmpMinValue); + // Here we're interested in the case when both %x is TMin and %y is -1. + // In this case the result will overflow. + // If that's not the case, we can perform usual division. These blocks + // will be inserted after DivByZero, so the division will be safe. + CmpSignedOvf->insertBefore(ChkDivMinBB->getTerminator()); + BranchInst::Create(DivMinBB, DivBB, CmpSignedOvf, + ChkDivMinBB->getTerminator()); + ChkDivMinBB->getTerminator()->eraseFromParent(); + } + + // Check the condition (1): + // RHS == 0. + Value *CmpDivZero = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, + RHS, Zero, "cmp.rhs.zero", + StartBB->getTerminator()); + + // If RHS != 0, we want to check condition (2) in signed case, or proceed + // to usual division in unsigned case. + BranchInst::Create(DivByZeroBB, IsSigned ? ChkDivMinBB : DivBB, CmpDivZero, + StartBB->getTerminator()); + StartBB->getTerminator()->eraseFromParent(); + + // At the moment we have all the control flow created. We just need to + // insert DIV and PHI (if needed) to get the result value. + Instruction *DivRes, *FlagRes; + Instruction *InsPoint = nullptr; + if (ResultNeeded[0]) { + BinaryOperator *Div = BinaryOperator::Create(Op, LHS, RHS); + if (DivWellDefined) { + // The result value is the result of DIV operation placed right at the + // original place of the intrinsic. + Div->insertAfter(II); + DivRes = Div; + } else { + // The result is a PHI-node. + Div->insertBefore(DivBB->getTerminator()); + PHINode *DivResPN = + PHINode::Create(LHS->getType(), IsSigned ? 3 : 2, "div.res.phi", + NextBB->begin()); + DivResPN->addIncoming(Div, DivBB); + DivResPN->addIncoming(Zero, DivByZeroBB); + if (IsSigned) + DivResPN->addIncoming(MinValue, DivMinBB); + DivRes = DivResPN; + InsPoint = DivResPN; + } + } + + // Prepare a value for the second result (flag) if it is needed. + if (ResultNeeded[1]) { + Type *FlagTy = II->getType()->getStructElementType(1); + PHINode *FlagResPN = + PHINode::Create(FlagTy, IsSigned ? 3 : 2, "div.flag.phi", + NextBB->begin()); + FlagResPN->addIncoming(Constant::getNullValue(FlagTy), DivBB); + FlagResPN->addIncoming(Constant::getAllOnesValue(FlagTy), DivByZeroBB); + if (IsSigned) + FlagResPN->addIncoming(Constant::getAllOnesValue(FlagTy), DivMinBB); + FlagRes = FlagResPN; + if (!InsPoint) + InsPoint = FlagRes; + } + + // If possible, propagate the results to the user. Otherwise, create alloca, + // and create a struct with the results on stack. + if (!BadCase) { + if (ResultNeeded[0]) { + for (User *U: ResultsUsers[0]) { + Instruction *UserInst = dyn_cast<Instruction>(U); + assert(UserInst && "Unexpected null-instruction"); + UserInst->replaceAllUsesWith(DivRes); + UserInst->eraseFromParent(); + } + } + if (ResultNeeded[1]) { + for (User *FlagU: ResultsUsers[1]) { + Instruction *FlagUInst = dyn_cast<Instruction>(FlagU); + FlagUInst->replaceAllUsesWith(FlagRes); + FlagUInst->eraseFromParent(); + } + } + } else { + // Create alloca, store our new values to it, and then load the final + // result from it. + Constant *Idx0 = ConstantInt::get(Type::getInt32Ty(II->getContext()), 0); + Constant *Idx1 = ConstantInt::get(Type::getInt32Ty(II->getContext()), 1); + Value *Idxs_DivRes[2] = {Idx0, Idx0}; + Value *Idxs_FlagRes[2] = {Idx0, Idx1}; + Value *NewRes = new llvm::AllocaInst(II->getType(), 0, "div.res.ptr", II); + Instruction *ResDivAddr = GetElementPtrInst::Create(NewRes, Idxs_DivRes); + Instruction *ResFlagAddr = + GetElementPtrInst::Create(NewRes, Idxs_FlagRes); + ResDivAddr->insertAfter(InsPoint); + ResFlagAddr->insertAfter(ResDivAddr); + StoreInst *StoreResDiv = new StoreInst(DivRes, ResDivAddr); + StoreInst *StoreResFlag = new StoreInst(FlagRes, ResFlagAddr); + StoreResDiv->insertAfter(ResFlagAddr); + StoreResFlag->insertAfter(StoreResDiv); + LoadInst *LoadRes = new LoadInst(NewRes, "div.res"); + LoadRes->insertAfter(StoreResFlag); + II->replaceAllUsesWith(LoadRes); + } + + II->eraseFromParent(); + CurInstIterator = StartBB->end(); + ModifiedDT = true; + return true; + } if (II && TLI) { SmallVector<Value*, 2> PtrOps; |