Page MenuHomePhabricator

[ConstantRange] Add makeAllowedNoWrapRegion()
AcceptedPublic

Authored by nikic on May 7 2019, 1:41 PM.

Details

Summary

This adds a counterpart to makeGuaranteedNoWrapRegion(): While makeGNWR creates an LHS range which will never cause overflow, makeANWR creates a range outside of which will always cause overflow (more specifically: the smallest such range -- a conservative implementation would be to always return the full range). The intended use-case is to intersect the LHS operand of nuw/nsw operations with it.

The implementation is to the most part exactly the same as makeGNWR but with min/max swapped. The only non-trivial case is signed multiplication, where we need to take into account both the smallest non-negative value and the largest negative one (insofar as they exist). These are extracted by intersecting with the signed half-spaces.

Diff Detail

Event Timeline

nikic created this revision.May 7 2019, 1:41 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 7 2019, 1:41 PM

This kinds fell off my radar (best to ping weekly).
I should ask, can this be implemented in terms of some other function[s], to reduce code duplication?

@lebedev.ri For the mul part I think I have already extracted the reusable parts (the exact nuw/nsw calculation). For add/sub the code for guaranteed and allowed nowrap region is really similar, the only difference is basically that min/max is swapped everywhere. However, I'm not sure how I can share this code in a way that makes sense semantically.

One possibility that comes to mind is to extract more "exact" (single value) helper functions like this:

static ConstantRange makeExactAddNSWRegion(const APInt &V) {
  APInt SignedMinVal = APInt::getSignedMinValue(V.getBitWidth());
  if (V.isNegative())
    return ConstantRange::getNonEmpty(SignedMinVal - V, SignedMinVal);
  else
    return ConstantRange::getNonEmpty(SignedMinVal, SignedMinVal - V);
}

and then compute guaranteed/allowed as either an intersection or union of them:

// guaranteed
makeExactAddNSWRegion(Other.getSignedMin())
    .intersectWith(Other.getSignedMax())
// allowed
makeExactAddNSWRegion(Other.getSignedMin())
    .unionWith(Other.getSignedMax())

That would maybe be semantically cleaner, though less efficient than explicitly constructing the result range.

lebedev.ri accepted this revision.Jul 10 2019, 2:56 PM

I'm sorry.
I was initially hoping someone else would comment on the semantics (@sanjoy ?),
but then this has completely fallen off my radar.

I think this is ok, but it would be good to have at least one actual piece of code that actually uses this.

This revision is now accepted and ready to land.Jul 10 2019, 2:56 PM