Tobias Edler von Koch
2015-Jun-02 16:32 UTC
[LLVMdev] BasicAA unable to analyze recursive PHI nodes
Hi all, I came across the following limitation in our BasicAliasAnalysis. This happens with the following IR pattern: %x = phi [ %incptr, ... ] [ %var, ... ] %incptr = getelementptr %x, 1 We will basically always return MayAlias for %x and any other value because aliasPHI recurses on the first value and gives up. There are, however, many cases where this is too conservative. Take the following example: typedef struct { unsigned num_words; unsigned word_ofs; const unsigned *data; } section_t; void test(section_t* restrict section, unsigned* restrict dst) { while (section->data != NULL) { const unsigned *src = section->data; for (unsigned i=0; i < section->num_words; ++i) { dst[section->word_ofs + i] = src[i]; } ++section; } } There is no need to reload section->word_ofs on every iteration of the for loop, but due to the limitation described above, we're unable to tell that section doesn't alias with dst inside the loop. I have a fix, but would like to discuss it here first. In aliasPHI, we can detect incoming values that are recursive GEPs with a constant offset. Instead of treating them as an ordinary incoming value, I instead create a temporary GEP expression with an undef offset for every other (non-recursive) incoming value and then let aliasPHI do its usual analysis for each of those. In the example above, %x = phi [ %incptr, ... ] [ %var, ... ] %incptr = getelementptr %x, 1 the incoming values of %x would become, for the purpose of analysis in aliasPHI: getelementptr %var, undef and %var I believe the undef GEP correctly represents the various offsets by which %x advances across all iterations. I'm not seeing any regressions on our test suites with this solution (and some good performance improvements). Any thoughts? Can anyone think of a better solution? I'm happy to post the patch if this is OK. Tobias -- Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project.
Tobias Edler von Koch
2015-Jun-10 22:32 UTC
[LLVMdev] BasicAA unable to analyze recursive PHI nodes
On Tue, 2 Jun 2015 11:32:13 -0500 Tobias Edler von Koch <tobias at codeaurora.org> wrote:> Hi all, > > I came across the following limitation in our BasicAliasAnalysis. This > happens with the following IR pattern: > > %x = phi [ %incptr, ... ] [ %var, ... ] > %incptr = getelementptr %x, 1 > > We will basically always return MayAlias for %x and any other value > because aliasPHI recurses on the first value and gives up.Patch now posted as http://reviews.llvm.org/D10368 Tobias -- Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project.
Daniel Berlin
2015-Jun-10 22:44 UTC
[LLVMdev] BasicAA unable to analyze recursive PHI nodes
What is the compile time impact? Basic AA is supposed to be basic, not catch every case On Wed, Jun 10, 2015, 3:33 PM Tobias Edler von Koch <tobias at codeaurora.org> wrote:> On Tue, 2 Jun 2015 11:32:13 -0500 Tobias Edler von Koch > <tobias at codeaurora.org> wrote: > > > Hi all, > > > > I came across the following limitation in our BasicAliasAnalysis. This > > happens with the following IR pattern: > > > > %x = phi [ %incptr, ... ] [ %var, ... ] > > %incptr = getelementptr %x, 1 > > > > We will basically always return MayAlias for %x and any other value > > because aliasPHI recurses on the first value and gives up. > > Patch now posted as http://reviews.llvm.org/D10368 > > Tobias > > -- > Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a > Linux Foundation Collaborative Project. > _______________________________________________ > 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/20150610/97b82969/attachment.html>
Sorry for missing this the first time around, but I think -scev-aa does what you want. I've commented on the phabricator review. On Wed, Jun 10, 2015 at 3:32 PM, Tobias Edler von Koch <tobias at codeaurora.org> wrote:> On Tue, 2 Jun 2015 11:32:13 -0500 Tobias Edler von Koch > <tobias at codeaurora.org> wrote: > >> Hi all, >> >> I came across the following limitation in our BasicAliasAnalysis. This >> happens with the following IR pattern: >> >> %x = phi [ %incptr, ... ] [ %var, ... ] >> %incptr = getelementptr %x, 1 >> >> We will basically always return MayAlias for %x and any other value >> because aliasPHI recurses on the first value and gives up. > > Patch now posted as http://reviews.llvm.org/D10368 > > Tobias > > -- > Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a > Linux Foundation Collaborative Project. > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Possibly Parallel Threads
- [LLVMdev] BasicAA unable to analyze recursive PHI nodes
- [LLVMdev] BasicAA unable to analyze recursive PHI nodes
- [LLVMdev] BasicAA unable to analyze recursive PHI nodes
- [LLVMdev] BasicAA unable to analyze recursive PHI nodes
- CloneFunction during LTO leads to seg fault?