[llvm-dev] RFC: [GlobalISel] Towards a generic MI combiner framework

Aditya Nandakumar via llvm-dev llvm-dev at lists.llvm.org
Fri Nov 10 14:04:45 PST 2017



> On Nov 10, 2017, at 10:19 AM, Hal Finkel via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> 
> On 11/10/2017 11:12 AM, Amara Emerson via llvm-dev wrote:
>> Hi everyone,
>> 
>> This RFC concerns the design and architecture of a generic machine instruction combiner/optimizer framework to be developed as part of the GISel pipeline. As we transition from correctness and reducing the fallback rate to SelectionDAG at -O0, we’re now starting to think about using GlobalISel with optimizations enabled. There are obviously many parts to this story as optimizations happen at various stages of the codegen pipeline. The focus of this RFC is the replacement of the equivalent of the DAGCombiner in SDAG land. Despite the focus on the DAGCombiner, since there aren’t perfect 1-1 mappings between SDAG and GlobalISel components, this may also include features that are currently implemented as part of the target lowerings, and tablegen isel patterns. As we’re starting from a blank slate, we have an opportunity here to think about what we might need from such a framework without the legacy cruft (although we still have the high performance bar to meet).
>> 
>> I want to poll the community about what future requirements we have for the GISel G_MI optimizer/combiner. The following are the general requirements we have so far:
>> 
>> It should have at least equivalent, but hopefully better runtime/compile time trade off than the DAGCombiner.
>> There needs to be flexibility in the design to allow targets to run subsets of the overall optimizer. For example, some targets may want to avoid trying to run certain types of optimizations like vector or FP combines if they’re either not applicable, or not worth the compile time.
>> Have a reasonably concise way to write most optimizations. Hand written C++ will always be an option, but there’s value in having easy to read and reason about descriptions of transforms.
>> 
>> These requirements aren’t set in stone nor complete, but using them as a starting point: a single monolithic “Generic MI combiner” component doesn’t look like the right approach. Our current thinking is that, like we’ve done with the Legalizer, the specific mechanics of the actual optimization should be separated into it’s own unit. This would allow the combines to be re-used at different stages of the pipeline according to target needs. Using the current situation with instcombine as an example, there is no way to explicitly pick and choose a specific subset of IC, it’s only available as a whole pass with all the costs that entails.
>> 
>> The reasoning behind req 3 is that there may be compile time savings available if we can describe in a declarative style the combines we want to do, like it’s currently possible with tablegen patterns. This hasn’t been proven out yet, but consider an alternative where we use the machine instruction equivalent of the IR/PatternMatch tooling which allows easy and expressive matching of IR sub-trees. A concern I have with using that as the main approach to writing combines is that it’s easy to add new matchers in an routine which re-computes information that’s previously been computed in previous match() attempts.
> 
> I share this concern.
> 
>> This form of back-tracking might be avoided if we can reason about a group of combines together automatically (or perhaps we could add caching capabilities to PatternMatch).
>> 
>> What would everyone else like to see from this?
> 
> The current DAGCombine, being constructed on top of SDAG, has a kind of built-in CSE and automatic DCE. How will things change, if they'll change, in this new model?
Hi Hal,

I suspect one option is to have a separate CSE pass, and the backends get to choose where exactly they plug in their pipeline. I think DCE should be part of the combine pass (and the legalizer is about to start doing that as well).
> 
> Thanks again,
> Hal
> 
>> 
>> Thanks,
>> Amara
>> 
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
> 
> -- 
> Hal Finkel
> Lead, Compiler Technology and Programming Languages
> Leadership Computing Facility
> Argonne National Laboratory
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20171110/b9cef47d/attachment-0001.html>


More information about the llvm-dev mailing list