that was too much lub(), N-1 to be precise

Today I noticed something interesting in the dataflow algorithm we use. There's room for improvement.

After applying the transfer function to a basic block to obtain a lattice element `output`, we proceed to update the inputs of successors as follows:

  lattice.lub(in(p) :: (p.predecessors map out.apply), p.exceptionHandlerStart)

ie. all predecessor's outputs are lub-bed (besides the only one that changed, N-1 other lattice elems are lubbed, whose effect is already accounted for in `in(p)`)

The result doesn't change by leaving out those N-1 redundant inputs:

  lattice.lub(List(output, in(p)), p.exceptionHandlerStart)

What changes are the running times of all optimization phases (see attached picture).

BTW, the steep fall in Inliner is explained not only by this change, it includes other optimizations in branch

  https://github.com/magarciaEPFL/scala/tree/improvedInliner

that will eventually be merged into trunk (review and testing is welcome).


Miguel
http://lampwww.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/