Тут как сказать... Если маленький код очень плохо сидит на кэше и весь горячий, то он прямо напрашивается на серьёзную оптимизацию.
А вот для холодного большого кода наоборот можно пожертвовать качеством оптимизаций для большей части кода, так как это в общем execution time роли особо не сыграет.
Но это всё граничные случаи. Имхо по-хорошему действительно надо настоящие межпроцедурные оптимизации делать линейной или квадратичной сложности. Ну или свести различными способами сложность хотя бы к чему-то меньше куба.