I am confirming this affects me as well, installing the kernel from stretch-backports, using an AMD RX 580.
The workaround is to clone https://git.kernel.org/pub/scm/linux/kernel/ git/firmware/linux-firmware.git/, and copy the missing files to their proper place using rsync -a -v --ignore-existing source /lib/firmware/amdgpu/. After that, the system boots fine. I am hoping the appropriate firmware files will be added soon in backports.
