[llvm-dev] [RFC][LV][VPlan] Proposal for Outer Loop Vectorization Implementation Plan

[Saito, Hideki via llvm-dev]

>From http://lists.llvm.org/pipermail/llvm-dev/2017-December/119567.html

>>That sounds like an excellent idea! Any concrete ideas/plans how people could get involved, besides doing reviews?
>
>Let's talk about this in the RFC context. http://lists.llvm.org/pipermail/llvm-dev/2017-December/119523.html.
>Divergence Analysis work mentioned there is a good example.

One of the big things we are hoping to see people outside of our Intel team contributing is dependence analysis --- for outer
loop auto-vectorization (and most of that can also be used for auto-parallelization of outer level loops). The plan
outlined below aims for explicit vectorization, but we'd certainly want to hook this up for outer loop auto-vectorization.
Having sent out the second clean up patch (https://reviews.llvm.org/D41045), I'm currently looking at LoopVectorizationLegality class
and thinking about how to 1) make it more modular, 2) take it out of LoopVectorize.cpp, and 3) move it to Analysis directory (but not
necessarily a separate Analysis pass, yet). Part of the Legality is the dependence checking that needs to be upgraded to deal
with outer loops. Any interest in working in this area? It's not really dependent on the VPlan progress. Can be started right away.

Thanks,
Hideki

-----Original Message-----
From: Saito, Hideki 
Sent: Tuesday, December 05, 2017 5:09 PM
To: llvm-dev at lists.llvm.org; renato.golin at linaro.org; aemerson at apple.com; mkuper at google.com; mssimpso at codeaurora.org; Simon Moll <moll at cs.uni-saarland.de>; hfinkel at anl.gov
Cc: Saito, Hideki <hideki.saito at intel.com>; Rapaport, Gil <gil.rapaport at intel.com>; Zaks, Ayal <ayal.zaks at intel.com>; Kreitzer, David L <david.l.kreitzer at intel.com>
Subject: [RFC][LV][VPlan] Proposal for Outer Loop Vectorization Implementation Plan


Proposal for Outer Loop Vectorization Implementation Plan =============================================

=====
Goal:
=====
Extending Loop Vectorizer (LV) such that it can handle outer loops, via VPlan infrastructure enhancements.
Understand the trade-offs in trying to make concurrent progress with moving remaining inner loop vectorization functionality to VPlan infrastructure
 
===========
Background:
===========
This is related to VPlan infrastructure project we started a while back, a project to extend the (inner loop vectorization focused) Loop Vectorizer to support outer loop vectorization.
VPlan is the vectorization planner that records the decisions and candidate directions to pursue in order to drive cost modeling and vector code generation. When it is fully integrated into LV (i.e., at the end of this big project), VPlan will use a Hierarchical-CFG (HCFG) and transform it starting from the abstraction of the input IR to reflect current vectorization decisions being made. The HCFG eventually becomes the abstraction of the output IR, and the vector code generation is driven by this abstract representation.
 
This is a follow up of the previous RFCs and LLVM Developer Conference presentations: 
          http://lists.llvm.org/pipermail/llvm-dev/2016-September/105057.html (RFC: Extending LV to vectorize outerloops)
          http://lists.llvm.org/pipermail/llvm-dev/2017-February/110159.html (RFC: Introducing VPlan to model the vectorized code and drive its transformation)
          https://www.youtube.com/watch?v=XXAvdUwO7kQ (Extending LoopVectorizer: OpenMP4.5 SIMD and Outer Loop Auto-Vectorization)
          https://www.youtube.com/watch?v=IqzJRs6tb7Y (Introducing VPlan to the LoopVectorizer)
          https://www.youtube.com/watch?v=BjBSJFzYDVk (Vectorizing Loops with VPlan - Current State and Next Steps) Please also refer to the separately sent out status update http://lists.llvm.org/pipermail/llvm-dev/2017-December/119522.html.
.
 
So far, two big patches related to VPlan implementation have been committed.
https://reviews.llvm.org/D28975 by Gil Rapaport. (Introducing VPlan to model the vectorized code and drive its transformation)
     Has been broken down to a series of smaller patches and went in. The last (re)commit of the series is
     https://reviews.llvm.org/rL311849
https://reviews.llvm.org/D38676 by Gil Rapaport. (Modeling masking in VPlan, introducing VPInstructions)
     This is also broken down to a series of smaller patches to facilitate the review.
     Committed as https://reviews.llvm.org/rL318645
 
With the first patch, we introduced the concept of VPlan to LV and started explicitly recording decisions like interleave memory access optimization and serialization.
With the second patch, we also introduced the concept of VPInstruction (to model newly introduced use-def) and started explicitly modeling masking and mask manipulations.
 
So far, work in this area has been mostly restricted to refactoring of Loop Vectorizer's existing functionality with several remaining areas of LV that still need to be refactored into the new VPlan based representation. The following is a non-exhaustive list of areas that need to be worked on and gives an idea of the amount of remaining work.
* Predication
* Cost model
* Remainder Loop
* Runtime Guards
* External Users
* Reduction Epilog
* Interleave Grouping
* Sink Scalar Operands
 
While it is important to keep refactoring the above mentioned items such that entire LV becomes fully VPlan based (which completes the transition into VPlan infrastructure), we are aware that there is also a need to make progress in outer loop vectorization. Function vectorization via VecClone pass (https://reviews.llvm.org/D22792) also depends on the progress of outer loop vectorization.
 
==============
Proposed Plan:
==============
Instead of waiting for most of the above mentioned refactoring to finish before working on outer loop vectorization, we believe it serves the best interest of the community if we start making concurrent progress on continued refactoring effort and outer loop vectorization effort.
To implement outer loop vectorization in incremental steps, we propose adding new code paths that would be exercised initially for only outer loop vectorization cases. This would ensure that the changes are NFC for innermost loop vectorization cases until we (slowly) transition them to also go through these new code paths.
 
Given that LV never had the ability to vectorize outer level loops, letting outer loop vectorization take slightly different code paths, compared to innermost loop vectorization, won't cause any issues in innermost loop vectorization. The new paths are what inner loop vectorization will eventually go through (i.e., post-refactoring), after the kinks are worked out so that doing so will not regress any of the existing functionality and performance. Having the new code paths exposed early would encourage more community participating in maturing the new code paths, makes it clearer what still needs to be moved over to VPlan infrastructure, and hopefully also encourage more community participation in the remaining refactoring effort.
 
======================
Proposed Patch Series:
======================
There will be a lot of new development before declaring "feature complete". As such, we propose to break it into five or more series of patches ---- starting from vectorizing trivial outer loops. Along the way, we expect to include NFC patches to make LV more modular, in order to keep LoopVectorize.cpp file size from growing too much.
 
  Patch Series #1
  ---------------
    Trivial outer loop vectorization
    * Inner loops are trivially lock-step among all vector elements
    * No other branches inside the outer loop (to avoid touching divergence analysis in this series)
    This should require
    1) inner loop uniformity check (SCEV based invariance will do) --- the first small patch https://reviews.llvm.org/D40874 is a subset of this.
    2) VPlan construction
    3) Vector code generation (w/ unmodified uniform inner control flow) from VPlan
 
    for (i=0;i<N;i++){ // vectorize here
      // no branches here
      for (j=0;j<loop_invariant_value; j++){
        // no branches here
      }
      // no branches here
    }
 
  Patch Series #2
  ---------------
    Simple outer loop vectorization
    * Inner loops are still trivially lock-step among all vector elements
    * Non-loop branches are blindly assumed as divergent
    This should require
    1) Patch Series #1
    2) Predication analysis and masking on VPlan
    3) Vector code generation support for masking
 
    for (i=0;i<N;i++){ // vectorize here
      // branches may be here
      for (j=0;j<loop_invariant_value; j++){ // unconditional w.r.t. i-loop
        // branches may be here
      }
      // branches may be here
    }
 
  Patch Series #3
  ---------------
    Better simple outer loop vectorization
    * Inner loops are still trivially lock-step among all vector elements
    * Non-loop branches may be uniform/non-uniform
    This should require
    1) Patch Series #1, #2
    2) We first use SCEV invariance for uniformity analysis.
    3) Vector code generation support for uniform forward branches
    4) We are working with Simon Moll (U-Saarland) to improve uniformity analysis (https://www.youtube.com/watch?v=svMEphbFukw&feature=youtu.be).
       Not a hard dependency, but improved analysis is good for performance.
 
    Same kind of loop as Patch Series #2, but uniform branches are optimized (i.e., less masking). 
 
  Patch Series #4
  ---------------
    Less simple outer loop vectorization
    * Inner loops may not be lock-step among all vector elements, but single-entry/single-exit
    This should require
    1) Patch Series #1, #2, #3
    2) VPlan to VPlan transformation to make inner loop lock-step. After the transform, the VPlan should look like the ones #3 can handle.
       We'll look into porting code from U-Saarland RV project, which performs this transformation in IR to IR manner.
 
    for (i=0;i<N;i++){ // vectorize here
      // branches may be here
      if (cond(i)) {
        // branches may be here
        while (cond1(i)){
          // branches may be here
        }
        // branches may be here
      }
      // branch may be here
    }
 
  Patch Series #5
  ---------------
    Outer loop vectorization "Feature Complete"
    * Inner loops must be redusible, allows multiple exits.
    This should require
    1) Patch Series #1, #2, #3, #4
    2) VPlan to VPlan transformation to make inner loop lock-step.
    3) Vector code generation support for inner loop with multiple exits
 
    for (i=0;i<N;i++){ // vectorize here
      // branches may be here
      if (cond(1)) {
        // branches may be here
        while (cond1(i)){
          .
          if (cond2) break;
          .
          if (cond3) break;
          .
        }
        // branches may be here
      }
      // branch may be here
    }
 
============================
Future Work beyond this RFC:
============================
  * Outer loop auto-vectorization legality analysis
  * Outer loop auto-vectorization cost model
  * Cost model to compute VF/UF for explicit outer loop vectorization (when not specified)
  * (lower in priority) Irrducible inner loop handling (VPlan to VPlan transform to make inner loops reducible. After the transform, the VPlan should look like the ones #5 can handle.)
 
===========
Trade-Offs:
===========
The new code path also has the ability to perform innermost loop vectorization (as a trivial subset of outer loop vectorization if we want to exercise that path for such purposes). It's good to be able to compare, side-by-side, what existing code path does and what new path does so that we can incrementally build up confidence/experience levels on the new code path. For the time being, however, that can be seen as extra maintenance needs. Instead of trying to do this on the trunk, we can do the same thing on the side, using github, until "outer loop vectorization feature" becomes mature enough. Amount of code review required, to get into the trunk, most likely would be comparable.
 
========
Summary:
========
Outer loop vectorization feature implementation plan is presented. We think concurrent progress has a good enough chance of expediting overall transition of LV into the new infrastructure while benefiting from delivering new functionality to those in need sooner, with wider community participation in the overall development.
 
Thanks,
Hideki Saito