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

Hal Finkel via llvm-dev llvm-dev at lists.llvm.org
Fri Nov 10 10:19:47 PST 2017

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:
>  1. It should have at least equivalent, but hopefully better
>     runtime/compile time trade off than the DAGCombiner.
>  2. 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.
>  3. 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?

Thanks again,

> Thanks,
> Amara
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://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/20171110/178c7e00/attachment.html>

More information about the llvm-dev mailing list