CodeGenPrepare.cpp [plain text]
#define DEBUG_TYPE "codegenprepare"
#include "llvm/CodeGen/Passes.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/ValueMap.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InlineAsm.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/Pass.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/PatternMatch.h"
#include "llvm/Support/ValueHandle.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetLibraryInfo.h"
#include "llvm/Target/TargetLowering.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/BuildLibCalls.h"
#include "llvm/Transforms/Utils/BypassSlowDivision.h"
#include "llvm/Transforms/Utils/Local.h"
using namespace llvm;
using namespace llvm::PatternMatch;
STATISTIC(NumBlocksElim, "Number of blocks eliminated");
STATISTIC(NumPHIsElim, "Number of trivial PHIs eliminated");
STATISTIC(NumGEPsElim, "Number of GEPs converted to casts");
STATISTIC(NumCmpUses, "Number of uses of Cmp expressions replaced with uses of "
"sunken Cmps");
STATISTIC(NumCastUses, "Number of uses of Cast expressions replaced with uses "
"of sunken Casts");
STATISTIC(NumMemoryInsts, "Number of memory instructions whose address "
"computations were sunk");
STATISTIC(NumExtsMoved, "Number of [s|z]ext instructions combined with loads");
STATISTIC(NumExtUses, "Number of uses of [s|z]ext instructions optimized");
STATISTIC(NumRetsDup, "Number of return instructions duplicated");
STATISTIC(NumDbgValueMoved, "Number of debug value instructions moved");
STATISTIC(NumSelectsExpanded, "Number of selects turned into branches");
STATISTIC(NumAndCmpsMoved, "Number of and/cmp's pushed into branches");
static cl::opt<bool> DisableBranchOpts(
"disable-cgp-branch-opts", cl::Hidden, cl::init(false),
cl::desc("Disable branch optimizations in CodeGenPrepare"));
static cl::opt<bool> DisableSelectToBranch(
"disable-cgp-select2branch", cl::Hidden, cl::init(false),
cl::desc("Disable select to branch conversion."));
static cl::opt<bool> EnableAndCmpSinking(
"enable-andcmp-sinking", cl::Hidden, cl::init(true),
cl::desc("Enable sinkinig and/cmp into branches."));
namespace {
typedef SmallPtrSet<Instruction *, 16> SetOfInstrs;
typedef DenseMap<Instruction *, Type *> InstrToOrigTy;
class CodeGenPrepare : public FunctionPass {
const TargetMachine *TM;
const TargetLowering *TLI;
const TargetLibraryInfo *TLInfo;
DominatorTree *DT;
BasicBlock::iterator CurInstIterator;
ValueMap<Value*, Value*> SunkAddrs;
SetOfInstrs InsertedTruncsSet;
InstrToOrigTy PromotedInsts;
bool ModifiedDT;
bool OptSize;
public:
static char ID; explicit CodeGenPrepare(const TargetMachine *TM = 0)
: FunctionPass(ID), TM(TM), TLI(0) {
initializeCodeGenPreparePass(*PassRegistry::getPassRegistry());
}
bool runOnFunction(Function &F);
const char *getPassName() const { return "CodeGen Prepare"; }
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addPreserved<DominatorTreeWrapperPass>();
AU.addRequired<TargetLibraryInfo>();
}
private:
bool EliminateFallThrough(Function &F);
bool EliminateMostlyEmptyBlocks(Function &F);
bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const;
void EliminateMostlyEmptyBlock(BasicBlock *BB);
bool OptimizeBlock(BasicBlock &BB);
bool OptimizeInst(Instruction *I);
bool OptimizeMemoryInst(Instruction *I, Value *Addr, Type *AccessTy);
bool OptimizeInlineAsmInst(CallInst *CS);
bool OptimizeCallInst(CallInst *CI);
bool MoveExtToFormExtLoad(Instruction *I);
bool OptimizeExtUses(Instruction *I);
bool OptimizeSelectInst(SelectInst *SI);
bool OptimizeShuffleVectorInst(ShuffleVectorInst *SI);
bool DupRetToEnableTailCallOpts(BasicBlock *BB);
bool PlaceDbgValues(Function &F);
bool sinkAndCmp(Function &F);
};
}
char CodeGenPrepare::ID = 0;
static void *initializeCodeGenPreparePassOnce(PassRegistry &Registry) {
initializeTargetLibraryInfoPass(Registry);
PassInfo *PI = new PassInfo(
"Optimize for code generation", "codegenprepare", &CodeGenPrepare::ID,
PassInfo::NormalCtor_t(callDefaultCtor<CodeGenPrepare>), false, false,
PassInfo::TargetMachineCtor_t(callTargetMachineCtor<CodeGenPrepare>));
Registry.registerPass(*PI, true);
return PI;
}
void llvm::initializeCodeGenPreparePass(PassRegistry &Registry) {
CALL_ONCE_INITIALIZATION(initializeCodeGenPreparePassOnce)
}
FunctionPass *llvm::createCodeGenPreparePass(const TargetMachine *TM) {
return new CodeGenPrepare(TM);
}
bool CodeGenPrepare::runOnFunction(Function &F) {
bool EverMadeChange = false;
InsertedTruncsSet.clear();
PromotedInsts.clear();
ModifiedDT = false;
if (TM) TLI = TM->getTargetLowering();
TLInfo = &getAnalysis<TargetLibraryInfo>();
DominatorTreeWrapperPass *DTWP =
getAnalysisIfAvailable<DominatorTreeWrapperPass>();
DT = DTWP ? &DTWP->getDomTree() : 0;
OptSize = F.getAttributes().hasAttribute(AttributeSet::FunctionIndex,
Attribute::OptimizeForSize);
if (!OptSize && TLI && TLI->isSlowDivBypassed()) {
const DenseMap<unsigned int, unsigned int> &BypassWidths =
TLI->getBypassSlowDivWidths();
for (Function::iterator I = F.begin(); I != F.end(); I++)
EverMadeChange |= bypassSlowDivision(F, I, BypassWidths);
}
EverMadeChange |= EliminateMostlyEmptyBlocks(F);
EverMadeChange |= PlaceDbgValues(F);
if (!DisableBranchOpts)
EverMadeChange |= sinkAndCmp(F);
bool MadeChange = true;
while (MadeChange) {
MadeChange = false;
for (Function::iterator I = F.begin(); I != F.end(); ) {
BasicBlock *BB = I++;
MadeChange |= OptimizeBlock(*BB);
}
EverMadeChange |= MadeChange;
}
SunkAddrs.clear();
if (!DisableBranchOpts) {
MadeChange = false;
SmallPtrSet<BasicBlock*, 8> WorkList;
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
SmallVector<BasicBlock*, 2> Successors(succ_begin(BB), succ_end(BB));
MadeChange |= ConstantFoldTerminator(BB, true);
if (!MadeChange) continue;
for (SmallVectorImpl<BasicBlock*>::iterator
II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
if (pred_begin(*II) == pred_end(*II))
WorkList.insert(*II);
}
MadeChange |= !WorkList.empty();
while (!WorkList.empty()) {
BasicBlock *BB = *WorkList.begin();
WorkList.erase(BB);
SmallVector<BasicBlock*, 2> Successors(succ_begin(BB), succ_end(BB));
DeleteDeadBlock(BB);
for (SmallVectorImpl<BasicBlock*>::iterator
II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
if (pred_begin(*II) == pred_end(*II))
WorkList.insert(*II);
}
if (EverMadeChange || MadeChange)
MadeChange |= EliminateFallThrough(F);
if (MadeChange)
ModifiedDT = true;
EverMadeChange |= MadeChange;
}
if (ModifiedDT && DT)
DT->recalculate(F);
return EverMadeChange;
}
bool CodeGenPrepare::EliminateFallThrough(Function &F) {
bool Changed = false;
for (Function::iterator I = llvm::next(F.begin()), E = F.end(); I != E; ) {
BasicBlock *BB = I++;
BasicBlock *SinglePred = BB->getSinglePredecessor();
if (!SinglePred || SinglePred == BB || BB->hasAddressTaken()) continue;
BranchInst *Term = dyn_cast<BranchInst>(SinglePred->getTerminator());
if (Term && !Term->isConditional()) {
Changed = true;
DEBUG(dbgs() << "To merge:\n"<< *SinglePred << "\n\n\n");
bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
MergeBasicBlockIntoOnlyPred(BB, this);
if (isEntry && BB != &BB->getParent()->getEntryBlock())
BB->moveBefore(&BB->getParent()->getEntryBlock());
I = BB;
}
}
return Changed;
}
bool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) {
bool MadeChange = false;
for (Function::iterator I = llvm::next(F.begin()), E = F.end(); I != E; ) {
BasicBlock *BB = I++;
BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
if (!BI || !BI->isUnconditional())
continue;
BasicBlock::iterator BBI = BI;
if (BBI != BB->begin()) {
--BBI;
while (isa<DbgInfoIntrinsic>(BBI)) {
if (BBI == BB->begin())
break;
--BBI;
}
if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI))
continue;
}
BasicBlock *DestBB = BI->getSuccessor(0);
if (DestBB == BB)
continue;
if (!CanMergeBlocks(BB, DestBB))
continue;
EliminateMostlyEmptyBlock(BB);
MadeChange = true;
}
return MadeChange;
}
bool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB,
const BasicBlock *DestBB) const {
BasicBlock::const_iterator BBI = BB->begin();
while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) {
for (Value::const_use_iterator UI = PN->use_begin(), E = PN->use_end();
UI != E; ++UI) {
const Instruction *User = cast<Instruction>(*UI);
if (User->getParent() != DestBB || !isa<PHINode>(User))
return false;
if (User->getParent() == DestBB) {
if (const PHINode *UPN = dyn_cast<PHINode>(User))
for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) {
Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I));
if (Insn && Insn->getParent() == BB &&
Insn->getParent() != UPN->getIncomingBlock(I))
return false;
}
}
}
}
const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin());
if (!DestBBPN) return true;
SmallPtrSet<const BasicBlock*, 16> BBPreds;
if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) {
for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
BBPreds.insert(BBPN->getIncomingBlock(i));
} else {
BBPreds.insert(pred_begin(BB), pred_end(BB));
}
for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) {
BasicBlock *Pred = DestBBPN->getIncomingBlock(i);
if (BBPreds.count(Pred)) { BBI = DestBB->begin();
while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) {
const Value *V1 = PN->getIncomingValueForBlock(Pred);
const Value *V2 = PN->getIncomingValueForBlock(BB);
if (const PHINode *V2PN = dyn_cast<PHINode>(V2))
if (V2PN->getParent() == BB)
V2 = V2PN->getIncomingValueForBlock(Pred);
if (V1 != V2) return false;
}
}
}
return true;
}
void CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) {
BranchInst *BI = cast<BranchInst>(BB->getTerminator());
BasicBlock *DestBB = BI->getSuccessor(0);
DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB);
if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) {
if (SinglePred != DestBB) {
bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
MergeBasicBlockIntoOnlyPred(DestBB, this);
if (isEntry && BB != &BB->getParent()->getEntryBlock())
BB->moveBefore(&BB->getParent()->getEntryBlock());
DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
return;
}
}
PHINode *PN;
for (BasicBlock::iterator BBI = DestBB->begin();
(PN = dyn_cast<PHINode>(BBI)); ++BBI) {
Value *InVal = PN->removeIncomingValue(BB, false);
PHINode *InValPhi = dyn_cast<PHINode>(InVal);
if (InValPhi && InValPhi->getParent() == BB) {
for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i)
PN->addIncoming(InValPhi->getIncomingValue(i),
InValPhi->getIncomingBlock(i));
} else {
if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) {
for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
PN->addIncoming(InVal, BBPN->getIncomingBlock(i));
} else {
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
PN->addIncoming(InVal, *PI);
}
}
}
BB->replaceAllUsesWith(DestBB);
if (DT && !ModifiedDT) {
BasicBlock *BBIDom = DT->getNode(BB)->getIDom()->getBlock();
BasicBlock *DestBBIDom = DT->getNode(DestBB)->getIDom()->getBlock();
BasicBlock *NewIDom = DT->findNearestCommonDominator(BBIDom, DestBBIDom);
DT->changeImmediateDominator(DestBB, NewIDom);
DT->eraseNode(BB);
}
BB->eraseFromParent();
++NumBlocksElim;
DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
}
static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){
EVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType());
EVT DstVT = TLI.getValueType(CI->getType());
if (SrcVT.isInteger() != DstVT.isInteger())
return false;
if (SrcVT.bitsLT(DstVT)) return false;
if (TLI.getTypeAction(CI->getContext(), SrcVT) ==
TargetLowering::TypePromoteInteger)
SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT);
if (TLI.getTypeAction(CI->getContext(), DstVT) ==
TargetLowering::TypePromoteInteger)
DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT);
if (SrcVT != DstVT)
return false;
BasicBlock *DefBB = CI->getParent();
DenseMap<BasicBlock*, CastInst*> InsertedCasts;
bool MadeChange = false;
for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end();
UI != E; ) {
Use &TheUse = UI.getUse();
Instruction *User = cast<Instruction>(*UI);
BasicBlock *UserBB = User->getParent();
if (PHINode *PN = dyn_cast<PHINode>(User)) {
UserBB = PN->getIncomingBlock(UI);
}
++UI;
if (UserBB == DefBB) continue;
CastInst *&InsertedCast = InsertedCasts[UserBB];
if (!InsertedCast) {
BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
InsertedCast =
CastInst::Create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "",
InsertPt);
MadeChange = true;
}
TheUse = InsertedCast;
++NumCastUses;
}
if (CI->use_empty()) {
CI->eraseFromParent();
MadeChange = true;
}
return MadeChange;
}
static bool OptimizeCmpExpression(CmpInst *CI) {
BasicBlock *DefBB = CI->getParent();
DenseMap<BasicBlock*, CmpInst*> InsertedCmps;
bool MadeChange = false;
for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end();
UI != E; ) {
Use &TheUse = UI.getUse();
Instruction *User = cast<Instruction>(*UI);
++UI;
if (isa<PHINode>(User))
continue;
BasicBlock *UserBB = User->getParent();
if (UserBB == DefBB) continue;
CmpInst *&InsertedCmp = InsertedCmps[UserBB];
if (!InsertedCmp) {
BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
InsertedCmp =
CmpInst::Create(CI->getOpcode(),
CI->getPredicate(), CI->getOperand(0),
CI->getOperand(1), "", InsertPt);
MadeChange = true;
}
TheUse = InsertedCmp;
++NumCmpUses;
}
if (CI->use_empty())
CI->eraseFromParent();
return MadeChange;
}
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;
}
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::use_iterator TruncUI = TruncI->use_begin(),
TruncE = TruncI->use_end();
TruncUI != TruncE;) {
Use &TruncTheUse = TruncUI.getUse();
Instruction *TruncUser = cast<Instruction>(*TruncUI);
++TruncUI;
int ISDOpcode = TLI.InstructionOpcodeToISD(TruncUser->getOpcode());
if (!ISDOpcode)
continue;
if (TLI.isOperationLegalOrCustom(ISDOpcode,
EVT::getEVT(TruncUser->getType())))
continue;
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();
if (ShiftI->getOpcode() == Instruction::AShr)
InsertedShift =
BinaryOperator::CreateAShr(ShiftI->getOperand(0), CI, "", InsertPt);
else
InsertedShift =
BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI, "", InsertPt);
BasicBlock::iterator TruncInsertPt = TruncUserBB->getFirstInsertionPt();
TruncInsertPt++;
InsertedTrunc = CastInst::Create(TruncI->getOpcode(), InsertedShift,
TruncI->getType(), "", TruncInsertPt);
MadeChange = true;
TruncTheUse = InsertedTrunc;
}
}
return MadeChange;
}
static bool OptimizeExtractBits(BinaryOperator *ShiftI, ConstantInt *CI,
const TargetLowering &TLI) {
BasicBlock *DefBB = ShiftI->getParent();
DenseMap<BasicBlock *, BinaryOperator *> InsertedShifts;
bool shiftIsLegal = TLI.isTypeLegal(TLI.getValueType(ShiftI->getType()));
bool MadeChange = false;
for (Value::use_iterator UI = ShiftI->use_begin(), E = ShiftI->use_end();
UI != E;) {
Use &TheUse = UI.getUse();
Instruction *User = cast<Instruction>(*UI);
++UI;
if (isa<PHINode>(User))
continue;
if (!isExtractBitsCandidateUse(User))
continue;
BasicBlock *UserBB = User->getParent();
if (UserBB == DefBB) {
if (isa<TruncInst>(User) && shiftIsLegal
&& (!TLI.isTypeLegal(TLI.getValueType(User->getType()))))
MadeChange =
SinkShiftAndTruncate(ShiftI, User, CI, InsertedShifts, TLI);
continue;
}
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;
}
TheUse = InsertedShift;
}
if (ShiftI->use_empty())
ShiftI->eraseFromParent();
return MadeChange;
}
namespace {
class CodeGenPrepareFortifiedLibCalls : public SimplifyFortifiedLibCalls {
protected:
void replaceCall(Value *With) {
CI->replaceAllUsesWith(With);
CI->eraseFromParent();
}
bool isFoldable(unsigned SizeCIOp, unsigned, bool) const {
if (ConstantInt *SizeCI =
dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp)))
return SizeCI->isAllOnesValue();
return false;
}
};
}
bool CodeGenPrepare::OptimizeCallInst(CallInst *CI) {
BasicBlock *BB = CI->getParent();
if (TLI && isa<InlineAsm>(CI->getCalledValue())) {
if (TLI->ExpandInlineAsm(CI)) {
CurInstIterator = BB->begin();
SunkAddrs.clear();
return true;
}
if (OptimizeInlineAsmInst(CI))
return true;
}
IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI);
if (II && II->getIntrinsicID() == Intrinsic::objectsize) {
bool Min = (cast<ConstantInt>(II->getArgOperand(1))->getZExtValue() == 1);
Type *ReturnTy = CI->getType();
Constant *RetVal = ConstantInt::get(ReturnTy, Min ? 0 : -1ULL);
WeakVH IterHandle(CurInstIterator);
replaceAndRecursivelySimplify(CI, RetVal, TLI ? TLI->getDataLayout() : 0,
TLInfo, ModifiedDT ? 0 : DT);
if (IterHandle != CurInstIterator) {
CurInstIterator = BB->begin();
SunkAddrs.clear();
}
return true;
}
if (II && TLI) {
SmallVector<Value*, 2> PtrOps;
Type *AccessTy;
if (TLI->GetAddrModeArguments(II, PtrOps, AccessTy))
while (!PtrOps.empty())
if (OptimizeMemoryInst(II, PtrOps.pop_back_val(), AccessTy))
return true;
}
if (CI->getCalledFunction() == 0) return false;
const DataLayout *TD = TLI ? TLI->getDataLayout() : 0;
if (!TD) return false;
CodeGenPrepareFortifiedLibCalls Simplifier;
return Simplifier.fold(CI, TD, TLInfo);
}
bool CodeGenPrepare::DupRetToEnableTailCallOpts(BasicBlock *BB) {
if (!TLI)
return false;
ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator());
if (!RI)
return false;
PHINode *PN = 0;
BitCastInst *BCI = 0;
Value *V = RI->getReturnValue();
if (V) {
BCI = dyn_cast<BitCastInst>(V);
if (BCI)
V = BCI->getOperand(0);
PN = dyn_cast<PHINode>(V);
if (!PN)
return false;
}
if (PN && PN->getParent() != BB)
return false;
const Function *F = BB->getParent();
AttributeSet CallerAttrs = F->getAttributes();
if (CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::ZExt) ||
CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::SExt))
return false;
if (PN) {
BasicBlock::iterator BI = BB->begin();
do { ++BI; } while (isa<DbgInfoIntrinsic>(BI));
if (&*BI == BCI)
++BI;
if (&*BI != RI)
return false;
} else {
BasicBlock::iterator BI = BB->begin();
while (isa<DbgInfoIntrinsic>(BI)) ++BI;
if (&*BI != RI)
return false;
}
SmallVector<CallInst*, 4> TailCalls;
if (PN) {
for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) {
CallInst *CI = dyn_cast<CallInst>(PN->getIncomingValue(I));
if (CI && CI->hasOneUse() && CI->getParent() == PN->getIncomingBlock(I) &&
TLI->mayBeEmittedAsTailCall(CI))
TailCalls.push_back(CI);
}
} else {
SmallPtrSet<BasicBlock*, 4> VisitedBBs;
for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
if (!VisitedBBs.insert(*PI))
continue;
BasicBlock::InstListType &InstList = (*PI)->getInstList();
BasicBlock::InstListType::reverse_iterator RI = InstList.rbegin();
BasicBlock::InstListType::reverse_iterator RE = InstList.rend();
do { ++RI; } while (RI != RE && isa<DbgInfoIntrinsic>(&*RI));
if (RI == RE)
continue;
CallInst *CI = dyn_cast<CallInst>(&*RI);
if (CI && CI->use_empty() && TLI->mayBeEmittedAsTailCall(CI))
TailCalls.push_back(CI);
}
}
bool Changed = false;
for (unsigned i = 0, e = TailCalls.size(); i != e; ++i) {
CallInst *CI = TailCalls[i];
CallSite CS(CI);
AttributeSet CalleeAttrs = CS.getAttributes();
if (AttrBuilder(CalleeAttrs, AttributeSet::ReturnIndex).
removeAttribute(Attribute::NoAlias) !=
AttrBuilder(CalleeAttrs, AttributeSet::ReturnIndex).
removeAttribute(Attribute::NoAlias))
continue;
BasicBlock *CallBB = CI->getParent();
BranchInst *BI = dyn_cast<BranchInst>(CallBB->getTerminator());
if (!BI || !BI->isUnconditional() || BI->getSuccessor(0) != BB)
continue;
(void)FoldReturnIntoUncondBranch(RI, BB, CallBB);
ModifiedDT = Changed = true;
++NumRetsDup;
}
if (Changed && !BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB))
BB->eraseFromParent();
return Changed;
}
namespace {
struct ExtAddrMode : public TargetLowering::AddrMode {
Value *BaseReg;
Value *ScaledReg;
ExtAddrMode() : BaseReg(0), ScaledReg(0) {}
void print(raw_ostream &OS) const;
void dump() const;
bool operator==(const ExtAddrMode& O) const {
return (BaseReg == O.BaseReg) && (ScaledReg == O.ScaledReg) &&
(BaseGV == O.BaseGV) && (BaseOffs == O.BaseOffs) &&
(HasBaseReg == O.HasBaseReg) && (Scale == O.Scale);
}
};
#ifndef NDEBUG
static inline raw_ostream &operator<<(raw_ostream &OS, const ExtAddrMode &AM) {
AM.print(OS);
return OS;
}
#endif
void ExtAddrMode::print(raw_ostream &OS) const {
bool NeedPlus = false;
OS << "[";
if (BaseGV) {
OS << (NeedPlus ? " + " : "")
<< "GV:";
BaseGV->printAsOperand(OS, false);
NeedPlus = true;
}
if (BaseOffs)
OS << (NeedPlus ? " + " : "") << BaseOffs, NeedPlus = true;
if (BaseReg) {
OS << (NeedPlus ? " + " : "")
<< "Base:";
BaseReg->printAsOperand(OS, false);
NeedPlus = true;
}
if (Scale) {
OS << (NeedPlus ? " + " : "")
<< Scale << "*";
ScaledReg->printAsOperand(OS, false);
}
OS << ']';
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void ExtAddrMode::dump() const {
print(dbgs());
dbgs() << '\n';
}
#endif
class TypePromotionTransaction {
class TypePromotionAction {
protected:
Instruction *Inst;
public:
TypePromotionAction(Instruction *Inst) : Inst(Inst) {}
virtual ~TypePromotionAction() {}
virtual void undo() = 0;
virtual void commit() {
}
};
class InsertionHandler {
union {
Instruction *PrevInst;
BasicBlock *BB;
} Point;
bool HasPrevInstruction;
public:
InsertionHandler(Instruction *Inst) {
BasicBlock::iterator It = Inst;
HasPrevInstruction = (It != (Inst->getParent()->begin()));
if (HasPrevInstruction)
Point.PrevInst = --It;
else
Point.BB = Inst->getParent();
}
void insert(Instruction *Inst) {
if (HasPrevInstruction) {
if (Inst->getParent())
Inst->removeFromParent();
Inst->insertAfter(Point.PrevInst);
} else {
Instruction *Position = Point.BB->getFirstInsertionPt();
if (Inst->getParent())
Inst->moveBefore(Position);
else
Inst->insertBefore(Position);
}
}
};
class InstructionMoveBefore : public TypePromotionAction {
InsertionHandler Position;
public:
InstructionMoveBefore(Instruction *Inst, Instruction *Before)
: TypePromotionAction(Inst), Position(Inst) {
DEBUG(dbgs() << "Do: move: " << *Inst << "\nbefore: " << *Before << "\n");
Inst->moveBefore(Before);
}
void undo() {
DEBUG(dbgs() << "Undo: moveBefore: " << *Inst << "\n");
Position.insert(Inst);
}
};
class OperandSetter : public TypePromotionAction {
Value *Origin;
unsigned Idx;
public:
OperandSetter(Instruction *Inst, unsigned Idx, Value *NewVal)
: TypePromotionAction(Inst), Idx(Idx) {
DEBUG(dbgs() << "Do: setOperand: " << Idx << "\n"
<< "for:" << *Inst << "\n"
<< "with:" << *NewVal << "\n");
Origin = Inst->getOperand(Idx);
Inst->setOperand(Idx, NewVal);
}
void undo() {
DEBUG(dbgs() << "Undo: setOperand:" << Idx << "\n"
<< "for: " << *Inst << "\n"
<< "with: " << *Origin << "\n");
Inst->setOperand(Idx, Origin);
}
};
class OperandsHider : public TypePromotionAction {
SmallVector<Value *, 4> OriginalValues;
public:
OperandsHider(Instruction *Inst) : TypePromotionAction(Inst) {
DEBUG(dbgs() << "Do: OperandsHider: " << *Inst << "\n");
unsigned NumOpnds = Inst->getNumOperands();
OriginalValues.reserve(NumOpnds);
for (unsigned It = 0; It < NumOpnds; ++It) {
Value *Val = Inst->getOperand(It);
OriginalValues.push_back(Val);
Inst->setOperand(It, UndefValue::get(Val->getType()));
}
}
void undo() {
DEBUG(dbgs() << "Undo: OperandsHider: " << *Inst << "\n");
for (unsigned It = 0, EndIt = OriginalValues.size(); It != EndIt; ++It)
Inst->setOperand(It, OriginalValues[It]);
}
};
class TruncBuilder : public TypePromotionAction {
public:
TruncBuilder(Instruction *Opnd, Type *Ty) : TypePromotionAction(Opnd) {
IRBuilder<> Builder(Opnd);
Inst = cast<Instruction>(Builder.CreateTrunc(Opnd, Ty, "promoted"));
DEBUG(dbgs() << "Do: TruncBuilder: " << *Inst << "\n");
}
Instruction *getBuiltInstruction() { return Inst; }
void undo() {
DEBUG(dbgs() << "Undo: TruncBuilder: " << *Inst << "\n");
Inst->eraseFromParent();
}
};
class SExtBuilder : public TypePromotionAction {
public:
SExtBuilder(Instruction *InsertPt, Value *Opnd, Type *Ty)
: TypePromotionAction(Inst) {
IRBuilder<> Builder(InsertPt);
Inst = cast<Instruction>(Builder.CreateSExt(Opnd, Ty, "promoted"));
DEBUG(dbgs() << "Do: SExtBuilder: " << *Inst << "\n");
}
Instruction *getBuiltInstruction() { return Inst; }
void undo() {
DEBUG(dbgs() << "Undo: SExtBuilder: " << *Inst << "\n");
Inst->eraseFromParent();
}
};
class TypeMutator : public TypePromotionAction {
Type *OrigTy;
public:
TypeMutator(Instruction *Inst, Type *NewTy)
: TypePromotionAction(Inst), OrigTy(Inst->getType()) {
DEBUG(dbgs() << "Do: MutateType: " << *Inst << " with " << *NewTy
<< "\n");
Inst->mutateType(NewTy);
}
void undo() {
DEBUG(dbgs() << "Undo: MutateType: " << *Inst << " with " << *OrigTy
<< "\n");
Inst->mutateType(OrigTy);
}
};
class UsesReplacer : public TypePromotionAction {
struct InstructionAndIdx {
Instruction *Inst;
unsigned Idx;
InstructionAndIdx(Instruction *Inst, unsigned Idx)
: Inst(Inst), Idx(Idx) {}
};
SmallVector<InstructionAndIdx, 4> OriginalUses;
typedef SmallVectorImpl<InstructionAndIdx>::iterator use_iterator;
public:
UsesReplacer(Instruction *Inst, Value *New) : TypePromotionAction(Inst) {
DEBUG(dbgs() << "Do: UsersReplacer: " << *Inst << " with " << *New
<< "\n");
for (Value::use_iterator UseIt = Inst->use_begin(),
EndIt = Inst->use_end();
UseIt != EndIt; ++UseIt) {
Instruction *Use = cast<Instruction>(*UseIt);
OriginalUses.push_back(InstructionAndIdx(Use, UseIt.getOperandNo()));
}
Inst->replaceAllUsesWith(New);
}
void undo() {
DEBUG(dbgs() << "Undo: UsersReplacer: " << *Inst << "\n");
for (use_iterator UseIt = OriginalUses.begin(),
EndIt = OriginalUses.end();
UseIt != EndIt; ++UseIt) {
UseIt->Inst->setOperand(UseIt->Idx, Inst);
}
}
};
class InstructionRemover : public TypePromotionAction {
InsertionHandler Inserter;
OperandsHider Hider;
UsesReplacer *Replacer;
public:
InstructionRemover(Instruction *Inst, Value *New = NULL)
: TypePromotionAction(Inst), Inserter(Inst), Hider(Inst),
Replacer(NULL) {
if (New)
Replacer = new UsesReplacer(Inst, New);
DEBUG(dbgs() << "Do: InstructionRemover: " << *Inst << "\n");
Inst->removeFromParent();
}
~InstructionRemover() { delete Replacer; }
void commit() { delete Inst; }
void undo() {
DEBUG(dbgs() << "Undo: InstructionRemover: " << *Inst << "\n");
Inserter.insert(Inst);
if (Replacer)
Replacer->undo();
Hider.undo();
}
};
public:
typedef const TypePromotionAction *ConstRestorationPt;
void commit();
void rollback(ConstRestorationPt Point);
ConstRestorationPt getRestorationPoint() const;
void setOperand(Instruction *Inst, unsigned Idx, Value *NewVal);
void eraseInstruction(Instruction *Inst, Value *NewVal = NULL);
void replaceAllUsesWith(Instruction *Inst, Value *New);
void mutateType(Instruction *Inst, Type *NewTy);
Instruction *createTrunc(Instruction *Opnd, Type *Ty);
Instruction *createSExt(Instruction *Inst, Value *Opnd, Type *Ty);
void moveBefore(Instruction *Inst, Instruction *Before);
~TypePromotionTransaction();
private:
SmallVector<TypePromotionAction *, 16> Actions;
typedef SmallVectorImpl<TypePromotionAction *>::iterator CommitPt;
};
void TypePromotionTransaction::setOperand(Instruction *Inst, unsigned Idx,
Value *NewVal) {
Actions.push_back(
new TypePromotionTransaction::OperandSetter(Inst, Idx, NewVal));
}
void TypePromotionTransaction::eraseInstruction(Instruction *Inst,
Value *NewVal) {
Actions.push_back(
new TypePromotionTransaction::InstructionRemover(Inst, NewVal));
}
void TypePromotionTransaction::replaceAllUsesWith(Instruction *Inst,
Value *New) {
Actions.push_back(new TypePromotionTransaction::UsesReplacer(Inst, New));
}
void TypePromotionTransaction::mutateType(Instruction *Inst, Type *NewTy) {
Actions.push_back(new TypePromotionTransaction::TypeMutator(Inst, NewTy));
}
Instruction *TypePromotionTransaction::createTrunc(Instruction *Opnd,
Type *Ty) {
TruncBuilder *TB = new TruncBuilder(Opnd, Ty);
Actions.push_back(TB);
return TB->getBuiltInstruction();
}
Instruction *TypePromotionTransaction::createSExt(Instruction *Inst,
Value *Opnd, Type *Ty) {
SExtBuilder *SB = new SExtBuilder(Inst, Opnd, Ty);
Actions.push_back(SB);
return SB->getBuiltInstruction();
}
void TypePromotionTransaction::moveBefore(Instruction *Inst,
Instruction *Before) {
Actions.push_back(
new TypePromotionTransaction::InstructionMoveBefore(Inst, Before));
}
TypePromotionTransaction::ConstRestorationPt
TypePromotionTransaction::getRestorationPoint() const {
return Actions.rbegin() != Actions.rend() ? *Actions.rbegin() : NULL;
}
void TypePromotionTransaction::commit() {
for (CommitPt It = Actions.begin(), EndIt = Actions.end(); It != EndIt;
++It) {
(*It)->commit();
delete *It;
}
Actions.clear();
}
void TypePromotionTransaction::rollback(
TypePromotionTransaction::ConstRestorationPt Point) {
while (!Actions.empty() && Point != (*Actions.rbegin())) {
TypePromotionAction *Curr = Actions.pop_back_val();
Curr->undo();
delete Curr;
}
}
TypePromotionTransaction::~TypePromotionTransaction() {
for (CommitPt It = Actions.begin(), EndIt = Actions.end(); It != EndIt; ++It)
delete *It;
Actions.clear();
}
class AddressingModeMatcher {
SmallVectorImpl<Instruction*> &AddrModeInsts;
const TargetLowering &TLI;
Type *AccessTy;
Instruction *MemoryInst;
ExtAddrMode &AddrMode;
const SetOfInstrs &InsertedTruncs;
InstrToOrigTy &PromotedInsts;
TypePromotionTransaction &TPT;
bool IgnoreProfitability;
AddressingModeMatcher(SmallVectorImpl<Instruction*> &AMI,
const TargetLowering &T, Type *AT,
Instruction *MI, ExtAddrMode &AM,
const SetOfInstrs &InsertedTruncs,
InstrToOrigTy &PromotedInsts,
TypePromotionTransaction &TPT)
: AddrModeInsts(AMI), TLI(T), AccessTy(AT), MemoryInst(MI), AddrMode(AM),
InsertedTruncs(InsertedTruncs), PromotedInsts(PromotedInsts), TPT(TPT) {
IgnoreProfitability = false;
}
public:
static ExtAddrMode Match(Value *V, Type *AccessTy,
Instruction *MemoryInst,
SmallVectorImpl<Instruction*> &AddrModeInsts,
const TargetLowering &TLI,
const SetOfInstrs &InsertedTruncs,
InstrToOrigTy &PromotedInsts,
TypePromotionTransaction &TPT) {
ExtAddrMode Result;
bool Success = AddressingModeMatcher(AddrModeInsts, TLI, AccessTy,
MemoryInst, Result, InsertedTruncs,
PromotedInsts, TPT).MatchAddr(V, 0);
(void)Success; assert(Success && "Couldn't select *anything*?");
return Result;
}
private:
bool MatchScaledValue(Value *ScaleReg, int64_t Scale, unsigned Depth);
bool MatchAddr(Value *V, unsigned Depth);
bool MatchOperationAddr(User *Operation, unsigned Opcode, unsigned Depth,
bool *MovedAway = NULL);
bool IsProfitableToFoldIntoAddressingMode(Instruction *I,
ExtAddrMode &AMBefore,
ExtAddrMode &AMAfter);
bool ValueAlreadyLiveAtInst(Value *Val, Value *KnownLive1, Value *KnownLive2);
bool IsPromotionProfitable(unsigned MatchedSize, unsigned SizeWithPromotion,
Value *PromotedOperand) const;
};
bool AddressingModeMatcher::MatchScaledValue(Value *ScaleReg, int64_t Scale,
unsigned Depth) {
if (Scale == 1)
return MatchAddr(ScaleReg, Depth);
if (Scale == 0)
return true;
if (AddrMode.Scale != 0 && AddrMode.ScaledReg != ScaleReg)
return false;
ExtAddrMode TestAddrMode = AddrMode;
TestAddrMode.Scale += Scale;
TestAddrMode.ScaledReg = ScaleReg;
if (!TLI.isLegalAddressingMode(TestAddrMode, AccessTy))
return false;
AddrMode = TestAddrMode;
ConstantInt *CI = 0; Value *AddLHS = 0;
if (isa<Instruction>(ScaleReg) && match(ScaleReg, m_Add(m_Value(AddLHS), m_ConstantInt(CI)))) {
TestAddrMode.ScaledReg = AddLHS;
TestAddrMode.BaseOffs += CI->getSExtValue()*TestAddrMode.Scale;
if (TLI.isLegalAddressingMode(TestAddrMode, AccessTy)) {
AddrModeInsts.push_back(cast<Instruction>(ScaleReg));
AddrMode = TestAddrMode;
return true;
}
}
return true;
}
static bool MightBeFoldableInst(Instruction *I) {
switch (I->getOpcode()) {
case Instruction::BitCast:
if (I->getType() == I->getOperand(0)->getType())
return false;
return I->getType()->isPointerTy() || I->getType()->isIntegerTy();
case Instruction::PtrToInt:
return true;
case Instruction::IntToPtr:
return true;
case Instruction::Add:
return true;
case Instruction::Mul:
case Instruction::Shl:
return isa<ConstantInt>(I->getOperand(1));
case Instruction::GetElementPtr:
return true;
default:
return false;
}
}
class TypePromotionHelper {
static bool canGetThrough(const Instruction *Inst, Type *ConsideredSExtType,
const InstrToOrigTy &PromotedInsts);
static bool shouldSExtOperand(const Instruction *Inst, int OpIdx) {
if (isa<SelectInst>(Inst) && OpIdx == 0)
return false;
return true;
}
static Value *promoteOperandForTruncAndSExt(Instruction *SExt,
TypePromotionTransaction &TPT,
InstrToOrigTy &PromotedInsts,
unsigned &CreatedInsts);
static Value *promoteOperandForOther(Instruction *SExt,
TypePromotionTransaction &TPT,
InstrToOrigTy &PromotedInsts,
unsigned &CreatedInsts);
public:
typedef Value *(*Action)(Instruction *SExt, TypePromotionTransaction &TPT,
InstrToOrigTy &PromotedInsts,
unsigned &CreatedInsts);
static Action getAction(Instruction *SExt, const SetOfInstrs &InsertedTruncs,
const TargetLowering &TLI,
const InstrToOrigTy &PromotedInsts);
};
bool TypePromotionHelper::canGetThrough(const Instruction *Inst,
Type *ConsideredSExtType,
const InstrToOrigTy &PromotedInsts) {
if (isa<SExtInst>(Inst))
return true;
const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst);
if (BinOp && isa<OverflowingBinaryOperator>(BinOp) &&
(BinOp->hasNoUnsignedWrap() || BinOp->hasNoSignedWrap()))
return true;
if (!isa<TruncInst>(Inst))
return false;
Value *OpndVal = Inst->getOperand(0);
if (OpndVal->getType()->getIntegerBitWidth() >
ConsideredSExtType->getIntegerBitWidth())
return false;
Instruction *Opnd = dyn_cast<Instruction>(OpndVal);
if (!Opnd)
return false;
const Type *OpndType;
InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd);
if (It != PromotedInsts.end())
OpndType = It->second;
else if (isa<SExtInst>(Opnd))
OpndType = cast<Instruction>(Opnd)->getOperand(0)->getType();
else
return false;
if (Inst->getType()->getIntegerBitWidth() >= OpndType->getIntegerBitWidth())
return true;
return false;
}
TypePromotionHelper::Action TypePromotionHelper::getAction(
Instruction *SExt, const SetOfInstrs &InsertedTruncs,
const TargetLowering &TLI, const InstrToOrigTy &PromotedInsts) {
Instruction *SExtOpnd = dyn_cast<Instruction>(SExt->getOperand(0));
Type *SExtTy = SExt->getType();
if (!SExtOpnd || !canGetThrough(SExtOpnd, SExtTy, PromotedInsts))
return NULL;
if (isa<TruncInst>(SExtOpnd) && InsertedTruncs.count(SExtOpnd))
return NULL;
if (isa<SExtInst>(SExtOpnd) || isa<TruncInst>(SExtOpnd))
return promoteOperandForTruncAndSExt;
if (!SExtOpnd->hasOneUse() &&
!TLI.isTruncateFree(SExtTy, SExtOpnd->getType()))
return NULL;
return promoteOperandForOther;
}
Value *TypePromotionHelper::promoteOperandForTruncAndSExt(
llvm::Instruction *SExt, TypePromotionTransaction &TPT,
InstrToOrigTy &PromotedInsts, unsigned &CreatedInsts) {
Instruction *SExtOpnd = cast<Instruction>(SExt->getOperand(0));
TPT.setOperand(SExt, 0, SExtOpnd->getOperand(0));
CreatedInsts = 0;
if (SExtOpnd->use_empty())
TPT.eraseInstruction(SExtOpnd);
if (SExt->getType() != SExt->getOperand(0)->getType())
return SExt;
Value *NextVal = SExt->getOperand(0);
TPT.eraseInstruction(SExt, NextVal);
return NextVal;
}
Value *
TypePromotionHelper::promoteOperandForOther(Instruction *SExt,
TypePromotionTransaction &TPT,
InstrToOrigTy &PromotedInsts,
unsigned &CreatedInsts) {
Instruction *SExtOpnd = cast<Instruction>(SExt->getOperand(0));
CreatedInsts = 0;
if (!SExtOpnd->hasOneUse()) {
Instruction *Trunc = TPT.createTrunc(SExt, SExtOpnd->getType());
Trunc->removeFromParent();
Trunc->insertAfter(SExtOpnd);
TPT.replaceAllUsesWith(SExtOpnd, Trunc);
TPT.setOperand(SExt, 0, SExtOpnd);
}
PromotedInsts.insert(
std::pair<Instruction *, Type *>(SExtOpnd, SExtOpnd->getType()));
TPT.mutateType(SExtOpnd, SExt->getType());
TPT.replaceAllUsesWith(SExt, SExtOpnd);
Instruction *SExtForOpnd = SExt;
DEBUG(dbgs() << "Propagate SExt to operands\n");
for (int OpIdx = 0, EndOpIdx = SExtOpnd->getNumOperands(); OpIdx != EndOpIdx;
++OpIdx) {
DEBUG(dbgs() << "Operand:\n" << *(SExtOpnd->getOperand(OpIdx)) << '\n');
if (SExtOpnd->getOperand(OpIdx)->getType() == SExt->getType() ||
!shouldSExtOperand(SExtOpnd, OpIdx)) {
DEBUG(dbgs() << "No need to propagate\n");
continue;
}
Value *Opnd = SExtOpnd->getOperand(OpIdx);
if (const ConstantInt *Cst = dyn_cast<ConstantInt>(Opnd)) {
DEBUG(dbgs() << "Statically sign extend\n");
TPT.setOperand(
SExtOpnd, OpIdx,
ConstantInt::getSigned(SExt->getType(), Cst->getSExtValue()));
continue;
}
if (isa<UndefValue>(Opnd)) {
DEBUG(dbgs() << "Statically sign extend\n");
TPT.setOperand(SExtOpnd, OpIdx, UndefValue::get(SExt->getType()));
continue;
}
if (!SExtForOpnd) {
DEBUG(dbgs() << "More operands to sext\n");
SExtForOpnd = TPT.createSExt(SExt, Opnd, SExt->getType());
++CreatedInsts;
}
TPT.setOperand(SExtForOpnd, 0, Opnd);
TPT.moveBefore(SExtForOpnd, SExtOpnd);
TPT.setOperand(SExtOpnd, OpIdx, SExtForOpnd);
SExtForOpnd = NULL;
}
if (SExtForOpnd == SExt) {
DEBUG(dbgs() << "Sign extension is useless now\n");
TPT.eraseInstruction(SExt);
}
return SExtOpnd;
}
bool
AddressingModeMatcher::IsPromotionProfitable(unsigned MatchedSize,
unsigned SizeWithPromotion,
Value *PromotedOperand) const {
if (MatchedSize < SizeWithPromotion)
return false;
if (MatchedSize > SizeWithPromotion)
return true;
Instruction *PromotedInst = dyn_cast<Instruction>(PromotedOperand);
if (!PromotedInst)
return false;
int ISDOpcode = TLI.InstructionOpcodeToISD(PromotedInst->getOpcode());
if (!ISDOpcode)
return true;
return TLI.isOperationLegalOrCustom(ISDOpcode,
EVT::getEVT(PromotedInst->getType()));
}
bool AddressingModeMatcher::MatchOperationAddr(User *AddrInst, unsigned Opcode,
unsigned Depth,
bool *MovedAway) {
if (Depth >= 5) return false;
if (MovedAway)
*MovedAway = false;
switch (Opcode) {
case Instruction::PtrToInt:
return MatchAddr(AddrInst->getOperand(0), Depth);
case Instruction::IntToPtr:
if (TLI.getValueType(AddrInst->getOperand(0)->getType()) ==
TLI.getPointerTy(AddrInst->getType()->getPointerAddressSpace()))
return MatchAddr(AddrInst->getOperand(0), Depth);
return false;
case Instruction::BitCast:
if ((AddrInst->getOperand(0)->getType()->isPointerTy() ||
AddrInst->getOperand(0)->getType()->isIntegerTy()) &&
AddrInst->getOperand(0)->getType() != AddrInst->getType())
return MatchAddr(AddrInst->getOperand(0), Depth);
return false;
case Instruction::Add: {
ExtAddrMode BackupAddrMode = AddrMode;
unsigned OldSize = AddrModeInsts.size();
TypePromotionTransaction::ConstRestorationPt LastKnownGood =
TPT.getRestorationPoint();
if (MatchAddr(AddrInst->getOperand(1), Depth+1) &&
MatchAddr(AddrInst->getOperand(0), Depth+1))
return true;
AddrMode = BackupAddrMode;
AddrModeInsts.resize(OldSize);
TPT.rollback(LastKnownGood);
if (MatchAddr(AddrInst->getOperand(0), Depth+1) &&
MatchAddr(AddrInst->getOperand(1), Depth+1))
return true;
AddrMode = BackupAddrMode;
AddrModeInsts.resize(OldSize);
TPT.rollback(LastKnownGood);
break;
}
case Instruction::Mul:
case Instruction::Shl: {
ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1));
if (!RHS) return false;
int64_t Scale = RHS->getSExtValue();
if (Opcode == Instruction::Shl)
Scale = 1LL << Scale;
return MatchScaledValue(AddrInst->getOperand(0), Scale, Depth);
}
case Instruction::GetElementPtr: {
int VariableOperand = -1;
unsigned VariableScale = 0;
int64_t ConstantOffset = 0;
const DataLayout *TD = TLI.getDataLayout();
gep_type_iterator GTI = gep_type_begin(AddrInst);
for (unsigned i = 1, e = AddrInst->getNumOperands(); i != e; ++i, ++GTI) {
if (StructType *STy = dyn_cast<StructType>(*GTI)) {
const StructLayout *SL = TD->getStructLayout(STy);
unsigned Idx =
cast<ConstantInt>(AddrInst->getOperand(i))->getZExtValue();
ConstantOffset += SL->getElementOffset(Idx);
} else {
uint64_t TypeSize = TD->getTypeAllocSize(GTI.getIndexedType());
if (ConstantInt *CI = dyn_cast<ConstantInt>(AddrInst->getOperand(i))) {
ConstantOffset += CI->getSExtValue()*TypeSize;
} else if (TypeSize) { if (VariableOperand != -1)
return false;
VariableOperand = i;
VariableScale = TypeSize;
}
}
}
if (VariableOperand == -1) {
AddrMode.BaseOffs += ConstantOffset;
if (ConstantOffset == 0 || TLI.isLegalAddressingMode(AddrMode, AccessTy)){
if (MatchAddr(AddrInst->getOperand(0), Depth+1))
return true;
}
AddrMode.BaseOffs -= ConstantOffset;
return false;
}
ExtAddrMode BackupAddrMode = AddrMode;
unsigned OldSize = AddrModeInsts.size();
AddrMode.BaseOffs += ConstantOffset;
if (!MatchAddr(AddrInst->getOperand(0), Depth+1)) {
if (AddrMode.HasBaseReg) {
AddrMode = BackupAddrMode;
AddrModeInsts.resize(OldSize);
return false;
}
AddrMode.HasBaseReg = true;
AddrMode.BaseReg = AddrInst->getOperand(0);
}
if (!MatchScaledValue(AddrInst->getOperand(VariableOperand), VariableScale,
Depth)) {
AddrMode = BackupAddrMode;
AddrModeInsts.resize(OldSize);
if (AddrMode.HasBaseReg)
return false;
AddrMode.HasBaseReg = true;
AddrMode.BaseReg = AddrInst->getOperand(0);
AddrMode.BaseOffs += ConstantOffset;
if (!MatchScaledValue(AddrInst->getOperand(VariableOperand),
VariableScale, Depth)) {
AddrMode = BackupAddrMode;
AddrModeInsts.resize(OldSize);
return false;
}
}
return true;
}
case Instruction::SExt: {
Instruction *SExt = cast<Instruction>(AddrInst);
TypePromotionHelper::Action TPH = TypePromotionHelper::getAction(
SExt, InsertedTruncs, TLI, PromotedInsts);
if (!TPH)
return false;
TypePromotionTransaction::ConstRestorationPt LastKnownGood =
TPT.getRestorationPoint();
unsigned CreatedInsts = 0;
Value *PromotedOperand = TPH(SExt, TPT, PromotedInsts, CreatedInsts);
if (MovedAway)
*MovedAway = true;
assert(PromotedOperand &&
"TypePromotionHelper should have filtered out those cases");
ExtAddrMode BackupAddrMode = AddrMode;
unsigned OldSize = AddrModeInsts.size();
if (!MatchAddr(PromotedOperand, Depth) ||
!IsPromotionProfitable(AddrModeInsts.size(), OldSize + CreatedInsts,
PromotedOperand)) {
AddrMode = BackupAddrMode;
AddrModeInsts.resize(OldSize);
DEBUG(dbgs() << "Sign extension does not pay off: rollback\n");
TPT.rollback(LastKnownGood);
return false;
}
return true;
}
}
return false;
}
bool AddressingModeMatcher::MatchAddr(Value *Addr, unsigned Depth) {
TypePromotionTransaction::ConstRestorationPt LastKnownGood =
TPT.getRestorationPoint();
if (ConstantInt *CI = dyn_cast<ConstantInt>(Addr)) {
AddrMode.BaseOffs += CI->getSExtValue();
if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
return true;
AddrMode.BaseOffs -= CI->getSExtValue();
} else if (GlobalValue *GV = dyn_cast<GlobalValue>(Addr)) {
if (AddrMode.BaseGV == 0) {
AddrMode.BaseGV = GV;
if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
return true;
AddrMode.BaseGV = 0;
}
} else if (Instruction *I = dyn_cast<Instruction>(Addr)) {
ExtAddrMode BackupAddrMode = AddrMode;
unsigned OldSize = AddrModeInsts.size();
bool MovedAway = false;
if (MatchOperationAddr(I, I->getOpcode(), Depth, &MovedAway)) {
if (MovedAway)
return true;
if (I->hasOneUse() ||
IsProfitableToFoldIntoAddressingMode(I, BackupAddrMode, AddrMode)) {
AddrModeInsts.push_back(I);
return true;
}
AddrMode = BackupAddrMode;
AddrModeInsts.resize(OldSize);
TPT.rollback(LastKnownGood);
}
} else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) {
if (MatchOperationAddr(CE, CE->getOpcode(), Depth))
return true;
TPT.rollback(LastKnownGood);
} else if (isa<ConstantPointerNull>(Addr)) {
return true;
}
if (!AddrMode.HasBaseReg) {
AddrMode.HasBaseReg = true;
AddrMode.BaseReg = Addr;
if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
return true;
AddrMode.HasBaseReg = false;
AddrMode.BaseReg = 0;
}
if (AddrMode.Scale == 0) {
AddrMode.Scale = 1;
AddrMode.ScaledReg = Addr;
if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
return true;
AddrMode.Scale = 0;
AddrMode.ScaledReg = 0;
}
TPT.rollback(LastKnownGood);
return false;
}
static bool IsOperandAMemoryOperand(CallInst *CI, InlineAsm *IA, Value *OpVal,
const TargetLowering &TLI) {
TargetLowering::AsmOperandInfoVector TargetConstraints = TLI.ParseConstraints(ImmutableCallSite(CI));
for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) {
TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i];
TLI.ComputeConstraintToUse(OpInfo, SDValue());
if (OpInfo.CallOperandVal == OpVal &&
(OpInfo.ConstraintType != TargetLowering::C_Memory ||
!OpInfo.isIndirect))
return false;
}
return true;
}
static bool FindAllMemoryUses(Instruction *I,
SmallVectorImpl<std::pair<Instruction*,unsigned> > &MemoryUses,
SmallPtrSet<Instruction*, 16> &ConsideredInsts,
const TargetLowering &TLI) {
if (!ConsideredInsts.insert(I))
return false;
if (!MightBeFoldableInst(I))
return true;
for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
UI != E; ++UI) {
User *U = *UI;
if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
MemoryUses.push_back(std::make_pair(LI, UI.getOperandNo()));
continue;
}
if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
unsigned opNo = UI.getOperandNo();
if (opNo == 0) return true; MemoryUses.push_back(std::make_pair(SI, opNo));
continue;
}
if (CallInst *CI = dyn_cast<CallInst>(U)) {
InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledValue());
if (!IA) return true;
if (!IsOperandAMemoryOperand(CI, IA, I, TLI))
return true;
continue;
}
if (FindAllMemoryUses(cast<Instruction>(U), MemoryUses, ConsideredInsts,
TLI))
return true;
}
return false;
}
bool AddressingModeMatcher::ValueAlreadyLiveAtInst(Value *Val,Value *KnownLive1,
Value *KnownLive2) {
if (Val == 0 || Val == KnownLive1 || Val == KnownLive2)
return true;
if (!isa<Instruction>(Val) && !isa<Argument>(Val)) return true;
if (AllocaInst *AI = dyn_cast<AllocaInst>(Val))
if (AI->isStaticAlloca())
return true;
return Val->isUsedInBasicBlock(MemoryInst->getParent());
}
bool AddressingModeMatcher::
IsProfitableToFoldIntoAddressingMode(Instruction *I, ExtAddrMode &AMBefore,
ExtAddrMode &AMAfter) {
if (IgnoreProfitability) return true;
Value *BaseReg = AMAfter.BaseReg, *ScaledReg = AMAfter.ScaledReg;
if (ValueAlreadyLiveAtInst(BaseReg, AMBefore.BaseReg, AMBefore.ScaledReg))
BaseReg = 0;
if (ValueAlreadyLiveAtInst(ScaledReg, AMBefore.BaseReg, AMBefore.ScaledReg))
ScaledReg = 0;
if (BaseReg == 0 && ScaledReg == 0)
return true;
SmallVector<std::pair<Instruction*,unsigned>, 16> MemoryUses;
SmallPtrSet<Instruction*, 16> ConsideredInsts;
if (FindAllMemoryUses(I, MemoryUses, ConsideredInsts, TLI))
return false;
SmallVector<Instruction*, 32> MatchedAddrModeInsts;
for (unsigned i = 0, e = MemoryUses.size(); i != e; ++i) {
Instruction *User = MemoryUses[i].first;
unsigned OpNo = MemoryUses[i].second;
Value *Address = User->getOperand(OpNo);
if (!Address->getType()->isPointerTy())
return false;
Type *AddressAccessTy = Address->getType()->getPointerElementType();
ExtAddrMode Result;
TypePromotionTransaction::ConstRestorationPt LastKnownGood =
TPT.getRestorationPoint();
AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI, AddressAccessTy,
MemoryInst, Result, InsertedTruncs,
PromotedInsts, TPT);
Matcher.IgnoreProfitability = true;
bool Success = Matcher.MatchAddr(Address, 0);
(void)Success; assert(Success && "Couldn't select *anything*?");
TPT.rollback(LastKnownGood);
if (std::find(MatchedAddrModeInsts.begin(), MatchedAddrModeInsts.end(),
I) == MatchedAddrModeInsts.end())
return false;
MatchedAddrModeInsts.clear();
}
return true;
}
}
static bool IsNonLocalValue(Value *V, BasicBlock *BB) {
if (Instruction *I = dyn_cast<Instruction>(V))
return I->getParent() != BB;
return false;
}
bool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr,
Type *AccessTy) {
Value *Repl = Addr;
SmallVector<Value*, 8> worklist;
SmallPtrSet<Value*, 16> Visited;
worklist.push_back(Addr);
Value *Consensus = 0;
unsigned NumUsesConsensus = 0;
bool IsNumUsesConsensusValid = false;
SmallVector<Instruction*, 16> AddrModeInsts;
ExtAddrMode AddrMode;
TypePromotionTransaction TPT;
TypePromotionTransaction::ConstRestorationPt LastKnownGood =
TPT.getRestorationPoint();
while (!worklist.empty()) {
Value *V = worklist.back();
worklist.pop_back();
if (!Visited.insert(V)) {
Consensus = 0;
break;
}
if (PHINode *P = dyn_cast<PHINode>(V)) {
for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i)
worklist.push_back(P->getIncomingValue(i));
continue;
}
SmallVector<Instruction*, 16> NewAddrModeInsts;
ExtAddrMode NewAddrMode = AddressingModeMatcher::Match(
V, AccessTy, MemoryInst, NewAddrModeInsts, *TLI, InsertedTruncsSet,
PromotedInsts, TPT);
if (!Consensus) {
Consensus = V;
AddrMode = NewAddrMode;
AddrModeInsts = NewAddrModeInsts;
continue;
} else if (NewAddrMode == AddrMode) {
if (!IsNumUsesConsensusValid) {
NumUsesConsensus = Consensus->getNumUses();
IsNumUsesConsensusValid = true;
}
unsigned NumUses = V->getNumUses();
if (NumUses > NumUsesConsensus) {
Consensus = V;
NumUsesConsensus = NumUses;
AddrModeInsts = NewAddrModeInsts;
}
continue;
}
Consensus = 0;
break;
}
if (!Consensus) {
TPT.rollback(LastKnownGood);
return false;
}
TPT.commit();
bool AnyNonLocal = false;
for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) {
if (IsNonLocalValue(AddrModeInsts[i], MemoryInst->getParent())) {
AnyNonLocal = true;
break;
}
}
if (!AnyNonLocal) {
DEBUG(dbgs() << "CGP: Found local addrmode: " << AddrMode << "\n");
return false;
}
IRBuilder<> Builder(MemoryInst);
Value *&SunkAddr = SunkAddrs[Addr];
if (SunkAddr) {
DEBUG(dbgs() << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for "
<< *MemoryInst);
if (SunkAddr->getType() != Addr->getType())
SunkAddr = Builder.CreateBitCast(SunkAddr, Addr->getType());
} else {
DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for "
<< *MemoryInst);
Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(Addr->getType());
Value *Result = 0;
if (AddrMode.BaseReg) {
Value *V = AddrMode.BaseReg;
if (V->getType()->isPointerTy())
V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr");
if (V->getType() != IntPtrTy)
V = Builder.CreateIntCast(V, IntPtrTy, true, "sunkaddr");
Result = V;
}
if (AddrMode.Scale) {
Value *V = AddrMode.ScaledReg;
if (V->getType() == IntPtrTy) {
} else if (V->getType()->isPointerTy()) {
V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr");
} else if (cast<IntegerType>(IntPtrTy)->getBitWidth() <
cast<IntegerType>(V->getType())->getBitWidth()) {
V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr");
} else {
Instruction *I = dyn_cast<Instruction>(Result);
if (I && (Result != AddrMode.BaseReg))
I->eraseFromParent();
return false;
}
if (AddrMode.Scale != 1)
V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy, AddrMode.Scale),
"sunkaddr");
if (Result)
Result = Builder.CreateAdd(Result, V, "sunkaddr");
else
Result = V;
}
if (AddrMode.BaseGV) {
Value *V = Builder.CreatePtrToInt(AddrMode.BaseGV, IntPtrTy, "sunkaddr");
if (Result)
Result = Builder.CreateAdd(Result, V, "sunkaddr");
else
Result = V;
}
if (AddrMode.BaseOffs) {
Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs);
if (Result)
Result = Builder.CreateAdd(Result, V, "sunkaddr");
else
Result = V;
}
if (Result == 0)
SunkAddr = Constant::getNullValue(Addr->getType());
else
SunkAddr = Builder.CreateIntToPtr(Result, Addr->getType(), "sunkaddr");
}
MemoryInst->replaceUsesOfWith(Repl, SunkAddr);
if (Repl->use_empty()) {
WeakVH IterHandle(CurInstIterator);
BasicBlock *BB = CurInstIterator->getParent();
RecursivelyDeleteTriviallyDeadInstructions(Repl, TLInfo);
if (IterHandle != CurInstIterator) {
CurInstIterator = BB->begin();
SunkAddrs.clear();
}
}
++NumMemoryInsts;
return true;
}
bool CodeGenPrepare::OptimizeInlineAsmInst(CallInst *CS) {
bool MadeChange = false;
TargetLowering::AsmOperandInfoVector
TargetConstraints = TLI->ParseConstraints(CS);
unsigned ArgNo = 0;
for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) {
TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i];
TLI->ComputeConstraintToUse(OpInfo, SDValue());
if (OpInfo.ConstraintType == TargetLowering::C_Memory &&
OpInfo.isIndirect) {
Value *OpVal = CS->getArgOperand(ArgNo++);
MadeChange |= OptimizeMemoryInst(CS, OpVal, OpVal->getType());
} else if (OpInfo.Type == InlineAsm::isInput)
ArgNo++;
}
return MadeChange;
}
bool CodeGenPrepare::MoveExtToFormExtLoad(Instruction *I) {
LoadInst *LI = dyn_cast<LoadInst>(I->getOperand(0));
if (!LI) return false;
if (LI->getParent() == I->getParent())
return false;
if (!LI->hasOneUse() &&
TLI && (TLI->isTypeLegal(TLI->getValueType(LI->getType())) ||
!TLI->isTypeLegal(TLI->getValueType(I->getType()))) &&
!TLI->isTruncateFree(I->getType(), LI->getType()))
return false;
unsigned LType;
if (isa<ZExtInst>(I))
LType = ISD::ZEXTLOAD;
else {
assert(isa<SExtInst>(I) && "Unexpected ext type!");
LType = ISD::SEXTLOAD;
}
if (TLI && !TLI->isLoadExtLegal(LType, TLI->getValueType(LI->getType())))
return false;
I->removeFromParent();
I->insertAfter(LI);
++NumExtsMoved;
return true;
}
bool CodeGenPrepare::OptimizeExtUses(Instruction *I) {
BasicBlock *DefBB = I->getParent();
Value *Src = I->getOperand(0);
if (Src->hasOneUse())
return false;
if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType()))
return false;
if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent())
return false;
bool DefIsLiveOut = false;
for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
UI != E; ++UI) {
Instruction *User = cast<Instruction>(*UI);
BasicBlock *UserBB = User->getParent();
if (UserBB == DefBB) continue;
DefIsLiveOut = true;
break;
}
if (!DefIsLiveOut)
return false;
for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end();
UI != E; ++UI) {
Instruction *User = cast<Instruction>(*UI);
BasicBlock *UserBB = User->getParent();
if (UserBB == DefBB) continue;
if (isa<PHINode>(User) || isa<LoadInst>(User) || isa<StoreInst>(User))
return false;
}
DenseMap<BasicBlock*, Instruction*> InsertedTruncs;
bool MadeChange = false;
for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end();
UI != E; ++UI) {
Use &TheUse = UI.getUse();
Instruction *User = cast<Instruction>(*UI);
BasicBlock *UserBB = User->getParent();
if (UserBB == DefBB) continue;
Instruction *&InsertedTrunc = InsertedTruncs[UserBB];
if (!InsertedTrunc) {
BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt);
InsertedTruncsSet.insert(InsertedTrunc);
}
TheUse = InsertedTrunc;
++NumExtUses;
MadeChange = true;
}
return MadeChange;
}
static bool isFormingBranchFromSelectProfitable(SelectInst *SI) {
CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
if (!Cmp)
return false;
Value *CmpOp0 = Cmp->getOperand(0);
Value *CmpOp1 = Cmp->getOperand(1);
return Cmp->hasOneUse() &&
((isa<LoadInst>(CmpOp0) && CmpOp0->hasOneUse()) ||
(isa<LoadInst>(CmpOp1) && CmpOp1->hasOneUse()));
}
bool CodeGenPrepare::OptimizeSelectInst(SelectInst *SI) {
bool VectorCond = !SI->getCondition()->getType()->isIntegerTy(1);
if (DisableSelectToBranch || OptSize || !TLI || VectorCond)
return false;
TargetLowering::SelectSupportKind SelectKind;
if (VectorCond)
SelectKind = TargetLowering::VectorMaskSelect;
else if (SI->getType()->isVectorTy())
SelectKind = TargetLowering::ScalarCondVectorVal;
else
SelectKind = TargetLowering::ScalarValSelect;
if (TLI->isSelectSupported(SelectKind)) {
if (!TLI->isPredictableSelectExpensive() ||
!isFormingBranchFromSelectProfitable(SI))
return false;
}
ModifiedDT = true;
BasicBlock *StartBlock = SI->getParent();
BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(SI));
BasicBlock *NextBlock = StartBlock->splitBasicBlock(SplitPt, "select.end");
BasicBlock *SmallBlock = BasicBlock::Create(SI->getContext(), "select.mid",
NextBlock->getParent(), NextBlock);
StartBlock->getTerminator()->eraseFromParent();
BranchInst::Create(NextBlock, SmallBlock);
BranchInst::Create(NextBlock, SmallBlock, SI->getCondition(), SI);
PHINode *PN = PHINode::Create(SI->getType(), 2, "", NextBlock->begin());
PN->takeName(SI);
PN->addIncoming(SI->getTrueValue(), StartBlock);
PN->addIncoming(SI->getFalseValue(), SmallBlock);
SI->replaceAllUsesWith(PN);
SI->eraseFromParent();
CurInstIterator = StartBlock->end();
++NumSelectsExpanded;
return true;
}
bool isBroadcastShuffle(ShuffleVectorInst *SVI) {
SmallVector<int, 16> Mask(SVI->getShuffleMask());
int SplatElem = -1;
for (unsigned i = 0; i < Mask.size(); ++i) {
if (SplatElem != -1 && Mask[i] != -1 && Mask[i] != SplatElem)
return false;
SplatElem = Mask[i];
}
return true;
}
bool CodeGenPrepare::OptimizeShuffleVectorInst(ShuffleVectorInst *SVI) {
BasicBlock *DefBB = SVI->getParent();
if (!TLI || !TLI->isVectorShiftByScalarCheap(SVI->getType()))
return false;
if (!isBroadcastShuffle(SVI))
return false;
DenseMap<BasicBlock*, Instruction*> InsertedShuffles;
bool MadeChange = false;
for (Value::use_iterator UI = SVI->use_begin(), E = SVI->use_end();
UI != E; ++UI) {
Instruction *User = cast<Instruction>(*UI);
BasicBlock *UserBB = User->getParent();
if (UserBB == DefBB) continue;
if (!User->isShift()) continue;
Instruction *&InsertedShuffle = InsertedShuffles[UserBB];
if (!InsertedShuffle) {
BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
InsertedShuffle = new ShuffleVectorInst(SVI->getOperand(0),
SVI->getOperand(1),
SVI->getOperand(2), "", InsertPt);
}
User->replaceUsesOfWith(SVI, InsertedShuffle);
MadeChange = true;
}
if (SVI->use_empty()) {
SVI->eraseFromParent();
MadeChange = true;
}
return MadeChange;
}
bool CodeGenPrepare::OptimizeInst(Instruction *I) {
if (PHINode *P = dyn_cast<PHINode>(I)) {
if (Value *V = SimplifyInstruction(P, TLI ? TLI->getDataLayout() : 0,
TLInfo, DT)) {
P->replaceAllUsesWith(V);
P->eraseFromParent();
++NumPHIsElim;
return true;
}
return false;
}
if (CastInst *CI = dyn_cast<CastInst>(I)) {
if (isa<Constant>(CI->getOperand(0)))
return false;
if (TLI && OptimizeNoopCopyExpression(CI, *TLI))
return true;
if (isa<ZExtInst>(I) || isa<SExtInst>(I)) {
bool MadeChange = MoveExtToFormExtLoad(I);
return MadeChange | OptimizeExtUses(I);
}
return false;
}
if (CmpInst *CI = dyn_cast<CmpInst>(I))
if (!TLI || !TLI->hasMultipleConditionRegisters())
return OptimizeCmpExpression(CI);
if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
if (TLI)
return OptimizeMemoryInst(I, I->getOperand(0), LI->getType());
return false;
}
if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
if (TLI)
return OptimizeMemoryInst(I, SI->getOperand(1),
SI->getOperand(0)->getType());
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()) {
Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(),
GEPI->getName(), GEPI);
GEPI->replaceAllUsesWith(NC);
GEPI->eraseFromParent();
++NumGEPsElim;
OptimizeInst(NC);
return true;
}
return false;
}
if (CallInst *CI = dyn_cast<CallInst>(I))
return OptimizeCallInst(CI);
if (SelectInst *SI = dyn_cast<SelectInst>(I))
return OptimizeSelectInst(SI);
if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I))
return OptimizeShuffleVectorInst(SVI);
return false;
}
bool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) {
SunkAddrs.clear();
bool MadeChange = false;
CurInstIterator = BB.begin();
while (CurInstIterator != BB.end())
MadeChange |= OptimizeInst(CurInstIterator++);
MadeChange |= DupRetToEnableTailCallOpts(&BB);
return MadeChange;
}
bool CodeGenPrepare::PlaceDbgValues(Function &F) {
bool MadeChange = false;
for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
Instruction *PrevNonDbgInst = NULL;
for (BasicBlock::iterator BI = I->begin(), BE = I->end(); BI != BE;) {
Instruction *Insn = BI; ++BI;
DbgValueInst *DVI = dyn_cast<DbgValueInst>(Insn);
if (!DVI) {
PrevNonDbgInst = Insn;
continue;
}
Instruction *VI = dyn_cast_or_null<Instruction>(DVI->getValue());
if (VI && VI != PrevNonDbgInst && !VI->isTerminator()) {
DEBUG(dbgs() << "Moving Debug Value before :\n" << *DVI << ' ' << *VI);
DVI->removeFromParent();
if (isa<PHINode>(VI))
DVI->insertBefore(VI->getParent()->getFirstInsertionPt());
else
DVI->insertAfter(VI);
MadeChange = true;
++NumDbgValueMoved;
}
}
}
return MadeChange;
}
bool CodeGenPrepare::sinkAndCmp(Function &F) {
if (!EnableAndCmpSinking)
return false;
if (!TLI || !TLI->isMaskAndBranchFoldingLegal())
return false;
bool MadeChange = false;
for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
BasicBlock *BB = I++;
BranchInst *Brcc = dyn_cast<BranchInst>(BB->getTerminator());
if (!Brcc || !Brcc->isConditional())
continue;
ICmpInst *Cmp = dyn_cast<ICmpInst>(Brcc->getOperand(0));
if (!Cmp || Cmp->getParent() != BB)
continue;
ConstantInt *Zero = dyn_cast<ConstantInt>(Cmp->getOperand(1));
if (!Zero || !Zero->isZero())
continue;
Instruction *And = dyn_cast<Instruction>(Cmp->getOperand(0));
if (!And || And->getOpcode() != Instruction::And || And->getParent() != BB)
continue;
ConstantInt* Mask = dyn_cast<ConstantInt>(And->getOperand(1));
if (!Mask || !Mask->getUniqueInteger().isPowerOf2())
continue;
DEBUG(dbgs() << "found and; icmp ?,0; brcc\n"); DEBUG(BB->dump());
for (Value::use_iterator UI = Cmp->use_begin(), E = Cmp->use_end();
UI != E; ) {
Use &TheUse = UI.getUse();
BranchInst *BrccUser = dyn_cast<BranchInst>(*UI);
++UI;
if (!BrccUser || !BrccUser->isConditional())
continue;
BasicBlock *UserBB = BrccUser->getParent();
if (UserBB == BB) continue;
DEBUG(dbgs() << "found Brcc use\n");
MadeChange = true;
BinaryOperator *NewAnd =
BinaryOperator::CreateAnd(And->getOperand(0), And->getOperand(1), "",
BrccUser);
CmpInst *NewCmp =
CmpInst::Create(Cmp->getOpcode(), Cmp->getPredicate(), NewAnd, Zero,
"", BrccUser);
TheUse = NewCmp;
++NumAndCmpsMoved;
DEBUG(BrccUser->getParent()->dump());
}
}
return MadeChange;
}