[DynInst_API:] nondeterministic loop tree results with irreducible loops

["Mark W. Krentel" <krentel@xxxxxxxx>]

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