[patch] Tame if-combining when loop unswitching is enabled

[patch] Tame if-combining when loop unswitching is enabled

[Eric Botcazou]

[-- Attachment #1: Type: text/plain, Size: 1353 bytes --]

Hi,

in order to make it possible to vectorize loops running over arrays in Ada, 
which generally contain index checks, hence control-flow instructions, we rely 
on loop unswitching to generate two copies of the loop, one guarded with a 
global condition (no index check fails in the loop) and vectorizable and one 
with the original index checks and non-vectorizable.  This is achieved by the 
simple trick of prepending the global_condition to the condition of the index 
checks and letting the loop unswitching pass do its magic.

But there is an enemy, namely if-combining, which can turn a simple boolean 
conjunction into something else that loop unswitching cannot deal with, and a 
testcase is attached with 3 slightly different versions of the same issue.

Therefore the attached patch attempts to tame if-combining by reasoning on the 
loop invariant status (really loop depths) of the conditions.

Bootstrapped/regtested on x86-64/Linux, OK for the mainline?


2021-10-15  Eric Botcazou  <ebotcazou@adacore.com>

	* tree-ssa-ifcombine.c: Include cfgloop.h.
	(operand_loop_depth): New function.
	(ifcombine_ifandif): When loop unswitching is enabled, do not merge
	conditions whose loop invariant status is different.


2021-10-15  Eric Botcazou  <ebotcazou@adacore.com>

	* gnat.dg/vect19.ads, gnat.dg/vect19.adb: New test.

-- 
Eric Botcazou

[-- Attachment #2: p.diff --]
[-- Type: text/x-patch, Size: 2029 bytes --]

diff --git a/gcc/tree-ssa-ifcombine.c b/gcc/tree-ssa-ifcombine.c
index f93e04aa4df..986084049da 100644
--- a/gcc/tree-ssa-ifcombine.c
+++ b/gcc/tree-ssa-ifcombine.c
@@ -35,6 +35,7 @@ along with GCC; see the file COPYING3.  If not see
    BRANCH_COST.  */
 #include "fold-const.h"
 #include "cfganal.h"
+#include "cfgloop.h"
 #include "gimple-fold.h"
 #include "gimple-iterator.h"
 #include "gimplify-me.h"
@@ -378,6 +379,19 @@ update_profile_after_ifcombine (basic_block inner_cond_bb,
   outer2->probability = profile_probability::never ();
 }
 
+/* Return the loop depth of GIMPLE operand OP.  */
+
+static int
+operand_loop_depth (tree op)
+{
+  basic_block bb;
+
+  if (TREE_CODE (op) == SSA_NAME && (bb = gimple_bb (SSA_NAME_DEF_STMT (op))))
+    return bb_loop_depth (bb);
+
+  return 0;
+}
+
 /* If-convert on a and pattern with a common else block.  The inner
    if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
    inner_inv, outer_inv and result_inv indicate whether the conditions
@@ -554,6 +568,22 @@ ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv,
 	  HONOR_NANS (gimple_cond_lhs (outer_cond)));
       if (outer_cond_code == ERROR_MARK)
 	return false;
+      /* Do not merge if the loop invariant status of the conditions is not
+	 the same and we'll be unswitching loops downstream.  */
+      if (flag_unswitch_loops)
+	{
+	  const int current_depth
+	    = MIN (bb_loop_depth (inner_cond_bb),
+		   bb_loop_depth (outer_cond_bb));
+	  const int inner_depth
+	    = MAX (operand_loop_depth (gimple_cond_lhs (inner_cond)),
+		   operand_loop_depth (gimple_cond_rhs (inner_cond)));
+	  const int outer_depth
+	    = MAX (operand_loop_depth (gimple_cond_lhs (outer_cond)),
+		   operand_loop_depth (gimple_cond_rhs (outer_cond)));
+	  if ((inner_depth < current_depth) != (outer_depth < current_depth))
+	    return false;
+	}
       /* Don't return false so fast, try maybe_fold_or_comparisons?  */
 
       if (!(t = maybe_fold_and_comparisons (boolean_type_node, inner_cond_code,

[-- Attachment #3: vect19.adb --]
[-- Type: text/x-adasrc, Size: 778 bytes --]

-- { dg-do compile { target i?86-*-* x86_64-*-* } }
-- { dg-options "-O3 -msse2 -fno-vect-cost-model -fdump-tree-vect-details" }
-- { dg-additional-options "-gnatX" }

package body Vect19 is

   function "+" (X, Y : Varray) return Varray is
      R : Varray (X'Range);
   begin
      for I in X'Range loop
         R(I) := X(I) + Y(I);
      end loop;
      return R;
   end;

   procedure Add (X, Y : Varray; R : out Varray) is
   begin
      for I in X'Range loop
         R(I) := X(I) + Y(I);
      end loop;
   end;

   procedure Add (X, Y : not null access Varray; R : not null access Varray) is
   begin
      for I in X'Range loop
         R(I) := X(I) + Y(I);
      end loop;
   end;

end Vect19;

-- { dg-final { scan-tree-dump-times "vectorized 1 loops" 3 "vect"  } }

[-- Attachment #4: vect19.ads --]
[-- Type: text/x-adasrc, Size: 303 bytes --]

package Vect19 is

   type Varray is array (Natural range 1 .. <>) of Long_Float;
   for Varray'Alignment use 16;

   function "+" (X, Y : Varray) return Varray;
   procedure Add (X, Y : Varray; R : out Varray);
   procedure Add (X, Y : not null access Varray; R : not null access Varray);

end Vect19;

Re: [patch] Tame if-combining when loop unswitching is enabled

[Richard Biener]

On Fri, Oct 15, 2021 at 11:15 AM Eric Botcazou via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> Hi,
>
> in order to make it possible to vectorize loops running over arrays in Ada,
> which generally contain index checks, hence control-flow instructions, we rely
> on loop unswitching to generate two copies of the loop, one guarded with a
> global condition (no index check fails in the loop) and vectorizable and one
> with the original index checks and non-vectorizable.  This is achieved by the
> simple trick of prepending the global_condition to the condition of the index
> checks and letting the loop unswitching pass do its magic.
>
> But there is an enemy, namely if-combining, which can turn a simple boolean
> conjunction into something else that loop unswitching cannot deal with, and a
> testcase is attached with 3 slightly different versions of the same issue.
>
> Therefore the attached patch attempts to tame if-combining by reasoning on the
> loop invariant status (really loop depths) of the conditions.
>
> Bootstrapped/regtested on x86-64/Linux, OK for the mainline?

Hmm, I see the issue.

This heuristic probably defeats associating the combined conditions to
"good" order?  That is, it looks to me that eventually teaching unswitching
to unswitch on comparisons [feeding GIMPLE_CONDs] would solve the
issue as well?  Martin was working on generalizing the code to handle
switches so eventually he can look into also handling condition parts.

That said, reassoc does order the outermost loop invariant conditions
in the leaf of the condition chain, no?

So,

   for (i;;)
     {
        bool a = inv < 0;
        bool b = i > 3;
        bool c = a && b;
        if (c)
          ...
     }

could be unswitched as


 if (inv < 0)
   for (i;;)
     {
        bool a = true;
        bool b = i > 3;
        bool c = a && b;
        if (c)
          ...
     }
 else
   for (i;;)
     {
        bool a = false;
        bool b = i > 3;
        bool c = a && b;
        if (c)
          ...
     }

>
> 2021-10-15  Eric Botcazou  <ebotcazou@adacore.com>
>
>         * tree-ssa-ifcombine.c: Include cfgloop.h.
>         (operand_loop_depth): New function.
>         (ifcombine_ifandif): When loop unswitching is enabled, do not merge
>         conditions whose loop invariant status is different.
>
>
> 2021-10-15  Eric Botcazou  <ebotcazou@adacore.com>
>
>         * gnat.dg/vect19.ads, gnat.dg/vect19.adb: New test.
>
> --
> Eric Botcazou