Re: [GSoC] questions about graphite_clast_to_gimple.c

[Tobias Grosser <tobias at grosser dot es>]

On 06/05/2014 10:19, Richard Biener wrote:

Hi Richi,

thanks for the comments.

> On Tue, May 6, 2014 at 8:57 AM, Tobias Grosser <tobias@grosser.es> wrote:
> > On 05/05/2014 21:11, Roman Gareev wrote:
> > > Hi Tobias,
> > >
> > > thank you for your reply! I have questions about types. Could you
> > > please answer them?
> >
> >
> > I looked through them and most seem to be related to how we derive types in
> > graphite. As I said before, this is a _very_ fragile hack
> > that works surprisingly well, but which is both too complex and
> > in the end still incorrect. Sebastian wrote this code, so I am not familiar
> > with the details. I also don't think it is necessary to
> > understand the details. Instead of using any code, we should start
> > implementing the new code using 64 bit signed integers. This
> > should be correct in 99.9% of the cases.
>
> Of course compilers have to work correctly in 100% of the cases, so
> if you choose an approach that will be incorrect in > 0% of the cases
> then you should make sure to detect those and not apply any transform.

I agree we want to get to 100%. Just the way how to get there needs to 
be chosen.

Detecting broken cases does not work. During code generation we generate
new expressions, e.g. i + j + 200 * b. To code generate them we need to
choose a type for the computation.

cloog has zero knowledge about possible types, that's why graphite tries 
to derive types by estimating the minimal/maximal value of
an expression i + j from the knowledge it has about i and j. This 
estimate is very imprecise especially as the initial knowledge we have 
is incomplete. As Roman pointed out, several of the 'estimates' just 
don't make sense at all.

To get it 100% right we need to derive the minimal/maximal value a 
subexpression i + j can take and to use this to find a type that is 
large enough and also fast on our target platform. The best solution I 
see is to compute this information within the isl code generation, where 
we have all necessary information available.

Unfortunately, this patch is not finished yet. There are two ways to 
proceed.

1) finish the patch as the very first step

2) Go for 64bits and plug in the patch later

I would obviously prefer to get 1) done as soon as possible, but in case 
it still needs more time, defaulting to 64/128 bit types allows Roman to 
proceed. In the end, 64 bits is almost always large enough.

I am busy for the next 6 weeks, but am planning to work on the isl patch 
after. Sven, do you happen to have any time to work on the isl patch?

> > One of the selling points for the new isl code generation was however,
> > that it will be possible to get precise information about the types
> > needed for code generation. There existed already a patch for an older
> > isl version and there is a partial patch for newer versions that Sven and me
> > have been working on. It is not yet stable enough to be tested, but I
> > attached it anyway for illustration. The idea is to
> > introduce a set of functions
> >
> > +       int isl_ast_expr_has_known_size(
> > +               __isl_keep isl_ast_expr *expr);
> > +       int isl_ast_expr_is_bounded(
> > +               __isl_keep isl_ast_expr *expr);
> > +       int isl_ast_expr_is_signed(
> > +               __isl_keep isl_ast_expr *expr);
> > +       size_t isl_ast_expr_size_in_bits(
> > +               __isl_keep isl_ast_expr *expr);
> >
> > in isl, where we can precisely compute the minimal legal type. We can then
> > use this during code generation to derive good types.
>
> You should be able to do this for all types you need up-front and check
> if there is a suitable GIMPLE type available.  For example by using
> lang_hooks.types.type_for_size () which will return NULL_TREE if there
> isn't one.

How could we do this upfront? For each subexpression, we need to know 
what is the minimal legal type. Only after we know this we can derive a 
type for it.

> > > 2. Why do we want to generate signed types as much as possible?
> >
> >
> > Because in the code cloog generates negative values are common. To be save
> > we generate unsigned code.

That should have been _signed_ code.

> > Again, I do not think spending time to understand the heuristics in
> > type_for_clast is worth it. Some are rather complex and work well, some
> > or just buggy but have never been triggered and a small percentage actually
> > might be reusable later (pointer handling). As the approach
> > has generally too little information to work reliably, I would not spend
> > any time on it. I pointed out the correct approach above. Going with 64bit
> > types will bring us a very long way, and we can finish the isl patch to get
> > it 100% right.
>
> If ISL can give you for each expression a type precision and signedness
> then I'd stick to that if it is available (or else punt).

Not yet, but hopefully soon.

At the moment, we have zero information about the types (the same holds 
for cloog).

I see only three choices:

	1) Finish this feature of the isl code generation first
	2) Try to do 'estimate' the types from the graphite side as
           we did it before.
	3) Assume 64/128 bits and plug in the precise analysis later.

I strongly dislike 2), see two as an intermediate solution and obviously 
would prefer to have 1) immediately. So as I don't have time to 
implement 1) myself, we either need to see if Sven can do it or we ask 
Roman to do it.

To use Romans' time most efficiently, I believe it would be better to 
have him focus on the gcc parts first.



Cheers,
Tobias