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
@@ -126,6 +126,10 @@
   iterator begin() { return Root.Edges.begin(); }
   iterator end() { return Root.Edges.end(); }
   ProfiledCallGraphNode *getEntryNode() { return &Root; }
+  StringMap<ProfiledCallGraphNode> &getProfiledFunctions() {
+    return ProfiledFunctions;
+  }
+
   void addProfiledFunction(StringRef Name) {
     if (!ProfiledFunctions.count(Name)) {
       // Link to synthetic root to make sure every node is reachable
@@ -148,8 +152,9 @@
     auto EdgeIt = Edges.find(Edge);
     if (EdgeIt == Edges.end()) {
       Edges.insert(Edge);
-    } else if (EdgeIt->Weight < Edge.Weight) {
-      // Replace existing call edges with same target but smaller weight.
+    } else {
+      // Accumulate weight to the existing edge.
+      Edge.Weight += EdgeIt->Weight;
       Edges.erase(EdgeIt);
       Edges.insert(Edge);
     }
diff --git a/llvm/tools/llvm-profgen/CSPreInliner.cpp b/llvm/tools/llvm-profgen/CSPreInliner.cpp
--- a/llvm/tools/llvm-profgen/CSPreInliner.cpp
+++ b/llvm/tools/llvm-profgen/CSPreInliner.cpp
@@ -78,6 +78,22 @@
   std::vector<StringRef> Order;
   ProfiledCallGraph ProfiledCG(ContextTracker);
 
+  // Trim cold edges to get a more stable call graph. This allows for a more
+  // stable top-down order which in turns helps the stablity of the generated
+  // profile from run to run.
+  uint64_t ColdCountThreshold = ProfileSummaryBuilder::getColdCountThreshold(
+      (Summary->getDetailedSummary()));
+  for (auto &Node : ProfiledCG.getProfiledFunctions()) {
+    auto &Edges = Node.second.Edges;
+    auto I = Edges.begin();
+    while (I != Edges.end()) {
+      if (I->Weight <= ColdCountThreshold)
+        I = Edges.erase(I);
+      else
+        I++;
+    }
+  }
+
   // Now that we have a profiled call graph, construct top-down order
   // by building up SCC and reversing SCC order.
   scc_iterator<ProfiledCallGraph *> I = scc_begin(&ProfiledCG);