| https://books.google.com/books?id=u38h_fV3UqgC&pg=PA173&lpg=... See also the citations to it, http://dl.acm.org/citation.cfm?id=340757 See also
https://www.researchgate.net/publication/221200232_Algorithm... http://ieeexplore.ieee.org/abstract/document/5447280/ http://perso.ens-lyon.fr/christophe.alias/pub/alias_thesis.p... https://www.ideals.illinois.edu/handle/2142/45394 http://gac.udc.es/~juan/papers/toplas.pdf and ... As the last paper says:
"e. The development of techniques for automatic recognition of computational kernels such as
inductions, reductions and array recurrences has been an intensive research area in the scope of
compiler technology during the 90’s." If you want a simpler example, all of your compilers are usually replacing your divisions by a different algorithm :)
It replaces your sum reductions, recurrences, etc. Seriously, these are really really old compiler problems.
Compilers do the parts people care about, and will often replace the algorithms that are usually "slow", like math, or have well defined semantics that won't cause api breakage for you. Compilers replace memcpy, printf, etc, all the time. If you want a compiler that replaces your much higher level algorithms, as the papers show, they have existed over the years. When the research papers are scanned copies, it's old tech :P But the truth is that, for example, a lot of common languagers (C++, etc) are not good languages for that. It's not about compiler technology. I can teach a compiler to recognize your sorts, for example, pretty easily. But proving i can legally change it and not destroy the programming semantics is often literally not possible. You'd have to tell me "it's okay". It's only stuff that is well specified enough (like standard library functions) that i could do. Think about trying to swap STL data structures for some code. We can recognize when it is possible. We can even determine when it is profitable, and do it.
Usually, the problem is it destroys the API you've built to do so (IE you pass it around as an argument), etc.
and in the end, it's usually not worth it for those languages to do it in the compiler. It's infinitely more effective to do something like http://lists.llvm.org/pipermail/llvm-dev/2016-April/098355.h... and tell people "you should switch this datastructure".
At least, for these languages. But hey, if you want the compiler to duplicate and inline all the functions and swap out the algorithms, it could! It's just that, for example, C and C++ are not languages that lends itself to compilers doing it, it's one that lends itself to telling humans to do it (or at least, asking them if they want it done and then doing it) This is obviously all easier in functional languages, and they actually have a fairly rich history of doing algorithm replacement :) |
No they're not. I don't actually specify the algorithm to be used for division, I just write "/" (usually), and so the compiler (or runtime or whoever) is certainly free to implement that "high level" specification (I want these two quantities divided) in any way it sees fit.