[Spill2Reg][1/9] Initial commit. This is boilerplate code.

[vporpo]

Summary

This is the first commit for the Spill2Reg optimization pass.
The goal of this pass is to selectively replace spills to the stack with
spills to vector registers. This can help remove back-end stalls in x86.

RFC:
https://lists.llvm.org/pipermail/llvm-dev/2022-January/154782.html
https://discourse.llvm.org/t/rfc-spill2reg-selectively-replace-spills-to-stack-with-spills-to-vector-registers/59630

[vporpo]

Disable the pass by default.

[arsenm]

llvm/lib/CodeGen/Spill2Reg.cpp

26–28

Probably should move this to TargetPassConfig

[vporpo]

Moved spill2reg flag to TargetPassConfig.

llvm/lib/CodeGen/Spill2Reg.cpp

26–28

Done.

[RKSimon]

Please can you rename the Spill2Reg patch sequence using [X/N] so we can more easily track dependencies

[xiangzhangllvm]

Very good idea!
and go further, we may create concept of "cheaper spills" for scalar regs in RA (by check the interference of vector regs with it) to recalculate the spill energy in spillplacer,
and if we can load/store more scalar regs from/to one vector, it may be profitable to spill a vector reg (even the interference exist between scalar regs and vector regs) instead of spill more scalar regs.

[vporpo]

Yes, a two-tier spilling scheme might make sense for some targets: first spill to consecutive lanes in the vector, and then spill the vectors to memory. I think though that in x86 it may be a lot trickier to check when this will perform better than standard spills to stack.

[arsenm]

LGTM, but wait for more of the rest of the sequence to submit

llvm/lib/CodeGen/Spill2Reg.cpp

53

Pointless overload and ;?

[vporpo]

Removed redundant overload.

[vporpo]

Rebased

[vporpo]

Rebased

[yiminli]

Should this patch set optimize out spill/reload in function "test" of

test.cpp965 BDownload

?

I tried:

llvm-project/build/bin/clang -S -emit-llvm test.cpp -march=skylake-avx512 -O2
llvm-project/build/bin/llc \
	-enable-spill2reg -simplify-mir -spill2reg-mem-instrs=0 -spill2reg-vec-instrs=99999 \
	-march x86 -mattr=+avx2 -filetype=asm --x86-asm-syntax=intel test.ll

and got:

_Z4testPfS_S_:                          # @_Z4testPfS_S_
        .cfi_startproc
# %bb.0:                                # %entry
        sub     esp, 140
        .cfi_def_cfa_offset 144
        mov     eax, dword ptr [esp + 152]
        mov     ecx, dword ptr [esp + 144]
        vmovaps zmm0, zmmword ptr [ecx]
        vmovups zmmword ptr [esp + 64], zmm0    # 64-byte Spill
        mov     ecx, dword ptr [esp + 148]
        vmovaps zmm1, zmmword ptr [ecx]
        vaddps  zmm0, zmm0, zmm1
        vaddps  zmm1, zmm1, zmmword ptr [eax]
        vmovups zmmword ptr [esp], zmm1         # 64-byte Spill
        call    _Z12print_m512_fDv16_f
        vmovups zmm0, zmmword ptr [esp]         # 64-byte Reload
        call    _Z12print_m512_fDv16_f
        vmovups zmm0, zmmword ptr [esp + 64]    # 64-byte Reload
        add     esp, 140
        .cfi_def_cfa_offset 4
        ret

Did I miss anything? Thanks!

[vporpo]

In the test you provided vector registers are spilled across the call . Spill2reg will not try to work with vector spills/reloads. The reasoning is that if there is a free register for spill2reg to use, then the register allocator would have already found it and used it to avoid the spill. It would also make little sense performance wise because saving/restoring a vector register to another vector register is simply redundant: you could have just used the destination register in the first place.

llvm/include/llvm/CodeGen/MachinePassRegistry.def

 DUMMY_MACHINE_FUNCTION_PASS("ra-pbqp", RAPBQPPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("legalizer", LegalizerPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("irtranslator", IRTranslatorPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("regbankselect", RegBankSelectPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("instruction-select", InstructionSelectPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("reset-machine-function", ResetMachineFunctionPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("machineverifier", MachineVerifierPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("print-machine-cycles", MachineCycleInfoPrinterPass, ())
+DUMMY_MACHINE_FUNCTION_PASS("spill2reg", Spill2RegPass, ())
 #undef DUMMY_MACHINE_FUNCTION_PASS

llvm/include/llvm/CodeGen/Passes.h

namespace llvm {
   /// otherwise this does nothing
   FunctionPass *createRegAllocScoringPass();
 
   /// JMC instrument pass.
   ModulePass *createJMCInstrumenterPass();
 
   /// This pass converts conditional moves to conditional jumps when profitable.
   FunctionPass *createSelectOptimizePass();
+
+  /// This pass replaces spills to stack with spills to registers.
+  extern char &Spill2RegID;
 } // End llvm namespace
 
 #endif

llvm/include/llvm/InitializePasses.h

 void initializeVirtRegMapPass(PassRegistry&);
 void initializeVirtRegRewriterPass(PassRegistry&);
 void initializeWarnMissedTransformationsLegacyPass(PassRegistry &);
 void initializeWasmEHPreparePass(PassRegistry&);
 void initializeWinEHPreparePass(PassRegistry&);
 void initializeWriteBitcodePassPass(PassRegistry&);
 void initializeWriteThinLTOBitcodePass(PassRegistry&);
 void initializeXRayInstrumentationPass(PassRegistry&);
+void initializeSpill2RegPass(PassRegistry &);
 
 } // end namespace llvm
 
 #endif // LLVM_INITIALIZEPASSES_H

llvm/lib/CodeGen/CMakeLists.txt

add_llvm_component_library(LLVMCodeGen
   ScheduleDAGPrinter.cpp
   ScoreboardHazardRecognizer.cpp
   SelectOptimize.cpp
   ShadowStackGCLowering.cpp
   ShrinkWrap.cpp
   SjLjEHPrepare.cpp
   SlotIndexes.cpp
   SpillPlacement.cpp
+  Spill2Reg.cpp
   SplitKit.cpp
   StackColoring.cpp
   StackMapLivenessAnalysis.cpp
   StackMaps.cpp
   StackProtector.cpp
   StackSlotColoring.cpp
   SwiftErrorValueTracking.cpp
   SwitchLoweringUtils.cpp

llvm/lib/CodeGen/CodeGen.cpp

void llvm::initializeCodeGen(PassRegistry &Registry) {
   initializeUnpackMachineBundlesPass(Registry);
   initializeUnreachableBlockElimLegacyPassPass(Registry);
   initializeUnreachableMachineBlockElimPass(Registry);
   initializeVirtRegMapPass(Registry);
   initializeVirtRegRewriterPass(Registry);
   initializeWasmEHPreparePass(Registry);
   initializeWinEHPreparePass(Registry);
   initializeXRayInstrumentationPass(Registry);
+  initializeSpill2RegPass(Registry);
 }
 
 void LLVMInitializeCodeGen(LLVMPassRegistryRef R) {
   initializeCodeGen(*unwrap(R));
 }

llvm/lib/CodeGen/Spill2Reg.cpp

+//===- Spill2Reg.cpp - Spill To Register Optimization ---------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+//
+/// \file This file implements Spill2Reg, an optimization which selectively
+/// replaces spills/reloads to/from the stack with register copies to/from the
+/// vector register file. This works even on targets where load/stores have
+/// similar latency to register copies because it can free up memory units which
+/// helps avoid back-end stalls.
+///
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Support/CommandLine.h"
+
+using namespace llvm;
+
+namespace {
+
+class Spill2Reg : public MachineFunctionPass {
+public:
+  static char ID;
+  Spill2Reg() : MachineFunctionPass(ID) {
+    initializeSpill2RegPass(*PassRegistry::getPassRegistry());
+  }
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+  void releaseMemory() override;
+  bool runOnMachineFunction(MachineFunction &) override;
+};
+
+} // namespace
+
+void Spill2Reg::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesCFG();
+  MachineFunctionPass::getAnalysisUsage(AU);
+}
+
+void Spill2Reg::releaseMemory() {}
+
+bool Spill2Reg::runOnMachineFunction(MachineFunction &MFn) {
+  llvm_unreachable("Unimplemented");
+}
+
+char Spill2Reg::ID = 0;
+
+char &llvm::Spill2RegID = Spill2Reg::ID;
+
+INITIALIZE_PASS_BEGIN(Spill2Reg, "spill2reg", "Spill2Reg", false, false)
+INITIALIZE_PASS_END(Spill2Reg, "spill2reg", "Spill2Reg", false, false)

llvm/lib/CodeGen/TargetPassConfig.cpp

static cl::opt<CFLAAType> UseCFLAA(
     cl::values(clEnumValN(CFLAAType::None, "none", "Disable CFL-AA"),
                clEnumValN(CFLAAType::Steensgaard, "steens",
                           "Enable unification-based CFL-AA"),
                clEnumValN(CFLAAType::Andersen, "anders",
                           "Enable inclusion-based CFL-AA"),
                clEnumValN(CFLAAType::Both, "both",
                           "Enable both variants of CFL-AA")));
 
+// Enable the Spill2Reg pass.
+static cl::opt<bool> EnableSpill2Reg("enable-spill2reg", cl::Hidden,
+                                     cl::init(false),
+                                     cl::desc("Enable Spill2Reg pass"));
+
 /// Option names for limiting the codegen pipeline.
 /// Those are used in error reporting and we didn't want
 /// to duplicate their names all over the place.
 static const char StartAfterOptName[] = "start-after";
 static const char StartBeforeOptName[] = "start-before";
 static const char StopAfterOptName[] = "stop-after";
 static const char StopBeforeOptName[] = "stop-before";
 
bool TargetPassConfig::addRegAssignAndRewriteOptimized() {
   addPass(createRegAllocPass(true));
 
   // Allow targets to change the register assignments before rewriting.
   addPreRewrite();
 
   // Finally rewrite virtual registers.
   addPass(&VirtRegRewriterID);
 
+  // Replace spills to stack with spills to registers.
+  if (EnableSpill2Reg)
+    addPass(&Spill2RegID);
+
   // Regalloc scoring for ML-driven eviction - noop except when learning a new
   // eviction policy.
   addPass(createRegAllocScoringPass());
   return true;
 }
 
 /// Return true if the default global register allocator is in use and
 /// has not be overriden on the command line with '-regalloc=...'