[CodeGen][NewPM] Port SpillPlacement analysis to NPM

[optimisan]

I am not sure how to test this.
Porting Greedy regalloc next.

[optimisan]

• [CodeGen][NewPM] Port SpillPlacement analysis to NPM #116618 👈 (View in Graphite)
• [NFC] Use unique_ptr in SparseSet #116617
• [CodeGen][NewPM] Port EdgeBundles analysis to NPM #116616
• main

This stack of pull requests is managed by Graphite. Learn more about stacking.

[llvmbot]

@llvm/pr-subscribers-llvm-regalloc

Author: Akshat Oke (optimisan)

Changes

I am not sure how to test this.

---

Full diff: https://github.com/llvm/llvm-project/pull/116618.diff

4 Files Affected:

• (modified) llvm/include/llvm/InitializePasses.h (+1-1)
• (modified) llvm/lib/CodeGen/RegAllocGreedy.cpp (+3-3)
• (modified) llvm/lib/CodeGen/SpillPlacement.cpp (+58-33)
• (modified) llvm/lib/CodeGen/SpillPlacement.h (+42-10)

diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h
index fb8356b9c98cb9..728b178e0cdad7 100644
--- a/llvm/include/llvm/InitializePasses.h
+++ b/llvm/include/llvm/InitializePasses.h
@@ -289,7 +289,7 @@ void initializeSinkingLegacyPassPass(PassRegistry &);
 void initializeSjLjEHPreparePass(PassRegistry &);
 void initializeSlotIndexesWrapperPassPass(PassRegistry &);
 void initializeSpeculativeExecutionLegacyPassPass(PassRegistry &);
-void initializeSpillPlacementPass(PassRegistry &);
+void initializeSpillPlacementWrapperLegacyPass(PassRegistry &);
 void initializeStackColoringLegacyPass(PassRegistry &);
 void initializeStackFrameLayoutAnalysisPassPass(PassRegistry &);
 void initializeStackMapLivenessPass(PassRegistry &);
diff --git a/llvm/lib/CodeGen/RegAllocGreedy.cpp b/llvm/lib/CodeGen/RegAllocGreedy.cpp
index 3542bfe18af46f..3fdf2d6e07a75f 100644
--- a/llvm/lib/CodeGen/RegAllocGreedy.cpp
+++ b/llvm/lib/CodeGen/RegAllocGreedy.cpp
@@ -162,7 +162,7 @@ INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(VirtRegMapWrapperLegacy)
 INITIALIZE_PASS_DEPENDENCY(LiveRegMatrixWrapperLegacy)
 INITIALIZE_PASS_DEPENDENCY(EdgeBundlesWrapperLegacy)
-INITIALIZE_PASS_DEPENDENCY(SpillPlacement)
+INITIALIZE_PASS_DEPENDENCY(SpillPlacementWrapperLegacy)
 INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass)
 INITIALIZE_PASS_DEPENDENCY(RegAllocEvictionAdvisorAnalysis)
 INITIALIZE_PASS_DEPENDENCY(RegAllocPriorityAdvisorAnalysis)
@@ -217,7 +217,7 @@ void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<LiveRegMatrixWrapperLegacy>();
   AU.addPreserved<LiveRegMatrixWrapperLegacy>();
   AU.addRequired<EdgeBundlesWrapperLegacy>();
-  AU.addRequired<SpillPlacement>();
+  AU.addRequired<SpillPlacementWrapperLegacy>();
   AU.addRequired<MachineOptimizationRemarkEmitterPass>();
   AU.addRequired<RegAllocEvictionAdvisorAnalysis>();
   AU.addRequired<RegAllocPriorityAdvisorAnalysis>();
@@ -2731,7 +2731,7 @@ bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
   ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
   Loops = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
   Bundles = &getAnalysis<EdgeBundlesWrapperLegacy>().getEdgeBundles();
-  SpillPlacer = &getAnalysis<SpillPlacement>();
+  SpillPlacer = &getAnalysis<SpillPlacementWrapperLegacy>().getResult();
   DebugVars = &getAnalysis<LiveDebugVariables>();
 
   initializeCSRCost();
diff --git a/llvm/lib/CodeGen/SpillPlacement.cpp b/llvm/lib/CodeGen/SpillPlacement.cpp
index 318e2b19322bb4..c9baabf6161d3a 100644
--- a/llvm/lib/CodeGen/SpillPlacement.cpp
+++ b/llvm/lib/CodeGen/SpillPlacement.cpp
@@ -44,17 +44,17 @@ using namespace llvm;
 
 #define DEBUG_TYPE "spill-code-placement"
 
-char SpillPlacement::ID = 0;
+char SpillPlacementWrapperLegacy::ID = 0;
 
-char &llvm::SpillPlacementID = SpillPlacement::ID;
+char &llvm::SpillPlacementID = SpillPlacementWrapperLegacy::ID;
 
-INITIALIZE_PASS_BEGIN(SpillPlacement, DEBUG_TYPE,
+INITIALIZE_PASS_BEGIN(SpillPlacementWrapperLegacy, DEBUG_TYPE,
                       "Spill Code Placement Analysis", true, true)
 INITIALIZE_PASS_DEPENDENCY(EdgeBundlesWrapperLegacy)
-INITIALIZE_PASS_END(SpillPlacement, DEBUG_TYPE,
+INITIALIZE_PASS_END(SpillPlacementWrapperLegacy, DEBUG_TYPE,
                     "Spill Code Placement Analysis", true, true)
 
-void SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const {
+void SpillPlacementWrapperLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
   AU.addRequiredTransitive<EdgeBundlesWrapperLegacy>();
@@ -189,32 +189,57 @@ struct SpillPlacement::Node {
   }
 };
 
-bool SpillPlacement::runOnMachineFunction(MachineFunction &mf) {
+bool SpillPlacementWrapperLegacy::runOnMachineFunction(MachineFunction &MF) {
+  auto *Bundles = &getAnalysis<EdgeBundlesWrapperLegacy>().getEdgeBundles();
+  auto *MBFI = &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
+
+  Impl.reset(new SpillPlacement(Bundles, MBFI));
+  Impl->run(MF);
+  return false;
+}
+
+AnalysisKey SpillPlacementAnalysis::Key;
+
+SpillPlacement
+SpillPlacementAnalysis::run(MachineFunction &MF,
+                            MachineFunctionAnalysisManager &MFAM) {
+  auto *Bundles = &MFAM.getResult<EdgeBundlesAnalysis>(MF);
+  auto *MBFI = &MFAM.getResult<MachineBlockFrequencyAnalysis>(MF);
+  SpillPlacement Impl(Bundles, MBFI);
+  Impl.run(MF);
+  return Impl;
+}
+
+bool SpillPlacementAnalysis::Result::invalidate(
+    MachineFunction &MF, const PreservedAnalyses &PA,
+    MachineFunctionAnalysisManager::Invalidator &Inv) {
+  auto PAC = PA.getChecker<SpillPlacementAnalysis>();
+  return !(PAC.preserved() ||
+           PAC.preservedSet<AllAnalysesOn<MachineFunction>>()) ||
+         Inv.invalidate<EdgeBundlesAnalysis>(MF, PA) ||
+         Inv.invalidate<MachineBlockFrequencyAnalysis>(MF, PA);
+}
+
+void SpillPlacement::arrayDeleter(Node *N) {
+  if (N)
+    delete[] N;
+}
+
+void SpillPlacement::run(MachineFunction &mf) {
   MF = &mf;
-  bundles = &getAnalysis<EdgeBundlesWrapperLegacy>().getEdgeBundles();
 
   assert(!nodes && "Leaking node array");
-  nodes = new Node[bundles->getNumBundles()];
+  nodes.reset(new Node[bundles->getNumBundles()]);
   TodoList.clear();
   TodoList.setUniverse(bundles->getNumBundles());
 
   // Compute total ingoing and outgoing block frequencies for all bundles.
   BlockFrequencies.resize(mf.getNumBlockIDs());
-  MBFI = &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
   setThreshold(MBFI->getEntryFreq());
   for (auto &I : mf) {
     unsigned Num = I.getNumber();
     BlockFrequencies[Num] = MBFI->getBlockFreq(&I);
   }
-
-  // We never change the function.
-  return false;
-}
-
-void SpillPlacement::releaseMemory() {
-  delete[] nodes;
-  nodes = nullptr;
-  TodoList.clear();
 }
 
 /// activate - mark node n as active if it wasn't already.
@@ -223,7 +248,7 @@ void SpillPlacement::activate(unsigned n) {
   if (ActiveNodes->test(n))
     return;
   ActiveNodes->set(n);
-  nodes[n].clear(Threshold);
+  nodes.get()[n].clear(Threshold);
 
   // Very large bundles usually come from big switches, indirect branches,
   // landing pads, or loops with many 'continue' statements. It is difficult to
@@ -235,10 +260,10 @@ void SpillPlacement::activate(unsigned n) {
   // limiting the number of blocks visited and the number of links in the
   // Hopfield network.
   if (bundles->getBlocks(n).size() > 100) {
-    nodes[n].BiasP = BlockFrequency(0);
+    nodes.get()[n].BiasP = BlockFrequency(0);
     BlockFrequency BiasN = MBFI->getEntryFreq();
     BiasN >>= 4;
-    nodes[n].BiasN = BiasN;
+    nodes.get()[n].BiasN = BiasN;
   }
 }
 
@@ -265,14 +290,14 @@ void SpillPlacement::addConstraints(ArrayRef<BlockConstraint> LiveBlocks) {
     if (LB.Entry != DontCare) {
       unsigned ib = bundles->getBundle(LB.Number, false);
       activate(ib);
-      nodes[ib].addBias(Freq, LB.Entry);
+      nodes.get()[ib].addBias(Freq, LB.Entry);
     }
 
     // Live-out from block?
     if (LB.Exit != DontCare) {
       unsigned ob = bundles->getBundle(LB.Number, true);
       activate(ob);
-      nodes[ob].addBias(Freq, LB.Exit);
+      nodes.get()[ob].addBias(Freq, LB.Exit);
     }
   }
 }
@@ -287,8 +312,8 @@ void SpillPlacement::addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong) {
     unsigned ob = bundles->getBundle(B, true);
     activate(ib);
     activate(ob);
-    nodes[ib].addBias(Freq, PrefSpill);
-    nodes[ob].addBias(Freq, PrefSpill);
+    nodes.get()[ib].addBias(Freq, PrefSpill);
+    nodes.get()[ob].addBias(Freq, PrefSpill);
   }
 }
 
@@ -303,8 +328,8 @@ void SpillPlacement::addLinks(ArrayRef<unsigned> Links) {
     activate(ib);
     activate(ob);
     BlockFrequency Freq = BlockFrequencies[Number];
-    nodes[ib].addLink(ob, Freq);
-    nodes[ob].addLink(ib, Freq);
+    nodes.get()[ib].addLink(ob, Freq);
+    nodes.get()[ob].addLink(ib, Freq);
   }
 }
 
@@ -314,18 +339,18 @@ bool SpillPlacement::scanActiveBundles() {
     update(n);
     // A node that must spill, or a node without any links is not going to
     // change its value ever again, so exclude it from iterations.
-    if (nodes[n].mustSpill())
+    if (nodes.get()[n].mustSpill())
       continue;
-    if (nodes[n].preferReg())
+    if (nodes.get()[n].preferReg())
       RecentPositive.push_back(n);
   }
   return !RecentPositive.empty();
 }
 
 bool SpillPlacement::update(unsigned n) {
-  if (!nodes[n].update(nodes, Threshold))
+  if (!nodes.get()[n].update(nodes.get(), Threshold))
     return false;
-  nodes[n].getDissentingNeighbors(TodoList, nodes);
+  nodes.get()[n].getDissentingNeighbors(TodoList, nodes.get());
   return true;
 }
 
@@ -345,7 +370,7 @@ void SpillPlacement::iterate() {
     unsigned n = TodoList.pop_back_val();
     if (!update(n))
       continue;
-    if (nodes[n].preferReg())
+    if (nodes.get()[n].preferReg())
       RecentPositive.push_back(n);
   }
 }
@@ -366,7 +391,7 @@ SpillPlacement::finish() {
   // Write preferences back to ActiveNodes.
   bool Perfect = true;
   for (unsigned n : ActiveNodes->set_bits())
-    if (!nodes[n].preferReg()) {
+    if (!nodes.get()[n].preferReg()) {
       ActiveNodes->reset(n);
       Perfect = false;
     }
diff --git a/llvm/lib/CodeGen/SpillPlacement.h b/llvm/lib/CodeGen/SpillPlacement.h
index 5fd9b085259d1d..e5c03a3db9f987 100644
--- a/llvm/lib/CodeGen/SpillPlacement.h
+++ b/llvm/lib/CodeGen/SpillPlacement.h
@@ -29,6 +29,7 @@
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/SparseSet.h"
+#include "llvm/CodeGen/MachineFunctionAnalysis.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/Support/BlockFrequency.h"
 
@@ -38,13 +39,21 @@ class BitVector;
 class EdgeBundles;
 class MachineBlockFrequencyInfo;
 class MachineFunction;
+class SpillPlacementWrapperLegacy;
+class SpillPlacementAnalysis;
+
+class SpillPlacement {
+  friend class SpillPlacementWrapperLegacy;
+  friend class SpillPlacementAnalysis;
 
-class SpillPlacement : public MachineFunctionPass {
   struct Node;
+
   const MachineFunction *MF = nullptr;
   const EdgeBundles *bundles = nullptr;
   const MachineBlockFrequencyInfo *MBFI = nullptr;
-  Node *nodes = nullptr;
+
+  static void arrayDeleter(Node *N);
+  std::unique_ptr<Node, decltype(&arrayDeleter)> nodes;
 
   // Nodes that are active in the current computation. Owned by the prepare()
   // caller.
@@ -68,11 +77,6 @@ class SpillPlacement : public MachineFunctionPass {
   SparseSet<unsigned> TodoList;
 
 public:
-  static char ID; // Pass identification, replacement for typeid.
-
-  SpillPlacement() : MachineFunctionPass(ID) {}
-  ~SpillPlacement() override { releaseMemory(); }
-
   /// BorderConstraint - A basic block has separate constraints for entry and
   /// exit.
   enum BorderConstraint {
@@ -154,17 +158,45 @@ class SpillPlacement : public MachineFunctionPass {
     return BlockFrequencies[Number];
   }
 
+  bool invalidate(MachineFunction &MF, const PreservedAnalyses &PA,
+                  MachineFunctionAnalysisManager::Invalidator &Inv);
+
 private:
-  bool runOnMachineFunction(MachineFunction &mf) override;
-  void getAnalysisUsage(AnalysisUsage &AU) const override;
-  void releaseMemory() override;
+  SpillPlacement(EdgeBundles *Bundles, MachineBlockFrequencyInfo *MBFI)
+      : bundles(Bundles), MBFI(MBFI), nodes(nullptr, &arrayDeleter) {}
 
+  void run(MachineFunction &MF);
   void activate(unsigned n);
   void setThreshold(BlockFrequency Entry);
 
   bool update(unsigned n);
 };
 
+class SpillPlacementWrapperLegacy : public MachineFunctionPass {
+public:
+  static char ID;
+  SpillPlacementWrapperLegacy() : MachineFunctionPass(ID) {}
+
+  SpillPlacement &getResult() { return *Impl; }
+  const SpillPlacement &getResult() const { return *Impl; }
+
+private:
+  std::unique_ptr<SpillPlacement> Impl;
+  bool runOnMachineFunction(MachineFunction &MF) override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+  void releaseMemory() override { Impl.reset(); }
+};
+
+class SpillPlacementAnalysis
+    : public AnalysisInfoMixin<SpillPlacementAnalysis> {
+  friend AnalysisInfoMixin<SpillPlacementAnalysis>;
+  static AnalysisKey Key;
+
+public:
+  using Result = SpillPlacement;
+  SpillPlacement run(MachineFunction &, MachineFunctionAnalysisManager &);
+};
+
 } // end namespace llvm
 
 #endif // LLVM_LIB_CODEGEN_SPILLPLACEMENT_H

[paperchalice]

Array form would be better:

Suggested change

	std::unique_ptr<Node, decltype(&arrayDeleter)> nodes;
	std::unique_ptr<Node[]> nodes;

https://en.cppreference.com/w/cpp/memory/unique_ptr

[optimisan]

The definition of Node is not available here, so the default deleter fails to compile sizeof(Node) for this incomplete type. To hack around it I put the definition of arrayDeleter in the implementation where struct Node is defined.

But changing to unique_ptr<Node[], theDeleter> facilitates removal of .get() calls

[paperchalice]

An outlined default destructor would work. 🤔

[optimisan]

That works

[paperchalice]

You can use operator [] if nodes is an array form unique_ptr.

[arsenm]

demorgan condition

[arsenm]

Don't see why this needs to be heap allocated and not just a pass member

[github-actions]

✅ With the latest revision this PR passed the C/C++ code formatter.

[arsenm]

Alphabetical order

[arsenm]

demorgan this

[arsenm]

Not sure what this comment is supposed to mean