[Polly] [DependenceInfo] change WAR, WAW generation to correct semantics.

[bollu]

Summary

Change of WAR, WAW generation:

• buildFlow(Sink, MustSource, MaySource, Sink) treates any flow of the form sink <- may source <- must source as a *may* dependence.

• we used to call:

Flow = buildFlow(MustWrite, MustWrite, Read, Schedule);
WAW = isl_union_flow_get_must_dependence(Flow);
WAR = isl_union_flow_get_may_dependence(Flow);

• This caused some WAW dependences to be treated as WAR dependences.
• Incorrect semantics.

• Now, we call WAR and WAW correctly.

Correct WAW:

Flow = buildFlow(Write, MustWrite, MayWrite, Schedule);
WAW = isl_union_flow_get_may_dependence(Flow);
isl_union_flow_free(Flow);

• Straightforward call.

Correct WAR:

Flow = buildFlow(Write, Read, Write, Schedule);
WAR = isl_union_flow_get_must_dependence(Flow);
isl_union_flow_free(Flow);

• We want the "shortest" WAR possible (exact dependences).
• We mark all the writes as may-source, reads as must-souce.
• Then, we ask for *must* dependence.
• This removes all the reads that flow through a write before reaching a sink.
• Leaves with direct (R -> W).

• This affects reduction generation since RED is built using WAW and WAR.

New StrictWAW for Reductions:

• We used to call: Flow = buildFlow(MustWrite, MustWrite, Read, Schedule); WAW = isl_union_flow_get_must_dependence(Flow); WAR = isl_union_flow_get_may_dependence(Flow);

• This *is* the right model of WAW we need for reductions, just not in general.
• Reductions need to track only *strict* WAW, without any reads in between.

Example for strict WAW:

example-strict-waw.cpp

void f(int *A, int *B) {
    for(int i = 0; i <= 100; i++) {
    S0:    *A += i; --WAW (S0 -> S0) --*
                                       |
        if (i >= 98) {               WAR (S0 -> S1)
    S1:        *B = *A; <--------------*
        }
    }
}

• Since the writes to S0 happen *between* reads at S1, the entire loop is not a legal reduction. It is only a reduction in (0 <= i <= 98).

• To detect these sorts of patterns, we need to generate strict WAW that do not have reads between them.

Explanation: Why the new WAR dependences in tests are correct:

• We no longer set WAR = WAR - WAW
• Hence, we will have WAR dependences that were originally removed.
• These may look incorrect, but in fact make sense.

Code:

new-war-dependence.ll

;    void manyreductions(long *A) {
;      for (long i = 0; i < 1024; i++)
;        for (long j = 0; j < 1024; j++)
; S0:          *A += 42;
;
;      for (long i = 0; i < 1024; i++)
;        for (long j = 0; j < 1024; j++)
; S1:          *A += 42;
;       ...

WAR dependence:

{  S0[1023, 1023] -> S1[0, 0] }

• Between S0[1023, 1023] and S1[0, 0], we will have the dependences:

dependence-incorrect

        S0[1023, 1023]:
    *-- tmp = *A (load0)--*
WAR 2   add = tmp + 42    |
    *-> *A = add (store0) |
                         WAR 1
        S1[0, 0]:         |
        tmp = *A (load1)  |
        add = tmp + 42    |
        A = add (store1)<-*

• One may assume that WAR2 *hides* WAR1 (since store0 happens before store1). However, within a statement, Polly has no idea about the ordering of loads and stores.

• Hence, according to Polly, the code may have looked like this:

dependence-correct

S0[1023, 1023]:
A = add (store0)
tmp = A (load0) ---*
add = A + 42       |
                 WAR 1
S1[0, 0]:          |
tmp = A (load1)    |
add = A + 42       |
A = add (store1) <-*

• So, Polly generates (correct) WAR dependences. It does not make sense to remove these dependences, since they are correct with respect to Polly's model.

[grosser]

Cool. This looks good from my side. Maybe Michael has a comment.

I am OK with a compile time regression here. We should first get it correct, then tune the compile time.

[Meinersbur]

Thanks for this patch. I already mentioned to Tobias was that this code looked incorrect, but he explained to me that this was taken over from something Sven did and I did not investigate further. The new way of computing the dependencies is much more understandable and you explained well why changes are necessary.

Also thanks for the detailed summary. I usually care more about comments in the code that the commit message since I cannot lookup the whole history of the file when I look at the code. The summary is good for explaining the differences to the previous state. However, think your comments are sufficient.

Change of WAR, WAW generation:

• buildFlow(Sink, MustSource, MaySource, Sink) treates any flow of the form sink <- may source <- must source as a *may* dependence.

• we used to call:

Flow = buildFlow(MustWrite, MustWrite, Read, Schedule);
WAW = isl_union_flow_get_must_dependence(Flow);
WAR = isl_union_flow_get_may_dependence(Flow);

• This caused some WAW dependences to be treated as WAR dependences.
• Incorrect semantics.

Do you have examples for when this happened?

New StrictWAW for Reductions:

• We used to call: Flow = buildFlow(MustWrite, MustWrite, Read, Schedule); WAW = isl_union_flow_get_must_dependence(Flow); WAR = isl_union_flow_get_may_dependence(Flow);

• This *is* the right model of WAW we need for reductions, just not in general.

Why?

• Reductions need to track only *strict* WAW, without any reads in between.

See inline comment.

Explanation: Why the new WAR dependences in tests are correct:

• We no longer set WAR = WAR - WAW
• Hence, we will have WAR dependences that were originally removed.
• These may look incorrect, but in fact make sense.

Code:

new-war-dependence.ll

;    void manyreductions(long *A) {
;      for (long i = 0; i < 1024; i++)
;        for (long j = 0; j < 1024; j++)
; S0:          *A += 42;
;
;      for (long i = 0; i < 1024; i++)
;        for (long j = 0; j < 1024; j++)
; S1:          *A += 42;
;       ...

WAR dependence:

{  S0[1023, 1023] -> S1[0, 0] }

• Between S0[1023, 1023] and S1[0, 0], we will have the dependences:

dependence-incorrect

        S0[1023, 1023]:
    *-- tmp = *A (load0)--*
WAR 2   add = tmp + 42    |
    *-> *A = add (store0) |
                         WAR 1
        S1[0, 0]:         |
        tmp = *A (load1)  |
        add = tmp + 42    |
        A = add (store1)<-*

• One may assume that WAR2 *hides* WAR1 (since store0 happens before store1). However, within a statement, Polly has no idea about the ordering of loads and stores.

This is a general problem in Polly. We need to implicitly assume an order of reads and writes within a single statement instance. The most sane way to do this is to always assume that loads are done first, as in your examples.

However, this isn't necessarily so. Code is just as valid if it is done the other way around:

*A = ...
... = *A

this is a kind of self-dependency we can ignore because such self-dependencies do not influence scheduling. So we have to assume the worst case that the read is visible outside, even if it can only read the value written in itself. But we have to take care for that the isl_flow understands it the same way, which I currently doesn't know how it does it. Do you?

• Hence, according to Polly, the code may have looked like this:

dependence-correct

S0[1023, 1023]:
A = add (store0)
tmp = A (load0) ---*
add = A + 42       |
                 WAR 1
S1[0, 0]:          |
tmp = A (load1)    |
add = A + 42       |
A = add (store1) <-*

Did you mix up the order in the first block?

I am surprised that Tobias just greenlit this patch. There are some issues that he consistently remarks in my patches, but I personally do not care (that much) about:

• Unrelated whitespace changes
• Unrelated NFC changes: An additional null-check for MaySrc, but buildFlow is never called with nullptr; ScheduleOptimizer.cpp
• pattern-matching-based-opts_3.ll has been changed, but just the beginning braces been removed (did you use my automatic update tool?)
• There are at least 2 independent changes that can be made separate patches:
  • Modification of how WAW is computed.
  • Modification of how RAW is computed.
  • Introduction of StrictWAW

lib/Analysis/DependenceInfo.cpp

437–438

This set is used in both branches and should be hoisted before branching.

440

Could you clarify that the first <- is a WAW dependency and only the second is a WAR dependency? Also mention that in this examples all writes are MUST writes. If W1 is a may-write, there should be a W2->R dependency (correct?)

443

reads themselves do not have side-effects (assuming segfaulting is undefined behaviour)

448–449

Is this correct? With the goal mentioned in the above comment, I would assume this:

Flow = buildFlow(Write, MustWrite, Read, Schedule);
WAR = isl_union_flow_get_non_must_dependence(Flow);

450

What is this WAW (S0 -> S0) within this arrow? If it is the self-dependency (which should be a separate arrow), shouldn't it be a WAR?

458

"... writes at/in S0 ..." (S0 is no write target)

Also nitpick: double space in comment.

458–459

It is a reduction over the complete domain. The only issue is that some intermediate value is grabbed. An implementation could use the reduction to compute the final value of *A, but leave all operations of *A up to i >= 98 (the difference would be clearer if the condition was i == 1) in there. Normally the operations would become dead because the final value would be computed in another way, just not here. ScalarEvolution would do that. The grabbed value could also be computed by a second reduction. Not saying it makes sense, but the claim it is not a reduction anymore is incorrect.

463–464

Do may-writes cause problems with reductions? There are handles just like must-writes here.

Also, a statement

*A += x;

is a read and a write to *A (read it, update it, then write it back). That is, logically there is always read between two writes.

I have to look up what isl does when the source and sink are at the same timepoint.

486–489

As both branches compute this, it should be put just after the conditionals.

lib/Transform/ScheduleOptimizer.cpp

784–789

Why this change?

test/DependenceInfo/reduction_privatization_deps.ll

8–9

I don't get this additional comment. S2 was never considered a reduction, no?

test/DependenceInfo/reduction_simple_privatization_deps_w_parameter.ll

6

Not aligned to the other indentions anymore.

[bollu]

Updated style changes in DependenceInfo.cpp, test cases.

[bollu]

Regarding WAR dependences:

In "Presburger formulas and Polyhedral Compilation", Section 6.3, it's written that:

K := sink
Y := may-source
T := must-source

must-dependences := {k→(i→a):i→a∈K ∧  k→a∈T  ∧  k<i  ∧  ¬(∃j:j→a∈(T∪Y)  ∧  k<j<i)}
may-dependences := {k→(i→a):i→a∈K  ∧  k→a∈(T∪Y)  ∧  k<i  ∧  ¬(∃j:j→a∈T  ∧  k<j<i)}

The current code is:

current.cpp

Flow = buildFlow(Write, Read, Write, Schedule);
WAR = isl_union_flow_get_must_dependence(Flow);

• For a must-dependence, we get elements in the must-source that have no may-source or must-source dependence between them and the sink.
• In this interpretation, my call leads to the semantics: "Give all elements in Read that have no Read or Write between them and the sink.

you suggested using:

suggestion.cpp

Flow = buildFlow(Write, MustWrite, Read, Schedule);
WAR = isl_union_flow_get_non_must_dependence(Flow);

• For a may-source, we get elements form the may source U must-source that have no must-source dependence between them and the sink.-
• your call leads to the semantics: "Give all elements in Read U Write that have no Read between them and the sink"
• This gives write -> sink (write) like-dependences which are incorrect

I believe that mine is the correct semantics.

• If there is read0 -> read1 -> sink, then the read in between (read1) should be the RAW, so it is correct to not be allowed
• If there is read0 -> write0 -> sink, then read0 -> write0 should be the RAW, so it is correct to not be allowed.

Please do correct me if I have misinterpreted the meaning of the two invocations.

lib/Analysis/DependenceInfo.cpp

440

yes, there are all must-writes. I will clarify this.

443

hm, yes. What I meant was "a read from our statement S0 that leads to a write somewhere else (S1)"

450

It is meant to be a self dependence. Let me clean up the design a little bit. There will be a WAW from S0[i] -> S0[i + 1]?

458–459

I think this depends on our definition of what a reduction is.

If we consider the same block of code and say that everything is a reduction from 0 <= i <= 100, then we should allow free reordering of statements from 0 <= i <= 100. (We subtract RED dependences from RAW, WAW`, and WAR dependences to allow reordering of the reduction statements.

In this case, if we allow reordering, the value written to *B may be incorrect. This was what I meant by is not a reduction,

463–464

1. I'm not totally sure on how May-writes interact with reductions. I suppose it could be argued that for now, we should only use must-writes.

2. for

*A += x

buildFlow appears to do the correct thing even though there is the read between the two writes. However, according to the spec in Presburger Sets and Relations, I'm not entirely sure what is supposed to happen. I will read and find out.

lib/Transform/ScheduleOptimizer.cpp

784–789

This was from when I was trying to fuse WAR and WAW into one "False" dependence. Will revert.

784–789

I mis-remembered. Not having this causes test cases to fail (9 of them). From what I can tell, checking that WAR dependences was empty is some sort of performance optimisation. However, now that we have more WAR dependences than we did previous (since I removed WAR = WAR - WAW), this heuristic no longer applies.

test/DependenceInfo/generate_may_write_dependence_info.ll

63

@Meinersbur This is an example where we find WAW dependences that we did not find before.

test/DependenceInfo/reduction_privatization_deps.ll

8–9

Yes, it is not. It was a comment I had put in to explain the behaviour to myself. WIl remove it

test/ScheduleOptimizer/pattern-matching-based-opts_3.ll

80 ↗

(On Diff #93105)

This missed me. There used to be a conflict with the pattern matching and the generated output. I'll revert this.

[bollu]

@Meinersbur: ping

lib/Transform/ScheduleOptimizer.cpp

784–789

This was from when I was trying to fuse WAR and WAW into one "False" dependence. Will revert.

[Meinersbur]

In D31386#714175, @bollu wrote:

Regarding WAR dependences:

In "Presburger formulas and Polyhedral Compilation", Section 6.3, it's written that:

K := sink
Y := may-source
T := must-source

must-dependences := {k→(i→a):i→a∈K ∧  k→a∈T  ∧  k<i  ∧  ¬(∃j:j→a∈(T∪Y)  ∧  k<j<i)}
may-dependences := {k→(i→a):i→a∈K  ∧  k→a∈(T∪Y)  ∧  k<i  ∧  ¬(∃j:j→a∈T  ∧  k<j<i)}

OK, thank you for looking up isl's defintion. For some reason I expected that dependencies to must-sources would also always be must-dependencies. That was my misconception.

I think the following points still have to be addressed:

• Must and may-sources are handled exactly the same way for WAR (that might be intendent, but I would like to know why)
• WAR-dependencies in reductions.
• How read and write accesses to the same element in the same statement are handeled, especially in reductions.

lib/Analysis/DependenceInfo.cpp

371

My opinion is still that reads do not imply side-effects. Consider using a different explanation why they do not count as reduction.

378–381

There is a RAW self-dependency here as well. You should at least mention that.

E.g. for the test case reduction_simple_iv.ll without reductions, I get the following dependencies:

RAW dependences:
        { Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0] : 0 <= i0 <= 99 }
WAR dependences:
        { Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0] : 0 <= i0 <= 99 }
WAW dependences:
        { Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0] : 0 <= i0 <= 99 }

452–453

The point I was trying to make was the different handling of may-writes. May-writes, at least in flow-dependencies, do not break other dependencies. I'd naively expect the same for anti-dependencies. What is your argument to handle may-writes exactly as must-writes?

That is, for a sequence

must-W2 (sink) <- may-W1 (sink) <- R (source)

I'd naively expect the dependencies

WAR = { W2-> R, W1 -> R }

458–459

Reductions are usually defined as folding as a list of values into a single value. That is, your example contains two reductions with the following values at the end:

*A = sum { A*, 0, ..., 100 }

and

*B = sum { A*, 0, ..., 100 }

(they are the same because *B = *A in the last iteration)
That is, I do not understand this as no reductions, but two reductions that share some instructions to compute them. This does not change the fact that *A is computing a reduction. The order of computation is also irrelevant for being a reduction. It is also irrelevant which modifications can be done on the loop that break the computation. The original code still computed a reduction and stored it into *A, respectively *B.

I suggest to reformulate it in a way saying that intermediate values a used by other computation and therefore cannot arbitrarily modify how reduction *A is computed without duplicating the instructions needed computing *A and *B.

528

Can you undo this change in the next update? Thanks.

lib/Transform/ScheduleOptimizer.cpp

784–789

We maybe should check with Roman about this.

test/DependenceInfo/generate_may_write_dependence_info.ll

63

OK, thanks.

test/DependenceInfo/reduction_privatization_deps.ll

8–9

Still not removed?

[bollu]

NFC: style cleanup

[bollu]

1. Must and may-sources are handled exactly the same way for WAR (that might be intended, but I would like to know why)

The point I was trying to make was the different handling of may-writes. May-writes, at least in flow-dependencies, do not break other dependencies. I'd naively expect the same for anti-dependencies. What is your argument to handle may-writes exactly as must-writes?

That is, for a sequence

must-W2 (sink) <- may-W1 (sink) <- R (source)

I'd naively expect the dependencies

WAR = { W2-> R, W1 -> R }

I see what you mean now. I think you are right, May-Writes should not interfere with Must-Writes. The correct call in that case would be:

correct-war-build.cpp

Flow = buildFlow(Write, Read, MustWrite, Schedule);
WAR = isl_flow_get_must_dependence(Flow);

That way, Must-Writes will block each other, while May-writes will not be allowed to block other writes (both Must and May). Does this work?

2. WAR-dependencies in reductions.

• The reduction detection algorithm has not changed. It still uses RAW and WAW dependences, not WAR.
• We subtract reduction dependences out from the WAR dependences. Before, this was not needed since we used to do WAR = WAR - WAW (but this is not correct semantics).
• So, we remove reduction dependences from WAR to allow freedom of rearrangement

3. How read and write accesses to the same element in the same statement are handled, especially in reductions

• the same element in the same statement are not tracked by ISL.

simple_reduction.ll

; RUN: opt %loadPolly -analyze < %s | FileCheck %s
;
; FIXME: Edit the run line and add checks!
;
; XFAIL: *
;
;    static const int N = 3000;
;
;    void f(int *sum, int A[N]) {
;      for (int i = 0; i < N; i++) {
;        *sum += A[i];
;      }
;    }
;
source_filename = "testbed.c"
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"

define void @f(i32* %sum, i32* %A) {
entry:
  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry
  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
  %exitcond = icmp ne i64 %indvars.iv, 3000
  br i1 %exitcond, label %S0, label %for.end

S0:                                         ; preds = %for.cond
  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
  %tmp = load i32, i32* %arrayidx, align 4
  %tmp1 = load i32, i32* %sum, align 4
  %add = add nsw i32 %tmp1, %tmp
  store i32 %add, i32* %sum, align 4
  br label %for.inc

for.inc:                                          ; preds = %S0
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  br label %for.cond

for.end:                                          ; preds = %for.cond
  ret void
}

dependences

Wrapped Dependences:
    RAW dependences:
        { [Stmt_S0[i0] -> MemRef_sum[0]] -> [Stmt_S0[o0] -> MemRef_sum[0]] : i0 >= 0 and i0 < o0 <= 2999 }
    WAR dependences:
        { [Stmt_S0[i0] -> MemRef_sum[0]] -> [Stmt_S0[1 + i0] -> MemRef_sum[0]] : 0 <= i0 <= 2998 }
    WAW dependences:
        { [Stmt_S0[i0] -> MemRef_sum[0]] -> [Stmt_S0[o0] -> MemRef_sum[0]] : i0 >= 0 and i0 < o0 <= 2999 }

• There is no WAR generated from S0[i] -> S0[i] even though technically *sum = *sum + A[i] does contain a WAR for sum.

WAR-current-code.cpp

Flow = buildFlow(Write, Read, Write, Schedule);
WAR = isl_union_flow_get_must_dependence(Flow);

• This is because isl_union_flow_get_must_dependence specifies that the sink must be strictly less than the source according to the schedule order.
• In this case, the sink is equal to the source in the schedule order.
• Math: See (k<i) (must-dependences := {k→(i→a):i→a∈K ∧ k→a∈T ∧ ***k<i*** ∧ ¬(∃j:j→a∈(T∪Y) ∧ k<j<i)}).
• This will hold true for WAR, WAW, RAW.

lib/Analysis/DependenceInfo.cpp

378–381

I did not believe it was necessary to describe it since it was unimportant to the discussion that the comment was having. However, I'll add it since you want me to.

528

done.

test/DependenceInfo/reduction_privatization_deps.ll

8–9

removed.

test/DependenceInfo/reduction_simple_privatization_deps_w_parameter.ll

6

It's fixed now, correct?

[bollu]

Interestingly enough, changing WAR such that may-writes do not block Writes (may + must) does not lead to a single regression. However, this feels like correct behaviour, so I am updating the code to reflect this.
@grosser: do you have any thoughts on this?

WAR is now:

Flow = buildFlow(Write, Read, MustWrite, Schedule);
WAR = isl_union_flow_get_must_dependence(Flow);

[bollu]

Change how WAR is computed. Also change the StrictWAW explanation to focus
on the fact that the reduction variable is being captured outside the reduction

[bollu]

Add test to check that may-writes to not block must-writes in WAR dependence
generation.

[bollu]

@Meinersbur: ping, I have made the necessary changes to WAR. I've also edited the explanation to make more sense when it comes to reductions. Could you take another look?

[gareevroman]

lib/Transform/ScheduleOptimizer.cpp

784–789

I think it's fine now.

[Meinersbur]

In D31386#716079, @bollu wrote:

1. Must and may-sources are handled exactly the same way for WAR (that might be intended, but I would like to know why)

That way, Must-Writes will block each other, while May-writes will not be allowed to block other writes (both Must and May). Does this work?

Yes.

2. WAR-dependencies in reductions.

• The reduction detection algorithm has not changed. It still uses RAW and WAW dependences, not WAR.
• We subtract reduction dependences out from the WAR dependences. Before, this was not needed since we used to do WAR = WAR - WAW (but this is not correct semantics).
• So, we remove reduction dependences from WAR to allow freedom of rearrangement

Yes, the detection itself has indeed not changed, so I assume it is fine. Although my feeling is still that it should check WAR, not WAW.

3. How read and write accesses to the same element in the same statement are handled, especially in reductions

I tried this example:

selfdep.ll1 KBDownload

to see what happens when the reduction is used in the statement itself. It is actually not recognized as a reduction candidate in the first place. The code that checks for uses in the same statement is checkForReductions().

Could you maybe add a line for StrictWAW so future me won't be confused again?

For all other dependencies, we get an overapproximation, so it should be fine. Problem is, we cannot model the order of accesses within a statement.

[bollu]

What line would you like me to add for StrictWAW?

[Meinersbur]

In D31386#716981, @bollu wrote:

What line would you like me to add for StrictWAW?

Mention that if *A is captured in the same statement/BB as the reduction operation (that is, not made conditional by if (i >= 98)), the reduction in question will already rejected/not added to the candidate list by ScopInfo::checkForReductions(), which verifies that exactly one read and one write in the statement access the reduction variable.

[bollu]

Added short explanation in StrictWAW as to how reductions are guaranteed to have only one load and one store in a statement

[bollu]

@Meinersbur: Done, added the comment. Is there anything else to be fixed?

[Meinersbur]

Tobias usually wants functionally independent parts committed separately (here: StrictWAW, changing how WAW is computed and changing how RAW is computed), but since he already gave his OK, you are free to commit.

lib/Analysis/DependenceInfo.cpp

417–427

nice!

[bollu]

removed whitespace in new testcase.

[bollu]

Closed by commit 490659bdcf7557513f29542c59ce01af72cdc25b

lib/Analysis/DependenceInfo.cpp

 
 static __isl_give isl_union_flow *buildFlow(__isl_keep isl_union_map *Snk,
                                             __isl_keep isl_union_map *Src,
                                             __isl_keep isl_union_map *MaySrc,
                                             __isl_keep isl_schedule *Schedule) {
   isl_union_access_info *AI;
 
   AI = isl_union_access_info_from_sink(isl_union_map_copy(Snk));
+  if (MaySrc)
     AI = isl_union_access_info_set_may_source(AI, isl_union_map_copy(MaySrc));
   if (Src)
     AI = isl_union_access_info_set_must_source(AI, isl_union_map_copy(Src));
   AI = isl_union_access_info_set_schedule(AI, isl_schedule_copy(Schedule));
   auto Flow = isl_union_access_info_compute_flow(AI);
   DEBUG(if (!Flow) dbgs() << "last error: "
                           << isl_ctx_last_error(isl_schedule_get_ctx(Schedule))
                           << '\n';);
   return Flow;
if (!HasReductions) {
     Schedule = isl_schedule_pullback_union_pw_multi_aff(Schedule, Tags);
   }
 
   DEBUG(dbgs() << "Read: " << Read << "\n";
         dbgs() << "MustWrite: " << MustWrite << "\n";
         dbgs() << "MayWrite: " << MayWrite << "\n";
         dbgs() << "Schedule: " << Schedule << "\n");
 
+  isl_union_map *StrictWAW = nullptr;
   {
     IslMaxOperationsGuard MaxOpGuard(IslCtx.get(), OptComputeOut);
 
     RAW = WAW = WAR = RED = nullptr;
+    isl_union_map *Write = isl_union_map_union(isl_union_map_copy(MustWrite),
+                                               isl_union_map_copy(MayWrite));
 
-    if (OptAnalysisType == VALUE_BASED_ANALYSIS) {
-      isl_union_flow *Flow;
+    // We are interested in detecting reductions that do not have intermediate
+    // computations that are captured by other statements.
+    //
+    // Example:
+    // void f(int *A, int *B) {
+    //     for(int i = 0; i <= 100; i++) {
+    //
+    //            *-WAR (S0[i] -> S0[i + 1] 0 <= i <= 100)------------*
+    //            |                                                   |
+    //            *-WAW (S0[i] -> S0[i + 1] 0 <= i <= 100)------------*
+    //            |                                                   |
+    //            v                                                   |
+    //     S0:    *A += i; >------------------*-----------------------*
+    //                                        |
+    //         if (i >= 98) {          WAR (S0[i] -> S1[i]) 98 <= i <= 100
+    //                                        |
+    //     S1:        *B = *A; <--------------*
+    //         }
+    //     }
+    // }
+    //
+    // S0[0 <= i <= 100] has a reduction. However, the values in
+    // S0[98 <= i <= 100] is captured in S1[98 <= i <= 100].
+    // Since we allow free reordering on our reduction dependences, we need to
+    // remove all instances of a reduction statement that have data dependences
+    // orignating from them.
+    // In the case of the example, we need to remove S0[98 <= i <= 100] from
+    // our reduction dependences.
+    //
+    // When we build up the WAW dependences that are used to detect reductions,
+    // we consider only **Writes that have no intermediate Reads**.
+    //
+    // `isl_union_flow_get_must_dependence` gives us dependences of the form:
+    // (sink <- must_source).
+    //
+    // It *will not give* dependences of the form:
+    // 1. (sink <- ... <- may_source <- ... <- must_source)
+    // 2. (sink <- ... <- must_source <- ... <- must_source)
+    //
+    // For a detailed reference on ISL's flow analysis, see:
+    // "Presburger Formulas and Polyhedral Compilation" - Approximate Dataflow
+    //  Analysis.
+    //
+    // Since we set "Write" as a must-source, "Read" as a may-source, and ask
+    // for must dependences, we get all Writes to Writes that **do not flow
+    // through a Read**.
+    //
+    // ScopInfo::checkForReductions makes sure that if something captures
+    // the reduction variable in the same basic block, then it is rejected
+    // before it is even handed here. This makes sure that there is exactly
+    // one read and one write to a reduction variable in a Statement.
+    // Example:
+    //     void f(int *sum, int A[N], int B[N]) {
+    //       for (int i = 0; i < N; i++) {
+    //         *sum += A[i]; < the store and the load is not tagged as a
+    //         B[i] = *sum;  < reductionLike acccess due to the overlap.
+    //       }
+    //     }
 
-      Flow = buildFlow(Read, MustWrite, MayWrite, Schedule);
+    isl_union_flow *Flow = buildFlow(Write, Write, Read, Schedule);
+    StrictWAW = isl_union_flow_get_must_dependence(Flow);
+    isl_union_flow_free(Flow);
 
+    if (OptAnalysisType == VALUE_BASED_ANALYSIS) {
+      Flow = buildFlow(Read, MustWrite, MayWrite, Schedule);
       RAW = isl_union_flow_get_may_dependence(Flow);
       isl_union_flow_free(Flow);
 
-      Flow = buildFlow(MustWrite, MustWrite, Read, Schedule);
-
-      WAW = isl_union_flow_get_must_dependence(Flow);
-      WAR = isl_union_flow_get_may_dependence(Flow);
-
-      // This subtraction is needed to obtain the same results as were given by
-      // isl_union_map_compute_flow. For large sets this may add some
-      // compile-time cost. As there does not seem to be a need to distinguish
-      // between WAW and WAR, refactoring Polly to only track general non-flow
-      // dependences may improve performance.
-      WAR = isl_union_map_subtract(WAR, isl_union_map_copy(WAW));
+      Flow = buildFlow(Write, MustWrite, MayWrite, Schedule);
+      WAW = isl_union_flow_get_may_dependence(Flow);
+      isl_union_flow_free(Flow);
 
+      // We need exact WAR dependences. That is, if there are
+      // dependences of the form:
+      // must-W2 (sink) <- must-W1 (sink) <- R (source)
+      // We wish to generate *ONLY*:
+      // { R -> W1 },
+      // NOT:
+      // { R -> W2, R -> W1 }
+      //
+      // However, in the case of may-writes, we do *not* wish to allow
+      // may-writes to block must-writes. This makes sense, since perhaps the
+      // may-write will not happen. In that case, the exact dependence will
+      // be the (read -> must-write).
+      // Example:
+      // must-W2 (sink) <- may-W1 (sink) <- R (source)
+      // We wish to generate:
+      // { R-> W1, R -> W2 }
+      //
+      //
+      // To achieve this, we use the fact that *must* dependences are not
+      // allowed to flow through the may-source.
+      // Since we set the may-source to MustWrite, we are guarenteed that
+      // only the exact ("shortest") (must-write -> read) is captured.
+      // Any number of intermediate may-writes are allowed.
+      Flow = buildFlow(Write, Read, MustWrite, Schedule);
+      WAR = isl_union_flow_get_must_dependence(Flow);
       isl_union_flow_free(Flow);
+
+      isl_union_map_free(Write);
       isl_schedule_free(Schedule);
     } else {
       isl_union_flow *Flow;
 
-      isl_union_map *Write = isl_union_map_union(isl_union_map_copy(MustWrite),
-                                                 isl_union_map_copy(MayWrite));
-
       Flow = buildFlow(Read, nullptr, Write, Schedule);
-
       RAW = isl_union_flow_get_may_dependence(Flow);
       isl_union_flow_free(Flow);
 
       Flow = buildFlow(Write, nullptr, Read, Schedule);
-
       WAR = isl_union_flow_get_may_dependence(Flow);
       isl_union_flow_free(Flow);
 
       Flow = buildFlow(Write, nullptr, Write, Schedule);
-
       WAW = isl_union_flow_get_may_dependence(Flow);
       isl_union_flow_free(Flow);
-      isl_schedule_free(Schedule);
+
       isl_union_map_free(Write);
+      isl_schedule_free(Schedule);
     }
 
     isl_union_map_free(MustWrite);
     isl_union_map_free(MayWrite);
     isl_union_map_free(Read);
 
     RAW = isl_union_map_coalesce(RAW);
     WAW = isl_union_map_coalesce(WAW);
     WAR = isl_union_map_coalesce(WAR);
 
     // End of max_operations scope.
   }
 
   if (isl_ctx_last_error(IslCtx.get()) == isl_error_quota) {
     isl_union_map_free(RAW);
     isl_union_map_free(WAW);
     isl_union_map_free(WAR);
-    RAW = WAW = WAR = nullptr;
+    isl_union_map_free(StrictWAW);
+    RAW = WAW = WAR = StrictWAW = nullptr;
     isl_ctx_reset_error(IslCtx.get());
   }
 
   // Drop out early, as the remaining computations are only needed for
   // reduction dependences or dependences that are finer than statement
   // level dependences.
   if (!HasReductions && Level == AL_Statement) {
     RED = isl_union_map_empty(isl_union_map_get_space(RAW));
     TC_RED = isl_union_map_empty(isl_union_set_get_space(TaggedStmtDomain));
     isl_union_set_free(TaggedStmtDomain);
+    isl_union_map_free(StrictWAW);
     return;
   }
 
   isl_union_map *STMT_RAW, *STMT_WAW, *STMT_WAR;
   STMT_RAW = isl_union_map_intersect_domain(
       isl_union_map_copy(RAW), isl_union_set_copy(TaggedStmtDomain));
   STMT_WAW = isl_union_map_intersect_domain(
       isl_union_map_copy(WAW), isl_union_set_copy(TaggedStmtDomain));
   STMT_WAR =
       isl_union_map_intersect_domain(isl_union_map_copy(WAR), TaggedStmtDomain);
   DEBUG({
     dbgs() << "Wrapped Dependences:\n";
     dump();
     dbgs() << "\n";
   });
 
   // To handle reduction dependences we proceed as follows:
   // 1) Aggregate all possible reduction dependences, namely all self
   //    dependences on reduction like statements.
   // 2) Intersect them with the actual RAW & WAW dependences to the get the
   //    actual reduction dependences. This will ensure the load/store memory
   //    addresses were __identical__ in the two iterations of the statement.
-  // 3) Relax the original RAW and WAW dependences by subtracting the actual
-  //    reduction dependences. Binary reductions (sum += A[i]) cause both, and
-  //    the same, RAW and WAW dependences.
+  // 3) Relax the original RAW, WAW and WAR dependences by subtracting the
+  //    actual reduction dependences. Binary reductions (sum += A[i]) cause
+  //    the same, RAW, WAW and WAR dependences.
   // 4) Add the privatization dependences which are widened versions of
   //    already present dependences. They model the effect of manual
   //    privatization at the outermost possible place (namely after the last
   //    write and before the first access to a reduction location).
 
   // Step 1)
   RED = isl_union_map_empty(isl_union_map_get_space(RAW));
   for (ScopStmt &Stmt : S) {
     for (MemoryAccess *MA : Stmt) {
       if (!MA->isReductionLike())
         continue;
       isl_set *AccDomW = isl_map_wrap(MA->getAccessRelation());
       isl_map *Identity =
           isl_map_from_domain_and_range(isl_set_copy(AccDomW), AccDomW);
       RED = isl_union_map_add_map(RED, Identity);
     }
   }
 
   // Step 2)
   RED = isl_union_map_intersect(RED, isl_union_map_copy(RAW));
-  RED = isl_union_map_intersect(RED, isl_union_map_copy(WAW));
+  RED = isl_union_map_intersect(RED, StrictWAW);
 
   if (!isl_union_map_is_empty(RED)) {
 
     // Step 3)
     RAW = isl_union_map_subtract(RAW, isl_union_map_copy(RED));
     WAW = isl_union_map_subtract(WAW, isl_union_map_copy(RED));
+    WAR = isl_union_map_subtract(WAR, isl_union_map_copy(RED));
 
     // Step 4)
     addPrivatizationDependences();
   }
 
   DEBUG({
     dbgs() << "Final Wrapped Dependences:\n";
     dump();

lib/Transform/ScheduleOptimizer.cpp

 /// @param  D The SCoP dependencies.
 /// @param  Pos The parameter to desribe an acceptable true dependence.
 ///             In case it has a negative value, try to determine its
 ///             acceptable value.
 /// @return True in case dependencies correspond to the matrix multiplication
 ///         and false, otherwise.
 static bool containsOnlyMatMulDep(__isl_keep isl_map *Schedule,
                                   const Dependences *D, int &Pos) {
-  auto *WAR = D->getDependences(Dependences::TYPE_WAR);
-  if (!isl_union_map_is_empty(WAR)) {
-    isl_union_map_free(WAR);
-    return false;
-  }
-  isl_union_map_free(WAR);
   auto *Dep = D->getDependences(Dependences::TYPE_RAW);
   auto *Red = D->getDependences(Dependences::TYPE_RED);
   if (Red)
     Dep = isl_union_map_union(Dep, Red);
   auto *DomainSpace = isl_space_domain(isl_map_get_space(Schedule));
   auto *Space = isl_space_map_from_domain_and_range(isl_space_copy(DomainSpace),
                                                     DomainSpace);
   auto *Deltas = isl_map_deltas(isl_union_map_extract_map(Dep, Space));

test/DependenceInfo/different_schedule_dimensions.ll

 ; RUN: opt -S %loadPolly -polly-dependences \
 ; RUN:                   -analyze < %s | FileCheck %s
 ; RUN: opt -S %loadPolly -polly-function-dependences \
 ; RUN:                   -analyze < %s | FileCheck %s -check-prefix=FUNC
 
 ; CHECK: RAW dependences:
 ; CHECK:   { Stmt_bb9[0] -> Stmt_bb10[0] }
 ; CHECK: WAR dependences:
-; CHECK:   {  }
+; CHECK:   { Stmt_bb3[0] -> Stmt_bb10[0] }
 ; CHECK: WAW dependences:
 ; CHECK:   { Stmt_bb3[0] -> Stmt_bb10[0] }
 ; CHECK: Reduction dependences:
 ; CHECK:   {  }
 
 ; FUNC: RAW dependences:
 ; FUNC-NEXT:   { Stmt_bb9[0] -> Stmt_bb10[0]; [Stmt_bb9[0] -> Stmt_bb9_Write0_MemRef_tmp11[]] -> [Stmt_bb10[0] -> Stmt_bb10_Read0_MemRef_tmp11[]] }
 ; FUNC-NEXT: WAR dependences:
-; FUNC-NEXT:   {  }
+; FUNC-NEXT:   { Stmt_bb3[0] -> Stmt_bb10[0]; [Stmt_bb3[0] -> Stmt_bb3_Read0_MemRef_arg1[]] -> [Stmt_bb10[0] -> Stmt_bb10_Write1_MemRef_arg1[]] }
 ; FUNC-NEXT: WAW dependences:
 ; FUNC-NEXT:   { Stmt_bb3[0] -> Stmt_bb10[0]; [Stmt_bb3[0] -> Stmt_bb3_Write1_MemRef_arg1[]] -> [Stmt_bb10[0] -> Stmt_bb10_Write1_MemRef_arg1[]] }
 ; FUNC-NEXT: Reduction dependences:
 ; FUNC-NEXT:   {  }
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @hoge(i32 %arg, [1024 x double]* %arg1) {

test/DependenceInfo/do_pluto_matmult.ll

 do.end45:                                         ; preds = %do.cond42
   fence seq_cst
   ret void
 }
 
 ; VALUE:      RAW dependences:
 ; VALUE-NEXT:     { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34 }
 ; VALUE-NEXT: WAR dependences:
-; VALUE-NEXT:     {  }
+; VALUE-NEXT: { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34 }
 ; VALUE-NEXT: WAW dependences:
 ; VALUE-NEXT:     { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34 }
 
 ; MEMORY:      RAW dependences:
 ; MEMORY-NEXT:     { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35 }
 ; MEMORY-NEXT: WAR dependences:
 ; MEMORY-NEXT:     { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35 }
 ; MEMORY-NEXT: WAW dependences:
 ; MEMORY-NEXT:     { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35 }
 
 ; FUNC-VALUE:      RAW dependences:
 ; FUNC-VALUE-NEXT:     { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Write3_MemRef_C[]] -> [Stmt_do_body2[i0, i1, 1 + i2] -> Stmt_do_body2_Read0_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34 }
 ; FUNC-VALUE-NEXT: WAR dependences:
-; FUNC-VALUE-NEXT:     {  }
+; FUNC-VALUE-NEXT:     { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Read0_MemRef_C[]] -> [Stmt_do_body2[i0, i1, 1 + i2] -> Stmt_do_body2_Write3_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34 }
 ; FUNC-VALUE-NEXT: WAW dependences:
 ; FUNC-VALUE-NEXT:     { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Write3_MemRef_C[]] -> [Stmt_do_body2[i0, i1, 1 + i2] -> Stmt_do_body2_Write3_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34 }
 
 ; FUNC-MEMORY:      RAW dependences:
 ; FUNC-MEMORY-NEXT:     { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Write3_MemRef_C[]] -> [Stmt_do_body2[i0, i1, o2] -> Stmt_do_body2_Read0_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35 }
 ; FUNC-MEMORY-NEXT: WAR dependences:
 ; FUNC-MEMORY-NEXT:     { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Read0_MemRef_C[]] -> [Stmt_do_body2[i0, i1, o2] -> Stmt_do_body2_Write3_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35 }
 ; FUNC-MEMORY-NEXT: WAW dependences:
 ; FUNC-MEMORY-NEXT:     { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Write3_MemRef_C[]] -> [Stmt_do_body2[i0, i1, o2] -> Stmt_do_body2_Write3_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35 }

test/DependenceInfo/generate_may_write_dependence_info.ll

for.inc:                                          ; preds = %if.end
   br label %for.cond
 
 for.end:                                          ; preds = %for.cond
   ret void
 }
 ; VALUE: RAW dependences:
 ; VALUE-NEXT:   { Stmt_A_must_write_20[i0] -> Stmt_B_write_from_A[i0] : 0 <= i0 <= 2999; Stmt_compute_i_square__TO__B_write_from_A[i0] -> Stmt_B_write_from_A[i0] : 0 <= i0 <= 2999 }
 ; VALUE-NEXT: WAR dependences:
-; VALUE-NEXT:   { Stmt_A_must_write_20[i0] -> Stmt_A_must_write_42[i0] : 0 <= i0 <= 2999; Stmt_B_write_from_A[i0] -> Stmt_A_must_write_42[i0] : 0 <= i0 <= 2999 }
+; VALUE-NEXT:   { Stmt_B_write_from_A[i0] -> Stmt_A_must_write_42[i0] : 0 <= i0 <= 2999 }
 ; VALUE-NEXT: WAW dependences:
-; VALUE-NEXT:   {  }
+; VALUE-NEXT:   { Stmt_compute_i_square__TO__B_write_from_A[i0] -> Stmt_A_must_write_42[i0] : 0 <= i0 <= 2999; Stmt_A_must_write_20[i0] -> Stmt_A_must_write_42[i0] : 0 <= i0 <= 2999; Stmt_A_must_write_20[i0] -> Stmt_compute_i_square__TO__B_write_from_A[i0] : 0 <= i0 <= 2999 }
 ; VALUE-NEXT: Reduction dependences:
 ; VALUE-NEXT:   {  }
 ; VALUE-NEXT: Transitive closure of reduction dependences:
-; VALUE-NEXT:   {  }
+; VALUE-NEXT:   {  }
 

test/DependenceInfo/may_writes_do_not_block_must_writes_for_war.ll

+; RUN: opt %loadPolly -polly-dependences -analyze < %s | FileCheck %s
+;
+; Verify that the presence of a may-write (S1) between a read (S0) and a
+; must-write (S2) does not block the generation of RAW dependences. This makes
+; sure that we capture as many RAW dependences as possible.
+;
+; For this example, we want both (S0(Read) -> S1 (May-Write)) as well as
+; (S0(Read) -> S2(Must-Write)).
+;
+; CHECK: WAR dependences:
+; CHECK-NEXT:     { Stmt_S0[i0] -> Stmt_S2[i0] : 0 < i0 <= 2; Stmt_S0[i0] -> Stmt_if_end__TO__S2[i0] : 0 < i0 <= 2 }
+;
+;
+;    static const int N = 3000;
+;
+;    void f(int *sum, int *A, int *B, int *out) {
+;      for (int i = 0; i <= 2; i++) {
+;        if (i) {
+; S0:          *out += *sum;
+;        }
+;
+;        if (i * i) {
+; S1:          *sum = *A;
+;        }
+; S2:        *sum = *B;
+;      }
+;    }
+;
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %sum, i32* %A, i32* %B, i32* %out) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %exitcond = icmp ne i32 %i.0, 3
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tobool = icmp eq i32 %i.0, 0
+  br i1 %tobool, label %if.end, label %S0
+
+S0:                                          ; preds = %for.body
+  %tmp = load i32, i32* %sum, align 4
+  %tmp1 = load i32, i32* %out, align 4
+  %add = add nsw i32 %tmp1, %tmp
+  store i32 %add, i32* %out, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %S0
+  %mul = mul nsw i32 %i.0, %i.0
+  %tobool1 = icmp eq i32 %mul, 0
+  br i1 %tobool1, label %S2, label %S1
+
+S1:                                         ; preds = %if.end
+  %tmp2 = load i32, i32* %A, align 4
+  store i32 %tmp2, i32* %sum, align 4
+  br label %S2
+
+S2:                                          ; preds = %if.end, %S1
+  %tmp3 = load i32, i32* %B, align 4
+  store i32 %tmp3, i32* %sum, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %S2
+  %inc = add nuw nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+

test/DependenceInfo/reduction_dependences_equal_non_reduction_dependences.ll

 ; RUN: opt %loadPolly -basicaa -polly-dependences -analyze < %s | FileCheck %s
 ;
 ; This loopnest contains a reduction which imposes the same dependences as the
 ; accesses to the array A. We need to ensure we keep the dependences of A.
 ;
 ; CHECK:      RAW dependences:
 ; CHECK-NEXT:     { Stmt_for_body[i0] -> Stmt_for_body[1 + i0] : 0 <= i0 <= 1022 }
 ; CHECK-NEXT: WAR dependences:
-; CHECK-NEXT:     {  }
+; CHECK-NEXT:     { Stmt_for_body[i0] -> Stmt_for_body[1 + i0] : 0 <= i0 <= 1022 }
 ; CHECK-NEXT: WAW dependences:
 ; CHECK-NEXT:     { Stmt_for_body[i0] -> Stmt_for_body[1 + i0] : 0 <= i0 <= 1022 }
 ; CHECK-NEXT: Reduction dependences:
 ; CHECK-NEXT:     { Stmt_for_body[i0] -> Stmt_for_body[1 + i0] : 0 <= i0 <= 1022 }
 ;
 ;
 ;    void AandSum(int *restrict sum, int *restrict A) {
 ;      for (int i = 0; i < 1024; i++) {

test/DependenceInfo/reduction_multiple_reductions_2.ll

 ; RUN: opt %loadPolly -basicaa -polly-dependences -analyze < %s | FileCheck %s
 ;
 ;
 ; These are the important RAW dependences, as they need to originate/end in only one iteration:
 ;   Stmt_S1[i0, 1023] -> Stmt_S2[i0, o1]
 ;   Stmt_S1[i0, i1] -> Stmt_S2[i0, 0]
 ;
 ; These are the important WAW dependences, as they need to originate/end in only one iteration:
 ;   Stmt_S1[i0, 1023] -> Stmt_S2[i0, o1]
 ;   Stmt_S1[i0, i1] -> Stmt_S2[i0, 0]
 ;
 ; CHECK:      RAW dependences:
 ; CHECK-NEXT:     { Stmt_S0[i0] -> Stmt_S1[i0, o1] : 0 <= i0 <= 1023 and 0 <= o1 <= 1023; Stmt_S2[i0, i1] -> Stmt_S3[i0] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023; Stmt_S3[i0] -> Stmt_S0[1 + i0] : 0 <= i0 <= 1022; Stmt_S1[i0, 1023] -> Stmt_S2[i0, o1] : 0 <= i0 <= 1023 and 0 <= o1 <= 1023; Stmt_S1[i0, i1] -> Stmt_S2[i0, 0] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022 }
 ; CHECK-NEXT: WAR dependences:
-; CHECK-NEXT:     {  }
+; CHECK-NEXT:     { Stmt_S0[i0] -> Stmt_S1[i0, o1] : 0 <= i0 <= 1023 and 0 <= o1 <= 1023; Stmt_S2[i0, i1] -> Stmt_S3[i0] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023; Stmt_S3[i0] -> Stmt_S0[1 + i0] : 0 <= i0 <= 1022; Stmt_S1[i0, 1023] -> Stmt_S2[i0, o1] : 0 <= i0 <= 1023 and 0 <= o1 <= 1023; Stmt_S1[i0, i1] -> Stmt_S2[i0, 0] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022 }
 ; CHECK-NEXT: WAW dependences:
 ; CHECK-NEXT:     { Stmt_S0[i0] -> Stmt_S1[i0, o1] : 0 <= i0 <= 1023 and 0 <= o1 <= 1023; Stmt_S2[i0, i1] -> Stmt_S3[i0] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023; Stmt_S3[i0] -> Stmt_S0[1 + i0] : 0 <= i0 <= 1022; Stmt_S1[i0, 1023] -> Stmt_S2[i0, o1] : 0 <= i0 <= 1023 and 0 <= o1 <= 1023; Stmt_S1[i0, i1] -> Stmt_S2[i0, 0] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022 }
 ; CHECK-NEXT: Reduction dependences:
 ; CHECK-NEXT:     { Stmt_S1[i0, i1] -> Stmt_S1[i0, 1 + i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022; Stmt_S2[i0, i1] -> Stmt_S2[i0, 1 + i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022 }
 ;
 ;    void f(int *restrict red) {
 ;      for (int j = 0; j < 1024; j++) {
 ; S0:    *red = 42 + *red * 5;

test/DependenceInfo/reduction_privatization_deps.ll

 ; RUN: opt %loadPolly -polly-dependences -analyze < %s | FileCheck %s
 ;
 ; CHECK:      RAW dependences:
 ; CHECK-NEXT:     { Stmt_S0[i0] -> Stmt_S1[o0, i0 - o0] : i0 <= 1023 and 0 <= o0 <= i0; Stmt_S1[i0, i1] -> Stmt_S2[-1 + i0 + i1] : 0 <= i0 <= 1023 and i1 >= 0 and -i0 < i1 <= 1024 - i0 and i1 <= 1023 }
 ; CHECK-NEXT: WAR dependences:
-; CHECK-NEXT:     { Stmt_S2[i0] -> Stmt_S2[1 + i0] : 0 <= i0 <= 1022; Stmt_S1[i0, i1] -> Stmt_S2[i0 + i1] : i0 >= 0 and i1 >= 0 and -i0 < i1 <= 1023 - i0 }
+; CHECK-NEXT:     { Stmt_S2[i0] -> Stmt_S2[1 + i0] : 0 <= i0 <= 1022; Stmt_S1[0, 0] -> Stmt_S2[0] }
 ; CHECK-NEXT: WAW dependences:
-; CHECK-NEXT:     { Stmt_S0[i0] -> Stmt_S1[o0, i0 - o0] : i0 <= 1023 and 0 <= o0 <= i0; Stmt_S1[0, 0] -> Stmt_S2[0] }
+; CHECK-NEXT:     { Stmt_S0[i0] -> Stmt_S1[o0, i0 - o0] : i0 <= 1023 and 0 <= o0 <= i0; Stmt_S1[i0, i1] -> Stmt_S2[i0 + i1] : i0 >= 0 and 0 <= i1 <= 1023 - i0 }
 ; CHECK-NEXT: Reduction dependences:
 ; CHECK-NEXT:     { Stmt_S1[i0, i1] -> Stmt_S1[1 + i0, -1 + i1] : 0 <= i0 <= 1022 and 0 < i1 <= 1023 }
 ;
 ;    void f(int *sum) {
 ;      for (int i = 0; i < 1024; i++)
 ; S0:    sum[i] = 0;
 ;      for (int i = 0; i < 1024; i++)
 ;        for (int j = 0; j < 1024; j++)
 ; S1:      sum[i + j] += i;

test/DependenceInfo/reduction_privatization_deps_2.ll

 ; RUN: opt %loadPolly -polly-dependences -analyze < %s | FileCheck %s
 ;
 ; We have privatization dependences from a textually later statement to a
 ; textually earlier one, but the dependences still go forward in time.
 ;
 ; CHECK:      RAW dependences:
 ; CHECK-NEXT:     { Stmt_S3[i0] -> Stmt_S2[1 + i0, o1] : 0 <= i0 <= 97 and 0 <= o1 <= 99; Stmt_S1[i0] -> Stmt_S3[i0] : 0 <= i0 <= 98 }
 ; CHECK-NEXT: WAR dependences:
-; CHECK-NEXT:     {  }
+; CHECK-NEXT:     { Stmt_S3[i0] -> Stmt_S2[1 + i0, o1] : 0 <= i0 <= 97 and 0 <= o1 <= 99; Stmt_S1[i0] -> Stmt_S3[i0] : 0 <= i0 <= 98 }
 ; CHECK-NEXT: WAW dependences:
 ; CHECK-NEXT:     { Stmt_S3[i0] -> Stmt_S2[1 + i0, o1] : 0 <= i0 <= 97 and 0 <= o1 <= 99; Stmt_S1[i0] -> Stmt_S3[i0] : 0 <= i0 <= 98 }
 ; CHECK-NEXT: Reduction dependences:
 ; CHECK-NEXT:     { Stmt_S2[i0, i1] -> Stmt_S2[i0, 1 + i1] : 0 <= i0 <= 98 and 0 <= i1 <= 98 }
 ;
 ;    void f(int *sum) {
 ;      int i, j;
 ;      for (i = 0; i < 99; i++) {

test/DependenceInfo/reduction_privatization_deps_3.ll

 ; RUN: opt %loadPolly -polly-dependences -analyze < %s | FileCheck %s
 ;
 ; CHECK:      RAW dependences:
 ; CHECK-NEXT:     { Stmt_S2[i0, i1] -> Stmt_S3[o0] : i1 <= 1 - i0 and -i1 < o0 <= 1 and o0 <= 1 + i0 - i1; Stmt_S3[i0] -> Stmt_S2[o0, 1 - i0] : 0 <= i0 <= 1 and i0 < o0 <= 98; Stmt_S1[i0] -> Stmt_S3[2 + i0] : 0 <= i0 <= 96 }
 ; CHECK-NEXT: WAR dependences:
-; CHECK-NEXT:     {  }
+; CHECK-NEXT:   { Stmt_S2[i0, i1] -> Stmt_S3[o0] : i1 <= 1 - i0 and -i1 < o0 <= 1 and o0 <= 1 + i0 - i1; Stmt_S3[i0] -> Stmt_S2[o0, 1 - i0] : 0 <= i0 <= 1 and i0 < o0 <= 98; Stmt_S1[i0] -> Stmt_S3[2 + i0] : 0 <= i0 <= 96 }
 ; CHECK-NEXT: WAW dependences:
 ; CHECK-NEXT:     { Stmt_S2[i0, i1] -> Stmt_S3[o0] : i1 <= 1 - i0 and -i1 < o0 <= 1 and o0 <= 1 + i0 - i1; Stmt_S3[i0] -> Stmt_S2[o0, 1 - i0] : 0 <= i0 <= 1 and i0 < o0 <= 98; Stmt_S1[i0] -> Stmt_S3[2 + i0] : 0 <= i0 <= 96 }
 ; CHECK-NEXT: Reduction dependences:
 ; CHECK-NEXT:     { Stmt_S2[i0, i1] -> Stmt_S2[1 + i0, i1] : 0 <= i0 <= 97 and i1 >= 0 and 2 - i0 <= i1 <= 98 - i0; Stmt_S2[0, 0] -> Stmt_S2[1, 0] }
 ;
 ;    void f(int *sum) {
 ;      int i, j;
 ;      for (i = 0; i < 99; i++) {

test/DependenceInfo/reduction_privatization_deps_4.ll

 ; RUN: opt %loadPolly -polly-dependences -analyze < %s | FileCheck %s
 ;
 ; CHECK:      RAW dependences:
 ; CHECK-NEXT:     { Stmt_S2[i0, i1] -> Stmt_S1[i1] : i0 >= 0 and i0 < i1 <= 98; Stmt_S1[i0] -> Stmt_S2[i0, i0] : 0 <= i0 <= 98; Stmt_S2[i0, i0] -> Stmt_S3[i0] : 0 <= i0 <= 98; Stmt_S3[i0] -> Stmt_S2[o0, i0] : i0 >= 0 and i0 < o0 <= 98 }
 ; CHECK-NEXT: WAR dependences:
-; CHECK-NEXT:     {  }
+; CHECK-NEXT:   { Stmt_S2[i0, i1] -> Stmt_S1[i1] : i0 >= 0 and i0 < i1 <= 98; Stmt_S1[i0] -> Stmt_S2[i0, i0] : 0 <= i0 <= 98; Stmt_S2[i0, i0] -> Stmt_S3[i0] : 0 <= i0 <= 98; Stmt_S3[i0] -> Stmt_S2[o0, i0] : i0 >= 0 and i0 < o0 <= 98 }
 ; CHECK-NEXT: WAW dependences:
 ; CHECK-NEXT:     { Stmt_S2[i0, i1] -> Stmt_S1[i1] : i0 >= 0 and i0 < i1 <= 98; Stmt_S1[i0] -> Stmt_S2[i0, i0] : 0 <= i0 <= 98; Stmt_S2[i0, i0] -> Stmt_S3[i0] : 0 <= i0 <= 98; Stmt_S3[i0] -> Stmt_S2[o0, i0] : i0 >= 0 and i0 < o0 <= 98 }
 ; CHECK-NEXT: Reduction dependences:
 ; CHECK-NEXT:     { Stmt_S2[i0, i1] -> Stmt_S2[1 + i0, i1] : (i0 >= 0 and 2 + i0 <= i1 <= 99) or (i0 <= 97 and 0 <= i1 < i0) }
 ;
 ;    void f(int *sum) {
 ;      for (int i = 0; i < 99; i++) {
 ; S1:    sum[i] += 42;

test/DependenceInfo/reduction_privatization_deps_5.ll

 ; RUN: opt %loadPolly -polly-dependences -analyze < %s | FileCheck %s
 ;
 ; CHECK:      RAW dependences:
 ; CHECK-NEXT:     { Stmt_S2[i0, 0] -> Stmt_S1[1 + i0, 0] : 0 <= i0 <= 97; Stmt_S1[i0, 0] -> Stmt_S2[i0, 0] : 0 <= i0 <= 98 }
 ; CHECK-NEXT: WAR dependences:
-; CHECK-NEXT:     {  }
+; CHECK-NEXT:     { Stmt_S2[i0, 0] -> Stmt_S1[1 + i0, 0] : 0 <= i0 <= 97; Stmt_S1[i0, 0] -> Stmt_S2[i0, 0] : 0 <= i0 <= 98 }
 ; CHECK-NEXT: WAW dependences:
 ; CHECK-NEXT:     { Stmt_S2[i0, 0] -> Stmt_S1[1 + i0, 0] : 0 <= i0 <= 97; Stmt_S1[i0, 0] -> Stmt_S2[i0, 0] : 0 <= i0 <= 98 }
 ; CHECK-NEXT: Reduction dependences:
 ; CHECK-NEXT:     { Stmt_S2[i0, i1] -> Stmt_S2[1 + i0, i1] : 0 <= i0 <= 97 and 0 < i1 <= 99 }
 ;
 ;    void f(int *sum) {
 ;      for (int i = 0; i < 99; i++) {
 ;        for (int j = 0; j < 1; j++)

test/DependenceInfo/reduction_sequence.ll

 ;      for (long i = 0; i < 1024; i++)
 ;        for (long j = 0; j < 1024; j++)
 ;          *A += 42;
 ;    }
 
 ; CHECK:  RAW dependences:
 ; CHECK-NEXT:     { Stmt_bb150[1023, 1023] -> Stmt_bb162[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb150[i0, i1] -> Stmt_bb162[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb150[1023, 1023] -> Stmt_bb162[0, 0]; Stmt_bb174[1023, 1023] -> Stmt_bb186[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb174[i0, i1] -> Stmt_bb186[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb174[1023, 1023] -> Stmt_bb186[0, 0]; Stmt_bb102[1023, 1023] -> Stmt_bb114[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb114[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb102[1023, 1023] -> Stmt_bb114[0, 0]; Stmt_bb42[1023, 1023] -> Stmt_bb54[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb54[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb42[1023, 1023] -> Stmt_bb54[0, 0]; Stmt_bb54[1023, 1023] -> Stmt_bb66[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb66[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb54[1023, 1023] -> Stmt_bb66[0, 0]; Stmt_bb31[1023, 1023] -> Stmt_bb42[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb42[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb31[1023, 1023] -> Stmt_bb42[0, 0]; Stmt_bb162[1023, 1023] -> Stmt_bb174[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb162[i0, i1] -> Stmt_bb174[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb162[1023, 1023] -> Stmt_bb174[0, 0]; Stmt_bb126[1023, 1023] -> Stmt_bb138[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb126[i0, i1] -> Stmt_bb138[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb126[1023, 1023] -> Stmt_bb138[0, 0]; Stmt_bb90[1023, 1023] -> Stmt_bb102[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb102[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb90[1023, 1023] -> Stmt_bb102[0, 0]; Stmt_bb138[1023, 1023] -> Stmt_bb150[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb138[i0, i1] -> Stmt_bb150[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb138[1023, 1023] -> Stmt_bb150[0, 0]; Stmt_bb66[1023, 1023] -> Stmt_bb78[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb78[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb66[1023, 1023] -> Stmt_bb78[0, 0]; Stmt_bb78[1023, 1023] -> Stmt_bb90[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb90[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb78[1023, 1023] -> Stmt_bb90[0, 0]; Stmt_bb114[1023, 1023] -> Stmt_bb126[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb126[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb114[1023, 1023] -> Stmt_bb126[0, 0] }
 ; CHECK-NEXT:   WAR dependences:
-; CHECK-NEXT:     {  }
+; CHECK-NEXT:     { Stmt_bb150[1023, 1023] -> Stmt_bb162[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb150[i0, i1] -> Stmt_bb162[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb150[1023, 1023] -> Stmt_bb162[0, 0]; Stmt_bb174[1023, 1023] -> Stmt_bb186[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb174[i0, i1] -> Stmt_bb186[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb174[1023, 1023] -> Stmt_bb186[0, 0]; Stmt_bb102[1023, 1023] -> Stmt_bb114[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb114[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb102[1023, 1023] -> Stmt_bb114[0, 0]; Stmt_bb42[1023, 1023] -> Stmt_bb54[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb54[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb42[1023, 1023] -> Stmt_bb54[0, 0]; Stmt_bb54[1023, 1023] -> Stmt_bb66[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb66[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb54[1023, 1023] -> Stmt_bb66[0, 0]; Stmt_bb31[1023, 1023] -> Stmt_bb42[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb42[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb31[1023, 1023] -> Stmt_bb42[0, 0]; Stmt_bb162[1023, 1023] -> Stmt_bb174[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb162[i0, i1] -> Stmt_bb174[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb162[1023, 1023] -> Stmt_bb174[0, 0]; Stmt_bb126[1023, 1023] -> Stmt_bb138[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb126[i0, i1] -> Stmt_bb138[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb126[1023, 1023] -> Stmt_bb138[0, 0]; Stmt_bb90[1023, 1023] -> Stmt_bb102[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb102[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb90[1023, 1023] -> Stmt_bb102[0, 0]; Stmt_bb138[1023, 1023] -> Stmt_bb150[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb138[i0, i1] -> Stmt_bb150[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb138[1023, 1023] -> Stmt_bb150[0, 0]; Stmt_bb66[1023, 1023] -> Stmt_bb78[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb78[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb66[1023, 1023] -> Stmt_bb78[0, 0]; Stmt_bb78[1023, 1023] -> Stmt_bb90[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb90[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb78[1023, 1023] -> Stmt_bb90[0, 0]; Stmt_bb114[1023, 1023] -> Stmt_bb126[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb126[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb114[1023, 1023] -> Stmt_bb126[0, 0] }
 ; CHECK-NEXT:   WAW dependences:
 ; CHECK-NEXT:     { Stmt_bb150[1023, 1023] -> Stmt_bb162[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb150[i0, i1] -> Stmt_bb162[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb150[1023, 1023] -> Stmt_bb162[0, 0]; Stmt_bb174[1023, 1023] -> Stmt_bb186[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb174[i0, i1] -> Stmt_bb186[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb174[1023, 1023] -> Stmt_bb186[0, 0]; Stmt_bb102[1023, 1023] -> Stmt_bb114[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb114[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb102[1023, 1023] -> Stmt_bb114[0, 0]; Stmt_bb42[1023, 1023] -> Stmt_bb54[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb54[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb42[1023, 1023] -> Stmt_bb54[0, 0]; Stmt_bb54[1023, 1023] -> Stmt_bb66[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb66[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb54[1023, 1023] -> Stmt_bb66[0, 0]; Stmt_bb31[1023, 1023] -> Stmt_bb42[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb42[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb31[1023, 1023] -> Stmt_bb42[0, 0]; Stmt_bb162[1023, 1023] -> Stmt_bb174[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb162[i0, i1] -> Stmt_bb174[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb162[1023, 1023] -> Stmt_bb174[0, 0]; Stmt_bb126[1023, 1023] -> Stmt_bb138[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb126[i0, i1] -> Stmt_bb138[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb126[1023, 1023] -> Stmt_bb138[0, 0]; Stmt_bb90[1023, 1023] -> Stmt_bb102[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb102[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb90[1023, 1023] -> Stmt_bb102[0, 0]; Stmt_bb138[1023, 1023] -> Stmt_bb150[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb138[i0, i1] -> Stmt_bb150[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb138[1023, 1023] -> Stmt_bb150[0, 0]; Stmt_bb66[1023, 1023] -> Stmt_bb78[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb78[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb66[1023, 1023] -> Stmt_bb78[0, 0]; Stmt_bb78[1023, 1023] -> Stmt_bb90[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb90[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb78[1023, 1023] -> Stmt_bb90[0, 0]; Stmt_bb114[1023, 1023] -> Stmt_bb126[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb126[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb114[1023, 1023] -> Stmt_bb126[0, 0] }
 ; CHECK-NEXT:   Reduction dependences:
 ; CHECK-NEXT:     { Stmt_bb102[i0, i1] -> Stmt_bb102[i0, 1 + i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022; Stmt_bb102[i0, 1023] -> Stmt_bb102[1 + i0, 0] : 0 <= i0 <= 1022; Stmt_bb186[i0, i1] -> Stmt_bb186[i0, 1 + i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022; Stmt_bb186[i0, 1023] -> Stmt_bb186[1 + i0, 0] : 0 <= i0 <= 1022; Stmt_bb90[i0, i1] -> Stmt_bb90[i0, 1 + i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022; Stmt_bb90[i0, 1023] -> Stmt_bb90[1 + i0, 0] : 0 <= i0 <= 1022; Stmt_bb66[i0, i1] -> Stmt_bb66[i0, 1 + i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022; Stmt_bb66[i0, 1023] -> Stmt_bb66[1 + i0, 0] : 0 <= i0 <= 1022; Stmt_bb31[i0, i1] -> Stmt_bb31[i0, 1 + i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022; Stmt_bb31[i0, 1023] -> Stmt_bb31[1 + i0, 0] : 0 <= i0 <= 1022; Stmt_bb138[i0, i1] -> Stmt_bb138[i0, 1 + i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022; Stmt_bb138[i0, 1023] -> Stmt_bb138[1 + i0, 0] : 0 <= i0 <= 1022; Stmt_bb126[i0, i1] -> Stmt_bb126[i0, 1 + i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022; Stmt_bb126[i0, 1023] -> Stmt_bb126[1 + i0, 0] : 0 <= i0 <= 1022; Stmt_bb150[i0, i1] -> Stmt_bb150[i0, 1 + i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022; Stmt_bb150[i0, 1023] -> Stmt_bb150[1 + i0, 0] : 0 <= i0 <= 1022; Stmt_bb42[i0, i1] -> Stmt_bb42[i0, 1 + i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022; Stmt_bb42[i0, 1023] -> Stmt_bb42[1 + i0, 0] : 0 <= i0 <= 1022; Stmt_bb78[i0, i1] -> Stmt_bb78[i0, 1 + i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022; Stmt_bb78[i0, 1023] -> Stmt_bb78[1 + i0, 0] : 0 <= i0 <= 1022; Stmt_bb114[i0, i1] -> Stmt_bb114[i0, 1 + i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022; Stmt_bb114[i0, 1023] -> Stmt_bb114[1 + i0, 0] : 0 <= i0 <= 1022; Stmt_bb174[i0, i1] -> Stmt_bb174[i0, 1 + i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022; Stmt_bb174[i0, 1023] -> Stmt_bb174[1 + i0, 0] : 0 <= i0 <= 1022; Stmt_bb162[i0, i1] -> Stmt_bb162[i0, 1 + i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022; Stmt_bb162[i0, 1023] -> Stmt_bb162[1 + i0, 0] : 0 <= i0 <= 1022; Stmt_bb54[i0, i1] -> Stmt_bb54[i0, 1 + i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022; Stmt_bb54[i0, 1023] -> Stmt_bb54[1 + i0, 0] : 0 <= i0 <= 1022 }
 ; CHECK-NEXT:   Transitive closure of reduction dependences:
 ; CHECK-NEXT:     { Stmt_bb102[i0, i1] -> Stmt_bb102[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 >= 0 and o0 <= 1023 and o1 > 1024i0 + i1 - 1024o0) or (i0 <= 1023 and o0 >= 0 and o1 < 1024i0 + i1 - 1024o0)); Stmt_bb186[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 >= 0 and o0 <= 1023 and o1 > 1024i0 + i1 - 1024o0) or (i0 <= 1023 and o0 >= 0 and o1 < 1024i0 + i1 - 1024o0)); Stmt_bb90[i0, i1] -> Stmt_bb90[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 >= 0 and o0 <= 1023 and o1 > 1024i0 + i1 - 1024o0) or (i0 <= 1023 and o0 >= 0 and o1 < 1024i0 + i1 - 1024o0)); Stmt_bb66[i0, i1] -> Stmt_bb66[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 >= 0 and o0 <= 1023 and o1 > 1024i0 + i1 - 1024o0) or (i0 <= 1023 and o0 >= 0 and o1 < 1024i0 + i1 - 1024o0)); Stmt_bb31[i0, i1] -> Stmt_bb31[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 >= 0 and o0 <= 1023 and o1 > 1024i0 + i1 - 1024o0) or (i0 <= 1023 and o0 >= 0 and o1 < 1024i0 + i1 - 1024o0)); Stmt_bb138[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 >= 0 and o0 <= 1023 and o1 > 1024i0 + i1 - 1024o0) or (i0 <= 1023 and o0 >= 0 and o1 < 1024i0 + i1 - 1024o0)); Stmt_bb126[i0, i1] -> Stmt_bb126[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 >= 0 and o0 <= 1023 and o1 > 1024i0 + i1 - 1024o0) or (i0 <= 1023 and o0 >= 0 and o1 < 1024i0 + i1 - 1024o0)); Stmt_bb150[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 >= 0 and o0 <= 1023 and o1 > 1024i0 + i1 - 1024o0) or (i0 <= 1023 and o0 >= 0 and o1 < 1024i0 + i1 - 1024o0)); Stmt_bb42[i0, i1] -> Stmt_bb42[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 >= 0 and o0 <= 1023 and o1 > 1024i0 + i1 - 1024o0) or (i0 <= 1023 and o0 >= 0 and o1 < 1024i0 + i1 - 1024o0)); Stmt_bb78[i0, i1] -> Stmt_bb78[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 >= 0 and o0 <= 1023 and o1 > 1024i0 + i1 - 1024o0) or (i0 <= 1023 and o0 >= 0 and o1 < 1024i0 + i1 - 1024o0)); Stmt_bb114[i0, i1] -> Stmt_bb114[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 >= 0 and o0 <= 1023 and o1 > 1024i0 + i1 - 1024o0) or (i0 <= 1023 and o0 >= 0 and o1 < 1024i0 + i1 - 1024o0)); Stmt_bb174[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 >= 0 and o0 <= 1023 and o1 > 1024i0 + i1 - 1024o0) or (i0 <= 1023 and o0 >= 0 and o1 < 1024i0 + i1 - 1024o0)); Stmt_bb162[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 >= 0 and o0 <= 1023 and o1 > 1024i0 + i1 - 1024o0) or (i0 <= 1023 and o0 >= 0 and o1 < 1024i0 + i1 - 1024o0)); Stmt_bb54[i0, i1] -> Stmt_bb54[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 >= 0 and o0 <= 1023 and o1 > 1024i0 + i1 - 1024o0) or (i0 <= 1023 and o0 >= 0 and o1 < 1024i0 + i1 - 1024o0)) }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"

test/DependenceInfo/reduction_simple_iv_debug_wrapped_dependences.ll

 ; RUN: opt %loadPolly -polly-dependences -analyze -debug-only=polly-dependence 2>&1 < %s | FileCheck %s
 ;
 ; REQUIRES: asserts
 ;
 ; CHECK:      Read: { [Stmt_for_cond[i0] -> MemRef_sum[0{{\]\]}} -> MemRef_sum[0] : 0 <= i0 <= 100 }
 ; CHECK-NEXT: Write: { [Stmt_for_cond[i0] -> MemRef_sum[0{{\]\]}} -> MemRef_sum[0] : 0 <= i0 <= 100 }
 ; CHECK-NEXT: MayWrite: {  }
 ;
 ; CHECK:      Wrapped Dependences:
 ; CHECK-NEXT:     RAW dependences:
 ; CHECK-NEXT:         { [Stmt_for_cond[i0] -> MemRef_sum[0{{\]\]}} -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0{{\]\]}} : 0 <= i0 <= 99 }
 ; CHECK-NEXT:     WAR dependences:
-; CHECK-NEXT:         {  }
+; CHECK-NEXT:         { [Stmt_for_cond[i0] -> MemRef_sum[0{{\]\]}} -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0{{\]\]}} : 0 <= i0 <= 99 }
 ; CHECK-NEXT:     WAW dependences:
 ; CHECK-NEXT:         { [Stmt_for_cond[i0] -> MemRef_sum[0{{\]\]}} -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0{{\]\]}} : 0 <= i0 <= 99 }
 ; CHECK-NEXT:     Reduction dependences:
 ; CHECK-NEXT:         n/a
 ;
 ; CHECK:      Final Wrapped Dependences:
 ; CHECK-NEXT:     RAW dependences:
 ; CHECK-NEXT:         {  }

test/DependenceInfo/reduction_simple_privatization_deps_2.ll

 ; RUN: opt %loadPolly -polly-dependences -analyze < %s | FileCheck %s
 ;
 ; CHECK:      RAW dependences:
 ; CHECK-NEXT:     { Stmt_S2[i0] -> Stmt_S0[1 + i0] : 0 <= i0 <= 98; Stmt_S0[i0] -> Stmt_S1[i0, o1] : 0 <= i0 <= 99 and 0 <= o1 <= 99; Stmt_S1[i0, i1] -> Stmt_S2[i0] : 0 <= i0 <= 99 and 0 <= i1 <= 99 }
 ; CHECK-NEXT: WAR dependences:
-; CHECK-NEXT:     {  }
+; CHECK-NEXT:     { Stmt_S2[i0] -> Stmt_S0[1 + i0] : 0 <= i0 <= 98; Stmt_S0[i0] -> Stmt_S1[i0, o1] : 0 <= i0 <= 99 and 0 <= o1 <= 99; Stmt_S1[i0, i1] -> Stmt_S2[i0] : 0 <= i0 <= 99 and 0 <= i1 <= 99 }
 ; CHECK-NEXT: WAW dependences:
 ; CHECK-NEXT:     { Stmt_S2[i0] -> Stmt_S0[1 + i0] : 0 <= i0 <= 98; Stmt_S0[i0] -> Stmt_S1[i0, o1] : 0 <= i0 <= 99 and 0 <= o1 <= 99; Stmt_S1[i0, i1] -> Stmt_S2[i0] : 0 <= i0 <= 99 and 0 <= i1 <= 99 }
 ; CHECK-NEXT: Reduction dependences:
 ; CHECK-NEXT:     { Stmt_S1[i0, i1] -> Stmt_S1[i0, 1 + i1] : 0 <= i0 <= 99 and 0 <= i1 <= 98 }
 ;
 ;    void f(int *sum) {
 ;      for (int i = 0; i < 100; i++) {
 ; S0:    *sum *= 42;

test/DependenceInfo/reduction_simple_privatization_deps_w_parameter.ll

 ; RUN: opt %loadPolly -polly-dependences -analyze < %s | FileCheck %s
 ;
 ; CHECK:      RAW dependences:
 ; CHECK-NEXT:     [N] -> { Stmt_S0[] -> Stmt_S1[o0] : N >= 11 and 0 <= o0 <= 1023; Stmt_S1[i0] -> Stmt_S2[] : N >= 11 and 0 <= i0 <= 1023 }
 ; CHECK-NEXT: WAR dependences:
-; CHECK-NEXT:     [N] -> {  }
+; CHECK-NEXT:     [N] -> { Stmt_S1[i0] -> Stmt_S2[] : N >= 11 and 0 <= i0 <= 1023 }
 ; CHECK-NEXT: WAW dependences:
 ; CHECK-NEXT:     [N] -> { Stmt_S0[] -> Stmt_S1[o0] : N >= 11 and 0 <= o0 <= 1023; Stmt_S1[i0] -> Stmt_S2[] : N >= 11 and 0 <= i0 <= 1023 }
 ; CHECK-NEXT: Reduction dependences:
 ; CHECK-NEXT:     [N] -> { Stmt_S1[i0] -> Stmt_S1[1 + i0] : N >= 11 and 0 <= i0 <= 1022 }
 ;
 ;    void f(int *sum, int N) {
 ;      if (N >= 10) {
 ; S0:    *sum = 0;