[LLVMdev] Missed devirtualization opportunities

[Nick Lewycky]

Kenneth Uildriks wrote:
>> 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 have no idea how to make use of llvm.invariant to help 
devirtualization. If no use or other use case for them can be found, 
maybe they should be removed.

> 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.

Right, there's been talk of a "reverse memdep". Owen?

   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.

This is complex enough that I would need to think about it some more.

Nick