path: root/regalloc.c

#include <stdlib.h>
#include <assert.h>
#include "regalloc.h"

#define new0(t) ((t*)calloc(1, sizeof(t)))
#define FALSE 0
#define TRUE 1

typedef int boolean;

typedef struct VarInfo VarInfo;
typedef struct Location Location;

struct VarInfo
{
    reg_type_t	reg_type;
    Location *	home_location;
    Location *	current_location;

    VarInfo *	next;
    VarInfo *	prev;

    boolean	deallocated;
};

struct Location
{
    reg_type_t	type;
    op_t	op;
    boolean	is_home;	/* Whether it is the home location for some variable */
    boolean	is_current;	/* Whether it is the current location for some variable */
    Location *	next;
    Location *  prev;
};

struct RegAlloc
{
    VarInfo *	vars;
    int		spill_pos;
    int		spill_max;

    Location *	locations;

    Asm *	as;
};

static int
max (int a, int b)
{
    return (a > b) ? a : b;
}

static Location *
append (Location *location, Location *next)
{
    Location *loc = location;
    
    if (loc)
    {
	while (loc->next)
	    loc = loc->next;

	loc->next = next;
	next->prev = loc;

	return location;
    }
    else
    {
	return next;
    }
}

static Location *
new_spill (RegAlloc *ra, reg_type_t type)
{
    Location *spill = new0 (Location);
    int n_bytes;

    switch (type)
    {
    case REG_TYPE_GP:
	n_bytes = 4;
	break;

    case REG_TYPE_MMX:
	n_bytes = 8;
	break;

    case REG_TYPE_SSE:
	n_bytes = 16;
	break;
    };

    /* Align spill location */ 
    /* FIXME: we potentially waste space here - keep 16, 8 and 4 byte location separate */
    ra->spill_pos += (n_bytes - 1);
    ra->spill_pos &= ~(n_bytes - 1);

    spill->op = x86_membase (x86_esp(), ra->spill_pos);
    spill->is_home = FALSE;
    spill->is_current = FALSE;
    spill->next = NULL;
    spill->prev = NULL;
    spill->type = type;
    
    ra->spill_pos += n_bytes;

    ra->spill_max = max (ra->spill_pos, ra->spill_max);

    ra->locations = append (ra->locations, spill);
    
    return spill;
}

static Location *
new_register (RegAlloc *ra, reg_type_t type, reg_t reg)
{
    Location *location = new0 (Location);

    location->op.type = REG;
    location->op.reg.reg = reg;
    location->is_home = FALSE;
    location->is_current = FALSE;
    location->next = NULL;
    location->prev = NULL;
    location->type = type;

    ra->locations = append (ra->locations, location);
    
    return location;
}

static Location *
get_home_location (RegAlloc *ra, reg_type_t type)
{
    Location *location;

    for (location = ra->locations; location != NULL; location = location->next)
    {
	if (location->type == type && !location->is_home)
	    return location;
    }

    return new_spill (ra, type);
}

#define N_ELEMENTS(a) (sizeof (a) / sizeof (a[0]))

RegAlloc *
reg_alloc_new (Asm *a)
{
    static const reg_t mmx_registers[] = {
	MM0, MM1, MM2, MM3, MM4, MM5, MM6, MM7
    };
    static const reg_t gp_registers[] = {
	EAX, EBX, ECX, EDX, ESI, EDI
    };
    static const reg_t sse_registers[] = {
	XMM0, XMM1, XMM2, XMM3, XMM4, XMM5, XMM6, XMM7
    };
    
    RegAlloc *ra = new0 (RegAlloc);
    int i;

    ra->vars = NULL;
    ra->spill_pos = 0;
    ra->spill_max = 0;
    ra->as = a;

    for (i = 0; i < N_ELEMENTS (gp_registers); ++i)
	new_register (ra, REG_TYPE_GP, gp_registers[i]);

    for (i = 0; i < N_ELEMENTS (mmx_registers); ++i)
	new_register (ra, REG_TYPE_MMX, mmx_registers[i]);

    for (i = 0; i < N_ELEMENTS (sse_registers); ++i)
	new_register (ra, REG_TYPE_SSE, sse_registers[i]);
    
    return ra;
}

static op_t
allocate_var (RegAlloc *ra, reg_type_t type)
{
    op_t result;
    VarInfo *info = new0 (VarInfo); /* FIXME: check for NULL */

    info->reg_type = type;
    info->home_location = get_home_location (ra, type);
    info->current_location = NULL;
    
    result.type = ALLOC;
    result.alloc.info = info;

    info->home_location->is_home = TRUE;

    if (ra->vars)
	ra->vars->prev = info;
    info->next = ra->vars;
    ra->vars = info;
    
    return result;
}

op_t
reg_alloc_alloc_gp (RegAlloc *ra)
{
    return allocate_var (ra, REG_TYPE_GP);
}

op_t
reg_alloc_alloc_mmx (RegAlloc *ra)
{
    return allocate_var (ra, REG_TYPE_MMX);
}

op_t
reg_alloc_alloc_sse (RegAlloc *ra)
{
    return allocate_var (ra, REG_TYPE_SSE);
}

void
reg_alloc_normalize (RegAlloc *ra)
{
    int x;

    
    
}

static VarInfo *
find_evict_variable (VarInfo *vars, reg_type_t type)
{
    VarInfo *info;

    if (!vars)
	return NULL;
    
    info = find_evict_variable (vars->next, type);
    if (info)
	return info;

    if (vars->deallocated)
	return NULL;

    if (vars->reg_type != type)
	return NULL;

    if (!vars->current_location)
	return NULL;

    if (vars->current_location->op.type != REG)
	return NULL;

    return vars;
}

static Location *
find_evict_location (RegAlloc *ra, reg_type_t type)
{
    Location *location;

    for (location = ra->locations; location != NULL; location = location->next)
    {
	if (location->type == type && !location->is_current)
	    return location;
    }

    return new_spill (ra, type);
}

static void
move_variable (RegAlloc *ra, VarInfo *info, Location *new_location)
{
    op_t from, to;
    
    assert (info->current_location);

    from = info->current_location->op;
    to = new_location->op;
    
    switch (info->reg_type)
    {
    case REG_TYPE_GP:
	x86_mov (ra->as, from, to);
	break;
    case REG_TYPE_MMX:
	x86_movq (ra->as, from, to);
	break;
    case REG_TYPE_SSE:
	x86_movdqa (ra->as, from, to);
	break;
    }

    info->current_location->is_current = FALSE;
    info->current_location = new_location;
    info->current_location->is_current = TRUE;
}

static Location *
get_unused_register (RegAlloc *ra, VarInfo *info)
{
    VarInfo *evict;
    Location *evict_location;
    Location *location;

    /* Prefer the home location if available */
    if (info->home_location->op.type == REG && !info->home_location->is_current)
	return info->home_location;
    
    for (location = ra->locations; location != NULL; location = location->next)
    {
	if (location->type == info->reg_type	&&
	    location->op.type == REG		&&
	    !location->is_current)
	{
	    return location;
	}
    }

    /* No register available, evict some variable */
    evict = find_evict_variable (ra->vars, info->reg_type);
    evict_location = find_evict_location (ra, info->reg_type);

    assert (evict);
    
    location = evict->current_location;
    
    move_variable (ra, evict, evict_location);

    return location;
}

static void
move_to_front (RegAlloc *ra, VarInfo *info)
{
    if (info->prev)
    {
	info->prev->next = info->next;
	if (info->next)
	    info->next->prev = info->prev;

	if (ra->vars)
	    ra->vars->prev = info;
	info->next = ra->vars;
	ra->vars = info;
    }
}

op_t
reg_alloc_get_register (RegAlloc *ra, op_t op)
{
    VarInfo *info;
    
    assert (op.type == ALLOC);

    info = op.alloc.info;

    if (info->current_location)
    {
	if (info->current_location->op.type != REG)
	{
	    Location *new_loc = get_unused_register (ra, info);

	    move_variable (ra, info, new_loc);
	}
    }
    else
    {
	Location *new_loc = get_unused_register (ra, info);

	info->current_location = new_loc;
	info->current_location->is_current = TRUE;
    }

    move_to_front (ra, info);

    return info->current_location->op;
}

void
reg_alloc_dealloc (RegAlloc *ra,
		   op_t      var)
{
    VarInfo *info;

    assert (var.type == ALLOC);
    
    info = var.alloc.info;
    
    info->home_location->is_home = FALSE;
    if (info->current_location)
	info->current_location->is_current = FALSE;

    info->deallocated = TRUE;
}