Page MenuHomePhabricator

[LVI] Normalize pointer behavior
ClosedPublic

Authored by nikic on Nov 6 2019, 10:59 AM.

Details

Summary

Related to D69686. As noted there, LVI currently behaves differently for integer and pointer values: For integers, the block value is always valid inside the basic block, while for pointers it is only valid at the end of the basic block. I believe the integer behavior is the correct one, and CVP relies on it via its getConstantRange() uses.

The reason for the special pointer behavior is that LVI checks whether a pointer is dereferenced in a given basic block and marks it as non-null in that case. Of course, this information is valid only after the dereferencing instruction, or in conservative approximation, at the end of the block.

This patch changes the treatment of dereferencability: Instead of including it inside the block value, we instead treat it as something similar to an assume (it essentially is a non-nullness assume) and incorporate this information in intersectAssumeOrGuardBlockValueConstantRange() if the context instruction is the terminator of the basic block. This happens either when determining an edge-value internally in LVI, or when a terminator was explicitly passed to getValueAt(). The latter case makes this change not fully NFC, because we can now fold terminator icmps based on the dereferencability information in the same block. This is the reason why I changed one JumpThreading test (it would optimize the condition away without the change).

Of course, we do not want to recompute dereferencability on each intersectAssume call, so we need a new cache for this. The dereferencability analysis requires walking the entire basic block and computing underlying objects of all memory operands. This was previously done separately for each queried pointer value. In the new implementation (both because this makes the caching simpler, and because it is faster), I instead only walk the full BB once and cache all the dereferenced pointers. So the traversal is now performed only once per BB, instead of once per queried pointer value.

I think the overall model now makes more sense than before, and there will be no more pitfalls due to differing integer/pointer behavior.

Diff Detail

Event Timeline

nikic created this revision.Nov 6 2019, 10:59 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 6 2019, 10:59 AM
reames requested changes to this revision.Nov 6 2019, 6:50 PM

This is definitely heading in the right direction. Nicely done overall, see suggestions as inline comments.

llvm/lib/Analysis/LazyValueInfo.cpp
248–249

Minor: I think this can become a free function as opposed to a member function. It doesn't appear to be using member state.

647

Please add a todo about using address space property (i.e. null is defined) instead of the raw AS==0 check here.

809

Ok, I don't think this placement quite works. The challenge is that your changing the point of the block scan from the furthest reached block during the backwards walk (entry, or point of overdefine) to instead scan the query source block.

I'd suggest adjusting the two call sites you remove to use the new caching logic, and then only do the scan if a) context is terminator, or b) context is not in same block (i.e. full block case)

This revision now requires changes to proceed.Nov 6 2019, 6:50 PM
nikic marked an inline comment as done.Nov 7 2019, 12:27 AM
nikic added inline comments.
llvm/lib/Analysis/LazyValueInfo.cpp
809

The challenge is that your changing the point of the block scan from the furthest reached block during the backwards walk (entry, or point of overdefine) to instead scan the query source block.

I believe the behavior of the scan essentially stays the same: intersectAssume() is not only used to calculate the final result of the query, it is also invoked internally by LVI when computing edge values. So if you query a pointer in BB2 with incoming edge from BB1, then the first thing we do is calculate the edge value BB1 -> BB2, at which point we will intersectAssume() with the terminator of BB1.

I'd suggest adjusting the two call sites you remove to use the new caching logic, and then only do the scan if a) context is terminator, or b) context is not in same block (i.e. full block case)

We'd have to insert checks into getEdgeValue() (always) and getValueAt() / getValueInBlock() (if context is terminator), which are exactly the places where we already use intersectAssume().

nikic updated this revision to Diff 228253.Nov 7 2019, 8:24 AM
nikic marked 2 inline comments as done.

Make eraseValueFromPerBlockValueCache a free function, add todo.

reames accepted this revision.Nov 8 2019, 8:17 AM

LGTM. Very nice cleanup, thank you for doing this.

llvm/lib/Analysis/LazyValueInfo.cpp
809

You are correct. I'd misremembered the code and hadn't checked the callers before commenting. Objection withdrawn.

This revision is now accepted and ready to land.Nov 8 2019, 8:17 AM
This revision was automatically updated to reflect the committed changes.
nikic reopened this revision.Mon, Nov 18, 12:56 AM

Reopening as this has been reverted in rG7a3ad48d6de0e79a92361252a815b894565b9a0f.

This revision is now accepted and ready to land.Mon, Nov 18, 12:56 AM
lebedev.ri requested changes to this revision.Mon, Nov 25, 2:07 AM
lebedev.ri added a subscriber: echristo.

Just marking as "changes needed" to denote the revert until there's more info.
@echristo any progress on reproducer?

This revision now requires changes to proceed.Mon, Nov 25, 2:07 AM
nikic added a comment.Mon, Nov 25, 2:35 PM

I'll rebase this over D70376 once that lands, which should hopefully fix the python compilation issue. To provide some context, we were not properly invalidating elements in the overdefined value cache if they are deleted, which might result in incorrect "overdefined" result if something later happens to be allocated at the same location. This just causes non-determinism, because "overdefined" is a conservative assumption. However, this patch introduces a second cache that uses the same structure as the overdefined cache, and here missing the invalidation may result in a miscompile instead.

I'm traveling right now, so will probably only get around to this next week.

nikic updated this revision to Diff 232187.Wed, Dec 4, 11:53 AM

Rebase over D70376, fixing cache invalidation.

nikic added a comment.Thu, Dec 5, 6:52 AM

Would be good if someone could take another quick look at it, as the caching part changed significantly. The fact that the LVI caching happens in a separate class from LVI (why?) makes things slightly awkward.

Ping for re-review.

reames requested changes to this revision.Thu, Dec 12, 12:01 PM
reames added inline comments.
llvm/lib/Analysis/LazyValueInfo.cpp
162

Can you add a note to the comment about the None state being used to represent a block whose dereferenceability hasn't yet been memoized?

689

This function signature and usage seems needlessly complicated here. Can I suggest something along the lines of the following:
if (None == TheCache[BB].DereferenceablePointers) {

// populate cache

}

return TheCache[BB].DereferenceablePointers->count(V);

You could hide the population inside an ensureDereferenceabilityCached or getDereferenceablePointers interface if you wanted.

This revision now requires changes to proceed.Thu, Dec 12, 12:01 PM
nikic marked an inline comment as done.Thu, Dec 12, 12:10 PM
nikic added inline comments.
llvm/lib/Analysis/LazyValueInfo.cpp
689

The somewhat awkward API here is used to keep all the members of LazyValueInfoCache private -- I'd have to make parts of it public to allow directly populating the cache directly here.

nikic marked an inline comment as done.Thu, Dec 12, 12:16 PM
nikic added inline comments.
llvm/lib/Analysis/LazyValueInfo.cpp
689

Or is the suggestion here to just move the population of the cache itself into LazyValueInfoCache as well? That would certainly be easiest.

nikic updated this revision to Diff 233674.Thu, Dec 12, 1:23 PM

Improve cache interface: Use a single isPointerDereferenceInBlock() method which accepts a callback to initialize the cache. I think that gives a reasonable balance between hiding cache details and having natural control flow. What do you think?

reames accepted this revision.Thu, Dec 12, 4:34 PM

LGTM again.

This revision was not accepted when it landed; it landed in state Needs Review.Fri, Dec 13, 12:14 AM
This revision was automatically updated to reflect the committed changes.