[LLVMdev] [polly] scev codegen (first step to remove the dependence on ivcanon pass)

[Sebastian Pop]

Hi Tobi,

I would like to remove the SCEVRewriter code and replace it with a call to
SCEVAddRec::apply (see attached a patch that adds just this function).  More
precisely I want to add another function called apply_map that applies a map
(loop -> expr) on a given scev.  This is the apply function on a multi-variate
polynomial.

So here is an overview of how I would like the scev code generator to work on an
example: supposing that we have a Stmt_1 that gets code generated by either
CLooG or ISL-codegen like this:

  Stmt_1(c1, c1+4, c1+c2);

we will construct a map that maps the old iteration domain with 3 dimensions
(there are 3 arguments in Stmt_1 representing the original loop nest in which
Stmt_1 was located, let's call the original loop nest loop_1, loop_2, loop_3) to
the new expressions generated by cloog that are function of the new iteration
domain with 2 dimensions (c1 and c2 are the new induction variables of the code
generated by cloog).  So the content of that map is:

loop_1 -> c1
loop_2 -> c1+7
loop_3 -> c1+c2

Given an access function from the original program: 
  Scev_1 = {{{0, +, 4}_1, +, 5}_2, +, 6}_3

we will apply the map on it, and we will get a symbolic expression function of
the new induction variables c1, and c2:

Scev_2 = apply (loop_1 -> c1)    on Scev_1 = {{4*c1, +, 5}_2, +, 6}_3
Scev_3 = apply (loop_2 -> c1+7)  on Scev_2 = {4*c1 + 5*(c1+7), +, 6}_3
Scev_4 = apply (loop_3 -> c1+c2) on Scev_3 = 4*c1 + 5*(c1+7) + 6*(c1+c2)

We will then code generate Scev_4 and we will use this new expression for the
array access in the new loop nest.

Remark that in all this process we have never referred to the original
"canonical induction variable".  SCEV actually provides such a canonical form
for the induction variables without having to transform the code.

Sebastian
-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-add-SCEVAddRecExpr-apply.patch
Type: text/x-diff
Size: 2628 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121130/69edcf56/attachment.patch>