llvm/llvm/lib/Transforms/Utils/IntegerDivision.cpp

//===-- 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"

usingnamespacellvm;

#define DEBUG_TYPE …

/// 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) { … }


/// 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) { … }

/// 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) { … }

/// 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) { … }

/// 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.
///
/// Replace Rem with generated code.
bool llvm::expandRemainder(BinaryOperator *Rem) { … }

/// 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.
///
/// Replace Div with generated code.
bool llvm::expandDivision(BinaryOperator *Div) { … }

/// 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) { … }

/// 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) { … }

/// 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) { … }

/// 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) { … }