On 21/07/2014 14:23, Roman Gareev wrote:
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);
}

It seems S_6 is now scheduled before S_4 which is surprising, as
dependences from S_4 to S_6 should prevent us from generating a schedule that yields such a result. What is the schedule that you give to the isl ast generator?

Cheers,
Tobias

P.S.: The patch looks good by itself, but needs some test cases. As you have them in this email, we can just add them after we understood this bug.

Reply via email to