blob: 51f2a320b299fe082bbe29ac51f65bd735b9d218 [file] [log] [blame]
//===- CodeGenPrepare.cpp - Prepare a function for code generation --------===//
// The LLVM Compiler Infrastructure
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
// This pass munges the code in the input function to better prepare it for
// SelectionDAG-based code generation. This works around limitations in it's
// basic-block-at-a-time approach. It should eventually be removed.
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/BlockFrequencyInfo.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/ProfileSummaryInfo.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/CodeGen/Analysis.h"
#include "llvm/CodeGen/ISDOpcodes.h"
#include "llvm/CodeGen/MachineValueType.h"
#include "llvm/CodeGen/SelectionDAGNodes.h"
#include "llvm/CodeGen/TargetPassConfig.h"
#include "llvm/CodeGen/ValueTypes.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/Constant.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/GlobalValue.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InlineAsm.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Statepoint.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/IR/ValueMap.h"
#include "llvm/Pass.h"
#include "llvm/Support/BlockFrequency.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetLowering.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
#include "llvm/Target/TargetSubtargetInfo.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/BypassSlowDivision.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/SimplifyLibCalls.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <limits>
#include <memory>
#include <utility>
#include <vector>
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");
"Number of and mask instructions added to form ext loads");
STATISTIC(NumAndUses, "Number of uses of and mask 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(NumStoreExtractExposed, "Number of store(extractelement) exposed");
STATISTIC(NumMemCmpCalls, "Number of memcmp calls");
STATISTIC(NumMemCmpNotConstant, "Number of memcmp calls without constant size");
"Number of memcmp calls with size greater than max size");
STATISTIC(NumMemCmpInlined, "Number of inlined memcmp calls");
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(true),
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 "
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"));
static cl::opt<bool> DisablePreheaderProtect(
"disable-preheader-prot", cl::Hidden, cl::init(false),
cl::desc("Disable protection against removing loop preheaders"));
static cl::opt<bool> ProfileGuidedSectionPrefix(
"profile-guided-section-prefix", cl::Hidden, cl::init(true), cl::ZeroOrMore,
cl::desc("Use profile info to add section prefix for hot/cold functions"));
static cl::opt<unsigned> FreqRatioToSkipMerge(
"cgp-freq-ratio-to-skip-merge", cl::Hidden, cl::init(2),
cl::desc("Skip merging empty blocks if (frequency of empty block) / "
"(frequency of destination block) is greater than this ratio"));
static cl::opt<bool> ForceSplitStore(
"force-split-store", cl::Hidden, cl::init(false),
cl::desc("Force store splitting no matter what the target query says."));
static cl::opt<bool>
EnableTypePromotionMerge("cgp-type-promotion-merge", cl::Hidden,
cl::desc("Enable merging of redundant sexts when one is dominating"
" the other."), cl::init(true));
static cl::opt<unsigned> MemCmpNumLoadsPerBlock(
"memcmp-num-loads-per-block", cl::Hidden, cl::init(1),
cl::desc("The number of loads per basic block for inline expansion of "
"memcmp that is only being compared against zero."));
namespace {
using SetOfInstrs = SmallPtrSet<Instruction *, 16>;
using TypeIsSExt = PointerIntPair<Type *, 1, bool>;
using InstrToOrigTy = DenseMap<Instruction *, TypeIsSExt>;
using SExts = SmallVector<Instruction *, 16>;
using ValueToSExts = DenseMap<Value *, SExts>;
class TypePromotionTransaction;
class CodeGenPrepare : public FunctionPass {
const TargetMachine *TM = nullptr;
const TargetSubtargetInfo *SubtargetInfo;
const TargetLowering *TLI = nullptr;
const TargetRegisterInfo *TRI;
const TargetTransformInfo *TTI = nullptr;
const TargetLibraryInfo *TLInfo;
const LoopInfo *LI;
std::unique_ptr<BlockFrequencyInfo> BFI;
std::unique_ptr<BranchProbabilityInfo> BPI;
/// As we scan instructions optimizing them, this is the next instruction
/// to optimize. Transforms that can invalidate this should update it.
BasicBlock::iterator CurInstIterator;
/// Keeps track of non-local addresses that have been sunk into a block.
/// This allows us to avoid inserting duplicate code for blocks with
/// multiple load/stores of the same address.
ValueMap<Value*, Value*> SunkAddrs;
/// Keeps track of all instructions inserted for the current function.
SetOfInstrs InsertedInsts;
/// Keeps track of the type of the related instruction before their
/// promotion for the current function.
InstrToOrigTy PromotedInsts;
/// Keep track of instructions removed during promotion.
SetOfInstrs RemovedInsts;
/// Keep track of sext chains based on their initial value.
DenseMap<Value *, Instruction *> SeenChainsForSExt;
/// Keep track of SExt promoted.
ValueToSExts ValToSExtendedUses;
/// True if CFG is modified in any way.
bool ModifiedDT;
/// True if optimizing for size.
bool OptSize;
/// DataLayout for the Function being processed.
const DataLayout *DL = nullptr;
static char ID; // Pass identification, replacement for typeid
CodeGenPrepare() : FunctionPass(ID) {
bool runOnFunction(Function &F) override;
StringRef getPassName() const override { return "CodeGen Prepare"; }
void getAnalysisUsage(AnalysisUsage &AU) const override {
// FIXME: When we can selectively preserve passes, preserve the domtree.
bool eliminateFallThrough(Function &F);
bool eliminateMostlyEmptyBlocks(Function &F);
BasicBlock *findDestBlockOfMergeableEmptyBlock(BasicBlock *BB);
bool canMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const;
void eliminateMostlyEmptyBlock(BasicBlock *BB);
bool isMergingEmptyBlockProfitable(BasicBlock *BB, BasicBlock *DestBB,
bool isPreheader);
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 optimizeExt(Instruction *&I);
bool optimizeExtUses(Instruction *I);
bool optimizeLoadExt(LoadInst *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 canFormExtLd(const SmallVectorImpl<Instruction *> &MovedExts,
LoadInst *&LI, Instruction *&Inst, bool HasPromoted);
bool tryToPromoteExts(TypePromotionTransaction &TPT,
const SmallVectorImpl<Instruction *> &Exts,
SmallVectorImpl<Instruction *> &ProfitablyMovedExts,
unsigned CreatedInstsCost = 0);
bool mergeSExts(Function &F);
bool performAddressTypePromotion(
Instruction *&Inst,
bool AllowPromotionWithoutCommonHeader,
bool HasPromoted, TypePromotionTransaction &TPT,
SmallVectorImpl<Instruction *> &SpeculativelyMovedExts);
bool splitBranchCondition(Function &F);
bool simplifyOffsetableRelocate(Instruction &I);
bool splitIndirectCriticalEdges(Function &F);
} // end anonymous namespace
char CodeGenPrepare::ID = 0;
"Optimize for code generation", false, false)
"Optimize for code generation", false, false)
FunctionPass *llvm::createCodeGenPreparePass() { return new CodeGenPrepare(); }
bool CodeGenPrepare::runOnFunction(Function &F) {
if (skipFunction(F))
return false;
DL = &F.getParent()->getDataLayout();
bool EverMadeChange = false;
// Clear per function information.
ModifiedDT = false;
if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>()) {
TM = &TPC->getTM<TargetMachine>();
SubtargetInfo = TM->getSubtargetImpl(F);
TLI = SubtargetInfo->getTargetLowering();
TRI = SubtargetInfo->getRegisterInfo();
TLInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
OptSize = F.optForSize();
if (ProfileGuidedSectionPrefix) {
ProfileSummaryInfo *PSI =
if (PSI->isFunctionHotInCallGraph(&F))
else if (PSI->isFunctionColdInCallGraph(&F))
/// This optimization identifies DIV instructions that can be
/// profitably bypassed and carried out with a shorter, faster divide.
if (!OptSize && TLI && TLI->isSlowDivBypassed()) {
const DenseMap<unsigned int, unsigned int> &BypassWidths =
BasicBlock* BB = &*F.begin();
while (BB != nullptr) {
// bypassSlowDivision may create new BBs, but we don't want to reapply the
// optimization to those blocks.
BasicBlock* Next = BB->getNextNode();
EverMadeChange |= bypassSlowDivision(BB, BypassWidths);
BB = Next;
// Eliminate blocks that contain only PHI nodes and an
// unconditional branch.
EverMadeChange |= eliminateMostlyEmptyBlocks(F);
// llvm.dbg.value is far away from the value then iSel may not be able
// handle it properly. iSel will drop llvm.dbg.value if it can not
// find a node corresponding to the value.
EverMadeChange |= placeDbgValues(F);
if (!DisableBranchOpts)
EverMadeChange |= splitBranchCondition(F);
// Split some critical edges where one of the sources is an indirect branch,
// to help generate sane code for PHIs involving such edges.
EverMadeChange |= splitIndirectCriticalEdges(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);
// Restart BB iteration if the dominator tree of the Function was changed
if (ModifiedDTOnIteration)
if (EnableTypePromotionMerge && !ValToSExtendedUses.empty())
MadeChange |= mergeSExts(F);
// Really free removed instructions during promotion.
for (Instruction *I : RemovedInsts)
EverMadeChange |= MadeChange;
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))
// Delete the dead blocks and any of their dead successors.
MadeChange |= !WorkList.empty();
while (!WorkList.empty()) {
BasicBlock *BB = *WorkList.begin();
SmallVector<BasicBlock*, 2> Successors(succ_begin(BB), succ_end(BB));
for (SmallVectorImpl<BasicBlock*>::iterator
II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
if (pred_begin(*II) == pred_end(*II))
// Merge pairs of basic blocks with unconditional branches, connected by
// a single edge.
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))
for (auto &I : Statepoints)
EverMadeChange |= simplifyOffsetableRelocate(*I);
return EverMadeChange;
/// Merge basic blocks which are connected by a single edge, where one of the
/// basic blocks has a single successor pointing to the other basic block,
/// which has a single predecessor.
bool CodeGenPrepare::eliminateFallThrough(Function &F) {
bool Changed = false;
// Scan all of the blocks in the function, except for the entry block.
for (Function::iterator I = std::next(F.begin()), E = F.end(); I != E;) {
BasicBlock *BB = &*I++;
// If the destination block has a single pred, then this is a trivial
// edge, just collapse it.
BasicBlock *SinglePred = BB->getSinglePredecessor();
// Don't merge if BB's address is taken.
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");
// Remember if SinglePred was the entry block of the function.
// If so, we will need to move BB back to the entry position.
bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
MergeBasicBlockIntoOnlyPred(BB, nullptr);
if (isEntry && BB != &BB->getParent()->getEntryBlock())
// We have erased a block. Update the iterator.
I = BB->getIterator();
return Changed;
/// Find a destination block from BB if BB is mergeable empty block.
BasicBlock *CodeGenPrepare::findDestBlockOfMergeableEmptyBlock(BasicBlock *BB) {
// If this block doesn't end with an uncond branch, ignore it.
BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
if (!BI || !BI->isUnconditional())
return nullptr;
// If the instruction before the branch (skipping debug info) isn't a phi
// node, then other stuff is happening here.
BasicBlock::iterator BBI = BI->getIterator();
if (BBI != BB->begin()) {
while (isa<DbgInfoIntrinsic>(BBI)) {
if (BBI == BB->begin())
if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI))
return nullptr;
// Do not break infinite loops.
BasicBlock *DestBB = BI->getSuccessor(0);
if (DestBB == BB)
return nullptr;
if (!canMergeBlocks(BB, DestBB))
DestBB = nullptr;
return DestBB;
// Return the unique indirectbr predecessor of a block. This may return null
// even if such a predecessor exists, if it's not useful for splitting.
// If a predecessor is found, OtherPreds will contain all other (non-indirectbr)
// predecessors of BB.
static BasicBlock *
findIBRPredecessor(BasicBlock *BB, SmallVectorImpl<BasicBlock *> &OtherPreds) {
// If the block doesn't have any PHIs, we don't care about it, since there's
// no point in splitting it.
PHINode *PN = dyn_cast<PHINode>(BB->begin());
if (!PN)
return nullptr;
// Verify we have exactly one IBR predecessor.
// Conservatively bail out if one of the other predecessors is not a "regular"
// terminator (that is, not a switch or a br).
BasicBlock *IBB = nullptr;
for (unsigned Pred = 0, E = PN->getNumIncomingValues(); Pred != E; ++Pred) {
BasicBlock *PredBB = PN->getIncomingBlock(Pred);
TerminatorInst *PredTerm = PredBB->getTerminator();
switch (PredTerm->getOpcode()) {
case Instruction::IndirectBr:
if (IBB)
return nullptr;
IBB = PredBB;
case Instruction::Br:
case Instruction::Switch:
return nullptr;
return IBB;
// Split critical edges where the source of the edge is an indirectbr
// instruction. This isn't always possible, but we can handle some easy cases.
// This is useful because MI is unable to split such critical edges,
// which means it will not be able to sink instructions along those edges.
// This is especially painful for indirect branches with many successors, where
// we end up having to prepare all outgoing values in the origin block.
// Our normal algorithm for splitting critical edges requires us to update
// the outgoing edges of the edge origin block, but for an indirectbr this
// is hard, since it would require finding and updating the block addresses
// the indirect branch uses. But if a block only has a single indirectbr
// predecessor, with the others being regular branches, we can do it in a
// different way.
// Say we have A -> D, B -> D, I -> D where only I -> D is an indirectbr.
// We can split D into D0 and D1, where D0 contains only the PHIs from D,
// and D1 is the D block body. We can then duplicate D0 as D0A and D0B, and
// create the following structure:
// A -> D0A, B -> D0A, I -> D0B, D0A -> D1, D0B -> D1
bool CodeGenPrepare::splitIndirectCriticalEdges(Function &F) {
// Check whether the function has any indirectbrs, and collect which blocks
// they may jump to. Since most functions don't have indirect branches,
// this lowers the common case's overhead to O(Blocks) instead of O(Edges).
SmallSetVector<BasicBlock *, 16> Targets;
for (auto &BB : F) {
auto *IBI = dyn_cast<IndirectBrInst>(BB.getTerminator());
if (!IBI)
for (unsigned Succ = 0, E = IBI->getNumSuccessors(); Succ != E; ++Succ)
if (Targets.empty())
return false;
bool Changed = false;
for (BasicBlock *Target : Targets) {
SmallVector<BasicBlock *, 16> OtherPreds;
BasicBlock *IBRPred = findIBRPredecessor(Target, OtherPreds);
// If we did not found an indirectbr, or the indirectbr is the only
// incoming edge, this isn't the kind of edge we're looking for.
if (!IBRPred || OtherPreds.empty())
// Don't even think about ehpads/landingpads.
Instruction *FirstNonPHI = Target->getFirstNonPHI();
if (FirstNonPHI->isEHPad() || Target->isLandingPad())
BasicBlock *BodyBlock = Target->splitBasicBlock(FirstNonPHI, ".split");
// It's possible Target was its own successor through an indirectbr.
// In this case, the indirectbr now comes from BodyBlock.
if (IBRPred == Target)
IBRPred = BodyBlock;
// At this point Target only has PHIs, and BodyBlock has the rest of the
// block's body. Create a copy of Target that will be used by the "direct"
// preds.
ValueToValueMapTy VMap;
BasicBlock *DirectSucc = CloneBasicBlock(Target, VMap, ".clone", &F);
for (BasicBlock *Pred : OtherPreds) {
// If the target is a loop to itself, then the terminator of the split
// block needs to be updated.
if (Pred == Target)
BodyBlock->getTerminator()->replaceUsesOfWith(Target, DirectSucc);
Pred->getTerminator()->replaceUsesOfWith(Target, DirectSucc);
// Ok, now fix up the PHIs. We know the two blocks only have PHIs, and that
// they are clones, so the number of PHIs are the same.
// (a) Remove the edge coming from IBRPred from the "Direct" PHI
// (b) Leave that as the only edge in the "Indirect" PHI.
// (c) Merge the two in the body block.
BasicBlock::iterator Indirect = Target->begin(),
End = Target->getFirstNonPHI()->getIterator();
BasicBlock::iterator Direct = DirectSucc->begin();
BasicBlock::iterator MergeInsert = BodyBlock->getFirstInsertionPt();
assert(&*End == Target->getTerminator() &&
"Block was expected to only contain PHIs");
while (Indirect != End) {
PHINode *DirPHI = cast<PHINode>(Direct);
PHINode *IndPHI = cast<PHINode>(Indirect);
// Now, clean up - the direct block shouldn't get the indirect value,
// and vice versa.
// Advance the pointer here, to avoid invalidation issues when the old
// PHI is erased.
PHINode *NewIndPHI = PHINode::Create(IndPHI->getType(), 1, "ind", IndPHI);
// Create a PHI in the body block, to merge the direct and indirect
// predecessors.
PHINode *MergePHI =
PHINode::Create(IndPHI->getType(), 2, "merge", &*MergeInsert);
MergePHI->addIncoming(NewIndPHI, Target);
MergePHI->addIncoming(DirPHI, DirectSucc);
Changed = true;
return Changed;
/// Eliminate blocks that contain only PHI nodes, debug info directives, and an
/// unconditional branch. Passes before isel (e.g. LSR/loopsimplify) often split
/// edges in ways that are non-optimal for isel. Start by eliminating these
/// blocks so we can split them the way we want them.
bool CodeGenPrepare::eliminateMostlyEmptyBlocks(Function &F) {
SmallPtrSet<BasicBlock *, 16> Preheaders;
SmallVector<Loop *, 16> LoopList(LI->begin(), LI->end());
while (!LoopList.empty()) {
Loop *L = LoopList.pop_back_val();
LoopList.insert(LoopList.end(), L->begin(), L->end());
if (BasicBlock *Preheader = L->getLoopPreheader())
bool MadeChange = false;
// Note that this intentionally skips the entry block.
for (Function::iterator I = std::next(F.begin()), E = F.end(); I != E;) {
BasicBlock *BB = &*I++;
BasicBlock *DestBB = findDestBlockOfMergeableEmptyBlock(BB);
if (!DestBB ||
!isMergingEmptyBlockProfitable(BB, DestBB, Preheaders.count(BB)))
MadeChange = true;
return MadeChange;
bool CodeGenPrepare::isMergingEmptyBlockProfitable(BasicBlock *BB,
BasicBlock *DestBB,
bool isPreheader) {
// Do not delete loop preheaders if doing so would create a critical edge.
// Loop preheaders can be good locations to spill registers. If the
// preheader is deleted and we create a critical edge, registers may be
// spilled in the loop body instead.
if (!DisablePreheaderProtect && isPreheader &&
!(BB->getSinglePredecessor() &&
return false;
// Try to skip merging if the unique predecessor of BB is terminated by a
// switch or indirect branch instruction, and BB is used as an incoming block
// of PHIs in DestBB. In such case, merging BB and DestBB would cause ISel to
// add COPY instructions in the predecessor of BB instead of BB (if it is not
// merged). Note that the critical edge created by merging such blocks wont be
// split in MachineSink because the jump table is not analyzable. By keeping
// such empty block (BB), ISel will place COPY instructions in BB, not in the
// predecessor of BB.
BasicBlock *Pred = BB->getUniquePredecessor();
if (!Pred ||
!(isa<SwitchInst>(Pred->getTerminator()) ||
return true;
if (BB->getTerminator() != BB->getFirstNonPHI())
return true;
// We use a simple cost heuristic which determine skipping merging is
// profitable if the cost of skipping merging is less than the cost of
// merging : Cost(skipping merging) < Cost(merging BB), where the
// Cost(skipping merging) is Freq(BB) * (Cost(Copy) + Cost(Branch)), and
// the Cost(merging BB) is Freq(Pred) * Cost(Copy).
// Assuming Cost(Copy) == Cost(Branch), we could simplify it to :
// Freq(Pred) / Freq(BB) > 2.
// Note that if there are multiple empty blocks sharing the same incoming
// value for the PHIs in the DestBB, we consider them together. In such
// case, Cost(merging BB) will be the sum of their frequencies.
if (!isa<PHINode>(DestBB->begin()))
return true;
SmallPtrSet<BasicBlock *, 16> SameIncomingValueBBs;
// Find all other incoming blocks from which incoming values of all PHIs in
// DestBB are the same as the ones from BB.
for (pred_iterator PI = pred_begin(DestBB), E = pred_end(DestBB); PI != E;
++PI) {
BasicBlock *DestBBPred = *PI;
if (DestBBPred == BB)
bool HasAllSameValue = true;
BasicBlock::const_iterator DestBBI = DestBB->begin();
while (const PHINode *DestPN = dyn_cast<PHINode>(DestBBI++)) {
if (DestPN->getIncomingValueForBlock(BB) !=
DestPN->getIncomingValueForBlock(DestBBPred)) {
HasAllSameValue = false;
if (HasAllSameValue)
// See if all BB's incoming values are same as the value from Pred. In this
// case, no reason to skip merging because COPYs are expected to be place in
// Pred already.
if (SameIncomingValueBBs.count(Pred))
return true;
if (!BFI) {
Function &F = *BB->getParent();
LoopInfo LI{DominatorTree(F)};
BPI.reset(new BranchProbabilityInfo(F, LI));
BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
BlockFrequency PredFreq = BFI->getBlockFreq(Pred);
BlockFrequency BBFreq = BFI->getBlockFreq(BB);
for (auto SameValueBB : SameIncomingValueBBs)
if (SameValueBB->getUniquePredecessor() == Pred &&
DestBB == findDestBlockOfMergeableEmptyBlock(SameValueBB))
BBFreq += BFI->getBlockFreq(SameValueBB);
return PredFreq.getFrequency() <=
BBFreq.getFrequency() * FreqRatioToSkipMerge;
/// Return true if we can merge BB into DestBB if there is a single
/// unconditional branch between them, and BB contains no other non-phi
/// instructions.
bool CodeGenPrepare::canMergeBlocks(const BasicBlock *BB,
const BasicBlock *DestBB) const {
// We only want to eliminate blocks whose phi nodes are used by phi nodes in
// the successor. If there are more complex condition (e.g. preheaders),
// don't mess around with them.
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 User is inside DestBB block and it is a PHINode then check
// incoming value. If incoming value is not from BB then this is
// a complex condition (e.g. preheaders) we want to avoid here.
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;
// If BB and DestBB contain any common predecessors, then the phi nodes in BB
// and DestBB may have conflicting incoming values for the block. If so, we
// can't merge the block.
const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin());
if (!DestBBPN) return true; // no conflict.
// Collect the preds of BB.
SmallPtrSet<const BasicBlock*, 16> BBPreds;
if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) {
// It is faster to get preds from a PHI than with pred_iterator.
for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
} else {
BBPreds.insert(pred_begin(BB), pred_end(BB));
// Walk the preds of DestBB.
for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) {
BasicBlock *Pred = DestBBPN->getIncomingBlock(i);
if (BBPreds.count(Pred)) { // Common predecessor?
BBI = DestBB->begin();
while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) {
const Value *V1 = PN->getIncomingValueForBlock(Pred);
const Value *V2 = PN->getIncomingValueForBlock(BB);
// If V2 is a phi node in BB, look up what the mapped value will be.
if (const PHINode *V2PN = dyn_cast<PHINode>(V2))
if (V2PN->getParent() == BB)
V2 = V2PN->getIncomingValueForBlock(Pred);
// If there is a conflict, bail out.
if (V1 != V2) return false;
return true;
/// Eliminate a basic block that has only phi's and an unconditional branch in
/// it.
void CodeGenPrepare::eliminateMostlyEmptyBlock(BasicBlock *BB) {
BranchInst *BI = cast<BranchInst>(BB->getTerminator());
BasicBlock *DestBB = BI->getSuccessor(0);
// If the destination block has a single pred, then this is a trivial edge,
// just collapse it.
if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) {
if (SinglePred != DestBB) {
// Remember if SinglePred was the entry block of the function. If so, we
// will need to move BB back to the entry position.
bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
MergeBasicBlockIntoOnlyPred(DestBB, nullptr);
if (isEntry && BB != &BB->getParent()->getEntryBlock())
DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
// Otherwise, we have multiple predecessors of BB. Update the PHIs in DestBB
// to handle the new incoming edges it is about to have.
PHINode *PN;
for (BasicBlock::iterator BBI = DestBB->begin();
(PN = dyn_cast<PHINode>(BBI)); ++BBI) {
// Remove the incoming value for BB, and remember it.
Value *InVal = PN->removeIncomingValue(BB, false);
// Two options: either the InVal is a phi node defined in BB or it is some
// value that dominates BB.
PHINode *InValPhi = dyn_cast<PHINode>(InVal);
if (InValPhi && InValPhi->getParent() == BB) {
// Add all of the input values of the input PHI as inputs of this phi.
for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i)
} else {
// Otherwise, add one instance of the dominating value for each edge that
// we will be adding.
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);
// The PHIs are now updated, change everything that refers to BB to use
// DestBB and remove BB.
DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
// Computes a map of base pointer relocation instructions to corresponding
// derived pointer relocation instructions given a vector of all relocate calls
static void computeBaseDerivedRelocateMap(
const SmallVectorImpl<GCRelocateInst *> &AllRelocateCalls,
DenseMap<GCRelocateInst *, SmallVector<GCRelocateInst *, 2>>
&RelocateInstMap) {
// Collect information in two maps: one primarily for locating the base object
// while filling the second map; the second map is the final structure holding
// a mapping between Base and corresponding Derived relocate calls
DenseMap<std::pair<unsigned, unsigned>, GCRelocateInst *> RelocateIdxMap;
for (auto *ThisRelocate : AllRelocateCalls) {
auto K = std::make_pair(ThisRelocate->getBasePtrIndex(),
RelocateIdxMap.insert(std::make_pair(K, ThisRelocate));
for (auto &Item : RelocateIdxMap) {
std::pair<unsigned, unsigned> Key = Item.first;
if (Key.first == Key.second)
// Base relocation: nothing to insert
GCRelocateInst *I = Item.second;
auto BaseKey = std::make_pair(Key.first, Key.first);
// We're iterating over RelocateIdxMap so we cannot modify it.
auto MaybeBase = RelocateIdxMap.find(BaseKey);
if (MaybeBase == RelocateIdxMap.end())
// TODO: We might want to insert a new base object relocate and gep off
// that, if there are enough derived object relocates.
// Accepts a GEP and extracts the operands into a vector provided they're all
// small integer constants
static bool getGEPSmallConstantIntOffsetV(GetElementPtrInst *GEP,
SmallVectorImpl<Value *> &OffsetV) {
for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
// Only accept small constant integer operands
auto Op = dyn_cast<ConstantInt>(GEP->getOperand(i));
if (!Op || Op->getZExtValue() > 20)
return false;
for (unsigned i = 1; i < GEP->getNumOperands(); i++)
return true;
// Takes a RelocatedBase (base pointer relocation instruction) and Targets to
// replace, computes a replacement, and affects it.
static bool
simplifyRelocatesOffABase(GCRelocateInst *RelocatedBase,
const SmallVectorImpl<GCRelocateInst *> &Targets) {
bool MadeChange = false;
// We must ensure the relocation of derived pointer is defined after
// relocation of base pointer. If we find a relocation corresponding to base
// defined earlier than relocation of base then we move relocation of base
// right before found relocation. We consider only relocation in the same
// basic block as relocation of base. Relocations from other basic block will
// be skipped by optimization and we do not care about them.
for (auto R = RelocatedBase->getParent()->getFirstInsertionPt();
&*R != RelocatedBase; ++R)
if (auto RI = dyn_cast<GCRelocateInst>(R))
if (RI->getStatepoint() == RelocatedBase->getStatepoint())
if (RI->getBasePtrIndex() == RelocatedBase->getBasePtrIndex()) {
for (GCRelocateInst *ToReplace : Targets) {
assert(ToReplace->getBasePtrIndex() == RelocatedBase->getBasePtrIndex() &&
"Not relocating a derived object of the original base object");
if (ToReplace->getBasePtrIndex() == ToReplace->getDerivedPtrIndex()) {
// A duplicate relocate call. TODO: coalesce duplicates.
if (RelocatedBase->getParent() != ToReplace->getParent()) {
// Base and derived relocates are in different basic blocks.
// In this case transform is only valid when base dominates derived
// relocate. However it would be too expensive to check dominance
// for each such relocate, so we skip the whole transformation.
Value *Base = ToReplace->getBasePtr();
auto Derived = dyn_cast<GetElementPtrInst>(ToReplace->getDerivedPtr());
if (!Derived || Derived->getPointerOperand() != Base)
SmallVector<Value *, 2> OffsetV;
if (!getGEPSmallConstantIntOffsetV(Derived, OffsetV))
// Create a Builder and replace the target callsite with a gep
assert(RelocatedBase->getNextNode() &&
"Should always have one since it's not a terminator");
// Insert after RelocatedBase
IRBuilder<> Builder(RelocatedBase->getNextNode());
// If gc_relocate does not match the actual type, cast it to the right type.
// In theory, there must be a bitcast after gc_relocate if the type does not
// match, and we should reuse it to get the derived pointer. But it could be
// cases like this:
// bb1:
// ...
// %g1 = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(...)
// br label %merge
// bb2:
// ...
// %g2 = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(...)
// br label %merge
// merge:
// %p1 = phi i8 addrspace(1)* [ %g1, %bb1 ], [ %g2, %bb2 ]
// %cast = bitcast i8 addrspace(1)* %p1 in to i32 addrspace(1)*
// In this case, we can not find the bitcast any more. So we insert a new bitcast
// no matter there is already one or not. In this way, we can handle all cases, and
// the extra bitcast should be optimized away in later passes.
Value *ActualRelocatedBase = RelocatedBase;
if (RelocatedBase->getType() != Base->getType()) {
ActualRelocatedBase =
Builder.CreateBitCast(RelocatedBase, Base->getType());
Value *Replacement = Builder.CreateGEP(
Derived->getSourceElementType(), ActualRelocatedBase, makeArrayRef(OffsetV));
// If the newly generated derived pointer's type does not match the original derived
// pointer's type, cast the new derived pointer to match it. Same reasoning as above.
Value *ActualReplacement = Replacement;
if (Replacement->getType() != ToReplace->getType()) {
ActualReplacement =
Builder.CreateBitCast(Replacement, ToReplace->getType());
MadeChange = true;
return MadeChange;
// Turns this:
// %base = ...
// %ptr = gep %base + 15
// %tok = statepoint (%fun, i32 0, i32 0, i32 0, %base, %ptr)
// %base' = relocate(%tok, i32 4, i32 4)
// %ptr' = relocate(%tok, i32 4, i32 5)
// %val = load %ptr'
// into this:
// %base = ...
// %ptr = gep %base + 15
// %tok = statepoint (%fun, i32 0, i32 0, i32 0, %base, %ptr)
// %base' = gc.relocate(%tok, i32 4, i32 4)
// %ptr' = gep %base' + 15
// %val = load %ptr'
bool CodeGenPrepare::simplifyOffsetableRelocate(Instruction &I) {
bool MadeChange = false;
SmallVector<GCRelocateInst *, 2> AllRelocateCalls;
for (auto *U : I.users())
if (GCRelocateInst *Relocate = dyn_cast<GCRelocateInst>(U))
// Collect all the relocate calls associated with a statepoint
// We need atleast one base pointer relocation + one derived pointer
// relocation to mangle
if (AllRelocateCalls.size() < 2)
return false;
// RelocateInstMap is a mapping from the base relocate instruction to the
// corresponding derived relocate instructions
DenseMap<GCRelocateInst *, SmallVector<GCRelocateInst *, 2>> RelocateInstMap;
computeBaseDerivedRelocateMap(AllRelocateCalls, RelocateInstMap);
if (RelocateInstMap.empty())
return false;
for (auto &Item : RelocateInstMap)
// Item.first is the RelocatedBase to offset against
// Item.second is the vector of Targets to replace
MadeChange = simplifyRelocatesOffABase(Item.first, Item.second);
return MadeChange;
/// SinkCast - Sink the specified cast instruction into its user blocks
static bool SinkCast(CastInst *CI) {
BasicBlock *DefBB = CI->getParent();
/// InsertedCasts - Only insert a cast in each block once.
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);
// Figure out which BB this cast is used in. For PHI's this is the
// appropriate predecessor block.
BasicBlock *UserBB = User->getParent();
if (PHINode *PN = dyn_cast<PHINode>(User)) {
UserBB = PN->getIncomingBlock(TheUse);
// Preincrement use iterator so we don't invalidate it.
// The first insertion point of a block containing an EH pad is after the
// pad. If the pad is the user, we cannot sink the cast past the pad.
if (User->isEHPad())
// If the block selected to receive the cast is an EH pad that does not
// allow non-PHI instructions before the terminator, we can't sink the
// cast.
if (UserBB->getTerminator()->isEHPad())
// If this user is in the same block as the cast, don't change the cast.
if (UserBB == DefBB) continue;
// If we have already inserted a cast into this block, use it.
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);
// Replace a use of the cast with a use of the new cast.
TheUse = InsertedCast;
MadeChange = true;
// If we removed all uses, nuke the cast.
if (CI->use_empty()) {
MadeChange = true;
return MadeChange;
/// If the specified cast instruction is a noop copy (e.g. it's casting from
/// one pointer type to another, i32->i8 on PPC), sink it into user blocks to
/// reduce the number of virtual registers that must be created and coalesced.
/// Return true if any changes are made.
static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI,
const DataLayout &DL) {
// Sink only "cheap" (or nop) address-space casts. This is a weaker condition
// than sinking only nop casts, but is helpful on some platforms.
if (auto *ASC = dyn_cast<AddrSpaceCastInst>(CI)) {
if (!TLI.isCheapAddrSpaceCast(ASC->getSrcAddressSpace(),
return false;
// If this is a noop copy,
EVT SrcVT = TLI.getValueType(DL, CI->getOperand(0)->getType());
EVT DstVT = TLI.getValueType(DL, CI->getType());
// This is an fp<->int conversion?
if (SrcVT.isInteger() != DstVT.isInteger())
return false;
// If this is an extension, it will be a zero or sign extension, which
// isn't a noop.
if (SrcVT.bitsLT(DstVT)) return false;
// If these values will be promoted, find out what they will be promoted
// to. This helps us consider truncates on PPC as noop copies when they
// are.
if (TLI.getTypeAction(CI->getContext(), SrcVT) ==
SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT);
if (TLI.getTypeAction(CI->getContext(), DstVT) ==
DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT);
// If, after promotion, these are the same types, this is a noop copy.
if (SrcVT != DstVT)
return false;
return SinkCast(CI);
/// Try to combine CI into a call to the llvm.uadd.with.overflow intrinsic if
/// possible.
/// Return true if any changes were made.
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;
// We don't want to move around uses of condition values this late, so we we
// check if it is legal to create the call to the intrinsic in the basic
// block containing the icmp:
if (AddI->getParent() != CI->getParent() && !AddI->hasOneUse())
return false;
#ifndef NDEBUG
// Someday m_UAddWithOverflow may get smarter, but this is a safe assumption
// for now:
if (AddI->hasOneUse())
assert(*AddI->user_begin() == CI && "expected!");
Module *M = CI->getModule();
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);
return true;
/// Sink the given CmpInst into user blocks to reduce the number of virtual
/// registers that must be created and coalesced. This is a clear win except on
/// targets with multiple condition code registers (PowerPC), where it might
/// lose; some adjustment may be wanted there.
/// Return true if any changes are made.
static bool SinkCmpExpression(CmpInst *CI, const TargetLowering *TLI) {
BasicBlock *DefBB = CI->getParent();
// Avoid sinking soft-FP comparisons, since this can move them into a loop.
if (TLI && TLI->useSoftFloat() && isa<FCmpInst>(CI))
return false;
// Only insert a cmp in each block once.
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);
// Preincrement use iterator so we don't invalidate it.
// Don't bother for PHI nodes.
if (isa<PHINode>(User))
// Figure out which BB this cmp is used in.
BasicBlock *UserBB = User->getParent();
// If this user is in the same block as the cmp, don't change the cmp.
if (UserBB == DefBB) continue;
// If we have already inserted a cmp into this block, use it.
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);
// Propagate the debug info.
// Replace a use of the cmp with a use of the new cmp.
TheUse = InsertedCmp;
MadeChange = true;
// If we removed all uses, nuke the cmp.
if (CI->use_empty()) {
MadeChange = true;
return MadeChange;
static bool OptimizeCmpExpression(CmpInst *CI, const TargetLowering *TLI) {
if (SinkCmpExpression(CI, TLI))
return true;
if (CombineUAddWithOverflow(CI))
return true;
return false;
/// Duplicate and sink the given 'and' instruction into user blocks where it is
/// used in a compare to allow isel to generate better code for targets where
/// this operation can be combined.
/// Return true if any changes are made.
static bool sinkAndCmp0Expression(Instruction *AndI,
const TargetLowering &TLI,
SetOfInstrs &InsertedInsts) {
// Double-check that we're not trying to optimize an instruction that was
// already optimized by some other part of this pass.
assert(!InsertedInsts.count(AndI) &&
"Attempting to optimize already optimized and instruction");
(void) InsertedInsts;
// Nothing to do for single use in same basic block.
if (AndI->hasOneUse() &&
AndI->getParent() == cast<Instruction>(*AndI->user_begin())->getParent())
return false;
// Try to avoid cases where sinking/duplicating is likely to increase register
// pressure.
if (!isa<ConstantInt>(AndI->getOperand(0)) &&
!isa<ConstantInt>(AndI->getOperand(1)) &&
AndI->getOperand(0)->hasOneUse() && AndI->getOperand(1)->hasOneUse())
return false;
for (auto *U : AndI->users()) {
Instruction *User = cast<Instruction>(U);
// Only sink for and mask feeding icmp with 0.
if (!isa<ICmpInst>(User))
return false;
auto *CmpC = dyn_cast<ConstantInt>(User->getOperand(1));
if (!CmpC || !CmpC->isZero())
return false;
if (!TLI.isMaskAndCmp0FoldingBeneficial(*AndI))
return false;
DEBUG(dbgs() << "found 'and' feeding only icmp 0;\n");
// Push the 'and' into the same block as the icmp 0. There should only be
// one (icmp (and, 0)) in each block, since CSE/GVN should have removed any
// others, so we don't need to keep track of which BBs we insert into.
for (Value::user_iterator UI = AndI->user_begin(), E = AndI->user_end();
UI != E; ) {
Use &TheUse = UI.getUse();
Instruction *User = cast<Instruction>(*UI);
// Preincrement use iterator so we don't invalidate it.
DEBUG(dbgs() << "sinking 'and' use: " << *User << "\n");
// Keep the 'and' in the same place if the use is already in the same block.
Instruction *InsertPt =
User->getParent() == AndI->getParent() ? AndI : User;
Instruction *InsertedAnd =
BinaryOperator::Create(Instruction::And, AndI->getOperand(0),
AndI->getOperand(1), "", InsertPt);
// Propagate the debug info.
// Replace a use of the 'and' with a use of the new 'and'.
TheUse = InsertedAnd;
// We removed all uses, nuke the and.
return true;
/// Check if the candidates could be combined with a shift instruction, which
/// includes:
/// 1. Truncate instruction
/// 2. And instruction and the imm is a mask of the low bits:
/// imm & (imm+1) == 0
static bool isExtractBitsCandidateUse(Instruction *User) {
if (!isa<TruncInst>(User)) {
if (User->getOpcode() != Instruction::And ||
return false;
const APInt &Cimm = cast<ConstantInt>(User->getOperand(1))->getValue();
if ((Cimm & (Cimm + 1)).getBoolValue())
return false;
return true;
/// Sink both shift and truncate instruction to the use of truncate's BB.
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);
// Preincrement use iterator so we don't invalidate it.
int ISDOpcode = TLI.InstructionOpcodeToISD(TruncUser->getOpcode());
if (!ISDOpcode)
// If the use is actually a legal node, there will not be an
// implicit truncate.
// FIXME: always querying the result type is just an
// approximation; some nodes' legality is determined by the
// operand or other means. There's no good way to find out though.
if (TLI.isOperationLegalOrCustom(
ISDOpcode, TLI.getValueType(DL, TruncUser->getType(), true)))
// Don't bother for PHI nodes.
if (isa<PHINode>(TruncUser))
BasicBlock *TruncUserBB = TruncUser->getParent();
if (UserBB == TruncUserBB)
BinaryOperator *&InsertedShift = InsertedShifts[TruncUserBB];
CastInst *&InsertedTrunc = InsertedTruncs[TruncUserBB];
if (!InsertedShift && !InsertedTrunc) {
BasicBlock::iterator InsertPt = TruncUserBB->getFirstInsertionPt();
assert(InsertPt != TruncUserBB->end());
// Sink the shift
if (ShiftI->getOpcode() == Instruction::AShr)
InsertedShift = BinaryOperator::CreateAShr(ShiftI->getOperand(0), CI,
"", &*InsertPt);
InsertedShift = BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI,
"", &*InsertPt);
// Sink the trunc
BasicBlock::iterator TruncInsertPt = TruncUserBB->getFirstInsertionPt();
assert(TruncInsertPt != TruncUserBB->end());
InsertedTrunc = CastInst::Create(TruncI->getOpcode(), InsertedShift,
TruncI->getType(), "", &*TruncInsertPt);
MadeChange = true;
TruncTheUse = InsertedTrunc;
return MadeChange;
/// Sink the shift *right* instruction into user blocks if the uses could
/// potentially be combined with this shift instruction and generate BitExtract
/// instruction. It will only be applied if the architecture supports BitExtract
/// instruction. Here is an example:
/// BB1:
/// %x.extract.shift = lshr i64 %arg1, 32
/// BB2:
/// %x.extract.trunc = trunc i64 %x.extract.shift to i16
/// ==>
/// BB2:
/// %x.extract.shift.1 = lshr i64 %arg1, 32
/// %x.extract.trunc = trunc i64 %x.extract.shift.1 to i16
/// CodeGen will recoginze the pattern in BB2 and generate BitExtract
/// instruction.
/// Return true if any changes are made.
static bool OptimizeExtractBits(BinaryOperator *ShiftI, ConstantInt *CI,
const TargetLowering &TLI,
const DataLayout &DL) {
BasicBlock *DefBB = ShiftI->getParent();
/// Only insert instructions in each block once.
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);
// Preincrement use iterator so we don't invalidate it.
// Don't bother for PHI nodes.
if (isa<PHINode>(User))
if (!isExtractBitsCandidateUse(User))
BasicBlock *UserBB = User->getParent();
if (UserBB == DefBB) {
// If the shift and truncate instruction are in the same BB. The use of
// the truncate(TruncUse) may still introduce another truncate if not
// legal. In this case, we would like to sink both shift and truncate
// instruction to the BB of TruncUse.
// for example:
// BB1:
// i64 shift.result = lshr i64 opnd, imm
// trunc.result = trunc shift.result to i16
// BB2:
// ----> We will have an implicit truncate here if the architecture does
// not have i16 compare.
// cmp i16 trunc.result, opnd2
if (isa<TruncInst>(User) && shiftIsLegal
// If the type of the truncate is legal, no trucate will be
// introduced in other basic blocks.
(!TLI.isTypeLegal(TLI.getValueType(DL, User->getType()))))
MadeChange =
SinkShiftAndTruncate(ShiftI, User, CI, InsertedShifts, TLI, DL);
// If we have already inserted a shift into this block, use it.
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);
InsertedShift = BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI,
"", &*InsertPt);
MadeChange = true;
// Replace a use of the shift with a use of the new shift.
TheUse = InsertedShift;
// If we removed all uses, nuke the shift.
if (ShiftI->use_empty())
return MadeChange;
/// If counting leading or trailing zeros is an expensive operation and a zero
/// input is defined, add a check for zero to avoid calling the intrinsic.
/// We want to transform:
/// %z = call i64 @llvm.cttz.i64(i64 %A, i1 false)
/// into:
/// entry:
/// %cmpz = icmp eq i64 %A, 0
/// br i1 %cmpz, label %cond.end, label %cond.false
/// cond.false:
/// %z = call i64 @llvm.cttz.i64(i64 %A, i1 true)
/// br label %cond.end
/// cond.end:
/// %ctz = phi i64 [ 64, %entry ], [ %z, %cond.false ]
/// If the transform is performed, return true and set ModifiedDT to true.
static bool despeculateCountZeros(IntrinsicInst *CountZeros,
const TargetLowering *TLI,
const DataLayout *DL,
bool &ModifiedDT) {
if (!TLI || !DL)
return false;
// If a zero input is undefined, it doesn't make sense to despeculate that.
if (match(CountZeros->getOperand(1), m_One()))
return false;
// If it's cheap to speculate, there's nothing to do.
auto IntrinsicID = CountZeros->getIntrinsicID();
if ((IntrinsicID == Intrinsic::cttz && TLI->isCheapToSpeculateCttz()) ||
(IntrinsicID == Intrinsic::ctlz && TLI->isCheapToSpeculateCtlz()))
return false;
// Only handle legal scalar cases. Anything else requires too much work.
Type *Ty = CountZeros->getType();
unsigned SizeInBits = Ty->getPrimitiveSizeInBits();
if (Ty->isVectorTy() || SizeInBits > DL->getLargestLegalIntTypeSizeInBits())
return false;
// The intrinsic will be sunk behind a compare against zero and branch.
BasicBlock *StartBlock = CountZeros->getParent();
BasicBlock *CallBlock = StartBlock->splitBasicBlock(CountZeros, "cond.false");
// Create another block after the count zero intrinsic. A PHI will be added
// in this block to select the result of the intrinsic or the bit-width
// constant if the input to the intrinsic is zero.
BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(CountZeros));
BasicBlock *EndBlock = CallBlock->splitBasicBlock(SplitPt, "cond.end");
// Set up a builder to create a compare, conditional branch, and PHI.
IRBuilder<> Builder(CountZeros->getContext());
// Replace the unconditional branch that was created by the first split with
// a compare against zero and a conditional branch.
Value *Zero = Constant::getNullValue(Ty);
Value *Cmp = Builder.CreateICmpEQ(CountZeros->getOperand(0), Zero, "cmpz");
Builder.CreateCondBr(Cmp, EndBlock, CallBlock);
// Create a PHI in the end block to select either the output of the intrinsic
// or the bit width of the operand.
PHINode *PN = Builder.CreatePHI(Ty, 2, "ctz");
Value *BitWidth = Builder.getInt(APInt(SizeInBits, SizeInBits));
PN->addIncoming(BitWidth, StartBlock);
PN->addIncoming(CountZeros, CallBlock);
// We are explicitly handling the zero case, so we can set the intrinsic's
// undefined zero argument to 'true'. This will also prevent reprocessing the
// intrinsic; we only despeculate when a zero input is defined.
CountZeros->setArgOperand(1, Builder.getTrue());
ModifiedDT = true;
return true;
namespace {
// This class provides helper functions to expand a memcmp library call into an
// inline expansion.
class MemCmpExpansion {
struct ResultBlock {
BasicBlock *BB = nullptr;
PHINode *PhiSrc1 = nullptr;
PHINode *PhiSrc2 = nullptr;
ResultBlock() = default;
CallInst *const CI;
ResultBlock ResBlock;
const uint64_t Size;
unsigned MaxLoadSize;
uint64_t NumLoadsNonOneByte;
const uint64_t NumLoadsPerBlock;
std::vector<BasicBlock *> LoadCmpBlocks;
BasicBlock *EndBlock;
PHINode *PhiRes;
const bool IsUsedForZeroCmp;
const DataLayout &DL;
IRBuilder<> Builder;
// Represents the decomposition in blocks of the expansion. For example,
// comparing 33 bytes on X86+sse can be done with 2x16-byte loads and
// 1x1-byte load, which would be represented as [{16, 0}, {16, 16}, {32, 1}.
// TODO(courbet): Involve the target more in this computation. On X86, 7
// bytes can be done more efficiently with two overlaping 4-byte loads than
// covering the interval with [{4, 0},{2, 4},{1, 6}}.
struct LoadEntry {
LoadEntry(unsigned LoadSize, uint64_t Offset)
: LoadSize(LoadSize), Offset(Offset) {
assert(Offset % LoadSize == 0 && "invalid load entry");
uint64_t getGEPIndex() const { return Offset / LoadSize; }
// The size of the load for this block, in bytes.
const unsigned LoadSize;
// The offset of this load WRT the base pointer, in bytes.
const uint64_t Offset;
SmallVector<LoadEntry, 8> LoadSequence;
void createLoadCmpBlocks();
void createResultBlock();
void setupResultBlockPHINodes();
void setupEndBlockPHINodes();
Value *getCompareLoadPairs(unsigned BlockIndex, unsigned &LoadIndex);
void emitLoadCompareBlock(unsigned BlockIndex);
void emitLoadCompareBlockMultipleLoads(unsigned BlockIndex,
unsigned &LoadIndex);
void emitLoadCompareByteBlock(unsigned BlockIndex, unsigned GEPIndex);
void emitMemCmpResultBlock();
Value *getMemCmpExpansionZeroCase();
Value *getMemCmpEqZeroOneBlock();
Value *getMemCmpOneBlock();
MemCmpExpansion(CallInst *CI, uint64_t Size,
const TargetTransformInfo::MemCmpExpansionOptions &Options,
unsigned MaxNumLoads, const bool IsUsedForZeroCmp,
unsigned NumLoadsPerBlock, const DataLayout &DL);
unsigned getNumBlocks();
uint64_t getNumLoads() const { return LoadSequence.size(); }
Value *getMemCmpExpansion();
} // end anonymous namespace
// Initialize the basic block structure required for expansion of memcmp call
// with given maximum load size and memcmp size parameter.
// This structure includes:
// 1. A list of load compare blocks - LoadCmpBlocks.
// 2. An EndBlock, split from original instruction point, which is the block to
// return from.
// 3. ResultBlock, block to branch to for early exit when a
// LoadCmpBlock finds a difference.
CallInst *const CI, uint64_t Size,
const TargetTransformInfo::MemCmpExpansionOptions &Options,
const unsigned MaxNumLoads, const bool IsUsedForZeroCmp,
const unsigned NumLoadsPerBlock, const DataLayout &TheDataLayout)
: CI(CI),
Builder(CI) {
assert(Size > 0 && "zero blocks");
// Scale the max size down if the target can load more bytes than we need.
size_t LoadSizeIndex = 0;
while (LoadSizeIndex < Options.LoadSizes.size() &&
Options.LoadSizes[LoadSizeIndex] > Size) {
this->MaxLoadSize = Options.LoadSizes[LoadSizeIndex];
// Compute the decomposition.
uint64_t CurSize = Size;
uint64_t Offset = 0;
while (CurSize && LoadSizeIndex < Options.LoadSizes.size()) {
const unsigned LoadSize = Options.LoadSizes[LoadSizeIndex];
assert(LoadSize > 0 && "zero load size");
const uint64_t NumLoadsForThisSize = CurSize / LoadSize;
if (LoadSequence.size() + NumLoadsForThisSize > MaxNumLoads) {
// Do not expand if the total number of loads is larger than what the
// target allows. Note that it's important that we exit before completing
// the expansion to avoid using a ton of memory to store the expansion for
// large sizes.
if (NumLoadsForThisSize > 0) {
for (uint64_t I = 0; I < NumLoadsForThisSize; ++I) {
LoadSequence.push_back({LoadSize, Offset});
Offset += LoadSize;
if (LoadSize > 1) {
CurSize = CurSize % LoadSize;
assert(LoadSequence.size() <= MaxNumLoads && "broken invariant");
unsigned MemCmpExpansion::getNumBlocks() {
if (IsUsedForZeroCmp)
return getNumLoads() / NumLoadsPerBlock +
(getNumLoads() % NumLoadsPerBlock != 0 ? 1 : 0);
return getNumLoads();
void MemCmpExpansion::createLoadCmpBlocks() {
for (unsigned i = 0; i < getNumBlocks(); i++) {
BasicBlock *BB = BasicBlock::Create(CI->getContext(), "loadbb",
EndBlock->getParent(), EndBlock);
void MemCmpExpansion::createResultBlock() {
ResBlock.BB = BasicBlock::Create(CI->getContext(), "res_block",
EndBlock->getParent(), EndBlock);
// This function creates the IR instructions for loading and comparing 1 byte.
// It loads 1 byte from each source of the memcmp parameters with the given
// GEPIndex. It then subtracts the two loaded values and adds this result to the
// final phi node for selecting the memcmp result.
void MemCmpExpansion::emitLoadCompareByteBlock(unsigned BlockIndex,
unsigned GEPIndex) {
Value *Source1 = CI->getArgOperand(0);
Value *Source2 = CI->getArgOperand(1);
Type *LoadSizeType = Type::getInt8Ty(CI->getContext());
// Cast source to LoadSizeType*.
if (Source1->getType() != LoadSizeType)
Source1 = Builder.CreateBitCast(Source1, LoadSizeType->getPointerTo());
if (Source2->getType() != LoadSizeType)
Source2 = Builder.CreateBitCast(Source2, LoadSizeType->getPointerTo());
// Get the base address using the GEPIndex.
if (GEPIndex != 0) {
Source1 = Builder.CreateGEP(LoadSizeType, Source1,
ConstantInt::get(LoadSizeType, GEPIndex));
Source2 = Builder.CreateGEP(LoadSizeType, Source2,
ConstantInt::get(LoadSizeType, GEPIndex));
Value *LoadSrc1 = Builder.CreateLoad(LoadSizeType, Source1);
Value *LoadSrc2 = Builder.CreateLoad(LoadSizeType, Source2);
LoadSrc1 = Builder.CreateZExt(LoadSrc1, Type::getInt32Ty(CI->getContext()));
LoadSrc2 = Builder.CreateZExt(LoadSrc2, Type::getInt32Ty(CI->getContext()));
Value *Diff = Builder.CreateSub(LoadSrc1, LoadSrc2);
PhiRes->addIncoming(Diff, LoadCmpBlocks[BlockIndex]);
if (BlockIndex < (LoadCmpBlocks.size() - 1)) {
// Early exit branch if difference found to EndBlock. Otherwise, continue to
// next LoadCmpBlock,
Value *Cmp = Builder.CreateICmp(ICmpInst::ICMP_NE, Diff,
ConstantInt::get(Diff->getType(), 0));
BranchInst *CmpBr =
BranchInst::Create(EndBlock, LoadCmpBlocks[BlockIndex + 1], Cmp);
} else {
// The last block has an unconditional branch to EndBlock.
BranchInst *CmpBr = BranchInst::Create(EndBlock);
/// Generate an equality comparison for one or more pairs of loaded values.
/// This is used in the case where the memcmp() call is compared equal or not
/// equal to zero.
Value *MemCmpExpansion::getCompareLoadPairs(unsigned BlockIndex,
unsigned &LoadIndex) {
assert(LoadIndex < getNumLoads() &&
"getCompareLoadPairs() called with no remaining loads");
std::vector<Value *> XorList, OrList;
Value *Diff;
const unsigned NumLoads =
std::min(getNumLoads() - LoadIndex, NumLoadsPerBlock);
// For a single-block expansion, start inserting before the memcmp call.
if (LoadCmpBlocks.empty())
Value *Cmp = nullptr;
// If we have multiple loads per block, we need to generate a composite
// comparison using xor+or. The type for the combinations is the largest load
// type.
IntegerType *const MaxLoadType =
NumLoads == 1 ? nullptr
: IntegerType::get(CI->getContext(), MaxLoadSize * 8);
for (unsigned i = 0; i < NumLoads; ++i, ++LoadIndex) {
const LoadEntry &CurLoadEntry = LoadSequence[LoadIndex];
IntegerType *LoadSizeType =
IntegerType::get(CI->getContext(), CurLoadEntry.LoadSize * 8);
Value *Source1 = CI->getArgOperand(0);
Value *Source2 = CI->getArgOperand(1);
// Cast source to LoadSizeType*.
if (Source1->getType() != LoadSizeType)
Source1 = Builder.CreateBitCast(Source1, LoadSizeType->getPointerTo());
if (Source2->getType() != LoadSizeType)
Source2 = Builder.CreateBitCast(Source2, LoadSizeType->getPointerTo());
// Get the base address using a GEP.
if (CurLoadEntry.Offset != 0) {
Source1 = Builder.CreateGEP(
LoadSizeType, Source1,
ConstantInt::get(LoadSizeType, CurLoadEntry.getGEPIndex()));
Source2 = Builder.CreateGEP(
LoadSizeType, Source2,
ConstantInt::get(LoadSizeType, CurLoadEntry.getGEPIndex()));
// Get a constant or load a value for each source address.
Value *LoadSrc1 = nullptr;
if (auto *Source1C = dyn_cast<Constant>(Source1))
LoadSrc1 = ConstantFoldLoadFromConstPtr(Source1C, LoadSizeType, DL);
if (!LoadSrc1)
LoadSrc1 = Builder.CreateLoad(LoadSizeType, Source1);
Value *LoadSrc2 = nullptr;
if (auto *Source2C = dyn_cast<Constant>(Source2))
LoadSrc2 = ConstantFoldLoadFromConstPtr(Source2C, LoadSizeType, DL);
if (!LoadSrc2)
LoadSrc2 = Builder.CreateLoad(LoadSizeType, Source2);
if (NumLoads != 1) {
if (LoadSizeType != MaxLoadType) {
LoadSrc1 = Builder.CreateZExt(LoadSrc1, MaxLoadType);
LoadSrc2 = Builder.CreateZExt(LoadSrc2, MaxLoadType);
// If we have multiple loads per block, we need to generate a composite
// comparison using xor+or.
Diff = Builder.CreateXor(LoadSrc1, LoadSrc2);
Diff = Builder.CreateZExt(Diff, MaxLoadType);
} else {
// If there's only one load per block, we just compare the loaded values.
Cmp = Builder.CreateICmpNE(LoadSrc1, LoadSrc2);
auto pairWiseOr = [&](std::vector<Value *> &InList) -> std::vector<Value *> {
std::vector<Value *> OutList;
for (unsigned i = 0; i < InList.size() - 1; i = i + 2) {
Value *Or = Builder.CreateOr(InList[i], InList[i + 1]);
if (InList.size() % 2 != 0)
return OutList;
if (!Cmp) {
// Pairwise OR the XOR results.
OrList = pairWiseOr(XorList);
// Pairwise OR the OR results until one result left.
while (OrList.size() != 1) {
OrList = pairWiseOr(OrList);
Cmp = Builder.CreateICmpNE(OrList[0], ConstantInt::get(Diff->getType(), 0));
return Cmp;
void MemCmpExpansion::emitLoadCompareBlockMultipleLoads(unsigned BlockIndex,
unsigned &LoadIndex) {
Value *Cmp = getCompareLoadPairs(BlockIndex, LoadIndex);
BasicBlock *NextBB = (BlockIndex == (LoadCmpBlocks.size() - 1))
? EndBlock
: LoadCmpBlocks[BlockIndex + 1];
// Early exit branch if difference found to ResultBlock. Otherwise,
// continue to next LoadCmpBlock or EndBlock.
BranchInst *CmpBr = BranchInst::Create(ResBlock.BB, NextBB, Cmp);
// Add a phi edge for the last LoadCmpBlock to Endblock with a value of 0
// since early exit to ResultBlock was not taken (no difference was found in
// any of the bytes).
if (BlockIndex == LoadCmpBlocks.size() - 1) {
Value *Zero = ConstantInt::get(Type::getInt32Ty(CI->getContext()), 0);
PhiRes->addIncoming(Zero, LoadCmpBlocks[BlockIndex]);
// This function creates the IR intructions for loading and comparing using the
// given LoadSize. It loads the number of bytes specified by LoadSize from each
// source of the memcmp parameters. It then does a subtract to see if there was
// a difference in the loaded values. If a difference is found, it branches
// with an early exit to the ResultBlock for calculating which source was
// larger. Otherwise, it falls through to the either the next LoadCmpBlock or
// the EndBlock if this is the last LoadCmpBlock. Loading 1 byte is handled with
// a special case through emitLoadCompareByteBlock. The special handling can
// simply subtract the loaded values and add it to the result phi node.
void MemCmpExpansion::emitLoadCompareBlock(unsigned BlockIndex) {
// There is one load per block in this case, BlockIndex == LoadIndex.
const LoadEntry &CurLoadEntry = LoadSequence[BlockIndex];
if (CurLoadEntry.LoadSize == 1) {
Type *LoadSizeType =
IntegerType::get(CI->getContext(), CurLoadEntry.LoadSize * 8);
Type *MaxLoadType = IntegerType::get(CI->getContext(), MaxLoadSize * 8);
assert(CurLoadEntry.LoadSize <= MaxLoadSize && "Unexpected load type");
Value *Source1 = CI->getArgOperand(0);
Value *Source2 = CI->getArgOperand(1);
// Cast source to LoadSizeType*.
if (Source1->getType() != LoadSizeType)
Source1 = Builder.CreateBitCast(Source1, LoadSizeType->getPointerTo());
if (Source2->getType() != LoadSizeType)
Source2 = Builder.CreateBitCast(Source2, LoadSizeType->getPointerTo());
// Get the base address using a GEP.
if (CurLoadEntry.Offset != 0) {
Source1 = Builder.CreateGEP(
LoadSizeType, Source1,
ConstantInt::get(LoadSizeType, CurLoadEntry.getGEPIndex()));
Source2 = Builder.CreateGEP(
LoadSizeType, Source2,
ConstantInt::get(LoadSizeType, CurLoadEntry.getGEPIndex()));
// Load LoadSizeType from the base address.
Value *LoadSrc1 = Builder.CreateLoad(LoadSizeType, Source1);
Value *LoadSrc2 = Builder.CreateLoad(LoadSizeType, Source2);
if (DL.isLittleEndian()) {
Function *Bswap = Intrinsic::getDeclaration(CI->getModule(),
Intrinsic::bswap, LoadSizeType);
LoadSrc1 = Builder.CreateCall(Bswap, LoadSrc1);
LoadSrc2 = Builder.CreateCall(Bswap, LoadSrc2);
if (LoadSizeType != MaxLoadType) {
LoadSrc1 = Builder.CreateZExt(LoadSrc1, MaxLoadType);
LoadSrc2 = Builder.CreateZExt(LoadSrc2, MaxLoadType);
// Add the loaded values to the phi nodes for calculating memcmp result only
// if result is not used in a zero equality.
if (!IsUsedForZeroCmp) {
ResBlock.PhiSrc1->addIncoming(LoadSrc1, LoadCmpBlocks[BlockIndex]);
ResBlock.PhiSrc2->addIncoming(LoadSrc2, LoadCmpBlocks[BlockIndex]);
Value *Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, LoadSrc1, LoadSrc2);
BasicBlock *NextBB = (BlockIndex == (LoadCmpBlocks.size() - 1))
? EndBlock
: LoadCmpBlocks[BlockIndex + 1];
// Early exit branch if difference found to ResultBlock. Otherwise, continue
// to next LoadCmpBlock or EndBlock.
BranchInst *CmpBr = BranchInst::Create(NextBB, ResBlock.BB, Cmp);
// Add a phi edge for the last LoadCmpBlock to Endblock with a value of 0
// since early exit to ResultBlock was not taken (no difference was found in
// any of the bytes).
if (BlockIndex == LoadCmpBlocks.size() - 1) {
Value *Zero = ConstantInt::get(Type::getInt32Ty(CI->getContext()), 0);
PhiRes->addIncoming(Zero, LoadCmpBlocks[BlockIndex]);
// This function populates the ResultBlock with a sequence to calculate the
// memcmp result. It compares the two loaded source values and returns -1 if
// src1 < src2 and 1 if src1 > src2.
void MemCmpExpansion::emitMemCmpResultBlock() {
// Special case: if memcmp result is used in a zero equality, result does not
// need to be calculated and can simply return 1.
if (IsUsedForZeroCmp) {
BasicBlock::iterator InsertPt = ResBlock.BB->getFirstInsertionPt();
Builder.SetInsertPoint(ResBlock.BB, InsertPt);
Value *Res = ConstantInt::get(Type::getInt32Ty(CI->getContext()), 1);
PhiRes->addIncoming(Res, ResBlock.BB);
BranchInst *NewBr = BranchInst::Create(EndBlock);
BasicBlock::iterator InsertPt = ResBlock.BB->getFirstInsertionPt();
Builder.SetInsertPoint(ResBlock.BB, InsertPt);
Value *Cmp = Builder.CreateICmp(ICmpInst::ICMP_ULT, ResBlock.PhiSrc1,
Value *Res =
Builder.CreateSelect(Cmp, ConstantInt::get(Builder.getInt32Ty(), -1),
ConstantInt::get(Builder.getInt32Ty(), 1));
BranchInst *NewBr = BranchInst::Create(EndBlock);
PhiRes->addIncoming(Res, ResBlock.BB);
void MemCmpExpansion::setupResultBlockPHINodes() {
Type *MaxLoadType = IntegerType::get(CI->getContext(), MaxLoadSize * 8);
// Note: this assumes one load per block.
ResBlock.PhiSrc1 =
Builder.CreatePHI(MaxLoadType, NumLoadsNonOneByte, "phi.src1");
ResBlock.PhiSrc2 =
Builder.CreatePHI(MaxLoadType, NumLoadsNonOneByte, "phi.src2");
void MemCmpExpansion::setupEndBlockPHINodes() {
PhiRes = Builder.CreatePHI(Type::getInt32Ty(CI->getContext()), 2, "phi.res");
Value *MemCmpExpansion::getMemCmpExpansionZeroCase() {
unsigned LoadIndex = 0;
// This loop populates each of the LoadCmpBlocks with the IR sequence to
// handle multiple loads per block.
for (unsigned I = 0; I < getNumBlocks(); ++I) {
emitLoadCompareBlockMultipleLoads(I, LoadIndex);
return PhiRes;
/// A memcmp expansion that compares equality with 0 and only has one block of
/// load and compare can bypass the compare, branch, and phi IR that is required
/// in the general case.
Value *MemCmpExpansion::getMemCmpEqZeroOneBlock() {
unsigned LoadIndex = 0;
Value *Cmp = getCompareLoadPairs(0, LoadIndex);
assert(LoadIndex == getNumLoads() && "some entries were not consumed");
return Builder.CreateZExt(Cmp, Type::getInt32Ty(CI->getContext()));
/// A memcmp expansion that only has one block of load and compare can bypass
/// the compare, branch, and phi IR that is required in the general case.
Value *MemCmpExpansion::getMemCmpOneBlock() {
assert(NumLoadsPerBlock == 1 && "Only handles one load pair per block");
Type *LoadSizeType = IntegerType::get(CI->getContext(), Size * 8);
Value *Source1 = CI->getArgOperand(0);
Value *Source2 = CI->getArgOperand(1);
// Cast source to LoadSizeType*.
if (Source1->getType() != LoadSizeType)
Source1 = Builder.CreateBitCast(Source1, LoadSizeType->getPointerTo());
if (Source2->getType() != LoadSizeType)
Source2 = Builder.CreateBitCast(Source2, LoadSizeType->getPointerTo());
// Load LoadSizeType from the base address.
Value *LoadSrc1 = Builder.CreateLoad(LoadSizeType, Source1);
Value *LoadSrc2 = Builder.CreateLoad(LoadSizeType, Source2);
if (DL.isLittleEndian() && Size != 1) {
Function *Bswap = Intrinsic::getDeclaration(CI->getModule(),
Intrinsic::bswap, LoadSizeType);
LoadSrc1 = Builder.CreateCall(Bswap, LoadSrc1);
LoadSrc2 = Builder.CreateCall(Bswap, LoadSrc2);
if (Size < 4) {
// The i8 and i16 cases don't need compares. We zext the loaded values and
// subtract them to get the suitable negative, zero, or positive i32 result.
LoadSrc1 = Builder.CreateZExt(LoadSrc1, Builder.getInt32Ty());
LoadSrc2 = Builder.CreateZExt(LoadSrc2, Builder.getInt32Ty());
return Builder.CreateSub(LoadSrc1, LoadSrc2);
// The result of memcmp is negative, zero, or positive, so produce that by
// subtracting 2 extended compare bits: sub (ugt, ult).
// If a target prefers to use selects to get -1/0/1, they should be able
// to transform this later. The inverse transform (going from selects to math)
// may not be possible in the DAG because the selects got converted into
// branches before we got there.
Value *CmpUGT = Builder.CreateICmpUGT(LoadSrc1, LoadSrc2);
Value *CmpULT = Builder.CreateICmpULT(LoadSrc1, LoadSrc2);
Value *ZextUGT = Builder.CreateZExt(CmpUGT, Builder.getInt32Ty());
Value *ZextULT = Builder.CreateZExt(CmpULT, Builder.getInt32Ty());
return Builder.CreateSub(ZextUGT, ZextULT);
// This function expands the memcmp call into an inline expansion and returns
// the memcmp result.
Value *MemCmpExpansion::getMemCmpExpansion() {
// A memcmp with zero-comparison with only one block of load and compare does
// not need to set up any extra blocks. This case could be handled in the DAG,
// but since we have all of the machinery to flexibly expand any memcpy here,
// we choose to handle this case too to avoid fragmented lowering.
if ((!IsUsedForZeroCmp && NumLoadsPerBlock != 1) || getNumBlocks() != 1) {
BasicBlock *StartBlock = CI->getParent();
EndBlock = StartBlock->splitBasicBlock(CI, "endblock");
// If return value of memcmp is not used in a zero equality, we need to
// calculate which source was larger. The calculation requires the
// two loaded source values of each load compare block.
// These will be saved in the phi nodes created by setupResultBlockPHINodes.
if (!IsUsedForZeroCmp) setupResultBlockPHINodes();
// Create the number of required load compare basic blocks.
// Update the terminator added by splitBasicBlock to branch to the first
// LoadCmpBlock.
StartBlock->getTerminator()->setSuccessor(0, LoadCmpBlocks[0]);
if (IsUsedForZeroCmp)
return getNumBlocks() == 1 ? getMemCmpEqZeroOneBlock()
: getMemCmpExpansionZeroCase();
// TODO: Handle more than one load pair per block in getMemCmpOneBlock().
if (getNumBlocks() == 1 && NumLoadsPerBlock == 1) return getMemCmpOneBlock();
for (unsigned I = 0; I < getNumBlocks(); ++I) {
return PhiRes;
// This function checks to see if an expansion of memcmp can be generated.
// It checks for constant compare size that is less than the max inline size.
// If an expansion cannot occur, returns false to leave as a library call.
// Otherwise, the library call is replaced with a new IR instruction sequence.
/// We want to transform:
/// %call = call signext i32 @memcmp(i8* %0, i8* %1, i64 15)
/// To:
/// loadbb:
/// %0 = bitcast i32* %buffer2 to i8*
/// %1 = bitcast i32* %buffer1 to i8*
/// %2 = bitcast i8* %1 to i64*
/// %3 = bitcast i8* %0 to i64*
/// %4 = load i64, i64* %2
/// %5 = load i64, i64* %3
/// %6 = call i64 @llvm.bswap.i64(i64 %4)
/// %7 = call i64 @llvm.bswap.i64(i64 %5)
/// %8 = sub i64 %6, %7
/// %9 = icmp ne i64 %8, 0
/// br i1 %9, label %res_block, label %loadbb1
/// res_block: ; preds = %loadbb2,
/// %loadbb1, %loadbb
/// %phi.src1 = phi i64 [ %6, %loadbb ], [ %22, %loadbb1 ], [ %36, %loadbb2 ]
/// %phi.src2 = phi i64 [ %7, %loadbb ], [ %23, %loadbb1 ], [ %37, %loadbb2 ]
/// %10 = icmp ult i64 %phi.src1, %phi.src2
/// %11 = select i1 %10, i32 -1, i32 1
/// br label %endblock
/// loadbb1: ; preds = %loadbb
/// %12 = bitcast i32* %buffer2 to i8*
/// %13 = bitcast i32* %buffer1 to i8*
/// %14 = bitcast i8* %13 to i32*
/// %15 = bitcast i8* %12 to i32*
/// %16 = getelementptr i32, i32* %14, i32 2
/// %17 = getelementptr i32, i32* %15, i32 2
/// %18 = load i32, i32* %16
/// %19 = load i32, i32* %17
/// %20 = call i32 @llvm.bswap.i32(i32 %18)
/// %21 = call i32 @llvm.bswap.i32(i32 %19)
/// %22 = zext i32 %20 to i64
/// %23 = zext i32 %21 to i64
/// %24 = sub i64 %22, %23
/// %25 = icmp ne i64 %24, 0
/// br i1 %25, label %res_block, label %loadbb2
/// loadbb2: ; preds = %loadbb1
/// %26 = bitcast i32* %buffer2 to i8*
/// %27 = bitcast i32* %buffer1 to i8*
/// %28 = bitcast i8* %27 to i16*
/// %29 = bitcast i8* %26 to i16*
/// %30 = getelementptr i16, i16* %28, i16 6
/// %31 = getelementptr i16, i16* %29, i16 6
/// %32 = load i16, i16* %30
/// %33 = load i16, i16* %31
/// %34 = call i16 @llvm.bswap.i16(i16 %32)
/// %35 = call i16 @llvm.bswap.i16(i16 %33)
/// %36 = zext i16 %34 to i64
/// %37 = zext i16 %35 to i64
/// %38 = sub i64 %36, %37
/// %39 = icmp ne i64 %38, 0
/// br i1 %39, label %res_block, label %loadbb3
/// loadbb3: ; preds = %loadbb2
/// %40 = bitcast i32* %buffer2 to i8*
/// %41 = bitcast i32* %buffer1 to i8*
/// %42 = getelementptr i8, i8* %41, i8 14
/// %43 = getelementptr i8, i8* %40, i8 14
/// %44 = load i8, i8* %42
/// %45 = load i8, i8* %43
/// %46 = zext i8 %44 to i32
/// %47 = zext i8 %45 to i32
/// %48 = sub i32 %46, %47
/// br label %endblock
/// endblock: ; preds = %res_block,
/// %loadbb3
/// %phi.res = phi i32 [ %48, %loadbb3 ], [ %11, %res_block ]
/// ret i32 %phi.res
static bool expandMemCmp(CallInst *CI, const TargetTransformInfo *TTI,
const TargetLowering *TLI, const DataLayout *DL) {
// Early exit from expansion if -Oz.
if (CI->getFunction()->optForMinSize())
return false;
// Early exit from expansion if size is not a constant.
ConstantInt *SizeCast = dyn_cast<ConstantInt>(CI->getArgOperand(2));
if (!SizeCast) {
return false;
const uint64_t SizeVal = SizeCast->getZExtValue();
if (SizeVal == 0) {
return false;
// TTI call to check if target would like to expand memcmp. Also, get the
// available load sizes.
const bool IsUsedForZeroCmp = isOnlyUsedInZeroEqualityComparison(CI);
const auto *const Options = TTI->enableMemCmpExpansion(IsUsedForZeroCmp);
if (!Options) return false;
const unsigned MaxNumLoads =
MemCmpExpansion Expansion(CI, SizeVal, *Options, MaxNumLoads,
IsUsedForZeroCmp, MemCmpNumLoadsPerBlock, *DL);
// Don't expand if this will require more loads than desired by the target.
if (Expansion.getNumLoads() == 0) {
return false;
Value *Res = Expansion.getMemCmpExpansion();
// Replace call with result of expansion and erase call.
return true;
bool CodeGenPrepare::optimizeCallInst(CallInst *CI, bool &ModifiedDT) {
BasicBlock *BB = CI->getParent();
// Lower inline assembly if we can.
// If we found an inline asm expession, and if the target knows how to
// lower it to normal LLVM code, do so now.
if (TLI && isa<InlineAsm>(CI->getCalledValue())) {
if (TLI->ExpandInlineAsm(CI)) {
// Avoid invalidating the iterator.
CurInstIterator = BB->begin();
// Avoid processing instructions out of order, which could cause
// reuse before a value is defined.
return true;
// Sink address computing for memory operands into the block.
if (optimizeInlineAsmInst(CI))
return true;
// Align the pointer arguments to this call if the target thinks it's a good
// idea
unsigned MinSize, PrefAlign;
if (TLI && TLI->shouldAlignPointerArgs(CI, MinSize, PrefAlign)) {
for (auto &Arg : CI->arg_operands()) {
// We want to align both objects whose address is used directly and
// objects whose address is used in casts and GEPs, though it only makes
// sense for GEPs if the offset is a multiple of the desired alignment and
// if size - offset meets the size threshold.
if (!Arg->getType()->isPointerTy())
APInt Offset(DL->getPointerSizeInBits(
Value *Val = Arg->stripAndAccumulateInBoundsConstantOffsets(*DL, Offset);
uint64_t Offset2 = Offset.getLimitedValue();
if ((Offset2 & (PrefAlign-1)) != 0)
AllocaInst *AI;
if ((AI = dyn_cast<AllocaInst>(Val)) && AI->getAlignment() < PrefAlign &&
DL->getTypeAllocSize(AI->getAllocatedType()) >= MinSize + Offset2)
// Global variables can only be aligned if they are defined in this
// object (i.e. they are uniquely initialized in this object), and
// over-aligning global variables that have an explicit section is
// forbidden.
GlobalVariable *GV;
if ((GV = dyn_cast<GlobalVariable>(Val)) && GV->canIncreaseAlignment() &&
GV->getPointerAlignment(*DL) < PrefAlign &&
DL->getTypeAllocSize(GV->getValueType()) >=
MinSize + Offset2)
// If this is a memcpy (or similar) then we may be able to improve the
// alignment
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));
// If we have a cold call site, try to sink addressing computation into the
// cold block. This interacts with our handling for loads and stores to
// ensure that we can fold all uses of a potential addressing computation
// into their uses. TODO: generalize this to work over profiling data
if (!OptSize && CI->hasFnAttr(Attribute::Cold))
for (auto &Arg : CI->arg_operands()) {
if (!Arg->getType()->isPointerTy())
unsigned AS = Arg->getType()->getPointerAddressSpace();
return optimizeMemoryInst(CI, Arg, Arg->getType(), AS);
IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI);
if (II) {
switch (II->getIntrinsicID()) {
default: break;
case Intrinsic::objectsize: {
// Lower all uses of llvm.objectsize.*
ConstantInt *RetVal =
lowerObjectSizeCall(II, *DL, TLInfo, /*MustSucceed=*/true);
// Substituting this can cause recursive simplifications, which can
// invalidate our iterator. Use a WeakTrackingVH to hold onto it in case
// this
// happens.
Value *CurValue = &*CurInstIterator;
WeakTrackingVH IterHandle(CurValue);
replaceAndRecursivelySimplify(CI, RetVal, TLInfo, nullptr);
// If the iterator instruction was recursively deleted, start over at the
// start of the block.
if (IterHandle != CurValue) {
CurInstIterator = BB->begin();
return true;
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;
// Sink a zext feeding stlxr/stxr before it, so it can be folded into it.
// Mark this instruction as "inserted by CGP", so that other
// optimizations don't touch it.
return true;
case Intrinsic::invariant_group_barrier:
return true;