This is an archive of the discontinued LLVM Phabricator instance.

[GISel]: Add Legalization/lowering code for bit counting operations
ClosedPublic

Authored by aditya_nandakumar on Jul 2 2018, 12:36 PM.

Details

Summary

Ported Legalization expansions for CTLZ/CTTZ.. from DAG to GISel.

Diff Detail

Event Timeline

Updated to make use of the FileCheck API for testing all the expansions.

Hi Aditya,

Thank you for doing this!

Most of my comments are nitpicks and mild suggestions except the following ones:

https://reviews.llvm.org/D48847#inline-446232
https://reviews.llvm.org/D48847#inline-446277
https://reviews.llvm.org/D48847#inline-446317
https://reviews.llvm.org/D48847#inline-446328

include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h
671

I'm not sure what's the point of having variadic templates here. Does buildICmp or buildSelect make sense with 0, 1, or let's say 4 operands (excluding destination)?

lib/CodeGen/GlobalISel/LegalizerHelper.cpp
40

๐Ÿ‘

1063

Do you think we could MI.setDesc(TII.get(TargetOpcode:: G_CTLZ_ZERO_UNDEF)); here in-place instead of recreating the instruction from scratch?

1083

I don't think this is going to work if Len is not a power of 2.

For the sake of a smaller example, let's say Len is 6. The shift amount is going to take values 1 and 2. Let's say the SrcReg's value is 10 00 00. The Op takes values:
10 00 00
11 00 00 = 10 00 00 | 01 00 00, i == 0
11 11 00 = 11 00 00 | 00 11 00, i == 1

The final value is 2, while it had to be 0.

This could probably be fixed by rounding Len up to the closest power of 2.

1084

Maybe slightly more meaningful name?

1093

Same here, could we change MI in-place?

1101

I think there is a little opportunity here, not sure how useful in practice: if we check

if (!isLegalOrCustom({TargetOpcode::G_CTPOP, {Ty}}) &&
    isLegalOrCustom({TargetOpcode:: G_CTLZ_ZERO_UNDEF, {Ty}}))

here and fall-through if true we could lower this to 32 - ctlz_zero_undef(~x & (x-1)) with no extra selects.

Just a thought, it almost certainly doesn't worth the effort.

1129

We already have -1 constant built just above, maybe do G_ADD with it instead?

unittests/CodeGen/GlobalISel/LegalizerHelperTest.cpp
32

missing %0 at the end?

139

ditto

185

Maybe it makes sense to check here that we actually thread things correctly.

unittests/CodeGen/GlobalISel/LegalizerHelperTest.h
74

Shouldn't we call MachineModuleInfo::doInitialization(Module &M) here?

Also, if we do, MMI will be accessible as MMI.getModule() which should make createDummyModules interface simpler.

95

Why not bb.0?

98

Do you want to make these live-in?

99

The last two Twine(...)s are probably not needed (I would expect Twine::operator+ to be overloaded for every string type)

101

Any reason this is created here and passed to parseMIR by reference instead of being created and destroyed all within parseMIR?

109

It looks like if MMI is initialized properly the Module *M will be accessible from MMI.

116

Maybe swap these so an out parameter is the last?

144

doesn't look like this is used by any of the tests at the moment.

146

Not used by any of the tests?

147

So we run multiple tests over the same instance of machine function, adding new instructions w/o clearing out the machine function and the rest of the context? Also, in some not really well defined order probably (like alphabetical by test name or something).

Shouldn't we put all of this into setUp instead and clear it out properly in tearDown and run every test in a clean state?

162

Maybe call x a Block or SettingUpActionsBlock or something along these lines, then

do Block while (0);

here and at the "call site" something like

LInfoBuilder(A, {
  getActionDefinitionsBuilder(G_CTTZ_ZERO_UNDEF).legalFor({s64});
});

instead of

LInfoBuilder(A,
               getActionDefinitionsBuilder(G_CTTZ_ZERO_UNDEF).legalFor({s64}););

?

As for the name, maybe DefineLegalizerInfo is a tad better than LInfoBuilder, not sure.

164

Maybe also call verify(*ST.getInstrInfo());?

188

Do we run MachineVerifier somewhere here?

aditya_nandakumar marked 10 inline comments as done.Aug 17 2018, 3:59 PM

Thanks roman for the feedback. I'll update the patch shortly based on the feedback.

include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h
671

This required less typing one extra argument ;) . Additionally this lets you directly buildICmp like this
auto MIB = something...
auto Reg = someReg;
auto MIBCmp = Builder.buildICmp(Pred, SomeTy, MIB, Reg); This lets Op0 and Op1 be either MachineInstrBuilder or Register (for the various 4 combinations possible).
If you need to explicitly specify the use args, it needs to be something like this.

template<typename DstTy, typename UseArg0Ty, typename UseArg1Ty>
MachineInstrBuilder buildICmp(CmpInst::Predicate Pred, DstTy &&Dst,
                                                      UseArg0Ty &&Arg0, UseArg1Ty &&Arg1) {
     return buildICmp(Pred, getDestFromArg(Dst), getRegFromArg(Arg0), getRegFromArg(Arg1));
}

Which is a little more typing and longer.

lib/CodeGen/GlobalISel/LegalizerHelper.cpp
1063

Definitely we should be doing that as often as we can, but in this case, if we go that route, we'd end up in a situation where the final select would need to create a new vreg and then it's probably not safe to just blindly replace the original dest with new reg. It's definitely possible to do it in a more ugly way where we replace the first inst in place, change it's destination to a newly created vreg but this sacrifices readability of code. I think CTLZ is not frequent enough to do this.

1083

Good catch. I'll replace it with the following.
NewLen = RoundUpToPow2(Len);
x = x | (x >>1);
... until NewLen/2
return Len - PopCount(x);

1101

That's something we could do. I can possibly address this in a subsequent patch.

1129

I've changed it. Thanks

unittests/CodeGen/GlobalISel/LegalizerHelperTest.h
74

This was copied over from another unit test. I'll refactor both of these in a subsequent patch.

116

Ditto for all of the above.

144

This is currently only used to set the insertion point. I left it available if any of the future tests needed that. I can remove it if required.

146

MRI was just left here in case any tests want to use it - but it's easily accessible with B.getMF().getRegInfo(). Again, I don't mind removing it.

147

I believe each googletest does not reuse the same test fixture object across multiple tests - it creates a new fixture object, constructs/calls setup, runs test, and call teardown()/destructor. I believe each test in it's own should be in a clean state when it runs.
I hope I've not misunderstood your question.

188

No we don't currently run the verifier here.

aditya_nandakumar marked 3 inline comments as done.

Updated patch based on feedback.

rtereshin accepted this revision.Aug 17 2018, 4:24 PM

Thank you!

LGTM

unittests/CodeGen/GlobalISel/LegalizerHelperTest.h
147
188

Feels like a good idea to do that. Maybe, by default with the possibility to opt out on a test-case per test-case basis.

This revision is now accepted and ready to land.Aug 17 2018, 4:24 PM

Thanks Roman.
Submitted in r340111