[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

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

1959

nit: constexpr

2006

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

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

211 ↗

(On Diff #508269)

Should we assert that Clone->CloneOf is unset?

1181 ↗

(On Diff #508269)

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

1942 ↗

(On Diff #508269)

nit: "iterate on that"?

1946 ↗

(On Diff #508269)

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.

1949 ↗

(On Diff #508269)

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

1957 ↗

(On Diff #508269)

The code below allows 1 caller?

1966 ↗

(On Diff #508269)

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.

1994 ↗

(On Diff #508269)

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

1998 ↗

(On Diff #508269)

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

2013 ↗

(On Diff #508269)

nit: cases

2018 ↗

(On Diff #508269)

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

2027 ↗

(On Diff #508269)

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

1181 ↗

(On Diff #508269)

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

1949 ↗

(On Diff #508269)

It would have been removed. Added assert.

1957 ↗

(On Diff #508269)

Fixed wording - I mean only a single caller.

1994 ↗

(On Diff #508269)

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.

1998 ↗

(On Diff #508269)

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

1994 ↗

(On Diff #508269)

Sounds good, thanks for the explanation.

1998 ↗

(On Diff #508269)

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

[tejohnson]

llvm/lib/Transforms/IPO/MemProfContextDisambiguation.cpp

1998 ↗

(On Diff #508269)

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

2004 ↗

(On Diff #515979)

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

2004 ↗

(On Diff #515979)

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

2004 ↗

(On Diff #515979)

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

2004 ↗

(On Diff #515979)

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

2004 ↗

(On Diff #515979)

Fixed in 969268831b9e409dd66af10c12fe17431e09b70f.

[aganea]

llvm/lib/Transforms/IPO/MemProfContextDisambiguation.cpp

2004 ↗

(On Diff #515979)

Thank you!

llvm/lib/Transforms/IPO/PGHOContextDisambiguation.cpp

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 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);
+
   /// Saves edge removed from graph in the RemovedEdges set for subsequent
   /// deletion by deleteRemovedEdges at a point where it is no longer saved
   /// in any intermediate data structures.
   void recordRemovedEdge(ContextEdge *Edge);
 
   /// Checks if edge has been removed from graph.
   bool isRemovedEdge(const ContextEdge *Edge);
 
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(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(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;
void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
   }
   ContextEdge *Edge =
       new ContextEdge(this, Caller, (uint8_t)AllocType, {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);
+      EI = Node->CalleeEdges.erase(EI);
+      // Save edges for later deletion, as they may be saved in data structures.
+      RemovedEdges.insert(Edge);
+      // Denote that the edge is removed by setting the nodes to null
+      Edge->Callee = nullptr;
+      Edge->Caller = nullptr;
+    } else
+      ++EI;
+  }
+}
+
+template <typename DerivedCCG, typename FuncTy, typename CallTy>
 void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::recordRemovedEdge(
     ContextEdge *Edge) {
   assert(Edge->ContextIds.empty());
   // Save edge for later deletion, as it may be saved in data structures.
   RemovedEdges.insert(Edge);
   // Denote that the edge is removed by setting the nodes to null.
   Edge->Callee = nullptr;
   Edge->Caller = 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>
 ContextNode<DerivedCCG, FuncTy, CallTy> *
 CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::addAllocNode(CallInfo Call) {
   assert(!getNodeForAlloc(Call));
   ContextNode *AllocNode = new ContextNode(/*IsAllocation*/ true, Call);
   AllocationCallToContextNodeMap[Call] = AllocNode;
   // Use LastContextId as a uniq id for MIB allocation nodes.
   AllocNode->OrigStackOrAllocId = LastContextId;
   // Alloc type should be updated as we add in the MIBs. We should assert
return Callee == FSToVIMap[Func] ||
          // If callee is an alias, check the aliasee, since only function
          // summary base objects will contain the stack node summaries and thus
          // get a context node.
          (Alias && Alias->getAliaseeVI() == FSToVIMap[Func]);
 }
 
 template <typename DerivedCCG, typename FuncTy, typename CallTy>
 CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::~CallsiteContextGraph() {
+  deleteRemovedEdges();
   auto DeleteCallerEdges = [](ContextNode *Node) {
     for (auto *Edge : Node->CallerEdges)
       delete Edge;
   };
   auto DeleteNodeCloneAndCallerEdges = [DeleteCallerEdges](ContextNode *Node) {
     for (auto *Clone : Node->Clones) {
       DeleteCallerEdges(Clone);
       delete Clone;
if (VerifyCCG) {
     for (auto *Edge : OldCallee->CalleeEdges)
       checkNode<DerivedCCG, FuncTy, CallTy>(Edge->Callee);
     for (auto *Edge : NewCallee->CalleeEdges)
       checkNode<DerivedCCG, FuncTy, CallTy>(Edge->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);
+
+  // Clean up edges removed during the cloning.
+  deleteRemovedEdges();
+}
+
+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 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)
+      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 no more callers.
+  if (hasSingleAllocType(Node->AllocTypes) || Node->CallerEdges.size() <= 1)
+    return;
+
+  // We need to clone.
+
+  // 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.
+  auto AllocTypesMatch = [](const std::vector<uint8_t> &InAllocTypes,
+                            const std::vector<ContextEdge *> &Edges) {
+    return std::equal(InAllocTypes.begin(), InAllocTypes.end(), Edges.begin(),
+                      [](const uint8_t &l, const ContextEdge *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);
+                      });
+  };
+
+  // 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.
+  unsigned AllocTypeCloningPriority[] = {/*None*/ 3, /*NotCold*/ 4, /*Cold*/ 1,
+                                         /*NotColdCold*/ 2};
+  std::sort(Node->CallerEdges.begin(), Node->CallerEdges.end(),
+            [&](const ContextEdge *A, const 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);
+
+  // 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 *Edge = *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;
+    for (auto *CalleeEdge : Node->CalleeEdges)
+      CalleeEdgeAllocTypesForCallerEdge.push_back(intersectAllocTypes(
+          CalleeEdge->getContextIds(), Edge->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(Edge->AllocTypes != (uint8_t)AllocationType::None);
+    assert(Node->AllocTypes != (uint8_t)AllocationType::None);
+    if (allocTypeToUse(Edge->AllocTypes) == allocTypeToUse(Node->AllocTypes) &&
+        AllocTypesMatch(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(Edge->AllocTypes))
+        continue;
+
+      if (!AllocTypesMatch(CalleeEdgeAllocTypesForCallerEdge,
+                           CurClone->CalleeEdges))
+        continue;
+      Clone = CurClone;
+      break;
+    }
+
+    if (Clone)
+      moveEdgeToExistingCalleeClone(Edge, Clone, &EI);
+    else
+      Clone = moveEdgeToNewCalleeClone(Edge, &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, [&](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, [&](ContextEdge *E) {
+    return E->AllocTypes == (uint8_t)AllocationType::None;
+  }));
+  assert(llvm::none_of(Node->CallerEdges, [&](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("ccg.postbuild.dot");
 
   if (VerifyCCG) {
     check();
   }
 
+  identifyClones();
+
+  if (VerifyCCG) {
+    check();
+  }
+
+  if (DumpCCG) {
+    dbgs() << "CCG after cloning:\n";
+    dbgs() << *this;
+  }
+  if (ExportToDot)
+    exportToDot("ccg.cloned.dot");
+
   return false;
 }
 
 bool PGHOContextDisambiguation::processModule(
     Module &M) {
   bool Changed = false;
 
   ModuleCallsiteContextGraph CCG(M);

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

 ; RUN:  -r=%t.o,_ZdaPv, \
 ; RUN:  -r=%t.o,sleep, \
 ; RUN:  -r=%t.o,_Znam, \
 ; RUN:  -pgho-verify-ccg -pgho-verify-nodes -pgho-dump-ccg \
 ; RUN:  -pgho-export-to-dot -pgho-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
 
 ; ModuleID = 'pgho-basic.ll'
 source_filename = "pgho-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"
 
 ; Function Attrs: mustprogress noinline norecurse optnone uwtable
 define dso_local noundef i32 @main(i32 noundef %argc, ptr noundef %argv) #0 {

 ; DUMP: Node [[MAIN2]]
 ; DUMP:   Callee: 6988045695824228603 (_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:0x[a-z0-9]+]]
+; 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:0x[a-z0-9]+]] AllocTypes: NotCold ContextIds: 1
+
+; DUMP: Node [[BAZ]]
+; DUMP:   Callee: 10756268697391741933 (_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:0x[a-z0-9]+]] AllocTypes: NotCold ContextIds: 1
+
+; DUMP: Node [[FOO]]
+; DUMP:   Callee: 17547784407117670007 (_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:0x[a-z0-9]+]] AllocTypes: NotCold ContextIds: 1
+
+; DUMP: Node [[MAIN1]]
+; DUMP:   Callee: 6988045695824228603 (_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 [[BAR2:0x[a-z0-9]+]]
+; 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:0x[a-z0-9]+]] AllocTypes: Cold ContextIds: 2
+
+; DUMP: Node [[BAZ2]]
+; DUMP:   Callee: 10756268697391741933 (_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:0x[a-z0-9]+]] AllocTypes: Cold ContextIds: 2
+
+; DUMP: Node [[FOO2]]
+; DUMP:   Callee: 17547784407117670007 (_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:0x[a-z0-9]+]] AllocTypes: Cold ContextIds: 2
+
+; DUMP: Node [[MAIN2]]
+; DUMP:   Callee: 6988045695824228603 (_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:
+
 
 ; DOT: digraph CallsiteContextGraph {
 ; DOT:     N[[BAR:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z3barv -\> alloc",tooltip="N[[BAR]] ContextIds: 2 1",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
 ; DOT:     N[[BAZ:0x[a-z0-9]+]] [shape="record",label="OrigId: 12481870273128938184\n_Z3bazv -\> _Z3barv",tooltip="N[[BAZ]] ContextIds: 2 1",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
 ; DOT:     N[[FOO:0x[a-z0-9]+]] [shape="record",label="OrigId: 2732490490862098848\n_Z3foov -\> _Z3bazv",tooltip="N[[FOO]] ContextIds: 2 1",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
 ; DOT:     N[[MAIN1:0x[a-z0-9]+]] [shape="record",label="OrigId: 15025054523792398438\nmain -\> _Z3foov",tooltip="N[[MAIN1]] ContextIds: 2",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
 ; DOT:     N[[MAIN2:0x[a-z0-9]+]] [shape="record",label="OrigId: 8632435727821051414\nmain -\> _Z3foov",tooltip="N[[MAIN2]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
 ; DOT:     // Edges:
 ; DOT:     N[[BAZ]] -> N[[BAR]][tooltip=" ContextIds: 1 2",fillcolor="mediumorchid1"]; // default|cold
 ; DOT:     N[[FOO]] -> N[[BAZ]][tooltip=" ContextIds: 1 2",fillcolor="mediumorchid1"]; // default|cold
 ; DOT:     N[[MAIN2]] -> N[[FOO]][tooltip=" ContextIds: 1",fillcolor="brown1"]; // default
 ; DOT:     N[[MAIN1]] -> N[[FOO]][tooltip=" ContextIds: 2",fillcolor="cyan"]; // cold
 ; DOT: }
+
+
+; DOTCLONED: digraph CallsiteContextGraph {
+; DOTCLONED:     N[[BAR2:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z3barv -\> alloc",tooltip="N[[BAR2]] ContextIds: 2",fillcolor="cyan",style="filled",color="blue",style="filled, bold, dashed"]; // callsite, cold
+; DOTCLONED:     N[[BAZ2:0x[a-z0-9]+]] [shape="record",label="OrigId: 0\n_Z3bazv -\> _Z3barv",tooltip="N[[BAZ2]] ContextIds: 2",fillcolor="cyan",style="filled",color="blue",style="filled, bold, dashed"]; // callsite, cold
+; DOTCLONED:     N[[FOO2:0x[a-z0-9]+]] [shape="record",label="OrigId: 0\n_Z3foov -\> _Z3bazv",tooltip="N[[FOO2]] ContextIds: 2",fillcolor="cyan",style="filled",color="blue",style="filled, bold, dashed"]; // callsite, cold
+; DOTCLONED:     N[[MAIN2:0x[a-z0-9]+]] [shape="record",label="OrigId: 15025054523792398438\nmain -\> _Z3foov",tooltip="N[[MAIN2]] ContextIds: 2",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
+; DOTCLONED:     N[[BAR:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z3barv -\> alloc",tooltip="N[[BAR]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
+; DOTCLONED:     N[[BAZ:0x[a-z0-9]+]] [shape="record",label="OrigId: 12481870273128938184\n_Z3bazv -\> _Z3barv",tooltip="N[[BAZ]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
+; DOTCLONED:     N[[FOO:0x[a-z0-9]+]] [shape="record",label="OrigId: 2732490490862098848\n_Z3foov -\> _Z3bazv",tooltip="N[[FOO]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
+; DOTCLONED:     N[[MAIN1:0x[a-z0-9]+]] [shape="record",label="OrigId: 8632435727821051414\nmain -\> _Z3foov",tooltip="N[[MAIN1]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
+; DOTCLONED:     // Edges:
+; DOTCLONED:     N[[BAZ2]] -> N[[BAR2]][tooltip=" ContextIds: 2",fillcolor="cyan"]; // cold
+; DOTCLONED:     N[[FOO2]] -> N[[BAZ2]][tooltip=" ContextIds: 2",fillcolor="cyan"]; // cold
+; DOTCLONED:     N[[MAIN2]] -> N[[FOO2]][tooltip=" ContextIds: 2",fillcolor="cyan"]; // cold
+; DOTCLONED:     N[[BAZ]] -> N[[BAR]][tooltip=" ContextIds: 1",fillcolor="brown1"]; // default
+; DOTCLONED:     N[[FOO]] -> N[[BAZ]][tooltip=" ContextIds: 1",fillcolor="brown1"]; // default
+; DOTCLONED:     N[[MAIN1]] -> N[[FOO]][tooltip=" ContextIds: 1",fillcolor="brown1"]; // default
+; DOTCLONED: }

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

 ; RUN:  -r=%t.o,sleep, \
 ; RUN:  -r=%t.o,_Znam, \
 ; RUN:  -pgho-verify-ccg -pgho-verify-nodes -pgho-dump-ccg \
 ; RUN:  -pgho-export-to-dot -pgho-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
 
 ; ModuleID = 'duplicate-context-ids.ll'
 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"
 
 ; Function Attrs: mustprogress noinline optnone uwtable
 define internal noundef ptr @_Z1Dv() #0 {

 ; 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 [[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: 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 [[D2:0x[a-z0-9]+]]
+; DUMP:   Versions: 1 MIB:
+; DUMP:     AllocType 2 StackIds: 0
+; DUMP:     AllocType 1 StackIds: 1
+; DUMP:   (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 4 1 3
+; 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: 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 [[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:
+
 
 ; DOTPRE: digraph CallsiteContextGraph {
 ; DOTPRE:     N[[D:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z1Dv -\> alloc",tooltip="N[[D]] ContextIds: 2 1",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
 ; DOTPRE:     N[[F:0x[a-z0-9]+]] [shape="record",label="OrigId: 13543580133643026784\nnull call (external)",tooltip="N[[F]] ContextIds: 2",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
 ; DOTPRE:     N[[C:0x[a-z0-9]+]] [shape="record",label="OrigId: 12176601099670543485\nnull call (external)",tooltip="N[[C]] ContextIds: 1",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
 ; DOTPRE:     // Edges:
 ; DOTPRE:     N[[C]] -> N[[D]][tooltip=" ContextIds: 1",fillcolor="cyan"]; // cold
 ; DOTPRE:     N[[F]] -> N[[D]][tooltip=" ContextIds: 2",fillcolor="brown1"]; // default
 ; DOTPRE: }
 
 
 ; DOTPOST: digraph CallsiteContextGraph {
 ; DOTPOST:     N[[D:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z1Dv -\> alloc",tooltip="N[[D]] ContextIds: 2 4 1 3",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
 ; DOTPOST:     N[[E:0x[a-z0-9]+]] [shape="record",label="OrigId: 0\n_Z1Ev -\> _Z1Dv",tooltip="N[[E]] ContextIds: 1",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
 ; DOTPOST:     N[[B:0x[a-z0-9]+]] [shape="record",label="OrigId: 0\n_Z1Bv -\> _Z1Dv",tooltip="N[[B]] ContextIds: 4",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
 ; DOTPOST:     N[[C:0x[a-z0-9]+]] [shape="record",label="OrigId: 0\n_Z1Cv -\> _Z1Dv",tooltip="N[[C]] ContextIds: 3",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
 ; DOTPOST:     N[[F:0x[a-z0-9]+]] [shape="record",label="OrigId: 13543580133643026784\n_Z1Fv -\> _Z1Dv",tooltip="N[[F]] ContextIds: 2",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
 ; DOTPOST:     // Edges:
 ; DOTPOST:     N[[F]] -> N[[D]][tooltip=" ContextIds: 2",fillcolor="brown1"]; // default
 ; DOTPOST:     N[[C]] -> N[[D]][tooltip=" ContextIds: 3",fillcolor="cyan"]; // cold
 ; DOTPOST:     N[[B]] -> N[[D]][tooltip=" ContextIds: 4",fillcolor="cyan"]; // cold
 ; DOTPOST:     N[[E]] -> N[[D]][tooltip=" ContextIds: 1",fillcolor="cyan"]; // cold
 ; DOTPOST: }
+
+
+; DOTCLONED: digraph CallsiteContextGraph {
+; DOTCLONED:     N[[D2:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z1Dv -\> alloc",tooltip="N[[D2]] ContextIds: 4 1 3",fillcolor="cyan",style="filled",color="blue",style="filled, bold, dashed"]; // callsite, cold
+; DOTCLONED:     N[[B:0x[a-z0-9]+]] [shape="record",label="OrigId: 0\n_Z1Bv -\> _Z1Dv",tooltip="N[[B]] ContextIds: 4",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
+; DOTCLONED:     N[[C:0x[a-z0-9]+]] [shape="record",label="OrigId: 0\n_Z1Cv -\> _Z1Dv",tooltip="N[[C]] ContextIds: 3",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
+; DOTCLONED:     N[[E:0x[a-z0-9]+]] [shape="record",label="OrigId: 0\n_Z1Ev -\> _Z1Dv",tooltip="N[[E]] ContextIds: 1",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
+; DOTCLONED:     N[[D:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z1Dv -\> alloc",tooltip="N[[D]] ContextIds: 2",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
+; DOTCLONED:     N[[F:0x[a-z0-9]+]] [shape="record",label="OrigId: 13543580133643026784\n_Z1Fv -\> _Z1Dv",tooltip="N[[F]] ContextIds: 2",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
+; DOTCLONED:     // Edges:
+; DOTCLONED:     N[[E]] -> N[[D2]][tooltip=" ContextIds: 1",fillcolor="cyan"]; // cold
+; DOTCLONED:     N[[C]] -> N[[D2]][tooltip=" ContextIds: 3",fillcolor="cyan"]; // cold
+; DOTCLONED:     N[[B]] -> N[[D2]][tooltip=" ContextIds: 4",fillcolor="cyan"]; // cold
+; DOTCLONED:     N[[F]] -> N[[D]][tooltip=" ContextIds: 2",fillcolor="brown1"]; // default
+; DOTCLONED: }

llvm/test/ThinLTO/X86/pgho-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:  -pgho-verify-ccg -pgho-verify-nodes -pgho-dump-ccg \
 ; RUN:  -pgho-export-to-dot -pgho-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
 
 ; ModuleID = 'indirectcall.ll'
 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"
 
 %class.B = type { %class.A }
 %class.A = type { 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:0x[a-z0-9]+]]
+; 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: 2 4 1 3 5
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[AX:0x[a-z0-9]+]] AllocTypes: NotColdCold ContextIds: 1 2
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[BX:0x[a-z0-9]+]] AllocTypes: NotColdCold ContextIds: 4 5
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN1:0x[a-z0-9]+]] AllocTypes: NotCold ContextIds: 3
+
+; DUMP: Node [[AX]]
+; DUMP:   Callee: 12914368124089294956 (_Z3foov) Clones: 0 StackIds: 6    (clone 0)
+; DUMP:   AllocTypes: NotColdCold
+; DUMP:   ContextIds: 2 1
+; 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:0x[a-z0-9]+]] AllocTypes: NotColdCold ContextIds: 1 2
+
+; DUMP: Node [[BAR]]
+; DUMP:   null Call
+; DUMP:   AllocTypes: NotColdCold
+; DUMP:   ContextIds: 2 4 1 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:0x[a-z0-9]+]] AllocTypes: NotCold ContextIds: 1
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN4:0x[a-z0-9]+]] AllocTypes: Cold ContextIds: 2
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN5:0x[a-z0-9]+]] AllocTypes: Cold ContextIds: 4
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN6:0x[a-z0-9]+]] 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 [[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 [[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 [[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 [[FOO2:0x[a-z0-9]+]]
+; 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:0x[a-z0-9]+]] AllocTypes: Cold ContextIds: 6
+
+; 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:
+
 
 ; DOT: digraph CallsiteContextGraph {
 ; DOT:     N[[FOO:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z3foov -\> alloc",tooltip="N[[FOO]] ContextIds: 2 4 6 1 3 5",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
 ; DOT:     N[[MAIN1:0x[a-z0-9]+]] [shape="record",label="OrigId: 15025054523792398438\nmain -\> _Z3foov",tooltip="N[[MAIN1]] ContextIds: 6",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
 ; DOT:     N[[BX:0x[a-z0-9]+]] [shape="record",label="OrigId: 13614864978754796978\n_ZN1B1xEv -\> _Z3foov",tooltip="N[[BX]] ContextIds: 4 5",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
 ;; Bar contains an indirect call, with multiple targets. It's call should be null.
 ; DOT:     N[[BAR:0x[a-z0-9]+]] [shape="record",label="OrigId: 13626499562959447861\nnull call (external)",tooltip="N[[BAR]] ContextIds: 2 4 1 5",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
 ; DOT:     N[[MAIN2:0x[a-z0-9]+]] [shape="record",label="OrigId: 15737101490731057601\nmain -\> _Z3barP1A",tooltip="N[[MAIN2]] ContextIds: 5",fillcolor="brown1",style="filled",style="filled"]; // callsite, default

 ; DOT:     N[[MAIN1]] -> N[[FOO]][tooltip=" ContextIds: 6",fillcolor="cyan"]; // cold
 ; DOT:     N[[BAR]] -> N[[BX]][tooltip=" ContextIds: 4 5",fillcolor="mediumorchid1"]; // default|cold
 ; DOT:     N[[MAIN5]] -> N[[BAR]][tooltip=" ContextIds: 1",fillcolor="brown1"]; // default
 ; DOT:     N[[MAIN4]] -> N[[BAR]][tooltip=" ContextIds: 2",fillcolor="cyan"]; // cold
 ; DOT:     N[[MAIN3]] -> N[[BAR]][tooltip=" ContextIds: 4",fillcolor="cyan"]; // cold
 ; DOT:     N[[MAIN2]] -> N[[BAR]][tooltip=" ContextIds: 5",fillcolor="brown1"]; // default
 ; DOT:     N[[BAR]] -> N[[AX]][tooltip=" ContextIds: 1 2",fillcolor="mediumorchid1"]; // default|cold
 ; DOT: }
+
+
+; DOTCLONED: digraph CallsiteContextGraph {
+; DOTCLONED:     N[[FOO2:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z3foov -\> alloc",tooltip="N[[FOO2]] ContextIds: 6",fillcolor="cyan",style="filled",color="blue",style="filled, bold, dashed"]; // callsite, cold
+; DOTCLONED:     N[[MAIN1:0x[a-z0-9]+]] [shape="record",label="OrigId: 15025054523792398438\nmain -\> _Z3foov",tooltip="N[[MAIN1]] ContextIds: 6",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
+; DOTCLONED:     N[[FOO:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z3foov -\> alloc",tooltip="N[[FOO]] ContextIds: 2 4 1 3 5",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
+; DOTCLONED:     N[[MAIN6:0x[a-z0-9]+]] [shape="record",label="OrigId: 8632435727821051414\nmain -\> _Z3foov",tooltip="N[[MAIN6]] ContextIds: 3",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
+; DOTCLONED:     N[[BX:0x[a-z0-9]+]] [shape="record",label="OrigId: 13614864978754796978\n_ZN1B1xEv -\> _Z3foov",tooltip="N[[BX]] ContextIds: 4 5",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
+;; Bar contains an indirect call, with multiple targets. It's call should be null.
+; DOTCLONED:     N[[BAR:0x[a-z0-9]+]] [shape="record",label="OrigId: 13626499562959447861\nnull call (external)",tooltip="N[[BAR]] ContextIds: 2 4 1 5",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
+; DOTCLONED:     N[[MAIN2:0x[a-z0-9]+]] [shape="record",label="OrigId: 15737101490731057601\nmain -\> _Z3barP1A",tooltip="N[[MAIN2]] ContextIds: 5",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
+; DOTCLONED:     N[[MAIN3:0x[a-z0-9]+]] [shape="record",label="OrigId: 6792096022461663180\nmain -\> _Z3barP1A",tooltip="N[[MAIN3]] ContextIds: 4",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
+; DOTCLONED:     N[[MAIN4:0x[a-z0-9]+]] [shape="record",label="OrigId: 12699492813229484831\nmain -\> _Z3barP1A",tooltip="N[[MAIN4]] ContextIds: 2",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
+; DOTCLONED:     N[[MAIN5:0x[a-z0-9]+]] [shape="record",label="OrigId: 748269490701775343\nmain -\> _Z3barP1A",tooltip="N[[MAIN5]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
+; DOTCLONED:     N[[AX:0x[a-z0-9]+]] [shape="record",label="OrigId: 8256774051149711748\n_ZN1A1xEv -\> _Z3foov",tooltip="N[[AX]] ContextIds: 2 1",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
+; DOTCLONED:     // Edges:
+; DOTCLONED:     N[[MAIN1]] -> N[[FOO2]][tooltip=" ContextIds: 6",fillcolor="cyan"]; // cold
+; DOTCLONED:     N[[AX]] -> N[[FOO]][tooltip=" ContextIds: 1 2",fillcolor="mediumorchid1"]; // default|cold
+; DOTCLONED:     N[[BX]] -> N[[FOO]][tooltip=" ContextIds: 4 5",fillcolor="mediumorchid1"]; // default|cold
+; DOTCLONED:     N[[MAIN6]] -> N[[FOO]][tooltip=" ContextIds: 3",fillcolor="brown1"]; // default
+; DOTCLONED:     N[[BAR]] -> N[[BX]][tooltip=" ContextIds: 4 5",fillcolor="mediumorchid1"]; // default|cold
+; DOTCLONED:     N[[MAIN5]] -> N[[BAR]][tooltip=" ContextIds: 1",fillcolor="brown1"]; // default
+; DOTCLONED:     N[[MAIN4]] -> N[[BAR]][tooltip=" ContextIds: 2",fillcolor="cyan"]; // cold
+; DOTCLONED:     N[[MAIN3]] -> N[[BAR]][tooltip=" ContextIds: 4",fillcolor="cyan"]; // cold
+; DOTCLONED:     N[[MAIN2]] -> N[[BAR]][tooltip=" ContextIds: 5",fillcolor="brown1"]; // default
+; DOTCLONED:     N[[BAR]] -> N[[AX]][tooltip=" ContextIds: 1 2",fillcolor="mediumorchid1"]; // default|cold
+; DOTCLONED: }

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

 ; RUN:  -r=%t.o,_ZdaPv, \
 ; RUN:  -r=%t.o,sleep, \
 ; RUN:  -r=%t.o,_Znam, \
 ; RUN:  -pgho-verify-ccg -pgho-verify-nodes -pgho-dump-ccg \
 ; RUN:  -pgho-export-to-dot -pgho-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
 
 ; ModuleID = 'inlined.ll'
 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"
 
 ; Function Attrs: mustprogress uwtable
 define internal noundef ptr @_Z3barv() #0 {

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

llvm/test/Transforms/PGHOContextDisambiguation/basic.ll

 ;; memory freed after sleep(10) results in cold lifetimes.
 
 ; RUN: opt -passes=pgho-context-disambiguation \
 ; RUN:  -pgho-verify-ccg -pgho-verify-nodes -pgho-dump-ccg \
 ; RUN:  -pgho-export-to-dot -pgho-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
 
 ; ModuleID = 'basic.ll'
 source_filename = "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"
 
 ; Function Attrs: mustprogress noinline norecurse optnone uwtable
 define dso_local noundef i32 @main(i32 noundef %argc, ptr noundef %argv) #0 {

 ; 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: 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: 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: 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 [[BAR2:0x[a-z0-9]+]]
+; 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:0x[a-z0-9]+]] AllocTypes: Cold ContextIds: 2
+
+; 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:0x[a-z0-9]+]] AllocTypes: Cold ContextIds: 2
+
+; 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: 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:
+
 
 ; DOT: digraph CallsiteContextGraph {
 ; DOT:     N[[BAR:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z3barv -\> _Znam",tooltip="N[[BAR]] ContextIds: 2 1",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
 ; DOT:     N[[BAZ:0x[a-z0-9]+]] [shape="record",label="OrigId: 12481870273128938184\n_Z3bazv -\> _Z3barv",tooltip="N[[BAZ]] ContextIds: 2 1",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
 ; DOT:     N[[FOO:0x[a-z0-9]+]] [shape="record",label="OrigId: 2732490490862098848\n_Z3foov -\> _Z3bazv",tooltip="N[[FOO]] ContextIds: 2 1",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
 ; DOT:     N[[MAIN1:0x[a-z0-9]+]] [shape="record",label="OrigId: 15025054523792398438\nmain -\> _Z3foov",tooltip="N[[MAIN1]] ContextIds: 2",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
 ; DOT:     N[[MAIN2:0x[a-z0-9]+]] [shape="record",label="OrigId: 8632435727821051414\nmain -\> _Z3foov",tooltip="N[[MAIN2]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
 ; DOT:     // Edges:
 ; DOT:     N[[BAZ]] -> N[[BAR]][tooltip=" ContextIds: 1 2",fillcolor="mediumorchid1"]; // default|cold
 ; DOT:     N[[FOO]] -> N[[BAZ]][tooltip=" ContextIds: 1 2",fillcolor="mediumorchid1"]; // default|cold
 ; DOT:     N[[MAIN2]] -> N[[FOO]][tooltip=" ContextIds: 1",fillcolor="brown1"]; // default
 ; DOT:     N[[MAIN1]] -> N[[FOO]][tooltip=" ContextIds: 2",fillcolor="cyan"]; // cold
 ; DOT: }
+
+
+; DOTCLONED: digraph CallsiteContextGraph {
+; DOTCLONED:     N[[BAR2:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z3barv -\> _Znam",tooltip="N[[BAR2]] ContextIds: 2",fillcolor="cyan",style="filled",color="blue",style="filled, bold, dashed"]; // callsite, cold
+; DOTCLONED:     N[[BAZ2:0x[a-z0-9]+]] [shape="record",label="OrigId: 0\n_Z3bazv -\> _Z3barv",tooltip="N[[BAZ2]] ContextIds: 2",fillcolor="cyan",style="filled",color="blue",style="filled, bold, dashed"]; // callsite, cold
+; DOTCLONED:     N[[FOO2:0x[a-z0-9]+]] [shape="record",label="OrigId: 0\n_Z3foov -\> _Z3bazv",tooltip="N[[FOO2]] ContextIds: 2",fillcolor="cyan",style="filled",color="blue",style="filled, bold, dashed"]; // callsite, cold
+; DOTCLONED:     N[[MAIN2:0x[a-z0-9]+]] [shape="record",label="OrigId: 15025054523792398438\nmain -\> _Z3foov",tooltip="N[[MAIN2]] ContextIds: 2",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
+; DOTCLONED:     N[[BAR:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z3barv -\> _Znam",tooltip="N[[BAR]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
+; DOTCLONED:     N[[BAZ:0x[a-z0-9]+]] [shape="record",label="OrigId: 12481870273128938184\n_Z3bazv -\> _Z3barv",tooltip="N[[BAZ]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
+; DOTCLONED:     N[[FOO:0x[a-z0-9]+]] [shape="record",label="OrigId: 2732490490862098848\n_Z3foov -\> _Z3bazv",tooltip="N[[FOO]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
+; DOTCLONED:     N[[MAIN1:0x[a-z0-9]+]] [shape="record",label="OrigId: 8632435727821051414\nmain -\> _Z3foov",tooltip="N[[MAIN1]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
+; DOTCLONED:     // Edges:
+; DOTCLONED:     N[[BAZ2]] -> N[[BAR2]][tooltip=" ContextIds: 2",fillcolor="cyan"]; // cold
+; DOTCLONED:     N[[FOO2]] -> N[[BAZ2]][tooltip=" ContextIds: 2",fillcolor="cyan"]; // cold
+; DOTCLONED:     N[[MAIN2]] -> N[[FOO2]][tooltip=" ContextIds: 2",fillcolor="cyan"]; // cold
+; DOTCLONED:     N[[BAZ]] -> N[[BAR]][tooltip=" ContextIds: 1",fillcolor="brown1"]; // default
+; DOTCLONED:     N[[FOO]] -> N[[BAZ]][tooltip=" ContextIds: 1",fillcolor="brown1"]; // default
+; DOTCLONED:     N[[MAIN1]] -> N[[FOO]][tooltip=" ContextIds: 1",fillcolor="brown1"]; // default
+; DOTCLONED: }

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

 
 ; RUN: opt -passes=pgho-context-disambiguation \
 ; RUN:  -pgho-verify-ccg -pgho-verify-nodes -pgho-dump-ccg \
 ; RUN:  -pgho-export-to-dot -pgho-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
 
 ; ModuleID = 'duplicate-context-ids.ll'
 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"
 
 ; Function Attrs: mustprogress noinline optnone uwtable
 define internal noundef ptr @_Z1Dv() #0 {

 ; 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: 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 [[D2:0x[a-z0-9]+]]
+; DUMP:     %call = call noalias noundef nonnull ptr @_Znam(i64 noundef 10) #6  (clone 0)
+; DUMP:   AllocTypes: Cold
+; DUMP:   ContextIds: 4 1 3
+; 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: 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 [[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:
+
 
 ; DOTPRE: digraph CallsiteContextGraph {
 ; DOTPRE:     N[[D:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z1Dv -\> _Znam",tooltip="N[[D]] ContextIds: 2 1",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
 ; DOTPRE:     N[[F:0x[a-z0-9]+]] [shape="record",label="OrigId: 13543580133643026784\nnull call (external)",tooltip="N[[F]] ContextIds: 2",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
 ; DOTPRE:     N[[C:0x[a-z0-9]+]] [shape="record",label="OrigId: 12176601099670543485\nnull call (external)",tooltip="N[[C]] ContextIds: 1",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
 ; DOTPRE:     // Edges:
 ; DOTPRE:     N[[C]] -> N[[D]][tooltip=" ContextIds: 1",fillcolor="cyan"]; // cold
 ; DOTPRE:     N[[F]] -> N[[D]][tooltip=" ContextIds: 2",fillcolor="brown1"]; // default
 ; DOTPRE: }
 
 
 ; DOTPOST: digraph CallsiteContextGraph {
 ; DOTPOST:     N[[D:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z1Dv -\> _Znam",tooltip="N[[D]] ContextIds: 2 4 1 3",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
 ; DOTPOST:     N[[E:0x[a-z0-9]+]] [shape="record",label="OrigId: 0\n_Z1Ev -\> _Z1Dv",tooltip="N[[E]] ContextIds: 1",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
 ; DOTPOST:     N[[B:0x[a-z0-9]+]] [shape="record",label="OrigId: 0\n_Z1Bv -\> _Z1Dv",tooltip="N[[B]] ContextIds: 4",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
 ; DOTPOST:     N[[C:0x[a-z0-9]+]] [shape="record",label="OrigId: 0\n_Z1Cv -\> _Z1Dv",tooltip="N[[C]] ContextIds: 3",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
 ; DOTPOST:     N[[F:0x[a-z0-9]+]] [shape="record",label="OrigId: 13543580133643026784\n_Z1Fv -\> _Z1Dv",tooltip="N[[F]] ContextIds: 2",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
 ; DOTPOST:     // Edges:
 ; DOTPOST:     N[[F]] -> N[[D]][tooltip=" ContextIds: 2",fillcolor="brown1"]; // default
 ; DOTPOST:     N[[C]] -> N[[D]][tooltip=" ContextIds: 3",fillcolor="cyan"]; // cold
 ; DOTPOST:     N[[B]] -> N[[D]][tooltip=" ContextIds: 4",fillcolor="cyan"]; // cold
 ; DOTPOST:     N[[E]] -> N[[D]][tooltip=" ContextIds: 1",fillcolor="cyan"]; // cold
 ; DOTPOST: }
+
+
+; DOTCLONED: digraph CallsiteContextGraph {
+; DOTCLONED:     N[[D2:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z1Dv -\> _Znam",tooltip="N[[D2]] ContextIds: 4 1 3",fillcolor="cyan",style="filled",color="blue",style="filled, bold, dashed"]; // callsite, cold
+; DOTCLONED:     N[[B:0x[a-z0-9]+]] [shape="record",label="OrigId: 0\n_Z1Bv -\> _Z1Dv",tooltip="N[[B]] ContextIds: 4",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
+; DOTCLONED:     N[[C:0x[a-z0-9]+]] [shape="record",label="OrigId: 0\n_Z1Cv -\> _Z1Dv",tooltip="N[[C]] ContextIds: 3",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
+; DOTCLONED:     N[[E:0x[a-z0-9]+]] [shape="record",label="OrigId: 0\n_Z1Ev -\> _Z1Dv",tooltip="N[[E]] ContextIds: 1",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
+; DOTCLONED:     N[[D:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z1Dv -\> _Znam",tooltip="N[[D]] ContextIds: 2",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
+; DOTCLONED:     N[[F:0x[a-z0-9]+]] [shape="record",label="OrigId: 13543580133643026784\n_Z1Fv -\> _Z1Dv",tooltip="N[[F]] ContextIds: 2",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
+; DOTCLONED:     // Edges:
+; DOTCLONED:     N[[E]] -> N[[D2]][tooltip=" ContextIds: 1",fillcolor="cyan"]; // cold
+; DOTCLONED:     N[[C]] -> N[[D2]][tooltip=" ContextIds: 3",fillcolor="cyan"]; // cold
+; DOTCLONED:     N[[B]] -> N[[D2]][tooltip=" ContextIds: 4",fillcolor="cyan"]; // cold
+; DOTCLONED:     N[[F]] -> N[[D]][tooltip=" ContextIds: 2",fillcolor="brown1"]; // default
+; DOTCLONED: }

llvm/test/Transforms/PGHOContextDisambiguation/indirectcall.ll

 ;; Compiled without optimization to prevent inlining and devirtualization.
 
 ; RUN: opt -passes=pgho-context-disambiguation \
 ; RUN:  -pgho-verify-ccg -pgho-verify-nodes -pgho-dump-ccg \
 ; RUN:  -pgho-export-to-dot -pgho-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
 
 ; ModuleID = 'indirectcall.ll'
 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"
 
 %class.B = type { %class.A }
 %class.A = type { ptr }

 ; 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:0x[a-z0-9]+]]
+; DUMP:     %call = call noalias noundef nonnull ptr @_Znam(i64 noundef 10) #7  (clone 0)
+; DUMP:   AllocTypes: NotColdCold
+; DUMP:   ContextIds: 2 4 1 3 5
+; DUMP:   CalleeEdges:
+; DUMP:   CallerEdges:
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[AX:0x[a-z0-9]+]] AllocTypes: NotColdCold ContextIds: 1 2
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[BX:0x[a-z0-9]+]] AllocTypes: NotColdCold ContextIds: 4 5
+; DUMP:     Edge from Callee [[FOO]] to Caller: [[MAIN1:0x[a-z0-9]+]] AllocTypes: NotCold ContextIds: 3
+
+; DUMP: Node [[AX]]
+; DUMP:     %call = call noundef ptr @_Z3foov() (clone 0)
+; DUMP:   AllocTypes: NotColdCold
+; DUMP:   ContextIds: 2 1
+; 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:0x[a-z0-9]+]] AllocTypes: NotColdCold ContextIds: 1 2
+
+; DUMP: Node [[BAR]]
+; DUMP:   null Call
+; DUMP:   AllocTypes: NotColdCold
+; DUMP:   ContextIds: 2 4 1 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:0x[a-z0-9]+]] AllocTypes: NotCold ContextIds: 1
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN4:0x[a-z0-9]+]] AllocTypes: Cold ContextIds: 2
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN5:0x[a-z0-9]+]] AllocTypes: Cold ContextIds: 4
+; DUMP:     Edge from Callee [[BAR]] to Caller: [[MAIN6:0x[a-z0-9]+]] 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 [[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 [[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 [[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 [[FOO2:0x[a-z0-9]+]]
+; 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:0x[a-z0-9]+]] AllocTypes: Cold ContextIds: 6
+
+; 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:
+
 
 ; DOT: digraph CallsiteContextGraph {
 ; DOT:     N[[FOO:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z3foov -\> _Znam",tooltip="N[[FOO]] ContextIds: 2 4 6 1 3 5",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
 ; DOT:     N[[MAIN1:0x[a-z0-9]+]] [shape="record",label="OrigId: 15025054523792398438\nmain -\> _Z3foov",tooltip="N[[MAIN1]] ContextIds: 6",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
 ; DOT:     N[[BX:0x[a-z0-9]+]] [shape="record",label="OrigId: 13614864978754796978\n_ZN1B1xEv -\> _Z3foov",tooltip="N[[BX]] ContextIds: 4 5",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
 ;; Bar contains an indirect call, with multiple targets. It's call should be null.
 ; DOT:     N[[BAR:0x[a-z0-9]+]] [shape="record",label="OrigId: 13626499562959447861\nnull call (external)",tooltip="N[[BAR]] ContextIds: 2 4 1 5",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
 ; DOT:     N[[MAIN2:0x[a-z0-9]+]] [shape="record",label="OrigId: 15737101490731057601\nmain -\> _Z3barP1A",tooltip="N[[MAIN2]] ContextIds: 5",fillcolor="brown1",style="filled",style="filled"]; // callsite, default

 ; DOT:     N[[MAIN1]] -> N[[FOO]][tooltip=" ContextIds: 6",fillcolor="cyan"]; // cold
 ; DOT:     N[[BAR]] -> N[[BX]][tooltip=" ContextIds: 4 5",fillcolor="mediumorchid1"]; // default|cold
 ; DOT:     N[[MAIN5]] -> N[[BAR]][tooltip=" ContextIds: 1",fillcolor="brown1"]; // default
 ; DOT:     N[[MAIN4]] -> N[[BAR]][tooltip=" ContextIds: 2",fillcolor="cyan"]; // cold
 ; DOT:     N[[MAIN3]] -> N[[BAR]][tooltip=" ContextIds: 4",fillcolor="cyan"]; // cold
 ; DOT:     N[[MAIN2]] -> N[[BAR]][tooltip=" ContextIds: 5",fillcolor="brown1"]; // default
 ; DOT:     N[[BAR]] -> N[[AX]][tooltip=" ContextIds: 1 2",fillcolor="mediumorchid1"]; // default|cold
 ; DOT: }
+
+
+; DOTCLONED: digraph CallsiteContextGraph {
+; DOTCLONED:     N[[FOO2:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z3foov -\> _Znam",tooltip="N[[FOO2]] ContextIds: 6",fillcolor="cyan",style="filled",color="blue",style="filled, bold, dashed"]; // callsite, cold
+; DOTCLONED:     N[[MAIN1:0x[a-z0-9]+]] [shape="record",label="OrigId: 15025054523792398438\nmain -\> _Z3foov",tooltip="N[[MAIN1]] ContextIds: 6",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
+; DOTCLONED:     N[[FOO:0x[a-z0-9]+]] [shape="record",label="OrigId: Alloc0\n_Z3foov -\> _Znam",tooltip="N[[FOO]] ContextIds: 2 4 1 3 5",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
+; DOTCLONED:     N[[MAIN6:0x[a-z0-9]+]] [shape="record",label="OrigId: 8632435727821051414\nmain -\> _Z3foov",tooltip="N[[MAIN6]] ContextIds: 3",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
+; DOTCLONED:     N[[BX:0x[a-z0-9]+]] [shape="record",label="OrigId: 13614864978754796978\n_ZN1B1xEv -\> _Z3foov",tooltip="N[[BX]] ContextIds: 4 5",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
+;; Bar contains an indirect call, with multiple targets. It's call should be null.
+; DOTCLONED:     N[[BAR:0x[a-z0-9]+]] [shape="record",label="OrigId: 13626499562959447861\nnull call (external)",tooltip="N[[BAR]] ContextIds: 2 4 1 5",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
+; DOTCLONED:     N[[MAIN2:0x[a-z0-9]+]] [shape="record",label="OrigId: 15737101490731057601\nmain -\> _Z3barP1A",tooltip="N[[MAIN2]] ContextIds: 5",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
+; DOTCLONED:     N[[MAIN3:0x[a-z0-9]+]] [shape="record",label="OrigId: 6792096022461663180\nmain -\> _Z3barP1A",tooltip="N[[MAIN3]] ContextIds: 4",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
+; DOTCLONED:     N[[MAIN4:0x[a-z0-9]+]] [shape="record",label="OrigId: 12699492813229484831\nmain -\> _Z3barP1A",tooltip="N[[MAIN4]] ContextIds: 2",fillcolor="cyan",style="filled",style="filled"]; // callsite, cold
+; DOTCLONED:     N[[MAIN5:0x[a-z0-9]+]] [shape="record",label="OrigId: 748269490701775343\nmain -\> _Z3barP1A",tooltip="N[[MAIN5]] ContextIds: 1",fillcolor="brown1",style="filled",style="filled"]; // callsite, default
+; DOTCLONED:     N[[AX:0x[a-z0-9]+]] [shape="record",label="OrigId: 8256774051149711748\n_ZN1A1xEv -\> _Z3foov",tooltip="N[[AX]] ContextIds: 2 1",fillcolor="mediumorchid1",style="filled",style="filled"]; // callsite, default|cold
+; DOTCLONED:     // Edges:
+; DOTCLONED:     N[[MAIN1]] -> N[[FOO2]][tooltip=" ContextIds: 6",fillcolor="cyan"]; // cold
+; DOTCLONED:     N[[AX]] -> N[[FOO]][tooltip=" ContextIds: 1 2",fillcolor="mediumorchid1"]; // default|cold
+; DOTCLONED:     N[[BX]] -> N[[FOO]][tooltip=" ContextIds: 4 5",fillcolor="mediumorchid1"]; // default|cold
+; DOTCLONED:     N[[MAIN6]] -> N[[FOO]][tooltip=" ContextIds: 3",fillcolor="brown1"]; // default
+; DOTCLONED:     N[[BAR]] -> N[[BX]][tooltip=" ContextIds: 4 5",fillcolor="mediumorchid1"]; // default|cold
+; DOTCLONED:     N[[MAIN5]] -> N[[BAR]][tooltip=" ContextIds: 1",fillcolor="brown1"]; // default
+; DOTCLONED:     N[[MAIN4]] -> N[[BAR]][tooltip=" ContextIds: 2",fillcolor="cyan"]; // cold
+; DOTCLONED:     N[[MAIN3]] -> N[[BAR]][tooltip=" ContextIds: 4",fillcolor="cyan"]; // cold
+; DOTCLONED:     N[[MAIN2]] -> N[[BAR]][tooltip=" ContextIds: 5",fillcolor="brown1"]; // default
+; DOTCLONED:     N[[BAR]] -> N[[AX]][tooltip=" ContextIds: 1 2",fillcolor="mediumorchid1"]; // default|cold
+; DOTCLONED: }

llvm/test/Transforms/PGHOContextDisambiguation/inlined.ll

 ;; like main -> foo(+baz) -> bar after the inlining reflected in this IR).
 
 ; RUN: opt -passes=pgho-context-disambiguation \
 ; RUN:  -pgho-verify-ccg -pgho-verify-nodes -pgho-dump-ccg \
 ; RUN:  -pgho-export-to-dot -pgho-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
 
 ; ModuleID = 'inlined.ll'
 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"
 
 ; Function Attrs: mustprogress uwtable
 define internal noundef ptr @_Z3barv() #0 {

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