This is an archive of the discontinued LLVM Phabricator instance.

[mlir][sparse] scalarize reductions in for-loops during sparse codegen
ClosedPublic

Authored by aartbik on Dec 11 2020, 2:30 PM.

Details

Summary

Reductions in innermost loops become harder for the backend to disambiguate
after bufferization into memrefs, resulting in less efficient load-update-store
cycles. By scalarizing innermost reductions, the backend is more likely to assign
a register to perform the reduction (also prepares vectorization). Even though
we could scalarize reductions for more outer loops and while-loops as well,
currently scalarization is only done for chains of innermost for-loops, where
it matters most, to avoid complicating codegen unnecessary (viz. adding lots
of yield instructions).

This CL also refactors condition simplification into the merger class,
where it belongs, so that conditions are simplified only once per loop
nest and not repeatedly as was currently done. This CL also fixes a few
minor bugs, some layout issues, and comments.

Diff Detail

Event Timeline

aartbik created this revision.Dec 11 2020, 2:30 PM
aartbik requested review of this revision.Dec 11 2020, 2:30 PM
aartbik edited the summary of this revision. (Show Details)
aartbik updated this revision to Diff 311700.Dec 14 2020, 1:57 PM

trigger test

penpornk accepted this revision.Dec 17 2020, 3:24 PM

I'm so sorry for the delay!

mlir/lib/Dialect/Linalg/Transforms/Sparsification.cpp
55

It's great that we are switching to enum. In the format extension paper there are 6 types [1]. :)

[1] http://tensor-compiler.org/chou-oopsla18-taco-formats.pdf -- page 123:7

103

Should "last tensor" be "2nd-to-last tensor" or "last non-artificial tensor"? (This sounds verbose but it technically isn't the last tensor anymore so we should be clear.)

104

Nit: Maybe add "at the end" after "non-existing tensor"?

155

What does /\_op mean? Do you mean to draw disjunction \/?

214

Should the quick check p0 != p1 be in latGT instead? Or do you want to avoid the function call? (It's small enough and is likely inlined though.)

This revision is now accepted and ready to land.Dec 17 2020, 3:24 PM
aartbik marked 4 inline comments as done.Dec 17 2020, 3:46 PM

Thanks for the review Penporn!

mlir/lib/Dialect/Linalg/Transforms/Sparsification.cpp
55

Yes, the initial goal was to make "not-used" a bit more apparent (rather than sweeping them under the dense carpet ;-), but you are right this also prepares future extension!

103

Yes, last was relative to the given #, but I agree this could be phrased better. Reworded.

155

No, it really is conjunction operator. This may be confusing at first, but check Fred's paper, section 5.1

214

No, because I really want LT, and not LE in this case. I could add a latEQ if you think that is better, and then combine the two into a latLE?

aartbik updated this revision to Diff 312632.Dec 17 2020, 3:54 PM
aartbik marked 3 inline comments as done.

addressed comments

penpornk added inline comments.Dec 17 2020, 4:07 PM
mlir/lib/Dialect/Linalg/Transforms/Sparsification.cpp
214

I think this is fine. Thank you for the clarification! :)

This revision was landed with ongoing or failed builds.Dec 17 2020, 4:12 PM
This revision was automatically updated to reflect the committed changes.