5 ms·

Inlining doesn't always work in side-effecting languages. E.g. only if `f` is pure are the following two fragments identical. let a = f () in a + a f

by tel 12y ago

Inlining doesn't always work in side-effecting languages. E.g. only if `f` is pure are the following two fragments identical. let a = f () in a + a f () + f ()

JoshTriplett 12y ago
If the compiler has the full source of f() available at compilation time, it knows whether it can convert between those two. (Though not all compilers are good at knowing the memory-usage implications of doing that kind of commoning operation.) (And, for that matter, whether it can convert that to "f()<<1".)
- mappu 12y ago
  Does `shl eax 1` really outperform `add eax eax`? Although i guess that's a question for `-mtune` to decide.
  - JoshTriplett 12y ago
    Shift definitely outperforms "mul"; it may or may not outperform "add", but it'll probably outperform a series of adds to implement a larger power of 2. And if you're using the result as part of an address, you can use [eax*2 + ...] as an operand and the shift will happen as part of addressing.
  - spc476 12y ago
    SHL EAX,1 and ADD EAX,EAX are the same, time wise. The only difference is that the A flag (auxiliary carry [1]) is undefined for SHL and defined for ADD. SHL EAX,n may be faster than n repeats of ADD EAX,EAX, but there are other ways to do quick multiplication by powers of 2 though. [1] The auxiliary carry reflects a borrow from bit 4 to bit 3, or a carry from bit 3 to bit 4. It's used for BCD [2] arithmetic, and there is is no direct way to test for it. [2] Binary Coded Decimal
- tel 12y ago
  Sure, and thus inlining does not always work. To be clear, what I probably should have said was beta reduction, but I wanted to keep the terminology of the op. The point being that one has to be aware of state in order to execute an inline/beta reduction. In pure and total[0] code the above can only ever change the execution speed, never the meaning. [0] And of course "pure and total" just means "pure" since non-termination is an effect.
kazinator 12y ago
Inlining always works, by definition, otherwise your compiler is buggy. In side effecting languages, inlining cannot make function calls disappear, unless the compiler can convince itself that it's safe to do so. If an expression calls f() twice, and f has a side effect, then the inlined version of the code has to do that side effect twice, exactly if the non-inlined function were called, just without some of the overhead of a function call. (On a different note, in a language like C, inlining a side effect actually improves safety. If we have f() { global++ } then f() + f() is safe and has the effect of incrementing global twice, whereas global++ + global++ is undefined behavior.)
- tel 12y ago
  Sorry, you're using a slightly different definition of inlining than I was. Fortunately, it still demonstrates the same point: you have to be aware of state/side effects in order to do inlining. In a pure and total language the two fragments are always the same. No further thought needed.
  - kazinator 12y ago
    Not really. Inlining can be done by mechanically incorporating the called function into the caller, in a way that respects lexical scopes. This will result in identical semantics. Then the resulting bloated code is optimized: subject to caching optimizations, common subexpression optimizations and whatnot. These have to obey the usual rules for not deleting or reordering side effects. The issue you're referring to boils down to the fact that in an imperative language, we cannot assume that two occurrences of a variable X can be replaced by the same value, because X may have been assigned in between. So compilers have to do flow analysis to discover in what part of a call graph does a given variable have a stable value. E.g. if we have a silly C function like int accumulate(int x, int y) { global += (x + y); } and then call it in two places: accumulate(s, t); accumulate(u, v); the inlining is almost like just macro-expansion of the above into: { int x = s; /* "parameter" passing */ int y = t; global += (x + y); } { int x = u; /* "parameter" passing */ int y = v; global += (x + y); } we don't have to care about side effects when we are doing this expansion. That's the job of later optimization. The later optimization pass can worry about things like whether global is volatile-qualified. If it is, then the best that can be done is: global += s + t; global += u + v; these can't be merged or re-ordered. And so this stays faithful to the original function calls. If global isn't volatile, then more can be done: global += s + t + u + v;
Guvante 12y ago
But that isn't the kind of inlining he is advocating. He is talking about f _ = do_work 12 let a = do_work 12 in a + a

by tel 12y ago

Inlining doesn't always work in side-effecting languages. E.g. only if `f` is pure are the following two fragments identical. let a = f () in a + a f () + f ()

JoshTriplett 12y ago

If the compiler has the full source of f() available at compilation time, it knows whether it can convert between those two. (Though not all compilers are good at knowing the memory-usage implications of doing that kind of commoning operation.) (And, for that matter, whether it can convert that to "f()<<1".)

mappu 12y ago
Does `shl eax 1` really outperform `add eax eax`? Although i guess that's a question for `-mtune` to decide.
- JoshTriplett 12y ago
  Shift definitely outperforms "mul"; it may or may not outperform "add", but it'll probably outperform a series of adds to implement a larger power of 2. And if you're using the result as part of an address, you can use [eax*2 + ...] as an operand and the shift will happen as part of addressing.
- spc476 12y ago
  SHL EAX,1 and ADD EAX,EAX are the same, time wise. The only difference is that the A flag (auxiliary carry [1]) is undefined for SHL and defined for ADD. SHL EAX,n may be faster than n repeats of ADD EAX,EAX, but there are other ways to do quick multiplication by powers of 2 though. [1] The auxiliary carry reflects a borrow from bit 4 to bit 3, or a carry from bit 3 to bit 4. It's used for BCD [2] arithmetic, and there is is no direct way to test for it. [2] Binary Coded Decimal
tel 12y ago
Sure, and thus inlining does not always work. To be clear, what I probably should have said was beta reduction, but I wanted to keep the terminology of the op. The point being that one has to be aware of state in order to execute an inline/beta reduction. In pure and total[0] code the above can only ever change the execution speed, never the meaning. [0] And of course "pure and total" just means "pure" since non-termination is an effect.

kazinator 12y ago

Inlining always works, by definition, otherwise your compiler is buggy. In side effecting languages, inlining cannot make function calls disappear, unless the compiler can convince itself that it's safe to do so. If an expression calls f() twice, and f has a side effect, then the inlined version of the code has to do that side effect twice, exactly if the non-inlined function were called, just without some of the overhead of a function call. (On a different note, in a language like C, inlining a side effect actually improves safety. If we have f() { global++ } then f() + f() is safe and has the effect of incrementing global twice, whereas global++ + global++ is undefined behavior.)

tel 12y ago
Sorry, you're using a slightly different definition of inlining than I was. Fortunately, it still demonstrates the same point: you have to be aware of state/side effects in order to do inlining. In a pure and total language the two fragments are always the same. No further thought needed.
- kazinator 12y ago
  Not really. Inlining can be done by mechanically incorporating the called function into the caller, in a way that respects lexical scopes. This will result in identical semantics. Then the resulting bloated code is optimized: subject to caching optimizations, common subexpression optimizations and whatnot. These have to obey the usual rules for not deleting or reordering side effects. The issue you're referring to boils down to the fact that in an imperative language, we cannot assume that two occurrences of a variable X can be replaced by the same value, because X may have been assigned in between. So compilers have to do flow analysis to discover in what part of a call graph does a given variable have a stable value. E.g. if we have a silly C function like int accumulate(int x, int y) { global += (x + y); } and then call it in two places: accumulate(s, t); accumulate(u, v); the inlining is almost like just macro-expansion of the above into: { int x = s; /* "parameter" passing */ int y = t; global += (x + y); } { int x = u; /* "parameter" passing */ int y = v; global += (x + y); } we don't have to care about side effects when we are doing this expansion. That's the job of later optimization. The later optimization pass can worry about things like whether global is volatile-qualified. If it is, then the best that can be done is: global += s + t; global += u + v; these can't be merged or re-ordered. And so this stays faithful to the original function calls. If global isn't volatile, then more can be done: global += s + t + u + v;

Guvante 12y ago

But that isn't the kind of inlining he is advocating. He is talking about f _ = do_work 12 let a = do_work 12 in a + a