[RFC] Add zext nneg flag

IR & Optimizations
1

Background

LLVM currently canonicalizes sext operations to zext operations if the argument is known to be non-negative. This enables better analysis, redundancy elimination and is preferred on most targets.

However, the conversion to zext is not always beneficial, for two main reasons:

  • If the extension is used in a signed context, sext may be preferable. For example, while icmp slt sext(%x), sext(%y) can be converted into icmp slt %x, %y, this is not the case if either of the sext operations has been converted into a zext.
  • Unlike most other targets, RISC-V prefers sext over zext. The latter may require additional instructions.

This problem can be addressed to some degree by undoing the canonicalization in places where sext is preferred. However, this does not work reliably, because the necessary information may have been lost or is not readily available (e.g. if the canonicalization was performed by IPSCCP or CVP, but the undo transform only has access to VT).

Proposal

The proposal is to add a new nneg flag to zext, with the following semantics:

If the nneg flag is set, and the zext argument is negative, the result is a poison value.

A corollary is that replacing a zext nneg with sext is a refinement.

Passes that convert sext to zext would add this flag, which would enable conversion back to sext to be more reliable. Additionally, the flag can be inferred based on different analysis passes (IPSCCP, LVI, SCEV, VT).

Alternatives

There are a number of minor and major variations of the basic idea:

Also support sext nneg

The same flag could be supported on sext. sext nneg and zext nneg would be equivalent.

This is arguably more consistent, but as we would canonicalize any sext nneg to zext nneg anyway, the value of having such a flag (and associated cost) is dubious.

Call the flags nuw and nsw

In a previous discussion it was suggested to instead add nuw and nsw flags to zext and sext. One of the flags is implied by the operation and always set:

  • zext nuw (implied)
  • sext nsw (implied)
  • zext nsw (same as zext nneg)
  • sext nuw (same as sext nneg from previous section)

This is nice in that it reuses the existing nuw/nsw flags, but I find their use here rather non-obvious and awkward, especially as one of the flags is always implicit. I don’t think we actually gain anything from using the same name (especially as the existing flags are fairly hard-coded to binary operators).

Introduce a general ext instruction

A disadvantage of zext nneg is that it still leaves zext as the privileged operation, because it is our canonicalization target. Transforms that require zero extension can just look for zext. Transforms that require sign extension would have to look for sext or zext nneg.

A way to avoid this would be to combine zext and sext into a single instruction, as follows:

  • ext zero: Zero-extend.
  • ext sign: Sign-extend.
  • ext zero sign: Both zero-extend and sign-extend. Returns poison when these conflict, i.e. when the argument is negative.

This removes any asymmetry between zext/sext. The sext to zext canonicalization is replaced with inferring that a sign ext is also a zero ext.

The zero/sign flags here are not standard poison-generating flags, so some additional handling would be needed in relation to flag manipulation.

This is arguably the most principled approach, but also requires a lot more implementation effort and IR churn. This is probably not justified at this point.

Patches

@karouzakisp has implemented a patch series for introducing the nneg flag starting with ⚙ D156444 [llvm][RISCV][IR] Zext flag in IR for RISC-V. I’ve submitted a slightly cleaned up version of the first step in https://github.com/llvm/llvm-project/pull/67982.

1 Like
2

I can see the appeal of the ‘ext’ instruction, but I think the implementation effort is probably not worth it.

I would go with the nneg attribute. Nsw/nuw aren’t very intuitive. And you already have the patch for it, so just go for it.

The attribute seems well justified & well defined, so no concerns from me.

1 Like
3

Sorry for missing this until now: I think it makes sense to add these sorts of flags, and agree we want to “capture and maintain information in the IR” not “make a transformation and expect we can reconstruct the information later”.

The main challenge of adding this sort of information to the IR is that transformations that manipulate these ops need to maintain it correctly, but I think that is fine.

Instead of a “nneg” flag on the extensions, would it make sense to have a full set of known zero/one/undef bits on the input? This would be a more general model that could apply to other integer operations and would better model what ComputeMaskedBits et al are doing.

-Chris