> No, no idea. To my understanding the entry block should not even appear
> within a scop (see build_scops, where we only start detecting scops at
> the successor of the entry_block). Maybe we replace this with an assert
> to get a good error message in case I have missed something.
Yes, I think this would be a good solution at this moment.
> I think this region is actually not needed. At the place where you need
> it, you have a pbb available, from which you can obtain a pointer to the
> surrounding scop and from this you can obtain this region itself.
Yes, this is redundant.
> This is a pure style change which seems unrelated. Also, is the original
> line really too long? I may have miscounted, but it seems to fit
> exactly.
If I am not mistaken, lines should be limited to 80 characters,
according to conventions, which are mentioned here
https://gcc.gnu.org/wiki/CppConventions. This line contains 81
characters.
> In polly we just create an iv_map from [0, max-loop-depth-within-scop], so
> it contains at most as many elements as the maximal loop depth. Your map
> is unnecessarily large, as it contains all loops in the function.
>
> If we can avoid this immediately, e.g. by indexing according to the
> loop-depths that would be great. On the other side, if the existing
> functions require this, I propose to not touch this area, but to add a
> fixme that documents this issue. We can solve it after having removed
> the CLooG codegen.
If I am not mistaken, the existing function doesn't require that
iv_map contains at most as many elements as the maximal loop depth.
(If we consider chrec_apply_map (I think that it is the only function,
which works with iv_map), we'll see that it calls chrec_apply when the
expression is not NULL. In our case, we push NULL_TREEs into iv_map to
extend its size to the maximal loop depth. They aren't considered,
because tree NULL_TREE is equivalent to NULL, according to tree.h)
Maybe we could use a number of the innermost loop that contains the
basic block gbb. If I am not mistaken, outer loops considered in
build_iv_mapping have smaller numbers than it. What do you think about
this?
> I was just briefly looking the code to remind me what this
> bb_pbb_mapping hash table is about, but could not find the reason it is
> needed. Do you know why it is needed?
>
> Is it necessary for this patch? Or did you just copy it from the
> previous code generation?
Yes, I've forgotten to remove this. If I am not mistaken,
bb_pbb_mapping is used for checking for the loop parallelism in
graphite-clast-to-gimple.c.
> Why do you need to first push NULL_TREEs into this vec, which will be
> overwritten right after?
In the current implementation, we'll get the error “internal compiler
error: in operator[], at vec.h:736”, if we try to assign a value to
iv_map via [] and remove initial pushing of NULL_TREEs. We could push
new values into iv_map in build_iv_mapping, but I am not sure if there
are cases, which require special processing (for example, NULL_TREEs
should be pushed into iv_map before the next old_loop->num. Possibly,
there are no such cases.).
> It is unclear how this patches have been tested. Can you elaborate?
I've compared the result of Gimple code generation (I've attached them
to the letter) for the following examples:
int
main (int n, int *a)
{
int i;
for (i = n; i < 100; i++)
a[i] = i;
return 0;
}
int
main (int 0, int *a)
{
int i;
for (i = n; i < 100; i++)
a[i] = i;
return 0;
}
> Also, we need to find a way to test this in gcc itself, possibly by
> running test cases that already work with both the cloog and the isl ast
> generator.
Maybe we could choose the strategy, which was used in
/gcc/testsuite/gcc.dg/graphite/interchange-1.c,
/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c,
/gcc/testsuite/gcc.dg/graphite/run-id-5.c?
(The result of the transformed function is compared to the assumed
value and the abort function is called in case of inequality.) What do
you think about this?
--
Cheers, Roman Gareev.
2014-07-12 Roman Gareev <gareevro...@gmail.com>
gcc/
* graphite-isl-ast-to-gimple.c:
Add inclusion of gimple-ssa.h, tree-into-ssa.h.
(ivs_params_clear):
(build_iv_mapping): New function.
(translate_isl_ast_node_user): Likewise.
(translate_isl_ast): Add calling of translate_isl_ast_node_user.
loop_0 (header = 0, latch = 1, niter = )
{
bb_2 (preds = {bb_0 }, succs = {bb_3 })
{
<bb 2>:
}
bb_5 (preds = {bb_3 }, succs = {bb_1 })
{
<bb 5>:
# .MEM_18 = PHI <.MEM_11(3)>
# VUSE <.MEM_18>
return 0;
}
loop_2 (header = 3, latch = 4, niter = )
{
bb_3 (preds = {bb_2 bb_4 }, succs = {bb_4 bb_5 })
{
<bb 3>:
# graphite_IV.3_1 = PHI <0(2), graphite_IV.3_14(4)>
# .MEM_19 = PHI <.MEM_3(D)(2), .MEM_11(4)>
_2 = (sizetype) graphite_IV.3_1;
_15 = _2 * 4;
_16 = a_6(D) + _15;
_17 = (int) graphite_IV.3_1;
# .MEM_11 = VDEF <.MEM_19>
*_16 = _17;
graphite_IV.3_14 = graphite_IV.3_1 + 1;
if (graphite_IV.3_1 < 99)
goto <bb 4>;
else
goto <bb 5>;
}
bb_4 (preds = {bb_3 }, succs = {bb_3 })
{
<bb 4>:
goto <bb 3>;
}
}
}
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>;
}
}
}
loop_0 (header = 0, latch = 1, niter = )
{
bb_2 (preds = {bb_0 }, succs = {bb_3 })
{
<bb 2>:
}
bb_5 (preds = {bb_3 }, succs = {bb_1 })
{
<bb 5>:
# .MEM_18 = PHI <.MEM_11(3)>
# VUSE <.MEM_18>
return 0;
}
loop_2 (header = 3, latch = 4, niter = )
{
bb_3 (preds = {bb_2 bb_4 }, succs = {bb_4 bb_5 })
{
<bb 3>:
# graphite_IV.3_1 = PHI <0(2), graphite_IV.3_14(4)>
# .MEM_19 = PHI <.MEM_3(D)(2), .MEM_11(4)>
_2 = (sizetype) graphite_IV.3_1;
_15 = _2 * 4;
_16 = a_6(D) + _15;
_17 = (int) graphite_IV.3_1;
# .MEM_11 = VDEF <.MEM_19>
*_16 = _17;
graphite_IV.3_14 = graphite_IV.3_1 + 1;
if (graphite_IV.3_1 < 99)
goto <bb 4>;
else
goto <bb 5>;
}
bb_4 (preds = {bb_3 }, succs = {bb_3 })
{
<bb 4>:
goto <bb 3>;
}
}
}
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_27(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 = (long long int) n_3(D);
_16 = 99 - _1;
}
bb_8 (preds = {bb_6 bb_4 }, succs = {bb_3 })
{
<bb 8>:
# .MEM_27 = PHI <.MEM_19(6), .MEM_4(D)(4)>
goto <bb 3>;
}
loop_2 (header = 6, latch = 7, niter = (unsigned long) MAX_EXPR <_16, 0>,
upper_bound = 4611686018427387902)
{
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)>
# .MEM_28 = PHI <.MEM_4(D)(5), .MEM_19(7)>
_20 = (sizetype) n_3(D);
_21 = (sizetype) graphite_IV.3_17;
_22 = _20 + _21;
_23 = _22 * 4;
_24 = a_7(D) + _23;
_25 = (int) graphite_IV.3_17;
_26 = n_3(D) + _25;
# .MEM_19 = VDEF <.MEM_28>
*_24 = _26;
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>;
}
}
}
Index: gcc/graphite-isl-ast-to-gimple.c
===================================================================
--- gcc/graphite-isl-ast-to-gimple.c (revision 212491)
+++ gcc/graphite-isl-ast-to-gimple.c (working copy)
@@ -51,6 +51,8 @@
#include "sese.h"
#include "tree-ssa-loop-manip.h"
#include "tree-scalar-evolution.h"
+#include "gimple-ssa.h"
+#include "tree-into-ssa.h"
#include <map>
#ifdef HAVE_cloog
@@ -65,7 +67,9 @@
/* We always use signed 128, until isl is able to give information about
types */
-static tree *graphite_expression_size_type = &int128_integer_type_node;
+static tree *graphite_expression_size_type = int128_integer_type_node ?
+ &int128_integer_type_node :
+ &long_long_integer_type_node;
/* Converts a GMP constant VAL to a tree and returns it. */
@@ -460,7 +464,8 @@
case isl_ast_op_lt:
{
// (iterator < ub) => (iterator <= ub - 1)
- isl_val *one = isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond),
1);
+ isl_val *one =
+ isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1);
isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1);
res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one));
break;
@@ -541,6 +546,68 @@
return last_e;
}
+/* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the
+ induction variables of the loops around GBB in SESE. */
+
+static void
+build_iv_mapping (vec<tree> iv_map, gimple_bb_p gbb,
+ __isl_keep isl_ast_expr *user_expr, ivs_params &ip,
+ sese region)
+{
+ gcc_assert (isl_ast_expr_get_type (user_expr) == isl_ast_expr_op &&
+ isl_ast_expr_get_op_type (user_expr) == isl_ast_op_call);
+ int i;
+ isl_ast_expr *arg_expr;
+ for (i = 1; i < isl_ast_expr_get_op_n_arg (user_expr); i++)
+ {
+ arg_expr = isl_ast_expr_get_op_arg (user_expr, i);
+ tree type = *graphite_expression_size_type;
+ tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
+ loop_p old_loop = gbb_loop_at_index (gbb, region, i - 1);
+ iv_map[old_loop->num] = t;
+ }
+
+}
+
+/* Translates an isl_ast_node_user to Gimple. */
+
+static edge
+translate_isl_ast_node_user (__isl_keep isl_ast_node *node,
+ edge next_e, ivs_params &ip)
+{
+ gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_user);
+ isl_ast_expr *user_expr = isl_ast_node_user_get_expr (node);
+ isl_ast_expr *name_expr = isl_ast_expr_get_op_arg (user_expr, 0);
+ gcc_assert (isl_ast_expr_get_type (name_expr) == isl_ast_expr_id);
+ isl_id *name_id = isl_ast_expr_get_id (name_expr);
+ poly_bb_p pbb = (poly_bb_p) isl_id_get_user (name_id);
+ gcc_assert (pbb);
+ gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
+ vec<tree> iv_map;
+ isl_ast_expr_free (name_expr);
+ isl_id_free (name_id);
+
+ gcc_assert (GBB_BB (gbb) != ENTRY_BLOCK_PTR_FOR_FN (cfun) &&
+ "The entry block should not even appear within a scop");
+
+ loop_p loop = gbb_loop (gbb);
+ iv_map.create (loop->num + 1);
+ int i;
+ for (i = 0; i < loop->num + 1; i++)
+ iv_map.quick_push (NULL_TREE);
+
+ build_iv_mapping (iv_map, gbb, user_expr, ip, SCOP_REGION (pbb->scop));
+ isl_ast_expr_free (user_expr);
+ next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb),
+ SCOP_REGION (pbb->scop), next_e,
+ iv_map,
+ &graphite_regenerate_error);
+ iv_map.release ();
+ mark_virtual_operands_for_renaming (cfun);
+ update_ssa (TODO_update_ssa);
+ return next_e;
+}
+
/* Translates an ISL AST node NODE to GCC representation in the
context of a SESE. */
@@ -561,7 +628,7 @@
return next_e;
case isl_ast_node_user:
- return next_e;
+ return translate_isl_ast_node_user (node, next_e, ip);
case isl_ast_node_block:
return next_e;
