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.
Index: gcc/graphite-isl-ast-to-gimple.c
===================================================================
--- gcc/graphite-isl-ast-to-gimple.c (revision 212888)
+++ gcc/graphite-isl-ast-to-gimple.c (working copy)
@@ -547,6 +547,26 @@
return last_e;
}
+/* Translates an isl_ast_node_block to Gimple. */
+
+static edge
+translate_isl_ast_node_block (loop_p context_loop,
+ __isl_keep isl_ast_node *node,
+ edge next_e, ivs_params &ip)
+{
+ gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_block);
+ isl_ast_node_list *node_list = isl_ast_node_block_get_children (node);
+ int i;
+ for (i = 0; i < isl_ast_node_list_n_ast_node (node_list); i++)
+ {
+ isl_ast_node *tmp_node = isl_ast_node_list_get_ast_node (node_list, i);
+ next_e = translate_isl_ast (context_loop, tmp_node, next_e, ip);
+ isl_ast_node_free (tmp_node);
+ }
+ isl_ast_node_list_free (node_list);
+ return next_e;
+}
+
/* Translates an ISL AST node NODE to GCC representation in the
context of a SESE. */
@@ -570,7 +590,8 @@
return next_e;
case isl_ast_node_block:
- return next_e;
+ return translate_isl_ast_node_block (context_loop, node,
+ next_e, ip);
default:
gcc_unreachable ();
