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

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

Xiaozhu,

I was able to adapt your patch on the overlapping instructions to our
build system.  (There was one tiny issue over ah.retreat() versus
ah->retreat(), but that was easy.)

Now, I don't see any more non-determinism in our hpcstruct answer on
x86.  I've run it a bunch of times on the hpcstruct and amg2006
binaries and I always get identical answers.

But if you're interested in a deeper answer, I still see some
non-determinism in two cases.

(1) Although the hpcstruct answer is consistent, when I turn on my
internal debugging output, I see different ordering in it.  This would
be things like, print all inclusive or exclusive blocks of some loop
or function.  I dump these in whatever order I get them from parseapi,
and they often come back in different orders.

I think what's happening is that you're constructing a deterministic
tree, but traversing it in malloc order.  So, I'll get the same set of
blocks, just in a different order.  Something like that.

The reason hpcstruct produces a deterministic answer is that I take
all the blocks and statements and put them into a map by vma and that
normalizes the order.

Anyway, this is not really serious, don't worry about it.  I just
though you might like to know.

(2) I still get non-deterministic answers on powerpc.  And I'm
guessing the overlapping instructions patch is a no-op on powerpc
since powerpc shouldn't have overlapping instructions.

These seem to happen for a different reason.  On x86, it was
irreducible loops coming from misinterpreting instructions.  On
powerpc, it seems related to inline sequences.

But I'm not sure if the non-determinism is coming from your side or
mine.  That is, I'm not sure if my code normalizes the order of
side-by-side inline sequences or not.  (Plus, my directory is a bit of
a franken-build right now, so I'm not 100% sure if there is a problem
at all.)

Anyway, don't worry about this one either.  For one thing, when we
start running parallel analysis, then there will certainly be ordering
differences.

Thanks!  And make sure this fix finds its way into master.

--Mark




On 03/22/18 12:23, Xiaozhu Meng wrote:
> Hi Mark,
>
> It turned out that this was not a loop problem. There are overlapping 
> instructions in this function and ParseAPI was not correctly aligning 
> these overlapping blocks, causing weird and nondeterministic block 
> boundaries. You can get my fix at 
> https://github.com/mxz297/dyninst/tree/powerpc_and_loop. I was also 
> running Dyninst testsuite on powerpc and doing fixes. So I bundled 
> those fixes, which is not an ideal practice... Anyway, right now, on 
> my side, the problematic function now has two natural loops, and no 
> irreducible loops. Let me know if such nice loops are actually wrong...
> Thank,
>
> --Xiaozhu