[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

244

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

244

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

244

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

244

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());
   // 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 (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 if (isa<GEPOperator>(CE))
+        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/ThinLTO/X86/import-constant.ll

 ; Check that variable has been promoted in the source module
 ; PROMOTE: @_ZL3Obj.llvm.{{.*}} = hidden constant %struct.S { i32 4, i32 8, ptr @val }
 
 ; @outer is a write-only variable, so it's been converted to zeroinitializer.
 ; IMPORT:      @val = available_externally global i32 42
 ; IMPORT-NEXT: @_ZL3Obj.llvm.{{.*}} = available_externally hidden constant %struct.S { i32 4, i32 8, ptr @val }
 ; IMPORT-NEXT: @outer = internal local_unnamed_addr global %struct.Q zeroinitializer
 
-; OPT: @outer = internal unnamed_addr global %struct.Q zeroinitializer
+; @outer is a write-only variable that's stored to once, so the store and the global can be removed.
+; OPT-NOT: @outer
 
 ; OPT:      define dso_local i32 @main()
 ; OPT-NEXT: entry:
-; OPT-NEXT:   store ptr null, ptr getelementptr inbounds (%struct.Q, ptr @outer, i64 1, i32 0)
 ; OPT-NEXT:   ret i32 12
 
 ; NOREFS:      @_ZL3Obj.llvm.{{.*}} = external hidden constant %struct.S
 ; NOREFS-NEXT: @outer = internal local_unnamed_addr global %struct.Q zeroinitializer
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 

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:    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
   store ptr @fn1, ptr getelementptr inbounds (%struct.global.20ptr, ptr @global.20ptr, i64 0, i32 5), align 8
   store ptr @fn2, ptr getelementptr inbounds (%struct.global.20ptr, ptr @global.20ptr, i64 0, i32 6), align 8
   store ptr @fn3, ptr getelementptr inbounds (%struct.global.20ptr, ptr @global.20ptr, i64 0, i32 7), align 8
   store ptr @fn0, ptr getelementptr inbounds (%struct.global.20ptr, ptr @global.20ptr, i64 0, i32 8), 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
 }
 

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes=globalopt -S %s | FileCheck %s
+
+%struct.global.20ptr = type { ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr }
+
+@global.20ptr = internal unnamed_addr global %struct.global.20ptr zeroinitializer
+
+declare i32 @fn0()
+
+declare i32 @fn1()
+
+define void @stores_single_use_gep_constexpr() {
+; CHECK-LABEL: @stores_single_use_gep_constexpr(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store ptr @fn0, ptr @global.20ptr, align 8
+; CHECK-NEXT:    store ptr @fn1, ptr getelementptr inbounds ([[STRUCT_GLOBAL_20PTR:%.*]], ptr @global.20ptr, i64 0, i32 1), 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
+  ret void
+}
+
+define void @stores_ptrtoint_constexpr() {
+; CHECK-LABEL: @stores_ptrtoint_constexpr(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i32 0, ptr inttoptr (i64 add (i64 ptrtoint (ptr @global.20ptr to i64), i64 200) to ptr), align 8
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i32 0, ptr inttoptr (i64 add (i64 ptrtoint (ptr @global.20ptr to i64), i64 200) to ptr), align 8
+  ret void
+}