llvm dev - Oct 2009 - [LLVMdev] request for help writing a register allocator

I found the problem!  My generated code is spilling correctly but is not 
reloading at all.  For example, if the original code has the equivalent of 
this (where %1024 is a virtual reg):

 	%1024 = xxx
 	...
 	yyy = %1024

and I find no physical register for %1024, then I assign it to physical 
register %edi and to a stackslot.  That creates code like this:

 	%edi = xxx
 	store from %edi to the stack
 	...
 	yyy = %edi

The last instruction is wrong.  There needs to be a load from the 
stackslot into %edi before copying from there into yyy.

The documentation says:
 	If the indirect strategy is used, after all the virtual registers
 	have been mapped to physical registers or stack slots, it is
 	necessary to use a spiller object to place load and store
 	instructions in the code.  Every virtual that has been mapped to a
 	stack slot will be stored to memory after been defined and will be
 	loaded before being used.
But this doesn't seem to be happening; the stores to memory are there but 
the loads are not.

Any ideas what's going wrong?

If not, any advice on how to generate the loads myself??

Susan

Hi Susan,

> But this doesn't seem to be happening; the stores to memory are there
but
> the loads are not.
>
> Any ideas what's going wrong?

Are you using VirtRegMap::addSpillPoint and VirtRegMap::addRestorePoint ? If
not you may need to add calls to them to let the rewriter know where to
insert the loads/stores.

> If not, any advice on how to generate the loads myself??

The TargetInstrInfo class has methods storeRegToStackSlot and
loadRegFromStackSlot, however I'd avoid mixing direct calls to these with
calls to the spiller.

Regarding Török's suggestion - make sure you #define the DEBUG_TYPE macro
(e.g. #define DEBUG_TYPE "foo") if you want your debugging output to
be
available using the -debug-only=foo option.

If you're running llc under a debugger you can also call
MachineFunction::dump (actually _many_ of the objects have a dump method) at
any time to print out the state of your machine function. I've found this to
be quite handy.

Cheers,
Lang.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20091022/1f849dcd/attachment.html>

I was NOT using addSpillPoint and addRestorePoint.  I will add those, 
THANK YOU!

I've also found that RegAllocSimple.cpp is a good model for me if I decide 
to give up on using the spiller and instead add the spill/reload code 
myself.

So I'm currently feeling much more optimistic about this project.

Thanks for all the (very quick!) help!!

Susan


On Thu, 22 Oct 2009, Lang Hames wrote:
> Hi Susan,
>
>
>> But this doesn't seem to be happening; the stores to memory are
there but
>> the loads are not.
>>
>> Any ideas what's going wrong?
>
>
> Are you using VirtRegMap::addSpillPoint and VirtRegMap::addRestorePoint ?
If
> not you may need to add calls to them to let the rewriter know where to
> insert the loads/stores.
>
>
>> If not, any advice on how to generate the loads myself??
>
>
> The TargetInstrInfo class has methods storeRegToStackSlot and
> loadRegFromStackSlot, however I'd avoid mixing direct calls to these
with
> calls to the spiller.
>
> Regarding T�r�k's suggestion - make sure you #define the DEBUG_TYPE
macro
> (e.g. #define DEBUG_TYPE "foo") if you want your debugging output
to be
> available using the -debug-only=foo option.
>
> If you're running llc under a debugger you can also call
> MachineFunction::dump (actually _many_ of the objects have a dump method)
at
> any time to print out the state of your machine function. I've found
this to
> be quite handy.
>
> Cheers,
> Lang.
>

I tried both the most recent version of "simple" register allocation
and
the one from last August, and neither seems to work correctly (they run, 
but produce bad output).  I used them to compile an old version of the 
Unix "replace" utility (source code attached).  Here's how I
created the
executable:

   llvm-gcc -emit-llvm -O0 -c replace.c -o replace.bc
   opt -mem2reg replace.bc > replace.ssa
   mv replace.ssa replace.bc
   llc -f -regalloc=simple replace.bc
   gcc replace.s

Then I ran it like this (file "input" also attached):

   a.out This XXXX < input

I get a Segmentation fault with the current version of LLVM.  With the old 
version it runs, but I get garbage output.

If I create the ".s" file using just
   llc -f replace.bc
everything is fine.


Does anyone know how to fix either version of RegAllocSimple?

Susan Horwitz
-------------- next part --------------
/*  -*- Last-Edit:  Mon Dec  7 10:31:51 1992 by Tarak S. Goradia; -*- */

extern void	exit();
# include <stdio.h>

void	Caseerror();

typedef char	bool;
# define false 0
# define true  1
# define NULL 0

# define MAXSTR 100
# define MAXPAT MAXSTR

# define ENDSTR  '\0'
# define ESCAPE  '@'
# define CLOSURE '*'
# define BOL     '%'
# define EOL     '$'
# define ANY     '?'
# define CCL     '['
# define CCLEND  ']'
# define NEGATE  '^'
# define NCCL    '!'
# define LITCHAR 'c'
# define DITTO   -1
# define DASH    '-'

# define TAB     9
# define NEWLINE 10

# define CLOSIZE 1

typedef char	character;
typedef char string[MAXSTR];

bool
getline(s, maxsize)
char	*s;
int	maxsize;
{
    char *result;
    result = fgets(s, maxsize, stdin);
    return (result != NULL);
}
int
addstr(c, outset, j, maxset)
char	c;
char	*outset;
int	*j;
int	maxset;
{
    bool	result;
    if (*j >= maxset)
	result = false;
    else {
	outset[*j] = c;
	*j = *j + 1;
	result = true;
    }
    return result;
}

char
esc(s, i)
char 	*s;
int	*i;
{
    char	result;
    if (s[*i] != ESCAPE)
	result = s[*i];
    else
	if (s[*i + 1] == ENDSTR)
	    result = ESCAPE;
	else 
	{
	    *i = *i + 1;
	    if (s[*i] == 'n')
		result = NEWLINE;
	    else
		if (s[*i] == 't')
		    result = TAB;
		else
		    result = s[*i];
	}
    return result;
}

void change();

 void
dodash(delim, src, i, dest, j, maxset)
char	delim;
char	*src;
int	*i;
char	*dest;
int	*j;
int	maxset;
{
    int	k;
    bool	junk;
    char	escjunk;

    while ((src[*i] != delim) && (src[*i] != ENDSTR)) 
    {
	if (src[*i - 1] == ESCAPE) {
	    escjunk = esc(src, i);
	    junk = addstr(escjunk, dest, j, maxset);
	} else	
	    if (src[*i] != DASH)
		junk = addstr(src[*i], dest, j, maxset);
	    else if (*j <= 1 || src[*i + 1] == ENDSTR)
		junk = addstr(DASH, dest, j, maxset);
	    else if ((isalnum(src[*i - 1])) && (isalnum(src[*i + 1])) 
		&& (src[*i - 1] <= src[*i + 1]))
		{
		    for (k = src[*i-1]+1; k<=src[*i+1]; k++) 
		    {
			junk = addstr(k, dest, j, maxset);
		    }	
		    *i = *i + 1;	
		} 
	    else	
		junk = addstr(DASH, dest, j, maxset);
	(*i) = (*i) + 1;
    }
}

bool
getccl(arg, i, pat, j)
char	*arg;
int	*i;
char	*pat;
int	*j;
{
    int	jstart;
    bool	junk;

    *i = *i + 1;
    if (arg[*i] == NEGATE) {
	junk = addstr(NCCL, pat, j, MAXPAT);
	*i = *i + 1;
    } else
	junk = addstr(CCL, pat, j, MAXPAT);
    jstart = *j;
    junk = addstr(0, pat, j, MAXPAT);
    dodash(CCLEND, arg, i, pat, j, MAXPAT);
    pat[jstart] = *j - jstart - 1;
    return (arg[*i] == CCLEND);
}

 void
stclose(pat, j, lastj)
char	*pat;
int	*j;
int	lastj;
{
    int	jt;
    int	jp;
    bool	junk;


    for (jp = *j - 1; jp >= lastj ; jp--) 
    {
	jt = jp + CLOSIZE;
	junk = addstr(pat[jp], pat, &jt, MAXPAT);
    }
    *j = *j + CLOSIZE;
    pat[lastj] = CLOSURE;
}

bool in_set_2(c)
char c;
{
  return (c == BOL || c == EOL || c == CLOSURE);
}      

bool in_pat_set(c)
char c;
{
  return (   c == LITCHAR || c == BOL  || c == EOL || c == ANY 
          || c == CCL     || c == NCCL || c == CLOSURE);
}      

int
makepat(arg, start, delim, pat)
char	*arg;
int	start;
char	delim;
char	*pat;
{
    int	result;
    int	i, j, lastj, lj;
    bool	done, junk;
    bool	getres;
    char	escjunk;

    j = 0;
    i = start;
    lastj = 0;
    done = false;
    while ((!done) && (arg[i] != delim) && (arg[i] != ENDSTR)) {
	lj = j;
	if ((arg[i] == ANY))
	    junk = addstr(ANY, pat, &j, MAXPAT);
	else if ((arg[i] == BOL) && (i == start))
	    junk = addstr(BOL, pat, &j, MAXPAT);
	else if ((arg[i] == EOL) && (arg[i+1] == delim))
	    junk = addstr(EOL, pat, &j, MAXPAT);
	else if ((arg[i] == CCL)) 
	{
	    getres = getccl(arg, &i, pat, &j);
	    done = (bool)(getres == false);
	} 
	else if ((arg[i] == CLOSURE) && (i > start)) 
	{
	    lj = lastj;
	    if (in_set_2(pat[lj]))
		done = true;
	    else
		stclose(pat, &j, lastj);
	} 
	else 
	{
	    junk = addstr(LITCHAR, pat, &j, MAXPAT);
	    escjunk = esc(arg, &i);
	    junk = addstr(escjunk, pat, &j, MAXPAT);
	}
	lastj = lj;
	if ((!done))
	    i = i + 1;
    }	
    junk = addstr(ENDSTR, pat, &j, MAXPAT);
    if ((done) || (arg[i] != delim))
	result = 0;
    else
	if ((!junk))
	    result = 0;
	else
	    result = i;
    return result;
}

int
getpat(arg, pat)
char*	arg;
char*	pat;
{
    int	makeres;

    makeres = makepat(arg, 0, ENDSTR, pat);
    return (makeres > 0);
}

int
makesub(arg, from, delim, sub)
	char*	arg;
	int	from;
	character	delim;
	char*	sub;
{
    int  result;
    int	i, j;
    bool	junk;
    character	escjunk;

    j = 0;
    i = from;
    while ((arg[i] != delim) && (arg[i] != ENDSTR)) {
	if ((arg[i] == (unsigned)('&')))
	    junk = addstr(DITTO, sub, &j, MAXPAT);
	else {
	    escjunk = esc(arg, &i);
	    junk = addstr(escjunk, sub, &j, MAXPAT);
	}
	i = i + 1;
    }
    if (arg[i] != delim)
	result = 0;
    else {
	junk = addstr(ENDSTR, &(*sub), &j, MAXPAT);
	if ((!junk))
	    result = 0;
	else
	    result = i;
    }	
    return result;
}

bool
getsub(arg, sub)
	char*	arg;
	char*	sub;
{
    int	makeres;

    makeres = makesub(arg, 0, ENDSTR, sub);
    return (makeres > 0);
}

void subline();

 bool
locate(c, pat, offset)
	character	c;
	char *	pat;
	int	offset;
{
    int	i;
    bool flag;

    flag = false;
    i = offset + pat[offset];
    while ((i > offset))
    {
	if (c == pat[i]) {
	    flag = true;
	    i = offset;
	} else
	    i = i - 1;
    }
    return flag;
}

bool
omatch(lin, i, pat, j)
	char*	lin;
	int	*i;
	char*	pat;
	int	j;
{
    char	advance;
    bool result;
    
    advance = -1;
    if ((lin[*i] == ENDSTR))
	result = false;
    else 
    {
	if (!in_pat_set(pat[j]))
	{
	    (void)fprintf(stdout, "in omatch: can't happen\n");
	    abort();	
	} else
	{
	     switch (pat[j]) 
	     {			
	     case LITCHAR:
		 if (lin[*i] == pat[j + 1])
		     advance = 1;
		 break ;	
	     case BOL:
		 if (*i == 0)
		     advance = 0;
		 break ;
	     case ANY:
		 if (lin[*i] != NEWLINE)
		     advance = 1;
		 break ;
	     case EOL:
		 if (lin[*i] == NEWLINE)
		     advance = 0;
		 break ;
	     case CCL:
		 if (locate(lin[*i], pat, j + 1))
		     advance = 1;	
		 break ;
	     case NCCL:
		 if ((lin[*i] != NEWLINE) && (!locate(lin[*i], pat, j+1)))
		     advance = 1;	
		 break ;
	     default:
		 Caseerror(pat[j]);
	     };
	 }	
    }
    if ((advance >= 0)) 
    {
	*i = *i + advance;
	result = true;
    } else
	result = false;
    return result;
}


patsize(pat, n)
	char*	pat;
	int	n;
{
    int size;
    if (!in_pat_set(pat[n])) {
	(void)fprintf(stdout, "in patsize: can't happen\n");
	abort();
    } else
	switch (pat[n]) 
	{
	case LITCHAR: size = 2; break;
	    
	case BOL:  case EOL:  case ANY:
	    size = 1;
	    break;
	case CCL:  case NCCL:
	    size = pat[n + 1] + 2;
	    break ;
	case CLOSURE:
	    size = CLOSIZE;
	    break ;
	default:
	    Caseerror(pat[n]);
	}
    return size;
}

int
amatch(lin, offset, pat, j)
	char*	lin;
	int	offset;
	char*	pat;
	int	j;
{
    int	i, k;
    bool	result, done;

    done = false;
    while ((!done) && (pat[j] != ENDSTR))
	if ((pat[j] == CLOSURE)) {
	    j = j + patsize(pat, j);
	    i = offset;
	    while ((!done) && (lin[i] != ENDSTR)) {
		result = omatch(lin, &i, pat, j);
		if (!result)	
		    done = true;
	    }
	    done = false;
	    while ((!done) && (i >= offset)) {
		k = amatch(lin, i, pat, j + patsize(pat, j));
		if ((k >= 0))
		    done = true;
		else
		    i = i - 1;
	    }
	    offset = k;
	    done = true;
	} else {
	    result = omatch(lin, &offset, pat, j);
	    if ((!result)) {	
		offset = -1;
		done = true;
	    } else
		j = j + patsize(pat, j);
	}
     return offset;
}

void
putsub(lin, s1, s2, sub)
  char *	lin;
  int	s1, s2;
  char *	sub;
{
    int	i;
    int		j;

    i = 0;
    while ((sub[i] != ENDSTR)) {
	if ((sub[i] == DITTO))
	    for (j = s1; j < s2; j++) 
	    {
		fputc(lin[j],stdout);
	    }	
	else	
	{
	    fputc(sub[i],stdout);
	}
	i = i + 1;
    }
}

void
subline(lin, pat, sub)
 char	*lin;
 char   *pat;
 char   *sub;
{	
	int	i, lastm, m;

	lastm = -1;
	i = 0;
	while ((lin[i] != ENDSTR)) 
	{
	    m = amatch(lin, i, pat, 0);
	    if ((m >= 0) && (lastm != m)) {
		putsub(lin, i, m, sub);
		lastm = m;
	    }
	    if ((m == -1) || (m == i)) {
		fputc(lin[i],stdout);
		i = i + 1;
	    } else
		i = m;
	}
}

 void
change(pat, sub)
char *pat, *sub;
{
    string  line;
    bool result;
    
    result = getline(line, MAXSTR);
    while ((result)) {
	subline(line, pat, sub);
	result = getline(line, MAXSTR);
    }
}

main(argc, argv)
int	argc;
char	*argv[];
{
   string pat, sub;
   bool result;

   if (argc < 2) 
   {
       (void)fprintf(stdout, "usage: change from [to]\n");
       exit(1);
   };

   result = getpat(argv[1], pat);
   if (!result)
   {
       (void)fprintf(stdout, "change: illegal \"from\"
pattern\n");
       exit(2);
   }

   if (argc >= 3)
   {
       result = getsub(argv[2], sub);
       if (!result)
       {	
	   (void)fprintf(stdout, "change: illegal \"to\"
string\n");
	   exit(3);
       }
   } else
   {
       sub[0] = '\0';
   }
   
   change(pat, sub);
   return 0;
}

void
Caseerror(n)
	int	n;
{
	(void)fprintf(stdout, "Missing case limb: line %d\n", n);
	exit(4);
}
-------------- next part --------------
This is a test

I'm having no luck getting my register allocator to work.  I'm trying to
do it using the "indirect" approach; i.e., using a VirtRegMap, with
calls
to assignVirt2Phys, assignVirt2StackSlot, etc. and a call to a
"spiller"
at the end.

As a warm-up exercise (before implementing register allocation via graph 
coloring) I'm trying to implement a very simple scheme in which NO 
pseudo-registers are allocated to physical registers across instructions. 
So for each virtual register I call assignVirt2StackSlot.  I thought that 
I should call assignVirt2Phys as well for each virtual register in an 
instruction, mapping that vreg to an unused preg.  For example, for an 
instruction like this:
 	%reg1024<def> = MOV32rr %ESP
I assign virtual register 1024 to some available physical register in the 
appropriate class so that the generated code will assign to that physical 
register.  (I also assign virtual register 1024 to a stack slot so that 
the value assigned to the physical register is spilled to that slot.)

If a virtual register is used in an instruction, rather than defined, I 
again assign it to a physical register preg (but not to a stack slot 
because it will already have been assigned a slot) so that the generated 
code will load from the stack into that preg.

However, if the same virtual register is used in two different 
instructions, I get an abort with an error message saying that I'm trying 
to assign a physical register to a virtual register that's already been 
mapped.  If I don't call assignVirt2Phys then I get an abort with an error 
message saying that some virtual register was not assigned a physical 
register.

I've tried calling addSpillPoint and addRestorePoint for every instruction 
that involves a virtual register, and also not calling those functions, 
and I still get the same aborts.

I would very much appreciate any help!

Susan Horwitz