Index: llvm/trunk/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp
+++ llvm/trunk/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp
@@ -2796,17 +2796,12 @@
   StatepointLiveSetTy Updated;
   findLiveSetAtInst(Inst, RevisedLivenessData, Updated);
 
-#ifndef NDEBUG
-  DenseSet<Value *> Bases;
-  for (auto KVPair : Info.PointerToBase)
-    Bases.insert(KVPair.second);
-#endif
-
   // We may have base pointers which are now live that weren't before.  We need
   // to update the PointerToBase structure to reflect this.
   for (auto V : Updated)
     if (Info.PointerToBase.insert({V, V}).second) {
-      assert(Bases.count(V) && "Can't find base for unexpected live value!");
+      assert(isKnownBaseResult(V) &&
+             "Can't find base for unexpected live value!");
       continue;
     }
 
Index: llvm/trunk/test/Transforms/RewriteStatepointsForGC/check_traversal_order.ll
===================================================================
--- llvm/trunk/test/Transforms/RewriteStatepointsForGC/check_traversal_order.ll
+++ llvm/trunk/test/Transforms/RewriteStatepointsForGC/check_traversal_order.ll
@@ -0,0 +1,38 @@
+; RUN: opt -S -rewrite-statepoints-for-gc < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @f()
+declare void @g(i8 addrspace(1)*, i8 addrspace(1)*)
+declare i32 @personality_function()
+
+; Make sure that we do not fail assertion because we process call of @g before
+; we process the call of @f.
+
+define void @test_01(i8 addrspace(1)* %p, i1 %cond) gc "statepoint-example" personality i32 ()* @personality_function {
+
+; CHECK-LABEL: @test_01(
+
+entry:
+  %tmp0 = insertelement <2 x i8 addrspace(1)*> undef, i8 addrspace(1)* %p, i32 0
+  %tmp1 = insertelement <2 x i8 addrspace(1)*> %tmp0, i8 addrspace(1)* %p, i32 1
+  %tmp2 = extractelement <2 x i8 addrspace(1)*> %tmp1, i32 1
+  %tmp3 = extractelement <2 x i8 addrspace(1)*> %tmp1, i32 0
+  br label %loop
+
+loop:
+  br i1 %cond, label %cond_block, label %exit
+
+cond_block:
+  br i1 %cond, label %backedge, label %exit
+
+exit:
+  %tmp4 = phi i8 addrspace(1)* [ %tmp2, %loop ], [ %tmp2, %cond_block ]
+  call void @g(i8 addrspace(1)* %tmp3, i8 addrspace(1)* %tmp4)
+  ret void
+
+backedge:
+  call void @f()
+  br label %loop
+}