Calculate precise and minimal data types during code generation

[tobiasgrosser]

Bugzilla Link	10381
Version	unspecified
OS	Linux
CC	@jdoerfert

Extended Description

The code generated by cloog assumes unlimited integer data types. However, in LLVM the data types are always of a limited size. In Polly it is therefore necessary to choose a data type size. At the moment we always take i64.

This has two problems:

1. It may be too small and therefore incorrect
2. It may be unneccessarily large and therefore slow (especially for 32bit chips)

The right solution is to enhance CLooG such that it can provide for every subexpression a lower and an upper bound. Those bounds are then used to calculate the minimal type that is still large to always ensure correct results.

[tlattner]

Move to Polly Product.

[jdoerfert]

We would probably need to remember the ranges for our values and then generate the appropriate type. For induction variables that is easy (I think) and from there on we can do a range analysis on the expression. E.g.,

for (i = LB, i <= UB; i += STRIDE) A[c + i * 3] = ...

when we generate code for i we have to check LB, UB and STRIDE and ensure the range [LB, UB + STRIDE] is representable by the type (then we can also use nsw and nuw flags).

For "c + i 3" we combine the different ranges, thus: i ==> [LB, UB + STRIDE] i 3 ==> [LB 3, UB 3 + STRIDE 3] c + i 3 ==> [lb(c) + LB 3, ub(c) + UB 3 + STRIDE * 3] when we cast the types before the computation we should never get an overflow.

Any toughts about such an approach?

[tobiasgrosser]

This does not need to be done with CLooG, but could also be done by a new code generator that provides this information automatically.