[ExecutionDepsFix] Don't make copies of LiveReg objects when collecting operands for soft instructions

[craig.topper]

Summary

While collecting operands we make copies of the LiveReg objects which are stored in the LiveRegs array. If the instruction uses the same register multiple times we end up with multiple copies. Later we iterate through the collected list of LiveReg objects and merge DomainValues. In the process of doing this the merge function can change the contents of the original LiveReg object in the LiveRegs array, but not the copies that have been made. So when we get to the second usage of the register we end up seeing a stale copy of the LiveReg object.

To fix this I've stopped copying and now just store a pointer to the original LiveReg object. Another option might be to avoid adding the same register to the Regs array twice, but this approach seemed simpler.

The included test case from PR 30284 exposes this bug due to an AVX-512 masked OR instruction using the same register for the passthru operand and one of the inputs to the OR operation.

[myatsina]

I've seen some places that do SmallVector<std::unique_ptr<type>, size>. This might be a bit better as it states explicitly that there is no duplication in this data structure.

Another option is using SamllSetVector data structure and std::sort (instead of the sorted insertion section), but it will require to define a comparison operator for LiveReg.

[craig.topper]

Can't use SmallVector of std::unique_ptr on the vector I changed because then the vector would become the owner for these objects, but they need to be owned by the LiveRegs member variable not his local vector.

[RKSimon]

lib/CodeGen/ExecutionDepsFix.cpp

737 ↗

(On Diff #89319)

It looks like this code was reusing the same i variable name for the inner loop - change it if you can? Also, possibly replace with a for-range loop and just break on the insertion.

test/CodeGen/X86/pr30284.ll

5 ↗

(On Diff #89319)

I realise its a test case but is it worth cleaning this up - remove unnecessary metadata etc. ?

[craig.topper]

Address Simon's feedback.

I made the outer loop a range-based for loop and commited it in r296093.

I've replaced the sorted insert loop with std::upper_bound and vector::insert which should sort in the same way though std::upper_bound would do a binary search instead of the previous linear search.

[RKSimon]

LGTM

llvm/trunk/lib/CodeGen/ExecutionDepsFix.cpp

if (isPowerOf2_32(available)) {
     unsigned domain = countTrailingZeros(available);
     TII->setExecutionDomain(*mi, domain);
     visitHardInstr(mi, domain);
     return;
   }
 
   // Kill off any remaining uses that don't match available, and build a list of
   // incoming DomainValues that we want to merge.
-  SmallVector<LiveReg, 4> Regs;
+  SmallVector<const LiveReg *, 4> Regs;
   for (int rx : used) {
     assert(LiveRegs && "no space allocated for live registers");
     const LiveReg &LR = LiveRegs[rx];
     // This useless DomainValue could have been missed above.
     if (!LR.Value->getCommonDomains(available)) {
       kill(rx);
       continue;
     }
     // Sorted insertion.
-    bool Inserted = false;
-    for (SmallVectorImpl<LiveReg>::iterator i = Regs.begin(), e = Regs.end();
-           i != e && !Inserted; ++i) {
-      if (LR.Def < i->Def) {
-        Inserted = true;
-        Regs.insert(i, LR);
-      }
-    }
-    if (!Inserted)
-      Regs.push_back(LR);
+    auto I = std::upper_bound(Regs.begin(), Regs.end(), &LR,
+                              [](const LiveReg *LHS, const LiveReg *RHS) {
+                                return LHS->Def < RHS->Def;
+                              });
+    Regs.insert(I, &LR);
   }
 
   // doms are now sorted in order of appearance. Try to merge them all, giving
   // priority to the latest ones.
   DomainValue *dv = nullptr;
   while (!Regs.empty()) {
     if (!dv) {
-      dv = Regs.pop_back_val().Value;
+      dv = Regs.pop_back_val()->Value;
       // Force the first dv to match the current instruction.
       dv->AvailableDomains = dv->getCommonDomains(available);
       assert(dv->AvailableDomains && "Domain should have been filtered");
       continue;
     }
 
-    DomainValue *Latest = Regs.pop_back_val().Value;
+    DomainValue *Latest = Regs.pop_back_val()->Value;
     // Skip already merged values.
     if (Latest == dv || Latest->Next)
       continue;
     if (merge(dv, Latest))
       continue;
 
     // If latest didn't merge, it is useless now. Kill all registers using it.
     for (int i : used) {

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

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=i386-unknown-linux-gnu -mattr=avx512dq | FileCheck %s
+
+define void @f_f___un_3C_unf_3E_un_3C_unf_3E_() {
+; CHECK-LABEL: f_f___un_3C_unf_3E_un_3C_unf_3E_:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    vmovapd 0, %zmm0
+; CHECK-NEXT:    vmovapd 64, %zmm1
+; CHECK-NEXT:    vmovapd {{.*#+}} zmm2 = [0,16,0,16,0,16,0,16,0,16,0,16,0,16,0,16]
+; CHECK-NEXT:    vorpd %zmm2, %zmm0, %zmm0 {%k1}
+; CHECK-NEXT:    vorpd %zmm2, %zmm1, %zmm1 {%k1}
+; CHECK-NEXT:    vmovapd %zmm1, 64
+; CHECK-NEXT:    vmovapd %zmm0, 0
+; CHECK-NEXT:    retl
+  %a_load22 = load <16 x i64>, <16 x i64>* null, align 1
+  %bitop = or <16 x i64> %a_load22, <i64 68719476736, i64 68719476736, i64 68719476736, i64 68719476736, i64 68719476736, i64 68719476736, i64 68719476736, i64 68719476736, i64 68719476736, i64 68719476736, i64 68719476736, i64 68719476736, i64 68719476736, i64 68719476736, i64 68719476736, i64 68719476736>
+  %v.i = load <16 x i64>, <16 x i64>* null
+  %v1.i41 = select <16 x i1> undef, <16 x i64> %bitop, <16 x i64> %v.i
+  store <16 x i64> %v1.i41, <16 x i64>* null
+  ret void
+}