How do I create a loading overlay(with loading gif) while php script runs and returns data
PHP is a server-side language and what you're looking for is something that interacts with the browser on the clientside.
You're probably best of using a solution involving AJAX - for example using Jquery:
When the user loads the page, make an AJAX call that runs your script. Show a div that displays your 'loading' gif. When the AJAX call finishes, hide the div with your 'loading' gif.
Use AJAX-like technologies and 2 php-scripts. The first should output only "loading..." div and start of AJAX-request to the second one, which returns the full content of your page.
PS: actually, I'm not sure if you understand, that "loading" exists on client-side browser as php's output, but php script runs on server before your browser gets it's output... read more about how HTTP and web servers work - this knowlege is quite neccesary for any good web-developer.