[GSoC] generation of GCC expression trees from isl ast expressions
Roman Gareev
gareevroman@gmail.com
Wed Jun 25 14:25:00 GMT 2014
Hi Tobias,
I haven't found out how to use unit tests in gcc. I've asked community
about this. Maybe it is better to postpone testing using DejaGnu tests
until generation of loops with empty bodies is finished, because we
have to traverse isl ast to transform expressions anyway. What do you
think about this?
I've written the following functions to compare the semantics of the
GCC and isl expressions: isl_ast_bin_expression_comp_test and
graphite_bin_expression_comp_test. graphite_bin_expression_comp_test
compares the result of evaluation of binary tree expression of the
given type with the given assumed result.
isl_ast_bin_expression_comp_test the result of evaluation of binary
isl_ast_expression with the given assumed result. They are called
after “if (dump_file && (dump_flags & TDF_DETAILS))» and can be
eliminated in the future. However, it seems that it is impossible to
verify all types of isl_ast_expression, because only add, sub, mul,
div, and, or can be generated. If I am not mistaken, there is a
possibility of generation of any isl_ast_expression using
isl_ast_epxr_alloc_binary, but it is missing in isl_ast.h. Could you
please advise me what can be done in this situation?
I've rewritten the generation of isl_ast_expr_int, but after
successful building of gcc the following error arises:
/home/roman/compiled/build/graphite8/libexec/gcc/x86_64-unknown-linux-gnu/4.10.0/cc1plus:
symbol lookup error:
/home/roman/compiled/build/graphite8/libexec/gcc/x86_64-unknown-linux-gnu/4.10.0/cc1plus:
undefined symbol: isl_val_from_gmp
Do you know anything about this mistake? Should I use something
undocumented in isl manual, but important for Graphite like
+#if defined(__cplusplus)
+extern "C" {
+#endif
+#include <isl/val_gmp.h>
+#if defined(__cplusplus)
+}
+#endif
I have to write the code above to use isl_val_get_num_gmp from isl/val_gmp.h.
--
Cheers, Roman Gareev
-------------- next part --------------
diff --git a/gcc/graphite-isl-ast-to-gimple.c b/gcc/graphite-isl-ast-to-gimple.c
index 6ddaa28..d5efd94 100644
--- a/gcc/graphite-isl-ast-to-gimple.c
+++ b/gcc/graphite-isl-ast-to-gimple.c
@@ -20,10 +20,15 @@ along with GCC; see the file COPYING3. If not see
#include "config.h"
-#include <isl/set.h>
#include <isl/map.h>
-#include <isl/union_map.h>
#include <isl/ast_build.h>
+#if defined(__cplusplus)
+extern "C" {
+#endif
+#include <isl/val_gmp.h>
+#if defined(__cplusplus)
+}
+#endif
#include "system.h"
#include "coretypes.h"
@@ -49,6 +54,323 @@ along with GCC; see the file COPYING3. If not see
static bool graphite_regenerate_error;
+/* Converts a GMP constant VAL to a tree and returns it. */
+
+static tree
+gmp_cst_to_tree (tree type, mpz_t val)
+{
+ tree t = type ? type : integer_type_node;
+ mpz_t tmp;
+
+ mpz_init (tmp);
+ mpz_set (tmp, val);
+ wide_int wi = wi::from_mpz (t, tmp, true);
+ mpz_clear (tmp);
+
+ return wide_int_to_tree (t, wi);
+}
+
+static tree
+gcc_expression_from_isl_expression (tree type, __isl_keep isl_ast_expr *);
+
+/* Converts a isl_ast_expr_int expression E to a GCC expression tree of
+ type TYPE. */
+
+static tree
+gcc_expression_from_isl_expr_int (tree type, __isl_keep isl_ast_expr *expr)
+{
+ gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int);
+ isl_val *val = isl_ast_expr_get_val (expr);
+ mpz_t val_mpz_t;
+ mpz_init (val_mpz_t);
+ tree res;
+ if (isl_val_get_num_gmp (val, val_mpz_t) == -1)
+ res = NULL_TREE;
+ else
+ res = gmp_cst_to_tree (type, val_mpz_t);
+ isl_val_free (val);
+ mpz_clear (val_mpz_t);
+ return res;
+}
+
+/* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
+ type TYPE. */
+
+static tree
+binary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr)
+{
+ isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+ tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr);
+ isl_ast_expr_free (arg_expr);
+ arg_expr = isl_ast_expr_get_op_arg (expr, 1);
+ tree tree_rhs_expr = gcc_expression_from_isl_expression (type, arg_expr);
+ isl_ast_expr_free (arg_expr);
+ switch (isl_ast_expr_get_op_type (expr))
+ {
+ case isl_ast_op_add:
+ return fold_build2 (PLUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_sub:
+ return fold_build2 (MINUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_mul:
+ return fold_build2 (MULT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_div:
+ return fold_build2 (EXACT_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_fdiv_q:
+ return fold_build2 (FLOOR_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_and:
+ return fold_build2 (TRUTH_ANDIF_EXPR, type,
+ tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_or:
+ return fold_build2 (TRUTH_ORIF_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_eq:
+ return fold_build2 (EQ_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_le:
+ return fold_build2 (LE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_lt:
+ return fold_build2 (LT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_ge:
+ return fold_build2 (GE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_gt:
+ return fold_build2 (GT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ default:
+ gcc_unreachable ();
+ }
+}
+
+/* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
+ type TYPE. */
+
+static tree
+ternary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr)
+{
+ gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
+ isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+ tree tree_first_expr = gcc_expression_from_isl_expression (type, arg_expr);
+ isl_ast_expr_free (arg_expr);
+ arg_expr = isl_ast_expr_get_op_arg (expr, 1);
+ tree tree_second_expr = gcc_expression_from_isl_expression (type, arg_expr);
+ isl_ast_expr_free (arg_expr);
+ arg_expr = isl_ast_expr_get_op_arg (expr, 2);
+ tree tree_third_expr = gcc_expression_from_isl_expression (type, arg_expr);
+ isl_ast_expr_free (arg_expr);
+ return fold_build3 (COND_EXPR, type, tree_first_expr,
+ tree_second_expr, tree_third_expr);
+}
+
+/* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
+ type TYPE. */
+
+static tree
+unary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr)
+{
+ gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_cond);
+ isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+ tree tree_expr = gcc_expression_from_isl_expression (type, arg_expr);
+ isl_ast_expr_free (arg_expr);
+ return fold_build1 (NEGATE_EXPR, type, tree_expr);
+}
+
+/* Converts a isl_ast_expr_op expression E with unknown number of arguments
+ to a GCC expression tree of type TYPE. */
+
+static tree
+nary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr)
+{
+ enum tree_code op_code;
+ switch (isl_ast_expr_get_op_type (expr))
+ {
+ case isl_ast_op_max:
+ op_code = MAX_EXPR;
+ break;
+
+ case isl_ast_op_min:
+ op_code = MIN_EXPR;
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+ isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+ tree res = gcc_expression_from_isl_expression (type, arg_expr);
+ isl_ast_expr_free (arg_expr);
+ int i;
+ for (i = 1; i < isl_ast_expr_get_op_n_arg (expr); i++)
+ {
+ arg_expr = isl_ast_expr_get_op_arg (expr, i);
+ tree t = gcc_expression_from_isl_expression (type, arg_expr);
+ res = fold_build2 (op_code, type, res, t);
+ isl_ast_expr_free (arg_expr);
+ }
+ return res;
+}
+
+
+/* Converts a isl_ast_expr_op expression E to a GCC expression tree of
+ type TYPE. */
+
+static tree
+gcc_expression_from_isl_expr_op (tree type, __isl_keep isl_ast_expr *expr)
+{
+ gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_op);
+ switch (isl_ast_expr_get_op_type (expr))
+ {
+ /* These isl ast expressions are not supported yet */
+ case isl_ast_op_error:
+ case isl_ast_op_call:
+ case isl_ast_op_and_then:
+ case isl_ast_op_or_else:
+ case isl_ast_op_pdiv_q:
+ case isl_ast_op_pdiv_r:
+ case isl_ast_op_select:
+ gcc_unreachable ();
+
+ case isl_ast_op_max:
+ case isl_ast_op_min:
+ return nary_op_to_tree (type, expr);
+
+ case isl_ast_op_add:
+ case isl_ast_op_sub:
+ case isl_ast_op_mul:
+ case isl_ast_op_div:
+ case isl_ast_op_fdiv_q:
+ case isl_ast_op_and:
+ case isl_ast_op_or:
+ case isl_ast_op_eq:
+ case isl_ast_op_le:
+ case isl_ast_op_lt:
+ case isl_ast_op_ge:
+ case isl_ast_op_gt:
+ return binary_op_to_tree (type, expr);
+
+ case isl_ast_op_minus:
+ return unary_op_to_tree (type, expr);
+
+ case isl_ast_op_cond:
+ return ternary_op_to_tree (type, expr);
+
+ default:
+ gcc_unreachable ();
+ }
+
+ return NULL_TREE;
+}
+
+/* Converts a ISL AST expression E back to a GCC expression tree of
+ type TYPE. */
+
+static tree
+gcc_expression_from_isl_expression (tree type, __isl_keep isl_ast_expr *expr)
+{
+ switch (isl_ast_expr_get_type (expr))
+ {
+ case isl_ast_expr_id:
+ gcc_unreachable ();
+
+ case isl_ast_expr_int:
+ return gcc_expression_from_isl_expr_int (type, expr);
+
+ case isl_ast_expr_op:
+ return gcc_expression_from_isl_expr_op (type, expr);
+
+ default:
+ gcc_unreachable ();
+ }
+
+ return NULL_TREE;
+}
+
+/* Compares result of graphite binary expression with type OP_CODE and OP1,
+ OP2 arguments of tree type TYPE with predicted result PRED_RES.
+ TRUE if they are equal. */
+
+bool
+graphite_bin_expression_comp_test (enum tree_code op_code, tree type,
+ tree op1, tree op2, tree pred_res)
+{
+ tree res = fold_binary_to_constant (op_code, type, op1, op2);
+ /* res is NULL_TREE if it is not a constant */
+ gcc_assert (res != NULL);
+ return operand_equal_p (res, pred_res, OEP_PURE_SAME);
+}
+
+/* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
+ the given SCOP. Return true if code generation succeeded. */
+
+bool
+graphite_bin_expression_comp_test (enum tree_code op_code, int iop1,
+ int iop2, int ipred_res)
+{
+ mpz_t op1;
+ mpz_t op2;
+ mpz_t pred_res;
+ /* By default these operands are always converted to signed 128 */
+ tree type = build_nonstandard_integer_type (128, 0);
+ mpz_init_set_si (op1, iop1);
+ mpz_init_set_si (op2, iop2);
+ mpz_init_set_si (pred_res, ipred_res);
+ tree tree_op1 = gmp_cst_to_tree (type, op1);
+ tree tree_op2 = gmp_cst_to_tree (type, op2);
+ tree tree_pred_res = gmp_cst_to_tree (type, pred_res);
+ bool status = graphite_bin_expression_comp_test (op_code, type, tree_op1,
+ tree_op2, tree_pred_res);
+ mpz_clear (op1);
+ mpz_clear (op2);
+ mpz_clear (pred_res);
+ return status;
+}
+
+/* Compares result of isl binary expression converted to Gimple expression
+ with code OP_TYPE and OP1, OP2 arguments of int type with predicted result
+ IPRED_RES. TRUE if they are equal. */
+
+/*bool
+isl_ast_bin_expression_comp_test (enum isl_ast_op_type op_type, int iop1,
+ int iop2, int ipred_res)*/
+bool
+isl_ast_bin_expression_comp_test (int iop1, int iop2, int ipred_res)
+{
+ mpz_t op1;
+ mpz_t op2;
+ mpz_t one;
+ mpz_t pred_res;
+ /* By default these operands are always converted to signed 128 */
+ tree type = build_nonstandard_integer_type (128, 0);
+ mpz_init_set_si (op1, iop1);
+ mpz_init_set_si (op2, iop2);
+ mpz_init_set_si (op2, 1);
+ mpz_init_set_si (pred_res, ipred_res);
+ isl_ctx *ctx = isl_ctx_alloc ();
+ isl_val *op1_val = isl_val_from_gmp (ctx, op1, one);
+ isl_val *op2_val = isl_val_from_gmp (ctx, op2, one);
+ isl_ast_expr *expr_op1 = isl_ast_expr_from_val (op1_val);
+ isl_ast_expr *expr_op2 = isl_ast_expr_from_val (op2_val);
+ /* isl_ast_expr *expr =
+ isl_ast_expr_alloc_binary (op_type, expr_op1, expr_op2);*/
+ isl_ast_expr *expr = isl_ast_expr_add (expr_op1, expr_op2);
+ tree tree_expr = gcc_expression_from_isl_expression (type, expr);
+ tree tree_pred_res = gmp_cst_to_tree (type, pred_res);
+ bool status = operand_equal_p (tree_expr, tree_pred_res, OEP_PURE_SAME);
+ isl_ctx_free (ctx);
+ isl_ast_expr_free (expr);
+ mpz_clear (op1);
+ mpz_clear (op2);
+ mpz_clear (one);
+ mpz_clear (pred_res);
+ return status;
+}
+
/* Prints NODE to FILE. */
void
@@ -125,6 +447,11 @@ graphite_regenerate_ast_isl (scop_p scop)
isl_ast_node *root_node = scop_to_isl_ast (scop);
if (dump_file && (dump_flags & TDF_DETAILS))
{
+ gcc_assert (graphite_bin_expression_comp_test (PLUS_EXPR,
+ 1, -2, -1) == true);
+ /* gcc_assert (isl_ast_bin_expression_comp_test (isl_ast_op_add,
+ 1, -2, -1) == true); */
+ gcc_assert (isl_ast_bin_expression_comp_test (1, -2, -1) == true);
fprintf (dump_file, "\nISL AST generated by ISL: \n");
print_isl_ast_node (dump_file, root_node, scop->ctx);
}
More information about the Gcc
mailing list