Differential D32530
[SVE][IR] Scalable Vector IR Type Authored by huntergr on Apr 26 2017, 4:12 AM.
Details
See the latest version of the RFC here: http://lists.llvm.org/pipermail/llvm-dev/2018-July/124396.html
Diff Detail
Event TimelineThere are a very large number of changes, so older changes are hidden. Show Older Changes
Comment Actions I think this is a coherent set of changes. Given the current top of trunk, this expands support from just assembly/disassembly of machine instructions to include LLVM IR, right? Such being the case, I think this patch should go in. I have some ideas on how to structure passes so SV IR supporting optimizations can be added incrementally. If anyone thinks such a proposal would help, let me know. Comment Actions I think there is one more thing we still have to do. Does scalable vector type apply to all Instructions where non-scalable vector is allowed? If the answer is no, we need to identify which ones are not allowed to take scalable vector type operand/result. Some of the Instructions are not plain element-wise operation. Do we have agreed upon semantics for all those that are allowed? If we are allowing just element-wise Instructions, we should explicitly say that in LangRef, warn at LLVM-DEV mailing list that new scalable vector types are coming, wait a little to let last minute screams to happen, assure them by saying scalable vector on element-wise Instructions won't cause any mess beyond non-scalable vector, and then commit. This would be the quickest route, and it still enables other interesting follow-up patches to be reviewed/committed. I think we are ready enough to do this if we choose to take this route. If we are going for more than element-wise Instructions, we need to have well defined and agreed semantics for each of those, and that should be part of the LangRef for each such Instruction. We can certainly let element-wise stuff to go in first and then extend to non-element-wise stuff later. Any thoughts in this regard? Comment Actions Agreed.
Same for intrinsics. If any of the vector ones apply to scalable vectors (ex. reduce), it needs to be documented.
Precisely, we should go in baby-steps, with each step making sure we don't touch/break *anything* that isn't scalable, updating LangRef as we go. Doing a single review on everything would be painful and counter-productive. Comment Actions I don't recall this being an issue, but I agree, if there are instructions that currently take vector types that don't take scalable vectors, that certainly needs to be documented.
I think that there's been plenty of traffic on this subject on llvm-dev. We do send warnings for potentially-downstream-disruptive changes, as a general best practice. I'm not really sure if this falls into this category, but I'm sure a note to llvm-dev will be sent to let everyone know when this lands, if nothing else, as an FYI to review other related patches.
FWIW, I took a quick look through the intrinsics and nothing jumped out at me as an intrinsic that currently has vector types on its interface that shouldn't take scalable vectors. So, if there things which don't work, we should certainly note that.
We should indeed review patches in small/medium-sized units (so long as the changes are testable). Comment Actions The main difference is for 'shufflevector'. For a splat it's simple, since you just use a zeroinitializer mask. For anything else, though, you currently need a constant vector with immediate values; this obviously won't work if you don't know how many elements there are. Downstream, we solve this by allowing shufflevector masks to be ConstantExprs, and then using 'vscale' and 'stepvector' as symbolic Constant nodes. With those and a few arithmetic and logical ops, we can synthesize the usual set of shuffles (reverse, top/bottom half, odd/even, interleaves, zips, etc). Would also work for fixed-length vectors. There's been some pushback on introducing them as symbolic constants though, and the initial demo patch set has them as intrinsics. So if we wanted to keep them as intrinsics for now, I think we have one of three options:
The discussion at the EuroLLVM roundtable was leaning towards option 1, with an action on me to provide a set of canonical shuffle examples using vscale and stepvector for community consideration. Comment Actions Given the current state, this is the easiest path.
This warrants a larger discussion, which would hinder the current progress. Comment Actions I agree, although this is an important part of the model, so we should start having this discussion in parallel (sooner rather than later). I had been under the impression that a set of intrinsics were being proposed for this, but extending shufflevector is also an option worth considering. If these are first-class types, then having first-class instruction support is probably the right path. This deserves it's own RFC.
I agree. We should have a separate RFC on this. Comment Actions We need to clarify on insertelement/extractelement. Maybe already done in some other patches, but that clarification should be part of this patch. Going with length of val being "scalable * n", if there is an optimization that takes advantages of poison value being returned by evaluating "idx >= n" at compile time, we need to disable that for scalable vector. Also, if any verifier is checking whether constant idx value is less than n, we need to disable that for scalable vector. Comment Actions That's pretty much what LLVM-VP is about: https://reviews.llvm.org/D57504 We are proposing compress/expand and lane shift as intrinsics. IMHO, the redesigned reduction intrinsics should go there as well (https://reviews.llvm.org/D60261 and/or https://reviews.llvm.org/D60262).
Even if shuffle masks don't need to be constants anymore, it will be awkward to encode compress/expand without additional intrinsics (you would need a prefix sum vector over the mask bits or similar).
+1 Comment Actions
I am not sure how it could be anything but n. If you don't know how long the vector is, you can't correctly generate an index beyond n. I assume for vectors of length > n one would have to use shufflevector or something similar (using vscale and stepvector as Graham mentioned) to get the elements you want to the lower n positions. Either way, the semantics and any restrictions certainly need to be documented.
If the index is still restricted by n then this shouldn't be an issue.
Comment Actions But you know at runtime... there has to be a way to determine, at runtime, vscale. And the index doesn't need to be a constant. I'm not sure that we need to restrict non-constant n to only values valid for vscale == 1.
Comment Actions I'm hoping we can use an extended shufflevector for this still, but if we do end up going down the extra intrinsics route then I'll certainly use the same namespace.
Agreed, and it also extends to predicated inserts and extracts -- using SVE's 'lasta/lastb' instructions in a vectorized loop tail, for example -- they don't map well to the current instructions, so would need intrinsics.
Agreed. Handling shuffles was part of the original RFC, but that RFC was far too large to discuss all at once. I've started reworking that section based on current feedback, and I'll send it out once ready. Comment Actions For now, I suspect keeping the limit as 'n' is sufficient, as we only really need to insert into the first element to be able to generate a splat. If we need more later we can discuss it then.
Agreed.
Comment Actions Yes; in our downstream compiler we allow inserts and extracts at arbitrary offsets in IR (though we admittedly haven't found too much use for it) using vscale (as a constant, though obtaining the Value via an intrinsic will still work) to give us the required element index. e.g. (vscale * n) - 1 for the last element. I don't think we need to support this initially, though. The SVE ISA doesn't allow arbitrary indices for inserts or extracts, but we can generate an appropriate predicate quite easily in the backend. Comment Actions
Good point. 100% agree. I was only considering the constant case. Comment Actions Ok, so do we have agreement that constant literal indices should be limited to 0..n-1 for now, but non-constant indices can potentially exceed n so that expressions featuring vscale can be used? Comment Actions I want to say yes here, but that leaves a bit of oddness. It's true that nobody can really police on true variable values. However, some variable values can become constant through optimization. Comment Actions Exactly. Non-constant values can become constant. Constant values can be guarded by vscale-dependent runtime guards (both hand-written and compiler generated). My preference is to leave this not restricted to vscale == 1 values, but rather allow all values that can be supported at runtime, and have it be UB if, at runtime, the relevant index is not available. Comment Actions That means a need for a warning to general developers: If there is a check for constant_index >= n to see if the result is a poison value, that code has to be changed so that it applies to non-scalable vector only. Hopefully not too many instances of that. I'm fine with this as long as the communication to the rest of LLVM community is clear about it. Comment Actions Ok; I'll update the patch for that. I think this works out fine, since this behaviour matches our downstream implementation, but I can summarize the extra semantic decisions in this review in a post to llvm-dev as well. Comment Actions Why implementation defined and not UB for the case where the index exceeds the runtime length? How do you intend to define this for SVE?
Comment Actions SVE uses a predicate for indexed inserts and extracts. We generate that predicate by comparing a splat of the index against a stepvector (0,1,2,3...); if the index is out of range then the predicate will be all false. For a mov (insert), that results in an unmodified vector. For a lastb (extract), that extracts the last lane in the vector if no predicate bits are true. I don't know if RVV or SX-Aurora have similarly defined semantics. If the preference is to make it UB, that's fine. Comment Actions I think this should be UB, or at least return poison. However, making it UB has the unfortunate side effect of making it illegal to hoist these operations out of conditionals (which currently isn't the case), so maybe poison is better. For me the main reason for making is UB (aside from generally being conservative) is that element insert/extract can be usefully legalized by putting the vector into a stack slot and accessing the affected element with scalar loads/stores -- in fact, that's the default legalization strategy in trunk. But in that setting an out-of-bounds lane index would become a wild read/write (= clear-cut UB), unless the legalization code jumps through extra hoops to add a bounds check or clamp the lane index into range. This wouldn't affect SVE or RVV since they would implement custom lowering anyway, but for other targets (especially if we eventually generalize insert/extract to accept variable lane positions and do so for all vector types for consistency) it could become an unnecessary headache. Though if we make insertelement with out-of-range lane index return poison instead of being UB, then at minimum clamping in insertelement is necessary to avoid the wild write. Aside: your proposed semantics for SVE would break the property extractelt(insertelt(vec, i, elt), i) = elt which instcombine (and others) most likely assumes. If we make the insertelt return poison (or even just undef, FWIW), that issue goes away. Comment Actions Sorry to be late to the party, but I have a quick question:
What if we know the width is fixed on our target machine? Let's say it's fixed at 512b. So a full width scalable double vector would be: <vscale x 2 x double> Since our width is fixed, we know that vscale=4 here and there are 8 elements in this vector. I'd like to be able to do a really fast insert at say index 3. I.e. insert_element(<vscale x 2 x double> res, double elt, int 3). Would that insert be as fast with the vscale method as it would be for an index < n-1? Comment Actions If you know the exact size of your vectors at compile time, then I believe fixed length vector types should be used, at least at the IR level. The performance of insert/extract is target dependent. For SVE you almost always need a predicate for a single element insert or extract, so you're not going to gain anything by knowing the size ahead of time. Comment Actions
Ah, ok. So let's say we're targeting SVE and I know my vector length is 512b. I was imagining building a vector like this: %r1 = insertelement <scalable 2 x double> undef, double %x, i32 0 %r2 = insertelement <scalable 2 x double > %r1, double %x1, i32 1 %r3 = insertelement <scalable 2 x double > %r2, double %x2, i32 2 %r4 = insertelement <scalable 2 x double > %r3, double %x3, i32 3 %r5 = insertelement <scalable 2 x double > %r4, double %x4, i32 4 %r6 = insertelement <scalable 2 x double > %r5, double %x5, i32 5 %r7 = insertelement <scalable 2 x double > %r6, double %x6, i32 6 %r8 = insertelement <scalable 2 x double > %r7, double %x7, i32 7 But it sounds like I should rather just build a <8 x double> vector instead. Would that <8 x double> vector legalize to SVE vector instructions? Or would it be split into four 128b NEON vectors?
So back to my scalable vector example above, it sounds like even if the above IR was valid, we'd still have to produce predicates at the hardware instruction level. So maybe my concern is moot... Comment Actions So you could do that (judging by the rest of the discussion), but you'd have poison values (effectively) if you exceeded the runtime length. I guess if you're treating scalable vectors as pseudo-fixed-length then you don't care about using the same binary on different hardware.
In the current code, you'd get 4 NEON vectors. In future we'd implement fixed length SVE support as well (for SLP autovec without introducing extra predicate generation/branching), but the recommended method of loop autovec for SVE would be VLA. For your own work you'd be able to use fixed-length types then, but we're still figuring out the design (to minimize the number of ISel patterns).
Yes, though if the index is known to be within a certain range (5bit signed immediate), then you can skip generating a splat and just compare against the stepvector directly; so for your 512b example cpu, you'd be able to generate one fewer instruction when indexing 32b or 64b elements. If you're building up an entire vector (as in your IR), the insr instruction will shift all elements along by one and insert into the first lane, so no predicates would be needed -- but we would need to pattern match and optimize for this case. Comment Actions That's great.
Ok. Thanks for the clarification. Comment Actions What's the status of this? It seems like discussion has died down a bit. I think Graham's idea to change from <scalable 2 x float> to <vscale x 2 x float> will make the IR more readable/understandable but it's not a show-stopper for me. Are there any other outstanding issues to address before this lands? Comment Actions I think @huntergr still needs to update the insertelement/extractelement doc. For me, the last remaining thing is the definition of shufflevector behavior that his last revision did not address. Do we allow scalable vector? Do we allow anything other than zeroinitializer mask? I'm fine not allowing for the time being or restricting to zeroinitializer mask for the time being. We still need to write it down since generally supporting shufflevector of scalable vectors is outside the scope of this patch. Comment Actions
(Sorry about the delay in updating, I've been out at a conference this week) Comment Actions While I don't want to hold up this patch, a name change to the type will be difficult to get through once the type is in and the terminology has settled, so it may be worth getting it right from the start. Personally I think <vscale x 16 x i8> is more explicit (and therefore easier to understand for those new to the type) than <scalable 16 x i8>. And now that we all have a better understanding and clear definition of scalable types, I wonder if <n x 16 x i8> instead of <vscale x 16 x i8> is worth considering again, since it is much easier to read in tests. Other than that, great to see this discussion on scalable types converging and so close to agreement! Comment Actions I kind of like <n x 16 x i8>. It's concise. I don't think vscale really adds a lot of value, but it does eat up characters on a line. Comment Actions I know very well how annoying it can be to read and write (and say) the scalable prefix all the time and wish for something shorter sometimes, but I also prefer <vscale x ...> for the reasons Sander gave. I'll add that <vscale x 4 x i32> feels a bit lighter than <scalable 4 x i32> even though it's the same number of characters (maybe because there's more whitespace?). The <n x ...> syntax is shorter but doesn't have the mnemonic aspect and also clashes with the pre-existing use of "n" as a metavariable standing for some fixed vector length (as in, <N x i1> for example), so I'd rather have <scalable ...> if those are the two options. Comment Actions +1. I like vscale over n because it directly references a term documented in the IR with this patch. Comment Actions It seems like there's enough support for changing to <vscale x as the prefix, so I'll revise the patch.
Comment Actions Hi, this slowed down thinlto links 3-4x, and other things probably too. PR42210 has details. I've reverted this for now in r362913. Comment Actions Ok, thanks. I'll investigate -- I guess having a persistent map for the duration of verification might resolve it. Comment Actions Link to llvm presentation for reference: https://llvm.org/devmtg/2019-04/slides/TechTalk-Kruppe-Espasa-RISC-V_Vectors_and_LLVM.pdf | ||||||||||||||||||||||||||||||||||||||||||||||||