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. 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.... (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 -- Chip Salzenberg <[EMAIL PROTECTED]>
