Possible bug calculating dominators

0 views
Skip to first unread message

Curtis Rawls

unread,
Jul 5, 2005, 2:50:44 AM7/5/05
to Perl 6 Internals
I seem to have come across a bug in the compute_dominators() algorithm
with the following PIR:

.sub _main
L1:
eq I0, 0, L3
L2:
goto L5
L3:
L4:
L5:
goto L7
L6:
inc I0
L7:
le I0, 0, L6
end
.end

Running with:
$ ./parrot/parrot -d 32 testbug.pir

I get "7 <- 0 1 2 5 7" for the dominators, which should instead be "7
<- 0 1 5 7" (no 2). Blocks 6 and 8 also incorrectly include block 2
in their dominator set.

Can anyone confirm that this is incorrect behavior? And possibly
suggest a fix or explanation? Thanks,

-Curtis

Leopold Toetsch

unread,
Jul 5, 2005, 12:53:11 PM7/5/05
to Curtis Rawls, Perl 6 Internals

On Jul 5, 2005, at 8:50, Curtis Rawls wrote:

>
> I seem to have come across a bug in the compute_dominators() algorithm
> with the following PIR:

It's not unlikely that there are bugs in that part of imcc. It was
contributed by Angel Faus, who seems to be not participating in Parrot
dev anymore. Some times ago, I was pondering some tests for CFG-related
items, but no one (including me) seems to have the tuits to attack it.

> -Curtis

leo

Curtis Rawls

unread,
Jul 12, 2005, 4:09:08 AM7/12/05
to Leopold Toetsch, Perl 6 Internals

Yes, I'm running into a lot of areas of the CFG/optimizer that I would
like to modify, and some CFG tests would be great to help avoid
introducing new bugs. Basically just checking the cfg and dominator
dump outputs for correctness. I have looked at the tests in t/ and
imcc/t/, but have not found a way to test the compiler debug output.
Any suggestions?

Also, I am working on some new (and hopefully more correct)
implementations of some of the CFG algorithms, such as
compute_dominators(). I would appreciate having someone to run these
by. Any takers?

-Curtis

Reply all
Reply to author
Forward
0 new messages