[LLVMdev] Missed devirtualization opportunities

[Kenneth Uildriks]

> You're right, I hadn't thought this through. The whole point of making them
> local is to say that "I'm sure these callees won't modify that memory"
> regardless of what functions actually get called, even indirectly. We can't
> know that they won't modify the vptr in advance, so invariant doesn't work
> here. Making it non-local just means that we would need to know the static
> call graph, which we don't because we haven't devirtualized yet so all the
> calls are indirect.
> Nick

So that means you're now saying that llvm.invariant.end ought to be
left the way it is, right?

I've been thinking about how to better take the invariant regions into
account, and it quickly became clear that it would be easier to handle
if we scanned forward instead of backwards.  Any way you do it,
there'd be a lot more scanning in memdep than there is at present...
you can't tell just by looking at the instructions between a load and
a preceding potential clobber that those two instructions are actually
in an invariant region.

Which led me to wonder if perhaps instead of tracing individual
pointers on request with memdep, we should maybe create an
generalization of mem2reg to handle all pointers mentioned in a
function.  A clobber outside of an invariant region would "unassign"
the location and all of its may-aliases.  A store would "assign" the
location and all of its must-aliases and "unassign" all of its
may-aliases.  A load would then use the SSA assignment if one is
unquestionably available, or remain in place as a load and then
"assign" the load result back to the pointer.  No attempt would be
made to remove stores during this pass.  AliasSetTracker would be
helpful as soon as I could get it to optionally keep all of its sets
"must alias" instead of downgrading them to "may alias" as soon as a
may-alias of an existing set showed up.  Then I'd use a "must alias"
tracker and a "may alias" tracker so I could quickly answer "what are
all of this pointer's MustAlias's?" and "what are all of this
pointer's MayAlias's?".

After such a pass runs, the loads that now get fed to memdep are
already resolved as values whenever they can be and don't have to be
traced again or cached separately.