[GlobalOpt] Replace recursion with extended worklist

[jdoerfert]

Summary

As noted in D99845, there is a worklist already but we do recursion
because other values change. This tracks them in the worklist and
removes the recursion.

[lebedev.ri]

LGTM, thanks!

llvm/lib/Transforms/IPO/GlobalOpt.cpp

296

[lebedev.ri]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

336–339

We need to track hopefully-dead-in-the-end instrs in some vector, and delete them if they are unused.

[jdoerfert]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

336–339

Not totally sure what you want me to do.

TBH, I thought this would help me but it turns out some dead-constant user that are floating around prevent my global array from ever making it this far.

I'll clean up my Attributor code and get rid of my global arrays. Also need to do some value prop through another one that is not picked up IPSCCP, so might be worth to find a wholesome solution.

384

This return true is wrong now.

[jdoerfert]

Address review, fix return mistake

[lebedev.ri]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

336–339

Previously, CE would not have users by now because we recursed,
and got to the condition after we've dealt with it's users.
Now, we get here after we enqueue it's users,
so naturally, it won't have no users by now.
So we need to defer it's destruction until after we've done with the worklist.

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

llvm/lib/Transforms/IPO/GlobalOpt.cpp

CleanupPointerRootUsers(GlobalVariable *GV,
 
   return Changed;
 }
 
 /// We just marked GV constant.  Loop over all users of the global, cleaning up
 /// the obvious ones.  This is largely just a quick scan over the use list to
 /// clean up the easy and obvious cruft.  This returns true if it made a change.
 static bool CleanupConstantGlobalUsers(
-    Value *V, Constant *Init, const DataLayout &DL,
+    Value *FirstV, Constant *FirstInit, const DataLayout &DL,
     function_ref<TargetLibraryInfo &(Function &)> GetTLI) {
   bool Changed = false;
   // Note that we need to use a weak value handle for the worklist items. When
   // we delete a constant array, we may also be holding pointer to one of its
   // elements (or an element of one of its elements if we're dealing with an
   // array of arrays) in the worklist.
-  SmallVector<WeakTrackingVH, 8> WorkList(V->users());
+  struct WorkItem {
+    WeakTrackingVH UserValue;
+    Value *Ptr;
+    Constant *Init;
+  };
+  SmallVector<WorkItem> WorkList;
+
+  auto EnqueueUsers = [&WorkList](Value *Ptr, Constant *Init) {
+    for (auto *U : Ptr->users())
+      WorkList.push_back(WorkItem{U, Ptr, Init});
+  };
+  EnqueueUsers(FirstV, FirstInit);
+
   while (!WorkList.empty()) {
-    Value *UV = WorkList.pop_back_val();
-    if (!UV)
+    WorkItem WI = WorkList.pop_back_val();
+    Value *U = WI.UserValue;
+    if (!U)
       continue;
 
-    User *U = cast<User>(UV);
+    Constant *Init = WI.Init;
+    Value *Ptr = WI.Ptr;
 
     if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
       if (Init) {
         // Replace the load with the initializer.
         LI->replaceAllUsesWith(Init);
         LI->eraseFromParent();
         Changed = true;
       }
     } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
       // Store must be unreachable or storing Init into the global.
       SI->eraseFromParent();
       Changed = true;
     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
       if (CE->getOpcode() == Instruction::GetElementPtr) {
         Constant *SubInit = nullptr;
         if (Init)
           SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE);
-        Changed |= CleanupConstantGlobalUsers(CE, SubInit, DL, GetTLI);
+        EnqueueUsers(CE, SubInit);
       } else if ((CE->getOpcode() == Instruction::BitCast &&
                   CE->getType()->isPointerTy()) ||
                  CE->getOpcode() == Instruction::AddrSpaceCast) {
         // Pointer cast, delete any stores and memsets to the global.
         // TODO: We should try to cast the Init value to the new type.
-        Changed |= CleanupConstantGlobalUsers(CE, nullptr, DL, GetTLI);
+        EnqueueUsers(CE, nullptr);
       }
 
       if (CE->use_empty()) {
         CE->destroyConstant();
         Changed = true;
       }
     } else if (CastInst *CI = dyn_cast<CastInst>(U)) {
       if (CI->getType()->isPointerTy()) {
         // Pointer cast, delete any stores and memsets to the global.
         // TODO: We should try to cast the Init value to the new type.
-        Changed |= CleanupConstantGlobalUsers(CI, nullptr, DL, GetTLI);
+        EnqueueUsers(CI, nullptr);
         if (CI->use_empty()) {
           CI->eraseFromParent();
           Changed = true;
         }
       }
     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) {
       // Do not transform "gepinst (gep constexpr (GV))" here, because forming
       // "gepconstexpr (gep constexpr (GV))" will cause the two gep's to fold
       // and will invalidate our notion of what Init is.
       Constant *SubInit = nullptr;
       if (!isa<ConstantExpr>(GEP->getOperand(0))) {
         ConstantExpr *CE = dyn_cast_or_null<ConstantExpr>(
             ConstantFoldInstruction(GEP, DL, &GetTLI(*GEP->getFunction())));
         if (Init && CE && CE->getOpcode() == Instruction::GetElementPtr)
           SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE);
 
         // If the initializer is an all-null value and we have an inbounds GEP,
         // we already know what the result of any load from that GEP is.
         // TODO: Handle splats.
-        if (Init && isa<ConstantAggregateZero>(Init) && GEP->isInBounds())
+        if (isa_and_nonnull<ConstantAggregateZero>(Init) && GEP->isInBounds())
           SubInit = Constant::getNullValue(GEP->getResultElementType());
       }
-      Changed |= CleanupConstantGlobalUsers(GEP, SubInit, DL, GetTLI);
+      EnqueueUsers(GEP, SubInit);
 
       if (GEP->use_empty()) {
         GEP->eraseFromParent();
         Changed = true;
       }
     } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(U)) { // memset/cpy/mv
-      if (MI->getRawDest() == V) {
+      if (MI->getRawDest() == Ptr) {
         MI->eraseFromParent();
         Changed = true;
       }
 
     } else if (Constant *C = dyn_cast<Constant>(U)) {
       // If we have a chain of dead constantexprs or other things dangling from
       // us, and if they are all dead, nuke them without remorse.
       if (isSafeToDestroyConstant(C)) {
         C->destroyConstant();
-        CleanupConstantGlobalUsers(V, Init, DL, GetTLI);
-        return true;
+        Changed = true;
       }
     }
   }
   return Changed;
 }
 
 static bool isSafeSROAElementUse(Value *V);