<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Hi!<div class="">I like this of course!</div><div class="">A comment about the code that I noticed.<br class=""><div class=""><div><blockquote type="cite" class=""><div class="">On 13 Sep 2015, at 09:03, escha via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="Content-Type" content="text/html charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">LLVM has two similar bits of infrastructure: a simplifyInstructionsInBlock function and a SimplifyInstructions pass, both intended to be lightweight “fix up this code without doing serious optimizations” functions, as far as I can tell. I don’t think either is used in a performance-sensitive place in-tree; the former is mostly called in minor places when doing CFG twiddling, and the latter seems to be for testing purposes.<div class=""><br class=""></div><div class="">However, in our out-of-tree code, I found we were calling simplifyInstructionsInBlock on the entire function to clean things up before another pass. This turns out to be quite costly: the function is not very efficient, tends to revisit instructions more than is necessary, and spends a lot of time constructing weak handles and handling its worklists. I wrote a new version of it that is about ~3x faster and reduced our total compilation time by about 2%. The new version is very very fast: it’s a full-function simplify-and-DCE that looks to be about twice as fast as comparatively “fast” passes like ADCE — fast enough that I can imagine plopping it down in a pipeline pretty much wherever is relevant.</div><div class=""><br class=""></div><div class="">Would anyone be interested in having this in LLVM? It could be a replacement for simplifyInstructionsInBlock, a replacement for SimplifyInstructionsPass, or whatever else is reasonable; I’m mostly just not sure where to put it, and want to be sure it’d be useful to someone (given the current comparative lack of use of this code in-tree). It -should- be NFC compared to simplifyInstructionsInBlock other than running per-function instead of per-block (which can be easily changed, I just made it per-function since that’s what was most useful to us).</div><div class=""><br class=""></div><div class="">—escha</div><div class=""><br class=""></div><div class="">P.S. Here’s the code. The main optimizations here are:</div><div class="">1. Use a worklist, not a recursive approach, to avoid needless revisitation and being repeatedly forced to jump back to the start of the BB if a handle is invalidated.</div><div class="">2. Only insert operands to the worklist if they become unused after a dead instruction is removed, so we don’t have to visit them again in most cases.</div><div class="">3. Use a SmallSetVector to track the worklist.</div><div class="">4. Instead of pre-initting the SmallSetVector like in DeadCodeEliminationPass, only put things into the worklist if they have to be revisited after the first run-through. This minimizes how much the actual SmallSetVector gets used, which saves a lot of time.</div><div class=""><br class=""></div><div class=""><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">static</span> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">bool</span> simplifyAndDCEInstruction(<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Instruction</span> *I,</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">SmallSetVector</span><<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Instruction</span> *, <span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">16</span>> &WorkList,</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">const</span> <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">DataLayout</span> &DL) {</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(49, 89, 93);" class=""><span style="" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">if</span><span style="" class=""> (</span>isInstructionTriviallyDead<span style="" class="">(I, </span><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">nullptr</span><span style="" class="">)) {</span></div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>// Loop over all of the values that the instruction uses. If there are</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>// instructions being used, add them to the worklist, because they might</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>// go dead after this one is removed.</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">SmallVector</span><<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Instruction</span> *, <span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">8</span>> Operands;</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">for</span> (<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">User</span>::<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">op_iterator</span> OI = I-><span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">op_begin</span>(), E = I-><span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">op_end</span>(); OI != E; ++OI)</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">if</span> (<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Instruction</span> *Used = <span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">dyn_cast</span><<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Instruction</span>>(*OI))</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> Operands.<span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">push_back</span>(Used);</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>// Remove the instruction.</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(49, 89, 93);" class=""><span style="" class=""> I-></span>eraseFromParent<span style="" class="">();</span></div><div style="margin: 0px; font-size: 11px; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>// Only add the operands to the worklist if their uses are now empty,</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>// to avoid needlessly revisiting instructions.</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">for</span> (<span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">auto</span> U : Operands)</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">if</span> (U-><span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">use_empty</span>())</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> WorkList.<span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">insert</span>(U);</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; min-height: 13px;" class=""><br class=""></div></div></div></div></blockquote><div><br class=""></div><div>Instead of adding the operands to a list, erase the instruction and add them to the worklist wouldn’t be probably faster something like:</div><div><br class=""></div><div>if (Instruction *Used = dyn_cast<Instruction>(*OI))</div><div> if (Used->hasOneUse())</div><div> WorkList.insert(Used);</div><div><br class=""></div><div>If it has one use is going to be the instruction we are going to remove anyway, right?</div><div><br class=""></div><div><br class=""></div>Cheers,</div><div>Marcello<br class=""><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(187, 44, 162);" class=""><span style="" class=""> </span>return<span style="" class=""> </span>true<span style="" class="">;</span></div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> }</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">if</span> (<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Value</span> *SimpleV = <span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">SimplifyInstruction</span>(I, DL)) {</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>// Add the users to the worklist.</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">for</span> (<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">User</span> *U : I-><span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">users</span>())</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> WorkList.<span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">insert</span>(<span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">cast</span><<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Instruction</span>>(U));</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>// Replace the instruction with its simplified value.</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(49, 89, 93);" class=""><span style="" class=""> I-></span>replaceAllUsesWith<span style="" class="">(SimpleV);</span></div><div style="margin: 0px; font-size: 11px; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>// Gracefully handle edge cases where the instruction is not wired into any</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>// parent block.</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">if</span> (I-><span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">getParent</span>())</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(49, 89, 93);" class=""><span style="" class=""> I-></span>eraseFromParent<span style="" class="">();</span></div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(187, 44, 162);" class=""><span style="" class=""> </span>return<span style="" class=""> </span>true<span style="" class="">;</span></div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> }</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(187, 44, 162);" class=""><span style="" class=""> </span>return<span style="" class=""> </span>false<span style="" class="">;</span></div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class="">}</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(0, 132, 0);" class="">// A faster version of SimplifyInstructionsInBlock, designed for a whole</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(0, 132, 0);" class="">// function. Modelled after DeadCodeEliminationPass.</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">static</span> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">bool</span> simplifyAndDCEFunction(<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Function</span> &F) {</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">bool</span> MadeChange = <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">false</span>;</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(49, 89, 93);" class=""><span style="" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">const</span><span style="" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">DataLayout</span><span style="" class=""> &DL = F.</span>getParent<span style="" class="">()-></span>getDataLayout<span style="" class="">();</span></div><div style="margin: 0px; font-size: 11px; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">SmallSetVector</span><<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Instruction</span> *, <span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">16</span>> WorkList;</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>// Iterate over the original function, only adding insts to the worklist</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>// if they actually need to be revisited. This avoids having to pre-init</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>// the worklist with the entire function's worth of instructions.</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">for</span> (<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">inst_iterator</span> FI = <span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">inst_begin</span>(F), FE = <span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">inst_end</span>(F); FI != FE;) {</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Instruction</span> *I = &*FI;</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> ++FI;</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>// We're visiting this instruction now, so make sure it's not in the</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>// worklist from an earlier visit.</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> WorkList.<span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">remove</span>(I);</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> MadeChange |= <span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">simplifyAndDCEInstruction</span>(I, WorkList, DL);</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> }</div><div style="margin: 0px; font-size: 11px; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">while</span> (!WorkList.<span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">empty</span>()) {</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Instruction</span> *I = WorkList.<span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">pop_back_val</span>();</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> MadeChange |= <span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">simplifyAndDCEInstruction</span>(I, WorkList, DL);</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> }</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">return</span> MadeChange;</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class="">}</div></div></div>_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br class=""></div></blockquote></div><br class=""></div></div></body></html>