[LLVMdev] Extending GetElementPointer, or Premature Linearization Considered Harmful

[Hongbin Zheng]

Hi Preston,

On Fri, May 4, 2012 at 9:12 AM, Preston Briggs <preston.briggs at gmail.com> wrote:
>
> which produces
>
> %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>
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.

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.

best regards
ether

[1]http://llvm.org/viewvc/llvm-project/polly/trunk/lib/Support/SCEVValidator.cpp?view=markup
[2]http://llvm.org/viewvc/llvm-project/polly/trunk/lib/Analysis/ScopInfo.cpp?view=markup