contrib/llvm/lib/Transforms/Scalar/AlignmentFromAssumptions.cpp

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