[RFC][WebAssembly] Optimize GEPs

[samparker]

Summary

Workaround the shortcomings of LoopStrengthReduce and ScalarEvolutionExpander to allow inbounds getelemenptr instructions, in unrolled loops, to reach the backend. This enables greater usage of memory operations with immediate offsets.

The pass simply pattern matches geps, in the form: (getelementptr ptr %base (or i32 %reg_offset, i32 constant)) and then creates a new base from %base and %reg_offset, using pointer arithmetic. This is then shared amongst the geps, all of each can then use an immediate index too.

[lebedev.ri]

Do you have specific examples of those existing passes deficiencies?
It would be best to fix them, and benefit all, instead of workaround them for a single target.

[samparker]

Do you have specific examples of those existing passes deficiencies?

I'd firstly say that I think this is a very webassembly shaped problem, I don't think any other architectures will have similar addressing modes.

As to the specific problems, it's mainly due to SCEVExpander often not being able to regenerate no wrap flags or inbound geps. Judging by the number of TODOs in that area, and I think I've done some in the past, it seems very much non-trivial. The function that I was looking at for this was SCEVExpander::expandAddToGEP. If there is a clear plan on how this can be implemented, I would be very happy to hear it.

LSR is just the driver of the problem... but a very dense driver at that (which I struggle with!), but the main problem is that it isn't very 'predictable' when it comes to unrolled loops, due it's complexity limit, which results in LSR behaving differently for different sized loops.

[tlively]

llvm/lib/Target/WebAssembly/WebAssemblyOptimizeGEPs.cpp

139

Would this be hard to change? Wasm64 is generally supported elsewhere in LLVM these days.

167–168

Why use a hash value as the key? Wouldn't it be better to use the pair itself as the key?

llvm/test/CodeGen/WebAssembly/optimize-geps.ll

7

Would it be possible to have a smaller test case? It's hard to tell what to look at here.

[samparker]

llvm/lib/Target/WebAssembly/WebAssemblyOptimizeGEPs.cpp

139

Okay, will do.

167–168

Good point.

llvm/test/CodeGen/WebAssembly/optimize-geps.ll

7

Yeah, if I remove one array and move to i32 this should hopefully half the size.

[samparker]

• Changed 'key' type.
• Added wasm64 support.
• Reduced some tests.
• Added option to disable the pass.

[tlively]

llvm/lib/Target/WebAssembly/WebAssemblyOptimizeGEPs.cpp

12

16

110

Do we need BasePairs? It looks like we could remove it if we iterate through the Candidates keys instead.

llvm/test/CodeGen/WebAssembly/optimize-geps.ll

7

Thanks! Could you also add comments in the test input pointing out where interesting things happen?

[lebedev.ri]

llvm/lib/Target/WebAssembly/WebAssemblyOptimizeGEPs.cpp

19

How is this different from SeparateConstOffsetFromGEP pass?

[samparker]

llvm/lib/Target/WebAssembly/WebAssemblyOptimizeGEPs.cpp

19

I started by trying to use it and it didn't do anything. But, looking again, that appears to be a TTI issue. It still produces IR that we don't want, as the base address is generated by a GEP and not pointer arithmetic. I should be able to remedy this through another TTI hook though. I'll experiment.

[aheejin]

llvm/lib/Target/WebAssembly/WebAssemblyOptimizeGEPs.cpp

2

Can you add a motivating example of small code snippets that tries to solve that the status quo doesn't?

llvm/test/CodeGen/WebAssembly/optimize-geps.ll

7

Can we have some comments for most of the tests to help what to look at? Not sure which part of the code we need to look. Also, what is dim?

[dschuff]

llvm/lib/Target/WebAssembly/WebAssemblyTargetMachine.cpp

457

Does this pass fix up debug info when necessary?
If feasible, it should; but if not, maybe we should restrict it to CodeGenOpt::Default and higher.

[samparker]

llvm/lib/Target/WebAssembly/WebAssemblyOptimizeGEPs.cpp

110

IIUC, we then won't have a stable iteration order - I originally tried doing this but I got intermittent test failures.

llvm/lib/Target/WebAssembly/WebAssemblyTargetMachine.cpp

457

No, it doesn't. I'm going to update the patch to not add it into the backend pipeline yet.

[samparker]

Hopefully addressed all the comments...

I've removed the pass from the backend for now, and my expectation is that SeparateConstOffsetFromGEP and EarlyCSE will need to run before this as they get the code into an easily analyzable form. I need to run some benchmarks though to see if they have any negative affects.

[samparker]

I just realized that I'm creating the new base address incorrectly, I will fix it after the weekend.

[samparker]

Fixed base address calculation.

[samparker]

Handling global base addresses.

[samparker]

Taking D141926 as a base, this transform brings the total code size of my local benchmarks down from 7982KB to 7970KB.

llvm/lib/Target/WebAssembly/CMakeLists.txt

add_llvm_target(WebAssemblyCodeGen
   WebAssemblyInstrInfo.cpp
   WebAssemblyLowerBrUnless.cpp
   WebAssemblyLowerEmscriptenEHSjLj.cpp
   WebAssemblyLowerRefTypesIntPtrConv.cpp
   WebAssemblyMachineFunctionInfo.cpp
   WebAssemblyMCInstLower.cpp
   WebAssemblyMCLowerPrePass.cpp
   WebAssemblyNullifyDebugValueLists.cpp
+  WebAssemblyOptimizeGEPs.cpp
   WebAssemblyOptimizeLiveIntervals.cpp
   WebAssemblyOptimizeReturned.cpp
   WebAssemblyPeephole.cpp
   WebAssemblyRegisterInfo.cpp
   WebAssemblyRegColoring.cpp
   WebAssemblyRegNumbering.cpp
   WebAssemblyRegStackify.cpp
   WebAssemblyReplacePhysRegs.cpp

llvm/lib/Target/WebAssembly/WebAssembly.h

 #include "llvm/PassRegistry.h"
 #include "llvm/Support/CodeGen.h"
 
 namespace llvm {
 
 class WebAssemblyTargetMachine;
 class ModulePass;
 class FunctionPass;
+class Pass;
 
 // LLVM IR passes.
 ModulePass *createWebAssemblyLowerEmscriptenEHSjLj();
 ModulePass *createWebAssemblyAddMissingPrototypes();
 ModulePass *createWebAssemblyFixFunctionBitcasts();
 FunctionPass *createWebAssemblyOptimizeReturned();
 FunctionPass *createWebAssemblyLowerRefTypesIntPtrConv();
+Pass *createWebAssemblyOptimizeGEPs();
 
 // ISel and immediate followup passes.
 FunctionPass *createWebAssemblyISelDag(WebAssemblyTargetMachine &TM,
                                        CodeGenOpt::Level OptLevel);
 FunctionPass *createWebAssemblyArgumentMove();
 FunctionPass *createWebAssemblySetP2AlignOperands();
 
 // Late passes.

 void initializeWebAssemblyCFGStackifyPass(PassRegistry &);
 void initializeWebAssemblyExplicitLocalsPass(PassRegistry &);
 void initializeWebAssemblyLowerBrUnlessPass(PassRegistry &);
 void initializeWebAssemblyRegNumberingPass(PassRegistry &);
 void initializeWebAssemblyDebugFixupPass(PassRegistry &);
 void initializeWebAssemblyPeepholePass(PassRegistry &);
 void initializeWebAssemblyMCLowerPrePassPass(PassRegistry &);
 void initializeWebAssemblyLowerRefTypesIntPtrConvPass(PassRegistry &);
+void initializeWebAssemblyOptimizeGEPsPass(PassRegistry &);
 
 namespace WebAssembly {
 enum TargetIndex {
   // Followed by a local index (ULEB).
   TI_LOCAL,
   // Followed by an absolute global index (ULEB). DEPRECATED.
   TI_GLOBAL_FIXED,
   // Followed by the index from the bottom of the Wasm stack.

llvm/lib/Target/WebAssembly/WebAssemblyOptimizeGEPs.cpp

+//===--- WebAssemblyOptimizeGEPs.cpp - GetElementPtr index processing ---===//
+//
+// 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
+/// Optimize inbounds GetElemenPtrInst so that LoopStrengthReduce and
+/// ScalarEvolutionExpander don't make modifications to the IR which lose the
+/// inbounds information.
+///
+/// To use immediate address offsets, the add operations need to be marked as
+/// nuw due to WebAssembly's infinite precision address offset calculation. The
+/// add operations are lowered from GetElemenPtrInst and, if it's inbounds, the
+/// add will be nuw. Unfortunately, the inbounds information is easily lost when
+/// converting between IR -> SCEV -> IR during LSR. This pass finds inbounds
+/// GEPs, with a single immediate index and converts the base pointer to use
+/// pointer arithmetic. It's this arithmetic that prevents SCEVExpander from
+/// losing the nowrap / inbounds attributes.
+///
+/// SeparateConstOffsetFromGEP and EarlyCSE are used to prepare the code for
+/// this pass.
+///
+/// As an example, a common pattern in an unrolled loop would be an or of an
+/// indvar to generate an index for gep, eg:
+///
+/// %index = or i32 %i, 1
+/// %gep = getelementptr inbounds i32, ptr %base, i32 %index
+/// %data = load i32, ptr %gep, align 4
+///
+/// However, after LoopStrengthReduce the code is usually transformed into the
+/// form which is less friendly for WebAssembly as we cannot lower non-inbound
+/// geps to load/store with immediate offsets:
+///
+/// %uglygep = getelementptr i8, ptr %base, i32 %lsr.iv
+/// %uglygep2 = getelementptr i8, ptr %uglygep, i32 4
+/// %data = load i32, ptr %uglygep2, align 4
+///
+//===----------------------------------------------------------------------===//
+
+#include "WebAssembly.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopPass.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Value.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+
+#define DEBUG_TYPE "wasm-optimize-geps"
+#define PASS_DESC "Optimize inner-loop GEPs for Webassembly"
+
+using namespace llvm;
+
+static cl::opt<bool> DisableWebAssemblyOptimizeGEPs(
+    "disable-wasm-optimize-geps", cl::Hidden,
+    cl::desc("WebAssembly: Disable getelementptr optimizations."),
+    cl::init(false));
+
+namespace {
+
+class RebaseCandidate {
+public:
+  RebaseCandidate(GetElementPtrInst *GEP) : GEP(GEP) {
+    assert(GEP->getNumOperands() == 2 && "Expected two operand GEP");
+  }
+
+  void update(Value *NewBasePtr) {
+    assert(NewBasePtr->getType()->isPointerTy() && "Expected PointerTy");
+    GEP->setOperand(0, NewBasePtr);
+  }
+
+  GetElementPtrInst *getGEP() const { return GEP; }
+
+#ifndef NDEBUG
+  void dump() {
+    LLVM_DEBUG(dbgs() << "Candidate:\n"
+                      << "  GEP: " << *GEP << "\n"
+                      << "  Base: " << *GEP->getPointerOperand() << "\n");
+  }
+#endif
+
+private:
+  GetElementPtrInst *GEP;
+};
+
+class WebAssemblyOptimizeGEPs : public LoopPass {
+public:
+  static char ID;
+
+  WebAssemblyOptimizeGEPs() : LoopPass(ID) {}
+
+private:
+  StringRef getPassName() const override { return PASS_DESC; }
+
+  bool runOnLoop(Loop *L, LPPassManager &LPM) override;
+
+  bool run(Loop *L);
+  void addCandidate(GetElementPtrInst *GEP);
+  // Create a new base address using pointer casting and add nuw. This should
+  // prevent LSR from messing with our inbound geps.
+  Instruction *createNewBaseAddr(GetElementPtrInst *BaseGEP, Loop *L);
+
+  LLVMContext *Ctx = nullptr;
+  IntegerType *IntPtrTy = nullptr;
+  SmallVector<GetElementPtrInst *, 4> BasePtrs;
+  DenseMap<GetElementPtrInst *, SmallVector<RebaseCandidate, 4>> Candidates;
+};
+
+} // end anonymous namespace
+
+char WebAssemblyOptimizeGEPs::ID = 0;
+INITIALIZE_PASS_BEGIN(WebAssemblyOptimizeGEPs, DEBUG_TYPE, PASS_DESC, false,
+                      false)
+INITIALIZE_PASS_END(WebAssemblyOptimizeGEPs, DEBUG_TYPE, PASS_DESC, false,
+                    false)
+
+Pass *llvm::createWebAssemblyOptimizeGEPs() {
+  return new WebAssemblyOptimizeGEPs();
+}
+
+bool WebAssemblyOptimizeGEPs::runOnLoop(Loop *L, LPPassManager &) {
+  if (DisableWebAssemblyOptimizeGEPs)
+    return false;
+  if (skipLoop(L))
+    return false;
+  if (!L->getLoopPreheader())
+    return false;
+
+  // LSR only operates on the inner most loops, so do the same.
+  if (!L->isInnermost()) {
+    LLVM_DEBUG(dbgs() << "WasmOptGep: Not inner most loop.\n");
+    return false;
+  }
+
+  if (L->getNumBlocks() > 1) {
+    LLVM_DEBUG(dbgs() << "WasmOptGep: Only handling single-block loops.\n");
+    return false;
+  }
+
+  Function *F = L->getLoopPreheader()->getParent();
+  Ctx = &F->getContext();
+  // Set the type we'll use for pointer arithmetic.
+  IntPtrTy = F->getParent()->getDataLayout().getIntPtrType(*Ctx);
+  Candidates.clear();
+  BasePtrs.clear();
+  return run(L);
+}
+
+void WebAssemblyOptimizeGEPs::addCandidate(GetElementPtrInst *GEP) {
+  assert(isa<GetElementPtrInst>(GEP->getPointerOperand()) &&
+         "Expected GEP base pointer");
+  auto *BasePtr = cast<GetElementPtrInst>(GEP->getPointerOperand());
+  if (!Candidates.count(BasePtr))
+    BasePtrs.push_back(BasePtr);
+  Candidates[BasePtr].emplace_back(GEP);
+}
+
+Instruction *
+WebAssemblyOptimizeGEPs::createNewBaseAddr(GetElementPtrInst *BaseGEP,
+                                           Loop *L) {
+  Value *BasePtr = BaseGEP->getOperand(0);
+  Value *Offset = BaseGEP->getOperand(1);
+  Type *BaseType = BasePtr->getType();
+  IRBuilder<> Builder(*Ctx);
+
+  LLVM_DEBUG(dbgs() << "WasmOptGep: Creating new base addr.\n"
+                    << "  with base address: " << *BasePtr << "\n"
+                    << "  and offset: " << *Offset << "\n");
+
+  assert(BasePtr->getType()->isPointerTy() && "Expected PointerTy");
+  assert(Offset->getType() == IntPtrTy && "Expected matching IntegerTy");
+
+  auto *PtrToInt = cast<Instruction>(Builder.CreatePtrToInt(BasePtr, IntPtrTy));
+  auto *PtrArith = cast<Instruction>(Builder.CreateAdd(PtrToInt, Offset));
+  auto *NewBase = cast<Instruction>(Builder.CreateIntToPtr(PtrArith, BaseType));
+
+  // Update the base gep to use the new base register with a zero index.
+  BaseGEP->setOperand(0, NewBase);
+  BaseGEP->setOperand(1, ConstantInt::get(IntPtrTy, 0));
+
+  NewBase->insertBefore(BaseGEP);
+  PtrArith->insertBefore(NewBase);
+  PtrToInt->insertBefore(PtrArith);
+
+  LLVM_DEBUG(dbgs() << "  new base addr: " << *NewBase << "\n");
+  return NewBase;
+}
+
+bool WebAssemblyOptimizeGEPs::run(Loop *L) {
+  // - inbounds
+  // - gep base ptr
+  // - single, constant, index
+  auto IsCandidateGEP = [](GetElementPtrInst *GEP) {
+    return GEP && GEP->isInBounds() && GEP->getNumIndices() == 1 &&
+           isa<GetElementPtrInst>(GEP->getOperand(0)) &&
+           isa<ConstantInt>(GEP->getOperand(1));
+  };
+
+  // Search the loop for all the GEPs.
+  assert(L->getNumBlocks() == 1 && "Expected single block loop");
+  SmallVector<GetElementPtrInst *, 4> ToRevisit;
+  for (auto &I : *L->getHeader()) {
+    auto *GEP = dyn_cast<GetElementPtrInst>(&I);
+    if (IsCandidateGEP(GEP))
+      addCandidate(GEP);
+  }
+
+  if (Candidates.empty())
+    return false;
+
+  LLVM_DEBUG(dbgs() << "WasmOptGep: Found rebase candidates:\n";
+             for (auto BasePtr
+                  : BasePtrs) for (auto &Candidate
+                                   : Candidates[BasePtr]) Candidate.dump(););
+
+  // Refactor the common base components into a new base address, updating each
+  // GEP to use it.
+  for (auto &BasePtr : BasePtrs) {
+    Instruction *NewBase = createNewBaseAddr(BasePtr, L);
+    for (auto &Candidate : Candidates[BasePtr])
+      Candidate.update(NewBase);
+  }
+
+  return true;
+}

llvm/lib/Target/WebAssembly/WebAssemblyTargetMachine.cpp

extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeWebAssemblyTarget() {
   initializeWebAssemblyExplicitLocalsPass(PR);
   initializeWebAssemblyLowerBrUnlessPass(PR);
   initializeWebAssemblyRegNumberingPass(PR);
   initializeWebAssemblyDebugFixupPass(PR);
   initializeWebAssemblyPeepholePass(PR);
   initializeWebAssemblyMCLowerPrePassPass(PR);
   initializeWebAssemblyLowerRefTypesIntPtrConvPass(PR);
   initializeWebAssemblyFixBrTableDefaultsPass(PR);
+  initializeWebAssemblyOptimizeGEPsPass(PR);
 }
 
 //===----------------------------------------------------------------------===//
 // WebAssembly Lowering public interface.
 //===----------------------------------------------------------------------===//
 
 static Reloc::Model getEffectiveRelocModel(std::optional<Reloc::Model> RM,
                                            const Triple &TT) {
void WebAssemblyPassConfig::addIRPasses() {
   // LowerEmscriptenEHSjLj pass also when Wasm SjLj is enabled.
   if (WasmEnableEmEH || WasmEnableEmSjLj || WasmEnableSjLj)
     addPass(createWebAssemblyLowerEmscriptenEHSjLj());
 
   // Expand indirectbr instructions to switches.
   addPass(createIndirectBrExpandPass());
 
   TargetPassConfig::addIRPasses();
 }
 
 void WebAssemblyPassConfig::addISelPrepare() {
   // Lower atomics and TLS if necessary
   addPass(new CoalesceFeaturesAndStripAtomics(&getWebAssemblyTargetMachine()));
 
   // This is a no-op if atomics are not used in the module
   addPass(createAtomicExpandPass());
 

llvm/test/CodeGen/WebAssembly/optimize-geps-wasm64.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -mtriple=wasm64 -separate-const-offset-from-gep -early-cse -wasm-optimize-geps -loop-reduce -S %s -o - | FileCheck %s
+target datalayout = "e-m:e-p:64:64-p10:8:8-p20:8:8-i64:64-n32:64-S128-ni:1:10:20"
+
+; Test that all inbound geps remain so after loop-reduce
+
+define hidden void @unroll_twice(ptr nocapture noundef readonly %0, ptr nocapture noundef writeonly %1) {
+; CHECK-LABEL: @unroll_twice(
+; CHECK-NEXT:    [[TMP3:%.*]] = ptrtoint ptr [[TMP0:%.*]] to i64
+; CHECK-NEXT:    [[TMP4:%.*]] = ptrtoint ptr [[TMP1:%.*]] to i64
+; CHECK-NEXT:    br label [[TMP6:%.*]]
+; CHECK:       5:
+; CHECK-NEXT:    ret void
+; CHECK:       6:
+; CHECK-NEXT:    [[TMP7:%.*]] = phi i64 [ 0, [[TMP2:%.*]] ], [ [[TMP18:%.*]], [[TMP6]] ]
+; CHECK-NEXT:    [[TMP8:%.*]] = add i64 [[TMP3]], [[TMP7]]
+; CHECK-NEXT:    [[TMP9:%.*]] = inttoptr i64 [[TMP8]] to ptr
+; CHECK-NEXT:    [[TMP10:%.*]] = getelementptr inbounds i32, ptr [[TMP9]], i64 0
+; CHECK-NEXT:    [[TMP11:%.*]] = load i32, ptr [[TMP10]], align 4
+; CHECK-NEXT:    [[TMP12:%.*]] = add i64 [[TMP4]], [[TMP7]]
+; CHECK-NEXT:    [[TMP13:%.*]] = inttoptr i64 [[TMP12]] to ptr
+; CHECK-NEXT:    [[TMP14:%.*]] = getelementptr inbounds i32, ptr [[TMP13]], i64 0
+; CHECK-NEXT:    store i32 [[TMP11]], ptr [[TMP14]], align 4
+; CHECK-NEXT:    [[TMP15:%.*]] = getelementptr inbounds i32, ptr [[TMP9]], i64 1
+; CHECK-NEXT:    [[TMP16:%.*]] = load i32, ptr [[TMP15]], align 4
+; CHECK-NEXT:    [[TMP17:%.*]] = getelementptr inbounds i32, ptr [[TMP13]], i64 1
+; CHECK-NEXT:    store i32 [[TMP16]], ptr [[TMP17]], align 4
+; CHECK-NEXT:    [[TMP18]] = add nuw nsw i64 [[TMP7]], 2
+; CHECK-NEXT:    [[TMP19:%.*]] = icmp eq i64 [[TMP18]], 10000
+; CHECK-NEXT:    br i1 [[TMP19]], label [[TMP5:%.*]], label [[TMP6]]
+;
+  br label %4
+
+3:                                                ; preds = %4
+  ret void
+
+4:                                                ; preds = %4, %2
+  %5 = phi i64 [ 0, %2 ], [ %13, %4 ]
+  %6 = getelementptr inbounds i32, ptr %0, i64 %5
+  %7 = load i32, ptr %6, align 4
+  %8 = getelementptr inbounds i32, ptr %1, i64 %5
+  store i32 %7, ptr %8, align 4
+  %9 = or i64 %5, 1
+  %10 = getelementptr inbounds i32, ptr %0, i64 %9
+  %11 = load i32, ptr %10, align 4
+  %12 = getelementptr inbounds i32, ptr %1, i64 %9
+  store i32 %11, ptr %12, align 4
+  %13 = add nuw nsw i64 %5, 2
+  %14 = icmp eq i64 %13, 10000
+  br i1 %14, label %3, label %4
+}

llvm/test/CodeGen/WebAssembly/optimize-geps.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -mtriple=wasm32 -separate-const-offset-from-gep -early-cse -wasm-optimize-geps -loop-reduce -S %s -o - | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-p10:8:8-p20:8:8-i64:64-n32:64-S128-ni:1:10:20"
+
+; Test that all the inbounds getelementptr instructions are still inbounds
+; after loop-reduce.
+
+define hidden void @unroll_twice(ptr nocapture noundef readonly %arg, ptr nocapture noundef writeonly %arg1) {
+; CHECK-LABEL: @unroll_twice(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[ARG6:%.*]] = ptrtoint ptr [[ARG:%.*]] to i32
+; CHECK-NEXT:    [[ARG15:%.*]] = ptrtoint ptr [[ARG1:%.*]] to i32
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    ret void
+; CHECK:       bb3:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[BB:%.*]] ], [ [[I11:%.*]], [[BB3]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[ARG6]], [[I]]
+; CHECK-NEXT:    [[TMP1:%.*]] = inttoptr i32 [[TMP0]] to ptr
+; CHECK-NEXT:    [[I4:%.*]] = getelementptr inbounds i32, ptr [[TMP1]], i32 0
+; CHECK-NEXT:    [[I5:%.*]] = load i32, ptr [[I4]], align 4
+; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[ARG15]], [[I]]
+; CHECK-NEXT:    [[TMP3:%.*]] = inttoptr i32 [[TMP2]] to ptr
+; CHECK-NEXT:    [[I6:%.*]] = getelementptr inbounds i32, ptr [[TMP3]], i32 0
+; CHECK-NEXT:    store i32 [[I5]], ptr [[I6]], align 4
+; CHECK-NEXT:    [[I82:%.*]] = getelementptr inbounds i32, ptr [[TMP1]], i32 1
+; CHECK-NEXT:    [[I9:%.*]] = load i32, ptr [[I82]], align 4
+; CHECK-NEXT:    [[I104:%.*]] = getelementptr inbounds i32, ptr [[TMP3]], i32 1
+; CHECK-NEXT:    store i32 [[I9]], ptr [[I104]], align 4
+; CHECK-NEXT:    [[I11]] = add nuw nsw i32 [[I]], 2
+; CHECK-NEXT:    [[I12:%.*]] = icmp eq i32 [[I11]], 10000
+; CHECK-NEXT:    br i1 [[I12]], label [[BB2:%.*]], label [[BB3]]
+;
+bb:
+  br label %bb3
+
+bb2:                                              ; preds = %bb3
+  ret void
+
+bb3:                                              ; preds = %bb3, %bb
+  %i = phi i32 [ 0, %bb ], [ %i11, %bb3 ]
+  %i4 = getelementptr inbounds i32, ptr %arg, i32 %i
+  %i5 = load i32, ptr %i4, align 4
+  %i6 = getelementptr inbounds i32, ptr %arg1, i32 %i
+  store i32 %i5, ptr %i6, align 4
+  %i7 = or i32 %i, 1
+  %i8 = getelementptr inbounds i32, ptr %arg, i32 %i7
+  %i9 = load i32, ptr %i8, align 4
+  %i10 = getelementptr inbounds i32, ptr %arg1, i32 %i7
+  store i32 %i9, ptr %i10, align 4
+  %i11 = add nuw nsw i32 %i, 2
+  %i12 = icmp eq i32 %i11, 10000
+  br i1 %i12, label %bb2, label %bb3
+}
+
+define hidden void @no_inbound_loads(ptr nocapture noundef readonly %arg, ptr nocapture noundef writeonly %arg1) {
+; CHECK-LABEL: @no_inbound_loads(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[ARG15:%.*]] = ptrtoint ptr [[ARG1:%.*]] to i32
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    ret void
+; CHECK:       bb3:
+; CHECK-NEXT:    [[LSR_IV:%.*]] = phi ptr [ [[UGLYGEP:%.*]], [[BB3]] ], [ [[ARG:%.*]], [[BB:%.*]] ]
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[BB]] ], [ [[I11:%.*]], [[BB3]] ]
+; CHECK-NEXT:    [[I5:%.*]] = load i32, ptr [[LSR_IV]], align 4
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[ARG15]], [[I]]
+; CHECK-NEXT:    [[TMP1:%.*]] = inttoptr i32 [[TMP0]] to ptr
+; CHECK-NEXT:    [[I6:%.*]] = getelementptr inbounds i32, ptr [[TMP1]], i32 0
+; CHECK-NEXT:    store i32 [[I5]], ptr [[I6]], align 4
+; CHECK-NEXT:    [[UGLYGEP6:%.*]] = getelementptr i8, ptr [[LSR_IV]], i32 4
+; CHECK-NEXT:    [[I9:%.*]] = load i32, ptr [[UGLYGEP6]], align 4
+; CHECK-NEXT:    [[I104:%.*]] = getelementptr inbounds i32, ptr [[TMP1]], i32 1
+; CHECK-NEXT:    store i32 [[I9]], ptr [[I104]], align 4
+; CHECK-NEXT:    [[I11]] = add nuw nsw i32 [[I]], 2
+; CHECK-NEXT:    [[UGLYGEP]] = getelementptr i8, ptr [[LSR_IV]], i32 8
+; CHECK-NEXT:    [[I12:%.*]] = icmp eq i32 [[I11]], 10000
+; CHECK-NEXT:    br i1 [[I12]], label [[BB2:%.*]], label [[BB3]]
+;
+bb:
+  br label %bb3
+
+bb2:                                              ; preds = %bb3
+  ret void
+
+bb3:                                              ; preds = %bb3, %bb
+  %i = phi i32 [ 0, %bb ], [ %i11, %bb3 ]
+  %i4 = getelementptr i32, ptr %arg, i32 %i
+  %i5 = load i32, ptr %i4, align 4
+  %i6 = getelementptr inbounds i32, ptr %arg1, i32 %i
+  store i32 %i5, ptr %i6, align 4
+  %i7 = or i32 %i, 1
+  %i8 = getelementptr i32, ptr %arg, i32 %i7
+  %i9 = load i32, ptr %i8, align 4
+  %i10 = getelementptr inbounds i32, ptr %arg1, i32 %i7
+  store i32 %i9, ptr %i10, align 4
+  %i11 = add nuw nsw i32 %i, 2
+  %i12 = icmp eq i32 %i11, 10000
+  br i1 %i12, label %bb2, label %bb3
+}
+
+define hidden void @runtime_unroll(ptr nocapture noundef readonly %arg, ptr nocapture noundef readonly %arg1, ptr nocapture noundef writeonly %arg2, i32 noundef %arg3) {
+; CHECK-LABEL: @runtime_unroll(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[ARG9:%.*]] = ptrtoint ptr [[ARG:%.*]] to i32
+; CHECK-NEXT:    [[ARG18:%.*]] = ptrtoint ptr [[ARG1:%.*]] to i32
+; CHECK-NEXT:    [[ARG27:%.*]] = ptrtoint ptr [[ARG2:%.*]] to i32
+; CHECK-NEXT:    [[I:%.*]] = icmp eq i32 [[ARG3:%.*]], 0
+; CHECK-NEXT:    br i1 [[I]], label [[BB19:%.*]], label [[BB4:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    [[I5:%.*]] = and i32 [[ARG3]], 1
+; CHECK-NEXT:    [[I6:%.*]] = icmp eq i32 [[ARG3]], 1
+; CHECK-NEXT:    br i1 [[I6]], label [[BB9:%.*]], label [[BB7:%.*]]
+; CHECK:       bb7:
+; CHECK-NEXT:    [[I8:%.*]] = and i32 [[ARG3]], -2
+; CHECK-NEXT:    br label [[BB20:%.*]]
+; CHECK:       bb9.loopexit:
+; CHECK-NEXT:    br label [[BB9]]
+; CHECK:       bb9:
+; CHECK-NEXT:    [[I10:%.*]] = phi i32 [ 0, [[BB4]] ], [ [[I36:%.*]], [[BB9_LOOPEXIT:%.*]] ]
+; CHECK-NEXT:    [[I11:%.*]] = icmp eq i32 [[I5]], 0
+; CHECK-NEXT:    br i1 [[I11]], label [[BB19]], label [[BB12:%.*]]
+; CHECK:       bb12:
+; CHECK-NEXT:    [[I13:%.*]] = getelementptr inbounds float, ptr [[ARG]], i32 [[I10]]
+; CHECK-NEXT:    [[I14:%.*]] = load float, ptr [[I13]], align 4
+; CHECK-NEXT:    [[I15:%.*]] = getelementptr inbounds float, ptr [[ARG1]], i32 [[I10]]
+; CHECK-NEXT:    [[I16:%.*]] = load float, ptr [[I15]], align 4
+; CHECK-NEXT:    [[I17:%.*]] = fadd float [[I14]], [[I16]]
+; CHECK-NEXT:    [[I18:%.*]] = getelementptr inbounds float, ptr [[ARG2]], i32 [[I10]]
+; CHECK-NEXT:    store float [[I17]], ptr [[I18]], align 4
+; CHECK-NEXT:    br label [[BB19]]
+; CHECK:       bb19:
+; CHECK-NEXT:    ret void
+; CHECK:       bb20:
+; CHECK-NEXT:    [[I21:%.*]] = phi i32 [ 0, [[BB7]] ], [ [[I36]], [[BB20]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[ARG9]], [[I21]]
+; CHECK-NEXT:    [[TMP1:%.*]] = inttoptr i32 [[TMP0]] to ptr
+; CHECK-NEXT:    [[I23:%.*]] = getelementptr inbounds float, ptr [[TMP1]], i32 0
+; CHECK-NEXT:    [[I24:%.*]] = load float, ptr [[I23]], align 4
+; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[ARG18]], [[I21]]
+; CHECK-NEXT:    [[TMP3:%.*]] = inttoptr i32 [[TMP2]] to ptr
+; CHECK-NEXT:    [[I25:%.*]] = getelementptr inbounds float, ptr [[TMP3]], i32 0
+; CHECK-NEXT:    [[I26:%.*]] = load float, ptr [[I25]], align 4
+; CHECK-NEXT:    [[I27:%.*]] = fadd float [[I24]], [[I26]]
+; CHECK-NEXT:    [[TMP4:%.*]] = add i32 [[ARG27]], [[I21]]
+; CHECK-NEXT:    [[TMP5:%.*]] = inttoptr i32 [[TMP4]] to ptr
+; CHECK-NEXT:    [[I28:%.*]] = getelementptr inbounds float, ptr [[TMP5]], i32 0
+; CHECK-NEXT:    store float [[I27]], ptr [[I28]], align 4
+; CHECK-NEXT:    [[I302:%.*]] = getelementptr inbounds float, ptr [[TMP1]], i32 1
+; CHECK-NEXT:    [[I31:%.*]] = load float, ptr [[I302]], align 4
+; CHECK-NEXT:    [[I324:%.*]] = getelementptr inbounds float, ptr [[TMP3]], i32 1
+; CHECK-NEXT:    [[I33:%.*]] = load float, ptr [[I324]], align 4
+; CHECK-NEXT:    [[I34:%.*]] = fadd float [[I31]], [[I33]]
+; CHECK-NEXT:    [[I356:%.*]] = getelementptr inbounds float, ptr [[TMP5]], i32 1
+; CHECK-NEXT:    store float [[I34]], ptr [[I356]], align 4
+; CHECK-NEXT:    [[I36]] = add i32 [[I21]], 2
+; CHECK-NEXT:    [[I38:%.*]] = icmp eq i32 [[I8]], [[I36]]
+; CHECK-NEXT:    br i1 [[I38]], label [[BB9_LOOPEXIT]], label [[BB20]]
+;
+bb:
+  %i = icmp eq i32 %arg3, 0
+  br i1 %i, label %bb19, label %bb4
+
+bb4:                                              ; preds = %bb
+  %i5 = and i32 %arg3, 1
+  %i6 = icmp eq i32 %arg3, 1
+  br i1 %i6, label %bb9, label %bb7
+
+bb7:                                              ; preds = %bb4
+  %i8 = and i32 %arg3, -2
+  br label %bb20
+
+bb9:                                              ; preds = %bb20, %bb4
+  %i10 = phi i32 [ 0, %bb4 ], [ %i36, %bb20 ]
+  %i11 = icmp eq i32 %i5, 0
+  br i1 %i11, label %bb19, label %bb12
+
+bb12:                                             ; preds = %bb9
+  %i13 = getelementptr inbounds float, ptr %arg, i32 %i10
+  %i14 = load float, ptr %i13, align 4
+  %i15 = getelementptr inbounds float, ptr %arg1, i32 %i10
+  %i16 = load float, ptr %i15, align 4
+  %i17 = fadd float %i14, %i16
+  %i18 = getelementptr inbounds float, ptr %arg2, i32 %i10
+  store float %i17, ptr %i18, align 4
+  br label %bb19
+
+bb19:                                             ; preds = %bb12, %bb9, %bb
+  ret void
+
+bb20:                                             ; preds = %bb20, %bb7
+  %i21 = phi i32 [ 0, %bb7 ], [ %i36, %bb20 ]
+  %i22 = phi i32 [ 0, %bb7 ], [ %i37, %bb20 ]
+  %i23 = getelementptr inbounds float, ptr %arg, i32 %i21
+  %i24 = load float, ptr %i23, align 4
+  %i25 = getelementptr inbounds float, ptr %arg1, i32 %i21
+  %i26 = load float, ptr %i25, align 4
+  %i27 = fadd float %i24, %i26
+  %i28 = getelementptr inbounds float, ptr %arg2, i32 %i21
+  store float %i27, ptr %i28, align 4
+  %i29 = or i32 %i21, 1
+  %i30 = getelementptr inbounds float, ptr %arg, i32 %i29
+  %i31 = load float, ptr %i30, align 4
+  %i32 = getelementptr inbounds float, ptr %arg1, i32 %i29
+  %i33 = load float, ptr %i32, align 4
+  %i34 = fadd float %i31, %i33
+  %i35 = getelementptr inbounds float, ptr %arg2, i32 %i29
+  store float %i34, ptr %i35, align 4
+  %i36 = add nuw i32 %i21, 2
+  %i37 = add i32 %i22, 2
+  %i38 = icmp eq i32 %i37, %i8
+  br i1 %i38, label %bb9, label %bb20
+}

llvm/utils/gn/secondary/llvm/lib/Target/WebAssembly/BUILD.gn

sources = [
     "WebAssemblyLowerBrUnless.cpp",
     "WebAssemblyLowerEmscriptenEHSjLj.cpp",
     "WebAssemblyLowerRefTypesIntPtrConv.cpp",
     "WebAssemblyMCInstLower.cpp",
     "WebAssemblyMCLowerPrePass.cpp",
     "WebAssemblyMachineFunctionInfo.cpp",
     "WebAssemblyMemIntrinsicResults.cpp",
     "WebAssemblyNullifyDebugValueLists.cpp",
+    "WebAssemblyOptimizeGEPs.cpp",
     "WebAssemblyOptimizeLiveIntervals.cpp",
     "WebAssemblyOptimizeReturned.cpp",
     "WebAssemblyPeephole.cpp",
     "WebAssemblyRegColoring.cpp",
     "WebAssemblyRegNumbering.cpp",
     "WebAssemblyRegStackify.cpp",
     "WebAssemblyRegisterInfo.cpp",
     "WebAssemblyReplacePhysRegs.cpp",