Instruction selection
*********************

We want to have asm from our intermediate representation.

Types des microprocesseurs
==========================

CISC processors characteristics include:

  - 6, 8, 16 registers, some for pointers, others for int computation

  - artihmetic in memory can be processed

  - two adresses code

  - many possible effects (eg, self-incrementation)

RISC processors characteristics include:

  - 32 polyvalent registers

  - arithmetic only available on registers

  - 3 adresses code

  - LOAD and STORE are relative to a register (M[r + const])

  - only one effect or result by instruction

We will generate asm RISC related. CISC will have to be adapted by adding suplementary instructions. For instance, our intermediate language uses 3 adresses, production rules will eventually needed for the production of several instruction implying several registers. We want to minimize MOVE utilization, so we need a good register allocation.

Make a correlation between asm instructions and intermediate representation trees modelizing it. For example with RISC, STORE which effect is $M[r_j + c] := r_i$ covers 4 tree patterns ($r_0$ register always contain 0, so there is also the case M[c] :=). For some other, we use commutativity, so we understand there is more trees, than significations...

Search for those intructions pattern.(three adressed)

ADD, MUL, SUB, DIV, ADDI, SUBI (const substraction) LOAD ($r_i := M[r_j + c]$), STORE add MOVEM (M[r_i] := M[r_j]).

think about the intermediate representation of:

     a[i] := x

Selecting instruction is of course an combinational optimisaton problem, hence optimal words and optimum have an obvious meaning here. For the proposed solutions, wich are optimum, consider having a cost of 1 for every instructions but MOVEM : we suppose 1, or more.

Sélection d'instructions
========================

We don't take care of pipe lines.

Maximal Munch
-------------

Start for the root, find the largest tile that can cover it.  Emit the assembly instruction which corresponds, and start again on the sub trees.

Note that the instruction are emitted in reversed order.

Try it on the representation of

     a[i] := x

where A and X are in the frame, and I is in an register.

Dynamic Programming
-------------------

Dynamic programming is a method which can be used when an optimum is always composed of optima.

We start from the bottom, each time we keep the less costing solutions.

Try on M[1 + 2]

That can become very hard to implement. We only want to declare knowledge and let a program make the reflexion. This knowledge can be expressed by an LRR(1) grammar, we should then use generators of code generators.

Though, with RISC processors, it's difficult to find differences between optimum and optimal, therefore we don't need to take care of such complicated things.

Implemention for Tiger
======================

We choose to implement instruction selection before register allocation. Nevertheless instruction selection depends upon the target, while register allocation does not, so we need to find a means to represent target dependent assembly language instruction in s target independent method!

The proposed answer is dead simple: only consider the string representation of these instructions.

But since the register allocation phase will need to know where the register (temporaries) are defined and used, since we also need to trace the labels, we enrich our strings which a list of the temporaries which are defined and used by each instruction.

Finally, the string will not directly hard code the temporaries' names, but simply symbols which denotes either the nth defined or used temporary.

We end up with something like three different classes in the name space assem: Oper, Move, and Label.  The class Oper is very general, since it includes the jumps too.

     Oper (string asm, list<Temp*> dst, list<Temp*> src, list<Label*> jmps)
     Move (string asm, Temp &dst, Temp &src)
     Label (string asm, Label &label)

We have introduced Move because our next task is to get rid of most of these.

For instance, the tree + temp1 temp2 becomes

     Oper ("add 'd0 , 's1, 's2",
           (new temp::Temp ()), (temp1, temp2), ())

As you notice, the tiling algorithms must keep us informed of the temporaries they create at each joint of the tree (here the additional Temp).

How do you think call should be represented?  What of the caller saved registers?