[DAGCombine] Refactor DAGCombiner::ReduceLoadWidth. NFCI

[bjope]

Summary

Update code comments in DAGCombiner::ReduceLoadWidth and refactor
the handling of SRL a bit. The refactoring is done with the intent
of adding support for folding away SRA by using SEXTLOAD in a
follow-up patch.

[bjope]

This is an attempt to refactor the code a bit, making the diff in the D116930 child revision smaller.

There is still some code duplication since SRL is handled in two places. I kind of focused on making the introduction of SRA support easier, while still refactoring the second part of SRL handling just to describe that part a bit more. Maybe it too aggressive refactoring?

[spatel]

There are a complicated set of conditions to handle the various patterns/inputs. I don't know if I have accounted for all of the combinations.
I wonder if we'd be better off breaking it up, but if you feel confident that it's correct, let's keep it. :)

See inline for some minor changes.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12098

This sounds like it was originally written with a little-endian-only implementation.
How about generalizing to:

/// If the result of a load is shifted/masked/truncated to an effectively 
/// narrower type, try to transform the load to a narrower type and/or
/// use an extending load.

And fix the capitalization? "DAGCombiner::reduceLoadWidth()"

12120

is masked -> are masked

12152

that it -> that is

12181

needs to be -> need to be

12214

This assumes that ExtVTBits is a power-of-2, but is that enforced/asserted?

12271–12272

This seems backwards.
It's the little-endian target that needs to adjust the pointer. We're chopping off the LSB, so this is always converting ShAmt back to zero for big-endian?
fe17ce0fa6626f79be66

[bjope]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12214

I've not really understood why these checks exist. I mean, if there is no SRL at all we won't even take this path. So the code below (I figure mainly isLegalNarrowLdSt) need to ensure the legality anyway for the more general situation. So maybe this is some kind of early out (possibly saving a tiny amount of compile time). Or it is protecting the AND masking below somehow (but I can't really see that the AND masking depend on these properties).

Nevertheless, just like you have spotted, these checks aren't even making sense when ExtVTBits isn't a power of two.

As it happens we do get here for multiple lit tests with ExtEVTBits not being a power-of-2.

If I simply remove the checks, then I get diffs in several lit tests. I did examined one such test, and it turned out that we ended up with some slightly different order of transforms (resulting in (and (load i32), 7) instead of (and (sexload i8 to i32), 7), not really sure whichever would be better in that particular case). If the sextload is preferred, then I guess there should be another DAGCombine added that is doing such a transform(?).

If I instead bail out here if ExtVTBits isn't a power-of-2, then I get diffs in 3 lit tests. Those diffs looked like regressions as the instruction count increased in all three cases.

Skipping the tests seems like the better solution of the two above, but I'd rather fix that in a separate patch. And there might actually be some alternatives to explore. The AND mask hack below might detect that ExtVT can be reduced further into something that is a power-of-2, so bailing out on ExtVTBits not being a power-of-2 before the AND mask check was perhaps too restricting.

[spatel]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12214

Then this is even more confusing than I thought!
It's fine if you want to leave any more changes to other patches. You've probably stepped through this more than anyone else by now. :)

[spatel]

Adding Sam as a potential reviewer - code history shows that the last significant changes were:
D39595
D40034
D50432

[spatel]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12271–12272

To be clear, I think the code is correct. I just meant that the comment seems inverted for endian.

[bjope]

Updates based on review feedback.

[bjope]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12271–12272

I relaxed the description a bit. We could end up adjusting the pointer both for big/little endian here. Such as only loading a single byte from the middle of an i64.

[bjope]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12214

I made a follow-up patch related to this here D117406.

[spatel]

LGTM

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

 //===- DAGCombiner.cpp - Implement a DAG node combiner --------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
case ISD::SUB: {
     }
     break;
   }
   }
 
   return SDValue();
 }
 
-/// If the result of a wider load is shifted to right of N  bits and then
-/// truncated to a narrower type and where N is a multiple of number of bits of
-/// the narrower type, transform it to a narrower load from address + N / num of
+/// If the result of a wider load is shifted to right of C bits and then
+/// truncated to a narrower type and where C is a multiple of number of bits of
+/// the narrower type, transform it to a narrower load from address + C / num of
 /// bits of new type. Also narrow the load if the result is masked with an AND
 /// to effectively produce a smaller type. If the result is to be extended, also
-/// fold the extension to form a extending load.
+/// fold the extension to form an extending load.
 SDValue DAGCombiner::ReduceLoadWidth(SDNode *N) {
   unsigned Opc = N->getOpcode();
 
   ISD::LoadExtType ExtType = ISD::NON_EXTLOAD;
   SDValue N0 = N->getOperand(0);
   EVT VT = N->getValueType(0);
   EVT ExtVT = VT;
 
   // This transformation isn't valid for vector loads.
   if (VT.isVector())
     return SDValue();
 
+  // The ShAmt variable is used to indicate that we've consumed a right
+  // shift. I.e. we want to narrow the width of the load by skipping to load the
+  // ShAmt least significant bits.
   unsigned ShAmt = 0;
+  // A special case is when the least significant bits from the load is masked
+  // away, but using an AND rather than a right shift. HasShiftedOffset is used
+  // to indicate that the narrowed load should be left-shifted ShAmt bits to get
+  // the result.
   bool HasShiftedOffset = false;
   // Special case: SIGN_EXTEND_INREG is basically truncating to ExtVT then
   // extended to VT.
   if (Opc == ISD::SIGN_EXTEND_INREG) {
     ExtType = ISD::SEXTLOAD;
     ExtVT = cast<VTSDNode>(N->getOperand(1))->getVT();
   } else if (Opc == ISD::SRL) {
     // Another special-case: SRL is basically zero-extending a narrower value,
-    // or it maybe shifting a higher subword, half or byte into the lowest
+    // or it may be shifting a higher subword, half or byte into the lowest
     // bits.
-    ExtType = ISD::ZEXTLOAD;
-    N0 = SDValue(N, 0);
 
-    auto *LN0 = dyn_cast<LoadSDNode>(N0.getOperand(0));
-    auto *N01 = dyn_cast<ConstantSDNode>(N0.getOperand(1));
-    if (!N01 || !LN0)
+    // Only handle shift with constant shift amount, and the shiftee must be a
+    // load.
+    auto *LN = dyn_cast<LoadSDNode>(N0);
+    auto *N1C = dyn_cast<ConstantSDNode>(N->getOperand(1));
+    if (!N1C || !LN)
+      return SDValue();
+    // If the shift amount is larger than the memory type then we're not
+    // accessing any of the loaded bytes.
+    ShAmt = N1C->getZExtValue();
+    uint64_t MemoryWidth = LN->getMemoryVT().getScalarSizeInBits();
+    if (MemoryWidth <= ShAmt)
+      return SDValue();
+    // Attempt to fold away the SRL by using ZEXTLOAD.
+    ExtType = ISD::ZEXTLOAD;
+    ExtVT = EVT::getIntegerVT(*DAG.getContext(), MemoryWidth - ShAmt);
+    // If original load is a SEXTLOAD then we can't simply replace it by a
+    // ZEXTLOAD (we could potentially replace it by a more narrow SEXTLOAD
+    // followed by a ZEXT, but that it not handled at the moment).
+    if (LN->getExtensionType() == ISD::SEXTLOAD)
       return SDValue();
-
-    uint64_t ShiftAmt = N01->getZExtValue();
-    uint64_t MemoryWidth = LN0->getMemoryVT().getScalarSizeInBits();
-    if (LN0->getExtensionType() != ISD::SEXTLOAD && MemoryWidth > ShiftAmt)
-      ExtVT = EVT::getIntegerVT(*DAG.getContext(), MemoryWidth - ShiftAmt);
-    else
-      ExtVT = EVT::getIntegerVT(*DAG.getContext(),
-                                VT.getScalarSizeInBits() - ShiftAmt);
   } else if (Opc == ISD::AND) {
     // An AND with a constant mask is the same as a truncate + zero-extend.
     auto AndC = dyn_cast<ConstantSDNode>(N->getOperand(1));
     if (!AndC)
       return SDValue();
 
     const APInt &Mask = AndC->getAPIntValue();
     unsigned ActiveBits = 0;
     if (Mask.isMask()) {
       ActiveBits = Mask.countTrailingOnes();
     } else if (Mask.isShiftedMask()) {
       ShAmt = Mask.countTrailingZeros();
       APInt ShiftedMask = Mask.lshr(ShAmt);
       ActiveBits = ShiftedMask.countTrailingOnes();
       HasShiftedOffset = true;
     } else
       return SDValue();
 
     ExtType = ISD::ZEXTLOAD;
     ExtVT = EVT::getIntegerVT(*DAG.getContext(), ActiveBits);
   }
 
-  if (N0.getOpcode() == ISD::SRL && N0.hasOneUse()) {
-    SDValue SRL = N0;
-    if (auto *ConstShift = dyn_cast<ConstantSDNode>(SRL.getOperand(1))) {
-      ShAmt = ConstShift->getZExtValue();
-      unsigned EVTBits = ExtVT.getScalarSizeInBits();
-      // Is the shift amount a multiple of size of VT?
-      if ((ShAmt & (EVTBits-1)) == 0) {
-        N0 = N0.getOperand(0);
-        // Is the load width a multiple of size of VT?
-        if ((N0.getScalarValueSizeInBits() & (EVTBits - 1)) != 0)
-          return SDValue();
-      }
+  // In case Opc==SRL we've already prepared ExtVT/ExtType/ShAmt based on doing
+  // a right shift. Here we redo some of those checks, to possibly adjust the
+  // ExtVT even further based on "a masking AND". We could also end up here for
+  // other reasons (e.g. based on Opc==TRUNCATE) and that is why some checks
+  // needs to be done here as well.
+  if (Opc == ISD::SRL || N0.getOpcode() == ISD::SRL) {
+    SDValue SRL = Opc == ISD::SRL ? SDValue(N, 0) : N0;
+    // Bail out when the SRL has more than one use. This is done for historical
+    // (undocumented) reasons. Maybe intent was to guard the AND-masking below
+    // check below? And maybe it could be non-profitable to do the transform in
+    // case the SRL has multiple uses and we get here with Opc!=ISD::SRL?
+    // FIXME: Can't we just skip this check for the Opc==ISD::SRL case.
+    if (!SRL.hasOneUse())
 
-      // At this point, we must have a load or else we can't do the transform.
-      auto *LN0 = dyn_cast<LoadSDNode>(N0);
-      if (!LN0) return SDValue();
+    // Only handle shift with constant shift amount, and the shiftee must be a
+    // load.
+    auto *LN = dyn_cast<LoadSDNode>(SRL.getOperand(0));
+    auto *SRL1C = dyn_cast<ConstantSDNode>(SRL.getOperand(1));
+    if (!SRL1C || !LN)
+      return SDValue();
+
+    // If the shift amount is larger than the input type then we're not
+    // accessing any of the loaded bytes.  If the load was a zextload/extload
+    // then the result of the shift+trunc is zero/undef (handled elsewhere).
+    ShAmt = SRL1C->getZExtValue();
+    if (ShAmt >= LN->getMemoryVT().getSizeInBits())
+      return SDValue();
 
-      // Because a SRL must be assumed to *need* to zero-extend the high bits
-      // (as opposed to anyext the high bits), we can't combine the zextload
-      // lowering of SRL and an sextload.
-      if (LN0->getExtensionType() == ISD::SEXTLOAD)
-        return SDValue();
+    if (LN->getExtensionType() == ISD::SEXTLOAD)
 
-      // If the shift amount is larger than the input type then we're not
-      // accessing any of the loaded bytes.  If the load was a zextload/extload
-      // then the result of the shift+trunc is zero/undef (handled elsewhere).
-      if (ShAmt >= LN0->getMemoryVT().getSizeInBits())
-        return SDValue();
+    unsigned ExtVTBits = ExtVT.getScalarSizeInBits();
+    // Is the shift amount a multiple of size of ExtVT?
+    if ((ShAmt & (ExtVTBits-1)) != 0)
+      return SDValue();
+    // Is the load width a multiple of size of ExtVT?
+    if ((SRL.getScalarValueSizeInBits() & (ExtVTBits - 1)) != 0)
 
-      // If the SRL is only used by a masking AND, we may be able to adjust
-      // the ExtVT to make the AND redundant.
-      SDNode *Mask = *(SRL->use_begin());
-      if (Mask->getOpcode() == ISD::AND &&
-          isa<ConstantSDNode>(Mask->getOperand(1))) {
-        const APInt& ShiftMask = Mask->getConstantOperandAPInt(1);
-        if (ShiftMask.isMask()) {
-          EVT MaskedVT = EVT::getIntegerVT(*DAG.getContext(),
-                                           ShiftMask.countTrailingOnes());
-          // If the mask is smaller, recompute the type.
-          if ((ExtVT.getScalarSizeInBits() > MaskedVT.getScalarSizeInBits()) &&
-              TLI.isLoadExtLegal(ExtType, N0.getValueType(), MaskedVT))
-            ExtVT = MaskedVT;
-        }
-      }
-    }
+    if (SRL.hasOneUse() && Mask->getOpcode() == ISD::AND &&
+        if ((ExtVTBits > MaskedVT.getScalarSizeInBits()) &&
+            TLI.isLoadExtLegal(ExtType, SRL.getValueType(), MaskedVT))
+
+    N0 = SRL.getOperand(0);
   }
 
-  // If the load is shifted left (and the result isn't shifted back right),
-  // we can fold the truncate through the shift.
+  // If the load is shifted left (and the result isn't shifted back right), we
+  // can fold a truncate through the shift. The typical scenario is that N
+  // points at a TRUNCATE here so the attempted fold is:
+  //   (truncate (shl (load x), c))) -> (shl (narrow load x), c)
+  // ShLeftAmt will indicate how much a narrowed load should be shifted left.
   unsigned ShLeftAmt = 0;
   if (ShAmt == 0 && N0.getOpcode() == ISD::SHL && N0.hasOneUse() &&
       ExtVT == VT && TLI.isNarrowingProfitable(N0.getValueType(), VT)) {
     if (ConstantSDNode *N01 = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
       ShLeftAmt = N01->getZExtValue();
       N0 = N0.getOperand(0);
     }
   }
SDValue DAGCombiner::ReduceLoadWidth(SDNode *N) {
 
   auto AdjustBigEndianShift = [&](unsigned ShAmt) {
     unsigned LVTStoreBits =
         LN0->getMemoryVT().getStoreSizeInBits().getFixedSize();
     unsigned EVTStoreBits = ExtVT.getStoreSizeInBits().getFixedSize();
     return LVTStoreBits - EVTStoreBits - ShAmt;
   };
 
   // For big endian targets, we need to adjust the offset to the pointer to
   // load the correct bytes.
   if (DAG.getDataLayout().isBigEndian())
     ShAmt = AdjustBigEndianShift(ShAmt);
 
   uint64_t PtrOff = ShAmt / 8;
   Align NewAlign = commonAlignment(LN0->getAlign(), PtrOff);
   SDLoc DL(LN0);
   // The original load itself didn't wrap, so an offset within it doesn't.
   SDNodeFlags Flags;