<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Exchange Server">
<!-- converted from text --><style><!-- .EmailQuote { margin-left: 1pt; padding-left: 4pt; border-left: #800000 2px solid; } --></style>
</head>
<body>
<div>I do apologize for the bad abstract example. There are more edges I've elided for brevity. The full dag and NodeSets are more complicated. I only stated that pred_L wasn't a subset of S1 without adding nodes and edges to make it so.<br>
<br>
If I'm able to replicate the ordering behavior on an upstream target, I'll look into sharing the loop code (an in-house benchmark, so the rules may be .. complicated).<br>
<br>
JB
<hr tabindex="-1" style="display:inline-block; width:98%">
<div id="x_divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" color="#000000" style="font-size:11pt"><b>From:</b> Cahoon, Brendon <Brendon.Cahoon@amd.com><br>
<b>Sent:</b> Saturday, September 11, 2021 12:00:51 PM<br>
<b>To:</b> Nagurne, James; Jason Eckhardt<br>
<b>Cc:</b> llvm-dev@lists.llvm.org; Jayaraj, Ajay<br>
<b>Subject:</b> [EXTERNAL] RE: Looking for some history on MachinePipeliner</font>
<div> </div>
</div>
</div>
<font size="2"><span style="font-size:10pt;">
<div class="PlainText">[Public]<br>
<br>
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):<br>
<br>
if (pred_L(NodeOrder, N) && llvm::set_is_subset(N, Nodes)) {<br>
/* bottom up */<br>
} else if (succ_L(NodeOrder, N) && isIntersect(N, Nodes, R)) {<br>
/* top down */<br>
<br>
So, really, it would just change the logic for the pred_L case.<br>
<br>
One comment about the example provided earlier. Using the subset test generates a good node order for this example.<br>
> This is the problem my particular loop runs into.<br>
> With NodeSets:<br>
> S0 = {1, 2, 3, 4}, maxASAP is node 4<br>
> S1 = {5, 6, 7, 8}, maxASAP is node 8 (tied with 7, tie-broken because id 8 > 7)<br>
> <br>
> With a skeletal set of DAG edges<br>
> 2 -> 6 -> 7<br>
> 6 -> 8<br>
> <br>
> computeNodeOrder looks something like:<br>
> 1. S0 is added to the node order bottom-up (default), say NodeOrder = {4, 3, 2, 1}<br>
> 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<br>
<br>
Step 2 with the subset test should be:<br>
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}).<br>
<br>
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.<br>
<br>
Thanks,<br>
Brendon<br>
</div>
</span></font>
</body>
</html>