1

I just asked about the Polyhedral Model, and have looked into other compiler optimizations (Loop unrolling, Constant folding and propagation, Dead code elimination etc.).

But I haven't seen anything on entire program transformation/optimization. Wondering if there is anything on that topic, any materials or techniques. An example would be taking your whole program and reordering the function calls and variable uses at the scale of the whole program to make it more optimized (as opposed to at the scale of individual loops or basic blocks).

I'm specifically wondering how this optimizer would know to replace a high-level function (referencing multiple other functions/high-level functions) could be replaced by another function. Same with a set of these functions. The optimizer would have to somehow know the intent of the programmer it seems, but who knows maybe they've figured out a way.

Improve this question
3
  • 1
    Replacing a function f1 by another function f2 can only work if the optimizer knows f1 and f2 are semantically equivalent. This may be detected automatically if f1 and f2 are essentially containing the same instructions, or at least equivalent instructions. But in this case, I fail to see the point of this "whole program" optimization approach, f2 is just a (locally) optimized version of f1. Or do you think of a case where f2 contains a completely different algorithm than f1, but still has the same semantics, the same side effects etc?
    – Doc Brown
    Commented May 1, 2018 at 6:27
  • The term "whole program optimization" usually means that the optimizer looks beyond the scope of a single source/object file for performing the optimizations. Which optimizations are performed is not that different.
    – Bart van Ingen Schenau
    Commented May 1, 2018 at 6:29
  • @DocBrown yes I'm thinking a totally different function but it has the same overall effect.
    – Lance Pollard
    Commented May 1, 2018 at 6:51

2 Answers 2

Reset to default
7

Whole program optimization includes (practically, at least for C or C++ and similar languages) inlining across translation units, so is sometimes (improperly) called link-time optimization (LTO), but still is done by the compiler also running during the linking step. BTW, LTO existed at least since the 1990s (and probably even in the mainframe time, 1970s).

In practice, recent compilers such as GCC or Clang are able to do that, e.g. with the -flto optimization flag (to be passed, with some other flag like -O2, both at compile and at link time to gcc, clang, g++, clang++ etc...). That works essentially by almost duplicating the optimization effort: for every translation unit, the internal representation of the source code (e.g. some kind of GIMPLE for GCC) is also generated in the object files. At "link" time all these representations are optimized together again. So the overall compilation time (including "link-time optimization" which happens in the compiler...) is nearly doubled in practice.

However, link-time optimization is usually not worth the effort, since in practice you double the build time to gain only a few percents of performance at runtime of the compiled program (of course, there are exceptions to this rule-of-thumb observation).

Compilers for languages having an explicit notion of modules (and reifying their representation in some kind of data), or for homoiconic languages, may also whole program optimize in a different way (by still having a representation of the code of the entire program). Look into Stalin or PolyML (or even Ocaml or Go or SBCL sometimes) or CAIA or SELF for examples. Even the C++20 standard should have modules.

(I don't understand why researchers named their prototype software "Stalin". That name is so disgusting to me that I am psychologically unable to try that compiler. For future academics: please name your software carefully!)

Improve this answer
2
  • 3
    I just took a look at the link for the compiler you dislike the name of. From my reading of that page they deliberately chose that name in order to satisfy their idea of a joke - in other words they carefully chose the name. A classic example of being tone deaf.
    – Peter M
    Commented May 1, 2018 at 12:08
  • hybrid lto object files are becoming rare, thus avoiding the duplicated work.
    – Deduplicator
    Commented Jun 19, 2020 at 16:03
1

Whole-Program optimizations are optimizations that are done across method boundary (I'm talking Java/c#, not c/c++). An example would be the Advanced-Technology Whole-Program Optimization used in libminecraft, the high-performance pirated Minecraft version. It's an inline-then-optimize approach that works by inlining methods regardless of their size and then performing peephole optimizations. The inlining step bloats method sizes by replacing method invocations with method bodies so more peephole optimizations can be performed, which is nearly the equivalent of a static analysis of the entire program.

The only safe Whole-Program optimization technique is inlining. Most Whole-Program optimization techniques your compiler is offering you are just variants of inlining. Some compilers only do inlining as part of the Whole-Program optimization but with different aggressiveness levels favoring speed/size. If the compiler give you any more aggressive optimizations, you may risk turning your program into an unsafe Boeing 737 MAX 8 designed to crash. Also, some compilers even do inlining after the peephole optimization step, which is not as helpful as it would be if it is performed before the peephole optimization step.

Improve this answer
5
  • 1
    Whole program optimizations is possible on C or C++ code with both GCC and Clang compilers
    – Basile Starynkevitch
    Commented Jun 21, 2020 at 5:58
  • 2
    The only safe Whole-Program optimization technique is inlining [citation needed] -- one useful optimization that needs whole-program scope is escape analysis, which can be used in languages that do not provide a way of specifying that an object's lifespan is limited to the function creating it (eg Java/C#/Swift) to determine whether it is safe to allocate an object on the stack rather than the heap. As far as I'm aware, common implementations of such languages use this optimization on a whole program basis without causing catastrophic issues. Do you have evidence to the contrary?
    – occipita
    Commented Jun 23, 2020 at 3:46
  • 4
    I'd regard in-lining, the way some compilers perform it, as less safe than some other approaches to whole-program optimization because the authors of the C Standard saw no need to include a way of specifying semantics that would naturally be implied by calls across compilation unit boundaries. For example, if code places an some data into a buffer and passes its address to an external function that writes that to a volatile-qualified DMA controller register, the cross-module call would prevent the compiler from deferring the store of the object until after the function call, but...
    – supercat
    Commented Aug 6, 2020 at 15:31
  • 4
    ...an aggressive whole-program optimizer might decide that because the function doesn't directly access the storage in question, it can reorder operations to it across the function call. Some other approaches to whole-program optimization are much safer because they avoid making any changes to actions requested by the programmer. A build system, for example, might use a name-mangling or other convention for functions that are guaranteed to leave various registers undisturbed, and then instead of saving registers across a function call, invoke the function with a name that...
    – supercat
    Commented Aug 6, 2020 at 15:36
  • 4
    ...would guarantee that those registers won't be altered. If most callers of a function would need the registers to be preserved, all callers could use a version that preserves registers. If relatively few would, calls to the function by those which need the registers preserved could save the values themselves and then use the entry point that wouldn't guarantee such behavior. Systems for cross-module register optimizations are often a bit trickier than that, but the they can save code without affecting program semantics.
    – supercat
    Commented Aug 6, 2020 at 15:39

Not the answer you're looking for? Browse other questions tagged or ask your own question.