Subject: bug#12883: [2.0.6] CSE bug

From: Stefan Israelsson Tampe <[email-masked]>
Date: Wed, 21 Nov 2012 15:32:16 +0100

> I think this sentence is ungrammatical, or at least I’m lost.

eh, sorry, but consider the db as
h,db-len

e1 <- m = 0
e2
e3
e4
e5
e6 <- h*
e7

then db-len is 7 and db-len* is 2 and db-len - deb-len* = 5
which is the number of steps to go from e2 to e6, e.g.
we will scan through the list from m = 0 ro h* and verify that we do not
enter
an element that is not commutative for the expression at hand.  This is the
logic of before, but if m = k at e1 and db-len = 7 + k, and db-len* is
again 2
we must use db-len - fb-len* - k to get the right number of iterations to
go from m to h*, so you see as we try consecutive h* in the search we will
scan for violations of the commutativity in batches covering the whole path
from m=0 to the found h* = h. Because m was missing in the calculation of
the number of iteration to many iterations was done and generally this
could mean that optimizations opportunities was lost or that we hit the end
of the list and the error as you noticed was triggered.

please apply the patch and enter a suitable docstring for the commit.

A suggestion for test code is to design cases where various code fragment
that hinders the commutation is placed and one verify that no error will
result for missing in the commutativity check. To verify that it optimizes
is more difficult to do in a test-case. I could help to try design a few of
these testcases, also making sure all test passes after patching the code
is also still needed (of cause).

On Tue, Nov 20, 2012 at 9:16 PM, Ludovic Courtès <[email-masked]> wrote:

> Hi Stefan!
>
> Thanks for your message!
>
> Stefan Israelsson Tampe <[email-masked]> skribis:
>
> > The intention of unroll is to scan db to check that a commutative
> > property for an item going into the function holds for all elements in
> > db up to h==h* is found.
>
> I think this sentence is ungrammatical, or at least I’m lost.
>
> The comments in cse.scm convey the big picture, but I miss the
> connection between that and the actual code.
>
> > Now at each symbol db-len* is the length of db when created so (-
> > db-len db-len*) is the length of all elements in db created after the
> > symbol name.  now db-len* will in the loop lp be decreasing so this
> > length is increasing and the base = m is the position in db where we
> > scan to last time, the fix was to make sure we scan up to the db-len*
> > 'index' e.g. niter had to be corrected by the base m.  Otherwise we
> > could scan out of the length of db* and the error we saw was
> > introduced. Another fix is for unroll to return #t if the length is
> > out of the db length but this is probably a bandage, not the bug, the
> > bug is most probably fixed by this patch.
> >
> > Is things more clear now?
>
> From a pure boundary analysis viewpoint, it’s a somewhat clearer.
>
> Should I apply the patch, or did you want to prepare another one?
>
> I tried further reducing the test case, and synthesizing the new one,
> but the little understanding I have of this code doesn’t allow me to do
> the latter.  Any help would be welcome.
>
> Thanks!
>
> Ludo’.
>