Page MenuHomePhabricator

[LVI] Teach LVI to see through x.with.overflow calls
Needs RevisionPublic

Authored by regehr on May 3 2016, 7:11 AM.

Details

Reviewers
reames
nikic
Summary

If we're going to use LVI as a remover for overflow checks, then it should be able to see through calls to x.with.overflow intrinsics. This patch does that.

I'm not too happy with the code copied from solveBlockValueBinaryOp() and would be happy for suggestions for how to factor this better.

Diff Detail

Event Timeline

regehr updated this revision to Diff 55990.May 3 2016, 7:11 AM
regehr retitled this revision from to [LVI] Teach LVI to see through x.with.overflow calls.
regehr updated this object.
regehr added a reviewer: reames.
regehr set the repository for this revision to rL LLVM.
reames added inline comments.May 5 2016, 6:49 PM
lib/Analysis/LazyValueInfo.cpp
654

minor: place this below the PHI and select handling please. Those two are mildly special in the current structure. Also, this should be below the pointer bail.

824

Prefer early exit please.

826

I think this should be:
if (EV->getNumIndices() != 1 && *EV->idx_begin() != 0)

832

Hm, semantics question. Is the first value of sadd.with.overflow result well defined if the second is true? (i.e. overflow did occur?)

I had thought the answer to this was "no". I suspect you're trying to use the result of this to prove the no-overflow on the intrinsic via CVP and I'm not sure that's safe.

874

You can separate out this bit into a helper of the form:
CR transfer(OpCode, CR, CR)

and share it with the current binaryoperator handling.

reames requested changes to this revision.May 5 2016, 6:49 PM
reames edited edge metadata.
This revision now requires changes to proceed.May 5 2016, 6:49 PM
regehr added inline comments.May 8 2016, 1:17 PM
lib/Analysis/LazyValueInfo.cpp
832

My read of the langref is that the first and second values are independently valid, but I'll double-check on the mailing list.

regehr added inline comments.May 8 2016, 1:59 PM
lib/Analysis/LazyValueInfo.cpp
874

Just to be clear-- do the intrinsicIDs and regular opcodes live in different parts of the namespace? Can I safely mix them in a switch? I had been wondering about this but didn't find the thing I wanted to know in the documentation.

regehr updated this revision to Diff 56614.May 9 2016, 12:58 PM
regehr edited edge metadata.
regehr removed rL LLVM as the repository for this revision.
regehr marked 7 inline comments as done.

Address Philip's feedback and rebase. Thanks for the comments!

regehr added a comment.EditedMay 11 2016, 4:39 AM

I have a small, well-defined program that gets compiled into a crash by clang -O2 -fsanitize=signed-integer-overflow -fsanitize-trap=signed-integer-overflow. So either there's a bug in this patch or else teaching LLVM to see through overflow intrinsics is exposing a bug elsewhere. I'll narrow it down.

This is the program.

int a;
int fn1(p1) { return 1 - p1 + 1; }
int main() {
  int b = 0;
  if (fn1(0))
    a = b = 1;
  fn1(b);
  return 0;
}
regehr edited edge metadata.May 11 2016, 6:26 AM
regehr set the repository for this revision to rL LLVM.
regehr updated this revision to Diff 56898.May 11 2016, 6:29 AM

Oops-- instead of

(EV->getNumIndices() != 1 && *EV->idx_begin() != 0)

we wanted

(EV->getNumIndices() != 1 || *EV->idx_begin() != 0)

luckily Csmith caught this since I didn't.

regehr updated this revision to Diff 58763.May 27 2016, 2:38 AM
regehr removed rL LLVM as the repository for this revision.

rebase and bump

reames requested changes to this revision.Oct 7 2016, 3:27 PM
reames edited edge metadata.

Sorry for letting this lie for so long. If you separate out the two helper functions and rebase, I think this is very close to going in. You can land the refactorings suggested without further review for them.

lib/Analysis/LazyValueInfo.cpp
681

Please update with full context.

819

Separating out this transfer function is a useful cleanup for the code as is. Please separate, commit, then rebase. (LGTM for that only)

864

Shifting this below the next check would make the code easier to read (at least for me) as it groups related checks.

874

I believe there are different namespaces.

891

extracting out a helper function getRangeForOperand(...) would greatly simplify this code.

894

The patch needs rebased.

This revision now requires changes to proceed.Oct 7 2016, 3:27 PM
lebedev.ri added a subscriber: lebedev.ri.

@regehr reverse-ping? :)

I briefly thought so too, but the tests here still don't get folded: https://godbolt.org/z/AvKbzY
So this is still applicable in some capacity.

nikic added a comment.Aug 31 2019, 1:17 AM

@lebedev.ri Thanks! The problem here is that for these test cases CVP will convert the with.overflow intrinsic to a simple add/sub/mul together with insertvalue instructions. LVI can't see through extractvalue of insertvalue, which is why the followup optimization on the condition does not trigger (it would only happen on the next run). I'll look into fixing this.