common-subexpression elimination (cse)

[Stephen Weeks]

--zHkd1lCaSw
Content-Type: text/plain; charset=us-ascii
Content-Description: message body text
Content-Transfer-Encoding: 7bit


> But  that  (just replacing latter occurances with the name bound to the first
> result) isn't always correct.

Let me be more precise.  The later occurrences are replaced if the primitive is
functional (or may overflow) and the first occurrence dominates them in the
intraprocedural control-flow graph.  I believe this is safe.

> There is, of course, side effect things  which
> have  to  be duplicated, but the more serious example I was talking about was
> the delay due to lambda.
> 
> Consider something like
> 
>     let val magic: (unit -> int) option ref = ref NONE
>         fun f x =
>                (magic := SOME (fn () => 1 div x);
>                 1 div x)
>     in f 0
>           handle _ => 0;
>        valOf (! magic) ()
>     end
> 
> You have to raise the exception twice.

Agreed.  MLton simplifies this quite nicely.  Just to show off my fine new
control-flow graph feature, here is the control-flow graph that MLton produces
(not suitable for printing, just for viewing).  The important stuff is near the
top, starting at L_38.



--zHkd1lCaSw
Content-Type: application/octet-stream
Content-Disposition: attachment;
	filename="z.sml.main_0.dot"
Content-Transfer-Encoding: base64

ZGlncmFwaCAibWFpbl8wIiB7CmxhYmVsID0gIm1haW5fMCI7IHsgcmFuayAgPSAibWluIjsgbjAg
fQpuMSBbbGFiZWwgPSAiTF81KHhfNTEpIFtMXzVdXGxIYW5kbGVyUG9wXGx4XzUzID0gU3RkaW9f
cHJpbnQgKFwiVG9wbGV2ZWwgaGFuZGxlciByYWlzZWQgZXhjZXB0aW9uLlxuXCIpXGx4XzUyID0g
TUx0b25faGFsdCAoMSlcbHJldHVybiAoKVxsIiwgc2hhcGUgPSAiYm94Il0KbjIgW2xhYmVsID0g
IkxfOCgpIFtdXGxMXzQgKFwiT3ZlcmZsb3dcIilcbCIsIHNoYXBlID0gImJveCJdCm4yIC0+IG4z
IFtsYWJlbCA9ICIiLCBzdHlsZSA9ICJzb2xpZCJdCm40IFtsYWJlbCA9ICJMXzEwKCkgW11cbExf
NCAoXCJEaXZcIilcbCIsIHNoYXBlID0gImJveCJdCm40IC0+IG4zIFtsYWJlbCA9ICIiLCBzdHls
ZSA9ICJzb2xpZCJdCm41IFtsYWJlbCA9ICJMXzU0KHhfNDUpIFtdXGxMXzQgKFwiRmFpbFwiKVxs
Iiwgc2hhcGUgPSAiYm94Il0KbjUgLT4gbjMgW2xhYmVsID0gIiIsIHN0eWxlID0gInNvbGlkIl0K
bjYgW2xhYmVsID0gIkxfMTMoKSBbXVxsTF80IChcIk9wdGlvblwiKVxsIiwgc2hhcGUgPSAiYm94
Il0KbjYgLT4gbjMgW2xhYmVsID0gIiIsIHN0eWxlID0gInNvbGlkIl0KbjMgW2xhYmVsID0gIkxf
NCh4XzQ2KSBbXVxsSGFuZGxlclB1c2ggTF81XGx4XzUwID0gU3RkaW9fcHJpbnQgKFwidW5oYW5k
bGVkIGV4Y2VwdGlvbiBcIilcbHhfNDkgPSBTdGRpb19wcmludCAoeF80NilcbHhfNDggPSBTdGRp
b19wcmludCAoXCJcblwiKVxseF80NyA9IE1MdG9uX2hhbHQgKDEpXGxyYWlzZSAoRmFpbF8wKC4u
LikpXGwiLCBzaGFwZSA9ICJib3giXQpuNyBbbGFiZWwgPSAiTF81MigpIFtdXGx4XzQyID0gU3Ry
aW5nX3N1YiAoeF8zMix4XzMzKVxseF80MCA9IHhfMzMgKyAxXGx4XzQxID0gQXJyYXlfdXBkYXRl
ICh4XzI0LHhfMjkseF80MilcbHhfMzkgPSB4XzI5ICsgMVxsbG9vcF81ICh4XzMxLHhfMzIseF80
MCx4XzM5KVxsIiwgc2hhcGUgPSAiYm94Il0KbjcgLT4gbjggW2xhYmVsID0gIk92ZXJmbG93Iiwg
c3R5bGUgPSAiZGFzaGVkIl0KbjcgLT4gbjggW2xhYmVsID0gIk92ZXJmbG93Iiwgc3R5bGUgPSAi
ZGFzaGVkIl0KbjcgLT4gbjkgW2xhYmVsID0gIiIsIHN0eWxlID0gInNvbGlkIl0KbjEwIFtsYWJl
bCA9ICJMXzUwKHhfMzYseF8zNykgW11cbGxvb3BfNiAoeF8zNix4XzM3LDApXGwiLCBzaGFwZSA9
ICJib3giXQpuMTAgLT4gbjExIFtsYWJlbCA9ICIiLCBzdHlsZSA9ICJzb2xpZCJdCm4xMiBbbGFi
ZWwgPSAiTF81MSgpIFtdXGx4XzM4ID0geF8zMyA+PXUgeF8zNVxsY2FzZSB4XzM4XGwiLCBzaGFw
ZSA9ICJib3giXQpuMTIgLT4gbjggW2xhYmVsID0gInRydWUiLCBzdHlsZSA9ICJzb2xpZCJdCm4x
MiAtPiBuNyBbbGFiZWwgPSAiZmFsc2UiLCBzdHlsZSA9ICJzb2xpZCJdCm4xMyBbbGFiZWwgPSAi
TF80OSgpIFtdXGxjYXNlIHhfMzFcbCIsIHNoYXBlID0gImJveCJdCm4xMyAtPiBuOCBbbGFiZWwg
PSAibmlsXzEiLCBzdHlsZSA9ICJzb2xpZCJdCm4xMyAtPiBuMTAgW2xhYmVsID0gIjo6XzEiLCBz
dHlsZSA9ICJzb2xpZCJdCm4xMSBbbGFiZWwgPSAibG9vcF82KHhfMzEseF8zMix4XzMzKSBbXVxs
eF8zNSA9IHNpemUgeF8zMlxseF8zNCA9IHhfMzMgPCB4XzM1XGxjYXNlIHhfMzRcbCIsIHNoYXBl
ID0gImJveCJdCm4xMSAtPiBuMTIgW2xhYmVsID0gInRydWUiLCBzdHlsZSA9ICJzb2xpZCJdCm4x
MSAtPiBuMTMgW2xhYmVsID0gImZhbHNlIiwgc3R5bGUgPSAic29saWQiXQpuMTQgW2xhYmVsID0g
IkxfNTMoKSBbXVxseF80NCA9IFZlY3Rvcl9mcm9tQXJyYXkgKHhfMjQpXGx4XzQzID0gU3RyaW5n
X2Zyb21DaGFyVmVjdG9yICh4XzQ0KVxsTF80ICh4XzQzKVxsIiwgc2hhcGUgPSAiYm94Il0KbjE0
IC0+IG4zIFtsYWJlbCA9ICIiLCBzdHlsZSA9ICJzb2xpZCJdCm4xNSBbbGFiZWwgPSAiTF80OCgp
IFtdXGxsb29wXzYgKHhfMjYseF8yNyx4XzI4KVxsIiwgc2hhcGUgPSAiYm94Il0KbjE1IC0+IG4x
MSBbbGFiZWwgPSAiIiwgc3R5bGUgPSAic29saWQiXQpuOSBbbGFiZWwgPSAibG9vcF81KHhfMjYs
eF8yNyx4XzI4LHhfMjkpIFtdXGx4XzMwID0geF8yOSA9IHhfMTVcbGNhc2UgeF8zMFxsIiwgc2hh
cGUgPSAiYm94Il0KbjkgLT4gbjE0IFtsYWJlbCA9ICJ0cnVlIiwgc3R5bGUgPSAic29saWQiXQpu
OSAtPiBuMTUgW2xhYmVsID0gImZhbHNlIiwgc3R5bGUgPSAic29saWQiXQpuMTYgW2xhYmVsID0g
IkxfNDcoKSBbXVxseF8yMyA9IEFycmF5X2FycmF5ICh4XzE1KVxsTF80NSAoeF8yMylcbCIsIHNo
YXBlID0gImJveCJdCm4xNiAtPiBuMTcgW2xhYmVsID0gIiIsIHN0eWxlID0gInNvbGlkIl0KbjE3
IFtsYWJlbCA9ICJMXzQ1KHhfMjQpIFtdXGxsb29wXzUgKHhfMjUsXCJGYWlsIFwiLDAsMClcbCIs
IHNoYXBlID0gImJveCJdCm4xNyAtPiBuOSBbbGFiZWwgPSAiIiwgc3R5bGUgPSAic29saWQiXQpu
MTggW2xhYmVsID0gIkxfNDQoKSBbXVxsTF80NSAoZ2xvYmFsXzI3KVxsIiwgc2hhcGUgPSAiYm94
Il0KbjE4IC0+IG4xNyBbbGFiZWwgPSAiIiwgc3R5bGUgPSAic29saWQiXQpuMTkgW2xhYmVsID0g
IkxfNDYoKSBbXVxseF8yMiA9IHhfMTUgPj11IDEwNzM3NDE4MjNcbGNhc2UgeF8yMlxsIiwgc2hh
cGUgPSAiYm94Il0KbjE5IC0+IG44IFtsYWJlbCA9ICJ0cnVlIiwgc3R5bGUgPSAic29saWQiXQpu
MTkgLT4gbjE2IFtsYWJlbCA9ICJmYWxzZSIsIHN0eWxlID0gInNvbGlkIl0KbjggW2xhYmVsID0g
IkxfMCgpIFtdXGx4XzU0ID0gTUx0b25fYnVnIChcInRvcGxldmVsIGhhbmRsZXIgbm90IGluc3Rh
bGxlZFwiKVxscmV0dXJuICgpXGwiLCBzaGFwZSA9ICJib3giXQpuMjAgW2xhYmVsID0gIkxfNDMo
KSBbXVxseF8yMSA9IDAgPSB4XzE1XGxjYXNlIHhfMjFcbCIsIHNoYXBlID0gImJveCJdCm4yMCAt
PiBuMTggW2xhYmVsID0gInRydWUiLCBzdHlsZSA9ICJzb2xpZCJdCm4yMCAtPiBuMTkgW2xhYmVs
ID0gImZhbHNlIiwgc3R5bGUgPSAic29saWQiXQpuMjEgW2xhYmVsID0gIkxfNDIoeF8xNyx4XzE4
KSBbXVxseF8yMCA9IHNpemUgeF8xOFxseF8xOSA9IHhfMjAgKyB4XzE1XGxsb29wXzQgKHhfMTks
eF8xNylcbCIsIHNoYXBlID0gImJveCJdCm4yMSAtPiBuOCBbbGFiZWwgPSAiT3ZlcmZsb3ciLCBz
dHlsZSA9ICJkYXNoZWQiXQpuMjEgLT4gbjIyIFtsYWJlbCA9ICIiLCBzdHlsZSA9ICJzb2xpZCJd
Cm4yMiBbbGFiZWwgPSAibG9vcF80KHhfMTUseF8xNikgW11cbGNhc2UgeF8xNlxsIiwgc2hhcGUg
PSAiYm94Il0KbjIyIC0+IG4yMCBbbGFiZWwgPSAibmlsXzEiLCBzdHlsZSA9ICJzb2xpZCJdCm4y
MiAtPiBuMjEgW2xhYmVsID0gIjo6XzEiLCBzdHlsZSA9ICJzb2xpZCJdCm4yMyBbbGFiZWwgPSAi
TF8xNCgpIFtdXGxjYXNlIHhfMTBcbCIsIHNoYXBlID0gImJveCJdCm4yMyAtPiBuMiBbbGFiZWwg
PSAiT3ZlcmZsb3ciLCBzdHlsZSA9ICJzb2xpZCJdCm4yMyAtPiBuNCBbbGFiZWwgPSAiRGl2XzAi
LCBzdHlsZSA9ICJzb2xpZCJdCm4yMyAtPiBuNSBbbGFiZWwgPSAiRmFpbF8wIiwgc3R5bGUgPSAi
c29saWQiXQpuMjMgLT4gbjYgW2xhYmVsID0gIk9wdGlvbl8wIiwgc3R5bGUgPSAic29saWQiXQpu
MjQgW2xhYmVsID0gIkxfMTUoeF8xMykgW11cbHhfMjUgPSA6Ol8xIChuaWxfMSx4XzEzKVxseF8x
NCA9IDo6XzEgKHhfMjUsXCJGYWlsIFwiKVxsbG9vcF80ICgwLHhfMTQpXGwiLCBzaGFwZSA9ICJi
b3giXQpuMjQgLT4gbjIyIFtsYWJlbCA9ICIiLCBzdHlsZSA9ICJzb2xpZCJdCm4yNSBbbGFiZWwg
PSAiTF8zKCkgW11cbGNhc2UgeF8xMFxsIiwgc2hhcGUgPSAiYm94Il0KbjI1IC0+IG4yMyBbbGFi
ZWwgPSAiZGVmYXVsdCIsIHN0eWxlID0gInNvbGlkIl0KbjI1IC0+IG4yNCBbbGFiZWwgPSAiRmFp
bF8wIiwgc3R5bGUgPSAic29saWQiXQpuMjYgW2xhYmVsID0gIkxfMTgoKSBbXVxseF8xMiA9IE1M
dG9uX2J1ZyAoXCJ0b3BsZXZlbCBoYW5kbGVyIG5vdCBpbnN0YWxsZWRcIilcbHJldHVybiAoKVxs
Iiwgc2hhcGUgPSAiYm94Il0KbjI3IFtsYWJlbCA9ICJMXzI2KCkgW11cbExfMiAoT3B0aW9uXzAp
XGwiLCBzaGFwZSA9ICJib3giXQpuMjcgLT4gbjI4IFtsYWJlbCA9ICIiLCBzdHlsZSA9ICJzb2xp
ZCJdCm4yOSBbbGFiZWwgPSAiTF8yNSgpIFtdXGxMXzIgKERpdl8wKVxsIiwgc2hhcGUgPSAiYm94
Il0KbjI5IC0+IG4yOCBbbGFiZWwgPSAiIiwgc3R5bGUgPSAic29saWQiXQpuMjggW2xhYmVsID0g
IkxfMih4XzEwKSBbXVxseF8xMSA9ICEgeF8xXGxjYXNlIHhfMTFcbCIsIHNoYXBlID0gImJveCJd
Cm4yOCAtPiBuMjUgW2xhYmVsID0gIkVudl8xIiwgc3R5bGUgPSAic29saWQiXQpuMjggLT4gbjI2
IFtsYWJlbCA9ICJFbnZfMCIsIHN0eWxlID0gInNvbGlkIl0KbjMwIFtsYWJlbCA9ICJMXzQwKCkg
W11cbExfMiAoT3ZlcmZsb3cpXGwiLCBzaGFwZSA9ICJib3giXQpuMzAgLT4gbjI4IFtsYWJlbCA9
ICIiLCBzdHlsZSA9ICJzb2xpZCJdCm4zMSBbbGFiZWwgPSAiTF8zOCgpIFtdXGx4XzkgPSBFbnZf
MSAoKVxseF84ID0geF8xIDo9IHhfOVxsbWFnaWNfMCA9IHJlZiBkdW1teV8wXGx4XzcgPSBtYWdp
Y18wIDo9IFNPTUVfMFxseF82ID0gISBtYWdpY18wXGxjYXNlIHhfNlxsIiwgc2hhcGUgPSAiYm94
Il0KbjMxIC0+IG4yNyBbbGFiZWwgPSAiZGVmYXVsdCIsIHN0eWxlID0gInNvbGlkIl0KbjMxIC0+
IG4yOSBbbGFiZWwgPSAiU09NRV8wIiwgc3R5bGUgPSAic29saWQiXQpuMzIgW2xhYmVsID0gIkxf
MzkoKSBbXVxseF81ID0geF8zICsgMVxsbG9vcF8zICh4XzUpXGwiLCBzaGFwZSA9ICJib3giXQpu
MzIgLT4gbjMwIFtsYWJlbCA9ICJPdmVyZmxvdyIsIHN0eWxlID0gImRhc2hlZCJdCm4zMiAtPiBu
MzMgW2xhYmVsID0gIiIsIHN0eWxlID0gInNvbGlkIl0KbjMzIFtsYWJlbCA9ICJsb29wXzMoeF8z
KSBbXVxseF80ID0gMCA9IHhfM1xsY2FzZSB4XzRcbCIsIHNoYXBlID0gImJveCJdCm4zMyAtPiBu
MzEgW2xhYmVsID0gInRydWUiLCBzdHlsZSA9ICJzb2xpZCJdCm4zMyAtPiBuMzIgW2xhYmVsID0g
ImZhbHNlIiwgc3R5bGUgPSAic29saWQiXQpuMzQgW2xhYmVsID0gIkxfMTkoKSBbXVxsbG9vcF8z
ICgwKVxsIiwgc2hhcGUgPSAiYm94Il0KbjM0IC0+IG4zMyBbbGFiZWwgPSAiIiwgc3R5bGUgPSAi
c29saWQiXQpuMzUgW2xhYmVsID0gImxvb3BfMCh4XzIpIFtdXGxjYXNlIHhfMlxsIiwgc2hhcGUg
PSAiYm94Il0KbjM1IC0+IG4zNCBbbGFiZWwgPSAibmlsXzAiLCBzdHlsZSA9ICJzb2xpZCJdCm4z
NSAtPiBuMzUgW2xhYmVsID0gIjo6XzAiLCBzdHlsZSA9ICJzb2xpZCJdCm4wIFtsYWJlbCA9ICJt
YWluXzBcbGxvb3BfMCAoOjpfMCguLi4pKVxsIiwgc2hhcGUgPSAiYm94Il0KbjAgLT4gbjM1IFts
YWJlbCA9ICIiLCBzdHlsZSA9ICJzb2xpZCJdCn0K

--zHkd1lCaSw--