Re: [PATCH] Fix reassoc qsort checking ICE (PR tree-optimization/83221)

[Richard Biener <rguenther@suse.de>]

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