[BOLT] Fixing relative ordering of cold sections under multi-way function splitting

[shatianw_mt]

Summary

Order code sections with names in the form of ".text.cold.i" based on the value of i

[Context] SplitFunctions.cpp implements splitting strategies that can potentially split each function into maximum N>2 fragments.
When such N-way splitting happens, new code sections with names ".text.cold.1", ..., ".text.cold.i", ... "text.cold.N-2" will be created
A section with name ".text.cold.i" contains the the (i+2)th fragment of each function.
As an example, if each function is splitted into N=3 fragments: hot, warm, cold, then code sections will now include

• a section with name ".text" containing hot fragments
• a section with name ".text.cold" containing warm fragments
• a section with name ".text.cold.1" containing cold fragments

The order of these new sections in the output binary currently depends on the order in which they are encountered by the emitter.
For example, under N=3-way splitting, if the first function is 2-way splitted into hot and cold and the second function is 3-way splitted into hot, warm, and cold
then the cold fragment is encountered first, resulting in the final section to be in the following order
.text (hot), .text.cold.1 (cold), .text.cold (warm)

The above is suboptimal because the distance of jumps/calls between the hot and the warm sections will be much bigger than when ordering the sections as follows
.text (hot), .text.cold (warm), .text.cold.1 (cold)

This diff orders the sections with names in the form of ".text.cold" or ".text.cold.i" based on the value of i (assuming the i-value of ".text.cold" is 0).

[shatianw_mt]

Remove unnecessary print statements...

[shatianw_mt]

ran git clang-format

[rafauler]

LGTM

[shatianw_mt]

Added missing {} for the outer if statement. Without it we get undesirable behavior such as mover section being placed after text sections. Thanks rafauler for catching this.

bolt/lib/Rewrite/RewriteInstance.cpp

 
 std::vector<BinarySection *> RewriteInstance::getCodeSections() {
   std::vector<BinarySection *> CodeSections;
   for (BinarySection &Section : BC->textSections())
     if (Section.hasValidSectionID())
       CodeSections.emplace_back(&Section);
 
   auto compareSections = [&](const BinarySection *A, const BinarySection *B) {
+
+    // If both A and B have names starting with ".text.cold", then
+    // - if opts::HotFunctionsAtEnd is true, we want order
+    //   ".text.cold.T", ".text.cold.T-1", ... ".text.cold.1", ".text.cold"
+    // - if opts::HotFunctionsAtEnd is false, we want order
+    //   ".text.cold", ".text.cold.1", ... ".text.cold.T-1", ".text.cold.T"
+    if (A->getName().startswith(BC->getColdCodeSectionName()) &&
+        B->getName().startswith(BC->getColdCodeSectionName()))
+      if (A->getName().size() != B->getName().size())
+        return (opts::HotFunctionsAtEnd)
+                   ? (A->getName().size() > B->getName().size())
+                   : (A->getName().size() < B->getName().size());
+    return (opts::HotFunctionsAtEnd) ? (A->getName() > B->getName())
+                                     : (A->getName() < B->getName());
+
     // Place movers before anything else.
     if (A->getName() == BC->getHotTextMoverSectionName())
       return true;
     if (B->getName() == BC->getHotTextMoverSectionName())
       return false;
 
     // Depending on the option, put main text at the beginning or at the end.
     if (opts::HotFunctionsAtEnd)
       return B->getName() == BC->getMainCodeSectionName();
     else
       return A->getName() == BC->getMainCodeSectionName();
   };
 
   // Determine the order of sections.
   llvm::stable_sort(CodeSections, compareSections);
+  for (BinarySection *Section : CodeSections) {
+    outs() << "Shatian DDebug: " << Section->getName() << '\n';
+  }
 
   return CodeSections;
 }
 
 void RewriteInstance::mapCodeSections(RuntimeDyld &RTDyld) {
   if (BC->HasRelocations) {
     // Map sections for functions with pre-assigned addresses.
     for (BinaryFunction *InjectedFunction : BC->getInjectedBinaryFunctions()) {