The Optimization Space

Dear LLVMers,

If I define the optimization space as the set of all the possible sequences of optimizations that produce a unique effect on some program, is this space infinitely large?

Let me explain: opt applies sequences of optimizations on programs. As an example, below we have two different sequences of optimizations, one with three passes, another with five:

$> opt -mem2reg -sccp -simplifycfg file.ll -S -o file.opt.ll
$> opt -mem2reg -sccp -simplifycfg -sccp -simplifycfg file.ll -S -o file.opt.ll

I would like to have an example of a kind of “pumping lemma” for optimizations: a sequence of passes “p0 … pk (pi … pj)^X”, where “p0 … pk” is fixed, and “pi … pj” repeats X times, so that for any X, we can find a program P such that X+1 optimizes P more than X. Notice that any combination of passes is ok.

I apologize if the question is weird, but we have been doing some theoretical research on the optimization space. I would like to know if it would make sense to saturate this space, e.g., to have a string Ox of passes that is long enough so that for any program, Ox always produces the best optimized version of that program.

Notice that I am assuming that the pool of available optimization passes is finite (ie., you can only draw passes from LLVM’s Analysis and Transform Passes — LLVM 15.0.0git documentation, for instance). I am, by no means, trying to break The Full-Employment Theorem for Compiler Writers (Full-employment theorem - Wikipedia) that appears in Appel’s book.

Kind regards,

Fernando

Oi Fernando!

(assuming you are talking about LLVM optimizations, not arbitrary code transformations)

It’s finite. LLVM has a bunch of thresholds in place to make sure things don’t keep growing forever. For example, running loop unrolling 10 times won’t unroll loops 10x more. There are also thresholds around function size/complexity.
Other optimizations rewrite code towards a canonical form, so it’s not the case that you can keep doing rewrites to it.
Finally, optimizations refine the code (i.e., they remove undefined behavior in a monotonic way). Eventually you would also run out of UB to refine.

I’m sure there are other arguments, but I leave you with those 3 thoughts: thresholds + canonicalization + refinement.

In a theoretical sense, the possible search space can be infinitely large. You can imagine an optimization pass that introduces an extra guard to a program, so that a program X effectively becomes if (!cond) return; X, and if this pass doesn’t check for a guard before introducing one, then running it twice produces if (!cond) return; if (!cond) return; X, and this can be reproduced ad infinitum.

In another theoretical sense, the search space is finite in practice, because the data structures that are used to store a program are finite in size and therefore the possible result space is finite (if exceptionally large in size).

In a more practical space, the search space is finite because the optimizations that might grow a function arbitrarily large tend to be guarded with various optimization limits, including quite frequently simply not doing something if it’s already been done (e.g., vectorization or loop unrolling). An optimization that allows unbounded growth would be considered a buggy optimization, but I would hesitate before declaring LLVM free of such buggy optimizations.

A final comment I would give: while the set of optimized results may ultimately be finite, the sequence of applying optimizations is definitely not monotonic: it’s not the case that taking on another optimization pass makes the result “more optimized” than the previous version. Additionally, I wouldn’t rely on an assumption that the result converges to a single fixed output–the result very well could result in a cycle between several programs as opposed to a single output fixed point.

Hi guys,

Thank you very much for the insightful answers. Something that made me think that maybe the space could be infinite was the observation that some optimizations appear more times in O2 than in O1. For instance, simplifycfg appears eight times in O1 and nine in O2. I thought that perhaps a combination of inline and sccp (not ipsccp!) could demonstrate that the space was infinite. Imagine the sequence “-mem2reg + (-inline -sccp)^X”. Now, for any X, build a program like:

static foo0(int a, int b) {

// int x = computations with a and b that make foo0 larger than the inline threshold

return x;

}

static foo1(int a, int b) {

return foo0(a, b);

}

static fooX(int a, int b) {

return foo{X-1}(a, b);

}

Imagine that you could inline foo0 into foo1, and then constant propagation would reduce foo0 enough to allow it to be inlined in foo2 if you could apply sccp again, and so forth. But, I could not make it work. Nevertheless, mind it that in this kind of experiment, we have an adversarial game: for each sequence S[N] of optimization with size N, the adversary is allowed to craft a new program P, such that S[N+1] optimizes P more than S[N].

Regards,

Fernando

For inlining LLVM doesn’t have thresholds to limit the number of times it is applied. So, in theory, you can apply it infinitely many times.
But, if the program terminates, inlining + constant folding must be a finite chain. Consecutive application of inlining amounts to unrolling a loop. That has to terminate eventually if the loop terminates.