[tree-ssa] Insert on edge fix.
Andrew MacLeod
amacleod@redhat.com
Thu May 15 22:39:00 GMT 2003
Whilst attempting to bootstrap with overlapping live ranges and
copyprop, I encountered a bootstrap problem when building the stage 3
compiler. (I hate those. At least it wasnt a verification error!)
The situation is:
BLOCK 0
x_1 = blah;
if (cond)
BLOCK 1
x_2 = blah2;
BLOCK 2
x_3 = PHI <x_1(0), x_2(1)>
well, it just so happens that copy prop replaces x_1 and x_2 with blah's
leaving us with:
BLOCK 0
x_1 = blah;
if (cond)
BLOCK 1
x_2 = blah2;
BLOCK 2
x_3 = PHI <blah(0), blah2(1)>
the SSA->Normal pass realizes it needs to insert stuff onto each edge,
but insert_on_edge doesn't do the (0,2) edge properly.
So, here's the changes to make insert_on_edge do the right thing.
If the else clause doesn't exist, then we'll create a new basic block
and make it the else clause. At the same time, I've added code to handle
insertions on the edges to the THEN and ELSE clauses when the edge it
critical. This can happen when the first stmt in the clause is a label,
and there exists a GOTO that label.
Those are all the issues I was aware of for insert_on_edge, and I was
finally forced to deal with them :-)
There was also a blatent bug in bsi_insert_before. If you inserted at
the head of a basic block, it didn't update the BB head pointer. Not
sure how that was missed. I also added some code to check if we've
inserted at the head of a block which is pointed to by a LOOP_EXPR or
COND_EXPR, and update those pointers appropriately.
bootstrapped, verified, etc.
Andrew
-------------- next part --------------
2003-05-15 Andrew MacLeod <amacleod@redhat.com>
* tree-cfg.c (enum find_location_action): Enum for find_insert_location.
(bsi_insert_before): Handle insert at start of a BB and update pointers
from parents if appropriate.
(find_insert_location): Handle COND_EXPR properly. Return
an enum type indicating what action to take on the returned value.
(bsi_commit_first_edge_insert): Use new returned action.
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.87
diff -c -p -r1.1.4.87 tree-cfg.c
*** tree-cfg.c 9 May 2003 19:20:06 -0000 1.1.4.87
--- tree-cfg.c 15 May 2003 21:51:52 -0000
*************** static block_stmt_iterator bsi_init PAR
*** 138,144 ****
static inline void bsi_update_from_tsi PARAMS (( block_stmt_iterator *, tree_stmt_iterator));
static tree_stmt_iterator bsi_link_after PARAMS ((tree_stmt_iterator *, tree, basic_block, tree));
static block_stmt_iterator bsi_commit_first_edge_insert PARAMS ((edge, tree));
! static tree_stmt_iterator find_insert_location PARAMS ((basic_block, basic_block, int *));
/* Location to track pending stmt for edge insertion. */
#define PENDING_STMT(e) ((tree)(e->insns))
--- 138,154 ----
static inline void bsi_update_from_tsi PARAMS (( block_stmt_iterator *, tree_stmt_iterator));
static tree_stmt_iterator bsi_link_after PARAMS ((tree_stmt_iterator *, tree, basic_block, tree));
static block_stmt_iterator bsi_commit_first_edge_insert PARAMS ((edge, tree));
!
! /* Values returned by location parameter of find_insert_location. */
!
! enum find_location_action {
! EDGE_INSERT_LOCATION_BEFORE,
! EDGE_INSERT_LOCATION_AFTER,
! EDGE_INSERT_LOCATION_THEN,
! EDGE_INSERT_LOCATION_ELSE,
! EDGE_INSERT_LOCATION_NEW_ELSE };
!
! static tree_stmt_iterator find_insert_location PARAMS ((basic_block, basic_block, enum find_location_action *));
/* Location to track pending stmt for edge insertion. */
#define PENDING_STMT(e) ((tree)(e->insns))
*************** bsi_insert_before (curr_bsi, t, mode)
*** 3499,3507 ****
same_tsi = inserted_tsi;
tsi_next (&same_tsi);
! if (curr_container == curr_bb->end_tree_p)
! curr_bb->end_tree_p = tsi_container (same_tsi);
!
if (mode == BSI_SAME_STMT)
bsi_update_from_tsi (curr_bsi, same_tsi);
else
--- 3509,3544 ----
same_tsi = inserted_tsi;
tsi_next (&same_tsi);
!
! if (curr_container == curr_bb->head_tree_p)
! {
! curr_bb->head_tree_p = tsi_container (same_tsi);
! /* If the parent block is a COND_EXPR or LOOP_EXPR, check if this
! is the block which they point to and update if necessary. */
! if (parent)
! {
! tree insert_container = *tsi_container (inserted_tsi);
! switch (TREE_CODE (parent))
! {
! case COND_EXPR:
! if (bb_for_stmt (COND_EXPR_THEN (parent)) == curr_bb)
! COND_EXPR_THEN (parent) = insert_container;
! else
! if (bb_for_stmt (COND_EXPR_ELSE (parent)) == curr_bb)
! COND_EXPR_ELSE (parent) = insert_container;
! break;
!
! case LOOP_EXPR:
! if (bb_for_stmt (LOOP_EXPR_BODY (parent)) == curr_bb)
! LOOP_EXPR_BODY (parent) = insert_container;
! break;
!
! default:
! break;
! }
! }
! }
!
if (mode == BSI_SAME_STMT)
bsi_update_from_tsi (curr_bsi, same_tsi);
else
*************** bsi_insert_before (curr_bsi, t, mode)
*** 3515,3546 ****
return;
}
-
/* Given an edge between src and dest, return a TSI representing the location
that any instructions on this edge should be inserted.
! A flag indicating whether to insert the new stmt before or after the
! iterator is returned in the 'after' parameter. */
static tree_stmt_iterator
! find_insert_location (src, dest, after)
basic_block src;
basic_block dest;
! int *after;
{
block_stmt_iterator bsi;
tree *ret, stmt;
! *after = 0;
bsi = bsi_last (src);
if (!bsi_end_p (bsi))
{
stmt = bsi_stmt (bsi);
switch (TREE_CODE (stmt))
! {
case COND_EXPR:
case LOOP_EXPR:
ret = src->end_tree_p;
! *after = 1;
break;
default:
--- 3552,3610 ----
return;
}
/* Given an edge between src and dest, return a TSI representing the location
that any instructions on this edge should be inserted.
! The location parameter returns a value indicating how this iterator is
! to be used. */
static tree_stmt_iterator
! find_insert_location (src, dest, location)
basic_block src;
basic_block dest;
! enum find_location_action *location;
{
block_stmt_iterator bsi;
tree *ret, stmt;
! *location = EDGE_INSERT_LOCATION_BEFORE;
bsi = bsi_last (src);
if (!bsi_end_p (bsi))
{
stmt = bsi_stmt (bsi);
switch (TREE_CODE (stmt))
! {
case COND_EXPR:
+ /* If the ELSE block is non-existant, and this is an edge from the
+ COND_EXPR to a block other than the THEN block, then we create
+ a new ELSE clause. */
+ if (bb_for_stmt (COND_EXPR_ELSE (stmt)) == NULL)
+ if (bb_for_stmt (COND_EXPR_THEN (stmt)) != dest)
+ {
+ ret = &COND_EXPR_ELSE (stmt);
+ *location = EDGE_INSERT_LOCATION_NEW_ELSE;
+ break;
+ }
+
+ /* It must be an edge from the COND_EXPR to either the THEN or
+ ELSE block. We will need to insert a new stmt in front of the
+ first stmt in the block, *and* update the pointer to the
+ THEN or ELSE clause. */
+ if (bb_for_stmt (COND_EXPR_THEN (stmt)) == dest)
+ {
+ ret = &COND_EXPR_THEN (stmt);
+ *location = EDGE_INSERT_LOCATION_THEN;
+ }
+ else
+ {
+ ret = &COND_EXPR_ELSE (stmt);
+ *location = EDGE_INSERT_LOCATION_ELSE;
+ }
+ break;
+
+
case LOOP_EXPR:
ret = src->end_tree_p;
! *location = EDGE_INSERT_LOCATION_AFTER;
break;
default:
*************** find_insert_location (src, dest, after)
*** 3552,3559 ****
ret = src->end_tree_p;
return tsi_start (ret);
-
}
/* This routine inserts a stmt on an edge. Every attempt is made to place the
stmt in an existing basic block, but sometimes that isn't possible. When
it isn't possible, a new basic block is created, edges updated, and the
--- 3616,3623 ----
ret = src->end_tree_p;
return tsi_start (ret);
}
+
/* This routine inserts a stmt on an edge. Every attempt is made to place the
stmt in an existing basic block, but sometimes that isn't possible. When
it isn't possible, a new basic block is created, edges updated, and the
*************** bsi_commit_first_edge_insert (e, stmt)
*** 3567,3573 ****
basic_block src, dest, new_bb;
block_stmt_iterator bsi, tmp;
tree_stmt_iterator tsi;
! int single_exit, single_entry, after;
tree first, last, inserted_stmt, parent;
bb_ann_t bb_ann;
--- 3631,3638 ----
basic_block src, dest, new_bb;
block_stmt_iterator bsi, tmp;
tree_stmt_iterator tsi;
! int single_exit, single_entry;
! enum find_location_action location;
tree first, last, inserted_stmt, parent;
bb_ann_t bb_ann;
*************** bsi_commit_first_edge_insert (e, stmt)
*** 3662,3687 ****
bb_ann->ephi_nodes = NULL_TREE;
bb_ann->dom_children = (bitmap) NULL;
! tsi = find_insert_location (src, dest, &after);
parent = parent_stmt (tsi_stmt (tsi));
! if (after)
! tsi_link_after (&tsi, stmt, TSI_NEW_STMT);
! else
! tsi_link_before (&tsi, stmt, TSI_NEW_STMT);
append_stmt_to_bb (tsi_container (tsi), new_bb, parent);
inserted_stmt = tsi_stmt (tsi);
bsi = bsi_from_tsi (tsi);
! /* It is also known for a fact that the container for the head of the dest
! block has been changed. (we've linked a new stmt in front of it.) */
! tsi_next (&tsi);
!
! /* Handle the case of one stmt in a basic block, so it is both the head and
! the end of the block. */
! if (dest->end_tree_p == dest->head_tree_p)
! dest->end_tree_p = tsi_container (tsi);
! dest->head_tree_p = tsi_container (tsi);
/* Now update the required SSA bits. */
modify_stmt (inserted_stmt);
--- 3727,3786 ----
bb_ann->ephi_nodes = NULL_TREE;
bb_ann->dom_children = (bitmap) NULL;
! tsi = find_insert_location (src, dest, &location);
parent = parent_stmt (tsi_stmt (tsi));
!
! switch (location)
! {
! case EDGE_INSERT_LOCATION_BEFORE:
! case EDGE_INSERT_LOCATION_THEN:
! case EDGE_INSERT_LOCATION_ELSE:
! case EDGE_INSERT_LOCATION_NEW_ELSE:
! tsi_link_before (&tsi, stmt, TSI_NEW_STMT);
! break;
!
! case EDGE_INSERT_LOCATION_AFTER:
! tsi_link_after (&tsi, stmt, TSI_NEW_STMT);
! break;
! }
append_stmt_to_bb (tsi_container (tsi), new_bb, parent);
inserted_stmt = tsi_stmt (tsi);
bsi = bsi_from_tsi (tsi);
! switch (location)
! {
! case EDGE_INSERT_LOCATION_THEN:
! case EDGE_INSERT_LOCATION_ELSE:
! stmt = last_stmt (src);
! if (location == EDGE_INSERT_LOCATION_THEN)
! COND_EXPR_THEN (stmt) = inserted_stmt;
! else
! COND_EXPR_ELSE (stmt) = inserted_stmt;
! /* Fallthru. */
!
! case EDGE_INSERT_LOCATION_BEFORE:
! case EDGE_INSERT_LOCATION_AFTER:
! /* The container for the head of the dest block has been changed.
! (we've linked a new stmt in front of it.) */
!
! tsi_next (&tsi);
! if (dest->end_tree_p == dest->head_tree_p)
! dest->end_tree_p = tsi_container (tsi);
! dest->head_tree_p = tsi_container (tsi);
! break;
!
! case EDGE_INSERT_LOCATION_NEW_ELSE:
! /* This causes a new stmt chain to be formed, and the ELSE clause needs
! to be set. Set the block number for the empty stmt which might
! follow this stmt as well. */
! stmt = last_stmt (src);
! COND_EXPR_ELSE (stmt) = inserted_stmt;
! tsi_next (&tsi);
! if (tsi_container (tsi))
! append_stmt_to_bb (tsi_container (tsi), new_bb, parent);
! break;
! }
/* Now update the required SSA bits. */
modify_stmt (inserted_stmt);
More information about the Gcc-patches
mailing list