Accelerate StringCoding.hasNegatives for JDK 11, 17, StringCoding.countPositives for JDK 21+ on x86

[dylanjtuttle]

This PR accelerates intrinsic candidates StringCoding.hasNegatives and StringCoding.countPositives on x86, the former on JDK 9-18 and the latter on JDK 19+.

This PR is incremental in a few ways.

• The acceleration currently only delivers the desired performance boost for arrays of up to 31 elements. For arrays of 32 elements and longer, the acceleration still outperforms default OpenJ9, but can no longer keep up with HotSpot. For that, I will need to take advantage of larger SIMD instructions.
• I have discovered a strange performance anomaly in OpenJ9 that causes it to perform significantly faster than expected for hasNegatives for arrays of 0-8 elements on JDK 19+. It performs so well for these short arrays that implementing my 'acceleration' would actually cause a performance regression there. While this anomaly is investigated, I will not be accelerating hasNegatives on JDK 19+.

In the interest of taking advantage of the performance boost as it currently stands for the 0.51 release, this PR will deliver these changes in their incremental state, with plans for another PR or two down the road to close the aforementioned gaps.

[dylanjtuttle]

Paging @vijaysun-omr, @0xdaryl for review and @r30shah, @dchopra001 as requested for comparison to acceleration on Z

[vijaysun-omr]

Looks fine to me from a quick review. I'll probably defer to @hzongaro for the review since he has much more direct awareness of this work than I do, and can easily review the inliner parts as well (that I skimmed over too).

[dylanjtuttle]

It appears that the crash is due to a recent OMR commit and is therefore unrelated to my changes. I can build successfully with the openj9 branch of the openj9-omr repo, and can now confirm all of the performance testing checks out.

[BradleyWood]

at least one of the sign bits is set

Don't you need to keep track of the index of last positive element? This function should find the number of leading positive elements so the location of that negative matters. You cannot return (i - off) as you do in the residue processing because you don't know where in the vector the first negative is.

[dylanjtuttle]

The key here was pointed out by Henry early on when I was first trying to figure out how to accelerate countPositives:

    /**
     * Count the number of leading positive bytes in the range.
     *
     * @implSpec the implementation must return len if there are no negative
     *   bytes in the range. If there are negative bytes, the implementation must return
     *   a value that is less than or equal to the index of the first negative byte
     *   in the range.
     */

countPositives only needs to return a value less than or equal to the index of the first negative byte. There are a few places in String.java that call countPositives and then do the work of finding the exact index themselves. I suppose the reason it was designed this way is to take advantage of small time saves in situations where you don't care about the exact index (like when being called by hasNegatives).

[dylanjtuttle]

@0xdaryl @hzongaro I apparently still have a bug in here somewhere because I'm getting a failure in the JCL during the build, but I thought I'd open up for a second round of review in the meantime while I work on squashing it.

[BradleyWood]

You already called cg->setSupportsInlineStringCodingCountPositives() so you should be calling cg->getSupportsInlineStringCodingCountPositives()

[dylanjtuttle]

I consolidated all of the inlining logic into InlinerTempForJ9, since I was already using it to conditionally only inline countPositives into hasNegatives. I've confirmed that the inlining behaviour is still correct using this method.

[dylanjtuttle]

I fixed the bug! I squashed all of my review comment changes into one commit, just doing some more performance testing

[hzongaro]

Great work! I just have a few suggestions/comments

[hzongaro]

Instead of having a falseLabel where resultReg is set to zero, I wonder whether it would be better to set resultReg to zero at the start of the inline code sequence. Then this end sequence would only need to handle the returnTrueLabel case:

returnTrueLabel:
   resultReg = 1
endLabel:

and the if bytes_left == 0 above could branch directly to endLabel.

[dylanjtuttle]

I chose to implement your other suggestion in #21121 (comment) instead, since I combined inlineHasNegatives and inlineCountPositives and had to choose one.

[BradleyWood]

You still have added offset before ANDing:

loopLimit = ((off + length) & -16) + off

It should be as follows:

loopLimit = (length & -16) + off

[dylanjtuttle]

Hi Brad, I might confused, but I don't think I'm adding offset before ANDing?

   // loopLimit = (length & -16) + offset
   generateRegRegInstruction(TR::InstOpCode::MOV4RegReg, node, loopLimitReg, lengthReg, cg);
   generateRegImmInstruction(TR::InstOpCode::AND4RegImm4, node, loopLimitReg, -16, cg);
   generateRegRegInstruction(TR::InstOpCode::ADD4RegReg, node, loopLimitReg, offsetReg, cg);

[dylanjtuttle]

@0xdaryl I believe I am ready for your review whenever you are!