This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Invalidate user SCEVs along with operand SCEVs to avoid cache corruption
ClosedPublic

Authored by mkazantsev on Oct 11 2021, 3:19 AM.

Details

Summary

Following discussion in D110390, it seems that we are suffering from unability
to traverse users of a SCEV being invalidated. The result of that is that ScalarEvolution's
inner caches may store obsolete data about SCEVs even if their operands are
forgotten. It creates problems when we try to verify the contents of those caches.

It's also a frequent situation when messing with cache causes very sneaky and
hard-to-analyze bugs related to corruption of memory when dealing with cached
data. They are lurking there because ScalarEvolution's veirfication is not powerful
enough and misses many problematic cases. I plan to make SCEV's verification
much stricter in follow-ups, and this requires dangling-pointers-free caches.

This patch makes sure that, whenever we forget cached information for a SCEV,
we also forget it for all SCEVs that (transitively) use it.

This may have negative compile time impact. It's a sacrifice we are more
than willing to make to enforce correctness. We can also save some time by
reworking invokers of forgetMemoizedResults (maybe we can forget multiple
SCEVs with single query).

Diff Detail

Event Timeline

mkazantsev created this revision.Oct 11 2021, 3:19 AM
mkazantsev requested review of this revision.Oct 11 2021, 3:19 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 11 2021, 3:19 AM

If it's too bad in terms of compile time, I have some ideas how to improve it. Need to know whether they are needed immediately or can be done as follow-ups.

Before anything else, I'd really love to see compile time data. @nikic Can you easily collect?

Style wise, I think this makes a lot more sense to have a user list on the SCEV itself than a separate structure, but we can debate that separately.

Style wise, I think this makes a lot more sense to have a user list on the SCEV itself than a separate structure, but we can debate that separately.

We can't do it without const_casts, and consts_casts may cause UB. I don't want to take this risk unless you have *really* strong arguments in favour of this.

Style wise, I think this makes a lot more sense to have a user list on the SCEV itself than a separate structure, but we can debate that separately.

We can't do it without const_casts, and consts_casts may cause UB. I don't want to take this risk unless you have *really* strong arguments in favour of this.

You can always make the UseList field mutable, but let's hold that debate until we have CT numbers. One reason I prefer the field is likely better cache locality, but I could be completely wrong about that and measurements to see if it matters are a good starting point.

Compile-time on CTMark: https://llvm-compile-time-tracker.com/compare.php?from=943b3048484b7e3cf04f4d51c23c82fcece2185d&to=5e2c6abab42241c06680941be06fddcb9279e63d&stat=instructions

It doesn't look terrible at least, though some individual files go up by up to 7%. However, I suspect that as implemented this will make some of our already bad cases worse, i.e. when we're scanning over a large use-def graph, and this will effectively revisit SCEVs through an additional SCEV-level use graph. Passing in the Visited set and retaining it across a whole forgetValue()/forgetLoop() call would probably make things better at little additional complexity.

I think we can save a lot of time by making mass requests from forgetValue/loop. Let me wright a draft...

@nikic could you please re-measure this one together with D111602?

Just forwarding here:

And here's both patches together: http://llvm-compile-time-tracker.com/compare.php?from=943b3048484b7e3cf04f4d51c23c82fcece2185d&to=82329ed73bb4100f3641703982cb661f77b95344&stat=instructions

So with the CT algorithmic fix isn't so bad. At least it's not spiralling out of control. Can we continue discussion assuming that it's fairly fine?

danilaml added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
4103–4106

Why is this if needed?

I think this makes sense, and is worth the remaining compile time cost. If you want to rebase over the other patch (see my suggestion there), and address the minor style comments, I'd be willing to LGTM.

llvm/lib/Analysis/ScalarEvolution.cpp
1104

Please address the lint check.

4103–4106

Yeah, the default constructor should handle this case if I'm reading it right.

12847

I'm not sure this is the right place for the use list walk. Doing it here has the effecting of leaving all the user SCEVs around, and simplify forgetting the cached property of said SCEVs. Is that actually what we want? In particular, the (transitively reached) SCEVs will still be in the ValueExprMap and thus still mapped to the instructions.

Maybe we should be forgetting all the transitive inst->SCEV mappings as well? If we've, e.g., added flags to the IR instruction, that could very well map to a new SCEV node.

Hm, thinking about it, that's a deeper change than it first sounded. So yes, I'm convinced this is a reasonable starting point. :)

I think tracking users is generally the right thing to do, but I have some reservations about the approach. This makes a big implicit change, and I don't think we have a good understanding of the effects it has for all users of this API.

For example, if I look at https://github.com/llvm/llvm-project/blob/13c31539f7da403fee11fe2163249837460c3bf2/llvm/lib/Analysis/ScalarEvolution.cpp#L4424, which forgets all values using a SCEVUnknown placeholder, it seems like we should be replacing that code with just an invalidation of the SCEV node and it's users, rather than doing walks both on SCEV users and IR users. Of course, this would require also clearing out the corresponding SCEV <-> IR mappings at the same time.

I'm also thinking that the concept of invalid SCEVs (see checkValidity()) becomes rather silly if we're tracking users -- we should be dropping the invalid SCEV users directly and guarantee that none of the SCEVs in the map are invalid.

I would prefer it if we initially only landed the infrastructure to track users (without touching invalidation) and then migrate over individual invalidation users.

nikic added inline comments.Oct 21 2021, 10:08 AM
llvm/include/llvm/Analysis/ScalarEvolution.h
1505 ↗(On Diff #378605)

I would expect that on average there's less than 16 users for a given SCEV.

(snip)

I generally agree that once we have users, we should revisit a bunch of how we do invalidation. I have no problem with this being used in one place first, but I agree we can and should push this further.

I would prefer it if we initially only landed the infrastructure to track users (without touching invalidation) and then migrate over individual invalidation users.

I have no problem with this approach. I don't advocate it, but I'd be completely fine with the SCEV user infrastructure landing on it's own.

(Oh, one thing that occurred to me. We should probably add verification/asserts of the use links themselves at some point. I would be fine with that being a separate patch.)

mkazantsev added inline comments.Oct 21 2021, 9:59 PM
llvm/lib/Analysis/ScalarEvolution.cpp
1104

But it's what LLVM's in-bult clang-format is generating...

4103–4106

Good point!

mkazantsev planned changes to this revision.Oct 21 2021, 10:28 PM

Thanks for the input, I'll try to split out everything that can be split to make this one easier.

mkazantsev added inline comments.Oct 22 2021, 12:39 AM
llvm/include/llvm/Analysis/ScalarEvolution.h
1505 ↗(On Diff #378605)

Honestly, this depends on workload. Let's reduce it down to 8. I think the reasonable choise here requires research too big to be made.

All splittable parts are split out.

I'd LGTM this, but Nikita seemed to prefer a slightly different approach. Give him a chance to response and redirect if he feels necessary, and if not, you can treat this as LGTMed in a day or two.

mkazantsev accepted this revision.Oct 26 2021, 7:59 PM

Upon that, I'm going to merge it tomorrow if there will be no objections.

This revision is now accepted and ready to land.Oct 26 2021, 7:59 PM
nikic added a comment.Oct 27 2021, 1:12 PM

Upon that, I'm going to merge it tomorrow if there will be no objections.

Yeah, feel free. I didn't have time to work on this and don't want to hold it up further.

llvm/lib/Analysis/ScalarEvolution.cpp
12849

Might make sense to initialize this from ToForget to avoid duplicates in the initial worklist?

12877

Hm ... we don't really need to consider user SCEVs here, as the used SCEV will be part of the operands as well.

Alternatively, if we're already considering user SCEVs, we no longer need the hasOperand() approach, we could directly check whether ENT.ExactNotTaken == S.

nikic added inline comments.Oct 27 2021, 2:59 PM
llvm/lib/Analysis/ScalarEvolution.cpp
12877

To finish the thought, we could do something like for (const auto &EI : BEInfo.ExitNotTaken) if (ToForget.contains(EI.ExactNotTaken)) erase(), which makes this approximately O(exits) rather than O(loops * scevs). In any case, that's for a followup...

mkazantsev added inline comments.Oct 27 2021, 7:02 PM
llvm/lib/Analysis/ScalarEvolution.cpp
12849

Good catch!

12877

Thanks for the idea. I'll try to follow-up on that.

This revision was landed with ongoing or failed builds.Oct 27 2021, 7:39 PM
This revision was automatically updated to reflect the committed changes.

Hi,

The following starts crashing with this patch:

opt -passes='loop-mssa(indvars,indvars)' -o /dev/null bbi-63564.ll

We hit this assert:

opt: ../include/llvm/Support/Casting.h:104: static bool llvm::isa_impl_cl<llvm::Instruction, const llvm::Value *>::doit(const From *) [To = llvm::Instruction, From = const llvm::Value *]: Assertion `Val && "isa<> used on a null pointer"' failed.

nikic added a comment.Nov 29 2021, 1:09 PM

Just looking at the trace, I suspect we leave behind invalid SCEVs in ValuesAtScope. This is basically a (SCEV, Loop) -> SCEV map, and while we do clear entries if the SCEV on the left side is invalidated, we don't if the SCEV on the right is.

Just looking at the trace, I suspect we leave behind invalid SCEVs in ValuesAtScope. This is basically a (SCEV, Loop) -> SCEV map, and while we do clear entries if the SCEV on the left side is invalidated, we don't if the SCEV on the right is.

This is exactly correct. I just finished confirming this experimentally when I saw your comment.