Smalltalk › Squeak › Squeak VM

[OpenSmalltalk/opensmalltalk-vm] Proposal: an (optional) primitive for SmallInteger highBit (#418)

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

5 messages Options

David T Lewis

[OpenSmalltalk/opensmalltalk-vm] Proposal: an (optional) primitive for SmallInteger highBit (#418)

I have more and more algorithms depending on highBit and the code is fast yet but not enough (appears in tally espcially in Spur64)...

The primitive could use the Count Leading Zero instructions available on most uproc via gcc builtin_clz or MSVC __lzcnt, 32 and 64 bits variants.
Something like this pseudo code:

leadingZeroCount := builtin_clz( taggedIntegerReceiver );
if (clz == 0) return primitiveFail();
else {
    highBit := WordSize * 8 "CHAR_BIT" - numTagBits - leadingZeroCount;
    return makeSmallInteger( highBit );
}

This primitive should be jitted of course (easy, just need to add an instruction).

Primitive fallback code would aggregate < 0 failure test case + code of highBitOfPositiveReceiver if primitive is absent (no need for two messages, in most case the primitive will be here and fast enough).

Is a primitive number mandatory for being jitted?
If yes, how to reserve/allocate one?

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub, or mute the thread.

David T Lewis

Re: [OpenSmalltalk/opensmalltalk-vm] Proposal: an (optional) primitive for SmallInteger highBit (#418)

Is a primitive number mandatory for being jitted?

I'd be surprised if a number is mandatory, but I'm not sure this should be part of some plugin (e.g. LargeIntegers).

If yes, how to reserve/allocate one?

Primitives 541-559 are used for SmallFloats and there's still some unused numbers after them (560 569). But I don't know how primitive numbers were reserved in the past. We might want to inform the Squeak/Pharo boards?

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub, or mute the thread.

David T Lewis

Re: [OpenSmalltalk/opensmalltalk-vm] Proposal: an (optional) primitive for SmallInteger highBit (#418)

In reply to this post by David T Lewis

I came up with a first implementation in InterpreterPrimitives

primitiveHighBit
	| integerReceiverOop leadingZeroCount highestBitZeroBased indexWasSet integerValue |
	integerReceiverOop := self stackTop.
	self cppIf: #'__GNUC__' defined
		ifTrue:
			["Note: in gcc, result is undefined if input is zero (for compatibility with BSR(RBIT) fallback when no CLZ instruction available).
			but input is never zero because we pass the oop with tag bits set, so we are safe"
			self cppIf: objectMemory wordSize = 4
				ifTrue:
					[leadingZeroCount := self __builtin_clz: integerReceiverOop..
					leadingZeroCount = 0
						ifTrue:
							["highBit is not defined for negative Integer"
							self primitiveFail]
						ifFalse: [self pop: 1 thenPushInteger: (leadingZeroCount bitXor: 31)]]
				ifFalse:
					["Setting all the tag bits is necessary so as to have the right answer for 0 highBit."
					leadingZeroCount := self __builtin_clzll: (integerReceiverOop bitOr: (1 << objectMemory numTagBits - 1))].
					leadingZeroCount = 0
						ifTrue:
							["highBit is not defined for negative Integer"
							self primitiveFail]
						ifFalse: [self pop: 1 thenPushInteger: objectMemory wordSize * 8 - objectMemory numTagBits - leadingZeroCount]]
		ifFalse: [self cppIf: #'_MSC_VER' defined
			ifTrue:
				["In MSVC, _lzcnt and _lzcnt64 builtins do not fallback to BSR(RBIT) when not supported by CPU
				Instead of messing with __cpuid() we always use the BSR intrinsic"
				
				"Trick: we test the oop sign rather than the integerValue. Assume oop are signed (so far, they are, sqInt are signed)"
				integerReceiverOop < 0 ifTrue: [self primitiveFail] ifFalse: [		
				self cppIf: objectMemory wordSize = 4
					ifTrue:
						["We do not even test the return value, because integerReceiverOop is never zero"
						self _BitScanReverse: highestBitZeroBased address _: integerReceiverOop.
						"thanks to the tag bit, the +1 operation for getting 1-based rank is not necessary"
						self pop: 1 thenPushInteger: highestBitZeroBased]
					ifFalse:
						["In 64 bits, that' a bit more tricky because of 3 tag bits, use un-tagged value"
						integerValue := objectMemory integerValueOf: integerReceiverOop.
						"initialize with -1 so that adding +1 works when integerValue is zero"
						highestBitZeroBased := -1.
						indexWasSet := self _BitScanReverse64: highestBitZeroBased address _: integerValue.
						"assume that highestBitZeroBased is untouched when integerValue is zero"
						self pop: 1 thenPushInteger: highestBitZeroBased + 1]]]
			ifFalse:
				["not gcc/clang, nor MSVC, you have to implement if your compiler provide useful builtins"
				self primitiveFail]].

It works, gives a speed-up of 1.5x to 3x in Spur64, and I expect much more from JIT version.

For JIT, I will have to test cpu capabilities via CPUID and switch to LZCNT or BSR(RBIT) instructions on INTEL (or just BSR as demonstrated in the MSVC branch above).
It seems there is a CLZ on both ARM and MIPS.
But I first need to enhance our cogit with new instructions. How to name the generic/specific selectors?

For the primitive, it's better to abandon the monolithic-omniscient style for a more distributed-object-oriented one, or there's no point in writing the VM in Smalltalk...

Specifically, I would like to delegate the object-representation-dependent code to specialized classes...
For example above code generate incorrect (but unreachable) code for 32bits words in 64bits VM, et vice et versa. This is yet another smell...

I don't well see which class (ObjectMemory, SpurMemoryManager, ...) nor which selector would fit the current VM-style...

There will be some duplication of C-Compiler-dependent-builtin-logic, because we do not reify the C-compiler and cannot double dispatch... If there's a way to avoid, I'm all ears (JIT is somehow easier!!!).

Any thought appreciated.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub, or mute the thread.

David T Lewis

Re: [OpenSmalltalk/opensmalltalk-vm] Proposal: an (optional) primitive for SmallInteger highBit (#418)

In reply to this post by David T Lewis

I have published VMMaker.oscog-nice.2542 / 2543 in https://source.squeak.org/VMMakerInbox

https://source.squeak.org/VMMakerInbox/VMMaker.oscog-nice.2542.diff
https://source.squeak.org/VMMakerInbox/VMMaker.oscog-nice.2543.diff

It's not ready for inclusion but somehow works on X64 (beware, I tested first then refactored...)

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub, or mute the thread.

David T Lewis

Re: [OpenSmalltalk/opensmalltalk-vm] Proposal: an (optional) primitive for SmallInteger highBit (#418)

In reply to this post by David T Lewis

Closed #418.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub, or unsubscribe.