Well didn't it back itself up within itunes?
when ever I sync my phone, it always creates a backup.
If there's no backup and you installed the new OS, then everything is gone. Its not deleted, but removed from the flash ram. There's no mechanism on the iPhone to use some sort of trash basket. When you install an OS, on the phone it wipes everything out.
Its like formatting a hard drive and installing a new version of OSX. you lose everything unless you have a backup