From c0bfd9672e19caf08e45afeb4277f848488ced2b Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Fri, 30 Oct 2020 09:57:02 +0100 Subject: [PATCH] tree-optimization/97633 - fix SLP scheduling of single-node cycles This makes sure to update backedges in single-node cycles. 2020-10-30 Richard Biener PR tree-optimization/97633 * tree-vect-slp.c (): Update backedges in single-node cycles. Optimize processing of externals. * g++.dg/vect/slp-pr97636.cc: New testcase. * gcc.dg/vect/bb-slp-pr97633.c: Likewise. --- gcc/testsuite/g++.dg/vect/slp-pr97636.cc | 83 +++++++++++ gcc/testsuite/gcc.dg/vect/bb-slp-pr97633.c | 27 ++++ gcc/tree-vect-slp.c | 162 +++++++++++---------- 3 files changed, 198 insertions(+), 74 deletions(-) create mode 100644 gcc/testsuite/g++.dg/vect/slp-pr97636.cc create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-pr97633.c diff --git a/gcc/testsuite/g++.dg/vect/slp-pr97636.cc b/gcc/testsuite/g++.dg/vect/slp-pr97636.cc new file mode 100644 index 00000000000..012342004f1 --- /dev/null +++ b/gcc/testsuite/g++.dg/vect/slp-pr97636.cc @@ -0,0 +1,83 @@ +/* { dg-do compile } */ +/* { dg-require-effective-target c++17 } */ + +struct u { + int b; + int c; + template u(d, e); +}; +template struct f { u g; }; +template class v { + typedef f k; + k *l[4]; + k m; +public: + v(h, h); + void aa(h, i); +}; +template void v::aa(h, i) { n(&l[1], &m); } +template void n(f **o, f *ab) { + bool p, r; + f q = **o; + f *t; + h a = q.g; + h b = t->g; + if (r) + ; + else + goto ac; +s: + p = a.b || a.c < b.c; + if (p) + goto s; +ac: + ab->g = b; + b = t->g; + goto s; +} +template class w {}; +template class x; +template class z; +class ad { +public: + template + static void ah(const z &, const z &, x *&); +}; +template +void ad::ah(const z &ai, const z &aj, x *&) { + u c(0, 0), d(0, 0), g(aj, ai); + v e(c, d); + e.aa(g, 0); +} +template class ak; +template +void ao(ak ap, ak aq) { + x *f; + ad::ah(*ap.ar, *aq.ar, f); +} +template +void au(w ap, w aq) { + ao(static_cast(ap), static_cast(aq)); +} +template class z {}; +template class ak : public w> { +public: + z *ar; +}; +template class av; +template +void ay(av, av) { + aw h, i; + au(h, i); +} +template class av {}; +class az { +public: + typedef av> ba; +}; +int main() { + az::ba j, k; + ay(j, k); +} diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr97633.c b/gcc/testsuite/gcc.dg/vect/bb-slp-pr97633.c new file mode 100644 index 00000000000..ab0ae1de9c9 --- /dev/null +++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr97633.c @@ -0,0 +1,27 @@ +/* { dg-do compile } */ + +extern short i (void); + +struct { + short a; + short b; +} c; + +int d, e; +static int f = 1; + +void g () { + if (e) { + if (f) + goto L; + while (d) { + i (); + short j = d, k = i (), l = k; + L: + if (!(d && e) || l) + goto L; + c.a = j; + c.b = k; + } + } +} diff --git a/gcc/tree-vect-slp.c b/gcc/tree-vect-slp.c index 5d69a98c2a9..714e50697bd 100644 --- a/gcc/tree-vect-slp.c +++ b/gcc/tree-vect-slp.c @@ -5554,97 +5554,114 @@ vect_schedule_scc (vec_info *vinfo, slp_tree node, slp_instance instance, gcc_assert (!existed_p); info->dfs = maxdfs; info->lowlink = maxdfs; - info->on_stack = true; maxdfs++; + + /* Leaf. */ + if (SLP_TREE_DEF_TYPE (node) != vect_internal_def) + { + info->on_stack = false; + vect_schedule_slp_node (vinfo, node, instance); + return; + } + + info->on_stack = true; stack.safe_push (node); + unsigned i; slp_tree child; - - /* ??? We're keeping SLP_TREE_CHILDREN of externalized nodes. */ - if (SLP_TREE_DEF_TYPE (node) == vect_internal_def) - FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child) - { - if (!child) - continue; - slp_scc_info *child_info = scc_info.get (child); - if (!child_info) - { - vect_schedule_scc (vinfo, child, instance, scc_info, maxdfs, stack); - /* Recursion might have re-allocated the node. */ - info = scc_info.get (node); - child_info = scc_info.get (child); - info->lowlink = MIN (info->lowlink, child_info->lowlink); - } - else if (child_info->on_stack) - info->lowlink = MIN (info->lowlink, child_info->dfs); - } + /* DFS recurse. */ + FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child) + { + if (!child) + continue; + slp_scc_info *child_info = scc_info.get (child); + if (!child_info) + { + vect_schedule_scc (vinfo, child, instance, scc_info, maxdfs, stack); + /* Recursion might have re-allocated the node. */ + info = scc_info.get (node); + child_info = scc_info.get (child); + info->lowlink = MIN (info->lowlink, child_info->lowlink); + } + else if (child_info->on_stack) + info->lowlink = MIN (info->lowlink, child_info->dfs); + } if (info->lowlink != info->dfs) return; + auto_vec phis_to_fixup; + /* Singleton. */ if (stack.last () == node) { stack.pop (); info->on_stack = false; vect_schedule_slp_node (vinfo, node, instance); - return; + if (SLP_TREE_CODE (node) != VEC_PERM_EXPR + && is_a (SLP_TREE_REPRESENTATIVE (node)->stmt)) + phis_to_fixup.quick_push (node); } - /* SCC. */ - int last_idx = stack.length () - 1; - while (stack[last_idx] != node) - last_idx--; - /* We can break the cycle at PHIs who have at least one child - code generated. Then we could re-start the DFS walk until - all nodes in the SCC are covered (we might have new entries - for only back-reachable nodes). But it's simpler to just - iterate and schedule those that are ready. */ - auto_vec phis_to_fixup; - unsigned todo = stack.length () - last_idx; - do + else { - for (int idx = stack.length () - 1; idx >= last_idx; --idx) + /* SCC. */ + int last_idx = stack.length () - 1; + while (stack[last_idx] != node) + last_idx--; + /* We can break the cycle at PHIs who have at least one child + code generated. Then we could re-start the DFS walk until + all nodes in the SCC are covered (we might have new entries + for only back-reachable nodes). But it's simpler to just + iterate and schedule those that are ready. */ + unsigned todo = stack.length () - last_idx; + do { - slp_tree entry = stack[idx]; - if (!entry) - continue; - bool phi = (SLP_TREE_CODE (entry) != VEC_PERM_EXPR - && is_a (SLP_TREE_REPRESENTATIVE (entry)->stmt)); - bool ready = !phi; - FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (entry), i, child) - if (!child) - { - gcc_assert (phi); - ready = true; - break; - } - else if (scc_info.get (child)->on_stack) - { - if (!phi) - { - ready = false; - break; - } - } - else - { - if (phi) - { - ready = true; - break; - } - } - if (ready) + for (int idx = stack.length () - 1; idx >= last_idx; --idx) { - vect_schedule_slp_node (vinfo, entry, instance); - scc_info.get (entry)->on_stack = false; - stack[idx] = NULL; - todo--; - if (phi) - phis_to_fixup.safe_push (entry); + slp_tree entry = stack[idx]; + if (!entry) + continue; + bool phi = (SLP_TREE_CODE (entry) != VEC_PERM_EXPR + && is_a (SLP_TREE_REPRESENTATIVE (entry)->stmt)); + bool ready = !phi; + FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (entry), i, child) + if (!child) + { + gcc_assert (phi); + ready = true; + break; + } + else if (scc_info.get (child)->on_stack) + { + if (!phi) + { + ready = false; + break; + } + } + else + { + if (phi) + { + ready = true; + break; + } + } + if (ready) + { + vect_schedule_slp_node (vinfo, entry, instance); + scc_info.get (entry)->on_stack = false; + stack[idx] = NULL; + todo--; + if (phi) + phis_to_fixup.safe_push (entry); + } } } + while (todo != 0); + + /* Pop the SCC. */ + stack.truncate (last_idx); } - while (todo != 0); /* Now fixup the backedge def of the vectorized PHIs in this SCC. */ slp_tree phi_node; @@ -5666,9 +5683,6 @@ vect_schedule_scc (vec_info *vinfo, slp_tree node, slp_instance instance, e, gimple_phi_arg_location (phi, dest_idx)); } } - - /* Pop the SCC. */ - stack.truncate (last_idx); } /* Generate vector code for SLP_INSTANCES in the loop/basic block. */ -- 2.30.2