314 lines · cpp
1//===----------------------- AlignmentFromAssumptions.cpp -----------------===//2// Set Load/Store Alignments From Assumptions3//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-exception7//8//===----------------------------------------------------------------------===//9//10// This file implements a ScalarEvolution-based transformation to set11// the alignments of load, stores and memory intrinsics based on the truth12// expressions of assume intrinsics. The primary motivation is to handle13// complex alignment assumptions that apply to vector loads and stores that14// appear after vectorization and unrolling.15//16//===----------------------------------------------------------------------===//17 18#include "llvm/Transforms/Scalar/AlignmentFromAssumptions.h"19#include "llvm/ADT/SmallPtrSet.h"20#include "llvm/ADT/Statistic.h"21#include "llvm/Analysis/AliasAnalysis.h"22#include "llvm/Analysis/AssumptionCache.h"23#include "llvm/Analysis/GlobalsModRef.h"24#include "llvm/Analysis/LoopInfo.h"25#include "llvm/Analysis/ScalarEvolutionExpressions.h"26#include "llvm/Analysis/ValueTracking.h"27#include "llvm/IR/Dominators.h"28#include "llvm/IR/Instruction.h"29#include "llvm/IR/Instructions.h"30#include "llvm/IR/IntrinsicInst.h"31#include "llvm/Support/Debug.h"32#include "llvm/Support/raw_ostream.h"33 34#define DEBUG_TYPE "alignment-from-assumptions"35using namespace llvm;36 37STATISTIC(NumLoadAlignChanged,38 "Number of loads changed by alignment assumptions");39STATISTIC(NumStoreAlignChanged,40 "Number of stores changed by alignment assumptions");41STATISTIC(NumMemIntAlignChanged,42 "Number of memory intrinsics changed by alignment assumptions");43 44// Given an expression for the (constant) alignment, AlignSCEV, and an45// expression for the displacement between a pointer and the aligned address,46// DiffSCEV, compute the alignment of the displaced pointer if it can be reduced47// to a constant. Using SCEV to compute alignment handles the case where48// DiffSCEV is a recurrence with constant start such that the aligned offset49// is constant. e.g. {16,+,32} % 32 -> 16.50static MaybeAlign getNewAlignmentDiff(const SCEV *DiffSCEV,51 const SCEV *AlignSCEV,52 ScalarEvolution *SE) {53 // DiffUnits = Diff % int64_t(Alignment)54 const SCEV *DiffUnitsSCEV = SE->getURemExpr(DiffSCEV, AlignSCEV);55 56 LLVM_DEBUG(dbgs() << "\talignment relative to " << *AlignSCEV << " is "57 << *DiffUnitsSCEV << " (diff: " << *DiffSCEV << ")\n");58 59 if (const SCEVConstant *ConstDUSCEV =60 dyn_cast<SCEVConstant>(DiffUnitsSCEV)) {61 int64_t DiffUnits = ConstDUSCEV->getValue()->getSExtValue();62 63 // If the displacement is an exact multiple of the alignment, then the64 // displaced pointer has the same alignment as the aligned pointer, so65 // return the alignment value.66 if (!DiffUnits)67 return cast<SCEVConstant>(AlignSCEV)->getValue()->getAlignValue();68 69 // If the displacement is not an exact multiple, but the remainder is a70 // constant, then return this remainder (but only if it is a power of 2).71 uint64_t DiffUnitsAbs = std::abs(DiffUnits);72 if (isPowerOf2_64(DiffUnitsAbs))73 return Align(DiffUnitsAbs);74 }75 76 return std::nullopt;77}78 79// There is an address given by an offset OffSCEV from AASCEV which has an80// alignment AlignSCEV. Use that information, if possible, to compute a new81// alignment for Ptr.82static Align getNewAlignment(const SCEV *AASCEV, const SCEV *AlignSCEV,83 const SCEV *OffSCEV, Value *Ptr,84 ScalarEvolution *SE) {85 const SCEV *PtrSCEV = SE->getSCEV(Ptr);86 87 const SCEV *DiffSCEV = SE->getMinusSCEV(PtrSCEV, AASCEV);88 if (isa<SCEVCouldNotCompute>(DiffSCEV))89 return Align(1);90 91 // On 32-bit platforms, DiffSCEV might now have type i32 -- we've always92 // sign-extended OffSCEV to i64, so make sure they agree again.93 DiffSCEV = SE->getNoopOrSignExtend(DiffSCEV, OffSCEV->getType());94 95 // What we really want to know is the overall offset to the aligned96 // address. This address is displaced by the provided offset.97 DiffSCEV = SE->getAddExpr(DiffSCEV, OffSCEV);98 99 LLVM_DEBUG(dbgs() << "AFI: alignment of " << *Ptr << " relative to "100 << *AlignSCEV << " and offset " << *OffSCEV101 << " using diff " << *DiffSCEV << "\n");102 103 if (MaybeAlign NewAlignment = getNewAlignmentDiff(DiffSCEV, AlignSCEV, SE)) {104 LLVM_DEBUG(dbgs() << "\tnew alignment: " << DebugStr(NewAlignment) << "\n");105 return *NewAlignment;106 }107 108 if (const SCEVAddRecExpr *DiffARSCEV = dyn_cast<SCEVAddRecExpr>(DiffSCEV)) {109 // The relative offset to the alignment assumption did not yield a constant,110 // but we should try harder: if we assume that a is 32-byte aligned, then in111 // for (i = 0; i < 1024; i += 4) r += a[i]; not all of the loads from a are112 // 32-byte aligned, but instead alternate between 32 and 16-byte alignment.113 // As a result, the new alignment will not be a constant, but can still114 // be improved over the default (of 4) to 16.115 116 const SCEV *DiffStartSCEV = DiffARSCEV->getStart();117 const SCEV *DiffIncSCEV = DiffARSCEV->getStepRecurrence(*SE);118 119 LLVM_DEBUG(dbgs() << "\ttrying start/inc alignment using start "120 << *DiffStartSCEV << " and inc " << *DiffIncSCEV << "\n");121 122 // Now compute the new alignment using the displacement to the value in the123 // first iteration, and also the alignment using the per-iteration delta.124 // If these are the same, then use that answer. Otherwise, use the smaller125 // one, but only if it divides the larger one.126 MaybeAlign NewAlignment = getNewAlignmentDiff(DiffStartSCEV, AlignSCEV, SE);127 MaybeAlign NewIncAlignment =128 getNewAlignmentDiff(DiffIncSCEV, AlignSCEV, SE);129 130 LLVM_DEBUG(dbgs() << "\tnew start alignment: " << DebugStr(NewAlignment)131 << "\n");132 LLVM_DEBUG(dbgs() << "\tnew inc alignment: " << DebugStr(NewIncAlignment)133 << "\n");134 135 if (!NewAlignment || !NewIncAlignment)136 return Align(1);137 138 const Align NewAlign = *NewAlignment;139 const Align NewIncAlign = *NewIncAlignment;140 if (NewAlign > NewIncAlign) {141 LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: "142 << DebugStr(NewIncAlign) << "\n");143 return NewIncAlign;144 }145 if (NewIncAlign > NewAlign) {146 LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: " << DebugStr(NewAlign)147 << "\n");148 return NewAlign;149 }150 assert(NewIncAlign == NewAlign);151 LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: " << DebugStr(NewAlign)152 << "\n");153 return NewAlign;154 }155 156 return Align(1);157}158 159bool AlignmentFromAssumptionsPass::extractAlignmentInfo(CallInst *I,160 unsigned Idx,161 Value *&AAPtr,162 const SCEV *&AlignSCEV,163 const SCEV *&OffSCEV) {164 Type *Int64Ty = Type::getInt64Ty(I->getContext());165 OperandBundleUse AlignOB = I->getOperandBundleAt(Idx);166 if (AlignOB.getTagID() != LLVMContext::OB_align)167 return false;168 assert(AlignOB.Inputs.size() >= 2);169 AAPtr = AlignOB.Inputs[0].get();170 // TODO: Consider accumulating the offset to the base.171 AAPtr = AAPtr->stripPointerCastsSameRepresentation();172 AlignSCEV = SE->getSCEV(AlignOB.Inputs[1].get());173 AlignSCEV = SE->getTruncateOrZeroExtend(AlignSCEV, Int64Ty);174 if (!isa<SCEVConstant>(AlignSCEV))175 // Added to suppress a crash because consumer doesn't expect non-constant176 // alignments in the assume bundle. TODO: Consider generalizing caller.177 return false;178 if (!cast<SCEVConstant>(AlignSCEV)->getAPInt().isPowerOf2())179 // Only power of two alignments are supported.180 return false;181 if (AlignOB.Inputs.size() == 3)182 OffSCEV = SE->getSCEV(AlignOB.Inputs[2].get());183 else184 OffSCEV = SE->getZero(Int64Ty);185 OffSCEV = SE->getTruncateOrZeroExtend(OffSCEV, Int64Ty);186 return true;187}188 189bool AlignmentFromAssumptionsPass::processAssumption(CallInst *ACall,190 unsigned Idx) {191 Value *AAPtr;192 const SCEV *AlignSCEV, *OffSCEV;193 if (!extractAlignmentInfo(ACall, Idx, AAPtr, AlignSCEV, OffSCEV))194 return false;195 196 // Skip ConstantPointerNull and UndefValue. Assumptions on these shouldn't197 // affect other users.198 if (isa<ConstantData>(AAPtr))199 return false;200 201 const SCEV *AASCEV = SE->getSCEV(AAPtr);202 203 // Apply the assumption to all other users of the specified pointer.204 SmallPtrSet<Instruction *, 32> Visited;205 SmallVector<Instruction*, 16> WorkList;206 for (User *J : AAPtr->users()) {207 if (J == ACall)208 continue;209 210 if (Instruction *K = dyn_cast<Instruction>(J))211 if (K->getFunction() == ACall->getFunction())212 WorkList.push_back(K);213 }214 215 while (!WorkList.empty()) {216 Instruction *J = WorkList.pop_back_val();217 if (LoadInst *LI = dyn_cast<LoadInst>(J)) {218 if (!isValidAssumeForContext(ACall, J, DT))219 continue;220 Align NewAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV,221 LI->getPointerOperand(), SE);222 if (NewAlignment > LI->getAlign()) {223 LI->setAlignment(NewAlignment);224 ++NumLoadAlignChanged;225 }226 } else if (StoreInst *SI = dyn_cast<StoreInst>(J)) {227 if (!isValidAssumeForContext(ACall, J, DT))228 continue;229 Align NewAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV,230 SI->getPointerOperand(), SE);231 if (NewAlignment > SI->getAlign()) {232 SI->setAlignment(NewAlignment);233 ++NumStoreAlignChanged;234 }235 } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(J)) {236 if (!isValidAssumeForContext(ACall, J, DT))237 continue;238 Align NewDestAlignment =239 getNewAlignment(AASCEV, AlignSCEV, OffSCEV, MI->getDest(), SE);240 241 LLVM_DEBUG(dbgs() << "\tmem inst: " << DebugStr(NewDestAlignment)242 << "\n";);243 if (NewDestAlignment > *MI->getDestAlign()) {244 MI->setDestAlignment(NewDestAlignment);245 ++NumMemIntAlignChanged;246 }247 248 // For memory transfers, there is also a source alignment that249 // can be set.250 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) {251 Align NewSrcAlignment =252 getNewAlignment(AASCEV, AlignSCEV, OffSCEV, MTI->getSource(), SE);253 254 LLVM_DEBUG(dbgs() << "\tmem trans: " << DebugStr(NewSrcAlignment)255 << "\n";);256 257 if (NewSrcAlignment > *MTI->getSourceAlign()) {258 MTI->setSourceAlignment(NewSrcAlignment);259 ++NumMemIntAlignChanged;260 }261 }262 }263 264 // Now that we've updated that use of the pointer, look for other uses of265 // the pointer to update.266 Visited.insert(J);267 if (isa<GetElementPtrInst>(J) || isa<PHINode>(J))268 for (auto &U : J->uses()) {269 if (U->getType()->isPointerTy()) {270 Instruction *K = cast<Instruction>(U.getUser());271 StoreInst *SI = dyn_cast<StoreInst>(K);272 if (SI && SI->getPointerOperandIndex() != U.getOperandNo())273 continue;274 if (!Visited.count(K))275 WorkList.push_back(K);276 }277 }278 }279 280 return true;281}282 283bool AlignmentFromAssumptionsPass::runImpl(Function &F, AssumptionCache &AC,284 ScalarEvolution *SE_,285 DominatorTree *DT_) {286 SE = SE_;287 DT = DT_;288 289 bool Changed = false;290 for (auto &AssumeVH : AC.assumptions())291 if (AssumeVH) {292 CallInst *Call = cast<CallInst>(AssumeVH);293 for (unsigned Idx = 0; Idx < Call->getNumOperandBundles(); Idx++)294 Changed |= processAssumption(Call, Idx);295 }296 297 return Changed;298}299 300PreservedAnalyses301AlignmentFromAssumptionsPass::run(Function &F, FunctionAnalysisManager &AM) {302 303 AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);304 ScalarEvolution &SE = AM.getResult<ScalarEvolutionAnalysis>(F);305 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);306 if (!runImpl(F, AC, &SE, &DT))307 return PreservedAnalyses::all();308 309 PreservedAnalyses PA;310 PA.preserveSet<CFGAnalyses>();311 PA.preserve<ScalarEvolutionAnalysis>();312 return PA;313}314