This is an archive of the discontinued LLVM Phabricator instance.

[ConstantFold] Fix defect in constant folding computation for GEP
ClosedPublic

Authored by javed.absar on Mar 6 2017, 4:14 AM.

Details

Summary

When the array indexes are all determined by GVN to be constants,
a call is made to constant-folding to optimize/simplify the address
computation.
The constant-folding, however, makes a mistake in that it sometimes reads
back stale Idxs instead of NewIdxs, that it re-computed in previous iteration.
This leads to incorrect addresses coming out of constant-folding to GEP.

A test case is included. The error is only triggered when indexes have particular
patterns that the stale/new index updates interplay matters.

Diff Detail

Event Timeline

javed.absar created this revision.Mar 6 2017, 4:14 AM

Is there a reason to split NewIdx and Idx at all?
I don't see it in this code and context.

That would solve your problem without introducing yet another array.
It also would be a step on fixing the N^2'dness of this function (since it restarts itself on the changed indices, which is silly)

Yes makes sense if it can be done without breaking some corner case. I will wait a bit for the original author of this algorithm, who I believe are on the review-list, to comment on why originally two arrays, Idxs and NewIdxs, was thought best to have.
Best Regards
Javed

javed.absar updated this revision to Diff 90985.Mar 8 2017, 1:23 AM

Hi:
Here is a simpler fix for that same defect.

On the point of removing NewIdxs completely, I did give it a try, but then found (a) Idxs is passed as constant reference and so it is not a good idea to modify it; (b) the algorithm is not really N^2 as the indexes are re-computed only once.

Hope this patch with the fix for that specific original problem (stale data reading) is acceptable.
Best Regards
Javed

Hi:
Here is a simpler fix for that same defect.

On the point of removing NewIdxs completely, I did give it a try, but then found (a) Idxs is passed as constant reference and so it is not a good idea to modify it;

Ugh. Unless this code is going to do a thing to them that is bad, that seems silly, but ...
yeah, not gonna make you fix it.

(b) the algorithm is not really N^2 as the indexes are re-computed only once.

Once per GEP in the tree, you mean

// If we did any factoring, start over with the adjusted indices.
if (!NewIdxs.empty()) {
  for (unsigned i = 0, e = Idxs.size(); i != e; ++i)
    if (!NewIdxs[i]) NewIdxs[i] = cast<Constant>(Idxs[i]);
  return ConstantExpr::getGetElementPtr(PointeeTy, C, NewIdxs, InBounds,
                                        InRangeIndex);

This will call this function, and that call could also adjust and recurse.
all the way up the tree.

So if you constant folded a gep tree like this:

1=GEP 0
2=GEP 1
3=GEP 2
..

Imagine constant folding only fails at the last second for some reason:

calling constant fold on 1 will call it on 0
calling constant fold on 2 will call it on 1 which will call it on 0
calling constant fold on 3 will call it on 2 which will call it on 1 which will call it on 0.

So yes, the function itself is not N^2, but pretty much any normal usage will be.

Hope this patch with the fix for that specific original problem (stale data reading) is acceptable.
Best Regards
Javed

Hi Daniel:

Agree with you that the ConstantFolding algorithm seems to need improvement. I will try to improve it and send you a new patch.
But I also think this defect fix need not be gated on it.

Best Regards
Javed

dberlin accepted this revision.Mar 8 2017, 7:30 AM

Hi Daniel:

Agree with you that the ConstantFolding algorithm seems to need improvement. I will try to improve it and send you a new patch.
But I also think this defect fix need not be gated on it.

Sorry, thought i already accepted this.
I was just responding to your comment that it only does things once :)

This revision is now accepted and ready to land.Mar 8 2017, 7:30 AM
This revision was automatically updated to reflect the committed changes.