[BasicAA] Check if V is itself a PHI in isValueEqualInPotentialCycles

[jholewinski]

Summary

BasicAAResult::isValueEqualInPotentialCycles uses previously visited
PHI nodes to determine if a value is provably equal across cycles.
But it does not consider the case where the value itself is a PHI
node that is reachable from itself, implying a cycle in the CFG. This
change teaches isValueEqualInPotentialCycles to handle this case by
explicitly checking if the incoming value is a PHI and checking if it
is reachable from itself.

[nikic]

Reporting NoAlias here is correct -- cross-iteration behavior is outside the purview of AA. Consuming code is responsible for interpreting this correctly, see e.g. the loop invariance checks in MemorySSA and DSE.

Can you share what your original problem was? Possibly some transform makes incorrect assumptions about the meaning of AA results.

[jholewinski]

In D122671#3414805, @nikic wrote:

Reporting NoAlias here is correct -- cross-iteration behavior is outside the purview of AA. Consuming code is responsible for interpreting this correctly, see e.g. the loop invariance checks in MemorySSA and DSE.

Ok, thanks for the information. Is this documented somewhere in the LLVM docs? I looked around before creating this diff but didn't see anything that says either way whether LLVM AA is supposed to return MayAlias if it cannot prove pointers cannot alias across iterations. I was also thrown off by a few comments in BasicAA that seems to imply it does track aliasing across iterations.

[is this not checking whether the value may change across iterations?]

// Make sure that the visited phis cannot reach the Value. This ensures that
// the Values cannot come from different iterations of a potential cycle the
// phi nodes could be involved in.
for (auto *P : VisitedPhiBBs)
  if (isPotentiallyReachable(&P->front(), Inst, nullptr, DT))
    return false;

[reference to skipping a case to prevent needing to handle cross-iteration aliasing]

// VarIndex = Scale*V0 + (-Scale)*V1.
// If V0 != V1 then abs(VarIndex) >= abs(Scale).
// Check that VisitedPhiBBs is empty, to avoid reasoning about
// inequality of values across loop iterations.
const VariableGEPIndex &Var0 = DecompGEP1.VarIndices[0];
const VariableGEPIndex &Var1 = DecompGEP1.VarIndices[1];

[analyzes cross-iteration equality?]

// Are we checking for alias of the same value?
// Because we look 'through' phi nodes, we could look at "Value" pointers from
// different iterations. We must therefore make sure that this is not the
// case. The function isValueEqualInPotentialCycles ensures that this cannot
// happen by looking at the visited phi nodes and making sure they cannot
// reach the value.
if (isValueEqualInPotentialCycles(V1, V2))
  return AliasResult::MustAlias;

Am I just misunderstanding what BasicAA is trying to do here?

Can you share what your original problem was? Possibly some transform makes incorrect assumptions about the meaning of AA results.

The issue is in an out-of-tree pass that we wrote. If BasicAA does not return MayAlias for pointers across loop iterations then we do have an incorrect assumption.

[nikic]

The VisitedPhiBBs handling is related, but handles a different case: Sometimes, BasicAA itself will be looking across loop iterations when recursing into a phi, and VisitedPhiBBs is used to not assume equality relationships when that happens.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 //===- BasicAliasAnalysis.cpp - Stateless Alias Analysis Impl -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
                                                   const Value *V2) {
   if (V != V2)
     return false;
 
   const Instruction *Inst = dyn_cast<Instruction>(V);
   if (!Inst)
     return true;
 
+  // Check if the value is itself a PHI node that is reachable from itself,
+  // implying a cycle that can cause the value to have a different value on
+  // different iterations. In this case, return false to indicate that we cannot
+  // prove the two values will be equal across cycles.
+  if (const PHINode *PN = dyn_cast<const PHINode>(Inst)) {
+    if (isPotentiallyReachable(PN->getParent(), PN->getParent(), nullptr, DT)) {
+      return false;
+    }
+  }
+
   if (VisitedPhiBBs.empty())
     return true;
 
   if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck)
     return false;
 
   // Make sure that the visited phis cannot reach the Value. This ensures that
   // the Values cannot come from different iterations of a potential cycle the

llvm/test/Analysis/BasicAA/value-equal-cycle-phi.ll

+; RUN: opt -aa-pipeline=basic-aa -passes=aa-eval -print-all-alias-modref-info -disable-output < %s 2>&1 | FileCheck %s
+
+; CHECK-LABEL: may_alias_ptr
+; CHECK: MayAlias: float* %p, float* %p.1
+
+define void @may_alias_ptr(float* %arr, float* %out, i32* %idx) local_unnamed_addr {
+entry:
+  br label %header
+
+header:
+  %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
+  %p.3 = getelementptr i32, i32* %idx, i32 %i
+  %t = load i32, i32* %p.3, align 4
+  %a = icmp eq i32 %t, 0
+  br i1 %a, label %if.then, label %if.else
+
+if.then:
+  ; BasicAA cannot know whether the prior iteration wrote to arr[i], so it must
+  ; return MayAlias between %p and %p.1.
+  %p = getelementptr inbounds float, float* %arr, i32 %i
+  %v = load float, float* %p, align 4
+  %p.2 = getelementptr inbounds float, float* %out, i32 0
+  store float %v, float* %p.2, align 4
+  br label %latch
+
+if.else:
+  ; This will write to arr[i+1], which will be arr[i] on the next iteration
+  %i.0 = add nuw nsw i32 %i, 1
+  %p.1 = getelementptr float, float* %arr, i32 %i.0
+  store float 0.0, float* %p.1, align 4
+  br label %latch
+
+latch:
+  %i.next = add nuw nsw i32 %i, 1
+  %c = icmp ult i32 %i.next, 4
+  br i1 %c, label %header, label %exit
+
+exit:
+  ret void
+}