* [PATCH] Fix reassoc qsort checking ICE (PR tree-optimization/83221)
@ 2017-11-30 23:19 Jakub Jelinek
2017-12-01 7:04 ` Richard Biener
0 siblings, 1 reply; 2+ messages in thread
From: Jakub Jelinek @ 2017-11-30 23:19 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
Hi!
bb_rank is long and has basic block indexes << 16, and oe rank
is unsigned int.
So, if some function has over 32767 basic blocks, we can run into various
issues.
As I said in the PR, I see 3 possible fixes, one is attached below and
the shortest, which I've bootstrapped/regtested on x86_64-linux and
i686-linux. While it not fix all possible issues, at least if there
aren't way too many basic blocks (2G+) on 64-bit hosts it shouldn't
fail the qsort checking, and on 32-bit hosts also, even when above 64K
basic blocks it is possible two different basic blocks will have the same
rank and we fall through to reassoc_stmt_dominates_stmt_p.
Another possibility is to store bb_rank still as long, but don't << 16
it when initializing, but when using except for this sort_by_operand_rank
spot.
And probably best but most involved change would be to switch to using
uint64_t for bb_rank, phi_rank as well as oe->rank. By reordering fields
in oe it shouldn't make things worse on 64-bit hosts, but for 32-bit hosts
will need more memory; on the other side, it should handle better 32K+ basic
block cases, which even for 32-bit host compilers in some cases can be
handled within the limited 32-bit host address space.
So, is this ok for trunk or should I pick some other option?
2017-11-30 Jakub Jelinek <jakub@redhat.com>
PR tree-optimization/83221
* tree-ssa-reassoc.c (sort_by_operand_rank): Shift bb_rank
down by 16.
(init_reassoc): Formatting fix.
--- gcc/tree-ssa-reassoc.c.jj 2017-10-28 09:00:48.000000000 +0200
+++ gcc/tree-ssa-reassoc.c 2017-11-30 16:07:47.220334364 +0100
@@ -543,7 +543,7 @@ sort_by_operand_rank (const void *pa, co
return -1;
/* If neither is, compare bb_rank. */
if (bb_rank[bbb->index] != bb_rank[bba->index])
- return bb_rank[bbb->index] - bb_rank[bba->index];
+ return (bb_rank[bbb->index] >> 16) - (bb_rank[bba->index] >> 16);
}
bool da = reassoc_stmt_dominates_stmt_p (stmta, stmtb);
@@ -6131,7 +6131,7 @@ init_reassoc (void)
/* 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;
+ bb_rank[bbs[i]] = ++rank << 16;
free (bbs);
calculate_dominance_info (CDI_POST_DOMINATORS);
Jakub
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [PATCH] Fix reassoc qsort checking ICE (PR tree-optimization/83221)
2017-11-30 23:19 [PATCH] Fix reassoc qsort checking ICE (PR tree-optimization/83221) Jakub Jelinek
@ 2017-12-01 7:04 ` Richard Biener
0 siblings, 0 replies; 2+ messages in thread
From: Richard Biener @ 2017-12-01 7:04 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: gcc-patches
On December 1, 2017 12:10:45 AM GMT+01:00, Jakub Jelinek <jakub@redhat.com> wrote:
>Hi!
>
>bb_rank is long and has basic block indexes << 16, and oe rank
>is unsigned int.
>
>So, if some function has over 32767 basic blocks, we can run into
>various
>issues.
>
>As I said in the PR, I see 3 possible fixes, one is attached below and
>the shortest, which I've bootstrapped/regtested on x86_64-linux and
>i686-linux. While it not fix all possible issues, at least if there
>aren't way too many basic blocks (2G+) on 64-bit hosts it shouldn't
>fail the qsort checking, and on 32-bit hosts also, even when above 64K
>basic blocks it is possible two different basic blocks will have the
>same
>rank and we fall through to reassoc_stmt_dominates_stmt_p.
>
>Another possibility is to store bb_rank still as long, but don't << 16
>it when initializing, but when using except for this
>sort_by_operand_rank
>spot.
>
>And probably best but most involved change would be to switch to using
>uint64_t for bb_rank, phi_rank as well as oe->rank. By reordering
>fields
>in oe it shouldn't make things worse on 64-bit hosts, but for 32-bit
>hosts
>will need more memory; on the other side, it should handle better 32K+
>basic
>block cases, which even for 32-bit host compilers in some cases can be
>handled within the limited 32-bit host address space.
>
>So, is this ok for trunk or should I pick some other option?
This minimal fix is OK. If there's further fallout we can switch to uint64_t.
Richard.
>2017-11-30 Jakub Jelinek <jakub@redhat.com>
>
> PR tree-optimization/83221
> * tree-ssa-reassoc.c (sort_by_operand_rank): Shift bb_rank
> down by 16.
> (init_reassoc): Formatting fix.
>
>--- gcc/tree-ssa-reassoc.c.jj 2017-10-28 09:00:48.000000000 +0200
>+++ gcc/tree-ssa-reassoc.c 2017-11-30 16:07:47.220334364 +0100
>@@ -543,7 +543,7 @@ sort_by_operand_rank (const void *pa, co
> return -1;
> /* If neither is, compare bb_rank. */
> if (bb_rank[bbb->index] != bb_rank[bba->index])
>- return bb_rank[bbb->index] - bb_rank[bba->index];
>+ return (bb_rank[bbb->index] >> 16) - (bb_rank[bba->index] >> 16);
> }
>
> bool da = reassoc_stmt_dominates_stmt_p (stmta, stmtb);
>@@ -6131,7 +6131,7 @@ init_reassoc (void)
>
> /* 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;
>+ bb_rank[bbs[i]] = ++rank << 16;
>
> free (bbs);
> calculate_dominance_info (CDI_POST_DOMINATORS);
>
> Jakub
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2017-12-01 7:04 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-11-30 23:19 [PATCH] Fix reassoc qsort checking ICE (PR tree-optimization/83221) Jakub Jelinek
2017-12-01 7:04 ` 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).