MLton

CommonArg is an optimization pass for the SSA IntermediateLanguage, invoked from SSASimplify.

Description

It optimizes instances of Goto transfers that pass the same arguments to the same label; e.g.

L_1 ()
  ...
  z1 = ?
  ...
  L_3 (x, y, z1)
L_2 ()
  ...
  z2 = ?
  ...
  L_3 (x, y, z2)
L_3 (a, b, c)
  ...

This code can be simplified to:

L_1 ()
  ...
  z1 = ?
  ...
  L_3 (z1)
L_2 ()
  ...
  z2 = ?
  ...
  L_3 (z2)
L_3 (c)
  a = x
  b = y

which saves a number of resources: time of setting up the arguments for the jump to L_3, space (either stack slots or temporaries) for the arguments of L_3, etc. It may also expose some other optimizations, if more information is known about x or y.

Implementation

Details and Notes

Three analyses were originally proposed to drive the optimization transformation. Only the Dominator Analysis is currently implemented. (Implementations of the other analyses are available in the repository history.)

Syntactic Analysis

The simplest analysis I could think of maintains

varInfo: Var.t -> Var.t option list ref

initialized to [].

  • For each variable v bound in a Statement.t or in the Function.t args, then List.push(varInfo v, NONE).

  • For each L (x1, …​, xn) transfer where (a1, …​, an) are the formals of L, then List.push(varInfo ai, SOME xi).

  • For each block argument a used in an unknown context (e.g., arguments of blocks used as continuations, handlers, arith success, runtime return, or case switch labels), then List.push(varInfo a, NONE).

Now, any block argument a such that varInfo a = xs, where all of the elements of xs are equal to SOME x, can be optimized by setting a = x at the beginning of the block and dropping the argument from Goto transfers.

That takes care of the example above. We can clearly do slightly better, by changing the transformation criteria to the following: any block argument a such that varInfo a = xs, where all of the elements of xs are equal to SOME x or are equal to SOME a, can be optimized by setting a = x at the beginning of the block and dropping the argument from Goto transfers. This optimizes a case like:

L_1 ()
  ... z1 = ? ...
  L_3 (x, y, z1)
L_2 ()
  ... z2 = ? ...
  L_3(x, y, z2)
L_3 (a, b, c)
  ... w = ? ...
  case w of
    true => L_4 | false => L_5
L_4 ()
   ...
   L_3 (a, b, w)
L_5 ()
   ...

where a common argument is passed to a loop (and is invariant through the loop). Of course, the LoopInvariant optimization pass would normally introduce a local loop and essentially reduce this to the first example, but I have seen this in practice, which suggests that some optimizations after LoopInvariant do enough simplifications to introduce (new) loop invariant arguments.

Fixpoint Analysis

However, the above analysis and transformation doesn’t cover the cases where eliminating one common argument exposes the opportunity to eliminate other common arguments. For example:

L_1 ()
  ...
  L_3 (x)
L_2 ()
  ...
  L_3 (x)
L_3 (a)
  ...
  L_5 (a)
L_4 ()
  ...
  L_5 (x)
L_5 (b)
  ...

One pass of analysis and transformation would eliminate the argument to L_3 and rewrite the L_5(a) transfer to L_5 (x), thereby exposing the opportunity to eliminate the common argument to L_5.

The interdependency the arguments to L_3 and L_5 suggest performing some sort of fixed-point analysis. This analysis is relatively simple; maintain

varInfo: Var.t -> VarLattice.t

where

VarLattice.t ~=~ Bot | Point of Var.t | Top

(but is implemented by the FlatLattice functor with a lessThan list and value ref under the hood), initialized to Bot.

  • For each variable v bound in a Statement.t or in the Function.t args, then VarLattice.⇐ (Point v, varInfo v)

  • For each L (x1, …​, xn) transfer where (a1, …​, an) are the formals of L}, then VarLattice.⇐ (varInfo xi, varInfo ai).

  • For each block argument a used in an unknown context, then VarLattice.⇐ (Point a, varInfo a).

Now, any block argument a such that varInfo a = Point x can be optimized by setting a = x at the beginning of the block and dropping the argument from Goto transfers.

Now, with the last example, we introduce the ordering constraints:

varInfo x <= varInfo a
varInfo a <= varInfo b
varInfo x <= varInfo b

Assuming that varInfo x = Point x, then we get varInfo a = Point x and varInfo b = Point x, and we optimize the example as desired.

But, that is a rather weak assumption. It’s quite possible for varInfo x = Top. For example, consider:

G_1 ()
  ... n = 1 ...
  L_0 (n)
G_2 ()
  ... m = 2 ...
  L_0 (m)
L_0 (x)
  ...
L_1 ()
  ...
  L_3 (x)
L_2 ()
  ...
  L_3 (x)
L_3 (a)
  ...
  L_5(a)
L_4 ()
  ...
  L_5(x)
L_5 (b)
   ...

Now varInfo x = varInfo a = varInfo b = Top. What went wrong here? When varInfo x went to Top, it got propagated all the way through to a and b, and prevented the elimination of any common arguments. What we’d like to do instead is when varInfo x goes to Top, propagate on Point x — we have no hope of eliminating x, but if we hold x constant, then we have a chance of eliminating arguments for which x is passed as an actual.

Dominator Analysis

Does anyone see where this is going yet? Pausing for a little thought, MatthewFluet realized that he had once before tried proposing this kind of "fix" to a fixed-point analysis — when we were first investigating the Contify optimization in light of John Reppy’s CWS paper. Of course, that "fix" failed because it defined a non-monotonic function and one couldn’t take the fixed point. But, StephenWeeks suggested a dominator based approach, and we were able to show that, indeed, the dominator analysis subsumed both the previous call based analysis and the cont based analysis. And, a moment’s reflection reveals further parallels: when varInfo: Var.t -> Var.t option list ref, we have something analogous to the call analysis, and when varInfo: Var.t -> VarLattice.t, we have something analogous to the cont analysis. Maybe there is something analogous to the dominator approach (and therefore superior to the previous analyses).

And this turns out to be the case. Construct the graph G as follows:

nodes(G) = {Root} U Var.t
edges(G) = {Root -> v | v bound in a Statement.t or
                                in the Function.t args} U
           {xi -> ai | L(x1, ..., xn) transfer where (a1, ..., an)
                                      are the formals of L} U
           {Root -> a | a is a block argument used in an unknown context}

Let idom(x) be the immediate dominator of x in G with root Root. Now, any block argument a such that idom(a) = x <> Root can be optimized by setting a = x at the beginning of the block and dropping the argument from Goto transfers.

Furthermore, experimental evidence suggests (and we are confident that a formal presentation could prove) that the dominator analysis subsumes the "syntactic" and "fixpoint" based analyses in this context as well and that the dominator analysis gets "everything" in one go.

Final Thoughts

I must admit, I was rather surprised at this progression and final result. At the outset, I never would have thought of a connection between Contify and CommonArg optimizations. They would seem to be two completely different optimizations. Although, this may not really be the case. As one of the reviewers of the ICFP paper said:

I understand that such a form of CPS might be convenient in some cases, but when we’re talking about analyzing code to detect that some continuation is constant, I think it makes a lot more sense to make all the continuation arguments completely explicit.

I believe that making all the continuation arguments explicit will show that the optimization can be generalized to eliminating constant arguments, whether continuations or not.

What I think the common argument optimization shows is that the dominator analysis does slightly better than the reviewer puts it: we find more than just constant continuations, we find common continuations. And I think this is further justified by the fact that I have observed common argument eliminate some env_X arguments which would appear to correspond to determining that while the closure being executed isn’t constant it is at least the same as the closure being passed elsewhere.

At first, I was curious whether or not we had missed a bigger picture with the dominator analysis. When we wrote the contification paper, I assumed that the dominator analysis was a specialized solution to a specialized problem; we never suggested that it was a technique suited to a larger class of analyses. After initially finding a connection between Contify and CommonArg (and thinking that the only connection was the technique), I wondered if the dominator technique really was applicable to a larger class of analyses. That is still a question, but after writing up the above, I’m suspecting that the "real story" is that the dominator analysis is a solution to the common argument optimization, and that the Contify optimization is specializing CommonArg to the case of continuation arguments (with a different transformation at the end). (Note, a whole-program, inter-procedural common argument analysis doesn’t really make sense (in our SSA IntermediateLanguage), because the only way of passing values between functions is as arguments. (Unless of course in the case that the common argument is also a constant argument, in which case ConstantPropagation could lift it to a global.) The inter-procedural Contify optimization works out because there we move the function to the argument.)

Anyways, it’s still unclear to me whether or not the dominator based approach solves other kinds of problems.

Phase Ordering

On the downside, the optimization doesn’t have a huge impact on runtime, although it does predictably saved some code size. I stuck it in the optimization sequence after Flatten and (the third round of) LocalFlatten, since it seems to me that we could have cases where some components of a tuple used as an argument are common, but the whole tuple isn’t. I think it makes sense to add it after IntroduceLoops and LoopInvariant (even though CommonArg get some things that LoopInvariant gets, it doesn’t get all of them). I also think that it makes sense to add it before CommonSubexp, since identifying variables could expose more common subexpressions. I would think a similar thought applies to RedundantTests.