[BasicBlockSections] Introduce the path cloning profile format to BasicBlockSectionsProfileReader.

[rahmanl]

Summary

Following up on prior RFC (https://lists.llvm.org/pipermail/llvm-dev/2020-September/145357.html) we can now improve above our highly-optimized basic-block-sections binary (e.g., 2% for clang) by applying path cloning. Cloning can improve performance by reducing taken branches.

This patch prepares the profile format for applying cloning actions.

The basic block cloning profile format extends the basic block sections profile in two ways.

1. Specifies the cloning paths with a !!! prefix. For example, !!!1 4 5 specifies that blocks with BB ids 4 and 5 must be cloned along the edge 1 --> 4.
2. For each cloned block, it will appear in the cluster info as <bb_id>.<clone_id> where clone_id is the id associated with this clone.

For example, the following profile specifies one cloned block (2) and determines its cluster position as well.

!foo
!!!1 2
!!0 1 2.1 3 2 5

This patch keeps backward-compatibility (retains the behavior for old profile format).

[rahmanl]

Add BasicBlockSections.cpp changes.

[rahmanl]

nit.

[rahmanl]

fixes.

[rahmanl]

clang-format.

[rahmanl]

nit.

[rahmanl]

Add the cloning profile format to the function comment.

[tmsriram]

The description requires more details. Please point to any prior discussions on cloning and its performance potential. Can you explain in some more detail how this syntax is powerful enough to capture a general cloning operation?

Rather than just use "number of !s", can we try to change the grammar? How about a character to specify the action type, 'c' for cloning?

llvm/include/llvm/CodeGen/BasicBlockSectionsProfileReader.h

 #include "llvm/Pass.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/LineIterator.h"
 #include "llvm/Support/MemoryBuffer.h"
 using namespace llvm;
 
 namespace llvm {
 
-// The cluster information for a machine basic block.
-struct BBClusterInfo {
-  // Unique ID for this basic block.
+// This structure represents a unique ID for every block specified in the
+// profile.
+struct ProfileBBID {
   unsigned BBID;
+  unsigned CloneID;
+};
+
+// Provides DenseMapInfo for ProfileBBID.
+template <> struct DenseMapInfo<ProfileBBID> {
+  static inline ProfileBBID getEmptyKey() {
+    unsigned EmptyKey = DenseMapInfo<unsigned>::getEmptyKey();
+    return ProfileBBID{EmptyKey, EmptyKey};
+  }
+  static inline ProfileBBID getTombstoneKey() {
+    unsigned TombstoneKey = DenseMapInfo<unsigned>::getTombstoneKey();
+    return ProfileBBID{TombstoneKey, TombstoneKey};
+  }
+  static unsigned getHashValue(const ProfileBBID &Val) {
+    std::pair<unsigned, unsigned> PairVal =
+        std::make_pair(Val.BBID, Val.CloneID);
+    return DenseMapInfo<std::pair<unsigned, unsigned>>::getHashValue(PairVal);
+  }
+  static bool isEqual(const ProfileBBID &LHS, const ProfileBBID &RHS) {
+    return DenseMapInfo<unsigned>::isEqual(LHS.BBID, RHS.BBID) &&
+           DenseMapInfo<unsigned>::isEqual(LHS.CloneID, RHS.CloneID);
+  }
+};
+
+// This struct represents the cluster information for a machine basic block,
+// which is specifed by a unique ID.
+template <typename BBIDType> struct BBProfile {
+  // Basic block ID.
+  BBIDType BasicBlockID;
   // Cluster ID this basic block belongs to.
   unsigned ClusterID;
   // Position of basic block within the cluster.
   unsigned PositionInCluster;
 };
 
-using ProgramBBClusterInfoMapTy = StringMap<SmallVector<BBClusterInfo>>;
+// This represents the profile for one function.
+struct RawFunctionProfile {
+  // BB Cluster information specified by `ProfileBBID`s (before cloning).
+  SmallVector<BBProfile<ProfileBBID>> RawBBProfiles;
+  // Paths to clone. A path a -> b -> c -> d implies cloning b, c, and d along
+  // the edge a -> b.
+  SmallVector<SmallVector<unsigned>> ClonePaths;
+};
 
 class BasicBlockSectionsProfileReader : public ImmutablePass {
 public:
   static char ID;
 
   BasicBlockSectionsProfileReader(const MemoryBuffer *Buf)
-      : ImmutablePass(ID), MBuf(Buf) {
+      : ImmutablePass(ID), MBuf(Buf),
+        LineIt(*Buf, /*SkipBlanks=*/true, /*CommentMarker=*/'#') {
     initializeBasicBlockSectionsProfileReaderPass(
         *PassRegistry::getPassRegistry());
   };
 
   BasicBlockSectionsProfileReader() : ImmutablePass(ID) {
     initializeBasicBlockSectionsProfileReaderPass(
         *PassRegistry::getPassRegistry());
   }
 
   StringRef getPassName() const override {
     return "Basic Block Sections Profile Reader";
   }
 
   // Returns true if basic block sections profile exist for function \p
   // FuncName.
   bool isFunctionHot(StringRef FuncName) const;
 
   // Returns a pair with first element representing whether basic block sections
   // profile exist for the function \p FuncName, and the second element
   // representing the basic block sections profile (cluster info) for this
   // function. If the first element is true and the second element is empty, it
   // means unique basic block sections are desired for all basic blocks of the
   // function.
-  std::pair<bool, SmallVector<BBClusterInfo>>
-  getBBClusterInfoForFunction(StringRef FuncName) const;
+  std::pair<bool, RawFunctionProfile>
+  getRawProfileForFunction(StringRef FuncName) const;
 
   // Initializes the FunctionNameToDIFilename map for the current module and
   // then reads the profile for matching functions.
   bool doInitialization(Module &M) override;
 
 private:
   StringRef getAliasName(StringRef FuncName) const {
     auto R = FuncAliasMap.find(FuncName);
     return R == FuncAliasMap.end() ? FuncName : R->second;
   }
 
+  // Returns a profile parsing error for the current line.
+  Error createProfileParseError(Twine Message) const {
+    return make_error<StringError>(
+        Twine("invalid profile " + MBuf->getBufferIdentifier() + " at line " +
+              Twine(LineIt.line_number()) + ": " + Message),
+        inconvertibleErrorCode());
+  };
+
+  // Parses a `ProfileBBID` from `S`.
+  Expected<ProfileBBID> parseProfileBBID(StringRef S) const;
+
   // Reads the basic block sections profile for functions in this module.
   Error ReadProfile();
 
   // This contains the basic-block-sections profile.
   const MemoryBuffer *MBuf = nullptr;
 
+  // Iterator to the line being parsed.
+  line_iterator LineIt;
+
   // Map from every function name in the module to its debug info filename or
   // empty string if no debug info is available.
   StringMap<SmallString<128>> FunctionNameToDIFilename;
 
   // This encapsulates the BB cluster information for the whole program.
   //
-  // For every function name, it contains the cluster information for (all or
-  // some of) its basic blocks. The cluster information for every basic block
-  // includes its cluster ID along with the position of the basic block in that
-  // cluster.
-  ProgramBBClusterInfoMapTy ProgramBBClusterInfo;
+  // For every function name, it contains the cloning and cluster information
+  // for (all or some of) its basic blocks. The cluster information for every
+  // basic block includes its cluster ID along with the position of the basic
+  // block in that cluster.
+  StringMap<RawFunctionProfile> RawProgramProfile;
 
   // Some functions have alias names. We use this map to find the main alias
   // name for which we have mapping in ProgramBBClusterInfo.
   StringMap<StringRef> FuncAliasMap;
 };
 
 // Creates a BasicBlockSectionsProfileReader pass to parse the basic block
 // sections profile. \p Buf is a memory buffer that contains the list of
 // functions and basic block ids to selectively enable basic block sections.
 ImmutablePass *
 createBasicBlockSectionsProfileReaderPass(const MemoryBuffer *Buf);
 
 } // namespace llvm
 #endif // LLVM_CODEGEN_BASICBLOCKSECTIONSPROFILEREADER_H

llvm/lib/CodeGen/BasicBlockSections.cpp

for (auto &MBB : MF) {
     Cond.clear();
     MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For analyzeBranch.
     if (TII->analyzeBranch(MBB, TBB, FBB, Cond))
       continue;
     MBB.updateTerminator(FTMBB);
   }
 }
 
-// This function provides the BBCluster information associated with a function.
-// Returns true if a valid association exists and false otherwise.
-bool getBBClusterInfoForFunction(
-    const MachineFunction &MF,
-    BasicBlockSectionsProfileReader *BBSectionsProfileReader,
-    DenseMap<unsigned, BBClusterInfo> &V) {
-
-  // Find the assoicated cluster information.
-  std::pair<bool, SmallVector<BBClusterInfo, 4>> P =
-      BBSectionsProfileReader->getBBClusterInfoForFunction(MF.getName());
-  if (!P.first)
-    return false;
-
-  if (P.second.empty()) {
-    // This indicates that sections are desired for all basic blocks of this
-    // function. We clear the BBClusterInfo vector to denote this.
-    V.clear();
-    return true;
-  }
-
-  for (const BBClusterInfo &BBCI : P.second)
-    V[BBCI.BBID] = BBCI;
-  return true;
-}
-
 // This function sorts basic blocks according to the cluster's information.
 // All explicitly specified clusters of basic blocks will be ordered
 // accordingly. All non-specified BBs go into a separate "Cold" section.
 // Additionally, if exception handling landing pads end up in more than one
 // clusters, they are moved into a single "Exception" section. Eventually,
 // clusters are ordered in increasing order of their IDs, with the "Exception"
 // and "Cold" succeeding all other clusters.
-// FuncBBClusterInfo represent the cluster information for basic blocks. It
+// BBProfilesByBBID represents the cluster information for basic blocks. It
 // maps from BBID of basic blocks to their cluster information. If this is
 // empty, it means unique sections for all basic blocks in the function.
-static void
-assignSections(MachineFunction &MF,
-               const DenseMap<unsigned, BBClusterInfo> &FuncBBClusterInfo) {
+static void assignSections(
+    MachineFunction &MF,
+    const DenseMap<unsigned, BBProfile<unsigned>> &BBProfilesByBBID) {
   assert(MF.hasBBSections() && "BB Sections is not set for function.");
   // This variable stores the section ID of the cluster containing eh_pads (if
   // all eh_pads are one cluster). If more than one cluster contain eh_pads, we
   // set it equal to ExceptionSectionID.
   std::optional<MBBSectionID> EHPadsSectionID;
 
   for (auto &MBB : MF) {
     // With the 'all' option, every basic block is placed in a unique section.
     // With the 'list' option, every basic block is placed in a section
     // associated with its cluster, unless we want individual unique sections
-    // for every basic block in this function (if FuncBBClusterInfo is empty).
+    // for every basic block in this function (if BBProfilesByBBID is empty).
     if (MF.getTarget().getBBSectionsType() == llvm::BasicBlockSection::All ||
-        FuncBBClusterInfo.empty()) {
+        BBProfilesByBBID.empty()) {
       // If unique sections are desired for all basic blocks of the function, we
       // set every basic block's section ID equal to its original position in
       // the layout (which is equal to its number). This ensures that basic
       // blocks are ordered canonically.
       MBB.setSectionID(MBB.getNumber());
     } else {
-      auto I = FuncBBClusterInfo.find(*MBB.getBBID());
-      if (I != FuncBBClusterInfo.end()) {
+      auto I = BBProfilesByBBID.find(*MBB.getBBID());
+      if (I != BBProfilesByBBID.end()) {
         MBB.setSectionID(I->second.ClusterID);
       } else {
         // BB goes into the special cold section if it is not specified in the
         // cluster info map.
         MBB.setSectionID(MBBSectionID::ColdSectionID);
       }
     }
 
bool BasicBlockSections::runOnMachineFunction(MachineFunction &MF) {
   // original layout positions and finding the original fallthroughs.
   MF.RenumberBlocks();
 
   if (BBSectionsType == BasicBlockSection::Labels) {
     MF.setBBSectionsType(BBSectionsType);
     return true;
   }
 
-  BBSectionsProfileReader = &getAnalysis<BasicBlockSectionsProfileReader>();
-
-  // Map from BBID of blocks to their cluster information.
-  DenseMap<unsigned, BBClusterInfo> FuncBBClusterInfo;
-  if (BBSectionsType == BasicBlockSection::List &&
-      !getBBClusterInfoForFunction(MF, BBSectionsProfileReader,
-                                   FuncBBClusterInfo))
+  DenseMap<unsigned, BBProfile<unsigned>> BBProfilesByBBID;
+  if (BBSectionsType == BasicBlockSection::List) {
+    auto [HasProfile, RawProfile] =
+        getAnalysis<BasicBlockSectionsProfileReader>().getRawProfileForFunction(
+            MF.getName());
+    if (!HasProfile)
       return true;
+    // TODO: Apply the path cloning profile.
+    for (const BBProfile<ProfileBBID> &BBP : RawProfile.RawBBProfiles) {
+      assert(!BBP.BasicBlockID.CloneID && "Path cloning is not supported yet.");
+      BBProfilesByBBID.try_emplace(BBP.BasicBlockID.BBID,
+                                   BBProfile<unsigned>{BBP.BasicBlockID.BBID,
+                                                       BBP.ClusterID,
+                                                       BBP.PositionInCluster});
+    }
+  }
+
   MF.setBBSectionsType(BBSectionsType);
-  assignSections(MF, FuncBBClusterInfo);
+  assignSections(MF, BBProfilesByBBID);
 
   // We make sure that the cluster including the entry basic block precedes all
   // other clusters.
   auto EntryBBSectionID = MF.front().getSectionID();
 
   // Helper function for ordering BB sections as follows:
   //   * Entry section (section including the entry block).
   //   * Regular sections (in increasing order of their Number).
auto Comparator = [&](const MachineBasicBlock &X,
                         const MachineBasicBlock &Y) {
     auto XSectionID = X.getSectionID();
     auto YSectionID = Y.getSectionID();
     if (XSectionID != YSectionID)
       return MBBSectionOrder(XSectionID, YSectionID);
     // If the two basic block are in the same section, the order is decided by
     // their position within the section.
     if (XSectionID.Type == MBBSectionID::SectionType::Default)
-      return FuncBBClusterInfo.lookup(*X.getBBID()).PositionInCluster <
-             FuncBBClusterInfo.lookup(*Y.getBBID()).PositionInCluster;
+      return BBProfilesByBBID.lookup(*X.getBBID()).PositionInCluster <
+             BBProfilesByBBID.lookup(*Y.getBBID()).PositionInCluster;
     return X.getNumber() < Y.getNumber();
   };
 
   sortBasicBlocksAndUpdateBranches(MF, Comparator);
   avoidZeroOffsetLandingPad(MF);
   return true;
 }
 

llvm/lib/CodeGen/BasicBlockSectionsProfileReader.cpp

 //===-- BasicBlockSectionsProfileReader.cpp -------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Implementation of the basic block sections profile reader pass. It parses
 // and stores the basic block sections profile file (which is specified via the
 // `-basic-block-sections` flag).
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/BasicBlockSectionsProfileReader.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/LineIterator.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include <llvm/ADT/STLExtras.h>
 
 using namespace llvm;
 
 char BasicBlockSectionsProfileReader::ID = 0;
 INITIALIZE_PASS(BasicBlockSectionsProfileReader, "bbsections-profile-reader",
                 "Reads and parses a basic block sections profile.", false,
                 false)
 
+Expected<ProfileBBID>
+BasicBlockSectionsProfileReader::parseProfileBBID(StringRef S) const {
+  SmallVector<StringRef, 2> Parts;
+  S.split(Parts, '.');
+  if (Parts.size() > 2)
+    return createProfileParseError(Twine("unable to parse basic block id: '") +
+                                   S + "'");
+  unsigned long long BBID;
+  if (getAsUnsignedInteger(Parts[0], 10, BBID))
+    return createProfileParseError(
+        Twine("unable to parse BB id: '" + Parts[0]) +
+        "': unsigned integer expected");
+  unsigned long long CloneID = 0;
+  if (Parts.size() > 1 && getAsUnsignedInteger(Parts[1], 10, CloneID))
+    return createProfileParseError(Twine("unable to parse clone id: '") +
+                                   Parts[1] + "': unsigned integer expected");
+  return ProfileBBID{static_cast<unsigned>(BBID),
+                     static_cast<unsigned>(CloneID)};
+}
+
 bool BasicBlockSectionsProfileReader::isFunctionHot(StringRef FuncName) const {
-  return getBBClusterInfoForFunction(FuncName).first;
+  return getRawProfileForFunction(FuncName).first;
 }
 
-std::pair<bool, SmallVector<BBClusterInfo>>
-BasicBlockSectionsProfileReader::getBBClusterInfoForFunction(
+std::pair<bool, RawFunctionProfile>
+BasicBlockSectionsProfileReader::getRawProfileForFunction(
     StringRef FuncName) const {
-  auto R = ProgramBBClusterInfo.find(getAliasName(FuncName));
-  return R != ProgramBBClusterInfo.end()
-             ? std::pair(true, R->second)
-             : std::pair(false, SmallVector<BBClusterInfo>{});
+  auto R = RawProgramProfile.find(getAliasName(FuncName));
+  return R != RawProgramProfile.end() ? std::pair(true, R->second)
+                                      : std::pair(false, RawFunctionProfile());
 }
 
 // Basic Block Sections can be enabled for a subset of machine basic blocks.
 // This is done by passing a file containing names of functions for which basic
-// block sections are desired.  Additionally, machine basic block ids of the
+// block sections are desired. Additionally, machine basic block ids of the
 // functions can also be specified for a finer granularity. Moreover, a cluster
 // of basic blocks could be assigned to the same section.
 // Optionally, a debug-info filename can be specified for each function to allow
 // distinguishing internal-linkage functions of the same name.
+// This profile can also specify cloning paths which instruct the compiler to
+// clone basic blocks along a path. The cloned blocks are then specified in the
+// cluster information.
 // A file with basic block sections for all of function main and three blocks
 // for function foo (of which 1 and 2 are placed in a cluster) looks like this:
 // (Profile for function foo is only loaded when its debug-info filename
 // matches 'path/to/foo_file.cc').
 // ----------------------------
 // list.txt:
 // !main
 // !foo M=path/to/foo_file.cc
 // !!1 2
 // !!4
+// The following profile lists two cloning paths (prefixed by !!!) for function
+// bar and places the total 11 blocks within two clusters. Each cloned block is
+// identified by its original block id, along with its clone id. A block cloned
+// multiple times (2 in this example) appears with distinct clone ids (2.1
+// and 2.2).
+// ---------------------------
+// !main
+// !bar
+// !!!1 2 3
+// !!!4 2 5
+// !!2 3 5 6 7
+// !!1 2.1 3.1 4 2.2 5.1
 Error BasicBlockSectionsProfileReader::ReadProfile() {
   assert(MBuf);
-  line_iterator LineIt(*MBuf, /*SkipBlanks=*/true, /*CommentMarker=*/'#');
 
-  auto invalidProfileError = [&](auto Message) {
-    return make_error<StringError>(
-        Twine("Invalid profile " + MBuf->getBufferIdentifier() + " at line " +
-              Twine(LineIt.line_number()) + ": " + Message),
-        inconvertibleErrorCode());
-  };
-
-  auto FI = ProgramBBClusterInfo.end();
+  auto FI = RawProgramProfile.end();
 
   // Current cluster ID corresponding to this function.
   unsigned CurrentCluster = 0;
   // Current position in the current cluster.
   unsigned CurrentPosition = 0;
 
   // Temporary set to ensure every basic block ID appears once in the clusters
   // of a function.
-  SmallSet<unsigned, 4> FuncBBIDs;
+  DenseSet<ProfileBBID> FuncBasicBlockIDs;
 
   for (; !LineIt.is_at_eof(); ++LineIt) {
     StringRef S(*LineIt);
     if (S[0] == '@')
       continue;
     // Check for the leading "!"
     if (!S.consume_front("!") || S.empty())
       break;
-    // Check for second "!" which indicates a cluster of basic blocks.
-    if (S.consume_front("!")) {
-      // Skip the profile when we the profile iterator (FI) refers to the
-      // past-the-end element.
-      if (FI == ProgramBBClusterInfo.end())
-        continue;
-      SmallVector<StringRef, 4> BBIDs;
-      S.split(BBIDs, ' ');
-      // Reset current cluster position.
-      CurrentPosition = 0;
-      for (auto BBIDStr : BBIDs) {
-        unsigned long long BBID;
-        if (getAsUnsignedInteger(BBIDStr, 10, BBID))
-          return invalidProfileError(Twine("Unsigned integer expected: '") +
-                                     BBIDStr + "'.");
-        if (!FuncBBIDs.insert(BBID).second)
-          return invalidProfileError(Twine("Duplicate basic block id found '") +
-                                     BBIDStr + "'.");
-        if (BBID == 0 && CurrentPosition)
-          return invalidProfileError("Entry BB (0) does not begin a cluster.");
 
-        FI->second.emplace_back(
-            BBClusterInfo{((unsigned)BBID), CurrentCluster, CurrentPosition++});
-      }
-      CurrentCluster++;
-    } else {
-      // This is a function name specifier. It may include a debug info filename
-      // specifier starting with `M=`.
+    // Check for the second "!" which indicates a cluster of basic blocks.
+    if (!S.consume_front("!")) {
+      // A single "!" represents a function name specifier.
+      // It may include a debug info filename specifier starting with `M=`.
       auto [AliasesStr, DIFilenameStr] = S.split(' ');
       SmallString<128> DIFilename;
       if (DIFilenameStr.startswith("M=")) {
         DIFilename =
             sys::path::remove_leading_dotslash(DIFilenameStr.substr(2));
         if (DIFilename.empty())
-          return invalidProfileError("Empty module name specifier.");
+          return createProfileParseError("empty module name specifier");
       } else if (!DIFilenameStr.empty()) {
-        return invalidProfileError("Unknown string found: '" + DIFilenameStr +
-                                   "'.");
+        return createProfileParseError("unknown string found: '" +
+                                       DIFilenameStr + "'");
       }
       // Function aliases are separated using '/'. We use the first function
       // name for the cluster info mapping and delegate all other aliases to
       // this one.
       SmallVector<StringRef, 4> Aliases;
       AliasesStr.split(Aliases, '/');
       bool FunctionFound = any_of(Aliases, [&](StringRef Alias) {
         auto It = FunctionNameToDIFilename.find(Alias);
         // No match if this function name is not found in this module.
         if (It == FunctionNameToDIFilename.end())
           return false;
         // Return a match if debug-info-filename is not specified. Otherwise,
         // check for equality.
         return DIFilename.empty() || It->second.equals(DIFilename);
       });
       if (!FunctionFound) {
         // Skip the following profile by setting the profile iterator (FI) to
         // the past-the-end element.
-        FI = ProgramBBClusterInfo.end();
+        FI = RawProgramProfile.end();
         continue;
       }
       for (size_t i = 1; i < Aliases.size(); ++i)
         FuncAliasMap.try_emplace(Aliases[i], Aliases.front());
 
       // Prepare for parsing clusters of this function name.
       // Start a new cluster map for this function name.
-      auto R = ProgramBBClusterInfo.try_emplace(Aliases.front());
+      auto R = RawProgramProfile.try_emplace(Aliases.front());
       // Report error when multiple profiles have been specified for the same
       // function.
       if (!R.second)
-        return invalidProfileError("Duplicate profile for function '" +
-                                   Aliases.front() + "'.");
+        return createProfileParseError("duplicate profile for function '" +
+                                       Aliases.front() + "'");
       FI = R.first;
       CurrentCluster = 0;
-      FuncBBIDs.clear();
+      FuncBasicBlockIDs.clear();
+      continue;
+    }
+    // Skip the profile when the profile iterator (FI) refers to the
+    // past-the-end element.
+    if (FI == RawProgramProfile.end())
+      continue;
+
+    // Check for the third "!" which indicates a clone path.
+    if (!S.consume_front("!")) {
+      // Two "!"s represent a cluster of basic blocks.
+      SmallVector<StringRef, 4> BasicBlockIDs;
+      S.split(BasicBlockIDs, ' ');
+      // Reset current cluster position.
+      CurrentPosition = 0;
+      for (auto BasicBlockIDStr : BasicBlockIDs) {
+        auto BasicBlockID = parseProfileBBID(BasicBlockIDStr);
+        if (!BasicBlockID)
+          return BasicBlockID.takeError();
+        if (!FuncBasicBlockIDs.insert(*BasicBlockID).second)
+          return createProfileParseError(
+              Twine("duplicate basic block id found '") + BasicBlockIDStr +
+              "'");
+
+        if (!BasicBlockID->BBID && CurrentPosition)
+          return createProfileParseError(
+              "entry BB (0) does not begin a cluster.");
+
+        FI->second.RawBBProfiles.emplace_back(BBProfile<ProfileBBID>{
+            *std::move(BasicBlockID), CurrentCluster, CurrentPosition++});
+      }
+      CurrentCluster++;
+      continue;
+    }
+
+    // Three "!"s Represent a clone path.
+    FI->second.ClonePaths.push_back({});
+    SmallVector<StringRef, 5> ClonePath;
+    S.split(ClonePath, ' ');
+    SmallSet<unsigned, 5> BBsInPath;
+
+    for (size_t I = 0; I < ClonePath.size(); ++I) {
+      auto BBIDStr = ClonePath[I];
+      unsigned long long BBID = 0;
+      if (getAsUnsignedInteger(BBIDStr, 10, BBID))
+        return createProfileParseError(Twine("unsigned integer expected: '") +
+                                       BBIDStr + "'");
+      if (I != 0 && !BBsInPath.insert(BBID).second)
+        return createProfileParseError(
+            Twine("duplicate cloned block in path: '") + BBIDStr + "'");
+      FI->second.ClonePaths.back().push_back(BBID);
     }
   }
   return Error::success();
 }
 
 bool BasicBlockSectionsProfileReader::doInitialization(Module &M) {
   if (!MBuf)
     return false;

llvm/test/CodeGen/X86/basic-block-sections-clusters-error.ll

 ; BB cluster sections error handling
 ; RUN: echo '!dummy1' > %t1
 ; RUN: echo '!!1 4' >> %t1
 ; RUN: echo '!!1' >> %t1
 ; RUN: not --crash llc < %s -O0 -mtriple=x86_64-pc-linux -function-sections -basic-block-sections=%t1 2>&1 | FileCheck %s --check-prefix=CHECK-ERROR1
-; CHECK-ERROR1: LLVM ERROR: Invalid profile {{.*}} at line 3: Duplicate basic block id found '1'.
+; CHECK-ERROR1: LLVM ERROR: invalid profile {{.*}} at line 3: duplicate basic block id found '1'
 ; RUN: echo '!dummy1' > %t2
 ; RUN: echo '!!4 0' >> %t2
 ; RUN: not --crash llc < %s -O0 -mtriple=x86_64-pc-linux -function-sections -basic-block-sections=%t2 2>&1 | FileCheck %s --check-prefix=CHECK-ERROR2
-; CHECK-ERROR2: LLVM ERROR: Invalid profile {{.*}} at line 2: Entry BB (0) does not begin a cluster.
+; CHECK-ERROR2: LLVM ERROR: invalid profile {{.*}} at line 2: entry BB (0) does not begin a cluster
 ; RUN: echo '!dummy1' > %t3
 ; RUN: echo '!!-1' >> %t3
 ; RUN: not --crash llc < %s -O0 -mtriple=x86_64-pc-linux -function-sections -basic-block-sections=%t3 2>&1 | FileCheck %s --check-prefix=CHECK-ERROR3
-; CHECK-ERROR3: LLVM ERROR: Invalid profile {{.*}} at line 2: Unsigned integer expected: '-1'.
+; CHECK-ERROR3: LLVM ERROR: invalid profile {{.*}} at line 2: unable to parse BB id: '-1': unsigned integer expected
 ; RUN: echo '!dummy1 /path/to/filename' > %t4
 ; RUN: not --crash llc < %s -O0 -mtriple=x86_64 -function-sections -basic-block-sections=%t4 2>&1 | FileCheck %s --check-prefix=CHECK-ERROR4
-; CHECK-ERROR4: LLVM ERROR: Invalid profile {{.*}} at line 1: Unknown string found: '/path/to/filename'.
+; CHECK-ERROR4: LLVM ERROR: invalid profile {{.*}} at line 1: unknown string found: '/path/to/filename'
 ; RUN: echo '!dummy2 M=test_dir/test_file' > %t5
 ; RUN: echo '!dummy2 M=test_dir/test_file' >> %t5
 ; RUN: not --crash llc < %s -O0 -mtriple=x86_64 -function-sections -basic-block-sections=%t5 2>&1 | FileCheck %s --check-prefix=CHECK-ERROR5
-; CHECK-ERROR5: LLVM ERROR: Invalid profile {{.*}} at line 2: Duplicate profile for function 'dummy2'.
-; RUN: echo '!dummy1 M=' >> %t6
+; CHECK-ERROR5: LLVM ERROR: invalid profile {{.*}} at line 2: duplicate profile for function 'dummy2'
+; RUN: echo '!dummy1 M=' > %t6
 ; RUN: not --crash llc < %s -O0 -mtriple=x86_64 -function-sections -basic-block-sections=%t6 2>&1 | FileCheck %s --check-prefix=CHECK-ERROR6
-; CHECK-ERROR6: LLVM ERROR: Invalid profile {{.*}} at line 1: Empty module name specifier.
+; CHECK-ERROR6: LLVM ERROR: invalid profile {{.*}} at line 1: empty module name specifier
+; RUN: echo '!dummy1' > %t7
+; RUN: echo '!!0 1.1.1' >> %t7
+; RUN: not --crash llc < %s -O0 -mtriple=x86_64 -function-sections -basic-block-sections=%t7 2>&1 | FileCheck %s --check-prefix=CHECK-ERROR7
+; CHECK-ERROR7: LLVM ERROR: invalid profile {{.*}} at line 2: unable to parse basic block id: '1.1.1'
+; RUN: echo '!dummy1' > %t8
+; RUN: echo '!!0 1.a' >> %t8
+; RUN: not --crash llc < %s -O0 -mtriple=x86_64 -function-sections -basic-block-sections=%t8 2>&1 | FileCheck %s --check-prefix=CHECK-ERROR8
+; CHECK-ERROR8: LLVM ERROR: invalid profile {{.*}} at line 2: unable to parse clone id: 'a' 
+; RUN: echo '!dummy1' > %t9
+; RUN: echo '!!0 1' >> %t9
+; RUN: echo '!!!1 2.1' >> %t9
+; RUN: not --crash llc < %s -O0 -mtriple=x86_64 -function-sections -basic-block-sections=%t9 2>&1 | FileCheck %s --check-prefix=CHECK-ERROR9
+; CHECK-ERROR9: LLVM ERROR: invalid profile {{.*}} at line 3: unsigned integer expected: '2.1'
+; RUN: echo '!dummy1' > %t10
+; RUN: echo '!!0 1' >> %t10
+; RUN: echo '!!!1 2 3 2' >> %t10
+; RUN: not --crash llc < %s -O0 -mtriple=x86_64 -function-sections -basic-block-sections=%t10 2>&1 | FileCheck %s --check-prefix=CHECK-ERROR10
+; CHECK-ERROR10: LLVM ERROR: invalid profile {{.*}} at line 3: duplicate cloned block in path: '2'
 
 define i32 @dummy1(i32 %x, i32 %y, i32 %z) {
   entry:
     %tmp = mul i32 %x, %y
     %tmp2 = add i32 %tmp, %z
     ret i32 %tmp2
 }