This is an archive of the discontinued LLVM Phabricator instance.

[Analysis] Add support for vscale in computeKnownBitsFromOperator
ClosedPublic

Authored by david-arm on Sep 16 2021, 7:08 AM.

Details

Summary

In ValueTracking.cpp we use a function called
computeKnownBitsFromOperator to determine the known bits of a value.
For the vscale intrinsic if the function contains the vscale_range
attribute we can use the maximum and minimum values of vscale to
determine some known zero bits. This should help to improve code quality
by allowing certain optimisations to take place.

Tests added here:

Transforms/InstCombine/icmp-vscale.ll

Diff Detail

Event Timeline

david-arm created this revision.Sep 16 2021, 7:08 AM
david-arm requested review of this revision.Sep 16 2021, 7:08 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 16 2021, 7:08 AM

Sounds good. I assume that unsetting low bits from the min value does not help much?

llvm/lib/Analysis/ValueTracking.cpp
1705

Will VScaleTypeSize be BitWidth?

david-arm added inline comments.Sep 17 2021, 12:21 AM
llvm/lib/Analysis/ValueTracking.cpp
1705

I can't see anything in the code that guarantees the result type of an instruction will have the same width as Known. However, I'm not sure this really matters? If VScaleTypeSize < BitWidth, then I'd expect any bits above BitWidth to also be zero. I looked at Instruction::ZExt as a guide just now and we first truncate Known to be the same as the input, compute the bits on that, then zero-extend back to the original BitWidth.

What specific problem were you worried about here?

dmgreen added inline comments.Sep 17 2021, 1:01 AM
llvm/lib/Analysis/ValueTracking.cpp
1705

It just seems to be re-calculating a value that we already have.

1838

This appears to be where Known is calculated.

1882

And it's asserted that the size is correct here.

Sounds good. I assume that unsetting low bits from the min value does not help much?

I could see this being useful when min == max, which may help fold away code that checks if the vscale value is known even or a power of two.

Sounds good. I assume that unsetting low bits from the min value does not help much?

I could see this being useful when min == max, which may help fold away code that checks if the vscale value is known even or a power of two.

OK fair points @dmgreen and @sdesmalen! I'll look into taking min vscale into account as well. :)

llvm/lib/Analysis/ValueTracking.cpp
1838

Oh right I see. Thanks for explaining - I'll update the patch!

david-arm updated this revision to Diff 373185.Sep 17 2021, 3:53 AM
david-arm edited the summary of this revision. (Show Details)
  • Added checks for min vscale values too!
david-arm marked 4 inline comments as done.Sep 17 2021, 3:54 AM
foad added inline comments.Sep 17 2021, 5:04 AM
llvm/lib/Analysis/ValueTracking.cpp
1696

Maybe use auto?

1708

Can min ever be zero here?

1710

This assumes that vscale is a multiple of min, which is not documented in the langref.

david-arm added inline comments.Sep 17 2021, 5:11 AM
llvm/lib/Analysis/ValueTracking.cpp
1708

Yeah min can be zero. I think see the problem now because FirstSetBit will be set to UINT_MAX.

1710

Yes you're absolutely right. Of course if min=4, then a value of 5 would still set bit 0 too. I think that means I can only use min to check if it's equal to max.

foad added inline comments.Sep 17 2021, 5:20 AM
llvm/lib/Analysis/ValueTracking.cpp
1710

Well, you could still deduce *some* extra info from an arbitrary (min,max) pair, but it's probably overkill to try to implement that in this patch. Maybe we should have general helpers for that sort of thing. It could be useful in value tracking passes to be able to convert a known value range into known bits, and vice versa.

david-arm updated this revision to Diff 373197.Sep 17 2021, 5:45 AM
  • Fixed bug with using min vscale.
david-arm marked 4 inline comments as done.Sep 17 2021, 5:46 AM
foad added a comment.Sep 17 2021, 5:54 AM

The logic looks good to me now. I wonder if we should have an overload of KnownBits::makeConstant that takes a uint64_t?

This is a bit of a roundabout way of setting a constant, but that sounds OK to me considering what else this does. (So long as removing the llvm.vscale and replacing it with a constant won't cause problems elsewhere, I assume it shouldn't).

Can you add a quick comment explaining VScaleRange.first == VScaleRange.second vs other part of the code? And it might be worth having a test directly for converting vscale to a constant:

define i64 @const_vscale64_range4_4() vscale_range(4,4) {
entry:
  %vscale = call i64 @llvm.vscale.i64()
  ret i64 %vscale
}
david-arm updated this revision to Diff 373516.Sep 20 2021, 1:58 AM
  • Added new trivial function KnownBits::makeConstant(uint64_t) and changed ValueTracking code to use it.
  • Added simple test for a vscale constant.
  • Added comments to min == max case.
foad added inline comments.Sep 20 2021, 2:03 AM
llvm/include/llvm/Support/KnownBits.h
291 ↗(On Diff #373516)

I'm confused. How does this work (since there is no implicit conversion from uint64_t to APInt) and what does it do (i.e. what BitWidth does it use)?

david-arm marked an inline comment as done.Sep 20 2021, 2:35 AM
david-arm added inline comments.
llvm/include/llvm/Support/KnownBits.h
291 ↗(On Diff #373516)

Hi @foad, oh I see. I should probably write

return makeConstant(APInt(C));

instead. I imagine the compiler has just assumed I'm calling the version that takes an APInt!

david-arm marked an inline comment as done.Sep 20 2021, 3:13 AM
david-arm added inline comments.
llvm/include/llvm/Support/KnownBits.h
291 ↗(On Diff #373516)

Hi @foad, I just wonder if it's really worth adding this overloaded version as you were suggesting in a comment last week? Having looked into this again I realise I probably do need to pass in the BitWidth as well and I'm not sure how commonly this function would be called? I'd also have to deal with a possible mis-match in bitwidths, i.e. if we request a bit width of 32 but the constant has more than 32 bits?

foad added inline comments.Sep 20 2021, 3:23 AM
llvm/include/llvm/Support/KnownBits.h
291 ↗(On Diff #373516)

Sure, it was just a half-baked idea, I hadn't really thought through the details. It definitely wouldn't need to be part of this patch anway.

david-arm updated this revision to Diff 373541.Sep 20 2021, 3:44 AM
foad accepted this revision.Sep 20 2021, 3:48 AM

LGTM (though I don't really know anything about vscale!).

This revision is now accepted and ready to land.Sep 20 2021, 3:48 AM
dmgreen accepted this revision.Sep 20 2021, 4:33 AM

Thanks for adding the comments. LGTM

This revision was landed with ongoing or failed builds.Sep 20 2021, 7:02 AM
This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptSep 20 2021, 7:02 AM
Herald added a subscriber: cfe-commits. · View Herald Transcript