Hi folks.
This is a follow-up on Jeff and Richi's interaction on the
aforementioned PR here:
https://gcc.gnu.org/ml/gcc-patches/2016-08/msg01397.html
I decided to explore the idea of analyzing may-undefness on-demand,
which actually looks rather cheap.
BTW, I don't understand why we don't have auto_bitmap's, as we already
have auto_sbitmap's. I've implemented the former based on
auto_sbitmap's code we already have.
The attached patch fixes the bug without introducing any regressions.
I also tested the patch by compiling 242 .ii files with -O3. These were
gathered from a stage1 build with -save-temps. There is a slight time
degradation of 4 seconds within 27 minutes of user time:
tainted: 26:52
orig: 26:48
This was the average aggregate time of two runs compiling all 242 .ii
files. IMO, this looks reasonable. It is after all, -O3. Is it
acceptable?
Aldy
commit 2310bcd0e2552a40ca1de354faf005ed3e9daf4e
Author: Aldy Hernandez <al...@redhat.com>
Date: Fri Dec 16 03:44:52 2016 -0500
PR tree-optimization/71691
* bitmap.h (class auto_bitmap): New.
* tree-ssa-loop-unswitch.c (ssa_maybe_undefined_value_p): New.
(tree_may_unswitch_on): Call ssa_maybe_undefined_value_p.
diff --git a/gcc/bitmap.h b/gcc/bitmap.h
index 1b2c8e0..bc32a21 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/gcc.c-torture/execute/pr71691.c
b/gcc/testsuite/gcc.c-torture/execute/pr71691.c
new file mode 100644
index 0000000..1ffd1a2
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr71691.c
@@ -0,0 +1,47 @@
+/* { dg-options "-fno-tree-vrp" } */
+
+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 40905af..bc34395 100644
--- a/gcc/tree-ssa-loop-unswitch.c
+++ b/gcc/tree-ssa-loop-unswitch.c
@@ -109,6 +109,71 @@ tree_ssa_unswitch_loops (void)
return 0;
}
+/* Return TRUE if an SSA_NAME may be undefined. */
+
+static bool
+ssa_maybe_undefined_value_p (tree name)
+{
+ /* If it's obviously undefined, avoid further computations. */
+ if (ssa_undefined_value_p (name, true))
+ return true;
+
+ auto_bitmap visited_ssa;
+ auto_vec<tree> worklist;
+ worklist.safe_push (name);
+ while (!worklist.is_empty ())
+ {
+ name = worklist.pop ();
+ gcc_assert (TREE_CODE (name) == SSA_NAME);
+
+ if (ssa_undefined_value_p (name, true))
+ return true;
+
+ bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (name));
+
+ /* Check that all the PHI args are fully defined. */
+ gimple *def = SSA_NAME_DEF_STMT (name);
+ if (gphi *phi = dyn_cast <gphi *> (def))
+ {
+ if (virtual_operand_p (PHI_RESULT (phi)))
+ continue;
+ for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
+ {
+ name = gimple_phi_arg_def (phi, i);
+ if (TREE_CODE (name) == SSA_NAME)
+ {
+ /* If an SSA has already been seen, this may be a loop.
+ Fail conservatively. */
+ if (bitmap_bit_p (visited_ssa, SSA_NAME_VERSION (name)))
+ return false;
+ bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (name));
+ worklist.safe_push (name);
+ }
+ }
+ continue;
+ }
+
+ /* Check that any SSA names used to define NAME is also fully
+ defined. */
+ use_operand_p use_p;
+ ssa_op_iter iter;
+ FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE)
+ {
+ name = USE_FROM_PTR (use_p);
+ if (TREE_CODE (name) == SSA_NAME)
+ {
+ /* If an SSA has already been seen, this may be a loop.
+ Fail conservatively. */
+ if (bitmap_bit_p (visited_ssa, SSA_NAME_VERSION (name)))
+ return false;
+ bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (name));
+ worklist.safe_push (name);
+ }
+ }
+ }
+ 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). */
@@ -138,7 +203,7 @@ tree_may_unswitch_on (basic_block bb, struct loop *loop)
{
/* Unswitching on undefined values would introduce undefined
behavior that the original program might never exercise. */
- if (ssa_undefined_value_p (use, true))
+ if (ssa_maybe_undefined_value_p (use))
return NULL_TREE;
def = SSA_NAME_DEF_STMT (use);
def_bb = gimple_bb (def);
