[llvm][CodeGen] Add a default implementation to check whether two memory accesses are trivially disjoint

[csstormq]

Summary

Add a target independent method using machine memory operands to check whether two instructions can alias. And as a default implementation to TargetInstrInfo::areMemAccessesTriviallyDisjoint function. It's useful for targets whose memory accesses are known at compile time.

[efriedma]

Most of the existing target-independent code related to memoperand aliasing is in MachineInstr::mayAlias (specifically the MemOperandsHaveAlias helper). Is there some reason you can't just extend that?

[csstormq]

In D127095#3560947, @efriedma wrote:

Most of the existing target-independent code related to memoperand aliasing is in MachineInstr::mayAlias (specifically the MemOperandsHaveAlias helper). Is there some reason you can't just extend that?

In our case, we want to do the following two things.

First, in the overloaded SelectionDAGISel::PostprocessISelDAG, we want to break unnecessary chain dependencies between load and store instructions, represented as MachineSDNode, for having a positive affect on pre-RA scheduler.

I am not sure whether it's suit to construct temporary variables of MachineInstr here just for enabling to invoke MachineInstr::mayAlias. So I provide an individual function, called areMemAccessesTriviallyDisjoint, to finish the same work. This function does not care whether both instructions are MachineInstr or not. That's why the parameters of it are machine memory operands.

Second, because the result of pre-RA scheduler whichever we choose is not exactly what we expected, we write a machine pass to adjust slightly the sequence between load and store instructions, represented as MachineInstr. Here, it is natural to invoke MachineInstr::mayAlias. To finish our work, I add a default implementation for TargetInstrInfo::areMemAccessesTriviallyDisjoint as the code shown. So the users of invoking MachineInstr::mayAlias will benefit from it by default.

That's all.

[efriedma]

You might want to look at TargetSubtargetInfo::useAA() and TargetSubtargetInfo::enableMachineScheduler(); might be helpful for your target, depending on what you're doing. (Actually, maybe we should consider just turning these on by default for all targets, given the number of targets overriding them.)

If you want to refactor out the relevant bits of MachineInstr::mayAlias into a helper, then enhance it, that would be fine, I guess. It's just weird to have two separate codepaths for checking MachineMemOperands.

[csstormq]

In D127095#3564745, @efriedma wrote:

You might want to look at TargetSubtargetInfo::useAA() and TargetSubtargetInfo::enableMachineScheduler(); might be helpful for your target, depending on what you're doing. (Actually, maybe we should consider just turning these on by default for all targets, given the number of targets overriding them.)

I have tried TargetSubtargetInfo::useAA for my target, but it is not helpful for my case.
I will try TargetSubtargetInfo::enableMachineScheduler() later. Thank you for your advice!

In D127095#3564745, @efriedma wrote:

If you want to refactor out the relevant bits of MachineInstr::mayAlias into a helper, then enhance it, that would be fine, I guess. It's just weird to have two separate codepaths for checking MachineMemOperands.

I agree with your idea. I have submitted a new patch. Please review it again. At last, whether the title and summary need re edit to accord with the latest patch.

[efriedma]

llvm/lib/CodeGen/MachineInstr.cpp

1242

Address spaces are, in general, allowed to overlap. I think there might be a target hook to check if two address spaces are disjoint.

1274

Do we care if all the bits are actually address-significant? For example, on AArch64, there's a setting to tell the processor to ignore the top 16 bits of a pointer.

I guess there are other places we do aliasing checks based on the pointer bits, so maybe this isn't a practical issue.

1345

Do we reach this call isNoAlias() for two different intoptr constants? Does it not handle the case you're trying to deal with?

[csstormq]

llvm/lib/CodeGen/MachineInstr.cpp

1242

It makes sense.

1274

I didn't take this into account. Maybe it's better to provide a target hook here.

At present, I don't find that some places, especially the users of MachineInstr::mayAlias, have done similar thing as me. So it will be helpful for some targets like ours, I guess.

1345

I migrate our backend to the latest main branch. And I tried again. I truly reach this call isNoAlias() for two different intoptr constants using gdb step by step, but it still returns false wrongly.

[csstormq]

Addressing code review comments.

[efriedma]

llvm/lib/CodeGen/MachineInstr.cpp

1345

Maybe worth looking into modifying BasicAAResult::aliasCheck to make this work? That would also benefit IR-level optimizations.

2482

Instead of repeating the loop from MachineInstr::mayAlias, can we make MemOperandsHaveAlias call areMemOperandsTriviallyDisjoint?

[csstormq]

llvm/lib/CodeGen/MachineInstr.cpp

1345

I'm afraid not. In my view, when we reach BasicAAResult::aliasCheck, we can't determine the starting address for memory access because the offset from the base address has lost.

2482

Yes, I will do that as your advice in the next patch.

[csstormq]

Eliminate the duplicate loop over memory operands.

[efriedma]

llvm/include/llvm/CodeGen/MachineInstr.h

1842 ↗

(On Diff #437052)

Please don't add "virtual" methods to MachineInstr; it doesn't have any derived classes.

If you need some target-specific info, look at TargetLoweringInfo.

1856 ↗

(On Diff #437052)

Does areMemAccessesTriviallyDisjoint really need to be in the header?

"Align" is just an integer; don't pass it by const reference.

llvm/lib/CodeGen/MachineInstr.cpp

2418

Probably want to check that the operand of the IntToPtr isn't wider than the pointer type.

Also, getZExtValue() will assert on targets that support pointer widths greater than 64.

2433

Don't think "auto" makes sense here; see https://llvm.org/docs/CodingStandards.html#use-auto-type-deduction-to-make-code-more-readable .

2443

I think this is missing a check for whether the address-spaces are different?

[csstormq]

llvm/include/llvm/CodeGen/MachineInstr.h

1842 ↗

(On Diff #437052)

I moved these virtual functions into TargetMachine. Is this OK?

1856 ↗

(On Diff #437052)

As the LLVM document says, the semantics of non-zero address spaces are target-specific. Thus the intent of areMemAccessesTriviallyDisjoint as virtual function is enable to cope with the odd behavior of some targets, although this funciton provides a default implementation for most cases.

llvm/lib/CodeGen/MachineInstr.cpp

2418

Excuse me, is there any problem if I don't check that?

I address the problem of getZExtValue soon.

[csstormq]

1. move virtual functions into TargetMachine
2. avoid getZExtValue() assert issue
3. don’t “almost always” use auto
4. pass "Align" by unsigned integer
5. invoke mayAddressSpacesOverlap iff the address-spaces are different
6. check whether two memory accesses are disjoint iff the address-spaces are same

[csstormq]

Thanks, @Eli.

[csstormq]

Ping

llvm/include/llvm/Target/TargetMachine.h

public:
 
   static std::pair<int, int> parseBinutilsVersion(StringRef Version);
 
   /// getAddressSpaceForPseudoSourceKind - Given the kind of memory
   /// (e.g. stack) the target returns the corresponding address space.
   virtual unsigned getAddressSpaceForPseudoSourceKind(unsigned Kind) const {
     return 0;
   }
+
+  /// Return true if two memory address spaces may overlap and false otherwise.
+  virtual bool mayAddressSpacesOverlap(unsigned AddrSpaceA,
+                                       unsigned AddrSpaceB) const {
+    // Conservatively assume that any two memory address spaces may overlap.
+    return true;
+  }
+
+  /// Return true if two memory accesses are disjoint for your target and false
+  /// otherwise.
+  ///
+  /// Offset, width and alignment are in bytes.
+  virtual bool areMemAccessesTriviallyDisjoint(
+      uint64_t BaseAddrA, uint64_t OffsetA, uint64_t WidthA, uint64_t AlignA,
+      unsigned AddrSpaceA, uint64_t BaseAddrB, uint64_t OffsetB,
+      uint64_t WidthB, uint64_t AlignB, unsigned AddrSpaceB) const;
 };
 
 /// This class describes a target machine that is implemented with the LLVM
 /// target-independent code generator.
 ///
 class LLVMTargetMachine : public TargetMachine {
 protected: // Can only create subclasses.
   LLVMTargetMachine(const Target &T, StringRef DataLayoutString,

llvm/lib/CodeGen/MachineInstr.cpp

bool MachineInstr::isSafeToMove(AAResults *AA, bool &SawStore) const {
   if (mayLoad() && !isDereferenceableInvariantLoad(AA))
     // Otherwise, this is a real load.  If there is a store between the load and
     // end of block, we can't move it.
     return !SawStore;
 
   return true;
 }
 
-static bool MemOperandsHaveAlias(const MachineFrameInfo &MFI, AAResults *AA,
+// If the value of base address contained in this memory operand is constant,
+// update it to `BaseAddr` and return true. Otherwise, return false.
+static bool getConstantBaseAddress(const MachineMemOperand *MMO,
+                                   uint64_t &BaseAddr) {
+  const Value *Val = MMO->getValue();
+
+  if (!Val) {
+    return false;
+  }
+
+  if (auto *CE = dyn_cast<ConstantExpr>(Val)) {
+    if (CE->getOpcode() == Instruction::IntToPtr &&
+        isa<ConstantInt>(CE->getOperand(0))) {
+      auto Op0 = dyn_cast<Constant>(CE->getOperand(0));
+      const APInt &Int = Op0->getUniqueInteger();
+      if (Int.getActiveBits() <= 64) {
+        BaseAddr = Int.getZExtValue();
+        return true;
+      }
+    }
+  }
+
+  return false;
+}
+
+/// Return true if two memory operands access different memory addresses and
+/// false otherwise.
+static bool areMemOperandsTriviallyDisjoint(const TargetMachine &TM,
+                                            const MachineMemOperand *MMOa,
+                                            const MachineMemOperand *MMOb) {
+  const unsigned AddrSpaceA = MMOa->getAddrSpace();
+  const unsigned AddrSpaceB = MMOb->getAddrSpace();
+  if (AddrSpaceA != AddrSpaceB &&
+      !TM.mayAddressSpacesOverlap(AddrSpaceA, AddrSpaceB)) {
+    return true;
+  }
+
+  // Skip if the base address is not constant.
+  uint64_t BaseAddrA = 0;
+  uint64_t BaseAddrB = 0;
+  if (!getConstantBaseAddress(MMOa, BaseAddrA) ||
+      !getConstantBaseAddress(MMOb, BaseAddrB)) {
+    return false;
+  }
+
+  // Skip if the offset from the base address is negative.
+  const int64_t OffsetA = MMOa->getOffset();
+  const int64_t OffsetB = MMOb->getOffset();
+  if (OffsetA < 0 || OffsetB < 0) {
+    return false;
+  }
+
+  // Skip if the size of the memory reference is unknown.
+  const uint64_t WidthA = MMOa->getSize();
+  const uint64_t WidthB = MMOb->getSize();
+  if (WidthA == MemoryLocation::UnknownSize ||
+      WidthB == MemoryLocation::UnknownSize) {
+    return false;
+  }
+
+  return TM.areMemAccessesTriviallyDisjoint(
+      BaseAddrA, OffsetA, WidthA, MMOa->getAlign().value(), AddrSpaceA,
+      BaseAddrB, OffsetB, WidthB, MMOb->getAlign().value(), AddrSpaceB);
+}
+
+static bool MemOperandsHaveAlias(const TargetMachine &TM,
+                                 const MachineFrameInfo &MFI, AAResults *AA,
                                  bool UseTBAA, const MachineMemOperand *MMOa,
                                  const MachineMemOperand *MMOb) {
   // The following interface to AA is fashioned after DAGCombiner::isAlias and
   // operates with MachineMemOperand offset with some important assumptions:
   //   - LLVM fundamentally assumes flat address spaces.
   //   - MachineOperand offset can *only* result from legalization and cannot
   //     affect queries other than the trivial case of overlap checking.
   //   - These offsets never wrap and never step outside of allocated objects.
   //   - There should never be any negative offsets here.
   //
   // FIXME: Modify API to hide this math from "user"
   // Even before we go to AA we can reason locally about some memory objects. It
   // can save compile time, and possibly catch some corner cases not currently
   // covered.
 
+  if (areMemOperandsTriviallyDisjoint(TM, MMOa, MMOb)) {
+    return false;
+  }
+
   int64_t OffsetA = MMOa->getOffset();
   int64_t OffsetB = MMOb->getOffset();
   int64_t MinOffset = std::min(OffsetA, OffsetB);
 
   uint64_t WidthA = MMOa->getSize();
   uint64_t WidthB = MMOb->getSize();
   bool KnownWidthA = WidthA != MemoryLocation::UnknownSize;
   bool KnownWidthB = WidthB != MemoryLocation::UnknownSize;
static bool MemOperandsHaveAlias(const TargetMachine &TM,
   assert((OffsetA >= 0) && "Negative MachineMemOperand offset");
   assert((OffsetB >= 0) && "Negative MachineMemOperand offset");
 
   int64_t OverlapA =
       KnownWidthA ? WidthA + OffsetA - MinOffset : MemoryLocation::UnknownSize;
   int64_t OverlapB =
       KnownWidthB ? WidthB + OffsetB - MinOffset : MemoryLocation::UnknownSize;
 
   return !AA->isNoAlias(
       MemoryLocation(ValA, OverlapA, UseTBAA ? MMOa->getAAInfo() : AAMDNodes()),
       MemoryLocation(ValB, OverlapB,
                      UseTBAA ? MMOb->getAAInfo() : AAMDNodes()));
 }
 
 bool MachineInstr::mayAlias(AAResults *AA, const MachineInstr &Other,
                             bool UseTBAA) const {
   const MachineFunction *MF = getMF();
   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
   const MachineFrameInfo &MFI = MF->getFrameInfo();
+  const TargetMachine &TM = MF->getTarget();
 
   // Exclude call instruction which may alter the memory but can not be handled
   // by this function.
   if (isCall() || Other.isCall())
     return true;
 
   // If neither instruction stores to memory, they can't alias in any
   // meaningful way, even if they read from the same address.
bool MachineInstr::mayAlias(AAResults *AA, const MachineInstr &Other,
   auto NumChecks = getNumMemOperands() * Other.getNumMemOperands();
   if (NumChecks > TII->getMemOperandAACheckLimit())
     return true;
 
   // Check each pair of memory operands from both instructions, which can't
   // alias only if all pairs won't alias.
   for (auto *MMOa : memoperands())
     for (auto *MMOb : Other.memoperands())
-      if (MemOperandsHaveAlias(MFI, AA, UseTBAA, MMOa, MMOb))
+      if (MemOperandsHaveAlias(TM, MFI, AA, UseTBAA, MMOa, MMOb))
         return true;
 
   return false;
 }
 
 /// hasOrderedMemoryRef - Return true if this instruction may have an ordered
 /// or volatile memory reference, or if the information describing the memory
 /// reference is not available. Return false if it is known to have no ordered
if (DebugInstrNum == 0)
     DebugInstrNum = getParent()->getParent()->getNewDebugInstrNum();
   return DebugInstrNum;
 }
 
 unsigned MachineInstr::getDebugInstrNum(MachineFunction &MF) {
   if (DebugInstrNum == 0)
     DebugInstrNum = MF.getNewDebugInstrNum();
   return DebugInstrNum;
 }

llvm/lib/Target/TargetMachine.cpp

 std::pair<int, int> TargetMachine::parseBinutilsVersion(StringRef Version) {
   if (Version == "none")
     return {INT_MAX, INT_MAX}; // Make binutilsIsAtLeast() return true.
   std::pair<int, int> Ret;
   if (!Version.consumeInteger(10, Ret.first) && Version.consume_front("."))
     Version.consumeInteger(10, Ret.second);
   return Ret;
 }
+
+bool TargetMachine::areMemAccessesTriviallyDisjoint(
+    uint64_t BaseAddrA, uint64_t OffsetA, uint64_t WidthA, uint64_t AlignA,
+    unsigned AddrSpaceA, uint64_t BaseAddrB, uint64_t OffsetB, uint64_t WidthB,
+    uint64_t AlignB, unsigned AddrSpaceB) const {
+  if (AddrSpaceA != AddrSpaceB) {
+    return false;
+  }
+
+  // Check whether two memory accesses with the same address space overlap,
+  // ignoring alignment.
+  uint64_t StartAddrA = BaseAddrA + OffsetA;
+  uint64_t EndAddrA = StartAddrA + WidthA;
+  uint64_t StartAddrB = BaseAddrB + OffsetB;
+  uint64_t EndAddrB = StartAddrB + WidthB;
+  return std::max(StartAddrA, StartAddrB) >= std::min(EndAddrA, EndAddrB);
+}