Page MenuHomePhabricator

[Polly] Do not store scalar accesses in InstructionToAccess
ClosedPublic

Authored by Meinersbur on Oct 12 2015, 2:54 PM.

Details

Summary

At code generation, scalar reads are generated before the other statement's instructions, respectively scalar writes after them, in contrast to array accesses which are "executed" with the instructions they are linked to. Therefore it makes sense to not map the scalar accesses to a place of execution. Follow-up patches (e.g. D13762) will also remove some of the directs links from a scalar access to a single instruction, such that only having array accesses in InstructionToAccess ensures its consistency.

Diff Detail

Repository
rL LLVM

Event Timeline

Meinersbur updated this revision to Diff 37177.Oct 12 2015, 2:54 PM
Meinersbur retitled this revision from to [Polly] Store leading and trailing memory accesses separately.
Meinersbur updated this object.
Meinersbur added reviewers: jdoerfert, grosser.
Meinersbur added a project: Restricted Project.
Meinersbur added subscribers: pollydev, llvm-commits.
grosser edited edge metadata.EditedOct 12 2015, 11:12 PM

Hi Michael,

the patch looks generally fine. I am only slightly concerned your removal of the instruction to multiple read/write accesses. As it seems to not be strictly necessary, I wonder if we should rather leave the multi read/write accesses in?

include/polly/ScopInfo.h
746 ↗(On Diff #37177)

I understand that with the currently supported features we now only have a single read/write access per statement, but I do not think this will/should hold in general. If we e.g. model function calls or intrinsics like _atomic_exchange_n this won't hold any more. Hence, I personally would prefer to not specialize too much here.

885 ↗(On Diff #37177)

trailing

lib/Analysis/ScopInfo.cpp
3488 ↗(On Diff #37177)

This pattern seems rather repetitive. It happens five times at least. Does it make sense to add the "if (!Acc) ..." part directly to addMemoryAccess?

This comment was removed by grosser.
jdoerfert added inline comments.Oct 13 2015, 2:01 AM
include/polly/ScopInfo.h
749 ↗(On Diff #37177)

Now that I think about it, maybe leading and trailing is not the best wording here. While it is literally true, it doesn't help to understand why they are leading/trailing. Maybe if we combine leading with the DependentScalars from D13611 and and rename trailing writes in escaping writes the purpose/need becomes clear.

lib/Analysis/ScopInfo.cpp
1375 ↗(On Diff #37177)

You mentioned at some point we should extract the "removeMemoryAccesses" from this function and I now see the need. In D13611 this happened we could use some fancy lambda magic like this to get rid of the weird traversal order if we can still get the same "runtime".

lib/CodeGen/BlockGenerators.cpp
427 ↗(On Diff #37177)

MAVec It's not a list ;)

the patch looks generally fine. I am only slightly concerned your removal of the instruction to multiple read/write accesses. As it seems to not be strictly necessary, I wonder if we should rather leave the multi read/write accesses in?

This was one of the things I was most happy to simplify. No more memory management of lists in lists, or the difficulty to understand when a MemoryAccess is connected to an instruction.

include/polly/ScopInfo.h
746 ↗(On Diff #37177)

D13616 also assumes there is exactly one explicit access per instruction (lookupExplicitAccessFor).

Function calls cannot be modeled with any fixed number of MemoryAccesses.

Atomic exchange is more interesting. Not sure how to model this, it could also be a single MemoryAccess of a special type. If not, it would still be at most one read and one write per instructions, for which we do not need the overhead of a list. (e.g. two maps InstructionToReadAccess+InstructionToWriteAccess; or a single map to a pair<MemoryAccess*,MemoryAccess*>)

749 ↗(On Diff #37177)

I don't know what DependentScalars are meant to be, but those reads are not 'dependent' nor necessarily scalars (but also PHIs).

'writes' are also not escaping. Escaping also already has a meaning of values that are used after the scop.

For me, a name describing the content is sufficient. There can be multiple reasons why something is in there, which can be described in a comment.

lib/Analysis/ScopInfo.cpp
1375 ↗(On Diff #37177)

Shouldn't that be a separate patch?

3488 ↗(On Diff #37177)

No, Acc is added to different lists each time.

The alternative would be to have some detection logic in addMemoryAccess to which list the access it to add, but more error prone than simple NULL checks.

Meinersbur added a comment.

In http://reviews.llvm.org/D13676#265724, @grosser wrote:

> the patch looks generally fine. I am only slightly concerned your removal of the instruction to multiple read/write accesses. As it seems to not be strictly necessary, I wonder if we should rather leave the multi read/write accesses in?

This was one of the things I was most happy to simplify. No more memory management of lists in lists, or the difficulty to understand when a MemoryAccess is connected to an instruction.

With this patch but multiple accesses per instruction we would still
simplify both. All MemoryAccesses connected to an instruction would be
real (explicit) memory accesses (maybe) caused by that instruction.

================
Comment at: include/polly/ScopInfo.h:746
@@ +745,3 @@
+ /// @brief Mapping from instructions to explicit memory accesses.
+ DenseMap<const Instruction *, MemoryAccess *> InstructionToAccess;
+


grosser wrote:
> I understand that with the currently supported features we now only have a single read/write access per statement, but I do not think this will/should hold in general. If we e.g. model function calls or intrinsics like _atomic_exchange_n this won't hold any more. Hence, I personally would prefer to not specialize too much here.
D13616 also assumes there is exactly one explicit access per instruction (lookupExplicitAccessFor).

Because at the moment there is. But that is different from cutting
support for something else. I only used the fact that there can be at
most one explicit access at the moment to simplify the algorithm.

Function calls cannot be modeled with any fixed number of MemoryAccesses.

I am not sure how this generalization is helping the discussion or what
it even means. In any way, that sentence above doesn't suffice to
ignore the function call modeling problem.

Atomic exchange is more interesting. Not sure how to model this, it could also be a single MemoryAccess of a special type. If not, it would still be at most one read and one write per instructions, for which we do not need the overhead of a list. (e.g. two maps InstructionToReadAccess+InstructionToWriteAccess; or a single map to a pair<MemoryAccess*,MemoryAccess*>)

================
Comment at: include/polly/ScopInfo.h:749
@@ +748,3 @@
+ /// @brief Implicit loads at the beginning of a statement.
+ MemoryAccessVec LeadingReads;
+


jdoerfert wrote:
> Now that I think about it, maybe leading and trailing is not the best wording here. While it is literally true, it doesn't help to understand why they are leading/trailing. Maybe if we combine leading with the DependentScalars from D13611 and and rename trailing writes in escaping writes the purpose/need becomes clear.
I don't know what DependentScalars are meant to be, but those reads are not 'dependent' nor necessarily scalars (but also PHIs).

  1. DependentScalars are scalars that need to be recomputed in order to generate code for that statement (it says something like this in the comment). Leading loads are scalars that need to be reloaded in order to .. (copy text from above). Already the definition is so similar that we should merge those two.
  2. Generally PHIs and PHI operands are considered scalars too.

'writes' are also not escaping. Escaping also already has a meaning of values that are used after the scop.

Escaping the block/statement or escaping the SCoP, whatever. In the end
it is almost the same and it is not important. Important is that they
need to be communicated from the defining statement (where they escape)
to somewhere else and we do that via memory. That they are tailing the
statement is a mere side effect and isn't even like that at the moment.

For me, a name describing the content is sufficient. There can be multiple reasons why something is in there, which can be described in a comment.

I don't understand this part. Are you saying leading/trailing are
descriptive enough to understand what is going on and why?

================
Comment at: lib/Analysis/ScopInfo.cpp:1375
@@ -1360,7 +1374,3 @@

  • // Remove all memory accesses in @p InvMAs from this statement together
  • // with all scalar accesses that were caused by them. The tricky iteration
  • // order uses is needed because the MemAccs is a vector and the order in
  • // which the accesses of each memory access list (MAL) are stored in this
  • vector is reversed. + Remove the MemoryAccess from all lists. for (MemoryAccess *MA : InvMAs) { ---------------- jdoerfert wrote: > You mentioned at some point we should extract the "removeMemoryAccesses" from this function and I now see the need. In D13611 this happened we could use some fancy lambda magic like this to get rid of the weird traversal order if we can still get the same "runtime". Shouldn't that be a separate patch?

Yes, and if it would happen prior to any of those we would have
smaller diffs, thus my comment.

================
Comment at: lib/Analysis/ScopInfo.cpp:3488
@@ -3458,1 +3487,3 @@
+ return;
+ Acc->getStatement()->addLeadingLoad(Acc);

}

grosser wrote:
> This pattern seems rather repetitive. It happens five times at least. Does it make sense to add the "if (!Acc) ..." part directly to addMemoryAccess?
No, Acc is added to different lists each time.

The alternative would be to have some detection logic in addMemoryAccess to which list the access it to add, but more error prone than simple NULL checks.

We could simply hand the list to the method instead of guessing?

In any case:
{

...
if (!A)
  return
B;

}

>

{

...
if (A)
  B;

}

http://reviews.llvm.org/D13676

As both of you voted for keeping the InstructionToAccess as a map-of-lists, I will undo that part in an update.

Meinersbur updated this revision to Diff 37254.Oct 13 2015, 8:15 AM
Meinersbur updated this object.
Meinersbur edited edge metadata.

Make InstructionToAccess a map-of-lists again, consistently use LeadingLoads/TrailingStores in BlockGenerator. addressing smaller comments

================
Comment at: include/polly/ScopInfo.h:746
@@ +745,3 @@
+ /// @brief Mapping from instructions to explicit memory accesses.
+ DenseMap<const Instruction *, MemoryAccess *> InstructionToAccess;
+


grosser wrote:
> I understand that with the currently supported features we now only have a single read/write access per statement, but I do not think this will/should hold in general. If we e.g. model function calls or intrinsics like _atomic_exchange_n this won't hold any more. Hence, I personally would prefer to not specialize too much here.
D13616 also assumes there is exactly one explicit access per instruction (lookupExplicitAccessFor).

Because at the moment there is. But that is different from cutting
support for something else. I only used the fact that there can be at
most one explicit access at the moment to simplify the algorithm.

Function calls cannot be modeled with any fixed number of MemoryAccesses.

I am not sure how this generalization is helping the discussion or what
it even means. In any way, that sentence above doesn't suffice to
ignore the function call modeling problem.

How do you model a function calls that accesses data like this:

for (int i = 0; i < n; i+=1)
   A[i] = xyz;

The number of accesses is only known at runtime, hence one cannot add a MemoryAccess for each write.

'writes' are also not escaping. Escaping also already has a meaning of values that are used after the scop.

Escaping the block/statement or escaping the SCoP, whatever. In the end
it is almost the same and it is not important. Important is that they
need to be communicated from the defining statement (where they escape)
to somewhere else and we do that via memory. That they are tailing the
statement is a mere side effect and isn't even like that at the moment.

This patch depends on D13487. Sorry, seems I didn't mark it as such.

For me, a name describing the content is sufficient. There can be multiple reasons why something is in there, which can be described in a comment.

I don't understand this part. Are you saying leading/trailing are
descriptive enough to understand what is going on and why?

It is enough to know what the vectors contains, which is all that matters for their names. How elements are put in there and what they are used for is better explained in a comment.

================
Comment at: lib/Analysis/ScopInfo.cpp:1375
@@ -1360,7 +1374,3 @@

  • // Remove all memory accesses in @p InvMAs from this statement together
  • // with all scalar accesses that were caused by them. The tricky iteration
  • // order uses is needed because the MemAccs is a vector and the order in
  • // which the accesses of each memory access list (MAL) are stored in this
  • vector is reversed. + Remove the MemoryAccess from all lists. for (MemoryAccess *MA : InvMAs) { ---------------- jdoerfert wrote: > You mentioned at some point we should extract the "removeMemoryAccesses" from this function and I now see the need. In D13611 this happened we could use some fancy lambda magic like this to get rid of the weird traversal order if we can still get the same "runtime". Shouldn't that be a separate patch?

Yes, and if it would happen prior to any of those we would have
smaller diffs, thus my comment.

I cannot work on hypothetical patches. When I asked that editing ScopStmt could be refactored out, you said when necessary. It hasn't become more necessary with this patch. However, I'd welcome if you commit such refactoring either prior of after this patch.

Could you answer withing the web interface? Phabricator screws up formatting from emails and has "llvm-commits" as author.

Meinersbur updated this revision to Diff 37692.Oct 17 2015, 3:22 PM

rebase to r250627

Meinersbur updated this revision to Diff 40156.Nov 13 2015, 9:08 AM

Rebase to 252942, fix for Isl/Ast/runtime_context_with_error_blocks.ll

Meinersbur updated this revision to Diff 41231.Nov 26 2015, 4:47 AM

Rebase to r254150

Rebase to r254343

Hi Michael,

from my perspective the patch looks good to me, except the name concerns Johannes raised. Having looked into some of the other patches, I see this small (but apparently recurring) issue again. I started a mailing list discussion to hopefully resolve this once and for all.

Best,
Tobias

include/polly/ScopInfo.h
685 ↗(On Diff #41466)

This change is unrelated. Please commit it separately.

Meinersbur updated this revision to Diff 42578.Dec 11 2015, 2:16 PM
Meinersbur updated this object.

Rebase to r255107; remove not required changes mostly in comments.

Meinersbur updated this revision to Diff 42673.Dec 13 2015, 3:12 PM
Meinersbur updated this object.

Rebase to r255474; use new naming scheme for access kinds.

Meinersbur updated this revision to Diff 42727.Dec 14 2015, 8:57 AM
Meinersbur retitled this revision from [Polly] Store leading and trailing memory accesses separately to [Polly] Do not store scalar accesses in InstructionToAccess.
Meinersbur updated this object.

Remove explicit LeadingReads and TrailingWrites vectors; they are implicit by iterating over all MemoryAccesses with a filter

Thank you Michael for this rebase. This new change is now clearly minimal such that we can now focus on the semantic change.

There are good points for this patch:

We currently do not use the InstructionToArray mapping for scalars, it was originally not introduced with scalars in mind and - in fact - us adding scalars to this mapping introduced bugs at various places (which I just fixed).

As your patch also allows us to avoid the construction of redundant scalar memory accesses in a ScopStmt, I am clearly in favor of adding it.

I understand that in certain situations we might want to know if an instruction caused scalar memory accesses, but I think such information should probably be maintained separately. Adding functionality seems to be rather simple (and orthogonal). Hence, we can do it when the need arises.

From my point this patch is ready to commit, but let's see if people at the phone call tonight have any further thoughts.

grosser accepted this revision.Dec 18 2015, 2:38 AM
grosser edited edge metadata.

Accepted if my minor comments have been addressed.

This revision is now accepted and ready to land.Dec 18 2015, 2:38 AM
Meinersbur updated this revision to Diff 43333.Dec 20 2015, 9:22 AM
Meinersbur edited edge metadata.
Meinersbur marked 2 inline comments as done.

Rebase to r256124

Accepted if my minor comments have been addressed.

What comments are you referring to?

No comments. I thought I had some, but I did not.
It's fine to commit as it is.

Tobias

This revision was automatically updated to reflect the committed changes.