I would say it is undecidable, to be honest. For example
if(undecidable_function())
return lots_of_code();
else
return 0;
Things like dead-code removal are a pretty standard for modern optimizing compilers!
Purity analysis is indeed trivially decidable, if you limit yourself to "probably always pure", not "pure when executed on a Tuesday". It boils down to "is this function calling only pure functions and not using any of the impure operators?". The trouble comes with dynamic languages where you usually don't know shit about a function's arguments, though. In that case you need a control flow Analysis of the whole program.
You'd be surprised how much code this doesn't apply to.
But the true question is: can an algorithm figure that out?
Computer programs can have remarkably simple semantics.
All compilers do is analyse dependencies (or a lack of) and do things to exploit them or their absence. The algorithms that do that are inherently not able to solve the halting problem, but that clearly doesn't hurt or we wouldn't have processors at all.
You can all kinds of useful stuff without Turing completeness - eBPF code for example is guaranteed to terminate.
It's not that it's impossible, but that 1% (or 5%, 10%, ???% depending on how the project is structured and whether it uses a lot of side-effects or dynamic properties) can be enough make your program crash if the assumption turns out to be wrong.
Another example that you could go for, is can you determine whether a property of an object is used or not. If you have a language like JavaScript where you can do `object[propertyName]`, that turns out to be very hard. In a pure functional language, that is comparatively pretty straightforward to detect.
Notably this is largely a problem with JavaScript and Ruby. There are plenty of non-functional languages where we don't need to havoc wildly to handle ordinary program behavior.
I've seen some very large companies abuse JS object proxies so that code is nearly impossible to follow even with the best IDEs and someone who's excellent at grepping.