Fix invalid addrspacecast due to combining alloca with global var

[yaxunl]

Summary

For function-scope variables with large initialisation list, FE usually generates a global variable to hold the initializer, then generates memcpy intrinsic to initialize the alloca. InstCombiner::visitAllocaInst identifies such allocas which are accessed only by reading and replaces them with the global variable. This is done by casting the global variable to the type of the alloca and replacing all references.

However, when the global variable is in a different address space which is disjoint with addr space 0 (e.g. for IR generated from OpenCL, global variable cannot be in private addr space i.e. addr space 0), casting the global variable to addr space 0 results in invalid IR for certain targets (e.g. amdgpu).

To fix this issue, when the global variable is not in addr space 0, instead of casting it to addr space 0, this patch chases down the uses of alloca until reaching the load instructions, then replaces load from alloca with load from the global variable. If during the chasing bitcast and GEP are encountered, new bitcast and GEP based on the global variable are generated and used in the load instructions.

A debug output is also added to amdgpu backend to facilitate debugging such issues.

[majnemer]

Please use auto * instead of auto when dealing with pointer types.

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

240–241 ↗

(On Diff #79811)

Formatting.

243 ↗

(On Diff #79811)

Please format this appropriately.

244 ↗

(On Diff #79811)

Don't use llvm:: here.

268–269 ↗

(On Diff #79811)

Please brace this.

test/Transforms/InstCombine/memcpy-addrspace.ll

66 ↗

(On Diff #79811)

Please fix.

[yaxunl]

Revised by David's comments.

[yaxunl]

ping

[majnemer]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

238–240 ↗

(On Diff #79913)

I'd make these cast<> instead of dyn_cast<> and remove PT and NT from the assert.

253–256 ↗

(On Diff #79913)

Is it possible for you to create instructions which you never RAUW?

345–351 ↗

(On Diff #79913)

Formatting looks funny.

[arsenm]

lib/Target/AMDGPU/SIISelLowering.cpp

37–39 ↗

(On Diff #79913)

I think these will break -debug-only=isel so this should also be removed

2141–2142 ↗

(On Diff #79913)

This should be removed

[yaxunl]

lib/Target/AMDGPU/SIISelLowering.cpp

2141–2142 ↗

(On Diff #79913)

I can keep it to myself but without this debug output it is much difficult to debug the "invalid addrspacecast" issue.

[arsenm]

lib/Target/AMDGPU/SIISelLowering.cpp

2141–2142 ↗

(On Diff #79913)

It already produces an error here which is easy to track down

[yaxunl]

lib/Target/AMDGPU/SIISelLowering.cpp

2141–2142 ↗

(On Diff #79913)

but it does not tell you what SDNode causes it. Even if you break into it you still need to dump it to know what happens.

[yaxunl]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

253–256 ↗

(On Diff #79913)

Yes, but then these instructions will be removed. The lit test checks that.

[yaxunl]

Revised by David's and Matt's comments.

[majnemer]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

253–256 ↗

(On Diff #79913)

It is bad form to create new instructions in instcombine if you aren't sure you will want to keep them. Please keep in mind that IC is heavily relied upon and shows up several times in the pass pipeline.

[majnemer]

There are two different things going on in this patch: a correctness fix and an optimization. How about we split out the correctness fix out to another patch?

[yaxunl]

In D27283#617931, @majnemer wrote:

There are two different things going on in this patch: a correctness fix and an optimization. How about we split out the correctness fix out to another patch?

The correctness-only fix will generate less optimal code which cause a regression in another lit test.

I have a fix for the issue you mentioned above.

[yaxunl]

Revised so that no useless instructions generated during instruction combination.

[yaxunl]

Ping

[yaxunl]

Hi David,

Do I still need to split this patch into two: one for disabling the optimisation to fix the functional issue, and the second to add the new optimization?

Thanks.

[rivanvx]

Whoa, this seems to fix the remaining part of https://bugs.freedesktop.org/show_bug.cgi?id=99552
Reviewing.

[rivanvx]

To the extent of my knowledge and testing, this looks good.

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

256 ↗

(On Diff #81114)

If the first user isn't an instruction, what guarantees that others aren't? How come there isn't a continue here instead?

287–288 ↗

(On Diff #81114)

Does the order matter here? If not, can you make it consistent with other two cases?

[yaxunl]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

256 ↗

(On Diff #81114)

The function is recursive. It tries to iterate through the users and then the users of users, so long so forth, to find a chain of GEP/casts that ends with a load, then try to replace the uses of the load with the load of another pointer. The replacing only happens when we reach the load instruction.

For example, we want to replace a with aa, which are pointers to the same pointee type in different addr space:

b = bitcast a
c = GEP b, 1
d = load c
// uses of d

so we create new casts/GEPs/loads

bb = bitcast aa
cc = GEP bb, 1
dd = load cc
// replace uses of d with dd

If the first user is not an instruction, that means this will not end up as a chain of instructions, so we will just return so that the recursive function will try the next path.

287–288 ↗

(On Diff #81114)

The handling of load instructions is different from the handling of GEP/casts. For example, we want to replace a with aa

b = cast a
// uses of b
c = load b
// uses of c

We will create new casts following the uses of a,

bb = cast aa
cc = load bb
// replaces uses of c with uses of cc

However, we should not replace uses of b with bb since they have different address space therefore different type. Also we may not be able to remove b since it may have other users. However, since one inst combine pass contains multiple iterations, it will be removed in the next iteration if it does not have any users.

llvm/trunk/lib/Transforms/InstCombine/InstCombineInternal.h

public:
   /// The routine checks that the DI parent and DB are different.
   bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
                         const BasicBlock *DB) const;
 
   /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
   bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
                                  const unsigned SIOpd);
 
+  /// Try to replace instruction \p I with value \p V which are pointers
+  /// in different address space.
+  /// \return true if successful.
+  bool replacePointer(Instruction &I, Value *V);
+
 private:
   bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
   bool shouldChangeType(Type *From, Type *To) const;
   Value *dyn_castNegVal(Value *V) const;
   Value *dyn_castFNegVal(Value *V, bool NoSignedZero = false) const;
   Type *FindElementAtOffset(PointerType *PtrTy, int64_t Offset,
                             SmallVectorImpl<Value *> &NewIndices);
 

llvm/trunk/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

 //===- InstCombineLoadStoreAlloca.cpp -------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the visit functions for load, store and alloca.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InstCombineInternal.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugInfo.h"
-#include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "instcombine"
 
 STATISTIC(NumDeadStore,    "Number of dead stores eliminated");
if (AI.getArraySize()->getType() != IntPtrTy) {
     Value *V = IC.Builder->CreateIntCast(AI.getArraySize(), IntPtrTy, false);
     AI.setOperand(0, V);
     return &AI;
   }
 
   return nullptr;
 }
 
+// If I and V are pointers in different address space, it is not allowed to
+// use replaceAllUsesWith since I and V have different types. A
+// non-target-specific transformation should not use addrspacecast on V since
+// the two address space may be disjoint depending on target.
+//
+// This class chases down uses of the old pointer until reaching the load
+// instructions, then replaces the old pointer in the load instructions with
+// the new pointer. If during the chasing it sees bitcast or GEP, it will
+// create new bitcast or GEP with the new pointer and use them in the load
+// instruction.
+class PointerReplacer {
+public:
+  PointerReplacer(InstCombiner &IC) : IC(IC) {}
+  void replacePointer(Instruction &I, Value *V);
+
+private:
+  void findLoadAndReplace(Instruction &I);
+  void replace(Instruction *I);
+  Value *getReplacement(Value *I);
+
+  SmallVector<Instruction *, 4> Path;
+  MapVector<Value *, Value *> WorkMap;
+  InstCombiner &IC;
+};
+
+void PointerReplacer::findLoadAndReplace(Instruction &I) {
+  for (auto U : I.users()) {
+    auto *Inst = dyn_cast<Instruction>(&*U);
+    if (!Inst)
+      return;
+    DEBUG(dbgs() << "Found pointer user: " << *U << '\n');
+    if (isa<LoadInst>(Inst)) {
+      for (auto P : Path)
+        replace(P);
+      replace(Inst);
+    } else if (isa<GetElementPtrInst>(Inst) || isa<BitCastInst>(Inst)) {
+      Path.push_back(Inst);
+      findLoadAndReplace(*Inst);
+      Path.pop_back();
+    } else {
+      return;
+    }
+  }
+}
+
+Value *PointerReplacer::getReplacement(Value *V) {
+  auto Loc = WorkMap.find(V);
+  if (Loc != WorkMap.end())
+    return Loc->second;
+  return nullptr;
+}
+
+void PointerReplacer::replace(Instruction *I) {
+  if (getReplacement(I))
+    return;
+
+  if (auto *LT = dyn_cast<LoadInst>(I)) {
+    auto *V = getReplacement(LT->getPointerOperand());
+    assert(V && "Operand not replaced");
+    auto *NewI = new LoadInst(V);
+    NewI->takeName(LT);
+    IC.InsertNewInstWith(NewI, *LT);
+    IC.replaceInstUsesWith(*LT, NewI);
+    WorkMap[LT] = NewI;
+  } else if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
+    auto *V = getReplacement(GEP->getPointerOperand());
+    assert(V && "Operand not replaced");
+    SmallVector<Value *, 8> Indices;
+    Indices.append(GEP->idx_begin(), GEP->idx_end());
+    auto *NewI = GetElementPtrInst::Create(
+        V->getType()->getPointerElementType(), V, Indices);
+    IC.InsertNewInstWith(NewI, *GEP);
+    NewI->takeName(GEP);
+    WorkMap[GEP] = NewI;
+  } else if (auto *BC = dyn_cast<BitCastInst>(I)) {
+    auto *V = getReplacement(BC->getOperand(0));
+    assert(V && "Operand not replaced");
+    auto *NewT = PointerType::get(BC->getType()->getPointerElementType(),
+                                  V->getType()->getPointerAddressSpace());
+    auto *NewI = new BitCastInst(V, NewT);
+    IC.InsertNewInstWith(NewI, *BC);
+    NewI->takeName(BC);
+    WorkMap[GEP] = NewI;
+  } else {
+    llvm_unreachable("should never reach here");
+  }
+}
+
+void PointerReplacer::replacePointer(Instruction &I, Value *V) {
+  auto *PT = cast<PointerType>(I.getType());
+  auto *NT = cast<PointerType>(V->getType());
+  assert(PT != NT && PT->getElementType() == NT->getElementType() &&
+         "Invalid usage");
+  WorkMap[&I] = V;
+  findLoadAndReplace(I);
+}
+
 Instruction *InstCombiner::visitAllocaInst(AllocaInst &AI) {
   if (auto *I = simplifyAllocaArraySize(*this, AI))
     return I;
 
   if (AI.getAllocatedType()->isSized()) {
     // If the alignment is 0 (unspecified), assign it the preferred alignment.
     if (AI.getAlignment() == 0)
       AI.setAlignment(DL.getPrefTypeAlignment(AI.getAllocatedType()));
if (MemTransferInst *Copy = isOnlyCopiedFromConstantGlobal(&AI, ToDelete)) {
       unsigned SourceAlign = getOrEnforceKnownAlignment(
           Copy->getSource(), AI.getAlignment(), DL, &AI, &AC, &DT);
       if (AI.getAlignment() <= SourceAlign) {
         DEBUG(dbgs() << "Found alloca equal to global: " << AI << '\n');
         DEBUG(dbgs() << "  memcpy = " << *Copy << '\n');
         for (unsigned i = 0, e = ToDelete.size(); i != e; ++i)
           eraseInstFromFunction(*ToDelete[i]);
         Constant *TheSrc = cast<Constant>(Copy->getSource());
-        Constant *Cast
-          = ConstantExpr::getPointerBitCastOrAddrSpaceCast(TheSrc, AI.getType());
+        auto *SrcTy = TheSrc->getType();
+        auto *DestTy = PointerType::get(AI.getType()->getPointerElementType(),
+                                        SrcTy->getPointerAddressSpace());
+        Constant *Cast =
+            ConstantExpr::getPointerBitCastOrAddrSpaceCast(TheSrc, DestTy);
+        if (AI.getType()->getPointerAddressSpace() ==
+            SrcTy->getPointerAddressSpace()) {
           Instruction *NewI = replaceInstUsesWith(AI, Cast);
           eraseInstFromFunction(*Copy);
           ++NumGlobalCopies;
           return NewI;
+        } else {
+          PointerReplacer PtrReplacer(*this);
+          PtrReplacer.replacePointer(AI, Cast);
+          ++NumGlobalCopies;
+        }
       }
     }
   }
 
   // At last, use the generic allocation site handler to aggressively remove
   // unused allocas.
   return visitAllocSite(AI);
 }

llvm/trunk/test/Transforms/InstCombine/memcpy-addrspace.ll

+; RUN: opt < %s -instcombine -S | FileCheck %s
+
[e-mail] = private unnamed_addr addrspace(2) constant [8 x i32] [i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7], align 4
+
+; CHECK-LABEL: test_load
+; CHECK: %[[GEP:.*]] = getelementptr [8 x i32], [8 x i32] addrspace(2)* @test.data, i64 0, i64 %x
+; CHECK: %{{.*}} = load i32, i32 addrspace(2)* %[[GEP]]
+; CHECK-NOT: alloca
+; CHECK-NOT: call void @llvm.memcpy.p0i8.p2i8.i64
+; CHECK-NOT: addrspacecast
+; CHECK-NOT: load i32, i32*
+define void @test_load(i32 addrspace(1)* %out, i64 %x) {
+entry:
+  %data = alloca [8 x i32], align 4
+  %0 = bitcast [8 x i32]* %data to i8*
+  call void @llvm.memcpy.p0i8.p2i8.i64(i8* %0, i8 addrspace(2)* bitcast ([8 x i32] addrspace(2)* @test.data to i8 addrspace(2)*), i64 32, i32 4, i1 false)
+  %arrayidx = getelementptr inbounds [8 x i32], [8 x i32]* %data, i64 0, i64 %x
+  %1 = load i32, i32* %arrayidx, align 4
+  %arrayidx1 = getelementptr inbounds i32, i32 addrspace(1)* %out, i64 %x
+  store i32 %1, i32 addrspace(1)* %arrayidx1, align 4
+  ret void
+}
+
+; CHECK-LABEL: test_call
+; CHECK: alloca
+; CHECK: call void @llvm.memcpy.p0i8.p2i8.i64
+; CHECK-NOT: addrspacecast
+; CHECK: call i32 @foo(i32* %{{.*}})
+define void @test_call(i32 addrspace(1)* %out, i64 %x) {
+entry:
+  %data = alloca [8 x i32], align 4
+  %0 = bitcast [8 x i32]* %data to i8*
+  call void @llvm.memcpy.p0i8.p2i8.i64(i8* %0, i8 addrspace(2)* bitcast ([8 x i32] addrspace(2)* @test.data to i8 addrspace(2)*), i64 32, i32 4, i1 false)
+  %arrayidx = getelementptr inbounds [8 x i32], [8 x i32]* %data, i64 0, i64 %x
+  %1 = call i32 @foo(i32* %arrayidx)
+  %arrayidx1 = getelementptr inbounds i32, i32 addrspace(1)* %out, i64 %x
+  store i32 %1, i32 addrspace(1)* %arrayidx1, align 4
+  ret void
+}
+
+; CHECK-LABEL: test_load_and_call
+; CHECK: alloca
+; CHECK: call void @llvm.memcpy.p0i8.p2i8.i64
+; CHECK: load i32, i32* %{{.*}}
+; CHECK: call i32 @foo(i32* %{{.*}})
+; CHECK-NOT: addrspacecast
+; CHECK-NOT: load i32, i32 addrspace(2)*
+define void @test_load_and_call(i32 addrspace(1)* %out, i64 %x, i64 %y) {
+entry:
+  %data = alloca [8 x i32], align 4
+  %0 = bitcast [8 x i32]* %data to i8*
+  call void @llvm.memcpy.p0i8.p2i8.i64(i8* %0, i8 addrspace(2)* bitcast ([8 x i32] addrspace(2)* @test.data to i8 addrspace(2)*), i64 32, i32 4, i1 false)
+  %arrayidx = getelementptr inbounds [8 x i32], [8 x i32]* %data, i64 0, i64 %x
+  %1 = load i32, i32* %arrayidx, align 4
+  %arrayidx1 = getelementptr inbounds i32, i32 addrspace(1)* %out, i64 %x
+  store i32 %1, i32 addrspace(1)* %arrayidx1, align 4
+  %2 = call i32 @foo(i32* %arrayidx)
+  %arrayidx2 = getelementptr inbounds i32, i32 addrspace(1)* %out, i64 %y
+  store i32 %2, i32 addrspace(1)* %arrayidx2, align 4
+  ret void
+}
+
+
+declare void @llvm.memcpy.p0i8.p2i8.i64(i8* nocapture writeonly, i8 addrspace(2)* nocapture readonly, i64, i32, i1)
+declare i32 @foo(i32* %x)