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.

Closed #418.