LLVM  10.0.0svn
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

◆ DEBUG_TYPE

 #define DEBUG_TYPE   "div-rem-pairs"

Definition at line 31 of file DivRemPairs.cpp.

◆ DivRemWorklistTy

 using DivRemWorklistTy = SmallVector

Definition at line 113 of file DivRemPairs.cpp.

◆ 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 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.

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

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" )

◆ false

 div rem Hoist decompose integer division and false

Definition at line 353 of file DivRemPairs.cpp.

◆ pairs

 div rem pairs

Definition at line 353 of file DivRemPairs.cpp.

◆ remainder

 div rem Hoist decompose integer division and remainder

Definition at line 353 of file DivRemPairs.cpp.