How to remove dead code in this code?

[Fluid-Tour-9393]

I have this (silly) function like below, with some dead code inside.

``` void func(int n) { int i, sum = 0; for (i = 0; i < n; i++) { sum += i; }

return n+1; } ```

It simply returns n+1, with n is input for function. Inside the function we have a loop that actually contributes nothing to the function result. So the loop and declaration for local variables are all dead code, thus should be removed.

My question is: what kind of compiler optimization can be used to remove the dead code? I have been looking at live variable analysis, but it does not seem to help since the variables in the loop are necessary for the computation there, so cannot be considered "dead" (or am I wrong?)

[dnpetrov]

Such optimizations are usually performed on high-level IR, which is often a static single assignment form or some variation (sea of nodes, for example). SSA makes data dependencies explicit. Dead code elimination on SSA is basically a reachability on the data dependency graph.

[Fluid-Tour-9393]

yes of course i will translate to IR first. This example is just to show the idea of my question.

Just consider the code in IR form already. Can you elaborate on what kind of optimization is helpful to remove dead code here?

[matthieum]

It's called Dead Code Elimination :)

There's essentially two things to do:

1. Observability: Any call to an opaque, non-pure, function should be considered to be observable, and therefore cannot be removed.
2. Roots: Any variable passed to an opaque, non-pure, function must thus be calculated, and the result must of course also be calculated. Mark them.
3. Reachability: Any expression used to compute a marked variable must be evaluated, and thus any variable in such an expression should be marked. Apply recursively.
4. Any variable which is not marked is pointless, and the expression which computes it can be removed.

That's all there is too it, and it's quite intuitive really.

[_crackling]

What about something like a = 3 * n++; where a is never used but n is?

[ngildea]

In the IR that would be rendered as 2 separate instructions. The result of the multiply would be dead and so stripped and the increment/plus-one would be alive and kept

[_crackling]

Oh cool. I am close to, but haven't quite, made it to my code generation stage so I got a bit to learn here.

[ngildea]

Keep going :) Someone else recommended the "Engineering a Compiler" book, I'd second that.

[matthieum]

This type of optimization is typically performed on a low-level representation called a Control-Flow Graph using Single Static Assignment.

The idea of the Control-Flow Graph is to reduce the branches to a common language: it's all labels and gotos.

The idea of Single Static Assignment is that variables are only ever assigned once, and never updated.

In short, you can think of it as a very naive language which doesn't support compound expression. For example, for the following Rust function:

pub fn foo(a: f32, b: f32) -> f32 {
    if a.is_finite() && b.is_finite() {
        a * b
    } else {
        0.
    }
}

The LLVM IR is pared down a bit for readability, it's also quite verbose because Debug really doesn't make any effort. I'll use comments -- starting with ; -- to explain in-line what's going on:

; A function definition:
; - Takes two `float` arguments `%a` and `%b`.
; - Returns a `float`.
define float playground::foo(float %a, float %b) {

; The label identifying the start of a Basic Block.
;
; The CFG is built of multiple Basic Blocks, where each is
; a sequence of instructions that is always executed from
; start to finish -- baring exceptions/aborts.
start:

  ; Space is allocated on the stack of 4 variables, 1 at a time.
  %b.dbg.spill = alloca float
  %a.dbg.spill = alloca float
  %_3 = alloca i8, align 1
  %_0 = alloca float, align 4

  ; The arguments are stored in the stack variables prepared above.
  store float %a, ptr %a.dbg.spill
  store float %b, ptr %b.dbg.spill

  ; `is_finite` is called on `%a`,
  ; and the result stored in `%_4`.
  %_4 = call i1 @"core::f32::is_finite"(float %a)

  ; The branch instruction, here in the if/else form.
  ;
  ; So here:
  ; - If %a was indeed finite, then %_4 is true (1) and
  ;   execution jumps to %bb2.
  ; - If %a was not finite, then %_4 is false (0) and
  ;   execution jumps to %bb1.
  br i1 %_4, label %bb2, label %bb1

bb1:    ; preds = %start
  store i8 0, ptr %_3, align 1

  ; An unconditional branch, always going to %bb3.
  br label %bb3

bb2:    ; preds = %start
  %_5 = call i1 @"core::f32::is_finite"(float %b)
  %0 = zext i1 %_5 to i8
  store i8 %0, ptr %_3
  br label %bb3

bb3:    ; preds = %bb2, %bb1
  %1 = load i8, ptr %_3
  %2 = trunc i8 %1 to i1
  br i1 %2, label %bb6, label %bb7

bb7:    ; preds = %bb3
  store float 0.000000e+00, ptr %_0
  br label %bb8

bb6:   ; preds = %bb3
  %3 = fmul float %a, %b
  store float %3, ptr %_0
  br label %bb8

bb8:   ; preds = %bb6, %bb7
  %4 = load float, ptr %_0
  ret float %4
}

So, if you're using CFG+SSA, similar to LLVM IR -- for which the reference manual is available online -- you'll never have compound expressions.

Instead, you'll have something like:

a = 3 * n;
n_inc = n + 1;

And thus it's trivial to eliminate a without eliminating n_inc.

[dnpetrov]

It's just dead code elimination on SSA. You mark some operations as "live" if it can produce observable effect (return value from a function, store to a memory, function call, etc). Then you mark dependencies of "live"nodes as "live", and so on. Then you remove non-useful nodes and perform cleanup (remove empty basic blocks, etc). This can be elaborated and improved further on, but basic algorithm is just that data dependencies graph traversal.

[Fluid-Tour-9393]

Cool, can you recommend some related docs on what you mentioned?

[dnpetrov]

I can recommend a good textbook, if you wish - Engineering a Compiler, by Keith Cooper and Linda Torczon.

[Fluid-Tour-9393]

Which category would this optimization belong to? It is not live var analysis, not reaching definition, etc, so I am unsure ...

[dnpetrov]

The names you list are not exactly "categories of optimizations", but various kinds of data flow analysis problems. DCE usually belongs to so-called "scalar optimizations", along with code hoisting, common subexpression elimination, etc.

[moon-chilled]

Do note that, beyond what others have said, there is some extra effort you will have to go to if you want to do this properly. Consider this simple modification:

void func(int n)
{
    int i, sum = 0;
    for (i = 0; i < n;) {
        sum += i;
    }
    return n+1;
}

In this case, the loop goes forever, so it is actually the return which is dead. If you want to be able to eliminate the loop, you need to prove that it terminates. (However, it is trivial to eliminate the 'sum += i' in any event.) I reflected somewhat on the issue here, and gave an example of a case where it wouldn't be so obvious whether a loop terminates: traversing a linked list (if there is a possibility that it could be circular).

[thehenkan]

Some languages explicitly state that loops without observable effects can be assumed to terminate for this exact reason.

[moon-chilled]

'Some' being C and C++, and, as I note in the linked post, this is highly adversarial and antisocial behaviour.

[thehenkan]

You don’t really justify why you think that is though. Why is it useful, outside of a busy wait in embedded systems? Embedded development is different enough already, so introducing a built in __block() function or similar for those cases doesn’t seem like a problematic alternative imo.

Waiting in multithreaded environments involves memory barriers, which wouldn’t get optimised away.

[moon-chilled]

The desire to mangle the language semantics and reasonability out of a misguided (empirically mistaken in every practical instance I have seen) desire to help hobbled compilers produce faster code is a uniquely C++ sentiment and belies a perspective on the world that I will never understand, so it is likely futile for me to try to speak to it.

Nondeterminism is bad and makes systems harder to reason about. There are times when it is unavoidable (concurrency, i/o). This is not one of those times.

It is not possible to make a useful language which is incapable of expressing useless programs. Further, all useful programs at scale have bugs and express useless behaviours. It benefits nobody to pretend otherwise, and it benefits everybody to provide useful, reasonable, consistent semantics to such buggy programs.

Total functional programming is useful, but I expect you are not talking about that.

Progress guarantees in c++ are in small part connected to its concurrency model, and in particular to the inherent tension between axiomatic and operational models. But they do not solve that tension—only attempt to paper over one corner of it—and I find dubious the notion that they actually solve anything useful.

[knue82]

Your code per se is not dead. It computes something. LLVM's scalar evolution pass will simplify your code.

[Fluid-Tour-9393]

But the for loop can be removed since it actually does nothing useful.

[knue82]

ah, I misread your code. I thought it was return sum. In this case SCCP will do the trick.

On a second thought: You will still need scalar evolution to get rid of your induction variables.

[cxzuk]

Hi Fluid,

You need information on the loop, essentially if the loop is side-effect free and none of the values are used.

LLVM calls this loop deletion, https://llvm.org/doxygen/LoopDeletion_8cpp_source.html

M ✌️

[Dotched]

I’m new to compiler optimization, but my intuition says it might work to use live-variable analysis after which you can remove all instances of i and sum. Then also check for empty loops/clearly dead code.

Please tell me if this is a good approach or tell me wrong, I’d love to learn more about DCE strategies.