Avoid code duplication for argument evaluation
Motivation
Consider a function with multiple arguments, in which all arguments will be evaluated on all branches. As we branch we evaluate arguments as we need them.
A simple example might look like this:
myFoo :: Bool -> Bool -> Int
myFoo x y =
case x of
True -> case y of
True -> 1
False -> 2
False -> case y of
True -> 3
False -> 4
What is bad about this code becomes clear if we write it out in pseudo C:
x = EVAL(x);
if(x==True) {
y = EVAL(y);
if(y==True) {
return 1;
} else {
return 2;
}
} else {
y = EVAL(y);
if(y==True) {
return 3;
} else {
return 4;
}
}
Here we duplicate the code for y = EVAL(y)
into both branches.
Ideally we would pull out y = EVAL(y)
from the branches and just generate code like this:
x = EVAL(x);
y = EVAL(y);
if(x == True) {
if(y == True) {
...
The call itself isn't really an issue.
But we also end up duplicating any register allocation related instructions along with the call stack setup which makes this a non-trivial cost. Especially if we have many live variables.
Solutions?
I don't have clear idea how to solve this.
In Core the model of what is evaluated is not strict enough to express this.
In Cmm I think trying to do this transformation would be prohibitively expensive.
In STG it is possible to express the code we want like this:
myFoo x y =
case x of x' { DEFAULT ->
case y of y' { DEFAULT ->
case x' of {
True -> case y' of {
True -> 1;
False -> 2; }
False -> case y' of {
True -> 3;
False -> 4; }
}}}
But it's not trivial to determine when and how we could reasonably transform code like this.
Anyway I came across this deficiency recently and thought it would be to document it properly.