[MemProf] Context disambiguation cloning pass [patch 2/3]

[tejohnson]

Summary

Performs cloning on the CallsiteContextGraph (not on the IR or summary
index), in order to uniquely identify the allocation behavior of an
allocation call given its context. In order to do this, the graph is
recursively traversed starting from the allocation nodes, until we
identify a point where the allocation behavior is unambiguous (the edges
have a single allocation type). Nodes are then cloned as we unwind the
recursion. We try to perform the minimal amount of cloning required to
disambiguate the contexts.

The follow-on patch will contain the support for applying the cloning to
the IR.

Depends on D140908 and D145836.

[tejohnson]

I've attached the post-cloning dot file (and a png of it) for llvm/test/Transforms/PGHOContextDisambiguation/basic.ll.

basic.ll.tmp.ccg.cloned.dot2 KBDownload

[tejohnson]

Rebase on top of patch 1 changes.

[tejohnson]

Small fix made while testing on a large application

[snehasish]

llvm/lib/Transforms/IPO/PGHOContextDisambiguation.cpp

634 ↗

(On Diff #487954)

Should we use shared_ptr for edges so that we don't have to manually track ownership?

1959 ↗

(On Diff #487954)

nit: constexpr

2006 ↗

(On Diff #487954)

Still trying to understand this but it wasn't clear to me how we terminate this loop if we only increment the iterator here?

[tejohnson]

Finished rebasing the patch on the earlier commits.

llvm/lib/Transforms/IPO/PGHOContextDisambiguation.cpp

2006 ↗

(On Diff #487954)

See the calls to moveEdgeTo*CalleeClone below which takes the iterator. The current edge is erased from the iterator which is thus advanced. Mostly we terminate the loop when after enough cloning the Node has a single alloc type (see the break up near the top of the loop). Added a comment above the loop, and above the calls to moveEdgeTo* below.

[tejohnson]

Rebase on committed patches 1a/1b, address comments

[snehasish]

llvm/lib/Passes/PassBuilder.cpp

124 ↗

(On Diff #508269)

I don't see anything used from this header in this file?

llvm/lib/Transforms/IPO/MemProfContextDisambiguation.cpp

212

Should we assert that Clone->CloneOf is unset?

1204

I think this var shadows the LastNode var outside the loop nest. Is this intentional? Should we rename this var if not?

1963

nit: "iterate on that"?

1967

Should we bound the scope of CallerEdges just to make it clear to the reader and avoid accidental use?

A c++20 init-statement would be nice but we don't allow c++20 in LLVM yet.

1970

Can we also drop this Edge from the Node->CallerEdges set if both Caller and Callee are set to null?

1978

The code below allows 1 caller?

1987

Can we make this functor a static function defined after allocTypeToUse? AllocTypesMatch doesn't depend on any function local state and it contains another functor; reducing the nesting would make it easier to read. It is also defined a bit further away from the use.

2015

I think EnumeratedArray [1] is a good fit for this use case. I think it would also provide some checks against out of bounds access if the AllocType enum class changed.

[1] llvm-project/llvm/include/llvm/ADT/EnumeratedArray.h

2019

We only need to capture AllocTypeCloningPriority here. Do you know if a more permissive capture has any overhead?

2034

nit: cases

2039

auto CallerEdge would make the code below a little easier to read.

2048

nit: CalleeEdgeAllocTypesForCallerEdge.reserve(Node->CalleeEdges.size()); to avoid reallocations.

[tejohnson]

llvm/lib/Passes/PassBuilder.cpp

124 ↗

(On Diff #508269)

This turns out to be a merge issue. We actually do need the header (otherwise we get errors because of the use in PassRegistry.def which is included from this file), but I already have it included in the properly alphabetized location just above here at line 120. Removed this one.

llvm/lib/Transforms/IPO/MemProfContextDisambiguation.cpp

1204

Not intentional, but thankfully not causing a bug. I simply removed LastNode and use CurNode directly in the one use below.

1970

It would have been removed. Added assert.

1978

Fixed wording - I mean only a single caller.

2015

I don't think an EnumeratedArray will work, because index 3 is not an actual AllocationType enum value - it is the OR of the NotCold and Cold enumeration values (AllocTypes is a uint8_t as a result). As an aside I did not want to add it as an enum value because as we extend AllocationTypes with different types (as documented in the definition, all need to be powers of 2 to allow the ORing) you could presumably have various combinations, and it didn't seem practical to encode all of them in the enum itself.

Instead I added an "All" type to the enum that is documented as needing to be the OR of all values, and I use that in an assert here.

2019

I don't believe it adds overhead, just expresses intent to the frontend. In any case, turns out constexpr don't need to be captured, so I could remove the "&" completely.

[tejohnson]

Address comments

[snehasish]

lgtm

llvm/lib/Transforms/IPO/MemProfContextDisambiguation.cpp

2015

Sounds good, thanks for the explanation.

2019

TIL that constexpr doesn't need to be captured, makes sense in retrospect.

[tejohnson]

llvm/lib/Transforms/IPO/MemProfContextDisambiguation.cpp

2019

Well...it turns out it is not so simple. I got bot failures with other compilers that gave errors like:

'AllocTypeCloningPriority' cannot be implicitly captured because no default capture mode has been specified

I was able to reproduce an error building with gcc. Unfortunately, clang complains if I try to explicitly capture this constexpr variable. Therefore I am back to the earlier version that just had a default "&" capture.

[tejohnson]

Will update shortly with couple fixes for bot failures when building with other compilers. I'll wait until the bots settle down and I finish going through all the failures to make sure there aren't any other issues that show up before I push again.

[tejohnson]

Fixes for bot failures

[aganea]

llvm/lib/Transforms/IPO/MemProfContextDisambiguation.cpp

2001

Hello @tejohnson! Quite note - This patch fails on Windows with MSVC. Historically, MSVC has troubles capturing constexpr variables in lambdas (on L2018). Changing to const locally works. See diagnostics:

FAILED: lib/Transforms/IPO/CMakeFiles/LLVMipo.dir/MemProfContextDisambiguation.cpp.obj
C:\PROGRA~1\MIB055~1\2022\PROFES~1\VC\Tools\MSVC\1433~1.316\bin\HostX64\x64\cl.exe  /nologo /TP -DGTEST_HAS_RTTI=0 -DUNICODE -D_CRT_NONSTDC_NO_DEPRECATE -D_CRT_NONSTDC_NO_WARNINGS -D_CRT_SECURE_NO_DEPRECATE -D_CRT_SECURE_NO_WARNINGS -D_GLIBCXX_ASSERTIONS -D_HAS_EXCEPTIONS=0 -D_LIBCPP_ENABLE_ASSERTIONS -D_SCL_SECURE_NO_DEPRECATE -D_SCL_SECURE_NO_WARNINGS -D_UNICODE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -IC:\git\llvm-project\stage1_msvc_debug\lib\Transforms\IPO -IC:\git\llvm-project\llvm\lib\Transforms\IPO -IC:\git\llvm-project\stage1_msvc_debug\include -IC:\git\llvm-project\llvm\include /DWIN32 /D_WINDOWS   /Zc:inline /Zc:preprocessor /Zc:__cplusplus /Oi /bigobj /permissive- /W4 -wd4141 -wd4146 -wd4244 -wd4267 -wd4291 -wd4351 -wd4456 -wd4457 -wd4458 -wd4459 -wd4503 -wd4624 -wd4722 -wd4100 -wd4127 -wd4512 -wd4505 -wd4610 -wd4510 -wd4702 -wd4245 -wd4706 -wd4310 -wd4701 -wd4703 -wd4389 -wd4611 -wd4805 -wd4204 -wd4577 -wd4091 -wd4592 -wd4319 -wd4709 -wd5105 -wd4324 -w14062 -we4238 /MTd /Zi /Ob0 /Od /RTC1  /EHs-c- /GR- -std:c++17 /showIncludes /Folib\Transforms\IPO\CMakeFiles\LLVMipo.dir\MemProfContextDisambiguation.cpp.obj /Fdlib\Transforms\IPO\CMakeFiles\LLVMipo.dir\LLVMipo.pdb /FS -c C:\git\llvm-project\llvm\lib\Transforms\IPO\MemProfContextDisambiguation.cpp
C:\git\llvm-project\llvm\lib\Transforms\IPO\MemProfContextDisambiguation.cpp(2018): error C2326: 'bool CallsiteContextGraph<ModuleCallsiteContextGraph,llvm::Function,llvm::Instruction *>::identifyClones::<lambda_1>::operator ()(const std::shared_ptr<CallsiteContextGraph<ModuleCallsiteContextGraph,llvm::Function,llvm::Instruction *>::ContextEdge> &,const std::shared_ptr<CallsiteContextGraph<ModuleCallsiteContextGraph,llvm::Function,llvm::Instruction *>::ContextEdge> &) const': function cannot access 'AllocTypeCloningPriority'
C:\git\llvm-project\llvm\lib\Transforms\IPO\MemProfContextDisambiguation.cpp(1946): note: while compiling class template member function 'void CallsiteContextGraph<ModuleCallsiteContextGraph,llvm::Function,llvm::Instruction *>::identifyClones(CallsiteContextGraph<ModuleCallsiteContextGraph,llvm::Function,llvm::Instruction *>::ContextNode *,llvm::DenseSet<const CallsiteContextGraph<ModuleCallsiteContextGraph,llvm::Function,llvm::Instruction *>::ContextNode *,llvm::DenseMapInfo<ValueT,void>> &)'
        with
        [
            ValueT=const CallsiteContextGraph<ModuleCallsiteContextGraph,llvm::Function,llvm::Instruction *>::ContextNode *
        ]
C:\git\llvm-project\llvm\lib\Transforms\IPO\MemProfContextDisambiguation.cpp(1941): note: see reference to function template instantiation 'void CallsiteContextGraph<ModuleCallsiteContextGraph,llvm::Function,llvm::Instruction *>::identifyClones(CallsiteContextGraph<ModuleCallsiteContextGraph,llvm::Function,llvm::Instruction *>::ContextNode *,llvm::DenseSet<const CallsiteContextGraph<ModuleCallsiteContextGraph,llvm::Function,llvm::Instruction *>::ContextNode *,llvm::DenseMapInfo<ValueT,void>> &)' being compiled
        with
        [
            ValueT=const CallsiteContextGraph<ModuleCallsiteContextGraph,llvm::Function,llvm::Instruction *>::ContextNode *
        ]
C:\git\llvm-project\llvm\lib\Transforms\IPO\MemProfContextDisambiguation.cpp(1938): note: while compiling class template member function 'void CallsiteContextGraph<ModuleCallsiteContextGraph,llvm::Function,llvm::Instruction *>::identifyClones(void)'
C:\git\llvm-project\llvm\lib\Transforms\IPO\MemProfContextDisambiguation.cpp(2139): note: see reference to function template instantiation 'void CallsiteContextGraph<ModuleCallsiteContextGraph,llvm::Function,llvm::Instruction *>::identifyClones(void)' being compiled
C:\git\llvm-project\llvm\lib\Transforms\IPO\MemProfContextDisambiguation.cpp(2127): note: while compiling class template member function 'bool CallsiteContextGraph<ModuleCallsiteContextGraph,llvm::Function,llvm::Instruction *>::process(void)'
C:\git\llvm-project\llvm\lib\Transforms\IPO\MemProfContextDisambiguation.cpp(2159): note: see reference to function template instantiation 'bool CallsiteContextGraph<ModuleCallsiteContextGraph,llvm::Function,llvm::Instruction *>::process(void)' being compiled
C:\git\llvm-project\llvm\lib\Transforms\IPO\MemProfContextDisambiguation.cpp(470): note: see reference to class template instantiation 'CallsiteContextGraph<ModuleCallsiteContextGraph,llvm::Function,llvm::Instruction *>' being compiled
C:\git\llvm-project\llvm\lib\Transforms\IPO\MemProfContextDisambiguation.cpp(2019): error C2326: 'bool CallsiteContextGraph<ModuleCallsiteContextGraph,llvm::Function,llvm::Instruction *>::identifyClones::<lambda_1>::operator ()(const std::shared_ptr<CallsiteContextGraph<ModuleCallsiteContextGraph,llvm::Function,llvm::Instruction *>::ContextEdge> &,const std::shared_ptr<CallsiteContextGraph<ModuleCallsiteContextGraph,llvm::Function,llvm::Instruction *>::ContextEdge> &) const': function cannot access 'AllocTypeCloningPriority'
C:\git\llvm-project\llvm\lib\Transforms\IPO\MemProfContextDisambiguation.cpp(2018): error C2326: 'bool CallsiteContextGraph<IndexCallsiteContextGraph,llvm::FunctionSummary,IndexCall>::identifyClones::<lambda_1>::operator ()(const std::shared_ptr<CallsiteContextGraph<IndexCallsiteContextGraph,llvm::FunctionSummary,IndexCall>::ContextEdge> &,const std::shared_ptr<CallsiteContextGraph<IndexCallsiteContextGraph,llvm::FunctionSummary,IndexCall>::ContextEdge> &) const': function cannot access 'AllocTypeCloningPriority'
C:\git\llvm-project\llvm\lib\Transforms\IPO\MemProfContextDisambiguation.cpp(1946): note: while compiling class template member function 'void CallsiteContextGraph<IndexCallsiteContextGraph,llvm::FunctionSummary,IndexCall>::identifyClones(CallsiteContextGraph<IndexCallsiteContextGraph,llvm::FunctionSummary,IndexCall>::ContextNode *,llvm::DenseSet<const CallsiteContextGraph<IndexCallsiteContextGraph,llvm::FunctionSummary,IndexCall>::ContextNode *,llvm::DenseMapInfo<ValueT,void>> &)'
        with
        [
            ValueT=const CallsiteContextGraph<IndexCallsiteContextGraph,llvm::FunctionSummary,IndexCall>::ContextNode *
        ]
C:\git\llvm-project\llvm\lib\Transforms\IPO\MemProfContextDisambiguation.cpp(1941): note: see reference to function template instantiation 'void CallsiteContextGraph<IndexCallsiteContextGraph,llvm::FunctionSummary,IndexCall>::identifyClones(CallsiteContextGraph<IndexCallsiteContextGraph,llvm::FunctionSummary,IndexCall>::ContextNode *,llvm::DenseSet<const CallsiteContextGraph<IndexCallsiteContextGraph,llvm::FunctionSummary,IndexCall>::ContextNode *,llvm::DenseMapInfo<ValueT,void>> &)' being compiled
        with
        [
            ValueT=const CallsiteContextGraph<IndexCallsiteContextGraph,llvm::FunctionSummary,IndexCall>::ContextNode *
        ]
C:\git\llvm-project\llvm\lib\Transforms\IPO\MemProfContextDisambiguation.cpp(1938): note: while compiling class template member function 'void CallsiteContextGraph<IndexCallsiteContextGraph,llvm::FunctionSummary,IndexCall>::identifyClones(void)'
C:\git\llvm-project\llvm\lib\Transforms\IPO\MemProfContextDisambiguation.cpp(2139): note: see reference to function template instantiation 'void CallsiteContextGraph<IndexCallsiteContextGraph,llvm::FunctionSummary,IndexCall>::identifyClones(void)' being compiled
C:\git\llvm-project\llvm\lib\Transforms\IPO\MemProfContextDisambiguation.cpp(2127): note: while compiling class template member function 'bool CallsiteContextGraph<IndexCallsiteContextGraph,llvm::FunctionSummary,IndexCall>::process(void)'
C:\git\llvm-project\llvm\lib\Transforms\IPO\MemProfContextDisambiguation.cpp(2176): note: see reference to function template instantiation 'bool CallsiteContextGraph<IndexCallsiteContextGraph,llvm::FunctionSummary,IndexCall>::process(void)' being compiled
C:\git\llvm-project\llvm\lib\Transforms\IPO\MemProfContextDisambiguation.cpp(515): note: see reference to class template instantiation 'CallsiteContextGraph<IndexCallsiteContextGraph,llvm::FunctionSummary,IndexCall>' being compiled
C:\git\llvm-project\llvm\lib\Transforms\IPO\MemProfContextDisambiguation.cpp(2019): error C2326: 'bool CallsiteContextGraph<IndexCallsiteContextGraph,llvm::FunctionSummary,IndexCall>::identifyClones::<lambda_1>::operator ()(const std::shared_ptr<CallsiteContextGraph<IndexCallsiteContextGraph,llvm::FunctionSummary,IndexCall>::ContextEdge> &,const std::shared_ptr<CallsiteContextGraph<IndexCallsiteContextGraph,llvm::FunctionSummary,IndexCall>::ContextEdge> &) const': function cannot access 'AllocTypeCloningPriority'

[tejohnson]

llvm/lib/Transforms/IPO/MemProfContextDisambiguation.cpp

2001

Thanks for the report. I didn't see any bot failure reports - do you know if this showed up on one?

Just to confirm, I should remove the constexpr and make it:

const unsigned AllocTypeCloningPriority[] = ...

?

[tejohnson]

llvm/lib/Transforms/IPO/MemProfContextDisambiguation.cpp

2001

Also, just to confirm, is this is happening with the most recent version of the patch that was committed (a104e27030587507a711cef0e2b0ddb447fe68fe)? A number of compilers complained about the lambda capture of this constexpr before I changed it slightly.

[aganea]

llvm/lib/Transforms/IPO/MemProfContextDisambiguation.cpp

2001

Yes to both questions. From quickly browsing through the builders configs it seems none of them use MSVC 2022, where the issue happens.

[tejohnson]

llvm/lib/Transforms/IPO/MemProfContextDisambiguation.cpp

2001

Fixed in 969268831b9e409dd66af10c12fe17431e09b70f.

[aganea]

llvm/lib/Transforms/IPO/MemProfContextDisambiguation.cpp

2001

Thank you!

llvm/include/llvm/IR/ModuleSummaryIndex.h

inline raw_ostream &operator<<(raw_ostream &OS, const CallsiteInfo &SNI) {
   return OS;
 }
 
 // Allocation type assigned to an allocation reached by a given context.
 // More can be added but initially this is just noncold and cold.
 // Values should be powers of two so that they can be ORed, in particular to
 // track allocations that have different behavior with different calling
 // contexts.
-enum class AllocationType : uint8_t { None = 0, NotCold = 1, Cold = 2 };
+enum class AllocationType : uint8_t {
+  None = 0,
+  NotCold = 1,
+  Cold = 2,
+  All = 3 // This should always be set to the OR of all values.
+};
 
 /// Summary of a single MIB in a memprof metadata on allocations.
 struct MIBInfo {
   // The allocation type for this profiled context.
   AllocationType AllocType;
 
   // Represents stack ids in this context, recorded as indices into the
   // StackIds vector in the summary index, which in turn holds the full 64-bit

llvm/lib/Transforms/IPO/MemProfContextDisambiguation.cpp

 static cl::opt<bool>
     VerifyCCG("memprof-verify-ccg", cl::init(false), cl::Hidden,
               cl::desc("Perform verification checks on CallingContextGraph."));
 
 static cl::opt<bool>
     VerifyNodes("memprof-verify-nodes", cl::init(false), cl::Hidden,
                 cl::desc("Perform frequent verification checks on nodes."));
 
-inline bool hasSingleAllocType(uint8_t AllocTypes) {
-  switch (AllocTypes) {
-  case (uint8_t)AllocationType::Cold:
-  case (uint8_t)AllocationType::NotCold:
-    return true;
-    break;
-  case (uint8_t)AllocationType::None:
-    assert(false);
-    break;
-  default:
-    return false;
-    break;
-  }
-  llvm_unreachable("invalid alloc type");
-}
-
 /// CRTP base for graphs built from either IR or ThinLTO summary index.
 ///
 /// The graph represents the call contexts in all memprof metadata on allocation
 /// calls, with nodes for the allocations themselves, as well as for the calls
 /// in each context. The graph is initially built from the allocation memprof
 /// metadata (or summary) MIBs. It is then updated to match calls with callsite
 /// metadata onto the nodes, updating it to reflect any inlining performed on
 /// those calls.
 ///
 /// Each MIB (representing an allocation's call context with allocation
 /// behavior) is assigned a unique context id during the graph build. The edges
 /// and nodes in the graph are decorated with the context ids they carry. This
 /// is used to correctly update the graph when cloning is performed so that we
 /// can uniquify the context for a single (possibly cloned) allocation.
 template <typename DerivedCCG, typename FuncTy, typename CallTy>
 class CallsiteContextGraph {
 public:
   CallsiteContextGraph() = default;
   CallsiteContextGraph(const CallsiteContextGraph &) = default;
   CallsiteContextGraph(CallsiteContextGraph &&) = default;
 
   /// Main entry point to perform analysis and transformations on graph.
   bool process();
 
+  /// Perform cloning on the graph necessary to uniquely identify the allocation
+  /// behavior of an allocation based on its context.
+  void identifyClones();
+
   void dump() const;
   void print(raw_ostream &OS) const;
 
   friend raw_ostream &operator<<(raw_ostream &OS,
                                  const CallsiteContextGraph &CCG) {
     CCG.print(OS);
     return OS;
   }
struct ContextNode {
     // If a clone, points to the original uncloned node.
     ContextNode *CloneOf = nullptr;
 
     ContextNode(bool IsAllocation) : IsAllocation(IsAllocation), Call() {}
 
     ContextNode(bool IsAllocation, CallInfo C)
         : IsAllocation(IsAllocation), Call(C) {}
 
-    std::unique_ptr<ContextNode> clone() {
-      auto Clone = std::make_unique<ContextNode>(IsAllocation, Call);
+    void addClone(ContextNode *Clone) {
       if (CloneOf) {
-        CloneOf->Clones.push_back(Clone.get());
+        CloneOf->Clones.push_back(Clone);
         Clone->CloneOf = CloneOf;
       } else {
-        Clones.push_back(Clone.get());
+        Clones.push_back(Clone);
+        assert(!Clone->CloneOf);
         Clone->CloneOf = this;
       }
-      return Clone;
     }
 
     ContextNode *getOrigNode() {
       if (!CloneOf)
         return this;
       return CloneOf;
     }
 
struct ContextEdge {
     void print(raw_ostream &OS) const;
 
     friend raw_ostream &operator<<(raw_ostream &OS, const ContextEdge &Edge) {
       Edge.print(OS);
       return OS;
     }
   };
 
+  /// Helper to remove callee edges that have allocation type None (due to not
+  /// carrying any context ids) after transformations.
+  void removeNoneTypeCalleeEdges(ContextNode *Node);
+
 protected:
   /// Get a list of nodes corresponding to the stack ids in the given callsite
   /// context.
   template <class NodeT, class IteratorT>
   std::vector<uint64_t>
   getStackIdsWithContextNodes(CallStack<NodeT, IteratorT> &CallsiteContext);
 
   /// Adds nodes for the given allocation and any stack ids on its memprof MIB
private:
 
   /// Removes the node information recorded for the given call.
   void unsetNodeForInst(const CallInfo &C);
 
   /// Computes the alloc type corresponding to the given context ids, by
   /// unioning their recorded alloc types.
   uint8_t computeAllocType(DenseSet<uint32_t> &ContextIds);
 
+  /// Returns the alloction type of the intersection of the contexts of two
+  /// nodes (based on their provided context id sets), optimized for the case
+  /// when Node1Ids is smaller than Node2Ids.
+  uint8_t intersectAllocTypesImpl(const DenseSet<uint32_t> &Node1Ids,
+                                  const DenseSet<uint32_t> &Node2Ids);
+
+  /// Returns the alloction type of the intersection of the contexts of two
+  /// nodes (based on their provided context id sets).
+  uint8_t intersectAllocTypes(const DenseSet<uint32_t> &Node1Ids,
+                              const DenseSet<uint32_t> &Node2Ids);
+
+  /// Create a clone of Edge's callee and move Edge to that new callee node,
+  /// performing the necessary context id and allocation type updates.
+  /// If callee's caller edge iterator is supplied, it is updated when removing
+  /// the edge from that list.
+  ContextNode *
+  moveEdgeToNewCalleeClone(const std::shared_ptr<ContextEdge> &Edge,
+                           EdgeIter *CallerEdgeI = nullptr);
+
+  /// Change the callee of Edge to existing callee clone NewCallee, performing
+  /// the necessary context id and allocation type updates.
+  /// If callee's caller edge iterator is supplied, it is updated when removing
+  /// the edge from that list.
+  void moveEdgeToExistingCalleeClone(const std::shared_ptr<ContextEdge> &Edge,
+                                     ContextNode *NewCallee,
+                                     EdgeIter *CallerEdgeI = nullptr,
+                                     bool NewClone = false);
+
+  /// Recursively perform cloning on the graph for the given Node and its
+  /// callers, in order to uniquely identify the allocation behavior of an
+  /// allocation given its context.
+  void identifyClones(ContextNode *Node,
+                      DenseSet<const ContextNode *> &Visited);
+
   /// Map from each context ID to the AllocationType assigned to that context.
   std::map<uint32_t, AllocationType> ContextIdToAllocationType;
 
   /// Identifies the context node created for a stack id when adding the MIB
   /// contexts to the graph. This is used to locate the context nodes when
   /// trying to assign the corresponding callsites with those stack ids to these
   /// nodes.
   std::map<uint64_t, ContextNode *> StackEntryIdToContextNodeMap;
AllocationType allocTypeToUse(uint8_t AllocTypes) {
   assert(AllocTypes != (uint8_t)AllocationType::None);
   if (AllocTypes ==
       ((uint8_t)AllocationType::NotCold | (uint8_t)AllocationType::Cold))
     return AllocationType::NotCold;
   else
     return (AllocationType)AllocTypes;
 }
 
+// Helper to check if the alloc types for all edges recorded in the
+// InAllocTypes vector match the alloc types for all edges in the Edges
+// vector.
+template <typename DerivedCCG, typename FuncTy, typename CallTy>
+bool allocTypesMatch(
+    const std::vector<uint8_t> &InAllocTypes,
+    const std::vector<std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>>>
+        &Edges) {
+  return std::equal(
+      InAllocTypes.begin(), InAllocTypes.end(), Edges.begin(),
+      [](const uint8_t &l,
+         const std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>> &r) {
+        // Can share if one of the edges is None type - don't
+        // care about the type along that edge as it doesn't
+        // exist for those context ids.
+        if (l == (uint8_t)AllocationType::None ||
+            r->AllocTypes == (uint8_t)AllocationType::None)
+          return true;
+        return allocTypeToUse(l) == allocTypeToUse(r->AllocTypes);
+      });
+}
+
 } // end anonymous namespace
 
 template <typename DerivedCCG, typename FuncTy, typename CallTy>
 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
 CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getNodeForInst(
     const CallInfo &C) {
   ContextNode *Node = getNodeForAlloc(C);
   if (Node)
void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
   }
   std::shared_ptr<ContextEdge> Edge = std::make_shared<ContextEdge>(
       this, Caller, (uint8_t)AllocType, DenseSet<uint32_t>({ContextId}));
   CallerEdges.push_back(Edge);
   Caller->CalleeEdges.push_back(Edge);
 }
 
 template <typename DerivedCCG, typename FuncTy, typename CallTy>
+void CallsiteContextGraph<
+    DerivedCCG, FuncTy, CallTy>::removeNoneTypeCalleeEdges(ContextNode *Node) {
+  for (auto EI = Node->CalleeEdges.begin(); EI != Node->CalleeEdges.end();) {
+    auto Edge = *EI;
+    if (Edge->AllocTypes == (uint8_t)AllocationType::None) {
+      assert(Edge->ContextIds.empty());
+      Edge->Callee->eraseCallerEdge(Edge.get());
+      EI = Node->CalleeEdges.erase(EI);
+    } else
+      ++EI;
+  }
+}
+
+template <typename DerivedCCG, typename FuncTy, typename CallTy>
 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge *
 CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
     findEdgeFromCallee(const ContextNode *Callee) {
   for (const auto &Edge : CalleeEdges)
     if (Edge->Callee == Callee)
       return Edge.get();
   return nullptr;
 }
for (auto Id : ContextIds) {
     // Bail early if alloc type reached both, no further refinement.
     if (AllocType == BothTypes)
       return AllocType;
   }
   return AllocType;
 }
 
 template <typename DerivedCCG, typename FuncTy, typename CallTy>
+uint8_t
+CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::intersectAllocTypesImpl(
+    const DenseSet<uint32_t> &Node1Ids, const DenseSet<uint32_t> &Node2Ids) {
+  uint8_t BothTypes =
+      (uint8_t)AllocationType::Cold | (uint8_t)AllocationType::NotCold;
+  uint8_t AllocType = (uint8_t)AllocationType::None;
+  for (auto Id : Node1Ids) {
+    if (!Node2Ids.count(Id))
+      continue;
+    AllocType |= (uint8_t)ContextIdToAllocationType[Id];
+    // Bail early if alloc type reached both, no further refinement.
+    if (AllocType == BothTypes)
+      return AllocType;
+  }
+  return AllocType;
+}
+
+template <typename DerivedCCG, typename FuncTy, typename CallTy>
+uint8_t CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::intersectAllocTypes(
+    const DenseSet<uint32_t> &Node1Ids, const DenseSet<uint32_t> &Node2Ids) {
+  if (Node1Ids.size() < Node2Ids.size())
+    return intersectAllocTypesImpl(Node1Ids, Node2Ids);
+  else
+    return intersectAllocTypesImpl(Node2Ids, Node1Ids);
+}
+
+template <typename DerivedCCG, typename FuncTy, typename CallTy>
 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
 CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::addAllocNode(
     CallInfo Call, const FuncTy *F) {
   assert(!getNodeForAlloc(Call));
   NodeOwner.push_back(
       std::make_unique<ContextNode>(/*IsAllocation=*/true, Call));
   ContextNode *AllocNode = NodeOwner.back().get();
   AllocationCallToContextNodeMap[Call] = AllocNode;
for (unsigned I = 0; I < Calls.size(); I++) {
         if (StackSequenceContextIds.empty()) {
           Skip = true;
           break;
         }
       }
       if (Skip)
         continue;
 
       // If some of this call's stack ids did not have corresponding nodes (due
       // to pruning), don't include any context ids for contexts that extend
       // beyond these nodes. Otherwise we would be matching part of unrelated /
       // not fully matching stack contexts. To do this, subtract any context ids
       // found in caller nodes of the last node found above.
       if (Ids.back() != getLastStackId(Call)) {
-        for (auto PE : LastNode->CallerEdges) {
+        for (auto PE : CurNode->CallerEdges) {
           set_subtract(StackSequenceContextIds, PE->getContextIds());
           if (StackSequenceContextIds.empty())
             break;
         }
         // If we now have no context ids for clone, skip this call.
         if (StackSequenceContextIds.empty())
           continue;
       }
static void checkEdge(
     const std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>> &Edge) {
   // Confirm that alloc type is not None and that we have at least one context
   // id.
   assert(Edge->AllocTypes != (uint8_t)AllocationType::None);
   assert(!Edge->ContextIds.empty());
 }
 
 template <typename DerivedCCG, typename FuncTy, typename CallTy>
-static void checkNode(const ContextNode<DerivedCCG, FuncTy, CallTy> *Node) {
+static void checkNode(const ContextNode<DerivedCCG, FuncTy, CallTy> *Node,
+                      bool CheckEdges = false) {
   if (Node->isRemoved())
     return;
   // Node's context ids should be the union of both its callee and caller edge
   // context ids.
   if (Node->CallerEdges.size()) {
     auto EI = Node->CallerEdges.begin();
     auto &FirstEdge = *EI;
     EI++;
     DenseSet<uint32_t> CallerEdgeContextIds(FirstEdge->ContextIds);
     for (; EI != Node->CallerEdges.end(); EI++) {
       const auto &Edge = *EI;
+      if (CheckEdges)
+        checkEdge<DerivedCCG, FuncTy, CallTy>(Edge);
       set_union(CallerEdgeContextIds, Edge->ContextIds);
     }
     // Node can have more context ids than callers if some contexts terminate at
     // node and some are longer.
     assert(Node->ContextIds == CallerEdgeContextIds ||
            set_is_subset(CallerEdgeContextIds, Node->ContextIds));
   }
   if (Node->CalleeEdges.size()) {
     auto EI = Node->CalleeEdges.begin();
     auto &FirstEdge = *EI;
     EI++;
     DenseSet<uint32_t> CalleeEdgeContextIds(FirstEdge->ContextIds);
     for (; EI != Node->CalleeEdges.end(); EI++) {
       const auto &Edge = *EI;
+      if (CheckEdges)
+        checkEdge<DerivedCCG, FuncTy, CallTy>(Edge);
       set_union(CalleeEdgeContextIds, Edge->ContextIds);
     }
     assert(Node->ContextIds == CalleeEdgeContextIds);
   }
 }
 
 template <typename DerivedCCG, typename FuncTy, typename CallTy>
 void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::check() const {

 template <typename DerivedCCG, typename FuncTy, typename CallTy>
 void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::exportToDot(
     std::string Label) const {
   WriteGraph(this, "", false, Label,
              DotFilePathPrefix + "ccg." + Label + ".dot");
 }
 
 template <typename DerivedCCG, typename FuncTy, typename CallTy>
+ContextNode<DerivedCCG, FuncTy, CallTy> *
+CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::moveEdgeToNewCalleeClone(
+    const std::shared_ptr<ContextEdge> &Edge, EdgeIter *CallerEdgeI) {
+  ContextNode *Node = Edge->Callee;
+  NodeOwner.push_back(
+      std::make_unique<ContextNode>(Node->IsAllocation, Node->Call));
+  ContextNode *Clone = NodeOwner.back().get();
+  Node->addClone(Clone);
+  assert(NodeToCallingFunc.count(Node));
+  NodeToCallingFunc[Clone] = NodeToCallingFunc[Node];
+  moveEdgeToExistingCalleeClone(Edge, Clone, CallerEdgeI, /*NewClone=*/true);
+  return Clone;
+}
+
+template <typename DerivedCCG, typename FuncTy, typename CallTy>
+void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
+    moveEdgeToExistingCalleeClone(const std::shared_ptr<ContextEdge> &Edge,
+                                  ContextNode *NewCallee, EdgeIter *CallerEdgeI,
+                                  bool NewClone) {
+  // NewCallee and Edge's current callee must be clones of the same original
+  // node (Edge's current callee may be the original node too).
+  assert(NewCallee->getOrigNode() == Edge->Callee->getOrigNode());
+  auto &EdgeContextIds = Edge->getContextIds();
+  ContextNode *OldCallee = Edge->Callee;
+  if (CallerEdgeI)
+    *CallerEdgeI = OldCallee->CallerEdges.erase(*CallerEdgeI);
+  else
+    OldCallee->eraseCallerEdge(Edge.get());
+  Edge->Callee = NewCallee;
+  NewCallee->CallerEdges.push_back(Edge);
+  // Don't need to update Edge's context ids since we are simply reconnecting
+  // it.
+  set_subtract(OldCallee->ContextIds, EdgeContextIds);
+  NewCallee->ContextIds.insert(EdgeContextIds.begin(), EdgeContextIds.end());
+  NewCallee->AllocTypes |= Edge->AllocTypes;
+  OldCallee->AllocTypes = computeAllocType(OldCallee->ContextIds);
+  // OldCallee alloc type should be None iff its context id set is now empty.
+  assert((OldCallee->AllocTypes == (uint8_t)AllocationType::None) ==
+         OldCallee->ContextIds.empty());
+  // Now walk the old callee node's callee edges and move Edge's context ids
+  // over to the corresponding edge into the clone (which is created here if
+  // this is a newly created clone).
+  for (auto &OldCalleeEdge : OldCallee->CalleeEdges) {
+    // The context ids moving to the new callee are the subset of this edge's
+    // context ids and the context ids on the caller edge being moved.
+    DenseSet<uint32_t> EdgeContextIdsToMove =
+        set_intersection(OldCalleeEdge->getContextIds(), EdgeContextIds);
+    set_subtract(OldCalleeEdge->getContextIds(), EdgeContextIdsToMove);
+    OldCalleeEdge->AllocTypes =
+        computeAllocType(OldCalleeEdge->getContextIds());
+    if (!NewClone) {
+      // Update context ids / alloc type on corresponding edge to NewCallee.
+      // There is a chance this may not exist if we are reusing an existing
+      // clone, specifically during function assignment, where we would have
+      // removed none type edges after creating the clone. If we can't find
+      // a corresponding edge there, fall through to the cloning below.
+      if (auto *NewCalleeEdge =
+              NewCallee->findEdgeFromCallee(OldCalleeEdge->Callee)) {
+        NewCalleeEdge->getContextIds().insert(EdgeContextIdsToMove.begin(),
+                                              EdgeContextIdsToMove.end());
+        NewCalleeEdge->AllocTypes |= computeAllocType(EdgeContextIdsToMove);
+        continue;
+      }
+    }
+    auto NewEdge = std::make_shared<ContextEdge>(
+        OldCalleeEdge->Callee, NewCallee,
+        computeAllocType(EdgeContextIdsToMove), EdgeContextIdsToMove);
+    NewCallee->CalleeEdges.push_back(NewEdge);
+    NewEdge->Callee->CallerEdges.push_back(NewEdge);
+  }
+  if (VerifyCCG) {
+    checkNode<DerivedCCG, FuncTy, CallTy>(OldCallee);
+    checkNode<DerivedCCG, FuncTy, CallTy>(NewCallee);
+    for (const auto &OldCalleeEdge : OldCallee->CalleeEdges)
+      checkNode<DerivedCCG, FuncTy, CallTy>(OldCalleeEdge->Callee);
+    for (const auto &NewCalleeEdge : NewCallee->CalleeEdges)
+      checkNode<DerivedCCG, FuncTy, CallTy>(NewCalleeEdge->Callee);
+  }
+}
+
+template <typename DerivedCCG, typename FuncTy, typename CallTy>
+void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::identifyClones() {
+  DenseSet<const ContextNode *> Visited;
+  for (auto &Entry : AllocationCallToContextNodeMap)
+    identifyClones(Entry.second, Visited);
+}
+
+template <typename DerivedCCG, typename FuncTy, typename CallTy>
+void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::identifyClones(
+    ContextNode *Node, DenseSet<const ContextNode *> &Visited) {
+  if (VerifyNodes)
+    checkNode<DerivedCCG, FuncTy, CallTy>(Node, /*CheckEdges=*/true);
+  assert(!Node->CloneOf);
+
+  // If Node as a null call, then either it wasn't found in the module (regular
+  // LTO) or summary index (ThinLTO), or there were other conditions blocking
+  // cloning (e.g. recursion, calls multiple targets, etc).
+  // Do this here so that we don't try to recursively clone callers below, which
+  // isn't useful at least for this node.
+  if (!Node->hasCall())
+    return;
+
+#ifndef NDEBUG
+  auto Insert =
+#endif
+      Visited.insert(Node);
+  // We should not have visited this node yet.
+  assert(Insert.second);
+  // The recursive call to identifyClones may delete the current edge from the
+  // CallerEdges vector. Make a copy and iterate on that, simpler than passing
+  // in an iterator and having recursive call erase from it. Other edges may
+  // also get removed during the recursion, which will have null Callee and
+  // Caller pointers (and are deleted later), so we skip those below.
+  {
+    auto CallerEdges = Node->CallerEdges;
+    for (auto &Edge : CallerEdges) {
+      // Skip any that have been removed by an earlier recursive call.
+      if (Edge->Callee == nullptr && Edge->Caller == nullptr) {
+        assert(!std::count(Node->CallerEdges.begin(), Node->CallerEdges.end(),
+                           Edge));
+        continue;
+      }
+      // Ignore any caller we previously visited via another edge.
+      if (!Visited.count(Edge->Caller) && !Edge->Caller->CloneOf) {
+        identifyClones(Edge->Caller, Visited);
+      }
+    }
+  }
+
+  // Check if we reached an unambiguous call or have have only a single caller.
+  if (hasSingleAllocType(Node->AllocTypes) || Node->CallerEdges.size() <= 1)
+    return;
+
+  // We need to clone.
+
+  // Try to keep the original version as alloc type NotCold. This will make
+  // cases with indirect calls or any other situation with an unknown call to
+  // the original function get the default behavior. We do this by sorting the
+  // CallerEdges of the Node we will clone by alloc type.
+  //
+  // Give NotCold edge the lowest sort priority so those edges are at the end of
+  // the caller edges vector, and stay on the original version (since the below
+  // code clones greedily until it finds all remaining edges have the same type
+  // and leaves the remaining ones on the original Node).
+  //
+  // We shouldn't actually have any None type edges, so the sorting priority for
+  // that is arbitrary, and we assert in that case below.
+  constexpr unsigned AllocTypeCloningPriority[] = {/*None*/ 3, /*NotCold*/ 4,
+                                                   /*Cold*/ 1,
+                                                   /*NotColdCold*/ 2};
+  assert(std::size(AllocTypeCloningPriority) ==
+         (std::size_t)AllocationType::All + 1);
+  std::stable_sort(Node->CallerEdges.begin(), Node->CallerEdges.end(),
+                   [](const std::shared_ptr<ContextEdge> &A,
+                      const std::shared_ptr<ContextEdge> &B) {
+                     assert(A->AllocTypes != (uint8_t)AllocationType::None &&
+                            B->AllocTypes != (uint8_t)AllocationType::None);
+                     if (A->AllocTypes == B->AllocTypes)
+                       // Use the first context id for each edge as a
+                       // tie-breaker.
+                       return *A->ContextIds.begin() < *B->ContextIds.begin();
+                     return AllocTypeCloningPriority[A->AllocTypes] <
+                            AllocTypeCloningPriority[B->AllocTypes];
+                   });
+
+  assert(Node->AllocTypes != (uint8_t)AllocationType::None);
+
+  // Iterate until we find no more opportunities for disambiguating the alloc
+  // types via cloning. In most cases this loop will terminate once the Node
+  // has a single allocation type, in which case no more cloning is needed.
+  // We need to be able to remove Edge from CallerEdges, so need to adjust
+  // iterator inside the loop.
+  for (auto EI = Node->CallerEdges.begin(); EI != Node->CallerEdges.end();) {
+    auto CallerEdge = *EI;
+
+    // See if cloning the prior caller edge left this node with a single alloc
+    // type or a single caller. In that case no more cloning of Node is needed.
+    if (hasSingleAllocType(Node->AllocTypes) || Node->CallerEdges.size() <= 1)
+      break;
+
+    // Compute the node callee edge alloc types corresponding to the context ids
+    // for this caller edge.
+    std::vector<uint8_t> CalleeEdgeAllocTypesForCallerEdge;
+    CalleeEdgeAllocTypesForCallerEdge.reserve(Node->CalleeEdges.size());
+    for (auto &CalleeEdge : Node->CalleeEdges)
+      CalleeEdgeAllocTypesForCallerEdge.push_back(intersectAllocTypes(
+          CalleeEdge->getContextIds(), CallerEdge->getContextIds()));
+
+    // Don't clone if doing so will not disambiguate any alloc types amongst
+    // caller edges (including the callee edges that would be cloned).
+    // Otherwise we will simply move all edges to the clone.
+    //
+    // First check if by cloning we will disambiguate the caller allocation
+    // type from node's allocation type. Query allocTypeToUse so that we don't
+    // bother cloning to distinguish NotCold+Cold from NotCold. Note that
+    // neither of these should be None type.
+    //
+    // Then check if by cloning node at least one of the callee edges will be
+    // disambiguated by splitting out different context ids.
+    assert(CallerEdge->AllocTypes != (uint8_t)AllocationType::None);
+    assert(Node->AllocTypes != (uint8_t)AllocationType::None);
+    if (allocTypeToUse(CallerEdge->AllocTypes) ==
+            allocTypeToUse(Node->AllocTypes) &&
+        allocTypesMatch<DerivedCCG, FuncTy, CallTy>(
+            CalleeEdgeAllocTypesForCallerEdge, Node->CalleeEdges)) {
+      ++EI;
+      continue;
+    }
+
+    // First see if we can use an existing clone. Check each clone and its
+    // callee edges for matching alloc types.
+    ContextNode *Clone = nullptr;
+    for (auto *CurClone : Node->Clones) {
+      if (allocTypeToUse(CurClone->AllocTypes) !=
+          allocTypeToUse(CallerEdge->AllocTypes))
+        continue;
+
+      if (!allocTypesMatch<DerivedCCG, FuncTy, CallTy>(
+              CalleeEdgeAllocTypesForCallerEdge, CurClone->CalleeEdges))
+        continue;
+      Clone = CurClone;
+      break;
+    }
+
+    // The edge iterator is adjusted when we move the CallerEdge to the clone.
+    if (Clone)
+      moveEdgeToExistingCalleeClone(CallerEdge, Clone, &EI);
+    else
+      Clone = moveEdgeToNewCalleeClone(CallerEdge, &EI);
+
+    assert(EI == Node->CallerEdges.end() ||
+           Node->AllocTypes != (uint8_t)AllocationType::None);
+    // Sanity check that no alloc types on clone or its edges are None.
+    assert(Clone->AllocTypes != (uint8_t)AllocationType::None);
+    assert(llvm::none_of(
+        Clone->CallerEdges, [&](const std::shared_ptr<ContextEdge> &E) {
+          return E->AllocTypes == (uint8_t)AllocationType::None;
+        }));
+  }
+
+  // Cloning may have resulted in some cloned callee edges with type None,
+  // because they aren't carrying any contexts. Remove those edges.
+  for (auto *Clone : Node->Clones) {
+    removeNoneTypeCalleeEdges(Clone);
+    if (VerifyNodes)
+      checkNode<DerivedCCG, FuncTy, CallTy>(Clone, /*CheckEdges=*/true);
+  }
+  // We should still have some context ids on the original Node.
+  assert(!Node->ContextIds.empty());
+
+  // Remove any callee edges that ended up with alloc type None after creating
+  // clones and updating callee edges.
+  removeNoneTypeCalleeEdges(Node);
+
+  // Sanity check that no alloc types on node or edges are None.
+  assert(Node->AllocTypes != (uint8_t)AllocationType::None);
+  assert(llvm::none_of(Node->CalleeEdges,
+                       [&](const std::shared_ptr<ContextEdge> &E) {
+                         return E->AllocTypes == (uint8_t)AllocationType::None;
+                       }));
+  assert(llvm::none_of(Node->CallerEdges,
+                       [&](const std::shared_ptr<ContextEdge> &E) {
+                         return E->AllocTypes == (uint8_t)AllocationType::None;
+                       }));
+
+  if (VerifyNodes)
+    checkNode<DerivedCCG, FuncTy, CallTy>(Node, /*CheckEdges=*/true);
+}
+
+template <typename DerivedCCG, typename FuncTy, typename CallTy>
 bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::process() {
   if (DumpCCG) {
     dbgs() << "CCG before cloning:\n";
     dbgs() << *this;
   }
   if (ExportToDot)
     exportToDot("postbuild");
 
   if (VerifyCCG) {
     check();
   }
 
+  identifyClones();
+
+  if (VerifyCCG) {
+    check();
+  }
+
+  if (DumpCCG) {
+    dbgs() << "CCG after cloning:\n";
+    dbgs() << *this;
+  }
+  if (ExportToDot)
+    exportToDot("cloned");
+
   return false;
 }
 
 bool MemProfContextDisambiguation::processModule(Module &M) {
   bool Changed = false;
 
   ModuleCallsiteContextGraph CCG(M);
   Changed = CCG.process();

llvm/test/ThinLTO/X86/memprof-basic.ll

 ; RUN:  -r=%t.o,_ZdaPv, \
 ; RUN:  -r=%t.o,sleep, \
 ; RUN:  -r=%t.o,_Znam, \
 ; RUN:  -memprof-verify-ccg -memprof-verify-nodes -memprof-dump-ccg \
 ; RUN:  -memprof-export-to-dot -memprof-dot-file-path-prefix=%t. \
 ; RUN:  -o %t.out 2>&1 | FileCheck %s --check-prefix=DUMP
 
 ; RUN:  cat %t.ccg.postbuild.dot | FileCheck %s --check-prefix=DOT
+;; We should have cloned bar, baz, and foo, for the cold memory allocation.
+; RUN:  cat %t.ccg.cloned.dot | FileCheck %s --check-prefix=DOTCLONED
 
 
 source_filename = "memprof-basic.ll"
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define i32 @main() {
 entry:

 ; DUMP: Node [[MAIN2]]
 ; DUMP:   Callee: 6731117468105397038 (_Z3foov) Clones: 0 StackIds: 1 (clone 0)
 ; DUMP:   AllocTypes: Cold
 ; DUMP:   ContextIds: 2
 ; DUMP:   CalleeEdges:
 ; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 2
 ; DUMP:   CallerEdges:
 
+; DUMP: CCG after cloning:
+; DUMP: Callsite Context Graph:
+; DUMP: Node [[BAR]]
+; DUMP:   Versions: 1 MIB:
+; DUMP:                 AllocType 1 StackIds: 2, 3, 0
+; DUMP:                 AllocType 2 StackIds: 2, 3, 1
+; DUMP:         (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 1
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[BAZ]] AllocTypes: NotCold ContextIds: 1
+; DUMP:   Clones: [[BAR2:0x[a-z0-9]+]]
+
+; DUMP: Node [[BAZ]]
+; DUMP:   Callee: 9832687305761716512 (_Z3barv) Clones: 0 StackIds: 2    (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 1
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[BAZ]] AllocTypes: NotCold ContextIds: 1
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[BAZ]] to Caller: [[FOO]] AllocTypes: NotCold ContextIds: 1
+; DUMP:   Clones: [[BAZ2:0x[a-z0-9]+]]
+
+; DUMP: Node [[FOO]]
+; DUMP:   Callee: 5878270615442837395 (_Z3bazv) Clones: 0 StackIds: 3    (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 1
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAZ]] to Caller: [[FOO]] AllocTypes: NotCold ContextIds: 1
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN1]] AllocTypes: NotCold ContextIds: 1
+; DUMP:   Clones: [[FOO2:0x[a-z0-9]+]]
+
+; DUMP: Node [[MAIN1]]
+; DUMP:   Callee: 6731117468105397038 (_Z3foov) Clones: 0 StackIds: 0     (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 1
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN1]] AllocTypes: NotCold ContextIds: 1
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[MAIN2]]
+; DUMP:   Callee: 6731117468105397038 (_Z3foov) Clones: 0 StackIds: 1     (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 2
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[FOO2]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 2
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[FOO2]]
+; DUMP:   Callee: 5878270615442837395 (_Z3bazv) Clones: 0 StackIds: 3    (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 2
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAZ2]] to Caller: [[FOO2]] AllocTypes: Cold ContextIds: 2
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[FOO2]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 2
+; DUMP:   Clone of [[FOO]]
+
+; DUMP: Node [[BAZ2]]
+; DUMP:   Callee: 9832687305761716512 (_Z3barv) Clones: 0 StackIds: 2    (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 2
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAR2]] to Caller: [[BAZ2]] AllocTypes: Cold ContextIds: 2
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[BAZ2]] to Caller: [[FOO2]] AllocTypes: Cold ContextIds: 2
+; DUMP:   Clone of [[BAZ]]
+
+; DUMP: Node [[BAR2]]
+; DUMP:   Versions: 1 MIB:
+; DUMP:                 AllocType 1 StackIds: 2, 3, 0
+; DUMP:                 AllocType 2 StackIds: 2, 3, 1
+; DUMP:         (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 2
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[BAR2]] to Caller: [[BAZ2]] AllocTypes: Cold ContextIds: 2
+; DUMP:   Clone of [[BAR]]
+
 
 ; DOT: digraph "postbuild" {
 ; DOT:  label="postbuild";
 ; DOT:   Node[[BAR:0x[a-z0-9]+]] [shape=record,tooltip="N[[BAR]] ContextIds: 1 2",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: Alloc0\n_Z3barv -\> alloc}"];
 ; DOT:   Node[[BAZ:0x[a-z0-9]+]] [shape=record,tooltip="N[[BAZ]] ContextIds: 1 2",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 12481870273128938184\n_Z3bazv -\> _Z3barv}"];
 ; DOT:  Node[[BAZ]] -> Node[[BAR]][tooltip="ContextIds: 1 2",fillcolor="mediumorchid1"];
 ; DOT:   Node[[FOO:0x[a-z0-9]+]] [shape=record,tooltip="N[[FOO]] ContextIds: 1 2",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 2732490490862098848\n_Z3foov -\> _Z3bazv}"];
 ; DOT:  Node[[FOO]] -> Node[[BAZ]][tooltip="ContextIds: 1 2",fillcolor="mediumorchid1"];
 ; DOT:   Node[[MAIN1:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN1]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 8632435727821051414\nmain -\> _Z3foov}"];
 ; DOT:  Node[[MAIN1]] -> Node[[FOO]][tooltip="ContextIds: 1",fillcolor="brown1"];
 ; DOT:   Node[[MAIN2:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN2]] ContextIds: 2",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 15025054523792398438\nmain -\> _Z3foov}"];
 ; DOT:  Node[[MAIN2]] -> Node[[FOO]][tooltip="ContextIds: 2",fillcolor="cyan"];
 ; DOT: }
+
+
+; DOTCLONED: digraph "cloned" {
+; DOTCLONED:  label="cloned";
+; DOTCLONED:  Node[[BAR:0x[a-z0-9]+]] [shape=record,tooltip="N[[BAR]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled",label="{OrigId: Alloc0\n_Z3barv -\> alloc}"];
+; DOTCLONED:   Node[[BAZ:0x[a-z0-9]+]] [shape=record,tooltip="N[[BAZ]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 12481870273128938184\n_Z3bazv -\> _Z3barv}"];
+; DOTCLONED:  Node[[BAZ]] -> Node[[BAR]][tooltip="ContextIds: 1",fillcolor="brown1"];
+; DOTCLONED:   Node[[FOO:0x[a-z0-9]+]] [shape=record,tooltip="N[[FOO]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 2732490490862098848\n_Z3foov -\> _Z3bazv}"];
+; DOTCLONED:  Node[[FOO]] -> Node[[BAZ]][tooltip="ContextIds: 1",fillcolor="brown1"];
+; DOTCLONED:   Node[[MAIN1:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN1]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 8632435727821051414\nmain -\> _Z3foov}"];
+; DOTCLONED:  Node[[MAIN1]] -> Node[[FOO]][tooltip="ContextIds: 1",fillcolor="brown1"];
+; DOTCLONED:   Node[[MAIN2:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN2]] ContextIds: 2",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 15025054523792398438\nmain -\> _Z3foov}"];
+; DOTCLONED:  Node[[MAIN2]] -> Node[[FOO2:0x[a-z0-9]+]][tooltip="ContextIds: 2",fillcolor="cyan"];
+; DOTCLONED:   Node[[FOO2]] [shape=record,tooltip="N[[FOO2]] ContextIds: 2",fillcolor="cyan",style="filled",color="blue",style="filled,bold,dashed",label="{OrigId: 0\n_Z3foov -\> _Z3bazv}"];
+; DOTCLONED:  Node[[FOO2]] -> Node[[BAZ2:0x[a-z0-9]+]][tooltip="ContextIds: 2",fillcolor="cyan"];
+; DOTCLONED:   Node[[BAZ2]] [shape=record,tooltip="N[[BAZ2]] ContextIds: 2",fillcolor="cyan",style="filled",color="blue",style="filled,bold,dashed",label="{OrigId: 0\n_Z3bazv -\> _Z3barv}"];
+; DOTCLONED:  Node[[BAZ2]] -> Node[[BAR2:0x[a-z0-9]+]][tooltip="ContextIds: 2",fillcolor="cyan"];
+; DOTCLONED:   Node[[BAR2]] [shape=record,tooltip="N[[BAR2]] ContextIds: 2",fillcolor="cyan",style="filled",color="blue",style="filled,bold,dashed",label="{OrigId: Alloc0\n_Z3barv -\> alloc}"];
+; DOTCLONED: }

llvm/test/ThinLTO/X86/memprof-duplicate-context-ids.ll

 ; RUN:  -r=%t.o,sleep, \
 ; RUN:  -r=%t.o,_Znam, \
 ; RUN:  -memprof-verify-ccg -memprof-verify-nodes -memprof-dump-ccg \
 ; RUN:  -memprof-export-to-dot -memprof-dot-file-path-prefix=%t. \
 ; RUN:  -o %t.out 2>&1 | FileCheck %s --check-prefix=DUMP
 
 ; RUN:  cat %t.ccg.prestackupdate.dot | FileCheck %s --check-prefix=DOTPRE
 ; RUN:  cat %t.ccg.postbuild.dot | FileCheck %s --check-prefix=DOTPOST
+;; We should clone D once for the cold allocations via C.
+; RUN:  cat %t.ccg.cloned.dot | FileCheck %s --check-prefix=DOTCLONED
 
 
 source_filename = "duplicate-context-ids.ll"
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define internal ptr @_Z1Dv() {
 entry:

 ; DUMP:   Callee: 4881081444663423788 (_Z1Dv) Clones: 0 StackIds: 0, 3  (clone 0)
 ; DUMP:   AllocTypes: Cold
 ; DUMP:   ContextIds: 1
 ; DUMP:   CalleeEdges:
 ; DUMP:     Edge from Callee [[D]] to Caller: [[E]] AllocTypes: Cold ContextIds: 1
 ; DUMP:   CallerEdges:
 
 
+; DUMP: CCG after cloning:
+; DUMP: Callsite Context Graph:
+; DUMP: Node [[D]]
+; DUMP:         Versions: 1 MIB:
+; DUMP:                 AllocType 2 StackIds: 0
+; DUMP:                 AllocType 1 StackIds: 1
+; DUMP:         (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 2
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[D]] to Caller: [[F]] AllocTypes: NotCold ContextIds: 2
+; DUMP:         Clones: [[D2:0x[a-z0-9]+]]
+
+; DUMP: Node [[F]]
+; DUMP:         Callee: 4881081444663423788 (_Z1Dv) Clones: 0 StackIds: 1       (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 2
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[D]] to Caller: [[F]] AllocTypes: NotCold ContextIds: 2
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[C2]]
+; DUMP:         Callee: 4881081444663423788 (_Z1Dv) Clones: 0 StackIds: 0       (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 3
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[D2]] to Caller: [[C2]] AllocTypes: Cold ContextIds: 3
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[B]]
+; DUMP:         Callee: 4881081444663423788 (_Z1Dv) Clones: 0 StackIds: 0, 2    (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 4
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[D2]] to Caller: [[B]] AllocTypes: Cold ContextIds: 4
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[E]]
+; DUMP:         Callee: 4881081444663423788 (_Z1Dv) Clones: 0 StackIds: 0, 3    (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 1
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[D2]] to Caller: [[E]] AllocTypes: Cold ContextIds: 1
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[D2]]
+; DUMP:         Versions: 1 MIB:
+; DUMP:                 AllocType 2 StackIds: 0
+; DUMP:                 AllocType 1 StackIds: 1
+; DUMP:         (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 1 3 4
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[D2]] to Caller: [[E:0x[a-z0-9]+]] AllocTypes: Cold ContextIds: 1
+; DUMP:     Edge from Callee [[D2]] to Caller: [[C2:0x[a-z0-9]+]] AllocTypes: Cold ContextIds: 3
+; DUMP:     Edge from Callee [[D2]] to Caller: [[B:0x[a-z0-9]+]] AllocTypes: Cold ContextIds: 4
+; DUMP:         Clone of [[D]]
+
+
 ; DOTPRE: digraph "prestackupdate" {
 ; DOTPRE:   label="prestackupdate";
 ; DOTPRE:   Node[[D:0x[a-z0-9]+]] [shape=record,tooltip="N[[D]] ContextIds: 1 2",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: Alloc0\n_Z1Dv -\> alloc}"];
 ; DOTPRE:   Node[[C:0x[a-z0-9]+]] [shape=record,tooltip="N[[C]] ContextIds: 1",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 12176601099670543485\nnull call (external)}"];
 ; DOTPRE:   Node[[C]] -> Node[[D]][tooltip="ContextIds: 1",fillcolor="cyan"];
 ; DOTPRE:   Node[[F:0x[a-z0-9]+]] [shape=record,tooltip="N[[F]] ContextIds: 2",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 13543580133643026784\nnull call (external)}"];
 ; DOTPRE:   Node[[F]] -> Node[[D]][tooltip="ContextIds: 2",fillcolor="brown1"];
 ; DOTPRE: }
 
 
 ; DOTPOST:digraph "postbuild" {
 ; DOTPOST:  label="postbuild";
 ; DOTPOST:  Node[[D:0x[a-z0-9]+]] [shape=record,tooltip="N[[D]] ContextIds: 1 2 3 4",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: Alloc0\n_Z1Dv -\> alloc}"];
 ; DOTPOST:  Node[[F:0x[a-z0-9]+]] [shape=record,tooltip="N[[F]] ContextIds: 2",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 13543580133643026784\n_Z1Fv -\> _Z1Dv}"];
 ; DOTPOST:  Node[[F]] -> Node[[D]][tooltip="ContextIds: 2",fillcolor="brown1"];
 ; DOTPOST:  Node[[C:0x[a-z0-9]+]] [shape=record,tooltip="N[[C]] ContextIds: 3",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 0\n_Z1Cv -\> _Z1Dv}"];
 ; DOTPOST:  Node[[C]] -> Node[[D]][tooltip="ContextIds: 3",fillcolor="cyan"];
 ; DOTPOST:  Node[[B:0x[a-z0-9]+]] [shape=record,tooltip="N[[B]] ContextIds: 4",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 0\n_Z1Bv -\> _Z1Dv}"];
 ; DOTPOST:  Node[[B]] -> Node[[D]][tooltip="ContextIds: 4",fillcolor="cyan"];
 ; DOTPOST:  Node[[E:0x[a-z0-9]+]] [shape=record,tooltip="N[[E]] ContextIds: 1",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 0\n_Z1Ev -\> _Z1Dv}"];
 ; DOTPOST:  Node[[E]] -> Node[[D]][tooltip="ContextIds: 1",fillcolor="cyan"];
 ; DOTPOST:}
+
+
+; DOTCLONED: digraph "cloned" {
+; DOTCLONED:  label="cloned";
+; DOTCLONED:  Node[[D:0x[a-z0-9]+]] [shape=record,tooltip="N[[D]] ContextIds: 2",fillcolor="brown1",style="filled",style="filled",label="{OrigId: Alloc0\n_Z1Dv -\> alloc}"];
+; DOTCLONED:   Node[[F:0x[a-z0-9]+]] [shape=record,tooltip="N[[F]] ContextIds: 2",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 13543580133643026784\n_Z1Fv -\> _Z1Dv}"];
+; DOTCLONED:  Node[[F]] -> Node[[D]][tooltip="ContextIds: 2",fillcolor="brown1"];
+; DOTCLONED:  Node[[C:0x[a-z0-9]+]] [shape=record,tooltip="N[[C]] ContextIds: 3",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 0\n_Z1Cv -\> _Z1Dv}"];
+; DOTCLONED:  Node[[C]] -> Node[[D2:0x[a-z0-9]+]][tooltip="ContextIds: 3",fillcolor="cyan"];
+; DOTCLONED:  Node[[B:0x[a-z0-9]+]] [shape=record,tooltip="N[[B]] ContextIds: 4",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 0\n_Z1Bv -\> _Z1Dv}"];
+; DOTCLONED:  Node[[B]] -> Node[[D2]][tooltip="ContextIds: 4",fillcolor="cyan"];
+; DOTCLONED:  Node[[E:0x[a-z0-9]+]] [shape=record,tooltip="N[[E]] ContextIds: 1",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 0\n_Z1Ev -\> _Z1Dv}"];
+; DOTCLONED:  Node[[E]] -> Node[[D2]][tooltip="ContextIds: 1",fillcolor="cyan"];
+; DOTCLONED:   Node[[D2]] [shape=record,tooltip="N[[D2]] ContextIds: 1 3 4",fillcolor="cyan",style="filled",color="blue",style="filled,bold,dashed",label="{OrigId: Alloc0\n_Z1Dv -\> alloc}"];
+; DOTCLONED: }

llvm/test/ThinLTO/X86/memprof-indirectcall.ll

 ; RUN:  -r=%t.o,_ZdaPv, \
 ; RUN:  -r=%t.o,_ZTVN10__cxxabiv120__si_class_type_infoE, \
 ; RUN:  -r=%t.o,_ZTVN10__cxxabiv117__class_type_infoE, \
 ; RUN:  -memprof-verify-ccg -memprof-verify-nodes -memprof-dump-ccg \
 ; RUN:  -memprof-export-to-dot -memprof-dot-file-path-prefix=%t. \
 ; RUN:  -o %t.out 2>&1 | FileCheck %s --check-prefix=DUMP
 
 ; RUN:  cat %t.ccg.postbuild.dot | FileCheck %s --check-prefix=DOT
+;; We should only create a single clone of foo, for the direct call
+;; from main allocating cold memory.
+; RUN:  cat %t.ccg.cloned.dot | FileCheck %s --check-prefix=DOTCLONED
 
 
 source_filename = "indirectcall.ll"
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @_ZTVN10__cxxabiv120__si_class_type_infoE = external global ptr
 @_ZTVN10__cxxabiv117__class_type_infoE = external global ptr

 ; DUMP: Node [[MAIN2]]
 ; DUMP:   Callee: 12914368124089294956 (_Z3foov) Clones: 0 StackIds: 1  (clone 0)
 ; DUMP:   AllocTypes: Cold
 ; DUMP:   ContextIds: 6
 ; DUMP:   CalleeEdges:
 ; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 6
 ; DUMP:   CallerEdges:
 
+; DUMP: CCG after cloning:
+; DUMP: Callsite Context Graph:
+; DUMP: Node [[FOO]]
+; DUMP:         Versions: 1 MIB:
+; DUMP:                 AllocType 1 StackIds: 6, 8, 4
+; DUMP:                 AllocType 2 StackIds: 6, 8, 5
+; DUMP:                 AllocType 1 StackIds: 0
+; DUMP:                 AllocType 2 StackIds: 7, 8, 2
+; DUMP:                 AllocType 1 StackIds: 7, 8, 3
+; DUMP:                 AllocType 2 StackIds: 1
+; DUMP:         (clone 0)
+; DUMP:   AllocTypes: NotColdCold
+; DUMP:   ContextIds: 1 2 3 4 5
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[AX]] AllocTypes: NotColdCold ContextIds: 1 2
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[BX]] AllocTypes: NotColdCold ContextIds: 4 5
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN1]] AllocTypes: NotCold ContextIds: 3
+; DUMP:   Clones: [[FOO2:0x[a-z0-9]+]]
+
+; DUMP: Node [[AX]]
+; DUMP:   Callee: 12914368124089294956 (_Z3foov) Clones: 0 StackIds: 6    (clone 0)
+; DUMP:   AllocTypes: NotColdCold
+; DUMP:   ContextIds: 1 2
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[AX]] AllocTypes: NotColdCold ContextIds: 1 2
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[AX]] to Caller: [[BAR]] AllocTypes: NotColdCold ContextIds: 1 2
+
+; DUMP: Node [[BAR]]
+; DUMP:   null Call
+; DUMP:   AllocTypes: NotColdCold
+; DUMP:   ContextIds: 1 2 4 5
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[AX]] to Caller: [[BAR]] AllocTypes: NotColdCold ContextIds: 1 2
+; DUMP:     Edge from Callee [[BX]] to Caller: [[BAR]] AllocTypes: NotColdCold ContextIds: 4 5
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN3]] AllocTypes: NotCold ContextIds: 1
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN4]] AllocTypes: Cold ContextIds: 2
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN5]] AllocTypes: Cold ContextIds: 4
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN6]] AllocTypes: NotCold ContextIds: 5
+
+; DUMP: Node [[MAIN3]]
+; DUMP:   Callee: 4095956691517954349 (_Z3barP1A) Clones: 0 StackIds: 4   (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 1
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN3]] AllocTypes: NotCold ContextIds: 1
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[MAIN4]]
+; DUMP:   Callee: 4095956691517954349 (_Z3barP1A) Clones: 0 StackIds: 5   (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 2
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN4]] AllocTypes: Cold ContextIds: 2
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[MAIN1]]
+; DUMP:   Callee: 12914368124089294956 (_Z3foov) Clones: 0 StackIds: 0    (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 3
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN1]] AllocTypes: NotCold ContextIds: 3
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[BX]]
+; DUMP:   Callee: 12914368124089294956 (_Z3foov) Clones: 0 StackIds: 7    (clone 0)
+; DUMP:   AllocTypes: NotColdCold
+; DUMP:   ContextIds: 4 5
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[BX]] AllocTypes: NotColdCold ContextIds: 4 5
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[BX]] to Caller: [[BAR]] AllocTypes: NotColdCold ContextIds: 4 5
+
+; DUMP: Node [[MAIN5]]
+; DUMP:   Callee: 4095956691517954349 (_Z3barP1A) Clones: 0 StackIds: 2   (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 4
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN5]] AllocTypes: Cold ContextIds: 4
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[MAIN6]]
+; DUMP:   Callee: 4095956691517954349 (_Z3barP1A) Clones: 0 StackIds: 3   (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 5
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN6]] AllocTypes: NotCold ContextIds: 5
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[MAIN2]]
+; DUMP:   Callee: 12914368124089294956 (_Z3foov) Clones: 0 StackIds: 1    (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 6
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[FOO2]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 6
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[FOO2]]
+; DUMP:         Versions: 1 MIB:
+; DUMP:                 AllocType 1 StackIds: 6, 8, 4
+; DUMP:                 AllocType 2 StackIds: 6, 8, 5
+; DUMP:                 AllocType 1 StackIds: 0
+; DUMP:                 AllocType 2 StackIds: 7, 8, 2
+; DUMP:                 AllocType 1 StackIds: 7, 8, 3
+; DUMP:                 AllocType 2 StackIds: 1
+; DUMP:         (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 6
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[FOO2]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 6
+; DUMP:   Clone of [[FOO]]
+
 
 ; DOT: digraph "postbuild" {
 ; DOT:  label="postbuild";
 ; DOT:   Node[[FOO:0x[a-z0-9]+]] [shape=record,tooltip="N[[FOO]] ContextIds: 1 2 3 4 5 6",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: Alloc0\n_Z3foov -\> alloc}"];
 ; DOT:   Node[[AX:0x[a-z0-9]+]] [shape=record,tooltip="N[[AX]] ContextIds: 1 2",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 8256774051149711748\n_ZN1A1xEv -\> _Z3foov}"];
 ; DOT:  Node[[AX]] -> Node[[FOO]][tooltip="ContextIds: 1 2",fillcolor="mediumorchid1"];
 ; DOT:   Node[[BAR:0x[a-z0-9]+]] [shape=record,tooltip="N[[BAR]] ContextIds: 1 2 4 5",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 13626499562959447861\nnull call (external)}"];
 ; DOT:  Node[[BAR]] -> Node[[AX]][tooltip="ContextIds: 1 2",fillcolor="mediumorchid1"];
 ; DOT:  Node[[BAR]] -> Node[[BX:0x[a-z0-9]+]][tooltip="ContextIds: 4 5",fillcolor="mediumorchid1"];
 ; DOT:   Node[[MAIN1:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN1]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 748269490701775343\nmain -\> _Z3barP1A}"];
 ; DOT:  Node[[MAIN1]] -> Node[[BAR]][tooltip="ContextIds: 1",fillcolor="brown1"];
 ; DOT:   Node[[MAIN2:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN2]] ContextIds: 2",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 12699492813229484831\nmain -\> _Z3barP1A}"];
 ; DOT:  Node[[MAIN2]] -> Node[[BAR]][tooltip="ContextIds: 2",fillcolor="cyan"];
 ; DOT:   Node[[MAIN3:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN3]] ContextIds: 3",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 8632435727821051414\nmain -\> _Z3foov}"];
 ; DOT:  Node[[MAIN3]] -> Node[[FOO]][tooltip="ContextIds: 3",fillcolor="brown1"];
 ; DOT:   Node[[BX]] [shape=record,tooltip="N[[BX]] ContextIds: 4 5",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 13614864978754796978\n_ZN1B1xEv -\> _Z3foov}"];
 ; DOT:  Node[[BX]] -> Node[[FOO]][tooltip="ContextIds: 4 5",fillcolor="mediumorchid1"];
 ; DOT:   Node[[MAIN4:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN4]] ContextIds: 4",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 6792096022461663180\nmain -\> _Z3barP1A}"];
 ; DOT:  Node[[MAIN4]] -> Node[[BAR]][tooltip="ContextIds: 4",fillcolor="cyan"];
 ; DOT:   Node[[MAIN5:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN5]] ContextIds: 5",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 15737101490731057601\nmain -\> _Z3barP1A}"];
 ; DOT:  Node[[MAIN5]] -> Node[[BAR]][tooltip="ContextIds: 5",fillcolor="brown1"];
 ; DOT:   Node[[MAIN6:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN6]] ContextIds: 6",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 15025054523792398438\nmain -\> _Z3foov}"];
 ; DOT:  Node[[MAIN6]] -> Node[[FOO]][tooltip="ContextIds: 6",fillcolor="cyan"];
 ; DOT: }
+
+
+; DOTCLONED: digraph "cloned" {
+; DOTCLONED:  label="cloned";
+; DOTCLONED:   Node[[FOO2:0x[a-z0-9]+]] [shape=record,tooltip="N[[FOO2]] ContextIds: 1 2 3 4 5",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: Alloc0\n_Z3foov -\> alloc}"];
+; DOTCLONED:   Node[[AX:0x[a-z0-9]+]] [shape=record,tooltip="N[[AX]] ContextIds: 1 2",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 8256774051149711748\n_ZN1A1xEv -\> _Z3foov}"];
+; DOTCLONED:  Node[[AX]] -> Node[[FOO2]][tooltip="ContextIds: 1 2",fillcolor="mediumorchid1"];
+; DOTCLONED:   Node[[BAR:0x[a-z0-9]+]] [shape=record,tooltip="N[[BAR]] ContextIds: 1 2 4 5",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 13626499562959447861\nnull call (external)}"];
+; DOTCLONED:  Node[[BAR]] -> Node[[AX]][tooltip="ContextIds: 1 2",fillcolor="mediumorchid1"];
+; DOTCLONED:  Node[[BAR]] -> Node[[BX:0x[a-z0-9]+]][tooltip="ContextIds: 4 5",fillcolor="mediumorchid1"];
+; DOTCLONED:   Node[[MAIN1:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN1]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 748269490701775343\nmain -\> _Z3barP1A}"];
+; DOTCLONED:  Node[[MAIN1]] -> Node[[BAR]][tooltip="ContextIds: 1",fillcolor="brown1"];
+; DOTCLONED:   Node[[MAIN2:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN2]] ContextIds: 2",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 12699492813229484831\nmain -\> _Z3barP1A}"];
+; DOTCLONED:  Node[[MAIN2]] -> Node[[BAR]][tooltip="ContextIds: 2",fillcolor="cyan"];
+; DOTCLONED:   Node[[MAIN3:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN3]] ContextIds: 3",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 8632435727821051414\nmain -\> _Z3foov}"];
+; DOTCLONED:  Node[[MAIN3]] -> Node[[FOO2]][tooltip="ContextIds: 3",fillcolor="brown1"];
+; DOTCLONED:   Node[[BX]] [shape=record,tooltip="N[[BX]] ContextIds: 4 5",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 13614864978754796978\n_ZN1B1xEv -\> _Z3foov}"];
+; DOTCLONED:  Node[[BX]] -> Node[[FOO2]][tooltip="ContextIds: 4 5",fillcolor="mediumorchid1"];
+; DOTCLONED:   Node[[MAIN4:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN4]] ContextIds: 4",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 6792096022461663180\nmain -\> _Z3barP1A}"];
+; DOTCLONED:  Node[[MAIN4]] -> Node[[BAR]][tooltip="ContextIds: 4",fillcolor="cyan"];
+; DOTCLONED:   Node[[MAIN5:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN5]] ContextIds: 5",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 15737101490731057601\nmain -\> _Z3barP1A}"];
+; DOTCLONED:  Node[[MAIN5]] -> Node[[BAR]][tooltip="ContextIds: 5",fillcolor="brown1"];
+; DOTCLONED:   Node[[MAIN6:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN6]] ContextIds: 6",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 15025054523792398438\nmain -\> _Z3foov}"];
+; DOTCLONED:  Node[[MAIN6]] -> Node[[FOO2:0x[a-z0-9]+]][tooltip="ContextIds: 6",fillcolor="cyan"];
+; DOTCLONED:   Node[[FOO2]] [shape=record,tooltip="N[[FOO2]] ContextIds: 6",fillcolor="cyan",style="filled",color="blue",style="filled,bold,dashed",label="{OrigId: Alloc0\n_Z3foov -\> alloc}"];
+; DOTCLONED: }

llvm/test/ThinLTO/X86/memprof-inlined.ll

 ; RUN:  -r=%t.o,_ZdaPv, \
 ; RUN:  -r=%t.o,sleep, \
 ; RUN:  -r=%t.o,_Znam, \
 ; RUN:  -memprof-verify-ccg -memprof-verify-nodes -memprof-dump-ccg \
 ; RUN:  -memprof-export-to-dot -memprof-dot-file-path-prefix=%t. \
 ; RUN:  -o %t.out 2>&1 | FileCheck %s --check-prefix=DUMP
 
 ; RUN:  cat %t.ccg.postbuild.dot | FileCheck %s --check-prefix=DOT
+;; We should create clones for foo and bar for the call from main to allocate
+;; cold memory.
+; RUN:  cat %t.ccg.cloned.dot | FileCheck %s --check-prefix=DOTCLONED
 
 
 source_filename = "inlined.ll"
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define internal ptr @_Z3barv() {
 entry:

 ; DUMP:   AllocTypes: NotColdCold
 ; DUMP:   ContextIds: 3 4
 ; DUMP:   CalleeEdges:
 ; DUMP:     Edge from Callee [[BAR]] to Caller: [[FOO]] AllocTypes: NotColdCold ContextIds: 3 4
 ; DUMP:   CallerEdges:
 ; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN1]] AllocTypes: NotCold ContextIds: 3
 ; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 4
 
+; DUMP: CCG after cloning:
+; DUMP: Callsite Context Graph:
+; DUMP: Node [[BAZ]]
+; DUMP:         Versions: 1 MIB:
+; DUMP:                 AllocType 1 StackIds: 1, 2
+; DUMP:                 AllocType 2 StackIds: 1, 3
+; DUMP:         (clone 0)
+; DUMP:   AllocTypes: NotColdCold
+; DUMP:   ContextIds: 1 2
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[BAZ]] to Caller: [[FOO2]] AllocTypes: NotColdCold ContextIds: 1 2
+
+; DUMP: Node [[FOO2]]
+; DUMP:   null Call
+; DUMP:   AllocTypes: NotColdCold
+; DUMP:   ContextIds: 1 2
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAZ]] to Caller: [[FOO2]] AllocTypes: NotColdCold ContextIds: 1 2
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[FOO2]] to Caller: [[MAIN1]] AllocTypes: NotCold ContextIds: 1
+; DUMP:     Edge from Callee [[FOO2]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 2
+
+; DUMP: Node [[MAIN1]]
+; DUMP:         Callee: 2229562716906371625 (_Z3foov) Clones: 0 StackIds: 2     (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 1 3
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[FOO2]] to Caller: [[MAIN1]] AllocTypes: NotCold ContextIds: 1
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN1]] AllocTypes: NotCold ContextIds: 3
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[MAIN2]]
+; DUMP:         Callee: 2229562716906371625 (_Z3foov) Clones: 0 StackIds: 3     (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 2 4
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[FOO2]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 2
+; DUMP:     Edge from Callee [[FOO3:0x[a-z0-9]+]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 4
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[BAR]]
+; DUMP:         Versions: 1 MIB:
+; DUMP:                 AllocType 1 StackIds: 0, 1, 2
+; DUMP:                 AllocType 2 StackIds: 0, 1, 3
+; DUMP:         (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 3
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[FOO]] AllocTypes: NotCold ContextIds: 3
+; DUMP:         Clones: [[BAR2:0x[a-z0-9]+]]
+
+; DUMP: Node [[FOO]]
+; DUMP:         Callee: 16064618363798697104 (_Z3barv) Clones: 0 StackIds: 0, 1 (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 3
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[FOO]] AllocTypes: NotCold ContextIds: 3
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN1]] AllocTypes: NotCold ContextIds: 3
+; DUMP:         Clones: [[FOO3]]
+
+; DUMP: Node [[FOO3]]
+; DUMP:         Callee: 16064618363798697104 (_Z3barv) Clones: 0 StackIds: 0, 1 (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 4
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAR2]] to Caller: [[FOO3]] AllocTypes: Cold ContextIds: 4
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[FOO3]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 4
+; DUMP:         Clone of [[FOO]]
+
+; DUMP: Node [[BAR2]]
+; DUMP:         Versions: 1 MIB:
+; DUMP:                 AllocType 1 StackIds: 0, 1, 2
+; DUMP:                 AllocType 2 StackIds: 0, 1, 3
+; DUMP:         (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 4
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[BAR2]] to Caller: [[FOO3]] AllocTypes: Cold ContextIds: 4
+; DUMP:         Clone of [[BAR]]
+
 
 ; DOT: digraph "postbuild" {
 ; DOT:  label="postbuild";
 ; DOT:   Node[[BAZ:0x[a-z0-9]+]] [shape=record,tooltip="N[[BAZ]] ContextIds: 1 2",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: Alloc0\n_Z3bazv -\> alloc}"];
 ; DOT:   Node[[FOO:0x[a-z0-9]+]] [shape=record,tooltip="N[[FOO]] ContextIds: 1 2",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 2732490490862098848\nnull call (external)}"];
 ; DOT:  Node[[FOO]] -> Node[[BAZ]][tooltip="ContextIds: 1 2",fillcolor="mediumorchid1"];
 ; DOT:   Node[[MAIN1:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN1]] ContextIds: 1 3",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 8632435727821051414\nmain -\> _Z3foov}"];
 ; DOT:  Node[[MAIN1]] -> Node[[FOO]][tooltip="ContextIds: 1",fillcolor="brown1"];
 ; DOT:  Node[[MAIN1]] -> Node[[FOO2:0x[a-z0-9]+]][tooltip="ContextIds: 3",fillcolor="brown1"];
 ; DOT:   Node[[MAIN2:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN2]] ContextIds: 2 4",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 15025054523792398438\nmain -\> _Z3foov}"];
 ; DOT:  Node[[MAIN2]] -> Node[[FOO]][tooltip="ContextIds: 2",fillcolor="cyan"];
 ; DOT:  Node[[MAIN2]] -> Node[[FOO2]][tooltip="ContextIds: 4",fillcolor="cyan"];
 ; DOT:   Node[[BAR:0x[a-z0-9]+]] [shape=record,tooltip="N[[BAR]] ContextIds: 3 4",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: Alloc2\n_Z3barv -\> alloc}"];
 ; DOT:  Node[[FOO2]] [shape=record,tooltip="N[[FOO2]] ContextIds: 3 4",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 0\n_Z3foov -\> _Z3barv}"];
 ; DOT:  Node[[FOO2]] -> Node[[BAR]][tooltip="ContextIds: 3 4",fillcolor="mediumorchid1"];
 ; DOT: }
+
+
+; DOTCLONED: digraph "cloned" {
+; DOTCLONED:  label="cloned";
+; DOTCLONED:   Node[[BAZ:0x[a-z0-9]+]] [shape=record,tooltip="N[[BAZ]] ContextIds: 1 2",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: Alloc0\n_Z3bazv -\> alloc}"];
+; DOTCLONED:   Node[[FOO2:0x[a-z0-9]+]] [shape=record,tooltip="N[[FOO2]] ContextIds: 1 2",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 2732490490862098848\nnull call (external)}"];
+; DOTCLONED:  Node[[FOO2]] -> Node[[BAZ]][tooltip="ContextIds: 1 2",fillcolor="mediumorchid1"];
+; DOTCLONED:   Node[[MAIN1:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN1]] ContextIds: 1 3",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 8632435727821051414\nmain -\> _Z3foov}"];
+; DOTCLONED:  Node[[MAIN1]] -> Node[[FOO2]][tooltip="ContextIds: 1",fillcolor="brown1"];
+; DOTCLONED:  Node[[MAIN1]] -> Node[[FOO:0x[a-z0-9]+]][tooltip="ContextIds: 3",fillcolor="brown1"];
+; DOTCLONED:   Node[[MAIN2:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN2]] ContextIds: 2 4",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 15025054523792398438\nmain -\> _Z3foov}"];
+; DOTCLONED:  Node[[MAIN2]] -> Node[[FOO2]][tooltip="ContextIds: 2",fillcolor="cyan"];
+; DOTCLONED:  Node[[MAIN2]] -> Node[[FOO3:0x[a-z0-9]+]][tooltip="ContextIds: 4",fillcolor="cyan"];
+; DOTCLONED:  Node[[BAR:0x[a-z0-9]+]] [shape=record,tooltip="N[[BAR]] ContextIds: 3",fillcolor="brown1",style="filled",style="filled",label="{OrigId: Alloc2\n_Z3barv -\> alloc}"];
+; DOTCLONED:  Node[[FOO]] [shape=record,tooltip="N[[FOO]] ContextIds: 3",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 0\n_Z3foov -\> _Z3barv}"];
+; DOTCLONED:  Node[[FOO]] -> Node[[BAR]][tooltip="ContextIds: 3",fillcolor="brown1"];
+; DOTCLONED:   Node[[FOO3]] [shape=record,tooltip="N[[FOO3]] ContextIds: 4",fillcolor="cyan",style="filled",color="blue",style="filled,bold,dashed",label="{OrigId: 0\n_Z3foov -\> _Z3barv}"];
+; DOTCLONED:  Node[[FOO3]] -> Node[[BAR2:0x[a-z0-9]+]][tooltip="ContextIds: 4",fillcolor="cyan"];
+; DOTCLONED:   Node[[BAR2]] [shape=record,tooltip="N[[BAR2]] ContextIds: 4",fillcolor="cyan",style="filled",color="blue",style="filled,bold,dashed",label="{OrigId: Alloc0\n_Z3barv -\> alloc}"];
+; DOTCLONED: }

llvm/test/Transforms/MemProfContextDisambiguation/basic.ll

 ;; The IR was then reduced using llvm-reduce with the expected FileCheck input.
 
 ; RUN: opt -passes=memprof-context-disambiguation \
 ; RUN:  -memprof-verify-ccg -memprof-verify-nodes -memprof-dump-ccg \
 ; RUN:  -memprof-export-to-dot -memprof-dot-file-path-prefix=%t. \
 ; RUN:  %s -S 2>&1 | FileCheck %s --check-prefix=DUMP
 
 ; RUN:  cat %t.ccg.postbuild.dot | FileCheck %s --check-prefix=DOT
+;; We should have cloned bar, baz, and foo, for the cold memory allocation.
+; RUN:  cat %t.ccg.cloned.dot | FileCheck %s --check-prefix=DOTCLONED
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define i32 @main() #0 {
 entry:
   %call = call noundef ptr @_Z3foov(), !callsite !0
   %call1 = call noundef ptr @_Z3foov(), !callsite !1

 ; DUMP: Node [[MAIN2]]
 ; DUMP:     %call1 = call noundef ptr @_Z3foov()  (clone 0)
 ; DUMP:   AllocTypes: Cold
 ; DUMP:   ContextIds: 2
 ; DUMP:   CalleeEdges:
 ; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 2
 ; DUMP:   CallerEdges:
 
+; DUMP: CCG after cloning:
+; DUMP: Callsite Context Graph:
+; DUMP: Node [[BAR:0x[a-z0-9]+]]
+; DUMP:     %call = call noalias noundef nonnull ptr @_Znam(i64 noundef 10) #6  (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 1
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[BAZ:0x[a-z0-9]+]] AllocTypes: NotCold ContextIds: 1
+; DUMP:   Clones: [[BAR2:0x[a-z0-9]+]]
+
+; DUMP: Node [[BAZ]]
+; DUMP:     %call = call noundef ptr @_Z3barv() (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 1
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[BAZ]] AllocTypes: NotCold ContextIds: 1
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[BAZ]] to Caller: [[FOO:0x[a-z0-9]+]] AllocTypes: NotCold ContextIds: 1
+; DUMP:   Clones: [[BAZ2:0x[a-z0-9]+]]
+
+; DUMP: Node [[FOO]]
+; DUMP:     %call = call noundef ptr @_Z3bazv() (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 1
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAZ]] to Caller: [[FOO]] AllocTypes: NotCold ContextIds: 1
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN1:0x[a-z0-9]+]] AllocTypes: NotCold ContextIds: 1
+; DUMP:   Clones: [[FOO2:0x[a-z0-9]+]]
+
+; DUMP: Node [[MAIN1]]
+; DUMP:     %call = call noundef ptr @_Z3foov() (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 1
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN1]] AllocTypes: NotCold ContextIds: 1
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[MAIN2]]
+; DUMP:     %call1 = call noundef ptr @_Z3foov()  (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 2
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[FOO2]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 2
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[FOO2]]
+; DUMP:     %call = call noundef ptr @_Z3bazv() (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 2
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAZ2]] to Caller: [[FOO2]] AllocTypes: Cold ContextIds: 2
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[FOO2]] to Caller: [[MAIN2:0x[a-z0-9]+]] AllocTypes: Cold ContextIds: 2
+; DUMP:   Clone of [[FOO]]
+
+; DUMP: Node [[BAZ2]]
+; DUMP:     %call = call noundef ptr @_Z3barv() (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 2
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAR2]] to Caller: [[BAZ2]] AllocTypes: Cold ContextIds: 2
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[BAZ2]] to Caller: [[FOO2]] AllocTypes: Cold ContextIds: 2
+; DUMP:   Clone of [[BAZ]]
+
+; DUMP: Node [[BAR2]]
+; DUMP:     %call = call noalias noundef nonnull ptr @_Znam(i64 noundef 10) #6  (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 2
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[BAR2]] to Caller: [[BAZ2]] AllocTypes: Cold ContextIds: 2
+; DUMP:   Clone of [[BAR]]
+
 
 ; DOT: digraph "postbuild" {
 ; DOT:  label="postbuild";
 ; DOT:   Node[[BAR:0x[a-z0-9]+]] [shape=record,tooltip="N[[BAR]] ContextIds: 1 2",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: Alloc0\n_Z3barv -\> _Znam}"];
 ; DOT:   Node[[BAZ:0x[a-z0-9]+]] [shape=record,tooltip="N[[BAZ]] ContextIds: 1 2",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 12481870273128938184\n_Z3bazv -\> _Z3barv}"];
 ; DOT:  Node[[BAZ]] -> Node[[BAR]][tooltip="ContextIds: 1 2",fillcolor="mediumorchid1"];
 ; DOT:   Node[[FOO:0x[a-z0-9]+]] [shape=record,tooltip="N[[FOO]] ContextIds: 1 2",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 2732490490862098848\n_Z3foov -\> _Z3bazv}"];
 ; DOT:  Node[[FOO]] -> Node[[BAZ]][tooltip="ContextIds: 1 2",fillcolor="mediumorchid1"];
 ; DOT:   Node[[MAIN1:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN1]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 8632435727821051414\nmain -\> _Z3foov}"];
 ; DOT:  Node[[MAIN1]] -> Node[[FOO]][tooltip="ContextIds: 1",fillcolor="brown1"];
 ; DOT:   Node[[MAIN2:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN2]] ContextIds: 2",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 15025054523792398438\nmain -\> _Z3foov}"];
 ; DOT:  Node[[MAIN2]] -> Node[[FOO]][tooltip="ContextIds: 2",fillcolor="cyan"];
 ; DOT: }
+
+
+; DOTCLONED: digraph "cloned" {
+; DOTCLONED:  label="cloned";
+; DOTCLONED:  Node[[BAR:0x[a-z0-9]+]] [shape=record,tooltip="N[[BAR]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled",label="{OrigId: Alloc0\n_Z3barv -\> _Znam}"];
+; DOTCLONED:   Node[[BAZ:0x[a-z0-9]+]] [shape=record,tooltip="N[[BAZ]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 12481870273128938184\n_Z3bazv -\> _Z3barv}"];
+; DOTCLONED:  Node[[BAZ]] -> Node[[BAR]][tooltip="ContextIds: 1",fillcolor="brown1"];
+; DOTCLONED:   Node[[FOO:0x[a-z0-9]+]] [shape=record,tooltip="N[[FOO]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 2732490490862098848\n_Z3foov -\> _Z3bazv}"];
+; DOTCLONED:  Node[[FOO]] -> Node[[BAZ]][tooltip="ContextIds: 1",fillcolor="brown1"];
+; DOTCLONED:   Node[[MAIN1:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN1]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 8632435727821051414\nmain -\> _Z3foov}"];
+; DOTCLONED:  Node[[MAIN1]] -> Node[[FOO]][tooltip="ContextIds: 1",fillcolor="brown1"];
+; DOTCLONED:   Node[[MAIN2:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN2]] ContextIds: 2",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 15025054523792398438\nmain -\> _Z3foov}"];
+; DOTCLONED:  Node[[MAIN2]] -> Node[[FOO2:0x[a-z0-9]+]][tooltip="ContextIds: 2",fillcolor="cyan"];
+; DOTCLONED:   Node[[FOO2]] [shape=record,tooltip="N[[FOO2]] ContextIds: 2",fillcolor="cyan",style="filled",color="blue",style="filled,bold,dashed",label="{OrigId: 0\n_Z3foov -\> _Z3bazv}"];
+; DOTCLONED:  Node[[FOO2]] -> Node[[BAZ2:0x[a-z0-9]+]][tooltip="ContextIds: 2",fillcolor="cyan"];
+; DOTCLONED:   Node[[BAZ2]] [shape=record,tooltip="N[[BAZ2]] ContextIds: 2",fillcolor="cyan",style="filled",color="blue",style="filled,bold,dashed",label="{OrigId: 0\n_Z3bazv -\> _Z3barv}"];
+; DOTCLONED:  Node[[BAZ2]] -> Node[[BAR2:0x[a-z0-9]+]][tooltip="ContextIds: 2",fillcolor="cyan"];
+; DOTCLONED:   Node[[BAR2]] [shape=record,tooltip="N[[BAR2]] ContextIds: 2",fillcolor="cyan",style="filled",color="blue",style="filled,bold,dashed",label="{OrigId: Alloc0\n_Z3barv -\> _Znam}"];
+; DOTCLONED: }

llvm/test/Transforms/MemProfContextDisambiguation/duplicate-context-ids.ll

 
 ; RUN: opt -passes=memprof-context-disambiguation \
 ; RUN:  -memprof-verify-ccg -memprof-verify-nodes -memprof-dump-ccg \
 ; RUN:  -memprof-export-to-dot -memprof-dot-file-path-prefix=%t. \
 ; RUN:  %s -S 2>&1 | FileCheck %s --check-prefix=DUMP
 
 ; RUN:  cat %t.ccg.prestackupdate.dot | FileCheck %s --check-prefix=DOTPRE
 ; RUN:  cat %t.ccg.postbuild.dot | FileCheck %s --check-prefix=DOTPOST
+;; We should clone D once for the cold allocations via C.
+; RUN:  cat %t.ccg.cloned.dot | FileCheck %s --check-prefix=DOTCLONED
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define internal ptr @_Z1Dv() {
 entry:
   %call = call noalias noundef nonnull ptr @_Znam(i64 noundef 10) #6, !memprof !0, !callsite !5
   ret ptr null

 ; DUMP: Node [[E]]
 ; DUMP:     %call.i = call noundef ptr @_Z1Dv() (clone 0)
 ; DUMP:   AllocTypes: Cold
 ; DUMP:   ContextIds: 1
 ; DUMP:   CalleeEdges:
 ; DUMP:     Edge from Callee [[D]] to Caller: [[E]] AllocTypes: Cold ContextIds: 1
 ; DUMP:   CallerEdges:
 
+; DUMP: CCG after cloning:
+; DUMP: Callsite Context Graph:
+; DUMP: Node [[D]]
+; DUMP:     %call = call noalias noundef nonnull ptr @_Znam(i64 noundef 10) #6  (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 2
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[D]] to Caller: [[F]] AllocTypes: NotCold ContextIds: 2
+; DUMP:         Clones: [[D2:0x[a-z0-9]+]]
+
+; DUMP: Node [[F]]
+; DUMP:     %call = call noundef ptr @_Z1Dv() (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 2
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[D]] to Caller: [[F]] AllocTypes: NotCold ContextIds: 2
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[C2]]
+; DUMP:     %call = call noundef ptr @_Z1Dv() (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 3
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[D2]] to Caller: [[C2]] AllocTypes: Cold ContextIds: 3
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[B]]
+; DUMP:     %call.i = call noundef ptr @_Z1Dv() (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 4
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[D2]] to Caller: [[B]] AllocTypes: Cold ContextIds: 4
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[E]]
+; DUMP:     %call.i = call noundef ptr @_Z1Dv() (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 1
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[D2]] to Caller: [[E]] AllocTypes: Cold ContextIds: 1
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[D2]]
+; DUMP:     %call = call noalias noundef nonnull ptr @_Znam(i64 noundef 10) #6  (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 1 3 4
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[D2]] to Caller: [[E:0x[a-z0-9]+]] AllocTypes: Cold ContextIds: 1
+; DUMP:     Edge from Callee [[D2]] to Caller: [[C2:0x[a-z0-9]+]] AllocTypes: Cold ContextIds: 3
+; DUMP:     Edge from Callee [[D2]] to Caller: [[B:0x[a-z0-9]+]] AllocTypes: Cold ContextIds: 4
+; DUMP:         Clone of [[D]]
+
 
 ; DOTPRE: digraph "prestackupdate" {
 ; DOTPRE:   label="prestackupdate";
 ; DOTPRE:   Node[[D:0x[a-z0-9]+]] [shape=record,tooltip="N[[D]] ContextIds: 1 2",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: Alloc0\n_Z1Dv -\> _Znam}"];
 ; DOTPRE:   Node[[C:0x[a-z0-9]+]] [shape=record,tooltip="N[[C]] ContextIds: 1",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 12176601099670543485\nnull call (external)}"];
 ; DOTPRE:   Node[[C]] -> Node[[D]][tooltip="ContextIds: 1",fillcolor="cyan"];
 ; DOTPRE:   Node[[F:0x[a-z0-9]+]] [shape=record,tooltip="N[[F]] ContextIds: 2",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 13543580133643026784\nnull call (external)}"];
 ; DOTPRE:   Node[[F]] -> Node[[D]][tooltip="ContextIds: 2",fillcolor="brown1"];
 ; DOTPRE: }
 
 
 ; DOTPOST:digraph "postbuild" {
 ; DOTPOST:  label="postbuild";
 ; DOTPOST:  Node[[D:0x[a-z0-9]+]] [shape=record,tooltip="N[[D]] ContextIds: 1 2 3 4",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: Alloc0\n_Z1Dv -\> _Znam}"];
 ; DOTPOST:  Node[[F:0x[a-z0-9]+]] [shape=record,tooltip="N[[F]] ContextIds: 2",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 13543580133643026784\n_Z1Fv -\> _Z1Dv}"];
 ; DOTPOST:  Node[[F]] -> Node[[D]][tooltip="ContextIds: 2",fillcolor="brown1"];
 ; DOTPOST:  Node[[C:0x[a-z0-9]+]] [shape=record,tooltip="N[[C]] ContextIds: 3",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 0\n_Z1Cv -\> _Z1Dv}"];
 ; DOTPOST:  Node[[C]] -> Node[[D]][tooltip="ContextIds: 3",fillcolor="cyan"];
 ; DOTPOST:  Node[[B:0x[a-z0-9]+]] [shape=record,tooltip="N[[B]] ContextIds: 4",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 0\n_Z1Bv -\> _Z1Dv}"];
 ; DOTPOST:  Node[[B]] -> Node[[D]][tooltip="ContextIds: 4",fillcolor="cyan"];
 ; DOTPOST:  Node[[E:0x[a-z0-9]+]] [shape=record,tooltip="N[[E]] ContextIds: 1",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 0\n_Z1Ev -\> _Z1Dv}"];
 ; DOTPOST:  Node[[E]] -> Node[[D]][tooltip="ContextIds: 1",fillcolor="cyan"];
 ; DOTPOST:}
+
+
+; DOTCLONED: digraph "cloned" {
+; DOTCLONED:  label="cloned";
+; DOTCLONED:  Node[[D:0x[a-z0-9]+]] [shape=record,tooltip="N[[D]] ContextIds: 2",fillcolor="brown1",style="filled",style="filled",label="{OrigId: Alloc0\n_Z1Dv -\> _Znam}"];
+; DOTCLONED:   Node[[F:0x[a-z0-9]+]] [shape=record,tooltip="N[[F]] ContextIds: 2",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 13543580133643026784\n_Z1Fv -\> _Z1Dv}"];
+; DOTCLONED:  Node[[F]] -> Node[[D]][tooltip="ContextIds: 2",fillcolor="brown1"];
+; DOTCLONED:  Node[[C:0x[a-z0-9]+]] [shape=record,tooltip="N[[C]] ContextIds: 3",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 0\n_Z1Cv -\> _Z1Dv}"];
+; DOTCLONED:  Node[[C]] -> Node[[D2:0x[a-z0-9]+]][tooltip="ContextIds: 3",fillcolor="cyan"];
+; DOTCLONED:  Node[[B:0x[a-z0-9]+]] [shape=record,tooltip="N[[B]] ContextIds: 4",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 0\n_Z1Bv -\> _Z1Dv}"];
+; DOTCLONED:  Node[[B]] -> Node[[D2]][tooltip="ContextIds: 4",fillcolor="cyan"];
+; DOTCLONED:  Node[[E:0x[a-z0-9]+]] [shape=record,tooltip="N[[E]] ContextIds: 1",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 0\n_Z1Ev -\> _Z1Dv}"];
+; DOTCLONED:  Node[[E]] -> Node[[D2]][tooltip="ContextIds: 1",fillcolor="cyan"];
+; DOTCLONED:   Node[[D2]] [shape=record,tooltip="N[[D2]] ContextIds: 1 3 4",fillcolor="cyan",style="filled",color="blue",style="filled,bold,dashed",label="{OrigId: Alloc0\n_Z1Dv -\> _Znam}"];
+; DOTCLONED: }

llvm/test/Transforms/MemProfContextDisambiguation/indirectcall.ll

 ;; The IR was then reduced using llvm-reduce with the expected FileCheck input.
 
 ; RUN: opt -passes=memprof-context-disambiguation \
 ; RUN:  -memprof-verify-ccg -memprof-verify-nodes -memprof-dump-ccg \
 ; RUN:  -memprof-export-to-dot -memprof-dot-file-path-prefix=%t. \
 ; RUN:  %s -S 2>&1 | FileCheck %s --check-prefix=DUMP
 
 ; RUN:  cat %t.ccg.postbuild.dot | FileCheck %s --check-prefix=DOT
+;; We should only create a single clone of foo, for the direct call
+;; from main allocating cold memory.
+; RUN:  cat %t.ccg.cloned.dot | FileCheck %s --check-prefix=DOTCLONED
 
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 declare ptr @_Z3barP1A(ptr)
 
 define i32 @main(ptr %b, ptr %a) #0 {

 ; DUMP: Node [[MAIN2]]
 ; DUMP:     %call1 = call noundef ptr @_Z3foov()  (clone 0)
 ; DUMP:   AllocTypes: Cold
 ; DUMP:   ContextIds: 6
 ; DUMP:   CalleeEdges:
 ; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 6
 ; DUMP:   CallerEdges:
 
+; DUMP: CCG after cloning:
+; DUMP: Callsite Context Graph:
+; DUMP: Node [[FOO]]
+; DUMP:     %call = call noalias noundef nonnull ptr @_Znam(i64 noundef 10) #7  (clone 0)
+; DUMP:   AllocTypes: NotColdCold
+; DUMP:   ContextIds: 1 2 3 4 5
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[AX]] AllocTypes: NotColdCold ContextIds: 1 2
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[BX]] AllocTypes: NotColdCold ContextIds: 4 5
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN1]] AllocTypes: NotCold ContextIds: 3
+; DUMP:   Clones: [[FOO2:0x[a-z0-9]+]]
+
+; DUMP: Node [[AX]]
+; DUMP:     %call = call noundef ptr @_Z3foov() (clone 0)
+; DUMP:   AllocTypes: NotColdCold
+; DUMP:   ContextIds: 1 2
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[AX]] AllocTypes: NotColdCold ContextIds: 1 2
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[AX]] to Caller: [[BAR]] AllocTypes: NotColdCold ContextIds: 1 2
+
+; DUMP: Node [[BAR]]
+; DUMP:   null Call
+; DUMP:   AllocTypes: NotColdCold
+; DUMP:   ContextIds: 1 2 4 5
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[AX]] to Caller: [[BAR]] AllocTypes: NotColdCold ContextIds: 1 2
+; DUMP:     Edge from Callee [[BX]] to Caller: [[BAR]] AllocTypes: NotColdCold ContextIds: 4 5
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN3]] AllocTypes: NotCold ContextIds: 1
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN4]] AllocTypes: Cold ContextIds: 2
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN5]] AllocTypes: Cold ContextIds: 4
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN6]] AllocTypes: NotCold ContextIds: 5
+
+; DUMP: Node [[MAIN3]]
+; DUMP:     %call4 = call noundef ptr @_Z3barP1A(ptr noundef %a)  (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 1
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN3]] AllocTypes: NotCold ContextIds: 1
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[MAIN4]]
+; DUMP:     %call5 = call noundef ptr @_Z3barP1A(ptr noundef %a)  (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 2
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN4]] AllocTypes: Cold ContextIds: 2
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[MAIN1]]
+; DUMP:     %call = call noundef ptr @_Z3foov() (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 3
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN1]] AllocTypes: NotCold ContextIds: 3
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[BX]]
+; DUMP:     %call = call noundef ptr @_Z3foov() (clone 0)
+; DUMP:   AllocTypes: NotColdCold
+; DUMP:   ContextIds: 4 5
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[BX]] AllocTypes: NotColdCold ContextIds: 4 5
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[BX]] to Caller: [[BAR]] AllocTypes: NotColdCold ContextIds: 4 5
+
+; DUMP: Node [[MAIN5]]
+; DUMP:     %call2 = call noundef ptr @_Z3barP1A(ptr noundef %b)  (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 4
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN5]] AllocTypes: Cold ContextIds: 4
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[MAIN6]]
+; DUMP:     %call3 = call noundef ptr @_Z3barP1A(ptr noundef %b)  (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 5
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN6]] AllocTypes: NotCold ContextIds: 5
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[MAIN2]]
+; DUMP:     %call1 = call noundef ptr @_Z3foov()  (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 6
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[FOO2]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 6
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[FOO2]]
+; DUMP:     %call = call noalias noundef nonnull ptr @_Znam(i64 noundef 10) #7  (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 6
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[FOO2]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 6
+; DUMP:   Clone of [[FOO]]
+
 
 ; DOT: digraph "postbuild" {
 ; DOT:  label="postbuild";
 ; DOT:   Node[[FOO:0x[a-z0-9]+]] [shape=record,tooltip="N[[FOO]] ContextIds: 1 2 3 4 5 6",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: Alloc0\n_Z3foov -\> _Znam}"];
 ; DOT:   Node[[AX:0x[a-z0-9]+]] [shape=record,tooltip="N[[AX]] ContextIds: 1 2",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 8256774051149711748\n_ZN1A1xEv -\> _Z3foov}"];
 ; DOT:  Node[[AX]] -> Node[[FOO]][tooltip="ContextIds: 1 2",fillcolor="mediumorchid1"];
 ; DOT:   Node[[BAR:0x[a-z0-9]+]] [shape=record,tooltip="N[[BAR]] ContextIds: 1 2 4 5",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 13626499562959447861\nnull call (external)}"];
 ; DOT:  Node[[BAR]] -> Node[[AX]][tooltip="ContextIds: 1 2",fillcolor="mediumorchid1"];
 ; DOT:  Node[[BAR]] -> Node[[BX:0x[a-z0-9]+]][tooltip="ContextIds: 4 5",fillcolor="mediumorchid1"];
 ; DOT:   Node[[MAIN1:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN1]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 748269490701775343\nmain -\> _Z3barP1A}"];
 ; DOT:  Node[[MAIN1]] -> Node[[BAR]][tooltip="ContextIds: 1",fillcolor="brown1"];
 ; DOT:   Node[[MAIN2:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN2]] ContextIds: 2",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 12699492813229484831\nmain -\> _Z3barP1A}"];
 ; DOT:  Node[[MAIN2]] -> Node[[BAR]][tooltip="ContextIds: 2",fillcolor="cyan"];
 ; DOT:   Node[[MAIN3:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN3]] ContextIds: 3",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 8632435727821051414\nmain -\> _Z3foov}"];
 ; DOT:  Node[[MAIN3]] -> Node[[FOO]][tooltip="ContextIds: 3",fillcolor="brown1"];
 ; DOT:   Node[[BX]] [shape=record,tooltip="N[[BX]] ContextIds: 4 5",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 13614864978754796978\n_ZN1B1xEv -\> _Z3foov}"];
 ; DOT:  Node[[BX]] -> Node[[FOO]][tooltip="ContextIds: 4 5",fillcolor="mediumorchid1"];
 ; DOT:   Node[[MAIN4:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN4]] ContextIds: 4",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 6792096022461663180\nmain -\> _Z3barP1A}"];
 ; DOT:  Node[[MAIN4]] -> Node[[BAR]][tooltip="ContextIds: 4",fillcolor="cyan"];
 ; DOT:   Node[[MAIN5:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN5]] ContextIds: 5",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 15737101490731057601\nmain -\> _Z3barP1A}"];
 ; DOT:  Node[[MAIN5]] -> Node[[BAR]][tooltip="ContextIds: 5",fillcolor="brown1"];
 ; DOT:   Node[[MAIN6:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN6]] ContextIds: 6",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 15025054523792398438\nmain -\> _Z3foov}"];
 ; DOT:  Node[[MAIN6]] -> Node[[FOO]][tooltip="ContextIds: 6",fillcolor="cyan"];
 ; DOT: }
+
+
+; DOTCLONED: digraph "cloned" {
+; DOTCLONED:  label="cloned";
+; DOTCLONED:   Node[[FOO2:0x[a-z0-9]+]] [shape=record,tooltip="N[[FOO2]] ContextIds: 1 2 3 4 5",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: Alloc0\n_Z3foov -\> _Znam}"];
+; DOTCLONED:   Node[[AX:0x[a-z0-9]+]] [shape=record,tooltip="N[[AX]] ContextIds: 1 2",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 8256774051149711748\n_ZN1A1xEv -\> _Z3foov}"];
+; DOTCLONED:  Node[[AX]] -> Node[[FOO2]][tooltip="ContextIds: 1 2",fillcolor="mediumorchid1"];
+; DOTCLONED:   Node[[BAR:0x[a-z0-9]+]] [shape=record,tooltip="N[[BAR]] ContextIds: 1 2 4 5",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 13626499562959447861\nnull call (external)}"];
+; DOTCLONED:  Node[[BAR]] -> Node[[AX]][tooltip="ContextIds: 1 2",fillcolor="mediumorchid1"];
+; DOTCLONED:  Node[[BAR]] -> Node[[BX:0x[a-z0-9]+]][tooltip="ContextIds: 4 5",fillcolor="mediumorchid1"];
+; DOTCLONED:   Node[[MAIN1:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN1]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 748269490701775343\nmain -\> _Z3barP1A}"];
+; DOTCLONED:  Node[[MAIN1]] -> Node[[BAR]][tooltip="ContextIds: 1",fillcolor="brown1"];
+; DOTCLONED:   Node[[MAIN2:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN2]] ContextIds: 2",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 12699492813229484831\nmain -\> _Z3barP1A}"];
+; DOTCLONED:  Node[[MAIN2]] -> Node[[BAR]][tooltip="ContextIds: 2",fillcolor="cyan"];
+; DOTCLONED:   Node[[MAIN3:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN3]] ContextIds: 3",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 8632435727821051414\nmain -\> _Z3foov}"];
+; DOTCLONED:  Node[[MAIN3]] -> Node[[FOO2]][tooltip="ContextIds: 3",fillcolor="brown1"];
+; DOTCLONED:   Node[[BX]] [shape=record,tooltip="N[[BX]] ContextIds: 4 5",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 13614864978754796978\n_ZN1B1xEv -\> _Z3foov}"];
+; DOTCLONED:  Node[[BX]] -> Node[[FOO2]][tooltip="ContextIds: 4 5",fillcolor="mediumorchid1"];
+; DOTCLONED:   Node[[MAIN4:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN4]] ContextIds: 4",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 6792096022461663180\nmain -\> _Z3barP1A}"];
+; DOTCLONED:  Node[[MAIN4]] -> Node[[BAR]][tooltip="ContextIds: 4",fillcolor="cyan"];
+; DOTCLONED:   Node[[MAIN5:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN5]] ContextIds: 5",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 15737101490731057601\nmain -\> _Z3barP1A}"];
+; DOTCLONED:  Node[[MAIN5]] -> Node[[BAR]][tooltip="ContextIds: 5",fillcolor="brown1"];
+; DOTCLONED:   Node[[MAIN6:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN6]] ContextIds: 6",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 15025054523792398438\nmain -\> _Z3foov}"];
+; DOTCLONED:  Node[[MAIN6]] -> Node[[FOO2:0x[a-z0-9]+]][tooltip="ContextIds: 6",fillcolor="cyan"];
+; DOTCLONED:   Node[[FOO2]] [shape=record,tooltip="N[[FOO2]] ContextIds: 6",fillcolor="cyan",style="filled",color="blue",style="filled,bold,dashed",label="{OrigId: Alloc0\n_Z3foov -\> _Znam}"];
+; DOTCLONED: }

llvm/test/Transforms/MemProfContextDisambiguation/inlined.ll

 ;; The IR was then reduced using llvm-reduce with the expected FileCheck input.
 
 ; RUN: opt -passes=memprof-context-disambiguation \
 ; RUN:  -memprof-verify-ccg -memprof-verify-nodes -memprof-dump-ccg \
 ; RUN:  -memprof-export-to-dot -memprof-dot-file-path-prefix=%t. \
 ; RUN:  %s -S 2>&1 | FileCheck %s --check-prefix=DUMP
 
 ; RUN:  cat %t.ccg.postbuild.dot | FileCheck %s --check-prefix=DOT
+;; We should create clones for foo and bar for the call from main to allocate
+;; cold memory.
+; RUN:  cat %t.ccg.cloned.dot | FileCheck %s --check-prefix=DOTCLONED
 
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define internal ptr @_Z3barv() {
 entry:
   %call = call noalias noundef nonnull ptr @_Znam(i64 noundef 10) #7, !memprof !0, !callsite !5

 ; DUMP:   AllocTypes: NotColdCold
 ; DUMP:   ContextIds: 1 2
 ; DUMP:   CalleeEdges:
 ; DUMP:     Edge from Callee [[BAR]] to Caller: [[FOO]] AllocTypes: NotColdCold ContextIds: 1 2
 ; DUMP:   CallerEdges:
 ; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN1]] AllocTypes: NotCold ContextIds: 1
 ; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 2
 
+; DUMP: CCG after cloning:
+; DUMP: Callsite Context Graph:
+; DUMP: Node [[BAR]]
+; DUMP:     %call = call noalias noundef nonnull ptr @_Znam(i64 noundef 10) #7  (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 1
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[FOO]] AllocTypes: NotCold ContextIds: 1
+; DUMP:         Clones: [[BAR2:0x[a-z0-9]+]]
+
+; DUMP: Node [[FOO2]]
+; DUMP:   null Call
+; DUMP:   AllocTypes: NotColdCold
+; DUMP:   ContextIds: 3 4
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAZ]] to Caller: [[FOO2]] AllocTypes: NotColdCold ContextIds: 3 4
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[FOO2]] to Caller: [[MAIN1]] AllocTypes: NotCold ContextIds: 3
+; DUMP:     Edge from Callee [[FOO2]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 4
+
+; DUMP: Node [[MAIN1]]
+; DUMP:     %call = call noundef ptr @_Z3foov() (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 1 3
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[FOO2]] to Caller: [[MAIN1]] AllocTypes: NotCold ContextIds: 3
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN1]] AllocTypes: NotCold ContextIds: 1
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[MAIN2]]
+; DUMP:     %call1 = call noundef ptr @_Z3foov()  (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 2 4
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[FOO2]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 4
+; DUMP:     Edge from Callee [[FOO3:0x[a-z0-9]+]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 2
+; DUMP:   CallerEdges:
+
+; DUMP: Node [[BAZ]]
+; DUMP:     %call.i = call noalias noundef nonnull ptr @_Znam(i64 noundef 10) #7  (clone 0)
+; DUMP:   AllocTypes: NotColdCold
+; DUMP:   ContextIds: 3 4
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[BAZ]] to Caller: [[FOO2]] AllocTypes: NotColdCold ContextIds: 3 4
+
+; DUMP: Node [[FOO]]
+; DUMP:     %call.i = call noundef ptr @_Z3barv() (clone 0)
+; DUMP:   AllocTypes: NotCold
+; DUMP:   ContextIds: 1
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[FOO]] AllocTypes: NotCold ContextIds: 1
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN1]] AllocTypes: NotCold ContextIds: 1
+; DUMP:         Clones: [[FOO3]]
+
+; DUMP: Node [[FOO3]]
+; DUMP:     %call.i = call noundef ptr @_Z3barv() (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 2
+; DUMP:   CalleeEdges:
+; DUMP:     Edge from Callee [[BAR2]] to Caller: [[FOO3]] AllocTypes: Cold ContextIds: 2
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[FOO3]] to Caller: [[MAIN2]] AllocTypes: Cold ContextIds: 2
+; DUMP:         Clone of [[FOO]]
+
+; DUMP: Node [[BAR2]]
+; DUMP:     %call = call noalias noundef nonnull ptr @_Znam(i64 noundef 10) #7  (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 2
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[BAR2]] to Caller: [[FOO3]] AllocTypes: Cold ContextIds: 2
+; DUMP:         Clone of [[BAR]]
+
 
 ; DOT: digraph "postbuild" {
 ; DOT:  label="postbuild";
 ; DOT:   Node[[BAR:0x[a-z0-9]+]] [shape=record,tooltip="N[[BAR]] ContextIds: 1 2",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: Alloc0\n_Z3barv -\> _Znam}"];
 ; DOT:   Node[[FOO:0x[a-z0-9]+]] [shape=record,tooltip="N[[FOO]] ContextIds: 3 4",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 2732490490862098848\nnull call (external)}"];
 ; DOT:  Node[[FOO]] -> Node[[BAZ:0x[a-z0-9]+]][tooltip="ContextIds: 3 4",fillcolor="mediumorchid1"];
 ; DOT:   Node[[MAIN1:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN1]] ContextIds: 1 3",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 8632435727821051414\nmain -\> _Z3foov}"];
 ; DOT:  Node[[MAIN1]] -> Node[[FOO]][tooltip="ContextIds: 3",fillcolor="brown1"];
 ; DOT:  Node[[MAIN1]] -> Node[[FOO2:0x[a-z0-9]+]][tooltip="ContextIds: 1",fillcolor="brown1"];
 ; DOT:   Node[[MAIN2:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN2]] ContextIds: 2 4",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 15025054523792398438\nmain -\> _Z3foov}"];
 ; DOT:  Node[[MAIN2]] -> Node[[FOO]][tooltip="ContextIds: 4",fillcolor="cyan"];
 ; DOT:  Node[[MAIN2]] -> Node[[FOO2]][tooltip="ContextIds: 2",fillcolor="cyan"];
 ; DOT:  Node[[BAZ]] [shape=record,tooltip="N[[BAZ]] ContextIds: 3 4",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: Alloc2\n_Z3bazv -\> _Znam}"];
 ; DOT:  Node[[FOO2]] [shape=record,tooltip="N[[FOO2]] ContextIds: 1 2",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 0\n_Z3foov -\> _Z3barv}"];
 ; DOT:  Node[[FOO2]] -> Node[[BAR]][tooltip="ContextIds: 1 2",fillcolor="mediumorchid1"];
 ; DOT: }
+
+
+; DOTCLONED: digraph "cloned" {
+; DOTCLONED:  label="cloned";
+; DOTCLONED:  Node[[BAR:0x[a-z0-9]+]] [shape=record,tooltip="N[[BAR]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled",label="{OrigId: Alloc0\n_Z3barv -\> _Znam}"];
+; DOTCLONED:   Node[[FOO2:0x[a-z0-9]+]] [shape=record,tooltip="N[[FOO2]] ContextIds: 3 4",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: 2732490490862098848\nnull call (external)}"];
+; DOTCLONED:  Node[[FOO2]] -> Node[[BAZ:0x[a-z0-9]+]][tooltip="ContextIds: 3 4",fillcolor="mediumorchid1"];
+; DOTCLONED:   Node[[MAIN1:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN1]] ContextIds: 1 3",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 8632435727821051414\nmain -\> _Z3foov}"];
+; DOTCLONED:  Node[[MAIN1]] -> Node[[FOO2]][tooltip="ContextIds: 3",fillcolor="brown1"];
+; DOTCLONED:  Node[[MAIN1]] -> Node[[FOO:0x[a-z0-9]+]][tooltip="ContextIds: 1",fillcolor="brown1"];
+; DOTCLONED:   Node[[MAIN2:0x[a-z0-9]+]] [shape=record,tooltip="N[[MAIN2]] ContextIds: 2 4",fillcolor="cyan",style="filled",style="filled",label="{OrigId: 15025054523792398438\nmain -\> _Z3foov}"];
+; DOTCLONED:  Node[[MAIN2]] -> Node[[FOO2]][tooltip="ContextIds: 4",fillcolor="cyan"];
+; DOTCLONED:  Node[[MAIN2]] -> Node[[FOO3:0x[a-z0-9]+]][tooltip="ContextIds: 2",fillcolor="cyan"];
+; DOTCLONED:  Node[[BAZ]] [shape=record,tooltip="N[[BAZ]] ContextIds: 3 4",fillcolor="mediumorchid1",style="filled",style="filled",label="{OrigId: Alloc2\n_Z3bazv -\> _Znam}"];
+; DOTCLONED:  Node[[FOO]] [shape=record,tooltip="N[[FOO]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled",label="{OrigId: 0\n_Z3foov -\> _Z3barv}"];
+; DOTCLONED:  Node[[FOO]] -> Node[[BAR]][tooltip="ContextIds: 1",fillcolor="brown1"];
+; DOTCLONED:   Node[[FOO3]] [shape=record,tooltip="N[[FOO3]] ContextIds: 2",fillcolor="cyan",style="filled",color="blue",style="filled,bold,dashed",label="{OrigId: 0\n_Z3foov -\> _Z3barv}"];
+; DOTCLONED:  Node[[FOO3]] -> Node[[BAR2:0x[a-z0-9]+]][tooltip="ContextIds: 2",fillcolor="cyan"];
+; DOTCLONED:   Node[[BAR2]] [shape=record,tooltip="N[[BAR2]] ContextIds: 2",fillcolor="cyan",style="filled",color="blue",style="filled,bold,dashed",label="{OrigId: Alloc0\n_Z3barv -\> _Znam}"];
+; DOTCLONED: }