CodeGenPrepare.cpp [plain text]
#include "llvm/CodeGen/Passes.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/CallSite.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/GetElementPtrTypeIterator.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InlineAsm.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Statepoint.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/IR/ValueMap.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetLowering.h"
#include "llvm/Target/TargetSubtargetInfo.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"
#include "llvm/Transforms/Utils/SimplifyLibCalls.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");
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");
STATISTIC(NumStoreExtractExposed, "Number of store(extractelement) exposed");
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>
DisableGCOpts("disable-cgp-gc-opts", cl::Hidden, cl::init(false),
cl::desc("Disable GC 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> AddrSinkUsingGEPs(
"addr-sink-using-gep", cl::Hidden, cl::init(false),
cl::desc("Address sinking in CGP using GEPs."));
static cl::opt<bool> EnableAndCmpSinking(
"enable-andcmp-sinking", cl::Hidden, cl::init(true),
cl::desc("Enable sinkinig and/cmp into branches."));
static cl::opt<bool> DisableStoreExtract(
"disable-cgp-store-extract", cl::Hidden, cl::init(false),
cl::desc("Disable store(extract) optimizations in CodeGenPrepare"));
static cl::opt<bool> StressStoreExtract(
"stress-cgp-store-extract", cl::Hidden, cl::init(false),
cl::desc("Stress test store(extract) optimizations in CodeGenPrepare"));
static cl::opt<bool> DisableExtLdPromotion(
"disable-cgp-ext-ld-promotion", cl::Hidden, cl::init(false),
cl::desc("Disable ext(promotable(ld)) -> promoted(ext(ld)) optimization in "
"CodeGenPrepare"));
static cl::opt<bool> StressExtLdPromotion(
"stress-cgp-ext-ld-promotion", cl::Hidden, cl::init(false),
cl::desc("Stress test ext(promotable(ld)) -> promoted(ext(ld)) "
"optimization in CodeGenPrepare"));
namespace {
typedef SmallPtrSet<Instruction *, 16> SetOfInstrs;
typedef PointerIntPair<Type *, 1, bool> TypeIsSExt;
typedef DenseMap<Instruction *, TypeIsSExt> InstrToOrigTy;
class TypePromotionTransaction;
class CodeGenPrepare : public FunctionPass {
const TargetMachine *TM;
const TargetLowering *TLI;
const TargetTransformInfo *TTI;
const TargetLibraryInfo *TLInfo;
BasicBlock::iterator CurInstIterator;
ValueMap<Value*, Value*> SunkAddrs;
SetOfInstrs InsertedInsts;
InstrToOrigTy PromotedInsts;
bool ModifiedDT;
bool OptSize;
const DataLayout *DL;
public:
static char ID; explicit CodeGenPrepare(const TargetMachine *TM = nullptr)
: FunctionPass(ID), TM(TM), TLI(nullptr), TTI(nullptr), DL(nullptr) {
initializeCodeGenPreparePass(*PassRegistry::getPassRegistry());
}
bool runOnFunction(Function &F) override;
const char *getPassName() const override { return "CodeGen Prepare"; }
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addPreserved<DominatorTreeWrapperPass>();
AU.addRequired<TargetLibraryInfoWrapperPass>();
AU.addRequired<TargetTransformInfoWrapperPass>();
}
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& ModifiedDT);
bool optimizeInst(Instruction *I, bool& ModifiedDT);
bool optimizeMemoryInst(Instruction *I, Value *Addr,
Type *AccessTy, unsigned AS);
bool optimizeInlineAsmInst(CallInst *CS);
bool optimizeCallInst(CallInst *CI, bool& ModifiedDT);
bool moveExtToFormExtLoad(Instruction *&I);
bool optimizeExtUses(Instruction *I);
bool optimizeSelectInst(SelectInst *SI);
bool optimizeShuffleVectorInst(ShuffleVectorInst *SI);
bool optimizeSwitchInst(SwitchInst *CI);
bool optimizeExtractElementInst(Instruction *Inst);
bool dupRetToEnableTailCallOpts(BasicBlock *BB);
bool placeDbgValues(Function &F);
bool sinkAndCmp(Function &F);
bool extLdPromotion(TypePromotionTransaction &TPT, LoadInst *&LI,
Instruction *&Inst,
const SmallVectorImpl<Instruction *> &Exts,
unsigned CreatedInstCost);
bool splitBranchCondition(Function &F);
bool simplifyOffsetableRelocate(Instruction &I);
void stripInvariantGroupMetadata(Instruction &I);
};
}
char CodeGenPrepare::ID = 0;
INITIALIZE_TM_PASS(CodeGenPrepare, "codegenprepare",
"Optimize for code generation", false, false)
FunctionPass *llvm::createCodeGenPreparePass(const TargetMachine *TM) {
return new CodeGenPrepare(TM);
}
bool CodeGenPrepare::runOnFunction(Function &F) {
if (skipOptnoneFunction(F))
return false;
DL = &F.getParent()->getDataLayout();
bool EverMadeChange = false;
InsertedInsts.clear();
PromotedInsts.clear();
ModifiedDT = false;
if (TM)
TLI = TM->getSubtargetImpl(F)->getTargetLowering();
TLInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
OptSize = F.optForSize();
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);
EverMadeChange |= splitBranchCondition(F);
}
bool MadeChange = true;
while (MadeChange) {
MadeChange = false;
for (Function::iterator I = F.begin(); I != F.end(); ) {
BasicBlock *BB = &*I++;
bool ModifiedDTOnIteration = false;
MadeChange |= optimizeBlock(*BB, ModifiedDTOnIteration);
if (ModifiedDTOnIteration)
break;
}
EverMadeChange |= MadeChange;
}
SunkAddrs.clear();
if (!DisableBranchOpts) {
MadeChange = false;
SmallPtrSet<BasicBlock*, 8> WorkList;
for (BasicBlock &BB : F) {
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);
EverMadeChange |= MadeChange;
}
if (!DisableGCOpts) {
SmallVector<Instruction *, 2> Statepoints;
for (BasicBlock &BB : F)
for (Instruction &I : BB)
if (isStatepoint(I))
Statepoints.push_back(&I);
for (auto &I : Statepoints)
EverMadeChange |= simplifyOffsetableRelocate(*I);
}
return EverMadeChange;
}
bool CodeGenPrepare::eliminateFallThrough(Function &F) {
bool Changed = false;
for (Function::iterator I = std::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, nullptr);
if (isEntry && BB != &BB->getParent()->getEntryBlock())
BB->moveBefore(&BB->getParent()->getEntryBlock());
I = BB->getIterator();
}
}
return Changed;
}
bool CodeGenPrepare::eliminateMostlyEmptyBlocks(Function &F) {
bool MadeChange = false;
for (Function::iterator I = std::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->getIterator();
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 (const User *U : PN->users()) {
const Instruction *UI = cast<Instruction>(U);
if (UI->getParent() != DestBB || !isa<PHINode>(UI))
return false;
if (UI->getParent() == DestBB) {
if (const PHINode *UPN = dyn_cast<PHINode>(UI))
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, nullptr);
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);
BB->eraseFromParent();
++NumBlocksElim;
DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
}
static void computeBaseDerivedRelocateMap(
const SmallVectorImpl<User *> &AllRelocateCalls,
DenseMap<IntrinsicInst *, SmallVector<IntrinsicInst *, 2>> &
RelocateInstMap) {
DenseMap<std::pair<unsigned, unsigned>, IntrinsicInst *> RelocateIdxMap;
for (auto &U : AllRelocateCalls) {
GCRelocateOperands ThisRelocate(U);
IntrinsicInst *I = cast<IntrinsicInst>(U);
auto K = std::make_pair(ThisRelocate.getBasePtrIndex(),
ThisRelocate.getDerivedPtrIndex());
RelocateIdxMap.insert(std::make_pair(K, I));
}
for (auto &Item : RelocateIdxMap) {
std::pair<unsigned, unsigned> Key = Item.first;
if (Key.first == Key.second)
continue;
IntrinsicInst *I = Item.second;
auto BaseKey = std::make_pair(Key.first, Key.first);
auto MaybeBase = RelocateIdxMap.find(BaseKey);
if (MaybeBase == RelocateIdxMap.end())
continue;
RelocateInstMap[MaybeBase->second].push_back(I);
}
}
static bool getGEPSmallConstantIntOffsetV(GetElementPtrInst *GEP,
SmallVectorImpl<Value *> &OffsetV) {
for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
auto Op = dyn_cast<ConstantInt>(GEP->getOperand(i));
if (!Op || Op->getZExtValue() > 20)
return false;
}
for (unsigned i = 1; i < GEP->getNumOperands(); i++)
OffsetV.push_back(GEP->getOperand(i));
return true;
}
static bool
simplifyRelocatesOffABase(IntrinsicInst *RelocatedBase,
const SmallVectorImpl<IntrinsicInst *> &Targets) {
bool MadeChange = false;
for (auto &ToReplace : Targets) {
GCRelocateOperands MasterRelocate(RelocatedBase);
GCRelocateOperands ThisRelocate(ToReplace);
assert(ThisRelocate.getBasePtrIndex() == MasterRelocate.getBasePtrIndex() &&
"Not relocating a derived object of the original base object");
if (ThisRelocate.getBasePtrIndex() == ThisRelocate.getDerivedPtrIndex()) {
continue;
}
if (RelocatedBase->getParent() != ToReplace->getParent()) {
continue;
}
Value *Base = ThisRelocate.getBasePtr();
auto Derived = dyn_cast<GetElementPtrInst>(ThisRelocate.getDerivedPtr());
if (!Derived || Derived->getPointerOperand() != Base)
continue;
SmallVector<Value *, 2> OffsetV;
if (!getGEPSmallConstantIntOffsetV(Derived, OffsetV))
continue;
assert(RelocatedBase->getNextNode() && "Should always have one since it's not a terminator");
IRBuilder<> Builder(RelocatedBase->getNextNode());
Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc());
Instruction *ActualRelocatedBase = RelocatedBase;
if (RelocatedBase->getType() != Base->getType()) {
ActualRelocatedBase =
cast<Instruction>(Builder.CreateBitCast(RelocatedBase, Base->getType()));
}
Value *Replacement = Builder.CreateGEP(
Derived->getSourceElementType(), ActualRelocatedBase, makeArrayRef(OffsetV));
Instruction *ReplacementInst = cast<Instruction>(Replacement);
Replacement->takeName(ToReplace);
Instruction *ActualReplacement = ReplacementInst;
if (ReplacementInst->getType() != ToReplace->getType()) {
ActualReplacement =
cast<Instruction>(Builder.CreateBitCast(ReplacementInst, ToReplace->getType()));
}
ToReplace->replaceAllUsesWith(ActualReplacement);
ToReplace->eraseFromParent();
MadeChange = true;
}
return MadeChange;
}
bool CodeGenPrepare::simplifyOffsetableRelocate(Instruction &I) {
bool MadeChange = false;
SmallVector<User *, 2> AllRelocateCalls;
for (auto *U : I.users())
if (isGCRelocate(dyn_cast<Instruction>(U)))
AllRelocateCalls.push_back(U);
if (AllRelocateCalls.size() < 2)
return false;
DenseMap<IntrinsicInst *, SmallVector<IntrinsicInst *, 2>> RelocateInstMap;
computeBaseDerivedRelocateMap(AllRelocateCalls, RelocateInstMap);
if (RelocateInstMap.empty())
return false;
for (auto &Item : RelocateInstMap)
MadeChange = simplifyRelocatesOffABase(Item.first, Item.second);
return MadeChange;
}
static bool SinkCast(CastInst *CI) {
BasicBlock *DefBB = CI->getParent();
DenseMap<BasicBlock*, CastInst*> InsertedCasts;
bool MadeChange = false;
for (Value::user_iterator UI = CI->user_begin(), E = CI->user_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(TheUse);
}
++UI;
if (UserBB == DefBB) continue;
CastInst *&InsertedCast = InsertedCasts[UserBB];
if (!InsertedCast) {
BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
assert(InsertPt != UserBB->end());
InsertedCast = CastInst::Create(CI->getOpcode(), CI->getOperand(0),
CI->getType(), "", &*InsertPt);
}
TheUse = InsertedCast;
MadeChange = true;
++NumCastUses;
}
if (CI->use_empty()) {
CI->eraseFromParent();
MadeChange = true;
}
return MadeChange;
}
static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI,
const DataLayout &DL) {
EVT SrcVT = TLI.getValueType(DL, CI->getOperand(0)->getType());
EVT DstVT = TLI.getValueType(DL, 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;
return SinkCast(CI);
}
static bool CombineUAddWithOverflow(CmpInst *CI) {
Value *A, *B;
Instruction *AddI;
if (!match(CI,
m_UAddWithOverflow(m_Value(A), m_Value(B), m_Instruction(AddI))))
return false;
Type *Ty = AddI->getType();
if (!isa<IntegerType>(Ty))
return false;
if (AddI->getParent() != CI->getParent() && !AddI->hasOneUse())
return false;
#ifndef NDEBUG
if (AddI->hasOneUse())
assert(*AddI->user_begin() == CI && "expected!");
#endif
Module *M = CI->getParent()->getParent()->getParent();
Value *F = Intrinsic::getDeclaration(M, Intrinsic::uadd_with_overflow, Ty);
auto *InsertPt = AddI->hasOneUse() ? CI : AddI;
auto *UAddWithOverflow =
CallInst::Create(F, {A, B}, "uadd.overflow", InsertPt);
auto *UAdd = ExtractValueInst::Create(UAddWithOverflow, 0, "uadd", InsertPt);
auto *Overflow =
ExtractValueInst::Create(UAddWithOverflow, 1, "overflow", InsertPt);
CI->replaceAllUsesWith(Overflow);
AddI->replaceAllUsesWith(UAdd);
CI->eraseFromParent();
AddI->eraseFromParent();
return true;
}
static bool SinkCmpExpression(CmpInst *CI) {
BasicBlock *DefBB = CI->getParent();
DenseMap<BasicBlock*, CmpInst*> InsertedCmps;
bool MadeChange = false;
for (Value::user_iterator UI = CI->user_begin(), E = CI->user_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();
assert(InsertPt != UserBB->end());
InsertedCmp =
CmpInst::Create(CI->getOpcode(), CI->getPredicate(),
CI->getOperand(0), CI->getOperand(1), "", &*InsertPt);
}
TheUse = InsertedCmp;
MadeChange = true;
++NumCmpUses;
}
if (CI->use_empty()) {
CI->eraseFromParent();
MadeChange = true;
}
return MadeChange;
}
static bool OptimizeCmpExpression(CmpInst *CI) {
if (SinkCmpExpression(CI))
return true;
if (CombineUAddWithOverflow(CI))
return true;
return false;
}
static 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;
}
static bool
SinkShiftAndTruncate(BinaryOperator *ShiftI, Instruction *User, ConstantInt *CI,
DenseMap<BasicBlock *, BinaryOperator *> &InsertedShifts,
const TargetLowering &TLI, const DataLayout &DL) {
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);
++TruncUI;
int ISDOpcode = TLI.InstructionOpcodeToISD(TruncUser->getOpcode());
if (!ISDOpcode)
continue;
if (TLI.isOperationLegalOrCustom(
ISDOpcode, TLI.getValueType(DL, TruncUser->getType(), true)))
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();
assert(InsertPt != TruncUserBB->end());
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++;
assert(TruncInsertPt != TruncUserBB->end());
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,
const DataLayout &DL) {
BasicBlock *DefBB = ShiftI->getParent();
DenseMap<BasicBlock *, BinaryOperator *> InsertedShifts;
bool shiftIsLegal = TLI.isTypeLegal(TLI.getValueType(DL, 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);
++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(DL, User->getType()))))
MadeChange =
SinkShiftAndTruncate(ShiftI, User, CI, InsertedShifts, TLI, DL);
continue;
}
BinaryOperator *&InsertedShift = InsertedShifts[UserBB];
if (!InsertedShift) {
BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
assert(InsertPt != UserBB->end());
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;
}
static void ScalarizeMaskedLoad(CallInst *CI) {
Value *Ptr = CI->getArgOperand(0);
Value *Alignment = CI->getArgOperand(1);
Value *Mask = CI->getArgOperand(2);
Value *Src0 = CI->getArgOperand(3);
unsigned AlignVal = cast<ConstantInt>(Alignment)->getZExtValue();
VectorType *VecType = dyn_cast<VectorType>(CI->getType());
assert(VecType && "Unexpected return type of masked load intrinsic");
Type *EltTy = CI->getType()->getVectorElementType();
IRBuilder<> Builder(CI->getContext());
Instruction *InsertPt = CI;
BasicBlock *IfBlock = CI->getParent();
BasicBlock *CondBlock = nullptr;
BasicBlock *PrevIfBlock = CI->getParent();
Builder.SetInsertPoint(InsertPt);
Builder.SetCurrentDebugLocation(CI->getDebugLoc());
bool IsAllOnesMask = isa<Constant>(Mask) &&
cast<Constant>(Mask)->isAllOnesValue();
if (IsAllOnesMask) {
Value *NewI = Builder.CreateAlignedLoad(Ptr, AlignVal);
CI->replaceAllUsesWith(NewI);
CI->eraseFromParent();
return;
}
AlignVal = std::min(AlignVal, VecType->getScalarSizeInBits()/8);
Type *NewPtrType =
EltTy->getPointerTo(cast<PointerType>(Ptr->getType())->getAddressSpace());
Value *FirstEltPtr = Builder.CreateBitCast(Ptr, NewPtrType);
unsigned VectorWidth = VecType->getNumElements();
Value *UndefVal = UndefValue::get(VecType);
Value *VResult = UndefVal;
if (isa<ConstantVector>(Mask)) {
for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
if (cast<ConstantVector>(Mask)->getOperand(Idx)->isNullValue())
continue;
Value *Gep =
Builder.CreateInBoundsGEP(EltTy, FirstEltPtr, Builder.getInt32(Idx));
LoadInst* Load = Builder.CreateAlignedLoad(Gep, AlignVal);
VResult = Builder.CreateInsertElement(VResult, Load,
Builder.getInt32(Idx));
}
Value *NewI = Builder.CreateSelect(Mask, VResult, Src0);
CI->replaceAllUsesWith(NewI);
CI->eraseFromParent();
return;
}
PHINode *Phi = nullptr;
Value *PrevPhi = UndefVal;
for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
if (Idx > 0) {
Phi = Builder.CreatePHI(VecType, 2, "res.phi.else");
Phi->addIncoming(VResult, CondBlock);
Phi->addIncoming(PrevPhi, PrevIfBlock);
PrevPhi = Phi;
VResult = Phi;
}
Value *Predicate = Builder.CreateExtractElement(Mask, Builder.getInt32(Idx));
Value *Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Predicate,
ConstantInt::get(Predicate->getType(), 1));
CondBlock = IfBlock->splitBasicBlock(InsertPt->getIterator(), "cond.load");
Builder.SetInsertPoint(InsertPt);
Value *Gep =
Builder.CreateInBoundsGEP(EltTy, FirstEltPtr, Builder.getInt32(Idx));
LoadInst *Load = Builder.CreateAlignedLoad(Gep, AlignVal);
VResult = Builder.CreateInsertElement(VResult, Load, Builder.getInt32(Idx));
BasicBlock *NewIfBlock =
CondBlock->splitBasicBlock(InsertPt->getIterator(), "else");
Builder.SetInsertPoint(InsertPt);
Instruction *OldBr = IfBlock->getTerminator();
BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
OldBr->eraseFromParent();
PrevIfBlock = IfBlock;
IfBlock = NewIfBlock;
}
Phi = Builder.CreatePHI(VecType, 2, "res.phi.select");
Phi->addIncoming(VResult, CondBlock);
Phi->addIncoming(PrevPhi, PrevIfBlock);
Value *NewI = Builder.CreateSelect(Mask, Phi, Src0);
CI->replaceAllUsesWith(NewI);
CI->eraseFromParent();
}
static void ScalarizeMaskedStore(CallInst *CI) {
Value *Src = CI->getArgOperand(0);
Value *Ptr = CI->getArgOperand(1);
Value *Alignment = CI->getArgOperand(2);
Value *Mask = CI->getArgOperand(3);
unsigned AlignVal = cast<ConstantInt>(Alignment)->getZExtValue();
VectorType *VecType = dyn_cast<VectorType>(Src->getType());
assert(VecType && "Unexpected data type in masked store intrinsic");
Type *EltTy = VecType->getElementType();
IRBuilder<> Builder(CI->getContext());
Instruction *InsertPt = CI;
BasicBlock *IfBlock = CI->getParent();
Builder.SetInsertPoint(InsertPt);
Builder.SetCurrentDebugLocation(CI->getDebugLoc());
bool IsAllOnesMask = isa<Constant>(Mask) &&
cast<Constant>(Mask)->isAllOnesValue();
if (IsAllOnesMask) {
Builder.CreateAlignedStore(Src, Ptr, AlignVal);
CI->eraseFromParent();
return;
}
AlignVal = std::max(AlignVal, VecType->getScalarSizeInBits()/8);
Type *NewPtrType =
EltTy->getPointerTo(cast<PointerType>(Ptr->getType())->getAddressSpace());
Value *FirstEltPtr = Builder.CreateBitCast(Ptr, NewPtrType);
unsigned VectorWidth = VecType->getNumElements();
if (isa<ConstantVector>(Mask)) {
for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
if (cast<ConstantVector>(Mask)->getOperand(Idx)->isNullValue())
continue;
Value *OneElt = Builder.CreateExtractElement(Src, Builder.getInt32(Idx));
Value *Gep =
Builder.CreateInBoundsGEP(EltTy, FirstEltPtr, Builder.getInt32(Idx));
Builder.CreateAlignedStore(OneElt, Gep, AlignVal);
}
CI->eraseFromParent();
return;
}
for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
Value *Predicate = Builder.CreateExtractElement(Mask, Builder.getInt32(Idx));
Value *Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Predicate,
ConstantInt::get(Predicate->getType(), 1));
BasicBlock *CondBlock =
IfBlock->splitBasicBlock(InsertPt->getIterator(), "cond.store");
Builder.SetInsertPoint(InsertPt);
Value *OneElt = Builder.CreateExtractElement(Src, Builder.getInt32(Idx));
Value *Gep =
Builder.CreateInBoundsGEP(EltTy, FirstEltPtr, Builder.getInt32(Idx));
Builder.CreateAlignedStore(OneElt, Gep, AlignVal);
BasicBlock *NewIfBlock =
CondBlock->splitBasicBlock(InsertPt->getIterator(), "else");
Builder.SetInsertPoint(InsertPt);
Instruction *OldBr = IfBlock->getTerminator();
BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
OldBr->eraseFromParent();
IfBlock = NewIfBlock;
}
CI->eraseFromParent();
}
static void ScalarizeMaskedGather(CallInst *CI) {
Value *Ptrs = CI->getArgOperand(0);
Value *Alignment = CI->getArgOperand(1);
Value *Mask = CI->getArgOperand(2);
Value *Src0 = CI->getArgOperand(3);
VectorType *VecType = dyn_cast<VectorType>(CI->getType());
assert(VecType && "Unexpected return type of masked load intrinsic");
IRBuilder<> Builder(CI->getContext());
Instruction *InsertPt = CI;
BasicBlock *IfBlock = CI->getParent();
BasicBlock *CondBlock = nullptr;
BasicBlock *PrevIfBlock = CI->getParent();
Builder.SetInsertPoint(InsertPt);
unsigned AlignVal = cast<ConstantInt>(Alignment)->getZExtValue();
Builder.SetCurrentDebugLocation(CI->getDebugLoc());
Value *UndefVal = UndefValue::get(VecType);
Value *VResult = UndefVal;
unsigned VectorWidth = VecType->getNumElements();
bool IsConstMask = isa<ConstantVector>(Mask);
if (IsConstMask) {
for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
if (cast<ConstantVector>(Mask)->getOperand(Idx)->isNullValue())
continue;
Value *Ptr = Builder.CreateExtractElement(Ptrs, Builder.getInt32(Idx),
"Ptr" + Twine(Idx));
LoadInst *Load = Builder.CreateAlignedLoad(Ptr, AlignVal,
"Load" + Twine(Idx));
VResult = Builder.CreateInsertElement(VResult, Load,
Builder.getInt32(Idx),
"Res" + Twine(Idx));
}
Value *NewI = Builder.CreateSelect(Mask, VResult, Src0);
CI->replaceAllUsesWith(NewI);
CI->eraseFromParent();
return;
}
PHINode *Phi = nullptr;
Value *PrevPhi = UndefVal;
for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
if (Idx > 0) {
Phi = Builder.CreatePHI(VecType, 2, "res.phi.else");
Phi->addIncoming(VResult, CondBlock);
Phi->addIncoming(PrevPhi, PrevIfBlock);
PrevPhi = Phi;
VResult = Phi;
}
Value *Predicate = Builder.CreateExtractElement(Mask,
Builder.getInt32(Idx),
"Mask" + Twine(Idx));
Value *Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Predicate,
ConstantInt::get(Predicate->getType(), 1),
"ToLoad" + Twine(Idx));
CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.load");
Builder.SetInsertPoint(InsertPt);
Value *Ptr = Builder.CreateExtractElement(Ptrs, Builder.getInt32(Idx),
"Ptr" + Twine(Idx));
LoadInst *Load = Builder.CreateAlignedLoad(Ptr, AlignVal,
"Load" + Twine(Idx));
VResult = Builder.CreateInsertElement(VResult, Load, Builder.getInt32(Idx),
"Res" + Twine(Idx));
BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else");
Builder.SetInsertPoint(InsertPt);
Instruction *OldBr = IfBlock->getTerminator();
BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
OldBr->eraseFromParent();
PrevIfBlock = IfBlock;
IfBlock = NewIfBlock;
}
Phi = Builder.CreatePHI(VecType, 2, "res.phi.select");
Phi->addIncoming(VResult, CondBlock);
Phi->addIncoming(PrevPhi, PrevIfBlock);
Value *NewI = Builder.CreateSelect(Mask, Phi, Src0);
CI->replaceAllUsesWith(NewI);
CI->eraseFromParent();
}
static void ScalarizeMaskedScatter(CallInst *CI) {
Value *Src = CI->getArgOperand(0);
Value *Ptrs = CI->getArgOperand(1);
Value *Alignment = CI->getArgOperand(2);
Value *Mask = CI->getArgOperand(3);
assert(isa<VectorType>(Src->getType()) &&
"Unexpected data type in masked scatter intrinsic");
assert(isa<VectorType>(Ptrs->getType()) &&
isa<PointerType>(Ptrs->getType()->getVectorElementType()) &&
"Vector of pointers is expected in masked scatter intrinsic");
IRBuilder<> Builder(CI->getContext());
Instruction *InsertPt = CI;
BasicBlock *IfBlock = CI->getParent();
Builder.SetInsertPoint(InsertPt);
Builder.SetCurrentDebugLocation(CI->getDebugLoc());
unsigned AlignVal = cast<ConstantInt>(Alignment)->getZExtValue();
unsigned VectorWidth = Src->getType()->getVectorNumElements();
bool IsConstMask = isa<ConstantVector>(Mask);
if (IsConstMask) {
for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
if (cast<ConstantVector>(Mask)->getOperand(Idx)->isNullValue())
continue;
Value *OneElt = Builder.CreateExtractElement(Src, Builder.getInt32(Idx),
"Elt" + Twine(Idx));
Value *Ptr = Builder.CreateExtractElement(Ptrs, Builder.getInt32(Idx),
"Ptr" + Twine(Idx));
Builder.CreateAlignedStore(OneElt, Ptr, AlignVal);
}
CI->eraseFromParent();
return;
}
for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
Value *Predicate = Builder.CreateExtractElement(Mask,
Builder.getInt32(Idx),
"Mask" + Twine(Idx));
Value *Cmp =
Builder.CreateICmp(ICmpInst::ICMP_EQ, Predicate,
ConstantInt::get(Predicate->getType(), 1),
"ToStore" + Twine(Idx));
BasicBlock *CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.store");
Builder.SetInsertPoint(InsertPt);
Value *OneElt = Builder.CreateExtractElement(Src, Builder.getInt32(Idx),
"Elt" + Twine(Idx));
Value *Ptr = Builder.CreateExtractElement(Ptrs, Builder.getInt32(Idx),
"Ptr" + Twine(Idx));
Builder.CreateAlignedStore(OneElt, Ptr, AlignVal);
BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else");
Builder.SetInsertPoint(InsertPt);
Instruction *OldBr = IfBlock->getTerminator();
BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
OldBr->eraseFromParent();
IfBlock = NewIfBlock;
}
CI->eraseFromParent();
}
bool CodeGenPrepare::optimizeCallInst(CallInst *CI, bool& ModifiedDT) {
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;
}
unsigned MinSize, PrefAlign;
if (TLI && TLI->shouldAlignPointerArgs(CI, MinSize, PrefAlign)) {
for (auto &Arg : CI->arg_operands()) {
if (!Arg->getType()->isPointerTy())
continue;
APInt Offset(DL->getPointerSizeInBits(
cast<PointerType>(Arg->getType())->getAddressSpace()),
0);
Value *Val = Arg->stripAndAccumulateInBoundsConstantOffsets(*DL, Offset);
uint64_t Offset2 = Offset.getLimitedValue();
if ((Offset2 & (PrefAlign-1)) != 0)
continue;
AllocaInst *AI;
if ((AI = dyn_cast<AllocaInst>(Val)) && AI->getAlignment() < PrefAlign &&
DL->getTypeAllocSize(AI->getAllocatedType()) >= MinSize + Offset2)
AI->setAlignment(PrefAlign);
GlobalVariable *GV;
if ((GV = dyn_cast<GlobalVariable>(Val)) && GV->hasUniqueInitializer() &&
!GV->hasSection() && GV->getAlignment() < PrefAlign &&
DL->getTypeAllocSize(GV->getType()->getElementType()) >=
MinSize + Offset2)
GV->setAlignment(PrefAlign);
}
if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(CI)) {
unsigned Align = getKnownAlignment(MI->getDest(), *DL);
if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
Align = std::min(Align, getKnownAlignment(MTI->getSource(), *DL));
if (Align > MI->getAlignment())
MI->setAlignment(ConstantInt::get(MI->getAlignmentType(), Align));
}
}
IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI);
if (II) {
switch (II->getIntrinsicID()) {
default: break;
case 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,
TLInfo, nullptr);
if (IterHandle != CurInstIterator.getNodePtrUnchecked()) {
CurInstIterator = BB->begin();
SunkAddrs.clear();
}
return true;
}
case Intrinsic::masked_load: {
if (!TTI->isLegalMaskedLoad(CI->getType())) {
ScalarizeMaskedLoad(CI);
ModifiedDT = true;
return true;
}
return false;
}
case Intrinsic::masked_store: {
if (!TTI->isLegalMaskedStore(CI->getArgOperand(0)->getType())) {
ScalarizeMaskedStore(CI);
ModifiedDT = true;
return true;
}
return false;
}
case Intrinsic::masked_gather: {
if (!TTI->isLegalMaskedGather(CI->getType())) {
ScalarizeMaskedGather(CI);
ModifiedDT = true;
return true;
}
return false;
}
case Intrinsic::masked_scatter: {
if (!TTI->isLegalMaskedScatter(CI->getArgOperand(0)->getType())) {
ScalarizeMaskedScatter(CI);
ModifiedDT = true;
return true;
}
return false;
}
case Intrinsic::aarch64_stlxr:
case Intrinsic::aarch64_stxr: {
ZExtInst *ExtVal = dyn_cast<ZExtInst>(CI->getArgOperand(0));
if (!ExtVal || !ExtVal->hasOneUse() ||
ExtVal->getParent() == CI->getParent())
return false;
ExtVal->moveBefore(CI);
InsertedInsts.insert(ExtVal);
return true;
}
case Intrinsic::invariant_group_barrier:
II->replaceAllUsesWith(II->getArgOperand(0));
II->eraseFromParent();
return true;
}
if (TLI) {
unsigned AddrSpace = ~0u;
SmallVector<Value*, 2> PtrOps;
Type *AccessTy;
if (TLI->GetAddrModeArguments(II, PtrOps, AccessTy, AddrSpace))
while (!PtrOps.empty())
if (optimizeMemoryInst(II, PtrOps.pop_back_val(), AccessTy, AddrSpace))
return true;
}
}
if (!CI->getCalledFunction()) return false;
FortifiedLibCallSimplifier Simplifier(TLInfo, true);
if (Value *V = Simplifier.optimizeCall(CI)) {
CI->replaceAllUsesWith(V);
CI->eraseFromParent();
return true;
}
return false;
}
bool CodeGenPrepare::dupRetToEnableTailCallOpts(BasicBlock *BB) {
if (!TLI)
return false;
ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator());
if (!RI)
return false;
PHINode *PN = nullptr;
BitCastInst *BCI = nullptr;
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).second)
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(nullptr), ScaledReg(nullptr) {}
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->getIterator();
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() override {
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() override {
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() override {
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 {
Value *Val;
public:
TruncBuilder(Instruction *Opnd, Type *Ty) : TypePromotionAction(Opnd) {
IRBuilder<> Builder(Opnd);
Val = Builder.CreateTrunc(Opnd, Ty, "promoted");
DEBUG(dbgs() << "Do: TruncBuilder: " << *Val << "\n");
}
Value *getBuiltValue() { return Val; }
void undo() override {
DEBUG(dbgs() << "Undo: TruncBuilder: " << *Val << "\n");
if (Instruction *IVal = dyn_cast<Instruction>(Val))
IVal->eraseFromParent();
}
};
class SExtBuilder : public TypePromotionAction {
Value *Val;
public:
SExtBuilder(Instruction *InsertPt, Value *Opnd, Type *Ty)
: TypePromotionAction(InsertPt) {
IRBuilder<> Builder(InsertPt);
Val = Builder.CreateSExt(Opnd, Ty, "promoted");
DEBUG(dbgs() << "Do: SExtBuilder: " << *Val << "\n");
}
Value *getBuiltValue() { return Val; }
void undo() override {
DEBUG(dbgs() << "Undo: SExtBuilder: " << *Val << "\n");
if (Instruction *IVal = dyn_cast<Instruction>(Val))
IVal->eraseFromParent();
}
};
class ZExtBuilder : public TypePromotionAction {
Value *Val;
public:
ZExtBuilder(Instruction *InsertPt, Value *Opnd, Type *Ty)
: TypePromotionAction(InsertPt) {
IRBuilder<> Builder(InsertPt);
Val = Builder.CreateZExt(Opnd, Ty, "promoted");
DEBUG(dbgs() << "Do: ZExtBuilder: " << *Val << "\n");
}
Value *getBuiltValue() { return Val; }
void undo() override {
DEBUG(dbgs() << "Undo: ZExtBuilder: " << *Val << "\n");
if (Instruction *IVal = dyn_cast<Instruction>(Val))
IVal->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() override {
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 (Use &U : Inst->uses()) {
Instruction *UserI = cast<Instruction>(U.getUser());
OriginalUses.push_back(InstructionAndIdx(UserI, U.getOperandNo()));
}
Inst->replaceAllUsesWith(New);
}
void undo() override {
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 = nullptr)
: TypePromotionAction(Inst), Inserter(Inst), Hider(Inst),
Replacer(nullptr) {
if (New)
Replacer = new UsesReplacer(Inst, New);
DEBUG(dbgs() << "Do: InstructionRemover: " << *Inst << "\n");
Inst->removeFromParent();
}
~InstructionRemover() override { delete Replacer; }
void commit() override { delete Inst; }
void undo() override {
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 = nullptr);
void replaceAllUsesWith(Instruction *Inst, Value *New);
void mutateType(Instruction *Inst, Type *NewTy);
Value *createTrunc(Instruction *Opnd, Type *Ty);
Value *createSExt(Instruction *Inst, Value *Opnd, Type *Ty);
Value *createZExt(Instruction *Inst, Value *Opnd, Type *Ty);
void moveBefore(Instruction *Inst, Instruction *Before);
private:
SmallVector<std::unique_ptr<TypePromotionAction>, 16> Actions;
typedef SmallVectorImpl<std::unique_ptr<TypePromotionAction>>::iterator CommitPt;
};
void TypePromotionTransaction::setOperand(Instruction *Inst, unsigned Idx,
Value *NewVal) {
Actions.push_back(
make_unique<TypePromotionTransaction::OperandSetter>(Inst, Idx, NewVal));
}
void TypePromotionTransaction::eraseInstruction(Instruction *Inst,
Value *NewVal) {
Actions.push_back(
make_unique<TypePromotionTransaction::InstructionRemover>(Inst, NewVal));
}
void TypePromotionTransaction::replaceAllUsesWith(Instruction *Inst,
Value *New) {
Actions.push_back(make_unique<TypePromotionTransaction::UsesReplacer>(Inst, New));
}
void TypePromotionTransaction::mutateType(Instruction *Inst, Type *NewTy) {
Actions.push_back(make_unique<TypePromotionTransaction::TypeMutator>(Inst, NewTy));
}
Value *TypePromotionTransaction::createTrunc(Instruction *Opnd,
Type *Ty) {
std::unique_ptr<TruncBuilder> Ptr(new TruncBuilder(Opnd, Ty));
Value *Val = Ptr->getBuiltValue();
Actions.push_back(std::move(Ptr));
return Val;
}
Value *TypePromotionTransaction::createSExt(Instruction *Inst,
Value *Opnd, Type *Ty) {
std::unique_ptr<SExtBuilder> Ptr(new SExtBuilder(Inst, Opnd, Ty));
Value *Val = Ptr->getBuiltValue();
Actions.push_back(std::move(Ptr));
return Val;
}
Value *TypePromotionTransaction::createZExt(Instruction *Inst,
Value *Opnd, Type *Ty) {
std::unique_ptr<ZExtBuilder> Ptr(new ZExtBuilder(Inst, Opnd, Ty));
Value *Val = Ptr->getBuiltValue();
Actions.push_back(std::move(Ptr));
return Val;
}
void TypePromotionTransaction::moveBefore(Instruction *Inst,
Instruction *Before) {
Actions.push_back(
make_unique<TypePromotionTransaction::InstructionMoveBefore>(Inst, Before));
}
TypePromotionTransaction::ConstRestorationPt
TypePromotionTransaction::getRestorationPoint() const {
return !Actions.empty() ? Actions.back().get() : nullptr;
}
void TypePromotionTransaction::commit() {
for (CommitPt It = Actions.begin(), EndIt = Actions.end(); It != EndIt;
++It)
(*It)->commit();
Actions.clear();
}
void TypePromotionTransaction::rollback(
TypePromotionTransaction::ConstRestorationPt Point) {
while (!Actions.empty() && Point != Actions.back().get()) {
std::unique_ptr<TypePromotionAction> Curr = Actions.pop_back_val();
Curr->undo();
}
}
class AddressingModeMatcher {
SmallVectorImpl<Instruction*> &AddrModeInsts;
const TargetMachine &TM;
const TargetLowering &TLI;
const DataLayout &DL;
Type *AccessTy;
unsigned AddrSpace;
Instruction *MemoryInst;
ExtAddrMode &AddrMode;
const SetOfInstrs &InsertedInsts;
InstrToOrigTy &PromotedInsts;
TypePromotionTransaction &TPT;
bool IgnoreProfitability;
AddressingModeMatcher(SmallVectorImpl<Instruction *> &AMI,
const TargetMachine &TM, Type *AT, unsigned AS,
Instruction *MI, ExtAddrMode &AM,
const SetOfInstrs &InsertedInsts,
InstrToOrigTy &PromotedInsts,
TypePromotionTransaction &TPT)
: AddrModeInsts(AMI), TM(TM),
TLI(*TM.getSubtargetImpl(*MI->getParent()->getParent())
->getTargetLowering()),
DL(MI->getModule()->getDataLayout()), AccessTy(AT), AddrSpace(AS),
MemoryInst(MI), AddrMode(AM), InsertedInsts(InsertedInsts),
PromotedInsts(PromotedInsts), TPT(TPT) {
IgnoreProfitability = false;
}
public:
static ExtAddrMode Match(Value *V, Type *AccessTy, unsigned AS,
Instruction *MemoryInst,
SmallVectorImpl<Instruction*> &AddrModeInsts,
const TargetMachine &TM,
const SetOfInstrs &InsertedInsts,
InstrToOrigTy &PromotedInsts,
TypePromotionTransaction &TPT) {
ExtAddrMode Result;
bool Success = AddressingModeMatcher(AddrModeInsts, TM, AccessTy, AS,
MemoryInst, Result, InsertedInsts,
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 = nullptr);
bool isProfitableToFoldIntoAddressingMode(Instruction *I,
ExtAddrMode &AMBefore,
ExtAddrMode &AMAfter);
bool valueAlreadyLiveAtInst(Value *Val, Value *KnownLive1, Value *KnownLive2);
bool isPromotionProfitable(unsigned NewCost, unsigned OldCost,
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(DL, TestAddrMode, AccessTy, AddrSpace))
return false;
AddrMode = TestAddrMode;
ConstantInt *CI = nullptr; Value *AddLHS = nullptr;
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(DL, TestAddrMode, AccessTy, AddrSpace)) {
AddrModeInsts.push_back(cast<Instruction>(ScaleReg));
AddrMode = TestAddrMode;
return true;
}
}
return true;
}
static bool MightBeFoldableInst(Instruction *I) {
switch (I->getOpcode()) {
case Instruction::BitCast:
case Instruction::AddrSpaceCast:
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;
}
}
static bool isPromotedInstructionLegal(const TargetLowering &TLI,
const DataLayout &DL, Value *Val) {
Instruction *PromotedInst = dyn_cast<Instruction>(Val);
if (!PromotedInst)
return false;
int ISDOpcode = TLI.InstructionOpcodeToISD(PromotedInst->getOpcode());
if (!ISDOpcode)
return true;
return TLI.isOperationLegalOrCustom(
ISDOpcode, TLI.getValueType(DL, PromotedInst->getType()));
}
class TypePromotionHelper {
static bool canGetThrough(const Instruction *Inst, Type *ConsideredExtType,
const InstrToOrigTy &PromotedInsts, bool IsSExt);
static bool shouldExtOperand(const Instruction *Inst, int OpIdx) {
return !(isa<SelectInst>(Inst) && OpIdx == 0);
}
static Value *promoteOperandForTruncAndAnyExt(
Instruction *Ext, TypePromotionTransaction &TPT,
InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
SmallVectorImpl<Instruction *> *Exts,
SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI);
static Value *promoteOperandForOther(Instruction *Ext,
TypePromotionTransaction &TPT,
InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
SmallVectorImpl<Instruction *> *Exts,
SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI, bool IsSExt);
static Value *signExtendOperandForOther(
Instruction *Ext, TypePromotionTransaction &TPT,
InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
SmallVectorImpl<Instruction *> *Exts,
SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI) {
return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
Exts, Truncs, TLI, true);
}
static Value *zeroExtendOperandForOther(
Instruction *Ext, TypePromotionTransaction &TPT,
InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
SmallVectorImpl<Instruction *> *Exts,
SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI) {
return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
Exts, Truncs, TLI, false);
}
public:
typedef Value *(*Action)(Instruction *Ext, TypePromotionTransaction &TPT,
InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
SmallVectorImpl<Instruction *> *Exts,
SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI);
static Action getAction(Instruction *Ext, const SetOfInstrs &InsertedInsts,
const TargetLowering &TLI,
const InstrToOrigTy &PromotedInsts);
};
bool TypePromotionHelper::canGetThrough(const Instruction *Inst,
Type *ConsideredExtType,
const InstrToOrigTy &PromotedInsts,
bool IsSExt) {
if (Inst->getType()->isVectorTy())
return false;
if (isa<ZExtInst>(Inst))
return true;
if (IsSExt && isa<SExtInst>(Inst))
return true;
const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst);
if (BinOp && isa<OverflowingBinaryOperator>(BinOp) &&
((!IsSExt && BinOp->hasNoUnsignedWrap()) ||
(IsSExt && BinOp->hasNoSignedWrap())))
return true;
if (!isa<TruncInst>(Inst))
return false;
Value *OpndVal = Inst->getOperand(0);
if (!OpndVal->getType()->isIntegerTy() ||
OpndVal->getType()->getIntegerBitWidth() >
ConsideredExtType->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() && It->second.getInt() == IsSExt)
OpndType = It->second.getPointer();
else if ((IsSExt && isa<SExtInst>(Opnd)) || (!IsSExt && isa<ZExtInst>(Opnd)))
OpndType = Opnd->getOperand(0)->getType();
else
return false;
return Inst->getType()->getIntegerBitWidth() >=
OpndType->getIntegerBitWidth();
}
TypePromotionHelper::Action TypePromotionHelper::getAction(
Instruction *Ext, const SetOfInstrs &InsertedInsts,
const TargetLowering &TLI, const InstrToOrigTy &PromotedInsts) {
assert((isa<SExtInst>(Ext) || isa<ZExtInst>(Ext)) &&
"Unexpected instruction type");
Instruction *ExtOpnd = dyn_cast<Instruction>(Ext->getOperand(0));
Type *ExtTy = Ext->getType();
bool IsSExt = isa<SExtInst>(Ext);
if (!ExtOpnd || !canGetThrough(ExtOpnd, ExtTy, PromotedInsts, IsSExt))
return nullptr;
if (isa<TruncInst>(ExtOpnd) && InsertedInsts.count(ExtOpnd))
return nullptr;
if (isa<SExtInst>(ExtOpnd) || isa<TruncInst>(ExtOpnd) ||
isa<ZExtInst>(ExtOpnd))
return promoteOperandForTruncAndAnyExt;
if (!ExtOpnd->hasOneUse() && !TLI.isTruncateFree(ExtTy, ExtOpnd->getType()))
return nullptr;
return IsSExt ? signExtendOperandForOther : zeroExtendOperandForOther;
}
Value *TypePromotionHelper::promoteOperandForTruncAndAnyExt(
llvm::Instruction *SExt, TypePromotionTransaction &TPT,
InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
SmallVectorImpl<Instruction *> *Exts,
SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI) {
Instruction *SExtOpnd = cast<Instruction>(SExt->getOperand(0));
Value *ExtVal = SExt;
bool HasMergedNonFreeExt = false;
if (isa<ZExtInst>(SExtOpnd)) {
HasMergedNonFreeExt = !TLI.isExtFree(SExtOpnd);
Value *ZExt =
TPT.createZExt(SExt, SExtOpnd->getOperand(0), SExt->getType());
TPT.replaceAllUsesWith(SExt, ZExt);
TPT.eraseInstruction(SExt);
ExtVal = ZExt;
} else {
TPT.setOperand(SExt, 0, SExtOpnd->getOperand(0));
}
CreatedInstsCost = 0;
if (SExtOpnd->use_empty())
TPT.eraseInstruction(SExtOpnd);
Instruction *ExtInst = dyn_cast<Instruction>(ExtVal);
if (!ExtInst || ExtInst->getType() != ExtInst->getOperand(0)->getType()) {
if (ExtInst) {
if (Exts)
Exts->push_back(ExtInst);
CreatedInstsCost = !TLI.isExtFree(ExtInst) && !HasMergedNonFreeExt;
}
return ExtVal;
}
Value *NextVal = ExtInst->getOperand(0);
TPT.eraseInstruction(ExtInst, NextVal);
return NextVal;
}
Value *TypePromotionHelper::promoteOperandForOther(
Instruction *Ext, TypePromotionTransaction &TPT,
InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
SmallVectorImpl<Instruction *> *Exts,
SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI,
bool IsSExt) {
Instruction *ExtOpnd = cast<Instruction>(Ext->getOperand(0));
CreatedInstsCost = 0;
if (!ExtOpnd->hasOneUse()) {
Value *Trunc = TPT.createTrunc(Ext, ExtOpnd->getType());
if (Instruction *ITrunc = dyn_cast<Instruction>(Trunc)) {
ITrunc->removeFromParent();
ITrunc->insertAfter(ExtOpnd);
if (Truncs)
Truncs->push_back(ITrunc);
}
TPT.replaceAllUsesWith(ExtOpnd, Trunc);
TPT.setOperand(Ext, 0, ExtOpnd);
}
PromotedInsts.insert(std::pair<Instruction *, TypeIsSExt>(
ExtOpnd, TypeIsSExt(ExtOpnd->getType(), IsSExt)));
TPT.mutateType(ExtOpnd, Ext->getType());
TPT.replaceAllUsesWith(Ext, ExtOpnd);
Instruction *ExtForOpnd = Ext;
DEBUG(dbgs() << "Propagate Ext to operands\n");
for (int OpIdx = 0, EndOpIdx = ExtOpnd->getNumOperands(); OpIdx != EndOpIdx;
++OpIdx) {
DEBUG(dbgs() << "Operand:\n" << *(ExtOpnd->getOperand(OpIdx)) << '\n');
if (ExtOpnd->getOperand(OpIdx)->getType() == Ext->getType() ||
!shouldExtOperand(ExtOpnd, OpIdx)) {
DEBUG(dbgs() << "No need to propagate\n");
continue;
}
Value *Opnd = ExtOpnd->getOperand(OpIdx);
if (const ConstantInt *Cst = dyn_cast<ConstantInt>(Opnd)) {
DEBUG(dbgs() << "Statically extend\n");
unsigned BitWidth = Ext->getType()->getIntegerBitWidth();
APInt CstVal = IsSExt ? Cst->getValue().sext(BitWidth)
: Cst->getValue().zext(BitWidth);
TPT.setOperand(ExtOpnd, OpIdx, ConstantInt::get(Ext->getType(), CstVal));
continue;
}
if (isa<UndefValue>(Opnd)) {
DEBUG(dbgs() << "Statically extend\n");
TPT.setOperand(ExtOpnd, OpIdx, UndefValue::get(Ext->getType()));
continue;
}
if (!ExtForOpnd) {
DEBUG(dbgs() << "More operands to ext\n");
Value *ValForExtOpnd = IsSExt ? TPT.createSExt(Ext, Opnd, Ext->getType())
: TPT.createZExt(Ext, Opnd, Ext->getType());
if (!isa<Instruction>(ValForExtOpnd)) {
TPT.setOperand(ExtOpnd, OpIdx, ValForExtOpnd);
continue;
}
ExtForOpnd = cast<Instruction>(ValForExtOpnd);
}
if (Exts)
Exts->push_back(ExtForOpnd);
TPT.setOperand(ExtForOpnd, 0, Opnd);
TPT.moveBefore(ExtForOpnd, ExtOpnd);
TPT.setOperand(ExtOpnd, OpIdx, ExtForOpnd);
CreatedInstsCost += !TLI.isExtFree(ExtForOpnd);
ExtForOpnd = nullptr;
}
if (ExtForOpnd == Ext) {
DEBUG(dbgs() << "Extension is useless now\n");
TPT.eraseInstruction(Ext);
}
return ExtOpnd;
}
bool AddressingModeMatcher::isPromotionProfitable(
unsigned NewCost, unsigned OldCost, Value *PromotedOperand) const {
DEBUG(dbgs() << "OldCost: " << OldCost << "\tNewCost: " << NewCost << '\n');
if (NewCost > OldCost)
return false;
if (NewCost < OldCost)
return true;
return isPromotedInstructionLegal(TLI, DL, PromotedOperand);
}
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: {
auto AS = AddrInst->getType()->getPointerAddressSpace();
auto PtrTy = MVT::getIntegerVT(DL.getPointerSizeInBits(AS));
if (TLI.getValueType(DL, AddrInst->getOperand(0)->getType()) == PtrTy)
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::AddrSpaceCast: {
unsigned SrcAS
= AddrInst->getOperand(0)->getType()->getPointerAddressSpace();
unsigned DestAS = AddrInst->getType()->getPointerAddressSpace();
if (TLI.isNoopAddrSpaceCast(SrcAS, DestAS))
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;
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 = DL.getStructLayout(STy);
unsigned Idx =
cast<ConstantInt>(AddrInst->getOperand(i))->getZExtValue();
ConstantOffset += SL->getElementOffset(Idx);
} else {
uint64_t TypeSize = DL.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(DL, AddrMode, AccessTy, AddrSpace)) {
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:
case Instruction::ZExt: {
Instruction *Ext = dyn_cast<Instruction>(AddrInst);
if (!Ext)
return false;
TypePromotionHelper::Action TPH =
TypePromotionHelper::getAction(Ext, InsertedInsts, TLI, PromotedInsts);
if (!TPH)
return false;
TypePromotionTransaction::ConstRestorationPt LastKnownGood =
TPT.getRestorationPoint();
unsigned CreatedInstsCost = 0;
unsigned ExtCost = !TLI.isExtFree(Ext);
Value *PromotedOperand =
TPH(Ext, TPT, PromotedInsts, CreatedInstsCost, nullptr, nullptr, TLI);
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(CreatedInstsCost,
ExtCost + (AddrModeInsts.size() - OldSize),
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(DL, AddrMode, AccessTy, AddrSpace))
return true;
AddrMode.BaseOffs -= CI->getSExtValue();
} else if (GlobalValue *GV = dyn_cast<GlobalValue>(Addr)) {
if (!AddrMode.BaseGV) {
AddrMode.BaseGV = GV;
if (TLI.isLegalAddressingMode(DL, AddrMode, AccessTy, AddrSpace))
return true;
AddrMode.BaseGV = nullptr;
}
} 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(DL, AddrMode, AccessTy, AddrSpace))
return true;
AddrMode.HasBaseReg = false;
AddrMode.BaseReg = nullptr;
}
if (AddrMode.Scale == 0) {
AddrMode.Scale = 1;
AddrMode.ScaledReg = Addr;
if (TLI.isLegalAddressingMode(DL, AddrMode, AccessTy, AddrSpace))
return true;
AddrMode.Scale = 0;
AddrMode.ScaledReg = nullptr;
}
TPT.rollback(LastKnownGood);
return false;
}
static bool IsOperandAMemoryOperand(CallInst *CI, InlineAsm *IA, Value *OpVal,
const TargetMachine &TM) {
const Function *F = CI->getParent()->getParent();
const TargetLowering *TLI = TM.getSubtargetImpl(*F)->getTargetLowering();
const TargetRegisterInfo *TRI = TM.getSubtargetImpl(*F)->getRegisterInfo();
TargetLowering::AsmOperandInfoVector TargetConstraints =
TLI->ParseConstraints(F->getParent()->getDataLayout(), TRI,
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,
SmallPtrSetImpl<Instruction *> &ConsideredInsts, const TargetMachine &TM) {
if (!ConsideredInsts.insert(I).second)
return false;
if (!MightBeFoldableInst(I))
return true;
for (Use &U : I->uses()) {
Instruction *UserI = cast<Instruction>(U.getUser());
if (LoadInst *LI = dyn_cast<LoadInst>(UserI)) {
MemoryUses.push_back(std::make_pair(LI, U.getOperandNo()));
continue;
}
if (StoreInst *SI = dyn_cast<StoreInst>(UserI)) {
unsigned opNo = U.getOperandNo();
if (opNo == 0) return true; MemoryUses.push_back(std::make_pair(SI, opNo));
continue;
}
if (CallInst *CI = dyn_cast<CallInst>(UserI)) {
InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledValue());
if (!IA) return true;
if (!IsOperandAMemoryOperand(CI, IA, I, TM))
return true;
continue;
}
if (FindAllMemoryUses(UserI, MemoryUses, ConsideredInsts, TM))
return true;
}
return false;
}
bool AddressingModeMatcher::valueAlreadyLiveAtInst(Value *Val,Value *KnownLive1,
Value *KnownLive2) {
if (Val == nullptr || 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 = nullptr;
if (valueAlreadyLiveAtInst(ScaledReg, AMBefore.BaseReg, AMBefore.ScaledReg))
ScaledReg = nullptr;
if (!BaseReg && !ScaledReg)
return true;
SmallVector<std::pair<Instruction*,unsigned>, 16> MemoryUses;
SmallPtrSet<Instruction*, 16> ConsideredInsts;
if (FindAllMemoryUses(I, MemoryUses, ConsideredInsts, TM))
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);
PointerType *AddrTy = dyn_cast<PointerType>(Address->getType());
if (!AddrTy)
return false;
Type *AddressAccessTy = AddrTy->getElementType();
unsigned AS = AddrTy->getAddressSpace();
ExtAddrMode Result;
TypePromotionTransaction::ConstRestorationPt LastKnownGood =
TPT.getRestorationPoint();
AddressingModeMatcher Matcher(MatchedAddrModeInsts, TM, AddressAccessTy, AS,
MemoryInst, Result, InsertedInsts,
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, unsigned AddrSpace) {
Value *Repl = Addr;
SmallVector<Value*, 8> worklist;
SmallPtrSet<Value*, 16> Visited;
worklist.push_back(Addr);
Value *Consensus = nullptr;
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).second) {
Consensus = nullptr;
break;
}
if (PHINode *P = dyn_cast<PHINode>(V)) {
for (Value *IncValue : P->incoming_values())
worklist.push_back(IncValue);
continue;
}
SmallVector<Instruction*, 16> NewAddrModeInsts;
ExtAddrMode NewAddrMode = AddressingModeMatcher::Match(
V, AccessTy, AddrSpace, MemoryInst, NewAddrModeInsts, *TM,
InsertedInsts, 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 = nullptr;
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 << "\n");
if (SunkAddr->getType() != Addr->getType())
SunkAddr = Builder.CreateBitCast(SunkAddr, Addr->getType());
} else if (AddrSinkUsingGEPs ||
(!AddrSinkUsingGEPs.getNumOccurrences() && TM &&
TM->getSubtargetImpl(*MemoryInst->getParent()->getParent())
->useAA())) {
DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for "
<< *MemoryInst << "\n");
Type *IntPtrTy = DL->getIntPtrType(Addr->getType());
Value *ResultPtr = nullptr, *ResultIndex = nullptr;
if (AddrMode.BaseReg && AddrMode.BaseReg->getType()->isPointerTy()) {
ResultPtr = AddrMode.BaseReg;
AddrMode.BaseReg = nullptr;
}
if (AddrMode.Scale && AddrMode.ScaledReg->getType()->isPointerTy()) {
if (ResultPtr || AddrMode.Scale != 1)
return false;
ResultPtr = AddrMode.ScaledReg;
AddrMode.Scale = 0;
}
if (AddrMode.BaseGV) {
if (ResultPtr)
return false;
ResultPtr = AddrMode.BaseGV;
}
if (!ResultPtr && AddrMode.BaseReg) {
ResultPtr =
Builder.CreateIntToPtr(AddrMode.BaseReg, Addr->getType(), "sunkaddr");
AddrMode.BaseReg = nullptr;
} else if (!ResultPtr && AddrMode.Scale == 1) {
ResultPtr =
Builder.CreateIntToPtr(AddrMode.ScaledReg, Addr->getType(), "sunkaddr");
AddrMode.Scale = 0;
}
if (!ResultPtr &&
!AddrMode.BaseReg && !AddrMode.Scale && !AddrMode.BaseOffs) {
SunkAddr = Constant::getNullValue(Addr->getType());
} else if (!ResultPtr) {
return false;
} else {
Type *I8PtrTy =
Builder.getInt8PtrTy(Addr->getType()->getPointerAddressSpace());
Type *I8Ty = Builder.getInt8Ty();
if (AddrMode.BaseReg) {
Value *V = AddrMode.BaseReg;
if (V->getType() != IntPtrTy)
V = Builder.CreateIntCast(V, IntPtrTy, true, "sunkaddr");
ResultIndex = V;
}
if (AddrMode.Scale) {
Value *V = AddrMode.ScaledReg;
if (V->getType() == IntPtrTy) {
} else if (cast<IntegerType>(IntPtrTy)->getBitWidth() <
cast<IntegerType>(V->getType())->getBitWidth()) {
V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr");
} else {
Instruction *I = dyn_cast_or_null<Instruction>(ResultIndex);
if (I && (ResultIndex != AddrMode.BaseReg))
I->eraseFromParent();
return false;
}
if (AddrMode.Scale != 1)
V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy, AddrMode.Scale),
"sunkaddr");
if (ResultIndex)
ResultIndex = Builder.CreateAdd(ResultIndex, V, "sunkaddr");
else
ResultIndex = V;
}
if (AddrMode.BaseOffs) {
Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs);
if (ResultIndex) {
if (ResultPtr->getType() != I8PtrTy)
ResultPtr = Builder.CreateBitCast(ResultPtr, I8PtrTy);
ResultPtr = Builder.CreateGEP(I8Ty, ResultPtr, ResultIndex, "sunkaddr");
}
ResultIndex = V;
}
if (!ResultIndex) {
SunkAddr = ResultPtr;
} else {
if (ResultPtr->getType() != I8PtrTy)
ResultPtr = Builder.CreateBitCast(ResultPtr, I8PtrTy);
SunkAddr = Builder.CreateGEP(I8Ty, ResultPtr, ResultIndex, "sunkaddr");
}
if (SunkAddr->getType() != Addr->getType())
SunkAddr = Builder.CreateBitCast(SunkAddr, Addr->getType());
}
} else {
DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for "
<< *MemoryInst << "\n");
Type *IntPtrTy = DL->getIntPtrType(Addr->getType());
Value *Result = nullptr;
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_or_null<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)
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.getNodePtrUnchecked()) {
CurInstIterator = BB->begin();
SunkAddrs.clear();
}
}
++NumMemoryInsts;
return true;
}
bool CodeGenPrepare::optimizeInlineAsmInst(CallInst *CS) {
bool MadeChange = false;
const TargetRegisterInfo *TRI =
TM->getSubtargetImpl(*CS->getParent()->getParent())->getRegisterInfo();
TargetLowering::AsmOperandInfoVector TargetConstraints =
TLI->ParseConstraints(*DL, TRI, 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(), ~0u);
} else if (OpInfo.Type == InlineAsm::isInput)
ArgNo++;
}
return MadeChange;
}
static bool hasSameExtUse(Instruction *Inst, const TargetLowering &TLI) {
assert(!Inst->use_empty() && "Input must have at least one use");
const Instruction *FirstUser = cast<Instruction>(*Inst->user_begin());
bool IsSExt = isa<SExtInst>(FirstUser);
Type *ExtTy = FirstUser->getType();
for (const User *U : Inst->users()) {
const Instruction *UI = cast<Instruction>(U);
if ((IsSExt && !isa<SExtInst>(UI)) || (!IsSExt && !isa<ZExtInst>(UI)))
return false;
Type *CurTy = UI->getType();
if (CurTy == ExtTy)
continue;
if (IsSExt)
return false;
Type *NarrowTy;
Type *LargeTy;
if (ExtTy->getScalarType()->getIntegerBitWidth() >
CurTy->getScalarType()->getIntegerBitWidth()) {
NarrowTy = CurTy;
LargeTy = ExtTy;
} else {
NarrowTy = ExtTy;
LargeTy = CurTy;
}
if (!TLI.isZExtFree(NarrowTy, LargeTy))
return false;
}
return true;
}
bool CodeGenPrepare::extLdPromotion(TypePromotionTransaction &TPT,
LoadInst *&LI, Instruction *&Inst,
const SmallVectorImpl<Instruction *> &Exts,
unsigned CreatedInstsCost = 0) {
for (auto I : Exts) {
if ((LI = dyn_cast<LoadInst>(I->getOperand(0)))) {
Inst = I;
return false;
}
if (!TLI || !TLI->enableExtLdPromotion() || DisableExtLdPromotion)
continue;
TypePromotionHelper::Action TPH = TypePromotionHelper::getAction(
I, InsertedInsts, *TLI, PromotedInsts);
if (!TPH)
continue;
TypePromotionTransaction::ConstRestorationPt LastKnownGood =
TPT.getRestorationPoint();
SmallVector<Instruction *, 4> NewExts;
unsigned NewCreatedInstsCost = 0;
unsigned ExtCost = !TLI->isExtFree(I);
Value *PromotedVal = TPH(I, TPT, PromotedInsts, NewCreatedInstsCost,
&NewExts, nullptr, *TLI);
assert(PromotedVal &&
"TypePromotionHelper should have filtered out those cases");
long long TotalCreatedInstsCost = CreatedInstsCost + NewCreatedInstsCost;
TotalCreatedInstsCost -= ExtCost;
if (!StressExtLdPromotion &&
(TotalCreatedInstsCost > 1 ||
!isPromotedInstructionLegal(*TLI, *DL, PromotedVal))) {
TPT.rollback(LastKnownGood);
continue;
}
(void)extLdPromotion(TPT, LI, Inst, NewExts, TotalCreatedInstsCost);
if (LI && (StressExtLdPromotion || NewCreatedInstsCost <= ExtCost ||
(LI->hasOneUse() || hasSameExtUse(LI, *TLI))))
return true;
TPT.rollback(LastKnownGood);
}
LI = nullptr;
Inst = nullptr;
return false;
}
bool CodeGenPrepare::moveExtToFormExtLoad(Instruction *&I) {
TypePromotionTransaction TPT;
TypePromotionTransaction::ConstRestorationPt LastKnownGood =
TPT.getRestorationPoint();
SmallVector<Instruction *, 1> Exts;
Exts.push_back(I);
LoadInst *LI = nullptr;
Instruction *OldExt = I;
bool HasPromoted = extLdPromotion(TPT, LI, I, Exts);
if (!LI || !I) {
assert(!HasPromoted && !LI && "If we did not match any load instruction "
"the code must remain the same");
I = OldExt;
return false;
}
if (!HasPromoted && LI->getParent() == I->getParent())
return false;
EVT VT = TLI->getValueType(*DL, I->getType());
EVT LoadVT = TLI->getValueType(*DL, LI->getType());
if (!LI->hasOneUse() && TLI &&
(TLI->isTypeLegal(LoadVT) || !TLI->isTypeLegal(VT)) &&
!TLI->isTruncateFree(I->getType(), LI->getType())) {
I = OldExt;
TPT.rollback(LastKnownGood);
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, VT, LoadVT)) {
I = OldExt;
TPT.rollback(LastKnownGood);
return false;
}
TPT.commit();
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 (User *U : I->users()) {
Instruction *UI = cast<Instruction>(U);
BasicBlock *UserBB = UI->getParent();
if (UserBB == DefBB) continue;
DefIsLiveOut = true;
break;
}
if (!DefIsLiveOut)
return false;
for (User *U : Src->users()) {
Instruction *UI = cast<Instruction>(U);
BasicBlock *UserBB = UI->getParent();
if (UserBB == DefBB) continue;
if (isa<PHINode>(UI) || isa<LoadInst>(UI) || isa<StoreInst>(UI))
return false;
}
DenseMap<BasicBlock*, Instruction*> InsertedTruncs;
bool MadeChange = false;
for (Use &U : Src->uses()) {
Instruction *User = cast<Instruction>(U.getUser());
BasicBlock *UserBB = User->getParent();
if (UserBB == DefBB) continue;
Instruction *&InsertedTrunc = InsertedTruncs[UserBB];
if (!InsertedTrunc) {
BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
assert(InsertPt != UserBB->end());
InsertedTrunc = new TruncInst(I, Src->getType(), "", &*InsertPt);
InsertedInsts.insert(InsertedTrunc);
}
U = InsertedTrunc;
++NumExtUses;
MadeChange = true;
}
return MadeChange;
}
static bool sinkSelectOperand(const TargetTransformInfo *TTI, Value *V) {
auto *I = dyn_cast<Instruction>(V);
return I && I->hasOneUse() && isSafeToSpeculativelyExecute(I) &&
TTI->getUserCost(I) >= TargetTransformInfo::TCC_Expensive;
}
static bool isFormingBranchFromSelectProfitable(const TargetTransformInfo *TTI,
SelectInst *SI) {
CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
if (!Cmp || !Cmp->hasOneUse())
return false;
Value *CmpOp0 = Cmp->getOperand(0);
Value *CmpOp1 = Cmp->getOperand(1);
if ((isa<LoadInst>(CmpOp0) && CmpOp0->hasOneUse()) ||
(isa<LoadInst>(CmpOp1) && CmpOp1->hasOneUse()))
return true;
if (sinkSelectOperand(TTI, SI->getTrueValue()) ||
sinkSelectOperand(TTI, SI->getFalseValue()))
return true;
return false;
}
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(TTI, SI))
return false;
}
ModifiedDT = true;
BasicBlock *StartBlock = SI->getParent();
BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(SI));
BasicBlock *EndBlock = StartBlock->splitBasicBlock(SplitPt, "select.end");
StartBlock->getTerminator()->eraseFromParent();
BasicBlock *TrueBlock = nullptr;
BasicBlock *FalseBlock = nullptr;
if (sinkSelectOperand(TTI, SI->getTrueValue())) {
TrueBlock = BasicBlock::Create(SI->getContext(), "select.true.sink",
EndBlock->getParent(), EndBlock);
auto *TrueBranch = BranchInst::Create(EndBlock, TrueBlock);
auto *TrueInst = cast<Instruction>(SI->getTrueValue());
TrueInst->moveBefore(TrueBranch);
}
if (sinkSelectOperand(TTI, SI->getFalseValue())) {
FalseBlock = BasicBlock::Create(SI->getContext(), "select.false.sink",
EndBlock->getParent(), EndBlock);
auto *FalseBranch = BranchInst::Create(EndBlock, FalseBlock);
auto *FalseInst = cast<Instruction>(SI->getFalseValue());
FalseInst->moveBefore(FalseBranch);
}
if (TrueBlock == FalseBlock) {
assert(TrueBlock == nullptr &&
"Unexpected basic block transform while optimizing select");
FalseBlock = BasicBlock::Create(SI->getContext(), "select.false",
EndBlock->getParent(), EndBlock);
BranchInst::Create(EndBlock, FalseBlock);
}
if (TrueBlock == nullptr) {
BranchInst::Create(EndBlock, FalseBlock, SI->getCondition(), SI);
TrueBlock = StartBlock;
} else if (FalseBlock == nullptr) {
BranchInst::Create(TrueBlock, EndBlock, SI->getCondition(), SI);
FalseBlock = StartBlock;
} else {
BranchInst::Create(TrueBlock, FalseBlock, SI->getCondition(), SI);
}
PHINode *PN = PHINode::Create(SI->getType(), 2, "", &EndBlock->front());
PN->takeName(SI);
PN->addIncoming(SI->getTrueValue(), TrueBlock);
PN->addIncoming(SI->getFalseValue(), FalseBlock);
SI->replaceAllUsesWith(PN);
SI->eraseFromParent();
CurInstIterator = StartBlock->end();
++NumSelectsExpanded;
return true;
}
static 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 (User *U : SVI->users()) {
Instruction *UI = cast<Instruction>(U);
BasicBlock *UserBB = UI->getParent();
if (UserBB == DefBB) continue;
if (!UI->isShift()) continue;
Instruction *&InsertedShuffle = InsertedShuffles[UserBB];
if (!InsertedShuffle) {
BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
assert(InsertPt != UserBB->end());
InsertedShuffle =
new ShuffleVectorInst(SVI->getOperand(0), SVI->getOperand(1),
SVI->getOperand(2), "", &*InsertPt);
}
UI->replaceUsesOfWith(SVI, InsertedShuffle);
MadeChange = true;
}
if (SVI->use_empty()) {
SVI->eraseFromParent();
MadeChange = true;
}
return MadeChange;
}
bool CodeGenPrepare::optimizeSwitchInst(SwitchInst *SI) {
if (!TLI || !DL)
return false;
Value *Cond = SI->getCondition();
Type *OldType = Cond->getType();
LLVMContext &Context = Cond->getContext();
MVT RegType = TLI->getRegisterType(Context, TLI->getValueType(*DL, OldType));
unsigned RegWidth = RegType.getSizeInBits();
if (RegWidth <= cast<IntegerType>(OldType)->getBitWidth())
return false;
auto *NewType = Type::getIntNTy(Context, RegWidth);
Instruction::CastOps ExtType = Instruction::ZExt;
if (auto *Arg = dyn_cast<Argument>(Cond))
if (Arg->hasSExtAttr())
ExtType = Instruction::SExt;
auto *ExtInst = CastInst::Create(ExtType, Cond, NewType);
ExtInst->insertBefore(SI);
SI->setCondition(ExtInst);
for (SwitchInst::CaseIt Case : SI->cases()) {
APInt NarrowConst = Case.getCaseValue()->getValue();
APInt WideConst = (ExtType == Instruction::ZExt) ?
NarrowConst.zext(RegWidth) : NarrowConst.sext(RegWidth);
Case.setValue(ConstantInt::get(Context, WideConst));
}
return true;
}
namespace {
class VectorPromoteHelper {
const DataLayout &DL;
const TargetLowering &TLI;
const TargetTransformInfo &TTI;
Instruction *Transition;
SmallVector<Instruction *, 4> InstsToBePromoted;
unsigned StoreExtractCombineCost;
Instruction *CombineInst;
Instruction *getEndOfTransition() const {
if (InstsToBePromoted.empty())
return Transition;
return InstsToBePromoted.back();
}
unsigned getTransitionOriginalValueIdx() const {
assert(isa<ExtractElementInst>(Transition) &&
"Other kind of transitions are not supported yet");
return 0;
}
unsigned getTransitionIdx() const {
assert(isa<ExtractElementInst>(Transition) &&
"Other kind of transitions are not supported yet");
return 1;
}
Type *getTransitionType() const {
return Transition->getOperand(getTransitionOriginalValueIdx())->getType();
}
void promoteImpl(Instruction *ToBePromoted);
bool isProfitableToPromote() {
Value *ValIdx = Transition->getOperand(getTransitionOriginalValueIdx());
unsigned Index = isa<ConstantInt>(ValIdx)
? cast<ConstantInt>(ValIdx)->getZExtValue()
: -1;
Type *PromotedType = getTransitionType();
StoreInst *ST = cast<StoreInst>(CombineInst);
unsigned AS = ST->getPointerAddressSpace();
unsigned Align = ST->getAlignment();
if (!TLI.allowsMisalignedMemoryAccesses(
TLI.getValueType(DL, ST->getValueOperand()->getType()), AS,
Align)) {
return false;
}
uint64_t ScalarCost =
TTI.getVectorInstrCost(Transition->getOpcode(), PromotedType, Index);
uint64_t VectorCost = StoreExtractCombineCost;
for (const auto &Inst : InstsToBePromoted) {
Value *Arg0 = Inst->getOperand(0);
bool IsArg0Constant = isa<UndefValue>(Arg0) || isa<ConstantInt>(Arg0) ||
isa<ConstantFP>(Arg0);
TargetTransformInfo::OperandValueKind Arg0OVK =
IsArg0Constant ? TargetTransformInfo::OK_UniformConstantValue
: TargetTransformInfo::OK_AnyValue;
TargetTransformInfo::OperandValueKind Arg1OVK =
!IsArg0Constant ? TargetTransformInfo::OK_UniformConstantValue
: TargetTransformInfo::OK_AnyValue;
ScalarCost += TTI.getArithmeticInstrCost(
Inst->getOpcode(), Inst->getType(), Arg0OVK, Arg1OVK);
VectorCost += TTI.getArithmeticInstrCost(Inst->getOpcode(), PromotedType,
Arg0OVK, Arg1OVK);
}
DEBUG(dbgs() << "Estimated cost of computation to be promoted:\nScalar: "
<< ScalarCost << "\nVector: " << VectorCost << '\n');
return ScalarCost > VectorCost;
}
Value *getConstantVector(Constant *Val, bool UseSplat) const {
unsigned ExtractIdx = UINT_MAX;
if (!UseSplat) {
Value *ValExtractIdx = Transition->getOperand(getTransitionIdx());
if (ConstantInt *CstVal = dyn_cast<ConstantInt>(ValExtractIdx))
ExtractIdx = CstVal->getSExtValue();
else
UseSplat = true;
}
unsigned End = getTransitionType()->getVectorNumElements();
if (UseSplat)
return ConstantVector::getSplat(End, Val);
SmallVector<Constant *, 4> ConstVec;
UndefValue *UndefVal = UndefValue::get(Val->getType());
for (unsigned Idx = 0; Idx != End; ++Idx) {
if (Idx == ExtractIdx)
ConstVec.push_back(Val);
else
ConstVec.push_back(UndefVal);
}
return ConstantVector::get(ConstVec);
}
static bool canCauseUndefinedBehavior(const Instruction *Use,
unsigned OperandIdx) {
if (OperandIdx != 1)
return false;
switch (Use->getOpcode()) {
default:
return false;
case Instruction::SDiv:
case Instruction::UDiv:
case Instruction::SRem:
case Instruction::URem:
return true;
case Instruction::FDiv:
case Instruction::FRem:
return !Use->hasNoNaNs();
}
llvm_unreachable(nullptr);
}
public:
VectorPromoteHelper(const DataLayout &DL, const TargetLowering &TLI,
const TargetTransformInfo &TTI, Instruction *Transition,
unsigned CombineCost)
: DL(DL), TLI(TLI), TTI(TTI), Transition(Transition),
StoreExtractCombineCost(CombineCost), CombineInst(nullptr) {
assert(Transition && "Do not know how to promote null");
}
bool canPromote(const Instruction *ToBePromoted) const {
return isa<BinaryOperator>(ToBePromoted);
}
bool shouldPromote(const Instruction *ToBePromoted) const {
for (const Use &U : ToBePromoted->operands()) {
const Value *Val = U.get();
if (Val == getEndOfTransition()) {
if (canCauseUndefinedBehavior(ToBePromoted, U.getOperandNo()))
return false;
continue;
}
if (!isa<ConstantInt>(Val) && !isa<UndefValue>(Val) &&
!isa<ConstantFP>(Val))
return false;
}
int ISDOpcode = TLI.InstructionOpcodeToISD(ToBePromoted->getOpcode());
if (!ISDOpcode)
return false;
return StressStoreExtract ||
TLI.isOperationLegalOrCustom(
ISDOpcode, TLI.getValueType(DL, getTransitionType(), true));
}
bool canCombine(const Instruction *Use) { return isa<StoreInst>(Use); }
void enqueueForPromotion(Instruction *ToBePromoted) {
InstsToBePromoted.push_back(ToBePromoted);
}
void recordCombineInstruction(Instruction *ToBeCombined) {
assert(canCombine(ToBeCombined) && "Unsupported instruction to combine");
CombineInst = ToBeCombined;
}
bool promote() {
if (InstsToBePromoted.empty() || !CombineInst)
return false;
if (!StressStoreExtract && !isProfitableToPromote())
return false;
for (auto &ToBePromoted : InstsToBePromoted)
promoteImpl(ToBePromoted);
InstsToBePromoted.clear();
return true;
}
};
}
void VectorPromoteHelper::promoteImpl(Instruction *ToBePromoted) {
assert(ToBePromoted->getType() == Transition->getType() &&
"The type of the result of the transition does not match "
"the final type");
ToBePromoted->replaceAllUsesWith(Transition);
Type *TransitionTy = getTransitionType();
ToBePromoted->mutateType(TransitionTy);
for (Use &U : ToBePromoted->operands()) {
Value *Val = U.get();
Value *NewVal = nullptr;
if (Val == Transition)
NewVal = Transition->getOperand(getTransitionOriginalValueIdx());
else if (isa<UndefValue>(Val) || isa<ConstantInt>(Val) ||
isa<ConstantFP>(Val)) {
NewVal = getConstantVector(
cast<Constant>(Val),
isa<UndefValue>(Val) ||
canCauseUndefinedBehavior(ToBePromoted, U.getOperandNo()));
} else
llvm_unreachable("Did you modified shouldPromote and forgot to update "
"this?");
ToBePromoted->setOperand(U.getOperandNo(), NewVal);
}
Transition->removeFromParent();
Transition->insertAfter(ToBePromoted);
Transition->setOperand(getTransitionOriginalValueIdx(), ToBePromoted);
}
bool CodeGenPrepare::optimizeExtractElementInst(Instruction *Inst) {
unsigned CombineCost = UINT_MAX;
if (DisableStoreExtract || !TLI ||
(!StressStoreExtract &&
!TLI->canCombineStoreAndExtract(Inst->getOperand(0)->getType(),
Inst->getOperand(1), CombineCost)))
return false;
BasicBlock *Parent = Inst->getParent();
DEBUG(dbgs() << "Found an interesting transition: " << *Inst << '\n');
VectorPromoteHelper VPH(*DL, *TLI, *TTI, Inst, CombineCost);
while (Inst->hasOneUse()) {
Instruction *ToBePromoted = cast<Instruction>(*Inst->user_begin());
DEBUG(dbgs() << "Use: " << *ToBePromoted << '\n');
if (ToBePromoted->getParent() != Parent) {
DEBUG(dbgs() << "Instruction to promote is in a different block ("
<< ToBePromoted->getParent()->getName()
<< ") than the transition (" << Parent->getName() << ").\n");
return false;
}
if (VPH.canCombine(ToBePromoted)) {
DEBUG(dbgs() << "Assume " << *Inst << '\n'
<< "will be combined with: " << *ToBePromoted << '\n');
VPH.recordCombineInstruction(ToBePromoted);
bool Changed = VPH.promote();
NumStoreExtractExposed += Changed;
return Changed;
}
DEBUG(dbgs() << "Try promoting.\n");
if (!VPH.canPromote(ToBePromoted) || !VPH.shouldPromote(ToBePromoted))
return false;
DEBUG(dbgs() << "Promoting is possible... Enqueue for promotion!\n");
VPH.enqueueForPromotion(ToBePromoted);
Inst = ToBePromoted;
}
return false;
}
bool CodeGenPrepare::optimizeInst(Instruction *I, bool& ModifiedDT) {
if (InsertedInsts.count(I))
return false;
if (PHINode *P = dyn_cast<PHINode>(I)) {
if (Value *V = SimplifyInstruction(P, *DL, TLInfo, nullptr)) {
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, *DL))
return true;
if (isa<ZExtInst>(I) || isa<SExtInst>(I)) {
if (TLI &&
TLI->getTypeAction(CI->getContext(),
TLI->getValueType(*DL, CI->getType())) ==
TargetLowering::TypeExpandInteger) {
return SinkCast(CI);
} else {
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)) {
stripInvariantGroupMetadata(*LI);
if (TLI) {
unsigned AS = LI->getPointerAddressSpace();
return optimizeMemoryInst(I, I->getOperand(0), LI->getType(), AS);
}
return false;
}
if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
stripInvariantGroupMetadata(*SI);
if (TLI) {
unsigned AS = SI->getPointerAddressSpace();
return optimizeMemoryInst(I, SI->getOperand(1),
SI->getOperand(0)->getType(), AS);
}
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, *DL);
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, ModifiedDT);
return true;
}
return false;
}
if (CallInst *CI = dyn_cast<CallInst>(I))
return optimizeCallInst(CI, ModifiedDT);
if (SelectInst *SI = dyn_cast<SelectInst>(I))
return optimizeSelectInst(SI);
if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I))
return optimizeShuffleVectorInst(SVI);
if (auto *Switch = dyn_cast<SwitchInst>(I))
return optimizeSwitchInst(Switch);
if (isa<ExtractElementInst>(I))
return optimizeExtractElementInst(I);
return false;
}
bool CodeGenPrepare::optimizeBlock(BasicBlock &BB, bool& ModifiedDT) {
SunkAddrs.clear();
bool MadeChange = false;
CurInstIterator = BB.begin();
while (CurInstIterator != BB.end()) {
MadeChange |= optimizeInst(&*CurInstIterator++, ModifiedDT);
if (ModifiedDT)
return true;
}
MadeChange |= dupRetToEnableTailCallOpts(&BB);
return MadeChange;
}
bool CodeGenPrepare::placeDbgValues(Function &F) {
bool MadeChange = false;
for (BasicBlock &BB : F) {
Instruction *PrevNonDbgInst = nullptr;
for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) {
Instruction *Insn = &*BI++;
DbgValueInst *DVI = dyn_cast<DbgValueInst>(Insn);
if (!DVI || (DVI->getValue() && isa<AllocaInst>(DVI->getValue()))) {
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;
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;
}
static bool extractBranchMetadata(BranchInst *BI,
uint64_t &ProbTrue, uint64_t &ProbFalse) {
assert(BI->isConditional() &&
"Looking for probabilities on unconditional branch?");
auto *ProfileData = BI->getMetadata(LLVMContext::MD_prof);
if (!ProfileData || ProfileData->getNumOperands() != 3)
return false;
const auto *CITrue =
mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(1));
const auto *CIFalse =
mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(2));
if (!CITrue || !CIFalse)
return false;
ProbTrue = CITrue->getValue().getZExtValue();
ProbFalse = CIFalse->getValue().getZExtValue();
return true;
}
static void scaleWeights(uint64_t &NewTrue, uint64_t &NewFalse) {
uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse;
uint32_t Scale = (NewMax / UINT32_MAX) + 1;
NewTrue = NewTrue / Scale;
NewFalse = NewFalse / Scale;
}
bool CodeGenPrepare::splitBranchCondition(Function &F) {
if (!TM || !TM->Options.EnableFastISel || !TLI || TLI->isJumpExpensive())
return false;
bool MadeChange = false;
for (auto &BB : F) {
BinaryOperator *LogicOp;
BasicBlock *TBB, *FBB;
if (!match(BB.getTerminator(), m_Br(m_OneUse(m_BinOp(LogicOp)), TBB, FBB)))
continue;
auto *Br1 = cast<BranchInst>(BB.getTerminator());
if (Br1->getMetadata(LLVMContext::MD_unpredictable))
continue;
unsigned Opc;
Value *Cond1, *Cond2;
if (match(LogicOp, m_And(m_OneUse(m_Value(Cond1)),
m_OneUse(m_Value(Cond2)))))
Opc = Instruction::And;
else if (match(LogicOp, m_Or(m_OneUse(m_Value(Cond1)),
m_OneUse(m_Value(Cond2)))))
Opc = Instruction::Or;
else
continue;
if (!match(Cond1, m_CombineOr(m_Cmp(), m_BinOp())) ||
!match(Cond2, m_CombineOr(m_Cmp(), m_BinOp())) )
continue;
DEBUG(dbgs() << "Before branch condition splitting\n"; BB.dump());
auto *InsertBefore = std::next(Function::iterator(BB))
.getNodePtrUnchecked();
auto TmpBB = BasicBlock::Create(BB.getContext(),
BB.getName() + ".cond.split",
BB.getParent(), InsertBefore);
Br1->setCondition(Cond1);
LogicOp->eraseFromParent();
if (Opc == Instruction::And)
Br1->setSuccessor(0, TmpBB);
else
Br1->setSuccessor(1, TmpBB);
auto *Br2 = IRBuilder<>(TmpBB).CreateCondBr(Cond2, TBB, FBB);
if (auto *I = dyn_cast<Instruction>(Cond2)) {
I->removeFromParent();
I->insertBefore(Br2);
}
if (Opc == Instruction::Or)
std::swap(TBB, FBB);
for (auto &I : *TBB) {
PHINode *PN = dyn_cast<PHINode>(&I);
if (!PN)
break;
int i;
while ((i = PN->getBasicBlockIndex(&BB)) >= 0)
PN->setIncomingBlock(i, TmpBB);
}
for (auto &I : *FBB) {
PHINode *PN = dyn_cast<PHINode>(&I);
if (!PN)
break;
auto *Val = PN->getIncomingValueForBlock(&BB);
PN->addIncoming(Val, TmpBB);
}
if (Opc == Instruction::Or) {
uint64_t TrueWeight, FalseWeight;
if (extractBranchMetadata(Br1, TrueWeight, FalseWeight)) {
uint64_t NewTrueWeight = TrueWeight;
uint64_t NewFalseWeight = TrueWeight + 2 * FalseWeight;
scaleWeights(NewTrueWeight, NewFalseWeight);
Br1->setMetadata(LLVMContext::MD_prof, MDBuilder(Br1->getContext())
.createBranchWeights(TrueWeight, FalseWeight));
NewTrueWeight = TrueWeight;
NewFalseWeight = 2 * FalseWeight;
scaleWeights(NewTrueWeight, NewFalseWeight);
Br2->setMetadata(LLVMContext::MD_prof, MDBuilder(Br2->getContext())
.createBranchWeights(TrueWeight, FalseWeight));
}
} else {
uint64_t TrueWeight, FalseWeight;
if (extractBranchMetadata(Br1, TrueWeight, FalseWeight)) {
uint64_t NewTrueWeight = 2 * TrueWeight + FalseWeight;
uint64_t NewFalseWeight = FalseWeight;
scaleWeights(NewTrueWeight, NewFalseWeight);
Br1->setMetadata(LLVMContext::MD_prof, MDBuilder(Br1->getContext())
.createBranchWeights(TrueWeight, FalseWeight));
NewTrueWeight = 2 * TrueWeight;
NewFalseWeight = FalseWeight;
scaleWeights(NewTrueWeight, NewFalseWeight);
Br2->setMetadata(LLVMContext::MD_prof, MDBuilder(Br2->getContext())
.createBranchWeights(TrueWeight, FalseWeight));
}
}
ModifiedDT = true;
MadeChange = true;
DEBUG(dbgs() << "After branch condition splitting\n"; BB.dump();
TmpBB->dump());
}
return MadeChange;
}
void CodeGenPrepare::stripInvariantGroupMetadata(Instruction &I) {
if (auto *InvariantMD = I.getMetadata(LLVMContext::MD_invariant_group))
I.dropUnknownNonDebugMetadata(InvariantMD->getMetadataID());
}