<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"><base href="x-msg://10814/"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On Oct 17, 2012, at 3:10 PM, Sergei Larin <<a href="mailto:slarin@codeaurora.org">slarin@codeaurora.org</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div lang="EN-US" link="blue" vlink="purple" style="font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div class="WordSection1" style="page: WordSection1; "><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">Andy,<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> So if it is not a feature… then couple questions:<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> First, I also do not see an easy way to restructure work sets in this case – so let’s assume std::map is needed here. Then the way I understand it, there are five objects that cause the indeterminism:<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> std::map<const Value *, SUnit *> AliasMemDefs, NonAliasMemDefs;<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> std::map<const Value *, std::vector<SUnit *> > AliasMemUses, NonAliasMemUses;<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> std::set<SUnit*> RejectMemNodes;<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">…since all of them at different point of time are traversed begin to end, and as such are affected by pointer value.<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">The case of “std::set<SUnit*> RejectMemNodes; “ is easy. Something like this will work:<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">struct SortSUComp {<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> bool operator()(const SUnit *left, const SUnit *right) const {<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> return left->NodeNum < right->NodeNum;<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> }<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> };<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> typedef std::set<SUnit*, SortSUComp> SortedSUSet;<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> SortedSUSet RejectMemNodes;<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">But in case of Value * as a key – is there any unique ID that is deterministic and could be used here? As I understand getValueID () is not unique, or could it be sufficient in this case?<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">Something as bulky as temporary sorting queue/vector is also possible, but I do not like it very much.<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">Any other ideas?</span></div></div></div></blockquote><div><br></div><div>I don't have any great ideas, but anything is an improvement over std::map/std::set.</div><div><br></div><div>AFAIK we don't need to remove individual elements from the map. Is that right? So SetVector and MapVector should work fine. They don't sort by key but maintain a side vector to track insertion order.</div><div><br></div><div>-Andy</div><br><blockquote type="cite"><div lang="EN-US" link="blue" vlink="purple" style="font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div class="WordSection1" style="page: WordSection1; "><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "><o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">Thanks.<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">Sergei<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 10.5pt; font-family: Consolas; color: rgb(31, 73, 125); ">---<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 10.5pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation</span><span style="font-size: 10.5pt; font-family: Consolas; color: rgb(31, 73, 125); "><o:p></o:p></span></div></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span></div><div style="border-style: none none none solid; border-left-width: 1.5pt; border-left-color: blue; padding: 0in 0in 0in 4pt; "><div><div style="border-style: solid none none; border-top-width: 1pt; border-top-color: rgb(181, 196, 223); padding: 3pt 0in 0in; "><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><b><span style="font-size: 10pt; font-family: Tahoma, sans-serif; ">From:</span></b><span style="font-size: 10pt; font-family: Tahoma, sans-serif; "><span class="Apple-converted-space"> </span>Andrew Trick [mailto:atrick@<a href="http://apple.com">apple.com</a>]<span class="Apple-converted-space"> </span><br><b>Sent:</b><span class="Apple-converted-space"> </span>Tuesday, October 16, 2012 10:44 PM<br><b>To:</b><span class="Apple-converted-space"> </span>Sergei Larin<br><b>Cc:</b><span class="Apple-converted-space"> </span>'LLVM Developers Mailing List'<br><b>Subject:</b><span class="Apple-converted-space"> </span>Re: [LLVMdev] MI DAG constructor indeterminism<o:p></o:p></span></div></div></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><o:p> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><o:p> </o:p></div><div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; ">On Oct 16, 2012, at 1:43 PM, Sergei Larin <<a href="mailto:slarin@codeaurora.org" style="color: purple; text-decoration: underline; ">slarin@codeaurora.org</a>> wrote:<o:p></o:p></div></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><br><br><o:p></o:p></div><div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span><o:p></o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">Andy,</span><o:p></o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span><o:p></o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> This is less of a question but rather a status quo verification…</span><o:p></o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span><o:p></o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> We currently have certain indeterminism in MI scheduler DAG construction – it is introduces by the use of std::map/std::set during edge traversal.</span><o:p></o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">Result – a random variation in SUnit edge order (which will remain fixed thereafter). Logically, it is the same DAG, but topologically it is a slightly different one, and if some algorithm is dependent on the order of edge traversal, we can have performance and debugging indeterminism. The way I have discovered it – VLIW scheduler can produce identical cost function for a pair of SUs, making visitation order the tie breaker, which is not deterministic per above discussion. For me it is trivial to fix, but I wonder if this might become a source of well hidden issues in the future.</span><o:p></o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> </span><o:p></o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "> I am at this time not proposing anything – a fix is definitely possible, but I wonder what people think about it before I even consider this a bug.</span><o:p></o:p></div></div></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><o:p> </o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; ">This looks like a bug. The edge order could even affect some heuristics and influence codegen.<o:p></o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><o:p> </o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; ">I don't have a better idea than using SetVector/MapVector for Value* keys. For SUnits we could just key on NodeNum. Go ahead and file a bug and/or submit a patch.<o:p></o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; "><o:p> </o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; ">Thanks!<o:p></o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; ">-Andy</div></div></div></div></div></blockquote></div><br></body></html>