GCC: Difference between -O3 and -Os
The GCC documentation describes what these options do very explicitly.
-O3 tries to optimize code very heavily for performance. It includes all of the optimizations -O2 includes, plus some more.
-Os, on the other hand, instructs GCC to "optimize for size." It enables all -O2 optimizations which do not increase the size of the executable, and then it also toggles some optimization flags to further reduce executable size.
Note that I've been deliberately a bit vague with my descriptions - read the GCC documentation for a more in-depth discussion of exactly which flags are enabled for either optimization level.
I believe the -O* optimization levels are just that - mutually exclusive, distinct levels of optimization. It doesn't really make sense to mix them, since two levels will enable or leave out flags that the other one intentionally leaves out or enables (respectively). If you want to mix and match (you probably don't actually want to do this, unless you have a really good reason to want a specific set of flags), you are best off reading the documentation and mixing and matching the flags each level enables by hand.
I think I'll also link this article from the Gentoo Linux Wiki, which talks about optimization flags as they relate to building the packages for the operating system. Obviously not all of this is applicable, but it still contains some interesting information - for one:
Compiling with -O3 is not a guaranteed way to improve performance, and in fact in many cases can slow down a system due to larger binaries and increased memory usage. -O3 is also known to break several packages. Therefore, using -O3 is not recommended.
According to that article, -O2 is, most of the time, "as good as" -O3, and is safer to use, regarding broken executable output.
I suggest to read GCC documentation. -O3 is for getting a fast running code (even at the expense of some code bloat), while -Os is optimizing for size of the generated code.
There are tons of other (obscure) GCC optimization flags (e.g. -fgcse-sm) many of which are not enabled even at -O3.
You might perhaps be also interested by -flto (for Link-Time Optimization) to be used, in addition of e.g. -O3 or -Os, both at compile time and at link time. Then see also this answer.
At last, take care to use the latest version of GCC (currently 4.8 at end of 2013), because GCC is improving significantly its optimizations.
You might want to also use -mtune=native (at least for x86).
And you might even write your own optimization pass, specific to your own particular libraries and APIs, perhaps using MELT plugin.
As CmdrMoozy answered you might prefer using -O2 over -O3 (but notice that recent GCC versions have improved a lot their -O3, so the Gentoo citation -recommending against -O3 and in favor of -O2 is becoming less relevant.).
Also, as this SlashDot-ed Stack paper (by Xi Wang, Nickolai Zeldovich, M. Frans Kaashoek, and Armando Solar-Lezama) shows, many programs are not entirely C standard compliant and are not happy (and behave incorrectly) when some valid optimizations are done. Undefined behavior is a tricky subject.
BTW, notice that using -O3 usually makes your compilation time much longer, and brings often (but not always) at most a few percent more performance than -O2 or even -O1.... (it is even worse with -flto). This is why I rarely use it.
It depends. Do you need to optimize speed or size?
-O3
Optimize yet more. -O3 turns on all optimizations specified by -O2 and also turns on the -finline-functions, -funswitch-loops, -fpredictive-commoning, -fgcse-after-reload, -ftree-loop-vectorize, -ftree-slp-vectorize, -fvect-cost-model, -ftree-partial-pre and -fipa-cp-clone options.-O0
Reduce compilation time and make debugging produce the expected results. This is the default.-Os
Optimize for size. -Os enables all -O2 optimizations that do not typically increase code size. It also performs further optimizations designed to reduce code size.
-Os Disables the following optimization flags:
-falign-functions-falign-jumps-falign-loops-falign-labels-freorder-blocks-freorder-blocks-and-partition-fprefetch-loop-arrays
Actually, -O is a shorthand for a long list of independent optimizations. If you don't know what you need, just go for -O3.