[LLVMdev] Extending GetElementPointer, or Premature Linearization Considered Harmful

[Preston Briggs]

Hi Ether,

> Preston wrote:
> > %arrayidx24 = getelementptr inbounds [100 x [100 x i64]]* %A, i64
> > %arrayidx21.sum, i64 %add1411, i64 %add
> > store i64 0, i64* %arrayidx24, align 8
> > {{{(5 + ((3 + %n) * %n)),+,(2 * %n * %n)}<%for.cond1.preheader>,+,(4 * %n)}<%for.cond4.preheader>,+,6}<%for.cond7.preheader>

And Ether replied:
> This expression is not straight forward because llvm always fold the
> loop invariant in the AddExpr into the AddRecExpr.
> If I understand the AddRecExpr correctly, the above SCEV is equivalent to:
> (5 + ((3 + %n) * %n)) + (2 * %n * %n) * {0,+,1}<%for.cond1.preheader>
> + (4 * %n) * {0,+,1}<%for.cond4.preheader> + 6 *
> {0,+,1}<%for.cond7.preheader>
> In the above example, you can treat {0,+,1}<%for.cond1.preheader>,
> {0,+,1}<%for.cond4.preheader> and {0,+,1}<%for.cond7.preheader> as the
> (virtual) canonical induction variables of the corresponding loop,
> which start from 0, and increased by 1 in every iteration.

Well, these are two representations of the same thing.
I think they're both equally easy to interpret.
When we see an SECV like {a, +, b}<loop.i>, we can interpret it as [a
+ b*i] directly, or first rewrite it as a + b*{0, +, 1}, doesn't
matter.

> In this case, you may need to introduce your own data structure to
> represent linear expressions, which re-organize the sub-expressions in
> SCEV in form of what you want. To construct the linear expressions,
> you need to visit and analyze all sub-expressions in the SCEV, instead
> of simply looking at the top-level SCEV. Maybe you could have a look
> at the SCEVValidator[1], which check if a SCEV is affine, and and
> SCEVAffinator[2], which build a kind of affine expression from SCEV,
> all of them need to visit and analyze all sub-expressions in the SCEV.

I've written various bits of code that exhaustively explore SCEVs;
that's not the difficulty. The hard part is taking something like:

{{{((7 + (104 * %n)) * %n),+,((8 + (200 * %n)) *
%n)}<%for.cond1.preheader>,+,(305 * %n *
%n)}<%for.cond4.preheader>,+,(9 + (6 * %n * %n))}<%for.body6>

and figuring out the number of subscripts and what they might be.
I'm sure there are 3 indices, call them i, j, and k.
2 of the subscripts have bounds of n,
but figuring out that one has a bound of 100 seems hard.
And how many subscripts are there?

i appears in 2 subscripts, one with stride 8, but the other might be
any factor of 200.
j appears would seem to appear in 2 subscripts, but they're hard to prove.
k appears in 2 subscripts, one with stride 9 and one with stride 6.

Knowing somehow that there's a bound of 100 in one of the subscripts
would help a lot, but how to prove that?

Note that this is example is affine; it confuses us because some of
the subscripts are coupled.

Extending the GEP, my real goal, avoid this confusion.

Thanks,
Preston