* [patch] Tame if-combining when loop unswitching is enabled
@ 2021-10-15 9:12 Eric Botcazou
2021-10-15 11:10 ` Richard Biener
0 siblings, 1 reply; 2+ messages in thread
From: Eric Botcazou @ 2021-10-15 9:12 UTC (permalink / raw)
To: gcc-patches
[-- 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;
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [patch] Tame if-combining when loop unswitching is enabled
2021-10-15 9:12 [patch] Tame if-combining when loop unswitching is enabled Eric Botcazou
@ 2021-10-15 11:10 ` Richard Biener
0 siblings, 0 replies; 2+ messages in thread
From: Richard Biener @ 2021-10-15 11:10 UTC (permalink / raw)
To: Eric Botcazou, Martin Liška; +Cc: GCC Patches
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
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2021-10-15 11:10 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-10-15 9:12 [patch] Tame if-combining when loop unswitching is enabled Eric Botcazou
2021-10-15 11:10 ` Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).