Re: [DynInst_API:] nondeterministic loop tree results with irreducible loops

[Xiaozhu Meng <xmeng@xxxxxxxxxxx>]

Hi Mark,

It will be helpful if you can share me this amg2006 binary and show me the two different loop trees. I looked at the loop code again, but it was not clear to me which part of the implementation caused such nondeterministic behavior. So, having access to the binary will be extremely helpful.

Thanks,

--Xiaozhu

On Wed, Mar 21, 2018 at 12:18 AM, Mark W. Krentel <krentel@xxxxxxxx> wrote:

Xiaozhu,

I asked you before about making the loop analysis (and thus hpcstruct)
more deterministic. You suggested a short patch to sort the outedges
of a basic block.

I tried the patch, both in 9.3.2 and in master, and I'm still getting
nondeterministic results in the loop trees.

The fundamental problem is with irreducible loops. AFAIK, if there
are no irreducible loops, then everything is deterministic. But
somewhere in constructing the loop tree, when you're confronted with
an irreducible loop, you have to make a choice for how to break the
loop. It's that choice that leads to the nondeterministic results.

For example, on one amg2006 binary, I see one loop tree that comes out
in two fundamentally different ways. One way has a tree of two nested
loops, the outer is irreducible and the inner is reducible. The other
way has a tower of three nested loops, the outer two are irreducible
(the inner reducible loop is always the same).

We were wondering if there was an easy way to make a deterministic
choice for how to break an irreducible loop.

I don't have a unit test for this. But I can run hpcstruct with
debugging turned on and it's pretty clear what the two trees are.
I can show you the binary and the relevant parts of the debugging
output.

Thanks,

--Mark

_______________________________________________
Dyninst-api mailing list
Dyninst-api@xxxxxxxxxxx
https://lists.cs.wisc.edu/mailman/listinfo/dyninst-api