Scheduler / Regalloc: use unique_ptr[] instead of std::vector

[escha]

Summary

std::vector.resize() is actually about 2-3x slower than using unique_ptr, at least for me; it doesn't compile to bzero because the resize() in std:: consists of repeated appending (agh). On our out of tree target with a huge number of registers, this patch actually saves 1% of compile time. It should help significantly on AMDGPU as well, though likely a factor less due to them not having quite the same level of ridiculous register counts.

In general, we probably shouldn't use the heavyweight-ness of std::vector for constant-size arrays. There's really no reason to.

[MatzeB]

Given that the vectors are fixed size I don't see why we would need the additional complexity of std::vector (it has to manage the size and capacity, ...). To me this change looks good with the nitpicks below addressed.

Of course it's bad that llvm doesn't get the vector initialisation optimized, but this is a separate issue, would you agree David?

lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

1221

This can be a simple SUnit * now.

1243–1246

This could use an ArrayRef<SUnit*> instead of std::unique_ptr reference + NumRegs.

[escha]

Bumping this -- given that there doesn't seem to be any sign of LLVM properly optimizing this any time soon, is this optimization okay?

[MatzeB]

Giving an official LGTM as my impression is that we are stuck with an imperfect optimizer and the work around here is easy enough. The nitpicks above still stand though.

include/llvm/CodeGen/MachineRegisterInfo.h

 
   /// PhysRegUseDefLists - This is an array of the head of the use/def list for
   /// physical registers.
-  std::vector<MachineOperand *> PhysRegUseDefLists;
+  std::unique_ptr<MachineOperand *[]> PhysRegUseDefLists;
 
   /// getRegUseDefListHead - Return the head pointer for the register use/def
   /// list for the specified virtual or physical register.

lib/CodeGen/MachineRegisterInfo.cpp

 MachineRegisterInfo::MachineRegisterInfo(const MachineFunction *MF)
   : MF(MF), TheDelegate(nullptr), IsSSA(true), TracksLiveness(true),
     TracksSubRegLiveness(false) {
+  unsigned NumRegs = getTargetRegisterInfo()->getNumRegs();
   VRegInfo.reserve(256);
   RegAllocHints.reserve(256);
-  UsedPhysRegMask.resize(getTargetRegisterInfo()->getNumRegs());
-
-  // Create the physreg use/def lists.
-  PhysRegUseDefLists.resize(getTargetRegisterInfo()->getNumRegs(), nullptr);
+  UsedPhysRegMask.resize(NumRegs);
+  PhysRegUseDefLists.reset(new MachineOperand*[NumRegs]());
 }
 
 /// setRegClass - Set the register class of the specified virtual register.

lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

   /// that are "live". These nodes must be scheduled before any other nodes that
   /// modifies the registers can be scheduled.
   unsigned NumLiveRegs;
-  std::vector<SUnit*> LiveRegDefs;
-  std::vector<SUnit*> LiveRegGens;
+  std::unique_ptr<SUnit*[]> LiveRegDefs;
+  std::unique_ptr<SUnit*[]> LiveRegGens;
 
   // Collect interferences between physical register use/defs.
   // Each interference is an SUnit and set of physical registers.

   NumLiveRegs = 0;
   // Allocate slots for each physical register, plus one for a special register
   // to track the virtual resource of a calling sequence.
-  LiveRegDefs.resize(TRI->getNumRegs() + 1, nullptr);
-  LiveRegGens.resize(TRI->getNumRegs() + 1, nullptr);
+  LiveRegDefs.reset(new SUnit*[TRI->getNumRegs() + 1]());
+  LiveRegGens.reset(new SUnit*[TRI->getNumRegs() + 1]());
   CallSeqEndForStart.clear();
   assert(Interferences.empty() && LRegsMap.empty() && "stale Interferences");
 

 /// CheckForLiveRegDef - Return true and update live register vector if the
 /// specified register def of the specified SUnit clobbers any "live" registers.
 static void CheckForLiveRegDef(SUnit *SU, unsigned Reg,
-                               std::vector<SUnit*> &LiveRegDefs,
+                               std::unique_ptr<SUnit*[]> &LiveRegDefs,
                                SmallSet<unsigned, 4> &RegAdded,
                                SmallVectorImpl<unsigned> &LRegs,
                                const TargetRegisterInfo *TRI) {

 /// CheckForLiveRegDefMasked - Check for any live physregs that are clobbered
 /// by RegMask, and add them to LRegs.
 static void CheckForLiveRegDefMasked(SUnit *SU, const uint32_t *RegMask,
-                                     std::vector<SUnit*> &LiveRegDefs,
+                                     std::unique_ptr<SUnit*[]> &LiveRegDefs,
                                      SmallSet<unsigned, 4> &RegAdded,
-                                     SmallVectorImpl<unsigned> &LRegs) {
+                                     SmallVectorImpl<unsigned> &LRegs,
+                                     unsigned NumRegs) {
   // Look at all live registers. Skip Reg0 and the special CallResource.
-  for (unsigned i = 1, e = LiveRegDefs.size()-1; i != e; ++i) {
+  for (unsigned i = 1, e = NumRegs; i != e; ++i) {
     if (!LiveRegDefs[i]) continue;
     if (LiveRegDefs[i] == SU) continue;
     if (!MachineOperand::clobbersPhysReg(RegMask, i)) continue;

       }
     }
     if (const uint32_t *RegMask = getNodeRegMask(Node))
-      CheckForLiveRegDefMasked(SU, RegMask, LiveRegDefs, RegAdded, LRegs);
+      CheckForLiveRegDefMasked(SU, RegMask, LiveRegDefs, RegAdded, LRegs,
+                               TRI->getNumRegs());
 
     const MCInstrDesc &MCID = TII->get(Node->getMachineOpcode());
     if (!MCID.ImplicitDefs)