//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "codegenprepare"
#include "llvm/CodeGen/Passes.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallSet.h"
using namespace llvm;
using namespace llvm::PatternMatch;
+#define DEBUG_TYPE "codegenprepare"
+
STATISTIC(NumBlocksElim, "Number of blocks eliminated");
STATISTIC(NumPHIsElim, "Number of trivial PHIs eliminated");
STATISTIC(NumGEPsElim, "Number of GEPs converted to casts");
return MadeChange;
}
+/// isExtractBitsCandidateUse - Check if the candidates could
+/// be combined with shift instruction, which includes:
+/// 1. Truncate instruction
+/// 2. And instruction and the imm is a mask of the low bits:
+/// imm & (imm+1) == 0
+bool isExtractBitsCandidateUse(Instruction *User) {
+ if (!isa<TruncInst>(User)) {
+ if (User->getOpcode() != Instruction::And ||
+ !isa<ConstantInt>(User->getOperand(1)))
+ return false;
+
+ const APInt &Cimm = cast<ConstantInt>(User->getOperand(1))->getValue();
+
+ if ((Cimm & (Cimm + 1)).getBoolValue())
+ return false;
+ }
+ return true;
+}
+
+/// SinkShiftAndTruncate - sink both shift and truncate instruction
+/// to the use of truncate's BB.
+bool
+SinkShiftAndTruncate(BinaryOperator *ShiftI, Instruction *User, ConstantInt *CI,
+ DenseMap<BasicBlock *, BinaryOperator *> &InsertedShifts,
+ const TargetLowering &TLI) {
+ BasicBlock *UserBB = User->getParent();
+ DenseMap<BasicBlock *, CastInst *> InsertedTruncs;
+ TruncInst *TruncI = dyn_cast<TruncInst>(User);
+ bool MadeChange = false;
+
+ for (Value::user_iterator TruncUI = TruncI->user_begin(),
+ TruncE = TruncI->user_end();
+ TruncUI != TruncE;) {
+
+ Use &TruncTheUse = TruncUI.getUse();
+ Instruction *TruncUser = cast<Instruction>(*TruncUI);
+ // Preincrement use iterator so we don't invalidate it.
+
+ ++TruncUI;
+
+ int ISDOpcode = TLI.InstructionOpcodeToISD(TruncUser->getOpcode());
+ if (!ISDOpcode)
+ continue;
+
+ // If the use is actually a legal node, there will not be an implicit
+ // truncate.
+ if (TLI.isOperationLegalOrCustom(ISDOpcode,
+ EVT::getEVT(TruncUser->getType())))
+ continue;
+
+ // Don't bother for PHI nodes.
+ if (isa<PHINode>(TruncUser))
+ continue;
+
+ BasicBlock *TruncUserBB = TruncUser->getParent();
+
+ if (UserBB == TruncUserBB)
+ continue;
+
+ BinaryOperator *&InsertedShift = InsertedShifts[TruncUserBB];
+ CastInst *&InsertedTrunc = InsertedTruncs[TruncUserBB];
+
+ if (!InsertedShift && !InsertedTrunc) {
+ BasicBlock::iterator InsertPt = TruncUserBB->getFirstInsertionPt();
+ // Sink the shift
+ if (ShiftI->getOpcode() == Instruction::AShr)
+ InsertedShift =
+ BinaryOperator::CreateAShr(ShiftI->getOperand(0), CI, "", InsertPt);
+ else
+ InsertedShift =
+ BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI, "", InsertPt);
+
+ // Sink the trunc
+ BasicBlock::iterator TruncInsertPt = TruncUserBB->getFirstInsertionPt();
+ TruncInsertPt++;
+
+ InsertedTrunc = CastInst::Create(TruncI->getOpcode(), InsertedShift,
+ TruncI->getType(), "", TruncInsertPt);
+
+ MadeChange = true;
+
+ TruncTheUse = InsertedTrunc;
+ }
+ }
+ return MadeChange;
+}
+
+/// OptimizeExtractBits - sink the shift *right* instruction into user blocks if
+/// the uses could potentially be combined with this shift instruction and
+/// generate BitExtract instruction. It will only be applied if the architecture
+/// supports BitExtract instruction. Here is an example:
+/// BB1:
+/// %x.extract.shift = lshr i64 %arg1, 32
+/// BB2:
+/// %x.extract.trunc = trunc i64 %x.extract.shift to i16
+/// ==>
+///
+/// BB2:
+/// %x.extract.shift.1 = lshr i64 %arg1, 32
+/// %x.extract.trunc = trunc i64 %x.extract.shift.1 to i16
+///
+/// CodeGen will recoginze the pattern in BB2 and generate BitExtract
+/// instruction.
+/// Return true if any changes are made.
+static bool OptimizeExtractBits(BinaryOperator *ShiftI, ConstantInt *CI,
+ const TargetLowering &TLI) {
+ BasicBlock *DefBB = ShiftI->getParent();
+
+ /// Only insert instructions in each block once.
+ DenseMap<BasicBlock *, BinaryOperator *> InsertedShifts;
+
+ bool shiftIsLegal = TLI.isTypeLegal(TLI.getValueType(ShiftI->getType()));
+
+ bool MadeChange = false;
+ for (Value::user_iterator UI = ShiftI->user_begin(), E = ShiftI->user_end();
+ UI != E;) {
+ Use &TheUse = UI.getUse();
+ Instruction *User = cast<Instruction>(*UI);
+ // Preincrement use iterator so we don't invalidate it.
+ ++UI;
+
+ // Don't bother for PHI nodes.
+ if (isa<PHINode>(User))
+ continue;
+
+ if (!isExtractBitsCandidateUse(User))
+ continue;
+
+ BasicBlock *UserBB = User->getParent();
+
+ if (UserBB == DefBB) {
+ // If the shift and truncate instruction are in the same BB. The use of
+ // the truncate(TruncUse) may still introduce another truncate if not
+ // legal. In this case, we would like to sink both shift and truncate
+ // instruction to the BB of TruncUse.
+ // for example:
+ // BB1:
+ // i64 shift.result = lshr i64 opnd, imm
+ // trunc.result = trunc shift.result to i16
+ //
+ // BB2:
+ // ----> We will have an implicit truncate here if the architecture does
+ // not have i16 compare.
+ // cmp i16 trunc.result, opnd2
+ //
+ if (isa<TruncInst>(User) && shiftIsLegal
+ // If the type of the truncate is legal, no trucate will be
+ // introduced in other basic blocks.
+ && (!TLI.isTypeLegal(TLI.getValueType(User->getType()))))
+ MadeChange =
+ SinkShiftAndTruncate(ShiftI, User, CI, InsertedShifts, TLI);
+
+ continue;
+ }
+ // If we have already inserted a shift into this block, use it.
+ BinaryOperator *&InsertedShift = InsertedShifts[UserBB];
+
+ if (!InsertedShift) {
+ BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
+
+ if (ShiftI->getOpcode() == Instruction::AShr)
+ InsertedShift =
+ BinaryOperator::CreateAShr(ShiftI->getOperand(0), CI, "", InsertPt);
+ else
+ InsertedShift =
+ BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI, "", InsertPt);
+
+ MadeChange = true;
+ }
+
+ // Replace a use of the shift with a use of the new shift.
+ TheUse = InsertedShift;
+ }
+
+ // If we removed all uses, nuke the shift.
+ if (ShiftI->use_empty())
+ ShiftI->eraseFromParent();
+
+ return MadeChange;
+}
+
namespace {
class CodeGenPrepareFortifiedLibCalls : public SimplifyFortifiedLibCalls {
protected:
return true;
}
- // Check if the flag is used to jump out to a 'trap' block
- // If it's the case, we want to use this block directly when we create
- // branches after comparing with 0 and comparing with -1 (signed case).
- // We can do it only iff we can track all the uses of the flag, i.e. the
- // only users are EXTRACTVALUE-insns, and their users are conditional
- // branches, targeting the same 'trap' basic block.
- BasicBlock *TrapBB = nullptr;
- bool DoRelinkTrap = true;
- for (User *FlagU: ResultsUsers[1]) {
- for (User *U: FlagU->users()) {
- BranchInst *TrapBranch = dyn_cast<BranchInst>(U);
- // If the user isn't a branch-insn, or it jumps to another BB, don't
- // try to use TrapBB in the lowering.
- if (!TrapBranch || (TrapBB && TrapBB != TrapBranch->getSuccessor(0))) {
- DoRelinkTrap = false;
- break;
- }
- TrapBB = TrapBranch->getSuccessor(0);
- }
- }
- if (!TrapBB)
- DoRelinkTrap = false;
- // We want to reuse TrapBB if possible, because in that case we can avoid
- // creating new basic blocks and thus overcomplicating the IR. However, if
- // DIV instruction isn't well defined, we still need those blocks to model
- // well-defined behaviour. Thus, we can't reuse TrapBB in this case.
- if (!DivWellDefined)
- DoRelinkTrap = false;
-
Value *MinusOne = Constant::getAllOnesValue(LHS->getType());
Value *Zero = Constant::getNullValue(LHS->getType());
BasicBlock *NextBB = StartBB->splitBasicBlock(SplitPt, "div.end");
BasicBlock *DivByZeroBB;
- if (!DoRelinkTrap) {
- DivByZeroBB = BasicBlock::Create(II->getContext(), "div.divz",
- NextBB->getParent(), NextBB);
- BranchInst::Create(NextBB, 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);
ChkDivMinBB = BasicBlock::Create(II->getContext(), "div.chkdivmin",
NextBB->getParent(), NextBB);
BranchInst::Create(NextBB, ChkDivMinBB);
- if (!DoRelinkTrap) {
- DivMinBB = BasicBlock::Create(II->getContext(), "div.divmin",
- NextBB->getParent(), NextBB);
- BranchInst::Create(NextBB, DivMinBB);
- }
+ 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());
// 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(DoRelinkTrap ? TrapBB : DivMinBB, DivBB, CmpSignedOvf,
+ BranchInst::Create(DivMinBB, DivBB, CmpSignedOvf,
ChkDivMinBB->getTerminator());
ChkDivMinBB->getTerminator()->eraseFromParent();
}
// If RHS != 0, we want to check condition (2) in signed case, or proceed
// to usual division in unsigned case.
- BranchInst::Create(DoRelinkTrap ? TrapBB : DivByZeroBB,
- IsSigned ? ChkDivMinBB : DivBB, CmpDivZero,
+ BranchInst::Create(DivByZeroBB, IsSigned ? ChkDivMinBB : DivBB, CmpDivZero,
StartBB->getTerminator());
StartBB->getTerminator()->eraseFromParent();
}
// Prepare a value for the second result (flag) if it is needed.
- if (ResultNeeded[1] && !DoRelinkTrap) {
+ if (ResultNeeded[1]) {
Type *FlagTy = II->getType()->getStructElementType(1);
PHINode *FlagResPN =
PHINode::Create(FlagTy, IsSigned ? 3 : 2, "div.flag.phi",
if (ResultNeeded[1]) {
for (User *FlagU: ResultsUsers[1]) {
Instruction *FlagUInst = dyn_cast<Instruction>(FlagU);
- if (DoRelinkTrap) {
- // Replace
- // %flag = extractvalue %intrinsic.res, 1
- // br i1 %flag, label %trap.bb, label %other.bb
- // With
- // br label %other.bb
- // We've already created checks that are pointing to %trap.bb, there
- // is no need to have the same checks here.
- for (User *U: FlagUInst->users()) {
- BranchInst *TrapBranch = dyn_cast<BranchInst>(U);
- BasicBlock *CurBB = TrapBranch->getParent();
- BasicBlock *SuccessorBB = TrapBranch->getSuccessor(1);
- CurBB->getTerminator()->eraseFromParent();
- BranchInst::Create(SuccessorBB, CurBB);
- }
- } else {
- FlagUInst->replaceAllUsesWith(FlagRes);
- }
- dyn_cast<Instruction>(FlagUInst)->eraseFromParent();
+ FlagUInst->replaceAllUsesWith(FlagRes);
+ FlagUInst->eraseFromParent();
}
}
} else {
return false;
}
+ BinaryOperator *BinOp = dyn_cast<BinaryOperator>(I);
+
+ if (BinOp && (BinOp->getOpcode() == Instruction::AShr ||
+ BinOp->getOpcode() == Instruction::LShr)) {
+ ConstantInt *CI = dyn_cast<ConstantInt>(BinOp->getOperand(1));
+ if (TLI && CI && TLI->hasExtractBitsInsn())
+ return OptimizeExtractBits(BinOp, CI, *TLI);
+
+ return false;
+ }
+
if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
if (GEPI->hasAllZeroIndices()) {
/// The GEP operand must be a pointer, so must its result -> BitCast
projects / oota-llvm.git / blobdiff