A pass that performs loop fusion on a StructuredSDFG.
Though mostly between Maps at this point.
Current impl. walks the SDFG in execution order with a sliding window (of 3). It can only fuse loops in the same sequence and at most with 1 independent block in between them and it does not retry past fused loops other then using the result of the last fusion as start of the next (which works for simple chains that always fuse forward)
The pass builds a FusionLoopCandidate cache at the start and then maintains all the data (assumptions, indvars, arguments) across modifications
The core function is in LoopFusionHandler::match, which gets called for candidate pairs. It then tries
- fusion by-domain
- can fuse intermediate levels of loops (that contain further, arbitrary loops)
- checks iteration domain for exact equality for all levels that will be fused across (only supported for "map-stacks", which are perfectly nested & parallel)
- checks for overlapping indirect memory usages (can fuse if there is no overlap at all, just no conflicts)
- checks the subsets on all overlapping usages to match exactly
- further nested loops indvars are represented by their iteration bounds, stepsize and nesting level for those exact matches
- fusion by-access via MapFusionByAccessWorker
- if the domain or subset checks fail, we proceed to the more complex case, that collects every access and solves for all reads being covered by matching writes.
- this can fuse only innermost loops with restrictive content, but can handle changes in iteration domain
- when the domains are not equal, it needs to copy one loop and replaces reads with the direct results of the productions, elliding the indirect memory accesses
- when the domains are equal, it keeps indirect accesses in same as by-domain (so the fused loop is a full replacement for both source loops), leaving the RedundantLoadElimination and cleanup of superfluous accesses for other passes
- by-access is currently restricted to fusing single-block producers into a larger consumer and specific reduction patterns
Either way needs to rely only on the data cached in the FusionLoopCandidate and LoopAnalysis as only those are kept up-to-date. After every change, LoopAnalysis and cached data update... functions need to be called to maintain the cached data.
Eventually, this should become a Dataflow-based pass, that will fixpoint iterate, can fuse loops that are further apart and can prioritize the order of fusions other then greedy, forward-only. It was designed such that the match() can still be called in that case
1.15.0