[llvm-dev] Writing loop transformations on the right representation is more productive (original) (raw)

Hal Finkel via llvm-dev llvm-dev at lists.llvm.org
Wed Feb 5 16:51:40 PST 2020

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>

More information about the llvm-dev mailing list