[GlobalISel]: Allow backends to custom legalize Intrinsics

[aditya_nandakumar]

Summary

Add a hook "legalizeInstrinsic" to allow backends to override this and custom lower/legalize intrinsics.
One caveat is the handling of case where target deleted the intrinsic instruction. It is possible that the intrinsic was successfully lowered/legalized but the additional instructions that were created can't be legalized and finally when we try to reportGISelFailure, we might be dealing with a erased instruction.
Instead, the target would return an enum value indicating that the instruction needs to be erased which we can erase after making sure we don't need to reportGISelFailure.
This unfortunately has to expose LegalizeHelper to the backends.

Looking forward to your feedback.

[ab]

lib/CodeGen/GlobalISel/LegalizerHelper.cpp

89

I don't think you want this behavior: you should only return "Erase" if you want to erase the "root"/initial MI, not any arbitrary MI in the worklist.

Thought that does raise an interesting question: what happens if you legalize an intrinsic to two new intrinsics, and you want to erase one of those? Who should be responsible for that?

[igorb]

Hello,
I think this case relevant not only for intrinsic instruction.
Any instruction can be successfully lowered/legalized but the additional instructions that were created can't be legalized and finally when we try to reportGISelFailure, we might be dealing with a erased instruction.

[aditya_nandakumar]

lib/CodeGen/GlobalISel/LegalizerHelper.cpp

89

You're right.
The problem is reportGISelFailure for the main instruction. We could perhaps erase instructions that are not MI here (Idx == 0) and fallback to erasing the main instruction after reporting GISelFailure.

[aditya_nandakumar]

The other (easier) approach is to reportGlobalISelFailure on intermediate instructions whenever we're unable to legalize/Lower them. That means, the backend custom lowering code could erase the instructions that it needs, and won't have to worry about calling reportGlobalISelfailure on erased instructions.

[t.p.northover]

The other (easier) approach is to reportGlobalISelFailure on intermediate instructions whenever we're unable to legalize/Lower them.

Is this all accounting for the fact that you may not know if you can legalize an intrinsic before you've already erased it? Seems like a bit of an odd situation to be in if so.

[aditya_nandakumar]

In D31359#712574, @t.p.northover wrote:

The other (easier) approach is to reportGlobalISelFailure on intermediate instructions whenever we're unable to legalize/Lower them.

Is this all accounting for the fact that you may not know if you can legalize an intrinsic before you've already erased it? Seems like a bit of an odd situation to be in if so.

Not sure if I understand the question correctly. My view is the Intrinsic was legalized by the backend (created some machine instruction, erased the generic intrinsic and created intermediate instructions). It's entirely possible that the intermediate instructions may fail legalization (for e.g. missing LegalizeActions/custom lowering of other intrinsics etc).

[kristof.beyls]

In D31359#712612, @aditya_nandakumar wrote:

In D31359#712574, @t.p.northover wrote:

The other (easier) approach is to reportGlobalISelFailure on intermediate instructions whenever we're unable to legalize/Lower them.

Is this all accounting for the fact that you may not know if you can legalize an intrinsic before you've already erased it? Seems like a bit of an odd situation to be in if so.

Not sure if I understand the question correctly. My view is the Intrinsic was legalized by the backend (created some machine instruction, erased the generic intrinsic and created intermediate instructions). It's entirely possible that the intermediate instructions may fail legalization (for e.g. missing LegalizeActions/custom lowering of other intrinsics etc).

FWIW, I think I've seen similar situations while working on my patch for non-power-of-2-patches at https://reviews.llvm.org/D30529.
For example, I think I've seen this while working on that patch when legalizing e.g. <3 x i3> in a number of steps (<3 x i3>-> <3 x i8>, then <3 x i8> -> <8 x i8>).
If the <3 x i3> -> <3 x i8> step succeeds and the second <3 x i8> -> <8 x i8> step fails, the original instruction was indeed removed already.
I think I saw the reportGISelFailure call to then try and access the already erased instruction, leading to a segfault.
I don't fully remember the details and may have misremembered some of this above. If it'd be useful I can dig deeper to see if I could reproduce the issue.

It'd be nice if there could be a test case for the fallback mechanism in-tree for a case like this. It's not immediately obvious to me how such an in-tree test could be created at the moment.
All in all, my impression so far is that patch has 2 changes:

1. Having a mechanism to not blow up reportGISelFailure when a multi-step legalization fails half-way through
2. Allowing custom legalization of intrinsics.

If I've understood correctly, maybe best to commit them separately once there's agreement?

[aditya_nandakumar]

In D31359#713066, @kristof.beyls wrote:

In D31359#712612, @aditya_nandakumar wrote:

In D31359#712574, @t.p.northover wrote:

The other (easier) approach is to reportGlobalISelFailure on intermediate instructions whenever we're unable to legalize/Lower them.

Is this all accounting for the fact that you may not know if you can legalize an intrinsic before you've already erased it? Seems like a bit of an odd situation to be in if so.

Not sure if I understand the question correctly. My view is the Intrinsic was legalized by the backend (created some machine instruction, erased the generic intrinsic and created intermediate instructions). It's entirely possible that the intermediate instructions may fail legalization (for e.g. missing LegalizeActions/custom lowering of other intrinsics etc).

FWIW, I think I've seen similar situations while working on my patch for non-power-of-2-patches at https://reviews.llvm.org/D30529.
For example, I think I've seen this while working on that patch when legalizing e.g. <3 x i3> in a number of steps (<3 x i3>-> <3 x i8>, then <3 x i8> -> <8 x i8>).
If the <3 x i3> -> <3 x i8> step succeeds and the second <3 x i8> -> <8 x i8> step fails, the original instruction was indeed removed already.
I think I saw the reportGISelFailure call to then try and access the already erased instruction, leading to a segfault.
I don't fully remember the details and may have misremembered some of this above. If it'd be useful I can dig deeper to see if I could reproduce the issue.

It'd be nice if there could be a test case for the fallback mechanism in-tree for a case like this. It's not immediately obvious to me how such an in-tree test could be created at the moment.
All in all, my impression so far is that patch has 2 changes:

1. Having a mechanism to not blow up reportGISelFailure when a multi-step legalization fails half-way through
2. Allowing custom legalization of intrinsics.

If I've understood correctly, maybe best to commit them separately once there's agreement?

Yes - you are correct with the above 2 impressions.
Please let me know if I should create two separate reviews instead of this one.

[kristof.beyls]

It'd be nice if there could be a test case for the fallback mechanism in-tree for a case like this. It's not immediately obvious to me how such an in-tree test could be created at the moment.
All in all, my impression so far is that patch has 2 changes:

1. Having a mechanism to not blow up reportGISelFailure when a multi-step legalization fails half-way through
2. Allowing custom legalization of intrinsics.

If I've understood correctly, maybe best to commit them separately once there's agreement?

Yes - you are correct with the above 2 impressions.
Please let me know if I should create two separate reviews instead of this one.

Not needed for me to split the review in two.
Having separate commits once the patch is approved definitely is desirable.

[t.p.northover]

It's entirely possible that the intermediate instructions may fail legalization (for e.g. missing LegalizeActions/custom lowering of other intrinsics etc).

And then reporting an error on those would be fine, surely? I don't see why we have to defer deleting an instruction by passing a weird success code up the stack.

[aditya_nandakumar]

In D31359#713440, @t.p.northover wrote:

It's entirely possible that the intermediate instructions may fail legalization (for e.g. missing LegalizeActions/custom lowering of other intrinsics etc).

And then reporting an error on those would be fine, surely? I don't see why we have to defer deleting an instruction by passing a weird success code up the stack.

The latest proposal was to move the reportGISelFailure into legalizeInstr (right where we return UnableToLegalize). That way we report failure on the first instruction that fails (whether it's the original instruction or an intermediate one). There's no need to pass up weird success code up the stack or defer it for later. The backend (intrinsic Lowering) can erase the instruction and return success as before.

[aditya_nandakumar]

Updated this to just handle the lowering of the Intrinsics.
Handling the case of reporting failure on deleted instructions is being discussed here (and is orthogonal to this).
https://reviews.llvm.org/D31503

[aditya_nandakumar]

Ping?

[tstellar]

Here is an AMDGPU patch that uses legalizeIntrinsic() https://reviews.llvm.org/D52923

[aditya_nandakumar]

In D31359#1257145, @tstellar wrote:

Here is an AMDGPU patch that uses legalizeIntrinsic() https://reviews.llvm.org/D52923

Thanks. Should I go ahead and commit this patch so you can get the AMD legalization intrinsic in?

[arsenm]

I have a few possible uses for this. llvm.amdgcn.icmp/llvm.amdgcn.fcmp are supposed to mirror the standard operations, and need legalization (at least for i16 values on older subtargets). I'm also considering whether some intrinsics should be directly selected prior to regbankselect.

[arsenm]

I'm not sure I understand why this needs to be separate from legalizeCustom

lib/CodeGen/GlobalISel/LegalizerHelper.cpp

40–41

Conditions written backwards

[aditya_nandakumar]

In D31359#1412300, @arsenm wrote:

I'm not sure I understand why this needs to be separate from legalizeCustom

IIUC, intrinsics are defined with variable no of srcs and dsts and I'm not sure if it's possible for any legalization query to specify actions(custom) based on intrinsic id which would imply different types for different operands. Also, this patch was written a long time and at that time it wasn't possible to specify intrinsic ids + operands for legalization rules. Also, I'm not sure if it's' possible now.

[arsenm]

include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

195–196

I think this need to directly return LegalizeResult. Some intrinsics may be AlreadyLegal, or Legalized

[aditya_nandakumar]

include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

195–196

When this was written originally, all this patch provided was a hook to custom lower intrinsics - and return true if either it was legalized or was already legal and false if it failed to legalize due to some reason. Of course it can return LegalizeResult (when it makes sense to differentiate b/w already legal and just legalized). Is this what this patch needs to move forward at this point?

[arsenm]

LGTM. I have a few patches depending on this now, and returning the bool is good enough. I think refining the result may be useful, but I haven't run into a concrete need for it yet. It would be more useful if we had a mechanism for detecting whether an intrinsic is legal or not, so that the selector verifier could error like any other instruction.

[aditya_nandakumar]

In D31359#1564825, @arsenm wrote:

LGTM. I have a few patches depending on this now, and returning the bool is good enough. I think refining the result may be useful, but I haven't run into a concrete need for it yet. It would be more useful if we had a mechanism for detecting whether an intrinsic is legal or not, so that the selector verifier could error like any other instruction.

Thanks. I think for now it's important to get this patch in - considering how l long it's been open :). I agree it would be nice to have a mechanism to detect legality of intrinsics - but that's for another commit I think.

[aditya_nandakumar]

Thanks. Committed in 364821.

include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

public:
   }
 
   bool isLegal(const MachineInstr &MI, const MachineRegisterInfo &MRI) const;
 
   virtual bool legalizeCustom(MachineInstr &MI,
                               MachineRegisterInfo &MRI,
                               MachineIRBuilder &MIRBuilder) const;
 
+  virtual bool legalizeIntrinsic(MachineInstr &MI, MachineRegisterInfo &MRI,
+                                 MachineIRBuilder &MIRBuilder) const;
+
 private:
   static const int FirstOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_START;
   static const int LastOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_END;
 
   typedef DenseMap<LLT, LegalizeAction> TypeMap;
   typedef DenseMap<std::pair<unsigned, LLT>, LegalizeAction> SIVActionMap;
 
   SmallVector<TypeMap, 1> Actions[LastOp - FirstOp + 1];

lib/CodeGen/GlobalISel/LegalizerHelper.cpp

 
 LegalizerHelper::LegalizerHelper(MachineFunction &MF, const TargetPassConfig &TPC)
     : MRI(MF.getRegInfo()), LI(*MF.getSubtarget().getLegalizerInfo()), TPC(TPC) {
   MIRBuilder.setMF(MF);
 }
 
 LegalizerHelper::LegalizeResult
 LegalizerHelper::legalizeInstrStep(MachineInstr &MI) {
+  if (TargetOpcode::G_INTRINSIC == MI.getOpcode() ||
+      TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS == MI.getOpcode())
+    return LI.legalizeIntrinsic(MI, MRI, MIRBuilder) ? Legalized
+                                                     : UnableToLegalize;
   auto Action = LI.getAction(MI, MRI);
   switch (std::get<0>(Action)) {
   case LegalizerInfo::Legal:
     return AlreadyLegal;
   case LegalizerInfo::Libcall:
     return libcall(MI);
   case LegalizerInfo::NarrowScalar:
     return narrowScalar(MI, std::get<1>(Action), std::get<2>(Action));
do {
     if (Res == UnableToLegalize) {
       MIRBuilder.stopRecordingInsertions();
       MachineFunction *MF = TmpMI->getParent()->getParent();
       MachineOptimizationRemarkEmitter MORE(*MF, /*MBFI=*/nullptr);
       reportGISelFailure(*MF, TPC, MORE, "gisel-legalize",
                          "unable to legalize instruction", *TmpMI);
       return UnableToLegalize;
     }
     Changed |= Res == Legalized;
     ++Idx;
   } while (Idx < WorkList.size());
 
   MIRBuilder.stopRecordingInsertions();
 
   return Changed ? Legalized : AlreadyLegal;
 }
 

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

LLT LegalizerInfo::findLegalType(const InstrAspect &Aspect,
   }
 }
 
 bool LegalizerInfo::legalizeCustom(MachineInstr &MI,
                                    MachineRegisterInfo &MRI,
                                    MachineIRBuilder &MIRBuilder) const {
   return false;
 }
+bool LegalizerInfo::legalizeIntrinsic(MachineInstr &MI,
+                                   MachineRegisterInfo &MRI,
+                                   MachineIRBuilder &MIRBuilder) const {
+  return true;
+}