Re: Using extra outputs of an instruction

  Dobes Vandermeer <dobes@dobesland.com> writes:
>However, I have realized that there are some instructions which are
>useless when using tree matching. The first class of instruction is
>one which produces multiple independent outputs (e.g. ia32's XCHG
>operation which exchanges its operands). The second class is one
>which has a side-effect but where there is an equivalent instruction
>which does not (e.g. PowerPC's stwu vs. stw, where stwu adjusts the
>base register by the offset; also PUSH vs. ADD under intel).


I also see this as instructions producing two results. In a
conversation Helmut Emmelmann suggested modeling pre- or
postincrement/decrement addressing modes in the intermediate
representation, e.g., by having a "++" (or "+=") operator in the
intermediate representation; then you would have rules like


store(reg,preinc(reg,const)) 1 emit("stwu ...");
store(reg,add(reg,const)) 1 emit("stw ...");


There are several reasons why I think this is a bad idea:


- IR operators should be functional or at least idempotent, otherwise
things like using tree parsing on DAGs, and some optimizations and
tree grammar transformations don't work, and there will probably be
more bugs in the code selection grammar; you would also get additional
scheduling dependencies into the tree/DAG that the code generator
would have to preserve.


- You would need to know in advance where to put these operators.
Unless you take them directly from the source language (in case of C,
and then you are limited to those occurences that come from the source
code), you would need a peephole optimizer or something similar for
that. If you do such a peephole optimizer, better do it after the
code selection.


One particular thing about the update instructions in PPC is that in
many PPC implementations they are not faster (only smaller) than the
two instructions you would normally generate.


>I haven't seen much in the literature about solving this problem; most
>people seem to use a peephole optimizer to collapse the two
>instructions. To me this would only be acceptable if I could
>automatically generate this peephole optimizer and it was fast;


Take a look at some of the later papers about Davidson-Fraser code
generators, in particular:


@InProceedings{wendt90,
    author = "Alan L. Wendt",
    title = "Fast Code Generation Using Automatically-Generated
Decision Trees",
    pages = "9--15",
    booktitle = "SIGPLAN '90 Conference on Programming Language
Design and Implementation",
    year = "1990",
    annote = "Describes code generation based on DAG
rewriting. The code generators described in the
paper are particularly fast, because the code
generator generator combines several rules into
profitable combinations in a preprocessing step. A
training run is used to determine which combinations
play a role in practice. This optimization halves
the number of rule applications, and even the number
of rules is slightly reduced."
}


Of course, once you do that, you don't need the tree parsing code
generator:-).


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/home.html

Return to the comp.compilers page.
Search the comp.compilers archives again.