Page MenuHomePhabricator

[Bug 24848] Use range metadata to constant fold comparisons with constant values
ClosedPublic

Authored by chenli on Sep 18 2015, 3:44 PM.

Details

Summary

This is the first part of fixing bug 24848 https://llvm.org/bugs/show_bug.cgi?id=24848.

When range metadata is provided, it should be used to constant fold comparisons with constant values.

Diff Detail

Repository
rL LLVM

Event Timeline

chenli updated this revision to Diff 35146.Sep 18 2015, 3:44 PM
chenli retitled this revision from to [Bug 24848] Use range metadata to constant fold comparisons with constant values.
chenli updated this object.
chenli added reviewers: sanjoy, hfinkel.
chenli added a subscriber: llvm-commits.
sanjoy requested changes to this revision.Sep 18 2015, 6:30 PM
sanjoy edited edge metadata.
sanjoy added inline comments.
lib/Analysis/InstructionSimplify.cpp
2392 ↗(On Diff #35146)

I don't think this is correct. When an instruction has a !range like [a,b) [c,d), the set of possible values is the union of all of these ranges.

For instance, I think you'll constant fold x slt 10 to true here if the range of x is [0,9) [100,200), even though x can be 120.

I also don't think FirstRangeContainsSecond is a good abstraction, and its name is misleading.

I'd structure this bit of code as:

instead of

if (Lower != Upper) {
  ConstantRange LHS_CR = ConstantRange(Lower, Upper);

  if (Value *RetVal =
      FirstRangeContainsSecond(RHS_CR, LHS_CR, RHS->getContext())) {
    return RetVal;
  }
}
ConstantRange LHS_CR = Lower == Upper ? ConstantRange::getFullSet() : ConstantRange(Lower, Upper);
if (Instruction has !range MD) {
  ConstantRange CR = NullSet;
  for (auto Range : Inst->Ranges) {
    CR = CR.union(RangeMD)
  }
  LHS_CR = LHS_CR.intersect(CR);
}

if (!LHS_CR.isFullSet()) {
  if (RHS_CR.contains(LHS_CR))
  ... // the code as it is today
}
This revision now requires changes to proceed.Sep 18 2015, 6:30 PM
chenli added inline comments.Sep 18 2015, 9:51 PM
lib/Analysis/InstructionSimplify.cpp
2392 ↗(On Diff #35146)

Yes, you are correct. It should check the union of all the ranges here. I will fix it and update the patch.

chenli added inline comments.Sep 18 2015, 11:45 PM
lib/Analysis/InstructionSimplify.cpp
2392 ↗(On Diff #35146)
ConstantRange LHS_CR = Lower == Upper ? ConstantRange::getFullSet() : ConstantRange(Lower, Upper);
if (Instruction has !range MD) {
  ConstantRange CR = NullSet;
  for (auto Range : Inst->Ranges) {
    CR = CR.union(RangeMD)
  }
  LHS_CR = LHS_CR.intersect(CR);
}

The union part will actually give you false positive result. Consider you have a value of ranges [0, 3), [5, 7), and it is compared with == 4. Union the two ranges result a new range [0, 7), which can not be proven not equal to 4, while the original ranges can fold it. So instead of taking the union, it might be better to check each range separately, and return true if RHS_CR contains all ranges and false if RHS_CR.inverse() contains all.

sanjoy added inline comments.Sep 18 2015, 11:54 PM
lib/Analysis/InstructionSimplify.cpp
2392 ↗(On Diff #35146)

Agreed. If you can prove some fact about each of the individual ranges separately, then you can assume the fact to be true for the union of the ranges.

However, I suspect in most cases the !range metadata will contain exactly one range (in which case there is no loss of precision when taking the union of all the ranges) so the additional complexity may not be worth it. I'll leave it to you to make the final decision on this.

chenli added inline comments.Sep 18 2015, 11:57 PM
lib/Analysis/InstructionSimplify.cpp
2392 ↗(On Diff #35146)

I think that makes sense. I will take the general approach (union) first, and improve it if it shows profitable in practice in the future.

chenli edited edge metadata.

Update patch w.r.t Sanjoy's comments.

sanjoy added inline comments.Sep 19 2015, 12:24 AM
lib/Analysis/InstructionSimplify.cpp
2131 ↗(On Diff #35163)

I'm still not very happy with the interface here -- I'd rather have this function do *just* the metadata parsing; and have the dyn_cast<Instruction>(..) logic in its caller. I'd also rename this GetConstantRangeFromMetadata (and not repeat "Range" in the CR bit and RangeMetadata):

static ConstantRange GetConstantRangeFromMetadata(MDNode *RangeMD, unsigned BitWidth) {
  ...
}

and in its caller

if (auto *I = dyn_cast<Instruction>(Val))
  if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
    LHS_CR.intersectWith(GetConstantRangeFromMetadata(Ranges, LHS_BitWidth));
2137 ↗(On Diff #35163)

Why not ConstantRange CR(BitWidth, false);?

2140 ↗(On Diff #35163)

[Optional]
This is a matter of style, but I'd have written these as

auto *Low = ...
auto *High = ...

since the types are obvious, and Low, High are briefer.

2146 ↗(On Diff #35163)

[Optional]
Why not CR.unionWith({Lower->getValue(), Upper->getValue()})? Alternatively, if that does not work, CR.unionWith(ConstantRange(Lower->getValue(), Upper->getValue()))?

2394 ↗(On Diff #35163)

Can the Width declared in line 2286 be used here? I can't tell if it is out of scope easily from phabricator.

test/Transforms/InstCombine/icmp-range.ll
57 ↗(On Diff #35163)

Please add a few more test cases. At the very least, add

  • one that does not constant fold
  • one that folds to false
  • one that has a multiple sub ranges in the !range metadata
sanjoy requested changes to this revision.Sep 19 2015, 12:25 AM
sanjoy edited edge metadata.
This revision now requires changes to proceed.Sep 19 2015, 12:25 AM
chenli updated this revision to Diff 35299.Sep 21 2015, 1:14 PM
chenli edited edge metadata.

Update patch w.r.t Sanjoy's request.

I think this looks ready to go in. @hfinkel WDYT?

lib/Analysis/InstructionSimplify.cpp
2131 ↗(On Diff #35299)

There is also a similar GetRangeFromMetadata function in ScalarEvolution. As a later patch you might want to common the two (totally optional).

2133 ↗(On Diff #35299)

Since you're asserting here anyway, I'd make this stronger: assert(NumRanges >= 1 && Ranges->getNumOperands() % 2 == 0 && "Ill formed IR!");

hfinkel accepted this revision.Sep 23 2015, 2:33 AM
hfinkel edited edge metadata.

I think this looks ready to go in. @hfinkel WDYT?

LGTM too. There is obviously more than can be done here (where we propagate ranges through expressions), but that likely belongs in LVI.

I think this looks ready to go in. @hfinkel WDYT?

LGTM too. There is obviously more than can be done here (where we propagate ranges through expressions), but that likely belongs in LVI.

Thanks! I plan to do some more improvements on LVI after this patch.

This revision was automatically updated to reflect the committed changes.