[LLVMdev] alias set collapse and LICM

[Andrew Trick]

> On Jun 17, 2015, at 3:57 PM, Philip Reames <listmail at philipreames.com> wrote:
> 
> 
> 
> On 06/12/2015 06:00 PM, Andrew Trick wrote:
>>> On Jun 12, 2015, at 5:23 PM, Philip Reames <listmail at philipreames.com> wrote:
>>> 
>>> On 06/12/2015 04:14 PM, Andrew Trick wrote:
>>>>> On Jun 12, 2015, at 2:52 PM, Philip Reames <listmail at philipreames.com> wrote:
>>>>> 
>>>>> For upstream, I now know of four possible implementation strategies:
>>>>> 
>>>>> Option 1 - Resort to pairwise modref queries for sufficiently small loops.  This has the advantage of being already implemented and easy to upstream, but would introduce a capped N^2 algorithm and thus a performance cliff.  It might be worth upstreaming this with the threshold defaulted to 0 (i.e. nop) just as a testing mechanism for identifying places AST's imprecision is hurting us.
>>>>> 
>>>>> Option 2 - As a variant of option 1, we can keep track of potentially clobbering instructions seen during a single walk of the loop.  With this, the above N^2 algorithm becomes #L*#S, and we can easily bound the maximum number of clobbering instructions we track.  I think this is actually a reasonable compromise and is worth considering.  This gives us fully precise aliasing for most loops within LICM at reasonable cost.
>>>>> 
>>>>> Option 3 - We can track readonly calls separately within AST.  This wouldn't change the inherent purpose of AST (i.e. it would still be about transitive aliasing), but would enable more precise results in the specific case we care about.  This only helps the readonly call case and does not help with general aliasing collapse issue.  It also requires every consumer of the AST interface to be updated to explicit check the "alias all" set.  (Note: This could help other "unknown instruction" cases as well as readonly calls.  It just doesn't solve the imprecise aliasing transitivity for known instructions.)
>>>>> 
>>>>> Option 4 - We can split AST into two sets of alias sets.  One set of set is based on aliasing ref behaviour, the other on mod behaviour. The rules for adding to the first set of sets are the existing AST rules.  A load would only be added to an mod based set if a store within the set aliased it directly.  We would still merge all of sets that a load belong to.  The difference is that a load would not be considered to belong to a set unless a store within that set aliases it, not just another load.  With LICM, we'd use the mod-set for hoisting of loads, and the ref-set for sinking of stores.  This is a fairly involved change.
>>>>> 
>>>>> My mild preference would be for option 2, followed by 4, then 1, then 3.  What do others think?  I'm willing to implement any of 1, 2, and likely 3.  Option 4 is likely more work than I can commit to given that the symptom biting me is now fixed locally.
>>>> Makes sense to me. I think Option 3 is also more work than anyone wants to take on. I suggested it because what you’re calling a special case is really the common and interesting case, and intuitively AST is almost useless at tracking reads without handling unknown readers. But looking at where AST is used, I don’t think it makes sense for it to track reads anyway.
>>> I'm having a real hard time parsing the paragraph above.  Could you restate?
>> If AST tracker is being used to track memory reads, then it should set aside unknown reads in a special “alias-all" set rather than merging all sets. Reading from unknown memory is a common case, not a special case.
>> 
>> However, most clients would not do anything with this information other than check that the alias-all set only contains reads (!isMod). So I think a better solution to this problem would be to restructure the client so that AliasSetTracker only tracks writes (Mods), not reads, and use a different approach to finding aliasing loads.
> I think this means you end up being in support of something like my option 4 above.  Whether we call the aliasing load finder AST or not is somewhat immaterial.  The important point is in one case (load hoisting) we only want information about mods and in the other (store sinking) we need information about both.

Yes. Regardless of the approach, tracking readonly calls in the alias tracker is a bad idea. Checking for their existence is sufficient.
Andy

>>>> For sinking, I think you could give up on the pairwise alias check after the first unsuccessful attempt in each AliasSet (tracking mods only) without losing useful precision.
>>> Sorry, I should have been more clear.  I was only planning on applying the pair wise aliasing to load hoisting.  The conservative aliasing involved in store sinking is much less problematic.  For example, if there's a readonly call in the loop, it wouldn't be legal to sink a store.
>> That’s probably fine. This is what I was thinking, without really considering all the alternatives…
>> 
>> For hoisting: If the AliasTracker tracks stores, then you don’t need to do pairwise aliasing for load hoisting. You could just check if the load’s pointer already has an AliasSet.
> Assuming you have the mod only form of the alias set tracker mentioned above, then yes.  We don't have that today.
>> For sinking: If the loop contains readonly calls, don’t sink. Using an AliasSetTracker to tell you this is absurd. Otherwise, you could pairwise check the store against all the loads for aliasing. You will either bail-quickly or do useful optimization. I imagine you only need to bail-out once per store AliasSet.
> In the existing code, we have to generate the AST anyway.  Thus reusing it is not absurd.  :)  However, if we'd switched to alias set only tracking mods, then yes, we could find something better for sinking.
>> 
>> Andy
>> 
>>> Philip
>> 
>> 
>