[LLVMdev] BasicAA unable to analyze recursive PHI nodes

[Tobias Edler von Koch]

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.