+++
title = "Kildall's algorithm"
author = "Yann Herklotz"
tags = []
categories = []
backlinks = ["2e1"]
forwardlinks = ["2e1b", "2e1a1"]
zettelid = "2e1a"
+++

-   Each instruction has a pool, which represents information that the
    compiler knows at the time that function is executed.
-   The algorithm has a "work set" which at the start consists of at
    least one instruction
-   The algorithm returns a map from instructions to pools
-   Goes through the control flow graph and updates the pool for each
    instruction
-   At every iteration, one instruction is taken from the "work set",
    and associated with the pool that is the meet of the pool in the map
    and the pool it was associated with in the "work set".
-   Then the optimisation function is called on the current instruction
    and its pool

\[1\]

<div id="refs" class="references csl-bib-body" markdown="1">

<div id="ref-kildall73_unified_approac_global_progr_optim"
class="csl-entry" markdown="1">

<span class="csl-left-margin">\[1\]
</span><span class="csl-right-inline">G. A. Kildall, “A unified approach
to global program optimization,” in *Proceedings of the 1st annual ACM
SIGACT-SIGPLAN symposium on principles of programming languages*, in
POPL ’73. Boston, Massachusetts: Association for Computing Machinery,
1973, pp. 194–206. doi: [10.1145/512927.512945].</span>

</div>

</div>

  [10.1145/512927.512945]: https://doi.org/10.1145/512927.512945