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/Analysis/AssumptionCache.h"
16 #include "llvm/Analysis/ValueTracking.h"
17 #include "llvm/IR/Instructions.h"
18 #include "llvm/InitializePasses.h"
19 #include "llvm/Support/KnownBits.h"
20 #include "llvm/Transforms/Scalar.h"
21 #include "llvm/Transforms/Utils/Local.h"
22
23 using namespace llvm;
24
tryToImproveAlign(const DataLayout & DL,Instruction * I,function_ref<Align (Value * PtrOp,Align OldAlign,Align PrefAlign)> Fn)25 static bool tryToImproveAlign(
26 const DataLayout &DL, Instruction *I,
27 function_ref<Align(Value *PtrOp, Align OldAlign, Align PrefAlign)> Fn) {
28 if (auto *LI = dyn_cast<LoadInst>(I)) {
29 Value *PtrOp = LI->getPointerOperand();
30 Align OldAlign = LI->getAlign();
31 Align NewAlign = Fn(PtrOp, OldAlign, DL.getPrefTypeAlign(LI->getType()));
32 if (NewAlign > OldAlign) {
33 LI->setAlignment(NewAlign);
34 return true;
35 }
36 } else if (auto *SI = dyn_cast<StoreInst>(I)) {
37 Value *PtrOp = SI->getPointerOperand();
38 Value *ValOp = SI->getValueOperand();
39 Align OldAlign = SI->getAlign();
40 Align NewAlign = Fn(PtrOp, OldAlign, DL.getPrefTypeAlign(ValOp->getType()));
41 if (NewAlign > OldAlign) {
42 SI->setAlignment(NewAlign);
43 return true;
44 }
45 }
46 // TODO: Also handle memory intrinsics.
47 return false;
48 }
49
inferAlignment(Function & F,AssumptionCache & AC,DominatorTree & DT)50 bool inferAlignment(Function &F, AssumptionCache &AC, DominatorTree &DT) {
51 const DataLayout &DL = F.getDataLayout();
52 bool Changed = false;
53
54 // Enforce preferred type alignment if possible. We do this as a separate
55 // pass first, because it may improve the alignments we infer below.
56 for (BasicBlock &BB : F) {
57 for (Instruction &I : BB) {
58 Changed |= tryToImproveAlign(
59 DL, &I, [&](Value *PtrOp, Align OldAlign, Align PrefAlign) {
60 if (PrefAlign > OldAlign)
61 return std::max(OldAlign,
62 tryEnforceAlignment(PtrOp, PrefAlign, DL));
63 return OldAlign;
64 });
65 }
66 }
67
68 // Compute alignment from known bits.
69 for (BasicBlock &BB : F) {
70 for (Instruction &I : BB) {
71 Changed |= tryToImproveAlign(
72 DL, &I, [&](Value *PtrOp, Align OldAlign, Align PrefAlign) {
73 KnownBits Known = computeKnownBits(PtrOp, DL, 0, &AC, &I, &DT);
74 unsigned TrailZ = std::min(Known.countMinTrailingZeros(),
75 +Value::MaxAlignmentExponent);
76 return Align(1ull << std::min(Known.getBitWidth() - 1, TrailZ));
77 });
78 }
79 }
80
81 return Changed;
82 }
83
run(Function & F,FunctionAnalysisManager & AM)84 PreservedAnalyses InferAlignmentPass::run(Function &F,
85 FunctionAnalysisManager &AM) {
86 AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);
87 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
88 inferAlignment(F, AC, DT);
89 // Changes to alignment shouldn't invalidated analyses.
90 return PreservedAnalyses::all();
91 }
92