[SelectionDAG] Assume that a GlobalAlias may alias other global values

[bjope]

Summary

This fixes a bug detected in DAGCombiner when using global alias
variables. Here is an example:

@foo = global i16 0, align 1
@aliasFoo = alias i16, i16 * @foo
define i16 @bar() {
  ...
  store i16 7, i16 * @foo, align 1
  store i16 8, i16 * @aliasFoo, align 1
  ...
}

BaseIndexOffset::computeAliasing would incorrectly derive NoAlias
for the two accesses in the example above, resulting in DAGCombiner
miscompiles.

This patch fixes the problem by a defensive approach letting
BaseIndexOffset::computeAliasing return false, i.e. that the aliasing
couldn't be determined, when comparing two global values and at least
one is a GlobalAlias. In the future we might improve this with a
deeper analysis to look at the aliasee for the GlobalAlias etc. But
that is a bit more complicated considering that we could have
'local_unnamed_addr' and situations with several 'alias' variables.

Fixes PR51878.

[niravd]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp

155

It looks like we can walk the GlobalAlias to the referenced object. If so, we should fully walk to a non-alias global instead.

168

We should handle this case earlier so we can correct determine that identical global aliases do in fact alias.

[bjope]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp

155

As I wrote in the desciption "In the future we might improve this with a deeper analysis to look at the aliasee for the GlobalAlias etc. But that is a bit more complicated considering that we could have 'local_unnamed_addr' and situations with several 'alias' variables.".

I'd actually prefer doing a bugfix that I'm confortable with. And I didn't quite understand the part about "Aliases that are not unnamed_addr are guaranteed to have the same address as the aliasee expression. unnamed_addr ones are only guaranteed to point to the same content." from https://llvm.org/docs/LangRef.html#aliases .

But if my approach was too naive and defensive, then I wonder why we have references to GlobalAlias:es in the IR in the first place. Couldn't we just reference the aliasee instead (leaving the GlobalAlias declaration as an unused declaration)?

168

Well, this if-statement derives IsAlias=false. So I'm just as confused about this check as your suggestion here. I needed to pull this check out from the orignal if-statment just to make it possible to add the check for global aliases before this. Otherwise it would derive that there is no alias between global aliases.

On the other hand, if this check of indices is considered as a bug in itself, to be removed, then my new check for global aliases isn't really needed either.

Removing this if-statement makes about 10 lit-tests to fail. Probably just due to getting slightly different codegen. Haven't really been able to prove that something is wrong with those tests.
Although, when adding a unittest that calls BaseIndexOffset::computeAliasing with the Op0 and Op1 being identical, but with NumBytes0 or NumBytes1 being unset (avoiding to enter the if at line 99) then computeAliasing would answer that there is no aliasing. That really seems wrong (but maybe that never happens in reality).

[bjope]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp

156

Maybe it is safer to look for GlobalIndirectSymbol here instead of GlobalAlias (as that would include any other indirect reference)?

168

I think that it maybe would be safer (and more correct) to check if we access two different GlobalValue here, and then derive NoAlias. Wouldn't it be weird to access one global using the address of another GlobalValue (the actual layout in memory between globals isn't given, or is it)?

(Although my intention with this patch has been to avoid the miscompiles for GlobalAlias:es, and I had planned to leave this mess with deriving NoAlias based on having identival Index in the BaseOffsetIndex for the future.)

[bjope]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp

168

I made a follow up for this in D110256.

[niravd]

Can you add a codegen test for PR51878? The example listed in your message should do.

Once I think with the follow up, this should be good to go.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp

155

I don't remember why this clause was neces

[bjope]

Adding a codegen reproducer.

[bjope]

In D110064#3015456, @niravd wrote:

Can you add a codegen test for PR51878? The example listed in your message should do.

Once I think with the follow up, this should be good to go.

D110256 has not been accepted yet, but is it OK to land this now (to be able to close PR51878)?

[niravd]

D110256 has not been accepted yet, but is it OK to land this now (to be able to close PR51878)?

I was just waiting for you to fix the unit tests.

[bjope]

Ran clang-format on unittest updates.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp

 //==- llvm/CodeGen/SelectionDAGAddressAnalysis.cpp - DAG Address Analysis --==//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/SelectionDAGAddressAnalysis.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/CodeGen/ISDOpcodes.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/CodeGen/SelectionDAGNodes.h"
 #include "llvm/CodeGen/TargetLowering.h"
+#include "llvm/IR/GlobalAlias.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Debug.h"
 #include <cstdint>
 
 using namespace llvm;
 
 bool BaseIndexOffset::equalBaseIndex(const BaseIndexOffset &Other,
                                      const SelectionDAG &DAG,
bool BaseIndexOffset::computeAliasing(const SDNode *Op0,
 
   bool IsFI0 = isa<FrameIndexSDNode>(BasePtr0.getBase());
   bool IsFI1 = isa<FrameIndexSDNode>(BasePtr1.getBase());
   bool IsGV0 = isa<GlobalAddressSDNode>(BasePtr0.getBase());
   bool IsGV1 = isa<GlobalAddressSDNode>(BasePtr1.getBase());
   bool IsCV0 = isa<ConstantPoolSDNode>(BasePtr0.getBase());
   bool IsCV1 = isa<ConstantPoolSDNode>(BasePtr1.getBase());
 
-  // If of mismatched base types or checkable indices we can check
-  // they do not alias.
-  if ((BasePtr0.getIndex() == BasePtr1.getIndex() || (IsFI0 != IsFI1) ||
-       (IsGV0 != IsGV1) || (IsCV0 != IsCV1)) &&
-      (IsFI0 || IsGV0 || IsCV0) && (IsFI1 || IsGV1 || IsCV1)) {
+  if ((IsFI0 || IsGV0 || IsCV0) && (IsFI1 || IsGV1 || IsCV1)) {
+    // We can derive NoAlias In case of mismatched base types.
+    if (IsFI0 != IsFI1 || IsGV0 != IsGV1 || IsCV0 != IsCV1) {
       IsAlias = false;
       return true;
     }
+    // We cannot safely determine whether the pointers alias if we compare two
+    // global values and at least one is a GlobalAlias.
+    if (IsGV0 && IsGV1 &&
+        (isa<GlobalAlias>(
+             cast<GlobalAddressSDNode>(BasePtr0.getBase())->getGlobal()) ||
+         isa<GlobalAlias>(
+             cast<GlobalAddressSDNode>(BasePtr1.getBase())->getGlobal())))
+      return false;
+    // If checkable indices we can check they do not alias.
+    // FIXME: Please describe this a bit better. Looks weird to say that there
+    // is no alias if the indices are the same. Is this code assuming that
+    // someone has checked that the base isn't the same as a precondition? And
+    // what about offsets? And what about NumBytes0 and NumBytest1 (can we
+    // really derive NoAlias here if we do not even know how many bytes that are
+    // dereferenced)?
+    if (BasePtr0.getIndex() == BasePtr1.getIndex()) {
+      IsAlias = false;
+      return true;
+    }
+  }
   return false; // Cannot determine whether the pointers alias.
 }
 
 bool BaseIndexOffset::contains(const SelectionDAG &DAG, int64_t BitSize,
                                const BaseIndexOffset &Other,
                                int64_t OtherBitSize, int64_t &BitOffset) const {
   int64_t Offset;
   if (!equalBaseIndex(Other, DAG, Offset))

llvm/test/CodeGen/X86/pr51878_computeAliasing.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -O1 -mtriple i686-unknown-linux-gnu -o - %s | FileCheck %s
+
+@foo = global i16 0, align 1
+@aliasFoo = alias i16, i16 * @foo
+@bar = global i16 0, align 1
+
+; This used to miscompile due to not realizing that the store to @aliasFoo
+; clobbered @foo (see PR51878).
+;
+; With some improvements to codegen it should be possible to detect that @foo
+; and @aliasFoo are aliases, and that @aliasFoo isn't aliasing with @bar. So
+; ideally we would end up with three movw instructions here. Running opt
+; before llc on this test case would take care of that, but llc is not smart
+; enough to deduce that itself yet.
+define i16 @main() {
+; CHECK-LABEL: main:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    movw $1, foo
+; CHECK-NEXT:    movw $2, bar
+; CHECK-NEXT:    movw $4, aliasFoo
+; CHECK-NEXT:    movzwl foo, %eax
+; CHECK-NEXT:    addw bar, %ax
+; CHECK-NEXT:    retl
+entry:
+  store i16 1, i16 * @foo
+  store i16 2, i16 * @bar
+  store i16 4, i16 * @aliasFoo
+  %foo = load i16, i16 * @foo
+  %bar = load i16, i16 * @bar
+  %res = add i16 %foo, %bar
+  ret i16 %res
+}

llvm/unittests/CodeGen/SelectionDAGAddressAnalysisTest.cpp

 //===- llvm/unittest/CodeGen/SelectionDAGAddressAnalysisTest.cpp  ---------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 

 protected:
   static void SetUpTestCase() {
     InitializeAllTargets();
     InitializeAllTargetMCs();
   }
 
   void SetUp() override {
     StringRef Assembly = "@g = global i32 0\n"
+                         "@g_alias = alias i32, i32* @g\n"
                          "define i32 @f() {\n"
                          "  %1 = load i32, i32* @g\n"
                          "  ret i32 %1\n"
                          "}";
 
     Triple TargetTriple("aarch64--");
     std::string Error;
     const Target *T = TargetRegistry::lookupTarget("", TargetTriple, Error);
void SetUp() override {
     M->setDataLayout(TM->createDataLayout());
 
     F = M->getFunction("f");
     if (!F)
       report_fatal_error("F?");
     G = M->getGlobalVariable("g");
     if (!G)
       report_fatal_error("G?");
+    AliasedG = M->getNamedAlias("g_alias");
+    if (!AliasedG)
+      report_fatal_error("AliasedG?");
 
     MachineModuleInfo MMI(TM.get());
 
     MF = std::make_unique<MachineFunction>(*F, *TM, *TM->getSubtargetImpl(*F),
                                            0, MMI);
 
     DAG = std::make_unique<SelectionDAG>(*TM, CodeGenOpt::None);
     if (!DAG)
EVT getTypeToTransformTo(EVT VT) {
     return DAG->getTargetLoweringInfo().getTypeToTransformTo(Context, VT);
   }
 
   LLVMContext Context;
   std::unique_ptr<LLVMTargetMachine> TM;
   std::unique_ptr<Module> M;
   Function *F;
   GlobalVariable *G;
+  GlobalAlias *AliasedG;
   std::unique_ptr<MachineFunction> MF;
   std::unique_ptr<SelectionDAG> DAG;
 };
 
 TEST_F(SelectionDAGAddressAnalysisTest, sameFrameObject) {
   SDLoc Loc;
   auto Int8VT = EVT::getIntegerVT(Context, 8);
   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4);
TEST_F(SelectionDAGAddressAnalysisTest, globalWithFrameObject) {
   bool IsAlias;
   bool IsValid = BaseIndexOffset::computeAliasing(
       Store.getNode(), NumBytes, GStore.getNode(), GNumBytes, *DAG, IsAlias);
 
   EXPECT_TRUE(IsValid);
   EXPECT_FALSE(IsAlias);
 }
 
+TEST_F(SelectionDAGAddressAnalysisTest, globalWithAliasedGlobal) {
+  SDLoc Loc;
+
+  EVT GTy = DAG->getTargetLoweringInfo().getValueType(DAG->getDataLayout(),
+                                                      G->getType());
+  SDValue GValue = DAG->getConstant(0, Loc, GTy);
+  SDValue GAddr = DAG->getGlobalAddress(G, Loc, GTy);
+  SDValue GStore = DAG->getStore(DAG->getEntryNode(), Loc, GValue, GAddr,
+                                 MachinePointerInfo(G, 0));
+  Optional<int64_t> GNumBytes = MemoryLocation::getSizeOrUnknown(
+      cast<StoreSDNode>(GStore)->getMemoryVT().getStoreSize());
+
+  SDValue AliasedGValue = DAG->getConstant(1, Loc, GTy);
+  SDValue AliasedGAddr = DAG->getGlobalAddress(AliasedG, Loc, GTy);
+  SDValue AliasedGStore = DAG->getStore(DAG->getEntryNode(), Loc,
+                                        AliasedGValue, AliasedGAddr,
+                                        MachinePointerInfo(AliasedG, 0));
+
+  bool IsAlias;
+  bool IsValid = BaseIndexOffset::computeAliasing(
+      GStore.getNode(), GNumBytes, AliasedGStore.getNode(), GNumBytes, *DAG,
+      IsAlias);
+
+  // We some deeper analysis we could detect if G and AliasedG is aliasing or
+  // not. But computeAliasing is currently defensive and assumes that a
+  // GlobalAlias might alias with any global variable.
+  EXPECT_FALSE(IsValid);
+}
+
 TEST_F(SelectionDAGAddressAnalysisTest, fixedSizeFrameObjectsWithinDiff) {
   SDLoc Loc;
   auto Int8VT = EVT::getIntegerVT(Context, 8);
   // <vscale x 4 x i8>
   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true);
   // <vscale x 2 x i8>
   auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2, true);
   // <2 x i8>