[llvm-dev] Looking for some history on MachinePipeliner

[Nagurne, James via llvm-dev]

I've been tinkering with the MachinePipeliner for my team's downstream target, and have run into a particular issue with node ordering in the SMS algorithm. In particular, I've noticed that in some cases, I'm receiving an 'Invalid node order' warning in the debug. I've tracked this down to how 'computeNodeOrder' is implemented.

computeNodeOrder's algorithm seems to be relatively untouched from the initial commit:
https://reviews.llvm.org/D16829

However, the algorithm is very different from those found in the 3 papers upon which the implementation is based:
                https://github.com/llvm/llvm-project/blob/f40bba48a593d4297a6d0b4d1534082858b1d0ac/llvm/include/llvm/CodeGen/MachinePipeliner.h#L18

In the implementation:
                https://github.com/llvm/llvm-project/blob/f40bba48a593d4297a6d0b4d1534082858b1d0ac/llvm/lib/CodeGen/MachinePipeliner.cpp#L1877
The order seems to be:

  *   If pred_L is a subset of the NodeSet, BottomUp and add subset to work list
  *   If succ_L is s subset of the NodeSet, TopDown and add subset to work list
  *   If intersect(succ_L, NodeSet) is non-empty, TopDown and add intersect to work list
  *   If there is only 1 NodeSet, BottomUp and add nodes at the bottom of the schedule (Succs.size() == 0) to work list
  *   Otherwise, BottomUp and add node with the highest ASAP to work list

In the papers (Using Tanya Lattner's master's thesis<https://llvm.org/pubs/2005-06-17-LattnerMSThesis.html> as the example), the order is:

  *   If intersect(pred_L, NodeSet) is non-empty, BottomUp and add subset to work list
  *   If intersect(succ_L, NodeSet) is non-empty, TopDown and add subset to work list
  *   Otherwise, BottomUp and add node with the highest ASAP to work list

Interestingly, when I implement the ordering from the paper, the node order for my loop is valid.

This difference in implementation is not mentioned or commented on in the review, so I'm wondering if there are any documents or emails I may have missed in my search that would shed some light. Certainly, this ordering is just a heuristic, so I can understand that the current incarnation just resulted in better performance for the targets utilizing it, but I'm curious if there was something more to the decision.

Regards,
J.B. Nagurne
Code Generation
Texas Instruments
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210909/38898e09/attachment.html>