34#define DEBUG_TYPE "div-rem-pairs"
36STATISTIC(NumRecomposed,
"Number of instructions recomposed");
37STATISTIC(NumHoisted,
"Number of instructions hoisted");
38STATISTIC(NumDecomposed,
"Number of instructions decomposed");
40 "Controls transformations in div-rem-pairs pass");
54 Value *Dividend, *XroundedDownToMultipleOfY;
62 XroundedDownToMultipleOfY,
69 M.Key.SignedOp = Div->
getOpcode() == Instruction::SDiv;
70 M.Key.Dividend = Dividend;
71 M.Key.Divisor = Divisor;
79struct DivRemPairWorklistEntry {
88 : DivInst(DivInst_), RemInst(RemInst_) {
89 assert((DivInst->getOpcode() == Instruction::UDiv ||
90 DivInst->getOpcode() == Instruction::SDiv) &&
92 assert(DivInst->getType() == RemInst->getType() &&
"Types should match.");
98 Type *
getType()
const {
return DivInst->getType(); }
101 bool isSigned()
const {
return DivInst->getOpcode() == Instruction::SDiv; }
104 Value *getDividend()
const {
return DivInst->getOperand(0); }
105 Value *getDivisor()
const {
return DivInst->getOperand(1); }
107 bool isRemExpanded()
const {
108 switch (RemInst->getOpcode()) {
109 case Instruction::SRem:
110 case Instruction::URem:
134 if (
I.getOpcode() == Instruction::SDiv)
136 else if (
I.getOpcode() == Instruction::UDiv)
138 else if (
I.getOpcode() == Instruction::SRem)
140 else if (
I.getOpcode() == Instruction::URem)
153 for (
auto &RemPair : RemMap) {
155 auto It = DivMap.
find(RemPair.first);
156 if (It == DivMap.
end())
186 bool Changed =
false;
193 for (DivRemPairWorklistEntry &
E : Worklist) {
199 auto &DivInst =
E.DivInst;
200 auto &RemInst =
E.RemInst;
202 const bool RemOriginallyWasInExpandedForm =
E.isRemExpanded();
203 (void)RemOriginallyWasInExpandedForm;
205 if (HasDivRemOp &&
E.isRemExpanded()) {
210 Instruction *RealRem =
E.isSigned() ? BinaryOperator::CreateSRem(
X,
Y)
211 : BinaryOperator::CreateURem(
X,
Y);
214 RealRem->
setName(RemInst->getName() +
".recomposed");
228 assert((!
E.isRemExpanded() || !HasDivRemOp) &&
229 "*If* the target supports div-rem, then by now the RemInst *is* "
230 "Instruction::[US]Rem.");
235 if (HasDivRemOp && RemInst->getParent() == DivInst->getParent())
238 bool DivDominates = DT.
dominates(DivInst, RemInst);
239 if (!DivDominates && !DT.
dominates(RemInst, DivInst)) {
293 if (PredBB && !isa<CatchSwitchInst>(PredBB->
getTerminator()) &&
295 IsSafeToHoist(RemInst, RemBB) && IsSafeToHoist(DivInst, DivBB) &&
297 [&](
BasicBlock *BB) {
return BB == DivBB || BB == RemBB; }) &&
299 [&](
BasicBlock *BB) {
return BB == RemBB || BB == PredBB; })) {
313 if (!HasDivRemOp &&
E.isRemExpanded())
320 RemInst->moveAfter(DivInst);
322 DivInst->moveAfter(RemInst);
330 assert(!RemOriginallyWasInExpandedForm &&
331 "We should not be expanding if the rem was in expanded form to "
370 DivInst->moveBefore(RemInst);
376 DivInst->dropPoisonGeneratingFlags();
389 auto *FrX =
new FreezeInst(
X,
X->getName() +
".frozen", DivInst);
390 DivInst->setOperand(0, FrX);
396 auto *FrY =
new FreezeInst(
Y,
Y->getName() +
".frozen", DivInst);
397 DivInst->setOperand(1, FrY);
403 Sub->
setName(RemInst->getName() +
".decomposed");
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
This file defines the DenseMap class.
static DivRemWorklistTy getWorklist(Function &F)
Find matching pairs of integer div/rem ops (they have the same numerator, denominator,...
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,...
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 ...
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool isSigned(unsigned int Opcode)
This is the interface for a simple mod/ref and alias analysis over globals.
This file implements a map that provides insertion order iteration.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
FunctionAnalysisManager FAM
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static SymbolRef::Type getType(const Symbol *Sym)
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Value handle that asserts if the Value is deleted.
LLVM Basic Block Representation.
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
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...
Represents analyses that only rely on functions' control flow.
static bool shouldExecute(unsigned CounterName)
iterator find(const_arg_type_t< KeyT > Val)
Analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
This class represents a freeze function that returns random concrete value if an operand is either a ...
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
This class implements a map that also provides access to all stored values in a deterministic order.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserveSet()
Mark an analysis set as preserved.
reference emplace_back(ArgTypes &&... Args)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Analysis pass providing the TargetTransformInfo.
The instances of the Type class are immutable: once they are created, they are never changed.
void setOperand(unsigned i, Value *Val)
LLVM Value Representation.
void setName(const Twine &Name)
Change the name of the value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
self_iterator getIterator()
bool match(Val *V, const Pattern &P)
BinOpPred_match< LHS, RHS, is_idiv_op > m_IDiv(const LHS &L, const RHS &R)
Matches integer division operations.
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
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()...
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
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.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
This is an optimization pass for GlobalISel generic memory operations.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
auto successors(const MachineBasicBlock *BB)
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.
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
auto predecessors(const MachineBasicBlock *BB)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)