diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
index 429734f954a..d6b79600cea 100644
--- a/gcc/gimple-range-fold.cc
+++ b/gcc/gimple-range-fold.cc
@@ -743,6 +743,7 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src)
   // Track if all executable arguments are the same.
   tree single_arg = NULL_TREE;
   bool seen_arg = false;
+  bool seen_undefined = false;
 
   // Start with an empty range, unioning in each argument's range.
   r.set_undefined ();
@@ -781,6 +782,8 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src)
 	  else if (single_arg != arg)
 	    single_arg = NULL_TREE;
 	}
+      else
+	seen_undefined = true;
 
       // Once the value reaches varying, stop looking.
       if (r.varying_p () && single_arg == NULL_TREE)
@@ -798,23 +801,13 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src)
 	// Symbolic arguments can be equivalences.
 	if (gimple_range_ssa_p (single_arg))
 	  {
-	    // Only allow the equivalence if the PHI definition does not
-	    // dominate any incoming edge for SINGLE_ARG.
-	    // See PR 108139 and 109462.
-	    basic_block bb = gimple_bb (phi);
-	    if (!dom_info_available_p (CDI_DOMINATORS))
-	      single_arg = NULL;
-	    else
-	      for (x = 0; x < gimple_phi_num_args (phi); x++)
-		if (gimple_phi_arg_def (phi, x) == single_arg
-		    && dominated_by_p (CDI_DOMINATORS,
-					gimple_phi_arg_edge (phi, x)->src,
-					bb))
-		  {
-		    single_arg = NULL;
-		    break;
-		  }
-	    if (single_arg)
+	    // Only allow the equivalence if there isn't any UNDEFINED
+	    // argument we ignored.  Such equivalences are one way
+	    // PHIDEF == name, but name == PHIDEF might not hold.
+	    // See PR 108139, 109462 and 109564.
+	    // ???  This misses cases with not executable edges such
+	    // as gcc.dg/tree-ssa/vrp06.c
+	    if (!seen_undefined)
 	      src.register_relation (phi, VREL_EQ, phi_def, single_arg);
 	  }
 	else if (src.get_operand (arg_range, single_arg)
diff --git a/gcc/testsuite/gcc.dg/torture/pr109564-1.c b/gcc/testsuite/gcc.dg/torture/pr109564-1.c
new file mode 100644
index 00000000000..e7c855f1edf
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr109564-1.c
@@ -0,0 +1,74 @@
+/* { dg-do run } */
+
+struct libkeccak_spec {
+    long int bitrate;
+};
+
+struct libkeccak_generalised_spec {
+    long int bitrate;
+    long int state_size;
+    long int word_size;
+};
+
+int __attribute__((noipa))
+libkeccak_degeneralise_spec(struct libkeccak_generalised_spec *restrict spec,
+			    struct libkeccak_spec *restrict output_spec)
+{
+  long int state_size, word_size, bitrate, output;
+  const int have_state_size = spec->state_size != (-65536L);
+  const int have_word_size = spec->word_size != (-65536L);
+  const int have_bitrate = spec->bitrate != (-65536L);
+
+  if (have_state_size)
+    {
+      state_size = spec->state_size;
+      if (state_size <= 0)
+	return 1;
+      if (state_size > 1600)
+	return 2;
+    }
+
+  if (have_word_size)
+    {
+      word_size = spec->word_size;
+      if (word_size <= 0)
+	return 4;
+      if (word_size > 64)
+	return 5;
+      if (have_state_size && state_size != word_size * 25)
+	return 6;
+      else if (!have_state_size) {
+	  spec->state_size = 1;
+	  state_size = word_size * 25;
+      }
+    }
+
+  if (have_bitrate)
+    bitrate = spec->bitrate;
+
+  if (!have_bitrate)
+    {
+      state_size = (have_state_size ? state_size : (1600L));
+      output = ((state_size << 5) / 100L + 7L) & ~0x07L;
+      bitrate = output << 1;
+    }
+
+  output_spec->bitrate = bitrate;
+
+  return 0;
+}
+
+int main ()
+{
+  struct libkeccak_generalised_spec gspec;
+  struct libkeccak_spec spec;
+  spec.bitrate = -1;
+  gspec.bitrate = -65536;
+  gspec.state_size = -65536;
+  gspec.word_size = -65536;
+  if (libkeccak_degeneralise_spec(&gspec, &spec))
+    __builtin_abort ();
+  if (spec.bitrate != 1024)
+    __builtin_abort ();
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/torture/pr109564-2.c b/gcc/testsuite/gcc.dg/torture/pr109564-2.c
new file mode 100644
index 00000000000..eeab437c0b3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr109564-2.c
@@ -0,0 +1,33 @@
+/* { dg-do run } */
+
+struct libkeccak_generalised_spec {
+  int state_size;
+  int word_size;
+} main_gspec;
+
+long gvar;
+
+int libkeccak_degeneralise_spec(struct libkeccak_generalised_spec *spec)
+{
+  int state_size;
+  int have_state_size = spec->state_size != -1;
+  int have_word_size = spec->word_size;
+
+  if (have_state_size)
+    state_size = spec->state_size;
+  if (have_word_size)
+    gvar = 12345;
+  if (have_state_size && state_size != spec->word_size)
+    return 1;
+  if (spec)
+    gvar++;
+  return 0;
+}
+
+int main()
+{
+  main_gspec.state_size = -1;
+  if (libkeccak_degeneralise_spec(&main_gspec))
+    __builtin_abort();
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp-ignore.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp-ignore.c
index 9bfaed6a50a..ee93e5ad9f6 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/evrp-ignore.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/evrp-ignore.c
@@ -25,4 +25,4 @@ void foo (int x, int y, int z)
     kill();
 
 }
-/* { dg-final { scan-tree-dump-not "kill" "evrp" } } */
+/* { dg-final { scan-tree-dump-not "kill" "evrp" { xfail *-*-* } } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c
index 898477e42fb..8f5f86021c8 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c
@@ -30,4 +30,4 @@ foo (int i, int j, int a)
 
 /* { dg-final { scan-tree-dump-times "Folding predicate \[i|j\]_\[0-9\]+.*0 to 0" 1 "vrp1" } } */
 /* { dg-final { scan-tree-dump-times "Folding predicate \[i|j\]_\[0-9\]+.*0 to 1" 1 "vrp1" } } */
-/* { dg-final { scan-tree-dump-times "Folding predicate i_\[0-9]+.*j_\[0-9\]+.* to 0" 1 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "Folding predicate i_\[0-9]+.*j_\[0-9\]+.* to 0" 1 "vrp1" { xfail *-*-* } } } */
