diff --git a/llvm/include/llvm/Transforms/IPO/ProfiledCallGraph.h b/llvm/include/llvm/Transforms/IPO/ProfiledCallGraph.h
--- a/llvm/include/llvm/Transforms/IPO/ProfiledCallGraph.h
+++ b/llvm/include/llvm/Transforms/IPO/ProfiledCallGraph.h
@@ -87,8 +87,8 @@
     if (!ProfiledFunctions.count(Name)) {
       // Link to synthetic root to make sure every node is reachable
       // from root. This does not affect SCC order.
-      Root.Callees.insert(&ProfiledFunctions[Name]);
       ProfiledFunctions[Name] = ProfiledCallGraphNode(Name);
+      Root.Callees.insert(&ProfiledFunctions[Name]);
     }
   }