This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[graphite] Handle guard_stmt (if conditions) in the code generator of graphite.
- From: Jan Sjodin <jan_sjodin at yahoo dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 22 Aug 2008 14:55:55 -0700 (PDT)
- Subject: [graphite] Handle guard_stmt (if conditions) in the code generator of graphite.
This patch implements translation of clast guard_stmt to gimple. There are a few test cases that fail with this patch because it exposes a bug where scalar dependences that are not handled correctly. We plan to fix this next.
This patch was committed to the graphite branch as rev 139498.
- Jan
Index: cfgloopmanip.c
===================================================================
--- cfgloopmanip.c (revision 139497)
+++ cfgloopmanip.c (revision 139498)
@@ -503,6 +503,88 @@ static void update_dominators_in_loop (s
VEC_free (basic_block, heap, dom_bbs);
}
+/* Creates an if region as shown above. CONDITION is used to create
+ the test for the if.
+
+ |
+ | ------------- -------------
+ | | pred_bb | | pred_bb |
+ | ------------- -------------
+ | | |
+ | | | ENTRY_EDGE
+ | | ENTRY_EDGE V
+ | | ====> -------------
+ | | | cond_bb |
+ | | | CONDITION |
+ | | -------------
+ | V / \
+ | ------------- e_false / \ e_true
+ | | succ_bb | V V
+ | ------------- ----------- -----------
+ | | false_bb | | true_bb |
+ | ----------- -----------
+ | \ /
+ | \ /
+ | V V
+ | -------------
+ | | join_bb |
+ | -------------
+ | | exit_edge (result)
+ | V
+ | -----------
+ | | succ_bb |
+ | -----------
+ |
+ */
+
+edge
+create_empty_if_region_on_edge (edge entry_edge, tree condition)
+{
+
+ basic_block succ_bb, cond_bb, true_bb, false_bb, join_bb;
+ edge e_true, e_false, exit_edge;
+ gimple cond_stmt;
+ tree simple_cond;
+ gimple_stmt_iterator gsi;
+
+ succ_bb = entry_edge->dest;
+ cond_bb = split_edge (entry_edge);
+
+ /* Insert condition in cond_bb. */
+ gsi = gsi_last_bb (cond_bb);
+ simple_cond =
+ force_gimple_operand_gsi (&gsi, condition, true, NULL,
+ false, GSI_NEW_STMT);
+ cond_stmt = gimple_build_cond_from_tree (simple_cond, NULL_TREE, NULL_TREE);
+ gsi = gsi_last_bb (cond_bb);
+ gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
+
+ join_bb = split_edge (single_succ_edge (cond_bb));
+
+ e_true = single_succ_edge (cond_bb);
+ true_bb = split_edge (e_true);
+
+ e_false = make_edge (cond_bb, join_bb, 0);
+ false_bb = split_edge (e_false);
+
+ e_true->flags &= ~EDGE_FALLTHRU;
+ e_true->flags |= EDGE_TRUE_VALUE;
+ e_false->flags &= ~EDGE_FALLTHRU;
+ e_false->flags |= EDGE_FALSE_VALUE;
+
+ set_immediate_dominator (CDI_DOMINATORS, cond_bb, entry_edge->src);
+ set_immediate_dominator (CDI_DOMINATORS, true_bb, cond_bb);
+ set_immediate_dominator (CDI_DOMINATORS, false_bb, cond_bb);
+ set_immediate_dominator (CDI_DOMINATORS, join_bb, cond_bb);
+
+ exit_edge = single_succ_edge (join_bb);
+
+ if (single_pred_p (exit_edge->dest))
+ set_immediate_dominator (CDI_DOMINATORS, exit_edge->dest, join_bb);
+
+ return exit_edge;
+}
+
/* create_empty_loop_on_edge
|
| ------------- ------------------------
Index: graphite.c
===================================================================
--- graphite.c (revision 139497)
+++ graphite.c (revision 139498)
@@ -2756,7 +2756,10 @@ clast_to_gcc_expression (struct clast_ex
struct clast_expr *lhs = (struct clast_expr *) b->LHS;
struct clast_expr *rhs = (struct clast_expr *) b->RHS;
tree tl = clast_to_gcc_expression (lhs, type, params, ivstack);
- tree tr = clast_to_gcc_expression (rhs, type, params, ivstack);
+
+ /* Cloog assumes a constant as RHS, the warning cannot be eliminated
+ because of the type of Value. Cloog must be fixed. */
+ tree tr = gmp_cst_to_tree (rhs);
switch (b->type)
{
@@ -2784,6 +2787,69 @@ clast_to_gcc_expression (struct clast_ex
return NULL_TREE;
}
+/* Translates a clast equation CLEQ to a tree. */
+
+static tree
+graphite_translate_clast_equation (scop_p scop,
+ struct clast_equation *cleq,
+ loop_iv_stack ivstack)
+{
+ tree result = NULL;
+ enum tree_code comp;
+ tree lhs = clast_to_gcc_expression(cleq->LHS,
+ integer_type_node,
+ SCOP_PARAMS (scop),
+ ivstack);
+ tree rhs = clast_to_gcc_expression(cleq->RHS,
+ integer_type_node,
+ SCOP_PARAMS (scop),
+ ivstack);
+ if (cleq->sign == 0)
+ comp = EQ_EXPR;
+ else if (cleq->sign > 0)
+ comp = GE_EXPR;
+ else
+ comp = LE_EXPR;
+
+ result = fold_build2 (comp, integer_type_node, lhs, rhs);
+ return result;
+}
+
+/* Creates the test for the condition in STMT. */
+
+static tree
+graphite_create_guard_cond_expr (scop_p scop, struct clast_guard *stmt,
+ loop_iv_stack ivstack)
+{
+ tree cond = NULL;
+ int i;
+ for (i = 0; i < stmt->n; i++)
+ {
+ tree equation =
+ graphite_translate_clast_equation (scop, &stmt->eq[i], ivstack);
+ if (cond)
+ cond = fold_build2 (TRUTH_AND_EXPR, integer_type_node,
+ cond, equation);
+ else
+ cond = equation;
+ }
+
+ return cond;
+}
+
+/* Creates a new if region corresponding to Cloog's guard. */
+
+static edge
+graphite_create_new_guard (scop_p scop, edge entry_edge,
+ struct clast_guard *stmt,
+ loop_iv_stack ivstack)
+{
+ tree cond_expr = graphite_create_guard_cond_expr (scop, stmt, ivstack);
+ edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
+ return exit_edge;
+}
+
+
/* Creates a new LOOP corresponding to Cloog's STMT. Inserts an induction
variable for the new LOOP. New LOOP is attached to CFG starting at
ENTRY_EDGE. LOOP is inserted into the loop tree and becomes the child
@@ -2850,22 +2916,6 @@ remove_all_edges (basic_block bb, edge k
remove_all_edges_1 (bb->preds, keep);
}
-/* Returns the stack index for LOOP in GBB. */
-
-static int
-get_stack_index_from_iv (graphite_bb_p gbb, loop_p loop)
-{
- int i;
- loop_p current_loop;
-
- for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gbb), i, current_loop); i++)
- if (loop == current_loop)
- return i;
-
- gcc_unreachable();
- return -1;
-}
-
/* Rename the SSA_NAMEs used in STMT and that appear in IVSTACK. */
static void
@@ -2883,7 +2933,7 @@ graphite_rename_ivs_stmt (gimple stmt, g
if (old_iv)
{
- int a = get_stack_index_from_iv (gbb, old_iv->loop);
+ int a = gbb_loop_index (gbb, old_iv->loop);
new_iv = loop_iv_stack_get_iv (ivstack, a);
}
@@ -2958,6 +3008,22 @@ remove_cond_exprs (basic_block bb)
}
}
+/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
+
+static edge
+get_true_edge_from_guard_bb (basic_block bb)
+{
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (e->flags & EDGE_TRUE_VALUE)
+ return e;
+
+ gcc_unreachable ();
+ return NULL;
+}
+
/* Translates a CLAST statement STMT to GCC representation. NEXT_E is
the edge where new generated code should be attached. BB_EXIT is the last
basic block that defines the scope of code generation. CONTEXT_LOOP is the
@@ -3021,6 +3087,19 @@ translate_clast (scop_p scop, struct loo
return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
}
+ if (CLAST_STMT_IS_A (stmt, stmt_guard))
+ {
+ edge last_e = graphite_create_new_guard (scop, next_e,
+ ((struct clast_guard *) stmt),
+ ivstack);
+ edge true_e = get_true_edge_from_guard_bb (next_e->dest);
+ next_e = translate_clast (scop, context_loop,
+ ((struct clast_guard *) stmt)->then,
+ true_e, ivstack);
+ redirect_edge_succ_nodup (next_e, last_e->src);
+ return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
+ }
+
if (CLAST_STMT_IS_A (stmt, stmt_block))
{
next_e = translate_clast (scop, context_loop,
@@ -3236,10 +3315,31 @@ get_construction_edge (scop_p scop)
return EDGE_PRED (entry, 0);
else
- /* FIXME: This is not handled yet. For fixing this we should
- have SCOPs defined as single entry single exit regions,
- that means that SCOP_ENTRY and SCOP_EXIT should be edges. */
- return NULL;
+ {
+ /* FIXME: This is not handled yet. For fixing this we should
+ have SCOPs defined as single entry single exit regions,
+ that means that SCOP_ENTRY and SCOP_EXIT should be edges. */
+ /* We can refine this slightly if one of the predecessors
+ is the immediate dominator of the block. */
+ edge e;
+ edge_iterator ei;
+ basic_block entry_idom = get_immediate_dominator (CDI_DOMINATORS,
+ entry);
+
+ FOR_EACH_EDGE (e, ei, entry->preds)
+ if (e->src == entry_idom)
+ {
+ /* If the successor is in a different loop we must insert
+ a basic block between to guarantee that a loop exit
+ will not be going directly to the entry of another
+ loop. */
+ if (e->src->loop_father != e->dest->loop_father)
+ split_edge (e);
+ return e;
+ }
+
+ return NULL;
+ }
}
/* Return a vector of all the virtual phi nodes in the current
@@ -3460,6 +3560,10 @@ can_generate_code_stmt (struct clast_stm
used_basic_blocks)
&& can_generate_code_stmt (stmt->next, used_basic_blocks);
+ if (CLAST_STMT_IS_A (stmt, stmt_guard))
+ return can_generate_code_stmt (((struct clast_guard *) stmt)->then,
+ used_basic_blocks);
+
if (CLAST_STMT_IS_A (stmt, stmt_block))
return can_generate_code_stmt (((struct clast_block *) stmt)->body,
used_basic_blocks)
@@ -3518,7 +3622,8 @@ gloog (scop_p scop, struct clast_stmt *s
}
gather_blocks_in_sese_region (SCOP_ENTRY (scop), SCOP_EXIT (scop), &bbs);
- new_scop_exit_edge = translate_clast (scop, SCOP_ENTRY(scop)->loop_father,
+ new_scop_exit_edge = translate_clast (scop,
+ construction_edge->src->loop_father,
stmt, construction_edge, &ivstack);
redirect_edge_succ (new_scop_exit_edge, scop_exit);
cloog_clast_free (stmt);
@@ -3546,7 +3651,6 @@ gloog (scop_p scop, struct clast_stmt *s
#ifdef ENABLE_CHECKING
verify_loop_structure ();
verify_dominators (CDI_DOMINATORS);
- verify_dominators (CDI_POST_DOMINATORS);
#endif
rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
Index: cfgloop.h
===================================================================
--- cfgloop.h (revision 139497)
+++ cfgloop.h (revision 139498)
@@ -280,6 +280,7 @@ extern bool can_duplicate_loop_p (const
#define DLTHE_FLAG_COMPLETTE_PEEL 4 /* Update frequencies expecting
a complete peeling. */
+extern edge create_empty_if_region_on_edge (edge, tree);
extern struct loop *create_empty_loop_on_edge (edge, tree, tree, tree, tree,
tree *, struct loop *);
extern struct loop * duplicate_loop (struct loop *, struct loop *);
Index: ChangeLog.graphite
===================================================================
--- ChangeLog.graphite (revision 139497)
+++ ChangeLog.graphite (revision 139498)
@@ -1,3 +1,22 @@
+2008-08-22 Jan Sjodin <jan.sjodin@amd.com>
+
+ * cfgloopmanip.c (create_empty_if_region_on_edge): New.
+ * graphite.c (clast_to_gcc_expression): Call gmp_cst_to_tree
+ instead of recursive call.
+ (graphite_translate_clast_equation): New.
+ (graphite_create_guard_cond_expr): New.
+ (graphite_create_new_guard): New.
+ (get_stack_index_from_iv): Removed.
+ (graphite_rename_ivs_stmt): Use gbb_loop_index.
+ (get_true_edge_from_guard_bb): New.
+ (translate_clast): Handle stmt_guard in clast.
+ (get_construction_edge): Allow construction edge detection for
+ a scope entry with multiple predecessors if one predecessor is
+ the immediate dominator of scope entry.
+ (can_generate_code_stmt): Enable code generation for clast_guard.
+ (gloog): Use correct context loop. Removed check for post dominators.
+ * cfgloop.h (create_empty_if_region_on_edge): Declared.
+
2008-08-21 Sebastian Pop <sebastian.pop@amd.com>
* graphite.c (remove_dead_loops): Document better which