[AArch64] Override useAA and remove unneeded edges in the scheduling graph. (Phabricator)

[ssijaric]

Summary

All,
This patch removes edges in the scheduling graph between stores/loads off the same base register if memory accesses do not overlap. An improvement on eembc/automark on a cortex-a53 device, as well as a small improvement on spec2000/eon. No significant performance changes were observed on cortex-a57, but this may be more relevant on in-order architectures. Please have a look.

Thanks,

Sanjin

(I submitted on behalf of Sanjin to ease review.)

[mcrosier]

lib/Target/AArch64/AArch64InstrInfo.cpp

1312

Spacing of parameters.

1396

Check prior to the switch?

[hfinkel]

Just to share some experience... (I enable AA during CodeGen on many PowerPC cores)

I've found using AA during CodeGen is very useful for in-order cores. It is less useful for ooo cores, but this is somewhat dependent on the size of the reorder buffers (and sometimes the loop dispatch buffers, depending on how the architecture is setup), because its main effect is to reduce pressure on these resources.

But it is sometimes very useful on ooo cores for architecture-specific reasons. For example, on the POWER cores there are expensive load-after-store hazards that are critical to avoid. These can be avoided by forcing dispatch-group termination using special nop instructions, but you don't want to do this if you don't have to. Using AA in CodeGen to reduce the number of unneeded group-terminating nops inserted is very helpful.

There is potentially some compile-time impact to doing this, so make sure you keep that in mind.

[mcrosier]

Add missing test case.

[jmolloy]

Hi Sanjin,

I have a bunch of comments, but this patch looks in good shape already! One other thing, it looks like you're adding quite a few blank lines between functions. There should be one blank line only. A nitpick I know, but nitpicks like this keep the codebase in decent shape.

Cheers,

James

include/llvm/Target/TargetInstrInfo.h

1195

I don't like the truncation of "different" to "diff". In fact, I think "disjoint" would be more accurate: "areMemAccessesTriviallyDisjoint".

What is the behaviour is MIa or MIb are not memory access instructions? you've below had them return false but I think it should assert in this case.

1204

Unused function.

lib/CodeGen/ScheduleDAGInstrs.cpp

521

Either you need to check if these are memory accesses first, or you should rename the function or make it explicit that it will be well behaved on non-memory operands. With its current name, one would expect that a precondition is the arguments are memory instructions.

lib/Target/AArch64/AArch64InstrInfo.cpp

617

As mentioned above, unintuitive.

631

For clarity, I'd prefer if you used the same condition in each ternary instead of chaining off the first condition:

int LowOffset = OffsetA < OffsetB ? ...
int HighOffset = OffsetA < OffsetB ? ...

1396

Probably best to early-exit this before the switch.

lib/Target/AArch64/AArch64Subtarget.h

114 ↗

(On Diff #13041)

This should go in in a separate commit before the rest of the code as it is orthogonal.

test/CodeGen/AArch64/arm64-triv-diff-mem-access.ll

2 ↗

(On Diff #13041)

Do we need -enable-misched here? isn't it enabled by default?

6 ↗

(On Diff #13041)

Tests that check debug output are generally frowned upon, unless there is no better way to write them.

I assume there is no better way to write this?

[ssijaric]

Thanks, Hal. We saw some improvements on an in-order cortex-a53 device, but didn't observe performance improvements on an out-of-order cortex-a57 device. We also didn't observe significant compile time degradations when compiling spec2006 with -Ofast.

[Jiangning]

Hi Sanjin,

spec.cpu2000.ref.181_mcf -1.86%
spec.cpu2000.ref.183_equake -3.11%
spec.cpu2000.ref.186_crafty 1.53%
spec.cpu2000.ref.254_gap 1.40%

I can confirm that we only see some fluctuations on coretex-A57 as above,
so there isn't degradation observed for spec2000 at least.

Thanks,
-Jiangning

2014-08-30 2:04 GMT+08:00 Sanjin Sijaric <[e-mail]>:

Thanks, Hal. We saw some improvements on an in-order cortex-a53 device,
but didn't observe performance improvements on an out-of-order cortex-a57
device. We also didn't observe significant compile time degradations when
compiling spec2006 with -Ofast.

http://reviews.llvm.org/D5103

[ssijaric]

Thanks, James. The updated patch should address some of the problems. The call to MIsNeedChainEdge from addChainDependency depends on AA being enabled, so I enabled AA together with the rest of the changes. Otherwise, the test case will fail. Enabling AA may go in a separate commit, but it would have to be committed before any other changes.

Thanks for the results, Jiangning. The updated patch enables AA for the in-order cortex-a53 core only.

[hfinkel]

I recommend splitting the useAA change from the rest of it (for better bisecting ;) ).

include/llvm/Target/TargetInstrInfo.h

1200

Can you also pass an optional AliasAnalysis* here too, so the target can use AA in conjunction with whatever target-specific information it has to determine aliasing.

[ssijaric]

Incorporate Hal's suggestions.

[mcrosier]

Sanjin,
After committing the change to enable AA in AArch64Subtarget.h, this patch LGTM.

Chad

[mcrosier]

Committed in r217370, r217371, and r217381.

include/llvm/Target/TargetInstrInfo.h

     return nullptr;
   }
 
+  // areMemAccessesTriviallyDisjoint - Sometimes, it is possible for the target
+  // to tell, even without aliasing information, that two MIs access different
+  // memory addresses. This function returns true if two MIs access different
+  // memory addresses, and false otherwise.
+  virtual bool
+  areMemAccessesTriviallyDisjoint(MachineInstr *MIa, MachineInstr *MIb,
+                                  AliasAnalysis *AA = nullptr) const {
+    assert(MIa && (MIa->mayLoad() || MIa->mayStore()) &&
+           "MIa must load from or modify a memory location");
+    assert(MIb && (MIb->mayLoad() || MIb->mayStore()) &&
+           "MIb must load from or modify a memory location");
+    return false;
+  }
+
 private:
   int CallFrameSetupOpcode, CallFrameDestroyOpcode;
 };

lib/CodeGen/ScheduleDAGInstrs.cpp

 static bool MIsNeedChainEdge(AliasAnalysis *AA, const MachineFrameInfo *MFI,
                              MachineInstr *MIa,
                              MachineInstr *MIb) {
+  const MachineFunction *MF = MIa->getParent()->getParent();
+  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
+
   // Cover a trivial case - no edge is need to itself.
   if (MIa == MIb)
     return false;
+ 
+  // Let the target decide if memory accesses cannot possibly overlap.
+  if ((MIa->mayLoad() || MIa->mayStore()) &&
+      (MIb->mayLoad() || MIb->mayStore()))
+    if (TII->areMemAccessesTriviallyDisjoint(MIa, MIb, AA))
+      return false;
 
   // FIXME: Need to handle multiple memory operands to support all targets.
   if (!MIa->hasOneMemOperand() || !MIb->hasOneMemOperand())

lib/Target/AArch64/AArch64InstrInfo.h

   bool isCoalescableExtInstr(const MachineInstr &MI, unsigned &SrcReg,
                              unsigned &DstReg, unsigned &SubIdx) const override;
 
+  bool
+  areMemAccessesTriviallyDisjoint(MachineInstr *MIa, MachineInstr *MIb,
+                                  AliasAnalysis *AA = nullptr) const override;
+
   unsigned isLoadFromStackSlot(const MachineInstr *MI,
                                int &FrameIndex) const override;
   unsigned isStoreToStackSlot(const MachineInstr *MI,

                             unsigned &Offset,
                             const TargetRegisterInfo *TRI) const override;
 
+  bool getLdStBaseRegImmOfsWidth(MachineInstr *LdSt, unsigned &BaseReg,
+                                 int &Offset, int &Width,
+                                 const TargetRegisterInfo *TRI) const;
+
   bool enableClusterLoads() const override { return true; }
 
   bool shouldClusterLoads(MachineInstr *FirstLdSt, MachineInstr *SecondLdSt,

lib/Target/AArch64/AArch64InstrInfo.cpp

   }
 }
 
+bool
+AArch64InstrInfo::areMemAccessesTriviallyDisjoint(MachineInstr *MIa,
+                                                  MachineInstr *MIb,
+                                                  AliasAnalysis *AA) const {
+  const TargetRegisterInfo *TRI = &getRegisterInfo();
+  unsigned BaseRegA = 0, BaseRegB = 0;
+  int OffsetA = 0, OffsetB = 0;
+  int WidthA = 0, WidthB = 0;
+
+  assert(MIa && (MIa->mayLoad() || MIa->mayStore()) &&
+         "MIa must be a store or a load");
+  assert(MIb && (MIb->mayLoad() || MIb->mayStore()) &&
+         "MIb must be a store or a load");
+
+  if (MIa->hasUnmodeledSideEffects() || MIb->hasUnmodeledSideEffects() ||
+      MIa->hasOrderedMemoryRef() || MIb->hasOrderedMemoryRef())
+    return false;
+
+  // Retrieve the base register, offset from the base register and width. Width
+  // is the size of memory that is being loaded/stored (e.g. 1, 2, 4, 8).  If
+  // base registers are identical, and the offset of a lower memory access +
+  // the width doesn't overlap the offset of a higher memory access,
+  // then the memory accesses are different.
+  if (getLdStBaseRegImmOfsWidth(MIa, BaseRegA, OffsetA, WidthA, TRI) &&
+      getLdStBaseRegImmOfsWidth(MIb, BaseRegB, OffsetB, WidthB, TRI)) {
+    if (BaseRegA == BaseRegB) {
+      int LowOffset = OffsetA < OffsetB ? OffsetA : OffsetB;
+      int HighOffset = OffsetA < OffsetB ? OffsetB : OffsetA;
+      int LowWidth = (LowOffset == OffsetA) ? WidthA : WidthB;
+      if (LowOffset + LowWidth <= HighOffset)
+        return true;
+    }
+  }
+  return false;
+}
+
 /// analyzeCompare - For a comparison instruction, return the source registers
 /// in SrcReg and SrcReg2, and the value it compares against in CmpValue.
 /// Return true if the comparison instruction can be analyzed.

   };
 }
 
+bool AArch64InstrInfo::getLdStBaseRegImmOfsWidth(
+    MachineInstr *LdSt, unsigned &BaseReg, int &Offset, int &Width,
+    const TargetRegisterInfo *TRI) const {
+  // Handle only loads/stores with base register followed by immediate offset.
+  if (LdSt->getNumOperands() != 3)
+    return false;
+  if (!LdSt->getOperand(1).isReg() || !LdSt->getOperand(2).isImm())
+    return false;
+
+  // Offset is calculated as the immediate operand multiplied by the scaling factor.
+  // Unscaled instructions have scaling factor set to 1.
+  int Scale = 0;
+  switch (LdSt->getOpcode()) {
+  default:
+    return false;
+  case AArch64::LDURQi:
+  case AArch64::STURQi:
+    Width = 16;
+    Scale = 1;
+    break;
+  case AArch64::LDURXi:
+  case AArch64::LDURDi:
+  case AArch64::STURXi:
+  case AArch64::STURDi:
+    Width = 8;
+    Scale = 1;
+    break;
+  case AArch64::LDURWi:
+  case AArch64::LDURSi:
+  case AArch64::LDURSWi:
+  case AArch64::STURWi:
+  case AArch64::STURSi:
+    Width = 4;
+    Scale = 1;
+    break;
+  case AArch64::LDURHi:
+  case AArch64::LDURHHi:
+  case AArch64::LDURSHXi:
+  case AArch64::LDURSHWi:
+  case AArch64::STURHi:
+  case AArch64::STURHHi:
+    Width = 2;
+    Scale = 1;
+    break;
+  case AArch64::LDURBi:
+  case AArch64::LDURBBi:
+  case AArch64::LDURSBXi:
+  case AArch64::LDURSBWi:
+  case AArch64::STURBi:
+  case AArch64::STURBBi:
+    Width = 1;
+    Scale = 1;
+    break;
+  case AArch64::LDRXui:
+  case AArch64::STRXui:
+    Scale = Width = 8;
+    break;
+  case AArch64::LDRWui:
+  case AArch64::STRWui:
+    Scale = Width = 4;
+    break;
+  case AArch64::LDRBui:
+  case AArch64::STRBui:
+    Scale = Width = 1;
+    break;
+  case AArch64::LDRHui:
+  case AArch64::STRHui:
+    Scale = Width = 2;
+    break;
+  case AArch64::LDRSui:
+  case AArch64::STRSui:
+    Scale = Width = 4;
+    break;
+  case AArch64::LDRDui:
+  case AArch64::STRDui:
+    Scale = Width = 8;
+    break;
+  case AArch64::LDRQui:
+  case AArch64::STRQui:
+    Scale = Width = 16;
+    break;
+  case AArch64::LDRBBui:
+  case AArch64::STRBBui:
+    Scale = Width = 1;
+    break;
+  case AArch64::LDRHHui:
+  case AArch64::STRHHui:
+    Scale = Width = 2;
+    break;
+  };
+
+  BaseReg = LdSt->getOperand(1).getReg();
+  Offset = LdSt->getOperand(2).getImm() * Scale;
+  return true;
+}
+
 /// Detect opportunities for ldp/stp formation.
 ///
 /// Only called for LdSt for which getLdStBaseRegImmOfs returns true.

test/CodeGen/AArch64/arm64-triv-disjoint-mem-access.ll

+; RUN: llc < %s -mtriple=arm64-linux-gnu -mcpu=cortex-a53 -enable-aa-sched-mi | FileCheck %s
+; Check that the scheduler moves the load from a[1] past the store into a[2].
+@a = common global i32* null, align 8
+@m = common global i32 0, align 4
+
+; Function Attrs: nounwind
+define i32 @func(i32 %i, i32 %j, i32 %k) #0 {
+entry:
+; CHECK: ldr {{w[0-9]+}}, [x[[REG:[0-9]+]], #4]
+; CHECK: str {{w[0-9]+}}, [x[[REG]], #8]
+  %0 = load i32** @a, align 8, !tbaa !1
+  %arrayidx = getelementptr inbounds i32* %0, i64 2
+  store i32 %i, i32* %arrayidx, align 4, !tbaa !5
+  %arrayidx1 = getelementptr inbounds i32* %0, i64 1
+  %1 = load i32* %arrayidx1, align 4, !tbaa !5
+  %add = add nsw i32 %k, %i
+  store i32 %add, i32* @m, align 4, !tbaa !5
+  ret i32 %1
+}
+
+attributes #0 = { nounwind "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="true" "no-nans-fp-math"="true" "stack-protector-buffer-size"="8" "unsafe-fp-math"="true" "use-soft-float"="false" }
+
+!llvm.ident = !{!0}
+
+!0 = metadata !{metadata !"clang version 3.6.0 "}
+!1 = metadata !{metadata !2, metadata !2, i64 0}
+!2 = metadata !{metadata !"any pointer", metadata !3, i64 0}
+!3 = metadata !{metadata !"omnipotent char", metadata !4, i64 0}
+!4 = metadata !{metadata !"Simple C/C++ TBAA"}
+!5 = metadata !{metadata !6, metadata !6, i64 0}
+!6 = metadata !{metadata !"int", metadata !3, i64 0}