On Mon, 2006-07-03 at 13:03 -0700, Chip Salzenberg wrote:
> Thanks muchly for this contribution. I love making failing tests pass.
> There are some adjustments needed, though, before we can integrate this
> patch into Parrot.
>
> The use of a fixed constant like MAX_REGISTER doesn't really work; Parrot
> has an unbounded (if not infinite :-)) number of registers, set on a
> per-function basis. [When you talked to me on IRC, if I'd known you were
> indexing registers I'd have mentioned this.] You'll have to use the INTVAL
> typedef as the data type to hold register numbers.
The function prototype is
void
Parrot_register_move(Interp *interpreter, int n_regs,
unsigned char *dest_regs, unsigned char *src_regs,
unsigned char temp_reg,
reg_move_func mov,
reg_move_func mov_alt,
void *info);
src_regs and dest_regs are pointers to unsigned char. Unsinged char
being 1 byte will store 256 distinct values. Hence I declared the
MAX_REGISTER to 256.
But I agree if we need to support unbounded number of registers we need
to fix this algorithm and places where it is called. Let me know what
case do we need to code for unbounded number of registers or 256
registers for now.
> So the first step in making this patch ready to apply is to make it adapt
> automatically to the actual number of registers used in the given function.
> It's possible the Parrot Cage Cleaners could have a volunteer ready to help
> you with this....
>
I can take care of fixing once we decide on number of registers. The
algorithm will need to move away from using adjacency matrix to probably
a graph-vertex data structure approach as the adjacency matrix could eat
up memory.
> (C maven alert: I can imagine an interesting hack to use 'short' or
> 'unsigned char' when functions are small and INTVAL when they are large.
> But I digress.)
>
> Perhaps separately: I recall that Audrey Tang (Pugs mastermind) ran into
> problems with aggressive use of continuations conflicting with the register
> coloring algorithm. Continuations allow any function call to pop out at any
> function return point, not just at the return point that follows the last
> call made. From a register coloring point of view, the point after each
> function call starts a new basic block. Being new pumpking I'm not versed
> in the register allocation parts of Parrot yet, so I may have missed
> something, but IIRC this is an issue that must be dealt with. Is your patch
> relevant to this question, or orthogonal?
>
> Finally: The coding style of your patch will need a little work. Style is
> something a Cage Cleaner volunteer can help with once the code is otherwise
> ready. I'm not religious about coding styles, but style _consistency_ is
> pretty important in a multi-person project. Ideally, a reader should be
> unable to tell newly inserted code from old code. (Except that new code
> should always work. :-))
>
> There are also some Parrot coding style issues that are functionally
> important, and not just about looking good. For example, shared
> declarations must always be in header files (yes there are exceptions in the
> current code base but we're weeding them out gradually). Also, extern
> symbols must always a Parrot_ prefix, to facilitate embedding Parrot in
> other applications. There are other lesser style issues WRT spacing and
> braces, but they're easy to deal with.
>
> The main thing is to get the algorithm solid, and the rest can be dealt with
> later (before the patch is applied, though :-)).
>
> On Sun, Jul 02, 2006 at 02:02:34PM -0500, Vishal Soni wrote:
> > This patch implements the register content preserving move operation.
> >
> > Thanks,
> > Vishal
> >
> > Previously:
> > -------------
> > Now:1..3
> > ok 1 - in P param
> > ok 2 - tailcall 1
> > not ok 3 - tailcall 2 # TODO use temp
> > # Failed (TODO) test (t/compilers/imcc/imcpasm/optc.t at line 59)
> > # '# IMCC does produce b0rken PASM files
> > # # see http://[EMAIL PROTECTED]/rt3/Ticket/Display.html?id=32392
> > # _main:
> > # @pcc_sub_call_0:
> > # set_args
> > # set_p_pc P0, foo
> > # get_results
> > # invokecc P0
> > # set_returns
> > # returncc
> > # foo:
> > # get_params
> > # [EMAIL PROTECTED]:
> > # @pcc_sub_call_1:
> > # set I0, I1
> > # set I1, I0
> > # branch [EMAIL PROTECTED]
> > # '
> > # doesn't match '/ set I(\d), I(\d)
> > # set I\2, I(\d)
> > # set I\3, I\1/
> > # '
> >
> > ------
> > 1..3
> > ok 1 - in P param
> > ok 2 - tailcall 1
> > ok 3 - tailcall 2 # TODO use temp
> >
> >
> > Patch:
> > -------Index: src/utils.c
> > ===================================================================
> > --- src/utils.c (revision 13113)
> > +++ src/utils.c (working copy)
> > @@ -48,6 +48,7 @@
> > =cut
> >
> > */
> > +#define MAX_REGISTER 256
> >
> > INTVAL
> > intval_mod(INTVAL i2, INTVAL i3)
> > @@ -678,12 +679,29 @@
> >
> > TODO add a define, if it's implemented so that we can start filling the
> > gaps
> >
> > +TODO The current implementation will not work for following cases
> > +
> > +1. I0->I1 I1->I0 I0->I3
> > +2. I1->I2 I3->I2
> > +
> > +Vishal Soni
> > =cut
> >
> > */
> >
> > /* proto TODO mv to hdr */
> > typedef int (*reg_move_func)(Interp*, unsigned char d, unsigned char s,
> > void *);
> > +int reorder_move(unsigned char (*a)[MAX_REGISTER],unsigned char *val ,int
> > src , int prev, int depth ,reg_move_func mov,Interp *interpreter,void
> > *info,int temp);
> > +int find_first_indegree(unsigned char (*a)[MAX_REGISTER] , int dest);
> > +int find_root(unsigned char (*a)[MAX_REGISTER],unsigned char* root_vertex
> > ,int src, int dest);
> > +void emit_mov(reg_move_func mov,Interp *interpreter,void *info,int emit,int
> > emit_temp,int src,int dest,int temp);
> > +void
> > +Parrot_register_move(Interp *interpreter, int n_regs,
> > + unsigned char *dest_regs, unsigned char *src_regs,
> > + unsigned char temp_reg,
> > + reg_move_func mov,
> > + reg_move_func mov_alt,
> > + void *info);
> >
> > void
> > Parrot_register_move(Interp *interpreter, int n_regs,
> > @@ -693,16 +711,113 @@
> > reg_move_func mov_alt,
> > void *info)
> > {
> > - int i;
> > + //int i;
> > /* TODO */
> >
> > /* brute force and wrong */
> > - for (i = 0; i < n_regs; ++i) {
> > + /* for (i = 0; i < n_regs; ++i) {
> > if (dest_regs[i] != src_regs[i])
> > mov(interpreter, dest_regs[i], src_regs[i], info);
> > + printf("Vishal:[%d],[%d]\n",dest_regs[i],src_regs[i]);
> > + }*/
> > +
> > + int i;
> > + unsigned char (*reg_move_graph)[MAX_REGISTER] = (unsigned char
> > (*)[MAX_REGISTER])mem_sys_allocate_zeroed(sizeof (unsigned
> > char)*MAX_REGISTER *MAX_REGISTER);
> > + unsigned char *root_vertx= (unsigned char
> > *)mem_sys_allocate_zeroed(sizeof (unsigned char)*MAX_REGISTER);
> > +
> > + for (i = 0 ; i < n_regs; i++)
> > + {
> > + reg_move_graph[src_regs[i]][dest_regs[i]]=1;
> > +
> > root_vertx[find_root(reg_move_graph,root_vertx,src_regs[i],dest_regs[i])]=1;
> > }
> > +
> > + unsigned char *val = (unsigned char *)mem_sys_allocate_zeroed(sizeof
> > (unsigned char)*MAX_REGISTER);
> > + for (i = 0 ; i < MAX_REGISTER; i++)
> > + {
> > + if (root_vertx[i]>0)
> > + {
> > + mov(interpreter,temp_reg,i,info);
> > +
> > reorder_move(reg_move_graph,val,i,-1,0,mov,interpreter,info,temp_reg);
> > + }
> > + }
> > + free(val);
> > + free(reg_move_graph);
> > + free(root_vertx);
> > }
> >
> > +int find_root(unsigned char (*a)[MAX_REGISTER],unsigned char* root_vertex
> > ,int src, int dest)
> > +{
> > + if (a[src][dest]==2)
> > + {
> > + a[src][dest]=1;
> > + return dest;
> > + }
> > + root_vertex[src]=0;
> > + a[src][dest]=2;
> > + int in_degree=find_first_indegree(a,src);
> > + if (in_degree==-1)
> > + {
> > + a[src][dest]=1;
> > + return src;
> > + }
> > + return find_root(a,root_vertex,in_degree,src);
> > +}
> > +
> > +int find_first_indegree(unsigned char (*a)[MAX_REGISTER] , int dest)
> > +{
> > + int i=0;
> > + for( i= 0; i<MAX_REGISTER; i++)
> > + {
> > + if (a[i][dest] >0 )
> > + {
> > + return i;
> > + }
> > + }
> > + return -1;
> > +}
> > +int reorder_move(unsigned char (*a)[MAX_REGISTER],unsigned char (*val),int
> > src , int prev, int depth , reg_move_func mov,Interp *interpreter,void
> > *info,int temp)
> > +{
> > + int i=0;
> > + val[src]=1;
> > + for (i=0;i<MAX_REGISTER;i++)
> > + {
> > + if (a[src][i]>0 )
> > + {
> > + if (val[i]==1)
> > + {
> > + emit_mov(mov,interpreter,info,prev,0,i,src,temp);
> > + emit_mov(mov,interpreter,info,prev,depth <=
> > 1,src,prev,temp);
> > + return 1;
> > + }
> > + if (val[i]!=2 )
> > + {
> > + depth++;
> > + int
> > x=reorder_move(a,val,i,src,depth,mov,interpreter,info,temp);
> > + depth--;
> > + emit_mov(mov,interpreter,info,prev,x && (depth <=
> > 1),src,prev,temp);
> > + return x;
> > + }
> > + }
> > + }
> > + val[src]=2;
> > + emit_mov(mov,interpreter,info,prev,0,src,prev,temp);
> > + return 0;
> > +}
> > +
> > +void emit_mov(reg_move_func mov,Interp *interpreter,void *info,int emit,int
> > emit_temp,int dest,int src,int temp)
> > +{
> > + if (emit >-1 )
> > + {
> > + if (emit_temp)
> > + {
> > + mov(interpreter,dest,temp,info);
> > + }
> > + else
> > + {
> > + mov(interpreter,dest,src,info);
> > + }
> > + }
> > +}
> > /*
> >
> > =back
>
> > Index: src/utils.c
> > ===================================================================
> > --- src/utils.c (revision 13113)
> > +++ src/utils.c (working copy)
> > @@ -48,6 +48,7 @@
> > =cut
> >
> > */
> > +#define MAX_REGISTER 256
> >
> > INTVAL
> > intval_mod(INTVAL i2, INTVAL i3)
> > @@ -678,12 +679,29 @@
> >
> > TODO add a define, if it's implemented so that we can start filling the
> > gaps
> >
> > +TODO The current implementation will not work for following cases
> > +
> > +1. I0->I1 I1->I0 I0->I3
> > +2. I1->I2 I3->I2
> > +
> > +Vishal Soni
> > =cut
> >
> > */
> >
> > /* proto TODO mv to hdr */
> > typedef int (*reg_move_func)(Interp*, unsigned char d, unsigned char s,
> > void *);
> > +int reorder_move(unsigned char (*a)[MAX_REGISTER],unsigned char *val ,int
> > src , int prev, int depth ,reg_move_func mov,Interp *interpreter,void
> > *info,int temp);
> > +int find_first_indegree(unsigned char (*a)[MAX_REGISTER] , int dest);
> > +int find_root(unsigned char (*a)[MAX_REGISTER],unsigned char* root_vertex
> > ,int src, int dest);
> > +void emit_mov(reg_move_func mov,Interp *interpreter,void *info,int
> > emit,int emit_temp,int src,int dest,int temp);
> > +void
> > +Parrot_register_move(Interp *interpreter, int n_regs,
> > + unsigned char *dest_regs, unsigned char *src_regs,
> > + unsigned char temp_reg,
> > + reg_move_func mov,
> > + reg_move_func mov_alt,
> > + void *info);
> >
> > void
> > Parrot_register_move(Interp *interpreter, int n_regs,
> > @@ -693,16 +711,113 @@
> > reg_move_func mov_alt,
> > void *info)
> > {
> > - int i;
> > + //int i;
> > /* TODO */
> >
> > /* brute force and wrong */
> > - for (i = 0; i < n_regs; ++i) {
> > + /* for (i = 0; i < n_regs; ++i) {
> > if (dest_regs[i] != src_regs[i])
> > mov(interpreter, dest_regs[i], src_regs[i], info);
> > + printf("Vishal:[%d],[%d]\n",dest_regs[i],src_regs[i]);
> > + }*/
> > +
> > + int i;
> > + unsigned char (*reg_move_graph)[MAX_REGISTER] = (unsigned char
> > (*)[MAX_REGISTER])mem_sys_allocate_zeroed(sizeof (unsigned
> > char)*MAX_REGISTER *MAX_REGISTER);
> > + unsigned char *root_vertx= (unsigned char
> > *)mem_sys_allocate_zeroed(sizeof (unsigned char)*MAX_REGISTER);
> > +
> > + for (i = 0 ; i < n_regs; i++)
> > + {
> > + reg_move_graph[src_regs[i]][dest_regs[i]]=1;
> > +
> > root_vertx[find_root(reg_move_graph,root_vertx,src_regs[i],dest_regs[i])]=1;
> >
> > }
> > +
> > + unsigned char *val = (unsigned char *)mem_sys_allocate_zeroed(sizeof
> > (unsigned char)*MAX_REGISTER);
> > + for (i = 0 ; i < MAX_REGISTER; i++)
> > + {
> > + if (root_vertx[i]>0)
> > + {
> > + mov(interpreter,temp_reg,i,info);
> > +
> > reorder_move(reg_move_graph,val,i,-1,0,mov,interpreter,info,temp_reg);
> > + }
> > + }
> > + free(val);
> > + free(reg_move_graph);
> > + free(root_vertx);
> > }
> >
> > +int find_root(unsigned char (*a)[MAX_REGISTER],unsigned char* root_vertex
> > ,int src, int dest)
> > +{
> > + if (a[src][dest]==2)
> > + {
> > + a[src][dest]=1;
> > + return dest;
> > + }
> > + root_vertex[src]=0;
> > + a[src][dest]=2;
> > + int in_degree=find_first_indegree(a,src);
> > + if (in_degree==-1)
> > + {
> > + a[src][dest]=1;
> > + return src;
> > + }
> > + return find_root(a,root_vertex,in_degree,src);
> > +}
> > +
> > +int find_first_indegree(unsigned char (*a)[MAX_REGISTER] , int dest)
> > +{
> > + int i=0;
> > + for( i= 0; i<MAX_REGISTER; i++)
> > + {
> > + if (a[i][dest] >0 )
> > + {
> > + return i;
> > + }
> > + }
> > + return -1;
> > +}
> > +int reorder_move(unsigned char (*a)[MAX_REGISTER],unsigned char (*val),int
> > src , int prev, int depth , reg_move_func mov,Interp *interpreter,void
> > *info,int temp)
> > +{
> > + int i=0;
> > + val[src]=1;
> > + for (i=0;i<MAX_REGISTER;i++)
> > + {
> > + if (a[src][i]>0 )
> > + {
> > + if (val[i]==1)
> > + {
> > + emit_mov(mov,interpreter,info,prev,0,i,src,temp);
> > + emit_mov(mov,interpreter,info,prev,depth <=
> > 1,src,prev,temp);
> > + return 1;
> > + }
> > + if (val[i]!=2 )
> > + {
> > + depth++;
> > + int
> > x=reorder_move(a,val,i,src,depth,mov,interpreter,info,temp);
> > + depth--;
> > + emit_mov(mov,interpreter,info,prev,x && (depth <=
> > 1),src,prev,temp);
> > + return x;
> > + }
> > + }
> > + }
> > + val[src]=2;
> > + emit_mov(mov,interpreter,info,prev,0,src,prev,temp);
> > + return 0;
> > +}
> > +
> > +void emit_mov(reg_move_func mov,Interp *interpreter,void *info,int
> > emit,int emit_temp,int dest,int src,int temp)
> > +{
> > + if (emit >-1 )
> > + {
> > + if (emit_temp)
> > + {
> > + mov(interpreter,dest,temp,info);
> > + }
> > + else
> > + {
> > + mov(interpreter,dest,src,info);
> > + }
> > + }
> > +}
> > /*
> >
> > =back
>
>
