[AMDGPU] Prevent spills before exec mask is restored

[rampitec]

Summary

Inline spiller can decide to move a spill as early as possible in the basic block. It will skip phis and label, but we also need to make sure it skips instructions in the basic block prologue which restore exec mask.

Added isPositionLike callback in TargetInstrInfo to detect instructions which shall be skipped in addition to common phis, labels etc.

[arsenm]

lib/Target/AMDGPU/SIInstrInfo.cpp

3647–3650 ↗

(On Diff #82139)

The modifiesRegister check should be last. This can also be simplified to return X instead of if (X) return true. You also might be able to combine this with isSchedulingBoundary

[qcolombet]

include/llvm/Target/TargetInstrInfo.h

1515 ↗

(On Diff #82139)

For the comment, I would use the same terminology as MachineInstr::isPosition. Right now, the comment seems off compared to the function name.
Also, would it make sense to have this flag exposed in the TDs?

[rampitec]

1. Changed comment on the callback.
2. Rearranged conditions check in the SIInstrInfo::isPositionLike()

[rampitec]

include/llvm/Target/TargetInstrInfo.h

1515 ↗

(On Diff #82139)

Fixed comment.
I thought about exposing the flag in TD, but it is not always can be expressed that way. The same instruction can be used at the end of a basic block, so this in fact does not necessarily depend on the instruction only.

[rampitec]

include/llvm/Target/TargetInstrInfo.h

1515 ↗

(On Diff #82139)

And then instructions themselves are just a scalar or/and/xor etc, they just happen to write exec mask register. If exposed through a bit in TD all of them would need to be duplicated as pseudo and expanded past RA, which is clearly more definitions and more code.

[MatzeB]

In general I find rules like "no spill may be before a isPositionLike() instruction" dangerous in that they are not at all obvious to people writing generic codegen passes and you run the danger that even if you fix the register allocator other passes may disregard the new rule.

Have you considered alternative solutions? Like having a late pass that moves your exec mask back to the top in a late pass so that the exec mask rules only need to be known by that one pass?

[rampitec]

In D27997#633402, @MatzeB wrote:

In general I find rules like "no spill may be before a isPositionLike() instruction" dangerous in that they are not at all obvious to people writing generic codegen passes and you run the danger that even if you fix the register allocator other passes may disregard the new rule.

Have you considered alternative solutions? Like having a late pass that moves your exec mask back to the top in a late pass so that the exec mask rules only need to be known by that one pass?

I have started with exploring alternative solutions which do not require any target callbacks. That turns to be pretty difficult and dangerous. Not only that is extremely tricky to recover, but also creates some paradoxes, like if I need a register being spilled before the new insertion point. Also instructions which operate exec mask are all the same at the beginning of a BB and at the end, and in case of a small BB that would be too late to distinguish. The safest solution is not to recover from broken IR, but prevent the problem at the first place.

Regarding other passes which might do the same, I'm not aware of them. Machine instructions have all bits like side effects and register use-def dependencies set, so no pass (like LICM for example) can illegally rearrange them. That is in particular difficult to recover from wrong spilling, because I would have to perform formally illegal transformations. Only the regalloc is a problem because it does not try to rearrange instructions, it just inserts new.

[MatzeB]

In D27997#634166, @rampitec wrote:

In D27997#633402, @MatzeB wrote:

In general I find rules like "no spill may be before a isPositionLike() instruction" dangerous in that they are not at all obvious to people writing generic codegen passes and you run the danger that even if you fix the register allocator other passes may disregard the new rule.

Have you considered alternative solutions? Like having a late pass that moves your exec mask back to the top in a late pass so that the exec mask rules only need to be known by that one pass?

I have started with exploring alternative solutions which do not require any target callbacks. That turns to be pretty difficult and dangerous. Not only that is extremely tricky to recover, but also creates some paradoxes, like if I need a register being spilled before the new insertion point. Also instructions which operate exec mask are all the same at the beginning of a BB and at the end, and in case of a small BB that would be too late to distinguish. The safest solution is not to recover from broken IR, but prevent the problem at the first place.

Regarding other passes which might do the same, I'm not aware of them. Machine instructions have all bits like side effects and register use-def dependencies set, so no pass (like LICM for example) can illegally rearrange them. That is in particular difficult to recover from wrong spilling, because I would have to perform formally illegal transformations. Only the regalloc is a problem because it does not try to rearrange instructions, it just inserts new.

Ok so if I understand this correctly the dependencies are actually visible by means of defs/uses of some mask register, this only affects spill placement code just because it is not obvious that a spill instruction will read the mask register and before actually creating it?

I don't like the name isPositionLike(). The semantic do not seem to be too similar to isPosition() which are instructions that mark a place in a function that is somehow visible elsewhere (because of exception handling tables, ...), this is not the case here. Also if the only use of this function is fixing a spill code placement problem, then the documentation comment should mention that.

[rampitec]

In D27997#637109, @MatzeB wrote:

Ok so if I understand this correctly the dependencies are actually visible by means of defs/uses of some mask register, this only affects spill placement code just because it is not obvious that a spill instruction will read the mask register and before actually creating it?

Yes.

I don't like the name isPositionLike(). The semantic do not seem to be too similar to isPosition() which are instructions that mark a place in a function that is somehow visible elsewhere (because of exception handling tables, ...), this is not the case here.

Will the "isBasicBlockPrologue()" name be better?

Also if the only use of this function is fixing a spill code placement problem, then the documentation comment should mention that.

OK, will add comment.

[rampitec]

• Renamed callback.
• Modified comment.

[rampitec]

Ping.

[rampitec]

Ping

[arsenm]

lib/Target/AMDGPU/SIInstrInfo.cpp

3644 ↗

(On Diff #83287)

There are some weird graphics intrinsics that end up with exec modifications in the middle of the block (I was working towards splitting the blocks at these points, but I'm not sure it's generally possible. For the purposes of this hook, it's probably good enough. I'm not sure I have any better name ideas

3645–3648 ↗

(On Diff #83287)

You can access the RI member directly in SIInstrInfo

[rampitec]

Use existing SIInstrInfo::RI instead of querying TRI.

[MatzeB]

All of this feels a bit odd still, but I don't have any better suggestion right now, so LGTM.

llvm/trunk/include/llvm/Target/TargetInstrInfo.h

getSerializableBitmaskMachineOperandTargetFlags() const {
     return None;
   }
 
   /// Determines whether |Inst| is a tail call instruction.
   virtual bool isTailCall(const MachineInstr &Inst) const {
     return false;
   }
 
+  /// True if the instruction is bound to the top of its basic block and no
+  /// other instructions shall be inserted before it. This can be implemented
+  /// to prevent register allocator to insert spills before such instructions.
+  virtual bool isBasicBlockPrologue(const MachineInstr &MI) const {
+    return false;
+  }
+
 private:
   unsigned CallFrameSetupOpcode, CallFrameDestroyOpcode;
   unsigned CatchRetOpcode;
   unsigned ReturnOpcode;
 };
 
 /// \brief Provide DenseMapInfo for TargetInstrInfo::RegSubRegPair.
 template<>

llvm/trunk/lib/CodeGen/MachineBasicBlock.cpp

while (I != E && I->isPHI())
     ++I;
   assert((I == E || !I->isInsideBundle()) &&
          "First non-phi MI cannot be inside a bundle!");
   return I;
 }
 
 MachineBasicBlock::iterator
 MachineBasicBlock::SkipPHIsAndLabels(MachineBasicBlock::iterator I) {
+  const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
+
   iterator E = end();
-  while (I != E && (I->isPHI() || I->isPosition()))
+  while (I != E && (I->isPHI() || I->isPosition() ||
+                    TII->isBasicBlockPrologue(*I)))
     ++I;
   // FIXME: This needs to change if we wish to bundle labels
   // inside the bundle.
   assert((I == E || !I->isInsideBundle()) &&
          "First non-phi / non-label instruction is inside a bundle!");
   return I;
 }
 
 MachineBasicBlock::iterator
 MachineBasicBlock::SkipPHIsLabelsAndDebug(MachineBasicBlock::iterator I) {
+  const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
+
   iterator E = end();
-  while (I != E && (I->isPHI() || I->isPosition() || I->isDebugValue()))
+  while (I != E && (I->isPHI() || I->isPosition() || I->isDebugValue() ||
+                    TII->isBasicBlockPrologue(*I)))
     ++I;
   // FIXME: This needs to change if we wish to bundle labels / dbg_values
   // inside the bundle.
   assert((I == E || !I->isInsideBundle()) &&
          "First non-phi / non-label / non-debug "
          "instruction is inside a bundle!");
   return I;
 }

llvm/trunk/lib/Target/AMDGPU/SIInstrInfo.h

public:
   getSerializableTargetIndices() const override;
 
   ScheduleHazardRecognizer *
   CreateTargetPostRAHazardRecognizer(const InstrItineraryData *II,
                                  const ScheduleDAG *DAG) const override;
 
   ScheduleHazardRecognizer *
   CreateTargetPostRAHazardRecognizer(const MachineFunction &MF) const override;
+
+  bool isBasicBlockPrologue(const MachineInstr &MI) const override;
 };
 
 namespace AMDGPU {
   LLVM_READONLY
   int getVOPe64(uint16_t Opcode);
 
   LLVM_READONLY
   int getVOPe32(uint16_t Opcode);

llvm/trunk/lib/Target/AMDGPU/SIInstrInfo.cpp

 }
 
 /// This is the hazard recognizer used at -O0 by the PostRAHazardRecognizer
 /// pass.
 ScheduleHazardRecognizer *
 SIInstrInfo::CreateTargetPostRAHazardRecognizer(const MachineFunction &MF) const {
   return new GCNHazardRecognizer(MF);
 }
+
+bool SIInstrInfo::isBasicBlockPrologue(const MachineInstr &MI) const {
+  return !MI.isTerminator() && MI.getOpcode() != AMDGPU::COPY &&
+         MI.modifiesRegister(AMDGPU::EXEC, &RI);
+}

llvm/trunk/test/CodeGen/AMDGPU/spill-cfg-position.ll

+; RUN: llc -march=amdgcn -verify-machineinstrs -stress-regalloc=6 < %s | FileCheck %s
+
+; Inline spiller can decide to move a spill as early as possible in the basic block.
+; It will skip phis and label, but we also need to make sure it skips instructions
+; in the basic block prologue which restore exec mask.
+; Make sure instruction to restore exec mask immediately follows label
+
+; CHECK-LABEL: {{^}}spill_cfg_position:
+; CHECK: s_cbranch_execz [[LABEL1:BB[0-9_]+]]
+; CHECK: {{^}}[[LABEL1]]:
+; CHECK: s_cbranch_execz [[LABEL2:BB[0-9_]+]]
+; CHECK: {{^}}[[LABEL2]]:
+; CHECK-NEXT: s_or_b64 exec
+; CHECK: buffer_
+
+define void @spill_cfg_position(i32 addrspace(1)* nocapture %arg) {
+bb:
+  %tmp1 = tail call i32 @llvm.amdgcn.workitem.id.x() #0
+  %tmp14 = load i32, i32 addrspace(1)* %arg, align 4
+  %tmp15 = getelementptr inbounds i32, i32 addrspace(1)* %arg, i64 1
+  %tmp16 = load i32, i32 addrspace(1)* %tmp15, align 4
+  %tmp17 = getelementptr inbounds i32, i32 addrspace(1)* %arg, i64 2
+  %tmp18 = load i32, i32 addrspace(1)* %tmp17, align 4
+  %tmp19 = getelementptr inbounds i32, i32 addrspace(1)* %arg, i64 3
+  %tmp20 = load i32, i32 addrspace(1)* %tmp19, align 4
+  %tmp21 = getelementptr inbounds i32, i32 addrspace(1)* %arg, i64 4
+  %tmp22 = load i32, i32 addrspace(1)* %tmp21, align 4
+  %tmp23 = getelementptr inbounds i32, i32 addrspace(1)* %arg, i64 5
+  %tmp24 = load i32, i32 addrspace(1)* %tmp23, align 4
+  %tmp25 = getelementptr inbounds i32, i32 addrspace(1)* %arg, i64 6
+  %tmp26 = load i32, i32 addrspace(1)* %tmp25, align 4
+  %tmp27 = getelementptr inbounds i32, i32 addrspace(1)* %arg, i64 7
+  %tmp28 = load i32, i32 addrspace(1)* %tmp27, align 4
+  %tmp29 = getelementptr inbounds i32, i32 addrspace(1)* %arg, i64 8
+  %tmp30 = load i32, i32 addrspace(1)* %tmp29, align 4
+  %tmp33 = getelementptr inbounds i32, i32 addrspace(1)* %arg, i32 %tmp1
+  %tmp34 = load i32, i32 addrspace(1)* %tmp33, align 4
+  %tmp35 = icmp eq i32 %tmp34, 0
+  br i1 %tmp35, label %bb44, label %bb36
+
+bb36:                                             ; preds = %bb
+  %tmp37 = mul nsw i32 %tmp20, %tmp18
+  %tmp38 = add nsw i32 %tmp37, %tmp16
+  %tmp39 = mul nsw i32 %tmp24, %tmp22
+  %tmp40 = add nsw i32 %tmp38, %tmp39
+  %tmp41 = mul nsw i32 %tmp28, %tmp26
+  %tmp42 = add nsw i32 %tmp40, %tmp41
+  %tmp43 = add nsw i32 %tmp42, %tmp30
+  br label %bb52
+
+bb44:                                             ; preds = %bb
+  %tmp45 = mul nsw i32 %tmp18, %tmp16
+  %tmp46 = mul nsw i32 %tmp22, %tmp20
+  %tmp47 = add nsw i32 %tmp46, %tmp45
+  %tmp48 = mul nsw i32 %tmp26, %tmp24
+  %tmp49 = add nsw i32 %tmp47, %tmp48
+  %tmp50 = mul nsw i32 %tmp30, %tmp28
+  %tmp51 = add nsw i32 %tmp49, %tmp50
+  br label %bb52
+
+bb52:                                             ; preds = %bb44, %bb36
+  %tmp53 = phi i32 [ %tmp43, %bb36 ], [ %tmp51, %bb44 ]
+  %tmp54 = mul nsw i32 %tmp16, %tmp14
+  %tmp55 = mul nsw i32 %tmp22, %tmp18
+  %tmp56 = mul nsw i32 %tmp24, %tmp20
+  %tmp57 = mul nsw i32 %tmp30, %tmp26
+  %tmp58 = add i32 %tmp55, %tmp54
+  %tmp59 = add i32 %tmp58, %tmp56
+  %tmp60 = add i32 %tmp59, %tmp28
+  %tmp61 = add i32 %tmp60, %tmp57
+  %tmp62 = add i32 %tmp61, %tmp53
+  store i32 %tmp62, i32 addrspace(1)* %tmp33, align 4
+  ret void
+}
+
+declare i32 @llvm.amdgcn.workitem.id.x() #0
+
+attributes #0 = { nounwind readnone }