LARA

Control-Flow Graph to Assembly with Global Variables

Recall SimpleCFG.scala from Lecture 11

How to compile e.g. a quadruple?

x = y * z

One possibility: translate each quadruple independently into machine instruction sequence such as

Move(Register(r1), Memory(yAddr))
Move(Register(r2), Memory(zAddr))
Quad(Register(r1), Register(r1), Register(r2))
Move(Memory(xAddr), Register(r1))

How do we pick

  • r1, r2 - pick any general purpose register
  • xAddr, yAddr, zAddr
    • let assember pick them (usually sequentially in 'data segment' part of process image)
    • remark: linker can shift these, and virtual memory hardware can shift them again

Branching instructions etc. are similar, just make sure operands are in the right place

Advantages:

  • simple
  • work for arbitrarily complex expressions
    • translation to CFG introduces additional variables

Disadvantages:

  • occupies static memory if these are global variables
    • better to allocate them on stack
    • we will explain how stack looks like in machine code
  • can introduce unnecessary memory operations
    • much more expensive than CPU operations
    • much better if we can avoid re-loading value from memory
    • register allocation

Example

Compiling

res = x * y + y * z + x * z

can be expressed as compilation of this program

static int x;
static int y;
static int z;
static int res;
 
static int xy;
static int yz;
static int xz; 
static int res1;
 
int f() {
  xy = x * y;
  yz = y * z;
  xz = x * z;
  res1 = xy + yz;
  res = res1 + xz;
}

which (using gcc -S) generates assembly code of this form

movl	x, %edx
movl	y, %eax
imull	%edx, %eax
movl	%eax, xy
movl	y, %edx
movl	z, %eax
imull	%edx, %eax
movl	%eax, yz
movl	x, %edx
movl	z, %eax
imull	%edx, %eax
movl	%eax, xz
movl	xy, %edx
movl	yz, %eax
leal	(%edx,%eax), %eax
movl	%eax, res1
movl	res1, %edx
movl	xz, %eax
leal	(%edx,%eax), %eax
movl	%eax, res

The 'leal' instruction above

  • means 'load effective address, long'
  • here used simply as addition of registers
leal (%edx,%eax), %eax

means

%eax = %edx + %eax