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.
You need to provide more information as to what to show and when to show the image. but to start with here is post about hot you can show a "loading" message (gif) using php and JQuery.
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.