[BOLT] Use LTO fuzzy name matching in function-order

[Amir]

Summary

Allow partial name matching wrt LTO suffixes in function-order
user-supplied function list, the same as permitted by profile matching.

[Amir]

Augment the list of functions to process with those that match common LTO
prefix of -function-order functions.

[Amir]

Add test

[rafauler]

LGTM

bolt/lib/Passes/ReorderFunctions.cpp

 //===- bolt/Passes/ReorderFunctions.cpp - Function reordering pass --------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements ReorderFunctions class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "bolt/Passes/ReorderFunctions.h"
 #include "bolt/Passes/HFSort.h"
+#include "bolt/Utils/Utils.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/CommandLine.h"
 #include <fstream>
 
 #define DEBUG_TYPE "hfsort"
 
 using namespace llvm;
 
 namespace opts {
case RT_PETTIS_HANSEN:
     Clusters = pettisAndHansen(Cg);
     break;
   case RT_RANDOM:
     std::srand(opts::RandomSeed);
     Clusters = randomClusters(Cg);
     break;
   case RT_USER:
     {
+      // Build LTOCommonNameMap
+      StringMap<std::vector<uint64_t>> LTOCommonNameMap;
+      for (const BinaryFunction &BF : llvm::make_second_range(BFs))
+        for (StringRef Name : BF.getNames())
+          if (std::optional<StringRef> LTOCommonName = getLTOCommonName(Name))
+            LTOCommonNameMap[*LTOCommonName].push_back(BF.getAddress());
+
       uint32_t Index = 0;
       uint32_t InvalidEntries = 0;
       for (const std::string &Function : readFunctionOrderFile()) {
         std::vector<uint64_t> FuncAddrs;
 
         BinaryData *BD = BC.getBinaryDataByName(Function);
         if (!BD) {
+          // If we can't find the main symbol name, look for alternates.
           uint32_t LocalID = 1;
           while (true) {
-            // If we can't find the main symbol name, look for alternates.
             const std::string FuncName =
                 Function + "/" + std::to_string(LocalID);
             BD = BC.getBinaryDataByName(FuncName);
             if (BD)
               FuncAddrs.push_back(BD->getAddress());
             else
               break;
             LocalID++;
           }
+          // Strip LTO suffixes
+          if (std::optional<StringRef> CommonName = getLTOCommonName(Function))
+            if (LTOCommonNameMap.find(*CommonName) != LTOCommonNameMap.end())
+              llvm::append_range(FuncAddrs, LTOCommonNameMap[*CommonName]);
         } else {
           FuncAddrs.push_back(BD->getAddress());
         }
 
         if (FuncAddrs.empty()) {
           if (opts::Verbosity >= 1)
             errs() << "BOLT-WARNING: Reorder functions: can't find function "
                    << "for " << Function << "\n";

bolt/lib/Rewrite/RewriteInstance.cpp

if (opts::LiteThresholdPct) {
     LiteThresholdExecCount = TopFunctions[Index]->getKnownExecutionCount();
     outs() << "BOLT-INFO: limiting processing to functions with at least "
            << LiteThresholdExecCount << " invocations\n";
   }
   LiteThresholdExecCount = std::max(
       LiteThresholdExecCount, static_cast<uint64_t>(opts::LiteThresholdCount));
 
   StringSet<> ReorderFunctionsUserSet;
+  StringSet<> ReorderFunctionsLTOCommonSet;
   if (opts::ReorderFunctions == ReorderFunctions::RT_USER) {
     for (const std::string &Function :
-         ReorderFunctions::readFunctionOrderFile())
+         ReorderFunctions::readFunctionOrderFile()) {
       ReorderFunctionsUserSet.insert(Function);
+      if (std::optional<StringRef> LTOCommonName = getLTOCommonName(Function))
+        ReorderFunctionsLTOCommonSet.insert(*LTOCommonName);
+    }
   }
 
   uint64_t NumFunctionsToProcess = 0;
   auto shouldProcess = [&](const BinaryFunction &Function) {
     if (opts::MaxFunctions && NumFunctionsToProcess > opts::MaxFunctions)
       return false;
 
     // If the list is not empty, only process functions from the list.
if (opts::Lite) {
       // Forcibly include functions specified in the -function-order file.
       if (opts::ReorderFunctions == ReorderFunctions::RT_USER) {
         std::optional<StringRef> Match =
             Function.forEachName([&](StringRef Name) {
               return ReorderFunctionsUserSet.contains(Name);
             });
         if (Match.has_value())
           return true;
+        for (const StringRef Name : Function.getNames())
+          if (std::optional<StringRef> LTOCommonName = getLTOCommonName(Name))
+            if (ReorderFunctionsLTOCommonSet.contains(*LTOCommonName))
+              return true;
       }
 
       if (ProfileReader && !ProfileReader->mayHaveProfileData(Function))
         return false;
 
       if (Function.getKnownExecutionCount() < LiteThresholdExecCount)
         return false;
     }

bolt/test/X86/Inputs/order-lite.txt

 main
+foo.__uniq.321

bolt/test/X86/function-order-lite.s

 # Check that functions listed in -function-order list take precedence over
 # lite mode function filtering.
 
 # RUN: llvm-mc -filetype=obj -triple x86_64-unknown-unknown %s -o %t.o
 # RUN: link_fdata %s %t.o %t.fdata
 # RUN: %clang %cflags %t.o -o %t.exe -Wl,-q
 # RUN: llvm-bolt %t.exe --data %t.fdata --lite --reorder-functions=user \
 # RUN:   --function-order=%p/Inputs/order-lite.txt -o %t -print-all 2>&1 \
 # RUN:   | FileCheck %s
 
-# CHECK: 1 out of 2 functions in the binary (50.0%) have non-empty execution profile
-# CHECK: Binary Function "main" after reorder-functions
+# CHECK: 1 out of 3 functions in the binary (33.3%) have non-empty execution profile
+# CHECK-DAG: Binary Function "main" after reorder-functions
+# CHECK-DAG: Binary Function "foo.__uniq.123" after reorder-functions
 
   .globl main
   .type main, %function
 main:
   .cfi_startproc
 .LBB06:
   callq testfunc
   retq
   .cfi_endproc
 .size main, .-main
 
   .globl testfunc
   .type testfunc, %function
 testfunc:
 # FDATA: 0 [unknown] 0 1 testfunc 0 1 0
   .cfi_startproc
   pushq %rbp
   movq  %rsp, %rbp
   movl  $0x0, %eax
   popq  %rbp
   retq
   .cfi_endproc
 .size testfunc, .-testfunc
+
+  .globl foo.__uniq.123
+  .type foo.__uniq.123, %function
+foo.__uniq.123:
+  .cfi_startproc
+  pushq %rbp
+  movq  %rsp, %rbp
+  movl  $0x0, %eax
+  popq  %rbp
+  retq
+  .cfi_endproc
+.size foo.__uniq.123, .-foo.__uniq.123