Go to the documentation of this file.
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());
50 struct 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; }
67 struct 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; }
90 struct SCEVHasAddRec {
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; }
124 struct SCEVCollectAddRecMultiplies {
130 : Terms(
T), SE(SE) {}
132 bool follow(
const SCEV *
S) {
133 if (
auto *Mul = dyn_cast<SCEVMulExpr>(
S)) {
134 bool HasAddRec =
false;
138 if (Unknown && !isa<CallInst>(
Unknown->getValue())) {
140 }
else if (Unknown) {
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);
203 int Last = Terms.size() - 1;
204 const SCEV *Step = Terms[Last];
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);
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)
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))
271 Factors.push_back(
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";
318 for (
const SCEV *
T : Terms)
320 NewTerms.push_back(NewT);
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";
385 Subscripts.push_back(R);
390 Subscripts.push_back(Res);
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 <<
"]";
490 assert(Subscripts.empty() && Sizes.empty() &&
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;
504 Subscripts.push_back(Expr);
508 auto *ArrayTy = dyn_cast<ArrayType>(Ty);
515 Subscripts.push_back(Expr);
516 if (!(DroppedFirstDim &&
i == 2))
517 Sizes.push_back(ArrayTy->getNumElements());
519 Ty = ArrayTy->getElementType();
521 return !Subscripts.empty();
527 Delinearization(
const Delinearization &);
546 O <<
"Delinearization on function " <<
F->getName() <<
":\n";
549 if (!isa<StoreInst>(&Inst) && !isa<LoadInst>(&Inst) &&
550 !isa<GetElementPtrInst>(&Inst))
567 O <<
"Inst:" << Inst <<
"\n";
568 O <<
"In Loop with Header: " << L->getHeader()->getName() <<
"\n";
569 O <<
"AccessFunction: " << *AccessFn <<
"\n";
573 if (Subscripts.size() == 0 || Sizes.size() == 0 ||
574 Subscripts.size() != Sizes.size()) {
575 O <<
"failed to delinearize\n";
579 O <<
"Base offset: " << *BasePointer <<
"\n";
580 O <<
"ArrayDecl[UnknownSize]";
581 int Size = Subscripts.size();
582 for (
int i = 0;
i <
Size - 1;
i++)
583 O <<
"[" << *Sizes[
i] <<
"]";
584 O <<
" with elements of " << *Sizes[
Size - 1] <<
" bytes.\n";
588 O <<
"[" << *Subscripts[
i] <<
"]";
596 void Delinearization::getAnalysisUsage(
AnalysisUsage &AU)
const {
604 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
605 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
610 printDelinearization(
O,
F, LI, SE);
A set of analyses that are preserved following a run of a transformation pass.
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Analysis pass that exposes the ScalarEvolution for a function.
This is an optimization pass for GlobalISel generic memory operations.
iterator erase(const_iterator CI)
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
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represents a single loop in the control flow graph.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
The main scalar evolution driver.
FunctionPass * createDelinearizationPass()
The instances of the Type class are immutable: once they are created, they are never changed.
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
The legacy pass manager's analysis pass to compute loop information.
static const char delinearization_name[]
const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
LLVM Basic Block Representation.
void initializeDelinearizationPass(PassRegistry &)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
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.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Represent the analysis usage information of a pass.
This node represents multiplication of some number of SCEVs.
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
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.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
void collectParametricTerms(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Terms)
Collect parametric terms occurring in step expressions (first step of delinearization).
mir Rename Register Operands
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
This class represents an analyzed expression in the program.
inst_range instructions(Function *F)
static bool findArrayDimensionsRec(ScalarEvolution &SE, SmallVectorImpl< const SCEV * > &Terms, SmallVectorImpl< const SCEV * > &Sizes)
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
A Module instance is used to store all the information related to an LLVM module.
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...
const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
bool getIndexExpressionsFromGEP(ScalarEvolution &SE, const GetElementPtrInst *GEP, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< int > &Sizes)
Gathers the individual index expressions from a GEP instruction.
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
static void divide(ScalarEvolution &SE, const SCEV *Numerator, const SCEV *Denominator, const SCEV **Quotient, const SCEV **Remainder)
static bool runOnFunction(Function &F, bool PostInlining)
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...
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
void setPreservesAll()
Set by analyses that do not transform their input at all.
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 means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
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 sort(IteratorTy Start, IteratorTy End)
auto unique(Range &&R, Predicate P)
static const SCEV * removeConstantFactors(ScalarEvolution &SE, const SCEV *T)
INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true, true) FunctionPass *llvm
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
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()
static bool containsParameters(SmallVectorImpl< const SCEV * > &Terms)
static int numberOfTerms(const SCEV *S)
static bool containsUndefs(const SCEV *S)
DelinearizationPrinterPass(raw_ostream &OS)
bool isZero() const
Return true if the expression is a constant zero.
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
Analysis pass that exposes the LoopInfo for a function.