[llvm/CodeGen] Add ExpandLargeDivRem pass

[mgehre-amd]

Summary

Adds a pass ExpandLargeDivRem to expand div/rem instructions
with more than 128 bits into auto-generated loops.

For example, urem i129 is expanded into a loop that is
automatically generated to implement
a simple shift-subtract algorithm similar to

loop:                                             ; preds = %if.end, %entry
  %i = phi i32 [ 128, %entry ], [ %new_i, %if.end ]
  %r = phi i129 [ 0, %entry ], [ %r3, %if.end ]
  %iext = zext i32 %i to i129
  %2 = lshr i129 %0, %iext
  %3 = trunc i129 %2 to i1
  %new_r = shl i129 %r, 1
  %4 = zext i1 %3 to i129
  %new_r1 = or i129 %new_r, %4
  %loop_exit_cond = icmp eq i32 %i, 0
  %new_i = add i32 %i, -1
  %5 = icmp uge i129 %new_r1, %1
  br i1 %5, label %then, label %if.end

then:                                             ; preds = %loop
  %new_r2 = sub i129 %new_r1, %1
  br label %if.end

if.end:                                           ; preds = %then, %loop
  %r3 = phi i129 [ %new_r2, %then ], [ %new_r1, %loop ]
  br i1 %loop_exit_cond, label %exit, label %loop

  ; Result is in %r3
}

As discussed on https://reviews.llvm.org/D120327, this approach has the advantage
that it is independent of the runtime library. This also helps the clang driver,
which otherwise would need to understand enough about the runtime library
to know whether to allow _BitInts with more than 128 bits.

Targets are still free to disable this pass and instead provide a faster
implementation in a runtime library.

Fixes https://github.com/llvm/llvm-project/issues/44994

[efriedma]

My primary concern here is that we're unconditionally iterating over every instruction in the module, even if the pass has nothing to do. In the grand scheme of things, it isn't *that* expensive, but it's still not cheap, and we seem to have grown a number of passes doing similar walks. Can we merge this with some other walk over the module?

[mgehre-amd]

In D126644#3580139, @efriedma wrote:

My primary concern here is that we're unconditionally iterating over every instruction in the module, even if the pass has nothing to do. In the grand scheme of things, it isn't *that* expensive, but it's still not cheap, and we seem to have grown a number of passes doing similar walks. Can we merge this with some other walk over the module?

Hey, thanks for taking the time to look into this PR.
I looked around the pipeline to find passes that look relevant. I saw a few that didn't work because they are only enabled above -O0.
Then I found others that in principle would work, but all of those are so focused (createGCLoweringPass, createLowerConstantIntrinsicsPass, createExpandMemCmpPass, createPreISelIntrinsicLoweringPass, ...) that it felt wrong
to dilute their focus by adding the div/rem transformation.
Under -O2, we currently run 454 passes in the middle end and the backend combined.

Do you have a concrete proposal how I could address your concern?

[arsenm]

It's very unusual for a lowering strategy to introduce a new function. I would expect to expand the instruction inline and not emit a separate function, which avoids the need for this to be a module pass.

llvm/lib/CodeGen/ExpandLargeDivRem.cpp

54–60

Can you set these all at once with AttributeList

219

You shouldn't need to pre-accumulate the instructions, just use make_early_inc_range on the instruction iterator?

227–228

dyn_cast instead of isa + implicit cast to IntegerType?

228

Since this is ultimately a workaround for SelectionDAG, ideally this would be a TargetLowering control

[arsenm]

Actually, how is this really different from lib/Transforms/Utils/IntegerDivision.cpp? This just goes to 128 but the existing code goes up to 64. Can you merge them, or at least move the implementation bodies to the same place?

[mgehre-amd]

In D126644#3581484, @arsenm wrote:

Actually, how is this really different from lib/Transforms/Utils/IntegerDivision.cpp? This just goes to 128 but the existing code goes up to 64. Can you merge them, or at least move the implementation bodies to the same place?

Thanks, I really didn't know about IntegerDivision.cpp! I'll try to merge both implementations. If that works, I can use it here and avoid emitting a new function.

[arsenm]

Another problem is this will miss divisions embedded in constant expressions

[mgehre-amd]

In D126644#3582347, @arsenm wrote:

Another problem is this will miss divisions embedded in constant expressions

Good point. I wasn't able to create a reproducer from C to a sdiv constant expression, but there is a C++ reproducer: https://godbolt.org/z/v5Tsh8n9x.
My hypothesis is that there is no C/C++ code that creates an sdiv/udiv/srem/urem constant expression in a global variable initializers.
So it would be sufficient to walk the ConstantExpr operands of all instructions, looking for sdiv etc that needs to be converted, and
then uses something like replaceConstantUsesInFunction() to turn them into instructions. Does that sound sensible?

[mgehre-amd]

Use IntegerDivison.cpp
Do not emit separate functions
Turn into FunctionPass

llvm/lib/CodeGen/ExpandLargeDivRem.cpp

219

I tried, but it crashed. I think that's because we not only remove the current instruction but also insert new basic blocks, which confuses make_early_inc_range (instructions(F)).

228

I'm not sure how I would wire TargetLowering into the pass - I didn't find other passes using it.
Would TargetTransformInfo also work for you?

[mgehre-amd]

With the work around constant expressions (e.g. https://reviews.llvm.org/rG941c8e0ea50b), I might not need to handle div/mod constants anymore. For that reason, I would at least land this PR without support for transforming constant expressions.

[nikic]

In D126644#3634017, @mgehre-amd wrote:

With the work around constant expressions (e.g. https://reviews.llvm.org/rG941c8e0ea50b), I might not need to handle div/mod constants anymore. For that reason, I would at least land this PR without support for transforming constant expressions.

div/rem constant expressions have already been removed. So yes, no need to handle them here anymore.

[mgehre-amd]

Ping, how can I get review/approval for this PR? Should I add somebody else as reviewer?

[nikic]

I'm a bit confused, where in the code does this actually create functions? It doesn't look like expandDivision() does that, and I can't spot anything else creating __llvm_udivXXX either.

llvm/lib/CodeGen/ExpandLargeDivRem.cpp

41

You should either do the replacement directly in this loop, or not use make_early_inc_range. Doesn't make sense to use it if you're not modifying anything.

42

Unnecessary newline

69

Could use a vector of BinaryOperator to avoid the casts here.

85

At least for the new pass manager, I don't think it's legal to add new functions in a function pass. I'm not sure about the legacy pass manager.

llvm/lib/CodeGen/TargetPassConfig.cpp

859 ↗

(On Diff #437840)

Spurious change.

llvm/lib/Transforms/Utils/IntegerDivision.cpp

35

Precommit as NFC changes?

llvm/test/CodeGen/X86/urem-seteq.ll

380

What happened here?

[arsenm]

llvm/lib/CodeGen/ExpandLargeDivRem.cpp

48

This won't handle vectors

llvm/test/Transforms/ExpandLargeDivRem/urem129.ll

14

This looks out of date?

llvm/test/Transforms/ExpandLargeDivRem/values129.ll

6 ↗

(On Diff #437840)

Shouldn't use -O2 in a test like this

21 ↗

(On Diff #437840)

I'm not sure cases that constant fold are the most helpful tests

[mgehre-amd]

In D126644#3645177, @nikic wrote:

I'm a bit confused, where in the code does this actually create functions? It doesn't look like expandDivision() does that, and I can't spot anything else creating __llvm_udivXXX either.

Yes, I changed that approach to directly generate a loop in place of the original instruction as it was requested by one of the initial review comments here. I now also updated the PR description to reflect that.

[mgehre-amd]

Implement review comments

[mgehre-amd]

Thanks for the review! I updated the PR to reflect your comments.

llvm/lib/CodeGen/ExpandLargeDivRem.cpp

48

True, I'm not concerned about vectors right now. I can add a TODO comment here.

85

Yes, this was one of the early comments I got on this PR, so I changed it to not insert new functions but instead insert the loop in-place.

llvm/test/CodeGen/X86/urem-seteq.ll

380

This IR used to crash LLVM. I don't think that the actual assembly is relevant here, and after my changes it's much longer due to the loops that were inserted.

llvm/test/Transforms/ExpandLargeDivRem/urem129.ll

14

Yes, stupid me. I'll update.

llvm/test/Transforms/ExpandLargeDivRem/values129.ll

21 ↗

(On Diff #437840)

I wrote this test when the implementation of the shift-subtract loop was still mine. It is verifying that
the value that is computed by that loop is the same as the value of the urem.
This is done by comparing whether constant-folding the urem directly gives the same value
as first replacing the urem by expandlargedivrem and then constant folding the result.

Then, I learned that there was existing implementation of the shift-subtract loop in llvm/lib/Transforms/Utils/IntegerDivision.cpp and switched to that.
Because Utils/IntegerDivision.cpp is already tested, I will get rid of this test here.

[arsenm]

llvm/lib/CodeGen/TargetPassConfig.cpp

1115 ↗

(On Diff #444914)

This doesn't belong in this patch. Currently this is lacking in legality checks for the expansion. I would prefer to see a separate patch which adds the pass and checks the legality per target, rather than relying on the arbitrary command line threshold

llvm/test/Transforms/ExpandLargeDivRem/sdiv129.ll

12

The positioning of the checks looks weird. Usually update_test_checks put these comments inside the function?

[mgehre-amd]

llvm/lib/CodeGen/TargetPassConfig.cpp

1115 ↗

(On Diff #444914)

Ok, I'll make a follow-up PR to add the pass and configure a per-target threshold.
I'm thinking about adding an int MaxLegalDivRemBitSize member to TargetTransformInfo.

llvm/test/Transforms/ExpandLargeDivRem/sdiv129.ll

12

I guess the position is still from the time where this was an extra function. I regenerated the check-lines, but update_test_checks.py doesn't move them around. I will re-generate them from scratch to get the typical position.

[mgehre-amd]

Remove pass from pass pipeline (will be added in next PR)

[craig.topper]

llvm/lib/CodeGen/ExpandLargeDivRem.cpp

13

I think but haven't checked that 32-bit x86, ARM, RISCV32, and other 32-bit targets can't lower division with more than 64 bits.

34

This says "<N> or more bits", but the code exits for <= ExpandDivRemBits

llvm/lib/Transforms/Utils/IntegerDivision.cpp

145–148

You already have the DivTy, why not go through ConstantInt::get for all of these?

llvm/test/Transforms/ExpandLargeDivRem/urem129.ll

15

Is this code handling the possible poison result from the ctlz's incorrectly? If [A] is zero then [TMP3] is poison, [TMP4] is poison, [TMP5] is poison, [TMP6] being an or won't block the poison. Assuming I understand poison correctly.

I don't think that was caused by this patch. It's an issue in the existing code.

[craig.topper]

llvm/test/Transforms/ExpandLargeDivRem/urem129.ll

15

Patch for the poison issue https://reviews.llvm.org/D130680

[mgehre-amd]

Fix description of expand-div-rem-bits argument
Use ConstantInt::get

llvm/lib/CodeGen/ExpandLargeDivRem.cpp

13

I checked x86_32 and it lowers 128 bit divisions to __divti3: https://godbolt.org/z/Y6hT9n3x5

34

done

llvm/lib/Transforms/Utils/IntegerDivision.cpp

145–148

done

[craig.topper]

llvm/lib/CodeGen/ExpandLargeDivRem.cpp

13

But it fails to link https://godbolt.org/z/5x38Gxqa9 so I think that's a bug. __divti3 doesn't exist in 32-bit libgcc.

[mgehre-amd]

llvm/lib/CodeGen/ExpandLargeDivRem.cpp

13

That's a good observation! I will update the comment.
I also need to modify the follow-up PR, https://reviews.llvm.org/D130076,
to set the correct limits for those targets.

[mgehre-amd]

Clarify that x86_32 cannot lower division with more than 64 bits.

[craig.topper]

llvm/lib/CodeGen/ExpandLargeDivRem.cpp

13

I thought about disabling that libcall in 32-bit mode, but the it is supported by compiler-rt. So I guess a linker error when using libgcc is better than a compiler error when using compiler-rt or libgcc until we get this pass in.

[hiraditya]

We usually provide a runtime library for specialized functionalities like this. Are such division operations common enough to benefit from compiler generated code?

[mgehre-amd]

In D126644#3686479, @hiraditya wrote:

We usually provide a runtime library for specialized functionalities like this. Are such division operations common enough to benefit from compiler generated code?

We explored and prototyped the approach of adding a functions to compiler-rt in a different PR. We discovered multiple issues.

One issues is that we don't have a fixed type here. There are existing library functions to do 64 bit or 128 bit division, but here we want to implement divisions with any bitsize above 129. This makes defining an ABI harder.
In addition, the main runtime library on Linux is libgcc, and it lacks such functions. It won't be easy to get them added to libgcc due to the fact that gcc doesn't have _BitInt support yet.
Providing an additional runtime on top of libgcc with just those new functions is also new territory.

So in the end, a lot of things become easier by just doing the transformation on the IR directly.

[mgehre-amd]

Friendly ping :-)
I think I addressed all comments. Is somebody able to approve this?

[mgehre-amd]

Rebased

[pengfei]

One issues is that we don't have a fixed type here. There are existing library functions to do 64 bit or 128 bit division, but here we want to implement divisions with any bitsize above 129. This makes defining an ABI harder.

Yeah, X86 psABI has new defination for fixed bitsize. But it doesn't help here.

In addition, the main runtime library on Linux is libgcc, and it lacks such functions. It won't be easy to get them added to libgcc due to the fact that gcc doesn't have _BitInt support yet.

Applaud. Implementing runtime library per to ABI is problematic. It is easy resulting in backward compatibility issues. So I incline to this approach. But I didn't look into the details and long discussions, I'd like to other reviewers to sign off.

llvm/include/llvm/CodeGen/ExpandLargeDivRem.h

2

Update the name.

llvm/include/llvm/CodeGen/MachinePassRegistry.def

46

Nit: Maybe better to use expand-large-div-rem.

llvm/lib/CodeGen/ExpandLargeDivRem.cpp

2

Ditto.

[mgehre-amd]

Rename expandlargedivrem to expand-large-div-rem
Fix filenames in comments

[mgehre-amd]

Ping :)

[pengfei]

I don't find any problems. Maybe we can let it go :)

llvm/include/llvm/CodeGen/ExpandLargeDivRem.h

+//===----- ExpandLargeDivRem.h - Expand large div/rem ---------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_EXPANDLARGEDIVREM_H
+#define LLVM_CODEGEN_EXPANDLARGEDIVREM_H
+
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+/// Expands div/rem instructions with a bitwidth above a threshold
+/// into a loop.
+/// This is useful for backends like x86 that cannot lower divisions
+/// with more than 128 bits.
+class ExpandLargeDivRemPass : public PassInfoMixin<ExpandLargeDivRemPass> {
+public:
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+
+  // The backend asserts when seeing large div/rem instructions.
+  static bool isRequired() { return true; }
+};
+} // end namespace llvm
+
+#endif // LLVM_CODEGEN_EXPANDLARGEDIVREM_H

llvm/include/llvm/CodeGen/MachinePassRegistry.def

 FUNCTION_PASS("mergeicmps", MergeICmpsPass, ())
 FUNCTION_PASS("lower-constant-intrinsics", LowerConstantIntrinsicsPass, ())
 FUNCTION_PASS("unreachableblockelim", UnreachableBlockElimPass, ())
 FUNCTION_PASS("consthoist", ConstantHoistingPass, ())
 FUNCTION_PASS("replace-with-veclib", ReplaceWithVeclib, ())
 FUNCTION_PASS("partially-inline-libcalls", PartiallyInlineLibCallsPass, ())
 FUNCTION_PASS("ee-instrument", EntryExitInstrumenterPass, (false))
 FUNCTION_PASS("post-inline-ee-instrument", EntryExitInstrumenterPass, (true))
+FUNCTION_PASS("expand-large-div-rem", ExpandLargeDivRemPass, ())
 FUNCTION_PASS("expand-reductions", ExpandReductionsPass, ())
 FUNCTION_PASS("expandvp", ExpandVectorPredicationPass, ())
 FUNCTION_PASS("lowerinvoke", LowerInvokePass, ())
 FUNCTION_PASS("scalarize-masked-mem-intrin", ScalarizeMaskedMemIntrinPass, ())
 FUNCTION_PASS("tlshoist", TLSVariableHoistPass, ())
 FUNCTION_PASS("verify", VerifierPass, ())
 #undef FUNCTION_PASS
 

llvm/include/llvm/CodeGen/Passes.h

namespace llvm {
   // the corresponding function in a vector library (e.g., SVML, libmvec).
   FunctionPass *createReplaceWithVeclibLegacyPass();
 
   /// This pass expands the vector predication intrinsics into unpredicated
   /// instructions with selects or just the explicit vector length into the
   /// predicate mask.
   FunctionPass *createExpandVectorPredicationPass();
 
+  // Expands large div/rem instructions.
+  FunctionPass *createExpandLargeDivRemPass();
+
   // This pass expands memcmp() to load/stores.
   FunctionPass *createExpandMemCmpPass();
 
   /// Creates Break False Dependencies pass. \see BreakFalseDeps.cpp
   FunctionPass *createBreakFalseDeps();
 
   // This pass expands indirectbr instructions.
   FunctionPass *createIndirectBrExpandPass();

llvm/include/llvm/InitializePasses.h

 void initializeEarlyCSEMemSSALegacyPassPass(PassRegistry&);
 void initializeEarlyIfConverterPass(PassRegistry&);
 void initializeEarlyIfPredicatorPass(PassRegistry &);
 void initializeEarlyMachineLICMPass(PassRegistry&);
 void initializeEarlyTailDuplicatePass(PassRegistry&);
 void initializeEdgeBundlesPass(PassRegistry&);
 void initializeEHContGuardCatchretPass(PassRegistry &);
 void initializeEliminateAvailableExternallyLegacyPassPass(PassRegistry&);
+void initializeExpandLargeDivRemLegacyPassPass(PassRegistry&);
 void initializeExpandMemCmpPassPass(PassRegistry&);
 void initializeExpandPostRAPass(PassRegistry&);
 void initializeExpandReductionsPass(PassRegistry&);
 void initializeExpandVectorPredicationPass(PassRegistry &);
 void initializeMakeGuardsExplicitLegacyPassPass(PassRegistry&);
 void initializeExternalAAWrapperPassPass(PassRegistry&);
 void initializeFEntryInserterPass(PassRegistry&);
 void initializeFinalizeISelPass(PassRegistry&);

llvm/include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createInstructionNamerPass();
       (void) llvm::createMetaRenamerPass();
       (void) llvm::createAttributorLegacyPass();
       (void) llvm::createAttributorCGSCCLegacyPass();
       (void) llvm::createPostOrderFunctionAttrsLegacyPass();
       (void) llvm::createReversePostOrderFunctionAttrsPass();
       (void) llvm::createMergeFunctionsPass();
       (void) llvm::createMergeICmpsLegacyPass();
+      (void) llvm::createExpandLargeDivRemPass();
       (void) llvm::createExpandMemCmpPass();
       (void) llvm::createExpandVectorPredicationPass();
       std::string buf;
       llvm::raw_string_ostream os(buf);
       (void) llvm::createPrintModulePass(os);
       (void) llvm::createPrintFunctionPass(os);
       (void) llvm::createModuleDebugInfoPrinterPass();
       (void) llvm::createPartialInliningPass();

llvm/lib/CodeGen/CMakeLists.txt

add_llvm_component_library(LLVMCodeGen
   DeadMachineInstructionElim.cpp
   DetectDeadLanes.cpp
   DFAPacketizer.cpp
   DwarfEHPrepare.cpp
   EarlyIfConversion.cpp
   EdgeBundles.cpp
   EHContGuardCatchret.cpp
   ExecutionDomainFix.cpp
+  ExpandLargeDivRem.cpp
   ExpandMemCmp.cpp
   ExpandPostRAPseudos.cpp
   ExpandReductions.cpp
   ExpandVectorPredication.cpp
   FaultMaps.cpp
   FEntryInserter.cpp
   FinalizeISel.cpp
   FixupStatepointCallerSaved.cpp

llvm/lib/CodeGen/CodeGen.cpp

void llvm::initializeCodeGen(PassRegistry &Registry) {
   initializeDeadMachineInstructionElimPass(Registry);
   initializeDebugifyMachineModulePass(Registry);
   initializeDetectDeadLanesPass(Registry);
   initializeDwarfEHPrepareLegacyPassPass(Registry);
   initializeEarlyIfConverterPass(Registry);
   initializeEarlyIfPredicatorPass(Registry);
   initializeEarlyMachineLICMPass(Registry);
   initializeEarlyTailDuplicatePass(Registry);
+  initializeExpandLargeDivRemLegacyPassPass(Registry);
   initializeExpandMemCmpPassPass(Registry);
   initializeExpandPostRAPass(Registry);
   initializeFEntryInserterPass(Registry);
   initializeFinalizeISelPass(Registry);
   initializeFinalizeMachineBundlesPass(Registry);
   initializeFixupStatepointCallerSavedPass(Registry);
   initializeFuncletLayoutPass(Registry);
   initializeGCMachineCodeAnalysisPass(Registry);

llvm/lib/CodeGen/ExpandLargeDivRem.cpp

+//===--- ExpandLargeDivRem.cpp - Expand large div/rem ---------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass expands div/rem instructions with a bitwidth above a threshold
+// into a call to auto-generated functions.
+// This is useful for targets like x86_64 that cannot lower divisions
+// with more than 128 bits or targets like x86_32 that cannot lower divisions
+// with more than 64 bits.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/ExpandLargeDivRem.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Transforms/Utils/IntegerDivision.h"
+
+using namespace llvm;
+
+static cl::opt<unsigned>
+    ExpandDivRemBits("expand-div-rem-bits", cl::Hidden, cl::init(128),
+                     cl::desc("div and rem instructions on integers with "
+                              "more than <N> bits are expanded."));
+
+static bool runImpl(Function &F) {
+  SmallVector<BinaryOperator *, 4> Replace;
+  bool Modified = false;
+
+  for (auto &I : instructions(F)) {
+    switch (I.getOpcode()) {
+    case Instruction::UDiv:
+    case Instruction::SDiv:
+    case Instruction::URem:
+    case Instruction::SRem: {
+      // TODO: This doesn't handle vectors.
+      auto *IntTy = dyn_cast<IntegerType>(I.getType());
+      if (!IntTy || IntTy->getIntegerBitWidth() <= ExpandDivRemBits)
+        continue;
+
+      Replace.push_back(&cast<BinaryOperator>(I));
+      Modified = true;
+      break;
+    }
+    default:
+      break;
+    }
+  }
+
+  if (Replace.empty())
+    return false;
+
+  while (!Replace.empty()) {
+    BinaryOperator *I = Replace.pop_back_val();
+
+    if (I->getOpcode() == Instruction::UDiv ||
+        I->getOpcode() == Instruction::SDiv) {
+      expandDivision(I);
+    } else {
+      expandRemainder(I);
+    }
+  }
+
+  return Modified;
+}
+
+PreservedAnalyses ExpandLargeDivRemPass::run(Function &F,
+                                             FunctionAnalysisManager &AM) {
+  bool Changed = runImpl(F);
+
+  if (Changed)
+    return PreservedAnalyses::none();
+
+  return PreservedAnalyses::all();
+}
+
+class ExpandLargeDivRemLegacyPass : public FunctionPass {
+public:
+  static char ID;
+
+  ExpandLargeDivRemLegacyPass() : FunctionPass(ID) {
+    initializeExpandLargeDivRemLegacyPassPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &F) override { return runImpl(F); }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addPreserved<AAResultsWrapperPass>();
+    AU.addPreserved<GlobalsAAWrapperPass>();
+  }
+};
+
+char ExpandLargeDivRemLegacyPass::ID = 0;
+INITIALIZE_PASS_BEGIN(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
+                      "Expand large div/rem", false, false)
+INITIALIZE_PASS_END(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
+                    "Expand large div/rem", false, false)
+
+FunctionPass *llvm::createExpandLargeDivRemPass() {
+  return new ExpandLargeDivRemLegacyPass();
+}

llvm/lib/Transforms/Utils/IntegerDivision.cpp

 /// remainder, which will have the sign of the dividend. Builder's insert point
 /// should be pointing where the caller wants code generated, e.g. at the srem
 /// instruction. This will generate a urem in the process, and Builder's insert
 /// point will be pointing at the uren (if present, i.e. not folded), ready to
 /// be expanded if the user wishes
 static Value *generateSignedRemainderCode(Value *Dividend, Value *Divisor,
                                           IRBuilder<> &Builder) {
   unsigned BitWidth = Dividend->getType()->getIntegerBitWidth();
-  ConstantInt *Shift;
-
-  if (BitWidth == 64) {
-    Shift = Builder.getInt64(63);
-  } else {
-    assert(BitWidth == 32 && "Unexpected bit width");
-    Shift = Builder.getInt32(31);
-  }
+  ConstantInt *Shift = Builder.getIntN(BitWidth, BitWidth - 1);
 
   // Following instructions are generated for both i32 (shift 31) and
   // i64 (shift 63).
 
   // ;   %dividend_sgn = ashr i32 %dividend, 31
   // ;   %divisor_sgn  = ashr i32 %divisor, 31
   // ;   %dvd_xor      = xor i32 %dividend, %dividend_sgn
   // ;   %dvs_xor      = xor i32 %divisor, %divisor_sgn

 /// code generated, e.g. at the sdiv instruction. This will generate a udiv in
 /// the process, and Builder's insert point will be pointing at the udiv (if
 /// present, i.e. not folded), ready to be expanded if the user wishes.
 static Value *generateSignedDivisionCode(Value *Dividend, Value *Divisor,
                                          IRBuilder<> &Builder) {
   // Implementation taken from compiler-rt's __divsi3 and __divdi3
 
   unsigned BitWidth = Dividend->getType()->getIntegerBitWidth();
-  ConstantInt *Shift;
-
-  if (BitWidth == 64) {
-    Shift = Builder.getInt64(63);
-  } else {
-    assert(BitWidth == 32 && "Unexpected bit width");
-    Shift = Builder.getInt32(31);
-  }
+  ConstantInt *Shift = Builder.getIntN(BitWidth, BitWidth - 1);
 
   // Following instructions are generated for both i32 (shift 31) and
   // i64 (shift 63).
 
   // ;   %tmp    = ashr i32 %dividend, 31
   // ;   %tmp1   = ashr i32 %divisor, 31
   // ;   %tmp2   = xor i32 %tmp, %dividend
   // ;   %u_dvnd = sub nsw i32 %tmp2, %tmp
static Value *generateUnsignedDivisionCode(Value *Dividend, Value *Divisor,
   // The basic algorithm can be found in the compiler-rt project's
   // implementation of __udivsi3.c. Here, we do a lower-level IR based approach
   // that's been hand-tuned to lessen the amount of control flow involved.
 
   // Some helper values
   IntegerType *DivTy = cast<IntegerType>(Dividend->getType());
   unsigned BitWidth = DivTy->getBitWidth();
 
-  ConstantInt *Zero;
-  ConstantInt *One;
-  ConstantInt *NegOne;
-  ConstantInt *MSB;
-
-  if (BitWidth == 64) {
-    Zero      = Builder.getInt64(0);
-    One       = Builder.getInt64(1);
-    NegOne    = ConstantInt::getSigned(DivTy, -1);
-    MSB       = Builder.getInt64(63);
-  } else {
-    assert(BitWidth == 32 && "Unexpected bit width");
-    Zero      = Builder.getInt32(0);
-    One       = Builder.getInt32(1);
-    NegOne    = ConstantInt::getSigned(DivTy, -1);
-    MSB       = Builder.getInt32(31);
-  }
+  ConstantInt *Zero = ConstantInt::get(DivTy, 0);
+  ConstantInt *One = ConstantInt::get(DivTy, 1);
+  ConstantInt *NegOne = ConstantInt::getSigned(DivTy, -1);
+  ConstantInt *MSB = ConstantInt::get(DivTy, BitWidth - 1);
 
   ConstantInt *True = Builder.getTrue();
 
   BasicBlock *IBB = Builder.GetInsertBlock();
   Function *F = IBB->getParent();
   Function *CTLZ = Intrinsic::getDeclaration(F->getParent(), Intrinsic::ctlz,
                                              DivTy);
 
static Value *generateUnsignedDivisionCode(Value *Dividend, Value *Divisor,
   Q_5->addIncoming(RetVal, SpecialCases);
 
   return Q_5;
 }
 
 /// Generate code to calculate the remainder of two integers, replacing Rem with
 /// the generated code. This currently generates code using the udiv expansion,
 /// but future work includes generating more specialized code, e.g. when more
-/// information about the operands are known. Implements both 32bit and 64bit
-/// scalar division.
+/// information about the operands are known.
 ///
 /// Replace Rem with generated code.
 bool llvm::expandRemainder(BinaryOperator *Rem) {
   assert((Rem->getOpcode() == Instruction::SRem ||
           Rem->getOpcode() == Instruction::URem) &&
          "Trying to expand remainder from a non-remainder function");
 
   IRBuilder<> Builder(Rem);
 
   assert(!Rem->getType()->isVectorTy() && "Div over vectors not supported");
-  assert((Rem->getType()->getIntegerBitWidth() == 32 ||
-          Rem->getType()->getIntegerBitWidth() == 64) &&
-         "Div of bitwidth other than 32 or 64 not supported");
 
   // First prepare the sign if it's a signed remainder
   if (Rem->getOpcode() == Instruction::SRem) {
     Value *Remainder = generateSignedRemainderCode(Rem->getOperand(0),
                                                    Rem->getOperand(1), Builder);
 
     // Check whether this is the insert point while Rem is still valid.
     bool IsInsertPoint = Rem->getIterator() == Builder.GetInsertPoint();
bool llvm::expandRemainder(BinaryOperator *Rem) {
   if (BinaryOperator *UDiv = dyn_cast<BinaryOperator>(Builder.GetInsertPoint())) {
     assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?");
     expandDivision(UDiv);
   }
 
   return true;
 }
 
-
 /// Generate code to divide two integers, replacing Div with the generated
 /// code. This currently generates code similarly to compiler-rt's
 /// implementations, but future work includes generating more specialized code
-/// when more information about the operands are known. Implements both
-/// 32bit and 64bit scalar division.
+/// when more information about the operands are known.
 ///
 /// Replace Div with generated code.
 bool llvm::expandDivision(BinaryOperator *Div) {
   assert((Div->getOpcode() == Instruction::SDiv ||
           Div->getOpcode() == Instruction::UDiv) &&
          "Trying to expand division from a non-division function");
 
   IRBuilder<> Builder(Div);
 
   assert(!Div->getType()->isVectorTy() && "Div over vectors not supported");
-  assert((Div->getType()->getIntegerBitWidth() == 32 ||
-          Div->getType()->getIntegerBitWidth() == 64) &&
-         "Div of bitwidth other than 32 or 64 not supported");
 
   // First prepare the sign if it's a signed division
   if (Div->getOpcode() == Instruction::SDiv) {
     // Lower the code to unsigned division, and reset Div to point to the udiv.
     Value *Quotient = generateSignedDivisionCode(Div->getOperand(0),
                                                  Div->getOperand(1), Builder);
 
     // Check whether this is the insert point while Div is still valid.
assert((Rem->getOpcode() == Instruction::SRem ||
           Rem->getOpcode() == Instruction::URem) &&
           "Trying to expand remainder from a non-remainder function");
 
   Type *RemTy = Rem->getType();
   assert(!RemTy->isVectorTy() && "Div over vectors not supported");
 
   unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
 
-  assert(RemTyBitWidth <= 64 && "Div of bitwidth greater than 64 not supported");
-
-  if (RemTyBitWidth == 64)
+  if (RemTyBitWidth >= 64)
     return expandRemainder(Rem);
 
   // If bitwidth smaller than 64 extend inputs, extend output and proceed
   // with 64 bit division.
   IRBuilder<> Builder(Rem);
 
   Value *ExtDividend;
   Value *ExtDivisor;
assert((Div->getOpcode() == Instruction::SDiv ||
           Div->getOpcode() == Instruction::UDiv) &&
           "Trying to expand division from a non-division function");
 
   Type *DivTy = Div->getType();
   assert(!DivTy->isVectorTy() && "Div over vectors not supported");
 
   unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
 
-  assert(DivTyBitWidth <= 64 &&
-         "Div of bitwidth greater than 64 not supported");
-
-  if (DivTyBitWidth == 64)
+  if (DivTyBitWidth >= 64)
     return expandDivision(Div);
 
   // If bitwidth smaller than 64 extend inputs, extend output and proceed
   // with 64 bit division.
   IRBuilder<> Builder(Div);
 
   Value *ExtDividend;
   Value *ExtDivisor;

llvm/test/CodeGen/X86/urem-seteq.ll

; X64-NEXT:    retq
   ret i32 %ret
 }
 
 ; Check illegal types.
 
 ; https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=34366
 define void @ossfuzz34366() {
 ; X86-LABEL: ossfuzz34366:
-; X86:       # %bb.0:
-; X86-NEXT:    movl (%eax), %eax
-; X86-NEXT:    movl %eax, %ecx
-; X86-NEXT:    andl $2147483647, %ecx # imm = 0x7FFFFFFF
-; X86-NEXT:    orl %eax, %ecx
-; X86-NEXT:    sete (%eax)
-; X86-NEXT:    retl
-;
 ; X64-LABEL: ossfuzz34366:
-; X64:       # %bb.0:
-; X64-NEXT:    movq (%rax), %rax
-; X64-NEXT:    movabsq $9223372036854775807, %rcx # imm = 0x7FFFFFFFFFFFFFFF
-; X64-NEXT:    andq %rax, %rcx
-; X64-NEXT:    orq %rax, %rcx
-; X64-NEXT:    sete (%rax)
-; X64-NEXT:    retq
   %L10 = load i448, ptr undef, align 4
   %B18 = urem i448 %L10, -363419362147803445274661903944002267176820680343659030140745099590319644056698961663095525356881782780381260803133088966767300814307328
   %C13 = icmp ule i448 %B18, 0
   store i1 %C13, ptr undef, align 1
   ret void
 }

llvm/test/Transforms/ExpandLargeDivRem/sdiv129.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -expand-large-div-rem < %s | FileCheck %s
+
+define void @sdiv129(i129* %ptr, i129* %out) nounwind {
+; CHECK-LABEL: @sdiv129(
+; CHECK-NEXT:  _udiv-special-cases:
+; CHECK-NEXT:    [[A:%.*]] = load i129, i129* [[PTR:%.*]], align 4
+; CHECK-NEXT:    [[TMP0:%.*]] = ashr i129 [[A]], 128
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i129 [[TMP0]], [[A]]
+; CHECK-NEXT:    [[TMP2:%.*]] = sub i129 [[TMP1]], [[TMP0]]
+; CHECK-NEXT:    [[TMP3:%.*]] = xor i129 0, [[TMP0]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i129 [[TMP2]], 0
+; CHECK-NEXT:    [[TMP5:%.*]] = or i1 false, [[TMP4]]
+; CHECK-NEXT:    [[TMP6:%.*]] = call i129 @llvm.ctlz.i129(i129 3, i1 true)
+; CHECK-NEXT:    [[TMP7:%.*]] = call i129 @llvm.ctlz.i129(i129 [[TMP2]], i1 true)
+; CHECK-NEXT:    [[TMP8:%.*]] = sub i129 [[TMP6]], [[TMP7]]
+; CHECK-NEXT:    [[TMP9:%.*]] = icmp ugt i129 [[TMP8]], 128
+; CHECK-NEXT:    [[TMP10:%.*]] = or i1 [[TMP5]], [[TMP9]]
+; CHECK-NEXT:    [[TMP11:%.*]] = icmp eq i129 [[TMP8]], 128
+; CHECK-NEXT:    [[TMP12:%.*]] = select i1 [[TMP10]], i129 0, i129 [[TMP2]]
+; CHECK-NEXT:    [[TMP13:%.*]] = or i1 [[TMP10]], [[TMP11]]
+; CHECK-NEXT:    br i1 [[TMP13]], label [[UDIV_END:%.*]], label [[UDIV_BB1:%.*]]
+; CHECK:       udiv-loop-exit:
+; CHECK-NEXT:    [[TMP14:%.*]] = phi i129 [ 0, [[UDIV_BB1]] ], [ [[TMP29:%.*]], [[UDIV_DO_WHILE:%.*]] ]
+; CHECK-NEXT:    [[TMP15:%.*]] = phi i129 [ [[TMP37:%.*]], [[UDIV_BB1]] ], [ [[TMP26:%.*]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP16:%.*]] = shl i129 [[TMP15]], 1
+; CHECK-NEXT:    [[TMP17:%.*]] = or i129 [[TMP14]], [[TMP16]]
+; CHECK-NEXT:    br label [[UDIV_END]]
+; CHECK:       udiv-do-while:
+; CHECK-NEXT:    [[TMP18:%.*]] = phi i129 [ 0, [[UDIV_PREHEADER:%.*]] ], [ [[TMP29]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP19:%.*]] = phi i129 [ [[TMP35:%.*]], [[UDIV_PREHEADER]] ], [ [[TMP32:%.*]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP20:%.*]] = phi i129 [ [[TMP34:%.*]], [[UDIV_PREHEADER]] ], [ [[TMP31:%.*]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP21:%.*]] = phi i129 [ [[TMP37]], [[UDIV_PREHEADER]] ], [ [[TMP26]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP22:%.*]] = shl i129 [[TMP20]], 1
+; CHECK-NEXT:    [[TMP23:%.*]] = lshr i129 [[TMP21]], 128
+; CHECK-NEXT:    [[TMP24:%.*]] = or i129 [[TMP22]], [[TMP23]]
+; CHECK-NEXT:    [[TMP25:%.*]] = shl i129 [[TMP21]], 1
+; CHECK-NEXT:    [[TMP26]] = or i129 [[TMP18]], [[TMP25]]
+; CHECK-NEXT:    [[TMP27:%.*]] = sub i129 2, [[TMP24]]
+; CHECK-NEXT:    [[TMP28:%.*]] = ashr i129 [[TMP27]], 128
+; CHECK-NEXT:    [[TMP29]] = and i129 [[TMP28]], 1
+; CHECK-NEXT:    [[TMP30:%.*]] = and i129 [[TMP28]], 3
+; CHECK-NEXT:    [[TMP31]] = sub i129 [[TMP24]], [[TMP30]]
+; CHECK-NEXT:    [[TMP32]] = add i129 [[TMP19]], -1
+; CHECK-NEXT:    [[TMP33:%.*]] = icmp eq i129 [[TMP32]], 0
+; CHECK-NEXT:    br i1 [[TMP33]], label [[UDIV_LOOP_EXIT:%.*]], label [[UDIV_DO_WHILE]]
+; CHECK:       udiv-preheader:
+; CHECK-NEXT:    [[TMP34]] = lshr i129 [[TMP2]], [[TMP35]]
+; CHECK-NEXT:    br label [[UDIV_DO_WHILE]]
+; CHECK:       udiv-bb1:
+; CHECK-NEXT:    [[TMP35]] = add i129 [[TMP8]], 1
+; CHECK-NEXT:    [[TMP36:%.*]] = sub i129 128, [[TMP8]]
+; CHECK-NEXT:    [[TMP37]] = shl i129 [[TMP2]], [[TMP36]]
+; CHECK-NEXT:    [[TMP38:%.*]] = icmp eq i129 [[TMP35]], 0
+; CHECK-NEXT:    br i1 [[TMP38]], label [[UDIV_LOOP_EXIT]], label [[UDIV_PREHEADER]]
+; CHECK:       udiv-end:
+; CHECK-NEXT:    [[TMP39:%.*]] = phi i129 [ [[TMP17]], [[UDIV_LOOP_EXIT]] ], [ [[TMP12]], [[_UDIV_SPECIAL_CASES:%.*]] ]
+; CHECK-NEXT:    [[TMP40:%.*]] = xor i129 [[TMP39]], [[TMP3]]
+; CHECK-NEXT:    [[TMP41:%.*]] = sub i129 [[TMP40]], [[TMP3]]
+; CHECK-NEXT:    store i129 [[TMP41]], i129* [[OUT:%.*]], align 4
+; CHECK-NEXT:    ret void
+;
+  %a = load i129, i129* %ptr
+  %res = sdiv i129 %a, 3
+  store i129 %res, i129* %out
+  ret void
+}

llvm/test/Transforms/ExpandLargeDivRem/srem129.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -expand-large-div-rem < %s | FileCheck %s
+
+define void @test(i129* %ptr, i129* %out) nounwind {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  _udiv-special-cases:
+; CHECK-NEXT:    [[A:%.*]] = load i129, i129* [[PTR:%.*]], align 4
+; CHECK-NEXT:    [[TMP0:%.*]] = ashr i129 [[A]], 128
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i129 [[A]], [[TMP0]]
+; CHECK-NEXT:    [[TMP2:%.*]] = sub i129 [[TMP1]], [[TMP0]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i129 [[TMP2]], 0
+; CHECK-NEXT:    [[TMP4:%.*]] = or i1 false, [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = call i129 @llvm.ctlz.i129(i129 3, i1 true)
+; CHECK-NEXT:    [[TMP6:%.*]] = call i129 @llvm.ctlz.i129(i129 [[TMP2]], i1 true)
+; CHECK-NEXT:    [[TMP7:%.*]] = sub i129 [[TMP5]], [[TMP6]]
+; CHECK-NEXT:    [[TMP8:%.*]] = icmp ugt i129 [[TMP7]], 128
+; CHECK-NEXT:    [[TMP9:%.*]] = or i1 [[TMP4]], [[TMP8]]
+; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i129 [[TMP7]], 128
+; CHECK-NEXT:    [[TMP11:%.*]] = select i1 [[TMP9]], i129 0, i129 [[TMP2]]
+; CHECK-NEXT:    [[TMP12:%.*]] = or i1 [[TMP9]], [[TMP10]]
+; CHECK-NEXT:    br i1 [[TMP12]], label [[UDIV_END:%.*]], label [[UDIV_BB1:%.*]]
+; CHECK:       udiv-loop-exit:
+; CHECK-NEXT:    [[TMP13:%.*]] = phi i129 [ 0, [[UDIV_BB1]] ], [ [[TMP28:%.*]], [[UDIV_DO_WHILE:%.*]] ]
+; CHECK-NEXT:    [[TMP14:%.*]] = phi i129 [ [[TMP36:%.*]], [[UDIV_BB1]] ], [ [[TMP25:%.*]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP15:%.*]] = shl i129 [[TMP14]], 1
+; CHECK-NEXT:    [[TMP16:%.*]] = or i129 [[TMP13]], [[TMP15]]
+; CHECK-NEXT:    br label [[UDIV_END]]
+; CHECK:       udiv-do-while:
+; CHECK-NEXT:    [[TMP17:%.*]] = phi i129 [ 0, [[UDIV_PREHEADER:%.*]] ], [ [[TMP28]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP18:%.*]] = phi i129 [ [[TMP34:%.*]], [[UDIV_PREHEADER]] ], [ [[TMP31:%.*]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP19:%.*]] = phi i129 [ [[TMP33:%.*]], [[UDIV_PREHEADER]] ], [ [[TMP30:%.*]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP20:%.*]] = phi i129 [ [[TMP36]], [[UDIV_PREHEADER]] ], [ [[TMP25]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP21:%.*]] = shl i129 [[TMP19]], 1
+; CHECK-NEXT:    [[TMP22:%.*]] = lshr i129 [[TMP20]], 128
+; CHECK-NEXT:    [[TMP23:%.*]] = or i129 [[TMP21]], [[TMP22]]
+; CHECK-NEXT:    [[TMP24:%.*]] = shl i129 [[TMP20]], 1
+; CHECK-NEXT:    [[TMP25]] = or i129 [[TMP17]], [[TMP24]]
+; CHECK-NEXT:    [[TMP26:%.*]] = sub i129 2, [[TMP23]]
+; CHECK-NEXT:    [[TMP27:%.*]] = ashr i129 [[TMP26]], 128
+; CHECK-NEXT:    [[TMP28]] = and i129 [[TMP27]], 1
+; CHECK-NEXT:    [[TMP29:%.*]] = and i129 [[TMP27]], 3
+; CHECK-NEXT:    [[TMP30]] = sub i129 [[TMP23]], [[TMP29]]
+; CHECK-NEXT:    [[TMP31]] = add i129 [[TMP18]], -1
+; CHECK-NEXT:    [[TMP32:%.*]] = icmp eq i129 [[TMP31]], 0
+; CHECK-NEXT:    br i1 [[TMP32]], label [[UDIV_LOOP_EXIT:%.*]], label [[UDIV_DO_WHILE]]
+; CHECK:       udiv-preheader:
+; CHECK-NEXT:    [[TMP33]] = lshr i129 [[TMP2]], [[TMP34]]
+; CHECK-NEXT:    br label [[UDIV_DO_WHILE]]
+; CHECK:       udiv-bb1:
+; CHECK-NEXT:    [[TMP34]] = add i129 [[TMP7]], 1
+; CHECK-NEXT:    [[TMP35:%.*]] = sub i129 128, [[TMP7]]
+; CHECK-NEXT:    [[TMP36]] = shl i129 [[TMP2]], [[TMP35]]
+; CHECK-NEXT:    [[TMP37:%.*]] = icmp eq i129 [[TMP34]], 0
+; CHECK-NEXT:    br i1 [[TMP37]], label [[UDIV_LOOP_EXIT]], label [[UDIV_PREHEADER]]
+; CHECK:       udiv-end:
+; CHECK-NEXT:    [[TMP38:%.*]] = phi i129 [ [[TMP16]], [[UDIV_LOOP_EXIT]] ], [ [[TMP11]], [[_UDIV_SPECIAL_CASES:%.*]] ]
+; CHECK-NEXT:    [[TMP39:%.*]] = mul i129 3, [[TMP38]]
+; CHECK-NEXT:    [[TMP40:%.*]] = sub i129 [[TMP2]], [[TMP39]]
+; CHECK-NEXT:    [[TMP41:%.*]] = xor i129 [[TMP40]], [[TMP0]]
+; CHECK-NEXT:    [[TMP42:%.*]] = sub i129 [[TMP41]], [[TMP0]]
+; CHECK-NEXT:    store i129 [[TMP42]], i129* [[OUT:%.*]], align 4
+; CHECK-NEXT:    ret void
+;
+  %a = load i129, i129* %ptr
+  %res = srem i129 %a, 3
+  store i129 %res, i129* %out
+  ret void
+}

llvm/test/Transforms/ExpandLargeDivRem/udiv129.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -expand-large-div-rem < %s | FileCheck %s
+
+define void @test(i129* %ptr, i129* %out) nounwind {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  _udiv-special-cases:
+; CHECK-NEXT:    [[A:%.*]] = load i129, i129* [[PTR:%.*]], align 4
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i129 [[A]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = or i1 false, [[TMP0]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call i129 @llvm.ctlz.i129(i129 3, i1 true)
+; CHECK-NEXT:    [[TMP3:%.*]] = call i129 @llvm.ctlz.i129(i129 [[A]], i1 true)
+; CHECK-NEXT:    [[TMP4:%.*]] = sub i129 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ugt i129 [[TMP4]], 128
+; CHECK-NEXT:    [[TMP6:%.*]] = or i1 [[TMP1]], [[TMP5]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i129 [[TMP4]], 128
+; CHECK-NEXT:    [[TMP8:%.*]] = select i1 [[TMP6]], i129 0, i129 [[A]]
+; CHECK-NEXT:    [[TMP9:%.*]] = or i1 [[TMP6]], [[TMP7]]
+; CHECK-NEXT:    br i1 [[TMP9]], label [[UDIV_END:%.*]], label [[UDIV_BB1:%.*]]
+; CHECK:       udiv-loop-exit:
+; CHECK-NEXT:    [[TMP10:%.*]] = phi i129 [ 0, [[UDIV_BB1]] ], [ [[TMP25:%.*]], [[UDIV_DO_WHILE:%.*]] ]
+; CHECK-NEXT:    [[TMP11:%.*]] = phi i129 [ [[TMP33:%.*]], [[UDIV_BB1]] ], [ [[TMP22:%.*]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP12:%.*]] = shl i129 [[TMP11]], 1
+; CHECK-NEXT:    [[TMP13:%.*]] = or i129 [[TMP10]], [[TMP12]]
+; CHECK-NEXT:    br label [[UDIV_END]]
+; CHECK:       udiv-do-while:
+; CHECK-NEXT:    [[TMP14:%.*]] = phi i129 [ 0, [[UDIV_PREHEADER:%.*]] ], [ [[TMP25]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP15:%.*]] = phi i129 [ [[TMP31:%.*]], [[UDIV_PREHEADER]] ], [ [[TMP28:%.*]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP16:%.*]] = phi i129 [ [[TMP30:%.*]], [[UDIV_PREHEADER]] ], [ [[TMP27:%.*]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP17:%.*]] = phi i129 [ [[TMP33]], [[UDIV_PREHEADER]] ], [ [[TMP22]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP18:%.*]] = shl i129 [[TMP16]], 1
+; CHECK-NEXT:    [[TMP19:%.*]] = lshr i129 [[TMP17]], 128
+; CHECK-NEXT:    [[TMP20:%.*]] = or i129 [[TMP18]], [[TMP19]]
+; CHECK-NEXT:    [[TMP21:%.*]] = shl i129 [[TMP17]], 1
+; CHECK-NEXT:    [[TMP22]] = or i129 [[TMP14]], [[TMP21]]
+; CHECK-NEXT:    [[TMP23:%.*]] = sub i129 2, [[TMP20]]
+; CHECK-NEXT:    [[TMP24:%.*]] = ashr i129 [[TMP23]], 128
+; CHECK-NEXT:    [[TMP25]] = and i129 [[TMP24]], 1
+; CHECK-NEXT:    [[TMP26:%.*]] = and i129 [[TMP24]], 3
+; CHECK-NEXT:    [[TMP27]] = sub i129 [[TMP20]], [[TMP26]]
+; CHECK-NEXT:    [[TMP28]] = add i129 [[TMP15]], -1
+; CHECK-NEXT:    [[TMP29:%.*]] = icmp eq i129 [[TMP28]], 0
+; CHECK-NEXT:    br i1 [[TMP29]], label [[UDIV_LOOP_EXIT:%.*]], label [[UDIV_DO_WHILE]]
+; CHECK:       udiv-preheader:
+; CHECK-NEXT:    [[TMP30]] = lshr i129 [[A]], [[TMP31]]
+; CHECK-NEXT:    br label [[UDIV_DO_WHILE]]
+; CHECK:       udiv-bb1:
+; CHECK-NEXT:    [[TMP31]] = add i129 [[TMP4]], 1
+; CHECK-NEXT:    [[TMP32:%.*]] = sub i129 128, [[TMP4]]
+; CHECK-NEXT:    [[TMP33]] = shl i129 [[A]], [[TMP32]]
+; CHECK-NEXT:    [[TMP34:%.*]] = icmp eq i129 [[TMP31]], 0
+; CHECK-NEXT:    br i1 [[TMP34]], label [[UDIV_LOOP_EXIT]], label [[UDIV_PREHEADER]]
+; CHECK:       udiv-end:
+; CHECK-NEXT:    [[TMP35:%.*]] = phi i129 [ [[TMP13]], [[UDIV_LOOP_EXIT]] ], [ [[TMP8]], [[_UDIV_SPECIAL_CASES:%.*]] ]
+; CHECK-NEXT:    store i129 [[TMP35]], i129* [[OUT:%.*]], align 4
+; CHECK-NEXT:    ret void
+;
+  %a = load i129, i129* %ptr
+  %res = udiv i129 %a, 3
+  store i129 %res, i129* %out
+  ret void
+}

llvm/test/Transforms/ExpandLargeDivRem/urem129.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -expand-large-div-rem < %s | FileCheck %s
+
+define void @test(i129* %ptr, i129* %out) nounwind {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  _udiv-special-cases:
+; CHECK-NEXT:    [[A:%.*]] = load i129, i129* [[PTR:%.*]], align 4
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i129 [[A]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = or i1 false, [[TMP0]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call i129 @llvm.ctlz.i129(i129 3, i1 true)
+; CHECK-NEXT:    [[TMP3:%.*]] = call i129 @llvm.ctlz.i129(i129 [[A]], i1 true)
+; CHECK-NEXT:    [[TMP4:%.*]] = sub i129 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ugt i129 [[TMP4]], 128
+; CHECK-NEXT:    [[TMP6:%.*]] = or i1 [[TMP1]], [[TMP5]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i129 [[TMP4]], 128
+; CHECK-NEXT:    [[TMP8:%.*]] = select i1 [[TMP6]], i129 0, i129 [[A]]
+; CHECK-NEXT:    [[TMP9:%.*]] = or i1 [[TMP6]], [[TMP7]]
+; CHECK-NEXT:    br i1 [[TMP9]], label [[UDIV_END:%.*]], label [[UDIV_BB1:%.*]]
+; CHECK:       udiv-loop-exit:
+; CHECK-NEXT:    [[TMP10:%.*]] = phi i129 [ 0, [[UDIV_BB1]] ], [ [[TMP25:%.*]], [[UDIV_DO_WHILE:%.*]] ]
+; CHECK-NEXT:    [[TMP11:%.*]] = phi i129 [ [[TMP33:%.*]], [[UDIV_BB1]] ], [ [[TMP22:%.*]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP12:%.*]] = shl i129 [[TMP11]], 1
+; CHECK-NEXT:    [[TMP13:%.*]] = or i129 [[TMP10]], [[TMP12]]
+; CHECK-NEXT:    br label [[UDIV_END]]
+; CHECK:       udiv-do-while:
+; CHECK-NEXT:    [[TMP14:%.*]] = phi i129 [ 0, [[UDIV_PREHEADER:%.*]] ], [ [[TMP25]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP15:%.*]] = phi i129 [ [[TMP31:%.*]], [[UDIV_PREHEADER]] ], [ [[TMP28:%.*]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP16:%.*]] = phi i129 [ [[TMP30:%.*]], [[UDIV_PREHEADER]] ], [ [[TMP27:%.*]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP17:%.*]] = phi i129 [ [[TMP33]], [[UDIV_PREHEADER]] ], [ [[TMP22]], [[UDIV_DO_WHILE]] ]
+; CHECK-NEXT:    [[TMP18:%.*]] = shl i129 [[TMP16]], 1
+; CHECK-NEXT:    [[TMP19:%.*]] = lshr i129 [[TMP17]], 128
+; CHECK-NEXT:    [[TMP20:%.*]] = or i129 [[TMP18]], [[TMP19]]
+; CHECK-NEXT:    [[TMP21:%.*]] = shl i129 [[TMP17]], 1
+; CHECK-NEXT:    [[TMP22]] = or i129 [[TMP14]], [[TMP21]]
+; CHECK-NEXT:    [[TMP23:%.*]] = sub i129 2, [[TMP20]]
+; CHECK-NEXT:    [[TMP24:%.*]] = ashr i129 [[TMP23]], 128
+; CHECK-NEXT:    [[TMP25]] = and i129 [[TMP24]], 1
+; CHECK-NEXT:    [[TMP26:%.*]] = and i129 [[TMP24]], 3
+; CHECK-NEXT:    [[TMP27]] = sub i129 [[TMP20]], [[TMP26]]
+; CHECK-NEXT:    [[TMP28]] = add i129 [[TMP15]], -1
+; CHECK-NEXT:    [[TMP29:%.*]] = icmp eq i129 [[TMP28]], 0
+; CHECK-NEXT:    br i1 [[TMP29]], label [[UDIV_LOOP_EXIT:%.*]], label [[UDIV_DO_WHILE]]
+; CHECK:       udiv-preheader:
+; CHECK-NEXT:    [[TMP30]] = lshr i129 [[A]], [[TMP31]]
+; CHECK-NEXT:    br label [[UDIV_DO_WHILE]]
+; CHECK:       udiv-bb1:
+; CHECK-NEXT:    [[TMP31]] = add i129 [[TMP4]], 1
+; CHECK-NEXT:    [[TMP32:%.*]] = sub i129 128, [[TMP4]]
+; CHECK-NEXT:    [[TMP33]] = shl i129 [[A]], [[TMP32]]
+; CHECK-NEXT:    [[TMP34:%.*]] = icmp eq i129 [[TMP31]], 0
+; CHECK-NEXT:    br i1 [[TMP34]], label [[UDIV_LOOP_EXIT]], label [[UDIV_PREHEADER]]
+; CHECK:       udiv-end:
+; CHECK-NEXT:    [[TMP35:%.*]] = phi i129 [ [[TMP13]], [[UDIV_LOOP_EXIT]] ], [ [[TMP8]], [[_UDIV_SPECIAL_CASES:%.*]] ]
+; CHECK-NEXT:    [[TMP36:%.*]] = mul i129 3, [[TMP35]]
+; CHECK-NEXT:    [[TMP37:%.*]] = sub i129 [[A]], [[TMP36]]
+; CHECK-NEXT:    store i129 [[TMP37]], i129* [[OUT:%.*]], align 4
+; CHECK-NEXT:    ret void
+;
+  %a = load i129, i129* %ptr
+  %res = urem i129 %a, 3
+  store i129 %res, i129* %out
+  ret void
+}

llvm/tools/opt/opt.cpp

std::vector<StringRef> PassNameExact = {
       "expand-reductions",    "indirectbr-expand",
       "generic-to-nvvm",      "expandmemcmp",
       "loop-reduce",          "lower-amx-type",
       "pre-amx-config",       "lower-amx-intrinsics",
       "polyhedral-info",      "print-polyhedral-info",
       "replace-with-veclib",  "jmc-instrument",
       "dot-regions",          "dot-regions-only",
       "view-regions",         "view-regions-only",
-      "select-optimize"};
+      "select-optimize",      "expand-large-div-rem"};
   for (const auto &P : PassNamePrefix)
     if (Pass.startswith(P))
       return true;
   for (const auto &P : PassNameContain)
     if (Pass.contains(P))
       return true;
   return llvm::is_contained(PassNameExact, Pass);
 }
int main(int argc, char **argv) {
   initializeAnalysis(Registry);
   initializeTransformUtils(Registry);
   initializeInstCombine(Registry);
   initializeAggressiveInstCombine(Registry);
   initializeInstrumentation(Registry);
   initializeTarget(Registry);
   // For codegen passes, only passes that do IR to IR transformation are
   // supported.
+  initializeExpandLargeDivRemLegacyPassPass(Registry);
   initializeExpandMemCmpPassPass(Registry);
   initializeScalarizeMaskedMemIntrinLegacyPassPass(Registry);
   initializeSelectOptimizePass(Registry);
   initializeCodeGenPreparePass(Registry);
   initializeAtomicExpandPass(Registry);
   initializeRewriteSymbolsLegacyPassPass(Registry);
   initializeWinEHPreparePass(Registry);
   initializeDwarfEHPrepareLegacyPassPass(Registry);