Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1619 > unrolled thread

Maximal Munch instruction selection: how to connect tiles?

Back to article view | Back to comp.compilers

Contents

  Maximal Munch instruction selection: how to connect tiles? César <divcesar@gmail.com> - 2015-09-28 15:56 -0300
    Re: Maximal Munch instruction selection: how to connect tiles? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2015-09-29 17:16 +0200

#1619 — Maximal Munch instruction selection: how to connect tiles?

Given the expression a = b + c; my compiler currently produces the
following IR-tree:

    =
  /     \
a       + (_t1)
       /    \
     b      c

that is, it assumes:
- an assignment operator that copy from a register (_t1) to a memory (a);
- an add operator that sum the content of two memory regions (b and c)
and put the result in a register (_t1).

I am trying to use the maximal munch strategy to produce assembly code
for this tree but I'm stuck with the following questions:

1) The '=' operator assume the right hand side expression to be in a
register; what happens if that turn out to be impossible? I.e., what
happens if there is no '+' instruction that put the result in a
register.

2) Consider that there is no '+' instruction that can sum two memory
regions but there is one that can sum two registers. How can I make
use of the later instruction? I imagine that I should use loads to
move the variables to registers and later connect the '+' instruction
to these registers. But in that case, should the tree be modified to
reflect that change?

3) Is there any text with a complete and formal description of the
Maximal Munch IS algorithm?
[Appel's Modern Compiler Implementation in <x> has a description and sample
code, but it doesn't look like it'd be very helpful here.  I'd suggest adding
more nodes to your tree to make it easier for instruction patterns to match,
e.g., start with a tree that pretends every value will be loaded into a
register, and if your ISA has memory to register ops, the instruction patterns
match some of the loads and you can then forget about the registers that
the matched loads didn't use:

     =
  /     \
a       + (_t1)
       /    \
      _t2   _t3
       |     |
       b     c

-John]

[toc] | [next] | [standalone]

#1621

CC)sar schrieb:
> Given the expression a = b + c; my compiler currently produces the
> following IR-tree:
>
>     =
>   /     \
> a       + (_t1)
>        /    \
>      b      c
>  ...

> I am trying to use the maximal munch strategy to produce assembly code
> for this tree but I'm stuck with the following questions: ...

You can consider many more cases, like the x86 addressing modes with
base, index and scaling, which can be used for some arithmetic
expressions in general.

In case the '+' operator stores the result in memory, a '+=' opcode (add
to memory) could be used in above expression. All that can end up in
multiple possible different instruction sequences, which have to be
"weighted" for the final selection of the "best" sequence. The sequences
then can map to different tree structures, which are created from the
AST. That means that modifications should be applied to copies of the
AST, and it's unpredictable how big the different trees for more complex
expressions will become.

DoDi

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web