public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [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).