gimple-ssa-strength-reduction.c (cand_kind): Add CAND_PHI.

gcc:

2013-05-03  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

	* gimple-ssa-strength-reduction.c (cand_kind): Add CAND_PHI.
	(slsr_cand_d): Redefine def_phi.
	(stride_status, phi_adjust_status, count_phis_status): New enums.
	(find_phi_def): New.
	(find_basis_for_base_expr): New.
	(find_basis_for_candidate): Handle hidden bases.
	(alloc_cand_and_find_basis): Handle phi candidates.
	(slsr_process_phi): New.
	(create_mul_ssa_cand): Exclude phi base candidates; use integer_onep.
	(create_mul_imm_cand): Likewise.
	(create_add_ssa_cand): Exclude phi base candidates.
	(create_add_imm_cand): Likewise.
	(slsr_process_cast): Likewise.
	(slsr_process_copy): Likewise.
	(find_candidates_in_block): Handle phi candidates.
	(dump_candidate): Likewise.
	(unconditional_cands): Delete.
	(unconditional_cands_with_known_stride_p): Delete.
	(phi_dependent_cand_p): New.
	(cand_increment): Handle phi-dependent candidates.
	(replace_dependent): Delete.
	(replace_mult_candidate): New.
	(replace_unconditional_candidate): New.
	(incr_vec_index): Move to avoid forward reference.
	(create_add_on_incoming_edge): New.
	(create_phi_basis): New.
	(replace_dependents): Delete.
	(replace_conditional_candidate): New.
	(phi_add_costs): New.
	(replace_uncond_cands_and_profitable_phis): New.
	(record_increment): Handle phi adjustments.
	(record_phi_increments): New.
	(record_increments): Handle phi adjustments.
	(phi_incr_cost): New.
	(lowest_cost_path): Handle phis.
	(total_savings): Likewise.
	(analyze_increments): Likewise.
	(ncd_with_phi): New.
	(ncd_of_cand_and_phis): New.
	(nearest_common_dominator_for_cands): Handle phi increments.
	(all_phi_incrs_profitable): New.
	(replace_profitable_candidates): Handle phi-dependent candidates.
	(analyze_candidates_and_replace): Likewise.

gcc/testsuite:

2013-05-03  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

	* gcc.dg/tree-ssa/slsr-32.c: New.
	* gcc.dg/tree-ssa/slsr-33.c: New.
	* gcc.dg/tree-ssa/slsr-34.c: New.
	* gcc.dg/tree-ssa/slsr-35.c: New.
	* gcc.dg/tree-ssa/slsr-36.c: New.
	* gcc.dg/tree-ssa/slsr-37.c: New.
	* gcc.dg/tree-ssa/slsr-38.c: New.

From-SVN: r198586

7 files changed, 228 insertions, 0 deletions

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/slsr-32.c b/gcc/testsuite/gcc.dg/tree-ssa/slsr-32.c
new file mode 100644
index 0000000..73e6797
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/slsr-32.c
@@ -0,0 +1,32 @@
+/* Verify straight-line strength reduction for a candidate with a basis
+   hidden by a phi dependence and having an unknown stride.  */
+
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+int
+f (int s, int c, int i)
+{
+  int a1, a2, a3, x1, x2, x3, x;
+
+  a1 = i * s;
+  x1 = c + a1;
+
+  i = i + 2;
+  a2 = i * s;
+  x2 = c + a2;
+
+  if (x2 > 6)
+    i = i + 2;
+
+  i = i + 2;
+  a3 = i * s;
+  x3 = c + a3;
+
+  x = x1 + x2 + x3;
+  return x;
+}
+
+/* { dg-final { scan-tree-dump-times " \\* s" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " \\* 2" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/slsr-33.c b/gcc/testsuite/gcc.dg/tree-ssa/slsr-33.c
new file mode 100644
index 0000000..5cd4276
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/slsr-33.c
@@ -0,0 +1,31 @@
+/* Verify straight-line strength reduction for a candidate with a basis
+   hidden by a phi dependence and having a known stride.  */
+
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+int
+f (int c, int i)
+{
+  int a1, a2, a3, x1, x2, x3, x;
+
+  a1 = i * 16;
+  x1 = c + a1;
+
+  i = i + 2;
+  a2 = i * 16;
+  x2 = c + a2;
+
+  if (x2 > 6)
+    i = i + 2;
+
+  i = i + 2;
+  a3 = i * 16;
+  x3 = c + a3;
+
+  x = x1 + x2 + x3;
+  return x;
+}
+
+/* { dg-final { scan-tree-dump-times " \\* " 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/slsr-34.c b/gcc/testsuite/gcc.dg/tree-ssa/slsr-34.c
new file mode 100644
index 0000000..3593f86
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/slsr-34.c
@@ -0,0 +1,43 @@
+/* Verify straight-line strength reduction for a candidate with a basis
+   hidden by two phi dependences, and having a known stride.  */
+
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+extern void
+g (void);
+
+int
+f (int c, int i)
+{
+  int a1, a2, a3, x1, x2, x3, x;
+
+  a1 = i * 16;
+  x1 = c + a1;
+
+  i = i + 2;
+  a2 = i * 16;
+  x2 = c + a2;
+
+  if (x2 > 6)
+    {
+      if (c < 200)
+	i = i + 2;
+      else
+	i = i + 4;
+      g ();
+    }
+  else
+    i = i + 6;
+
+  i = i + 2;
+  a3 = i * 16;
+  x3 = c + a3;
+
+  x = x1 + x2 + x3;
+  return x;
+}
+
+/* { dg-final { scan-tree-dump-times " \\* " 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "PHI" 2 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/slsr-35.c b/gcc/testsuite/gcc.dg/tree-ssa/slsr-35.c
new file mode 100644
index 0000000..3f4d136
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/slsr-35.c
@@ -0,0 +1,28 @@
+/* Verify straight-line strength reduction for a candidate with a basis
+   hidden by a phi dependences, having a known stride, and where the 
+   phi has an argument which is a parameter.  */
+
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+int
+f (int c, int i)
+{
+  int a1, a3, x1, x3, x;
+
+  a1 = i * 16;
+  x1 = c + a1;
+
+  if (x1 > 6)
+    i = i + 2;
+
+  i = i + 2;
+  a3 = i * 16;
+  x3 = c + a3;
+
+  x = x1 + x3;
+  return x;
+}
+
+/* { dg-final { scan-tree-dump-times " \\* " 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/slsr-36.c b/gcc/testsuite/gcc.dg/tree-ssa/slsr-36.c
new file mode 100644
index 0000000..8cb09e0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/slsr-36.c
@@ -0,0 +1,29 @@
+/* Verify straight-line strength reduction for a candidate with a basis
+   hidden by a phi dependences, having an unknown stride, and where the 
+   phi has an argument which is a parameter.  */
+
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+int
+f (int s, int c, int i)
+{
+  int a1, a3, x1, x3, x;
+
+  a1 = i * s;
+  x1 = c + a1;
+
+  if (x1 > 6)
+    i = i + 2;
+
+  i = i + 2;
+  a3 = i * s;
+  x3 = c + a3;
+
+  x = x1 + x3;
+  return x;
+}
+
+/* { dg-final { scan-tree-dump-times " \\* s" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " \\* 2" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/slsr-37.c b/gcc/testsuite/gcc.dg/tree-ssa/slsr-37.c
new file mode 100644
index 0000000..fb13b20
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/slsr-37.c
@@ -0,0 +1,33 @@
+/* Verify straight-line strength reduction for a candidate with a basis
+   hidden by a phi dependence and having an unknown stride.  Variation
+   using negative increments.  */
+
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+int
+f (int s, int c, int i)
+{
+  int a1, a2, a3, x1, x2, x3, x;
+
+  a1 = i * s;
+  x1 = c + a1;
+
+  i = i - 2;
+  a2 = i * s;
+  x2 = c + a2;
+
+  if (x2 > 6)
+    i = i - 2;
+
+  i = i - 2;
+  a3 = i * s;
+  x3 = c + a3;
+
+  x = x1 + x2 + x3;
+  return x;
+}
+
+/* { dg-final { scan-tree-dump-times " \\* s" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " \\* 2" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/slsr-38.c b/gcc/testsuite/gcc.dg/tree-ssa/slsr-38.c
new file mode 100644
index 0000000..1a0ab79
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/slsr-38.c
@@ -0,0 +1,32 @@
+/* Verify straight-line strength reduction for a candidate with a basis
+   hidden by a phi dependence and having a known stride.  Variation using
+   negative increments.  */
+
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+int
+f (int c, int i)
+{
+  int a1, a2, a3, x1, x2, x3, x;
+
+  a1 = i * 16;
+  x1 = c + a1;
+
+  i = i - 2;
+  a2 = i * 16;
+  x2 = c + a2;
+
+  if (x2 > 6)
+    i = i - 2;
+
+  i = i - 2;
+  a3 = i * 16;
+  x3 = c + a3;
+
+  x = x1 + x2 + x3;
+  return x;
+}
+
+/* { dg-final { scan-tree-dump-times " \\* " 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */