[llvm-dev] [PM] I think that the new PM needs to learn about inter-analysis dependencies...

[Sean Silva via llvm-dev]

On Wed, Jul 13, 2016 at 12:34 AM, Chandler Carruth <chandlerc at gmail.com>
wrote:

> On Wed, Jul 13, 2016 at 12:25 AM Sean Silva <chisophugis at gmail.com> wrote:
>
>> On Tue, Jul 12, 2016 at 11:39 PM, Chandler Carruth <chandlerc at gmail.com>
>> wrote:
>>
>>> On Tue, Jul 12, 2016 at 11:34 PM Sean Silva <chisophugis at gmail.com>
>>> wrote:
>>>
>>>> On Tue, Jul 12, 2016 at 11:32 PM, Xinliang David Li <davidxl at google.com
>>>> > wrote:
>>>>
>>>>>
>>>>>
>>>>> On Tue, Jul 12, 2016 at 10:57 PM, Chandler Carruth <
>>>>> chandlerc at gmail.com> wrote:
>>>>>
>>>>>> Yea, this is a nasty problem.
>>>>>>
>>>>>> One important thing to understand is that this is specific to
>>>>>> analyses which hold references to other analyses. While this isn't unheard
>>>>>> of, it isn't as common as it could be. Still, definitely something we need
>>>>>> to address.
>>>>>>
>>>>>
>>>>> We can call this type of dependencies (holding references)
>>>>> hard-dependency. The soft dependency refers to the case where analysis 'A'
>>>>> depends on 'B' during computation, but does not need 'B' once it is
>>>>> computed.
>>>>>
>>>>> There are actually quite a few examples of hard-dependency case. For
>>>>> instance LoopAccessInfo, LazyValueInfo etc which hold references to other
>>>>> analyses.
>>>>>
>>>>> Problem involving hard-dependency is actually easier to detect, as it
>>>>> is usually a compile time problem. Issues involving soft dependencies are
>>>>> more subtle and can lead to wrong code gen.
>>>>>
>>>>
>>>> Did you mean to say that soft-dependency problems are easier to detect?
>>>> At least my intuition is that soft-dependency is easier because there is no
>>>> risk of dangling pointers to other analyses.
>>>>
>>>
>>> The issue is that the fact that there is *any* dependency isn't clear.
>>>
>>> However, I think the only real problem here are these "hard
>>> dependencies" (I don't really like that term though). For others, only an
>>> analysis that is *explicitly* preserved survives. So I'm not worried about
>>> the fact that people have to remember this.
>>>
>>> The question is how often there are cross-data-structure references.
>>> David mentions a few examples, and I'm sure there are more, but it isn't
>>> clear to me yet whether this is pervasive or occasional.
>>>
>>
>>
>> I just did a quick run-through of PassRegistry.def and this is what I
>> found:
>>
>> Module analyses: 0/5 hold pointers to other analyses
>> CallGraph: No pointers to other analyses.
>> LazyCallGraph: No pointers to other analyses.
>> ProfileSummaryAnalysis: No pointers to other analyses.
>> TargetLibraryAnalysis: No pointers to other analyses.
>> VerifierAnalysis: No pointers to other analyses.
>>
>> Module alias analyses: 1/1 keeps pointer to other analysis.
>> GlobalsAA: Result keeps pointer to TLI (this is a function analysis).
>>
>> Function analyses: 9/17 keep pointers to other analysis
>> AAManager: Its Result holds TLI pointer and pointers to individual AA
>> result objects.
>> AssumptionAnalysis: No pointers to other analyses.
>> BlockFrequencyAnalysis: Its Result holds pointers to LoopInfo and BPI.
>> BranchProbabilityAnalysis: Stores no pointers to other analyses. (uses
>> LoopInfo to "recalculate" though)
>> DominatorTreeAnalysis: Stores no pointers to other analyses.
>> PostDominatorTreeAnalysis: Stores no pointers to other analyses.
>> DemandedBitsAnalysis: Stores pointers to AssumptionCache and DominatorTree
>> DominanceFrontierAnalysis: Stores no pointers to other analyses.
>> (uses DominatorTreeAnalysis for "recalculate" though).
>> LoopInfo: Uses DominatorTreeAnalysis for "recalculate" but stores no
>> pointers.
>> LazyValueAnalysis: Stores pointers to AssumptionCache, TargetLibraryInfo,
>> DominatorTree.
>> DependenceAnalysis: Stores pointers to AliasAnalysis, ScalarEvolution,
>> LoopInfo
>> MemoryDependenceAnalysis: Stores pointers to AliasAnalysis,
>> AssumptionCache, TargetLibraryInfo, DominatorTree
>> MemorySSAAnalysis: Stores pointers to AliasAnalysis, DominatorTree
>> RegionInfoAnalysis: Stores pointers to DomTree, PostDomTree, DomFrontier
>> ScalarEvolutionAnalysis: Stores pointers to TargetLibraryInfo,
>> AssumptionCache, DominatorTree, LoopInfo
>> TargetLibraryAnalysis: Has no dependencies
>> TargetIRAnalysis: Has no dependencies.
>>
>> Function alias analyses: 3/5 keep pointers to other analyses
>> BasicAA: Keeps pointers to TargetLibraryInfo, AssumptionCache,
>> DominatorTree, LoopInfo
>> CFLAA: Keeps pointer to TargetLibraryInfo
>> SCEVAA: Keeps pointer to ScalarEvolution
>> ScopedNoAliasAA: No dependencies
>> TypeBasedAA: No dependencies
>>
>>
>> Total: 13/28 analyses (~50%) hold pointers to other analyses.
>> Of the 15/28 analyses that don't hold pointers, 12/15 simply have no
>> dependencies. Only 3/15 (BPI, LoopInfo, DominanceFrontier) have
>> dependencies that are used just for a "recalculate" step that retains no
>> pointers.
>> So I think it is fair to say that analyses which hold pointers to other
>> analyses is not an exceptional case. In fact, analyses that use other
>> analyses just for a "recalculate" step seems to be the exceptional case
>> (only 3/28 or about 10%)
>>
>
> Interesting!
>
> Most of these look like they hold a pointer to the root analysis as
> opposed to detailed objects *inside* the analysis?
>
> It might make sense to try to handle this very specific pattern in a
> special way of overriding the invalidate routines is too error prone.... We
> could try to make this work "automatically" but I'm worried this would be
> challenging to get right. Open to suggestions of course.
>
> Any other ideas about what would make sense to handle this?
>
> Does it make sense to override the invalidate routines now and iterate
> from there? I feel like you've done a lot of the research necessary for
> this already...
>

I'll keep pushing forward tomorrow with building test-suite successfully
using the new PM for the LTO pipeline (I was doing some unrelated LLD stuff
for most of today). It will be interesting to see how many `invalidate`
overrides will be needed to avoid these issues for just the LTO pipeline on
test-suite.

-- Sean Silva
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160713/a98a6fd0/attachment-0001.html>