[Bug tree-optimization/83221] [8 Regression] qsort comparator not anti-commutative: -2147483648, -2147483648

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2017-11-30
                 CC|                            |jakub at gcc dot gnu.org
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The problem is that the testcase contains more than 32768 basic blocks.

One way to fix it is:
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);

Another possibility is to store bb_rank unshifted and shift only when using
bb_rank
except for this sort_by_operand_rank spot.

Perhaps the best fix is to change the types of all the ranks from unsigned int
(used in some spots) and long (in other spots) to uint64_t, on 64-bit hosts it
shouldn't make much difference if we say reorder:
struct operand_entry
{
  unsigned int rank;
  unsigned int id;
  tree op;
  unsigned int count;
  gimple *stmt_to_insert;
};
to
struct operand_entry
{
  unsigned int count;
  unsigned int id;
  tree op;
  uint64_t rank;
  gimple *stmt_to_insert;
};

Guess
static int
compare_repeat_factors (const void *x1, const void *x2)
{
  const repeat_factor *rf1 = (const repeat_factor *) x1;
  const repeat_factor *rf2 = (const repeat_factor *) x2;

  if (rf1->count != rf2->count)
    return rf1->count - rf2->count;

  return rf2->rank - rf1->rank;
}
should be changed in any case to do:
  if (rf1->rank != rf2->rank)
    return rf2->rank > rf1->rank ? 1 : -1;
  return 0;
and likely also the count case.

Richard, thoughts on this?