[GlobalOpt] Extend CleanupPointerRootUsers to handle CE users.

[fhahn]

Summary

Extend CleanupPointerRootUsers to iterate over a worklist, add users of
constant expressions to the worklist to enable additional cleanups.

[nikic]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

247

Do we know that the users here are only cast/GEP?

[fhahn]

Rebase on top of c34936465c5648f825414fe76ccad7a9ad82dddd which adds a test with non GEP constant expressions.

Also update ThinLTO test.

[fhahn]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

247

It could be any constant expression, but would that be a problem? I think the existing code should handle any type of constant expressions already. I added some extra tests with different constant expressions in c34936465c56 and 7f51145b1bc2

[nikic]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

247

To give a silly example store i32 0, ptr inttoptr (i64 add (i64 ptrtoint ptr @g to i64, i64 100)) to ptr) could be writing to a different underlying object (without UB if certain conditions are met).

[fhahn]

Limit to GEPOperator CEs for now.

[fhahn]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

247

At the moment, earlier global analysis will fail if we encounter such constant expressions, but it is probably safest to just limit things to GEPOperator constant expressions here for now to avoid potentially breaking things in the future if the analysis may change. Updated the patch and also removed the Visited set which shouldn't be needed with the restricted version.

[nikic]

LGTM

[uabelho]

Hi,

The followiong starts crashing with this patch:

opt -passes="globalopt" bbi-80589.ll -o /dev/null

I get

opt: ../include/llvm/Support/Casting.h:708: auto llvm::cast_if_present(Y *) [X = llvm::Constant, Y = llvm::Value]: Assertion `isa<X>(Val) && "cast_if_present<Ty>() argument of incompatible type!"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.	Program arguments: ../../main-github/llvm/build-all/bin/opt -passes=globalopt bbi-80589.ll -o /dev/null
 #0 0x0000000002e62f98 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (../../main-github/llvm/build-all/bin/opt+0x2e62f98)
 #1 0x0000000002e60b2e llvm::sys::RunSignalHandlers() (../../main-github/llvm/build-all/bin/opt+0x2e60b2e)
 #2 0x0000000002e63616 SignalHandler(int) Signals.cpp:0:0
 #3 0x00007f4e70ae7630 __restore_rt sigaction.c:0:0
 #4 0x00007f4e6e22e387 raise (/lib64/libc.so.6+0x36387)
 #5 0x00007f4e6e22fa78 abort (/lib64/libc.so.6+0x37a78)
 #6 0x00007f4e6e2271a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6)
 #7 0x00007f4e6e227252 (/lib64/libc.so.6+0x2f252)
 #8 0x00000000026aac05 llvm::ConstantExprKeyType::ConstantExprKeyType(llvm::ConstantExpr const*, llvm::SmallVectorImpl<llvm::Constant*>&) crtstuff.c:0:0
 #9 0x00000000026aa90e llvm::ConstantUniqueMap<llvm::ConstantExpr>::MapInfo::getHashValue(llvm::ConstantExpr const*) crtstuff.c:0:0
#10 0x000000000269e6b5 llvm::ConstantUniqueMap<llvm::ConstantExpr>::remove(llvm::ConstantExpr*) crtstuff.c:0:0
#11 0x0000000002690340 llvm::Constant::destroyConstant() (../../main-github/llvm/build-all/bin/opt+0x2690340)
#12 0x000000000316fc59 CleanupPointerRootUsers(llvm::GlobalVariable*, llvm::function_ref<llvm::TargetLibraryInfo& (llvm::Function&)>) GlobalOpt.cpp:0:0
#13 0x000000000316a12a processInternalGlobal(llvm::GlobalVariable*, llvm::GlobalStatus const&, llvm::function_ref<llvm::TargetTransformInfo& (llvm::Function&)>, llvm::function_ref<llvm::TargetLibraryInfo& (llvm::Function&)>, llvm::function_ref<llvm::DominatorTree& (llvm::Function&)>) GlobalOpt.cpp:0:0
#14 0x0000000003169a7d processGlobal(llvm::GlobalValue&, llvm::function_ref<llvm::TargetTransformInfo& (llvm::Function&)>, llvm::function_ref<llvm::TargetLibraryInfo& (llvm::Function&)>, llvm::function_ref<llvm::DominatorTree& (llvm::Function&)>) GlobalOpt.cpp:0:0
#15 0x0000000003167aca 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&)>, llvm::function_ref<void (llvm::Function&)>, llvm::function_ref<void (llvm::Function&)>) GlobalOpt.cpp:0:0
#16 0x0000000003165c82 llvm::GlobalOptPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../main-github/llvm/build-all/bin/opt+0x3165c82)
#17 0x00000000030815fd llvm::detail::PassModel<llvm::Module, llvm::GlobalOptPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) crtstuff.c:0:0
#18 0x00000000027d75db llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../main-github/llvm/build-all/bin/opt+0x27d75db)
#19 0x000000000073b8b3 llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool) (../../main-github/llvm/build-all/bin/opt+0x73b8b3)
#20 0x0000000000749eb2 main (../../main-github/llvm/build-all/bin/opt+0x749eb2)
#21 0x00007f4e6e21a555 __libc_start_main (/lib64/libc.so.6+0x22555)
#22 0x0000000000734b10 _start (../../main-github/llvm/build-all/bin/opt+0x734b10)
Abort (core dumped)

The original unreduced reproducer randomly crashed this way and sometimes it instead hit

opt: ../lib/IR/ConstantsContext.h:616: void llvm::ConstantUniqueMap<llvm::ConstantExpr>::remove(ConstantClass *) [ConstantClass = llvm::ConstantExpr]: Assertion `I != Map.end() && "Constant not found in constant table!"' failed.

so I'm not sure if there is something more lurking here.

bbi-80589.ll960 BDownload

[uabelho]

I wrote https://github.com/llvm/llvm-project/issues/61674 about the crash.

llvm/lib/Transforms/IPO/GlobalOpt.cpp

CleanupPointerRootUsers(GlobalVariable *GV,
   // destroy it.
 
   bool Changed = false;
 
   // If Dead[n].first is the only use of a malloc result, we can delete its
   // chain of computation and the store to the global in Dead[n].second.
   SmallVector<std::pair<Instruction *, Instruction *>, 32> Dead;
 
+  SmallVector<User *> Worklist(GV->users());
+  SmallPtrSet<User *, 8> Seen;
   // Constants can't be pointers to dynamically allocated memory.
-  for (User *U : llvm::make_early_inc_range(GV->users())) {
+  while (!Worklist.empty()) {
+    User *U = Worklist.pop_back_val();
+    if (!Seen.insert(U).second)
+      continue;
     if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
       Value *V = SI->getValueOperand();
       if (isa<Constant>(V)) {
         Changed = true;
         SI->eraseFromParent();
       } else if (Instruction *I = dyn_cast<Instruction>(V)) {
         if (I->hasOneUse())
           Dead.push_back(std::make_pair(I, SI));
if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
       } else if (Instruction *I = dyn_cast<Instruction>(MTI->getSource())) {
         if (I->hasOneUse())
           Dead.push_back(std::make_pair(I, MTI));
       }
     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
       if (CE->use_empty()) {
         CE->destroyConstant();
         Changed = true;
-      }
+      } else
+        append_range(Worklist, CE->users());
     } else if (Constant *C = dyn_cast<Constant>(U)) {
       if (isSafeToDestroyConstant(C)) {
         C->destroyConstant();
         // This could have invalidated UI, start over from scratch.
         Dead.clear();
         CleanupPointerRootUsers(GV, GetTLI);
         return true;
       }

llvm/test/Transforms/GlobalOpt/cleanup-pointer-root-users-gep-constexpr.ll

 
 declare i32 @fn2()
 
 declare i32 @fn3()
 
 define void @stores_single_use_gep_constexpr() {
 ; CHECK-LABEL: @stores_single_use_gep_constexpr(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    store ptr @fn1, ptr getelementptr inbounds ([[STRUCT_GLOBAL_20PTR:%.*]], ptr @global.20ptr, i64 0, i32 1), align 8
-; CHECK-NEXT:    store ptr @fn2, ptr getelementptr inbounds ([[STRUCT_GLOBAL_20PTR]], ptr @global.20ptr, i64 0, i32 2), align 8
-; CHECK-NEXT:    store ptr @fn3, ptr getelementptr inbounds ([[STRUCT_GLOBAL_20PTR]], ptr @global.20ptr, i64 0, i32 3), align 8
-; CHECK-NEXT:    store ptr @fn0, ptr getelementptr inbounds ([[STRUCT_GLOBAL_20PTR]], ptr @global.20ptr, i64 0, i32 4), align 8
-; CHECK-NEXT:    store ptr @fn1, ptr getelementptr inbounds ([[STRUCT_GLOBAL_20PTR]], ptr @global.20ptr, i64 0, i32 5), align 8
-; CHECK-NEXT:    store ptr @fn2, ptr getelementptr inbounds ([[STRUCT_GLOBAL_20PTR]], ptr @global.20ptr, i64 0, i32 6), align 8
-; CHECK-NEXT:    store ptr @fn3, ptr getelementptr inbounds ([[STRUCT_GLOBAL_20PTR]], ptr @global.20ptr, i64 0, i32 7), align 8
-; CHECK-NEXT:    store ptr @fn0, ptr getelementptr inbounds ([[STRUCT_GLOBAL_20PTR]], ptr @global.20ptr, i64 0, i32 8), align 8
-; CHECK-NEXT:    store ptr @fn1, ptr getelementptr inbounds ([[STRUCT_GLOBAL_20PTR]], ptr @global.20ptr, i64 0, i32 9), align 8
-; CHECK-NEXT:    store ptr @fn2, ptr getelementptr inbounds ([[STRUCT_GLOBAL_20PTR]], ptr @global.20ptr, i64 0, i32 10), align 8
-; CHECK-NEXT:    store ptr @fn3, ptr getelementptr inbounds ([[STRUCT_GLOBAL_20PTR]], ptr @global.20ptr, i64 0, i32 11), align 8
-; CHECK-NEXT:    store ptr @fn0, ptr getelementptr inbounds ([[STRUCT_GLOBAL_20PTR]], ptr @global.20ptr, i64 0, i32 12), align 8
-; CHECK-NEXT:    store ptr @fn1, ptr getelementptr inbounds ([[STRUCT_GLOBAL_20PTR]], ptr @global.20ptr, i64 0, i32 13), align 8
-; CHECK-NEXT:    store ptr @fn2, ptr getelementptr inbounds ([[STRUCT_GLOBAL_20PTR]], ptr @global.20ptr, i64 0, i32 14), align 8
-; CHECK-NEXT:    store ptr @fn3, ptr getelementptr inbounds ([[STRUCT_GLOBAL_20PTR]], ptr @global.20ptr, i64 0, i32 15), align 8
 ; CHECK-NEXT:    ret void
 ;
 entry:
   store ptr @fn0, ptr getelementptr inbounds (%struct.global.20ptr, ptr @global.20ptr, i64 0, i32 0), align 8
   store ptr @fn1, ptr getelementptr inbounds (%struct.global.20ptr, ptr @global.20ptr, i64 0, i32 1), align 8
   store ptr @fn2, ptr getelementptr inbounds (%struct.global.20ptr, ptr @global.20ptr, i64 0, i32 2), align 8
   store ptr @fn3, ptr getelementptr inbounds (%struct.global.20ptr, ptr @global.20ptr, i64 0, i32 3), align 8
   store ptr @fn0, ptr getelementptr inbounds (%struct.global.20ptr, ptr @global.20ptr, i64 0, i32 4), align 8
entry:
   store ptr @fn2, ptr getelementptr inbounds (%struct.global.20ptr, ptr @global.20ptr, i64 0, i32 14), align 8
   store ptr @fn3, ptr getelementptr inbounds (%struct.global.20ptr, ptr @global.20ptr, i64 0, i32 15), align 8
   ret void
 }
 
 define void @stores_multi_use_gep_constexpr() {
 ; CHECK-LABEL: @stores_multi_use_gep_constexpr(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    store i32 0, ptr getelementptr inbounds ([[STRUCT_GLOBAL_20PTR:%.*]], ptr @global.20ptr, i64 0, i32 16), align 8
-; CHECK-NEXT:    store i32 0, ptr getelementptr inbounds ([[STRUCT_GLOBAL_20PTR]], ptr @global.20ptr, i64 0, i32 16), align 8
 ; CHECK-NEXT:    ret void
 ;
 entry:
   store i32 0, ptr getelementptr inbounds (%struct.global.20ptr, ptr @global.20ptr, i64 0, i32 16), align 8
   store i32 0, ptr getelementptr inbounds (%struct.global.20ptr, ptr @global.20ptr, i64 0, i32 16), align 8
   ret void
 }