[LazyCallGraph] Skip blockaddresses

[aeubanks]

Summary

blockaddresses do not participate in the call graph since the only
instructions that use them must all return to someplace within the
current function. And passes cannot retrieve a function address from a
blockaddress.

This was suggested by efriedma in D58260.

Fixes PR50881.

[nickdesaulniers]

llvm/lib/Analysis/LazyCallGraph.cpp

1986

I pulled in "llvm/ADT/STLExtras.h" for llvm::all_of in D58260. Can that header now not be included?

llvm/test/Analysis/LazyCallGraph/blockaddress.ll

3

I think you can drop <?

llvm/test/Transforms/Attributor/IPConstantProp/dangling-block-address.ll

37

Can we remove IS__CGSCC_OPM from the RUN lines, too? Looks like this change removes all references? Perhaps we can get rid of the OPM RUN lines? And pre-commit that?

[aeubanks]

llvm/lib/Analysis/LazyCallGraph.cpp

1986

there are other instances of all_of in this file

llvm/test/Analysis/LazyCallGraph/blockaddress.ll

3

I think it's generally added to prevent the file name from being leaked to opt, but usually doesn't really matter

llvm/test/Transforms/Attributor/IPConstantProp/dangling-block-address.ll

37

will do

[aeubanks]

llvm/test/Transforms/Attributor/IPConstantProp/dangling-block-address.ll

37

apparently it's a bit more complicated than I originally thought: https://reviews.llvm.org/D112184

can we punt on this for now?

[aeubanks]

ping

[nickdesaulniers]

llvm/test/Transforms/Attributor/IPConstantProp/dangling-block-address.ll

37

Can you remove one run line from one test?

[aeubanks]

llvm/test/Transforms/Attributor/IPConstantProp/dangling-block-address.ll

37

I'd rather keep this consistent with the many other attributor tests which always do this sort of thing.

llvm/lib/Analysis/LazyCallGraph.cpp

while (!Worklist.empty()) {
     Constant *C = Worklist.pop_back_val();
 
     if (Function *F = dyn_cast<Function>(C)) {
       if (!F->isDeclaration())
         Callback(*F);
       continue;
     }
 
-    // The blockaddress constant expression is a weird special case, we can't
-    // generically walk its operands the way we do for all other constants.
-    if (BlockAddress *BA = dyn_cast<BlockAddress>(C)) {
-      // If we've already visited the function referred to by the block
-      // address, we don't need to revisit it.
-      if (Visited.count(BA->getFunction()))
-        continue;
+    // blockaddresses are weird and don't participate in the call graph anyway,
+    // skip them.
+    if (isa<BlockAddress>(C))
 
-      // If all of the blockaddress' users are instructions within the
-      // referred to function, we don't need to insert a cycle.
-      if (llvm::all_of(BA->users(), [&](User *U) {
-            if (Instruction *I = dyn_cast<Instruction>(U))
-              return I->getFunction() == BA->getFunction();
-            return false;
-          }))
-        continue;
-
-      // Otherwise we should go visit the referred to function.
-      Visited.insert(BA->getFunction());
-      Worklist.push_back(BA->getFunction());
-      continue;
-    }
-
     for (Value *Op : C->operand_values())
       if (Visited.insert(cast<Constant>(Op)).second)
         Worklist.push_back(cast<Constant>(Op));
   }
 }
 
 AnalysisKey LazyCallGraphAnalysis::Key;
 

llvm/test/Analysis/LazyCallGraph/blockaddress.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes="cgscc(function(sccp,simplifycfg))" < %s -S | FileCheck %s
+
+define i32 @baz(i32 %y, i1 %b) {
+; CHECK-LABEL: @baz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[B:%.*]], label [[LAB:%.*]], label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[P_0:%.*]] = phi i8* [ null, [[FOR_COND]] ], [ blockaddress(@baz, [[LAB]]), [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[INCDEC_PTR:%.*]] = getelementptr inbounds i8, i8* [[P_0]], i64 1
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       lab:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  br i1 %b, label %lab, label %for.cond.preheader
+
+for.cond.preheader:
+  br label %for.cond
+
+for.cond:
+  %p.0 = phi i8* [ null, %for.cond ], [ blockaddress(@baz, %lab), %for.cond.preheader ]
+  %incdec.ptr = getelementptr inbounds i8, i8* %p.0, i64 1
+  br label %for.cond
+
+lab:
+  ret i32 0
+}

llvm/test/Transforms/Attributor/IPConstantProp/dangling-block-address.ll

 ;
 entry:
   %b = alloca i32, align 4                        ; <i32*> [#uses=1]
   store volatile i32 -1, i32* %b
   ret void
 }
 
 define internal void @bar(i32* nocapture %pc) nounwind readonly {
-; IS__CGSCC_OPM: Function Attrs: nounwind readonly
-; IS__CGSCC_OPM-LABEL: define {{[^@]+}}@bar
-; IS__CGSCC_OPM-SAME: (i32* nocapture [[PC:%.*]]) #[[ATTR1:[0-9]+]] {
-; IS__CGSCC_OPM-NEXT:  entry:
-; IS__CGSCC_OPM-NEXT:    br label [[INDIRECTGOTO:%.*]]
-; IS__CGSCC_OPM:       lab0:
-; IS__CGSCC_OPM-NEXT:    [[INDVAR_NEXT:%.*]] = add i32 [[INDVAR:%.*]], 1
-; IS__CGSCC_OPM-NEXT:    br label [[INDIRECTGOTO]]
-; IS__CGSCC_OPM:       end:
-; IS__CGSCC_OPM-NEXT:    ret void
-; IS__CGSCC_OPM:       indirectgoto:
-; IS__CGSCC_OPM-NEXT:    [[INDVAR]] = phi i32 [ [[INDVAR_NEXT]], [[LAB0:%.*]] ], [ 0, [[ENTRY:%.*]] ]
-; IS__CGSCC_OPM-NEXT:    [[PC_ADDR_0:%.*]] = getelementptr i32, i32* [[PC]], i32 [[INDVAR]]
-; IS__CGSCC_OPM-NEXT:    [[TMP1_PN:%.*]] = load i32, i32* [[PC_ADDR_0]], align 4
-; IS__CGSCC_OPM-NEXT:    [[INDIRECT_GOTO_DEST_IN:%.*]] = getelementptr inbounds [2 x i8*], [2 x i8*]* @bar.l, i32 0, i32 [[TMP1_PN]]
-; IS__CGSCC_OPM-NEXT:    [[INDIRECT_GOTO_DEST:%.*]] = load i8*, i8** [[INDIRECT_GOTO_DEST_IN]], align 8
-; IS__CGSCC_OPM-NEXT:    indirectbr i8* [[INDIRECT_GOTO_DEST]], [label [[LAB0]], label %end]
-;
-; IS__CGSCC_NPM: Function Attrs: nofree norecurse nosync nounwind readnone
-; IS__CGSCC_NPM-LABEL: define {{[^@]+}}@bar
-; IS__CGSCC_NPM-SAME: () #[[ATTR1:[0-9]+]] {
-; IS__CGSCC_NPM-NEXT:  entry:
-; IS__CGSCC_NPM-NEXT:    br label [[INDIRECTGOTO:%.*]]
-; IS__CGSCC_NPM:       lab0:
-; IS__CGSCC_NPM-NEXT:    [[INDVAR_NEXT:%.*]] = add i32 [[INDVAR:%.*]], 1
-; IS__CGSCC_NPM-NEXT:    br label [[INDIRECTGOTO]]
-; IS__CGSCC_NPM:       end:
-; IS__CGSCC_NPM-NEXT:    ret void
-; IS__CGSCC_NPM:       indirectgoto:
-; IS__CGSCC_NPM-NEXT:    [[INDVAR]] = phi i32 [ [[INDVAR_NEXT]], [[LAB0:%.*]] ], [ 0, [[ENTRY:%.*]] ]
-; IS__CGSCC_NPM-NEXT:    indirectbr i8* undef, [label [[LAB0]], label %end]
+; IS__CGSCC____: Function Attrs: nounwind readonly
+; IS__CGSCC____-LABEL: define {{[^@]+}}@bar
+; IS__CGSCC____-SAME: (i32* nocapture [[PC:%.*]]) #[[ATTR1:[0-9]+]] {
+; IS__CGSCC____-NEXT:  entry:
+; IS__CGSCC____-NEXT:    br label [[INDIRECTGOTO:%.*]]
+; IS__CGSCC____:       lab0:
+; IS__CGSCC____-NEXT:    [[INDVAR_NEXT:%.*]] = add i32 [[INDVAR:%.*]], 1
+; IS__CGSCC____-NEXT:    br label [[INDIRECTGOTO]]
+; IS__CGSCC____:       end:
+; IS__CGSCC____-NEXT:    ret void
+; IS__CGSCC____:       indirectgoto:
+; IS__CGSCC____-NEXT:    [[INDVAR]] = phi i32 [ [[INDVAR_NEXT]], [[LAB0:%.*]] ], [ 0, [[ENTRY:%.*]] ]
+; IS__CGSCC____-NEXT:    [[PC_ADDR_0:%.*]] = getelementptr i32, i32* [[PC]], i32 [[INDVAR]]
+; IS__CGSCC____-NEXT:    [[TMP1_PN:%.*]] = load i32, i32* [[PC_ADDR_0]], align 4
+; IS__CGSCC____-NEXT:    [[INDIRECT_GOTO_DEST_IN:%.*]] = getelementptr inbounds [2 x i8*], [2 x i8*]* @bar.l, i32 0, i32 [[TMP1_PN]]
+; IS__CGSCC____-NEXT:    [[INDIRECT_GOTO_DEST:%.*]] = load i8*, i8** [[INDIRECT_GOTO_DEST_IN]], align 8
+; IS__CGSCC____-NEXT:    indirectbr i8* [[INDIRECT_GOTO_DEST]], [label [[LAB0]], label %end]
 ;
 entry:
   br label %indirectgoto
 
 lab0:                                             ; preds = %indirectgoto
   %indvar.next = add i32 %indvar, 1               ; <i32> [#uses=1]
   br label %indirectgoto
 

 ; IS__CGSCC____-NEXT:    ret i32 0
 ;
 entry:
   ret i32 0
 }
 ;.
 ; IS__TUNIT____: attributes #[[ATTR0]] = { nofree nosync nounwind readnone willreturn }
 ;.
-; IS__CGSCC_OPM: attributes #[[ATTR0]] = { nounwind readnone }
-; IS__CGSCC_OPM: attributes #[[ATTR1]] = { nounwind readonly }
-; IS__CGSCC_OPM: attributes #[[ATTR2]] = { nofree norecurse nosync nounwind readnone willreturn }
-;.
-; IS__CGSCC_NPM: attributes #[[ATTR0]] = { nounwind readnone }
-; IS__CGSCC_NPM: attributes #[[ATTR1]] = { nofree norecurse nosync nounwind readnone }
-; IS__CGSCC_NPM: attributes #[[ATTR2]] = { nofree norecurse nosync nounwind readnone willreturn }
+; IS__CGSCC____: attributes #[[ATTR0]] = { nounwind readnone }
+; IS__CGSCC____: attributes #[[ATTR1]] = { nounwind readonly }
+; IS__CGSCC____: attributes #[[ATTR2]] = { nofree norecurse nosync nounwind readnone willreturn }
 ;.

llvm/test/Transforms/Attributor/liveness.ll

 ; IS__CGSCC_OPM:       indirectgoto:
 ; IS__CGSCC_OPM-NEXT:    [[INDVAR]] = phi i32 [ [[INDVAR_NEXT]], [[LAB0:%.*]] ], [ 0, [[ENTRY:%.*]] ]
 ; IS__CGSCC_OPM-NEXT:    [[PC_ADDR_0:%.*]] = getelementptr i32, i32* [[PC]], i32 [[INDVAR]]
 ; IS__CGSCC_OPM-NEXT:    [[TMP1_PN:%.*]] = load i32, i32* [[PC_ADDR_0]]
 ; IS__CGSCC_OPM-NEXT:    [[INDIRECT_GOTO_DEST_IN:%.*]] = getelementptr inbounds [2 x i8*], [2 x i8*]* @dead_with_blockaddress_users.l, i32 0, i32 [[TMP1_PN]]
 ; IS__CGSCC_OPM-NEXT:    [[INDIRECT_GOTO_DEST:%.*]] = load i8*, i8** [[INDIRECT_GOTO_DEST_IN]]
 ; IS__CGSCC_OPM-NEXT:    indirectbr i8* [[INDIRECT_GOTO_DEST]], [label [[LAB0]], label %end]
 ;
-; IS__CGSCC____: Function Attrs: nofree norecurse nosync nounwind readnone
+; IS__CGSCC____: Function Attrs: nounwind readonly
 ; IS__CGSCC____-LABEL: define {{[^@]+}}@dead_with_blockaddress_users
-; IS__CGSCC____-SAME: () #[[ATTR14:[0-9]+]] {
+; IS__CGSCC____-SAME: (i32* nocapture [[PC:%.*]]) #[[ATTR14:[0-9]+]] {
 ; IS__CGSCC____-NEXT:  entry:
 ; IS__CGSCC____-NEXT:    br label [[INDIRECTGOTO:%.*]]
 ; IS__CGSCC____:       lab0:
 ; IS__CGSCC____-NEXT:    [[INDVAR_NEXT:%.*]] = add i32 [[INDVAR:%.*]], 1
 ; IS__CGSCC____-NEXT:    br label [[INDIRECTGOTO]]
 ; IS__CGSCC____:       end:
 ; IS__CGSCC____-NEXT:    ret void
 ; IS__CGSCC____:       indirectgoto:
 ; IS__CGSCC____-NEXT:    [[INDVAR]] = phi i32 [ [[INDVAR_NEXT]], [[LAB0:%.*]] ], [ 0, [[ENTRY:%.*]] ]
-; IS__CGSCC____-NEXT:    indirectbr i8* undef, [label [[LAB0]], label %end]
+; IS__CGSCC____-NEXT:    [[PC_ADDR_0:%.*]] = getelementptr i32, i32* [[PC]], i32 [[INDVAR]]
+; IS__CGSCC____-NEXT:    [[TMP1_PN:%.*]] = load i32, i32* [[PC_ADDR_0]], align 4
+; IS__CGSCC____-NEXT:    [[INDIRECT_GOTO_DEST_IN:%.*]] = getelementptr inbounds [2 x i8*], [2 x i8*]* @dead_with_blockaddress_users.l, i32 0, i32 [[TMP1_PN]]
+; IS__CGSCC____-NEXT:    [[INDIRECT_GOTO_DEST:%.*]] = load i8*, i8** [[INDIRECT_GOTO_DEST_IN]], align 8
+; IS__CGSCC____-NEXT:    indirectbr i8* [[INDIRECT_GOTO_DEST]], [label [[LAB0]], label %end]
 ;
 entry:
   br label %indirectgoto
 
 lab0:                                             ; preds = %indirectgoto
   %indvar.next = add i32 %indvar, 1               ; <i32> [#uses=1]
   br label %indirectgoto
 

 ; IS__CGSCC____: attributes #[[ATTR6]] = { nofree norecurse nosync nounwind readnone willreturn }
 ; IS__CGSCC____: attributes #[[ATTR7]] = { argmemonly nofree norecurse nounwind uwtable willreturn }
 ; IS__CGSCC____: attributes #[[ATTR8]] = { nofree norecurse nosync nounwind readnone uwtable willreturn }
 ; IS__CGSCC____: attributes #[[ATTR9]] = { nosync }
 ; IS__CGSCC____: attributes #[[ATTR10]] = { argmemonly nofree norecurse nosync nounwind willreturn writeonly }
 ; IS__CGSCC____: attributes #[[ATTR11]] = { nofree norecurse noreturn nosync nounwind readnone }
 ; IS__CGSCC____: attributes #[[ATTR12]] = { nofree norecurse noreturn nosync nounwind readnone willreturn }
 ; IS__CGSCC____: attributes #[[ATTR13]] = { nofree nosync nounwind willreturn }
-; IS__CGSCC____: attributes #[[ATTR14]] = { nofree norecurse nosync nounwind readnone }
+; IS__CGSCC____: attributes #[[ATTR14]] = { nounwind readonly }
 ; IS__CGSCC____: attributes #[[ATTR15]] = { nofree nosync nounwind readnone willreturn }
 ; IS__CGSCC____: attributes #[[ATTR16:[0-9]+]] = { argmemonly nofree nosync nounwind willreturn }
 ; IS__CGSCC____: attributes #[[ATTR17]] = { nounwind willreturn }
 ; IS__CGSCC____: attributes #[[ATTR18]] = { willreturn }
 ;.

llvm/unittests/Analysis/LazyCallGraphTest.cpp

TEST(LazyCallGraphTest, HandleBlockAddress) {
   LazyCallGraph::RefSCC &FRC = *I++;
   LazyCallGraph::RefSCC &GRC = *I++;
   EXPECT_EQ(CG.postorder_ref_scc_end(), I);
 
   LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f"));
   LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g"));
   EXPECT_EQ(&FRC, CG.lookupRefSCC(F));
   EXPECT_EQ(&GRC, CG.lookupRefSCC(G));
-  EXPECT_TRUE(GRC.isParentOf(FRC));
+  EXPECT_FALSE(GRC.isParentOf(FRC));
+  EXPECT_FALSE(FRC.isParentOf(GRC));
 }
 
 // Test that a blockaddress that refers to itself creates no new RefSCC
 // connections. https://bugs.llvm.org/show_bug.cgi?id=40722
 TEST(LazyCallGraphTest, HandleBlockAddress2) {
   LLVMContext Context;
   std::unique_ptr<Module> M =
       parseAssembly(Context, "define void @f() {\n"