[dwohnitmok]

Rice's Theorem generalizes this to any implementation-independent attribute (i.e. properties of the idealized function on natural natural numbers a program represents). However, certain implementation-specific details such as run time (i.e. performance) are fair game. In particular it is quite simple to at least calculate lower bounds on run time. Simply choose a lower bound and then run the program and see if it halts before then.

[baddox]

If you can do that with your program then you can probably just precompute the actual result at build time. Many, if not most unexpected performance problems occur with unexpected or unconsidered inputs.

[dwohnitmok]

There are far less wasteful ways of calculating implementation-specific details. My "run until completion" was just an existence proof that general techniques exist. Things like symbolic execution, type systems, and other static analysis tools could in theory help here.

That being said I have personally yet to see non-toy static analysis tools for performance (although I suspect they exist at least in some limited fashion or operating in some constrained domains). This is probably due to the nature of certain pathological inputs and code paths as you point out.

There may nonetheless be hope if you guide the way users can write programs as a sibling comment points out.