[llvm-dev] Looking for some history on MachinePipeliner

[Cahoon, Brendon via llvm-dev]

[Public]

I think it would be fine to propose changing the subset test to an intersection test and try to get some feedback on the impact. Although I think I've tried it, that would have been a long time ago, so I don't remember the outcome.  I'm curious because looking at the code again, it uses the intersection test, but only for successors. The following is equivalent to the existing code (and replaces separate tests for subset then intersection):

    if (pred_L(NodeOrder, N) && llvm::set_is_subset(N, Nodes)) {
        /* bottom up */
    } else if (succ_L(NodeOrder, N) && isIntersect(N, Nodes, R)) {
        /* top down */

So, really, it would just change the logic for the pred_L case.

One comment about the example provided earlier. Using the subset test generates a good node order for this example.
> This is the problem my particular loop runs into.
> With NodeSets:
> S0 = {1, 2, 3, 4}, maxASAP is node 4
> S1 = {5, 6, 7, 8}, maxASAP is node 8 (tied with 7, tie-broken because id 8 > 7)
> 
> With a skeletal set of DAG edges
> 2 -> 6 -> 7
> 6 -> 8
> 
> computeNodeOrder looks something like:
> 1. S0 is added to the node order bottom-up (default), say NodeOrder = {4, 3, 2, 1}
> 2. Starting on S1: pred_L(NodeOrder) is non-empty, but not a subset of S1, so execution eventually drops into bottom-up (default), with node 8 added to the work list as maxASAP

Step 2 with the subset test should be:
2. NodeOrder is {4, 3, 2, 1} so, succ_L(NodeOrder) is {6}. Since {6} is a subset of {5, 6, 7, 8}, then the top down order is chosen.  Nodes 6, 7, and 8 are added to NodeOrder({4, 3, 2, 1, 6, 7, 8}). Then, the algorithm switches to bottom up and 5 is added to produce NodeOrder({4, 3, 2, 1, 6, 7, 8, 5}).

Now, if there is a 3rd NodeSet, S3 = {9}, and an edge from, say, 4 -> 9, then the subset test doesn't work because succ_L({4, 3, 2, 1}) is {6, 9}, which is not a subset of {5, 6, 7, 8}. So if there is no subsequent intersection test, then the bottom-up order is used on NodeSet S1.

Thanks,
Brendon