[llvm-dev] [RFC] Goals for VPlan-based cost modelling

[Renato Golin via llvm-dev]

On Mon, 2 Nov 2020 at 09:53, Anna Sophia Welker <
s9aawelk at stud.uni-saarland.de> wrote:

> Yes, that's a big issue to be solved. I do like the idea from Florians
> reply, basically encoding an instruction's environment in the
> VPInstruction that is generated and make it such that target-specific
> cost components would overwrite the cost calculations for the general
> class if they can be treated in a special way by the architecture.
>

Merging instructions as a single VPInst is a good target-specific
optimisation to do to simplify the cost model, especially if the target can
lower them into a single instruction. But I worry that we'll have to create
too many VPInst variants for each platform, where for the cost model, it
doesn't usually matter what instructions are inside, other than their cost.

In the example of a "zext (load)", instead of having two VPInsts, you have
one, and the hardware will have to have a cost of zext, load and zext-load.
This may be enough, or it may lead to a combinatorial explosion. If it
does, something leaner like adding a check on Zext for operands, see that
it's a load, and return zero. This also keeps the logic inside the
instruction itself, so it's easy to understand the code.

I'm honestly not sure which approach is best. Perhaps a mix of both?
Florian is working on this, so I'd trust his judgement more than mine.

But I'd keep in mind that the goals of the cost model need to account for
patterns that we don't necessarily know about now.

Maybe there are cases that are more
> complex, that e.g. merge or depend on far more then two instructions, in
> which case the generation of the right VPInstructions might become
> tricky - especially if there are multiple possible 'merge patterns' (for
> one or different architectures) that are overlapping, which would
> require to generate alternative VPlans, whose number for long loops with
> many special cases might grow exponentially to cover all possible
> combinations.
>

Exactly my thinking...

Yes, there needs to be a good way to say things like that, and
> preferrably 'good' should not only mean efficient, but also easy to
> understand, maintain and extend - but that's just me dreaming :)
>

Agreed!

Are you thinking of a concrete example when mentioning those shuffles?
> Because concrete examples would really help me a lot when thinking
> further about this - if I decide to do this as a thesis, I might have to
> constrain the actual implementation to (a subset of instructions for) a
> single architecture, but for thinking about the issue itself any
> concrete examples for any architecture would be a great help!
>

Unfortunately, the last time I worked on this was many years ago. There
should be examples on the vectoriser tests for each platform.

I'm thinking about special instructions in each arch that resolve into a
complicated set of LLVM IR. For example strides loads/stores in Arm
(LDn/STn), gather-scatter in AVX/SVE, vector predication, reduction, etc.

Some of those things have gained intrinsics since the last time I worked
with the vectoriser (ex. reduction, which was particularly messy), and that
would make the cost model a lot simpler to implement.

Hm, I hadn't yet gotten as far as how to use it, but you're right of
> course - that will be another challenge.


Indeed. One problem at a time. :)

But as you help design the cost model, we need to make sure its structure
is the most sensible (efficient, simple to read, easy to understand and
extend) so that others can make use of it (and extend later), as they
implement the VPlan transformations.

I didn't mean you'd have to do it all, just to have it in mind how it could
be used, perhaps even write (in pseudo-code) a few examples from each
use-case in VPlan, to guide you on the cost model design. This would also
look nice in your thesis introduction, to guide the reader into why we need
your work in the first place and why your design is what it is.

I know that there are many
> things being planned and on the way for VPlan, but I'll willingly admit
> that I am currently still having some trouble gaining an overview of
> what is there, what is not, and what might be on its way. It's simply
> hard and takes a lot of time to find documentation for all the new
> things, but I'm sure I'll get there.
>

It's still very much work in progress, and a lot of work and a lot of
progress, so it's hard to keep up with what's done or in flight.

Initially it looks daunting, but soon enough you'll get the hang of it,
don't worry. When in doubt, ask the list (or IRC). There are enough people
that can help you around.

cheers,
--renato
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20201102/f5cf6712/attachment.html>