This is an archive of the discontinued LLVM Phabricator instance.

Reimplement depedency tracking in the ImplicitNullChecks pass
ClosedPublic

Authored by sanjoy on Dec 8 2016, 1:59 PM.

Details

Summary

This change rewrites a core component in the ImplicitNullChecks pass for
greater simplicity since the original design was over-complicated for no
good reason. Please review this as essentially a new pass. The change
is almost NFC and I've added a test case for a scenario that this new
code handles that wasn't handled earlier.

The implicit null check pass, at its core, is a code hoisting transform.
It differs from "normal" code transforms in that it speculates
potentially faulting instructions (by design), but a lot of the usual
hazard detection logic (register read-after-write etc.) still applies.
We previously detected hazards by keeping track of registers defined and
used by machine instructions over an instruction range, but that was
unwieldy and did not actually confer any performance benefits. The
intent was to have linear time complexity over the number of machine
instructions considered, but it ended up being N^2 is practice.

This new version is more obviously O(N^2) (with N capped to 8 by
default) in hazard detection. It does not attempt to be clever in
tracking register uses or defs (the previous cleverness here was a
source of bugs).

Once this is checked in, I'll extract out the IsSuitableMemoryOp and
CanHoistLoadInst lambda into member functions (they're too complicated
to be inline lambdas) and do some other related NFC cleanups.

Diff Detail

Repository
rL LLVM

Event Timeline

sanjoy updated this revision to Diff 80820.Dec 8 2016, 1:59 PM
sanjoy retitled this revision from to Reimplement depedency tracking in the ImplicitNullChecks pass.
sanjoy updated this object.
sanjoy added reviewers: reames, anna, atrick.
sanjoy added a subscriber: llvm-commits.
atrick resigned from this revision.Dec 8 2016, 4:10 PM
atrick removed a reviewer: atrick.

Sounds great, but I 'm unavailable for code reviews for about the next month.

anna added inline comments.Dec 20 2016, 8:22 AM
lib/CodeGen/ImplicitNullChecks.cpp
77 ↗(On Diff #80820)

Add the fact that we handle at most one dependent instruction?

97 ↗(On Diff #80820)

This is actually not true right? There are checks done after getting the dependent instruction, to make sure that the register in dependent instruction does not overlap with the PointerReg.

195 ↗(On Diff #80820)

Nit: const with pass by reference.

217 ↗(On Diff #80820)

Could you please clarify the type of MachineInstr we consider in canReorder using asserts? IIUC, only one of A or B can be a memory instruction (this is verified by caller of canReorder).

If both are memory instructions, this method can incorrectly return true.

435 ↗(On Diff #80820)

What does the comment mean? Couldn't find any TODO.

441 ↗(On Diff #80820)

this assert is also valid because of the check done at the end of IsSuitableMemoryOp: line 386, right?

sanjoy planned changes to this revision.Dec 20 2016, 9:28 AM

Replied to some comments inline, will upload new revision soon.

lib/CodeGen/ImplicitNullChecks.cpp
97 ↗(On Diff #80820)

That check is required not to check the validity of the hoist, but to check if the hoisted pair of instructions can be used to do an implicit null check on PointerReg. That is, if we didn't care about implicit null checking, but only cared for hoisting, that check in PointerReg won't be necessary.

195 ↗(On Diff #80820)

Are you talking about ArrayRef? ArrayRef are lightweight immutable objects that are generally supposed to be passed by value.

217 ↗(On Diff #80820)

Good point, I'll either add an explicit check or add an assert.

435 ↗(On Diff #80820)

Ugh, I meant to fill in that comment before uploading the patch (the TODO was really "TODO - complete the comment"). I'll fix this in the next iteration.

441 ↗(On Diff #80820)

Yes.

sanjoy updated this revision to Diff 82190.Dec 20 2016, 6:13 PM
sanjoy marked 4 inline comments as done.
  • Address review
sanjoy added inline comments.Dec 20 2016, 6:44 PM
lib/CodeGen/ImplicitNullChecks.cpp
195 ↗(On Diff #80820)

In case you were talking about the MachineInstr, I did manage to constify some of the parameters. Did not change to a reference since that would involved more dereferencing ceremony than I think is necessary.

anna added inline comments.Dec 21 2016, 8:11 AM
lib/CodeGen/ImplicitNullChecks.cpp
195 ↗(On Diff #80820)

Actually, I meant the ArrayRef itself. You're right, I checked the ADT definition, the elements are const.

anna accepted this revision.Dec 21 2016, 8:28 AM
anna edited edge metadata.

LGTM with comments.

lib/CodeGen/ImplicitNullChecks.cpp
203 ↗(On Diff #82190)

Nit: range based for loop here, unless some reason not to have it?

for (auto *I : Block)
374 ↗(On Diff #82190)

Just curious if there's any reason for choosing 8? I think the usual number for any sort of llvm related threshold is 6?

97 ↗(On Diff #80820)

agreed.

This revision is now accepted and ready to land.Dec 21 2016, 8:28 AM
sanjoy added inline comments.Dec 21 2016, 8:31 AM
lib/CodeGen/ImplicitNullChecks.cpp
203 ↗(On Diff #82190)

I need the iterator because I want to assign to Dep.

374 ↗(On Diff #82190)

No reason -- 8 just seemed "more than enough". I can change it to 6 if feel strongly about it.

anna added inline comments.Dec 22 2016, 7:56 AM
lib/CodeGen/ImplicitNullChecks.cpp
374 ↗(On Diff #82190)

8 is fine.

This revision was automatically updated to reflect the committed changes.