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/Analysis/ValueTracking.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/DebugCounter.h"
#include "llvm/Transforms/Utils/BypassSlowDivision.h"
#include <optional>

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "div-rem-pairs"

Typedefs
using	DivRemWorklistTy = SmallVector< DivRemPairWorklistEntry, 4 >

Functions
	STATISTIC (NumPairs, "Number of div/rem pairs")
	STATISTIC (NumRecomposed, "Number of instructions recomposed")
	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 std::optional< ExpandedMatch >	matchExpandedRem (Instruction &I)
	See if we can match: (which is the form we expand into) X - ((X ?/ Y) * Y) which is equivalent to: X ?% Y.
static DivRemWorklistTy	getWorklist (Function &F)
	Find matching pairs of integer div/rem ops (they have the same numerator, denominator, and signedness).
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).

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "div-rem-pairs"

Definition at line 31 of file DivRemPairs.cpp.

Typedef Documentation

DivRemWorklistTy

using DivRemWorklistTy = SmallVector<DivRemPairWorklistEntry, 4>

Definition at line 115 of file DivRemPairs.cpp.

Function Documentation

DEBUG_COUNTER()

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

getWorklist()

static DivRemWorklistTy getWorklist ( Function &  F )

static

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

Place those pairs into a worklist for further processing. This indirection is needed because we have to use TrackingVH<> because we will be doing RAUW, and if one of the rem instructions we change happens to be an input to another div/rem in the maps, we'd have problems.

Definition at line 122 of file DivRemPairs.cpp.

References llvm::SmallVectorImpl< T >::emplace_back(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), F, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), I, llvm::Match, and matchExpandedRem().

Referenced by optimizeDivRem().

matchExpandedRem()

static std::optional< ExpandedMatch > matchExpandedRem ( Instruction &  I )

static

See if we can match: (which is the form we expand into) X - ((X ?/ Y) * Y) which is equivalent to: X ?% Y.

Definition at line 50 of file DivRemPairs.cpp.

References llvm::Instruction::getOpcode(), I, llvm::PatternMatch::m_c_Mul(), llvm::PatternMatch::m_CombineAnd(), llvm::PatternMatch::m_Deferred(), llvm::PatternMatch::m_IDiv(), llvm::PatternMatch::m_Instruction(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Sub(), llvm::PatternMatch::m_Value(), and llvm::PatternMatch::match().

Referenced by getWorklist().

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 181 of file DivRemPairs.cpp.

References llvm::all_of(), assert(), llvm::DominatorTree::dominates(), llvm::Instruction::eraseFromParent(), F, llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::BasicBlock::getSingleSuccessor(), llvm::BasicBlock::getTerminator(), llvm::BasicBlock::getUniquePredecessor(), getWorklist(), llvm::TargetTransformInfo::hasDivRemOp(), I, llvm::Instruction::insertAfter(), llvm::isGuaranteedNotToBeUndefOrPoison(), llvm::isGuaranteedToTransferExecutionToSuccessor(), Mul, llvm::predecessors(), llvm::Value::replaceAllUsesWith(), llvm::Value::setName(), llvm::User::setOperand(), llvm::DebugCounter::shouldExecute(), llvm::successors(), X, and Y.

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

STATISTIC() [1/4]

STATISTIC	(	NumDecomposed	,
		"Number of instructions decomposed"
	)

STATISTIC() [2/4]

STATISTIC	(	NumHoisted	,
		"Number of instructions hoisted"
	)

STATISTIC() [3/4]

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

STATISTIC() [4/4]

STATISTIC	(	NumRecomposed	,
		"Number of instructions recomposed"
	)