Re: [PATCH] Fix for PR52009 - Another missed tail merging opportunity
On Wed, Jul 4, 2012 at 8:07 PM, Tom de Vries tom_devr...@mentor.com wrote: On 31/01/12 22:07, Tom de Vries wrote: On 31/01/12 22:05, Tom de Vries wrote: Richard, Sorry, with patch this time. this patch fixes PR52009. Consider this test-case: ... int z; void foo (int y) { if (y == 6) z = 5; else z = 5; } ... Currently, compiling with -O2 gives us this representation at pr51879-7.c.094t.pre: ... # BLOCK 3 freq:1991 # PRED: 2 [19.9%] (true,exec) # .MEMD.1710_4 = VDEF .MEMD.1710_3(D) zD.1702 = 5; goto bb 5; # SUCC: 5 [100.0%] (fallthru,exec) # BLOCK 4 freq:8009 # PRED: 2 [80.1%] (false,exec) # .MEMD.1710_5 = VDEF .MEMD.1710_3(D) zD.1702 = 5; # SUCC: 5 [100.0%] (fallthru,exec) # BLOCK 5 freq:1 # PRED: 3 [100.0%] (fallthru,exec) 4 [100.0%] (fallthru,exec) # .MEMD.1710_2 = PHI .MEMD.1710_4(3), .MEMD.1710_5(4) # VUSE .MEMD.1710_2 return; ... Blocks 3 and 4 are not tail-merged. The patch allows the example to be tail-merged by: - value numbering .MEMD.1710_4 and .MEMD.1710_5 equal - comparing gimple_vdef value numbers for assignments during tail-merge Bootstrapped and reg-tested on x86_64. OK for stage1? Richard, I did some trivial changes such that the patch is applicable again to trunk, and added a test-case, which you suggested in http://gcc.gnu.org/ml/gcc-patches/2012-05/msg00220.html. The test-case handles the case of 2 identical calls assigning to different deferenced pointers, where the pointers are value-numbered the same: ... void bar (int c, int *p) { int *q = p; if (c) *p = foo (); else *q = foo (); } ... The representation before pre looks like this: ... # BLOCK 3 freq:3900 # PRED: 2 [39.0%] (true,exec) # .MEMD.1724_8 = VDEF .MEMD.1724_7(D) # USE = nonlocal # CLB = nonlocal D.1721_4 = fooD.1712 (); # .MEMD.1724_9 = VDEF .MEMD.1724_8 *pD.1714_1(D) = D.1721_4; goto bb 5; # SUCC: 5 [100.0%] (fallthru,exec) # BLOCK 4 freq:6100 # PRED: 2 [61.0%] (false,exec) # .MEMD.1724_10 = VDEF .MEMD.1724_7(D) # USE = nonlocal # CLB = nonlocal D.1723_5 = fooD.1712 (); # .MEMD.1724_11 = VDEF .MEMD.1724_10 *qD.1717_2 = D.1723_5; # SUCC: 5 [100.0%] (fallthru,exec) ... In pre, we're already value numbering the result and vdef of the calls the same, and the pointers the same: ... Value numbers: q_2 = p_1(D) D.1723_5 = D.1721_4 .MEM_10 = .MEM_8 ... But not the vdefs of the stores. This patch implements that, and allows the blocks to be merged. ok for trunk? Ok. Thanks, Richard. Thanks, - Tom 2012-07-04 Tom de Vries t...@codesourcery.com PR tree-optimization/52009 * tree-ssa-tail-merge.c (gimple_equal_p): For GIMPLE_ASSIGN, compare value numbers of gimple_vdef. * tree-ssa-sccvn.h (vn_reference_insert): Add vdef parameter to prototype. * tree-ssa-sccvn.c (copy_reference_ops_from_ref): Handle MODIFY_EXPR. (vn_reference_insert): Add and handle vdef parameter. (visit_reference_op_load): Add argument to vn_reference_insert call. (visit_reference_op_store): Find value number of vdef of store. Insert value number of vdef of store. * gcc.dg/pr51879-7.c: New test. * gcc.dg/pr51879-18.c: New test.
Re: [PATCH] Fix for PR52009 - Another missed tail merging opportunity
On 31/01/12 22:07, Tom de Vries wrote: On 31/01/12 22:05, Tom de Vries wrote: Richard, Sorry, with patch this time. this patch fixes PR52009. Consider this test-case: ... int z; void foo (int y) { if (y == 6) z = 5; else z = 5; } ... Currently, compiling with -O2 gives us this representation at pr51879-7.c.094t.pre: ... # BLOCK 3 freq:1991 # PRED: 2 [19.9%] (true,exec) # .MEMD.1710_4 = VDEF .MEMD.1710_3(D) zD.1702 = 5; goto bb 5; # SUCC: 5 [100.0%] (fallthru,exec) # BLOCK 4 freq:8009 # PRED: 2 [80.1%] (false,exec) # .MEMD.1710_5 = VDEF .MEMD.1710_3(D) zD.1702 = 5; # SUCC: 5 [100.0%] (fallthru,exec) # BLOCK 5 freq:1 # PRED: 3 [100.0%] (fallthru,exec) 4 [100.0%] (fallthru,exec) # .MEMD.1710_2 = PHI .MEMD.1710_4(3), .MEMD.1710_5(4) # VUSE .MEMD.1710_2 return; ... Blocks 3 and 4 are not tail-merged. The patch allows the example to be tail-merged by: - value numbering .MEMD.1710_4 and .MEMD.1710_5 equal - comparing gimple_vdef value numbers for assignments during tail-merge Bootstrapped and reg-tested on x86_64. OK for stage1? Richard, I did some trivial changes such that the patch is applicable again to trunk, and added a test-case, which you suggested in http://gcc.gnu.org/ml/gcc-patches/2012-05/msg00220.html. The test-case handles the case of 2 identical calls assigning to different deferenced pointers, where the pointers are value-numbered the same: ... void bar (int c, int *p) { int *q = p; if (c) *p = foo (); else *q = foo (); } ... The representation before pre looks like this: ... # BLOCK 3 freq:3900 # PRED: 2 [39.0%] (true,exec) # .MEMD.1724_8 = VDEF .MEMD.1724_7(D) # USE = nonlocal # CLB = nonlocal D.1721_4 = fooD.1712 (); # .MEMD.1724_9 = VDEF .MEMD.1724_8 *pD.1714_1(D) = D.1721_4; goto bb 5; # SUCC: 5 [100.0%] (fallthru,exec) # BLOCK 4 freq:6100 # PRED: 2 [61.0%] (false,exec) # .MEMD.1724_10 = VDEF .MEMD.1724_7(D) # USE = nonlocal # CLB = nonlocal D.1723_5 = fooD.1712 (); # .MEMD.1724_11 = VDEF .MEMD.1724_10 *qD.1717_2 = D.1723_5; # SUCC: 5 [100.0%] (fallthru,exec) ... In pre, we're already value numbering the result and vdef of the calls the same, and the pointers the same: ... Value numbers: q_2 = p_1(D) D.1723_5 = D.1721_4 .MEM_10 = .MEM_8 ... But not the vdefs of the stores. This patch implements that, and allows the blocks to be merged. ok for trunk? Thanks, - Tom 2012-07-04 Tom de Vries t...@codesourcery.com PR tree-optimization/52009 * tree-ssa-tail-merge.c (gimple_equal_p): For GIMPLE_ASSIGN, compare value numbers of gimple_vdef. * tree-ssa-sccvn.h (vn_reference_insert): Add vdef parameter to prototype. * tree-ssa-sccvn.c (copy_reference_ops_from_ref): Handle MODIFY_EXPR. (vn_reference_insert): Add and handle vdef parameter. (visit_reference_op_load): Add argument to vn_reference_insert call. (visit_reference_op_store): Find value number of vdef of store. Insert value number of vdef of store. * gcc.dg/pr51879-7.c: New test. * gcc.dg/pr51879-18.c: New test. Index: gcc/tree-ssa-tail-merge.c === --- gcc/tree-ssa-tail-merge.c (revision 189007) +++ gcc/tree-ssa-tail-merge.c (working copy) @@ -1119,6 +1119,14 @@ gimple_equal_p (same_succ same_succ, gim case GIMPLE_ASSIGN: lhs1 = gimple_get_lhs (s1); lhs2 = gimple_get_lhs (s2); + if (gimple_vdef (s1)) + { + if (vn_valueize (gimple_vdef (s1)) != vn_valueize (gimple_vdef (s2))) + return false; + if (TREE_CODE (lhs1) != SSA_NAME + TREE_CODE (lhs2) != SSA_NAME) + return true; + } return (TREE_CODE (lhs1) == SSA_NAME TREE_CODE (lhs2) == SSA_NAME vn_valueize (lhs1) == vn_valueize (lhs2)); Index: gcc/tree-ssa-sccvn.c === --- gcc/tree-ssa-sccvn.c (revision 189007) +++ gcc/tree-ssa-sccvn.c (working copy) @@ -628,6 +628,9 @@ copy_reference_ops_from_ref (tree ref, V switch (temp.opcode) { + case MODIFY_EXPR: + temp.op0 = TREE_OPERAND (ref, 1); + break; case WITH_SIZE_EXPR: temp.op0 = TREE_OPERAND (ref, 1); temp.off = 0; @@ -748,6 +751,7 @@ copy_reference_ops_from_ref (tree ref, V VEC_safe_push (vn_reference_op_s, heap, *result, temp); if (REFERENCE_CLASS_P (ref) + || TREE_CODE (ref) == MODIFY_EXPR || TREE_CODE (ref) == WITH_SIZE_EXPR || (TREE_CODE (ref) == ADDR_EXPR !is_gimple_min_invariant (ref))) @@ -1941,7 +1945,7 @@ vn_reference_lookup (tree op, tree vuse, RESULT, and return the resulting reference structure we created. */ vn_reference_t -vn_reference_insert (tree op, tree result, tree vuse) +vn_reference_insert (tree op, tree result, tree vuse, tree vdef) { void **slot; vn_reference_t vr1; @@ -1957,6 +1961,7 @@
Re: [PATCH] Fix for PR52009 - Another missed tail merging opportunity
On 31/01/12 22:05, Tom de Vries wrote: Richard, Sorry, with patch this time. this patch fixes PR52009. Consider this test-case: ... int z; void foo (int y) { if (y == 6) z = 5; else z = 5; } ... Currently, compiling with -O2 gives us this representation at pr51879-7.c.094t.pre: ... # BLOCK 3 freq:1991 # PRED: 2 [19.9%] (true,exec) # .MEMD.1710_4 = VDEF .MEMD.1710_3(D) zD.1702 = 5; goto bb 5; # SUCC: 5 [100.0%] (fallthru,exec) # BLOCK 4 freq:8009 # PRED: 2 [80.1%] (false,exec) # .MEMD.1710_5 = VDEF .MEMD.1710_3(D) zD.1702 = 5; # SUCC: 5 [100.0%] (fallthru,exec) # BLOCK 5 freq:1 # PRED: 3 [100.0%] (fallthru,exec) 4 [100.0%] (fallthru,exec) # .MEMD.1710_2 = PHI .MEMD.1710_4(3), .MEMD.1710_5(4) # VUSE .MEMD.1710_2 return; ... Blocks 3 and 4 are not tail-merged. The patch allows the example to be tail-merged by: - value numbering .MEMD.1710_4 and .MEMD.1710_5 equal - comparing gimple_vdef value numbers for assignments during tail-merge Bootstrapped and reg-tested on x86_64. OK for stage1? Thanks, - Tom 2012-01-31 Tom de Vries t...@codesourcery.com PR tree-optimization/52009 * tree-ssa-tail-merge.c (gimple_equal_p): For GIMPLE_ASSIGN, compare value numbers of gimple_vdef. * tree-ssa-sccvn.h (struct vn_reference_s): Add vdef field. (vn_reference_insert): Add vdef parameter to prototype. * tree-ssa-sccvn.c (copy_reference_ops_from_ref): Handle MODIFY_EXPR. (vn_reference_insert): Add and handle vdef parameter. (visit_reference_op_load): Add argument to vn_reference_insert call. (visit_reference_op_store): Find value number of vdef of store. Insert value number of vdef of store. * gcc.dg/pr51879-7.c: New test. Index: gcc/tree-ssa-tail-merge.c === --- gcc/tree-ssa-tail-merge.c (revision 183325) +++ gcc/tree-ssa-tail-merge.c (working copy) @@ -1087,6 +1087,14 @@ gimple_equal_p (same_succ same_succ, gim case GIMPLE_ASSIGN: lhs1 = gimple_get_lhs (s1); lhs2 = gimple_get_lhs (s2); + if (gimple_vdef (s1)) + { + if (vn_valueize (gimple_vdef (s1)) != vn_valueize (gimple_vdef (s2))) + return false; + if (TREE_CODE (lhs1) != SSA_NAME + TREE_CODE (lhs2) != SSA_NAME) + return true; + } return (TREE_CODE (lhs1) == SSA_NAME TREE_CODE (lhs2) == SSA_NAME vn_valueize (lhs1) == vn_valueize (lhs2)); Index: gcc/tree-ssa-sccvn.c === --- gcc/tree-ssa-sccvn.c (revision 183325) +++ gcc/tree-ssa-sccvn.c (working copy) @@ -624,6 +624,9 @@ copy_reference_ops_from_ref (tree ref, V switch (temp.opcode) { + case MODIFY_EXPR: + temp.op0 = TREE_OPERAND (ref, 1); + break; case MEM_REF: /* The base address gets its own vn_reference_op_s structure. */ temp.op0 = TREE_OPERAND (ref, 1); @@ -740,6 +743,7 @@ copy_reference_ops_from_ref (tree ref, V VEC_safe_push (vn_reference_op_s, heap, *result, temp); if (REFERENCE_CLASS_P (ref) + || TREE_CODE (ref) == MODIFY_EXPR || (TREE_CODE (ref) == ADDR_EXPR !is_gimple_min_invariant (ref))) ref = TREE_OPERAND (ref, 0); @@ -1928,7 +1932,7 @@ vn_reference_lookup (tree op, tree vuse, RESULT, and return the resulting reference structure we created. */ vn_reference_t -vn_reference_insert (tree op, tree result, tree vuse) +vn_reference_insert (tree op, tree result, tree vuse, tree vdef) { void **slot; vn_reference_t vr1; @@ -1944,6 +1948,7 @@ vn_reference_insert (tree op, tree resul vr1-set = get_alias_set (op); vr1-hashcode = vn_reference_compute_hash (vr1); vr1-result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result; + vr1-vdef = vdef; slot = htab_find_slot_with_hash (current_info-references, vr1, vr1-hashcode, INSERT); @@ -2725,7 +2730,7 @@ visit_reference_op_load (tree lhs, tree else { changed = set_ssa_val_to (lhs, lhs); - vn_reference_insert (op, lhs, last_vuse); + vn_reference_insert (op, lhs, last_vuse, NULL_TREE); } return changed; @@ -2739,8 +2744,11 @@ static bool visit_reference_op_store (tree lhs, tree op, gimple stmt) { bool changed = false; - tree result; + vn_reference_t vnresult = NULL; + tree result, assign; bool resultsame = false; + tree vuse = gimple_vuse (stmt); + tree vdef = gimple_vdef (stmt); /* First we want to lookup using the *vuses* from the store and see if there the last store to this location with the same address @@ -2758,7 +2766,7 @@ visit_reference_op_store (tree lhs, tree Otherwise, the vdefs for the store are used when inserting into the table, since the store generates a new memory state. */ - result = vn_reference_lookup (lhs, gimple_vuse (stmt), VN_NOWALK, NULL); + result = vn_reference_lookup (lhs,