1 //===----------------------- AlignmentFromAssumptions.cpp -----------------===//
2 // Set Load/Store Alignments From Assumptions
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
8 //===----------------------------------------------------------------------===//
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.
16 //===----------------------------------------------------------------------===//
18 #include "llvm/InitializePasses.h"
19 #define AA_NAME "alignment-from-assumptions"
20 #define DEBUG_TYPE AA_NAME
21 #include "llvm/Transforms/Scalar/AlignmentFromAssumptions.h"
22 #include "llvm/ADT/SmallPtrSet.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/Analysis/AliasAnalysis.h"
25 #include "llvm/Analysis/AssumptionCache.h"
26 #include "llvm/Analysis/GlobalsModRef.h"
27 #include "llvm/Analysis/LoopInfo.h"
28 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
29 #include "llvm/Analysis/ValueTracking.h"
30 #include "llvm/IR/Constant.h"
31 #include "llvm/IR/Dominators.h"
32 #include "llvm/IR/Instruction.h"
33 #include "llvm/IR/Intrinsics.h"
34 #include "llvm/IR/Module.h"
35 #include "llvm/Support/Debug.h"
36 #include "llvm/Support/raw_ostream.h"
37 #include "llvm/Transforms/Scalar.h"
40 STATISTIC(NumLoadAlignChanged,
41 "Number of loads changed by alignment assumptions");
42 STATISTIC(NumStoreAlignChanged,
43 "Number of stores changed by alignment assumptions");
44 STATISTIC(NumMemIntAlignChanged,
45 "Number of memory intrinsics changed by alignment assumptions");
48 struct AlignmentFromAssumptions : public FunctionPass {
49 static char ID; // Pass identification, replacement for typeid
50 AlignmentFromAssumptions() : FunctionPass(ID) {
51 initializeAlignmentFromAssumptionsPass(*PassRegistry::getPassRegistry());
54 bool runOnFunction(Function &F) override;
56 void getAnalysisUsage(AnalysisUsage &AU) const override {
57 AU.addRequired<AssumptionCacheTracker>();
58 AU.addRequired<ScalarEvolutionWrapperPass>();
59 AU.addRequired<DominatorTreeWrapperPass>();
62 AU.addPreserved<AAResultsWrapperPass>();
63 AU.addPreserved<GlobalsAAWrapperPass>();
64 AU.addPreserved<LoopInfoWrapperPass>();
65 AU.addPreserved<DominatorTreeWrapperPass>();
66 AU.addPreserved<ScalarEvolutionWrapperPass>();
69 AlignmentFromAssumptionsPass Impl;
73 char AlignmentFromAssumptions::ID = 0;
74 static const char aip_name[] = "Alignment from assumptions";
75 INITIALIZE_PASS_BEGIN(AlignmentFromAssumptions, AA_NAME,
76 aip_name, false, false)
77 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
78 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
79 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
80 INITIALIZE_PASS_END(AlignmentFromAssumptions, AA_NAME,
81 aip_name, false, false)
83 FunctionPass *llvm::createAlignmentFromAssumptionsPass() {
84 return new AlignmentFromAssumptions();
87 // Given an expression for the (constant) alignment, AlignSCEV, and an
88 // expression for the displacement between a pointer and the aligned address,
89 // DiffSCEV, compute the alignment of the displaced pointer if it can be reduced
90 // to a constant. Using SCEV to compute alignment handles the case where
91 // DiffSCEV is a recurrence with constant start such that the aligned offset
92 // is constant. e.g. {16,+,32} % 32 -> 16.
93 static unsigned getNewAlignmentDiff(const SCEV *DiffSCEV,
94 const SCEV *AlignSCEV,
95 ScalarEvolution *SE) {
96 // DiffUnits = Diff % int64_t(Alignment)
97 const SCEV *DiffUnitsSCEV = SE->getURemExpr(DiffSCEV, AlignSCEV);
99 LLVM_DEBUG(dbgs() << "\talignment relative to " << *AlignSCEV << " is "
100 << *DiffUnitsSCEV << " (diff: " << *DiffSCEV << ")\n");
102 if (const SCEVConstant *ConstDUSCEV =
103 dyn_cast<SCEVConstant>(DiffUnitsSCEV)) {
104 int64_t DiffUnits = ConstDUSCEV->getValue()->getSExtValue();
106 // If the displacement is an exact multiple of the alignment, then the
107 // displaced pointer has the same alignment as the aligned pointer, so
108 // return the alignment value.
111 cast<SCEVConstant>(AlignSCEV)->getValue()->getSExtValue();
113 // If the displacement is not an exact multiple, but the remainder is a
114 // constant, then return this remainder (but only if it is a power of 2).
115 uint64_t DiffUnitsAbs = std::abs(DiffUnits);
116 if (isPowerOf2_64(DiffUnitsAbs))
117 return (unsigned) DiffUnitsAbs;
123 // There is an address given by an offset OffSCEV from AASCEV which has an
124 // alignment AlignSCEV. Use that information, if possible, to compute a new
125 // alignment for Ptr.
126 static unsigned getNewAlignment(const SCEV *AASCEV, const SCEV *AlignSCEV,
127 const SCEV *OffSCEV, Value *Ptr,
128 ScalarEvolution *SE) {
129 const SCEV *PtrSCEV = SE->getSCEV(Ptr);
130 const SCEV *DiffSCEV = SE->getMinusSCEV(PtrSCEV, AASCEV);
132 // On 32-bit platforms, DiffSCEV might now have type i32 -- we've always
133 // sign-extended OffSCEV to i64, so make sure they agree again.
134 DiffSCEV = SE->getNoopOrSignExtend(DiffSCEV, OffSCEV->getType());
136 // What we really want to know is the overall offset to the aligned
137 // address. This address is displaced by the provided offset.
138 DiffSCEV = SE->getMinusSCEV(DiffSCEV, OffSCEV);
140 LLVM_DEBUG(dbgs() << "AFI: alignment of " << *Ptr << " relative to "
141 << *AlignSCEV << " and offset " << *OffSCEV
142 << " using diff " << *DiffSCEV << "\n");
144 unsigned NewAlignment = getNewAlignmentDiff(DiffSCEV, AlignSCEV, SE);
145 LLVM_DEBUG(dbgs() << "\tnew alignment: " << NewAlignment << "\n");
149 } else if (const SCEVAddRecExpr *DiffARSCEV =
150 dyn_cast<SCEVAddRecExpr>(DiffSCEV)) {
151 // The relative offset to the alignment assumption did not yield a constant,
152 // but we should try harder: if we assume that a is 32-byte aligned, then in
153 // for (i = 0; i < 1024; i += 4) r += a[i]; not all of the loads from a are
154 // 32-byte aligned, but instead alternate between 32 and 16-byte alignment.
155 // As a result, the new alignment will not be a constant, but can still
156 // be improved over the default (of 4) to 16.
158 const SCEV *DiffStartSCEV = DiffARSCEV->getStart();
159 const SCEV *DiffIncSCEV = DiffARSCEV->getStepRecurrence(*SE);
161 LLVM_DEBUG(dbgs() << "\ttrying start/inc alignment using start "
162 << *DiffStartSCEV << " and inc " << *DiffIncSCEV << "\n");
164 // Now compute the new alignment using the displacement to the value in the
165 // first iteration, and also the alignment using the per-iteration delta.
166 // If these are the same, then use that answer. Otherwise, use the smaller
167 // one, but only if it divides the larger one.
168 NewAlignment = getNewAlignmentDiff(DiffStartSCEV, AlignSCEV, SE);
169 unsigned NewIncAlignment = getNewAlignmentDiff(DiffIncSCEV, AlignSCEV, SE);
171 LLVM_DEBUG(dbgs() << "\tnew start alignment: " << NewAlignment << "\n");
172 LLVM_DEBUG(dbgs() << "\tnew inc alignment: " << NewIncAlignment << "\n");
174 if (!NewAlignment || !NewIncAlignment) {
176 } else if (NewAlignment > NewIncAlignment) {
177 if (NewAlignment % NewIncAlignment == 0) {
178 LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: " << NewIncAlignment
180 return NewIncAlignment;
182 } else if (NewIncAlignment > NewAlignment) {
183 if (NewIncAlignment % NewAlignment == 0) {
184 LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: " << NewAlignment
188 } else if (NewIncAlignment == NewAlignment) {
189 LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: " << NewAlignment
198 bool AlignmentFromAssumptionsPass::extractAlignmentInfo(CallInst *I,
200 const SCEV *&AlignSCEV,
201 const SCEV *&OffSCEV) {
202 // An alignment assume must be a statement about the least-significant
203 // bits of the pointer being zero, possibly with some offset.
204 ICmpInst *ICI = dyn_cast<ICmpInst>(I->getArgOperand(0));
208 // This must be an expression of the form: x & m == 0.
209 if (ICI->getPredicate() != ICmpInst::ICMP_EQ)
212 // Swap things around so that the RHS is 0.
213 Value *CmpLHS = ICI->getOperand(0);
214 Value *CmpRHS = ICI->getOperand(1);
215 const SCEV *CmpLHSSCEV = SE->getSCEV(CmpLHS);
216 const SCEV *CmpRHSSCEV = SE->getSCEV(CmpRHS);
217 if (CmpLHSSCEV->isZero())
218 std::swap(CmpLHS, CmpRHS);
219 else if (!CmpRHSSCEV->isZero())
222 BinaryOperator *CmpBO = dyn_cast<BinaryOperator>(CmpLHS);
223 if (!CmpBO || CmpBO->getOpcode() != Instruction::And)
226 // Swap things around so that the right operand of the and is a constant
227 // (the mask); we cannot deal with variable masks.
228 Value *AndLHS = CmpBO->getOperand(0);
229 Value *AndRHS = CmpBO->getOperand(1);
230 const SCEV *AndLHSSCEV = SE->getSCEV(AndLHS);
231 const SCEV *AndRHSSCEV = SE->getSCEV(AndRHS);
232 if (isa<SCEVConstant>(AndLHSSCEV)) {
233 std::swap(AndLHS, AndRHS);
234 std::swap(AndLHSSCEV, AndRHSSCEV);
237 const SCEVConstant *MaskSCEV = dyn_cast<SCEVConstant>(AndRHSSCEV);
241 // The mask must have some trailing ones (otherwise the condition is
242 // trivial and tells us nothing about the alignment of the left operand).
243 unsigned TrailingOnes = MaskSCEV->getAPInt().countTrailingOnes();
247 // Cap the alignment at the maximum with which LLVM can deal (and make sure
248 // we don't overflow the shift).
250 TrailingOnes = std::min(TrailingOnes,
251 unsigned(sizeof(unsigned) * CHAR_BIT - 1));
252 Alignment = std::min(1u << TrailingOnes, +Value::MaximumAlignment);
254 Type *Int64Ty = Type::getInt64Ty(I->getParent()->getParent()->getContext());
255 AlignSCEV = SE->getConstant(Int64Ty, Alignment);
257 // The LHS might be a ptrtoint instruction, or it might be the pointer
261 if (PtrToIntInst *PToI = dyn_cast<PtrToIntInst>(AndLHS)) {
262 AAPtr = PToI->getPointerOperand();
263 OffSCEV = SE->getZero(Int64Ty);
264 } else if (const SCEVAddExpr* AndLHSAddSCEV =
265 dyn_cast<SCEVAddExpr>(AndLHSSCEV)) {
266 // Try to find the ptrtoint; subtract it and the rest is the offset.
267 for (SCEVAddExpr::op_iterator J = AndLHSAddSCEV->op_begin(),
268 JE = AndLHSAddSCEV->op_end(); J != JE; ++J)
269 if (const SCEVUnknown *OpUnk = dyn_cast<SCEVUnknown>(*J))
270 if (PtrToIntInst *PToI = dyn_cast<PtrToIntInst>(OpUnk->getValue())) {
271 AAPtr = PToI->getPointerOperand();
272 OffSCEV = SE->getMinusSCEV(AndLHSAddSCEV, *J);
280 // Sign extend the offset to 64 bits (so that it is like all of the other
282 unsigned OffSCEVBits = OffSCEV->getType()->getPrimitiveSizeInBits();
283 if (OffSCEVBits < 64)
284 OffSCEV = SE->getSignExtendExpr(OffSCEV, Int64Ty);
285 else if (OffSCEVBits > 64)
288 AAPtr = AAPtr->stripPointerCasts();
292 bool AlignmentFromAssumptionsPass::processAssumption(CallInst *ACall) {
294 const SCEV *AlignSCEV, *OffSCEV;
295 if (!extractAlignmentInfo(ACall, AAPtr, AlignSCEV, OffSCEV))
298 // Skip ConstantPointerNull and UndefValue. Assumptions on these shouldn't
299 // affect other users.
300 if (isa<ConstantData>(AAPtr))
303 const SCEV *AASCEV = SE->getSCEV(AAPtr);
305 // Apply the assumption to all other users of the specified pointer.
306 SmallPtrSet<Instruction *, 32> Visited;
307 SmallVector<Instruction*, 16> WorkList;
308 for (User *J : AAPtr->users()) {
312 if (Instruction *K = dyn_cast<Instruction>(J))
313 if (isValidAssumeForContext(ACall, K, DT))
314 WorkList.push_back(K);
317 while (!WorkList.empty()) {
318 Instruction *J = WorkList.pop_back_val();
320 if (LoadInst *LI = dyn_cast<LoadInst>(J)) {
321 unsigned NewAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV,
322 LI->getPointerOperand(), SE);
324 if (NewAlignment > LI->getAlignment()) {
325 LI->setAlignment(MaybeAlign(NewAlignment));
326 ++NumLoadAlignChanged;
328 } else if (StoreInst *SI = dyn_cast<StoreInst>(J)) {
329 unsigned NewAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV,
330 SI->getPointerOperand(), SE);
332 if (NewAlignment > SI->getAlignment()) {
333 SI->setAlignment(MaybeAlign(NewAlignment));
334 ++NumStoreAlignChanged;
336 } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(J)) {
337 unsigned NewDestAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV,
340 LLVM_DEBUG(dbgs() << "\tmem inst: " << NewDestAlignment << "\n";);
341 if (NewDestAlignment > MI->getDestAlignment()) {
342 MI->setDestAlignment(NewDestAlignment);
343 ++NumMemIntAlignChanged;
346 // For memory transfers, there is also a source alignment that
348 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) {
349 unsigned NewSrcAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV,
350 MTI->getSource(), SE);
352 LLVM_DEBUG(dbgs() << "\tmem trans: " << NewSrcAlignment << "\n";);
354 if (NewSrcAlignment > MTI->getSourceAlignment()) {
355 MTI->setSourceAlignment(NewSrcAlignment);
356 ++NumMemIntAlignChanged;
361 // Now that we've updated that use of the pointer, look for other uses of
362 // the pointer to update.
364 for (User *UJ : J->users()) {
365 Instruction *K = cast<Instruction>(UJ);
366 if (!Visited.count(K) && isValidAssumeForContext(ACall, K, DT))
367 WorkList.push_back(K);
374 bool AlignmentFromAssumptions::runOnFunction(Function &F) {
378 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
379 ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
380 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
382 return Impl.runImpl(F, AC, SE, DT);
385 bool AlignmentFromAssumptionsPass::runImpl(Function &F, AssumptionCache &AC,
386 ScalarEvolution *SE_,
387 DominatorTree *DT_) {
391 bool Changed = false;
392 for (auto &AssumeVH : AC.assumptions())
394 Changed |= processAssumption(cast<CallInst>(AssumeVH));
400 AlignmentFromAssumptionsPass::run(Function &F, FunctionAnalysisManager &AM) {
402 AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);
403 ScalarEvolution &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
404 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
405 if (!runImpl(F, AC, &SE, &DT))
406 return PreservedAnalyses::all();
408 PreservedAnalyses PA;
409 PA.preserveSet<CFGAnalyses>();
410 PA.preserve<AAManager>();
411 PA.preserve<ScalarEvolutionAnalysis>();
412 PA.preserve<GlobalsAA>();