[RegAlloc] CalcSpillWeights: Fix infinite loop

[timshen]

Summary

isRematerializable() doesn't have to check the same VNInfo for twice, since it doesn't mutate anything. With this it can handle circles.

There is no functional change.

[timshen]

Hmmm...not sure why llvm-commits is not publishing this. Test test.

[qcolombet]

Hi Tim,

Do you actually have a test case for that?

Since we bail out on PHIs, I do not see how you can have a loop here.

Cheers,
-Quentin

[timshen]

Attached reduced test case.

Sorry, I also found that this change is wrong. I thought it works but I forgot to turn on assertion. This test case triggers an assertion failure with this change. I will do more investigation.

[qcolombet]

Thanks for the update.

If you need help narrowing that down, please file a PR with the symptoms and how to reproduce.

Cheers,
Q.

[timshen]

Never mind, I turned on -verify-machineinstrs and it shows a bug in a previous pass.

lib/CodeGen/CalcSpillWeights.cpp

static unsigned copyHint(const MachineInstr *mi, unsigned reg,
   if (sub == 0)
     return rc->contains(hreg) ? hreg : 0;
 
   // reg:sub should match the physreg hreg.
   return tri.getMatchingSuperReg(hreg, sub, rc);
 }
 
 // Check if all values in LI are rematerializable
-static bool isRematerializable(const LiveInterval &LI,
-                               const LiveIntervals &LIS,
-                               VirtRegMap *VRM,
+static bool isRematerializable(const LiveInterval &LI, const LiveIntervals &LIS,
+                               const VirtRegMap *VRM,
                                const TargetInstrInfo &TII) {
   unsigned Reg = LI.reg;
   unsigned Original = VRM ? VRM->getOriginal(Reg) : 0;
+  SmallPtrSet<const VNInfo *, 4> Visited;
   for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
        I != E; ++I) {
     const VNInfo *VNI = *I;
     if (VNI->isUnused())
       continue;
     if (VNI->isPHIDef())
       return false;
 
if (VRM) {
         if (!TargetRegisterInfo::isVirtualRegister(Reg) ||
             VRM->getOriginal(Reg) != Original)
           return false;
 
         // Follow the copy live-in value.
         const LiveInterval &SrcLI = LIS.getInterval(Reg);
         LiveQueryResult SrcQ = SrcLI.Query(VNI->def);
         VNI = SrcQ.valueIn();
+        if (!Visited.insert(VNI).second)
+          break;
         assert(VNI && "Copy from non-existing value");
         if (VNI->isPHIDef())
           return false;
         MI = LIS.getInstructionFromIndex(VNI->def);
         assert(MI && "Dead valno in interval");
       }
     }
 

test/CodeGen/PowerPC/calc-spill-weight-circle.ll

+; RUN: llc < %s | FileCheck %s
+; CHECK-LABEL: TestFoo
+target triple = "powerpc64le-unknown-linux-gnu"
+
+declare double @sqrt(double)
+
+declare double @cos(double)
+
+declare <2 x double> @llvm.fma.v2f64(<2 x double>, <2 x double>, <2 x double>)
+
+define void @TestFoo() {
+bb3:
+  %tmp = load <2 x double>, <2 x double>* undef
+  %tmp4 = fsub <2 x double> zeroinitializer, undef
+  %tmp5 = fsub <2 x double> zeroinitializer, undef
+  %tmp6 = call <2 x double> @llvm.fma.v2f64(<2 x double> undef, <2 x double> undef, <2 x double> %tmp)
+  %tmp7 = fsub <2 x double> %tmp4, %tmp6
+  %tmp8 = call <2 x double> @llvm.fma.v2f64(<2 x double> %tmp7, <2 x double> undef, <2 x double> %tmp)
+  %tmp9 = call <2 x double> @llvm.fma.v2f64(<2 x double> undef, <2 x double> undef, <2 x double> %tmp)
+  %tmp10 = fsub <2 x double> %tmp5, %tmp9
+  %tmp11 = call <2 x double> @llvm.fma.v2f64(<2 x double> %tmp10, <2 x double> undef, <2 x double> %tmp)
+  %tmp12 = load <2 x double>, <2 x double>* undef
+  %tmp13 = call <2 x double> @llvm.fma.v2f64(<2 x double> undef, <2 x double> zeroinitializer, <2 x double> %tmp12)
+  br i1 undef, label %bb23, label %bb24
+
+bb15:
+  %tmp16 = call double @cos(double undef)
+  %tmp17 = call <2 x double> @llvm.fma.v2f64(<2 x double> %tmp11, <2 x double> undef, <2 x double> undef)
+  %tmp18 = fadd <2 x double> %tmp17, undef
+  %tmp19 = fsub <2 x double> %tmp18, undef
+  %tmp20 = call <2 x double> @llvm.fma.v2f64(<2 x double> %tmp19, <2 x double> undef, <2 x double> undef)
+  store <2 x double> %tmp20, <2 x double>* undef
+  %tmp21 = fsub <2 x double> %tmp13, undef
+  %tmp22 = call <2 x double> @llvm.fma.v2f64(<2 x double> %tmp21, <2 x double> undef, <2 x double> undef)
+  store <2 x double> %tmp22, <2 x double>* undef
+  ret void
+
+bb23:
+  %exitcond.i.i.i16.i = icmp eq i32 undef, 10
+  br i1 %exitcond.i.i.i16.i, label %bb15, label %bb23
+
+bb24:
+  %tmp25 = call double @sqrt(double undef)
+  %tmp26 = fsub <2 x double> %tmp8, undef
+  %tmp27 = call <2 x double> @llvm.fma.v2f64(<2 x double> %tmp26, <2 x double> undef, <2 x double> undef)
+  store <2 x double> %tmp27, <2 x double>* undef
+  ret void
+}