1 //===----------------------- AlignmentFromAssumptions.cpp -----------------===//
2 // Set Load/Store Alignments From Assumptions
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements a ScalarEvolution-based transformation to set
11 // the alignments of load, stores and memory intrinsics based on the truth
12 // expressions of assume intrinsics. The primary motivation is to handle
13 // complex alignment assumptions that apply to vector loads and stores that
14 // appear after vectorization and unrolling.
15 //
16 //===----------------------------------------------------------------------===//
17
18 #include "llvm/IR/Instructions.h"
19 #include "llvm/InitializePasses.h"
20 #define AA_NAME "alignment-from-assumptions"
21 #define DEBUG_TYPE AA_NAME
22 #include "llvm/Transforms/Scalar/AlignmentFromAssumptions.h"
23 #include "llvm/ADT/SmallPtrSet.h"
24 #include "llvm/ADT/Statistic.h"
25 #include "llvm/Analysis/AliasAnalysis.h"
26 #include "llvm/Analysis/AssumptionCache.h"
27 #include "llvm/Analysis/GlobalsModRef.h"
28 #include "llvm/Analysis/LoopInfo.h"
29 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
30 #include "llvm/Analysis/ValueTracking.h"
31 #include "llvm/IR/Constant.h"
32 #include "llvm/IR/Dominators.h"
33 #include "llvm/IR/Instruction.h"
34 #include "llvm/IR/IntrinsicInst.h"
35 #include "llvm/IR/Intrinsics.h"
36 #include "llvm/IR/Module.h"
37 #include "llvm/Support/Debug.h"
38 #include "llvm/Support/raw_ostream.h"
39 #include "llvm/Transforms/Scalar.h"
40 using namespace llvm;
41
42 STATISTIC(NumLoadAlignChanged,
43 "Number of loads changed by alignment assumptions");
44 STATISTIC(NumStoreAlignChanged,
45 "Number of stores changed by alignment assumptions");
46 STATISTIC(NumMemIntAlignChanged,
47 "Number of memory intrinsics changed by alignment assumptions");
48
49 namespace {
50 struct AlignmentFromAssumptions : public FunctionPass {
51 static char ID; // Pass identification, replacement for typeid
AlignmentFromAssumptions__anon7d3517170111::AlignmentFromAssumptions52 AlignmentFromAssumptions() : FunctionPass(ID) {
53 initializeAlignmentFromAssumptionsPass(*PassRegistry::getPassRegistry());
54 }
55
56 bool runOnFunction(Function &F) override;
57
getAnalysisUsage__anon7d3517170111::AlignmentFromAssumptions58 void getAnalysisUsage(AnalysisUsage &AU) const override {
59 AU.addRequired<AssumptionCacheTracker>();
60 AU.addRequired<ScalarEvolutionWrapperPass>();
61 AU.addRequired<DominatorTreeWrapperPass>();
62
63 AU.setPreservesCFG();
64 AU.addPreserved<AAResultsWrapperPass>();
65 AU.addPreserved<GlobalsAAWrapperPass>();
66 AU.addPreserved<LoopInfoWrapperPass>();
67 AU.addPreserved<DominatorTreeWrapperPass>();
68 AU.addPreserved<ScalarEvolutionWrapperPass>();
69 }
70
71 AlignmentFromAssumptionsPass Impl;
72 };
73 }
74
75 char AlignmentFromAssumptions::ID = 0;
76 static const char aip_name[] = "Alignment from assumptions";
INITIALIZE_PASS_BEGIN(AlignmentFromAssumptions,AA_NAME,aip_name,false,false)77 INITIALIZE_PASS_BEGIN(AlignmentFromAssumptions, AA_NAME,
78 aip_name, false, false)
79 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
80 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
81 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
82 INITIALIZE_PASS_END(AlignmentFromAssumptions, AA_NAME,
83 aip_name, false, false)
84
85 FunctionPass *llvm::createAlignmentFromAssumptionsPass() {
86 return new AlignmentFromAssumptions();
87 }
88
89 // Given an expression for the (constant) alignment, AlignSCEV, and an
90 // expression for the displacement between a pointer and the aligned address,
91 // DiffSCEV, compute the alignment of the displaced pointer if it can be reduced
92 // to a constant. Using SCEV to compute alignment handles the case where
93 // DiffSCEV is a recurrence with constant start such that the aligned offset
94 // is constant. e.g. {16,+,32} % 32 -> 16.
getNewAlignmentDiff(const SCEV * DiffSCEV,const SCEV * AlignSCEV,ScalarEvolution * SE)95 static MaybeAlign getNewAlignmentDiff(const SCEV *DiffSCEV,
96 const SCEV *AlignSCEV,
97 ScalarEvolution *SE) {
98 // DiffUnits = Diff % int64_t(Alignment)
99 const SCEV *DiffUnitsSCEV = SE->getURemExpr(DiffSCEV, AlignSCEV);
100
101 LLVM_DEBUG(dbgs() << "\talignment relative to " << *AlignSCEV << " is "
102 << *DiffUnitsSCEV << " (diff: " << *DiffSCEV << ")\n");
103
104 if (const SCEVConstant *ConstDUSCEV =
105 dyn_cast<SCEVConstant>(DiffUnitsSCEV)) {
106 int64_t DiffUnits = ConstDUSCEV->getValue()->getSExtValue();
107
108 // If the displacement is an exact multiple of the alignment, then the
109 // displaced pointer has the same alignment as the aligned pointer, so
110 // return the alignment value.
111 if (!DiffUnits)
112 return cast<SCEVConstant>(AlignSCEV)->getValue()->getAlignValue();
113
114 // If the displacement is not an exact multiple, but the remainder is a
115 // constant, then return this remainder (but only if it is a power of 2).
116 uint64_t DiffUnitsAbs = std::abs(DiffUnits);
117 if (isPowerOf2_64(DiffUnitsAbs))
118 return Align(DiffUnitsAbs);
119 }
120
121 return None;
122 }
123
124 // There is an address given by an offset OffSCEV from AASCEV which has an
125 // alignment AlignSCEV. Use that information, if possible, to compute a new
126 // alignment for Ptr.
getNewAlignment(const SCEV * AASCEV,const SCEV * AlignSCEV,const SCEV * OffSCEV,Value * Ptr,ScalarEvolution * SE)127 static Align getNewAlignment(const SCEV *AASCEV, const SCEV *AlignSCEV,
128 const SCEV *OffSCEV, Value *Ptr,
129 ScalarEvolution *SE) {
130 const SCEV *PtrSCEV = SE->getSCEV(Ptr);
131 // On a platform with 32-bit allocas, but 64-bit flat/global pointer sizes
132 // (*cough* AMDGPU), the effective SCEV type of AASCEV and PtrSCEV
133 // may disagree. Trunc/extend so they agree.
134 PtrSCEV = SE->getTruncateOrZeroExtend(
135 PtrSCEV, SE->getEffectiveSCEVType(AASCEV->getType()));
136 const SCEV *DiffSCEV = SE->getMinusSCEV(PtrSCEV, AASCEV);
137
138 // On 32-bit platforms, DiffSCEV might now have type i32 -- we've always
139 // sign-extended OffSCEV to i64, so make sure they agree again.
140 DiffSCEV = SE->getNoopOrSignExtend(DiffSCEV, OffSCEV->getType());
141
142 // What we really want to know is the overall offset to the aligned
143 // address. This address is displaced by the provided offset.
144 DiffSCEV = SE->getAddExpr(DiffSCEV, OffSCEV);
145
146 LLVM_DEBUG(dbgs() << "AFI: alignment of " << *Ptr << " relative to "
147 << *AlignSCEV << " and offset " << *OffSCEV
148 << " using diff " << *DiffSCEV << "\n");
149
150 if (MaybeAlign NewAlignment = getNewAlignmentDiff(DiffSCEV, AlignSCEV, SE)) {
151 LLVM_DEBUG(dbgs() << "\tnew alignment: " << DebugStr(NewAlignment) << "\n");
152 return *NewAlignment;
153 }
154
155 if (const SCEVAddRecExpr *DiffARSCEV = dyn_cast<SCEVAddRecExpr>(DiffSCEV)) {
156 // The relative offset to the alignment assumption did not yield a constant,
157 // but we should try harder: if we assume that a is 32-byte aligned, then in
158 // for (i = 0; i < 1024; i += 4) r += a[i]; not all of the loads from a are
159 // 32-byte aligned, but instead alternate between 32 and 16-byte alignment.
160 // As a result, the new alignment will not be a constant, but can still
161 // be improved over the default (of 4) to 16.
162
163 const SCEV *DiffStartSCEV = DiffARSCEV->getStart();
164 const SCEV *DiffIncSCEV = DiffARSCEV->getStepRecurrence(*SE);
165
166 LLVM_DEBUG(dbgs() << "\ttrying start/inc alignment using start "
167 << *DiffStartSCEV << " and inc " << *DiffIncSCEV << "\n");
168
169 // Now compute the new alignment using the displacement to the value in the
170 // first iteration, and also the alignment using the per-iteration delta.
171 // If these are the same, then use that answer. Otherwise, use the smaller
172 // one, but only if it divides the larger one.
173 MaybeAlign NewAlignment = getNewAlignmentDiff(DiffStartSCEV, AlignSCEV, SE);
174 MaybeAlign NewIncAlignment =
175 getNewAlignmentDiff(DiffIncSCEV, AlignSCEV, SE);
176
177 LLVM_DEBUG(dbgs() << "\tnew start alignment: " << DebugStr(NewAlignment)
178 << "\n");
179 LLVM_DEBUG(dbgs() << "\tnew inc alignment: " << DebugStr(NewIncAlignment)
180 << "\n");
181
182 if (!NewAlignment || !NewIncAlignment)
183 return Align(1);
184
185 const Align NewAlign = *NewAlignment;
186 const Align NewIncAlign = *NewIncAlignment;
187 if (NewAlign > NewIncAlign) {
188 LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: "
189 << DebugStr(NewIncAlign) << "\n");
190 return NewIncAlign;
191 }
192 if (NewIncAlign > NewAlign) {
193 LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: " << DebugStr(NewAlign)
194 << "\n");
195 return NewAlign;
196 }
197 assert(NewIncAlign == NewAlign);
198 LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: " << DebugStr(NewAlign)
199 << "\n");
200 return NewAlign;
201 }
202
203 return Align(1);
204 }
205
extractAlignmentInfo(CallInst * I,unsigned Idx,Value * & AAPtr,const SCEV * & AlignSCEV,const SCEV * & OffSCEV)206 bool AlignmentFromAssumptionsPass::extractAlignmentInfo(CallInst *I,
207 unsigned Idx,
208 Value *&AAPtr,
209 const SCEV *&AlignSCEV,
210 const SCEV *&OffSCEV) {
211 Type *Int64Ty = Type::getInt64Ty(I->getContext());
212 OperandBundleUse AlignOB = I->getOperandBundleAt(Idx);
213 if (AlignOB.getTagName() != "align")
214 return false;
215 assert(AlignOB.Inputs.size() >= 2);
216 AAPtr = AlignOB.Inputs[0].get();
217 // TODO: Consider accumulating the offset to the base.
218 AAPtr = AAPtr->stripPointerCastsSameRepresentation();
219 AlignSCEV = SE->getSCEV(AlignOB.Inputs[1].get());
220 AlignSCEV = SE->getTruncateOrZeroExtend(AlignSCEV, Int64Ty);
221 if (AlignOB.Inputs.size() == 3)
222 OffSCEV = SE->getSCEV(AlignOB.Inputs[2].get());
223 else
224 OffSCEV = SE->getZero(Int64Ty);
225 OffSCEV = SE->getTruncateOrZeroExtend(OffSCEV, Int64Ty);
226 return true;
227 }
228
processAssumption(CallInst * ACall,unsigned Idx)229 bool AlignmentFromAssumptionsPass::processAssumption(CallInst *ACall,
230 unsigned Idx) {
231 Value *AAPtr;
232 const SCEV *AlignSCEV, *OffSCEV;
233 if (!extractAlignmentInfo(ACall, Idx, AAPtr, AlignSCEV, OffSCEV))
234 return false;
235
236 // Skip ConstantPointerNull and UndefValue. Assumptions on these shouldn't
237 // affect other users.
238 if (isa<ConstantData>(AAPtr))
239 return false;
240
241 const SCEV *AASCEV = SE->getSCEV(AAPtr);
242
243 // Apply the assumption to all other users of the specified pointer.
244 SmallPtrSet<Instruction *, 32> Visited;
245 SmallVector<Instruction*, 16> WorkList;
246 for (User *J : AAPtr->users()) {
247 if (J == ACall)
248 continue;
249
250 if (Instruction *K = dyn_cast<Instruction>(J))
251 WorkList.push_back(K);
252 }
253
254 while (!WorkList.empty()) {
255 Instruction *J = WorkList.pop_back_val();
256 if (LoadInst *LI = dyn_cast<LoadInst>(J)) {
257 if (!isValidAssumeForContext(ACall, J, DT))
258 continue;
259 Align NewAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV,
260 LI->getPointerOperand(), SE);
261 if (NewAlignment > LI->getAlign()) {
262 LI->setAlignment(NewAlignment);
263 ++NumLoadAlignChanged;
264 }
265 } else if (StoreInst *SI = dyn_cast<StoreInst>(J)) {
266 if (!isValidAssumeForContext(ACall, J, DT))
267 continue;
268 Align NewAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV,
269 SI->getPointerOperand(), SE);
270 if (NewAlignment > SI->getAlign()) {
271 SI->setAlignment(NewAlignment);
272 ++NumStoreAlignChanged;
273 }
274 } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(J)) {
275 if (!isValidAssumeForContext(ACall, J, DT))
276 continue;
277 Align NewDestAlignment =
278 getNewAlignment(AASCEV, AlignSCEV, OffSCEV, MI->getDest(), SE);
279
280 LLVM_DEBUG(dbgs() << "\tmem inst: " << DebugStr(NewDestAlignment)
281 << "\n";);
282 if (NewDestAlignment > *MI->getDestAlign()) {
283 MI->setDestAlignment(NewDestAlignment);
284 ++NumMemIntAlignChanged;
285 }
286
287 // For memory transfers, there is also a source alignment that
288 // can be set.
289 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) {
290 Align NewSrcAlignment =
291 getNewAlignment(AASCEV, AlignSCEV, OffSCEV, MTI->getSource(), SE);
292
293 LLVM_DEBUG(dbgs() << "\tmem trans: " << DebugStr(NewSrcAlignment)
294 << "\n";);
295
296 if (NewSrcAlignment > *MTI->getSourceAlign()) {
297 MTI->setSourceAlignment(NewSrcAlignment);
298 ++NumMemIntAlignChanged;
299 }
300 }
301 }
302
303 // Now that we've updated that use of the pointer, look for other uses of
304 // the pointer to update.
305 Visited.insert(J);
306 for (User *UJ : J->users()) {
307 Instruction *K = cast<Instruction>(UJ);
308 if (!Visited.count(K))
309 WorkList.push_back(K);
310 }
311 }
312
313 return true;
314 }
315
runOnFunction(Function & F)316 bool AlignmentFromAssumptions::runOnFunction(Function &F) {
317 if (skipFunction(F))
318 return false;
319
320 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
321 ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
322 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
323
324 return Impl.runImpl(F, AC, SE, DT);
325 }
326
runImpl(Function & F,AssumptionCache & AC,ScalarEvolution * SE_,DominatorTree * DT_)327 bool AlignmentFromAssumptionsPass::runImpl(Function &F, AssumptionCache &AC,
328 ScalarEvolution *SE_,
329 DominatorTree *DT_) {
330 SE = SE_;
331 DT = DT_;
332
333 bool Changed = false;
334 for (auto &AssumeVH : AC.assumptions())
335 if (AssumeVH) {
336 CallInst *Call = cast<CallInst>(AssumeVH);
337 for (unsigned Idx = 0; Idx < Call->getNumOperandBundles(); Idx++)
338 Changed |= processAssumption(Call, Idx);
339 }
340
341 return Changed;
342 }
343
344 PreservedAnalyses
run(Function & F,FunctionAnalysisManager & AM)345 AlignmentFromAssumptionsPass::run(Function &F, FunctionAnalysisManager &AM) {
346
347 AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);
348 ScalarEvolution &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
349 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
350 if (!runImpl(F, AC, &SE, &DT))
351 return PreservedAnalyses::all();
352
353 PreservedAnalyses PA;
354 PA.preserveSet<CFGAnalyses>();
355 PA.preserve<ScalarEvolutionAnalysis>();
356 return PA;
357 }
358