[TargetRegisterInfo] Remove temporary hook enableMultipleCopyHints()

[jonpa]

Summary

Finally, all targets are enabling multiple regalloc hints, so the hook to disable this can now be removed.

NFC.

[RKSimon]

Does this need a comment in the 8.00 release notes? What about RISVC/WASM since it looks like they're about to lose their experimental status?

[RKSimon]

This probably needs to wait until the compile time regressions have been addressed: https://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20180924/590785.html

[jonpa]

I think the recent discoveries of compile time regressions were due to multiple copy hints being added for the same register many times.

The CopyHint is inserted into a set, and I must have assumed that the hint weight would most likely be the same for the same physical register, and therefore there should only be one CopyHint per reg. This was not the case in the test case provided by Jonathan where a lot of hints were added, since this happens even with just a tiny difference in the float spill weight. This test case seemed to have thousands of small intervals for some phys regs, so in this case that meant a lot of hints for that register.

I updated the patch to make sure that the sorted set of CopyHints only has one hint per register. This is achieved by checking at insertion if the register already had a hint, and if so, remove that hint and insert the new one, if the new hint has a greater weight.

This luckily seems to be completely NFC, so all tests are still passing.

In fact, the temporary hack (which this patch removes) really should be removed since it is now clear that its ordering of the hints with the temporary CopyHintOrder++ method (for targets that do not enable), is also getting a lot of duplicated hints for the same register.

Possibly, I could first handle this issue with a patch without removing the target hook if there is any reason to do so. It seems however this is "general goodness" as Quentin pointed out earlier, so there shouldn't be any target desiring to not enable, right (in-trunk or not)?

[rupprecht]

In D52316#1249892, @RKSimon wrote:

This probably needs to wait until the compile time regressions have been addressed: https://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20180924/590785.html

I patched this in, and I'm no longer seeing compile time regressions at head.

[RKSimon]

@jonpa Please can you split this patch into 2 stages (the regression fix and the removal of enableMultipleCopyHints()).

[jonpa]

In D52316#1251615, @RKSimon wrote:

@jonpa Please can you split this patch into 2 stages (the regression fix and the removal of enableMultipleCopyHints()).

First part for the regression fix is now here: https://reviews.llvm.org/D52826

The actual handling is somewhat different now and should this time be correct.

[jonpa]

Updated patch to again just remove the enableMultipleCopyHints() hook.

[RKSimon]

LGTM - thanks

[jonpa]

Thanks for review!
r343851.

include/llvm/CodeGen/TargetRegisterInfo.h

public:
   /// e.g. On ARM, some virtual registers should target register pairs,
   /// if one of pair is coalesced to another register, the allocation hint of
   /// the other half of the pair should be changed to point to the new register.
   virtual void updateRegAllocHint(unsigned Reg, unsigned NewReg,
                                   MachineFunction &MF) const {
     // Do nothing.
   }
 
-  /// The creation of multiple copy hints have been implemented in
-  /// weightCalcHelper(), but since this affects so many tests for many
-  /// targets, this is temporarily disabled per default. THIS SHOULD BE
-  /// "GENERAL GOODNESS" and hopefully all targets will update their tests
-  /// and enable this soon. This hook should then be removed.
-  virtual bool enableMultipleCopyHints() const { return false; }
-
   /// Allow the target to reverse allocation order of local live ranges. This
   /// will generally allocate shorter local live ranges first. For targets with
   /// many registers, this could reduce regalloc compile time by a large
   /// factor. It is disabled by default for three reasons:
   /// (1) Top-down allocation is simpler and easier to debug for targets that
   /// don't benefit from reversing the order.
   /// (2) Bottom-up allocation could result in poor evicition decisions on some
   /// targets affecting the performance of compiled code.

lib/CodeGen/CalcSpillWeights.cpp

static unsigned copyHint(const MachineInstr *mi, unsigned reg,
 
   if (!hreg)
     return 0;
 
   if (TargetRegisterInfo::isVirtualRegister(hreg))
     return sub == hsub ? hreg : 0;
 
   const TargetRegisterClass *rc = mri.getRegClass(reg);
-  if (!tri.enableMultipleCopyHints()) {
-    // Only allow physreg hints in rc.
-    if (sub == 0)
-      return rc->contains(hreg) ? hreg : 0;
-
-    // reg:sub should match the physreg hreg.
-    return tri.getMatchingSuperReg(hreg, sub, rc);
-  }
-
   unsigned CopiedPReg = (hsub ? tri.getSubReg(hreg, hsub) : hreg);
   if (rc->contains(CopiedPReg))
     return CopiedPReg;
 
   // Check if reg:sub matches so that a super register could be hinted.
   if (sub)
     return tri.getMatchingSuperReg(CopiedPReg, sub, rc);
 
if (localSplitArtifact) {
     numInstr += 2;
   }
 
   // CopyHint is a sortable hint derived from a COPY instruction.
   struct CopyHint {
     unsigned Reg;
     float Weight;
     bool IsPhys;
-    unsigned HintOrder;
-    CopyHint(unsigned R, float W, bool P, unsigned HR) :
-      Reg(R), Weight(W), IsPhys(P), HintOrder(HR) {}
+    CopyHint(unsigned R, float W, bool P) :
+      Reg(R), Weight(W), IsPhys(P) {}
     bool operator<(const CopyHint &rhs) const {
+      if (Reg == rhs.Reg)
+        return false;
       // Always prefer any physreg hint.
       if (IsPhys != rhs.IsPhys)
         return (IsPhys && !rhs.IsPhys);
       if (Weight != rhs.Weight)
         return (Weight > rhs.Weight);
-
-      // This is just a temporary way to achive NFC for targets that don't
-      // enable multiple copy hints. HintOrder should be removed when all
-      // targets return true in enableMultipleCopyHints().
-      return (HintOrder < rhs.HintOrder);
-
-#if 0 // Should replace the HintOrder check, see above.
-      // (just for the purpose of maintaining the set)
-      return Reg < rhs.Reg;
-#endif
+      return Reg < rhs.Reg; // Tie-breaker.
     }
   };
   std::set<CopyHint> CopyHints;
 
-  // Temporary: see comment for HintOrder above.
-  unsigned CopyHintOrder = 0;
   for (MachineRegisterInfo::reg_instr_iterator
        I = mri.reg_instr_begin(li.reg), E = mri.reg_instr_end();
        I != E; ) {
     MachineInstr *mi = &*(I++);
 
     // For local split artifacts, we are interested only in instructions between
     // the expected start and end of the range.
     SlotIndex si = LIS.getInstructionIndex(*mi);
if (Spillable) {
       // Give extra weight to what looks like a loop induction variable update.
       if (writes && isExiting && LIS.isLiveOutOfMBB(li, mbb))
         weight *= 3;
 
       totalWeight += weight;
     }
 
     // Get allocation hints from copies.
-    if (!mi->isCopy() ||
-        (TargetHint.first != 0 && !tri.enableMultipleCopyHints()))
+    if (!mi->isCopy())
       continue;
     unsigned hint = copyHint(mi, li.reg, tri, mri);
     if (!hint)
       continue;
     // Force hweight onto the stack so that x86 doesn't add hidden precision,
     // making the comparison incorrectly pass (i.e., 1 > 1 == true??).
     //
     // FIXME: we probably shouldn't use floats at all.
     volatile float hweight = Hint[hint] += weight;
-    if (TargetRegisterInfo::isVirtualRegister(hint) || mri.isAllocatable(hint))
-      CopyHints.insert(CopyHint(hint, hweight, tri.isPhysicalRegister(hint),
-                     (tri.enableMultipleCopyHints() ? hint : CopyHintOrder++)));
+    if (TargetRegisterInfo::isVirtualRegister(hint) || mri.isAllocatable(hint)){
+      CopyHint NewHint(hint, hweight, tri.isPhysicalRegister(hint));
+      std::pair<std::set<CopyHint>::iterator, bool> Ret =
+        CopyHints.insert(NewHint);
+      if (Ret.second == false && hweight > Ret.first->Weight) {
+        // Reg has a new hint with greater weight: reinsert it.
+        CopyHints.erase(Ret.first);
+        CopyHints.insert(NewHint);
+      }
+    }
   }
 
   Hint.clear();
 
   // Pass all the sorted copy hints to mri.
   if (updateLI && CopyHints.size()) {
     // Remove a generic hint if previously added by target.
     if (TargetHint.first == 0 && TargetHint.second)
       mri.clearSimpleHint(li.reg);
 
     for (auto &Hint : CopyHints) {
       if (TargetHint.first != 0 && Hint.Reg == TargetHint.second)
         // Don't add again the target-type hint.
         continue;
       mri.addRegAllocationHint(li.reg, Hint.Reg);
-      if (!tri.enableMultipleCopyHints())
-        break;
     }
 
     // Weakly boost the spill weight of hinted registers.
     totalWeight *= 1.01F;
   }
 
   // If the live interval was already unspillable, leave it that way.
   if (!Spillable)

lib/Target/AArch64/AArch64RegisterInfo.h

bool isAsmClobberable(const MachineFunction &MF,
                        unsigned PhysReg) const override;
   bool isConstantPhysReg(unsigned PhysReg) const override;
   const TargetRegisterClass *
   getPointerRegClass(const MachineFunction &MF,
                      unsigned Kind = 0) const override;
   const TargetRegisterClass *
   getCrossCopyRegClass(const TargetRegisterClass *RC) const override;
 
-  bool enableMultipleCopyHints() const override { return true; }
-
   bool requiresRegisterScavenging(const MachineFunction &MF) const override;
   bool useFPForScavengingIndex(const MachineFunction &MF) const override;
   bool requiresFrameIndexScavenging(const MachineFunction &MF) const override;
 
   bool needsFrameBaseReg(MachineInstr *MI, int64_t Offset) const override;
   bool isFrameOffsetLegal(const MachineInstr *MI, unsigned BaseReg,
                           int64_t Offset) const override;
   void materializeFrameBaseRegister(MachineBasicBlock *MBB, unsigned BaseReg,

lib/Target/AMDGPU/AMDGPURegisterInfo.h

 namespace llvm {
 
 class GCNSubtarget;
 class TargetInstrInfo;
 
 struct AMDGPURegisterInfo : public AMDGPUGenRegisterInfo {
   AMDGPURegisterInfo();
 
-  bool enableMultipleCopyHints() const override { return true; }
-
   /// \returns the sub reg enum value for the given \p Channel
   /// (e.g. getSubRegFromChannel(0) -> AMDGPU::sub0)
   static unsigned getSubRegFromChannel(unsigned Channel);
 
   void reserveRegisterTuples(BitVector &, unsigned Reg) const;
 };
 
 } // End namespace llvm
 
 #endif

lib/Target/ARM/ARMBaseRegisterInfo.h

bool getRegAllocationHints(unsigned VirtReg,
                              ArrayRef<MCPhysReg> Order,
                              SmallVectorImpl<MCPhysReg> &Hints,
                              const MachineFunction &MF,
                              const VirtRegMap *VRM,
                              const LiveRegMatrix *Matrix) const override;
 
   void updateRegAllocHint(unsigned Reg, unsigned NewReg,
                           MachineFunction &MF) const override;
-  bool enableMultipleCopyHints() const override { return true; }
 
   bool hasBasePointer(const MachineFunction &MF) const;
 
   bool canRealignStack(const MachineFunction &MF) const override;
   int64_t getFrameIndexInstrOffset(const MachineInstr *MI,
                                    int Idx) const override;
   bool needsFrameBaseReg(MachineInstr *MI, int64_t Offset) const override;
   void materializeFrameBaseRegister(MachineBasicBlock *MBB,

lib/Target/BPF/BPFRegisterInfo.h

 struct BPFRegisterInfo : public BPFGenRegisterInfo {
 
   BPFRegisterInfo();
 
   const MCPhysReg *getCalleeSavedRegs(const MachineFunction *MF) const override;
 
   BitVector getReservedRegs(const MachineFunction &MF) const override;
 
-  bool enableMultipleCopyHints() const override { return true; }
-
   void eliminateFrameIndex(MachineBasicBlock::iterator MI, int SPAdj,
                            unsigned FIOperandNum,
                            RegScavenger *RS = nullptr) const override;
 
   unsigned getFrameRegister(const MachineFunction &MF) const override;
 };
 }
 
 #endif

lib/Target/Hexagon/HexagonRegisterInfo.h

public:
   /// Code Generation virtual methods...
   const MCPhysReg *getCalleeSavedRegs(const MachineFunction *MF)
         const override;
   const uint32_t *getCallPreservedMask(const MachineFunction &MF,
         CallingConv::ID) const override;
 
   BitVector getReservedRegs(const MachineFunction &MF) const override;
 
-  bool enableMultipleCopyHints() const override { return true; }
-
   void eliminateFrameIndex(MachineBasicBlock::iterator II, int SPAdj,
         unsigned FIOperandNum, RegScavenger *RS = nullptr) const override;
 
   /// Returns true since we may need scavenging for a temporary register
   /// when generating hardware loop instructions.
   bool requiresRegisterScavenging(const MachineFunction &MF) const override {
     return true;
   }

lib/Target/Mips/MipsRegisterInfo.h

unsigned getRegPressureLimit(const TargetRegisterClass *RC,
                                MachineFunction &MF) const override;
   const MCPhysReg *getCalleeSavedRegs(const MachineFunction *MF) const override;
   const uint32_t *getCallPreservedMask(const MachineFunction &MF,
                                        CallingConv::ID) const override;
   static const uint32_t *getMips16RetHelperMask();
 
   BitVector getReservedRegs(const MachineFunction &MF) const override;
 
-  bool enableMultipleCopyHints() const override { return true; }
-
   bool requiresRegisterScavenging(const MachineFunction &MF) const override;
 
   bool trackLivenessAfterRegAlloc(const MachineFunction &MF) const override;
 
   /// Stack Frame Processing Methods
   void eliminateFrameIndex(MachineBasicBlock::iterator II,
                            int SPAdj, unsigned FIOperandNum,
                            RegScavenger *RS = nullptr) const override;

lib/Target/PowerPC/PPCRegisterInfo.h

const uint32_t *getCallPreservedMask(const MachineFunction &MF,
                                        CallingConv::ID CC) const override;
   const uint32_t *getNoPreservedMask() const override;
 
   void adjustStackMapLiveOutMask(uint32_t *Mask) const override;
 
   BitVector getReservedRegs(const MachineFunction &MF) const override;
   bool isCallerPreservedPhysReg(unsigned PhysReg, const MachineFunction &MF) const override;
 
-  bool enableMultipleCopyHints() const override { return true; }
-
   /// We require the register scavenger.
   bool requiresRegisterScavenging(const MachineFunction &MF) const override {
     return true;
   }
 
   bool requiresFrameIndexScavenging(const MachineFunction &MF) const override {
     return true;
   }

lib/Target/Sparc/SparcRegisterInfo.h

struct SparcRegisterInfo : public SparcGenRegisterInfo {
 
   const uint32_t* getRTCallPreservedMask(CallingConv::ID CC) const;
 
   BitVector getReservedRegs(const MachineFunction &MF) const override;
 
   const TargetRegisterClass *getPointerRegClass(const MachineFunction &MF,
                                                 unsigned Kind) const override;
 
-  bool enableMultipleCopyHints() const override { return true; }
-
   void eliminateFrameIndex(MachineBasicBlock::iterator II,
                            int SPAdj, unsigned FIOperandNum,
                            RegScavenger *RS = nullptr) const override;
 
   unsigned getFrameRegister(const MachineFunction &MF) const override;
 
   bool canRealignStack(const MachineFunction &MF) const override;
 
 };
 
 } // end namespace llvm
 
 #endif

lib/Target/SystemZ/SystemZRegisterInfo.h

public:
 
   bool getRegAllocationHints(unsigned VirtReg,
                              ArrayRef<MCPhysReg> Order,
                              SmallVectorImpl<MCPhysReg> &Hints,
                              const MachineFunction &MF,
                              const VirtRegMap *VRM,
                              const LiveRegMatrix *Matrix) const override;
 
-  bool enableMultipleCopyHints() const override { return true; }
-
   // Override TargetRegisterInfo.h.
   bool requiresRegisterScavenging(const MachineFunction &MF) const override {
     return true;
   }
   bool requiresFrameIndexScavenging(const MachineFunction &MF) const override {
     return true;
   }
   bool trackLivenessAfterRegAlloc(const MachineFunction &MF) const override {

lib/Target/X86/X86RegisterInfo.h

public:
   /// getGPRsForTailCall - Returns a register class with registers that can be
   /// used in forming tail calls.
   const TargetRegisterClass *
   getGPRsForTailCall(const MachineFunction &MF) const;
 
   unsigned getRegPressureLimit(const TargetRegisterClass *RC,
                                MachineFunction &MF) const override;
 
-  bool enableMultipleCopyHints() const override { return true; }
-
   /// getCalleeSavedRegs - Return a null-terminated list of all of the
   /// callee-save registers on this target.
   const MCPhysReg *
   getCalleeSavedRegs(const MachineFunction* MF) const override;
   const MCPhysReg *
   getCalleeSavedRegsViaCopy(const MachineFunction *MF) const;
   const uint32_t *getCallPreservedMask(const MachineFunction &MF,
                                        CallingConv::ID) const override;

lib/Target/XCore/XCoreRegisterInfo.h

public:
   XCoreRegisterInfo();
 
   /// Code Generation virtual methods...
 
   const MCPhysReg *getCalleeSavedRegs(const MachineFunction *MF) const override;
 
   BitVector getReservedRegs(const MachineFunction &MF) const override;
 
-  bool enableMultipleCopyHints() const override { return true; }
-
   bool requiresRegisterScavenging(const MachineFunction &MF) const override;
 
   bool trackLivenessAfterRegAlloc(const MachineFunction &MF) const override;
 
   bool useFPForScavengingIndex(const MachineFunction &MF) const override;
 
   void eliminateFrameIndex(MachineBasicBlock::iterator II,
                            int SPAdj, unsigned FIOperandNum,