On 06/05/2014 13:52, Richard Biener wrote:
On Tue, May 6, 2014 at 1:02 PM, Tobias Grosser <tob...@grosser.es> wrote:
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 <tob...@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.

I thought that ISL gives you this information.  If not, then of course there
is no way - but then there is no way at any point.

Not yet. We are close, but it is not finished enough to use it in production.

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).

Oh, ok ...
>
>
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.

I'd say go for 3) then.  The old code in 2) should go away, if we need sth
similar later we should do it better and differently (I can help with that).

Great. That was my thought as well.

Thanks for the feedback. And yes, we should get feedback from you regarding the precise analysis later on.

Tobias

Reply via email to