[AArch64] Make instruction fusion more aggressive.

[fhahn]

Summary

This patch makes instruction fusion more aggressive by

• adding artificial edges between the successors of FirstSU and SecondSU, similar to BaseMemOpClusterMutation::clusterNeighboringMemOps.
• updating PostGenericScheduler::tryCandidate to keep clusters together, similar to GenericScheduler::tryCandidate.

This change increases the number of AES instruction pairs generated on
Cortex-A57 and Cortex-A72. This doesn't change code at all in
most benchmarks or general code, but we've seen improvement on kernels
using AESE/AESMC and AESD/AESIMC.

[javed.absar]

lib/CodeGen/MachineScheduler.cpp

3236

This seems to change core PostRA-Scheduler logic and that may impact other targets. On the other hand, I see that GenericScheduler tries ClusteredNodes candidates and this was missing from here (perhaps for no good reason).

[evandro]

lib/Target/AArch64/AArch64MacroFusion.cpp

243

You can write this line as:
DEBUG(dbgs() << " Copy Succ "; SI->print(dbgs(), DAG); dbgs() << '\n';);

lib/Target/AArch64/AArch64TargetMachine.cpp

283

Sorting these methods in alphabetical order would look better.

test/CodeGen/AArch64/misched-fusion-aes.ll

1

Is CHECKA5A72 a typo?

[fhahn]

Addressed feedback and rebased

[fhahn]

lib/CodeGen/MachineScheduler.cpp

3236

Yes that change may impact other targets, but I think it makes sense to try keep clustered instruction together during PostRA scheduling as well, as GenericScheduler does.

[evandro]

Can you please modify misched-fusion-aes.ll with this patch?

misched-fusion-aes.patch2 KBDownload

[fhahn]

Thanks for the feedback, I've updated with @evandro 's changes. Unfortunately I do not have access to a machine with an exynos-m1 CPU, so I can't benchmark the change on it, but it increases the number of AESE/AESMC pairs on that CPU in the test cases, so it should be positive.

[evandro]

Thank you.

lib/CodeGen/MachineScheduler.cpp

if (!Cand.isValid()) {
     return;
   }
 
   // Prioritize instructions that read unbuffered resources by stall cycles.
   if (tryLess(Top.getLatencyStallCycles(TryCand.SU),
               Top.getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall))
     return;
 
+  // Keep clustered nodes together.
+  if (tryGreater(TryCand.SU == DAG->getNextClusterSucc(),
+                 Cand.SU == DAG->getNextClusterSucc(),
+                 TryCand, Cand, Cluster))
+    return;
+
   // Avoid critical resource consumption and balance the schedule.
   if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources,
               TryCand, Cand, ResourceReduce))
     return;
   if (tryGreater(TryCand.ResDelta.DemandedResources,
                  Cand.ResDelta.DemandedResources,
                  TryCand, Cand, ResourceDemand))
     return;

lib/Target/AArch64/AArch64MacroFusion.cpp

for (SDep &IDep : Preds ? DepSU.Succs : DepSU.Preds)
         IDep.setLatency(0);
 
     DEBUG(dbgs() << DAG->MF.getName() << "(): Macro fuse ";
           FirstSU.print(dbgs(), DAG); dbgs() << " - ";
           SecondSU.print(dbgs(), DAG); dbgs() << " /  ";
           dbgs() << DAG->TII->getName(FirstMI->getOpcode()) << " - " <<
                     DAG->TII->getName(SecondMI->getOpcode()) << '\n'; );
 
+    if (&SecondSU != &DAG->ExitSU)
+      // Make instructions dependent on FirstSU also dependent on SecondSU to
+      // prevent them from being scheduled between FirstSU and and SecondSU.
+      for (SUnit::const_succ_iterator
+             SI = FirstSU.Succs.begin(), SE = FirstSU.Succs.end();
+           SI != SE; ++SI) {
+        if (SI->getSUnit() == &SecondSU)
+          continue;
+        DEBUG(dbgs() << "  Copy Succ SU(" << SI->getSUnit()->NodeNum << ")\n");
+        DAG->addEdge(SI->getSUnit(), SDep(&SecondSU, SDep::Artificial));
+      }
+
     ++NumFused;
     return true;
   }
 
   return false;
 }
 
 /// \brief Post-process the DAG to create cluster edges between instrs that may

lib/Target/AArch64/AArch64TargetMachine.cpp

createMachineScheduler(MachineSchedContext *C) const override {
     DAG->addMutation(createStoreClusterDAGMutation(DAG->TII, DAG->TRI));
     DAG->addMutation(createAArch64MacroFusionDAGMutation());
     return DAG;
   }
 
   ScheduleDAGInstrs *
   createPostMachineScheduler(MachineSchedContext *C) const override {
     const AArch64Subtarget &ST = C->MF->getSubtarget<AArch64Subtarget>();
-    if (ST.hasFuseLiterals()) {
+    if (ST.hasFuseLiterals() || ST.hasFuseAES()) {
       // Run the Macro Fusion after RA again since literals are expanded from
       // pseudos then (v. addPreSched2()).
       ScheduleDAGMI *DAG = createGenericSchedPostRA(C);
       DAG->addMutation(createAArch64MacroFusionDAGMutation());
       return DAG;
     }
 
     return nullptr;

test/CodeGen/AArch64/misched-fusion-aes.ll

-; RUN: llc %s -o - -mtriple=aarch64-unknown -mcpu=cortex-a57 | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKA57
-; RUN: llc %s -o - -mtriple=aarch64-unknown -mcpu=cortex-a72 | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKA72
+; RUN: llc %s -o - -mtriple=aarch64-unknown -mcpu=cortex-a57 | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKA5A72
+; RUN: llc %s -o - -mtriple=aarch64-unknown -mcpu=cortex-a72 | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKA57A72
 ; RUN: llc %s -o - -mtriple=aarch64-unknown -mcpu=exynos-m1  | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKM1
 
 declare <16 x i8> @llvm.aarch64.crypto.aese(<16 x i8> %d, <16 x i8> %k)
 declare <16 x i8> @llvm.aarch64.crypto.aesmc(<16 x i8> %d)
 declare <16 x i8> @llvm.aarch64.crypto.aesd(<16 x i8> %d, <16 x i8> %k)
 declare <16 x i8> @llvm.aarch64.crypto.aesimc(<16 x i8> %d)
 
 define void @aesea(<16 x i8>* %a0, <16 x i8>* %b0, <16 x i8>* %c0, <16 x i8> %d, <16 x i8> %e) {
define void @aesea(<16 x i8>* %a0, <16 x i8>* %b0, <16 x i8>* %c0, <16 x i8> %d, <16 x i8> %e) {
   store <16 x i8> %h1, <16 x i8>* %c1
   %c2 = getelementptr inbounds <16 x i8>, <16 x i8>* %c0, i64 2
   store <16 x i8> %h2, <16 x i8>* %c2
   %c3 = getelementptr inbounds <16 x i8>, <16 x i8>* %c0, i64 3
   store <16 x i8> %h3, <16 x i8>* %c3
   ret void
 
 ; CHECK-LABEL: aesea:
-; CHECKA57: aese [[VA:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA57: aese [[VB:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA57: aese [[VC:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA57-NEXT: aesmc {{v[0-7].16b}}, [[VC]]
-; CHECKA57: aesmc {{v[0-7].16b}}, [[VA]]
-; CHECKA57: aese [[VD:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA57-NEXT: aesmc {{v[0-7].16b}}, [[VD]]
-; CHECKA57: aesmc {{v[0-7].16b}}, [[VB]]
-; CHECKA57: aese [[VE:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA57-NEXT: aesmc {{v[0-7].16b}}, [[VE]]
-; CHECKA57: aese [[VF:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA57-NEXT: aesmc {{v[0-7].16b}}, [[VF]]
-; CHECKA57: aese [[VG:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA57-NEXT: aesmc {{v[0-7].16b}}, [[VG]]
-; CHECKA57: aese [[VH:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA57-NEXT: aesmc {{v[0-7].16b}}, [[VH]]
-; CHECKA72: aese [[VA:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA72-NEXT: aesmc {{v[0-7].16b}}, [[VA]]
-; CHECKA72: aese [[VB:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA72-NEXT: aesmc {{v[0-7].16b}}, [[VB]]
-; CHECKA72: aese [[VC:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA72-NEXT: aesmc {{v[0-7].16b}}, [[VC]]
-; CHECKA72: aese [[VD:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA72-NEXT: aesmc {{v[0-7].16b}}, [[VD]]
-; CHECKA72: aese [[VE:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA72-NEXT: aesmc {{v[0-7].16b}}, [[VE]]
-; CHECKA72: aese [[VF:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA72-NEXT: aesmc {{v[0-7].16b}}, [[VF]]
-; CHECKA72: aese [[VG:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA72-NEXT: aesmc {{v[0-7].16b}}, [[VG]]
-; CHECKA72: aese [[VH:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA72-NEXT: aesmc {{v[0-7].16b}}, [[VH]]
+; CHECKA57A72: aese [[VA:v[0-7].16b]], {{v[0-7].16b}}
+; CHECKA57A72-NEXT: aesmc {{v[0-7].16b}}, [[VA]]
+; CHECKA57A72: aese [[VB:v[0-7].16b]], {{v[0-7].16b}}
+; CHECKA57A72-NEXT: aesmc {{v[0-7].16b}}, [[VB]]
+; CHECKA57A72: aese [[VC:v[0-7].16b]], {{v[0-7].16b}}
+; CHECKA57A72-NEXT: aesmc {{v[0-7].16b}}, [[VC]]
+; CHECKA57A72: aese [[VD:v[0-7].16b]], {{v[0-7].16b}}
+; CHECKA57A72-NEXT: aesmc {{v[0-7].16b}}, [[VD]]
+; CHECKA57A72: aese [[VE:v[0-7].16b]], {{v[0-7].16b}}
+; CHECKA57A72-NEXT: aesmc {{v[0-7].16b}}, [[VE]]
+; CHECKA57A72: aese [[VF:v[0-7].16b]], {{v[0-7].16b}}
+; CHECKA57A72-NEXT: aesmc {{v[0-7].16b}}, [[VF]]
+; CHECKA57A72: aese [[VG:v[0-7].16b]], {{v[0-7].16b}}
+; CHECKA57A72-NEXT: aesmc {{v[0-7].16b}}, [[VG]]
+; CHECKA57A72: aese [[VH:v[0-7].16b]], {{v[0-7].16b}}
+; CHECKA57A72-NEXT: aesmc {{v[0-7].16b}}, [[VH]]
 ; CHECKM1: aese [[VA:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKM1: aesmc {{v[0-7].16b}}, [[VA]]
+; CHECKM1-NEXT: aesmc {{v[0-7].16b}}, [[VA]]
+; CHECKM1: aese {{v[0-7].16b}}, {{v[0-7].16b}}
 ; CHECKM1: aese [[VB:v[0-7].16b]], {{v[0-7].16b}}
 ; CHECKM1-NEXT: aesmc {{v[0-7].16b}}, [[VB]]
 ; CHECKM1: aese {{v[0-7].16b}}, {{v[0-7].16b}}
 ; CHECKM1: aese [[VC:v[0-7].16b]], {{v[0-7].16b}}
 ; CHECKM1-NEXT: aesmc {{v[0-7].16b}}, [[VC]]
 ; CHECKM1: aese [[VD:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKM1: aesmc {{v[0-7].16b}}, [[VD]]
+; CHECKM1-NEXT: aesmc {{v[0-7].16b}}, [[VD]]
 ; CHECKM1: aese [[VE:v[0-7].16b]], {{v[0-7].16b}}
 ; CHECKM1-NEXT: aesmc {{v[0-7].16b}}, [[VE]]
 ; CHECKM1: aese [[VF:v[0-7].16b]], {{v[0-7].16b}}
 ; CHECKM1-NEXT: aesmc {{v[0-7].16b}}, [[VF]]
 ; CHECKM1: aese [[VG:v[0-7].16b]], {{v[0-7].16b}}
 ; CHECKM1-NEXT: aesmc {{v[0-7].16b}}, [[VG]]
 ; CHECKM1: aese [[VH:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKM1-NEXT: aesmc {{v[0-7].16b}}, [[VH]]
 }
 
 define void @aesda(<16 x i8>* %a0, <16 x i8>* %b0, <16 x i8>* %c0, <16 x i8> %d, <16 x i8> %e) {
   %d0 = load <16 x i8>, <16 x i8>* %a0
   %a1 = getelementptr inbounds <16 x i8>, <16 x i8>* %a0, i64 1
   %d1 = load <16 x i8>, <16 x i8>* %a1
   %a2 = getelementptr inbounds <16 x i8>, <16 x i8>* %a0, i64 2
   %d2 = load <16 x i8>, <16 x i8>* %a2
define void @aesda(<16 x i8>* %a0, <16 x i8>* %b0, <16 x i8>* %c0, <16 x i8> %d, <16 x i8> %e) {
   store <16 x i8> %h1, <16 x i8>* %c1
   %c2 = getelementptr inbounds <16 x i8>, <16 x i8>* %c0, i64 2
   store <16 x i8> %h2, <16 x i8>* %c2
   %c3 = getelementptr inbounds <16 x i8>, <16 x i8>* %c0, i64 3
   store <16 x i8> %h3, <16 x i8>* %c3
   ret void
 
 ; CHECK-LABEL: aesda:
-; CHECKA57: aesd [[VA:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA57: aesd [[VB:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA57: aesd [[VC:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA57-NEXT: aesimc {{v[0-7].16b}}, [[VC]]
-; CHECKA57: aesimc {{v[0-7].16b}}, [[VA]]
-; CHECKA57: aesd [[VD:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA57-NEXT: aesimc {{v[0-7].16b}}, [[VD]]
-; CHECKA57: aesimc {{v[0-7].16b}}, [[VB]]
-; CHECKA57: aesd [[VE:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA57-NEXT: aesimc {{v[0-7].16b}}, [[VE]]
-; CHECKA57: aesd [[VF:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA57-NEXT: aesimc {{v[0-7].16b}}, [[VF]]
-; CHECKA57: aesd [[VG:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA57-NEXT: aesimc {{v[0-7].16b}}, [[VG]]
-; CHECKA57: aesd [[VH:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA57-NEXT: aesimc {{v[0-7].16b}}, [[VH]]
-; CHECKA72: aesd [[VA:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA72-NEXT: aesimc {{v[0-7].16b}}, [[VA]]
-; CHECKA72: aesd [[VB:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA72-NEXT: aesimc {{v[0-7].16b}}, [[VB]]
-; CHECKA72: aesd [[VC:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA72-NEXT: aesimc {{v[0-7].16b}}, [[VC]]
-; CHECKA72: aesd [[VD:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA72-NEXT: aesimc {{v[0-7].16b}}, [[VD]]
-; CHECKA72: aesd [[VE:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA72-NEXT: aesimc {{v[0-7].16b}}, [[VE]]
-; CHECKA72: aesd [[VF:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA72-NEXT: aesimc {{v[0-7].16b}}, [[VF]]
-; CHECKA72: aesd [[VG:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA72-NEXT: aesimc {{v[0-7].16b}}, [[VG]]
-; CHECKA72: aesd [[VH:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKA72-NEXT: aesimc {{v[0-7].16b}}, [[VH]]
+; CHECKA57A72: aesd [[VA:v[0-7].16b]], {{v[0-7].16b}}
+; CHECKA57A72-NEXT: aesimc {{v[0-7].16b}}, [[VA]]
+; CHECKA57A72: aesd [[VB:v[0-7].16b]], {{v[0-7].16b}}
+; CHECKA57A72-NEXT: aesimc {{v[0-7].16b}}, [[VB]]
+; CHECKA57A72: aesd [[VC:v[0-7].16b]], {{v[0-7].16b}}
+; CHECKA57A72-NEXT: aesimc {{v[0-7].16b}}, [[VC]]
+; CHECKA57A72: aesd [[VD:v[0-7].16b]], {{v[0-7].16b}}
+; CHECKA57A72-NEXT: aesimc {{v[0-7].16b}}, [[VD]]
+; CHECKA57A72: aesd [[VE:v[0-7].16b]], {{v[0-7].16b}}
+; CHECKA57A72-NEXT: aesimc {{v[0-7].16b}}, [[VE]]
+; CHECKA57A72: aesd [[VF:v[0-7].16b]], {{v[0-7].16b}}
+; CHECKA57A72-NEXT: aesimc {{v[0-7].16b}}, [[VF]]
+; CHECKA57A72: aesd [[VG:v[0-7].16b]], {{v[0-7].16b}}
+; CHECKA57A72-NEXT: aesimc {{v[0-7].16b}}, [[VG]]
+; CHECKA57A72: aesd [[VH:v[0-7].16b]], {{v[0-7].16b}}
+; CHECKA57A72-NEXT: aesimc {{v[0-7].16b}}, [[VH]]
 ; CHECKM1: aesd [[VA:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKM1: aesimc {{v[0-7].16b}}, [[VA]]
+; CHECKM1-NEXT: aesimc {{v[0-7].16b}}, [[VA]]
+; CHECKM1: aesd {{v[0-7].16b}}, {{v[0-7].16b}}
 ; CHECKM1: aesd [[VB:v[0-7].16b]], {{v[0-7].16b}}
 ; CHECKM1-NEXT: aesimc {{v[0-7].16b}}, [[VB]]
 ; CHECKM1: aesd {{v[0-7].16b}}, {{v[0-7].16b}}
 ; CHECKM1: aesd [[VC:v[0-7].16b]], {{v[0-7].16b}}
 ; CHECKM1-NEXT: aesimc {{v[0-7].16b}}, [[VC]]
 ; CHECKM1: aesd [[VD:v[0-7].16b]], {{v[0-7].16b}}
 ; CHECKM1: aesimc {{v[0-7].16b}}, [[VD]]
 ; CHECKM1: aesd [[VE:v[0-7].16b]], {{v[0-7].16b}}
 ; CHECKM1-NEXT: aesimc {{v[0-7].16b}}, [[VE]]
 ; CHECKM1: aesd [[VF:v[0-7].16b]], {{v[0-7].16b}}
 ; CHECKM1-NEXT: aesimc {{v[0-7].16b}}, [[VF]]
 ; CHECKM1: aesd [[VG:v[0-7].16b]], {{v[0-7].16b}}
 ; CHECKM1-NEXT: aesimc {{v[0-7].16b}}, [[VG]]
 ; CHECKM1: aesd [[VH:v[0-7].16b]], {{v[0-7].16b}}
-; CHECKM1-NEXT: aesimc {{v[0-7].16b}}, [[VH]]
+}
+
+define void @aes_load_store(<16 x i8> *%p1, <16 x i8> *%p2 , <16 x i8> *%p3) {
+entry:
+  %x1 = alloca <16 x i8>, align 16
+  %x2 = alloca <16 x i8>, align 16
+  %x3 = alloca <16 x i8>, align 16
+  %x4 = alloca <16 x i8>, align 16
+  %x5 = alloca <16 x i8>, align 16
+  %in1 = load <16 x i8>, <16 x i8>* %p1, align 16
+  store <16 x i8> %in1, <16 x i8>* %x1, align 16
+  %aese1 = call <16 x i8> @llvm.aarch64.crypto.aese(<16 x i8> %in1, <16 x i8> %in1) #2
+  store <16 x i8> %aese1, <16 x i8>* %x2, align 16
+  %in2 = load <16 x i8>, <16 x i8>* %p2, align 16
+  %aesmc1= call <16 x i8> @llvm.aarch64.crypto.aesmc(<16 x i8> %aese1) #2
+  store <16 x i8> %aesmc1, <16 x i8>* %x3, align 16
+  %aese2 = call <16 x i8> @llvm.aarch64.crypto.aese(<16 x i8> %in1, <16 x i8> %in2) #2
+  store <16 x i8> %aese2, <16 x i8>* %x4, align 16
+  %aesmc2= call <16 x i8> @llvm.aarch64.crypto.aesmc(<16 x i8> %aese2) #2
+  store <16 x i8> %aesmc2, <16 x i8>* %x5, align 16
+  ret void
+
+; CHECK-LABEL: aes_load_store:
+; CHECK: aese [[VA:v[0-7].16b]], {{v[0-7].16b}}
+; CHECK-NEXT: aesmc {{v[0-7].16b}}, [[VA]]
+; CHECK: aese [[VB:v[0-7].16b]], {{v[0-7].16b}}
+; CHECK-NEXT: aesmc {{v[0-7].16b}}, [[VB]]
 }