[CodeGen] Store LiveRegs in SetVector

[samparker]

Summary

liveins are dumped in many of the test cases and so storing them in a set can result in non-deterministic failures. I'm not sure whether this could cause of issues too... I'm also wondering how this hasn't come up before, have I missed something? SparseSet has now been replaced with a SetVector.

[samparker]

Ping.

[ributzka]

SpareSet is deterministic given the same input order - similar to SetVector. Printing the result is not the common use case, so changing the print function to sort the output first might be more useful for testing purposes.

[samparker]

Ah, thanks, then maybe I need to look elsewhere. I appear to be running into const issues when trying to sort in print and dump.

llvm/include/llvm/CodeGen/LivePhysRegs.h

 ///
 /// %ymm0 = ...
 /// %xmm0 = ..., implicit %ymm0 (%ymm0 and all its sub-registers are alive)
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_LIVEPHYSREGS_H
 #define LLVM_CODEGEN_LIVEPHYSREGS_H
 
-#include "llvm/ADT/SparseSet.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
 #include "llvm/MC/MCRegisterInfo.h"
 #include <cassert>
 #include <utility>
 
 namespace llvm {
 
 class MachineInstr;
 class MachineOperand;
 class MachineRegisterInfo;
 class raw_ostream;
 
 /// A set of physical registers with utility functions to track liveness
 /// when walking backward/forward through a basic block.
 class LivePhysRegs {
   const TargetRegisterInfo *TRI = nullptr;
-  using RegisterSet = SparseSet<MCPhysReg, identity<MCPhysReg>>;
+  using RegisterSet = SetVector<MCPhysReg>;
   RegisterSet LiveRegs;
 
 public:
   /// Constructs an unitialized set. init() needs to be called to initialize it.
   LivePhysRegs() = default;
 
   /// Constructs and initializes an empty set.
-  LivePhysRegs(const TargetRegisterInfo &TRI) : TRI(&TRI) {
-    LiveRegs.setUniverse(TRI.getNumRegs());
-  }
+  LivePhysRegs(const TargetRegisterInfo &TRI) : TRI(&TRI) { }
 
   LivePhysRegs(const LivePhysRegs&) = delete;
   LivePhysRegs &operator=(const LivePhysRegs&) = delete;
 
   /// (re-)initializes and clears the set.
   void init(const TargetRegisterInfo &TRI) {
     this->TRI = &TRI;
     LiveRegs.clear();
-    LiveRegs.setUniverse(TRI.getNumRegs());
   }
 
   /// Clears the set.
   void clear() { LiveRegs.clear(); }
 
   /// Returns true if the set is empty.
   bool empty() const { return LiveRegs.empty(); }
 
   /// Adds a physical register and all its sub-registers to the set.
   void addReg(MCPhysReg Reg) {
     assert(TRI && "LivePhysRegs is not initialized.");
     assert(Reg <= TRI->getNumRegs() && "Expected a physical register.");
     for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
          SubRegs.isValid(); ++SubRegs)
       LiveRegs.insert(*SubRegs);
   }
 
   /// Removes a physical register, all its sub-registers, and all its
   /// super-registers from the set.
   void removeReg(MCPhysReg Reg) {
     assert(TRI && "LivePhysRegs is not initialized.");
     assert(Reg <= TRI->getNumRegs() && "Expected a physical register.");
     for (MCRegAliasIterator R(Reg, TRI, true); R.isValid(); ++R)
-      LiveRegs.erase(*R);
+      LiveRegs.remove(*R);
   }
 
   /// Removes physical registers clobbered by the regmask operand \p MO.
   void removeRegsInMask(const MachineOperand &MO,
         SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> *Clobbers =
         nullptr);
 
   /// Returns true if register \p Reg is contained in the set. This also

llvm/test/CodeGen/ARM/constant-island-movwt.mir

 # CHECK-NEXT:     t2B %bb.2, 14, $noreg
 # CHECK-NEXT: {{^  $}}
 # CHECK-NEXT:   bb.1 (align 4):
 # CHECK-NEXT:     successors:{{ }}
 # CHECK-NEXT: {{^  $}}
 # CHECK-NEXT:    CONSTPOOL_ENTRY 1, %const.0, 4
 # CHECK-NEXT: {{^  $}}
 # CHECK-NEXT:   bb.2.entry (align 2):
-# CHECK-NEXT:   liveins: $d13, $s27, $r10, $r9, $r8, $s26, $d12, $s25, $s24,
-# CHECK-SAME:            $d15, $s30, $s31, $d14, $s28, $s29, $lr, $r0, $d21,
-# CHECK-SAME:            $r3, $q10, $d20, $d17, $r2, $d25, $q11, $d22, $d23,
-# CHECK-SAME:            $r1, $q8, $d16, $s3, $q14, $d28, $d29, $d19, $s17,
-# CHECK-SAME:            $d8, $s16, $r6, $r7, $r4, $q12, $q9, $d18, $s0, $q15,
-# CHECK-SAME:            $d30, $d31, $r12, $s1, $d0, $d24, $s2, $d1, $q0, $s6,
-# CHECK-SAME:            $d3, $d2, $s4, $q1, $s7, $s5, $d9, $s18, $s19, $q4
+# CHECK-NEXT: liveins: $r10, $r9, $r8, $d15, $s30, $s31, $d14, $s28, $s29,
+# CHECK-SAME:          $d13, $s26, $s27, $d12, $s24, $s25, $lr, $r0, $q10,
+# CHECK-SAME:          $d20, $d21, $r2, $q11, $d22, $d23, $q8, $d16, $d17,
+# CHECK-SAME:          $q14, $d28, $d29, $r6, $q9, $d18, $d19, $r1, $r12,
+# CHECK-SAME:          $r7, $r3, $d0, $s0, $s1, $q0, $d1, $s2, $s3, $d31,
+# CHECK-SAME:          $q15, $d30, $d25, $q12, $d24, $d9, $s18, $s19, $q4,
+# CHECK-SAME:          $d8, $s16, $s17, $q1, $d2, $s4, $s5, $d3, $s6, $s7, $r4
 # CHECK-NEXT: {{^  $}}
 # CHECK-NEXT:     $r5 = t2MOVi16 target-flags(arm-lo16) @.str.84, 14, $noreg
 # CHECK-NEXT:     $r5 = t2MOVTi16 $r5, target-flags(arm-hi16) @.str.84, 14, $noreg

llvm/test/CodeGen/X86/tail-call-conditional.mir

body:             |
 
   ; CHECK: bb.1:
   ; CHECK-NEXT: successors: %bb.2({{[^)]+}}){{$}}
   ; CHECK-NEXT: liveins: $rax, $rsi
   ; CHECK-NEXT: {{^  $}}
   ; CHECK-NEXT: $rdi = COPY $rsi
   ; CHECK-NEXT: $rsi = COPY $rax
   ; CHECK-NEXT: CMP64ri8 $rax, 9, implicit-def $eflags
-  ; CHECK-NEXT: TCRETURNdi64cc @f1, 0, 6, csr_64, implicit $rsp, implicit $eflags, implicit $ssp, implicit $rsp, implicit $rdi, implicit $rsi, implicit $rdi, implicit-def $rdi, implicit $hsi, implicit-def $hsi, implicit $sih, implicit-def $sih, implicit $sil, implicit-def $sil, implicit $si, implicit-def $si, implicit $esi, implicit-def $esi, implicit $rsi, implicit-def $rsi, implicit $hdi, implicit-def $hdi, implicit $dih, implicit-def $dih, implicit $dil, implicit-def $dil, implicit $di, implicit-def $di, implicit $edi, implicit-def $edi
+  ; CHECK-NEXT: TCRETURNdi64cc @f1, 0, 6, csr_64, implicit $rsp, implicit $eflags, implicit $ssp, implicit $rsp, implicit $rdi, implicit $rsi, implicit $rdi, implicit-def $rdi, implicit $edi, implicit-def $edi, implicit $di, implicit-def $di, implicit $dil, implicit-def $dil, implicit $dih, implicit-def $dih, implicit $hdi, implicit-def $hdi, implicit $rsi, implicit-def $rsi, implicit $esi, implicit-def $esi, implicit $si, implicit-def $si, implicit $sil, implicit-def $sil, implicit $sih, implicit-def $sih, implicit $hsi, implicit-def $hsi
 
   bb.1:
     successors: %bb.2, %bb.3
     liveins: $rax, $rsi
 
     CMP64ri8 $rax, 9, implicit-def $eflags
     JCC_1 %bb.3, 7, implicit $eflags
     JMP_1 %bb.2