This is an archive of the discontinued LLVM Phabricator instance.

[DAGCombiner] Allow operand of step_vector to be negative.
ClosedPublic

Authored by junparser on Apr 19 2021, 9:05 PM.

Details

Summary

It is proper to relax non-negative limitation of step_vector. Also this patch adds more combines for step_vector:
(sub X, step_vector(C)) -> (add X, step_vector(-C))

TestPlan: check-llvm

Diff Detail

Unit TestsFailed

Event Timeline

junparser created this revision.Apr 19 2021, 9:05 PM
junparser requested review of this revision.Apr 19 2021, 9:05 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 19 2021, 9:05 PM
junparser edited the summary of this revision. (Show Details)Apr 19 2021, 9:05 PM
junparser edited the summary of this revision. (Show Details)Apr 19 2021, 9:09 PM

I've nothing against the change but it is more involved than updating the comment and assert. There are places where STEP_VECTOR's operand is treated as unsigned, based on the original requirement, that will need to be updated. For example DAGTypeLegalizer::PromoteIntRes_STEP_VECTOR. Ideally we'd want to add/update tests to show the signedness is properly protected during type legalisation.

I've nothing against the change but it is more involved than updating the comment and assert. There are places where STEP_VECTOR's operand is treated as unsigned, based on the original requirement, that will need to be updated. For example DAGTypeLegalizer::PromoteIntRes_STEP_VECTOR. Ideally we'd want to add/update tests to show the signedness is properly protected during type legalisation.

Yep, I'll update later.

junparser updated this revision to Diff 338838.Apr 20 2021, 5:37 AM

Address comments.

@frasercrmck, Do you have any idea about the change in riscv?

I also have nothing against the change in principle, but in addition to @paulwalker-arm's comments, RISC-V won't support this: it expects IMM to be 1, as it always was before this. We shouldn't introduce something that regresses this target, so the lowering of STEP_VECTOR will need to be extended to legalize/lower the operation.

Hmm I just saw that D100088 went in without anyone involved with RISC-V being on the reviewer list or notified. I think that's technically a regression since the RISC-V backend crashes on all those test cases that were added.

llvm/test/CodeGen/RISCV/rvv/stepvector.ll
277–285

This is definitely a regression so I think we need to see what's going on here. The split-vector legalization will be causing this. Perhaps because it's still zero-extending there?

I also have nothing against the change in principle, but in addition to @paulwalker-arm's comments, RISC-V won't support this: it expects IMM to be 1, as it always was before this. We shouldn't introduce something that regresses this target, so the lowering of STEP_VECTOR will need to be extended to legalize/lower the operation.

Yes, I just noticed that after D100088 committed. I'm fixing this.

Hmm I just saw that D100088 went in without anyone involved with RISC-V being on the reviewer list or notified. I think that's technically a regression since the RISC-V backend crashes on all those test cases that were added.

OK, I saw D100856.

junparser added inline comments.Apr 20 2021, 9:23 PM
llvm/test/CodeGen/RISCV/rvv/stepvector.ll
277–285

This is caused by SplitVecRes_STEP_VECTOR which changes getZExtOrTrunc to getSExtOrTrunc, we may need check whether stepval is isNonNegative.

junparser updated this revision to Diff 339146.Apr 21 2021, 2:17 AM

Fix regression in riscv32.

sdesmalen added inline comments.Apr 21 2021, 2:56 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
3547

nit: double space.

3548

If there are multiple uses of step_vector(C), then it may be more beneficial to have a single step_vector(C) and use separate add/sub. Can you add a check that N1 has only a single use?

llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp
1663

This can also use getSExtOrTrunc for the non-negative case?

paulwalker-arm added inline comments.Apr 21 2021, 2:58 AM
llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
4794–4795

Is calling sextOrTrunc necessary? I would have thought you could just replace getZExtValue() with getSExtValue().

That said with @frasercrmck previous patch to remove the size restriction of STEP_VECTOR's operands I don't believe there's need for this function to extend the operand at all and so N->getOperand(0) can be passed directly to getStepVector.

llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp
1658–1665

This doesn't look correct to me. The operand is either signed or unsigned and should be treated accordingly. Given this patch wants to allow negative value then we're essentially converting the STEP_VECTOR to take a signed operand and should always use SExt.

That said I'm wondering if the issue here is using DAG to do the extension even though the operand is defined to be a constant. Perhaps the following works for you?

SDValue StartOfHi =
      DAG.getVScale(HiVT.getVectorElementType(), StepVal * LoVT.getVectorMinNumElements());
frasercrmck added inline comments.Apr 21 2021, 3:05 AM
llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
4794–4795

Yeah I think if the incoming step is legal (which it possibly isn't in theory -- in practice we always create a step with TypeToTransformTo?) then it should be possible to pass it straight through.

llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp
1658–1665

I agree, I think it should be consistently SExt. I think @junparser tried to mitigate a RISC-V regression but in line with what you're saying, I bet some of the poor RISC-V code comes from the DAG extending VSCALE and not being able to optimize it due to not being able to infer the known bits.

junparser added inline comments.Apr 21 2021, 3:47 AM
llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
4794–4795

ok,let's use it directly and add assertion here.

llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp
1658–1665

@paulwalker-arm, The tradeoff here does try to mitigate regression in riscv-32 with element type like i64. Meanwhile, extension is necessary for vscale(i64) under riscv-32. I checked PromoteIntRes_VSCALE which does not do truncation. @frasercrmck, would it be ok to relax vscale as same as step_vector?

junparser added inline comments.Apr 21 2021, 4:31 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
3548

will update later.

llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp
1658–1665

@paulwalker-arm, The tradeoff here does try to mitigate regression in riscv-32 with element type like i64. Meanwhile, extension is necessary for vscale(i64) under riscv-32. Since there is no ExpandIntegerResult with vscale. @frasercrmck, would it be ok to relax vscale as same as step_vector?

paulwalker-arm added inline comments.Apr 21 2021, 5:17 AM
llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp
1658–1665

I believe VSCALE and STEP_VECTOR have different problems. STEP_VECTOR has a vector result but scalar operand so it seemed reasonable to allow the flexibility with regards to its operand's type. I don't believe the same flexibility should be given to VSCALE because that is a scalar only operation.

That's to say that if a target doesn't support i64 for the operand type, then it will also not support i64 as its result. I mean if we decided STEP_VECTOR's operand was not worth the effort and removed it then this code will still need to plant an explicit MUL that'll have the same problem.

So whilst I agree there's a problem I'm not sure this is the function to solve it. Perhaps SPLAT_VECTOR_PARTS need to be involved somewhere?

Perhaps what we're really asking for here is that SPLAT_VECTOR's operand be relaxed to allow an operand that is smaller than its result element type?

junparser added inline comments.Apr 21 2021, 5:57 AM
llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp
1658–1665

yes, relax vscale does not work here. I have did some local test in ExpandIntegerResult:

case ISD::VSCALE:
   {
 EVT VT = N->getValueType(0);
 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
SDLoc dl(N);
 SDValue NewNode = DAG.getNode(ISD::MUL, dl, VT, DAG.getZExtOrTrunc(DAG.getVScale(dl, 
 NVT, APInt(NVT.getSizeInBits(), 1)), dl, VT), N->getOperand(0));
 ReplaceValueWith(SDValue(N, 0), NewNode);
  break;
  }

turns out as @frasercrmck said, we get much worse code here. So I prefer keep SEXT here.

Matt added a subscriber: Matt.Apr 21 2021, 6:24 AM
junparser updated this revision to Diff 339230.Apr 21 2021, 7:25 AM

Address comments.

junparser added inline comments.Apr 21 2021, 7:27 AM
llvm/test/CodeGen/RISCV/rvv/stepvector.ll
277–285

@frasercrmck still keep this issue open.

paulwalker-arm added inline comments.Apr 21 2021, 8:48 AM
llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp
1658–1665

I'm not happy with this approach. It doesn't make sense to change the definition of ISD::STEP_VECTOR and then have to tip toe around this definition because a target might not be in a position to generate the most optimal code for it. I see two options:

  1. We change the definition of ISD::STEP_VECTOR and work within that definition, or
  2. We maintain the current definition.

Personally I prefer option 1 because it's in the spirit of this node's original intent, but option 2 also works until we're in a position to revisit.

That said, I really think the poor code generation problem is more to do with the definition of ISD::SPLAT_VECTOR which doesn't work well for target's whose max legal scalar type is smaller than its max legal vector element type.

frasercrmck added inline comments.Apr 21 2021, 8:57 AM
llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp
1658–1665

I haven't had time to dig in but I was wondering if the issue of poor code generation could be mitigated by some "known bits" analysis for ISD::VSCALE. I don't know if there's precedent for target-specific known-bits analysis of a generic node, but I feel like that's what it'd have to be. RISC-V has known limits on vscale.

We do have ISD::SPLAT_VECTOR_PARTS to deal with ISD::SPLAT_VECTOR for targets whose max scalar type is smaller than the max vector element type. But I feel like the sign extension is still going to be the blocker?

junparser added inline comments.Apr 21 2021, 8:02 PM
llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp
1658–1665

Although it is also ok with me to maintain current definition of step_vector. Since then we may make some promise to keep operand of step_vector still be positive constant after combine in D100088. As for D100816, we also need some extra pattern to handle negative case with sub. I prefer 1 as well.
@frasercrmck, do you have any suggestion about where to start, I may have time to dig in.

craig.topper added inline comments.
llvm/test/CodeGen/RISCV/rvv/stepvector.ll
277–285

Does f6d8cf7798440f303d5a273999e6647cbe795ac6 make this code better?

rebased.
@craig.topper, Now rv32 get some code as rv64, thanks!

paulwalker-arm accepted this revision.Apr 22 2021, 3:14 AM

A couple of minor requests plus it's worth adding a "step-vector has more than one use" test but otherwise looks good to me. Thanks for your efforts @junparser, also thanks @frasercrmck and @craig.topper for the assists.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
3552

DL

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
4722

to fit

This revision is now accepted and ready to land.Apr 22 2021, 3:14 AM
junparser updated this revision to Diff 339568.Apr 22 2021, 4:47 AM

Address comments.

sdesmalen accepted this revision.Apr 22 2021, 5:00 AM

The patch looks good to me, thanks @junparser.

This revision was landed with ongoing or failed builds.Apr 22 2021, 5:58 AM
This revision was automatically updated to reflect the committed changes.