This is an archive of the discontinued LLVM Phabricator instance.

Differential D23267

[LVI] Take range metadata into account while calculating icmp condition constraints
ClosedPublic

Authored by apilipenko on Aug 8 2016, 8:29 AM.

Details

Reviewers
sanjoy
Commits
rG6669f253d582: [LVI] Take range metadata into account while calculating icmp condition…
rL278496: [LVI] Take range metadata into account while calculating icmp condition…
Summary

Take range metadata into account for conditions like this:

%length = load i32, i32* %length_ptr, !range !{i32 0, i32 2147483647}
%cmp = icmp ult i32 %a, %length

This is a common pattern for range checks where the length of the array is dynamically loaded.

Diff Detail

Event Timeline

apilipenko updated this revision to Diff 67174.Aug 8 2016, 8:29 AM
apilipenko retitled this revision from to [LVI] Take range metadata into account while calculating icmp condition constraints.
apilipenko updated this object.
apilipenko added a reviewer: sanjoy.
apilipenko updated this object.
apilipenko added a subscriber: llvm-commits.
sanjoy accepted this revision.Aug 8 2016, 10:09 AM
sanjoy edited edge metadata.

lgtm

test/Transforms/CorrelatedValuePropagation/range.ll
460

Phabricator says there's a missing newline at the end of this file.

This revision is now accepted and ready to land.Aug 8 2016, 10:09 AM
Closed by commit rL278496: [LVI] Take range metadata into account while calculating icmp condition… (authored by apilipenko). · Explain WhyAug 12 2016, 3:22 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents

PathSize
lib/
Analysis/
3 lines
test/
Transforms/
CorrelatedValuePropagation/
19 lines
17 lines

Diff 67174

lib/Analysis/LazyValueInfo.cpp

Show First 20 Lines • Show All 1,212 Lines • ▼ Show 20 Lines if (LHS != Val)
match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset))); match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset)));
if (LHS == Val || Offset) { if (LHS == Val || Offset) {
// Calculate the range of values that are allowed by the comparison // Calculate the range of values that are allowed by the comparison
ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(), ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
/*isFullSet=*/true); /*isFullSet=*/true);
if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
RHSRange = ConstantRange(CI->getValue()); RHSRange = ConstantRange(CI->getValue());
else if (Instruction *I = dyn_cast<Instruction>(RHS))
if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
RHSRange = getConstantRangeFromMetadata(*Ranges);
// If we're interested in the false dest, invert the condition // If we're interested in the false dest, invert the condition
CmpInst::Predicate Pred = CmpInst::Predicate Pred =
isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate); isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate);
ConstantRange TrueValues = ConstantRange TrueValues =
ConstantRange::makeAllowedICmpRegion(Pred, RHSRange); ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);
if (Offset) // Apply the offset from above. if (Offset) // Apply the offset from above.
▲ Show 20 Lines • Show All 552 Lines • Show Last 20 Lines

test/Transforms/CorrelatedValuePropagation/add.ll

Show First 20 Lines • Show All 159 Lines • ▼ Show 20 Lines
bb: bb:
; CHECK: %add = add nuw nsw i32 %a, 1 ; CHECK: %add = add nuw nsw i32 %a, 1
%add = add i32 %a, 1 %add = add i32 %a, 1
br label %exit br label %exit
exit: exit:
ret void ret void
} }
@limit = external global i32
; CHECK-LABEL: @test9(
define i32 @test9(i32* %p, i32 %i) {
%limit = load i32, i32* %p, !range !{i32 0, i32 2147483647}
%within.1 = icmp ugt i32 %limit, %i
%i.plus.7 = add i32 %i, 7
%within.2 = icmp ugt i32 %limit, %i.plus.7
%within = and i1 %within.1, %within.2
br i1 %within, label %then, label %else
then:
; CHECK: %add = add nuw nsw i32 %a, 6
%i.plus.6 = add i32 %i, 6
ret i32 %i.plus.6
else:
ret i32 0
}

test/Transforms/CorrelatedValuePropagation/range.ll

Show First 20 Lines • Show All 439 Lines • ▼ Show 20 Linesthen:
%dead = icmp eq i32 %a, 8 %dead = icmp eq i32 %a, 8
%alive = icmp eq i32 %a, 16 %alive = icmp eq i32 %a, 16
%result = or i1 %dead, %alive %result = or i1 %dead, %alive
ret i1 %result ret i1 %result
else: else:
ret i1 false ret i1 false
} }
@limit = external global i32
define i1 @test15(i32 %a) {
; CHECK-LABEL: @test15(
; CHECK: then:
; CHECK-NEXT: ret i1 false
%limit = load i32, i32* @limit, !range !{i32 0, i32 256}
%cmp = icmp ult i32 %a, %limit
br i1 %cmp, label %then, label %else
then:
%result = icmp eq i32 %a, 255
ret i1 %result
sanjoyUnsubmitted
Not Done
ReplyInline Actions

Phabricator says there's a missing newline at the end of this file.

sanjoy: Phabricator says there's a missing newline at the end of this file.
else:
ret i1 false
}
No newline at end of file