Skip to main content
Software Engineering

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

9
  • 9
    Being generally undecidable isn't actually important. That's about a function containing code that would make it not pure, and deciding whether that code ever gets executed. But that is such a rare case... What you need is just to check whether there is anything that would make the function impure. Functions that are sometimes pure, sometimes not, are a tiny minority. Commented Jan 31, 2021 at 18:50
  • 26
    @gnasher729: It is true that compilers do undecidable things all the time. Escape Analysis is undecidable, but compilers do it nonetheless. You just have to live with the fact that sometimes the answer is "I don't know", which in this case means that you cannot perform the optimization because you risk crashing the program. Devirtualization is another example: undecidable in the general case, but implemented in many C++ compilers as an optimization. However, devirtualization fails often enough that C++ programmers are taught to avoid virtual functions. Dead code detection: the Java Language … Commented Jan 31, 2021 at 19:36
  • 8
    … Specification specifies a specific subset of cases where it is performed, and the language is specifically designed to allow it. The rules about definite assignment, "effectively final", etc. in C++, Java, C# and co. are there precisely because liveness in general is undecidable. And so on. In general, you need specific restrictions in the language and/or help from the programmer to make it work often enough that it is worth it. For concurrency, specifically, I feel that having the language be explicitly concurrent is much easier than bolting it on as a compiler optimization. Commented Jan 31, 2021 at 19:39
  • 4
    However, I may also be misunderstanding the OP's question here. I am assuming "given an existing language, not specially designed for concurrency, can I automatically discover potential concurrency as a compiler optimization?" If we are allowed to assume a language that is specifically designed for automatic concurrency, that's a whole different ballgame. Then we end up with something like Fortress, data flow languages, Occam-π, APL, vector languages, etc. Commented Jan 31, 2021 at 19:42
  • 1
    Data-parallelism in a single long-running loop can be exploited by compilers by auto-magically creating thread-level parallelism as well as auto-vectorizing with SIMD. OpenMP #pragma omp parallel ... hints the compiler to do this, and gcc -ftree-parallelize-loops=4 will even do that on non-hinted loop. Maybe not a good idea without profile-guided optimization to find actually hot loops, though, because of the high overhead! C loop optimization help for final assignment (with compiler optimization disabled) shows it doing a poor job. (@Ben) Commented Feb 1, 2021 at 23:20