I tried a few things, but wasn't really able to nail this down.
I downgraded to mesa 11.2 to see if that helps, but it does not.

However, today I had plasmashell freezing after unlocking the screen.
Only plasmashell froze, everything else kept working as expected.

I contacted Martin on IRC and he thought it might be related to this.
I'll attach the log from the conversation as well as the backtrace.

He might be right, because around the time when this happened, I get these
messages in dmesg:
[88765.431890] [drm:amdgpu_crtc_page_flip] *ERROR* failed to reserve new rbo
buffer before flip
[88765.436865] [drm:amdgpu_crtc_page_flip] *ERROR* failed to reserve new rbo
buffer before flip
[88765.441940] [drm:amdgpu_crtc_page_flip] *ERROR* failed to reserve new rbo
buffer before flip
[88765.446861] [drm:amdgpu_crtc_page_flip] *ERROR* failed to reserve new rbo
buffer before flip
[88765.451865] [drm:amdgpu_crtc_page_flip] *ERROR* failed to reserve new rbo
buffer before flip
[88765.456903] [drm:amdgpu_crtc_page_flip] *ERROR* failed to reserve new rbo
buffer before flip
[89579.510005] [drm:amdgpu_crtc_page_flip] *ERROR* failed to reserve new rbo
buffer before flip
[89579.514998] [drm:amdgpu_crtc_page_flip] *ERROR* failed to reserve new rbo
buffer before flip
[89579.520053] [drm:amdgpu_crtc_page_flip] *ERROR* failed to reserve new rbo
buffer before flip
[89579.525158] [drm:amdgpu_crtc_page_flip] *ERROR* failed to reserve new rbo
buffer before flip
[113833.139104] [drm:amdgpu_atombios_dp_link_train] *ERROR* displayport link
status failed
[113833.139117] [drm:amdgpu_atombios_dp_link_train] *ERROR* clock recovery
failed
[113833.361471] [drm:amdgpu_atombios_dp_link_train] *ERROR* displayport link
status failed
[113833.361484] [drm:amdgpu_atombios_dp_link_train] *ERROR* clock recovery
failed
[113836.962993] [drm:amdgpu_crtc_page_flip] *ERROR* failed to get vblank before
flip