[LazyCallGraph] Build SCCs of the reference graph in order

[MaskRay]

Summary

// The legacy PM CGPassManager discovers SCCs this way:
for function in the source order
  tarjanSCC(function)

// While the new PM CGSCCPassManager does:
for function in the reversed source order [1]
  discover a reference graph SCC
  build call graph SCCs inside the reference graph SCC

In the common cases, reference graph ~= call graph, the new PM order is
undesired because for a | b | c (3 independent functions), the new PM will
process them in the reversed order: c, b, a. If a <-> b <-> c, we can see
that -print-after-all will report the sole SCC as scc: (c, b, a).

This patch corrects the iteration order [1]. The discovered SCC order will match
the legacy PM in the common cases.

For some tests (Transforms/Inline/cgscc-*.ll and
unittests/Analysis/CGSCCPassManagerTest.cpp), the behaviors are dependent on
the SCC discovery order and there are too many check lines for the particular
order. This patch simply reverses the function order to avoid change too many
check lines.

[jdoerfert]

I stumbled over the difference before, this makes sense to me.

[aeubanks]

lgtm (thanks for doing this!), just one question about a test

llvm/test/Other/scc-pass-printer.ll

14–24

what's the reason for splitting the NPM and legacy PM RUN lines?

[MaskRay]

llvm/test/Other/scc-pass-printer.ll

14–24

The orders of bar and foo are different...

The legacy PM SCC is bar,foo and thus llvm/lib/Analysis/CallGraphSCCPass.cpp prints the functions in the (reversed) order.

[aeubanks]

llvm/test/Other/scc-pass-printer.ll

14–24

Oh sorry I missed that, I thought the only change was the "bar, foo" -> "foo, bar".

llvm/lib/Analysis/LazyCallGraph.cpp

if (EntryEdges.empty() || !PostOrderRefSCCs.empty())
     return;
 
   assert(RefSCCIndices.empty() && "Already mapped RefSCC indices!");
 
   SmallVector<Node *, 16> Roots;
   for (Edge &E : *this)
     Roots.push_back(&E.getNode());
 
-  // The roots will be popped of a stack, so use reverse to get a less
-  // surprising order. This doesn't change any of the semantics anywhere.
-  std::reverse(Roots.begin(), Roots.end());
-
+  // The roots will be iterated in order.
   buildGenericSCCs(
       Roots,
       [](Node &N) {
         // We need to populate each node as we begin to walk its edges.
         N.populate();
         return N->begin();
       },
       [](Node &N) { return N->end(); },

llvm/test/Analysis/LazyCallGraph/alias.ll

 ; RUN: opt -disable-output -passes=print-lcg %s 2>&1 | FileCheck %s
 ;
 ; Aliased function should be reachable in CGSCC.
 
 target triple = "x86_64-grtev4-linux-gnu"
 
 ; CHECK:        Edges in function: foo
 ; CHECK:        Edges in function: bar
 ; CHECK:        Edges in function: baz
 
-; CHECK:        RefSCC with 1 call SCCs:
-; CHECK-NEXT:     SCC with 1 functions:
-; CHECK-NEXT:       bar
-
+; CHECK:       RefSCC with 1 call SCCs:
+; CHECK-NEXT:    SCC with 1 functions:
+; CHECK-NEXT:      foo
+; CHECK-EMPTY:
 ; CHECK:       RefSCC with 1 call SCCs:
 ; CHECK-NEXT:    SCC with 1 functions:
-; CHECK-NEXT:      foo
+; CHECK-NEXT:      bar
 
 ; CHECK-NOT:       baz
 
 @alias1 = weak dso_local alias i8* (i8*), i8* (i8*)* @foo
 
 define dso_local i8* @foo(i8* %returned) {
   ret i8* %returned
 }

llvm/test/Analysis/LazyCallGraph/basic.ll

 entry:
   call void @test3_ca1()
   ret void
 }
 
 ; Verify the SCCs formed.
 ;
 ; CHECK-LABEL: RefSCC with 1 call SCCs:
-; CHECK-NEXT:    SCC with 3 functions:
-; CHECK-NEXT:      test3_ca3
-; CHECK-NEXT:      test3_ca1
-; CHECK-NEXT:      test3_ca2
-;
-; CHECK-LABEL: RefSCC with 2 call SCCs:
-; CHECK-NEXT:    SCC with 1 functions:
-; CHECK-NEXT:      test3_bb1
 ; CHECK-NEXT:    SCC with 1 functions:
-; CHECK-NEXT:      test3_ba1
-;
-; CHECK-LABEL: RefSCC with 3 call SCCs:
-; CHECK-NEXT:    SCC with 2 functions:
-; CHECK-NEXT:      test3_ac2
-; CHECK-NEXT:      test3_ac1
-; CHECK-NEXT:    SCC with 2 functions:
-; CHECK-NEXT:      test3_ab2
-; CHECK-NEXT:      test3_ab1
-; CHECK-NEXT:    SCC with 2 functions:
-; CHECK-NEXT:      test3_aa2
-; CHECK-NEXT:      test3_aa1
+; CHECK-NEXT:      f
 ;
 ; CHECK-LABEL: RefSCC with 1 call SCCs:
 ; CHECK-NEXT:    SCC with 1 functions:
-; CHECK-NEXT:      f7
+; CHECK-NEXT:      f1
 ;
 ; CHECK-LABEL: RefSCC with 1 call SCCs:
 ; CHECK-NEXT:    SCC with 1 functions:
-; CHECK-NEXT:      f6
+; CHECK-NEXT:      f2
 ;
 ; CHECK-LABEL: RefSCC with 1 call SCCs:
 ; CHECK-NEXT:    SCC with 1 functions:
-; CHECK-NEXT:      f5
+; CHECK-NEXT:      f3
 ;
 ; CHECK-LABEL: RefSCC with 1 call SCCs:
 ; CHECK-NEXT:    SCC with 1 functions:
 ; CHECK-NEXT:      f4
 ;
 ; CHECK-LABEL: RefSCC with 1 call SCCs:
 ; CHECK-NEXT:    SCC with 1 functions:
-; CHECK-NEXT:      f3
+; CHECK-NEXT:      f5
 ;
 ; CHECK-LABEL: RefSCC with 1 call SCCs:
 ; CHECK-NEXT:    SCC with 1 functions:
-; CHECK-NEXT:      f2
+; CHECK-NEXT:      f6
 ;
 ; CHECK-LABEL: RefSCC with 1 call SCCs:
 ; CHECK-NEXT:    SCC with 1 functions:
-; CHECK-NEXT:      f1
+; CHECK-NEXT:      f7
 ;
 ; CHECK-LABEL: RefSCC with 1 call SCCs:
 ; CHECK-NEXT:    SCC with 1 functions:
-; CHECK-NEXT:      test2
+; CHECK-NEXT:      f8
 ;
 ; CHECK-LABEL: RefSCC with 1 call SCCs:
 ; CHECK-NEXT:    SCC with 1 functions:
-; CHECK-NEXT:      f10
+; CHECK-NEXT:      f9
 ;
 ; CHECK-LABEL: RefSCC with 1 call SCCs:
 ; CHECK-NEXT:    SCC with 1 functions:
-; CHECK-NEXT:      f12
+; CHECK-NEXT:      f10
 ;
 ; CHECK-LABEL: RefSCC with 1 call SCCs:
 ; CHECK-NEXT:    SCC with 1 functions:
 ; CHECK-NEXT:      f11
 ;
 ; CHECK-LABEL: RefSCC with 1 call SCCs:
 ; CHECK-NEXT:    SCC with 1 functions:
-; CHECK-NEXT:      f9
+; CHECK-NEXT:      f12
 ;
 ; CHECK-LABEL: RefSCC with 1 call SCCs:
 ; CHECK-NEXT:    SCC with 1 functions:
-; CHECK-NEXT:      f8
+; CHECK-NEXT:      test0
 ;
 ; CHECK-LABEL: RefSCC with 1 call SCCs:
 ; CHECK-NEXT:    SCC with 1 functions:
 ; CHECK-NEXT:      test1
 ;
 ; CHECK-LABEL: RefSCC with 1 call SCCs:
 ; CHECK-NEXT:    SCC with 1 functions:
-; CHECK-NEXT:      f
+; CHECK-NEXT:      test2
 ;
 ; CHECK-LABEL: RefSCC with 1 call SCCs:
+; CHECK-NEXT:    SCC with 3 functions:
+; CHECK-NEXT:      test3_ca2
+; CHECK-NEXT:      test3_ca3
+; CHECK-NEXT:      test3_ca1
+;
+; CHECK-LABEL: RefSCC with 2 call SCCs:
 ; CHECK-NEXT:    SCC with 1 functions:
-; CHECK-NEXT:      test0
+; CHECK-NEXT:      test3_bb1
+; CHECK-NEXT:    SCC with 1 functions:
+; CHECK-NEXT:      test3_ba1
+;
+; CHECK-LABEL: RefSCC with 3 call SCCs:
+; CHECK-NEXT:    SCC with 2 functions:
+; CHECK-NEXT:      test3_ac1
+; CHECK-NEXT:      test3_ac2
+; CHECK-NEXT:    SCC with 2 functions:
+; CHECK-NEXT:      test3_ab2
+; CHECK-NEXT:      test3_ab1
+; CHECK-NEXT:    SCC with 2 functions:
+; CHECK-NEXT:      test3_aa1
+; CHECK-NEXT:      test3_aa2

llvm/test/Other/scc-pass-printer.ll

 ; RUN: opt < %s 2>&1 -disable-output \
-; RUN:     -inline -print-after-all | FileCheck %s -check-prefix=INL
+; RUN:     -inline -print-after-all | FileCheck %s --check-prefix=LEGACY
 ; RUN: opt < %s 2>&1 -disable-output \
 ; RUN:     -passes=inline -print-after-all | FileCheck %s -check-prefix=INL
 ; RUN: opt < %s 2>&1 -disable-output \
 ; RUN:     -passes=inliner-wrapper -print-after-all | FileCheck %s -check-prefix=INL
 ; RUN: opt < %s 2>&1 -disable-output \
-; RUN:     -inline -print-after-all -print-module-scope | FileCheck %s -check-prefix=INL-MOD
+; RUN:     -inline -print-after-all -print-module-scope | FileCheck %s -check-prefix=LEGACY-MOD
 ; RUN: opt < %s 2>&1 -disable-output \
 ; RUN:     -passes=inline -print-after-all -print-module-scope | FileCheck %s -check-prefix=INL-MOD
 ; RUN: opt < %s 2>&1 -disable-output \
 ; RUN:     -passes=inliner-wrapper -print-after-all -print-module-scope | FileCheck %s -check-prefix=INL-MOD
 
-; INL: IR Dump After {{Function Integration/Inlining|InlinerPass .*scc: .bar, foo}}
-; INL: define void @bar()
-; INL-NEXT:  call void @foo()
-; INL: define void @foo()
+; LEGACY: IR Dump After Function Integration/Inlining
+; LEGACY:        define void @bar()
+; LEGACY-NEXT:   call void @foo()
+; LEGACY: define void @foo()
+; LEGACY-NEXT:   call void @bar()
+; LEGACY: IR Dump After Function Integration/Inlining
+; LEGACY: define void @tester()
+; LEGACY-NEXT:  call void @foo()
+
+; INL:      IR Dump After InlinerPass *** (scc: (foo, bar))
+; INL:      define void @foo()
 ; INL-NEXT:   call void @bar()
-; INL: IR Dump After {{Function Integration/Inlining|InlinerPass .*scc: .tester}}
-; INL: define void @tester()
-; INL-NEXT:  call void @foo()
-; INL: IR Dump After
+; INL:      define void @bar()
+; INL-NEXT:   call void @foo()
+; INL:      IR Dump After InlinerPass *** (scc: (tester))
+; INL:      define void @tester()
+; INL-NEXT:   call void @foo()
 
-; INL-MOD: IR Dump After {{Function Integration/Inlining|InlinerPass .*scc: .bar, foo}}
+; LEGACY-MOD:      IR Dump After Function Integration/Inlining
+; LEGACY-MOD-NEXT: ModuleID =
+; LEGACY-MOD:      define void @tester()
+; LEGACY-MOD:      define void @foo()
+; LEGACY-MOD:      define void @bar()
+
+; INL-MOD-LABEL:*** IR Dump After InlinerPass *** (scc: (foo, bar))
 ; INL-MOD-NEXT: ModuleID =
 ; INL-MOD-NEXT: source_filename =
 ; INL-MOD: define void @tester()
 ; INL-MOD-NEXT:  call void @foo()
 ; INL-MOD: define void @foo()
-; INL-MOD-NEXT:   call void @bar()
+; INL-MOD-NEXT:  call void @bar()
 ; INL-MOD: define void @bar()
-; INL-MOD-NEXT:  call void @foo()
-; INL-MOD: IR Dump After {{Function Integration/Inlining|InlinerPass .*scc: .tester}}
+; INL-MOD-NEXT:   call void @foo()
+; INL-MOD-LABEL:*** IR Dump After InlinerPass *** (scc: (tester))
 ; INL-MOD-NEXT: ModuleID =
 ; INL-MOD-NEXT: source_filename =
 ; INL-MOD: define void @tester()
 ; INL-MOD-NEXT:  call void @foo()
 ; INL-MOD: define void @foo()
 ; INL-MOD-NEXT:   call void @bar()
 ; INL-MOD: define void @bar()
 ; INL-MOD-NEXT:  call void @foo()

llvm/test/Transforms/Attributor/IPConstantProp/PR26044.ll

 ; IS__TUNIT____-NEXT:    [[E_2:%.*]] = phi i32* [ undef, [[ENTRY:%.*]] ], [ null, [[FOR_COND1:%.*]] ]
 ; IS__TUNIT____-NEXT:    [[TMP0:%.*]] = load i32, i32* null, align 4
 ; IS__TUNIT____-NEXT:    [[CALL:%.*]] = call i32 @fn0(i32 [[TMP0]]) [[ATTR3]]
 ; IS__TUNIT____-NEXT:    store i32 [[CALL]], i32* [[P]], align 4
 ; IS__TUNIT____-NEXT:    br label [[FOR_COND1]]
 ; IS__TUNIT____:       exit:
 ; IS__TUNIT____-NEXT:    ret void
 ;
-; IS__CGSCC_OPM: Function Attrs: nofree norecurse nosync nounwind null_pointer_is_valid
-; IS__CGSCC_OPM-LABEL: define {{[^@]+}}@fn_no_null_opt
-; IS__CGSCC_OPM-SAME: (i32* nocapture nofree writeonly align 4 dereferenceable_or_null(4) [[P:%.*]], i1 [[C:%.*]]) [[ATTR2:#.*]] {
-; IS__CGSCC_OPM-NEXT:  entry:
-; IS__CGSCC_OPM-NEXT:    br label [[IF_END:%.*]]
-; IS__CGSCC_OPM:       for.cond1:
-; IS__CGSCC_OPM-NEXT:    br i1 [[C]], label [[IF_END]], label [[EXIT:%.*]]
-; IS__CGSCC_OPM:       if.end:
-; IS__CGSCC_OPM-NEXT:    [[E_2:%.*]] = phi i32* [ undef, [[ENTRY:%.*]] ], [ null, [[FOR_COND1:%.*]] ]
-; IS__CGSCC_OPM-NEXT:    [[TMP0:%.*]] = load i32, i32* null, align 4
-; IS__CGSCC_OPM-NEXT:    [[CALL:%.*]] = call i32 @fn0(i32 [[TMP0]])
-; IS__CGSCC_OPM-NEXT:    store i32 [[CALL]], i32* [[P]], align 4
-; IS__CGSCC_OPM-NEXT:    br label [[FOR_COND1]]
-; IS__CGSCC_OPM:       exit:
-; IS__CGSCC_OPM-NEXT:    ret void
-;
-; IS__CGSCC_NPM: Function Attrs: nofree norecurse nosync nounwind null_pointer_is_valid
-; IS__CGSCC_NPM-LABEL: define {{[^@]+}}@fn_no_null_opt
-; IS__CGSCC_NPM-SAME: (i32* nocapture nofree writeonly align 4 dereferenceable_or_null(4) [[P:%.*]], i1 [[C:%.*]]) [[ATTR2:#.*]] {
-; IS__CGSCC_NPM-NEXT:  entry:
-; IS__CGSCC_NPM-NEXT:    br label [[IF_END:%.*]]
-; IS__CGSCC_NPM:       for.cond1:
-; IS__CGSCC_NPM-NEXT:    br i1 [[C]], label [[IF_END]], label [[EXIT:%.*]]
-; IS__CGSCC_NPM:       if.end:
-; IS__CGSCC_NPM-NEXT:    [[E_2:%.*]] = phi i32* [ undef, [[ENTRY:%.*]] ], [ null, [[FOR_COND1:%.*]] ]
-; IS__CGSCC_NPM-NEXT:    [[TMP0:%.*]] = load i32, i32* null, align 536870912
-; IS__CGSCC_NPM-NEXT:    [[CALL:%.*]] = call i32 @fn0(i32 [[TMP0]])
-; IS__CGSCC_NPM-NEXT:    store i32 [[CALL]], i32* [[P]], align 4
-; IS__CGSCC_NPM-NEXT:    br label [[FOR_COND1]]
-; IS__CGSCC_NPM:       exit:
-; IS__CGSCC_NPM-NEXT:    ret void
+; IS__CGSCC____: Function Attrs: nofree norecurse nosync nounwind null_pointer_is_valid
+; IS__CGSCC____-LABEL: define {{[^@]+}}@fn_no_null_opt
+; IS__CGSCC____-SAME: (i32* nocapture nofree writeonly align 4 dereferenceable_or_null(4) [[P:%.*]], i1 [[C:%.*]]) [[ATTR2:#.*]] {
+; IS__CGSCC____-NEXT:  entry:
+; IS__CGSCC____-NEXT:    br label [[IF_END:%.*]]
+; IS__CGSCC____:       for.cond1:
+; IS__CGSCC____-NEXT:    br i1 [[C]], label [[IF_END]], label [[EXIT:%.*]]
+; IS__CGSCC____:       if.end:
+; IS__CGSCC____-NEXT:    [[E_2:%.*]] = phi i32* [ undef, [[ENTRY:%.*]] ], [ null, [[FOR_COND1:%.*]] ]
+; IS__CGSCC____-NEXT:    [[TMP0:%.*]] = load i32, i32* null, align 4
+; IS__CGSCC____-NEXT:    [[CALL:%.*]] = call i32 @fn0(i32 [[TMP0]])
+; IS__CGSCC____-NEXT:    store i32 [[CALL]], i32* [[P]], align 4
+; IS__CGSCC____-NEXT:    br label [[FOR_COND1]]
+; IS__CGSCC____:       exit:
+; IS__CGSCC____-NEXT:    ret void
 ;
 entry:
   br label %if.end
 
 for.cond1:                                        ; preds = %if.end
   br i1 %C, label %if.end, label %exit
 
 if.end:                                           ; preds = %entry, %for.cond1

llvm/test/Transforms/Inline/cgscc-cycle-debug.ll

 ; When an SCC got split due to inlining, we have two mechanisms for reprocessing the updated SCC, first is UR.UpdatedC
 ; that repeatedly rerun the new, current SCC; second is a worklist for all newly split SCCs. We need to avoid rerun of
 ; the same SCC when the SCC is set to be processed by both mechanisms back to back. In pathological cases, such extra,
 ; redundant rerun could cause exponential size growth due to inlining along cycles.
 ;
 ; The test cases here illustrates potential redundant rerun and how it's prevented, however there's no extra inlining
 ; even if we allow the redundant rerun. In real code, when inliner makes different decisions for different call sites
 ; of the same caller-callee edge, we could end up getting more recursive inlining without SCC mutation.
 ;
 ; REQUIRES: asserts
 ; RUN: opt < %s -passes='cgscc(inline)' -inline-threshold=500 -debug-only=cgscc -S 2>&1 | FileCheck %s
 
-; CHECK: Running an SCC pass across the RefSCC: [(test1_c, test1_a, test1_b)]
+; CHECK: Running an SCC pass across the RefSCC: [(test1_a, test1_b, test1_c)]
 ; CHECK: Enqueuing the existing SCC in the worklist:(test1_b)
 ; CHECK: Enqueuing a newly formed SCC:(test1_c)
 ; CHECK: Enqueuing a new RefSCC in the update worklist: [(test1_b)]
 ; CHECK: Switch an internal ref edge to a call edge from 'test1_a' to 'test1_c'
 ; CHECK: Switch an internal ref edge to a call edge from 'test1_a' to 'test1_a'
 ; CHECK: Re-running SCC passes after a refinement of the current SCC: (test1_c, test1_a)
 ; CHECK: Skipping redundant run on SCC: (test1_c, test1_a)
 ; CHECK: Skipping an SCC that is now part of some other RefSCC...
entry:
   ret void
 }
 
 define void @test1_c(i32 %num) #0 {
   call void @test1_a(i32 %num)
   ret void
 }
 
-attributes #0 = { noinline nounwind optnone }
+attributes #0 = { noinline nounwind optnone }
 

llvm/test/Transforms/Inline/cgscc-cycle.ll

 ; {test3_a, test3_b}, immediately after the newly added ref edge
 ; test3_a->test3_c will be converted to a call edge, and the two SCCs will be
 ; merged into the original one again. During this cycle, the original SCC will
 ; be added into UR.CWorklist again and this creates an infinite loop.
 
 @a = global i64 0
 @b = global i64 0
 
-define void @test3_c(i32 %i) {
+; Check test3_c is inlined into test3_a once and only once.
+; CHECK-LABEL: @test3_a(
+; CHECK: tail call void @test3_b()
+; CHECK-NEXT: tail call void @test3_d(i32 5)
+; CHECK-NEXT: %[[LD1:.*]] = load i64, i64* @a
+; CHECK-NEXT: %[[ADD1:.*]] = add nsw i64 %[[LD1]], 1
+; CHECK-NEXT: store i64 %[[ADD1]], i64* @a
+; CHECK-NEXT: %[[LD2:.*]] = load i64, i64* @b
+; CHECK-NEXT: %[[ADD2:.*]] = add nsw i64 %[[LD2]], 5
+; CHECK-NEXT: store i64 %[[ADD2]], i64* @b
+; CHECK-NEXT: ret void
+
+; Function Attrs: noinline
+define void @test3_a() #0 {
 entry:
-  %cmp = icmp eq i32 %i, 5
-  br i1 %cmp, label %if.end, label %if.then
+  tail call void @test3_b()
+  tail call void @test3_c(i32 5)
+  %t0 = load i64, i64* @b
+  %add = add nsw i64 %t0, 5
+  store i64 %add, i64* @b
+  ret void
+}
 
-if.then:                                          ; preds = %entry
-  %call = tail call i64 @random()
+; Function Attrs: noinline
+define void @test3_b() #0 {
+entry:
+  tail call void @test3_a()
   %t0 = load i64, i64* @a
-  %add = add nsw i64 %t0, %call
+  %add = add nsw i64 %t0, 2
   store i64 %add, i64* @a
-  br label %if.end
-
-if.end:                                           ; preds = %entry, %if.then
-  tail call void @test3_d(i32 %i)
-  %t6 = load i64, i64* @a
-  %add85 = add nsw i64 %t6, 1
-  store i64 %add85, i64* @a
   ret void
 }
 
-declare i64 @random()
-
 define void @test3_d(i32 %i) {
 entry:
   %cmp = icmp eq i32 %i, 5
   br i1 %cmp, label %if.end, label %if.then
 
 if.then:                                          ; preds = %entry
   %call = tail call i64 @random()
   %t0 = load i64, i64* @a
   %add = add nsw i64 %t0, %call
   store i64 %add, i64* @a
   br label %if.end
 
 if.end:                                           ; preds = %entry, %if.then
   tail call void @test3_c(i32 %i)
   tail call void @test3_b()
   %t6 = load i64, i64* @a
   %add79 = add nsw i64 %t6, 3
   store i64 %add79, i64* @a
   ret void
 }
 
-; Function Attrs: noinline
-define void @test3_b() #0 {
+define void @test3_c(i32 %i) {
 entry:
-  tail call void @test3_a()
+  %cmp = icmp eq i32 %i, 5
+  br i1 %cmp, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call i64 @random()
   %t0 = load i64, i64* @a
-  %add = add nsw i64 %t0, 2
+  %add = add nsw i64 %t0, %call
   store i64 %add, i64* @a
-  ret void
-}
-
-; Check test3_c is inlined into test3_a once and only once.
-; CHECK-LABEL: @test3_a(
-; CHECK: tail call void @test3_b()
-; CHECK-NEXT: tail call void @test3_d(i32 5)
-; CHECK-NEXT: %[[LD1:.*]] = load i64, i64* @a
-; CHECK-NEXT: %[[ADD1:.*]] = add nsw i64 %[[LD1]], 1
-; CHECK-NEXT: store i64 %[[ADD1]], i64* @a
-; CHECK-NEXT: %[[LD2:.*]] = load i64, i64* @b
-; CHECK-NEXT: %[[ADD2:.*]] = add nsw i64 %[[LD2]], 5
-; CHECK-NEXT: store i64 %[[ADD2]], i64* @b
-; CHECK-NEXT: ret void
+  br label %if.end
 
-; Function Attrs: noinline
-define void @test3_a() #0 {
-entry:
-  tail call void @test3_b()
-  tail call void @test3_c(i32 5)
-  %t0 = load i64, i64* @b
-  %add = add nsw i64 %t0, 5
-  store i64 %add, i64* @b
+if.end:                                           ; preds = %entry, %if.then
+  tail call void @test3_d(i32 %i)
+  %t6 = load i64, i64* @a
+  %add85 = add nsw i64 %t6, 1
+  store i64 %add85, i64* @a
   ret void
 }
 
+declare i64 @random()
+
 attributes #0 = { noinline }

llvm/test/Transforms/Inline/cgscc-incremental-invalidate.ll

 return:
   ret void
 }
 
 ; The 'test1_' prefixed functions work to carefully test that incrementally
 ; reducing an SCC in the inliner cannot accidentially leave stale function
 ; analysis results due to failing to invalidate them for all the functions.
 
-; The inliner visits this last function. It can't actually break any cycles
-; here, but because we visit this function we compute fresh analyses for it.
-; These analyses are then invalidated when we inline callee disrupting the
-; CFG, and it is important that they be freed.
-define void @test1_h() {
-; CHECK-LABEL: define void @test1_h()
+; We visit this function first in the inliner, and while we inline callee
+; perturbing the CFG, we don't inline anything else and the SCC structure
+; remains in tact.
+define void @test1_f() {
+; CHECK-LABEL: define void @test1_f()
 entry:
-  call void @test1_g()
+  ; We force this edge to survive inlining.
+  call void @test1_g() noinline
 ; CHECK: call void @test1_g()
 
   ; Pull interesting CFG into this function.
   call void @callee()
 ; CHECK-NOT: call void @callee()
 
   ret void
 ; CHECK: ret void
; CHECK: call void @test1_h()
   ; Pull interesting CFG into this function.
   call void @callee()
 ; CHECK-NOT: call void @callee()
 
   ret void
 ; CHECK: ret void
 }
 
-; We visit this function first in the inliner, and while we inline callee
-; perturbing the CFG, we don't inline anything else and the SCC structure
-; remains in tact.
-define void @test1_f() {
-; CHECK-LABEL: define void @test1_f()
+; The inliner visits this last function. It can't actually break any cycles
+; here, but because we visit this function we compute fresh analyses for it.
+; These analyses are then invalidated when we inline callee disrupting the
+; CFG, and it is important that they be freed.
+define void @test1_h() {
+; CHECK-LABEL: define void @test1_h()
 entry:
-  ; We force this edge to survive inlining.
-  call void @test1_g() noinline
+  call void @test1_g()
 ; CHECK: call void @test1_g()
 
   ; Pull interesting CFG into this function.
   call void @callee()
 ; CHECK-NOT: call void @callee()
 
   ret void
 ; CHECK: ret void

llvm/test/Transforms/Inline/cgscc-invalidate.ll

; CHECK: call void @callee
   ret void
 ; CHECK: ret void
 }
 
 
 ; The 'test3_' prefixed functions test the scenario of not inlining preserving
 ; dominators after splitting an SCC into two smaller SCCs.
 
-; This function ends up split into a separate SCC, which can cause its analyses
-; to become stale if the splitting doesn't properly invalidate things. Also, as
-; a consequence of being split out, test3_f is too large to inline by the time
-; we get here.
-define void @test3_g() {
-; CHECK-LABEL: define void @test3_g()
+; This function gets visited first and we end up inlining everything we
+; can into this routine. That splits test3_g into a separate SCC that is enqued
+; for later processing.
+define void @test3_f() {
+; CHECK-LABEL: define void @test3_f()
 entry:
-  ; Create the second edge in the SCC cycle.
-  call void @test3_f()
+  ; Create the first edge in the SCC cycle.
+  call void @test3_g()
+; CHECK-NOT: @test3_g()
 ; CHECK: call void @test3_f()
 
   ; Pull interesting CFG into this function.
   call void @callee()
 ; CHECK-NOT: call void @callee()
 
   ret void
 ; CHECK: ret void
 }
 
-; The second function gets visited first and we end up inlining everything we
-; can into this routine. That splits test3_g into a separate SCC that is enqued
-; for later processing.
-define void @test3_f() {
-; CHECK-LABEL: define void @test3_f()
+; This function ends up split into a separate SCC, which can cause its analyses
+; to become stale if the splitting doesn't properly invalidate things. Also, as
+; a consequence of being split out, test3_f is too large to inline by the time
+; we get here.
+define void @test3_g() {
+; CHECK-LABEL: define void @test3_g()
 entry:
-  ; Create the first edge in the SCC cycle.
-  call void @test3_g()
-; CHECK-NOT: @test3_g()
+  ; Create the second edge in the SCC cycle.
+  call void @test3_f()
 ; CHECK: call void @test3_f()
 
   ; Pull interesting CFG into this function.
   call void @callee()
 ; CHECK-NOT: call void @callee()
 
   ret void
 ; CHECK: ret void
 }

llvm/test/Transforms/OpenMP/globalization_remarks.ll

 ; RUN: opt -passes=openmpopt -pass-remarks-analysis=openmp-opt -disable-output < %s 2>&1 | FileCheck %s
 ; ModuleID = 'declare_target_codegen_globalization.cpp'
 source_filename = "declare_target_codegen_globalization.cpp"
 target datalayout = "e-i64:64-i128:128-v16:16-v32:32-n16:32:64"
 target triple = "nvptx64-nvidia-cuda"
 
 %struct.ident_t = type { i32, i32, i32, i32, i8* }
 %struct._globalized_locals_ty = type { [32 x i32] }
 
 @0 = private unnamed_addr constant [56 x i8] c";declare_target_codegen_globalization.cpp;maini1;17;1;;\00", align 1
 @1 = private unnamed_addr constant %struct.ident_t { i32 0, i32 2, i32 1, i32 0, i8* getelementptr inbounds ([56 x i8], [56 x i8]* @0, i32 0, i32 0) }, align 8
 @__omp_offloading_801_3022563__Z6maini1v_l17_exec_mode = weak constant i8 0
 @llvm.compiler.used = appending global [1 x i8*] [i8* @__omp_offloading_801_3022563__Z6maini1v_l17_exec_mode], section "llvm.metadata"
 
-; CHECK: remark: declare_target_codegen_globalization.cpp:10:1: Found thread data sharing on the GPU. Expect degraded performance due to data globalization.
 ; CHECK: remark: declare_target_codegen_globalization.cpp:17:1: Found thread data sharing on the GPU. Expect degraded performance due to data globalization.
+; CHECK: remark: declare_target_codegen_globalization.cpp:10:1: Found thread data sharing on the GPU. Expect degraded performance due to data globalization.
 
 ; Function Attrs: norecurse nounwind
 define weak void @__omp_offloading_801_3022563__Z6maini1v_l17(i32* nonnull align 4 dereferenceable(4) %a) local_unnamed_addr #0 !dbg !10 {
 entry:
   %nvptx_num_threads = tail call i32 @llvm.nvvm.read.ptx.sreg.ntid.x(), !dbg !12, !range !13
   tail call void @__kmpc_spmd_kernel_init(i32 %nvptx_num_threads, i16 1, i16 0) #4, !dbg !12
   tail call void @__kmpc_data_sharing_init_stack_spmd() #4, !dbg !12
   %0 = tail call i32 @__kmpc_global_thread_num(%struct.ident_t* nonnull @1)

llvm/test/Transforms/OpenMP/parallel_region_merging.ll

 ;   void merge_cancellable_regions(int cancel1, int cancel2)
 ;   {
 ;   #pragma omp parallel
 ;       {
 ;           if(cancel1) {
 ;   #pragma omp cancel parallel
 ;           }
 ;       }
-;   
 ;   #pragma omp parallel
 ;       {
 ;           if (cancel2) {
 ;   #pragma omp cancel parallel
 ;           }
 ;       }
 ;   }
 ;

 !2 = !{i64 2, i64 -1, i64 -1, i1 true}
 ; CHECK-LABEL: define {{[^@]+}}@merge_all() local_unnamed_addr {
 ; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @__kmpc_global_thread_num(%struct.ident_t* noundef nonnull align 8 dereferenceable(24) [[GLOB1:@.*]])
 ; CHECK-NEXT:    [[TMP2:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    store i32 1, i32* [[TMP2]], align 4
 ; CHECK-NEXT:    [[OMP_GLOBAL_THREAD_NUM:%.*]] = call i32 @__kmpc_global_thread_num(%struct.ident_t* [[GLOB1]])
 ; CHECK-NEXT:    br label [[OMP_PARALLEL:%.*]]
 ; CHECK:       omp_parallel:
-; CHECK-NEXT:    call void (%struct.ident_t*, i32, void (i32*, i32*, ...)*, ...) @__kmpc_fork_call(%struct.ident_t* [[GLOB1]], i32 1, void (i32*, i32*, ...)* bitcast (void (i32*, i32*, i32*)* @merge_all..omp_par.3 to void (i32*, i32*, ...)*), i32* [[TMP2]])
+; CHECK-NEXT:    call void (%struct.ident_t*, i32, void (i32*, i32*, ...)*, ...) @__kmpc_fork_call(%struct.ident_t* [[GLOB1]], i32 1, void (i32*, i32*, ...)* bitcast (void (i32*, i32*, i32*)* @merge_all..omp_par.2 to void (i32*, i32*, ...)*), i32* [[TMP2]])
 ; CHECK-NEXT:    br label [[OMP_PAR_OUTLINED_EXIT:%.*]]
 ; CHECK:       omp.par.outlined.exit:
 ; CHECK-NEXT:    br label [[OMP_PAR_EXIT_SPLIT:%.*]]
 ; CHECK:       omp.par.exit.split:
 ; CHECK-NEXT:    br label [[DOTSPLIT_SPLIT:%.*]]
 ; CHECK:       .split.split:
 ; CHECK-NEXT:    ret void
 ;
 ;
-; CHECK-LABEL: define {{[^@]+}}@merge_all..omp_par.3
+; CHECK-LABEL: define {{[^@]+}}@merge_all..omp_par.2
 ; CHECK-SAME: (i32* noalias [[TID_ADDR:%.*]], i32* noalias [[ZERO_ADDR:%.*]], i32* [[TMP0:%.*]]) [[ATTR0:#.*]] {
 ; CHECK-NEXT:  omp.par.entry:
 ; CHECK-NEXT:    [[TID_ADDR_LOCAL:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[TID_ADDR]], align 4
 ; CHECK-NEXT:    store i32 [[TMP1]], i32* [[TID_ADDR_LOCAL]], align 4
 ; CHECK-NEXT:    [[TID:%.*]] = load i32, i32* [[TID_ADDR_LOCAL]], align 4
 ; CHECK-NEXT:    br label [[OMP_PAR_REGION:%.*]]
 ; CHECK:       omp.par.outlined.exit.exitStub:

 ; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @__kmpc_global_thread_num(%struct.ident_t* noundef nonnull align 8 dereferenceable(24) [[GLOB1]])
 ; CHECK-NEXT:    [[TMP2:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    store i32 1, i32* [[TMP2]], align 4
 ; CHECK-NEXT:    call void (%struct.ident_t*, i32, void (i32*, i32*, ...)*, ...) @__kmpc_fork_call(%struct.ident_t* noundef nonnull align 8 dereferenceable(24) [[GLOB1]], i32 noundef 1, void (i32*, i32*, ...)* noundef bitcast (void (i32*, i32*, i32*)* @merge_some..omp_par to void (i32*, i32*, ...)*), i32* nocapture nofree noundef nonnull writeonly align 4 dereferenceable(4) [[TMP2]])
 ; CHECK-NEXT:    store i32 3, i32* [[TMP2]], align 4
 ; CHECK-NEXT:    [[OMP_GLOBAL_THREAD_NUM:%.*]] = call i32 @__kmpc_global_thread_num(%struct.ident_t* [[GLOB1]])
 ; CHECK-NEXT:    br label [[OMP_PARALLEL:%.*]]
 ; CHECK:       omp_parallel:
-; CHECK-NEXT:    call void (%struct.ident_t*, i32, void (i32*, i32*, ...)*, ...) @__kmpc_fork_call(%struct.ident_t* [[GLOB1]], i32 1, void (i32*, i32*, ...)* bitcast (void (i32*, i32*, i32*)* @merge_some..omp_par.2 to void (i32*, i32*, ...)*), i32* [[TMP2]])
+; CHECK-NEXT:    call void (%struct.ident_t*, i32, void (i32*, i32*, ...)*, ...) @__kmpc_fork_call(%struct.ident_t* [[GLOB1]], i32 1, void (i32*, i32*, ...)* bitcast (void (i32*, i32*, i32*)* @merge_some..omp_par.5 to void (i32*, i32*, ...)*), i32* [[TMP2]])
 ; CHECK-NEXT:    br label [[OMP_PAR_OUTLINED_EXIT:%.*]]
 ; CHECK:       omp.par.outlined.exit:
 ; CHECK-NEXT:    br label [[OMP_PAR_EXIT_SPLIT:%.*]]
 ; CHECK:       omp.par.exit.split:
 ; CHECK-NEXT:    br label [[DOTSPLIT_SPLIT:%.*]]
 ; CHECK:       .split.split:
 ; CHECK-NEXT:    ret void
 ;
 ;
-; CHECK-LABEL: define {{[^@]+}}@merge_some..omp_par.2
+; CHECK-LABEL: define {{[^@]+}}@merge_some..omp_par.5
 ; CHECK-SAME: (i32* noalias [[TID_ADDR:%.*]], i32* noalias [[ZERO_ADDR:%.*]], i32* [[TMP0:%.*]]) [[ATTR0]] {
 ; CHECK-NEXT:  omp.par.entry:
 ; CHECK-NEXT:    [[TID_ADDR_LOCAL:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[TID_ADDR]], align 4
 ; CHECK-NEXT:    store i32 [[TMP1]], i32* [[TID_ADDR_LOCAL]], align 4
 ; CHECK-NEXT:    [[TID:%.*]] = load i32, i32* [[TID_ADDR_LOCAL]], align 4
 ; CHECK-NEXT:    br label [[OMP_PAR_REGION:%.*]]
 ; CHECK:       omp.par.outlined.exit.exitStub:

 ; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @__kmpc_global_thread_num(%struct.ident_t* noundef nonnull align 8 dereferenceable(24) [[GLOB1]])
 ; CHECK-NEXT:    [[TMP4:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[TMP5:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    store i32 [[TMP0]], i32* [[TMP4]], align 4
 ; CHECK-NEXT:    store i32 [[TMP1]], i32* [[TMP5]], align 4
 ; CHECK-NEXT:    [[OMP_GLOBAL_THREAD_NUM:%.*]] = call i32 @__kmpc_global_thread_num(%struct.ident_t* [[GLOB1]])
 ; CHECK-NEXT:    br label [[OMP_PARALLEL:%.*]]
 ; CHECK:       omp_parallel:
-; CHECK-NEXT:    call void (%struct.ident_t*, i32, void (i32*, i32*, ...)*, ...) @__kmpc_fork_call(%struct.ident_t* [[GLOB1]], i32 2, void (i32*, i32*, ...)* bitcast (void (i32*, i32*, i32*, i32*)* @merge_cancellable_regions..omp_par.1 to void (i32*, i32*, ...)*), i32* [[TMP4]], i32* [[TMP5]])
+; CHECK-NEXT:    call void (%struct.ident_t*, i32, void (i32*, i32*, ...)*, ...) @__kmpc_fork_call(%struct.ident_t* [[GLOB1]], i32 2, void (i32*, i32*, ...)* bitcast (void (i32*, i32*, i32*, i32*)* @merge_cancellable_regions..omp_par.6 to void (i32*, i32*, ...)*), i32* [[TMP4]], i32* [[TMP5]])
 ; CHECK-NEXT:    br label [[OMP_PAR_OUTLINED_EXIT:%.*]]
 ; CHECK:       omp.par.outlined.exit:
 ; CHECK-NEXT:    br label [[OMP_PAR_EXIT_SPLIT:%.*]]
 ; CHECK:       omp.par.exit.split:
 ; CHECK-NEXT:    br label [[DOTSPLIT_SPLIT:%.*]]
 ; CHECK:       .split.split:
 ; CHECK-NEXT:    ret void
 ;
 ;
-; CHECK-LABEL: define {{[^@]+}}@merge_cancellable_regions..omp_par.1
+; CHECK-LABEL: define {{[^@]+}}@merge_cancellable_regions..omp_par.6
 ; CHECK-SAME: (i32* noalias [[TID_ADDR:%.*]], i32* noalias [[ZERO_ADDR:%.*]], i32* [[TMP0:%.*]], i32* [[TMP1:%.*]]) [[ATTR0]] {
 ; CHECK-NEXT:  omp.par.entry:
 ; CHECK-NEXT:    [[TID_ADDR_LOCAL:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[TID_ADDR]], align 4
 ; CHECK-NEXT:    store i32 [[TMP2]], i32* [[TID_ADDR_LOCAL]], align 4
 ; CHECK-NEXT:    [[TID:%.*]] = load i32, i32* [[TID_ADDR_LOCAL]], align 4
 ; CHECK-NEXT:    br label [[OMP_PAR_REGION:%.*]]
 ; CHECK:       omp.par.outlined.exit.exitStub:

llvm/unittests/Analysis/CGSCCPassManagerTest.cpp

CGSCCPassManagerTest()
             // |  |  |
             // |  h2 |
             // |  |  |
             // |  h3 |
             // | / \_/
             // |/
             // x
             //
-            "define void @f() {\n"
+            "define void @x() {\n"
+            "entry:\n"
+            "  ret void\n"
+            "}\n"
+            "define void @h3() {\n"
             "entry:\n"
-            "  call void @g()\n"
             "  call void @h1()\n"
             "  ret void\n"
             "}\n"
-            "define void @g() {\n"
+            "define void @h2() {\n"
             "entry:\n"
-            "  call void @g()\n"
+            "  call void @h3()\n"
             "  call void @x()\n"
             "  ret void\n"
             "}\n"
             "define void @h1() {\n"
             "entry:\n"
             "  call void @h2()\n"
             "  ret void\n"
             "}\n"
-            "define void @h2() {\n"
+            "define void @g() {\n"
             "entry:\n"
-            "  call void @h3()\n"
+            "  call void @g()\n"
             "  call void @x()\n"
             "  ret void\n"
             "}\n"
-            "define void @h3() {\n"
+            "define void @f() {\n"
             "entry:\n"
+            "  call void @g()\n"
             "  call void @h1()\n"
             "  ret void\n"
-            "}\n"
-            "define void @x() {\n"
-            "entry:\n"
-            "  ret void\n"
             "}\n")) {
     FAM.registerPass([&] { return TargetLibraryAnalysis(); });
     MAM.registerPass([&] { return LazyCallGraphAnalysis(); });
     MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); });
 
     // Register required pass instrumentation analysis.
     MAM.registerPass([&] { return PassInstrumentationAnalysis(); });
     CGAM.registerPass([&] { return PassInstrumentationAnalysis(); });

llvm/unittests/Analysis/LazyCallGraphTest.cpp

TEST(LazyCallGraphTest, BasicGraphFormation) {
   EXPECT_EQ("d3", Nodes[2]);
   Nodes.clear();
   EXPECT_FALSE(D.isParentOf(D));
   EXPECT_FALSE(D.isChildOf(D));
   EXPECT_FALSE(D.isAncestorOf(D));
   EXPECT_FALSE(D.isDescendantOf(D));
   EXPECT_EQ(&D, &*CG.postorder_ref_scc_begin());
 
-  LazyCallGraph::RefSCC &C = *J++;
-  ASSERT_EQ(1, C.size());
-  for (LazyCallGraph::Node &N : *C.begin())
-    Nodes.push_back(std::string(N.getFunction().getName()));
-  llvm::sort(Nodes);
-  EXPECT_EQ(3u, Nodes.size());
-  EXPECT_EQ("c1", Nodes[0]);
-  EXPECT_EQ("c2", Nodes[1]);
-  EXPECT_EQ("c3", Nodes[2]);
-  Nodes.clear();
-  EXPECT_TRUE(C.isParentOf(D));
-  EXPECT_FALSE(C.isChildOf(D));
-  EXPECT_TRUE(C.isAncestorOf(D));
-  EXPECT_FALSE(C.isDescendantOf(D));
-  EXPECT_EQ(&C, &*std::next(CG.postorder_ref_scc_begin()));
-
   LazyCallGraph::RefSCC &B = *J++;
   ASSERT_EQ(1, B.size());
   for (LazyCallGraph::Node &N : *B.begin())
     Nodes.push_back(std::string(N.getFunction().getName()));
   llvm::sort(Nodes);
   EXPECT_EQ(3u, Nodes.size());
   EXPECT_EQ("b1", Nodes[0]);
   EXPECT_EQ("b2", Nodes[1]);
   EXPECT_EQ("b3", Nodes[2]);
   Nodes.clear();
   EXPECT_TRUE(B.isParentOf(D));
   EXPECT_FALSE(B.isChildOf(D));
   EXPECT_TRUE(B.isAncestorOf(D));
   EXPECT_FALSE(B.isDescendantOf(D));
+  EXPECT_EQ(&B, &*std::next(CG.postorder_ref_scc_begin()));
+
+  LazyCallGraph::RefSCC &C = *J++;
+  ASSERT_EQ(1, C.size());
+  for (LazyCallGraph::Node &N : *C.begin())
+    Nodes.push_back(std::string(N.getFunction().getName()));
+  llvm::sort(Nodes);
+  EXPECT_EQ(3u, Nodes.size());
+  EXPECT_EQ("c1", Nodes[0]);
+  EXPECT_EQ("c2", Nodes[1]);
+  EXPECT_EQ("c3", Nodes[2]);
+  Nodes.clear();
   EXPECT_FALSE(B.isAncestorOf(C));
   EXPECT_FALSE(C.isAncestorOf(B));
-  EXPECT_EQ(&B, &*std::next(CG.postorder_ref_scc_begin(), 2));
+  EXPECT_TRUE(C.isParentOf(D));
+  EXPECT_FALSE(C.isChildOf(D));
+  EXPECT_TRUE(C.isAncestorOf(D));
+  EXPECT_FALSE(C.isDescendantOf(D));
+  EXPECT_EQ(&C, &*std::next(CG.postorder_ref_scc_begin(), 2));
 
   LazyCallGraph::RefSCC &A = *J++;
   ASSERT_EQ(1, A.size());
   for (LazyCallGraph::Node &N : *A.begin())
     Nodes.push_back(std::string(N.getFunction().getName()));
   llvm::sort(Nodes);
   EXPECT_EQ(3u, Nodes.size());
   EXPECT_EQ("a1", Nodes[0]);
TEST(LazyCallGraphTest, InlineAndDeleteFunction) {
   EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
   EXPECT_TRUE(CRC.isParentOf(NewDRC));
 
   // Verify the post-order walk hasn't changed.
   auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
   ASSERT_NE(I, E);
   EXPECT_EQ(&NewDRC, &*I) << "Actual RefSCC: " << *I;
   ASSERT_NE(++I, E);
-  EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I;
-  ASSERT_NE(++I, E);
   EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
   ASSERT_NE(++I, E);
+  EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I;
+  ASSERT_NE(++I, E);
   EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
   EXPECT_EQ(++I, E);
 }
 
 TEST(LazyCallGraphTest, InternalEdgeMutation) {
   LLVMContext Context;
   std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
                                                      "entry:\n"
std::unique_ptr<Module> M =
                              "bb:\n"
                              "  store i8* blockaddress(@g, %bb), i8** %ptr\n"
                              "  ret void\n"
                              "}\n");
   LazyCallGraph CG = buildCG(*M);
 
   CG.buildRefSCCs();
   auto I = CG.postorder_ref_scc_begin();
-  LazyCallGraph::RefSCC &GRC = *I++;
   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_FALSE(GRC.isParentOf(FRC));
   EXPECT_FALSE(FRC.isParentOf(GRC));