1//===- Loads.h - Local load analysis --------------------------------------===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8//
9// This file declares simple local analyses for load instructions.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_ANALYSIS_LOADS_H
14#define LLVM_ANALYSIS_LOADS_H
15
16#include "llvm/IR/BasicBlock.h"
17#include "llvm/Support/CommandLine.h"
18
19namespace llvm {
20
21class AAResults;
22class DataLayout;
23class DominatorTree;
24class Instruction;
25class LoadInst;
26class Loop;
27class MDNode;
28class MemoryLocation;
29class ScalarEvolution;
30class TargetLibraryInfo;
31
32/// Return true if this is always a dereferenceable pointer. If the context
33/// instruction is specified perform context-sensitive analysis and return true
34/// if the pointer is dereferenceable at the specified instruction.
35bool isDereferenceablePointer(const Value *V, Type *Ty,
36                              const DataLayout &DL,
37                              const Instruction *CtxI = nullptr,
38                              const DominatorTree *DT = nullptr,
39                              const TargetLibraryInfo *TLI = nullptr);
40
41/// Returns true if V is always a dereferenceable pointer with alignment
42/// greater or equal than requested. If the context instruction is specified
43/// performs context-sensitive analysis and returns true if the pointer is
44/// dereferenceable at the specified instruction.
45bool isDereferenceableAndAlignedPointer(const Value *V, Type *Ty,
46                                        MaybeAlign Alignment,
47                                        const DataLayout &DL,
48                                        const Instruction *CtxI = nullptr,
49                                        const DominatorTree *DT = nullptr,
50                                        const TargetLibraryInfo *TLI = nullptr);
51
52/// Returns true if V is always dereferenceable for Size byte with alignment
53/// greater or equal than requested. If the context instruction is specified
54/// performs context-sensitive analysis and returns true if the pointer is
55/// dereferenceable at the specified instruction.
56bool isDereferenceableAndAlignedPointer(const Value *V, Align Alignment,
57                                        const APInt &Size, const DataLayout &DL,
58                                        const Instruction *CtxI = nullptr,
59                                        const DominatorTree *DT = nullptr,
60                                        const TargetLibraryInfo *TLI = nullptr);
61
62/// Return true if we know that executing a load from this value cannot trap.
63///
64/// If DT and ScanFrom are specified this method performs context-sensitive
65/// analysis and returns true if it is safe to load immediately before ScanFrom.
66///
67/// If it is not obviously safe to load from the specified pointer, we do a
68/// quick local scan of the basic block containing ScanFrom, to determine if
69/// the address is already accessed.
70bool isSafeToLoadUnconditionally(Value *V, Align Alignment, APInt &Size,
71                                 const DataLayout &DL,
72                                 Instruction *ScanFrom = nullptr,
73                                 const DominatorTree *DT = nullptr,
74                                 const TargetLibraryInfo *TLI = nullptr);
75
76/// Return true if we can prove that the given load (which is assumed to be
77/// within the specified loop) would access only dereferenceable memory, and
78/// be properly aligned on every iteration of the specified loop regardless of
79/// its placement within the loop. (i.e. does not require predication beyond
80/// that required by the the header itself and could be hoisted into the header
81/// if desired.)  This is more powerful than the variants above when the
82/// address loaded from is analyzeable by SCEV.
83bool isDereferenceableAndAlignedInLoop(LoadInst *LI, Loop *L,
84                                       ScalarEvolution &SE,
85                                       DominatorTree &DT);
86
87/// Return true if we know that executing a load from this value cannot trap.
88///
89/// If DT and ScanFrom are specified this method performs context-sensitive
90/// analysis and returns true if it is safe to load immediately before ScanFrom.
91///
92/// If it is not obviously safe to load from the specified pointer, we do a
93/// quick local scan of the basic block containing ScanFrom, to determine if
94/// the address is already accessed.
95bool isSafeToLoadUnconditionally(Value *V, Type *Ty, Align Alignment,
96                                 const DataLayout &DL,
97                                 Instruction *ScanFrom = nullptr,
98                                 const DominatorTree *DT = nullptr,
99                                 const TargetLibraryInfo *TLI = nullptr);
100
101/// The default number of maximum instructions to scan in the block, used by
102/// FindAvailableLoadedValue().
103extern cl::opt<unsigned> DefMaxInstsToScan;
104
105/// Scan backwards to see if we have the value of the given load available
106/// locally within a small number of instructions.
107///
108/// You can use this function to scan across multiple blocks: after you call
109/// this function, if ScanFrom points at the beginning of the block, it's safe
110/// to continue scanning the predecessors.
111///
112/// Note that performing load CSE requires special care to make sure the
113/// metadata is set appropriately.  In particular, aliasing metadata needs
114/// to be merged.  (This doesn't matter for store-to-load forwarding because
115/// the only relevant load gets deleted.)
116///
117/// \param Load The load we want to replace.
118/// \param ScanBB The basic block to scan.
119/// \param [in,out] ScanFrom The location to start scanning from. When this
120/// function returns, it points at the last instruction scanned.
121/// \param MaxInstsToScan The maximum number of instructions to scan. If this
122/// is zero, the whole block will be scanned.
123/// \param AA Optional pointer to alias analysis, to make the scan more
124/// precise.
125/// \param [out] IsLoadCSE Whether the returned value is a load from the same
126/// location in memory, as opposed to the value operand of a store.
127///
128/// \returns The found value, or nullptr if no value is found.
129Value *FindAvailableLoadedValue(LoadInst *Load,
130                                BasicBlock *ScanBB,
131                                BasicBlock::iterator &ScanFrom,
132                                unsigned MaxInstsToScan = DefMaxInstsToScan,
133                                AAResults *AA = nullptr,
134                                bool *IsLoadCSE = nullptr,
135                                unsigned *NumScanedInst = nullptr);
136
137/// This overload provides a more efficient implementation of
138/// FindAvailableLoadedValue() for the case where we are not interested in
139/// finding the closest clobbering instruction if no available load is found.
140/// This overload cannot be used to scan across multiple blocks.
141Value *FindAvailableLoadedValue(LoadInst *Load, AAResults &AA, bool *IsLoadCSE,
142                                unsigned MaxInstsToScan = DefMaxInstsToScan);
143
144/// Scan backwards to see if we have the value of the given pointer available
145/// locally within a small number of instructions.
146///
147/// You can use this function to scan across multiple blocks: after you call
148/// this function, if ScanFrom points at the beginning of the block, it's safe
149/// to continue scanning the predecessors.
150///
151/// \param Loc The location we want the load and store to originate from.
152/// \param AccessTy The access type of the pointer.
153/// \param AtLeastAtomic Are we looking for at-least an atomic load/store ? In
154/// case it is false, we can return an atomic or non-atomic load or store. In
155/// case it is true, we need to return an atomic load or store.
156/// \param ScanBB The basic block to scan.
157/// \param [in,out] ScanFrom The location to start scanning from. When this
158/// function returns, it points at the last instruction scanned.
159/// \param MaxInstsToScan The maximum number of instructions to scan. If this
160/// is zero, the whole block will be scanned.
161/// \param AA Optional pointer to alias analysis, to make the scan more
162/// precise.
163/// \param [out] IsLoadCSE Whether the returned value is a load from the same
164/// location in memory, as opposed to the value operand of a store.
165///
166/// \returns The found value, or nullptr if no value is found.
167Value *findAvailablePtrLoadStore(const MemoryLocation &Loc, Type *AccessTy,
168                                 bool AtLeastAtomic, BasicBlock *ScanBB,
169                                 BasicBlock::iterator &ScanFrom,
170                                 unsigned MaxInstsToScan, AAResults *AA,
171                                 bool *IsLoadCSE, unsigned *NumScanedInst);
172
173/// Returns true if a pointer value \p A can be replace with another pointer
174/// value \B if they are deemed equal through some means (e.g. information from
175/// conditions).
176/// NOTE: the current implementations is incomplete and unsound. It does not
177/// reject all invalid cases yet, but will be made stricter in the future. In
178/// particular this means returning true means unknown if replacement is safe.
179bool canReplacePointersIfEqual(Value *A, Value *B, const DataLayout &DL,
180                               Instruction *CtxI);
181}
182
183#endif
184