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

Yep. Allocate in opposite order to execution, assume no branches / control flow / phi nodes. Single pass.

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.

> like if taller buildings always need more shafts or something

The dependence is on keeping wait times reasonable. Taller buildings mean each shaft's elevator spends more time travelling, i.e. less time being available.

At this point you start doing locals (multiple elevators per shaft traversing only a subset of the entire building) and express (elevators skipping floors, usually between ground floors and various "sky lobbies" at 30~40 floors interval).

Which still involves adding shafts.

There's also a weight issue. The longer the shaft, the longer and heavier the cable must be, and the more tension and stretch. In some buildings, there may also be structural issues militating against an open shaft running the entire heightof the buldng.

Taller buildings need more shafts because they'll spend more time in transit so unless the occupants have the patience of saints you need lots shafts to keep wait times down. Eventually most tall buildings setup sky lobbies and express lifts that only service a certain range of floors to keep wait times down during peak hours.

It's really rough in convention center hotels when a huge convention comes to town a lot of the time it's practically impossible to get an elevator down from the middle floors because it's already full from the floors above you.

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.

In the case of "let x = &xs[i]" it would immutably borrow. But we'd need more MIR optimizations to make use of that fact.

  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.]

Typo? PRE hoists upwards, so it would make sense to move closer to entry, not exit.

No, it's correct. It's saying "if they are always computed, we move them up".

IE

  if (a)
    foo = a + b
  else b 
    foo = a + b
  ->
  foo = a+b
  if (a)
  else (b)

Possible side effects correction:

    ->
      if (a)
      else (b)
      foo = a+b

How do you move up towards exit?

I think you have to read it like "executed on >all paths to the function exit< as early as possible". As in, if you have an expression that is always executed regardless which path you take before returning. It's useful to move that expression upwards instead of having copies on the different paths to the function exit.

My guess is that they meant "up" in the sense of "up in post dominator tree".

Naive question: if you move towards the exit of a function, wouldn't that be beneficial? That is, if a function terminates early, you're not evaluating the expressions unnecessarily, no?

In practice, you want to do both.IE hoist everything you can, sink everything you can.

But not because of "That is, if a function terminates early, you're not evaluating the expressions unnecessarily, no?"

If the function terminates early, and you've moved the expression computation before or after an early termination point, you've by definition changed what paths it is computed on (unless it was already computed there). That is not legal in all cases (it's speculative PRE/PDE)

PRE and VBE (which is what this is) guarantee that the expression is still computed at on the same paths. They just make it so it's computed once.

What is happening here is really a size optimization. If it can prove that it is always executed, it has one copy of the computation, instead of multiple ones.

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.

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

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

In any case, because the GCC implementation is written on top of a sane PRE infrastructure, it is like 50 lines of code to do this :)

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

Fine, it's what MLSM aspires to: http://llvm-cs.pcc.me.uk/lib/Transforms/Scalar/MergedLoadSto... (:

Writing "TODO: generalize to other regions" in a crazy N^3/N^4 approach to merging load/stores is like writing "TODO: solve prime number conjecture" in somebody's hand-rolled two's complement addition code.

Maybe it happens, but it ain't gonna happen with anything like this code :)