mindleyhilner

Just skimmed, central idea is to linear scan in reverse?

Paper: http://people.csail.mit.edu/lamanda/assets/documents/LiuPOPL...

Small typo:

    --- before      2018-01-31 17:12:13.626560688 -0800
    +++ after       2018-01-31 17:12:17.494580179 -0800
    @@ -1 +1 @@
    -uint32_t buf = mmap(NULL, len, PROT_READ | PROT_WRITE, MAP_SHARED, fb, 0);
    +uint32_t *buf = mmap(NULL, len, PROT_READ | PROT_WRITE, MAP_SHARED, fb, 0);

Sorry to sound stupid, but how is that exponential? Isn't it O(mn) where m = number of floors and n = number of shafts?

EDIT: Unless there's some dependence between m and n, like if taller buildings always need more shafts or something.

Small typo: "hunt-and-pack" should be "hunt-and-peck."

Doesn't `let x = xs[i]` immutably borrow from xs? So for the duration of x's lifetime (which is the entire for-body block), xs cannot be changed and therefore its length must remain the same.

Though this might be information that rustc knows about but not LLVM.

  It's actually not. It's what GVNHoist does, but not MLSM. MLSM only handles diamonds.

How do you move up towards exit?

The point of hoisting towards entry is to reduce code size, as the changelog indicates. It's safe to hoist the expression from program points P_{0..i..n-1} to some point Q that dominates all P_i if the expression is available at each P_i. That reduces the number of occurrences by n - 1. It's a basic corollary of PRE.

This is identical to what LLVM's load-store motion does for loads, except for all expressions and not just loads.

  It attempts to move evaluation of expressions executed on all paths to the function *exit* as early as possible, which helps primarily for code size, but can be useful for speed of generated code as well. [Emphasis added.]