Do you have good computer case air circulation? Remove one side and see if the GPU card continues to overheat.
When the GPU Card is overheating, is the GPU fan going at maximum?
Do you have all the PSU GPU Power cables connected if applicable?
Have you tried configuring the RX-580 using AMD Wattman? kingfish or pokester can assist you on this part.
Try using the latest RX 5xx driver : Radeon™ RX 580 Drivers & Support | AMD . The latest is from 04/03.2019. If it continues to overheat and the GPU fan is working at Maximum with good Computer case air circulation.
If your RX is still under Warranty I not sure if this next suggestion might void it or not. But you can always remove the GPU shroud (heatsink & Fan) and reapply thermal paste to the GPU and see if it runs cooler if nothing else works.
I have not run the latest driver myself, but I noticed my 580 running about 10 degrees hotter myself a few drivers back. Now I took my fan and heatsink off and put better thermal grease and pads on it and that did help, but I don't think my old grease and pads were the issue.
From day one with that card it would throttle at default settings and black screen in games without raising the power limit to 50 and using a custom fan curve. From what I have seen reported here and in other forums this is wide spread and approaching normal I think for these cards. They are not capable of running anywhere near their stated thermal limits at least not under load in a game.
I will share my settings in wattman and hope it helps the OP. I don't recommend you change the grease as I did unless you know it doesn't void the warranty on my XFX it does, and if you don't have the spare pads for the VRMS and memory as they typically break when you remove the sink.
Here are my settings for wattman, if that doesn't do the trick RMA the card or return to a previous driver that worked.