This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[GSoC] generation of Gimple code from isl_ast_node_block


I've attached the patch, which contains generation of Gimple code from
isl_ast_node_block.

However, I've found out a problem. The following example:

int k = 50;
static int __attribute__((noinline))
foo ()
{
  int i, res;
  for (i = 0, res = 0; i < k; i++)
    res += i;

  return res;
}

extern void abort ();

int
main (void)
{
  int res = foo ();


  if (res != 1225)
    abort ();

  return 0;
}.

produces the following code, which executes without error:

ISL AST generated by ISL:
{
  for (int c1 = 0; c1 < k.0; c1 += 1)
    S_4(c1);
  S_6();
}

Gimple code:
loop_0 (header = 0, latch = 1, niter = )
{
  bb_2 (preds = {bb_0 }, succs = {bb_3 bb_8 })
  {
    <bb 2>:
    # VUSE <.MEM_3(D)>
    k.0_9 = k;
    if (k.0_9 > 0)
      goto <bb 3>;
    else
      goto <bb 8>;

  }
  bb_3 (preds = {bb_2 }, succs = {bb_4 bb_7 })
  {
    <bb 3>:
    # .MEM_8 = VDEF <.MEM_3(D)>
    phi_out_of_ssa.5[0] = 0;
    _20 = k.0_9 > 0;
    if (_20 != 0)
      goto <bb 4>;
    else
      goto <bb 7>;

  }
  bb_4 (preds = {bb_3 }, succs = {bb_5 })
  {
    <bb 4>:
    _21 = (signed long) k.0_9;
    _22 = _21 + -1;

  }
  bb_7 (preds = {bb_5 bb_3 }, succs = {bb_8 })
  {
    <bb 7>:
    # .MEM_30 = PHI <.MEM_29(5), .MEM_8(3)>
    # VUSE <.MEM_30>
    res_32 = Close_Phi.6[0];
    # .MEM_33 = VDEF <.MEM_30>
    Cross_BB_scalar_dependence.7[0] = res_32;
    # VUSE <.MEM_33>
    res_17 = Cross_BB_scalar_dependence.7[0];
    _16 = res_17;

  }
  bb_8 (preds = {bb_7 bb_2 }, succs = {bb_1 })
  {
    <bb 8>:
    # res_12 = PHI <_16(7), 0(2)>
    # .MEM_2 = PHI <.MEM_33(7), .MEM_3(D)(2)>
    # VUSE <.MEM_2>
    return res_12;

  }
  loop_2 (header = 5, latch = 6, niter = (unsigned long) ((signed
long) k.0_9 + -1), upper_bound = 9223372036854775806)
  {
    bb_5 (preds = {bb_4 bb_6 }, succs = {bb_6 bb_7 })
    {
      <bb 5>:
      # graphite_IV.8_23 = PHI <0(4), graphite_IV.8_24(6)>
      # .MEM_31 = PHI <.MEM_8(4), .MEM_29(6)>
      # VUSE <.MEM_31>
      res_25 = phi_out_of_ssa.5[0];
      _27 = (int) graphite_IV.8_23;
      res_26 = res_25 + _27;
      # .MEM_28 = VDEF <.MEM_31>
      Close_Phi.6[0] = res_26;
      # .MEM_29 = VDEF <.MEM_28>
      phi_out_of_ssa.5[0] = res_26;
      graphite_IV.8_24 = graphite_IV.8_23 + 1;
      if (graphite_IV.8_23 < _22)
        goto <bb 6>;
      else
        goto <bb 7>;

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

    }
  }
}

It is similar to the original code:

loop_0 (header = 0, latch = 1, niter = )
{
  bb_2 (preds = {bb_0 }, succs = {bb_3 bb_8 })
  {
    <bb 2>:
    # VUSE <.MEM_3(D)>
    k.0_9 = k;
    if (k.0_9 > 0)
      goto <bb 3>;
    else
      goto <bb 8>;

  }
  bb_3 (preds = {bb_2 }, succs = {bb_5 })
  {
    <bb 3>:
    # .MEM_8 = VDEF <.MEM_3(D)>
    phi_out_of_ssa.5[0] = 0;
    goto <bb 5>;

  }
  bb_4 (preds = {bb_7 }, succs = {bb_8 })
  {
    <bb 4>:
    # .MEM_19 = PHI <.MEM_18(7)>
    # VUSE <.MEM_19>
    res_17 = Cross_BB_scalar_dependence.7[0];
    _16 = res_17;
    goto <bb 8>;

  }
  bb_7 (preds = {bb_5 }, succs = {bb_4 })
  {
    <bb 7>:
    # VUSE <.MEM_13>
    res_4 = Close_Phi.6[0];
    # .MEM_18 = VDEF <.MEM_13>
    Cross_BB_scalar_dependence.7[0] = res_4;
    goto <bb 4>;

  }
  bb_8 (preds = {bb_4 bb_2 }, succs = {bb_1 })
  {
    <bb 8>:
    # res_12 = PHI <_16(4), 0(2)>
    # .MEM_2 = PHI <.MEM_19(4), .MEM_3(D)(2)>
    # VUSE <.MEM_2>
    return res_12;

  }
  loop_1 (header = 5, latch = 6, niter = , upper_bound = 2147483646)
  {
    bb_5 (preds = {bb_3 bb_6 }, succs = {bb_6 bb_7 })
    {
      <bb 5>:
      # i_10 = PHI <0(3), i_6(6)>
      # .MEM_1 = PHI <.MEM_8(3), .MEM_13(6)>
      # VUSE <.MEM_1>
      res_11 = phi_out_of_ssa.5[0];
      res_5 = res_11 + i_10;
      # .MEM_7 = VDEF <.MEM_1>
      Close_Phi.6[0] = res_5;
      # .MEM_13 = VDEF <.MEM_7>
      phi_out_of_ssa.5[0] = res_5;
      i_6 = i_10 + 1;
      if (i_6 < k.0_9)
        goto <bb 6>;
      else
        goto <bb 7>;

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

    }
  }
}

If we change the name of variable k to n:

int n = 50;
static int __attribute__((noinline))
foo ()
{
  int i, res;
  for (i = 0, res = 0; i < n; i++)
    res += i;

  return res;
}

extern void abort ();

int
main (void)
{
  int res = foo ();


  if (res != 1225)
    abort ();

  return 0;
}

the following code will be produced, which gives wrong result

ISL AST generated by ISL:
{
  S_6();
  for (int c1 = 0; c1 < n.0; c1 += 1)
    S_4(c1);
}

Gimple code:
loop_0 (header = 0, latch = 1, niter = )
{
  bb_2 (preds = {bb_0 }, succs = {bb_3 bb_8 })
  {
    <bb 2>:
    # VUSE <.MEM_3(D)>
    n.0_9 = n;
    if (n.0_9 > 0)
      goto <bb 3>;
    else
      goto <bb 8>;

  }
  bb_3 (preds = {bb_2 }, succs = {bb_4 bb_7 })
  {
    <bb 3>:
    # .MEM_8 = VDEF <.MEM_3(D)>
    phi_out_of_ssa.5[0] = 0;
    # VUSE <.MEM_8>
    res_20 = Close_Phi.6[0];
    # .MEM_21 = VDEF <.MEM_8>
    Cross_BB_scalar_dependence.7[0] = res_20;
    _22 = n.0_9 > 0;
    if (_22 != 0)
      goto <bb 4>;
    else
      goto <bb 7>;

  }
  bb_4 (preds = {bb_3 }, succs = {bb_5 })
  {
    <bb 4>:
    _23 = (signed long) n.0_9;
    _24 = _23 + -1;

  }
  bb_7 (preds = {bb_5 bb_3 }, succs = {bb_8 })
  {
    <bb 7>:
    # .MEM_32 = PHI <.MEM_31(5), .MEM_21(3)>
    # VUSE <.MEM_32>
    res_17 = Cross_BB_scalar_dependence.7[0];
    _16 = res_17;

  }
  bb_8 (preds = {bb_7 bb_2 }, succs = {bb_1 })
  {
    <bb 8>:
    # res_12 = PHI <_16(7), 0(2)>
    # .MEM_2 = PHI <.MEM_32(7), .MEM_3(D)(2)>
    # VUSE <.MEM_2>
    return res_12;

  }
  loop_2 (header = 5, latch = 6, niter = (unsigned long) ((signed
long) n.0_9 + -1), upper_bound = 9223372036854775806)
  {
    bb_5 (preds = {bb_4 bb_6 }, succs = {bb_6 bb_7 })
    {
      <bb 5>:
      # graphite_IV.8_25 = PHI <0(4), graphite_IV.8_26(6)>
      # .MEM_33 = PHI <.MEM_21(4), .MEM_31(6)>
      # VUSE <.MEM_33>
      res_27 = phi_out_of_ssa.5[0];
      _29 = (int) graphite_IV.8_25;
      res_28 = res_27 + _29;
      # .MEM_30 = VDEF <.MEM_33>
      Close_Phi.6[0] = res_28;
      # .MEM_31 = VDEF <.MEM_30>
      phi_out_of_ssa.5[0] = res_28;
      graphite_IV.8_26 = graphite_IV.8_25 + 1;
      if (graphite_IV.8_25 < _24)
        goto <bb 6>;
      else
        goto <bb 7>;

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

    }
  }
}

It seems that isl produce some illegal transformation, because in the
last case it uses the old version of variable res:

  bb_7 (preds = {bb_5 bb_3 }, succs = {bb_8 })
  {
    <bb 7>:
    # .MEM_32 = PHI <.MEM_31(5), .MEM_21(3)>
    # VUSE <.MEM_32>
    res_17 = Cross_BB_scalar_dependence.7[0];
    _16 = res_17;

  }

The original Gimple code for the second example is similar to the first one:

loop_0 (header = 0, latch = 1, niter = )
{
  bb_2 (preds = {bb_0 }, succs = {bb_3 bb_8 })
  {
    <bb 2>:
    # VUSE <.MEM_3(D)>
    n.0_9 = n;
    if (n.0_9 > 0)
      goto <bb 3>;
    else
      goto <bb 8>;

  }
  bb_3 (preds = {bb_2 }, succs = {bb_5 })
  {
    <bb 3>:
    # .MEM_8 = VDEF <.MEM_3(D)>
    phi_out_of_ssa.5[0] = 0;
    goto <bb 5>;

  }
  bb_4 (preds = {bb_7 }, succs = {bb_8 })
  {
    <bb 4>:
    # .MEM_19 = PHI <.MEM_18(7)>
    # VUSE <.MEM_19>
    res_17 = Cross_BB_scalar_dependence.7[0];
    _16 = res_17;
    goto <bb 8>;

  }
  bb_7 (preds = {bb_5 }, succs = {bb_4 })
  {
    <bb 7>:
    # VUSE <.MEM_13>
    res_4 = Close_Phi.6[0];
    # .MEM_18 = VDEF <.MEM_13>
    Cross_BB_scalar_dependence.7[0] = res_4;
    goto <bb 4>;

  }
  bb_8 (preds = {bb_4 bb_2 }, succs = {bb_1 })
  {
    <bb 8>:
    # res_12 = PHI <_16(4), 0(2)>
    # .MEM_2 = PHI <.MEM_19(4), .MEM_3(D)(2)>
    # VUSE <.MEM_2>
    return res_12;

  }
  loop_1 (header = 5, latch = 6, niter = , upper_bound = 2147483646)
  {
    bb_5 (preds = {bb_3 bb_6 }, succs = {bb_6 bb_7 })
    {
      <bb 5>:
      # i_10 = PHI <0(3), i_6(6)>
      # .MEM_1 = PHI <.MEM_8(3), .MEM_13(6)>
      # VUSE <.MEM_1>
      res_11 = phi_out_of_ssa.5[0];
      res_5 = res_11 + i_10;
      # .MEM_7 = VDEF <.MEM_1>
      Close_Phi.6[0] = res_5;
      # .MEM_13 = VDEF <.MEM_7>
      phi_out_of_ssa.5[0] = res_5;
      i_6 = i_10 + 1;
      if (i_6 < n.0_9)
        goto <bb 6>;
      else
        goto <bb 7>;

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

    }
  }
}

Do you know anything about this issue? Should we use some options to
avoid illegal transformations (I haven't fount them)? Is it possible
to manually update SSA form to use the last versions of variables (I
haven't found such possibilities)?

P.S. There are other examples of wrong generations, but it is
difficult to find the reason of errors in them.

P.S. CLooG generates the same code for both examples:

CLAST generated by CLooG:
for (scat_1=0;scat_1<=k.0_9-1;scat_1++) {
  (scat_1);
}
();

--
                                   Cheers, Roman Gareev.

Attachment: patch.txt
Description: Text document


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]