[FastISel] Don't trivially kill extractvalues (PR49467)

[nikic]

Summary

All extractvalues of the same value at the same index will map to the same register, so even if one specific extractvalue only has one use, we should not mark it as a trivial kill, as there may be more extractvalues later.

Fixes https://bugs.llvm.org/show_bug.cgi?id=49467.

[nagisa]

This seems like a reasonable fix, whatever value my review of fastisel code has.

This issue seems likely to show up for other instructions in the future, as well. Some that come to mind as likely to trigger this same bug are: gep, freeze, phi, select, extractelement (not currently supported by fastisel),

[spatel]

I don't know this well, so a couple of drive-by comments inline.
@craig.topper or @RKSimon should have a look.

llvm/lib/CodeGen/SelectionDAG/FastISel.cpp

241

The header comment for this function only says:

/// Test whether the given value has exactly one use.

That should be updated with a little more detail about the logic and usage.

llvm/test/CodeGen/X86/pr49467.ll

3

Does it make sense to specify the point-of-failure in the RUN line more explicitly with something like:

-fast-isel -optimize-regalloc=0

[nikic]

Expand comment on hasTrivialKill(), explicitly specify -fast-isel in test.

[nikic]

llvm/lib/CodeGen/SelectionDAG/FastISel.cpp

241

I expanded the comment a bit -- hopefully it makes sense, as I'm also not familiar with this code.

llvm/test/CodeGen/X86/pr49467.ll

3

I've added the -fast-isel flag, but don't think that -optimize-regalloc=0 is really relevant here, in that the problem manifests before that and is caught by -verify-machineinstrs (although FastRA would also assert).

[craig.topper]

llvm/lib/CodeGen/SelectionDAG/FastISel.cpp

273–274

Should this list of exception opcodes just be hoisted up to its own if+"return false" with a more directed comment? It's not important that we check I->hasOneUse() before them is it?

[nikic]

Move instruction type checks into separate condition.

[nikic]

This patch is intended as a minimal fix for LLVM 12. For the main branch, I think we should rip out the whole kill tracking in FastISel entirely. FastRA can determine kills itself, and at least in my test, there is no negative compile-time impact to letting it do so. Maybe this used to be different, but currently the hasTrivialKill functionality seems to be unnecessary complexity.

[craig.topper]

LGTM

llvm/include/llvm/CodeGen/FastISel.h

protected:
   ///
   /// \c Add can be folded into \c GEP if:
   /// - \c Add is an add,
   /// - \c Add's size matches \c GEP's,
   /// - \c Add is in the same basic block as \c GEP, and
   /// - \c Add has a constant operand.
   bool canFoldAddIntoGEP(const User *GEP, const Value *Add);
 
-  /// Test whether the given value has exactly one use.
+  /// Test whether the register associated with this value has exactly one use,
+  /// in which case that single use is killing. Note that multiple IR values
+  /// may map onto the same register, in which case this is not the same as
+  /// checking that an IR value has one use.
   bool hasTrivialKill(const Value *V);
 
   /// Create a machine mem operand from the given instruction.
   MachineMemOperand *createMachineMemOperandFor(const Instruction *I) const;
 
   CmpInst::Predicate optimizeCmpPredicate(const CmpInst *CI) const;
 
   bool lowerCallTo(const CallInst *CI, MCSymbol *Symbol, unsigned NumArgs);

llvm/lib/CodeGen/SelectionDAG/FastISel.cpp

void FastISel::flushLocalValueMap() {
   }
 
   LocalValueMap.clear();
   LastLocalValue = EmitStartPt;
   recomputeInsertPt();
   SavedInsertPt = FuncInfo.InsertPt;
 }
 
 bool FastISel::hasTrivialKill(const Value *V) {
   // Don't consider constants or arguments to have trivial kills.
   const Instruction *I = dyn_cast<Instruction>(V);
   if (!I)
     return false;
 
   // No-op casts are trivially coalesced by fast-isel.
   if (const auto *Cast = dyn_cast<CastInst>(I))
     if (Cast->isNoopCast(DL) && !hasTrivialKill(Cast->getOperand(0)))
       return false;
 
   // Even the value might have only one use in the LLVM IR, it is possible that
   // FastISel might fold the use into another instruction and now there is more
   // than one use at the Machine Instruction level.
   Register Reg = lookUpRegForValue(V);
   if (Reg && !MRI.use_empty(Reg))
     return false;
 
   // GEPs with all zero indices are trivially coalesced by fast-isel.
   if (const auto *GEP = dyn_cast<GetElementPtrInst>(I))
     if (GEP->hasAllZeroIndices() && !hasTrivialKill(GEP->getOperand(0)))
       return false;
 
+  // Casts and extractvalues may be trivially coalesced by fast-isel.
+  if (I->getOpcode() == Instruction::BitCast ||
+      I->getOpcode() == Instruction::PtrToInt ||
+      I->getOpcode() == Instruction::IntToPtr ||
+      I->getOpcode() == Instruction::ExtractValue)
+    return false;
+
   // Only instructions with a single use in the same basic block are considered
   // to have trivial kills.
   return I->hasOneUse() &&
-         !(I->getOpcode() == Instruction::BitCast ||
-           I->getOpcode() == Instruction::PtrToInt ||
-           I->getOpcode() == Instruction::IntToPtr) &&
          cast<Instruction>(*I->user_begin())->getParent() == I->getParent();
 }
 
 Register FastISel::getRegForValue(const Value *V) {
   EVT RealVT = TLI.getValueType(DL, V->getType(), /*AllowUnknown=*/true);
   // Don't handle non-simple values in FastISel.
   if (!RealVT.isSimple())
     return Register();
 

llvm/test/CodeGen/X86/pr49467.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -O0 -fast-isel -verify-machineinstrs -mtriple=x86_64 < %s | FileCheck %s
+
+declare { i8*, i64 } @get()
+
+declare void @use(i8*, i64)
+
+define void @test(i64* %p) nounwind {
+; CHECK-LABEL: test:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    pushq %rax
+; CHECK-NEXT:    movq %rdi, (%rsp) # 8-byte Spill
+; CHECK-NEXT:    callq get@PLT
+; CHECK-NEXT:    movq (%rsp), %rdi # 8-byte Reload
+; CHECK-NEXT:    movq %rdx, %rsi
+; CHECK-NEXT:    movq %rsi, (%rdi)
+; CHECK-NEXT:    # implicit-def: $rdi
+; CHECK-NEXT:    callq use@PLT
+; CHECK-NEXT:    popq %rax
+; CHECK-NEXT:    retq
+  %struct = call { i8*, i64 } @get()
+  %struct.1 = extractvalue { i8*, i64 } %struct, 1
+  store i64 %struct.1, i64* %p, align 8
+  %struct.2 = extractvalue { i8*, i64 } %struct, 1
+  call void @use(i8* undef, i64 %struct.2)
+  ret void
+}