Index: lib/Transforms/IPO/Inliner.cpp
===================================================================
--- lib/Transforms/IPO/Inliner.cpp
+++ lib/Transforms/IPO/Inliner.cpp
@@ -846,7 +846,18 @@
   if (Calls.empty())
     return PreservedAnalyses::all();
 
-  // Capture updatable variables for the current SCC and RefSCC.
+  // Now that we have all of the call sites, move the ones whose callee also
+  // calls its caller to the end of the list to delay the creation of recursive
+  // functions.
+  unsigned FirstCallCanBecomeRecursive = Calls.size();
+  for (unsigned i = 0; i < FirstCallCanBecomeRecursive; ++i)
+    if (Function *Callee = Calls[i].first.getCalledFunction()) {
+      Function *Caller = Calls[i].first.getCaller();
+      if ((*CG.lookup(*Callee))->lookup(*CG.lookup(*Caller)))
+        std::swap(Calls[i--], Calls[--FirstCallCanBecomeRecursive]);
+    }
+
+  // Capture updatable variables for the current SC and RefSCC.
   auto *C = &InitialC;
   auto *RC = &C->getOuterRefSCC();
 
Index: test/Transforms/Inline/cgscc-incremental-invalidate.ll
===================================================================
--- test/Transforms/Inline/cgscc-incremental-invalidate.ll
+++ test/Transforms/Inline/cgscc-incremental-invalidate.ll
@@ -7,8 +7,8 @@
 ; may stop testing anything.
 ;
 ; CHECK-LABEL: Starting llvm::Module pass manager run.
-; CHECK: Running pass: InlinerPass on (test1_f, test1_g, test1_h)
-; CHECK: Running analysis: FunctionAnalysisManagerCGSCCProxy on (test1_f, test1_g, test1_h)
+; CHECK: Running pass: InlinerPass on (test1_h, test1_g, test1_f)
+; CHECK: Running analysis: FunctionAnalysisManagerCGSCCProxy on (test1_h, test1_g, test1_f)
 ; CHECK: Running analysis: DominatorTreeAnalysis on test1_f
 ; CHECK: Running analysis: DominatorTreeAnalysis on test1_g
 ; CHECK: Invalidating all non-preserved analyses for: (test1_f)
@@ -17,26 +17,26 @@
 ; CHECK: Invalidating analysis: LoopAnalysis on test1_f
 ; CHECK: Invalidating analysis: BranchProbabilityAnalysis on test1_f
 ; CHECK: Invalidating analysis: BlockFrequencyAnalysis on test1_f
-; CHECK: Invalidating all non-preserved analyses for: (test1_g, test1_h)
-; CHECK: Invalidating all non-preserved analyses for: test1_g
-; CHECK: Invalidating analysis: DominatorTreeAnalysis on test1_g
-; CHECK: Invalidating analysis: LoopAnalysis on test1_g
-; CHECK: Invalidating analysis: BranchProbabilityAnalysis on test1_g
-; CHECK: Invalidating analysis: BlockFrequencyAnalysis on test1_g
+; CHECK: Invalidating all non-preserved analyses for: (test1_h, test1_g)
 ; CHECK: Invalidating all non-preserved analyses for: test1_h
 ; CHECK: Invalidating analysis: DominatorTreeAnalysis on test1_h
 ; CHECK: Invalidating analysis: LoopAnalysis on test1_h
 ; CHECK: Invalidating analysis: BranchProbabilityAnalysis on test1_h
 ; CHECK: Invalidating analysis: BlockFrequencyAnalysis on test1_h
+; CHECK: Invalidating all non-preserved analyses for: test1_g
+; CHECK: Invalidating analysis: DominatorTreeAnalysis on test1_g
+; CHECK: Invalidating analysis: LoopAnalysis on test1_g
+; CHECK: Invalidating analysis: BranchProbabilityAnalysis on test1_g
+; CHECK: Invalidating analysis: BlockFrequencyAnalysis on test1_g
 ; CHECK-NOT: Invalidating analysis:
 ; CHECK: Starting llvm::Function pass manager run.
-; CHECK-NEXT: Running pass: DominatorTreeVerifierPass on test1_g
-; CHECK-NEXT: Running analysis: DominatorTreeAnalysis on test1_g
-; CHECK-NEXT: Finished llvm::Function pass manager run.
-; CHECK-NEXT: Starting llvm::Function pass manager run.
 ; CHECK-NEXT: Running pass: DominatorTreeVerifierPass on test1_h
 ; CHECK-NEXT: Running analysis: DominatorTreeAnalysis on test1_h
 ; CHECK-NEXT: Finished llvm::Function pass manager run.
+; CHECK-NEXT: Starting llvm::Function pass manager run.
+; CHECK-NEXT: Running pass: DominatorTreeVerifierPass on test1_g
+; CHECK-NEXT: Running analysis: DominatorTreeAnalysis on test1_g
+; CHECK-NEXT: Finished llvm::Function pass manager run.
 ; CHECK-NOT: Invalidating analysis:
 ; CHECK: Running pass: DominatorTreeVerifierPass on test1_f
 ; CHECK-NEXT: Running analysis: DominatorTreeAnalysis on test1_f
@@ -69,14 +69,14 @@
 ; 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.
@@ -110,14 +110,14 @@
 ; 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.
Index: test/Transforms/Inline/cgscc-invalidate.ll
===================================================================
--- test/Transforms/Inline/cgscc-invalidate.ll
+++ test/Transforms/Inline/cgscc-invalidate.ll
@@ -65,15 +65,15 @@
 ; 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()
+; The function test3_f 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.
@@ -84,15 +84,15 @@
 ; 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.
Index: test/Transforms/Inline/cgscc-order.ll
===================================================================
--- /dev/null
+++ test/Transforms/Inline/cgscc-order.ll
@@ -0,0 +1,36 @@
+; RUN: opt < %s -passes='cgscc(inline)' -S -inline-threshold=30 | FileCheck %s
+
+@glbl = external global i32
+
+define void @out() {
+  store i32 0, i32* @glbl
+  store i32 1, i32* @glbl
+  store i32 2, i32* @glbl
+  store i32 3, i32* @glbl
+  store i32 4, i32* @glbl
+  store i32 5, i32* @glbl
+  store i32 6, i32* @glbl
+  store i32 7, i32* @glbl
+  store i32 8, i32* @glbl
+  store i32 9, i32* @glbl
+  ret void
+}
+
+define void @scc_a() {
+entry:
+  call void @scc_b()
+  call void @out()
+  ret void
+}
+
+define void @scc_b() {
+; CHECK-LABEL: define void @scc_b(
+; Make sure out is inlined into scc_a first so that scc_a is too big to be
+; inined into scc_b
+entry:
+; CHECK:    call
+; CHECK-NEXT:    ret
+  call void @scc_a()
+  ret void
+}
+
Index: test/Transforms/Inline/internal-scc-members.ll
===================================================================
--- test/Transforms/Inline/internal-scc-members.ll
+++ test/Transforms/Inline/internal-scc-members.ll
@@ -18,7 +18,7 @@
 ; CHECK-NOT: @test1_scc1
 define internal void @test1_scc1() {
 entry:
-  call void @test1_scc0()
+  call void @test1_scc0() noinline
   ret void
 }