Page MenuHomePhabricator

[APInt] Enable APInt to support zero bit integers.
ClosedPublic

Authored by lattner on Sep 9 2021, 4:20 PM.

Details

Summary

Motivation: APInt not supporting zero bit values leads to
a lot of special cases in various bits of code, particularly
when using APInt as a bit vector (where you want to start with
zero bits and then concat on more. This is particularly
challenging in the CIRCT project, where the absence of zero-bit
ConstantOp forces duplication of ops and makes instcombine-like
logic far more complicated.

Approach: zero bit integers are weird. There are two reasonable
approaches: either make it illegal to do general arithmetic on
them (e.g. sign extends), or treat them as as implicitly having
a zero value. This patch takes the conservative approach, which
enables their use in bitvector applications.

Diff Detail

Event Timeline

lattner created this revision.Sep 9 2021, 4:20 PM
lattner requested review of this revision.Sep 9 2021, 4:20 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 9 2021, 4:20 PM

Craig or Andrew's, would you be willing to review this?

One random example of where zero bit values would be better: https://github.com/llvm/circt/blob/main/lib/Dialect/Comb/CombFolds.cpp#L1909

The bigger problem is that things like firrtl.constant cannot represent zero bit values, which causes no end of problem, e.g. here:
https://github.com/llvm/circt/blob/main/lib/Dialect/FIRRTL/FIRRTLFolds.cpp

craig.topper added inline comments.Sep 9 2021, 4:50 PM
llvm/include/llvm/ADT/APInt.h
575–576

This comment is wrong. We aren't checking bitwidth, we're checking that both bitwidths are <=64, but not that they are the same.

580

Why don't we need to clearUnusedBits here?

llvm/lib/Support/APInt.cpp
262

I assume you droped this because it's checked in operator*?

1098

BitWidth?

lattner updated this revision to Diff 371752.Sep 9 2021, 5:02 PM
lattner marked 3 inline comments as done.

Fix an incorrect comment, and tweak some logic that Craig noticed.

lattner marked an inline comment as done.Sep 9 2021, 5:03 PM
lattner added inline comments.
llvm/include/llvm/ADT/APInt.h
575–576

agreed, good catch.

580

I can split this out to a different patch if you prefer. It just isn't needed. RHS is already a well formed APInt, so it already has the right zero bits at the top.

llvm/lib/Support/APInt.cpp
262

Right. I trimmed some redundant checks.

1098

great catch

craig.topper added inline comments.Sep 9 2021, 5:36 PM
llvm/include/llvm/ADT/APInt.h
580

Couldn't RHS have more bits than this which would require the bits to be removed?

lattner marked an inline comment as done.Sep 9 2021, 6:00 PM
lattner added inline comments.
llvm/include/llvm/ADT/APInt.h
580

Nope. This is a copy ctor, we're taking both the new value and the new bitwidth, so the new value is already guaranteed to be normalized under the new bitwidth by the instance we're copying from.

lattner updated this revision to Diff 371758.Sep 9 2021, 6:02 PM

Fix case issue in unit test to make clang-tidy happier.

youngar added inline comments.Sep 9 2021, 6:06 PM
llvm/include/llvm/ADT/APInt.h
1441–1446

In the initial comment block you mention that zext is defined, should this assert be removed?

youngar added inline comments.Sep 9 2021, 6:08 PM
llvm/include/llvm/ADT/APInt.h
1441–1446

Oh, this should be moved to getSExtValue()

lattner added inline comments.Sep 9 2021, 6:25 PM
llvm/include/llvm/ADT/APInt.h
1441–1446

What I meant is the zext() method which zero extends an APInt (by adding new zeros and not caring about what is already there). I chose to make this undefined on zero bit values because it is accessing the (non-existent) value.

We could change this (in this, or in a future patch), and make getZExtValue() also work. That would definitely enable a bunch of stuff to "just work" with zero bit APInts, I just started out conservative with this patch.

craig.topper added inline comments.Sep 9 2021, 6:57 PM
llvm/include/llvm/ADT/APInt.h
580

Derp. That makes sense.

lattner marked 4 inline comments as done.Sep 9 2021, 10:31 PM

Thanks. @youngar are you satisfied with this as a logical step forward? Anyone willing to provide an LGTM?

incidentally, I fixed the clang-tidy warnings in new code, but I don't plan to "clang tidy clean" this code pervasively. it would distract from the core of what this patch is about.

Yeah, I'm happy with this step forward. LGTM.

This revision is now accepted and ready to land.Sep 9 2021, 10:36 PM

Thanks both!

This revision was landed with ongoing or failed builds.Sep 9 2021, 10:44 PM
This revision was automatically updated to reflect the committed changes.
xbolva00 added inline comments.Sep 10 2021, 10:44 AM
llvm/include/llvm/ADT/APInt.h
351

LLVM_UNLIKELY?

1494

detto

1844

.

llvm/lib/Support/APInt.cpp
1067

.

1085

also here and below..

Thanks for the head's up @xbolva00. Will add those in a follow-up

foad added a subscriber: foad.Sep 13 2021, 2:30 AM
foad added inline comments.
llvm/include/llvm/ADT/APInt.h
352

Should be true, surely?

lattner added inline comments.Sep 13 2021, 9:01 AM
llvm/include/llvm/ADT/APInt.h
352

Welcome to the weirdness of zero bit integers :)

foad added inline comments.Sep 13 2021, 9:17 AM
llvm/include/llvm/ADT/APInt.h
352

I'm not joking. I assert that isAllOnes(getZeroWidth()) should return true, for the same reason that std::all_of() returns true on an empty range.

To put it another way, all of the bits in a zero-width integer are 1, and I challenge you to show me one that isn't!

To put it another way, isAllOnes(X) should be the same as X == (1 << X.getBitWidth()) - 1.

You're right - I think there are two logically consistent paths we could take (and this patch isn't either of them):

  1. We could take your approach.
  2. We could abort and die on isAllOnes() saying it is not defined.

The patch is already treating zero bit integers as "zero" (no bits set means the value is zero) in the isZero() and isOne() predicates, so I think that going with #1 is defensible. We could also define sext(zerobit) as filling with zeros as well. WDYT?

I'm happy to switch this if we can settle on a design.

foad added a comment.Sep 13 2021, 9:36 AM

My starting point is that a zero-width unsigned integer makes sense and always has the value 0, but a zero-width signed integer makes no sense at all (I think you could "logically" argue that it is always 0, or that is is always -1). With that in mind...

You're right - I think there are two logically consistent paths we could take (and this patch isn't either of them):

  1. We could take your approach.
  2. We could abort and die on isAllOnes() saying it is not defined.

I'd prefer (1) and I think it's logically consistent.

The patch is already treating zero bit integers as "zero" (no bits set means the value is zero) in the isZero() and isOne() predicates, so I think that going with #1 is defensible. We could also define sext(zerobit) as filling with zeros as well. WDYT?

I think isZero and isOne and zext should all work on zero-width integers, but sext should assert that the width is non-zero.

My starting point is that a zero-width unsigned integer makes sense and always has the value 0, but a zero-width signed integer makes no sense at all (I think you could "logically" argue that it is always 0, or that is is always -1). With that in mind...
I think isZero and isOne and zext should all work on zero-width integers, but sext should assert that the width is non-zero.

I don't understand how sext is different. APInt doesn't hold a signed value, and sext doesn't extend from a signed value. sext is a function defined based on the high bit of the existing value. It doesn't make sense for a zero-width APInt to return true for isZero() but not produce a n-bit zero value for sext(n).

foad added a comment.Sep 13 2021, 2:56 PM

It doesn't make sense for a zero-width APInt to return true for isZero() but not produce a n-bit zero value for sext(n).

You could just as well say: it doesn't make sense for a zero-width APInt to return true for isAllOnes() but not produce a n-bit all-ones value for sext(n).

Zero-width ints satisfy both isZero() and (I assert) isAllOnes(), so something has to give. I think the solution is to say that sext is not defined on zero-width ints because...

sext is a function defined based on the high bit of the existing value.

... a zero-width int doesn't have a high bit.

Hi Jay,

I'm getting caught back up on old patches and I'm not sure if I closed this off with you. isAllOnes() seems defined on zero bit values now, so I think you're happy. Am I missing anything more?

-Chris

foad added a comment.Oct 6 2021, 1:17 AM

I'm getting caught back up on old patches and I'm not sure if I closed this off with you. isAllOnes() seems defined on zero bit values now, so I think you're happy. Am I missing anything more?

isAllOnes returns false on zero bit values. I still maintain it should return true. Then I'd be happy :)

Ok, I'll take the scary risk of making you incrementally happier: https://reviews.llvm.org/D111241 :-)

Thanks Jay!

uenoku added a subscriber: uenoku.Nov 30 2021, 10:57 AM