This is an archive of the discontinued LLVM Phabricator instance.

[Polly] Identify and hoist definitively invariant loads
ClosedPublic

Authored by jdoerfert on Sep 26 2015, 2:15 PM.

Details

Summary
As a first step in the direction of assumed invariant loads (loads that are
not written in some context) we now detect and hoist definitively invariant
loads. Invariant loads will be separated from their statements and preloaded
in the code generation. The preloaded value is then used in the new SCoP. If
the load is only conditionally executed the preloaded version will also only
be executed under the same condition, hence we will never access memory that
wouldn't have been accessed otherwise. This is also the most distinguishing
feature compared to licm.

Diff Detail

Event Timeline

jdoerfert updated this revision to Diff 35811.Sep 26 2015, 2:15 PM
jdoerfert retitled this revision from to [Polly] Identify and hoist definitively invariant loads.
jdoerfert added reviewers: grosser, Meinersbur.
jdoerfert updated this object.
jdoerfert added a subscriber: Restricted Project.

Some comments to indicate things I will address.

include/polly/ScopInfo.h
875

replace "the whole SCoP." by "this statement."

1151

Will add something here.

1156

This should be only in the next commit, the same for the "required ones" part in the brief desc.

lib/Analysis/ScopInfo.cpp
2297

This is only needed for the next patch. D13195

lib/CodeGen/BlockGenerators.cpp
1

My bad.

lib/CodeGen/IslNodeBuilder.cpp
822

left over.

Meinersbur edited edge metadata.Sep 26 2015, 3:17 PM

What's the motivational use case that cannot be handled by LICM?

Could you create a separate pass that modifies the ScopInfo, i.e. lib/Transform/HoistInvariantLoads.cpp

Michael

include/polly/CodeGen/IslNodeBuilder.h
209

Grammar? I don't understand this sentence

lib/Analysis/ScopInfo.cpp
1299

list::remove_if

2285

Could you refactor removing a ScopStmt from a Scop into another function so it might be used by other code as well?

lib/CodeGen/IslNodeBuilder.cpp
830

Can you write a comment about how the CFG will look like?

jdoerfert marked an inline comment as done.Sep 26 2015, 3:37 PM

What's the motivational use case that cannot be handled by LICM?

I forgot to split the test cases, sorry. Here is one:

also note the commit message (it is stated there).

Could you create a separate pass that modifies the ScopInfo, i.e. lib/Transform/HoistInvariantLoads.cpp

I am unsure (not if I could but if it makes sense). This patch performs "licm" only as an optimization, true, but from D13195 onwards we will need it as a crucial part of the SCoP generation. Hence, I think it belongs (at least in the long run) in the ScoP class.

include/polly/CodeGen/IslNodeBuilder.h
209

I'll simplify the sentence and add a comma.

lib/Analysis/ScopInfo.cpp
1299

I am unsure. What should I replace by list::remove_if and why?

2285

We can do that easily as soon as another usecase presents itself. If ppl insist we can do it now but I don't see the benefit at the moment.

lib/CodeGen/IslNodeBuilder.cpp
830

I could, but it would just be the CFG from here a couple of times in sequence.

jdoerfert marked an inline comment as done.Sep 27 2015, 8:37 AM

lnt shows no problems, no gains and <10 regressions that are more than noise. However, these regressions sum up to less than 0.5s in total. Hence the detection of invariant loads costs a little bit but not much.

Could you create a separate pass that modifies the ScopInfo, i.e. lib/Transform/HoistInvariantLoads.cpp

I am unsure (not if I could but if it makes sense). This patch performs "licm" only as an optimization, true, but from D13195 onwards we will need it as a crucial part of the SCoP generation. Hence, I think it belongs (at least in the long run) in the ScoP class.

OK

lib/Analysis/ScopInfo.cpp
1299

Does this just remove all elements of MAL from MemAccs? Maybe if not by remove_if (std::std::set_difference), this could be probably rewritten using STL functions. It also looks fragile because it depends on the order of elements in MAL and MemAccs.

Please add at least a comment about what the code is supposed to do.

2238

These do not initialize the Scop, but transform it.

lib/CodeGen/IslNodeBuilder.cpp
830

Linking into files in Phabricator reviews doesn't work for me. It just jumps to a location before it lazily loads the diffs.

You could just refer to that code location in the comment.

This revision was automatically updated to reflect the committed changes.
test/Isl/CodeGen/non-affine-phi-node-expansion.ll