[Polly] [DependenceInfo] Change reduction building to use May-writes.

[bollu]

Summary

Change the way reductions are built to use may-writes and not use
the transitive closure. This simplifies the process of creating
reduction dependences. It also eliminates the need for StrictWAW.

Reduction dependences (RED) are widened. This is different
from previous behaviour where the reduction dependences were "exact"
while TC_RED was the widened dependences.

This also affected the matrix multiplication pattern match. It earlier
used to expect reduction dependences to look like:

S(i0, i1, ..., ik, ... in) -> S(i0, i1, ..., ik + 1, ...in)

Now, that is no longer possible since the reduction dependences will be
wider, and will look like so:

S(i0, i1, ..., ik, ... in) -> S(i0, i1, ..., ok, ...in) where
ik < ok < N.

So, we choose to allow anything along the "ok" dimension, since the other
checks make sure that illegal memory access cannot happen
in the first place.

[bollu]

@gareevroman: Could you take a look at containsOnlyMatMulDep and affirm that the assumption made is correct?

[bollu]

@gareevroman , @Meinersbur: ping, a review would be appreciated.

[Meinersbur]

include/polly/DependenceInfo.h

165

Leftover?

lib/Analysis/DependenceInfo.cpp

176

If you do not isl_map_copy() the both cases above, you don't need to free accdom.

Effectively, you are only appending || MA->isReductionLike() to the second conditional.

It seems to have the side-effect that all reduction candidates are treated as May-Writes from here on. A candidate doesn't necessarily need to turn out to be a reduction. I don't like the idea that we pessimize the dependences/schedule optimizer based on some in-between heuristic of a detection algorithm.

To see what I mean: Why not just add all writes to MayWrite and leave MustWrite empty, since every access is potentially a reduction.

417–418

Could you add a comment to this line what it is doing?

lib/Transform/ScheduleOptimizer.cpp

771

<anything> doesn't match the implementation which checks for a constant delta.

[gareevroman]

@gareevroman: Could you take a look at containsOnlyMatMulDep and affirm that the assumption made is correct?

@bollu: I think it's correct. However, what should we do if we need "exact" reduction dependences in future? How can we compute them in case that patch is applied?

lib/Transform/ScheduleOptimizer.cpp

788

Why do you define a separate variable DomainDep for isl_union_map_extract_map(Dep, Space)?

793

We can use the following code to avoid using the foundNonZeroDimension:

  ...
  for (int i = 0; i < DeltasDimNum; i++) {
    auto *Val = isl_set_plain_get_val_if_fixed(Deltas, isl_dim_set, i);
    Pos = Pos < 0 && !isl_val_is_zero(Val) ? i : Pos;
    if (!isl_val_is_zero(Val) && i != Pos) {
      isl_val_free(Val);
      isl_set_free(Deltas);
      return false;
    }
    isl_val_free(Val);
  }
  isl_set_free(Deltas);
  if (DeltasDimNum == 0 || Pos < 0)
    return false;
  return true;
}

[bollu]

@gareevroman I don't believe there is a way to get back the exact reduction dependences that we had access to previously. (Unless we change the dependence generation to be quite different from what we have now).

lib/Analysis/DependenceInfo.cpp

176

for the code structure: I'll change it.

Yes, you're right, I group all May-writes + ReductionLike into the MayWrite now.

Why not just add all writes to MayWrite and leave MustWrite empty, since every access is potentially a reduction.

This is too pessimistic, since from what I understand, we know which accesses _cannot_ be treated as reductions. This is a decent compromise IMO between exactness and simplicity.

However, I do agree that the change does reduce the quality of information we produce (in terms of RED dependences)

[bollu]

• [NFC] Simplify creation of MayWrite and MustWrite
• [NFC] comment on why we take the union with the reverse of TC_RED

[bollu]

• [Polly] [DependenceInfo] Change reduction building to use May-writes.
• [NFC] Simplify creation of MayWrite and MustWrite
• [NFC] comment on why we take the union with the reverse of TC_RED
• [NFC] remove forgotten comment in DependenceInfo.h, remove temporary variable from lib/Transform/ScheduleOptimizer.cpp

[bollu]

@Meinersbur , @gareevroman : I've made changes I was comfortable with. Could you take another look?

lib/Analysis/DependenceInfo.cpp

417–418

@Meinersbur: I wrote that to keep it consistent with that the original reduction implementation does. I believe we need the backwards dependences to make sure that dependences are tracked even when optimisations like loop reversal takes place.

lib/Transform/ScheduleOptimizer.cpp

771

Yes. However, I believe that containsOnlyMatrMultAcc also checks for the correct stride.

In the RED information that is generated from this change onwards, we lose access to fine-grained dependence information about reductions. as @gareevroman mentioned, perhaps this is an issue.

@Meinersbur: if you can think of an example that will break on this particular check, then I will be glad to know of it. I tried a little bit and couldn't come up with anything.

788

Ah, good catch. I'll eliminate the frivolous temporary variable.

793

Yes, I initially did keep it that way. However, I felt that we are overloading Pos as both a "state store" of whether we have found the dimension or not (based on it being < 0) and as a "value store" based on the nonzero value it takes.

I personally find it clearer with the extra boolean. However, if this impacts performance or something along those lines, I do not mind modifying it.

[Meinersbur]

Is it possible to put the changes to containsOnlyMatMulDep into a separate patch? Then we can discuss the changes to the reduction detection separately.

lib/Analysis/DependenceInfo.cpp

176

Yes, you're right, I group all May-writes + ReductionLike into the MayWrite now.

So could you rename it such that it reflects its purpose?

This is a decent compromise IMO between exactness and simplicity. However, I do agree that the change does reduce the quality of information we produce (in terms of RED dependences)

I don't agree on simplicity. Merging MayWrite and reduction candidates overcharges a variable with two meanings that are subtly different. If the purpose is to have less lines of code, put the common code in the separate function and call it once for MayWrite and ReductionLike.

The reason I don't like this is that switching reduction detection has an influence on something unrelated to reductions. If something does not work as expected it will take a long time until one realizes that the reduction detection was the cause, even though there are no reductions in the code. IMHO this is not worth any perceived simplicity of the code.

If your goal is to save computation time, you should show how much is saved to justify the regression and provide an option for the non-heuristic behaviour (this could already be switching off reductions altogether, though I'd prefer being able to do both at the same time).

417–418

Looks ok.

lib/Transform/ScheduleOptimizer.cpp

771

My remark war about the comment being wrong, not the code. S(..., k, ...) -> S(..., <anything>, ...) is the same as S(...) -> S(...).

However, from the code I read that it checks for S(..., k, ...) -> S(..., k+c, ...) with a constant c.

793

I think this is more about changing fewer lines so the review is easier and avoids non-intended changes.

Since this is already reviewed, no need to change it back (if Roman is fine with it).

[bollu]

Is it possible to put the changes to containsOnlyMatMulDep into a separate patch? Then we can discuss the changes to the reduction detection separately.

Unfortunately, no. This will cause a test case to break (since we now have coarser RED dependences).

lib/Analysis/DependenceInfo.cpp

176

I agree with what you are saying. We are overloading the "May write" semantics.

What if I create a separate union_map called as Reduction, add all the reductions to that in collectInfo, and then have a function in the dependence computation called taintWritesWithReduction which takes a union of the two? That way, we can document the rationale for fusing them at the site of the function. And, if something goes wrong, it will be easy to switch from the tainted-writes back to the non-tainted writes while experimenting.

[Meinersbur]

lib/Analysis/DependenceInfo.cpp

176

That sounds better.

However, wouldn't switching off taintWritesWithReduction have the same effect as -polly-detect-reductions=false? And what is the compile-time speedup?

lib/Transform/ScheduleOptimizer.cpp

771

It looks fine as done in D32157.

[bollu]

lib/Analysis/DependenceInfo.cpp

176

Yes, the two would be equivalent.

I haven't benchmarked the speedup, but there should be one since this eliminates a call to buildFlow from the StrictWAW computation. It also removes the (potentially) expensive transitive closure operation.

[bollu]

lib/Transform/ScheduleOptimizer.cpp

771

Actually, thinking about this, if it were only k+c, then this is pointless. This implementation is correct, in that it allows for ranges of values with the non-zero dimension.

Precisely, we wish to look for both lower and upper bounds along a single dimension. So, it should be something along the lines of:

matrix-dependences

S[..., k, ...] -> S[..., k', ...] where k < k' <= N

Since we will have widened dependences.

I had implemented the precise check [as a proof of concept here: https://github.com/bollu/polly/blob/remove-privatization-with-may-reduction-fix-matmul/lib/Transform/ScheduleOptimizer.cpp#L875](https://github.com/bollu/polly/blob/remove-privatization-with-may-reduction-fix-matmul/lib/Transform/ScheduleOptimizer.cpp#L875).

However, I decided that the check did not make sense - I was being overly cautious to check for exactly what I expected with widened matrix multiplication dependences in the constraints, because I did not understand the problem well enough. It is also brittle, since I look at the shape of the constraints, which can change under representations from what I understand.

I would like to hear your thoughts on this.

[Meinersbur]

lib/Transform/ScheduleOptimizer.cpp

771

I see that I misunderstood one thing. It uses isl_set_plain_get_val_if_fixed, but it is used only to check that it is zero. If it is nonzero, its value is ignored.

That means, it checks for:
S(i_0, ..., i_{n-1}) -> S(i_0, i_{k-1},i'_k,i_{k+1},..,i_{n-1}) where i'_k != i_k.

Is this correct?

[gareevroman]

lib/Transform/ScheduleOptimizer.cpp

793

Yes, I initially did keep it that way. However, I felt that we are overloading Pos as both a "state store" of whether we have found the dimension or not (based on it being < 0) and as a "value store" based on the nonzero value it takes.

AFAIK, the overloading doesn't deviate from the LLVM Coding Standards.

I personally find it clearer with the extra boolean. However, if this impacts performance or something along those lines, I do not mind modifying it.

Okay. However, it seems that it doesn't remove the overloading of 'Pos'. It still used as a "state store" and as a "value store".

Could you factor out the check of the form of the dependency to a separate function (I find it harder to read now)?

include/polly/DependenceInfo.h

 private:
   /// Create an empty dependences struct.
   explicit Dependences(const std::shared_ptr<isl_ctx> &IslCtx,
                        AnalysisLevel Level)
       : RAW(nullptr), WAR(nullptr), WAW(nullptr), RED(nullptr), TC_RED(nullptr),
         IslCtx(IslCtx), Level(Level) {}
 
   /// Calculate and add at the privatization dependences.
-  void addPrivatizationDependences();
+  // void addPrivatizationDependences();
 
   /// Calculate the dependences for a certain SCoP @p S.
   void calculateDependences(Scop &S);
 
   /// Set the reduction dependences for @p MA to @p Deps.
   void setReductionDependences(MemoryAccess *MA, __isl_take isl_map *Deps);
 
   /// Free the objects associated with this Dependences struct.

lib/Analysis/DependenceInfo.cpp

for (MemoryAccess *MA : Stmt) {
                  "handling.");
           isl_map *Schedule = tag(StmtScheduleMap, MA, Level);
           StmtSchedule = isl_union_map_add_map(StmtSchedule, Schedule);
         }
       }
 
       if (MA->isRead())
         Read = isl_union_map_add_map(Read, accdom);
-      else if (MA->isMayWrite())
-        MayWrite = isl_union_map_add_map(MayWrite, accdom);
-      else
-        MustWrite = isl_union_map_add_map(MustWrite, accdom);
+      else {
+        if (MA->isMayWrite() || MA->isReductionLike()) {
+          MayWrite = isl_union_map_add_map(MayWrite, isl_map_copy(accdom));
+        } else {
+          MustWrite = isl_union_map_add_map(MustWrite, isl_map_copy(accdom));
+        }
+        isl_map_free(accdom);
+      }
     }
 
     if (!ReductionArrays.empty() && Level == Dependences::AL_Statement)
       StmtSchedule = isl_union_map_add_map(StmtSchedule, Stmt.getSchedule());
   }
 
   StmtSchedule =
       isl_union_map_intersect_params(StmtSchedule, S.getAssumedContext());
   TaggedStmtDomain = isl_union_map_domain(StmtSchedule);
 
   ReductionTagMap = isl_union_map_coalesce(ReductionTagMap);
   Read = isl_union_map_coalesce(Read);
   MustWrite = isl_union_map_coalesce(MustWrite);
   MayWrite = isl_union_map_coalesce(MayWrite);
 }
 
-/// Fix all dimension of @p Zero to 0 and add it to @p user
-static isl_stat fixSetToZero(__isl_take isl_set *Zero, void *user) {
-  isl_union_set **User = (isl_union_set **)user;
-  for (unsigned i = 0; i < isl_set_dim(Zero, isl_dim_set); i++)
-    Zero = isl_set_fix_si(Zero, isl_dim_set, i, 0);
-  *User = isl_union_set_add_set(*User, Zero);
-  return isl_stat_ok;
-}
-
-/// Compute the privatization dependences for a given dependency @p Map
-///
-/// Privatization dependences are widened original dependences which originate
-/// or end in a reduction access. To compute them we apply the transitive close
-/// of the reduction dependences (which maps each iteration of a reduction
-/// statement to all following ones) on the RAW/WAR/WAW dependences. The
-/// dependences which start or end at a reduction statement will be extended to
-/// depend on all following reduction statement iterations as well.
-/// Note: "Following" here means according to the reduction dependences.
-///
-/// For the input:
-///
-///  S0:   *sum = 0;
-///        for (int i = 0; i < 1024; i++)
-///  S1:     *sum += i;
-///  S2:   *sum = *sum * 3;
-///
-/// we have the following dependences before we add privatization dependences:
-///
-///   RAW:
-///     { S0[] -> S1[0]; S1[1023] -> S2[] }
-///   WAR:
-///     {  }
-///   WAW:
-///     { S0[] -> S1[0]; S1[1024] -> S2[] }
-///   RED:
-///     { S1[i0] -> S1[1 + i0] : i0 >= 0 and i0 <= 1022 }
-///
-/// and afterwards:
-///
-///   RAW:
-///     { S0[] -> S1[i0] : i0 >= 0 and i0 <= 1023;
-///       S1[i0] -> S2[] : i0 >= 0 and i0 <= 1023}
-///   WAR:
-///     {  }
-///   WAW:
-///     { S0[] -> S1[i0] : i0 >= 0 and i0 <= 1023;
-///       S1[i0] -> S2[] : i0 >= 0 and i0 <= 1023}
-///   RED:
-///     { S1[i0] -> S1[1 + i0] : i0 >= 0 and i0 <= 1022 }
-///
-/// Note: This function also computes the (reverse) transitive closure of the
-///       reduction dependences.
-void Dependences::addPrivatizationDependences() {
-  isl_union_map *PrivRAW, *PrivWAW, *PrivWAR;
-
-  // The transitive closure might be over approximated, thus could lead to
-  // dependency cycles in the privatization dependences. To make sure this
-  // will not happen we remove all negative dependences after we computed
-  // the transitive closure.
-  TC_RED = isl_union_map_transitive_closure(isl_union_map_copy(RED), nullptr);
-
-  // FIXME: Apply the current schedule instead of assuming the identity schedule
-  //        here. The current approach is only valid as long as we compute the
-  //        dependences only with the initial (identity schedule). Any other
-  //        schedule could change "the direction of the backward dependences" we
-  //        want to eliminate here.
-  isl_union_set *UDeltas = isl_union_map_deltas(isl_union_map_copy(TC_RED));
-  isl_union_set *Universe = isl_union_set_universe(isl_union_set_copy(UDeltas));
-  isl_union_set *Zero = isl_union_set_empty(isl_union_set_get_space(Universe));
-  isl_union_set_foreach_set(Universe, fixSetToZero, &Zero);
-  isl_union_map *NonPositive = isl_union_set_lex_le_union_set(UDeltas, Zero);
-
-  TC_RED = isl_union_map_subtract(TC_RED, NonPositive);
-
-  TC_RED = isl_union_map_union(
-      TC_RED, isl_union_map_reverse(isl_union_map_copy(TC_RED)));
-  TC_RED = isl_union_map_coalesce(TC_RED);
-
-  isl_union_map **Maps[] = {&RAW, &WAW, &WAR};
-  isl_union_map **PrivMaps[] = {&PrivRAW, &PrivWAW, &PrivWAR};
-  for (unsigned u = 0; u < 3; u++) {
-    isl_union_map **Map = Maps[u], **PrivMap = PrivMaps[u];
-
-    *PrivMap = isl_union_map_apply_range(isl_union_map_copy(*Map),
-                                         isl_union_map_copy(TC_RED));
-    *PrivMap = isl_union_map_union(
-        *PrivMap, isl_union_map_apply_range(isl_union_map_copy(TC_RED),
-                                            isl_union_map_copy(*Map)));
-
-    *Map = isl_union_map_union(*Map, *PrivMap);
-  }
-
-  isl_union_set_free(Universe);
-}
-
 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)
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));
 
-    // 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.
-    //       }
-    //     }
-
-    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) {
+      isl_union_flow *Flow;
       Flow = buildFlow(Read, MustWrite, MayWrite, Schedule);
       RAW = isl_union_flow_get_may_dependence(Flow);
       isl_union_flow_free(Flow);
 
       Flow = buildFlow(Write, MustWrite, MayWrite, Schedule);
       WAW = isl_union_flow_get_may_dependence(Flow);
       isl_union_flow_free(Flow);
 
DEBUG(dbgs() << "Read: " << Read << "\n";
 
     // 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);
-    isl_union_map_free(StrictWAW);
-    RAW = WAW = WAR = StrictWAW = nullptr;
+    RAW = WAW = WAR = 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));
for (MemoryAccess *MA : Stmt) {
       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, StrictWAW);
+  RED = isl_union_map_intersect(RED, isl_union_map_copy(WAW));
 
   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();
+    TC_RED = isl_union_map_union(isl_union_map_reverse(isl_union_map_copy(RED)),
+                                 isl_union_map_copy(RED));
+    TC_RED = isl_union_map_coalesce(TC_RED);
   }
 
   DEBUG({
     dbgs() << "Final Wrapped Dependences:\n";
     dump();
     dbgs() << "\n";
   });
 

lib/Transform/ScheduleOptimizer.cpp

static bool containsOnlyMatrMultAcc(__isl_keep isl_map *PartialSchedule,
   isl_map_free(MapJ);
   isl_map_free(MapK);
   return true;
 }
 
 /// Check for dependencies corresponding to the matrix multiplication.
 ///
 /// Check that there is only true dependence of the form
-/// S(..., k, ...) -> S(..., k + 1, …), where S is the SCoP statement
+/// S(..., k, ...) -> S(..., <anything>, ...), where S is the SCoP statement
 /// represented by @p Schedule and k is @p Pos. Such a dependence corresponds
 /// to the dependency produced by the matrix multiplication.
 ///
 /// @param  Schedule The schedule of the SCoP statement.
 /// @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 *Dep = D->getDependences(Dependences::TYPE_RAW);
-  auto *Red = D->getDependences(Dependences::TYPE_RED);
-  if (Red)
-    Dep = isl_union_map_union(Dep, Red);
+  auto *Dep = D->getDependences(Dependences::TYPE_RAW | Dependences::TYPE_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));
+  auto *DomainDep = isl_union_map_extract_map(Dep, Space);
+  auto *Deltas = isl_map_deltas(DomainDep);
   isl_union_map_free(Dep);
   int DeltasDimNum = isl_set_dim(Deltas, isl_dim_set);
+
+  bool foundNonZeroDimension = false;
+
   for (int i = 0; i < DeltasDimNum; i++) {
     auto *Val = isl_set_plain_get_val_if_fixed(Deltas, isl_dim_set, i);
-    Pos = Pos < 0 && isl_val_is_one(Val) ? i : Pos;
-    if (isl_val_is_nan(Val) ||
-        !(isl_val_is_zero(Val) || (i == Pos && isl_val_is_one(Val)))) {
-      isl_val_free(Val);
+    if (isl_val_is_zero(Val)) {
+      isl_val_free(Val);
+      continue;
+    }
+
+    // we have already found a nonzero subspace. Getting another
+    // nonzero subspace means that we have a dependence along another dimension.
+    if (foundNonZeroDimension) {
+      isl_set_free(Deltas);
+      return false;
+    }
+    foundNonZeroDimension = true;
+
+    // Pos < 0, we need to set the parameter which corresponds the dependence.
+    if (Pos < 0) {
+      Pos = i;
+    }
+    // Pos > 0, we should verify that the dimension is the one along which
+    // the dependence is supposed to be,
+    else if (Pos != i) {
       isl_set_free(Deltas);
       return false;
     }
-    isl_val_free(Val);
   }
   isl_set_free(Deltas);
-  if (DeltasDimNum == 0 || Pos < 0)
+  if (DeltasDimNum == 0 || !foundNonZeroDimension)
     return false;
   return true;
 }
 
 /// Check if the SCoP statement could probably be optimized with analytical
 /// modeling.
 ///
 /// containsMatrMult tries to determine whether the following conditions

test/DependenceInfo/reduction_complex_location.ll

 ; RUN: opt %loadPolly -polly-dependences -analyze < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-dependences -polly-dependences-analysis-level=reference-wise -analyze < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-dependences -polly-dependences-analysis-level=access-wise -analyze < %s | FileCheck %s
 ;
 ; CHECK:      RAW dependences:
 ; CHECK-NEXT:     {  }
 ; CHECK-NEXT: WAR dependences:
 ; CHECK-NEXT:     {  }
 ; CHECK-NEXT: WAW dependences:
 ; CHECK-NEXT:     {  }
 ; CHECK-NEXT: Reduction dependences:
-; CHECK-NEXT:     { Stmt_for_body3[i0, i1] -> Stmt_for_body3[2 + i0, -1 + i1] : 0 <= i0 <= 97 and 0 < i1 <= 99 }
+; CHECK-NEXT:     { Stmt_for_body3[i0, i1] -> Stmt_for_body3[o0, o1] : 2o1 = i0 + 2i1 - o0 and i0 >= 0 and i1 <= 99 and i0 < o0 <= 99 and o0 <= i0 + 2i1 }
 ;
 ; void f(int *sum) {
 ;   for (int i = 0; i < 100; i++)
 ;     for (int j = 0; j < 100; j++)
 ;       sum[i+j*2] += j * i;
 ; }
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
 

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:    RAW dependences:
+; CHECK-NEXT:   { Stmt_for_body[i0] -> Stmt_for_body[1 + i0] : 0 <= i0 <= 1022 }
 ; CHECK-NEXT: WAR dependences:
-; CHECK-NEXT:     { Stmt_for_body[i0] -> Stmt_for_body[1 + i0] : 0 <= i0 <= 1022 }
+; 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:   { 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 }
+; CHECK-NEXT:    { Stmt_for_body[i0] -> Stmt_for_body[o0] : i0 >= 0 and i0 < o0 <= 1023 }
 ;
 ;
 ;    void AandSum(int *restrict sum, int *restrict A) {
 ;      for (int i = 0; i < 1024; i++) {
 ;        A[i] = A[i] + A[i - 1];
 ;        A[i - 1] = A[i] + A[i - 2];
 ;        *sum += i;
 ;      }

test/DependenceInfo/reduction_mixed_reduction_and_non_reduction_dependences.ll

 ; RUN: opt %loadPolly -polly-dependences -analyze < %s | FileCheck %s
 ;
 ; CHECK:      RAW dependences:
-; CHECK-NEXT:     { Stmt_for_body3[i0, i1] -> Stmt_for_body3[i0 + i1, o1] : i0 >= 0 and 0 <= i1 <= 1023 - i0 and i1 <= 1 and 0 < o1 <= 511 }
+; CHECK-NEXT:     { Stmt_for_body3[i0, i1] -> Stmt_for_body3[i0 + i1, o1] : i0 >= 0 and 0 <= i1 <= 1023 - i0 and i1 <= 511 and 0 < o1 <= 511 }
 ; CHECK-NEXT: WAR dependences:
 ; CHECK-NEXT:     {  }
 ; CHECK-NEXT: WAW dependences:
-; CHECK-NEXT:     { Stmt_for_body3[i0, i1] -> Stmt_for_body3[1 + i0, -1 + i1] : 0 <= i0 <= 1022 and 2 <= i1 <= 511; Stmt_for_body3[i0, 2] -> Stmt_for_body3[2 + i0, 0] : 0 <= i0 <= 1021 }
+; CHECK-NEXT:     { Stmt_for_body3[i0, i1] -> Stmt_for_body3[o0, i0 + i1 - o0] : i0 >= 0 and i1 <= 511 and i0 < o0 <= 1023 and o0 < i0 + i1 }
 ; CHECK-NEXT: Reduction dependences:
-; CHECK-NEXT:     { Stmt_for_body3[i0, 1] -> Stmt_for_body3[1 + i0, 0] : 0 <= i0 <= 1022 }
+; CHECK-NEXT:     { Stmt_for_body3[i0, i1] -> Stmt_for_body3[i0 + i1, 0] : i0 >= 0 and 0 < i1 <= 1023 - i0 and i1 <= 511 }
 ;
 ; void f(int *sum) {
 ;   for (int i = 0; i < 1024; i++)
 ;     for (int j = 0; j < 512; j++)
 ;       sum[i + j] = sum[i] + 3;
 ; }
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
 

test/DependenceInfo/reduction_multiple_loops_array_sum.ll

 ; RUN: opt -basicaa %loadPolly -polly-dependences -analyze < %s | FileCheck %s
 ; RUN: opt -basicaa %loadPolly -polly-dependences -polly-dependences-analysis-level=reference-wise -analyze < %s | FileCheck %s
 ; RUN: opt -basicaa %loadPolly -polly-dependences -polly-dependences-analysis-level=access-wise -analyze < %s | FileCheck %s
 ;
 ; Verify that only the inner reduction like accesses cause reduction dependences
 ;
 ; CHECK:      Reduction dependences:
-; CHECK-NEXT:     { Stmt_for_body3[i0, i1] -> Stmt_for_body3[i0, 1 + i1] : 0 <= i0 <= 99 and 0 <= i1 <= 98 }
+; CHECK-NEXT:     { Stmt_for_body[i0] -> Stmt_for_body[o0] : i0 >= 0 and i0 < o0 <= 99; Stmt_for_body3[i0, i1] -> Stmt_for_body3[o0, o1] : i0 >= 0 and 0 <= i1 <= 99 and i0 < o0 <= 99 and 0 <= o1 <= 99; Stmt_for_body3[i0, i1] -> Stmt_for_body3[i0, o1] : 0 <= i0 <= 99 and i1 >= 0 and i1 < o1 <= 99 }
 ;
 ; void f(int * restrict A, int * restrict sum) {
 ;   int i, j, k;
 ;   for (i = 0; i < 100; i++) {
 ;     *sum *= 7;
 ;     for (j = 0; j < 100; j++) {
 ;       *sum += A[i+j];
 ;       for (k = 0; k< 100; k++) {}

test/DependenceInfo/reduction_multiple_loops_array_sum_2.ll

 ; RUN: opt %loadPolly -polly-dependences -analyze -basicaa < %s | FileCheck %s
 ;
 ; CHECK:      RAW dependences:
 ; CHECK-NEXT:     {  }
 ; CHECK-NEXT: WAR dependences:
 ; CHECK-NEXT:     {  }
 ; CHECK-NEXT: WAW dependences:
 ; CHECK-NEXT:     {  }
 ; CHECK-NEXT: Reduction dependences:
-; CHECK-NEXT:     { Stmt_for_body3[i0, i1] -> Stmt_for_body3[i0, 1 + i1] : 0 <= i0 <= 99 and 0 <= i1 <= 98; Stmt_for_body3[i0, 99] -> Stmt_for_body3[1 + i0, 0] : 0 <= i0 <= 98 }
+; CHECK-NEXT:     { Stmt_for_body3[i0, i1] -> Stmt_for_body3[o0, o1] : i0 >= 0 and 0 <= i1 <= 99 and i0 < o0 <= 99 and 0 <= o1 <= 99; Stmt_for_body3[i0, i1] -> Stmt_for_body3[i0, o1] : 0 <= i0 <= 99 and i1 >= 0 and i1 < o1 <= 99 }
 ;
 ; int f(int * restrict A, int * restrict sum) {
 ;   int i, j, k;
 ;   for (i = 0; i < 100; i++) {
 ;     for (j = 0; j < 100; j++) {
 ;       sum += A[i+j];
 ;       for (k = 0; k< 100; k++) {}
 ;     }

test/DependenceInfo/reduction_multiple_loops_array_sum_3.ll

 ; RUN: opt %loadPolly -polly-dependences -analyze -basicaa < %s | FileCheck %s
 ;
 ; CHECK:      Reduction dependences:
-; CHECK-NEXT:     { Stmt_for_inc[i0, i1] -> Stmt_for_inc[i0, 1 + i1] : 0 <= i0 <= 99 and 0 <= i1 <= 98 }
+; CHECK-NEXT:     { Stmt_for_inc[i0, i1] -> Stmt_for_inc[i0, o1] : 0 <= i0 <= 99 and i1 >= 0 and i1 < o1 <= 99 }
 ;
 ; int f(int * __restrict__ A) {
 ;   int i, j, sum = 0;
 ;   for (k = 0; k < 37; k = g(k)) {
 ;     for (i = 0; i < 100; i++) {
 ;       sum *= 2;
 ;       for (j = 0; j < 100; j++) {
 ;         sum += A[i+j];

test/DependenceInfo/reduction_multiple_reductions.ll

 ; RUN: opt %loadPolly -basicaa -polly-dependences -analyze < %s | FileCheck %s
 ;
 ; Verify we do not have dependences between the if and the else clause
 ;
 ; CHECK:      RAW dependences:
 ; CHECK-NEXT:     {  }
 ; CHECK-NEXT: WAR dependences:
 ; CHECK-NEXT:     {  }
 ; CHECK-NEXT: WAW dependences:
 ; CHECK-NEXT:     {  }
 ; CHECK-NEXT: Reduction dependences:
-; CHECK-NEXT:     { Stmt_if_else[i0] -> Stmt_if_else[1 + i0] : 512 <= i0 <= 1022; Stmt_if_then[i0] -> Stmt_if_then[1 + i0] : 0 <= i0 <= 510 }
+; CHECK-NEXT:     { Stmt_if_else[i0] -> Stmt_if_else[o0] : i0 >= 512 and i0 < o0 <= 1023; Stmt_if_then[i0] -> Stmt_if_then[o0] : i0 >= 0 and i0 < o0 <= 511 }
 ;
 ; void f(int *restrict sum, int *restrict prod) {
 ;   for (int i = 0; i < 1024; i++)
 ;     if (i < 512)
 ;       *sum += i;
 ;     else
 ;       *prod *= 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:     { Stmt_S2[i0, i1] -> Stmt_S3[i0] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023; Stmt_S0[i0] -> Stmt_S2[i0, o1] : 0 <= i0 <= 1023 and 0 <= o1 <= 1023; Stmt_S1[i0, i1] -> Stmt_S3[i0] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023; Stmt_S1[i0, i1] -> Stmt_S2[i0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o1 <= 1023; Stmt_S0[i0] -> Stmt_S3[i0] : 0 <= i0 <= 1023; Stmt_S3[i0] -> Stmt_S0[1 + i0] : 0 <= i0 <= 1022; Stmt_S0[i0] -> Stmt_S1[i0, o1] : 0 <= i0 <= 1023 and 0 <= o1 <= 1023 }
 ; CHECK-NEXT: WAR 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:     { Stmt_S0[i0] -> Stmt_S1[i0, 0] : 0 <= i0 <= 1023; Stmt_S2[i0, 1023] -> Stmt_S3[i0] : 0 <= i0 <= 1023; Stmt_S3[i0] -> Stmt_S0[1 + i0] : 0 <= i0 <= 1022; Stmt_S1[i0, 1023] -> Stmt_S2[i0, 0] : 0 <= i0 <= 1023 }
 ; 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:     { Stmt_S2[i0, i1] -> Stmt_S3[i0] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023; Stmt_S0[i0] -> Stmt_S2[i0, o1] : 0 <= i0 <= 1023 and 0 <= o1 <= 1023; Stmt_S1[i0, i1] -> Stmt_S3[i0] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023; Stmt_S1[i0, i1] -> Stmt_S2[i0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o1 <= 1023; Stmt_S0[i0] -> Stmt_S3[i0] : 0 <= i0 <= 1023; Stmt_S3[i0] -> Stmt_S0[1 + i0] : 0 <= i0 <= 1022; Stmt_S0[i0] -> Stmt_S1[i0, o1] : 0 <= i0 <= 1023 and 0 <= o1 <= 1023 }
 ; 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 }
+; CHECK-NEXT:     { Stmt_S1[i0, i1] -> Stmt_S1[i0, o1] : 0 <= i0 <= 1023 and i1 >= 0 and i1 < o1 <= 1023; Stmt_S2[i0, i1] -> Stmt_S2[i0, o1] : 0 <= i0 <= 1023 and i1 >= 0 and i1 < o1 <= 1023 }
 ;
 ;    void f(int *restrict red) {
 ;      for (int j = 0; j < 1024; j++) {
 ; S0:    *red = 42 + *red * 5;
 ;        for (int i = 0; i < 1024; i++)
 ; S1:      *red *= i;
 ;        for (int i = 0; i < 1024; i++)
 ; S2:      *red += i;

test/DependenceInfo/reduction_partially_escaping_intermediate_in_other_stmt.ll

 ; RUN: opt %loadPolly -polly-dependences -analyze -basicaa < %s | FileCheck %s
 ;
 ; CHECK:      Reduction dependences:
-; CHECK-NEXT:     [N] -> { Stmt_for_body3[i0, i1] -> Stmt_for_body3[i0, 1 + i1] : 0 <= i0 <= 1023 and i1 >= 0 and 1024 - N + i0 <= i1 <= 1022 }
+; CHECK-NEXT:     [N] -> { Stmt_for_body3[i0, i1] -> Stmt_for_body3[i0, o1] : 0 <= i0 <= 1023 and i1 >= 0 and i1 < o1 <= 1023 }
 ;
 ; void f(int N, int * restrict sums, int * restrict escape) {
 ;   for (int i = 0; i < 1024; i++) {
 ;     for (int j = 0; j < 1024; j++) {
 ;       sums[i] += 5;
 ;       if (N - i + j < 1024)
 ;         escape[N - i + j] = sums[i];
 ;     }

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:     { Stmt_S0[i0] -> Stmt_S2[-1 + i0] : 0 < i0 <= 1023; 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[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[i0, i1] -> Stmt_S2[i0 + i1] : i0 >= 0 and 0 <= i1 <= 1023 - i0 }
+; CHECK-NEXT:     { Stmt_S0[i0] -> Stmt_S2[i0] : 0 <= i0 <= 1023; 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 }
+; CHECK-NEXT:     { Stmt_S1[i0, i1] -> Stmt_S1[o0, i0 + i1 - o0] : i0 >= 0 and i1 <= 1023 and i0 < o0 <= 1023 and o0 <= i0 + i1 }
 ;
 ;    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;
 ;      for (int i = 0; i < 1024; 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:     { Stmt_S1[i0] -> Stmt_S2[1 + i0, o1] : 0 <= i0 <= 97 and 0 <= o1 <= 99; 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:     { 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:     { Stmt_S3[i0] -> Stmt_S2[1 + i0, 0] : 0 <= i0 <= 97; 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:     { Stmt_S1[i0] -> Stmt_S2[1 + i0, o1] : 0 <= i0 <= 97 and 0 <= o1 <= 99; 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 }
+; CHECK-NEXT:     { Stmt_S2[i0, i1] -> Stmt_S2[i0, o1] : 0 <= i0 <= 98 and i1 >= 0 and i1 < o1 <= 99 }
 ;
 ;    void f(int *sum) {
 ;      int i, j;
 ;      for (i = 0; i < 99; i++) {
 ; S1:    sum[i + 1] += 42;
 ;        for (j = 0; j < 100; j++)
 ; S2:      sum[i] += i * j;
 ; S3:    sum[i + 1] += 7;

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:     { Stmt_S2[i0, i1] -> Stmt_S3[1 - i1] : i0 >= 0 and 0 <= i1 <= 1 - i0; 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:   { 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:     { Stmt_S2[i0, 1 - i0] -> Stmt_S3[i0] : 0 <= i0 <= 1; Stmt_S3[i0] -> Stmt_S2[1 + i0, 1 - i0] : 0 <= i0 <= 1; 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:     { Stmt_S2[i0, i1] -> Stmt_S3[1 - i1] : i0 >= 0 and 0 <= i1 <= 1 - i0; 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] }
+; CHECK-NEXT:     { Stmt_S2[i0, i1] -> Stmt_S2[o0, i1] : i0 >= 0 and i1 >= 0 and i0 < o0 <= 99 - i1 and o0 <= 98 }
 ;
 ;    void f(int *sum) {
 ;      int i, j;
 ;      for (i = 0; i < 99; i++) {
 ; S1:    sum[i + 1] += 42;
 ;        for (j = i; j < 100; j++)
 ; S2:      sum[i - j] += i * j;
 ; S3:    sum[i - 1] += 7;

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:     { Stmt_S2[i0, i1] -> Stmt_S1[i1] : i0 >= 0 and i0 < i1 <= 98; Stmt_S1[i0] -> Stmt_S2[o0, i0] : i0 >= 0 and i0 <= o0 <= 98; Stmt_S2[i0, i1] -> Stmt_S3[i1] : i0 >= 0 and i0 <= i1 <= 98; Stmt_S3[i0] -> Stmt_S2[o0, i0] : i0 >= 0 and i0 < o0 <= 98; Stmt_S1[i0] -> Stmt_S3[i0] : 0 <= i0 <= 98 }
 ; CHECK-NEXT: WAR 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:     { Stmt_S2[i0, 1 + i0] -> Stmt_S1[1 + i0] : 0 <= i0 <= 97; 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[1 + i0, i0] : 0 <= i0 <= 97 }
 ; 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:     { Stmt_S2[i0, i1] -> Stmt_S1[i1] : i0 >= 0 and i0 < i1 <= 98; Stmt_S1[i0] -> Stmt_S2[o0, i0] : i0 >= 0 and i0 <= o0 <= 98; Stmt_S2[i0, i1] -> Stmt_S3[i1] : i0 >= 0 and i0 <= i1 <= 98; Stmt_S3[i0] -> Stmt_S2[o0, i0] : i0 >= 0 and i0 < o0 <= 98; Stmt_S1[i0] -> Stmt_S3[i0] : 0 <= i0 <= 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) }
+; CHECK-NEXT:     { Stmt_S2[i0, i1] -> Stmt_S2[o0, i1] : i0 >= 0 and 0 <= i1 <= 99 and i0 < o0 <= 98 }
 ;
 ;    void f(int *sum) {
 ;      for (int i = 0; i < 99; i++) {
 ; S1:    sum[i] += 42;
 ;        for (int j = 0; j < 100; j++)
 ; S2:      sum[j] += i * j;
 ; S3:    sum[i] += 7;
 ;      }

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:       RAW dependences:
+; CHECK-NEXT:      { Stmt_S2[i0, 0] -> Stmt_S1[o0, 0] : i0 >= 0 and i0 < o0 <= 98; Stmt_S1[i0, 0] -> Stmt_S2[o0, 0] : i0 >= 0 and i0 <= o0 <= 98 }
 ; CHECK-NEXT: WAR 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: 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:     { Stmt_S2[i0, 0] -> Stmt_S1[o0, 0] : i0 >= 0 and i0 < o0 <= 98; Stmt_S1[i0, 0] -> Stmt_S2[o0, 0] : i0 >= 0 and i0 <= o0 <= 98 }
 ; CHECK-NEXT: Reduction dependences:
-; CHECK-NEXT:     { Stmt_S2[i0, i1] -> Stmt_S2[1 + i0, i1] : 0 <= i0 <= 97 and 0 < i1 <= 99 }
+; CHECK-NEXT:     { Stmt_S1[i0, 0] -> Stmt_S1[o0, 0] : i0 >= 0 and i0 < o0 <= 98; Stmt_S2[i0, i1] -> Stmt_S2[o0, i1] : i0 >= 0 and 0 <= i1 <= 99 and i0 < o0 <= 98 }
 ;
 ;    void f(int *sum) {
 ;      for (int i = 0; i < 99; i++) {
 ;        for (int j = 0; j < 1; j++)
 ; S1:      sum[j] += 42;
 ;        for (int j = 0; j < 100; j++)
 ; S2:      sum[j] += i * j;
 ;      }

test/DependenceInfo/reduction_sequence.ll

 ;        for (long j = 0; j < 1024; j++)
 ;          *A += 42;
 ;
 ;      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:     { 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)) }
+; CHECK:      RAW dependences:
+; CHECK-NEXT:     { Stmt_bb90[i0, i1] -> Stmt_bb102[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb162[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb138[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb66[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb174[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb78[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb138[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb90[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb54[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb102[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb138[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb90[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb114[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb126[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb150[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb90[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb66[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb126[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb114[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb114[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb138[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb126[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb114[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb126[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb150[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb114[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb114[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb102[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb102[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb78[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb126[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb150[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb126[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb126[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb66[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb78[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb42[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb162[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb102[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb126[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb126[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb90[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb126[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb90[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb126[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb102[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb126[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb54[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb126[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb78[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb114[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023 }
+; CHECK-NEXT: WAR dependences:
+; CHECK-NEXT:     { Stmt_bb150[1023, 1023] -> Stmt_bb162[0, 0]; Stmt_bb174[1023, 1023] -> Stmt_bb186[0, 0]; Stmt_bb102[1023, 1023] -> Stmt_bb114[0, 0]; Stmt_bb42[1023, 1023] -> Stmt_bb54[0, 0]; Stmt_bb54[1023, 1023] -> Stmt_bb66[0, 0]; Stmt_bb31[1023, 1023] -> Stmt_bb42[0, 0]; Stmt_bb162[1023, 1023] -> Stmt_bb174[0, 0]; Stmt_bb126[1023, 1023] -> Stmt_bb138[0, 0]; Stmt_bb90[1023, 1023] -> Stmt_bb102[0, 0]; Stmt_bb138[1023, 1023] -> Stmt_bb150[0, 0]; Stmt_bb66[1023, 1023] -> Stmt_bb78[0, 0]; Stmt_bb78[1023, 1023] -> Stmt_bb90[0, 0]; Stmt_bb114[1023, 1023] -> Stmt_bb126[0, 0] }
+; CHECK-NEXT: WAW dependences:
+; CHECK-NEXT:     { Stmt_bb90[i0, i1] -> Stmt_bb102[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb162[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb138[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb66[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb174[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb78[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb138[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb90[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb54[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb102[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb138[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb90[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb114[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb126[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb150[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb90[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb66[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb126[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb114[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb114[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb138[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb126[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb114[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb126[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb150[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb114[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb114[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb102[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb102[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb78[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb126[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb150[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb126[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb126[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb66[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb78[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb42[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb162[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb102[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb126[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb126[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb90[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb126[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb90[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb126[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb102[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb126[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb54[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb126[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb78[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb114[o0, o1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= o0 <= 1023 and 0 <= o1 <= 1023 }
+; CHECK-NEXT: Reduction dependences:
+; CHECK-NEXT:     { Stmt_bb102[i0, i1] -> Stmt_bb102[o0, o1] : i0 >= 0 and 0 <= i1 <= 1023 and i0 < o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb102[i0, o1] : 0 <= i0 <= 1023 and i1 >= 0 and i1 < o1 <= 1023; Stmt_bb186[i0, i1] -> Stmt_bb186[o0, o1] : i0 >= 0 and 0 <= i1 <= 1023 and i0 < o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb186[i0, i1] -> Stmt_bb186[i0, o1] : 0 <= i0 <= 1023 and i1 >= 0 and i1 < o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb90[o0, o1] : i0 >= 0 and 0 <= i1 <= 1023 and i0 < o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb90[i0, o1] : 0 <= i0 <= 1023 and i1 >= 0 and i1 < o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb66[o0, o1] : i0 >= 0 and 0 <= i1 <= 1023 and i0 < o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb66[i0, o1] : 0 <= i0 <= 1023 and i1 >= 0 and i1 < o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb31[o0, o1] : i0 >= 0 and 0 <= i1 <= 1023 and i0 < o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb31[i0, o1] : 0 <= i0 <= 1023 and i1 >= 0 and i1 < o1 <= 1023; Stmt_bb138[i0, i1] -> Stmt_bb138[o0, o1] : i0 >= 0 and 0 <= i1 <= 1023 and i0 < o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb138[i0, i1] -> Stmt_bb138[i0, o1] : 0 <= i0 <= 1023 and i1 >= 0 and i1 < o1 <= 1023; Stmt_bb126[i0, i1] -> Stmt_bb126[o0, o1] : i0 >= 0 and 0 <= i1 <= 1023 and i0 < o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb126[i0, i1] -> Stmt_bb126[i0, o1] : 0 <= i0 <= 1023 and i1 >= 0 and i1 < o1 <= 1023; Stmt_bb150[i0, i1] -> Stmt_bb150[o0, o1] : i0 >= 0 and 0 <= i1 <= 1023 and i0 < o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb150[i0, i1] -> Stmt_bb150[i0, o1] : 0 <= i0 <= 1023 and i1 >= 0 and i1 < o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb42[o0, o1] : i0 >= 0 and 0 <= i1 <= 1023 and i0 < o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb42[i0, o1] : 0 <= i0 <= 1023 and i1 >= 0 and i1 < o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb78[o0, o1] : i0 >= 0 and 0 <= i1 <= 1023 and i0 < o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb78[i0, o1] : 0 <= i0 <= 1023 and i1 >= 0 and i1 < o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb114[o0, o1] : i0 >= 0 and 0 <= i1 <= 1023 and i0 < o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb114[i0, o1] : 0 <= i0 <= 1023 and i1 >= 0 and i1 < o1 <= 1023; Stmt_bb174[i0, i1] -> Stmt_bb174[o0, o1] : i0 >= 0 and 0 <= i1 <= 1023 and i0 < o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb174[i0, i1] -> Stmt_bb174[i0, o1] : 0 <= i0 <= 1023 and i1 >= 0 and i1 < o1 <= 1023; Stmt_bb162[i0, i1] -> Stmt_bb162[o0, o1] : i0 >= 0 and 0 <= i1 <= 1023 and i0 < o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb162[i0, i1] -> Stmt_bb162[i0, o1] : 0 <= i0 <= 1023 and i1 >= 0 and i1 < o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb54[o0, o1] : i0 >= 0 and 0 <= i1 <= 1023 and i0 < o0 <= 1023 and 0 <= o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb54[i0, o1] : 0 <= i0 <= 1023 and i1 >= 0 and i1 < o1 <= 1023 }
+; 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 <= 1023 and 0 <= o0 < i0) or (i0 >= 0 and i0 < o0 <= 1023)); Stmt_bb102[i0, i1] -> Stmt_bb102[i0, o1] : 0 <= i0 <= 1023 and ((i1 <= 1023 and 0 <= o1 < i1) or (i1 >= 0 and i1 < o1 <= 1023)); Stmt_bb186[i0, i1] -> Stmt_bb186[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 <= 1023 and 0 <= o0 < i0) or (i0 >= 0 and i0 < o0 <= 1023)); Stmt_bb186[i0, i1] -> Stmt_bb186[i0, o1] : 0 <= i0 <= 1023 and ((i1 <= 1023 and 0 <= o1 < i1) or (i1 >= 0 and i1 < o1 <= 1023)); Stmt_bb90[i0, i1] -> Stmt_bb90[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 <= 1023 and 0 <= o0 < i0) or (i0 >= 0 and i0 < o0 <= 1023)); Stmt_bb90[i0, i1] -> Stmt_bb90[i0, o1] : 0 <= i0 <= 1023 and ((i1 <= 1023 and 0 <= o1 < i1) or (i1 >= 0 and i1 < o1 <= 1023)); Stmt_bb66[i0, i1] -> Stmt_bb66[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 <= 1023 and 0 <= o0 < i0) or (i0 >= 0 and i0 < o0 <= 1023)); Stmt_bb66[i0, i1] -> Stmt_bb66[i0, o1] : 0 <= i0 <= 1023 and ((i1 <= 1023 and 0 <= o1 < i1) or (i1 >= 0 and i1 < o1 <= 1023)); Stmt_bb31[i0, i1] -> Stmt_bb31[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 <= 1023 and 0 <= o0 < i0) or (i0 >= 0 and i0 < o0 <= 1023)); Stmt_bb31[i0, i1] -> Stmt_bb31[i0, o1] : 0 <= i0 <= 1023 and ((i1 <= 1023 and 0 <= o1 < i1) or (i1 >= 0 and i1 < o1 <= 1023)); Stmt_bb138[i0, i1] -> Stmt_bb138[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 <= 1023 and 0 <= o0 < i0) or (i0 >= 0 and i0 < o0 <= 1023)); Stmt_bb138[i0, i1] -> Stmt_bb138[i0, o1] : 0 <= i0 <= 1023 and ((i1 <= 1023 and 0 <= o1 < i1) or (i1 >= 0 and i1 < o1 <= 1023)); Stmt_bb126[i0, i1] -> Stmt_bb126[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 <= 1023 and 0 <= o0 < i0) or (i0 >= 0 and i0 < o0 <= 1023)); Stmt_bb126[i0, i1] -> Stmt_bb126[i0, o1] : 0 <= i0 <= 1023 and ((i1 <= 1023 and 0 <= o1 < i1) or (i1 >= 0 and i1 < o1 <= 1023)); Stmt_bb150[i0, i1] -> Stmt_bb150[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 <= 1023 and 0 <= o0 < i0) or (i0 >= 0 and i0 < o0 <= 1023)); Stmt_bb150[i0, i1] -> Stmt_bb150[i0, o1] : 0 <= i0 <= 1023 and ((i1 <= 1023 and 0 <= o1 < i1) or (i1 >= 0 and i1 < o1 <= 1023)); Stmt_bb42[i0, i1] -> Stmt_bb42[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 <= 1023 and 0 <= o0 < i0) or (i0 >= 0 and i0 < o0 <= 1023)); Stmt_bb42[i0, i1] -> Stmt_bb42[i0, o1] : 0 <= i0 <= 1023 and ((i1 <= 1023 and 0 <= o1 < i1) or (i1 >= 0 and i1 < o1 <= 1023)); Stmt_bb78[i0, i1] -> Stmt_bb78[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 <= 1023 and 0 <= o0 < i0) or (i0 >= 0 and i0 < o0 <= 1023)); Stmt_bb78[i0, i1] -> Stmt_bb78[i0, o1] : 0 <= i0 <= 1023 and ((i1 <= 1023 and 0 <= o1 < i1) or (i1 >= 0 and i1 < o1 <= 1023)); Stmt_bb114[i0, i1] -> Stmt_bb114[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 <= 1023 and 0 <= o0 < i0) or (i0 >= 0 and i0 < o0 <= 1023)); Stmt_bb114[i0, i1] -> Stmt_bb114[i0, o1] : 0 <= i0 <= 1023 and ((i1 <= 1023 and 0 <= o1 < i1) or (i1 >= 0 and i1 < o1 <= 1023)); Stmt_bb174[i0, i1] -> Stmt_bb174[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 <= 1023 and 0 <= o0 < i0) or (i0 >= 0 and i0 < o0 <= 1023)); Stmt_bb174[i0, i1] -> Stmt_bb174[i0, o1] : 0 <= i0 <= 1023 and ((i1 <= 1023 and 0 <= o1 < i1) or (i1 >= 0 and i1 < o1 <= 1023)); Stmt_bb162[i0, i1] -> Stmt_bb162[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 <= 1023 and 0 <= o0 < i0) or (i0 >= 0 and i0 < o0 <= 1023)); Stmt_bb162[i0, i1] -> Stmt_bb162[i0, o1] : 0 <= i0 <= 1023 and ((i1 <= 1023 and 0 <= o1 < i1) or (i1 >= 0 and i1 < o1 <= 1023)); Stmt_bb54[i0, i1] -> Stmt_bb54[o0, o1] : 0 <= i1 <= 1023 and 0 <= o1 <= 1023 and ((i0 <= 1023 and 0 <= o0 < i0) or (i0 >= 0 and i0 < o0 <= 1023)); Stmt_bb54[i0, i1] -> Stmt_bb54[i0, o1] : 0 <= i0 <= 1023 and ((i1 <= 1023 and 0 <= o1 < i1) or (i1 >= 0 and i1 < o1 <= 1023)) }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @manyreductions(i64* %A) {
 bb:
   br label %bb28
 
 bb28:                                             ; preds = %bb36, %bb

test/DependenceInfo/reduction_simple_iv.ll

 ; RUN: opt %loadPolly -polly-dependences -analyze < %s | FileCheck %s
 ;
 ; CHECK:      RAW dependences:
 ; CHECK-NEXT:     {  }
 ; CHECK-NEXT: WAR dependences:
 ; CHECK-NEXT:     {  }
 ; CHECK-NEXT: WAW dependences:
 ; CHECK-NEXT:     {  }
 ; CHECK-NEXT: Reduction dependences:
-; CHECK-NEXT:     { Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0] : 0 <= i0 <= 99 }
+; CHECK-NEXT:     { Stmt_for_cond[i0] -> Stmt_for_cond[o0] : i0 >= 0 and i0 < o0 <= 100 }
 ;
 ; void f(int* sum) {
 ;   for (int i = 0; i <= 100; i++)
 ;     sum += i * 3;
 ; }
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
 
 define void @f(i32* %sum) {

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-NEXT: MustWrite: {  }
+; CHECK-NEXT: MayWrite: { [Stmt_for_cond[i0] -> MemRef_sum[0{{\]\]}} -> MemRef_sum[0] : 0 <= i0 <= 100 }
 ;
 ; 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:         { [Stmt_for_cond[i0] -> MemRef_sum[0{{\]\]}} -> [Stmt_for_cond[o0] -> MemRef_sum[0{{\]\]}} : i0 >= 0 and i0 < o0 <= 100 }
 ; CHECK-NEXT:     WAR dependences:
 ; 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:         { [Stmt_for_cond[i0] -> MemRef_sum[0{{\]\]}} -> [Stmt_for_cond[o0] -> MemRef_sum[0{{\]\]}} : i0 >= 0 and i0 < o0 <= 100 }
 ; CHECK-NEXT:     Reduction dependences:
 ; CHECK-NEXT:         n/a
 ;
 ; CHECK:      Final Wrapped Dependences:
 ; CHECK-NEXT:     RAW dependences:
 ; CHECK-NEXT:         {  }
 ; CHECK-NEXT:     WAR dependences:
 ; CHECK-NEXT:         {  }
 ; CHECK-NEXT:     WAW dependences:
 ; CHECK-NEXT:         {  }
 ; CHECK-NEXT:     Reduction dependences:
-; CHECK-NEXT:         { [Stmt_for_cond[i0] -> MemRef_sum[0{{\]\]}} -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0{{\]\]}} : 0 <= i0 <= 99 }
+; CHECK-NEXT:         { [Stmt_for_cond[i0] -> MemRef_sum[0{{\]\]}} -> [Stmt_for_cond[o0] -> MemRef_sum[0{{\]\]}} : i0 >= 0 and i0 < o0 <= 100 }
 ;
 ; CHECK:      Zipped Dependences:
 ; CHECK-NEXT:     RAW dependences:
 ; CHECK-NEXT:         {  }
 ; CHECK-NEXT:     WAR dependences:
 ; CHECK-NEXT:         {  }
 ; CHECK-NEXT:     WAW dependences:
 ; CHECK-NEXT:         {  }
 ; CHECK-NEXT:     Reduction dependences:
-; CHECK-NEXT:         { [Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0{{\]\]}} -> [MemRef_sum[0] -> MemRef_sum[0{{\]\]}} : 0 <= i0 <= 99 }
+; CHECK-NEXT:         { [Stmt_for_cond[i0] -> Stmt_for_cond[i1{{\]\]}} -> [MemRef_sum[0] -> MemRef_sum[0{{\]\]}} : i0 >= 0 and i0 < i1 <= 100 }
 ;
 ; CHECK:      Unwrapped Dependences:
 ; CHECK-NEXT:     RAW dependences:
 ; CHECK-NEXT:         {  }
 ; CHECK-NEXT:     WAR dependences:
 ; CHECK-NEXT:         {  }
 ; CHECK-NEXT:     WAW dependences:
 ; CHECK-NEXT:         {  }
 ; CHECK-NEXT:     Reduction dependences:
-; CHECK-NEXT:         { Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0] : 0 <= i0 <= 99 }
+; CHECK-NEXT:         { Stmt_for_cond[i0] -> Stmt_for_cond[o0] : i0 >= 0 and i0 < o0 <= 100 }
 ;
 ; CHECK:          RAW dependences:
 ; CHECK-NEXT:         {  }
 ; CHECK-NEXT:     WAR dependences:
 ; CHECK-NEXT:         {  }
 ; CHECK-NEXT:     WAW dependences:
 ; CHECK-NEXT:         {  }
 ; CHECK-NEXT:     Reduction dependences:
-; CHECK-NEXT:         { Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0] : 0 <= i0 <= 99 }
+; CHECK-NEXT:         { Stmt_for_cond[i0] -> Stmt_for_cond[o0] : i0 >= 0 and i0 < o0 <= 100 }
 ;
 ; CHECK:          RAW dependences:
 ; CHECK-NEXT:         {  }
 ; CHECK-NEXT:     WAR dependences:
 ; CHECK-NEXT:         {  }
 ; CHECK-NEXT:     WAW dependences:
 ; CHECK-NEXT:         {  }
 ; CHECK-NEXT:     Reduction dependences:
-; CHECK-NEXT:         { Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0] : 0 <= i0 <= 99 }
+; CHECK-NEXT:         { Stmt_for_cond[i0] -> Stmt_for_cond[o0] : i0 >= 0 and i0 < o0 <= 100 }
 ;
 ; void f(int* sum) {
 ;   for (int i = 0; i <= 100; i++)
 ;     sum += i * 3;
 ; }
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
 
 define void @f(i32* %sum) {

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:     { Stmt_S2[i0] -> Stmt_S1[o0, o1] : i0 >= 0 and i0 < o0 <= 99 and 0 <= o1 <= 99; Stmt_S2[i0] -> Stmt_S0[o0] : i0 >= 0 and i0 < o0 <= 99; Stmt_S1[i0, i1] -> Stmt_S0[o0] : i0 >= 0 and 0 <= i1 <= 99 and i0 < o0 <= 99; Stmt_S0[i0] -> Stmt_S2[o0] : i0 >= 0 and i0 <= o0 <= 99; Stmt_S1[i0, i1] -> Stmt_S2[o0] : i0 >= 0 and 0 <= i1 <= 99 and i0 <= o0 <= 99; Stmt_S0[i0] -> Stmt_S1[o0, o1] : i0 >= 0 and i0 <= o0 <= 99 and 0 <= o1 <= 99 }
 ; CHECK-NEXT: WAR 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:     { Stmt_S2[i0] -> Stmt_S0[1 + i0] : 0 <= i0 <= 98; Stmt_S0[i0] -> Stmt_S1[i0, 0] : 0 <= i0 <= 99; Stmt_S1[i0, 99] -> Stmt_S2[i0] : 0 <= i0 <= 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:     { Stmt_S2[i0] -> Stmt_S1[o0, o1] : i0 >= 0 and i0 < o0 <= 99 and 0 <= o1 <= 99; Stmt_S2[i0] -> Stmt_S0[o0] : i0 >= 0 and i0 < o0 <= 99; Stmt_S1[i0, i1] -> Stmt_S0[o0] : i0 >= 0 and 0 <= i1 <= 99 and i0 < o0 <= 99; Stmt_S0[i0] -> Stmt_S2[o0] : i0 >= 0 and i0 <= o0 <= 99; Stmt_S1[i0, i1] -> Stmt_S2[o0] : i0 >= 0 and 0 <= i1 <= 99 and i0 <= o0 <= 99; Stmt_S0[i0] -> Stmt_S1[o0, o1] : i0 >= 0 and i0 <= o0 <= 99 and 0 <= o1 <= 99 }
 ; CHECK-NEXT: Reduction dependences:
-; CHECK-NEXT:     { Stmt_S1[i0, i1] -> Stmt_S1[i0, 1 + i1] : 0 <= i0 <= 99 and 0 <= i1 <= 98 }
+; CHECK-NEXT:     { Stmt_S0[i0] -> Stmt_S0[o0] : i0 >= 0 and i0 < o0 <= 99; Stmt_S2[i0] -> Stmt_S2[o0] : i0 >= 0 and i0 < o0 <= 99; Stmt_S1[i0, i1] -> Stmt_S1[o0, o1] : i0 >= 0 and 0 <= i1 <= 99 and i0 < o0 <= 99 and 0 <= o1 <= 99; Stmt_S1[i0, i1] -> Stmt_S1[i0, o1] : 0 <= i0 <= 99 and i1 >= 0 and i1 < o1 <= 99 }
 ;
 ;    void f(int *sum) {
 ;      for (int i = 0; i < 100; i++) {
 ; S0:    *sum *= 42;
 ;        for (int j = 0; j < 100; j++)
 ; S1:      *sum += i * j;
 ; S2:    *sum *= 7;
 ;      }

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:     [N] -> { Stmt_S0[] -> Stmt_S1[o0] : N >= 11 and 0 <= o0 <= 1023; Stmt_S0[] -> Stmt_S2[] : N >= 11; Stmt_S1[i0] -> Stmt_S2[] : N >= 11 and 0 <= i0 <= 1023 }
 ; CHECK-NEXT: WAR dependences:
-; CHECK-NEXT:     [N] -> { Stmt_S1[i0] -> Stmt_S2[] : N >= 11 and 0 <= i0 <= 1023 }
+; CHECK-NEXT:     [N] -> { Stmt_S1[1023] -> Stmt_S2[] : N >= 11 }
 ; 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:     [N] -> { Stmt_S0[] -> Stmt_S1[o0] : N >= 11 and 0 <= o0 <= 1023; Stmt_S0[] -> Stmt_S2[] : N >= 11; 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 }
+; CHECK-NEXT:     [N] -> { Stmt_S1[i0] -> Stmt_S1[o0] : N >= 11 and i0 >= 0 and i0 < o0 <= 1023 }
 ;
 ;    void f(int *sum, int N) {
 ;      if (N >= 10) {
 ; S0:    *sum = 0;
 ;        for (int i = 0; i < 1024; i++)
 ; S1:      *sum += i;
 ; S2:    *sum = *sum * 3;
 ;      }

test/DependenceInfo/reduction_two_reductions_different_rloops.ll

 ; RUN: opt %loadPolly -basicaa -polly-dependences -analyze < %s | FileCheck %s
 ;
 ; CHECK:      RAW dependences:
 ; CHECK-NEXT:     {  }
 ; CHECK-NEXT: WAR dependences:
 ; CHECK-NEXT:     {  }
 ; CHECK-NEXT: WAW dependences:
 ; CHECK-NEXT:     {  }
 ; CHECK-NEXT: Reduction dependences:
-; CHECK-NEXT:     { Stmt_for_body3[i0, i1] -> Stmt_for_body3[o0, 1 + i0 + i1 - o0] : i0 >= 0 and i1 >= 0 and o0 >= -1022 + i0 + i1 and i0 <= o0 <= 1023 and o0 <= 1 + i0 }
+; CHECK-NEXT:     { Stmt_for_body3[i0, i1] -> Stmt_for_body3[i0, o1] : 0 <= i0 <= 1023 and i1 >= 0 and i1 < o1 <= 1023; Stmt_for_body3[i0, i1] -> Stmt_for_body3[o0, i1] : i0 >= 0 and 0 <= i1 <= 1023 and i0 < o0 <= 1023 }
 ;
 ; void f(int *restrict A, int *restrict B, int *restrict Values) {
 ;   for (int i = 0; i < 1024; i++) {
 ;     for (int j = 0; j < 1024; j++) {
 ;       A[i] += Values[i + j - 1];
 ;       B[j] += Values[i + j + 42];
 ;     }
 ;   }

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

 ;
 ; DEPENDENCES:  RAW dependences:
 ; DEPENDENCES-NEXT:    {  }
 ; DEPENDENCES-NEXT:  WAR dependences:
 ; DEPENDENCES-NEXT:    {  }
 ; DEPENDENCES-NEXT:  WAW dependences:
 ; DEPENDENCES-NEXT:    {  }
 ; DEPENDENCES-NEXT:  Reduction dependences:
-; DEPENDENCES-NEXT:    { Stmt_for_body6[i0, i1, i2] -> Stmt_for_body6[i0, i1, 1 + i2] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and 0 <= i2 <= 1022 }
+; DEPENDENCES-NEXT:    { Stmt_for_body6[i0, i1, i2] -> Stmt_for_body6[i0, i1, o2] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and i2 >= 0 and i2 < o2 <= 1023 }
 ; DEPENDENCES-NEXT:  Transitive closure of reduction dependences:
-; DEPENDENCES-NEXT:    { Stmt_for_body6[i0, i1, i2] -> Stmt_for_body6[i0, i1, o2] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and ((i2 >= 0 and i2 < o2 <= 1023) or (i2 <= 1023 and 0 <= o2 < i2)) }
+; DEPENDENCES0NEXT:    { Stmt_for_body6[i0, i1, i2] -> Stmt_for_body6[i0, i1, o2] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 and ((i2 <= 1023 and 0 <= o2 < i2) or (i2 >= 0 and i2 < o2 <= 1023)) }
+
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-unknown"
 
 define internal void @kernel_gemm(i32 %ni, i32 %nj, i32 %nk, i8 signext %alpha, i8 signext %beta, [1024 x i8]* %C, [1024 x i8]* %A, [1024 x i8]* %B) {
 entry:
   br label %entry.split