Another issue that can't help fmax is the way the Avalon MM bus seems to do address decoding.
AFAICT it never aliases targets - so will be doing comparisons on more bits that strictly necessary. The nios selecting between tightly coupled data and other data ought to generate warnings for some cases it just allows.
We have a system with a 16MB sdram (base address 16M), some 16kB (or smaller) M9K blocks (below 128kB) and some io (just above 128kb).
The address decode need only use A24 (to select SDRAM) A17 (for io) and A14-16 to select between the M9K blocks.
However I don't see any address aliasing - even if we put down a 12kB block of M9K. All these extra comparisons must be affecting fmax.
(and there doesn't even seem to be a 'normal' option to enable an interrupt if the nios accessed an unmapped slave address.