1 //===----------------------- AlignmentFromAssumptions.cpp -----------------===// 2 // Set Load/Store Alignments From Assumptions 3 // 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 7 // 8 //===----------------------------------------------------------------------===// 9 // 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. 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" 35 using namespace llvm; 36 37 STATISTIC(NumLoadAlignChanged, 38 "Number of loads changed by alignment assumptions"); 39 STATISTIC(NumStoreAlignChanged, 40 "Number of stores changed by alignment assumptions"); 41 STATISTIC(NumMemIntAlignChanged, 42 "Number of memory intrinsics changed by alignment assumptions"); 43 44 // Given an expression for the (constant) alignment, AlignSCEV, and an 45 // expression for the displacement between a pointer and the aligned address, 46 // DiffSCEV, compute the alignment of the displaced pointer if it can be reduced 47 // to a constant. Using SCEV to compute alignment handles the case where 48 // DiffSCEV is a recurrence with constant start such that the aligned offset 49 // is constant. e.g. {16,+,32} % 32 -> 16. 50 static 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 the 64 // displaced pointer has the same alignment as the aligned pointer, so 65 // 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 a 70 // 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 an 80 // alignment AlignSCEV. Use that information, if possible, to compute a new 81 // alignment for Ptr. 82 static 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 // On a platform with 32-bit allocas, but 64-bit flat/global pointer sizes 87 // (*cough* AMDGPU), the effective SCEV type of AASCEV and PtrSCEV 88 // may disagree. Trunc/extend so they agree. 89 PtrSCEV = SE->getTruncateOrZeroExtend( 90 PtrSCEV, SE->getEffectiveSCEVType(AASCEV->getType())); 91 const SCEV *DiffSCEV = SE->getMinusSCEV(PtrSCEV, AASCEV); 92 if (isa<SCEVCouldNotCompute>(DiffSCEV)) 93 return Align(1); 94 95 // On 32-bit platforms, DiffSCEV might now have type i32 -- we've always 96 // sign-extended OffSCEV to i64, so make sure they agree again. 97 DiffSCEV = SE->getNoopOrSignExtend(DiffSCEV, OffSCEV->getType()); 98 99 // What we really want to know is the overall offset to the aligned 100 // address. This address is displaced by the provided offset. 101 DiffSCEV = SE->getAddExpr(DiffSCEV, OffSCEV); 102 103 LLVM_DEBUG(dbgs() << "AFI: alignment of " << *Ptr << " relative to " 104 << *AlignSCEV << " and offset " << *OffSCEV 105 << " using diff " << *DiffSCEV << "\n"); 106 107 if (MaybeAlign NewAlignment = getNewAlignmentDiff(DiffSCEV, AlignSCEV, SE)) { 108 LLVM_DEBUG(dbgs() << "\tnew alignment: " << DebugStr(NewAlignment) << "\n"); 109 return *NewAlignment; 110 } 111 112 if (const SCEVAddRecExpr *DiffARSCEV = dyn_cast<SCEVAddRecExpr>(DiffSCEV)) { 113 // The relative offset to the alignment assumption did not yield a constant, 114 // but we should try harder: if we assume that a is 32-byte aligned, then in 115 // for (i = 0; i < 1024; i += 4) r += a[i]; not all of the loads from a are 116 // 32-byte aligned, but instead alternate between 32 and 16-byte alignment. 117 // As a result, the new alignment will not be a constant, but can still 118 // be improved over the default (of 4) to 16. 119 120 const SCEV *DiffStartSCEV = DiffARSCEV->getStart(); 121 const SCEV *DiffIncSCEV = DiffARSCEV->getStepRecurrence(*SE); 122 123 LLVM_DEBUG(dbgs() << "\ttrying start/inc alignment using start " 124 << *DiffStartSCEV << " and inc " << *DiffIncSCEV << "\n"); 125 126 // Now compute the new alignment using the displacement to the value in the 127 // first iteration, and also the alignment using the per-iteration delta. 128 // If these are the same, then use that answer. Otherwise, use the smaller 129 // one, but only if it divides the larger one. 130 MaybeAlign NewAlignment = getNewAlignmentDiff(DiffStartSCEV, AlignSCEV, SE); 131 MaybeAlign NewIncAlignment = 132 getNewAlignmentDiff(DiffIncSCEV, AlignSCEV, SE); 133 134 LLVM_DEBUG(dbgs() << "\tnew start alignment: " << DebugStr(NewAlignment) 135 << "\n"); 136 LLVM_DEBUG(dbgs() << "\tnew inc alignment: " << DebugStr(NewIncAlignment) 137 << "\n"); 138 139 if (!NewAlignment || !NewIncAlignment) 140 return Align(1); 141 142 const Align NewAlign = *NewAlignment; 143 const Align NewIncAlign = *NewIncAlignment; 144 if (NewAlign > NewIncAlign) { 145 LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: " 146 << DebugStr(NewIncAlign) << "\n"); 147 return NewIncAlign; 148 } 149 if (NewIncAlign > NewAlign) { 150 LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: " << DebugStr(NewAlign) 151 << "\n"); 152 return NewAlign; 153 } 154 assert(NewIncAlign == NewAlign); 155 LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: " << DebugStr(NewAlign) 156 << "\n"); 157 return NewAlign; 158 } 159 160 return Align(1); 161 } 162 163 bool AlignmentFromAssumptionsPass::extractAlignmentInfo(CallInst *I, 164 unsigned Idx, 165 Value *&AAPtr, 166 const SCEV *&AlignSCEV, 167 const SCEV *&OffSCEV) { 168 Type *Int64Ty = Type::getInt64Ty(I->getContext()); 169 OperandBundleUse AlignOB = I->getOperandBundleAt(Idx); 170 if (AlignOB.getTagName() != "align") 171 return false; 172 assert(AlignOB.Inputs.size() >= 2); 173 AAPtr = AlignOB.Inputs[0].get(); 174 // TODO: Consider accumulating the offset to the base. 175 AAPtr = AAPtr->stripPointerCastsSameRepresentation(); 176 AlignSCEV = SE->getSCEV(AlignOB.Inputs[1].get()); 177 AlignSCEV = SE->getTruncateOrZeroExtend(AlignSCEV, Int64Ty); 178 if (!isa<SCEVConstant>(AlignSCEV)) 179 // Added to suppress a crash because consumer doesn't expect non-constant 180 // alignments in the assume bundle. TODO: Consider generalizing caller. 181 return false; 182 if (AlignOB.Inputs.size() == 3) 183 OffSCEV = SE->getSCEV(AlignOB.Inputs[2].get()); 184 else 185 OffSCEV = SE->getZero(Int64Ty); 186 OffSCEV = SE->getTruncateOrZeroExtend(OffSCEV, Int64Ty); 187 return true; 188 } 189 190 bool AlignmentFromAssumptionsPass::processAssumption(CallInst *ACall, 191 unsigned Idx) { 192 Value *AAPtr; 193 const SCEV *AlignSCEV, *OffSCEV; 194 if (!extractAlignmentInfo(ACall, Idx, AAPtr, AlignSCEV, OffSCEV)) 195 return false; 196 197 // Skip ConstantPointerNull and UndefValue. Assumptions on these shouldn't 198 // affect other users. 199 if (isa<ConstantData>(AAPtr)) 200 return false; 201 202 const SCEV *AASCEV = SE->getSCEV(AAPtr); 203 204 // Apply the assumption to all other users of the specified pointer. 205 SmallPtrSet<Instruction *, 32> Visited; 206 SmallVector<Instruction*, 16> WorkList; 207 for (User *J : AAPtr->users()) { 208 if (J == ACall) 209 continue; 210 211 if (Instruction *K = dyn_cast<Instruction>(J)) 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 that 249 // 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 of 265 // the pointer to update. 266 Visited.insert(J); 267 for (User *UJ : J->users()) { 268 Instruction *K = cast<Instruction>(UJ); 269 if (!Visited.count(K)) 270 WorkList.push_back(K); 271 } 272 } 273 274 return true; 275 } 276 277 bool AlignmentFromAssumptionsPass::runImpl(Function &F, AssumptionCache &AC, 278 ScalarEvolution *SE_, 279 DominatorTree *DT_) { 280 SE = SE_; 281 DT = DT_; 282 283 bool Changed = false; 284 for (auto &AssumeVH : AC.assumptions()) 285 if (AssumeVH) { 286 CallInst *Call = cast<CallInst>(AssumeVH); 287 for (unsigned Idx = 0; Idx < Call->getNumOperandBundles(); Idx++) 288 Changed |= processAssumption(Call, Idx); 289 } 290 291 return Changed; 292 } 293 294 PreservedAnalyses 295 AlignmentFromAssumptionsPass::run(Function &F, FunctionAnalysisManager &AM) { 296 297 AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F); 298 ScalarEvolution &SE = AM.getResult<ScalarEvolutionAnalysis>(F); 299 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F); 300 if (!runImpl(F, AC, &SE, &DT)) 301 return PreservedAnalyses::all(); 302 303 PreservedAnalyses PA; 304 PA.preserveSet<CFGAnalyses>(); 305 PA.preserve<ScalarEvolutionAnalysis>(); 306 return PA; 307 } 308