[DA] Aliasing checks in DA are incorrect

[DMG862]

Bugzilla Link	42143
Version	trunk
OS	Linux
CC	@fhahn,@hfinkel,@dobbelaj-snps,@LebedevRI,@Meinersbur,@felipepiovezan

Extended Description

The Aliasing checks in DA currently do this:
// Check the original locations (minus size) for noalias, which can happen for
// tbaa, incompatible underlying object locations, etc.
MemoryLocation LocAS(LocA.Ptr, LocationSize::unknown(), LocA.AATags);
MemoryLocation LocBS(LocB.Ptr, LocationSize::unknown(), LocB.AATags);
if (AA->alias(LocAS, LocBS) == NoAlias)
return NoAlias;

// Check the underlying objects are the same
const Value *AObj = GetUnderlyingObject(LocA.Ptr, DL);
const Value *BObj = GetUnderlyingObject(LocB.Ptr, DL);

// If the underlying objects are the same, they must alias
if (AObj == BObj)
return MustAlias;

// We may have hit the recursion limit for underlying objects, or have
// underlying objects where we don't know they will alias.
if (!isIdentifiedObject(AObj) || !isIdentifiedObject(BObj))
return MayAlias;

// Otherwise we know the objects are different and both identified objects so
// must not alias.
return NoAlias;

The alias check is invalid for cases like this, which will return noalias for individual loop iterations, but we care about cross-loop dependencies:
define float @​f() {
entry:
%g = alloca float, align 4
%h = alloca float, align 4
br label %for.body

for.body: ; preds = %for.body, %entry
%p = phi float* [ %g, %entry ], [ %q, %for.body ]
%q = phi float* [ %h, %entry ], [ %p, %for.body ]
%0 = load float, float* %p, align 4
store float undef, float* %q, align 4
%branch_cond = fcmp ugt float %0, 0.0
br i1 %branch_cond, label %for.cond.cleanup, label %for.body

for.cond.cleanup: ; preds = %for.body
ret float undef
}

[DMG862]

assigned to @DMG862

[hfinkel]

To repeat what I said on the mailing list:

We shouldn't need both the AA check here and the underlying-object check also, as the AA check includes an underlying-object check (and not much else, aside from checks on metadata, when both sizes are unknown). However, as this example shows, the fact that the two SSA values in question refer to different, identified underlying objects, doesn't prevent them from having a cross-iteration dependence as the identify of those underlying objects can change across different iterations (and, thus, the underlying object of one variable in one iteration might be the underlying object used by another variable in another iteration).

I'm open to suggestions on how to best resolve this situation. I'm leaning toward suggesting that we have a metadata-only AA query, and use that here, instead of calling something that will invoke BasicAA's logic. My metadata-only AA query, I specifically mean a fundamental dependency-analysis query, likely implemented by the AA subsystem for code-reuse reasons, which answers the question: is there some reason to believe that any instances of these two values never take the same value along any dynamic path through the CFG (or something similar).

[llvmbot]

There may be other instances where AliasAnalysis::alias() is used like this (for sure in my private code), so would it be safer to have chnage this function to return the "per-function/across iterations" result?

The current AliasAnalysis::alias() behavior could then be moved to a new AliasAnalysis::alias_ssa() function and used where that is intended/safe.

[DMG862]

I went looking through LAA for some inspiration, but it appears to fall into this trap too. This slightly modified code:
define void @​f(i32 %n) {
entry:
%g = alloca float, align 4
%h = alloca float, align 4
br label %for.body

for.body: ; preds = %for.body, %entry
%i = phi i32 [0, %entry ], [ %inc, %for.body ]
%p = phi float* [ %g, %entry ], [ %q, %for.body ]
%q = phi float* [ %h, %entry ], [ %p, %for.body ]
%0 = load float, float* %p, align 4
store float 0.0, float* %q, align 4
%inc = add nuw i32 %i, 1
%branch_cond = icmp ult i32 %i, %n
br i1 %branch_cond, label %for.body, label %for.cond.cleanup

for.cond.cleanup: ; preds = %for.body
ret void
}

Seems to produces two alias sets:

../build.clean/bin/opt -basicaa -tbaa -loop-accesses -analyze da2.ll -debug
LAA: Found a loop in f: for.body
LAA: Processing memory accesses...
AST: Alias Set Tracker: 2 alias sets for 2 pointer values.
AliasSet[0x72a1de0, 1] must alias, No access Pointers: (float* %q, unknown)
AliasSet[0x72a20b0, 1] must alias, No access Pointers: (float* %p, unknown)

LAA: Accesses(2):
%q = phi float* [ %h, %entry ], [ %p, %for.body ] (write)
%p = phi float* [ %g, %entry ], [ %q, %for.body ] (read-only)
Underlying objects for pointer %q = phi float* [ %h, %entry ], [ %p, %for.body ]
%g = alloca float, align 4
%h = alloca float, align 4
Underlying objects for pointer %p = phi float* [ %g, %entry ], [ %q, %for.body ]
%h = alloca float, align 4
%g = alloca float, align 4
LAA: We can perform a memory runtime check if needed.
LAA: No unsafe dependent memory operations in loop. We don't need runtime memory checks.
Memory dependences are safe
Dependences:
Run-time memory checks:
Grouped accesses:

Non vectorizable stores to invariant address were not found in loop.
SCEV assumptions:

Which I believe means it did not find any sorts of dependencies. I guess isn't a problem for the clients of LAA like the vectoriser as they will always be blocked by the cross-loop phis anyway.

[hfinkel]

I went looking through LAA for some inspiration

Exactly, it does the same thing.

[Meinersbur]

I think DI should query AA only on the underylying object. That is:

const Value *AObj = GetUnderlyingObject(LocA.Ptr, DL);
const Value *BObj = GetUnderlyingObject(LocB.Ptr, DL);

MemoryLocation LocAS(AObj , LocationSize::unknown());
MemoryLocation LocBS(AObj , LocationSize::unknown());
if (AA->alias(LocAS, LocBS) == NoAlias)
  return NoAlias;

Since we are looking whether the base array itself is overlapping (any of its element might be accessed), rather the individual element in one iteration.

[sebpop]

Memory SSA is way too heavy to maintain in loop passes.
I will post a patch to fix this with SCEV analysis.