Index: lib/Analysis/DependenceInfo.cpp =================================================================== --- lib/Analysis/DependenceInfo.cpp +++ lib/Analysis/DependenceInfo.cpp @@ -289,7 +289,8 @@ isl_union_access_info *AI; AI = isl_union_access_info_from_sink(isl_union_map_copy(Snk)); - AI = isl_union_access_info_set_may_source(AI, isl_union_map_copy(MaySrc)); + if (MaySrc) + AI = isl_union_access_info_set_may_source(AI, isl_union_map_copy(MaySrc)); if (Src) AI = isl_union_access_info_set_must_source(AI, isl_union_map_copy(Src)); AI = isl_union_access_info_set_schedule(AI, isl_schedule_copy(Schedule)); @@ -358,55 +359,84 @@ 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 need W <- W with no intermediate Reads in between. Intermediate + // reads imply side-effects. If there are side-effects, we should not + // re-order our statements. Hence, they should *not* be counted as + // reductions. + // + // Example: + // void f(int *A, int *B) { + // for(int i = 0; i <= 100; i++) { + // *-WAW (S0[i] -> S0[i + 1])--* + // | | + // v | + // S0: *A += i; -------------------* + // | + // if (i >= 98) { WAR (S0 -> S1) + // S1: *B = *A; <--------------* + // } + // } + // } + // + // Since the writes in S0 happen *between* reads at S1, the entire loop + // is not a legal reduction. It is only a reduction in (0 <= i <= 98). + // + // To detect these sorts of patterns, we need to generate strict WAW that + // do not have reads between them. + 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(MustWrite, MustWrite, Read, Schedule); - - WAW = isl_union_flow_get_must_dependence(Flow); - WAR = isl_union_flow_get_may_dependence(Flow); - - // This subtraction is needed to obtain the same results as were given by - // isl_union_map_compute_flow. For large sets this may add some - // compile-time cost. As there does not seem to be a need to distinguish - // between WAW and WAR, refactoring Polly to only track general non-flow - // dependences may improve performance. - WAR = isl_union_map_subtract(WAR, isl_union_map_copy(WAW)); + Flow = buildFlow(Write, MustWrite, MayWrite, Schedule); + WAW = isl_union_flow_get_may_dependence(Flow); + isl_union_flow_free(Flow); + // We need exact WAR dependences. That is, if there are + // dependences of the form: + // must-W2 (sink) <- must-W1 (sink) <- R (source) + // We wish to generate ONLY + // { R -> W1 }, NOT + // { R -> W2, R -> W1 } + // To achieve this, we use the fact that *must* dependences are not + // allowed to flow through the may-source. + // Since we set the may-source to Write, we are guaranteed that only + // exact WARs are captured. + Flow = buildFlow(Write, Read, Write, Schedule); + WAR = isl_union_flow_get_must_dependence(Flow); isl_union_flow_free(Flow); + + isl_union_map_free(Write); isl_schedule_free(Schedule); } else { isl_union_flow *Flow; - isl_union_map *Write = isl_union_map_union(isl_union_map_copy(MustWrite), - isl_union_map_copy(MayWrite)); - Flow = buildFlow(Read, nullptr, Write, Schedule); - RAW = isl_union_flow_get_may_dependence(Flow); isl_union_flow_free(Flow); Flow = buildFlow(Write, nullptr, Read, Schedule); - WAR = isl_union_flow_get_may_dependence(Flow); isl_union_flow_free(Flow); Flow = buildFlow(Write, nullptr, Write, Schedule); - WAW = isl_union_flow_get_may_dependence(Flow); isl_union_flow_free(Flow); - isl_schedule_free(Schedule); + isl_union_map_free(Write); + isl_schedule_free(Schedule); } isl_union_map_free(MustWrite); @@ -424,7 +454,8 @@ isl_union_map_free(RAW); isl_union_map_free(WAW); isl_union_map_free(WAR); - RAW = WAW = WAR = nullptr; + isl_union_map_free(StrictWAW); + RAW = WAW = WAR = StrictWAW = nullptr; isl_ctx_reset_error(IslCtx.get()); } @@ -435,6 +466,7 @@ 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; } @@ -457,9 +489,9 @@ // 2) Intersect them with the actual RAW & WAW dependences to the get the // actual reduction dependences. This will ensure the load/store memory // addresses were __identical__ in the two iterations of the statement. - // 3) Relax the original RAW and WAW dependences by subtracting the actual - // reduction dependences. Binary reductions (sum += A[i]) cause both, and - // the same, RAW and WAW dependences. + // 3) Relax the original RAW, WAW and WAR dependences by subtracting the + // actual reduction dependences. Binary reductions (sum += A[i]) cause + // the same, RAW, WAW and WAR dependences. // 4) Add the privatization dependences which are widened versions of // already present dependences. They model the effect of manual // privatization at the outermost possible place (namely after the last @@ -480,13 +512,14 @@ // Step 2) RED = isl_union_map_intersect(RED, isl_union_map_copy(RAW)); - RED = isl_union_map_intersect(RED, isl_union_map_copy(WAW)); + RED = isl_union_map_intersect(RED, StrictWAW); if (!isl_union_map_is_empty(RED)) { // Step 3) RAW = isl_union_map_subtract(RAW, isl_union_map_copy(RED)); WAW = isl_union_map_subtract(WAW, isl_union_map_copy(RED)); + WAR = isl_union_map_subtract(WAR, isl_union_map_copy(RED)); // Step 4) addPrivatizationDependences(); Index: lib/Transform/ScheduleOptimizer.cpp =================================================================== --- lib/Transform/ScheduleOptimizer.cpp +++ lib/Transform/ScheduleOptimizer.cpp @@ -781,12 +781,6 @@ /// and false, otherwise. static bool containsOnlyMatMulDep(__isl_keep isl_map *Schedule, const Dependences *D, int &Pos) { - auto *WAR = D->getDependences(Dependences::TYPE_WAR); - if (!isl_union_map_is_empty(WAR)) { - isl_union_map_free(WAR); - return false; - } - isl_union_map_free(WAR); auto *Dep = D->getDependences(Dependences::TYPE_RAW); auto *Red = D->getDependences(Dependences::TYPE_RED); if (Red) Index: test/DependenceInfo/different_schedule_dimensions.ll =================================================================== --- test/DependenceInfo/different_schedule_dimensions.ll +++ test/DependenceInfo/different_schedule_dimensions.ll @@ -6,7 +6,7 @@ ; CHECK: RAW dependences: ; CHECK: { Stmt_bb9[0] -> Stmt_bb10[0] } ; CHECK: WAR dependences: -; CHECK: { } +; CHECK: { Stmt_bb3[0] -> Stmt_bb10[0] } ; CHECK: WAW dependences: ; CHECK: { Stmt_bb3[0] -> Stmt_bb10[0] } ; CHECK: Reduction dependences: @@ -15,7 +15,7 @@ ; FUNC: RAW dependences: ; FUNC-NEXT: { Stmt_bb9[0] -> Stmt_bb10[0]; [Stmt_bb9[0] -> Stmt_bb9_Write0_MemRef_tmp11[]] -> [Stmt_bb10[0] -> Stmt_bb10_Read0_MemRef_tmp11[]] } ; FUNC-NEXT: WAR dependences: -; FUNC-NEXT: { } +; FUNC-NEXT: { Stmt_bb3[0] -> Stmt_bb10[0]; [Stmt_bb3[0] -> Stmt_bb3_Read0_MemRef_arg1[]] -> [Stmt_bb10[0] -> Stmt_bb10_Write1_MemRef_arg1[]] } ; FUNC-NEXT: WAW dependences: ; FUNC-NEXT: { Stmt_bb3[0] -> Stmt_bb10[0]; [Stmt_bb3[0] -> Stmt_bb3_Write1_MemRef_arg1[]] -> [Stmt_bb10[0] -> Stmt_bb10_Write1_MemRef_arg1[]] } ; FUNC-NEXT: Reduction dependences: Index: test/DependenceInfo/do_pluto_matmult.ll =================================================================== --- test/DependenceInfo/do_pluto_matmult.ll +++ test/DependenceInfo/do_pluto_matmult.ll @@ -69,7 +69,7 @@ ; VALUE: RAW dependences: ; VALUE-NEXT: { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34 } ; VALUE-NEXT: WAR dependences: -; VALUE-NEXT: { } +; VALUE-NEXT: { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34 } ; VALUE-NEXT: WAW dependences: ; VALUE-NEXT: { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34 } @@ -83,7 +83,7 @@ ; FUNC-VALUE: RAW dependences: ; FUNC-VALUE-NEXT: { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Write3_MemRef_C[]] -> [Stmt_do_body2[i0, i1, 1 + i2] -> Stmt_do_body2_Read0_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34 } ; FUNC-VALUE-NEXT: WAR dependences: -; FUNC-VALUE-NEXT: { } +; FUNC-VALUE-NEXT: { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Read0_MemRef_C[]] -> [Stmt_do_body2[i0, i1, 1 + i2] -> Stmt_do_body2_Write3_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34 } ; FUNC-VALUE-NEXT: WAW dependences: ; FUNC-VALUE-NEXT: { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Write3_MemRef_C[]] -> [Stmt_do_body2[i0, i1, 1 + i2] -> Stmt_do_body2_Write3_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34 } Index: test/DependenceInfo/generate_may_write_dependence_info.ll =================================================================== --- test/DependenceInfo/generate_may_write_dependence_info.ll +++ test/DependenceInfo/generate_may_write_dependence_info.ll @@ -58,10 +58,10 @@ ; VALUE: RAW dependences: ; VALUE-NEXT: { Stmt_A_must_write_20[i0] -> Stmt_B_write_from_A[i0] : 0 <= i0 <= 2999; Stmt_compute_i_square__TO__B_write_from_A[i0] -> Stmt_B_write_from_A[i0] : 0 <= i0 <= 2999 } ; VALUE-NEXT: WAR dependences: -; VALUE-NEXT: { Stmt_A_must_write_20[i0] -> Stmt_A_must_write_42[i0] : 0 <= i0 <= 2999; Stmt_B_write_from_A[i0] -> Stmt_A_must_write_42[i0] : 0 <= i0 <= 2999 } +; VALUE-NEXT: { Stmt_B_write_from_A[i0] -> Stmt_A_must_write_42[i0] : 0 <= i0 <= 2999 } ; VALUE-NEXT: WAW dependences: -; VALUE-NEXT: { } +; VALUE-NEXT: { Stmt_compute_i_square__TO__B_write_from_A[i0] -> Stmt_A_must_write_42[i0] : 0 <= i0 <= 2999; Stmt_A_must_write_20[i0] -> Stmt_A_must_write_42[i0] : 0 <= i0 <= 2999; Stmt_A_must_write_20[i0] -> Stmt_compute_i_square__TO__B_write_from_A[i0] : 0 <= i0 <= 2999 } ; VALUE-NEXT: Reduction dependences: ; VALUE-NEXT: { } ; VALUE-NEXT: Transitive closure of reduction dependences: -; VALUE-NEXT: { } \ No newline at end of file +; VALUE-NEXT: { } Index: test/DependenceInfo/reduction_dependences_equal_non_reduction_dependences.ll =================================================================== --- test/DependenceInfo/reduction_dependences_equal_non_reduction_dependences.ll +++ test/DependenceInfo/reduction_dependences_equal_non_reduction_dependences.ll @@ -6,7 +6,7 @@ ; CHECK: RAW dependences: ; CHECK-NEXT: { Stmt_for_body[i0] -> Stmt_for_body[1 + i0] : 0 <= i0 <= 1022 } ; CHECK-NEXT: WAR dependences: -; CHECK-NEXT: { } +; CHECK-NEXT: { Stmt_for_body[i0] -> Stmt_for_body[1 + i0] : 0 <= i0 <= 1022 } ; CHECK-NEXT: WAW dependences: ; CHECK-NEXT: { Stmt_for_body[i0] -> Stmt_for_body[1 + i0] : 0 <= i0 <= 1022 } ; CHECK-NEXT: Reduction dependences: Index: test/DependenceInfo/reduction_multiple_reductions_2.ll =================================================================== --- test/DependenceInfo/reduction_multiple_reductions_2.ll +++ test/DependenceInfo/reduction_multiple_reductions_2.ll @@ -12,7 +12,7 @@ ; CHECK: RAW dependences: ; CHECK-NEXT: { Stmt_S0[i0] -> Stmt_S1[i0, o1] : 0 <= i0 <= 1023 and 0 <= o1 <= 1023; Stmt_S2[i0, i1] -> Stmt_S3[i0] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023; Stmt_S3[i0] -> Stmt_S0[1 + i0] : 0 <= i0 <= 1022; Stmt_S1[i0, 1023] -> Stmt_S2[i0, o1] : 0 <= i0 <= 1023 and 0 <= o1 <= 1023; Stmt_S1[i0, i1] -> Stmt_S2[i0, 0] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022 } ; CHECK-NEXT: WAR dependences: -; CHECK-NEXT: { } +; CHECK-NEXT: { Stmt_S0[i0] -> Stmt_S1[i0, o1] : 0 <= i0 <= 1023 and 0 <= o1 <= 1023; Stmt_S2[i0, i1] -> Stmt_S3[i0] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023; Stmt_S3[i0] -> Stmt_S0[1 + i0] : 0 <= i0 <= 1022; Stmt_S1[i0, 1023] -> Stmt_S2[i0, o1] : 0 <= i0 <= 1023 and 0 <= o1 <= 1023; Stmt_S1[i0, i1] -> Stmt_S2[i0, 0] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022 } ; CHECK-NEXT: WAW dependences: ; CHECK-NEXT: { Stmt_S0[i0] -> Stmt_S1[i0, o1] : 0 <= i0 <= 1023 and 0 <= o1 <= 1023; Stmt_S2[i0, i1] -> Stmt_S3[i0] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023; Stmt_S3[i0] -> Stmt_S0[1 + i0] : 0 <= i0 <= 1022; Stmt_S1[i0, 1023] -> Stmt_S2[i0, o1] : 0 <= i0 <= 1023 and 0 <= o1 <= 1023; Stmt_S1[i0, i1] -> Stmt_S2[i0, 0] : 0 <= i0 <= 1023 and 0 <= i1 <= 1022 } ; CHECK-NEXT: Reduction dependences: Index: test/DependenceInfo/reduction_privatization_deps.ll =================================================================== --- test/DependenceInfo/reduction_privatization_deps.ll +++ test/DependenceInfo/reduction_privatization_deps.ll @@ -3,9 +3,9 @@ ; CHECK: RAW dependences: ; CHECK-NEXT: { Stmt_S0[i0] -> Stmt_S1[o0, i0 - o0] : i0 <= 1023 and 0 <= o0 <= i0; Stmt_S1[i0, i1] -> Stmt_S2[-1 + i0 + i1] : 0 <= i0 <= 1023 and i1 >= 0 and -i0 < i1 <= 1024 - i0 and i1 <= 1023 } ; CHECK-NEXT: WAR dependences: -; CHECK-NEXT: { Stmt_S2[i0] -> Stmt_S2[1 + i0] : 0 <= i0 <= 1022; Stmt_S1[i0, i1] -> Stmt_S2[i0 + i1] : i0 >= 0 and i1 >= 0 and -i0 < i1 <= 1023 - i0 } +; CHECK-NEXT: { Stmt_S2[i0] -> Stmt_S2[1 + i0] : 0 <= i0 <= 1022; Stmt_S1[0, 0] -> Stmt_S2[0] } ; CHECK-NEXT: WAW dependences: -; CHECK-NEXT: { Stmt_S0[i0] -> Stmt_S1[o0, i0 - o0] : i0 <= 1023 and 0 <= o0 <= i0; Stmt_S1[0, 0] -> Stmt_S2[0] } +; CHECK-NEXT: { Stmt_S0[i0] -> Stmt_S1[o0, i0 - o0] : i0 <= 1023 and 0 <= o0 <= i0; Stmt_S1[i0, i1] -> Stmt_S2[i0 + i1] : i0 >= 0 and 0 <= i1 <= 1023 - i0 } ; CHECK-NEXT: Reduction dependences: ; CHECK-NEXT: { Stmt_S1[i0, i1] -> Stmt_S1[1 + i0, -1 + i1] : 0 <= i0 <= 1022 and 0 < i1 <= 1023 } ; Index: test/DependenceInfo/reduction_privatization_deps_2.ll =================================================================== --- test/DependenceInfo/reduction_privatization_deps_2.ll +++ test/DependenceInfo/reduction_privatization_deps_2.ll @@ -6,7 +6,7 @@ ; CHECK: RAW dependences: ; CHECK-NEXT: { Stmt_S3[i0] -> Stmt_S2[1 + i0, o1] : 0 <= i0 <= 97 and 0 <= o1 <= 99; Stmt_S1[i0] -> Stmt_S3[i0] : 0 <= i0 <= 98 } ; CHECK-NEXT: WAR dependences: -; CHECK-NEXT: { } +; CHECK-NEXT: { Stmt_S3[i0] -> Stmt_S2[1 + i0, o1] : 0 <= i0 <= 97 and 0 <= o1 <= 99; Stmt_S1[i0] -> Stmt_S3[i0] : 0 <= i0 <= 98 } ; CHECK-NEXT: WAW dependences: ; CHECK-NEXT: { Stmt_S3[i0] -> Stmt_S2[1 + i0, o1] : 0 <= i0 <= 97 and 0 <= o1 <= 99; Stmt_S1[i0] -> Stmt_S3[i0] : 0 <= i0 <= 98 } ; CHECK-NEXT: Reduction dependences: Index: test/DependenceInfo/reduction_privatization_deps_3.ll =================================================================== --- test/DependenceInfo/reduction_privatization_deps_3.ll +++ test/DependenceInfo/reduction_privatization_deps_3.ll @@ -3,7 +3,7 @@ ; CHECK: RAW dependences: ; CHECK-NEXT: { Stmt_S2[i0, i1] -> Stmt_S3[o0] : i1 <= 1 - i0 and -i1 < o0 <= 1 and o0 <= 1 + i0 - i1; Stmt_S3[i0] -> Stmt_S2[o0, 1 - i0] : 0 <= i0 <= 1 and i0 < o0 <= 98; Stmt_S1[i0] -> Stmt_S3[2 + i0] : 0 <= i0 <= 96 } ; CHECK-NEXT: WAR dependences: -; CHECK-NEXT: { } +; CHECK-NEXT: { Stmt_S2[i0, i1] -> Stmt_S3[o0] : i1 <= 1 - i0 and -i1 < o0 <= 1 and o0 <= 1 + i0 - i1; Stmt_S3[i0] -> Stmt_S2[o0, 1 - i0] : 0 <= i0 <= 1 and i0 < o0 <= 98; Stmt_S1[i0] -> Stmt_S3[2 + i0] : 0 <= i0 <= 96 } ; CHECK-NEXT: WAW dependences: ; CHECK-NEXT: { Stmt_S2[i0, i1] -> Stmt_S3[o0] : i1 <= 1 - i0 and -i1 < o0 <= 1 and o0 <= 1 + i0 - i1; Stmt_S3[i0] -> Stmt_S2[o0, 1 - i0] : 0 <= i0 <= 1 and i0 < o0 <= 98; Stmt_S1[i0] -> Stmt_S3[2 + i0] : 0 <= i0 <= 96 } ; CHECK-NEXT: Reduction dependences: Index: test/DependenceInfo/reduction_privatization_deps_4.ll =================================================================== --- test/DependenceInfo/reduction_privatization_deps_4.ll +++ test/DependenceInfo/reduction_privatization_deps_4.ll @@ -3,7 +3,7 @@ ; CHECK: RAW dependences: ; CHECK-NEXT: { Stmt_S2[i0, i1] -> Stmt_S1[i1] : i0 >= 0 and i0 < i1 <= 98; Stmt_S1[i0] -> Stmt_S2[i0, i0] : 0 <= i0 <= 98; Stmt_S2[i0, i0] -> Stmt_S3[i0] : 0 <= i0 <= 98; Stmt_S3[i0] -> Stmt_S2[o0, i0] : i0 >= 0 and i0 < o0 <= 98 } ; CHECK-NEXT: WAR dependences: -; CHECK-NEXT: { } +; CHECK-NEXT: { Stmt_S2[i0, i1] -> Stmt_S1[i1] : i0 >= 0 and i0 < i1 <= 98; Stmt_S1[i0] -> Stmt_S2[i0, i0] : 0 <= i0 <= 98; Stmt_S2[i0, i0] -> Stmt_S3[i0] : 0 <= i0 <= 98; Stmt_S3[i0] -> Stmt_S2[o0, i0] : i0 >= 0 and i0 < o0 <= 98 } ; CHECK-NEXT: WAW dependences: ; CHECK-NEXT: { Stmt_S2[i0, i1] -> Stmt_S1[i1] : i0 >= 0 and i0 < i1 <= 98; Stmt_S1[i0] -> Stmt_S2[i0, i0] : 0 <= i0 <= 98; Stmt_S2[i0, i0] -> Stmt_S3[i0] : 0 <= i0 <= 98; Stmt_S3[i0] -> Stmt_S2[o0, i0] : i0 >= 0 and i0 < o0 <= 98 } ; CHECK-NEXT: Reduction dependences: Index: test/DependenceInfo/reduction_privatization_deps_5.ll =================================================================== --- test/DependenceInfo/reduction_privatization_deps_5.ll +++ test/DependenceInfo/reduction_privatization_deps_5.ll @@ -3,7 +3,7 @@ ; CHECK: RAW dependences: ; CHECK-NEXT: { Stmt_S2[i0, 0] -> Stmt_S1[1 + i0, 0] : 0 <= i0 <= 97; Stmt_S1[i0, 0] -> Stmt_S2[i0, 0] : 0 <= i0 <= 98 } ; CHECK-NEXT: WAR dependences: -; CHECK-NEXT: { } +; CHECK-NEXT: { Stmt_S2[i0, 0] -> Stmt_S1[1 + i0, 0] : 0 <= i0 <= 97; Stmt_S1[i0, 0] -> Stmt_S2[i0, 0] : 0 <= i0 <= 98 } ; CHECK-NEXT: WAW dependences: ; CHECK-NEXT: { Stmt_S2[i0, 0] -> Stmt_S1[1 + i0, 0] : 0 <= i0 <= 97; Stmt_S1[i0, 0] -> Stmt_S2[i0, 0] : 0 <= i0 <= 98 } ; CHECK-NEXT: Reduction dependences: Index: test/DependenceInfo/reduction_sequence.ll =================================================================== --- test/DependenceInfo/reduction_sequence.ll +++ test/DependenceInfo/reduction_sequence.ll @@ -61,7 +61,7 @@ ; CHECK: RAW dependences: ; CHECK-NEXT: { Stmt_bb150[1023, 1023] -> Stmt_bb162[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb150[i0, i1] -> Stmt_bb162[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb150[1023, 1023] -> Stmt_bb162[0, 0]; Stmt_bb174[1023, 1023] -> Stmt_bb186[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb174[i0, i1] -> Stmt_bb186[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb174[1023, 1023] -> Stmt_bb186[0, 0]; Stmt_bb102[1023, 1023] -> Stmt_bb114[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb114[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb102[1023, 1023] -> Stmt_bb114[0, 0]; Stmt_bb42[1023, 1023] -> Stmt_bb54[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb54[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb42[1023, 1023] -> Stmt_bb54[0, 0]; Stmt_bb54[1023, 1023] -> Stmt_bb66[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb66[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb54[1023, 1023] -> Stmt_bb66[0, 0]; Stmt_bb31[1023, 1023] -> Stmt_bb42[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb42[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb31[1023, 1023] -> Stmt_bb42[0, 0]; Stmt_bb162[1023, 1023] -> Stmt_bb174[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb162[i0, i1] -> Stmt_bb174[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb162[1023, 1023] -> Stmt_bb174[0, 0]; Stmt_bb126[1023, 1023] -> Stmt_bb138[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb126[i0, i1] -> Stmt_bb138[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb126[1023, 1023] -> Stmt_bb138[0, 0]; Stmt_bb90[1023, 1023] -> Stmt_bb102[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb102[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb90[1023, 1023] -> Stmt_bb102[0, 0]; Stmt_bb138[1023, 1023] -> Stmt_bb150[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb138[i0, i1] -> Stmt_bb150[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb138[1023, 1023] -> Stmt_bb150[0, 0]; Stmt_bb66[1023, 1023] -> Stmt_bb78[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb78[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb66[1023, 1023] -> Stmt_bb78[0, 0]; Stmt_bb78[1023, 1023] -> Stmt_bb90[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb90[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb78[1023, 1023] -> Stmt_bb90[0, 0]; Stmt_bb114[1023, 1023] -> Stmt_bb126[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb126[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb114[1023, 1023] -> Stmt_bb126[0, 0] } ; CHECK-NEXT: WAR dependences: -; CHECK-NEXT: { } +; CHECK-NEXT: { Stmt_bb150[1023, 1023] -> Stmt_bb162[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb150[i0, i1] -> Stmt_bb162[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb150[1023, 1023] -> Stmt_bb162[0, 0]; Stmt_bb174[1023, 1023] -> Stmt_bb186[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb174[i0, i1] -> Stmt_bb186[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb174[1023, 1023] -> Stmt_bb186[0, 0]; Stmt_bb102[1023, 1023] -> Stmt_bb114[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb114[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb102[1023, 1023] -> Stmt_bb114[0, 0]; Stmt_bb42[1023, 1023] -> Stmt_bb54[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb54[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb42[1023, 1023] -> Stmt_bb54[0, 0]; Stmt_bb54[1023, 1023] -> Stmt_bb66[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb66[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb54[1023, 1023] -> Stmt_bb66[0, 0]; Stmt_bb31[1023, 1023] -> Stmt_bb42[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb42[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb31[1023, 1023] -> Stmt_bb42[0, 0]; Stmt_bb162[1023, 1023] -> Stmt_bb174[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb162[i0, i1] -> Stmt_bb174[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb162[1023, 1023] -> Stmt_bb174[0, 0]; Stmt_bb126[1023, 1023] -> Stmt_bb138[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb126[i0, i1] -> Stmt_bb138[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb126[1023, 1023] -> Stmt_bb138[0, 0]; Stmt_bb90[1023, 1023] -> Stmt_bb102[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb102[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb90[1023, 1023] -> Stmt_bb102[0, 0]; Stmt_bb138[1023, 1023] -> Stmt_bb150[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb138[i0, i1] -> Stmt_bb150[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb138[1023, 1023] -> Stmt_bb150[0, 0]; Stmt_bb66[1023, 1023] -> Stmt_bb78[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb78[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb66[1023, 1023] -> Stmt_bb78[0, 0]; Stmt_bb78[1023, 1023] -> Stmt_bb90[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb90[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb78[1023, 1023] -> Stmt_bb90[0, 0]; Stmt_bb114[1023, 1023] -> Stmt_bb126[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb126[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb114[1023, 1023] -> Stmt_bb126[0, 0] } ; CHECK-NEXT: WAW dependences: ; CHECK-NEXT: { Stmt_bb150[1023, 1023] -> Stmt_bb162[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb150[i0, i1] -> Stmt_bb162[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb150[1023, 1023] -> Stmt_bb162[0, 0]; Stmt_bb174[1023, 1023] -> Stmt_bb186[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb174[i0, i1] -> Stmt_bb186[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb174[1023, 1023] -> Stmt_bb186[0, 0]; Stmt_bb102[1023, 1023] -> Stmt_bb114[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb102[i0, i1] -> Stmt_bb114[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb102[1023, 1023] -> Stmt_bb114[0, 0]; Stmt_bb42[1023, 1023] -> Stmt_bb54[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb42[i0, i1] -> Stmt_bb54[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb42[1023, 1023] -> Stmt_bb54[0, 0]; Stmt_bb54[1023, 1023] -> Stmt_bb66[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb54[i0, i1] -> Stmt_bb66[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb54[1023, 1023] -> Stmt_bb66[0, 0]; Stmt_bb31[1023, 1023] -> Stmt_bb42[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb31[i0, i1] -> Stmt_bb42[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb31[1023, 1023] -> Stmt_bb42[0, 0]; Stmt_bb162[1023, 1023] -> Stmt_bb174[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb162[i0, i1] -> Stmt_bb174[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb162[1023, 1023] -> Stmt_bb174[0, 0]; Stmt_bb126[1023, 1023] -> Stmt_bb138[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb126[i0, i1] -> Stmt_bb138[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb126[1023, 1023] -> Stmt_bb138[0, 0]; Stmt_bb90[1023, 1023] -> Stmt_bb102[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb90[i0, i1] -> Stmt_bb102[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb90[1023, 1023] -> Stmt_bb102[0, 0]; Stmt_bb138[1023, 1023] -> Stmt_bb150[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb138[i0, i1] -> Stmt_bb150[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb138[1023, 1023] -> Stmt_bb150[0, 0]; Stmt_bb66[1023, 1023] -> Stmt_bb78[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb66[i0, i1] -> Stmt_bb78[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb66[1023, 1023] -> Stmt_bb78[0, 0]; Stmt_bb78[1023, 1023] -> Stmt_bb90[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb78[i0, i1] -> Stmt_bb90[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb78[1023, 1023] -> Stmt_bb90[0, 0]; Stmt_bb114[1023, 1023] -> Stmt_bb126[o0, o1] : o0 <= 1023 and o1 >= 0 and -1024o0 < o1 <= 1023; Stmt_bb114[i0, i1] -> Stmt_bb126[0, 0] : i0 >= 0 and 0 <= i1 <= 1048574 - 1024i0 and i1 <= 1023; Stmt_bb114[1023, 1023] -> Stmt_bb126[0, 0] } ; CHECK-NEXT: Reduction dependences: Index: test/DependenceInfo/reduction_simple_iv_debug_wrapped_dependences.ll =================================================================== --- test/DependenceInfo/reduction_simple_iv_debug_wrapped_dependences.ll +++ test/DependenceInfo/reduction_simple_iv_debug_wrapped_dependences.ll @@ -10,7 +10,7 @@ ; CHECK-NEXT: RAW dependences: ; CHECK-NEXT: { [Stmt_for_cond[i0] -> MemRef_sum[0{{\]\]}} -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0{{\]\]}} : 0 <= i0 <= 99 } ; CHECK-NEXT: WAR dependences: -; CHECK-NEXT: { } +; CHECK-NEXT: { [Stmt_for_cond[i0] -> MemRef_sum[0{{\]\]}} -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0{{\]\]}} : 0 <= i0 <= 99 } ; CHECK-NEXT: WAW dependences: ; CHECK-NEXT: { [Stmt_for_cond[i0] -> MemRef_sum[0{{\]\]}} -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0{{\]\]}} : 0 <= i0 <= 99 } ; CHECK-NEXT: Reduction dependences: Index: test/DependenceInfo/reduction_simple_privatization_deps_2.ll =================================================================== --- test/DependenceInfo/reduction_simple_privatization_deps_2.ll +++ test/DependenceInfo/reduction_simple_privatization_deps_2.ll @@ -3,7 +3,7 @@ ; CHECK: RAW dependences: ; CHECK-NEXT: { Stmt_S2[i0] -> Stmt_S0[1 + i0] : 0 <= i0 <= 98; Stmt_S0[i0] -> Stmt_S1[i0, o1] : 0 <= i0 <= 99 and 0 <= o1 <= 99; Stmt_S1[i0, i1] -> Stmt_S2[i0] : 0 <= i0 <= 99 and 0 <= i1 <= 99 } ; CHECK-NEXT: WAR dependences: -; CHECK-NEXT: { } +; CHECK-NEXT: { Stmt_S2[i0] -> Stmt_S0[1 + i0] : 0 <= i0 <= 98; Stmt_S0[i0] -> Stmt_S1[i0, o1] : 0 <= i0 <= 99 and 0 <= o1 <= 99; Stmt_S1[i0, i1] -> Stmt_S2[i0] : 0 <= i0 <= 99 and 0 <= i1 <= 99 } ; CHECK-NEXT: WAW dependences: ; CHECK-NEXT: { Stmt_S2[i0] -> Stmt_S0[1 + i0] : 0 <= i0 <= 98; Stmt_S0[i0] -> Stmt_S1[i0, o1] : 0 <= i0 <= 99 and 0 <= o1 <= 99; Stmt_S1[i0, i1] -> Stmt_S2[i0] : 0 <= i0 <= 99 and 0 <= i1 <= 99 } ; CHECK-NEXT: Reduction dependences: Index: test/DependenceInfo/reduction_simple_privatization_deps_w_parameter.ll =================================================================== --- test/DependenceInfo/reduction_simple_privatization_deps_w_parameter.ll +++ test/DependenceInfo/reduction_simple_privatization_deps_w_parameter.ll @@ -3,7 +3,7 @@ ; CHECK: RAW dependences: ; CHECK-NEXT: [N] -> { Stmt_S0[] -> Stmt_S1[o0] : N >= 11 and 0 <= o0 <= 1023; Stmt_S1[i0] -> Stmt_S2[] : N >= 11 and 0 <= i0 <= 1023 } ; CHECK-NEXT: WAR dependences: -; CHECK-NEXT: [N] -> { } +; CHECK-NEXT: [N] -> { Stmt_S1[i0] -> Stmt_S2[] : N >= 11 and 0 <= i0 <= 1023 } ; CHECK-NEXT: WAW dependences: ; CHECK-NEXT: [N] -> { Stmt_S0[] -> Stmt_S1[o0] : N >= 11 and 0 <= o0 <= 1023; Stmt_S1[i0] -> Stmt_S2[] : N >= 11 and 0 <= i0 <= 1023 } ; CHECK-NEXT: Reduction dependences: