PGE bug?
Leopold Toetsch
realized that some PGE tests [2] are only failing with this patch installed.
I traced the created code on two different machines (the other w/o the
patch) and diffed the trace log. After a few rounds through the match
loop, one register suddenly differs by one, giving differing tests output.
I was not able to fully follow the control flow of the generated code
first, as the returned subroutine string seems to be different from the
one actually created. But:
$ parrot -D20 b_10.pir
eventually revealed the failing location, visbile in the debug file EVAL_1:
...
R5:
save pos
bsr R6
if cutting != goto fail <<<<<<<<<<<<<
goto R7
cutting is suddenly 1.
Given that there are several bsr calls involved and recursion, method
calls, yields() and what not, I'd just expect that the register of the
variable "cutting" (I15) is somewhere reused. Unlike other variables
like "pos" it's not saved on the user stack.
Using bsr/ret is fine only, if there are no function/method calls
intermixed that assume "caller saves". The generated code seems to
follow this scheme by protecting such calls with saveall/restoreall but
due to the wicked control flow inside the created code, it's extremely
complicated to verify the correctness of all the branches.
It's of course as well possbile that my patch still has a bug somewhere.
Nethertheless I think that the generated code is the culprit ;-)
I still consider the decision of using bsr/ret [3] inside pge as being
wrong or at least premature [4], but that's another point.
Anyway the question is: is the generated code for builtins_10 correct?
Thanks,
leo
[1] ticket #36374 context_4.patch
[2] e.g. builtins_10 <b2 @ 5 > 0
[3] <citing pge/README>
The generated code uses bsr/ret for its internal subroutine calls
(also optimized for tailcalls) and then uses Parrot calling
conventions for all interfaces with external callers/callees.
This should give some performance improvements.
</citing>
[4] function call tracing would IMHO simplify debugging a lot
Patrick R. Michaud
> During testing of the upcoming changes to the context handling [1] I
> realized that some PGE tests [2] are only failing with this patch installed.
> I traced the created code on two different machines (the other w/o the
> patch) and diffed the trace log. After a few rounds through the match
> loop, one register suddenly differs by one, giving differing tests output.
>
> I was not able to fully follow the control flow of the generated code
> first, as the returned subroutine string seems to be different from the
> one actually created. But:
>
> $ parrot -D20 b_10.pir
>
> eventually revealed the failing location, visbile in the debug file EVAL_1:
>
> ...
> R5:
> save pos
> bsr R6
> if cutting != goto fail <<<<<<<<<<<<<
> goto R7
>
> cutting is suddenly 1.
Just to verify -- I think there's a cut-and-paste error here and it should be
if cutting != 0 goto fail
> Given that there are several bsr calls involved and recursion, method
> calls, yields() and what not, I'd just expect that the register of the
> variable "cutting" (I15) is somewhere reused. Unlike other variables
> like "pos" it's not saved on the user stack.
Yes, it's not supposed to be saved, because the bsr call at R6 is
allowed to change "cutting" to indicate that we've hit a cut operation
and that previous nodes should be backtracking until we reach the
correct cut point (an alternation, group, subrule, rule, or match).
I suspect it's an issue with register spilling, that I15 is being
reused somewhere later to represent something other than the "cutting"
value. I've noticed this problem a few other times and I'm working out
ways to deal with it.
Given that the register spilling algorithm has trouble understanding
the control flow here (which, to be honest, isn't actually as bizarre
as it initially appears), what would be most helpful to PGE would be to
have a way to define symbolic names for registers that *don't* participate
in the register spilling allocator. The routines that PGE generates
only need a total of nine PMC registers, ten integer registers,
and three string registers, so spilling shouldn't be needed at all.
Lacking this, I'm thinking I'll end up just re-coding PGE to always
use hard-coded registers rather than symbolic equivalents -- it will
make the code less readable, but I won't have to worry about registers
spilling when I don't want them to.
> I still consider the decision of using bsr/ret [3] inside pge as being
> wrong or at least premature [4], but that's another point.
If it would help for me to give more details about the bsr/ret scheme
I'm using, I'll be glad to post it. I could certainly give a Perl 6
equivalent of the rule we're looking at. But essentially the key is
that a "bsr" always represents a backtracking point, a "ret" always
indicates fail, a "goto R*" is a tailcall, and the named registers
are variables in the scope of all of the R* subroutines.
Pm
Nicholas Clark
> If it would help for me to give more details about the bsr/ret scheme
> I'm using, I'll be glad to post it. I could certainly give a Perl 6
> equivalent of the rule we're looking at. But essentially the key is
> that a "bsr" always represents a backtracking point, a "ret" always
> indicates fail, a "goto R*" is a tailcall, and the named registers
> are variables in the scope of all of the R* subroutines.
Does this mean that you're using the same recursive approach that the perl 5
regular expression engine uses? (Not that I understand much of the perl 5
engine, except that uses recursion to maintain parts of state)
Nicholas Clark
Leopold Toetsch
> I suspect it's an issue with register spilling, that I15 is being
> reused somewhere later to represent something other than the "cutting"
> value.
Please not that this has nothing to do with register spilling, where due
to a lack of registers these are stored into (and fetched from) an array
in P31. We've got a problem of a register changing it's value - or not.
After another half of a day with gdb, I've eventually tracked it down.
What happens is this: the pattern is "<ident>", which happens to be just
another Rule. So during matching the precompiled coroutine for matching
"<ident>" is entered to try this rule at various positions. But the
relevant code piece in EVAL_1 [1] looks like this:
lastpos = length target
if pos >= 0 goto try_at_pos
pos = 0
try_match:
cutting = 0
...
try_at_pos:
...
if cutting != 0 goto fail <<<< bails out at first
"pos" is already 1, therefore "cutting" get's never initialized and has
some garbage value. I've a rather lengthy typescript here, which tracks
all changes to I15 and clearly shows this reason.
I don't think that Parrot should guarantee that registers have some
predifined value on entering a subroutine. We have to NULL out PMC and
STRING registers already for GC, which is a rather costy operation.
But if folks prefer that we should clean registers, we can of course do
it. It's probably not the best idea though (for the long run and
performance-wise).
An alternative would be to fill integer and number registers with some
arbitrary and changing values (in debug builds) to simplify catching
such errors. There is further some (disabled) code in imcc/cfg.c that
tries to catch such uninitialized variables but I doubt that it would
have warned in that case, as there is one possible execution path to
initialize "cutting".
leo
[1] parrot -D20 foo.pir
creates EVAL_n (n = 1...) for each "evaled" code piece in turn. So
EVAL_1 is the precompiled "ident" rule, EVAL_2 the code for matching the
test file pattern.
Patrick R. Michaud
> Please not that this has nothing to do with register spilling, where due
> to a lack of registers these are stored into (and fetched from) an array
> in P31. We've got a problem of a register changing it's value - or not.
Noted, and thanks for the clarification.
> After another half of a day with gdb, I've eventually tracked it down.
> [...]
> lastpos = length target
> if pos >= 0 goto try_at_pos
> pos = 0
> try_match:
> cutting = 0
> ...
> try_at_pos:
> ...
> if cutting != 0 goto fail <<<< bails out at first
>
> "pos" is already 1, therefore "cutting" get's never initialized and has
> some garbage value.
You're absolutely correct, and many thanks for the work in catching
this. Originally the "cutting = 0" initializer was at the top
of the routine, but apparently when I added the try_match loop
I didn't move it to outside of the loop.
> I don't think that Parrot should guarantee that registers have some
> predifined value on entering a subroutine.
I fully agree.
Again, thanks for the effort in tracking this down. Now fixed in r8484.
Pm
Patrick R. Michaud
Well, I don't know if I'm using the "same" recursive approach that
perl 5 uses, but yes PGE uses a subroutine call chain to maintain
certain parts of its backtracking status. The only recursive call is for
quantified group expressions of various sorts -- subpatterns and
subrules. Outside of that, it's just a linear chain of subroutine
calls (no recursion), and even then subroutine calls are only invoked
where some sort of range quantification is needed to keep backtracking
points. And the subroutine calls used are of the bsr/ret variety,
as opposed to using the continuation passing style calls.
For example, an expression like:
/^ab c**{3} \d+ xyz$/
will have a maximum bsr/ret call depth of 1, to handle the \d+.
Something like:
/^(abc)**{3} xyz$/
will have a maximum bsr/ret call depth of 4, to handle the
quantification of the group and match object. (Groups require an
extra initial bsr call to initialize the group.)
And something like
/^( [abc | def]**{3} )* xyz$/
can end up with a lot of bsr/rets because of the nested and quantified
groups.
I certainly won't claim this is the best way to do it, but for the
time being it seemed easier and more straightforward to just use bsr/ret
to maintain state than to build a separate chain to avoid using the
execution stack. Each pattern gets its own Coroutine and its own
copy of the stacks anyway, and the option to take an entirely different
approach is still available to us if/when we need it -- we'll just
change the codegen. (We can even have/use multiple codegen algorithms
and let an optimizer pick the best one.)
Pm
Nicholas Clark
> On Fri, Jul 01, 2005 at 08:38:01AM +0100, Nicholas Clark wrote:
> > Does this mean that you're using the same recursive approach that the perl 5
> > regular expression engine uses? (Not that I understand much of the perl 5
> > engine, except that uses recursion to maintain parts of state)
>
> Well, I don't know if I'm using the "same" recursive approach that
> perl 5 uses, but yes PGE uses a subroutine call chain to maintain
> certain parts of its backtracking status. The only recursive call is for
> quantified group expressions of various sorts -- subpatterns and
> subrules. Outside of that, it's just a linear chain of subroutine
Does that include simple quantifiers such as * and + ?
> I certainly won't claim this is the best way to do it, but for the
> time being it seemed easier and more straightforward to just use bsr/ret
> to maintain state than to build a separate chain to avoid using the
> execution stack. Each pattern gets its own Coroutine and its own
It's just that I'm wondering whether you're going the same way as the Perl 5
regexp engine and hence the current implementation will share its biggest
weakness - repetitive matches against long strings blowing the stack.
Nicholas Clark
Larry Wall
: regular expression engine uses? (Not that I understand much of the perl 5
: engine, except that uses recursion to maintain parts of state)
No, Perl 5 has to use recursion to emulate co-routines. Parrot has
real co-routines/continuations, so PGE can actually return at the end
of a submatch where P5 has to recurse, since P5 can only represent
failure by a return. So I think PGE's recursion is much more faithful
to the shape of the problem.
Larry
Patrick R. Michaud
> On Fri, Jul 01, 2005 at 11:11:01AM -0500, Patrick R. Michaud wrote:
> > On Fri, Jul 01, 2005 at 08:38:01AM +0100, Nicholas Clark wrote:
>
> > > Does this mean that you're using the same recursive approach that the perl 5
> > > regular expression engine uses? (Not that I understand much of the perl 5
> > > engine, except that uses recursion to maintain parts of state)
> >
> > Well, I don't know if I'm using the "same" recursive approach that
> > perl 5 uses, but yes PGE uses a subroutine call chain to maintain
> > certain parts of its backtracking status. The only recursive call is for
> > quantified group expressions of various sorts -- subpatterns and
> > subrules. Outside of that, it's just a linear chain of subroutine
>
> Does that include simple quantifiers such as * and + ?
The thing that causes recursion is quantified groups; a quantifier
on a simple atom won't do it on its own. For example, the
pattern / a* \d+ / will never cause recursion, regardless of the
number of a's or digits encountered. There will be at most two bsr's.
However, the pattern / (a)* (\d)+ / will have some recursion in it
depending on the input string, because of the need to generate
and destroy the intervening match objects for each captured 'a' and
digit. We may be able to eventually optimize simple cases like
this to be a bit smarter about how it manages the call stack, but
in the general case (with potentially nested and quantified
subpatterns and rules) I think we pretty much need to have the stack
around.
> It's just that I'm wondering whether you're going the same way as the Perl 5
> regexp engine and hence the current implementation will share its biggest
> weakness - repetitive matches against long strings blowing the stack.
Well, since each rule invocation ends up with its own stack
(it's a Coroutine), I'm hoping this won't be a big issue. But if
it does turn out to be one, I think we'll find a way to deal with
it then. :-)
Pm
Larry Wall
: Well, since each rule invocation ends up with its own stack
: it does turn out to be one, I think we'll find a way to deal with
: it then. :-)
Well, for simple subpatterns you can compress it somewhat if you
have a foolproof way of reconstructing prior states from fail states,
so that you don't have to keep actual states around, but maybe just
a range of possible states. But the simple fact is that you have to
keep the backtracking info *somewhere*, or you can't backtrack. The
only practical solution is finding some way to cut out unreachable
states, and that's hard in the absence of explicit user guidance.
All that being said, heaps are easier to share than stacks--though
my vague recollection is that Parrot stacks are really in the heap,
so maybe that particular subproblem is already dealt with.
Larry