predict.c (find_qualified_ssa_name): New

2012-05-08  Dehao Chen  <dehao@google.com>
gcc/
	* predict.c (find_qualified_ssa_name): New
	(find_ssa_name_in_expr): New
	(find_ssa_name_in_assign_stmt): New
	(is_comparison_with_loop_invariant_p): New
	(is_bound_expr_similar): New
	(predict_iv_comparison): New
	(predict_loops): Add heuristic for loop-nested branches that compare an
	induction variable to a loop bound variable.
	* predict.def (PRED_LOOP_IV_COMPARE): New macro
testsuite/
	* gcc.dg/predict-1.c: Check if LOOP_IV_COMPARE static predict
	heuristic is working properly.
	* gcc.dg/predict-2.c: Likewise.
	* gcc/dg/predict-3.c: Likewise.
	* gcc/dg/predict-4.c: Likewise.
	* gcc/dg/predict-5.c: Likewise.
	* gcc/dg/predict-6.c: Likewise.

From-SVN: r187277

7 files changed, 306 insertions, 0 deletions

diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 323c652..f9ef02a8 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,13 @@
+2012-05-08  Dehao Chen  <dehao@google.com>
+
+	* gcc.dg/predict-1.c: Check if LOOP_IV_COMPARE static predict
+	heuristic is working properly.
+	* gcc.dg/predict-2.c: Likewise.
+	* gcc/dg/predict-3.c: Likewise.
+	* gcc/dg/predict-4.c: Likewise.
+	* gcc/dg/predict-5.c: Likewise.
+	* gcc/dg/predict-6.c: Likewise.
+
 2012-05-07  Jakub Jelinek  <jakub@redhat.com>
 
 	PR tree-optimization/53239
diff --git a/gcc/testsuite/gcc.dg/predict-1.c b/gcc/testsuite/gcc.dg/predict-1.c
new file mode 100644
index 0000000..e7f4618
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-1.c
@@ -0,0 +1,54 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar(int);
+
+void foo (int bound)
+{
+  int i, ret = 0;
+  for (i = 0; i < bound; i++)
+    {
+      if (i > bound)
+	global += bar (i);
+      if (i >= bound + 2)
+	global += bar (i);
+      if (i > bound - 2)
+	global += bar (i);
+      if (i + 2 > bound)
+	global += bar (i);
+      if (i == 10)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 0.0%" 5 "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar(int);
+
+void foo (int bound)
+{
+  int i, ret = 0;
+  for (i = 0; i < bound; i++)
+    {
+      if (i > bound)
+	global += bar (i);
+      if (i >= bound + 2)
+	global += bar (i);
+      if (i > bound - 2)
+	global += bar (i);
+      if (i + 2 > bound)
+	global += bar (i);
+      if (i == 10)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 0.0%" 5 "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
diff --git a/gcc/testsuite/gcc.dg/predict-2.c b/gcc/testsuite/gcc.dg/predict-2.c
new file mode 100644
index 0000000..44895b7
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-2.c
@@ -0,0 +1,54 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar(int);
+
+void foo (int base, int bound)
+{
+  int i, ret = 0;
+  for (i = base; i < bound; i++)
+    {
+      if (i > bound * bound)
+	global += bar (i);
+      if (i > bound + 10)
+	global += bar (i);
+      if (i <= bound + 10)
+	global += bar (i);
+      if (i > base + 10)
+	global += bar (i);
+      if (i < base - 10)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-not "loop iv compare heuristics" "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar(int);
+
+void foo (int base, int bound)
+{
+  int i, ret = 0;
+  for (i = base; i < bound; i++)
+    {
+      if (i > bound * bound)
+	global += bar (i);
+      if (i > bound + 10)
+	global += bar (i);
+      if (i <= bound + 10)
+	global += bar (i);
+      if (i > base + 10)
+	global += bar (i);
+      if (i < base - 10)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-not "loop iv compare heuristics" "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
diff --git a/gcc/testsuite/gcc.dg/predict-3.c b/gcc/testsuite/gcc.dg/predict-3.c
new file mode 100644
index 0000000..afaf540
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-3.c
@@ -0,0 +1,50 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar(int);
+
+void foo (int bound)
+{
+  int i, ret = 0;
+  for (i = 0; i <= bound; i++)
+    {
+      if (i < bound - 2)
+	global += bar (i);
+      if (i <= bound)
+	global += bar (i);
+      if (i + 1 < bound)
+	global += bar (i);
+      if (i != bound)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 100.0%" 4 "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar(int);
+
+void foo (int bound)
+{
+  int i, ret = 0;
+  for (i = 0; i <= bound; i++)
+    {
+      if (i < bound - 2)
+	global += bar (i);
+      if (i <= bound)
+	global += bar (i);
+      if (i + 1 < bound)
+	global += bar (i);
+      if (i != bound)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 100.0%" 4 "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
diff --git a/gcc/testsuite/gcc.dg/predict-4.c b/gcc/testsuite/gcc.dg/predict-4.c
new file mode 100644
index 0000000..f575b98
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-4.c
@@ -0,0 +1,38 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar(int);
+
+void foo (int bound)
+{
+  int i, ret = 0;
+  for (i = 0; i < 10; i++)
+    {
+      if (i < 5)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump "loop iv compare heuristics: 50.0%" "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar(int);
+
+void foo (int bound)
+{
+  int i, ret = 0;
+  for (i = 0; i < 10; i++)
+    {
+      if (i < 5)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump "loop iv compare heuristics: 50.0%" "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
diff --git a/gcc/testsuite/gcc.dg/predict-5.c b/gcc/testsuite/gcc.dg/predict-5.c
new file mode 100644
index 0000000..f6e70d3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-5.c
@@ -0,0 +1,50 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar (int);
+
+void foo (int base, int bound)
+{
+  int i, ret = 0;
+  for (i = base; i <= bound; i++)
+    {
+      if (i > base)
+	global += bar (i);
+      if (i > base + 1)
+	global += bar (i);
+      if (i >= base + 3)
+	global += bar (i);
+      if (i - 2 >= base)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 100.0%" 4 "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar (int);
+
+void foo (int base, int bound)
+{
+  int i, ret = 0;
+  for (i = base; i <= bound; i++)
+    {
+      if (i > base)
+	global += bar (i);
+      if (i > base + 1)
+	global += bar (i);
+      if (i >= base + 3)
+	global += bar (i);
+      if (i - 2 >= base)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 100.0%" 4 "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
diff --git a/gcc/testsuite/gcc.dg/predict-6.c b/gcc/testsuite/gcc.dg/predict-6.c
new file mode 100644
index 0000000..552fd07
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-6.c
@@ -0,0 +1,50 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar (int);
+
+void foo (int base, int bound)
+{
+  int i, ret = 0;
+  for (i = base; i <= bound; i++)
+    {
+      if (i < base)
+	global += bar (i);
+      if (i < base + 1)
+	global += bar (i);
+      if (i <= base + 3)
+	global += bar (i);
+      if (i - 1 < base)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 0.0%" 4 "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar (int);
+
+void foo (int base, int bound)
+{
+  int i, ret = 0;
+  for (i = base; i <= bound; i++)
+    {
+      if (i < base)
+	global += bar (i);
+      if (i < base + 1)
+	global += bar (i);
+      if (i <= base + 3)
+	global += bar (i);
+      if (i - 1 < base)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 0.0%" 4 "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */