Remove dangling BlockAddresses in GlobalDCE

[bruno]

Summary

Whenever globaldce delete globals vars, it updates their initializers to nullptr and leave underlying constants to be cleaned up later by its uses. However, initializers containing dangling BlockAddresses are never removed because its uses (Functions and Basic Blocks) may still be alive. The presence of dead BlockAddress after globaldce is a bug - the target basic block reference count is never updated - and also prevents other optimizations; e.g. simplifycfg to merge blocks.

This patch fix this issue by removing dead BlockAddresses.

lib/Transforms/IPO/GlobalDCE.cpp

struct GlobalDCE : public ModulePass {
     // run - Do the GlobalDCE pass on the specified module, optionally updating
     // the specified callgraph to reflect the changes.
     //
     bool runOnModule(Module &M) override;
 
   private:
     SmallPtrSet<GlobalValue*, 32> AliveGlobals;
     SmallPtrSet<Constant *, 8> SeenConstants;
+    SmallPtrSet<Constant *, 8> SeenBlockAddressFnUsers;
 
     /// GlobalIsNeeded - mark the specific global value as needed, and
     /// recursively mark anything that it uses as also needed.
     void GlobalIsNeeded(GlobalValue *GV);
     void MarkUsedGlobalsAsNeeded(Constant *C);
 
     bool RemoveUnusedGlobalValue(GlobalValue &GV);
   };
if (!DeadAliases.empty()) {
     for (unsigned i = 0, e = DeadAliases.size(); i != e; ++i) {
       RemoveUnusedGlobalValue(*DeadAliases[i]);
       M.getAliasList().erase(DeadAliases[i]);
     }
     NumAliases += DeadAliases.size();
     Changed = true;
   }
 
+  // Some global initializers elements may leave dead references to functions,
+  // (e.g. BlockAddresses), clean them up.
+  for (auto F : SeenBlockAddressFnUsers)
+    F->removeDeadConstantUsers();
+
   // Make sure that all memory is released
   AliveGlobals.clear();
   SeenConstants.clear();
 
   return Changed;
 }
 
 /// GlobalIsNeeded - the specific global value as needed, and
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(G)) {
 
     for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
       for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
         for (User::op_iterator U = I->op_begin(), E = I->op_end(); U != E; ++U)
           if (GlobalValue *GV = dyn_cast<GlobalValue>(*U))
             GlobalIsNeeded(GV);
           else if (Constant *C = dyn_cast<Constant>(*U))
             MarkUsedGlobalsAsNeeded(C);
+
+    // Keep track of functions used by BlockAddresses; global initializers
+    // may leave dangling BlockAddresses referring to those.
+    for (auto UB = G->user_begin(), UE = G->user_end(); UB != UE; ++UB)
+      if (isa<BlockAddress>(*UB))
+        SeenBlockAddressFnUsers.insert(G);
   }
 }
 
 void GlobalDCE::MarkUsedGlobalsAsNeeded(Constant *C) {
   if (GlobalValue *GV = dyn_cast<GlobalValue>(C))
     return GlobalIsNeeded(GV);
 
   // Loop over all of the operands of the constant, adding any globals they

test/Transforms/GlobalDCE/deadblockaddr.ll

+; RUN: opt -O2 -simplifycfg -inline -early-cse -S < %s | FileCheck %s
+
+; Tests whether globaldce does the right cleanup while removing @foo.addrs
+; so that a dead BlockAddress reference to foo won't prevent other passes
+; to work properly, e.g. simplifycfg and inline in this test.
+
[e-mail] = private unnamed_addr constant [5 x i8*] [i8* blockaddress(@foo, %L1), i8* blockaddress(@foo, %L2), i8* blockaddress(@foo, %L3), i8* blockaddress(@foo, %L4), i8* blockaddress(@foo, %L5)], align 4
+
+; CHECK-LABEL: main
+; CHECK-NOT: call
+; CHECK: ret i32 210
+define i32 @main() #0 {
+entry:
+  %call = tail call i32 @foo(i32 3)
+  ret i32 %call
+}
+
+define internal i32 @foo(i32 %i) #0 {
+entry:
+  %addrs = alloca [5 x i8*], align 4
+  %tmp = bitcast [5 x i8*]* %addrs to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i32(i8* %tmp, i8* bitcast ([5 x i8*]* @foo.addrs to i8*), i32 20, i32 4, i1 false)
+  %arrayidx = getelementptr inbounds [5 x i8*]* %addrs, i32 0, i32 %i
+  %0 = load i8** %arrayidx, align 4
+  indirectbr i8* %0, [label %L1, label %L2, label %L3, label %L4, label %L5]
+
+L5:                                               ; preds = %entry
+  br label %L4
+
+L4:                                               ; preds = %entry, %L5
+  %1 = phi i32 [ 7, %entry ], [ 77, %L5 ]
+  br label %L3
+
+L3:                                               ; preds = %entry, %L4
+  %2 = phi i32 [ 1, %entry ], [ %1, %L4 ]
+  %phitmp = mul i32 %2, 15
+  br label %L2
+
+L2:                                               ; preds = %entry, %L3
+  %3 = phi i32 [ 3, %entry ], [ %phitmp, %L3 ]
+  br label %L1
+
+L1:                                               ; preds = %entry, %L2
+  %4 = phi i32 [ 1, %entry ], [ %3, %L2 ]
+  %mul4 = shl nsw i32 %4, 1
+  ret i32 %mul4
+}
+
+declare void @llvm.memcpy.p0i8.p0i8.i32(i8* nocapture, i8* nocapture readonly, i32, i32, i1) #1