1 //===----------------------- AlignmentFromAssumptions.cpp -----------------===// 2 // Set Load/Store Alignments From Assumptions 3 // 4 // The LLVM Compiler Infrastructure 5 // 6 // This file is distributed under the University of Illinois Open Source 7 // License. See LICENSE.TXT for details. 8 // 9 //===----------------------------------------------------------------------===// 10 // 11 // This file implements a ScalarEvolution-based transformation to set 12 // the alignments of load, stores and memory intrinsics based on the truth 13 // expressions of assume intrinsics. The primary motivation is to handle 14 // complex alignment assumptions that apply to vector loads and stores that 15 // appear after vectorization and unrolling. 16 // 17 //===----------------------------------------------------------------------===// 18 19 #define AA_NAME "alignment-from-assumptions" 20 #define DEBUG_TYPE AA_NAME 21 #include "llvm/Transforms/Scalar.h" 22 #include "llvm/ADT/SmallPtrSet.h" 23 #include "llvm/ADT/Statistic.h" 24 #include "llvm/Analysis/AssumptionTracker.h" 25 #include "llvm/Analysis/LoopInfo.h" 26 #include "llvm/Analysis/ValueTracking.h" 27 #include "llvm/Analysis/ScalarEvolution.h" 28 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 29 #include "llvm/IR/Constant.h" 30 #include "llvm/IR/Dominators.h" 31 #include "llvm/IR/Instruction.h" 32 #include "llvm/IR/IntrinsicInst.h" 33 #include "llvm/IR/Intrinsics.h" 34 #include "llvm/IR/DataLayout.h" 35 #include "llvm/Support/Debug.h" 36 #include "llvm/Support/raw_ostream.h" 37 using namespace llvm; 38 39 STATISTIC(NumLoadAlignChanged, 40 "Number of loads changed by alignment assumptions"); 41 STATISTIC(NumStoreAlignChanged, 42 "Number of stores changed by alignment assumptions"); 43 STATISTIC(NumMemIntAlignChanged, 44 "Number of memory intrinsics changed by alignment assumptions"); 45 46 namespace { 47 struct 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); 54 55 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 56 AU.addRequired<AssumptionTracker>(); 57 AU.addRequired<ScalarEvolution>(); 58 AU.addRequired<DominatorTreeWrapperPass>(); 59 60 AU.setPreservesCFG(); 61 AU.addPreserved<LoopInfo>(); 62 AU.addPreserved<DominatorTreeWrapperPass>(); 63 AU.addPreserved<ScalarEvolution>(); 64 } 65 66 // For memory transfers, we need a common alignment for both the source and 67 // destination. If we have a new alignment for only one operand of a transfer 68 // instruction, save it in these maps. If we reach the other operand through 69 // another assumption later, then we may change the alignment at that point. 70 DenseMap<MemTransferInst *, unsigned> NewDestAlignments, NewSrcAlignments; 71 72 AssumptionTracker *AT; 73 ScalarEvolution *SE; 74 DominatorTree *DT; 75 const DataLayout *DL; 76 77 bool extractAlignmentInfo(CallInst *I, Value *&AAPtr, const SCEV *&AlignSCEV, 78 const SCEV *&OffSCEV); 79 bool processAssumption(CallInst *I); 80 }; 81 } 82 83 char AlignmentFromAssumptions::ID = 0; 84 static const char aip_name[] = "Alignment from assumptions"; 85 INITIALIZE_PASS_BEGIN(AlignmentFromAssumptions, AA_NAME, 86 aip_name, false, false) 87 INITIALIZE_PASS_DEPENDENCY(AssumptionTracker) 88 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 89 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 90 INITIALIZE_PASS_END(AlignmentFromAssumptions, AA_NAME, 91 aip_name, false, false) 92 93 FunctionPass *llvm::createAlignmentFromAssumptionsPass() { 94 return new AlignmentFromAssumptions(); 95 } 96 97 // Given an expression for the (constant) alignment, AlignSCEV, and an 98 // expression for the displacement between a pointer and the aligned address, 99 // DiffSCEV, compute the alignment of the displaced pointer if it can be reduced 100 // to a constant. Using SCEV to compute alignment handles the case where 101 // DiffSCEV is a recurrence with constant start such that the aligned offset 102 // is constant. e.g. {16,+,32} % 32 -> 16. 103 static unsigned getNewAlignmentDiff(const SCEV *DiffSCEV, 104 const SCEV *AlignSCEV, 105 ScalarEvolution *SE) { 106 // DiffUnits = Diff % int64_t(Alignment) 107 const SCEV *DiffAlignDiv = SE->getUDivExpr(DiffSCEV, AlignSCEV); 108 const SCEV *DiffAlign = SE->getMulExpr(DiffAlignDiv, AlignSCEV); 109 const SCEV *DiffUnitsSCEV = SE->getMinusSCEV(DiffAlign, DiffSCEV); 110 111 DEBUG(dbgs() << "\talignment relative to " << *AlignSCEV << " is " << 112 *DiffUnitsSCEV << " (diff: " << *DiffSCEV << ")\n"); 113 114 if (const SCEVConstant *ConstDUSCEV = 115 dyn_cast<SCEVConstant>(DiffUnitsSCEV)) { 116 int64_t DiffUnits = ConstDUSCEV->getValue()->getSExtValue(); 117 118 // If the displacement is an exact multiple of the alignment, then the 119 // displaced pointer has the same alignment as the aligned pointer, so 120 // return the alignment value. 121 if (!DiffUnits) 122 return (unsigned) 123 cast<SCEVConstant>(AlignSCEV)->getValue()->getSExtValue(); 124 125 // If the displacement is not an exact multiple, but the remainder is a 126 // constant, then return this remainder (but only if it is a power of 2). 127 uint64_t DiffUnitsAbs = abs64(DiffUnits); 128 if (isPowerOf2_64(DiffUnitsAbs)) 129 return (unsigned) DiffUnitsAbs; 130 } 131 132 return 0; 133 } 134 135 // There is an address given by an offset OffSCEV from AASCEV which has an 136 // alignment AlignSCEV. Use that information, if possible, to compute a new 137 // alignment for Ptr. 138 static unsigned getNewAlignment(const SCEV *AASCEV, const SCEV *AlignSCEV, 139 const SCEV *OffSCEV, Value *Ptr, 140 ScalarEvolution *SE) { 141 const SCEV *PtrSCEV = SE->getSCEV(Ptr); 142 const SCEV *DiffSCEV = SE->getMinusSCEV(PtrSCEV, AASCEV); 143 144 // What we really want to know is the overall offset to the aligned 145 // address. This address is displaced by the provided offset. 146 DiffSCEV = SE->getMinusSCEV(DiffSCEV, OffSCEV); 147 148 DEBUG(dbgs() << "AFI: alignment of " << *Ptr << " relative to " << 149 *AlignSCEV << " and offset " << *OffSCEV << 150 " using diff " << *DiffSCEV << "\n"); 151 152 unsigned NewAlignment = getNewAlignmentDiff(DiffSCEV, AlignSCEV, SE); 153 DEBUG(dbgs() << "\tnew alignment: " << NewAlignment << "\n"); 154 155 if (NewAlignment) { 156 return NewAlignment; 157 } else if (const SCEVAddRecExpr *DiffARSCEV = 158 dyn_cast<SCEVAddRecExpr>(DiffSCEV)) { 159 // The relative offset to the alignment assumption did not yield a constant, 160 // but we should try harder: if we assume that a is 32-byte aligned, then in 161 // for (i = 0; i < 1024; i += 4) r += a[i]; not all of the loads from a are 162 // 32-byte aligned, but instead alternate between 32 and 16-byte alignment. 163 // As a result, the new alignment will not be a constant, but can still 164 // be improved over the default (of 4) to 16. 165 166 const SCEV *DiffStartSCEV = DiffARSCEV->getStart(); 167 const SCEV *DiffIncSCEV = DiffARSCEV->getStepRecurrence(*SE); 168 169 DEBUG(dbgs() << "\ttrying start/inc alignment using start " << 170 *DiffStartSCEV << " and inc " << *DiffIncSCEV << "\n"); 171 172 // Now compute the new alignment using the displacement to the value in the 173 // first iteration, and also the alignment using the per-iteration delta. 174 // If these are the same, then use that answer. Otherwise, use the smaller 175 // one, but only if it divides the larger one. 176 NewAlignment = getNewAlignmentDiff(DiffStartSCEV, AlignSCEV, SE); 177 unsigned NewIncAlignment = getNewAlignmentDiff(DiffIncSCEV, AlignSCEV, SE); 178 179 DEBUG(dbgs() << "\tnew start alignment: " << NewAlignment << "\n"); 180 DEBUG(dbgs() << "\tnew inc alignment: " << NewIncAlignment << "\n"); 181 182 if (NewAlignment > NewIncAlignment) { 183 if (NewAlignment % NewIncAlignment == 0) { 184 DEBUG(dbgs() << "\tnew start/inc alignment: " << 185 NewIncAlignment << "\n"); 186 return NewIncAlignment; 187 } 188 } else if (NewIncAlignment > NewAlignment) { 189 if (NewIncAlignment % NewAlignment == 0) { 190 DEBUG(dbgs() << "\tnew start/inc alignment: " << 191 NewAlignment << "\n"); 192 return NewAlignment; 193 } 194 } else if (NewIncAlignment == NewAlignment && NewIncAlignment) { 195 DEBUG(dbgs() << "\tnew start/inc alignment: " << 196 NewAlignment << "\n"); 197 return NewAlignment; 198 } 199 } 200 201 return 0; 202 } 203 204 bool AlignmentFromAssumptions::extractAlignmentInfo(CallInst *I, 205 Value *&AAPtr, const SCEV *&AlignSCEV, 206 const SCEV *&OffSCEV) { 207 // An alignment assume must be a statement about the least-significant 208 // bits of the pointer being zero, possibly with some offset. 209 ICmpInst *ICI = dyn_cast<ICmpInst>(I->getArgOperand(0)); 210 if (!ICI) 211 return false; 212 213 // This must be an expression of the form: x & m == 0. 214 if (ICI->getPredicate() != ICmpInst::ICMP_EQ) 215 return false; 216 217 // Swap things around so that the RHS is 0. 218 Value *CmpLHS = ICI->getOperand(0); 219 Value *CmpRHS = ICI->getOperand(1); 220 const SCEV *CmpLHSSCEV = SE->getSCEV(CmpLHS); 221 const SCEV *CmpRHSSCEV = SE->getSCEV(CmpRHS); 222 if (CmpLHSSCEV->isZero()) 223 std::swap(CmpLHS, CmpRHS); 224 else if (!CmpRHSSCEV->isZero()) 225 return false; 226 227 BinaryOperator *CmpBO = dyn_cast<BinaryOperator>(CmpLHS); 228 if (!CmpBO || CmpBO->getOpcode() != Instruction::And) 229 return false; 230 231 // Swap things around so that the right operand of the and is a constant 232 // (the mask); we cannot deal with variable masks. 233 Value *AndLHS = CmpBO->getOperand(0); 234 Value *AndRHS = CmpBO->getOperand(1); 235 const SCEV *AndLHSSCEV = SE->getSCEV(AndLHS); 236 const SCEV *AndRHSSCEV = SE->getSCEV(AndRHS); 237 if (isa<SCEVConstant>(AndLHSSCEV)) { 238 std::swap(AndLHS, AndRHS); 239 std::swap(AndLHSSCEV, AndRHSSCEV); 240 } 241 242 const SCEVConstant *MaskSCEV = dyn_cast<SCEVConstant>(AndRHSSCEV); 243 if (!MaskSCEV) 244 return false; 245 246 // The mask must have some trailing ones (otherwise the condition is 247 // trivial and tells us nothing about the alignment of the left operand). 248 unsigned TrailingOnes = 249 MaskSCEV->getValue()->getValue().countTrailingOnes(); 250 if (!TrailingOnes) 251 return false; 252 253 // Cap the alignment at the maximum with which LLVM can deal (and make sure 254 // we don't overflow the shift). 255 uint64_t Alignment; 256 TrailingOnes = std::min(TrailingOnes, 257 unsigned(sizeof(unsigned) * CHAR_BIT - 1)); 258 Alignment = std::min(1u << TrailingOnes, +Value::MaximumAlignment); 259 260 Type *Int64Ty = Type::getInt64Ty(I->getParent()->getParent()->getContext()); 261 AlignSCEV = SE->getConstant(Int64Ty, Alignment); 262 263 // The LHS might be a ptrtoint instruction, or it might be the pointer 264 // with an offset. 265 AAPtr = nullptr; 266 OffSCEV = nullptr; 267 if (PtrToIntInst *PToI = dyn_cast<PtrToIntInst>(AndLHS)) { 268 AAPtr = PToI->getPointerOperand(); 269 OffSCEV = SE->getConstant(Int64Ty, 0); 270 } else if (const SCEVAddExpr* AndLHSAddSCEV = 271 dyn_cast<SCEVAddExpr>(AndLHSSCEV)) { 272 // Try to find the ptrtoint; subtract it and the rest is the offset. 273 for (SCEVAddExpr::op_iterator J = AndLHSAddSCEV->op_begin(), 274 JE = AndLHSAddSCEV->op_end(); J != JE; ++J) 275 if (const SCEVUnknown *OpUnk = dyn_cast<SCEVUnknown>(*J)) 276 if (PtrToIntInst *PToI = dyn_cast<PtrToIntInst>(OpUnk->getValue())) { 277 AAPtr = PToI->getPointerOperand(); 278 OffSCEV = SE->getMinusSCEV(AndLHSAddSCEV, *J); 279 break; 280 } 281 } 282 283 if (!AAPtr) 284 return false; 285 286 // Sign extend the offset to 64 bits (so that it is like all of the other 287 // expressions). 288 unsigned OffSCEVBits = OffSCEV->getType()->getPrimitiveSizeInBits(); 289 if (OffSCEVBits < 64) 290 OffSCEV = SE->getSignExtendExpr(OffSCEV, Int64Ty); 291 else if (OffSCEVBits > 64) 292 return false; 293 294 AAPtr = AAPtr->stripPointerCasts(); 295 return true; 296 } 297 298 bool AlignmentFromAssumptions::processAssumption(CallInst *ACall) { 299 Value *AAPtr; 300 const SCEV *AlignSCEV, *OffSCEV; 301 if (!extractAlignmentInfo(ACall, AAPtr, AlignSCEV, OffSCEV)) 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, DL, 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 // For memory transfers, we need a common alignment for both the 342 // source and destination. If we have a new alignment for this 343 // instruction, but only for one operand, save it. If we reach the 344 // other operand through another assumption later, then we may 345 // change the alignment at that point. 346 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) { 347 unsigned NewSrcAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV, 348 MTI->getSource(), SE); 349 350 DenseMap<MemTransferInst *, unsigned>::iterator DI = 351 NewDestAlignments.find(MTI); 352 unsigned AltDestAlignment = (DI == NewDestAlignments.end()) ? 353 0 : DI->second; 354 355 DenseMap<MemTransferInst *, unsigned>::iterator SI = 356 NewSrcAlignments.find(MTI); 357 unsigned AltSrcAlignment = (SI == NewSrcAlignments.end()) ? 358 0 : SI->second; 359 360 DEBUG(dbgs() << "\tmem trans: " << NewDestAlignment << " " << 361 AltDestAlignment << " " << NewSrcAlignment << 362 " " << AltSrcAlignment << "\n"); 363 364 // Of these four alignments, pick the largest possible... 365 unsigned NewAlignment = 0; 366 if (NewDestAlignment <= std::max(NewSrcAlignment, AltSrcAlignment)) 367 NewAlignment = std::max(NewAlignment, NewDestAlignment); 368 if (AltDestAlignment <= std::max(NewSrcAlignment, AltSrcAlignment)) 369 NewAlignment = std::max(NewAlignment, AltDestAlignment); 370 if (NewSrcAlignment <= std::max(NewDestAlignment, AltDestAlignment)) 371 NewAlignment = std::max(NewAlignment, NewSrcAlignment); 372 if (AltSrcAlignment <= std::max(NewDestAlignment, AltDestAlignment)) 373 NewAlignment = std::max(NewAlignment, AltSrcAlignment); 374 375 if (NewAlignment > MI->getAlignment()) { 376 MI->setAlignment(ConstantInt::get(Type::getInt32Ty( 377 MI->getParent()->getContext()), NewAlignment)); 378 ++NumMemIntAlignChanged; 379 } 380 381 NewDestAlignments.insert(std::make_pair(MTI, NewDestAlignment)); 382 NewSrcAlignments.insert(std::make_pair(MTI, NewSrcAlignment)); 383 } else if (NewDestAlignment > MI->getAlignment()) { 384 assert((!isa<MemIntrinsic>(MI) || isa<MemSetInst>(MI)) && 385 "Unknown memory intrinsic"); 386 387 MI->setAlignment(ConstantInt::get(Type::getInt32Ty( 388 MI->getParent()->getContext()), NewDestAlignment)); 389 ++NumMemIntAlignChanged; 390 } 391 } 392 393 // Now that we've updated that use of the pointer, look for other uses of 394 // the pointer to update. 395 Visited.insert(J); 396 for (User *UJ : J->users()) { 397 Instruction *K = cast<Instruction>(UJ); 398 if (!Visited.count(K) && isValidAssumeForContext(ACall, K, DL, DT)) 399 WorkList.push_back(K); 400 } 401 } 402 403 return true; 404 } 405 406 bool AlignmentFromAssumptions::runOnFunction(Function &F) { 407 bool Changed = false; 408 AT = &getAnalysis<AssumptionTracker>(); 409 SE = &getAnalysis<ScalarEvolution>(); 410 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 411 DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); 412 DL = DLP ? &DLP->getDataLayout() : nullptr; 413 414 NewDestAlignments.clear(); 415 NewSrcAlignments.clear(); 416 417 for (auto &I : AT->assumptions(&F)) 418 Changed |= processAssumption(I); 419 420 return Changed; 421 } 422 423