1 //===- Local.h - Functions to perform local transformations -----*- C++ -*-===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This family of functions perform various local transformations to the
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_TRANSFORMS_UTILS_LOCAL_H
15 #define LLVM_TRANSFORMS_UTILS_LOCAL_H
17 #include "llvm/ADT/ArrayRef.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/TinyPtrVector.h"
22 #include "llvm/Analysis/AliasAnalysis.h"
23 #include "llvm/Analysis/DomTreeUpdater.h"
24 #include "llvm/Analysis/Utils/Local.h"
25 #include "llvm/IR/Constant.h"
26 #include "llvm/IR/Constants.h"
27 #include "llvm/IR/DataLayout.h"
28 #include "llvm/IR/Dominators.h"
29 #include "llvm/IR/GetElementPtrTypeIterator.h"
30 #include "llvm/IR/Operator.h"
31 #include "llvm/IR/Type.h"
32 #include "llvm/IR/User.h"
33 #include "llvm/IR/Value.h"
34 #include "llvm/Support/Casting.h"
41 class AssumptionCache
;
45 class DbgVariableIntrinsic
;
53 class MemorySSAUpdater
;
56 class TargetLibraryInfo
;
57 class TargetTransformInfo
;
59 /// A set of parameters used to control the transforms in the SimplifyCFG pass.
60 /// Options may change depending on the position in the optimization pipeline.
61 /// For example, canonical form that includes switches and branches may later be
62 /// replaced by lookup tables and selects.
63 struct SimplifyCFGOptions
{
64 int BonusInstThreshold
;
65 bool ForwardSwitchCondToPhi
;
66 bool ConvertSwitchToLookupTable
;
67 bool NeedCanonicalLoop
;
71 SimplifyCFGOptions(unsigned BonusThreshold
= 1,
72 bool ForwardSwitchCond
= false,
73 bool SwitchToLookup
= false, bool CanonicalLoops
= true,
74 bool SinkCommon
= false,
75 AssumptionCache
*AssumpCache
= nullptr)
76 : BonusInstThreshold(BonusThreshold
),
77 ForwardSwitchCondToPhi(ForwardSwitchCond
),
78 ConvertSwitchToLookupTable(SwitchToLookup
),
79 NeedCanonicalLoop(CanonicalLoops
),
80 SinkCommonInsts(SinkCommon
),
83 // Support 'builder' pattern to set members by name at construction time.
84 SimplifyCFGOptions
&bonusInstThreshold(int I
) {
85 BonusInstThreshold
= I
;
88 SimplifyCFGOptions
&forwardSwitchCondToPhi(bool B
) {
89 ForwardSwitchCondToPhi
= B
;
92 SimplifyCFGOptions
&convertSwitchToLookupTable(bool B
) {
93 ConvertSwitchToLookupTable
= B
;
96 SimplifyCFGOptions
&needCanonicalLoops(bool B
) {
97 NeedCanonicalLoop
= B
;
100 SimplifyCFGOptions
&sinkCommonInsts(bool B
) {
104 SimplifyCFGOptions
&setAssumptionCache(AssumptionCache
*Cache
) {
110 //===----------------------------------------------------------------------===//
111 // Local constant propagation.
114 /// If a terminator instruction is predicated on a constant value, convert it
115 /// into an unconditional branch to the constant destination.
116 /// This is a nontrivial operation because the successors of this basic block
117 /// must have their PHI nodes updated.
118 /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
119 /// conditions and indirectbr addresses this might make dead if
120 /// DeleteDeadConditions is true.
121 bool ConstantFoldTerminator(BasicBlock
*BB
, bool DeleteDeadConditions
= false,
122 const TargetLibraryInfo
*TLI
= nullptr,
123 DomTreeUpdater
*DTU
= nullptr);
125 //===----------------------------------------------------------------------===//
126 // Local dead code elimination.
129 /// Return true if the result produced by the instruction is not used, and the
130 /// instruction has no side effects.
131 bool isInstructionTriviallyDead(Instruction
*I
,
132 const TargetLibraryInfo
*TLI
= nullptr);
134 /// Return true if the result produced by the instruction would have no side
135 /// effects if it was not used. This is equivalent to checking whether
136 /// isInstructionTriviallyDead would be true if the use count was 0.
137 bool wouldInstructionBeTriviallyDead(Instruction
*I
,
138 const TargetLibraryInfo
*TLI
= nullptr);
140 /// If the specified value is a trivially dead instruction, delete it.
141 /// If that makes any of its operands trivially dead, delete them too,
142 /// recursively. Return true if any instructions were deleted.
143 bool RecursivelyDeleteTriviallyDeadInstructions(
144 Value
*V
, const TargetLibraryInfo
*TLI
= nullptr,
145 MemorySSAUpdater
*MSSAU
= nullptr);
147 /// Delete all of the instructions in `DeadInsts`, and all other instructions
148 /// that deleting these in turn causes to be trivially dead.
150 /// The initial instructions in the provided vector must all have empty use
151 /// lists and satisfy `isInstructionTriviallyDead`.
153 /// `DeadInsts` will be used as scratch storage for this routine and will be
155 void RecursivelyDeleteTriviallyDeadInstructions(
156 SmallVectorImpl
<Instruction
*> &DeadInsts
,
157 const TargetLibraryInfo
*TLI
= nullptr, MemorySSAUpdater
*MSSAU
= nullptr);
159 /// If the specified value is an effectively dead PHI node, due to being a
160 /// def-use chain of single-use nodes that either forms a cycle or is terminated
161 /// by a trivially dead instruction, delete it. If that makes any of its
162 /// operands trivially dead, delete them too, recursively. Return true if a
164 bool RecursivelyDeleteDeadPHINode(PHINode
*PN
,
165 const TargetLibraryInfo
*TLI
= nullptr);
167 /// Scan the specified basic block and try to simplify any instructions in it
168 /// and recursively delete dead instructions.
170 /// This returns true if it changed the code, note that it can delete
171 /// instructions in other blocks as well in this block.
172 bool SimplifyInstructionsInBlock(BasicBlock
*BB
,
173 const TargetLibraryInfo
*TLI
= nullptr);
175 /// Replace all the uses of an SSA value in @llvm.dbg intrinsics with
176 /// undef. This is useful for signaling that a variable, e.g. has been
177 /// found dead and hence it's unavailable at a given program point.
178 /// Returns true if the dbg values have been changed.
179 bool replaceDbgUsesWithUndef(Instruction
*I
);
181 //===----------------------------------------------------------------------===//
182 // Control Flow Graph Restructuring.
185 /// Like BasicBlock::removePredecessor, this method is called when we're about
186 /// to delete Pred as a predecessor of BB. If BB contains any PHI nodes, this
187 /// drops the entries in the PHI nodes for Pred.
189 /// Unlike the removePredecessor method, this attempts to simplify uses of PHI
190 /// nodes that collapse into identity values. For example, if we have:
191 /// x = phi(1, 0, 0, 0)
194 /// .. and delete the predecessor corresponding to the '1', this will attempt to
195 /// recursively fold the 'and' to 0.
196 void RemovePredecessorAndSimplify(BasicBlock
*BB
, BasicBlock
*Pred
,
197 DomTreeUpdater
*DTU
= nullptr);
199 /// BB is a block with one predecessor and its predecessor is known to have one
200 /// successor (BB!). Eliminate the edge between them, moving the instructions in
201 /// the predecessor into BB. This deletes the predecessor block.
202 void MergeBasicBlockIntoOnlyPred(BasicBlock
*BB
, DomTreeUpdater
*DTU
= nullptr);
204 /// BB is known to contain an unconditional branch, and contains no instructions
205 /// other than PHI nodes, potential debug intrinsics and the branch. If
206 /// possible, eliminate BB by rewriting all the predecessors to branch to the
207 /// successor block and return true. If we can't transform, return false.
208 bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock
*BB
,
209 DomTreeUpdater
*DTU
= nullptr);
211 /// Check for and eliminate duplicate PHI nodes in this block. This doesn't try
212 /// to be clever about PHI nodes which differ only in the order of the incoming
213 /// values, but instcombine orders them so it usually won't matter.
214 bool EliminateDuplicatePHINodes(BasicBlock
*BB
);
216 /// This function is used to do simplification of a CFG. For example, it
217 /// adjusts branches to branches to eliminate the extra hop, it eliminates
218 /// unreachable basic blocks, and does other peephole optimization of the CFG.
219 /// It returns true if a modification was made, possibly deleting the basic
220 /// block that was pointed to. LoopHeaders is an optional input parameter
221 /// providing the set of loop headers that SimplifyCFG should not eliminate.
222 bool simplifyCFG(BasicBlock
*BB
, const TargetTransformInfo
&TTI
,
223 const SimplifyCFGOptions
&Options
= {},
224 SmallPtrSetImpl
<BasicBlock
*> *LoopHeaders
= nullptr);
226 /// This function is used to flatten a CFG. For example, it uses parallel-and
227 /// and parallel-or mode to collapse if-conditions and merge if-regions with
228 /// identical statements.
229 bool FlattenCFG(BasicBlock
*BB
, AliasAnalysis
*AA
= nullptr);
231 /// If this basic block is ONLY a setcc and a branch, and if a predecessor
232 /// branches to us and one of our successors, fold the setcc into the
233 /// predecessor and use logical operations to pick the right destination.
234 bool FoldBranchToCommonDest(BranchInst
*BI
, MemorySSAUpdater
*MSSAU
= nullptr,
235 unsigned BonusInstThreshold
= 1);
237 /// This function takes a virtual register computed by an Instruction and
238 /// replaces it with a slot in the stack frame, allocated via alloca.
239 /// This allows the CFG to be changed around without fear of invalidating the
240 /// SSA information for the value. It returns the pointer to the alloca inserted
241 /// to create a stack slot for X.
242 AllocaInst
*DemoteRegToStack(Instruction
&X
,
243 bool VolatileLoads
= false,
244 Instruction
*AllocaPoint
= nullptr);
246 /// This function takes a virtual register computed by a phi node and replaces
247 /// it with a slot in the stack frame, allocated via alloca. The phi node is
248 /// deleted and it returns the pointer to the alloca inserted.
249 AllocaInst
*DemotePHIToStack(PHINode
*P
, Instruction
*AllocaPoint
= nullptr);
251 /// Try to ensure that the alignment of \p V is at least \p PrefAlign bytes. If
252 /// the owning object can be modified and has an alignment less than \p
253 /// PrefAlign, it will be increased and \p PrefAlign returned. If the alignment
254 /// cannot be increased, the known alignment of the value is returned.
256 /// It is not always possible to modify the alignment of the underlying object,
257 /// so if alignment is important, a more reliable approach is to simply align
258 /// all global variables and allocation instructions to their preferred
259 /// alignment from the beginning.
260 unsigned getOrEnforceKnownAlignment(Value
*V
, unsigned PrefAlign
,
261 const DataLayout
&DL
,
262 const Instruction
*CxtI
= nullptr,
263 AssumptionCache
*AC
= nullptr,
264 const DominatorTree
*DT
= nullptr);
266 /// Try to infer an alignment for the specified pointer.
267 inline unsigned getKnownAlignment(Value
*V
, const DataLayout
&DL
,
268 const Instruction
*CxtI
= nullptr,
269 AssumptionCache
*AC
= nullptr,
270 const DominatorTree
*DT
= nullptr) {
271 return getOrEnforceKnownAlignment(V
, 0, DL
, CxtI
, AC
, DT
);
274 /// Create a call that matches the invoke \p II in terms of arguments,
275 /// attributes, debug information, etc. The call is not placed in a block and it
276 /// will not have a name. The invoke instruction is not removed, nor are the
277 /// uses replaced by the new call.
278 CallInst
*createCallMatchingInvoke(InvokeInst
*II
);
280 /// This function converts the specified invoek into a normall call.
281 void changeToCall(InvokeInst
*II
, DomTreeUpdater
*DTU
= nullptr);
283 ///===---------------------------------------------------------------------===//
284 /// Dbg Intrinsic utilities
287 /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value
288 /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic.
289 void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic
*DII
,
290 StoreInst
*SI
, DIBuilder
&Builder
);
292 /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value
293 /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic.
294 void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic
*DII
,
295 LoadInst
*LI
, DIBuilder
&Builder
);
297 /// Inserts a llvm.dbg.value intrinsic after a phi that has an associated
298 /// llvm.dbg.declare or llvm.dbg.addr intrinsic.
299 void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic
*DII
,
300 PHINode
*LI
, DIBuilder
&Builder
);
302 /// Lowers llvm.dbg.declare intrinsics into appropriate set of
303 /// llvm.dbg.value intrinsics.
304 bool LowerDbgDeclare(Function
&F
);
306 /// Propagate dbg.value intrinsics through the newly inserted PHIs.
307 void insertDebugValuesForPHIs(BasicBlock
*BB
,
308 SmallVectorImpl
<PHINode
*> &InsertedPHIs
);
310 /// Finds all intrinsics declaring local variables as living in the memory that
311 /// 'V' points to. This may include a mix of dbg.declare and
312 /// dbg.addr intrinsics.
313 TinyPtrVector
<DbgVariableIntrinsic
*> FindDbgAddrUses(Value
*V
);
315 /// Finds the llvm.dbg.value intrinsics describing a value.
316 void findDbgValues(SmallVectorImpl
<DbgValueInst
*> &DbgValues
, Value
*V
);
318 /// Finds the debug info intrinsics describing a value.
319 void findDbgUsers(SmallVectorImpl
<DbgVariableIntrinsic
*> &DbgInsts
, Value
*V
);
321 /// Replaces llvm.dbg.declare instruction when the address it
322 /// describes is replaced with a new value. If Deref is true, an
323 /// additional DW_OP_deref is prepended to the expression. If Offset
324 /// is non-zero, a constant displacement is added to the expression
325 /// (between the optional Deref operations). Offset can be negative.
326 bool replaceDbgDeclare(Value
*Address
, Value
*NewAddress
,
327 Instruction
*InsertBefore
, DIBuilder
&Builder
,
328 uint8_t DIExprFlags
, int Offset
);
330 /// Replaces llvm.dbg.declare instruction when the alloca it describes
331 /// is replaced with a new value. If Deref is true, an additional
332 /// DW_OP_deref is prepended to the expression. If Offset is non-zero,
333 /// a constant displacement is added to the expression (between the
334 /// optional Deref operations). Offset can be negative. The new
335 /// llvm.dbg.declare is inserted immediately after AI.
336 bool replaceDbgDeclareForAlloca(AllocaInst
*AI
, Value
*NewAllocaAddress
,
337 DIBuilder
&Builder
, uint8_t DIExprFlags
,
340 /// Replaces multiple llvm.dbg.value instructions when the alloca it describes
341 /// is replaced with a new value. If Offset is non-zero, a constant displacement
342 /// is added to the expression (after the mandatory Deref). Offset can be
343 /// negative. New llvm.dbg.value instructions are inserted at the locations of
344 /// the instructions they replace.
345 void replaceDbgValueForAlloca(AllocaInst
*AI
, Value
*NewAllocaAddress
,
346 DIBuilder
&Builder
, int Offset
= 0);
348 /// Finds alloca where the value comes from.
349 AllocaInst
*findAllocaForValue(Value
*V
,
350 DenseMap
<Value
*, AllocaInst
*> &AllocaForValue
);
352 /// Assuming the instruction \p I is going to be deleted, attempt to salvage
353 /// debug users of \p I by writing the effect of \p I in a DIExpression.
354 /// Returns true if any debug users were updated.
355 bool salvageDebugInfo(Instruction
&I
);
357 /// Implementation of salvageDebugInfo, applying only to instructions in
358 /// \p Insns, rather than all debug users of \p I.
359 bool salvageDebugInfoForDbgValues(Instruction
&I
,
360 ArrayRef
<DbgVariableIntrinsic
*> Insns
);
362 /// Given an instruction \p I and DIExpression \p DIExpr operating on it, write
363 /// the effects of \p I into the returned DIExpression, or return nullptr if
364 /// it cannot be salvaged. \p StackVal: whether DW_OP_stack_value should be
365 /// appended to the expression.
366 DIExpression
*salvageDebugInfoImpl(Instruction
&I
, DIExpression
*DIExpr
,
369 /// Point debug users of \p From to \p To or salvage them. Use this function
370 /// only when replacing all uses of \p From with \p To, with a guarantee that
371 /// \p From is going to be deleted.
373 /// Follow these rules to prevent use-before-def of \p To:
374 /// . If \p To is a linked Instruction, set \p DomPoint to \p To.
375 /// . If \p To is an unlinked Instruction, set \p DomPoint to the Instruction
376 /// \p To will be inserted after.
377 /// . If \p To is not an Instruction (e.g a Constant), the choice of
378 /// \p DomPoint is arbitrary. Pick \p From for simplicity.
380 /// If a debug user cannot be preserved without reordering variable updates or
381 /// introducing a use-before-def, it is either salvaged (\ref salvageDebugInfo)
382 /// or deleted. Returns true if any debug users were updated.
383 bool replaceAllDbgUsesWith(Instruction
&From
, Value
&To
, Instruction
&DomPoint
,
386 /// Remove all instructions from a basic block other than it's terminator
387 /// and any present EH pad instructions.
388 unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock
*BB
);
390 /// Insert an unreachable instruction before the specified
391 /// instruction, making it and the rest of the code in the block dead.
392 unsigned changeToUnreachable(Instruction
*I
, bool UseLLVMTrap
,
393 bool PreserveLCSSA
= false,
394 DomTreeUpdater
*DTU
= nullptr,
395 MemorySSAUpdater
*MSSAU
= nullptr);
397 /// Convert the CallInst to InvokeInst with the specified unwind edge basic
398 /// block. This also splits the basic block where CI is located, because
399 /// InvokeInst is a terminator instruction. Returns the newly split basic
401 BasicBlock
*changeToInvokeAndSplitBasicBlock(CallInst
*CI
,
402 BasicBlock
*UnwindEdge
);
404 /// Replace 'BB's terminator with one that does not have an unwind successor
405 /// block. Rewrites `invoke` to `call`, etc. Updates any PHIs in unwind
408 /// \param BB Block whose terminator will be replaced. Its terminator must
409 /// have an unwind successor.
410 void removeUnwindEdge(BasicBlock
*BB
, DomTreeUpdater
*DTU
= nullptr);
412 /// Remove all blocks that can not be reached from the function's entry.
414 /// Returns true if any basic block was removed.
415 bool removeUnreachableBlocks(Function
&F
, LazyValueInfo
*LVI
= nullptr,
416 DomTreeUpdater
*DTU
= nullptr,
417 MemorySSAUpdater
*MSSAU
= nullptr);
419 /// Combine the metadata of two instructions so that K can replace J. Some
420 /// metadata kinds can only be kept if K does not move, meaning it dominated
421 /// J in the original IR.
423 /// Metadata not listed as known via KnownIDs is removed
424 void combineMetadata(Instruction
*K
, const Instruction
*J
,
425 ArrayRef
<unsigned> KnownIDs
, bool DoesKMove
);
427 /// Combine the metadata of two instructions so that K can replace J. This
428 /// specifically handles the case of CSE-like transformations. Some
429 /// metadata can only be kept if K dominates J. For this to be correct,
430 /// K cannot be hoisted.
432 /// Unknown metadata is removed.
433 void combineMetadataForCSE(Instruction
*K
, const Instruction
*J
,
436 /// Copy the metadata from the source instruction to the destination (the
437 /// replacement for the source instruction).
438 void copyMetadataForLoad(LoadInst
&Dest
, const LoadInst
&Source
);
440 /// Patch the replacement so that it is not more restrictive than the value
441 /// being replaced. It assumes that the replacement does not get moved from
442 /// its original position.
443 void patchReplacementInstruction(Instruction
*I
, Value
*Repl
);
445 // Replace each use of 'From' with 'To', if that use does not belong to basic
446 // block where 'From' is defined. Returns the number of replacements made.
447 unsigned replaceNonLocalUsesWith(Instruction
*From
, Value
*To
);
449 /// Replace each use of 'From' with 'To' if that use is dominated by
450 /// the given edge. Returns the number of replacements made.
451 unsigned replaceDominatedUsesWith(Value
*From
, Value
*To
, DominatorTree
&DT
,
452 const BasicBlockEdge
&Edge
);
453 /// Replace each use of 'From' with 'To' if that use is dominated by
454 /// the end of the given BasicBlock. Returns the number of replacements made.
455 unsigned replaceDominatedUsesWith(Value
*From
, Value
*To
, DominatorTree
&DT
,
456 const BasicBlock
*BB
);
458 /// Return true if this call calls a gc leaf function.
460 /// A leaf function is a function that does not safepoint the thread during its
461 /// execution. During a call or invoke to such a function, the callers stack
462 /// does not have to be made parseable.
464 /// Most passes can and should ignore this information, and it is only used
465 /// during lowering by the GC infrastructure.
466 bool callsGCLeafFunction(const CallBase
*Call
, const TargetLibraryInfo
&TLI
);
468 /// Copy a nonnull metadata node to a new load instruction.
470 /// This handles mapping it to range metadata if the new load is an integer
471 /// load instead of a pointer load.
472 void copyNonnullMetadata(const LoadInst
&OldLI
, MDNode
*N
, LoadInst
&NewLI
);
474 /// Copy a range metadata node to a new load instruction.
476 /// This handles mapping it to nonnull metadata if the new load is a pointer
477 /// load instead of an integer load and the range doesn't cover null.
478 void copyRangeMetadata(const DataLayout
&DL
, const LoadInst
&OldLI
, MDNode
*N
,
481 /// Remove the debug intrinsic instructions for the given instruction.
482 void dropDebugUsers(Instruction
&I
);
484 /// Hoist all of the instructions in the \p IfBlock to the dominant block
485 /// \p DomBlock, by moving its instructions to the insertion point \p InsertPt.
487 /// The moved instructions receive the insertion point debug location values
488 /// (DILocations) and their debug intrinsic instructions are removed.
489 void hoistAllInstructionsInto(BasicBlock
*DomBlock
, Instruction
*InsertPt
,
492 //===----------------------------------------------------------------------===//
493 // Intrinsic pattern matching
496 /// Try to match a bswap or bitreverse idiom.
498 /// If an idiom is matched, an intrinsic call is inserted before \c I. Any added
499 /// instructions are returned in \c InsertedInsts. They will all have been added
500 /// to a basic block.
502 /// A bitreverse idiom normally requires around 2*BW nodes to be searched (where
503 /// BW is the bitwidth of the integer type). A bswap idiom requires anywhere up
504 /// to BW / 4 nodes to be searched, so is significantly faster.
506 /// This function returns true on a successful match or false otherwise.
507 bool recognizeBSwapOrBitReverseIdiom(
508 Instruction
*I
, bool MatchBSwaps
, bool MatchBitReversals
,
509 SmallVectorImpl
<Instruction
*> &InsertedInsts
);
511 //===----------------------------------------------------------------------===//
512 // Sanitizer utilities
515 /// Given a CallInst, check if it calls a string function known to CodeGen,
516 /// and mark it with NoBuiltin if so. To be used by sanitizers that intend
517 /// to intercept string functions and want to avoid converting them to target
518 /// specific instructions.
519 void maybeMarkSanitizerLibraryCallNoBuiltin(CallInst
*CI
,
520 const TargetLibraryInfo
*TLI
);
522 //===----------------------------------------------------------------------===//
523 // Transform predicates
526 /// Given an instruction, is it legal to set operand OpIdx to a non-constant
528 bool canReplaceOperandWithVariable(const Instruction
*I
, unsigned OpIdx
);
530 } // end namespace llvm
532 #endif // LLVM_TRANSFORMS_UTILS_LOCAL_H