blog

Building a respectable compiler requires basic blocks in order for liveness analysis to be performant. Consider my own Apple compiler:

Compilation was dominated by mkLiveness and moreover simple functions took tens of milliseconds to compile.

benchmarking pipeline/bytes (gamma)
time                 62.52 ms   (62.14 ms .. 62.86 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 62.54 ms   (62.29 ms .. 62.80 ms)
std dev              470.3 μs   (308.3 μs .. 657.9 μs)

benchmarking pipeline/bytes (fcdf)
time                 108.3 ms   (106.6 ms .. 110.5 ms)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 106.1 ms   (105.4 ms .. 107.1 ms)
std dev              1.288 ms   (696.6 μs .. 2.067 ms)

After rewriting to use basic blocks, compilation times were less than 20ms, a far better user experience. Moreover, liveness analysis no longer dominates.

benchmarking pipeline/bytes (gamma)
time                 5.313 ms   (5.171 ms .. 5.485 ms)
                     0.994 R²   (0.991 R² .. 0.997 R²)
mean                 5.166 ms   (5.087 ms .. 5.262 ms)
std dev              267.0 μs   (218.5 μs .. 321.2 μs)
variance introduced by outliers: 29% (moderately inflated)

benchmarking pipeline/bytes (fcdf)
time                 10.42 ms   (9.838 ms .. 10.96 ms)
                     0.982 R²   (0.971 R² .. 0.991 R²)
mean                 12.13 ms   (11.71 ms .. 12.55 ms)
std dev              1.090 ms   (907.0 μs .. 1.409 ms)
variance introduced by outliers: 48% (moderately inflated)

Appel mentions basic blocks as an advanced optimization but does not fill in details; the precise implementation in Haskell is instructive and elegant.

First, we define uBB, dBB to simulate uses and defs on a basic block:

uBB, dBB :: E reg => [X86 reg freg a] -> IS.IntSet
uBB = foldr (\p n -> uses p \`IS.union\` (n IS.\\\ defs p)) IS.empty
dBB = foldMap defs

Note that foldr processes instructions in reverse execution order.

Then, to get liveness information for each instruction, we apply the liveness equations (each instruction has one successor in a basic block):

\( {\tt in}[n]={\tt uses}[n]\cup ({\tt out}[n]~\backslash~{\tt defs}[n])\)

\( {\tt out}[n]={\tt in}[succ(n)]\)

Using the live-out information for the basic block as an initial value, we proceed in reverse order:

data Liveness = Liveness { ins :: !IS.IntSet, out :: !IS.IntSet, fins :: !IS.IntSet, fout :: !IS.IntSet }
    deriving (Eq)

data BB arch reg freg a b = BB { unBB :: [arch reg freg a], caBB :: b }

expand :: (E reg, E freg) => BB X86 reg freg () Liveness -> [X86 reg freg Liveness]
expand (BB asms@(\_:\_) li) = scanr (\n p -> lN n (ann p)) lS iasms
    where lN a s =
            let ai=uses a <> (ao IS.\\\ defs a)
                ao=ins s
                aif=usesF a <> (aof IS.\\\ defsF a)
                aof=fins s
            in a $> Liveness ai ao aif aof
          lS = let ao=out li
                   aof=fout li
               in asm $> Liveness (uses asm \`IS.union\` (ao \`IS.difference\` defs asm)) ao (usesF asm \`IS.union\` (aof \`IS.difference\` defsF asm)) aof
          (iasms, asm) = (init asms, last asms)
expand _ = []