[perl #39694] Re: [PATCH] #38627: [TODO] fill Parrot_register_move() with code
# New Ticket Created by Vishal Soni # Please include the string: [perl #39694] # in the subject line of all future correspondence about this issue. # URL: https://rt.perl.org/rt3/Ticket/Display.html?id=39694 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,
Re: [PATCH] #38627: [TODO] fill Parrot_register_move() with code
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 */
Re: [PATCH] #38627: [TODO] fill Parrot_register_move() with code
On Mon, Jul 03, 2006 at 03:39:19PM -0500, Vishal Soni wrote: On Mon, 2006-07-03 at 13:03 -0700, Chip Salzenberg wrote: The use of a fixed constant like MAX_REGISTER doesn't really work; Parrot has an unbounded (if not infinite :-)) number of registers [...] 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. Well look at that. If I'd looked a bit closer at the diffs I might have noticed that myself. That's definitely an RT-able bug. Let me know what case do we need to code for unbounded number of registers or 256 registers for now. The former, please. I'd consider it the beginning of fixing that bug about using 'unsigned char' for 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. I don't know if it would help, but Audrey speaks highly of the Judy library: http://judy.sourceforge.net/ which provides sparse dynamic arrays in what is apparently a very efficient way. If Judy would provide the best solution, we could have Parrot use it. -- Chip Salzenberg [EMAIL PROTECTED]
[perl #39695] Re: [PATCH] #38627: [TODO] fill Parrot_register_move() with code
# New Ticket Created by Chip Salzenberg # Please include the string: [perl #39695] # in the subject line of all future correspondence about this issue. # URL: https://rt.perl.org/rt3/Ticket/Display.html?id=39695 On Mon, Jul 03, 2006 at 03:39:19PM -0500, Vishal Soni wrote: On Mon, 2006-07-03 at 13:03 -0700, Chip Salzenberg wrote: The use of a fixed constant like MAX_REGISTER doesn't really work; Parrot has an unbounded (if not infinite :-)) number of registers [...] 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. Well look at that. If I'd looked a bit closer at the diffs I might have noticed that myself. That's definitely an RT-able bug. Let me know what case do we need to code for unbounded number of registers or 256 registers for now. The former, please. I'd consider it the beginning of fixing that bug about using 'unsigned char' for 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. I don't know if it would help, but Audrey speaks highly of the Judy library: http://judy.sourceforge.net/ which provides sparse dynamic arrays in what is apparently a very efficient way. If Judy would provide the best solution, we could have Parrot use it. -- Chip Salzenberg [EMAIL PROTECTED]
[PATCH] #38627: [TODO] fill Parrot_register_move() with code
This patch implements the register content preserving move operation.
Thanks,VishalPreviously:-Now:1..3ok 1 - in P paramok 2 - tailcall 1not 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..3ok 1 - in P paramok 2 - tailcall 1ok 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 256INTVALintval_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);voidParrot_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; iMAX_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;iMAX_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
[perl #39683] [PATCH] #38627: [TODO] fill Parrot_register_move() with code
# New Ticket Created by Vishal Soni
# Please include the string: [perl #39683]
# in the subject line of all future correspondence about this issue.
# URL: https://rt.perl.org/rt3/Ticket/Display.html?id=39683
This transaction appears to have no contentThis 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; iMAX_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;iMAX_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
