https://gcc.gnu.org/bugzilla/show_bug.cgi?id=128070
--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> --- The CFG structure does not seem problematic at all, but I can confirm super-linear behavior. -details time report shows tree PRE : 1.91 ( 4%) 167M ( 43%) `- alias stmt walking : 41.84 ( 87%) 12M ( 3%) complete unrolling : 0.06 ( 0%) 7582k ( 2%) `- tree SSA incremental : 0.00 ( 0%) 1851k ( 0%) `- tree operand scan : 0.00 ( 0%) 1088k ( 0%) so unrolling itself is not the problem but instead the unrolled IL is problematic for PRE. Specifically the IL presented to the PRE pass, not the iterating FRE that runs after cunrolli. The loops get rotated by loop header copying and the 2nd loop gets a PHI from store-motion. Disabling loop header copying avoids the slowness. w/ loop header copying on a single loop: RPO iteration over 20 blocks visited 41 blocks in total discovering 20 executable blocks iterating 2.0 times, a block was visited max. 3 times RPO tracked 225 values available at 172 locations and 225 lattice elements w/o RPO iteration over 23 blocks visited 44 blocks in total discovering 23 executable blocks iterating 1.9 times, a block was visited max. 3 times RPO tracked 232 values available at 174 locations and 232 lattice elements bumping the number of copies doesn't meaningfully change that but the total number of lines of the PRE dump goes 4682 -> 10254 -> 16587 -> 23676 (5x) -..-> 346975 (74.1x) vs. 4068 -> 8187 -> 12247 -> 16287 (4x) -..-> 100956 (24.8x) where the exit test placement has an influence on the dataflow and insertion iteration order while the value-numbering part uses RPO order optimized for iteration. bad: Pass statistics of "pre": ---------------- RPO blocks: 467 RPO num lattice == 5625: 1 compute_antic iterations == 3: 1 RPO blocks visited: 977 RPO num avail == 4276: 1 RPO num values == 5625: 1 RPO iterations == 20: 1 RPO blocks executable: 467 RPO block visited times == 1: 101 RPO block visited times == 2: 222 RPO block visited times == 3: 144 insert iterations == 1: 1 Eliminated: 74 good: Pass statistics of "pre": ---------------- RPO num avail == 4350: 1 RPO blocks: 542 compute_antic iterations == 4: 1 RPO blocks visited: 1052 RPO num values == 5800: 1 RPO iterations == 19: 1 New PHIs: 24 RPO blocks executable: 542 RPO block visited times == 1: 176 RPO block visited times == 2: 222 RPO block visited times == 3: 144 RPO num lattice == 5800: 1 insert iterations == 2: 1 Eliminated: 124 by that statistics the good case is worse even :/ Looking at a profile it is walk_non_aliased_vuses cobbling up cost, possibly due to the high walking budget. The non-copied CFG might cause us to give up walking earlier - esp. if we manage to walk through multiple of the chained loops. --param sccvn-max-alias-queries-per-access should still make this "constant time", but it's default is quite high.
