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 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 always 92 // 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 aligned 96 // 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 " << *OffSCEV 101 << " 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 in 111 // for (i = 0; i < 1024; i += 4) r += a[i]; not all of the loads from a are 112 // 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 still 114 // 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 the 123 // first iteration, and also the alignment using the per-iteration delta. 124 // If these are the same, then use that answer. Otherwise, use the smaller 125 // 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 159 bool 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.getTagName() != "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-constant 176 // 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 else 184 OffSCEV = SE->getZero(Int64Ty); 185 OffSCEV = SE->getTruncateOrZeroExtend(OffSCEV, Int64Ty); 186 return true; 187 } 188 189 bool 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't 197 // 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 WorkList.push_back(K); 212 } 213 214 while (!WorkList.empty()) { 215 Instruction *J = WorkList.pop_back_val(); 216 if (LoadInst *LI = dyn_cast<LoadInst>(J)) { 217 if (!isValidAssumeForContext(ACall, J, DT)) 218 continue; 219 Align NewAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV, 220 LI->getPointerOperand(), SE); 221 if (NewAlignment > LI->getAlign()) { 222 LI->setAlignment(NewAlignment); 223 ++NumLoadAlignChanged; 224 } 225 } else if (StoreInst *SI = dyn_cast<StoreInst>(J)) { 226 if (!isValidAssumeForContext(ACall, J, DT)) 227 continue; 228 Align NewAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV, 229 SI->getPointerOperand(), SE); 230 if (NewAlignment > SI->getAlign()) { 231 SI->setAlignment(NewAlignment); 232 ++NumStoreAlignChanged; 233 } 234 } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(J)) { 235 if (!isValidAssumeForContext(ACall, J, DT)) 236 continue; 237 Align NewDestAlignment = 238 getNewAlignment(AASCEV, AlignSCEV, OffSCEV, MI->getDest(), SE); 239 240 LLVM_DEBUG(dbgs() << "\tmem inst: " << DebugStr(NewDestAlignment) 241 << "\n";); 242 if (NewDestAlignment > *MI->getDestAlign()) { 243 MI->setDestAlignment(NewDestAlignment); 244 ++NumMemIntAlignChanged; 245 } 246 247 // For memory transfers, there is also a source alignment that 248 // can be set. 249 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) { 250 Align NewSrcAlignment = 251 getNewAlignment(AASCEV, AlignSCEV, OffSCEV, MTI->getSource(), SE); 252 253 LLVM_DEBUG(dbgs() << "\tmem trans: " << DebugStr(NewSrcAlignment) 254 << "\n";); 255 256 if (NewSrcAlignment > *MTI->getSourceAlign()) { 257 MTI->setSourceAlignment(NewSrcAlignment); 258 ++NumMemIntAlignChanged; 259 } 260 } 261 } 262 263 // Now that we've updated that use of the pointer, look for other uses of 264 // the pointer to update. 265 Visited.insert(J); 266 if (isa<GetElementPtrInst>(J) || isa<PHINode>(J)) 267 for (auto &U : J->uses()) { 268 if (U->getType()->isPointerTy()) { 269 Instruction *K = cast<Instruction>(U.getUser()); 270 StoreInst *SI = dyn_cast<StoreInst>(K); 271 if (SI && SI->getPointerOperandIndex() != U.getOperandNo()) 272 continue; 273 if (!Visited.count(K)) 274 WorkList.push_back(K); 275 } 276 } 277 } 278 279 return true; 280 } 281 282 bool AlignmentFromAssumptionsPass::runImpl(Function &F, AssumptionCache &AC, 283 ScalarEvolution *SE_, 284 DominatorTree *DT_) { 285 SE = SE_; 286 DT = DT_; 287 288 bool Changed = false; 289 for (auto &AssumeVH : AC.assumptions()) 290 if (AssumeVH) { 291 CallInst *Call = cast<CallInst>(AssumeVH); 292 for (unsigned Idx = 0; Idx < Call->getNumOperandBundles(); Idx++) 293 Changed |= processAssumption(Call, Idx); 294 } 295 296 return Changed; 297 } 298 299 PreservedAnalyses 300 AlignmentFromAssumptionsPass::run(Function &F, FunctionAnalysisManager &AM) { 301 302 AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F); 303 ScalarEvolution &SE = AM.getResult<ScalarEvolutionAnalysis>(F); 304 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F); 305 if (!runImpl(F, AC, &SE, &DT)) 306 return PreservedAnalyses::all(); 307 308 PreservedAnalyses PA; 309 PA.preserveSet<CFGAnalyses>(); 310 PA.preserve<ScalarEvolutionAnalysis>(); 311 return PA; 312 } 313