From 8b670f93ab11361ae88a22fea4f96c770afb6311 Mon Sep 17 00:00:00 2001 From: Aldy Hernandez Date: Tue, 31 Jan 2017 10:30:47 +0000 Subject: [PATCH] re PR tree-optimization/71691 (wrong code at -O3 in both 32-bit and 64-bit modes on x86_64-linux-gnu (Floating point exception)) PR tree-optimization/71691 * bitmap.h (class auto_bitmap): New. * tree-ssa-loop-unswitch.c (tree_may_unswitch_on): Call is_maybe_undefined instead of ssa_undefined_value_p. From-SVN: r245057 --- gcc/ChangeLog | 7 +++ gcc/bitmap.h | 21 +++++++ gcc/testsuite/ChangeLog | 5 ++ gcc/testsuite/gcc.dg/loop-unswitch-1.c | 4 +- gcc/testsuite/gcc.dg/loop-unswitch-5.c | 51 ++++++++++++++++ gcc/tree-ssa-loop-unswitch.c | 84 ++++++++++++++++++++++++-- 6 files changed, 167 insertions(+), 5 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/loop-unswitch-5.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index ac133d4b356..1ba1eb67ebd 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,10 @@ +2017-01-31 Aldy Hernandez + + PR tree-optimization/71691 + * bitmap.h (class auto_bitmap): New. + * tree-ssa-loop-unswitch.c (tree_may_unswitch_on): Call + is_maybe_undefined instead of ssa_undefined_value_p. + 2017-01-31 Andreas Krebbel * config/s390/s390-c.c (s390_cpu_cpp_builtins_internal): Rename diff --git a/gcc/bitmap.h b/gcc/bitmap.h index 196738b1a7d..f158b447357 100644 --- a/gcc/bitmap.h +++ b/gcc/bitmap.h @@ -802,4 +802,25 @@ bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no) bmp_iter_and_compl (&(ITER), &(BITNUM)); \ bmp_iter_next (&(ITER), &(BITNUM))) +/* A class that ties the lifetime of a bitmap to its scope. */ +class auto_bitmap +{ + public: + auto_bitmap () { bits = BITMAP_ALLOC (NULL); } + ~auto_bitmap () { BITMAP_FREE (bits); } + // Allow calling bitmap functions on our bitmap. + operator bitmap () { return bits; } + + private: + // Prevent making a copy that references our bitmap. + auto_bitmap (const auto_bitmap &); + auto_bitmap &operator = (const auto_bitmap &); +#if __cplusplus >= 201103L + auto_bitmap (auto_bitmap &&); + auto_bitmap &operator = (auto_bitmap &&); +#endif + + bitmap bits; +}; + #endif /* GCC_BITMAP_H */ diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index ca79200494b..fef5e87b9af 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2017-01-30 Aldy Hernandez + + PR tree-optimization/71691 + * gcc.dg/loop-unswitch-5.c: Test that we actually unswitch a loop. + 2017-01-31 Andreas Krebbel * gcc.target/s390/s390.exp: Rename __S390_ARCH_LEVEL__ to diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-1.c b/gcc/testsuite/gcc.dg/loop-unswitch-1.c index 930364c8175..f6fc41d6bcc 100644 --- a/gcc/testsuite/gcc.dg/loop-unswitch-1.c +++ b/gcc/testsuite/gcc.dg/loop-unswitch-1.c @@ -1,6 +1,6 @@ /* For PR rtl-optimization/27735 */ /* { dg-do compile } */ -/* { dg-options "-O2 -funswitch-loops" } */ +/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details" } */ void set_color(void); void xml_colorize_line(unsigned int *p, int state) @@ -32,3 +32,5 @@ parse_tag: ; } } +/* Test that we actually unswitched something. */ +/* { dg-final { scan-tree-dump ";; Unswitching loop" "unswitch" } } */ diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-5.c b/gcc/testsuite/gcc.dg/loop-unswitch-5.c new file mode 100644 index 00000000000..b41e85379ae --- /dev/null +++ b/gcc/testsuite/gcc.dg/loop-unswitch-5.c @@ -0,0 +1,51 @@ +/* PR middle-end/71691 */ +/* { dg-do run } */ +/* { dg-options "-fno-tree-vrp -O2 -funswitch-loops -fdump-tree-unswitch-details" } */ + +/* Note: The -fno-tree-vrp above is only there to avoid VRP papering + over the problem. */ + +char b; +short f; +unsigned e; +int g = 20; + +void +foo () +{ + int l, h; + for (l = 0; l <= 7; l++) + { + int j = 38; + if (g) + h = 0; + for (; h <= 7; h++) + { + int i, k = b % (j % 4); + g = f; + for (;;) + { + j = 6 || b; + if (e) + { + for (; j; --j) + if (k) + __builtin_printf ("%d", 9); + if (i) + __builtin_printf ("%d", j); + } + if (l) + continue; + break; + } + i = f || b; + } + } +} + +int +main () +{ + foo (); + return 0; +} diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c index 92599fb1379..4ef3a6bf80a 100644 --- a/gcc/tree-ssa-loop-unswitch.c +++ b/gcc/tree-ssa-loop-unswitch.c @@ -109,6 +109,82 @@ tree_ssa_unswitch_loops (void) return 0; } +/* Return TRUE if an SSA_NAME maybe undefined and is therefore + unsuitable for unswitching. STMT is the statement we are + considering for unswitching and LOOP is the loop it appears in. */ + +static bool +is_maybe_undefined (const tree name, gimple *stmt, struct loop *loop) +{ + /* The loop header is the only block we can trivially determine that + will always be executed. If the comparison is in the loop + header, we know it's OK to unswitch on it. */ + if (gimple_bb (stmt) == loop->header) + return false; + + auto_bitmap visited_ssa; + auto_vec worklist; + worklist.safe_push (name); + bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (name)); + while (!worklist.is_empty ()) + { + tree t = worklist.pop (); + + /* If it's obviously undefined, avoid further computations. */ + if (ssa_undefined_value_p (t, true)) + return true; + + /* A PARM_DECL will not have an SSA_NAME_DEF_STMT. Parameters + get their initial value from function entry. */ + if (SSA_NAME_VAR (t) && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL) + continue; + + gimple *def = SSA_NAME_DEF_STMT (t); + + /* Check that all the PHI args are fully defined. */ + if (gphi *phi = dyn_cast (def)) + { + for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i) + { + tree t = gimple_phi_arg_def (phi, i); + /* If an SSA has already been seen, it may be a loop, + but we can continue and ignore this use. Otherwise, + add the SSA_NAME to the queue and visit it later. */ + if (TREE_CODE (t) == SSA_NAME + && bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t))) + worklist.safe_push (t); + } + continue; + } + + /* Uses in stmts always executed when the region header executes + are fine. */ + if (dominated_by_p (CDI_DOMINATORS, loop->header, gimple_bb (def))) + continue; + + /* Handle calls and memory loads conservatively. */ + if (!is_gimple_assign (def) + || (gimple_assign_single_p (def) + && gimple_vuse (def))) + return true; + + /* Check that any SSA names used to define NAME are also fully + defined. */ + use_operand_p use_p; + ssa_op_iter iter; + FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE) + { + tree t = USE_FROM_PTR (use_p); + /* If an SSA has already been seen, it may be a loop, + but we can continue and ignore this use. Otherwise, + add the SSA_NAME to the queue and visit it later. */ + if (bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t))) + worklist.safe_push (t); + } + } + return false; +} + /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its basic blocks (for what it means see comments below). */ @@ -136,15 +212,15 @@ tree_may_unswitch_on (basic_block bb, struct loop *loop) /* Condition must be invariant. */ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) { - /* Unswitching on undefined values would introduce undefined - behavior that the original program might never exercise. */ - if (ssa_undefined_value_p (use, true)) - return NULL_TREE; def = SSA_NAME_DEF_STMT (use); def_bb = gimple_bb (def); if (def_bb && flow_bb_inside_loop_p (loop, def_bb)) return NULL_TREE; + /* Unswitching on undefined values would introduce undefined + behavior that the original program might never exercise. */ + if (is_maybe_undefined (use, stmt, loop)) + return NULL_TREE; } cond = build2 (gimple_cond_code (stmt), boolean_type_node, -- 2.30.2