RFC: Constant Hoisting

I’ve had a bug/pessimization which I’ve tracked down for 1 bit bitmasks:

if (((xx) & (1ULL << (40))))

return 1;

if (!((yy) & (1ULL << (40))))

The second time Constant Hoisting sees the value (1<<40) it wraps it up with a bitcast.

That value then gets hoisted. However, the first (1<<40) is not bitcast and gets recognized
as a BT. The second doesn’t get recognised because of the hoisting.
The result is some register allocation and unnecessary constant loading instructions.

There are maybe three ‘solutions’ to this problem, maybe more.

Starting with the second, in the middle of things, you could try pattern matching in
EmitTest() or LowerToBT(). I’ve tried this and it doesn’t work since it needs to reach
outside of a Selection DAG. Doesn’t work. Can’t work.

Thirdly, it’s been suggested to use a peephole pass and to look at
AArch64LoadStoreOptimizer.cpp. This also doesn’t work for pretty much the
same reason. Moreover, this is after register allocation so even for the limited
situations where it can work, it leaves allocated but unutilized registers.
Doesn’t work. In fact, I’d suggest the Arm backend adopt my approach.

So firstly, I think the best way to solve this problem is to avoid this problem
in the first place. Just don’t hoist these values.

For the X86 backend, X86TTI::getIntImmCost() in X86TargetTransformInfo.cpp
is an overridden function. Just mark these 1 bit masks there as TCC_Free:

// Don’t hoist 1 bit masks. They’ll probably be used for BT, BTS, BTC.
if (Imm.isPowerOf2()) // this could be limited to bits 32-63
return TCC_Free;

This works. Its only downside is when these values are being used twice
AND then not being combined into another instruction.

I’d also recommend looking at not hoisting other values. However I haven’t really
looked this over very thoroughly.

newtst.c (1.5 KB)

Yes, it does seem to be a regression (and not pilot error) although I can’t imagine how. I pulled a new tree and recompiled. Untouched and unpatched the bugs are there. newtst.c newtst.ll and newtst.s are attached.

newtst.s (1.75 KB)

newtst.ll (3.15 KB)

newtst.c (1.5 KB)

So between 3.4.1 and 3.5 since it isn't in 3.4.1 and it is in the current
XCode.

Hi Chris,

If you have everything setup to test, can you generate the LLVM IR with -03 from 3.4.1 and 3.5 to be sure they match. Then we can focus on the backend.

Thanks,

Mehdi

newtst.ll (2.61 KB)

I may have missed on email, did you send a patch?

Thanks,

Mehdi

This was an RFC and so I included the suggested patch in the text but here
it is as a patch diff. Just ignore (or remove) the Imm.isSignedIntN(8) for
now. That was mentioned in the first post as well but it was just a
suggestion.

const_patch (584 Bytes)

to get the old IR. See attached. It’s clean (except for bug #2). So 3.4.1 generates good IR and assembly and 3.5 generates good IR and bad assembly.

newtst.s (9.44 KB)

Hi all,

For what it’s worth you can click the “Permalink” button to get a short-URL version that encodes all the compiler settings and the source itself. For example: http://goo.gl/T1ZrQm

-matt

The Xcode release is from an Apple branch, which is not done at the same time as the LLVM 3.5 branch. Note the “svn” on the end of the 3.5 reference in the version info. That means that the Apple branch was done sometime between when open source 3.4 was branched and when open source 3.5 was branched.

-Jim