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]

Re: [GSoC] generation of Gimple code from isl_ast_node_block


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.


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