Index: projects/clang380-import/contrib/llvm/include/llvm/IR/GlobalValue.h =================================================================== --- projects/clang380-import/contrib/llvm/include/llvm/IR/GlobalValue.h (revision 294176) +++ projects/clang380-import/contrib/llvm/include/llvm/IR/GlobalValue.h (revision 294177) @@ -1,370 +1,374 @@ //===-- llvm/GlobalValue.h - Class to represent a global value --*- C++ -*-===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file is a common base class of all globally definable objects. As such, // it is subclassed by GlobalVariable, GlobalAlias and by Function. This is // used because you can do certain things with these global objects that you // can't do to anything else. For example, use the address of one as a // constant. // //===----------------------------------------------------------------------===// #ifndef LLVM_IR_GLOBALVALUE_H #define LLVM_IR_GLOBALVALUE_H #include "llvm/IR/Constant.h" #include "llvm/IR/DerivedTypes.h" #include namespace llvm { class Comdat; class PointerType; class Module; namespace Intrinsic { enum ID : unsigned; } class GlobalValue : public Constant { GlobalValue(const GlobalValue &) = delete; public: /// @brief An enumeration for the kinds of linkage for global values. enum LinkageTypes { ExternalLinkage = 0,///< Externally visible function AvailableExternallyLinkage, ///< Available for inspection, not emission. LinkOnceAnyLinkage, ///< Keep one copy of function when linking (inline) LinkOnceODRLinkage, ///< Same, but only replaced by something equivalent. WeakAnyLinkage, ///< Keep one copy of named function when linking (weak) WeakODRLinkage, ///< Same, but only replaced by something equivalent. AppendingLinkage, ///< Special purpose, only applies to global arrays InternalLinkage, ///< Rename collisions when linking (static functions). PrivateLinkage, ///< Like Internal, but omit from symbol table. ExternalWeakLinkage,///< ExternalWeak linkage description. CommonLinkage ///< Tentative definitions. }; /// @brief An enumeration for the kinds of visibility of global values. enum VisibilityTypes { DefaultVisibility = 0, ///< The GV is visible HiddenVisibility, ///< The GV is hidden ProtectedVisibility ///< The GV is protected }; /// @brief Storage classes of global values for PE targets. enum DLLStorageClassTypes { DefaultStorageClass = 0, DLLImportStorageClass = 1, ///< Function to be imported from DLL DLLExportStorageClass = 2 ///< Function to be accessible from DLL. }; protected: GlobalValue(Type *Ty, ValueTy VTy, Use *Ops, unsigned NumOps, LinkageTypes Linkage, const Twine &Name, unsigned AddressSpace) : Constant(PointerType::get(Ty, AddressSpace), VTy, Ops, NumOps), ValueType(Ty), Linkage(Linkage), Visibility(DefaultVisibility), UnnamedAddr(0), DllStorageClass(DefaultStorageClass), ThreadLocal(NotThreadLocal), IntID((Intrinsic::ID)0U), Parent(nullptr) { setName(Name); } Type *ValueType; // Note: VC++ treats enums as signed, so an extra bit is required to prevent // Linkage and Visibility from turning into negative values. LinkageTypes Linkage : 5; // The linkage of this global unsigned Visibility : 2; // The visibility style of this global unsigned UnnamedAddr : 1; // This value's address is not significant unsigned DllStorageClass : 2; // DLL storage class unsigned ThreadLocal : 3; // Is this symbol "Thread Local", if so, what is // the desired model? static const unsigned GlobalValueSubClassDataBits = 19; private: // Give subclasses access to what otherwise would be wasted padding. // (19 + 3 + 2 + 1 + 2 + 5) == 32. unsigned SubClassData : GlobalValueSubClassDataBits; friend class Constant; void destroyConstantImpl(); Value *handleOperandChangeImpl(Value *From, Value *To, Use *U); protected: /// \brief The intrinsic ID for this subclass (which must be a Function). /// /// This member is defined by this class, but not used for anything. /// Subclasses can use it to store their intrinsic ID, if they have one. /// /// This is stored here to save space in Function on 64-bit hosts. Intrinsic::ID IntID; unsigned getGlobalValueSubClassData() const { return SubClassData; } void setGlobalValueSubClassData(unsigned V) { assert(V < (1 << GlobalValueSubClassDataBits) && "It will not fit"); SubClassData = V; } Module *Parent; // The containing module. public: enum ThreadLocalMode { NotThreadLocal = 0, GeneralDynamicTLSModel, LocalDynamicTLSModel, InitialExecTLSModel, LocalExecTLSModel }; ~GlobalValue() override { removeDeadConstantUsers(); // remove any dead constants using this. } unsigned getAlignment() const; bool hasUnnamedAddr() const { return UnnamedAddr; } void setUnnamedAddr(bool Val) { UnnamedAddr = Val; } bool hasComdat() const { return getComdat() != nullptr; } Comdat *getComdat(); const Comdat *getComdat() const { return const_cast(this)->getComdat(); } VisibilityTypes getVisibility() const { return VisibilityTypes(Visibility); } bool hasDefaultVisibility() const { return Visibility == DefaultVisibility; } bool hasHiddenVisibility() const { return Visibility == HiddenVisibility; } bool hasProtectedVisibility() const { return Visibility == ProtectedVisibility; } void setVisibility(VisibilityTypes V) { assert((!hasLocalLinkage() || V == DefaultVisibility) && "local linkage requires default visibility"); Visibility = V; } /// If the value is "Thread Local", its value isn't shared by the threads. bool isThreadLocal() const { return getThreadLocalMode() != NotThreadLocal; } void setThreadLocal(bool Val) { setThreadLocalMode(Val ? GeneralDynamicTLSModel : NotThreadLocal); } void setThreadLocalMode(ThreadLocalMode Val) { assert(Val == NotThreadLocal || getValueID() != Value::FunctionVal); ThreadLocal = Val; } ThreadLocalMode getThreadLocalMode() const { return static_cast(ThreadLocal); } DLLStorageClassTypes getDLLStorageClass() const { return DLLStorageClassTypes(DllStorageClass); } bool hasDLLImportStorageClass() const { return DllStorageClass == DLLImportStorageClass; } bool hasDLLExportStorageClass() const { return DllStorageClass == DLLExportStorageClass; } void setDLLStorageClass(DLLStorageClassTypes C) { DllStorageClass = C; } bool hasSection() const { return !StringRef(getSection()).empty(); } // It is unfortunate that we have to use "char *" in here since this is // always non NULL, but: // * The C API expects a null terminated string, so we cannot use StringRef. // * The C API expects us to own it, so we cannot use a std:string. // * For GlobalAliases we can fail to find the section and we have to // return "", so we cannot use a "const std::string &". const char *getSection() const; /// Global values are always pointers. PointerType *getType() const { return cast(User::getType()); } Type *getValueType() const { return ValueType; } static LinkageTypes getLinkOnceLinkage(bool ODR) { return ODR ? LinkOnceODRLinkage : LinkOnceAnyLinkage; } static LinkageTypes getWeakLinkage(bool ODR) { return ODR ? WeakODRLinkage : WeakAnyLinkage; } static bool isExternalLinkage(LinkageTypes Linkage) { return Linkage == ExternalLinkage; } static bool isAvailableExternallyLinkage(LinkageTypes Linkage) { return Linkage == AvailableExternallyLinkage; } static bool isLinkOnceODRLinkage(LinkageTypes Linkage) { return Linkage == LinkOnceODRLinkage; } static bool isLinkOnceLinkage(LinkageTypes Linkage) { return Linkage == LinkOnceAnyLinkage || Linkage == LinkOnceODRLinkage; } static bool isWeakAnyLinkage(LinkageTypes Linkage) { return Linkage == WeakAnyLinkage; } static bool isWeakODRLinkage(LinkageTypes Linkage) { return Linkage == WeakODRLinkage; } static bool isWeakLinkage(LinkageTypes Linkage) { return isWeakAnyLinkage(Linkage) || isWeakODRLinkage(Linkage); } static bool isAppendingLinkage(LinkageTypes Linkage) { return Linkage == AppendingLinkage; } static bool isInternalLinkage(LinkageTypes Linkage) { return Linkage == InternalLinkage; } static bool isPrivateLinkage(LinkageTypes Linkage) { return Linkage == PrivateLinkage; } static bool isLocalLinkage(LinkageTypes Linkage) { return isInternalLinkage(Linkage) || isPrivateLinkage(Linkage); } static bool isExternalWeakLinkage(LinkageTypes Linkage) { return Linkage == ExternalWeakLinkage; } static bool isCommonLinkage(LinkageTypes Linkage) { return Linkage == CommonLinkage; } /// Whether the definition of this global may be discarded if it is not used /// in its compilation unit. static bool isDiscardableIfUnused(LinkageTypes Linkage) { return isLinkOnceLinkage(Linkage) || isLocalLinkage(Linkage) || isAvailableExternallyLinkage(Linkage); } /// Whether the definition of this global may be replaced by something /// non-equivalent at link time. For example, if a function has weak linkage /// then the code defining it may be replaced by different code. static bool mayBeOverridden(LinkageTypes Linkage) { return Linkage == WeakAnyLinkage || Linkage == LinkOnceAnyLinkage || Linkage == CommonLinkage || Linkage == ExternalWeakLinkage; } /// Whether the definition of this global may be replaced at link time. NB: /// Using this method outside of the code generators is almost always a /// mistake: when working at the IR level use mayBeOverridden instead as it /// knows about ODR semantics. static bool isWeakForLinker(LinkageTypes Linkage) { return Linkage == WeakAnyLinkage || Linkage == WeakODRLinkage || Linkage == LinkOnceAnyLinkage || Linkage == LinkOnceODRLinkage || Linkage == CommonLinkage || Linkage == ExternalWeakLinkage; } bool hasExternalLinkage() const { return isExternalLinkage(Linkage); } bool hasAvailableExternallyLinkage() const { return isAvailableExternallyLinkage(Linkage); } bool hasLinkOnceLinkage() const { return isLinkOnceLinkage(Linkage); } bool hasLinkOnceODRLinkage() const { return isLinkOnceODRLinkage(Linkage); } bool hasWeakLinkage() const { return isWeakLinkage(Linkage); } bool hasWeakAnyLinkage() const { return isWeakAnyLinkage(Linkage); } bool hasWeakODRLinkage() const { return isWeakODRLinkage(Linkage); } bool hasAppendingLinkage() const { return isAppendingLinkage(Linkage); } bool hasInternalLinkage() const { return isInternalLinkage(Linkage); } bool hasPrivateLinkage() const { return isPrivateLinkage(Linkage); } bool hasLocalLinkage() const { return isLocalLinkage(Linkage); } bool hasExternalWeakLinkage() const { return isExternalWeakLinkage(Linkage); } bool hasCommonLinkage() const { return isCommonLinkage(Linkage); } void setLinkage(LinkageTypes LT) { if (isLocalLinkage(LT)) Visibility = DefaultVisibility; Linkage = LT; } LinkageTypes getLinkage() const { return Linkage; } bool isDiscardableIfUnused() const { return isDiscardableIfUnused(Linkage); } bool mayBeOverridden() const { return mayBeOverridden(Linkage); } bool isWeakForLinker() const { return isWeakForLinker(Linkage); } /// Copy all additional attributes (those not needed to create a GlobalValue) /// from the GlobalValue Src to this one. virtual void copyAttributesFrom(const GlobalValue *Src); /// If special LLVM prefix that is used to inform the asm printer to not emit /// usual symbol prefix before the symbol name is used then return linkage /// name after skipping this special LLVM prefix. static StringRef getRealLinkageName(StringRef Name) { if (!Name.empty() && Name[0] == '\1') return Name.substr(1); return Name; } /// @name Materialization /// Materialization is used to construct functions only as they're needed. This /// is useful to reduce memory usage in LLVM or parsing work done by the /// BitcodeReader to load the Module. /// @{ /// If this function's Module is being lazily streamed in functions from disk /// or some other source, this method can be used to check to see if the /// function has been read in yet or not. bool isMaterializable() const; /// Make sure this GlobalValue is fully read. If the module is corrupt, this /// returns true and fills in the optional string with information about the /// problem. If successful, this returns false. std::error_code materialize(); /// @} /// Return true if the primary definition of this global value is outside of /// the current translation unit. bool isDeclaration() const; bool isDeclarationForLinker() const { if (hasAvailableExternallyLinkage()) return true; return isDeclaration(); } /// Returns true if this global's definition will be the one chosen by the /// linker. bool isStrongDefinitionForLinker() const { return !(isDeclarationForLinker() || isWeakForLinker()); } + // Returns true if the alignment of the value can be unilaterally + // increased. + bool canIncreaseAlignment() const; + /// This method unlinks 'this' from the containing module, but does not delete /// it. virtual void removeFromParent() = 0; /// This method unlinks 'this' from the containing module and deletes it. virtual void eraseFromParent() = 0; /// Get the module that this global value is contained inside of... Module *getParent() { return Parent; } const Module *getParent() const { return Parent; } // Methods for support type inquiry through isa, cast, and dyn_cast: static bool classof(const Value *V) { return V->getValueID() == Value::FunctionVal || V->getValueID() == Value::GlobalVariableVal || V->getValueID() == Value::GlobalAliasVal; } }; } // End llvm namespace #endif Index: projects/clang380-import/contrib/llvm/lib/CodeGen/CodeGenPrepare.cpp =================================================================== --- projects/clang380-import/contrib/llvm/lib/CodeGen/CodeGenPrepare.cpp (revision 294176) +++ projects/clang380-import/contrib/llvm/lib/CodeGen/CodeGenPrepare.cpp (revision 294177) @@ -1,5572 +1,5572 @@ //===- 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/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(NumAndsAdded, "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(NumAndCmpsMoved, "Number of and/cmp's pushed into branches"); STATISTIC(NumStoreExtractExposed, "Number of store(extractelement) exposed"); static cl::opt DisableBranchOpts( "disable-cgp-branch-opts", cl::Hidden, cl::init(false), cl::desc("Disable branch optimizations in CodeGenPrepare")); static cl::opt DisableGCOpts("disable-cgp-gc-opts", cl::Hidden, cl::init(false), cl::desc("Disable GC optimizations in CodeGenPrepare")); static cl::opt DisableSelectToBranch( "disable-cgp-select2branch", cl::Hidden, cl::init(false), cl::desc("Disable select to branch conversion.")); static cl::opt AddrSinkUsingGEPs( "addr-sink-using-gep", cl::Hidden, cl::init(false), cl::desc("Address sinking in CGP using GEPs.")); static cl::opt EnableAndCmpSinking( "enable-andcmp-sinking", cl::Hidden, cl::init(true), cl::desc("Enable sinkinig and/cmp into branches.")); static cl::opt DisableStoreExtract( "disable-cgp-store-extract", cl::Hidden, cl::init(false), cl::desc("Disable store(extract) optimizations in CodeGenPrepare")); static cl::opt StressStoreExtract( "stress-cgp-store-extract", cl::Hidden, cl::init(false), cl::desc("Stress test store(extract) optimizations in CodeGenPrepare")); static cl::opt 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 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 SetOfInstrs; typedef PointerIntPair TypeIsSExt; typedef DenseMap InstrToOrigTy; class TypePromotionTransaction; class CodeGenPrepare : public FunctionPass { const TargetMachine *TM; const TargetLowering *TLI; const TargetTransformInfo *TTI; const TargetLibraryInfo *TLInfo; /// 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 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; /// 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; public: static char ID; // Pass identification, replacement for typeid 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(); AU.addRequired(); AU.addRequired(); } 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 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 sinkAndCmp(Function &F); bool extLdPromotion(TypePromotionTransaction &TPT, LoadInst *&LI, Instruction *&Inst, const SmallVectorImpl &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; // Clear per function information. InsertedInsts.clear(); PromotedInsts.clear(); ModifiedDT = false; if (TM) TLI = TM->getSubtargetImpl(F)->getTargetLowering(); TLInfo = &getAnalysis().getTLI(); TTI = &getAnalysis().getTTI(F); OptSize = F.optForSize(); /// 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 &BypassWidths = TLI->getBypassSlowDivWidths(); 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 there is a mask, compare against zero, and branch that can be combined // into a single target instruction, push the mask and compare into branch // users. Do this before OptimizeBlock -> OptimizeInst -> // OptimizeCmpExpression, which perturbs the pattern being searched for. 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); // Restart BB iteration if the dominator tree of the Function was changed if (ModifiedDTOnIteration) break; } EverMadeChange |= MadeChange; } SunkAddrs.clear(); if (!DisableBranchOpts) { MadeChange = false; SmallPtrSet WorkList; for (BasicBlock &BB : F) { SmallVector Successors(succ_begin(&BB), succ_end(&BB)); MadeChange |= ConstantFoldTerminator(&BB, true); if (!MadeChange) continue; for (SmallVectorImpl::iterator II = Successors.begin(), IE = Successors.end(); II != IE; ++II) if (pred_begin(*II) == pred_end(*II)) WorkList.insert(*II); } // Delete the dead blocks and any of their dead successors. MadeChange |= !WorkList.empty(); while (!WorkList.empty()) { BasicBlock *BB = *WorkList.begin(); WorkList.erase(BB); SmallVector Successors(succ_begin(BB), succ_end(BB)); DeleteDeadBlock(BB); for (SmallVectorImpl::iterator II = Successors.begin(), IE = Successors.end(); II != IE; ++II) if (pred_begin(*II) == pred_end(*II)) WorkList.insert(*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 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; } /// 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(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()) BB->moveBefore(&BB->getParent()->getEntryBlock()); // We have erased a block. Update the iterator. I = BB->getIterator(); } } 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) { 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++; // If this block doesn't end with an uncond branch, ignore it. BranchInst *BI = dyn_cast(BB->getTerminator()); if (!BI || !BI->isUnconditional()) continue; // 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()) { --BBI; while (isa(BBI)) { if (BBI == BB->begin()) break; --BBI; } if (!isa(BBI) && !isa(BBI)) continue; } // Do not break infinite loops. BasicBlock *DestBB = BI->getSuccessor(0); if (DestBB == BB) continue; if (!canMergeBlocks(BB, DestBB)) continue; eliminateMostlyEmptyBlock(BB); MadeChange = true; } return MadeChange; } /// 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(BBI++)) { for (const User *U : PN->users()) { const Instruction *UI = cast(U); if (UI->getParent() != DestBB || !isa(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(UI)) for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) { Instruction *Insn = dyn_cast(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(DestBB->begin()); if (!DestBBPN) return true; // no conflict. // Collect the preds of BB. SmallPtrSet BBPreds; if (const PHINode *BBPN = dyn_cast(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) BBPreds.insert(BBPN->getIncomingBlock(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(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(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(BB->getTerminator()); BasicBlock *DestBB = BI->getSuccessor(0); DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB); // 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()) BB->moveBefore(&BB->getParent()->getEntryBlock()); DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); return; } } // 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(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(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) PN->addIncoming(InValPhi->getIncomingValue(i), InValPhi->getIncomingBlock(i)); } else { // Otherwise, add one instance of the dominating value for each edge that // we will be adding. if (PHINode *BBPN = dyn_cast(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. BB->replaceAllUsesWith(DestBB); BB->eraseFromParent(); ++NumBlocksElim; 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 &AllRelocateCalls, DenseMap> &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, GCRelocateInst *> RelocateIdxMap; for (auto *ThisRelocate : AllRelocateCalls) { auto K = std::make_pair(ThisRelocate->getBasePtrIndex(), ThisRelocate->getDerivedPtrIndex()); RelocateIdxMap.insert(std::make_pair(K, ThisRelocate)); } for (auto &Item : RelocateIdxMap) { std::pair Key = Item.first; if (Key.first == Key.second) // Base relocation: nothing to insert continue; 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. continue; RelocateInstMap[MaybeBase->second].push_back(I); } } // Accepts a GEP and extracts the operands into a vector provided they're all // small integer constants static bool getGEPSmallConstantIntOffsetV(GetElementPtrInst *GEP, SmallVectorImpl &OffsetV) { for (unsigned i = 1; i < GEP->getNumOperands(); i++) { // Only accept small constant integer operands auto Op = dyn_cast(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; } // Takes a RelocatedBase (base pointer relocation instruction) and Targets to // replace, computes a replacement, and affects it. static bool simplifyRelocatesOffABase(GCRelocateInst *RelocatedBase, const SmallVectorImpl &Targets) { bool MadeChange = false; 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. continue; } 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. continue; } Value *Base = ToReplace->getBasePtr(); auto Derived = dyn_cast(ToReplace->getDerivedPtr()); if (!Derived || Derived->getPointerOperand() != Base) continue; SmallVector OffsetV; if (!getGEPSmallConstantIntOffsetV(Derived, OffsetV)) continue; // 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()); Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc()); // 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)); Replacement->takeName(ToReplace); // 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()); } ToReplace->replaceAllUsesWith(ActualReplacement); ToReplace->eraseFromParent(); 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 AllRelocateCalls; for (auto *U : I.users()) if (GCRelocateInst *Relocate = dyn_cast(U)) // Collect all the relocate calls associated with a statepoint AllRelocateCalls.push_back(Relocate); // 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> 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 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(*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(User)) { UserBB = PN->getIncomingBlock(TheUse); } // Preincrement use iterator so we don't invalidate it. ++UI; // 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()) continue; // 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; ++NumCastUses; } // If we removed all uses, nuke the cast. if (CI->use_empty()) { CI->eraseFromParent(); 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) { // 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) == TargetLowering::TypePromoteInteger) SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT); if (TLI.getTypeAction(CI->getContext(), DstVT) == TargetLowering::TypePromoteInteger) 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(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!"); #endif 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); CI->replaceAllUsesWith(Overflow); AddI->replaceAllUsesWith(UAdd); CI->eraseFromParent(); AddI->eraseFromParent(); 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) { BasicBlock *DefBB = CI->getParent(); /// Only insert a cmp in each block once. DenseMap 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(*UI); // Preincrement use iterator so we don't invalidate it. ++UI; // Don't bother for PHI nodes. if (isa(User)) continue; // 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); } // Replace a use of the cmp with a use of the new cmp. TheUse = InsertedCmp; MadeChange = true; ++NumCmpUses; } // If we removed all uses, nuke the cmp. 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; } /// 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(User)) { if (User->getOpcode() != Instruction::And || !isa(User->getOperand(1))) return false; const APInt &Cimm = cast(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 &InsertedShifts, const TargetLowering &TLI, const DataLayout &DL) { BasicBlock *UserBB = User->getParent(); DenseMap InsertedTruncs; TruncInst *TruncI = dyn_cast(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(*TruncUI); // Preincrement use iterator so we don't invalidate it. ++TruncUI; int ISDOpcode = TLI.InstructionOpcodeToISD(TruncUser->getOpcode()); if (!ISDOpcode) continue; // If the use is actually a legal node, there will not be an // implicit truncate. // 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))) continue; // Don't bother for PHI nodes. if (isa(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()); // Sink the shift if (ShiftI->getOpcode() == Instruction::AShr) InsertedShift = BinaryOperator::CreateAShr(ShiftI->getOperand(0), CI, "", &*InsertPt); else InsertedShift = BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI, "", &*InsertPt); // Sink the trunc BasicBlock::iterator TruncInsertPt = TruncUserBB->getFirstInsertionPt(); TruncInsertPt++; 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 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(*UI); // Preincrement use iterator so we don't invalidate it. ++UI; // Don't bother for PHI nodes. if (isa(User)) continue; if (!isExtractBitsCandidateUse(User)) continue; BasicBlock *UserBB = User->getParent(); if (UserBB == DefBB) { // If the shift and truncate instruction are in the same BB. The use of // the truncate(TruncUse) may still introduce another truncate if not // legal. In this case, we would like to sink both shift and truncate // instruction to the BB of TruncUse. // for example: // BB1: // i64 shift.result = lshr i64 opnd, imm // trunc.result = trunc shift.result to i16 // // BB2: // ----> We will have an implicit truncate here if the architecture does // not have i16 compare. // cmp i16 trunc.result, opnd2 // if (isa(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); continue; } // 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); else InsertedShift = BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI, "", &*InsertPt); MadeChange = true; } // Replace a use of the shift with a use of the new shift. TheUse = InsertedShift; } // If we removed all uses, nuke the shift. if (ShiftI->use_empty()) ShiftI->eraseFromParent(); return MadeChange; } // Translate a masked load intrinsic like // <16 x i32 > @llvm.masked.load( <16 x i32>* %addr, i32 align, // <16 x i1> %mask, <16 x i32> %passthru) // to a chain of basic blocks, with loading element one-by-one if // the appropriate mask bit is set // // %1 = bitcast i8* %addr to i32* // %2 = extractelement <16 x i1> %mask, i32 0 // %3 = icmp eq i1 %2, true // br i1 %3, label %cond.load, label %else // //cond.load: ; preds = %0 // %4 = getelementptr i32* %1, i32 0 // %5 = load i32* %4 // %6 = insertelement <16 x i32> undef, i32 %5, i32 0 // br label %else // //else: ; preds = %0, %cond.load // %res.phi.else = phi <16 x i32> [ %6, %cond.load ], [ undef, %0 ] // %7 = extractelement <16 x i1> %mask, i32 1 // %8 = icmp eq i1 %7, true // br i1 %8, label %cond.load1, label %else2 // //cond.load1: ; preds = %else // %9 = getelementptr i32* %1, i32 1 // %10 = load i32* %9 // %11 = insertelement <16 x i32> %res.phi.else, i32 %10, i32 1 // br label %else2 // //else2: ; preds = %else, %cond.load1 // %res.phi.else3 = phi <16 x i32> [ %11, %cond.load1 ], [ %res.phi.else, %else ] // %12 = extractelement <16 x i1> %mask, i32 2 // %13 = icmp eq i1 %12, true // br i1 %13, label %cond.load4, label %else5 // 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(Alignment)->getZExtValue(); VectorType *VecType = dyn_cast(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()); // Short-cut if the mask is all-true. bool IsAllOnesMask = isa(Mask) && cast(Mask)->isAllOnesValue(); if (IsAllOnesMask) { Value *NewI = Builder.CreateAlignedLoad(Ptr, AlignVal); CI->replaceAllUsesWith(NewI); CI->eraseFromParent(); return; } // Adjust alignment for the scalar instruction. AlignVal = std::min(AlignVal, VecType->getScalarSizeInBits()/8); // Bitcast %addr fron i8* to EltTy* Type *NewPtrType = EltTy->getPointerTo(cast(Ptr->getType())->getAddressSpace()); Value *FirstEltPtr = Builder.CreateBitCast(Ptr, NewPtrType); unsigned VectorWidth = VecType->getNumElements(); Value *UndefVal = UndefValue::get(VecType); // The result vector Value *VResult = UndefVal; if (isa(Mask)) { for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) { if (cast(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) { // Fill the "else" block, created in the previous iteration // // %res.phi.else3 = phi <16 x i32> [ %11, %cond.load1 ], [ %res.phi.else, %else ] // %mask_1 = extractelement <16 x i1> %mask, i32 Idx // %to_load = icmp eq i1 %mask_1, true // br i1 %to_load, label %cond.load, label %else // 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)); // Create "cond" block // // %EltAddr = getelementptr i32* %1, i32 0 // %Elt = load i32* %EltAddr // VResult = insertelement <16 x i32> VResult, i32 %Elt, i32 Idx // 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)); // Create "else" block, fill it in the next iteration 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(); } // Translate a masked store intrinsic, like // void @llvm.masked.store(<16 x i32> %src, <16 x i32>* %addr, i32 align, // <16 x i1> %mask) // to a chain of basic blocks, that stores element one-by-one if // the appropriate mask bit is set // // %1 = bitcast i8* %addr to i32* // %2 = extractelement <16 x i1> %mask, i32 0 // %3 = icmp eq i1 %2, true // br i1 %3, label %cond.store, label %else // // cond.store: ; preds = %0 // %4 = extractelement <16 x i32> %val, i32 0 // %5 = getelementptr i32* %1, i32 0 // store i32 %4, i32* %5 // br label %else // // else: ; preds = %0, %cond.store // %6 = extractelement <16 x i1> %mask, i32 1 // %7 = icmp eq i1 %6, true // br i1 %7, label %cond.store1, label %else2 // // cond.store1: ; preds = %else // %8 = extractelement <16 x i32> %val, i32 1 // %9 = getelementptr i32* %1, i32 1 // store i32 %8, i32* %9 // br label %else2 // . . . 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(Alignment)->getZExtValue(); VectorType *VecType = dyn_cast(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()); // Short-cut if the mask is all-true. bool IsAllOnesMask = isa(Mask) && cast(Mask)->isAllOnesValue(); if (IsAllOnesMask) { Builder.CreateAlignedStore(Src, Ptr, AlignVal); CI->eraseFromParent(); return; } // Adjust alignment for the scalar instruction. AlignVal = std::max(AlignVal, VecType->getScalarSizeInBits()/8); // Bitcast %addr fron i8* to EltTy* Type *NewPtrType = EltTy->getPointerTo(cast(Ptr->getType())->getAddressSpace()); Value *FirstEltPtr = Builder.CreateBitCast(Ptr, NewPtrType); unsigned VectorWidth = VecType->getNumElements(); if (isa(Mask)) { for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) { if (cast(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) { // Fill the "else" block, created in the previous iteration // // %mask_1 = extractelement <16 x i1> %mask, i32 Idx // %to_store = icmp eq i1 %mask_1, true // br i1 %to_store, label %cond.store, label %else // Value *Predicate = Builder.CreateExtractElement(Mask, Builder.getInt32(Idx)); Value *Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Predicate, ConstantInt::get(Predicate->getType(), 1)); // Create "cond" block // // %OneElt = extractelement <16 x i32> %Src, i32 Idx // %EltAddr = getelementptr i32* %1, i32 0 // %store i32 %OneElt, i32* %EltAddr // 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); // Create "else" block, fill it in the next iteration 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(); } // Translate a masked gather intrinsic like // <16 x i32 > @llvm.masked.gather.v16i32( <16 x i32*> %Ptrs, i32 4, // <16 x i1> %Mask, <16 x i32> %Src) // to a chain of basic blocks, with loading element one-by-one if // the appropriate mask bit is set // // % Ptrs = getelementptr i32, i32* %base, <16 x i64> %ind // % Mask0 = extractelement <16 x i1> %Mask, i32 0 // % ToLoad0 = icmp eq i1 % Mask0, true // br i1 % ToLoad0, label %cond.load, label %else // // cond.load: // % Ptr0 = extractelement <16 x i32*> %Ptrs, i32 0 // % Load0 = load i32, i32* % Ptr0, align 4 // % Res0 = insertelement <16 x i32> undef, i32 % Load0, i32 0 // br label %else // // else: // %res.phi.else = phi <16 x i32>[% Res0, %cond.load], [undef, % 0] // % Mask1 = extractelement <16 x i1> %Mask, i32 1 // % ToLoad1 = icmp eq i1 % Mask1, true // br i1 % ToLoad1, label %cond.load1, label %else2 // // cond.load1: // % Ptr1 = extractelement <16 x i32*> %Ptrs, i32 1 // % Load1 = load i32, i32* % Ptr1, align 4 // % Res1 = insertelement <16 x i32> %res.phi.else, i32 % Load1, i32 1 // br label %else2 // . . . // % Result = select <16 x i1> %Mask, <16 x i32> %res.phi.select, <16 x i32> %Src // ret <16 x i32> %Result 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(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(Alignment)->getZExtValue(); Builder.SetCurrentDebugLocation(CI->getDebugLoc()); Value *UndefVal = UndefValue::get(VecType); // The result vector Value *VResult = UndefVal; unsigned VectorWidth = VecType->getNumElements(); // Shorten the way if the mask is a vector of constants. bool IsConstMask = isa(Mask); if (IsConstMask) { for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) { if (cast(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) { // Fill the "else" block, created in the previous iteration // // %Mask1 = extractelement <16 x i1> %Mask, i32 1 // %ToLoad1 = icmp eq i1 %Mask1, true // br i1 %ToLoad1, label %cond.load, label %else // 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)); // Create "cond" block // // %EltAddr = getelementptr i32* %1, i32 0 // %Elt = load i32* %EltAddr // VResult = insertelement <16 x i32> VResult, i32 %Elt, i32 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)); // Create "else" block, fill it in the next iteration 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(); } // Translate a masked scatter intrinsic, like // void @llvm.masked.scatter.v16i32(<16 x i32> %Src, <16 x i32*>* %Ptrs, i32 4, // <16 x i1> %Mask) // to a chain of basic blocks, that stores element one-by-one if // the appropriate mask bit is set. // // % Ptrs = getelementptr i32, i32* %ptr, <16 x i64> %ind // % Mask0 = extractelement <16 x i1> % Mask, i32 0 // % ToStore0 = icmp eq i1 % Mask0, true // br i1 %ToStore0, label %cond.store, label %else // // cond.store: // % Elt0 = extractelement <16 x i32> %Src, i32 0 // % Ptr0 = extractelement <16 x i32*> %Ptrs, i32 0 // store i32 %Elt0, i32* % Ptr0, align 4 // br label %else // // else: // % Mask1 = extractelement <16 x i1> % Mask, i32 1 // % ToStore1 = icmp eq i1 % Mask1, true // br i1 % ToStore1, label %cond.store1, label %else2 // // cond.store1: // % Elt1 = extractelement <16 x i32> %Src, i32 1 // % Ptr1 = extractelement <16 x i32*> %Ptrs, i32 1 // store i32 % Elt1, i32* % Ptr1, align 4 // br label %else2 // . . . 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(Src->getType()) && "Unexpected data type in masked scatter intrinsic"); assert(isa(Ptrs->getType()) && isa(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(Alignment)->getZExtValue(); unsigned VectorWidth = Src->getType()->getVectorNumElements(); // Shorten the way if the mask is a vector of constants. bool IsConstMask = isa(Mask); if (IsConstMask) { for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) { if (cast(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) { // Fill the "else" block, created in the previous iteration // // % Mask1 = extractelement <16 x i1> % Mask, i32 Idx // % ToStore = icmp eq i1 % Mask1, true // br i1 % ToStore, label %cond.store, label %else // 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)); // Create "cond" block // // % Elt1 = extractelement <16 x i32> %Src, i32 1 // % Ptr1 = extractelement <16 x i32*> %Ptrs, i32 1 // %store i32 % Elt1, i32* % Ptr1 // 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); // Create "else" block, fill it in the next iteration 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(); } /// 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->getLargestLegalIntTypeSize()) 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()); Builder.SetInsertPoint(StartBlock->getTerminator()); Builder.SetCurrentDebugLocation(CountZeros->getDebugLoc()); // 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); StartBlock->getTerminator()->eraseFromParent(); // Create a PHI in the end block to select either the output of the intrinsic // or the bit width of the operand. Builder.SetInsertPoint(&EndBlock->front()); PHINode *PN = Builder.CreatePHI(Ty, 2, "ctz"); CountZeros->replaceAllUsesWith(PN); 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; } 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(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. SunkAddrs.clear(); 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()) continue; APInt Offset(DL->getPointerSizeInBits( cast(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(Val)) && AI->getAlignment() < PrefAlign && DL->getTypeAllocSize(AI->getAllocatedType()) >= MinSize + Offset2) AI->setAlignment(PrefAlign); // 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(Val)) && GV->hasUniqueInitializer() && - !GV->hasSection() && GV->getAlignment() < PrefAlign && + if ((GV = dyn_cast(Val)) && GV->canIncreaseAlignment() && + GV->getAlignment() < PrefAlign && DL->getTypeAllocSize(GV->getType()->getElementType()) >= MinSize + Offset2) GV->setAlignment(PrefAlign); } // If this is a memcpy (or similar) then we may be able to improve the // alignment if (MemIntrinsic *MI = dyn_cast(CI)) { unsigned Align = getKnownAlignment(MI->getDest(), *DL); if (MemTransferInst *MTI = dyn_cast(MI)) Align = std::min(Align, getKnownAlignment(MTI->getSource(), *DL)); if (Align > MI->getAlignment()) MI->setAlignment(ConstantInt::get(MI->getAlignmentType(), Align)); } } IntrinsicInst *II = dyn_cast(CI); if (II) { switch (II->getIntrinsicID()) { default: break; case Intrinsic::objectsize: { // Lower all uses of llvm.objectsize.* bool Min = (cast(II->getArgOperand(1))->getZExtValue() == 1); Type *ReturnTy = CI->getType(); Constant *RetVal = ConstantInt::get(ReturnTy, Min ? 0 : -1ULL); // Substituting this can cause recursive simplifications, which can // invalidate our iterator. Use a WeakVH to hold onto it in case this // happens. WeakVH IterHandle(&*CurInstIterator); replaceAndRecursivelySimplify(CI, RetVal, TLInfo, nullptr); // If the iterator instruction was recursively deleted, start over at the // start of the block. if (IterHandle != CurInstIterator.getNodePtrUnchecked()) { CurInstIterator = BB->begin(); SunkAddrs.clear(); } return true; } case Intrinsic::masked_load: { // Scalarize unsupported vector 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(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. ExtVal->moveBefore(CI); // Mark this instruction as "inserted by CGP", so that other // optimizations don't touch it. InsertedInsts.insert(ExtVal); return true; } case Intrinsic::invariant_group_barrier: II->replaceAllUsesWith(II->getArgOperand(0)); II->eraseFromParent(); return true; case Intrinsic::cttz: case Intrinsic::ctlz: // If counting zeros is expensive, try to avoid it. return despeculateCountZeros(II, TLI, DL, ModifiedDT); } if (TLI) { // Unknown address space. // TODO: Target hook to pick which address space the intrinsic cares // about? unsigned AddrSpace = ~0u; SmallVector PtrOps; Type *AccessTy; if (TLI->GetAddrModeArguments(II, PtrOps, AccessTy, AddrSpace)) while (!PtrOps.empty()) if (optimizeMemoryInst(II, PtrOps.pop_back_val(), AccessTy, AddrSpace)) return true; } } // From here on out we're working with named functions. if (!CI->getCalledFunction()) return false; // Lower all default uses of _chk calls. This is very similar // to what InstCombineCalls does, but here we are only lowering calls // to fortified library functions (e.g. __memcpy_chk) that have the default // "don't know" as the objectsize. Anything else should be left alone. FortifiedLibCallSimplifier Simplifier(TLInfo, true); if (Value *V = Simplifier.optimizeCall(CI)) { CI->replaceAllUsesWith(V); CI->eraseFromParent(); return true; } return false; } /// Look for opportunities to duplicate return instructions to the predecessor /// to enable tail call optimizations. The case it is currently looking for is: /// @code /// bb0: /// %tmp0 = tail call i32 @f0() /// br label %return /// bb1: /// %tmp1 = tail call i32 @f1() /// br label %return /// bb2: /// %tmp2 = tail call i32 @f2() /// br label %return /// return: /// %retval = phi i32 [ %tmp0, %bb0 ], [ %tmp1, %bb1 ], [ %tmp2, %bb2 ] /// ret i32 %retval /// @endcode /// /// => /// /// @code /// bb0: /// %tmp0 = tail call i32 @f0() /// ret i32 %tmp0 /// bb1: /// %tmp1 = tail call i32 @f1() /// ret i32 %tmp1 /// bb2: /// %tmp2 = tail call i32 @f2() /// ret i32 %tmp2 /// @endcode bool CodeGenPrepare::dupRetToEnableTailCallOpts(BasicBlock *BB) { if (!TLI) return false; ReturnInst *RI = dyn_cast(BB->getTerminator()); if (!RI) return false; PHINode *PN = nullptr; BitCastInst *BCI = nullptr; Value *V = RI->getReturnValue(); if (V) { BCI = dyn_cast(V); if (BCI) V = BCI->getOperand(0); PN = dyn_cast(V); if (!PN) return false; } if (PN && PN->getParent() != BB) return false; // It's not safe to eliminate the sign / zero extension of the return value. // See llvm::isInTailCallPosition(). const Function *F = BB->getParent(); AttributeSet CallerAttrs = F->getAttributes(); if (CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::ZExt) || CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::SExt)) return false; // Make sure there are no instructions between the PHI and return, or that the // return is the first instruction in the block. if (PN) { BasicBlock::iterator BI = BB->begin(); do { ++BI; } while (isa(BI)); if (&*BI == BCI) // Also skip over the bitcast. ++BI; if (&*BI != RI) return false; } else { BasicBlock::iterator BI = BB->begin(); while (isa(BI)) ++BI; if (&*BI != RI) return false; } /// Only dup the ReturnInst if the CallInst is likely to be emitted as a tail /// call. SmallVector TailCalls; if (PN) { for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) { CallInst *CI = dyn_cast(PN->getIncomingValue(I)); // Make sure the phi value is indeed produced by the tail call. if (CI && CI->hasOneUse() && CI->getParent() == PN->getIncomingBlock(I) && TLI->mayBeEmittedAsTailCall(CI)) TailCalls.push_back(CI); } } else { SmallPtrSet 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(&*RI)); if (RI == RE) continue; CallInst *CI = dyn_cast(&*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); // Conservatively require the attributes of the call to match those of the // return. Ignore noalias because it doesn't affect the call sequence. AttributeSet CalleeAttrs = CS.getAttributes(); if (AttrBuilder(CalleeAttrs, AttributeSet::ReturnIndex). removeAttribute(Attribute::NoAlias) != AttrBuilder(CalleeAttrs, AttributeSet::ReturnIndex). removeAttribute(Attribute::NoAlias)) continue; // Make sure the call instruction is followed by an unconditional branch to // the return block. BasicBlock *CallBB = CI->getParent(); BranchInst *BI = dyn_cast(CallBB->getTerminator()); if (!BI || !BI->isUnconditional() || BI->getSuccessor(0) != BB) continue; // Duplicate the return into CallBB. (void)FoldReturnIntoUncondBranch(RI, BB, CallBB); ModifiedDT = Changed = true; ++NumRetsDup; } // If we eliminated all predecessors of the block, delete the block now. if (Changed && !BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB)) BB->eraseFromParent(); return Changed; } //===----------------------------------------------------------------------===// // Memory Optimization //===----------------------------------------------------------------------===// namespace { /// This is an extended version of TargetLowering::AddrMode /// which holds actual Value*'s for register values. 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, /*PrintType=*/false); NeedPlus = true; } if (BaseOffs) { OS << (NeedPlus ? " + " : "") << BaseOffs; NeedPlus = true; } if (BaseReg) { OS << (NeedPlus ? " + " : "") << "Base:"; BaseReg->printAsOperand(OS, /*PrintType=*/false); NeedPlus = true; } if (Scale) { OS << (NeedPlus ? " + " : "") << Scale << "*"; ScaledReg->printAsOperand(OS, /*PrintType=*/false); } OS << ']'; } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) void ExtAddrMode::dump() const { print(dbgs()); dbgs() << '\n'; } #endif /// \brief This class provides transaction based operation on the IR. /// Every change made through this class is recorded in the internal state and /// can be undone (rollback) until commit is called. class TypePromotionTransaction { /// \brief This represents the common interface of the individual transaction. /// Each class implements the logic for doing one specific modification on /// the IR via the TypePromotionTransaction. class TypePromotionAction { protected: /// The Instruction modified. Instruction *Inst; public: /// \brief Constructor of the action. /// The constructor performs the related action on the IR. TypePromotionAction(Instruction *Inst) : Inst(Inst) {} virtual ~TypePromotionAction() {} /// \brief Undo the modification done by this action. /// When this method is called, the IR must be in the same state as it was /// before this action was applied. /// \pre Undoing the action works if and only if the IR is in the exact same /// state as it was directly after this action was applied. virtual void undo() = 0; /// \brief Advocate every change made by this action. /// When the results on the IR of the action are to be kept, it is important /// to call this function, otherwise hidden information may be kept forever. virtual void commit() { // Nothing to be done, this action is not doing anything. } }; /// \brief Utility to remember the position of an instruction. class InsertionHandler { /// Position of an instruction. /// Either an instruction: /// - Is the first in a basic block: BB is used. /// - Has a previous instructon: PrevInst is used. union { Instruction *PrevInst; BasicBlock *BB; } Point; /// Remember whether or not the instruction had a previous instruction. bool HasPrevInstruction; public: /// \brief Record the position of \p Inst. InsertionHandler(Instruction *Inst) { BasicBlock::iterator It = Inst->getIterator(); HasPrevInstruction = (It != (Inst->getParent()->begin())); if (HasPrevInstruction) Point.PrevInst = &*--It; else Point.BB = Inst->getParent(); } /// \brief Insert \p Inst at the recorded position. 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); } } }; /// \brief Move an instruction before another. class InstructionMoveBefore : public TypePromotionAction { /// Original position of the instruction. InsertionHandler Position; public: /// \brief Move \p Inst before \p Before. InstructionMoveBefore(Instruction *Inst, Instruction *Before) : TypePromotionAction(Inst), Position(Inst) { DEBUG(dbgs() << "Do: move: " << *Inst << "\nbefore: " << *Before << "\n"); Inst->moveBefore(Before); } /// \brief Move the instruction back to its original position. void undo() override { DEBUG(dbgs() << "Undo: moveBefore: " << *Inst << "\n"); Position.insert(Inst); } }; /// \brief Set the operand of an instruction with a new value. class OperandSetter : public TypePromotionAction { /// Original operand of the instruction. Value *Origin; /// Index of the modified instruction. unsigned Idx; public: /// \brief Set \p Idx operand of \p Inst with \p NewVal. 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); } /// \brief Restore the original value of the instruction. void undo() override { DEBUG(dbgs() << "Undo: setOperand:" << Idx << "\n" << "for: " << *Inst << "\n" << "with: " << *Origin << "\n"); Inst->setOperand(Idx, Origin); } }; /// \brief Hide the operands of an instruction. /// Do as if this instruction was not using any of its operands. class OperandsHider : public TypePromotionAction { /// The list of original operands. SmallVector OriginalValues; public: /// \brief Remove \p Inst from the uses of the operands of \p Inst. 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) { // Save the current operand. Value *Val = Inst->getOperand(It); OriginalValues.push_back(Val); // Set a dummy one. // We could use OperandSetter here, but that would imply an overhead // that we are not willing to pay. Inst->setOperand(It, UndefValue::get(Val->getType())); } } /// \brief Restore the original list of uses. void undo() override { DEBUG(dbgs() << "Undo: OperandsHider: " << *Inst << "\n"); for (unsigned It = 0, EndIt = OriginalValues.size(); It != EndIt; ++It) Inst->setOperand(It, OriginalValues[It]); } }; /// \brief Build a truncate instruction. class TruncBuilder : public TypePromotionAction { Value *Val; public: /// \brief Build a truncate instruction of \p Opnd producing a \p Ty /// result. /// trunc Opnd to Ty. TruncBuilder(Instruction *Opnd, Type *Ty) : TypePromotionAction(Opnd) { IRBuilder<> Builder(Opnd); Val = Builder.CreateTrunc(Opnd, Ty, "promoted"); DEBUG(dbgs() << "Do: TruncBuilder: " << *Val << "\n"); } /// \brief Get the built value. Value *getBuiltValue() { return Val; } /// \brief Remove the built instruction. void undo() override { DEBUG(dbgs() << "Undo: TruncBuilder: " << *Val << "\n"); if (Instruction *IVal = dyn_cast(Val)) IVal->eraseFromParent(); } }; /// \brief Build a sign extension instruction. class SExtBuilder : public TypePromotionAction { Value *Val; public: /// \brief Build a sign extension instruction of \p Opnd producing a \p Ty /// result. /// sext Opnd to Ty. SExtBuilder(Instruction *InsertPt, Value *Opnd, Type *Ty) : TypePromotionAction(InsertPt) { IRBuilder<> Builder(InsertPt); Val = Builder.CreateSExt(Opnd, Ty, "promoted"); DEBUG(dbgs() << "Do: SExtBuilder: " << *Val << "\n"); } /// \brief Get the built value. Value *getBuiltValue() { return Val; } /// \brief Remove the built instruction. void undo() override { DEBUG(dbgs() << "Undo: SExtBuilder: " << *Val << "\n"); if (Instruction *IVal = dyn_cast(Val)) IVal->eraseFromParent(); } }; /// \brief Build a zero extension instruction. class ZExtBuilder : public TypePromotionAction { Value *Val; public: /// \brief Build a zero extension instruction of \p Opnd producing a \p Ty /// result. /// zext Opnd to Ty. ZExtBuilder(Instruction *InsertPt, Value *Opnd, Type *Ty) : TypePromotionAction(InsertPt) { IRBuilder<> Builder(InsertPt); Val = Builder.CreateZExt(Opnd, Ty, "promoted"); DEBUG(dbgs() << "Do: ZExtBuilder: " << *Val << "\n"); } /// \brief Get the built value. Value *getBuiltValue() { return Val; } /// \brief Remove the built instruction. void undo() override { DEBUG(dbgs() << "Undo: ZExtBuilder: " << *Val << "\n"); if (Instruction *IVal = dyn_cast(Val)) IVal->eraseFromParent(); } }; /// \brief Mutate an instruction to another type. class TypeMutator : public TypePromotionAction { /// Record the original type. Type *OrigTy; public: /// \brief Mutate the type of \p Inst into \p NewTy. TypeMutator(Instruction *Inst, Type *NewTy) : TypePromotionAction(Inst), OrigTy(Inst->getType()) { DEBUG(dbgs() << "Do: MutateType: " << *Inst << " with " << *NewTy << "\n"); Inst->mutateType(NewTy); } /// \brief Mutate the instruction back to its original type. void undo() override { DEBUG(dbgs() << "Undo: MutateType: " << *Inst << " with " << *OrigTy << "\n"); Inst->mutateType(OrigTy); } }; /// \brief Replace the uses of an instruction by another instruction. class UsesReplacer : public TypePromotionAction { /// Helper structure to keep track of the replaced uses. struct InstructionAndIdx { /// The instruction using the instruction. Instruction *Inst; /// The index where this instruction is used for Inst. unsigned Idx; InstructionAndIdx(Instruction *Inst, unsigned Idx) : Inst(Inst), Idx(Idx) {} }; /// Keep track of the original uses (pair Instruction, Index). SmallVector OriginalUses; typedef SmallVectorImpl::iterator use_iterator; public: /// \brief Replace all the use of \p Inst by \p New. UsesReplacer(Instruction *Inst, Value *New) : TypePromotionAction(Inst) { DEBUG(dbgs() << "Do: UsersReplacer: " << *Inst << " with " << *New << "\n"); // Record the original uses. for (Use &U : Inst->uses()) { Instruction *UserI = cast(U.getUser()); OriginalUses.push_back(InstructionAndIdx(UserI, U.getOperandNo())); } // Now, we can replace the uses. Inst->replaceAllUsesWith(New); } /// \brief Reassign the original uses of Inst to Inst. 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); } } }; /// \brief Remove an instruction from the IR. class InstructionRemover : public TypePromotionAction { /// Original position of the instruction. InsertionHandler Inserter; /// Helper structure to hide all the link to the instruction. In other /// words, this helps to do as if the instruction was removed. OperandsHider Hider; /// Keep track of the uses replaced, if any. UsesReplacer *Replacer; public: /// \brief Remove all reference of \p Inst and optinally replace all its /// uses with New. /// \pre If !Inst->use_empty(), then New != nullptr 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; } /// \brief Really remove the instruction. void commit() override { delete Inst; } /// \brief Resurrect the instruction and reassign it to the proper uses if /// new value was provided when build this action. void undo() override { DEBUG(dbgs() << "Undo: InstructionRemover: " << *Inst << "\n"); Inserter.insert(Inst); if (Replacer) Replacer->undo(); Hider.undo(); } }; public: /// Restoration point. /// The restoration point is a pointer to an action instead of an iterator /// because the iterator may be invalidated but not the pointer. typedef const TypePromotionAction *ConstRestorationPt; /// Advocate every changes made in that transaction. void commit(); /// Undo all the changes made after the given point. void rollback(ConstRestorationPt Point); /// Get the current restoration point. ConstRestorationPt getRestorationPoint() const; /// \name API for IR modification with state keeping to support rollback. /// @{ /// Same as Instruction::setOperand. void setOperand(Instruction *Inst, unsigned Idx, Value *NewVal); /// Same as Instruction::eraseFromParent. void eraseInstruction(Instruction *Inst, Value *NewVal = nullptr); /// Same as Value::replaceAllUsesWith. void replaceAllUsesWith(Instruction *Inst, Value *New); /// Same as Value::mutateType. void mutateType(Instruction *Inst, Type *NewTy); /// Same as IRBuilder::createTrunc. Value *createTrunc(Instruction *Opnd, Type *Ty); /// Same as IRBuilder::createSExt. Value *createSExt(Instruction *Inst, Value *Opnd, Type *Ty); /// Same as IRBuilder::createZExt. Value *createZExt(Instruction *Inst, Value *Opnd, Type *Ty); /// Same as Instruction::moveBefore. void moveBefore(Instruction *Inst, Instruction *Before); /// @} private: /// The ordered list of actions made so far. SmallVector, 16> Actions; typedef SmallVectorImpl>::iterator CommitPt; }; void TypePromotionTransaction::setOperand(Instruction *Inst, unsigned Idx, Value *NewVal) { Actions.push_back( make_unique(Inst, Idx, NewVal)); } void TypePromotionTransaction::eraseInstruction(Instruction *Inst, Value *NewVal) { Actions.push_back( make_unique(Inst, NewVal)); } void TypePromotionTransaction::replaceAllUsesWith(Instruction *Inst, Value *New) { Actions.push_back(make_unique(Inst, New)); } void TypePromotionTransaction::mutateType(Instruction *Inst, Type *NewTy) { Actions.push_back(make_unique(Inst, NewTy)); } Value *TypePromotionTransaction::createTrunc(Instruction *Opnd, Type *Ty) { std::unique_ptr 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 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 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(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 Curr = Actions.pop_back_val(); Curr->undo(); } } /// \brief A helper class for matching addressing modes. /// /// This encapsulates the logic for matching the target-legal addressing modes. class AddressingModeMatcher { SmallVectorImpl &AddrModeInsts; const TargetMachine &TM; const TargetLowering &TLI; const DataLayout &DL; /// AccessTy/MemoryInst - This is the type for the access (e.g. double) and /// the memory instruction that we're computing this address for. Type *AccessTy; unsigned AddrSpace; Instruction *MemoryInst; /// This is the addressing mode that we're building up. This is /// part of the return value of this addressing mode matching stuff. ExtAddrMode &AddrMode; /// The instructions inserted by other CodeGenPrepare optimizations. const SetOfInstrs &InsertedInsts; /// A map from the instructions to their type before promotion. InstrToOrigTy &PromotedInsts; /// The ongoing transaction where every action should be registered. TypePromotionTransaction &TPT; /// This is set to true when we should not do profitability checks. /// When true, IsProfitableToFoldIntoAddressingMode always returns true. bool IgnoreProfitability; AddressingModeMatcher(SmallVectorImpl &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: /// Find the maximal addressing mode that a load/store of V can fold, /// give an access type of AccessTy. This returns a list of involved /// instructions in AddrModeInsts. /// \p InsertedInsts The instructions inserted by other CodeGenPrepare /// optimizations. /// \p PromotedInsts maps the instructions to their type before promotion. /// \p The ongoing transaction where every action should be registered. static ExtAddrMode Match(Value *V, Type *AccessTy, unsigned AS, Instruction *MemoryInst, SmallVectorImpl &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; }; /// Try adding ScaleReg*Scale to the current addressing mode. /// Return true and update AddrMode if this addr mode is legal for the target, /// false if not. bool AddressingModeMatcher::matchScaledValue(Value *ScaleReg, int64_t Scale, unsigned Depth) { // If Scale is 1, then this is the same as adding ScaleReg to the addressing // mode. Just process that directly. if (Scale == 1) return matchAddr(ScaleReg, Depth); // If the scale is 0, it takes nothing to add this. if (Scale == 0) return true; // If we already have a scale of this value, we can add to it, otherwise, we // need an available scale field. if (AddrMode.Scale != 0 && AddrMode.ScaledReg != ScaleReg) return false; ExtAddrMode TestAddrMode = AddrMode; // Add scale to turn X*4+X*3 -> X*7. This could also do things like // [A+B + A*7] -> [B+A*8]. TestAddrMode.Scale += Scale; TestAddrMode.ScaledReg = ScaleReg; // If the new address isn't legal, bail out. if (!TLI.isLegalAddressingMode(DL, TestAddrMode, AccessTy, AddrSpace)) return false; // It was legal, so commit it. AddrMode = TestAddrMode; // Okay, we decided that we can add ScaleReg+Scale to AddrMode. Check now // to see if ScaleReg is actually X+C. If so, we can turn this into adding // X*Scale + C*Scale to addr mode. ConstantInt *CI = nullptr; Value *AddLHS = nullptr; if (isa(ScaleReg) && // not a constant expr. match(ScaleReg, m_Add(m_Value(AddLHS), m_ConstantInt(CI)))) { TestAddrMode.ScaledReg = AddLHS; TestAddrMode.BaseOffs += CI->getSExtValue()*TestAddrMode.Scale; // If this addressing mode is legal, commit it and remember that we folded // this instruction. if (TLI.isLegalAddressingMode(DL, TestAddrMode, AccessTy, AddrSpace)) { AddrModeInsts.push_back(cast(ScaleReg)); AddrMode = TestAddrMode; return true; } } // Otherwise, not (x+c)*scale, just return what we have. return true; } /// This is a little filter, which returns true if an addressing computation /// involving I might be folded into a load/store accessing it. /// This doesn't need to be perfect, but needs to accept at least /// the set of instructions that MatchOperationAddr can. static bool MightBeFoldableInst(Instruction *I) { switch (I->getOpcode()) { case Instruction::BitCast: case Instruction::AddrSpaceCast: // Don't touch identity bitcasts. if (I->getType() == I->getOperand(0)->getType()) return false; return I->getType()->isPointerTy() || I->getType()->isIntegerTy(); case Instruction::PtrToInt: // PtrToInt is always a noop, as we know that the int type is pointer sized. return true; case Instruction::IntToPtr: // We know the input is intptr_t, so this is foldable. return true; case Instruction::Add: return true; case Instruction::Mul: case Instruction::Shl: // Can only handle X*C and X << C. return isa(I->getOperand(1)); case Instruction::GetElementPtr: return true; default: return false; } } /// \brief Check whether or not \p Val is a legal instruction for \p TLI. /// \note \p Val is assumed to be the product of some type promotion. /// Therefore if \p Val has an undefined state in \p TLI, this is assumed /// to be legal, as the non-promoted value would have had the same state. static bool isPromotedInstructionLegal(const TargetLowering &TLI, const DataLayout &DL, Value *Val) { Instruction *PromotedInst = dyn_cast(Val); if (!PromotedInst) return false; int ISDOpcode = TLI.InstructionOpcodeToISD(PromotedInst->getOpcode()); // If the ISDOpcode is undefined, it was undefined before the promotion. if (!ISDOpcode) return true; // Otherwise, check if the promoted instruction is legal or not. return TLI.isOperationLegalOrCustom( ISDOpcode, TLI.getValueType(DL, PromotedInst->getType())); } /// \brief Hepler class to perform type promotion. class TypePromotionHelper { /// \brief Utility function to check whether or not a sign or zero extension /// of \p Inst with \p ConsideredExtType can be moved through \p Inst by /// either using the operands of \p Inst or promoting \p Inst. /// The type of the extension is defined by \p IsSExt. /// In other words, check if: /// ext (Ty Inst opnd1 opnd2 ... opndN) to ConsideredExtType. /// #1 Promotion applies: /// ConsideredExtType Inst (ext opnd1 to ConsideredExtType, ...). /// #2 Operand reuses: /// ext opnd1 to ConsideredExtType. /// \p PromotedInsts maps the instructions to their type before promotion. static bool canGetThrough(const Instruction *Inst, Type *ConsideredExtType, const InstrToOrigTy &PromotedInsts, bool IsSExt); /// \brief Utility function to determine if \p OpIdx should be promoted when /// promoting \p Inst. static bool shouldExtOperand(const Instruction *Inst, int OpIdx) { return !(isa(Inst) && OpIdx == 0); } /// \brief Utility function to promote the operand of \p Ext when this /// operand is a promotable trunc or sext or zext. /// \p PromotedInsts maps the instructions to their type before promotion. /// \p CreatedInstsCost[out] contains the cost of all instructions /// created to promote the operand of Ext. /// Newly added extensions are inserted in \p Exts. /// Newly added truncates are inserted in \p Truncs. /// Should never be called directly. /// \return The promoted value which is used instead of Ext. static Value *promoteOperandForTruncAndAnyExt( Instruction *Ext, TypePromotionTransaction &TPT, InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost, SmallVectorImpl *Exts, SmallVectorImpl *Truncs, const TargetLowering &TLI); /// \brief Utility function to promote the operand of \p Ext when this /// operand is promotable and is not a supported trunc or sext. /// \p PromotedInsts maps the instructions to their type before promotion. /// \p CreatedInstsCost[out] contains the cost of all the instructions /// created to promote the operand of Ext. /// Newly added extensions are inserted in \p Exts. /// Newly added truncates are inserted in \p Truncs. /// Should never be called directly. /// \return The promoted value which is used instead of Ext. static Value *promoteOperandForOther(Instruction *Ext, TypePromotionTransaction &TPT, InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost, SmallVectorImpl *Exts, SmallVectorImpl *Truncs, const TargetLowering &TLI, bool IsSExt); /// \see promoteOperandForOther. static Value *signExtendOperandForOther( Instruction *Ext, TypePromotionTransaction &TPT, InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost, SmallVectorImpl *Exts, SmallVectorImpl *Truncs, const TargetLowering &TLI) { return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost, Exts, Truncs, TLI, true); } /// \see promoteOperandForOther. static Value *zeroExtendOperandForOther( Instruction *Ext, TypePromotionTransaction &TPT, InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost, SmallVectorImpl *Exts, SmallVectorImpl *Truncs, const TargetLowering &TLI) { return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost, Exts, Truncs, TLI, false); } public: /// Type for the utility function that promotes the operand of Ext. typedef Value *(*Action)(Instruction *Ext, TypePromotionTransaction &TPT, InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost, SmallVectorImpl *Exts, SmallVectorImpl *Truncs, const TargetLowering &TLI); /// \brief Given a sign/zero extend instruction \p Ext, return the approriate /// action to promote the operand of \p Ext instead of using Ext. /// \return NULL if no promotable action is possible with the current /// sign extension. /// \p InsertedInsts keeps track of all the instructions inserted by the /// other CodeGenPrepare optimizations. This information is important /// because we do not want to promote these instructions as CodeGenPrepare /// will reinsert them later. Thus creating an infinite loop: create/remove. /// \p PromotedInsts maps the instructions to their type before promotion. 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) { // The promotion helper does not know how to deal with vector types yet. // To be able to fix that, we would need to fix the places where we // statically extend, e.g., constants and such. if (Inst->getType()->isVectorTy()) return false; // We can always get through zext. if (isa(Inst)) return true; // sext(sext) is ok too. if (IsSExt && isa(Inst)) return true; // We can get through binary operator, if it is legal. In other words, the // binary operator must have a nuw or nsw flag. const BinaryOperator *BinOp = dyn_cast(Inst); if (BinOp && isa(BinOp) && ((!IsSExt && BinOp->hasNoUnsignedWrap()) || (IsSExt && BinOp->hasNoSignedWrap()))) return true; // Check if we can do the following simplification. // ext(trunc(opnd)) --> ext(opnd) if (!isa(Inst)) return false; Value *OpndVal = Inst->getOperand(0); // Check if we can use this operand in the extension. // If the type is larger than the result type of the extension, we cannot. if (!OpndVal->getType()->isIntegerTy() || OpndVal->getType()->getIntegerBitWidth() > ConsideredExtType->getIntegerBitWidth()) return false; // If the operand of the truncate is not an instruction, we will not have // any information on the dropped bits. // (Actually we could for constant but it is not worth the extra logic). Instruction *Opnd = dyn_cast(OpndVal); if (!Opnd) return false; // Check if the source of the type is narrow enough. // I.e., check that trunc just drops extended bits of the same kind of // the extension. // #1 get the type of the operand and check the kind of the extended bits. 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(Opnd)) || (!IsSExt && isa(Opnd))) OpndType = Opnd->getOperand(0)->getType(); else return false; // #2 check that the truncate just drops extended bits. return Inst->getType()->getIntegerBitWidth() >= OpndType->getIntegerBitWidth(); } TypePromotionHelper::Action TypePromotionHelper::getAction( Instruction *Ext, const SetOfInstrs &InsertedInsts, const TargetLowering &TLI, const InstrToOrigTy &PromotedInsts) { assert((isa(Ext) || isa(Ext)) && "Unexpected instruction type"); Instruction *ExtOpnd = dyn_cast(Ext->getOperand(0)); Type *ExtTy = Ext->getType(); bool IsSExt = isa(Ext); // If the operand of the extension is not an instruction, we cannot // get through. // If it, check we can get through. if (!ExtOpnd || !canGetThrough(ExtOpnd, ExtTy, PromotedInsts, IsSExt)) return nullptr; // Do not promote if the operand has been added by codegenprepare. // Otherwise, it means we are undoing an optimization that is likely to be // redone, thus causing potential infinite loop. if (isa(ExtOpnd) && InsertedInsts.count(ExtOpnd)) return nullptr; // SExt or Trunc instructions. // Return the related handler. if (isa(ExtOpnd) || isa(ExtOpnd) || isa(ExtOpnd)) return promoteOperandForTruncAndAnyExt; // Regular instruction. // Abort early if we will have to insert non-free instructions. 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 *Exts, SmallVectorImpl *Truncs, const TargetLowering &TLI) { // By construction, the operand of SExt is an instruction. Otherwise we cannot // get through it and this method should not be called. Instruction *SExtOpnd = cast(SExt->getOperand(0)); Value *ExtVal = SExt; bool HasMergedNonFreeExt = false; if (isa(SExtOpnd)) { // Replace s|zext(zext(opnd)) // => zext(opnd). HasMergedNonFreeExt = !TLI.isExtFree(SExtOpnd); Value *ZExt = TPT.createZExt(SExt, SExtOpnd->getOperand(0), SExt->getType()); TPT.replaceAllUsesWith(SExt, ZExt); TPT.eraseInstruction(SExt); ExtVal = ZExt; } else { // Replace z|sext(trunc(opnd)) or sext(sext(opnd)) // => z|sext(opnd). TPT.setOperand(SExt, 0, SExtOpnd->getOperand(0)); } CreatedInstsCost = 0; // Remove dead code. if (SExtOpnd->use_empty()) TPT.eraseInstruction(SExtOpnd); // Check if the extension is still needed. Instruction *ExtInst = dyn_cast(ExtVal); if (!ExtInst || ExtInst->getType() != ExtInst->getOperand(0)->getType()) { if (ExtInst) { if (Exts) Exts->push_back(ExtInst); CreatedInstsCost = !TLI.isExtFree(ExtInst) && !HasMergedNonFreeExt; } return ExtVal; } // At this point we have: ext ty opnd to ty. // Reassign the uses of ExtInst to the opnd and remove ExtInst. Value *NextVal = ExtInst->getOperand(0); TPT.eraseInstruction(ExtInst, NextVal); return NextVal; } Value *TypePromotionHelper::promoteOperandForOther( Instruction *Ext, TypePromotionTransaction &TPT, InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost, SmallVectorImpl *Exts, SmallVectorImpl *Truncs, const TargetLowering &TLI, bool IsSExt) { // By construction, the operand of Ext is an instruction. Otherwise we cannot // get through it and this method should not be called. Instruction *ExtOpnd = cast(Ext->getOperand(0)); CreatedInstsCost = 0; if (!ExtOpnd->hasOneUse()) { // ExtOpnd will be promoted. // All its uses, but Ext, will need to use a truncated value of the // promoted version. // Create the truncate now. Value *Trunc = TPT.createTrunc(Ext, ExtOpnd->getType()); if (Instruction *ITrunc = dyn_cast(Trunc)) { ITrunc->removeFromParent(); // Insert it just after the definition. ITrunc->insertAfter(ExtOpnd); if (Truncs) Truncs->push_back(ITrunc); } TPT.replaceAllUsesWith(ExtOpnd, Trunc); // Restore the operand of Ext (which has been replaced by the previous call // to replaceAllUsesWith) to avoid creating a cycle trunc <-> sext. TPT.setOperand(Ext, 0, ExtOpnd); } // Get through the Instruction: // 1. Update its type. // 2. Replace the uses of Ext by Inst. // 3. Extend each operand that needs to be extended. // Remember the original type of the instruction before promotion. // This is useful to know that the high bits are sign extended bits. PromotedInsts.insert(std::pair( ExtOpnd, TypeIsSExt(ExtOpnd->getType(), IsSExt))); // Step #1. TPT.mutateType(ExtOpnd, Ext->getType()); // Step #2. TPT.replaceAllUsesWith(Ext, ExtOpnd); // Step #3. 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; } // Check if we can statically extend the operand. Value *Opnd = ExtOpnd->getOperand(OpIdx); if (const ConstantInt *Cst = dyn_cast(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; } // UndefValue are typed, so we have to statically sign extend them. if (isa(Opnd)) { DEBUG(dbgs() << "Statically extend\n"); TPT.setOperand(ExtOpnd, OpIdx, UndefValue::get(Ext->getType())); continue; } // Otherwise we have to explicity sign extend the operand. // Check if Ext was reused to extend an operand. if (!ExtForOpnd) { // If yes, create a new one. DEBUG(dbgs() << "More operands to ext\n"); Value *ValForExtOpnd = IsSExt ? TPT.createSExt(Ext, Opnd, Ext->getType()) : TPT.createZExt(Ext, Opnd, Ext->getType()); if (!isa(ValForExtOpnd)) { TPT.setOperand(ExtOpnd, OpIdx, ValForExtOpnd); continue; } ExtForOpnd = cast(ValForExtOpnd); } if (Exts) Exts->push_back(ExtForOpnd); TPT.setOperand(ExtForOpnd, 0, Opnd); // Move the sign extension before the insertion point. TPT.moveBefore(ExtForOpnd, ExtOpnd); TPT.setOperand(ExtOpnd, OpIdx, ExtForOpnd); CreatedInstsCost += !TLI.isExtFree(ExtForOpnd); // If more sext are required, new instructions will have to be created. ExtForOpnd = nullptr; } if (ExtForOpnd == Ext) { DEBUG(dbgs() << "Extension is useless now\n"); TPT.eraseInstruction(Ext); } return ExtOpnd; } /// Check whether or not promoting an instruction to a wider type is profitable. /// \p NewCost gives the cost of extension instructions created by the /// promotion. /// \p OldCost gives the cost of extension instructions before the promotion /// plus the number of instructions that have been /// matched in the addressing mode the promotion. /// \p PromotedOperand is the value that has been promoted. /// \return True if the promotion is profitable, false otherwise. bool AddressingModeMatcher::isPromotionProfitable( unsigned NewCost, unsigned OldCost, Value *PromotedOperand) const { DEBUG(dbgs() << "OldCost: " << OldCost << "\tNewCost: " << NewCost << '\n'); // The cost of the new extensions is greater than the cost of the // old extension plus what we folded. // This is not profitable. if (NewCost > OldCost) return false; if (NewCost < OldCost) return true; // The promotion is neutral but it may help folding the sign extension in // loads for instance. // Check that we did not create an illegal instruction. return isPromotedInstructionLegal(TLI, DL, PromotedOperand); } /// Given an instruction or constant expr, see if we can fold the operation /// into the addressing mode. If so, update the addressing mode and return /// true, otherwise return false without modifying AddrMode. /// If \p MovedAway is not NULL, it contains the information of whether or /// not AddrInst has to be folded into the addressing mode on success. /// If \p MovedAway == true, \p AddrInst will not be part of the addressing /// because it has been moved away. /// Thus AddrInst must not be added in the matched instructions. /// This state can happen when AddrInst is a sext, since it may be moved away. /// Therefore, AddrInst may not be valid when MovedAway is true and it must /// not be referenced anymore. bool AddressingModeMatcher::matchOperationAddr(User *AddrInst, unsigned Opcode, unsigned Depth, bool *MovedAway) { // Avoid exponential behavior on extremely deep expression trees. if (Depth >= 5) return false; // By default, all matched instructions stay in place. if (MovedAway) *MovedAway = false; switch (Opcode) { case Instruction::PtrToInt: // PtrToInt is always a noop, as we know that the int type is pointer sized. return matchAddr(AddrInst->getOperand(0), Depth); case Instruction::IntToPtr: { auto AS = AddrInst->getType()->getPointerAddressSpace(); auto PtrTy = MVT::getIntegerVT(DL.getPointerSizeInBits(AS)); // This inttoptr is a no-op if the integer type is pointer sized. if (TLI.getValueType(DL, AddrInst->getOperand(0)->getType()) == PtrTy) return matchAddr(AddrInst->getOperand(0), Depth); return false; } case Instruction::BitCast: // BitCast is always a noop, and we can handle it as long as it is // int->int or pointer->pointer (we don't want int<->fp or something). if ((AddrInst->getOperand(0)->getType()->isPointerTy() || AddrInst->getOperand(0)->getType()->isIntegerTy()) && // Don't touch identity bitcasts. These were probably put here by LSR, // and we don't want to mess around with them. Assume it knows what it // is doing. 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: { // Check to see if we can merge in the RHS then the LHS. If so, we win. ExtAddrMode BackupAddrMode = AddrMode; unsigned OldSize = AddrModeInsts.size(); // Start a transaction at this point. // The LHS may match but not the RHS. // Therefore, we need a higher level restoration point to undo partially // matched operation. TypePromotionTransaction::ConstRestorationPt LastKnownGood = TPT.getRestorationPoint(); if (matchAddr(AddrInst->getOperand(1), Depth+1) && matchAddr(AddrInst->getOperand(0), Depth+1)) return true; // Restore the old addr mode info. AddrMode = BackupAddrMode; AddrModeInsts.resize(OldSize); TPT.rollback(LastKnownGood); // Otherwise this was over-aggressive. Try merging in the LHS then the RHS. if (matchAddr(AddrInst->getOperand(0), Depth+1) && matchAddr(AddrInst->getOperand(1), Depth+1)) return true; // Otherwise we definitely can't merge the ADD in. AddrMode = BackupAddrMode; AddrModeInsts.resize(OldSize); TPT.rollback(LastKnownGood); break; } //case Instruction::Or: // TODO: We can handle "Or Val, Imm" iff this OR is equivalent to an ADD. //break; case Instruction::Mul: case Instruction::Shl: { // Can only handle X*C and X << C. ConstantInt *RHS = dyn_cast(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: { // Scan the GEP. We check it if it contains constant offsets and at most // one variable offset. 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(*GTI)) { const StructLayout *SL = DL.getStructLayout(STy); unsigned Idx = cast(AddrInst->getOperand(i))->getZExtValue(); ConstantOffset += SL->getElementOffset(Idx); } else { uint64_t TypeSize = DL.getTypeAllocSize(GTI.getIndexedType()); if (ConstantInt *CI = dyn_cast(AddrInst->getOperand(i))) { ConstantOffset += CI->getSExtValue()*TypeSize; } else if (TypeSize) { // Scales of zero don't do anything. // We only allow one variable index at the moment. if (VariableOperand != -1) return false; // Remember the variable index. VariableOperand = i; VariableScale = TypeSize; } } } // A common case is for the GEP to only do a constant offset. In this case, // just add it to the disp field and check validity. if (VariableOperand == -1) { AddrMode.BaseOffs += ConstantOffset; if (ConstantOffset == 0 || TLI.isLegalAddressingMode(DL, AddrMode, AccessTy, AddrSpace)) { // Check to see if we can fold the base pointer in too. if (matchAddr(AddrInst->getOperand(0), Depth+1)) return true; } AddrMode.BaseOffs -= ConstantOffset; return false; } // Save the valid addressing mode in case we can't match. ExtAddrMode BackupAddrMode = AddrMode; unsigned OldSize = AddrModeInsts.size(); // See if the scale and offset amount is valid for this target. AddrMode.BaseOffs += ConstantOffset; // Match the base operand of the GEP. if (!matchAddr(AddrInst->getOperand(0), Depth+1)) { // If it couldn't be matched, just stuff the value in a register. if (AddrMode.HasBaseReg) { AddrMode = BackupAddrMode; AddrModeInsts.resize(OldSize); return false; } AddrMode.HasBaseReg = true; AddrMode.BaseReg = AddrInst->getOperand(0); } // Match the remaining variable portion of the GEP. if (!matchScaledValue(AddrInst->getOperand(VariableOperand), VariableScale, Depth)) { // If it couldn't be matched, try stuffing the base into a register // instead of matching it, and retrying the match of the scale. 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)) { // If even that didn't work, bail. AddrMode = BackupAddrMode; AddrModeInsts.resize(OldSize); return false; } } return true; } case Instruction::SExt: case Instruction::ZExt: { Instruction *Ext = dyn_cast(AddrInst); if (!Ext) return false; // Try to move this ext out of the way of the addressing mode. // Ask for a method for doing so. 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); // SExt has been moved away. // Thus either it will be rematched later in the recursive calls or it is // gone. Anyway, we must not fold it into the addressing mode at this point. // E.g., // op = add opnd, 1 // idx = ext op // addr = gep base, idx // is now: // promotedOpnd = ext opnd <- no match here // op = promoted_add promotedOpnd, 1 <- match (later in recursive calls) // addr = gep base, op <- match if (MovedAway) *MovedAway = true; assert(PromotedOperand && "TypePromotionHelper should have filtered out those cases"); ExtAddrMode BackupAddrMode = AddrMode; unsigned OldSize = AddrModeInsts.size(); if (!matchAddr(PromotedOperand, Depth) || // The total of the new cost is equal to the cost of the created // instructions. // The total of the old cost is equal to the cost of the extension plus // what we have saved in the addressing mode. !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; } /// If we can, try to add the value of 'Addr' into the current addressing mode. /// If Addr can't be added to AddrMode this returns false and leaves AddrMode /// unmodified. This assumes that Addr is either a pointer type or intptr_t /// for the target. /// bool AddressingModeMatcher::matchAddr(Value *Addr, unsigned Depth) { // Start a transaction at this point that we will rollback if the matching // fails. TypePromotionTransaction::ConstRestorationPt LastKnownGood = TPT.getRestorationPoint(); if (ConstantInt *CI = dyn_cast(Addr)) { // Fold in immediates if legal for the target. AddrMode.BaseOffs += CI->getSExtValue(); if (TLI.isLegalAddressingMode(DL, AddrMode, AccessTy, AddrSpace)) return true; AddrMode.BaseOffs -= CI->getSExtValue(); } else if (GlobalValue *GV = dyn_cast(Addr)) { // If this is a global variable, try to fold it into the addressing mode. if (!AddrMode.BaseGV) { AddrMode.BaseGV = GV; if (TLI.isLegalAddressingMode(DL, AddrMode, AccessTy, AddrSpace)) return true; AddrMode.BaseGV = nullptr; } } else if (Instruction *I = dyn_cast(Addr)) { ExtAddrMode BackupAddrMode = AddrMode; unsigned OldSize = AddrModeInsts.size(); // Check to see if it is possible to fold this operation. bool MovedAway = false; if (matchOperationAddr(I, I->getOpcode(), Depth, &MovedAway)) { // This instruction may have been moved away. If so, there is nothing // to check here. if (MovedAway) return true; // Okay, it's possible to fold this. Check to see if it is actually // *profitable* to do so. We use a simple cost model to avoid increasing // register pressure too much. if (I->hasOneUse() || isProfitableToFoldIntoAddressingMode(I, BackupAddrMode, AddrMode)) { AddrModeInsts.push_back(I); return true; } // It isn't profitable to do this, roll back. //cerr << "NOT FOLDING: " << *I; AddrMode = BackupAddrMode; AddrModeInsts.resize(OldSize); TPT.rollback(LastKnownGood); } } else if (ConstantExpr *CE = dyn_cast(Addr)) { if (matchOperationAddr(CE, CE->getOpcode(), Depth)) return true; TPT.rollback(LastKnownGood); } else if (isa(Addr)) { // Null pointer gets folded without affecting the addressing mode. return true; } // Worse case, the target should support [reg] addressing modes. :) if (!AddrMode.HasBaseReg) { AddrMode.HasBaseReg = true; AddrMode.BaseReg = Addr; // Still check for legality in case the target supports [imm] but not [i+r]. if (TLI.isLegalAddressingMode(DL, AddrMode, AccessTy, AddrSpace)) return true; AddrMode.HasBaseReg = false; AddrMode.BaseReg = nullptr; } // If the base register is already taken, see if we can do [r+r]. 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; } // Couldn't match. TPT.rollback(LastKnownGood); return false; } /// Check to see if all uses of OpVal by the specified inline asm call are due /// to memory operands. If so, return true, otherwise 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]; // Compute the constraint code and ConstraintType to use. TLI->ComputeConstraintToUse(OpInfo, SDValue()); // If this asm operand is our Value*, and if it isn't an indirect memory // operand, we can't fold it! if (OpInfo.CallOperandVal == OpVal && (OpInfo.ConstraintType != TargetLowering::C_Memory || !OpInfo.isIndirect)) return false; } return true; } /// Recursively walk all the uses of I until we find a memory use. /// If we find an obviously non-foldable instruction, return true. /// Add the ultimately found memory instructions to MemoryUses. static bool FindAllMemoryUses( Instruction *I, SmallVectorImpl> &MemoryUses, SmallPtrSetImpl &ConsideredInsts, const TargetMachine &TM) { // If we already considered this instruction, we're done. if (!ConsideredInsts.insert(I).second) return false; // If this is an obviously unfoldable instruction, bail out. if (!MightBeFoldableInst(I)) return true; // Loop over all the uses, recursively processing them. for (Use &U : I->uses()) { Instruction *UserI = cast(U.getUser()); if (LoadInst *LI = dyn_cast(UserI)) { MemoryUses.push_back(std::make_pair(LI, U.getOperandNo())); continue; } if (StoreInst *SI = dyn_cast(UserI)) { unsigned opNo = U.getOperandNo(); if (opNo == 0) return true; // Storing addr, not into addr. MemoryUses.push_back(std::make_pair(SI, opNo)); continue; } if (CallInst *CI = dyn_cast(UserI)) { InlineAsm *IA = dyn_cast(CI->getCalledValue()); if (!IA) return true; // If this is a memory operand, we're cool, otherwise bail out. if (!IsOperandAMemoryOperand(CI, IA, I, TM)) return true; continue; } if (FindAllMemoryUses(UserI, MemoryUses, ConsideredInsts, TM)) return true; } return false; } /// Return true if Val is already known to be live at the use site that we're /// folding it into. If so, there is no cost to include it in the addressing /// mode. KnownLive1 and KnownLive2 are two values that we know are live at the /// instruction already. bool AddressingModeMatcher::valueAlreadyLiveAtInst(Value *Val,Value *KnownLive1, Value *KnownLive2) { // If Val is either of the known-live values, we know it is live! if (Val == nullptr || Val == KnownLive1 || Val == KnownLive2) return true; // All values other than instructions and arguments (e.g. constants) are live. if (!isa(Val) && !isa(Val)) return true; // If Val is a constant sized alloca in the entry block, it is live, this is // true because it is just a reference to the stack/frame pointer, which is // live for the whole function. if (AllocaInst *AI = dyn_cast(Val)) if (AI->isStaticAlloca()) return true; // Check to see if this value is already used in the memory instruction's // block. If so, it's already live into the block at the very least, so we // can reasonably fold it. return Val->isUsedInBasicBlock(MemoryInst->getParent()); } /// It is possible for the addressing mode of the machine to fold the specified /// instruction into a load or store that ultimately uses it. /// However, the specified instruction has multiple uses. /// Given this, it may actually increase register pressure to fold it /// into the load. For example, consider this code: /// /// X = ... /// Y = X+1 /// use(Y) -> nonload/store /// Z = Y+1 /// load Z /// /// In this case, Y has multiple uses, and can be folded into the load of Z /// (yielding load [X+2]). However, doing this will cause both "X" and "X+1" to /// be live at the use(Y) line. If we don't fold Y into load Z, we use one /// fewer register. Since Y can't be folded into "use(Y)" we don't increase the /// number of computations either. /// /// Note that this (like most of CodeGenPrepare) is just a rough heuristic. If /// X was live across 'load Z' for other reasons, we actually *would* want to /// fold the addressing mode in the Z case. This would make Y die earlier. bool AddressingModeMatcher:: isProfitableToFoldIntoAddressingMode(Instruction *I, ExtAddrMode &AMBefore, ExtAddrMode &AMAfter) { if (IgnoreProfitability) return true; // AMBefore is the addressing mode before this instruction was folded into it, // and AMAfter is the addressing mode after the instruction was folded. Get // the set of registers referenced by AMAfter and subtract out those // referenced by AMBefore: this is the set of values which folding in this // address extends the lifetime of. // // Note that there are only two potential values being referenced here, // BaseReg and ScaleReg (global addresses are always available, as are any // folded immediates). Value *BaseReg = AMAfter.BaseReg, *ScaledReg = AMAfter.ScaledReg; // If the BaseReg or ScaledReg was referenced by the previous addrmode, their // lifetime wasn't extended by adding this instruction. if (valueAlreadyLiveAtInst(BaseReg, AMBefore.BaseReg, AMBefore.ScaledReg)) BaseReg = nullptr; if (valueAlreadyLiveAtInst(ScaledReg, AMBefore.BaseReg, AMBefore.ScaledReg)) ScaledReg = nullptr; // If folding this instruction (and it's subexprs) didn't extend any live // ranges, we're ok with it. if (!BaseReg && !ScaledReg) return true; // If all uses of this instruction are ultimately load/store/inlineasm's, // check to see if their addressing modes will include this instruction. If // so, we can fold it into all uses, so it doesn't matter if it has multiple // uses. SmallVector, 16> MemoryUses; SmallPtrSet ConsideredInsts; if (FindAllMemoryUses(I, MemoryUses, ConsideredInsts, TM)) return false; // Has a non-memory, non-foldable use! // Now that we know that all uses of this instruction are part of a chain of // computation involving only operations that could theoretically be folded // into a memory use, loop over each of these uses and see if they could // *actually* fold the instruction. SmallVector MatchedAddrModeInsts; for (unsigned i = 0, e = MemoryUses.size(); i != e; ++i) { Instruction *User = MemoryUses[i].first; unsigned OpNo = MemoryUses[i].second; // Get the access type of this use. If the use isn't a pointer, we don't // know what it accesses. Value *Address = User->getOperand(OpNo); PointerType *AddrTy = dyn_cast(Address->getType()); if (!AddrTy) return false; Type *AddressAccessTy = AddrTy->getElementType(); unsigned AS = AddrTy->getAddressSpace(); // Do a match against the root of this address, ignoring profitability. This // will tell us if the addressing mode for the memory operation will // *actually* cover the shared instruction. 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*?"); // The match was to check the profitability, the changes made are not // part of the original matcher. Therefore, they should be dropped // otherwise the original matcher will not present the right state. TPT.rollback(LastKnownGood); // If the match didn't cover I, then it won't be shared by it. if (std::find(MatchedAddrModeInsts.begin(), MatchedAddrModeInsts.end(), I) == MatchedAddrModeInsts.end()) return false; MatchedAddrModeInsts.clear(); } return true; } } // end anonymous namespace /// Return true if the specified values are defined in a /// different basic block than BB. static bool IsNonLocalValue(Value *V, BasicBlock *BB) { if (Instruction *I = dyn_cast(V)) return I->getParent() != BB; return false; } /// Load and Store Instructions often have addressing modes that can do /// significant amounts of computation. As such, instruction selection will try /// to get the load or store to do as much computation as possible for the /// program. The problem is that isel can only see within a single block. As /// such, we sink as much legal addressing mode work into the block as possible. /// /// This method is used to optimize both load/store and inline asms with memory /// operands. bool CodeGenPrepare::optimizeMemoryInst(Instruction *MemoryInst, Value *Addr, Type *AccessTy, unsigned AddrSpace) { Value *Repl = Addr; // Try to collapse single-value PHI nodes. This is necessary to undo // unprofitable PRE transformations. SmallVector worklist; SmallPtrSet Visited; worklist.push_back(Addr); // Use a worklist to iteratively look through PHI nodes, and ensure that // the addressing mode obtained from the non-PHI roots of the graph // are equivalent. Value *Consensus = nullptr; unsigned NumUsesConsensus = 0; bool IsNumUsesConsensusValid = false; SmallVector AddrModeInsts; ExtAddrMode AddrMode; TypePromotionTransaction TPT; TypePromotionTransaction::ConstRestorationPt LastKnownGood = TPT.getRestorationPoint(); while (!worklist.empty()) { Value *V = worklist.back(); worklist.pop_back(); // Break use-def graph loops. if (!Visited.insert(V).second) { Consensus = nullptr; break; } // For a PHI node, push all of its incoming values. if (PHINode *P = dyn_cast(V)) { for (Value *IncValue : P->incoming_values()) worklist.push_back(IncValue); continue; } // For non-PHIs, determine the addressing mode being computed. SmallVector NewAddrModeInsts; ExtAddrMode NewAddrMode = AddressingModeMatcher::Match( V, AccessTy, AddrSpace, MemoryInst, NewAddrModeInsts, *TM, InsertedInsts, PromotedInsts, TPT); // This check is broken into two cases with very similar code to avoid using // getNumUses() as much as possible. Some values have a lot of uses, so // calling getNumUses() unconditionally caused a significant compile-time // regression. if (!Consensus) { Consensus = V; AddrMode = NewAddrMode; AddrModeInsts = NewAddrModeInsts; continue; } else if (NewAddrMode == AddrMode) { if (!IsNumUsesConsensusValid) { NumUsesConsensus = Consensus->getNumUses(); IsNumUsesConsensusValid = true; } // Ensure that the obtained addressing mode is equivalent to that obtained // for all other roots of the PHI traversal. Also, when choosing one // such root as representative, select the one with the most uses in order // to keep the cost modeling heuristics in AddressingModeMatcher // applicable. unsigned NumUses = V->getNumUses(); if (NumUses > NumUsesConsensus) { Consensus = V; NumUsesConsensus = NumUses; AddrModeInsts = NewAddrModeInsts; } continue; } Consensus = nullptr; break; } // If the addressing mode couldn't be determined, or if multiple different // ones were determined, bail out now. if (!Consensus) { TPT.rollback(LastKnownGood); return false; } TPT.commit(); // Check to see if any of the instructions supersumed by this addr mode are // non-local to I's BB. bool AnyNonLocal = false; for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) { if (IsNonLocalValue(AddrModeInsts[i], MemoryInst->getParent())) { AnyNonLocal = true; break; } } // If all the instructions matched are already in this BB, don't do anything. if (!AnyNonLocal) { DEBUG(dbgs() << "CGP: Found local addrmode: " << AddrMode << "\n"); return false; } // Insert this computation right after this user. Since our caller is // scanning from the top of the BB to the bottom, reuse of the expr are // guaranteed to happen later. IRBuilder<> Builder(MemoryInst); // Now that we determined the addressing expression we want to use and know // that we have to sink it into this block. Check to see if we have already // done this for some other load/store instr in this block. If so, reuse the // computation. 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())) { // By default, we use the GEP-based method when AA is used later. This // prevents new inttoptr/ptrtoint pairs from degrading AA capabilities. DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for " << *MemoryInst << "\n"); Type *IntPtrTy = DL->getIntPtrType(Addr->getType()); Value *ResultPtr = nullptr, *ResultIndex = nullptr; // First, find the pointer. if (AddrMode.BaseReg && AddrMode.BaseReg->getType()->isPointerTy()) { ResultPtr = AddrMode.BaseReg; AddrMode.BaseReg = nullptr; } if (AddrMode.Scale && AddrMode.ScaledReg->getType()->isPointerTy()) { // We can't add more than one pointer together, nor can we scale a // pointer (both of which seem meaningless). if (ResultPtr || AddrMode.Scale != 1) return false; ResultPtr = AddrMode.ScaledReg; AddrMode.Scale = 0; } if (AddrMode.BaseGV) { if (ResultPtr) return false; ResultPtr = AddrMode.BaseGV; } // If the real base value actually came from an inttoptr, then the matcher // will look through it and provide only the integer value. In that case, // use it here. 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(); // Start with the base register. Do this first so that subsequent address // matching finds it last, which will prevent it from trying to match it // as the scaled value in case it happens to be a mul. That would be // problematic if we've sunk a different mul for the scale, because then // we'd end up sinking both muls. if (AddrMode.BaseReg) { Value *V = AddrMode.BaseReg; if (V->getType() != IntPtrTy) V = Builder.CreateIntCast(V, IntPtrTy, /*isSigned=*/true, "sunkaddr"); ResultIndex = V; } // Add the scale value. if (AddrMode.Scale) { Value *V = AddrMode.ScaledReg; if (V->getType() == IntPtrTy) { // done. } else if (cast(IntPtrTy)->getBitWidth() < cast(V->getType())->getBitWidth()) { V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr"); } else { // It is only safe to sign extend the BaseReg if we know that the math // required to create it did not overflow before we extend it. Since // the original IR value was tossed in favor of a constant back when // the AddrMode was created we need to bail out gracefully if widths // do not match instead of extending it. Instruction *I = dyn_cast_or_null(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; } // Add in the Base Offset if present. if (AddrMode.BaseOffs) { Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs); if (ResultIndex) { // We need to add this separately from the scale above to help with // SDAG consecutive load/store merging. 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; // Start with the base register. Do this first so that subsequent address // matching finds it last, which will prevent it from trying to match it // as the scaled value in case it happens to be a mul. That would be // problematic if we've sunk a different mul for the scale, because then // we'd end up sinking both muls. 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, /*isSigned=*/true, "sunkaddr"); Result = V; } // Add the scale value. if (AddrMode.Scale) { Value *V = AddrMode.ScaledReg; if (V->getType() == IntPtrTy) { // done. } else if (V->getType()->isPointerTy()) { V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr"); } else if (cast(IntPtrTy)->getBitWidth() < cast(V->getType())->getBitWidth()) { V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr"); } else { // It is only safe to sign extend the BaseReg if we know that the math // required to create it did not overflow before we extend it. Since // the original IR value was tossed in favor of a constant back when // the AddrMode was created we need to bail out gracefully if widths // do not match instead of extending it. Instruction *I = dyn_cast_or_null(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; } // Add in the BaseGV if present. if (AddrMode.BaseGV) { Value *V = Builder.CreatePtrToInt(AddrMode.BaseGV, IntPtrTy, "sunkaddr"); if (Result) Result = Builder.CreateAdd(Result, V, "sunkaddr"); else Result = V; } // Add in the Base Offset if present. 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 we have no uses, recursively delete the value and all dead instructions // using it. if (Repl->use_empty()) { // This can cause recursive deletion, which can invalidate our iterator. // Use a WeakVH to hold onto it in case this happens. WeakVH IterHandle(&*CurInstIterator); BasicBlock *BB = CurInstIterator->getParent(); RecursivelyDeleteTriviallyDeadInstructions(Repl, TLInfo); if (IterHandle != CurInstIterator.getNodePtrUnchecked()) { // If the iterator instruction was recursively deleted, start over at the // start of the block. CurInstIterator = BB->begin(); SunkAddrs.clear(); } } ++NumMemoryInsts; return true; } /// If there are any memory operands, use OptimizeMemoryInst to sink their /// address computing into the block when possible / profitable. 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]; // Compute the constraint code and ConstraintType to use. 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; } /// \brief Check if all the uses of \p Inst are equivalent (or free) zero or /// sign extensions. static bool hasSameExtUse(Instruction *Inst, const TargetLowering &TLI) { assert(!Inst->use_empty() && "Input must have at least one use"); const Instruction *FirstUser = cast(*Inst->user_begin()); bool IsSExt = isa(FirstUser); Type *ExtTy = FirstUser->getType(); for (const User *U : Inst->users()) { const Instruction *UI = cast(U); if ((IsSExt && !isa(UI)) || (!IsSExt && !isa(UI))) return false; Type *CurTy = UI->getType(); // Same input and output types: Same instruction after CSE. if (CurTy == ExtTy) continue; // If IsSExt is true, we are in this situation: // a = Inst // b = sext ty1 a to ty2 // c = sext ty1 a to ty3 // Assuming ty2 is shorter than ty3, this could be turned into: // a = Inst // b = sext ty1 a to ty2 // c = sext ty2 b to ty3 // However, the last sext is not free. if (IsSExt) return false; // This is a ZExt, maybe this is free to extend from one type to another. // In that case, we would not account for a different use. 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; } // All uses are the same or can be derived from one another for free. return true; } /// \brief Try to form ExtLd by promoting \p Exts until they reach a /// load instruction. /// If an ext(load) can be formed, it is returned via \p LI for the load /// and \p Inst for the extension. /// Otherwise LI == nullptr and Inst == nullptr. /// When some promotion happened, \p TPT contains the proper state to /// revert them. /// /// \return true when promoting was necessary to expose the ext(load) /// opportunity, false otherwise. /// /// Example: /// \code /// %ld = load i32* %addr /// %add = add nuw i32 %ld, 4 /// %zext = zext i32 %add to i64 /// \endcode /// => /// \code /// %ld = load i32* %addr /// %zext = zext i32 %ld to i64 /// %add = add nuw i64 %zext, 4 /// \encode /// Thanks to the promotion, we can match zext(load i32*) to i64. bool CodeGenPrepare::extLdPromotion(TypePromotionTransaction &TPT, LoadInst *&LI, Instruction *&Inst, const SmallVectorImpl &Exts, unsigned CreatedInstsCost = 0) { // Iterate over all the extensions to see if one form an ext(load). for (auto I : Exts) { // Check if we directly have ext(load). if ((LI = dyn_cast(I->getOperand(0)))) { Inst = I; // No promotion happened here. return false; } // Check whether or not we want to do any promotion. if (!TLI || !TLI->enableExtLdPromotion() || DisableExtLdPromotion) continue; // Get the action to perform the promotion. TypePromotionHelper::Action TPH = TypePromotionHelper::getAction( I, InsertedInsts, *TLI, PromotedInsts); // Check if we can promote. if (!TPH) continue; // Save the current state. TypePromotionTransaction::ConstRestorationPt LastKnownGood = TPT.getRestorationPoint(); SmallVector NewExts; unsigned NewCreatedInstsCost = 0; unsigned ExtCost = !TLI->isExtFree(I); // Promote. Value *PromotedVal = TPH(I, TPT, PromotedInsts, NewCreatedInstsCost, &NewExts, nullptr, *TLI); assert(PromotedVal && "TypePromotionHelper should have filtered out those cases"); // We would be able to merge only one extension in a load. // Therefore, if we have more than 1 new extension we heuristically // cut this search path, because it means we degrade the code quality. // With exactly 2, the transformation is neutral, because we will merge // one extension but leave one. However, we optimistically keep going, // because the new extension may be removed too. long long TotalCreatedInstsCost = CreatedInstsCost + NewCreatedInstsCost; TotalCreatedInstsCost -= ExtCost; if (!StressExtLdPromotion && (TotalCreatedInstsCost > 1 || !isPromotedInstructionLegal(*TLI, *DL, PromotedVal))) { // The promotion is not profitable, rollback to the previous state. TPT.rollback(LastKnownGood); continue; } // The promotion is profitable. // Check if it exposes an ext(load). (void)extLdPromotion(TPT, LI, Inst, NewExts, TotalCreatedInstsCost); if (LI && (StressExtLdPromotion || NewCreatedInstsCost <= ExtCost || // If we have created a new extension, i.e., now we have two // extensions. We must make sure one of them is merged with // the load, otherwise we may degrade the code quality. (LI->hasOneUse() || hasSameExtUse(LI, *TLI)))) // Promotion happened. return true; // If this does not help to expose an ext(load) then, rollback. TPT.rollback(LastKnownGood); } // None of the extension can form an ext(load). LI = nullptr; Inst = nullptr; return false; } /// Move a zext or sext fed by a load into the same basic block as the load, /// unless conditions are unfavorable. This allows SelectionDAG to fold the /// extend into the load. /// \p I[in/out] the extension may be modified during the process if some /// promotions apply. /// bool CodeGenPrepare::moveExtToFormExtLoad(Instruction *&I) { // Try to promote a chain of computation if it allows to form // an extended load. TypePromotionTransaction TPT; TypePromotionTransaction::ConstRestorationPt LastKnownGood = TPT.getRestorationPoint(); SmallVector Exts; Exts.push_back(I); // Look for a load being extended. 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 they're already in the same block, there's nothing to do. // Make the cheap checks first if we did not promote. // If we promoted, we need to check if it is indeed profitable. if (!HasPromoted && LI->getParent() == I->getParent()) return false; EVT VT = TLI->getValueType(*DL, I->getType()); EVT LoadVT = TLI->getValueType(*DL, LI->getType()); // If the load has other users and the truncate is not free, this probably // isn't worthwhile. if (!LI->hasOneUse() && TLI && (TLI->isTypeLegal(LoadVT) || !TLI->isTypeLegal(VT)) && !TLI->isTruncateFree(I->getType(), LI->getType())) { I = OldExt; TPT.rollback(LastKnownGood); return false; } // Check whether the target supports casts folded into loads. unsigned LType; if (isa(I)) LType = ISD::ZEXTLOAD; else { assert(isa(I) && "Unexpected ext type!"); LType = ISD::SEXTLOAD; } if (TLI && !TLI->isLoadExtLegal(LType, VT, LoadVT)) { I = OldExt; TPT.rollback(LastKnownGood); return false; } // Move the extend into the same block as the load, so that SelectionDAG // can fold it. TPT.commit(); I->removeFromParent(); I->insertAfter(LI); ++NumExtsMoved; return true; } bool CodeGenPrepare::optimizeExtUses(Instruction *I) { BasicBlock *DefBB = I->getParent(); // If the result of a {s|z}ext and its source are both live out, rewrite all // other uses of the source with result of extension. Value *Src = I->getOperand(0); if (Src->hasOneUse()) return false; // Only do this xform if truncating is free. if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType())) return false; // Only safe to perform the optimization if the source is also defined in // this block. if (!isa(Src) || DefBB != cast(Src)->getParent()) return false; bool DefIsLiveOut = false; for (User *U : I->users()) { Instruction *UI = cast(U); // Figure out which BB this ext is used in. BasicBlock *UserBB = UI->getParent(); if (UserBB == DefBB) continue; DefIsLiveOut = true; break; } if (!DefIsLiveOut) return false; // Make sure none of the uses are PHI nodes. for (User *U : Src->users()) { Instruction *UI = cast(U); BasicBlock *UserBB = UI->getParent(); if (UserBB == DefBB) continue; // Be conservative. We don't want this xform to end up introducing // reloads just before load / store instructions. if (isa(UI) || isa(UI) || isa(UI)) return false; } // InsertedTruncs - Only insert one trunc in each block once. DenseMap InsertedTruncs; bool MadeChange = false; for (Use &U : Src->uses()) { Instruction *User = cast(U.getUser()); // Figure out which BB this ext is used in. BasicBlock *UserBB = User->getParent(); if (UserBB == DefBB) continue; // Both src and def are live in this block. Rewrite the use. 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); } // Replace a use of the {s|z}ext source with a use of the result. U = InsertedTrunc; ++NumExtUses; MadeChange = true; } return MadeChange; } // Find loads whose uses only use some of the loaded value's bits. Add an "and" // just after the load if the target can fold this into one extload instruction, // with the hope of eliminating some of the other later "and" instructions using // the loaded value. "and"s that are made trivially redundant by the insertion // of the new "and" are removed by this function, while others (e.g. those whose // path from the load goes through a phi) are left for isel to potentially // remove. // // For example: // // b0: // x = load i32 // ... // b1: // y = and x, 0xff // z = use y // // becomes: // // b0: // x = load i32 // x' = and x, 0xff // ... // b1: // z = use x' // // whereas: // // b0: // x1 = load i32 // ... // b1: // x2 = load i32 // ... // b2: // x = phi x1, x2 // y = and x, 0xff // // becomes (after a call to optimizeLoadExt for each load): // // b0: // x1 = load i32 // x1' = and x1, 0xff // ... // b1: // x2 = load i32 // x2' = and x2, 0xff // ... // b2: // x = phi x1', x2' // y = and x, 0xff // bool CodeGenPrepare::optimizeLoadExt(LoadInst *Load) { if (!Load->isSimple() || !(Load->getType()->isIntegerTy() || Load->getType()->isPointerTy())) return false; // Skip loads we've already transformed or have no reason to transform. if (Load->hasOneUse()) { User *LoadUser = *Load->user_begin(); if (cast(LoadUser)->getParent() == Load->getParent() && !dyn_cast(LoadUser)) return false; } // Look at all uses of Load, looking through phis, to determine how many bits // of the loaded value are needed. SmallVector WorkList; SmallPtrSet Visited; SmallVector AndsToMaybeRemove; for (auto *U : Load->users()) WorkList.push_back(cast(U)); EVT LoadResultVT = TLI->getValueType(*DL, Load->getType()); unsigned BitWidth = LoadResultVT.getSizeInBits(); APInt DemandBits(BitWidth, 0); APInt WidestAndBits(BitWidth, 0); while (!WorkList.empty()) { Instruction *I = WorkList.back(); WorkList.pop_back(); // Break use-def graph loops. if (!Visited.insert(I).second) continue; // For a PHI node, push all of its users. if (auto *Phi = dyn_cast(I)) { for (auto *U : Phi->users()) WorkList.push_back(cast(U)); continue; } switch (I->getOpcode()) { case llvm::Instruction::And: { auto *AndC = dyn_cast(I->getOperand(1)); if (!AndC) return false; APInt AndBits = AndC->getValue(); DemandBits |= AndBits; // Keep track of the widest and mask we see. if (AndBits.ugt(WidestAndBits)) WidestAndBits = AndBits; if (AndBits == WidestAndBits && I->getOperand(0) == Load) AndsToMaybeRemove.push_back(I); break; } case llvm::Instruction::Shl: { auto *ShlC = dyn_cast(I->getOperand(1)); if (!ShlC) return false; uint64_t ShiftAmt = ShlC->getLimitedValue(BitWidth - 1); auto ShlDemandBits = APInt::getAllOnesValue(BitWidth).lshr(ShiftAmt); DemandBits |= ShlDemandBits; break; } case llvm::Instruction::Trunc: { EVT TruncVT = TLI->getValueType(*DL, I->getType()); unsigned TruncBitWidth = TruncVT.getSizeInBits(); auto TruncBits = APInt::getAllOnesValue(TruncBitWidth).zext(BitWidth); DemandBits |= TruncBits; break; } default: return false; } } uint32_t ActiveBits = DemandBits.getActiveBits(); // Avoid hoisting (and (load x) 1) since it is unlikely to be folded by the // target even if isLoadExtLegal says an i1 EXTLOAD is valid. For example, // for the AArch64 target isLoadExtLegal(ZEXTLOAD, i32, i1) returns true, but // (and (load x) 1) is not matched as a single instruction, rather as a LDR // followed by an AND. // TODO: Look into removing this restriction by fixing backends to either // return false for isLoadExtLegal for i1 or have them select this pattern to // a single instruction. // // Also avoid hoisting if we didn't see any ands with the exact DemandBits // mask, since these are the only ands that will be removed by isel. if (ActiveBits <= 1 || !APIntOps::isMask(ActiveBits, DemandBits) || WidestAndBits != DemandBits) return false; LLVMContext &Ctx = Load->getType()->getContext(); Type *TruncTy = Type::getIntNTy(Ctx, ActiveBits); EVT TruncVT = TLI->getValueType(*DL, TruncTy); // Reject cases that won't be matched as extloads. if (!LoadResultVT.bitsGT(TruncVT) || !TruncVT.isRound() || !TLI->isLoadExtLegal(ISD::ZEXTLOAD, LoadResultVT, TruncVT)) return false; IRBuilder<> Builder(Load->getNextNode()); auto *NewAnd = dyn_cast( Builder.CreateAnd(Load, ConstantInt::get(Ctx, DemandBits))); // Replace all uses of load with new and (except for the use of load in the // new and itself). Load->replaceAllUsesWith(NewAnd); NewAnd->setOperand(0, Load); // Remove any and instructions that are now redundant. for (auto *And : AndsToMaybeRemove) // Check that the and mask is the same as the one we decided to put on the // new and. if (cast(And->getOperand(1))->getValue() == DemandBits) { And->replaceAllUsesWith(NewAnd); if (&*CurInstIterator == And) CurInstIterator = std::next(And->getIterator()); And->eraseFromParent(); ++NumAndUses; } ++NumAndsAdded; return true; } /// Check if V (an operand of a select instruction) is an expensive instruction /// that is only used once. static bool sinkSelectOperand(const TargetTransformInfo *TTI, Value *V) { auto *I = dyn_cast(V); // If it's safe to speculatively execute, then it should not have side // effects; therefore, it's safe to sink and possibly *not* execute. return I && I->hasOneUse() && isSafeToSpeculativelyExecute(I) && TTI->getUserCost(I) >= TargetTransformInfo::TCC_Expensive; } /// Returns true if a SelectInst should be turned into an explicit branch. static bool isFormingBranchFromSelectProfitable(const TargetTransformInfo *TTI, SelectInst *SI) { // FIXME: This should use the same heuristics as IfConversion to determine // whether a select is better represented as a branch. This requires that // branch probability metadata is preserved for the select, which is not the // case currently. CmpInst *Cmp = dyn_cast(SI->getCondition()); // If a branch is predictable, an out-of-order CPU can avoid blocking on its // comparison condition. If the compare has more than one use, there's // probably another cmov or setcc around, so it's not worth emitting a branch. if (!Cmp || !Cmp->hasOneUse()) return false; Value *CmpOp0 = Cmp->getOperand(0); Value *CmpOp1 = Cmp->getOperand(1); // Emit "cmov on compare with a memory operand" as a branch to avoid stalls // on a load from memory. But if the load is used more than once, do not // change the select to a branch because the load is probably needed // regardless of whether the branch is taken or not. if ((isa(CmpOp0) && CmpOp0->hasOneUse()) || (isa(CmpOp1) && CmpOp1->hasOneUse())) return true; // If either operand of the select is expensive and only needed on one side // of the select, we should form a branch. if (sinkSelectOperand(TTI, SI->getTrueValue()) || sinkSelectOperand(TTI, SI->getFalseValue())) return true; return false; } /// If we have a SelectInst that will likely profit from branch prediction, /// turn it into a branch. bool CodeGenPrepare::optimizeSelectInst(SelectInst *SI) { bool VectorCond = !SI->getCondition()->getType()->isIntegerTy(1); // Can we convert the 'select' to CF ? 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; // Do we have efficient codegen support for this kind of 'selects' ? if (TLI->isSelectSupported(SelectKind)) { // We have efficient codegen support for the select instruction. // Check if it is profitable to keep this 'select'. if (!TLI->isPredictableSelectExpensive() || !isFormingBranchFromSelectProfitable(TTI, SI)) return false; } ModifiedDT = true; // Transform a sequence like this: // start: // %cmp = cmp uge i32 %a, %b // %sel = select i1 %cmp, i32 %c, i32 %d // // Into: // start: // %cmp = cmp uge i32 %a, %b // br i1 %cmp, label %select.true, label %select.false // select.true: // br label %select.end // select.false: // br label %select.end // select.end: // %sel = phi i32 [ %c, %select.true ], [ %d, %select.false ] // // In addition, we may sink instructions that produce %c or %d from // the entry block into the destination(s) of the new branch. // If the true or false blocks do not contain a sunken instruction, that // block and its branch may be optimized away. In that case, one side of the // first branch will point directly to select.end, and the corresponding PHI // predecessor block will be the start block. // First, we split the block containing the select into 2 blocks. BasicBlock *StartBlock = SI->getParent(); BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(SI)); BasicBlock *EndBlock = StartBlock->splitBasicBlock(SplitPt, "select.end"); // Delete the unconditional branch that was just created by the split. StartBlock->getTerminator()->eraseFromParent(); // These are the new basic blocks for the conditional branch. // At least one will become an actual new basic block. BasicBlock *TrueBlock = nullptr; BasicBlock *FalseBlock = nullptr; // Sink expensive instructions into the conditional blocks to avoid executing // them speculatively. 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(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(SI->getFalseValue()); FalseInst->moveBefore(FalseBranch); } // If there was nothing to sink, then arbitrarily choose the 'false' side // for a new input value to the PHI. 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); } // Insert the real conditional branch based on the original condition. // If we did not create a new block for one of the 'true' or 'false' paths // of the condition, it means that side of the branch goes to the end block // directly and the path originates from the start block from the point of // view of the new PHI. 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); } // The select itself is replaced with a PHI Node. 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(); // Instruct OptimizeBlock to skip to the next block. CurInstIterator = StartBlock->end(); ++NumSelectsExpanded; return true; } static bool isBroadcastShuffle(ShuffleVectorInst *SVI) { SmallVector 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; } /// Some targets have expensive vector shifts if the lanes aren't all the same /// (e.g. x86 only introduced "vpsllvd" and friends with AVX2). In these cases /// it's often worth sinking a shufflevector splat down to its use so that /// codegen can spot all lanes are identical. bool CodeGenPrepare::optimizeShuffleVectorInst(ShuffleVectorInst *SVI) { BasicBlock *DefBB = SVI->getParent(); // Only do this xform if variable vector shifts are particularly expensive. if (!TLI || !TLI->isVectorShiftByScalarCheap(SVI->getType())) return false; // We only expect better codegen by sinking a shuffle if we can recognise a // constant splat. if (!isBroadcastShuffle(SVI)) return false; // InsertedShuffles - Only insert a shuffle in each block once. DenseMap InsertedShuffles; bool MadeChange = false; for (User *U : SVI->users()) { Instruction *UI = cast(U); // Figure out which BB this ext is used in. BasicBlock *UserBB = UI->getParent(); if (UserBB == DefBB) continue; // For now only apply this when the splat is used by a shift instruction. if (!UI->isShift()) continue; // Everything checks out, sink the shuffle if the user's block doesn't // already have a copy. 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 we removed all uses, nuke the shuffle. 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(OldType)->getBitWidth()) return false; // If the register width is greater than the type width, expand the condition // of the switch instruction and each case constant to the width of the // register. By widening the type of the switch condition, subsequent // comparisons (for case comparisons) will not need to be extended to the // preferred register width, so we will potentially eliminate N-1 extends, // where N is the number of cases in the switch. auto *NewType = Type::getIntNTy(Context, RegWidth); // Zero-extend the switch condition and case constants unless the switch // condition is a function argument that is already being sign-extended. // In that case, we can avoid an unnecessary mask/extension by sign-extending // everything instead. Instruction::CastOps ExtType = Instruction::ZExt; if (auto *Arg = dyn_cast(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 { /// \brief Helper class to promote a scalar operation to a vector one. /// This class is used to move downward extractelement transition. /// E.g., /// a = vector_op <2 x i32> /// b = extractelement <2 x i32> a, i32 0 /// c = scalar_op b /// store c /// /// => /// a = vector_op <2 x i32> /// c = vector_op a (equivalent to scalar_op on the related lane) /// * d = extractelement <2 x i32> c, i32 0 /// * store d /// Assuming both extractelement and store can be combine, we get rid of the /// transition. class VectorPromoteHelper { /// DataLayout associated with the current module. const DataLayout &DL; /// Used to perform some checks on the legality of vector operations. const TargetLowering &TLI; /// Used to estimated the cost of the promoted chain. const TargetTransformInfo &TTI; /// The transition being moved downwards. Instruction *Transition; /// The sequence of instructions to be promoted. SmallVector InstsToBePromoted; /// Cost of combining a store and an extract. unsigned StoreExtractCombineCost; /// Instruction that will be combined with the transition. Instruction *CombineInst; /// \brief The instruction that represents the current end of the transition. /// Since we are faking the promotion until we reach the end of the chain /// of computation, we need a way to get the current end of the transition. Instruction *getEndOfTransition() const { if (InstsToBePromoted.empty()) return Transition; return InstsToBePromoted.back(); } /// \brief Return the index of the original value in the transition. /// E.g., for "extractelement <2 x i32> c, i32 1" the original value, /// c, is at index 0. unsigned getTransitionOriginalValueIdx() const { assert(isa(Transition) && "Other kind of transitions are not supported yet"); return 0; } /// \brief Return the index of the index in the transition. /// E.g., for "extractelement <2 x i32> c, i32 0" the index /// is at index 1. unsigned getTransitionIdx() const { assert(isa(Transition) && "Other kind of transitions are not supported yet"); return 1; } /// \brief Get the type of the transition. /// This is the type of the original value. /// E.g., for "extractelement <2 x i32> c, i32 1" the type of the /// transition is <2 x i32>. Type *getTransitionType() const { return Transition->getOperand(getTransitionOriginalValueIdx())->getType(); } /// \brief Promote \p ToBePromoted by moving \p Def downward through. /// I.e., we have the following sequence: /// Def = Transition a to /// b = ToBePromoted Def, ... /// => /// b = ToBePromoted a, ... /// Def = Transition ToBePromoted to void promoteImpl(Instruction *ToBePromoted); /// \brief Check whether or not it is profitable to promote all the /// instructions enqueued to be promoted. bool isProfitableToPromote() { Value *ValIdx = Transition->getOperand(getTransitionOriginalValueIdx()); unsigned Index = isa(ValIdx) ? cast(ValIdx)->getZExtValue() : -1; Type *PromotedType = getTransitionType(); StoreInst *ST = cast(CombineInst); unsigned AS = ST->getPointerAddressSpace(); unsigned Align = ST->getAlignment(); // Check if this store is supported. if (!TLI.allowsMisalignedMemoryAccesses( TLI.getValueType(DL, ST->getValueOperand()->getType()), AS, Align)) { // If this is not supported, there is no way we can combine // the extract with the store. return false; } // The scalar chain of computation has to pay for the transition // scalar to vector. // The vector chain has to account for the combining cost. uint64_t ScalarCost = TTI.getVectorInstrCost(Transition->getOpcode(), PromotedType, Index); uint64_t VectorCost = StoreExtractCombineCost; for (const auto &Inst : InstsToBePromoted) { // Compute the cost. // By construction, all instructions being promoted are arithmetic ones. // Moreover, one argument is a constant that can be viewed as a splat // constant. Value *Arg0 = Inst->getOperand(0); bool IsArg0Constant = isa(Arg0) || isa(Arg0) || isa(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; } /// \brief Generate a constant vector with \p Val with the same /// number of elements as the transition. /// \p UseSplat defines whether or not \p Val should be replicated /// across the whole vector. /// In other words, if UseSplat == true, we generate , /// otherwise we generate a vector with as many undef as possible: /// where \p Val is only /// used at the index of the extract. Value *getConstantVector(Constant *Val, bool UseSplat) const { unsigned ExtractIdx = UINT_MAX; if (!UseSplat) { // If we cannot determine where the constant must be, we have to // use a splat constant. Value *ValExtractIdx = Transition->getOperand(getTransitionIdx()); if (ConstantInt *CstVal = dyn_cast(ValExtractIdx)) ExtractIdx = CstVal->getSExtValue(); else UseSplat = true; } unsigned End = getTransitionType()->getVectorNumElements(); if (UseSplat) return ConstantVector::getSplat(End, Val); SmallVector 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); } /// \brief Check if promoting to a vector type an operand at \p OperandIdx /// in \p Use can trigger undefined behavior. static bool canCauseUndefinedBehavior(const Instruction *Use, unsigned OperandIdx) { // This is not safe to introduce undef when the operand is on // the right hand side of a division-like instruction. 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"); } /// \brief Check if we can promote \p ToBePromoted to \p Type. bool canPromote(const Instruction *ToBePromoted) const { // We could support CastInst too. return isa(ToBePromoted); } /// \brief Check if it is profitable to promote \p ToBePromoted /// by moving downward the transition through. bool shouldPromote(const Instruction *ToBePromoted) const { // Promote only if all the operands can be statically expanded. // Indeed, we do not want to introduce any new kind of transitions. for (const Use &U : ToBePromoted->operands()) { const Value *Val = U.get(); if (Val == getEndOfTransition()) { // If the use is a division and the transition is on the rhs, // we cannot promote the operation, otherwise we may create a // division by zero. if (canCauseUndefinedBehavior(ToBePromoted, U.getOperandNo())) return false; continue; } if (!isa(Val) && !isa(Val) && !isa(Val)) return false; } // Check that the resulting operation is legal. int ISDOpcode = TLI.InstructionOpcodeToISD(ToBePromoted->getOpcode()); if (!ISDOpcode) return false; return StressStoreExtract || TLI.isOperationLegalOrCustom( ISDOpcode, TLI.getValueType(DL, getTransitionType(), true)); } /// \brief Check whether or not \p Use can be combined /// with the transition. /// I.e., is it possible to do Use(Transition) => AnotherUse? bool canCombine(const Instruction *Use) { return isa(Use); } /// \brief Record \p ToBePromoted as part of the chain to be promoted. void enqueueForPromotion(Instruction *ToBePromoted) { InstsToBePromoted.push_back(ToBePromoted); } /// \brief Set the instruction that will be combined with the transition. void recordCombineInstruction(Instruction *ToBeCombined) { assert(canCombine(ToBeCombined) && "Unsupported instruction to combine"); CombineInst = ToBeCombined; } /// \brief Promote all the instructions enqueued for promotion if it is /// is profitable. /// \return True if the promotion happened, false otherwise. bool promote() { // Check if there is something to promote. // Right now, if we do not have anything to combine with, // we assume the promotion is not profitable. if (InstsToBePromoted.empty() || !CombineInst) return false; // Check cost. if (!StressStoreExtract && !isProfitableToPromote()) return false; // Promote. for (auto &ToBePromoted : InstsToBePromoted) promoteImpl(ToBePromoted); InstsToBePromoted.clear(); return true; } }; } // End of anonymous namespace. void VectorPromoteHelper::promoteImpl(Instruction *ToBePromoted) { // At this point, we know that all the operands of ToBePromoted but Def // can be statically promoted. // For Def, we need to use its parameter in ToBePromoted: // b = ToBePromoted ty1 a // Def = Transition ty1 b to ty2 // Move the transition down. // 1. Replace all uses of the promoted operation by the transition. // = ... b => = ... Def. assert(ToBePromoted->getType() == Transition->getType() && "The type of the result of the transition does not match " "the final type"); ToBePromoted->replaceAllUsesWith(Transition); // 2. Update the type of the uses. // b = ToBePromoted ty2 Def => b = ToBePromoted ty1 Def. Type *TransitionTy = getTransitionType(); ToBePromoted->mutateType(TransitionTy); // 3. Update all the operands of the promoted operation with promoted // operands. // b = ToBePromoted ty1 Def => b = ToBePromoted ty1 a. for (Use &U : ToBePromoted->operands()) { Value *Val = U.get(); Value *NewVal = nullptr; if (Val == Transition) NewVal = Transition->getOperand(getTransitionOriginalValueIdx()); else if (isa(Val) || isa(Val) || isa(Val)) { // Use a splat constant if it is not safe to use undef. NewVal = getConstantVector( cast(Val), isa(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); } /// Some targets can do store(extractelement) with one instruction. /// Try to push the extractelement towards the stores when the target /// has this feature and this is profitable. 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; // At this point we know that Inst is a vector to scalar transition. // Try to move it down the def-use chain, until: // - We can combine the transition with its single use // => we got rid of the transition. // - We escape the current basic block // => we would need to check that we are moving it at a cheaper place and // we do not do that for now. BasicBlock *Parent = Inst->getParent(); DEBUG(dbgs() << "Found an interesting transition: " << *Inst << '\n'); VectorPromoteHelper VPH(*DL, *TLI, *TTI, Inst, CombineCost); // If the transition has more than one use, assume this is not going to be // beneficial. while (Inst->hasOneUse()) { Instruction *ToBePromoted = cast(*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) { // Bail out if we inserted the instruction to prevent optimizations from // stepping on each other's toes. if (InsertedInsts.count(I)) return false; if (PHINode *P = dyn_cast(I)) { // It is possible for very late stage optimizations (such as SimplifyCFG) // to introduce PHI nodes too late to be cleaned up. If we detect such a // trivial PHI, go ahead and zap it here. if (Value *V = SimplifyInstruction(P, *DL, TLInfo, nullptr)) { P->replaceAllUsesWith(V); P->eraseFromParent(); ++NumPHIsElim; return true; } return false; } if (CastInst *CI = dyn_cast(I)) { // If the source of the cast is a constant, then this should have // already been constant folded. The only reason NOT to constant fold // it is if something (e.g. LSR) was careful to place the constant // evaluation in a block other than then one that uses it (e.g. to hoist // the address of globals out of a loop). If this is the case, we don't // want to forward-subst the cast. if (isa(CI->getOperand(0))) return false; if (TLI && OptimizeNoopCopyExpression(CI, *TLI, *DL)) return true; if (isa(I) || isa(I)) { /// Sink a zext or sext into its user blocks if the target type doesn't /// fit in one register 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(I)) if (!TLI || !TLI->hasMultipleConditionRegisters()) return OptimizeCmpExpression(CI); if (LoadInst *LI = dyn_cast(I)) { stripInvariantGroupMetadata(*LI); if (TLI) { bool Modified = optimizeLoadExt(LI); unsigned AS = LI->getPointerAddressSpace(); Modified |= optimizeMemoryInst(I, I->getOperand(0), LI->getType(), AS); return Modified; } return false; } if (StoreInst *SI = dyn_cast(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(I); if (BinOp && (BinOp->getOpcode() == Instruction::AShr || BinOp->getOpcode() == Instruction::LShr)) { ConstantInt *CI = dyn_cast(BinOp->getOperand(1)); if (TLI && CI && TLI->hasExtractBitsInsn()) return OptimizeExtractBits(BinOp, CI, *TLI, *DL); return false; } if (GetElementPtrInst *GEPI = dyn_cast(I)) { if (GEPI->hasAllZeroIndices()) { /// The GEP operand must be a pointer, so must its result -> BitCast 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(I)) return optimizeCallInst(CI, ModifiedDT); if (SelectInst *SI = dyn_cast(I)) return optimizeSelectInst(SI); if (ShuffleVectorInst *SVI = dyn_cast(I)) return optimizeShuffleVectorInst(SVI); if (auto *Switch = dyn_cast(I)) return optimizeSwitchInst(Switch); if (isa(I)) return optimizeExtractElementInst(I); return false; } // In this pass we look for GEP and cast instructions that are used // across basic blocks and rewrite them to improve basic-block-at-a-time // selection. 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; } // 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. 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(Insn); // Leave dbg.values that refer to an alloca alone. These // instrinsics describe the address of a variable (= the alloca) // being taken. They should not be moved next to the alloca // (and to the beginning of the scope), but rather stay close to // where said address is used. if (!DVI || (DVI->getValue() && isa(DVI->getValue()))) { PrevNonDbgInst = Insn; continue; } Instruction *VI = dyn_cast_or_null(DVI->getValue()); if (VI && VI != PrevNonDbgInst && !VI->isTerminator()) { // If VI is a phi in a block with an EHPad terminator, we can't insert // after it. if (isa(VI) && VI->getParent()->getTerminator()->isEHPad()) continue; DEBUG(dbgs() << "Moving Debug Value before :\n" << *DVI << ' ' << *VI); DVI->removeFromParent(); if (isa(VI)) DVI->insertBefore(&*VI->getParent()->getFirstInsertionPt()); else DVI->insertAfter(VI); MadeChange = true; ++NumDbgValueMoved; } } } return MadeChange; } // If there is a sequence that branches based on comparing a single bit // against zero that can be combined into a single instruction, and the // target supports folding these into a single instruction, sink the // mask and compare into the branch uses. Do this before OptimizeBlock -> // OptimizeInst -> OptimizeCmpExpression, which perturbs the pattern being // searched for. 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++; // Does this BB end with the following? // %andVal = and %val, #single-bit-set // %icmpVal = icmp %andResult, 0 // br i1 %cmpVal label %dest1, label %dest2" BranchInst *Brcc = dyn_cast(BB->getTerminator()); if (!Brcc || !Brcc->isConditional()) continue; ICmpInst *Cmp = dyn_cast(Brcc->getOperand(0)); if (!Cmp || Cmp->getParent() != BB) continue; ConstantInt *Zero = dyn_cast(Cmp->getOperand(1)); if (!Zero || !Zero->isZero()) continue; Instruction *And = dyn_cast(Cmp->getOperand(0)); if (!And || And->getOpcode() != Instruction::And || And->getParent() != BB) continue; ConstantInt* Mask = dyn_cast(And->getOperand(1)); if (!Mask || !Mask->getUniqueInteger().isPowerOf2()) continue; DEBUG(dbgs() << "found and; icmp ?,0; brcc\n"); DEBUG(BB->dump()); // Push the "and; icmp" for any users that are conditional branches. // Since there can only be one branch use per BB, we don't need to keep // track of which BBs we insert into. for (Value::use_iterator UI = Cmp->use_begin(), E = Cmp->use_end(); UI != E; ) { Use &TheUse = *UI; // Find brcc use. BranchInst *BrccUser = dyn_cast(*UI); ++UI; if (!BrccUser || !BrccUser->isConditional()) continue; BasicBlock *UserBB = BrccUser->getParent(); if (UserBB == BB) continue; DEBUG(dbgs() << "found Brcc use\n"); // Sink the "and; icmp" to use. 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; } /// \brief Retrieve the probabilities of a conditional branch. Returns true on /// success, or returns false if no or invalid metadata was found. 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(ProfileData->getOperand(1)); const auto *CIFalse = mdconst::dyn_extract(ProfileData->getOperand(2)); if (!CITrue || !CIFalse) return false; ProbTrue = CITrue->getValue().getZExtValue(); ProbFalse = CIFalse->getValue().getZExtValue(); return true; } /// \brief Scale down both weights to fit into uint32_t. 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; } /// \brief Some targets prefer to split a conditional branch like: /// \code /// %0 = icmp ne i32 %a, 0 /// %1 = icmp ne i32 %b, 0 /// %or.cond = or i1 %0, %1 /// br i1 %or.cond, label %TrueBB, label %FalseBB /// \endcode /// into multiple branch instructions like: /// \code /// bb1: /// %0 = icmp ne i32 %a, 0 /// br i1 %0, label %TrueBB, label %bb2 /// bb2: /// %1 = icmp ne i32 %b, 0 /// br i1 %1, label %TrueBB, label %FalseBB /// \endcode /// This usually allows instruction selection to do even further optimizations /// and combine the compare with the branch instruction. Currently this is /// applied for targets which have "cheap" jump instructions. /// /// FIXME: Remove the (equivalent?) implementation in SelectionDAG. /// bool CodeGenPrepare::splitBranchCondition(Function &F) { if (!TM || !TM->Options.EnableFastISel || !TLI || TLI->isJumpExpensive()) return false; bool MadeChange = false; for (auto &BB : F) { // Does this BB end with the following? // %cond1 = icmp|fcmp|binary instruction ... // %cond2 = icmp|fcmp|binary instruction ... // %cond.or = or|and i1 %cond1, cond2 // br i1 %cond.or label %dest1, label %dest2" BinaryOperator *LogicOp; BasicBlock *TBB, *FBB; if (!match(BB.getTerminator(), m_Br(m_OneUse(m_BinOp(LogicOp)), TBB, FBB))) continue; auto *Br1 = cast(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()); // Create a new BB. auto *InsertBefore = std::next(Function::iterator(BB)) .getNodePtrUnchecked(); auto TmpBB = BasicBlock::Create(BB.getContext(), BB.getName() + ".cond.split", BB.getParent(), InsertBefore); // Update original basic block by using the first condition directly by the // branch instruction and removing the no longer needed and/or instruction. Br1->setCondition(Cond1); LogicOp->eraseFromParent(); // Depending on the conditon we have to either replace the true or the false // successor of the original branch instruction. if (Opc == Instruction::And) Br1->setSuccessor(0, TmpBB); else Br1->setSuccessor(1, TmpBB); // Fill in the new basic block. auto *Br2 = IRBuilder<>(TmpBB).CreateCondBr(Cond2, TBB, FBB); if (auto *I = dyn_cast(Cond2)) { I->removeFromParent(); I->insertBefore(Br2); } // Update PHI nodes in both successors. The original BB needs to be // replaced in one succesor's PHI nodes, because the branch comes now from // the newly generated BB (NewBB). In the other successor we need to add one // incoming edge to the PHI nodes, because both branch instructions target // now the same successor. Depending on the original branch condition // (and/or) we have to swap the successors (TrueDest, FalseDest), so that // we perfrom the correct update for the PHI nodes. // This doesn't change the successor order of the just created branch // instruction (or any other instruction). if (Opc == Instruction::Or) std::swap(TBB, FBB); // Replace the old BB with the new BB. for (auto &I : *TBB) { PHINode *PN = dyn_cast(&I); if (!PN) break; int i; while ((i = PN->getBasicBlockIndex(&BB)) >= 0) PN->setIncomingBlock(i, TmpBB); } // Add another incoming edge form the new BB. for (auto &I : *FBB) { PHINode *PN = dyn_cast(&I); if (!PN) break; auto *Val = PN->getIncomingValueForBlock(&BB); PN->addIncoming(Val, TmpBB); } // Update the branch weights (from SelectionDAGBuilder:: // FindMergedConditions). if (Opc == Instruction::Or) { // Codegen X | Y as: // BB1: // jmp_if_X TBB // jmp TmpBB // TmpBB: // jmp_if_Y TBB // jmp FBB // // We have flexibility in setting Prob for BB1 and Prob for NewBB. // The requirement is that // TrueProb for BB1 + (FalseProb for BB1 * TrueProb for TmpBB) // = TrueProb for orignal BB. // Assuming the orignal weights are A and B, one choice is to set BB1's // weights to A and A+2B, and set TmpBB's weights to A and 2B. This choice // assumes that // TrueProb for BB1 == FalseProb for BB1 * TrueProb for TmpBB. // Another choice is to assume TrueProb for BB1 equals to TrueProb for // TmpBB, but the math is more complicated. 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 { // Codegen X & Y as: // BB1: // jmp_if_X TmpBB // jmp FBB // TmpBB: // jmp_if_Y TBB // jmp FBB // // This requires creation of TmpBB after CurBB. // We have flexibility in setting Prob for BB1 and Prob for TmpBB. // The requirement is that // FalseProb for BB1 + (TrueProb for BB1 * FalseProb for TmpBB) // = FalseProb for orignal BB. // Assuming the orignal weights are A and B, one choice is to set BB1's // weights to 2A+B and B, and set TmpBB's weights to 2A and B. This choice // assumes that // FalseProb for BB1 == TrueProb for BB1 * FalseProb for TmpBB. 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)); } } // Note: No point in getting fancy here, since the DT info is never // available to CodeGenPrepare. 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()); } Index: projects/clang380-import/contrib/llvm/lib/IR/Globals.cpp =================================================================== --- projects/clang380-import/contrib/llvm/lib/IR/Globals.cpp (revision 294176) +++ projects/clang380-import/contrib/llvm/lib/IR/Globals.cpp (revision 294177) @@ -1,285 +1,327 @@ //===-- Globals.cpp - Implement the GlobalValue & GlobalVariable class ----===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file implements the GlobalValue & GlobalVariable classes for the IR // library. // //===----------------------------------------------------------------------===// -#include "llvm/IR/GlobalValue.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/Triple.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DerivedTypes.h" #include "llvm/IR/GlobalAlias.h" +#include "llvm/IR/GlobalValue.h" #include "llvm/IR/GlobalVariable.h" #include "llvm/IR/Module.h" #include "llvm/IR/Operator.h" #include "llvm/Support/ErrorHandling.h" using namespace llvm; //===----------------------------------------------------------------------===// // GlobalValue Class //===----------------------------------------------------------------------===// bool GlobalValue::isMaterializable() const { if (const Function *F = dyn_cast(this)) return F->isMaterializable(); return false; } std::error_code GlobalValue::materialize() { return getParent()->materialize(this); } /// Override destroyConstantImpl to make sure it doesn't get called on /// GlobalValue's because they shouldn't be treated like other constants. void GlobalValue::destroyConstantImpl() { llvm_unreachable("You can't GV->destroyConstantImpl()!"); } Value *GlobalValue::handleOperandChangeImpl(Value *From, Value *To, Use *U) { llvm_unreachable("Unsupported class for handleOperandChange()!"); } /// copyAttributesFrom - copy all additional attributes (those not needed to /// create a GlobalValue) from the GlobalValue Src to this one. void GlobalValue::copyAttributesFrom(const GlobalValue *Src) { setVisibility(Src->getVisibility()); setUnnamedAddr(Src->hasUnnamedAddr()); setDLLStorageClass(Src->getDLLStorageClass()); } unsigned GlobalValue::getAlignment() const { if (auto *GA = dyn_cast(this)) { // In general we cannot compute this at the IR level, but we try. if (const GlobalObject *GO = GA->getBaseObject()) return GO->getAlignment(); // FIXME: we should also be able to handle: // Alias = Global + Offset // Alias = Absolute return 0; } return cast(this)->getAlignment(); } void GlobalObject::setAlignment(unsigned Align) { assert((Align & (Align-1)) == 0 && "Alignment is not a power of 2!"); assert(Align <= MaximumAlignment && "Alignment is greater than MaximumAlignment!"); unsigned AlignmentData = Log2_32(Align) + 1; unsigned OldData = getGlobalValueSubClassData(); setGlobalValueSubClassData((OldData & ~AlignmentMask) | AlignmentData); assert(getAlignment() == Align && "Alignment representation error!"); } unsigned GlobalObject::getGlobalObjectSubClassData() const { unsigned ValueData = getGlobalValueSubClassData(); return ValueData >> AlignmentBits; } void GlobalObject::setGlobalObjectSubClassData(unsigned Val) { unsigned OldData = getGlobalValueSubClassData(); setGlobalValueSubClassData((OldData & AlignmentMask) | (Val << AlignmentBits)); assert(getGlobalObjectSubClassData() == Val && "representation error"); } void GlobalObject::copyAttributesFrom(const GlobalValue *Src) { GlobalValue::copyAttributesFrom(Src); if (const auto *GV = dyn_cast(Src)) { setAlignment(GV->getAlignment()); setSection(GV->getSection()); } } const char *GlobalValue::getSection() const { if (auto *GA = dyn_cast(this)) { // In general we cannot compute this at the IR level, but we try. if (const GlobalObject *GO = GA->getBaseObject()) return GO->getSection(); return ""; } return cast(this)->getSection(); } Comdat *GlobalValue::getComdat() { if (auto *GA = dyn_cast(this)) { // In general we cannot compute this at the IR level, but we try. if (const GlobalObject *GO = GA->getBaseObject()) return const_cast(GO)->getComdat(); return nullptr; } return cast(this)->getComdat(); } void GlobalObject::setSection(StringRef S) { Section = S; } bool GlobalValue::isDeclaration() const { // Globals are definitions if they have an initializer. if (const GlobalVariable *GV = dyn_cast(this)) return GV->getNumOperands() == 0; // Functions are definitions if they have a body. if (const Function *F = dyn_cast(this)) return F->empty() && !F->isMaterializable(); // Aliases are always definitions. assert(isa(this)); return false; +} + +bool GlobalValue::canIncreaseAlignment() const { + // Firstly, can only increase the alignment of a global if it + // is a strong definition. + if (!isStrongDefinitionForLinker()) + return false; + + // It also has to either not have a section defined, or, not have + // alignment specified. (If it is assigned a section, the global + // could be densely packed with other objects in the section, and + // increasing the alignment could cause padding issues.) + if (hasSection() && getAlignment() > 0) + return false; + + // On ELF platforms, we're further restricted in that we can't + // increase the alignment of any variable which might be emitted + // into a shared library, and which is exported. If the main + // executable accesses a variable found in a shared-lib, the main + // exe actually allocates memory for and exports the symbol ITSELF, + // overriding the symbol found in the library. That is, at link + // time, the observed alignment of the variable is copied into the + // executable binary. (A COPY relocation is also generated, to copy + // the initial data from the shadowed variable in the shared-lib + // into the location in the main binary, before running code.) + // + // And thus, even though you might think you are defining the + // global, and allocating the memory for the global in your object + // file, and thus should be able to set the alignment arbitrarily, + // that's not actually true. Doing so can cause an ABI breakage; an + // executable might have already been built with the previous + // alignment of the variable, and then assuming an increased + // alignment will be incorrect. + + // Conservatively assume ELF if there's no parent pointer. + bool isELF = + (!Parent || Triple(Parent->getTargetTriple()).isOSBinFormatELF()); + if (isELF && hasDefaultVisibility() && !hasLocalLinkage()) + return false; + + return true; } //===----------------------------------------------------------------------===// // GlobalVariable Implementation //===----------------------------------------------------------------------===// GlobalVariable::GlobalVariable(Type *Ty, bool constant, LinkageTypes Link, Constant *InitVal, const Twine &Name, ThreadLocalMode TLMode, unsigned AddressSpace, bool isExternallyInitialized) : GlobalObject(Ty, Value::GlobalVariableVal, OperandTraits::op_begin(this), InitVal != nullptr, Link, Name, AddressSpace), isConstantGlobal(constant), isExternallyInitializedConstant(isExternallyInitialized) { setThreadLocalMode(TLMode); if (InitVal) { assert(InitVal->getType() == Ty && "Initializer should be the same type as the GlobalVariable!"); Op<0>() = InitVal; } } GlobalVariable::GlobalVariable(Module &M, Type *Ty, bool constant, LinkageTypes Link, Constant *InitVal, const Twine &Name, GlobalVariable *Before, ThreadLocalMode TLMode, unsigned AddressSpace, bool isExternallyInitialized) : GlobalObject(Ty, Value::GlobalVariableVal, OperandTraits::op_begin(this), InitVal != nullptr, Link, Name, AddressSpace), isConstantGlobal(constant), isExternallyInitializedConstant(isExternallyInitialized) { setThreadLocalMode(TLMode); if (InitVal) { assert(InitVal->getType() == Ty && "Initializer should be the same type as the GlobalVariable!"); Op<0>() = InitVal; } if (Before) Before->getParent()->getGlobalList().insert(Before->getIterator(), this); else M.getGlobalList().push_back(this); } void GlobalVariable::setParent(Module *parent) { Parent = parent; } void GlobalVariable::removeFromParent() { getParent()->getGlobalList().remove(getIterator()); } void GlobalVariable::eraseFromParent() { getParent()->getGlobalList().erase(getIterator()); } void GlobalVariable::setInitializer(Constant *InitVal) { if (!InitVal) { if (hasInitializer()) { // Note, the num operands is used to compute the offset of the operand, so // the order here matters. Clearing the operand then clearing the num // operands ensures we have the correct offset to the operand. Op<0>().set(nullptr); setGlobalVariableNumOperands(0); } } else { assert(InitVal->getType() == getType()->getElementType() && "Initializer type must match GlobalVariable type"); // Note, the num operands is used to compute the offset of the operand, so // the order here matters. We need to set num operands to 1 first so that // we get the correct offset to the first operand when we set it. if (!hasInitializer()) setGlobalVariableNumOperands(1); Op<0>().set(InitVal); } } /// Copy all additional attributes (those not needed to create a GlobalVariable) /// from the GlobalVariable Src to this one. void GlobalVariable::copyAttributesFrom(const GlobalValue *Src) { GlobalObject::copyAttributesFrom(Src); if (const GlobalVariable *SrcVar = dyn_cast(Src)) { setThreadLocalMode(SrcVar->getThreadLocalMode()); setExternallyInitialized(SrcVar->isExternallyInitialized()); } } //===----------------------------------------------------------------------===// // GlobalAlias Implementation //===----------------------------------------------------------------------===// GlobalAlias::GlobalAlias(Type *Ty, unsigned AddressSpace, LinkageTypes Link, const Twine &Name, Constant *Aliasee, Module *ParentModule) : GlobalValue(Ty, Value::GlobalAliasVal, &Op<0>(), 1, Link, Name, AddressSpace) { Op<0>() = Aliasee; if (ParentModule) ParentModule->getAliasList().push_back(this); } GlobalAlias *GlobalAlias::create(Type *Ty, unsigned AddressSpace, LinkageTypes Link, const Twine &Name, Constant *Aliasee, Module *ParentModule) { return new GlobalAlias(Ty, AddressSpace, Link, Name, Aliasee, ParentModule); } GlobalAlias *GlobalAlias::create(Type *Ty, unsigned AddressSpace, LinkageTypes Linkage, const Twine &Name, Module *Parent) { return create(Ty, AddressSpace, Linkage, Name, nullptr, Parent); } GlobalAlias *GlobalAlias::create(Type *Ty, unsigned AddressSpace, LinkageTypes Linkage, const Twine &Name, GlobalValue *Aliasee) { return create(Ty, AddressSpace, Linkage, Name, Aliasee, Aliasee->getParent()); } GlobalAlias *GlobalAlias::create(LinkageTypes Link, const Twine &Name, GlobalValue *Aliasee) { PointerType *PTy = Aliasee->getType(); return create(PTy->getElementType(), PTy->getAddressSpace(), Link, Name, Aliasee); } GlobalAlias *GlobalAlias::create(const Twine &Name, GlobalValue *Aliasee) { return create(Aliasee->getLinkage(), Name, Aliasee); } void GlobalAlias::setParent(Module *parent) { Parent = parent; } void GlobalAlias::removeFromParent() { getParent()->getAliasList().remove(getIterator()); } void GlobalAlias::eraseFromParent() { getParent()->getAliasList().erase(getIterator()); } void GlobalAlias::setAliasee(Constant *Aliasee) { assert((!Aliasee || Aliasee->getType() == getType()) && "Alias and aliasee types should match!"); setOperand(0, Aliasee); } Index: projects/clang380-import/contrib/llvm/lib/Transforms/Utils/Local.cpp =================================================================== --- projects/clang380-import/contrib/llvm/lib/Transforms/Utils/Local.cpp (revision 294176) +++ projects/clang380-import/contrib/llvm/lib/Transforms/Utils/Local.cpp (revision 294177) @@ -1,1587 +1,1594 @@ //===-- Local.cpp - Functions to perform local transformations ------------===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This family of functions perform various local transformations to the // program. // //===----------------------------------------------------------------------===// #include "llvm/Transforms/Utils/Local.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/Hashing.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/EHPersonalities.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/LazyValueInfo.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DIBuilder.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DebugInfo.h" #include "llvm/IR/DerivedTypes.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/GetElementPtrTypeIterator.h" #include "llvm/IR/GlobalAlias.h" #include "llvm/IR/GlobalVariable.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Intrinsics.h" #include "llvm/IR/MDBuilder.h" #include "llvm/IR/Metadata.h" #include "llvm/IR/Operator.h" #include "llvm/IR/ValueHandle.h" #include "llvm/Support/Debug.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; #define DEBUG_TYPE "local" STATISTIC(NumRemoved, "Number of unreachable basic blocks removed"); //===----------------------------------------------------------------------===// // Local constant propagation. // /// ConstantFoldTerminator - If a terminator instruction is predicated on a /// constant value, convert it into an unconditional branch to the constant /// destination. This is a nontrivial operation because the successors of this /// basic block must have their PHI nodes updated. /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch /// conditions and indirectbr addresses this might make dead if /// DeleteDeadConditions is true. bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, const TargetLibraryInfo *TLI) { TerminatorInst *T = BB->getTerminator(); IRBuilder<> Builder(T); // Branch - See if we are conditional jumping on constant if (BranchInst *BI = dyn_cast(T)) { if (BI->isUnconditional()) return false; // Can't optimize uncond branch BasicBlock *Dest1 = BI->getSuccessor(0); BasicBlock *Dest2 = BI->getSuccessor(1); if (ConstantInt *Cond = dyn_cast(BI->getCondition())) { // Are we branching on constant? // YES. Change to unconditional branch... BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; //cerr << "Function: " << T->getParent()->getParent() // << "\nRemoving branch from " << T->getParent() // << "\n\nTo: " << OldDest << endl; // Let the basic block know that we are letting go of it. Based on this, // it will adjust it's PHI nodes. OldDest->removePredecessor(BB); // Replace the conditional branch with an unconditional one. Builder.CreateBr(Destination); BI->eraseFromParent(); return true; } if (Dest2 == Dest1) { // Conditional branch to same location? // This branch matches something like this: // br bool %cond, label %Dest, label %Dest // and changes it into: br label %Dest // Let the basic block know that we are letting go of one copy of it. assert(BI->getParent() && "Terminator not inserted in block!"); Dest1->removePredecessor(BI->getParent()); // Replace the conditional branch with an unconditional one. Builder.CreateBr(Dest1); Value *Cond = BI->getCondition(); BI->eraseFromParent(); if (DeleteDeadConditions) RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); return true; } return false; } if (SwitchInst *SI = dyn_cast(T)) { // If we are switching on a constant, we can convert the switch to an // unconditional branch. ConstantInt *CI = dyn_cast(SI->getCondition()); BasicBlock *DefaultDest = SI->getDefaultDest(); BasicBlock *TheOnlyDest = DefaultDest; // If the default is unreachable, ignore it when searching for TheOnlyDest. if (isa(DefaultDest->getFirstNonPHIOrDbg()) && SI->getNumCases() > 0) { TheOnlyDest = SI->case_begin().getCaseSuccessor(); } // Figure out which case it goes to. for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i) { // Found case matching a constant operand? if (i.getCaseValue() == CI) { TheOnlyDest = i.getCaseSuccessor(); break; } // Check to see if this branch is going to the same place as the default // dest. If so, eliminate it as an explicit compare. if (i.getCaseSuccessor() == DefaultDest) { MDNode *MD = SI->getMetadata(LLVMContext::MD_prof); unsigned NCases = SI->getNumCases(); // Fold the case metadata into the default if there will be any branches // left, unless the metadata doesn't match the switch. if (NCases > 1 && MD && MD->getNumOperands() == 2 + NCases) { // Collect branch weights into a vector. SmallVector Weights; for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e; ++MD_i) { ConstantInt *CI = mdconst::dyn_extract(MD->getOperand(MD_i)); assert(CI); Weights.push_back(CI->getValue().getZExtValue()); } // Merge weight of this case to the default weight. unsigned idx = i.getCaseIndex(); Weights[0] += Weights[idx+1]; // Remove weight for this case. std::swap(Weights[idx+1], Weights.back()); Weights.pop_back(); SI->setMetadata(LLVMContext::MD_prof, MDBuilder(BB->getContext()). createBranchWeights(Weights)); } // Remove this entry. DefaultDest->removePredecessor(SI->getParent()); SI->removeCase(i); --i; --e; continue; } // Otherwise, check to see if the switch only branches to one destination. // We do this by reseting "TheOnlyDest" to null when we find two non-equal // destinations. if (i.getCaseSuccessor() != TheOnlyDest) TheOnlyDest = nullptr; } if (CI && !TheOnlyDest) { // Branching on a constant, but not any of the cases, go to the default // successor. TheOnlyDest = SI->getDefaultDest(); } // If we found a single destination that we can fold the switch into, do so // now. if (TheOnlyDest) { // Insert the new branch. Builder.CreateBr(TheOnlyDest); BasicBlock *BB = SI->getParent(); // Remove entries from PHI nodes which we no longer branch to... for (BasicBlock *Succ : SI->successors()) { // Found case matching a constant operand? if (Succ == TheOnlyDest) TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest else Succ->removePredecessor(BB); } // Delete the old switch. Value *Cond = SI->getCondition(); SI->eraseFromParent(); if (DeleteDeadConditions) RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); return true; } if (SI->getNumCases() == 1) { // Otherwise, we can fold this switch into a conditional branch // instruction if it has only one non-default destination. SwitchInst::CaseIt FirstCase = SI->case_begin(); Value *Cond = Builder.CreateICmpEQ(SI->getCondition(), FirstCase.getCaseValue(), "cond"); // Insert the new branch. BranchInst *NewBr = Builder.CreateCondBr(Cond, FirstCase.getCaseSuccessor(), SI->getDefaultDest()); MDNode *MD = SI->getMetadata(LLVMContext::MD_prof); if (MD && MD->getNumOperands() == 3) { ConstantInt *SICase = mdconst::dyn_extract(MD->getOperand(2)); ConstantInt *SIDef = mdconst::dyn_extract(MD->getOperand(1)); assert(SICase && SIDef); // The TrueWeight should be the weight for the single case of SI. NewBr->setMetadata(LLVMContext::MD_prof, MDBuilder(BB->getContext()). createBranchWeights(SICase->getValue().getZExtValue(), SIDef->getValue().getZExtValue())); } // Update make.implicit metadata to the newly-created conditional branch. MDNode *MakeImplicitMD = SI->getMetadata(LLVMContext::MD_make_implicit); if (MakeImplicitMD) NewBr->setMetadata(LLVMContext::MD_make_implicit, MakeImplicitMD); // Delete the old switch. SI->eraseFromParent(); return true; } return false; } if (IndirectBrInst *IBI = dyn_cast(T)) { // indirectbr blockaddress(@F, @BB) -> br label @BB if (BlockAddress *BA = dyn_cast(IBI->getAddress()->stripPointerCasts())) { BasicBlock *TheOnlyDest = BA->getBasicBlock(); // Insert the new branch. Builder.CreateBr(TheOnlyDest); for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { if (IBI->getDestination(i) == TheOnlyDest) TheOnlyDest = nullptr; else IBI->getDestination(i)->removePredecessor(IBI->getParent()); } Value *Address = IBI->getAddress(); IBI->eraseFromParent(); if (DeleteDeadConditions) RecursivelyDeleteTriviallyDeadInstructions(Address, TLI); // If we didn't find our destination in the IBI successor list, then we // have undefined behavior. Replace the unconditional branch with an // 'unreachable' instruction. if (TheOnlyDest) { BB->getTerminator()->eraseFromParent(); new UnreachableInst(BB->getContext(), BB); } return true; } } return false; } //===----------------------------------------------------------------------===// // Local dead code elimination. // /// isInstructionTriviallyDead - Return true if the result produced by the /// instruction is not used, and the instruction has no side effects. /// bool llvm::isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI) { if (!I->use_empty() || isa(I)) return false; // We don't want the landingpad-like instructions removed by anything this // general. if (I->isEHPad()) return false; // We don't want debug info removed by anything this general, unless // debug info is empty. if (DbgDeclareInst *DDI = dyn_cast(I)) { if (DDI->getAddress()) return false; return true; } if (DbgValueInst *DVI = dyn_cast(I)) { if (DVI->getValue()) return false; return true; } if (!I->mayHaveSideEffects()) return true; // Special case intrinsics that "may have side effects" but can be deleted // when dead. if (IntrinsicInst *II = dyn_cast(I)) { // Safe to delete llvm.stacksave if dead. if (II->getIntrinsicID() == Intrinsic::stacksave) return true; // Lifetime intrinsics are dead when their right-hand is undef. if (II->getIntrinsicID() == Intrinsic::lifetime_start || II->getIntrinsicID() == Intrinsic::lifetime_end) return isa(II->getArgOperand(1)); // Assumptions are dead if their condition is trivially true. if (II->getIntrinsicID() == Intrinsic::assume) { if (ConstantInt *Cond = dyn_cast(II->getArgOperand(0))) return !Cond->isZero(); return false; } } if (isAllocLikeFn(I, TLI)) return true; if (CallInst *CI = isFreeCall(I, TLI)) if (Constant *C = dyn_cast(CI->getArgOperand(0))) return C->isNullValue() || isa(C); return false; } /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a /// trivially dead instruction, delete it. If that makes any of its operands /// trivially dead, delete them too, recursively. Return true if any /// instructions were deleted. bool llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI) { Instruction *I = dyn_cast(V); if (!I || !I->use_empty() || !isInstructionTriviallyDead(I, TLI)) return false; SmallVector DeadInsts; DeadInsts.push_back(I); do { I = DeadInsts.pop_back_val(); // Null out all of the instruction's operands to see if any operand becomes // dead as we go. for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { Value *OpV = I->getOperand(i); I->setOperand(i, nullptr); if (!OpV->use_empty()) continue; // If the operand is an instruction that became dead as we nulled out the // operand, and if it is 'trivially' dead, delete it in a future loop // iteration. if (Instruction *OpI = dyn_cast(OpV)) if (isInstructionTriviallyDead(OpI, TLI)) DeadInsts.push_back(OpI); } I->eraseFromParent(); } while (!DeadInsts.empty()); return true; } /// areAllUsesEqual - Check whether the uses of a value are all the same. /// This is similar to Instruction::hasOneUse() except this will also return /// true when there are no uses or multiple uses that all refer to the same /// value. static bool areAllUsesEqual(Instruction *I) { Value::user_iterator UI = I->user_begin(); Value::user_iterator UE = I->user_end(); if (UI == UE) return true; User *TheUse = *UI; for (++UI; UI != UE; ++UI) { if (*UI != TheUse) return false; } return true; } /// RecursivelyDeleteDeadPHINode - If the specified value is an effectively /// dead PHI node, due to being a def-use chain of single-use nodes that /// either forms a cycle or is terminated by a trivially dead instruction, /// delete it. If that makes any of its operands trivially dead, delete them /// too, recursively. Return true if a change was made. bool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI) { SmallPtrSet Visited; for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects(); I = cast(*I->user_begin())) { if (I->use_empty()) return RecursivelyDeleteTriviallyDeadInstructions(I, TLI); // If we find an instruction more than once, we're on a cycle that // won't prove fruitful. if (!Visited.insert(I).second) { // Break the cycle and delete the instruction and its operands. I->replaceAllUsesWith(UndefValue::get(I->getType())); (void)RecursivelyDeleteTriviallyDeadInstructions(I, TLI); return true; } } return false; } static bool simplifyAndDCEInstruction(Instruction *I, SmallSetVector &WorkList, const DataLayout &DL, const TargetLibraryInfo *TLI) { if (isInstructionTriviallyDead(I, TLI)) { // Null out all of the instruction's operands to see if any operand becomes // dead as we go. for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { Value *OpV = I->getOperand(i); I->setOperand(i, nullptr); if (!OpV->use_empty() || I == OpV) continue; // If the operand is an instruction that became dead as we nulled out the // operand, and if it is 'trivially' dead, delete it in a future loop // iteration. if (Instruction *OpI = dyn_cast(OpV)) if (isInstructionTriviallyDead(OpI, TLI)) WorkList.insert(OpI); } I->eraseFromParent(); return true; } if (Value *SimpleV = SimplifyInstruction(I, DL)) { // Add the users to the worklist. CAREFUL: an instruction can use itself, // in the case of a phi node. for (User *U : I->users()) if (U != I) WorkList.insert(cast(U)); // Replace the instruction with its simplified value. I->replaceAllUsesWith(SimpleV); I->eraseFromParent(); return true; } return false; } /// SimplifyInstructionsInBlock - Scan the specified basic block and try to /// simplify any instructions in it and recursively delete dead instructions. /// /// This returns true if it changed the code, note that it can delete /// instructions in other blocks as well in this block. bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI) { bool MadeChange = false; const DataLayout &DL = BB->getModule()->getDataLayout(); #ifndef NDEBUG // In debug builds, ensure that the terminator of the block is never replaced // or deleted by these simplifications. The idea of simplification is that it // cannot introduce new instructions, and there is no way to replace the // terminator of a block without introducing a new instruction. AssertingVH TerminatorVH(&BB->back()); #endif SmallSetVector WorkList; // Iterate over the original function, only adding insts to the worklist // if they actually need to be revisited. This avoids having to pre-init // the worklist with the entire function's worth of instructions. for (BasicBlock::iterator BI = BB->begin(), E = std::prev(BB->end()); BI != E;) { assert(!BI->isTerminator()); Instruction *I = &*BI; ++BI; // We're visiting this instruction now, so make sure it's not in the // worklist from an earlier visit. if (!WorkList.count(I)) MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI); } while (!WorkList.empty()) { Instruction *I = WorkList.pop_back_val(); MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI); } return MadeChange; } //===----------------------------------------------------------------------===// // Control Flow Graph Restructuring. // /// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this /// method is called when we're about to delete Pred as a predecessor of BB. If /// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred. /// /// Unlike the removePredecessor method, this attempts to simplify uses of PHI /// nodes that collapse into identity values. For example, if we have: /// x = phi(1, 0, 0, 0) /// y = and x, z /// /// .. and delete the predecessor corresponding to the '1', this will attempt to /// recursively fold the and to 0. void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred) { // This only adjusts blocks with PHI nodes. if (!isa(BB->begin())) return; // Remove the entries for Pred from the PHI nodes in BB, but do not simplify // them down. This will leave us with single entry phi nodes and other phis // that can be removed. BB->removePredecessor(Pred, true); WeakVH PhiIt = &BB->front(); while (PHINode *PN = dyn_cast(PhiIt)) { PhiIt = &*++BasicBlock::iterator(cast(PhiIt)); Value *OldPhiIt = PhiIt; if (!recursivelySimplifyInstruction(PN)) continue; // If recursive simplification ended up deleting the next PHI node we would // iterate to, then our iterator is invalid, restart scanning from the top // of the block. if (PhiIt != OldPhiIt) PhiIt = &BB->front(); } } /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its /// predecessor is known to have one successor (DestBB!). Eliminate the edge /// between them, moving the instructions in the predecessor into DestBB and /// deleting the predecessor block. /// void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT) { // If BB has single-entry PHI nodes, fold them. while (PHINode *PN = dyn_cast(DestBB->begin())) { Value *NewVal = PN->getIncomingValue(0); // Replace self referencing PHI with undef, it must be dead. if (NewVal == PN) NewVal = UndefValue::get(PN->getType()); PN->replaceAllUsesWith(NewVal); PN->eraseFromParent(); } BasicBlock *PredBB = DestBB->getSinglePredecessor(); assert(PredBB && "Block doesn't have a single predecessor!"); // Zap anything that took the address of DestBB. Not doing this will give the // address an invalid value. if (DestBB->hasAddressTaken()) { BlockAddress *BA = BlockAddress::get(DestBB); Constant *Replacement = ConstantInt::get(llvm::Type::getInt32Ty(BA->getContext()), 1); BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement, BA->getType())); BA->destroyConstant(); } // Anything that branched to PredBB now branches to DestBB. PredBB->replaceAllUsesWith(DestBB); // Splice all the instructions from PredBB to DestBB. PredBB->getTerminator()->eraseFromParent(); DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList()); // If the PredBB is the entry block of the function, move DestBB up to // become the entry block after we erase PredBB. if (PredBB == &DestBB->getParent()->getEntryBlock()) DestBB->moveAfter(PredBB); if (DT) { BasicBlock *PredBBIDom = DT->getNode(PredBB)->getIDom()->getBlock(); DT->changeImmediateDominator(DestBB, PredBBIDom); DT->eraseNode(PredBB); } // Nuke BB. PredBB->eraseFromParent(); } /// CanMergeValues - Return true if we can choose one of these values to use /// in place of the other. Note that we will always choose the non-undef /// value to keep. static bool CanMergeValues(Value *First, Value *Second) { return First == Second || isa(First) || isa(Second); } /// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an /// almost-empty BB ending in an unconditional branch to Succ, into Succ. /// /// Assumption: Succ is the single successor for BB. /// static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into " << Succ->getName() << "\n"); // Shortcut, if there is only a single predecessor it must be BB and merging // is always safe if (Succ->getSinglePredecessor()) return true; // Make a list of the predecessors of BB SmallPtrSet BBPreds(pred_begin(BB), pred_end(BB)); // Look at all the phi nodes in Succ, to see if they present a conflict when // merging these blocks for (BasicBlock::iterator I = Succ->begin(); isa(I); ++I) { PHINode *PN = cast(I); // If the incoming value from BB is again a PHINode in // BB which has the same incoming value for *PI as PN does, we can // merge the phi nodes and then the blocks can still be merged PHINode *BBPN = dyn_cast(PN->getIncomingValueForBlock(BB)); if (BBPN && BBPN->getParent() == BB) { for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { BasicBlock *IBB = PN->getIncomingBlock(PI); if (BBPreds.count(IBB) && !CanMergeValues(BBPN->getIncomingValueForBlock(IBB), PN->getIncomingValue(PI))) { DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " << Succ->getName() << " is conflicting with " << BBPN->getName() << " with regard to common predecessor " << IBB->getName() << "\n"); return false; } } } else { Value* Val = PN->getIncomingValueForBlock(BB); for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { // See if the incoming value for the common predecessor is equal to the // one for BB, in which case this phi node will not prevent the merging // of the block. BasicBlock *IBB = PN->getIncomingBlock(PI); if (BBPreds.count(IBB) && !CanMergeValues(Val, PN->getIncomingValue(PI))) { DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " << Succ->getName() << " is conflicting with regard to common " << "predecessor " << IBB->getName() << "\n"); return false; } } } } return true; } typedef SmallVector PredBlockVector; typedef DenseMap IncomingValueMap; /// \brief Determines the value to use as the phi node input for a block. /// /// Select between \p OldVal any value that we know flows from \p BB /// to a particular phi on the basis of which one (if either) is not /// undef. Update IncomingValues based on the selected value. /// /// \param OldVal The value we are considering selecting. /// \param BB The block that the value flows in from. /// \param IncomingValues A map from block-to-value for other phi inputs /// that we have examined. /// /// \returns the selected value. static Value *selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB, IncomingValueMap &IncomingValues) { if (!isa(OldVal)) { assert((!IncomingValues.count(BB) || IncomingValues.find(BB)->second == OldVal) && "Expected OldVal to match incoming value from BB!"); IncomingValues.insert(std::make_pair(BB, OldVal)); return OldVal; } IncomingValueMap::const_iterator It = IncomingValues.find(BB); if (It != IncomingValues.end()) return It->second; return OldVal; } /// \brief Create a map from block to value for the operands of a /// given phi. /// /// Create a map from block to value for each non-undef value flowing /// into \p PN. /// /// \param PN The phi we are collecting the map for. /// \param IncomingValues [out] The map from block to value for this phi. static void gatherIncomingValuesToPhi(PHINode *PN, IncomingValueMap &IncomingValues) { for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { BasicBlock *BB = PN->getIncomingBlock(i); Value *V = PN->getIncomingValue(i); if (!isa(V)) IncomingValues.insert(std::make_pair(BB, V)); } } /// \brief Replace the incoming undef values to a phi with the values /// from a block-to-value map. /// /// \param PN The phi we are replacing the undefs in. /// \param IncomingValues A map from block to value. static void replaceUndefValuesInPhi(PHINode *PN, const IncomingValueMap &IncomingValues) { for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { Value *V = PN->getIncomingValue(i); if (!isa(V)) continue; BasicBlock *BB = PN->getIncomingBlock(i); IncomingValueMap::const_iterator It = IncomingValues.find(BB); if (It == IncomingValues.end()) continue; PN->setIncomingValue(i, It->second); } } /// \brief Replace a value flowing from a block to a phi with /// potentially multiple instances of that value flowing from the /// block's predecessors to the phi. /// /// \param BB The block with the value flowing into the phi. /// \param BBPreds The predecessors of BB. /// \param PN The phi that we are updating. static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB, const PredBlockVector &BBPreds, PHINode *PN) { Value *OldVal = PN->removeIncomingValue(BB, false); assert(OldVal && "No entry in PHI for Pred BB!"); IncomingValueMap IncomingValues; // We are merging two blocks - BB, and the block containing PN - and // as a result we need to redirect edges from the predecessors of BB // to go to the block containing PN, and update PN // accordingly. Since we allow merging blocks in the case where the // predecessor and successor blocks both share some predecessors, // and where some of those common predecessors might have undef // values flowing into PN, we want to rewrite those values to be // consistent with the non-undef values. gatherIncomingValuesToPhi(PN, IncomingValues); // If this incoming value is one of the PHI nodes in BB, the new entries // in the PHI node are the entries from the old PHI. if (isa(OldVal) && cast(OldVal)->getParent() == BB) { PHINode *OldValPN = cast(OldVal); for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) { // Note that, since we are merging phi nodes and BB and Succ might // have common predecessors, we could end up with a phi node with // identical incoming branches. This will be cleaned up later (and // will trigger asserts if we try to clean it up now, without also // simplifying the corresponding conditional branch). BasicBlock *PredBB = OldValPN->getIncomingBlock(i); Value *PredVal = OldValPN->getIncomingValue(i); Value *Selected = selectIncomingValueForBlock(PredVal, PredBB, IncomingValues); // And add a new incoming value for this predecessor for the // newly retargeted branch. PN->addIncoming(Selected, PredBB); } } else { for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) { // Update existing incoming values in PN for this // predecessor of BB. BasicBlock *PredBB = BBPreds[i]; Value *Selected = selectIncomingValueForBlock(OldVal, PredBB, IncomingValues); // And add a new incoming value for this predecessor for the // newly retargeted branch. PN->addIncoming(Selected, PredBB); } } replaceUndefValuesInPhi(PN, IncomingValues); } /// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an /// unconditional branch, and contains no instructions other than PHI nodes, /// potential side-effect free intrinsics and the branch. If possible, /// eliminate BB by rewriting all the predecessors to branch to the successor /// block and return true. If we can't transform, return false. bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { assert(BB != &BB->getParent()->getEntryBlock() && "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!"); // We can't eliminate infinite loops. BasicBlock *Succ = cast(BB->getTerminator())->getSuccessor(0); if (BB == Succ) return false; // Check to see if merging these blocks would cause conflicts for any of the // phi nodes in BB or Succ. If not, we can safely merge. if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; // Check for cases where Succ has multiple predecessors and a PHI node in BB // has uses which will not disappear when the PHI nodes are merged. It is // possible to handle such cases, but difficult: it requires checking whether // BB dominates Succ, which is non-trivial to calculate in the case where // Succ has multiple predecessors. Also, it requires checking whether // constructing the necessary self-referential PHI node doesn't introduce any // conflicts; this isn't too difficult, but the previous code for doing this // was incorrect. // // Note that if this check finds a live use, BB dominates Succ, so BB is // something like a loop pre-header (or rarely, a part of an irreducible CFG); // folding the branch isn't profitable in that case anyway. if (!Succ->getSinglePredecessor()) { BasicBlock::iterator BBI = BB->begin(); while (isa(*BBI)) { for (Use &U : BBI->uses()) { if (PHINode* PN = dyn_cast(U.getUser())) { if (PN->getIncomingBlock(U) != BB) return false; } else { return false; } } ++BBI; } } DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB); if (isa(Succ->begin())) { // If there is more than one pred of succ, and there are PHI nodes in // the successor, then we need to add incoming edges for the PHI nodes // const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB)); // Loop over all of the PHI nodes in the successor of BB. for (BasicBlock::iterator I = Succ->begin(); isa(I); ++I) { PHINode *PN = cast(I); redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN); } } if (Succ->getSinglePredecessor()) { // BB is the only predecessor of Succ, so Succ will end up with exactly // the same predecessors BB had. // Copy over any phi, debug or lifetime instruction. BB->getTerminator()->eraseFromParent(); Succ->getInstList().splice(Succ->getFirstNonPHI()->getIterator(), BB->getInstList()); } else { while (PHINode *PN = dyn_cast(&BB->front())) { // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. assert(PN->use_empty() && "There shouldn't be any uses here!"); PN->eraseFromParent(); } } // Everything that jumped to BB now goes to Succ. BB->replaceAllUsesWith(Succ); if (!Succ->hasName()) Succ->takeName(BB); BB->eraseFromParent(); // Delete the old basic block. return true; } /// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI /// nodes in this block. This doesn't try to be clever about PHI nodes /// which differ only in the order of the incoming values, but instcombine /// orders them so it usually won't matter. /// bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { // This implementation doesn't currently consider undef operands // specially. Theoretically, two phis which are identical except for // one having an undef where the other doesn't could be collapsed. struct PHIDenseMapInfo { static PHINode *getEmptyKey() { return DenseMapInfo::getEmptyKey(); } static PHINode *getTombstoneKey() { return DenseMapInfo::getTombstoneKey(); } static unsigned getHashValue(PHINode *PN) { // Compute a hash value on the operands. Instcombine will likely have // sorted them, which helps expose duplicates, but we have to check all // the operands to be safe in case instcombine hasn't run. return static_cast(hash_combine( hash_combine_range(PN->value_op_begin(), PN->value_op_end()), hash_combine_range(PN->block_begin(), PN->block_end()))); } static bool isEqual(PHINode *LHS, PHINode *RHS) { if (LHS == getEmptyKey() || LHS == getTombstoneKey() || RHS == getEmptyKey() || RHS == getTombstoneKey()) return LHS == RHS; return LHS->isIdenticalTo(RHS); } }; // Set of unique PHINodes. DenseSet PHISet; // Examine each PHI. bool Changed = false; for (auto I = BB->begin(); PHINode *PN = dyn_cast(I++);) { auto Inserted = PHISet.insert(PN); if (!Inserted.second) { // A duplicate. Replace this PHI with its duplicate. PN->replaceAllUsesWith(*Inserted.first); PN->eraseFromParent(); Changed = true; // The RAUW can change PHIs that we already visited. Start over from the // beginning. PHISet.clear(); I = BB->begin(); } } return Changed; } /// enforceKnownAlignment - If the specified pointer points to an object that /// we control, modify the object's alignment to PrefAlign. This isn't /// often possible though. If alignment is important, a more reliable approach /// is to simply align all global variables and allocation instructions to /// their preferred alignment from the beginning. /// static unsigned enforceKnownAlignment(Value *V, unsigned Align, unsigned PrefAlign, const DataLayout &DL) { + assert(PrefAlign > Align); + V = V->stripPointerCasts(); if (AllocaInst *AI = dyn_cast(V)) { + // TODO: ideally, computeKnownBits ought to have used + // AllocaInst::getAlignment() in its computation already, making + // the below max redundant. But, as it turns out, + // stripPointerCasts recurses through infinite layers of bitcasts, + // while computeKnownBits is not allowed to traverse more than 6 + // levels. + Align = std::max(AI->getAlignment(), Align); + if (PrefAlign <= Align) + return Align; + // If the preferred alignment is greater than the natural stack alignment // then don't round up. This avoids dynamic stack realignment. if (DL.exceedsNaturalStackAlignment(PrefAlign)) return Align; - // If there is a requested alignment and if this is an alloca, round up. - if (AI->getAlignment() >= PrefAlign) - return AI->getAlignment(); AI->setAlignment(PrefAlign); return PrefAlign; } if (auto *GO = dyn_cast(V)) { + // TODO: as above, this shouldn't be necessary. + Align = std::max(GO->getAlignment(), Align); + if (PrefAlign <= Align) + return Align; + // If there is a large requested alignment and we can, bump up the alignment // of the global. If the memory we set aside for the global may not be the // memory used by the final program then it is impossible for us to reliably // enforce the preferred alignment. - if (!GO->isStrongDefinitionForLinker()) + if (!GO->canIncreaseAlignment()) return Align; - if (GO->getAlignment() >= PrefAlign) - return GO->getAlignment(); - // We can only increase the alignment of the global if it has no alignment - // specified or if it is not assigned a section. If it is assigned a - // section, the global could be densely packed with other objects in the - // section, increasing the alignment could cause padding issues. - if (!GO->hasSection() || GO->getAlignment() == 0) - GO->setAlignment(PrefAlign); - return GO->getAlignment(); + GO->setAlignment(PrefAlign); + return PrefAlign; } return Align; } /// getOrEnforceKnownAlignment - If the specified pointer has an alignment that /// we can determine, return it, otherwise return 0. If PrefAlign is specified, /// and it is more than the alignment of the ultimate object, see if we can /// increase the alignment of the ultimate object, making this check succeed. unsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, const DataLayout &DL, const Instruction *CxtI, AssumptionCache *AC, const DominatorTree *DT) { assert(V->getType()->isPointerTy() && "getOrEnforceKnownAlignment expects a pointer!"); unsigned BitWidth = DL.getPointerTypeSizeInBits(V->getType()); APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); computeKnownBits(V, KnownZero, KnownOne, DL, 0, AC, CxtI, DT); unsigned TrailZ = KnownZero.countTrailingOnes(); // Avoid trouble with ridiculously large TrailZ values, such as // those computed from a null pointer. TrailZ = std::min(TrailZ, unsigned(sizeof(unsigned) * CHAR_BIT - 1)); unsigned Align = 1u << std::min(BitWidth - 1, TrailZ); // LLVM doesn't support alignments larger than this currently. Align = std::min(Align, +Value::MaximumAlignment); if (PrefAlign > Align) Align = enforceKnownAlignment(V, Align, PrefAlign, DL); // We don't need to make any adjustment. return Align; } ///===---------------------------------------------------------------------===// /// Dbg Intrinsic utilities /// /// See if there is a dbg.value intrinsic for DIVar before I. static bool LdStHasDebugValue(const DILocalVariable *DIVar, Instruction *I) { // Since we can't guarantee that the original dbg.declare instrinsic // is removed by LowerDbgDeclare(), we need to make sure that we are // not inserting the same dbg.value intrinsic over and over. llvm::BasicBlock::InstListType::iterator PrevI(I); if (PrevI != I->getParent()->getInstList().begin()) { --PrevI; if (DbgValueInst *DVI = dyn_cast(PrevI)) if (DVI->getValue() == I->getOperand(0) && DVI->getOffset() == 0 && DVI->getVariable() == DIVar) return true; } return false; } /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value /// that has an associated llvm.dbg.decl intrinsic. bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, StoreInst *SI, DIBuilder &Builder) { auto *DIVar = DDI->getVariable(); auto *DIExpr = DDI->getExpression(); assert(DIVar && "Missing variable"); if (LdStHasDebugValue(DIVar, SI)) return true; // If an argument is zero extended then use argument directly. The ZExt // may be zapped by an optimization pass in future. Argument *ExtendedArg = nullptr; if (ZExtInst *ZExt = dyn_cast(SI->getOperand(0))) ExtendedArg = dyn_cast(ZExt->getOperand(0)); if (SExtInst *SExt = dyn_cast(SI->getOperand(0))) ExtendedArg = dyn_cast(SExt->getOperand(0)); if (ExtendedArg) { // We're now only describing a subset of the variable. The piece we're // describing will always be smaller than the variable size, because // VariableSize == Size of Alloca described by DDI. Since SI stores // to the alloca described by DDI, if it's first operand is an extend, // we're guaranteed that before extension, the value was narrower than // the size of the alloca, hence the size of the described variable. SmallVector NewDIExpr; unsigned PieceOffset = 0; // If this already is a bit piece, we drop the bit piece from the expression // and record the offset. if (DIExpr->isBitPiece()) { NewDIExpr.append(DIExpr->elements_begin(), DIExpr->elements_end()-3); PieceOffset = DIExpr->getBitPieceOffset(); } else { NewDIExpr.append(DIExpr->elements_begin(), DIExpr->elements_end()); } NewDIExpr.push_back(dwarf::DW_OP_bit_piece); NewDIExpr.push_back(PieceOffset); //Offset const DataLayout &DL = DDI->getModule()->getDataLayout(); NewDIExpr.push_back(DL.getTypeSizeInBits(ExtendedArg->getType())); // Size Builder.insertDbgValueIntrinsic(ExtendedArg, 0, DIVar, Builder.createExpression(NewDIExpr), DDI->getDebugLoc(), SI); } else Builder.insertDbgValueIntrinsic(SI->getOperand(0), 0, DIVar, DIExpr, DDI->getDebugLoc(), SI); return true; } /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value /// that has an associated llvm.dbg.decl intrinsic. bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, LoadInst *LI, DIBuilder &Builder) { auto *DIVar = DDI->getVariable(); auto *DIExpr = DDI->getExpression(); assert(DIVar && "Missing variable"); if (LdStHasDebugValue(DIVar, LI)) return true; // We are now tracking the loaded value instead of the address. In the // future if multi-location support is added to the IR, it might be // preferable to keep tracking both the loaded value and the original // address in case the alloca can not be elided. Instruction *DbgValue = Builder.insertDbgValueIntrinsic( LI, 0, DIVar, DIExpr, DDI->getDebugLoc(), (Instruction *)nullptr); DbgValue->insertAfter(LI); return true; } /// Determine whether this alloca is either a VLA or an array. static bool isArray(AllocaInst *AI) { return AI->isArrayAllocation() || AI->getType()->getElementType()->isArrayTy(); } /// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set /// of llvm.dbg.value intrinsics. bool llvm::LowerDbgDeclare(Function &F) { DIBuilder DIB(*F.getParent(), /*AllowUnresolved*/ false); SmallVector Dbgs; for (auto &FI : F) for (Instruction &BI : FI) if (auto DDI = dyn_cast(&BI)) Dbgs.push_back(DDI); if (Dbgs.empty()) return false; for (auto &I : Dbgs) { DbgDeclareInst *DDI = I; AllocaInst *AI = dyn_cast_or_null(DDI->getAddress()); // If this is an alloca for a scalar variable, insert a dbg.value // at each load and store to the alloca and erase the dbg.declare. // The dbg.values allow tracking a variable even if it is not // stored on the stack, while the dbg.declare can only describe // the stack slot (and at a lexical-scope granularity). Later // passes will attempt to elide the stack slot. if (AI && !isArray(AI)) { for (User *U : AI->users()) if (StoreInst *SI = dyn_cast(U)) ConvertDebugDeclareToDebugValue(DDI, SI, DIB); else if (LoadInst *LI = dyn_cast(U)) ConvertDebugDeclareToDebugValue(DDI, LI, DIB); else if (CallInst *CI = dyn_cast(U)) { // This is a call by-value or some other instruction that // takes a pointer to the variable. Insert a *value* // intrinsic that describes the alloca. SmallVector NewDIExpr; auto *DIExpr = DDI->getExpression(); NewDIExpr.push_back(dwarf::DW_OP_deref); NewDIExpr.append(DIExpr->elements_begin(), DIExpr->elements_end()); DIB.insertDbgValueIntrinsic(AI, 0, DDI->getVariable(), DIB.createExpression(NewDIExpr), DDI->getDebugLoc(), CI); } DDI->eraseFromParent(); } } return true; } /// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic describing the /// alloca 'V', if any. DbgDeclareInst *llvm::FindAllocaDbgDeclare(Value *V) { if (auto *L = LocalAsMetadata::getIfExists(V)) if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L)) for (User *U : MDV->users()) if (DbgDeclareInst *DDI = dyn_cast(U)) return DDI; return nullptr; } bool llvm::replaceDbgDeclare(Value *Address, Value *NewAddress, Instruction *InsertBefore, DIBuilder &Builder, bool Deref, int Offset) { DbgDeclareInst *DDI = FindAllocaDbgDeclare(Address); if (!DDI) return false; DebugLoc Loc = DDI->getDebugLoc(); auto *DIVar = DDI->getVariable(); auto *DIExpr = DDI->getExpression(); assert(DIVar && "Missing variable"); if (Deref || Offset) { // Create a copy of the original DIDescriptor for user variable, prepending // "deref" operation to a list of address elements, as new llvm.dbg.declare // will take a value storing address of the memory for variable, not // alloca itself. SmallVector NewDIExpr; if (Deref) NewDIExpr.push_back(dwarf::DW_OP_deref); if (Offset > 0) { NewDIExpr.push_back(dwarf::DW_OP_plus); NewDIExpr.push_back(Offset); } else if (Offset < 0) { NewDIExpr.push_back(dwarf::DW_OP_minus); NewDIExpr.push_back(-Offset); } if (DIExpr) NewDIExpr.append(DIExpr->elements_begin(), DIExpr->elements_end()); DIExpr = Builder.createExpression(NewDIExpr); } // Insert llvm.dbg.declare immediately after the original alloca, and remove // old llvm.dbg.declare. Builder.insertDeclare(NewAddress, DIVar, DIExpr, Loc, InsertBefore); DDI->eraseFromParent(); return true; } bool llvm::replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, DIBuilder &Builder, bool Deref, int Offset) { return replaceDbgDeclare(AI, NewAllocaAddress, AI->getNextNode(), Builder, Deref, Offset); } void llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap) { BasicBlock *BB = I->getParent(); // Loop over all of the successors, removing BB's entry from any PHI // nodes. for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) (*SI)->removePredecessor(BB); // Insert a call to llvm.trap right before this. This turns the undefined // behavior into a hard fail instead of falling through into random code. if (UseLLVMTrap) { Function *TrapFn = Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap); CallInst *CallTrap = CallInst::Create(TrapFn, "", I); CallTrap->setDebugLoc(I->getDebugLoc()); } new UnreachableInst(I->getContext(), I); // All instructions after this are dead. BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end(); while (BBI != BBE) { if (!BBI->use_empty()) BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); BB->getInstList().erase(BBI++); } } /// changeToCall - Convert the specified invoke into a normal call. static void changeToCall(InvokeInst *II) { SmallVector Args(II->arg_begin(), II->arg_end()); SmallVector OpBundles; II->getOperandBundlesAsDefs(OpBundles); CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, OpBundles, "", II); NewCall->takeName(II); NewCall->setCallingConv(II->getCallingConv()); NewCall->setAttributes(II->getAttributes()); NewCall->setDebugLoc(II->getDebugLoc()); II->replaceAllUsesWith(NewCall); // Follow the call by a branch to the normal destination. BranchInst::Create(II->getNormalDest(), II); // Update PHI nodes in the unwind destination II->getUnwindDest()->removePredecessor(II->getParent()); II->eraseFromParent(); } static bool markAliveBlocks(Function &F, SmallPtrSetImpl &Reachable) { SmallVector Worklist; BasicBlock *BB = &F.front(); Worklist.push_back(BB); Reachable.insert(BB); bool Changed = false; do { BB = Worklist.pop_back_val(); // Do a quick scan of the basic block, turning any obviously unreachable // instructions into LLVM unreachable insts. The instruction combining pass // canonicalizes unreachable insts into stores to null or undef. for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;++BBI){ // Assumptions that are known to be false are equivalent to unreachable. // Also, if the condition is undefined, then we make the choice most // beneficial to the optimizer, and choose that to also be unreachable. if (IntrinsicInst *II = dyn_cast(BBI)) if (II->getIntrinsicID() == Intrinsic::assume) { bool MakeUnreachable = false; if (isa(II->getArgOperand(0))) MakeUnreachable = true; else if (ConstantInt *Cond = dyn_cast(II->getArgOperand(0))) MakeUnreachable = Cond->isZero(); if (MakeUnreachable) { // Don't insert a call to llvm.trap right before the unreachable. changeToUnreachable(&*BBI, false); Changed = true; break; } } if (CallInst *CI = dyn_cast(BBI)) { if (CI->doesNotReturn()) { // If we found a call to a no-return function, insert an unreachable // instruction after it. Make sure there isn't *already* one there // though. ++BBI; if (!isa(BBI)) { // Don't insert a call to llvm.trap right before the unreachable. changeToUnreachable(&*BBI, false); Changed = true; } break; } } // Store to undef and store to null are undefined and used to signal that // they should be changed to unreachable by passes that can't modify the // CFG. if (StoreInst *SI = dyn_cast(BBI)) { // Don't touch volatile stores. if (SI->isVolatile()) continue; Value *Ptr = SI->getOperand(1); if (isa(Ptr) || (isa(Ptr) && SI->getPointerAddressSpace() == 0)) { changeToUnreachable(SI, true); Changed = true; break; } } } TerminatorInst *Terminator = BB->getTerminator(); if (auto *II = dyn_cast(Terminator)) { // Turn invokes that call 'nounwind' functions into ordinary calls. Value *Callee = II->getCalledValue(); if (isa(Callee) || isa(Callee)) { changeToUnreachable(II, true); Changed = true; } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) { if (II->use_empty() && II->onlyReadsMemory()) { // jump to the normal destination branch. BranchInst::Create(II->getNormalDest(), II); II->getUnwindDest()->removePredecessor(II->getParent()); II->eraseFromParent(); } else changeToCall(II); Changed = true; } } else if (auto *CatchSwitch = dyn_cast(Terminator)) { // Remove catchpads which cannot be reached. struct CatchPadDenseMapInfo { static CatchPadInst *getEmptyKey() { return DenseMapInfo::getEmptyKey(); } static CatchPadInst *getTombstoneKey() { return DenseMapInfo::getTombstoneKey(); } static unsigned getHashValue(CatchPadInst *CatchPad) { return static_cast(hash_combine_range( CatchPad->value_op_begin(), CatchPad->value_op_end())); } static bool isEqual(CatchPadInst *LHS, CatchPadInst *RHS) { if (LHS == getEmptyKey() || LHS == getTombstoneKey() || RHS == getEmptyKey() || RHS == getTombstoneKey()) return LHS == RHS; return LHS->isIdenticalTo(RHS); } }; // Set of unique CatchPads. SmallDenseMap> HandlerSet; detail::DenseSetEmpty Empty; for (CatchSwitchInst::handler_iterator I = CatchSwitch->handler_begin(), E = CatchSwitch->handler_end(); I != E; ++I) { BasicBlock *HandlerBB = *I; auto *CatchPad = cast(HandlerBB->getFirstNonPHI()); if (!HandlerSet.insert({CatchPad, Empty}).second) { CatchSwitch->removeHandler(I); --I; --E; Changed = true; } } } Changed |= ConstantFoldTerminator(BB, true); for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) if (Reachable.insert(*SI).second) Worklist.push_back(*SI); } while (!Worklist.empty()); return Changed; } void llvm::removeUnwindEdge(BasicBlock *BB) { TerminatorInst *TI = BB->getTerminator(); if (auto *II = dyn_cast(TI)) { changeToCall(II); return; } TerminatorInst *NewTI; BasicBlock *UnwindDest; if (auto *CRI = dyn_cast(TI)) { NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI); UnwindDest = CRI->getUnwindDest(); } else if (auto *CatchSwitch = dyn_cast(TI)) { auto *NewCatchSwitch = CatchSwitchInst::Create( CatchSwitch->getParentPad(), nullptr, CatchSwitch->getNumHandlers(), CatchSwitch->getName(), CatchSwitch); for (BasicBlock *PadBB : CatchSwitch->handlers()) NewCatchSwitch->addHandler(PadBB); NewTI = NewCatchSwitch; UnwindDest = CatchSwitch->getUnwindDest(); } else { llvm_unreachable("Could not find unwind successor"); } NewTI->takeName(TI); NewTI->setDebugLoc(TI->getDebugLoc()); UnwindDest->removePredecessor(BB); TI->replaceAllUsesWith(NewTI); TI->eraseFromParent(); } /// removeUnreachableBlocksFromFn - Remove blocks that are not reachable, even /// if they are in a dead cycle. Return true if a change was made, false /// otherwise. bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI) { SmallPtrSet Reachable; bool Changed = markAliveBlocks(F, Reachable); // If there are unreachable blocks in the CFG... if (Reachable.size() == F.size()) return Changed; assert(Reachable.size() < F.size()); NumRemoved += F.size()-Reachable.size(); // Loop over all of the basic blocks that are not reachable, dropping all of // their internal references... for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) { if (Reachable.count(&*BB)) continue; for (succ_iterator SI = succ_begin(&*BB), SE = succ_end(&*BB); SI != SE; ++SI) if (Reachable.count(*SI)) (*SI)->removePredecessor(&*BB); if (LVI) LVI->eraseBlock(&*BB); BB->dropAllReferences(); } for (Function::iterator I = ++F.begin(); I != F.end();) if (!Reachable.count(&*I)) I = F.getBasicBlockList().erase(I); else ++I; return true; } void llvm::combineMetadata(Instruction *K, const Instruction *J, ArrayRef KnownIDs) { SmallVector, 4> Metadata; K->dropUnknownNonDebugMetadata(KnownIDs); K->getAllMetadataOtherThanDebugLoc(Metadata); for (unsigned i = 0, n = Metadata.size(); i < n; ++i) { unsigned Kind = Metadata[i].first; MDNode *JMD = J->getMetadata(Kind); MDNode *KMD = Metadata[i].second; switch (Kind) { default: K->setMetadata(Kind, nullptr); // Remove unknown metadata break; case LLVMContext::MD_dbg: llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg"); case LLVMContext::MD_tbaa: K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD)); break; case LLVMContext::MD_alias_scope: K->setMetadata(Kind, MDNode::getMostGenericAliasScope(JMD, KMD)); break; case LLVMContext::MD_noalias: K->setMetadata(Kind, MDNode::intersect(JMD, KMD)); break; case LLVMContext::MD_range: K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD)); break; case LLVMContext::MD_fpmath: K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD)); break; case LLVMContext::MD_invariant_load: // Only set the !invariant.load if it is present in both instructions. K->setMetadata(Kind, JMD); break; case LLVMContext::MD_nonnull: // Only set the !nonnull if it is present in both instructions. K->setMetadata(Kind, JMD); break; case LLVMContext::MD_invariant_group: // Preserve !invariant.group in K. break; case LLVMContext::MD_align: K->setMetadata(Kind, MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD)); break; case LLVMContext::MD_dereferenceable: case LLVMContext::MD_dereferenceable_or_null: K->setMetadata(Kind, MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD)); break; } } // Set !invariant.group from J if J has it. If both instructions have it // then we will just pick it from J - even when they are different. // Also make sure that K is load or store - f.e. combining bitcast with load // could produce bitcast with invariant.group metadata, which is invalid. // FIXME: we should try to preserve both invariant.group md if they are // different, but right now instruction can only have one invariant.group. if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group)) if (isa(K) || isa(K)) K->setMetadata(LLVMContext::MD_invariant_group, JMD); } unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Root) { assert(From->getType() == To->getType()); unsigned Count = 0; for (Value::use_iterator UI = From->use_begin(), UE = From->use_end(); UI != UE; ) { Use &U = *UI++; if (DT.dominates(Root, U)) { U.set(To); DEBUG(dbgs() << "Replace dominated use of '" << From->getName() << "' as " << *To << " in " << *U << "\n"); ++Count; } } return Count; } unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlock *BB) { assert(From->getType() == To->getType()); unsigned Count = 0; for (Value::use_iterator UI = From->use_begin(), UE = From->use_end(); UI != UE;) { Use &U = *UI++; auto *I = cast(U.getUser()); if (DT.dominates(BB, I->getParent())) { U.set(To); DEBUG(dbgs() << "Replace dominated use of '" << From->getName() << "' as " << *To << " in " << *U << "\n"); ++Count; } } return Count; } bool llvm::callsGCLeafFunction(ImmutableCallSite CS) { if (isa(CS.getInstruction())) // Most LLVM intrinsics are things which can never take a safepoint. // As a result, we don't need to have the stack parsable at the // callsite. This is a highly useful optimization since intrinsic // calls are fairly prevalent, particularly in debug builds. return true; // Check if the function is specifically marked as a gc leaf function. if (CS.hasFnAttr("gc-leaf-function")) return true; if (const Function *F = CS.getCalledFunction()) return F->hasFnAttribute("gc-leaf-function"); return false; }