On 07/19/2011 12:33 AM, Sebastian Pop wrote:
On Mon, Jul 18, 2011 at 16:40, Tobias Grosser<tob...@grosser.es> wrote:
You are right. In case we want to downcast b we would also need to prove
that b itself fits into the smaller type. (This may happen, if the larger
type was introduced earlier to remove casts, but is not needed to store the
result).
[...]
for (i = -128; i< min (127, j + 200); i++)
we need a type large enough to be able to represent "j + 200", and
that would be short. So we need to take again the "max of the types
of sub-expressions".
What is the "max of the types of sub-expressions"? Just the larges type is
in general not large enough. a+b may not fit into the type of a nor in the
type of b. However, assuming a and b may have any value that the types of a
and b allow, would require us to assume a type that is definitely larger
then the type of each argument (we do not do this, thats why some function
are incorrect). Implementing this approach would yield to an explosion in
type size.
What I propose is that you take advantage of your newly built lb/ub
infrastructure and that we calculate for every subexpression the type as
follows.
minimal_correct_type = max(min_type(lb_result, ub_result),
min_type(lb_op1, ub_op1),
min_type(lb_op2, ub_op2))
And then we choose a type that is equal or larger than minimal_correct_type
and that reduces the number of introduced downcasts.
minimal_correct_type wouldn't work on this example:
Suppose we have a loop that we have already generated with an
induction variable of type short for the same reasons as in the
previous example, and such that the lb_ub of the IV is still in the
range of char:
for (i = -100; i< min (100, j + 200); i++)
Now suppose that we want to determine the type of expression "i + 1".
Based on the lb_ub information of i, we would compute that
minimal_correct_type is char, because the result of "i + 1" is in
[-99, 101], so that's char and the lb_ub of the op1 and op2 are char
as well, so max (char, char, char) = char.
Generating code for "i + 1" of type char would need a cast of i from
short to char, and then computing the plus expr in the char type:
"(char) i + 1", and here you cannot eliminate the cast.
So if CLooG's answer to "what is the type of i + 1" is char, then you
would not be able to remove that cast to make the loop vectorizable.
In this particular example, I really want CLooG to answer "the type of
i + 1 is short", such that I do not need any extra casts between the
main induction variable and the plus expression.
What about the following formula that integrates not only the lb_ub
info (minimal_correct_type as you defined it), but also the types of
the sub-expressions:
minimal_correct_type_1 = max(minimal_correct_type, type_op1, type_op2)
This formula sounds reasonable and is one solution for what I ment with
"And then we choose a type that is equal or larger than
minimal_correct_type and that reduces the number of introduced downcast"
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
So by adding the max with the op1 and op2 types, we try to reduce the
the number of introduced downcasts. I am not sure if your proposed
formular is optimal in all cases, however it seems to be a good start.
Can you think at an example where that would still lead to an
"explosion in type size"?
No. This formular is correct and I do not think it would lead to any
explosion. We would not use minimal types, but I agree that minimizing
the types should only be done if we know it will be beneficial even
though it introduces additional casts. We can think later about such an
optimization.
With your formular we have a criteria, that allows us to select the type
for each subexpression locally. I like this a lot better.
Cheers
Tobi
P.S.: In respect of getting these changes in, it may be best to just
commit the patches you already have and keep improving from this. The
patches you already have do not introduce any regressions. They are just
do not fix all problems.
