[llvm-dev] Writing loop transformations on the right representation is more productive

[Hal Finkel via llvm-dev]

On 2/5/20 6:13 PM, Chris Lattner via llvm-dev wrote:
>
>
>> On Feb 2, 2020, at 10:35 PM, Michael Kruse via llvm-dev 
>> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>>
>>>
>>> That's actually not how I read it. Red/green trees was *one* of the 
>>> nine items you mentioned in your list and this didn't come out as 
>>> the central idea in your opening paras, but let's go with this now 
>>> that it's clearer to me.
>>
>> Indeed, red/green trees (or DAGs) are one one of the ideas to improve
>> loop optimizations, but does justify its use by itself. They happen to
>> be effectively necessary for others in the list (e.g. versioning,
>> profitiability heuristic by cost function, etc...) and the reason why
>> I think the same cannot be done with MLIR. In hindsight, I could have
>> pointed this out more in the original RFC. Note that a hierarchical
>> representation was not an explicit feature in the list.
>>
>> To convince me that MLIR is the better IR for loop optimizations,
>> might show that each of the features enabled by cheap subtree reuse
>> can also be done sufficiently efficient and easily on MLIR (or that a
>> feature is not what would actually would want).
>
> Hi Michael,
>
> If I understand your claims, you are claiming both that red/green 
> trees are essential for a loop optimizer, and that this essential 
> nature “justifies” the cost of reinventing an entire compiler 
> infrastructure is lower than the benefit of using (e.g.) MLIR to do 
> this.  I haven’t seen evidence of either point:


Michael and I have discussed this offilne, and I think that more 
quantitative information here would be helpful. One phrasing might be: 
For a reasonable test suite of programs, for the loops we might 
optimize, how many different loop-nest variants do we need to represent 
for costing purposes (also note that, depending on profiling information 
and/or heuristics, we may need to cost at multiple trip-count values)? 
Given that, what is the relative cost of creating deep copies of the 
loop nests and transforming them vs. the cost of using a red/green tree? 
Does that cost seem significant?

We don't want to invest significant effort into a infrastructure that we 
know ahead of time won't scale sufficiently.


> lots of loop optimizers exist that don’t use red/green trees.


I've worked with many compilers, some from vendors known for having 
strong loop optimizers, and none of them would meet our goals for 
performance, robustness, and modeling accuracy (e.g., not regressing 
performance in many cases). Our goal here is to significantly improve on 
the state of the art.


>
> Furthermore, my experience is that specialized IRs never get the 
> investment in (e.g.). testing, location propagation for debugging 
> optimized code, textual round tripping, pass management, and the 
> multitude of other things that are required for a world class compiler 
> implementation.


I agree, but I think that these are well-known requirements within this 
ecosystem. What this means also depends on context (it might be more 
helpful to think of this more like SCEV than like a custom IR).

  -Hal


>
> -Chris
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200205/8da9bd11/attachment.html>