From df80fc5328ebafa5c33a783a32dd819271a49312 Mon Sep 17 00:00:00 2001 From: Jeff Law Date: Tue, 12 Dec 2017 15:46:46 -0700 Subject: [PATCH] re PR tree-optimization/83298 (wrong code at -O1, -O2 and -O3 on x86_64-linux-gnu) PR tree-optimization/83298 PR tree-optimization/83362 PR tree-optimization/83383 * gimple-ssa-evrp-analyze.h (class evrp_range_analyzer): Make push_value_range a public interface. Add new argument to record_ranges_from_stmt. * gimple-ssa-evrp-analyze.c (evrp_range_analyzer::record_ranges_from_stmt): Add new argument. Update comments. Handle recording temporary equivalences. * tree-ssa-dom.c (dom_opt_opt_walker::before_dom_children): Add new argument to call to evrp_range_analyzer::record_ranges_from_stmt. * gimple-ssa-evrp.c (evrp_dom_walker::before_dom_children): Likewise. * tree-ssa-threadedge.c: Include alloc-pool.h, vr-values.h and gimple-ssa-evrp-analyze.h. (record_temporary_equivalences_from_phis): Add new argument. When the PHI arg is an SSA_NAME, set the result's range to the range of the PHI arg. (record_temporary_equivalences_from_stmts_at_dest): Record ranges from statements too. (thread_through_normal_block): Accept new argument, evrp_range_analyzer. Pass it down to children as needed. (thread_outgoing_edges): Likewise. (thread_across_edge): Likewise. Push/pop range state as needed. * tree-ssa-threadedge.h (thread_outgoing_edges): Update prototype. PR tree-optimization/83298 PR tree-optimization/83362 PR tree-optimization/83383 * gcc.c-torture/execute/pr83298.c: New test. * gcc.c-torture/execute/pr83362.c New test. * gcc.c-torture/execute/pr83383.c New test. From-SVN: r255593 --- gcc/ChangeLog | 27 ++++++++ gcc/gimple-ssa-evrp-analyze.c | 66 ++++++++++++++++--- gcc/gimple-ssa-evrp-analyze.h | 8 ++- gcc/gimple-ssa-evrp.c | 2 +- gcc/testsuite/ChangeLog | 9 +++ gcc/testsuite/gcc.c-torture/execute/pr83298.c | 11 ++++ gcc/testsuite/gcc.c-torture/execute/pr83362.c | 31 +++++++++ gcc/testsuite/gcc.c-torture/execute/pr83383.c | 25 +++++++ gcc/tree-ssa-dom.c | 3 +- gcc/tree-ssa-threadedge.c | 61 +++++++++++++---- gcc/tree-ssa-threadedge.h | 2 + gcc/tree-vrp.c | 2 +- 12 files changed, 223 insertions(+), 24 deletions(-) create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr83298.c create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr83362.c create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr83383.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 3289f18f662..9b4829d670a 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,30 @@ +2017-12-12 Jeff Law + + PR tree-optimization/83298 + PR tree-optimization/83362 + PR tree-optimization/83383 + * gimple-ssa-evrp-analyze.h (class evrp_range_analyzer): Make + push_value_range a public interface. Add new argument to + record_ranges_from_stmt. + * gimple-ssa-evrp-analyze.c + (evrp_range_analyzer::record_ranges_from_stmt): Add new argument. + Update comments. Handle recording temporary equivalences. + * tree-ssa-dom.c (dom_opt_opt_walker::before_dom_children): Add + new argument to call to evrp_range_analyzer::record_ranges_from_stmt. + * gimple-ssa-evrp.c (evrp_dom_walker::before_dom_children): Likewise. + * tree-ssa-threadedge.c: Include alloc-pool.h, vr-values.h and + gimple-ssa-evrp-analyze.h. + (record_temporary_equivalences_from_phis): Add new argument. When + the PHI arg is an SSA_NAME, set the result's range to the range + of the PHI arg. + (record_temporary_equivalences_from_stmts_at_dest): Record ranges + from statements too. + (thread_through_normal_block): Accept new argument, evrp_range_analyzer. + Pass it down to children as needed. + (thread_outgoing_edges): Likewise. + (thread_across_edge): Likewise. Push/pop range state as needed. + * tree-ssa-threadedge.h (thread_outgoing_edges): Update prototype. + 2017-12-12 Julia Koval * config/i386/i386.c (PTA_SKYLAKE_AVX512): Add PTA_CLWB. diff --git a/gcc/gimple-ssa-evrp-analyze.c b/gcc/gimple-ssa-evrp-analyze.c index fb3d3297a78..8e9881b6964 100644 --- a/gcc/gimple-ssa-evrp-analyze.c +++ b/gcc/gimple-ssa-evrp-analyze.c @@ -56,10 +56,20 @@ evrp_range_analyzer::evrp_range_analyzer () : stack (10) vr_values = new class vr_values; } +/* Push an unwinding marker onto the unwinding stack. */ + void -evrp_range_analyzer::enter (basic_block bb) +evrp_range_analyzer::push_marker () { stack.safe_push (std::make_pair (NULL_TREE, (value_range *)NULL)); +} + +/* Analyze ranges as we enter basic block BB. */ + +void +evrp_range_analyzer::enter (basic_block bb) +{ + push_marker (); record_ranges_from_incoming_edge (bb); record_ranges_from_phis (bb); bb->flags |= BB_VISITED; @@ -259,8 +269,13 @@ evrp_range_analyzer::record_ranges_from_phis (basic_block bb) } } +/* Record ranges from STMT into our VR_VALUES class. If TEMPORARY is + true, then this is a temporary equivalence and should be recorded + into the unwind table. Othewise record the equivalence into the + global table. */ + void -evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt) +evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt, bool temporary) { tree output = NULL_TREE; @@ -273,10 +288,36 @@ evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt) vr_values->extract_range_from_stmt (stmt, &taken_edge, &output, &vr); if (output) { - vr_values->update_value_range (output, &vr); - - /* Set the SSA with the value range. */ - set_ssa_range_info (output, &vr); + /* Set the SSA with the value range. There are two cases to + consider. First (the the most common) is we are processing + STMT in a context where its resulting range globally holds + and thus it can be reflected into the global ranges and need + not be unwound as we leave scope. + + The second case occurs if we are processing a statement in + a context where the resulting range must not be reflected + into the global tables and must be unwound as we leave + the current context. This happens in jump threading for + example. */ + if (!temporary) + { + /* Case one. We can just update the underlying range + information as well as the global information. */ + vr_values->update_value_range (output, &vr); + set_ssa_range_info (output, &vr); + } + else + { + /* We're going to need to unwind this range. We can + not use VR as that's a stack object. We have to allocate + a new range and push the old range onto the stack. We + also have to be very careful about sharing the underlying + bitmaps. Ugh. */ + value_range *new_vr = vr_values->allocate_value_range (); + *new_vr = vr; + new_vr->equiv = NULL; + push_value_range (output, new_vr); + } } else vr_values->set_defs_to_varying (stmt); @@ -333,10 +374,10 @@ evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt) } } -/* Restore/pop VRs valid only for BB when we leave BB. */ +/* Unwind recorded ranges to their most recent state. */ void -evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED) +evrp_range_analyzer::pop_to_marker (void) { gcc_checking_assert (!stack.is_empty ()); while (stack.last ().first != NULL_TREE) @@ -344,6 +385,15 @@ evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED) stack.pop (); } +/* Restore/pop VRs valid only for BB when we leave BB. */ + +void +evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED) +{ + pop_to_marker (); +} + + /* Push the Value Range of VAR to the stack and update it with new VR. */ void diff --git a/gcc/gimple-ssa-evrp-analyze.h b/gcc/gimple-ssa-evrp-analyze.h index 4783e6f772e..3968cfd805a 100644 --- a/gcc/gimple-ssa-evrp-analyze.h +++ b/gcc/gimple-ssa-evrp-analyze.h @@ -31,13 +31,18 @@ class evrp_range_analyzer } void enter (basic_block); + void push_marker (void); + void pop_to_marker (void); void leave (basic_block); - void record_ranges_from_stmt (gimple *); + void record_ranges_from_stmt (gimple *, bool); /* Main interface to retrieve range information. */ value_range *get_value_range (const_tree op) { return vr_values->get_value_range (op); } + /* Record a new unwindable range. */ + void push_value_range (tree var, value_range *vr); + /* Dump all the current value ranges. This is primarily a debugging interface. */ void dump_all_value_ranges (FILE *fp) @@ -57,7 +62,6 @@ class evrp_range_analyzer DISABLE_COPY_AND_ASSIGN (evrp_range_analyzer); class vr_values *vr_values; - void push_value_range (tree var, value_range *vr); value_range *pop_value_range (tree var); value_range *try_find_new_range (tree, tree op, tree_code code, tree limit); void record_ranges_from_incoming_edge (basic_block); diff --git a/gcc/gimple-ssa-evrp.c b/gcc/gimple-ssa-evrp.c index 609ce38f218..112a43f4e8e 100644 --- a/gcc/gimple-ssa-evrp.c +++ b/gcc/gimple-ssa-evrp.c @@ -134,7 +134,7 @@ evrp_dom_walker::before_dom_children (basic_block bb) print_gimple_stmt (dump_file, stmt, 0); } - evrp_range_analyzer.record_ranges_from_stmt (stmt); + evrp_range_analyzer.record_ranges_from_stmt (stmt, false); if (gcond *cond = dyn_cast (stmt)) { diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index f259bbffadb..2a863db30fa 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,12 @@ +2017-12-12 Jeff Law + + PR tree-optimization/83298 + PR tree-optimization/83362 + PR tree-optimization/83383 + * gcc.c-torture/execute/pr83298.c: New test. + * gcc.c-torture/execute/pr83362.c New test. + * gcc.c-torture/execute/pr83383.c New test. + 2017-12-12 Rainer Orth * lib/gcc-dg.exp (process-message): Avoid additional whitespace in diff --git a/gcc/testsuite/gcc.c-torture/execute/pr83298.c b/gcc/testsuite/gcc.c-torture/execute/pr83298.c new file mode 100644 index 00000000000..0e51ababf5c --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/pr83298.c @@ -0,0 +1,11 @@ + +int a, b, c = 1; + +int main () +{ + for (; b < 1; b++) + ; + if (!(c * (a < 1))) + __builtin_abort (); + return 0; +} diff --git a/gcc/testsuite/gcc.c-torture/execute/pr83362.c b/gcc/testsuite/gcc.c-torture/execute/pr83362.c new file mode 100644 index 00000000000..54350819c56 --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/pr83362.c @@ -0,0 +1,31 @@ +typedef unsigned char u8; +typedef unsigned int u32; + +u32 a, b, d, e; +u8 c; + +static u32 __attribute__ ((noinline, noclone)) +foo (u32 p) +{ + do + { + e /= 0xfff; + if (p > c) + d = 0; + e -= 3; + e *= b <= a; + } + while (e >= 88030); + return e; +} + +int +main (void) +{ + u32 x = foo (1164); + if (x != 0xfd) + __builtin_abort (); + return 0; +} + + diff --git a/gcc/testsuite/gcc.c-torture/execute/pr83383.c b/gcc/testsuite/gcc.c-torture/execute/pr83383.c new file mode 100644 index 00000000000..e803bea565b --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/pr83383.c @@ -0,0 +1,25 @@ +/* PR tree-optimization/83383 */ + +unsigned long long int a = 16ULL; +unsigned char b = 195; +unsigned long long int c = ~0ULL; +unsigned char d = 1; +unsigned long long int e[2] = { 3625445792498952486ULL, 0 }; +unsigned long long int f[2] = { 0, 8985037393681294663ULL }; +unsigned long long int g = 5052410635626804928ULL; + +void +foo () +{ + a = ((signed char) a) < b; + c = (d ? e[0] : 0) - (f[1] * a ? 1 : g); +} + +int +main() +{ + foo (); + if (a != 1 || c != 3625445792498952485ULL) + __builtin_abort (); + return 0; +} diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c index 59a7d87898e..93c992a9215 100644 --- a/gcc/tree-ssa-dom.c +++ b/gcc/tree-ssa-dom.c @@ -1433,7 +1433,7 @@ dom_opt_dom_walker::before_dom_children (basic_block bb) edge taken_edge = NULL; for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { - evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi)); + evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false); taken_edge = this->optimize_stmt (bb, gsi); } @@ -1456,6 +1456,7 @@ dom_opt_dom_walker::after_dom_children (basic_block bb) x_vr_values = evrp_range_analyzer.get_vr_values (); thread_outgoing_edges (bb, m_dummy_cond, m_const_and_copies, m_avail_exprs_stack, + &evrp_range_analyzer, simplify_stmt_for_jump_threading); x_vr_values = NULL; diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c index 91793bfa59d..b7781dc7d60 100644 --- a/gcc/tree-ssa-threadedge.c +++ b/gcc/tree-ssa-threadedge.c @@ -37,6 +37,9 @@ along with GCC; see the file COPYING3. If not see #include "tree-ssa-dom.h" #include "gimple-fold.h" #include "cfganal.h" +#include "alloc-pool.h" +#include "vr-values.h" +#include "gimple-ssa-evrp-analyze.h" /* To avoid code explosion due to jump threading, we limit the number of statements we are going to copy. This variable @@ -114,17 +117,16 @@ potentially_threadable_block (basic_block bb) } /* Record temporary equivalences created by PHIs at the target of the - edge E. Record unwind information for the equivalences onto STACK. + edge E. Record unwind information for the equivalences into + CONST_AND_COPIES and EVRP_RANGE_DATA. If a PHI which prevents threading is encountered, then return FALSE - indicating we should not thread this edge, else return TRUE. - - If SRC_MAP/DST_MAP exist, then mark the source and destination SSA_NAMEs - of any equivalences recorded. We use this to make invalidation after - traversing back edges less painful. */ + indicating we should not thread this edge, else return TRUE. */ static bool -record_temporary_equivalences_from_phis (edge e, const_and_copies *const_and_copies) +record_temporary_equivalences_from_phis (edge e, + const_and_copies *const_and_copies, + evrp_range_analyzer *evrp_range_analyzer) { gphi_iterator gsi; @@ -152,6 +154,14 @@ record_temporary_equivalences_from_phis (edge e, const_and_copies *const_and_cop stmt_count++; const_and_copies->record_const_or_copy (dst, src); + + /* Also update the value range associated with DST, using + the range from SRC. */ + if (evrp_range_analyzer && TREE_CODE (src) == SSA_NAME) + { + value_range *vr = evrp_range_analyzer->get_value_range (src); + evrp_range_analyzer->push_value_range (dst, vr); + } } return true; } @@ -191,6 +201,7 @@ static gimple * record_temporary_equivalences_from_stmts_at_dest (edge e, const_and_copies *const_and_copies, avail_exprs_stack *avail_exprs_stack, + evrp_range_analyzer *evrp_range_analyzer, pfn_simplify simplify) { gimple *stmt = NULL; @@ -235,6 +246,11 @@ record_temporary_equivalences_from_stmts_at_dest (edge e, if (stmt_count > max_stmt_count) return NULL; + /* These are temporary ranges, do nto reflect them back into + the global range data. */ + if (evrp_range_analyzer) + evrp_range_analyzer->record_ranges_from_stmt (stmt, true); + /* If this is not a statement that sets an SSA_NAME to a new value, then do not try to simplify this statement as it will not simplify in any way that is helpful for jump threading. */ @@ -981,6 +997,7 @@ thread_through_normal_block (edge e, gcond *dummy_cond, const_and_copies *const_and_copies, avail_exprs_stack *avail_exprs_stack, + evrp_range_analyzer *evrp_range_analyzer, pfn_simplify simplify, vec *path, bitmap visited) @@ -992,7 +1009,8 @@ thread_through_normal_block (edge e, Note that if we found a PHI that made the block non-threadable, then we need to bubble that up to our caller in the same manner we do when we prematurely stop processing statements below. */ - if (!record_temporary_equivalences_from_phis (e, const_and_copies)) + if (!record_temporary_equivalences_from_phis (e, const_and_copies, + evrp_range_analyzer)) return -1; /* Now walk each statement recording any context sensitive @@ -1000,6 +1018,7 @@ thread_through_normal_block (edge e, gimple *stmt = record_temporary_equivalences_from_stmts_at_dest (e, const_and_copies, avail_exprs_stack, + evrp_range_analyzer, simplify); /* There's two reasons STMT might be null, and distinguishing @@ -1114,12 +1133,15 @@ thread_across_edge (gcond *dummy_cond, edge e, class const_and_copies *const_and_copies, class avail_exprs_stack *avail_exprs_stack, + class evrp_range_analyzer *evrp_range_analyzer, pfn_simplify simplify) { bitmap visited = BITMAP_ALLOC (NULL); const_and_copies->push_marker (); avail_exprs_stack->push_marker (); + if (evrp_range_analyzer) + evrp_range_analyzer->push_marker (); stmt_count = 0; @@ -1133,6 +1155,7 @@ thread_across_edge (gcond *dummy_cond, threaded = thread_through_normal_block (e, dummy_cond, const_and_copies, avail_exprs_stack, + evrp_range_analyzer, simplify, path, visited); else @@ -1144,6 +1167,8 @@ thread_across_edge (gcond *dummy_cond, e->dest); const_and_copies->pop_to_marker (); avail_exprs_stack->pop_to_marker (); + if (evrp_range_analyzer) + evrp_range_analyzer->pop_to_marker (); BITMAP_FREE (visited); register_jump_thread (path); return; @@ -1169,6 +1194,8 @@ thread_across_edge (gcond *dummy_cond, BITMAP_FREE (visited); const_and_copies->pop_to_marker (); avail_exprs_stack->pop_to_marker (); + if (evrp_range_analyzer) + evrp_range_analyzer->pop_to_marker (); return; } } @@ -1196,6 +1223,8 @@ thread_across_edge (gcond *dummy_cond, { const_and_copies->pop_to_marker (); avail_exprs_stack->pop_to_marker (); + if (evrp_range_analyzer) + evrp_range_analyzer->pop_to_marker (); BITMAP_FREE (visited); return; } @@ -1211,6 +1240,8 @@ thread_across_edge (gcond *dummy_cond, for each of E->dest's successors. */ const_and_copies->push_marker (); avail_exprs_stack->push_marker (); + if (evrp_range_analyzer) + evrp_range_analyzer->push_marker (); /* Avoid threading to any block we have already visited. */ bitmap_clear (visited); @@ -1238,6 +1269,7 @@ thread_across_edge (gcond *dummy_cond, found = thread_through_normal_block (path->last ()->e, dummy_cond, const_and_copies, avail_exprs_stack, + evrp_range_analyzer, simplify, path, visited) > 0; @@ -1253,12 +1285,16 @@ thread_across_edge (gcond *dummy_cond, delete_jump_thread_path (path); /* And unwind the equivalence table. */ + if (evrp_range_analyzer) + evrp_range_analyzer->pop_to_marker (); avail_exprs_stack->pop_to_marker (); const_and_copies->pop_to_marker (); } BITMAP_FREE (visited); } + if (evrp_range_analyzer) + evrp_range_analyzer->pop_to_marker (); const_and_copies->pop_to_marker (); avail_exprs_stack->pop_to_marker (); } @@ -1280,6 +1316,7 @@ void thread_outgoing_edges (basic_block bb, gcond *dummy_cond, class const_and_copies *const_and_copies, class avail_exprs_stack *avail_exprs_stack, + class evrp_range_analyzer *evrp_range_analyzer, tree (*simplify) (gimple *, gimple *, class avail_exprs_stack *, basic_block)) @@ -1297,7 +1334,7 @@ thread_outgoing_edges (basic_block bb, gcond *dummy_cond, { thread_across_edge (dummy_cond, single_succ_edge (bb), const_and_copies, avail_exprs_stack, - simplify); + evrp_range_analyzer, simplify); } else if ((last = last_stmt (bb)) && gimple_code (last) == GIMPLE_COND @@ -1313,11 +1350,13 @@ thread_outgoing_edges (basic_block bb, gcond *dummy_cond, more than one predecessor and more than one successor. */ if (potentially_threadable_block (true_edge->dest)) thread_across_edge (dummy_cond, true_edge, - const_and_copies, avail_exprs_stack, simplify); + const_and_copies, avail_exprs_stack, + evrp_range_analyzer, simplify); /* Similarly for the ELSE arm. */ if (potentially_threadable_block (false_edge->dest)) thread_across_edge (dummy_cond, false_edge, - const_and_copies, avail_exprs_stack, simplify); + const_and_copies, avail_exprs_stack, + evrp_range_analyzer, simplify); } } diff --git a/gcc/tree-ssa-threadedge.h b/gcc/tree-ssa-threadedge.h index 49dfa9c94d4..0f2e39f72e3 100644 --- a/gcc/tree-ssa-threadedge.h +++ b/gcc/tree-ssa-threadedge.h @@ -30,9 +30,11 @@ extern void threadedge_initialize_values (void); extern void threadedge_finalize_values (void); extern bool potentially_threadable_block (basic_block); extern void propagate_threaded_block_debug_into (basic_block, basic_block); +class evrp_range_analyzer; extern void thread_outgoing_edges (basic_block, gcond *, const_and_copies *, avail_exprs_stack *, + evrp_range_analyzer *, tree (*) (gimple *, gimple *, avail_exprs_stack *, basic_block)); diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index a86b38208ab..7df6f244657 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -6677,7 +6677,7 @@ vrp_dom_walker::after_dom_children (basic_block bb) x_vr_values = vr_values; thread_outgoing_edges (bb, m_dummy_cond, m_const_and_copies, - m_avail_exprs_stack, + m_avail_exprs_stack, NULL, simplify_stmt_for_jump_threading); x_vr_values = NULL; -- 2.30.2