10
$\begingroup$

I have a compiler backend which targets high-level languages, by building an abstract syntax tree for the output and then using this to generate code ─ that is, this tree is really an intermediate representation (IR) rather than a representation of the original source code.

However, when the compiler initially creates this tree-based IR, it looks a bit silly; it often has statements like this:

if(true) {
    // other statements
}

while(condition) {
    // other statements
    break;
}

Therefore I have some rules for transforming the IR, in order to simplify these forms; for example, the if(true) part should be elided, and the while ... break pattern should be replaced with an if statement. However, these rules aren't exactly correct, because the "other statements" can include things like this:

if(true) {
    let x = 1;
    // ...
}
if(true) {
    let x = 2;
    // ...
}

while(condition) {
    // ...
    if(other_condition) { continue; }
    break;
}

If the transformations are applied to the above code, we will end up with two variables named x declared in the same scope (an error in some target languages), and the continue statement will apply to the next-outermost loop instead of the original while loop in this code (changing its meaning). A similar problem can occur when transforming a chain of if/else statements into a switch statement, as this changes the meaning of break statements in the original code.

I think this kind of problem occurs because certain statements violate the principle of compositionality ─ i.e. the meaning of the whole should be determined by the meaning of the parts, and the meaning of the parts shouldn't change if you move them around.

The obvious solution is to check first before applying each transformation, to make sure that the "other statements" don't include any "forbidden" sub-statements whose meaning would be changed by that specific transformation. However, this isn't scalable, because different sub-statements are "forbidden" for each transformation: I might have hundreds of transformations, and I can't guarantee that I'll think of every way that every transformation might go wrong.

Is there any other way to ensure that transformations like these won't change the program's meaning?

$\endgroup$
1
  • 1
    $\begingroup$ The first problem symbol definitions could be handled by adjusting the names of scoped symbols with a prefix or suffix that uniquely identifies their scope. The second problem could be handled by keeping flags for each loop indicating whether there had been any continue and/or break statements, or goto target labels, and disabling some optimizations if necessary based upon that. What other problems would you need to address? $\endgroup$
    – supercat
    Aug 7, 2023 at 20:51

4 Answers 4

7
$\begingroup$

ASTs are not that great at representing control-flow -- SSA & Basic Blocks would definitely make this easier -- but for simple transformations such as mentioned, a bit of tag propagation would be enough.

The idea is to tag each AST node with any control-flow effect that may escape it. Depending on what's available you'll want to surface things like:

  • Continue.
  • Break.
  • Return.
  • Throw.

Note: you may want more granularity, most notably, whether the effect is unconditional, or not. It helps for Dead Code Elimination.

A parent node typically gains the union of the effects of all its children nodes, with an exception for control-flow related nodes:

  • A try ... catch ... node may "suppress" the Throw effect.
  • A for, while, or loop node may "suppress" the Continue & Break effects.
  • A lambda node may "suppress" the Continue, Break, & Return effects.

You may still, though, wish to keep track of which effects are contained within the node, even if they're suppressed afterwards.

Note: in some languages, Continue/Break can be applied to outer loops, in which case you would need to track which loop they apply to, to know up to which point they propagate.

Let's pick both mentioned transformations:

the if (true) statement should be elided

An if (false) { ... } statement should be elided. An if (true) { ... } statement, should become just a block { ... }.

You can have a separate transformation to remove superfluous block delimiters, but as you noticed it's a bit more complicated due to shadowing/name conflicts, and possibly destructors or defer statements being invoked at the end of the scope.

and the while ... break pattern should be replaced with an if statement.

This transformation can only be performed if the inner body of the loop doesn't have the Continue effect for that loop.

The obvious solution is to check first before applying each transformations, to make sure that the "other statements" don't include any "forbidden" sub-statements whose meaning would be changed by that specific transformation. However, this isn't scalable, because different sub-statements are "forbidden" for each transformation: I might have hundreds of transformations, and I can't guarantee that I'll think of every way that every transformation might go wrong.

Welcome to the wonderful world of optimizers...

... unfortunately, there's no magic here. The Alive2 project for example attempts to identify incorrectly applied optimizations in LLVM, which is itself a confirmation that even LLVM developers struggle with this very problem.

Yes, you will have, for each transformation, to carefully think about what the exact pre-conditions are that ensure that the semantics of the code are preserved by the transformation. And any failure will result in a miscompilation.

The presence of the tags can help you in this endeavor, a bit, by acting as double-check: if you explicitly must indicate which effects may be added/removed by your transformation, you can verify that only those effects are indeed added/removed when executing the transformation on one particular input.

The general solutions for verifying transformations that I know of are:

  • Formal Verification: the golden standard, though translation or verification errors may still occur. See CompCert1.
  • Symbolic Verification: the other golden standard, proving the transformation correct for all input programs satisfying its pre-conditions. Generally intractable.
  • Partial Symbolic Verification see Cranelift Register Allocator: proving the actual transformation of this one input program into this one output program correct. Actually tractable, though adds a compile-time cost to each run of the compiler.
  • Differential Fuzzing: throw many sets of input values at the input program and output program of the transformation, for many inputs, and record any difference in output. Done offline, compute-intensive, and suffer from "generator blindness" in that the generator may not generate a certain subset of valid programs.
  • Partial Differential Fuzzing: applies the fuzzing on one particular input program & output program. I suppose after compilation ends?

And it's very much an unsolved problem...

1 CompCert has very few optimizations for now, however the team has announced that with the foundations correct after a decade of effots they were looking forward to adding some... formally verifying them one at a time.

Is there any other way to ensure that transformations like these won't change the program's meaning?

Partially.

Total solutions tend to be intractable, and tractable solutions tend to be partial.

Partial Symbolic Verification is my darling here. It is actually tractable, and yet manages to be total for the program being compiled. That is, instead of proving the compiler correct, it proves the result of a particular compilation correct. A weaker statement, but a sufficient statement to give piece of mind to the user.

Also, Partial Symbolic Verification is very much amenable to fuzzing: throw a program generator at it (or a program fragment generator), and check if any generated program breaks any transformation. A few bugs were surfaced in the Cranelift Register Allocator with this technique, and patched before the register allocator even went live.

$\endgroup$
13
$\begingroup$

The solution to this is to use a different choice of IR that doesn’t suffer from these problems (or at least makes the invariants easier to maintain). For imperative languages, an almost universal choice of IR is static single assignment form (SSA), which addresses the issues mentioned in your question. Modern compilers generally represent SSA using a so-called “sea of nodes”, which makes transformations particularly easy to write.

Therefore I have some rules for transforming the IR, in order to simplify these forms; for example, the if(true) statement should be elided, and the while ... break pattern should be replaced with an if statement.

SSA “boils away” the distinctions between these different constructions by translating all control features to a regularized structure. Jumps always occur at the end of basic blocks.

If the transformations are applied to the above code, we will end up with two variables named x declared in the same scope (an error in the target language)

The way SSA prevents this from happening is in its name: all variables are unique and are assigned exactly once.


One reason that you might not want to use SSA is if you’re translating to a human-readable language and want to output code that is comprehensible to humans. Personally, I think this is often a futile goal, but I understand that it is one many people have.

In that case, you may wish to use a different IR that preserves a little more structure, such as A-normal form (ANF). Alternatively, you could use an enhanced version of SSA that is annotated with additional information that allows reconstructing some of the source structure in the final result.

Regardless of what you do, the advantages of using a simple intermediate language are too big to pass up. If your compiler does any nontrivial transformations at all, you want to be using an IR that makes those transformations easier to express safely.

$\endgroup$
2
  • 1
    $\begingroup$ As I understand, SSA and similar lower-level representations are common for compiling from imperative languages, but is SSA really suitable for compiling to a high-level imperative language? For example, if you have basic blocks and jumps in your IR then you will have to rebuild structured control-flow later. $\endgroup$
    – kaya3
    Aug 5, 2023 at 18:22
  • 1
    $\begingroup$ @kaya3-supportthestrike Depends on the language. Keep in mind that every basic block can always be represented as a function. If you’re compiling to a language that supports tail calls, you can generate things quite directly. If it doesn’t, you can always trampoline in cases where you can’t reconstruct control flow. $\endgroup$
    – Alexis King
    Aug 5, 2023 at 22:55
3
$\begingroup$

From my experience, your fundamental error is that you are trying to represent a general graph structure with a tree.

For an internal representation at that level, I'd suggest using a graph of basic blocks. If you have an implementation language with OOP, I'd suggest splitting the IR instructions into ones that can branch and ones that cannot.

Try to have instructions that are as simple as possible. For instance, you can represent if/else by switch { case true {} default {} }. This might look very odd at first glance. But, it simplifies your compiler a lot.

Formulate your simplifications as graph transformations rather then looking at examples and handling examples. For instance, switch (true) case true bb1 default bb2 can be replaced by goto bb1. Use a hell lot of example to check your assumptions on these rules because you will likely come up with some rules that do not work if you add things like break and continue to your loops.

Use dominators for your transformations. If you are not, they are most likely not correct or inefficient.

Finally, add IDs to all entities and make sure all transformations are deterministic. This last rule is required to allow you to debug your transformations for non-trivial cases. You should also write some DOT dumping code that helps you visualize your current status.

$\endgroup$
5
  • 1
    $\begingroup$ I don't find this answer very helpful. The goal is to compile to high-level languages, which have tree-structured syntax ─ so going via a lower-level representation with basic blocks is possible but you will need to rebuild structured control-flow eventually, and a tree-IR will still be needed for code generation. I don't know what you mean by "looking at examples and handling examples", the examples I included in the question are for the purpose of explaining the question. I don't know how adding IDs would ensure determinism but all of my transformations are necessarily deterministic anyway. $\endgroup$
    – kaya3
    Aug 6, 2023 at 14:24
  • $\begingroup$ You can keep the pointers to the original tree-IR if you think that this might help, but the transformation you asked for is fundamentally a graph-transformation. You can insist to use the wrong data structures, but this will only cause you to get the overall transformation wrong at the end. $\endgroup$
    – feldentm
    Aug 7, 2023 at 16:09
  • 1
    $\begingroup$ The point is that I am not trying to represent a graph structure with a tree, I am trying to represent a tree structure ─ i.e. syntax in the targeted high-level imperative language ─ with a tree. Using a control-flow graph instead of that is not an option, because an arbitrary control-flow graph can't be used to generate code in the target language; it does not serve the same purpose as it does not represent the same thing. If you were just proposing to use a CFG as an additional intermediate representation before generating the tree-IR from it, then your answer should be worded differently. $\endgroup$
    – kaya3
    Aug 7, 2023 at 16:15
  • $\begingroup$ I understood what you are thinking, but this is exactly why your approach won't work. The CFG is a graph. Also, based on your problem statement, the target language will be able to represent arbitrary result, but they might not be pretty. I'm not sure if I should provide a second answer essentially explaining why you shouldn't do it at all. It sounds a bit like the best approach is letting the compiler of the target language do the optimizations. Is there an unmentioned readability requirement? $\endgroup$
    – feldentm
    Aug 8, 2023 at 7:02
  • $\begingroup$ If you are even thinking about writing an answer saying I shouldn't do it at all, then I will save you the trouble ─ don't bother, such an answer is guaranteed to be useless to me. $\endgroup$
    – kaya3
    Aug 8, 2023 at 11:29
0
$\begingroup$

In an AST every non-toplevel statement is a child of another statement (block-statement, conditional-statement, etc.).

so to discover which loop-control statement a break or continue belongs to you walk up the ancestors until you find an applicable statement (for or while) or a invalid node (a function statement).

AST* discover_parent_loop(AST* statement){
    if(statement==null)return null
    AST* result = statement->parent;

    while(result){
        if(result->type == AST_function) return null; //no parent loop
        if(result->type == AST_while) return statement; //parent loop is while
        if(result->type == AST_for) return statement; //parent loop is for
        result = result->parent;
    }
    return null;
} 

When iterating over the AST you can instead put the containing loop (and loop names for labeled breaks) as part of the scope stack which lets you do a similar thing but doesn't require a parent pointer in your AST node structure.

$\endgroup$
1
  • $\begingroup$ I'm not sure how this answers the question. $\endgroup$
    – kaya3
    Aug 7, 2023 at 13:02

You must log in to answer this question.

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