Prototype BasicAA improvements for discussion on llvm-dev

[lebedev.ri]

lib/Analysis/BasicAliasAnalysis.cpp

1016

Constants should always have already been canonicalized to the RHS

[aqjune]

I think we need to check whether shl/mul has nsw flag.

For example, 'shl i16 1024, 10' and 'shl i16 1024, 11' are both 0, so we need to check whether they don't overflow.

[markus]

In D55107#1314238, @aqjune wrote:

I think we need to check whether shl/mul has nsw flag.

For example, 'shl i16 1024, 10' and 'shl i16 1024, 11' are both 0, so we need to check whether they don't overflow.

Right. For my input there is no nsw flag but I guess one could equally well require more assumes on %X e.g. that it is in interval [a,b] and for this range the shl does not overflow.

edit: Or maybe if those assumes were already present some other pass would already have set a nsw flag on on the shl.

[markus]

Did some more experiments, trying to clean up the code and make it more generic.
Instead of only determining if X != 0 (which is clearly not sufficient) try to produce a value range for the variable and use that.

[asbirlea]

Could you add some tests to this?

include/llvm/Analysis/BasicAliasAnalysis.h

 struct AAMDNodes;
 class APInt;
 class AssumptionCache;
 class BasicBlock;
 class DataLayout;
 class DominatorTree;
 class Function;
 class GEPOperator;
+class LazyValueInfo;
 class LoopInfo;
 class PHINode;
 class SelectInst;
 class TargetLibraryInfo;
 class PhiValues;
 class Value;
 
 /// This is the AA result object for the basic, local, and stateless alias
 /// analysis. It implements the AA query interface in an entirely stateless
 /// manner. As one consequence, it is never invalidated due to IR changes.
 /// While it does retain some storage, that is used as an optimization and not
 /// to preserve information from query to query. However it does retain handles
 /// to various other analyses and must be recomputed when those analyses are.
 class BasicAAResult : public AAResultBase<BasicAAResult> {
   friend AAResultBase<BasicAAResult>;
 
   const DataLayout &DL;
   const Function &F;
   const TargetLibraryInfo &TLI;
   AssumptionCache &AC;
   DominatorTree *DT;
   LoopInfo *LI;
   PhiValues *PV;
+  LazyValueInfo *LVI;
 
 public:
   BasicAAResult(const DataLayout &DL, const Function &F,
                 const TargetLibraryInfo &TLI, AssumptionCache &AC,
                 DominatorTree *DT = nullptr, LoopInfo *LI = nullptr,
-                PhiValues *PV = nullptr)
-      : AAResultBase(), DL(DL), F(F), TLI(TLI), AC(AC), DT(DT), LI(LI), PV(PV)
+                PhiValues *PV = nullptr, LazyValueInfo *LVI = nullptr)
+      : AAResultBase(), DL(DL), F(F), TLI(TLI), AC(AC), DT(DT), LI(LI), PV(PV), LVI(LVI)
         {}
 
   BasicAAResult(const BasicAAResult &Arg)
       : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC),
         DT(Arg.DT),  LI(Arg.LI), PV(Arg.PV) {}
   BasicAAResult(BasicAAResult &&Arg)
       : AAResultBase(std::move(Arg)), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI),
         AC(Arg.AC), DT(Arg.DT), LI(Arg.LI), PV(Arg.PV) {}

include/llvm/Analysis/LazyValueInfo.h

public:
   /// constant at the end of the specified block.  Return null if not.
   Constant *getConstant(Value *V, BasicBlock *BB, Instruction *CxtI = nullptr);
 
   /// Return the ConstantRange constraint that is known to hold for the
   /// specified value at the end of the specified block. This may only be called
   /// on integer-typed Values.
   ConstantRange getConstantRange(Value *V, BasicBlock *BB, Instruction *CxtI = nullptr);
 
+  ConstantRange getConstantRange(const Value *V, const BasicBlock *BB,
+                                 const Instruction *CxtI = nullptr);
+
   /// Determine whether the specified value is known to be a
   /// constant on the specified edge.  Return null if not.
   Constant *getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
                               Instruction *CxtI = nullptr);
 
   /// Return the ConstantRage constraint that is known to hold for the
   /// specified value on the specified edge. This may be only be called
   /// on integer-typed Values.
class LazyValueInfoWrapperPass : public FunctionPass {
   LazyValueInfoWrapperPass(const LazyValueInfoWrapperPass&) = delete;
   void operator=(const LazyValueInfoWrapperPass&) = delete;
 public:
   static char ID;
   LazyValueInfoWrapperPass() : FunctionPass(ID) {
     initializeLazyValueInfoWrapperPassPass(*PassRegistry::getPassRegistry());
   }
   ~LazyValueInfoWrapperPass() override {
+#if 0
+    // TODO:FIXME: There appears to be a problem with pass scheduling where LVI
+    // is called (via AA) after it has been freed. See --debug-pass=Executions
+    // for details with gdb breakpoints in releaseMemory and getImpl.
+
     assert(!Info.PImpl && "releaseMemory not called");
+#endif
   }
 
   LazyValueInfo &getLVI();
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
   void releaseMemory() override;
   bool runOnFunction(Function &F) override;
 private:
   LazyValueInfo Info;
 };
 
 }  // end namespace llvm
 
 #endif
 

lib/Analysis/AssumptionCache.cpp

if (Pred == ICmpInst::ICMP_EQ) {
         }
       };
 
       AddAffectedFromEq(A);
       AddAffectedFromEq(B);
     }
   }
 
+  // TODO:FIXME: The expression (inside) __builtin_assume(x > 0 && x < 16)
+  // would get transformed into:
+  // %x.off = add i16 %x, -1
+  // %0 = icmp ult i16 %x.off, 15
+  // The following pattern is needed to add %x to the AC.
+  //
+  // Unclear what this means for the 'in-sync with ValueTracking' comment in
+  // the beginning of this function. As an observation LazyValueInfo has code
+  // for this exact pattern but without the AddAffected here it will never find
+  // those in the AC.
+  if (match(Cond, m_ICmp(Pred, m_Add(m_Value(A), m_Value()), m_Value()))) {
+    AddAffected(A);
+  }
+
   for (auto &AV : Affected) {
     auto &AVV = getOrInsertAffectedValues(AV);
     if (std::find(AVV.begin(), AVV.end(), CI) == AVV.end())
       AVV.push_back(CI);
   }
 }
 
 void AssumptionCache::AffectedValueCallbackVH::deleted() {

lib/Analysis/BasicAliasAnalysis.cpp

 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Analysis/PhiValues.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
+#include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/GlobalVariable.h"

 }
 
 /// Provide ad-hoc rules to disambiguate accesses through two GEP operators,
 /// both having the exact same pointer operand.
 static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
                                             LocationSize MaybeV1Size,
                                             const GEPOperator *GEP2,
                                             LocationSize MaybeV2Size,
-                                            const DataLayout &DL) {
+                                            const DataLayout &DL,
+                                            LazyValueInfo *LVI) {
   assert(GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups() ==
              GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups() &&
          GEP1->getPointerOperandType() == GEP2->getPointerOperandType() &&
          "Expected GEPs with the same pointer operand");
 
-  // Try to determine whether GEP1 and GEP2 index through arrays, into structs,
-  // such that the struct field accesses provably cannot alias.
-  // We also need at least two indices (the pointer, and the struct field).
-  if (GEP1->getNumIndices() != GEP2->getNumIndices() ||
-      GEP1->getNumIndices() < 2)
-    return MayAlias;
-
   // If we don't know the size of the accesses through both GEPs, we can't
   // determine whether the struct fields accessed can't alias.
   if (MaybeV1Size == LocationSize::unknown() ||
       MaybeV2Size == LocationSize::unknown())
     return MayAlias;
 
   const uint64_t V1Size = MaybeV1Size.getValue();
   const uint64_t V2Size = MaybeV2Size.getValue();
 
+  // The situation is:
+  //  %I1 = shl/mul i16 %X, C1
+  //  %I2 = shl/mul i16 %X, C2
+  //  %G1 = getelementptr i16, i16* %baseptr, i16 %I1
+  //  %G2 = getelementptr i16, i16* %baseptr, i16 %I2
+  // Given that we have value range information on %I1 and %I2 we can determine
+  // if there is alias by comparing the lower bounds of those ranges (since %X
+  // is used in both)
+  if (GEP1->getNumIndices() == 1 && GEP2->getNumIndices() == 1 && LVI) {
+    const BinaryOperator *I1 = dyn_cast<BinaryOperator>(GEP1->getOperand(1));
+    const BinaryOperator *I2 = dyn_cast<BinaryOperator>(GEP2->getOperand(1));
+
+    auto isSupported = [] (const BinaryOperator *I) {
+      return (I && dyn_cast<ConstantInt>(I->getOperand(1)) &&
+              (I->getOpcode() == Instruction::Mul ||
+               I->getOpcode() == Instruction::Shl));
+    };
+
+    if (isSupported(I1) && isSupported(I2) &&
+        I1->getOperand(0) == I2->getOperand(0)) {
+      ConstantRange R1 = LVI->getConstantRange(I1, I1->getParent(), I1);
+      ConstantRange R2 = LVI->getConstantRange(I2, I2->getParent(), I1);
+
+      const unsigned BitWidth = I1->getType()->getIntegerBitWidth();
+      // The idea behind SafeRange is to have a range, to compare against, that
+      // would guarantee that %X was not zero and did not cause an overflow.
+      const ConstantRange SafeRange(APInt(BitWidth, 1),
+                                    APInt(BitWidth, (1U << BitWidth) - 1));
+
+      if (SafeRange.contains(R1) && SafeRange.contains(R2)) {
+        unsigned Ty1Size = DL.getTypeStoreSize(GEP1->getSourceElementType());
+        unsigned Ty2Size = DL.getTypeStoreSize(GEP2->getSourceElementType());
+        const uint64_t R1Lower = R1.getLower().getZExtValue() * Ty1Size;
+        const uint64_t R2Lower = R2.getLower().getZExtValue() * Ty2Size;
+
+        // Since %X is the same in both we can now pick a value for it that
+        // corresponds to the lower bounds and compare those with the sizes.
+        if (R1Lower < R2Lower) {
+          if (R1Lower + V1Size <= R2Lower)
+            return NoAlias;
+        } else {
+          if (R2Lower + V2Size <= R1Lower)
+            return NoAlias;
+        }
+      }
+    }
+  }
+
+  // Try to determine whether GEP1 and GEP2 index through arrays, into structs,
+  // such that the struct field accesses provably cannot alias.
+  // We also need at least two indices (the pointer, and the struct field).
+  if (GEP1->getNumIndices() != GEP2->getNumIndices() ||
+      GEP1->getNumIndices() < 2)
+    return MayAlias;
+
   ConstantInt *C1 =
       dyn_cast<ConstantInt>(GEP1->getOperand(GEP1->getNumOperands() - 1));
   ConstantInt *C2 =
       dyn_cast<ConstantInt>(GEP2->getOperand(GEP2->getNumOperands() - 1));
 
   // If the last (struct) indices are constants and are equal, the other indices
   // might be also be dynamically equal, so the GEPs can alias.
   if (C1 && C2 && C1->getSExtValue() == C2->getSExtValue())

 /// We know that V1 is a GEP, but we don't know anything about V2.
 /// UnderlyingV1 is GetUnderlyingObject(GEP1, DL), UnderlyingV2 is the same for
 /// V2.
 AliasResult
 BasicAAResult::aliasGEP(const GEPOperator *GEP1, LocationSize V1Size,
                         const AAMDNodes &V1AAInfo, const Value *V2,
                         LocationSize V2Size, const AAMDNodes &V2AAInfo,
                         const Value *UnderlyingV1, const Value *UnderlyingV2) {
+  // If %G1 = getelementptr i16, i16* %P, i16 %I1
+  // Then try to determine if %G1 and %P alias by looking at the value range of
+  // %I1 and comparing it to the size of the %P access.
+  if (UnderlyingV1 == V2 && GEP1->getNumIndices() == 1 && LVI) {
+    const BinaryOperator *I1 = dyn_cast<BinaryOperator>(GEP1->getOperand(1));
+    if (I1 && dyn_cast<ConstantInt>(I1->getOperand(1)) &&
+        (I1->getOpcode() == Instruction::Mul ||
+         I1->getOpcode() == Instruction::Shl)) {
+      ConstantRange R1 = LVI->getConstantRange(I1, I1->getParent(), I1);
+      const unsigned BitWidth = I1->getType()->getIntegerBitWidth();
+      const ConstantRange SafeRange(APInt(BitWidth, 1),
+                                    APInt(BitWidth, (1U << BitWidth) - 1));
+      unsigned Ty1Size = DL.getTypeStoreSize(GEP1->getSourceElementType());
+      if (SafeRange.contains(R1) &&
+          V2Size.getValue() <= R1.getLower().getZExtValue() * Ty1Size)
+        return NoAlias;
+    }
+  }
+
   DecomposedGEP DecompGEP1, DecompGEP2;
   bool GEP1MaxLookupReached =
     DecomposeGEPExpression(GEP1, DecompGEP1, DL, &AC, DT);
   bool GEP2MaxLookupReached =
     DecomposeGEPExpression(V2, DecompGEP2, DL, &AC, DT);
 
   int64_t GEP1BaseOffset = DecompGEP1.StructOffset + DecompGEP1.OtherOffset;
   int64_t GEP2BaseOffset = DecompGEP2.StructOffset + DecompGEP2.OtherOffset;
if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) {
     // exactly, see if the computed offset from the common pointer tells us
     // about the relation of the resulting pointer.
     // If we know the two GEPs are based off of the exact same pointer (and not
     // just the same underlying object), see if that tells us anything about
     // the resulting pointers.
     if (GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups() ==
             GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups() &&
         GEP1->getPointerOperandType() == GEP2->getPointerOperandType()) {
-      AliasResult R = aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, DL);
+      AliasResult R = aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, DL, LVI);
       // If we couldn't find anything interesting, don't abandon just yet.
       if (R != MayAlias)
         return R;
     }
 
     // If the max search depth is reached, the result is undefined
     if (GEP2MaxLookupReached || GEP1MaxLookupReached)
       return MayAlias;

 
 void BasicAAWrapperPass::anchor() {}
 
 INITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basicaa",
                       "Basic Alias Analysis (stateless AA impl)", false, true)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
 INITIALIZE_PASS_END(BasicAAWrapperPass, "basicaa",
                     "Basic Alias Analysis (stateless AA impl)", false, true)
 
 FunctionPass *llvm::createBasicAAWrapperPass() {
   return new BasicAAWrapperPass();
 }
 
 bool BasicAAWrapperPass::runOnFunction(Function &F) {
   auto &ACT = getAnalysis<AssumptionCacheTracker>();
   auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
   auto &DTWP = getAnalysis<DominatorTreeWrapperPass>();
   auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
   auto *PVWP = getAnalysisIfAvailable<PhiValuesWrapperPass>();
+  auto *LVIP = &getAnalysis<LazyValueInfoWrapperPass>();
 
   Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), F, TLIWP.getTLI(),
                                  ACT.getAssumptionCache(F), &DTWP.getDomTree(),
                                  LIWP ? &LIWP->getLoopInfo() : nullptr,
-                                 PVWP ? &PVWP->getResult() : nullptr));
+                                 PVWP ? &PVWP->getResult() : nullptr,
+                                 LVIP ? &LVIP->getLVI() : nullptr));
 
   return false;
 }
 
 void BasicAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequired<AssumptionCacheTracker>();
   AU.addRequired<DominatorTreeWrapperPass>();
+  AU.addRequired<LazyValueInfoWrapperPass>();
   AU.addRequired<TargetLibraryInfoWrapperPass>();
   AU.addUsedIfAvailable<PhiValuesWrapperPass>();
 }
 
 BasicAAResult llvm::createLegacyPMBasicAAResult(Pass &P, Function &F) {
   return BasicAAResult(
       F.getParent()->getDataLayout(),
       F,
       P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
       P.getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F));
 }

lib/Analysis/LazyValueInfo.cpp

Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB,
   if (Result.isConstantRange()) {
     const ConstantRange &CR = Result.getConstantRange();
     if (const APInt *SingleVal = CR.getSingleElement())
       return ConstantInt::get(V->getContext(), *SingleVal);
   }
   return nullptr;
 }
 
+ConstantRange LazyValueInfo::getConstantRange(const Value *V, const BasicBlock *BB,
+                                              const Instruction *CxtI) {
+    return getConstantRange(const_cast<Value*>(V), const_cast<BasicBlock*>(BB),
+                            const_cast<Instruction*>(CxtI));
+}
+
 ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB,
                                               Instruction *CxtI) {
   assert(V->getType()->isIntegerTy());
   unsigned Width = V->getType()->getIntegerBitWidth();
   const DataLayout &DL = BB->getModule()->getDataLayout();
   ValueLatticeElement Result =
       getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
   if (Result.isUndefined())