There are some similarities with Windaria
The mountainous kingdom of Paro and the coastal city-state of Itha had been at peace for over a century. They would have remained that way but for the ambitions of Paro's power-hungry king. Paro invaded Itha, despite the love between Jill, Paro's prince, and Ahanas, Itha's princess. Caught between duty and emotion,...
You're most likely thinking of the Windaria movie, based on a novel of the same name, by Keisuke Fujikawa.
In the movie, when people die they turn into red light shaped like birds and fly to an airship in the sky over the ocean.
It might also go by the name Legend of Fabulous Battle Windaria and Once Upon a Time, Windaria. The English version by Harmony ...
Stone legends are indeed pretty common just as TurkeyFried stated. Most of these are based on Loyalty towards a person ( most common in anime waiting for a loved one)
It is said that the petrifaction version originate's from Vietnam
Hòn Vọng Phu (Statue of Husband Waiting)
But now a days in tv shows and such they give their own meaning to it and ...
Stone legends can be found in various cultures, not just Japan. For example, Australia has The Three Sisters, Puerto Rico has The Stone Dog and you can even find this trope in Inca culture. Someone's love remaining eternal through petrifaction is just a common (and effective) storytelling trope.