[LLVMdev] LICM/store-aliasing of global loads

[Stefanus Du Toit]

On 22-Jul-08, at 1:22 PM, Dan Gohman wrote:
> On Jul 21, 2008, at 3:51 PM, Stefanus Du Toit wrote:
>> - build a custom alias analysis pass that indicates that these loads
>> never alias with any stores in a given function
>> - declare these globals as external constants within the module
>
> If you can convince yourself that no interprocedural optimization
> will ever get in trouble, the second approach here sounds reasonable
> and simpler. But if the values aren't really constant, it may be
> difficult to be sure.

Yes, we definitely can be sure.

> Building a custom alias analysis is reasonable too.


Right, and is helpful for other reasons.

> One way to fix this would be to have AliasSetTracker pretend that
> pointers to constant memory never alias anything. That's a little
> sneaky though, so offhand I think an approach such as what's in
> your patch is better.

That does seem a little... unethical? :)

At the very least it seems this should still return must-alias results  
correctly, otherwise this could hurt optimizations (I assume).

I was going to suggest that at least getModRefInfo should handle this  
for stores, but it looks like it already does.

>> If I apply the patch found further down, LICM moves the loads out (as
>> expected), but of course this is a fairly specific fix.
>
> Slightly better than checking for GlobalVariabls directly
> is to call the AliasAnalysis' pointsToConstantMemory method.
> BasicAliasAnalysis' implementation of that does exactly the same  
> thing,
> checking for constant GlobalVariables, but it would allow alias
> analyses to do more sophisticated things. Could you submit a patch
> for this?

Ah, I was going to ask if there was such a method.

I'll submit a patch once I'm done testing it.

>> What's the right way to handle this? Should Basic AA handle this  
>> case?
>> Will the RA be aware that it can remat these loads or do I need to do
>> something else to allow it to know this? Will the scheduler be aware
>> that it can reorder them?
>
> It would be nice to have an AA that's smart enough to do things
> like this. However for now, having code use
> AliasAnalysis::pointsToConstantMemory should cover many of the
> obvious cases.

OK, are there any other obvious places this should go? I expect  
optimizations that use getModRefInfo on stores rather than alias sets  
won't need any changes.

>> Obviously I can also move the loads to the entry block of the
>> function, but that does not address the RA/scheduling issues and is
>> difficult to do in general due to some additional semantics in our
>> frontend.
>
> In the scheduling department, LLVM is not yet using any alias
> information. You can experiment with the -combiner-alias-analysis and
> -combiner-global-alias-analysis options, which use AliasAnalysis
> queries and do a pretty good job, but aren't very efficient and not
> very widely tested. Ideally we'd like to do something better here.

Could you expand on this a bit (or point me to past discussions/...)?  
This can be pretty important on architectures like Cell SPU.

> For register allocation, LLVM currently has some simple hooks which
> individual targets use to specify which loads are rematerializable.
> See isReallyTriviallyReMaterializable. Currently this code is all
> target-specific and doesn't use AliasAnalysis information, but I
> think it could be reasonably generalized to use the new
> MachineMemOperand information to be less target-dependent and to
> make at least AliasAnalysis::pointsToConstantMemory queries.

OK, I will have a look. I assume the reference to M_REMATERIALIZABLE  
in the comment for it should really be TID::Rematerializable? I also  
noticed that the documentation for  
TargetInstrDesc::isRematerializable() says "This flag is deprecated,  
please don't use it anymore" -- could you explain what replaces it?

Stefanus

--
Stefanus Du Toit <stefanus.dutoit at rapidmind.com>
   RapidMind Inc.
   phone: +1 519 885 5455 x116 -- fax: +1 519 885 1463