This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Only add uses to worklist for instrs in map, loop or phis.
Needs ReviewPublic

Authored by fhahn on Feb 27 2023, 12:51 AM.



This patch limits the def-use traversal in forgetValue to defs that have
a value in ValueExprMap, are in the same loop as the starting
instructions or are phis. This should ensure that we invalidate SCEVs as
needed, but avoid traversing instructions for which no SCEVs exist or
which have already been invalidated.

In particular, it should still invalidate

  • SCEVs for instructions if any of its operands have a SCEV which is invalidate,
  • any add-recs that depend on a given value in the current loop,
  • and LCSSA loop exit phis.

There's assertions to try to catch any cases where invalidation is
missed now, which should help to surface any edge-cases, if any.

This can cut down the time spent invalidating SCEVs. For some internal
workloads with very large functions, this reduces the time spent in
passes using SCEV by 2-5x.

For CTmark, there are also some notable improvements, mostly in ClamAV
(-0.91% with -O3):

  • NewPM-O3: -0.12%
  • NewPM-ReleaseThinLTO: -0.10%
  • NewPM-ReleaseLTO-g: -0.07%

Depends on D144848.

Diff Detail

Event Timeline

fhahn created this revision.Feb 27 2023, 12:51 AM
fhahn requested review of this revision.Feb 27 2023, 12:51 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 27 2023, 12:51 AM
nikic added a comment.Feb 27 2023, 3:21 AM

I like the idea here, and have tried changes along these lines in the past, but always ran into issues. Some questions:

  • If we have %y = add %x, 1; %z = add %y, 1 and create SCEV for %z, we will create one for %x, but not for %y. Doesn't this break the invalidation chain?
  • Can we rely on LCSSA in SCEV? I don't think it's guaranteed.
  • I don't really understand the LCSSA phi special case. The LCSSA phis themselves should already get added without the isa<PHINode> check by dint of being users of a loop value. Why do we need to enforce addition of the LCSSA users, but not its transitive users?

LCSSA is not guaranteed, SCEV can be used in non-loop passes. I think Florian's intent here is to invalidate one-input Phis (which often happen to be LCSSA phis). I'd expect they are not in value map in this case.