This is an archive of the discontinued LLVM Phabricator instance.

[LegalizeVectorOps] Improve handling of multi-result operations.
ClosedPublic

Authored by craig.topper on Jan 5 2020, 12:25 AM.

Details

Summary

This system wasn't very well designed for multi-result nodes. As
a consequence they weren't consistently registered in the
LegalizedNodes map leading to nodes being revisited for different
results.

I've removed the "Result" variable from the main LegalizeOp method
and used a SDNode* instead. The result number from the incoming
Op SDValue is only used for deciding which result to return to the
caller. When LegalizeOp is called it should always register a
legalized result for all of its results. Future calls for any other
result should be pulled for the LegalizedNodes map.

Legal nodes will now register all of their results in the map
instead of just the one we were called for.

The Expand and Promote handling to use a vector of results similar
to LegalizeDAG. Each of the new results is then re-legalized and
logged in the LegalizedNodes map for all of the Results for the
node being legalized. None of the handles register their own
results now. And none call ReplaceAllUsesOfValueWith now.

Custom handling now always passes result number 0 to LowerOperation.
This matches what LegalizeDAG does. Since the introduction of
STRICT nodes, I've encountered several issues with X86's custom
handling being called with an SDValue pointing at the chain and
our custom handlers using that to get a VT instead of result 0.
This should prevent us from having any more of those issues. On
return we will update the LegalizedNodes map for all results so
we shouldn't call the custom handler again for each result number.

I want to push SDNode* further into the Expand and Promote
handlers, but I've left that for a follow to keep this patch size
down. I've created a dummy SDValue(Node, 0) to keep the handlers
working.

This replaces D71861.

Event Timeline

craig.topper created this revision.Jan 5 2020, 12:25 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 5 2020, 12:26 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
RKSimon added inline comments.Jan 5 2020, 5:02 AM
llvm/lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp
64

?

craig.topper marked an inline comment as done.Jan 5 2020, 11:30 AM
craig.topper added inline comments.
llvm/lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp
64

Must have accidentally changed it when I copied the name into the commit message. Thanks!

Register the results of Expand and Promote in the LegalizedNodes map. Somehow I missed doing that before.

arsenm added inline comments.Jan 6 2020, 6:46 AM
llvm/lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp
145–148

Extra space here.

Is there a real point to returning SDValues here instead of just the SDNode*? I assume this always returns (N, 0), (N, 1)

kpn added a comment.Jan 6 2020, 10:38 AM

I'm happy to see the uses of ReplaceAllUsesOfValueWith() gone. Having nodes be only halfway spliced into the tree for a while seemed like it could cause bugs later. I imagine the scalar legalizer might could benefit from similar changes at some point in the future.

llvm/lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp
495

Is this a new case? Or was this a situation that could occur before your changes but was too subtle to see?

502

It seems like a code smell to have the rules duplicated in the Promote, Expand, and Custom cases. Is there a way to pull most of this block out into a function shared by the three cases? And yet the Custom case looks a little different from the others.

678

Nice. It's much cleaner than MERGE_VALUES.

craig.topper marked 3 inline comments as done.Jan 6 2020, 10:58 AM
craig.topper added inline comments.
llvm/lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp
145–148

The handlers are calling out to TargetLowering and that's giving back two separate SDValues. I think they are different nodes. For example for UADDO, I think one result would be from an ADD and one would be from a SETCC.

495

It causes the assert below to fail in some cases. We never had the assert before and we only ever put one of the results from the custom handling into the map. You'll see there's a similar 1 result check in LegalizeDAG as well.

502

Custom is a bit nasty due to only returning one SDValue. I had to rework it again for D72238. I should probably move that part of the change over here as I'm not entirely sure the changes I had to make there aren't needed for other cases.

I'll look into merging the handling.

efriedma added inline comments.Jan 6 2020, 12:13 PM
llvm/lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp
502

We should probably fix the whole LowerOperation/LowerOperationWrapper mess at some point, so custom legalization always returns a list of values. But I guess we don't have to do that here.

-Address review comments.
-Move the Expand/Promote result registration in the cache up to the caller as they need to use "Op" rather than "Node" to update the translation cache. Node almost always points to the same thing as Op, but the UpdateNodeOperands call that assigned Node might trigger CSE. When that happens we still need to use the original Op as the translation cache key since other nodes are holding that reference. This was the bug D71861 was trying to fix.
-Add the test case from D71861 which tests for that bug in the Custom path.

kpn added a comment.Jan 7 2020, 6:51 AM

Looks like the test case didn't make it over.

With test case for real this time

In general this all makes sense to me. See a few minor inline comments.

I agree with @kpn's comment about code duplication. I was wondering whether it might make sense to abstract some of that, even while the TLI.LowerOperation interface remains unchanged. E.g. we could have a routine like this:

bool CustomLower(SDNode *Node, SmallVectorImpl<SDValue> &Results) {
  if (SDValue Tmp = TLI.LowerOperation(SDValue(Node, 0), DAG)) {
    LLVM_DEBUG(dbgs() << "Successfully custom legalized node\n");
    if (Tmp == SDValue(Node, 0))
      return true;
    
    // Tmp might point to a single result from a multi result node, in that
    // case we need to use it's result number.
    if (Node->getNumValues() == 1) {
      Results.push_back(Tmp);
      return true;
    }
    
    // Otherwise it should be a multi-result node with the same number of
    // results.
    assert(Tmp->getNumValues() == Node->getNumValues() &&
           "Unexpected number of results");
    
    for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
      Results.push_back(Tmp.getValue(i));
    return true;
  }
  
  LLVM_DEBUG(dbgs() << "Could not custom legalize node\n");
  return false;
}

which could be used e.g. like so:

SmallVector<SDValue, 8> ResultVals;
if (CustomLower(Node, ResultVals)) {
  if (ResultVals.empty())
    return TranslateLegalizeResults(Op, Node);

  Changed = true;
  return RecursivelyLegalizeResults(Op, ResultVals);
}
LLVM_FALLTHROUGH;  // to expand

which would make the interfaces of the CustomLower / Expand / Promote cases the same, probably enabling further code sharing at the call site(s).

llvm/lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp
266

Lowered.getNode() must always be Node here, right?

480

Could just return the result of TranslateLegalizeResults, right?

517

Likewise, just return the result.

854

It's a bit odd to hard-code that some expanders may return a null SDValue and others may not. It may be preferable to just pass the Results vector through.

craig.topper marked an inline comment as done.Jan 8 2020, 10:17 AM
craig.topper added inline comments.
llvm/lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp
854

Agreed. I was trying to minimize the changes to the handlers in this patch to keep the size down. I'm going to do a follow up patch to pass SDNode *N instead of Op to all the handlers. I can push Results while I'm doing that.

Add a LowerOperationWrapper helper that updates a Result vector. It looks a lot like X86's override of TargetLowering::LowerOperationWrapper except the bool result. The TargetLowering version doesn't allow for the possibility of keeping the existing node since it only called by the type legalizer today. I think in the future we could try to merge this together, but it will require changes to other targets.

Pass Results vector into the overflow operation expanders instead of returning std::pair. I plan to pass Results to all expanders in a follow up. Or possibly inline some of the smaller functions into the switch.

pengfei added a subscriber: pengfei.Jan 8 2020, 5:19 PM
uweigand accepted this revision.Jan 10 2020, 6:56 AM

OK, this looks all good to me now. I agree that there can be future API cleanup, but that can be done in follow-on patches. I think we should go with this for now.

This revision is now accepted and ready to land.Jan 10 2020, 6:56 AM
This revision was automatically updated to reflect the committed changes.