3 ms·

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 expr

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?

mindleyhilner 10y ago
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.
- DannyBee 10y ago
  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 :)
  - mindleyhilner 10y ago
    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/MergedLoadStoreMotion.cpp#71 http://llvm-cs.pcc.me.uk/lib/Transforms/Scalar/MergedLoadSto... (:
    - DannyBee 10y ago
      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 :)
DannyBee 10y ago
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.

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?

mindleyhilner 10y ago

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.

DannyBee 10y ago
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 :)
- mindleyhilner 10y ago
  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/MergedLoadStoreMotion.cpp#71 http://llvm-cs.pcc.me.uk/lib/Transforms/Scalar/MergedLoadSto... (:
  - DannyBee 10y ago
    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 :)

DannyBee 10y ago

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.