diff --git a/llvm/include/llvm/Transforms/Utils/Local.h b/llvm/include/llvm/Transforms/Utils/Local.h index c5a447a5d5fa..f09ebe5e2471 100644 --- a/llvm/include/llvm/Transforms/Utils/Local.h +++ b/llvm/include/llvm/Transforms/Utils/Local.h @@ -1,454 +1,465 @@ //===- Local.h - Functions to perform local transformations -----*- C++ -*-===// // // 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. // //===----------------------------------------------------------------------===// #ifndef LLVM_TRANSFORMS_UTILS_LOCAL_H #define LLVM_TRANSFORMS_UTILS_LOCAL_H #include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/TinyPtrVector.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/Utils/Local.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/Constant.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/GetElementPtrTypeIterator.h" #include "llvm/IR/Operator.h" #include "llvm/IR/Type.h" #include "llvm/IR/User.h" #include "llvm/IR/Value.h" #include "llvm/Support/Casting.h" #include #include namespace llvm { class AllocaInst; class AssumptionCache; class BasicBlock; class BranchInst; class CallInst; class DbgInfoIntrinsic; class DbgValueInst; class DIBuilder; class Function; class Instruction; class LazyValueInfo; class LoadInst; class MDNode; class PHINode; class StoreInst; class TargetLibraryInfo; class TargetTransformInfo; /// A set of parameters used to control the transforms in the SimplifyCFG pass. /// Options may change depending on the position in the optimization pipeline. /// For example, canonical form that includes switches and branches may later be /// replaced by lookup tables and selects. struct SimplifyCFGOptions { int BonusInstThreshold; bool ForwardSwitchCondToPhi; bool ConvertSwitchToLookupTable; bool NeedCanonicalLoop; bool SinkCommonInsts; AssumptionCache *AC; SimplifyCFGOptions(unsigned BonusThreshold = 1, bool ForwardSwitchCond = false, bool SwitchToLookup = false, bool CanonicalLoops = true, bool SinkCommon = false, AssumptionCache *AssumpCache = nullptr) : BonusInstThreshold(BonusThreshold), ForwardSwitchCondToPhi(ForwardSwitchCond), ConvertSwitchToLookupTable(SwitchToLookup), NeedCanonicalLoop(CanonicalLoops), SinkCommonInsts(SinkCommon), AC(AssumpCache) {} // Support 'builder' pattern to set members by name at construction time. SimplifyCFGOptions &bonusInstThreshold(int I) { BonusInstThreshold = I; return *this; } SimplifyCFGOptions &forwardSwitchCondToPhi(bool B) { ForwardSwitchCondToPhi = B; return *this; } SimplifyCFGOptions &convertSwitchToLookupTable(bool B) { ConvertSwitchToLookupTable = B; return *this; } SimplifyCFGOptions &needCanonicalLoops(bool B) { NeedCanonicalLoop = B; return *this; } SimplifyCFGOptions &sinkCommonInsts(bool B) { SinkCommonInsts = B; return *this; } SimplifyCFGOptions &setAssumptionCache(AssumptionCache *Cache) { AC = Cache; return *this; } }; //===----------------------------------------------------------------------===// // Local constant propagation. // /// 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 ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false, const TargetLibraryInfo *TLI = nullptr, DeferredDominance *DDT = nullptr); //===----------------------------------------------------------------------===// // Local dead code elimination. // /// Return true if the result produced by the instruction is not used, and the /// instruction has no side effects. bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI = nullptr); /// Return true if the result produced by the instruction would have no side /// effects if it was not used. This is equivalent to checking whether /// isInstructionTriviallyDead would be true if the use count was 0. bool wouldInstructionBeTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI = nullptr); /// 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 RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI = nullptr); /// Delete all of the instructions in `DeadInsts`, and all other instructions /// that deleting these in turn causes to be trivially dead. /// /// The initial instructions in the provided vector must all have empty use /// lists and satisfy `isInstructionTriviallyDead`. /// /// `DeadInsts` will be used as scratch storage for this routine and will be /// empty afterward. void RecursivelyDeleteTriviallyDeadInstructions( SmallVectorImpl &DeadInsts, const TargetLibraryInfo *TLI = nullptr); /// 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 RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI = nullptr); /// 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 SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr); //===----------------------------------------------------------------------===// // Control Flow Graph Restructuring. // /// 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 RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, DeferredDominance *DDT = nullptr); /// BB is a block with one predecessor and its predecessor is known to have one /// successor (BB!). Eliminate the edge between them, moving the instructions in /// the predecessor into BB. This deletes the predecessor block. void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT = nullptr, DeferredDominance *DDT = nullptr); /// BB is known to contain an unconditional branch, and contains no instructions /// other than PHI nodes, potential debug 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 TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DeferredDominance *DDT = nullptr); /// 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 EliminateDuplicatePHINodes(BasicBlock *BB); /// This function is used to do simplification of a CFG. For example, it /// adjusts branches to branches to eliminate the extra hop, it eliminates /// unreachable basic blocks, and does other peephole optimization of the CFG. /// It returns true if a modification was made, possibly deleting the basic /// block that was pointed to. LoopHeaders is an optional input parameter /// providing the set of loop headers that SimplifyCFG should not eliminate. bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, const SimplifyCFGOptions &Options = {}, SmallPtrSetImpl *LoopHeaders = nullptr); /// This function is used to flatten a CFG. For example, it uses parallel-and /// and parallel-or mode to collapse if-conditions and merge if-regions with /// identical statements. bool FlattenCFG(BasicBlock *BB, AliasAnalysis *AA = nullptr); /// If this basic block is ONLY a setcc and a branch, and if a predecessor /// branches to us and one of our successors, fold the setcc into the /// predecessor and use logical operations to pick the right destination. bool FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold = 1); /// This function takes a virtual register computed by an Instruction and /// replaces it with a slot in the stack frame, allocated via alloca. /// This allows the CFG to be changed around without fear of invalidating the /// SSA information for the value. It returns the pointer to the alloca inserted /// to create a stack slot for X. AllocaInst *DemoteRegToStack(Instruction &X, bool VolatileLoads = false, Instruction *AllocaPoint = nullptr); /// This function takes a virtual register computed by a phi node and replaces /// it with a slot in the stack frame, allocated via alloca. The phi node is /// deleted and it returns the pointer to the alloca inserted. AllocaInst *DemotePHIToStack(PHINode *P, Instruction *AllocaPoint = nullptr); /// Try to ensure that the alignment of \p V is at least \p PrefAlign bytes. If /// the owning object can be modified and has an alignment less than \p /// PrefAlign, it will be increased and \p PrefAlign returned. If the alignment /// cannot be increased, the known alignment of the value is returned. /// /// It is not always possible to modify the alignment of the underlying object, /// so 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. unsigned getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, const DataLayout &DL, const Instruction *CxtI = nullptr, AssumptionCache *AC = nullptr, const DominatorTree *DT = nullptr); /// Try to infer an alignment for the specified pointer. inline unsigned getKnownAlignment(Value *V, const DataLayout &DL, const Instruction *CxtI = nullptr, AssumptionCache *AC = nullptr, const DominatorTree *DT = nullptr) { return getOrEnforceKnownAlignment(V, 0, DL, CxtI, AC, DT); } ///===---------------------------------------------------------------------===// /// Dbg Intrinsic utilities /// /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic. void ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, StoreInst *SI, DIBuilder &Builder); /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic. void ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, LoadInst *LI, DIBuilder &Builder); /// Inserts a llvm.dbg.value intrinsic after a phi that has an associated /// llvm.dbg.declare or llvm.dbg.addr intrinsic. void ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, PHINode *LI, DIBuilder &Builder); /// Lowers llvm.dbg.declare intrinsics into appropriate set of /// llvm.dbg.value intrinsics. bool LowerDbgDeclare(Function &F); /// Propagate dbg.value intrinsics through the newly inserted PHIs. void insertDebugValuesForPHIs(BasicBlock *BB, SmallVectorImpl &InsertedPHIs); /// Finds all intrinsics declaring local variables as living in the memory that /// 'V' points to. This may include a mix of dbg.declare and /// dbg.addr intrinsics. TinyPtrVector FindDbgAddrUses(Value *V); /// Finds the llvm.dbg.value intrinsics describing a value. void findDbgValues(SmallVectorImpl &DbgValues, Value *V); /// Finds the debug info intrinsics describing a value. void findDbgUsers(SmallVectorImpl &DbgInsts, Value *V); /// Replaces llvm.dbg.declare instruction when the address it /// describes is replaced with a new value. If Deref is true, an /// additional DW_OP_deref is prepended to the expression. If Offset /// is non-zero, a constant displacement is added to the expression /// (between the optional Deref operations). Offset can be negative. bool replaceDbgDeclare(Value *Address, Value *NewAddress, Instruction *InsertBefore, DIBuilder &Builder, bool DerefBefore, int Offset, bool DerefAfter); /// Replaces llvm.dbg.declare instruction when the alloca it describes /// is replaced with a new value. If Deref is true, an additional /// DW_OP_deref is prepended to the expression. If Offset is non-zero, /// a constant displacement is added to the expression (between the /// optional Deref operations). Offset can be negative. The new /// llvm.dbg.declare is inserted immediately before AI. bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, DIBuilder &Builder, bool DerefBefore, int Offset, bool DerefAfter); /// Replaces multiple llvm.dbg.value instructions when the alloca it describes /// is replaced with a new value. If Offset is non-zero, a constant displacement /// is added to the expression (after the mandatory Deref). Offset can be /// negative. New llvm.dbg.value instructions are inserted at the locations of /// the instructions they replace. void replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress, DIBuilder &Builder, int Offset = 0); /// Assuming the instruction \p I is going to be deleted, attempt to salvage any /// dbg.value intrinsics referring to \p I by rewriting its effect into a /// DIExpression. void salvageDebugInfo(Instruction &I); +/// Assuming the instruction \p From is going to be deleted, insert replacement +/// dbg.value intrinsics for each debug user of \p From. The newly-inserted +/// dbg.values refer to \p To instead of \p From. Each replacement dbg.value +/// has the same location and variable as the debug user it replaces, has a +/// DIExpression determined by the result of \p RewriteExpr applied to an old +/// debug user of \p From, and is placed before \p InsertBefore. +void insertReplacementDbgValues( + Instruction &From, Instruction &To, Instruction &InsertBefore, + function_ref RewriteExpr); + /// Remove all instructions from a basic block other than it's terminator /// and any present EH pad instructions. unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB); /// Insert an unreachable instruction before the specified /// instruction, making it and the rest of the code in the block dead. unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap, bool PreserveLCSSA = false, DeferredDominance *DDT = nullptr); /// Convert the CallInst to InvokeInst with the specified unwind edge basic /// block. This also splits the basic block where CI is located, because /// InvokeInst is a terminator instruction. Returns the newly split basic /// block. BasicBlock *changeToInvokeAndSplitBasicBlock(CallInst *CI, BasicBlock *UnwindEdge); /// Replace 'BB's terminator with one that does not have an unwind successor /// block. Rewrites `invoke` to `call`, etc. Updates any PHIs in unwind /// successor. /// /// \param BB Block whose terminator will be replaced. Its terminator must /// have an unwind successor. void removeUnwindEdge(BasicBlock *BB, DeferredDominance *DDT = nullptr); /// Remove all blocks that can not be reached from the function's entry. /// /// Returns true if any basic block was removed. bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr, DeferredDominance *DDT = nullptr); /// Combine the metadata of two instructions so that K can replace J /// /// Metadata not listed as known via KnownIDs is removed void combineMetadata(Instruction *K, const Instruction *J, ArrayRef KnownIDs); /// Combine the metadata of two instructions so that K can replace J. This /// specifically handles the case of CSE-like transformations. /// /// Unknown metadata is removed. void combineMetadataForCSE(Instruction *K, const Instruction *J); // Replace each use of 'From' with 'To', if that use does not belong to basic // block where 'From' is defined. Returns the number of replacements made. unsigned replaceNonLocalUsesWith(Instruction *From, Value *To); /// Replace each use of 'From' with 'To' if that use is dominated by /// the given edge. Returns the number of replacements made. unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge); /// Replace each use of 'From' with 'To' if that use is dominated by /// the end of the given BasicBlock. Returns the number of replacements made. unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlock *BB); /// Return true if the CallSite CS calls a gc leaf function. /// /// A leaf function is a function that does not safepoint the thread during its /// execution. During a call or invoke to such a function, the callers stack /// does not have to be made parseable. /// /// Most passes can and should ignore this information, and it is only used /// during lowering by the GC infrastructure. bool callsGCLeafFunction(ImmutableCallSite CS, const TargetLibraryInfo &TLI); /// Copy a nonnull metadata node to a new load instruction. /// /// This handles mapping it to range metadata if the new load is an integer /// load instead of a pointer load. void copyNonnullMetadata(const LoadInst &OldLI, MDNode *N, LoadInst &NewLI); /// Copy a range metadata node to a new load instruction. /// /// This handles mapping it to nonnull metadata if the new load is a pointer /// load instead of an integer load and the range doesn't cover null. void copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI, MDNode *N, LoadInst &NewLI); //===----------------------------------------------------------------------===// // Intrinsic pattern matching // /// Try to match a bswap or bitreverse idiom. /// /// If an idiom is matched, an intrinsic call is inserted before \c I. Any added /// instructions are returned in \c InsertedInsts. They will all have been added /// to a basic block. /// /// A bitreverse idiom normally requires around 2*BW nodes to be searched (where /// BW is the bitwidth of the integer type). A bswap idiom requires anywhere up /// to BW / 4 nodes to be searched, so is significantly faster. /// /// This function returns true on a successful match or false otherwise. bool recognizeBSwapOrBitReverseIdiom( Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl &InsertedInsts); //===----------------------------------------------------------------------===// // Sanitizer utilities // /// Given a CallInst, check if it calls a string function known to CodeGen, /// and mark it with NoBuiltin if so. To be used by sanitizers that intend /// to intercept string functions and want to avoid converting them to target /// specific instructions. void maybeMarkSanitizerLibraryCallNoBuiltin(CallInst *CI, const TargetLibraryInfo *TLI); //===----------------------------------------------------------------------===// // Transform predicates // /// Given an instruction, is it legal to set operand OpIdx to a non-constant /// value? bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx); } // end namespace llvm #endif // LLVM_TRANSFORMS_UTILS_LOCAL_H diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp index 9f297b0aab08..aa86dddf04d0 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp @@ -1,2396 +1,2391 @@ //===- InstCombineCasts.cpp -----------------------------------------------===// // // 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 visit functions for cast operations. // //===----------------------------------------------------------------------===// #include "InstCombineInternal.h" #include "llvm/ADT/SetVector.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DIBuilder.h" #include "llvm/IR/PatternMatch.h" #include "llvm/Support/KnownBits.h" using namespace llvm; using namespace PatternMatch; #define DEBUG_TYPE "instcombine" /// Analyze 'Val', seeing if it is a simple linear expression. /// If so, decompose it, returning some value X, such that Val is /// X*Scale+Offset. /// static Value *decomposeSimpleLinearExpr(Value *Val, unsigned &Scale, uint64_t &Offset) { if (ConstantInt *CI = dyn_cast(Val)) { Offset = CI->getZExtValue(); Scale = 0; return ConstantInt::get(Val->getType(), 0); } if (BinaryOperator *I = dyn_cast(Val)) { // Cannot look past anything that might overflow. OverflowingBinaryOperator *OBI = dyn_cast(Val); if (OBI && !OBI->hasNoUnsignedWrap() && !OBI->hasNoSignedWrap()) { Scale = 1; Offset = 0; return Val; } if (ConstantInt *RHS = dyn_cast(I->getOperand(1))) { if (I->getOpcode() == Instruction::Shl) { // This is a value scaled by '1 << the shift amt'. Scale = UINT64_C(1) << RHS->getZExtValue(); Offset = 0; return I->getOperand(0); } if (I->getOpcode() == Instruction::Mul) { // This value is scaled by 'RHS'. Scale = RHS->getZExtValue(); Offset = 0; return I->getOperand(0); } if (I->getOpcode() == Instruction::Add) { // We have X+C. Check to see if we really have (X*C2)+C1, // where C1 is divisible by C2. unsigned SubScale; Value *SubVal = decomposeSimpleLinearExpr(I->getOperand(0), SubScale, Offset); Offset += RHS->getZExtValue(); Scale = SubScale; return SubVal; } } } // Otherwise, we can't look past this. Scale = 1; Offset = 0; return Val; } /// If we find a cast of an allocation instruction, try to eliminate the cast by /// moving the type information into the alloc. Instruction *InstCombiner::PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI) { PointerType *PTy = cast(CI.getType()); BuilderTy AllocaBuilder(Builder); AllocaBuilder.SetInsertPoint(&AI); // Get the type really allocated and the type casted to. Type *AllocElTy = AI.getAllocatedType(); Type *CastElTy = PTy->getElementType(); if (!AllocElTy->isSized() || !CastElTy->isSized()) return nullptr; unsigned AllocElTyAlign = DL.getABITypeAlignment(AllocElTy); unsigned CastElTyAlign = DL.getABITypeAlignment(CastElTy); if (CastElTyAlign < AllocElTyAlign) return nullptr; // If the allocation has multiple uses, only promote it if we are strictly // increasing the alignment of the resultant allocation. If we keep it the // same, we open the door to infinite loops of various kinds. if (!AI.hasOneUse() && CastElTyAlign == AllocElTyAlign) return nullptr; uint64_t AllocElTySize = DL.getTypeAllocSize(AllocElTy); uint64_t CastElTySize = DL.getTypeAllocSize(CastElTy); if (CastElTySize == 0 || AllocElTySize == 0) return nullptr; // If the allocation has multiple uses, only promote it if we're not // shrinking the amount of memory being allocated. uint64_t AllocElTyStoreSize = DL.getTypeStoreSize(AllocElTy); uint64_t CastElTyStoreSize = DL.getTypeStoreSize(CastElTy); if (!AI.hasOneUse() && CastElTyStoreSize < AllocElTyStoreSize) return nullptr; // See if we can satisfy the modulus by pulling a scale out of the array // size argument. unsigned ArraySizeScale; uint64_t ArrayOffset; Value *NumElements = // See if the array size is a decomposable linear expr. decomposeSimpleLinearExpr(AI.getOperand(0), ArraySizeScale, ArrayOffset); // If we can now satisfy the modulus, by using a non-1 scale, we really can // do the xform. if ((AllocElTySize*ArraySizeScale) % CastElTySize != 0 || (AllocElTySize*ArrayOffset ) % CastElTySize != 0) return nullptr; unsigned Scale = (AllocElTySize*ArraySizeScale)/CastElTySize; Value *Amt = nullptr; if (Scale == 1) { Amt = NumElements; } else { Amt = ConstantInt::get(AI.getArraySize()->getType(), Scale); // Insert before the alloca, not before the cast. Amt = AllocaBuilder.CreateMul(Amt, NumElements); } if (uint64_t Offset = (AllocElTySize*ArrayOffset)/CastElTySize) { Value *Off = ConstantInt::get(AI.getArraySize()->getType(), Offset, true); Amt = AllocaBuilder.CreateAdd(Amt, Off); } AllocaInst *New = AllocaBuilder.CreateAlloca(CastElTy, Amt); New->setAlignment(AI.getAlignment()); New->takeName(&AI); New->setUsedWithInAlloca(AI.isUsedWithInAlloca()); // If the allocation has multiple real uses, insert a cast and change all // things that used it to use the new cast. This will also hack on CI, but it // will die soon. if (!AI.hasOneUse()) { // New is the allocation instruction, pointer typed. AI is the original // allocation instruction, also pointer typed. Thus, cast to use is BitCast. Value *NewCast = AllocaBuilder.CreateBitCast(New, AI.getType(), "tmpcast"); replaceInstUsesWith(AI, NewCast); } return replaceInstUsesWith(CI, New); } /// Given an expression that CanEvaluateTruncated or CanEvaluateSExtd returns /// true for, actually insert the code to evaluate the expression. Value *InstCombiner::EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned) { if (Constant *C = dyn_cast(V)) { C = ConstantExpr::getIntegerCast(C, Ty, isSigned /*Sext or ZExt*/); // If we got a constantexpr back, try to simplify it with DL info. if (Constant *FoldedC = ConstantFoldConstant(C, DL, &TLI)) C = FoldedC; return C; } // Otherwise, it must be an instruction. Instruction *I = cast(V); Instruction *Res = nullptr; unsigned Opc = I->getOpcode(); switch (Opc) { case Instruction::Add: case Instruction::Sub: case Instruction::Mul: case Instruction::And: case Instruction::Or: case Instruction::Xor: case Instruction::AShr: case Instruction::LShr: case Instruction::Shl: case Instruction::UDiv: case Instruction::URem: { Value *LHS = EvaluateInDifferentType(I->getOperand(0), Ty, isSigned); Value *RHS = EvaluateInDifferentType(I->getOperand(1), Ty, isSigned); Res = BinaryOperator::Create((Instruction::BinaryOps)Opc, LHS, RHS); break; } case Instruction::Trunc: case Instruction::ZExt: case Instruction::SExt: // If the source type of the cast is the type we're trying for then we can // just return the source. There's no need to insert it because it is not // new. if (I->getOperand(0)->getType() == Ty) return I->getOperand(0); // Otherwise, must be the same type of cast, so just reinsert a new one. // This also handles the case of zext(trunc(x)) -> zext(x). Res = CastInst::CreateIntegerCast(I->getOperand(0), Ty, Opc == Instruction::SExt); break; case Instruction::Select: { Value *True = EvaluateInDifferentType(I->getOperand(1), Ty, isSigned); Value *False = EvaluateInDifferentType(I->getOperand(2), Ty, isSigned); Res = SelectInst::Create(I->getOperand(0), True, False); break; } case Instruction::PHI: { PHINode *OPN = cast(I); PHINode *NPN = PHINode::Create(Ty, OPN->getNumIncomingValues()); for (unsigned i = 0, e = OPN->getNumIncomingValues(); i != e; ++i) { Value *V = EvaluateInDifferentType(OPN->getIncomingValue(i), Ty, isSigned); NPN->addIncoming(V, OPN->getIncomingBlock(i)); } Res = NPN; break; } default: // TODO: Can handle more cases here. llvm_unreachable("Unreachable!"); } Res->takeName(I); return InsertNewInstWith(Res, *I); } Instruction::CastOps InstCombiner::isEliminableCastPair(const CastInst *CI1, const CastInst *CI2) { Type *SrcTy = CI1->getSrcTy(); Type *MidTy = CI1->getDestTy(); Type *DstTy = CI2->getDestTy(); Instruction::CastOps firstOp = CI1->getOpcode(); Instruction::CastOps secondOp = CI2->getOpcode(); Type *SrcIntPtrTy = SrcTy->isPtrOrPtrVectorTy() ? DL.getIntPtrType(SrcTy) : nullptr; Type *MidIntPtrTy = MidTy->isPtrOrPtrVectorTy() ? DL.getIntPtrType(MidTy) : nullptr; Type *DstIntPtrTy = DstTy->isPtrOrPtrVectorTy() ? DL.getIntPtrType(DstTy) : nullptr; unsigned Res = CastInst::isEliminableCastPair(firstOp, secondOp, SrcTy, MidTy, DstTy, SrcIntPtrTy, MidIntPtrTy, DstIntPtrTy); // We don't want to form an inttoptr or ptrtoint that converts to an integer // type that differs from the pointer size. if ((Res == Instruction::IntToPtr && SrcTy != DstIntPtrTy) || (Res == Instruction::PtrToInt && DstTy != SrcIntPtrTy)) Res = 0; return Instruction::CastOps(Res); } /// Implement the transforms common to all CastInst visitors. Instruction *InstCombiner::commonCastTransforms(CastInst &CI) { Value *Src = CI.getOperand(0); // Try to eliminate a cast of a cast. if (auto *CSrc = dyn_cast(Src)) { // A->B->C cast if (Instruction::CastOps NewOpc = isEliminableCastPair(CSrc, &CI)) { // The first cast (CSrc) is eliminable so we need to fix up or replace // the second cast (CI). CSrc will then have a good chance of being dead. auto *Res = CastInst::Create(NewOpc, CSrc->getOperand(0), CI.getType()); - // If the eliminable cast has debug users, insert a debug value after the - // cast pointing to the new Value. - SmallVector CSrcDbgInsts; - findDbgUsers(CSrcDbgInsts, CSrc); - if (CSrcDbgInsts.size()) { - DIBuilder DIB(*CI.getModule()); - for (auto *DII : CSrcDbgInsts) - DIB.insertDbgValueIntrinsic( - Res, DII->getVariable(), DII->getExpression(), - DII->getDebugLoc().get(), &*std::next(CI.getIterator())); - } + // Replace debug users of the eliminable cast by emitting debug values + // which refer to the new cast. + insertReplacementDbgValues( + *CSrc, *Res, *std::next(CI.getIterator()), + [](DbgInfoIntrinsic &OldDII) { return OldDII.getExpression(); }); + return Res; } } if (auto *Sel = dyn_cast(Src)) { // We are casting a select. Try to fold the cast into the select, but only // if the select does not have a compare instruction with matching operand // types. Creating a select with operands that are different sizes than its // condition may inhibit other folds and lead to worse codegen. auto *Cmp = dyn_cast(Sel->getCondition()); if (!Cmp || Cmp->getOperand(0)->getType() != Sel->getType()) if (Instruction *NV = FoldOpIntoSelect(CI, Sel)) return NV; } // If we are casting a PHI, then fold the cast into the PHI. if (auto *PN = dyn_cast(Src)) { // Don't do this if it would create a PHI node with an illegal type from a // legal type. if (!Src->getType()->isIntegerTy() || !CI.getType()->isIntegerTy() || shouldChangeType(CI.getType(), Src->getType())) if (Instruction *NV = foldOpIntoPhi(CI, PN)) return NV; } return nullptr; } /// Constants and extensions/truncates from the destination type are always /// free to be evaluated in that type. This is a helper for canEvaluate*. static bool canAlwaysEvaluateInType(Value *V, Type *Ty) { if (isa(V)) return true; Value *X; if ((match(V, m_ZExtOrSExt(m_Value(X))) || match(V, m_Trunc(m_Value(X)))) && X->getType() == Ty) return true; return false; } /// Filter out values that we can not evaluate in the destination type for free. /// This is a helper for canEvaluate*. static bool canNotEvaluateInType(Value *V, Type *Ty) { assert(!isa(V) && "Constant should already be handled."); if (!isa(V)) return true; // We don't extend or shrink something that has multiple uses -- doing so // would require duplicating the instruction which isn't profitable. if (!V->hasOneUse()) return true; return false; } /// Return true if we can evaluate the specified expression tree as type Ty /// instead of its larger type, and arrive with the same value. /// This is used by code that tries to eliminate truncates. /// /// Ty will always be a type smaller than V. We should return true if trunc(V) /// can be computed by computing V in the smaller type. If V is an instruction, /// then trunc(inst(x,y)) can be computed as inst(trunc(x),trunc(y)), which only /// makes sense if x and y can be efficiently truncated. /// /// This function works on both vectors and scalars. /// static bool canEvaluateTruncated(Value *V, Type *Ty, InstCombiner &IC, Instruction *CxtI) { if (canAlwaysEvaluateInType(V, Ty)) return true; if (canNotEvaluateInType(V, Ty)) return false; auto *I = cast(V); Type *OrigTy = V->getType(); switch (I->getOpcode()) { case Instruction::Add: case Instruction::Sub: case Instruction::Mul: case Instruction::And: case Instruction::Or: case Instruction::Xor: // These operators can all arbitrarily be extended or truncated. return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI) && canEvaluateTruncated(I->getOperand(1), Ty, IC, CxtI); case Instruction::UDiv: case Instruction::URem: { // UDiv and URem can be truncated if all the truncated bits are zero. uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits(); uint32_t BitWidth = Ty->getScalarSizeInBits(); assert(BitWidth < OrigBitWidth && "Unexpected bitwidths!"); APInt Mask = APInt::getBitsSetFrom(OrigBitWidth, BitWidth); if (IC.MaskedValueIsZero(I->getOperand(0), Mask, 0, CxtI) && IC.MaskedValueIsZero(I->getOperand(1), Mask, 0, CxtI)) { return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI) && canEvaluateTruncated(I->getOperand(1), Ty, IC, CxtI); } break; } case Instruction::Shl: { // If we are truncating the result of this SHL, and if it's a shift of a // constant amount, we can always perform a SHL in a smaller type. const APInt *Amt; if (match(I->getOperand(1), m_APInt(Amt))) { uint32_t BitWidth = Ty->getScalarSizeInBits(); if (Amt->getLimitedValue(BitWidth) < BitWidth) return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI); } break; } case Instruction::LShr: { // If this is a truncate of a logical shr, we can truncate it to a smaller // lshr iff we know that the bits we would otherwise be shifting in are // already zeros. const APInt *Amt; if (match(I->getOperand(1), m_APInt(Amt))) { uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits(); uint32_t BitWidth = Ty->getScalarSizeInBits(); if (Amt->getLimitedValue(BitWidth) < BitWidth && IC.MaskedValueIsZero(I->getOperand(0), APInt::getBitsSetFrom(OrigBitWidth, BitWidth), 0, CxtI)) { return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI); } } break; } case Instruction::AShr: { // If this is a truncate of an arithmetic shr, we can truncate it to a // smaller ashr iff we know that all the bits from the sign bit of the // original type and the sign bit of the truncate type are similar. // TODO: It is enough to check that the bits we would be shifting in are // similar to sign bit of the truncate type. const APInt *Amt; if (match(I->getOperand(1), m_APInt(Amt))) { uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits(); uint32_t BitWidth = Ty->getScalarSizeInBits(); if (Amt->getLimitedValue(BitWidth) < BitWidth && OrigBitWidth - BitWidth < IC.ComputeNumSignBits(I->getOperand(0), 0, CxtI)) return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI); } break; } case Instruction::Trunc: // trunc(trunc(x)) -> trunc(x) return true; case Instruction::ZExt: case Instruction::SExt: // trunc(ext(x)) -> ext(x) if the source type is smaller than the new dest // trunc(ext(x)) -> trunc(x) if the source type is larger than the new dest return true; case Instruction::Select: { SelectInst *SI = cast(I); return canEvaluateTruncated(SI->getTrueValue(), Ty, IC, CxtI) && canEvaluateTruncated(SI->getFalseValue(), Ty, IC, CxtI); } case Instruction::PHI: { // We can change a phi if we can change all operands. Note that we never // get into trouble with cyclic PHIs here because we only consider // instructions with a single use. PHINode *PN = cast(I); for (Value *IncValue : PN->incoming_values()) if (!canEvaluateTruncated(IncValue, Ty, IC, CxtI)) return false; return true; } default: // TODO: Can handle more cases here. break; } return false; } /// Given a vector that is bitcast to an integer, optionally logically /// right-shifted, and truncated, convert it to an extractelement. /// Example (big endian): /// trunc (lshr (bitcast <4 x i32> %X to i128), 32) to i32 /// ---> /// extractelement <4 x i32> %X, 1 static Instruction *foldVecTruncToExtElt(TruncInst &Trunc, InstCombiner &IC) { Value *TruncOp = Trunc.getOperand(0); Type *DestType = Trunc.getType(); if (!TruncOp->hasOneUse() || !isa(DestType)) return nullptr; Value *VecInput = nullptr; ConstantInt *ShiftVal = nullptr; if (!match(TruncOp, m_CombineOr(m_BitCast(m_Value(VecInput)), m_LShr(m_BitCast(m_Value(VecInput)), m_ConstantInt(ShiftVal)))) || !isa(VecInput->getType())) return nullptr; VectorType *VecType = cast(VecInput->getType()); unsigned VecWidth = VecType->getPrimitiveSizeInBits(); unsigned DestWidth = DestType->getPrimitiveSizeInBits(); unsigned ShiftAmount = ShiftVal ? ShiftVal->getZExtValue() : 0; if ((VecWidth % DestWidth != 0) || (ShiftAmount % DestWidth != 0)) return nullptr; // If the element type of the vector doesn't match the result type, // bitcast it to a vector type that we can extract from. unsigned NumVecElts = VecWidth / DestWidth; if (VecType->getElementType() != DestType) { VecType = VectorType::get(DestType, NumVecElts); VecInput = IC.Builder.CreateBitCast(VecInput, VecType, "bc"); } unsigned Elt = ShiftAmount / DestWidth; if (IC.getDataLayout().isBigEndian()) Elt = NumVecElts - 1 - Elt; return ExtractElementInst::Create(VecInput, IC.Builder.getInt32(Elt)); } /// Rotate left/right may occur in a wider type than necessary because of type /// promotion rules. Try to narrow all of the component instructions. Instruction *InstCombiner::narrowRotate(TruncInst &Trunc) { assert((isa(Trunc.getSrcTy()) || shouldChangeType(Trunc.getSrcTy(), Trunc.getType())) && "Don't narrow to an illegal scalar type"); // First, find an or'd pair of opposite shifts with the same shifted operand: // trunc (or (lshr ShVal, ShAmt0), (shl ShVal, ShAmt1)) Value *Or0, *Or1; if (!match(Trunc.getOperand(0), m_OneUse(m_Or(m_Value(Or0), m_Value(Or1))))) return nullptr; Value *ShVal, *ShAmt0, *ShAmt1; if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(ShVal), m_Value(ShAmt0)))) || !match(Or1, m_OneUse(m_LogicalShift(m_Specific(ShVal), m_Value(ShAmt1))))) return nullptr; auto ShiftOpcode0 = cast(Or0)->getOpcode(); auto ShiftOpcode1 = cast(Or1)->getOpcode(); if (ShiftOpcode0 == ShiftOpcode1) return nullptr; // The shift amounts must add up to the narrow bit width. Value *ShAmt; bool SubIsOnLHS; Type *DestTy = Trunc.getType(); unsigned NarrowWidth = DestTy->getScalarSizeInBits(); if (match(ShAmt0, m_OneUse(m_Sub(m_SpecificInt(NarrowWidth), m_Specific(ShAmt1))))) { ShAmt = ShAmt1; SubIsOnLHS = true; } else if (match(ShAmt1, m_OneUse(m_Sub(m_SpecificInt(NarrowWidth), m_Specific(ShAmt0))))) { ShAmt = ShAmt0; SubIsOnLHS = false; } else { return nullptr; } // The shifted value must have high zeros in the wide type. Typically, this // will be a zext, but it could also be the result of an 'and' or 'shift'. unsigned WideWidth = Trunc.getSrcTy()->getScalarSizeInBits(); APInt HiBitMask = APInt::getHighBitsSet(WideWidth, WideWidth - NarrowWidth); if (!MaskedValueIsZero(ShVal, HiBitMask, 0, &Trunc)) return nullptr; // We have an unnecessarily wide rotate! // trunc (or (lshr ShVal, ShAmt), (shl ShVal, BitWidth - ShAmt)) // Narrow it down to eliminate the zext/trunc: // or (lshr trunc(ShVal), ShAmt0'), (shl trunc(ShVal), ShAmt1') Value *NarrowShAmt = Builder.CreateTrunc(ShAmt, DestTy); Value *NegShAmt = Builder.CreateNeg(NarrowShAmt); // Mask both shift amounts to ensure there's no UB from oversized shifts. Constant *MaskC = ConstantInt::get(DestTy, NarrowWidth - 1); Value *MaskedShAmt = Builder.CreateAnd(NarrowShAmt, MaskC); Value *MaskedNegShAmt = Builder.CreateAnd(NegShAmt, MaskC); // Truncate the original value and use narrow ops. Value *X = Builder.CreateTrunc(ShVal, DestTy); Value *NarrowShAmt0 = SubIsOnLHS ? MaskedNegShAmt : MaskedShAmt; Value *NarrowShAmt1 = SubIsOnLHS ? MaskedShAmt : MaskedNegShAmt; Value *NarrowSh0 = Builder.CreateBinOp(ShiftOpcode0, X, NarrowShAmt0); Value *NarrowSh1 = Builder.CreateBinOp(ShiftOpcode1, X, NarrowShAmt1); return BinaryOperator::CreateOr(NarrowSh0, NarrowSh1); } /// Try to narrow the width of math or bitwise logic instructions by pulling a /// truncate ahead of binary operators. /// TODO: Transforms for truncated shifts should be moved into here. Instruction *InstCombiner::narrowBinOp(TruncInst &Trunc) { Type *SrcTy = Trunc.getSrcTy(); Type *DestTy = Trunc.getType(); if (!isa(SrcTy) && !shouldChangeType(SrcTy, DestTy)) return nullptr; BinaryOperator *BinOp; if (!match(Trunc.getOperand(0), m_OneUse(m_BinOp(BinOp)))) return nullptr; Value *BinOp0 = BinOp->getOperand(0); Value *BinOp1 = BinOp->getOperand(1); switch (BinOp->getOpcode()) { case Instruction::And: case Instruction::Or: case Instruction::Xor: case Instruction::Add: case Instruction::Sub: case Instruction::Mul: { Constant *C; if (match(BinOp0, m_Constant(C))) { // trunc (binop C, X) --> binop (trunc C', X) Constant *NarrowC = ConstantExpr::getTrunc(C, DestTy); Value *TruncX = Builder.CreateTrunc(BinOp1, DestTy); return BinaryOperator::Create(BinOp->getOpcode(), NarrowC, TruncX); } if (match(BinOp1, m_Constant(C))) { // trunc (binop X, C) --> binop (trunc X, C') Constant *NarrowC = ConstantExpr::getTrunc(C, DestTy); Value *TruncX = Builder.CreateTrunc(BinOp0, DestTy); return BinaryOperator::Create(BinOp->getOpcode(), TruncX, NarrowC); } Value *X; if (match(BinOp0, m_ZExtOrSExt(m_Value(X))) && X->getType() == DestTy) { // trunc (binop (ext X), Y) --> binop X, (trunc Y) Value *NarrowOp1 = Builder.CreateTrunc(BinOp1, DestTy); return BinaryOperator::Create(BinOp->getOpcode(), X, NarrowOp1); } if (match(BinOp1, m_ZExtOrSExt(m_Value(X))) && X->getType() == DestTy) { // trunc (binop Y, (ext X)) --> binop (trunc Y), X Value *NarrowOp0 = Builder.CreateTrunc(BinOp0, DestTy); return BinaryOperator::Create(BinOp->getOpcode(), NarrowOp0, X); } break; } default: break; } if (Instruction *NarrowOr = narrowRotate(Trunc)) return NarrowOr; return nullptr; } /// Try to narrow the width of a splat shuffle. This could be generalized to any /// shuffle with a constant operand, but we limit the transform to avoid /// creating a shuffle type that targets may not be able to lower effectively. static Instruction *shrinkSplatShuffle(TruncInst &Trunc, InstCombiner::BuilderTy &Builder) { auto *Shuf = dyn_cast(Trunc.getOperand(0)); if (Shuf && Shuf->hasOneUse() && isa(Shuf->getOperand(1)) && Shuf->getMask()->getSplatValue() && Shuf->getType() == Shuf->getOperand(0)->getType()) { // trunc (shuf X, Undef, SplatMask) --> shuf (trunc X), Undef, SplatMask Constant *NarrowUndef = UndefValue::get(Trunc.getType()); Value *NarrowOp = Builder.CreateTrunc(Shuf->getOperand(0), Trunc.getType()); return new ShuffleVectorInst(NarrowOp, NarrowUndef, Shuf->getMask()); } return nullptr; } /// Try to narrow the width of an insert element. This could be generalized for /// any vector constant, but we limit the transform to insertion into undef to /// avoid potential backend problems from unsupported insertion widths. This /// could also be extended to handle the case of inserting a scalar constant /// into a vector variable. static Instruction *shrinkInsertElt(CastInst &Trunc, InstCombiner::BuilderTy &Builder) { Instruction::CastOps Opcode = Trunc.getOpcode(); assert((Opcode == Instruction::Trunc || Opcode == Instruction::FPTrunc) && "Unexpected instruction for shrinking"); auto *InsElt = dyn_cast(Trunc.getOperand(0)); if (!InsElt || !InsElt->hasOneUse()) return nullptr; Type *DestTy = Trunc.getType(); Type *DestScalarTy = DestTy->getScalarType(); Value *VecOp = InsElt->getOperand(0); Value *ScalarOp = InsElt->getOperand(1); Value *Index = InsElt->getOperand(2); if (isa(VecOp)) { // trunc (inselt undef, X, Index) --> inselt undef, (trunc X), Index // fptrunc (inselt undef, X, Index) --> inselt undef, (fptrunc X), Index UndefValue *NarrowUndef = UndefValue::get(DestTy); Value *NarrowOp = Builder.CreateCast(Opcode, ScalarOp, DestScalarTy); return InsertElementInst::Create(NarrowUndef, NarrowOp, Index); } return nullptr; } Instruction *InstCombiner::visitTrunc(TruncInst &CI) { if (Instruction *Result = commonCastTransforms(CI)) return Result; // Test if the trunc is the user of a select which is part of a // minimum or maximum operation. If so, don't do any more simplification. // Even simplifying demanded bits can break the canonical form of a // min/max. Value *LHS, *RHS; if (SelectInst *SI = dyn_cast(CI.getOperand(0))) if (matchSelectPattern(SI, LHS, RHS).Flavor != SPF_UNKNOWN) return nullptr; // See if we can simplify any instructions used by the input whose sole // purpose is to compute bits we don't care about. if (SimplifyDemandedInstructionBits(CI)) return &CI; Value *Src = CI.getOperand(0); Type *DestTy = CI.getType(), *SrcTy = Src->getType(); // Attempt to truncate the entire input expression tree to the destination // type. Only do this if the dest type is a simple type, don't convert the // expression tree to something weird like i93 unless the source is also // strange. if ((DestTy->isVectorTy() || shouldChangeType(SrcTy, DestTy)) && canEvaluateTruncated(Src, DestTy, *this, &CI)) { // If this cast is a truncate, evaluting in a different type always // eliminates the cast, so it is always a win. LLVM_DEBUG( dbgs() << "ICE: EvaluateInDifferentType converting expression type" " to avoid cast: " << CI << '\n'); Value *Res = EvaluateInDifferentType(Src, DestTy, false); assert(Res->getType() == DestTy); return replaceInstUsesWith(CI, Res); } // Canonicalize trunc x to i1 -> (icmp ne (and x, 1), 0), likewise for vector. if (DestTy->getScalarSizeInBits() == 1) { Constant *One = ConstantInt::get(SrcTy, 1); Src = Builder.CreateAnd(Src, One); Value *Zero = Constant::getNullValue(Src->getType()); return new ICmpInst(ICmpInst::ICMP_NE, Src, Zero); } // FIXME: Maybe combine the next two transforms to handle the no cast case // more efficiently. Support vector types. Cleanup code by using m_OneUse. // Transform trunc(lshr (zext A), Cst) to eliminate one type conversion. Value *A = nullptr; ConstantInt *Cst = nullptr; if (Src->hasOneUse() && match(Src, m_LShr(m_ZExt(m_Value(A)), m_ConstantInt(Cst)))) { // We have three types to worry about here, the type of A, the source of // the truncate (MidSize), and the destination of the truncate. We know that // ASize < MidSize and MidSize > ResultSize, but don't know the relation // between ASize and ResultSize. unsigned ASize = A->getType()->getPrimitiveSizeInBits(); // If the shift amount is larger than the size of A, then the result is // known to be zero because all the input bits got shifted out. if (Cst->getZExtValue() >= ASize) return replaceInstUsesWith(CI, Constant::getNullValue(DestTy)); // Since we're doing an lshr and a zero extend, and know that the shift // amount is smaller than ASize, it is always safe to do the shift in A's // type, then zero extend or truncate to the result. Value *Shift = Builder.CreateLShr(A, Cst->getZExtValue()); Shift->takeName(Src); return CastInst::CreateIntegerCast(Shift, DestTy, false); } // FIXME: We should canonicalize to zext/trunc and remove this transform. // Transform trunc(lshr (sext A), Cst) to ashr A, Cst to eliminate type // conversion. // It works because bits coming from sign extension have the same value as // the sign bit of the original value; performing ashr instead of lshr // generates bits of the same value as the sign bit. if (Src->hasOneUse() && match(Src, m_LShr(m_SExt(m_Value(A)), m_ConstantInt(Cst)))) { Value *SExt = cast(Src)->getOperand(0); const unsigned SExtSize = SExt->getType()->getPrimitiveSizeInBits(); const unsigned ASize = A->getType()->getPrimitiveSizeInBits(); const unsigned CISize = CI.getType()->getPrimitiveSizeInBits(); const unsigned MaxAmt = SExtSize - std::max(CISize, ASize); unsigned ShiftAmt = Cst->getZExtValue(); // This optimization can be only performed when zero bits generated by // the original lshr aren't pulled into the value after truncation, so we // can only shift by values no larger than the number of extension bits. // FIXME: Instead of bailing when the shift is too large, use and to clear // the extra bits. if (ShiftAmt <= MaxAmt) { if (CISize == ASize) return BinaryOperator::CreateAShr(A, ConstantInt::get(CI.getType(), std::min(ShiftAmt, ASize - 1))); if (SExt->hasOneUse()) { Value *Shift = Builder.CreateAShr(A, std::min(ShiftAmt, ASize - 1)); Shift->takeName(Src); return CastInst::CreateIntegerCast(Shift, CI.getType(), true); } } } if (Instruction *I = narrowBinOp(CI)) return I; if (Instruction *I = shrinkSplatShuffle(CI, Builder)) return I; if (Instruction *I = shrinkInsertElt(CI, Builder)) return I; if (Src->hasOneUse() && isa(SrcTy) && shouldChangeType(SrcTy, DestTy)) { // Transform "trunc (shl X, cst)" -> "shl (trunc X), cst" so long as the // dest type is native and cst < dest size. if (match(Src, m_Shl(m_Value(A), m_ConstantInt(Cst))) && !match(A, m_Shr(m_Value(), m_Constant()))) { // Skip shifts of shift by constants. It undoes a combine in // FoldShiftByConstant and is the extend in reg pattern. const unsigned DestSize = DestTy->getScalarSizeInBits(); if (Cst->getValue().ult(DestSize)) { Value *NewTrunc = Builder.CreateTrunc(A, DestTy, A->getName() + ".tr"); return BinaryOperator::Create( Instruction::Shl, NewTrunc, ConstantInt::get(DestTy, Cst->getValue().trunc(DestSize))); } } } if (Instruction *I = foldVecTruncToExtElt(CI, *this)) return I; return nullptr; } Instruction *InstCombiner::transformZExtICmp(ICmpInst *ICI, ZExtInst &CI, bool DoTransform) { // If we are just checking for a icmp eq of a single bit and zext'ing it // to an integer, then shift the bit to the appropriate place and then // cast to integer to avoid the comparison. const APInt *Op1CV; if (match(ICI->getOperand(1), m_APInt(Op1CV))) { // zext (x x>>u31 true if signbit set. // zext (x >s -1) to i32 --> (x>>u31)^1 true if signbit clear. if ((ICI->getPredicate() == ICmpInst::ICMP_SLT && Op1CV->isNullValue()) || (ICI->getPredicate() == ICmpInst::ICMP_SGT && Op1CV->isAllOnesValue())) { if (!DoTransform) return ICI; Value *In = ICI->getOperand(0); Value *Sh = ConstantInt::get(In->getType(), In->getType()->getScalarSizeInBits() - 1); In = Builder.CreateLShr(In, Sh, In->getName() + ".lobit"); if (In->getType() != CI.getType()) In = Builder.CreateIntCast(In, CI.getType(), false /*ZExt*/); if (ICI->getPredicate() == ICmpInst::ICMP_SGT) { Constant *One = ConstantInt::get(In->getType(), 1); In = Builder.CreateXor(In, One, In->getName() + ".not"); } return replaceInstUsesWith(CI, In); } // zext (X == 0) to i32 --> X^1 iff X has only the low bit set. // zext (X == 0) to i32 --> (X>>1)^1 iff X has only the 2nd bit set. // zext (X == 1) to i32 --> X iff X has only the low bit set. // zext (X == 2) to i32 --> X>>1 iff X has only the 2nd bit set. // zext (X != 0) to i32 --> X iff X has only the low bit set. // zext (X != 0) to i32 --> X>>1 iff X has only the 2nd bit set. // zext (X != 1) to i32 --> X^1 iff X has only the low bit set. // zext (X != 2) to i32 --> (X>>1)^1 iff X has only the 2nd bit set. if ((Op1CV->isNullValue() || Op1CV->isPowerOf2()) && // This only works for EQ and NE ICI->isEquality()) { // If Op1C some other power of two, convert: KnownBits Known = computeKnownBits(ICI->getOperand(0), 0, &CI); APInt KnownZeroMask(~Known.Zero); if (KnownZeroMask.isPowerOf2()) { // Exactly 1 possible 1? if (!DoTransform) return ICI; bool isNE = ICI->getPredicate() == ICmpInst::ICMP_NE; if (!Op1CV->isNullValue() && (*Op1CV != KnownZeroMask)) { // (X&4) == 2 --> false // (X&4) != 2 --> true Constant *Res = ConstantInt::get(CI.getType(), isNE); return replaceInstUsesWith(CI, Res); } uint32_t ShAmt = KnownZeroMask.logBase2(); Value *In = ICI->getOperand(0); if (ShAmt) { // Perform a logical shr by shiftamt. // Insert the shift to put the result in the low bit. In = Builder.CreateLShr(In, ConstantInt::get(In->getType(), ShAmt), In->getName() + ".lobit"); } if (!Op1CV->isNullValue() == isNE) { // Toggle the low bit. Constant *One = ConstantInt::get(In->getType(), 1); In = Builder.CreateXor(In, One); } if (CI.getType() == In->getType()) return replaceInstUsesWith(CI, In); Value *IntCast = Builder.CreateIntCast(In, CI.getType(), false); return replaceInstUsesWith(CI, IntCast); } } } // icmp ne A, B is equal to xor A, B when A and B only really have one bit. // It is also profitable to transform icmp eq into not(xor(A, B)) because that // may lead to additional simplifications. if (ICI->isEquality() && CI.getType() == ICI->getOperand(0)->getType()) { if (IntegerType *ITy = dyn_cast(CI.getType())) { Value *LHS = ICI->getOperand(0); Value *RHS = ICI->getOperand(1); KnownBits KnownLHS = computeKnownBits(LHS, 0, &CI); KnownBits KnownRHS = computeKnownBits(RHS, 0, &CI); if (KnownLHS.Zero == KnownRHS.Zero && KnownLHS.One == KnownRHS.One) { APInt KnownBits = KnownLHS.Zero | KnownLHS.One; APInt UnknownBit = ~KnownBits; if (UnknownBit.countPopulation() == 1) { if (!DoTransform) return ICI; Value *Result = Builder.CreateXor(LHS, RHS); // Mask off any bits that are set and won't be shifted away. if (KnownLHS.One.uge(UnknownBit)) Result = Builder.CreateAnd(Result, ConstantInt::get(ITy, UnknownBit)); // Shift the bit we're testing down to the lsb. Result = Builder.CreateLShr( Result, ConstantInt::get(ITy, UnknownBit.countTrailingZeros())); if (ICI->getPredicate() == ICmpInst::ICMP_EQ) Result = Builder.CreateXor(Result, ConstantInt::get(ITy, 1)); Result->takeName(ICI); return replaceInstUsesWith(CI, Result); } } } } return nullptr; } /// Determine if the specified value can be computed in the specified wider type /// and produce the same low bits. If not, return false. /// /// If this function returns true, it can also return a non-zero number of bits /// (in BitsToClear) which indicates that the value it computes is correct for /// the zero extend, but that the additional BitsToClear bits need to be zero'd /// out. For example, to promote something like: /// /// %B = trunc i64 %A to i32 /// %C = lshr i32 %B, 8 /// %E = zext i32 %C to i64 /// /// CanEvaluateZExtd for the 'lshr' will return true, and BitsToClear will be /// set to 8 to indicate that the promoted value needs to have bits 24-31 /// cleared in addition to bits 32-63. Since an 'and' will be generated to /// clear the top bits anyway, doing this has no extra cost. /// /// This function works on both vectors and scalars. static bool canEvaluateZExtd(Value *V, Type *Ty, unsigned &BitsToClear, InstCombiner &IC, Instruction *CxtI) { BitsToClear = 0; if (canAlwaysEvaluateInType(V, Ty)) return true; if (canNotEvaluateInType(V, Ty)) return false; auto *I = cast(V); unsigned Tmp; switch (I->getOpcode()) { case Instruction::ZExt: // zext(zext(x)) -> zext(x). case Instruction::SExt: // zext(sext(x)) -> sext(x). case Instruction::Trunc: // zext(trunc(x)) -> trunc(x) or zext(x) return true; case Instruction::And: case Instruction::Or: case Instruction::Xor: case Instruction::Add: case Instruction::Sub: case Instruction::Mul: if (!canEvaluateZExtd(I->getOperand(0), Ty, BitsToClear, IC, CxtI) || !canEvaluateZExtd(I->getOperand(1), Ty, Tmp, IC, CxtI)) return false; // These can all be promoted if neither operand has 'bits to clear'. if (BitsToClear == 0 && Tmp == 0) return true; // If the operation is an AND/OR/XOR and the bits to clear are zero in the // other side, BitsToClear is ok. if (Tmp == 0 && I->isBitwiseLogicOp()) { // We use MaskedValueIsZero here for generality, but the case we care // about the most is constant RHS. unsigned VSize = V->getType()->getScalarSizeInBits(); if (IC.MaskedValueIsZero(I->getOperand(1), APInt::getHighBitsSet(VSize, BitsToClear), 0, CxtI)) { // If this is an And instruction and all of the BitsToClear are // known to be zero we can reset BitsToClear. if (I->getOpcode() == Instruction::And) BitsToClear = 0; return true; } } // Otherwise, we don't know how to analyze this BitsToClear case yet. return false; case Instruction::Shl: { // We can promote shl(x, cst) if we can promote x. Since shl overwrites the // upper bits we can reduce BitsToClear by the shift amount. const APInt *Amt; if (match(I->getOperand(1), m_APInt(Amt))) { if (!canEvaluateZExtd(I->getOperand(0), Ty, BitsToClear, IC, CxtI)) return false; uint64_t ShiftAmt = Amt->getZExtValue(); BitsToClear = ShiftAmt < BitsToClear ? BitsToClear - ShiftAmt : 0; return true; } return false; } case Instruction::LShr: { // We can promote lshr(x, cst) if we can promote x. This requires the // ultimate 'and' to clear out the high zero bits we're clearing out though. const APInt *Amt; if (match(I->getOperand(1), m_APInt(Amt))) { if (!canEvaluateZExtd(I->getOperand(0), Ty, BitsToClear, IC, CxtI)) return false; BitsToClear += Amt->getZExtValue(); if (BitsToClear > V->getType()->getScalarSizeInBits()) BitsToClear = V->getType()->getScalarSizeInBits(); return true; } // Cannot promote variable LSHR. return false; } case Instruction::Select: if (!canEvaluateZExtd(I->getOperand(1), Ty, Tmp, IC, CxtI) || !canEvaluateZExtd(I->getOperand(2), Ty, BitsToClear, IC, CxtI) || // TODO: If important, we could handle the case when the BitsToClear are // known zero in the disagreeing side. Tmp != BitsToClear) return false; return true; case Instruction::PHI: { // We can change a phi if we can change all operands. Note that we never // get into trouble with cyclic PHIs here because we only consider // instructions with a single use. PHINode *PN = cast(I); if (!canEvaluateZExtd(PN->getIncomingValue(0), Ty, BitsToClear, IC, CxtI)) return false; for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) if (!canEvaluateZExtd(PN->getIncomingValue(i), Ty, Tmp, IC, CxtI) || // TODO: If important, we could handle the case when the BitsToClear // are known zero in the disagreeing input. Tmp != BitsToClear) return false; return true; } default: // TODO: Can handle more cases here. return false; } } Instruction *InstCombiner::visitZExt(ZExtInst &CI) { // If this zero extend is only used by a truncate, let the truncate be // eliminated before we try to optimize this zext. if (CI.hasOneUse() && isa(CI.user_back())) return nullptr; // If one of the common conversion will work, do it. if (Instruction *Result = commonCastTransforms(CI)) return Result; Value *Src = CI.getOperand(0); Type *SrcTy = Src->getType(), *DestTy = CI.getType(); // Attempt to extend the entire input expression tree to the destination // type. Only do this if the dest type is a simple type, don't convert the // expression tree to something weird like i93 unless the source is also // strange. unsigned BitsToClear; if ((DestTy->isVectorTy() || shouldChangeType(SrcTy, DestTy)) && canEvaluateZExtd(Src, DestTy, BitsToClear, *this, &CI)) { assert(BitsToClear <= SrcTy->getScalarSizeInBits() && "Can't clear more bits than in SrcTy"); // Okay, we can transform this! Insert the new expression now. LLVM_DEBUG( dbgs() << "ICE: EvaluateInDifferentType converting expression type" " to avoid zero extend: " << CI << '\n'); Value *Res = EvaluateInDifferentType(Src, DestTy, false); assert(Res->getType() == DestTy); uint32_t SrcBitsKept = SrcTy->getScalarSizeInBits()-BitsToClear; uint32_t DestBitSize = DestTy->getScalarSizeInBits(); // If the high bits are already filled with zeros, just replace this // cast with the result. if (MaskedValueIsZero(Res, APInt::getHighBitsSet(DestBitSize, DestBitSize-SrcBitsKept), 0, &CI)) return replaceInstUsesWith(CI, Res); // We need to emit an AND to clear the high bits. Constant *C = ConstantInt::get(Res->getType(), APInt::getLowBitsSet(DestBitSize, SrcBitsKept)); return BinaryOperator::CreateAnd(Res, C); } // If this is a TRUNC followed by a ZEXT then we are dealing with integral // types and if the sizes are just right we can convert this into a logical // 'and' which will be much cheaper than the pair of casts. if (TruncInst *CSrc = dyn_cast(Src)) { // A->B->C cast // TODO: Subsume this into EvaluateInDifferentType. // Get the sizes of the types involved. We know that the intermediate type // will be smaller than A or C, but don't know the relation between A and C. Value *A = CSrc->getOperand(0); unsigned SrcSize = A->getType()->getScalarSizeInBits(); unsigned MidSize = CSrc->getType()->getScalarSizeInBits(); unsigned DstSize = CI.getType()->getScalarSizeInBits(); // If we're actually extending zero bits, then if // SrcSize < DstSize: zext(a & mask) // SrcSize == DstSize: a & mask // SrcSize > DstSize: trunc(a) & mask if (SrcSize < DstSize) { APInt AndValue(APInt::getLowBitsSet(SrcSize, MidSize)); Constant *AndConst = ConstantInt::get(A->getType(), AndValue); Value *And = Builder.CreateAnd(A, AndConst, CSrc->getName() + ".mask"); return new ZExtInst(And, CI.getType()); } if (SrcSize == DstSize) { APInt AndValue(APInt::getLowBitsSet(SrcSize, MidSize)); return BinaryOperator::CreateAnd(A, ConstantInt::get(A->getType(), AndValue)); } if (SrcSize > DstSize) { Value *Trunc = Builder.CreateTrunc(A, CI.getType()); APInt AndValue(APInt::getLowBitsSet(DstSize, MidSize)); return BinaryOperator::CreateAnd(Trunc, ConstantInt::get(Trunc->getType(), AndValue)); } } if (ICmpInst *ICI = dyn_cast(Src)) return transformZExtICmp(ICI, CI); BinaryOperator *SrcI = dyn_cast(Src); if (SrcI && SrcI->getOpcode() == Instruction::Or) { // zext (or icmp, icmp) -> or (zext icmp), (zext icmp) if at least one // of the (zext icmp) can be eliminated. If so, immediately perform the // according elimination. ICmpInst *LHS = dyn_cast(SrcI->getOperand(0)); ICmpInst *RHS = dyn_cast(SrcI->getOperand(1)); if (LHS && RHS && LHS->hasOneUse() && RHS->hasOneUse() && (transformZExtICmp(LHS, CI, false) || transformZExtICmp(RHS, CI, false))) { // zext (or icmp, icmp) -> or (zext icmp), (zext icmp) Value *LCast = Builder.CreateZExt(LHS, CI.getType(), LHS->getName()); Value *RCast = Builder.CreateZExt(RHS, CI.getType(), RHS->getName()); BinaryOperator *Or = BinaryOperator::Create(Instruction::Or, LCast, RCast); // Perform the elimination. if (auto *LZExt = dyn_cast(LCast)) transformZExtICmp(LHS, *LZExt); if (auto *RZExt = dyn_cast(RCast)) transformZExtICmp(RHS, *RZExt); return Or; } } // zext(trunc(X) & C) -> (X & zext(C)). Constant *C; Value *X; if (SrcI && match(SrcI, m_OneUse(m_And(m_Trunc(m_Value(X)), m_Constant(C)))) && X->getType() == CI.getType()) return BinaryOperator::CreateAnd(X, ConstantExpr::getZExt(C, CI.getType())); // zext((trunc(X) & C) ^ C) -> ((X & zext(C)) ^ zext(C)). Value *And; if (SrcI && match(SrcI, m_OneUse(m_Xor(m_Value(And), m_Constant(C)))) && match(And, m_OneUse(m_And(m_Trunc(m_Value(X)), m_Specific(C)))) && X->getType() == CI.getType()) { Constant *ZC = ConstantExpr::getZExt(C, CI.getType()); return BinaryOperator::CreateXor(Builder.CreateAnd(X, ZC), ZC); } return nullptr; } /// Transform (sext icmp) to bitwise / integer operations to eliminate the icmp. Instruction *InstCombiner::transformSExtICmp(ICmpInst *ICI, Instruction &CI) { Value *Op0 = ICI->getOperand(0), *Op1 = ICI->getOperand(1); ICmpInst::Predicate Pred = ICI->getPredicate(); // Don't bother if Op1 isn't of vector or integer type. if (!Op1->getType()->isIntOrIntVectorTy()) return nullptr; if (Constant *Op1C = dyn_cast(Op1)) { // (x ashr x, 31 -> all ones if negative // (x >s -1) ? -1 : 0 -> not (ashr x, 31) -> all ones if positive if ((Pred == ICmpInst::ICMP_SLT && Op1C->isNullValue()) || (Pred == ICmpInst::ICMP_SGT && Op1C->isAllOnesValue())) { Value *Sh = ConstantInt::get(Op0->getType(), Op0->getType()->getScalarSizeInBits()-1); Value *In = Builder.CreateAShr(Op0, Sh, Op0->getName() + ".lobit"); if (In->getType() != CI.getType()) In = Builder.CreateIntCast(In, CI.getType(), true /*SExt*/); if (Pred == ICmpInst::ICMP_SGT) In = Builder.CreateNot(In, In->getName() + ".not"); return replaceInstUsesWith(CI, In); } } if (ConstantInt *Op1C = dyn_cast(Op1)) { // If we know that only one bit of the LHS of the icmp can be set and we // have an equality comparison with zero or a power of 2, we can transform // the icmp and sext into bitwise/integer operations. if (ICI->hasOneUse() && ICI->isEquality() && (Op1C->isZero() || Op1C->getValue().isPowerOf2())){ KnownBits Known = computeKnownBits(Op0, 0, &CI); APInt KnownZeroMask(~Known.Zero); if (KnownZeroMask.isPowerOf2()) { Value *In = ICI->getOperand(0); // If the icmp tests for a known zero bit we can constant fold it. if (!Op1C->isZero() && Op1C->getValue() != KnownZeroMask) { Value *V = Pred == ICmpInst::ICMP_NE ? ConstantInt::getAllOnesValue(CI.getType()) : ConstantInt::getNullValue(CI.getType()); return replaceInstUsesWith(CI, V); } if (!Op1C->isZero() == (Pred == ICmpInst::ICMP_NE)) { // sext ((x & 2^n) == 0) -> (x >> n) - 1 // sext ((x & 2^n) != 2^n) -> (x >> n) - 1 unsigned ShiftAmt = KnownZeroMask.countTrailingZeros(); // Perform a right shift to place the desired bit in the LSB. if (ShiftAmt) In = Builder.CreateLShr(In, ConstantInt::get(In->getType(), ShiftAmt)); // At this point "In" is either 1 or 0. Subtract 1 to turn // {1, 0} -> {0, -1}. In = Builder.CreateAdd(In, ConstantInt::getAllOnesValue(In->getType()), "sext"); } else { // sext ((x & 2^n) != 0) -> (x << bitwidth-n) a>> bitwidth-1 // sext ((x & 2^n) == 2^n) -> (x << bitwidth-n) a>> bitwidth-1 unsigned ShiftAmt = KnownZeroMask.countLeadingZeros(); // Perform a left shift to place the desired bit in the MSB. if (ShiftAmt) In = Builder.CreateShl(In, ConstantInt::get(In->getType(), ShiftAmt)); // Distribute the bit over the whole bit width. In = Builder.CreateAShr(In, ConstantInt::get(In->getType(), KnownZeroMask.getBitWidth() - 1), "sext"); } if (CI.getType() == In->getType()) return replaceInstUsesWith(CI, In); return CastInst::CreateIntegerCast(In, CI.getType(), true/*SExt*/); } } } return nullptr; } /// Return true if we can take the specified value and return it as type Ty /// without inserting any new casts and without changing the value of the common /// low bits. This is used by code that tries to promote integer operations to /// a wider types will allow us to eliminate the extension. /// /// This function works on both vectors and scalars. /// static bool canEvaluateSExtd(Value *V, Type *Ty) { assert(V->getType()->getScalarSizeInBits() < Ty->getScalarSizeInBits() && "Can't sign extend type to a smaller type"); if (canAlwaysEvaluateInType(V, Ty)) return true; if (canNotEvaluateInType(V, Ty)) return false; auto *I = cast(V); switch (I->getOpcode()) { case Instruction::SExt: // sext(sext(x)) -> sext(x) case Instruction::ZExt: // sext(zext(x)) -> zext(x) case Instruction::Trunc: // sext(trunc(x)) -> trunc(x) or sext(x) return true; case Instruction::And: case Instruction::Or: case Instruction::Xor: case Instruction::Add: case Instruction::Sub: case Instruction::Mul: // These operators can all arbitrarily be extended if their inputs can. return canEvaluateSExtd(I->getOperand(0), Ty) && canEvaluateSExtd(I->getOperand(1), Ty); //case Instruction::Shl: TODO //case Instruction::LShr: TODO case Instruction::Select: return canEvaluateSExtd(I->getOperand(1), Ty) && canEvaluateSExtd(I->getOperand(2), Ty); case Instruction::PHI: { // We can change a phi if we can change all operands. Note that we never // get into trouble with cyclic PHIs here because we only consider // instructions with a single use. PHINode *PN = cast(I); for (Value *IncValue : PN->incoming_values()) if (!canEvaluateSExtd(IncValue, Ty)) return false; return true; } default: // TODO: Can handle more cases here. break; } return false; } Instruction *InstCombiner::visitSExt(SExtInst &CI) { // If this sign extend is only used by a truncate, let the truncate be // eliminated before we try to optimize this sext. if (CI.hasOneUse() && isa(CI.user_back())) return nullptr; if (Instruction *I = commonCastTransforms(CI)) return I; Value *Src = CI.getOperand(0); Type *SrcTy = Src->getType(), *DestTy = CI.getType(); // If we know that the value being extended is positive, we can use a zext // instead. KnownBits Known = computeKnownBits(Src, 0, &CI); if (Known.isNonNegative()) { Value *ZExt = Builder.CreateZExt(Src, DestTy); return replaceInstUsesWith(CI, ZExt); } // Attempt to extend the entire input expression tree to the destination // type. Only do this if the dest type is a simple type, don't convert the // expression tree to something weird like i93 unless the source is also // strange. if ((DestTy->isVectorTy() || shouldChangeType(SrcTy, DestTy)) && canEvaluateSExtd(Src, DestTy)) { // Okay, we can transform this! Insert the new expression now. LLVM_DEBUG( dbgs() << "ICE: EvaluateInDifferentType converting expression type" " to avoid sign extend: " << CI << '\n'); Value *Res = EvaluateInDifferentType(Src, DestTy, true); assert(Res->getType() == DestTy); uint32_t SrcBitSize = SrcTy->getScalarSizeInBits(); uint32_t DestBitSize = DestTy->getScalarSizeInBits(); // If the high bits are already filled with sign bit, just replace this // cast with the result. if (ComputeNumSignBits(Res, 0, &CI) > DestBitSize - SrcBitSize) return replaceInstUsesWith(CI, Res); // We need to emit a shl + ashr to do the sign extend. Value *ShAmt = ConstantInt::get(DestTy, DestBitSize-SrcBitSize); return BinaryOperator::CreateAShr(Builder.CreateShl(Res, ShAmt, "sext"), ShAmt); } // If the input is a trunc from the destination type, then turn sext(trunc(x)) // into shifts. Value *X; if (match(Src, m_OneUse(m_Trunc(m_Value(X)))) && X->getType() == DestTy) { // sext(trunc(X)) --> ashr(shl(X, C), C) unsigned SrcBitSize = SrcTy->getScalarSizeInBits(); unsigned DestBitSize = DestTy->getScalarSizeInBits(); Constant *ShAmt = ConstantInt::get(DestTy, DestBitSize - SrcBitSize); return BinaryOperator::CreateAShr(Builder.CreateShl(X, ShAmt), ShAmt); } if (ICmpInst *ICI = dyn_cast(Src)) return transformSExtICmp(ICI, CI); // If the input is a shl/ashr pair of a same constant, then this is a sign // extension from a smaller value. If we could trust arbitrary bitwidth // integers, we could turn this into a truncate to the smaller bit and then // use a sext for the whole extension. Since we don't, look deeper and check // for a truncate. If the source and dest are the same type, eliminate the // trunc and extend and just do shifts. For example, turn: // %a = trunc i32 %i to i8 // %b = shl i8 %a, 6 // %c = ashr i8 %b, 6 // %d = sext i8 %c to i32 // into: // %a = shl i32 %i, 30 // %d = ashr i32 %a, 30 Value *A = nullptr; // TODO: Eventually this could be subsumed by EvaluateInDifferentType. ConstantInt *BA = nullptr, *CA = nullptr; if (match(Src, m_AShr(m_Shl(m_Trunc(m_Value(A)), m_ConstantInt(BA)), m_ConstantInt(CA))) && BA == CA && A->getType() == CI.getType()) { unsigned MidSize = Src->getType()->getScalarSizeInBits(); unsigned SrcDstSize = CI.getType()->getScalarSizeInBits(); unsigned ShAmt = CA->getZExtValue()+SrcDstSize-MidSize; Constant *ShAmtV = ConstantInt::get(CI.getType(), ShAmt); A = Builder.CreateShl(A, ShAmtV, CI.getName()); return BinaryOperator::CreateAShr(A, ShAmtV); } return nullptr; } /// Return a Constant* for the specified floating-point constant if it fits /// in the specified FP type without changing its value. static bool fitsInFPType(ConstantFP *CFP, const fltSemantics &Sem) { bool losesInfo; APFloat F = CFP->getValueAPF(); (void)F.convert(Sem, APFloat::rmNearestTiesToEven, &losesInfo); return !losesInfo; } static Type *shrinkFPConstant(ConstantFP *CFP) { if (CFP->getType() == Type::getPPC_FP128Ty(CFP->getContext())) return nullptr; // No constant folding of this. // See if the value can be truncated to half and then reextended. if (fitsInFPType(CFP, APFloat::IEEEhalf())) return Type::getHalfTy(CFP->getContext()); // See if the value can be truncated to float and then reextended. if (fitsInFPType(CFP, APFloat::IEEEsingle())) return Type::getFloatTy(CFP->getContext()); if (CFP->getType()->isDoubleTy()) return nullptr; // Won't shrink. if (fitsInFPType(CFP, APFloat::IEEEdouble())) return Type::getDoubleTy(CFP->getContext()); // Don't try to shrink to various long double types. return nullptr; } // Determine if this is a vector of ConstantFPs and if so, return the minimal // type we can safely truncate all elements to. // TODO: Make these support undef elements. static Type *shrinkFPConstantVector(Value *V) { auto *CV = dyn_cast(V); if (!CV || !CV->getType()->isVectorTy()) return nullptr; Type *MinType = nullptr; unsigned NumElts = CV->getType()->getVectorNumElements(); for (unsigned i = 0; i != NumElts; ++i) { auto *CFP = dyn_cast_or_null(CV->getAggregateElement(i)); if (!CFP) return nullptr; Type *T = shrinkFPConstant(CFP); if (!T) return nullptr; // If we haven't found a type yet or this type has a larger mantissa than // our previous type, this is our new minimal type. if (!MinType || T->getFPMantissaWidth() > MinType->getFPMantissaWidth()) MinType = T; } // Make a vector type from the minimal type. return VectorType::get(MinType, NumElts); } /// Find the minimum FP type we can safely truncate to. static Type *getMinimumFPType(Value *V) { if (auto *FPExt = dyn_cast(V)) return FPExt->getOperand(0)->getType(); // If this value is a constant, return the constant in the smallest FP type // that can accurately represent it. This allows us to turn // (float)((double)X+2.0) into x+2.0f. if (auto *CFP = dyn_cast(V)) if (Type *T = shrinkFPConstant(CFP)) return T; // Try to shrink a vector of FP constants. if (Type *T = shrinkFPConstantVector(V)) return T; return V->getType(); } Instruction *InstCombiner::visitFPTrunc(FPTruncInst &FPT) { if (Instruction *I = commonCastTransforms(FPT)) return I; // If we have fptrunc(OpI (fpextend x), (fpextend y)), we would like to // simplify this expression to avoid one or more of the trunc/extend // operations if we can do so without changing the numerical results. // // The exact manner in which the widths of the operands interact to limit // what we can and cannot do safely varies from operation to operation, and // is explained below in the various case statements. Type *Ty = FPT.getType(); BinaryOperator *OpI = dyn_cast(FPT.getOperand(0)); if (OpI && OpI->hasOneUse()) { Type *LHSMinType = getMinimumFPType(OpI->getOperand(0)); Type *RHSMinType = getMinimumFPType(OpI->getOperand(1)); unsigned OpWidth = OpI->getType()->getFPMantissaWidth(); unsigned LHSWidth = LHSMinType->getFPMantissaWidth(); unsigned RHSWidth = RHSMinType->getFPMantissaWidth(); unsigned SrcWidth = std::max(LHSWidth, RHSWidth); unsigned DstWidth = Ty->getFPMantissaWidth(); switch (OpI->getOpcode()) { default: break; case Instruction::FAdd: case Instruction::FSub: // For addition and subtraction, the infinitely precise result can // essentially be arbitrarily wide; proving that double rounding // will not occur because the result of OpI is exact (as we will for // FMul, for example) is hopeless. However, we *can* nonetheless // frequently know that double rounding cannot occur (or that it is // innocuous) by taking advantage of the specific structure of // infinitely-precise results that admit double rounding. // // Specifically, if OpWidth >= 2*DstWdith+1 and DstWidth is sufficient // to represent both sources, we can guarantee that the double // rounding is innocuous (See p50 of Figueroa's 2000 PhD thesis, // "A Rigorous Framework for Fully Supporting the IEEE Standard ..." // for proof of this fact). // // Note: Figueroa does not consider the case where DstFormat != // SrcFormat. It's possible (likely even!) that this analysis // could be tightened for those cases, but they are rare (the main // case of interest here is (float)((double)float + float)). if (OpWidth >= 2*DstWidth+1 && DstWidth >= SrcWidth) { Value *LHS = Builder.CreateFPTrunc(OpI->getOperand(0), Ty); Value *RHS = Builder.CreateFPTrunc(OpI->getOperand(1), Ty); Instruction *RI = BinaryOperator::Create(OpI->getOpcode(), LHS, RHS); RI->copyFastMathFlags(OpI); return RI; } break; case Instruction::FMul: // For multiplication, the infinitely precise result has at most // LHSWidth + RHSWidth significant bits; if OpWidth is sufficient // that such a value can be exactly represented, then no double // rounding can possibly occur; we can safely perform the operation // in the destination format if it can represent both sources. if (OpWidth >= LHSWidth + RHSWidth && DstWidth >= SrcWidth) { Value *LHS = Builder.CreateFPTrunc(OpI->getOperand(0), Ty); Value *RHS = Builder.CreateFPTrunc(OpI->getOperand(1), Ty); return BinaryOperator::CreateFMulFMF(LHS, RHS, OpI); } break; case Instruction::FDiv: // For division, we use again use the bound from Figueroa's // dissertation. I am entirely certain that this bound can be // tightened in the unbalanced operand case by an analysis based on // the diophantine rational approximation bound, but the well-known // condition used here is a good conservative first pass. // TODO: Tighten bound via rigorous analysis of the unbalanced case. if (OpWidth >= 2*DstWidth && DstWidth >= SrcWidth) { Value *LHS = Builder.CreateFPTrunc(OpI->getOperand(0), Ty); Value *RHS = Builder.CreateFPTrunc(OpI->getOperand(1), Ty); return BinaryOperator::CreateFDivFMF(LHS, RHS, OpI); } break; case Instruction::FRem: { // Remainder is straightforward. Remainder is always exact, so the // type of OpI doesn't enter into things at all. We simply evaluate // in whichever source type is larger, then convert to the // destination type. if (SrcWidth == OpWidth) break; Value *LHS, *RHS; if (LHSWidth == SrcWidth) { LHS = Builder.CreateFPTrunc(OpI->getOperand(0), LHSMinType); RHS = Builder.CreateFPTrunc(OpI->getOperand(1), LHSMinType); } else { LHS = Builder.CreateFPTrunc(OpI->getOperand(0), RHSMinType); RHS = Builder.CreateFPTrunc(OpI->getOperand(1), RHSMinType); } Value *ExactResult = Builder.CreateFRemFMF(LHS, RHS, OpI); return CastInst::CreateFPCast(ExactResult, Ty); } } // (fptrunc (fneg x)) -> (fneg (fptrunc x)) if (BinaryOperator::isFNeg(OpI)) { Value *InnerTrunc = Builder.CreateFPTrunc(OpI->getOperand(1), Ty); return BinaryOperator::CreateFNegFMF(InnerTrunc, OpI); } } if (auto *II = dyn_cast(FPT.getOperand(0))) { switch (II->getIntrinsicID()) { default: break; case Intrinsic::ceil: case Intrinsic::fabs: case Intrinsic::floor: case Intrinsic::nearbyint: case Intrinsic::rint: case Intrinsic::round: case Intrinsic::trunc: { Value *Src = II->getArgOperand(0); if (!Src->hasOneUse()) break; // Except for fabs, this transformation requires the input of the unary FP // operation to be itself an fpext from the type to which we're // truncating. if (II->getIntrinsicID() != Intrinsic::fabs) { FPExtInst *FPExtSrc = dyn_cast(Src); if (!FPExtSrc || FPExtSrc->getSrcTy() != Ty) break; } // Do unary FP operation on smaller type. // (fptrunc (fabs x)) -> (fabs (fptrunc x)) Value *InnerTrunc = Builder.CreateFPTrunc(Src, Ty); Function *Overload = Intrinsic::getDeclaration(FPT.getModule(), II->getIntrinsicID(), Ty); SmallVector OpBundles; II->getOperandBundlesAsDefs(OpBundles); CallInst *NewCI = CallInst::Create(Overload, { InnerTrunc }, OpBundles, II->getName()); NewCI->copyFastMathFlags(II); return NewCI; } } } if (Instruction *I = shrinkInsertElt(FPT, Builder)) return I; return nullptr; } Instruction *InstCombiner::visitFPExt(CastInst &CI) { return commonCastTransforms(CI); } // fpto{s/u}i({u/s}itofp(X)) --> X or zext(X) or sext(X) or trunc(X) // This is safe if the intermediate type has enough bits in its mantissa to // accurately represent all values of X. For example, this won't work with // i64 -> float -> i64. Instruction *InstCombiner::FoldItoFPtoI(Instruction &FI) { if (!isa(FI.getOperand(0)) && !isa(FI.getOperand(0))) return nullptr; Instruction *OpI = cast(FI.getOperand(0)); Value *SrcI = OpI->getOperand(0); Type *FITy = FI.getType(); Type *OpITy = OpI->getType(); Type *SrcTy = SrcI->getType(); bool IsInputSigned = isa(OpI); bool IsOutputSigned = isa(FI); // We can safely assume the conversion won't overflow the output range, // because (for example) (uint8_t)18293.f is undefined behavior. // Since we can assume the conversion won't overflow, our decision as to // whether the input will fit in the float should depend on the minimum // of the input range and output range. // This means this is also safe for a signed input and unsigned output, since // a negative input would lead to undefined behavior. int InputSize = (int)SrcTy->getScalarSizeInBits() - IsInputSigned; int OutputSize = (int)FITy->getScalarSizeInBits() - IsOutputSigned; int ActualSize = std::min(InputSize, OutputSize); if (ActualSize <= OpITy->getFPMantissaWidth()) { if (FITy->getScalarSizeInBits() > SrcTy->getScalarSizeInBits()) { if (IsInputSigned && IsOutputSigned) return new SExtInst(SrcI, FITy); return new ZExtInst(SrcI, FITy); } if (FITy->getScalarSizeInBits() < SrcTy->getScalarSizeInBits()) return new TruncInst(SrcI, FITy); if (SrcTy == FITy) return replaceInstUsesWith(FI, SrcI); return new BitCastInst(SrcI, FITy); } return nullptr; } Instruction *InstCombiner::visitFPToUI(FPToUIInst &FI) { Instruction *OpI = dyn_cast(FI.getOperand(0)); if (!OpI) return commonCastTransforms(FI); if (Instruction *I = FoldItoFPtoI(FI)) return I; return commonCastTransforms(FI); } Instruction *InstCombiner::visitFPToSI(FPToSIInst &FI) { Instruction *OpI = dyn_cast(FI.getOperand(0)); if (!OpI) return commonCastTransforms(FI); if (Instruction *I = FoldItoFPtoI(FI)) return I; return commonCastTransforms(FI); } Instruction *InstCombiner::visitUIToFP(CastInst &CI) { return commonCastTransforms(CI); } Instruction *InstCombiner::visitSIToFP(CastInst &CI) { return commonCastTransforms(CI); } Instruction *InstCombiner::visitIntToPtr(IntToPtrInst &CI) { // If the source integer type is not the intptr_t type for this target, do a // trunc or zext to the intptr_t type, then inttoptr of it. This allows the // cast to be exposed to other transforms. unsigned AS = CI.getAddressSpace(); if (CI.getOperand(0)->getType()->getScalarSizeInBits() != DL.getPointerSizeInBits(AS)) { Type *Ty = DL.getIntPtrType(CI.getContext(), AS); if (CI.getType()->isVectorTy()) // Handle vectors of pointers. Ty = VectorType::get(Ty, CI.getType()->getVectorNumElements()); Value *P = Builder.CreateZExtOrTrunc(CI.getOperand(0), Ty); return new IntToPtrInst(P, CI.getType()); } if (Instruction *I = commonCastTransforms(CI)) return I; return nullptr; } /// Implement the transforms for cast of pointer (bitcast/ptrtoint) Instruction *InstCombiner::commonPointerCastTransforms(CastInst &CI) { Value *Src = CI.getOperand(0); if (GetElementPtrInst *GEP = dyn_cast(Src)) { // If casting the result of a getelementptr instruction with no offset, turn // this into a cast of the original pointer! if (GEP->hasAllZeroIndices() && // If CI is an addrspacecast and GEP changes the poiner type, merging // GEP into CI would undo canonicalizing addrspacecast with different // pointer types, causing infinite loops. (!isa(CI) || GEP->getType() == GEP->getPointerOperandType())) { // Changing the cast operand is usually not a good idea but it is safe // here because the pointer operand is being replaced with another // pointer operand so the opcode doesn't need to change. Worklist.Add(GEP); CI.setOperand(0, GEP->getOperand(0)); return &CI; } } return commonCastTransforms(CI); } Instruction *InstCombiner::visitPtrToInt(PtrToIntInst &CI) { // If the destination integer type is not the intptr_t type for this target, // do a ptrtoint to intptr_t then do a trunc or zext. This allows the cast // to be exposed to other transforms. Type *Ty = CI.getType(); unsigned AS = CI.getPointerAddressSpace(); if (Ty->getScalarSizeInBits() == DL.getIndexSizeInBits(AS)) return commonPointerCastTransforms(CI); Type *PtrTy = DL.getIntPtrType(CI.getContext(), AS); if (Ty->isVectorTy()) // Handle vectors of pointers. PtrTy = VectorType::get(PtrTy, Ty->getVectorNumElements()); Value *P = Builder.CreatePtrToInt(CI.getOperand(0), PtrTy); return CastInst::CreateIntegerCast(P, Ty, /*isSigned=*/false); } /// This input value (which is known to have vector type) is being zero extended /// or truncated to the specified vector type. /// Try to replace it with a shuffle (and vector/vector bitcast) if possible. /// /// The source and destination vector types may have different element types. static Instruction *optimizeVectorResize(Value *InVal, VectorType *DestTy, InstCombiner &IC) { // We can only do this optimization if the output is a multiple of the input // element size, or the input is a multiple of the output element size. // Convert the input type to have the same element type as the output. VectorType *SrcTy = cast(InVal->getType()); if (SrcTy->getElementType() != DestTy->getElementType()) { // The input types don't need to be identical, but for now they must be the // same size. There is no specific reason we couldn't handle things like // <4 x i16> -> <4 x i32> by bitcasting to <2 x i32> but haven't gotten // there yet. if (SrcTy->getElementType()->getPrimitiveSizeInBits() != DestTy->getElementType()->getPrimitiveSizeInBits()) return nullptr; SrcTy = VectorType::get(DestTy->getElementType(), SrcTy->getNumElements()); InVal = IC.Builder.CreateBitCast(InVal, SrcTy); } // Now that the element types match, get the shuffle mask and RHS of the // shuffle to use, which depends on whether we're increasing or decreasing the // size of the input. SmallVector ShuffleMask; Value *V2; if (SrcTy->getNumElements() > DestTy->getNumElements()) { // If we're shrinking the number of elements, just shuffle in the low // elements from the input and use undef as the second shuffle input. V2 = UndefValue::get(SrcTy); for (unsigned i = 0, e = DestTy->getNumElements(); i != e; ++i) ShuffleMask.push_back(i); } else { // If we're increasing the number of elements, shuffle in all of the // elements from InVal and fill the rest of the result elements with zeros // from a constant zero. V2 = Constant::getNullValue(SrcTy); unsigned SrcElts = SrcTy->getNumElements(); for (unsigned i = 0, e = SrcElts; i != e; ++i) ShuffleMask.push_back(i); // The excess elements reference the first element of the zero input. for (unsigned i = 0, e = DestTy->getNumElements()-SrcElts; i != e; ++i) ShuffleMask.push_back(SrcElts); } return new ShuffleVectorInst(InVal, V2, ConstantDataVector::get(V2->getContext(), ShuffleMask)); } static bool isMultipleOfTypeSize(unsigned Value, Type *Ty) { return Value % Ty->getPrimitiveSizeInBits() == 0; } static unsigned getTypeSizeIndex(unsigned Value, Type *Ty) { return Value / Ty->getPrimitiveSizeInBits(); } /// V is a value which is inserted into a vector of VecEltTy. /// Look through the value to see if we can decompose it into /// insertions into the vector. See the example in the comment for /// OptimizeIntegerToVectorInsertions for the pattern this handles. /// The type of V is always a non-zero multiple of VecEltTy's size. /// Shift is the number of bits between the lsb of V and the lsb of /// the vector. /// /// This returns false if the pattern can't be matched or true if it can, /// filling in Elements with the elements found here. static bool collectInsertionElements(Value *V, unsigned Shift, SmallVectorImpl &Elements, Type *VecEltTy, bool isBigEndian) { assert(isMultipleOfTypeSize(Shift, VecEltTy) && "Shift should be a multiple of the element type size"); // Undef values never contribute useful bits to the result. if (isa(V)) return true; // If we got down to a value of the right type, we win, try inserting into the // right element. if (V->getType() == VecEltTy) { // Inserting null doesn't actually insert any elements. if (Constant *C = dyn_cast(V)) if (C->isNullValue()) return true; unsigned ElementIndex = getTypeSizeIndex(Shift, VecEltTy); if (isBigEndian) ElementIndex = Elements.size() - ElementIndex - 1; // Fail if multiple elements are inserted into this slot. if (Elements[ElementIndex]) return false; Elements[ElementIndex] = V; return true; } if (Constant *C = dyn_cast(V)) { // Figure out the # elements this provides, and bitcast it or slice it up // as required. unsigned NumElts = getTypeSizeIndex(C->getType()->getPrimitiveSizeInBits(), VecEltTy); // If the constant is the size of a vector element, we just need to bitcast // it to the right type so it gets properly inserted. if (NumElts == 1) return collectInsertionElements(ConstantExpr::getBitCast(C, VecEltTy), Shift, Elements, VecEltTy, isBigEndian); // Okay, this is a constant that covers multiple elements. Slice it up into // pieces and insert each element-sized piece into the vector. if (!isa(C->getType())) C = ConstantExpr::getBitCast(C, IntegerType::get(V->getContext(), C->getType()->getPrimitiveSizeInBits())); unsigned ElementSize = VecEltTy->getPrimitiveSizeInBits(); Type *ElementIntTy = IntegerType::get(C->getContext(), ElementSize); for (unsigned i = 0; i != NumElts; ++i) { unsigned ShiftI = Shift+i*ElementSize; Constant *Piece = ConstantExpr::getLShr(C, ConstantInt::get(C->getType(), ShiftI)); Piece = ConstantExpr::getTrunc(Piece, ElementIntTy); if (!collectInsertionElements(Piece, ShiftI, Elements, VecEltTy, isBigEndian)) return false; } return true; } if (!V->hasOneUse()) return false; Instruction *I = dyn_cast(V); if (!I) return false; switch (I->getOpcode()) { default: return false; // Unhandled case. case Instruction::BitCast: return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy, isBigEndian); case Instruction::ZExt: if (!isMultipleOfTypeSize( I->getOperand(0)->getType()->getPrimitiveSizeInBits(), VecEltTy)) return false; return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy, isBigEndian); case Instruction::Or: return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy, isBigEndian) && collectInsertionElements(I->getOperand(1), Shift, Elements, VecEltTy, isBigEndian); case Instruction::Shl: { // Must be shifting by a constant that is a multiple of the element size. ConstantInt *CI = dyn_cast(I->getOperand(1)); if (!CI) return false; Shift += CI->getZExtValue(); if (!isMultipleOfTypeSize(Shift, VecEltTy)) return false; return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy, isBigEndian); } } } /// If the input is an 'or' instruction, we may be doing shifts and ors to /// assemble the elements of the vector manually. /// Try to rip the code out and replace it with insertelements. This is to /// optimize code like this: /// /// %tmp37 = bitcast float %inc to i32 /// %tmp38 = zext i32 %tmp37 to i64 /// %tmp31 = bitcast float %inc5 to i32 /// %tmp32 = zext i32 %tmp31 to i64 /// %tmp33 = shl i64 %tmp32, 32 /// %ins35 = or i64 %tmp33, %tmp38 /// %tmp43 = bitcast i64 %ins35 to <2 x float> /// /// Into two insertelements that do "buildvector{%inc, %inc5}". static Value *optimizeIntegerToVectorInsertions(BitCastInst &CI, InstCombiner &IC) { VectorType *DestVecTy = cast(CI.getType()); Value *IntInput = CI.getOperand(0); SmallVector Elements(DestVecTy->getNumElements()); if (!collectInsertionElements(IntInput, 0, Elements, DestVecTy->getElementType(), IC.getDataLayout().isBigEndian())) return nullptr; // If we succeeded, we know that all of the element are specified by Elements // or are zero if Elements has a null entry. Recast this as a set of // insertions. Value *Result = Constant::getNullValue(CI.getType()); for (unsigned i = 0, e = Elements.size(); i != e; ++i) { if (!Elements[i]) continue; // Unset element. Result = IC.Builder.CreateInsertElement(Result, Elements[i], IC.Builder.getInt32(i)); } return Result; } /// Canonicalize scalar bitcasts of extracted elements into a bitcast of the /// vector followed by extract element. The backend tends to handle bitcasts of /// vectors better than bitcasts of scalars because vector registers are /// usually not type-specific like scalar integer or scalar floating-point. static Instruction *canonicalizeBitCastExtElt(BitCastInst &BitCast, InstCombiner &IC) { // TODO: Create and use a pattern matcher for ExtractElementInst. auto *ExtElt = dyn_cast(BitCast.getOperand(0)); if (!ExtElt || !ExtElt->hasOneUse()) return nullptr; // The bitcast must be to a vectorizable type, otherwise we can't make a new // type to extract from. Type *DestType = BitCast.getType(); if (!VectorType::isValidElementType(DestType)) return nullptr; unsigned NumElts = ExtElt->getVectorOperandType()->getNumElements(); auto *NewVecType = VectorType::get(DestType, NumElts); auto *NewBC = IC.Builder.CreateBitCast(ExtElt->getVectorOperand(), NewVecType, "bc"); return ExtractElementInst::Create(NewBC, ExtElt->getIndexOperand()); } /// Change the type of a bitwise logic operation if we can eliminate a bitcast. static Instruction *foldBitCastBitwiseLogic(BitCastInst &BitCast, InstCombiner::BuilderTy &Builder) { Type *DestTy = BitCast.getType(); BinaryOperator *BO; if (!DestTy->isIntOrIntVectorTy() || !match(BitCast.getOperand(0), m_OneUse(m_BinOp(BO))) || !BO->isBitwiseLogicOp()) return nullptr; // FIXME: This transform is restricted to vector types to avoid backend // problems caused by creating potentially illegal operations. If a fix-up is // added to handle that situation, we can remove this check. if (!DestTy->isVectorTy() || !BO->getType()->isVectorTy()) return nullptr; Value *X; if (match(BO->getOperand(0), m_OneUse(m_BitCast(m_Value(X)))) && X->getType() == DestTy && !isa(X)) { // bitcast(logic(bitcast(X), Y)) --> logic'(X, bitcast(Y)) Value *CastedOp1 = Builder.CreateBitCast(BO->getOperand(1), DestTy); return BinaryOperator::Create(BO->getOpcode(), X, CastedOp1); } if (match(BO->getOperand(1), m_OneUse(m_BitCast(m_Value(X)))) && X->getType() == DestTy && !isa(X)) { // bitcast(logic(Y, bitcast(X))) --> logic'(bitcast(Y), X) Value *CastedOp0 = Builder.CreateBitCast(BO->getOperand(0), DestTy); return BinaryOperator::Create(BO->getOpcode(), CastedOp0, X); } // Canonicalize vector bitcasts to come before vector bitwise logic with a // constant. This eases recognition of special constants for later ops. // Example: // icmp u/s (a ^ signmask), (b ^ signmask) --> icmp s/u a, b Constant *C; if (match(BO->getOperand(1), m_Constant(C))) { // bitcast (logic X, C) --> logic (bitcast X, C') Value *CastedOp0 = Builder.CreateBitCast(BO->getOperand(0), DestTy); Value *CastedC = ConstantExpr::getBitCast(C, DestTy); return BinaryOperator::Create(BO->getOpcode(), CastedOp0, CastedC); } return nullptr; } /// Change the type of a select if we can eliminate a bitcast. static Instruction *foldBitCastSelect(BitCastInst &BitCast, InstCombiner::BuilderTy &Builder) { Value *Cond, *TVal, *FVal; if (!match(BitCast.getOperand(0), m_OneUse(m_Select(m_Value(Cond), m_Value(TVal), m_Value(FVal))))) return nullptr; // A vector select must maintain the same number of elements in its operands. Type *CondTy = Cond->getType(); Type *DestTy = BitCast.getType(); if (CondTy->isVectorTy()) { if (!DestTy->isVectorTy()) return nullptr; if (DestTy->getVectorNumElements() != CondTy->getVectorNumElements()) return nullptr; } // FIXME: This transform is restricted from changing the select between // scalars and vectors to avoid backend problems caused by creating // potentially illegal operations. If a fix-up is added to handle that // situation, we can remove this check. if (DestTy->isVectorTy() != TVal->getType()->isVectorTy()) return nullptr; auto *Sel = cast(BitCast.getOperand(0)); Value *X; if (match(TVal, m_OneUse(m_BitCast(m_Value(X)))) && X->getType() == DestTy && !isa(X)) { // bitcast(select(Cond, bitcast(X), Y)) --> select'(Cond, X, bitcast(Y)) Value *CastedVal = Builder.CreateBitCast(FVal, DestTy); return SelectInst::Create(Cond, X, CastedVal, "", nullptr, Sel); } if (match(FVal, m_OneUse(m_BitCast(m_Value(X)))) && X->getType() == DestTy && !isa(X)) { // bitcast(select(Cond, Y, bitcast(X))) --> select'(Cond, bitcast(Y), X) Value *CastedVal = Builder.CreateBitCast(TVal, DestTy); return SelectInst::Create(Cond, CastedVal, X, "", nullptr, Sel); } return nullptr; } /// Check if all users of CI are StoreInsts. static bool hasStoreUsersOnly(CastInst &CI) { for (User *U : CI.users()) { if (!isa(U)) return false; } return true; } /// This function handles following case /// /// A -> B cast /// PHI /// B -> A cast /// /// All the related PHI nodes can be replaced by new PHI nodes with type A. /// The uses of \p CI can be changed to the new PHI node corresponding to \p PN. Instruction *InstCombiner::optimizeBitCastFromPhi(CastInst &CI, PHINode *PN) { // BitCast used by Store can be handled in InstCombineLoadStoreAlloca.cpp. if (hasStoreUsersOnly(CI)) return nullptr; Value *Src = CI.getOperand(0); Type *SrcTy = Src->getType(); // Type B Type *DestTy = CI.getType(); // Type A SmallVector PhiWorklist; SmallSetVector OldPhiNodes; // Find all of the A->B casts and PHI nodes. // We need to inpect all related PHI nodes, but PHIs can be cyclic, so // OldPhiNodes is used to track all known PHI nodes, before adding a new // PHI to PhiWorklist, it is checked against and added to OldPhiNodes first. PhiWorklist.push_back(PN); OldPhiNodes.insert(PN); while (!PhiWorklist.empty()) { auto *OldPN = PhiWorklist.pop_back_val(); for (Value *IncValue : OldPN->incoming_values()) { if (isa(IncValue)) continue; if (auto *LI = dyn_cast(IncValue)) { // If there is a sequence of one or more load instructions, each loaded // value is used as address of later load instruction, bitcast is // necessary to change the value type, don't optimize it. For // simplicity we give up if the load address comes from another load. Value *Addr = LI->getOperand(0); if (Addr == &CI || isa(Addr)) return nullptr; if (LI->hasOneUse() && LI->isSimple()) continue; // If a LoadInst has more than one use, changing the type of loaded // value may create another bitcast. return nullptr; } if (auto *PNode = dyn_cast(IncValue)) { if (OldPhiNodes.insert(PNode)) PhiWorklist.push_back(PNode); continue; } auto *BCI = dyn_cast(IncValue); // We can't handle other instructions. if (!BCI) return nullptr; // Verify it's a A->B cast. Type *TyA = BCI->getOperand(0)->getType(); Type *TyB = BCI->getType(); if (TyA != DestTy || TyB != SrcTy) return nullptr; } } // For each old PHI node, create a corresponding new PHI node with a type A. SmallDenseMap NewPNodes; for (auto *OldPN : OldPhiNodes) { Builder.SetInsertPoint(OldPN); PHINode *NewPN = Builder.CreatePHI(DestTy, OldPN->getNumOperands()); NewPNodes[OldPN] = NewPN; } // Fill in the operands of new PHI nodes. for (auto *OldPN : OldPhiNodes) { PHINode *NewPN = NewPNodes[OldPN]; for (unsigned j = 0, e = OldPN->getNumOperands(); j != e; ++j) { Value *V = OldPN->getOperand(j); Value *NewV = nullptr; if (auto *C = dyn_cast(V)) { NewV = ConstantExpr::getBitCast(C, DestTy); } else if (auto *LI = dyn_cast(V)) { Builder.SetInsertPoint(LI->getNextNode()); NewV = Builder.CreateBitCast(LI, DestTy); Worklist.Add(LI); } else if (auto *BCI = dyn_cast(V)) { NewV = BCI->getOperand(0); } else if (auto *PrevPN = dyn_cast(V)) { NewV = NewPNodes[PrevPN]; } assert(NewV); NewPN->addIncoming(NewV, OldPN->getIncomingBlock(j)); } } // If there is a store with type B, change it to type A. for (User *U : PN->users()) { auto *SI = dyn_cast(U); if (SI && SI->isSimple() && SI->getOperand(0) == PN) { Builder.SetInsertPoint(SI); auto *NewBC = cast(Builder.CreateBitCast(NewPNodes[PN], SrcTy)); SI->setOperand(0, NewBC); Worklist.Add(SI); assert(hasStoreUsersOnly(*NewBC)); } } return replaceInstUsesWith(CI, NewPNodes[PN]); } Instruction *InstCombiner::visitBitCast(BitCastInst &CI) { // If the operands are integer typed then apply the integer transforms, // otherwise just apply the common ones. Value *Src = CI.getOperand(0); Type *SrcTy = Src->getType(); Type *DestTy = CI.getType(); // Get rid of casts from one type to the same type. These are useless and can // be replaced by the operand. if (DestTy == Src->getType()) return replaceInstUsesWith(CI, Src); if (PointerType *DstPTy = dyn_cast(DestTy)) { PointerType *SrcPTy = cast(SrcTy); Type *DstElTy = DstPTy->getElementType(); Type *SrcElTy = SrcPTy->getElementType(); // If we are casting a alloca to a pointer to a type of the same // size, rewrite the allocation instruction to allocate the "right" type. // There is no need to modify malloc calls because it is their bitcast that // needs to be cleaned up. if (AllocaInst *AI = dyn_cast(Src)) if (Instruction *V = PromoteCastOfAllocation(CI, *AI)) return V; // When the type pointed to is not sized the cast cannot be // turned into a gep. Type *PointeeType = cast(Src->getType()->getScalarType())->getElementType(); if (!PointeeType->isSized()) return nullptr; // If the source and destination are pointers, and this cast is equivalent // to a getelementptr X, 0, 0, 0... turn it into the appropriate gep. // This can enhance SROA and other transforms that want type-safe pointers. unsigned NumZeros = 0; while (SrcElTy != DstElTy && isa(SrcElTy) && !SrcElTy->isPointerTy() && SrcElTy->getNumContainedTypes() /* not "{}" */) { SrcElTy = cast(SrcElTy)->getTypeAtIndex(0U); ++NumZeros; } // If we found a path from the src to dest, create the getelementptr now. if (SrcElTy == DstElTy) { SmallVector Idxs(NumZeros + 1, Builder.getInt32(0)); return GetElementPtrInst::CreateInBounds(Src, Idxs); } } if (VectorType *DestVTy = dyn_cast(DestTy)) { if (DestVTy->getNumElements() == 1 && !SrcTy->isVectorTy()) { Value *Elem = Builder.CreateBitCast(Src, DestVTy->getElementType()); return InsertElementInst::Create(UndefValue::get(DestTy), Elem, Constant::getNullValue(Type::getInt32Ty(CI.getContext()))); // FIXME: Canonicalize bitcast(insertelement) -> insertelement(bitcast) } if (isa(SrcTy)) { // If this is a cast from an integer to vector, check to see if the input // is a trunc or zext of a bitcast from vector. If so, we can replace all // the casts with a shuffle and (potentially) a bitcast. if (isa(Src) || isa(Src)) { CastInst *SrcCast = cast(Src); if (BitCastInst *BCIn = dyn_cast(SrcCast->getOperand(0))) if (isa(BCIn->getOperand(0)->getType())) if (Instruction *I = optimizeVectorResize(BCIn->getOperand(0), cast(DestTy), *this)) return I; } // If the input is an 'or' instruction, we may be doing shifts and ors to // assemble the elements of the vector manually. Try to rip the code out // and replace it with insertelements. if (Value *V = optimizeIntegerToVectorInsertions(CI, *this)) return replaceInstUsesWith(CI, V); } } if (VectorType *SrcVTy = dyn_cast(SrcTy)) { if (SrcVTy->getNumElements() == 1) { // If our destination is not a vector, then make this a straight // scalar-scalar cast. if (!DestTy->isVectorTy()) { Value *Elem = Builder.CreateExtractElement(Src, Constant::getNullValue(Type::getInt32Ty(CI.getContext()))); return CastInst::Create(Instruction::BitCast, Elem, DestTy); } // Otherwise, see if our source is an insert. If so, then use the scalar // component directly. if (InsertElementInst *IEI = dyn_cast(CI.getOperand(0))) return CastInst::Create(Instruction::BitCast, IEI->getOperand(1), DestTy); } } if (ShuffleVectorInst *SVI = dyn_cast(Src)) { // Okay, we have (bitcast (shuffle ..)). Check to see if this is // a bitcast to a vector with the same # elts. if (SVI->hasOneUse() && DestTy->isVectorTy() && DestTy->getVectorNumElements() == SVI->getType()->getNumElements() && SVI->getType()->getNumElements() == SVI->getOperand(0)->getType()->getVectorNumElements()) { BitCastInst *Tmp; // If either of the operands is a cast from CI.getType(), then // evaluating the shuffle in the casted destination's type will allow // us to eliminate at least one cast. if (((Tmp = dyn_cast(SVI->getOperand(0))) && Tmp->getOperand(0)->getType() == DestTy) || ((Tmp = dyn_cast(SVI->getOperand(1))) && Tmp->getOperand(0)->getType() == DestTy)) { Value *LHS = Builder.CreateBitCast(SVI->getOperand(0), DestTy); Value *RHS = Builder.CreateBitCast(SVI->getOperand(1), DestTy); // Return a new shuffle vector. Use the same element ID's, as we // know the vector types match #elts. return new ShuffleVectorInst(LHS, RHS, SVI->getOperand(2)); } } } // Handle the A->B->A cast, and there is an intervening PHI node. if (PHINode *PN = dyn_cast(Src)) if (Instruction *I = optimizeBitCastFromPhi(CI, PN)) return I; if (Instruction *I = canonicalizeBitCastExtElt(CI, *this)) return I; if (Instruction *I = foldBitCastBitwiseLogic(CI, Builder)) return I; if (Instruction *I = foldBitCastSelect(CI, Builder)) return I; if (SrcTy->isPointerTy()) return commonPointerCastTransforms(CI); return commonCastTransforms(CI); } Instruction *InstCombiner::visitAddrSpaceCast(AddrSpaceCastInst &CI) { // If the destination pointer element type is not the same as the source's // first do a bitcast to the destination type, and then the addrspacecast. // This allows the cast to be exposed to other transforms. Value *Src = CI.getOperand(0); PointerType *SrcTy = cast(Src->getType()->getScalarType()); PointerType *DestTy = cast(CI.getType()->getScalarType()); Type *DestElemTy = DestTy->getElementType(); if (SrcTy->getElementType() != DestElemTy) { Type *MidTy = PointerType::get(DestElemTy, SrcTy->getAddressSpace()); if (VectorType *VT = dyn_cast(CI.getType())) { // Handle vectors of pointers. MidTy = VectorType::get(MidTy, VT->getNumElements()); } Value *NewBitCast = Builder.CreateBitCast(Src, MidTy); return new AddrSpaceCastInst(NewBitCast, CI.getType()); } return commonPointerCastTransforms(CI); } diff --git a/llvm/lib/Transforms/Utils/Local.cpp b/llvm/lib/Transforms/Utils/Local.cpp index 3a43025cb832..7dd74a1aa40b 100644 --- a/llvm/lib/Transforms/Utils/Local.cpp +++ b/llvm/lib/Transforms/Utils/Local.cpp @@ -1,2559 +1,2577 @@ //===- 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/APInt.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseMapInfo.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/Hashing.h" #include "llvm/ADT/None.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/TinyPtrVector.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/EHPersonalities.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LazyValueInfo.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/BinaryFormat/Dwarf.h" #include "llvm/IR/Argument.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/Constant.h" #include "llvm/IR/ConstantRange.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DIBuilder.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DebugInfoMetadata.h" #include "llvm/IR/DebugLoc.h" #include "llvm/IR/DerivedTypes.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/GetElementPtrTypeIterator.h" #include "llvm/IR/GlobalObject.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Intrinsics.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/MDBuilder.h" #include "llvm/IR/Metadata.h" #include "llvm/IR/Module.h" #include "llvm/IR/Operator.h" #include "llvm/IR/PatternMatch.h" #include "llvm/IR/Type.h" #include "llvm/IR/Use.h" #include "llvm/IR/User.h" #include "llvm/IR/Value.h" #include "llvm/IR/ValueHandle.h" #include "llvm/Support/Casting.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/KnownBits.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/ValueMapper.h" #include #include #include #include #include #include #include using namespace llvm; using namespace llvm::PatternMatch; #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, DeferredDominance *DDT) { TerminatorInst *T = BB->getTerminator(); IRBuilder<> Builder(T); // Branch - See if we are conditional jumping on constant if (auto *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 (auto *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; // 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(); if (DDT) DDT->deleteEdge(BB, OldDest); 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 (auto *SI = dyn_cast(T)) { // If we are switching on a constant, we can convert the switch to an // unconditional branch. auto *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 (auto i = SI->case_begin(), e = SI->case_end(); i != e;) { // 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) { auto *CI = mdconst::extract(MD->getOperand(MD_i)); 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. BasicBlock *ParentBB = SI->getParent(); DefaultDest->removePredecessor(ParentBB); i = SI->removeCase(i); e = SI->case_end(); if (DDT) DDT->deleteEdge(ParentBB, DefaultDest); 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; // Increment this iterator as we haven't removed the case. ++i; } 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(); std::vector Updates; if (DDT) Updates.reserve(SI->getNumSuccessors() - 1); // 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); if (DDT) Updates.push_back({DominatorTree::Delete, BB, Succ}); } } // Delete the old switch. Value *Cond = SI->getCondition(); SI->eraseFromParent(); if (DeleteDeadConditions) RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); if (DDT) DDT->applyUpdates(Updates); 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. auto 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 (auto *IBI = dyn_cast(T)) { // indirectbr blockaddress(@F, @BB) -> br label @BB if (auto *BA = dyn_cast(IBI->getAddress()->stripPointerCasts())) { BasicBlock *TheOnlyDest = BA->getBasicBlock(); std::vector Updates; if (DDT) Updates.reserve(IBI->getNumDestinations() - 1); // 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 { BasicBlock *ParentBB = IBI->getParent(); BasicBlock *DestBB = IBI->getDestination(i); DestBB->removePredecessor(ParentBB); if (DDT) Updates.push_back({DominatorTree::Delete, ParentBB, DestBB}); } } 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); } if (DDT) DDT->applyUpdates(Updates); 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()) return false; return wouldInstructionBeTriviallyDead(I, TLI); } bool llvm::wouldInstructionBeTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI) { if (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 (DbgLabelInst *DLI = dyn_cast(I)) { if (DLI->getLabel()) 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 and launder.invariant.group if dead. if (II->getIntrinsicID() == Intrinsic::stacksave || II->getIntrinsicID() == Intrinsic::launder_invariant_group) 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. Guards on // true are operationally no-ops. In the future we can consider more // sophisticated tradeoffs for guards considering potential for check // widening, but for now we keep things simple. if (II->getIntrinsicID() == Intrinsic::assume || II->getIntrinsicID() == Intrinsic::experimental_guard) { 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); if (CallSite CS = CallSite(I)) if (isMathLibCallNoop(CS, TLI)) return true; 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); RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI); return true; } void llvm::RecursivelyDeleteTriviallyDeadInstructions( SmallVectorImpl &DeadInsts, const TargetLibraryInfo *TLI) { // Process the dead instruction list until empty. while (!DeadInsts.empty()) { Instruction &I = *DeadInsts.pop_back_val(); assert(I.use_empty() && "Instructions with uses are not dead."); assert(isInstructionTriviallyDead(&I, TLI) && "Live instruction found in dead worklist!"); // Don't lose the debug info while deleting the instructions. salvageDebugInfo(I); // Null out all of the instruction's operands to see if any operand becomes // dead as we go. for (Use &OpU : I.operands()) { Value *OpV = OpU.get(); OpU.set(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(); } } /// 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)) { salvageDebugInfo(*I); // 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. bool Changed = false; if (!I->use_empty()) { I->replaceAllUsesWith(SimpleV); Changed = true; } if (isInstructionTriviallyDead(I, TLI)) { I->eraseFromParent(); Changed = true; } return Changed; } 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, DeferredDominance *DDT) { // 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); WeakTrackingVH 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(); } if (DDT) DDT->deleteEdge(Pred, BB); } /// 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, DeferredDominance *DDT) { assert(!(DT && DDT) && "Cannot call with both DT and DDT."); // 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!"); bool ReplaceEntryBB = false; if (PredBB == &DestBB->getParent()->getEntryBlock()) ReplaceEntryBB = true; // Deferred DT update: Collect all the edges that enter PredBB. These // dominator edges will be redirected to DestBB. std::vector Updates; if (DDT && !ReplaceEntryBB) { Updates.reserve(1 + (2 * pred_size(PredBB))); Updates.push_back({DominatorTree::Delete, PredBB, DestBB}); for (auto I = pred_begin(PredBB), E = pred_end(PredBB); I != E; ++I) { Updates.push_back({DominatorTree::Delete, *I, PredBB}); // This predecessor of PredBB may already have DestBB as a successor. if (llvm::find(successors(*I), DestBB) == succ_end(*I)) Updates.push_back({DominatorTree::Insert, *I, DestBB}); } } // 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(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 (ReplaceEntryBB) DestBB->moveAfter(PredBB); if (DT) { // For some irreducible CFG we end up having forward-unreachable blocks // so check if getNode returns a valid node before updating the domtree. if (DomTreeNode *DTN = DT->getNode(PredBB)) { BasicBlock *PredBBIDom = DTN->getIDom()->getBlock(); DT->changeImmediateDominator(DestBB, PredBBIDom); DT->eraseNode(PredBB); } } if (DDT) { DDT->deleteBB(PredBB); // Deferred deletion of BB. if (ReplaceEntryBB) // The entry block was removed and there is no external interface for the // dominator tree to be notified of this change. In this corner-case we // recalculate the entire tree. DDT->recalculate(*(DestBB->getParent())); else DDT->applyUpdates(Updates); } else { PredBB->eraseFromParent(); // Nuke BB. } } /// 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!"); LLVM_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))) { LLVM_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))) { LLVM_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; } using PredBlockVector = SmallVector; using IncomingValueMap = DenseMap; /// 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; } /// 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)); } } /// 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); } } /// 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, DeferredDominance *DDT) { 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; } } LLVM_DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB); std::vector Updates; if (DDT) { Updates.reserve(1 + (2 * pred_size(BB))); Updates.push_back({DominatorTree::Delete, BB, Succ}); // All predecessors of BB will be moved to Succ. for (auto I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { Updates.push_back({DominatorTree::Delete, *I, BB}); // This predecessor of BB may already have Succ as a successor. if (llvm::find(successors(*I), Succ) == succ_end(*I)) Updates.push_back({DominatorTree::Insert, *I, Succ}); } } 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(); } } // If the unconditional branch we replaced contains llvm.loop metadata, we // add the metadata to the branch instructions in the predecessors. unsigned LoopMDKind = BB->getContext().getMDKindID("llvm.loop"); Instruction *TI = BB->getTerminator(); if (TI) if (MDNode *LoopMD = TI->getMetadata(LoopMDKind)) for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { BasicBlock *Pred = *PI; Pred->getTerminator()->setMetadata(LoopMDKind, LoopMD); } // Everything that jumped to BB now goes to Succ. BB->replaceAllUsesWith(Succ); if (!Succ->hasName()) Succ->takeName(BB); if (DDT) { DDT->deleteBB(BB); // Deferred deletion of the old basic block. DDT->applyUpdates(Updates); } else { 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; 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->canIncreaseAlignment()) return Align; GO->setAlignment(PrefAlign); return PrefAlign; } return Align; } 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!"); KnownBits Known = computeKnownBits(V, DL, 0, AC, CxtI, DT); unsigned TrailZ = Known.countMinTrailingZeros(); // 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(Known.getBitWidth() - 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(DILocalVariable *DIVar, DIExpression *DIExpr, 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. 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->getVariable() == DIVar && DVI->getExpression() == DIExpr) return true; } return false; } /// See if there is a dbg.value intrinsic for DIVar for the PHI node. static bool PhiHasDebugValue(DILocalVariable *DIVar, DIExpression *DIExpr, PHINode *APN) { // 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. SmallVector DbgValues; findDbgValues(DbgValues, APN); for (auto *DVI : DbgValues) { assert(DVI->getValue() == APN); if ((DVI->getVariable() == DIVar) && (DVI->getExpression() == DIExpr)) return true; } return false; } /// Check if the alloc size of \p ValTy is large enough to cover the variable /// (or fragment of the variable) described by \p DII. /// /// This is primarily intended as a helper for the different /// ConvertDebugDeclareToDebugValue functions. The dbg.declare/dbg.addr that is /// converted describes an alloca'd variable, so we need to use the /// alloc size of the value when doing the comparison. E.g. an i1 value will be /// identified as covering an n-bit fragment, if the store size of i1 is at /// least n bits. static bool valueCoversEntireFragment(Type *ValTy, DbgInfoIntrinsic *DII) { const DataLayout &DL = DII->getModule()->getDataLayout(); uint64_t ValueSize = DL.getTypeAllocSizeInBits(ValTy); if (auto FragmentSize = DII->getFragmentSizeInBits()) return ValueSize >= *FragmentSize; return false; } /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic. void llvm::ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, StoreInst *SI, DIBuilder &Builder) { assert(DII->isAddressOfVariable()); auto *DIVar = DII->getVariable(); assert(DIVar && "Missing variable"); auto *DIExpr = DII->getExpression(); Value *DV = SI->getOperand(0); if (!valueCoversEntireFragment(SI->getValueOperand()->getType(), DII)) { // FIXME: If storing to a part of the variable described by the dbg.declare, // then we want to insert a dbg.value for the corresponding fragment. LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: " << *DII << '\n'); // For now, when there is a store to parts of the variable (but we do not // know which part) we insert an dbg.value instrinsic to indicate that we // know nothing about the variable's content. DV = UndefValue::get(DV->getType()); if (!LdStHasDebugValue(DIVar, DIExpr, SI)) Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, DII->getDebugLoc(), SI); return; } // 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) { // If this DII was already describing only a fragment of a variable, ensure // that fragment is appropriately narrowed here. // But if a fragment wasn't used, describe the value as the original // argument (rather than the zext or sext) so that it remains described even // if the sext/zext is optimized away. This widens the variable description, // leaving it up to the consumer to know how the smaller value may be // represented in a larger register. if (auto Fragment = DIExpr->getFragmentInfo()) { unsigned FragmentOffset = Fragment->OffsetInBits; SmallVector Ops(DIExpr->elements_begin(), DIExpr->elements_end() - 3); Ops.push_back(dwarf::DW_OP_LLVM_fragment); Ops.push_back(FragmentOffset); const DataLayout &DL = DII->getModule()->getDataLayout(); Ops.push_back(DL.getTypeSizeInBits(ExtendedArg->getType())); DIExpr = Builder.createExpression(Ops); } DV = ExtendedArg; } if (!LdStHasDebugValue(DIVar, DIExpr, SI)) Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, DII->getDebugLoc(), SI); } /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic. void llvm::ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, LoadInst *LI, DIBuilder &Builder) { auto *DIVar = DII->getVariable(); auto *DIExpr = DII->getExpression(); assert(DIVar && "Missing variable"); if (LdStHasDebugValue(DIVar, DIExpr, LI)) return; // 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, DIVar, DIExpr, DII->getDebugLoc(), (Instruction *)nullptr); DbgValue->insertAfter(LI); } /// Inserts a llvm.dbg.value intrinsic after a phi that has an associated /// llvm.dbg.declare or llvm.dbg.addr intrinsic. void llvm::ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, PHINode *APN, DIBuilder &Builder) { auto *DIVar = DII->getVariable(); auto *DIExpr = DII->getExpression(); assert(DIVar && "Missing variable"); if (PhiHasDebugValue(DIVar, DIExpr, APN)) return; BasicBlock *BB = APN->getParent(); auto InsertionPt = BB->getFirstInsertionPt(); // The block may be a catchswitch block, which does not have a valid // insertion point. // FIXME: Insert dbg.value markers in the successors when appropriate. if (InsertionPt != BB->end()) Builder.insertDbgValueIntrinsic(APN, DIVar, DIExpr, DII->getDebugLoc(), &*InsertionPt); } /// 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)) continue; // A volatile load/store means that the alloca can't be elided anyway. if (llvm::any_of(AI->users(), [](User *U) -> bool { if (LoadInst *LI = dyn_cast(U)) return LI->isVolatile(); if (StoreInst *SI = dyn_cast(U)) return SI->isVolatile(); return false; })) continue; for (auto &AIUse : AI->uses()) { User *U = AIUse.getUser(); if (StoreInst *SI = dyn_cast(U)) { if (AIUse.getOperandNo() == 1) 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. DIB.insertDbgValueIntrinsic(AI, DDI->getVariable(), DDI->getExpression(), DDI->getDebugLoc(), CI); } } DDI->eraseFromParent(); } return true; } /// Propagate dbg.value intrinsics through the newly inserted PHIs. void llvm::insertDebugValuesForPHIs(BasicBlock *BB, SmallVectorImpl &InsertedPHIs) { assert(BB && "No BasicBlock to clone dbg.value(s) from."); if (InsertedPHIs.size() == 0) return; // Map existing PHI nodes to their dbg.values. ValueToValueMapTy DbgValueMap; for (auto &I : *BB) { if (auto DbgII = dyn_cast(&I)) { if (auto *Loc = dyn_cast_or_null(DbgII->getVariableLocation())) DbgValueMap.insert({Loc, DbgII}); } } if (DbgValueMap.size() == 0) return; // Then iterate through the new PHIs and look to see if they use one of the // previously mapped PHIs. If so, insert a new dbg.value intrinsic that will // propagate the info through the new PHI. LLVMContext &C = BB->getContext(); for (auto PHI : InsertedPHIs) { BasicBlock *Parent = PHI->getParent(); // Avoid inserting an intrinsic into an EH block. if (Parent->getFirstNonPHI()->isEHPad()) continue; auto PhiMAV = MetadataAsValue::get(C, ValueAsMetadata::get(PHI)); for (auto VI : PHI->operand_values()) { auto V = DbgValueMap.find(VI); if (V != DbgValueMap.end()) { auto *DbgII = cast(V->second); Instruction *NewDbgII = DbgII->clone(); NewDbgII->setOperand(0, PhiMAV); auto InsertionPt = Parent->getFirstInsertionPt(); assert(InsertionPt != Parent->end() && "Ill-formed basic block"); NewDbgII->insertBefore(&*InsertionPt); } } } } /// Finds all intrinsics declaring local variables as living in the memory that /// 'V' points to. This may include a mix of dbg.declare and /// dbg.addr intrinsics. TinyPtrVector llvm::FindDbgAddrUses(Value *V) { auto *L = LocalAsMetadata::getIfExists(V); if (!L) return {}; auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L); if (!MDV) return {}; TinyPtrVector Declares; for (User *U : MDV->users()) { if (auto *DII = dyn_cast(U)) if (DII->isAddressOfVariable()) Declares.push_back(DII); } return Declares; } void llvm::findDbgValues(SmallVectorImpl &DbgValues, Value *V) { if (auto *L = LocalAsMetadata::getIfExists(V)) if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L)) for (User *U : MDV->users()) if (DbgValueInst *DVI = dyn_cast(U)) DbgValues.push_back(DVI); } void llvm::findDbgUsers(SmallVectorImpl &DbgUsers, Value *V) { if (auto *L = LocalAsMetadata::getIfExists(V)) if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L)) for (User *U : MDV->users()) if (DbgInfoIntrinsic *DII = dyn_cast(U)) DbgUsers.push_back(DII); } bool llvm::replaceDbgDeclare(Value *Address, Value *NewAddress, Instruction *InsertBefore, DIBuilder &Builder, bool DerefBefore, int Offset, bool DerefAfter) { auto DbgAddrs = FindDbgAddrUses(Address); for (DbgInfoIntrinsic *DII : DbgAddrs) { DebugLoc Loc = DII->getDebugLoc(); auto *DIVar = DII->getVariable(); auto *DIExpr = DII->getExpression(); assert(DIVar && "Missing variable"); DIExpr = DIExpression::prepend(DIExpr, DerefBefore, Offset, DerefAfter); // Insert llvm.dbg.declare immediately after InsertBefore, and remove old // llvm.dbg.declare. Builder.insertDeclare(NewAddress, DIVar, DIExpr, Loc, InsertBefore); if (DII == InsertBefore) InsertBefore = &*std::next(InsertBefore->getIterator()); DII->eraseFromParent(); } return !DbgAddrs.empty(); } bool llvm::replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, DIBuilder &Builder, bool DerefBefore, int Offset, bool DerefAfter) { return replaceDbgDeclare(AI, NewAllocaAddress, AI->getNextNode(), Builder, DerefBefore, Offset, DerefAfter); } static void replaceOneDbgValueForAlloca(DbgValueInst *DVI, Value *NewAddress, DIBuilder &Builder, int Offset) { DebugLoc Loc = DVI->getDebugLoc(); auto *DIVar = DVI->getVariable(); auto *DIExpr = DVI->getExpression(); assert(DIVar && "Missing variable"); // This is an alloca-based llvm.dbg.value. The first thing it should do with // the alloca pointer is dereference it. Otherwise we don't know how to handle // it and give up. if (!DIExpr || DIExpr->getNumElements() < 1 || DIExpr->getElement(0) != dwarf::DW_OP_deref) return; // Insert the offset immediately after the first deref. // We could just change the offset argument of dbg.value, but it's unsigned... if (Offset) { SmallVector Ops; Ops.push_back(dwarf::DW_OP_deref); DIExpression::appendOffset(Ops, Offset); Ops.append(DIExpr->elements_begin() + 1, DIExpr->elements_end()); DIExpr = Builder.createExpression(Ops); } Builder.insertDbgValueIntrinsic(NewAddress, DIVar, DIExpr, Loc, DVI); DVI->eraseFromParent(); } void llvm::replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress, DIBuilder &Builder, int Offset) { if (auto *L = LocalAsMetadata::getIfExists(AI)) if (auto *MDV = MetadataAsValue::getIfExists(AI->getContext(), L)) for (auto UI = MDV->use_begin(), UE = MDV->use_end(); UI != UE;) { Use &U = *UI++; if (auto *DVI = dyn_cast(U.getUser())) replaceOneDbgValueForAlloca(DVI, NewAllocaAddress, Builder, Offset); } } void llvm::salvageDebugInfo(Instruction &I) { // This function is hot. An early check to determine whether the instruction // has any metadata to save allows it to return earlier on average. if (!I.isUsedByMetadata()) return; SmallVector DbgUsers; findDbgUsers(DbgUsers, &I); if (DbgUsers.empty()) return; auto &M = *I.getModule(); auto &DL = M.getDataLayout(); auto wrapMD = [&](Value *V) { return MetadataAsValue::get(I.getContext(), ValueAsMetadata::get(V)); }; auto doSalvage = [&](DbgInfoIntrinsic *DII, SmallVectorImpl &Ops) { auto *DIExpr = DII->getExpression(); DIExpr = DIExpression::prependOpcodes(DIExpr, Ops, DIExpression::WithStackValue); DII->setOperand(0, wrapMD(I.getOperand(0))); DII->setOperand(2, MetadataAsValue::get(I.getContext(), DIExpr)); LLVM_DEBUG(dbgs() << "SALVAGE: " << *DII << '\n'); }; auto applyOffset = [&](DbgInfoIntrinsic *DII, uint64_t Offset) { SmallVector Ops; DIExpression::appendOffset(Ops, Offset); doSalvage(DII, Ops); }; auto applyOps = [&](DbgInfoIntrinsic *DII, std::initializer_list Opcodes) { SmallVector Ops(Opcodes); doSalvage(DII, Ops); }; if (auto *CI = dyn_cast(&I)) { if (!CI->isNoopCast(DL)) return; // No-op casts are irrelevant for debug info. MetadataAsValue *CastSrc = wrapMD(I.getOperand(0)); for (auto *DII : DbgUsers) { DII->setOperand(0, CastSrc); LLVM_DEBUG(dbgs() << "SALVAGE: " << *DII << '\n'); } } else if (auto *GEP = dyn_cast(&I)) { unsigned BitWidth = M.getDataLayout().getIndexSizeInBits(GEP->getPointerAddressSpace()); // Rewrite a constant GEP into a DIExpression. Since we are performing // arithmetic to compute the variable's *value* in the DIExpression, we // need to mark the expression with a DW_OP_stack_value. APInt Offset(BitWidth, 0); if (GEP->accumulateConstantOffset(M.getDataLayout(), Offset)) for (auto *DII : DbgUsers) applyOffset(DII, Offset.getSExtValue()); } else if (auto *BI = dyn_cast(&I)) { // Rewrite binary operations with constant integer operands. auto *ConstInt = dyn_cast(I.getOperand(1)); if (!ConstInt || ConstInt->getBitWidth() > 64) return; uint64_t Val = ConstInt->getSExtValue(); for (auto *DII : DbgUsers) { switch (BI->getOpcode()) { case Instruction::Add: applyOffset(DII, Val); break; case Instruction::Sub: applyOffset(DII, -int64_t(Val)); break; case Instruction::Mul: applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_mul}); break; case Instruction::SDiv: applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_div}); break; case Instruction::SRem: applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_mod}); break; case Instruction::Or: applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_or}); break; case Instruction::And: applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_and}); break; case Instruction::Xor: applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_xor}); break; case Instruction::Shl: applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_shl}); break; case Instruction::LShr: applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_shr}); break; case Instruction::AShr: applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_shra}); break; default: // TODO: Salvage constants from each kind of binop we know about. continue; } } } else if (isa(&I)) { MetadataAsValue *AddrMD = wrapMD(I.getOperand(0)); for (auto *DII : DbgUsers) { // Rewrite the load into DW_OP_deref. auto *DIExpr = DII->getExpression(); DIExpr = DIExpression::prepend(DIExpr, DIExpression::WithDeref); DII->setOperand(0, AddrMD); DII->setOperand(2, MetadataAsValue::get(I.getContext(), DIExpr)); LLVM_DEBUG(dbgs() << "SALVAGE: " << *DII << '\n'); } } } +void llvm::insertReplacementDbgValues( + Instruction &From, Instruction &To, Instruction &InsertBefore, + function_ref RewriteExpr) { + // Collect all debug users of From. + SmallVector Users; + findDbgUsers(Users, &From); + if (Users.empty()) + return; + + // Insert a replacement debug value for each old debug user. It's assumed + // that the old debug users will be erased later. + DIBuilder DIB(*From.getModule()); + for (auto *OldDII : Users) + DIB.insertDbgValueIntrinsic(&To, OldDII->getVariable(), + RewriteExpr(*OldDII), + OldDII->getDebugLoc().get(), &InsertBefore); +} + unsigned llvm::removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB) { unsigned NumDeadInst = 0; // Delete the instructions backwards, as it has a reduced likelihood of // having to update as many def-use and use-def chains. Instruction *EndInst = BB->getTerminator(); // Last not to be deleted. while (EndInst != &BB->front()) { // Delete the next to last instruction. Instruction *Inst = &*--EndInst->getIterator(); if (!Inst->use_empty() && !Inst->getType()->isTokenTy()) Inst->replaceAllUsesWith(UndefValue::get(Inst->getType())); if (Inst->isEHPad() || Inst->getType()->isTokenTy()) { EndInst = Inst; continue; } if (!isa(Inst)) ++NumDeadInst; Inst->eraseFromParent(); } return NumDeadInst; } unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap, bool PreserveLCSSA, DeferredDominance *DDT) { BasicBlock *BB = I->getParent(); std::vector Updates; // Loop over all of the successors, removing BB's entry from any PHI // nodes. if (DDT) Updates.reserve(BB->getTerminator()->getNumSuccessors()); for (BasicBlock *Successor : successors(BB)) { Successor->removePredecessor(BB, PreserveLCSSA); if (DDT) Updates.push_back({DominatorTree::Delete, BB, Successor}); } // 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. unsigned NumInstrsRemoved = 0; 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++); ++NumInstrsRemoved; } if (DDT) DDT->applyUpdates(Updates); return NumInstrsRemoved; } /// changeToCall - Convert the specified invoke into a normal call. static void changeToCall(InvokeInst *II, DeferredDominance *DDT = nullptr) { 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. BasicBlock *NormalDestBB = II->getNormalDest(); BranchInst::Create(NormalDestBB, II); // Update PHI nodes in the unwind destination BasicBlock *BB = II->getParent(); BasicBlock *UnwindDestBB = II->getUnwindDest(); UnwindDestBB->removePredecessor(BB); II->eraseFromParent(); if (DDT) DDT->deleteEdge(BB, UnwindDestBB); } BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI, BasicBlock *UnwindEdge) { BasicBlock *BB = CI->getParent(); // Convert this function call into an invoke instruction. First, split the // basic block. BasicBlock *Split = BB->splitBasicBlock(CI->getIterator(), CI->getName() + ".noexc"); // Delete the unconditional branch inserted by splitBasicBlock BB->getInstList().pop_back(); // Create the new invoke instruction. SmallVector InvokeArgs(CI->arg_begin(), CI->arg_end()); SmallVector OpBundles; CI->getOperandBundlesAsDefs(OpBundles); // Note: we're round tripping operand bundles through memory here, and that // can potentially be avoided with a cleverer API design that we do not have // as of this time. InvokeInst *II = InvokeInst::Create(CI->getCalledValue(), Split, UnwindEdge, InvokeArgs, OpBundles, CI->getName(), BB); II->setDebugLoc(CI->getDebugLoc()); II->setCallingConv(CI->getCallingConv()); II->setAttributes(CI->getAttributes()); // Make sure that anything using the call now uses the invoke! This also // updates the CallGraph if present, because it uses a WeakTrackingVH. CI->replaceAllUsesWith(II); // Delete the original call Split->getInstList().pop_front(); return Split; } static bool markAliveBlocks(Function &F, SmallPtrSetImpl &Reachable, DeferredDominance *DDT = nullptr) { 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 (Instruction &I : *BB) { // 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 (auto *II = dyn_cast(&I)) { if (II->getIntrinsicID() == Intrinsic::assume) { if (match(II->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) { // Don't insert a call to llvm.trap right before the unreachable. changeToUnreachable(II, false, false, DDT); Changed = true; break; } } if (II->getIntrinsicID() == Intrinsic::experimental_guard) { // A call to the guard intrinsic bails out of the current compilation // unit if the predicate passed to it is false. If the predicate is a // constant false, then we know the guard will bail out of the current // compile unconditionally, so all code following it is dead. // // Note: unlike in llvm.assume, it is not "obviously profitable" for // guards to treat `undef` as `false` since a guard on `undef` can // still be useful for widening. if (match(II->getArgOperand(0), m_Zero())) if (!isa(II->getNextNode())) { changeToUnreachable(II->getNextNode(), /*UseLLVMTrap=*/false, false, DDT); Changed = true; break; } } } if (auto *CI = dyn_cast(&I)) { Value *Callee = CI->getCalledValue(); if (isa(Callee) || isa(Callee)) { changeToUnreachable(CI, /*UseLLVMTrap=*/false, false, DDT); Changed = true; break; } 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. if (!isa(CI->getNextNode())) { // Don't insert a call to llvm.trap right before the unreachable. changeToUnreachable(CI->getNextNode(), false, false, DDT); 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 (auto *SI = dyn_cast(&I)) { // 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, false, DDT); 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, false, DDT); Changed = true; } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) { if (II->use_empty() && II->onlyReadsMemory()) { // jump to the normal destination branch. BasicBlock *NormalDestBB = II->getNormalDest(); BasicBlock *UnwindDestBB = II->getUnwindDest(); BranchInst::Create(NormalDestBB, II); UnwindDestBB->removePredecessor(II->getParent()); II->eraseFromParent(); if (DDT) DDT->deleteEdge(BB, UnwindDestBB); } else changeToCall(II, DDT); 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, nullptr, DDT); for (BasicBlock *Successor : successors(BB)) if (Reachable.insert(Successor).second) Worklist.push_back(Successor); } while (!Worklist.empty()); return Changed; } void llvm::removeUnwindEdge(BasicBlock *BB, DeferredDominance *DDT) { TerminatorInst *TI = BB->getTerminator(); if (auto *II = dyn_cast(TI)) { changeToCall(II, DDT); 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(); if (DDT) DDT->deleteEdge(BB, UnwindDest); } /// removeUnreachableBlocks - Remove blocks that are not reachable, even /// if they are in a dead cycle. Return true if a change was made, false /// otherwise. If `LVI` is passed, this function preserves LazyValueInfo /// after modifying the CFG. bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI, DeferredDominance *DDT) { SmallPtrSet Reachable; bool Changed = markAliveBlocks(F, Reachable, DDT); // 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. Update DDT and LVI if available. std::vector Updates; for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ++I) { auto *BB = &*I; if (Reachable.count(BB)) continue; for (BasicBlock *Successor : successors(BB)) { if (Reachable.count(Successor)) Successor->removePredecessor(BB); if (DDT) Updates.push_back({DominatorTree::Delete, BB, Successor}); } if (LVI) LVI->eraseBlock(BB); BB->dropAllReferences(); } for (Function::iterator I = ++F.begin(); I != F.end();) { auto *BB = &*I; if (Reachable.count(BB)) { ++I; continue; } if (DDT) { DDT->deleteBB(BB); // deferred deletion of BB. ++I; } else { I = F.getBasicBlockList().erase(I); } } if (DDT) DDT->applyUpdates(Updates); return true; } void llvm::combineMetadata(Instruction *K, const Instruction *J, ArrayRef KnownIDs) { SmallVector, 4> Metadata; K->dropUnknownNonDebugMetadata(KnownIDs); K->getAllMetadataOtherThanDebugLoc(Metadata); for (const auto &MD : Metadata) { unsigned Kind = MD.first; MDNode *JMD = J->getMetadata(Kind); MDNode *KMD = MD.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: case LLVMContext::MD_mem_parallel_loop_access: 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); } void llvm::combineMetadataForCSE(Instruction *K, const Instruction *J) { unsigned KnownIDs[] = { LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope, LLVMContext::MD_noalias, LLVMContext::MD_range, LLVMContext::MD_invariant_load, LLVMContext::MD_nonnull, LLVMContext::MD_invariant_group, LLVMContext::MD_align, LLVMContext::MD_dereferenceable, LLVMContext::MD_dereferenceable_or_null}; combineMetadata(K, J, KnownIDs); } template static unsigned replaceDominatedUsesWith(Value *From, Value *To, const RootType &Root, const DominatesFn &Dominates) { 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 (!Dominates(Root, U)) continue; U.set(To); LLVM_DEBUG(dbgs() << "Replace dominated use of '" << From->getName() << "' as " << *To << " in " << *U << "\n"); ++Count; } return Count; } unsigned llvm::replaceNonLocalUsesWith(Instruction *From, Value *To) { assert(From->getType() == To->getType()); auto *BB = From->getParent(); 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 (I->getParent() == BB) continue; U.set(To); ++Count; } return Count; } unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Root) { auto Dominates = [&DT](const BasicBlockEdge &Root, const Use &U) { return DT.dominates(Root, U); }; return ::replaceDominatedUsesWith(From, To, Root, Dominates); } unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlock *BB) { auto ProperlyDominates = [&DT](const BasicBlock *BB, const Use &U) { auto *I = cast(U.getUser())->getParent(); return DT.properlyDominates(BB, I); }; return ::replaceDominatedUsesWith(From, To, BB, ProperlyDominates); } bool llvm::callsGCLeafFunction(ImmutableCallSite CS, const TargetLibraryInfo &TLI) { // 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()) { if (F->hasFnAttribute("gc-leaf-function")) return true; if (auto IID = F->getIntrinsicID()) // Most LLVM intrinsics do not take safepoints. return IID != Intrinsic::experimental_gc_statepoint && IID != Intrinsic::experimental_deoptimize; } // Lib calls can be materialized by some passes, and won't be // marked as 'gc-leaf-function.' All available Libcalls are // GC-leaf. LibFunc LF; if (TLI.getLibFunc(CS, LF)) { return TLI.has(LF); } return false; } void llvm::copyNonnullMetadata(const LoadInst &OldLI, MDNode *N, LoadInst &NewLI) { auto *NewTy = NewLI.getType(); // This only directly applies if the new type is also a pointer. if (NewTy->isPointerTy()) { NewLI.setMetadata(LLVMContext::MD_nonnull, N); return; } // The only other translation we can do is to integral loads with !range // metadata. if (!NewTy->isIntegerTy()) return; MDBuilder MDB(NewLI.getContext()); const Value *Ptr = OldLI.getPointerOperand(); auto *ITy = cast(NewTy); auto *NullInt = ConstantExpr::getPtrToInt( ConstantPointerNull::get(cast(Ptr->getType())), ITy); auto *NonNullInt = ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1)); NewLI.setMetadata(LLVMContext::MD_range, MDB.createRange(NonNullInt, NullInt)); } void llvm::copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI, MDNode *N, LoadInst &NewLI) { auto *NewTy = NewLI.getType(); // Give up unless it is converted to a pointer where there is a single very // valuable mapping we can do reliably. // FIXME: It would be nice to propagate this in more ways, but the type // conversions make it hard. if (!NewTy->isPointerTy()) return; unsigned BitWidth = DL.getIndexTypeSizeInBits(NewTy); if (!getConstantRangeFromMetadata(*N).contains(APInt(BitWidth, 0))) { MDNode *NN = MDNode::get(OldLI.getContext(), None); NewLI.setMetadata(LLVMContext::MD_nonnull, NN); } } namespace { /// A potential constituent of a bitreverse or bswap expression. See /// collectBitParts for a fuller explanation. struct BitPart { BitPart(Value *P, unsigned BW) : Provider(P) { Provenance.resize(BW); } /// The Value that this is a bitreverse/bswap of. Value *Provider; /// The "provenance" of each bit. Provenance[A] = B means that bit A /// in Provider becomes bit B in the result of this expression. SmallVector Provenance; // int8_t means max size is i128. enum { Unset = -1 }; }; } // end anonymous namespace /// Analyze the specified subexpression and see if it is capable of providing /// pieces of a bswap or bitreverse. The subexpression provides a potential /// piece of a bswap or bitreverse if it can be proven that each non-zero bit in /// the output of the expression came from a corresponding bit in some other /// value. This function is recursive, and the end result is a mapping of /// bitnumber to bitnumber. It is the caller's responsibility to validate that /// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse. /// /// For example, if the current subexpression if "(shl i32 %X, 24)" then we know /// that the expression deposits the low byte of %X into the high byte of the /// result and that all other bits are zero. This expression is accepted and a /// BitPart is returned with Provider set to %X and Provenance[24-31] set to /// [0-7]. /// /// To avoid revisiting values, the BitPart results are memoized into the /// provided map. To avoid unnecessary copying of BitParts, BitParts are /// constructed in-place in the \c BPS map. Because of this \c BPS needs to /// store BitParts objects, not pointers. As we need the concept of a nullptr /// BitParts (Value has been analyzed and the analysis failed), we an Optional /// type instead to provide the same functionality. /// /// Because we pass around references into \c BPS, we must use a container that /// does not invalidate internal references (std::map instead of DenseMap). static const Optional & collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals, std::map> &BPS) { auto I = BPS.find(V); if (I != BPS.end()) return I->second; auto &Result = BPS[V] = None; auto BitWidth = cast(V->getType())->getBitWidth(); if (Instruction *I = dyn_cast(V)) { // If this is an or instruction, it may be an inner node of the bswap. if (I->getOpcode() == Instruction::Or) { auto &A = collectBitParts(I->getOperand(0), MatchBSwaps, MatchBitReversals, BPS); auto &B = collectBitParts(I->getOperand(1), MatchBSwaps, MatchBitReversals, BPS); if (!A || !B) return Result; // Try and merge the two together. if (!A->Provider || A->Provider != B->Provider) return Result; Result = BitPart(A->Provider, BitWidth); for (unsigned i = 0; i < A->Provenance.size(); ++i) { if (A->Provenance[i] != BitPart::Unset && B->Provenance[i] != BitPart::Unset && A->Provenance[i] != B->Provenance[i]) return Result = None; if (A->Provenance[i] == BitPart::Unset) Result->Provenance[i] = B->Provenance[i]; else Result->Provenance[i] = A->Provenance[i]; } return Result; } // If this is a logical shift by a constant, recurse then shift the result. if (I->isLogicalShift() && isa(I->getOperand(1))) { unsigned BitShift = cast(I->getOperand(1))->getLimitedValue(~0U); // Ensure the shift amount is defined. if (BitShift > BitWidth) return Result; auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps, MatchBitReversals, BPS); if (!Res) return Result; Result = Res; // Perform the "shift" on BitProvenance. auto &P = Result->Provenance; if (I->getOpcode() == Instruction::Shl) { P.erase(std::prev(P.end(), BitShift), P.end()); P.insert(P.begin(), BitShift, BitPart::Unset); } else { P.erase(P.begin(), std::next(P.begin(), BitShift)); P.insert(P.end(), BitShift, BitPart::Unset); } return Result; } // If this is a logical 'and' with a mask that clears bits, recurse then // unset the appropriate bits. if (I->getOpcode() == Instruction::And && isa(I->getOperand(1))) { APInt Bit(I->getType()->getPrimitiveSizeInBits(), 1); const APInt &AndMask = cast(I->getOperand(1))->getValue(); // Check that the mask allows a multiple of 8 bits for a bswap, for an // early exit. unsigned NumMaskedBits = AndMask.countPopulation(); if (!MatchBitReversals && NumMaskedBits % 8 != 0) return Result; auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps, MatchBitReversals, BPS); if (!Res) return Result; Result = Res; for (unsigned i = 0; i < BitWidth; ++i, Bit <<= 1) // If the AndMask is zero for this bit, clear the bit. if ((AndMask & Bit) == 0) Result->Provenance[i] = BitPart::Unset; return Result; } // If this is a zext instruction zero extend the result. if (I->getOpcode() == Instruction::ZExt) { auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps, MatchBitReversals, BPS); if (!Res) return Result; Result = BitPart(Res->Provider, BitWidth); auto NarrowBitWidth = cast(cast(I)->getSrcTy())->getBitWidth(); for (unsigned i = 0; i < NarrowBitWidth; ++i) Result->Provenance[i] = Res->Provenance[i]; for (unsigned i = NarrowBitWidth; i < BitWidth; ++i) Result->Provenance[i] = BitPart::Unset; return Result; } } // Okay, we got to something that isn't a shift, 'or' or 'and'. This must be // the input value to the bswap/bitreverse. Result = BitPart(V, BitWidth); for (unsigned i = 0; i < BitWidth; ++i) Result->Provenance[i] = i; return Result; } static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To, unsigned BitWidth) { if (From % 8 != To % 8) return false; // Convert from bit indices to byte indices and check for a byte reversal. From >>= 3; To >>= 3; BitWidth >>= 3; return From == BitWidth - To - 1; } static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To, unsigned BitWidth) { return From == BitWidth - To - 1; } bool llvm::recognizeBSwapOrBitReverseIdiom( Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl &InsertedInsts) { if (Operator::getOpcode(I) != Instruction::Or) return false; if (!MatchBSwaps && !MatchBitReversals) return false; IntegerType *ITy = dyn_cast(I->getType()); if (!ITy || ITy->getBitWidth() > 128) return false; // Can't do vectors or integers > 128 bits. unsigned BW = ITy->getBitWidth(); unsigned DemandedBW = BW; IntegerType *DemandedTy = ITy; if (I->hasOneUse()) { if (TruncInst *Trunc = dyn_cast(I->user_back())) { DemandedTy = cast(Trunc->getType()); DemandedBW = DemandedTy->getBitWidth(); } } // Try to find all the pieces corresponding to the bswap. std::map> BPS; auto Res = collectBitParts(I, MatchBSwaps, MatchBitReversals, BPS); if (!Res) return false; auto &BitProvenance = Res->Provenance; // Now, is the bit permutation correct for a bswap or a bitreverse? We can // only byteswap values with an even number of bytes. bool OKForBSwap = DemandedBW % 16 == 0, OKForBitReverse = true; for (unsigned i = 0; i < DemandedBW; ++i) { OKForBSwap &= bitTransformIsCorrectForBSwap(BitProvenance[i], i, DemandedBW); OKForBitReverse &= bitTransformIsCorrectForBitReverse(BitProvenance[i], i, DemandedBW); } Intrinsic::ID Intrin; if (OKForBSwap && MatchBSwaps) Intrin = Intrinsic::bswap; else if (OKForBitReverse && MatchBitReversals) Intrin = Intrinsic::bitreverse; else return false; if (ITy != DemandedTy) { Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, DemandedTy); Value *Provider = Res->Provider; IntegerType *ProviderTy = cast(Provider->getType()); // We may need to truncate the provider. if (DemandedTy != ProviderTy) { auto *Trunc = CastInst::Create(Instruction::Trunc, Provider, DemandedTy, "trunc", I); InsertedInsts.push_back(Trunc); Provider = Trunc; } auto *CI = CallInst::Create(F, Provider, "rev", I); InsertedInsts.push_back(CI); auto *ExtInst = CastInst::Create(Instruction::ZExt, CI, ITy, "zext", I); InsertedInsts.push_back(ExtInst); return true; } Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, ITy); InsertedInsts.push_back(CallInst::Create(F, Res->Provider, "rev", I)); return true; } // CodeGen has special handling for some string functions that may replace // them with target-specific intrinsics. Since that'd skip our interceptors // in ASan/MSan/TSan/DFSan, and thus make us miss some memory accesses, // we mark affected calls as NoBuiltin, which will disable optimization // in CodeGen. void llvm::maybeMarkSanitizerLibraryCallNoBuiltin( CallInst *CI, const TargetLibraryInfo *TLI) { Function *F = CI->getCalledFunction(); LibFunc Func; if (F && !F->hasLocalLinkage() && F->hasName() && TLI->getLibFunc(F->getName(), Func) && TLI->hasOptimizedCodeGen(Func) && !F->doesNotAccessMemory()) CI->addAttribute(AttributeList::FunctionIndex, Attribute::NoBuiltin); } bool llvm::canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx) { // We can't have a PHI with a metadata type. if (I->getOperand(OpIdx)->getType()->isMetadataTy()) return false; // Early exit. if (!isa(I->getOperand(OpIdx))) return true; switch (I->getOpcode()) { default: return true; case Instruction::Call: case Instruction::Invoke: // Can't handle inline asm. Skip it. if (isa(ImmutableCallSite(I).getCalledValue())) return false; // Many arithmetic intrinsics have no issue taking a // variable, however it's hard to distingish these from // specials such as @llvm.frameaddress that require a constant. if (isa(I)) return false; // Constant bundle operands may need to retain their constant-ness for // correctness. if (ImmutableCallSite(I).isBundleOperand(OpIdx)) return false; return true; case Instruction::ShuffleVector: // Shufflevector masks are constant. return OpIdx != 2; case Instruction::Switch: case Instruction::ExtractValue: // All operands apart from the first are constant. return OpIdx == 0; case Instruction::InsertValue: // All operands apart from the first and the second are constant. return OpIdx < 2; case Instruction::Alloca: // Static allocas (constant size in the entry block) are handled by // prologue/epilogue insertion so they're free anyway. We definitely don't // want to make them non-constant. return !cast(I)->isStaticAlloca(); case Instruction::GetElementPtr: if (OpIdx == 0) return true; gep_type_iterator It = gep_type_begin(I); for (auto E = std::next(It, OpIdx); It != E; ++It) if (It.isStruct()) return false; return true; } }