llvm dev - Jun 2015 - [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.

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.

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