34
$\begingroup$

An optimising compiler typically applies some set of rewrites to some intermediate representation of the program, replacing terms with other terms which are supposed to be equivalent but more efficient. For example, x * 8 may be rewritten as x << 3, or push x; push x may be rewritten as push x; dup.

In the most general case, systems of rewrite rules may not terminate: for example, if somebody had the great idea to also rewrite x << 3 as x * 8, then the compiler itself would loop infinitely (or perhaps overflow the stack), applying the two rules back and forth forever. Intuitively, "nobody would do that", because each rewrite rule should make the program "more efficient", and a program can't be made infinitely "more efficient", so there must reach a point at which no more rules can apply. That intuitive idea can in principle be made formal, but actually formalising it seems difficult; you'd need some mathematical measure of "how efficient" a given term is, and then show that each rewrite rule always improves that measure. But there are many real optimisations which don't necessarily respect simple measures (e.g. number of instructions).

So my question is: how do implementors of optimising compilers ensure that the compiler itself will always terminate? Are formal proofs practical (if so, how is "more efficient" formalised in practice?), or are other techniques used?

I'm especially interested in answers about how large, complex compilers like GCC and LLVM handle this; but answers based on experience from developing any optimising compiler, or on research, are also welcome.

$\endgroup$
9
  • 2
    $\begingroup$ A trivial fix would be to just keep a list of terms that have previously been considered, and check all proposed rewrites against this list. The same way that graph search algorithms still manage to terminate even when the graph contains cycles. $\endgroup$ Aug 26, 2023 at 3:02
  • 2
    $\begingroup$ GCC and LLVM both internally have heuristic stopping points - give up if the function has >N variables, or you've done more than M rewrites, etc, etc. It's nowhere near perfect and can lead to rough edges where a minor tweak to a function suddenly causes it to be terribly optimized, but it tends to work reasonably well in practice. $\endgroup$
    – TLW
    Aug 26, 2023 at 18:15
  • 1
    $\begingroup$ As a minor shift in the question, I'd point out that there are finite but still unacceptably expensive optimizations. For instance, operations which take exponential time with respect to the length of the code are unacceptable (unless bounded with additional logic). $\endgroup$
    – Cort Ammon
    Aug 26, 2023 at 19:13
  • 1
    $\begingroup$ Here's a fun bit of information: LLVM peephole optimizations like you describe often do not terminate! The ALIVE checker work identified some of these situations: ieeexplore.ieee.org/document/7886903 $\endgroup$
    – cody
    Aug 29, 2023 at 20:26
  • 1
    $\begingroup$ @cody Good find! Care to write up an answer about it? It looks like the paper directly addresses this question. $\endgroup$
    – kaya3
    Aug 29, 2023 at 20:48

6 Answers 6

30
$\begingroup$

The roots of the problem: cost models, and monotonicity

You're really getting at the heart of the problem when you say:

each rewrite rule should make the program "more efficient"

After all, why would you change the program in a way that makes it slower? But there are two problems:

  1. Cost models: how can we tell if something is faster or slower?

  2. Monotonicity: what if we need to make some changes that temporarily make the program slower, in order to eventually reach a global optimum?

That's the conceptual framework. Follows are some approaches for dealing with the problems in practice. These are complementary, not conflicting.

Timeouts

This might seem like a cop-out—and if you would get stuck in a loop without it, it actually is. But more broadly, optimisation is limited by a lack of computational resources, so, if appropriately designed, an optimiser should be able to make your code faster and faster the more time you give it (obviously with seriously diminishing returns); then, a timeout makes sense. You can also imagine an iterative optimiser, which gives a passable result immediately, so the user gets immediate feedback, but then continues optimising further in the background.

Edit: another answer draws a distinction between limiting wallclock time and limiting e.g. the number of rewrites performed. These are both reasonable directions to go in, depending on broader goals. In particular, going with the latter rather than the former provides a path to supporting reproducible builds; but the former can provide a more consistent user experience in contexts where that's not important.

Canonicalisation

One place these sorts of problems can start to creep in is due to redundancies in the ir—you mention x << 3 vs x * 8. But here's a question: is there really a need for the ir to support bitshifts? Arguably, taking advantage of bitshifts is solely an instruction selection problem, but not relevant to program analysis. So leave << out of the ir entirely—make it so that you couldn't say x << 3 even if you wanted to.

Similarly, simple algebraic properties like associativity and commutativity—is it a+b or b+a? a+(b+c) or (a+b)+c?—remove all question and represent + in your ir as a node with a variable number of dependencies that does not know which order they go in. Similarly, don't represent subtraction; only addition and negation.

One more example: scheduling. A traditional ir based on a basic-block control-flow-graph presumes a particular schedule—a particular instruction ordering—even though this information is not relevant for most optimisations prior to code generation. The sea of nodes representation (some exposition here iirc) destroys all unnecessary information about scheduling and ordering.

Abstract interpretation

Abstract interpretation is an approach to optimisation which treats it as an analysis problem moreso than a transformation problem. (Or, rather, abstract interpretation is an approach to analysis which works well for optimisation.) For instance, rather than replacing 2+3 with the constant 5, you would simply annotate it with the fact that its value is 5. Instead of removing dead code, you'd just mark it as dead. A full treatment is out of scope, but casting optimisations as abstract interpretations rather than transformations has a number of advantages, including that termination proofs are generally not hard. Recommended reading: combining analyses, combining optimisations, particularly chapters 2 and 3.

E-graphs

E-graphs have come into vogue recently. The basic idea of e-graphs is that the base nodes of the program ir, rather than simply being terms, will instead be sets of terms, which are all known to be equal. So for instance, rather than replacing x*8 with x<<3, you'd add x<<3 to a set of equivalent terms: {x*8, x<<3}. Then, at the end, once you've done all your optimisation, you extract some representative program, choosing one element from each set using some cost model. (Edit: Alexis's answer discusses these in more detail.) This helps get around the problem of monotonicity by admitting rewrites that make the program slower—since the ir is augmented with the slow term, instead of having to get rid of the fast term to make a place for the slow term, it doesn't cause problems, and if it ultimately helps you get to a faster term, great. May still have to be combined with a timeout. Recommended reading: https://egraphs-good.github.io/, and papers and videos linked therefrom.

To give an example of some of the synergies here: we could handle commutativity and associativity purely at the level of e-graphs: have a set containing {a+b, b+a}. But e-graphs have a tendency to grow very large, requiring a lot of computational resources (both space and time); so even if using e-graphs, it's a good idea to use the other approach I described for canonicalising associativity and commutativity, as that will increase the performance of the structure.

$\endgroup$
16
  • 1
    $\begingroup$ Re shl versus mul: this kind of works, but the flipside of lsr versus div doesn't for several reasons. First, x lsr 2 != x div 4 for negative values. Second, and admittedly this depends somewhat on your IR design, x lsr y typically produces some value (may be undef) for all values of y, whereas x div y is often trapping for y=0. This impedes later optimizations, as you can speculate x lsr y in places where you can't speculate x div y. You can define that your IR treats x div 0 == undef - but that just pushes the problem to instruction selection time. $\endgroup$
    – TLW
    Aug 26, 2023 at 18:10
  • $\begingroup$ It's a whole lot slower to have bunches and bunches of optimization passes calculate themselves if an input to a div is guaranteed to be a power of 2 (this is not so easy as it sounds, as said input may not be a constant power of 2...), then it is to do it once and store it in the operation itself. $\endgroup$
    – TLW
    Aug 26, 2023 at 18:12
  • 1
    $\begingroup$ "I don't know why it would be necessary to 'have bunches and bunches of optimization passes calculate themselves if an input to a div is guaranteed to be a power of 2'. " -> there are many optimizations that can be applied to bitshifts that cannot be applied to general divisions/multiplications (for instance, popcnt(a lsr b) <= popcnt(a)). Which means that if you are saying "don't have lsr in your IR at all; just use div" said optimizations have to figure out 'is this div actually a bitshift'. $\endgroup$
    – TLW
    Aug 26, 2023 at 20:45
  • 1
    $\begingroup$ And if you're not very careful what happens is you end up doing redundant calculations of "is this div actually a bitshift" all over the place... so you end up looking at it and going "this is doing redundant work, let's cache this"... and the most convenient way to cache the knowledge of "this div is actually a shift" is by, well, having a shift opcode. $\endgroup$
    – TLW
    Aug 26, 2023 at 20:47
  • 1
    $\begingroup$ Wouldn't you like to be able to speculate all divisions where the denominator is known to be nonzero? In general, it is useful to have analysis frameworks which can produce facts about terms—including, perhaps, that one is a power of two. And such a fact is useful generally, not just for this application. And I did mention that there are advantages to casting these problems as analyses rather than transformations. I do think that canonically transforming into right-shifts where possible would be harmless in most contexts, but I also don't think it would be particularly advantageous. $\endgroup$
    – Moonchild
    Aug 26, 2023 at 21:56
17
$\begingroup$

The existing answer is good and representative of the techniques currently used in most optimizing compilers. I’d like to add to that by mentioning equality saturation, a newer technique that seems quite promising.

The key idea behind equality saturation is to generalize the representation of expressions to represent the fixed point of applying a collection of rewritings. Given the example of x << 3 versus x * 8 from your question, an approach based on equality saturation would transform both expressions to a form that represents both versions at the same time. That is, the result of rewriting the term would be a sort of “superposition” of both x << 3 and x * 8.

By repeatedly applying rewritings to these “expression superpositions”, an optimizer can theoretically eventually produce a result that simultaneously represents all possible rewritings, and this is known as “saturation”. Since this represents the union of all possible rewritings, it is canonical, and there is no need to “bounce between” two different representations. After saturation been performed, a final code generation pass can transform the “expression superposition” into a concrete expression by using heuristics that attempt to select the best representation out of the set of known possibilities.

One immediate question is how to represent these “expression superpositions”. Though it would theoretically be possible to represent them directly as a set containing every version of the term, this would be prohibitively expensive due to the combinatorial explosion of potential rewritings. For that reason, equality saturation represents these superposition terms as graphs that permit sharing between possibilities with common structure. Since these graphs represent a set of equivalent terms, they are known as e-graphs.

Unfortunately, use of e-graphs alone does not fully mitigate the practical challenges of equality saturation. Some rewritings are difficult to efficiently encode into the e-graph structure, and some analyses are difficult to perform. The 2020 paper egg: Fast and Extensible Equality Saturation presents a more comprehensive design for practical application of equality saturation, realized in Rust as the egg library.

Equality saturation is a young technique under active research, so it remains to be seen to what extent it will supplant traditional, more ad-hoc rewriting techniques. Nevertheless, egg is the most immediately practical realization of the idea to date, and is already being applied in serious compiler projects like cranelift. Its principled approach provides many conceptual and practical simplifications, so I’d certainly call it an approach worth considering for any new optimizer.

$\endgroup$
5
  • 1
    $\begingroup$ "My code is being optimized by a quantum optimizer utilizing superpositions of nodes" :P $\endgroup$
    – Seggan
    Aug 25, 2023 at 22:28
  • $\begingroup$ How does this handle rewrites that can be applied infinitely? E.g. x -> x+0 -> x+0+0 -> ... $\endgroup$
    – TLW
    Aug 26, 2023 at 18:16
  • 2
    $\begingroup$ @TLW There's a nice talk on egg that goes into that here. Specifically, the speaker talks about how something like that is handled at this timestamp (though you might need to watch the beginning to fully understand that part). The brief answer is that such things are represented by cycles between e-classes of the e-graph. $\endgroup$ Aug 26, 2023 at 18:27
  • $\begingroup$ I guess my confusion lies in the following: Post tag machines are Turing-complete, and so finding the step at which an arbitrary Post tag machine has the shortest queue depth would imply solving the Halting problem - and yet it seems as though you could reduce a Post tag machine to an instance of compiler optimization via rewrite rules. $\endgroup$
    – TLW
    Aug 26, 2023 at 20:41
  • 1
    $\begingroup$ @TLW IIRC, the loop in the equality saturation algorithm is not guaranteed to halt and they use a timeout. I think it can always detect simple cycles like that one, though (assuming the term size doesn't cause it to time out). $\endgroup$ Aug 26, 2023 at 21:03
7
$\begingroup$

All that I've seen work with rule application limits, i.e. you give up after a certain number of steps. If you know how these limits work, you sometimes can create examples for programs that have an effective infinite execution time, but they work in practice. The same holds by the way for template applications.

In theory, one could imagine timeouts, but I haven't seen it in practice and would advise against it for a lot of reasons.

The idea with the measure will not work in practice because lots of algorithms have provably no measure that could be used. I'd expect that this statement is also true for templates. Besides, you'd have the practical problem that it would be outright complex to define a measure that works for a combination of transformations that are done together.

$\endgroup$
3
  • 1
    $\begingroup$ An interesting take on timeouts: the Rust compiler, as of 1.72, no longer limits the duration of compile-time expression evaluations, thereby allowing arbitrarily long computations at compile-time. Instead, after a certain time as elapsed, it will emit a warning that the computation is taking a long time, and then continue emitting those warnings with an exponential back-off, leaving it up to the user to interrupt when they are out of patience. $\endgroup$ Aug 27, 2023 at 15:14
  • $\begingroup$ How do you integrate such an approach into fully automated builds? The good thing about application limits in contrast to timeouts is that they are independent of a system's hardware or current load. Also, from my experience, they are good at detecting infinite application loops in cases, where small numbers should be reasonable. $\endgroup$
    – feldentm
    Aug 28, 2023 at 18:32
  • $\begingroup$ The problem about limits (aka "fuel") is that they can be so arbitrary. As you mentioned a minute change -- including upgrading the compiler -- and suddenly what was enough isn't... and trying to figure out the limit is always a pain. The warnings, instead, are just that - warnings. They do not trigger the termination of the build. Now, do mind that Rust 1.72 is fresh off the press (released a few days ago). Still, my expectation is that the intent is that a human will, during the course of development, judge the compile-time worth it; and CI will just run the computation until completion. $\endgroup$ Aug 28, 2023 at 19:27
6
$\begingroup$

As requested, I'm going to do my best to summarize the Termination-Checking for LLVM Peephole Optimizations paper, by Menendez and Nagarakatte.

The reality of compiler optimization staging is that it is a bit messy. Each pass or individual "peephole" optimization (so-called because they perform a local transformation on low-level code without much regard for context) usually improves performance, but the order in which they are run may affect effectiveness or termination. This order is usually determined by hand, based on messy heuristics.

Clang/LLVM peephole passes are typically run until saturation, that is a set of rules of the form $\text{source fragment pattern} \rightarrow \text{target fragment pattern}$ are repeatedly run until no rule applies. This requires preventing the exact situation from the original question, where a rewrite $a\rightarrow b$ occurs, and then another rule performs $b\rightarrow a$, which enables the first one to fire again, etc.

Things can be more subtle, where many rules have to interact to produce such non-termination. Typically this is avoided by the human having a notional concept of why a transformation is not "undone" by other transformations, or having side conditions on the applications of rules, e.g. $\%x \ll 3 \rightarrow \%x*8$ only if $\%x$ contains a signed integer and the converse only in the unsigned case (this is just notional, I don't actually know what the conditions are here).

Predictably, humans get this wrong, and the paper gives some examples of this occurring in the wild, with an example not much more complex than the shift one.

Ideally, one would "just" check mechanically termination of the combination of rules. There are many termination checking algorithms out there for such tasks (there's even a competition!), but this is a difficult task, and algorithms do not tend to scale well or handle bit-vectors easily, so the authors propose detecting non-termination at the cost of missing a few potential termination bugs.

They do this by trying to detect looping:

  1. Try to "guess" a sequence of abstract rules $a\rightarrow b \rightarrow \ldots\rightarrow a$
  2. Check whether this sequence is feasible, that is if the patterns can concretely be realized into an input program $a'$ which triggers these rewrites.

It's obvious that given rule $a\rightarrow b$ and $c\rightarrow d$, $b$ looks nothing alike $c$, (e.g. $b$ is $\mathtt{nand}\ X\ Y$ and $c$ is $X\ +\ Y$) then the rules cannot fire in succession, so these "mismatches" are pruned eagerly.

Then the more "semantic" conditions are checked, e.g. $C_2 = C_1\ \&\ C_2$ as in the paper example, which is easily seen to be satisfiable (take $C_2$ to be all zeroes, say).

I'll skip some additional details about how such loops are checked to be feasible, but the conclusion is that this approach did find a bunch of looping optimization sequences (184 of them!) within their tool, called alive2.

So what next? I imagine that these loops, if correctly identified (bugs in the alive2 tool are possible, and there is a manual step of translating the actual C++ optimization code to the alive2 optimization DSL) are being fixed by hand. I'd guess (complete speculation) that this is usually done by adding more conditions to avoid firing a rule in such a way that the loop is feasible, rather than removing or dramatically modifying rules. Generally mature systems are (correctly!) reluctant to make large changes. The paper doesn't say.

It would be an exciting challenge to see if termination tools can be actually put to task here. I think the main obstruction is expressing the side conditions, and the general user-friendliness of termination analysis, which is quite a bit behind that of SMT solvers, for instance.

$\endgroup$
4
$\begingroup$

Modern compilers don't have a clear separation between register allocation, code generation and peephole optimization anymore, because these things feed into each other.

For example, when you have complex addressing modes available that calculate a table access by bit-shifting an index register and adding the result to a base address register, and the data is accessed twice, there is a trade-off between calculating the address once and assigning it to a register, and calculating it twice.

If you want to find the optimal representation, you need to generate two different register allocations and see which one generates the fastest/shortest/... code. This depends on what else is inside the same function -- if many values are live, then repeating the calculation will win, as it saves the space and memory accesses for spilling a register, but if there are only few registers used, then using one to get a shorter representation and faster execution time for the accesses will be the better choice.

It doesn't stop there -- with modern CPUs disliking branches as much as they do, it is often beneficial to merge basic blocks, speculatively execute a branch and discard its result if it turns out the branch was not taken. This, of course, feeds back into the number of registers that are live at that point.

The solution here is to either have good heuristics on which representation will likely produce a good outcome and accept that it will not be optimal, or to present later stages with multiple alternatives, but in general decisions that have been taken are not revisited later except for a few that are obvious (for example, the assembler choosing a shorter encoding for a branch based on distance).

$\endgroup$
1
$\begingroup$

A very simple method is to look at the size of the code that you are trying to optimise, calculating some constant N based on the size, and stopping the optimization after N transformations have been made. The disadvantage if you do this carelessly is that you might have transformations that produce incorrect code unless another transformation is also made. For example if a compiler detects that x and y are never used simultaneously then it might change all uses of y to uses of x. It deletes the variable y (resulting in invalid code) and now it must immediately change all uses of y to uses of x to be back with valid code. So the check for >= N transformation can only be done when some primitive transformation is completed.

And I think you would make that value N large enough so that stopping optimisation because of it would be very rare, so rare that it is likely a bug in your compiler that produces a loop. The compiler might then want to produce a warning, asking you to send your code to the compiler developers so they can look for problems.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .