Re: [perl #36597] [PATCH]Dominance Frontiers

0 views
Skip to first unread message

Curtis Rawls

unread,
Jul 28, 2005, 12:53:07 PM7/28/05
to perl6-i...@perl.org
Can someone apply this? I have another patch ready that depends on this one.
Thanks!
-Curtis

On 7/19/05, via RT Curtis Rawls <parrotbug...@parrotcode.org> wrote:
> # New Ticket Created by Curtis Rawls
> # Please include the string: [perl #36597]
> # in the subject line of all future correspondence about this issue.
> # <URL: https://rt.perl.org/rt3/Ticket/Display.html?id=36597 >
>
>
> This patch adds support for "dominance frontiers" in imcc, including:
> -Array of Sets for dominance frontiers
> -An efficient algorithm described in "A Simple, Fast Dominance
> Algorithm", Cooper et al. (2001)
> -Free and dump functions
>
> -Curtis
>
>
>

Will Coleda

unread,
Jul 28, 2005, 1:55:12 PM7/28/05
to perl6-i...@perl.org, bugs-bi...@netlabs.develooper.com
FYI, on OS X 10.4.2, I get:

Failed Test Stat Wstat Total Fail Failed List of Failed
------------------------------------------------------------------------
-------
t/p6rules/backtrack.t 1 256 15 1 6.67% 2
t/pmc/eval.t 3 768 14 3 21.43% 12-14
t/pmc/perlstring.t 1 256 68 1 1.47% 61
t/pmc/string.t 1 256 35 1 2.86% 28

I have some slight differences from svn-latest which of course
"shouldn't affect these tests". =-)

On Jul 19, 2005, at 10:39 PM, Curtis Rawls (via RT) wrote:

> # New Ticket Created by Curtis Rawls
> # Please include the string: [perl #36597]
> # in the subject line of all future correspondence about this issue.
> # <URL: https://rt.perl.org/rt3/Ticket/Display.html?id=36597 >
>
>
> This patch adds support for "dominance frontiers" in imcc, including:
> -Array of Sets for dominance frontiers
> -An efficient algorithm described in "A Simple, Fast Dominance
> Algorithm", Cooper et al. (2001)
> -Free and dump functions
>
> -Curtis
>

> <df.patch>
>

Will Coleda

unread,
Jul 28, 2005, 3:12:58 PM7/28/05
to Internals List, bugs-bi...@netlabs.develooper.com
The eval tests are failing with a pristine checkout so we can ignore
those. Applying your patch to a pristine build yields only the
backtrack.t failure: #2 eats 100% of the CPU until I kill it: it
doesn't behave that way in svn-head.

Looks like PerlString and String were red herrings. Should track down
why p6rules is misbehaving with your patch, though.

Regards.

Andy Dougherty

unread,
Jul 28, 2005, 3:39:33 PM7/28/05
to Internals List
On Thu, 28 Jul 2005, Will Coleda wrote:

> Applying your patch to a pristine build yields only the backtrack.t failure:
> #2 eats 100% of the CPU until I kill it: it doesn't behave that way in
> svn-head.

I can confirm the backtrack #2 failure under SPARC/Solaris. I can't say
what other tests may have changed; the script I had running the comparison
got stuck at backtrack.t and never finished.

--
Andy Dougherty doug...@lafayette.edu

Curtis Rawls

unread,
Jul 29, 2005, 2:28:42 AM7/29/05
to perl6-i...@perl.org, Will Coleda
Thanks for pointing this out. I tracked the bug down, and it looks
like the dominator algorithm does not handle unreachable blocks
correctly, and the dominance frontier algorithm suffers for it. Why
the unreachable blocks are generated in the first place might be an
interesting question for someone working on PGE.

I'll work on the dominator bug before applying the DF patch.
-Curtis

Patrick R. Michaud

unread,
Jul 28, 2005, 10:10:32 PM7/28/05
to Andy Dougherty, Internals List

Just to add to the picture -- I also tried applying df.patch to a fresh
checkout of parrot/trunk (r8727), and also observed the same problem
of getting stuck on test #2 in t/p6rules/backtrack.t . (FWIW, I'm running
Fedora Core 4.)

Some additional investigation reveals that with df.patch applied it's
the PIR compiler that is getting stuck. I'm able to reproduce this
with the code below, which doesn't do anything useful other than
demonstrate that the compiler gets stuck when one tries to compile:

$ cat x4.pir
.sub foo
print "started\n"
bsr R1
goto end
R1:
goto R2
if $I0 goto R2
bsr R2
R2:
ret
end:
.end

$ parrot -t -v -o x4.pbc x4.pir
debug = 0x0
Reading x4.pir
using optimization '0' (0)
Starting parse...

at which point the process is stuck until interrupted somehow.

The problem seems to be with the exact goto/if/bsr sequence given in R1 --
remove any of them or reorder them and the code successfully compiles.

I completely grant that the specific sequence of statements that
trigger this problem is bizarre -- it only occurred in PGE because
of a missing optimization in PGE's code generator. The cut operator
(for backtracking control) generated a "goto R2" statement to
handle the cut, but then also generated the code that would've
performed the backtracking had the cut not been present. Note that
having the extra code after the goto doesn't change the syntactic
or semantic correctness at all -- it just causes the compiler to choke
somehow (when df.patch is applied).

I'll definitely fix PGE to not generate the unnecessary code
following the "goto", but it seems to me that the compiler should
not hang on something like this in any case.

I'll be very happy to add the above PIR segment to the imcc test
suite if someone can tell me which imcc/t/*/*.t file it should go in.
Then I'll fix PGE to not generate the code it should not have
been generating in the first place. :-)

Hope this helps!

Pm

Leopold Toetsch

unread,
Jul 29, 2005, 6:54:50 AM7/29/05
to Patrick R. Michaud, Andy Dougherty, Internals List
Patrick R. Michaud wrote:
>

> ... I'm able to reproduce this
> with the code below

Good catch.

> I'll be very happy to add the above PIR segment to the imcc test
> suite if someone can tell me which imcc/t/*/*.t file it should go in.

Probably time to start a new subdir:

imcc/t/cfg/df.t

or some such.

> Pm

leo

Curtis Rawls

unread,
Aug 9, 2005, 2:54:42 PM8/9/05
to parrotbug...@parrotcode.org
Can you check on the status of my commit access? I tried committing
today, and got this error:

$ svn commit --file ../logmsg
<snip>
Authentication realm: <https://svn.perl.org:443> perl.org
Username: cgrawls
Password for 'cgrawls':
svn: Commit failed (details follow):
svn: MKACTIVITY of
/parrot/!svn/act/d66942a2-ebfd-0310-9e04-e131c6e806bb: authorization
failed (https://svn.perl.org)

Thanks,
-Curtis

On 7/29/05, Leopold Toetsch via RT <parrotbug...@parrotcode.org> wrote:
> Hi Robert,
>
> please enable svn ci for Curtis (another google summer of code student)
> for the parrot tree.
> > username: cgrawls
>
> TIA,
> leo
>
> Begin forwarded message:
>
> > From: Curtis Rawls <cgr...@gmail.com>
> > Date: July 29, 2005 0:45:56 CEST
> > To: Leopold Toetsch <l...@toetsch.at>
> > Subject: Re: [perl #36597] [PATCH]Dominance Frontiers
> > Reply-To: Curtis Rawls <cgr...@gmail.com>
> >
> >
> > username: cgrawls
> > email: cgr...@gmail.com
> >
> > Thanks!
> > -Curtis
> >
> > On 7/28/05, Leopold Toetsch <l...@toetsch.at> wrote:


> >>
> >> On Jul 28, 2005, at 18:53, Curtis Rawls wrote:
> >>
> >>>
> >>> Can someone apply this? I have another patch ready that depends on
> >>> this one.
> >>> Thanks!
> >>

> >> Please send me you auth.perl account name, I'll forward it with
> >> approval to Robert, so that you get ci privs for parrot (if ypu want
> >> of
> >> course :-)
> >>
> >> leo
> >>
> >>
>
>
>

Curtis Rawls

unread,
Aug 10, 2005, 9:25:03 PM8/10/05
to perl6-i...@perl.org, Will Coleda
I have attached a patch that fixes this problem.

Description:
-----
This patch adds a bb_remove_edge() function, and decouples unreachable blocks
from the CFG by removing their successor edges.
-----

I think this is the best way to handle unreachable blocks in the CFG,
other than removing them, which is an -O1 optimization.

I still don't have commit access, so someone else can apply it now, or
I will apply it once I do, if there are no complaints.
-Curtis

Leopold Toetsch

unread,
Aug 11, 2005, 7:28:45 AM8/11/05
to Curtis Rawls, perl6-i...@perl.org, Will Coleda
Curtis Rawls wrote:

>>This patch adds a bb_remove_edge() function, and decouples unreachable blocks
>>from the CFG by removing their successor edges.

Thanks, applied - r8913

leo

Reply all
Reply to author
Forward
0 new messages