LLVM  10.0.0svn
Classes | Macros | Typedefs | Functions | Variables
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/IR/PatternMatch.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.

Classes

struct  DivRemPairWorklistEntry
 A thin wrapper to store two values that we matched as div-rem pair. More...
 

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 llvm::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. More...
 
static DivRemWorklistTy getWorklist (Function &F)
 Find matching pairs of integer div/rem ops (they have the same numerator, denominator, and signedness). More...
 
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 31 of file DivRemPairs.cpp.

Typedef Documentation

◆ DivRemWorklistTy

Definition at line 113 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 120 of file DivRemPairs.cpp.

References llvm::SmallVectorImpl< T >::emplace_back(), I, llvm::Match, and matchExpandedRem().

Referenced by optimizeDivRem().

◆ INITIALIZE_PASS_BEGIN()

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

Referenced by optimizeDivRem().

◆ matchExpandedRem()

static llvm::Optional<ExpandedMatch> matchExpandedRem ( Instruction I)
static

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

References llvm::AnalysisUsage::addPreserved(), llvm::AnalysisUsage::addRequired(), assert(), CreateMul(), llvm::DominatorTree::dominates(), E, llvm::Instruction::eraseFromParent(), F(), llvm::Pass::getAnalysisUsage(), llvm::PassRegistry::getPassRegistry(), getWorklist(), llvm::TargetTransformInfo::hasDivRemOp(), INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_DEPENDENCY, llvm::initializeDivRemPairsLegacyPassPass(), llvm::Instruction::insertAfter(), llvm::Value::replaceAllUsesWith(), runOnFunction(), llvm::Value::setName(), llvm::AnalysisUsage::setPreservesCFG(), llvm::DebugCounter::shouldExecute(), X, and Y.

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

◆ STATISTIC() [1/4]

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

◆ STATISTIC() [2/4]

STATISTIC ( NumRecomposed  ,
"Number of instructions recomposed"   
)

◆ STATISTIC() [3/4]

STATISTIC ( NumHoisted  ,
"Number of instructions hoisted"   
)

◆ STATISTIC() [4/4]

STATISTIC ( NumDecomposed  ,
"Number of instructions decomposed"   
)

Variable Documentation

◆ false

div rem Hoist decompose integer division and false

Definition at line 355 of file DivRemPairs.cpp.

◆ pairs

div rem pairs

Definition at line 355 of file DivRemPairs.cpp.

◆ remainder

div rem Hoist decompose integer division and remainder