Does GHC do dead code elimination? I observe that if you take a module and edit it so that some function is now no longer exported or called by any exported function, the size of the *.o file seems to go down. This suggests that dead code within a single module is eliminated. However... how about this? module Foo where f = ... g = ... h = ... module Main where import Foo main = ...f... Will the generated executable contain the code for g and h, even though they aren't called? Or does the unused code get eliminated? How about the standard libraries? I read somewhere that if one funtion returns a tuple, and the caller immediately extracts the values from the tuple, GHC tries to optimise away the tuple - so it's as if the function can just return multiple values at once. Is this true? Does it apply only to tuples, or to all types?
On Mon, Aug 13, 2007 at 07:05:03PM +0100, Andrew Coppin wrote:
Does GHC do dead code elimination?
Yes - all unused let-binders are removed.
I observe that if you take a module and edit it so that some function is now no longer exported or called by any exported function, the size of the *.o file seems to go down. This suggests that dead code within a single module is eliminated.
However... how about this?
module Foo where
f = ... g = ... h = ...
module Main where
import Foo
main = ...f...
Will the generated executable contain the code for g and h, even though they aren't called? Or does the unused code get eliminated? How about the standard libraries?
By default, GHC generates one object file per source module, so if any values from that module are used, the entire module is linked in. With the -split-objs flag, GHC generates one object file per top level function, sometimes significantly reducing the size of executables. This is not the default because it puts tremendous strain on the linker. It is common to spend several *minutes* linking base when compiling ghc, and it's not unheard of for ar to simply run out of memory and die.
I read somewhere that if one funtion returns a tuple, and the caller immediately extracts the values from the tuple, GHC tries to optimise away the tuple - so it's as if the function can just return multiple values at once. Is this true? Does it apply only to tuples, or to all types?
This is called the Constructed Product Return (CPR) analysis, and it applies to all types with one constructor (in archaic jargon, product types). For instance, (+) (I# x#) (I# y#) = I# (x# +# y#) foo = case 2 + 2 of I# x# -> ... is transformed into: zdzp (I# x#) (I# y#) = (x# +# y#) foo = case 2 + 2 of x# -> ... This is one of the two main pillars of arithmetic unboxing, alongside and equally important to strictness analysis. Stefan
Stefan O'Rear wrote:
On Mon, Aug 13, 2007 at 07:05:03PM +0100, Andrew Coppin wrote:
Does GHC do dead code elimination?
Yes - all unused let-binders are removed.
Not related to optimisation, but... is there some switch to warn you if something gets removed? (Presumably this means you forgot to export something, or you haven't coded the bit that calls it yet or something.)
Will the generated executable contain the code for g and h, even though they aren't called? Or does the unused code get eliminated? How about the standard libraries?
By default, GHC generates one object file per source module, so if any values from that module are used, the entire module is linked in.
Right, OK. I had a feeling that was the case. (I once compiled a program that used the GHC API. The final binary was several times larger than ghc.exe...)
With the -split-objs flag, GHC generates one object file per top level function, sometimes significantly reducing the size of executables. This is not the default because it puts tremendous strain on the linker. It is common to spend several *minutes* linking base when compiling ghc, and it's not unheard of for ar to simply run out of memory and die.
Ouch! o_O Probably simpler for me, as a human, to split the program into a sensible module structure... ;-)
I read somewhere that if one funtion returns a tuple, and the caller immediately extracts the values from the tuple, GHC tries to optimise away the tuple - so it's as if the function can just return multiple values at once. Is this true? Does it apply only to tuples, or to all types?
This is called the Constructed Product Return (CPR) analysis, and it applies to all types with one constructor (in archaic jargon, product types).
Right. So it doesn't have to have strict fields or anything? Just has to have exactly one constructor?
On Mon, Aug 13, 2007 at 07:35:31PM +0100, Andrew Coppin wrote:
Not related to optimisation, but... is there some switch to warn you if something gets removed? (Presumably this means you forgot to export something, or you haven't coded the bit that calls it yet or something.)
-fwarn-unused-binds (included in -Wall)
(I once compiled a program that used the GHC API. The final binary was several times larger than ghc.exe...)
GHC is a particularly bad case because what it does is determined by the settings of a bunch of switches in the configuration data. Of course, GHC isn't smart enough to perform inter-module control flow analysis, so even with -split-objs you'd probably still link most of GHC.
I read somewhere that if one funtion returns a tuple, and the caller immediately extracts the values from the tuple, GHC tries to optimise away the tuple - so it's as if the function can just return multiple values at once. Is this true? Does it apply only to tuples, or to all types?
This is called the Constructed Product Return (CPR) analysis, and it applies to all types with one constructor (in archaic jargon, product types).
Right. So it doesn't have to have strict fields or anything? Just has to have exactly one constructor?
Yep, CPR is completely independent of strictness, however the returned product must be *new*, since returning an old object by value risks losing sharing (and thus creating large memory leaks). Stefan
Stefan O'Rear wrote:
On Mon, Aug 13, 2007 at 07:35:31PM +0100, Andrew Coppin wrote:
(I once compiled a program that used the GHC API. The final binary was several times larger than ghc.exe...)
GHC is a particularly bad case because what it does is determined by the settings of a bunch of switches in the configuration data. Of course, GHC isn't smart enough to perform inter-module control flow analysis, so even with -split-objs you'd probably still link most of GHC.
Is it likely that GHC will ever become "smart enough" to do that kind of analysis? (I imagine this is going to be especially fun with precompiled libraries...)
This is called the Constructed Product Return (CPR) analysis, and it applies to all types with one constructor (in archaic jargon, product types).
Right. So it doesn't have to have strict fields or anything? Just has to have exactly one constructor?
Yep, CPR is completely independent of strictness, however the returned product must be *new*, since returning an old object by value risks losing sharing (and thus creating large memory leaks).
Right, OK.
participants (2)
-
Andrew Coppin -
Stefan O'Rear