[GlobalOpt] support ConstantExpr use of global address for OptimizeGlobalAddressOfMalloc

[scui]

Summary

I'm working on extending the OptimizeGlobalAddressOfMalloc to handle some more general cases. This is to add support of the ConstantExpr use of the global variables. The function allUsesOfLoadedValueWillTrapIfNull is now iterative with the added CE use of GV. Also, the recursive function valueIsOnlyUsedLocallyOrStoredToOneGlobal is changed to iterative using a worklist with the GEP case added.

[efriedma]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

737

I don't think you can just look past all ConstantExprs here? Maybe dyn_cast<GEPOperator>(U)?

983–987

Not sure why you're changing the pattern used here. It's a lot easier to show the while (!GV->use_empty()) { loop works correctly.

1079

VUse.getOperandNo() == 0?

[scui]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

737

You are right. Will change this to only consider bitcast and gep.

983–987

I prefer to use for loops as we need add additional code to handle CE uses, but I can change back to use while loop, and add some code to remove those CE uses to ensure the loop runs correctly.

1079

Thanks for the suggestion. This is the original code as it is, I can change it as you suggested - but looks to me no difference as SI is available.

[efriedma]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

983–987

In general, I don't like the early-increment pattern on constants because it's easy to mess up if constant expressions are involved.

1079

The SI->getOperand(1)->stripPointerCasts() != GV seems very suspicious to me; I don't understand why we want to special-case storing the address of a global to itself.

For the SI->getOperand(0) == V part, I guess it doesn't really matter.

[scui]

This is to address comments: (1) limit the case for ConstantExpr to only bitcast and gep in allUsesOfLoadedValueWillTrapIfNull, (2) change back using while loop to traverse uses of GV in OptimizeGlobalAddressOfMalloc

[scui]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

1079

I think this is to make sure the malloc site for GV is only for GV.

[efriedma]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

738

I'm not sure constant folding ensures that CE->stripPointerCasts() looks through exactly one pointer cast?

997

A constant can have more than one use?

1079

In case it wasn't clear, I meant, "For the SI->getOperand(0) == V part, I guess it doesn't really matter how you write it. SI->getOperand(0) == V is essentially equivalent to VUse.getOperandNo() == 0."

I don't follow your explanation for the SI->getOperand(1)->stripPointerCasts() != GV part; can you describe it in a bit more detail?

[scui]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

738

Yes, Should be if (CE->stripPointerCasts() != V).

997

Good point. Will rewrite the code to consider multiple uses of ConstantExpr.

1079

V is from malloc. For stores, V can be used in the following 3 forms:

1. store x, V
2. store V, GV
3. store V, not-GV

Case 1 is ok, as it stores through it. Case 2 is the one we care about - store to GV - we are trying to optimize this kind of malloc calls. This check is for case 3 - the malloc value is also stored to memory other than GV - simply return false, as there is no further code currently to handle this for safe transformation.

[scui]

This is to address comments: (1) fix for the ConstantExpr case in allUsesOfLoadedValueWillTrapIfNull, (2) Consider multiple uses of ConstantExpr for the loop to traverse uses of GV in OptimizeGlobalAddressOfMalloc. The load/store uses are collected in a set first and then loop over the set.

[efriedma]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

735

Instead of SI->getPointerOperand() != P, should be SI->getValueOperand() == P?

1079

Oh... right. Makes sense.

llvm/lib/Transforms/Utils/GlobalStatus.cpp

111

Is this going to affect other transforms that use the result of analyzeGlobalAux?

[scui]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

735

SI->getPointerOperand() != P is alright. It's ok to store into global (actually the StoredOnce).

llvm/lib/Transforms/Utils/GlobalStatus.cpp

111

I only see one user of GlobalStatus - that is processGlobal in GlobalOpt.cpp. I checked all the transformations under this function. Other than tryToOptimizeStoreOfMallocToGlobal, this added code should be ok for all other transformations, either ConstantExpr is handled already or bailout early if there is any use of ConstantExpr. There is only one to bailout early - TryToShrinkGlobalToBoolean - I'll leave this as it is for now as I don't see any real case for this with ConstantExpr.

[efriedma]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

735

My concern is that with opaque pointers, it will become possible to write something like store ptr @g, ptr @g, at which point the difference between SI->getPointerOperand() != P and SI->getValueOperand() == P will start to matter.

llvm/lib/Transforms/Utils/GlobalStatus.cpp

111

Okay, thanks for checking.

[scui]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

735

When this function is called, we know there is only one store to the global, and it is from malloc. There are no other stores to the global. So we don't need to worry about "store @g @g".

[efriedma]

LGTM

llvm/lib/Transforms/IPO/GlobalOpt.cpp

735

Okay, I guess.

[bjope]

This input might look weird, but I don't think the pass should hit an assert anyway, which it does with this patch:

; RUN: opt < %s -passes='globalopt' -S | FileCheck %s

@a162 = internal global i16* null, align 1

define void @f363() {
entry:
  %0 = load i16*, i16** @a162, align 1
  store i16 0, i16* bitcast (i16** @a162 to i16*), align 1
  ret void
}

I get

opt: ../lib/IR/Constants.cpp:2224: static llvm::Constant *llvm::ConstantExpr::getBitCast(llvm::Constant *, llvm::Type *, bool): Assertion `CastInst::castIsValid(Instruction::BitCast, C, DstTy) && "Invalid constantexpr bitcast!"' failed.

in

#9 0x00000000023e5478 processInternalGlobal(llvm::GlobalVariable*, llvm::GlobalStatus const&, llvm::function_ref<llvm::TargetLibraryInfo& (llvm::Function&)>, llvm::function_ref<llvm::DominatorTree& (llvm::Function&)>) GlobalOpt.cpp:0:0
#10 0x00000000023e4438 processGlobal(llvm::GlobalValue&, llvm::function_ref<llvm::TargetLibraryInfo& (llvm::Function&)>, llvm::function_ref<llvm::DominatorTree& (llvm::Function&)>) GlobalOpt.cpp:0:0
#11 0x00000000023e2394 optimizeGlobalsInModule(llvm::Module&, llvm::DataLayout const&, llvm::function_ref<llvm::TargetLibraryInfo& (llvm::Function&)>, llvm::function_ref<llvm::TargetTransformInfo& (llvm::Function&)>, llvm::function_ref<llvm::BlockFrequencyInfo& (llvm::Function&)>, llvm::function_ref<llvm::DominatorTree& (llvm::Function&)>) GlobalOpt.cpp:0:0
#12 0x00000000023e08ce llvm::GlobalOptPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&)

[saugustine]

This patch caused the following error for me:

error: Explicit load/store type does not match pointee type of pointer operand (Producer: 'LLVMgoogle3-trunk' Reader: 'LLVM google3-trunk')

Unfortunately, the error gives no source-code line and the input file is giant and highly optimized. The fix in D10730 doesn't help.

I'm working on a reduced test case, but it might take a while. If the error sparks any ideas, it would be good to hear them.

[scui]

In D106589#2920763, @saugustine wrote:

This patch caused the following error for me:

error: Explicit load/store type does not match pointee type of pointer operand (Producer: 'LLVMgoogle3-trunk' Reader: 'LLVM google3-trunk')

I'm working on a reduced test case, but it might take a while. If the error sparks any ideas, it would be good to hear them.

Thanks for your information and working on a reduced test case. I'm not sure what the problem is, I'll go through the code (transformation part) a little bit more to see if there is anything suspicious. But it would be great if you could provide a reduced case.

[asbirlea]

It looks like this patch introduced an assertion in GlobalOpt.
I filed a bug with reproducer here: https://bugs.llvm.org/show_bug.cgi?id=51608
Could you please take a look?

llvm/lib/Transforms/IPO/GlobalOpt.cpp

for (const User *U : V->users()) {
     }
   }
   return true;
 }
 
 /// Return true if all uses of any loads from GV will trap if the loaded value
 /// is null.  Note that this also permits comparisons of the loaded value
 /// against null, as a special case.
-static bool AllUsesOfLoadedValueWillTrapIfNull(const GlobalVariable *GV) {
-  for (const User *U : GV->users())
-    if (const LoadInst *LI = dyn_cast<LoadInst>(U)) {
-      SmallPtrSet<const PHINode*, 8> PHIs;
+static bool allUsesOfLoadedValueWillTrapIfNull(const GlobalVariable *GV) {
+  SmallVector<const Value *, 4> Worklist;
+  Worklist.push_back(GV);
+  while (!Worklist.empty()) {
+    const Value *P = Worklist.pop_back_val();
+    for (auto *U : P->users()) {
+      if (auto *LI = dyn_cast<LoadInst>(U)) {
+        SmallPtrSet<const PHINode *, 8> PHIs;
         if (!AllUsesOfValueWillTrapIfNull(LI, PHIs))
           return false;
-    } else if (isa<StoreInst>(U)) {
+      } else if (auto *SI = dyn_cast<StoreInst>(U)) {
         // Ignore stores to the global.
+        if (SI->getPointerOperand() != P)
+          return false;
+      } else if (auto *CE = dyn_cast<ConstantExpr>(U)) {
+        if (CE->stripPointerCasts() != GV)
+          return false;
+        // Check further the ConstantExpr.
+        Worklist.push_back(CE);
       } else {
         // We don't know or understand this user, bail out.
-      //cerr << "UNKNOWN USER OF GLOBAL!: " << *U;
         return false;
       }
+    }
+  }
+
   return true;
 }
 
+/// Get all the loads/store uses for global variable \p GV.
+static void allUsesOfLoadAndStores(GlobalVariable *GV,
+                                   SmallVector<Value *, 4> &Uses) {
+  SmallVector<Value *, 4> Worklist;
+  Worklist.push_back(GV);
+  while (!Worklist.empty()) {
+    auto *P = Worklist.pop_back_val();
+    for (auto *U : P->users()) {
+      if (auto *CE = dyn_cast<ConstantExpr>(U)) {
+        Worklist.push_back(CE);
+        continue;
+      }
+
+      assert((isa<LoadInst>(U) || isa<StoreInst>(U)) &&
+             "Expect only load or store instructions");
+      Uses.push_back(U);
+    }
+  }
+}
+
 static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) {
   bool Changed = false;
   for (auto UI = V->user_begin(), E = V->user_end(); UI != E; ) {
     Instruction *I = cast<Instruction>(*UI++);
     // Uses are non-trapping if null pointer is considered valid.
     // Non address-space 0 globals are already pruned by the caller.
     if (NullPointerIsDefined(I->getFunction()))
       return false;
OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, CallInst *CI, Type *AllocTy,
   // keep track of whether the global was initialized yet or not.
   GlobalVariable *InitBool =
     new GlobalVariable(Type::getInt1Ty(GV->getContext()), false,
                        GlobalValue::InternalLinkage,
                        ConstantInt::getFalse(GV->getContext()),
                        GV->getName()+".init", GV->getThreadLocalMode());
   bool InitBoolUsed = false;
 
-  // Loop over all uses of GV, processing them in turn.
-  while (!GV->use_empty()) {
-    if (StoreInst *SI = dyn_cast<StoreInst>(GV->user_back())) {
+  // Loop over all instruction uses of GV, processing them in turn.
+  SmallVector<Value *, 4> Guses;
+  allUsesOfLoadAndStores(GV, Guses);
+  for (auto *U : Guses) {
+    if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
       // The global is initialized when the store to it occurs. If the stored
       // value is null value, the global bool is set to false, otherwise true.
       new StoreInst(ConstantInt::getBool(
                         GV->getContext(),
                         !isa<ConstantPointerNull>(SI->getValueOperand())),
                     InitBool, false, Align(1), SI->getOrdering(),
                     SI->getSyncScopeID(), SI);
       SI->eraseFromParent();
       continue;
     }
 
-    LoadInst *LI = cast<LoadInst>(GV->user_back());
+    LoadInst *LI = cast<LoadInst>(U);
     while (!LI->use_empty()) {
       Use &LoadUse = *LI->use_begin();
       ICmpInst *ICI = dyn_cast<ICmpInst>(LoadUse.getUser());
       if (!ICI) {
         LoadUse = RepValue;
         continue;
       }
 
OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, CallInst *CI, Type *AllocTy,
   // indices into GEP constant-exprs, which will allow global-opt to hack on it.
   ConstantPropUsersOf(NewGV, DL, TLI);
   if (RepValue != NewGV)
     ConstantPropUsersOf(RepValue, DL, TLI);
 
   return NewGV;
 }
 
-/// Scan the use-list of V checking to make sure that there are no complex uses
-/// of V.  We permit simple things like dereferencing the pointer, but not
+/// Scan the use-list of GV checking to make sure that there are no complex uses
+/// of GV.  We permit simple things like dereferencing the pointer, but not
 /// storing through the address, unless it is to the specified global.
 static bool
-valueIsOnlyUsedLocallyOrStoredToOneGlobal(const Instruction *V,
+valueIsOnlyUsedLocallyOrStoredToOneGlobal(const CallInst *CI,
                                           const GlobalVariable *GV) {
-  for (const User *U : V->users()) {
-    const Instruction *Inst = cast<Instruction>(U);
+  SmallPtrSet<const Value *, 4> Visited;
+  SmallVector<const Value *, 4> Worklist;
+  Worklist.push_back(CI);
+
+  while (!Worklist.empty()) {
+    const Value *V = Worklist.pop_back_val();
+    if (!Visited.insert(V).second)
+      continue;
 
-    if (isa<LoadInst>(Inst) || isa<CmpInst>(Inst)) {
+    for (const Use &VUse : V->uses()) {
+      const User *U = VUse.getUser();
+      if (isa<LoadInst>(U) || isa<CmpInst>(U))
         continue; // Fine, ignore.
-    }
 
-    if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
-      if (SI->getOperand(0) == V && SI->getOperand(1) != GV)
-        return false;  // Storing the pointer itself... bad.
+      if (auto *SI = dyn_cast<StoreInst>(U)) {
+        if (SI->getValueOperand() == V &&
+            SI->getPointerOperand()->stripPointerCasts() != GV)
+          return false; // Storing the pointer not into GV... bad.
         continue; // Otherwise, storing through it, or storing into GV... fine.
       }
 
-    if (const BitCastInst *BCI = dyn_cast<BitCastInst>(Inst)) {
-      if (!valueIsOnlyUsedLocallyOrStoredToOneGlobal(BCI, GV))
-        return false;
+      if (auto *BCI = dyn_cast<BitCastInst>(U)) {
+        Worklist.push_back(BCI);
+        continue;
+      }
+
+      if (auto *GEPI = dyn_cast<GetElementPtrInst>(U)) {
+        Worklist.push_back(GEPI);
         continue;
       }
 
       return false;
     }
+  }
+
   return true;
 }
 
 /// This function is called when we see a pointer global variable with a single
 /// value stored it that is a malloc or cast of malloc.
 static bool tryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV, CallInst *CI,
                                                Type *AllocTy,
                                                AtomicOrdering Ordering,
                                                const DataLayout &DL,
                                                TargetLibraryInfo *TLI) {
   // If this is a malloc of an abstract type, don't touch it.
   if (!AllocTy->isSized())
     return false;
 
   // We can't optimize this global unless all uses of it are *known* to be
   // of the malloc value, not of the null initializer value (consider a use
   // that compares the global's value against zero to see if the malloc has
   // been reached).  To do this, we check to see if all uses of the global
   // would trap if the global were null: this proves that they must all
   // happen after the malloc.
-  if (!AllUsesOfLoadedValueWillTrapIfNull(GV))
+  if (!allUsesOfLoadedValueWillTrapIfNull(GV))
     return false;
 
   // We can't optimize this if the malloc itself is used in a complex way,
   // for example, being stored into multiple globals.  This allows the
-  // malloc to be stored into the specified global, loaded icmp'd.
+  // malloc to be stored into the specified global, loaded, gep, icmp'd.
   // These are all things we could transform to using the global for.
   if (!valueIsOnlyUsedLocallyOrStoredToOneGlobal(CI, GV))
     return false;
 
   // If we have a global that is only initialized with a fixed size malloc,
   // transform the program to use global memory instead of malloc'd memory.
   // This eliminates dynamic allocation, avoids an indirection accessing the
   // data, and exposes the resultant global to further GlobalOpt.

llvm/lib/Transforms/Utils/GlobalStatus.cpp

if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(UR)) {
           return true;
 
         GS.Ordering = strongerOrdering(GS.Ordering, SI->getOrdering());
 
         // If this is a direct store to the global (i.e., the global is a scalar
         // value, not an aggregate), keep more specific information about
         // stores.
         if (GS.StoredType != GlobalStatus::Stored) {
-          if (const GlobalVariable *GV =
-                  dyn_cast<GlobalVariable>(SI->getOperand(1))) {
+          const Value *Ptr = SI->getPointerOperand();
+          if (isa<ConstantExpr>(Ptr))
+            Ptr = Ptr->stripPointerCasts();
+          if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
             Value *StoredVal = SI->getOperand(0);
 
             if (Constant *C = dyn_cast<Constant>(StoredVal)) {
               if (C->isThreadDependent()) {
                 // The stored value changes between threads; don't track it.
                 return true;
               }
             }

llvm/test/Transforms/GlobalOpt/new-promote.ll

+; RUN: opt -globalopt -S < %s | FileCheck %s
+; RUN: opt -passes=globalopt -S < %s | FileCheck %s
+
+%s = type { i32 }
+@g = internal global %s* null, align 8
+
+; Test code pattern for:
+;   class s { int a; s() { a = 1;} };
+;   g = new s();
+;
+
+define internal void @f() {
+; CHECK-LABEL: @f(
+; CHECK-NEXT:    ret void
+;
+  %1 = tail call i8* @_Znwm(i64 4)
+  %2 = bitcast i8* %1 to %s*
+  %3 = getelementptr inbounds %s, %s* %2, i64 0, i32 0
+  store i32 1, i32* %3, align 4
+  store i8* %1, i8** bitcast (%s** @g to i8**), align 8
+  ret void
+}
+
+define dso_local signext i32 @main() {
+; CHECK-LABEL: @main(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call fastcc void @f()
+; CHECK-NEXT:    ret i32 1
+;
+entry:
+  call void @f()
+  %0 = load %s*, %s** @g, align 4
+  %1 = getelementptr inbounds %s, %s* %0, i64 0, i32 0
+  %2 = load i32, i32* %1, align 4
+  ret i32 %2
+}
+
+declare nonnull i8* @_Znwm(i64)
+
+declare signext i32 @printf(i8*, ...)
+