This is an archive of the discontinued LLVM Phabricator instance.

Differential D7338

Allow ScalarEvolution to catch more min/max cases
ClosedPublic

Authored by jdoerfert on Feb 2 2015, 5:17 AM.

Details

Reviewers
atrick
sunfish
bkramer
Summary
For the test case attached different types are used in the ICmpInst
and SelectInst that represent the min/max expressions. However, if the
ICmpInst type is smaller a comparison with the sign/zero extended
operands would have yielded the same result. This situation might arise after
the instruction combination pass was applied.

Diff Detail

Event Timeline

jdoerfert updated this revision to Diff 19144.Feb 2 2015, 5:17 AM
jdoerfert retitled this revision from to Allow ScalarEvolution to catch more min/max cases.
jdoerfert updated this object.
jdoerfert added reviewers: sunfish, atrick, bkramer.
jdoerfert added a subscriber: Unknown Object (MLST).
nicholas added a subscriber: nicholas.Feb 4 2015, 1:00 AM

The logic here looks pretty obviously correct. I am confused about the
whitespace though. This looks right:

+ if (getTypeSizeInBits(LHS->getType()) <=
+ getTypeSizeInBits(U->getType())) {

but these do not:

+ if (getTypeSizeInBits(LHS->getType()) <=
+ getTypeSizeInBits(U->getType()) &&

...

+ if (getTypeSizeInBits(LHS->getType()) <=
+ getTypeSizeInBits(U->getType()) &&

Consider clang-format'ing and then commit.

Johannes Doerfert wrote:

Hi sunfish, atrick, bkramer,

For the test case attached different types are used in the ICmpInst
and SelectInst that represent the min/max expressions. However, if the
ICmpInst type is smaller a comparison with the sign/zero extended
operands would have yielded the same result. This situation might arise after
the instruction combination pass was applied.

http://reviews.llvm.org/D7338

Files:

lib/Analysis/ScalarEvolution.cpp
test/Analysis/ScalarEvolution/min-max-exprs.ll

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

atrick accepted this revision.Feb 6 2015, 5:05 PM
atrick edited edge metadata.

LGTM

This revision is now accepted and ready to land.Feb 6 2015, 5:05 PM
jdoerfert added a comment.Feb 9 2015, 4:44 AM

Commited in r228571.

jdoerfert closed this revision.Feb 11 2015, 6:35 AM

Revision Contents

PathSize
lib/
Analysis/
48 lines
test/
Analysis/
ScalarEvolution/
53 lines

Diff 19144

lib/Analysis/ScalarEvolution.cpp

  • This file is larger than 256 KB, so syntax highlighting is disabled by default.
Show First 20 Lines • Show All 4,274 Lines • ▼ Show 20 Lines if (ICmpInst *ICI = dyn_cast<ICmpInst>(U->getOperand(0))) {
case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_SLT:
case ICmpInst::ICMP_SLE: case ICmpInst::ICMP_SLE:
std::swap(LHS, RHS); std::swap(LHS, RHS);
// fall through // fall through
case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_SGT:
case ICmpInst::ICMP_SGE: case ICmpInst::ICMP_SGE:
// a >s b ? a+x : b+x -> smax(a, b)+x // a >s b ? a+x : b+x -> smax(a, b)+x
// a >s b ? b+x : a+x -> smin(a, b)+x // a >s b ? b+x : a+x -> smin(a, b)+x
if (LHS->getType() == U->getType()) { if (getTypeSizeInBits(LHS->getType()) <=
const SCEV *LS = getSCEV(LHS); getTypeSizeInBits(U->getType())) {
const SCEV *RS = getSCEV(RHS); const SCEV *LS = getNoopOrSignExtend(getSCEV(LHS), U->getType());
const SCEV *RS = getNoopOrSignExtend(getSCEV(RHS), U->getType());
const SCEV *LA = getSCEV(U->getOperand(1)); const SCEV *LA = getSCEV(U->getOperand(1));
const SCEV *RA = getSCEV(U->getOperand(2)); const SCEV *RA = getSCEV(U->getOperand(2));
const SCEV *LDiff = getMinusSCEV(LA, LS); const SCEV *LDiff = getMinusSCEV(LA, LS);
const SCEV *RDiff = getMinusSCEV(RA, RS); const SCEV *RDiff = getMinusSCEV(RA, RS);
if (LDiff == RDiff) if (LDiff == RDiff)
return getAddExpr(getSMaxExpr(LS, RS), LDiff); return getAddExpr(getSMaxExpr(LS, RS), LDiff);
LDiff = getMinusSCEV(LA, RS); LDiff = getMinusSCEV(LA, RS);
RDiff = getMinusSCEV(RA, LS); RDiff = getMinusSCEV(RA, LS);
if (LDiff == RDiff) if (LDiff == RDiff)
return getAddExpr(getSMinExpr(LS, RS), LDiff); return getAddExpr(getSMinExpr(LS, RS), LDiff);
} }
break; break;
case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_ULT:
case ICmpInst::ICMP_ULE: case ICmpInst::ICMP_ULE:
std::swap(LHS, RHS); std::swap(LHS, RHS);
// fall through // fall through
case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_UGT:
case ICmpInst::ICMP_UGE: case ICmpInst::ICMP_UGE:
// a >u b ? a+x : b+x -> umax(a, b)+x // a >u b ? a+x : b+x -> umax(a, b)+x
// a >u b ? b+x : a+x -> umin(a, b)+x // a >u b ? b+x : a+x -> umin(a, b)+x
if (LHS->getType() == U->getType()) { if (getTypeSizeInBits(LHS->getType()) <=
const SCEV *LS = getSCEV(LHS); getTypeSizeInBits(U->getType())) {
const SCEV *RS = getSCEV(RHS); const SCEV *LS = getNoopOrZeroExtend(getSCEV(LHS), U->getType());
const SCEV *RS = getNoopOrZeroExtend(getSCEV(RHS), U->getType());
const SCEV *LA = getSCEV(U->getOperand(1)); const SCEV *LA = getSCEV(U->getOperand(1));
const SCEV *RA = getSCEV(U->getOperand(2)); const SCEV *RA = getSCEV(U->getOperand(2));
const SCEV *LDiff = getMinusSCEV(LA, LS); const SCEV *LDiff = getMinusSCEV(LA, LS);
const SCEV *RDiff = getMinusSCEV(RA, RS); const SCEV *RDiff = getMinusSCEV(RA, RS);
if (LDiff == RDiff) if (LDiff == RDiff)
return getAddExpr(getUMaxExpr(LS, RS), LDiff); return getAddExpr(getUMaxExpr(LS, RS), LDiff);
LDiff = getMinusSCEV(LA, RS); LDiff = getMinusSCEV(LA, RS);
RDiff = getMinusSCEV(RA, LS); RDiff = getMinusSCEV(RA, LS);
if (LDiff == RDiff) if (LDiff == RDiff)
return getAddExpr(getUMinExpr(LS, RS), LDiff); return getAddExpr(getUMinExpr(LS, RS), LDiff);
} }
break; break;
case ICmpInst::ICMP_NE: case ICmpInst::ICMP_NE:
// n != 0 ? n+x : 1+x -> umax(n, 1)+x // n != 0 ? n+x : 1+x -> umax(n, 1)+x
if (LHS->getType() == U->getType() && if (getTypeSizeInBits(LHS->getType()) <=
isa<ConstantInt>(RHS) && getTypeSizeInBits(U->getType()) &&
cast<ConstantInt>(RHS)->isZero()) { isa<ConstantInt>(RHS) && cast<ConstantInt>(RHS)->isZero()) {
const SCEV *One = getConstant(LHS->getType(), 1); const SCEV *One = getConstant(U->getType(), 1);
const SCEV *LS = getSCEV(LHS); const SCEV *LS = getNoopOrZeroExtend(getSCEV(LHS), U->getType());
const SCEV *LA = getSCEV(U->getOperand(1)); const SCEV *LA = getSCEV(U->getOperand(1));
const SCEV *RA = getSCEV(U->getOperand(2)); const SCEV *RA = getSCEV(U->getOperand(2));
const SCEV *LDiff = getMinusSCEV(LA, LS); const SCEV *LDiff = getMinusSCEV(LA, LS);
const SCEV *RDiff = getMinusSCEV(RA, One); const SCEV *RDiff = getMinusSCEV(RA, One);
if (LDiff == RDiff) if (LDiff == RDiff)
return getAddExpr(getUMaxExpr(One, LS), LDiff); return getAddExpr(getUMaxExpr(One, LS), LDiff);
} }
break; break;
case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_EQ:
// n == 0 ? 1+x : n+x -> umax(n, 1)+x // n == 0 ? 1+x : n+x -> umax(n, 1)+x
if (LHS->getType() == U->getType() && if (getTypeSizeInBits(LHS->getType()) <=
isa<ConstantInt>(RHS) && getTypeSizeInBits(U->getType()) &&
cast<ConstantInt>(RHS)->isZero()) { isa<ConstantInt>(RHS) && cast<ConstantInt>(RHS)->isZero()) {
const SCEV *One = getConstant(LHS->getType(), 1); const SCEV *One = getConstant(U->getType(), 1);
const SCEV *LS = getSCEV(LHS); const SCEV *LS = getNoopOrZeroExtend(getSCEV(LHS), U->getType());
const SCEV *LA = getSCEV(U->getOperand(1)); const SCEV *LA = getSCEV(U->getOperand(1));
const SCEV *RA = getSCEV(U->getOperand(2)); const SCEV *RA = getSCEV(U->getOperand(2));
const SCEV *LDiff = getMinusSCEV(LA, One); const SCEV *LDiff = getMinusSCEV(LA, One);
const SCEV *RDiff = getMinusSCEV(RA, LS); const SCEV *RDiff = getMinusSCEV(RA, LS);
if (LDiff == RDiff) if (LDiff == RDiff)
return getAddExpr(getUMaxExpr(One, LS), LDiff); return getAddExpr(getUMaxExpr(One, LS), LDiff);
} }
break; break;
▲ Show 20 Lines • Show All 2,655 Lines • ▼ Show 20 Lines if (IsKnownPredicateFull(ICmpInst::ICMP_UGE, LHS, FoundLHS) &&
IsKnownPredicateFull(ICmpInst::ICMP_ULE, RHS, FoundRHS)) IsKnownPredicateFull(ICmpInst::ICMP_ULE, RHS, FoundRHS))
return true; return true;
break; break;
} }
return false; return false;
} }
// Verify if an linear IV with positive stride can overflow when in a // Verify if an linear IV with positive stride can overflow when in a
// less-than comparison, knowing the invariant term of the comparison, the // less-than comparison, knowing the invariant term of the comparison, the
// stride and the knowledge of NSW/NUW flags on the recurrence. // stride and the knowledge of NSW/NUW flags on the recurrence.
bool ScalarEvolution::doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool ScalarEvolution::doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride,
bool IsSigned, bool NoWrap) { bool IsSigned, bool NoWrap) {
if (NoWrap) return false; if (NoWrap) return false;
unsigned BitWidth = getTypeSizeInBits(RHS->getType()); unsigned BitWidth = getTypeSizeInBits(RHS->getType());
const SCEV *One = getConstant(Stride->getType(), 1); const SCEV *One = getConstant(Stride->getType(), 1);
Show All 11 Linesbool ScalarEvolution::doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride,
APInt MaxValue = APInt::getMaxValue(BitWidth); APInt MaxValue = APInt::getMaxValue(BitWidth);
APInt MaxStrideMinusOne = getUnsignedRange(getMinusSCEV(Stride, One)) APInt MaxStrideMinusOne = getUnsignedRange(getMinusSCEV(Stride, One))
.getUnsignedMax(); .getUnsignedMax();
// UMaxRHS + UMaxStrideMinusOne > UMaxValue => overflow! // UMaxRHS + UMaxStrideMinusOne > UMaxValue => overflow!
return (MaxValue - MaxStrideMinusOne).ult(MaxRHS); return (MaxValue - MaxStrideMinusOne).ult(MaxRHS);
} }
// Verify if an linear IV with negative stride can overflow when in a // Verify if an linear IV with negative stride can overflow when in a
// greater-than comparison, knowing the invariant term of the comparison, // greater-than comparison, knowing the invariant term of the comparison,
// the stride and the knowledge of NSW/NUW flags on the recurrence. // the stride and the knowledge of NSW/NUW flags on the recurrence.
bool ScalarEvolution::doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool ScalarEvolution::doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride,
bool IsSigned, bool NoWrap) { bool IsSigned, bool NoWrap) {
if (NoWrap) return false; if (NoWrap) return false;
unsigned BitWidth = getTypeSizeInBits(RHS->getType()); unsigned BitWidth = getTypeSizeInBits(RHS->getType());
const SCEV *One = getConstant(Stride->getType(), 1); const SCEV *One = getConstant(Stride->getType(), 1);
Show All 14 Lines APInt MaxStrideMinusOne = getUnsignedRange(getMinusSCEV(Stride, One))
.getUnsignedMax(); .getUnsignedMax();
// UMinRHS - UMaxStrideMinusOne < UMinValue => overflow! // UMinRHS - UMaxStrideMinusOne < UMinValue => overflow!
return (MinValue + MaxStrideMinusOne).ugt(MinRHS); return (MinValue + MaxStrideMinusOne).ugt(MinRHS);
} }
// Compute the backedge taken count knowing the interval difference, the // Compute the backedge taken count knowing the interval difference, the
// stride and presence of the equality in the comparison. // stride and presence of the equality in the comparison.
const SCEV *ScalarEvolution::computeBECount(const SCEV *Delta, const SCEV *Step, const SCEV *ScalarEvolution::computeBECount(const SCEV *Delta, const SCEV *Step,
bool Equality) { bool Equality) {
const SCEV *One = getConstant(Step->getType(), 1); const SCEV *One = getConstant(Step->getType(), 1);
Delta = Equality ? getAddExpr(Delta, Step) Delta = Equality ? getAddExpr(Delta, Step)
: getAddExpr(Delta, getMinusSCEV(Step, One)); : getAddExpr(Delta, getMinusSCEV(Step, One));
return getUDivExpr(Delta, Step); return getUDivExpr(Delta, Step);
} }
/// HowManyLessThans - Return the number of times a backedge containing the /// HowManyLessThans - Return the number of times a backedge containing the
Show All 23 LinesScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
const SCEV *Stride = IV->getStepRecurrence(*this); const SCEV *Stride = IV->getStepRecurrence(*this);
// Avoid negative or zero stride values // Avoid negative or zero stride values
if (!isKnownPositive(Stride)) if (!isKnownPositive(Stride))
return getCouldNotCompute(); return getCouldNotCompute();
// Avoid proven overflow cases: this will ensure that the backedge taken count // Avoid proven overflow cases: this will ensure that the backedge taken count
// will not generate any unsigned overflow. Relaxed no-overflow conditions // will not generate any unsigned overflow. Relaxed no-overflow conditions
// exploit NoWrapFlags, allowing to optimize in presence of undefined // exploit NoWrapFlags, allowing to optimize in presence of undefined
// behaviors like the case of C language. // behaviors like the case of C language.
if (!Stride->isOne() && doesIVOverflowOnLT(RHS, Stride, IsSigned, NoWrap)) if (!Stride->isOne() && doesIVOverflowOnLT(RHS, Stride, IsSigned, NoWrap))
return getCouldNotCompute(); return getCouldNotCompute();
ICmpInst::Predicate Cond = IsSigned ? ICmpInst::ICMP_SLT ICmpInst::Predicate Cond = IsSigned ? ICmpInst::ICMP_SLT
: ICmpInst::ICMP_ULT; : ICmpInst::ICMP_ULT;
const SCEV *Start = IV->getStart(); const SCEV *Start = IV->getStart();
const SCEV *End = RHS; const SCEV *End = RHS;
▲ Show 20 Lines • Show All 63 Lines • ▼ Show 20 LinesScalarEvolution::HowManyGreaterThans(const SCEV *LHS, const SCEV *RHS,
const SCEV *Stride = getNegativeSCEV(IV->getStepRecurrence(*this)); const SCEV *Stride = getNegativeSCEV(IV->getStepRecurrence(*this));
// Avoid negative or zero stride values // Avoid negative or zero stride values
if (!isKnownPositive(Stride)) if (!isKnownPositive(Stride))
return getCouldNotCompute(); return getCouldNotCompute();
// Avoid proven overflow cases: this will ensure that the backedge taken count // Avoid proven overflow cases: this will ensure that the backedge taken count
// will not generate any unsigned overflow. Relaxed no-overflow conditions // will not generate any unsigned overflow. Relaxed no-overflow conditions
// exploit NoWrapFlags, allowing to optimize in presence of undefined // exploit NoWrapFlags, allowing to optimize in presence of undefined
// behaviors like the case of C language. // behaviors like the case of C language.
if (!Stride->isOne() && doesIVOverflowOnGT(RHS, Stride, IsSigned, NoWrap)) if (!Stride->isOne() && doesIVOverflowOnGT(RHS, Stride, IsSigned, NoWrap))
return getCouldNotCompute(); return getCouldNotCompute();
ICmpInst::Predicate Cond = IsSigned ? ICmpInst::ICMP_SGT ICmpInst::Predicate Cond = IsSigned ? ICmpInst::ICMP_SGT
: ICmpInst::ICMP_UGT; : ICmpInst::ICMP_UGT;
const SCEV *Start = IV->getStart(); const SCEV *Start = IV->getStart();
Show All 31 Lines APInt MinEnd =
IsSigned ? APIntOps::smax(getSignedRange(RHS).getSignedMin(), Limit) IsSigned ? APIntOps::smax(getSignedRange(RHS).getSignedMin(), Limit)
: APIntOps::umax(getUnsignedRange(RHS).getUnsignedMin(), Limit); : APIntOps::umax(getUnsignedRange(RHS).getUnsignedMin(), Limit);
const SCEV *MaxBECount = getCouldNotCompute(); const SCEV *MaxBECount = getCouldNotCompute();
if (isa<SCEVConstant>(BECount)) if (isa<SCEVConstant>(BECount))
MaxBECount = BECount; MaxBECount = BECount;
else else
MaxBECount = computeBECount(getConstant(MaxStart - MinEnd), MaxBECount = computeBECount(getConstant(MaxStart - MinEnd),
getConstant(MinStride), false); getConstant(MinStride), false);
if (isa<SCEVCouldNotCompute>(MaxBECount)) if (isa<SCEVCouldNotCompute>(MaxBECount))
MaxBECount = BECount; MaxBECount = BECount;
return ExitLimit(BECount, MaxBECount); return ExitLimit(BECount, MaxBECount);
} }
▲ Show 20 Lines • Show All 1,071 Lines • Show Last 20 Lines

test/Analysis/ScalarEvolution/min-max-exprs.ll

  • This file was added.
; RUN: opt -scalar-evolution -analyze < %s | FileCheck %s
;
; This checks if the min and max expressions are properly recognized by
; ScalarEvolution even though they the ICmpInst and SelectInst have different
; types.
;
; #define max(a, b) (a > b ? a : b)
; #define min(a, b) (a < b ? a : b)
;
; void f(int *A, int N) {
; for (int i = 0; i < N; i++) {
; A[max(0, i - 3)] = A[min(N, i + 3)] * 2;
; }
; }
;
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
define void @f(i32* %A, i32 %N) {
bb:
br label %bb1
bb1: ; preds = %bb2, %bb
%i.0 = phi i32 [ 0, %bb ], [ %tmp23, %bb2 ]
%i.0.1 = sext i32 %i.0 to i64
%tmp = icmp slt i32 %i.0, %N
br i1 %tmp, label %bb2, label %bb24
bb2: ; preds = %bb1
%tmp3 = add nuw nsw i32 %i.0, 3
%tmp4 = icmp slt i32 %tmp3, %N
%tmp5 = sext i32 %tmp3 to i64
%tmp6 = sext i32 %N to i64
%tmp9 = select i1 %tmp4, i64 %tmp5, i64 %tmp6
; min(N, i+3)
; CHECK: select i1 %tmp4, i64 %tmp5, i64 %tmp6
; CHECK-NEXT: --> (-1 + (-1 * ((-1 + (-1 * (sext i32 {3,+,1}<nw><%bb1> to i64))) smax (-1 + (-1 * (sext i32 %N to i64))))))
%tmp11 = getelementptr inbounds i32* %A, i64 %tmp9
%tmp12 = load i32* %tmp11, align 4
%tmp13 = shl nsw i32 %tmp12, 1
%tmp14 = icmp sge i32 3, %i.0
%tmp17 = add nsw i64 %i.0.1, -3
%tmp19 = select i1 %tmp14, i64 0, i64 %tmp17
; max(0, i - 3)
; CHECK: select i1 %tmp14, i64 0, i64 %tmp17
; CHECK-NEXT: --> (-3 + (3 smax {0,+,1}<nuw><nsw><%bb1>))
%tmp21 = getelementptr inbounds i32* %A, i64 %tmp19
store i32 %tmp13, i32* %tmp21, align 4
%tmp23 = add nuw nsw i32 %i.0, 1
br label %bb1
bb24: ; preds = %bb1
ret void
}