10b57cec5SDimitry Andric //===- Local.h - Functions to perform local transformations -----*- C++ -*-===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric // 90b57cec5SDimitry Andric // This family of functions perform various local transformations to the 100b57cec5SDimitry Andric // program. 110b57cec5SDimitry Andric // 120b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 130b57cec5SDimitry Andric 140b57cec5SDimitry Andric #ifndef LLVM_TRANSFORMS_UTILS_LOCAL_H 150b57cec5SDimitry Andric #define LLVM_TRANSFORMS_UTILS_LOCAL_H 160b57cec5SDimitry Andric 170b57cec5SDimitry Andric #include "llvm/ADT/ArrayRef.h" 180b57cec5SDimitry Andric #include "llvm/ADT/STLExtras.h" 190b57cec5SDimitry Andric #include "llvm/ADT/SmallPtrSet.h" 200b57cec5SDimitry Andric #include "llvm/ADT/SmallVector.h" 210b57cec5SDimitry Andric #include "llvm/ADT/TinyPtrVector.h" 220b57cec5SDimitry Andric #include "llvm/Analysis/AliasAnalysis.h" 230b57cec5SDimitry Andric #include "llvm/Analysis/DomTreeUpdater.h" 240b57cec5SDimitry Andric #include "llvm/Analysis/Utils/Local.h" 250b57cec5SDimitry Andric #include "llvm/IR/Constant.h" 260b57cec5SDimitry Andric #include "llvm/IR/Constants.h" 270b57cec5SDimitry Andric #include "llvm/IR/DataLayout.h" 280b57cec5SDimitry Andric #include "llvm/IR/Dominators.h" 290b57cec5SDimitry Andric #include "llvm/IR/GetElementPtrTypeIterator.h" 300b57cec5SDimitry Andric #include "llvm/IR/Operator.h" 310b57cec5SDimitry Andric #include "llvm/IR/Type.h" 320b57cec5SDimitry Andric #include "llvm/IR/User.h" 330b57cec5SDimitry Andric #include "llvm/IR/Value.h" 340b57cec5SDimitry Andric #include "llvm/Support/Casting.h" 350b57cec5SDimitry Andric #include <cstdint> 360b57cec5SDimitry Andric #include <limits> 370b57cec5SDimitry Andric 380b57cec5SDimitry Andric namespace llvm { 390b57cec5SDimitry Andric 400b57cec5SDimitry Andric class AllocaInst; 410b57cec5SDimitry Andric class AssumptionCache; 420b57cec5SDimitry Andric class BasicBlock; 430b57cec5SDimitry Andric class BranchInst; 440b57cec5SDimitry Andric class CallInst; 450b57cec5SDimitry Andric class DbgVariableIntrinsic; 460b57cec5SDimitry Andric class DbgValueInst; 470b57cec5SDimitry Andric class DIBuilder; 480b57cec5SDimitry Andric class Function; 490b57cec5SDimitry Andric class Instruction; 500b57cec5SDimitry Andric class LazyValueInfo; 510b57cec5SDimitry Andric class LoadInst; 520b57cec5SDimitry Andric class MDNode; 530b57cec5SDimitry Andric class MemorySSAUpdater; 540b57cec5SDimitry Andric class PHINode; 550b57cec5SDimitry Andric class StoreInst; 560b57cec5SDimitry Andric class TargetLibraryInfo; 570b57cec5SDimitry Andric class TargetTransformInfo; 580b57cec5SDimitry Andric 590b57cec5SDimitry Andric /// A set of parameters used to control the transforms in the SimplifyCFG pass. 600b57cec5SDimitry Andric /// Options may change depending on the position in the optimization pipeline. 610b57cec5SDimitry Andric /// For example, canonical form that includes switches and branches may later be 620b57cec5SDimitry Andric /// replaced by lookup tables and selects. 630b57cec5SDimitry Andric struct SimplifyCFGOptions { 640b57cec5SDimitry Andric int BonusInstThreshold; 650b57cec5SDimitry Andric bool ForwardSwitchCondToPhi; 660b57cec5SDimitry Andric bool ConvertSwitchToLookupTable; 670b57cec5SDimitry Andric bool NeedCanonicalLoop; 680b57cec5SDimitry Andric bool SinkCommonInsts; 690b57cec5SDimitry Andric AssumptionCache *AC; 700b57cec5SDimitry Andric 710b57cec5SDimitry Andric SimplifyCFGOptions(unsigned BonusThreshold = 1, 720b57cec5SDimitry Andric bool ForwardSwitchCond = false, 730b57cec5SDimitry Andric bool SwitchToLookup = false, bool CanonicalLoops = true, 740b57cec5SDimitry Andric bool SinkCommon = false, 750b57cec5SDimitry Andric AssumptionCache *AssumpCache = nullptr) 760b57cec5SDimitry Andric : BonusInstThreshold(BonusThreshold), 770b57cec5SDimitry Andric ForwardSwitchCondToPhi(ForwardSwitchCond), 780b57cec5SDimitry Andric ConvertSwitchToLookupTable(SwitchToLookup), 790b57cec5SDimitry Andric NeedCanonicalLoop(CanonicalLoops), 800b57cec5SDimitry Andric SinkCommonInsts(SinkCommon), 810b57cec5SDimitry Andric AC(AssumpCache) {} 820b57cec5SDimitry Andric 830b57cec5SDimitry Andric // Support 'builder' pattern to set members by name at construction time. 840b57cec5SDimitry Andric SimplifyCFGOptions &bonusInstThreshold(int I) { 850b57cec5SDimitry Andric BonusInstThreshold = I; 860b57cec5SDimitry Andric return *this; 870b57cec5SDimitry Andric } 880b57cec5SDimitry Andric SimplifyCFGOptions &forwardSwitchCondToPhi(bool B) { 890b57cec5SDimitry Andric ForwardSwitchCondToPhi = B; 900b57cec5SDimitry Andric return *this; 910b57cec5SDimitry Andric } 920b57cec5SDimitry Andric SimplifyCFGOptions &convertSwitchToLookupTable(bool B) { 930b57cec5SDimitry Andric ConvertSwitchToLookupTable = B; 940b57cec5SDimitry Andric return *this; 950b57cec5SDimitry Andric } 960b57cec5SDimitry Andric SimplifyCFGOptions &needCanonicalLoops(bool B) { 970b57cec5SDimitry Andric NeedCanonicalLoop = B; 980b57cec5SDimitry Andric return *this; 990b57cec5SDimitry Andric } 1000b57cec5SDimitry Andric SimplifyCFGOptions &sinkCommonInsts(bool B) { 1010b57cec5SDimitry Andric SinkCommonInsts = B; 1020b57cec5SDimitry Andric return *this; 1030b57cec5SDimitry Andric } 1040b57cec5SDimitry Andric SimplifyCFGOptions &setAssumptionCache(AssumptionCache *Cache) { 1050b57cec5SDimitry Andric AC = Cache; 1060b57cec5SDimitry Andric return *this; 1070b57cec5SDimitry Andric } 1080b57cec5SDimitry Andric }; 1090b57cec5SDimitry Andric 1100b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 1110b57cec5SDimitry Andric // Local constant propagation. 1120b57cec5SDimitry Andric // 1130b57cec5SDimitry Andric 1140b57cec5SDimitry Andric /// If a terminator instruction is predicated on a constant value, convert it 1150b57cec5SDimitry Andric /// into an unconditional branch to the constant destination. 1160b57cec5SDimitry Andric /// This is a nontrivial operation because the successors of this basic block 1170b57cec5SDimitry Andric /// must have their PHI nodes updated. 1180b57cec5SDimitry Andric /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch 1190b57cec5SDimitry Andric /// conditions and indirectbr addresses this might make dead if 1200b57cec5SDimitry Andric /// DeleteDeadConditions is true. 1210b57cec5SDimitry Andric bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false, 1220b57cec5SDimitry Andric const TargetLibraryInfo *TLI = nullptr, 1230b57cec5SDimitry Andric DomTreeUpdater *DTU = nullptr); 1240b57cec5SDimitry Andric 1250b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 1260b57cec5SDimitry Andric // Local dead code elimination. 1270b57cec5SDimitry Andric // 1280b57cec5SDimitry Andric 1290b57cec5SDimitry Andric /// Return true if the result produced by the instruction is not used, and the 1300b57cec5SDimitry Andric /// instruction has no side effects. 1310b57cec5SDimitry Andric bool isInstructionTriviallyDead(Instruction *I, 1320b57cec5SDimitry Andric const TargetLibraryInfo *TLI = nullptr); 1330b57cec5SDimitry Andric 1340b57cec5SDimitry Andric /// Return true if the result produced by the instruction would have no side 1350b57cec5SDimitry Andric /// effects if it was not used. This is equivalent to checking whether 1360b57cec5SDimitry Andric /// isInstructionTriviallyDead would be true if the use count was 0. 1370b57cec5SDimitry Andric bool wouldInstructionBeTriviallyDead(Instruction *I, 1380b57cec5SDimitry Andric const TargetLibraryInfo *TLI = nullptr); 1390b57cec5SDimitry Andric 1400b57cec5SDimitry Andric /// If the specified value is a trivially dead instruction, delete it. 1410b57cec5SDimitry Andric /// If that makes any of its operands trivially dead, delete them too, 1420b57cec5SDimitry Andric /// recursively. Return true if any instructions were deleted. 1430b57cec5SDimitry Andric bool RecursivelyDeleteTriviallyDeadInstructions( 1440b57cec5SDimitry Andric Value *V, const TargetLibraryInfo *TLI = nullptr, 1450b57cec5SDimitry Andric MemorySSAUpdater *MSSAU = nullptr); 1460b57cec5SDimitry Andric 1470b57cec5SDimitry Andric /// Delete all of the instructions in `DeadInsts`, and all other instructions 1480b57cec5SDimitry Andric /// that deleting these in turn causes to be trivially dead. 1490b57cec5SDimitry Andric /// 1500b57cec5SDimitry Andric /// The initial instructions in the provided vector must all have empty use 1510b57cec5SDimitry Andric /// lists and satisfy `isInstructionTriviallyDead`. 1520b57cec5SDimitry Andric /// 1530b57cec5SDimitry Andric /// `DeadInsts` will be used as scratch storage for this routine and will be 1540b57cec5SDimitry Andric /// empty afterward. 1550b57cec5SDimitry Andric void RecursivelyDeleteTriviallyDeadInstructions( 1560b57cec5SDimitry Andric SmallVectorImpl<Instruction *> &DeadInsts, 1570b57cec5SDimitry Andric const TargetLibraryInfo *TLI = nullptr, MemorySSAUpdater *MSSAU = nullptr); 1580b57cec5SDimitry Andric 1590b57cec5SDimitry Andric /// If the specified value is an effectively dead PHI node, due to being a 1600b57cec5SDimitry Andric /// def-use chain of single-use nodes that either forms a cycle or is terminated 1610b57cec5SDimitry Andric /// by a trivially dead instruction, delete it. If that makes any of its 1620b57cec5SDimitry Andric /// operands trivially dead, delete them too, recursively. Return true if a 1630b57cec5SDimitry Andric /// change was made. 1640b57cec5SDimitry Andric bool RecursivelyDeleteDeadPHINode(PHINode *PN, 1650b57cec5SDimitry Andric const TargetLibraryInfo *TLI = nullptr); 1660b57cec5SDimitry Andric 1670b57cec5SDimitry Andric /// Scan the specified basic block and try to simplify any instructions in it 1680b57cec5SDimitry Andric /// and recursively delete dead instructions. 1690b57cec5SDimitry Andric /// 1700b57cec5SDimitry Andric /// This returns true if it changed the code, note that it can delete 1710b57cec5SDimitry Andric /// instructions in other blocks as well in this block. 1720b57cec5SDimitry Andric bool SimplifyInstructionsInBlock(BasicBlock *BB, 1730b57cec5SDimitry Andric const TargetLibraryInfo *TLI = nullptr); 1740b57cec5SDimitry Andric 1750b57cec5SDimitry Andric /// Replace all the uses of an SSA value in @llvm.dbg intrinsics with 1760b57cec5SDimitry Andric /// undef. This is useful for signaling that a variable, e.g. has been 1770b57cec5SDimitry Andric /// found dead and hence it's unavailable at a given program point. 1780b57cec5SDimitry Andric /// Returns true if the dbg values have been changed. 1790b57cec5SDimitry Andric bool replaceDbgUsesWithUndef(Instruction *I); 1800b57cec5SDimitry Andric 1810b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 1820b57cec5SDimitry Andric // Control Flow Graph Restructuring. 1830b57cec5SDimitry Andric // 1840b57cec5SDimitry Andric 1850b57cec5SDimitry Andric /// Like BasicBlock::removePredecessor, this method is called when we're about 1860b57cec5SDimitry Andric /// to delete Pred as a predecessor of BB. If BB contains any PHI nodes, this 1870b57cec5SDimitry Andric /// drops the entries in the PHI nodes for Pred. 1880b57cec5SDimitry Andric /// 1890b57cec5SDimitry Andric /// Unlike the removePredecessor method, this attempts to simplify uses of PHI 1900b57cec5SDimitry Andric /// nodes that collapse into identity values. For example, if we have: 1910b57cec5SDimitry Andric /// x = phi(1, 0, 0, 0) 1920b57cec5SDimitry Andric /// y = and x, z 1930b57cec5SDimitry Andric /// 1940b57cec5SDimitry Andric /// .. and delete the predecessor corresponding to the '1', this will attempt to 1950b57cec5SDimitry Andric /// recursively fold the 'and' to 0. 1960b57cec5SDimitry Andric void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, 1970b57cec5SDimitry Andric DomTreeUpdater *DTU = nullptr); 1980b57cec5SDimitry Andric 1990b57cec5SDimitry Andric /// BB is a block with one predecessor and its predecessor is known to have one 2000b57cec5SDimitry Andric /// successor (BB!). Eliminate the edge between them, moving the instructions in 2010b57cec5SDimitry Andric /// the predecessor into BB. This deletes the predecessor block. 2020b57cec5SDimitry Andric void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DomTreeUpdater *DTU = nullptr); 2030b57cec5SDimitry Andric 2040b57cec5SDimitry Andric /// BB is known to contain an unconditional branch, and contains no instructions 2050b57cec5SDimitry Andric /// other than PHI nodes, potential debug intrinsics and the branch. If 2060b57cec5SDimitry Andric /// possible, eliminate BB by rewriting all the predecessors to branch to the 2070b57cec5SDimitry Andric /// successor block and return true. If we can't transform, return false. 2080b57cec5SDimitry Andric bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, 2090b57cec5SDimitry Andric DomTreeUpdater *DTU = nullptr); 2100b57cec5SDimitry Andric 2110b57cec5SDimitry Andric /// Check for and eliminate duplicate PHI nodes in this block. This doesn't try 2120b57cec5SDimitry Andric /// to be clever about PHI nodes which differ only in the order of the incoming 2130b57cec5SDimitry Andric /// values, but instcombine orders them so it usually won't matter. 2140b57cec5SDimitry Andric bool EliminateDuplicatePHINodes(BasicBlock *BB); 2150b57cec5SDimitry Andric 2160b57cec5SDimitry Andric /// This function is used to do simplification of a CFG. For example, it 2170b57cec5SDimitry Andric /// adjusts branches to branches to eliminate the extra hop, it eliminates 2180b57cec5SDimitry Andric /// unreachable basic blocks, and does other peephole optimization of the CFG. 2190b57cec5SDimitry Andric /// It returns true if a modification was made, possibly deleting the basic 2200b57cec5SDimitry Andric /// block that was pointed to. LoopHeaders is an optional input parameter 2210b57cec5SDimitry Andric /// providing the set of loop headers that SimplifyCFG should not eliminate. 2220b57cec5SDimitry Andric bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, 2230b57cec5SDimitry Andric const SimplifyCFGOptions &Options = {}, 2240b57cec5SDimitry Andric SmallPtrSetImpl<BasicBlock *> *LoopHeaders = nullptr); 2250b57cec5SDimitry Andric 2260b57cec5SDimitry Andric /// This function is used to flatten a CFG. For example, it uses parallel-and 2270b57cec5SDimitry Andric /// and parallel-or mode to collapse if-conditions and merge if-regions with 2280b57cec5SDimitry Andric /// identical statements. 2290b57cec5SDimitry Andric bool FlattenCFG(BasicBlock *BB, AliasAnalysis *AA = nullptr); 2300b57cec5SDimitry Andric 2310b57cec5SDimitry Andric /// If this basic block is ONLY a setcc and a branch, and if a predecessor 2320b57cec5SDimitry Andric /// branches to us and one of our successors, fold the setcc into the 2330b57cec5SDimitry Andric /// predecessor and use logical operations to pick the right destination. 2340b57cec5SDimitry Andric bool FoldBranchToCommonDest(BranchInst *BI, MemorySSAUpdater *MSSAU = nullptr, 2350b57cec5SDimitry Andric unsigned BonusInstThreshold = 1); 2360b57cec5SDimitry Andric 2370b57cec5SDimitry Andric /// This function takes a virtual register computed by an Instruction and 2380b57cec5SDimitry Andric /// replaces it with a slot in the stack frame, allocated via alloca. 2390b57cec5SDimitry Andric /// This allows the CFG to be changed around without fear of invalidating the 2400b57cec5SDimitry Andric /// SSA information for the value. It returns the pointer to the alloca inserted 2410b57cec5SDimitry Andric /// to create a stack slot for X. 2420b57cec5SDimitry Andric AllocaInst *DemoteRegToStack(Instruction &X, 2430b57cec5SDimitry Andric bool VolatileLoads = false, 2440b57cec5SDimitry Andric Instruction *AllocaPoint = nullptr); 2450b57cec5SDimitry Andric 2460b57cec5SDimitry Andric /// This function takes a virtual register computed by a phi node and replaces 2470b57cec5SDimitry Andric /// it with a slot in the stack frame, allocated via alloca. The phi node is 2480b57cec5SDimitry Andric /// deleted and it returns the pointer to the alloca inserted. 2490b57cec5SDimitry Andric AllocaInst *DemotePHIToStack(PHINode *P, Instruction *AllocaPoint = nullptr); 2500b57cec5SDimitry Andric 2510b57cec5SDimitry Andric /// Try to ensure that the alignment of \p V is at least \p PrefAlign bytes. If 2520b57cec5SDimitry Andric /// the owning object can be modified and has an alignment less than \p 2530b57cec5SDimitry Andric /// PrefAlign, it will be increased and \p PrefAlign returned. If the alignment 2540b57cec5SDimitry Andric /// cannot be increased, the known alignment of the value is returned. 2550b57cec5SDimitry Andric /// 2560b57cec5SDimitry Andric /// It is not always possible to modify the alignment of the underlying object, 2570b57cec5SDimitry Andric /// so if alignment is important, a more reliable approach is to simply align 2580b57cec5SDimitry Andric /// all global variables and allocation instructions to their preferred 2590b57cec5SDimitry Andric /// alignment from the beginning. 2600b57cec5SDimitry Andric unsigned getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, 2610b57cec5SDimitry Andric const DataLayout &DL, 2620b57cec5SDimitry Andric const Instruction *CxtI = nullptr, 2630b57cec5SDimitry Andric AssumptionCache *AC = nullptr, 2640b57cec5SDimitry Andric const DominatorTree *DT = nullptr); 2650b57cec5SDimitry Andric 2660b57cec5SDimitry Andric /// Try to infer an alignment for the specified pointer. 2670b57cec5SDimitry Andric inline unsigned getKnownAlignment(Value *V, const DataLayout &DL, 2680b57cec5SDimitry Andric const Instruction *CxtI = nullptr, 2690b57cec5SDimitry Andric AssumptionCache *AC = nullptr, 2700b57cec5SDimitry Andric const DominatorTree *DT = nullptr) { 2710b57cec5SDimitry Andric return getOrEnforceKnownAlignment(V, 0, DL, CxtI, AC, DT); 2720b57cec5SDimitry Andric } 2730b57cec5SDimitry Andric 2748bcb0991SDimitry Andric /// Create a call that matches the invoke \p II in terms of arguments, 2758bcb0991SDimitry Andric /// attributes, debug information, etc. The call is not placed in a block and it 2768bcb0991SDimitry Andric /// will not have a name. The invoke instruction is not removed, nor are the 2778bcb0991SDimitry Andric /// uses replaced by the new call. 2788bcb0991SDimitry Andric CallInst *createCallMatchingInvoke(InvokeInst *II); 2798bcb0991SDimitry Andric 2808bcb0991SDimitry Andric /// This function converts the specified invoek into a normall call. 2818bcb0991SDimitry Andric void changeToCall(InvokeInst *II, DomTreeUpdater *DTU = nullptr); 2828bcb0991SDimitry Andric 2830b57cec5SDimitry Andric ///===---------------------------------------------------------------------===// 2840b57cec5SDimitry Andric /// Dbg Intrinsic utilities 2850b57cec5SDimitry Andric /// 2860b57cec5SDimitry Andric 2870b57cec5SDimitry Andric /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value 2880b57cec5SDimitry Andric /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic. 2890b57cec5SDimitry Andric void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, 2900b57cec5SDimitry Andric StoreInst *SI, DIBuilder &Builder); 2910b57cec5SDimitry Andric 2920b57cec5SDimitry Andric /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value 2930b57cec5SDimitry Andric /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic. 2940b57cec5SDimitry Andric void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, 2950b57cec5SDimitry Andric LoadInst *LI, DIBuilder &Builder); 2960b57cec5SDimitry Andric 2970b57cec5SDimitry Andric /// Inserts a llvm.dbg.value intrinsic after a phi that has an associated 2980b57cec5SDimitry Andric /// llvm.dbg.declare or llvm.dbg.addr intrinsic. 2990b57cec5SDimitry Andric void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, 3000b57cec5SDimitry Andric PHINode *LI, DIBuilder &Builder); 3010b57cec5SDimitry Andric 3020b57cec5SDimitry Andric /// Lowers llvm.dbg.declare intrinsics into appropriate set of 3030b57cec5SDimitry Andric /// llvm.dbg.value intrinsics. 3040b57cec5SDimitry Andric bool LowerDbgDeclare(Function &F); 3050b57cec5SDimitry Andric 3060b57cec5SDimitry Andric /// Propagate dbg.value intrinsics through the newly inserted PHIs. 3070b57cec5SDimitry Andric void insertDebugValuesForPHIs(BasicBlock *BB, 3080b57cec5SDimitry Andric SmallVectorImpl<PHINode *> &InsertedPHIs); 3090b57cec5SDimitry Andric 3100b57cec5SDimitry Andric /// Finds all intrinsics declaring local variables as living in the memory that 3110b57cec5SDimitry Andric /// 'V' points to. This may include a mix of dbg.declare and 3120b57cec5SDimitry Andric /// dbg.addr intrinsics. 3130b57cec5SDimitry Andric TinyPtrVector<DbgVariableIntrinsic *> FindDbgAddrUses(Value *V); 3140b57cec5SDimitry Andric 3150b57cec5SDimitry Andric /// Finds the llvm.dbg.value intrinsics describing a value. 3160b57cec5SDimitry Andric void findDbgValues(SmallVectorImpl<DbgValueInst *> &DbgValues, Value *V); 3170b57cec5SDimitry Andric 3180b57cec5SDimitry Andric /// Finds the debug info intrinsics describing a value. 3190b57cec5SDimitry Andric void findDbgUsers(SmallVectorImpl<DbgVariableIntrinsic *> &DbgInsts, Value *V); 3200b57cec5SDimitry Andric 3210b57cec5SDimitry Andric /// Replaces llvm.dbg.declare instruction when the address it 3220b57cec5SDimitry Andric /// describes is replaced with a new value. If Deref is true, an 3230b57cec5SDimitry Andric /// additional DW_OP_deref is prepended to the expression. If Offset 3240b57cec5SDimitry Andric /// is non-zero, a constant displacement is added to the expression 3250b57cec5SDimitry Andric /// (between the optional Deref operations). Offset can be negative. 3260b57cec5SDimitry Andric bool replaceDbgDeclare(Value *Address, Value *NewAddress, 3270b57cec5SDimitry Andric Instruction *InsertBefore, DIBuilder &Builder, 3280b57cec5SDimitry Andric uint8_t DIExprFlags, int Offset); 3290b57cec5SDimitry Andric 3300b57cec5SDimitry Andric /// Replaces llvm.dbg.declare instruction when the alloca it describes 3310b57cec5SDimitry Andric /// is replaced with a new value. If Deref is true, an additional 3320b57cec5SDimitry Andric /// DW_OP_deref is prepended to the expression. If Offset is non-zero, 3330b57cec5SDimitry Andric /// a constant displacement is added to the expression (between the 3340b57cec5SDimitry Andric /// optional Deref operations). Offset can be negative. The new 3350b57cec5SDimitry Andric /// llvm.dbg.declare is inserted immediately after AI. 3360b57cec5SDimitry Andric bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, 3370b57cec5SDimitry Andric DIBuilder &Builder, uint8_t DIExprFlags, 3380b57cec5SDimitry Andric int Offset); 3390b57cec5SDimitry Andric 3400b57cec5SDimitry Andric /// Replaces multiple llvm.dbg.value instructions when the alloca it describes 3410b57cec5SDimitry Andric /// is replaced with a new value. If Offset is non-zero, a constant displacement 3420b57cec5SDimitry Andric /// is added to the expression (after the mandatory Deref). Offset can be 3430b57cec5SDimitry Andric /// negative. New llvm.dbg.value instructions are inserted at the locations of 3440b57cec5SDimitry Andric /// the instructions they replace. 3450b57cec5SDimitry Andric void replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress, 3460b57cec5SDimitry Andric DIBuilder &Builder, int Offset = 0); 3470b57cec5SDimitry Andric 3480b57cec5SDimitry Andric /// Finds alloca where the value comes from. 3490b57cec5SDimitry Andric AllocaInst *findAllocaForValue(Value *V, 3500b57cec5SDimitry Andric DenseMap<Value *, AllocaInst *> &AllocaForValue); 3510b57cec5SDimitry Andric 3520b57cec5SDimitry Andric /// Assuming the instruction \p I is going to be deleted, attempt to salvage 3530b57cec5SDimitry Andric /// debug users of \p I by writing the effect of \p I in a DIExpression. 3540b57cec5SDimitry Andric /// Returns true if any debug users were updated. 3550b57cec5SDimitry Andric bool salvageDebugInfo(Instruction &I); 3560b57cec5SDimitry Andric 3570b57cec5SDimitry Andric /// Implementation of salvageDebugInfo, applying only to instructions in 3580b57cec5SDimitry Andric /// \p Insns, rather than all debug users of \p I. 3590b57cec5SDimitry Andric bool salvageDebugInfoForDbgValues(Instruction &I, 3600b57cec5SDimitry Andric ArrayRef<DbgVariableIntrinsic *> Insns); 3610b57cec5SDimitry Andric 3620b57cec5SDimitry Andric /// Given an instruction \p I and DIExpression \p DIExpr operating on it, write 3630b57cec5SDimitry Andric /// the effects of \p I into the returned DIExpression, or return nullptr if 3640b57cec5SDimitry Andric /// it cannot be salvaged. \p StackVal: whether DW_OP_stack_value should be 3650b57cec5SDimitry Andric /// appended to the expression. 3660b57cec5SDimitry Andric DIExpression *salvageDebugInfoImpl(Instruction &I, DIExpression *DIExpr, 3670b57cec5SDimitry Andric bool StackVal); 3680b57cec5SDimitry Andric 3690b57cec5SDimitry Andric /// Point debug users of \p From to \p To or salvage them. Use this function 3700b57cec5SDimitry Andric /// only when replacing all uses of \p From with \p To, with a guarantee that 3710b57cec5SDimitry Andric /// \p From is going to be deleted. 3720b57cec5SDimitry Andric /// 3730b57cec5SDimitry Andric /// Follow these rules to prevent use-before-def of \p To: 3740b57cec5SDimitry Andric /// . If \p To is a linked Instruction, set \p DomPoint to \p To. 3750b57cec5SDimitry Andric /// . If \p To is an unlinked Instruction, set \p DomPoint to the Instruction 3760b57cec5SDimitry Andric /// \p To will be inserted after. 3770b57cec5SDimitry Andric /// . If \p To is not an Instruction (e.g a Constant), the choice of 3780b57cec5SDimitry Andric /// \p DomPoint is arbitrary. Pick \p From for simplicity. 3790b57cec5SDimitry Andric /// 3800b57cec5SDimitry Andric /// If a debug user cannot be preserved without reordering variable updates or 3810b57cec5SDimitry Andric /// introducing a use-before-def, it is either salvaged (\ref salvageDebugInfo) 3820b57cec5SDimitry Andric /// or deleted. Returns true if any debug users were updated. 3830b57cec5SDimitry Andric bool replaceAllDbgUsesWith(Instruction &From, Value &To, Instruction &DomPoint, 3840b57cec5SDimitry Andric DominatorTree &DT); 3850b57cec5SDimitry Andric 3860b57cec5SDimitry Andric /// Remove all instructions from a basic block other than it's terminator 3870b57cec5SDimitry Andric /// and any present EH pad instructions. 3880b57cec5SDimitry Andric unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB); 3890b57cec5SDimitry Andric 3900b57cec5SDimitry Andric /// Insert an unreachable instruction before the specified 3910b57cec5SDimitry Andric /// instruction, making it and the rest of the code in the block dead. 3920b57cec5SDimitry Andric unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap, 3930b57cec5SDimitry Andric bool PreserveLCSSA = false, 3940b57cec5SDimitry Andric DomTreeUpdater *DTU = nullptr, 3950b57cec5SDimitry Andric MemorySSAUpdater *MSSAU = nullptr); 3960b57cec5SDimitry Andric 3970b57cec5SDimitry Andric /// Convert the CallInst to InvokeInst with the specified unwind edge basic 3980b57cec5SDimitry Andric /// block. This also splits the basic block where CI is located, because 3990b57cec5SDimitry Andric /// InvokeInst is a terminator instruction. Returns the newly split basic 4000b57cec5SDimitry Andric /// block. 4010b57cec5SDimitry Andric BasicBlock *changeToInvokeAndSplitBasicBlock(CallInst *CI, 4020b57cec5SDimitry Andric BasicBlock *UnwindEdge); 4030b57cec5SDimitry Andric 4040b57cec5SDimitry Andric /// Replace 'BB's terminator with one that does not have an unwind successor 4050b57cec5SDimitry Andric /// block. Rewrites `invoke` to `call`, etc. Updates any PHIs in unwind 4060b57cec5SDimitry Andric /// successor. 4070b57cec5SDimitry Andric /// 4080b57cec5SDimitry Andric /// \param BB Block whose terminator will be replaced. Its terminator must 4090b57cec5SDimitry Andric /// have an unwind successor. 4100b57cec5SDimitry Andric void removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU = nullptr); 4110b57cec5SDimitry Andric 4120b57cec5SDimitry Andric /// Remove all blocks that can not be reached from the function's entry. 4130b57cec5SDimitry Andric /// 4140b57cec5SDimitry Andric /// Returns true if any basic block was removed. 4158bcb0991SDimitry Andric bool removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU = nullptr, 4160b57cec5SDimitry Andric MemorySSAUpdater *MSSAU = nullptr); 4170b57cec5SDimitry Andric 4180b57cec5SDimitry Andric /// Combine the metadata of two instructions so that K can replace J. Some 4190b57cec5SDimitry Andric /// metadata kinds can only be kept if K does not move, meaning it dominated 4200b57cec5SDimitry Andric /// J in the original IR. 4210b57cec5SDimitry Andric /// 4220b57cec5SDimitry Andric /// Metadata not listed as known via KnownIDs is removed 4230b57cec5SDimitry Andric void combineMetadata(Instruction *K, const Instruction *J, 4240b57cec5SDimitry Andric ArrayRef<unsigned> KnownIDs, bool DoesKMove); 4250b57cec5SDimitry Andric 4260b57cec5SDimitry Andric /// Combine the metadata of two instructions so that K can replace J. This 4270b57cec5SDimitry Andric /// specifically handles the case of CSE-like transformations. Some 4280b57cec5SDimitry Andric /// metadata can only be kept if K dominates J. For this to be correct, 4290b57cec5SDimitry Andric /// K cannot be hoisted. 4300b57cec5SDimitry Andric /// 4310b57cec5SDimitry Andric /// Unknown metadata is removed. 4320b57cec5SDimitry Andric void combineMetadataForCSE(Instruction *K, const Instruction *J, 4330b57cec5SDimitry Andric bool DoesKMove); 4340b57cec5SDimitry Andric 4358bcb0991SDimitry Andric /// Copy the metadata from the source instruction to the destination (the 4368bcb0991SDimitry Andric /// replacement for the source instruction). 4378bcb0991SDimitry Andric void copyMetadataForLoad(LoadInst &Dest, const LoadInst &Source); 4388bcb0991SDimitry Andric 4390b57cec5SDimitry Andric /// Patch the replacement so that it is not more restrictive than the value 4400b57cec5SDimitry Andric /// being replaced. It assumes that the replacement does not get moved from 4410b57cec5SDimitry Andric /// its original position. 4420b57cec5SDimitry Andric void patchReplacementInstruction(Instruction *I, Value *Repl); 4430b57cec5SDimitry Andric 4440b57cec5SDimitry Andric // Replace each use of 'From' with 'To', if that use does not belong to basic 4450b57cec5SDimitry Andric // block where 'From' is defined. Returns the number of replacements made. 4460b57cec5SDimitry Andric unsigned replaceNonLocalUsesWith(Instruction *From, Value *To); 4470b57cec5SDimitry Andric 4480b57cec5SDimitry Andric /// Replace each use of 'From' with 'To' if that use is dominated by 4490b57cec5SDimitry Andric /// the given edge. Returns the number of replacements made. 4500b57cec5SDimitry Andric unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, 4510b57cec5SDimitry Andric const BasicBlockEdge &Edge); 4520b57cec5SDimitry Andric /// Replace each use of 'From' with 'To' if that use is dominated by 4530b57cec5SDimitry Andric /// the end of the given BasicBlock. Returns the number of replacements made. 4540b57cec5SDimitry Andric unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, 4550b57cec5SDimitry Andric const BasicBlock *BB); 4560b57cec5SDimitry Andric 4570b57cec5SDimitry Andric /// Return true if this call calls a gc leaf function. 4580b57cec5SDimitry Andric /// 4590b57cec5SDimitry Andric /// A leaf function is a function that does not safepoint the thread during its 4600b57cec5SDimitry Andric /// execution. During a call or invoke to such a function, the callers stack 4610b57cec5SDimitry Andric /// does not have to be made parseable. 4620b57cec5SDimitry Andric /// 4630b57cec5SDimitry Andric /// Most passes can and should ignore this information, and it is only used 4640b57cec5SDimitry Andric /// during lowering by the GC infrastructure. 4650b57cec5SDimitry Andric bool callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI); 4660b57cec5SDimitry Andric 4670b57cec5SDimitry Andric /// Copy a nonnull metadata node to a new load instruction. 4680b57cec5SDimitry Andric /// 4690b57cec5SDimitry Andric /// This handles mapping it to range metadata if the new load is an integer 4700b57cec5SDimitry Andric /// load instead of a pointer load. 4710b57cec5SDimitry Andric void copyNonnullMetadata(const LoadInst &OldLI, MDNode *N, LoadInst &NewLI); 4720b57cec5SDimitry Andric 4730b57cec5SDimitry Andric /// Copy a range metadata node to a new load instruction. 4740b57cec5SDimitry Andric /// 4750b57cec5SDimitry Andric /// This handles mapping it to nonnull metadata if the new load is a pointer 4760b57cec5SDimitry Andric /// load instead of an integer load and the range doesn't cover null. 4770b57cec5SDimitry Andric void copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI, MDNode *N, 4780b57cec5SDimitry Andric LoadInst &NewLI); 4790b57cec5SDimitry Andric 4800b57cec5SDimitry Andric /// Remove the debug intrinsic instructions for the given instruction. 4810b57cec5SDimitry Andric void dropDebugUsers(Instruction &I); 4820b57cec5SDimitry Andric 4830b57cec5SDimitry Andric /// Hoist all of the instructions in the \p IfBlock to the dominant block 4840b57cec5SDimitry Andric /// \p DomBlock, by moving its instructions to the insertion point \p InsertPt. 4850b57cec5SDimitry Andric /// 4860b57cec5SDimitry Andric /// The moved instructions receive the insertion point debug location values 4870b57cec5SDimitry Andric /// (DILocations) and their debug intrinsic instructions are removed. 4880b57cec5SDimitry Andric void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, 4890b57cec5SDimitry Andric BasicBlock *BB); 4900b57cec5SDimitry Andric 4910b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 4920b57cec5SDimitry Andric // Intrinsic pattern matching 4930b57cec5SDimitry Andric // 4940b57cec5SDimitry Andric 4950b57cec5SDimitry Andric /// Try to match a bswap or bitreverse idiom. 4960b57cec5SDimitry Andric /// 4970b57cec5SDimitry Andric /// If an idiom is matched, an intrinsic call is inserted before \c I. Any added 4980b57cec5SDimitry Andric /// instructions are returned in \c InsertedInsts. They will all have been added 4990b57cec5SDimitry Andric /// to a basic block. 5000b57cec5SDimitry Andric /// 5010b57cec5SDimitry Andric /// A bitreverse idiom normally requires around 2*BW nodes to be searched (where 5020b57cec5SDimitry Andric /// BW is the bitwidth of the integer type). A bswap idiom requires anywhere up 5030b57cec5SDimitry Andric /// to BW / 4 nodes to be searched, so is significantly faster. 5040b57cec5SDimitry Andric /// 5050b57cec5SDimitry Andric /// This function returns true on a successful match or false otherwise. 5060b57cec5SDimitry Andric bool recognizeBSwapOrBitReverseIdiom( 5070b57cec5SDimitry Andric Instruction *I, bool MatchBSwaps, bool MatchBitReversals, 5080b57cec5SDimitry Andric SmallVectorImpl<Instruction *> &InsertedInsts); 5090b57cec5SDimitry Andric 5100b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 5110b57cec5SDimitry Andric // Sanitizer utilities 5120b57cec5SDimitry Andric // 5130b57cec5SDimitry Andric 5140b57cec5SDimitry Andric /// Given a CallInst, check if it calls a string function known to CodeGen, 5150b57cec5SDimitry Andric /// and mark it with NoBuiltin if so. To be used by sanitizers that intend 5160b57cec5SDimitry Andric /// to intercept string functions and want to avoid converting them to target 5170b57cec5SDimitry Andric /// specific instructions. 5180b57cec5SDimitry Andric void maybeMarkSanitizerLibraryCallNoBuiltin(CallInst *CI, 5190b57cec5SDimitry Andric const TargetLibraryInfo *TLI); 5200b57cec5SDimitry Andric 5210b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 5220b57cec5SDimitry Andric // Transform predicates 5230b57cec5SDimitry Andric // 5240b57cec5SDimitry Andric 5250b57cec5SDimitry Andric /// Given an instruction, is it legal to set operand OpIdx to a non-constant 5260b57cec5SDimitry Andric /// value? 5270b57cec5SDimitry Andric bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx); 5280b57cec5SDimitry Andric 5290b57cec5SDimitry Andric } // end namespace llvm 5300b57cec5SDimitry Andric 5310b57cec5SDimitry Andric #endif // LLVM_TRANSFORMS_UTILS_LOCAL_H 532