On Mon, Jul 29, 2013 at 4:08 PM, Guo, Xiaoyi <Xiaoyi.Guo at amd.com> wrote:> Hi,**** > > ** ** > > We have a benchmark where there are 128 MAD computations in a loop. (See > the attached IR.) Creating SCEVs for these expressions takes a long time, > making the compile time too long. E.g., running opt with the “indvars” pass > only takes 45 seconds.**** > > ** ** > > It seems that the majority of the time is spent in comparing the > complexity of the expression operands to sort them. >Why not just fix this then? I assume the issue is that they all end up with the same length/complexity, so it both falls into the N^2 loop in GroupByComplexity, and the sort itself takes a long time because it compares operand by operand. This seems easy to fix by having GroupByComplexity calculate a very cheap hash prior to sorting when number of operands is large, and then using that hash before recursively comparing element by element to distinguish the cases. (You could also create/update this hash as you go, but that seems like it would be more work) Unless of course, they really are all the same expression, in which case, this is harder :)> **** > > ** ** > > I realize that the expression grows to be really large towards the end of > the loop.**** > > ** ** > > I don’t know of all the uses of the built SCEV. But I image it won’t be > very useful for such complex expressions. Yet, it’s making the compile time > much longer.**** > > ** ** > > So I’m wondering if it would make sense to abort the creation of SCEV when > the expression gets really complex and large. Or is there any way to > further optimize the performance of SCEV building for such cases.**** > > ** ** > > Thanks in advance for any response.**** > > ** ** > > Xiaoyi**** > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130729/e8d4fd9c/attachment.html>
Thank you very much for your reply. Do you mean calculate the hash based on element SCEV pointers? But according to the comments before GroupByComplexity(): /// Note that we go take special precautions to ensure that we get deterministic /// results from this routine. In other words, we don't want the results of /// this to depend on where the addresses of various SCEV objects happened to /// land in memory. Xiaoyi From: Daniel Berlin [mailto:dberlin at dberlin.org] Sent: Monday, July 29, 2013 4:18 PM To: Guo, Xiaoyi Cc: LLVMdev at cs.uiuc.edu Subject: Re: [LLVMdev] creating SCEV taking too long On Mon, Jul 29, 2013 at 4:08 PM, Guo, Xiaoyi <Xiaoyi.Guo at amd.com<mailto:Xiaoyi.Guo at amd.com>> wrote: Hi, We have a benchmark where there are 128 MAD computations in a loop. (See the attached IR.) Creating SCEVs for these expressions takes a long time, making the compile time too long. E.g., running opt with the "indvars" pass only takes 45 seconds. It seems that the majority of the time is spent in comparing the complexity of the expression operands to sort them. Why not just fix this then? I assume the issue is that they all end up with the same length/complexity, so it both falls into the N^2 loop in GroupByComplexity, and the sort itself takes a long time because it compares operand by operand. This seems easy to fix by having GroupByComplexity calculate a very cheap hash prior to sorting when number of operands is large, and then using that hash before recursively comparing element by element to distinguish the cases. (You could also create/update this hash as you go, but that seems like it would be more work) Unless of course, they really are all the same expression, in which case, this is harder :) I realize that the expression grows to be really large towards the end of the loop. I don't know of all the uses of the built SCEV. But I image it won't be very useful for such complex expressions. Yet, it's making the compile time much longer. So I'm wondering if it would make sense to abort the creation of SCEV when the expression gets really complex and large. Or is there any way to further optimize the performance of SCEV building for such cases. Thanks in advance for any response. Xiaoyi _______________________________________________ LLVM Developers mailing list LLVMdev at cs.uiuc.edu<mailto:LLVMdev at cs.uiuc.edu> http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130730/3ab6f584/attachment.html>
On Mon, Jul 29, 2013 at 8:48 PM, Guo, Xiaoyi <Xiaoyi.Guo at amd.com> wrote:> Thank you very much for your reply. > > > > Do you mean calculate the hash based on element SCEV pointers?No, based on the properties of them (IE type, etc). It will be entirely deterministic You have two cases: Either all these SCEV's are really the same, in which case, this will do nothing Or they are subtly different, but right now it's comparing 128 operands to find out. The hash helps with the second case, but not the first.