[DependenceAnalysis] Conservatively exit on type mismatch

[artemrad]

Summary

DA does not check that types match during analysis. Bitcasts can result in a wide access overlapping a narrower access, but because the pointer values are different, DA considers them independent.

Make sure that alignment matches store size.

Change Summary:

• Updated description of depends() to be descriptive instead of prescriptive
• Optimization: exit early if no common loops AND don't care about loop independent dependencies
• Check that alignment matches store size
• Renamed PossiblyLoopIndependent to PossiblyIntraIteration to be more clear with intent of code

[nikic]

llvm/lib/Analysis/DependenceAnalysis.cpp

3655

Why does this check the type store size of the pointer type, rather than the accessed type?

[Meinersbur]

llvm/lib/Analysis/DependenceAnalysis.cpp

3512–3516

Did you intend to replace the non-doxygen comment for depends?

3651

Please consider the LLVM coding style for use of auto.

[Meinersbur]

llvm/include/llvm/Analysis/DependenceAnalysis.h

285–286

Maybe we should rename PossiblyLoopIndependent to something else. I don't see how "LoopIndependent" makes a statement about non-loop dependences.

llvm/lib/Analysis/DependenceAnalysis.cpp

3570

3628–3631

underlyingObjectsAlias should return PartialAlias alias in such cases. That is, I think it still may return MustAlias if the address is the same but the size is different. In that case it should be sufficient to a compare just the sizes, but not the alignment

3654–3655

You could consider llvm::MemoryLocation for this. It abstracts over for LoadInst/StoreInst and also determines that access size.

[bmahjour]

llvm/include/llvm/Analysis/DependenceAnalysis.h

285–286

Any suggestions on what the rename should be? "Loop-Independent" is well defined in the literature and seems appropriately used here.

llvm/lib/Analysis/DependenceAnalysis.cpp

3572

add a LLVM_DEBUG before returning?

3628–3631

I agree this logic belongs to underlyingObjectsAlias.

3632

DL doesn't change in any invocation of the lambda, so better be captured instead of being passed as arg.

llvm/test/Analysis/DependenceAnalysis/OverlappingAddresses.ll

24

Should we also check if we can prove that the pointer differences will always be larger than the misalignment? For example if this was adding 2 to the base pointer, then the store on line 14 would not overlap with the two loads below.

[efriedma]

llvm/lib/Analysis/DependenceAnalysis.cpp

3640

Load/store instructions were fixed so alignment can't be zero.

You can use "LI->getAlign()" to get an llvm::Align instead of an unsigned.

[Meinersbur]

llvm/include/llvm/Analysis/DependenceAnalysis.h

285–286

It's just an idea. If it a well-established term we can keep it, I just don't think it is a good one. It gets really confusing if we consider that a dependence can be both, loop-carried and within the same iteration.

for (int i = ...) {
  use(A[0]);
  A[i] = ...;
  use(A[0]);
}

The comment itself would suggest PossiblyIntraIteration.

[artemrad]

Addressed some comments, but not all.

[artemrad]

llvm/lib/Analysis/DependenceAnalysis.cpp

3512–3516

Nope.

3640

Didn't know this. Neat. Fixed.

3655

Good catch. I missed this. Fixed

[Meinersbur]

llvm/lib/Analysis/DependenceAnalysis.cpp

3595–3598

Seems to make sense that DependenceAnalysis does not handle accesses that fall between two array elements. Am I correct that his makes sure that each load/store will access at most one alignment "slot"? And therefore conservatively bails out for any type that is larger than its alignment (such as _Complex, struct, classes, etc.)?

In that case, I propose a reformulation:

DependenceAnalysis assumes that accesses never partially overlap. Here we ensure that every access size is smaller than the alignment. This guarantees that two aligned accesses either have the same pointer value, or do not alias, not even partially.
FIXME: This excludes many common cases from analysis, such as array of structs, _Complex and bitcasts to i8* (eg. memset, memcpy, fallback type for many optimization passes).

3599

An "unaligned access" would be an access that is ... not aligned. However, this lambda tests whether partial overlap is possible despite alignment. Proposed name: "IsAccSizeExceeedingAlignment" (or some of the like).

3606

[nit] redundant outer parens

Is Width <= Alignment sufficient?

3609–3610

What makes partial overlap impossible if both pointer's last operation is a GEP?

3611–3616

llvm::Type::getPointerElementType() is a shortcut for cast<PointerType>(...)->getElementType()

[nikic]

llvm/lib/Analysis/DependenceAnalysis.cpp

3602

getLoadStoreType() + getLoadStoreAlignment()

3611–3616

This should use getLoadStoreType() for opaque pointer compatibility as well.

llvm/include/llvm/Analysis/DependenceAnalysis.h

public:
 
     /// Handle transitive invalidation when the cached analysis results go away.
     bool invalidate(Function &F, const PreservedAnalyses &PA,
                     FunctionAnalysisManager::Invalidator &Inv);
 
     /// depends - Tests for a dependence between the Src and Dst instructions.
     /// Returns NULL if no dependence; otherwise, returns a Dependence (or a
     /// FullDependence) with as much information as can be gleaned.
-    /// The flag PossiblyLoopIndependent should be set by the caller
-    /// if it appears that control flow can reach from Src to Dst
-    /// without traversing a loop back edge.
+    /// If PossiblyIntraIteration is true will also test for intra-iteration
+    /// dependencies.
     std::unique_ptr<Dependence> depends(Instruction *Src,
                                         Instruction *Dst,
-                                        bool PossiblyLoopIndependent);
+                                        bool PossiblyIntraIteration);
 
     /// getSplitIteration - Give a dependence that's splittable at some
     /// particular level, return the iteration that should be used to split
     /// the loop.
     ///
     /// Generally, the dependence analyzer will be used to build
     /// a dependence graph for a function (basically a map from instructions
     /// to dependences). Looking for cycles in the graph shows us loops

llvm/lib/Analysis/DependenceAnalysis.cpp

bool Dependence::isScalar(unsigned level) const {
   return false;
 }
 
 
 //===----------------------------------------------------------------------===//
 // FullDependence methods
 
 FullDependence::FullDependence(Instruction *Source, Instruction *Destination,
-                               bool PossiblyLoopIndependent,
+                               bool PossiblyIntraIteration,
                                unsigned CommonLevels)
     : Dependence(Source, Destination), Levels(CommonLevels),
-      LoopIndependent(PossiblyLoopIndependent) {
+      LoopIndependent(PossiblyIntraIteration) {
   Consistent = true;
   if (CommonLevels)
     DV = std::make_unique<DVEntry[]>(CommonLevels);
 }
 
 // The rest are simple getters that hide the implementation.
 
 // getDirection - Returns the direction associated with a particular level.
if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Function>>())
     return true;
 
   // Check transitive dependencies.
   return Inv.invalidate<AAManager>(F, PA) ||
          Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||
          Inv.invalidate<LoopAnalysis>(F, PA);
 }
 
 // depends -
 // Returns NULL if there is no dependence.
 // Otherwise, return a Dependence with as many details as possible.
+// If PossiblyIntraIteration is true will also test for intra-iteration 
+// dependencies.
 // Corresponds to Section 3.1 in the paper
 //
 //            Practical Dependence Testing
 //            Goff, Kennedy, Tseng
 //            PLDI 1991
 //
 // Care is required to keep the routine below, getSplitIteration(),
 // up to date with respect to this routine.
 std::unique_ptr<Dependence>
 DependenceInfo::depends(Instruction *Src, Instruction *Dst,
-                        bool PossiblyLoopIndependent) {
+                        bool PossiblyIntraIteration) {
   if (Src == Dst)
-    PossiblyLoopIndependent = false;
+    PossiblyIntraIteration = false;
 
   if (!(Src->mayReadOrWriteMemory() && Dst->mayReadOrWriteMemory()))
     // if both instructions don't reference memory, there's no dependence
     return nullptr;
 
   if (!isLoadOrStore(Src) || !isLoadOrStore(Dst)) {
     // can only analyze simple loads and stores, i.e., no calls, invokes, etc.
     LLVM_DEBUG(dbgs() << "can only handle simple loads and stores\n");
case AliasResult::MustAlias:
     break; // The underlying objects alias; test accesses for dependence.
   }
 
   // establish loop nesting levels
   establishNestingLevels(Src, Dst);
   LLVM_DEBUG(dbgs() << "    common nesting levels = " << CommonLevels << "\n");
   LLVM_DEBUG(dbgs() << "    maximum nesting levels = " << MaxLevels << "\n");
 
-  FullDependence Result(Src, Dst, PossiblyLoopIndependent, CommonLevels);
+  FullDependence Result(Src, Dst, PossiblyIntraIteration, CommonLevels);
   ++TotalArrayPairs;
 
+  if (!PossiblyIntraIteration && CommonLevels == 0) {
+    LLVM_DEBUG(dbgs() << "no common loops and no intra-iteration analysis\n");
+    return nullptr;
+  }
+
   unsigned Pairs = 1;
   SmallVector<Subscript, 2> Pair(Pairs);
   const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
   const SCEV *DstSCEV = SE->getSCEV(DstPtr);
   LLVM_DEBUG(dbgs() << "    SrcSCEV = " << *SrcSCEV << "\n");
   LLVM_DEBUG(dbgs() << "    DstSCEV = " << *DstSCEV << "\n");
   if (SE->getPointerBase(SrcSCEV) != SE->getPointerBase(DstSCEV)) {
     // If two pointers have different bases, trying to analyze indexes won't
     // work; we can't compare them to each other. This can happen, for example,
     // if one is produced by an LCSSA PHI node.
     //
     // We check this upfront so we don't crash in cases where getMinusSCEV()
     // returns a SCEVCouldNotCompute.
     LLVM_DEBUG(dbgs() << "can't analyze SCEV with different pointer base\n");
     return std::make_unique<Dependence>(Src, Dst);
   }
   Pair[0].Src = SrcSCEV;
   Pair[0].Dst = DstSCEV;
+  const DataLayout &DL = F->getParent()->getDataLayout();
+
+  // DependenceAnalysis isn't able to deal with different
+  // access widths. If access widths are the same, but alignment is
+  // smaller than the store size, accesses could overlap.
+  // Reject these cases.
+  auto IsUnalignedLoadStore = [&](const Instruction *I) {
+    const LoadInst *LI = dyn_cast<LoadInst>(I);
+    const StoreInst *SI = dyn_cast<StoreInst>(I);
+    Type *IType = (LI) ? LI->getType() : SI->getValueOperand()->getType();
+    uint64_t Width = DL.getTypeStoreSize(IType);
+    uint64_t Alignment = (LI) ? LI->getAlign().value() : SI->getAlign().value();
+
+    return ((Alignment % Width) != 0);
+  };
+
+  bool ModifiedGEPOp =
+      !dyn_cast<GEPOperator>(SrcPtr) || !dyn_cast<GEPOperator>(DstPtr);
+  Type *SrcOpType =
+      static_cast<PointerType *>(MemoryLocation::get(Src).Ptr->getType())
+          ->getElementType();
+  Type *DstOpType =
+      static_cast<PointerType *>(MemoryLocation::get(Dst).Ptr->getType())
+          ->getElementType();
+  TypeSize SrcWriteSize = DL.getTypeStoreSize(SrcOpType);
+  TypeSize DstWriteSize = DL.getTypeStoreSize(DstOpType);
+
+  if ((IsUnalignedLoadStore(Src) || IsUnalignedLoadStore(Dst) ||
+       (SrcWriteSize != DstWriteSize)) &&
+      ModifiedGEPOp) {
+    LLVM_DEBUG(
+        dbgs() << "Memory accesses are different widths from non-GEPs\n");
+    return std::make_unique<Dependence>(Src, Dst);
+  }
 
   if (Delinearize) {
     if (tryDelinearize(Src, Dst, Pair)) {
       LLVM_DEBUG(dbgs() << "    delinearized\n");
       Pairs = Pair.size();
     }
   }
 
   for (unsigned P = 0; P < Pairs; ++P) {
     Pair[P].Loops.resize(MaxLevels + 1);
     Pair[P].GroupLoops.resize(MaxLevels + 1);
     Pair[P].Group.resize(Pairs);
     removeMatchingExtensions(&Pair[P]);
     Pair[P].Classification =
       classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()),
                    Pair[P].Dst, LI->getLoopFor(Dst->getParent()),
                    Pair[P].Loops);
     Pair[P].GroupLoops = Pair[P].Loops;
     Pair[P].Group.set(P);
     LLVM_DEBUG(dbgs() << "    subscript " << P << "\n");
     LLVM_DEBUG(dbgs() << "\tsrc = " << *Pair[P].Src << "\n");
     LLVM_DEBUG(dbgs() << "\tdst = " << *Pair[P].Dst << "\n");
     LLVM_DEBUG(dbgs() << "\tclass = " << Pair[P].Classification << "\n");
     LLVM_DEBUG(dbgs() << "\tloops = ");
     LLVM_DEBUG(dumpSmallBitVector(Pair[P].Loops));
   }
 
   SmallBitVector Separable(Pairs);
   SmallBitVector Coupled(Pairs);
 
   // Partition subscripts into separable and minimally-coupled groups
   // Algorithm in paper is algorithmically better;
   // this may be faster in practice. Check someday.
   //
   // Here's an example of how it works. Consider this code:
   //
   //   for (i = ...) {
DependenceInfo::depends(Instruction *Src, Instruction *Dst,
   // Make sure the Scalar flags are set correctly.
   SmallBitVector CompleteLoops(MaxLevels + 1);
   for (unsigned SI = 0; SI < Pairs; ++SI)
     CompleteLoops |= Pair[SI].Loops;
   for (unsigned II = 1; II <= CommonLevels; ++II)
     if (CompleteLoops[II])
       Result.DV[II - 1].Scalar = false;
 
-  if (PossiblyLoopIndependent) {
+  if (PossiblyIntraIteration) {
     // Make sure the LoopIndependent flag is set correctly.
     // All directions must include equal, otherwise no
     // loop-independent dependence is possible.
     for (unsigned II = 1; II <= CommonLevels; ++II) {
       if (!(Result.getDirection(II) & Dependence::DVEntry::EQ)) {
         Result.LoopIndependent = false;
         break;
       }
     }
   }
   else {
     // On the other hand, if all directions are equal and there's no
     // loop-independent dependence possible, then no dependence exists.
     bool AllEqual = true;
     for (unsigned II = 1; II <= CommonLevels; ++II) {
       if (Result.getDirection(II) != Dependence::DVEntry::EQ) {
         AllEqual = false;
         break;

llvm/test/Analysis/DependenceAnalysis/OverlappingAddresses.ll

+; Verify that we do not consider overlapping accesses to be independent,
+; even though the raw pointer values are different
+; RUN: opt < %s -disable-output "-passes=print<da>" -aa-pipeline=basic-aa 2>&1 \
+; RUN: | FileCheck %s
+; RUN: opt < %s -analyze -enable-new-pm=0 -basic-aa -da | FileCheck %s
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.6.0"
+
+define void @overlapping0(i32* %A, i64 %n) nounwind uwtable ssp {
+entry:
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %n
+  %arrayidx_cast = bitcast i32* %arrayidx to i64*
+  store i64 0, i64* %arrayidx_cast, align 4
+
+; CHECK: da analyze - none!
+; CHECK: da analyze - confused!
+; CHECK: da analyze - confused!
+; CHECK: da analyze - none
+; CHECK: da analyze - confused!
+; CHECK: da analyze - none!
+
+  %add1 = add i64 %n, 1
+  %arrayidx2 = getelementptr inbounds i32, i32* %A, i64 %add1
+  %0 = load i32, i32* %arrayidx2, align 4
+ 
+  ; Even if the load and store types are the same, if their
+  ; alignments are smaller than the store size and they are
+  ; accesses through something other than a straightforward
+  ; gep, they can still overlap, as this access shows
+  %arrayidx2_cast = bitcast i32* %arrayidx2 to i64*
+  %1 = load i64, i64* %arrayidx2_cast, align 4
+  ret void
+}
+