Restoring authorship annotation for <orivej@yandex-team.ru>. Commit 2 of 2.

1 files changed, 673 insertions, 673 deletions

diff --git a/contrib/libs/llvm12/lib/Transforms/Utils/IntegerDivision.cpp b/contrib/libs/llvm12/lib/Transforms/Utils/IntegerDivision.cpp
index ffb56f2fbe..9082049c82 100644
--- a/contrib/libs/llvm12/lib/Transforms/Utils/IntegerDivision.cpp
+++ b/contrib/libs/llvm12/lib/Transforms/Utils/IntegerDivision.cpp
@@ -1,673 +1,673 @@
-//===-- IntegerDivision.cpp - Expand integer division ---------------------===// 
-// 
-// 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 file contains an implementation of 32bit and 64bit scalar integer 
-// division for targets that don't have native support. It's largely derived 
-// from compiler-rt's implementations of __udivsi3 and __udivmoddi4, 
-// but hand-tuned for targets that prefer less control flow. 
-// 
-//===----------------------------------------------------------------------===// 
- 
-#include "llvm/Transforms/Utils/IntegerDivision.h" 
-#include "llvm/IR/Function.h" 
-#include "llvm/IR/IRBuilder.h" 
-#include "llvm/IR/Instructions.h" 
-#include "llvm/IR/Intrinsics.h" 
-#include <utility> 
- 
-using namespace llvm; 
- 
-#define DEBUG_TYPE "integer-division" 
- 
-/// Generate code to compute the remainder of two signed integers. Returns the 
-/// 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); 
-  } 
- 
-  // 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 
-  // ;   %u_dividend   = sub i32 %dvd_xor, %dividend_sgn 
-  // ;   %u_divisor    = sub i32 %dvs_xor, %divisor_sgn 
-  // ;   %urem         = urem i32 %dividend, %divisor 
-  // ;   %xored        = xor i32 %urem, %dividend_sgn 
-  // ;   %srem         = sub i32 %xored, %dividend_sgn 
-  Value *DividendSign = Builder.CreateAShr(Dividend, Shift); 
-  Value *DivisorSign  = Builder.CreateAShr(Divisor, Shift); 
-  Value *DvdXor       = Builder.CreateXor(Dividend, DividendSign); 
-  Value *DvsXor       = Builder.CreateXor(Divisor, DivisorSign); 
-  Value *UDividend    = Builder.CreateSub(DvdXor, DividendSign); 
-  Value *UDivisor     = Builder.CreateSub(DvsXor, DivisorSign); 
-  Value *URem         = Builder.CreateURem(UDividend, UDivisor); 
-  Value *Xored        = Builder.CreateXor(URem, DividendSign); 
-  Value *SRem         = Builder.CreateSub(Xored, DividendSign); 
- 
-  if (Instruction *URemInst = dyn_cast<Instruction>(URem)) 
-    Builder.SetInsertPoint(URemInst); 
- 
-  return SRem; 
-} 
- 
- 
-/// Generate code to compute the remainder of two unsigned integers. Returns the 
-/// remainder. Builder's insert point should be pointing where the caller wants 
-/// code generated, e.g. at the urem 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 *generatedUnsignedRemainderCode(Value *Dividend, Value *Divisor, 
-                                             IRBuilder<> &Builder) { 
-  // Remainder = Dividend - Quotient*Divisor 
- 
-  // Following instructions are generated for both i32 and i64 
- 
-  // ;   %quotient  = udiv i32 %dividend, %divisor 
-  // ;   %product   = mul i32 %divisor, %quotient 
-  // ;   %remainder = sub i32 %dividend, %product 
-  Value *Quotient  = Builder.CreateUDiv(Dividend, Divisor); 
-  Value *Product   = Builder.CreateMul(Divisor, Quotient); 
-  Value *Remainder = Builder.CreateSub(Dividend, Product); 
- 
-  if (Instruction *UDiv = dyn_cast<Instruction>(Quotient)) 
-    Builder.SetInsertPoint(UDiv); 
- 
-  return Remainder; 
-} 
- 
-/// Generate code to divide two signed integers. Returns the quotient, rounded 
-/// towards 0. Builder's insert point should be pointing where the caller wants 
-/// 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); 
-  } 
- 
-  // 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 
-  // ;   %tmp3   = xor i32 %tmp1, %divisor 
-  // ;   %u_dvsr = sub nsw i32 %tmp3, %tmp1 
-  // ;   %q_sgn  = xor i32 %tmp1, %tmp 
-  // ;   %q_mag  = udiv i32 %u_dvnd, %u_dvsr 
-  // ;   %tmp4   = xor i32 %q_mag, %q_sgn 
-  // ;   %q      = sub i32 %tmp4, %q_sgn 
-  Value *Tmp    = Builder.CreateAShr(Dividend, Shift); 
-  Value *Tmp1   = Builder.CreateAShr(Divisor, Shift); 
-  Value *Tmp2   = Builder.CreateXor(Tmp, Dividend); 
-  Value *U_Dvnd = Builder.CreateSub(Tmp2, Tmp); 
-  Value *Tmp3   = Builder.CreateXor(Tmp1, Divisor); 
-  Value *U_Dvsr = Builder.CreateSub(Tmp3, Tmp1); 
-  Value *Q_Sgn  = Builder.CreateXor(Tmp1, Tmp); 
-  Value *Q_Mag  = Builder.CreateUDiv(U_Dvnd, U_Dvsr); 
-  Value *Tmp4   = Builder.CreateXor(Q_Mag, Q_Sgn); 
-  Value *Q      = Builder.CreateSub(Tmp4, Q_Sgn); 
- 
-  if (Instruction *UDiv = dyn_cast<Instruction>(Q_Mag)) 
-    Builder.SetInsertPoint(UDiv); 
- 
-  return Q; 
-} 
- 
-/// Generates code to divide two unsigned scalar 32-bit or 64-bit integers. 
-/// Returns the quotient, rounded towards 0. Builder's insert point should 
-/// point where the caller wants code generated, e.g. at the udiv instruction. 
-static Value *generateUnsignedDivisionCode(Value *Dividend, Value *Divisor, 
-                                           IRBuilder<> &Builder) { 
-  // 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 *True = Builder.getTrue(); 
- 
-  BasicBlock *IBB = Builder.GetInsertBlock(); 
-  Function *F = IBB->getParent(); 
-  Function *CTLZ = Intrinsic::getDeclaration(F->getParent(), Intrinsic::ctlz, 
-                                             DivTy); 
- 
-  // Our CFG is going to look like: 
-  // +---------------------+ 
-  // | special-cases       | 
-  // |   ...               | 
-  // +---------------------+ 
-  //  |       | 
-  //  |   +----------+ 
-  //  |   |  bb1     | 
-  //  |   |  ...     | 
-  //  |   +----------+ 
-  //  |    |      | 
-  //  |    |  +------------+ 
-  //  |    |  |  preheader | 
-  //  |    |  |  ...       | 
-  //  |    |  +------------+ 
-  //  |    |      | 
-  //  |    |      |      +---+ 
-  //  |    |      |      |   | 
-  //  |    |  +------------+ | 
-  //  |    |  |  do-while  | | 
-  //  |    |  |  ...       | | 
-  //  |    |  +------------+ | 
-  //  |    |      |      |   | 
-  //  |   +-----------+  +---+ 
-  //  |   | loop-exit | 
-  //  |   |  ...      | 
-  //  |   +-----------+ 
-  //  |     | 
-  // +-------+ 
-  // | ...   | 
-  // | end   | 
-  // +-------+ 
-  BasicBlock *SpecialCases = Builder.GetInsertBlock(); 
-  SpecialCases->setName(Twine(SpecialCases->getName(), "_udiv-special-cases")); 
-  BasicBlock *End = SpecialCases->splitBasicBlock(Builder.GetInsertPoint(), 
-                                                  "udiv-end"); 
-  BasicBlock *LoopExit  = BasicBlock::Create(Builder.getContext(), 
-                                             "udiv-loop-exit", F, End); 
-  BasicBlock *DoWhile   = BasicBlock::Create(Builder.getContext(), 
-                                             "udiv-do-while", F, End); 
-  BasicBlock *Preheader = BasicBlock::Create(Builder.getContext(), 
-                                             "udiv-preheader", F, End); 
-  BasicBlock *BB1       = BasicBlock::Create(Builder.getContext(), 
-                                             "udiv-bb1", F, End); 
- 
-  // We'll be overwriting the terminator to insert our extra blocks 
-  SpecialCases->getTerminator()->eraseFromParent(); 
- 
-  // Same instructions are generated for both i32 (msb 31) and i64 (msb 63). 
- 
-  // First off, check for special cases: dividend or divisor is zero, divisor 
-  // is greater than dividend, and divisor is 1. 
-  // ; special-cases: 
-  // ;   %ret0_1      = icmp eq i32 %divisor, 0 
-  // ;   %ret0_2      = icmp eq i32 %dividend, 0 
-  // ;   %ret0_3      = or i1 %ret0_1, %ret0_2 
-  // ;   %tmp0        = tail call i32 @llvm.ctlz.i32(i32 %divisor, i1 true) 
-  // ;   %tmp1        = tail call i32 @llvm.ctlz.i32(i32 %dividend, i1 true) 
-  // ;   %sr          = sub nsw i32 %tmp0, %tmp1 
-  // ;   %ret0_4      = icmp ugt i32 %sr, 31 
-  // ;   %ret0        = or i1 %ret0_3, %ret0_4 
-  // ;   %retDividend = icmp eq i32 %sr, 31 
-  // ;   %retVal      = select i1 %ret0, i32 0, i32 %dividend 
-  // ;   %earlyRet    = or i1 %ret0, %retDividend 
-  // ;   br i1 %earlyRet, label %end, label %bb1 
-  Builder.SetInsertPoint(SpecialCases); 
-  Value *Ret0_1      = Builder.CreateICmpEQ(Divisor, Zero); 
-  Value *Ret0_2      = Builder.CreateICmpEQ(Dividend, Zero); 
-  Value *Ret0_3      = Builder.CreateOr(Ret0_1, Ret0_2); 
-  Value *Tmp0 = Builder.CreateCall(CTLZ, {Divisor, True}); 
-  Value *Tmp1 = Builder.CreateCall(CTLZ, {Dividend, True}); 
-  Value *SR          = Builder.CreateSub(Tmp0, Tmp1); 
-  Value *Ret0_4      = Builder.CreateICmpUGT(SR, MSB); 
-  Value *Ret0        = Builder.CreateOr(Ret0_3, Ret0_4); 
-  Value *RetDividend = Builder.CreateICmpEQ(SR, MSB); 
-  Value *RetVal      = Builder.CreateSelect(Ret0, Zero, Dividend); 
-  Value *EarlyRet    = Builder.CreateOr(Ret0, RetDividend); 
-  Builder.CreateCondBr(EarlyRet, End, BB1); 
- 
-  // ; bb1:                                             ; preds = %special-cases 
-  // ;   %sr_1     = add i32 %sr, 1 
-  // ;   %tmp2     = sub i32 31, %sr 
-  // ;   %q        = shl i32 %dividend, %tmp2 
-  // ;   %skipLoop = icmp eq i32 %sr_1, 0 
-  // ;   br i1 %skipLoop, label %loop-exit, label %preheader 
-  Builder.SetInsertPoint(BB1); 
-  Value *SR_1     = Builder.CreateAdd(SR, One); 
-  Value *Tmp2     = Builder.CreateSub(MSB, SR); 
-  Value *Q        = Builder.CreateShl(Dividend, Tmp2); 
-  Value *SkipLoop = Builder.CreateICmpEQ(SR_1, Zero); 
-  Builder.CreateCondBr(SkipLoop, LoopExit, Preheader); 
- 
-  // ; preheader:                                           ; preds = %bb1 
-  // ;   %tmp3 = lshr i32 %dividend, %sr_1 
-  // ;   %tmp4 = add i32 %divisor, -1 
-  // ;   br label %do-while 
-  Builder.SetInsertPoint(Preheader); 
-  Value *Tmp3 = Builder.CreateLShr(Dividend, SR_1); 
-  Value *Tmp4 = Builder.CreateAdd(Divisor, NegOne); 
-  Builder.CreateBr(DoWhile); 
- 
-  // ; do-while:                                 ; preds = %do-while, %preheader 
-  // ;   %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ] 
-  // ;   %sr_3    = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ] 
-  // ;   %r_1     = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ] 
-  // ;   %q_2     = phi i32 [ %q, %preheader ], [ %q_1, %do-while ] 
-  // ;   %tmp5  = shl i32 %r_1, 1 
-  // ;   %tmp6  = lshr i32 %q_2, 31 
-  // ;   %tmp7  = or i32 %tmp5, %tmp6 
-  // ;   %tmp8  = shl i32 %q_2, 1 
-  // ;   %q_1   = or i32 %carry_1, %tmp8 
-  // ;   %tmp9  = sub i32 %tmp4, %tmp7 
-  // ;   %tmp10 = ashr i32 %tmp9, 31 
-  // ;   %carry = and i32 %tmp10, 1 
-  // ;   %tmp11 = and i32 %tmp10, %divisor 
-  // ;   %r     = sub i32 %tmp7, %tmp11 
-  // ;   %sr_2  = add i32 %sr_3, -1 
-  // ;   %tmp12 = icmp eq i32 %sr_2, 0 
-  // ;   br i1 %tmp12, label %loop-exit, label %do-while 
-  Builder.SetInsertPoint(DoWhile); 
-  PHINode *Carry_1 = Builder.CreatePHI(DivTy, 2); 
-  PHINode *SR_3    = Builder.CreatePHI(DivTy, 2); 
-  PHINode *R_1     = Builder.CreatePHI(DivTy, 2); 
-  PHINode *Q_2     = Builder.CreatePHI(DivTy, 2); 
-  Value *Tmp5  = Builder.CreateShl(R_1, One); 
-  Value *Tmp6  = Builder.CreateLShr(Q_2, MSB); 
-  Value *Tmp7  = Builder.CreateOr(Tmp5, Tmp6); 
-  Value *Tmp8  = Builder.CreateShl(Q_2, One); 
-  Value *Q_1   = Builder.CreateOr(Carry_1, Tmp8); 
-  Value *Tmp9  = Builder.CreateSub(Tmp4, Tmp7); 
-  Value *Tmp10 = Builder.CreateAShr(Tmp9, MSB); 
-  Value *Carry = Builder.CreateAnd(Tmp10, One); 
-  Value *Tmp11 = Builder.CreateAnd(Tmp10, Divisor); 
-  Value *R     = Builder.CreateSub(Tmp7, Tmp11); 
-  Value *SR_2  = Builder.CreateAdd(SR_3, NegOne); 
-  Value *Tmp12 = Builder.CreateICmpEQ(SR_2, Zero); 
-  Builder.CreateCondBr(Tmp12, LoopExit, DoWhile); 
- 
-  // ; loop-exit:                                      ; preds = %do-while, %bb1 
-  // ;   %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ] 
-  // ;   %q_3     = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ] 
-  // ;   %tmp13 = shl i32 %q_3, 1 
-  // ;   %q_4   = or i32 %carry_2, %tmp13 
-  // ;   br label %end 
-  Builder.SetInsertPoint(LoopExit); 
-  PHINode *Carry_2 = Builder.CreatePHI(DivTy, 2); 
-  PHINode *Q_3     = Builder.CreatePHI(DivTy, 2); 
-  Value *Tmp13 = Builder.CreateShl(Q_3, One); 
-  Value *Q_4   = Builder.CreateOr(Carry_2, Tmp13); 
-  Builder.CreateBr(End); 
- 
-  // ; end:                                 ; preds = %loop-exit, %special-cases 
-  // ;   %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ] 
-  // ;   ret i32 %q_5 
-  Builder.SetInsertPoint(End, End->begin()); 
-  PHINode *Q_5 = Builder.CreatePHI(DivTy, 2); 
- 
-  // Populate the Phis, since all values have now been created. Our Phis were: 
-  // ;   %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ] 
-  Carry_1->addIncoming(Zero, Preheader); 
-  Carry_1->addIncoming(Carry, DoWhile); 
-  // ;   %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ] 
-  SR_3->addIncoming(SR_1, Preheader); 
-  SR_3->addIncoming(SR_2, DoWhile); 
-  // ;   %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ] 
-  R_1->addIncoming(Tmp3, Preheader); 
-  R_1->addIncoming(R, DoWhile); 
-  // ;   %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ] 
-  Q_2->addIncoming(Q, Preheader); 
-  Q_2->addIncoming(Q_1, DoWhile); 
-  // ;   %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ] 
-  Carry_2->addIncoming(Zero, BB1); 
-  Carry_2->addIncoming(Carry, DoWhile); 
-  // ;   %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ] 
-  Q_3->addIncoming(Q, BB1); 
-  Q_3->addIncoming(Q_1, DoWhile); 
-  // ;   %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ] 
-  Q_5->addIncoming(Q_4, LoopExit); 
-  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. 
-/// 
-/// 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(); 
-    Rem->replaceAllUsesWith(Remainder); 
-    Rem->dropAllReferences(); 
-    Rem->eraseFromParent(); 
- 
-    // If we didn't actually generate an urem instruction, we're done 
-    // This happens for example if the input were constant. In this case the 
-    // Builder insertion point was unchanged 
-    if (IsInsertPoint) 
-      return true; 
- 
-    BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint()); 
-    Rem = BO; 
-  } 
- 
-  Value *Remainder = generatedUnsignedRemainderCode(Rem->getOperand(0), 
-                                                    Rem->getOperand(1), 
-                                                    Builder); 
- 
-  Rem->replaceAllUsesWith(Remainder); 
-  Rem->dropAllReferences(); 
-  Rem->eraseFromParent(); 
- 
-  // Expand the udiv 
-  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. 
-/// 
-/// 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. 
-    bool IsInsertPoint = Div->getIterator() == Builder.GetInsertPoint(); 
-    Div->replaceAllUsesWith(Quotient); 
-    Div->dropAllReferences(); 
-    Div->eraseFromParent(); 
- 
-    // If we didn't actually generate an udiv instruction, we're done 
-    // This happens for example if the input were constant. In this case the 
-    // Builder insertion point was unchanged 
-    if (IsInsertPoint) 
-      return true; 
- 
-    BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint()); 
-    Div = BO; 
-  } 
- 
-  // Insert the unsigned division code 
-  Value *Quotient = generateUnsignedDivisionCode(Div->getOperand(0), 
-                                                 Div->getOperand(1), 
-                                                 Builder); 
-  Div->replaceAllUsesWith(Quotient); 
-  Div->dropAllReferences(); 
-  Div->eraseFromParent(); 
- 
-  return true; 
-} 
- 
-/// Generate code to compute the remainder of two integers of bitwidth up to 
-/// 32 bits. Uses the above routines and extends the inputs/truncates the 
-/// outputs to operate in 32 bits; that is, these routines are good for targets 
-/// that have no or very little suppport for smaller than 32 bit integer 
-/// arithmetic. 
-/// 
-/// Replace Rem with emulation code. 
-bool llvm::expandRemainderUpTo32Bits(BinaryOperator *Rem) { 
-  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 <= 32 && 
-         "Div of bitwidth greater than 32 not supported"); 
- 
-  if (RemTyBitWidth == 32) 
-    return expandRemainder(Rem); 
- 
-  // If bitwidth smaller than 32 extend inputs, extend output and proceed 
-  // with 32 bit division. 
-  IRBuilder<> Builder(Rem); 
- 
-  Value *ExtDividend; 
-  Value *ExtDivisor; 
-  Value *ExtRem; 
-  Value *Trunc; 
-  Type *Int32Ty = Builder.getInt32Ty(); 
- 
-  if (Rem->getOpcode() == Instruction::SRem) { 
-    ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int32Ty); 
-    ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int32Ty); 
-    ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor); 
-  } else { 
-    ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int32Ty); 
-    ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int32Ty); 
-    ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor); 
-  } 
-  Trunc = Builder.CreateTrunc(ExtRem, RemTy); 
- 
-  Rem->replaceAllUsesWith(Trunc); 
-  Rem->dropAllReferences(); 
-  Rem->eraseFromParent(); 
- 
-  return expandRemainder(cast<BinaryOperator>(ExtRem)); 
-} 
- 
-/// Generate code to compute the remainder of two integers of bitwidth up to 
-/// 64 bits. Uses the above routines and extends the inputs/truncates the 
-/// outputs to operate in 64 bits. 
-/// 
-/// Replace Rem with emulation code. 
-bool llvm::expandRemainderUpTo64Bits(BinaryOperator *Rem) { 
-  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) 
-    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; 
-  Value *ExtRem; 
-  Value *Trunc; 
-  Type *Int64Ty = Builder.getInt64Ty(); 
- 
-  if (Rem->getOpcode() == Instruction::SRem) { 
-    ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int64Ty); 
-    ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int64Ty); 
-    ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor); 
-  } else { 
-    ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int64Ty); 
-    ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int64Ty); 
-    ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor); 
-  } 
-  Trunc = Builder.CreateTrunc(ExtRem, RemTy); 
- 
-  Rem->replaceAllUsesWith(Trunc); 
-  Rem->dropAllReferences(); 
-  Rem->eraseFromParent(); 
- 
-  return expandRemainder(cast<BinaryOperator>(ExtRem)); 
-} 
- 
-/// Generate code to divide two integers of bitwidth up to 32 bits. Uses the 
-/// above routines and extends the inputs/truncates the outputs to operate 
-/// in 32 bits; that is, these routines are good for targets that have no 
-/// or very little support for smaller than 32 bit integer arithmetic. 
-/// 
-/// Replace Div with emulation code. 
-bool llvm::expandDivisionUpTo32Bits(BinaryOperator *Div) { 
-  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 <= 32 && "Div of bitwidth greater than 32 not supported"); 
- 
-  if (DivTyBitWidth == 32) 
-    return expandDivision(Div); 
- 
-  // If bitwidth smaller than 32 extend inputs, extend output and proceed 
-  // with 32 bit division. 
-  IRBuilder<> Builder(Div); 
- 
-  Value *ExtDividend; 
-  Value *ExtDivisor; 
-  Value *ExtDiv; 
-  Value *Trunc; 
-  Type *Int32Ty = Builder.getInt32Ty(); 
- 
-  if (Div->getOpcode() == Instruction::SDiv) { 
-    ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int32Ty); 
-    ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int32Ty); 
-    ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor); 
-  } else { 
-    ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int32Ty); 
-    ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int32Ty); 
-    ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor); 
-  } 
-  Trunc = Builder.CreateTrunc(ExtDiv, DivTy); 
- 
-  Div->replaceAllUsesWith(Trunc); 
-  Div->dropAllReferences(); 
-  Div->eraseFromParent(); 
- 
-  return expandDivision(cast<BinaryOperator>(ExtDiv)); 
-} 
- 
-/// Generate code to divide two integers of bitwidth up to 64 bits. Uses the 
-/// above routines and extends the inputs/truncates the outputs to operate 
-/// in 64 bits. 
-/// 
-/// Replace Div with emulation code. 
-bool llvm::expandDivisionUpTo64Bits(BinaryOperator *Div) { 
-  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) 
-    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; 
-  Value *ExtDiv; 
-  Value *Trunc; 
-  Type *Int64Ty = Builder.getInt64Ty(); 
- 
-  if (Div->getOpcode() == Instruction::SDiv) { 
-    ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int64Ty); 
-    ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int64Ty); 
-    ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor); 
-  } else { 
-    ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int64Ty); 
-    ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int64Ty); 
-    ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor); 
-  } 
-  Trunc = Builder.CreateTrunc(ExtDiv, DivTy); 
- 
-  Div->replaceAllUsesWith(Trunc); 
-  Div->dropAllReferences(); 
-  Div->eraseFromParent(); 
- 
-  return expandDivision(cast<BinaryOperator>(ExtDiv)); 
-} 
+//===-- IntegerDivision.cpp - Expand integer division ---------------------===//
+//
+// 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 file contains an implementation of 32bit and 64bit scalar integer
+// division for targets that don't have native support. It's largely derived
+// from compiler-rt's implementations of __udivsi3 and __udivmoddi4,
+// but hand-tuned for targets that prefer less control flow.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/IntegerDivision.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Intrinsics.h"
+#include <utility>
+
+using namespace llvm;
+
+#define DEBUG_TYPE "integer-division"
+
+/// Generate code to compute the remainder of two signed integers. Returns the
+/// 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);
+  }
+
+  // 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
+  // ;   %u_dividend   = sub i32 %dvd_xor, %dividend_sgn
+  // ;   %u_divisor    = sub i32 %dvs_xor, %divisor_sgn
+  // ;   %urem         = urem i32 %dividend, %divisor
+  // ;   %xored        = xor i32 %urem, %dividend_sgn
+  // ;   %srem         = sub i32 %xored, %dividend_sgn
+  Value *DividendSign = Builder.CreateAShr(Dividend, Shift);
+  Value *DivisorSign  = Builder.CreateAShr(Divisor, Shift);
+  Value *DvdXor       = Builder.CreateXor(Dividend, DividendSign);
+  Value *DvsXor       = Builder.CreateXor(Divisor, DivisorSign);
+  Value *UDividend    = Builder.CreateSub(DvdXor, DividendSign);
+  Value *UDivisor     = Builder.CreateSub(DvsXor, DivisorSign);
+  Value *URem         = Builder.CreateURem(UDividend, UDivisor);
+  Value *Xored        = Builder.CreateXor(URem, DividendSign);
+  Value *SRem         = Builder.CreateSub(Xored, DividendSign);
+
+  if (Instruction *URemInst = dyn_cast<Instruction>(URem))
+    Builder.SetInsertPoint(URemInst);
+
+  return SRem;
+}
+
+
+/// Generate code to compute the remainder of two unsigned integers. Returns the
+/// remainder. Builder's insert point should be pointing where the caller wants
+/// code generated, e.g. at the urem 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 *generatedUnsignedRemainderCode(Value *Dividend, Value *Divisor,
+                                             IRBuilder<> &Builder) {
+  // Remainder = Dividend - Quotient*Divisor
+
+  // Following instructions are generated for both i32 and i64
+
+  // ;   %quotient  = udiv i32 %dividend, %divisor
+  // ;   %product   = mul i32 %divisor, %quotient
+  // ;   %remainder = sub i32 %dividend, %product
+  Value *Quotient  = Builder.CreateUDiv(Dividend, Divisor);
+  Value *Product   = Builder.CreateMul(Divisor, Quotient);
+  Value *Remainder = Builder.CreateSub(Dividend, Product);
+
+  if (Instruction *UDiv = dyn_cast<Instruction>(Quotient))
+    Builder.SetInsertPoint(UDiv);
+
+  return Remainder;
+}
+
+/// Generate code to divide two signed integers. Returns the quotient, rounded
+/// towards 0. Builder's insert point should be pointing where the caller wants
+/// 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);
+  }
+
+  // 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
+  // ;   %tmp3   = xor i32 %tmp1, %divisor
+  // ;   %u_dvsr = sub nsw i32 %tmp3, %tmp1
+  // ;   %q_sgn  = xor i32 %tmp1, %tmp
+  // ;   %q_mag  = udiv i32 %u_dvnd, %u_dvsr
+  // ;   %tmp4   = xor i32 %q_mag, %q_sgn
+  // ;   %q      = sub i32 %tmp4, %q_sgn
+  Value *Tmp    = Builder.CreateAShr(Dividend, Shift);
+  Value *Tmp1   = Builder.CreateAShr(Divisor, Shift);
+  Value *Tmp2   = Builder.CreateXor(Tmp, Dividend);
+  Value *U_Dvnd = Builder.CreateSub(Tmp2, Tmp);
+  Value *Tmp3   = Builder.CreateXor(Tmp1, Divisor);
+  Value *U_Dvsr = Builder.CreateSub(Tmp3, Tmp1);
+  Value *Q_Sgn  = Builder.CreateXor(Tmp1, Tmp);
+  Value *Q_Mag  = Builder.CreateUDiv(U_Dvnd, U_Dvsr);
+  Value *Tmp4   = Builder.CreateXor(Q_Mag, Q_Sgn);
+  Value *Q      = Builder.CreateSub(Tmp4, Q_Sgn);
+
+  if (Instruction *UDiv = dyn_cast<Instruction>(Q_Mag))
+    Builder.SetInsertPoint(UDiv);
+
+  return Q;
+}
+
+/// Generates code to divide two unsigned scalar 32-bit or 64-bit integers.
+/// Returns the quotient, rounded towards 0. Builder's insert point should
+/// point where the caller wants code generated, e.g. at the udiv instruction.
+static Value *generateUnsignedDivisionCode(Value *Dividend, Value *Divisor,
+                                           IRBuilder<> &Builder) {
+  // 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 *True = Builder.getTrue();
+
+  BasicBlock *IBB = Builder.GetInsertBlock();
+  Function *F = IBB->getParent();
+  Function *CTLZ = Intrinsic::getDeclaration(F->getParent(), Intrinsic::ctlz,
+                                             DivTy);
+
+  // Our CFG is going to look like:
+  // +---------------------+
+  // | special-cases       |
+  // |   ...               |
+  // +---------------------+
+  //  |       |
+  //  |   +----------+
+  //  |   |  bb1     |
+  //  |   |  ...     |
+  //  |   +----------+
+  //  |    |      |
+  //  |    |  +------------+
+  //  |    |  |  preheader |
+  //  |    |  |  ...       |
+  //  |    |  +------------+
+  //  |    |      |
+  //  |    |      |      +---+
+  //  |    |      |      |   |
+  //  |    |  +------------+ |
+  //  |    |  |  do-while  | |
+  //  |    |  |  ...       | |
+  //  |    |  +------------+ |
+  //  |    |      |      |   |
+  //  |   +-----------+  +---+
+  //  |   | loop-exit |
+  //  |   |  ...      |
+  //  |   +-----------+
+  //  |     |
+  // +-------+
+  // | ...   |
+  // | end   |
+  // +-------+
+  BasicBlock *SpecialCases = Builder.GetInsertBlock();
+  SpecialCases->setName(Twine(SpecialCases->getName(), "_udiv-special-cases"));
+  BasicBlock *End = SpecialCases->splitBasicBlock(Builder.GetInsertPoint(),
+                                                  "udiv-end");
+  BasicBlock *LoopExit  = BasicBlock::Create(Builder.getContext(),
+                                             "udiv-loop-exit", F, End);
+  BasicBlock *DoWhile   = BasicBlock::Create(Builder.getContext(),
+                                             "udiv-do-while", F, End);
+  BasicBlock *Preheader = BasicBlock::Create(Builder.getContext(),
+                                             "udiv-preheader", F, End);
+  BasicBlock *BB1       = BasicBlock::Create(Builder.getContext(),
+                                             "udiv-bb1", F, End);
+
+  // We'll be overwriting the terminator to insert our extra blocks
+  SpecialCases->getTerminator()->eraseFromParent();
+
+  // Same instructions are generated for both i32 (msb 31) and i64 (msb 63).
+
+  // First off, check for special cases: dividend or divisor is zero, divisor
+  // is greater than dividend, and divisor is 1.
+  // ; special-cases:
+  // ;   %ret0_1      = icmp eq i32 %divisor, 0
+  // ;   %ret0_2      = icmp eq i32 %dividend, 0
+  // ;   %ret0_3      = or i1 %ret0_1, %ret0_2
+  // ;   %tmp0        = tail call i32 @llvm.ctlz.i32(i32 %divisor, i1 true)
+  // ;   %tmp1        = tail call i32 @llvm.ctlz.i32(i32 %dividend, i1 true)
+  // ;   %sr          = sub nsw i32 %tmp0, %tmp1
+  // ;   %ret0_4      = icmp ugt i32 %sr, 31
+  // ;   %ret0        = or i1 %ret0_3, %ret0_4
+  // ;   %retDividend = icmp eq i32 %sr, 31
+  // ;   %retVal      = select i1 %ret0, i32 0, i32 %dividend
+  // ;   %earlyRet    = or i1 %ret0, %retDividend
+  // ;   br i1 %earlyRet, label %end, label %bb1
+  Builder.SetInsertPoint(SpecialCases);
+  Value *Ret0_1      = Builder.CreateICmpEQ(Divisor, Zero);
+  Value *Ret0_2      = Builder.CreateICmpEQ(Dividend, Zero);
+  Value *Ret0_3      = Builder.CreateOr(Ret0_1, Ret0_2);
+  Value *Tmp0 = Builder.CreateCall(CTLZ, {Divisor, True});
+  Value *Tmp1 = Builder.CreateCall(CTLZ, {Dividend, True});
+  Value *SR          = Builder.CreateSub(Tmp0, Tmp1);
+  Value *Ret0_4      = Builder.CreateICmpUGT(SR, MSB);
+  Value *Ret0        = Builder.CreateOr(Ret0_3, Ret0_4);
+  Value *RetDividend = Builder.CreateICmpEQ(SR, MSB);
+  Value *RetVal      = Builder.CreateSelect(Ret0, Zero, Dividend);
+  Value *EarlyRet    = Builder.CreateOr(Ret0, RetDividend);
+  Builder.CreateCondBr(EarlyRet, End, BB1);
+
+  // ; bb1:                                             ; preds = %special-cases
+  // ;   %sr_1     = add i32 %sr, 1
+  // ;   %tmp2     = sub i32 31, %sr
+  // ;   %q        = shl i32 %dividend, %tmp2
+  // ;   %skipLoop = icmp eq i32 %sr_1, 0
+  // ;   br i1 %skipLoop, label %loop-exit, label %preheader
+  Builder.SetInsertPoint(BB1);
+  Value *SR_1     = Builder.CreateAdd(SR, One);
+  Value *Tmp2     = Builder.CreateSub(MSB, SR);
+  Value *Q        = Builder.CreateShl(Dividend, Tmp2);
+  Value *SkipLoop = Builder.CreateICmpEQ(SR_1, Zero);
+  Builder.CreateCondBr(SkipLoop, LoopExit, Preheader);
+
+  // ; preheader:                                           ; preds = %bb1
+  // ;   %tmp3 = lshr i32 %dividend, %sr_1
+  // ;   %tmp4 = add i32 %divisor, -1
+  // ;   br label %do-while
+  Builder.SetInsertPoint(Preheader);
+  Value *Tmp3 = Builder.CreateLShr(Dividend, SR_1);
+  Value *Tmp4 = Builder.CreateAdd(Divisor, NegOne);
+  Builder.CreateBr(DoWhile);
+
+  // ; do-while:                                 ; preds = %do-while, %preheader
+  // ;   %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]
+  // ;   %sr_3    = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
+  // ;   %r_1     = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
+  // ;   %q_2     = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
+  // ;   %tmp5  = shl i32 %r_1, 1
+  // ;   %tmp6  = lshr i32 %q_2, 31
+  // ;   %tmp7  = or i32 %tmp5, %tmp6
+  // ;   %tmp8  = shl i32 %q_2, 1
+  // ;   %q_1   = or i32 %carry_1, %tmp8
+  // ;   %tmp9  = sub i32 %tmp4, %tmp7
+  // ;   %tmp10 = ashr i32 %tmp9, 31
+  // ;   %carry = and i32 %tmp10, 1
+  // ;   %tmp11 = and i32 %tmp10, %divisor
+  // ;   %r     = sub i32 %tmp7, %tmp11
+  // ;   %sr_2  = add i32 %sr_3, -1
+  // ;   %tmp12 = icmp eq i32 %sr_2, 0
+  // ;   br i1 %tmp12, label %loop-exit, label %do-while
+  Builder.SetInsertPoint(DoWhile);
+  PHINode *Carry_1 = Builder.CreatePHI(DivTy, 2);
+  PHINode *SR_3    = Builder.CreatePHI(DivTy, 2);
+  PHINode *R_1     = Builder.CreatePHI(DivTy, 2);
+  PHINode *Q_2     = Builder.CreatePHI(DivTy, 2);
+  Value *Tmp5  = Builder.CreateShl(R_1, One);
+  Value *Tmp6  = Builder.CreateLShr(Q_2, MSB);
+  Value *Tmp7  = Builder.CreateOr(Tmp5, Tmp6);
+  Value *Tmp8  = Builder.CreateShl(Q_2, One);
+  Value *Q_1   = Builder.CreateOr(Carry_1, Tmp8);
+  Value *Tmp9  = Builder.CreateSub(Tmp4, Tmp7);
+  Value *Tmp10 = Builder.CreateAShr(Tmp9, MSB);
+  Value *Carry = Builder.CreateAnd(Tmp10, One);
+  Value *Tmp11 = Builder.CreateAnd(Tmp10, Divisor);
+  Value *R     = Builder.CreateSub(Tmp7, Tmp11);
+  Value *SR_2  = Builder.CreateAdd(SR_3, NegOne);
+  Value *Tmp12 = Builder.CreateICmpEQ(SR_2, Zero);
+  Builder.CreateCondBr(Tmp12, LoopExit, DoWhile);
+
+  // ; loop-exit:                                      ; preds = %do-while, %bb1
+  // ;   %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
+  // ;   %q_3     = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
+  // ;   %tmp13 = shl i32 %q_3, 1
+  // ;   %q_4   = or i32 %carry_2, %tmp13
+  // ;   br label %end
+  Builder.SetInsertPoint(LoopExit);
+  PHINode *Carry_2 = Builder.CreatePHI(DivTy, 2);
+  PHINode *Q_3     = Builder.CreatePHI(DivTy, 2);
+  Value *Tmp13 = Builder.CreateShl(Q_3, One);
+  Value *Q_4   = Builder.CreateOr(Carry_2, Tmp13);
+  Builder.CreateBr(End);
+
+  // ; end:                                 ; preds = %loop-exit, %special-cases
+  // ;   %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
+  // ;   ret i32 %q_5
+  Builder.SetInsertPoint(End, End->begin());
+  PHINode *Q_5 = Builder.CreatePHI(DivTy, 2);
+
+  // Populate the Phis, since all values have now been created. Our Phis were:
+  // ;   %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]
+  Carry_1->addIncoming(Zero, Preheader);
+  Carry_1->addIncoming(Carry, DoWhile);
+  // ;   %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
+  SR_3->addIncoming(SR_1, Preheader);
+  SR_3->addIncoming(SR_2, DoWhile);
+  // ;   %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
+  R_1->addIncoming(Tmp3, Preheader);
+  R_1->addIncoming(R, DoWhile);
+  // ;   %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
+  Q_2->addIncoming(Q, Preheader);
+  Q_2->addIncoming(Q_1, DoWhile);
+  // ;   %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
+  Carry_2->addIncoming(Zero, BB1);
+  Carry_2->addIncoming(Carry, DoWhile);
+  // ;   %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
+  Q_3->addIncoming(Q, BB1);
+  Q_3->addIncoming(Q_1, DoWhile);
+  // ;   %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
+  Q_5->addIncoming(Q_4, LoopExit);
+  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.
+///
+/// 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();
+    Rem->replaceAllUsesWith(Remainder);
+    Rem->dropAllReferences();
+    Rem->eraseFromParent();
+
+    // If we didn't actually generate an urem instruction, we're done
+    // This happens for example if the input were constant. In this case the
+    // Builder insertion point was unchanged
+    if (IsInsertPoint)
+      return true;
+
+    BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
+    Rem = BO;
+  }
+
+  Value *Remainder = generatedUnsignedRemainderCode(Rem->getOperand(0),
+                                                    Rem->getOperand(1),
+                                                    Builder);
+
+  Rem->replaceAllUsesWith(Remainder);
+  Rem->dropAllReferences();
+  Rem->eraseFromParent();
+
+  // Expand the udiv
+  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.
+///
+/// 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.
+    bool IsInsertPoint = Div->getIterator() == Builder.GetInsertPoint();
+    Div->replaceAllUsesWith(Quotient);
+    Div->dropAllReferences();
+    Div->eraseFromParent();
+
+    // If we didn't actually generate an udiv instruction, we're done
+    // This happens for example if the input were constant. In this case the
+    // Builder insertion point was unchanged
+    if (IsInsertPoint)
+      return true;
+
+    BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
+    Div = BO;
+  }
+
+  // Insert the unsigned division code
+  Value *Quotient = generateUnsignedDivisionCode(Div->getOperand(0),
+                                                 Div->getOperand(1),
+                                                 Builder);
+  Div->replaceAllUsesWith(Quotient);
+  Div->dropAllReferences();
+  Div->eraseFromParent();
+
+  return true;
+}
+
+/// Generate code to compute the remainder of two integers of bitwidth up to
+/// 32 bits. Uses the above routines and extends the inputs/truncates the
+/// outputs to operate in 32 bits; that is, these routines are good for targets
+/// that have no or very little suppport for smaller than 32 bit integer
+/// arithmetic.
+///
+/// Replace Rem with emulation code.
+bool llvm::expandRemainderUpTo32Bits(BinaryOperator *Rem) {
+  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 <= 32 &&
+         "Div of bitwidth greater than 32 not supported");
+
+  if (RemTyBitWidth == 32)
+    return expandRemainder(Rem);
+
+  // If bitwidth smaller than 32 extend inputs, extend output and proceed
+  // with 32 bit division.
+  IRBuilder<> Builder(Rem);
+
+  Value *ExtDividend;
+  Value *ExtDivisor;
+  Value *ExtRem;
+  Value *Trunc;
+  Type *Int32Ty = Builder.getInt32Ty();
+
+  if (Rem->getOpcode() == Instruction::SRem) {
+    ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int32Ty);
+    ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int32Ty);
+    ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);
+  } else {
+    ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int32Ty);
+    ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int32Ty);
+    ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
+  }
+  Trunc = Builder.CreateTrunc(ExtRem, RemTy);
+
+  Rem->replaceAllUsesWith(Trunc);
+  Rem->dropAllReferences();
+  Rem->eraseFromParent();
+
+  return expandRemainder(cast<BinaryOperator>(ExtRem));
+}
+
+/// Generate code to compute the remainder of two integers of bitwidth up to
+/// 64 bits. Uses the above routines and extends the inputs/truncates the
+/// outputs to operate in 64 bits.
+///
+/// Replace Rem with emulation code.
+bool llvm::expandRemainderUpTo64Bits(BinaryOperator *Rem) {
+  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)
+    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;
+  Value *ExtRem;
+  Value *Trunc;
+  Type *Int64Ty = Builder.getInt64Ty();
+
+  if (Rem->getOpcode() == Instruction::SRem) {
+    ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int64Ty);
+    ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int64Ty);
+    ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);
+  } else {
+    ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int64Ty);
+    ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int64Ty);
+    ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
+  }
+  Trunc = Builder.CreateTrunc(ExtRem, RemTy);
+
+  Rem->replaceAllUsesWith(Trunc);
+  Rem->dropAllReferences();
+  Rem->eraseFromParent();
+
+  return expandRemainder(cast<BinaryOperator>(ExtRem));
+}
+
+/// Generate code to divide two integers of bitwidth up to 32 bits. Uses the
+/// above routines and extends the inputs/truncates the outputs to operate
+/// in 32 bits; that is, these routines are good for targets that have no
+/// or very little support for smaller than 32 bit integer arithmetic.
+///
+/// Replace Div with emulation code.
+bool llvm::expandDivisionUpTo32Bits(BinaryOperator *Div) {
+  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 <= 32 && "Div of bitwidth greater than 32 not supported");
+
+  if (DivTyBitWidth == 32)
+    return expandDivision(Div);
+
+  // If bitwidth smaller than 32 extend inputs, extend output and proceed
+  // with 32 bit division.
+  IRBuilder<> Builder(Div);
+
+  Value *ExtDividend;
+  Value *ExtDivisor;
+  Value *ExtDiv;
+  Value *Trunc;
+  Type *Int32Ty = Builder.getInt32Ty();
+
+  if (Div->getOpcode() == Instruction::SDiv) {
+    ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int32Ty);
+    ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int32Ty);
+    ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);
+  } else {
+    ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int32Ty);
+    ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int32Ty);
+    ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);
+  }
+  Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
+
+  Div->replaceAllUsesWith(Trunc);
+  Div->dropAllReferences();
+  Div->eraseFromParent();
+
+  return expandDivision(cast<BinaryOperator>(ExtDiv));
+}
+
+/// Generate code to divide two integers of bitwidth up to 64 bits. Uses the
+/// above routines and extends the inputs/truncates the outputs to operate
+/// in 64 bits.
+///
+/// Replace Div with emulation code.
+bool llvm::expandDivisionUpTo64Bits(BinaryOperator *Div) {
+  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)
+    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;
+  Value *ExtDiv;
+  Value *Trunc;
+  Type *Int64Ty = Builder.getInt64Ty();
+
+  if (Div->getOpcode() == Instruction::SDiv) {
+    ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int64Ty);
+    ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int64Ty);
+    ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);
+  } else {
+    ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int64Ty);
+    ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int64Ty);
+    ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);
+  }
+  Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
+
+  Div->replaceAllUsesWith(Trunc);
+  Div->dropAllReferences();
+  Div->eraseFromParent();
+
+  return expandDivision(cast<BinaryOperator>(ExtDiv));
+}