It seems like a big part of all these strategies is making sure the checks for the optimizations (checking if they're possible, checking if they're done) don't take more time than the optimizations save.
Or could there be a way to alter the execution graph so that once you add in the optimization, you never have to check if it's there?
You can't really check that, you can only hope your heuristics are right. You don't know in advance how many times a method will be executed and thus how much optimization budget is worth it. If you boot up a java application that runs for months and handles tons of traffic then you could theoretically justify many minutes of CPU cycles for optimization.
And that's not all that makes JITs complex. Some also do speculative optimizations that require guards and deoptimization points so they can fallback and recompile if those assumptions are violated. If the language has a garbage collector then the GC and JITs have to cooperate for ideal performance.
One of the things V8 does is store "field dependencies" -- a list of optimized code attached to fields that is invalidated if that field is modified in a certain way. The optimized code is known to only access that field in a certain way, thus doesn't need to check it, so this only slows down unoptimized paths (and only on their slow paths too, since even unoptimized code has fast paths for known access patterns thanks to inline caches). Comes with a memory/generality cost though, so this isn't used for every type of check.