UART not fast enough for debug purpose, what alternatives exist?
If I understand correctly, data flow is like:


Binary data inserted into FIFO
Nios reads binary data and formats it using printf()
This text data is sent to PC via JTAG UART


First thing you need to do is figure out if the bottleneck is the JTAG UART (these tend to be very slow) or the printf() formatting on Nios. You can do this simply by making Nios run a "while(1) printf("hello\n");"

Then look at the data rate received by the PC. This should run your virtual JTAG UART at its maximum speed, so you should get lots of data. If it is still very slow, then suspect the JTAG UART. If it runs over USB, then remember USB interrupt transfers only run every frame, so a dumb implementation which flushes every character would max out at one character per USB frame... Check if you can tweak its settings. Is it flushed after every line? Maybe you can use a larger buffer. Search the forums for people having slow UART issues.

If the JTAG UART is indeed the problem, perhaps try a real UART, which only needs one wire for debug messages, and a USB-serial dongle. Some of those can reach pretty high bit rates.

Then you can independently measure printf() speed by printing to a buffer, and NOT sending it to the uart. Just use sprintf() and make sure the optimizer does not remove this "useless" code. You can measure CPU load on your Nios: when the CPU is idling waiting for FIFO data, set a pin LOW. When it is busy processing data, set that pin HIGH. Then probe the pin with a scope, and you'll see cpu load as duty cycle. Likewise you can measure accurately how long a sprintf() takes by toggling GPIO before and after, and probing it with a scope.

If printf() is the problem, you can use a faster implementation, or you could just send FIFO contents to the PC, and do the formatting on the PC.