[llvm] Refactor BalancedPartitioning for fixing build failure with MSVC

[kamleshbhalui]

Summary

Fix build failure on windows system with msvc toolchain

[MaskRay]

Can you describe how this breaks in your Windows system?

[kamleshbhalui]

ThreadPool.h ends up including immintrin.h from MSVC after builtin generation in clang and It has definitions for replacing one builtins with another.
Clang maintain a enum for all generated builtin but due to above macro replacement enum ends up having two element with same name and it causes multiple definitions error.
There are some other instances where ThreadPool.h is not included directly(i.e. Debuginfod.h).

[ellis]

In D153318#4436375, @kamleshbhalui wrote:

ThreadPool.h ends up including immintrin.h from MSVC after builtin generation in clang and It has definitions for replacing one builtins with another.
Clang maintain a enum for all generated builtin but due to above macro replacement enum ends up having two element with same name and it causes multiple definitions error.
There are some other instances where ThreadPool.h is not included directly(i.e. Debuginfod.h).

I'm not understanding why this change fixes that since we are still including ThreadPool.h in BalancedPartitioning.cpp. This seems like something that should be fixed in ThreadPool.h itself.

llvm/include/llvm/Support/BalancedPartitioning.h

118

Why not keep ThreadPool owned by BPThreadPool? Why make this an alias?

[kamleshbhalui]

In D153318#4436431, @ellis wrote:

In D153318#4436375, @kamleshbhalui wrote:

ThreadPool.h ends up including immintrin.h from MSVC after builtin generation in clang and It has definitions for replacing one builtins with another.
Clang maintain a enum for all generated builtin but due to above macro replacement enum ends up having two element with same name and it causes multiple definitions error.
There are some other instances where ThreadPool.h is not included directly(i.e. Debuginfod.h).

I'm not understanding why this change fixes that since we are still including ThreadPool.h in BalancedPartitioning.cpp. This seems like something that should be fixed in ThreadPool.h itself.

Including ThreadPool.h in BalancedPartitioning.cpp is not an issue, issue comes when we include it in BalancedPartitioning.h.

[kamleshbhalui]

llvm/include/llvm/Support/BalancedPartitioning.h

118

We do not know complete type of ThreadPool here so we can not do that.

[kamleshbhalui]

clang-formatted

[kamleshbhalui]

clang-formatted

[ellis]

llvm/lib/Support/BalancedPartitioning.cpp

84

Lets move this line to be inside LLVM_ENABLE_THREADS because it won't be used if it's not enabled.

[kamleshbhalui]

address comments

[kamleshbhalui]

clang formatted

[ellis]

SGTM

llvm/include/llvm/Support/BalancedPartitioning.h

 //     https://arxiv.org/abs/2211.09285
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_BALANCED_PARTITIONING_H
 #define LLVM_SUPPORT_BALANCED_PARTITIONING_H
 
 #include "raw_ostream.h"
-#include "llvm/Support/ThreadPool.h"
+#include "llvm/ADT/ArrayRef.h"
 
+#include <atomic>
+#include <condition_variable>
+#include <mutex>
 #include <random>
 #include <vector>
 
 namespace llvm {
 
+class ThreadPool;
 /// A function with a set of utility nodes where it is beneficial to order two
 /// functions close together if they have similar utility nodes
 class BPFunctionNode {
   friend class BalancedPartitioning;
 
 public:
   using IDT = uint64_t;
   using UtilityNodeT = uint32_t;
private:
   using FunctionNodeRange =
       iterator_range<std::vector<BPFunctionNode>::iterator>;
 
   /// A special ThreadPool that allows for spawning new tasks after blocking on
   /// wait(). BalancedPartitioning recursively spawns new threads inside other
   /// threads, so we need to track how many active threads that could spawn more
   /// threads.
   struct BPThreadPool {
-    ThreadPool TheThreadPool;
+    ThreadPool &TheThreadPool;
     std::mutex mtx;
     std::condition_variable cv;
     /// The number of threads that could spawn more threads
     std::atomic<int> NumActiveThreads = 0;
     /// Only true when all threads are down spawning new threads
     bool IsFinishedSpawning = false;
     /// Asynchronous submission of the task to the pool
     template <typename Func> void async(Func &&F);
     /// Blocking wait for all threads to complete. Unlike ThreadPool, it is
     /// acceptable for other threads to add more tasks while blocking on this
     /// call.
     void wait();
+    BPThreadPool(ThreadPool &TheThreadPool) : TheThreadPool(TheThreadPool) {}
   };
 
   /// Run a recursive bisection of a given list of FunctionNodes
   /// \param RecDepth the current depth of recursion
   /// \param RootBucket the initial bucket of the dataVertices
   /// \param Offset the assigned buckets are the range [Offset, Offset +
   /// Nodes.size()]
   void bisect(const FunctionNodeRange Nodes, unsigned RecDepth,

llvm/lib/Support/BalancedPartitioning.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Support/BalancedPartitioning.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/ThreadPool.h"
 
 using namespace llvm;
 #define DEBUG_TYPE "balanced-partitioning"
 
 void BPFunctionNode::dump(raw_ostream &OS) const {
   OS << formatv("{{ID={0} Utilities={{{1:$[,]}} Bucket={2}}", Id,
                 make_range(UtilityNodes.begin(), UtilityNodes.end()), Bucket);
 }
for (unsigned I = 1; I < LOG_CACHE_SIZE; I++)
     Log2Cache[I] = std::log2(I);
 }
 
 void BalancedPartitioning::run(std::vector<BPFunctionNode> &Nodes) const {
   LLVM_DEBUG(
       dbgs() << format(
           "Partitioning %d nodes using depth %d and %d iterations per split\n",
           Nodes.size(), Config.SplitDepth, Config.IterationsPerSplit));
   std::optional<BPThreadPool> TP;
 #if LLVM_ENABLE_THREADS
+  ThreadPool TheThreadPool;
   if (Config.TaskSplitDepth > 1)
-    TP.emplace();
+    TP.emplace(TheThreadPool);
 #endif
 
   // Record the input order
   for (unsigned I = 0; I < Nodes.size(); I++)
     Nodes[I].InputOrderIndex = I;
 
   auto NodesRange = llvm::make_range(Nodes.begin(), Nodes.end());
   auto BisectTask = [=, &TP]() {