This is an archive of the discontinued LLVM Phabricator instance.

[SafepointIRVerifier] Allow deriving pointers from unrelocated base
ClosedPublic

Authored by DaniilSuchkov on Nov 21 2017, 1:44 AM.

Details

Summary

Deriving pointer (adding GEPs/casts to base pointer) from it's base by itself
isn't incorrect even if the base pointer is unrelocated. Correctness depends
only on uses of this derived pointer. This patch allows to use derived pointers
in the same way as base pointers no matter where (before or after safepoint)
they were derived from base.
It is acheived by two changes:

  1. When we have enough information to say if the pointer is unrelocated at some

point or not, we walk all BBs to remove from their Contributions all valid defs
of unrelocated pointers (GEP with unrelocated base or bitcast of unrelocated
pointer).

  1. When it comes to verification we just ignore instructions that were removed

at stage 1.

Diff Detail

Event Timeline

DaniilSuchkov created this revision.Nov 21 2017, 1:44 AM
mkazantsev requested changes to this revision.Nov 21 2017, 9:15 PM
mkazantsev added inline comments.
lib/IR/SafepointIRVerifier.cpp
125

CastInst doesn't look like what you need, it also includes sext, zext and a lot of stuff you don't need.

129

Why do you check it outside of isDerivedPointerDef? We don't want integer-to-integer casts to be treated as derived pointers. Please add it as check.

437

it's -> its

438

"only if base pointer is relocated or not"

This revision now requires changes to proceed.Nov 21 2017, 9:15 PM
DaniilSuchkov marked 4 inline comments as done.Nov 22 2017, 2:45 AM
DaniilSuchkov edited edge metadata.

All tests now have comments, one redundant test removed, one new added. getBasePointer now works more correctly and getImmediateBase now is the only place where we need to specify which instructions can produce derived pointers.

Made logic around getImmediateBasePointer/isDerivedPointerDef more consistent.

Add message to assert.

Looks fine for me, but I'd likeone else to take a look.

anna accepted this revision.Nov 22 2017, 6:54 AM

Thanks for addressing the comments in the downstream version (and Max's comments here). This LGTM.

DaniilSuchkov planned changes to this revision.Nov 23 2017, 6:06 AM

One crash was found during testing.

DaniilSuchkov edited the summary of this revision. (Show Details)

Algorithm rewritten, new tests added.

Previous solution would work only for GEPs/casts and it was impossible to make it work with phis/selects/etc. This new solution is much more general.

Changed order of the verification traversal to RPO.

mkazantsev added inline comments.Nov 29 2017, 10:17 PM
lib/IR/SafepointIRVerifier.cpp
309

Please rename Visitor to something that makes sense in terms of what it is expected to do. I'd rather prefer something like CalculateBlockContribution or CalculateBlockContributionVisitor.

311

It's not clear to me why. I see how topological order of successors gives us gain, but it's not clear why we need BFS in addition to that. Could you please give an example?

329–333

I'd propose InputsChanged and ContributionChanged respectively. If you want to keep these names, please capitalize 1st letter since these are variables.

338

What was the reason of changing > to >=? They can never be equal due to condition one line above.

340

"if any" -> "if such order is defined"?

444

same as above, I propose ContributionChanged or IsContributionChanged.

446

ProducesUnrelocatedPointer

464

it's -> its

467

Should be << *I << if you want a reasonable output.

493

Finalize sentence.

DaniilSuchkov marked 10 inline comments as done.Nov 30 2017, 12:14 AM
DaniilSuchkov added inline comments.
lib/IR/SafepointIRVerifier.cpp
311

Sorry, my comment wasn't clear enough.

338

This assertion was supposed to be before the if-statement.

467

I is a reference, so it's OK.

DaniilSuchkov marked 3 inline comments as done.

Comments addressed.

mkazantsev added inline comments.Nov 30 2017, 12:22 AM
lib/IR/SafepointIRVerifier.cpp
337–338

It is trivially true after the assert above, isn't it?

mkazantsev added inline comments.Nov 30 2017, 12:23 AM
lib/IR/SafepointIRVerifier.cpp
337–338

Me bad, it's not.

Looks fine for me, but I'd like someone else to take a look to verify that the logic is ok.

DaniilSuchkov updated this revision to Diff 124902.EditedNov 30 2017, 3:12 AM

Now the branch where valid defs of unrelocated pointers are skipped is the first one.

anna requested changes to this revision.Dec 1 2017, 6:42 AM

Some refactoring comments in place. I think the code structuring can be made much simpler. Pls see inline comments.

lib/IR/SafepointIRVerifier.cpp
300

Nit: Stale comment. It's BBContributionUpdater

303

If BBContributionUpdater is expected to have this type, then why templatize it?
You could just typedef instead of using templated type right, I think it makes the intent clearer.

<This comment is superseded by refactoring comment below>

330

Instead of passing in an entire lambda, why not just use a static function BBContributionUpdater that also takes in a bool, which identifies if this is "after computing def states" or if this is the initial stage (i.e. BBContributionUpdater just return false if it was the initial stage) ?

It avoids all this template and function pointers and identifying what's going on. Also all logic is in one place.

This revision now requires changes to proceed.Dec 1 2017, 6:42 AM
DaniilSuchkov added inline comments.Dec 1 2017, 7:25 AM
lib/IR/SafepointIRVerifier.cpp
303

Lambda with non-empty capture list cannot be passed as function pointer. I'd rather created a new class which can build and process BlockStateMap. Such refactoring is already planned but first I want to get rid of false-positives with GEPs/bitcasts and phis (patch for phis is almost ready).

anna added inline comments.Dec 1 2017, 8:23 AM
lib/IR/SafepointIRVerifier.cpp
303

Discussed with Daniil offline, this wasn't obvious. He'll be updating the capture list.
Daniil, pls also state here why you'll be having it as a template (perhaps as a FIXME instead of the TODO below).

DaniilSuchkov edited edge metadata.
DaniilSuchkov marked 2 inline comments as done.

Amended some comments, replaced lambda's wildcard capture list with explicit one, made isNotExclusivelyConstantDerived static function (to use it in lambdas without capturing).

anna accepted this revision.Dec 1 2017, 9:42 AM

thanks for making the changes. lgtm with a minor comment.

lib/IR/SafepointIRVerifier.cpp
308

Could you pls phrase it as:
"FIXME: It's a bit ugly and unclear, but other options causes us to spread the logic of RecalculateBBStates across the rest of the algorithm." This will nicely flow with the rest of the comment about encapsulating everything in a class.

DaniilSuchkov marked an inline comment as done.

Corrected the comment.

mkazantsev accepted this revision.Dec 4 2017, 1:57 AM
This revision is now accepted and ready to land.Dec 4 2017, 1:57 AM
This revision was automatically updated to reflect the committed changes.