Re: [GSoC] generation of GCC expression trees from isl ast expressions

[Roman Gareev <gareevroman at gmail dot com>]

>> However, this form doesn't have loop guards which are generated by
>> graphite_create_new_loop_guard in gcc/graphite-isl-ast-to-gimple.c and
>> by graphite_create_new_loop_guard in graphite-clast-to-gimple.c.
>
>
> Maybe the guards are directly constant folded? Can you try with:

I've tried this. It seems that the result is the same. If we consider
the following code, we'll see that the guards are generated:

int
main (int n, int *a)
{
  int i;

  for (i = n; i < 100; i++)
    a[i] = i;

  return 0;
}

gcc/graphite-isl-ast-to-gimple.c

loop_0 (header = 0, latch = 1, niter = )
{
  bb_2 (preds = {bb_0 }, succs = {bb_4 bb_3 })
  {
    <bb 2>:
    if (n_3(D) <= 99)
      goto <bb 4>;
    else
      goto <bb 3>;

  }
  bb_3 (preds = {bb_2 bb_8 }, succs = {bb_1 })
  {
    <bb 3>:
    # .MEM_12 = PHI <.MEM_4(D)(2), .MEM_11(8)>
    # VUSE <.MEM_12>
    return 0;

  }
  bb_4 (preds = {bb_2 }, succs = {bb_5 bb_8 })
  {
    <bb 4>:
    _2 = n_3(D) <= 99;
    if (_2 != 0)
      goto <bb 5>;
    else
      goto <bb 8>;

  }
  bb_5 (preds = {bb_4 }, succs = {bb_6 })
  {
    <bb 5>:
    _1 = (__int128) n_3(D);
    _16 = 99 - _1;

  }
  bb_8 (preds = {bb_4 bb_6 }, succs = {bb_3 })
  {
    <bb 8>:
    # .MEM_11 = PHI <.MEM_4(D)(4), .MEM_4(D)(6)>
    goto <bb 3>;

  }
  loop_2 (header = 6, latch = 7, niter = (uint128_t) MAX_EXPR <_16,
0>, upper_bound = 0x7ffffffffffffffffffffffffffffffe)
  {
    bb_6 (preds = {bb_5 bb_7 }, succs = {bb_7 bb_8 })
    {
      <bb 6>:
      # graphite_IV.3_17 = PHI <0(5), graphite_IV.3_18(7)>
      graphite_IV.3_18 = graphite_IV.3_17 + 1;
      if (graphite_IV.3_17 < _16)
        goto <bb 7>;
      else
        goto <bb 8>;

    }
    bb_7 (preds = {bb_6 }, succs = {bb_6 })
    {
      <bb 7>:
      goto <bb 6>;

    }
  }
}

graphite-clast-to-gimple.c

loop_0 (header = 0, latch = 1, niter = )
{
  bb_2 (preds = {bb_0 }, succs = {bb_4 bb_3 })
  {
    <bb 2>:
    if (n_3(D) <= 99)
      goto <bb 4>;
    else
      goto <bb 3>;

  }
  bb_3 (preds = {bb_2 bb_8 }, succs = {bb_1 })
  {
    <bb 3>:
    # .MEM_12 = PHI <.MEM_4(D)(2), .MEM_25(8)>
    # VUSE <.MEM_12>
    return 0;

  }
  bb_4 (preds = {bb_2 }, succs = {bb_5 bb_8 })
  {
    <bb 4>:
    _2 = n_3(D) <= 99;
    if (_2 != 0)
      goto <bb 5>;
    else
      goto <bb 8>;

  }
  bb_5 (preds = {bb_4 }, succs = {bb_6 })
  {
    <bb 5>:
    _1 = 99 - n_3(D);

  }
  bb_8 (preds = {bb_6 bb_4 }, succs = {bb_3 })
  {
    <bb 8>:
    # .MEM_25 = PHI <.MEM_18(6), .MEM_4(D)(4)>
    goto <bb 3>;

  }
  loop_2 (header = 6, latch = 7, niter = (unsigned int) MAX_EXPR <_1,
0>, upper_bound = 2147483646)
  {
    bb_6 (preds = {bb_5 bb_7 }, succs = {bb_7 bb_8 })
    {
      <bb 6>:
      # graphite_IV.3_16 = PHI <0(5), graphite_IV.3_17(7)>
      # .MEM_26 = PHI <.MEM_4(D)(5), .MEM_18(7)>
      _19 = (sizetype) n_3(D);
      _20 = (sizetype) graphite_IV.3_16;
      _21 = _19 + _20;
      _22 = _21 * 4;
      _23 = a_7(D) + _22;
      _24 = n_3(D) + graphite_IV.3_16;
      # .MEM_18 = VDEF <.MEM_26>
      *_23 = _24;
      graphite_IV.3_17 = graphite_IV.3_16 + 1;
      if (graphite_IV.3_16 < _1)
        goto <bb 7>;
      else
        goto <bb 8>;

    }
    bb_7 (preds = {bb_6 }, succs = {bb_6 })
    {
      <bb 7>:
      goto <bb 6>;

    }
  }
}

>> Below is the code of this generation (It still uses isl_int for
>> generation of isl_expr_int, because the error related to isl/val_gmp.h
>> still arises. I've tried to use isl 0.12.2 and 0.13, but gotten the
>> same error).
>
>
> Did using 'extern "C"' around the include statement not help?

I can't build gcc without using 'extern "C"'. After the successful
building the error is arising when I am trying to compile, for
example, the following code:

int
main (int n, int *a)
{
  int i;

  for (i = n; i < 100; i++)
    a[i] = i;

  return 0;
}

>> +/* Stores the INDEX in a vector and the loop nesting LEVEL for a given
>> +   isl_id NAME.  BOUND_ONE and BOUND_TWO represent the exact lower and
>> +   upper bounds that can be inferred from the polyhedral representation.
>> */
>
>
> Why do you mention BOUND_ONE & BOUND_TWO? I do not see any use of them?

This is a misprint. I've fixed it.

> Any reason this is not a simpel std::map<isl_id *, tree>, but you instead
> have this manually implemented hash table?

I think that using of std::map may create installation dependency,
which requires libstdc++. I've asked the community about this.

>Does gcc have a policy that forbids std::map?

I think, that it is normal to use std::map from the GNU C++ Library.

> Is there a reason we have separat newivs_index and params_index maps?
> This was necessary for CLooG as far as I remember, but for isl a simple
> isl_id -> tree map should be sufficient, no?

> Is there aneed for the level at all? I think in the current
> implementation and for isl in general it may not be needed as we have
> isl_ids to find the corresponding loop ivs.

Yes, this is redundant and removed in the new version. I wanted to
write the code, which reuses the code from graphite-clast-to-gimple.c
as much as possible, to reduce a number of errors. After this, I
planned to eliminate redundant parts.

> Please explain why we need a special function to get the upper bound.
> Specifically, explain that isl in some configurations can generate loop
> exit conditions such as:
>
> for (i = ?; i + 2 >= 3 && 3 <= i + m; i++)
>   ;
>
> This get upper bound assumes a certain shape of loop exit condition(
>
> for (i = ?; i < expr; i++)
>
> Also, you need to set the option --no-isl-ast-build-atomic-upper-bound
> in isl_ast_build to be able to rely on this behavior.
> (You did this below)
>
> Do you have a specific motivation, why you don't want to support
> arbitrary expressions? I assume this is necessary for the if - do-while
> optimization. If this is the case please state this.

I haven't found another function for generation loops in Gimple form.
The create_empty_loop_on_edge needs, which is being used now, requires
upper bound.

 /* create_empty_loop_on_edge
    |
    |    - pred_bb -             -------- pred_bb ------
    |   |           |                 | iv0 = initial_value |
    |    -----|-----                  --------------|-----------
    |         |                            ___    | entry_edge
    |         | entry_edge         /      |    |
    |         |             ====> /   -----V---V- loop_header -------------
    |         V                     |    |  iv_before = phi (iv0, iv_after) |
    |    - succ_bb -           |
----|-----------------------------------------
    |   |           |                |         |
    |    -----------                |      ---V--- loop_body
--------------------
    |                               |     | iv_after = iv_before + stride     |
    |                               |     | if (iv_before < upper_bound)     |
    |                               |
---|--------------------------\--------------
    |                               |         |
   \ exit_e
    |                               |         V                           \
    |                               |       - loop_latch -
---V- succ_bb -
    |                               |      |                   |
|                        |
    |                               |       /-----------------
-------------------------
    |                                \ _ /


Furthermore, at the moment of loop generation we don't have the
induction variable, which is need for generation of a loop condition
in case of the option âno-isl-ast-build-atomic-upper-bound is unset.
The induction variable is returned by create_empty_loop_on_edge. Could
you please advise me another function to generate them?

> Please explain why we do not just generate a loop that has the loop
> bound at the top, but instead create a structure of the form
>
> if (lb > ub)
>   do {
>
>   } while (lb ..)
>
> (Such a figure, but completed might help).
>
> (I think the original motivation was that later we may be able to prove
> that a loop is executed at least once which allows us to remove the if
> which again enables better loop invariant code motion)

I didn't have special intentions for this. As was mentioned above, I
haven't found another way for generation of loops.

> Why are the previous two functions necessary?

Yes, they are unimportant. I've replaced them with
add_parameters_to_ivs_params, which add tree representations and names
of parameters to ivs_param

> Why did you switch back to an isl_map?
> This seems incorrect for scops with more than two statements.

Yes, this is a mistake. I've fixed it.

> P.S.: I just wanted to let you know that your work is amazing. Almost
> fully unsupervised you are always providing high-quality patches! I am
> very impressed.

Thank you!

--
                                   Cheers, Roman Gareev

Attachment: patch.txt
Description: Text document