115using namespace PatternMatch;
117#define DEBUG_TYPE "nary-reassociate"
153char NaryReassociateLegacyPass::ID = 0;
156 "Nary reassociation",
false,
false)
166 return new NaryReassociateLegacyPass();
169bool NaryReassociateLegacyPass::runOnFunction(
Function &
F) {
173 auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
174 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
175 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
176 auto *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
177 auto *
TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
179 return Impl.runImpl(
F, AC, DT, SE, TLI,
TTI);
208 DL = &
F.getDataLayout();
210 bool Changed =
false, ChangedInThisIteration;
212 ChangedInThisIteration = doOneIteration(
F);
213 Changed |= ChangedInThisIteration;
214 }
while (ChangedInThisIteration);
218bool NaryReassociatePass::doOneIteration(
Function &
F) {
219 bool Changed =
false;
228 const SCEV *OrigSCEV =
nullptr;
229 if (
Instruction *NewI = tryReassociate(&OrigI, OrigSCEV)) {
231 OrigI.replaceAllUsesWith(NewI);
259 if (NewSCEV != OrigSCEV)
273template <
typename PredT>
275NaryReassociatePass::matchAndReassociateMinOrMax(
Instruction *
I,
276 const SCEV *&OrigSCEV) {
283 if (
match(
I, MinMaxMatcher)) {
285 if (
auto *NewMinMax = dyn_cast_or_null<Instruction>(
286 tryReassociateMinOrMax(
I, MinMaxMatcher, LHS, RHS)))
288 if (
auto *NewMinMax = dyn_cast_or_null<Instruction>(
289 tryReassociateMinOrMax(
I, MinMaxMatcher, RHS, LHS)))
296 const SCEV *&OrigSCEV) {
301 switch (
I->getOpcode()) {
302 case Instruction::Add:
303 case Instruction::Mul:
305 return tryReassociateBinaryOp(cast<BinaryOperator>(
I));
306 case Instruction::GetElementPtr:
308 return tryReassociateGEP(cast<GetElementPtrInst>(
I));
318 if (
I->getType()->isIntegerTy())
319 if ((ResI = matchAndReassociateMinOrMax<umin_pred_ty>(
I, OrigSCEV)) ||
320 (ResI = matchAndReassociateMinOrMax<smin_pred_ty>(
I, OrigSCEV)) ||
321 (ResI = matchAndReassociateMinOrMax<umax_pred_ty>(
I, OrigSCEV)) ||
322 (ResI = matchAndReassociateMinOrMax<smax_pred_ty>(
I, OrigSCEV)))
341 for (
unsigned I = 1, E =
GEP->getNumOperands();
I != E; ++
I, ++GTI) {
343 if (
auto *NewGEP = tryReassociateGEPAtIndex(
GEP,
I - 1,
352bool NaryReassociatePass::requiresSignExtension(
Value *
Index,
354 unsigned IndexSizeInBits =
356 return cast<IntegerType>(
Index->getType())->getBitWidth() < IndexSizeInBits;
361 unsigned I,
Type *IndexedType) {
363 Value *IndexToSplit =
GEP->getOperand(
I + 1);
364 if (
SExtInst *SExt = dyn_cast<SExtInst>(IndexToSplit)) {
365 IndexToSplit = SExt->getOperand(0);
366 }
else if (
ZExtInst *ZExt = dyn_cast<ZExtInst>(IndexToSplit)) {
369 IndexToSplit = ZExt->getOperand(0);
372 if (
AddOperator *AO = dyn_cast<AddOperator>(IndexToSplit)) {
376 if (requiresSignExtension(IndexToSplit,
GEP) &&
380 Value *
LHS = AO->getOperand(0), *
RHS = AO->getOperand(1);
382 if (
auto *NewGEP = tryReassociateGEPAtIndex(
GEP,
I, LHS, RHS, IndexedType))
387 tryReassociateGEPAtIndex(
GEP,
I, RHS, LHS, IndexedType))
419 Value *Candidate = findClosestMatchingDominator(CandidateExpr,
GEP);
420 if (Candidate ==
nullptr)
445 if (IndexedSize % ElementSize != 0)
451 RHS = Builder.CreateSExtOrTrunc(RHS, PtrIdxTy);
452 if (IndexedSize != ElementSize) {
453 RHS = Builder.CreateMul(
454 RHS, ConstantInt::get(PtrIdxTy, IndexedSize / ElementSize));
457 Builder.CreateGEP(
GEP->getResultElementType(), Candidate, RHS));
468 if (
auto *NewI = tryReassociateBinaryOp(LHS, RHS,
I))
470 if (
auto *NewI = tryReassociateBinaryOp(RHS, LHS,
I))
477 Value *
A =
nullptr, *
B =
nullptr;
485 if (BExpr != RHSExpr) {
487 tryReassociatedBinaryOp(getBinarySCEV(
I, AExpr, RHSExpr),
B,
I))
490 if (AExpr != RHSExpr) {
492 tryReassociatedBinaryOp(getBinarySCEV(
I, BExpr, RHSExpr),
A,
I))
499Instruction *NaryReassociatePass::tryReassociatedBinaryOp(
const SCEV *LHSExpr,
504 auto *
LHS = findClosestMatchingDominator(LHSExpr,
I);
509 switch (
I->getOpcode()) {
510 case Instruction::Add:
511 NewI = BinaryOperator::CreateAdd(LHS, RHS,
"",
I->getIterator());
513 case Instruction::Mul:
514 NewI = BinaryOperator::CreateMul(LHS, RHS,
"",
I->getIterator());
526 switch (
I->getOpcode()) {
527 case Instruction::Add:
529 case Instruction::Mul:
540 switch (
I->getOpcode()) {
541 case Instruction::Add:
543 case Instruction::Mul:
552NaryReassociatePass::findClosestMatchingDominator(
const SCEV *CandidateExpr,
554 auto Pos = SeenExprs.find(CandidateExpr);
555 if (Pos == SeenExprs.end())
558 auto &Candidates = Pos->second;
563 while (!Candidates.empty()) {
566 if (
Value *Candidate = Candidates.pop_back_val()) {
567 Instruction *CandidateInstruction = cast<Instruction>(Candidate);
568 if (!DT->
dominates(CandidateInstruction, Dominatee))
575 DropPoisonGeneratingInsts))
579 I->dropPoisonGeneratingAnnotations();
581 return CandidateInstruction;
588 if (std::is_same_v<smax_pred_ty, typename MaxMinT::PredType>)
590 else if (std::is_same_v<umax_pred_ty, typename MaxMinT::PredType>)
592 else if (std::is_same_v<smin_pred_ty, typename MaxMinT::PredType>)
594 else if (std::is_same_v<umin_pred_ty, typename MaxMinT::PredType>)
606template <
typename MaxMinT>
610 Value *
A =
nullptr, *
B =
nullptr;
619 !(U->hasOneUser() && *U->users().begin() == I);
621 !
match(LHS, m_MaxMin))
631 Instruction *R1MinMax = findClosestMatchingDominator(R1Expr,
I);
636 LLVM_DEBUG(
dbgs() <<
"NARY: Found common sub-expr: " << *R1MinMax <<
"\n");
643 Value *NewMinMax = Expander.expandCodeFor(R2Expr,
I->getType(),
I);
647 <<
"NARY: Inserting: " << *NewMinMax <<
"\n");
655 if (BExpr != RHSExpr) {
657 if (
auto *NewMinMax = tryCombination(
A, AExpr, RHS, RHSExpr,
B, BExpr))
661 if (AExpr != RHSExpr) {
663 if (
auto *NewMinMax = tryCombination(RHS, RHSExpr,
B, BExpr,
A, AExpr))
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
Module.h This file contains the declarations for the Module class.
static SCEVTypes convertToSCEVype(MaxMinT &MM)
static bool isGEPFoldable(GetElementPtrInst *GEP, const TargetTransformInfo *TTI)
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
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.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Represents analyses that only rely on functions' control flow.
IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
TypeSize getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
unsigned getIndexSizeInBits(unsigned AS) const
Size in bits of index used for address calculation in getelementptr.
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
Analysis pass which computes a DominatorTree.
Legacy 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.
FunctionPass class - This class is used to implement most global optimizations.
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
void setIsInBounds(bool b=true)
Set or clear the inbounds flag on this GEP instruction.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
A Module instance is used to store all the information related to an LLVM module.
bool runImpl(Function &F, AssumptionCache *AC_, DominatorTree *DT_, ScalarEvolution *SE_, TargetLibraryInfo *TLI_, TargetTransformInfo *TTI_)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
virtual bool doInitialization(Module &)
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
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.
void preserve()
Mark an analysis as preserved.
This class uses information about analyze scalars to rewrite expressions in canonical form.
This class represents an analyzed expression in the program.
bool isZero() const
Return true if the expression is a constant zero.
This class represents a sign extension of integer types.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
const SCEV * getGEPExpr(GEPOperator *GEP, const SmallVectorImpl< const SCEV * > &IndexExprs)
Returns an expression for a GEP.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
const SCEV * getUnknown(Value *V)
bool canReuseInstruction(const SCEV *S, Instruction *I, SmallVectorImpl< Instruction * > &DropPoisonGeneratingInsts)
Check whether it is poison-safe to represent the expression S using the instruction I.
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Twine concat(const Twine &Suffix) const
The instances of the Type class are immutable: once they are created, they are never changed.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
iterator_range< user_iterator > users()
bool hasNUsesOrMore(unsigned N) const
Return true if this value has N uses or more.
void takeName(Value *V)
Transfer the name from V to this value.
Value handle that is nullable, but tries to track the Value.
This class represents zero extension of integer types.
constexpr ScalarTy getFixedValue() const
bool isSequential() const
Type * getIndexedType() const
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
bool match(Val *V, const Pattern &P)
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
ElementType
The element type of an SRV or UAV resource.
This is an optimization pass for GlobalISel generic memory operations.
@ NeverOverflows
Never overflows.
FunctionPass * createNaryReassociatePass()
void initializeNaryReassociateLegacyPassPass(PassRegistry &)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
OverflowResult computeOverflowForSignedAdd(const WithCache< const Value * > &LHS, const WithCache< const Value * > &RHS, const SimplifyQuery &SQ)
bool RecursivelyDeleteTriviallyDeadInstructionsPermissive(SmallVectorImpl< WeakTrackingVH > &DeadInsts, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
Same functionality as RecursivelyDeleteTriviallyDeadInstructions, but allow instructions that are not...
gep_type_iterator gep_type_begin(const User *GEP)
iterator_range< df_iterator< T > > depth_first(const T &G)
bool isKnownNonNegative(const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)
Returns true if the give value is known to be non-negative.