SILoadStoreOptimizer pass schedules s_add,s_addc with interfering s_lshl

[ronlieb]

Summary

A 64 bit add implimented with two 32 bit add instructions uses the
$SCC register for carry.  The S_LSHL_B32 instruction write the $SCC reg
Pass was incorrectly transforming
  S_LSHL_B32
  S_ADD_U32
  S_ADDC_U32
into
  S_ADD_U32
  S_LSHL_B32
  S_ADDC_U32

SILoadStoreOptimizer constructs a list of instructions to move and did
not take into account the dependent S_ADD_u32 instruction when it chose
to move the S_ADDC_U32 instruction.

[arsenm]

You should use computeRegisterLiveness instead of adding a more naive search for a def, which may not exist.

The testcase can also be a lot simpler (and should probable be MIR)

test/CodeGen/AMDGPU/scc-add-lshl-addc.ll

79

I doubt you need any of this metadata

[ronlieb]

test will convert to MIR form.
Patch will change to use computeRegisterLiveness. i will have to use a pretty large neighborhood , as the original code this error occurred in (before running bugpoint) , had the s_add_u32 instruction was separated by over 400 instructions from the s_addc_u32 instruction. We will assert fail if we cannot find the s_add_u32 instruction, so that will alert us to increase neighborhood size. This patch will also handle the corresponding sub instructions.

test/CodeGen/AMDGPU/scc-add-lshl-addc.ll

79

it should vanish once i convert test to MIR form

[ronlieb]

correction: the original input test did NOT have the instructions separated by more than 1 or 2 instructions The resultant output showed the large separation.
The default neighborhood of 10 is probably more than enough.

[ronlieb]

after looking at the suggestion of using computeRegisterLiveness, I noticed that it does not return the MI where the register in question is most recently defined.
Rather, it informs on liveness within a range. I don’t really see how I would use this method effectively?
The problem I am trying to solve requires identifying a specific instruction that is needed by a subsequent instruction and then adding the identified instruction to a list constructed by SILoadStoreOptimizer.

Regarding the lit test, i cleaned it up quite a bit and will post a new version shortly.
I will create a .MIR test from this to specifically test the SILoadStoreOptimizer pass in a direct fashion.
Any objection to keeping the the .ll test after the MIR test is added?

[rampitec]

In D60459#1459784, @ronlieb wrote:

correction: the original input test did NOT have the instructions separated by more than 1 or 2 instructions The resultant output showed the large separation.
The default neighborhood of 10 is probably more than enough.

This is correction issue, not performance. Any kind of threshold is an error. If you did not find the def you probably need to bail.

lib/Target/AMDGPU/SILoadStoreOptimizer.cpp

276

It can be defined in another block. It can be also undef.

[ronlieb]

lib/Target/AMDGPU/SILoadStoreOptimizer.cpp

276

Splitting a pair of instructions across basic block boundaries in this situation seems really crazy. These instruction pairs are implementing a 64 bit add or 64 bit subtract. I understand that generally speaking we could see both situations (split or under). If this were to occur in this pass, i would want to assert (which is what this patch will do) so we can go look into it, rather than having broken code generated. To split them would mean that $SCC is live in to the block.

[rampitec]

lib/Target/AMDGPU/SILoadStoreOptimizer.cpp

276

Why not? What if half of that pair was hoisted out of the block into parent?

[ronlieb]

i agree it could happen. Not sure what to do about it here.

[ronlieb]

The current problem i am trying to resolve in somewhat analogous to hoisting 1/2 of the 64 bit add instruction pair. Although in this particular situation we are actually sinking 1/2 of the instruction pair into a later position within the same block. And yes, i can see how in the future a new machine instruction pass might choose to hoist one of the instructions into a pred BB. I realize i can write additional code to scan a previous block. However i think its better that passes not hoist part of an instruction pair, especially ones such as these. To that end i would rather see my patch assert so that we are forced to deal with such a situation should it arise.
Your example, btw, is a good one for why we should have an IR test for the current problem, rather than an MIR test. An MIR test that runs just before SILoadStoreOptimizer will not detect the affects of a new pass. Whereas the IR test attached to this patch stands a better chance of detecting the issue.

[rampitec]

In D60459#1460563, @ronlieb wrote:

The current problem i am trying to resolve in somewhat analogous to hoisting 1/2 of the 64 bit add instruction pair. Although in this particular situation we are actually sinking 1/2 of the instruction pair into a later position within the same block. And yes, i can see how in the future a new machine instruction pass might choose to hoist one of the instructions into a pred BB. I realize i can write additional code to scan a previous block. However i think its better that passes not hoist part of an instruction pair, especially ones such as these. To that end i would rather see my patch assert so that we are forced to deal with such a situation should it arise.
Your example, btw, is a good one for why we should have an IR test for the current problem, rather than an MIR test. An MIR test that runs just before SILoadStoreOptimizer will not detect the affects of a new pass. Whereas the IR test attached to this patch stands a better chance of detecting the issue.

Why not just bail the optimization if you didn't find a def reasonable close?

[ronlieb]

i think bailing the optimization if not found within some reasonable distance (10 seems to be popular), is a good suggestion. Much better than aborting. thx

[ronlieb]

Added check for instr match missing, and bail on optimization if so.
I prefer the .ll test we have for the patch now over that of creating an MIR test for this issue.

[rampitec]

lib/Target/AMDGPU/SILoadStoreOptimizer.cpp

305

Does that really mean to bail? Check the uses.
You also need a test where you did not find the pair, a mir test.

[ronlieb]

lib/Target/AMDGPU/SILoadStoreOptimizer.cpp

305

i see what you mean about the bail and uses , thx.
good suggestion for the mir test. will add

[ronlieb]

added two MIR tests,and refined logic to properly bail.

[rampitec]

lib/Target/AMDGPU/SILoadStoreOptimizer.cpp

271

Having i and I variables in the same statement is quite misleading.

test/CodeGen/AMDGPU/scc-missing-add.mir

1 ↗

(On Diff #194514)

You can combine both mir tests into a single file and significantly reduce them. For example you do not need all of the IR.

[ronlieb]

test/CodeGen/AMDGPU/scc-missing-add.mir

1 ↗

(On Diff #194514)

after playing with trying to reduce the IR, I don't really think I can.
This particular pass seems sensitive to PC relative references within the MIR that are defined within the IR, and other symbol references as well.

It sort of falls into this category as described in the MIR documentation:

MIR code contains a whole IR module. This is necessary because there are no equivalents in MIR for global variables, references to external functions, function attributes, metadata, debug info. Instead some MIR data references the IR constructs. You can often remove them if the test doesn’t depend on them.

And the above really complicates trying to merge the two tests into one.

[arsenm]

test/CodeGen/AMDGPU/scc-has-add.mir

10–12 ↗

(On Diff #194514)

You can drop the block names, and IR references in the MMOs to drop the IR section

113–115 ↗

(On Diff #194514)

You can strip out a lot of instructions too. Usually I just create a smaller, totally artificial test case from scratch

[ronlieb]

test/CodeGen/AMDGPU/scc-has-add.mir

10–12 ↗

(On Diff #194514)

The SILoadStoreOptimizer pass depends on Alias analysis on memory references as part of its decision to collect a group of instructions. So when i attempt to removes this information from the MIR, the test does not reproduce the issue. Similiarly, trying to remove the IR section also introduces issues with reproducing the issue, as their are PC relative definitions needed in the MIR test. So i think i need to keep the MIR test as is with a bit of cleanup. Also, since the scc-has-add.mir .test closely replicates the scc-add-lshl-addc.ll test, i plan to keep the .ll test, dump the scc-has-add.mir test, and keep the scc-missing-add,mir test.

[ronlieb]

slightly generalized to some physical reg. only look at previous instruction.
The definition is either there, and were all good, or we will bail.

[ronlieb]

Added use of LivePhysRegs, happily lifted some code Krzy wrote for Hexagon to compute getLiveRegsAt.

[arsenm]

lib/Target/AMDGPU/SILoadStoreOptimizer.cpp

196

Capitalize

200–201

Indentation

270–271

This is going to do a ~full scan of the block for every analyzed instruction, so this ends up being O(N^2). I was thinking more a single LivePhysReg instance for the entire block visit, which is lazily moved to the current point as necessary

293

This may not be broad enough. It only covers full defs. Usually modifiesRegister is what you want

297–301

The idea with using LivePhysRegs is to stop using this custom PhysRegUses set

300

The implicitness doesn't matter

[nhaehnle]

I wonder if this is related to D61313?

[ronlieb]

Superseded by D61313

lib/Target/AMDGPU/SILoadStoreOptimizer.cpp

private:
   void processBaseWithConstOffset(const MachineOperand &Base, MemAddress &Addr);
   /// Promotes constant offset to the immediate by adjusting the base. It
   /// tries to use a base from the nearby instructions that allows it to have
   /// a 13bit constant offset which gets promoted to the immediate.
   bool promoteConstantOffsetToImm(MachineInstr &CI,
                                   MemInfoMap &Visited,
                                   SmallPtrSet<MachineInstr *, 4> &Promoted);
 
 public:
   static char ID;
 
   SILoadStoreOptimizer() : MachineFunctionPass(ID) {
     initializeSILoadStoreOptimizerPass(*PassRegistry::getPassRegistry());
   }
 
   bool optimizeBlock(MachineBasicBlock &MBB);
 
   bool runOnMachineFunction(MachineFunction &MF) override;
 
   StringRef getPassName() const override { return "SI Load Store Optimizer"; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
static bool memAccessesCanBeReordered(MachineBasicBlock::iterator A,
                                       MachineBasicBlock::iterator B,
                                       AliasAnalysis *AA) {
   // RAW or WAR - cannot reorder
   // WAW - cannot reorder
   // RAR - safe to reorder
   return !(A->mayStore() || B->mayStore()) || !A->mayAlias(AA, *B, true);
 }
 
+// Find the associated instruction which sets SCC for an MI.
+static MachineInstr *addSCCDependInstr(MachineInstr &MI) {
+  if (!MI.hasRegisterImplicitUseOperand(AMDGPU::SCC))
+    return nullptr;
+
+  MachineBasicBlock::reverse_iterator I = MI, E = MI.getParent()->rend();
+  I++;
+  for (; I != E; ++I)
+    if (I->definesRegister(AMDGPU::SCC))
+      return &*I;
+  assert(0 && "Failed to find carry instr");
+  return nullptr;
+}
+
 // Add MI and its defs to the lists if MI reads one of the defs that are
 // already in the list. Returns true in that case.
 static bool addToListsIfDependent(MachineInstr &MI, DenseSet<unsigned> &RegDefs,
                                   DenseSet<unsigned> &PhysRegUses,
                                   SmallVectorImpl<MachineInstr *> &Insts) {
   for (MachineOperand &Use : MI.operands()) {
     // If one of the defs is read, then there is a use of Def between I and the
     // instruction that I will potentially be merged with. We will need to move
     // this instruction after the merged instructions.
     //
     // Similarly, if there is a def which is read by an instruction that is to
     // be moved for merging, then we need to move the def-instruction as well.
     // This can only happen for physical registers such as M0; virtual
     // registers are in SSA form.
     if (Use.isReg() &&
         ((Use.readsReg() && RegDefs.count(Use.getReg())) ||
          (Use.isDef() && TargetRegisterInfo::isPhysicalRegister(Use.getReg()) &&
           PhysRegUses.count(Use.getReg())))) {
+      // If this MI depends on SCC, find and add defining instr.
+      MachineInstr *Prev = addSCCDependInstr(MI);
+      if (Prev)
+        Insts.push_back(&*Prev);
       Insts.push_back(&MI);
       addDefsUsesToList(MI, RegDefs, PhysRegUses);
       return true;
     }
   }
 
   return false;
 }
 
 static bool canMoveInstsAcrossMemOp(MachineInstr &MemOp,
                                     ArrayRef<MachineInstr *> InstsToMove,
                                     AliasAnalysis *AA) {

test/CodeGen/AMDGPU/scc-add-lshl-addc.ll

+; RUN: llc -mtriple=amdgcn-amd-amdhsa  -mattr=-code-object-v3 -disable-promote-alloca-to-lds -mcpu=gfx900 -amdgpu-dump-hsa-metadata %s -o - | FileCheck -check-prefix=CHECK %s
+
+; CHECK: s_add_u32
+; CHECK: s_addc_u32
+; CHECK: s_add_u32
+; CHECK: s_addc_u32
+; CHECK: s_add_u32
+; CHECK-NOT: s_lshl_b32
+; CHECK: s_addc_u32
+; CHECK: global_load_dword
+
+target datalayout = "e-p:64:64-p1:64:64-p2:32:32-p3:32:32-p4:64:64-p5:32:32-p6:32:32-i64:64-v16:16-v24:32-v32:32-v48:64-v96:128-v192:256-v256:256-v512:512-v1024:1024-v2048:2048-n32:64-S32-A5"
+target triple = "amdgcn-amd-amdhsa"
+
+%class.omptarget_nvptx_Queue.11.45.62.79.96.113.147.181.198.215.232.759.827.1031.1098 = type { [32 x %class.omptarget_nvptx_ThreadPrivateContext.10.44.61.78.95.112.146.180.197.214.231.758.826.1030.1097], [32 x %class.omptarget_nvptx_ThreadPrivateContext.10.44.61.78.95.112.146.180.197.214.231.758.826.1030.1097*], i32, [32 x i32], i32, [8 x i8] }
+%class.omptarget_nvptx_ThreadPrivateContext.10.44.61.78.95.112.146.180.197.214.231.758.826.1030.1097 = type { %class.omptarget_nvptx_TeamDescr.8.42.59.76.93.110.144.178.195.212.229.756.824.1028.1095, [1024 x %class.omptarget_nvptx_TaskDescr.3.37.54.71.88.105.139.173.190.207.224.751.819.1023.1090], [1024 x %class.omptarget_nvptx_TaskDescr.3.37.54.71.88.105.139.173.190.207.224.751.819.1023.1090*], %union.anon.9.43.60.77.94.111.145.179.196.213.230.757.825.1029.1096, [1024 x i32], [1024 x i64], [1024 x i64], [1024 x i64], [1024 x i64] }
+%class.omptarget_nvptx_TeamDescr.8.42.59.76.93.110.144.178.195.212.229.756.824.1028.1095 = type { %class.omptarget_nvptx_TaskDescr.3.37.54.71.88.105.139.173.190.207.224.751.819.1023.1090, %class.omptarget_nvptx_WorkDescr.4.38.55.72.89.106.140.174.191.208.225.752.820.1024.1091, i64, [8 x i8], [64 x %struct.__kmpc_data_sharing_worker_slot_static.6.40.57.74.91.108.142.176.193.210.227.754.822.1026.1093], [1 x %struct.__kmpc_data_sharing_master_slot_static.7.41.58.75.92.109.143.177.194.211.228.755.823.1027.1094] }
+%class.omptarget_nvptx_TaskDescr.3.37.54.71.88.105.139.173.190.207.224.751.819.1023.1090 = type { %"struct.omptarget_nvptx_TaskDescr::SavedLoopDescr_items.1.35.52.69.86.103.137.171.188.205.222.749.817.1021.1088", %"struct.omptarget_nvptx_TaskDescr::TaskDescr_items.2.36.53.70.87.104.138.172.189.206.223.750.818.1022.1089", %class.omptarget_nvptx_TaskDescr.3.37.54.71.88.105.139.173.190.207.224.751.819.1023.1090* }
+%"struct.omptarget_nvptx_TaskDescr::SavedLoopDescr_items.1.35.52.69.86.103.137.171.188.205.222.749.817.1021.1088" = type { i64, i64, i64, i64, i32 }
+%"struct.omptarget_nvptx_TaskDescr::TaskDescr_items.2.36.53.70.87.104.138.172.189.206.223.750.818.1022.1089" = type { i8, i8, i16, i16, i16, i16, i64 }
+%class.omptarget_nvptx_WorkDescr.4.38.55.72.89.106.140.174.191.208.225.752.820.1024.1091 = type { %class.omptarget_nvptx_TaskDescr.3.37.54.71.88.105.139.173.190.207.224.751.819.1023.1090 }
+%struct.__kmpc_data_sharing_worker_slot_static.6.40.57.74.91.108.142.176.193.210.227.754.822.1026.1093 = type { %struct.__kmpc_data_sharing_slot.5.39.56.73.90.107.141.175.192.209.226.753.821.1025.1092*, %struct.__kmpc_data_sharing_slot.5.39.56.73.90.107.141.175.192.209.226.753.821.1025.1092*, i8*, i8*, [16384 x i8] }
+%struct.__kmpc_data_sharing_slot.5.39.56.73.90.107.141.175.192.209.226.753.821.1025.1092 = type { %struct.__kmpc_data_sharing_slot.5.39.56.73.90.107.141.175.192.209.226.753.821.1025.1092*, %struct.__kmpc_data_sharing_slot.5.39.56.73.90.107.141.175.192.209.226.753.821.1025.1092*, i8*, i8*, [0 x i8] }
+%struct.__kmpc_data_sharing_master_slot_static.7.41.58.75.92.109.143.177.194.211.228.755.823.1027.1094 = type { %struct.__kmpc_data_sharing_slot.5.39.56.73.90.107.141.175.192.209.226.753.821.1025.1092*, %struct.__kmpc_data_sharing_slot.5.39.56.73.90.107.141.175.192.209.226.753.821.1025.1092*, i8*, i8*, [256 x i8] }
+%union.anon.9.43.60.77.94.111.145.179.196.213.230.757.825.1029.1096 = type { [1024 x i16] }
+%class.omptarget_nvptx_SharedArgs.16.50.67.84.101.118.152.186.203.220.237.764.832.1036.1099 = type <{ [20 x i8*], i8**, i32, [4 x i8] }>
+
+@omptarget_nvptx_device_State = external addrspace(1) externally_initialized global [64 x %class.omptarget_nvptx_Queue.11.45.62.79.96.113.147.181.198.215.232.759.827.1031.1098], align 16
+@usedSlotIdx = external local_unnamed_addr addrspace(3) externally_initialized global i32, align 4
+@execution_param = external local_unnamed_addr addrspace(3) externally_initialized global i32, align 4
+@omptarget_nvptx_globalArgs = external addrspace(3) externally_initialized global %class.omptarget_nvptx_SharedArgs.16.50.67.84.101.118.152.186.203.220.237.764.832.1036.1099, align 8
+
+define amdgpu_kernel void @__omp_offloading_802_d9e513_main_l28([992 x i32] addrspace(1)* %A) local_unnamed_addr #0 {
+entry:
+  %0 = tail call i64 @__ockl_get_local_size() #3
+  %1 = trunc i64 %0 to i32
+  br i1 undef, label %.worker, label %.mastercheck
+
+.worker:                                          ; preds = %entry
+  ret void
+
+.mastercheck:                                     ; preds = %entry
+  %2 = load i32, i32 addrspace(3)* @execution_param, align 4, !tbaa !1
+  %and.i.i.i.i.i.i = and i32 %2, 1
+  %cmp.i.i.i.i.i.i = icmp eq i32 %and.i.i.i.i.i.i, 0
+  %storemerge.i.i.i.i.i = select i1 %cmp.i.i.i.i.i.i, i32 0, i32 %1
+  %conv.i.i.i = trunc i32 %storemerge.i.i.i.i.i to i16
+  store i16 %conv.i.i.i, i16* undef, align 2, !tbaa !5
+  %DataEnd.i.i.i = getelementptr inbounds %class.omptarget_nvptx_ThreadPrivateContext.10.44.61.78.95.112.146.180.197.214.231.758.826.1030.1097, %class.omptarget_nvptx_ThreadPrivateContext.10.44.61.78.95.112.146.180.197.214.231.758.826.1030.1097* null, i64 0, i32 0, i32 4, i64 0, i32 3
+  store i8* undef, i8** %DataEnd.i.i.i, align 8, !tbaa !13
+  store i8** getelementptr (%class.omptarget_nvptx_SharedArgs.16.50.67.84.101.118.152.186.203.220.237.764.832.1036.1099, %class.omptarget_nvptx_SharedArgs.16.50.67.84.101.118.152.186.203.220.237.764.832.1036.1099* addrspacecast (%class.omptarget_nvptx_SharedArgs.16.50.67.84.101.118.152.186.203.220.237.764.832.1036.1099 addrspace(3)* @omptarget_nvptx_globalArgs to %class.omptarget_nvptx_SharedArgs.16.50.67.84.101.118.152.186.203.220.237.764.832.1036.1099*), i64 0, i32 0, i64 0), i8** addrspace(3)* getelementptr inbounds (%class.omptarget_nvptx_SharedArgs.16.50.67.84.101.118.152.186.203.220.237.764.832.1036.1099, %class.omptarget_nvptx_SharedArgs.16.50.67.84.101.118.152.186.203.220.237.764.832.1036.1099 addrspace(3)* @omptarget_nvptx_globalArgs, i32 0, i32 1), align 8, !tbaa !15
+  %3 = tail call i32 @llvm.amdgcn.workgroup.id.x() #4
+  %idxprom.i1 = sext i32 %3 to i64
+  %arrayidx.i22 = getelementptr inbounds [992 x i32], [992 x i32] addrspace(1)* %A, i64 0, i64 %idxprom.i1
+  %4 = load i32, i32 addrspace(1)* %arrayidx.i22, align 4, !tbaa !17
+  %add.i = add nsw i32 %4, %3
+  store i32 %add.i, i32 addrspace(1)* %arrayidx.i22, align 4, !tbaa !17
+  %5 = load i32, i32 addrspace(3)* @usedSlotIdx, align 4, !tbaa !1
+  %idxprom.i = sext i32 %5 to i64
+  %arrayidx.i6.i.i = getelementptr inbounds [64 x %class.omptarget_nvptx_Queue.11.45.62.79.96.113.147.181.198.215.232.759.827.1031.1098], [64 x %class.omptarget_nvptx_Queue.11.45.62.79.96.113.147.181.198.215.232.759.827.1031.1098] addrspace(1)* @omptarget_nvptx_device_State, i64 0, i64 %idxprom.i, i32 3, i64 undef
+  %6 = addrspacecast i32 addrspace(1)* %arrayidx.i6.i.i to i32*
+  %7 = atomicrmw volatile add i32* %6, i32 0 seq_cst
+  unreachable
+}
+
+declare i64 @__ockl_get_local_size() local_unnamed_addr #1
+
+; Function Attrs: nounwind readnone speculatable
+declare i32 @llvm.amdgcn.workgroup.id.x() #2
+
+attributes #0 = { "use-soft-float"="false" }
+attributes #1 = { "target-cpu"="gfx900" }
+attributes #2 = { nounwind readnone speculatable }
+attributes #3 = { alwaysinline nounwind readnone }
+attributes #4 = { nounwind }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 8.0.0 "}
+!1 = !{!2, !2, i64 0}
+!2 = !{!"int", !3, i64 0}
+!3 = !{!"omnipotent char", !4, i64 0}
+!4 = !{!"Simple C++ TBAA"}
+!5 = !{!6, !11, i64 42}
+!6 = !{!"_ZTS25omptarget_nvptx_TaskDescr", !7, i64 0, !10, i64 40, !12, i64 64}
+!7 = !{!"_ZTSN25omptarget_nvptx_TaskDescr20SavedLoopDescr_itemsE", !8, i64 0, !8, i64 8, !8, i64 16, !8, i64 24, !9, i64 32}
+!8 = !{!"long", !3, i64 0}
+!9 = !{!"_ZTS11kmp_sched_t", !3, i64 0}
+!10 = !{!"_ZTSN25omptarget_nvptx_TaskDescr15TaskDescr_itemsE", !3, i64 0, !3, i64 1, !11, i64 2, !11, i64 4, !11, i64 6, !11, i64 8, !8, i64 16}
+!11 = !{!"short", !3, i64 0}
+!12 = !{!"any pointer", !3, i64 0}
+!13 = !{!14, !12, i64 24}
+!14 = !{!"_ZTS38__kmpc_data_sharing_worker_slot_static", !12, i64 0, !12, i64 8, !12, i64 16, !12, i64 24, !3, i64 32}
+!15 = !{!16, !12, i64 160}
+!16 = !{!"_ZTS26omptarget_nvptx_SharedArgs", !3, i64 0, !12, i64 160, !2, i64 168}
+!17 = !{!18, !18, i64 0}
+!18 = !{!"int", !19, i64 0}
+!19 = !{!"omnipotent char", !20, i64 0}
+!20 = !{!"Simple C/C++ TBAA"}