35#define DL_NAME "delinearize"
36#define DEBUG_TYPE DL_NAME
41 if (
const auto *SU = dyn_cast<SCEVUnknown>(S))
42 return isa<UndefValue>(SU->getValue());
50struct SCEVCollectStrides {
55 : SE(SE), Strides(S) {}
57 bool follow(
const SCEV *S) {
59 Strides.
push_back(AR->getStepRecurrence(SE));
63 bool isDone()
const {
return false; }
67struct SCEVCollectTerms {
72 bool follow(
const SCEV *S) {
73 if (isa<SCEVUnknown>(S) || isa<SCEVMulExpr>(S) ||
74 isa<SCEVSignExtendExpr>(S)) {
86 bool isDone()
const {
return false; }
93 SCEVHasAddRec(
bool &ContainsAddRec) : ContainsAddRec(ContainsAddRec) {
94 ContainsAddRec =
false;
97 bool follow(
const SCEV *S) {
98 if (isa<SCEVAddRecExpr>(S)) {
99 ContainsAddRec =
true;
109 bool isDone()
const {
return false; }
124struct SCEVCollectAddRecMultiplies {
130 : Terms(
T), SE(SE) {}
132 bool follow(
const SCEV *S) {
133 if (
auto *
Mul = dyn_cast<SCEVMulExpr>(S)) {
134 bool HasAddRec =
false;
143 bool ContainsAddRec =
false;
144 SCEVHasAddRec ContiansAddRec(ContainsAddRec);
146 HasAddRec |= ContainsAddRec;
164 bool isDone()
const {
return false; }
176 SCEVCollectStrides StrideCollector(SE, Strides);
180 dbgs() <<
"Strides:\n";
181 for (
const SCEV *S : Strides)
182 dbgs() << *S <<
"\n";
185 for (
const SCEV *S : Strides) {
186 SCEVCollectTerms TermCollector(Terms);
191 dbgs() <<
"Terms:\n";
192 for (
const SCEV *
T : Terms)
193 dbgs() << *
T <<
"\n";
196 SCEVCollectAddRecMultiplies MulCollector(Terms, SE);
208 if (
const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Step)) {
210 for (
const SCEV *
Op : M->operands())
211 if (!isa<SCEVConstant>(
Op))
217 Sizes.push_back(Step);
221 for (
const SCEV *&Term : Terms) {
234 erase_if(Terms, [](
const SCEV *
E) {
return isa<SCEVConstant>(
E); });
236 if (Terms.
size() > 0)
240 Sizes.push_back(Step);
246 for (
const SCEV *
T : Terms)
255 if (
const SCEVMulExpr *Expr = dyn_cast<SCEVMulExpr>(S))
256 return Expr->getNumOperands();
261 if (isa<SCEVConstant>(
T))
264 if (isa<SCEVUnknown>(
T))
269 for (
const SCEV *
Op : M->operands())
270 if (!isa<SCEVConstant>(
Op))
282 const SCEV *ElementSize) {
283 if (Terms.
size() < 1 || !ElementSize)
292 dbgs() <<
"Terms:\n";
293 for (
const SCEV *
T : Terms)
294 dbgs() << *
T <<
"\n";
308 for (
const SCEV *&Term : Terms) {
318 for (
const SCEV *
T : Terms)
323 dbgs() <<
"Terms after sorting:\n";
324 for (
const SCEV *
T : NewTerms)
325 dbgs() << *
T <<
"\n";
334 Sizes.push_back(ElementSize);
337 dbgs() <<
"Sizes:\n";
338 for (
const SCEV *S : Sizes)
339 dbgs() << *S <<
"\n";
350 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(Expr))
354 const SCEV *Res = Expr;
355 int Last = Sizes.size() - 1;
356 for (
int i =
Last; i >= 0; i--) {
361 dbgs() <<
"Res: " << *Res <<
"\n";
362 dbgs() <<
"Sizes[i]: " << *Sizes[i] <<
"\n";
363 dbgs() <<
"Res divided by Sizes[i]:\n";
364 dbgs() <<
"Quotient: " << *Q <<
"\n";
365 dbgs() <<
"Remainder: " << *R <<
"\n";
392 std::reverse(Subscripts.
begin(), Subscripts.
end());
395 dbgs() <<
"Subscripts:\n";
396 for (
const SCEV *S : Subscripts)
397 dbgs() << *S <<
"\n";
453 const SCEV *ElementSize) {
470 if (Subscripts.
empty())
474 dbgs() <<
"succeeded to delinearize " << *Expr <<
"\n";
475 dbgs() <<
"ArrayDecl[UnknownSize]";
476 for (
const SCEV *S : Sizes)
477 dbgs() <<
"[" << *S <<
"]";
479 dbgs() <<
"\nArrayRef";
480 for (
const SCEV *S : Subscripts)
481 dbgs() <<
"[" << *S <<
"]";
491 "Expected output lists to be empty on entry to this function.");
492 assert(
GEP &&
"getIndexExpressionsFromGEP called with a null GEP");
494 bool DroppedFirstDim =
false;
495 for (
unsigned i = 1; i <
GEP->getNumOperands(); i++) {
498 Ty =
GEP->getSourceElementType();
499 if (
auto *Const = dyn_cast<SCEVConstant>(Expr))
500 if (Const->getValue()->isZero()) {
501 DroppedFirstDim =
true;
508 auto *ArrayTy = dyn_cast<ArrayType>(Ty);
516 if (!(DroppedFirstDim && i == 2))
517 Sizes.push_back(ArrayTy->getNumElements());
519 Ty = ArrayTy->getElementType();
521 return !Subscripts.
empty();
530 auto *SrcGEP = dyn_cast<GetElementPtrInst>(SrcPtr);
540 if (Sizes.empty() || Subscripts.
size() <= 1) {
550 if (!SrcBase || SrcBasePtr != SrcBase->
getValue()) {
555 assert(Subscripts.
size() == Sizes.size() + 1 &&
556 "Expected equal number of entries in the list of size and "
565 Delinearization(
const Delinearization &);
584 O <<
"Delinearization on function " <<
F->getName() <<
":\n";
587 if (!isa<StoreInst>(&Inst) && !isa<LoadInst>(&Inst) &&
588 !isa<GetElementPtrInst>(&Inst))
594 for (
Loop *L = LI->
getLoopFor(BB); L !=
nullptr; L =
L->getParentLoop()) {
605 O <<
"Inst:" << Inst <<
"\n";
606 O <<
"In Loop with Header: " <<
L->getHeader()->getName() <<
"\n";
607 O <<
"AccessFunction: " << *AccessFn <<
"\n";
611 if (Subscripts.
size() == 0 ||
Sizes.size() == 0 ||
613 O <<
"failed to delinearize\n";
617 O <<
"Base offset: " << *BasePointer <<
"\n";
618 O <<
"ArrayDecl[UnknownSize]";
620 for (
int i = 0; i <
Size - 1; i++)
621 O <<
"[" << *Sizes[i] <<
"]";
622 O <<
" with elements of " << *
Sizes[
Size - 1] <<
" bytes.\n";
625 for (
int i = 0; i <
Size; i++)
626 O <<
"[" << *Subscripts[i] <<
"]";
634void Delinearization::getAnalysisUsage(
AnalysisUsage &AU)
const {
640bool Delinearization::runOnFunction(
Function &
F) {
642 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
643 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
648 printDelinearization(O,
F, LI, SE);
651char Delinearization::ID = 0;
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static const SCEV * removeConstantFactors(ScalarEvolution &SE, const SCEV *T)
static const char delinearization_name[]
static bool findArrayDimensionsRec(ScalarEvolution &SE, SmallVectorImpl< const SCEV * > &Terms, SmallVectorImpl< const SCEV * > &Sizes)
static bool containsUndefs(const SCEV *S)
static bool containsParameters(SmallVectorImpl< const SCEV * > &Terms)
static int numberOfTerms(const SCEV *S)
Select target instructions out of generic instructions
mir Rename Register Operands
This header defines various interfaces for pass management in LLVM.
#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())
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()
void setPreservesAll()
Set by analyses that do not transform their input at all.
LLVM Basic Block Representation.
const Function * getParent() const
Return the enclosing method, or null if none.
This class represents an Operation in the Expression.
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
Analysis pass that exposes the LoopInfo for a function.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
A Module instance is used to store all the information related to an LLVM module.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual void print(raw_ostream &OS, const Module *M) const
print - Print out the internal state of the pass.
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
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.
This node represents a polynomial recurrence on the trip count of the specified loop.
This node represents multiplication of some number of SCEVs.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents an analyzed expression in the program.
bool isZero() const
Return true if the expression is a constant zero.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
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 * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
iterator erase(const_iterator CI)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
The instances of the Type class are immutable: once they are created, they are never changed.
LLVM Value Representation.
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
This class implements an extremely fast bulk output stream that can only output to a stream.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
This is an optimization pass for GlobalISel generic memory operations.
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
void collectParametricTerms(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Terms)
Collect parametric terms occurring in step expressions (first step of delinearization).
void findArrayDimensions(ScalarEvolution &SE, SmallVectorImpl< const SCEV * > &Terms, SmallVectorImpl< const SCEV * > &Sizes, const SCEV *ElementSize)
Compute the array dimensions Sizes from the set of Terms extracted from the memory access function of...
FunctionPass * createDelinearizationPass()
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
void computeAccessFunctions(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< const SCEV * > &Sizes)
Return in Subscripts the access functions for each dimension in Sizes (third step of delinearization)...
void initializeDelinearizationPass(PassRegistry &)
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool getIndexExpressionsFromGEP(ScalarEvolution &SE, const GetElementPtrInst *GEP, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< int > &Sizes)
Gathers the individual index expressions from a GEP instruction.
bool tryDelinearizeFixedSizeImpl(ScalarEvolution *SE, Instruction *Inst, const SCEV *AccessFn, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< int > &Sizes)
Implementation of fixed size array delinearization.
void delinearize(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< const SCEV * > &Sizes, const SCEV *ElementSize)
Split this SCEVAddRecExpr into two vectors of SCEVs representing the subscripts and sizes of an array...
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
DelinearizationPrinterPass(raw_ostream &OS)
static void divide(ScalarEvolution &SE, const SCEV *Numerator, const SCEV *Denominator, const SCEV **Quotient, const SCEV **Remainder)