This is an archive of the discontinued LLVM Phabricator instance.

[ADT] Allocate memory less often by increase inline storage
Needs ReviewPublic

Authored by majnemer on Aug 17 2016, 5:13 PM.

Details

Summary

Previously, APInt was a tagged union between a single 64-bit value and a
pointer.

Extensive profiling revealed that an application of LLVM was spending
35% of its time allocating and freeing memory for 65-bit APInts.

This patch proposes to change our representation for APInts by adding an
additional 64-bit value.

On platforms which support 128-bit arithmetic, __u?int128_t is used to
speed up APInt computations for bitwidths between 65 and 128.

I would appreciate help benchmarking this change. It dramatically
speeds up my application of LLVM but more data would be gratefully
appreciated.

Diff Detail

Event Timeline

majnemer updated this revision to Diff 68458.Aug 17 2016, 5:13 PM
majnemer retitled this revision from to [ADT] Allocate memory less often by increase inline storage.
majnemer updated this object.
majnemer added a subscriber: llvm-commits.

A few quick comments.

include/llvm/ADT/APInt.h
83

If VAL was a pair, or a struct { uint64_t Low, High; }, it'd be copyable directly. Also I'd rather read Val.Low instead of Val[0].

271

Spurious braces for the if?

273

I'd have missed this one :)

276

Remove braces?

322

Same braces as above.

329

Couldn't you just copy VAL as whole all the time?

344

I guess the fact that VAL[1] can be initialized makes explains why you're copying only part of it. Do you expect better code with this? I feel it is easier to think about VAL as a single unit as much as possible.

436

VAL[0] == 0 && isPowerOf2_64(VAL[1]) ?

720

Any risk that you're reading uninitialized memory here? (in line with comment in the default ctor above)

majnemer added inline comments.Aug 17 2016, 9:07 PM
include/llvm/ADT/APInt.h
83

It might be a little misleading given that High would be uninitialized under certain circumstances.

271

I think its most common to brace all the if/else if if any of them are braced.

329

It might be uninitialized.

344

I prefer not initializing it if it will never be used. This allows tools like valgrind and ubsan find bugs.

436

I think your formulation is wrong if VAL[0] is 1 and VAL[1] is 0.

720

Good point, I'll amend this.

sanjoy edited edge metadata.Aug 30 2016, 9:50 PM

I'm not sure if this is the right approach -- I think it is better to avoid a change of this scale if possible.

Have you considered changing the access to pVal in APInt.cpp to go through an accessor that returns &VAL[0] if the bitwidth is <= 128? The union could be changed to:

union {
  uint64_t LocalArray[2];
  uint64_t VAL;
  uint64_t *pVal;
};

to avoid breaking existing uses of VAL, and most of the existing code (except perhaps things like AssignSlowCase) should work as they do now. This approach will also easily generalize to a LocalArray[N].

The downside of what I've suggested above is that the "fast path" for some of the two-word operations will not be visible but a) they may not actually matter, and b) we can change them one by one as needed.

sanjoy requested changes to this revision.Sep 11 2016, 10:05 PM
sanjoy edited edge metadata.

"Marking as read".

This revision now requires changes to proceed.Sep 11 2016, 10:05 PM
sanjoy resigned from this revision.Jan 29 2022, 5:27 PM
This revision now requires review to proceed.Jan 29 2022, 5:27 PM