Register Allocator
Hi, I read the #parrotsketch log from today. I cannot join the IRC now. The Graph based Register allocation is good for statically compiled languages like C. The real value of Graph Based allocation comes when you have limited number of registers and have to spill some of the variables to memory. Which variable goes to memory is decided by a cost function. The other issue might be Def-Usage (DU) chains. In a 9000 lines sub this might be getting to large. Going to Single Static Assignment(SSA) form eliminates the need of DU chains. I plan on implementing SSA in Byte Code Generator. But that is future. I need some decisions to be made on POST nodes to continue my work with BCG. In Parrot we do not have to worry about spilling as we can assume we have infinite number of registers of I,P,N and C type. Linear Scan allocation is good but would require some time to implement as it goes after the data collected from live varaible analysis. The simpler solution is to not do any optimization for reducing the number of registers. This is fine for now as we are in a development phase. IMHO getting things working is more important than optimization. I should be able to hack up a vanilla register allocation scheme that does no live variable analysis to find overlapping registers to reduce the number of registers. Currently I have implemented this scheme in Byte Code Generator (compilers/bcg/src/bcg_reg_alloc_vanilla.c). All this does is it makes sure each varaible gets a unique register. The quality of the code generate might not be good but this should be very fast in compile time performance compared to Graph Based allocator. This should be simple to do and we can still keep the graph allocator but only run it when the optimization flag -Ox is used. Let me know your thoughts. I'll try to catch you guys later on IRC. -- Thanks, Vishal
Shared Lib fro Dynamic PMC
Hi, I need to have a shared lib for a Dynamic PMC. The shared lib is generated from my own code. What is a good location to place the shared lib that I generate? Is lib/blib a good location? This is for Byte Code generator. -- Thanks, Vishal
Flex Debugging
Hi, Can some one help me with Flex debugging? Previously if I recall correctly the adding %option debug in imcc.l use to spit out debug information to the console. This does not seem to work now. Am I doing something wrong? -Vishal
Re: IMCC Reentrancy
On Mon, 2006-07-17 at 14:49 -0700, Allison Randal wrote: re2c and lemon aren't enough of an improvement over flex and bison to be worth the pain of rewriting IMCC from scratch. If we do create a new way of producing bytecode (and it's a safe bet that we will at some point), I would lean toward using our own tools. - Patrick is already looking into implementing a version of PGE in C. This will be an infinitely better parser than any existing alternatives, so it's worth waiting for. - We already want an OST(opcode syntax tree)-to-bytecode compiler that bypasses PIR for the compiler tools. That same compiler could be used to implement PIR (combined with a lightweight version of TGE in C). - IMCC is not a straight translator, it also performs optimizations. These should be implemented in a modular way, with a standard interface, so that developers can swap in new and improved optimizers as we go along. The best place to hook them is probably off the OST-to-bytecode compiler. Allison having said that we need an API for byte code generation that supports plug n play optimizers would it make sense to start implementing this layer. This API could be used for OST to byte code generation. Later when Patrick's PGE to C parser generator is ready we could use his code to implement the PIR compiler and just use the API's that we write for byte code generation. Initially for prototyping purposes we might just use the existing flex/yacc or re2c/lemon. Allison should this development wait or can we start working on it? Will we need a PDD before we can commence working on this API. Let me know your thoughts. It might not hurt to start working on a Prototype API and see how it fits withe OST-to-bytecode compiler. This approach does mean that the tools to start an IMCC rewrite aren't available yet. It's a long-term solution (possibly post-1.0), so we can afford to take a long-term view. Allison
Re: IMCC Reentrancy
Let's go for an agile, iterative approach to the spec. Write up some initial thoughts on the shape of the API and post them to parrot-porters. The group can do sanity-checking/brainstorming, and then you can start a prototype based on the result. After we've played with the prototype a bit (and probably after you've modified it a few times based on feedback from the group), I'll write a PDD to flesh out the spec, fill in any holes, and address any problems encountered along the way. Allison this sounds great. To get started I will need some reference to the OST format. Can you please point me in the right direction (some documentation or sample code shall do.)? I will assume the implementation of the Byte Code Generation/ Optimization API will be implemented in C (TGE could use loadlib or some PMC mechanism to call it). Let me know if my assumption is correct or does this API need to be in PIR. Thanks, Allison
IMCC Reentarancy
Hi, I have been working on trying to make reenterant and/or thread-safe. There are couple of things that have come up which might make it difficult to make the existing implemention thread-safe/re-entrant. The current implementation is implemented using Flex and YACC. Flex implementation has limitations in C mode. The C lexer generated by flex cannot be reentrant/threadsafe. Flex generates thread-safe parsers only in C++ mode. This limation of flex will defeat the whole effort of removing global variables from IMCC. In my opinion if we cannot get global variable free code from flex there is no sense in proceeding with cleaning up the other global variables. Audrey Tang reccomended using re2c as an alternative to flex (Lemon Parser replacemet for Yacc). re2c generates reenterant/thread-safe parsers. I also spend some time reading up on the paper published with re2c. Initial indicators are that it produces scanners that run faster than flex. So here are some options that I have come up with that we have. I would like you guys and especially Allison and Chip to provide some feedback on how to proceed further. 1st Option: Hack it and patch it to death !!! --- Since flex is not generating re-eentrant code, this option will get rid of flex altogether and replace it with re2c. This would require significant reworking on the code. So the plan of action would be as follows: a. Remove flex and implement re2c 2nd: Inaction is the best action !!! --- 3rd Option: Back to drawing board !!! -- Thanks, Vishal
Re: IMCC Reentarancy
Hi, Please disregard the previous mail. Hit the wrong shortcut key!! I have been working on trying to make reenterant and/or thread-safe. There are couple of things that have come up which might make it difficult to make the existing implementation thread-safe/re-entrant. The current implementation is implemented using Flex and YACC. Flex implementation has limitations in C mode. The C lexer generated by flex cannot be reentrant/threadsafe. Flex generates thread-safe parsers only in C++ mode. This limition of flex will defeat the whole effort of removing global variables from IMCC. In my opinion if we cannot get global variable free code from flex there is no sense in proceeding with cleaning up the other global variables. Audrey Tang recommended using re2c as an alternative to flex (Lemon Parser replacement for Yacc). re2c generates reenterant/thread-safe parsers. I also spend some time reading up on the paper published with re2c. Initial indicators are that it produces scanners that run faster than flex. So here are some options that I have come up with that we have. I would like you guys and especially Allison and Chip to provide some feedback on how to proceed further. 1st Option: Hack it and patch it to death !!! --- Since flex is not generating reeentrant code, this option will get rid of flex altogether and replace it with re2c. This would require significant reworking on the code. So the plan of action would be as follows: a. Remove flex and implement re2c b. Remove static and global variables Apart from this we also need to refactor the code to get rid of arrays to a hash table implementation for macros. All in all this would be over hauling lot of code. 2nd: Inaction is the best action !!! --- Lets not do anything a leave the code as it is. Just say IMCC is not re-entrant/thread-safe and leave it there We will address this issue in future. I highly doubt it this is the route we want to take 3rd Option: Back to drawing board !!! This option would require a complete re-write of IMCC ( possibly could call it PIRC). The cons of this approach is we will have to re-implement the whole IMCC again. The programming languages will have to live with IMCC limitations as long as the new version is ready. The pros of this approach are a. A clean implementation rather than a prototypish implementation b. Make PIR compiler production release ready. The way the compiler sits right now it is not a good release candidate. c. Structure the code in a way that is easy to maintain and extend. The 3rd option is lot of work but might be a good option in the long run. These are just some of my thoughts. Please let me know what you guys think or do you have other options in mind. Whatever it is we need to come to consensus to make the IMCC reenterany a reality. As usual please provide feedback. -- Thanks, Vishal On 7/16/06, Vishal Soni [EMAIL PROTECTED] wrote: Hi, I have been working on trying to make reenterant and/or thread-safe. There are couple of things that have come up which might make it difficult to make the existing implemention thread-safe/re-entrant. The current implementation is implemented using Flex and YACC. Flex implementation has limitations in C mode. The C lexer generated by flex cannot be reentrant/threadsafe. Flex generates thread-safe parsers only in C++ mode. This limation of flex will defeat the whole effort of removing global variables from IMCC. In my opinion if we cannot get global variable free code from flex there is no sense in proceeding with cleaning up the other global variables. Audrey Tang reccomended using re2c as an alternative to flex (Lemon Parser replacemet for Yacc). re2c generates reenterant/thread-safe parsers. I also spend some time reading up on the paper published with re2c. Initial indicators are that it produces scanners that run faster than flex. So here are some options that I have come up with that we have. I would like you guys and especially Allison and Chip to provide some feedback on how to proceed further. 1st Option: Hack it and patch it to death !!! --- Since flex is not generating re-eentrant code, this option will get rid of flex altogether and replace it with re2c. This would require significant reworking on the code. So the plan of action would be as follows: a. Remove flex and implement re2c 2nd: Inaction is the best action !!! --- 3rd Option: Back to drawing board !!! -- Thanks, Vishal -- Thanks, Vishal
Re: [perl #39715] [TODO] #39715 IMCC errors should throw Parrot exceptions
PARROT_API void *Parrot_compile_file(Parrot_Interp interpreter,char *fullname, String **error); I like this interface, except for the return value from Parrot_compile_file. Are there other options, such as returning a Sub PMC? Chip and I have had a chat about other possible API's which could be added in future. Some e.g. 1. To throw Parrot exceptions instead of the String **error. 2. Possibly using Compiler PMC. (not sure on that yet) Your suggestion is good and I will keep in mind. These two functions are just a start for defining Compile API's. Programming languages should not talk directly to IMCC or any other low level compiler like IMCC and PASM. Thanks for your suggestion. Vishal
Re: Java Script in Parrot
Hi Patrick,
This is is a good starting point. I have been writing the JavaScript grammar
in PGE fromECMA-262 spec. They lay out the operator precedence using Grammar
rules. Instead of using rules for operator precedence I would like to use
your optok approach. Is there some help I can get? I did look at your YAPC
2006 presentation. Are there any code examples?
The other that would be great to have is if we could suport Unicode
Character classes in PGE for e.g. [\u2028-\u2050]. JavaScript
specification assumes that the Source could be in Unicode format.
-Vishal
On 7/10/06, Patrick R. Michaud [EMAIL PROTECTED] wrote:
On Mon, Jul 10, 2006 at 09:19:14PM +0100, Norman Nunley, Jr wrote:
There's a rules grammar in http://svn.openfoundry.org/pugs/misc/
JavaScript-FrontEnd/Grammar.pm
When I last attempted to compile it with PGE, it gave up the ghost in
the character class definitions.
Wow, thanks for the update. PGE seems to be having trouble with
the -xyz rules, which are currently unimplemented. But the
grammar is also using incorrect regex syntax -- the statements
like:
rule no_LineTerminator_here {
[ ws -LineTerminator*? ]
}
rule USP { Zs-TAB-VT-FF-SP-NBSP }
need to eliminate the inner angles, as in:
rule no_LineTerminator_here {
[ ws -LineTerminator*? ]
}
rule USP { +Zs-TAB-VT-FF-SP-NBSP }
But I think the no_LineTerminator_here rule probably needs
to be rewritten altogether to avoid the conjunction.
At any rate, this is a very useful start; I think it could
be updated quite quickly. Thanks!
Pm
On 10 Jul 2006, at 20:47, Patrick R. Michaud wrote:
On Sun, Jul 09, 2006 at 04:11:55PM -0700, chromatic wrote:
On Sunday 09 July 2006 02:15, Vishal Soni wrote:
I am not an expert on which approach is the way to go:
1. Hack Mozilla's JavaScript excution engine to generate PIR.
If there's a fairly direct correspondence between JS bytecode (if
there is
such a thing; I have no idea -- whatever internal ops it uses to
represent a
program to execute), this may be easiest to start.
2. Use the Compiler Tool Chain developed by Parrot Wizards to
implement
JavaScript engine.
This is probably the best long-term approach, at least if you find
someone
good to write the grammar. (I hate parsing.)
FWIW, I'm more than happy to help with the grammar, especially if
there's an existing definition to work from.
Pm
--
Thanks,
Vishal
Re: Java Script in Parrot
Thanks Chris
I looked at it but it does not implement Unicode in PGE and Optok too..
On Mon, 2006-07-10 at 23:30 -0500, Chris Dolan wrote:
On Jul 10, 2006, at 4:31 PM, Vishal Soni wrote:
This is is a good starting point. I have been writing the
JavaScript grammar
in PGE fromECMA-262 spec. They lay out the operator precedence
using Grammar
rules. Instead of using rules for operator precedence I would like
to use
your optok approach. Is there some help I can get? I did look at
your YAPC
2006 presentation. Are there any code examples?
Take a look at parrot/languages/punie/lib/{punie.pg,PunieGrammar.pir}
which has both bottom up and top down parsing. I found it very
educational.
Chris
--
Chris Dolan, Software Developer, http://www.chrisdolan.net/
Public key: http://www.chrisdolan.net/public.key
vCard: http://www.chrisdolan.net/ChrisDolan.vcf
Re: Re: [perl #39777] Large Subroutine Segfaults IMCC
Hi Matt, I can patch up something that would spit out an error message and exit rather than Segfaulting. Right now there is no bounds check. Other thing I could do is re-allocate the Macro Array size when it gets full. So it would not fail until system starts swapping :-) I would prefer the second option. Because it might hinder your and other language development. This might become a bigger issue as you start writing bigger programs or libraries. Let me know your thoughts. -Vishal On Mon, 2006-07-10 at 22:11 -0700, Matt Diephouse wrote: Vishal Soni [EMAIL PROTECTED] wrote: Hi Matt, This patch is because the number of .constant decls in IMCC is limited to 4096. This is a todo to make this dynamic. The evil code seems to have about 4200 .constant decls being generated. Here is the patch to fix it. For now I bumped up the limit to 8192 and it works. But this is a TODO for sure. Thanks for investigating this, Vishal. Coke mentioned on IRC that he had bumped this number up once before. I'll change the ticket in RT to document the real problem. In the meantime, would it be possible to die with an error saying too many .constants instead of just segfaulting? Thanks again,
Re: Java Script in Parrot
Hi Norman, I am also in the implementing Java Script for Parrot. But the approach I have taken is, that I picked up the ECMA-262 Spec 3rd Edition and I have implemented in Parrot Grammar Engine (PGE). Write now I have implemented more than half of Java Script grammar in PGE to compile correctly. My game plan is as follows: 1. Implement Java Script Grammar in PGE 2. Convert PGE- PAST. 3. Convert PAST- POST. 4. Convert POST- Byte code. I have seen the Test bed from Mozillla and I plan to start using it once I have a testable implementation. I am not an expert on which approach is the way to go: 1. Hack Mozilla's JavaScript excution engine to generate PIR. 2. Use the Compiler Tool Chain developed by Parrot Wizards to implement JavaScript engine. Parrot experts any thoughts or comments. Any feedback as to how to unify the efforts if possible would be highly valuable. -Vishal Soni On Sun, 2006-07-09 at 09:51 +0100, Norman Nunley, Jr wrote: I've started work on a Javascript implementation, but haven't gotten very far yet. I've starting with the Narcissus implementation from the Mozilla project. My current plan is to: 1. Identify any objects that need to be bootstrapped into PMCs. 2. Write a Compile phase that borrows logic from jsexec.js, and convert it to a PIR generator. 3. Run it once in a Narcissus enabled SpiderMonkey interpreter. The Mozilla project has a huge suite of tests for EMCAScript compliance, which might be a good thing to borrow for any Parrot based Javascript implementation. Regards, Norman Nunley On 7 Jul 2006, at 17:34, Vishal Soni wrote: Hi, Is any one working on Java Script(ECMA-262) implementation in Parrot? -- Thanks, Vishal
Re: [perl #39777] Large Subroutine Segfaults IMCC
Hi Matt, This patch is because the number of .constant decls in IMCC is limited to 4096. This is a todo to make this dynamic. The evil code seems to have about 4200 .constant decls being generated. Here is the patch to fix it. For now I bumped up the limit to 8192 and it works. But this is a TODO for sure. I ran the after bumnping up the limit and it seems to work. After applying the patch If you have lex perl Configure.pl --lex=lex If you have flex perl Configure.pl --lex=lex make -Vishal Index: compilers/imcc/imcc.l === --- compilers/imcc/imcc.l (revision 13220) +++ compilers/imcc/imcc.l (working copy) @@ -31,7 +31,7 @@ }; /* XXX: boe: rework this hack to use a hash */ -#define N_MACROS 4096 +#define N_MACROS 8192 struct macro_t macros[N_MACROS]; int num_macros = 0; On Sun, 2006-07-09 at 20:49 -0700, Matt Diephouse wrote: # New Ticket Created by Matt Diephouse # Please include the string: [perl #39777] # in the subject line of all future correspondence about this issue. # URL: http://rt.perl.org/rt3/Ticket/Display.html?id=39777 The attached file, which has a ~1 line subroutine, makes IMCC segfault. Segfault bad. -- Matt Diephouse
Parrot Exceptions
Hi, I would like to throw a Parrot Exception from IMCC to the calling program instead of terminating IMCC when a parse error occurs. Are there some example in Parrot as to how to throw a Parrot exception and how to catch it? -Vishal
Java Script in Parrot
Hi, Is any one working on Java Script(ECMA-262) implementation in Parrot? -- Thanks, Vishal
Re: [perl #38594] [BUG] source line numbers
Hi Chip, Can you please apply this patch for me? This is a fix to the YACC file. As a result you will also have to checkin the imcparser.c and imcparser.h after applying the patch and recompiling the source. Thanks, Vishal Index: compilers/imcc/imcc.y === --- compilers/imcc/imcc.y (revision 13035) +++ compilers/imcc/imcc.y (working copy) @@ -202,7 +202,7 @@ r-type = (r-type VT_ENCODED) ? VT_PCC_SUB|VT_ENCODED : VT_PCC_SUB; r-pcc_sub = calloc(1, sizeof(struct pcc_sub_t)); cur_call = r; -i-line = line - 1; +i-line = line ; add_namespace(interp, unit); return i; } On 7/3/06, Vishal Soni [EMAIL PROTECTED] wrote: Will, Did we get this one in? -Vishal On 6/30/06, Vishal Soni [EMAIL PROTECTED] wrote: Hi, The .end seems to be replaced by an implicit end. -Vishal On 6/29/06, Will Coleda via RT [EMAIL PROTECTED] wrote: Hey, Vishal: [vsoni - Tue Jun 27 05:48:27 2006]: Hi, This was a straight forward fix. The line number was being decremented at the start of a 'sub' token imcc.y. Thanks, Vishal Here is a sample run Sample Code: --- .sub main :main print 2\n print 3\n print 4\n .end Output: ./parrot -d 10 ./hello.pir 1 last:5 pcc_sub main nparams 0 Dumping the instructions status: --- nins line blck deep flags type opnr size pc X ins 0100 0 8 -100 main: 1200 1 0 41320print 2\n 2300 1 0 41322print 3\n 3400 1 0 41324print 4\n 4400 0 18000016end Looks like the first line is fixed there (1) and then the guts are fixed (2,3,4), but is the duplicate line 4 correct? (is that corresponding to the implicit end that PIR puts in, or the .end of the subroutine? If you can just validate that, we can apply this. Labels namepos last ref --- Dumping the CFG: --- 0 (0)- - Dumping the Dominators Tree: --- 0 - ( 0) 0 Loop info - Patch Index: compilers/imcc/imcc.y = == --- compilers/imcc/imcc.y (revision 13035) +++ compilers/imcc/imcc.y (working copy) @@ -202,7 +202,7 @@ r-type = (r-type VT_ENCODED) ? VT_PCC_SUB|VT_ENCODED : VT_PCC_SUB; r-pcc_sub = calloc(1, sizeof(struct pcc_sub_t)); cur_call = r; -i-line = line - 1; +i-line = line ; add_namespace(interp, unit); return i; } -- Thanks, Vishal -- Thanks, Vishal -- Thanks, Vishal
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
[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
Re: [perl #38594] [BUG] source line numbers
Will, Did we get this one in? -Vishal On 6/30/06, Vishal Soni [EMAIL PROTECTED] wrote: Hi, The .end seems to be replaced by an implicit end. -Vishal On 6/29/06, Will Coleda via RT [EMAIL PROTECTED] wrote: Hey, Vishal: [vsoni - Tue Jun 27 05:48:27 2006]: Hi, This was a straight forward fix. The line number was being decremented at the start of a 'sub' token imcc.y. Thanks, Vishal Here is a sample run Sample Code: --- .sub main :main print 2\n print 3\n print 4\n .end Output: ./parrot -d 10 ./hello.pir 1 last:5 pcc_sub main nparams 0 Dumping the instructions status: --- nins line blck deep flags type opnr size pc X ins 0100 0 8 -100 main: 1200 1 0 41320print 2\n 2300 1 0 41322print 3\n 3400 1 0 41324print 4\n 4400 0 18000016end Looks like the first line is fixed there (1) and then the guts are fixed (2,3,4), but is the duplicate line 4 correct? (is that corresponding to the implicit end that PIR puts in, or the .end of the subroutine? If you can just validate that, we can apply this. Labels namepos last ref --- Dumping the CFG: --- 0 (0)- - Dumping the Dominators Tree: --- 0 - ( 0) 0 Loop info - Patch Index: compilers/imcc/imcc.y = == --- compilers/imcc/imcc.y (revision 13035) +++ compilers/imcc/imcc.y (working copy) @@ -202,7 +202,7 @@ r-type = (r-type VT_ENCODED) ? VT_PCC_SUB|VT_ENCODED : VT_PCC_SUB; r-pcc_sub = calloc(1, sizeof(struct pcc_sub_t)); cur_call = r; -i-line = line - 1; +i-line = line ; add_namespace(interp, unit); return i; } -- Thanks, Vishal -- Thanks, Vishal
[PATCH]#38469: [BUG] -O1 branch optimization
This patch fixes the branch reorganization failing for tail recursion.Previously.---$ ./parrot -Oc ack.pir 3Ack(3, 3) = 61
$ /parrot -Oc1 ack.pir 3maximum recursion depth exceeded (According to Leo)But on Linux I was getting a segfault.After--$ ./parrot -Oc ./examples/shootout/ack.pir 3
Ack(3, 3) = 61$ ./parrot -Oc1 ./examples/shootout/ack.pir 3Ack(3, 3) = 61Thanks,VishalIndex: CREDITS===
--- CREDITS (revision 13046)+++ CREDITS (working copy)@@ -470,3 +470,7 @@N: Norman NunleyD: Shaving a PonieE: [EMAIL PROTECTED]++N: Vishal Soni
+E: [EMAIL PROTECTED]+D: Bug fixes in IMCCIndex: compilers/imcc/optimizer.c===--- compilers/imcc/optimizer.c (revision 13046)
+++ compilers/imcc/optimizer.c (working copy)@@ -932,7 +932,7 @@ } /* this was screwing up multi-block loops... */- if (end != ins) {
+ if (end != ins ins-next !=NULL ) { ins-next-prev = end; start-prev-next = end-next; if (end-next)
-- Thanks,Vishal
Index: CREDITS
===
--- CREDITS (revision 13046)
+++ CREDITS (working copy)
@@ -470,3 +470,7 @@
N: Norman Nunley
D: Shaving a Ponie
E: [EMAIL PROTECTED]
+
+N: Vishal Soni
+E: [EMAIL PROTECTED]
+D: Bug fixes in IMCC
Index: compilers/imcc/optimizer.c
===
--- compilers/imcc/optimizer.c (revision 13046)
+++ compilers/imcc/optimizer.c (working copy)
@@ -932,7 +932,7 @@
}
/* this was screwing up multi-block loops... */
-if (end != ins) {
+if (end != ins ins-next !=NULL ) {
ins-next-prev = end;
start-prev-next = end-next;
if (end-next)
Re: [perl #38594] [BUG] source line numbers
Hi, The .end seems to be replaced by an implicit end. -Vishal On 6/29/06, Will Coleda via RT [EMAIL PROTECTED] wrote: Hey, Vishal: [vsoni - Tue Jun 27 05:48:27 2006]: Hi, This was a straight forward fix. The line number was being decremented at the start of a 'sub' token imcc.y. Thanks, Vishal Here is a sample run Sample Code: --- .sub main :main print 2\n print 3\n print 4\n .end Output: ./parrot -d 10 ./hello.pir 1 last:5 pcc_sub main nparams 0 Dumping the instructions status: --- nins line blck deep flags type opnr size pc X ins 0100 0 8 -100 main: 1200 1 0 41320print 2\n 2300 1 0 41322print 3\n 3400 1 0 41324print 4\n 4400 0 18000016end Looks like the first line is fixed there (1) and then the guts are fixed (2,3,4), but is the duplicate line 4 correct? (is that corresponding to the implicit end that PIR puts in, or the .end of the subroutine? If you can just validate that, we can apply this. Labels namepos last ref --- Dumping the CFG: --- 0 (0)- - Dumping the Dominators Tree: --- 0 - ( 0) 0 Loop info - Patch Index: compilers/imcc/imcc.y = == --- compilers/imcc/imcc.y (revision 13035) +++ compilers/imcc/imcc.y (working copy) @@ -202,7 +202,7 @@ r-type = (r-type VT_ENCODED) ? VT_PCC_SUB|VT_ENCODED : VT_PCC_SUB; r-pcc_sub = calloc(1, sizeof(struct pcc_sub_t)); cur_call = r; -i-line = line - 1; +i-line = line ; add_namespace(interp, unit); return i; } -- Thanks, Vishal
IMCC Register Allocation Algorithm
Hi Everyone, Currently IMCC uses a Graph Coloring based Register allocation algorithm. The implementation is a trimmed down version of Brigg's Allocator. I came across this research paper that talks about the new register allocation algorithm Linear Scan Allocationfor dynamically compiled languages. Parrot perfectly fits the mold of dynamically compiled language. The Linear Scan Allocator is faster at register allocation process and seems to have the same execution time for the code. For more information please refer to the research paper from IBM on Liner Scan Allocation http://www.research.ibm.com/jalapeno/papers/toplas99.pdf Let me know what your thoughts are and would it be worth implementing this algorithm to see how it performs compared to graph coloring algorithm. Please share your thoughts accordingly -- Thanks, Vishal
Parrot Platform API
Hi Chip, I have been looking at the Parrot code for last couple of weeks. While going through the code there were a few things that striked me. There are quite a few places where #ifdef constructs were used to define platform specific code (#ifdef WIN32). I was thinking would it make sense to define a Parrot Platform API that all parrot ports need to implement. This is very similar to the Linux kernel source. During the build time we should be able to resolve the platform specific code and link it in the parrot executable. There are couple of advantages of this. 1. Define a clean API that new parrot ports need to implement. 2. Keeps platforms specific code out of the parrot's core logic. 3. The new ports will not introduce bugs for already working ports. I have had some discusion with Leo about this and he thought it might be a good idea to run it by you. My initial thoughts are we could include following things could be added to the Parrot Platform API: 1. File I/O. This includes sync as well as async I/O. For platforms that do not have native Async I/O support we could build an emulation of Async I/O. 2. Network I/O: This would include API for TCP, UDP and possibly SCTP (Stream control Transmission protocol). 3. Threads and Mutexes 4. Signals / Events () 5. Environment: API to read the environment variables from OS 6. Math library (we could possibly use http://www.netlib.org/fdlibm/ for platforms that support IEEE 754 floating-point arithmetic) The idea is to define a clean seperation between parrot and the platform parrot is running on. The Parrot Platform API would possibly be the interface via which the Parrot VM discovers the platform specific functionality. A good example of a simiar abstraction is the Apache Portable Runtime ( http://apr.apache.org/). This is used in the Apache HTTP Webserver. Let me know what your thoughts are. I would not mind writing up a draft PDD or doing some proof of concept work. -- Thanks, Vishal
Parrot IO
Hi, Is Parrot IO going to be implemented via opcodes or PMC? I looked at some old email discussion. There were discussions on refactoring some IO opcodes to PMC's (e.g socket opcodes). Have we reached on any decisions as to how we are going to implement the Parrot IO? -- Thanks, Vishal
Re: [perl #38146] [TODO] OS.pmc - file copy 38146
Hi Leo, So do we need to change os.pmc to leverage this infrastructure and get rid of the platform specific code( currently implemented via IFDEF) from os.pmc? -Vishal On 6/19/06, Leopold Toetsch [EMAIL PROTECTED] wrote: On Jun 18, 2006, at 2:02, Vishal Soni via RT wrote: I am just wonedring if it would make sense to seperate out code for each supported operating system under a directory structure. At the time of build the specific code for target operating system is added to the source tree. Yep. Actually we already have and use the needed infrastructure for platform code. See also: - config/gen/platform* - src/platform.c (generated from above) leo -- Thanks, Vishal
[perl #38146] [TODO] OS.pmc - file copy 38146
Hi, I am trying implement #38146 todo item. While looking at the code for os.pmc there are IFDEF constructs defined for different operating systems (For e.g. WIN32 for now). I am just wonedring if it would make sense to seperate out code for each supported operating system under a directory structure. At the time of build the specific code for target operating system is added to the source tree. This very similar to the Linux source tree where the architecture specific code is implemented in a differen directory structure and correct directory structure is selected based on the architecture you are compiling for. There a couple of benifits that come to mind: 1. All the OS specific is maintained under seperated directory structure for each OS. 2. Defines a clean seperation b/w OS and Parrot Code. 3. Makes it easy to port Parrot to new platforms without breaking the implemented functionality for other platforms. Let me know what your thoguths are. Thanks, Vishal
[perl #38146] [TODO] OS.pmc - file copy 38146
Hi, I am trying implement #38146 todo item. While looking at the code for os.pmc there are IFDEF constructs defined for different operating systems (For e.g. WIN32 for now). I am just wonedring if it would make sense to seperate out code for each supported operating system under a directory structure. At the time of build the specific code for target operating system is added to the source tree. This very similar to the Linux source tree where the architecture specific code is implemented in a differen directory structure and correct directory structure is selected based on the architecture you are compiling for. There a couple of benifits that come to mind: 1. All the OS specific is maintained under seperated directory structure for each OS. 2. Defines a clean seperation b/w OS and Parrot Code. 3. Makes it easy to port Parrot to new platforms without breaking the implemented functionality for other platforms. Let me know what your thoguths are. Thanks, Vishal
