[X86]: Adding a new priority function 'guided-src' for Scheduler DAG instruction scheduling.

[jbhateja]

Summary

Following analysis is in context to bug# 33362 related to instruction scheduling.

1/ PRE-RA scheduler DAG based Instruction Scheduling algorithm which scans instruction bottom up

by default picks instruction as per source order(default) from the available
instructions to be scheduled in next cycle.
Of course  instructions are available in the priority queue only after they
have satisfied precedence and resource constraints.

Thus LZCNT64rr <second_argument> which corresponds to  following IR
   %4 = tail call i64 @llvm.ctlz.i64(i64 %1, i1 false)    <-- SWAP

is scheduled later (remember algorithm works bottom-up so final schedule
    is reverse order of instructions which algo produces.)

2/ Peephole optimizer which kicks in later down the pipeline could fold the TEST

with CMPNE to produce CMPAE in first case (clz_i128) as LZCNT operating on first
argument was adjacent to TEST instruction and both are EFLAGS reg defining MIs.

3/ In second function(clz_i128_swap) due to swapping of llvm.ctlz LZCNT operating

on first argument of function is no longer adjacent to TEST due to reason
mentioned in Point 1/. Which is why flag folding could not happen.

Adding a priority function based on heuristic which takes into
consideration already scheduled instruction which share their operands with
the next instruction to be chosen from from the available queue
under option -pre-RA-sched=guided-src. Fall back priority selection is source order.

This case works, share your thoughts on this and what could be a better heuristic.

[jbhateja]

ping @reviewers

[RKSimon]

I'll leave the scheduler part of the review to someone who understands it better!

include/llvm/CodeGen/SchedulerRegistry.h

64

Fix this comment for createGuidedSrcListDAGScheduler

lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

2614

(style) Put Weight += 10; on a newline.

test/CodeGen/X86/guided_sched.ll

3

Drop the avx2/skx requirements - you should be able to just use -mattr=+lzcnt

[jbhateja]

• Merge branch 'master' of https://github.com/llvm-mirror/llvm

Review comments from RKSimon

[jbhateja]

@Reviewers , kindly drop in your comments if any.

Thanks

[jbhateja]

@Reviewers , kindly drop in your comments if any.

[filcab]

lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

58

This should have a space, otherwise when concatenating the strings we end up with backson.

[jbhateja]

Change for better formatting.

[jbhateja]

Ping @ reviewers

[jbhateja]

Ping @ reviewers.

[RKSimon]

I'm not a scheduler expert so I don't think I can approve this. I have an additional concern - you've added a new scheduler just for one bug - will it ever get used?

[jbhateja]

In D34596#827110, @RKSimon wrote:

I'm not a scheduler expert so I don't think I can approve this. I have an additional concern - you've added a new scheduler just for one bug - will it ever get used?

This is not a new sheduler , its a new priority selector, we have several priority selectors like source order based, bottom up register reduction, hybrid . These priority selector pick the next instruction to be scheduled in the next cycle out of available candidates.

This new priority selector adds another heuristic which is to pick the instruction out of ready to schdule list whose operands have already been scheduled.

It will extend the list of already existing priority selectors which user can select using -pre-RA-sched option.

Thanks

[jbhateja]

• Merge branch 'master' of https://github.com/llvm-mirror/llvm
• Extending guided-src priority function to cover more case.

[MatzeB]

Sorry about this review stalling. To give at least some feedback:

• We generally want to phase out the SelectionDAG schedulers and only have them do a minimal amount of work. The actual scheduling should happen in the MachineScheduler. So ideally we would not add new features here. (That said I can see why you are doing it here: the MachineScheduler currently does not reorder flags producers/users)
• I believe none of the currently active LLVM developers is really familiar with the SelectionDAG schedulers.

I will try to find time for an actual review soon (otherwise please keep pinging).

[jbhateja]

In D34596#882578, @MatzeB wrote:

Sorry about this review stalling. To give at least some feedback:

• We generally want to phase out the SelectionDAG schedulers and only have them do a minimal amount of work. The actual scheduling should happen in the MachineScheduler. So ideally we would not add new features here. (That said I can see why you are doing it here: the MachineScheduler currently does not reorder flags producers/users)
• I believe none of the currently active LLVM developers is really familiar with the SelectionDAG schedulers.

I will try to find time for an actual review soon (otherwise please keep pinging).

Thanks Matze, I undertand your point here.

include/llvm/CodeGen/SchedulerRegistry.h

public:
   }
 };
 
 /// createBURRListDAGScheduler - This creates a bottom up register usage
 /// reduction list scheduler.
 ScheduleDAGSDNodes *createBURRListDAGScheduler(SelectionDAGISel *IS,
                                                CodeGenOpt::Level OptLevel);
 
 /// createBURRListDAGScheduler - This creates a bottom up list scheduler that
 /// schedules nodes in source code order when possible.
+ScheduleDAGSDNodes *createGuidedSrcListDAGScheduler(SelectionDAGISel *IS,
+                                                 CodeGenOpt::Level OptLevel);
+
+
+/// createBURRListDAGScheduler - This creates a bottom up list scheduler that
+/// schedules nodes in source code order when possible.
 ScheduleDAGSDNodes *createSourceListDAGScheduler(SelectionDAGISel *IS,
                                                  CodeGenOpt::Level OptLevel);
 
 /// createHybridListDAGScheduler - This creates a bottom up register pressure
 /// aware list scheduler that make use of latency information to avoid stalls
 /// for long latency instructions in low register pressure mode. In high
 /// register pressure mode it schedules to reduce register pressure.
 ScheduleDAGSDNodes *createHybridListDAGScheduler(SelectionDAGISel *IS,

lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

burrListDAGScheduler("list-burr",
                        createBURRListDAGScheduler);
 static RegisterScheduler
   sourceListDAGScheduler("source",
                          "Similar to list-burr but schedules in source "
                          "order when possible",
                          createSourceListDAGScheduler);
 
 static RegisterScheduler
+  guidedSrcListDAGScheduler("guided-src",
+                         "Heuristic based on already scheduled nodes, fall backs"
+                         "on source order priority.",
+                         createGuidedSrcListDAGScheduler);
+
+static RegisterScheduler
   hybridListDAGScheduler("list-hybrid",
                          "Bottom-up register pressure aware list scheduling "
                          "which tries to balance latency and register pressure",
                          createHybridListDAGScheduler);
 
 static RegisterScheduler
   ILPListDAGScheduler("list-ilp",
                       "Bottom-up register pressure aware list scheduling "
struct bu_ls_rr_sort : public queue_sort {
   };
 
   RegReductionPQBase *SPQ;
   bu_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
 
   bool operator()(SUnit* left, SUnit* right) const;
 };
 
+// gu_src_ls_rr_sort - Priority function for guided source order scheduler.
+struct gu_src_ls_rr_sort : public queue_sort {
+    enum {
+      IsBottomUp = true,
+      HasReadyFilter = false
+    };
+
+    RegReductionPQBase *SPQ;
+    gu_src_ls_rr_sort(RegReductionPQBase *spq)
+       : SPQ(spq) {}
+
+    bool operator()(SUnit* left, SUnit* right) const;
+  private:
+    unsigned getNodeWeight(SDNode *) const;
+};
+
 // src_ls_rr_sort - Priority function for source order scheduler.
 struct src_ls_rr_sort : public queue_sort {
   enum {
     IsBottomUp = true,
     HasReadyFilter = false
   };
 
   RegReductionPQBase *SPQ;
if (TracksRegPressure) {
         RegLimit[RC->getID()] = tri->getRegPressureLimit(RC, MF);
     }
   }
 
   void setScheduleDAG(ScheduleDAGRRList *scheduleDag) {
     scheduleDAG = scheduleDag;
   }
 
+  ScheduleDAGRRList * getScheduleDAG() {
+    return scheduleDAG;
+  }
+
   ScheduleHazardRecognizer* getHazardRec() {
     return scheduleDAG->getHazardRec();
   }
 
   void initNodes(std::vector<SUnit> &sunits) override;
 
   void addNode(const SUnit *SU) override;
 

 };
 
 typedef RegReductionPriorityQueue<bu_ls_rr_sort>
 BURegReductionPriorityQueue;
 
 typedef RegReductionPriorityQueue<src_ls_rr_sort>
 SrcRegReductionPriorityQueue;
 
+typedef RegReductionPriorityQueue<gu_src_ls_rr_sort>
+GuidedSrcRegReductionPriorityQueue;
+
 typedef RegReductionPriorityQueue<hybrid_ls_rr_sort>
 HybridBURRPriorityQueue;
 
 typedef RegReductionPriorityQueue<ilp_ls_rr_sort>
 ILPBURRPriorityQueue;
 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//

 // Bottom up
 bool bu_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
   if (int res = checkSpecialNodes(left, right))
     return res > 0;
 
   return BURRSort(left, right, SPQ);
 }
 
+
+unsigned gu_src_ls_rr_sort::getNodeWeight(SDNode *N) const {
+  unsigned Weight = 0;
+  SmallVector<SDNode *, 16> NodeList;
+  using SUVecT = std::vector<SUnit *>;
+  using SUVecItr = std::vector<SUnit *>::iterator;
+  SUVecT &Sequence = SPQ->getScheduleDAG()->Sequence;
+
+  auto IsValidNodeListNode = [](SDNode *N) -> bool {
+    unsigned Opc = N->getOpcode();
+    if (Opc == ISD::UNDEF || Opc == ISD::Constant ||
+        Opc == ISD::TargetConstant || Opc == ISD::ConstantFP ||
+        Opc == ISD::TargetConstantFP || Opc == ISD::Register ||
+        Opc == ISD::RegisterMask)
+      return false;
+    // Check for chain nodes.
+    if (N->getNumValues() == 1 && N->getSimpleValueType(0) == MVT::Other)
+      return false;
+    return true;
+  };
+
+  NodeList.push_back(N);
+  for (const SDValue &Op : N->op_values())
+    NodeList.push_back(Op.getNode());
+
+  for (SDNode *Node : NodeList) {
+    if (!IsValidNodeListNode(Node))
+      continue;
+    for (SDNode *User : Node->uses()) {
+      if (User == N)
+        continue;
+      SUVecItr SchedUnit = std::find_if(
+          Sequence.begin(), Sequence.end(), [&](const SUnit *SU) -> bool {
+            if (User->getNodeId() >= 0 &&
+                SU->NodeNum == static_cast<unsigned>(User->getNodeId()))
+              return true;
+            return false;
+          });
+      if (SchedUnit != Sequence.end())
+        Weight += 10;
+    }
+  }
+  return Weight;
+}
+
+// Guided scheduling with src order fall back, otherwise bottom up.
+bool gu_src_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
+  if (int res = checkSpecialNodes(left, right))
+    return res > 0;
+
+  SDNode *leftN = left->getNode();
+  SDNode *rightN = right->getNode();
+  unsigned leftNW = getNodeWeight(leftN);
+  unsigned rightNW = getNodeWeight(rightN);
+
+  if (leftNW > rightNW)
+    return false;
+  else if (leftNW < rightNW)
+    return true;
+
+  unsigned LOrder = SPQ->getNodeOrdering(left);
+  unsigned ROrder = SPQ->getNodeOrdering(right);
+
+  // Prefer an ordering where the lower the non-zero order number, the higher
+  // the preference.
+  if ((LOrder || ROrder) && LOrder != ROrder)
+    return LOrder != 0 && (LOrder < ROrder || ROrder == 0);
+
+  return BURRSort(left, right, SPQ);
+}
+
 // Source order, otherwise bottom up.
 bool src_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
   if (int res = checkSpecialNodes(left, right))
     return res > 0;
 
   unsigned LOrder = SPQ->getNodeOrdering(left);
   unsigned ROrder = SPQ->getNodeOrdering(right);
 
llvm::createBURRListDAGScheduler(SelectionDAGISel *IS,
   BURegReductionPriorityQueue *PQ =
     new BURegReductionPriorityQueue(*IS->MF, false, false, TII, TRI, nullptr);
   ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, false, PQ, OptLevel);
   PQ->setScheduleDAG(SD);
   return SD;
 }
 
 llvm::ScheduleDAGSDNodes *
+llvm::createGuidedSrcListDAGScheduler(SelectionDAGISel *IS,
+                                   CodeGenOpt::Level OptLevel) {
+  const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
+  const TargetInstrInfo *TII = STI.getInstrInfo();
+  const TargetRegisterInfo *TRI = STI.getRegisterInfo();
+
+  GuidedSrcRegReductionPriorityQueue *PQ =
+    new GuidedSrcRegReductionPriorityQueue(*IS->MF, false, true, TII, TRI, nullptr);
+  ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, false, PQ, OptLevel);
+  PQ->setScheduleDAG(SD);
+  return SD;
+}
+
+llvm::ScheduleDAGSDNodes *
 llvm::createSourceListDAGScheduler(SelectionDAGISel *IS,
                                    CodeGenOpt::Level OptLevel) {
   const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
   const TargetInstrInfo *TII = STI.getInstrInfo();
   const TargetRegisterInfo *TRI = STI.getRegisterInfo();
 
   SrcRegReductionPriorityQueue *PQ =
     new SrcRegReductionPriorityQueue(*IS->MF, false, true, TII, TRI, nullptr);

test/CodeGen/X86/guided_sched.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; NOTE: Both functions must emit same instruction schedule with -guided-src
+;RUN: llc < %s -mtriple=x86_64-unknown-linux-gnu -mcpu=skx | FileCheck --check-prefixes=DEFAULT-SCHED %s
+;RUN: llc < %s -pre-RA-sched=guided-src -mtriple=x86_64-unknown-linux-gnu -mcpu=skx | FileCheck --check-prefixes=GUIDED_SRC-SCHED %s
+
+define i32 @clz_i128(i64, i64)  {
+; DEFAULT-SCHED-LABEL: clz_i128:
+; DEFAULT-SCHED:       # BB#0:
+; DEFAULT-SCHED-NEXT:    lzcntq %rsi, %rcx
+; DEFAULT-SCHED-NEXT:    xorl %edx, %edx
+; DEFAULT-SCHED-NEXT:    lzcntq %rdi, %rax
+; DEFAULT-SCHED-NEXT:    cmovael %edx, %ecx
+; DEFAULT-SCHED-NEXT:    addl %ecx, %eax
+; DEFAULT-SCHED-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
+; DEFAULT-SCHED-NEXT:    retq
+;
+; GUIDED_SRC-SCHED-LABEL: clz_i128:
+; GUIDED_SRC-SCHED:       # BB#0:
+; GUIDED_SRC-SCHED-NEXT:    lzcntq %rsi, %rcx
+; GUIDED_SRC-SCHED-NEXT:    xorl %edx, %edx
+; GUIDED_SRC-SCHED-NEXT:    lzcntq %rdi, %rax
+; GUIDED_SRC-SCHED-NEXT:    cmovael %edx, %ecx
+; GUIDED_SRC-SCHED-NEXT:    addl %ecx, %eax
+; GUIDED_SRC-SCHED-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
+; GUIDED_SRC-SCHED-NEXT:    retq
+  %3 = tail call i64 @llvm.ctlz.i64(i64 %1, i1 false)
+  %4 = tail call i64 @llvm.ctlz.i64(i64 %0, i1 false)
+  %5 = icmp ne i64 %0, 0
+  %6 = select i1 %5, i64 0, i64 %3
+  %7 = add nuw nsw i64 %6, %4
+  %8 = trunc i64 %7 to i32
+  ret i32 %8
+}
+
+define i32 @clz_i128_swap(i64, i64)  {
+; DEFAULT-SCHED-LABEL: clz_i128_swap:
+; DEFAULT-SCHED:       # BB#0:
+; DEFAULT-SCHED-NEXT:    lzcntq %rdi, %rax
+; DEFAULT-SCHED-NEXT:    lzcntq %rsi, %rcx
+; DEFAULT-SCHED-NEXT:    xorl %edx, %edx
+; DEFAULT-SCHED-NEXT:    testq %rdi, %rdi
+; DEFAULT-SCHED-NEXT:    cmovnel %edx, %ecx
+; DEFAULT-SCHED-NEXT:    addl %ecx, %eax
+; DEFAULT-SCHED-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
+; DEFAULT-SCHED-NEXT:    retq
+;
+; GUIDED_SRC-SCHED-LABEL: clz_i128_swap:
+; GUIDED_SRC-SCHED:       # BB#0:
+; GUIDED_SRC-SCHED-NEXT:    lzcntq %rsi, %rcx
+; GUIDED_SRC-SCHED-NEXT:    xorl %edx, %edx
+; GUIDED_SRC-SCHED-NEXT:    lzcntq %rdi, %rax
+; GUIDED_SRC-SCHED-NEXT:    cmovael %edx, %ecx
+; GUIDED_SRC-SCHED-NEXT:    addl %ecx, %eax
+; GUIDED_SRC-SCHED-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
+; GUIDED_SRC-SCHED-NEXT:    retq
+  %3 = tail call i64 @llvm.ctlz.i64(i64 %0, i1 false) ;   <-- SWAP
+  %4 = tail call i64 @llvm.ctlz.i64(i64 %1, i1 false) ;   <-- SWAP
+  %5 = icmp ne i64 %0, 0
+  %6 = select i1 %5, i64 0, i64 %4
+  %7 = add nuw nsw i64 %6, %3
+  %8 = trunc i64 %7 to i32
+  ret i32 %8
+}
+declare i64 @llvm.ctlz.i64(i64, i1)
+