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
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.
In our case basicaa alone returns “may alias” on our pointers and we want to override that with tbaa data to “Wont alias” when we know that the pointers will never alias. So its not covered by your case.
Since the basicaa pass doesnt chain according to the llvm docs, it should have the last chance to affect the aliasing information, and that means it should be added first. If so the existing code in addInitialAliasAnalysisPasses has them round the wrong way.
In our case basicaa alone returns "may alias" on our pointers and we want to override that with tbaa data to "Wont alias" when we know that the pointers will never alias. So its not covered by your case.
Since the basicaa pass doesnt chain according to the llvm docs, it should have the last chance to affect the aliasing information, and that means it should be added first. If so the existing code in addInitialAliasAnalysisPasses has them round the wrong way.
Ah, the docs were out of date. Basic-aa does chain now.
> 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
Attached is a test case. Using 2.9 opt with -basicaa -tbaa in either order plus -gvn the code is optimized well, computed values are reused, etc. because the stores and non aliasing.
Using llvm 3.0 the order of basicaa and tbaa makes a difference: -basicaa -tbaa optimizes, -tbaa -basicaa doesnt. That’s why I tried reversing the order of calls in the alias analysis pass setup.
tbaa2.ll (2.37 KB)
Yes. And looking at the testcase, this appears to be the problem.
Dan
Is this issue still active? It sounded as though Dan or Hal were looking at it but I havent seen an response. Should I resubmit as a bug so it gets tracked?
thanks for your help
Maurice,
I think that your best option is to submit a patch that adds an option
to turn off the problematic overriding. As Dan confirmed, there is a
comment at the end of BasicAliasAnalysis::aliasGEP regarding "protecting
TBAA in the case of dynamic indices into arrays of unions", and the
logic at issue can be found there. Would a command-line option work for
you?
-Hal