Page MenuHomePhabricator

[SCEV] Compute exit count from overflow test
Changes PlannedPublic

Authored by reames on Jul 10 2019, 9:57 AM.

Details

Summary

If we have an exit test in a loop which is controlled by the overflow flag on an add.with.overflow intrinsic, we can possible compute which iteration would cause overflow. Knowing an exit count for the loop, then drives LFTR which is then able to rewrite the check in the form which eliminates the need for the overflow check entirely.

(Noticed while looking at the output of the PoisonChecking tool, but unrelated.)

Diff Detail

Event Timeline

reames created this revision.Jul 10 2019, 9:57 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 10 2019, 9:57 AM

Thanks very much for doing this, this is exactly what I want to do as a follow-up patch for https://reviews.llvm.org/D64422.

This patch looks most good to me except one PowerPC test case.

With this patch, we can get loop exit for more loops, so we get also get more hardware loops in HardwareLoops pass.
As I tested, one PowerPC FIXME test (main1) llvm/test/CodeGen/PowerPC/negctr.ll fails if accept this patch. Not sure why this is not showed in your patch. Could you help to have a look? Thanks.

llc < test/CodeGen/PowerPC/negctr.ll -mcpu=a2 -verify-machineinstrs | FileCheck test/CodeGen/PowerPC/negctr.ll
nikic added inline comments.Jul 11 2019, 1:56 PM
lib/Analysis/ScalarEvolution.cpp
7308

It's not wrong, but unnecessarily restrictive and a bit confusing to do the isKnownPositive check for an unsigned addition.

It might make sense to handle the negative stride case right away with a code structure like this:

const SCEV *MaxValue = nullptr, *MinValue = nullptr;
if (WO->getBinaryOp() == Instruction::Add) {
  if (!Signed)
    MaxValue = getMinusSCEV(
        getConstant(APInt::getNullValue(BitWidth)), RHSSCEV);
  else if (isKnownPositive(RHSSCEV))
    MaxValue = getMinusSCEV(
        getConstant(APInt::getSignedMinValue(BitWidth)), RHSSCEV);
  else if (isKnownNegative(RHSSCEV))
    MinValue = getAddExpr(
        getConstant(APInt::getSignedMaxValue(BitWidth)), RHSSCEV);
}
if (MaxValue) { ... howManyLessThans ... }
else if (MinValue) { ... howManyGreaterThans ... }

This should make it easy to extend to Sub as well.

7316

nit: Stray semicolon.

reames planned changes to this revision.Jul 30 2019, 11:25 AM

Just indicating in the review state that the next action item here is mine. Probably not going to get back to this for a bit, so want that to be clear to reviewers.

Just indicating in the review state that the next action item here is mine. Probably not going to get back to this for a bit, so want that to be clear to reviewers.

@nikic ping?