DivRemPairs.cpp File Reference

#include "llvm/Transforms/Scalar/DivRemPairs.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/Pass.h"
#include "llvm/Support/DebugCounter.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BypassSlowDivision.h"

Include dependency graph for DivRemPairs.cpp:

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "div-rem-pairs"

Functions
	STATISTIC (NumPairs, "Number of div/rem pairs")
	STATISTIC (NumHoisted, "Number of instructions hoisted")
	STATISTIC (NumDecomposed, "Number of instructions decomposed")
	DEBUG_COUNTER (DRPCounter, "div-rem-pairs-transform", "Controls transformations in div-rem-pairs pass")
static bool	optimizeDivRem (Function &F, const TargetTransformInfo &TTI, const DominatorTree &DT)
	Find matching pairs of integer div/rem ops (they have the same numerator, denominator, and signedness). More...
	INITIALIZE_PASS_BEGIN (DivRemPairsLegacyPass, "div-rem-pairs", "Hoist/decompose integer division and remainder", false, false) INITIALIZE_PASS_END(DivRemPairsLegacyPass

Variables
div rem	pairs
div rem Hoist decompose integer division and	remainder
div rem Hoist decompose integer division and	false

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "div-rem-pairs"

Definition at line 29 of file DivRemPairs.cpp.

Function Documentation

DEBUG_COUNTER()

DEBUG_COUNTER	(	DRPCounter	,
		"div-rem-pairs-transform"	,
		"Controls transformations in div-rem-pairs pass"
	)

INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	DivRemPairsLegacyPass	,
		"div-rem-pairs"	,
		"Hoist/decompose integer division and remainder"	,
		false	,
		false
	)

Referenced by optimizeDivRem().

optimizeDivRem()

static bool optimizeDivRem ( Function &  F, const TargetTransformInfo &  TTI, const DominatorTree &  DT  )

static

Find matching pairs of integer div/rem ops (they have the same numerator, denominator, and signedness).

If they exist in different basic blocks, bring them together by hoisting or replace the common division operation that is implicit in the remainder: X % Y <–> X - ((X / Y) * Y).

We can largely ignore the normal safety and cost constraints on speculation of these ops when we find a matching pair. This is because we are already guaranteed that any exceptions and most cost are already incurred by the first member of the pair.

Note: This transform could be an oddball enhancement to EarlyCSE, GVN, or SimplifyCFG, but it's split off on its own because it's different enough that it doesn't quite match the stated objectives of those passes.

Definition at line 50 of file DivRemPairs.cpp.

References llvm::AnalysisUsage::addPreserved(), llvm::AnalysisUsage::addRequired(), CreateMul(), llvm::DominatorTree::dominates(), llvm::Instruction::eraseFromParent(), F(), llvm::Pass::getAnalysisUsage(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::PassRegistry::getPassRegistry(), llvm::Value::getType(), llvm::TargetTransformInfo::hasDivRemOp(), I, INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_DEPENDENCY, llvm::initializeDivRemPairsLegacyPassPass(), llvm::Instruction::insertAfter(), llvm::Instruction::moveAfter(), llvm::Instruction::moveBefore(), llvm::Value::replaceAllUsesWith(), runOnFunction(), llvm::AnalysisUsage::setPreservesCFG(), llvm::DebugCounter::shouldExecute(), X, and Y.

Referenced by llvm::DivRemPairsPass::run().

STATISTIC() [1/3]

STATISTIC	(	NumPairs	,
		"Number of div/rem pairs"
	)

STATISTIC() [2/3]

STATISTIC	(	NumHoisted	,
		"Number of instructions hoisted"
	)

STATISTIC() [3/3]

STATISTIC	(	NumDecomposed	,
		"Number of instructions decomposed"
	)

Variable Documentation

false

div rem Hoist decompose integer division and false

Definition at line 199 of file DivRemPairs.cpp.

pairs

div rem pairs

Definition at line 199 of file DivRemPairs.cpp.

remainder

div rem Hoist decompose integer division and remainder

Definition at line 199 of file DivRemPairs.cpp.

Referenced by llvm::APInt::abs(), llvm::detail::DoubleAPFloat::getSecond(), KnuthDiv(), and llvm::detail::IEEEFloat::needsCleanup().