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