<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-cite-prefix">This seems like a useful change to me.
Why don't you post it for review on llvm-commits?<br>
<br>
This seems rather similar to both
RecursivelyDeleteTriviallyDeadInstructions and
replaceAndRecursivelySimplifyImpl. I think at least your single
user trick should be applied to those as well. Given how similar
all three are, I'm be tempted to common them into a common
implementation. <br>
<br>
Philip<br>
<br>
<br>
<br>
On 09/13/2015 09:03 AM, escha via llvm-dev wrote:<br>
</div>
<blockquote
cite="mid:1F6CE7BC-7B6B-41DF-B52E-D793400802F6@apple.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
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="font-variant-ligatures: no-common-ligatures; color:
#000000" class=""> </span><span
style="font-variant-ligatures: no-common-ligatures; color:
#bb2ca2" class="">if</span><span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" class=""> (</span>isInstructionTriviallyDead<span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" class="">(I, </span><span
style="font-variant-ligatures: no-common-ligatures; color:
#bb2ca2" class="">nullptr</span><span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" class="">)) {</span></div>
<div style="margin: 0px; font-size: 11px; font-family: Menlo;
color: rgb(0, 132, 0);" class=""><span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" 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="font-variant-ligatures: no-common-ligatures; color:
#000000" 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="font-variant-ligatures: no-common-ligatures; color:
#000000" 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="font-variant-ligatures: no-common-ligatures; color:
#000000" class=""> </span>// Remove the instruction.</div>
<div style="margin: 0px; font-size: 11px; font-family: Menlo;
color: rgb(49, 89, 93);" class=""><span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" class=""> I-></span>eraseFromParent<span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" 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="font-variant-ligatures: no-common-ligatures; color:
#000000" 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="font-variant-ligatures: no-common-ligatures; color:
#000000" 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 style="margin: 0px; font-size: 11px; font-family: Menlo;
color: rgb(187, 44, 162);" class=""><span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" class=""> </span>return<span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" class=""> </span>true<span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" 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="font-variant-ligatures: no-common-ligatures; color:
#000000" 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="font-variant-ligatures: no-common-ligatures; color:
#000000" 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="font-variant-ligatures: no-common-ligatures; color:
#000000" class=""> I-></span>replaceAllUsesWith<span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" 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="font-variant-ligatures: no-common-ligatures; color:
#000000" 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="font-variant-ligatures: no-common-ligatures; color:
#000000" 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="font-variant-ligatures: no-common-ligatures; color:
#000000" class=""> I-></span>eraseFromParent<span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" class="">();</span></div>
<div style="margin: 0px; font-size: 11px; font-family: Menlo;
color: rgb(187, 44, 162);" class=""><span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" class=""> </span>return<span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" class=""> </span>true<span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" 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="font-variant-ligatures: no-common-ligatures; color:
#000000" class=""> </span>return<span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" class=""> </span>false<span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" 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="font-variant-ligatures: no-common-ligatures; color:
#000000" class=""> </span><span
style="font-variant-ligatures: no-common-ligatures; color:
#bb2ca2" class="">const</span><span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" class=""> </span><span
style="font-variant-ligatures: no-common-ligatures; color:
#4f8187" class="">DataLayout</span><span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" class=""> &DL = F.</span>getParent<span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" class="">()-></span>getDataLayout<span
style="font-variant-ligatures: no-common-ligatures; color:
#000000" 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="font-variant-ligatures: no-common-ligatures; color:
#000000" 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="font-variant-ligatures: no-common-ligatures; color:
#000000" 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="font-variant-ligatures: no-common-ligatures; color:
#000000" 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="font-variant-ligatures: no-common-ligatures; color:
#000000" 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="font-variant-ligatures: no-common-ligatures; color:
#000000" 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>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
</body>
</html>