diff mbox series

[Bug,tree-optimization/109429,v2] ivopts: fixed complexities

Message ID PA4PR09MB4864528889BD5BA63D63986984692@PA4PR09MB4864.eurprd09.prod.outlook.com
State New
Headers show
Series [Bug,tree-optimization/109429,v2] ivopts: fixed complexities | expand

Commit Message

Aleksandar Rakic Sept. 25, 2024, 3:32 p.m. UTC 
Hi,

I think I managed to fix indentation from the previous version.
 
When comparing the tables showing the candidates for the group 1 before
and after applying this patch, it can be observed that complexities for
the candidates where the computation depends on the invariant
expressions or the invariant variables should be at least one, which
aligns with the approach used in the commit c2b64ce.
 
===== Before this patch =====
Group 1:
  cand	cost	compl.	inv.expr.	inv.vars
  1	11	0	5;	NIL;
  2	11	0	6;	NIL;
  4	8	0	7;	NIL;
  5	9	0	8;	NIL;
  6	1	0	NIL;	NIL;
  7	1	1	NIL;	NIL;
  9	7	0	5;	NIL;
===== Before this patch =====
===== After this patch =====
Group 1:
  cand	cost	compl.	inv.expr.	inv.vars
  1	11	2	4;	NIL;
  2	11	1	4;	NIL;
  4	8	1	5;	NIL;
  5	8	2	6;	NIL;
  6	1	0	NIL;	NIL;
  7	1	1	NIL;	NIL;
  9	7	2	4;	NIL;
===== After this patch =====
 
Hence, if the invariant expressions or the invariant variables are used
when representing use with candidate, the complexity should be larger
for more complex expressions, so it is incremented by one. I am not sure
whether inv_present could be expressed as parts.

Regards,
Aleksandar

Comments

Aleksandar Rakic Oct. 9, 2024, 12:15 p.m. UTC | #1 
A kind remind/ping on the patch.

Kind regards,
Aleksandar Rakić
Aleksandar Rakic Oct. 31, 2024, 11:46 a.m. UTC | #2 
A kind remind/ping on the patch.

Kind regards,
Aleksandar Rakić
diff mbox series

Patch

From a459b8fd04608de7f6ead52f373f59a8bc5f3199 Mon Sep 17 00:00:00 2001
From: Aleksandar <aleksandar.rakic@htecgroup.com>
Date: Tue, 24 Sep 2024 13:14:37 +0200
Subject: [PATCH v2] [Bug tree-optimization/109429] ivopts: fixed complexities

This patch addresses a bug introduced in commit f9f69dd by
correcting the complexity calculation in ivopts. The fix involves
complexity computation reordering and proper invariant variables
handling in address expressions. These changes align with the
approach used in parent commit c2b64ce. The improved complexity
calculations ensure better candidate selection and reduced code
size, particularly for RISC CPUs.

Signed-off-by: Aleksandar Rakic <aleksandar.rakic@htecgroup.com>
Signed-off-by: Jovan Dmitrovic <jovan.dmitrovic@htecgroup.com>

gcc/ChangeLog:

        * tree-ssa-loop-ivopts.cc (get_address_cost): Fixed
        complexity calculation.

gcc/testsuite/ChangeLog:

        * gcc.dg/tree-ssa/bug_tree-optimization_109429.c: New
        test.
---
 .../tree-ssa/bug_tree-optimization_109429.c   | 32 +++++++++++
 gcc/tree-ssa-loop-ivopts.cc                   | 56 +++++++++----------
 2 files changed, 60 insertions(+), 28 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bug_tree-optimization_109429.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bug_tree-optimization_109429.c b/gcc/testsuite/gcc.dg/tree-ssa/bug_tree-optimization_109429.c
new file mode 100644
index 00000000000..945693bd27f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/bug_tree-optimization_109429.c
@@ -0,0 +1,32 @@ 
+/* { dg-do compile { target mips64-r6-linux-gnu } } */
+/* { dg-options "-O2 -fdump-tree-ivopts-details" } */
+/* This test ensures that complexity must be greater than zero if there is
+   an invariant variable or an invariant expression in the address
+   expression.  */
+
+void daxpy (float *vector1, float *vector2, int n, float fp_const)
+{
+       for (int i = 0; i < n; ++i)
+               vector1[i] += fp_const * vector2[i];
+}
+
+void dgefa (float *vector, int m, int n, int l)
+{
+       for (int i = 0; i < n - 1; ++i)
+       {
+               for (int j = i + 1; j < n; ++j)
+               {
+                       float t = vector[m * j + l];
+                       daxpy (&vector[m * i + i + 1],
+                               &vector[m * j + i + 1], n - (i + 1), t);
+               }
+       }
+}
+
+
+/* { dg-final { scan-tree-dump-not "Processing loop 3(.*\n)*<IV Groups>:(.*\n)*Group 1:\n  Type:.*ADDRESS(.*\n)*Group 1:\n  cand\tcost\tcompl\.\tinv\.expr\.\tinv\.vars\n(.*\n)*(.+\t.+\t0\t\\d+(, \\d+)*;\t.+\n)(.*\n)*Group 2:\n  cand\tcost\tcompl\.\tinv\.expr\.\tinv\.vars\n(.*\n)*Selected IV set for loop 3" "ivopts" { target { mips64-r6-linux-gnu } } } } */
+
+
+/* { dg-final { scan-tree-dump-not "Processing loop 3(.*\n)*<IV Groups>:(.*\n)*Group 1:\n  Type:.*ADDRESS(.*\n)*Group 1:\n  cand\tcost\tcompl\.\tinv\.expr\.\tinv\.vars\n(.*\n)*(.+\t.+\t0\t.+\t\\d+(, \\d+)*\n)(.*\n)*Group 2:\n  cand\tcost\tcompl\.\tinv\.expr\.\tinv\.vars\n(.*\n)*Selected IV set for loop 3" "ivopts" { target { mips64-r6-linux-gnu } } } } */
+
+
diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 7cae5bdefea..960dd8be782 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -4755,38 +4755,35 @@  get_address_cost (struct ivopts_data *data, struct iv_use *use,
 	  if (!ok_with_ratio_p)
 	    parts.step = NULL_TREE;
 	}
-      if (ok_with_ratio_p || ok_without_ratio_p)
+      if (!(ok_with_ratio_p || ok_without_ratio_p))
+	  parts.index = NULL_TREE;
+      if (maybe_ne (aff_inv->offset, 0))
 	{
-	  if (maybe_ne (aff_inv->offset, 0))
-	    {
-	      parts.offset = wide_int_to_tree (sizetype, aff_inv->offset);
-	      /* Addressing mode "base + index [<< scale] + offset".  */
-	      if (!valid_mem_ref_p (mem_mode, as, &parts, code))
-		parts.offset = NULL_TREE;
-	      else
-		aff_inv->offset = 0;
-	    }
+	  parts.offset = wide_int_to_tree (sizetype, aff_inv->offset);
+	  /* Addressing mode "base[+ index[<< scale]] + offset".  */
+	  if (!valid_mem_ref_p (mem_mode, as, &parts, code))
+	    parts.offset = NULL_TREE;
+	  else
+	    aff_inv->offset = 0;
+	}
 
-	  move_fixed_address_to_symbol (&parts, aff_inv);
-	  /* Base is fixed address and is moved to symbol part.  */
-	  if (parts.symbol != NULL_TREE && aff_combination_zero_p (aff_inv))
-	    parts.base = NULL_TREE;
+      move_fixed_address_to_symbol (&parts, aff_inv);
+      /* Base is fixed address and is moved to symbol part.  */
+      if (parts.symbol != NULL_TREE && aff_combination_zero_p (aff_inv))
+	  parts.base = NULL_TREE;
 
-	  /* Addressing mode "symbol + base + index [<< scale] [+ offset]".  */
-	  if (parts.symbol != NULL_TREE
-	      && !valid_mem_ref_p (mem_mode, as, &parts, code))
-	    {
-	      aff_combination_add_elt (aff_inv, parts.symbol, 1);
-	      parts.symbol = NULL_TREE;
-	      /* Reset SIMPLE_INV since symbol address needs to be computed
-		 outside of address expression in this case.  */
-	      simple_inv = false;
-	      /* Symbol part is moved back to base part, it can't be NULL.  */
-	      parts.base = integer_one_node;
-	    }
+      /* Addressing mode "symbol + base[+ index[<< scale]] [+ offset]".  */
+      if (parts.symbol != NULL_TREE
+	  && !valid_mem_ref_p (mem_mode, as, &parts, code))
+	{
+	  aff_combination_add_elt (aff_inv, parts.symbol, 1);
+	  parts.symbol = NULL_TREE;
+	  /* Reset SIMPLE_INV since symbol address needs to be computed
+	     outside of address expression in this case.  */
+	  simple_inv = false;
+	  /* Symbol part is moved back to base part, it can't be NULL.  */
+	  parts.base = integer_one_node;
 	}
-      else
-	parts.index = NULL_TREE;
     }
   else
     {
@@ -4856,6 +4853,9 @@  get_address_cost (struct ivopts_data *data, struct iv_use *use,
 
   if (parts.symbol != NULL_TREE)
     cost.complexity += 1;
+  if ((inv_vars && *inv_vars && !bitmap_empty_p (*inv_vars))
+      || (inv_expr && *inv_expr != NULL))
+    cost.complexity += 1;
   /* Don't increase the complexity of adding a scaled index if it's
      the only kind of index that the target allows.  */
   if (parts.step != NULL_TREE && ok_without_ratio_p)
-- 
2.34.1