On 07/17/2011 07:55 AM, Sebastian Pop wrote:
Hi Tobias,
On Sat, Jul 16, 2011 at 20:02, Tobias Grosser<tob...@grosser.es> wrote:
Here I am a little lost. You write using the precise method you get an
interval [0,99] for the example in vect-pr43423.c. This is the example:
int a[100], b[100], c[100];
void foo(int n, int mid)
{
int i;
for(i=0; i<n; i++)
{
if (i< mid)
a[i] = a[i] + b[i];
else
a[i] = a[i] + c[i];
}
}
I do not see, how you would derive this small type, as the parameters of
function foo() allow a range that is a lot larger.
Accessing a[100] is undefined in C, so i< 100, and so n<= 100.
Sure. I am just surprised we already include this information in
graphite. Do we add this to the context?
# Access function 0: (int) {(<unnamed-unsigned:8>) graphite_IV.7_56, +,
1}_3;
#)
affine dependence test not usable: access function not affine or constant.
So we have to keep around the previous code gcc_type_for_clast_* that
computes the type of an expression as the max precision of the
components of that expression, and use that when computing the types
of substitution expressions.
Here I am lost again. I understand that very small types may introduce more
casts (and casts are always difficult to analyze). However, I do not
understand your solution.
First of all it seems the gcc_type_for_clast ... functions are always needed
to calculate the types, as just using polyhedral methods would not get
larger types, as they may be needed for intermediate results. Which
functions in your patch (or in the current graphite code), are only needed
to ensure that no problematic casts are inserted? This would probably help
me to understand how they ensure no problematic casts are generated.
The current graphite code contains the gcc_type_for_clast functions
that are computing wide enough types for expressions. The types are
computed based on the types of parameters and based on the types of
the induction variables of the loops surrounding the statement using
that expression. These functions are not touched by the current patch
set.
The functions lb_ub_for_* added by this patch are the ones that will
be very precise on the lower bound and upper bounds, as they are
computing based on the polyhedral representation, instead of asking
for the type of parameters, or the type of induction variables in an
expression. The lb_ub_for_* functions are too precise to compute the
type of expressions other than the loop bounds. This extra precision is
needed to address the problem you exposed of increasingly wider types
for inductions variables.
OK.
I just looked again through the gcc_type_ ... types and wondered why it
contains both calls to max_precision_type() and
max_signed_precision_type(). Is there a reason for this?
I also wondered if the solution of reusing the gcc_type_for_clast
functions is the right one. As far as I understood the reason we do not
use the type calculated by the lb_ub functions is that it may be too
small and that it may introduce too many casts. So where exactly do we
introduce these casts? 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.
If CLoog one day provides the lb/ub information itself, the migration
pass will be straightforward.
What do you think?
P.S.: I would love to see this upper/lower bound calculation being part of
CLooG.
+static struct clast_user_stmt *
+clast_get_body_of (struct clast_stmt *stmt)
+{
+ if (!stmt
+ || CLAST_STMT_IS_A (stmt, stmt_user))
+ return (struct clast_user_stmt *) stmt;
+
+ if (CLAST_STMT_IS_A (stmt, stmt_for))
+ return clast_get_body_of (((struct clast_for *) stmt)->body);
+
+ if (CLAST_STMT_IS_A (stmt, stmt_guard))
+ return clast_get_body_of (((struct clast_guard *) stmt)->then);
+
+ if (CLAST_STMT_IS_A (stmt, stmt_block))
+ return clast_get_body_of (((struct clast_block *) stmt)->body);
+
+ gcc_unreachable ();
+}
The use of this function seems incorrect to me. We seem to only get the
first statement in a loop and use its domain and scattering to derive
the size of the iv type. Let's assume we have this code:
for (s0 = 0; s0 <= n; s0++) {
if (s0 = 0)
S1(s0);
S2(s0);
}
Here we would get a range [0,0] instead of [0,n]. This does not seem to
be correct. A solution would be to completely switch to cloog-isl and
just use the information that the clast provides about the enumerated
space in each loop.
Cheers
Tobi
