AlignmentFromAssumptions.cpp revision 353358
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#define AA_NAME "alignment-from-assumptions" 19#define DEBUG_TYPE AA_NAME 20#include "llvm/Transforms/Scalar/AlignmentFromAssumptions.h" 21#include "llvm/ADT/SmallPtrSet.h" 22#include "llvm/ADT/Statistic.h" 23#include "llvm/Analysis/AliasAnalysis.h" 24#include "llvm/Analysis/AssumptionCache.h" 25#include "llvm/Analysis/GlobalsModRef.h" 26#include "llvm/Analysis/LoopInfo.h" 27#include "llvm/Analysis/ScalarEvolutionExpressions.h" 28#include "llvm/Analysis/ValueTracking.h" 29#include "llvm/IR/Constant.h" 30#include "llvm/IR/Dominators.h" 31#include "llvm/IR/Instruction.h" 32#include "llvm/IR/Intrinsics.h" 33#include "llvm/IR/Module.h" 34#include "llvm/Support/Debug.h" 35#include "llvm/Support/raw_ostream.h" 36#include "llvm/Transforms/Scalar.h" 37using namespace llvm; 38 39STATISTIC(NumLoadAlignChanged, 40 "Number of loads changed by alignment assumptions"); 41STATISTIC(NumStoreAlignChanged, 42 "Number of stores changed by alignment assumptions"); 43STATISTIC(NumMemIntAlignChanged, 44 "Number of memory intrinsics changed by alignment assumptions"); 45 46namespace { 47struct AlignmentFromAssumptions : public FunctionPass { 48 static char ID; // Pass identification, replacement for typeid 49 AlignmentFromAssumptions() : FunctionPass(ID) { 50 initializeAlignmentFromAssumptionsPass(*PassRegistry::getPassRegistry()); 51 } 52 53 bool runOnFunction(Function &F) override; 54 55 void getAnalysisUsage(AnalysisUsage &AU) const override { 56 AU.addRequired<AssumptionCacheTracker>(); 57 AU.addRequired<ScalarEvolutionWrapperPass>(); 58 AU.addRequired<DominatorTreeWrapperPass>(); 59 60 AU.setPreservesCFG(); 61 AU.addPreserved<AAResultsWrapperPass>(); 62 AU.addPreserved<GlobalsAAWrapperPass>(); 63 AU.addPreserved<LoopInfoWrapperPass>(); 64 AU.addPreserved<DominatorTreeWrapperPass>(); 65 AU.addPreserved<ScalarEvolutionWrapperPass>(); 66 } 67 68 AlignmentFromAssumptionsPass Impl; 69}; 70} 71 72char AlignmentFromAssumptions::ID = 0; 73static const char aip_name[] = "Alignment from assumptions"; 74INITIALIZE_PASS_BEGIN(AlignmentFromAssumptions, AA_NAME, 75 aip_name, false, false) 76INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 77INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 78INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) 79INITIALIZE_PASS_END(AlignmentFromAssumptions, AA_NAME, 80 aip_name, false, false) 81 82FunctionPass *llvm::createAlignmentFromAssumptionsPass() { 83 return new AlignmentFromAssumptions(); 84} 85 86// Given an expression for the (constant) alignment, AlignSCEV, and an 87// expression for the displacement between a pointer and the aligned address, 88// DiffSCEV, compute the alignment of the displaced pointer if it can be reduced 89// to a constant. Using SCEV to compute alignment handles the case where 90// DiffSCEV is a recurrence with constant start such that the aligned offset 91// is constant. e.g. {16,+,32} % 32 -> 16. 92static unsigned getNewAlignmentDiff(const SCEV *DiffSCEV, 93 const SCEV *AlignSCEV, 94 ScalarEvolution *SE) { 95 // DiffUnits = Diff % int64_t(Alignment) 96 const SCEV *DiffAlignDiv = SE->getUDivExpr(DiffSCEV, AlignSCEV); 97 const SCEV *DiffAlign = SE->getMulExpr(DiffAlignDiv, AlignSCEV); 98 const SCEV *DiffUnitsSCEV = SE->getMinusSCEV(DiffAlign, DiffSCEV); 99 100 LLVM_DEBUG(dbgs() << "\talignment relative to " << *AlignSCEV << " is " 101 << *DiffUnitsSCEV << " (diff: " << *DiffSCEV << ")\n"); 102 103 if (const SCEVConstant *ConstDUSCEV = 104 dyn_cast<SCEVConstant>(DiffUnitsSCEV)) { 105 int64_t DiffUnits = ConstDUSCEV->getValue()->getSExtValue(); 106 107 // If the displacement is an exact multiple of the alignment, then the 108 // displaced pointer has the same alignment as the aligned pointer, so 109 // return the alignment value. 110 if (!DiffUnits) 111 return (unsigned) 112 cast<SCEVConstant>(AlignSCEV)->getValue()->getSExtValue(); 113 114 // If the displacement is not an exact multiple, but the remainder is a 115 // constant, then return this remainder (but only if it is a power of 2). 116 uint64_t DiffUnitsAbs = std::abs(DiffUnits); 117 if (isPowerOf2_64(DiffUnitsAbs)) 118 return (unsigned) DiffUnitsAbs; 119 } 120 121 return 0; 122} 123 124// There is an address given by an offset OffSCEV from AASCEV which has an 125// alignment AlignSCEV. Use that information, if possible, to compute a new 126// alignment for Ptr. 127static unsigned getNewAlignment(const SCEV *AASCEV, const SCEV *AlignSCEV, 128 const SCEV *OffSCEV, Value *Ptr, 129 ScalarEvolution *SE) { 130 const SCEV *PtrSCEV = SE->getSCEV(Ptr); 131 const SCEV *DiffSCEV = SE->getMinusSCEV(PtrSCEV, AASCEV); 132 133 // On 32-bit platforms, DiffSCEV might now have type i32 -- we've always 134 // sign-extended OffSCEV to i64, so make sure they agree again. 135 DiffSCEV = SE->getNoopOrSignExtend(DiffSCEV, OffSCEV->getType()); 136 137 // What we really want to know is the overall offset to the aligned 138 // address. This address is displaced by the provided offset. 139 DiffSCEV = SE->getMinusSCEV(DiffSCEV, OffSCEV); 140 141 LLVM_DEBUG(dbgs() << "AFI: alignment of " << *Ptr << " relative to " 142 << *AlignSCEV << " and offset " << *OffSCEV 143 << " using diff " << *DiffSCEV << "\n"); 144 145 unsigned NewAlignment = getNewAlignmentDiff(DiffSCEV, AlignSCEV, SE); 146 LLVM_DEBUG(dbgs() << "\tnew alignment: " << NewAlignment << "\n"); 147 148 if (NewAlignment) { 149 return NewAlignment; 150 } else if (const SCEVAddRecExpr *DiffARSCEV = 151 dyn_cast<SCEVAddRecExpr>(DiffSCEV)) { 152 // The relative offset to the alignment assumption did not yield a constant, 153 // but we should try harder: if we assume that a is 32-byte aligned, then in 154 // for (i = 0; i < 1024; i += 4) r += a[i]; not all of the loads from a are 155 // 32-byte aligned, but instead alternate between 32 and 16-byte alignment. 156 // As a result, the new alignment will not be a constant, but can still 157 // be improved over the default (of 4) to 16. 158 159 const SCEV *DiffStartSCEV = DiffARSCEV->getStart(); 160 const SCEV *DiffIncSCEV = DiffARSCEV->getStepRecurrence(*SE); 161 162 LLVM_DEBUG(dbgs() << "\ttrying start/inc alignment using start " 163 << *DiffStartSCEV << " and inc " << *DiffIncSCEV << "\n"); 164 165 // Now compute the new alignment using the displacement to the value in the 166 // first iteration, and also the alignment using the per-iteration delta. 167 // If these are the same, then use that answer. Otherwise, use the smaller 168 // one, but only if it divides the larger one. 169 NewAlignment = getNewAlignmentDiff(DiffStartSCEV, AlignSCEV, SE); 170 unsigned NewIncAlignment = getNewAlignmentDiff(DiffIncSCEV, AlignSCEV, SE); 171 172 LLVM_DEBUG(dbgs() << "\tnew start alignment: " << NewAlignment << "\n"); 173 LLVM_DEBUG(dbgs() << "\tnew inc alignment: " << NewIncAlignment << "\n"); 174 175 if (!NewAlignment || !NewIncAlignment) { 176 return 0; 177 } else if (NewAlignment > NewIncAlignment) { 178 if (NewAlignment % NewIncAlignment == 0) { 179 LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: " << NewIncAlignment 180 << "\n"); 181 return NewIncAlignment; 182 } 183 } else if (NewIncAlignment > NewAlignment) { 184 if (NewIncAlignment % NewAlignment == 0) { 185 LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: " << NewAlignment 186 << "\n"); 187 return NewAlignment; 188 } 189 } else if (NewIncAlignment == NewAlignment) { 190 LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: " << NewAlignment 191 << "\n"); 192 return NewAlignment; 193 } 194 } 195 196 return 0; 197} 198 199bool AlignmentFromAssumptionsPass::extractAlignmentInfo(CallInst *I, 200 Value *&AAPtr, 201 const SCEV *&AlignSCEV, 202 const SCEV *&OffSCEV) { 203 // An alignment assume must be a statement about the least-significant 204 // bits of the pointer being zero, possibly with some offset. 205 ICmpInst *ICI = dyn_cast<ICmpInst>(I->getArgOperand(0)); 206 if (!ICI) 207 return false; 208 209 // This must be an expression of the form: x & m == 0. 210 if (ICI->getPredicate() != ICmpInst::ICMP_EQ) 211 return false; 212 213 // Swap things around so that the RHS is 0. 214 Value *CmpLHS = ICI->getOperand(0); 215 Value *CmpRHS = ICI->getOperand(1); 216 const SCEV *CmpLHSSCEV = SE->getSCEV(CmpLHS); 217 const SCEV *CmpRHSSCEV = SE->getSCEV(CmpRHS); 218 if (CmpLHSSCEV->isZero()) 219 std::swap(CmpLHS, CmpRHS); 220 else if (!CmpRHSSCEV->isZero()) 221 return false; 222 223 BinaryOperator *CmpBO = dyn_cast<BinaryOperator>(CmpLHS); 224 if (!CmpBO || CmpBO->getOpcode() != Instruction::And) 225 return false; 226 227 // Swap things around so that the right operand of the and is a constant 228 // (the mask); we cannot deal with variable masks. 229 Value *AndLHS = CmpBO->getOperand(0); 230 Value *AndRHS = CmpBO->getOperand(1); 231 const SCEV *AndLHSSCEV = SE->getSCEV(AndLHS); 232 const SCEV *AndRHSSCEV = SE->getSCEV(AndRHS); 233 if (isa<SCEVConstant>(AndLHSSCEV)) { 234 std::swap(AndLHS, AndRHS); 235 std::swap(AndLHSSCEV, AndRHSSCEV); 236 } 237 238 const SCEVConstant *MaskSCEV = dyn_cast<SCEVConstant>(AndRHSSCEV); 239 if (!MaskSCEV) 240 return false; 241 242 // The mask must have some trailing ones (otherwise the condition is 243 // trivial and tells us nothing about the alignment of the left operand). 244 unsigned TrailingOnes = MaskSCEV->getAPInt().countTrailingOnes(); 245 if (!TrailingOnes) 246 return false; 247 248 // Cap the alignment at the maximum with which LLVM can deal (and make sure 249 // we don't overflow the shift). 250 uint64_t Alignment; 251 TrailingOnes = std::min(TrailingOnes, 252 unsigned(sizeof(unsigned) * CHAR_BIT - 1)); 253 Alignment = std::min(1u << TrailingOnes, +Value::MaximumAlignment); 254 255 Type *Int64Ty = Type::getInt64Ty(I->getParent()->getParent()->getContext()); 256 AlignSCEV = SE->getConstant(Int64Ty, Alignment); 257 258 // The LHS might be a ptrtoint instruction, or it might be the pointer 259 // with an offset. 260 AAPtr = nullptr; 261 OffSCEV = nullptr; 262 if (PtrToIntInst *PToI = dyn_cast<PtrToIntInst>(AndLHS)) { 263 AAPtr = PToI->getPointerOperand(); 264 OffSCEV = SE->getZero(Int64Ty); 265 } else if (const SCEVAddExpr* AndLHSAddSCEV = 266 dyn_cast<SCEVAddExpr>(AndLHSSCEV)) { 267 // Try to find the ptrtoint; subtract it and the rest is the offset. 268 for (SCEVAddExpr::op_iterator J = AndLHSAddSCEV->op_begin(), 269 JE = AndLHSAddSCEV->op_end(); J != JE; ++J) 270 if (const SCEVUnknown *OpUnk = dyn_cast<SCEVUnknown>(*J)) 271 if (PtrToIntInst *PToI = dyn_cast<PtrToIntInst>(OpUnk->getValue())) { 272 AAPtr = PToI->getPointerOperand(); 273 OffSCEV = SE->getMinusSCEV(AndLHSAddSCEV, *J); 274 break; 275 } 276 } 277 278 if (!AAPtr) 279 return false; 280 281 // Sign extend the offset to 64 bits (so that it is like all of the other 282 // expressions). 283 unsigned OffSCEVBits = OffSCEV->getType()->getPrimitiveSizeInBits(); 284 if (OffSCEVBits < 64) 285 OffSCEV = SE->getSignExtendExpr(OffSCEV, Int64Ty); 286 else if (OffSCEVBits > 64) 287 return false; 288 289 AAPtr = AAPtr->stripPointerCasts(); 290 return true; 291} 292 293bool AlignmentFromAssumptionsPass::processAssumption(CallInst *ACall) { 294 Value *AAPtr; 295 const SCEV *AlignSCEV, *OffSCEV; 296 if (!extractAlignmentInfo(ACall, AAPtr, AlignSCEV, OffSCEV)) 297 return false; 298 299 // Skip ConstantPointerNull and UndefValue. Assumptions on these shouldn't 300 // affect other users. 301 if (isa<ConstantData>(AAPtr)) 302 return false; 303 304 const SCEV *AASCEV = SE->getSCEV(AAPtr); 305 306 // Apply the assumption to all other users of the specified pointer. 307 SmallPtrSet<Instruction *, 32> Visited; 308 SmallVector<Instruction*, 16> WorkList; 309 for (User *J : AAPtr->users()) { 310 if (J == ACall) 311 continue; 312 313 if (Instruction *K = dyn_cast<Instruction>(J)) 314 if (isValidAssumeForContext(ACall, K, DT)) 315 WorkList.push_back(K); 316 } 317 318 while (!WorkList.empty()) { 319 Instruction *J = WorkList.pop_back_val(); 320 321 if (LoadInst *LI = dyn_cast<LoadInst>(J)) { 322 unsigned NewAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV, 323 LI->getPointerOperand(), SE); 324 325 if (NewAlignment > LI->getAlignment()) { 326 LI->setAlignment(NewAlignment); 327 ++NumLoadAlignChanged; 328 } 329 } else if (StoreInst *SI = dyn_cast<StoreInst>(J)) { 330 unsigned NewAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV, 331 SI->getPointerOperand(), SE); 332 333 if (NewAlignment > SI->getAlignment()) { 334 SI->setAlignment(NewAlignment); 335 ++NumStoreAlignChanged; 336 } 337 } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(J)) { 338 unsigned NewDestAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV, 339 MI->getDest(), SE); 340 341 LLVM_DEBUG(dbgs() << "\tmem inst: " << NewDestAlignment << "\n";); 342 if (NewDestAlignment > MI->getDestAlignment()) { 343 MI->setDestAlignment(NewDestAlignment); 344 ++NumMemIntAlignChanged; 345 } 346 347 // For memory transfers, there is also a source alignment that 348 // can be set. 349 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) { 350 unsigned NewSrcAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV, 351 MTI->getSource(), SE); 352 353 LLVM_DEBUG(dbgs() << "\tmem trans: " << NewSrcAlignment << "\n";); 354 355 if (NewSrcAlignment > MTI->getSourceAlignment()) { 356 MTI->setSourceAlignment(NewSrcAlignment); 357 ++NumMemIntAlignChanged; 358 } 359 } 360 } 361 362 // Now that we've updated that use of the pointer, look for other uses of 363 // the pointer to update. 364 Visited.insert(J); 365 for (User *UJ : J->users()) { 366 Instruction *K = cast<Instruction>(UJ); 367 if (!Visited.count(K) && isValidAssumeForContext(ACall, K, DT)) 368 WorkList.push_back(K); 369 } 370 } 371 372 return true; 373} 374 375bool AlignmentFromAssumptions::runOnFunction(Function &F) { 376 if (skipFunction(F)) 377 return false; 378 379 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 380 ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 381 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 382 383 return Impl.runImpl(F, AC, SE, DT); 384} 385 386bool AlignmentFromAssumptionsPass::runImpl(Function &F, AssumptionCache &AC, 387 ScalarEvolution *SE_, 388 DominatorTree *DT_) { 389 SE = SE_; 390 DT = DT_; 391 392 bool Changed = false; 393 for (auto &AssumeVH : AC.assumptions()) 394 if (AssumeVH) 395 Changed |= processAssumption(cast<CallInst>(AssumeVH)); 396 397 return Changed; 398} 399 400PreservedAnalyses 401AlignmentFromAssumptionsPass::run(Function &F, FunctionAnalysisManager &AM) { 402 403 AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F); 404 ScalarEvolution &SE = AM.getResult<ScalarEvolutionAnalysis>(F); 405 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F); 406 if (!runImpl(F, AC, &SE, &DT)) 407 return PreservedAnalyses::all(); 408 409 PreservedAnalyses PA; 410 PA.preserveSet<CFGAnalyses>(); 411 PA.preserve<AAManager>(); 412 PA.preserve<ScalarEvolutionAnalysis>(); 413 PA.preserve<GlobalsAA>(); 414 return PA; 415} 416