[CodeGen] Add support for multiple memory operands in MachineInstr::mayAlias

[Kayjukh]

Summary

To support all targets, the mayAlias member function needs to support instructions with multiple operands.

This revision also changes the order of the emitted instructions in some test cases.

[efriedma]

I'd like to see an MIR test that shows the aliasing check actually working correctly.

[Kayjukh]

Update instruction ordering in failing test cases.

[dmgreen]

llvm/lib/CodeGen/MachineInstr.cpp

1280

It would seem incorrect to return false here now? Same for the pseudo values above.

[Kayjukh]

In D80161#2042626, @efriedma wrote:

I'd like to see an MIR test that shows the aliasing check actually working correctly.

I will have to find something that fits in a test case and covers this case. Working on it!

llvm/lib/CodeGen/MachineInstr.cpp

1280

Yes, we should only return if the result is true. For the pseudo-values I guess we can just skip the checks entirely and only update the value of SameVal.
It leads to more test cases failing because of instruction ordering. I will update the diff as soon as I fixed all of these.

[dmgreen]

llvm/lib/CodeGen/MachineInstr.cpp

1280

If the code before worked with two mmo's, would it be possible to do something like:

auto HasAlias = [](MMOa, MMOb) {
  old code as it was before return true/false;
};

for (auto &MMOa : memoperands()) {
  for (auto &MMOb : Other.memoperands()) {
    if (HasAlias(MMOa, MMOb))
      return true;
return false;

[Kayjukh]

llvm/lib/CodeGen/MachineInstr.cpp

1280

It would definitely make things clearer. Thanks for your suggestion!

[Kayjukh]

Simplify the method's control flow by wrapping the old dependency checking code in a helper lambda and calling it for each pair of memory operands.

[Kayjukh]

In D80161#2043591, @Kayjukh wrote:

In D80161#2042626, @efriedma wrote:

I'd like to see an MIR test that shows the aliasing check actually working correctly.

I will have to find something that fits in a test case and covers this case. Working on it!

@efriedma Except for some variations in instruction scheduling caused by the calls to mayAlias when adding chain dependencies, I cannot seem to find anything that could make for a good test case. I tried looking into the AArch64LoadStoreOptimizer as well as the ARMLoadStoreOptimizer but none of my attempts triggered the

// FIXME: Need to handle multiple memory operands to support all targets.
if (!hasOneMemOperand() || !Other.hasOneMemOperand())
  return true;

code path, even when compiling fairly complex codes for those targets.

Handcrafting a MIR test file that would trigger this code path proves to be quite challenging since we have no direct control over the propagation of memory operands. Did you have a specific test scenario in mind?

[efriedma]

On ARM specifically, operations don't usually more than one memoperand, with the exception of load store paired/multiple. So yes, I can see it would be hard to trigger outside of scheduling.

Maybe we could add some debug output to the scheduler showing when it does/does not add a dependency, and check that. So it would be checking scheduling, but not the final schedule.

[Kayjukh]

Add some debug output to the instruction sheduler to signal wether or not a chain dependency has been added between two given instructions. This change allows us to properly test the effect of handling multiple memory operands in alias queries on instruction scheduling.

This update also adds a test case that makes use of the newly added scheduler debug output.

[Kayjukh]

In D80161#2044571, @efriedma wrote:

On ARM specifically, operations don't usually more than one memoperand, with the exception of load store paired/multiple. So yes, I can see it would be hard to trigger outside of scheduling.

Maybe we could add some debug output to the scheduler showing when it does/does not add a dependency, and check that. So it would be checking scheduling, but not the final schedule.

Following your suggestion, I added some debug output to the instruction scheduler. It makes it way easier to test the changes as we don't have to go through a rarely executed code path to see a change in the output.

[efriedma]

LGTM with one small change.

llvm/test/CodeGen/X86/instr-sched-multiple-memops.mir

1 ↗

(On Diff #265561)

"# REQUIRES: asserts"; release builds don't support the "-debug" flag.

[Kayjukh]

Update FileCheck directives in

llvm/test/CodeGen/ARM/cortex-a57-misched-vldm-wrback.ll
llvm/test/CodeGen/ARM/cortex-a57-misched-vstm-wrback.ll
llvm/test/CodeGen/ARM/cortex-a57-misched-vstm.ll

to avoid matching the new instruction scheduler debug output.

[Kayjukh]

@efriedma Thanks for your feedback! I had to make some minor adjustments to ARM test cases. If it's still good for you, I will land the patch.

[efriedma]

Yes, looks fine.

llvm/lib/CodeGen/MachineInstr.cpp

bool MachineInstr::mayAlias(AAResults *AA, const MachineInstr &Other,
   // Both instructions must be memory operations to be able to alias.
   if (!mayLoadOrStore() || !Other.mayLoadOrStore())
     return false;
 
   // Let the target decide if memory accesses cannot possibly overlap.
   if (TII->areMemAccessesTriviallyDisjoint(*this, Other))
     return false;
 
-  // FIXME: Need to handle multiple memory operands to support all targets.
-  if (!hasOneMemOperand() || !Other.hasOneMemOperand())
+  if (memoperands_empty() || Other.memoperands_empty())
     return true;
 
-  MachineMemOperand *MMOa = *memoperands_begin();
-  MachineMemOperand *MMOb = *Other.memoperands_begin();
-
+  for (auto &&MMOa : memoperands()) {
+    for (auto &&MMOb : Other.memoperands()) {
       // 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.
 
       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;
 
       const Value *ValA = MMOa->getValue();
       const Value *ValB = MMOb->getValue();
       bool SameVal = (ValA && ValB && (ValA == ValB));
       if (!SameVal) {
         const PseudoSourceValue *PSVa = MMOa->getPseudoValue();
         const PseudoSourceValue *PSVb = MMOb->getPseudoValue();
         if (PSVa && ValB && !PSVa->mayAlias(&MFI))
           return false;
         if (PSVb && ValA && !PSVb->mayAlias(&MFI))
           return false;
         if (PSVa && PSVb && (PSVa == PSVb))
           SameVal = true;
       }
 
       if (SameVal) {
         if (!KnownWidthA || !KnownWidthB)
           return true;
         int64_t MaxOffset = std::max(OffsetA, OffsetB);
         int64_t LowWidth = (MinOffset == OffsetA) ? WidthA : WidthB;
         return (MinOffset + LowWidth > MaxOffset);
       }
 
       if (!AA)
         return true;
 
       if (!ValA || !ValB)
         return true;
 
       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;
 
-  AliasResult AAResult = AA->alias(
-      MemoryLocation(ValA, OverlapA,
+      AliasResult AAResult =
+          AA->alias(MemoryLocation(ValA, OverlapA,
                                    UseTBAA ? MMOa->getAAInfo() : AAMDNodes()),
                     MemoryLocation(ValB, OverlapB,
                                    UseTBAA ? MMOb->getAAInfo() : AAMDNodes()));
 
-  return (AAResult != NoAlias);
+      if (AAResult != NoAlias)
+        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
 /// memory references.
 bool MachineInstr::hasOrderedMemoryRef() const {
   // An instruction known never to access memory won't have a volatile access.

llvm/test/CodeGen/AArch64/merge-store-dependency.ll

 ; A53-NEXT:    .cfi_def_cfa_offset 16
 ; A53-NEXT:    .cfi_offset w19, -8
 ; A53-NEXT:    .cfi_offset w30, -16
 ; A53-NEXT:    movi v0.2d, #0000000000000000
 ; A53-NEXT:    mov x8, x0
 ; A53-NEXT:    mov x19, x8
 ; A53-NEXT:    mov w0, w1
 ; A53-NEXT:    mov w9, #256
+; A53-NEXT:    stp x2, x3, [x8, #32]
+; A53-NEXT:    mov x2, x8
 ; A53-NEXT:    str q0, [x19, #16]!
 ; A53-NEXT:    str w1, [x19]
 ; A53-NEXT:    mov w1, #4
-; A53-NEXT:    stp x2, x3, [x8, #32]
-; A53-NEXT:    mov x2, x8
 ; A53-NEXT:    str q0, [x8]
 ; A53-NEXT:    strh w9, [x8, #24]
 ; A53-NEXT:    str wzr, [x8, #20]
 ; A53-NEXT:    bl fcntl
 ; A53-NEXT:    adrp x9, gv0
 ; A53-NEXT:    add x9, x9, :lo12:gv0
 ; A53-NEXT:    cmp x19, x9
 ; A53-NEXT:    b.eq .LBB0_4

llvm/test/CodeGen/ARM/big-endian-neon-fp16-bitconv.ll

 ; CHECK-NEXT:    vrev64.16 q8, q8
 ; CHECK-NEXT:    vadd.f16 q8, q9, q8
 ; CHECK-NEXT:    vrev32.16 q8, q8
 ; CHECK-NEXT:    vmov.32 r12, d17[1]
 ; CHECK-NEXT:    vmov.32 r2, d17[0]
 ; CHECK-NEXT:    vmov.32 r3, d16[1]
 ; CHECK-NEXT:    vmov.32 r1, d16[0]
 ; CHECK-NEXT:    subs r12, r12, #1
+; CHECK-NEXT:    str r12, [r0, #12]
 ; CHECK-NEXT:    sbcs r2, r2, #0
+; CHECK-NEXT:    str r2, [r0, #8]
 ; CHECK-NEXT:    sbcs r3, r3, #0
 ; CHECK-NEXT:    sbc r1, r1, #0
 ; CHECK-NEXT:    stm r0, {r1, r3}
-; CHECK-NEXT:    str r2, [r0, #8]
-; CHECK-NEXT:    str r12, [r0, #12]
 ; CHECK-NEXT:    bx lr
 ; CHECK-NEXT:    .p2align 4
 ; CHECK-NEXT:  @ %bb.1:
 ; CHECK-NEXT:  .LCPI18_0:
 ; CHECK-NEXT:    .short 0xbc00 @ half -1
 ; CHECK-NEXT:    .short 0x3c00 @ half 1
 ; CHECK-NEXT:    .short 0xbc00 @ half -1
 ; CHECK-NEXT:    .short 0x3c00 @ half 1

llvm/test/CodeGen/Thumb2/mve-float32regloops.ll

 ; CHECK-NEXT:    @ Child Loop BB16_10 Depth 2
 ; CHECK-NEXT:    vldrw.u32 q0, [r1], #16
 ; CHECK-NEXT:    ldrd r0, r7, [r12]
 ; CHECK-NEXT:    ldrd r4, r6, [r12, #8]
 ; CHECK-NEXT:    ldrd r5, r3, [r12, #16]
 ; CHECK-NEXT:    ldrd lr, r10, [r12, #24]
 ; CHECK-NEXT:    vstrb.8 q0, [r11], #16
 ; CHECK-NEXT:    vldrw.u32 q0, [r8], #32
+; CHECK-NEXT:    strd r11, r1, [sp, #24] @ 8-byte Folded Spill
 ; CHECK-NEXT:    vldrw.u32 q1, [r8, #-28]
 ; CHECK-NEXT:    vmul.f32 q0, q0, r0
 ; CHECK-NEXT:    vldrw.u32 q6, [r8, #-24]
 ; CHECK-NEXT:    vldrw.u32 q4, [r8, #-20]
 ; CHECK-NEXT:    vfma.f32 q0, q1, r7
 ; CHECK-NEXT:    vldrw.u32 q5, [r8, #-16]
 ; CHECK-NEXT:    vfma.f32 q0, q6, r4
 ; CHECK-NEXT:    vldrw.u32 q2, [r8, #-12]
 ; CHECK-NEXT:    vfma.f32 q0, q4, r6
 ; CHECK-NEXT:    vldrw.u32 q3, [r8, #-8]
 ; CHECK-NEXT:    vfma.f32 q0, q5, r5
-; CHECK-NEXT:    vldrw.u32 q1, [r8, #-4]
-; CHECK-NEXT:    vfma.f32 q0, q2, r3
 ; CHECK-NEXT:    ldr r0, [sp, #16] @ 4-byte Reload
+; CHECK-NEXT:    vfma.f32 q0, q2, r3
+; CHECK-NEXT:    vldrw.u32 q1, [r8, #-4]
 ; CHECK-NEXT:    vfma.f32 q0, q3, lr
-; CHECK-NEXT:    strd r11, r1, [sp, #24] @ 8-byte Folded Spill
-; CHECK-NEXT:    vfma.f32 q0, q1, r10
 ; CHECK-NEXT:    cmp r0, #16
+; CHECK-NEXT:    vfma.f32 q0, q1, r10
 ; CHECK-NEXT:    blo .LBB16_7
 ; CHECK-NEXT:  @ %bb.5: @ %for.body.preheader
 ; CHECK-NEXT:    @ in Loop: Header=BB16_4 Depth=1
 ; CHECK-NEXT:    ldr.w lr, [sp] @ 4-byte Reload
 ; CHECK-NEXT:    dls lr, lr
 ; CHECK-NEXT:    ldr r7, [sp, #8] @ 4-byte Reload
 ; CHECK-NEXT:  .LBB16_6: @ %for.body
 ; CHECK-NEXT:    @ Parent Loop BB16_4 Depth=1

llvm/test/CodeGen/Thumb2/mve-phireg.ll

 ; CHECK-NEXT:    vmov r6, s3
 ; CHECK-NEXT:    ldr r0, [r7, #4]!
 ; CHECK-NEXT:    movw r4, :lower16:e
 ; CHECK-NEXT:    vmov.32 q4[0], r5
 ; CHECK-NEXT:    movt r4, :upper16:e
 ; CHECK-NEXT:    vmov q1, q4
 ; CHECK-NEXT:    vmov s1, r7
 ; CHECK-NEXT:    vmov.32 q1[1], r6
-; CHECK-NEXT:    mov.w r10, #0
-; CHECK-NEXT:    vmov.32 q1[2], r5
 ; CHECK-NEXT:    vmov.32 q5[0], r7
+; CHECK-NEXT:    vmov.32 q1[2], r5
+; CHECK-NEXT:    vmov s9, r4
 ; CHECK-NEXT:    vmov.32 q1[3], r4
-; CHECK-NEXT:    strd r0, r10, [sp, #24]
+; CHECK-NEXT:    vdup.32 q6, r7
 ; CHECK-NEXT:    vstrw.32 q1, [sp, #76]
 ; CHECK-NEXT:    vmov q1, q5
-; CHECK-NEXT:    vmov s9, r4
 ; CHECK-NEXT:    vmov.32 q1[1], r7
-; CHECK-NEXT:    vdup.32 q6, r7
 ; CHECK-NEXT:    vmov.f32 s2, s1
 ; CHECK-NEXT:    vmov.f32 s8, s0
 ; CHECK-NEXT:    vmov.32 q1[2], r6
 ; CHECK-NEXT:    vmov q3, q6
 ; CHECK-NEXT:    vmov q7, q6
 ; CHECK-NEXT:    vmov.f32 s10, s1
 ; CHECK-NEXT:    mov.w r8, #4
+; CHECK-NEXT:    mov.w r10, #0
 ; CHECK-NEXT:    vmov.32 q1[3], r4
 ; CHECK-NEXT:    vmov.32 q3[0], r4
 ; CHECK-NEXT:    vmov.32 q7[1], r4
 ; CHECK-NEXT:    str r1, [r0]
 ; CHECK-NEXT:    vmov.f32 s11, s3
 ; CHECK-NEXT:    movs r1, #64
 ; CHECK-NEXT:    strh.w r8, [sp, #390]
+; CHECK-NEXT:    strd r0, r10, [sp, #24]
 ; CHECK-NEXT:    vstrw.32 q0, [sp, #44]
 ; CHECK-NEXT:    str r0, [r0]
 ; CHECK-NEXT:    vstrw.32 q2, [r0]
 ; CHECK-NEXT:    vstrw.32 q7, [r0]
 ; CHECK-NEXT:    vstrw.32 q3, [r0]
 ; CHECK-NEXT:    vstrw.32 q1, [r0]
 ; CHECK-NEXT:    bl __aeabi_memclr4
 ; CHECK-NEXT:    vmov.32 q5[1], r5

llvm/test/CodeGen/Thumb2/mve-vst3.ll

 ; CHECK-NEXT:    vmov.f32 s8, s7
 ; CHECK-NEXT:    vmov.f32 s10, s1
 ; CHECK-NEXT:    vmov r2, s8
 ; CHECK-NEXT:    vmov r0, s10
 ; CHECK-NEXT:    vmov.f64 d4, d2
 ; CHECK-NEXT:    vmov.f32 s9, s6
 ; CHECK-NEXT:    vmov.f32 s10, s0
 ; CHECK-NEXT:    vmov.f32 s11, s5
-; CHECK-NEXT:    strd r2, r0, [r1, #16]
 ; CHECK-NEXT:    vstrw.32 q2, [r1]
+; CHECK-NEXT:    strd r2, r0, [r1, #16]
 ; CHECK-NEXT:    pop {r4, pc}
 entry:
   %s1 = getelementptr <2 x i32>, <2 x i32>* %src, i32 0
   %l1 = load <2 x i32>, <2 x i32>* %s1, align 4
   %s2 = getelementptr <2 x i32>, <2 x i32>* %src, i32 1
   %l2 = load <2 x i32>, <2 x i32>* %s2, align 4
   %s3 = getelementptr <2 x i32>, <2 x i32>* %src, i32 2
   %l3 = load <2 x i32>, <2 x i32>* %s3, align 4

llvm/test/CodeGen/Thumb2/umulo-128-legalisation-lowering.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=thumbv7-unknown-none-gnueabi | FileCheck %s --check-prefixes=THUMBV7
 
 define { i128, i8 } @muloti_test(i128 %l, i128 %r) unnamed_addr #0 {
 ; THUMBV7-LABEL: muloti_test:
 ; THUMBV7:       @ %bb.0: @ %start
 ; THUMBV7-NEXT:    .save {r4, r5, r6, r7, r8, r9, r10, r11, lr}
 ; THUMBV7-NEXT:    push.w {r4, r5, r6, r7, r8, r9, r10, r11, lr}
 ; THUMBV7-NEXT:    .pad #44
 ; THUMBV7-NEXT:    sub sp, #44
-; THUMBV7-NEXT:    ldrd r4, r7, [sp, #88]
-; THUMBV7-NEXT:    mov r5, r3
 ; THUMBV7-NEXT:    str r0, [sp, #40] @ 4-byte Spill
 ; THUMBV7-NEXT:    movs r0, #0
-; THUMBV7-NEXT:    strd r4, r7, [sp]
-; THUMBV7-NEXT:    mov r1, r3
+; THUMBV7-NEXT:    ldrd r4, r7, [sp, #88]
+; THUMBV7-NEXT:    mov r5, r3
 ; THUMBV7-NEXT:    strd r0, r0, [sp, #8]
+; THUMBV7-NEXT:    mov r1, r3
 ; THUMBV7-NEXT:    mov r6, r2
 ; THUMBV7-NEXT:    mov r0, r2
 ; THUMBV7-NEXT:    movs r2, #0
 ; THUMBV7-NEXT:    movs r3, #0
+; THUMBV7-NEXT:    strd r4, r7, [sp]
 ; THUMBV7-NEXT:    bl __multi3
 ; THUMBV7-NEXT:    strd r1, r0, [sp, #32] @ 8-byte Folded Spill
 ; THUMBV7-NEXT:    strd r3, r2, [sp, #24] @ 8-byte Folded Spill
 ; THUMBV7-NEXT:    ldrd r2, r0, [sp, #96]
 ; THUMBV7-NEXT:    ldr.w r9, [sp, #80]
 ; THUMBV7-NEXT:    umull lr, r0, r0, r6
 ; THUMBV7-NEXT:    ldr.w r11, [sp, #84]
 ; THUMBV7-NEXT:    umull r3, r1, r5, r2

llvm/test/CodeGen/X86/store_op_load_fold2.ll

cond_true2732.preheader:                ; preds = %entry
         %tmp2670.us.us = load i64, i64* null         ; <i64> [#uses=1]
         %shift.upgrd.1 = zext i8 %tmp2674 to i64                ; <i64> [#uses=1]
         %tmp2675.us.us = shl i64 %tmp2670.us.us, %shift.upgrd.1         ; <i64> [#uses=1]
         %tmp2675not.us.us = xor i64 %tmp2675.us.us, -1          ; <i64> [#uses=1]
         %tmp2676.us.us = and i64 %tmp2667.us.us, %tmp2675not.us.us              ; <i64> [#uses=1]
         store i64 %tmp2676.us.us, i64* %tmp2666
         ret i32 0
 
-; INTEL:  and {{e..}}, dword ptr [356]
 ; INTEL:  and dword ptr [360], {{e..}}
-; FIXME:  mov dword ptr [356], {{e..}}
-; The above line comes out as 'mov 360, eax', but when the register is ecx it works?
+; INTEL:  and {{e..}}, dword ptr [356]
+; INTEL:  mov dword ptr [356], {{e..}}
 
-; ATT:  andl  356, %{{e..}}
 ; ATT:  andl  %{{e..}}, 360
+; ATT:  andl  356, %{{e..}}
 ; ATT:  movl  %{{e..}}, 356
 
 }