This is an archive of the discontinued LLVM Phabricator instance.

[Polly] DeLICM/DePRE (WIP)
ClosedPublic

Authored by Meinersbur on Sep 19 2016, 2:27 AM.

Details

Summary

Implement -polly-delicm pass. The pass intends to undo the effects of LoadInvariantCodeMotion and GVN's Partial Redundancy Elimination (Load PTR) which adds additional scalar dependencies into scops.

DeLICM/DePRE will try to map those scalars back to the array elements they were promoted from, as long as the array element is unused.

This is work in progress. The patch is not as tidy as it could be, not all functions have been commended yet, most test cases fail and some refactoring is still planned.

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
grosser added inline comments.Jan 21 2017, 2:00 AM
include/polly/DeLICM.h
61

InclRedef=true RETURNS a

67

ARE ignored

70

"as where" -- Not sure what this means. Do you want to say:

"Whether to include the definition's timepoint to the set of well-defined elements"

You can probably also drop the "Whether to" at the beginning of the sentence.

72

enabling THIS OPTION adds

97

RESULTS in:

102

IS overwritten THE FIRST TIME by Write

"when before timepoint" : when what is before timepoint? Can you add the object for clarity? Is it "the write at timepoint [i] is before timepoint 0"?

108

ARE ignored

111

"an overwrite timepoints": the numerus seems to not match

146

The result IS

159

ARE ignored

164

load READS

166

loads use

167

THAT it had

175

written IS used

176

IS considered

lib/Transform/DeLICM.cpp
23

i.e.,

24

isl rational

40

i.e., strictly speaking

59

isl reference (isl is written lowercase)

follow isl syntax

230

I would place the "." after the ")"

256

"." after ")"

296

IN the result

298

IN the result

303

isl max

330

i.e.,

353

does not

355

i.e.,

500

are ignored.

504

comment flow seems wrong (below as well)

552

AND

does not need

611

comment flow seems wrong

650

compute_divs can sometimes make a map a lot more complex. Did you had a case where this is necessary.

We also should ask sven at some point if he can provide a simplify function for isl that does all simplifications in the right order.

678

"." at the end?

696

"st."?

708

of the contents <sth missing here?> any array elements in any zone

711

one OF three

712

so A transformation

715

Leftover documentation from the 'Known' part?

731

problems problem?

732

known ? Is this a leftover?

733

Last sentence is incomplete

838

Comment flow broken.

849

ARE the new lifetimes required for proposed UNUSED in existing?

895

? at the end

917

isl

942

a reference a counter????

949

I doubt this has any performance impact. I would prefer to keep the state local and not pollute global space with such caching things.

1076

IS as

1115

Get

1117

IS as

1209

A MemoryKind::Value ... A MemoryKind

1214

A ... A

1226

the transformation IS applied to the

1276

WITH each other

1339

of A

1399

HAS.

1520

comment flow broken

1532

USED?

1657

Map A

unittests/DeLICM/DeLICMTest.cpp
23

indef -> undef?

Meinersbur marked 39 inline comments as done.Jan 21 2017, 3:20 PM
Meinersbur added inline comments.
lib/Transform/DeLICM.cpp
650

I am not aware that this can make sets more complex, it just provides an additional explicit representation of a div that should make follow-up computations faster and was sometimes necessary for coalescing.

According to the source comments the issue is rather that compute_divs can be an expensive operation, but so is coalescing. If possible I'd not call simplify() at all but that results in other operations taking much longer, e.g. lexmin.

unittests/DeLICM/DeLICMTest.cpp
23

This refers to the definition of indef below

Meinersbur updated this revision to Diff 85252.Jan 21 2017, 4:00 PM
  • Address Tobias' comments

Hi Michael,

some of the comments from our discussion.

Best,
Tobias

include/polly/DeLICM.h
36

Add comment?

lib/Transform/DeLICM.cpp
40

Comma after i.e., missing.

83

Maybe give an overview comment describing the high-level structure of this approach.

355

Comma after i.e., missing.

496

Several of these functions above are not really tied to your DeLICM approach, but are generally useful. I would suggest to add these separately in an ISLTools.cpp file, in the optimal case with separate unit tests.

You can probably already upstream these today.

650

OK. We probably need to evaluate this in practice. Let's start with what you have.

708

Pull in getAccessRelation.

942

Drop this one as well?

1076

IS BE?? Just 'is as'?

1111

The above all really seem to be belong into ScopInfo. Let's leave them here for know, as this makes updating this patch easier, but maybe we can keep in mind that we want to unify this at some point.

1791

OK. I think this functionality should at some point be merged with ScopInfo, but let's leave it here for know to reduce the dependences to ScopInfo.

1864

I believe we should not use auto so much. As you correctly pointed out, auto is suggested by LLVM to be only used in rare cases. We had in Barcelone a discussion how much we should use auto and it seems we choose a rather liberal direction. I now believe that following LLVM here closer is better.

Now, currently auto makes sense as it saves the long IslPTr<.....> type so you probably do not need to change anything here immediately. We should just keep this in mind, when potentially switching to the C++ bindings.

unittests/DeLICM/DeLICMTest.cpp
424

To fix formatting, maybe use:

struct {
  type *Known, type *undef, type *written, type *unkown
} input;

void foo() {
  EXPECT_FALSE(conflicts(
      {aasdfsadf, basdfsadf, casdfasf, dsadfsadfsadfdsafdsafsafdfasdfsadf},
      {a, basdfsafd, casdfdsaf, dsadfsadf}));
}
427

It also seems as if these tests still cover the Known part. It would be nice if we could have a set of simpler tests that just take the current simpler isConflicting implementation and do not go through the complexity of checkIsConflicting.

Meinersbur updated this revision to Diff 86279.Jan 30 2017, 6:31 AM
Meinersbur marked 26 inline comments as done.
  • Rebase to r293429
  • Remove MapReport
  • Review isConflicting unittests.
  • Address remaining comments

Hi Michael,

thanks a lot for the very nice cleanup. I am very glad this patch proceeds this way. I may now seem to be very picky, but I really try to understand this one in detail. I added a bunch of smaller comments. I am not yet fully through, but believe I identified a new set of changes we can commit. All of checkConvertZoneToTimepoint, computeReachingDefinition, computeReachingOverwrite, and checkComputeArrayUnused are clearly self-contained and thanks to your nice unit tests are now easy to test independently. I suggest you commit them one-by-one. I did not go through all corner cases, but as they are well tested that seems to be fine.

The only concern I have is that there is some -- possibly unnecessary -- code duplication between computeReachingDefinition and computeReachingOverwrite, which I would prefer to avoid.

I also noted that you provide implementations for all corner cases always including or not including bounds. On the other side, most of the actual code is currently not using any of these (there is commonly only one configuration used). As this all looks very well tested, I don't want to ask you to drop all the special cases, especially as I have the impression that these may be useful for some of the later code or later discussions on how to model certain things best. Hence, I am fine leaving them in. However, if you have any cases in mind that are certainly not needed any more, don't hesitate to drop them.

As a next step, I will go through Knowledge and isConflicting.

Best,
Tobias

include/polly/DeLICM.h
45

The set OF timepoints

51

IS overwritten

79

This is only ever called with InclStart = true and InclEnd=false. Is this intentional and do you keep the other options just for completness?

146

(dover)write -> (over)write

180

NOT read in between

lib/Transform/DeLICM.cpp
135

one definition PER SCoP

143

The definition (write MemoryAccess) of a MemoryKind::Value scalar.

definitions -> definion
/ -> ()
an ->a

148

uses (read MemoryAccesses) of a MemoryKind::Value

/ -> ()
an -> a

152

The PHI instruction (read Memory Access) of a MemoryKind::PHI or MemoryKind::ExitPHI.

/ -> ()
an -> a
/ -> or (makes clear if this is an 'or' or an 'and')

156

List of all incoming values (write MemoryAccesses) for a MemoryKind::PHI or MemoryKind::ExitPHI scalar.

175

This fits into two lines

245

This is only ever called with

computeScalarReachingOverwrite(Schedule, TargetDom, false, true);

295

This is only ever called with "computeScalarReachingDefinition(Schedule, Domain, false, true)".

1489

The previous four lines can be dropped, but changing !MA->isWrite() to !MA->isMustWrite() a couple of lines earlier.

1709

This is only called with:

auto ArrayUnused = computeArrayUnused(Schedule, AllMustWrites, AllReads,

unittests/DeLICM/DeLICMTest.cpp
23

Right, I still don't understand why you call this 'indef'. This seems to be an abbreviation of "undefined", but then I would expect this word to be called "undef". What does "indef" stand for?

grosser added inline comments.Feb 3 2017, 8:33 AM
lib/Transform/DeLICM.cpp
187

This fits into two lines.

235

What is an "overwrite timepoints"?

284

What does not need to be specified?

and therefore THIS ELEMENT does not ...

356

of TWO states

370

the theses?

KnowledgeS need to know

468

This -> Existing
That -> Proposed

?

560

must be the declared .. Grammar?

619

before other accessES AND

621

Is this true? What about region statements that write to a PHI node?

638

Maybe add a test case?

641

If you add a continue above, the second MA->isWrite is not needed. This reduces indentation and also makes clear that this is an if-else construct.

647

What would be such a case? Is there an easy opportunity for a test case?

653

Should we have a test case for this? (including a comment in the test case that states that this is the reason it is not DeLICMed)

655

Should we have a test case for this? (including a comment in the test case that states that this is the reason it is not DeLICMed.

685

No {}.

689

No {}.

712

is as narrow

Drop 'be'

820

Are the last two definitions dead?

1617

Should this be ScatterRead instead of ScatterUse? You do not seem to modify the range. In computeReachingOverwrite you seem to call it ScatterRead as well.

1651

This assert is missing in computeReachingDefinition

1668

This should be called AfterMap, right? Maybe an oversight when renaming and adopting computeReachingDefinition?

1692

In computeReachingDefinition SelfUse has been hoisted outside the condition. Not a semantic difference, but a minor change that lets the code look different.

1702

Besides the comparisions isl_map_lex_lt/isl_map_lex_le this function seems to be indentical with computeReachingDefinition. It feels to me as if this is unnecessary complication of rather complicated code. Would it make sense to have one common implementation that just takes a comparision function to then deliver the two different implementations?

Hi Michael,

I just looked closer into Knowledge and isConflicting.

To me it is not well documented what "implicit" means. As far as I understand implicit means that only one of unknown and unused is actually stored and the other one is "implicitly" the opposite. It would be good to document this and also give a reason why you implemented it this way. I assume because the complement of one of these sets can possibly be very large.

I am not sure if Knowledges must be implicit or if also both sets can be explicit. In isConflicting you state "current implementation requires it to be implicit", but when testing you seem to compute two explicit sets using completeLifetime. This seems inconsistent.

Do you have an example that makes clear why you need zones, and cannot just track the values / life ranges? That seems like an interesting test for isConflicting.

Assuming both implicit and explicit representation are supported. I wonder if one of them would be enough? Or is there a reason to keep both? I have the feeling that having both currently makes the code (unnecessarily) hard to read?

That's all for now. I will later look into the remaining stuff.

lib/Transform/DeLICM.cpp
403

a nullptr

435

What does it mean to be implicitly unused. Can you somehow print this, e.g. as "universe - Occupied".

What happens if the first set does not contain elements from each space? Assuming we never write to a given array? This would mean it does not appear in Occupied and is completely unused. Now, the universe we compute won't contain an element from this space, after the (implicit) subtraction it won't appear, right?

You seem to be working around this in the tests, but it is not clear how this is resolved in general or which preconditions need to be satisfied to make this work.

450

The previous line does not have any test coverage? Should we just assert that such a condition is not expected to arise? Or is there a test case that would cover this situation? (Same for the condition below).

454

The previous line does not have any test coverage.

465

WITH each other

477

What do you mean by "use case X" here?

477

What do you mean with 'use case X'?

I am surprised that the current implementation only works with the first parameter being "implicit" unknown. It seems the tests provide an explicit representation of "unknown", no?

I tried to assert(!Existing.Occupied), but this fails (due to the tests using explicit constraints.

1761

Why do we move this stuff here? This does not seem to be performance sensitive.

unittests/DeLICM/DeLICMTest.cpp
379

Why do you compute the universe here? I was under the impression that Knowledges can also be created with implicit Unkown, Unused sets and should work well with them. In fact, there is a comment in isConflicting that claims that it _only_ works with implicit sets?

Would the tests still work if you do not create explicit representations of Unknown and Unused?

397

vs.

Also end this and the sentences below with "."

419

Maybe add a comment that states why these two conflict. Dom[1] is a zone that covers [0,1]. This took me a little while to understand.

Meinersbur marked 43 inline comments as done.Feb 3 2017, 2:41 PM

Thanks for the review

I also noted that you provide implementations for all corner cases always including or not including bounds. On the other side, most of the actual code is currently not using any of these (there is commonly only one configuration used). As this all looks very well tested, I don't want to ask you to drop all the special cases, especially as I have the impression that these may be useful for some of the later code or later discussions on how to model certain things best. Hence, I am fine leaving them in. However, if you have any cases in mind that are certainly not needed any more, don't hesitate to drop them.

I feel relative strongly about keeping them. They were certainly helpful in development when I did not yet have a singular definition of what a "zone" is. Currently a zone 0 < 1 < 1 is consistently represented by the integer set { [1] }. There is no strict necessity to fo this everywhere. E.g. it might be more intuitive to use the start of the range instead. These computations are currently agnostic to what a zone is (could be moved to ISLTools.cpp as well maybe?) and I would perceive it as a loss when they suddenly would.

I am not sure if Knowledges must be implicit or if also both sets can be explicit. In isConflicting you state "current implementation requires it to be implicit", but when testing you seem to compute two explicit sets using completeLifetime. This seems inconsistent.

That is comment was outdated. In previous revisions Unused, Known and Unknown was stored in the same map (instead in one Unsued and one Occupied). Two of them had to be defined, the third was implicit, hence "required" to be implicit.

Do you have an example that makes clear why you need zones, and cannot just track the values / life ranges? That seems like an interesting test for isConflicting.

See file comment in DeLICM.cpp

Assuming both implicit and explicit representation are supported. I wonder if one of them would be enough? Or is there a reason to keep both? I have the feeling that having both currently makes the code (unnecessarily) hard to read?

It's just the opposite, it makes it clearer that Unused/Occupied can be nullptr and therefore easier to understand. Previous versions of this patch used a flag which one is implicit, hence also requiring that one of the is implicit. I invite you to look into these versions to see if whether they are easier to understand.

The sets can be nullptr only because we want avoid computing them, not because of something conceptional. If they are still given, they are ignored. This is fine for the unit tests which are small, but the complement operation blew up easily in my experiments with even small programs.

Michael

lib/Transform/DeLICM.cpp
435

What does it mean to be implicitly unused.

The unused set has not been computed explicitly, but is assumed to be the complement of Occupied

Can you somehow print this, e.g. as "universe - Occupied".

I don't understand this suggestion.

What happens if the first set does not contain elements from each space?

Does not happen. In ZoneAlgorithm one of the two sets will always be implicit. In DeLICMTests unionSpace() is used.

Assuming we never write to a given array? This would mean it does not appear in Occupied and is completely unused. Now, the universe we compute won't contain an element from this space, after the (implicit) subtraction it won't appear, right?

As there is no write to the array, greedyCollapse() will not try to map anything to it.

621

True since commit r258809: Unique phi write accesses

638

You previously asked me to remove the non-"After Accesses" parts from the test cases. This currently cannot be tested effectively without more diagnostics.

There would be the possibility to copy reduction_preheader.ll a few times and add variations. In most cases the variations would already cause it not to be mapped (longer lifetimes), not because the SCoP is incompatible (Test would succeed even if this check was removed)

So I could add loads/store combinations to other array elements than the ones necessary for at least one mapping. But in the mid term I'd only want to mark the elements as incompatible, not the entire SCoP. That would then require to rewrite all tests.

Originally I intended to more systematically test all combinations of loads and stores orders in one ScopStmt when more diagnostics is available. I'd add that separately sometime later.

647

memcpy, memmove, memset

About testing, see comment above

653

About testing, see comment above

655

About testing, see comment above

1489

That wouldn't print a debug message.

1761

This is to avoid to exposing Knowledge only for testing isConflicting.

unittests/DeLICM/DeLICMTest.cpp
379

Why do you compute the universe here?

To compute an argument that got only a nullptr.

I was under the impression that Knowledges can also be created with implicit Unkown, Unused sets and should work well with them. In fact, there is a comment in isConflicting that claims that it _only_ works with implicit sets?

See main comment.

Would the tests still work if you do not create explicit representations of Unknown and Unused?

Yes, but the explicit representation is ignored.

Meinersbur updated this revision to Diff 87032.Feb 3 2017, 2:51 PM
Meinersbur marked 2 inline comments as done.
  • Rebase to r293890
  • Address Tobias' comments
  • Merge reachingDefinition and reachingOverwrite to reachingWrite
  • Revise unittests

Thanks for the review

I also noted that you provide implementations for all corner cases always including or not including bounds. On the other side, most of the actual code is currently not using any of these (there is commonly only one configuration used). As this all looks very well tested, I don't want to ask you to drop all the special cases, especially as I have the impression that these may be useful for some of the later code or later discussions on how to model certain things best. Hence, I am fine leaving them in. However, if you have any cases in mind that are certainly not needed any more, don't hesitate to drop them.

I feel relative strongly about keeping them. They were certainly helpful in development when I did not yet have a singular definition of what a "zone" is. Currently a zone 0 < 1 < 1 is consistently represented by the integer set { [1] }. There is no strict necessity to fo this everywhere. E.g. it might be more intuitive to use the start of the range instead. These computations are currently agnostic to what a zone is (could be moved to ISLTools.cpp as well maybe?) and I would perceive it as a loss when they suddenly would.

Sure, that's why I said I am fine with these to be kept in the current generality, as long as they are well

I am not sure if Knowledges must be implicit or if also both sets can be explicit. In isConflicting you state "current implementation requires it to be implicit", but when testing you seem to compute two explicit sets using completeLifetime. This seems inconsistent.

That is comment was outdated. In previous revisions Unused, Known and Unknown was stored in the same map (instead in one Unsued and one Occupied). Two of them had to be defined, the third was implicit, hence "required" to be implicit.

Do you have an example that makes clear why you need zones, and cannot just track the values / life ranges? That seems like an interesting test for isConflicting.

See file comment in DeLICM.cpp

Assuming both implicit and explicit representation are supported. I wonder if one of them would be enough? Or is there a reason to keep both? I have the feeling that having both currently makes the code (unnecessarily) hard to read?

It's just the opposite, it makes it clearer that Unused/Occupied can be nullptr and therefore easier to understand. Previous versions of this patch used a flag which one is implicit, hence also requiring that one of the is implicit. I invite you to look into these versions to see if whether they are easier to understand.

The sets can be nullptr only because we want avoid computing them, not because of something conceptional. If they are still given, they are ignored. This is fine for the unit tests which are small, but the complement operation blew up easily in my experiments with even small programs.

Michael

Thanks for the review

I also noted that you provide implementations for all corner cases always including or not including bounds. On the other side, most of the actual code is currently not using any of these (there is commonly only one configuration used). As this all looks very well tested, I don't want to ask you to drop all the special cases, especially as I have the impression that these may be useful for some of the later code or later discussions on how to model certain things best. Hence, I am fine leaving them in. However, if you have any cases in mind that are certainly not needed any more, don't hesitate to drop them.

I feel relative strongly about keeping them. They were certainly helpful in development when I did not yet have a singular definition of what a "zone" is. Currently a zone 0 < 1 < 1 is consistently represented by the integer set { [1] }. There is no strict necessity to fo this everywhere. E.g. it might be more intuitive to use the start of the range instead. These computations are currently agnostic to what a zone is (could be moved to ISLTools.cpp as well maybe?) and I would perceive it as a loss when they suddenly would.

I am not sure if Knowledges must be implicit or if also both sets can be explicit. In isConflicting you state "current implementation requires it to be implicit", but when testing you seem to compute two explicit sets using completeLifetime. This seems inconsistent.

That is comment was outdated. In previous revisions Unused, Known and Unknown was stored in the same map (instead in one Unsued and one Occupied). Two of them had to be defined, the third was implicit, hence "required" to be implicit.

Do you have an example that makes clear why you need zones, and cannot just track the values / life ranges? That seems like an interesting test for isConflicting.

See file comment in DeLICM.cpp

Assuming both implicit and explicit representation are supported. I wonder if one of them would be enough? Or is there a reason to keep both? I have the feeling that having both currently makes the code (unnecessarily) hard to read?

It's just the opposite, it makes it clearer that Unused/Occupied can be nullptr and therefore easier to understand. Previous versions of this patch used a flag which one is implicit, hence also requiring that one of the is implicit. I invite you to look into these versions to see if whether they are easier to understand.

The sets can be nullptr only because we want avoid computing them, not because of something conceptional. If they are still given, they are ignored. This is fine for the unit tests which are small, but the complement operation blew up easily in my experiments with even small programs.

Michael

Thanks for the review

I also noted that you provide implementations for all corner cases always including or not including bounds. On the other side, most of the actual code is currently not using any of these (there is commonly only one configuration used). As this all looks very well tested, I don't want to ask you to drop all the special cases, especially as I have the impression that these may be useful for some of the later code or later discussions on how to model certain things best. Hence, I am fine leaving them in. However, if you have any cases in mind that are certainly not needed any more, don't hesitate to drop them.

I feel relative strongly about keeping them. They were certainly helpful in development when I did not yet have a singular definition of what a "zone" is. Currently a zone 0 < 1 < 1 is consistently represented by the integer set { [1] }. There is no strict necessity to fo this everywhere. E.g. it might be more intuitive to use the start of the range instead. These computations are currently agnostic to what a zone is (could be moved to ISLTools.cpp as well maybe?) and I would perceive it as a loss when they suddenly would.

I am not sure if Knowledges must be implicit or if also both sets can be explicit. In isConflicting you state "current implementation requires it to be implicit", but when testing you seem to compute two explicit sets using completeLifetime. This seems inconsistent.

That is comment was outdated. In previous revisions Unused, Known and Unknown was stored in the same map (instead in one Unsued and one Occupied). Two of them had to be defined, the third was implicit, hence "required" to be implicit.

Do you have an example that makes clear why you need zones, and cannot just track the values / life ranges? That seems like an interesting test for isConflicting.

See file comment in DeLICM.cpp

Assuming both implicit and explicit representation are supported. I wonder if one of them would be enough? Or is there a reason to keep both? I have the feeling that having both currently makes the code (unnecessarily) hard to read?

It's just the opposite, it makes it clearer that Unused/Occupied can be nullptr and therefore easier to understand. Previous versions of this patch used a flag which one is implicit, hence also requiring that one of the is implicit. I invite you to look into these versions to see if whether they are easier to understand.

The sets can be nullptr only because we want avoid computing them, not because of something conceptional. If they are still given, they are ignored. This is fine for the unit tests which are small, but the complement operation blew up easily in my experiments with even small programs.

Michael

Thanks for the review

I also noted that you provide implementations for all corner cases always including or not including bounds. On the other side, most of the actual code is currently not using any of these (there is commonly only one configuration used). As this all looks very well tested, I don't want to ask you to drop all the special cases, especially as I have the impression that these may be useful for some of the later code or later discussions on how to model certain things best. Hence, I am fine leaving them in. However, if you have any cases in mind that are certainly not needed any more, don't hesitate to drop them.

I feel relative strongly about keeping them. They were certainly helpful in development when I did not yet have a singular definition of what a "zone" is. Currently a zone 0 < 1 < 1 is consistently represented by the integer set { [1] }. There is no strict necessity to fo this everywhere. E.g. it might be more intuitive to use the start of the range instead. These computations are currently agnostic to what a zone is (could be moved to ISLTools.cpp as well maybe?) and I would perceive it as a loss when they suddenly would.

I am not sure if Knowledges must be implicit or if also both sets can be explicit. In isConflicting you state "current implementation requires it to be implicit", but when testing you seem to compute two explicit sets using completeLifetime. This seems inconsistent.

That is comment was outdated. In previous revisions Unused, Known and Unknown was stored in the same map (instead in one Unsued and one Occupied). Two of them had to be defined, the third was implicit, hence "required" to be implicit.

Do you have an example that makes clear why you need zones, and cannot just track the values / life ranges? That seems like an interesting test for isConflicting.

See file comment in DeLICM.cpp

Assuming both implicit and explicit representation are supported. I wonder if one of them would be enough? Or is there a reason to keep both? I have the feeling that having both currently makes the code (unnecessarily) hard to read?

It's just the opposite, it makes it clearer that Unused/Occupied can be nullptr and therefore easier to understand. Previous versions of this patch used a flag which one is implicit, hence also requiring that one of the is implicit. I invite you to look into these versions to see if whether they are%2

lib/Transform/DeLICM.cpp
1657

Nice, this nicely removes the code duplication.

unittests/DeLICM/DeLICMTest.cpp
211

reduction_embedded.ll

Hi Michael,

please ignore the previous email. It got sent incomplete.

First, I like the changes to computeReachingWrite. The code duplication is nicely removed. Very cool!

I feel relative strongly about keeping them. They were certainly helpful in development when I did not yet have a singular definition of what a "zone" is. Currently a zone 0 < 1 < 1 is consistently represented by the integer set { [1] }. There is no strict necessity to fo this everywhere. E.g. it might be more intuitive to use the start of the range instead. These computations are currently agnostic to what a zone is (could be moved to ISLTools.cpp as well maybe?) and I would perceive it as a loss when they suddenly would.

I also agree with you that keeping the additional cases for now makes sense -- especially as we have good test coverage. In fact, I like the idea of adding this functionality to ISLTools.cpp. It clearly is self-contained, well documented, and well tested. Please feel free to push these out already.

In D24716#666155, @grosser wrote:

I am not sure if Knowledges must be implicit or if also both sets can be explicit. In isConflicting you state "current implementation requires it to be implicit", but when testing you seem to compute two explicit sets using completeLifetime. This seems inconsistent.

That is comment was outdated. In previous revisions Unused, Known and Unknown was stored in the same map (instead in one Unsued and one Occupied). Two of them had to be defined, the third was implicit, hence "required" to be implicit.

Do you have an example that makes clear why you need zones, and cannot just track the values / life ranges? That seems like an interesting test for isConflicting.

See file comment in DeLICM.cpp

Could such an example be added to the tests of isConflicting that illustrates why such a merge would result in an incorrect / unprecise answer.

Assuming both implicit and explicit representation are supported. I wonder if one of them would be enough? Or is there a reason to keep both? I have the feeling that having both currently makes the code (unnecessarily) hard to read?

It's just the opposite, it makes it clearer that Unused/Occupied can be nullptr and therefore easier to understand. Previous versions of this patch used a flag which one is implicit, hence also requiring that one of the is implicit. I invite you to look into these versions to see if whether they are%2

I did not mean that we should merge Unused/Occupied. I agree that having both makes a lot of sense. What I was suggesting above was if we should prohibit that both can be set simultaniously. The reason for this is that we now need to always support an explicit and an implicit representation of these sets. As such I always need to convince myself that both code paths are correct (or that ignoring one is correct). In the actual code that we run, we always seem to use implicit sets. So I wonder why we do not just limit our implementation to implicit sets and also test it with implicit sets.

Do you have an example that makes clear why you need zones, and cannot just track the values / life ranges? That seems like an interesting test for isConflicting.

See file comment in DeLICM.cpp

Could such an example be added to the tests of isConflicting that illustrates why such a merge would result in an incorrect / unprecise answer.

Could you suggest an EXPECT(...) line? I have no clue what kind of example you have in mind.

Meinersbur updated this revision to Diff 87095.Feb 4 2017, 8:29 AM
  • Rebase to r294094
  • Use implicit sets in unittests

Hi Michael,

here a first update. I would like to think a little bit more about this to get some illustrative examples (am busy on CC at the moment), but here already some comments on what I am thinking. (No need to change anything yet. I currently try to complete my understanding of this code).

Do you have an example that makes clear why you need zones, and cannot just track the values / life ranges? That seems like an interesting test for isConflicting.

See file comment in DeLICM.cpp

Could such an example be added to the tests of isConflicting that illustrates why such a merge would result in an incorrect / unprecise answer.

Could you suggest an EXPECT(...) line? I have no clue what kind of example you have in mind.

I am not sure how such test case can be constructed. You use "zones" to model occupied and undef sets in a knowledge. In isConflicting you always convert the zones to a set of timepoints (when comparing to writes). To me it looks as if we could as well store the zones as set of timepoints. I am looking for an argument that explains why we need to store occupied and undef indeed as zones.

lib/Transform/DeLICM.cpp
412

In your documentation and the code, you use "Unused" and "Undef" for the same thing. The set here is e.g., called Unused, but in the class documentation and the tests you talk about "Undef". Would it not be better to just use one of the two?

435

What does it mean to be implicitly unused.

The unused set has not been computed explicitly, but is assumed to be the complement of Occupied

OK. The comments now make this very clear. Thank you!

Can you somehow print this, e.g. as "universe - Occupied".

I don't understand this suggestion.

In "print(llvm::raw_ostream &OS, unsigned Indent = 0)" you just print "<implicit>" in case the corresponding set is a nullptr. Without reading the source code comments, I do not know what <implicit> means. Hence, this is difficult to understand. I wonder if we could print this in a way that one can easily understand what this means. E.g. by printing a string that shows how "implicit" is computed.

What happens if the first set does not contain elements from each space?

Does not happen. In ZoneAlgorithm one of the two sets will always be implicit. In DeLICMTests unionSpace() is used.

Assuming we never write to a given array? This would mean it does not appear in Occupied and is completely unused. Now, the universe we compute won't contain an element from this space, after the (implicit) subtraction it won't appear, right?

As there is no write to the array, greedyCollapse() will not try to map anything to it.

I wonder if there is an implicit assumption hidden. I need to think a little bit more about this to see if I can construct a test case that would validate this assumption and consequently result in incorrect answers being given by isConflicting. Overall, the correctness and the behavior of Knowledge should not depend on how Knowledge is used, but knowledge should have defined behavior for any input.

(In some way, we should make very clear which spaces a complement is actually formed. And how isConflicting works in case the sets are inconsistent -- if this can happen at all).

443

I wonder if it makes sense to document the implicit Occupied and Unused sets at this position and to explain precisely that the complement here means the complement for all spaces that are mentioned in the explicit of the two sets. In terms of interface, I could use see us enforcing and documenting that one of Occupied and Unused must be nullptr.

478

This "if" is not needed. It is always implied by the asserts.

510

I tried to replace these lines by:

+ assert(Existing.Unused && !Existing.Occupied);
+ assert(!Proposed.Unused && Proposed.Occupied);

This seems to work. Would this be correct and could we make Knowledge consistently limited to this pattern? Would this make sense at all? Are there cases where isConflicting would return wrong results for certain values of Existing.Occupied or Proposed.Unused (which are not useful).

Hi Michael,

thanks for explaining me this patch again on the phone in great detail. I think I now got the information I was lacking and added a couple of comments which I think might help others to get this information as well.

Would be great if you could cross-check this information and integrate it where appropriate. After this, we should be able to commit the Knowledge part and move on to the next pieces.

Best,
Tobias

Best,
Tobias

lib/Transform/DeLICM.cpp
405

Could we possibly explain why zones are used to represent lifetimes? Something like:

The set of alive array elements is represented as zone, as the set of live values can differ depending on how the elements are interpreted.

Assuming a value X is written at timestep [0] and read at timestep [1] without being used at any later point, then the value is alive in the interval ]0,1[. This interval cannot be represented by an integer set, as it does not contain any integer point. Zones allow us to represent this interval and can be converted to sets of timepoints when needed (e.g., in isConflicting when comparing to the write sets).

@see convertZoneToTimepoints for more details.

This might be a little verbose, but might help the reader.

461

What about "everything not in 'Occupied'"?

What about "everything not in 'Unused'"?

504

Can you add a comment that ensures that the universe of both Existing and Proposed need to be identical.

Also, if both are fully defined, can we add asserts to validate this.

527

Maybe an additional comment:

"
We convert here the set of lifetimes to actual timesteps. A lifetime is in conflict with a set of write timepoints, if either a lite timepoint is clearly within the lifetime or if a write happens at the beginning of the lifetime (where it would conflict with the value that actually writes the value alive). There is no conflict at the end of a lifetime, as the alive value will always be read, before it is overwritten again. The last property holds in Polly for all scalar values and we expect all users of Knowledge to check this property also for accesses to MemoryKind::Array.
"

unittests/DeLICM/DeLICMTest.cpp
109

Maybe test four cases?

Meinersbur updated this revision to Diff 88302.Feb 13 2017, 9:40 PM
Meinersbur marked 18 inline comments as done.
  • Refine documentation about zones
  • Testing and assertions for Knowledges with Occupied and Unused defined
  • Rebase to r294894
  • Address Tobias' other comments

Hi Michael,

thanks for the very fast update. This was exactly what I was looking for. I have a couple of minor typos and final questions on the Knowledge and Zone description. Otherwise, I think the knowledge stuff is good to go.

(I believe this was the most difficult part of the patch. The remaining part is still a lot larger, but I believe most of it is well explained and also not technically too complicated).

lib/Transform/DeLICM.cpp
47

AT the

at THE end

50

e.g., a LOAD

51

WE exclude ... starting the zone FROM THE LIVE-RANGE.

57

It is unclear to me why a write may overwrite a variable's value. Is it because it is a may write, due to the order of the writes in the statement, or because it may write an identical value (and consequently the write has no effect)?

Also, I am not sure why you mention "undefined behavior" here. In the context of C this term has a very strong meaning. Is this really what you mean here? Can you explain what exactly is undefined and why?

60

Hence, WE include

62

What is a contradiction of a live-range. You can contradict statements that state something, but what does contradicting a live-range mean?

64

starts

65

IN the live-range

68

e.g.,

69

e.g.,

498

I don't get the grammar of the sentence in the assert. Could you look at it again?

Meinersbur updated this revision to Diff 88365.Feb 14 2017, 6:12 AM
Meinersbur marked 11 inline comments as done.
  • Clarify considerations in comment about zones.

Hi Michael,

thank you for the quick update. The knowledge stuff is now really well polished. Thanks! Feel free to commit it.

I will try to have a look at the remaining parts later tonight!

lib/Transform/DeLICM.cpp
50

IN the following

Meinersbur updated this revision to Diff 88563.Feb 15 2017, 9:37 AM
Meinersbur marked an inline comment as done.
  • Rebase to r295204

Hi Michael,

this patch looks good to me. Just two minor typos. Also, I would really appreciate if you could add some negative tests.

Best,
Tobias

lib/Transform/DeLICM.cpp
855

NOT yet processed

1028

processed ELEMENT

grosser accepted this revision.Feb 16 2017, 8:17 AM

Also mark officially as accepted.

This revision is now accepted and ready to land.Feb 16 2017, 8:17 AM
This revision was automatically updated to reflect the committed changes.
Meinersbur marked an inline comment as done.