[Bug rtl-optimization/93264] [10 Regression] ICE in cfg_layout_redirect_edge_and_branch_force, at cfgrtl.c:4522

[Bug rtl-optimization/93264] [10 Regression] ICE in cfg_layout_redirect_edge_and_branch_force, at cfgrtl.c:4522

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93264

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
So let's try to address this in cfgloop.c - we're likely facing the situation
of

 header:
...
  if (...) goto latch1;

 latch2:
   goto header;

 latch1: // in cold section
   goto header;

where latch disambiguation via merge_latch_egdes tries to build

  header:
...
  if (...) goto latch1;

 latch2:
   goto latch3;

 latch1: // in cold section
   goto latch3;

 latch3: // somewhere
   goto header;

but somehow we end up redirecting a jump that was formerly crossing
to non-crossing.  Looking at the backtrace it must be entry edges
that are being redirected but the whole setup should be so that
the crossing state of a branch is never changed.

Unfortunately I can't reproduce on todays trunk, will try rewiding backwards
to the reporting time to have a closer look.

[Bug rtl-optimization/93264] [10 Regression] ICE in cfg_layout_redirect_edge_and_branch_force, at cfgrtl.c:4522

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93264

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #7)
> Unfortunately I can't reproduce on todays trunk, will try rewiding backwards
> to the reporting time to have a closer look.

Strange, I can (tried r10-7514).
./cc1 -quiet -nostdinc -O3 -fomit-frame-pointer -funroll-loops -fpeel-loops
-ftracer -finline-functions -fmodulo-sched -freorder-blocks-and-partition
pr71550.c
x86_64-linux -> aarch64-linux cross with installed cross-binutils for the
target.

[Bug rtl-optimization/93264] [10 Regression] ICE in cfg_layout_redirect_edge_and_branch_force, at cfgrtl.c:4522

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93264

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
Pilot error.

loop->header is in the cold partition, both latch sources are as well,
the loop entry source is in the hot partition.  We're correctly
redirecting that from hot -> cold to hot -> cold state so

  if (e->flags & EDGE_CROSSING
      && BB_PARTITION (e->src) == BB_PARTITION (dest)
      && simplejump_p (BB_END (src)))
    {

doesn't apply anyways so we run into

edge
try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout)
{
...
  /* If we are partitioning hot/cold basic blocks, we don't want to
     mess up unconditional or indirect jumps that cross between hot
     and cold sections.

     Basic block partitioning may result in some jumps that appear to
     be optimizable (or blocks that appear to be mergeable), but which really
     must be left untouched (they are required to make it safely across
     partition boundaries).  See  the comments at the top of
     bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */

  if (BB_PARTITION (src) != BB_PARTITION (target))
    return NULL;

where the referenced comment says

   IMPORTANT NOTE: This optimization causes some messy interactions
   with the cfg cleanup optimizations; those optimizations want to
   merge blocks wherever possible, and to collapse indirect jump
   sequences (change "A jumps to B jumps to C" directly into "A jumps
   to C").  Those optimizations can undo the jump fixes that
   partitioning is required to make (see above), in order to ensure
   that jumps attempting to cross section boundaries are really able
   to cover whatever distance the jump requires (on many architectures
   conditional or unconditional jumps are not able to reach all of
   memory).  Therefore tests have to be inserted into each such
   optimization to make sure that it does not undo stuff necessary to
   cross partition boundaries.  This would be much less of a problem
   if we could perform this optimization later in the compilation, but
   unfortunately the fact that we may need to create indirect jumps
   (through registers) requires that this optimization be performed
   before register allocation.

but any such fixup jumps would appear inside the original section
(and not crossing).  So preserving the crossing state should be a
good enough and better check?

diff --git a/gcc/cfgrtl.c b/gcc/cfgrtl.c
index fb551e3efc0..f2783b1d7ed 100644
--- a/gcc/cfgrtl.c
+++ b/gcc/cfgrtl.c
@@ -1046,7 +1046,7 @@ try_redirect_by_replacing_jump (edge e, basic_block
target, bool in_cfglayout)
      partition boundaries).  See  the comments at the top of
      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */

-  if (BB_PARTITION (src) != BB_PARTITION (target))
+  if (BB_PARTITION (e->dest) != BB_PARTITION (target))
     return NULL;

   /* We can replace or remove a complex jump only when we have exactly

covers the testcase but will inhibit redirects allowed previously
when e->src is hot, e->dest was cold and target is now hot.  But that
should be covered by the special-case using simplejump_p.

Ah, OK, here the jump is an indirect one, so not simple.  And we'd
need to replace it with an indirect one for partitioning correctness
which we are not able to do here.

For the testcase at hand we could use sth else than make_forwarder_block,
like manually create a new BB, redirect all latches to it and then
create a new edge to the old header from it.  The redirects/creations
would be all in the same partition.  But then there may be the case
of a latch edge being crossing (a very cold latch in a hot loop) and
we'd face the very same issue.

Currently loop analysis thinks it can always make loops only have a single
latch so "failure" isn't an option here.

So we need to teach cfgrtl.c to redirect forming a similar instruction
as it was there before (create another indirect jump, but after reload
this needs a register - we don't know whether the jump target reg is
live).  Ugh.

On the testcase itself

diff --git a/gcc/modulo-sched.c b/gcc/modulo-sched.c
index 77254b31b42..66260fa34f1 100644
--- a/gcc/modulo-sched.c
+++ b/gcc/modulo-sched.c
@@ -1347,8 +1347,7 @@ sms_schedule (void)
   edge latch_edge;
   HOST_WIDE_INT trip_count, max_trip_count;

-  loop_optimizer_init (LOOPS_HAVE_PREHEADERS
-                      | LOOPS_HAVE_RECORDED_EXITS);
+  loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
   if (number_of_loops (cfun) <= 1)
     {
       loop_optimizer_finalize ();

works.

[Bug rtl-optimization/93264] [10 Regression] ICE in cfg_layout_redirect_edge_and_branch_force, at cfgrtl.c:4522

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93264

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
Makes me wonder if hot/cold splitting should use a special jump instruction
for crossing jumps which we could fixup/split very late so we see

 (parallel
    (set reg (label_ref ..))
    (set pc (reg))
    (clobber reg))

or something like that.  That is, make sure the crossing jump, if
indirect, has the destination computation easily accessible and
replaceable.

[Bug rtl-optimization/93264] [10 Regression] ICE in cfg_layout_redirect_edge_and_branch_force, at cfgrtl.c:4522

[zhroma at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93264

--- Comment #11 from Roman Zhuykov <zhroma at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #9)

Thank you, I'm glad to see new ideas and some discussion.

> On the testcase itself
> 
> diff --git a/gcc/modulo-sched.c b/gcc/modulo-sched.c
> index 77254b31b42..66260fa34f1 100644
> --- a/gcc/modulo-sched.c
> +++ b/gcc/modulo-sched.c
> @@ -1347,8 +1347,7 @@ sms_schedule (void)
>    edge latch_edge;
>    HOST_WIDE_INT trip_count, max_trip_count;
>  
> -  loop_optimizer_init (LOOPS_HAVE_PREHEADERS
> -                      | LOOPS_HAVE_RECORDED_EXITS);
> +  loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
>    if (number_of_loops (cfun) <= 1)
>      {
>        loop_optimizer_finalize ();
> 
> works.
Unfortunately, this brokes the whole SMS workflow.  See e.g. loop_canon_p
function and a call to single_exit inside.  I've actually tried only improved
(with all my patches) master version and only few examples, but with
AVOID_CFG_MODIFICATIONS some of them bailout with "SMS loop many exits" instead
of succesfully passing analysis and transformation phases with "SMS succeeded".

[Bug rtl-optimization/93264] [10 Regression] ICE in cfg_layout_redirect_edge_and_branch_force, at cfgrtl.c:4522

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93264

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Roman Zhuykov from comment #6)
> First, I want here to mention that Richard have recently discussed
> partitioning in mailing list with Segher, starting from
> https://gcc.gnu.org/ml/gcc-patches/2020-02/msg00666.html
> 
> > I'll run some cross-testing to check how it works for now.
> Second, those tests have finished and there is nothing to say about the
> results. From correctness aspect everything looks fine.  But I haven't tried
> to look at each example where it prevents/allows loops to be scheduled, and
> know nothing about performance impact.
> 
> (In reply to rsandifo@gcc.gnu.org from comment #4)
> > Yeah, it ought to be better to do mode switching first.  But I think
> > the more important ones are:
> >
> >        NEXT_PASS (pass_split_all_insns);
> >        NEXT_PASS (pass_lower_subreg3);
> >
> > Scheduling should happen on the split form of insns rather than the
> > unsplit form.  lower_subreg should also improve "schedulability".
> Agreed, so it would be much better to fix the issue conservatively without
> moving the pass.

As of pass ordering partitioning needs to run before RA but I don't see
why it necessarily needs to run that early.  Well, it works on CFG layout
mode and it's the "last" pass before we go out of CFG layout - but obviously
SMS goes back into so we could do the very same dance for partitioning
and only schedule it after SMS (or even later).

The whole complication arises from the direct CFG edges that are
implemented with indirect jumps and which we cannot easily redirect.
A more high-level representation of those "direct jumps" would make
redirection possible again (at the expense of micro-optimizing the
reg set + indirect jump between partitioning and the point we
expose the operation).  The only thing we need is the RA giving us
a scratch register we can use.  Maybe we can have a special named
pattern for those jumps allocating an extra scratch and have targets
either split them after reload into true indirect jumps or leave them
in place all the way to asm output.  So they'd appear as simple_jump_p
for a much longer time?

Currently we have

(insn 577 350 578 27 (set (reg:DI 309)
        (high:DI (label_ref:DI 220))) "pr71550.c":19:20 -1
     (insn_list:REG_LABEL_OPERAND 220 (nil)))
(insn 578 577 579 27 (set (reg:DI 308)
        (lo_sum:DI (reg:DI 309)
            (label_ref:DI 220))) "pr71550.c":19:20 -1
     (insn_list:REG_LABEL_OPERAND 220 (expr_list:REG_EQUAL (label_ref:DI 220)
            (nil))))
(jump_insn/j 579 578 220 27 (set (pc)
        (reg:DI 308)) "pr71550.c":19:20 -1
     (nil)

not sure if jump_insns can have extra operands for the scratch but
we want part of the jump to be like

(jump_insn/j 579 578 220 27 (set (pc)
        (label_ref:DI 220)) "pr71550.c":19:20 -1
     (nil)

but also mention (reg:DI 309) as scratch.

Ideas?  I guess doing

(jump_insn/j 579 578 220 27 [
  (set (pc) (label_ref:DI 220))
  (clobber (reg:DI 309))])

might work?  The pattern of the jump insn woudl be a parallel though
so not match simplejump_p.  There's also JUMP_LABEL, not sure if that's
usable.  There's condjump_in_parallel_p so we could add
simplejump_in_parallel_p as well and use that in CFG manipulation.

This woudl of course need support from targets but where partitioning
decides it needs to emit indirect jumps it could say that it needs
such target support or otherwise refuse to operate.  Currently
we look at HAS_LONG_COND_BRANCH / HAS_LONG_UNCOND_BRANCH where
only failure in the latter needs indirect jumps using "indirect_jump".
So we'd add sth like

(define_insn "crossing_jump"
  [(set (pc) (label_ref (match_operand 0 "" ""))
   (clobber (match_scratch:DI 1))]
  ""
  "br\\t%1"
  [(set_attr "type" "branch")]
)

with the assembly part adjusted accordingly (the move is missing).  As said
a late splitter may be the best approach (but that's up to the target).

And partitioning would require either HAS_LONG_UNCOND_BRANCH or
targetm.have_crossing_jump and we'd arrange for CFG manipulation to
handle this form.
Oh, and while these issues can trigger in a way appearing as P1 regression
they of course really are not new issues.  So yeah, not really P1.

[Bug rtl-optimization/93264] [10 Regression] ICE in cfg_layout_redirect_edge_and_branch_force, at cfgrtl.c:4522

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93264

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
And for the moment we could declare !HAS_LONG_UNCOND_BRANCH as unsupported for
partitioning.  The list of unconditionally supported targets then is
just cr16, ft32, i386, m32c, moxie and pru.  aarch64 supports such branches
when aarch64_cmodel == AARCH64_CMODEL_TINY || aarch64_cmodel ==
AARCH64_CMODEL_TINY_PIC.

[Bug rtl-optimization/93264] [10 Regression] ICE in cfg_layout_redirect_edge_and_branch_force, at cfgrtl.c:4522

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93264

--- Comment #14 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
I bet even i386 shouldn't claim to support it if ix86_cmodel == CM_LARGE ||
ix86_cmodel == CM_LARGE_PIC.

[Bug rtl-optimization/93264] [10 Regression] ICE in cfg_layout_redirect_edge_and_branch_force, at cfgrtl.c:4522

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93264

--- Comment #15 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
And I agree having such a named patterns (but also with standardized RTL in it,
so that jump.c can recognize those and redirect) looks like a good idea, we
could then enable partitioning if HAVE_LONG_UNCOND_BRANCH or this named pattern
exists and disable otherwise, and targets could then enable it one by one at
their own pace.

[Bug rtl-optimization/93264] [10 Regression] ICE in cfg_layout_redirect_edge_and_branch_force, at cfgrtl.c:4522

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93264

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P1                          |P2
   Target Milestone|10.0                        |11.0

--- Comment #16 from Richard Biener <rguenth at gcc dot gnu.org> ---
Downgrading and re-targeting to GCC 11 (sorry).  The underlying issue is latent
since a long time while the actual testcase with SMS + partitioning on the
respective target worked before "by accident" and now no longer works.

[Bug rtl-optimization/93264] [10/11/12 Regression] ICE in cfg_layout_redirect_edge_and_branch_force, at cfgrtl.c:4522

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93264

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.0                        |11.2

--- Comment #17 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 11.1 has been released, retargeting bugs to GCC 11.2.

[Bug rtl-optimization/93264] [10/11/12 Regression] ICE in cfg_layout_redirect_edge_and_branch_force, at cfgrtl.c:4522

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93264

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.2                        |11.3

--- Comment #18 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 11.2 is being released, retargeting bugs to GCC 11.3

[Bug rtl-optimization/93264] [10/11/12 Regression] ICE in cfg_layout_redirect_edge_and_branch_force, at cfgrtl.c:4522

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93264

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.3                        |11.4

--- Comment #19 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 11.3 is being released, retargeting bugs to GCC 11.4.

[Bug rtl-optimization/93264] [10/11/12/13/14 Regression] ICE in cfg_layout_redirect_edge_and_branch_force, at cfgrtl.c:4522

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93264

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.4                        |11.5

--- Comment #20 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 11.4 is being released, retargeting bugs to GCC 11.5.