[llvm-dev] LoopVectorizer: Should the cost-model be used for legalisation?

[Vineet Kumar via llvm-dev]

Hi,

IIUC, for option 1, unless the legalizer and the cost-model follow the 
same logic to determine the feasibility of scalable-vectorization, it 
seems inaccurate to assert that if something is legal it must have a 
valid cost. But if that assertion is relaxed, then as you mentioned in 
another reply, it would be a  de facto choice for option 2. If we don't 
relax this assertion then for it to be accurate legalizer and cost-model 
will both do redundant work. Also, IIRC, an invalid cost also models a 
too-expensive-to-be-useful operation but that doesn't really imply 
illegal operation.

I am not sure if this makes sense, but with option 2, since VPlans are 
not discarded upfront there is a chance that a transofrmation on VPlan 
might actually make it feasible.

I didn't think deeply about this so I might be missing some obvious and 
key facts. Please correct me if I am wrong.


Best,

Vineet


On 2021-06-10 10:50 p.m., Sander De Smalen via llvm-dev wrote:
> Hi,
>
> Last year we added the InstructionCost class which adds the ability to
> represent that an operation cannot be costed, i.e. operations that cannot
> be expanded by the code-generator will have an invalid cost.
>
> We started using this information in the Loop Vectorizer for scalable
> auto-vectorization. The LV has a legality- and a cost-model stage, which are
> conceptually separate concepts with different purposes. But with the
> introduction of having valid/invalid costs it's more inviting to use the
> cost-model as 'legalisation', which leads us to the following question:
>
>     Should we be using the cost-model to do legalisation?
>
> 'Legalisation' in this context means asking the question beforehand if the
> code-generator can handle the IR emitted from the LV. Examples of
> operations that need such legalisation are predicated divides (at least
> until we can use the llvm.vp intrinsics), or intrinsic calls that have no
> scalable-vector equivalent. For fixed-width vectors this legalisation issue
> is mostly moot, since operations on fixed-width vectors can be scalarised.
> For scalable vectors this is neither supported nor feasible [1].
>
> This means there's the option to do one of two things:
> 

> [Option 1]
>
> Add checks to the LV legalisation to see if scalable-vectorisation is
> feasible. If so, assert the cost must be valid. Otherwise discard scalable
> VFs as possible candidates.
>   * This has the benefit that the compiler can avoid
>     calculating/considering VPlans that we know cannot be costed.
>   * Legalisation and cost-model keep each other in check. If something
>     cannot be costed then either the cost-model or legalisation was
>     incomplete.
>
>
> [Option 2]
>
> Leave the question about legalisation to the CostModel, i.e. if the
> CostModel says that <operation> for `VF=vscale x N` is Invalid, then avoid
> selecting that VF.
>   * This has the benefit that we don't need to do work up-front to
>     discard scalable VFs, keeping the LV design simpler.
>   * This makes gaps in the cost-model more difficult to spot.
>
> Note that it's not useful to combine Option 1 and Option 2, because having
> two ways to choose from takes away the need to do legalisation beforehand,
> and so that's basically a choice for Option 2.
>
> Both approaches lead to the same end-result, but we currently have a few
> patches in flight that have taken Option 1, and this led to some questions
> about the approach from both Florian and David Green. So we're looking to
> reach to a consensus and decision on what way to move forward.
>
> I've tentatively added this as a topic to the agenda of the upcoming LLVM
> SVE/Scalable Vector Sync-up meeting next Tuesday (June 15th, [2]) as an
> opportunity to discuss this more freely if we can get enough people who
> actively work on the LV together in that meeting (like Florian and David,
> although please forward to anyone else who might have input on this).
>
> Thanks,
>
> Sander
>
>
> [1] Expanding the vector operation into a scalarisation loop is currently
>      not supported. It could be done, but we have done extensive
>      experimentation with loops that handle each element of a scalable
>      vector sequentially, but this has never proved beneficial, even when
>      using special instructions to efficiently increment the predicate
>      vector. I doubt this will be any different for other scalable vector
>      architectures, because of the loop control overhead. Also the
>      insertion/extraction of elements from a scalable vector is unlikely to
>      be as cheap as for fixed-width vectors.
>
> [2] https://docs.google.com/document/d/1UPH2Hzou5RgGT8XfO39OmVXKEibWPfdYLELSaHr3xzo/edit?usp=sharing
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

http://bsc.es/disclaimer