| Message ID | 87fu268ywj.fsf@linaro.org |
|---|---|
| State | Accepted |
| Commit | 33031ee69097eeac734dfba91b717d5e9a583073 |
| Headers | show |
| Series | Fix phi backedge detection in backprop (PR85989) | expand |
On Fri, Jun 1, 2018 at 2:38 PM Richard Sandiford <richard.sandiford@linaro.org> wrote: > > This PR is a nasty wrong code bug due to my fluffing a test for a > backedge in gimple-ssa-backprop.c. Backedges are supposed to be > from definitions in the statement we're visiting to uses in statements > that we haven't visited yet. However, the check failed to account for > PHIs in the current block that had already been processed, so if two > PHIs in the same block referenced each other, we'd treat both > references as backedges. > > In more detail: > > The first phase of the pass goes through all statements in an arbitrary > order, making optimistic assumptions about any statements that haven't > been visited yet. The second phase then calculates a correct > (supposedly maximal) fixed point. > > Although the first phase order is arbitrary in principle, we still use > the CFG rpo to cut down on the backedges. This means that the only > thing that's truly arbitrary is the order that we process the PHIs > in a block. Any order should be OK and should eventually give the > same results. But we have to follow whatever order we pick, > and the pass wasn't doing that. > > Tested on aarch64-linux-gnu (with and without SVE), aarch64_be-elf > and x86_64-linux-gnu. OK for trunk and all release branches? OK. Thanks, Richard. > Sorry for what in hindsight was a really stupid bug. > > Richard > > > > 2018-06-01 Richard Sandiford <richard.sandiford@linaro.org> > > gcc/ > PR tree-optimization/85989 > * gimple-ssa-backprop.c (backprop::m_visited_phis): New member > variable. > (backprop::intersect_uses): Check it when deciding whether this > is a backedge reference. > (backprop::process_block): Add each phi to m_visited_phis > after visiting it, then clear it at the end. > > gcc/testsuite/ > PR tree-optimization/85989 > * gcc.dg/torture/pr85989.c: New test. > > Index: gcc/gimple-ssa-backprop.c > =================================================================== > --- gcc/gimple-ssa-backprop.c 2018-05-18 09:26:37.726714678 +0100 > +++ gcc/gimple-ssa-backprop.c 2018-06-01 13:36:04.223449400 +0100 > @@ -260,6 +260,11 @@ dump_usage_info (FILE *file, tree var, u > post-order walk. */ > auto_sbitmap m_visited_blocks; > > + /* A bitmap of phis that we have finished processing in the initial > + post-order walk, excluding those from blocks mentioned in > + M_VISITED_BLOCKS. */ > + auto_bitmap m_visited_phis; > + > /* A worklist of SSA names whose definitions need to be reconsidered. */ > auto_vec <tree, 64> m_worklist; > > @@ -496,8 +501,11 @@ backprop::intersect_uses (tree var, usag > { > if (is_gimple_debug (stmt)) > continue; > - if (is_a <gphi *> (stmt) > - && !bitmap_bit_p (m_visited_blocks, gimple_bb (stmt)->index)) > + gphi *phi = dyn_cast <gphi *> (stmt); > + if (phi > + && !bitmap_bit_p (m_visited_blocks, gimple_bb (phi)->index) > + && !bitmap_bit_p (m_visited_phis, > + SSA_NAME_VERSION (gimple_phi_result (phi)))) > { > /* Skip unprocessed phis. */ > if (dump_file && (dump_flags & TDF_DETAILS)) > @@ -505,7 +513,7 @@ backprop::intersect_uses (tree var, usag > fprintf (dump_file, "[BACKEDGE] "); > print_generic_expr (dump_file, var); > fprintf (dump_file, " in "); > - print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); > + print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); > } > } > else > @@ -629,7 +637,12 @@ backprop::process_block (basic_block bb) > } > for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi); > gsi_next (&gpi)) > - process_var (gimple_phi_result (gpi.phi ())); > + { > + tree result = gimple_phi_result (gpi.phi ()); > + process_var (result); > + bitmap_set_bit (m_visited_phis, SSA_NAME_VERSION (result)); > + } > + bitmap_clear (m_visited_phis); > } > > /* Delete the definition of VAR, which has no uses. */ > Index: gcc/testsuite/gcc.dg/torture/pr85989.c > =================================================================== > --- /dev/null 2018-04-20 16:19:46.369131350 +0100 > +++ gcc/testsuite/gcc.dg/torture/pr85989.c 2018-06-01 13:36:04.223449400 +0100 > @@ -0,0 +1,31 @@ > +/* { dg-do run } */ > + > +#define N 9 > + > +void __attribute__((noipa)) > +f (double x, double y, double *res) > +{ > + y = -y; > + for (int i = 0; i < N; ++i) > + { > + double tmp = y; > + y = x; > + x = tmp; > + res[i] = i; > + } > + res[N] = y * y; > + res[N + 1] = x; > +} > + > +int > +main (void) > +{ > + double res[N + 2]; > + f (10, 20, res); > + for (int i = 0; i < N; ++i) > + if (res[i] != i) > + __builtin_abort (); > + if (res[N] != 100 || res[N + 1] != -20) > + __builtin_abort (); > + return 0; > +}
Index: gcc/gimple-ssa-backprop.c =================================================================== --- gcc/gimple-ssa-backprop.c 2018-05-18 09:26:37.726714678 +0100 +++ gcc/gimple-ssa-backprop.c 2018-06-01 13:36:04.223449400 +0100 @@ -260,6 +260,11 @@ dump_usage_info (FILE *file, tree var, u post-order walk. */ auto_sbitmap m_visited_blocks; + /* A bitmap of phis that we have finished processing in the initial + post-order walk, excluding those from blocks mentioned in + M_VISITED_BLOCKS. */ + auto_bitmap m_visited_phis; + /* A worklist of SSA names whose definitions need to be reconsidered. */ auto_vec <tree, 64> m_worklist; @@ -496,8 +501,11 @@ backprop::intersect_uses (tree var, usag { if (is_gimple_debug (stmt)) continue; - if (is_a <gphi *> (stmt) - && !bitmap_bit_p (m_visited_blocks, gimple_bb (stmt)->index)) + gphi *phi = dyn_cast <gphi *> (stmt); + if (phi + && !bitmap_bit_p (m_visited_blocks, gimple_bb (phi)->index) + && !bitmap_bit_p (m_visited_phis, + SSA_NAME_VERSION (gimple_phi_result (phi)))) { /* Skip unprocessed phis. */ if (dump_file && (dump_flags & TDF_DETAILS)) @@ -505,7 +513,7 @@ backprop::intersect_uses (tree var, usag fprintf (dump_file, "[BACKEDGE] "); print_generic_expr (dump_file, var); fprintf (dump_file, " in "); - print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); } } else @@ -629,7 +637,12 @@ backprop::process_block (basic_block bb) } for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi); gsi_next (&gpi)) - process_var (gimple_phi_result (gpi.phi ())); + { + tree result = gimple_phi_result (gpi.phi ()); + process_var (result); + bitmap_set_bit (m_visited_phis, SSA_NAME_VERSION (result)); + } + bitmap_clear (m_visited_phis); } /* Delete the definition of VAR, which has no uses. */ Index: gcc/testsuite/gcc.dg/torture/pr85989.c =================================================================== --- /dev/null 2018-04-20 16:19:46.369131350 +0100 +++ gcc/testsuite/gcc.dg/torture/pr85989.c 2018-06-01 13:36:04.223449400 +0100 @@ -0,0 +1,31 @@ +/* { dg-do run } */ + +#define N 9 + +void __attribute__((noipa)) +f (double x, double y, double *res) +{ + y = -y; + for (int i = 0; i < N; ++i) + { + double tmp = y; + y = x; + x = tmp; + res[i] = i; + } + res[N] = y * y; + res[N + 1] = x; +} + +int +main (void) +{ + double res[N + 2]; + f (10, 20, res); + for (int i = 0; i < N; ++i) + if (res[i] != i) + __builtin_abort (); + if (res[N] != 100 || res[N + 1] != -20) + __builtin_abort (); + return 0; +}