[DAGCombiner][NFC] Factor out ByteProvider

[jrbyrnes]

Summary

Bring ByteProvider into header to serve as generic utility.

[jrbyrnes]

Fix comments.

[jrbyrnes]

Restructure

[jrbyrnes]

@arsenm is that what you had in mind?

[jrbyrnes]

Format + Comments

[jrbyrnes]

Factor out common code for use in https://reviews.llvm.org/D142782 . Template class for eventual porting to GlobalISel.

[jrbyrnes]

Require contained class in ByteProvider to have getOpcode (class must be node in selection DAG)

[jrbyrnes]

Typo

[tschuett]

llvm/include/llvm/ADT/ByteProvider.h

26 ↗

(On Diff #499914)

Why struct, when you use private and public?

29 ↗

(On Diff #499914)

using instead of typedef?

51 ↗

(On Diff #499914)

Why struct?

93 ↗

(On Diff #499914)

Newline missing

[jrbyrnes]

Address review comments -- thanks @tschuett

[jrbyrnes]

Add outside reviewers

[arsenm]

llvm/include/llvm/ADT/ByteProvider.h

53 ↗

(On Diff #500262)

probably should use int64_t offsets?

[jrbyrnes]

int64_t offsets

[RKSimon]

llvm/include/llvm/ADT/ByteProvider.h

23 ↗

(On Diff #506212)

Is there anyway that we can avoid an anonymous namespace in a header like this?

[jrbyrnes]

Rebase + move is_op into ByteProvider. Thanks @RKSimon for taking a look.

[barannikov88]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

21

(Just being skeptical.)
IMHO the implementation is not that abstract to be put into ADT.
Comments and names suggest that it has relation to instruction selection.
Keeping it to SelectionDAG/TargetLowering/CodeGen would make the SFINAE redundant, too.
Is it going to be used for anything other than SDValue anyway?

[jrbyrnes]

Hi @barannikov88 -- thanks for your comments. I tend to agree that it is not "abstract enough" for ADT as it is basically an ISel util -- I have moved it into include/llvm/CodeGen

That said, I think it should be generic in that it should be agnostic between SDNode and SDValu -- DAGCombiner currently uses SDNode but I am working on a patch which calculates ByteProviders in terms of SDValues https://reviews.llvm.org/D142782 . Eventually we will want to extend this work to GlobalISel as well, so it seems we may also want MachineInstrs as the Src.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

8401–8403

Is there anywhere we can safely put a typedef to avoid carrying around the same template argument?

[jrbyrnes]

Typdef SDNode *

[tschuett]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

8401

using SDByteProvider = ByteProvider<SDNode*>;

[jrbyrnes]

Use SDByteProvider

[jrbyrnes]

Thanks all for comments thus far -- are there any objections to merging this?

[arsenm]

I'd agree include/llvm/CodeGen would be better place than ADT

[jrbyrnes]

ping =)

[RKSimon]

llvm/include/llvm/CodeGen/ByteProvider.h

2

llvm/CodeGen/ByteProvider.h

19

Fix header guards

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

8829

(style) missing assert message (or merge the 2 asserts):

assert(P.hasSrc() && isa<LoadSDNode>(P.Src.value()) && "Must be a memory byte provider");

8830

auto*

8867

(style) missing assert message (or merge the 2 asserts):

assert(P->hasSrc() && isa<LoadSDNode>(P->Src.value()) && "provenance should either be memory or zero");

8868

auto*

8949–8950

this assert isn't necessary as the cast<> will also assert (same for the other above which I suggested merging with the other assert....)

8950

auto *

[jrbyrnes]

Thanks @RKSimon

[RKSimon]

LGTM with one minor - does anyone else have any comments?

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

8950

auto *FirstLoad

[jrbyrnes]

Nit

[RKSimon]

llvm/include/llvm/CodeGen/ByteProvider.h

2

Missing include path

[jrbyrnes]

Include path

llvm/include/llvm/CodeGen/ByteProvider.h

+//===-- llvm/ADT/ByteProvider.h - Map bytes from dest to source -*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// \file
+// This file implements ByteProvider. The purpose of ByteProvider is to provide
+// a map between a target node's byte (byte position is DestOffset) and the
+// source (and byte position) that provides it (in Src and SrcOffset
+// respectively) See CodeGen/SelectionDAG/DAGCombiner.cpp MatchLoadCombine
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_BYTEPROVIDER_H
+#define LLVM_ADT_BYTEPROVIDER_H
+
+#include <optional>
+#include <type_traits>
+
+namespace llvm {
+
+/// Represents known origin of an individual byte in combine pattern. The
+/// value of the byte is either constant zero, or comes from memory /
+/// some other productive instruction (e.g. arithmetic instructions).
+/// Bit manipulation instructions like shifts are not ByteProviders, rather
+/// are used to extract Bytes.
+template <typename ISelOp> class ByteProvider {
+private:
+  ByteProvider<ISelOp>(std::optional<ISelOp> Src, int64_t DestOffset,
+                       int64_t SrcOffset)
+      : Src(Src), DestOffset(DestOffset), SrcOffset(SrcOffset) {}
+
+  // TODO -- use constraint in c++20
+  // Does this type correspond with an operation in selection DAG
+  template <typename T> class is_op {
+  private:
+    using yes = std::true_type;
+    using no = std::false_type;
+
+    // Only allow classes with member function getOpcode
+    template <typename U>
+    static auto test(int) -> decltype(std::declval<U>().getOpcode(), yes());
+
+    template <typename> static no test(...);
+
+  public:
+    using remove_pointer_t = typename std::remove_pointer<T>::type;
+    static constexpr bool value =
+        std::is_same<decltype(test<remove_pointer_t>(0)), yes>::value;
+  };
+
+public:
+  // For constant zero providers Src is set to nullopt. For actual providers
+  // Src represents the node which originally produced the relevant bits.
+  std::optional<ISelOp> Src = std::nullopt;
+  // DestOffset is the offset of the byte in the dest we are trying to map for.
+  int64_t DestOffset = 0;
+  // SrcOffset is the offset in the ultimate source node that maps to the
+  // DestOffset
+  int64_t SrcOffset = 0;
+
+  ByteProvider() = default;
+
+  static ByteProvider getSrc(std::optional<ISelOp> Val, int64_t ByteOffset,
+                             int64_t VectorOffset) {
+    static_assert(is_op<ISelOp>().value,
+                  "ByteProviders must contain an operation in selection DAG.");
+    return ByteProvider(Val, ByteOffset, VectorOffset);
+  }
+
+  static ByteProvider getConstantZero() {
+    return ByteProvider<ISelOp>(std::nullopt, 0, 0);
+  }
+  bool isConstantZero() const { return !Src; }
+
+  bool hasSrc() const { return Src.has_value(); }
+
+  bool hasSameSrc(const ByteProvider &Other) const { return Other.Src == Src; }
+
+  bool operator==(const ByteProvider &Other) const {
+    return Other.Src == Src && Other.DestOffset == DestOffset &&
+           Other.SrcOffset == SrcOffset;
+  }
+};
+} // end namespace llvm
+
+#endif // LLVM_ADT_BYTEPROVIDER_H

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

 // primarily intended to handle simplification opportunities that are implicit
 // in the LLVM IR and exposed by the various codegen lowering phases.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/IntervalMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallBitVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Analysis/VectorUtils.h"
+#include "llvm/CodeGen/ByteProvider.h"
 #include "llvm/CodeGen/DAGCombine.h"
 #include "llvm/CodeGen/ISDOpcodes.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineValueType.h"
 #include "llvm/CodeGen/RuntimeLibcalls.h"
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/CodeGen/SelectionDAGAddressAnalysis.h"
SDValue TryR =
       MatchFunnelPosNeg(LHSShiftArg, RHSShiftArg, RHSShiftAmt, LHSShiftAmt,
                         RExtOp0, LExtOp0, HasFSHR, ISD::FSHR, ISD::FSHL, DL);
   if (TryR)
     return TryR;
 
   return SDValue();
 }
 
-namespace {
-
-/// Represents known origin of an individual byte in load combine pattern. The
-/// value of the byte is either constant zero or comes from memory.
-struct ByteProvider {
-  // For constant zero providers Load is set to nullptr. For memory providers
-  // Load represents the node which loads the byte from memory.
-  // ByteOffset is the offset of the byte in the value produced by the load.
-  LoadSDNode *Load = nullptr;
-  unsigned ByteOffset = 0;
-  unsigned VectorOffset = 0;
-
-  ByteProvider() = default;
-
-  static ByteProvider getMemory(LoadSDNode *Load, unsigned ByteOffset,
-                                unsigned VectorOffset) {
-    return ByteProvider(Load, ByteOffset, VectorOffset);
-  }
-
-  static ByteProvider getConstantZero() { return ByteProvider(nullptr, 0, 0); }
-
-  bool isConstantZero() const { return !Load; }
-  bool isMemory() const { return Load; }
-
-  bool operator==(const ByteProvider &Other) const {
-    return Other.Load == Load && Other.ByteOffset == ByteOffset &&
-           Other.VectorOffset == VectorOffset;
-  }
-
-private:
-  ByteProvider(LoadSDNode *Load, unsigned ByteOffset, unsigned VectorOffset)
-      : Load(Load), ByteOffset(ByteOffset), VectorOffset(VectorOffset) {}
-};
-
-} // end anonymous namespace
-
 /// Recursively traverses the expression calculating the origin of the requested
 /// byte of the given value. Returns std::nullopt if the provider can't be
 /// calculated.
 ///
 /// For all the values except the root of the expression, we verify that the
 /// value has exactly one use and if not then return std::nullopt. This way if
 /// the origin of the byte is returned it's guaranteed that the values which
 /// contribute to the byte are not used outside of this expression.

 ///                  |     |     |     |
 ///                 zext  EVE*  EVE*  LOAD
 ///                  |     |     |
 ///                 EVE*  LOAD  LOAD
 ///                  |
 ///                 LOAD
 ///
 /// *ExtractVectorElement
-static const std::optional<ByteProvider>
+typedef SDNode *ByteSrc;
+
+static const std::optional<ByteProvider<ByteSrc>>
 calculateByteProvider(SDValue Op, unsigned Index, unsigned Depth,
                       std::optional<uint64_t> VectorIndex,
                       unsigned StartingIndex = 0) {
 
   // Typical i64 by i8 pattern requires recursion up to 8 calls depth
   if (Depth == 10)
     return std::nullopt;
 
case ISD::SHL: {
     if (BitShift % 8 != 0)
       return std::nullopt;
     uint64_t ByteShift = BitShift / 8;
 
     // If we are shifting by an amount greater than the index we are trying to
     // provide, then do not provide anything. Otherwise, subtract the index by
     // the amount we shifted by.
     return Index < ByteShift
-               ? ByteProvider::getConstantZero()
+               ? ByteProvider<ByteSrc>::getConstantZero()
                : calculateByteProvider(Op->getOperand(0), Index - ByteShift,
                                        Depth + 1, VectorIndex, Index);
   }
   case ISD::ANY_EXTEND:
   case ISD::SIGN_EXTEND:
   case ISD::ZERO_EXTEND: {
     SDValue NarrowOp = Op->getOperand(0);
     unsigned NarrowBitWidth = NarrowOp.getScalarValueSizeInBits();
     if (NarrowBitWidth % 8 != 0)
       return std::nullopt;
     uint64_t NarrowByteWidth = NarrowBitWidth / 8;
 
     if (Index >= NarrowByteWidth)
       return Op.getOpcode() == ISD::ZERO_EXTEND
-                 ? std::optional<ByteProvider>(ByteProvider::getConstantZero())
+                 ? std::optional<ByteProvider<ByteSrc>>(
+                       ByteProvider<ByteSrc>::getConstantZero())
                  : std::nullopt;
     return calculateByteProvider(NarrowOp, Index, Depth + 1, VectorIndex,
                                  StartingIndex);
   }
   case ISD::BSWAP:
     return calculateByteProvider(Op->getOperand(0), ByteWidth - Index - 1,
                                  Depth + 1, VectorIndex, StartingIndex);
   case ISD::EXTRACT_VECTOR_ELT: {
if (NarrowBitWidth % 8 != 0)
       return std::nullopt;
     uint64_t NarrowByteWidth = NarrowBitWidth / 8;
 
     // If the width of the load does not reach byte we are trying to provide for
     // and it is not a ZEXTLOAD, then the load does not provide for the byte in
     // question
     if (Index >= NarrowByteWidth)
       return L->getExtensionType() == ISD::ZEXTLOAD
-                 ? std::optional<ByteProvider>(ByteProvider::getConstantZero())
+                 ? std::optional<ByteProvider<ByteSrc>>(
+                       ByteProvider<ByteSrc>::getConstantZero())
                  : std::nullopt;
 
     unsigned BPVectorIndex = VectorIndex.value_or(0U);
-    return ByteProvider::getMemory(L, Index, BPVectorIndex);
+    return ByteProvider<ByteSrc>::getSrc(L, Index, BPVectorIndex);
   }
   }
 
   return std::nullopt;
 }
 
 static unsigned littleEndianByteAt(unsigned BW, unsigned i) {
   return i;
SDValue DAGCombiner::MatchLoadCombine(SDNode *N) {
 
   // Handles simple types only
   EVT VT = N->getValueType(0);
   if (VT != MVT::i16 && VT != MVT::i32 && VT != MVT::i64)
     return SDValue();
   unsigned ByteWidth = VT.getSizeInBits() / 8;
 
   bool IsBigEndianTarget = DAG.getDataLayout().isBigEndian();
-  auto MemoryByteOffset = [&] (ByteProvider P) {
-    assert(P.isMemory() && "Must be a memory byte provider");
-    unsigned LoadBitWidth = P.Load->getMemoryVT().getScalarSizeInBits();
+  auto MemoryByteOffset = [&](ByteProvider<ByteSrc> P) {
+    assert(P.hasSrc() && "Must be a memory byte provider");
+    assert(isa<LoadSDNode>(P.Src.value()));
+    LoadSDNode *Load = cast<LoadSDNode>(P.Src.value());
+
+    unsigned LoadBitWidth = Load->getMemoryVT().getScalarSizeInBits();
 
     assert(LoadBitWidth % 8 == 0 &&
            "can only analyze providers for individual bytes not bit");
     unsigned LoadByteWidth = LoadBitWidth / 8;
-    return IsBigEndianTarget
-            ? bigEndianByteAt(LoadByteWidth, P.ByteOffset)
-            : littleEndianByteAt(LoadByteWidth, P.ByteOffset);
+    return IsBigEndianTarget ? bigEndianByteAt(LoadByteWidth, P.DestOffset)
+                             : littleEndianByteAt(LoadByteWidth, P.DestOffset);
   };
 
   std::optional<BaseIndexOffset> Base;
   SDValue Chain;
 
   SmallPtrSet<LoadSDNode *, 8> Loads;
-  std::optional<ByteProvider> FirstByteProvider;
+  std::optional<ByteProvider<ByteSrc>> FirstByteProvider;
   int64_t FirstOffset = INT64_MAX;
 
   // Check if all the bytes of the OR we are looking at are loaded from the same
   // base address. Collect bytes offsets from Base address in ByteOffsets.
   SmallVector<int64_t, 8> ByteOffsets(ByteWidth);
   unsigned ZeroExtendedBytes = 0;
   for (int i = ByteWidth - 1; i >= 0; --i) {
     auto P =
         calculateByteProvider(SDValue(N, 0), i, 0, /*VectorIndex*/ std::nullopt,
                               /*StartingIndex*/ i);
     if (!P)
       return SDValue();
 
     if (P->isConstantZero()) {
       // It's OK for the N most significant bytes to be 0, we can just
       // zero-extend the load.
       if (++ZeroExtendedBytes != (ByteWidth - static_cast<unsigned>(i)))
         return SDValue();
       continue;
     }
-    assert(P->isMemory() && "provenance should either be memory or zero");
-
-    LoadSDNode *L = P->Load;
+    assert(P->hasSrc() && "provenance should either be memory or zero");
+    assert(isa<LoadSDNode>(P->Src.value()));
+    LoadSDNode *L = cast<LoadSDNode>(P->Src.value());
 
     // All loads must share the same chain
     SDValue LChain = L->getChain();
     if (!Chain)
       Chain = LChain;
     else if (Chain != LChain)
       return SDValue();
 
     // Loads must share the same base address
     BaseIndexOffset Ptr = BaseIndexOffset::match(L, DAG);
     int64_t ByteOffsetFromBase = 0;
 
     // For vector loads, the expected load combine pattern will have an
     // ExtractElement for each index in the vector. While each of these
     // ExtractElements will be accessing the same base address as determined
     // by the load instruction, the actual bytes they interact with will differ
     // due to different ExtractElement indices. To accurately determine the
     // byte position of an ExtractElement, we offset the base load ptr with
     // the index multiplied by the byte size of each element in the vector.
     if (L->getMemoryVT().isVector()) {
       unsigned LoadWidthInBit = L->getMemoryVT().getScalarSizeInBits();
       if (LoadWidthInBit % 8 != 0)
         return SDValue();
-      unsigned ByteOffsetFromVector = P->VectorOffset * LoadWidthInBit / 8;
+      unsigned ByteOffsetFromVector = P->SrcOffset * LoadWidthInBit / 8;
       Ptr.addToOffset(ByteOffsetFromVector);
     }
 
     if (!Base)
       Base = Ptr;
 
     else if (!Base->equalBaseIndex(Ptr, DAG, ByteOffsetFromBase))
       return SDValue();
if (!IsBigEndian)
     return SDValue();
 
   assert(FirstByteProvider && "must be set");
 
   // Ensure that the first byte is loaded from zero offset of the first load.
   // So the combined value can be loaded from the first load address.
   if (MemoryByteOffset(*FirstByteProvider) != 0)
     return SDValue();
-  LoadSDNode *FirstLoad = FirstByteProvider->Load;
+  assert(isa<LoadSDNode>(FirstByteProvider->Src.value()));
+  LoadSDNode *FirstLoad = cast<LoadSDNode>(FirstByteProvider->Src.value());
 
   // The node we are looking at matches with the pattern, check if we can
   // replace it with a single (possibly zero-extended) load and bswap + shift if
   // needed.
 
   // If the load needs byte swap check if the target supports it
   bool NeedsBswap = IsBigEndianTarget != *IsBigEndian;