[Bug tree-optimization/98514] New: ICE in insert_operand_rank

[Bug tree-optimization/98514] New: ICE in insert_operand_rank

[jakub at gcc dot gnu.org]

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

            Bug ID: 98514
           Summary: ICE in insert_operand_rank
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: jakub at gcc dot gnu.org
  Target Milestone: ---

When building gmic on i686-linux (or other 32-bit arches) with LTO, one gets:
gmic.cpp: In member function '_run.isra':
gmic.cpp:4981:7: internal compiler error: in insert_operand_rank, at
tree-ssa-reassoc.c:367
 4981 | gmic& gmic::_run(const CImgList<char>& commands_line, unsigned int&
position,
      |       ^
It is in 101th partition and the function is huge, so am not going to reduce,
but it seems a general reassoc issue on 32-bit hosts.

The function in question has 104549 SSA_NAMEs and 36954 basic blocks.
Now, the bb ranks are computed as:
  /* Give each default definition a distinct rank.  This includes
     parameters and the static chain.  Walk backwards over all
     SSA names so that we get proper rank ordering according
     to tree_swap_operands_p.  */
  for (i = num_ssa_names - 1; i > 0; --i)
    {
      tree name = ssa_name (i);
      if (name && SSA_NAME_IS_DEFAULT_DEF (name))
        insert_operand_rank (name, ++rank);
    }

  /* Set up rank for each BB  */
  for (i = 0; i < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; i++)
    bb_rank[bbs[i]] = ++rank << 16;
and bb_rank as well as everything else that deals with ranks is long,
so obviously it can't work properly in any function which has more than
32767 (num_ssa_names + n_basic_blocks_for_fn (cfun)).
Either we should punt on trying to reassociate such functions, but that would
make 32-bit hosts behave differently from 64-bit hosts even when targeting the
same target, or my preferred way out of this is make the ranks just
HOST_WIDE_INTs, yes, it will need more memory on 32-bit hosts and will be
slightly slower, but it will be consistent with 64-bit hosts.  We have vectors
of ssa names and basic blocks and those have int length, so even on 64-bit
hosts we can't support more than 4 billion ssa names and more than 4 billion
basic blocks.

[Bug tree-optimization/98514] ICE in insert_operand_rank

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org
   Last reconfirmed|                            |2021-01-04

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 49876
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49876&action=edit
gcc11-pr98512.patch

Untested fix.

[Bug tree-optimization/98514] ICE in insert_operand_rank

[jakub at gcc dot gnu.org]

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

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Oops, sorry, it is just SSA_NAMEs which are default definitions, so that is
less than that; more than 32768 parameters to a function are unlikely, but one
can have thousands of uninitialized SSA_NAMEs, or one can have tens of
thousands of basic blocks.  Even the number of bbs alone is what causes this on
the function.

And I forgot to change %ld to " HOST_WIDE_INT_PRINT_DEC " when printing the
rank, fixed in my copy.

[Bug tree-optimization/98514] ICE in insert_operand_rank

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
note the BB rank assignment via ++rank << 16 implies no more than 1 << 15
SSA defs in each BB as well.  It would be better to simply assign the BB rank
while traversing the IL in a DFS walk (SSA names pick up rank from their
defs or the BB rank of their def) where we know how to assign a distinct
rank for the BB.

But yes, a HWI for the rank looks sensible (or int64_t - HWI is some
legacy thing and 'rank' isn't tied to any struct using HWIs)

[Bug tree-optimization/98514] ICE in insert_operand_rank

[cvs-commit at gcc dot gnu.org]

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

--- Comment #4 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:4ddee425b8c427d3cc13c49b26f442313e239572

commit r11-6473-g4ddee425b8c427d3cc13c49b26f442313e239572
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Jan 5 16:37:40 2021 +0100

    reassoc: Fix reassociation on 32-bit hosts with > 32767 bbs [PR98514]

    Apparently reassoc ICEs on large functions (more than 32767 basic blocks
    with something to reassociate in those).
    The problem is that the pass uses long type to store the ranks, and
    the bb ranks are (number of SSA_NAMEs with default defs + 2 + bb->index) <<
16,
    so with many basic blocks we overflow the ranks and we then have assertions
    rank is not negative.

    The following patch just uses int64_t instead of long in the pass,
    yes, it means slightly higher memory consumption (one array indexed by
    bb->index is twice as large, and one hash_map from trees to the ranks
    will grow by 50%, but I think it is better than punting on large functions
    the reassociation on 32-bit hosts and making it inconsistent e.g. when
    cross-compiling.  Given vec.h uses unsigned for vect element counts,
    we don't really support more than 4G of SSA_NAMEs or more than 2G of basic
    blocks in a function, so even with the << 16 we can't really overflow the
    int64_t rank counters.

    2021-01-05  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/98514
            * tree-ssa-reassoc.c (bb_rank): Change type from long * to
            int64_t *.
            (operand_rank): Change type from hash_map<tree, long> to
            hash_map<tree, int64_t>.
            (phi_rank): Change return type from long to int64_t.
            (loop_carried_phi): Change block_rank variable type from long to
            int64_t.
            (propagate_rank): Change return type, rank parameter type and
            op_rank variable type from long to int64_t.
            (find_operand_rank): Change return type from long to int64_t
            and change slot variable type from long * to int64_t *.
            (insert_operand_rank): Change rank parameter type from long to
            int64_t.
            (get_rank): Change return type and rank variable type from long to
            int64_t.  Use PRId64 instead of ld to print the rank.
            (init_reassoc): Change rank variable type from long to int64_t
            and adjust correspondingly bb_rank and operand_rank initialization.

[Bug tree-optimization/98514] ICE in insert_operand_rank

[jakub at gcc dot gnu.org]

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Hopefully fixed for GCC 11.

[Bug tree-optimization/98514] ICE in insert_operand_rank

[cvs-commit at gcc dot gnu.org]

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

--- Comment #6 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Jakub Jelinek
<jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:8d2e64c4a2892ca8889002b1a3dd713471ef9fab

commit r10-9225-g8d2e64c4a2892ca8889002b1a3dd713471ef9fab
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Jan 5 16:37:40 2021 +0100

    reassoc: Fix reassociation on 32-bit hosts with > 32767 bbs [PR98514]

    Apparently reassoc ICEs on large functions (more than 32767 basic blocks
    with something to reassociate in those).
    The problem is that the pass uses long type to store the ranks, and
    the bb ranks are (number of SSA_NAMEs with default defs + 2 + bb->index) <<
16,
    so with many basic blocks we overflow the ranks and we then have assertions
    rank is not negative.

    The following patch just uses int64_t instead of long in the pass,
    yes, it means slightly higher memory consumption (one array indexed by
    bb->index is twice as large, and one hash_map from trees to the ranks
    will grow by 50%, but I think it is better than punting on large functions
    the reassociation on 32-bit hosts and making it inconsistent e.g. when
    cross-compiling.  Given vec.h uses unsigned for vect element counts,
    we don't really support more than 4G of SSA_NAMEs or more than 2G of basic
    blocks in a function, so even with the << 16 we can't really overflow the
    int64_t rank counters.

    2021-01-05  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/98514
            * tree-ssa-reassoc.c (bb_rank): Change type from long * to
            int64_t *.
            (operand_rank): Change type from hash_map<tree, long> to
            hash_map<tree, int64_t>.
            (phi_rank): Change return type from long to int64_t.
            (loop_carried_phi): Change block_rank variable type from long to
            int64_t.
            (propagate_rank): Change return type, rank parameter type and
            op_rank variable type from long to int64_t.
            (find_operand_rank): Change return type from long to int64_t
            and change slot variable type from long * to int64_t *.
            (insert_operand_rank): Change rank parameter type from long to
            int64_t.
            (get_rank): Change return type and rank variable type from long to
            int64_t.  Use PRId64 instead of ld to print the rank.
            (init_reassoc): Change rank variable type from long to int64_t
            and adjust correspondingly bb_rank and operand_rank initialization.

    (cherry picked from commit 4ddee425b8c427d3cc13c49b26f442313e239572)

[Bug tree-optimization/98514] ICE in insert_operand_rank

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed for 10.3+ and 11+.