[LLVMdev] Some backend questions

[Chris Lattner]

On Fri, 4 Jun 2004, Vladimir Prus wrote:
> Ok, I'm now trying to write instruction selector and have some questions
>
> 1. The MachineInstrBuilder has methods to add register operand and immediate
> operand. However, what would be really nice is a method to add Value*.  So, I
> would write:
>
>     BuildMI(*BB, NM::add, 1).add(I.getOperand(0), I.getOperand(1));
>
> and depending on whether the passed Value* is contant or instruction, the add
> method would either add immediate constant or allocate/get new virtual
> register.

Okay, the problem with this is that the instruction selector is the code
that is supposed to know what constraints the instructions have.  For
example, on many architectures, immediates are limited to 13 bits or some
other small number.  Also, for virtual regsiters, there is no context to
hold the mapping of Value*'s -> vregs: this is what the instruction
selector is about.

I recommend taking a look at the getReg(*) methods in the X86 instruction
selector.  The basic code generation stage for an add, boiled down to its
simplest form, basically looks like this:

void visitAdd(BinaryOperator &B) {
  unsigned Op0Reg = getReg(B.getOperand(0));
  unsigned Op1Reg = getReg(B.getOperand(1));
  unsigned DestReg = getReg(B);

  unsigned Opcode = (get the opcode for the size of the add);
  BuildMI(<where>, Opcode, 2, DestReg).addReg(Op0Reg).addReg(Op1Reg);
}

The nice thing about the "getReg" functionality is that it is a member of
the instruction selector class, so it has the context to store the maps
and other things needed in it.

If you do this (which I recommend for the first step), you'll notice that
it produces pretty horrible code, as all immediates are copied into
registers before they are used.  In other words, instead of getting:

  R2 = add R1, 17

You'll get:

  R3 = mov 17
  R2 = add R2, R3

IOW, the code will work fine, but will be ugly and slow.  As the second
step, when the selector is basically working, you can add cases to handle
these.  Taken to a limit you'll get something as complex as the X86
InstSelectSimple (which as someone mentioned, is not really simple
anymore).

> 2. Why SSARegMap is called this way. As far as I can see, it's does not
> implement any mapping, it simply allocates registers given a register class.

You're right, it currently just keeps track of the register class for each
virtual register.  Eventually it will keep track of which machine
instruction defines each virtual register as well, at which point it will
live up to its name. :)

> 3. Maybe, the allocation of virtual registers for Value* should be made more
> reusable. The X86 backend has the code for that in getReg method in
> InstSelectSimple.cpp which:
>
>    - uses SSARegMap instance
>    - keeps internal Value* -> register mapping
>    - copies constants into register when needed
>
> At least first two things will be necessary for my backend too. I start to
> wonder if it makes sense to make a "BasicInstructionSelector" which will have
> such reusable logic?

That's a good idea, because basically all instruction selectors require
the same code.  The problem is that the code needs to know how to get an
immediate/constant into a register as well, which can be very complex on
some targets.

For now, I recommend just copying the code to get something up and running
quickly.  In the future we can talk about creating a target independent
helper class once we understand the requirements and constraints better.

> Sorry if the above is not very clear -- I'm only starting to getting underting
> of LLVM codebase.

Not at all!  Please ask!  BTW, what architecture are you targetting?

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/