[GlobalISel]: Fix bug where we can report GISelFailure on erased instructions

[aditya_nandakumar]

Summary

The original instruction might get legalized and erased and expanded

into intermediate insts. An intermediate instruction might fail
legalization and we would report failure on an erased inst.
Instead now report failure on the first failing instruction

[qcolombet]

Hi Aditya,

If I understand correctly, the problem with the current reporting scheme is the MI we use to print the report may have been deleted, therefore we may access invalid memory.
I would suggest a less invasive change, pretty similar to what we do when we know an iterator is going to be invalidated:
What do you think of printing the MI in a string before calling legalization, then use that string in the error message?

Cheers,
-Quentin

include/llvm/CodeGen/GlobalISel/LegalizerHelper.h

27

Use a forward declaration at this point.

49

I don't particularly like the fact that the Helper needs to do reporting.
At least, I would expect TPC to be optional.

lib/CodeGen/GlobalISel/LegalizerHelper.cpp

63

It feels wrong to me to have reporting in here.
My concerns are:

• We conflict reporting and doing the transformation
• We may report failure on product of legalization. Hence, it may actually be difficult to understand where it comes from.

[aditya_nandakumar]

Thanks Quentin. Seems like printing the MI to a string and printing that instead might address all the concerns raised above.

[ab]

I considered and dismissed speculatively printing: it's a pretty expensive operation (especially when it needs to print an IR value, and it needs to recompute slot numbers).

Here's another idea I considered: have legalizeInstr return the instruction it failed on, in a std::pair<LegalizeResult, MachineInstr*>.

In practice, the external users of the LegalizeHelper API shouldn't care about LegalizeResult: we either return UnableToLegalize, or we return a success value (Legalized/AlreadyLegal. So we could simply return a MachineInstr*, which is nullptr if we succeeded. It would be weird to read though, so we could go extra fancy and have an Error that either contains a MachineInstr*, or is Error::success().

[qcolombet]

I considered and dismissed speculatively printing: it's a pretty expensive operation

I was expecting something like that, but I thought we could mitigate this by only pre-printing stuff in debug build. Non-debug would just fail with unable to legalize.

Here's another idea I considered: have legalizeInstr return the instruction it failed on, in a std::pair<LegalizeResult, MachineInstr*>.

How would that work with a deleted instruction?

[qcolombet]

Here's another idea I considered: have legalizeInstr return the instruction it failed on, in a std::pair<LegalizeResult, MachineInstr*>.

How would that work with a deleted instruction?

Talked with Ahmed offline. He was thinking in terms of the current instruction being legalized.
Also given this is going to be used only for our own debugging purposes, the "it may be difficult to understand where it comes from" argument I made is pointless.

Therefore, Aditya, please go with Ahmed's idea. I would just suggest to print (in a DEBUG statement) the instruction we process or have some optimization remarks just for us (i.e., not emitted if !NDEBUG).

[aditya_nandakumar]

In D31503#714507, @ab wrote:

I considered and dismissed speculatively printing: it's a pretty expensive operation (especially when it needs to print an IR value, and it needs to recompute slot numbers).

Here's another idea I considered: have legalizeInstr return the instruction it failed on, in a std::pair<LegalizeResult, MachineInstr*>.

In practice, the external users of the LegalizeHelper API shouldn't care about LegalizeResult: we either return UnableToLegalize, or we return a success value (Legalized/AlreadyLegal. So we could simply return a MachineInstr*, which is nullptr if we succeeded. It would be weird to read though, so we could go extra fancy and have an Error that either contains a MachineInstr*, or is Error::success().

Just to clarify here, (IIUC) returning either an Error (with MachineInstr*) or Error::success() would mean that we'd not be able to differentiate b/w Legalized and AlreadyLegal. Did you mean Expected<LegalizeResult>?

[kristof.beyls]

lib/CodeGen/GlobalISel/LegalizerHelper.cpp

59–60

This is probably a moot point now, now that it shows that using the "std::pair<LegalizeResult, MachineInstr*>"-approach looks a lot more promising, but I think this code probably still suffers the same problem as before:
After legalizeInstrStep, TmpMI can be removed from the MachineBasicBlock, and TmpMI->getParent() will then probably return a nullptr, causing a segmentation fault.

I'm afraid I don't have a good insight on whether we'd still want to be able to differentiate between "AlreadyLegal" and "Legalized" in the "std::pair<LegalizeResult, MachineInstr*>"-approach.

[t.p.northover]

I'm not entirely keen on the pair solution. It seems to be designing the API around the (temporary) situation where legalization can routinely fail and need to fall back. In the long term most of these will be assertion failures.

Actually, I'm still unclear why the legalization doesn't know it'll fail before getting bogged down in erasing instructions. Normal instructions created while doing a single-step legalization would be added to the worklist to be seen by the top-level Legalizer wouldn't they?

[aditya_nandakumar]

Tim also suggested that we move the implementation of LegalizerHelper::LegalizeInstr (with the worklist) into Legalizer.cpp. This would work fine too (except we would need to make LegalizeHelper::MachineIRBuilder public member so we can start and stop recording insertions).

[qcolombet]

Sounds good to me.

[aditya_nandakumar]

Update for feedback from Tim/Quentin.
Move the legalizeInstr to Legalizer and report failure on first instruction that fails.
Also this needs MIRBuilder to be accessible outside of LegalizeHelper (to set/unset RecordInsertions).

[ab]

I'm not a big fan of this approach (because the iterative logic seems like it does belong in the helper), but it's mostly fine (we don't have users other than Legalizer), and it sounds like Tim and Quentin are on board. So, LGTM.

Can you add a test, say in arm64-fallback.ll? I was able to hit the same problem with:

define i16 @f(half* %p) {
  %tmp0 = load half, half* %p
  %tmp1 = fptoui half %tmp0 to i16
  ret i16 %tmp1
}

[aditya_nandakumar]

Committed in 299802

include/llvm/CodeGen/GlobalISel/LegalizerHelper.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_GLOBALISEL_MACHINELEGALIZEHELPER_H
 #define LLVM_CODEGEN_GLOBALISEL_MACHINELEGALIZEHELPER_H
 
 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/LowLevelType.h"
 
 namespace llvm {
 // Forward declarations.
 class LegalizerInfo;
 class Legalizer;
 class MachineRegisterInfo;
 
 class LegalizerHelper {
 public:
   enum LegalizeResult {
     /// Instruction was already legal and no change was made to the
     /// MachineFunction.
     AlreadyLegal,
 
     /// Instruction has been legalized and the MachineFunction changed.
     Legalized,
 
     /// Some kind of error has occurred and we could not legalize this
     /// instruction.
     UnableToLegalize,
   };
 
   LegalizerHelper(MachineFunction &MF);
 
   /// Replace \p MI by a sequence of legal instructions that can implement the
   /// same operation. Note that this means \p MI may be deleted, so any iterator
   /// steps should be performed before calling this function. \p Helper should
   /// be initialized to the MachineFunction containing \p MI.
   ///
   /// Considered as an opaque blob, the legal code will use and define the same
   /// registers as \p MI.
   LegalizeResult legalizeInstrStep(MachineInstr &MI);
 
-  LegalizeResult legalizeInstr(MachineInstr &MI);
-
   /// Legalize an instruction by emiting a runtime library call instead.
   LegalizeResult libcall(MachineInstr &MI);
 
   /// Legalize an instruction by reducing the width of the underlying scalar
   /// type.
   LegalizeResult narrowScalar(MachineInstr &MI, unsigned TypeIdx, LLT NarrowTy);
 
   /// Legalize an instruction by performing the operation on a wider scalar type
public:
   LegalizeResult fewerElementsVector(MachineInstr &MI, unsigned TypeIdx,
                                      LLT NarrowTy);
 
   /// Legalize a vector instruction by increasing the number of vector elements
   /// involved and ignoring the added elements later.
   LegalizeResult moreElementsVector(MachineInstr &MI, unsigned TypeIdx,
                                     LLT WideTy);
 
+  /// Expose MIRBuilder so clients can set their own RecordInsertInstruction
+  /// functions
+  MachineIRBuilder MIRBuilder;
+
 private:
 
   /// Helper function to split a wide generic register into bitwise blocks with
   /// the given Type (which implies the number of blocks needed). The generic
   /// registers created are appended to Ops, starting at bit 0 of Reg.
   void extractParts(unsigned Reg, LLT Ty, int NumParts,
                     SmallVectorImpl<unsigned> &Ops);
 
-  MachineIRBuilder MIRBuilder;
   MachineRegisterInfo &MRI;
   const LegalizerInfo &LI;
 };
 
 } // End namespace llvm.
 
 #endif

lib/CodeGen/GlobalISel/Legalizer.cpp

for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
       // Get the next Instruction before we try to legalize, because there's a
       // good chance MI will be deleted.
       NextMI = std::next(MI);
 
       // Only legalize pre-isel generic instructions: others don't have types
       // and are assumed to be legal.
       if (!isPreISelGenericOpcode(MI->getOpcode()))
         continue;
-
-      auto Res = Helper.legalizeInstr(*MI);
-
-      // Error out if we couldn't legalize this instruction. We may want to fall
+      SmallVector<MachineInstr *, 4> WorkList;
+      Helper.MIRBuilder.recordInsertions(
+          [&](MachineInstr *MI) { WorkList.push_back(MI); });
+      WorkList.push_back(&*MI);
+
+      LegalizerHelper::LegalizeResult Res;
+      unsigned Idx = 0;
+      do {
+        Res = Helper.legalizeInstrStep(*WorkList[Idx]);
+        // Error out if we couldn't legalize this instruction. We may want to
+        // fall
         // back to DAG ISel instead in the future.
         if (Res == LegalizerHelper::UnableToLegalize) {
+          Helper.MIRBuilder.stopRecordingInsertions();
+          if (Res == LegalizerHelper::UnableToLegalize) {
             reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
-                           "unable to legalize instruction", *MI);
+                               "unable to legalize instruction",
+                               *WorkList[Idx]);
             return false;
           }
-
-      Changed |= Res == LegalizerHelper::Legalized;
         }
+        Changed |= Res == LegalizerHelper::Legalized;
+        ++Idx;
+      } while (Idx < WorkList.size());
 
+      Helper.MIRBuilder.stopRecordingInsertions();
+    }
 
   MachineRegisterInfo &MRI = MF.getRegInfo();
   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
   for (auto &MBB : MF) {
     for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
       // Get the next Instruction before we try to legalize, because there's a
       // good chance MI will be deleted.
       NextMI = std::next(MI);
 
       Changed |= combineExtracts(*MI, MRI, TII);
       Changed |= combineMerges(*MI, MRI, TII);
     }
   }
 
   return Changed;
 }

lib/CodeGen/GlobalISel/LegalizerHelper.cpp

case LegalizerInfo::FewerElements:
     return fewerElementsVector(MI, std::get<1>(Action), std::get<2>(Action));
   case LegalizerInfo::Custom:
     return LI.legalizeCustom(MI, MRI, MIRBuilder) ? Legalized
                                                   : UnableToLegalize;
   default:
     return UnableToLegalize;
   }
 }
 
-LegalizerHelper::LegalizeResult
-LegalizerHelper::legalizeInstr(MachineInstr &MI) {
-  SmallVector<MachineInstr *, 4> WorkList;
-  MIRBuilder.recordInsertions(
-      [&](MachineInstr *MI) { WorkList.push_back(MI); });
-  WorkList.push_back(&MI);
-
-  bool Changed = false;
-  LegalizeResult Res;
-  unsigned Idx = 0;
-  do {
-    Res = legalizeInstrStep(*WorkList[Idx]);
-    if (Res == UnableToLegalize) {
-      MIRBuilder.stopRecordingInsertions();
-      return UnableToLegalize;
-    }
-    Changed |= Res == Legalized;
-    ++Idx;
-  } while (Idx < WorkList.size());
-
-  MIRBuilder.stopRecordingInsertions();
-
-  return Changed ? Legalized : AlreadyLegal;
-}
-
 void LegalizerHelper::extractParts(unsigned Reg, LLT Ty, int NumParts,
                                    SmallVectorImpl<unsigned> &VRegs) {
   for (int i = 0; i < NumParts; ++i)
     VRegs.push_back(MRI.createGenericVirtualRegister(Ty));
   MIRBuilder.buildUnmerge(VRegs, Reg);
 }
 
 static RTLIB::Libcall getRTLibDesc(unsigned Opcode, unsigned Size) {
   switch (Opcode) {
   case TargetOpcode::G_FREM:
     return Size == 64 ? RTLIB::REM_F64 : RTLIB::REM_F32;
   case TargetOpcode::G_FPOW: