[DAGCombiner] Match load by bytes idiom and fold it into a single load

[apilipenko]

Summary

I don't know who can be a good reviewer in this area, so I some added people who have touched something in DAGCombiner recently. If you know somebody who is a better reviewer for this change please let me know.

Match a pattern where a wide type scalar value is loaded by several narrow loads and combined by shifts and ors. Fold it into a single load or a load and a bswap if the targets supports it.

Assuming little endian target:

i8 *a = ...
i32 val = a[0] | (a[1] << 8) | (a[2] << 16) | (a[3] << 24)
=>
i32 val = *((i32)a)

i8 *a = ...
i32 val = (a[0] << 24) | (a[1] << 16) | (a[2] << 8) | a[3]
=>
i32 val = BSWAP(*((i32)a))

This optimization was discussed on llvm-dev some time ago in "Load combine pass" thread. We came to the conclusion that we want to do this transformation late in the pipeline because in presence of atomic loads load widening is irreversible transformation and it might hinder other optimizations.

Eventually we'd like to support folding patterns like this where the offset has a variable and a constant part:

i32 val = a[i] | (a[i + 1] << 8) | (a[i + 2] << 16) | (a[i + 3] << 24)

Matching the pattern above is easier at SelectionDAG level since address reassociation has already happened and the fact that the loads are adjacent is clear. Understanding that these loads are adjacent at IR level would have involved looking through geps/zexts/adds while looking at the addresses.

The general scheme is to match OR expressions by recursively calculating the origin of individual bits which constitute the resulting OR value. If all the OR bits come from memory verify that they are adjacent and match with little or big endian encoding of a wider value. If so and the load of the wider type (and bswap if needed) is allowed by the target generate a load and a bswap if needed.

[apilipenko]

Upload diff with full context

[apilipenko]

I found that this rule doesn't interact with the worklist mechanism in the right way. When a node is changed all its direct users are added to the work list so they can be visited and updated after the definition they are using is updated. The rule I'm adding matches complex patterns with OR node roots. When a part of the pattern is updated (e.g. one of the loads) I need to revisit the OR node but it's not necessarily a direct user of the changed node. For example, I'd like the address of this load to be reassociated so it's easier to analyze:

            t25: i32 = add t4, Constant:i32<2>
          t26: i64 = sign_extend t25
        t27: i64 = add t2, t26
      t28: i8,ch = load<LD1[%tmp9]> t0, t27, undef:i64
    t29: i32 = zero_extend t28
  t32: i32 = shl t29, Constant:i8<8>
t33: i32 = or t23, t32

But I have no way to trigger OR pattern matching after it happened because OR is not a direct user of the address.

What is the best way to work around this limitation?

[RKSimon]

Before deep diving - I don't want to start making feature creep demands here but I wonder if this should be trying to handle more general cases than just BSWAP - ROTL/ROTR for instance.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4344

I don't see any reason why these types are not inside DAGCombiner::MatchLoadCombine

4385

Introducing this type seems to be almost useless - why not just use SmallVector/ArrayRef types directly?

4391

Why not move this into MatchLoadCombine as a lambda?

test/CodeGen/X86/load-combine.ll

3

Please test with triples not archs and regenerate the test file using utils/update_llc_test_checks.py

444

Please add i64 test cases - to see what happens on 32-bit targets especially.

[hfinkel]

In D26149#583791, @apilipenko wrote:

I found that this rule doesn't interact with the worklist mechanism in the right way. When a node is changed all its direct users are added to the work list so they can be visited and updated after the definition they are using is updated. The rule I'm adding matches complex patterns with OR node roots. When a part of the pattern is updated (e.g. one of the loads) I need to revisit the OR node but it's not necessarily a direct user of the changed node. For example, I'd like the address of this load to be reassociated so it's easier to analyze:

            t25: i32 = add t4, Constant:i32<2>
          t26: i64 = sign_extend t25
        t27: i64 = add t2, t26
      t28: i8,ch = load<LD1[%tmp9]> t0, t27, undef:i64
    t29: i32 = zero_extend t28
  t32: i32 = shl t29, Constant:i8<8>
t33: i32 = or t23, t32

But I have no way to trigger OR pattern matching after it happened because OR is not a direct user of the address.

What is the best way to work around this limitation?

Are you looking for AddToWorklist or AddUsersToWorklist?

[apilipenko]

Address review comments.

[apilipenko]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4344

I guess it's a matter of style. We can move BitProvider type and collectBitProviders helper into MatchLoadCombine but I doubt that it will improve readability.

I put them into anonymous namespace so as not to pollute namespace, but if you think that they should live in MatchLoadCombine I don't mind.

4391

Same as above.

[apilipenko]

As for other patterns, in the code which motivated this change we see reads of different endiannes. I don't know how common will be other patterns, but in general it should not be difficult to extend the logic.

[apilipenko]

Use anonymous namespace instead of static function.

[apilipenko]

In D26149#590144, @hfinkel wrote:

In D26149#583791, @apilipenko wrote:

I found that this rule doesn't interact with the worklist mechanism in the right way. When a node is changed all its direct users are added to the work list so they can be visited and updated after the definition they are using is updated. The rule I'm adding matches complex patterns with OR node roots. When a part of the pattern is updated (e.g. one of the loads) I need to revisit the OR node but it's not necessarily a direct user of the changed node. For example, I'd like the address of this load to be reassociated so it's easier to analyze:

            t25: i32 = add t4, Constant:i32<2>
          t26: i64 = sign_extend t25
        t27: i64 = add t2, t26
      t28: i8,ch = load<LD1[%tmp9]> t0, t27, undef:i64
    t29: i32 = zero_extend t28
  t32: i32 = shl t29, Constant:i8<8>
t33: i32 = or t23, t32

But I have no way to trigger OR pattern matching after it happened because OR is not a direct user of the address.

What is the best way to work around this limitation?

Are you looking for AddToWorklist or AddUsersToWorklist?

I don't see how they can help me. What I need is to trigger combine for

t33: i32 = or t23, t32

When any of the node in this use-chain is combined, e.g. when

t26: i64 = sign_extend t25

is combined.

[hfinkel]

In D26149#591610, @apilipenko wrote:

In D26149#590144, @hfinkel wrote:

In D26149#583791, @apilipenko wrote:

I found that this rule doesn't interact with the worklist mechanism in the right way. When a node is changed all its direct users are added to the work list so they can be visited and updated after the definition they are using is updated. The rule I'm adding matches complex patterns with OR node roots. When a part of the pattern is updated (e.g. one of the loads) I need to revisit the OR node but it's not necessarily a direct user of the changed node. For example, I'd like the address of this load to be reassociated so it's easier to analyze:

            t25: i32 = add t4, Constant:i32<2>
          t26: i64 = sign_extend t25
        t27: i64 = add t2, t26
      t28: i8,ch = load<LD1[%tmp9]> t0, t27, undef:i64
    t29: i32 = zero_extend t28
  t32: i32 = shl t29, Constant:i8<8>
t33: i32 = or t23, t32

But I have no way to trigger OR pattern matching after it happened because OR is not a direct user of the address.

What is the best way to work around this limitation?

Are you looking for AddToWorklist or AddUsersToWorklist?

I don't see how they can help me. What I need is to trigger combine for

t33: i32 = or t23, t32

When any of the node in this use-chain is combined, e.g. when

t26: i64 = sign_extend t25

is combined.

Ah, indeed. You need, in essence, to trigger another whole iteration of the combiner. You can obviously search down the chain and add things to the worklist, but you obviously want to avoid a lot of rarely-profitable work.

Can you make your code match the pattern before the sext combine?

[apilipenko]

@hfinkel, this problem is more hypothetical than practical. For the cases we are interested in BaseIndexOffset logic is smart enough to look through non-combined addresses. Although triggering load combine might enable handling of more complex patterns.

As a possible fix we can add some logic in visitLoad which checks if the load can be a part of the load combine pattern. It should be fairly easy since all the nodes in the pattern must have only one use and this use must be on of few known nodes (or, shl, zext). If the load can be a part of the pattern visitLoad should add the potential root of the pattern ("or" node) to the work list. But this is definitely a separate improvement for this optimization.

[RKSimon]

test/CodeGen/X86/load-combine.ll

214

What is preventing the 32-bit target doing anything here?

300

What is preventing the 32-bit target doing anything here?

[apilipenko]

test/CodeGen/X86/load-combine.ll

214

This patch can only handle situations when all the bits of the value are available and can be loaded in a single load. In this pattern individual bytes are extended to i64 and all the computation are done with i64 values. So we have no chance to combine i32 halves of the pattern. I'm going to send a follow up patch to add support for partially available loads once this patch is in.

300

The same as above.

[hfinkel]

In D26149#594859, @apilipenko wrote:

@hfinkel, this problem is more hypothetical than practical. For the cases we are interested in BaseIndexOffset logic is smart enough to look through non-combined addresses. Although triggering load combine might enable handling of more complex patterns.

As a possible fix we can add some logic in visitLoad which checks if the load can be a part of the load combine pattern. It should be fairly easy since all the nodes in the pattern must have only one use and this use must be on of few known nodes (or, shl, zext). If the load can be a part of the pattern visitLoad should add the potential root of the pattern ("or" node) to the work list. But this is definitely a separate improvement for this optimization.

Okay; makes sense to me.

[filcab]

This is low-level enough that it's probably worth it to just do it byte by byte, instead of bit for bit. At least for now, no?

Your pattern matching on the non-x86 cases needs to be improved. At the very least, we need to match:
load
bswap if needed
"ret-ish" instruction

Or:
not bswap/rev
load
shift
or

Ideally, you'd use the same kinds of checks as the x86 versions.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4434

Why copy the whole vector only to replace parts of it?

4448

Maybe use std::fill_n, std::copy?

4492

Can you make the string more explicit? Something like "Can only match load combining against OR nodes" or something?

4591

Should we check this before we do all the work with the bitoffsets?
Might be hard as we probably need address space + alignment info. But we can at least bubble this up to above the little/big endian decision (unsure if that's very profitable, though).

[apilipenko]

@filcab, the idea was mentioned above that we might want to match patterns other that bswap, for example rotate. Given this I'd prefer to keep bit-by-bit matching.

As for improving the matching do you mean supporting the listed instructions as a part of the pattern? I do plan to add bswap and different extension nodes support in a follow up patch. I'd like to keep the initial patch simple though.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4591

I don't think that it will make a difference since LE/BE matching is not that expensive. On the other hand this placement seems a bit more logical: we ask about a possibility of load from a particular location when we know that the code in question is actually doing this load.

[apilipenko]

Address some of the review comments.

[filcab]

In D26149#607787, @apilipenko wrote:

@filcab, the idea was mentioned above that we might want to match patterns other that bswap, for example rotate. Given this I'd prefer to keep bit-by-bit matching.

Fair enough. Do you have plans on doing that "soon", or is it just a "in the future, probably we'll have X"?

As for improving the matching do you mean supporting the listed instructions as a part of the pattern? I do plan to add bswap and different extension nodes support in a follow up patch. I'd like to keep the initial patch simple though.

I'd prefer to be sure we're testing the thing we think we're testing. At the very least, we'd want to make sure there are no or instructions in most of those cases. I'd even go with "they should just load, maybe bswap, and exit the function", so most of those arm tests would have two or three check lines (at least). I know that currently we're emitting ldrb to load each byte. But I prefer tighter checks since we want them to fail as soon as possible.

btw, do you have numbers on how many times we end up triggering this on a specific code-base?

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4432

Having both Res and Result seems confusing: "Which is the actual result?"
Can you change this name to something like LHSBits/LHSProviders or something?

4444

Res vs Result again. If the Res means something other than "result", please write the full word, it might become sufficiently less ambiguous.
Otherwise, something like Original, Narrow, Value (not ideal), or something else should be better than Res for code reading.

[apilipenko]

Address review comments: rename locals in collectBitProviders, tighten CHECK patterns in non-x86 tests.

[apilipenko]

We see load by bytes (with optional bswap) patterns in Java code originating from ByteBuffers from the standard library. This is the main motivator for the change. I don't have any numbers for C/C++ code but I expect it's not uncommon.

As of matching patterns like rotate, we don't see it the the code we are interested about, so it's more like "this is where this code can evolve in the future".

[filcab]

Thanks, the non-x86 tests look good.

In D26149#609005, @apilipenko wrote:

We see load by bytes (with optional bswap) patterns in Java code originating from ByteBuffers from the standard library. This is the main motivator for the change. I don't have any numbers for C/C++ code but I expect it's not uncommon.

I'm sure we see it. I'm just curious about how frequently this shows up :-)

As of matching patterns like rotate, we don't see it the the code we are interested about, so it's more like "this is where this code can evolve in the future".

If there's no actual planned usage of the "bit by bit" feature, I'd much rather have an implementation that tracks full bytes. Even if we wanted to track bit by bit, having byte-tracking will get us most of the way there, since you can only fetch memory byte by byte. If an edge case arised that forced us to track bits, then I'd be ok with it. But as it is, I don't see why we should pay that price.

[apilipenko]

Analyze the pattern byte by byte.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4617

This all (4346:4617) looks like it needs to be run through clang-format

[apilipenko]

Clang-formatted.

[filcab]

Some minor nits: No need to size the vectors at 32, 4 will do it.
And use auto if you're declaring a var and initializing it to the return of a ..._cast operator, since you already mentioned the type in that line.

Please run the ASan test before pushing the commit.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4389

We can make this 4 now, no?
Making it 8 would save us a realloc() when compiling for 64-bit archs on a bunch of places, but I'm unsure it's worth it. Something to be tried later, though.

4397

You already had BitWidth. Using it makes this line more readable.

4401

Aren't you binding to the object returned in collectByteProviders? Can you run a test case that triggers this optimization under asan with ASAN_OPTIONS=detect_stack_use_after_return=true?

4423

4

4430

auto ShiftOp = ...

4444

4

4457

4

4466

auto L = ...

4474

4

[apilipenko]

Address review comments.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4401

collectByteProviders return the result by value, so it's not a problem. The reference here is misleading and should be just auto. Fixed here and there.

[filcab]

LGTM

[Joshua-401]

Did you consider doing the load combine at IR level? I'm now trying to combine loads at IR level during the InstCombine process, so I'm wondering why you didn't do that.

Matching the pattern above is easier at SelectionDAG level since address reassociation has already happened and the fact that the loads are adjacent is clear. Understanding that these loads are adjacent at IR level would have involved looking through geps/zexts/adds while looking at the addresses.

[spatel]

In D26149#3130357, @Joshua-401 wrote:

Did you consider doing the load combine at IR level? I'm now trying to combine loads at IR level during the InstCombine process, so I'm wondering why you didn't do that.

There was an IR load combine pass (see D3580 - although never enabled by default AFAIK), but it was removed because it could interfere with other passes like GVN.
https://lists.llvm.org/pipermail/llvm-dev/2016-September/105291.html
https://lists.llvm.org/pipermail/llvm-dev/2019-September/135052.html

But requests for this kind of transform pop up every few months or so, so it is probably worth experimenting to see if there is some limited/altered form of that pass that can get us optimizations without reducing effectiveness of other passes.

[reames]

In D26149#3131756, @spatel wrote:

In D26149#3130357, @Joshua-401 wrote:

Did you consider doing the load combine at IR level? I'm now trying to combine loads at IR level during the InstCombine process, so I'm wondering why you didn't do that.

There was an IR load combine pass (see D3580 - although never enabled by default AFAIK), but it was removed because it could interfere with other passes like GVN.
https://lists.llvm.org/pipermail/llvm-dev/2016-September/105291.html
https://lists.llvm.org/pipermail/llvm-dev/2019-September/135052.html

FYI, load merging at IR has some really hard cases.

One that I remember is that atomic loads are really problematic. four one byte atomic loads are different than one 4 byte atomic atomic load. Even if we have the four byte load on the target. Once we've committed to the wider load type, we have no way to go back. This greatly limits our optimization and lowering, and can lead to very poor outcomes. We'd vaguely discussed the possibility of an IR extension for "element wise atomic vectors" to resolve this particular case, but it never progressed.

I believe there were a couple of other really hard examples too. I just don't remember those. :)

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

                               unsigned PosOpcode, unsigned NegOpcode,
                               const SDLoc &DL);
     SDNode *MatchRotate(SDValue LHS, SDValue RHS, const SDLoc &DL);
+    SDValue MatchLoadCombine(SDNode *N);
     SDValue ReduceLoadWidth(SDNode *N);
     SDValue ReduceLoadOpStoreWidth(SDNode *N);
     SDValue splitMergedValStore(StoreSDNode *ST);

   if (SDNode *Rot = MatchRotate(N0, N1, SDLoc(N)))
     return SDValue(Rot, 0);
 
+  if (SDValue Load = MatchLoadCombine(N))
+    return Load;
+
   // Simplify the operands using demanded-bits information.
   if (!VT.isVector() &&
       SimplifyDemandedBits(SDValue(N, 0)))

 };
 } // namespace
 
+/// Represents the origin of an individual bit in load combine pattern. The
+/// value of the bit is either unknown, zero or comes from memory.
+struct BitProvider {
+  enum ProviderTy {
+    Unknown, ZeroConstant, Memory
+  };
+
+  ProviderTy Kind;
+  // Load and BitOffset are set for Memory providers only.
+  // Load represents the node which loads the bit from memory.
+  // BitOffset is the offset of the bit in the value produced by the load.
+  LoadSDNode *Load;
+  unsigned BitOffset;
+
+  BitProvider() : Kind(ProviderTy::Unknown), Load(nullptr), BitOffset(0) {}
+
+  static BitProvider getUnknown() {
+    return BitProvider(ProviderTy::Unknown, nullptr, 0);
+  }
+  static BitProvider getMemory(LoadSDNode *Load, unsigned BitOffset) {
+    return BitProvider(ProviderTy::Memory, Load, BitOffset);
+  }
+  static BitProvider getZero() {
+    return BitProvider(ProviderTy::ZeroConstant, nullptr, 0);
+  }
+
+  bool operator==(const BitProvider &Other) const {
+    return Other.Kind == Kind &&
+           Other.Load == Load &&
+           Other.BitOffset == BitOffset;
+  }
+
+private:
+  BitProvider(ProviderTy Kind, LoadSDNode *Load, unsigned BitOffset) :
+                Kind(Kind), Load(Load), BitOffset(BitOffset) {}
+};
+
+struct ValueBitProviders {
+  ValueBitProviders(unsigned BW) {
+    Bits.resize(BW);
+  }
+
+  SmallVector<BitProvider, 32> Bits;
+};
+
+/// Recursively traverses the expression collecting the origin of individual
+/// bits of the given value. For all the values except the root of the
+/// expression verifies that it doesn't have uses outside of the expression.
+const Optional<ValueBitProviders>
+collectBitProviders(SDValue Op, bool CheckNumberOfUses = false) {
+  Optional<ValueBitProviders> Result;
+
+  if (CheckNumberOfUses && !Op.hasOneUse())
+    return Result;
+
+  unsigned BitWidth = Op.getScalarValueSizeInBits();
+  switch (Op.getOpcode()) {
+  case ISD::OR: {
+    auto &A = collectBitProviders(Op->getOperand(0),
+                                  /*CheckNumberOfUses=*/true);
+    auto &B = collectBitProviders(Op->getOperand(1),
+                                  /*CheckNumberOfUses=*/true);
+    if (!A || !B)
+      return Result;
+
+    auto OR = [] (BitProvider A, BitProvider B) {
+      if (A == B)
+        return A;
+      if (A.Kind == BitProvider::Unknown ||
+          B.Kind == BitProvider::Unknown)
+        return BitProvider::getUnknown();
+      if (A.Kind == BitProvider::Memory &&
+          B.Kind == BitProvider::Memory)
+        return BitProvider::getUnknown();
+
+      if (A.Kind == BitProvider::Memory)
+        return A;
+      else
+        return B;
+    };
+
+    Result = ValueBitProviders(BitWidth);
+    for (unsigned i = 0; i < A->Bits.size(); i++)
+      Result->Bits[i] = OR(A->Bits[i], B->Bits[i]);
+
+    return Result;
+  }
+  case ISD::SHL: {
+    ConstantSDNode *ShiftOp = dyn_cast<ConstantSDNode>(Op->getOperand(1));
+    if (!ShiftOp)
+      return Result;
+
+    uint64_t BitShift = ShiftOp->getZExtValue();
+
+    auto &Res = collectBitProviders(Op->getOperand(0),
+                                    /*CheckNumberOfUses=*/true);
+    if (!Res)
+      return Result;
+    Result = Res;
+
+    auto &P = Result->Bits;
+    P.erase(std::prev(P.end(), BitShift), P.end());
+    P.insert(P.begin(), BitShift, BitProvider::getZero());
+
+    return Result;
+  }
+  case ISD::ZERO_EXTEND: {
+    auto &Res = collectBitProviders(Op->getOperand(0),
+                                    /*CheckNumberOfUses=*/true);
+    if (!Res)
+      return Result;
+
+    Result = ValueBitProviders(BitWidth);
+    unsigned NarrowBitWidth = Res->Bits.size();
+    for (unsigned i = 0; i < NarrowBitWidth; i++)
+      Result->Bits[i] = Res->Bits[i];
+    for (unsigned i = NarrowBitWidth; i < BitWidth; i++)
+      Result->Bits[i] = BitProvider::getZero();
+
+    return Result;
+  }
+  case ISD::LOAD: {
+    LoadSDNode *L = cast<LoadSDNode>(Op.getNode());
+    if (L->isVolatile() || L->isIndexed() ||
+        L->getExtensionType() != ISD::NON_EXTLOAD)
+      return None;
+
+    EVT VT = L->getMemoryVT();
+    // Handles simple types only
+    if (VT != MVT::i8 && VT != MVT::i16 &&
+        VT != MVT::i32 && VT != MVT::i64)
+      return None;
+
+    assert(BitWidth == VT.getSizeInBits() && "sanity");
+    Result = ValueBitProviders(BitWidth);
+    for (unsigned i = 0; i < BitWidth; i++)
+      Result->Bits[i] = BitProvider::getMemory(L, i);
+
+    return Result;
+  }
+  }
+
+  return None;
+}
+
+/// Match a pattern where a wide type scalar value is loaded by several narrow
+/// loads and combined by shifts and ors. Fold it into a single load or a load
+/// and a BSWAP if the targets supports it.
+///
+/// Assuming little endian target:
+///  i8 *a = ...
+///  i32 val = a[0] | (a[1] << 8) | (a[2] << 16) | (a[3] << 24)
+/// =>
+///  i32 val = *((i32)a)
+///
+///  i8 *a = ...
+///  i32 val = (a[0] << 24) | (a[1] << 16) | (a[2] << 8) | a[3]
+/// =>
+///  i32 val = BSWAP(*((i32)a))
+SDValue DAGCombiner::MatchLoadCombine(SDNode *N) {
+  assert(N->getOpcode() == ISD::OR && "must be OR");
+
+  // Handles simple types only
+  EVT VT = N->getValueType(0);
+  if (VT != MVT::i16 && VT != MVT::i32 && VT != MVT::i64)
+    return SDValue();
+
+  // There is nothing to do here if the target can't load a value of this type
+  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
+  if (!TLI.isOperationLegal(ISD::LOAD, VT))
+    return SDValue();
+
+  // Calculate bit providers for the OR we are looking at
+  auto Res = collectBitProviders(SDValue(N, 0), false);
+  if (!Res)
+    return SDValue();
+  auto &Bits = Res->Bits;
+  unsigned BitWidth = Bits.size();
+  assert(VT.getSizeInBits() == BitWidth && "sanity");
+
+  Optional<BaseIndexOffset> Base;
+  SDValue Chain;
+
+  SmallSet<LoadSDNode*, 8> Loads;
+  LoadSDNode *FirstLoad;
+
+  // Check if the bits of the OR we are looking at match with either big or
+  // little endian value load
+  bool BigEndian = true, LittleEndian = true;
+  for (unsigned i = 0; i < BitWidth; i++) {
+    // All the bits must be loaded from memory
+    if (Bits[i].Kind != BitProvider::Memory)
+      return SDValue();
+
+    LoadSDNode *L = Bits[i].Load;
+    assert(L->hasNUsesOfValue(1, 0) && !L->isVolatile() && !L->isIndexed() &&
+           (L->getExtensionType() == ISD::NON_EXTLOAD) &&
+           "Must be enforced by collectBitProviders");
+    assert(L->getOffset().isUndef() &&
+           "Unindexed load must have undef offset");
+
+    // All loads must share the same chain
+    SDValue LChain = L->getChain();
+    if (!Chain)
+      Chain = LChain;
+    if (Chain != LChain)
+      return SDValue();
+
+    // Loads must share the same base address
+    BaseIndexOffset Ptr = BaseIndexOffset::match(L->getBasePtr(), DAG);
+    if (!Base)
+      Base = Ptr;
+    if (!Base->equalBaseIndex(Ptr))
+      return SDValue();
+
+    auto LittleEndianBitAt = [] (unsigned BW, unsigned i) { return i; };
+    auto BigEndianBitAt = [] (unsigned BW, unsigned i) {
+      return BW - (i / 8) * 8 - 8 + i % 8;
+    };
+
+    // Calculate the offset of the current bit from the base address
+    unsigned LoadBitWidth = L->getMemoryVT().getSizeInBits();
+    int64_t MemoryBitOffset = DAG.getDataLayout().isBigEndian()
+                          ? BigEndianBitAt(LoadBitWidth, Bits[i].BitOffset)
+                          : LittleEndianBitAt(LoadBitWidth, Bits[i].BitOffset);
+    int64_t BitOffsetFromBase = Ptr.Offset * 8 + MemoryBitOffset;
+
+    // Check that the current bit matches with either big or little endian
+    // encoding
+    LittleEndian &= BitOffsetFromBase == LittleEndianBitAt(BitWidth, i);
+    BigEndian    &= BitOffsetFromBase == BigEndianBitAt(BitWidth, i);
+    if (!BigEndian && !LittleEndian)
+      return SDValue();
+
+    // Remember the first bit load
+    if (BitOffsetFromBase == 0)
+      FirstLoad = L;
+
+    Loads.insert(L);
+  }
+
+  assert((BigEndian != LittleEndian) && "should be either or");
+  assert(Base && "must be set");
+
+  // The node we are looking at matches with the pattern, check if we can
+  // replace it with a single load and bswap if needed.
+
+  // If the load needs byte swap check if the target supports it
+  bool NeedsBswap = DAG.getDataLayout().isBigEndian() != BigEndian;
+  if (NeedsBswap && !TLI.isOperationLegal(ISD::BSWAP, VT))
+    return SDValue();
+
+  // Check that a load of the wide type is both allowed and fast on the target
+  bool Fast = false;
+  bool Allowed = TLI.allowsMemoryAccess(*DAG.getContext(), DAG.getDataLayout(),
+                                        VT, FirstLoad->getAddressSpace(),
+                                        FirstLoad->getAlignment(), &Fast);
+  if (!Allowed || !Fast)
+    return SDValue();
+
+  SDValue NewLoad = DAG.getLoad(VT, SDLoc(N), Chain, FirstLoad->getBasePtr(),
+                                FirstLoad->getPointerInfo(),
+                                FirstLoad->getAlignment());
+
+  // Transfer chain users from old loads to the new load.
+  for (LoadSDNode *L : Loads)
+    DAG.ReplaceAllUsesOfValueWith(SDValue(L, 1),
+                                  SDValue(NewLoad.getNode(), 1));
+
+  if (NeedsBswap)
+    return DAG.getNode(ISD::BSWAP, SDLoc(N), VT, NewLoad);
+  else
+    return NewLoad;
+}
+
 SDValue DAGCombiner::visitXOR(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);

test/CodeGen/ARM/load-combine-big-endian.ll

+; RUN: llc < %s -mtriple=armeb-eabi | FileCheck %s
+
+; i8* p; // p is 4 byte aligned
+; ((i32) p[0] << 24) | ((i32) p[1] << 16) | ((i32) p[2] << 8) | (i32) p[3]
+define i32 @load_i32_by_i8_big_endian(i32*) {
+; CHECK-LABEL: load_i32_by_i8_big_endian:
+; CHECK: ldr r0, [r0]
+  %2 = bitcast i32* %0 to i8*
+  %3 = load i8, i8* %2, align 4
+  %4 = zext i8 %3 to i32
+  %5 = shl nuw nsw i32 %4, 24
+  %6 = getelementptr inbounds i8, i8* %2, i32 1
+  %7 = load i8, i8* %6, align 1
+  %8 = zext i8 %7 to i32
+  %9 = shl nuw nsw i32 %8, 16
+  %10 = or i32 %9, %5
+  %11 = getelementptr inbounds i8, i8* %2, i32 2
+  %12 = load i8, i8* %11, align 1
+  %13 = zext i8 %12 to i32
+  %14 = shl nuw nsw i32 %13, 8
+  %15 = or i32 %10, %14
+  %16 = getelementptr inbounds i8, i8* %2, i32 3
+  %17 = load i8, i8* %16, align 1
+  %18 = zext i8 %17 to i32
+  %19 = or i32 %15, %18
+  ret i32 %19
+}
+
+; i8* p; // p is 4 byte aligned
+; ((i32) (((i16) p[0] << 8) | (i16) p[1]) << 16) | (i32) (((i16) p[3] << 8) | (i16) p[4])
+define i32 @load_i32_by_i16_by_i8_big_endian(i32*) {
+; CHECK-LABEL: load_i32_by_i16_by_i8_big_endian:
+; CHECK: ldr r0, [r0]
+  %2 = bitcast i32* %0 to i8*
+  %3 = load i8, i8* %2, align 4
+  %4 = zext i8 %3 to i16
+  %5 = getelementptr inbounds i8, i8* %2, i32 1
+  %6 = load i8, i8* %5, align 1
+  %7 = zext i8 %6 to i16
+  %8 = shl nuw nsw i16 %4, 8
+  %9 = or i16 %8, %7
+  %10 = getelementptr inbounds i8, i8* %2, i32 2
+  %11 = load i8, i8* %10, align 1
+  %12 = zext i8 %11 to i16
+  %13 = getelementptr inbounds i8, i8* %2, i32 3
+  %14 = load i8, i8* %13, align 1
+  %15 = zext i8 %14 to i16
+  %16 = shl nuw nsw i16 %12, 8
+  %17 = or i16 %16, %15
+  %18 = zext i16 %9 to i32
+  %19 = zext i16 %17 to i32
+  %20 = shl nuw nsw i32 %18, 16
+  %21 = or i32 %20, %19
+  ret i32 %21
+}
+
+; i16* p; // p is 4 byte aligned
+; ((i32) p[0] << 16) | (i32) p[1]
+define i32 @load_i32_by_i16(i32*) {
+; CHECK-LABEL: load_i32_by_i16:
+; CHECK: ldr r0, [r0]
+  %2 = bitcast i32* %0 to i16*
+  %3 = load i16, i16* %2, align 4
+  %4 = zext i16 %3 to i32
+  %5 = getelementptr inbounds i16, i16* %2, i32 1
+  %6 = load i16, i16* %5, align 1
+  %7 = zext i16 %6 to i32
+  %8 = shl nuw nsw i32 %4, 16
+  %9 = or i32 %8, %7
+  ret i32 %9
+}
+
+; i16* p_16;
+; i8* p_8 = (i8*) p_16;
+; (i32) (p_16[0] << 16) | ((i32) p[2] << 8) | (i32) p[3]
+define i32 @load_i32_by_i16_i8(i32*) {
+; CHECK-LABEL: load_i32_by_i16_i8:
+; CHECK: ldr r0, [r0]
+  %2 = bitcast i32* %0 to i16*
+  %3 = bitcast i32* %0 to i8*
+  %4 = load i16, i16* %2, align 4
+  %5 = zext i16 %4 to i32
+  %6 = shl nuw nsw i32 %5, 16
+  %7 = getelementptr inbounds i8, i8* %3, i32 2
+  %8 = load i8, i8* %7, align 1
+  %9 = zext i8 %8 to i32
+  %10 = shl nuw nsw i32 %9, 8
+  %11 = getelementptr inbounds i8, i8* %3, i32 3
+  %12 = load i8, i8* %11, align 1
+  %13 = zext i8 %12 to i32
+  %14 = or i32 %10, %13
+  %15 = or i32 %14, %6
+  ret i32 %15
+}
 No newline at end of file

test/CodeGen/ARM/load-combine.ll

+; RUN: llc < %s -march=arm | FileCheck %s
+
+; i8* p; // p is 1 byte aligned
+; (i32) p[0] | ((i32) p[1] << 8) | ((i32) p[2] << 16) | ((i32) p[3] << 24)
+define i32 @load_i32_by_i8_unaligned(i32*) {
+; CHECK-LABEL: load_i32_by_i8_unaligned:
+; CHECK: orr
+  %2 = bitcast i32* %0 to i8*
+  %3 = getelementptr inbounds i8, i8* %2, i32 0
+  %4 = load i8, i8* %2, align 1
+  %5 = zext i8 %4 to i32
+  %6 = getelementptr inbounds i8, i8* %2, i32 1
+  %7 = load i8, i8* %6, align 1
+  %8 = zext i8 %7 to i32
+  %9 = shl nuw nsw i32 %8, 8
+  %10 = or i32 %9, %5
+  %11 = getelementptr inbounds i8, i8* %2, i32 2
+  %12 = load i8, i8* %11, align 1
+  %13 = zext i8 %12 to i32
+  %14 = shl nuw nsw i32 %13, 16
+  %15 = or i32 %10, %14
+  %16 = getelementptr inbounds i8, i8* %2, i32 3
+  %17 = load i8, i8* %16, align 1
+  %18 = zext i8 %17 to i32
+  %19 = shl nuw nsw i32 %18, 24
+  %20 = or i32 %15, %19
+  ret i32 %20
+}
+
+; i8* p; // p is 4 byte aligned
+; (i32) p[0] | ((i32) p[1] << 8) | ((i32) p[2] << 16) | ((i32) p[3] << 24)
+define i32 @load_i32_by_i8_aligned(i32*) {
+; CHECK-LABEL: load_i32_by_i8_aligned:
+; CHECK: ldr  r0, [r0]
+  %2 = bitcast i32* %0 to i8*
+  %3 = getelementptr inbounds i8, i8* %2, i32 0
+  %4 = load i8, i8* %2, align 4
+  %5 = zext i8 %4 to i32
+  %6 = getelementptr inbounds i8, i8* %2, i32 1
+  %7 = load i8, i8* %6, align 1
+  %8 = zext i8 %7 to i32
+  %9 = shl nuw nsw i32 %8, 8
+  %10 = or i32 %9, %5
+  %11 = getelementptr inbounds i8, i8* %2, i32 2
+  %12 = load i8, i8* %11, align 1
+  %13 = zext i8 %12 to i32
+  %14 = shl nuw nsw i32 %13, 16
+  %15 = or i32 %10, %14
+  %16 = getelementptr inbounds i8, i8* %2, i32 3
+  %17 = load i8, i8* %16, align 1
+  %18 = zext i8 %17 to i32
+  %19 = shl nuw nsw i32 %18, 24
+  %20 = or i32 %15, %19
+  ret i32 %20
+}
+
+; BSWAP is not supported by the target
+; i8* p; // p is 4 byte aligned
+; ((i32) p[0] << 24) | ((i32) p[1] << 16) | ((i32) p[2] << 8) | (i32) p[3]
+define i32 @load_i32_by_i8_nobswap(i32*) {
+; CHECK-LABEL: load_i32_by_i8_nobswap:
+; CHECK: orr
+  %2 = bitcast i32* %0 to i8*
+  %3 = load i8, i8* %2, align 4
+  %4 = zext i8 %3 to i32
+  %5 = shl nuw nsw i32 %4, 24
+  %6 = getelementptr inbounds i8, i8* %2, i32 1
+  %7 = load i8, i8* %6, align 1
+  %8 = zext i8 %7 to i32
+  %9 = shl nuw nsw i32 %8, 16
+  %10 = or i32 %9, %5
+  %11 = getelementptr inbounds i8, i8* %2, i32 2
+  %12 = load i8, i8* %11, align 1
+  %13 = zext i8 %12 to i32
+  %14 = shl nuw nsw i32 %13, 8
+  %15 = or i32 %10, %14
+  %16 = getelementptr inbounds i8, i8* %2, i32 3
+  %17 = load i8, i8* %16, align 1
+  %18 = zext i8 %17 to i32
+  %19 = or i32 %15, %18
+  ret i32 %19
+}
 No newline at end of file

test/CodeGen/X86/load-combine.ll

+; RUN: llc < %s -march=x86 | FileCheck %s
+; RUN: llc < %s -march=x86-64 | FileCheck %s --check-prefix=CHECK64
+
+; i8* p;
+; (i32) p[0] | ((i32) p[1] << 8) | ((i32) p[2] << 16) | ((i32) p[3] << 24)
+define i32 @load_i32_by_i8(i32*) {
+; CHECK-LABEL: load_i32_by_i8:
+; CHECK: movl  (%eax), %eax
+; CHECK-NOT: bswapl  %eax
+
+; CHECK64-LABEL: load_i32_by_i8:
+; CHECK64: movl  (%rdi), %eax
+; CHECK64-NOT: bswapl  %eax
+  %2 = bitcast i32* %0 to i8*
+  %3 = load i8, i8* %2, align 1
+  %4 = zext i8 %3 to i32
+  %5 = getelementptr inbounds i8, i8* %2, i32 1
+  %6 = load i8, i8* %5, align 1
+  %7 = zext i8 %6 to i32
+  %8 = shl nuw nsw i32 %7, 8
+  %9 = or i32 %8, %4
+  %10 = getelementptr inbounds i8, i8* %2, i32 2
+  %11 = load i8, i8* %10, align 1
+  %12 = zext i8 %11 to i32
+  %13 = shl nuw nsw i32 %12, 16
+  %14 = or i32 %9, %13
+  %15 = getelementptr inbounds i8, i8* %2, i32 3
+  %16 = load i8, i8* %15, align 1
+  %17 = zext i8 %16 to i32
+  %18 = shl nuw nsw i32 %17, 24
+  %19 = or i32 %14, %18
+  ret i32 %19
+}
+
+; i8* p;
+; ((i32) p[0] << 24) | ((i32) p[1] << 16) | ((i32) p[2] << 8) | (i32) p[3]
+define i32 @load_i32_by_i8_bswap(i32*) {
+; CHECK-LABEL: load_i32_by_i8_bswap:
+; CHECK: movl  (%eax), %eax
+; CHECK: bswapl  %eax
+
+; CHECK64-LABEL: load_i32_by_i8_bswap:
+; CHECK64: movl  (%rdi), %eax
+; CHECK64: bswapl  %eax
+  %2 = bitcast i32* %0 to i8*
+  %3 = load i8, i8* %2, align 1
+  %4 = zext i8 %3 to i32
+  %5 = shl nuw nsw i32 %4, 24
+  %6 = getelementptr inbounds i8, i8* %2, i32 1
+  %7 = load i8, i8* %6, align 1
+  %8 = zext i8 %7 to i32
+  %9 = shl nuw nsw i32 %8, 16
+  %10 = or i32 %9, %5
+  %11 = getelementptr inbounds i8, i8* %2, i32 2
+  %12 = load i8, i8* %11, align 1
+  %13 = zext i8 %12 to i32
+  %14 = shl nuw nsw i32 %13, 8
+  %15 = or i32 %10, %14
+  %16 = getelementptr inbounds i8, i8* %2, i32 3
+  %17 = load i8, i8* %16, align 1
+  %18 = zext i8 %17 to i32
+  %19 = or i32 %15, %18
+  ret i32 %19
+}
+
+; i16* p;
+; (i32) p[0] | ((i32) p[1] << 16)
+define i32 @load_i32_by_i16(i32*) {
+; CHECK-LABEL: load_i32_by_i16:
+; CHECK: movl  (%eax), %eax
+; CHECK-NOT: bswapl  %eax
+
+; CHECK64-LABEL: load_i32_by_i16:
+; CHECK64: movl  (%rdi), %eax
+; CHECK64-NOT: bswapl  %eax
+  %2 = bitcast i32* %0 to i16*
+  %3 = load i16, i16* %2, align 1
+  %4 = zext i16 %3 to i32
+  %5 = getelementptr inbounds i16, i16* %2, i32 1
+  %6 = load i16, i16* %5, align 1
+  %7 = zext i16 %6 to i32
+  %8 = shl nuw nsw i32 %7, 16
+  %9 = or i32 %8, %4
+  ret i32 %9
+}
+
+; i16* p_16;
+; i8* p_8 = (i8*) p_16;
+; (i32) p_16[0] | ((i32) p[2] << 16) | ((i32) p[3] << 24)
+define i32 @load_i32_by_i16_i8(i32*) {
+; CHECK-LABEL: load_i32_by_i16_i8:
+; CHECK: movl  (%eax), %eax
+; CHECK-NOT: bswapl  %eax
+
+; CHECK64-LABEL: load_i32_by_i16_i8:
+; CHECK64: movl  (%rdi), %eax
+; CHECK64-NOT: bswapl  %eax
+  %2 = bitcast i32* %0 to i16*
+  %3 = bitcast i32* %0 to i8*
+  %4 = load i16, i16* %2, align 1
+  %5 = zext i16 %4 to i32
+  %6 = getelementptr inbounds i8, i8* %3, i32 2
+  %7 = load i8, i8* %6, align 1
+  %8 = zext i8 %7 to i32
+  %9 = shl nuw nsw i32 %8, 16
+  %10 = getelementptr inbounds i8, i8* %3, i32 3
+  %11 = load i8, i8* %10, align 1
+  %12 = zext i8 %11 to i32
+  %13 = shl nuw nsw i32 %12, 24
+  %14 = or i32 %9, %13
+  %15 = or i32 %14, %5
+  ret i32 %15
+}
+
+
+; i8* p;
+; (i32) ((i16) p[0] | ((i16) p[1] << 8)) | (((i32) ((i16) p[3] | ((i16) p[4] << 8)) << 16)
+define i32 @load_i32_by_i16_by_i8(i32*) {
+; CHECK-LABEL: load_i32_by_i16_by_i8:
+; CHECK: movl  (%eax), %eax
+; CHECK-NOT: bswapl  %eax
+
+; CHECK64-LABEL: load_i32_by_i16_by_i8:
+; CHECK64: movl  (%rdi), %eax
+; CHECK64-NOT: bswapl  %eax
+  %2 = bitcast i32* %0 to i8*
+  %3 = load i8, i8* %2, align 1
+  %4 = zext i8 %3 to i16
+  %5 = getelementptr inbounds i8, i8* %2, i32 1
+  %6 = load i8, i8* %5, align 1
+  %7 = zext i8 %6 to i16
+  %8 = shl nuw nsw i16 %7, 8
+  %9 = or i16 %8, %4
+  %10 = getelementptr inbounds i8, i8* %2, i32 2
+  %11 = load i8, i8* %10, align 1
+  %12 = zext i8 %11 to i16
+  %13 = getelementptr inbounds i8, i8* %2, i32 3
+  %14 = load i8, i8* %13, align 1
+  %15 = zext i8 %14 to i16
+  %16 = shl nuw nsw i16 %15, 8
+  %17 = or i16 %16, %12
+  %18 = zext i16 %9 to i32
+  %19 = zext i16 %17 to i32
+  %20 = shl nuw nsw i32 %19, 16
+  %21 = or i32 %20, %18
+  ret i32 %21
+}
+
+; i8* p;
+; ((i32) (((i16) p[0] << 8) | (i16) p[1]) << 16) | (i32) (((i16) p[3] << 8) | (i16) p[4])
+define i32 @load_i32_by_i16_by_i8_bswap(i32*) {
+; CHECK-LABEL: load_i32_by_i16_by_i8_bswap:
+; CHECK: movl  (%eax), %eax
+; CHECK: bswapl  %eax
+
+; CHECK64-LABEL: load_i32_by_i16_by_i8_bswap:
+; CHECK64: movl  (%rdi), %eax
+; CHECK64: bswapl  %eax
+  %2 = bitcast i32* %0 to i8*
+  %3 = load i8, i8* %2, align 1
+  %4 = zext i8 %3 to i16
+  %5 = getelementptr inbounds i8, i8* %2, i32 1
+  %6 = load i8, i8* %5, align 1
+  %7 = zext i8 %6 to i16
+  %8 = shl nuw nsw i16 %4, 8
+  %9 = or i16 %8, %7
+  %10 = getelementptr inbounds i8, i8* %2, i32 2
+  %11 = load i8, i8* %10, align 1
+  %12 = zext i8 %11 to i16
+  %13 = getelementptr inbounds i8, i8* %2, i32 3
+  %14 = load i8, i8* %13, align 1
+  %15 = zext i8 %14 to i16
+  %16 = shl nuw nsw i16 %12, 8
+  %17 = or i16 %16, %15
+  %18 = zext i16 %9 to i32
+  %19 = zext i16 %17 to i32
+  %20 = shl nuw nsw i32 %18, 16
+  %21 = or i32 %20, %19
+  ret i32 %21
+}
+
+; i8* p;
+; (i64) p[0] | ((i64) p[1] << 8) | ((i64) p[2] << 16) | ((i64) p[3] << 24) | ((i64) p[4] << 32) | ((i64) p[5] << 40) | ((i64) p[6] << 48) | ((i64) p[7] << 56)
+define i64 @load_i64_by_i8(i64*) {
+; CHECK-LABEL: load_i64_by_i8:
+; CHECK: orl
+
+; CHECK64-LABEL: load_i64_by_i8:
+; CHECK64: movq (%rdi), %rax
+; CHECK64-NOT: bswapq  %rax
+  %2 = bitcast i64* %0 to i8*
+  %3 = load i8, i8* %2, align 1
+  %4 = zext i8 %3 to i64
+  %5 = getelementptr inbounds i8, i8* %2, i64 1
+  %6 = load i8, i8* %5, align 1
+  %7 = zext i8 %6 to i64
+  %8 = shl nuw nsw i64 %7, 8
+  %9 = or i64 %8, %4
+  %10 = getelementptr inbounds i8, i8* %2, i64 2
+  %11 = load i8, i8* %10, align 1
+  %12 = zext i8 %11 to i64
+  %13 = shl nuw nsw i64 %12, 16
+  %14 = or i64 %9, %13
+  %15 = getelementptr inbounds i8, i8* %2, i64 3
+  %16 = load i8, i8* %15, align 1
+  %17 = zext i8 %16 to i64
+  %18 = shl nuw nsw i64 %17, 24
+  %19 = or i64 %14, %18
+  %20 = getelementptr inbounds i8, i8* %2, i64 4
+  %21 = load i8, i8* %20, align 1
+  %22 = zext i8 %21 to i64
+  %23 = shl nuw nsw i64 %22, 32
+  %24 = or i64 %19, %23
+  %25 = getelementptr inbounds i8, i8* %2, i64 5
+  %26 = load i8, i8* %25, align 1
+  %27 = zext i8 %26 to i64
+  %28 = shl nuw nsw i64 %27, 40
+  %29 = or i64 %24, %28
+  %30 = getelementptr inbounds i8, i8* %2, i64 6
+  %31 = load i8, i8* %30, align 1
+  %32 = zext i8 %31 to i64
+  %33 = shl nuw nsw i64 %32, 48
+  %34 = or i64 %29, %33
+  %35 = getelementptr inbounds i8, i8* %2, i64 7
+  %36 = load i8, i8* %35, align 1
+  %37 = zext i8 %36 to i64
+  %38 = shl nuw i64 %37, 56
+  %39 = or i64 %34, %38
+  ret i64 %39
+}
+
+; i8* p;
+; ((i64) p[0] << 56) | ((i64) p[1] << 48) | ((i64) p[2] << 40) | ((i64) p[3] << 32) | ((i64) p[4] << 24) | ((i64) p[5] << 16) | ((i64) p[6] << 8) | (i64) p[7]
+define i64 @load_i64_by_i8_bswap(i64*) {
+; CHECK-LABEL: load_i64_by_i8_bswap:
+; CHECK: orl
+
+; CHECK64-LABEL: load_i64_by_i8_bswap:
+; CHECK64: movq (%rdi), %rax
+; CHECK64: bswapq  %rax
+  %2 = bitcast i64* %0 to i8*
+  %3 = load i8, i8* %2, align 1
+  %4 = zext i8 %3 to i64
+  %5 = shl nuw i64 %4, 56
+  %6 = getelementptr inbounds i8, i8* %2, i64 1
+  %7 = load i8, i8* %6, align 1
+  %8 = zext i8 %7 to i64
+  %9 = shl nuw nsw i64 %8, 48
+  %10 = or i64 %9, %5
+  %11 = getelementptr inbounds i8, i8* %2, i64 2
+  %12 = load i8, i8* %11, align 1
+  %13 = zext i8 %12 to i64
+  %14 = shl nuw nsw i64 %13, 40
+  %15 = or i64 %10, %14
+  %16 = getelementptr inbounds i8, i8* %2, i64 3
+  %17 = load i8, i8* %16, align 1
+  %18 = zext i8 %17 to i64
+  %19 = shl nuw nsw i64 %18, 32
+  %20 = or i64 %15, %19
+  %21 = getelementptr inbounds i8, i8* %2, i64 4
+  %22 = load i8, i8* %21, align 1
+  %23 = zext i8 %22 to i64
+  %24 = shl nuw nsw i64 %23, 24
+  %25 = or i64 %20, %24
+  %26 = getelementptr inbounds i8, i8* %2, i64 5
+  %27 = load i8, i8* %26, align 1
+  %28 = zext i8 %27 to i64
+  %29 = shl nuw nsw i64 %28, 16
+  %30 = or i64 %25, %29
+  %31 = getelementptr inbounds i8, i8* %2, i64 6
+  %32 = load i8, i8* %31, align 1
+  %33 = zext i8 %32 to i64
+  %34 = shl nuw nsw i64 %33, 8
+  %35 = or i64 %30, %34
+  %36 = getelementptr inbounds i8, i8* %2, i64 7
+  %37 = load i8, i8* %36, align 1
+  %38 = zext i8 %37 to i64
+  %39 = or i64 %35, %38
+  ret i64 %39
+}
+
+; Part of the load by bytes pattern is used outside of the pattern
+; i8* p;
+; i32 x = (i32) p[1]
+; res = ((i32) p[0] << 24) | (x << 16) | ((i32) p[2] << 8) | (i32) p[3]
+; x | res
+define i32 @load_i32_by_i8_bswap_uses(i32*) {
+; CHECK-LABEL: load_i32_by_i8_bswap_uses:
+; CHECK-NOT: movl  (%eax), %eax
+
+; CHECK64-LABEL: load_i32_by_i8_bswap_uses:
+; CHECK64-NOT: movl  (%rdi), %eax
+  %2 = bitcast i32* %0 to i8*
+  %3 = load i8, i8* %2, align 1
+  %4 = zext i8 %3 to i32
+  %5 = shl nuw nsw i32 %4, 24
+  %6 = getelementptr inbounds i8, i8* %2, i32 1
+  %7 = load i8, i8* %6, align 1
+  %8 = zext i8 %7 to i32
+  %9 = shl nuw nsw i32 %8, 16
+  %10 = or i32 %9, %5
+  %11 = getelementptr inbounds i8, i8* %2, i32 2
+  %12 = load i8, i8* %11, align 1
+  %13 = zext i8 %12 to i32
+  %14 = shl nuw nsw i32 %13, 8
+  %15 = or i32 %10, %14
+  %16 = getelementptr inbounds i8, i8* %2, i32 3
+  %17 = load i8, i8* %16, align 1
+  %18 = zext i8 %17 to i32
+  %19 = or i32 %15, %18
+  ; Use individual part of the pattern outside of the pattern
+  %20 = or i32 %8, %19
+  ret i32 %20
+}
+
+; One of the loads is volatile
+; i8* p;
+; p0 = volatile *p;
+; ((i32) p0 << 24) | ((i32) p[1] << 16) | ((i32) p[2] << 8) | (i32) p[3]
+define i32 @load_i32_by_i8_bswap_volatile(i32*) {
+; CHECK-LABEL: load_i32_by_i8_bswap_volatile:
+; CHECK-NOT: movl  (%eax), %eax
+
+; CHECK64-LABEL: load_i32_by_i8_bswap_volatile:
+; CHECK64-NOT: movl  (%rdi), %eax
+  %2 = bitcast i32* %0 to i8*
+  %3 = load volatile i8, i8* %2, align 1
+  %4 = zext i8 %3 to i32
+  %5 = shl nuw nsw i32 %4, 24
+  %6 = getelementptr inbounds i8, i8* %2, i32 1
+  %7 = load i8, i8* %6, align 1
+  %8 = zext i8 %7 to i32
+  %9 = shl nuw nsw i32 %8, 16
+  %10 = or i32 %9, %5
+  %11 = getelementptr inbounds i8, i8* %2, i32 2
+  %12 = load i8, i8* %11, align 1
+  %13 = zext i8 %12 to i32
+  %14 = shl nuw nsw i32 %13, 8
+  %15 = or i32 %10, %14
+  %16 = getelementptr inbounds i8, i8* %2, i32 3
+  %17 = load i8, i8* %16, align 1
+  %18 = zext i8 %17 to i32
+  %19 = or i32 %15, %18
+  ret i32 %19
+}
+
+; There is a store in between individual loads
+; i8* p, q;
+; res1 = ((i32) p[0] << 24) | ((i32) p[1] << 16)
+; *q = 0;
+; res2 = ((i32) p[2] << 8) | (i32) p[3]
+; res1 | res2
+define i32 @load_i32_by_i8_bswap_store_in_between(i32*, i32*) {
+; CHECK-LABEL: load_i32_by_i8_bswap_store_in_between:
+; CHECK-NOT: movl  (%eax), %eax
+
+; CHECK64-LABEL: load_i32_by_i8_bswap_store_in_between:
+; CHECK64-NOT: movl  (%rdi), %eax
+  %3 = bitcast i32* %0 to i8*
+  %4 = load i8, i8* %3, align 1
+  %5 = zext i8 %4 to i32
+  %6 = shl nuw nsw i32 %5, 24
+  %7 = getelementptr inbounds i8, i8* %3, i32 1
+  %8 = load i8, i8* %7, align 1
+  ; This store will prevent folding of the pattern
+  store i32 0, i32* %1
+  %9 = zext i8 %8 to i32
+  %10 = shl nuw nsw i32 %9, 16
+  %11 = or i32 %10, %6
+  %12 = getelementptr inbounds i8, i8* %3, i32 2
+  %13 = load i8, i8* %12, align 1
+  %14 = zext i8 %13 to i32
+  %15 = shl nuw nsw i32 %14, 8
+  %16 = or i32 %11, %15
+  %17 = getelementptr inbounds i8, i8* %3, i32 3
+  %18 = load i8, i8* %17, align 1
+  %19 = zext i8 %18 to i32
+  %20 = or i32 %16, %19
+  ret i32 %20
+}
+
+; One of the loads is from an unrelated location
+; i8* p, q;
+; ((i32) p[0] << 24) | ((i32) q[1] << 16) | ((i32) p[2] << 8) | (i32) p[3]
+define i32 @load_i32_by_i8_bswap_unrelated_load(i32*, i32*) {
+; CHECK-LABEL: load_i32_by_i8_bswap_unrelated_load:
+; CHECK-NOT: movl  (%eax), %eax
+
+; CHECK64-LABEL: load_i32_by_i8_bswap_unrelated_load:
+; CHECK64-NOT: movl  (%rdi), %eax
+  %3 = bitcast i32* %0 to i8*
+  %4 = bitcast i32* %1 to i8*
+  %5 = load i8, i8* %3, align 1
+  %6 = zext i8 %5 to i32
+  %7 = shl nuw nsw i32 %6, 24
+  ; Load from an unrelated address
+  %8 = getelementptr inbounds i8, i8* %4, i32 1
+  %9 = load i8, i8* %8, align 1
+  %10 = zext i8 %9 to i32
+  %11 = shl nuw nsw i32 %10, 16
+  %12 = or i32 %11, %7
+  %13 = getelementptr inbounds i8, i8* %3, i32 2
+  %14 = load i8, i8* %13, align 1
+  %15 = zext i8 %14 to i32
+  %16 = shl nuw nsw i32 %15, 8
+  %17 = or i32 %12, %16
+  %18 = getelementptr inbounds i8, i8* %3, i32 3
+  %19 = load i8, i8* %18, align 1
+  %20 = zext i8 %19 to i32
+  %21 = or i32 %17, %20
+  ret i32 %21
+}
+
+; Non-zero offsets are not supported for now
+; i8* p;
+; (i32) p[1] | ((i32) p[2] << 8) | ((i32) p[3] << 16) | ((i32) p[4] << 24)
+define i32 @load_i32_by_i8_unsupported_offset(i32*) {
+; CHECK-LABEL: load_i32_by_i8_unsupported_offset:
+; CHECK-NOT: movl  (%eax), %eax
+
+; CHECK64-LABEL: load_i32_by_i8_unsupported_offset:
+; CHECK64-NOT: movl  (%rdi), %eax
+  %2 = bitcast i32* %0 to i8*
+  %3 = getelementptr inbounds i8, i8* %2, i32 1
+  %4 = load i8, i8* %2, align 1
+  %5 = zext i8 %4 to i32
+  %6 = getelementptr inbounds i8, i8* %2, i32 2
+  %7 = load i8, i8* %6, align 1
+  %8 = zext i8 %7 to i32
+  %9 = shl nuw nsw i32 %8, 8
+  %10 = or i32 %9, %5
+  %11 = getelementptr inbounds i8, i8* %2, i32 3
+  %12 = load i8, i8* %11, align 1
+  %13 = zext i8 %12 to i32
+  %14 = shl nuw nsw i32 %13, 16
+  %15 = or i32 %10, %14
+  %16 = getelementptr inbounds i8, i8* %2, i32 4
+  %17 = load i8, i8* %16, align 1
+  %18 = zext i8 %17 to i32
+  %19 = shl nuw nsw i32 %18, 24
+  %20 = or i32 %15, %19
+  ret i32 %20
+}