[m-dev.] for review: rewrite of duplicate elimination.

[Zoltan Somogyi]

Fergus wrote:
> One test case for this that is worth looking at is rbtree.m.
> If this optimization does affect rbtree.m, it might even be worth
> rerunning the comparison between rbtree.m and tree234.m.

It does optimize some predicates in rbtree, but only auxiliary ones (count,
values, keys).

The insert and update predicates have no code that is duplicate in the sense
used by this version of duplicate elimination. Even though the initial
handling of red and black nodes is often the same, the blocks of code
doing this branch to different labels because the updated nodes have different
colors. The algorithm has no provision for saving the masked off tag and
later reusing it. In any case, in several places the code tests the color;
that is why the color is there.

The search predicates should be optimizable by the present dupelim,
but purely by chance the input code to dupelim is such that after the
recursive call in one switch arm, the fallthrough branch handles success
and the side branch handles failure, whereas after the recursive call in
the other switch arm it is the opposite. Dupelim cannot recognize and
optimize this, and since it cannot do so, it considers otherwise
identical earlier code blocks to be different as well (since they branch
to "different" later code). Fixing this problem is future work.

Other predicates elsewhere have code that is duplicate in the sense of this
algorithm, but some of the blocks also contain decision code. This code
could later be eliminated using a transform such as what is now in peephole,
but its presence there at the start of dupelim prevents the optimization
from being applied. This is also future work.

> Hmm, that comment disappeared and I didn't see anything to replace it.
> Was there a reason for that?

It was replaced by the much bigger comment up top.

> This predicate will need to be changed whenever anyone adds a new
> instruction, so could you please document it.  The documentation should
> be immediately preceding the definition of the predicate and should
> explain things in terms that someone who doesn't know anything about
> dupelim can understand.

Aw, the lack of documentation has never stopped people from doing the right
things before ... :-)

However, I take your point.  I have added a brief comment before each
predicate, and an explanation of what "generalization" means in this module
at the top of the module.

Zoltan.