| Summary: | [4.5 Regression] dom1 miscompiles binary search | ||
|---|---|---|---|
| Product: | gcc | Reporter: | Michael Matz <matz> |
| Component: | tree-optimization | Assignee: | Richard Biener <rguenth> |
| Status: | RESOLVED FIXED | ||
| Severity: | critical | CC: | gcc-bugs, rguenth |
| Priority: | P1 | Keywords: | wrong-code |
| Version: | 4.5.0 | ||
| Target Milestone: | 4.5.0 | ||
| Host: | x86_64-linux | Target: | |
| Build: | Known to work: | ||
| Known to fail: | Last reconfirmed: | 2010-03-17 16:42:29 | |
| Attachments: | testcase | ||
Created attachment 20127 [details]
testcase
Testcase reduced from ucnv_bld.c of libicu
Confirmed. It seems the jump threading somehow confuses cfgcleanup. Right after the
jumps are threaded (in tree_ssa_dominator_optimize after the call to
thread_through_all_blocks) the function looks like so:
<bb 2>:
goto <bb 9>;
<bb 3>:
# start_16 = PHI <mid_10(6), start_1(10)>
# limit_19 = PHI <limit_2(6), mid_10(10)>
# lastMid_15 = PHI <mid_10(6), mid_10(10)>
<bb 4>:
# start_1 = PHI <start_16(3)>
# limit_2 = PHI <limit_19(3)>
# lastMid_3 = PHI <mid_10(3)>
D.2744_9 = start_1 + limit_2;
mid_10 = D.2744_9 / 2;
if (lastMid_3 == mid_10)
goto <bb 8>;
else
goto <bb 5>;
<bb 6>:
if (result_14 > 0)
goto <bb 3>;
else
goto <bb 7>;
<bb 7>:
D.2754_17 = cnvNameType[mid_10].type;
D.2753_18 = converterData[D.2754_17];
<bb 8>:
# D.2753_4 = PHI <D.2753_18(7), 0B(4)>
return D.2753_4;
<bb 9>:
# start_21 = PHI <0(2)>
# limit_22 = PHI <3(2)>
# lastMid_23 = PHI <4294967295(2)>
D.2744_24 = start_1 + limit_2;
mid_25 = D.2744_9 / 2;
goto <bb 10>;
<bb 5>:
<bb 10>:
D.2746_12 = cnvNameType[mid_10].name;
result_14 = __builtin_strcmp (realName_13(D), D.2746_12);
if (result_14 < 0)
goto <bb 3>;
else
goto <bb 6>;
At that point the PHI nodes for BB 10 are still missing, and we have
registered these ssaname updates:
start_21 -> { start_1 }
limit_22 -> { limit_2 }
lastMid_23 -> { lastMid_3 }
D.2744_24 -> { D.2744_9 }
mid_25 -> { mid_10 }
With the right PHI nodes at bb 10 the code still looks good. But somehow
cfgcleanup scrambles the whole thing.
Um, we cleanup the CFG before updating SSA form, hence no wonder that the missing PHI nodes confuse it. Hmm, create_edge_and_update_destination_phis is supposed to add new PHI arguments for the ultimate threading destination. But it only does so if there are already PHI nodes in that BB. We need to create new ones, which is difficult as we would have to create a new SSA name to hold the result, and rewrite all dominating uses. I wonder how this all is supposed to work. It is caused by revision 157093: http://gcc.gnu.org/ml/gcc-cvs/2010-02/msg00676.html Hmm, I wonder how that could cause the bug. Probably because we can't rely on SSA form being uptodate during cfgcleanup, and hence looking up PHI arguments is wrong, at least for those SSA names that are registered for updating. (In reply to comment #7) > Hmm, I wonder how that could cause the bug. Probably because we can't rely > on SSA form being uptodate during cfgcleanup, and hence looking up PHI > arguments is wrong, at least for those SSA names that are registered for > updating. But you can't have SSA names around when you rename its symbol. And only with SSA names the lookup is performed. After DOM (but before cfgcleanup completes) we have <bb 4>: # start_1 = PHI <start_16(3)> # limit_2 = PHI <limit_19(3)> # lastMid_3 = PHI <mid_10(3)> D.1978_9 = start_1 + limit_2; mid_10 = D.1978_9 >> 1; if (lastMid_3 == mid_10) goto <bb 8>; else goto <bb 5>; which is then simplified. Hm. It seems we have a SSA name replacement table, thus probably the cfgcleanup lookup code has to honor this. The following seems to fix it: Index: tree-cfgcleanup.c =================================================================== *** tree-cfgcleanup.c (revision 157512) --- tree-cfgcleanup.c (working copy) *************** cleanup_control_expr_graph (basic_block *** 100,123 **** { tree lhs = gimple_cond_lhs (stmt); tree rhs = gimple_cond_rhs (stmt); ! /* For conditions try harder and lookup single-argument ! PHI nodes. Only do so from the same basic-block though ! as other basic-blocks may be dead already. */ ! if (TREE_CODE (lhs) == SSA_NAME) { ! gimple def_stmt = SSA_NAME_DEF_STMT (lhs); ! if (gimple_code (def_stmt) == GIMPLE_PHI ! && gimple_phi_num_args (def_stmt) == 1 ! && gimple_bb (def_stmt) == gimple_bb (stmt)) ! lhs = PHI_ARG_DEF (def_stmt, 0); ! } ! if (TREE_CODE (rhs) == SSA_NAME) ! { ! gimple def_stmt = SSA_NAME_DEF_STMT (rhs); ! if (gimple_code (def_stmt) == GIMPLE_PHI ! && gimple_phi_num_args (def_stmt) == 1 ! && gimple_bb (def_stmt) == gimple_bb (stmt)) ! rhs = PHI_ARG_DEF (def_stmt, 0); } val = fold_binary_loc (loc, gimple_cond_code (stmt), boolean_type_node, lhs, rhs); --- 100,126 ---- { tree lhs = gimple_cond_lhs (stmt); tree rhs = gimple_cond_rhs (stmt); ! if (!name_mappings_registered_p ()) { ! /* For conditions try harder and lookup single-argument ! PHI nodes. Only do so from the same basic-block though ! as other basic-blocks may be dead already. */ ! if (TREE_CODE (lhs) == SSA_NAME) ! { ! gimple def_stmt = SSA_NAME_DEF_STMT (lhs); ! if (gimple_code (def_stmt) == GIMPLE_PHI ! && gimple_phi_num_args (def_stmt) == 1 ! && gimple_bb (def_stmt) == gimple_bb (stmt)) ! lhs = PHI_ARG_DEF (def_stmt, 0); ! } ! if (TREE_CODE (rhs) == SSA_NAME) ! { ! gimple def_stmt = SSA_NAME_DEF_STMT (rhs); ! if (gimple_code (def_stmt) == GIMPLE_PHI ! && gimple_phi_num_args (def_stmt) == 1 ! && gimple_bb (def_stmt) == gimple_bb (stmt)) ! rhs = PHI_ARG_DEF (def_stmt, 0); ! } } val = fold_binary_loc (loc, gimple_cond_code (stmt), boolean_type_node, lhs, rhs); though the essence of r157093 was to capture single-valued PHI nodes with constant operands, so we could restrict the lookup to consider constants only. Subject: Bug 43402 Author: matz Date: Thu Mar 18 12:20:50 2010 New Revision: 157538 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=157538 Log: PR tree-optimization/43402 * tree-cfgcleanup.c (cleanup_control_expr_graph): Don't follow PHI chains of ssa names registered for update. testsuite/ * gcc.dg/pr43402.c: New testcase. Added: trunk/gcc/testsuite/gcc.dg/pr43402.c Modified: trunk/gcc/ChangeLog trunk/gcc/testsuite/ChangeLog trunk/gcc/tree-cfgcleanup.c Fixed. Subject: Bug 43402 Author: hjl Date: Thu Mar 25 16:39:51 2010 New Revision: 157726 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=157726 Log: Backport regression testcases from mainline. 2010-03-25 H.J. Lu <hongjiu.lu@intel.com> Backport from mainline: 2010-03-22 Jason Merrill <jason@redhat.com> PR c++/43333 * g++.dg/ext/is_pod_98.C: New. 2010-03-22 Michael Matz <matz@suse.de> PR middle-end/43475 * gfortran.dg/pr43475.f90: New testcase. 2010-03-22 Richard Guenther <rguenther@suse.de> PR tree-optimization/43390 * gfortran.fortran-torture/execute/pr43390.f90: New testcase. 2010-03-20 Dodji Seketeli <dodji@redhat.com> PR c++/43375 * g++.dg/abi/mangle42.C: New test. 2010-03-19 Andrew Pinski <andrew_pinski@caviumnetworks.com> PR C/43211 * gcc.dg/pr43211.c: New test. 2010-03-18 Martin Jambor <mjambor@suse.cz> PR middle-end/42450 * g++.dg/torture/pr42450.C: New test. 2010-03-18 Michael Matz <matz@suse.de> PR tree-optimization/43402 * gcc.dg/pr43402.c: New testcase. 2010-03-17 Peter Bergner <bergner@vnet.ibm.com> PR target/42427 * gcc.dg/pr42427.c: New test. 2010-03-16 Richard Guenther <rguenther@suse.de> PR middle-end/43379 * gcc.dg/pr43379.c: New testcase. 2010-03-15 Michael Matz <matz@suse.de> PR middle-end/43300 * gcc.dg/pr43300.c: New testcase. 2010-03-15 Richard Guenther <rguenther@suse.de> PR tree-optimization/43367 * gcc.c-torture/compile/pr43367.c: New testcase. Added: branches/gcc-4_4-branch/gcc/testsuite/g++.dg/abi/mangle42.C - copied unchanged from r157725, trunk/gcc/testsuite/g++.dg/abi/mangle42.C branches/gcc-4_4-branch/gcc/testsuite/g++.dg/ext/is_pod_98.C - copied unchanged from r157725, trunk/gcc/testsuite/g++.dg/ext/is_pod_98.C branches/gcc-4_4-branch/gcc/testsuite/g++.dg/torture/pr42450.C - copied unchanged from r157725, trunk/gcc/testsuite/g++.dg/torture/pr42450.C branches/gcc-4_4-branch/gcc/testsuite/gcc.c-torture/compile/pr43367.c - copied unchanged from r157725, trunk/gcc/testsuite/gcc.c-torture/compile/pr43367.c branches/gcc-4_4-branch/gcc/testsuite/gcc.dg/pr42427.c - copied unchanged from r157725, trunk/gcc/testsuite/gcc.dg/pr42427.c branches/gcc-4_4-branch/gcc/testsuite/gcc.dg/pr43211.c - copied unchanged from r157725, trunk/gcc/testsuite/gcc.dg/pr43211.c branches/gcc-4_4-branch/gcc/testsuite/gcc.dg/pr43300.c - copied unchanged from r157725, trunk/gcc/testsuite/gcc.dg/pr43300.c branches/gcc-4_4-branch/gcc/testsuite/gcc.dg/pr43379.c - copied unchanged from r157725, trunk/gcc/testsuite/gcc.dg/pr43379.c branches/gcc-4_4-branch/gcc/testsuite/gcc.dg/pr43402.c - copied unchanged from r157725, trunk/gcc/testsuite/gcc.dg/pr43402.c branches/gcc-4_4-branch/gcc/testsuite/gfortran.dg/pr43475.f90 - copied unchanged from r157725, trunk/gcc/testsuite/gfortran.dg/pr43475.f90 branches/gcc-4_4-branch/gcc/testsuite/gfortran.fortran-torture/execute/pr43390.f90 - copied unchanged from r157725, trunk/gcc/testsuite/gfortran.fortran-torture/execute/pr43390.f90 Modified: branches/gcc-4_4-branch/gcc/testsuite/ChangeLog |
This actually happens in libicu, preventing genbrk (and hence openoffice and texlive) to work. # gcc -O1 icubug.c && ./a.out Aborted With -O0 it works. The wrong transformation is done by dom1, it transforms the loop into a linear sequence without backedges. <bb 2>: goto <bb 8>; <bb 3>: # start_16 = PHI <mid_25(5), start_21(8)> # limit_19 = PHI <limit_22(5), mid_25(8)> # lastMid_15 = PHI <mid_25(5), mid_25(8)> <bb 4>: # start_1 = PHI <start_16(3)> # limit_2 = PHI <limit_19(3)> # lastMid_3 = PHI <mid_25(3)> D.2744_9 = start_1 + limit_2; mid_10 = D.2744_9 / 2; goto <bb 7>; <bb 5>: if (result_14 > 0) goto <bb 3>; else goto <bb 6>; <bb 6>: D.2754_17 = cnvNameType[mid_25].type; D.2753_18 = converterData[D.2754_17]; <bb 7>: # D.2753_4 = PHI <D.2753_18(6), 0B(4)> return D.2753_4; <bb 8>: # start_21 = PHI <0(2)> # limit_22 = PHI <3(2)> # lastMid_23 = PHI <4294967295(2)> D.2744_24 = start_21 + limit_22; mid_25 = D.2744_24 / 2; D.2746_12 = cnvNameType[mid_25].name; result_14 = __builtin_strcmp (realName_13(D), D.2746_12); if (result_14 < 0) goto <bb 3>; else goto <bb 5>;