[MIScheduler] Slightly better handling of constrainLocalCopy when both source and dest are local

[mkuper]

Summary

This fixes PR21792 by handling an additional case in constrainLocalCopy.

This should probably be generalized, but I don't understand the code well enough to figure out how, yet.
Any suggestions on how to improve this are welcome.

[qcolombet]

Hi Michael,

I am not familiar with that code either but the current patch makes sense to me.
I leave the LGTM to Andy though.

Now looking for a generalization, I guess we could loop over all the local candidate and try to apply the transformation until we looked for all or one work.
I.e.,
Currently, we do:
pick a candidate
try apply

Your patch does:
pick a better candidate
try apply

The generalization would be:
for all candidate:

try apply
if success -> exit

Where the list of candidates is the local virtual registers.

Anyhow, Andy would have a much more educated answer.

Thanks,
-Quentin

[mkuper]

Andy, ping?

[atrick]

Thanks for the improvement!

Your test case comment lists an incorrect bug number: PR21972.

I'm not sure the logic makes sense to me. What if DstReg is local, and SrcReg is global, but a single interval? Now we'll just fail.

I don't think your example has any live intervals with "holes". I think you just wanted to change the bias from Local=DstReg to Local=SrcReg because the contraints will happen to work in that case.

I would avoid checking LI->size() == 1. I'm not sure it's really relevant. For example, two-address instructions may tie two segments together like this:
128B %vreg5<def,tied1> = SAR64ri %vreg5<tied0>, 32, %EFLAGS<imp-def,dead>; GR64_NOSP:%vreg5

I think you can just reverse the default global LI. It really looks like that's what I intended. I have no idea why I defaulted to SrcReg=Global. It may have just been messed up during code cleanup. I would try this:

+ If both the copy's source and dest are local live intervals, then we
+ should treat the dest as the global for the purpose of adding
+ // constraints. This adds edges from source's other uses to the copy.
+ unsigned LocalReg = SrcReg;
+ unsigned GlobalReg = DstReg;

If you do that, it looks like a trivial fix is needed in the widen_load-2.ll test.

[mkuper]

Thanks a lot, Andrew!

As I wrote on the PR, I don't fully understand the surrounding code.
One of the constraints is that the "global" LI has at least one segment after the one that contains the start of the "local" LI. So a "global" LI with exactly one segment will never satisfy it, right? That's the case that I was trying to kill.

Anyway, if you're sure that treating the dest as the "global" works in all cases, I'm perfectly ok with that as well. :-)

Michael

[mkuper]

Changed according to Andrew's suggestion.

[atrick]

LGTM

lib/CodeGen/MachineScheduler.cpp

void CopyConstrain::constrainLocalCopy(SUnit *CopySU, ScheduleDAGMILive *DAG) {
 
   unsigned DstReg = Copy->getOperand(0).getReg();
   if (!TargetRegisterInfo::isVirtualRegister(DstReg))
     return;
 
   // Check if either the dest or source is local. If it's live across a back
   // edge, it's not local. Note that if both vregs are live across the back
   // edge, we cannot successfully contrain the copy without cyclic scheduling.
+  // If both the source and the dest are local, make sure the part of the 
+  // "global" is played by a vreg that has at least one potential hole in
+  // its live interval.
   unsigned LocalReg = DstReg;
   unsigned GlobalReg = SrcReg;
   LiveInterval *LocalLI = &LIS->getInterval(LocalReg);
-  if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx)) {
+  LiveInterval *GlobalLI = &LIS->getInterval(GlobalReg);
+  if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx) || 
+       GlobalLI->size() == 1) {
     LocalReg = SrcReg;
     GlobalReg = DstReg;
     LocalLI = &LIS->getInterval(LocalReg);
     if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx))
       return;
+    GlobalLI = &LIS->getInterval(GlobalReg);
   }
-  LiveInterval *GlobalLI = &LIS->getInterval(GlobalReg);
 
   // Find the global segment after the start of the local LI.
   LiveInterval::iterator GlobalSegment = GlobalLI->find(LocalLI->beginIndex());
   // If GlobalLI does not overlap LocalLI->start, then a copy directly feeds a
   // local live range. We could create edges from other global uses to the local
   // start, but the coalescer should have already eliminated these cases, so
   // don't bother dealing with it.
   if (GlobalSegment == GlobalLI->end())

test/CodeGen/X86/pr21972.ll

+; RUN: llc -mtriple=x86_64-linux -mcpu=corei7 < %s | FileCheck %s
+; This fixes a missing cases in the MI scheduler's constrainLocalCopy exposed by
+; PR21972
+
+@stuff = external constant [256 x double], align 16
+
+define void @func(<4 x float> %vx) {
+entry:
+  %tmp2 = bitcast <4 x float> %vx to <2 x i64>
+  %and.i = and <2 x i64> %tmp2, <i64 8727373547504, i64 8727373547504>
+  %tmp3 = bitcast <2 x i64> %and.i to <4 x i32>
+  %index.sroa.0.0.vec.extract = extractelement <4 x i32> %tmp3, i32 0
+  %idx.ext = sext i32 %index.sroa.0.0.vec.extract to i64
+  %add.ptr = getelementptr inbounds i8* bitcast ([256 x double]* @stuff to i8*), i64 %idx.ext
+  %tmp4 = bitcast i8* %add.ptr to double*
+  %index.sroa.0.4.vec.extract = extractelement <4 x i32> %tmp3, i32 1
+  %idx.ext5 = sext i32 %index.sroa.0.4.vec.extract to i64
+  %add.ptr6 = getelementptr inbounds i8* bitcast ([256 x double]* @stuff to i8*), i64 %idx.ext5
+  %tmp5 = bitcast i8* %add.ptr6 to double*
+  %index.sroa.0.8.vec.extract = extractelement <4 x i32> %tmp3, i32 2
+  %idx.ext14 = sext i32 %index.sroa.0.8.vec.extract to i64
+  %add.ptr15 = getelementptr inbounds i8* bitcast ([256 x double]* @stuff to i8*), i64 %idx.ext14
+  %tmp6 = bitcast i8* %add.ptr15 to double*
+  %index.sroa.0.12.vec.extract = extractelement <4 x i32> %tmp3, i32 3
+  %idx.ext19 = sext i32 %index.sroa.0.12.vec.extract to i64
+  %add.ptr20 = getelementptr inbounds i8* bitcast ([256 x double]* @stuff to i8*), i64 %idx.ext19
+  %tmp7 = bitcast i8* %add.ptr20 to double*
+  %add.ptr46 = getelementptr inbounds i8* bitcast (double* getelementptr inbounds ([256 x double]* @stuff, i64 0, i64 1) to i8*), i64 %idx.ext
+  %tmp16 = bitcast i8* %add.ptr46 to double*
+  %add.ptr51 = getelementptr inbounds i8* bitcast (double* getelementptr inbounds ([256 x double]* @stuff, i64 0, i64 1) to i8*), i64 %idx.ext5
+  %tmp17 = bitcast i8* %add.ptr51 to double*
+  call void @toto(double* %tmp4, double* %tmp5, double* %tmp6, double* %tmp7, double* %tmp16, double* %tmp17)
+  ret void
+; CHECK-LABEL: func:
+; CHECK: pextrq  $1, %xmm0,
+; CHECK-NEXT: movd    %xmm0, %r[[AX:..]]
+; CHECK-NEXT: movslq  %e[[AX]],
+; CHECK-NEXT: sarq    $32, %r[[AX]]
+}
+
+declare void @toto(double*, double*, double*, double*, double*, double*)

test/CodeGen/X86/vector-idiv.ll

 ; SSE41-NEXT:    psrad $2, %xmm1
 ; SSE41-NEXT:    paddd %xmm0, %xmm1
 ; SSE41-NEXT:    movdqa %xmm1, %xmm0
 ; SSE41-NEXT:    retq
 ;
 ; SSE-LABEL: test8:
 ; SSE:       # BB#0:
 ; SSE-NEXT:    movdqa {{.*#+}} xmm2 = [2454267027,2454267027,2454267027,2454267027]
-; SSE-NEXT:    movdqa %xmm2, %xmm1
-; SSE-NEXT:    psrad $31, %xmm1
-; SSE-NEXT:    pand %xmm0, %xmm1
 ; SSE-NEXT:    movdqa %xmm0, %xmm3
 ; SSE-NEXT:    psrad $31, %xmm3
 ; SSE-NEXT:    pand %xmm2, %xmm3
-; SSE-NEXT:    paddd %xmm1, %xmm3
 ; SSE-NEXT:    movdqa %xmm0, %xmm1
 ; SSE-NEXT:    pmuludq %xmm2, %xmm1
-; SSE-NEXT:    pshufd {{.*#+}} xmm2 = xmm2[1,1,3,3]
-; SSE-NEXT:    pshufd {{.*#+}} xmm4 = xmm0[1,1,3,3]
-; SSE-NEXT:    pmuludq %xmm2, %xmm4
-; SSE-NEXT:    shufps {{.*#+}} xmm1 = xmm1[1,3],xmm4[1,3]
+; SSE-NEXT:    pshufd {{.*#+}} xmm4 = xmm2[1,1,3,3]
+; SSE-NEXT:    psrad $31, %xmm2
+; SSE-NEXT:    pand %xmm0, %xmm2
+; SSE-NEXT:    paddd %xmm2, %xmm3
+; SSE-NEXT:    pshufd {{.*#+}} xmm2 = xmm0[1,1,3,3]
+; SSE-NEXT:    pmuludq %xmm4, %xmm2
+; SSE-NEXT:    shufps {{.*#+}} xmm1 = xmm1[1,3],xmm2[1,3]
 ; SSE-NEXT:    shufps {{.*#+}} xmm1 = xmm1[0,2,1,3]
 ; SSE-NEXT:    psubd %xmm3, %xmm1
 ; SSE-NEXT:    paddd %xmm0, %xmm1
 ; SSE-NEXT:    movdqa %xmm1, %xmm0
 ; SSE-NEXT:    psrld $31, %xmm0
 ; SSE-NEXT:    psrad $2, %xmm1
 ; SSE-NEXT:    paddd %xmm0, %xmm1
 ; SSE-NEXT:    movdqa %xmm1, %xmm0