152 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// Infer alignment for load, stores and other memory operations based on10// 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/IR/IntrinsicInst.h"19#include "llvm/Support/KnownBits.h"20#include "llvm/Transforms/Scalar.h"21#include "llvm/Transforms/Utils/Local.h"22 23using namespace llvm;24 25static bool tryToImproveAlign(26 const DataLayout &DL, Instruction *I,27 function_ref<Align(Value *PtrOp, Align OldAlign, Align PrefAlign)> Fn) {28 29 if (auto *PtrOp = getLoadStorePointerOperand(I)) {30 Align OldAlign = getLoadStoreAlignment(I);31 Align PrefAlign = DL.getPrefTypeAlign(getLoadStoreType(I));32 33 Align NewAlign = Fn(PtrOp, OldAlign, PrefAlign);34 if (NewAlign > OldAlign) {35 setLoadStoreAlignment(I, NewAlign);36 return true;37 }38 }39 40 IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);41 if (!II)42 return false;43 44 // TODO: Handle more memory intrinsics.45 switch (II->getIntrinsicID()) {46 case Intrinsic::masked_load:47 case Intrinsic::masked_store: {48 unsigned PtrOpIdx = II->getIntrinsicID() == Intrinsic::masked_load ? 0 : 1;49 Value *PtrOp = II->getArgOperand(PtrOpIdx);50 Type *Type = II->getIntrinsicID() == Intrinsic::masked_load51 ? II->getType()52 : II->getArgOperand(0)->getType();53 54 Align OldAlign = II->getParamAlign(PtrOpIdx).valueOrOne();55 Align PrefAlign = DL.getPrefTypeAlign(Type);56 Align NewAlign = Fn(PtrOp, OldAlign, PrefAlign);57 if (NewAlign <= OldAlign)58 return false;59 60 II->addParamAttr(PtrOpIdx,61 Attribute::getWithAlignment(II->getContext(), NewAlign));62 return true;63 }64 default:65 return false;66 }67}68 69bool inferAlignment(Function &F, AssumptionCache &AC, DominatorTree &DT) {70 const DataLayout &DL = F.getDataLayout();71 bool Changed = false;72 73 // Enforce preferred type alignment if possible. We do this as a separate74 // pass first, because it may improve the alignments we infer below.75 for (BasicBlock &BB : F) {76 for (Instruction &I : BB) {77 Changed |= tryToImproveAlign(78 DL, &I, [&](Value *PtrOp, Align OldAlign, Align PrefAlign) {79 if (PrefAlign > OldAlign)80 return std::max(OldAlign,81 tryEnforceAlignment(PtrOp, PrefAlign, DL));82 return OldAlign;83 });84 }85 }86 87 // Compute alignment from known bits.88 auto InferFromKnownBits = [&](Instruction &I, Value *PtrOp) {89 KnownBits Known = computeKnownBits(PtrOp, DL, &AC, &I, &DT);90 unsigned TrailZ =91 std::min(Known.countMinTrailingZeros(), +Value::MaxAlignmentExponent);92 return Align(1ull << std::min(Known.getBitWidth() - 1, TrailZ));93 };94 95 // Propagate alignment between loads and stores that originate from the96 // same base pointer.97 DenseMap<Value *, Align> BestBasePointerAligns;98 auto InferFromBasePointer = [&](Value *PtrOp, Align LoadStoreAlign) {99 APInt OffsetFromBase(DL.getIndexTypeSizeInBits(PtrOp->getType()), 0);100 PtrOp = PtrOp->stripAndAccumulateConstantOffsets(DL, OffsetFromBase, true);101 // Derive the base pointer alignment from the load/store alignment102 // and the offset from the base pointer.103 Align BasePointerAlign =104 commonAlignment(LoadStoreAlign, OffsetFromBase.getLimitedValue());105 106 auto [It, Inserted] =107 BestBasePointerAligns.try_emplace(PtrOp, BasePointerAlign);108 if (!Inserted) {109 // If the stored base pointer alignment is better than the110 // base pointer alignment we derived, we may be able to use it111 // to improve the load/store alignment. If not, store the112 // improved base pointer alignment for future iterations.113 if (It->second > BasePointerAlign) {114 Align BetterLoadStoreAlign =115 commonAlignment(It->second, OffsetFromBase.getLimitedValue());116 return BetterLoadStoreAlign;117 }118 It->second = BasePointerAlign;119 }120 return LoadStoreAlign;121 };122 123 for (BasicBlock &BB : F) {124 // We need to reset the map for each block because alignment information125 // can only be propagated from instruction A to B if A dominates B.126 // This is because control flow (and exception throwing) could be dependent127 // on the address (and its alignment) at runtime. Some sort of dominator128 // tree approach could be better, but doing a simple forward pass through a129 // single basic block is correct too.130 BestBasePointerAligns.clear();131 132 for (Instruction &I : BB) {133 Changed |= tryToImproveAlign(134 DL, &I, [&](Value *PtrOp, Align OldAlign, Align PrefAlign) {135 return std::max(InferFromKnownBits(I, PtrOp),136 InferFromBasePointer(PtrOp, OldAlign));137 });138 }139 }140 141 return Changed;142}143 144PreservedAnalyses InferAlignmentPass::run(Function &F,145 FunctionAnalysisManager &AM) {146 AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);147 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);148 inferAlignment(F, AC, DT);149 // Changes to alignment shouldn't invalidated analyses.150 return PreservedAnalyses::all();151}152