Make TwoAddressInstructionPass::rescheduleMIBelowKill subreg-aware

[mkuper]

Summary

This fixes PR28824

I'm mostly wondering if we already have something like regOverlapsSet() around.
I couldn't find one, but it sounds like it ought to exist.

(The registers in the test are explicit on purpose - for the mov, ecx is ABI-mandated, and for the shift, it's a special instruction form that we want to be using.)

[majnemer]

lib/CodeGen/TwoAddressInstructionPass.cpp

545 ↗

(On Diff #66990)

Formatting.

[mkuper]

Thanks David, will fix the formatting!
What I'd really like, though, is to get rid of that function entirely - assuming there's something like this hiding somewhere else in the codebase. :-)

[MatzeB]

I guess you can use a SmallVector now if all you do is iterating over all elements of the container.

[mkuper]

In D23220#512070, @MatzeB wrote:

I guess you can use a SmallVector now if all you do is iterating over all elements of the container.

I guess you're right. I left it as a set to avoid duplicates, but we shouldn't have those anyway, at least not in the common case.

[MatzeB]

LGTM with a change to SmallVector.

[MatzeB]

In D23220#512075, @mkuper wrote:

In D23220#512070, @MatzeB wrote:

I guess you can use a SmallVector now if all you do is iterating over all elements of the container.

I guess you're right. I left it as a set to avoid duplicates, but we shouldn't have those anyway, at least not in the common case.

There can be duplicates, but they shouldn't hurt. And it is probably more expensive to filter out the duplicates than just checking a register twice in the few cases where we actually have a duplicate.

[mkuper]

Right, will change it to a SmallVector.
Thanks!

llvm/trunk/lib/CodeGen/TwoAddressInstructionPass.cpp

 //
 // It is also worth noting that the duplicate operand of the two
 // address instruction is removed.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"

 regsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI) {
   if (RegA == RegB)
     return true;
   if (!RegA || !RegB)
     return false;
   return TRI->regsOverlap(RegA, RegB);
 }
 
+// Returns true if Reg is equal or aliased to at least one register in Set.
+static bool regOverlapsSet(const SmallVectorImpl<unsigned> &Set, unsigned Reg,
+                           const TargetRegisterInfo *TRI) {
+  for (unsigned R : Set)
+    if (TRI->regsOverlap(R, Reg))
+      return true;
+
+  return false;
+}
+
 /// Return true if it's potentially profitable to commute the two-address
 /// instruction that's being processed.
 bool
 TwoAddressInstructionPass::
 isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC,
                       MachineInstr *MI, unsigned Dist) {
   if (OptLevel == CodeGenOpt::None)
     return false;
rescheduleMIBelowKill(MachineBasicBlock::iterator &mi,
   bool SeenStore = true;
   if (!MI->isSafeToMove(AA, SeenStore))
     return false;
 
   if (TII->getInstrLatency(InstrItins, *MI) > 1)
     // FIXME: Needs more sophisticated heuristics.
     return false;
 
-  SmallSet<unsigned, 2> Uses;
-  SmallSet<unsigned, 2> Kills;
-  SmallSet<unsigned, 2> Defs;
+  SmallVector<unsigned, 2> Uses;
+  SmallVector<unsigned, 2> Kills;
+  SmallVector<unsigned, 2> Defs;
   for (const MachineOperand &MO : MI->operands()) {
     if (!MO.isReg())
       continue;
     unsigned MOReg = MO.getReg();
     if (!MOReg)
       continue;
     if (MO.isDef())
-      Defs.insert(MOReg);
+      Defs.push_back(MOReg);
     else {
-      Uses.insert(MOReg);
+      Uses.push_back(MOReg);
       if (MOReg != Reg && (MO.isKill() ||
                            (LIS && isPlainlyKilled(MI, MOReg, LIS))))
-        Kills.insert(MOReg);
+        Kills.push_back(MOReg);
     }
   }
 
   // Move the copies connected to MI down as well.
   MachineBasicBlock::iterator Begin = MI;
   MachineBasicBlock::iterator AfterMI = std::next(Begin);
 
   MachineBasicBlock::iterator End = AfterMI;
-  while (End->isCopy() && Defs.count(End->getOperand(1).getReg())) {
-    Defs.insert(End->getOperand(0).getReg());
+  while (End->isCopy() &&
+         regOverlapsSet(Defs, End->getOperand(1).getReg(), TRI)) {
+    Defs.push_back(End->getOperand(0).getReg());
     ++End;
   }
 
   // Check if the reschedule will not break depedencies.
   unsigned NumVisited = 0;
   MachineBasicBlock::iterator KillPos = KillMI;
   ++KillPos;
   for (MachineInstr &OtherMI : llvm::make_range(End, KillPos)) {
if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() ||
       return false;
     for (const MachineOperand &MO : OtherMI.operands()) {
       if (!MO.isReg())
         continue;
       unsigned MOReg = MO.getReg();
       if (!MOReg)
         continue;
       if (MO.isDef()) {
-        if (Uses.count(MOReg))
+        if (regOverlapsSet(Uses, MOReg, TRI))
           // Physical register use would be clobbered.
           return false;
-        if (!MO.isDead() && Defs.count(MOReg))
+        if (!MO.isDead() && regOverlapsSet(Defs, MOReg, TRI))
           // May clobber a physical register def.
           // FIXME: This may be too conservative. It's ok if the instruction
           // is sunken completely below the use.
           return false;
       } else {
-        if (Defs.count(MOReg))
+        if (regOverlapsSet(Defs, MOReg, TRI))
           return false;
         bool isKill =
             MO.isKill() || (LIS && isPlainlyKilled(&OtherMI, MOReg, LIS));
-        if (MOReg != Reg &&
-            ((isKill && Uses.count(MOReg)) || Kills.count(MOReg)))
+        if (MOReg != Reg && ((isKill && regOverlapsSet(Uses, MOReg, TRI)) ||
+                             regOverlapsSet(Kills, MOReg, TRI)))
           // Don't want to extend other live ranges and update kills.
           return false;
         if (MOReg == Reg && !isKill)
           // We can't schedule across a use of the register in question.
           return false;
         // Ensure that if this is register in question, its the kill we expect.
         assert((MOReg != Reg || &OtherMI == KillMI) &&
                "Found multiple kills of a register in a basic block");

llvm/trunk/test/CodeGen/X86/pr28824.ll

+; RUN: llc < %s -mtriple=i386-unknown-linux-gnu | FileCheck %s
+
+@d = global i32 0, align 4
+
+; Verify the sar happens before ecx is clobbered with the parameter being
+; passed to fn3
+; CHECK-LABEL: fn4
+; CHECK: movb d, %cl
+; CHECK: sarl %cl
+; CHECK: movl $2, %ecx
+define i32 @fn4(i32 %i) #0 {
+entry:
+  %0 = load i32, i32* @d, align 4
+  %shr = ashr i32 %i, %0
+  tail call fastcc void @fn3(i32 2, i32 5, i32 %shr, i32 %i)
+  %cmp = icmp slt i32 %shr, 1
+  %. = zext i1 %cmp to i32
+  ret i32 %.
+}
+
+declare void @fn3(i32 %p1, i32 %p2, i32 %p3, i32 %p4) #0
+
+attributes #0 = { nounwind }