On Mon, Jul 18, 2011 at 11:11, Tobias Grosser<tobias@grosser.es> wrote:
We introduce casts when we generate code for an expression with a type
smaller than the types of its constituents.
So the next question is: What is the type of the expression. As far as I
understand we decide ourselves which type the expression should have. Our
correctness constraint is that the type must be large enough to contain [lb,
ub] of the result as well as all operands. We can choose any larger type to
reduce the number of casts that will generated.
Right, and so we cannot only rely on the lb_ub info, and we have to
walk the CLAST expression and determine the largest type used as a we
sub-expression: that's what gcc_type_for_clast_expr tries to do.
OK
Here is an example: supposing that we already code generated an IV
graphite_IV with a signed short type, then we are asked to generate
code for the expression "42 * graphite_IV", and finally suppose that
lb_ub returns the interval [-100, 100] for this expression, then we
would have a signed char type for the expression
So the signed char type is the smallest type we can use for the expression.
and so we would
introduce a cast of the graphite_IV to signed char before doing the
multiplication: so I guess the code generated for this expression
would be something like: "42 * (char) graphite_IV" of type char.
Without taking the max of the types of the sub-expressions, you would
have to generate casts for a shorter type.
Your example is a little incomplete, as 42 is missing a type. At the moment
gcc_type_for_value() returns the smallest type that contains the scalar
value. So I assume the type is a signed char.
If we choose for as type of the expression signed char we get this:
42 * (char) graphite_IV
On the other hand, if we choose signed short for the expression we get:
((short) 42) * graphite_IV
That would be just "42 * graphite_IV" of type short, as widening from
char to short is possible without extra cast.
Both expressions contain a cast. Which one is better for the optimizer is
something I do not yet understand. However, I believe this choice is
basically a choice that can be taken locally for each expression. Using
either max(validy_type,(min(op1_type, op2_type, ...)) to favor small types
or max(validy_type,(max(op1_type, op2_type, ...)) to favor large types.
Can we find a solution that solves this problem more locally. I mean
instead
of using an imprecise algorithm that leads to larger types which
(accidentally?) leads to less casts, we could understand the type
calculated
by lb_ub_... as a minimal type needed for correctness. For each
instruction
that we code generate, we derive the type by electing a type that is
large
enough to be correct and that at the same time is not smaller than the
smallest type of each operand.
You surely mean "not smaller than the *largest* type of each operand".
No. As said above, both seem to be valid choices and this seems to be
Here is a counter-example where taking the type "not smaller than the
smallest type of each operand" produces wrong code:
expression "a + b"
type of a is char
type of b is short
a goes from -100 to 100
b goes from 100 to 200
Computing the type of "a + b" as the type "not smaller than the
smallest type of each operand" leads to char. Then, we would have to
generate the expression "(char) a + (char) b" of type char. Casting
200 into a char overflows and is undefined.
I honestly do not like this function chain. The problem is that we would
calculate huge types, if we derive the type of an expression by only taking
into account the types of its sub(sub, ...) expressions. At the moment we do
not get these huge types, as our calculations are not 100% correct.
Lets assume we have a clast consisting of a single addition from several
integers.
127 + 127 + 127 + 127
Each integer would get the type signed char. Now the function
gcc_type_for_clast_red() would calculate the necessary type as max(char,
char, char, char) => char. However the correct type is actually max
(type([lb, ub]), min/max(char,char,char,char)). Where type([lb,ub]) =
type([508,508]) = short and the result is max(short, char) = short.
Right. We should be able to represent both the sub-expressions and
their results in the computed type. The current implementation of
gcc_type_for_clast_* is wrong.
gcc_type_for_clast_term () seems also to just use the type of the variable
instead of the type that would actually be needed to calculate<integer> *
variable.
The types would become even larger as they would increase while walking up
the ClAST. This is because, we never take the actual ub,lb values into
account, but always derive the minimal type needed for correctness from the
types of the operands.
I believe, to derive correct types that are nor overly large, doing those
calculations locally would be better. For each expression we use ub/lb to
calculate the minimal type needed for correctness and then we choose a type
equal or larger than this type that minimizes the number of bad casts.
You would also need to make sure that every sub-expression can be
expressed in that computed type: the example here is that of a min or
a max expression of a loop bound: even if we know from the iteration
domain that the IV belongs to [-128, 127] we cannot generate a char
for this loop: