Our application generates IR that is used to generate X86_64 code for a Jit. We noticed that code generated with llvm 3.0 is worse in some circumstances that it was with 2.9. I traced the differences to alias analysis differences. Our IR references data structures that have lots of derived pointers and we use extensive tbaa metadata to indicate which pointers dont alias. Some of this seemed to be getting ignored in 3.0. I found by using opt on our IR that the ordering of the basicaa and tbaa optimization passes made all the difference. Code in addInitialAliasAnalysisPasses() adds the tbaa pass then basicaa pass. From Chris' comments in the forum about backward chaining of alais analysis that would execute basicaa before tbaa - and that would have the effect of basicaa doing the first pass of analysis followed by tbaa, possibly overriding the "wont alias" information we provided in the IR. The comments in the code imply that tbaa executes first. As an experiment I reversed the order of the passes in addInitialAliasAnalysisPasses, rebuilt llvm 3.0 and our application and reran our alias tests. Now we get the same (good) results as llvm 2.9. So my question is - which order is correct? I would expect that explicit tbaa tags that say that some pointers dont alias should have precedence. I can provide a fairly small .ll test case if necessary. thanks for your help and advice /maurice -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120127/b0c2060d/attachment.html>
On Jan 27, 2012, at 4:15 PM, Maurice Marks wrote:> Our application generates IR that is used to generate X86_64 code for a Jit. We noticed that code generated with llvm 3.0 is worse in some circumstances that it was with 2.9. I traced the differences to alias analysis differences. Our IR references data structures that have lots of derived pointers and we use extensive tbaa metadata to indicate which pointers dont alias. Some of this seemed to be getting ignored in 3.0. I found by using opt on our IR that the ordering of the basicaa and tbaa optimization passes made all the difference. Code in addInitialAliasAnalysisPasses() adds the tbaa pass then basicaa pass. From Chris' comments in the forum about backward chaining of alais analysis that would execute basicaa before tbaa - and that would have the effect of basicaa doing the first pass of analysis followed by tbaa, possibly overriding the "wont alias" information we provided in the IR. The comments in the code imply that tbaa executes first. > > As an experiment I reversed the order of the passes in addInitialAliasAnalysisPasses, rebuilt llvm 3.0 and our application and reran our alias tests. Now we get the same (good) results as llvm 2.9. > > So my question is - which order is correct? I would expect that explicit tbaa tags that say that some pointers dont alias should have precedence.The intention is for BasicAA to take precedence over TBAA. Whenever BasicAA says MustAlias, it's because the pointers really do alias, even if TBAA would say NoAlias. There's no utility in letting TBAA's NoAlias win in this case, because the code is either intentionally type punning, or it's buggy. There is one special case where BasicAA can't determine the aliasing relationship and still overrides TBAA, which is the case where the two memory locations have the same base address and potentially differing dynamic offsets. Special-casing this is a mild hack used to work around the fact that the TBAA implementation can't easily do the right thing for C code in the real world. Possibly this is causing the loss of precision you're seeing. Dan
Many of our pointers point into a structure where they could be considered as having the same base address. We use tbaa to indicate which ones could or could not alias because they are pointing into different substructures. This is exactly the sort of requirement that invoked the need for the restrict modifier in g++, c++0x etc. If I understand you correctly that cannot be expressed in llvm ir because it would be overridden by basicaa being conservative, overriding the explicit metadata. Is that true? It does make a big difference to optimization in our case, and based on early posters in the forum we aren't the only users to have a concern in this area. On Fri, Jan 27, 2012 at 6:46 PM, Dan Gohman <gohman at apple.com> wrote:> On Jan 27, 2012, at 4:15 PM, Maurice Marks wrote: > > > Our application generates IR that is used to generate X86_64 code for a > Jit. We noticed that code generated with llvm 3.0 is worse in some > circumstances that it was with 2.9. I traced the differences to alias > analysis differences. Our IR references data structures that have lots of > derived pointers and we use extensive tbaa metadata to indicate which > pointers dont alias. Some of this seemed to be getting ignored in 3.0. I > found by using opt on our IR that the ordering of the basicaa and tbaa > optimization passes made all the difference. Code in > addInitialAliasAnalysisPasses() adds the tbaa pass then basicaa pass. From > Chris' comments in the forum about backward chaining of alais analysis that > would execute basicaa before tbaa - and that would have the effect of > basicaa doing the first pass of analysis followed by tbaa, possibly > overriding the "wont alias" information we provided in the IR. The > comments in the code imply that tbaa executes first. > > > > As an experiment I reversed the order of the passes in > addInitialAliasAnalysisPasses, rebuilt llvm 3.0 and our application and > reran our alias tests. Now we get the same (good) results as llvm 2.9. > > > > So my question is - which order is correct? I would expect that explicit > tbaa tags that say that some pointers dont alias should have precedence. > > The intention is for BasicAA to take precedence over TBAA. > > Whenever BasicAA says MustAlias, it's because the pointers really > do alias, even if TBAA would say NoAlias. There's no utility in > letting TBAA's NoAlias win in this case, because the code is > either intentionally type punning, or it's buggy. > > There is one special case where BasicAA can't determine the > aliasing relationship and still overrides TBAA, which is the case > where the two memory locations have the same base address and > potentially differing dynamic offsets. Special-casing this is a > mild hack used to work around the fact that the TBAA implementation > can't easily do the right thing for C code in the real world. > Possibly this is causing the loss of precision you're seeing. > > Dan > >-- Not sent from my Blackberry, Raspberry or Gooseberry! -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120128/001fb5c9/attachment.html>
On Fri, 2012-01-27 at 16:46 -0800, Dan Gohman wrote:> On Jan 27, 2012, at 4:15 PM, Maurice Marks wrote: > > > Our application generates IR that is used to generate X86_64 code for a Jit. We noticed that code generated with llvm 3.0 is worse in some circumstances that it was with 2.9. I traced the differences to alias analysis differences. Our IR references data structures that have lots of derived pointers and we use extensive tbaa metadata to indicate which pointers dont alias. Some of this seemed to be getting ignored in 3.0. I found by using opt on our IR that the ordering of the basicaa and tbaa optimization passes made all the difference. Code in addInitialAliasAnalysisPasses() adds the tbaa pass then basicaa pass. From Chris' comments in the forum about backward chaining of alais analysis that would execute basicaa before tbaa - and that would have the effect of basicaa doing the first pass of analysis followed by tbaa, possibly overriding the "wont alias" information we provided in the IR. The comments in the code imply that tbaa executes first. > > > > As an experiment I reversed the order of the passes in addInitialAliasAnalysisPasses, rebuilt llvm 3.0 and our application and reran our alias tests. Now we get the same (good) results as llvm 2.9. > > > > So my question is - which order is correct? I would expect that explicit tbaa tags that say that some pointers dont alias should have precedence. > > The intention is for BasicAA to take precedence over TBAA. > > Whenever BasicAA says MustAlias, it's because the pointers really > do alias, even if TBAA would say NoAlias. There's no utility in > letting TBAA's NoAlias win in this case, because the code is > either intentionally type punning, or it's buggy. > > There is one special case where BasicAA can't determine the > aliasing relationship and still overrides TBAA, which is the case > where the two memory locations have the same base address and > potentially differing dynamic offsets. Special-casing this is a > mild hack used to work around the fact that the TBAA implementation > can't easily do the right thing for C code in the real world. > Possibly this is causing the loss of precision you're seeing.Maurice, can you please provide a test case that demonstrates the problem that you're seeing? Dan, where in the code is this done? I see a comment at the end of BasicAliasAnalysis::aliasGEP regarding "protecting TBAA in the case of dynamic indices into arrays of unions"; are you referring to that? -Hal> > Dan > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev-- Hal Finkel Postdoctoral Appointee Leadership Computing Facility Argonne National Laboratory