[Bug rtl-optimization/69609] block reordering consumes an inordinate amount of time, REE consumes much memory

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 37718
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=37718&action=edit
patch

The attached patch implements a simple caching mechanism which reduces time
(checking enabled but with -fno-checking) from

 reorder blocks          : 260.53 (80%) usr   0.37 (27%) sys 261.80 (80%) wall 
432597 kB (58%) ggc
 TOTAL                 : 323.98             1.38           328.14            
745950 kB

to

 reorder blocks          : 135.46 (71%) usr   0.12 ( 9%) sys 135.70 (71%) wall 
432597 kB (58%) ggc
 TOTAL                 : 190.60             1.29           192.10            
745950 kB

I'm going to see whether bb_to_key is still the issue (the resetting of cached
key could be made smarter, updating the value from the edge that changed).

Still the above is a reasonable improvement given we have

          FOR_EACH_EDGE (e, ei, bb->succs)
            {
              if (e == best_edge
                  || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
                  || bb_visited_trace (e->dest))
                continue;

              key = bb_to_key (e->dest);

where bb_to_key does FOR_EACH_EDGE (e, ei, bb->preds).

Yup.  Even with the patch bb_to_key is still taking 67% of the compile time
(according to perf).