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