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/IR/Dominators.h" 19e8d8bef9SDimitry Andric #include "llvm/Support/CommandLine.h" 20e8d8bef9SDimitry Andric #include "llvm/Transforms/Utils/SimplifyCFGOptions.h" 210b57cec5SDimitry Andric #include <cstdint> 220b57cec5SDimitry Andric 230b57cec5SDimitry Andric namespace llvm { 240b57cec5SDimitry Andric 2581ad6265SDimitry Andric class DataLayout; 2681ad6265SDimitry Andric class Value; 2781ad6265SDimitry Andric class WeakTrackingVH; 2881ad6265SDimitry Andric class WeakVH; 2981ad6265SDimitry Andric template <typename T> class SmallVectorImpl; 305ffd83dbSDimitry Andric class AAResults; 310b57cec5SDimitry Andric class AllocaInst; 320b57cec5SDimitry Andric class AssumptionCache; 330b57cec5SDimitry Andric class BasicBlock; 340b57cec5SDimitry Andric class BranchInst; 355ffd83dbSDimitry Andric class CallBase; 360b57cec5SDimitry Andric class CallInst; 370b57cec5SDimitry Andric class DbgVariableIntrinsic; 380b57cec5SDimitry Andric class DIBuilder; 395ffd83dbSDimitry Andric class DomTreeUpdater; 400b57cec5SDimitry Andric class Function; 410b57cec5SDimitry Andric class Instruction; 425ffd83dbSDimitry Andric class InvokeInst; 430b57cec5SDimitry Andric class LoadInst; 440b57cec5SDimitry Andric class MDNode; 450b57cec5SDimitry Andric class MemorySSAUpdater; 460b57cec5SDimitry Andric class PHINode; 470b57cec5SDimitry Andric class StoreInst; 480b57cec5SDimitry Andric class TargetLibraryInfo; 490b57cec5SDimitry Andric class TargetTransformInfo; 500b57cec5SDimitry Andric 510b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 520b57cec5SDimitry Andric // Local constant propagation. 530b57cec5SDimitry Andric // 540b57cec5SDimitry Andric 550b57cec5SDimitry Andric /// If a terminator instruction is predicated on a constant value, convert it 560b57cec5SDimitry Andric /// into an unconditional branch to the constant destination. 570b57cec5SDimitry Andric /// This is a nontrivial operation because the successors of this basic block 580b57cec5SDimitry Andric /// must have their PHI nodes updated. 590b57cec5SDimitry Andric /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch 600b57cec5SDimitry Andric /// conditions and indirectbr addresses this might make dead if 610b57cec5SDimitry Andric /// DeleteDeadConditions is true. 620b57cec5SDimitry Andric bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false, 630b57cec5SDimitry Andric const TargetLibraryInfo *TLI = nullptr, 640b57cec5SDimitry Andric DomTreeUpdater *DTU = nullptr); 650b57cec5SDimitry Andric 660b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 670b57cec5SDimitry Andric // Local dead code elimination. 680b57cec5SDimitry Andric // 690b57cec5SDimitry Andric 700b57cec5SDimitry Andric /// Return true if the result produced by the instruction is not used, and the 71349cc55cSDimitry Andric /// instruction will return. Certain side-effecting instructions are also 72349cc55cSDimitry Andric /// considered dead if there are no uses of the instruction. 730b57cec5SDimitry Andric bool isInstructionTriviallyDead(Instruction *I, 740b57cec5SDimitry Andric const TargetLibraryInfo *TLI = nullptr); 750b57cec5SDimitry Andric 760b57cec5SDimitry Andric /// Return true if the result produced by the instruction would have no side 770b57cec5SDimitry Andric /// effects if it was not used. This is equivalent to checking whether 780b57cec5SDimitry Andric /// isInstructionTriviallyDead would be true if the use count was 0. 795f757f3fSDimitry Andric bool wouldInstructionBeTriviallyDead(const Instruction *I, 800b57cec5SDimitry Andric const TargetLibraryInfo *TLI = nullptr); 810b57cec5SDimitry Andric 820eae32dcSDimitry Andric /// Return true if the result produced by the instruction has no side effects on 830eae32dcSDimitry Andric /// any paths other than where it is used. This is less conservative than 840eae32dcSDimitry Andric /// wouldInstructionBeTriviallyDead which is based on the assumption 850eae32dcSDimitry Andric /// that the use count will be 0. An example usage of this API is for 860eae32dcSDimitry Andric /// identifying instructions that can be sunk down to use(s). 870eae32dcSDimitry Andric bool wouldInstructionBeTriviallyDeadOnUnusedPaths( 880eae32dcSDimitry Andric Instruction *I, const TargetLibraryInfo *TLI = nullptr); 890eae32dcSDimitry Andric 900b57cec5SDimitry Andric /// If the specified value is a trivially dead instruction, delete it. 910b57cec5SDimitry Andric /// If that makes any of its operands trivially dead, delete them too, 920b57cec5SDimitry Andric /// recursively. Return true if any instructions were deleted. 930b57cec5SDimitry Andric bool RecursivelyDeleteTriviallyDeadInstructions( 940b57cec5SDimitry Andric Value *V, const TargetLibraryInfo *TLI = nullptr, 95e8d8bef9SDimitry Andric MemorySSAUpdater *MSSAU = nullptr, 96e8d8bef9SDimitry Andric std::function<void(Value *)> AboutToDeleteCallback = 97e8d8bef9SDimitry Andric std::function<void(Value *)>()); 980b57cec5SDimitry Andric 990b57cec5SDimitry Andric /// Delete all of the instructions in `DeadInsts`, and all other instructions 1000b57cec5SDimitry Andric /// that deleting these in turn causes to be trivially dead. 1010b57cec5SDimitry Andric /// 1020b57cec5SDimitry Andric /// The initial instructions in the provided vector must all have empty use 1030b57cec5SDimitry Andric /// lists and satisfy `isInstructionTriviallyDead`. 1040b57cec5SDimitry Andric /// 1050b57cec5SDimitry Andric /// `DeadInsts` will be used as scratch storage for this routine and will be 1060b57cec5SDimitry Andric /// empty afterward. 1070b57cec5SDimitry Andric void RecursivelyDeleteTriviallyDeadInstructions( 1085ffd83dbSDimitry Andric SmallVectorImpl<WeakTrackingVH> &DeadInsts, 109e8d8bef9SDimitry Andric const TargetLibraryInfo *TLI = nullptr, MemorySSAUpdater *MSSAU = nullptr, 110e8d8bef9SDimitry Andric std::function<void(Value *)> AboutToDeleteCallback = 111e8d8bef9SDimitry Andric std::function<void(Value *)>()); 1125ffd83dbSDimitry Andric 1135ffd83dbSDimitry Andric /// Same functionality as RecursivelyDeleteTriviallyDeadInstructions, but allow 1145ffd83dbSDimitry Andric /// instructions that are not trivially dead. These will be ignored. 1155ffd83dbSDimitry Andric /// Returns true if any changes were made, i.e. any instructions trivially dead 1165ffd83dbSDimitry Andric /// were found and deleted. 1175ffd83dbSDimitry Andric bool RecursivelyDeleteTriviallyDeadInstructionsPermissive( 1185ffd83dbSDimitry Andric SmallVectorImpl<WeakTrackingVH> &DeadInsts, 119e8d8bef9SDimitry Andric const TargetLibraryInfo *TLI = nullptr, MemorySSAUpdater *MSSAU = nullptr, 120e8d8bef9SDimitry Andric std::function<void(Value *)> AboutToDeleteCallback = 121e8d8bef9SDimitry Andric std::function<void(Value *)>()); 1220b57cec5SDimitry Andric 1230b57cec5SDimitry Andric /// If the specified value is an effectively dead PHI node, due to being a 1240b57cec5SDimitry Andric /// def-use chain of single-use nodes that either forms a cycle or is terminated 1250b57cec5SDimitry Andric /// by a trivially dead instruction, delete it. If that makes any of its 1260b57cec5SDimitry Andric /// operands trivially dead, delete them too, recursively. Return true if a 1270b57cec5SDimitry Andric /// change was made. 1280b57cec5SDimitry Andric bool RecursivelyDeleteDeadPHINode(PHINode *PN, 1295ffd83dbSDimitry Andric const TargetLibraryInfo *TLI = nullptr, 1305ffd83dbSDimitry Andric MemorySSAUpdater *MSSAU = nullptr); 1310b57cec5SDimitry Andric 1320b57cec5SDimitry Andric /// Scan the specified basic block and try to simplify any instructions in it 1330b57cec5SDimitry Andric /// and recursively delete dead instructions. 1340b57cec5SDimitry Andric /// 1350b57cec5SDimitry Andric /// This returns true if it changed the code, note that it can delete 1360b57cec5SDimitry Andric /// instructions in other blocks as well in this block. 1370b57cec5SDimitry Andric bool SimplifyInstructionsInBlock(BasicBlock *BB, 1380b57cec5SDimitry Andric const TargetLibraryInfo *TLI = nullptr); 1390b57cec5SDimitry Andric 1400b57cec5SDimitry Andric /// Replace all the uses of an SSA value in @llvm.dbg intrinsics with 1410b57cec5SDimitry Andric /// undef. This is useful for signaling that a variable, e.g. has been 1420b57cec5SDimitry Andric /// found dead and hence it's unavailable at a given program point. 1430b57cec5SDimitry Andric /// Returns true if the dbg values have been changed. 1440b57cec5SDimitry Andric bool replaceDbgUsesWithUndef(Instruction *I); 1450b57cec5SDimitry Andric 1460b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 1470b57cec5SDimitry Andric // Control Flow Graph Restructuring. 1480b57cec5SDimitry Andric // 1490b57cec5SDimitry Andric 1500b57cec5SDimitry Andric /// BB is a block with one predecessor and its predecessor is known to have one 1510b57cec5SDimitry Andric /// successor (BB!). Eliminate the edge between them, moving the instructions in 1520b57cec5SDimitry Andric /// the predecessor into BB. This deletes the predecessor block. 1530b57cec5SDimitry Andric void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DomTreeUpdater *DTU = nullptr); 1540b57cec5SDimitry Andric 1550b57cec5SDimitry Andric /// BB is known to contain an unconditional branch, and contains no instructions 1560b57cec5SDimitry Andric /// other than PHI nodes, potential debug intrinsics and the branch. If 1570b57cec5SDimitry Andric /// possible, eliminate BB by rewriting all the predecessors to branch to the 1580b57cec5SDimitry Andric /// successor block and return true. If we can't transform, return false. 1590b57cec5SDimitry Andric bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, 1600b57cec5SDimitry Andric DomTreeUpdater *DTU = nullptr); 1610b57cec5SDimitry Andric 1620b57cec5SDimitry Andric /// Check for and eliminate duplicate PHI nodes in this block. This doesn't try 1630b57cec5SDimitry Andric /// to be clever about PHI nodes which differ only in the order of the incoming 1640b57cec5SDimitry Andric /// values, but instcombine orders them so it usually won't matter. 1654542f901SDimitry Andric /// 1664542f901SDimitry Andric /// This overload removes the duplicate PHI nodes directly. 1670b57cec5SDimitry Andric bool EliminateDuplicatePHINodes(BasicBlock *BB); 1680b57cec5SDimitry Andric 1694542f901SDimitry Andric /// Check for and eliminate duplicate PHI nodes in this block. This doesn't try 1704542f901SDimitry Andric /// to be clever about PHI nodes which differ only in the order of the incoming 1714542f901SDimitry Andric /// values, but instcombine orders them so it usually won't matter. 1724542f901SDimitry Andric /// 1734542f901SDimitry Andric /// This overload collects the PHI nodes to be removed into the ToRemove set. 1744542f901SDimitry Andric bool EliminateDuplicatePHINodes(BasicBlock *BB, 1754542f901SDimitry Andric SmallPtrSetImpl<PHINode *> &ToRemove); 1764542f901SDimitry Andric 1770b57cec5SDimitry Andric /// This function is used to do simplification of a CFG. For example, it 1780b57cec5SDimitry Andric /// adjusts branches to branches to eliminate the extra hop, it eliminates 1790b57cec5SDimitry Andric /// unreachable basic blocks, and does other peephole optimization of the CFG. 1800b57cec5SDimitry Andric /// It returns true if a modification was made, possibly deleting the basic 1810b57cec5SDimitry Andric /// block that was pointed to. LoopHeaders is an optional input parameter 1820b57cec5SDimitry Andric /// providing the set of loop headers that SimplifyCFG should not eliminate. 183e8d8bef9SDimitry Andric extern cl::opt<bool> RequireAndPreserveDomTree; 1840b57cec5SDimitry Andric bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, 185e8d8bef9SDimitry Andric DomTreeUpdater *DTU = nullptr, 1860b57cec5SDimitry Andric const SimplifyCFGOptions &Options = {}, 187e8d8bef9SDimitry Andric ArrayRef<WeakVH> LoopHeaders = {}); 1880b57cec5SDimitry Andric 1890b57cec5SDimitry Andric /// This function is used to flatten a CFG. For example, it uses parallel-and 1900b57cec5SDimitry Andric /// and parallel-or mode to collapse if-conditions and merge if-regions with 1910b57cec5SDimitry Andric /// identical statements. 1925ffd83dbSDimitry Andric bool FlattenCFG(BasicBlock *BB, AAResults *AA = nullptr); 1930b57cec5SDimitry Andric 1940b57cec5SDimitry Andric /// If this basic block is ONLY a setcc and a branch, and if a predecessor 1950b57cec5SDimitry Andric /// branches to us and one of our successors, fold the setcc into the 1960b57cec5SDimitry Andric /// predecessor and use logical operations to pick the right destination. 197e8d8bef9SDimitry Andric bool FoldBranchToCommonDest(BranchInst *BI, llvm::DomTreeUpdater *DTU = nullptr, 198e8d8bef9SDimitry Andric MemorySSAUpdater *MSSAU = nullptr, 199e8d8bef9SDimitry Andric const TargetTransformInfo *TTI = nullptr, 2000b57cec5SDimitry Andric unsigned BonusInstThreshold = 1); 2010b57cec5SDimitry Andric 2020b57cec5SDimitry Andric /// This function takes a virtual register computed by an Instruction and 2030b57cec5SDimitry Andric /// replaces it with a slot in the stack frame, allocated via alloca. 2040b57cec5SDimitry Andric /// This allows the CFG to be changed around without fear of invalidating the 2050b57cec5SDimitry Andric /// SSA information for the value. It returns the pointer to the alloca inserted 2060b57cec5SDimitry Andric /// to create a stack slot for X. 2070b57cec5SDimitry Andric AllocaInst *DemoteRegToStack(Instruction &X, 2080b57cec5SDimitry Andric bool VolatileLoads = false, 2090b57cec5SDimitry Andric Instruction *AllocaPoint = nullptr); 2100b57cec5SDimitry Andric 2110b57cec5SDimitry Andric /// This function takes a virtual register computed by a phi node and replaces 2120b57cec5SDimitry Andric /// it with a slot in the stack frame, allocated via alloca. The phi node is 2130b57cec5SDimitry Andric /// deleted and it returns the pointer to the alloca inserted. 2140b57cec5SDimitry Andric AllocaInst *DemotePHIToStack(PHINode *P, Instruction *AllocaPoint = nullptr); 2150b57cec5SDimitry Andric 2165f757f3fSDimitry Andric /// If the specified pointer points to an object that we control, try to modify 2175f757f3fSDimitry Andric /// the object's alignment to PrefAlign. Returns a minimum known alignment of 2185f757f3fSDimitry Andric /// the value after the operation, which may be lower than PrefAlign. 2195f757f3fSDimitry Andric /// 2205f757f3fSDimitry Andric /// Increating value alignment isn't often possible though. If alignment is 2215f757f3fSDimitry Andric /// important, a more reliable approach is to simply align all global variables 2225f757f3fSDimitry Andric /// and allocation instructions to their preferred alignment from the beginning. 2235f757f3fSDimitry Andric Align tryEnforceAlignment(Value *V, Align PrefAlign, const DataLayout &DL); 2245f757f3fSDimitry Andric 2250b57cec5SDimitry Andric /// Try to ensure that the alignment of \p V is at least \p PrefAlign bytes. If 2260b57cec5SDimitry Andric /// the owning object can be modified and has an alignment less than \p 2270b57cec5SDimitry Andric /// PrefAlign, it will be increased and \p PrefAlign returned. If the alignment 2280b57cec5SDimitry Andric /// cannot be increased, the known alignment of the value is returned. 2290b57cec5SDimitry Andric /// 2300b57cec5SDimitry Andric /// It is not always possible to modify the alignment of the underlying object, 2310b57cec5SDimitry Andric /// so if alignment is important, a more reliable approach is to simply align 2320b57cec5SDimitry Andric /// all global variables and allocation instructions to their preferred 2330b57cec5SDimitry Andric /// alignment from the beginning. 2345ffd83dbSDimitry Andric Align getOrEnforceKnownAlignment(Value *V, MaybeAlign PrefAlign, 2350b57cec5SDimitry Andric const DataLayout &DL, 2360b57cec5SDimitry Andric const Instruction *CxtI = nullptr, 2370b57cec5SDimitry Andric AssumptionCache *AC = nullptr, 2380b57cec5SDimitry Andric const DominatorTree *DT = nullptr); 2390b57cec5SDimitry Andric 2400b57cec5SDimitry Andric /// Try to infer an alignment for the specified pointer. 2415ffd83dbSDimitry Andric inline Align getKnownAlignment(Value *V, const DataLayout &DL, 2420b57cec5SDimitry Andric const Instruction *CxtI = nullptr, 2430b57cec5SDimitry Andric AssumptionCache *AC = nullptr, 2440b57cec5SDimitry Andric const DominatorTree *DT = nullptr) { 2455ffd83dbSDimitry Andric return getOrEnforceKnownAlignment(V, MaybeAlign(), DL, CxtI, AC, DT); 2460b57cec5SDimitry Andric } 2470b57cec5SDimitry Andric 2488bcb0991SDimitry Andric /// Create a call that matches the invoke \p II in terms of arguments, 2498bcb0991SDimitry Andric /// attributes, debug information, etc. The call is not placed in a block and it 2508bcb0991SDimitry Andric /// will not have a name. The invoke instruction is not removed, nor are the 2518bcb0991SDimitry Andric /// uses replaced by the new call. 2528bcb0991SDimitry Andric CallInst *createCallMatchingInvoke(InvokeInst *II); 2538bcb0991SDimitry Andric 254bdd1243dSDimitry Andric /// This function converts the specified invoke into a normal call. 25504eeddc0SDimitry Andric CallInst *changeToCall(InvokeInst *II, DomTreeUpdater *DTU = nullptr); 2568bcb0991SDimitry Andric 2570b57cec5SDimitry Andric ///===---------------------------------------------------------------------===// 2580b57cec5SDimitry Andric /// Dbg Intrinsic utilities 2590b57cec5SDimitry Andric /// 2600b57cec5SDimitry Andric 2610b57cec5SDimitry Andric /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value 26206c3fb27SDimitry Andric /// that has an associated llvm.dbg.declare intrinsic. 2630b57cec5SDimitry Andric void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, 2640b57cec5SDimitry Andric StoreInst *SI, DIBuilder &Builder); 2655f757f3fSDimitry Andric void ConvertDebugDeclareToDebugValue(DPValue *DPV, StoreInst *SI, 2665f757f3fSDimitry Andric DIBuilder &Builder); 2670b57cec5SDimitry Andric 2680b57cec5SDimitry Andric /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value 26906c3fb27SDimitry Andric /// that has an associated llvm.dbg.declare intrinsic. 2700b57cec5SDimitry Andric void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, 2710b57cec5SDimitry Andric LoadInst *LI, DIBuilder &Builder); 2725f757f3fSDimitry Andric void ConvertDebugDeclareToDebugValue(DPValue *DPV, LoadInst *LI, 2735f757f3fSDimitry Andric DIBuilder &Builder); 2740b57cec5SDimitry Andric 2750b57cec5SDimitry Andric /// Inserts a llvm.dbg.value intrinsic after a phi that has an associated 27606c3fb27SDimitry Andric /// llvm.dbg.declare intrinsic. 2770b57cec5SDimitry Andric void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, 2780b57cec5SDimitry Andric PHINode *LI, DIBuilder &Builder); 2795f757f3fSDimitry Andric void ConvertDebugDeclareToDebugValue(DPValue *DPV, PHINode *LI, 2805f757f3fSDimitry Andric DIBuilder &Builder); 2810b57cec5SDimitry Andric 2820b57cec5SDimitry Andric /// Lowers llvm.dbg.declare intrinsics into appropriate set of 2830b57cec5SDimitry Andric /// llvm.dbg.value intrinsics. 2840b57cec5SDimitry Andric bool LowerDbgDeclare(Function &F); 2850b57cec5SDimitry Andric 2860b57cec5SDimitry Andric /// Propagate dbg.value intrinsics through the newly inserted PHIs. 2870b57cec5SDimitry Andric void insertDebugValuesForPHIs(BasicBlock *BB, 2880b57cec5SDimitry Andric SmallVectorImpl<PHINode *> &InsertedPHIs); 2890b57cec5SDimitry Andric 2900b57cec5SDimitry Andric /// Replaces llvm.dbg.declare instruction when the address it 2910b57cec5SDimitry Andric /// describes is replaced with a new value. If Deref is true, an 2920b57cec5SDimitry Andric /// additional DW_OP_deref is prepended to the expression. If Offset 2930b57cec5SDimitry Andric /// is non-zero, a constant displacement is added to the expression 2940b57cec5SDimitry Andric /// (between the optional Deref operations). Offset can be negative. 2955ffd83dbSDimitry Andric bool replaceDbgDeclare(Value *Address, Value *NewAddress, DIBuilder &Builder, 2960b57cec5SDimitry Andric uint8_t DIExprFlags, int Offset); 2970b57cec5SDimitry Andric 2980b57cec5SDimitry Andric /// Replaces multiple llvm.dbg.value instructions when the alloca it describes 2990b57cec5SDimitry Andric /// is replaced with a new value. If Offset is non-zero, a constant displacement 3000b57cec5SDimitry Andric /// is added to the expression (after the mandatory Deref). Offset can be 3010b57cec5SDimitry Andric /// negative. New llvm.dbg.value instructions are inserted at the locations of 3020b57cec5SDimitry Andric /// the instructions they replace. 3030b57cec5SDimitry Andric void replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress, 3040b57cec5SDimitry Andric DIBuilder &Builder, int Offset = 0); 3050b57cec5SDimitry Andric 3060b57cec5SDimitry Andric /// Assuming the instruction \p I is going to be deleted, attempt to salvage 3075ffd83dbSDimitry Andric /// debug users of \p I by writing the effect of \p I in a DIExpression. If it 3085ffd83dbSDimitry Andric /// cannot be salvaged changes its debug uses to undef. 3095ffd83dbSDimitry Andric void salvageDebugInfo(Instruction &I); 3100b57cec5SDimitry Andric 3110b57cec5SDimitry Andric /// Implementation of salvageDebugInfo, applying only to instructions in 3125ffd83dbSDimitry Andric /// \p Insns, rather than all debug users from findDbgUsers( \p I). 3135ffd83dbSDimitry Andric /// Mark undef if salvaging cannot be completed. 3145ffd83dbSDimitry Andric void salvageDebugInfoForDbgValues(Instruction &I, 3155f757f3fSDimitry Andric ArrayRef<DbgVariableIntrinsic *> Insns, 3165f757f3fSDimitry Andric ArrayRef<DPValue *> DPInsns); 3170b57cec5SDimitry Andric 318349cc55cSDimitry Andric /// Given an instruction \p I and DIExpression \p DIExpr operating on 319349cc55cSDimitry Andric /// it, append the effects of \p I to the DIExpression operand list 320349cc55cSDimitry Andric /// \p Ops, or return \p nullptr if it cannot be salvaged. 321349cc55cSDimitry Andric /// \p CurrentLocOps is the number of SSA values referenced by the 322349cc55cSDimitry Andric /// incoming \p Ops. \return the first non-constant operand 323349cc55cSDimitry Andric /// implicitly referred to by Ops. If \p I references more than one 324349cc55cSDimitry Andric /// non-constant operand, any additional operands are added to 325349cc55cSDimitry Andric /// \p AdditionalValues. 326349cc55cSDimitry Andric /// 327349cc55cSDimitry Andric /// \example 328349cc55cSDimitry Andric //// 329349cc55cSDimitry Andric /// I = add %a, i32 1 330349cc55cSDimitry Andric /// 331349cc55cSDimitry Andric /// Return = %a 332349cc55cSDimitry Andric /// Ops = llvm::dwarf::DW_OP_lit1 llvm::dwarf::DW_OP_add 333349cc55cSDimitry Andric /// 334349cc55cSDimitry Andric /// I = add %a, %b 335349cc55cSDimitry Andric /// 336349cc55cSDimitry Andric /// Return = %a 337349cc55cSDimitry Andric /// Ops = llvm::dwarf::DW_OP_LLVM_arg0 llvm::dwarf::DW_OP_add 338349cc55cSDimitry Andric /// AdditionalValues = %b 339349cc55cSDimitry Andric Value *salvageDebugInfoImpl(Instruction &I, uint64_t CurrentLocOps, 340349cc55cSDimitry Andric SmallVectorImpl<uint64_t> &Ops, 341fe6060f1SDimitry Andric SmallVectorImpl<Value *> &AdditionalValues); 3420b57cec5SDimitry Andric 3430b57cec5SDimitry Andric /// Point debug users of \p From to \p To or salvage them. Use this function 3440b57cec5SDimitry Andric /// only when replacing all uses of \p From with \p To, with a guarantee that 3450b57cec5SDimitry Andric /// \p From is going to be deleted. 3460b57cec5SDimitry Andric /// 3470b57cec5SDimitry Andric /// Follow these rules to prevent use-before-def of \p To: 3480b57cec5SDimitry Andric /// . If \p To is a linked Instruction, set \p DomPoint to \p To. 3490b57cec5SDimitry Andric /// . If \p To is an unlinked Instruction, set \p DomPoint to the Instruction 3500b57cec5SDimitry Andric /// \p To will be inserted after. 3510b57cec5SDimitry Andric /// . If \p To is not an Instruction (e.g a Constant), the choice of 3520b57cec5SDimitry Andric /// \p DomPoint is arbitrary. Pick \p From for simplicity. 3530b57cec5SDimitry Andric /// 3540b57cec5SDimitry Andric /// If a debug user cannot be preserved without reordering variable updates or 3550b57cec5SDimitry Andric /// introducing a use-before-def, it is either salvaged (\ref salvageDebugInfo) 3560b57cec5SDimitry Andric /// or deleted. Returns true if any debug users were updated. 3570b57cec5SDimitry Andric bool replaceAllDbgUsesWith(Instruction &From, Value &To, Instruction &DomPoint, 3580b57cec5SDimitry Andric DominatorTree &DT); 3590b57cec5SDimitry Andric 360e8d8bef9SDimitry Andric /// Remove all instructions from a basic block other than its terminator 361e8d8bef9SDimitry Andric /// and any present EH pad instructions. Returns a pair where the first element 36281ad6265SDimitry Andric /// is the number of instructions (excluding debug info intrinsics) that have 363e8d8bef9SDimitry Andric /// been removed, and the second element is the number of debug info intrinsics 364e8d8bef9SDimitry Andric /// that have been removed. 365e8d8bef9SDimitry Andric std::pair<unsigned, unsigned> 366e8d8bef9SDimitry Andric removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB); 3670b57cec5SDimitry Andric 3680b57cec5SDimitry Andric /// Insert an unreachable instruction before the specified 3690b57cec5SDimitry Andric /// instruction, making it and the rest of the code in the block dead. 370fe6060f1SDimitry Andric unsigned changeToUnreachable(Instruction *I, bool PreserveLCSSA = false, 3710b57cec5SDimitry Andric DomTreeUpdater *DTU = nullptr, 3720b57cec5SDimitry Andric MemorySSAUpdater *MSSAU = nullptr); 3730b57cec5SDimitry Andric 3740b57cec5SDimitry Andric /// Convert the CallInst to InvokeInst with the specified unwind edge basic 3750b57cec5SDimitry Andric /// block. This also splits the basic block where CI is located, because 3760b57cec5SDimitry Andric /// InvokeInst is a terminator instruction. Returns the newly split basic 3770b57cec5SDimitry Andric /// block. 3780b57cec5SDimitry Andric BasicBlock *changeToInvokeAndSplitBasicBlock(CallInst *CI, 379fe6060f1SDimitry Andric BasicBlock *UnwindEdge, 380fe6060f1SDimitry Andric DomTreeUpdater *DTU = nullptr); 3810b57cec5SDimitry Andric 3820b57cec5SDimitry Andric /// Replace 'BB's terminator with one that does not have an unwind successor 3830b57cec5SDimitry Andric /// block. Rewrites `invoke` to `call`, etc. Updates any PHIs in unwind 384bdd1243dSDimitry Andric /// successor. Returns the instruction that replaced the original terminator, 385bdd1243dSDimitry Andric /// which might be a call in case the original terminator was an invoke. 3860b57cec5SDimitry Andric /// 3870b57cec5SDimitry Andric /// \param BB Block whose terminator will be replaced. Its terminator must 3880b57cec5SDimitry Andric /// have an unwind successor. 389bdd1243dSDimitry Andric Instruction *removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU = nullptr); 3900b57cec5SDimitry Andric 3910b57cec5SDimitry Andric /// Remove all blocks that can not be reached from the function's entry. 3920b57cec5SDimitry Andric /// 3930b57cec5SDimitry Andric /// Returns true if any basic block was removed. 3948bcb0991SDimitry Andric bool removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU = nullptr, 3950b57cec5SDimitry Andric MemorySSAUpdater *MSSAU = nullptr); 3960b57cec5SDimitry Andric 3970b57cec5SDimitry Andric /// Combine the metadata of two instructions so that K can replace J. Some 3980b57cec5SDimitry Andric /// metadata kinds can only be kept if K does not move, meaning it dominated 3990b57cec5SDimitry Andric /// J in the original IR. 4000b57cec5SDimitry Andric /// 4010b57cec5SDimitry Andric /// Metadata not listed as known via KnownIDs is removed 4020b57cec5SDimitry Andric void combineMetadata(Instruction *K, const Instruction *J, 4030b57cec5SDimitry Andric ArrayRef<unsigned> KnownIDs, bool DoesKMove); 4040b57cec5SDimitry Andric 4050b57cec5SDimitry Andric /// Combine the metadata of two instructions so that K can replace J. This 4060b57cec5SDimitry Andric /// specifically handles the case of CSE-like transformations. Some 4070b57cec5SDimitry Andric /// metadata can only be kept if K dominates J. For this to be correct, 4080b57cec5SDimitry Andric /// K cannot be hoisted. 4090b57cec5SDimitry Andric /// 4100b57cec5SDimitry Andric /// Unknown metadata is removed. 4110b57cec5SDimitry Andric void combineMetadataForCSE(Instruction *K, const Instruction *J, 4120b57cec5SDimitry Andric bool DoesKMove); 4130b57cec5SDimitry Andric 4148bcb0991SDimitry Andric /// Copy the metadata from the source instruction to the destination (the 4158bcb0991SDimitry Andric /// replacement for the source instruction). 4168bcb0991SDimitry Andric void copyMetadataForLoad(LoadInst &Dest, const LoadInst &Source); 4178bcb0991SDimitry Andric 4180b57cec5SDimitry Andric /// Patch the replacement so that it is not more restrictive than the value 4190b57cec5SDimitry Andric /// being replaced. It assumes that the replacement does not get moved from 4200b57cec5SDimitry Andric /// its original position. 4210b57cec5SDimitry Andric void patchReplacementInstruction(Instruction *I, Value *Repl); 4220b57cec5SDimitry Andric 4230b57cec5SDimitry Andric // Replace each use of 'From' with 'To', if that use does not belong to basic 4240b57cec5SDimitry Andric // block where 'From' is defined. Returns the number of replacements made. 4250b57cec5SDimitry Andric unsigned replaceNonLocalUsesWith(Instruction *From, Value *To); 4260b57cec5SDimitry Andric 4270b57cec5SDimitry Andric /// Replace each use of 'From' with 'To' if that use is dominated by 4280b57cec5SDimitry Andric /// the given edge. Returns the number of replacements made. 4290b57cec5SDimitry Andric unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, 4300b57cec5SDimitry Andric const BasicBlockEdge &Edge); 4310b57cec5SDimitry Andric /// Replace each use of 'From' with 'To' if that use is dominated by 4320b57cec5SDimitry Andric /// the end of the given BasicBlock. Returns the number of replacements made. 4330b57cec5SDimitry Andric unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, 4340b57cec5SDimitry Andric const BasicBlock *BB); 4350b57cec5SDimitry Andric 4360b57cec5SDimitry Andric /// Return true if this call calls a gc leaf function. 4370b57cec5SDimitry Andric /// 4380b57cec5SDimitry Andric /// A leaf function is a function that does not safepoint the thread during its 4390b57cec5SDimitry Andric /// execution. During a call or invoke to such a function, the callers stack 4400b57cec5SDimitry Andric /// does not have to be made parseable. 4410b57cec5SDimitry Andric /// 4420b57cec5SDimitry Andric /// Most passes can and should ignore this information, and it is only used 4430b57cec5SDimitry Andric /// during lowering by the GC infrastructure. 4440b57cec5SDimitry Andric bool callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI); 4450b57cec5SDimitry Andric 4460b57cec5SDimitry Andric /// Copy a nonnull metadata node to a new load instruction. 4470b57cec5SDimitry Andric /// 4480b57cec5SDimitry Andric /// This handles mapping it to range metadata if the new load is an integer 4490b57cec5SDimitry Andric /// load instead of a pointer load. 4500b57cec5SDimitry Andric void copyNonnullMetadata(const LoadInst &OldLI, MDNode *N, LoadInst &NewLI); 4510b57cec5SDimitry Andric 4520b57cec5SDimitry Andric /// Copy a range metadata node to a new load instruction. 4530b57cec5SDimitry Andric /// 4540b57cec5SDimitry Andric /// This handles mapping it to nonnull metadata if the new load is a pointer 4550b57cec5SDimitry Andric /// load instead of an integer load and the range doesn't cover null. 4560b57cec5SDimitry Andric void copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI, MDNode *N, 4570b57cec5SDimitry Andric LoadInst &NewLI); 4580b57cec5SDimitry Andric 4590b57cec5SDimitry Andric /// Remove the debug intrinsic instructions for the given instruction. 4600b57cec5SDimitry Andric void dropDebugUsers(Instruction &I); 4610b57cec5SDimitry Andric 4620b57cec5SDimitry Andric /// Hoist all of the instructions in the \p IfBlock to the dominant block 4630b57cec5SDimitry Andric /// \p DomBlock, by moving its instructions to the insertion point \p InsertPt. 4640b57cec5SDimitry Andric /// 4650b57cec5SDimitry Andric /// The moved instructions receive the insertion point debug location values 4660b57cec5SDimitry Andric /// (DILocations) and their debug intrinsic instructions are removed. 4670b57cec5SDimitry Andric void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, 4680b57cec5SDimitry Andric BasicBlock *BB); 4690b57cec5SDimitry Andric 4705f757f3fSDimitry Andric /// Given a constant, create a debug information expression. 4715f757f3fSDimitry Andric DIExpression *getExpressionForConstant(DIBuilder &DIB, const Constant &C, 4725f757f3fSDimitry Andric Type &Ty); 4735f757f3fSDimitry Andric 4740b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 4750b57cec5SDimitry Andric // Intrinsic pattern matching 4760b57cec5SDimitry Andric // 4770b57cec5SDimitry Andric 4780b57cec5SDimitry Andric /// Try to match a bswap or bitreverse idiom. 4790b57cec5SDimitry Andric /// 4800b57cec5SDimitry Andric /// If an idiom is matched, an intrinsic call is inserted before \c I. Any added 4810b57cec5SDimitry Andric /// instructions are returned in \c InsertedInsts. They will all have been added 4820b57cec5SDimitry Andric /// to a basic block. 4830b57cec5SDimitry Andric /// 4840b57cec5SDimitry Andric /// A bitreverse idiom normally requires around 2*BW nodes to be searched (where 4850b57cec5SDimitry Andric /// BW is the bitwidth of the integer type). A bswap idiom requires anywhere up 4860b57cec5SDimitry Andric /// to BW / 4 nodes to be searched, so is significantly faster. 4870b57cec5SDimitry Andric /// 4880b57cec5SDimitry Andric /// This function returns true on a successful match or false otherwise. 4890b57cec5SDimitry Andric bool recognizeBSwapOrBitReverseIdiom( 4900b57cec5SDimitry Andric Instruction *I, bool MatchBSwaps, bool MatchBitReversals, 4910b57cec5SDimitry Andric SmallVectorImpl<Instruction *> &InsertedInsts); 4920b57cec5SDimitry Andric 4930b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 4940b57cec5SDimitry Andric // Sanitizer utilities 4950b57cec5SDimitry Andric // 4960b57cec5SDimitry Andric 4970b57cec5SDimitry Andric /// Given a CallInst, check if it calls a string function known to CodeGen, 4980b57cec5SDimitry Andric /// and mark it with NoBuiltin if so. To be used by sanitizers that intend 4990b57cec5SDimitry Andric /// to intercept string functions and want to avoid converting them to target 5000b57cec5SDimitry Andric /// specific instructions. 5010b57cec5SDimitry Andric void maybeMarkSanitizerLibraryCallNoBuiltin(CallInst *CI, 5020b57cec5SDimitry Andric const TargetLibraryInfo *TLI); 5030b57cec5SDimitry Andric 5040b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 5050b57cec5SDimitry Andric // Transform predicates 5060b57cec5SDimitry Andric // 5070b57cec5SDimitry Andric 5080b57cec5SDimitry Andric /// Given an instruction, is it legal to set operand OpIdx to a non-constant 5090b57cec5SDimitry Andric /// value? 5100b57cec5SDimitry Andric bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx); 5110b57cec5SDimitry Andric 5125ffd83dbSDimitry Andric //===----------------------------------------------------------------------===// 5135ffd83dbSDimitry Andric // Value helper functions 5145ffd83dbSDimitry Andric // 5155ffd83dbSDimitry Andric 5165ffd83dbSDimitry Andric /// Invert the given true/false value, possibly reusing an existing copy. 5175ffd83dbSDimitry Andric Value *invertCondition(Value *Condition); 5185ffd83dbSDimitry Andric 519fe6060f1SDimitry Andric 520fe6060f1SDimitry Andric //===----------------------------------------------------------------------===// 521fe6060f1SDimitry Andric // Assorted 522fe6060f1SDimitry Andric // 523fe6060f1SDimitry Andric 524fe6060f1SDimitry Andric /// If we can infer one attribute from another on the declaration of a 525fe6060f1SDimitry Andric /// function, explicitly materialize the maximal set in the IR. 526fe6060f1SDimitry Andric bool inferAttributesFromOthers(Function &F); 527fe6060f1SDimitry Andric 5280b57cec5SDimitry Andric } // end namespace llvm 5290b57cec5SDimitry Andric 5300b57cec5SDimitry Andric #endif // LLVM_TRANSFORMS_UTILS_LOCAL_H 531