[LLVMdev] Contributing to Polly with GSOC 2011

[Tobias Grosser]

On 03/24/2011 10:41 PM, ether zhhb wrote:
> hi tobi,
>>
>> Great. How do you plan to derive the minimal size needed for an
>> induction variable?
> hmm? never thought about this, can we compute the minimal size of the
> induction variable from the size of iterate domain and the wrapping
> information?

I think this is a good approach.

Here an example

   for (int i = 0; i < N; i++)
     Stmt(i);

We can use the type information to restrict the loop dimensions to the 
limits of the types. This means we add for each loop something like
-(2^31) <= i < (2^31)-1 to the domain.

This will yield to such a code after code generation.

Here we can now derive that an i32 is sufficient, to store s. However 
the code is still overly complex. To ensure CLooG simplifies it, we can
store the constraints for N in the context.

Context = N {[]: N < (2^32)-1);

This allows to simplify the code, but to still derive the optimal type 
for s.

for (type? s = 0; s < N; i++)
   Stmt(s);

In this case this was simple, however for more complex schedules I 
expect this will become pretty interesting.

We also need to see how this affects compile time performance.

>> Do you already have concrete plans?
> Plans for derive the minimal size needed for an induction variable? or
> allow polly (or even llvm) support more Parallel runtime library?

I was talking about the minimizing the type of the generated induction 
variables. However, I am also interested in adding support for 
mpc.sf.net as another OpenMP library. Do you plan to add other parallel 
libraries like MPI?

Cheers
Tobi