Go to the documentation of this file.
33 #define DEBUG_TYPE "div-rem-pairs"
34 STATISTIC(NumPairs,
"Number of div/rem pairs");
35 STATISTIC(NumRecomposed,
"Number of instructions recomposed");
36 STATISTIC(NumHoisted,
"Number of instructions hoisted");
37 STATISTIC(NumDecomposed,
"Number of instructions decomposed");
39 "Controls transformations in div-rem-pairs pass");
42 struct ExpandedMatch {
53 Value *Dividend, *XroundedDownToMultipleOfY;
61 XroundedDownToMultipleOfY,
68 M.Key.SignedOp = Div->
getOpcode() == Instruction::SDiv;
69 M.Key.Dividend = Dividend;
70 M.Key.Divisor = Divisor;
78 struct DivRemPairWorklistEntry {
87 : DivInst(DivInst_), RemInst(RemInst_) {
89 DivInst->
getOpcode() == Instruction::SDiv) &&
100 bool isSigned()
const {
return DivInst->
getOpcode() == Instruction::SDiv; }
106 bool isRemExpanded()
const {
108 case Instruction::SRem:
109 case Instruction::URem:
133 if (
I.getOpcode() == Instruction::SDiv)
135 else if (
I.getOpcode() == Instruction::UDiv)
137 else if (
I.getOpcode() == Instruction::SRem)
139 else if (
I.getOpcode() == Instruction::URem)
152 for (
auto &RemPair : RemMap) {
154 auto It = DivMap.
find(RemPair.first);
155 if (It == DivMap.
end())
185 bool Changed =
false;
192 for (DivRemPairWorklistEntry &
E : Worklist) {
198 auto &DivInst =
E.DivInst;
199 auto &RemInst =
E.RemInst;
201 const bool RemOriginallyWasInExpandedForm =
E.isRemExpanded();
202 (void)RemOriginallyWasInExpandedForm;
204 if (HasDivRemOp &&
E.isRemExpanded()) {
209 Instruction *RealRem =
E.isSigned() ? BinaryOperator::CreateSRem(
X,
Y)
210 : BinaryOperator::CreateURem(
X,
Y);
227 assert((!
E.isRemExpanded() || !HasDivRemOp) &&
228 "*If* the target supports div-rem, then by now the RemInst *is* "
229 "Instruction::[US]Rem.");
237 bool DivDominates = DT.
dominates(DivInst, RemInst);
238 if (!DivDominates && !DT.
dominates(RemInst, DivInst)) {
273 if (PredBB && IsSafeToHoist(RemInst, RemBB) &&
274 IsSafeToHoist(DivInst, DivBB) &&
292 if (!HasDivRemOp &&
E.isRemExpanded())
309 assert(!RemOriginallyWasInExpandedForm &&
310 "We should not be expanding if the rem was in expanded form to "
364 auto *FrX =
new FreezeInst(
X,
X->getName() +
".frozen", DivInst);
371 auto *FrY =
new FreezeInst(
Y,
Y->getName() +
".frozen", DivInst);
414 auto &
TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
415 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
423 "Hoist/decompose integer division and remainder",
false,
430 return new DivRemPairsLegacyPass();
A set of analyses that are preserved following a run of a transformation pass.
Analysis pass providing the TargetTransformInfo.
This is an optimization pass for GlobalISel generic memory operations.
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
TLS Variable Hoist
When an instruction is found to use only loop invariant operands that are safe to hoist,...
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
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,...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
FunctionAnalysisManager FAM
INITIALIZE_PASS_BEGIN(DivRemPairsLegacyPass, "div-rem-pairs", "Hoist/decompose integer division and remainder", false, false) INITIALIZE_PASS_END(DivRemPairsLegacyPass
The instances of the Type class are immutable: once they are created, they are never changed.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
This class implements a map that also provides access to all stored values in a deterministic order.
auto successors(MachineBasicBlock *BB)
We currently generate a but we really shouldn eax ecx xorl edx divl ecx eax divl ecx movl eax ret A similar code sequence works for division We currently compile i32 v2 eax eax jo LBB1_2 and
deferredval_ty< Value > m_Deferred(Value *const &V)
Like m_Specific(), but works if the specific value to match is determined as part of the same match()...
LLVM Basic Block Representation.
div rem Hoist decompose integer division and remainder
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
FunctionPass * createDivRemPairsPass()
FunctionType * getType(LLVMContext &Context, ID id, ArrayRef< Type * > Tys=None)
Return the function type for an intrinsic.
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool match(Val *V, const Pattern &P)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
Represent the analysis usage information of a pass.
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
BinOpPred_match< LHS, RHS, is_idiv_op > m_IDiv(const LHS &L, const RHS &R)
Matches integer division operations.
static bool shouldExecute(unsigned CounterName)
Legacy analysis pass which computes a DominatorTree.
STATISTIC(NumFunctions, "Total number of functions")
auto predecessors(MachineBasicBlock *BB)
void setName(const Twine &Name)
Change the name of the value.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
static DivRemWorklistTy getWorklist(Function &F)
Find matching pairs of integer div/rem ops (they have the same numerator, denominator,...
void moveAfter(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
iterator find(const_arg_type_t< KeyT > Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
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 ...
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
void setOperand(unsigned i, Value *Val)
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Type * getType() const
All values are typed, get the type of this value.
Represents analyses that only rely on functions' control flow.
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
self_iterator getIterator()
StringRef getName() const
Return a constant reference to the value's name.
void initializeDivRemPairsLegacyPassPass(PassRegistry &)
static bool runOnFunction(Function &F, bool PostInlining)
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
DEBUG_COUNTER(DRPCounter, "div-rem-pairs-transform", "Controls transformations in div-rem-pairs pass")
BinaryOp_match< LHS, RHS, Instruction::Mul, true > m_c_Mul(const LHS &L, const RHS &R)
Matches a Mul with LHS and RHS in either order.
Analysis pass which computes a DominatorTree.
void preserveSet()
Mark an analysis set as preserved.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
This class represents a freeze function that returns random concrete value if an operand is either a ...
static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Value handle that asserts if the Value is deleted.
const BasicBlock * getParent() const
static SmallVector< std::pair< int64_t, Value * >, 4 > decompose(Value *V, SmallVector< PreconditionTy, 4 > &Preconditions, bool IsSigned)
Legacy wrapper pass to provide the GlobalsAAResult object.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
A container for analyses that lazily runs them and caches their results.
FunctionPass class - This class is used to implement most global optimizations.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
AnalysisUsage & addRequired()
Value * getOperand(unsigned i) const
LLVM Value Representation.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
reference emplace_back(ArgTypes &&... Args)