ok@quintus.UUCP (Richard A. O'Keefe) (04/13/88)
A week ago, I was looking at a peephole optimiser that someone had written
in Prolog. I'm not going to identify the program further, other than to
say that it was NOT done at Quintus, because I don't want to embarrass or
offend the author, who has done a lot for Logic Programming. The point is
that there is a particular infelicity of style which occurs in a real
program by someone who demonstrably has a thorough understanding of Prolog,
so I thought it might be worth discussing.
One fairly obvious optimisation is that a conditional branch to the next
instruction might as well not be there. (In fact, it had _better_ not be
there, because some assemblers generate bad machine code!) The Prolog code
I exhibit here is similar to the actual code, but the indentation and the
identifiers are mine.
.
:
peep_1_instr(jeq(L), [label(L)|Raw], [label(L)|Opt]) :-
peep_1_instrs(Raw, Opt).
peep_1_instr(jne(L), [label(L)|Raw], [label(L)|Opt]) :-
peep_1_instrs(Raw, Opt).
peep_1_instr(jlt(L), [label(L)|Raw], [label(L)|Opt]) :-
peep_1_instrs(Raw, Opt).
peep_1_instr(jge(L), [label(L)|Raw], [label(L)|Opt]) :-
peep_1_instrs(Raw, Opt).
peep_1_instr(jgt(L), [label(L)|Raw], [label(L)|Opt]) :-
peep_1_instrs(Raw, Opt).
peep_1_instr(jle(L), [label(L)|Raw], [label(L)|Opt]) :-
peep_1_instrs(Raw, Opt).
.
:
The point is obvious: there are six copies of essentially the same piece
of code. Big deal. Well, if this were the only instance of this pattern,
it would be a minor thing. But there are four instances of it, and there
are several instances of similar patterns involving other instructions.
In particular, there are two moderately large clauses having five variants
each, not all of which are correct.
The disadvantages of this are clear:
there is that much more source to read;
there is more code tying up space in memory;
it is too easy to fix a bug in some but not all replicates;
and so on
The question is, what can we do about it? In a language like C or Pascal
we can have multiple labels on case statements:
switch (instr->opcode) {
...
case JEQ: case JLT: case JGT:
case JNE: case JGE: case JLE:
if (instr->next->opcode == LABEL &&
instr->next->arg1 == instr->arg1)
instr->prev->next = instr->next,
instr->next->prev = instr->prev;
break;
...
}
(Now that I come to look at it, I'm not sure I wouldn't prefer the Prolog
version, six replicates and all.) Anyway, we can't do that in Prolog, or
for that matter in ML. This really isn't a Prolog-specific problem.
One approach would be to introduce a classification predicate:
peep_1_instr(Instr, Raw, Opt) :-
classify(Instr, Class),
peep_1_instr(Class, Instr, Raw, Opt).
peep_1_instr(j, Instr, [label(L)|Raw], [label(L)|Opt]) :-
arg(1, Instr, L),
peep_1_instrs(Raw, Opt).
classify(jeq(_), j).
...
Now there are six clauses in classify/2, but there is no replication
elsewhere. There are two snags with this: getting at the arguments
of a term with arg/3 like this is clumsy compared with unification,
and it's a pain to keep calling classify/2.
A better idea is to change the data structure so that the common
behaviour of these instructions is represented by a common appearance,
e.g. j(Condition,Label).
With that approach, we just write
peep_1_instr(j(_,L), [label(L)|Raw], [label(L)|Opt]) :-
peep_1_instrs(Raw, Opt).
and whereever there was a specific instance of, say, jgt(L) before,
we write instead j(gt,L).
One of the other cases is somewhat more interesting. It is, roughly,
peep_load(load_reg(Dst,Src), _, Regs0, Regs, Flag) :-
( memberchk(r(Dst,reg(Src)), Regs0) ->
Flag = 1,
Regs = Regs0
; /* instruction is not redundant */
Flag = 0,
Regs = [r(Dst,reg(Src)|Regs0]
).
with similar clauses for load_atm, load_int, load_flt (Did I mention
that this is a peephole optimiser for a Lisp compiler? Well, it isn't.)
which differ only in the pattern used in place of reg(Src).
Suppose instead that the instruction were represented as
load(Dst, reg(Src)|atm(Atm)|int(Int)|flt(Flt))
Then, instead of four clauses all doing much the same thing,
we'd need only one, namely:
peep_load(load(Dst,Src), _, Regs0, Regs, Flag) :-
( memberchk(Dst=Src, Regs0) ->
Flag = 1,
Regs = Regs0
; /* Dst doesn't already hold Src */
Flag = 0,
Regs = [Dst=Src|Regs0]
).
In the actual program, the variable "Regs0" was misspelled at the
"Regs=Regs0" occurrence. It's much easier to fix something like that
when there is only one replicate to fix.
Having a different constructor function for each instruction seems like
a good idea. But when there are clusters of very similar instructions,
it is better to regard the clusters as primary. Even generating the final
assembly code or whatever simplifies: instead of doing
write_instr(jeq(L)) :-
format('\tjeq\t~w~n', [L]).
or whatever (six times!) you would do
write_instr(j(Condition,Label)) :-
asm_j(Condition, Op),
format('\t~w\t~w~n', [Op,Label]).
asm_j(eq, 'beq.l'). % or whatever (six tiny facts)
So even there you are winning.