aprell / compiler-potpourri Goto Github PK

View Code? Open in Web Editor NEW

108.0 108.0 2.0 2.47 MB

Tools for a compilers course

Lua 24.85% OCaml 60.34% Shell 2.13% Makefile 2.00% C 10.19% Python 0.49%

compiler-potpourri's People

Contributors

Stargazers

Watchers

Forkers

unshorn abdo643-hulk

compiler-potpourri's Issues

Generate opaque pointers (LLVM IR)

https://llvm.org/docs/OpaquePointers.html

Missed optimization: useless jumps

Optimization of

test08(flag) {
    x := 4
    y := 4 - x
    if y != 0 {
        x := 3
    }
    if flag == 0 {
        z := 10
    }
    z := x + 5
    return z
}

produces

[B1]
test08(flag_0):
    goto L4
[B5]
L4:
    return 9

which contains a useless jump between basic blocks B1 and B5. Instead, the two basic blocks should be combined to result in

[B1]
test08(flag_0):
    return 9

Note that test03_001.hir is similar in that it's optimized to

[B1]
test03(x_0):
    goto L2
[B3]
L2:
    goto L2

with a useless jump between basic blocks B1 and B3. We can either recognize and exclude this special case or combine the two basic blocks and rewrite goto L2 as goto test03(x_0):

[B1]
test03(x_0):
    goto test03(x_0)

Final basic blocks may fall off the end

The following fails with an assertion because code <> [] at the end of basic_blocks:

$ dune exec ./test_basic.exe three_address_code/test.hir
Fatal error: exception Assert_failure("basic.ml", 88, 36)

To understand why, it helps to examine the lowered program:

$ cd three_address_code && dune exec ./test_IR.exe
test:
    receive a
    receive b
    if a <= b goto L1
    return a
    goto L2
L1:
    return b
L2:

The last statement, label L2, starts a new basic block, which is left unfinished in the absence of a terminating statement.

gcc complains about casting between incompatible function types

$ cd openmp
$ gcc -Wall -Wextra -Werror -fsanitize=address,undefined -fopenmp -c -o omp.o omp.c
omp.c: In function ‘omp_parallel_start’:
omp.c:49:55: error: cast between incompatible function types from ‘void (*)(void *)’ to ‘void * (*)(void *)’ [-Werror=cast-function-type]
   49 |         pthread_create(&team.threads[i].handle, NULL, (void *(*)(void *))fn, data);
      |                                                       ^
cc1: all warnings being treated as errors
make: *** [<builtin>: omp.o] Error 1

Useless phi-function is not removed

Mutating sort.hir created a test case with an undefined variable t2 and a useless phi-function t2_2 := PHI(t2_2, t2_2) that we forget to remove, causing llc to complain: "Instruction does not dominate all uses!" This should be easy to remedy.

Branch simplification invalidates def-use information

The checks introduced by commits b495cc0 and e5f837a uncover this issue when simplifying fib_001.hir:

[B1]
fib(n_0):
    t0_0 := 0
    t1_0 := 1
    if n_0 < 2 goto L1 else goto L2
[B2]
L1:
    return n_0
[B5]
L4:
    return n_0
[B7]
L5:
    i_3 := 2
    goto L6
[B8]
L6:
    i_4 := PHI(i_3, i_6)
    t0_4 := PHI(t0_0, t0_6)
    t1_4 := PHI(t1_0, t1_6)
    if i_4 <= n_0 goto L7 else goto L8
[B9]
L7:
    t2_0 := t0_4 + t1_4
    t0_6 := t1_4
    t1_6 := t2_0
    i_6 := i_4 + 3262
    goto L6
[B10]
L8:
    return t1_4
[B11]
L2:
    i_9 := 2
    if i_9 <= 2 goto L4 else goto L5

[B8] i_4 := PHI(i_3, i_6) -use-> [B8] if i_4 <= n_0 goto L7 else goto L8
[B8] i_4 := PHI(i_3, i_6) -use-> [B9] i_6 := i_4 + 3262
[B1] t1_0 := 1 -use-> [B8] t1_4 := PHI(t1_0, t1_6)
[B1] fib(n_0): -use-> [B1] if n_0 < 2 goto L1 else goto L2
[B1] fib(n_0): -use-> [B2] return n_0
[B1] fib(n_0): -use-> [B5] return n_0
[B1] fib(n_0): -use-> [B8] if i_4 <= n_0 goto L7 else goto L8
[B8] t1_4 := PHI(t1_0, t1_6) -use-> [B10] return t1_4
[B8] t1_4 := PHI(t1_0, t1_6) -use-> [B9] t0_6 := t1_4
[B8] t1_4 := PHI(t1_0, t1_6) -use-> [B9] t2_0 := t0_4 + t1_4
[B7] i_3 := 2 -use-> [B8] i_4 := PHI(i_3, i_6)
[B9] t0_6 := t1_4 -use-> [B8] t0_4 := PHI(t0_0, t0_6)
[B9] i_6 := i_4 + 3262 -use-> [B8] i_4 := PHI(i_3, i_6)
[B11] i_9 := 2 -use-> [B11] if i_9 <= 2 goto L4 else goto L5
[B8] t0_4 := PHI(t0_0, t0_6) -use-> [B9] t2_0 := t0_4 + t1_4
[B9] t2_0 := t0_4 + t1_4 -use-> [B9] t1_6 := t2_0
[B1] t0_0 := 0 -use-> [B8] t0_4 := PHI(t0_0, t0_6)
[B9] t1_6 := t2_0 -use-> [B8] t1_4 := PHI(t1_0, t1_6)

Propagating copies
Checking SSA graph
Checking PHI functions
Propagating constants
After propagating i_9 := 2:
[B8] i_4 := PHI(i_3, i_6) -use-> [B8] if i_4 <= n_0 goto L7 else goto L8
[B8] i_4 := PHI(i_3, i_6) -use-> [B9] i_6 := i_4 + 3262
[B1] t1_0 := 1 -use-> [B8] t1_4 := PHI(t1_0, t1_6)
[B1] fib(n_0): -use-> [B1] if n_0 < 2 goto L1 else goto L2
[B1] fib(n_0): -use-> [B2] return n_0
[B1] fib(n_0): -use-> [B5] return n_0
[B1] fib(n_0): -use-> [B8] if i_4 <= n_0 goto L7 else goto L8
[B8] t1_4 := PHI(t1_0, t1_6) -use-> [B10] return t1_4
[B8] t1_4 := PHI(t1_0, t1_6) -use-> [B9] t0_6 := t1_4
[B8] t1_4 := PHI(t1_0, t1_6) -use-> [B9] t2_0 := t0_4 + t1_4
[B7] i_3 := 2 -use-> [B8] i_4 := PHI(i_3, i_6)
[B9] t0_6 := t1_4 -use-> [B8] t0_4 := PHI(t0_0, t0_6)
[B9] i_6 := i_4 + 3262 -use-> [B8] i_4 := PHI(i_3, i_6)
[B8] t0_4 := PHI(t0_0, t0_6) -use-> [B9] t2_0 := t0_4 + t1_4
[B9] t2_0 := t0_4 + t1_4 -use-> [B9] t1_6 := t2_0
[B1] t0_0 := 0 -use-> [B8] t0_4 := PHI(t0_0, t0_6)
[B9] t1_6 := t2_0 -use-> [B8] t1_4 := PHI(t1_0, t1_6)

Checking SSA graph
Checking PHI functions
Eliminating dead code
Checking SSA graph
Checking PHI functions
Simplifying control flow
Skipped B11
Checking SSA graph
Checking PHI functions
Eliminating unreachable code
After removing i_3 := 2:
[B8] i_4 := PHI(i_3, i_6) -use-> [B8] if i_4 <= n_0 goto L7 else goto L8
[B8] i_4 := PHI(i_3, i_6) -use-> [B9] i_6 := i_4 + 3262
[B1] t1_0 := 1 -use-> [B8] t1_4 := PHI(t1_0, t1_6)
[B1] fib(n_0): -use-> [B1] if n_0 < 2 goto L1 else goto L4
[B1] fib(n_0): -use-> [B2] return n_0
[B1] fib(n_0): -use-> [B5] return n_0
[B1] fib(n_0): -use-> [B8] if i_4 <= n_0 goto L7 else goto L8
[B8] t1_4 := PHI(t1_0, t1_6) -use-> [B10] return t1_4
[B8] t1_4 := PHI(t1_0, t1_6) -use-> [B9] t0_6 := t1_4
[B8] t1_4 := PHI(t1_0, t1_6) -use-> [B9] t2_0 := t0_4 + t1_4
[B9] t0_6 := t1_4 -use-> [B8] t0_4 := PHI(t0_0, t0_6)
[B9] i_6 := i_4 + 3262 -use-> [B8] i_4 := PHI(i_3, i_6)
[B8] t0_4 := PHI(t0_0, t0_6) -use-> [B9] t2_0 := t0_4 + t1_4
[B9] t2_0 := t0_4 + t1_4 -use-> [B9] t1_6 := t2_0
[B1] t0_0 := 0 -use-> [B8] t0_4 := PHI(t0_0, t0_6)
[B9] t1_6 := t2_0 -use-> [B8] t1_4 := PHI(t1_0, t1_6)

Removed B7
After removing i_4 := PHI(i_3, i_6):
[B1] t1_0 := 1 -use-> [B8] t1_4 := PHI(t1_0, t1_6)
[B1] fib(n_0): -use-> [B1] if n_0 < 2 goto L1 else goto L4
[B1] fib(n_0): -use-> [B2] return n_0
[B1] fib(n_0): -use-> [B5] return n_0
[B1] fib(n_0): -use-> [B8] if i_4 <= n_0 goto L7 else goto L8
[B8] t1_4 := PHI(t1_0, t1_6) -use-> [B10] return t1_4
[B8] t1_4 := PHI(t1_0, t1_6) -use-> [B9] t0_6 := t1_4
[B8] t1_4 := PHI(t1_0, t1_6) -use-> [B9] t2_0 := t0_4 + t1_4
[B9] t0_6 := t1_4 -use-> [B8] t0_4 := PHI(t0_0, t0_6)
[B9] i_6 := i_4 + 3262 has no use
[B8] t0_4 := PHI(t0_0, t0_6) -use-> [B9] t2_0 := t0_4 + t1_4
[B9] t2_0 := t0_4 + t1_4 -use-> [B9] t1_6 := t2_0
[B1] t0_0 := 0 -use-> [B8] t0_4 := PHI(t0_0, t0_6)
[B9] t1_6 := t2_0 -use-> [B8] t1_4 := PHI(t1_0, t1_6)

After removing t0_4 := PHI(t0_0, t0_6):
[B1] t1_0 := 1 -use-> [B8] t1_4 := PHI(t1_0, t1_6)
[B1] fib(n_0): -use-> [B1] if n_0 < 2 goto L1 else goto L4
[B1] fib(n_0): -use-> [B2] return n_0
[B1] fib(n_0): -use-> [B5] return n_0
[B1] fib(n_0): -use-> [B8] if i_4 <= n_0 goto L7 else goto L8
[B8] t1_4 := PHI(t1_0, t1_6) -use-> [B10] return t1_4
[B8] t1_4 := PHI(t1_0, t1_6) -use-> [B9] t0_6 := t1_4
[B8] t1_4 := PHI(t1_0, t1_6) -use-> [B9] t2_0 := t0_4 + t1_4
[B9] t0_6 := t1_4 has no use
[B9] i_6 := i_4 + 3262 has no use
[B9] t2_0 := t0_4 + t1_4 -use-> [B9] t1_6 := t2_0
[B1] t0_0 := 0 has no use
[B9] t1_6 := t2_0 -use-> [B8] t1_4 := PHI(t1_0, t1_6)

After removing t1_4 := PHI(t1_0, t1_6):
[B1] t1_0 := 1 has no use
[B1] fib(n_0): -use-> [B1] if n_0 < 2 goto L1 else goto L4
[B1] fib(n_0): -use-> [B2] return n_0
[B1] fib(n_0): -use-> [B5] return n_0
[B1] fib(n_0): -use-> [B8] if i_4 <= n_0 goto L7 else goto L8
[B9] t0_6 := t1_4 has no use
[B9] i_6 := i_4 + 3262 has no use
[B9] t2_0 := t0_4 + t1_4 -use-> [B9] t1_6 := t2_0
[B1] t0_0 := 0 has no use
[B9] t1_6 := t2_0 has no use

Removed B8
After removing t2_0 := t0_4 + t1_4:
[B1] t1_0 := 1 has no use
[B1] fib(n_0): -use-> [B1] if n_0 < 2 goto L1 else goto L4
[B1] fib(n_0): -use-> [B2] return n_0
[B1] fib(n_0): -use-> [B5] return n_0
[B9] t0_6 := t1_4 has no use
[B9] i_6 := i_4 + 3262 has no use
[B1] t0_0 := 0 has no use
[B9] t1_6 := t2_0 has no use

After removing t0_6 := t1_4:
[B1] t1_0 := 1 has no use
[B1] fib(n_0): -use-> [B1] if n_0 < 2 goto L1 else goto L4
[B1] fib(n_0): -use-> [B2] return n_0
[B1] fib(n_0): -use-> [B5] return n_0
[B9] i_6 := i_4 + 3262 has no use
[B1] t0_0 := 0 has no use
[B9] t1_6 := t2_0 has no use

After removing t1_6 := t2_0:
[B1] t1_0 := 1 has no use
[B1] fib(n_0): -use-> [B1] if n_0 < 2 goto L1 else goto L4
[B1] fib(n_0): -use-> [B2] return n_0
[B1] fib(n_0): -use-> [B5] return n_0
[B9] i_6 := i_4 + 3262 has no use
[B1] t0_0 := 0 has no use

After removing i_6 := i_4 + 3262:
[B1] t1_0 := 1 has no use
[B1] fib(n_0): -use-> [B1] if n_0 < 2 goto L1 else goto L4
[B1] fib(n_0): -use-> [B2] return n_0
[B1] fib(n_0): -use-> [B5] return n_0
[B1] t0_0 := 0 has no use

Removed B9
Removed B10
Removed B11
Checking SSA graph
Checking PHI functions
Propagating copies
Checking SSA graph
Checking PHI functions
Propagating constants
Checking SSA graph
Checking PHI functions
Eliminating dead code
After removing t1_0 := 1:
[B1] fib(n_0): -use-> [B1] if n_0 < 2 goto L1 else goto L4
[B1] fib(n_0): -use-> [B2] return n_0
[B1] fib(n_0): -use-> [B5] return n_0
[B1] t0_0 := 0 has no use

Checking SSA graph
Checking PHI functions
Simplifying control flow
Checking SSA graph
[B1] fib(n_0): -use-> [B1] goto L1
Variable n_0 is not in goto L1
Fatal error: exception Failure("Inconsistent SSA graph")

Building more than one CFG fails

Cfg.construct assumes that basic blocks are numbered starting from 1, which is only the case when building the first CFG:

utop # let graph = Graphs.graph_of_input "examples/pow.hir";;
val graph : Cfg.t = <abstr>

utop # let graph = Graphs.graph_of_input "examples/pow.hir";;
Exception: Not_found.

Block-local copy propagation is insufficient when deleting phi-functions

Converting pow.hir to SSA form reveals a problem with block-local copy propagation.

After deleting all unary phi-functions, there is one more phi-function that should be deleted, namely b_1 := PHI(b_0, b_1) in basic block B2:

[B1]
pow(b_0, e_0):
    r_0 := 1
    goto L1
[B2]
L1:
    b_1 := PHI(b_0, b_1)
    e_1 := PHI(e_0, e_2)
    r_1 := PHI(r_0, r_2)
    if e_1 <= 0 goto L2
[B3]
    r_2 := r_1 * b_1
    e_2 := e_1 - 1
    goto L1
[B4]
L2:
    return r_1

When we delete this phi-function and copy-propagate b_0 for b_1, we miss the use of b_1 in basic block B3 and end up with incorrect code:

[B1]
pow(b_0, e_0):
    r_0 := 1
    goto L1
[B2]
L1:
    e_1 := PHI(e_0, e_2)
    r_1 := PHI(r_0, r_2)
    if e_1 <= 0 goto L2
[B3]
    r_2 := r_1 * b_1
    e_2 := e_1 - 1
    goto L1
[B4]
L2:
    return r_1

Remaining shift/reduce conflicts

For reference:

$ menhir --explain parser.mly
Warning: one state has shift/reduce conflicts.
Warning: one shift/reduce conflict was arbitrarily resolved.

The problem:

utop # Parse.parse_prog ["return a"; "b := 1"];;
- : IR.stmt list =
[Three_address_code.IR.Return
  (Some (Three_address_code.IR.Ref (Three_address_code.IR.Var "a")));
 Three_address_code.IR.Move (Three_address_code.IR.Var "b",
  Three_address_code.IR.Const 1)]

utop # Parse.parse_prog ["return"; "b := 1"];;
Exception: Three_address_code.Parser.MenhirBasics.Error

Lowering loops

A loop like

while i < n {
    ...
}

is currently lowered to

L1:
    if i < n goto L2 else goto L3
L2:
    ...
    goto L1
L3:

ending with an unconditional jump back to the loop header. This is also what LLVM produces at -O0. At -O1 and higher, however, LLVM "rotates" the loop to turn it into a guarded do/while, resulting in code equivalent to

if i < n goto L1 else goto L2
L1:
    ...
    if i < n goto L1 else goto L2
L2:

goto L2
L1:
    ...
L2:
    if i < n goto L1 else goto L3
L3:

Unreachable code elimination matches other statements marked for removal

This curious mutation

int fib(int)

fib(n) {
    t0 := 0
    t1 := 1
    if n < 2 {
        return n
    }
    i := 2
    while i <= 2 {
        return n
    }
    i := 2
    while i <= n {
        t2 := t0 + t1
        t0 := t1
        t1 := t2
        i := i + 3262
    }
    return t1
}

causes an assertion failure in unreachable code elimination when trying to remove basic block B8:

[B1]
fib(n_0):
    t0_0 := 0
    t1_0 := 1
    if n_0 < 2 goto L1 else goto L2
[B2]
L1:
    return n_0
[B3]
L2:
    i_2 := 2
    goto L3
[B4]
L3:
    if i_2 <= 2 goto L4 else goto L5
[B5]
L4:
    return n_0
[B7]
L5:
    i_6 := 2
    goto L6
[B8]
L6:
    i_7 := PHI(i_6, i_9)
    t0_6 := PHI(t0_0, t0_8)
    t1_6 := PHI(t1_0, t1_8)
    if i_7 <= n_0 goto L7 else goto L8
[B9]
L7:
    t2_0 := t0_6 + t1_6
    t0_8 := t1_6
    t1_8 := t2_0
    i_9 := i_7 + 3262
    goto L6
[B10]
L8:
    return t1_6

i_2 := 2 -use-> if i_2 <= 2 goto L4 else goto L5
t1_0 := 1 -use-> t1_6 := PHI(t1_0, t1_8)
fib(n_0): -use-> if n_0 < 2 goto L1 else goto L2
fib(n_0): -use-> return n_0
fib(n_0): -use-> return n_0
fib(n_0): -use-> if i_7 <= n_0 goto L7 else goto L8
i_7 := PHI(i_6, i_9) -use-> if i_7 <= n_0 goto L7 else goto L8
i_7 := PHI(i_6, i_9) -use-> i_9 := i_7 + 3262
t0_8 := t1_6 -use-> t0_6 := PHI(t0_0, t0_8)
t0_6 := PHI(t0_0, t0_8) -use-> t2_0 := t0_6 + t1_6
i_6 := 2 -use-> i_7 := PHI(i_6, i_9)
t1_8 := t2_0 -use-> t1_6 := PHI(t1_0, t1_8)
i_9 := i_7 + 3262 -use-> i_7 := PHI(i_6, i_9)
t2_0 := t0_6 + t1_6 -use-> t1_8 := t2_0
t0_0 := 0 -use-> t0_6 := PHI(t0_0, t0_8)
t1_6 := PHI(t1_0, t1_8) -use-> return t1_6
t1_6 := PHI(t1_0, t1_8) -use-> t0_8 := t1_6
t1_6 := PHI(t1_0, t1_8) -use-> t2_0 := t0_6 + t1_6

Propagating copies
Propagating constants
After propagating i_2 := 2:
t1_0 := 1 -use-> t1_6 := PHI(t1_0, t1_8)
fib(n_0): -use-> if n_0 < 2 goto L1 else goto L2
fib(n_0): -use-> return n_0
fib(n_0): -use-> return n_0
fib(n_0): -use-> if i_7 <= n_0 goto L7 else goto L8
i_7 := PHI(i_6, i_9) -use-> if i_7 <= n_0 goto L7 else goto L8
i_7 := PHI(i_6, i_9) -use-> i_9 := i_7 + 3262
t0_8 := t1_6 -use-> t0_6 := PHI(t0_0, t0_8)
t0_6 := PHI(t0_0, t0_8) -use-> t2_0 := t0_6 + t1_6
i_6 := 2 -use-> i_7 := PHI(i_6, i_9)
t1_8 := t2_0 -use-> t1_6 := PHI(t1_0, t1_8)
i_9 := i_7 + 3262 -use-> i_7 := PHI(i_6, i_9)
t2_0 := t0_6 + t1_6 -use-> t1_8 := t2_0
t0_0 := 0 -use-> t0_6 := PHI(t0_0, t0_8)
t1_6 := PHI(t1_0, t1_8) -use-> return t1_6
t1_6 := PHI(t1_0, t1_8) -use-> t0_8 := t1_6
t1_6 := PHI(t1_0, t1_8) -use-> t2_0 := t0_6 + t1_6

Eliminating dead code
Simplifying control flow
Skipped B3
Skipped B4
Eliminating unreachable code
Trying to remove B3
Removed B3
Trying to remove B4
Removed B4
Trying to remove B7
After removing i_6 := 2:
t1_0 := 1 -use-> t1_6 := PHI(t1_0, t1_8)
fib(n_0): -use-> if n_0 < 2 goto L1 else goto L4
fib(n_0): -use-> return n_0
fib(n_0): -use-> return n_0
fib(n_0): -use-> if i_7 <= n_0 goto L7 else goto L8
i_7 := i_9 -use-> if i_7 <= n_0 goto L7 else goto L8
i_7 := i_9 -use-> i_9 := i_7 + 3262
t0_8 := t1_6 -use-> t0_6 := PHI(t0_0, t0_8)
t0_6 := PHI(t0_0, t0_8) -use-> t2_0 := t0_6 + t1_6
t1_8 := t2_0 -use-> t1_6 := PHI(t1_0, t1_8)
i_9 := i_7 + 3262 -use-> i_7 := i_9
t2_0 := t0_6 + t1_6 -use-> t1_8 := t2_0
t0_0 := 0 -use-> t0_6 := PHI(t0_0, t0_8)
t1_6 := PHI(t1_0, t1_8) -use-> return t1_6
t1_6 := PHI(t1_0, t1_8) -use-> t0_8 := t1_6
t1_6 := PHI(t1_0, t1_8) -use-> t2_0 := t0_6 + t1_6

Removed B7
Trying to remove B8
Fatal error: exception File "optim.ml", line 141, characters 17-23: Assertion failed

The problem is that eliminate_def considers basic blocks B8 and B9 to be reachable as long as their nodes are not removed from the CFG. I think it's best to make eliminate_def x disregard all uses of x in blocks that have been marked for removal, whether these blocks are technically still reachable or not.

Wrong dependence distance after strip mining

Strip-mining the loop

for (i = 1; i <= 16; i++)
    a[i+3] = a[i] + b[i];

with dependence distance d = (3) results in

// Strip size s = 5
for (is = 1; is <= 16; is += 5)
    for (i = is; i <= min(16, is + 4); i++)
        a[i+3] = a[i] + b[i];

with dependence distances d = (0, 3) and d = (5, 3) as determined by dep.lua.

d = (5, 3) is wrong: should be d = (1, -2).

Constant propagation invalidates def-use information

This version of "pow"

int pow(int, int)

pow(b, e) {
    r := 0
    while e > 0 {
        r := r * b
        e := e - 1
    }
    return r
}

reveals an issue in constant propagation:

[B1]
pow(b_0, e_0):
    r_0 := 0
    goto L1
[B2]
L1:
    e_1 := PHI(e_0, e_3)
    r_1 := PHI(r_0, r_3)
    if e_1 > 0 goto L2 else goto L3
[B3]
L2:
    r_3 := r_1 * b_0
    e_3 := e_1 - 1
    goto L1
[B4]
L3:
    return r_1

[B1] pow(b_0, e_0): -use-> [B3] r_3 := r_1 * b_0
[B1] r_0 := 0 -use-> [B2] r_1 := PHI(r_0, r_3)
[B3] e_3 := e_1 - 1 -use-> [B2] e_1 := PHI(e_0, e_3)
[B1] pow(b_0, e_0): -use-> [B2] e_1 := PHI(e_0, e_3)
[B3] r_3 := r_1 * b_0 -use-> [B2] r_1 := PHI(r_0, r_3)
[B2] e_1 := PHI(e_0, e_3) -use-> [B2] if e_1 > 0 goto L2 else goto L3
[B2] e_1 := PHI(e_0, e_3) -use-> [B3] e_3 := e_1 - 1
[B2] r_1 := PHI(r_0, r_3) -use-> [B3] r_3 := r_1 * b_0
[B2] r_1 := PHI(r_0, r_3) -use-> [B4] return r_1

Propagating copies
Checking SSA graph
Checking PHI functions
Propagating constants
After propagating r_1 := 0:
[B1] pow(b_0, e_0): -use-> [B3] r_3 := 0
[B1] r_0 := 0 has no use
[B3] e_3 := e_1 - 1 -use-> [B2] e_1 := PHI(e_0, e_3)
[B1] pow(b_0, e_0): -use-> [B2] e_1 := PHI(e_0, e_3)
[B3] r_3 := 0 has no use
[B2] e_1 := PHI(e_0, e_3) -use-> [B2] if e_1 > 0 goto L2 else goto L3
[B2] e_1 := PHI(e_0, e_3) -use-> [B3] e_3 := e_1 - 1

Checking SSA graph
[B1] pow(b_0, e_0): -use-> [B3] r_3 := 0
Variable b_0 is not in r_3 := 0
Fatal error: exception Failure("Inconsistent SSA graph")

Namely, constant propagation of r_1 := 0 replaces r_3 := r_1 * b_0 with r_3 := 0, removing b_0 as a result of expression simplification (0 * b_0 = 0). However, this use of b_0 is not removed from the SSA graph.

Nested high-level constructs are not lowered

Modify test.hir to read

test(a, b) {
    if a > b {
        if a < 100 {
            return a
        } else {
            return b
        }
    } else {
        return b
    }
}

and the following fails with an assertion in dump > string_of_stmt because the inner conditional is not lowered:

$ dune exec ./test_IR.exe
Fatal error: exception Assert_failure("three_address_code/IR.ml", 134, 9)

Calculating dominators in the presence of unreachable nodes

After fixing #2, we determine the following basic blocks for test.hir:

$ dune exec ./test_basic.exe three_address_code/test.hir
[B1]
  1 test:
  2     receive a
  3     receive b
  4     if a <= b goto L1
[B2]
  5     return a
[B3]
  6     goto L2
[B4]
  7 L1:
  8     return b
[B5]
  9 L2:

Notice that B3 and B5 are unreachable from Entry. This causes problems when trying to calculate dominators:

$ dune exec ./test_dom.exe basic_blocks/three_address_code/test.hir
Fatal error: exception Assert_failure("dom.ml", 59, 6)

Unreachable code elimination invalidates def-use information

My God, fuzzing is relentless. Optimization of this function

int test06(int)

test06(p) {
    x := 1
    x := 1
    while p > 10 {
        if x != 1 {
            x := 2
            x := 2
        }
    }
    return x
}

aborts after finding a broken SSA edge:

[B1]
test06(p_0):
    x_0 := 1
    x_1 := 1
    goto L3
[B2]
L3:
    x_2 := PHI(x_1, x_2, x_6)
    if p_0 > 10 goto L4 else goto L5
[B3]
L4:
    if x_2 != 1 goto L1 else goto L3
[B4]
L1:
    x_5 := 2
    x_6 := 2
    goto L3
[B6]
L5:
    return x_2

[B4] x_5 := 2 has no use
[B2] x_2 := PHI(x_1, x_2, x_6) -use-> [B2] x_2 := PHI(x_1, x_2, x_6)
[B2] x_2 := PHI(x_1, x_2, x_6) -use-> [B3] if x_2 != 1 goto L1 else goto L3
[B2] x_2 := PHI(x_1, x_2, x_6) -use-> [B6] return x_2
[B1] test06(p_0): -use-> [B2] if p_0 > 10 goto L4 else goto L5
[B1] x_0 := 1 has no use
[B1] x_1 := 1 -use-> [B2] x_2 := PHI(x_1, x_2, x_6)
[B4] x_6 := 2 -use-> [B2] x_2 := PHI(x_1, x_2, x_6)

Propagating copies
Checking SSA graph
Checking PHI functions
Propagating constants
After propagating x_2 := 1:
[B4] x_5 := 2 has no use
[B2] x_2 := PHI(x_1, x_2, x_6) -use-> [B2] x_2 := PHI(x_1, x_2, x_6)
[B1] test06(p_0): -use-> [B2] if p_0 > 10 goto L4 else goto L5
[B1] x_0 := 1 has no use
[B1] x_1 := 1 -use-> [B2] x_2 := PHI(x_1, x_2, x_6)
[B4] x_6 := 2 -use-> [B2] x_2 := PHI(x_1, x_2, x_6)

Checking SSA graph
Checking PHI functions
Eliminating dead code
After removing x_5 := 2:
[B2] x_2 := PHI(x_1, x_2, x_6) -use-> [B2] x_2 := PHI(x_1, x_2, x_6)
[B1] test06(p_0): -use-> [B2] if p_0 > 10 goto L4 else goto L5
[B1] x_0 := 1 has no use
[B1] x_1 := 1 -use-> [B2] x_2 := PHI(x_1, x_2, x_6)
[B4] x_6 := 2 -use-> [B2] x_2 := PHI(x_1, x_2, x_6)

Checking SSA graph
Checking PHI functions
Simplifying control flow
Skipped B3
Checking SSA graph
Checking PHI functions
Eliminating unreachable code
Removed B3
After removing x_6 := 2:
[B2] x_2 := x_1 -use-> [B2] x_2 := x_1
[B1] test06(p_0): -use-> [B2] if p_0 > 10 goto L3 else goto L5
[B1] x_0 := 1 has no use
[B1] x_1 := 1 -use-> [B2] x_2 := x_1

Removed B4
Checking SSA graph
[B2] x_2 := x_1 -use-> [B2] x_2 := x_1
Variable x_2 is not in x_2 := x_1
Fatal error: exception Failure("Inconsistent SSA graph")

When unreachable code elimination removes the use of x_6 in x_2 := PHI(x_1, x_2, x_6), the resulting x_2 := PHI(x_1, x_2) is replaced with x_2 := x_1, but the use of x_2 is not removed accordingly.

Self-referential phi-function is not eliminated

This function

int test06(int)

test06(p) {
    x := 2
    while p > 10 {
        if x != 1 {
            x := 2
        }
    }
    return x
}

causes an exception when trying to emit LLVM IR, after propagating x_1 := 2 and arriving at this code:

[B1]
test06(p_0):
    x_0 := 2
    goto L3
[B2]
L3:
    x_1 := PHI(x_0, x_1, x_4)
    if p_0 > 10 goto L1 else goto L5
[B4]
L1:
    x_4 := 2
    goto L3
[B6]
L5:
    return 2

There are several issues here:

Constant propagation has not removed the PHI at the beginning of basic block B2.
As a result, x_1 is effectively dead but not eliminated because of the self-referential use in its definition.
Notice that the PHI takes three arguments, but basic block B2 has only two incoming edges left. Further control flow optimizations have managed to break the invariant that every argument of a PHI corresponds to an incoming edge.

An empty else branch creates a redundant basic block

This code

test:
    if expr {
        ...
    } else {
    }

is lowered to

test:
    if expr goto L1 else goto L2
L1:
    ...
    goto L3
L2:
L3:

and turned into

[B1]
test:
    if expr goto L1 else goto L2
[B2]
L1:
    ...
    goto L3
[B3]
L2:
    goto L3
[B4]
L3:

after creating basic blocks.

Basic block B3 is redundant.

Constant and copy propagation in the presence of phi-functions

If we try to optimize our example programs, we notice two problems caused by messing with phi-function arguments:

Propagating constants into phi-functions is unsupported and raises an error. An example from pow.hir or fastpow.hir:
```
r_0 := 1
...
r_1 := PHI(r_0, r_5)
```
Propagating copies into phi-functions may complicate a later translation out of SSA form. An example from fib.hir, known as the swap problem:
```
t0_3 := PHI(t0_0, t0_5)
t1_3 := PHI(t1_0, t1_5)
...
t0_5 := t1_3
```

A possible solution would be to exclude phi-functions from optimization, except when propagating redundant phi-functions during SSA minimization.

Control reaches end of non-void function

This function

int test01(int, int)

test01(a, b) {
    if a > b {
        if a < 100 {
            return b
        }
    } else {
        c := b + 1
        return c
    }
}

is translated to

[B1]
test01(a_0, b_0):
    if a_0 > b_0 goto L3 else goto L4
[B2]
L3:
    if a_0 < 100 goto L1 else goto L5
[B3]
L1:
    return b_0
[B5]
L4:
    c_0 := b_0 + 1
    return c_0
[B6]
L5:
    return

where basic block B6 returns without value. Translating this code further to LLVM IR gives

define i32 @test01(i32 %a_0, i32 %b_0) {
test01:
  %0 = icmp sgt i32 %a_0, %b_0
  br i1 %0, label %L3, label %L4
L3:
  %1 = icmp slt i32 %a_0, 100
  br i1 %1, label %L1, label %L5
L1:
  ret i32 %b_0
L4:
  %c_0 = add i32 %b_0, 1
  ret i32 %c_0
L5:
  ret void
}

which causes llc to complain about ret void that "doesn't match function result type 'i32'". I propose to ret i32 undef instead.

Sparse conditional constant propagation is led astray

This function

int test06(int)

test06(p) {
    x := 1
    x := 1
    x := 1
    while p > 10 {
        if x != 1 {}
        x := 2
    }
    return x
}

fails an assertion shortly after propagating x_3 := 1, which seems wrong because x := 2 is certainly reachable. In fact, there's a problem with sparse conditional constant propagation:

[B1]
test06(p_0):
    x_0 := 1
    x_1 := 1
    x_2 := 1
    goto L3
[B2]
L3:
    x_3 := PHI(x_2, x_6)
    if p_0 > 10 goto L4 else goto L5
[B3]
L4:
    if x_3 != 1 goto L2 else goto L2
[B5]
L2:
    x_6 := 2
    goto L3
[B6]
L5:
    return x_3

Result of SSCP:
+----------+--------+
| Variable | Value  |
+----------+--------+
| p_0      | Bottom |
| x_0      | 1      |
| x_1      | 1      |
| x_2      | 1      |
| x_3      | Bottom |
| x_6      | 2      |
+----------+--------+

Result of SCCP:
Execute Entry -> B1
x_0 := 1
x_1 := 1
x_2 := 1
Queue B1 -> B2 (jump)
Execute B1 -> B2
x_3 := 1 meet Top = 1
if Bottom > 10 = Bottom
Queue B2 -> B3 (then)
Queue B2 -> B6 (else)
Execute B2 -> B3
if 1 != 1 = 0
Queue B3 -> B5 (else)
Execute B2 -> B6
Execute B3 -> B5
+----------+--------+
| Variable | Value  |
+----------+--------+
| p_0      | Bottom |
| x_0      | 1      |
| x_1      | 1      |
| x_2      | 1      |
| x_3      | 1      |
| x_6      | Top    |
+----------+--------+

Notice that x_6 := 2 is not interpreted. The algorithm can't distinguish identical edges, in this case, B3 -> B5 appearing twice. Following one edge is indistinguishable from following the other so that executing B3 -> B5 makes it look like B5 has been visited before, causing B5's statements to be skipped. The algorithm never sees x_6 := 2 and concludes that x_3 is 1.

Branch simplification is unaware of phi-functions in successor nodes

Optimization of this function

int test06(int)

test06(p) {
    x := 2
    while p > 10 {
        if x != 1 {
            x := 2
        }
        x := 2
    }
    return x
}

aborts after finding a broken phi-function:

[B1]
test06(p_0):
    x_0 := 2
    goto L3
[B2]
L3:
    x_1 := PHI(x_0, x_6)
    if p_0 > 10 goto L4 else goto L5
[B3]
L4:
    if x_1 != 1 goto L1 else goto L2
[B4]
L1:
    x_4 := 2
    goto L2
[B5]
L2:
    x_5 := PHI(x_1, x_4)
    x_6 := 2
    goto L3
[B6]
L5:
    return x_1

x_4 := 2 -use-> x_5 := PHI(x_1, x_4)
test06(p_0): -use-> if p_0 > 10 goto L4 else goto L5
x_0 := 2 -use-> x_1 := PHI(x_0, x_6)
x_1 := PHI(x_0, x_6) -use-> if x_1 != 1 goto L1 else goto L2
x_1 := PHI(x_0, x_6) -use-> x_5 := PHI(x_1, x_4)
x_1 := PHI(x_0, x_6) -use-> return x_1
x_6 := 2 -use-> x_1 := PHI(x_0, x_6)

Propagating copies
Propagating constants
After propagating x_1 := 2:
x_4 := 2 -use-> x_5 := PHI(x_1, x_4)
test06(p_0): -use-> if p_0 > 10 goto L4 else goto L5
x_0 := 2 -use-> x_1 := PHI(x_0, x_6)
x_1 := PHI(x_0, x_6) -use-> x_5 := PHI(x_1, x_4)
x_6 := 2 -use-> x_1 := PHI(x_0, x_6)

Eliminating dead code
Simplifying control flow
Skipped B3
Eliminating unreachable code
Removed B3
Found inconsistent x_5 := PHI(x_1, x_4): B5 has 1 incoming edge(s)
Fatal error: exception Failure("Inconsistent x_5 := PHI(x_1, x_4)")

Minor issue: Propagating x_1 := 2 should include replacing x_1 := PHI(x_0, x_6) with x_1 := 2 to enable dead store elimination of x_0 := 2 and x_6 := 2.
Major issue: Simplifying the branch in basic block B3 has no effect on x_5 := PHI(x_1, x_4) in basic block B5, which, left unchanged, causes the following phi-function check to fail.

Perhaps it's also time to reconsider propagating constants into phi-functions (see #10).

Pruning a conditional branch assumes distinct branch targets

This function

int test06(int)

test06(p) {
    x := 2
    while p > 10 {
        if x != 1 {}
        x := 2
    }
    return x
}

fails an assertion after optimizing basic block B3 from

L4:
    if x_1 != 1 goto L2 else goto L2

L4:
    goto L2

If we have a conditional branch, but only one branch target, pruning either branch cuts off the node from its only successor, causing problems further down the line when trying to skip the node.

Conditional branch is not patched

This function

int test06(int)

test06(p) {
    x := 2
    while p > 10 {
        if x != 1 {}
    }
    return x
}

with basic blocks

[B1]
test06(p):
    x := 2
    goto L3
[B2]
L3:
    if p > 10 goto L4 else goto L5
[B3]
L4:
    if x != 1 goto L1 else goto L2
[B4]
L1:
    goto L2
[B5]
L2:
    goto L3
[B6]
L5:
    return x

is simplified to

[B1]
test06(p):
    x := 2
    goto L3
[B2]
L3:
    if p > 10 goto L4 else goto L5
[B3]
L4:
    if x != 1 goto L3 else goto L2
[B6]
L5:
    return x

as a result of skipping basic blocks B4 and B5. Note the reference to label L2 of basic block B5 that no longer exists. This branch should have been redirected to label L3.

Optimizing a non-terminating function violates assertions

This function

void test03(int)

test03(x) {
    i := 1
    while i < 10 {
        x := 2 * i
        i := i + 0
    }
}

fails an assertion when trying to decide whether two basic blocks can be combined:

(* Guard against invalidating def-use information *)
let can_combine (node : Node.t) =
  is_simple node.block && (
    assert (NodeSet.cardinal node.succ = 1); (* <-- /!\ *)
    let succ = NodeSet.choose node.succ in
    is_simple succ.block
  )

The problem happens earlier, when we intend to skip basic block B3 after simplifying it to

[B3]
L2:
    goto L2

Fixing this reveals another problematic assertion:

let get_exit_node (graph : t) : Node.t =
  let _, exit = M.max_binding graph in
  assert (exit.block.name = "Exit"); (* <-- /!\ *)
  exit

Node Exit has been removed after becoming unreachable. Function get_exit_node should be changed to return a Node.t option if possible.

Late unreachable code elimination reveals broken phi-function invariant

This function

int test05()

test05() {
    x := 65535
    if x < 2 {
        y := 5 + x
    } else {
        y := x - 42
    }
    z := y * y
    return z
}

in SSA form

[B1]
test05():
    x_0 := 65535
    if x_0 < 2 goto L1 else goto L2
[B2]
L1:
    y_1 := 5 + x_0
    goto L3
[B3]
L2:
    y_3 := x_0 - 42
    goto L3
[B4]
L3:
    y_4 := PHI(y_1, y_3)
    z_0 := y_4 * y_4
    return z_0

causes an assertion failure in SCCP after basic block B2 is removed without immediately eliminating the definition of y_1 and its use in B4. SCCP looks at y_4 := PHI(y_1, y_3) and can't reconcile the two arguments with the remaining incoming edge from B3.

aprell / compiler-potpourri Goto Github PK

compiler-potpourri's People

Contributors

Stargazers

Watchers

Forkers

compiler-potpourri's Issues

Recommend Projects

Recommend Topics

Recommend Org