1//===- InferAlignment.cpp -------------------------------------------------===//
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// Infer alignment for load, stores and other memory operations based on
10// trailing zero known bits information.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Transforms/Scalar/InferAlignment.h"
15#include "llvm/ADT/APInt.h"
16#include "llvm/ADT/STLFunctionalExtras.h"
17#include "llvm/ADT/ScopedHashTable.h"
18#include "llvm/Analysis/AssumptionCache.h"
19#include "llvm/Analysis/ValueTracking.h"
20#include "llvm/IR/Instruction.h"
21#include "llvm/IR/Instructions.h"
22#include "llvm/IR/IntrinsicInst.h"
23#include "llvm/IR/PatternMatch.h"
24#include "llvm/Support/KnownBits.h"
25#include "llvm/Transforms/Scalar.h"
26#include "llvm/Transforms/Utils/Local.h"
27#include <list>
28
29using namespace llvm;
30using namespace llvm::PatternMatch;
31
32static bool tryToImproveAlign(
33 const DataLayout &DL, Instruction *I,
34 function_ref<Align(Value *PtrOp, Align OldAlign, Align PrefAlign)> Fn) {
35
36 if (auto *PtrOp = getLoadStorePointerOperand(V: I)) {
37 Align OldAlign = getLoadStoreAlignment(I);
38 Align PrefAlign = DL.getPrefTypeAlign(Ty: getLoadStoreType(I));
39
40 Align NewAlign = Fn(PtrOp, OldAlign, PrefAlign);
41 if (NewAlign > OldAlign) {
42 setLoadStoreAlignment(I, NewAlign);
43 return true;
44 }
45 }
46
47 Value *PtrOp;
48 const APInt *Const;
49 if (match(V: I, P: m_And(L: m_PtrToIntOrAddr(Op: m_Value(V&: PtrOp)), R: m_APInt(Res&: Const)))) {
50 Align ActualAlign = Fn(PtrOp, Align(1), Align(1));
51 if (Const->ult(RHS: ActualAlign.value())) {
52 I->replaceAllUsesWith(V: Constant::getNullValue(Ty: I->getType()));
53 return true;
54 }
55 if (Const->uge(
56 RHS: APInt::getBitsSetFrom(numBits: Const->getBitWidth(), loBit: Log2(A: ActualAlign)))) {
57 I->replaceAllUsesWith(V: I->getOperand(i: 0));
58 return true;
59 }
60 }
61 if (match(V: I, P: m_Trunc(Op: m_PtrToIntOrAddr(Op: m_Value(V&: PtrOp))))) {
62 Align ActualAlign = Fn(PtrOp, Align(1), Align(1));
63 if (Log2(A: ActualAlign) >= I->getType()->getScalarSizeInBits()) {
64 I->replaceAllUsesWith(V: Constant::getNullValue(Ty: I->getType()));
65 return true;
66 }
67 }
68
69 IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: I);
70 if (!II)
71 return false;
72
73 if (!isa<MemIntrinsic>(Val: II) &&
74 II->getIntrinsicID() != Intrinsic::masked_load &&
75 II->getIntrinsicID() != Intrinsic::masked_store)
76 return false;
77
78 bool Changed = false;
79 for (unsigned ArgNo = 0; ArgNo != II->arg_size(); ++ArgNo) {
80 Value *Arg = II->getArgOperand(i: ArgNo);
81 if (!Arg->getType()->isPointerTy())
82 continue;
83
84 // The align attribute only proves the alignment if passing poison is UB
85 // (e.g. noundef): otherwise a zero-length memset may pass an unaligned,
86 // poison pointer, so it must not seed the base pointer alignment.
87 Align OldAlign = II->getParamAlign(ArgNo).valueOrOne();
88 Align KnownAlign = II->isPassingUndefUB(ArgNo) ? OldAlign : Align(1);
89 Align NewAlign = Fn(Arg, KnownAlign, Align(1));
90 if (NewAlign <= OldAlign)
91 continue;
92
93 II->addParamAttr(ArgNo,
94 Attr: Attribute::getWithAlignment(Context&: II->getContext(), Alignment: NewAlign));
95 Changed = true;
96 }
97 return Changed;
98}
99
100using ScopedHT =
101 ScopedHashTable<Value *, Align, DenseMapInfo<Value *>, BumpPtrAllocator>;
102struct AlignmentScope {
103 // If BB is nullptr, the BB is processed.
104 BasicBlock *BB;
105 DomTreeNode::const_iterator Iter;
106 DomTreeNode::const_iterator End;
107 ScopedHT::ScopeTy Scope;
108
109 AlignmentScope(DomTreeNode *N, ScopedHT &Table)
110 : BB(N->getBlock()), Iter(N->begin()), End(N->end()), Scope(Table) {}
111};
112
113bool inferAlignment(Function &F, AssumptionCache &AC, DominatorTree &DT) {
114 const DataLayout &DL = F.getDataLayout();
115 bool Changed = false;
116
117 // Enforce preferred type alignment if possible. We do this as a separate
118 // pass first, because it may improve the alignments we infer below.
119 for (BasicBlock &BB : F) {
120 for (Instruction &I : BB) {
121 Changed |= tryToImproveAlign(
122 DL, I: &I, Fn: [&](Value *PtrOp, Align OldAlign, Align PrefAlign) {
123 if (PrefAlign > OldAlign)
124 return std::max(a: OldAlign,
125 b: tryEnforceAlignment(V: PtrOp, PrefAlign, DL));
126 return OldAlign;
127 });
128 }
129 }
130
131 // Compute alignment from known bits.
132 auto InferFromKnownBits = [&](Instruction &I, Value *PtrOp) {
133 KnownBits Known = computeKnownBits(V: PtrOp, DL, AC: &AC, CxtI: &I, DT: &DT);
134 unsigned TrailZ =
135 std::min(a: Known.countMinTrailingZeros(), b: +Value::MaxAlignmentExponent);
136 return Align(1ull << std::min(a: Known.getBitWidth() - 1, b: TrailZ));
137 };
138
139 // Propagate alignment between loads and stores that originate from the
140 // same base pointer.
141 ScopedHT BestBasePointerAligns;
142 auto InferFromBasePointer = [&](Value *PtrOp, Align LoadStoreAlign) {
143 APInt OffsetFromBase(DL.getIndexTypeSizeInBits(Ty: PtrOp->getType()), 0);
144 PtrOp = PtrOp->stripAndAccumulateConstantOffsets(DL, Offset&: OffsetFromBase, AllowNonInbounds: true);
145 // Derive the base pointer alignment from the load/store alignment
146 // and the offset from the base pointer.
147 Align BasePointerAlign =
148 commonAlignment(A: LoadStoreAlign, Offset: OffsetFromBase.getLimitedValue());
149
150 if (auto BestAlign = BestBasePointerAligns.lookup(Key: PtrOp);
151 BestAlign != Align()) {
152 // If the stored base pointer alignment is better than the
153 // base pointer alignment we derived, we may be able to use it
154 // to improve the load/store alignment. If not, store the
155 // improved base pointer alignment for future iterations.
156 if (BestAlign > BasePointerAlign) {
157 Align BetterLoadStoreAlign =
158 commonAlignment(A: BestAlign, Offset: OffsetFromBase.getLimitedValue());
159 return BetterLoadStoreAlign;
160 }
161 }
162
163 BestBasePointerAligns.insert(Key: PtrOp, Val: BasePointerAlign);
164 return LoadStoreAlign;
165 };
166
167 // AlignmentScope is unmovable.
168 std::list<AlignmentScope> Stack;
169 Stack.emplace_back(args: DT.getRootNode(), args&: BestBasePointerAligns);
170 while (!Stack.empty()) {
171 AlignmentScope &Top = Stack.back();
172 if (Top.BB) {
173 for (Instruction &I : *Top.BB) {
174 Changed |= tryToImproveAlign(
175 DL, I: &I, Fn: [&](Value *PtrOp, Align OldAlign, Align PrefAlign) {
176 return std::max(a: InferFromKnownBits(I, PtrOp),
177 b: InferFromBasePointer(PtrOp, OldAlign));
178 });
179 }
180 Top.BB = nullptr;
181 }
182
183 if (Top.Iter != Top.End)
184 Stack.emplace_back(args: *Top.Iter++, args&: BestBasePointerAligns);
185 else
186 Stack.pop_back();
187 }
188
189 return Changed;
190}
191
192PreservedAnalyses InferAlignmentPass::run(Function &F,
193 FunctionAnalysisManager &AM) {
194 AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(IR&: F);
195 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
196 inferAlignment(F, AC, DT);
197 // Changes to alignment shouldn't invalidated analyses.
198 return PreservedAnalyses::all();
199}
200