Fix backtracking of instruction scheduling (pre-RA-sched)

[chfast]

Summary

This patch fixes a bug in instruction scheduling backtracking code.
https://llvm.org/bugs/show_bug.cgi?id=22304

It can happen (by line CurSU->isPending = true; // This SU is not in AvailableQueue right now.) that a SUnit is mark as available but is not in the AvailableQueue. For SUnit being selected for scheduling both conditions must be met.

This patch mainly defensively protects from invalid removing a node from a queue. For noob like be this isAvailable flag and being in the AvailableQueue decoherence is annoying but maybe I don't have a full picture. I tried to synchronize that but it breaks the whole scheduling algorithm.

[chfast]

Tests added.

[qcolombet]

+Andy.

[atrick]

That looks like the right fix. Please add some CHECK lines to the test to at least verify that llc is running on each function, even though you can't directly test this code path.

[chfast]

CHECKs added to test, they check only function names as it is generic codegen test.
I also added separated llc runs for every scheduler available. Is that ok or it will not work on some other targets?

[atrick]

I already accepted this. But it isn't clear to my why each CHECK-LABEL is followed by a CHECK on the same string.

[chfast]

I removed unnecessary CHECKs from the test.

If you are happy with the patch, can you submit for me?

[atrick]

Author: Andrew Trick <[e-mail]>
Date: Thu Mar 26 20:44:13 2015

Fix a bug in SelectionDAG scheduling backtracking code: PR22304.

It can happen (by line CurSU->isPending = true; // This SU is not in
AvailableQueue right now.) that a SUnit is mark as available but is
not in the AvailableQueue. For SUnit being selected for scheduling
both conditions must be met.

This patch mainly defensively protects from invalid removing a node
from a queue. Sometimes nodes are marked isAvailable but are not in
the queue because they have been defered due to some hazard.

Patch by Pawel Bylica!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@233351 91177308-0d34-0410-b5e6-96231b3b80d8

lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

if (!WillCreateCycle(TrySU, BtSU))  {
           AvailableQueue->remove(BtSU);
       }
       DEBUG(dbgs() << "ARTIFICIAL edge from SU(" << BtSU->NodeNum << ") to SU("
             << TrySU->NodeNum << ")\n");
       AddPred(TrySU, SDep(BtSU, SDep::Artificial));
 
       // If one or more successors has been unscheduled, then the current
       // node is no longer available.
-      if (!TrySU->isAvailable)
+      if (!TrySU->isAvailable || !TrySU->NodeQueueId)
         CurSU = AvailableQueue->pop();
       else {
+        // Available and in AvailableQueue
         AvailableQueue->remove(TrySU);
         CurSU = TrySU;
       }
       // Interferences has been mutated. We must break.
       break;
     }
   }
 

test/CodeGen/Generic/scheduler-backtracking.ll

+; RUN: llc < %s -pre-RA-sched=list-ilp    | FileCheck %s
+; RUN: llc < %s -pre-RA-sched=list-hybrid | FileCheck %s
+; RUN: llc < %s -pre-RA-sched=source      | FileCheck %s
+; RUN: llc < %s -pre-RA-sched=list-burr   | FileCheck %s
+; RUN: llc < %s -pre-RA-sched=linearize   | FileCheck %s
+
+; PR22304 https://llvm.org/bugs/show_bug.cgi?id=22304
+; Tests checking backtracking in source scheduler. llc used to crash on them.
+
+; CHECK-LABEL: test1
+; CHECK: test1
+define i256 @test1(i256 %a) {
+  %b = add i256 %a, 1 
+  %m = shl i256 %b, 1
+  %p = add i256 %m, 1
+  %v = lshr i256 %b, %p
+  %t = trunc i256 %v to i1
+  %c = shl i256 1, %p
+  %f = select i1 %t, i256 undef, i256 %c
+  ret i256 %f
+}
+
+; CHECK-LABEL: test2
+; CHECK: test2
+define i256 @test2(i256 %a) {
+  %b = sub i256 0, %a
+  %c = and i256 %b, %a
+  %d = call i256 @llvm.ctlz.i256(i256 %c, i1 false)
+  ret i256 %d
+}
+
+; CHECK-LABEL: test3
+; CHECK: test3
+define i256 @test3(i256 %n) {
+  %m = sub i256 -1, %n
+  %x = sub i256 0, %n
+  %y = and i256 %x, %m
+  %z = call i256 @llvm.ctlz.i256(i256 %y, i1 false)
+  ret i256 %z
+}
+
+declare i256 @llvm.ctlz.i256(i256, i1) nounwind readnone
+
+; CHECK-LABEL: test4
+; CHECK: test4
+define i64 @test4(i64 %a, i64 %b) {
+  %r = zext i64 %b to i256
+  %u = add i256 %r, 1
+  %w = and i256 %u, 1461501637330902918203684832716283019655932542975
+  %x = zext i64 %a to i256
+  %c = icmp uge i256 %w, %x
+  %y = select i1 %c, i64 0, i64 1
+  %z = add i64 %y, 1
+  ret i64 %z
+}