[PATCH][RFC] Fix PR72851 by "randomizing" SSA propagator worklist extraction

[Richard Biener <rguenther at suse dot de>]

The following randomizes SSA propagator worklist processing to make the
processing order less likely hit the worst-case as in the PR.  Ideally
we'd process it in stmt order but that adds overhead to the idea of a
SSA propagator that makes it very much not appealing.  Using a queue
rather than a stack would als be a possibility (but also not really
fix the underlying issue).  So this patch uses a very simple approach
to fix the specific testcase.

Opinion?  Any great ideas on how to avoid O (n log n) sorting or
O (log n) insertion?  [mark blocks to be visited and simply iterate
over all stmts in to-be-visited BBs]

Bootstrap/regtest running on x86_64-unknown-linux-gnu.

Richard.

2016-08-10  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/72851
	* tree-ssa-propagate.c (process_ssa_edge_worklist): Use a
	randomized worklist item order.

	* gcc.dg/torture/pr72851.c: New testcase.

Index: gcc/tree-ssa-propagate.c
===================================================================
*** gcc/tree-ssa-propagate.c	(revision 238469)
--- gcc/tree-ssa-propagate.c	(working copy)
*************** process_ssa_edge_worklist (vec<gimple *>
*** 422,428 ****
        basic_block bb;
  
        /* Pull the statement to simulate off the worklist.  */
!       gimple *stmt = worklist->pop ();
  
        /* If this statement was already visited by simulate_block, then
  	 we don't need to visit it again here.  */
--- 422,429 ----
        basic_block bb;
  
        /* Pull the statement to simulate off the worklist.  */
!       gimple *stmt = (*worklist)[0];
!       worklist->unordered_remove (0);
  
        /* If this statement was already visited by simulate_block, then
  	 we don't need to visit it again here.  */
Index: gcc/testsuite/gcc.dg/torture/pr72851.c
===================================================================
*** gcc/testsuite/gcc.dg/torture/pr72851.c	(revision 0)
--- gcc/testsuite/gcc.dg/torture/pr72851.c	(working copy)
***************
*** 0 ****
--- 1,30 ----
+ /* { dg-do compile } */
+ 
+ typedef unsigned char uint8_t;
+ typedef unsigned long int uint64_t;
+ union unaligned_64 {
+     uint64_t l;
+ }
+ __attribute__((packed)) __attribute__((may_alias));
+ typedef struct AVDES {
+     uint64_t round_keys[3][16];
+ } AVDES;
+ static const uint8_t PC1_shuffle[] = {
+     64-57,64-49,64-41,64-33,64-25,64-17,64-9,     64-1,64-58,64-50,64-42,64-34,64-26,64-18,     64-10,64-2,64-59,64-51,64-43,64-35,64-27,     64-19,64-11,64-3,64-60,64-52,64-44,64-36,     64-63,64-55,64-47,64-39,64-31,64-23,64-15,     64-7,64-62,64-54,64-46,64-38,64-30,64-22,     64-14,64-6,64-61,64-53,64-45,64-37,64-29,     64-21,64-13,64-5,64-28,64-20,64-12,64-4 };
+ static const uint8_t PC2_shuffle[] = {
+     56-14,56-17,56-11,56-24,56-1,56-5,     56-3,56-28,56-15,56-6,56-21,56-10,     56-23,56-19,56-12,56-4,56-26,56-8,     56-16,56-7,56-27,56-20,56-13,56-2,     56-41,56-52,56-31,56-37,56-47,56-55,     56-30,56-40,56-51,56-45,56-33,56-48,     56-44,56-49,56-39,56-56,56-34,56-53,     56-46,56-42,56-50,56-36,56-29,56-32 };
+ static uint64_t shuffle(uint64_t in, const uint8_t *shuffle, int shuffle_len)
+ {
+   int i;
+   uint64_t res = 0;
+   for (i = 0; i < shuffle_len; i++)
+     res += res + ((in >> *shuffle++) & 1);
+   return res;
+ }
+ void gen_roundkeys(uint64_t K[16], uint64_t key)
+ {
+   int i;
+   uint64_t CDn = shuffle(key, PC1_shuffle, sizeof(PC1_shuffle));
+   for (i = 0; i < 16; i++)
+     K[i] = shuffle(CDn, PC2_shuffle, sizeof(PC2_shuffle));
+ }