[GlobalISel] Fix load-or combine moving loads across potential aliasing stores.

[aemerson]

Summary

Although this combine checks that there's no load folding barriers between the loads that it's trying to merge, it was inserting the load at the MIRBuilder's default insertion point, which is the G_OR use inst.

This was causing a miscompile in the test suite's SingleSource/Regression/C/gcc-c-torture/execute/GCC-C-execute-bswap-2

[paquette]

Oh wow.

LGTM, thanks!

llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h

private:
   ///
   /// Checks if every register in \p RegsToVisit is defined by a load
   /// instruction + some arithmetic.
   ///
   /// \param [out] MemOffset2Idx - Maps the byte positions each load ends up
   /// at to the index of the load.
   /// \param [in] MemSizeInBits - The number of bits each load should produce.
   ///
-  /// \returns The lowest-index load found and the lowest index on success.
-  Optional<std::pair<GZExtLoad *, int64_t>> findLoadOffsetsForLoadOrCombine(
+  /// \returns On success, a 3-tuple containing lowest-index load found, the
+  /// lowest index, and the last load in the sequence.
+  Optional<std::tuple<GZExtLoad *, int64_t, GZExtLoad *>>
+  findLoadOffsetsForLoadOrCombine(
       SmallDenseMap<int64_t, int64_t, 8> &MemOffset2Idx,
       const SmallVector<Register, 8> &RegsToVisit,
       const unsigned MemSizeInBits);
 
   /// Examines the G_PTR_ADD instruction \p PtrAdd and determines if performing
   /// a re-association of its operands would break an existing legal addressing
   /// mode that the address computation currently represents.
   bool reassociationCanBreakAddressingModePattern(MachineInstr &PtrAdd);
 };
 } // namespace llvm
 
 #endif

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/CodeGen/TargetOpcodes.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Target/TargetMachine.h"
+#include <tuple>
 
 #define DEBUG_TYPE "gi-combiner"
 
 using namespace llvm;
 using namespace MIPatternMatch;
 
 // Option to allow testing of the combiner while no targets know about indexed
 // addressing.
if (!Load)
     return None;
 
   if (!Load->isUnordered() || Load->getMemSizeInBits() != MemSizeInBits)
     return None;
 
   return std::make_pair(Load, Shift / MemSizeInBits);
 }
 
-Optional<std::pair<GZExtLoad *, int64_t>>
+Optional<std::tuple<GZExtLoad *, int64_t, GZExtLoad *>>
 CombinerHelper::findLoadOffsetsForLoadOrCombine(
     SmallDenseMap<int64_t, int64_t, 8> &MemOffset2Idx,
     const SmallVector<Register, 8> &RegsToVisit, const unsigned MemSizeInBits) {
 
   // Each load found for the pattern. There should be one for each RegsToVisit.
   SmallSetVector<const MachineInstr *, 8> Loads;
 
   // The lowest index used in any load. (The lowest "i" for each x[i].)
   int64_t LowestIdx = INT64_MAX;
 
   // The load which uses the lowest index.
   GZExtLoad *LowestIdxLoad = nullptr;
 
   // Keeps track of the load indices we see. We shouldn't see any indices twice.
   SmallSet<int64_t, 8> SeenIdx;
 
   // Ensure each load is in the same MBB.
   // TODO: Support multiple MachineBasicBlocks.
   MachineBasicBlock *MBB = nullptr;
   const MachineMemOperand *MMO = nullptr;
 
   // Earliest instruction-order load in the pattern.
-  MachineInstr *EarliestLoad = nullptr;
+  GZExtLoad *EarliestLoad = nullptr;
 
   // Latest instruction-order load in the pattern.
-  MachineInstr *LatestLoad = nullptr;
+  GZExtLoad *LatestLoad = nullptr;
 
   // Base pointer which every load should share.
   Register BasePtr;
 
   // We want to find a load for each register. Each load should have some
   // appropriate bit twiddling arithmetic. During this loop, we will also keep
   // track of the load which uses the lowest index. Later, we will check if we
   // can use its pointer in the final, combined load.
for (const auto &MI : instructionsWithoutDebug(EarliestLoad->getIterator(),
     if (Loads.count(&MI))
       continue;
     if (MI.isLoadFoldBarrier())
       return None;
     if (Iter++ == MaxIter)
       return None;
   }
 
-  return std::make_pair(LowestIdxLoad, LowestIdx);
+  return std::make_tuple(LowestIdxLoad, LowestIdx, LatestLoad);
 }
 
 bool CombinerHelper::matchLoadOrCombine(
     MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) {
   assert(MI.getOpcode() == TargetOpcode::G_OR);
   MachineFunction &MF = *MI.getMF();
   // Assuming a little-endian target, transform:
   //  s8 *a = ...
bool CombinerHelper::matchLoadOrCombine(
   // Check if each register feeding into each OR is a load from the same
   // base pointer + some arithmetic.
   //
   // e.g. a[0], a[1] << 8, a[2] << 16, etc.
   //
   // Also verify that each of these ends up putting a[i] into the same memory
   // offset as a load into a wide type would.
   SmallDenseMap<int64_t, int64_t, 8> MemOffset2Idx;
-  GZExtLoad *LowestIdxLoad;
+  GZExtLoad *LowestIdxLoad, *LatestLoad;
   int64_t LowestIdx;
   auto MaybeLoadInfo = findLoadOffsetsForLoadOrCombine(
       MemOffset2Idx, *RegsToVisit, NarrowMemSizeInBits);
   if (!MaybeLoadInfo)
     return false;
-  std::tie(LowestIdxLoad, LowestIdx) = *MaybeLoadInfo;
+  std::tie(LowestIdxLoad, LowestIdx, LatestLoad) = *MaybeLoadInfo;
 
   // We have a bunch of loads being OR'd together. Using the addresses + offsets
   // we found before, check if this corresponds to a big or little endian byte
   // pattern. If it does, then we can represent it using a load + possibly a
   // BSWAP.
   bool IsBigEndianTarget = MF.getDataLayout().isBigEndian();
   Optional<bool> IsBigEndian = isBigEndian(MemOffset2Idx, LowestIdx);
   if (!IsBigEndian.hasValue())
bool CombinerHelper::matchLoadOrCombine(
   LLVMContext &C = MF.getFunction().getContext();
   auto &DL = MF.getDataLayout();
   bool Fast = false;
   if (!getTargetLowering().allowsMemoryAccess(C, DL, Ty, *NewMMO, &Fast) ||
       !Fast)
     return false;
 
   MatchInfo = [=](MachineIRBuilder &MIB) {
+    MIB.setInstrAndDebugLoc(*LatestLoad);
     Register LoadDst = NeedsBSwap ? MRI.cloneVirtualRegister(Dst) : Dst;
     MIB.buildLoad(LoadDst, Ptr, *NewMMO);
     if (NeedsBSwap)
       MIB.buildBSwap(Dst, LoadDst);
   };
   return true;
 }
 

llvm/test/CodeGen/AArch64/GlobalISel/prelegalizer-combiner-load-or-pattern.mir

bb.0:
     $w1 = COPY %full_load(s32)
     RET_ReallyLR implicit $w1
 
 ...
 ---
 name:            dont_combine_store_between_different_mbb
 tracksRegLiveness: true
 body:             |
-  ; There is a store between the two loads, hidden away in a different MBB.
-  ; We should not combine here.
-
   ; LITTLE-LABEL: name: dont_combine_store_between_different_mbb
   ; LITTLE: bb.0:
   ; LITTLE:   successors: %bb.1(0x80000000)
   ; LITTLE:   liveins: $x0, $x1
   ; LITTLE:   %cst_1:_(s64) = G_CONSTANT i64 1
   ; LITTLE:   %cst_16:_(s32) = G_CONSTANT i32 16
   ; LITTLE:   %ptr:_(p0) = COPY $x1
   ; LITTLE:   %ptr_elt_1:_(p0) = G_PTR_ADD %ptr, %cst_1(s64)
body:             |
   ; BIG:   G_STORE %some_val(s32), %other_ptr(p0) :: (store (s16))
   ; BIG: bb.2:
   ; BIG:   liveins: $x0, $x1
   ; BIG:   %elt1:_(s32) = G_ZEXTLOAD %ptr_elt_1(p0) :: (load (s16))
   ; BIG:   %high_half:_(s32) = nuw G_SHL %elt1, %cst_16(s32)
   ; BIG:   %full_load:_(s32) = G_OR %low_half, %high_half
   ; BIG:   $w1 = COPY %full_load(s32)
   ; BIG:   RET_ReallyLR implicit $w1
+  ; There is a store between the two loads, hidden away in a different MBB.
+  ; We should not combine here.
+
 
   bb.0:
     successors: %bb.1(0x80000000)
     liveins: $x0, $x1
     ; If there is a store between any of the loads, then do not combine.
 
     %cst_1:_(s64) = G_CONSTANT i64 1
     %cst_16:_(s32) = G_CONSTANT i32 16
bb.2:
     $w1 = COPY %full_load(s32)
     RET_ReallyLR implicit $w1
 
 ...
 ---
 name:            different_mbb
 tracksRegLiveness: true
 body:             |
-  ; It should be possible to combine here, but it's not supported right now.
-
   ; LITTLE-LABEL: name: different_mbb
   ; LITTLE: bb.0:
   ; LITTLE:   successors: %bb.1(0x80000000)
   ; LITTLE:   liveins: $x0, $x1
   ; LITTLE:   %cst_1:_(s64) = G_CONSTANT i64 1
   ; LITTLE:   %cst_16:_(s32) = G_CONSTANT i32 16
   ; LITTLE:   %ptr:_(p0) = COPY $x1
   ; LITTLE:   %ptr_elt_1:_(p0) = G_PTR_ADD %ptr, %cst_1(s64)
body:             |
   ; BIG:   %low_half:_(s32) = G_ZEXTLOAD %ptr(p0) :: (load (s16))
   ; BIG: bb.1:
   ; BIG:   liveins: $x0, $x1
   ; BIG:   %elt1:_(s32) = G_ZEXTLOAD %ptr_elt_1(p0) :: (load (s16))
   ; BIG:   %high_half:_(s32) = nuw G_SHL %elt1, %cst_16(s32)
   ; BIG:   %full_load:_(s32) = G_OR %low_half, %high_half
   ; BIG:   $w1 = COPY %full_load(s32)
   ; BIG:   RET_ReallyLR implicit $w1
+  ; It should be possible to combine here, but it's not supported right now.
+
 
   bb.0:
     successors: %bb.1(0x80000000)
     liveins: $x0, $x1
 
     %cst_1:_(s64) = G_CONSTANT i64 1
     %cst_16:_(s32) = G_CONSTANT i32 16
 
bb.0:
     %ptr_elt_1:_(p0) = G_PTR_ADD %ptr, %cst_1(s64)
 
     %elt1:_(s32) = G_ZEXTLOAD %ptr_elt_1(p0) :: (load (s16))
     %high_half:_(s32) = nuw G_SHL %elt1, %cst_16(s32)
 
     %full_load:_(s32) = G_OR %low_half, %high_half
     $w1 = COPY %full_load(s32)
     RET_ReallyLR implicit $w1
+
+...
+---
+name:            store_between_loads_and_or
+alignment:       4
+tracksRegLiveness: true
+
+liveins:
+  - { reg: '$x0' }
+  - { reg: '$x1' }
+frameInfo:
+  maxAlignment:    1
+body:             |
+  bb.1:
+    liveins: $x0, $x1
+    ; Check that we build the G_LOAD at the point of the last load, instead of place of the G_OR.
+    ; We could have a G_STORE in between which may not be safe to move the load across.
+  liveins: $x0, $x1
+    ; LITTLE-LABEL: name: store_between_loads_and_or
+    ; LITTLE: liveins: $x0, $x1, $x0, $x1
+    ; LITTLE: [[COPY:%[0-9]+]]:_(p0) = COPY $x0
+    ; LITTLE: [[COPY1:%[0-9]+]]:_(p0) = COPY $x1
+    ; LITTLE: [[C:%[0-9]+]]:_(s8) = G_CONSTANT i8 1
+    ; LITTLE: [[LOAD:%[0-9]+]]:_(s32) = G_LOAD [[COPY]](p0) :: (load (s32), align 1)
+    ; LITTLE: G_STORE [[C]](s8), [[COPY1]](p0) :: (store (s8))
+    ; LITTLE: $w0 = COPY [[LOAD]](s32)
+    ; LITTLE: RET_ReallyLR implicit $w0
+    ; BIG-LABEL: name: store_between_loads_and_or
+    ; BIG: liveins: $x0, $x1, $x0, $x1
+    ; BIG: [[COPY:%[0-9]+]]:_(p0) = COPY $x0
+    ; BIG: [[COPY1:%[0-9]+]]:_(p0) = COPY $x1
+    ; BIG: [[C:%[0-9]+]]:_(s8) = G_CONSTANT i8 1
+    ; BIG: [[LOAD:%[0-9]+]]:_(s32) = G_LOAD [[COPY]](p0) :: (load (s32), align 1)
+    ; BIG: [[BSWAP:%[0-9]+]]:_(s32) = G_BSWAP [[LOAD]]
+    ; BIG: G_STORE [[C]](s8), [[COPY1]](p0) :: (store (s8))
+    ; BIG: $w0 = COPY [[BSWAP]](s32)
+    ; BIG: RET_ReallyLR implicit $w0
+  %0:_(p0) = COPY $x0
+  %1:_(p0) = COPY $x1
+  %12:_(s8) = G_CONSTANT i8 1
+  %15:_(s32) = G_CONSTANT i32 8
+  %19:_(s32) = G_CONSTANT i32 16
+  %23:_(s32) = G_CONSTANT i32 24
+  %13:_(s32) = G_ZEXTLOAD %0:_(p0) :: (load (s8))
+  %3:_(s64) = G_CONSTANT i64 1
+  %4:_(p0) = G_PTR_ADD %0:_, %3:_(s64)
+  %14:_(s32) = G_ZEXTLOAD %4:_(p0) :: (load (s8))
+  %6:_(s64) = G_CONSTANT i64 2
+  %7:_(p0) = G_PTR_ADD %0:_, %6:_(s64)
+  %18:_(s32) = G_ZEXTLOAD %7:_(p0) :: (load (s8))
+  %9:_(s64) = G_CONSTANT i64 3
+  %10:_(p0) = G_PTR_ADD %0:_, %9:_(s64)
+  %22:_(s32) = G_ZEXTLOAD %10:_(p0) :: (load (s8))
+  G_STORE %12:_(s8), %1:_(p0) :: (store (s8))
+  %16:_(s32) = nuw nsw G_SHL %14:_, %15:_(s32)
+  %17:_(s32) = G_OR %16:_, %13:_
+  %20:_(s32) = nuw nsw G_SHL %18:_, %19:_(s32)
+  %21:_(s32) = G_OR %17:_, %20:_
+  %24:_(s32) = nuw G_SHL %22:_, %23:_(s32)
+  %25:_(s32) = G_OR %21:_, %24:_
+  $w0 = COPY %25:_(s32)
+  RET_ReallyLR implicit $w0
+
+...