How to get OpenCL to work on an AMD GPU with Ubuntu 16.04?

I have a PC with a:

VGA compatible controller [0300]: Advanced Micro Devices, Inc. [AMD/ATI] Venus XT [Radeon HD 8870M / R9 M270X/M370X] [1002:6821] (rev ff) (prog-if ff)

How can I get OpenCL to work on it? I'm not offered a proprietary driver in the Software sources tool, and AFAIK it isn't supported on 16.04 anymore.

clinfo currently lists zero devices.

When clinfo shows "Number of platforms 0", you probably did not installed an ICD which is needed to use OpenCL-Products (like an Graphics card from AMD).

Use "sudo apt install mesa-opencl-icd" for a possible solution.