<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body>
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">
<div>Hi Krzysztof,</div>
<div><br>
</div>
<div>Thanks for the reply, I'm starting to understand the graph structure and terminology much better now, especially with the document in RDFGraph.h. I'm still a bit confused about some of the behavior I'm seeing with the phi nodes that involve aggregate registers.
Here is one example:</div>
<div><br>
</div>
<div> b1531: --- %bb.36 --- preds(2): %bb.35, %bb.128 succs(1): %bb.37<br>
p3193: phi [+d3194<RBP>(,,u3211):, u3195<RBP>(+d3170,b1526):u1437, u3196<RBP>(d2141,b2486):u2324]<br>
p3197: phi [+d3198<RBX>(,,u3216):, u3199<RBX>(+d3138,b1526):u1465, u3200<RBX>(+d3364,b2486):]<br>
p3201: phi [+d3202<R12D>(,d1541,):, u3203<R12D>(+d3146,b1526):, u3204<R12D>(d1878,b2486):u3148]<br>
p3205: phi [+d3206<#1073741833>(,d1551,u1552):, u3207"<#1073741833>(d1521,b1526):u1524, u3779"<#1073741833>(d1517,b1526):, u3780"<#1073741833>(d1513,b1526):u1522, u3208"<#1073741833>(d2481,b2486):u2484, u3695"<#1073741833>(d2477,b2486):, u3696"<#1073741833>(d2473,b2486):u2482]<br>
s1532: ADJCALLSTACKDOWN64 [d1533<RSP>!(+d3206,\~d3647",u1557):, d1534<EFLAGS>!(+d3206,d1540,):d1533, d1535<SSP>!(+d3206,\~d3646",u1558):d1534, u1536<RSP>!(+d3206):, u1537<SSP>!(+d3206):u1536]<br>
s1538: MOV32r0 [d1539<R12D>(+d3202,,):, d1540<EFLAGS>!(d1534,d1549,):, d1541<R12>(+d3202,,u3221):d1539]<br>
s1542: MOV32ri64 [d1543<RDX>(+d3206,\~d3645",u1561):d1535]<br>
s1544: COPY [d1545<RDI>(+d3206,\~d3644",u1559):d1543, u1546<R13>(d785):]<br>
s1547: MOV32r0 [d1548<ESI>(+d3206,\~d3643",u1560):d1545, d1549<EFLAGS>!(d1540,\~d3642",):]<br>
s1550: MOV64rm [d1551<R11>(+d3206,\~d1554",u1562):d1548, u1552<RIP>(+d3206):u1537]<br>
s1553: CALL64pcrel32 __foo [\~d1554"<#1073741833>!(d1551,d1579,):, \~d3642"<#1073741833>!(d1549,,):, \~d3643"<#1073741833>!(d1548,,):, \~d3644"<#1073741833>!(d1545,,):, \~d3645"<#1073741833>!(d1543,,):, \~d3646"<#1073741833>!(d1535,,):, \~d3647"<#1073741833>!(d1533,,):,
d1555<RSP>!(\~d1554",d1564,u1567):, d1556<SSP>!(\~d1554",d1566,u1568):d1555, u1557<RSP>!(d1533):, u1558<SSP>!(d1535):, u1559<RDI>!(d1545):, u1560<ESI>!(d1548):, u1561<RDX>!(d1543):, u1562<R11>!(d1551):]<br>
s1563: ADJCALLSTACKUP64 [d1564<RSP>!(d1555,,u3778"):, d1565<EFLAGS>!(\~d1554",d1571,):d1556, d1566<SSP>!(d1556,,u3777"):,</div>
<div> u1567<RSP>!(d1555):, u1568<SSP>!(d1556):]<br>
s1569: MOV32r0 [d1570<R10D>(\~d1554",,u3776"):d1565, d1571<EFLAGS>!(d1565,d1574,):]<br>
s1572: MOV32r0 [d1573<R8D>(\~d1554",,u3775"):d1570, d1574<EFLAGS>!(d1571,d1577,):]<br>
s1575: MOV32r0 [d1576<R9D>(\~d1554",,u3774"):d1573, d1577<EFLAGS>!(d1574,,u3773"):]<br>
---> s1578: MOV64rm [d1579<R11>(\~d1554",,u3226"):d1576]</div>
<div><br>
</div>
<div> b1580: --- %bb.37 --- preds(3): %bb.36, %bb.49, %bb.64 succs(1): %bb.38<br>
p3209: phi [+d3210<RBP>(,d1731,u3212):, u3211<RBP>(+d3194,b1531):, u3212<RBP>(+d3210,b1710):, u3213<RBP>(d1857,b1874):u3466]<br>
p3214: phi [+d3215<RBX>(,,u3217):, u3216<RBX>(+d3198,b1531):, u3217<RBX>(+d3215,b1710):u3257, u3218<RBX>(+d3290,b1874):u3470]<br>
p3219: phi [+d3220<R12D>(,d1712,u1714):, u3221<R12D>(d1541,b1531):, u3222<R12D>(d1712,b1710):u1717, u3223<R12D>(d1878,b1874):u3204]<br>
---> p3224: phi [+d3225<#1073741833>(,d1598,):, u3226"<#1073741833>(d1579,b1531):, u3773"<#1073741833>(d1577,b1531):, u3774"<#1073741833>(d1576,b1531):, u3775"<#1073741833>(d1573,b1531):, u3776"<#1073741833>(d1570,b1531):, u3777"<#1073741833>(d1566,b1531):,
u3778"<#1073741833>(d1564,b1531):, u3227<#1073741833>(d1716,b1710):u1719, u3228"<#1073741833>(d1885,b1874):u3751", u3754"<#1073741833>(d1880,b1874):u1887, u3755"<#1073741833>(d1865,b1874):u3752", u3756"<#1073741833>(d1861,b1874):u3753"]<br>
s1581: IMUL64rri8 [d1582<RAX>(+d3225,d1596,u1592):, d1583<EFLAGS>!(+d3225,d1595,):d1582, u1584<R12>(+d3220):]<br>
s1585: LEA64r [d1586<RSI>(+d3225,,u3772"):d1583, u1587<R15>(d776):, u1588<RAX>(d1582):]<br>
s1589: LEA64r [d1590<RDI>(+d3225,,u3771"):d1586, u1591<R14>(+d3142):u1455, u1592<RAX>(d1582):u1588]<br>
s1593: MOV32r0 [d1594<EAX>(d1582,,):, d1595<EFLAGS>!(d1583,d1599,):, d1596<RAX>(d1582,,u3770"):d1594]<br>
s1597: MOV32r0 [d1598<ECX>(+d3225,,u3769"):d1590, d1599<EFLAGS>!(d1595,,u3231"):]<br>
<br>
</div>
<div>I have used arrows to highlight two nodes. The first node, s1578, def's d1579<R11>, which has a single reached use in phi node p3224. I am surprised that this phi node exists and has no reached uses, for two reasons. First, I built the graph without the
KeepDeadPhis option. Shouldn't this remove phi nodes without reached uses? Second, there clearly
<i>is</i> a reached use of R11 (corresponding to the instruction represented by s1578) in another basic block:</div>
<div><br>
</div>
<div> b1721: --- %bb.50 --- preds(1): %bb.49 succs(1): %bb.51<br>
s1722: COPY [d1723<RSI>(+d3248,,u3765"):d1713, u1724<R13>(d785):u1546]<br>
---> s1725: COPY [d1726<RDI>(+d3248,,u3764"):d1723, u1727<R11>(+d3248):]<br>
s1728: MOV32r0 [d1729<EBP>(+d3210,,):, d1730<EFLAGS>!(d1716,,u3261"):, d1731<RBP>(+d3210,,u3253):d1729]</div>
<div><br>
</div>
<div>I have confirmed via manual inspection and the use of a dynamic analysis tool that the next use of the R11 def in s1578 is s1725.</div>
<div><br>
</div>
<div>Could you please clarify these two points?</div>
<div><br>
</div>
<div>Thanks,</div>
<div><br>
</div>
<div>Scott</div>
</div>
</div>
</div>
<br>
<div class="gmail_quote">
<div class="gmail_attr" dir="ltr">On Mon, Dec 23, 2019 at 12:46 PM Krzysztof Parzyszek <<a href="mailto:kparzysz@quicinc.com">kparzysz@quicinc.com</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;padding-left:1ex;border-left-color:rgb(204,204,204);border-left-width:1px;border-left-style:solid">
<div lang="EN-US">
<div class="gmail-m_7318943712744839235WordSection1">
<p class="MsoNormal">Hi Scott,<u></u><u></u></p>
<p class="MsoNormal">That #1073741833 is a register mask. They are treated as aggregate registers (essentially sets of registers), so if it includes R9D and R11D, it will be treated as being aliased with both.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">These separate defs are there because they reach disjoint registers.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal"><span style="font-family:Consolas;font-size:9pt">-- </span><span style="font-family:Consolas;font-size:9pt"><u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:Consolas;font-size:8pt">Krzysztof Parzyszek
<a href="mailto:kparzysz@quicinc.com" target="_blank"><span style="color:rgb(5,99,193)">kparzysz@quicinc.com</span></a> AI tools development<u></u><u></u></span></p>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
<div style="border-width:medium medium medium 1.5pt;border-style:none none none solid;border-color:currentColor currentColor currentColor blue;padding:0in 0in 0in 4pt">
<div>
<div style="border-width:1pt medium medium;border-style:solid none none;border-color:rgb(225,225,225) currentColor currentColor;padding:3pt 0in 0in">
<p class="MsoNormal"><b>From:</b> Scott Douglas Constable <<a href="mailto:sdconsta@syr.edu" target="_blank">sdconsta@syr.edu</a>>
<br>
<b>Sent:</b> Monday, December 23, 2019 2:10 PM<br>
<b>To:</b> Scott Douglas Constable <<a href="mailto:sdconsta@syr.edu" target="_blank">sdconsta@syr.edu</a>><br>
<b>Cc:</b> Krzysztof Parzyszek <<a href="mailto:kparzysz@quicinc.com" target="_blank">kparzysz@quicinc.com</a>>;
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<b>Subject:</b> [EXT] Re: [llvm-dev] Register Dataflow Analysis on X86<u></u><u></u></p>
</div>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<p class="MsoNormal">Revisiting this thread. I have been experimenting with the RDF module on the X86 target. For the most part, building the data-flow graph and following def-use chains seems to work fine. But I am also observing some strange behavior in the
phi nodes. For example, I have one basic block which begins with the following 4 phi nodes:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">b585: --- %bb.25 --- preds(5): %bb.24, %bb.20, %bb.22, %bb.49, %bb.52 succs(2): %bb.18, %bb.37<br>
p1095: phi [+d1096<EBP>(,d668,):, u1097<EBP>(d540,b477):u555, u1098<EBP>(d427,b448):u450, u1099<EBP>(d427,b462):u464, u1100<EBP>(d427,b1009):u1011, u1101<EBP>(d427,b1027):u1029]<br>
p1102: phi [+d1103<R13D>(,,u1075):, u1104<R13D>(d557,b477):u563, u1105<R13D>(d411,b448):, u1106<R13D>(d411,b462):u459, u1107<R13D>(d411,b1009):u1106, u1108<R13D>(d411,b1027):u1107]<br>
p1109: phi [+d1110<R14D>(,d625,u612):, u1111<R14D>(d584,b477):, u1112<R14D>(d452,b448):, u1113<R14D>(d466,b462):, u1114<R14D>(d1013,b1009):, u1115<R14D>(d1031,b1027):]<br>
p1116: phi [+d1117<#1073741833>(,d645,u648):, u1118"<#1073741833>(d579,b477):, u1466"<#1073741833>(d578,b477):, u1467"<#1073741833>(d569,b477):u581, u1468"<#1073741833>(d546,b477):, u1469"<#1073741833>(d543,b477):, u1470"<#1073741833>(d524,b477):u530, u1119"<#1073741833>(d453,b448):,
u1436"<#1073741833>(d420,b448):, u1437"<#1073741833>(d404,b448):u445, u1120"<#1073741833>(d467,b462):, u1438"<#1073741833>(d420,b462):u1436", u1439"<#1073741833>(d404,b462):u473, u1121"<#1073741833>(d1014,b1009):, u1440"<#1073741833>(d420,b1009):u1006, u1441"<#1073741833>(d404,b1009):u1439",
u1122"<#1073741833>(d1032,b1027):, u1442"<#1073741833>(d420,b1027):u1440", u1443"<#1073741833>(d404,b1027):u1441"]<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">The first three make perfect sense to me, and seem to reflect the post-allocation MIR correctly. The fourth phi node seems entirely composed of defs and uses for some unnamed register #1073741833 (what exactly is the significance of unnamed
registers?). Moreover, this phi seems to be introducing false def-use relationships into the DFG. For example, the phi introduces the following dependency chain, which as far as I can tell is not valid:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">// R11D is def'ed, def ID is d524<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">s523: SUB32rr [d524<R11D>(d519,,u1470"):, d525<EFLAGS>!(d520,d533,):, u526<R11D>(d519):, u527<ESI>(d508):]<br>
...<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">// d524 is used in the phi node to def d1117, corresponding to unnamed register #1073741833<br>
p1116: phi [+d1117<#1073741833>(,d645,u648):, u1118"<#1073741833>(d579,b477):, u1466"<#1073741833>(d578,b477):, u1467"<#1073741833>(d569,b477):u581, u1468"<#1073741833>(d546,b477):, u1469"<#1073741833>(d543,b477):, u1470"<#1073741833>(d524,b477):u530, u1119"<#1073741833>(d453,b448):,
u1436"<#1073741833>(d420,b448):, u1437"<#1073741833>(d404,b448):u445, u1120"<#1073741833>(d467,b462):, u1438"<#1073741833>(d420,b462):u1436", u1439"<#1073741833>(d404,b462):u473, u1121"<#1073741833>(d1014,b1009):, u1440"<#1073741833>(d420,b1009):u1006, u1441"<#1073741833>(d404,b1009):u1439",
u1122"<#1073741833>(d1032,b1027):, u1442"<#1073741833>(d420,b1027):u1440", u1443"<#1073741833>(d404,b1027):u1441"]<br>
...<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">// d1117 is used in def d645 of register R9D<br>
s644: ADD32rr [d645<R9D>(+d1117,d694,u659):d634, d646<EFLAGS>!(d633,d651,):, u647<R9D>(+d1117):u637, u648<R9D>(+d1117):u647]<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">But after examining the corresponding MIR, I do not think that R11D flows into R9D. So it looks to me as though this phi node is erroneous.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Any help wold be much appreciated!<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">I'm using the LLVM 8.0.1 release.<u></u><u></u></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<div>
<p class="MsoNormal">On Fri, Nov 8, 2019 at 10:35 AM Scott Douglas Constable via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<u></u><u></u></p>
</div>
<blockquote style="border-width:medium medium medium 1pt;border-style:none none none solid;border-color:currentColor currentColor currentColor rgb(204,204,204);padding:0in 0in 0in 6pt;margin-right:0in;margin-left:4.8pt">
<div>
<div>
<div>
<p class="MsoNormal">Do you know whether it has been fixed on the 8.0.1 release?<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Scott<u></u><u></u></p>
</div>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<div>
<p class="MsoNormal">On Fri, Nov 8, 2019 at 9:45 AM Krzysztof Parzyszek <<a href="mailto:kparzysz@quicinc.com" target="_blank">kparzysz@quicinc.com</a>> wrote:<u></u><u></u></p>
</div>
<blockquote style="border-width:medium medium medium 1pt;border-style:none none none solid;border-color:currentColor currentColor currentColor rgb(204,204,204);padding:0in 0in 0in 6pt;margin-right:0in;margin-left:4.8pt">
<div>
<div>
<p class="MsoNormal">The one blocking issue that existed in the past has been fixed. I haven’t had time to do any work on it lately, but I’m not aware of any fundamental problems that would make it not work on x86.<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<div>
<p class="MsoNormal"><span style="font-family:Consolas;font-size:9pt">-- </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Consolas;font-size:8pt">Krzysztof Parzyszek
<a href="mailto:kparzysz@quicinc.com" target="_blank"><span style="color:rgb(5,99,193)">kparzysz@quicinc.com</span></a> AI tools development</span><u></u><u></u></p>
</div>
<p class="MsoNormal"> <u></u><u></u></p>
<div style="border-width:medium medium medium 1.5pt;border-style:none none none solid;border-color:currentColor currentColor currentColor blue;padding:0in 0in 0in 4pt">
<div>
<div style="border-width:1pt medium medium;border-style:solid none none;border-color:currentColor;padding:3pt 0in 0in">
<p class="MsoNormal"><b>From:</b> llvm-dev <<a href="mailto:llvm-dev-bounces@lists.llvm.org" target="_blank">llvm-dev-bounces@lists.llvm.org</a>>
<b>On Behalf Of </b>Scott Douglas Constable via llvm-dev<br>
<b>Sent:</b> Friday, November 8, 2019 10:59 AM<br>
<b>To:</b> <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<b>Subject:</b> [EXT] [llvm-dev] Register Dataflow Analysis on X86<u></u><u></u></p>
</div>
</div>
<p class="MsoNormal"> <u></u><u></u></p>
<div>
<div>
<p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:"Arial",sans-serif;font-size:10pt">I came across this thread from a couple years ago:</span><u></u><u></u></p>
<p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:"Arial",sans-serif;font-size:10pt"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:"Arial",sans-serif;font-size:10pt"><a href="http://lists.llvm.org/pipermail/llvm-dev/2017-November/119346.html" target="_blank"><span style="color:rgb(17,85,204)">http://lists.llvm.org/pipermail/llvm-dev/2017-November/119346.html</span></a></span><u></u><u></u></p>
<p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:"Arial",sans-serif;font-size:10pt"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:"Arial",sans-serif;font-size:10pt">Has there been any progress on RDF for X86? Or is there some other preferred alternative for performing reachability analysis after register allocation?</span><u></u><u></u></p>
<p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:"Arial",sans-serif;font-size:10pt"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:"Arial",sans-serif;font-size:10pt">Thanks,</span><u></u><u></u></p>
<p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:"Arial",sans-serif;font-size:10pt"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:"Arial",sans-serif;font-size:10pt">Scott Constable</span><u></u><u></u></p>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</div>
<p class="MsoNormal">_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><u></u><u></u></p>
</blockquote>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</body>
</html>