<div dir="ltr">On Thu, May 15, 2014 at 9:31 AM, Philip Reames <span dir="ltr"><<a href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF"><div class="">
<div>On 05/14/2014 06:02 PM, Akira Hatanaka
wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">
<div>I would like to get feedback from the community on how I
can speed up the compilation of a function that has one huge
basic block consisting of over 150K instructions. It takes
about 10 minutes for clang to produce the object file and the
function that is taking up the majority of the time is
LoadAndStorePromoter::run, which is called when SROA is run:</div>
<div><br>
</div>
<div>
<p style="margin:0px;font-size:11px;font-family:Menlo"> //
Otherwise, we have mixed loads and stores (or just a bunch
of stores).</p>
<p style="margin:0px;font-size:11px;font-family:Menlo"> //
Since SSAUpdater is purely for cross-block values, we need
to determine</p>
<p style="margin:0px;font-size:11px;font-family:Menlo"> //
the order of these instructions in the block. If the first
use in the</p>
<p style="margin:0px;font-size:11px;font-family:Menlo"> //
block is a load, then it uses the live in value. The last
store defines</p>
<p style="margin:0px;font-size:11px;font-family:Menlo"> //
the live out value. We handle this by doing a linear scan
of the block.</p>
<p style="margin:0px;font-size:11px;font-family:Menlo">
Value *StoredValue = nullptr;</p>
<p style="margin:0px;font-size:11px;font-family:Menlo"> for
(BasicBlock::iterator II = BB->begin(), E = BB->end();
II != E; ++II) {</p>
<p style="margin:0px;font-size:11px;font-family:Menlo"><br>
</p>
<p style="margin:0px">
If I understand this code
correctly. LoadAndStorePromoter::run is called once per
every promotable alloca and iterates over the whole list to
determine the order of loads and stores in the basic block
that access the alloca.</p>
</div>
</div>
</blockquote></div>
I'm a bit confused about the cost here. Based on the code, I see us
walking each basic block at most once per alloca. Even at 150K
instructions, I wouldn't expect the loop to take *that* long. How
many allocas are you dealing with?<br>
<br>
I do see an outer loop in SROA::performPromotion. Are you possibly
triggering a large number of iterations there? That would make the
inner loop appear much more expensive. <br><div class="">
<br></div></div></blockquote><div><br></div><div>The unoptimized bitcode (compiled with clang -O0) has a large number of allocas (over 7000), which I think is also contributing to the long compilation time.</div><div>
<br></div><div>But making LoadAndStorePromoter::run faster is sufficient to reduce the compilation time (at least in my case).</div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF"><div class="">
<blockquote type="cite">
<div dir="ltr">
<div>
<p style="margin:0px"><br>
</p>
<p style="margin:0px">This is the list of ideas I have
considered or implemented that can possibly solve my
problem:</p>
<p style="margin:0px"><br>
</p>
<p style="margin:0px">1. In SROA::getAnalysisUsage, always
require DominatorTreeWrapperPass. This will enable
SROA::promoteAllocas to use mem2reg, which is fast because
it caches the per basic-block ordering of the relevant loads
and stores. If it's important to avoid always computing the
dominator tree, computing it conditionally based on whether
there is a huge basic block in the function is another idea,
but I am not sure if that is possible (I don't think this is
currently supported).</p>
<p style="margin:0px"><br>
</p>
<p style="margin:0px">This brings down the compilation time
(using clang -emit-llvm) from 350s to 30s (it still takes
about 23s to do GVN). It also might fix PR17855 (the program
that used to take 65s to compile now takes just 11s):</p>
<p style="margin:0px"><br>
</p>
<p style="margin:0px"><a href="http://llvm.org/bugs/show_bug.cgi?id=17855" target="_blank">http://llvm.org/bugs/show_bug.cgi?id=17855</a><br>
</p>
</div>
</div>
</blockquote></div>
Chandler commented here, I'll defer to him. <br><div class="">
<blockquote type="cite">
<div dir="ltr">
<div>
<p style="margin:0px"><br>
</p>
<p style="margin:0px">
2. Cache the ordering of loads and stores in
LoadAndStorePromoter::run. I don't know how hard it would be
to implement this, but I think it would be as fast as 1
(using mem2reg).</p>
</div>
</div>
</blockquote></div>
Caching the first load and first store for each alloca in a single
pass doesn't seem too bad. (Assuming that that doesn't change
across iterations at least - I'm not particularly familiar with this
code.) This seems like a fairly isolated improvement. Assuming
Chandler doesn't disagree, I'd say this seems like a reasonable
first step. <br><div class="">
<blockquote type="cite">
<div dir="ltr">
<div>
<p style="margin:0px"><br>
</p>
<p style="margin:0px">
3. Insert a pass that splits huge basic blocks into smaller
blocks prior to SROA and recombine them after the pass is
run.</p>
</div>
</div>
</blockquote></div>
How would this actually help? If you have uses in each of the split
blocks, wouldn't you spend the exact same time? <br><div class="">
<blockquote type="cite">
<div dir="ltr">
<div>
<p style="margin:0px"><br></p></div></div></blockquote></div></div></blockquote><div>It might not help much. The code in LoadAndStorePromoter::run avoids scanning all instructions in a basic block if either there is only one user in a basic block or there are no stores in a basic block, and splitting blocks might increase the number of such blocks.<br>
</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div text="#000000" bgcolor="#FFFFFF">
<div class=""><blockquote type="cite"><div dir="ltr"><div><p style="margin:0px">4. Change the definition of class
Instruction in IR/Instruction.h so that determining whether
one instruction precedes another becomes more efficient. My
current implementation brings down the compilation time to
just 6s.</p>
<p style="margin:0px"><br>
</p>
<p style="margin:0px">I won't go into much detail about the
change I made, but it basically replaces Instruction's
pointer to its parent BasicBlock with another data
structure. I haven't done much investigation into how this
will affect the common case.</p>
<p style="margin:0px"><br>
</p>
<div>This will also help speed up the execution of code in
other places. For example, these two functions are called
when GVN::processLoad is called and iterate over a basic
block's instruction list to determine the order of two (load
and stores) instructions.:</div>
<p style="margin:0px"><br>
</p>
<p style="margin:0px;font-size:11px;font-family:Menlo"><span style="font-family:arial;font-size:small">llvm::isPotentiallyReachable</span></p>
<p style="margin:0px;font-size:11px;font-family:Menlo">
<br>
</p>
<p style="margin:0px;font-size:11px;font-family:Menlo"> //
Linear scan, start at 'A', see whether we hit 'B' or the end
first.</p>
<p style="margin:0px;font-size:11px;font-family:Menlo"> for
(BasicBlock::const_iterator I = A, E = BB->end(); I != E;
++I) {</p>
<p style="margin:0px;font-size:11px;font-family:Menlo">
if (&*I == B)</p>
<p style="margin:0px;font-size:11px;font-family:Menlo">
return true;</p>
<p style="margin:0px;font-size:11px;font-family:Menlo">
}</p>
<div><br>
</div>
<div>DominatorTree::dominates</div>
<div><br>
</div>
<div>
<p style="margin:0px;font-size:11px;font-family:Menlo"> //
Loop through the basic block until we find Def or User.</p>
<p style="margin:0px;font-size:11px;font-family:Menlo">
BasicBlock::const_iterator I = DefBB->begin();</p>
<p style="margin:0px;font-size:11px;font-family:Menlo"> for
(; &*I != Def && &*I != User; ++I)</p>
<p style="margin:0px;font-size:11px;font-family:Menlo">
/*empty*/;</p>
</div>
</div>
</div>
</blockquote></div>
I'd be curious to see a proposal here. I've been bitten by the
DT::dominates issue myself. <br><div class="">
<blockquote type="cite">
<div dir="ltr">
<div>
<div><br></div></div></div></blockquote></div></div></blockquote><div>I was hesitant to make changes in classes such as BasicBlock and Instruction just to make it faster to compile a basic block with 150K+ instructions (which I think is a pathological case). If there are other use cases that need discovering orders of instructions in a basic block, it might be worth considering fixing those classes.</div>
<div> </div><div>The attached patch is the current implementation I have. Basically I am trying to make function Instruction::precede fast and use it to speed up functions that are currently iterating over the whole instruction list to determine the order of instructions in a basic block. </div>
<div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div text="#000000" bgcolor="#FFFFFF"><div class="">
<blockquote type="cite"><div dir="ltr"><div><div>
</div>
<p style="margin:0px">5. Simply give up doing SROA (and
GVN::processLoad) if there is a huge basic block that can
potentially take a long time to compile.</p>
</div>
</div>
</blockquote></div>
Until we have something better, this might be a necessary hack.
Whether it's actually worth introducing depends on how long Chandler
thinks the mem2reg version will take to land. <br><span class=""><font color="#888888">
<br></font></span></div></blockquote><div><br></div><div>I tried this idea today, and unfortunately it didn't reduce the compilation time. Skipping SROA leaves a lot of loads/stores in the code that could have been promoted, and that places the burden on other passes that are run later, such as GVN and DSE.</div>
<div> </div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div text="#000000" bgcolor="#FFFFFF">
<span class=""><font color="#888888">
Philip<br>
<br>
</font></span></div>
</blockquote></div><br></div></div>